this is expected to grow to 12.3 billion by 2022 [2]. Many of these devices will be data-processing-capable nodes in the hands of users that facilitate rapidly growing data-intensive applications running at the network edge, e.g., social networking, video streaming, and distributed data analytics. Given the bursty nature of user demands, when certain devices are occupied with processing for computationally-intensive applications, e.g., face recognition, 3D modeling/gaming, and augmented/virtual reality (AR/VR), it may be desirable for them to offload their data to devices with underutilized resources [3]- [5]. Traditionally, cloud computing architectures, such as Amazon Web Services and Microsoft Azure, have been adopted for such data intensive applications, but the exponential rise in data generation at the edge is making centralized architectures infeasible for providing latency-sensitive quality of service at scale [2].

As a current trend in wireless networks is reducing cell sizes [6], many 5G networks will be dense with small cell coverage areas and networks composed of several smaller subsets [7]. Networks of small subnets combined with improved computational and storage capabilities of edge devices are enabling mobile edge computing (MEC) architectures. At a high level, MEC leverages radio access networks (RANs) to increase the amount of computing power located close to the end user, which enables the end user to offload computations (e.g., using a central processing entity) as shown in Fig. 1(a) [8]- [17]. In an MEC architecture, the edge servers have high-performance computing units which can process large amounts of computationally intensive tasks efficiently. This concept has been extended to "helper" edge server architectures as well, where devices with idle computation resources become (small) edge servers [18]- [23].

The current trend in distributed computing, though, is a migration to architectures that are more decentralized than MEC. This is due to the fact that all edge nodes can take part in data offloading at different times because of the advances in 5G communication technologies in conjunction with improved computational capabilities of individual devices. For this reason, device-to-device (D2D) network architectures (in Fig. 1(b)) that were previously studied in 4G LTE standards now hold the promise of providing distributed computing at scale [24].

Unlike the MEC system in Fig. 1(a), distributed computing in the D2D network of Fig. 1(b) will have more complicated topology management needs that must be considered together with the management of device resources. From a computation perspective, the edge nodes that receive offloaded tasks must have a suitable strategy for allocating its central processing unit (CPU) and/or storage resources to the tasks. From a communication perspective, wireless transmissions between edge nodes will inevitably incur inter-channel interference due to concurrent data offloading. In contemporary wireless networks, devices are often equipped with multiple antennas to support multiple input multiple output (MIMO) communications, and the ability to communicate over different subchannels. Theoretically, having both multiple transmit and multiple receive antennas (i.e., a MIMO channel) provides an additional spatial dimension for communication and yields a degree-of-freedom gain [25], which can be leveraged to mitigate such inter-channel interference. This motivates interference management techniques that consider the joint effects of subchannel allocations, transmission powers, MIMO beamforming, and other device transmit resources.

The focus of this paper is on addressing these challenges. Specifically, we develop methodologies that jointly optimize computation and communication resources together with topology configuration in D2D wireless edge computing systems. These methodologies will aim to minimize the overhead incurred from communication and computation, measured in terms of time delay/latency and energy consumption incurred from processing tasks in the D2D network.

We discuss related works on task offloading, resource management, and edge computing. We divide our analysis into two main categories: MEC and D2D.

1) MEC Systems: Researchers have developed methods for resource management and offloading decision-making to maximize MEC system performance. Offloading decisions were thoroughly studied in [8], where management of device resources is assumed to be fixed. On the other hand, under the assumption that offloading decisions are given, studies have considered optimal allocations of CPU and subchannel resources [9], and have also considered these together with beamformer design for MIMO systems [14], [15]. Recently, offloading decisions have been considered together with management of resources in MEC systems such as CPU [10]- [13], subchannels [12], [17], transmit powers [12], [13], [16], and beamformer design [13].

Though we focus on D2D in this paper, as mentioned previously, newer MEC architectures allow idle devices in close proximity to be dedicated computing nodes. Therefore, optimization in MEC systems can be viewed as a special case of D2D networks, where offloading is restricted to specific devices unidirectionally. On the contrary, D2D networks allow multi-directional task offloading between devices. This requires additional optimization components to capture the multi-directional task offloading, CPU allocation across possibly multiple tasks at each device, and MIMO combiner design at receive devices, which are not considered in MEC systems.

2) D2D Networks: Several prior works have focused on optimizing communication quality in D2D systems, where the objectives have been to maximize sum-rate [26]- [31], spectral efficiency [32], or signal-to-noise ratio (SINR) [33], with consideration of device and channel resources such as subchannels [26], [27], [29]- [31], transmit powers [27], [30], [31], and beamformer design for MIMO systems [32], [33]. For beamforming specifically, a coordinated beamforming strategy, such as the weighted minimum mean square error (WMMSE) approach, can be used to maximize standard communication measures (e.g., sum-rate) [34]. However, conventional beamforming strategies are not designed to consider time delay and energy consumption in a joint overhead metric for D2D. Furthermore, in D2D edge computing, the total network overhead is also impacted by other system parameters, such as subchannels, CPU allocation, and topology configuration.

Works on D2D in edge computing have primarily focused on D2D-enabled (or D2D-assisted) MEC systems where several helper nodes are available as dedicated nodes for computing together with the edge server. In this respect, within a fixed topology, [18] investigated energy minimization based on CPU and transmission power allocation, and [19] studied joint time and energy minimization based on CPU, subchannel, and transmission power allocation. On the other hand, for a given set of system resources, the strategy of topology reconfiguration was discussed to minimize total energy in [20]. Some recent works have addressed topology configuration together with the allocation of specific device resources such as CPU [21]- [23] and power [21], [22]. Advanced offloading strategies for topology configuration have also been introduced in vehicular fog computing [35], [36]. In [35], a task offloading method leveraging pricing-based matching was proposed to minimize the total network delay under utility constraints. In [36], an ADMM-based approach was proposed for energy minimization via partial offloading decisions subject to computing capability and latency constraints. Overall, we are not aware of any work that has addressed computation, communication, and topology configuration together in a unified optimization model for D2D edge computing, which is the focus of our paper.

Compared to the related works discussed in Section I-A, the contributions of this paper are as follows:

Authorized licensed use limited to: University of Kansas Libraries. Downloaded on July 16,2022 at 16:56:39 UTC from IEEE Xplore. Restrictions apply.

• We formulate a unified optimization model for D2D edge computing networks that minimizes total network overhead, defined as the weighted sum of time and energy consumption required to process a given task. In doing so, we consider different dimensions of MIMO wireless for combating interference caused by concurrent data offloading, where each device is equipped with multiple antennas. Our model includes a framework for joint topology configuration, CPU allocation, subchannel allocation, and beamformer design for MIMO systems (Sections II and III). • We propose two methods for minimizing the total network overhead in our model, which we refer to as semi-exhaustive search optimization and efficient alternate optimization.

We compare these two methods in terms of optimality guarantees and computational complexity in solving our non-convex problem. While the semi-exhaustive search optimization can be viewed as a "best effort" to obtaining the optimal solution, its complexity becomes problematic as the network size grows, which motivates the efficient alternate optimization (Section IV). • In developing these methods, we study the decomposition of the optimization into several subproblems: topology design, CPU allocation, and beamformer design. In doing so, we develop a novel beamforming algorithm, minimum communication overhead beamforming (MCOB), that can be seen as a generalization of the WMMSE technique to utility functions incorporating both time and energy overhead. We prove that MCOB obtains the optimal beamformer for an MMSE receiver (Section IV). • We conduct several numerical experiments to evaluate the performance of our network overhead optimization methodology. Our results show, for example, that our efficient alternate optimization algorithm can reduce the total overhead in D2D networks by 20%-30% compared to computation without offloading (Section V).

NETWORK MODEL In this section, we develop our models for computational tasks, wireless signals, and the allocation of network resources in D2D systems.

We let K = {1, 2, . . . , K} be the set of nodes in the D2D network, with a total of K nodes. Each node k ∈ K has a task to be completed, consisting of computational work involved in data processing, where the objective of the data processing is to perform a transformation from input to output data. In this paper, we adopt an indivisible task model [37], where a task is processed as a whole. 1 A task is considered to be completed when the input data is successfully processed to the desired output. In general, task completion requires computational resources including CPU, RAM, and storage. In this paper, Fig. 2. Wireless device-to-device (D2D) network model among K nodes. Node k transmits with a beamformer f k to receive node k through subchannel i characterized as H (i) k,k , which is decoded with a receive combiner z k ,i . similar to previous works [11]- [13], [21]- [23], we focus on CPU as the computation resource. In case of mobile devices, many of today's tasks require computation-intensive processing with high CPU requirements, such as 3D-gaming and location-based augmented/virtual reality (AR/VR) [3]- [5].

To quantify the complexity of the task for node k (which we will refer to as task k for brevity), we introduce the task size I k (in bits), which is the length of the bit stream of input data consisting of task k. In other words, the bit stream of input data is represented as {0, 1} I k . Then, the task workload is denoted as µ k I k (in cycles), where µ k (in cycles/bit) is the processing density, meaning how many CPU cycles are required to process a bit of data. That is, µ k I k represents total number of CPU cycles required to complete task k. The processing density µ k depends on the application; for example, in the case of the audio signal detection in [38], since 500 cycles are required for processing 1 bit of data, µ k is 500.

Fig. 2 demonstrates our wireless D2D network model among a set of K nodes. We assume that the nodes can transmit using multiple antennas on S subchannels, where the set of subchannels is denoted S = {1, 2, . . . , S}. Each node k ∈ K receives a signal y k ,i through subchannel i ∈ S as

where node k uses only one subchannel for transmission; if b k,i = 1, then b k,j = 0 ∀j = i.

At receive node k on subchannel i, we consider a linear receive combiner z k ,i ∈ C N k so that the estimated value ŷk ,i is given by

where the superscript H denotes the conjugate transpose.

The assignment of tasks to either offloading or local processing determines the D2D network topology. Constraints on how subchannels and processing resources are allocated must be specified based on these assignments.

1) Task Assignment: Each task k can be either processed locally at node k or offloaded to another node k for processing. We define a k,k ∈ {0, 1} as the task assignment variable of whether task k is assigned to node k for k, k ∈ K. If a k,k = 1, then we have local processing of task k at node k. On the other hand, if a k,k = 1 for some k = k, then we have offloaded processing where task k is offloaded from k to k and processed at node k . The set of task assignments is denoted by

(

Since each task should be processed as a whole, task k should be assigned to only one node, i.e.,

For efficient offloading decisions, it is important to consider the channel matrices between nodes, as well as the subchannels and available computing capabilities of nodes. 22) Subchannel Allocation: The task assignment specifies the configuration of how the K nodes communicate with each other. Therefore, the subchannel allocation variable b k,i is related to task assignment variable a k,k as

a k,k = 0 implies node k is a transmit node, because task k is not locally processed at node k, implying transmission to another node. In this case, transmit node k uses one of the subchannels for transmission, i.e., S i=1 b k,i = 1. On the other hand, if node k is not a transmit node, then a k,k = 1 and there is no subchannel allocation for node k, i.e., S i=1 b k,i = 0. Each of the S subchannels is assumed to have equal and non-overlapping bandwidth of width W . Consider, however, the case that node k receives multiple tasks from multiple transmit nodes. If same subchannel i is used by these transmitters, the receive node must jointly decode the data of tasks, which leads to degraded decoding performance. Therefore, in this paper, we follow prior work and assume that the transmit nodes that transmit to the same receive node use different subchannels [17]. In other words, for each receive node k , we restrict the number of transmitters on subchannel i according to

where A k denotes the set of transmit nodes that transmit to the receive node k given by

3) Computational Resource Allocation: Consider that node k has multiple tasks to complete (its own and/or those offloaded to it). Its computational resource (CPU) F k will be shared across these multiple tasks, where F k (in cycles/sec or Hz) denotes the available CPU of node k . We define the amount of CPU resource of node k allocated to task k as F k,k , which is subject to the constraints

In ( 8), the total CPU resource allocated cannot exceed the available CPU resource for each node k . In ( 9), a k,k = 0 implies that task k has not been assigned to node k , so no CPU resources will be allocated to task k. In addition, the allocated CPU F k,k is restricted to a positive real value.

In this section, we formulate the optimization problem for minimizing D2D network task completion overhead. We define the total network overhead as a cost function to be minimized, consisting of both computation and communication overhead.

We first define the computation overhead associated with node k offloading to node k . Based on the models from Section II, we can compute the computation time T comp (k, k ) (in seconds) of task k computed at node k according to

The computation energy consumption E comp (k, k ) (in Joules) can be computed as

where κ k is the energy coefficient (in Joules • seconds 2 /cycles 3 ) of node k that depends on the processor chip architecture [39]. Here, κ k F 2 k,k denotes the energy consumption per cycle (in units of Joules/cycle).

We define the computation overhead Y comp (k, k ) as the weighted sum of time and energy consumption, given by

where β k ∈ [0, 1] is a demand overhead factor. From ( 10) and ( 11

We now define the communication overhead associated with transmission of a task from node k to k . When k = k , we can write the signal to interference plus noise ratio (SINR) from node k to node k on subchannel i as

where all other transmit nodes = k using subchannel i are interferences to the data stream of node k on subchannel i.

Assuming perfect channel state information (CSI), we can write the maximum achievable data rate R

where W is the bandwidth of each frequency subchannel. Then, the total maximum achievable data rate from node k to node k over all subchannels is

When node k is a transmitter, by (5), only one subchannel is active. In other words, when b

Given the data rate, we can compute the communication time T comm (k, k ) (in seconds) for offloading task k to node k as

The communication energy consumption for node k corresponding to the link from k to k is

where P c is the circuit power including power dissipations in the transmit filter, mixer, and digital-to-analog converter, which are independent of the actual transmit power

We allocate the same β k to the computation and communication overhead definitions (in ( 12) and ( 19)) because β k is the weighting factor between time delay and energy consumption for task k, which intuitively should be the same for both types of overhead. 3 There is a tradeoff between T comm (k, k ) and E comm (k, k ) with respect to the transmit power

Recall that there are two possibilities for task k: (i) local processing, i.e., a k,k = 1, and (ii) offloaded processing, i.e., a k,k = 1 for some k = k. Local processing only incurs computation overhead Y comp (k, k) while offloaded processing incurs both communication and computation overhead,

With this, for a given D2D network topology configuration, we can write the total network overhead to complete all tasks in the network as

We now formulate the problem of jointly optimizing the D2D network parameters to achieve the minimum total network overhead Y total . The degrees of freedom available are the task assignments {a k,k }, computational resource allocations {F k,k }, subchannel allocations {b k,i }, and beamformer design variables involving transmit beamformers {f k } and receive combiners {z k ,i }. The optimization problem is given by: minimize

Constraints ( 22)-( 24) and ( 26)-( 27) account for task assignment, subchannel allocation, and CPU allocation requirements, which were described in Section II-C. ( 25) captures the constraint for the transmission power budget P k of an individual node. Note that there is no constraint on {z k ,i } such as a maximum magnitude restriction because the data rate R k,k is not affected by the magnitude of z k ,i .

Assuming all nodes have N antennas, meaning that N k = N for all k, the optimization is a mixed integer program (MIP) with K(N +N S+K) non-integer variables from {f k }, {z k ,i }, {F k,k }, and K(K + S) integer variables from {a k,k }, {b k,i }. The function Y comm (k, k ) is non-convex with respect to {f k } and {z k ,i }, which makes the problem a non-convex MIP. Existing solvers for non-convex MIPs do not scale well with the number of variables [40], and even in a relatively small D2D setting with K = 20 nodes, S = 5 subchannels, and N = 10 antennas, our problem has already more than 2000 variables. In Section IV, we turn to addressing the challenge of solving this optimization at scale.

A few assumptions made on the D2D model in this section are noteworthy. First, although the network states will be dynamic over time, we assume a quasi-static scenario with K active nodes and fixed channels during one codeword block, similar to previous works [9], [12]- [15], [18], [19], [21], [22]. The algorithms we develop for solving the optimization ( 21)- (27) in Section IV could then be applied to each quasi-static scenario as the number of nodes and channel conditions change, or at some suitable time interval. Related to this, we focus our optimization on the tasks generated at nodes in a single time period. A straightforward way to extend this approach to a dynamic task generation scenario is through queuing [41], where new tasks are queued at nodes and processed by the optimization in a series of frames. We provide an experiment on this in Appendix D-C.

Second, we consider operator-assisted D2D networks [42]- [44], where a network operator functions as a centralized controller for resource management. The network operator, e.g., a base station (BS), executes our algorithms based on knowledge of the required network information, such as task size, CSI, and availability of subchannels and CPUs. This aligns with the current framework of cellular systems found in practice, where mobile devices typically have their radio access and resource allocation controlled through information sharing with the BS [45]. Our methodology can thus be seen as enabling distributed task processing in the data plane via centralized optimization for variable design in the control plane. The tasks generated by the nodes are processed in a distributed way, i.e., through offloading between devices or local processing, while the network operator will solve the optimization for orchestrating communication and computation resources.

Remark 1: The BS, as a network operator, can acquire the CSI of devices through standard protocols of existing cellular network architectures. First, for CSI estimation at each device, concurrent channel estimation from multiple transmit devices can be conducted via well-established frameworks in the Long-Term Evolution (LTE) [45] and 5G new radio (5G-NR) [46] standards, using UE-specific reference signals.

Since each device's wireless channel is temporally correlated in practice, CSI can be estimated with only a few parameters via channel tracking techniques [47]- [49]. Second, for CSI acquisition at the BS, the BS can obtain measures such as channel quality information (CQI), precoding matrix indicator (PMI), and rank indicator (RI) from the devices, without receiving entire channel matrices, through standard CSI reporting frameworks [45]. Since the number of CSI bits received at the BS would be very small compared to the sizes of modern computing tasks, the communication overhead for CSI acquisition can be safely ignored in the optimization. Although the CSI acquired at the BS will be imperfect, we will demonstrate in Section V that the effect of imperfect CSI (e.g., refer to [50]- [52]) has only a small effect on our proposed network overhead optimization.

Third, we do not consider the process of transferring the computation result of an offloaded task back to the source node, similar to previous works, e.g., [8], [53]. This assumption is reasonable since for many applications (e.g., facial recognition), the size of the output data (e.g., the recognized individuals) is in general much smaller than the size of the input data (e.g., the original full images). Therefore, we consider that the output data is negligible in size compared with the task so that it can be transferred through the network with minimal load.

In this section, we develop two methods for solving the minimum overhead optimization problem ( 21)- (27). The first method, semi-exhaustive search, provides a best-effort attempt to obtain the optimal solution, but has exponential complexity. The second method, efficient alternate optimization, reduces the complexity to polynomial time, for which we use semi-exhaustive search as an optimality benchmark. As a component of these two methods, we will derive a new algorithm for MIMO beamforming (Section IV-A2) which minimizes communication overhead in D2D wireless edge networks.

Given the task assignments {a k,k } and subchannel allocations {b k,i } variables are binary, an intuitive approach to solving the optimization is to exhaustively search through all of their possibilities, so long as the search space is not prohibitively large. Then, for each possibility, we can solve for the non-integer variables {f k }, {z k ,i }, and {F k,k }. We refer to this method as semi-exhaustive search. The overall procedure is described in Algorithm 1: each choice of {a k,k } and {b k,i } satisfying constraints ( 22)-( 24) is considered. For given task assignments {a k,k }, we solve the CPU allocation problem for the processing resources {F k,k }, which is a convex problem. In addition, for fixed task assignments {a k,k } and subchannel allocations {b k,i }, we solve the problem with respect to the beamformers {f k } and combiners {z k ,i }, which is a beamformer design problem. We will develop solutions to these two problems in the following.

Update Y total = Y total and G ← G. 9: end if 10: until There is no possible case of {a k,k } and {b k,i } 11:

1) CPU Allocation: With task assignments {a k,k } determined, the optimization problem ( 21)-( 27) with respect to CPU allocations {F k,k } can be reduced to minimize

subject to Constraints ( 26)

The problem can be decomposed into K independent subproblems: each node can allocate its own CPU regardless of the others. For each node k ∈ K, the optimization problem is given as minimize

Note that Y comp (k, k ) is convex with respect to {F k,k } (since all parameters in Y comp (k, k ) are positive) and the constraints ( 26)-( 27) are also convex. Therefore, optimization (28)-( 29) is convex. The decomposed subproblem (30)- (32) for each k is also a convex problem that can be solved accordingly.

2) Beamformer Design: With task assignments {a k,k } and subchannel allocations {b k,i } determined, the optimization problem ( 21)-( 27) with respect to the beamformer design variables f k and z k ,i ∀k, k ∈ K, i ∈ S, can be reduced to minimize

We refer to this as the minimum communication overhead beamforming (MCOB) problem. Conventionally, objective functions in beamforming resource allocation problems take the form of sum rate or sum harmonic rate utility functions [54]. In our D2D setting, the objective instead becomes the weighted sum of time and energy consumption for transmission.

We are interested in determining the variables f k and z k ,i related to active data streams, i.e., for k, k , and i with a k,k = 1 and b k,i = 1. Denote the set of all transmit nodes as

to one k on one subchannel i, we index this datastream as the tuple (k, k , i). 4 Our problem can be then rewritten as minimize

This communication overhead minimization problem is non-convex and hard to solve due to the logarithm term in the data rate R k,k in (16). However, if the beamformers {f k } are fixed,foot_5 minimizing (35) leads to the well known minimum mean square error (MMSE) receiver. If we restrict ourselves to using MMSE receiver, we can transform the data rate into a quadratic form with the following lemma.

Lemma 1: With an MMSE-designed receiver, the data rate in (16) can be represented in quadratic form as

where

w k ∈ R + is an auxiliary variable, and the term e mse k is the MSE of receive node k given by

The proof follows from Theorem 1 in [34]. Since u k in ( 38) is concave with respect to each of the variables {f k }, z k ,i and w k , the optimal solution to (37) is

where

,k + σ 2 I. Note that z k ,i is the MMSE receiver solution.

Using the formulation in Lemma 1, the optimization problem ( 35)-( 36) can be written as minimize

where

For a given {f k }, the optimal solutions of z k ,i and w k for ( 42)-( 43) are given by ( 40) and (41). Moreover, for given z k ,i and w k , the function g k is convex and u k is concave with respect to {f k }. Optimization ( 42)-( 43) with respect to {f k } is thus a convex-concave multiple-ratio fractional programming problem [55], which is not convex. Motivated by [56], we will exploit the fractional programming approach to solve it. Specifically, we have the following theorem, which introduces an equivalent problem that is convex with respect to each individual set of variables {f k }, {z k ,i }, and {w k } when two other sets of variables {λ k } and {γ k } are introduced.

Theorem 1: Consider the optimization problem minimize

)

and the system equations

If { fk }, {z k ,i }, and { wk } are solutions of the problem (45)-( 46) and also simultaneously satisfy the system equations in (47), then they are optimal solutions to (42)-( 43). The proof of Theorem 1 is relegated to Appendix A. Optimization ( 42)-( 43) is equivalent to ( 45)-( 47) in the sense that they have the same globally optimal solutions. Using the fact that optimization (45)-( 46) is convex with respect to each set of variables {f k }, {z k ,i }, and {w k }, we will solve for each set, iteratively, which will yield solutions with {λ k } and {γ k } being fixed. Specifically, we propose an iterative algorithm to solve (45)-( 46) and satisfy the system equations (47) simultaneously: given {λ k } and {γ k }, we solve for {f k }, {z k ,i }, and {w k }, and then update {λ k } and {γ k } from the updated variables {f k }, {z k ,i }, and {w k }.

To solve ( 45)-( 46) for fixed {λ k } and {γ k }, we use the block coordinate descent (BCD) method [57], where each set of the variables is solved fixing the other two. In particular, with {f k } and {w k } fixed, the optimal solution of each z k ,i is given in (40). With {f k } and {z k ,i } fixed, the optimal solution of each w k is given in (41). The remaining part is to solve for {f k } with {z k ,i } and {w k } fixed, which is not-trivial. To solve for {f k }, we reorganize the objective function in (45) by replacing u k and g k with (38) and (44): 40) and ( 41). Update the system equations {λ 52). 8: Set j = j + 1.

where

In (49), for the tuple ( , k ( ), i( )), k ( ) denotes the receive node of the transmit node and i( ) denotes the subchannel that uses. Since the first term in ( 48) is constant with respect to {f k }, we are only interested in the second and third terms. The optimization can be decoupled into |K Tx | independent subproblems, one for each f k , as minimize

A closed-form solution can be derived for ( 50)-( 51) with the Karush-Kuhn-Tucker (KKT) conditions [58], since the reduced problem ( 50)-( 51) is a quadratically constrained quadratic program (QCQP). The detailed derivation of this procedure is given in Appendix C. Through this process, we have transformed the original communication overhead minimization problem ( 33)-( 34) to a form in ( 40)-( 41), ( 50)-( 51) which allows each beamformer to be designed individually, under the BCD framework. The solution f k minimizes the communication overhead caused by concurrent task offloading, for a given topology configuration, subchannel allocation, and MMSE combiner at the receive nodes.

With {f k }, {z k ,i }, and {w k } in hand, we can then update {λ k } and {γ k } using (47). The overall MCOB algorithm is demonstrated in Algorithm 2, which determines {f k }, {z k ,i }, {w k }, {λ k }, and {γ k } that are the solutions to ( 45)- (47). The algorithm runs until the objective function value ρ in (45) changes less than a threshold and the system equation error is also less than that. We define the system equation error as

In this section, we propose a computationally efficient alternative to the semi-exhaustive search optimization (Algorithm 1) that avoids the brute force strategy of handling the binary variables {a k,k } and {b k,i }. This method, which we term efficient alternate optimization, is demonstrated in Algorithm 3. The key idea is that we divide the optimization ( 21)-( 27) into two subproblems and solve them alternately. The first problem is the beamformer design for the variables {f k } and {z k ,i } given task assignments {a k,k } and subchannel allocations {b k,i }, which we already developed in Algorithm 2. The second problem is the resource allocation design for {a k,k }, {b k,i }, and CPU allocation {F k,k } with given beamformer design variables {f k } and {z k ,i }. While each sub-algorithm is dedicated to each sub-problem, the overall composition via iterative alternating optimization is aiming to solve the overall problem ( 21)- (27). The experiments in Section V demonstrate that this efficient alternate optimization achieves a substantial reduction in network overhead compared to local processing.

Algorithm 4 demonstrates our approach for the resource allocation problem. The key idea is that at each step, we determine the data stream tuple (k, k , i) that provides the most reduction in overhead, and allocate these resources accordingly. The process continues until there are no cases that any tuple will improve the optimization objective. The maximizer for the current step is determined as

where K Tx denotes the candidate set of transmit nodes, K Rx denotes the candidate set of receive nodes, and η k,k ,i is the offloading benefit provided by tuple (k, k , i). The offloading benefit is defined as

which quantifies the reduction in network overhead by offloading from node k to k on subchannel i on top of the current resource allocations. Y loc denotes the total network overhead in case of no offloading from k to k , while Y off denotes the total network overhead in case of offloading. Algorithm 4 begins with K Tx = K, K Rx = K, meaning that all of the nodes are candidates for transmit and receive. With Algorithm 4 Greedy Algorithm for Task Assignment, Subchannel Allocation, and CPU Allocation

The Y loc and Y off are given in ( 55)&( 57). 28)-( 29). 11:

For a given A and B, Y loc is computed as

where

obtained by the optimal solution to ( 28)-( 29) for the allocation set A loc , and

A loc denotes the new task assignment set when node k and k process locally. In Algorithm 4, k is added as a local processing node. Otherwise, it might happen that at current step, task k occupies all of the CPU of node k without consideration of allocating CPU to task k . Then, k has no choice but to offload to other nodes at the next step.

To overcome this, we consider the local processing of task k when task k is being considered for offloading to node k . On the other hand, Y off is given by

where Y comp (k, k ) is the optimal value for the allocation set A off , and

A off denotes the new task assignment set when node k offloads to k . B off denotes the new subchannel allocation set when node k uses subchannel i for offloading. In each step of Algorithm 4, as long as the best data stream ( k, k , ĩ) from ( 53) has a positive offloading benefit η k, k , ĩ, then these resources are allocated. This means task k is offloaded to node k on subchannel ĩ, and node k locally processes its own task k . As a result, we update

Once there is no data stream with positive offloading benefit, the algorithm is terminated, and all remaining candidate transmit nodes are assigned to local processing.

As mentioned previously, Algorithm 1 (semi-exhaustive search) represents a best-effort approach for solving the optimization ( 21)-( 27) with manageable complexity for small networks. We will explain this reasoning now. Then, in Section IV-D, we will compare the computational complexities between Algorithms 1 and 3.

The optimal solution to ( 21)-( 27) can be obtained (in theory) by solving for the non-integer variables for all possible combinations of integer variables. If we represent the objective function Y total in its functional form

then by fixing the binary variables as {ā k,k } and { bk,i }, we are left with minimize (59) subject to the constraints. Since the CPU allocation variable {F k,k } is not affected by the beamformer design variables {f k } and {z k ,i }, and vice versa, this optimization can be divided into two independent problems given by minimize

(61) In summary, the optimization variables in (59) are separable, and the problem can be decomposed into (60) and ( 61) for every combination of {ā k,k } and { bk,i }.

Consider how the proposed semi-exhaustive search optimization addresses (60) and (61). Problem ( 60) is convex: for this, we arrive at the convex problem (30)-( 32) decomposed across nodes. Thus, we obtain the optimal solution {F k,k } for this set of integer variables as

In contrast, problem (61) is non-convex. To solve it, we developed the MCOB algorithm for optimizing the receive combiner {z k ,i } fixing the transmit beamformer {f k } and vice versa (see Algorithm 2). The solution for {z k ,i } for a fixed { fk } based on an MMSE receiver is given in (40), such that

The solution {f k } for a fixed {z k ,i } is given in ( 50)- (51), such that

Although {f k } and {z k ,i } are not guaranteed to be optimal solutions to the non-convex optimization in (61), they are practical solutions that have an efficient tradeoff between optimality and computational complexity. Similar tradeoffs have been made in related works [34], [56], [59], [60] for this reason. However, {z k ,i } is an optimal solution for a given { fk }, and {f k } is an optimal solution for a given {z k ,i }, which is one of the main contributions of this paper.

The semi-exhaustive search optimization still requires significant computation due to the large potential number of combinations of {a k,k } and {b k,i }. The efficient alternate optimization is much more computationally efficient, and as we will see in Section V-B, its observed solutions have comparable performance to that of the semi-exhaustive search optimization.

Considering the computational complexities of both algorithms with respect to the integer variables, we have the following lemma:

Lemma 2: With respect to the task assignment and subchannel allocation variables, the semi-exhaustive search optimization (Algorithm 1) has O((KS -S + 1) K ) and the efficient alternate optimization (Algorithm 3) has O(K 3 S), where K and S are the number of nodes and number of subchannels, respectively.

The proof is relegated to Appendix B. The computational complexity of the semi-exhaustive search optimization is worse than exponential in the number of nodes, while that of the efficient alternate optimization is polynomial. For example, if we consider K = 10 and S = 2, the semi-exhaustive search optimization already has up to 19 10 combinations of binary variables to consider (depending on condition (23)), and the optimization for non-integer variables will be performed for each combination. In contrast, the efficient alternate optimization limits the number of combinations to at most 2000, depending on how many combinations provide a positive offloading benefit. Further, the full optimization over non-integer variables is performed once the best combination is determined, i.e., it is not performed for every binary combination.

In this section, we conduct experiments to validate our methods for minimizing the total network overhead in D2D networks. After discussing our setup (Section V-A), in Section V-B, we will quantify improvements relative to local processing and compare the efficient alternate optimization to the semi-exhaustive search optimization. Then, in Sections V-C to V-F, we will evaluate the performance of the efficient alternate optimization under variation of different network parameters.

Values: For all of our experiments, we select values that are common for mobile computing environments [16], [61] i.i.d. following CN (0, β k,k ) [25]. Here, β k,k = β 0 -10α log 10 (d k,k /d 0 ) (dB) denotes the large-scale fading factor between nodes k and k , where β 0 = -30 dB is the path loss at the distance d 0 = 1 m, and α = 3.5 is the path loss exponent in cellular networks [62]. The distance between nodes k and k , d k,k , is randomly generated as d k,k ∼ U(10, 30) (m), where U(a, b) denotes the uniform distribution on the interval [a, b]. We assume that the individual transmit power limit is P k = P = 3 dBW [16] for k ∈ K, the noise power is σ 2 = -90 dBW [45], the circuit power is P c = -20 dBW [61], and the subchannel bandwidth is W = 1 MHz. The beamformers f k and combiners z k ,i are initially generated to be uniformly distributed on the complex sphere [63] with radius √ P and 1, respectively, for k, k ∈ K and i ∈ S.

As a computation task, we consider image recognition [8], [53], which is a popular application on mobile devices (e.g., for user authentication via facial recognition). To emulate heterogeneous devices, we consider different task sizes and CPUs across the nodes. For the task size, we sample I k ∼ U (1,8) in Mbits, i.e., U(0.128, 1) in Mbytes, for each node k. These represent common image sizes found on mobile devices [8], [53]. For CPU, we consider a bimodal distribution for each node k : F k ∼ 3 4 U(0.1, 0.2) + 1 4 U(0.9, 1), with units of GHz. This selection generates a composition of resource-hungry and resource-rich devices, reflecting common processor clock speeds found in mobile devices [8], [16], [53]. We assume constant processing density µ k = 200 cycles/bit, and energy coefficients κ k = 3.5×10 -27 across all nodes, as in [16]. The overhead factor β k is assumed to be the same for all nodes, i.e., β k = β for all k. Unless otherwise stated, β = 0.5. All nodes are considered to have N transmit and receive antennas, i.e., N k = N for all k. Each experiment is averaged over 20 different samplings of task sizes, CPUs, and channel realizations. For the efficient alternate optimization, we consider 10 different initializations of {a k,k } and {b k,i }, and choose the best solution. The threshold for Algorithms 2&3 is ε = 10 -4 .

2) Baselines: We compare the proposed algorithms with three different baselines. The first baseline is local computation, where all the nodes locally process their own tasks without offloading. The total network overhead for local processing is

This baseline will be used to assess the improvements obtained via our offloading optimization methodology. The second baseline is the efficient alternate optimization with the weighted minimum mean square error (WMMSE) approach [34] used in place of Algorithm 2. WMMSE is an existing method for beamformer design with a sum-utility maximization objective, proposed in [34]. Specifically, in place of ( 33)- (34), with WMMSE, we minimize the total communication time as minimize

(66) This baseline will allow us to assess the importance of balancing time and energy as competing objectives in overhead minimization.

The third baseline is the efficient alternate optimization but with equal CPU allocation. For a given task assignment, the CPU is equally allocated across the requested tasks. Specifically, in Algorithm 4, we do not consider the minimization problem with respect to {F k,k } in ( 55) and ( 57). This baseline, together with the second baseline, will assess the importance of our formulation as a joint optimization over communication and computation resources.

Our first experiment compares the total network overhead incurred by semi-exhaustive search, efficient alternate optimization, and local computation for different numbers of nodes K. Fig. 3 shows the results as K varies from 3 to 8 in a small network with S = 2 and N = 5. Compared to the local computation, the offloading through our methodology results in a significant decrease between 19% and 27% in the total network overhead even for small D2D networks. The semi-exhaustive search optimization provides a lower bound on the minimum achievable overhead required by the efficient alternate optimization, as discussed in Section IV-C. However, we find that the implementation of the semi-exhaustive search is computationally infeasible for more than K = 8 nodes, consistent with its computational complexity given in Lemma 2. Furthermore, the efficient alternate optimization gives almost the same overhead performance as the semi-exhaustive search optimization. Henceforth, we will present results based on the efficient alternate optimization. An experiment on the runtime growth rate of the efficient alternate optimization is provided in Appendix D-A, verifying its polynomial complexity.

Fig. 4 shows the convergence behavior of the efficient alternate optimization, plotting the total network overhead obtained after each iteration of Algorithm 3, for the same settings in Fig. 3 and K = 10 nodes. After the first iteration, the total network overhead decreases dramatically due to the high reduction in communication overhead obtained from the beamformer design. We observe in our experiments that, the objective function generally converges within a few iterations.

Fig. 5 demonstrates the effect of imperfect channels on our proposed framework and algorithms. Imperfect CSI is modeled

2 ), where θ 2 denotes the channel distortion ratio. As the distortion ratio increases to θ 2 = 0.5, the overhead improvement relative to local computing only decreases from 28% to 25%. This shows that our methodology is still applicable for minimizing total D2D network overhead in the presence of imperfect CSI.

Our next experiment assesses the benefit provided by each offloading node that the greedy algorithm adds in the efficient alternate optimization. Specifically, Fig. 6 shows the change in overhead as more data streams (k, k , i) are added for offloading in Algorithm 4, for K = 30, S = 2, and Fig. 7. Communication overhead with varying subchannels S for K = 30 and N = 5. Our method leverages additional subchannels for overhead reduction via interference mitigation. N = 5. We show the evolution of the communication overhead

and the total overhead Y total = Y comm + Y comp . Overall, we see that the total network overhead is decreasing at each iteration, which is consistent with the operation of the greedy algorithm. This is obtained by trading an increase in communication overhead for a more substantial decrease in computation overhead. The algorithm successively exploits low-cost opportunities for offloading from resource constrained to resource-rich nodes, until such opportunities are no longer cost-effective. In this case, 23% of the nodes (7 out of 30) become offloading nodes by the time the algorithm terminates.

Our next experiments assess the communication overhead reduction obtained by our methodology from leveraging interference management resources. When the number of subchannels S and number of antennas N are limited, we expect that communication overhead will be higher due to decreasing transmission data rates from inter-channel interferences. Fig. 7 shows the effect of S on Y comm for both the efficient alternate optimization and the baseline using WMMSE, when N = 5 and there are K = 30 devices. We see that the total communication overhead decreases as the number of subchannels increases because more subchannels enable avoiding interferences by allocating non-overlapping subchannels to different data streams. Moreover, the efficient alternate optimization with MCOB gives better performance than that with WMMSE -with improvements of roughly 37% for each choice of S -because MCOB is designed to minimize the total communication overhead, while WMMSE minimizes only the total communication time.

Fig. 8 shows the effect on communication overhead as more antennas are employed for K = 30 and S = 1. With a limited number of subchannels available (S = 1), the beamforming strategy plays a significant role in communication overhead reduction. As N increases, our methodology suppresses the interference further due to the increased spatial degrees of freedom. The gap in communication overhead between the efficient alternate optimization with MCOB vs. WMMSE increases with more antennas, reaching roughly a 43% improvement.

We are also interested in the impact of the importance placed on time vs. energy in the total network overhead optimization. Fig. 9 demonstrates the effect of the overhead demand factor β on the total time delay and energy consumption incurred, aggregating all tasks and over both communication and computation overhead components, for K = 10, S = 2, and N = 5. The individual time delay and energy consumption incurred by each task for different β is provided in Appendix D-B. The results in Fig. 9 are consistent with design of the optimization objective: compared to the case of all local computation, total time is reduced the most (36%) when β = 0.2, while more energy reduction (61%) is achieved when β = 0.8. This experiment confirms that the objective can be adjusted according to the tradeoff importance requirement of a specific use case. Now, we consider the communication overhead optimization to evaluate the performance of MCOB, according to different values of β. Fig. 10 shows total communication overhead as β varies from 0 to 1 with MCOB and WMMSE, for K = 10, S = 2, and N = 5. When β is small, the performances of MCOB and WMMSE are almost identical, as the emphasis is on completion time minimization; in other words, WMMSE is a special case of MCOB for β = 0. Since WMMSE does not factor in energy consumption minimization, at any value of β > 0.15, MCOB shows a substantial improvement compared to WMMSE. This emphasizes the importance of considering both time delay and energy consumption as components of the overhead model. Note that the communication overhead of WMMSE increases linearly as β increases. This is because the values of T comm and E comm in (19) are constant as a result of WMMSE, and E comm is larger than T comm in this specific D2D scenario. Additionally, the achievable communication overhead by MCOB drops as β increases beyond 0.15. This is also due to the specific D2D scenario being considered: in (19), as a result of MCOB, the value of E comm (in Joules) is further reduced than T comm (in seconds) as β increases.

In this experiment, we compare the total network overhead obtained by efficient alternate optimization and the three baselines as the size of the D2D network changes. Fig. 11 plots Y total as K increases for S = 2 and N = 5. Compared to local computation, the other three schemes each yield significant reduction in the total network overhead due to the benefit of offloading. Furthermore, the offloading-enabled methods scale better as the size of the network increase: the performance gap widens and the improvement of the efficient alternate optimization stays around 20% to 30% consistently. With more nodes, there are offloading opportunities, leading to more overhead reduction.

In comparing the offloading-enabled methods, we note that the efficient alternate optimization consistently outperforms the equal CPU allocation and WMMSE baselines (by 7% and 6%, respectively), which are partially optimized solutions. This emphasizes the importance of considering a joint optimization of communication and computation resources to obtain the lowest overhead in an environment of heterogeneous wireless devices. The equal CPU allocation baseline is a lower complexity algorithm, however, given it does not solve IEEE/ACM TRANSACTIONS ON NETWORKING the CPU optimization problem. This could be a necessary tradeoff if optimization speed is critical, which depends on the timescale at which the solver is employed in practice. We also provide a comparison between the theoretical and observed computational complexity of our method in Appendix D-A.

In this paper, we proposed a novel optimization methodology that minimizes the total network overhead required to process a set of tasks in wireless D2D edge networks. Our optimization model consists of several computation and communication resources including topology configuration, CPU allocations, subchannel allocations, and beamforming design for MIMO transmitters and receivers. Given that the problem is a non-convex MIP, we proposed two methods to solve it: semi-exhaustive search optimization and efficient alternate optimization. In analyzing the optimality and computational complexity of the proposed methods, we showed that the semi-exhaustive search can be regarded as a best effort for optimality, while the efficient alternate optimization has much smaller computational complexity. Through our numerical experiments, we showed the total network overhead can be reduced significantly by leveraging offloading opportunities to resource-rich nodes in D2D networks. Further, in comparison with solutions that only optimize a subset of the variables, our results showed that joint communication and computation resource optimization is critical to obtaining the highest reductions in network overhead.

There are several potential avenues of future work. First, while we have focused on tasks generated in a single time period, dynamic task generation at nodes can also be considered. This can be accomplished by augmenting our methodology with a stochastic optimization that models task generation over a long-term time horizon. Second, while we have focused on centralized control for optimizing distributed data processing, it will be desirable to decentralize this optimization in certain settings. One possibility is to investigate a fully distributed implementation of Algorithm 3, where each node solves its local beamforming and resource design sub-problems based on information provided by adjacent neighbors. Lastly, our overhead model can be extended to include components outside of data transmission and processing, e.g., waiting latency, handover latency, and latency of receiving the processed data result back at the origin.