# Cooperative Offloading in D2D-Enabled Three-Tier MEC Networks for IoT

Authors: Jingyan Wu; Jiawei Zhang; Yuming Xiao; Yuefeng Ji
Journal: Wireless Communications and Mobile Computing
 (2021)

---

## Abstract

Mobile/multi-access edge computing (MEC) takes advantage of its proximity to end-users, which greatly reduces the transmission delay of task offloading compared to mobile cloud computing (MCC). Offloading computing tasks to edge servers with a certain amount of computing ability can also reduce the computing delay. Meanwhile, device-to-device (D2D) cooperation can help to process small-scale delay-sensitive tasks to further decrease the delay of tasks. But where to offload the computing tasks is a critical issue. In this article, we integrate MEC and D2D cooperation techniques to optimize the offloading decisions and resource allocation problem in D2D-enabled three-tier MEC networks for Internet of Things (IoT). Mobile devices (MDs), edge clouds, and central cloud data center (DC) make up these three-tier MEC networks. They cooperate with each other to finish the offloading tasks. Each task can be processed by MD itself or its neighboring MDs at device tier, by edge servers at edge tier, or by remote cloud servers at cloud tier. Under the maximum energy cost constraints, we formulate the cooperative offloading problem into a mixed-integer nonlinear problem aiming to minimize the total delay of tasks. We utilize the alternating direction method of multipliers (ADMM) to speed up the computing process. The proposed scheme decomposes the complicated problem into 3 smaller subproblems, which are solved in a parallel fashion. Finally, we compare our proposal with D2D and MEC networks in simulations. Numerical results validate that the proposed D2D-enabled MEC networks for IoT can significantly enhance the computing abilities and reduce the total delay of tasks.


---

## Body

## 1. Introduction

Mobile devices (MDs) have limited computing resources and power capacity due to their portable sizes [1]. To cope with computation-intensive, delay-sensitive, and high-energy-cost tasks, mobile/multi-access edge computing (MEC) has been proposed to deploy resource-rich servers at base stations (BSs) within the proximity of MDs [2–5]. In Internet of Things (IoT), MEC has been advocated as a promising technique for providing massive MDs with enhanced computing and storage capabilities [6].For one thing, due to the physical proximity, MEC can significantly reduce the transmission latency [7, 8] involving in communication compared with mobile cloud computing (MCC) [9–12]. For another thing, MEC enables MDs to perform computation offloading, which can migrate their computing tasks [13] to resource-rich nodes and send results back to the MDs [14]. Offloading has always been a hot topic which can guarantee low computing time, as well as saving the battery energy of MDs [15], increasing the network throughput. Therefore, MEC can improve users’ satisfaction [16] or quality-of-experience (QoE) of the end-users [17], relieve network congestion [18, 19], prolong the battery lifetime [20] of MDs, and further reduce the total latency distinctly. Thus, MEC is an efficient solution for IoT.Nevertheless, offloading can obtain computing resources at the expense of extra transmission delay and associated energy consumption, due to the communication between the MDs and edge servers over the wireless channels [21]. Offloading may be really beneficial to MDs with large amounts of computation and relatively small amounts of communication [22].However, the edge servers associated with BSs have limited computing resources and can not always meet the requirements of the served MDs [23]. D2D cooperation can help to solve this problem, where the helpers (resource-rich MDs) can execute computing tasks from resource-limited MDs [24]. D2D-assisted cooperative offloading services play a complementary role in MEC, which is helpful when processing some small-scale tasks for energy-efficiency [25]. When a task has already been done well through D2D cooperation, accordingly, it can free up radio resources for other purposes and reduce the uplink delay of the task [26].Therefore, in this paper, we propose cooperative computation offloading in D2D-enabled MEC networks for IoT aiming to minimize the total delay of tasks with the maximum energy consumption constraints. By leveraging the advantages of both MEC and D2D cooperation techniques, computing resources can be fully used. Our contributions can be summarized as follows:(1)
We propose a computing architecture where cooperative offloading can be carried out in the D2D-enabled three-tier MEC networks. Each task can be processed locally by MD itself or its neighboring MDs at device tier, by edge servers at edge tier, or by remote cloud servers at cloud tier(2)
The proposed three-tier MEC networks provide MDs with multiple optional offloading destinations. We formulate the offloading decisions and resource allocation in this MEC networks as an optimization problem aiming to minimize the total delay of tasks(3)
The formulated problem is a mixed-integer nonlinear problem which is hard to solve. We decompose the problem into 3 subproblems. Then, we solve it utilizing the alternating direction method of multipliers (ADMM). Extensive simulation results validate that the proposed scheme is effectiveThe organization of this article is as follows. Section2 provides a review of related work. Sections 3 presents the system model, including the network model, communication model, and computing model. In Section 4, we formulate the problem and give the equivalent form. In Section 5, we propose a parallel optimization framework to solve the problem and develop an efficient computation offloading scheme. Related simulations are provided in Section 6. Finally, we conclude this article in Section 7.


## 2. Related Work

Extensive research has been conducted on MEC. Many existing works paid attention to the computation offloading problem [15, 16, 20, 21, 27–32]. Some works jointly considered the computation offloading policy and the involved resource allocation [15, 33–35]. Others jointly considered the offloading decisions, content caching [28, 36], and the resource allocation [20, 30]. All of these above works focused on two-tier edge computing networks.Works focusing on the task offloading problem in three-tier edge computing networks can be found in [17, 37–40]. Tong et al. [39] first proposed a three-tier hierarchical edge cloud architecture to maximize the amount of peak mobile workloads from MDs being served. The performance of the proposed hierarchical edge cloud architecture was evaluated by a small-scale system experiment. The deployment of edge servers and cloud servers formed a three-tier MEC architecture, where local computing, edge computing, and cloud computing could coexist and cooperate to assist the task execution [38]. This scheme provided multiple offloading decisions for devices. The different offloading decisions may largely impact the network performance [21]. For example, offloading the tasks to the edge node or remote cloud DC will inevitably incur additional long communication delay [39], whereas executing the task locally may result in larger computing delay. Consequently, it is critical for devices to make proper offloading decisions in the three-tier computing networks.Some works study cooperative offloading in MEC networks. du et al. [40] considered vertical cooperation between the fog and the cloud, in which the application can be processed in the MD locally, in the fog or in the cloud. The authors assumed that the offloading requests were usually very small; no buffer was needed for queueing the computing requests. Xiao and Krunz [17] designed optimal workload allocation solutions in a cooperative fog computing network. Instead of always relying on the cloud data center to process its unprocessed workload, each fog node can also forward part or all of its unprocessed workload to its neighboring fog nodes to further improve the QoE of its users. This paper solved the optimal workload allocation problem with the distributed ADMM. Wang et al. [38] developed a cooperative task offloading and computing resource allocation scheme in three-tier computing networks, considering the cooperation among the devices, the edge servers, and cloud servers vertically as well as the cooperation between the edge nodes horizontally. In these above works, they did not consider the cooperation among MDs.D2D cooperation focuses on the collaborative computation among MDs. Feng et al. [24] developed a computation offloading scheme based on D2D communications, in which resource-limited MDs could offload their computation-intensive tasks to appropriate nearby resource-rich MDs. Xing et al. [41] studied D2D-enabled multihelper MEC networks, where a local user could be helped by its nearby wireless devices serving as helpers for cooperative computation. Literature [26] considered offloading computational tasks to nearby devices or to an edge cloud and developed a decentralized algorithm to allocate the computational tasks among them. However, these works were not carried out in three-tier networks.In MEC networks, there are horizontal collaboration at the device tier [41] and the edge tier [17] as well as the vertical collaboration [40] among MDs, edge nodes, and cloud nodes [2]. Different from the above literatures, our paper proposes cooperative computation offloading in D2D-enabled three-tier MEC networks for IoT. Each task can be processed locally by MD itself or its neighboring MDs, by edge servers at edge tier, or by cloud servers at cloud tier.


## 3. System Model

In this section, the system model adopted in this paper is described. We introduce the proposed network model and present the communication and the computing model in detail. Finally, we calculate the total delay of tasks and energy consumption.


### 3.1. Network Model

As depicted in Figure1, we propose a D2D-enabled three-tier MEC network architecture as a part of the IoT, which consists of N MDs labeled as N=1,2,⋯,N, M base stations (BSs), and a remote central cloud DC equipped with many remote cloud servers. Each MD has the ability of D2D communication and is connected to the closest BS via a wireless link. Each BS is equipped with some edge servers in edge cloud at edge tier and can be regarded as an edge node. The BSs are connected to the remote cloud servers in central cloud DC at cloud tier via a low-latency wired backhaul link (e.g., optical link) [4]. Optical backhauling is a promising solution [42, 43] to offer high throughput, low latency, and reduced energy consumption. Moreover, the flexibility and reliability can be effectively improved by the adoption of artificial intelligence-driven autonomous optical networks [44].Figure 1
A D2D-enabled three-tier MEC network.In this D2D-enabled cooperative architecture, we assume that each MD has a computing task to be processed locally by MD itself or its neighboring MDs at device tier, by edge cloud, or by central cloud DC. MDs can help each other when they are free or have surplus computing resources. The helper may be rewarded in terms of accumulated reward points. MDs with more accumulated reward points can be helped with higher precedence when they need help. Multiple neighboring local MDs can communicate with each other through WiFi [45] or Bluetooth [46]. The network operator (e.g., BS) can gather sufficient D2D connectivity information through network-assisted device discovery and local information reporting by the devices [25]. If the network condition is bad, the task of each local MD is small and/or delay-sensitive; MDs may be more willing to choose D2D cooperation due to short transmission time. That is to say, these tasks prefer to be processed among local MDs.The computation offloading process is shown in Figure2 [35]. Each MD can send an offloading request including the information of the MD such as its local processing capability and power consumption, the properties of the task such as the size and emergency of the task, and the maximum tolerable delay [40]. According to this collected information, MDs finally decide where should the tasks be processed. The computing task of MD n can be completed locally within its CPU, or by its neighboring MD via D2D cooperation, or remotely in the edge cloud via MEC offloading, or further up the cloud DC via cloud offloading [35].Figure 2
Computation offloading process.After being processed in one of these nodes, the result of the computing task is transmitted back to the corresponding MD. Similar to many previous works about MEC [18, 20, 21, 26], we neglect the return result time of the computed tasks in this work. The assumption is justified for many applications including face recognition and anomaly detection, where the size of the result is much smaller than the size of the uplink data. We do not consider the queueing of offloading tasks, as in [19, 40]. To obtain tractable analysis, we also omit the delay due to decision-making [20].


### 3.2. Communication Model

For the communication model, the computing task of MDn is described by Γn=(Ln,τnmax,Cn), where Ln (in bits) stands for the input data size of task Γn, τnmax (in s) stands for the task computation deadline for MD n, and Cn (in CPU cycles) stands for the number of required CPU cycles to accomplish the task Γn.When a task of an MD can not be processed well by MD itself or its neighboring MDs, the task can be sent to the BS. The bandwidth resource of the BS is denoted asB Hz. However, the limited radio bandwidth needs to be allocated among all the edge-processing and the cloud-executing MDs for communication with the edge node. Within our communication model, all the devices equally share the bandwidth. The uplink bandwidth of MD n is Bn Hz; the uplink achievable transmission rate Rn for radio access can be approximated by Shannon’s formula:
(1)Rn=Bn·log21+pnBnGnσ2,where pn is the transmission power density of MD n, Gn stands for the channel gain between the MD n and the BS, and σ2 denotes the power of additive white Gaussian noise.Furthermore, the uplink transmission delay for MDn offloading the task Γn to the BS is calculated as
(2)Tntr=LnRn.And the transmission energy consumption for MDn offloading the task Γn to the BS can be given as
(3)Entr=PnTntr,where Pn is the total power consumption of MD n for transmission in the uplink, consisting of the static power consumption and transmit power [38].


### 3.3. Computing Model

We denote the offloading decisions for MDn by xn,j,yn,zn∈0,1, where xn,j=1,yn=1,zn=1 indicate that the task of MD n is executed by MD itself (e.g., n=j) or its neighboring MD j, by edge server, or by cloud server, respectively; otherwise, xn,j=0,yn=0,zn=0. Thus, the offloading decisions of device n is constrained by
(4)∑j=1Nxn,j+yn+zn=1,∀n∈N.In the constraint, it should be noted that one and only one of the offloading decisionsxn,j, yn, and zn for the MD n can be 1 at any time. It also implies that the task of each MD is impartible in this paper.Next, we will discuss the computation overhead in terms of processing delay and energy consumption of MDn with different offloading approaches.


#### 3.3.1. Local Processing

For the local task processing approach, letfnL denote the local computing capability (in CPU cycles/s) of MD n. Then, the computing delay of processing the task Γn locally can be
(5)TnL=TΓnn=CnfnL.The CPU power consumption is a function of execution frequencyfnL. We can compute the energy consumption of MD n as [47, 48]
(6)EnL=10−11CnfnL2.From (5) and (6), we can notice that both TnL and EnL are only related to Cn and fnL, which are the known inherent features of MD n and its computing task.


#### 3.3.2. D2D Cooperation

For D2D cooperation, we definedn,j as the D2D link between local MD n and j, PnD as the power consumption of MD n, and Tn,jtr as the round trip time (RTT) for task transferring between the D2D pairs. This RTT is assumed to be stable during an offloading period, while it may change across different periods. It can be estimated at the beginning of the offloading period, by using the history information or empirical formula [49]. Thus, when the task Γn is executed finally at MD j, the total delay TnD consists of the communication delay Tn,jtr between MD n and MD j and the processing delay TΓnj at MD j. It can be calculated as
(7)TnD=TΓnj+Tn,jtr,∀j∈N,according to (5), TΓnj=Cn/fjL. Note that Tn,jtr=0 when n=j, because there is no task to transfer within the local MD. Thus, the delays of tasks in the device tier all meet (7).In this case, the energy cost of MDn is mainly the transmission energy consumption. It can be given as
(8)EnD=PnDTn,jtr.


#### 3.3.3. Edge Computing

For the edge computing approach, the total computing capacity of the BS is denoted asF (in CPU cycles/s), which can be allocated to the computing tasks processed by the BS. Denote fnB as the computing resource allocated to MD n by the BS. Thus, the computing delay of MD n executed by BS is given as
(9)TnB=CnfnB.When the tasks are computed in the edge server, the MDn sends the task Γn to the associated BS. Then, the BS will process the offloaded task by employing its computing resources. Combining with equation (2), the total delay of task Γn processed by the BS is calculated by
(10)TnE=Tntr+TnB.


#### 3.3.4. Cloud Computing

For the computing task offloaded to the cloud DC, MDn firstly transmits the task Γn to the nearest BS through a wireless link. Then, the BS forwards the task Γn to the cloud DC through a fiber optical link. Since the cloud servers have plenty of computing resources and the fiber optical link between the edge cloud and the cloud DC is of sufficiently large capacity, the allocation of these resources will not be discussed here. Ordinarily, the computing capability of the cloud DC is much higher than that of the MEC servers.Let the RTT for task transmission between the edge server at BS and cloud server beTB,C. Denote fnC as the cloud computing capability (in CPU cycles/s) assigned to MD n, which is assumed to be a predetermined value according to the cloud computing service [40]. Therefore, the cloud computing delay of MD n is given by
(11)TnfC=CnfnC.Then, combining with equation (2), the total delay of cloud processing for MD n can be expressed as
(12)TnC=Tntr+TB,C+TnfC.The above notations that will be used in this paper are summarized in Table1.Table 1
Notation and corresponding definition.
NotationDefinitionΓnComputing task of MDnLnData size of taskΓn (in bits)CnCPU cycles required to accomplish the taskΓnBThe bandwidth of the BSBnThe uplink bandwidth of MDnRnThe uplink transmission rate of MDnpnThe transmission power density of MDnPnDThe power consumption of MDn in D2D cooperationPnThe total power consumption of MDnGnThe channel gain between the MDn and the BSσ2The power of the additive white Gaussian noisefnLThe local computing capability of MDn (in CPU cycles/s)fnBThe computing resource allocated to MDn by the BSfnCThe computing resource allocated to MDn by the cloudFThe computing capacity of the BSτdmaxThe task computation deadline for MDnTntrThe uplink transmission delay of taskΓn offloaded to the BSTΓnjThe computing delay of taskΓn processed at MD jTn,jtrThe average round trip time between MDn and jTnLThe delay of taskΓn processed locallyTnDThe total delay of taskΓn via D2D cooperationTnBThe computing delay of MDn by the BSTB,CThe round trip time between BS and the cloud serversTnfCThe cloud computing delay of MDnTnCThe total delay of taskΓn processed by the cloud serversEntrThe transmission energy consumption of taskΓn to the BSEnLThe energy consumption of processing the taskΓn locallyEnDThe energy consumption of processingΓn via D2D cooperationAs mentioned earlier, we ignore the return result time of the computed tasks. According to (2)–(12), the total task delay and energy consumption of MD n are calculated, respectively, as
(13)Tn=∑j=1Nxn,jTnD+ynTnE+znTnC,(14)En=xn,nEnL+∑j∈N\nxn,jEnD+1−∑j=1Nxn,jEntr.


## 3.1. Network Model

As depicted in Figure1, we propose a D2D-enabled three-tier MEC network architecture as a part of the IoT, which consists of N MDs labeled as N=1,2,⋯,N, M base stations (BSs), and a remote central cloud DC equipped with many remote cloud servers. Each MD has the ability of D2D communication and is connected to the closest BS via a wireless link. Each BS is equipped with some edge servers in edge cloud at edge tier and can be regarded as an edge node. The BSs are connected to the remote cloud servers in central cloud DC at cloud tier via a low-latency wired backhaul link (e.g., optical link) [4]. Optical backhauling is a promising solution [42, 43] to offer high throughput, low latency, and reduced energy consumption. Moreover, the flexibility and reliability can be effectively improved by the adoption of artificial intelligence-driven autonomous optical networks [44].Figure 1
A D2D-enabled three-tier MEC network.In this D2D-enabled cooperative architecture, we assume that each MD has a computing task to be processed locally by MD itself or its neighboring MDs at device tier, by edge cloud, or by central cloud DC. MDs can help each other when they are free or have surplus computing resources. The helper may be rewarded in terms of accumulated reward points. MDs with more accumulated reward points can be helped with higher precedence when they need help. Multiple neighboring local MDs can communicate with each other through WiFi [45] or Bluetooth [46]. The network operator (e.g., BS) can gather sufficient D2D connectivity information through network-assisted device discovery and local information reporting by the devices [25]. If the network condition is bad, the task of each local MD is small and/or delay-sensitive; MDs may be more willing to choose D2D cooperation due to short transmission time. That is to say, these tasks prefer to be processed among local MDs.The computation offloading process is shown in Figure2 [35]. Each MD can send an offloading request including the information of the MD such as its local processing capability and power consumption, the properties of the task such as the size and emergency of the task, and the maximum tolerable delay [40]. According to this collected information, MDs finally decide where should the tasks be processed. The computing task of MD n can be completed locally within its CPU, or by its neighboring MD via D2D cooperation, or remotely in the edge cloud via MEC offloading, or further up the cloud DC via cloud offloading [35].Figure 2
Computation offloading process.After being processed in one of these nodes, the result of the computing task is transmitted back to the corresponding MD. Similar to many previous works about MEC [18, 20, 21, 26], we neglect the return result time of the computed tasks in this work. The assumption is justified for many applications including face recognition and anomaly detection, where the size of the result is much smaller than the size of the uplink data. We do not consider the queueing of offloading tasks, as in [19, 40]. To obtain tractable analysis, we also omit the delay due to decision-making [20].


## 3.2. Communication Model

For the communication model, the computing task of MDn is described by Γn=(Ln,τnmax,Cn), where Ln (in bits) stands for the input data size of task Γn, τnmax (in s) stands for the task computation deadline for MD n, and Cn (in CPU cycles) stands for the number of required CPU cycles to accomplish the task Γn.When a task of an MD can not be processed well by MD itself or its neighboring MDs, the task can be sent to the BS. The bandwidth resource of the BS is denoted asB Hz. However, the limited radio bandwidth needs to be allocated among all the edge-processing and the cloud-executing MDs for communication with the edge node. Within our communication model, all the devices equally share the bandwidth. The uplink bandwidth of MD n is Bn Hz; the uplink achievable transmission rate Rn for radio access can be approximated by Shannon’s formula:
(1)Rn=Bn·log21+pnBnGnσ2,where pn is the transmission power density of MD n, Gn stands for the channel gain between the MD n and the BS, and σ2 denotes the power of additive white Gaussian noise.Furthermore, the uplink transmission delay for MDn offloading the task Γn to the BS is calculated as
(2)Tntr=LnRn.And the transmission energy consumption for MDn offloading the task Γn to the BS can be given as
(3)Entr=PnTntr,where Pn is the total power consumption of MD n for transmission in the uplink, consisting of the static power consumption and transmit power [38].


## 3.3. Computing Model

We denote the offloading decisions for MDn by xn,j,yn,zn∈0,1, where xn,j=1,yn=1,zn=1 indicate that the task of MD n is executed by MD itself (e.g., n=j) or its neighboring MD j, by edge server, or by cloud server, respectively; otherwise, xn,j=0,yn=0,zn=0. Thus, the offloading decisions of device n is constrained by
(4)∑j=1Nxn,j+yn+zn=1,∀n∈N.In the constraint, it should be noted that one and only one of the offloading decisionsxn,j, yn, and zn for the MD n can be 1 at any time. It also implies that the task of each MD is impartible in this paper.Next, we will discuss the computation overhead in terms of processing delay and energy consumption of MDn with different offloading approaches.


### 3.3.1. Local Processing

For the local task processing approach, letfnL denote the local computing capability (in CPU cycles/s) of MD n. Then, the computing delay of processing the task Γn locally can be
(5)TnL=TΓnn=CnfnL.The CPU power consumption is a function of execution frequencyfnL. We can compute the energy consumption of MD n as [47, 48]
(6)EnL=10−11CnfnL2.From (5) and (6), we can notice that both TnL and EnL are only related to Cn and fnL, which are the known inherent features of MD n and its computing task.


### 3.3.2. D2D Cooperation

For D2D cooperation, we definedn,j as the D2D link between local MD n and j, PnD as the power consumption of MD n, and Tn,jtr as the round trip time (RTT) for task transferring between the D2D pairs. This RTT is assumed to be stable during an offloading period, while it may change across different periods. It can be estimated at the beginning of the offloading period, by using the history information or empirical formula [49]. Thus, when the task Γn is executed finally at MD j, the total delay TnD consists of the communication delay Tn,jtr between MD n and MD j and the processing delay TΓnj at MD j. It can be calculated as
(7)TnD=TΓnj+Tn,jtr,∀j∈N,according to (5), TΓnj=Cn/fjL. Note that Tn,jtr=0 when n=j, because there is no task to transfer within the local MD. Thus, the delays of tasks in the device tier all meet (7).In this case, the energy cost of MDn is mainly the transmission energy consumption. It can be given as
(8)EnD=PnDTn,jtr.


### 3.3.3. Edge Computing

For the edge computing approach, the total computing capacity of the BS is denoted asF (in CPU cycles/s), which can be allocated to the computing tasks processed by the BS. Denote fnB as the computing resource allocated to MD n by the BS. Thus, the computing delay of MD n executed by BS is given as
(9)TnB=CnfnB.When the tasks are computed in the edge server, the MDn sends the task Γn to the associated BS. Then, the BS will process the offloaded task by employing its computing resources. Combining with equation (2), the total delay of task Γn processed by the BS is calculated by
(10)TnE=Tntr+TnB.


### 3.3.4. Cloud Computing

For the computing task offloaded to the cloud DC, MDn firstly transmits the task Γn to the nearest BS through a wireless link. Then, the BS forwards the task Γn to the cloud DC through a fiber optical link. Since the cloud servers have plenty of computing resources and the fiber optical link between the edge cloud and the cloud DC is of sufficiently large capacity, the allocation of these resources will not be discussed here. Ordinarily, the computing capability of the cloud DC is much higher than that of the MEC servers.Let the RTT for task transmission between the edge server at BS and cloud server beTB,C. Denote fnC as the cloud computing capability (in CPU cycles/s) assigned to MD n, which is assumed to be a predetermined value according to the cloud computing service [40]. Therefore, the cloud computing delay of MD n is given by
(11)TnfC=CnfnC.Then, combining with equation (2), the total delay of cloud processing for MD n can be expressed as
(12)TnC=Tntr+TB,C+TnfC.The above notations that will be used in this paper are summarized in Table1.Table 1
Notation and corresponding definition.
NotationDefinitionΓnComputing task of MDnLnData size of taskΓn (in bits)CnCPU cycles required to accomplish the taskΓnBThe bandwidth of the BSBnThe uplink bandwidth of MDnRnThe uplink transmission rate of MDnpnThe transmission power density of MDnPnDThe power consumption of MDn in D2D cooperationPnThe total power consumption of MDnGnThe channel gain between the MDn and the BSσ2The power of the additive white Gaussian noisefnLThe local computing capability of MDn (in CPU cycles/s)fnBThe computing resource allocated to MDn by the BSfnCThe computing resource allocated to MDn by the cloudFThe computing capacity of the BSτdmaxThe task computation deadline for MDnTntrThe uplink transmission delay of taskΓn offloaded to the BSTΓnjThe computing delay of taskΓn processed at MD jTn,jtrThe average round trip time between MDn and jTnLThe delay of taskΓn processed locallyTnDThe total delay of taskΓn via D2D cooperationTnBThe computing delay of MDn by the BSTB,CThe round trip time between BS and the cloud serversTnfCThe cloud computing delay of MDnTnCThe total delay of taskΓn processed by the cloud serversEntrThe transmission energy consumption of taskΓn to the BSEnLThe energy consumption of processing the taskΓn locallyEnDThe energy consumption of processingΓn via D2D cooperationAs mentioned earlier, we ignore the return result time of the computed tasks. According to (2)–(12), the total task delay and energy consumption of MD n are calculated, respectively, as
(13)Tn=∑j=1Nxn,jTnD+ynTnE+znTnC,(14)En=xn,nEnL+∑j∈N\nxn,jEnD+1−∑j=1Nxn,jEntr.


## 3.3.1. Local Processing

For the local task processing approach, letfnL denote the local computing capability (in CPU cycles/s) of MD n. Then, the computing delay of processing the task Γn locally can be
(5)TnL=TΓnn=CnfnL.The CPU power consumption is a function of execution frequencyfnL. We can compute the energy consumption of MD n as [47, 48]
(6)EnL=10−11CnfnL2.From (5) and (6), we can notice that both TnL and EnL are only related to Cn and fnL, which are the known inherent features of MD n and its computing task.


## 3.3.2. D2D Cooperation

For D2D cooperation, we definedn,j as the D2D link between local MD n and j, PnD as the power consumption of MD n, and Tn,jtr as the round trip time (RTT) for task transferring between the D2D pairs. This RTT is assumed to be stable during an offloading period, while it may change across different periods. It can be estimated at the beginning of the offloading period, by using the history information or empirical formula [49]. Thus, when the task Γn is executed finally at MD j, the total delay TnD consists of the communication delay Tn,jtr between MD n and MD j and the processing delay TΓnj at MD j. It can be calculated as
(7)TnD=TΓnj+Tn,jtr,∀j∈N,according to (5), TΓnj=Cn/fjL. Note that Tn,jtr=0 when n=j, because there is no task to transfer within the local MD. Thus, the delays of tasks in the device tier all meet (7).In this case, the energy cost of MDn is mainly the transmission energy consumption. It can be given as
(8)EnD=PnDTn,jtr.


## 3.3.3. Edge Computing

For the edge computing approach, the total computing capacity of the BS is denoted asF (in CPU cycles/s), which can be allocated to the computing tasks processed by the BS. Denote fnB as the computing resource allocated to MD n by the BS. Thus, the computing delay of MD n executed by BS is given as
(9)TnB=CnfnB.When the tasks are computed in the edge server, the MDn sends the task Γn to the associated BS. Then, the BS will process the offloaded task by employing its computing resources. Combining with equation (2), the total delay of task Γn processed by the BS is calculated by
(10)TnE=Tntr+TnB.


## 3.3.4. Cloud Computing

For the computing task offloaded to the cloud DC, MDn firstly transmits the task Γn to the nearest BS through a wireless link. Then, the BS forwards the task Γn to the cloud DC through a fiber optical link. Since the cloud servers have plenty of computing resources and the fiber optical link between the edge cloud and the cloud DC is of sufficiently large capacity, the allocation of these resources will not be discussed here. Ordinarily, the computing capability of the cloud DC is much higher than that of the MEC servers.Let the RTT for task transmission between the edge server at BS and cloud server beTB,C. Denote fnC as the cloud computing capability (in CPU cycles/s) assigned to MD n, which is assumed to be a predetermined value according to the cloud computing service [40]. Therefore, the cloud computing delay of MD n is given by
(11)TnfC=CnfnC.Then, combining with equation (2), the total delay of cloud processing for MD n can be expressed as
(12)TnC=Tntr+TB,C+TnfC.The above notations that will be used in this paper are summarized in Table1.Table 1
Notation and corresponding definition.
NotationDefinitionΓnComputing task of MDnLnData size of taskΓn (in bits)CnCPU cycles required to accomplish the taskΓnBThe bandwidth of the BSBnThe uplink bandwidth of MDnRnThe uplink transmission rate of MDnpnThe transmission power density of MDnPnDThe power consumption of MDn in D2D cooperationPnThe total power consumption of MDnGnThe channel gain between the MDn and the BSσ2The power of the additive white Gaussian noisefnLThe local computing capability of MDn (in CPU cycles/s)fnBThe computing resource allocated to MDn by the BSfnCThe computing resource allocated to MDn by the cloudFThe computing capacity of the BSτdmaxThe task computation deadline for MDnTntrThe uplink transmission delay of taskΓn offloaded to the BSTΓnjThe computing delay of taskΓn processed at MD jTn,jtrThe average round trip time between MDn and jTnLThe delay of taskΓn processed locallyTnDThe total delay of taskΓn via D2D cooperationTnBThe computing delay of MDn by the BSTB,CThe round trip time between BS and the cloud serversTnfCThe cloud computing delay of MDnTnCThe total delay of taskΓn processed by the cloud serversEntrThe transmission energy consumption of taskΓn to the BSEnLThe energy consumption of processing the taskΓn locallyEnDThe energy consumption of processingΓn via D2D cooperationAs mentioned earlier, we ignore the return result time of the computed tasks. According to (2)–(12), the total task delay and energy consumption of MD n are calculated, respectively, as
(13)Tn=∑j=1Nxn,jTnD+ynTnE+znTnC,(14)En=xn,nEnL+∑j∈N\nxn,jEnD+1−∑j=1Nxn,jEntr.


## 4. Problem Formulation and Transformation

### 4.1. Problem Formulation

To minimize the total delay, we formulate the task offloading and resource allocation problem with the maximum energy cost constraints. Let the offloading strategy vector of MDn as Θn=xn,1,xn,2,⋯,xn,N,yn,zn and the offloading decision profile of all devices as Θ=Θn,n∈N. The computing resource allocation vector of all devices is denoted as Ω=fnB,n∈N. The maximum energy cost of MD n is denoted as Enmax (e.g., the battery capacity). As a result, the joint task offloading and resource allocation problem are formulated as
(15)P1:minΘ,Ω∑n=1NTn(16)s.t.∑j=1Nxn,j+yn+zn=1,∀n∈N,(17)xn,j,yn,zn∈0,1,∀n∈N,(18)∑n=1NfnB≤F,(19)xn,nEnL+∑j∈N\nxn,jEnD+1−∑j=1Nxn,jEntr≤Enmax.The constraints (16) and (17) denote that each task is processed locally by MD itself or by its neighboring MDs, by edge servers, or by cloud servers. The constraint (18) states the computing resource consumption of all the MDs can not exceed the computing capacity of the edge servers. The constraint (19) indicates the maximum energy cost of MD n. Based on (7), (10), (12), and (13), the total delay of MD n can be written as
(20)Tn=∑j=1Nxn,jTnD+ynTnE+znTnC=∑j=1Nxn,jTΓnj+Tn,jtr+ynTntr+TnB+znTntr+TB,C+TnfC.The optimization problemP1 is a mixed-integer nonlinear problem and is difficult to solve due to the following observation. Since that xn,j, yn, and zn are binary variables, the feasible set of problem (15) is not convex, so that the objective function of problem (15) is not convex. As is shown, problem (15) is a mixed discrete and nonconvex optimization problem, and this kind of problem is usually considered as NP-hard [20]. Then, we rewrite the objective function (15) as
(21)ΨΘ=∑n=1NTn=∑n=1N∑j=1Nxn,jTΓnj+Tn,jtr+∑n=1NynTntr+TnB+∑n=1NznTntr+TB,C+TnfC.In that,P1 is a convex problem with all binary variables fixed. We can use the branch-and-bound method to find a near-optimal solution [38]. But as far as our objective function (15) is concerned, we should note that the complexity of the method remains exponential. The scale of the problem becomes large as the number of MDs grows, which makes it hard to obtain the solution in a reasonable amount of time. Then, in the next section, we will decouple the optimization problem (15) to present an effective computation offloading scheme ADMM to solve the problem P1.


### 4.2. Problem Transformation

To make it possible for each offloading decisions participating in the computation, we will decompose the problemP1 into several small subproblems, so that it can be solved in a distributed manner. Thus, we need to properly handle the coupling constraint among variables. Specially speaking, the optimization variables xn,j, yn, and zn are coupled in the constraints (16), which make the problem inseparable. Thus, to make the problem separable, we introduce the local copies of the global variables and denote them as x^n,j, y^n, and z^n, respectively. Then, we have
(22)x^n,j=xn,j,∀n∈N,j∈N,y^n=yn,∀n∈N,z^n=zn,∀n∈N.Based on equation (22), the coupling constraint of (16) can be written as
(23)∑j=1Nx^n,j+y^n+z^n=1,∀n∈N.LetΘ^=x^n,1,x^n,2,⋯,x^n,N,y^n,z^n,n∈N be the local variables vector of all MDs. Then, we give the equivalent global consensus version of P1 by substituting (16) with (22) and (23) shown as
(24)P2:minΘ,Ω,Θ^ΨΘs.t.17,18,19,22,23.Now, it is obvious that in problemP2, the objective functions ΨΘ with feasible sets are separable. But the consensus constraints (23) remain coupled. As far as the problem P2 is concerned, the numbers of variables and constraints reach N2+2N and 2N2+4N, respectively. The size of this problem becomes extremely large as the number of MDs grows.ADMM is a promising approach to solve the large-scale optimization problem [20], which is originally devised to solve convex optimization problems. Recently, it has been further explored to solve nonconvex problems due to the flexibility of the ADMM framework [30]. In the next section, we will apply ADMM to solve the problem in a distributed fashion.


## 4.1. Problem Formulation

To minimize the total delay, we formulate the task offloading and resource allocation problem with the maximum energy cost constraints. Let the offloading strategy vector of MDn as Θn=xn,1,xn,2,⋯,xn,N,yn,zn and the offloading decision profile of all devices as Θ=Θn,n∈N. The computing resource allocation vector of all devices is denoted as Ω=fnB,n∈N. The maximum energy cost of MD n is denoted as Enmax (e.g., the battery capacity). As a result, the joint task offloading and resource allocation problem are formulated as
(15)P1:minΘ,Ω∑n=1NTn(16)s.t.∑j=1Nxn,j+yn+zn=1,∀n∈N,(17)xn,j,yn,zn∈0,1,∀n∈N,(18)∑n=1NfnB≤F,(19)xn,nEnL+∑j∈N\nxn,jEnD+1−∑j=1Nxn,jEntr≤Enmax.The constraints (16) and (17) denote that each task is processed locally by MD itself or by its neighboring MDs, by edge servers, or by cloud servers. The constraint (18) states the computing resource consumption of all the MDs can not exceed the computing capacity of the edge servers. The constraint (19) indicates the maximum energy cost of MD n. Based on (7), (10), (12), and (13), the total delay of MD n can be written as
(20)Tn=∑j=1Nxn,jTnD+ynTnE+znTnC=∑j=1Nxn,jTΓnj+Tn,jtr+ynTntr+TnB+znTntr+TB,C+TnfC.The optimization problemP1 is a mixed-integer nonlinear problem and is difficult to solve due to the following observation. Since that xn,j, yn, and zn are binary variables, the feasible set of problem (15) is not convex, so that the objective function of problem (15) is not convex. As is shown, problem (15) is a mixed discrete and nonconvex optimization problem, and this kind of problem is usually considered as NP-hard [20]. Then, we rewrite the objective function (15) as
(21)ΨΘ=∑n=1NTn=∑n=1N∑j=1Nxn,jTΓnj+Tn,jtr+∑n=1NynTntr+TnB+∑n=1NznTntr+TB,C+TnfC.In that,P1 is a convex problem with all binary variables fixed. We can use the branch-and-bound method to find a near-optimal solution [38]. But as far as our objective function (15) is concerned, we should note that the complexity of the method remains exponential. The scale of the problem becomes large as the number of MDs grows, which makes it hard to obtain the solution in a reasonable amount of time. Then, in the next section, we will decouple the optimization problem (15) to present an effective computation offloading scheme ADMM to solve the problem P1.


## 4.2. Problem Transformation

To make it possible for each offloading decisions participating in the computation, we will decompose the problemP1 into several small subproblems, so that it can be solved in a distributed manner. Thus, we need to properly handle the coupling constraint among variables. Specially speaking, the optimization variables xn,j, yn, and zn are coupled in the constraints (16), which make the problem inseparable. Thus, to make the problem separable, we introduce the local copies of the global variables and denote them as x^n,j, y^n, and z^n, respectively. Then, we have
(22)x^n,j=xn,j,∀n∈N,j∈N,y^n=yn,∀n∈N,z^n=zn,∀n∈N.Based on equation (22), the coupling constraint of (16) can be written as
(23)∑j=1Nx^n,j+y^n+z^n=1,∀n∈N.LetΘ^=x^n,1,x^n,2,⋯,x^n,N,y^n,z^n,n∈N be the local variables vector of all MDs. Then, we give the equivalent global consensus version of P1 by substituting (16) with (22) and (23) shown as
(24)P2:minΘ,Ω,Θ^ΨΘs.t.17,18,19,22,23.Now, it is obvious that in problemP2, the objective functions ΨΘ with feasible sets are separable. But the consensus constraints (23) remain coupled. As far as the problem P2 is concerned, the numbers of variables and constraints reach N2+2N and 2N2+4N, respectively. The size of this problem becomes extremely large as the number of MDs grows.ADMM is a promising approach to solve the large-scale optimization problem [20], which is originally devised to solve convex optimization problems. Recently, it has been further explored to solve nonconvex problems due to the flexibility of the ADMM framework [30]. In the next section, we will apply ADMM to solve the problem in a distributed fashion.


## 5. Efficient Computation Offloading Scheme

In this section, we develop a parallel optimization framework based on ADMM and difference of convex function (D.C.) programming. First, we derive the augmented Lagrangian function. With corresponding global consensus constraints, we formulate the ADMM iteration steps [28, 38, 50]. Then, the update methods for ADMM iterations are presented, and the overall algorithm is summarized.


### 5.1. Augmented Lagrangian and ADMM Variables

According to [50], the augmented Lagrangian function is expressed as
(25)LρΘ,Θ^,λ,μ,γ=φΘ+∑n=1N∑j=1Nλn,jxn,j−x^n,j+∑n=1Nμnyn−y^n+∑n=1Nγnzn−z^n+ρ2∑n=1N∑j=1Nxn,j−x^n,j2+ρ2∑n=1Nyn−y^n2+ρ2∑n=1Nzn−z^n2,where λ=λn,jn,j∈N, μ=μnn∈N, and γ=γnn∈N are the Lagrange multipliers with respect to the constraint (23), respectively. ρ>0 is the so-called penalty parameter, augmented Lagrangian parameter, which is a constant parameter intend to adjust the convergence speed of ADMM [50].With the ADMM method to solve the problemP2, the resulting optimization steps are described as follows.


### 5.2. Global Variable Update

The global variablesΘ,λ,μ,γ are updated in the t+1-th iteration by settling the following optimization problem [51]:
(26)P3:minΘ,ΩLρΘ,Θ^t,λt,μt,γts.t.17,18,19, where the superscript t stands for the iteration index.We denotexn=xn,j,j∈N as the local offloading decision vector of MD n, y=yn,n∈N as the decision vector of offloading tasks to BS j. For cloud computing, z=zn,n∈N is the decision vector of offloading tasks to the cloud DC. Then, omitting the local copies of the variables x^n,j,y^n,z^n, the objective function in P3 can be rewritten as
(27)LρΘ,Θ^t,λt,μt,γt=∑j=1Mfjxn+gy+hz,where the functions fjxn, gy, and hz are given
(28)fjxn=∑n∈Nρ2xn,j−x^n,jt2+TnL+λntxn,j,(29)gy=∑n∈Nρ2yn−y^nt2+TnE+μntyn,(30)hz=∑n∈Nρ2zn−z^nt2+TnC+γntzn.Therefore, it is easy to recognize that the objective function and the feasible region inP3 are separable completely. As a result, P3 can be decomposed equivalently into the following three subproblems (P1′, P2′, and P3′), which are given by
(31)P1′:minxnfjxns.t.18,19,xn,j∈0,1,∀n∈N,(32)P2′:minygys.t.yn∈0,1,∀n∈N.Meanwhile, the subproblemP3′ related to the cloud servers is written as
(33)P3′:minzhzs.t.zn∈0,1,∀n∈N.


#### 5.2.1. The Solution of the First Subproblem P1′

There are some difficulties in solving this subproblemP1′ with the existence of the binary variable constraint. To overcome the difficulties, an equivalent transformation of the original problem is necessary. We can transform the binary constraints in P1′ as
(34)∑n∈Nxn,j−xn,j2≤0,(35)0≤xn,j≤1,∀n∈N.By replacing the binary constraint with (34) and (35), problem P1′ is rewritten as
(36)P4:minxnfjxns.t.18,19,34,35,∀n∈N.After the above equivalent transformations, the objective function ofP4 is linear and constraints except (34) are convex. To deal with (34), we further transform P4 as given by
(37)P5:minxjfjxj+α∑n∈Nxn,j−xn,j2s.t.18,19,35,∀n∈N,whereα acts as a penalty factor. It is proven for a sufficiently large amount; the problem P5 is equivalent to P4 [52].Here, we defineφjxn and ϕjxn,j as
(38)φjxn=fjxn+α∑n∈Nxn,j,(39)ϕjxn,j=α∑n∈Nxn,j2.Then, it can be found that the objective function can be written as the difference of the two convex functionsφjxn and ϕjxn,j. We can find that P5 is a D.C. programming problem [53]. Therefore, to solve P5, we can exploit the sequential convex approximation [24] of ϕjxn,j in the xn domain. ϕjxn,j can be approximated by its first-order Taylor expansion, and the objective function can be derived as
(40)φjxn−ϕjxn,j+∇xjϕjxn,j×xn,j−xn,jt,where ∇xnϕjxn,j is the gradient of ϕjxn,j at xn and can be expressed as ∇xnϕjxn,j=∂ϕjxn,j/∂xn,j,∀j∈N.Then, we can obtain an approximation solution to get a local optimal solutionxnt during each iteration, which is sketched in Algorithm 1, where xnt is the solution at the t-th iteration. As a result, P5 is a convex problem and can be solved efficiently by the standard convex optimization methods [54]. We can obtain near-optimal solution xnt of P5 by iteratively solving.Algorithm 1: D.C-based algorithm for subproblem P1′.
1. Initialization:Choose an initial feasible solutionxn,j0 of P1′,t=0.2. Iteration:repeatSolve the following convex problemP5:minxnφjxn−ϕjxn,j+∇xnϕjxn,j×xn,j−xn,jts.t. (18),(19),(35)obtain the optimal solutionxnt+1update t=t+13. until convergence ofxn.It is worth noting that the solutionxnt is better than the previous solution xnt−1. Since the constraint set is compact, the sequence xntt=1,2,3,⋯,n is proved to be convergent [52] by Cauchy theorem. The iterative process can stop after finite iterations. Given an initial point, due to the convexity of each iteration, Algorithm 1 converges to the same solution. In the issue, the convergence properties in Algorithm 1 could facilitate the convergence of ADMM.


#### 5.2.2. The Solutions of the Subproblem P2′

For the subproblemP2′, it is an unconstrained binary optimization problem. Due to the fact that possible values of yn are 0 and 1, we have yn2=yn. Then, the expression after the summation sign of (29) is
(41)ρ2yn−2yny^nt2+y^nt2+TnE+μntyn.By comparing the corresponding objective function values of two possible solutions, the solution can be given by(42)yn=0ρ2−ρy^nt+TnE+μnt>0,1ρ2−ρy^nt+TnE+μnt≤0.


#### 5.2.3. The Solutions of the Subproblem P3′

For the subproblemP3′, it is also an unconstrained binary optimization problem as P2′. Thus, the solution can also be given as
(43)zn=0ρ2−ρz^nt+TnC+γnt>0,1ρ2−ρz^nt+TnC+γnt≤0.


### 5.3. Local Variable Update

Now, we move on to the local variables. After obtaining the global variables, at thet+1-th iteration, the local variables Θ^ are updated by solving the following optimization problem:
(44)P6:minΘ^LρΘt+1,Θ^t,λt,μt,γts.t.23,x^n,j,y^n,z^n∈0,1,∀n∈N,j∈N.After eliminating some constant terms from the objective function, it is equivalent to solve the following problem:(45)P7:minΘ^∑n=1NFΘ^ns.t.23,x^n,j,y^n,z^n∈0,1,∀n∈N,j∈N,where the function FΘ^n is given by
(46)FΘ^n=∑j=1Mρ2x^n,j2−ρxn,jt+1+λn,jtx^n,j+ρ2y^n2−ρynt+1+μnty^n+ρ2z^n2−ρznt+1+γntz^n.As mentioned earlier, the constraint (23) implies that only one of xn,j, yn, and zn for the MD n can be 1 at any time. Thus, there are total N+2 possible solutions for each MD n. We only need to calculate the corresponding objective function values of the N+2 different offloading decisions and choose the minimum one, which corresponds to the optimal solution. Formally, the optimal solution of P6 is written as
(47)x^n,j=1,y^n=0,z^n=0,ifcn,j=Cn,min,∀n∈N,x^n,j=0,y^n=1,z^n=0,ifcn,N+1=Cn,min,∀n∈N,x^n,j=0,y^n=0,z^n=1,ifcn,N+2=Cn,min,∀n∈N,where cn,j=ρ/2−ρxn,jt+1−λn,jt, cn,N+1=ρ/2−ρynt+1−μnt, and cn,N+2=ρ/2−ρznt+1−γnt and Cn,min is the minimum value of all possible solutions for MD n, which is expressed as Cn,min=mincn,j∈N,cn,N+1,cn,N+2.


### 5.4. Dual Variable Update

After obtaining the global and local variables, we perform the process of dual variable update. In thet+1-th iteration, the dual variables are updated as follows:
(48)λn,jt+1=λn,jt+ρxn,jt+1−x^n,jt+1,∀n∈N,j∈N,(49)μnt+1=μnt+ρynt+1−y^nt+1,∀n∈N,(50)γnt+1=γnt+ρznt+1−z^nt+1,∀n∈N.In summary, the efficient offloading scheme is obtained by sequential iteration for global variables, local variables, and dual variables. By leveraging the ADMM algorithm to the problem P3, we firstly minimize the augmented Lagrangian function (25) over the global variables and decompose the optimization problem into some smaller subproblems, which is executed in parallel to improve the computing speed. Then, we performed the local variable update based on equation (47). Finally, the dual variables are updated based on equations (48)–(50). The algorithm is summarized in Algorithm 2.Algorithm 2: Parallel optimization algorithm via ADMM.
1. Initialization:t =1,ε=0.01, ρ=0.1, λt=0, and tmax=2000Choose an initial feasible solutionΘ^t satisfying (23)2. Iteration:whileΘ−Θ^2≥ε and t≤tmaxdoI) Global variable update: M computation units solveP1′.andP2′ in parallel and a computation unit solves P3′ toupdate the global variablesΘt+1II) Local variable update: Update the local variablesΘ^t+1 based on (47)III) Dual variable update: Update the dual variablesλ,μ,γt+1 based on the equations (48)-(50)end while3. Output:Output the optimal solutionxn,j,yn,zn∗.


## 5.1. Augmented Lagrangian and ADMM Variables

According to [50], the augmented Lagrangian function is expressed as
(25)LρΘ,Θ^,λ,μ,γ=φΘ+∑n=1N∑j=1Nλn,jxn,j−x^n,j+∑n=1Nμnyn−y^n+∑n=1Nγnzn−z^n+ρ2∑n=1N∑j=1Nxn,j−x^n,j2+ρ2∑n=1Nyn−y^n2+ρ2∑n=1Nzn−z^n2,where λ=λn,jn,j∈N, μ=μnn∈N, and γ=γnn∈N are the Lagrange multipliers with respect to the constraint (23), respectively. ρ>0 is the so-called penalty parameter, augmented Lagrangian parameter, which is a constant parameter intend to adjust the convergence speed of ADMM [50].With the ADMM method to solve the problemP2, the resulting optimization steps are described as follows.


## 5.2. Global Variable Update

The global variablesΘ,λ,μ,γ are updated in the t+1-th iteration by settling the following optimization problem [51]:
(26)P3:minΘ,ΩLρΘ,Θ^t,λt,μt,γts.t.17,18,19, where the superscript t stands for the iteration index.We denotexn=xn,j,j∈N as the local offloading decision vector of MD n, y=yn,n∈N as the decision vector of offloading tasks to BS j. For cloud computing, z=zn,n∈N is the decision vector of offloading tasks to the cloud DC. Then, omitting the local copies of the variables x^n,j,y^n,z^n, the objective function in P3 can be rewritten as
(27)LρΘ,Θ^t,λt,μt,γt=∑j=1Mfjxn+gy+hz,where the functions fjxn, gy, and hz are given
(28)fjxn=∑n∈Nρ2xn,j−x^n,jt2+TnL+λntxn,j,(29)gy=∑n∈Nρ2yn−y^nt2+TnE+μntyn,(30)hz=∑n∈Nρ2zn−z^nt2+TnC+γntzn.Therefore, it is easy to recognize that the objective function and the feasible region inP3 are separable completely. As a result, P3 can be decomposed equivalently into the following three subproblems (P1′, P2′, and P3′), which are given by
(31)P1′:minxnfjxns.t.18,19,xn,j∈0,1,∀n∈N,(32)P2′:minygys.t.yn∈0,1,∀n∈N.Meanwhile, the subproblemP3′ related to the cloud servers is written as
(33)P3′:minzhzs.t.zn∈0,1,∀n∈N.


### 5.2.1. The Solution of the First Subproblem P1′

There are some difficulties in solving this subproblemP1′ with the existence of the binary variable constraint. To overcome the difficulties, an equivalent transformation of the original problem is necessary. We can transform the binary constraints in P1′ as
(34)∑n∈Nxn,j−xn,j2≤0,(35)0≤xn,j≤1,∀n∈N.By replacing the binary constraint with (34) and (35), problem P1′ is rewritten as
(36)P4:minxnfjxns.t.18,19,34,35,∀n∈N.After the above equivalent transformations, the objective function ofP4 is linear and constraints except (34) are convex. To deal with (34), we further transform P4 as given by
(37)P5:minxjfjxj+α∑n∈Nxn,j−xn,j2s.t.18,19,35,∀n∈N,whereα acts as a penalty factor. It is proven for a sufficiently large amount; the problem P5 is equivalent to P4 [52].Here, we defineφjxn and ϕjxn,j as
(38)φjxn=fjxn+α∑n∈Nxn,j,(39)ϕjxn,j=α∑n∈Nxn,j2.Then, it can be found that the objective function can be written as the difference of the two convex functionsφjxn and ϕjxn,j. We can find that P5 is a D.C. programming problem [53]. Therefore, to solve P5, we can exploit the sequential convex approximation [24] of ϕjxn,j in the xn domain. ϕjxn,j can be approximated by its first-order Taylor expansion, and the objective function can be derived as
(40)φjxn−ϕjxn,j+∇xjϕjxn,j×xn,j−xn,jt,where ∇xnϕjxn,j is the gradient of ϕjxn,j at xn and can be expressed as ∇xnϕjxn,j=∂ϕjxn,j/∂xn,j,∀j∈N.Then, we can obtain an approximation solution to get a local optimal solutionxnt during each iteration, which is sketched in Algorithm 1, where xnt is the solution at the t-th iteration. As a result, P5 is a convex problem and can be solved efficiently by the standard convex optimization methods [54]. We can obtain near-optimal solution xnt of P5 by iteratively solving.Algorithm 1: D.C-based algorithm for subproblem P1′.
1. Initialization:Choose an initial feasible solutionxn,j0 of P1′,t=0.2. Iteration:repeatSolve the following convex problemP5:minxnφjxn−ϕjxn,j+∇xnϕjxn,j×xn,j−xn,jts.t. (18),(19),(35)obtain the optimal solutionxnt+1update t=t+13. until convergence ofxn.It is worth noting that the solutionxnt is better than the previous solution xnt−1. Since the constraint set is compact, the sequence xntt=1,2,3,⋯,n is proved to be convergent [52] by Cauchy theorem. The iterative process can stop after finite iterations. Given an initial point, due to the convexity of each iteration, Algorithm 1 converges to the same solution. In the issue, the convergence properties in Algorithm 1 could facilitate the convergence of ADMM.


### 5.2.2. The Solutions of the Subproblem P2′

For the subproblemP2′, it is an unconstrained binary optimization problem. Due to the fact that possible values of yn are 0 and 1, we have yn2=yn. Then, the expression after the summation sign of (29) is
(41)ρ2yn−2yny^nt2+y^nt2+TnE+μntyn.By comparing the corresponding objective function values of two possible solutions, the solution can be given by(42)yn=0ρ2−ρy^nt+TnE+μnt>0,1ρ2−ρy^nt+TnE+μnt≤0.


### 5.2.3. The Solutions of the Subproblem P3′

For the subproblemP3′, it is also an unconstrained binary optimization problem as P2′. Thus, the solution can also be given as
(43)zn=0ρ2−ρz^nt+TnC+γnt>0,1ρ2−ρz^nt+TnC+γnt≤0.


## 5.2.1. The Solution of the First Subproblem P1′

There are some difficulties in solving this subproblemP1′ with the existence of the binary variable constraint. To overcome the difficulties, an equivalent transformation of the original problem is necessary. We can transform the binary constraints in P1′ as
(34)∑n∈Nxn,j−xn,j2≤0,(35)0≤xn,j≤1,∀n∈N.By replacing the binary constraint with (34) and (35), problem P1′ is rewritten as
(36)P4:minxnfjxns.t.18,19,34,35,∀n∈N.After the above equivalent transformations, the objective function ofP4 is linear and constraints except (34) are convex. To deal with (34), we further transform P4 as given by
(37)P5:minxjfjxj+α∑n∈Nxn,j−xn,j2s.t.18,19,35,∀n∈N,whereα acts as a penalty factor. It is proven for a sufficiently large amount; the problem P5 is equivalent to P4 [52].Here, we defineφjxn and ϕjxn,j as
(38)φjxn=fjxn+α∑n∈Nxn,j,(39)ϕjxn,j=α∑n∈Nxn,j2.Then, it can be found that the objective function can be written as the difference of the two convex functionsφjxn and ϕjxn,j. We can find that P5 is a D.C. programming problem [53]. Therefore, to solve P5, we can exploit the sequential convex approximation [24] of ϕjxn,j in the xn domain. ϕjxn,j can be approximated by its first-order Taylor expansion, and the objective function can be derived as
(40)φjxn−ϕjxn,j+∇xjϕjxn,j×xn,j−xn,jt,where ∇xnϕjxn,j is the gradient of ϕjxn,j at xn and can be expressed as ∇xnϕjxn,j=∂ϕjxn,j/∂xn,j,∀j∈N.Then, we can obtain an approximation solution to get a local optimal solutionxnt during each iteration, which is sketched in Algorithm 1, where xnt is the solution at the t-th iteration. As a result, P5 is a convex problem and can be solved efficiently by the standard convex optimization methods [54]. We can obtain near-optimal solution xnt of P5 by iteratively solving.Algorithm 1: D.C-based algorithm for subproblem P1′.
1. Initialization:Choose an initial feasible solutionxn,j0 of P1′,t=0.2. Iteration:repeatSolve the following convex problemP5:minxnφjxn−ϕjxn,j+∇xnϕjxn,j×xn,j−xn,jts.t. (18),(19),(35)obtain the optimal solutionxnt+1update t=t+13. until convergence ofxn.It is worth noting that the solutionxnt is better than the previous solution xnt−1. Since the constraint set is compact, the sequence xntt=1,2,3,⋯,n is proved to be convergent [52] by Cauchy theorem. The iterative process can stop after finite iterations. Given an initial point, due to the convexity of each iteration, Algorithm 1 converges to the same solution. In the issue, the convergence properties in Algorithm 1 could facilitate the convergence of ADMM.


## 5.2.2. The Solutions of the Subproblem P2′

For the subproblemP2′, it is an unconstrained binary optimization problem. Due to the fact that possible values of yn are 0 and 1, we have yn2=yn. Then, the expression after the summation sign of (29) is
(41)ρ2yn−2yny^nt2+y^nt2+TnE+μntyn.By comparing the corresponding objective function values of two possible solutions, the solution can be given by(42)yn=0ρ2−ρy^nt+TnE+μnt>0,1ρ2−ρy^nt+TnE+μnt≤0.


## 5.2.3. The Solutions of the Subproblem P3′

For the subproblemP3′, it is also an unconstrained binary optimization problem as P2′. Thus, the solution can also be given as
(43)zn=0ρ2−ρz^nt+TnC+γnt>0,1ρ2−ρz^nt+TnC+γnt≤0.


## 5.3. Local Variable Update

Now, we move on to the local variables. After obtaining the global variables, at thet+1-th iteration, the local variables Θ^ are updated by solving the following optimization problem:
(44)P6:minΘ^LρΘt+1,Θ^t,λt,μt,γts.t.23,x^n,j,y^n,z^n∈0,1,∀n∈N,j∈N.After eliminating some constant terms from the objective function, it is equivalent to solve the following problem:(45)P7:minΘ^∑n=1NFΘ^ns.t.23,x^n,j,y^n,z^n∈0,1,∀n∈N,j∈N,where the function FΘ^n is given by
(46)FΘ^n=∑j=1Mρ2x^n,j2−ρxn,jt+1+λn,jtx^n,j+ρ2y^n2−ρynt+1+μnty^n+ρ2z^n2−ρznt+1+γntz^n.As mentioned earlier, the constraint (23) implies that only one of xn,j, yn, and zn for the MD n can be 1 at any time. Thus, there are total N+2 possible solutions for each MD n. We only need to calculate the corresponding objective function values of the N+2 different offloading decisions and choose the minimum one, which corresponds to the optimal solution. Formally, the optimal solution of P6 is written as
(47)x^n,j=1,y^n=0,z^n=0,ifcn,j=Cn,min,∀n∈N,x^n,j=0,y^n=1,z^n=0,ifcn,N+1=Cn,min,∀n∈N,x^n,j=0,y^n=0,z^n=1,ifcn,N+2=Cn,min,∀n∈N,where cn,j=ρ/2−ρxn,jt+1−λn,jt, cn,N+1=ρ/2−ρynt+1−μnt, and cn,N+2=ρ/2−ρznt+1−γnt and Cn,min is the minimum value of all possible solutions for MD n, which is expressed as Cn,min=mincn,j∈N,cn,N+1,cn,N+2.


## 5.4. Dual Variable Update

After obtaining the global and local variables, we perform the process of dual variable update. In thet+1-th iteration, the dual variables are updated as follows:
(48)λn,jt+1=λn,jt+ρxn,jt+1−x^n,jt+1,∀n∈N,j∈N,(49)μnt+1=μnt+ρynt+1−y^nt+1,∀n∈N,(50)γnt+1=γnt+ρznt+1−z^nt+1,∀n∈N.In summary, the efficient offloading scheme is obtained by sequential iteration for global variables, local variables, and dual variables. By leveraging the ADMM algorithm to the problem P3, we firstly minimize the augmented Lagrangian function (25) over the global variables and decompose the optimization problem into some smaller subproblems, which is executed in parallel to improve the computing speed. Then, we performed the local variable update based on equation (47). Finally, the dual variables are updated based on equations (48)–(50). The algorithm is summarized in Algorithm 2.Algorithm 2: Parallel optimization algorithm via ADMM.
1. Initialization:t =1,ε=0.01, ρ=0.1, λt=0, and tmax=2000Choose an initial feasible solutionΘ^t satisfying (23)2. Iteration:whileΘ−Θ^2≥ε and t≤tmaxdoI) Global variable update: M computation units solveP1′.andP2′ in parallel and a computation unit solves P3′ toupdate the global variablesΘt+1II) Local variable update: Update the local variablesΘ^t+1 based on (47)III) Dual variable update: Update the dual variablesλ,μ,γt+1 based on the equations (48)-(50)end while3. Output:Output the optimal solutionxn,j,yn,zn∗.


## 6. Evaluation

In this section, we will present simulation results to verify the performance of the proposed D2D-enabled three-tier MEC networks. In our simulations, the number of BSs is 4. Each BS has a radius of 400 m. And there are 80 MDs uniformly distributed in the coverage of each BS. We assume that each MD can establish one wireless link with the BS and one D2D link with a neighboring MD. The maximum range of each D2D link is set as 50 m. The channel gain model of all wireless links is chosen ash=127+30log10d (d in km), as suggested in [55]. Each MD has a task to be computed. The input data size of task n is Ln∈ [0.1, 4.0] Mbits. And the required computation amount of each task is assumed to be Cn∈2×109,5×109 CPU cycles. The maximum delay tolerance of each task is 1 s. The computing capability of each MD is uniformly distributed from 0.5×109 to 2×109 CPU cycles/s. The maximum transmission power is set as 0.5 W [56] for each MD.All random variables are independent for different MDs, modeling heterogeneous mobile computing resources. The main system parameters used in the simulation are summarized in Table2, if not specified.Table 2
Simulation parameters.
ParametersValueThe bandwidth resourceBn20 MHz [20]The number of BSsM4The transmission power of MDsPn20 dBm [4]Power of background noiseσ2-174 dBm/Hz [57]Path-loss model127+30∗log10d, d (km)Local computational capabilityfnL0.5GHz [56]Local computation powerPnL24 dBm [20]The computing capability of BSsF20 GHz [38]The computing capability of cloudF100 GHz [33]


### 6.1. Performance Comparison

We first compare the performance of the proposed D2D-enabled three-tier MEC framework with the other two networks [23, 35, 58]:
(1)
In the D2D networks, tasks which can be cooperatively processed only among local MDs(2)
In the MEC networks, vertical cooperation among local MD itself, edge node, and remote cloud node.(3)
In the D2D-enabled MEC networks, where each task can be processed locally by MD itself or its neighboring MDs, by edge cloud, or by remote cloud.From Figure3, we can observe that the number of supporting MDs in these different networks to edge computing resources. First of all, the numbers of supporting MDs in the MEC networks and the D2D-enabled MEC networks both increases with the edge computing resources. While the number of supporting MDs in the D2D networks keeps invariable. The reason is that the D2D networks does not utilize the edge computing resources. Secondly, the D2D-enabled three-tier MEC networks achieves the best performance among these three systems. The reason is that the D2D-enabled MEC networks can utilize the computing resources of MDs, the edge servers, even the central cloud servers when the edge computing resource is insufficient. Moreover, the computing capacity of the D2D-enabled MEC networks is larger than that of the MEC networks since the computing resource of the MDs can be used for processing the offloaded computing tasks. Finally, the upper bounds of the computing capacity of the D2D-enabled MEC networks and the MEC networks are the same, that is the overall number of MDs, i.e., 80. The result indicates that employing D2D communications can notably save the required computing resources from edge data center or cloud data center.Figure 3
The number of supported MDs.Figure4 depicts the access ratio. It is the proportion of MDs that can be supported versus the total number of MDs. It can be observed that the access rates of both the MEC networks and D2D-enabled MEC networks decreasing with the number of MDs due to the limited edge computing resources, while the access rate of the D2D networks will correspondingly increase. The reason is that, the allocated edge computing resources for each MD in the MEC networks and D2D-enabled MEC networks decreases with the total number of MDs, which results in the smaller proportion of MDs that can be supported. Furthermore, the MDs computing resources can be fully utilized as the total number of MDs in the D2D networks increase, which eventually improves the access rate. We can also observe that the access rate of the D2D-enabled MEC networks decreases slower than that of the MEC networks since it utilizes the MD computing resources for capacity enhancement.Figure 4
Access rate with different numbers of MDs.Figure5 illustrates the average required computing resources for each MD, versus the maximum range of D2D links in the MEC networks and D2D-enabled three-tier MEC networks, respectively. It shows that the average required computing resources in the D2D-enabled MEC networks are smaller than those in the MEC networks, especially when the maximum range of D2D links becomes large. This is because each MD has more potential neighboring MDs to offload tasks as the range of D2D link becomes larger. In this way, the computing resources of all MDs can be further utilized via D2D offloading. We can also observe a reduced required computing resource with the decreased delay tolerance in both networks.Figure 5
The average required edge computing resource vs. the maximum range of D2D links.Figure6 presents the total delay with different computation processing densities. Comparing the proposed scheme with two benchmarks (i.e., MEC networks and D2D networks), we can observe the following: when the processing density is low, the task processed at the device tier performs well compared to offloading to the edge cloud or central cloud DC. This is because the transmission latency on account of offloading from the MD to the edge node or cloud node dominates over the local processing time at the local device tier.Figure 6
Total delay with different processing densities.Nevertheless, as the processing density increases, the proposed scheme outperforms the D2D processing at the device tier. Furthermore, with higher processing density, only the MEC networks may not be able to meet the low-latency requirement. On the other hand, as our proposed D2D-enabled MEC networks optimize the offloading decisions, we obtain a significantly lower total latency compared to the other solutions.


## 6.1. Performance Comparison

We first compare the performance of the proposed D2D-enabled three-tier MEC framework with the other two networks [23, 35, 58]:
(1)
In the D2D networks, tasks which can be cooperatively processed only among local MDs(2)
In the MEC networks, vertical cooperation among local MD itself, edge node, and remote cloud node.(3)
In the D2D-enabled MEC networks, where each task can be processed locally by MD itself or its neighboring MDs, by edge cloud, or by remote cloud.From Figure3, we can observe that the number of supporting MDs in these different networks to edge computing resources. First of all, the numbers of supporting MDs in the MEC networks and the D2D-enabled MEC networks both increases with the edge computing resources. While the number of supporting MDs in the D2D networks keeps invariable. The reason is that the D2D networks does not utilize the edge computing resources. Secondly, the D2D-enabled three-tier MEC networks achieves the best performance among these three systems. The reason is that the D2D-enabled MEC networks can utilize the computing resources of MDs, the edge servers, even the central cloud servers when the edge computing resource is insufficient. Moreover, the computing capacity of the D2D-enabled MEC networks is larger than that of the MEC networks since the computing resource of the MDs can be used for processing the offloaded computing tasks. Finally, the upper bounds of the computing capacity of the D2D-enabled MEC networks and the MEC networks are the same, that is the overall number of MDs, i.e., 80. The result indicates that employing D2D communications can notably save the required computing resources from edge data center or cloud data center.Figure 3
The number of supported MDs.Figure4 depicts the access ratio. It is the proportion of MDs that can be supported versus the total number of MDs. It can be observed that the access rates of both the MEC networks and D2D-enabled MEC networks decreasing with the number of MDs due to the limited edge computing resources, while the access rate of the D2D networks will correspondingly increase. The reason is that, the allocated edge computing resources for each MD in the MEC networks and D2D-enabled MEC networks decreases with the total number of MDs, which results in the smaller proportion of MDs that can be supported. Furthermore, the MDs computing resources can be fully utilized as the total number of MDs in the D2D networks increase, which eventually improves the access rate. We can also observe that the access rate of the D2D-enabled MEC networks decreases slower than that of the MEC networks since it utilizes the MD computing resources for capacity enhancement.Figure 4
Access rate with different numbers of MDs.Figure5 illustrates the average required computing resources for each MD, versus the maximum range of D2D links in the MEC networks and D2D-enabled three-tier MEC networks, respectively. It shows that the average required computing resources in the D2D-enabled MEC networks are smaller than those in the MEC networks, especially when the maximum range of D2D links becomes large. This is because each MD has more potential neighboring MDs to offload tasks as the range of D2D link becomes larger. In this way, the computing resources of all MDs can be further utilized via D2D offloading. We can also observe a reduced required computing resource with the decreased delay tolerance in both networks.Figure 5
The average required edge computing resource vs. the maximum range of D2D links.Figure6 presents the total delay with different computation processing densities. Comparing the proposed scheme with two benchmarks (i.e., MEC networks and D2D networks), we can observe the following: when the processing density is low, the task processed at the device tier performs well compared to offloading to the edge cloud or central cloud DC. This is because the transmission latency on account of offloading from the MD to the edge node or cloud node dominates over the local processing time at the local device tier.Figure 6
Total delay with different processing densities.Nevertheless, as the processing density increases, the proposed scheme outperforms the D2D processing at the device tier. Furthermore, with higher processing density, only the MEC networks may not be able to meet the low-latency requirement. On the other hand, as our proposed D2D-enabled MEC networks optimize the offloading decisions, we obtain a significantly lower total latency compared to the other solutions.


## 7. Conclusion

In this article, we consider cooperative offloading in D2D-enabled three-tier MEC networks as a part of the IoT. By leveraging the advantages of both MEC and D2D cooperation techniques, the computing resources in edge nodes, cloud nodes, and D2D MDs can be effectively utilized. We jointly optimize the task offloading decisions and computing resource allocation to minimize the total delay of tasks. The formulated problem is a mixed-integer nonlinear optimization problem. When networks grow larger, it is difficult to be solved. To work out this problem, we adopt a parallel optimization framework based on the ADMM algorithm. Simulation results show that the proposed framework and solution outperform the other solutions with various parameters. In our future work, we may consider the queue of tasks, partible offloading, and privacy protection when investigating the offloading problem.



---

*Source: 9977700-2021-08-16.xml*