# Energy-Efficient Mobile Edge Computing: Three-Tier Computing under Heterogeneous Networks

Authors: Yongsheng Pei; Zhangyou Peng; Zhenling Wang; Haojia Wang
Journal: Wireless Communications and Mobile Computing
 (2020)

---

## Abstract

Mobile edge computing (MEC) is a promising technique to meet the demands of computing-intensive and delay-sensitive applications by providing computation and storage capabilities in close proximity to mobile users. In this paper, we study energy-efficient resource allocation (EERA) schemes for hierarchical MEC architecture in heterogeneous networks. In this architecture, both small base station (SBS) and macro base station (MBS) are equipped with MEC servers and help smart mobile devices (SMDs) to perform tasks. Each task can be partitioned into three parts. The SMD, SBS, and MBS each perform a part of the task and form a three-tier computing structure. Based on this computing structure, an optimization problem is formulated to minimize the energy consumption of all SMDs subject to the latency constraints, where radio and computation resources are considered jointly. Then, an EERA mechanism based on the variable substitution technique is designed to calculate the optimal workload distribution, edge computation capability allocation, and SMDs’ transmit power. Finally, numerical simulation results demonstrate the energy efficiency improvement of the proposed EERA mechanism over the baseline schemes.


---

## Body

## 1. Introduction

Driven by the rapid development of Internet of Things and mobile Internet, many novel applications are emerging [1]. However, most of these applications are computing-intensive and delay-sensitive, e.g., augmented reality, face recognition, and healthcare [2]. Running these applications locally is very challenging for smart mobile devices (SMDs) when ensuring users’ quality of experience (QoE) because of the limited resources of SMDs. How to complete the applications while guaranteeing users’ QoE becomes the focus of academic and industrial communities. Mobile edge computing (MEC) is a promising technique to solve this problem, which endows the radio access network with computation and storage capabilities. In order to improve users’ QoE, MEC helps SMDs complete applications by performing some tasks in the edge nodes of networks, which reduces the latency and energy consumption of task execution thanks to the close proximity of edge nodes to SMDs [3, 4].Extensive research on MEC has been conducted from many perspectives, e.g., single-server MEC models and multiserver MEC models. Regarding the single-server MEC models, much work has been done, e.g., single-user models [5–9] and multiuser models [10–15]. For a single-user MEC model, the authors in [5] considered a binary computation offloading model and derived a data consumption rate threshold that decided to offload the whole task or execute the entire task locally. Based on that work, for further reducing the energy consumption of SMDs, partial offloading was introduced into the single-user model. The task was partitioned into two parts, one of which was offloaded [6, 7]. Considering the stochastic arrival of tasks, the optimal task scheduling policy was derived to minimize the weighted sum of the energy consumption and latency [8]. In addition, the energy harvesting technique was incorporated into the MEC model and the Lyapunov optimization-based dynamic computation offloading algorithm was proposed in [9]. For a multiuser MEC model, to satisfy the requirements of as many users as possible in a channel environment with wireless interference, the multiuser offloading system was formulated as a game and analyzed to admit a Nash equilibrium [10]. Considering inelastic computation tasks and non-negligible task execution durations, the authors in [11] proposed an energy-efficient resource allocation schemes. To deal with the arbitrary arrival of tasks in multiuser MEC system, tasks scheduling techniques were utilized in [12, 13]. To reduce the redundant execution of the same tasks and minimize the energy consumption, the storage resource of the base station was utilized in [14]. For further improving users’ QoE, wireless power transfer was added into the multiuser MEC model and an access point energy minimization problem was formulated [15].Regarding the multiserver MEC models, many edge cloud architectures are emerging, e.g., flat edge cloud architectures [16–19] and hierarchical edge cloud architectures [20–22]. In the flat edge cloud architectures, MEC servers are located at the same tier. In the hierarchical edge cloud architectures, MEC servers are located at different tiers. And MEC servers in different tiers have distinct computation and storage capabilities [3, 23]. For a flat edge cloud architecture, geography information of SMDs and MEC servers was used to reduce the task execution delays in [16]. Considering maximizing the revenue of service providers, resources from different service providers were centralized to create a resource pool and the revenue was allocated by using core and Shapley values [17]. To minimize the communication latency, a cloudlet selection model based on mixed integer linear programming was developed in [18]. Furthermore, by utilizing the idle computing resources of vehicles, the authors in [19] proposed a decentralized framework named Autonomous Vehicular Edge to increase the computational capabilities of vehicles. For a hierarchical edge cloud architecture, a three-tier MEC model was built on the basis of LTE-advanced mobile backhaul network [20]. For improving the cost efficiency of network operators, the authors in [21] took the cost disparity of the edge tiers into account. Under a three-tier MEC model, the Stackelberg game was used to allocate the limited computing resources of edge severs to the data service subscribers [22].Combined with heterogeneous networks, the hierarchical MEC was further studied. The small base station (SBS) and macro base station (MBS) are equipped with MEC servers to serve SMDs. Particularly, in [24], offloading decisions and radio resource were optimized jointly for minimizing the system energy cost. Then, the framework was developed further. SBSs were endowed with computing capabilities. And a resource allocation problem for minimizing the energy consumption of mobile users and MEC servers was formulated [25]. Based on the heterogeneous network powered by hybrid energy, user association and resource allocation were optimized for maximizing the network utility [26]. Considering the variability of mobile devices’ capabilities and user preferences, offloading decisions and resource allocation were optimized for maximizing system utility [27]. In addition, a novel information-centric heterogeneous network framework was designed and a virtual resource allocation problem was formulated in [28].


### 1.1. Motivations and Contributions

Hierarchical architectures of edge servers have an advantage over flat architectures in serving the peak loads [23, 29]. In addition, under the three-tier MEC architectures, previous studies focused on the system construction [20–22] and maximization of the system utility [26–28]. However, it is also important how to allocate computation and communication resource energy efficiently under a three-tier MEC architecture to improve users’ QoE. In this paper, we investigate a multiuser three-tier computing model under heterogeneous networks. The SBS integrated with relatively small computation capability and MBS integrated with great computation capability jointly execute tasks. Based on this hierarchical MEC model, an energy-efficient resource allocation (EERA) scheme is proposed. In EERA, the computation and radio resources are optimized jointly for minimizing the energy consumption of all SMDs. The main contributions of this paper are summarized as follows:
(1)
Based on heterogeneous networks, we establish a three-tier computing model, including local computing, SBS computing, and MBS computing. An energy-efficient optimization problem is formulated. Workload placement strategy, transmit power, and computation capability allocation are optimized to minimize SMDs’ energy consumption under task delay constraints.
(2)
We propose an EERA scheme based on the variable substitution technique. In this scheme, the optimal workload distribution and computation capability allocation are first obtained. Then, the optimal SMDs’ transmit power is derived through the variable substitution.
(3)
Numerical simulation experiments are conducted. Simulation results are presented to validate that EERA outperforms other baseline schemes and effectively reduces the SMDs’ energy consumption.


### 1.2. Organization

The rest of this paper is organized as follows. In Section2, the three-tier computing model is presented and the energy-efficient optimization problem is formulated. In Section 3, EERA based on the variable substitution technique is proposed, where workload distribution in three-tier, computation capability allocation from SBS and SMDs’ transmit power are optimized jointly to minimize SMDs’ energy consumption. Numerical results are provided in Section 4, and conclusions are presented in Section 5.


## 1.1. Motivations and Contributions

Hierarchical architectures of edge servers have an advantage over flat architectures in serving the peak loads [23, 29]. In addition, under the three-tier MEC architectures, previous studies focused on the system construction [20–22] and maximization of the system utility [26–28]. However, it is also important how to allocate computation and communication resource energy efficiently under a three-tier MEC architecture to improve users’ QoE. In this paper, we investigate a multiuser three-tier computing model under heterogeneous networks. The SBS integrated with relatively small computation capability and MBS integrated with great computation capability jointly execute tasks. Based on this hierarchical MEC model, an energy-efficient resource allocation (EERA) scheme is proposed. In EERA, the computation and radio resources are optimized jointly for minimizing the energy consumption of all SMDs. The main contributions of this paper are summarized as follows:
(1)
Based on heterogeneous networks, we establish a three-tier computing model, including local computing, SBS computing, and MBS computing. An energy-efficient optimization problem is formulated. Workload placement strategy, transmit power, and computation capability allocation are optimized to minimize SMDs’ energy consumption under task delay constraints.
(2)
We propose an EERA scheme based on the variable substitution technique. In this scheme, the optimal workload distribution and computation capability allocation are first obtained. Then, the optimal SMDs’ transmit power is derived through the variable substitution.
(3)
Numerical simulation experiments are conducted. Simulation results are presented to validate that EERA outperforms other baseline schemes and effectively reduces the SMDs’ energy consumption.


## 1.2. Organization

The rest of this paper is organized as follows. In Section2, the three-tier computing model is presented and the energy-efficient optimization problem is formulated. In Section 3, EERA based on the variable substitution technique is proposed, where workload distribution in three-tier, computation capability allocation from SBS and SMDs’ transmit power are optimized jointly to minimize SMDs’ energy consumption. Numerical results are provided in Section 4, and conclusions are presented in Section 5.


## 2. System Model and Problem Formulation

As shown in Figure1, SBS and MBS are equipped with MEC servers and help SMDs perform tasks. SMDs, SBS, and MBS execute tasks together and establish a three-tier computing architecture. In the first tier, there is K SMDs and the set of SMDs is denoted as K=1,2,⋯,K. The processing capability of k-SMD k∈K is denoted as fk,l cycles/s. In the second tier, the SBS has the limited computation capability denoted as F cycles/s. In the third tier, we assume that the MBS has infinite computational resources and its execution latency is negligible [9, 30]. In addition, the backhaul link time delay between SBS and MBS is proportional to the transfer data size and the proportion coefficient is denoted as ϕ [24]. We assume that each user has one SMD and each SMD has one task. We only consider the case that SBS can transfer data to MBS and SMDs cannot offload tasks to MBS directly [24, 25]. Moreover, SMDs occupy orthogonal wireless channels. The k-SMD has the task denoted as AkDk,Ck,Tk. The task Ak containing Dk bits needs to be completed in time Tk. Each bit needs Ck cycles. We assume the task belongs to data-partitioned oriented tasks [6], which can be segmented arbitrarily, such as virus scan task and GZip task. The task can be executed separately in three tiers, i.e., SMDs, SBS, and MBS (Specially, in virus scan, the files can be partitioned into three parts. Then, each tier can scan a part of the total files in parallel. Finally, the results of three tiers are combined and the final result is obtained.) αk=αk,l,αk,s,αk,m0≤αk,l,αk,s,αk,m≤1 is set as the workload distribution. αk,l, αk,s, and αk,m denote the proportion of k-SMD workload, SBS workload, and MBS workload, respectively. We assume that the computation results are so small that the time delay from SBS and MBS to SMDs can be ignored [15, 30, 31].Figure 1
Multiuser task execution in three-tier computing architecture.


### 2.1. Local Computing and Transmitting Model

#### 2.1.1. Local Computing Model

The number of bits needed to be processed locally isαk,lDk and thus, it needs αk,lDkCk cycles. The latency of local computing is denoted as tk,lcomp and obtained as
(1)tk,lcomp=αk,lDkCkfk,l.We consider a low voltage task execution model and the energy consumed by one CPU cycle is denoted asε given by
(2)ε=κfk,l2,where κ is a constant related to capacitance coefficient [15]. Then, the computing energy consumed locally is written as
(3)Ek,lcomp=αk,lDkCkε=αk,lDkCkκfk,l2,where Ek,lcomp denotes the k-SMD energy consumption of local computing.


#### 2.1.2. Local Transmitting Model

The transmitting channel between SMDs and SBS is assumed as Rayleigh channels [6]. We assume that the coherence time is larger than the task deadline Tk, i.e., the channel gain is invariant during the task execution [31]. The channel gain is denoted as gk, and the task offloading rate can be obtained as
(4)rk=Blog21+pk,txgkN0,where rk, B, pk,tx, and N0 denote k-SMD’s transmit rate, channel bandwidth, transmit power, and white Gaussian noise power, respectively. The k-SMD’s transmit power cannot exceed the maximum transmit power pk,txmax. ptx denotes the SMDs’ transmit power vector, which is expressed as p1,tx,p2,tx,⋯,pK,tx. The task offloaded to MBS needs to be transferred to SBS first. Thus, the offloading time of k-SMD tk,ltrans is obtained as
(5)tk,ltrans=αk,s+αk,mDkrk.The offloading energy consumption is the product of the offloading time and transmit power as(6)Ek,ltrans=tk,ltranspk,tx=αk,s+αk,mDkrkpk,tx.


### 2.2. Computation Model

#### 2.2.1. SBS Computing Model

SBS has limited computation capabilities because of its limited volume compared with MBS.k-SMD has a priority βk from the telecom operator, which decides the portion of SBS computation capability allocated to k-SMD. The SBS computation ability of k-SMD is denoted as fk,s cycles/s. fs=f1,s,f2,s,⋯,fK,s denotes SBS computation capability allocation vector of K SMDs. And the following limitations exist:
(7)0≤fk,s≤βkF,∑k=1Kβk=1.The SBS workload fromk-SMD is αk,sDk, and the number of its computation cycles is αk,sDkCk. The time delay of SBS execution is obtained as
(8)tk,scomp=αk,sDkCkfk,s.The total delay of SBS computing is made up of offloading delay and execution delay, which is given by(9)tk,s=tk,ltrans+tk,scomp.


#### 2.2.2. MBS Computing Model

The backhaul link delaytk,mtrans is proportional to the transfer data size, i.e., the transfer delay between SBS and MBS is calculated as
(10)tk,mtrans=ϕDkαk,m.The MBS execution latency can be ignored. Therefore, the delay of MBS computingtk,m is the sum of offloading delay and backhaul link delay as
(11)tk,m=tk,ltrans+tk,mtrans.


### 2.3. Problem Formulation

Based on equations (3) and (6), the energy consumption of k-SMD Ek, which consists of computing consumption and transmitting consumption, is written as
(12)Ek=Ek,lcomp+Ek,ltrans.The task ofk-SMD is executed parallel in three-tier (local devices, SBS, and MBS), and thus, the execution delay tk is obtained as
(13)tk=maxtk,lcomp,tk,s,tk,m.The energy-efficient problem under tasks delay constraints is formulated as(14a)P1:minαk,ptx,fs∑k=1KEk,(14b)s.t.tk≤Tk,(14c)0≤fk,s≤βkF,(14d)∑k=1Kβk=1,(14e)αk,l+αk,s+αk,m=1,(14f)0≤αk,l,αk,s,αk,m≤1,(14g)0≤pk,tx≤pk,txmax,(14h)∀k∈K,where (14b) means that the delay needs to meet the demand. (14c) indicates that the SBS computation capability allocated to k-SMD cannot exceed the maximum allocation frequency. (14e) denotes that the sum workload of the local device, SBS, and MBS needs to be equal to the total task load of k-SMD.


## 2.1. Local Computing and Transmitting Model

### 2.1.1. Local Computing Model

The number of bits needed to be processed locally isαk,lDk and thus, it needs αk,lDkCk cycles. The latency of local computing is denoted as tk,lcomp and obtained as
(1)tk,lcomp=αk,lDkCkfk,l.We consider a low voltage task execution model and the energy consumed by one CPU cycle is denoted asε given by
(2)ε=κfk,l2,where κ is a constant related to capacitance coefficient [15]. Then, the computing energy consumed locally is written as
(3)Ek,lcomp=αk,lDkCkε=αk,lDkCkκfk,l2,where Ek,lcomp denotes the k-SMD energy consumption of local computing.


### 2.1.2. Local Transmitting Model

The transmitting channel between SMDs and SBS is assumed as Rayleigh channels [6]. We assume that the coherence time is larger than the task deadline Tk, i.e., the channel gain is invariant during the task execution [31]. The channel gain is denoted as gk, and the task offloading rate can be obtained as
(4)rk=Blog21+pk,txgkN0,where rk, B, pk,tx, and N0 denote k-SMD’s transmit rate, channel bandwidth, transmit power, and white Gaussian noise power, respectively. The k-SMD’s transmit power cannot exceed the maximum transmit power pk,txmax. ptx denotes the SMDs’ transmit power vector, which is expressed as p1,tx,p2,tx,⋯,pK,tx. The task offloaded to MBS needs to be transferred to SBS first. Thus, the offloading time of k-SMD tk,ltrans is obtained as
(5)tk,ltrans=αk,s+αk,mDkrk.The offloading energy consumption is the product of the offloading time and transmit power as(6)Ek,ltrans=tk,ltranspk,tx=αk,s+αk,mDkrkpk,tx.


## 2.1.1. Local Computing Model

The number of bits needed to be processed locally isαk,lDk and thus, it needs αk,lDkCk cycles. The latency of local computing is denoted as tk,lcomp and obtained as
(1)tk,lcomp=αk,lDkCkfk,l.We consider a low voltage task execution model and the energy consumed by one CPU cycle is denoted asε given by
(2)ε=κfk,l2,where κ is a constant related to capacitance coefficient [15]. Then, the computing energy consumed locally is written as
(3)Ek,lcomp=αk,lDkCkε=αk,lDkCkκfk,l2,where Ek,lcomp denotes the k-SMD energy consumption of local computing.


## 2.1.2. Local Transmitting Model

The transmitting channel between SMDs and SBS is assumed as Rayleigh channels [6]. We assume that the coherence time is larger than the task deadline Tk, i.e., the channel gain is invariant during the task execution [31]. The channel gain is denoted as gk, and the task offloading rate can be obtained as
(4)rk=Blog21+pk,txgkN0,where rk, B, pk,tx, and N0 denote k-SMD’s transmit rate, channel bandwidth, transmit power, and white Gaussian noise power, respectively. The k-SMD’s transmit power cannot exceed the maximum transmit power pk,txmax. ptx denotes the SMDs’ transmit power vector, which is expressed as p1,tx,p2,tx,⋯,pK,tx. The task offloaded to MBS needs to be transferred to SBS first. Thus, the offloading time of k-SMD tk,ltrans is obtained as
(5)tk,ltrans=αk,s+αk,mDkrk.The offloading energy consumption is the product of the offloading time and transmit power as(6)Ek,ltrans=tk,ltranspk,tx=αk,s+αk,mDkrkpk,tx.


## 2.2. Computation Model

### 2.2.1. SBS Computing Model

SBS has limited computation capabilities because of its limited volume compared with MBS.k-SMD has a priority βk from the telecom operator, which decides the portion of SBS computation capability allocated to k-SMD. The SBS computation ability of k-SMD is denoted as fk,s cycles/s. fs=f1,s,f2,s,⋯,fK,s denotes SBS computation capability allocation vector of K SMDs. And the following limitations exist:
(7)0≤fk,s≤βkF,∑k=1Kβk=1.The SBS workload fromk-SMD is αk,sDk, and the number of its computation cycles is αk,sDkCk. The time delay of SBS execution is obtained as
(8)tk,scomp=αk,sDkCkfk,s.The total delay of SBS computing is made up of offloading delay and execution delay, which is given by(9)tk,s=tk,ltrans+tk,scomp.


### 2.2.2. MBS Computing Model

The backhaul link delaytk,mtrans is proportional to the transfer data size, i.e., the transfer delay between SBS and MBS is calculated as
(10)tk,mtrans=ϕDkαk,m.The MBS execution latency can be ignored. Therefore, the delay of MBS computingtk,m is the sum of offloading delay and backhaul link delay as
(11)tk,m=tk,ltrans+tk,mtrans.


## 2.2.1. SBS Computing Model

SBS has limited computation capabilities because of its limited volume compared with MBS.k-SMD has a priority βk from the telecom operator, which decides the portion of SBS computation capability allocated to k-SMD. The SBS computation ability of k-SMD is denoted as fk,s cycles/s. fs=f1,s,f2,s,⋯,fK,s denotes SBS computation capability allocation vector of K SMDs. And the following limitations exist:
(7)0≤fk,s≤βkF,∑k=1Kβk=1.The SBS workload fromk-SMD is αk,sDk, and the number of its computation cycles is αk,sDkCk. The time delay of SBS execution is obtained as
(8)tk,scomp=αk,sDkCkfk,s.The total delay of SBS computing is made up of offloading delay and execution delay, which is given by(9)tk,s=tk,ltrans+tk,scomp.


## 2.2.2. MBS Computing Model

The backhaul link delaytk,mtrans is proportional to the transfer data size, i.e., the transfer delay between SBS and MBS is calculated as
(10)tk,mtrans=ϕDkαk,m.The MBS execution latency can be ignored. Therefore, the delay of MBS computingtk,m is the sum of offloading delay and backhaul link delay as
(11)tk,m=tk,ltrans+tk,mtrans.


## 2.3. Problem Formulation

Based on equations (3) and (6), the energy consumption of k-SMD Ek, which consists of computing consumption and transmitting consumption, is written as
(12)Ek=Ek,lcomp+Ek,ltrans.The task ofk-SMD is executed parallel in three-tier (local devices, SBS, and MBS), and thus, the execution delay tk is obtained as
(13)tk=maxtk,lcomp,tk,s,tk,m.The energy-efficient problem under tasks delay constraints is formulated as(14a)P1:minαk,ptx,fs∑k=1KEk,(14b)s.t.tk≤Tk,(14c)0≤fk,s≤βkF,(14d)∑k=1Kβk=1,(14e)αk,l+αk,s+αk,m=1,(14f)0≤αk,l,αk,s,αk,m≤1,(14g)0≤pk,tx≤pk,txmax,(14h)∀k∈K,where (14b) means that the delay needs to meet the demand. (14c) indicates that the SBS computation capability allocated to k-SMD cannot exceed the maximum allocation frequency. (14e) denotes that the sum workload of the local device, SBS, and MBS needs to be equal to the total task load of k-SMD.


## 3. Problem Solution

In this section, for gaining some engineering insights, an EERA scheme based on the variable substitution technique [6, 32] is proposed to solve problem P1. Firstly, we fix ptx and find the optimal workload distribution αk∗ and SBS computation capability allocation fs∗ by minimizing ∑k=1KEk. Then, we use αk∗ and fs∗ to find the optimal transmit power ptx∗.According to equations (3), (6), and (12), Ek can be rewritten as
(15)Ek=αk,lDkCkκfk,l2+αk,s+αk,mDkrkpk,tx.Substituting equation (14e) into (15), Ek can be written as
(16)Ek=αk,lDkCkκfk,l2−Dkpk,txrk+Dkpk,txrk.


### 3.1. Problem Decomposition

Fixing transmission powerptx, problem P1 is simplified to problem P2, where the second term of equation (16) is fixed and can be eliminated.
(17a)P2:minαk,fs∑k=1Kαk,lDkCkκfk,l2−Dkpk,txrk,(17b)s.t.tk≤Tk,(17c)0≤fk,s≤βkF,(17d)αk,l+αk,s+αk,m=1,(17e)∑k=1Kβk=1,(17f)0≤αk,l,αk,s,αk,m≤1,(17g)∀k∈K,where transmit power vector ptx is fixed. Substituting the solution of problem P2 into equation (15) and optimizing ptx by minimizing ∑k=1KEk, we formulate problem P3 as
(18a)P3:minptx∑k=1Kαk,lDkCkκfk,l2+αk,s+αk,mDkpk,txrk,(18b)s.t.tk≤Tk,(18c)0≤pk,tx≤ptxmax,(18d)∀k∈K.


### 3.2. Energy-Efficient Resource Allocation Scheme

We define the transmission energy consumption per bit asvk, which is obtained as
(19)vk=pk,txrk.Lemma 1.
vk increases monotonically with the increase of pk,tx.Proof.
See AppendixA.
Defineek as
(20)ek=αk,lDkCkκfk,l2−Dkpk,txrk.Lemma 2.
Based on Lemma1, ek changes with vk as follows:
(1)vk>κCkfk,l2, ek decreases monotonically with the increase of αk,l.
2vk<κCkfk,l2, ek increases monotonically with the increase of αk,l.
3vk=κCkfk,l2, ek is independent of αk,l.Proof.
The derivative ofek is dek/dαk,l=DkCkκfk,l2−Dkpk,tx/rk. When vk>κCkfk,l2, dek/dαk,l<0 and ek decreases monotonically with the increase of αk,l. The second case and the third case can be proved by the same way as the first case.Based on Lemma1 and Lemma 2, we can judge whether problem P1 has a solution or not and get Lemma 3.Lemma 3.
ProblemP1 is feasible.Proof.
See AppendixB.Remark 4.
Whenvk>κCkfk,l2, i.e., the energy consumed per bit by offloading is more than the energy consumed per bit by local execution. More bits will be processed in the local device to save energy. That is why ek decreases monotonically with the increase of αk,l. In the second case of Lemma 2, vk<κCkfk,l2, i.e., the energy consumed per bit by offloading is less than the energy consumed per bit by local execution. More bits will be processed by offloading to save energy. That is why ek increases monotonically with the increase of αk,l.Remark 5.
According to Lemma1, vk increases monotonically with the increase of pk,tx. From equation (4), a larger rk is due to a larger pk,tx and a larger pk,tx induces a larger rk. Wherefore, the larger is rk, the larger is vk. According to equation (15), when vk becomes larger, Ek becomes larger. Thus, Ek increases with the increase of rk, i.e., the energy consumption of SMDs increases with the increase of rk. In other words, the SMD will consume more energy when having a higher offloading rate.Substituting equation (13) into inequality (14b), we get
(21)tk,lcomp≤Tk,tk,s≤Tk,tk,m≤Tk.In order to simplify problemP2, tk,s and tk,m are compared and then, problem P2 becomes problem P2.1 and problem P2.2.Whentk,s≥tk,m, i.e., the delay of SBS computing is larger than MBS computing, problem P2 becomes problem P2.1, which is written as
(22a)P2.1:minαk,fs∑k=1Kαk,lDkCkκfk,l2−Dkpk,txrk,(22b)s.t.tk,lcomp≤Tk,(22c)tk,s≤Tk,(22d)tk,s≥tk,m,(22e)17c−17g.Whentk,s<tk,m, i.e., the delay of MBS computing is larger than that in SBS computing, problem P2 becomes problem P2.2, which can be written as
(23a)P2.2:minαk,fs∑k=1Kαk,lDkCkκfk,l2−Dkpk,txrk,(23b)s.t.tk,lcomp≤Tk,(23c)tk,m≤Tk,(23d)tk,s<tk,m,(23e)17c−17g.According to Lemma2, three cases are dealt with, respectively, to solve problem P1.(1)vk>κCkfk,l2: when the energy consumed per bit by offloading is more than the energy consumed per bit by local execution, the following derivations exist.Lemma 6.
Both problemsP2.1 and P2.2 have the same optimal local task load αk,l∗ as
(24)αk,l∗=fk,lTkDkCk.Proof.
From inequalities (22b) and (23b), αk,l≤fk,lTk/DkCk is obtained. In the light of the first case of Lemma 2, ekdecreases monotonously with the increase of αk,l. Wherefore, we take αk,l∗=fk,lTk/DkCk.Remark 7.
According to equation (24), the local workload is related to local computation ability and the task delay constraint. Larger local computation ability brings a larger local workload. In order to save energy, SMDs will process as many bits as possible locally if the processing latency meets the task delay constraint. Looser delay constraint brings the SMD a larger local workload. Looser delay constraint means that the local device has more time to execute the task and thus process more bits locally to save energy.Lemma 8.
Defineαk,s∗, αk,m∗, and fk,s∗ as the optimal SBS workload, MBS workload, and computation ability allocated from SBS, respectively. When vk>κCkfk,l2, both problem P2.1 and problem P2.2 have
(25)αk,s∗=ϕfk,s∗Ckαk,m∗,(26)fk,s∗=βkF.Proof.
See AppendixC.Remark 9.
According to equation (25), αk,s∗ is related to backhaul link delay coefficient ϕ and the computation ability fk,s∗ allocated from SBS. When much SBS computation ability is allocated to k-SMD or backhaul link delay is large, the SBS workload will be large. In other words, the task will be executed prior in SBS unless MBS execution costs less time.Whenvk>κCkfk,l2 , based on Lemma 6 and Lemma 8, the solution of problem P2 can be obtained as Theorem 10.Theorem 10.
The optimal workload distributionαk∗ and the optimal allocation of SBS computation ability fs∗ can be obtained as
(27)fk,s∗=βkF,(28)αk,l∗=fk,lTkDkCk,αk,s∗=ϕfk,s∗DkCk−fk,lTkCkDkCk+ϕfk,s∗αk,m∗=DkCk−fk,lTkDkCk+ϕfk,s∗.,Proof.
Substituting equations (24)–(26) into equation (17d), the optimal allocation of SBS computation ability and the optimal workload distribution can be obtained.In the light of Remark5, the optimal transmission rate rk∗ can be calculated by Lemma 11 and then, problem P3 can be solved.Lemma 11.
ProblemP2.1 and problem P2.2 have the same optimal transmission rate rk∗ as
(29)rk∗=1−αk,l∗DkTk−αk,s∗DkCk/fk,s∗.Proof.
According to inequalities (C.3) and (C.9), we choose the lower boundary of rkas rk∗ for saving energy. Considering Lemma 8, rk∗ of problems P2.1 and P2.2 are same and equation (29) is obtained.Then, substituting equation (29) into equation (4), we attain the optimal solution of problem P3 by Theorem 12.Theorem 12.
The optimal transmission powerpk,tx∗ is given by
(30)pk,tx∗=N0gk21−αk,l∗DkBTk−αk,s∗DkCk/fk,s∗−1.Remark 13.
As can be seen from equation (30), smaller αk,l∗ and larger αk,s∗ induce larger k-SMD’s transmission power pk,tx∗. When the proportion of the task executed locally is small, the offloading rate should be large enough to meet the task delay constraint, which results in large transmission power. Similarly, larger αk,s∗ means more bits will be processed in SBS and means a larger offloading rate, which accounts for larger transmit power.(2)vk<κCkfk,l2: when the energy consumed by offloading per bit is less than the energy consumed by local execution per bit, offloading will be prior to local execution for saving energy, i.e., smaller αk,l will be better for saving energy.Considering problemP2.1, we have the optimal local workload as Lemma 14.Lemma 14.
The optimalαk,l of problem P2.1 can be given by
(31)αk,l=1−TkrkDk+αk,sCkrkfk,s.Proof.
We haveαk,l≥1−Tkrk/Dk+αk,sCkrk/fk,s by substituting equations (5), (8), and (9) into inequality (22c). Smaller αk,l leads to less energy consumption of k-SMD. Therefore, we take αk,l=1−Tkrk/Dk+αk,sCkrk/fk,s.Similarly to Lemma14, we obtain the optimal local workload of problem P2.2 as Lemma 15 using inequality (23c).Lemma 15.
The optimalαk,l of problem P2.2 can be calculated as
(32)αk,l=1−TkrkDk+ϕαk,mrk.Lemma 16.
Whenvk<κCkfk,l2, the optimal MBS workload αk,m∗ and SBS workload αk,s∗ have
(33)αk,m∗=Ckϕfk,sαk,s∗.Proof.
Considering problemP2.1, we obtain tk,s≥tk,m, where αk,s≥ϕfk,s/Ckαk,m is attained according to equations (9) and (11). From equation (31), smaller αk,s/fk,s will be better for saving energy. Thus, we take αk,s=ϕfk,s/Ckαk,m. Considering problem P2.2, we get αk,m>Ck/ϕfk,sαk,s from tk,s<tk,m.According to equation (32), smaller αk,m brings smaller αk,l and saves more energy. In addition, αk,m can approach Ck/ϕfk,sαk,s as much as possible because of the continuity of αk,m. Hence, we obtain αk,m∗=Ck/ϕfk,sαk,s∗.Remark 17.
There always existsαk,s∗=ϕfk,s/Ckαk,m∗ whether vk is larger than κCkfk,l2 or not. It indicates that the energy consumed by offloading per bit has nothing to do with the relation between αk,s∗ and αk,m∗. The relation depends on the computation ability allocated from SBS and transfer delay of backhaul link, i.e, the distribution of workload between SBS and MBS is decided jointly by the computation ability allocated from SBS and MBS time cost.Remark 18.
Based on Lemma14, Lemma 15, and Lemma 16, we easily find that problem P2.1 and problem P2.2 have the same optimal αk,l. In other words, the optimal workload of local devices αk,l∗ is independent of the workload distribution between SBS and MBS.Remark 19.
In the second case of Lemma2, problem P2.1 and problem P2.2 have the same optimal local workload αk,l∗ and same relation between αk,s∗ and αk,m∗. Therefore, according to equation (17d), problem P2.1 and problem P2.2 have the same optimal solution about αk∗.Based on Remark19, the solution of problem P2 can be obtained by Theorem 20.Theorem 20.
Whenvk<κCkfk,l2, the optimal computation ability allocation from SBS fk,s∗ and the optimal workload distribution αk∗ among SMDs, SBS, and MBS can be attained as
(34)fk,s∗=βkF,(35)αk,l∗=1−TkrkDk+CkTkϕrk2DkϕCkrk+Ck+ϕfk,s∗,αk,s∗=Tkrkϕfk,s∗DkϕCkrk+Ck+ϕfk,s∗,αk,m∗=TkrkCkDkϕCkrk+Ck+ϕfk,s∗.Proof.
Substituting equations (31) and (33) into equation (17d), the optimal workload distribution αk∗ can be obtained. In addition, from equation (31), αk,l decreases with the increase of fk,s. A larger fk,s brings a smaller αk,l and saves more energy. Thus, we take fk,s∗=βkF.Considering problemP3, we substitute equations (34) and (35) into Ek and get the optimal transmit power pk,tx∗ as Theorem 21.Theorem 21.
Whenvk<κCkfk,l2, the optimal transmission power pk,tx∗ is
(36)pk,tx∗=minp,vk−1κCkfk,l2,where dQ/dpk,txpk,tx=p=0 and vk−1 denotes the inverse function of vkQ is defined as
(37)Q=Tkpk,tx−κCkfk,l2TkrkϕCkrk+Ck+ϕfk,s.Proof.
See AppendixD.It is difficult to solvevk−1 and dQ/dpk,txpk,tx=p=0. Hence, some tools are used to get the optimal transmission power pk,tx∗. In the first step, we use MATLAB to get the maximum transmission power pk,txend from pk,txend=vk−1κCkfk,l2. In the second step, we use the binary search technique to search the optimal transmit power pk,tx∗ between 0 and pk,txend for minimizing Q. The variables e, d, and pk,txmid denote the search error, search interval, and interval midpoint, respectively. The search is not stopped until d<e. The detailed search process is summarized in Algorithm 1.(3)vk=κCkfk,l2: when vk=κCkfk,l2, i.e., ek=0, αk,l cannot change ek. In this case, the energy consumed per bit by local execution equals the energy consumed per bit by offloading. Offloading cannot reduce energy consumption of task execution. We choose to execute tasks in local devices or the entire offloading to minimize execution latency and get the following Theorem 22.Algorithm 1: Binary search for pk,tx∗.
Input: error e, start point pk,txstart, end point pk,txend
Output:pk,tx∗
Initialization:
pk,txstart=0
pk,txend=vk−1κCkfk,l2
pk,txmid=pk,txstart+pk,txend2
d=pk,txend−pk,txstart
1:while d>e do
2:if Qpk,txmid−e/2≥Qpk,txmid+e/2 then
3:pk,txstart=pk,txmid
4:else
5:pk,txend=pk,txmid
6:d=pk,txend−pk,txstart
7:pk,txmid=pk,txstart+pk,txend2
8:return pk,txmidTheorem 22.
(1) Whentk,lall≤tk,off∗, the task will be executed entirely by the local device and have
(38)fk,s∗=0,pk,tx∗=0,αk,l∗=1,αk,s∗=0,αk,m∗=0.
(2) Whentk,lall>tk,off∗, the task will be executed entirely by offloading and have
(39)fk,s∗=βkF,pk,tx∗=vk−1κCkfk,l2,αk,l∗=0,αk,s∗=ϕfk,s∗Ck+ϕfk,s∗,αk,m∗=CkCk+ϕfk,s∗.
In (1) and (2), the latency of local execution entirely is denoted astk,lall and tk,lall=DkCk/fk,l. The minimum offloading latency is denoted as tk,off∗ and tk,off∗=Dk/Blog21+vk−1κCkfk,l2gk/N0+ϕDkCk/Ck+ϕfk,s∗.Proof.
See AppendixE.By now, the optimal solution of problemP1 is given by the theorems and the procedure is described in Algorithm 2.


### 3.3. Analysis of Special Cases

From the first four theorems, we not only consider energy minimization but also consider the delay constraint. That is why we still allocate resources when we know the case with the least energy consumption.Algorithm 2: The Main Process of the Energy-Efficient Resource Allocation Scheme
Step 1: According to Theorem 10 and Theorem 12, calculate
αk∗, fs∗ and ptx∗.
Step 2: Based on equation (19), compute vk∗ by substituting
the results of Step 1.
Step 3:
if vk∗<κCkfk,l2 then
recomputeαk∗ fk,s∗ and pk,tx∗ according to Theorem 20
and Theorem21.
else if vk∗=κCkfk,l2 then
recomputeαk∗ fk,s∗ and pk,tx∗ according to Theorem 22.In Theorem22, we only consider the latency. In this case, energy consumed per bit by offloading equals the energy consumed per bit by local execution, i.e., the offloading will not reduce energy consumption of the task execution. We cannot use the offloading to reduce SMDs’ energy consumption. However, we can choose the solution with the least delay to try to improve users’ QoE. Wherefore, we choose to execute the task either locally or remotely according to the latencies of the task execution in the local device and offloading.


## 3.1. Problem Decomposition

Fixing transmission powerptx, problem P1 is simplified to problem P2, where the second term of equation (16) is fixed and can be eliminated.
(17a)P2:minαk,fs∑k=1Kαk,lDkCkκfk,l2−Dkpk,txrk,(17b)s.t.tk≤Tk,(17c)0≤fk,s≤βkF,(17d)αk,l+αk,s+αk,m=1,(17e)∑k=1Kβk=1,(17f)0≤αk,l,αk,s,αk,m≤1,(17g)∀k∈K,where transmit power vector ptx is fixed. Substituting the solution of problem P2 into equation (15) and optimizing ptx by minimizing ∑k=1KEk, we formulate problem P3 as
(18a)P3:minptx∑k=1Kαk,lDkCkκfk,l2+αk,s+αk,mDkpk,txrk,(18b)s.t.tk≤Tk,(18c)0≤pk,tx≤ptxmax,(18d)∀k∈K.


## 3.2. Energy-Efficient Resource Allocation Scheme

We define the transmission energy consumption per bit asvk, which is obtained as
(19)vk=pk,txrk.Lemma 1.
vk increases monotonically with the increase of pk,tx.Proof.
See AppendixA.
Defineek as
(20)ek=αk,lDkCkκfk,l2−Dkpk,txrk.Lemma 2.
Based on Lemma1, ek changes with vk as follows:
(1)vk>κCkfk,l2, ek decreases monotonically with the increase of αk,l.
2vk<κCkfk,l2, ek increases monotonically with the increase of αk,l.
3vk=κCkfk,l2, ek is independent of αk,l.Proof.
The derivative ofek is dek/dαk,l=DkCkκfk,l2−Dkpk,tx/rk. When vk>κCkfk,l2, dek/dαk,l<0 and ek decreases monotonically with the increase of αk,l. The second case and the third case can be proved by the same way as the first case.Based on Lemma1 and Lemma 2, we can judge whether problem P1 has a solution or not and get Lemma 3.Lemma 3.
ProblemP1 is feasible.Proof.
See AppendixB.Remark 4.
Whenvk>κCkfk,l2, i.e., the energy consumed per bit by offloading is more than the energy consumed per bit by local execution. More bits will be processed in the local device to save energy. That is why ek decreases monotonically with the increase of αk,l. In the second case of Lemma 2, vk<κCkfk,l2, i.e., the energy consumed per bit by offloading is less than the energy consumed per bit by local execution. More bits will be processed by offloading to save energy. That is why ek increases monotonically with the increase of αk,l.Remark 5.
According to Lemma1, vk increases monotonically with the increase of pk,tx. From equation (4), a larger rk is due to a larger pk,tx and a larger pk,tx induces a larger rk. Wherefore, the larger is rk, the larger is vk. According to equation (15), when vk becomes larger, Ek becomes larger. Thus, Ek increases with the increase of rk, i.e., the energy consumption of SMDs increases with the increase of rk. In other words, the SMD will consume more energy when having a higher offloading rate.Substituting equation (13) into inequality (14b), we get
(21)tk,lcomp≤Tk,tk,s≤Tk,tk,m≤Tk.In order to simplify problemP2, tk,s and tk,m are compared and then, problem P2 becomes problem P2.1 and problem P2.2.Whentk,s≥tk,m, i.e., the delay of SBS computing is larger than MBS computing, problem P2 becomes problem P2.1, which is written as
(22a)P2.1:minαk,fs∑k=1Kαk,lDkCkκfk,l2−Dkpk,txrk,(22b)s.t.tk,lcomp≤Tk,(22c)tk,s≤Tk,(22d)tk,s≥tk,m,(22e)17c−17g.Whentk,s<tk,m, i.e., the delay of MBS computing is larger than that in SBS computing, problem P2 becomes problem P2.2, which can be written as
(23a)P2.2:minαk,fs∑k=1Kαk,lDkCkκfk,l2−Dkpk,txrk,(23b)s.t.tk,lcomp≤Tk,(23c)tk,m≤Tk,(23d)tk,s<tk,m,(23e)17c−17g.According to Lemma2, three cases are dealt with, respectively, to solve problem P1.(1)vk>κCkfk,l2: when the energy consumed per bit by offloading is more than the energy consumed per bit by local execution, the following derivations exist.Lemma 6.
Both problemsP2.1 and P2.2 have the same optimal local task load αk,l∗ as
(24)αk,l∗=fk,lTkDkCk.Proof.
From inequalities (22b) and (23b), αk,l≤fk,lTk/DkCk is obtained. In the light of the first case of Lemma 2, ekdecreases monotonously with the increase of αk,l. Wherefore, we take αk,l∗=fk,lTk/DkCk.Remark 7.
According to equation (24), the local workload is related to local computation ability and the task delay constraint. Larger local computation ability brings a larger local workload. In order to save energy, SMDs will process as many bits as possible locally if the processing latency meets the task delay constraint. Looser delay constraint brings the SMD a larger local workload. Looser delay constraint means that the local device has more time to execute the task and thus process more bits locally to save energy.Lemma 8.
Defineαk,s∗, αk,m∗, and fk,s∗ as the optimal SBS workload, MBS workload, and computation ability allocated from SBS, respectively. When vk>κCkfk,l2, both problem P2.1 and problem P2.2 have
(25)αk,s∗=ϕfk,s∗Ckαk,m∗,(26)fk,s∗=βkF.Proof.
See AppendixC.Remark 9.
According to equation (25), αk,s∗ is related to backhaul link delay coefficient ϕ and the computation ability fk,s∗ allocated from SBS. When much SBS computation ability is allocated to k-SMD or backhaul link delay is large, the SBS workload will be large. In other words, the task will be executed prior in SBS unless MBS execution costs less time.Whenvk>κCkfk,l2 , based on Lemma 6 and Lemma 8, the solution of problem P2 can be obtained as Theorem 10.Theorem 10.
The optimal workload distributionαk∗ and the optimal allocation of SBS computation ability fs∗ can be obtained as
(27)fk,s∗=βkF,(28)αk,l∗=fk,lTkDkCk,αk,s∗=ϕfk,s∗DkCk−fk,lTkCkDkCk+ϕfk,s∗αk,m∗=DkCk−fk,lTkDkCk+ϕfk,s∗.,Proof.
Substituting equations (24)–(26) into equation (17d), the optimal allocation of SBS computation ability and the optimal workload distribution can be obtained.In the light of Remark5, the optimal transmission rate rk∗ can be calculated by Lemma 11 and then, problem P3 can be solved.Lemma 11.
ProblemP2.1 and problem P2.2 have the same optimal transmission rate rk∗ as
(29)rk∗=1−αk,l∗DkTk−αk,s∗DkCk/fk,s∗.Proof.
According to inequalities (C.3) and (C.9), we choose the lower boundary of rkas rk∗ for saving energy. Considering Lemma 8, rk∗ of problems P2.1 and P2.2 are same and equation (29) is obtained.Then, substituting equation (29) into equation (4), we attain the optimal solution of problem P3 by Theorem 12.Theorem 12.
The optimal transmission powerpk,tx∗ is given by
(30)pk,tx∗=N0gk21−αk,l∗DkBTk−αk,s∗DkCk/fk,s∗−1.Remark 13.
As can be seen from equation (30), smaller αk,l∗ and larger αk,s∗ induce larger k-SMD’s transmission power pk,tx∗. When the proportion of the task executed locally is small, the offloading rate should be large enough to meet the task delay constraint, which results in large transmission power. Similarly, larger αk,s∗ means more bits will be processed in SBS and means a larger offloading rate, which accounts for larger transmit power.(2)vk<κCkfk,l2: when the energy consumed by offloading per bit is less than the energy consumed by local execution per bit, offloading will be prior to local execution for saving energy, i.e., smaller αk,l will be better for saving energy.Considering problemP2.1, we have the optimal local workload as Lemma 14.Lemma 14.
The optimalαk,l of problem P2.1 can be given by
(31)αk,l=1−TkrkDk+αk,sCkrkfk,s.Proof.
We haveαk,l≥1−Tkrk/Dk+αk,sCkrk/fk,s by substituting equations (5), (8), and (9) into inequality (22c). Smaller αk,l leads to less energy consumption of k-SMD. Therefore, we take αk,l=1−Tkrk/Dk+αk,sCkrk/fk,s.Similarly to Lemma14, we obtain the optimal local workload of problem P2.2 as Lemma 15 using inequality (23c).Lemma 15.
The optimalαk,l of problem P2.2 can be calculated as
(32)αk,l=1−TkrkDk+ϕαk,mrk.Lemma 16.
Whenvk<κCkfk,l2, the optimal MBS workload αk,m∗ and SBS workload αk,s∗ have
(33)αk,m∗=Ckϕfk,sαk,s∗.Proof.
Considering problemP2.1, we obtain tk,s≥tk,m, where αk,s≥ϕfk,s/Ckαk,m is attained according to equations (9) and (11). From equation (31), smaller αk,s/fk,s will be better for saving energy. Thus, we take αk,s=ϕfk,s/Ckαk,m. Considering problem P2.2, we get αk,m>Ck/ϕfk,sαk,s from tk,s<tk,m.According to equation (32), smaller αk,m brings smaller αk,l and saves more energy. In addition, αk,m can approach Ck/ϕfk,sαk,s as much as possible because of the continuity of αk,m. Hence, we obtain αk,m∗=Ck/ϕfk,sαk,s∗.Remark 17.
There always existsαk,s∗=ϕfk,s/Ckαk,m∗ whether vk is larger than κCkfk,l2 or not. It indicates that the energy consumed by offloading per bit has nothing to do with the relation between αk,s∗ and αk,m∗. The relation depends on the computation ability allocated from SBS and transfer delay of backhaul link, i.e, the distribution of workload between SBS and MBS is decided jointly by the computation ability allocated from SBS and MBS time cost.Remark 18.
Based on Lemma14, Lemma 15, and Lemma 16, we easily find that problem P2.1 and problem P2.2 have the same optimal αk,l. In other words, the optimal workload of local devices αk,l∗ is independent of the workload distribution between SBS and MBS.Remark 19.
In the second case of Lemma2, problem P2.1 and problem P2.2 have the same optimal local workload αk,l∗ and same relation between αk,s∗ and αk,m∗. Therefore, according to equation (17d), problem P2.1 and problem P2.2 have the same optimal solution about αk∗.Based on Remark19, the solution of problem P2 can be obtained by Theorem 20.Theorem 20.
Whenvk<κCkfk,l2, the optimal computation ability allocation from SBS fk,s∗ and the optimal workload distribution αk∗ among SMDs, SBS, and MBS can be attained as
(34)fk,s∗=βkF,(35)αk,l∗=1−TkrkDk+CkTkϕrk2DkϕCkrk+Ck+ϕfk,s∗,αk,s∗=Tkrkϕfk,s∗DkϕCkrk+Ck+ϕfk,s∗,αk,m∗=TkrkCkDkϕCkrk+Ck+ϕfk,s∗.Proof.
Substituting equations (31) and (33) into equation (17d), the optimal workload distribution αk∗ can be obtained. In addition, from equation (31), αk,l decreases with the increase of fk,s. A larger fk,s brings a smaller αk,l and saves more energy. Thus, we take fk,s∗=βkF.Considering problemP3, we substitute equations (34) and (35) into Ek and get the optimal transmit power pk,tx∗ as Theorem 21.Theorem 21.
Whenvk<κCkfk,l2, the optimal transmission power pk,tx∗ is
(36)pk,tx∗=minp,vk−1κCkfk,l2,where dQ/dpk,txpk,tx=p=0 and vk−1 denotes the inverse function of vkQ is defined as
(37)Q=Tkpk,tx−κCkfk,l2TkrkϕCkrk+Ck+ϕfk,s.Proof.
See AppendixD.It is difficult to solvevk−1 and dQ/dpk,txpk,tx=p=0. Hence, some tools are used to get the optimal transmission power pk,tx∗. In the first step, we use MATLAB to get the maximum transmission power pk,txend from pk,txend=vk−1κCkfk,l2. In the second step, we use the binary search technique to search the optimal transmit power pk,tx∗ between 0 and pk,txend for minimizing Q. The variables e, d, and pk,txmid denote the search error, search interval, and interval midpoint, respectively. The search is not stopped until d<e. The detailed search process is summarized in Algorithm 1.(3)vk=κCkfk,l2: when vk=κCkfk,l2, i.e., ek=0, αk,l cannot change ek. In this case, the energy consumed per bit by local execution equals the energy consumed per bit by offloading. Offloading cannot reduce energy consumption of task execution. We choose to execute tasks in local devices or the entire offloading to minimize execution latency and get the following Theorem 22.Algorithm 1: Binary search for pk,tx∗.
Input: error e, start point pk,txstart, end point pk,txend
Output:pk,tx∗
Initialization:
pk,txstart=0
pk,txend=vk−1κCkfk,l2
pk,txmid=pk,txstart+pk,txend2
d=pk,txend−pk,txstart
1:while d>e do
2:if Qpk,txmid−e/2≥Qpk,txmid+e/2 then
3:pk,txstart=pk,txmid
4:else
5:pk,txend=pk,txmid
6:d=pk,txend−pk,txstart
7:pk,txmid=pk,txstart+pk,txend2
8:return pk,txmidTheorem 22.
(1) Whentk,lall≤tk,off∗, the task will be executed entirely by the local device and have
(38)fk,s∗=0,pk,tx∗=0,αk,l∗=1,αk,s∗=0,αk,m∗=0.
(2) Whentk,lall>tk,off∗, the task will be executed entirely by offloading and have
(39)fk,s∗=βkF,pk,tx∗=vk−1κCkfk,l2,αk,l∗=0,αk,s∗=ϕfk,s∗Ck+ϕfk,s∗,αk,m∗=CkCk+ϕfk,s∗.
In (1) and (2), the latency of local execution entirely is denoted astk,lall and tk,lall=DkCk/fk,l. The minimum offloading latency is denoted as tk,off∗ and tk,off∗=Dk/Blog21+vk−1κCkfk,l2gk/N0+ϕDkCk/Ck+ϕfk,s∗.Proof.
See AppendixE.By now, the optimal solution of problemP1 is given by the theorems and the procedure is described in Algorithm 2.


## 3.3. Analysis of Special Cases

From the first four theorems, we not only consider energy minimization but also consider the delay constraint. That is why we still allocate resources when we know the case with the least energy consumption.Algorithm 2: The Main Process of the Energy-Efficient Resource Allocation Scheme
Step 1: According to Theorem 10 and Theorem 12, calculate
αk∗, fs∗ and ptx∗.
Step 2: Based on equation (19), compute vk∗ by substituting
the results of Step 1.
Step 3:
if vk∗<κCkfk,l2 then
recomputeαk∗ fk,s∗ and pk,tx∗ according to Theorem 20
and Theorem21.
else if vk∗=κCkfk,l2 then
recomputeαk∗ fk,s∗ and pk,tx∗ according to Theorem 22.In Theorem22, we only consider the latency. In this case, energy consumed per bit by offloading equals the energy consumed per bit by local execution, i.e., the offloading will not reduce energy consumption of the task execution. We cannot use the offloading to reduce SMDs’ energy consumption. However, we can choose the solution with the least delay to try to improve users’ QoE. Wherefore, we choose to execute the task either locally or remotely according to the latencies of the task execution in the local device and offloading.


## 4. Numerical Results

In this section, numerical results are given to evaluate the performances of the proposed EERA scheme, as compared to the following baseline schemes.(i)
Local Computing Only: all SMDs perform their own tasks by only local computing
(ii)
Full Offloading: all SMDs accomplish their own tasks by fully offloading
(iii)
Computing without MBS: the tasks are performed only by local devices and SBS server. Resource allocation for minimizing all SMDs’ energy consumption only takes place on local devices and the SBS serverSome parameters are set as follows unless stated otherwise. The tasks models of all SMDs are set to be identical, i.e.,Dk=10kbits [15], Ck=1000 cycles/bit [15], and Tk=2ms k∈K [9]. The local computation capability fk,l equals 5×108 cycles/s [33]. The energy coefficient of local computation κ is 10−28 [15]. The maximum transmission power pkmax is 0.1 watts [6]. The computation capability of the SBS server is 8×109 cycles/s [34]. The backhaul time delay coefficient ϕ is set to be 1.25×10−8 sec/bit [24]. We consider a Rayleigh fading channel model, and the channel gain gk=λg¯k. λ is an independent exponential random variable of unit mean. g¯k follows the free-space path loss model as
(40)g¯k=Ad3×1084πfcdkde,where Ad=4.11 denotes the antenna gain, fc=915MHz denotes the carrier frequency, dk=18m denotes the distance from the SBS to k-SMD [6], and de=2.8 denotes the path loss exponent. The channel bandwidth B is 2 MHz [31].


### 4.1. Performances of EERA

In this subsection, we analyze the performances of EERA compared with local-computing-only, full-offloading, and computing-without-MBS. Figures2–5 present the energy consumption of SMDs under different conditions. It is shown that the proposed EERA achieves the lowest energy consumption among those four methods.Figure 2
Energy consumption versus user number.Figure 3
Energy consumption versus computation task size.Figure 4
Energy consumption versus the channel bandwidth.Figure 5
Energy consumption versus the distance from the SBS to users.Figure2 plots the sum energy consumption of all SMDs versus the user number K. It is shown that the energy consumption by all the schemes increases as the user number grows. Besides, the energy consumption of computing-without-MBS is close to full-offloading when the user number is less than 15 while close to local-computing-only when the user number is greater than 15. The reason is that the computation resource that each user obtains from the SBS server becomes less as the user number increases. And SMDs process more bits locally for meeting the tasks’ deadline. It is also observed that EERA outperforms the other schemes. This is because EERA has more computation capacity thanks to the MBS server. And lower execution latency gives more time to offload computation bits.Figure3 depicts the sum energy consumption of all SMDs versus the computation tasks size D. It is shown that the energy consumption by the four schemes rises with the computation task size growth. When the computation task size is small, the energy consumption of computing-without-MBS is less than that of local-computing-only and more than that of full-offloading. When the computation task size is large, computing-without-MBS is close to full offloading. It indicates that the number of local computation bits decreases with the computation task size increase under the task latency constraints. The energy consumption of EERA is the least among these methods. In addition, the gap between EERA and full-offloading is gradually widening when the computation task size is less than 9.45 kbits and narrowing when the computation task size is greater than 9.45 kbits. The reason is that offloading consumes less energy and EERA processes more bits by offloading when the computation task size is small. To meet the task latency demand, more bits are offloaded when the computation task size grows.Figure4 shows the sum energy consumption versus the channel bandwidth B. As we can see, with the increase of the channel bandwidth, the energy consumption by local-computing-only remains invariant while other schemes decrease. The reason is that local-computing-only has nothing to do with offloading. However, other schemes can reduce transmit power owing to a bigger bandwidth under time delay constraints. The gap between full-offloading and computing-without-MBS is widening as the channel bandwidth grows. Full-offloading has more computation capability than computing-without-MBS and has lower execution latency, which leaves more time for offloading and lowers the transmit power. EERA is gradually close to full-offloading as the channel bandwidth rises. It indicates that EERA processes more bits by offloading when the channel bandwidth is widening.Figure5 shows the sum energy consumption versus distance from the SBS to users. It is observed that these schemes except local-computing-only rise when the distance becomes larger. Similar to Figure 4, local-computing-only has nothing to do with the communication distance. Longer distance leads to a larger path loss, which needs high transmit power to meet the time delay constraint. It is shown that the energy consumption by EERA is less than computing-without-MBS. That is because the existence of the MBS server lowers the execution latency and the transmit power. Moreover, the gap between EERA and full-offloading is widening. It illustrates that the offloading bit number becomes less owing to the longer communication distance.


### 4.2. Impacts of Backhaul Time Delay Coefficientϕ

In this subsection, we analyze the energy consumption with respect to the backhaul time delay coefficient in different conditions, e.g., the varying latency constraint, the varying user number, and the varying computation task size.Figure6 plots the sum energy consumption of all SMDs in different backhaul time delay coefficients ϕ versus the execution latency constraints. It is shown that the energy consumption decreases as the execution latency increases. The reason is that more time will be used to offload. And the low transmit power is allowed when the execution latency constraints relax.Figure 6
Energy consumption versus the execution latency.Figure7(a) shows the energy consumption versus user number under different ϕ. Figure 7(b) depicts the energy consumption versus computation task size given different ϕ. Combined with Figure 6, it is observed that a larger backhaul time delay coefficient results in larger energy consumption with the rise of the execution latency, user number, and computation task size. The reason is that a larger backhaul time delay coefficient increases the execution time and reduces the offloading time. Thus, transmit power increases for satisfying the task latency constraints.Figure 7
Effect of the backhaul time delay coefficientϕ on energy consumption.
(a)
Energy consumption versus user number
(b)
Energy consumption versus computation tasks size


## 4.1. Performances of EERA

In this subsection, we analyze the performances of EERA compared with local-computing-only, full-offloading, and computing-without-MBS. Figures2–5 present the energy consumption of SMDs under different conditions. It is shown that the proposed EERA achieves the lowest energy consumption among those four methods.Figure 2
Energy consumption versus user number.Figure 3
Energy consumption versus computation task size.Figure 4
Energy consumption versus the channel bandwidth.Figure 5
Energy consumption versus the distance from the SBS to users.Figure2 plots the sum energy consumption of all SMDs versus the user number K. It is shown that the energy consumption by all the schemes increases as the user number grows. Besides, the energy consumption of computing-without-MBS is close to full-offloading when the user number is less than 15 while close to local-computing-only when the user number is greater than 15. The reason is that the computation resource that each user obtains from the SBS server becomes less as the user number increases. And SMDs process more bits locally for meeting the tasks’ deadline. It is also observed that EERA outperforms the other schemes. This is because EERA has more computation capacity thanks to the MBS server. And lower execution latency gives more time to offload computation bits.Figure3 depicts the sum energy consumption of all SMDs versus the computation tasks size D. It is shown that the energy consumption by the four schemes rises with the computation task size growth. When the computation task size is small, the energy consumption of computing-without-MBS is less than that of local-computing-only and more than that of full-offloading. When the computation task size is large, computing-without-MBS is close to full offloading. It indicates that the number of local computation bits decreases with the computation task size increase under the task latency constraints. The energy consumption of EERA is the least among these methods. In addition, the gap between EERA and full-offloading is gradually widening when the computation task size is less than 9.45 kbits and narrowing when the computation task size is greater than 9.45 kbits. The reason is that offloading consumes less energy and EERA processes more bits by offloading when the computation task size is small. To meet the task latency demand, more bits are offloaded when the computation task size grows.Figure4 shows the sum energy consumption versus the channel bandwidth B. As we can see, with the increase of the channel bandwidth, the energy consumption by local-computing-only remains invariant while other schemes decrease. The reason is that local-computing-only has nothing to do with offloading. However, other schemes can reduce transmit power owing to a bigger bandwidth under time delay constraints. The gap between full-offloading and computing-without-MBS is widening as the channel bandwidth grows. Full-offloading has more computation capability than computing-without-MBS and has lower execution latency, which leaves more time for offloading and lowers the transmit power. EERA is gradually close to full-offloading as the channel bandwidth rises. It indicates that EERA processes more bits by offloading when the channel bandwidth is widening.Figure5 shows the sum energy consumption versus distance from the SBS to users. It is observed that these schemes except local-computing-only rise when the distance becomes larger. Similar to Figure 4, local-computing-only has nothing to do with the communication distance. Longer distance leads to a larger path loss, which needs high transmit power to meet the time delay constraint. It is shown that the energy consumption by EERA is less than computing-without-MBS. That is because the existence of the MBS server lowers the execution latency and the transmit power. Moreover, the gap between EERA and full-offloading is widening. It illustrates that the offloading bit number becomes less owing to the longer communication distance.


## 4.2. Impacts of Backhaul Time Delay Coefficientϕ

In this subsection, we analyze the energy consumption with respect to the backhaul time delay coefficient in different conditions, e.g., the varying latency constraint, the varying user number, and the varying computation task size.Figure6 plots the sum energy consumption of all SMDs in different backhaul time delay coefficients ϕ versus the execution latency constraints. It is shown that the energy consumption decreases as the execution latency increases. The reason is that more time will be used to offload. And the low transmit power is allowed when the execution latency constraints relax.Figure 6
Energy consumption versus the execution latency.Figure7(a) shows the energy consumption versus user number under different ϕ. Figure 7(b) depicts the energy consumption versus computation task size given different ϕ. Combined with Figure 6, it is observed that a larger backhaul time delay coefficient results in larger energy consumption with the rise of the execution latency, user number, and computation task size. The reason is that a larger backhaul time delay coefficient increases the execution time and reduces the offloading time. Thus, transmit power increases for satisfying the task latency constraints.Figure 7
Effect of the backhaul time delay coefficientϕ on energy consumption.
(a)
Energy consumption versus user number
(b)
Energy consumption versus computation tasks size


## 5. Conclusion

In this paper, we investigated resource allocation mechanisms for three-tier MEC architecture in heterogeneous networks. We considered that both MBS and SBS are integrated with MEC servers and are combined with local devices to form a three-tier computing architecture. Each task from SMDs can be divided into three parts. SMDs, SBS, and MBS perform a part of the task, respectively. We formulated an optimization problem to minimize all SMDs’ energy consumption under the time delay constraints. To improve the efficiency of resource allocation, we proposed an EERA mechanism based on the variable substitution technique, which jointly optimized the computation and radio resources. The optimal workload placement strategy among SMDs, SBS, and MBS was derived. And the optimal computation capability allocation and SMDs’ transmit power were obtained. Finally, numerical simulation results are presented. Compared with the benchmark schemes, the proposed EERA scheme can reduce the SMDs’ energy consumption significantly.



---

*Source: 6098786-2020-04-02.xml*