# Optimization Strategy of Task Offloading with Wireless and Computing Resource Management in Mobile Edge Computing

Authors: Xintao Wu; Jie Gan; Shiyong Chen; Xu Zhao; Yucheng Wu
Journal: Wireless Communications and Mobile Computing
 (2021)

---

## Abstract

Mobile edge computing (MEC) provides user equipment (UE) with computing capability through wireless networks to improve the quality of experience (QoE). The scenario with multiple base stations and multiple mobile users is modeled and analyzed. The optimization strategy of task offloading with wireless and computing resource management (TOWCRM) in mobile edge computing is considered. A resource allocation algorithm based on an improved graph coloring method is used to allocate wireless resource blocks (RBs). The optimal solution of computing resource is obtained by using KKT conditions. To improve the system utility, a semi-distributed TOWCRM strategy is proposed to obtain the task offloading decision. Theoretical simulations under different system parameters are executed, and the proposed semi-distributed TOWCRM strategy can be completed with finite iterations. Simulation results have verified the effectiveness of the proposed algorithm.


---

## Body

## 1. Introduction

With the continuous development of the Internet of things and ubiquitous computing, mobile devices are increasingly running resource-intensive applications, such as interactive games and augmented reality [1, 2]. However, the limited resources of mobile devices cannot fully meet the requirements of these applications for powerful computing power and high speed. In recent years, many solutions have been proposed to solve the problem. In particular, mobile edge computing (MEC) provides a new way for UEs to complete computing tasks. MEC allows user equipment (UE) to offload computing tasks to network edge nodes through the wireless cellular network and performs the offloading tasks. This not only satisfies the expansion demand of users’ computing capabilities but also compensates for the long delay of cloud computing [3]. It is a good method by using small base stations (SBSs) to meet the data rate demand of applications [4, 5]. As one of the key components of 5G, SBSs can enhance the coverage of local hot spots and increase system capacity. Dense network deployment can improve spectrum utilization and reduce end-to-end delay [6, 7].However, task offloading not only generates additional overhead but also may cause intercell interference as it shares the same wireless frequencies among small cells, which will significantly influence the performance of the network [8]. Therefore, a reasonable offloading decision and interference management become the key to achieve efficient computation offloading [9]. A lot of works have been devoted to the research of computation offloading. Most of them have only focused on the process of offloading computing tasks from UE to MEC [10–18]. Only the optimal offloading decision is considered in [10, 11]. Researchers only focused on optimizing the communication resources [12, 13] or the computing resources [14, 15]. In some works, the combination of optimizing offloading decisions and resource allocation is used to minimize the latency or enhance the system performance [16–18]. Recently, research works by combining task offloading and interference management are proposed to improve the system utility [9, 19–21]. However, the scene of one user per base station is studied in [19, 20]. The work about wireless resource allocation does not take the minimum transmission rate requirement of each user into account [9].The mobile devices can gather air quality data to analyze the environmental pollution or collect the image data to realize personal identity authentication from monitoring equipment. The MEC server determines whether the task is processed locally or offloaded to the server according to the computing capacity of the mobile device, the size of data, the delay, and the energy consumption requirements. The main contributions in this article are as follows:(i)
The communication model and the computing model in a multibase station and multiuser MEC scenario are described. The delay and energy consumption in local or remote computing are analyzed(ii)
The user utility is modeled as the weighted sum of the delay ratio and energy consumption ratio. And the system utility is defined as the sum of all user utilities. The optimization of the system utility is formulated by combining task offloading, wireless resource allocation, and computing resource allocation(iii)
The optimal goal is decomposed into three subproblems including wireless resource block allocation (RBA), computing resource allocation (CRA), and task offloading decision. The RBA is solved by using a resource allocation algorithm based on an improved graph coloring method. The optimal solution of CRA is obtained by using KKT conditions. In task offloading, a semi-distributed task offloading with wireless and computing resource management (TOWCRM) strategy is proposed to optimize the system utility under the constraints of computing resourcesThe rest of this article is organized as follows: the related works are discussed in Section2. The system model with multiple cells and multiple users in the MEC scenario is described in Section 3. The optimization of the system utility is formulated in Section 4. In Section 5, wireless resource optimization and computing resource allocation are discussed. A semi-distributed TOWCRM algorithm is proposed to optimize offloading tasks. The simulation results are given and discussed in Section 6. The conclusion of this work is described in Section 7.


## 2. Related Works

Edge computing could be affected by external environment (such as wireless channel, interferences among mobile users, communication link quality, and the status of the communication channel) during offloading [22]. Therefore, it is very important to establish a suitable environment of offloading policy for computation offloading. In [10, 11], these studies only paid attention to task offloading without optimizing communication and computing resources. It was assumed that the capacity of cloud computing is unlimited, and some studies only focused on the optimization of communication resources in [12, 13]. For instance, to maximize the network management profit, an optimal solution algorithm based on the idea of branch-and-price was put forward to address joint resource management for device-to-device (D2D) communication [12]. Based on combining resource allocation and task assignment, a low-complexity iteration algorithm was proposed to minimize the task execution latency of all users subject to task and resource constraints in [13]. In contrast, only computing resource was optimized during task offloading [14, 15]. A new market-based framework was proposed to efficiently allocate computing resources of heterogeneous capacity-limited edge nodes (EN) for multiple competing services at the network edge in [14]. In [15], a smart contract that exploited the state-of-the-art machine learning algorithm was used in a private blockchain network to allocate the edge computing resources. In [16–18], joint communication and computing resource optimization were considered during the task offloading. To minimize the average latency of users to complete tasks, a strongly nonconvex problem with coupled variables was described as jointly considering the offloading decision, computation, and broadband resource allocation [16]. In [17], the problem of joint service caching, computation offloading, transmission, and computing resource allocation in a scenario of multiple users with multiple tasks was formulated to minimize the overall computation and delay costs. Moreover, the scenario where each user had a computation cost constraint was studied. A semi-distributed heuristic offloading decision algorithm (HODA) was proposed to maximize the system utility, which jointly optimized the offloading decision, communication, and computing resources [18].In addition, there have been also some works that consider the joint optimization of task offloading and interference management at the same time [19–21]. Task offloading was studied in a MEC scenario with a single user per cell in [19, 20]. For example, offloading decision was made by considering the effect of intercell interference on system performance, where physical resource block (PRB) and computing resource allocation were treated as a joint optimization problem. The MEC server made the offloading decision to maximize the overhead, and the PRB was allocated by using a graph coloring algorithm [19]. In [21], the problem of joint task offloading and resource allocation was studied to maximize the offloading utility, which was modeled by the weighted sum of task completion time and device energy consumption. The resource allocation (RA) problem using convex and quasiconvex optimization was addressed, and a novel heuristic algorithm was proposed to solve the task offloading. It could achieve a suboptimal solution in polynomial time. However, there was no consideration to minimize interferences among mobile users.


## 3. System Model

This section describes the system model used in our work. Firstly, the network model is introduced in detail. Then, the corresponding communication model and calculation model are derived based on the proposed network model. For simplicity, the key notations used in the article are summarized in Table1.Table 1
Summary of key notations.
NotationDescriptionSSet of SBSsUsSet of UEs in the coverage area ofsXThe task offloading decisionYThe RB association strategyFComputing resource allocation policyNSet of RBsBThe bandwidth of every RBxusmThe offloading variableyusmnRB assigned variableIusmnThe interference intensityPusmThe transmission power ofusmKusmThe number of RBs assigned tousmHutm,SThe channel gain betweenutm and sRusmrUplink data rate fromusm to sCTusmComputational task ofusmDusmInput data of computation taskCTusmCusmWorkloads of computation taskCTusmfusmlocLocal computing capability ofusmTusmlocLocal execution time of taskCTusmTusm,offrTransmission time of taskCTusm to the MEC serverTusm,exerExecution time of taskCTusm at the MEC serverEusmlocEnergy consumption ofusm when executing its task locallyEusm,offrEnergy consumption ofusm when offloading its task CTusmfusmrComputing resources that the MEC server allocates tousmfComputing resources of the MEC serverβusmtPreference ofusm on task completion timeβusmePreference ofusm on task energy consumptionWusmUser utility ofusmOsThe set of offloading UEs under each SBSRusmminThe minimum rate requirement ofusmR1×OsUser benefit matrixRR1×NChannel benefit matrix


### 3.1. Network Model

As shown in Figure1, a two-layer cellular heterogeneous network composed of a macro cell base station (MBS) and S small cell base stations is considered [19, 20]. The MEC server is deployed on the side of the MBS and can perform multiple computing tasks at the same time. S SBSs are connected to the MEC server through optical fiber links like the MBS. Let S=1,2,⋯,s,⋯,S be the set of SBSs, and there are M UEs associated with each SBS in its coverage. We denote the set of UEs in the coverage area of s as Us=us1,us2,⋯,usm,⋯,usM, where usm represents a UE belonging to s. In addition, for simplicity, the mobility of users or the handover among cells was not considered as it was assumed in [23–25]. Similar to many previous works in cloud computing and mobile networks [26–28], it is a semistatic scenario, which means that the position and transmission channel conditions remain unchanged during offloading a task.Figure 1
Cellular heterogeneous network model in mobile edge computing.


### 3.2. Communication Model

It is assumed that each UE has a time-sensitive task that requires a lot of computing resources to complete. Each UE can perform by offloading the computing task to the MEC server through its associated SBS or execute the computing task locally. Therefore, we denote the offloading variable asxusm∈0,1. xusm=0 means that usm performs its task locally. xusm=1 means that the user of usm chooses to offload the task to the MEC server via a wireless link. The task offloading decision can be expressed as X=xusm, which is a matrix of S×M.Uplink spectrum multiplexing is used in this model. The spectrum resources of the entire system are divided intoN orthogonal RBs, and the RB set is defined as N=1,2,⋯,n,⋯,N The RB associated table is defined as Ys=yusmn, which is a M×N matrix, where M is the total number of UEs in the s-th cell and N is the total number of RBs. yusmn=1 means that the n-th RB is assigned to usm; otherwise, yusmn=0. And the RB allocation strategy is defined as Y=Ys, s∈S.During uplink transmission, each UE and each SBS have a single antenna for sending and receiving messages. Whenusm offloads its task to the MEC server for calculation, interference will occur if there are UEs in other SBSs sharing the same RB(s) with the current usm . As RBs are assigned orthogonally to users in each cell, there is no interference in intracell. The interference transmission power from utm sharing the n-th RB to the s-th cell can be described as
(1)Iusmn=∑t=1,t≠sS∑m=1MxutmyusmnPutmKutmHutm,S,where Putm represents the transmission power of utm, Kutm stands for the number of RBs assigned to utm, and Hutm,S denotes the channel gain between utm and s.Given the decision matrixX and the RB associated strategy Y, the uploading rate achieved by usm connected to s can be obtained by Shannon’s formula as [19]
(2)RusmrX,Y=xusm∑n=1NyusmnBlog21+PusmHusm,sKusmIusmn+σ2,where σ2 is the variance of background noise, B is the bandwidth of each RB, Pusm represents the transmission power of usm, Kusm stands for the number of RB allocated to usm, and Husm,s denotes the channel gain between usm and s.


### 3.3. Calculation Model

The computing task ofusm is described as CTusm=<Dusm,Cusm>, in which Dusm (in kB) represents the size of transmission data and Cusm (in megacycles) specifies the workload, i.e., the number of CPU cycles required to complete the computing task. The values of Dusm and Cusm can be obtained by carefully analyzing the offloading task [29, 30]. The delay and power consumption of local and remote computation will be discussed, respectively.
(1)
Local computing: letfusmloc>0 represent the local computing capacity of usm in terms of the number of CPU cycles/s. The computation time Tusmloc for the local execution of the task CTusm can be expressed as(3)Tusmloc=Cusmfusmloc,and the energy consumption Eusmloc is denoted as
(4)Eusmloc=kfusmloc2Cusm,where kfusmloc2 is the energy consumption per calculation cycle and k depends on the energy coefficient on the chip architecture. According to the actual measurement, k=10−27 is usually adopted [21].
(2)
Remote computing:usm is connected to the corresponding s through a wireless network, and its task is offloaded to the MEC server for calculation. The computing resources provided by the MEC server are quantified by the computing capacity f (CPU cycles/s), which can be shared among the related UEs. The uplink transmission delay of usm can be expressed as follows:(5)Tusm,offr=DusmRusmrX,Y.When a computing taskCTusm is offloaded to the MEC server, the MEC server allocates specific computing resources to process the task, which is represented by fusmr (CPU cycles/s). And the computing resource allocation profile is defined as F=fusmr. During the execution of the task, it is assumed that the calculation speed assigned by the MEC server to each UE is fixed. The time of the MEC server executing the task is described as
(6)Tusm,exer=Cusmfusmr.In addition, a feasible computing allocation strategy must satisfy the constraints of computing resources, which can be expressed as(7)∑s∈S∑usm∈Usxusmfusmr≤f.The total delay ofusm for finishing the task is given by the following equation:
(8)Tusmr=Tusm,exer+Tusm,offr=Cusmfusmr+DusmRusmrX,Y.Through the above analysis, the energy consumption ofusm during the transmission data can be calculated as
(9)Eusm,offr=Pusm×Tusm,offr=PusmDusmRusmrX,Y,where Pusm represents the transmitting power of usm.We mainly consider the energy consumption and delay of UEs, and the computing energy consumption of the MEC server is omitted. As the amount of data returned to the mobile users is small, the power consumption and latency of UE receiving the returned data are omitted.


## 3.1. Network Model

As shown in Figure1, a two-layer cellular heterogeneous network composed of a macro cell base station (MBS) and S small cell base stations is considered [19, 20]. The MEC server is deployed on the side of the MBS and can perform multiple computing tasks at the same time. S SBSs are connected to the MEC server through optical fiber links like the MBS. Let S=1,2,⋯,s,⋯,S be the set of SBSs, and there are M UEs associated with each SBS in its coverage. We denote the set of UEs in the coverage area of s as Us=us1,us2,⋯,usm,⋯,usM, where usm represents a UE belonging to s. In addition, for simplicity, the mobility of users or the handover among cells was not considered as it was assumed in [23–25]. Similar to many previous works in cloud computing and mobile networks [26–28], it is a semistatic scenario, which means that the position and transmission channel conditions remain unchanged during offloading a task.Figure 1
Cellular heterogeneous network model in mobile edge computing.


## 3.2. Communication Model

It is assumed that each UE has a time-sensitive task that requires a lot of computing resources to complete. Each UE can perform by offloading the computing task to the MEC server through its associated SBS or execute the computing task locally. Therefore, we denote the offloading variable asxusm∈0,1. xusm=0 means that usm performs its task locally. xusm=1 means that the user of usm chooses to offload the task to the MEC server via a wireless link. The task offloading decision can be expressed as X=xusm, which is a matrix of S×M.Uplink spectrum multiplexing is used in this model. The spectrum resources of the entire system are divided intoN orthogonal RBs, and the RB set is defined as N=1,2,⋯,n,⋯,N The RB associated table is defined as Ys=yusmn, which is a M×N matrix, where M is the total number of UEs in the s-th cell and N is the total number of RBs. yusmn=1 means that the n-th RB is assigned to usm; otherwise, yusmn=0. And the RB allocation strategy is defined as Y=Ys, s∈S.During uplink transmission, each UE and each SBS have a single antenna for sending and receiving messages. Whenusm offloads its task to the MEC server for calculation, interference will occur if there are UEs in other SBSs sharing the same RB(s) with the current usm . As RBs are assigned orthogonally to users in each cell, there is no interference in intracell. The interference transmission power from utm sharing the n-th RB to the s-th cell can be described as
(1)Iusmn=∑t=1,t≠sS∑m=1MxutmyusmnPutmKutmHutm,S,where Putm represents the transmission power of utm, Kutm stands for the number of RBs assigned to utm, and Hutm,S denotes the channel gain between utm and s.Given the decision matrixX and the RB associated strategy Y, the uploading rate achieved by usm connected to s can be obtained by Shannon’s formula as [19]
(2)RusmrX,Y=xusm∑n=1NyusmnBlog21+PusmHusm,sKusmIusmn+σ2,where σ2 is the variance of background noise, B is the bandwidth of each RB, Pusm represents the transmission power of usm, Kusm stands for the number of RB allocated to usm, and Husm,s denotes the channel gain between usm and s.


## 3.3. Calculation Model

The computing task ofusm is described as CTusm=<Dusm,Cusm>, in which Dusm (in kB) represents the size of transmission data and Cusm (in megacycles) specifies the workload, i.e., the number of CPU cycles required to complete the computing task. The values of Dusm and Cusm can be obtained by carefully analyzing the offloading task [29, 30]. The delay and power consumption of local and remote computation will be discussed, respectively.
(1)
Local computing: letfusmloc>0 represent the local computing capacity of usm in terms of the number of CPU cycles/s. The computation time Tusmloc for the local execution of the task CTusm can be expressed as(3)Tusmloc=Cusmfusmloc,and the energy consumption Eusmloc is denoted as
(4)Eusmloc=kfusmloc2Cusm,where kfusmloc2 is the energy consumption per calculation cycle and k depends on the energy coefficient on the chip architecture. According to the actual measurement, k=10−27 is usually adopted [21].
(2)
Remote computing:usm is connected to the corresponding s through a wireless network, and its task is offloaded to the MEC server for calculation. The computing resources provided by the MEC server are quantified by the computing capacity f (CPU cycles/s), which can be shared among the related UEs. The uplink transmission delay of usm can be expressed as follows:(5)Tusm,offr=DusmRusmrX,Y.When a computing taskCTusm is offloaded to the MEC server, the MEC server allocates specific computing resources to process the task, which is represented by fusmr (CPU cycles/s). And the computing resource allocation profile is defined as F=fusmr. During the execution of the task, it is assumed that the calculation speed assigned by the MEC server to each UE is fixed. The time of the MEC server executing the task is described as
(6)Tusm,exer=Cusmfusmr.In addition, a feasible computing allocation strategy must satisfy the constraints of computing resources, which can be expressed as(7)∑s∈S∑usm∈Usxusmfusmr≤f.The total delay ofusm for finishing the task is given by the following equation:
(8)Tusmr=Tusm,exer+Tusm,offr=Cusmfusmr+DusmRusmrX,Y.Through the above analysis, the energy consumption ofusm during the transmission data can be calculated as
(9)Eusm,offr=Pusm×Tusm,offr=PusmDusmRusmrX,Y,where Pusm represents the transmitting power of usm.We mainly consider the energy consumption and delay of UEs, and the computing energy consumption of the MEC server is omitted. As the amount of data returned to the mobile users is small, the power consumption and latency of UE receiving the returned data are omitted.


## 4. Problem Formulation

In this section, the problem of task offloading, wireless RBs, and computing resource allocation is formulated under the definition of user and system utility.In a mobile cloud computing system, UEs’ preference is mainly manifested in task completion time ofβusmt and energy consumption of βusme. βusmt, βusme∈0,1, and βusmt+βusme=1. The quality of experience (QoE) can be described by comparing the delay and the power consumption of remote computing with that of local execution [18, 21]. The user utility of Wusm for usm can be defined as
(10)Wusm=βusmtTusmloc−TusmrTusmloc+βusmeEusmloc−Eusm,offrEusmlocxusm.βusmt and βusme can be determined according to the life of the remaining battery and the mission completion time requirements. From the above expression, it is clear that its user utility Wusm is equal to 0 when the task of usm is executed locally (xusm=0). When the task of usm is executed on the MEC server xusm=1, its user utility Wusm is larger than 0.Given the offloading policy ofX, the RB allocation strategy of Y, and the calculating resource allocation policy of F, the system utility can be defined as the sum of all user utilities and is expressed as follows:
(11)WX,Y,F=∑s∈S∑usm∈UsWusm.To maximize the system utility by jointly optimizing task offloading, wireless RBs, and computing resource allocation in mobile edge computing, the optimal goal can be formulated as(12)maxX,Y,FWX,Y,Fs.t.C1:xusm∈0,1∀usm∈Us,s∈SC2:yusmn∈0,1∀usm∈Us,n∈N,s∈S,C3:∑s∈S∑usm∈Usxusmfusmr≤f.The constraints in the above formula can be interpreted as follows: constraintC1 in (12) implies that the task can be executed locally or offloaded to the MEC server for execution. Constraint C2 in (12) indicates whether the n-th RB is assigned to usm. Constraint C3 in (12) ensures that the sum of computing resources allocated to all offloading UEs does not exceed the computing capacity of the MEC server.Due to the existence of integer variables, the above equation is a mixed integer nonlinear program (MINLP) problem [31]. The equation of (12) can be rewritten as follows:
(13)maxX,Y,FWX,Y,F=maxXmaxY,FWX,Y,F.From (13), it can be seen that offloading decision, RB allocation, and computing resource allocation are decoupled from each other [32].The original problem can be translated into offloading decision and resource allocations. In the next section, we will present solutions to both the resource allocations and task offloading decision.


## 5. Resource Optimization and Task Offloading Strategy

In this section, considering the time delay and energy consumption demand of UEs, a resource allocation algorithm based on improved graph coloring is used to allocate RBs. The solution of computing resources is obtained by using KKT conditions, and a semi-distributed TOWCRM algorithm is adopted to optimize the offloading decision.The set of offloading UEs for thes-th SBS is defined as Os.If a feasible task offloading decision is given, the objective function of (12) can be translated as follows:
(14)maxX,FWX,Y,F=maxY,F∑s∈S∑usm∈Usβusmtβusme−VX,Y,F,s.t.C1:Yusmn∈0,1∀usm∈Us,n∈N,s∈S,C2:∑s∈S∑usm∈Usxusmfusmr≤f,where
(15)VX,Y,F=∑s∈S∑usm∈ϑsβusmtTusmrTusmloc+βusmeEusm,offrEusmloc.From (14), it is easy to see that ∑s∈S∑usm∈Usβusmt+βusme is an exact value for a specific offloading decision of X. The VX,Y,F can be regarded as the total offloading cost of all UEs who need to be offloaded. Therefore, the equation of (14) can be equivalent to minimize the total offloading overheads.
(16)minY,FVX,Y,F=minY,F∑s∈S∑usm∈Osϕusm+ψusmRusmrX,Y+∑s∈S∑usm∈Osηusmfusmrs.t.C1:Yusmn∈0,1∀usm∈Us,n∈N,s∈S,C2:∑s∈S∑usm∈Osfusmr≤f,where ∅usm=βusmtDusm/Tusmloc, ψusm=βusmtDusmPusm/Eusmloc, and ηusm=βusmtfusmloc.It can be seen from (16) that RB allocation and computing resource allocation are decoupled from each other in the target and constraint. We can decouple problem (16) into two independent problems, namely, resource block allocation (RBA) and computing resource allocation (CRA), and their respective solutions are presented in the following sections.


### 5.1. Resource Block Allocation (RBA)

Taking the first term in (16) as the objective function, the RB assignment problem of ΓX,Y can be written as
(17)minYΓX,Y=minY∑s∈S∑usm∈Osϕusm+ψusmRusmrX,Ys.t.yusmn∈0,1∀usm∈Us,n∈N,s∈S.Note that in the RB allocation phase, it is assumed that all UEs are transmitted with a fixed transmission power ofPusm. The transmitted power of each UE is equally distributed over each RB assigned to it. From (17), the minimal value of ΓX,Y is obtained if the transmission rate of each offloading UE is maximized.In order to better illustrate the transmission quality, the minimum transmission rate (when all UEs of the system are offloaded, computing resources are equally distributed to all UEs) is expressed as(18)Rusmmin=Dusm×fTusmloc×f−Cusm×S×M.For the above RBA problem, it can be equivalent to the matching problem of the number of offloading UEs and the number of RBs. Therefore, a resource allocation algorithm based on an improved graph coloring method [19] is proposed to solve the above problem. The algorithm flow is simply described as follows:
(1)
Initialization (step 1): in this step, the MEC server sets the RB allocation strategyY to zeros and constructs S user benefit matrices as R1×ϑs=rusm, where every user rate is rusm=Blog21+PusmHusm,s/σ2,usm∈ϑs,s∈S. At the same time, each UE also constructs its own channel benefit matrix R_R1×N=yusmnBlog21+PusmHusm,s/KusmIusmn+σ2, usm∈ϑs,s∈S(2)
Orthogonal allocation (step 2): if the number of the offloading UEs is less than or equal to the number of RBs, RBs are allocated according to a uniform zero frequency reuse (UZFR) method [9]. Otherwise, the elements in S user benefit matrices are sorted by rusm in descending order, and RBs are assigned to the first N UEs according to the UZFR method(3)
Allocate the RB with the greatest channel benefit (step3): on the basis of step 2, the MEC server selects a UE with the best user benefit from the remaining UEs. The selected UE starts to update its own channel benefit matrix according to the RB allocation strategy at this time and then selects the RB with the greatest channel benefit as the transmission RB. The MEC server deletes the selected UE from the remaining UEs. Step 3 will be repeated until all offloading UEs are assigned to RB(4)
Check whether all offloading UEs meet the minimum rate (step 4): according to (18), all offloading UEs will be checked whether they meet the minimum transmission rate. If satisfied, the algorithm terminates. If not, these UEs need to continue to allocate RBs. The set of these UEs is denoted as I′(5)
RB reallocation (step 5): the MEC server selects a UE with the best user benefit from UEs that needed to continue to allocate RBs. The selected UE starts to update its own channel benefit matrix according to the RB allocation strategy at this time and then selects the RB with the greatest channel benefit as the transmission RB. The MEC server deletes the selected UE from UEs that needed to continue to allocate RBs. Repeat step 5 until all UEs that do not meet the minimum rate are once again assigned to RB(6)
Iterative loop (step 6): step 4 to step 5 will be repeated until all UEs meet the minimum rate orI′=∅. Then, the algorithm terminates and the RB allocation strategy Y∗ is obtained under the offloading decisionThe optimal objective function of (17) can be calculated as
(19)minΓX,Y=min∑s∈S∑usm∈Osϕusm+ψusmRusmrX,Y∗.


### 5.2. Computing Resource Allocation (CRA)

From (16), computing resource allocation (CRA) is to optimize the second term of formula (16) and is expressed as follows:
(20)minFϕX,Fs.t.C1:∑s∈S∑usm∈Osfusmr≤f,C2:fusmr>0,where
(21)ΦX,F=∑s∈S∑usm∈Osηusmfusmr.From the above equation, it is a convex optimization problem. And constraintC2 in (20) is slack based on Karush-Kuhn-Tucker conditions, and it can be solved by using the KKT conditions.The equivalent Lagrange function of this problem can be expressed as(22)Lfusmr,β=∑s∈S∑usm∈ϑsηusmfusmr+β∑s∈S∑usm∈ϑsfusmr−f.Letβ>0 be the Lagrange operator; the derivatives of the Lagrange function of Lfusmr,β can be described as
(23)∂Lfusmr,β∂fusmr=−ηusmfusmr2+β.By setting the above equation equal to 0, the solution of optimal computing resource allocation for problem (20) can be obtained.
(24)fusmr∗=ηusmβ,where
(25)∑s∈S∑usm∈ϑsfusmr∗=f.By substituting (24) into (25) and setting fusmr=0, if usm does not belong to ϑs, s∈S, the solution of β can be obtained as
(26)β∗=1f∑s∈S∑usm∈ϑsηusm2.Substituting (26) into (24), the optimal solution can be obtained as follows:
(27)fusmr∗=fηusm∑s∈S∑usm∈ϑsηusm,usm∈ϑs,s∈S.The optimal objective function of (20) can be expressed as
(28)ΦX,F∗=∑s∈S∑usm∈Osηusmf.


### 5.3. Task Offloading Decision

In the previous section, for a given task offloading decisionX, the solutions of RBA and CRA are obtained. According to (13), (16), (19), and (28), the system utility can be expressed as follows:
(29)W∗X=∑s∈S∑usm∈Usβusmt+βusme−ΓX,Y∗−ΦX,F∗.Given the RB allocation strategy ofY∗ and computing allocation strategy of F∗, the objective function of (13) can be written as
(30)maxXW∗Xs.t.xusm∈0,1∀usm∈Us,s∈S.From the above equation, it is not a convex function due to the fact thatX is a binary variable. For the purpose of solving this nonconvex problem, a semi-distributed TOWCRM algorithm consisting of two stages that can find a local optimum to problem (30) is adopted, as shown in Algorithm 1. In the first stage, each mobile user independently optimizes its user utility after optimizing wireless and computing resource allocation and determines whether to send an offloading request, including the information on mobile user parameters and the features of computation task. In the second stage, the MEC server determines whether the offloading user joins the offloading set by comparing the system utility, which includes the offloading user or not. Finally, the selected mobile users offload their computation tasks.In stage 1, each UE calculates its own user utilityWusm, according to βusmtTusmloc−Tusmr/Tusmloc+βusmeEusmloc−Eusm,offr/Eusmloc. Moreover, each UE checks whether its user utility is larger than zero. If it satisfies, an offloading request is sent. Otherwise, an empty message is sent, which indicates that local computation is adopted.In stage 2, the MEC server waits until it has collected all the requests and accepts the topN UEs of user utility in the offloading request. The initial offloading policy X can be got. The corresponding RB allocation strategy of Y∗ and the corresponding computing resource allocation of F∗ are obtained, respectively. According to (29), the system utility of WX,Y∗,F∗ can be obtained. And let K be the set of UEs that the server accepts requests but does not accept offloading. The MEC server selects the UE with maximum user utility in K to add offloading policy X, and the RB allocation strategy Y and the computing resource allocation F will be updated. According to (19), the system utility WX,Y,F can be obtained. If WX,Y,F>WX,Y∗,F∗, the MEC server removes this UE from the offloading policy. Otherwise, the system utility, RB allocation strategy, and computing resource allocation are updated. Finally, this UE is removed from the set K, and steps 21 to 33 will be repeated until the set K is equal to ∅. The MEC server forms the RB allocation strategy and computing resource allocation strategy and starts to send offloading decision to UEs. Receiving this message, UEs start to offload their tasks accordingly.Algorithm 1: Semi-distributed TOWCRM Algorithm.
Stage 1: at UEs side1: for each base stations∈Sdo2: for each deviceusm∈Us do3:Y∗⟵ improved graph coloring algorithm4:F∗⟵ equation (28)5:Wusm⟵βusmtTusmloc−Tusmr/Tusmloc+βusmeEusmloc−Eusm,offr/Eusmloc6: end for7: end for8: ifWusm>0then9: send an offloading request10: else11: send NULL12: end ifStage 2: at the MEC side13: Wait until all requests are accepted14: fori=0;i<N;i++ do15:xusm⟵argmaxWusm, usm∈Us,s∈S.16: setX⟵X∪xusm17: end for18:Y∗⟵ step 3; F∗⟵ step419:WX,Y∗,F∗⟵ equation (29)20: letK be the set of UEs that the server accepts requests but does not accept offloading21: while∣K∣>0 do22:xk⟵argmaxWk,k∈K23:X⟵X∪xk24:Y⟵ step 3; F⟵ step 4; WX,Y,F⟵ step 1925: ifWX,Y,F<WX,Y∗,F∗ then26:X⟵X/xk27: else28:WX,Y∗,F∗=WX,Y,F29:Y∗=Y30:F∗=F31: end if32:K⟵K/k33: end while34: The MEC server forms RB allocation strategyY and computing resources F and starts to send offloading decision X to UEs


## 5.1. Resource Block Allocation (RBA)

Taking the first term in (16) as the objective function, the RB assignment problem of ΓX,Y can be written as
(17)minYΓX,Y=minY∑s∈S∑usm∈Osϕusm+ψusmRusmrX,Ys.t.yusmn∈0,1∀usm∈Us,n∈N,s∈S.Note that in the RB allocation phase, it is assumed that all UEs are transmitted with a fixed transmission power ofPusm. The transmitted power of each UE is equally distributed over each RB assigned to it. From (17), the minimal value of ΓX,Y is obtained if the transmission rate of each offloading UE is maximized.In order to better illustrate the transmission quality, the minimum transmission rate (when all UEs of the system are offloaded, computing resources are equally distributed to all UEs) is expressed as(18)Rusmmin=Dusm×fTusmloc×f−Cusm×S×M.For the above RBA problem, it can be equivalent to the matching problem of the number of offloading UEs and the number of RBs. Therefore, a resource allocation algorithm based on an improved graph coloring method [19] is proposed to solve the above problem. The algorithm flow is simply described as follows:
(1)
Initialization (step 1): in this step, the MEC server sets the RB allocation strategyY to zeros and constructs S user benefit matrices as R1×ϑs=rusm, where every user rate is rusm=Blog21+PusmHusm,s/σ2,usm∈ϑs,s∈S. At the same time, each UE also constructs its own channel benefit matrix R_R1×N=yusmnBlog21+PusmHusm,s/KusmIusmn+σ2, usm∈ϑs,s∈S(2)
Orthogonal allocation (step 2): if the number of the offloading UEs is less than or equal to the number of RBs, RBs are allocated according to a uniform zero frequency reuse (UZFR) method [9]. Otherwise, the elements in S user benefit matrices are sorted by rusm in descending order, and RBs are assigned to the first N UEs according to the UZFR method(3)
Allocate the RB with the greatest channel benefit (step3): on the basis of step 2, the MEC server selects a UE with the best user benefit from the remaining UEs. The selected UE starts to update its own channel benefit matrix according to the RB allocation strategy at this time and then selects the RB with the greatest channel benefit as the transmission RB. The MEC server deletes the selected UE from the remaining UEs. Step 3 will be repeated until all offloading UEs are assigned to RB(4)
Check whether all offloading UEs meet the minimum rate (step 4): according to (18), all offloading UEs will be checked whether they meet the minimum transmission rate. If satisfied, the algorithm terminates. If not, these UEs need to continue to allocate RBs. The set of these UEs is denoted as I′(5)
RB reallocation (step 5): the MEC server selects a UE with the best user benefit from UEs that needed to continue to allocate RBs. The selected UE starts to update its own channel benefit matrix according to the RB allocation strategy at this time and then selects the RB with the greatest channel benefit as the transmission RB. The MEC server deletes the selected UE from UEs that needed to continue to allocate RBs. Repeat step 5 until all UEs that do not meet the minimum rate are once again assigned to RB(6)
Iterative loop (step 6): step 4 to step 5 will be repeated until all UEs meet the minimum rate orI′=∅. Then, the algorithm terminates and the RB allocation strategy Y∗ is obtained under the offloading decisionThe optimal objective function of (17) can be calculated as
(19)minΓX,Y=min∑s∈S∑usm∈Osϕusm+ψusmRusmrX,Y∗.


## 5.2. Computing Resource Allocation (CRA)

From (16), computing resource allocation (CRA) is to optimize the second term of formula (16) and is expressed as follows:
(20)minFϕX,Fs.t.C1:∑s∈S∑usm∈Osfusmr≤f,C2:fusmr>0,where
(21)ΦX,F=∑s∈S∑usm∈Osηusmfusmr.From the above equation, it is a convex optimization problem. And constraintC2 in (20) is slack based on Karush-Kuhn-Tucker conditions, and it can be solved by using the KKT conditions.The equivalent Lagrange function of this problem can be expressed as(22)Lfusmr,β=∑s∈S∑usm∈ϑsηusmfusmr+β∑s∈S∑usm∈ϑsfusmr−f.Letβ>0 be the Lagrange operator; the derivatives of the Lagrange function of Lfusmr,β can be described as
(23)∂Lfusmr,β∂fusmr=−ηusmfusmr2+β.By setting the above equation equal to 0, the solution of optimal computing resource allocation for problem (20) can be obtained.
(24)fusmr∗=ηusmβ,where
(25)∑s∈S∑usm∈ϑsfusmr∗=f.By substituting (24) into (25) and setting fusmr=0, if usm does not belong to ϑs, s∈S, the solution of β can be obtained as
(26)β∗=1f∑s∈S∑usm∈ϑsηusm2.Substituting (26) into (24), the optimal solution can be obtained as follows:
(27)fusmr∗=fηusm∑s∈S∑usm∈ϑsηusm,usm∈ϑs,s∈S.The optimal objective function of (20) can be expressed as
(28)ΦX,F∗=∑s∈S∑usm∈Osηusmf.


## 5.3. Task Offloading Decision

In the previous section, for a given task offloading decisionX, the solutions of RBA and CRA are obtained. According to (13), (16), (19), and (28), the system utility can be expressed as follows:
(29)W∗X=∑s∈S∑usm∈Usβusmt+βusme−ΓX,Y∗−ΦX,F∗.Given the RB allocation strategy ofY∗ and computing allocation strategy of F∗, the objective function of (13) can be written as
(30)maxXW∗Xs.t.xusm∈0,1∀usm∈Us,s∈S.From the above equation, it is not a convex function due to the fact thatX is a binary variable. For the purpose of solving this nonconvex problem, a semi-distributed TOWCRM algorithm consisting of two stages that can find a local optimum to problem (30) is adopted, as shown in Algorithm 1. In the first stage, each mobile user independently optimizes its user utility after optimizing wireless and computing resource allocation and determines whether to send an offloading request, including the information on mobile user parameters and the features of computation task. In the second stage, the MEC server determines whether the offloading user joins the offloading set by comparing the system utility, which includes the offloading user or not. Finally, the selected mobile users offload their computation tasks.In stage 1, each UE calculates its own user utilityWusm, according to βusmtTusmloc−Tusmr/Tusmloc+βusmeEusmloc−Eusm,offr/Eusmloc. Moreover, each UE checks whether its user utility is larger than zero. If it satisfies, an offloading request is sent. Otherwise, an empty message is sent, which indicates that local computation is adopted.In stage 2, the MEC server waits until it has collected all the requests and accepts the topN UEs of user utility in the offloading request. The initial offloading policy X can be got. The corresponding RB allocation strategy of Y∗ and the corresponding computing resource allocation of F∗ are obtained, respectively. According to (29), the system utility of WX,Y∗,F∗ can be obtained. And let K be the set of UEs that the server accepts requests but does not accept offloading. The MEC server selects the UE with maximum user utility in K to add offloading policy X, and the RB allocation strategy Y and the computing resource allocation F will be updated. According to (19), the system utility WX,Y,F can be obtained. If WX,Y,F>WX,Y∗,F∗, the MEC server removes this UE from the offloading policy. Otherwise, the system utility, RB allocation strategy, and computing resource allocation are updated. Finally, this UE is removed from the set K, and steps 21 to 33 will be repeated until the set K is equal to ∅. The MEC server forms the RB allocation strategy and computing resource allocation strategy and starts to send offloading decision to UEs. Receiving this message, UEs start to offload their tasks accordingly.Algorithm 1: Semi-distributed TOWCRM Algorithm.
Stage 1: at UEs side1: for each base stations∈Sdo2: for each deviceusm∈Us do3:Y∗⟵ improved graph coloring algorithm4:F∗⟵ equation (28)5:Wusm⟵βusmtTusmloc−Tusmr/Tusmloc+βusmeEusmloc−Eusm,offr/Eusmloc6: end for7: end for8: ifWusm>0then9: send an offloading request10: else11: send NULL12: end ifStage 2: at the MEC side13: Wait until all requests are accepted14: fori=0;i<N;i++ do15:xusm⟵argmaxWusm, usm∈Us,s∈S.16: setX⟵X∪xusm17: end for18:Y∗⟵ step 3; F∗⟵ step419:WX,Y∗,F∗⟵ equation (29)20: letK be the set of UEs that the server accepts requests but does not accept offloading21: while∣K∣>0 do22:xk⟵argmaxWk,k∈K23:X⟵X∪xk24:Y⟵ step 3; F⟵ step 4; WX,Y,F⟵ step 1925: ifWX,Y,F<WX,Y∗,F∗ then26:X⟵X/xk27: else28:WX,Y∗,F∗=WX,Y,F29:Y∗=Y30:F∗=F31: end if32:K⟵K/k33: end while34: The MEC server forms RB allocation strategyY and computing resources F and starts to send offloading decision X to UEs


## 6. Simulation Results and Analysis

In a centralized MEC network, it consists of one MBS with the MEC server and four SBSs are deployed in100∗100m2. The MBS is located in the center of the area, and the four SBSs are placed in the four directions of the area. Each SBS has a coverage area of 30 m. The radio communication parameters follow the Third Generation Partnership Project specification [33]. It is assumed that the data size of Dusm is 420 kB and the workload of Cusm is 1000 megacycles. The MATLAB® package is used to carry out the simulations, and the system parameters are summarized in Table 2.Table 2
Basic parameters of system simulation.
ParametersValuesRB bandwidthB1 MHzNumber of resource blocks RB10UE transmitted powerPusm20 dBmUEs preferenceβusmt=βusme0.5Input data sizeDusm420 kBTotal number of CPU cyclesCusm1000 megacyclesUE computing capacityfusmloc0.7 GHzMEC computing capacityf100 GHzThe background noiseσ2-100 dBmPathloss from UE to SBS140.7+36.7log10rIn addition, UEs are randomly distributed in the coverage of each SBS. If not particularly indicated, the number of RBs is 10. The system utility performance of the proposed TOWCRM strategy is compared with that of the heuristic joint task offloading scheduling and resource allocation strategy (hJTORA) [21].In order to visually show the resource allocation algorithm based on improved graph coloring, Figure2 shows the RB allocation of UEs. There is a total of one MBS, four SBSs, and 10 RBs in the whole system, and there are 10 UEs associated with each SBS, among which there are 23 offloading UEs. We can observe that the UE covered by the same SBS does not occupy the same RBs, and the RB is reused by the UEs belonging to different SBS, such as the 2-th and the 4-th RB. Some UEs are assigned to multiple RBs, such as u12 and u26. The results of RB allocation show that the resource matching algorithm is effective.Figure 2
RB allocation based on improved graph coloring.By performing 1000 times of simulation, Figures3(a) and 3(b) show the system utility performance with different Dusm or Cusm, respectively. From Figures 3(a) and 3(b), the system utility calculated by the proposed TOWCRM strategy is higher than that computed by hJTORA. From Figure 3(a), it can be seen that the system performance of two strategies decreases as the tasks’ input data size increases. From Figure 3(b), the system utility becomes larger as the tasks’ workload increases. This means that the task with smaller input data or higher workloads will improve the value of system utility.Figure 3
The system utility against different task input data sizes (Dusm) or workloads (Cusm).
(a)
The system utility with different input data sizes (Dusm)(b)
The system utility with different workloads (Cusm)From Figure4, the proportion of offloading users decreases, as the number of user increases. This is mainly because the capacity of computing resources and the RBs assigned to each offloaded users decreases, as the number of users increases. Therefore, more tasks tend to be processed locally. In addition, the proportion of offloaded users will increase with the larger number of RBs in the network.Figure 4
The relationship between the proportion of offloaded UEs and the number of UEs.The number of offloading UEs under different computing power is analyzed, as shown in Figure5. It can be seen that the number of users offloaded by the TOWCRM and hJTORA algorithms is increasing with the enhancement of computing power. Because the computing power of MEC is stronger, the computation time of the offloading tasks becomes shorter. Therefore, more UEs will tend to offload their tasks to the MEC server to be processed. Moreover, under the same computing power of the MEC server, the number of UEs offloaded by the proposed algorithm is generally higher than that by using hJTORA.Figure 5
Comparison of the number of UEs offloaded against different MEC computing power.Figure6 shows the total time for finishing all offloading tasks and energy consumption obtained using TOWCRM when UEs’ preferences to time of βusmt vary from 0.1 to 0.9. It can be seen that the time is reduced, and the energy consumption is increased as βusmt becomes larger. In addition, when the number of users in the system increases, the total time and energy consumption of users will be increased. This is because when more users participate in the competition for limited resources, a longer delay and higher energy consumption of all offloading UEs will occur.Figure 6
Time and energy consumption of all users obtained using TOWCRM.


## 7. Conclusion

In this article, the scenario of a multicell and multiuser mobile-edge computing network is modeled and analyzed. The optimization of the user utility and the system utility is formulated by combining task offloading and wireless and computing resource management. The original problem is decomposed into resource block allocation (RBA), computing resource allocation (CRA), and task offloading decision. The RBA is solved by using a resource allocation algorithm based on an improved graph coloring method. The optimal solution of CRA is obtained by using KKT conditions. In task offloading, a semi-distributed TOWCRM strategy is proposed to optimize the system utility under the constraints of computing resources. Simulation results show the effectiveness of the scheme under different system parameters. The transmission power of every user is considered a fixed value and is equal to each other for wireless resource allocation in this work. The power control of each user will be studied to improve the system utility in the next research work.



---

*Source: 8288836-2021-11-11.xml*