# Task Allocation Optimization Scheme Based on Queuing Theory for Mobile Edge Computing in 5G Heterogeneous Networks

Authors: Jianbin Xue; Zesen Wang; Yonggang Zhang; Lu Wang
Journal: Mobile Information Systems
 (2020)

---

## Abstract

As an indispensable key technology in 5G Internet of Things (IoT), mobile edge computing (MEC) provides a variety of computing and services at the edge of the network for energy-limited and computation-constrained mobile devices (MDs). In this paper, we use the multiaccess characteristics of 5G heterogeneous networks and queuing theory. By considering the heterogeneity of base stations, we establish the waiting and transmission consumption model when tasks are offloaded. Then, the problem of jointly optimizing the energy and delay consumption of MDs is proposed. We adopt an optimization scheme based on task assignment probability; moreover, the task assignment algorithm based on quasi-Newton interior point (TA-QNIP) method is developed to solve the optimization issue. Compared with the Newton interior point algorithm, the proposed algorithm accelerates the convergence speed and reduces the complexity of the algorithm and is closer to the objective function optimal solution. The simulation results demonstrate that the proposed method can reduce the total consumption of MDs effectively; furthermore, the performance of the algorithm is proved.


---

## Body

## 1. Introduction

With the widespread deployment of Internet of Things (IoT) in 5G era [1], mobile applications such as natural language processing, virtual reality, and interactive games have greatly enriched our lives [2]. However, mobile devices (MDs) with constrained computing power and battery capacity could not handle the huge amount of data generated by mobile applications [3, 4]. To avoid this mismatch of resources, researchers have come up with various cloud-based solutions [5]. By utilizing the abundant resources in the center cloud, the computing intensive tasks of mobile applications can be offloaded, thus reducing the workload of IoT devices (smart furniture, smart glasses, and industrial sensor, etc. [6]) and shortening the computing delay [7]. However, due to the multihop structure of the core network, the delay between the MDs and the center cloud is too long. If a lot of IoT devices request cloud services from the same node at the same time, the backhaul link will be heavily burdened [8].In order to alleviate the burden of the core network, mobile edge computing (MEC) is gradually proposed and brings cloud computing functions to the edge of the network [9]. With the help of MEC, MDs can offload tasks to the edge of the network, instead of using servers located in the center of the network which is far away from MDs [10]. This greatly improves the offloading efficiency of the device, while reducing the energy consumption of the device and shortening the backhaul delay [11].In recent years, with the progress of 5G communication, MEC based on 5G architecture has been studied by many scholars [12–16]. In the 5G network, a heterogeneous network composed of a macro base station and a small base station is a common form of 5G architecture [17]. Since the macro base station and the small base station are located at different locations and the configured hardware levels are different, they have different effects in the small cell network. Therefore, our goal is to improve the offloading efficiency of MEC in 5G environments by considering the performance differences of the base stations.The MD has the offloading decision right. The question of whether, how much, and what to offload is determined by monitoring various parameters through the terminal system parser, such as the size of the data to be offloaded, the time delay caused by the offloading task, or the amount of energy required to execute locally. Compared with the deterministic task model, the average energy consumption and execution latency of the stochastic task model system have a stronger correlation, so designing an efficient computation offloading scheme is more challenging. Therefore, compared with the computation offloading optimization scheme of the deterministic task model, the design of MEC systems with random task arrival is a less explored field.Aiming at the problem of MDs’ consumption in MEC, this paper designs a task offloading scheme with base station collaboration based on 5G heterogeneous networks. The purpose of this scheme is to improve the low efficiency of task offloading caused by congestion. Different from the existing literature which only optimizes the delay or energy consumption, this paper reduces the overall consumption of MDs by optimizing the energy and delay consumption of MDs jointly. The contributions and innovations of this paper are as follows:(i)
In this paper, a base station cooperative task offloading scheme based on 5G heterogeneous networks is designed. By using queuing theory, the waiting energy and delay consumption of tasks to be offloaded are considered jointly; in addition, the offloading decision problem is transformed into the task assignment probability problem.(ii)
The optimization goal of the MDs-centered energy and delay consumption minimization is established. Then, the joint optimization of the total consumption of MDs with different demands on delay and energy consumption is accomplished by allocating the task assignment probability.(iii)
In order to solve the problem of consumption minimization, the task assignment algorithm based on quasi-Newton interior point (TA-QNIP) method is proposed. In addition, the complexity of the proposed algorithm is discussed and the convergence performance is verified.The rest of this paper is arranged as follows: we summarize the related work in Section2. Section 3 establishes a complete system model. In Section 4, we formulate the optimization problem of minimizing the energy and delay consumption of MDs. In Section 5, the Newton algorithm is briefly introduced; accordingly, the TA-QNIP method is proposed, and then we analyze the algorithm complexity. Simulation results are discussed in Section 6. Finally, we summarize the work of the full text in Section 7.


## 2. Related Work

At present, there are some related works focusing on MEC under 5G architecture. Wang et al. [12] improved system revenue by jointly optimizing computation offloading, resource allocation, and content caching. Zhang et al. studied how to decrease the computation offloading delay of the MEC system in 5G architecture [13]. In order to meet the key requirements of 5G networks for low latency and high reliability, the authors in [18, 19] proposed a joint optimization problem for computation offloading of MEC systems based on delay and reliability. However, the above works did not take into account the basic characteristics of the multiaccess feature of the 5G architecture. Combining the multiaccess characteristics of 5G heterogeneous networks, Zhang et al. [10] proposed the MEC energy-efficient computing offload mechanism in 5G heterogeneous networks, which effectively reduced energy consumption through joint optimization of offloading strategies and cellular network resource allocation. Considering the constraints of computing ability and service delay requirements, Yang et al. [4] developed an energy optimization scheme based on artificial fish swarm algorithm to minimize the entire energy consumption of the system. The above works have achieved good results in the optimization of system energy consumption when using the 5G multiaccess feature to design scheme, but the optimization of task processing delay is not considered at the same time.Recent survey [20] has shown that there are two types of computation offloading: binary offloading and partial offloading. Computing tasks cannot be divided into subtasks in binary offloading. The entire task must be executed on the local or MEC servers [21, 22], thus reducing the flexibility of the task processing in practical application environments. However, in partial offloading, subtasks can choose different offloading ways based on different processing requirements and optimal system efficiency [20]. In view of task separability, Guan et al. [23] designed an efficient task offloading scheme for IoT based on cooperative communication in the mobile cloud computing system. Pang et al. [24] studied the problem of delay-driven collaborative task calculation in fog wireless access network. Although previous research studies make good use of the separability of the task to establish a model, but did not fully utilize the small cell heterogeneous network characteristics under the 5G architecture.Applying queuing theory to MEC is the focus of scholars in recent years. In [25, 26], the energy consumption, execution delay, and price cost of the offloading process in the MEC system are studied in depth by using queuing theory. The authors in [27] based on Lyapunov optimization developed an online algorithm and the theoretical boundary of the algorithm in terms of average power consumption and average queue length was proved. In [28], different queue models were applied to study the energy cost and delay performance, and the optimal solution was solved by the semismooth Newton method of Armijo line search. Yang et al. [29] used a probabilistic optimization scheme to jointly optimize energy costs and packet congestion and effectively controlled congestion of edge servers by grouping with different priorities. Li [30] established a queuing model for one MD and multiple heterogeneous edge servers, and in the past work, the heterogeneity of the edge server was introduced for the first time to study the optimization of the computational offload strategy. The authors in [31] established three different queue models based on MD, cloudlet, and central cloud and then conducted in-depth research on the optimization of energy consumption and execution delay of cloudlet-assisted task offloading. However, the previous works did not consider the impact of congestion caused by the bearer capacity of the base station on the MEC system.Different from previous studies, under the 5G MEC heterogeneous networks, we proposed the object that jointly optimizing the energy and delay consumption of MDs. Through queuing theory, we comprehensively considered the differences of heterogeneous base stations and established the waiting consumption and transmission consumption model during task offloading. A task assignment algorithm based on quasi-Newton interior point method is proposed. MDs can reasonably assign offloading tasks according to the congestion degree of the system to minimize the total consumption. Finally, the complexity of the proposed algorithm is discussed and the convergence is verified.


## 3. System Model

In this part, we first establish the system model, including network model, local model, transmission model, and edge cloud model, and then, the problem model to be optimized is established.


### 3.1. Network Model

In the edge cloud network, the processing tasks generated by each MD can be executed locally or offloaded to the MEC server for computing. In order to save energy consumption and shorten time delay, we design an uncertain task offloading model based on queuing theory. As shown in Figure1, we consider a set of MDs in the system, which is denoted by MDi (i = 1, 2, 3 … N), a macro base station (MBS) equipped with MEC servers and a small base station (SBS). The MBS and SBS are connected by a fiber link. Due to the different types of tasks generated by each MD, the generated task requests are random. We assume that a task consists of multiple subtasks. In general, the computing tasks randomly generated by MDs can be processed locally, or some tasks can be offloaded to MEC servers through MBS for processing. In this model, MDs can also offload some tasks to MEC servers through SBS, thus reducing the processing pressure of MBS. Based on the queuing theory [32], we consider that the processing model of the local is the M/M/1 queue, and the model of the task transmission is the M/M/c queue. Figure 2 shows the task queuing process. Suppose the task generation rate of the MDi is λi (measured by the number of generation tasks on per unit of time, e.g., second), the size of request data is θi. The probability that the task generated by the MDi is locally executed is pil, the probability that the task is processed by the edge cloud is pic, and pim and pis are the probability that the MDi offloads the task through the macro base station and the probability that the task is offloaded through the small base station, respectively, where pic=pis+pim. Due to the nature of Poisson distribution, we assume that the service request offloaded to the MEC servers follows the Poisson process with an average rate of picλi, and the locally processed service request follows the Poisson process with an average rate of pilλi.Figure 1
Base station cooperative task offloading model based on 5G heterogeneous networks.Figure 2
Queuing model of task request processing.


### 3.2. Local Model

The consumption of MDs performing tasks locally is divided into two parts: computation and task response consumption. In order to simplification, we only consider the task response consumption.uiD represents the execution capability of MDi, and liD represents the proportion of CPU occupied by MDi. Since the generation of tasks is distributed negatively exponentially, the task processing model is considered to be M/M/1 queue on the MD side. By Little’s Law [33], the local task response time is T=1/u/1−η, and the queuing efficiency is η=λ/u, where λ and u are task arrival rate and device service rate, respectively. Therefore, the average response time and energy consumption of locally executed tasks are as follows:(1)TiD=1uiD1−liD−pilλi,(2)EiD=ξiTiD=ξi1uiD1−liD−pilλi,where ξi represents the response energy consumption coefficient of MDi.


### 3.3. Transmission Model

In the edge heterogeneous network, in addition to MBS, the SBS is regarded as the cooperative base station within the MBS coverage. In order to effectively utilize the spectrum resources, both MBS and SBS work in the same frequency band [10]. It is assumed that the bandwidth of the channels in the system is the same, which is denoted by B. Since this paper mainly researches task assignment problems and alleviates system congestion, in order to simplify the model, we assume that the interference can be negligible because channels allocated to MDs for computation offloading are all orthogonal [34, 35]. Therefore, we can calculate the uplink transmission rate of the MDi offloading tasks to the MBS:(3)Rim=Blog21+PimHimσ2.Similarly, the uplink transmission rate of the MDi offloading tasks to the SBS is given by(4)Ris=Blog21+PisHisσ2,where σ2 is the Gaussian white noise power and Pim and Pis denote the transmission power of MDs to MBS and SBS, respectively. The transmission power can be determined by the power control mechanism of MBS and SBS [36]. In addition, Pimax is the maximum transmission power of the MDi, Hiis the channel gain between the MDi and base stations, Hi=127+30×logdi, and di is the distance between the MDi and base stations [37].For MBS and SBS, the maximum acceptable task arrival rate isλmaxm and λmaxs, respectively, and the sum of all task request rates from different MDs is expressed as follows:(5)λtotalm=∑i=1Nλipim,(6)λtotals=∑i=1Nλipis.Then, the actual task arrival rate on the MBS isλpm=minλtotalm,λmaxm, and the actual task arrival rate on the SBS is λps=minλtotals,λmaxs. Assume that the service rate of MBS is um and the service rate of SBS is us. According to the M/M/c queuing model definition, the queue strengths of the tasks to the MBS and the SBS are as follows:(7)ρm=λpmcum,(8)ρs=λpscus.Queue strength is a parameter to measure the stability of the system. Whenρm<1and ρs<1, the average amount of tasks arriving at the system is less than the average amount of tasks leaving the system; therefore, the task waiting time will not be too long caused by the lengthy queue, and at this time, the system is stable. In order to offload computing tasks to the MEC servers, wireless uplink transmissions generate extra energy and delay overhead. The total transmission time includes the transmission time of the uplink and the waiting time for the task to be offloaded. Therefore, when the MDi offloads its tasks to the MEC servers through MBS, the transmission delay and energy consumption can be calculated as follows:(9)TimPim=pimλiθiRim+Wim=pimλiθiBlog21+PimHim/σ2+Wim,(10)EimPim=PimTimPim=PimpimλiθiRim+γiWim=PimpimλiθiBlog21+PimHim/σ2+γiWim,where γiis the waiting energy coefficient of MDi. Similarly, when MDi offloads its tasks to MEC servers through SBS, the transmission delay and energy consumption can be calculated as follows:(11)TisPis=pisλiθiRis+Wis=pisλiθiBlog21+PisHis/σ2+Wis,(12)EisPis=PisTisPis=PispisλiθiRis+γiWis=PispisλiθiBlog21+PisHis/σ2+γiWis,where Wim is the waiting time for the task generated by the MDi to be offloaded to MBS. According to the Little formula, the queuing system with an average arrival rate of λ, in the average sense, the waiting time under the M/M/c queuing system is as follows:(13)Wim=Lqmum=cρmc−1ρm/c!1−ρm2p0mum,where the idle probability of MBS is as follows:(14)p0m=∑k=0c−1cρmkk!+cρmcc!1−ρm−1.Similarly, the waiting time for the task generated by MDi to be offloaded to SBS is given by(15)Wis=Lqsus=cρsc−1ρs/c!1−ρs2p0sus,where the idle probability of SBS is as follows:(16)p0s=∑k=0c−1cρskk!+cρscc!1−ρs−1,where Lqm and Lqs are the average waiting queue length of the task. In addition, the backhaul link rate between SBS and MBS is much higher than that of the wireless link, so the rest of the paper simply omits the backhaul delay [29].


### 3.4. Edge Cloud Model

After receiving the offloaded task, the MEC server performs the calculation immediately. The maximum workload of the MEC system is limited to the maximum receiving rate, which is expressed asλmaxc. In the system, the total request rate from different MDs is expressed as follows:(17)λtotalD=∑i=1Nλipic=∑i=1Nλpmpim+λpspis.When the MEC servers perform the offloading task completely, the calculated result will be returned to the MD. We omit the time and energy consumption of MDs to receive and process the result, which is similar to [38].


## 3.1. Network Model

In the edge cloud network, the processing tasks generated by each MD can be executed locally or offloaded to the MEC server for computing. In order to save energy consumption and shorten time delay, we design an uncertain task offloading model based on queuing theory. As shown in Figure1, we consider a set of MDs in the system, which is denoted by MDi (i = 1, 2, 3 … N), a macro base station (MBS) equipped with MEC servers and a small base station (SBS). The MBS and SBS are connected by a fiber link. Due to the different types of tasks generated by each MD, the generated task requests are random. We assume that a task consists of multiple subtasks. In general, the computing tasks randomly generated by MDs can be processed locally, or some tasks can be offloaded to MEC servers through MBS for processing. In this model, MDs can also offload some tasks to MEC servers through SBS, thus reducing the processing pressure of MBS. Based on the queuing theory [32], we consider that the processing model of the local is the M/M/1 queue, and the model of the task transmission is the M/M/c queue. Figure 2 shows the task queuing process. Suppose the task generation rate of the MDi is λi (measured by the number of generation tasks on per unit of time, e.g., second), the size of request data is θi. The probability that the task generated by the MDi is locally executed is pil, the probability that the task is processed by the edge cloud is pic, and pim and pis are the probability that the MDi offloads the task through the macro base station and the probability that the task is offloaded through the small base station, respectively, where pic=pis+pim. Due to the nature of Poisson distribution, we assume that the service request offloaded to the MEC servers follows the Poisson process with an average rate of picλi, and the locally processed service request follows the Poisson process with an average rate of pilλi.Figure 1
Base station cooperative task offloading model based on 5G heterogeneous networks.Figure 2
Queuing model of task request processing.


## 3.2. Local Model

The consumption of MDs performing tasks locally is divided into two parts: computation and task response consumption. In order to simplification, we only consider the task response consumption.uiD represents the execution capability of MDi, and liD represents the proportion of CPU occupied by MDi. Since the generation of tasks is distributed negatively exponentially, the task processing model is considered to be M/M/1 queue on the MD side. By Little’s Law [33], the local task response time is T=1/u/1−η, and the queuing efficiency is η=λ/u, where λ and u are task arrival rate and device service rate, respectively. Therefore, the average response time and energy consumption of locally executed tasks are as follows:(1)TiD=1uiD1−liD−pilλi,(2)EiD=ξiTiD=ξi1uiD1−liD−pilλi,where ξi represents the response energy consumption coefficient of MDi.


## 3.3. Transmission Model

In the edge heterogeneous network, in addition to MBS, the SBS is regarded as the cooperative base station within the MBS coverage. In order to effectively utilize the spectrum resources, both MBS and SBS work in the same frequency band [10]. It is assumed that the bandwidth of the channels in the system is the same, which is denoted by B. Since this paper mainly researches task assignment problems and alleviates system congestion, in order to simplify the model, we assume that the interference can be negligible because channels allocated to MDs for computation offloading are all orthogonal [34, 35]. Therefore, we can calculate the uplink transmission rate of the MDi offloading tasks to the MBS:(3)Rim=Blog21+PimHimσ2.Similarly, the uplink transmission rate of the MDi offloading tasks to the SBS is given by(4)Ris=Blog21+PisHisσ2,where σ2 is the Gaussian white noise power and Pim and Pis denote the transmission power of MDs to MBS and SBS, respectively. The transmission power can be determined by the power control mechanism of MBS and SBS [36]. In addition, Pimax is the maximum transmission power of the MDi, Hiis the channel gain between the MDi and base stations, Hi=127+30×logdi, and di is the distance between the MDi and base stations [37].For MBS and SBS, the maximum acceptable task arrival rate isλmaxm and λmaxs, respectively, and the sum of all task request rates from different MDs is expressed as follows:(5)λtotalm=∑i=1Nλipim,(6)λtotals=∑i=1Nλipis.Then, the actual task arrival rate on the MBS isλpm=minλtotalm,λmaxm, and the actual task arrival rate on the SBS is λps=minλtotals,λmaxs. Assume that the service rate of MBS is um and the service rate of SBS is us. According to the M/M/c queuing model definition, the queue strengths of the tasks to the MBS and the SBS are as follows:(7)ρm=λpmcum,(8)ρs=λpscus.Queue strength is a parameter to measure the stability of the system. Whenρm<1and ρs<1, the average amount of tasks arriving at the system is less than the average amount of tasks leaving the system; therefore, the task waiting time will not be too long caused by the lengthy queue, and at this time, the system is stable. In order to offload computing tasks to the MEC servers, wireless uplink transmissions generate extra energy and delay overhead. The total transmission time includes the transmission time of the uplink and the waiting time for the task to be offloaded. Therefore, when the MDi offloads its tasks to the MEC servers through MBS, the transmission delay and energy consumption can be calculated as follows:(9)TimPim=pimλiθiRim+Wim=pimλiθiBlog21+PimHim/σ2+Wim,(10)EimPim=PimTimPim=PimpimλiθiRim+γiWim=PimpimλiθiBlog21+PimHim/σ2+γiWim,where γiis the waiting energy coefficient of MDi. Similarly, when MDi offloads its tasks to MEC servers through SBS, the transmission delay and energy consumption can be calculated as follows:(11)TisPis=pisλiθiRis+Wis=pisλiθiBlog21+PisHis/σ2+Wis,(12)EisPis=PisTisPis=PispisλiθiRis+γiWis=PispisλiθiBlog21+PisHis/σ2+γiWis,where Wim is the waiting time for the task generated by the MDi to be offloaded to MBS. According to the Little formula, the queuing system with an average arrival rate of λ, in the average sense, the waiting time under the M/M/c queuing system is as follows:(13)Wim=Lqmum=cρmc−1ρm/c!1−ρm2p0mum,where the idle probability of MBS is as follows:(14)p0m=∑k=0c−1cρmkk!+cρmcc!1−ρm−1.Similarly, the waiting time for the task generated by MDi to be offloaded to SBS is given by(15)Wis=Lqsus=cρsc−1ρs/c!1−ρs2p0sus,where the idle probability of SBS is as follows:(16)p0s=∑k=0c−1cρskk!+cρscc!1−ρs−1,where Lqm and Lqs are the average waiting queue length of the task. In addition, the backhaul link rate between SBS and MBS is much higher than that of the wireless link, so the rest of the paper simply omits the backhaul delay [29].


## 3.4. Edge Cloud Model

After receiving the offloaded task, the MEC server performs the calculation immediately. The maximum workload of the MEC system is limited to the maximum receiving rate, which is expressed asλmaxc. In the system, the total request rate from different MDs is expressed as follows:(17)λtotalD=∑i=1Nλipic=∑i=1Nλpmpim+λpspis.When the MEC servers perform the offloading task completely, the calculated result will be returned to the MD. We omit the time and energy consumption of MDs to receive and process the result, which is similar to [38].


## 4. Problem Formulation

In the 5G MEC network environment, under the conditions of meeting the maximum task arrival rate limit and task assignment probability constraints, and comprehensively considering the waiting consumption of MDs, we propose the problem of minimizing the delay and energy consumption of MDs based on multi-base station cooperation. Similar to the work in reference [39], the total delay consumption of the user's task processing can be obtained:(18)Tipil,pim,pis=TiDpil+Timpim+Tispis,and the total energy consumption of task processing can be obtained:(19)Eipil,pim,pis=EiDpil+Eimpim+Eispis.Therefore, in the system, the average execution delay and energy consumption of MDs are expressed as follows:(20)Tpil,pim,pis=∑i=1NTipil,pim,pis,(21)Epil,pim,pis=∑i=1NEipil,pim,pis.Since this paper considers the multiobjective optimization of MDs' energy and delay consumption, the transmission consumption between base stations is ignored. Considering that MEC servers have powerful computing ability, the computing energy and delay consumption of the MEC are ignored in this paper. Therefore, the objective function and the restriction conditions are as follows:(22)P1:minpil,pim,pisTpil,pim,pis,Epil,pim,pis,C1:pilλi<uiD1−liDi=1,2,3…N,C2:λtotalD<λmaxc,C3:0≤Pim+Pis≤Pimaxi=1,2,3…N,C4:pis+pim+pil=1i=1,2,3…N,C5:pil>0,pim>0,pis>0i=1,2,3…N,C6:∑i=1Nλipim<λmaxmi=1,2,3…N.C7:∑i=1Nλipis<λmaxsi=1,2,3…N.Here,C1 indicates that the local arrival rate of the task should be less than the remaining execution capacity of the local device. C2 ensures that the total task arrival rate offloaded to the edge cloud system does not exceed the maximum acceptable rate of the servers. When MDs offload the task, the transmit power strength should satisfy C3. The probability of offloading in different ways for different tasks should meet C4 and C5. C6 and C7 prevent the base station from being overloaded and maintain the stability of the system.Notice that P1 is a multiobjective nonlinear optimization problem with multiple constraints. In order to satisfy the different demands of MDi in various application environments, we introduce the delay weight factor α, and then the energy consumption weight factor is 1−α, where 0≤α≤1, so P1 can be transformed into the following form:(23)P2:minpil,pim,pisαTpil,pim,pis+1−αEpil,pim,pis,subject to C1∼C7, where(24)T=∑i=1N1uiD1−liD−pilλi+∑i=1NpimλiθiBlog21+PimHim/σ2+Wim+∑i=1NpisλiθiBlog21+PisHis/σ2+Wis,E=∑i=1Nξi1uiD1−liD−pilλi+∑i=1NPimpimλiθiBlog21+PimHim/σ2+γiWim+∑i=1NPispisλiθiBlog21+PisHis/σ2+γiWis.


## 5. Problem Solution through TA-QNIP Method

The interior point method is an optimization algorithm for solving the constraint problem. The basic idea is to convert the constraint optimization problem into the nonconstrained problem by introducing a penalty function method and then use the nonconstrained optimization method to iteratively solve the target value and continuously update the penalty function, then approach the optimal solution of the objective function. Since the Newton algorithm has the advantages of fast convergence, etc., when the interior point method is applied in the past work, most of the optimization iterative processes adopt the Newton method. The flow of the Newton algorithm is shown in Algorithm1.Algorithm 1: Newton algorithm
(1)
Initial feasible pointx0, define ε as a sufficiently small positive real number, k=0.(2)
Calculategk and Hk.(3)
Ifgk<ε,it should stop iterating;elsedetermine the search directionqk=−Hk−1⋅gk(4)
Calculate next iteration points:xk+1=xk+qk(5)
k=k+1 and turn to step 2.wheregk is the gradient vector of the objective function, Hk−1 is the inverse of the Hessian matrix, and the Newton iteration direction is qk=−Hk−1⋅gk. Each iteration of the Newton algorithm needs to solve the inverse of the Hessian matrix of the objective function, so that the calculation is complicated.In this paper, the quasi-Newton method is used to solve the optimization problem, and different objective functions can be solved by different quasi-Newton methods [40]. In order to solve this nonlinear optimization problem better, we adopt quasi-Newton algorithm based on Broyden–Fletcher–Goldfarb–Shanno optimization algorithm (BFGS) with the best performance to design the TA-QNIP method. Through the interior point method, the constraint problem is transformed into an unconstrained problem at first. By adopting the BFGS quasi-Newton optimization algorithm to approximate the optimal value and using the gradient vector information, a positive definite symmetric matrix that approximates the Hessian matrix is constructed. Because it is not necessary to solve the second partial derivative of the objective function, the difficulty in the calculation is greatly reduced. Therefore, the P2 can be transformed into a nonconstraint problem of minimizing penalty function:(25)P3:minpil,pim,pis,∇kϕpil,pim,pis,∇k,where the penalty function can be expressed as follows:(26)ϕpil,pim,pis,∇k=αTpil,pim,pis+1−αEpil,pim,pis−∇kln∏i=1NuiD1−liD−pilλi−∇klnλmaxc−∏i=1Nλipim+pis−∇kln∏i=1NPimax−Pim−Pis−∇kln∏i=1Npil−∇kln∏i=1Npim−∇kln∏i=1Npis−∇kln∏i=1Nλmaxm−∑i=1Nλipim−∇kln∏i=1Nλmaxs−∑i=1Nλipis+1∇k∏i=1N1−pil−pim−pis2.In the penalty function, when the arbitrary solutionpil0,pim0,pis0i=1N approaches the constraint boundary, the function value will increase rapidly, forcing the optimal value to be solved within the feasible domain. ∇k>0 (k  = 0, 1, 2 …) is penalty factor, it is a decreasing coefficient, and the reduction factor is set to Γ. Then, the penalty factor can be denoted as ∇k+1=Γ∇k (k  = 0, 1, 2 …), where pil∇k,pim∇k,pis∇ki=1N is the extreme point obtained by the penalty function under the TA-QNIP method. We express gk as the gradient vector of the objective function and Dk as the approximate matrix of the inverse of the Hessian matrix of the objective function, so that the search direction is qk=−Dk⋅gk. When solving Dk, we first need to derive the quasi-Newton conditions that the approximate matrix of the Hessian matrix needs to satisfy. Let the objective function be fℙ, ℙ is the set of solutions, and then expand the Taylor series of fℙ at ℙ=ℙk+1, that is:(27)fℙ=fℙk+1+f′ℙk+1ℙ−ℙk+1+12ℙ−ℙk+1Tf″ℙk+1ℙ−ℙk+1+Rnℙ≈fℙk+1+f′ℙk+1ℙ−ℙk+1+12ℙ−ℙk+1Tf″ℙk+1ℙ−ℙk+1.Take the first-order partial derivative offℙ:(28)f′ℙ≈f′ℙk+1+f″ℙk+1ℙ−ℙk+1,Whenℙ=ℙk, we can obtain: f′ℙk=f′ℙk+1+f″ℙk+1ℙk−ℙk+1. Through conversion, we can get: gk=gk+1+Hk+1ℙk−ℙk+1, that is, gk+1−gk=Hk+1ℙk+1−ℙk. To facilitate the definition, we set(29)yk=gk+1−gk,(30)sk=ℙk+1−ℙk,(31)Bk+1≈Hk+1,(32)Dk+1≈Bk+1−1,where Bk+1 is the approximation of the Hessian matrix and Dk+1 is the approximation of the inverse matrix Hk+1−1 of the Hessian matrix, then(33)yk=Bk+1sk,(34)sk=Dk+1yk.The above formula is the quasi-Newton condition, which constrains the approximation of the Hessian matrix in the iteration. Then, we construct an approximation matrix that satisfies the quasi-Newton condition by the BFGS method instead of the original Hessian matrix. Let the iterative formula of the approximate Hessian matrix be(35)Bk+1=Bk+ΔBk.LetΔBk=αuuT+βvvT, where vectors u and v are undetermined vectors, and their dimensions are n×1 (n is the dimension of ℙ). The variable quantity of matrix obtained by this way must be symmetric matrix; then(36)yk=Bk+1sk=Bk+αuuT+βvvTsk=Bksk+αuTsku+βvTskv.LetαuTsk=1, βvTsk=−1, then we have yk−Bksk=u−v; let u=yk and v=Bksk, we get α=1/ykTsk, β=−1/skTBkTsk. Finally, the correction matrix is obtained:(37)ΔBk=αuuT+βvvT=1ykTskuuT−1skTBkTskvvT=ykykTykTsk−BkskskTBkTskTBkTsk.The above formula can be replaced byBk+1=Bk+ykykT/ykTsk−BkskskTBkT/skTBkTsk. We introduce the identity matrix I, by using Sherman–Morrison formula, and the above equation can be converted into Bk+1−1=I−skykT/ykTskBk−1I−ykskT/ykTsk+skskT/ykTsk, that is:(38)Dk+1=I−skykTykTskDkI−ykskTykTsk+skskTykTsk.Thus, the inverse of the Hessian matrix is avoided in every iteration, and the difficulty in the calculation is greatly reduced. By iterating the correction matrix many times, the optimal search direction is changed continuously, and the approximate optimal solutionpil∗,pim∗,pis∗i=1N is obtained. The task assignment algorithm based on quasi-Newton interior point method is shown in Algorithm 2.Algorithm 2: Task assignment algorithm based on quasi-Newton interior point method
(1)
Input:Initialize the feasible point1−pim−pis0,pim0,pis0i=1N, initialize the penalty coefficient ∇0, set the dropping factor Γ, k=0, D0=I.(2)
Defineε1 and ε2 as a sufficiently small positive real number, where ε1>ε2.(3)
Determine search directionqk=−Dk⋅gk.(4)
Find the optimal step factor:ℓk=argminℓ∈Rϕ1−pim−pis∇k,pim∇k,pis∇ki=1N+ℓqksk=ℓkqk1−pim−pis∇k+1,pim∇k+1,pis∇k+1i=1N=1−pim−pis∇k,pim∇k,pis∇ki=1N+sk(5)
Iteration:Whilegk+1>ε1doyk=gk+1−gkDk+1=I−skykT/ykTskDkI−ykskT/ykTsk+skskT/ykTskk=k+1Go to step 4end whileoutput1−pim−pis∇k,pim∇k,pis∇ki=1N(6)
Set the algorithm termination condition:while1−pim−pis∇k,pim∇k,pis∇ki=1N−1−pim−pis0,pim0,pis0i=1N>ε2doIteration:∇k+1=Γ∇k (k = 0, 1, 2, …)1−pim−pis0,pim0,pis0i=1N=1−pim−pis∇k,pim∇k,pis∇ki=1N, k=k+1end while(7)
Return:1−pim−pis∇k,pim∇k,pis∇ki=1N(8)
Outputpil∗,pim∗,pis∗i=1N is the approximate optimal solution of the objective function.


### 5.1.∗Algorithm Complexity Analysis

The service difference between base stations will affect the offload probability, and the number of MDs and base stations will affect the algorithm complexity. In the two comparison algorithms in this paper, they both use the interior point method to set the penalty function and transform the constraint problem into a nonconstraint problem. When the task assignment algorithm based on Newton interior point (TA-NIP) method solves the optimal value in a nonconstrained problem, in order to find the optimal search direction, the Hessian matrix of the objective function must be solved first, and the inverse of the Hessian matrix of the objective function is calculated. The calculation complexity is exponential order. However, the TA-QNIP method proposed in this paper only needs to construct an approximate matrix to represent the inverse of the Hessian matrix, thereby reducing the complexity of the algorithm. In the complexity analysis, the first-order operation of matrix is ignored and the second-order operation of matrix is considered. LetN be the number of users, the number of base stations is 2, and k is the number of iterations. Then, the complexity of the TA-NIP method is O2N3∗k, and the complexity of the TA-QNIP method is O2N∗k.


## 5.1.∗Algorithm Complexity Analysis

The service difference between base stations will affect the offload probability, and the number of MDs and base stations will affect the algorithm complexity. In the two comparison algorithms in this paper, they both use the interior point method to set the penalty function and transform the constraint problem into a nonconstraint problem. When the task assignment algorithm based on Newton interior point (TA-NIP) method solves the optimal value in a nonconstrained problem, in order to find the optimal search direction, the Hessian matrix of the objective function must be solved first, and the inverse of the Hessian matrix of the objective function is calculated. The calculation complexity is exponential order. However, the TA-QNIP method proposed in this paper only needs to construct an approximate matrix to represent the inverse of the Hessian matrix, thereby reducing the complexity of the algorithm. In the complexity analysis, the first-order operation of matrix is ignored and the second-order operation of matrix is considered. LetN be the number of users, the number of base stations is 2, and k is the number of iterations. Then, the complexity of the TA-NIP method is O2N3∗k, and the complexity of the TA-QNIP method is O2N∗k.


## 6. Simulation Results

In this section, we evaluate the performance of the proposed TA-QNIP method through simulation results. At the same time, according to the simulation results, the advantages of the cooperative base station model are also proved. We consider that the distancedm between MBS and MDs is 1000 m, and the distance ds between SBS and MDs is 50 m [34]. The task generation rate of the device λi satisfies [0.1, 1.1] MB/s and the task size randomly generated by each device is θi = [2.5, 5] MB [41]. Local device execution capability is uiD = 0.5 GHz [10], and the CPU occupied proportion liD of MDi is randomly selected in [0, 1]. The response power coefficient of MDi is set atξi  = 0.1, and MDi's waiting power coefficient is γi=0.01 [42]. The channel bandwidth B  = 5 MHz [4], Gaussian white noise power σ2 = -127 dbm, and the transmission power Pim and Pis of the MD are randomly selected in [0.2, 0.3] w. In the following simulation analysis, we use “total consumption” to represent the sum of energy and delay consumption when MDs process the task under different energy and delay consumption demands. Because the total consumption reflects the cost of delay and energy consumption when MDs process the task, there is no specific unit, and it is only expressed in the simulation environment.Figures3 and 4 reflect the convergence of the TA-QNIP method and the TA-NIP algorithm. To facilitate the research, we discuss the convergence of the algorithm at ρ<0.8 and α=0.5. Figure 3 shows the influence of the number of MDs on the iterations; when the algorithm precision is 10−5, the iterations of the two algorithms increase with the increase of the number of MDs, but the TA-QNIP algorithm shows better convergence performance, especially when the number of MDs increases significantly. Figure 4 shows the effect of algorithm precision on the iterations when N=50, and it can be seen that, under different algorithm precision, the iterations of the proposed TA-QNIP algorithm are lower than those of the TA-NIP algorithm. Based on the verification of the above simulation results, the TA-QNIP algorithm has better convergence performance.Figure 3
The influence of the number of MDs on the iterations.Figure 4
The effect of algorithm precision on the iterations.As shown in Figure5, different schemes are applied to optimize the total consumption of MDs. In order to reflect the advantages of the proposed scheme in this paper, based on the TA-QNIP algorithm, the TA-NIP algorithm, random task assignment algorithm [4], and task assignment algorithm under a single base station were also proposed for analysis and comparison. It is noted that as the quantity of MDs increases, the trend of MDs’ total consumption will increase under different allocation algorithms. It shows that the total consumption of MDs optimized by the TA-NIP algorithm is slightly higher than that of the proposed algorithm because every step of the algorithm needs to solve the inverse matrix of the Hessian matrix of the objective function. When Hessian matrix is not positive, the correctness of the descent direction could not be guaranteed, so it could not converge at the approximate optimal solution. When using random task assignment algorithm, with the increase of MDs, the total consumption of MDs does not show stable optimization results. The reason is that random task assignment algorithm cannot produce a good allocation mechanism to ensure system performance, so the algorithm is the worst in the cooperative base station model. When applying the task assignment algorithm based on single base station, it can be seen that when the number of MDs is small, the single base station can meet the task requirements of fewer MDs at the same time, so the total consumption of MDs under the cooperative model is not much different. However, when the number of MDs increases, it is difficult for a single base station to meet the demands of multi-MD and multitask processing at the same time; therefore, compared with the cooperative model, the total consumption of MDs is more.Figure 5
The impact of the number of MDs.Figure6 shows the effect of total consumption on different queue strength. We discuss the situation when the delay weight coefficient α=0.5. It can be seen that the total consumption increases as the quantity of MDs increases. When the number of tasks is small, the allowable queue length does not reach saturation, and the tasks that need to be offloaded are successfully entered into the queuing sequence. Therefore, under the constraint of different allowable queue strength, the growth trend of total consumption is almost the same. It should be noted that, with the increase of the number of MDs, when the queue strength meets the limits of ρ<0.4 and ρ<0.6, respectively, the growth trend of the total MDs’ consumption is significantly faster than that of ρ<0.8, because the allowable queue length of the offloading task is reduced, and the tasks to be offloaded cannot successfully enter the queuing sequence, resulting in additional consumption due to system congestion.Figure 6
Effect of queue strength on the total consumption.Figure7 shows the influence of different delay weight coefficients α on the total consumption of MDs. It can be seen that when the number of MDs is constant, with the increase of delay weight and the decrease of energy consumption weight, the types of tasks that MDs need to process tend to be more sensitive to delay. Therefore, most tasks are executed on local devices, which will increase the overall cost of MDs. On the contrary, with the increase of energy consumption weight and the decrease of delay weight, it means that the target MDs pay more attention to the demand of energy consumption, so most tasks of MDs choose to be offloaded to the MEC for execution, thus reducing the total consumption of MDs.Figure 7
The influence of different weighting factors on the total consumption.


## 7. Conclusion

In this paper, a base station collaborative task offloading scheme in 5G MEC networks is established. First, we use queuing theory to model the process of task processing, and then the problem of minimizing the total consumption of MDs is formulated. We establish the probability-based optimization scheme. In order to solve the objective equation effectively, we propose the TA-QNIP method with lower computational complexity. Simulation results show that compared with the TA-NIP algorithm, the proposed algorithm can accelerate the convergence speed and reduce the total consumption of MDs more effectively. When the number of MDs and the task processing demands is massive, the proposed scheme is more effective. In addition, considering user task-intensive scenarios, this work can be extended to large-scale heterogeneous network for future research to greatly improve the offloading experience of user groups.



---

*Source: 1501403-2020-05-29.xml*