# Offloading Cost Optimization in Multiserver Mobile Edge Computing Systems with Energy Harvesting Devices

Authors: Zheng Liu; Kun Jiang; Xiuqiang Wu; Xianxiong Zeng
Journal: Wireless Communications and Mobile Computing
 (2022)

---

## Abstract

In mobile edge computing (MEC) systems with energy harvesting, edge devices are powered by unstable energy harvested from the environment. To prolong the lifetime of edge devices, some computing tasks should be offloaded to MEC servers. However, computing services offered by MEC servers may be very costly. In this work, we aim to minimize total costs caused by computing services and dropping tasks while avoiding the devices running out energy. With the consideration of the unpredictability of the harvestable energy, we adopt the stochastic Lyapunov optimization framework to jointly manage energy and make task execution decisions (i.e., local executing, offloading, or dropping tasks) and develop an online algorithm which could help asymptotically obtain the optimal results for the whole system. The algorithm does not require any knowledge of the harvestable energy and the statistics of task arriving processes and can be easily implemented in a distributed manner. Numerical results corroborate that the proposed algorithm can try its best to push battery energy of edge devices to a preset parameter and effectively reduce the service costs and task drops.


---

## Body

## 1. Introduction

In mobile edge computing systems, mobile applications such as face recognition, image identification, and augmented reality are usually computational-intensive and consume a large quantity of energy of edge devices [1–3]. Harvesting energy from the environment provides a promising solution to address energy scarcity problem in MEC systems. However, in many circumstances, the harvestable energy is usually unpredictable and not sufficient to support edge devices executing all computing tasks locally. Some computing tasks need to be offloaded to edge servers.Compared with edge devices, edge servers which are usually provided by service providers are more powerful and can assist edge devices to complete computing tasks nearby [4–6]. When edge devices offload their computing tasks to edge servers, there will be some service fee since it consumes bandwidth and computing resources of the servers [7, 8]. The service fee which is charged by service providers may be concerned to the types of tasks and can be time-varying. For example, the prices per bit of image identification may be different from augmented reality tasks, and when there are too many computing tasks being executed in a server, the service provider may raise the computation price of this server. For edge devices, more offloading means less energy consumption but more service costs. Hence, how to minimize service costs while guaranteeing edge devices never running out of energy will be a realistic problem.Many offloading techniques [9–15] have been proposed to minimize task execution latency and energy consumption or achieve the trade-off between them [16, 17]. However, in terms of energy management, most of those works focus on saving the energy cost of edge computing systems which may cause excessive computation offloading. Since the battery energy of edge devices can be constantly replenished in energy harvesting MEC systems, making full use of harvestable energy for local computation can effectively reduce data transfer and service overhead. Moreover, they do not take the cost of computation service into account, and most of them considered the problem from the perspective of static systems and single-user and single-server model.In this paper, we consider a more general scenario with multiple energy harvesting mobile edge devices and multiple MEC servers. The harvestable energy of each edge devices is different and unpredictable. Time is slotted, and computation tasks are delay sensitive and with the execution deadline no greater than the length of a time slot. We aim to find a task offloading strategy which jointly manage edge device energy and minimize the total costs resulted by computation offloading (i.e., service costs) and task dropping. With the consideration of the energy profile as a stochastic process, we adopt the Lyapunov optimization framework with weight perturbation to achieve long-term stability of energy queues of edge devices. Based on the theory of drift-plus-penalty, an online algorithm which can obtain the trade-off between energy performance (i.e., edge devices’ residual energy) and the total costs is developed. The algorithm makes greedy decisions in every time slot; hence, the complexity of the algorithm is low, and it can adapt to resource-constrained MEC systems very well. To summarize, the key contributions of this work are listed as follows:(1)
We consider both the heterogeneity and mobility of edge devices and model a MEC system with multiple energy harvesting edge devices and multiple MEC servers(2)
Instead of minimizing energy and delay costs, we define the total costs resulted by task offloading and dropping as the optimization object and formulate the computation offloading problem as a joint energy management and cost minimization problem(3)
We propose a low-cost computation offloading algorithm based on Lyapunov optimization framework to save the problem. This algorithm achieves nearly optimal costs meanwhile stabilizes the energy queues of edge devices and can be implemented in a distributed manner easilyThe rest of this article is organized as follows. In Section2, we conduct literature review. In Section 3, we present the system model and problem formulation. In Section 4, we present our algorithm and analysis. In Sections 5 and 6, we show the numerical results and conclude the article.


## 2. Related Work

In MEC systems, edge devices are allowed to offload some or all of the computation tasks to edge servers which releases the limited resources of mobile edge devices. However, due to the time-varying nature of wireless channels [18, 19], the mobility of edge devices, and the heterogeneity of computation intensive application tasks, the computation offloading and resource allocation problems remain challenging.There have been many works [9–15, 19–21] focus on developing offloading strategies to reduce the energy consumption and computation latency. Chen et al. [10] developed an offloading strategy based on a self-adaptive particle swarm optimization algorithm to reduce the system energy consumption for DNN-based smart IoT systems. Zhao et al. [12] proposed a task scheduling and partial offloading method to minimize the energy consumption of edge devices under a deadline constraint. Considering that the wireless channel state and task arrival process are uncertain and dynamic, Chen et al. [13] developed an online and polynomial-time-complexity algorithm based on Lyapunov optimization techniques aiming at minimizing average transmission energy consumption while guaranteeing the average queueing latency. Yang et al. [15] considered both the heterogeneity of edge servers and the mobility of mobile devices and proposed an optimal offloading node selection strategy based on changes in available network bandwidth and location of mobile devices to minimize the offloading time. However, those strategies are mainly presented to MEC systems without energy harvesting and need to be farther improved to take full use of the energy harvested from the environment.Energy harvesting technologies are supposed to be an efficient solution for MEC systems due to its self-sustainable nature [22, 23]. However, new challenges arise in jointly designing the energy management and offloading strategies since the harvestable energy is usually unpredictable in real world. Sun et al. [24] formulated the offloading problem in energy harvesting MEC systems as a joint minimization problem of energy consumption and delay in the long term and proposed a novel algorithm based on the reinforcement learning approach with noisy neural networks to solve the problem. Zhang et al. [25] proposed a continuous control-based deep reinforcement learning approach to minimize the execution time and energy consumption. Zhou et al. [26] proposed a Lyapunov optimization-based algorithm to minimize the time average of a weighted sum of energy consumption and execution delay meanwhile stabilize the battery energy queue. Most of those works simply use the minimization of energy consumption as one of the optimization objective and do not consider the costs of edge servers, which may lead those strategies offloading too much tasks to servers. At this point, the harvestable energy cannot be fully utilized, and the running mode of MEC systems is not fully characterized.


## 3. System Model and Problem Formulation

In this section, we introduce the system models for a mobile energy harvesting MEC system. The system containsM edge devices and N edge servers. We use M≜1,2,⋯,M and N≜1,2,⋯,N to denote edge devices (i.e., users) and edge servers, respectively. Time is slotted in this paper, and τ is the length of each time slot. The time slot index is t and t∈T, where T≜1,2,⋯. Edge devices keep traveling while edge servers are stationary. The distance between edge device m and edge server n is denoted by dm,nt.


### 3.1. Task Model

Computation tasks in this paper are delay-sensitive, and the execution deadline of those tasks is no greater than the length of each time slot. All the tasks generated by edge devicem are with fixed length Lm bits. Each edge devices may have a different Lm. Whether tasks are generated in time slot t is denoted by the binary variable ξmt. When ξmt=1, it means that there are tasks arriving on edge device m in time slot t and device m needs to make offloading decisions among local computing, task offloading, and dropping. ξmt is with an independently identical distribution (i.i.d.) Bernoulli process with Eξmt=λm, where 0≤λm≤1. Let ξt=ξmt,m∈M,t=0,1,2,⋯ be the task generation vector in time slot t.Denotexmlt, xm,nt, and xmdt be the decision variables of computation offloading. xmlt=1 and xmdt=1 indicated that the tasks are executed locally and dropped, respectively. xm,nt=1 indicated that edge device m chooses edge server n to offload tasks in time slot t. The computation offloading decision vector in time slot t can be defined as xt=xmlt,xmdt,xm,nt,m∈M&n∈N. In time slot t, device m offloads tasks to one server at most, which means ∑n=1Nxm,nt≤1. In every time slots, tasks must be executed locally, remotely, or dropped. Hence, when ξmt=1, we have
(1)xmlt+∑n=1Nxm,nt+xmdt=1.


### 3.2. Local Computation Model

Assume that it takescm CPU cycles for edge device m to process 1 bit of computing task; then, the local computation delay is
(2)Dmlt=cm·Lmfmt,where fmt is the CPU frequency in time slot t. Considering that tasks must be executed before the next time slot, the local computation delay should satisfy
(3)Dmlt≤τ.Assume that the dynamic voltage and frequency scaling technologies (DVFS) [27] are adopted in the edge devices, and the CPU frequencies scheduled for tasks remain the same in a single time slot. The computation power of local execution is
(4)pmlt=κfm3t,where κ is a parameter that depends on the chip architecture. According to (2) and (4), if there are tasks to execute locally, the computation energy is
(5)Emlt=Dmlt·pmlt=κ·cm·Lm·fm2t.Due to the limited computing power of CPU, the CPU frequency should satisfy(6)0≤fmt≤fmmax.


### 3.3. Offloading Computation Model

The data associated with the tasks to be offloaded to servers are transmitted over wireless links. Since MEC servers are usually equipped with high performance CPUS, we assume that the task execution time of MEC server can be ignored for convenience. We also assume that the output results of those tasks are of small sizes and the delay for returning the results back is negligible [26, 28, 29]. Let dm,nt be the distance between edge device m and edge server n in time slot t; then, the channel power gain can be calculated by
(7)gm,nt=γm,nt·g0·d0dm,ntψ,where γm,nt is the small-scale fading channel power gain, g0 is the channel loss coefficient, and d0 and ψ are reference distance and the channel loss exponent, respectively.According to Shannon theorem, the maximum uplink transmission rate betweenm and n can be expressed by
(8)rgm,nt,pm,nt=w·log21+gm,nt·pm,ntσ2,where σ2 is the noisy power and pm,nt is the transmission power of m in time slot t. The transmission delay of the offloading tasks between device m and n in time slot t can be computed by
(9)Dm,nt=Lmrgm,nt,pm,nt.Considering that the tasks must be finished before the end of the time slot and the transmission power of edge devices is limited, hence we have(10)Dm,nt≤τ,(11)pmmin≤pm,nt≤pmmax,where pmmax and pmmin are the maximum and minimum transmission power of edge device m. The energy consumption for m offloading those tasks to server n in time slot t is
(12)Em,nt=pm,nt·Dm,nt.


### 3.4. Energy Model

Since time is slotted in this paper, the process of energy harvesting is noncontinuous. Letemt be the harvestable energy in time slot t. We assume that emt is i.i.d and satisfies
(13)0≤emt≤Emhmax,where Emhmax is the maximum value of harvestable energy at each time slot. Let et=emt,m∈M be the energy arriving vector at time slot t.We denote the residual energy of devicem’s battery at the beginning of time slot t as Bmt and Bt=Bmt,m∈M be the residual energy vector at time slot t. Bm0 is set to 0J, and Bmt satisfies
(14)Bmt≤Bmmax,where Bmmax is the battery capacity of device m. To avoid running out of energy, the residual energy of edge devices should be stabilized. In a queueing network (e.g., a network with back-pressure routing), data queue is stable means that limT⟶∞sup1/T∑t=0T∑m=1MQmt<∞, where Qmt is the data queue of node m. However, we say that the energy queue of device m is stable if the following is met:
(15)limT⟶∞1T∑t=0TBmt≥θm−ε,where θm is the perturbation parameter of device m and ε is the gap between θm and the long-term average value of Bmt. θm can be set in the 0th time slot and should no less than V·α add the maximal energy which can be consumed by m in one slot [11]. V is the parameter trading off performance between energy and costs. Constraint (15) can effectively reduce the probability of running out of energy.For simplicity, we assume that energy consumption happens only in local computation and task offloading. Then, the residual energy ofm at time slot t is
(16)Bmt+1=minBmt−ξm·xmlt·Emlt−∑n=1Nxm,nt·Em,nt++emt,Bmmax,where x+=maxx,0. When ξmt=1 and there is not enough energy to offload or execute the tasks locally, the tasks will be dropped. Considering that emt is unpredictable, in order to guarantee the computation offloading decision can be executed, the residual energy should satisfy
(17)Bmt≥ξm·xmlt·Emlt+∑n=1Nxm,nt·Em,nt.


### 3.5. Problem Formulation

In our work, the primary goal is to minimize the total costs resulted by task offloading and dropping while guaranteeing the energy of the mobile device not be exhausted. Letcostn,mt be the price of servern computing one bit data for device m in time slot t and α>0 be the penalty of dropping tasks. Then, the total cost of the MEC system can be expressed as
(18)costt=∑m=1Mcostmt=∑m=1Mξm·∑n=1Nxm,ntcostn,mt·Lm+α·xmdt.Define the transmission power vector in time slott as pt≜pm,nt,m∈M&n∈N and the local computing frequency vector as ft=fmt,m∈M. The operation vector of the MEC system in time slot t can be defined as Opt=xt,pt,ft. Therefore, the computation offloading problem can be formulated as follows:
(19)P1:minOptlimT⟶∞1T∑t=0T−1costts.t.1,3,6,10,11,13,14,15,17.Since tasks have clear deadlines in this paper, we do not use delay or latency as the optimization goal. Most of previous works [9–15, 30–35] only focus on reducing energy consumption and the computation latency and do not consider the overheads of the servers. However, task offloading consumes bandwidth resource and computing tasks on the server which leads to the costs of memory and energy of the servers. Besides, service providers usually have their own pricing strategy. The price may be related to task type, computational complexity, and the usage of bandwidth and computation resources in every time slot which can be time varying. Note that as long as costn,mt is i.i.d, then our algorithm proposed in the following section can achieve near-optimality system performance based on drift-plus-penalty frameworks.


## 3.1. Task Model

Computation tasks in this paper are delay-sensitive, and the execution deadline of those tasks is no greater than the length of each time slot. All the tasks generated by edge devicem are with fixed length Lm bits. Each edge devices may have a different Lm. Whether tasks are generated in time slot t is denoted by the binary variable ξmt. When ξmt=1, it means that there are tasks arriving on edge device m in time slot t and device m needs to make offloading decisions among local computing, task offloading, and dropping. ξmt is with an independently identical distribution (i.i.d.) Bernoulli process with Eξmt=λm, where 0≤λm≤1. Let ξt=ξmt,m∈M,t=0,1,2,⋯ be the task generation vector in time slot t.Denotexmlt, xm,nt, and xmdt be the decision variables of computation offloading. xmlt=1 and xmdt=1 indicated that the tasks are executed locally and dropped, respectively. xm,nt=1 indicated that edge device m chooses edge server n to offload tasks in time slot t. The computation offloading decision vector in time slot t can be defined as xt=xmlt,xmdt,xm,nt,m∈M&n∈N. In time slot t, device m offloads tasks to one server at most, which means ∑n=1Nxm,nt≤1. In every time slots, tasks must be executed locally, remotely, or dropped. Hence, when ξmt=1, we have
(1)xmlt+∑n=1Nxm,nt+xmdt=1.


## 3.2. Local Computation Model

Assume that it takescm CPU cycles for edge device m to process 1 bit of computing task; then, the local computation delay is
(2)Dmlt=cm·Lmfmt,where fmt is the CPU frequency in time slot t. Considering that tasks must be executed before the next time slot, the local computation delay should satisfy
(3)Dmlt≤τ.Assume that the dynamic voltage and frequency scaling technologies (DVFS) [27] are adopted in the edge devices, and the CPU frequencies scheduled for tasks remain the same in a single time slot. The computation power of local execution is
(4)pmlt=κfm3t,where κ is a parameter that depends on the chip architecture. According to (2) and (4), if there are tasks to execute locally, the computation energy is
(5)Emlt=Dmlt·pmlt=κ·cm·Lm·fm2t.Due to the limited computing power of CPU, the CPU frequency should satisfy(6)0≤fmt≤fmmax.


## 3.3. Offloading Computation Model

The data associated with the tasks to be offloaded to servers are transmitted over wireless links. Since MEC servers are usually equipped with high performance CPUS, we assume that the task execution time of MEC server can be ignored for convenience. We also assume that the output results of those tasks are of small sizes and the delay for returning the results back is negligible [26, 28, 29]. Let dm,nt be the distance between edge device m and edge server n in time slot t; then, the channel power gain can be calculated by
(7)gm,nt=γm,nt·g0·d0dm,ntψ,where γm,nt is the small-scale fading channel power gain, g0 is the channel loss coefficient, and d0 and ψ are reference distance and the channel loss exponent, respectively.According to Shannon theorem, the maximum uplink transmission rate betweenm and n can be expressed by
(8)rgm,nt,pm,nt=w·log21+gm,nt·pm,ntσ2,where σ2 is the noisy power and pm,nt is the transmission power of m in time slot t. The transmission delay of the offloading tasks between device m and n in time slot t can be computed by
(9)Dm,nt=Lmrgm,nt,pm,nt.Considering that the tasks must be finished before the end of the time slot and the transmission power of edge devices is limited, hence we have(10)Dm,nt≤τ,(11)pmmin≤pm,nt≤pmmax,where pmmax and pmmin are the maximum and minimum transmission power of edge device m. The energy consumption for m offloading those tasks to server n in time slot t is
(12)Em,nt=pm,nt·Dm,nt.


## 3.4. Energy Model

Since time is slotted in this paper, the process of energy harvesting is noncontinuous. Letemt be the harvestable energy in time slot t. We assume that emt is i.i.d and satisfies
(13)0≤emt≤Emhmax,where Emhmax is the maximum value of harvestable energy at each time slot. Let et=emt,m∈M be the energy arriving vector at time slot t.We denote the residual energy of devicem’s battery at the beginning of time slot t as Bmt and Bt=Bmt,m∈M be the residual energy vector at time slot t. Bm0 is set to 0J, and Bmt satisfies
(14)Bmt≤Bmmax,where Bmmax is the battery capacity of device m. To avoid running out of energy, the residual energy of edge devices should be stabilized. In a queueing network (e.g., a network with back-pressure routing), data queue is stable means that limT⟶∞sup1/T∑t=0T∑m=1MQmt<∞, where Qmt is the data queue of node m. However, we say that the energy queue of device m is stable if the following is met:
(15)limT⟶∞1T∑t=0TBmt≥θm−ε,where θm is the perturbation parameter of device m and ε is the gap between θm and the long-term average value of Bmt. θm can be set in the 0th time slot and should no less than V·α add the maximal energy which can be consumed by m in one slot [11]. V is the parameter trading off performance between energy and costs. Constraint (15) can effectively reduce the probability of running out of energy.For simplicity, we assume that energy consumption happens only in local computation and task offloading. Then, the residual energy ofm at time slot t is
(16)Bmt+1=minBmt−ξm·xmlt·Emlt−∑n=1Nxm,nt·Em,nt++emt,Bmmax,where x+=maxx,0. When ξmt=1 and there is not enough energy to offload or execute the tasks locally, the tasks will be dropped. Considering that emt is unpredictable, in order to guarantee the computation offloading decision can be executed, the residual energy should satisfy
(17)Bmt≥ξm·xmlt·Emlt+∑n=1Nxm,nt·Em,nt.


## 3.5. Problem Formulation

In our work, the primary goal is to minimize the total costs resulted by task offloading and dropping while guaranteeing the energy of the mobile device not be exhausted. Letcostn,mt be the price of servern computing one bit data for device m in time slot t and α>0 be the penalty of dropping tasks. Then, the total cost of the MEC system can be expressed as
(18)costt=∑m=1Mcostmt=∑m=1Mξm·∑n=1Nxm,ntcostn,mt·Lm+α·xmdt.Define the transmission power vector in time slott as pt≜pm,nt,m∈M&n∈N and the local computing frequency vector as ft=fmt,m∈M. The operation vector of the MEC system in time slot t can be defined as Opt=xt,pt,ft. Therefore, the computation offloading problem can be formulated as follows:
(19)P1:minOptlimT⟶∞1T∑t=0T−1costts.t.1,3,6,10,11,13,14,15,17.Since tasks have clear deadlines in this paper, we do not use delay or latency as the optimization goal. Most of previous works [9–15, 30–35] only focus on reducing energy consumption and the computation latency and do not consider the overheads of the servers. However, task offloading consumes bandwidth resource and computing tasks on the server which leads to the costs of memory and energy of the servers. Besides, service providers usually have their own pricing strategy. The price may be related to task type, computational complexity, and the usage of bandwidth and computation resources in every time slot which can be time varying. Note that as long as costn,mt is i.i.d, then our algorithm proposed in the following section can achieve near-optimality system performance based on drift-plus-penalty frameworks.


## 4. Dynamic Offloading Algorithm Design

In this section, we will propose an online algorithm based on the framework of Lyapunov optimization to solve the computation offloading problem formulated above. By dynamically making greedy offloading decisions, the algorithm can obtain near minimum costs while pushing the residual energy of edge devices towards the configurable parameterθm. Considering the residual energy of battery is not i.i.d, we advocate the weighted perturbation method [36] to solve this issue.To stabilize the energy queue (i.e., the residual energy of battery), we define a virtual energy queueB~mt≜Bmt−θm. It is worth to note that when the virtual queue is stable, the energy queue is also stable. Let Lt denote the Lyapunov function, which is
(20)Lt≜12∑m=1MB~m2t.Then, the conditional Lyapunov drift can be defined as follows:(21)Δt≜ELt+1−LtB~mt=12∑m=1MB~m2t+1−B~m2t=∑m=1MB~mt·Zt+12Z2t,where Zt=emt−ξtm·xmlt·Emlt−∑n=1Nxm,nt·Em,nt. Considering that emt, Emlt, ξmt, and Em,nt are all equal or greater than 0 and xmlt and xm,nt can not both be 1, Z2t≤maxem2t,Eml2t,Em,n2t. Offloading tasks to server leads additional costs; hence, ∑n=1Nxm,nt·Em,nt=0 holds when device m needs more energy to offload tasks than execute those tasks locally. Therefore, the inequation Z2t≤maxem2t,Eml2t,Em,n2t holds. Then, the following inequality also holds:
(22)Δt≤C+∑m=1MB~mt·emt−ξm·xmlt·Emlt−∑n=1Nxm,nt·Em,nt,where C=M/2maxEmhmax2,κ·cm·Lm·fmmax2.Define the virtual energy queue vector of time slotB~t≜B~mt,m∈M, and then, the drift-plus-penalty function can be express as
(23)Δvt≜Δt+V·EcosttB~t,where Ex∣y is the expectation of x under the condition of y. Combine (22) and (23), we have
(24)Δvt≤∑m=1MB~mt·emt−ξm·xmlt·Emlt−∑n=1Nxm,nt·Em,nt+V·EcosttB~t+C.Then, P1 can be converted to P2 which approximately minimize the right-hand side of (24) subject to every constraints of P1.
(25)P2:minOptξm∑m=1MB~mt·emt⏟I1+V·α·xmdt⏟I3−B~mt·xmlt·Emlt⏟I4+∑n=1Nxm,ntV·Lm·costn,mt−B~mt·Em,nt⏟I2.


### 4.1. Calculations of Decision Parameters

In each time slots, all the edge devicesm with ξm=1 should firstly compute decision-related parameters and then make greedy decisions from offloading, locally computing, and dropping tasks based on those parameters. For locally executing, the device m should determine the CPU frequency of locally computing and the minimum energy cost of finishing the tasks. For offloading, the device m needs to calculate the minimum energy cost of communication associated with task offloading for every server n and correspondent transmission power.


#### 4.1.1. Calculations for Locally Executing

According to equation (5), Emlt is monotone increasing with fmt when fmt≥0. Combine (2) and (3), we have fmt≥cm·Lm/τ. Therefore, Emlt≥κ·cm3·Lm3/τ2 holds according to (5). Denote the minimum energy cost for locally executing and the correspondent frequency as Eml′t and fm′t; then, we have Eml′t=κ·cm3·Lm3/τ2 and fm′t=cm·Lm/τ.


#### 4.1.2. Calculations for Offloading

For every servern in m’s communication range, m solves Em,n′t=minEm,nt, s.t. (10) and (11). Note that the function Em,nt=fpm,nt has no obvious monotonicity; the minimum energy cost of offloading from m to n can be obtained by following traversal method. For pm,nt from pmmin to pmmax, use Δp as the step length, calculate all Em,nt which satisfies the condition (10) according to (9) and (12), and obtain the minimum energy cost Em,n′t and the correspondent transmission power pm,n′t.


### 4.2. Computation Offloading Algorithm

According to P2, itemsI1, I2, I3, and I4 are related to energy harvesting, task offloading, task dropping, and locally executing, respectively, and only an item of I2, I3, and I4 can be active in one time slot. Considering all those items are irrelevant, P2 can be converted into minimizing I1, I2, I3, and I4, respectively. To find the minimum values of those items, it needs to be discussed in the three cases which are B~mt=0, B~mt<0, and B~mt>0.WhenB~mt=0, I1 and I4 equals to 0. Assume that the edge device m decides to offload tasks to one of those servers, then ∑n=1Nxm,nt=1 andI2>0 holds. Assume that the edge device m decides to drop tasks, then xmdt=1 and I2>0 holds. Hence, executing tasks locally leads I2+I3+I4 to be minimum (equals to 0). Note that there will be enough energy to execute the tasks locally when B~mt=0; therefore, the strategy under the condition B~mt=0 can be described as follows: use the optimal frequency fm′t to execute the tasks locally, store all or part of the harvestable energy in the battery, and update the residual energyBmt+1 according to (16).WhenB~mt<0, obtain Eml′t, fm′t, Em,n′t, and pm,n′t using the method mentioned above. Compute costs for every server n using costn,m′t=V·Lm·costn,mt−B~mt·Em,n′t. Find the minimum item under the constraint (17) in the set costn,m′t,V·β,−B~mt·Eml′t,n∈N. If the result is costn∗,m′t, then choose server n∗ to offload tasks with the power pm,n∗′t. Else if the results goes to −B~mt·Eml′t, then use the frequency fm′t to locally executing tasks. Otherwise, drop the tasks. Store all the harvestable energy in the battery and update the residual energy Bmt+1 accordingly.WhenB~mt>0, I3≥0, I4≤0, and the sign of I2 is not guaranteed. Hence, the computation offloading decision only can be locally executing or offloading. Solve Em,n′′t=argminV·Lm·costn,mt−B~mt·Em,n′′t and obtain Em,n′′ for all the server n. Em,n′′ can be obtained by using iterative calculation method mentioned above similarly. After that, solve Em,n∗′′t=argminV·Lm·costn∗,mt−B~mt·Em,n∗′′t and obtain pm,n∗′′t, Em,n∗′′t, and n∗. According to (5), using fmmax to execute tasks locally leads the highest energy consumption. Hence, if V·Lm·costn∗,mt−B~mt·Em,n∗′′t<Eml′′t, choose server n∗ and use the transmission power pm,n∗′′t to offloading tasks. Otherwise, use frequency fmmax to execute tasks locally. In terms of energy harvesting, abandon all the harvestable energy.Based on the Lyapunov optimization framework, the computation offloading strategy above can obtain nearly the minimum long time average costs and achieve the minimum costs whenV⟶+∞. However, the strategy always tries to push the energy queue to θm which may lead edge devices to try their best to consume energy when B~mt>0. For example, edge devices will choose the server with the longest distance to offload tasks when the charges of servers (costn,mt, n∈N) are the same and use the largest frequency to execute tasks locally. The harvestable energy also will be discarded to increase energy consumption. In fact, executing tasks locally with fm′t is not only beneficial to save energy but also reduce the service fee of the servers when B~mt≥0. Besides, harvesting all the harvestable energy can efficiently increase the residual energy of edge devices and ability to cope with energy scarcity (e.g., harvesting little energy for a long time). To summarize and improve the computation offloading above, we propose Lyapunov-based computation offloading algorithm (i.e., Algorithm 1) as follows.Algorithm 1
Lyapunov-based computation offloading algorithm.Input:ξt,et,t∈T, G=M,N, costn,mt,dm,nt,γm,nt,m∈M,n∈N,t∈T, σ, κ,G=M,N,g0, Bm0,Bmmax,fmmax,pmmax,Lm,cm,m∈M.Output: The offloading strategy of different edge devices.for each time slot tdofor each device m with ξm=0, harvest all the energy and update Bmt+1.end forfor each device m with ξm=1doobtainBmt and fm′t, then compute B~mt.ifB~mt≥0, use fm′t for local computing.harvest all the energyemt, store it in battery, and update Bmt+1.else compute Eml′t according to (2),(3),(5) and (6).for all the n, device mdosolveEm,n′t=minEm,nts.t.10,11,obtainEm,n′t and pm,n′t accordingly,computecostn,m′t=V·Lm·costn,mt−B~mt·Em,n′t.end forfind minimum element incostn,m′t,V·α,−B~mtEml′t,n∈N, s.t.(13).if the element is costn∗,m′t, choose sever n∗and use pm,n∗′t to offloading tasks.else if the element is −B~mtEml′t, use fm′tfor local computing.else drop the tasks.end ifharvest all the energy, and updateBmt+1.end ifend forend forThe complexity of Algorithm1 is Om∗n in each time slot t. It is very lightweight and can be easily implemented in a distributed manner where each device only needs to know the distance and costs of its neighbor servers and can make offloading decisions locally. In this paper, we do not consider the interface between links. Note that Algorithm 1 will try its best to reduce offloading to achieve a lower service cost; hence, the transmission collision will also be reduced. Moreover, maximal matching-based algorithms [37, 38] can be adapted to our algorithm in the cases when the links interfere with each other.


## 4.1. Calculations of Decision Parameters

In each time slots, all the edge devicesm with ξm=1 should firstly compute decision-related parameters and then make greedy decisions from offloading, locally computing, and dropping tasks based on those parameters. For locally executing, the device m should determine the CPU frequency of locally computing and the minimum energy cost of finishing the tasks. For offloading, the device m needs to calculate the minimum energy cost of communication associated with task offloading for every server n and correspondent transmission power.


### 4.1.1. Calculations for Locally Executing

According to equation (5), Emlt is monotone increasing with fmt when fmt≥0. Combine (2) and (3), we have fmt≥cm·Lm/τ. Therefore, Emlt≥κ·cm3·Lm3/τ2 holds according to (5). Denote the minimum energy cost for locally executing and the correspondent frequency as Eml′t and fm′t; then, we have Eml′t=κ·cm3·Lm3/τ2 and fm′t=cm·Lm/τ.


### 4.1.2. Calculations for Offloading

For every servern in m’s communication range, m solves Em,n′t=minEm,nt, s.t. (10) and (11). Note that the function Em,nt=fpm,nt has no obvious monotonicity; the minimum energy cost of offloading from m to n can be obtained by following traversal method. For pm,nt from pmmin to pmmax, use Δp as the step length, calculate all Em,nt which satisfies the condition (10) according to (9) and (12), and obtain the minimum energy cost Em,n′t and the correspondent transmission power pm,n′t.


## 4.1.1. Calculations for Locally Executing

According to equation (5), Emlt is monotone increasing with fmt when fmt≥0. Combine (2) and (3), we have fmt≥cm·Lm/τ. Therefore, Emlt≥κ·cm3·Lm3/τ2 holds according to (5). Denote the minimum energy cost for locally executing and the correspondent frequency as Eml′t and fm′t; then, we have Eml′t=κ·cm3·Lm3/τ2 and fm′t=cm·Lm/τ.


## 4.1.2. Calculations for Offloading

For every servern in m’s communication range, m solves Em,n′t=minEm,nt, s.t. (10) and (11). Note that the function Em,nt=fpm,nt has no obvious monotonicity; the minimum energy cost of offloading from m to n can be obtained by following traversal method. For pm,nt from pmmin to pmmax, use Δp as the step length, calculate all Em,nt which satisfies the condition (10) according to (9) and (12), and obtain the minimum energy cost Em,n′t and the correspondent transmission power pm,n′t.


## 4.2. Computation Offloading Algorithm

According to P2, itemsI1, I2, I3, and I4 are related to energy harvesting, task offloading, task dropping, and locally executing, respectively, and only an item of I2, I3, and I4 can be active in one time slot. Considering all those items are irrelevant, P2 can be converted into minimizing I1, I2, I3, and I4, respectively. To find the minimum values of those items, it needs to be discussed in the three cases which are B~mt=0, B~mt<0, and B~mt>0.WhenB~mt=0, I1 and I4 equals to 0. Assume that the edge device m decides to offload tasks to one of those servers, then ∑n=1Nxm,nt=1 andI2>0 holds. Assume that the edge device m decides to drop tasks, then xmdt=1 and I2>0 holds. Hence, executing tasks locally leads I2+I3+I4 to be minimum (equals to 0). Note that there will be enough energy to execute the tasks locally when B~mt=0; therefore, the strategy under the condition B~mt=0 can be described as follows: use the optimal frequency fm′t to execute the tasks locally, store all or part of the harvestable energy in the battery, and update the residual energyBmt+1 according to (16).WhenB~mt<0, obtain Eml′t, fm′t, Em,n′t, and pm,n′t using the method mentioned above. Compute costs for every server n using costn,m′t=V·Lm·costn,mt−B~mt·Em,n′t. Find the minimum item under the constraint (17) in the set costn,m′t,V·β,−B~mt·Eml′t,n∈N. If the result is costn∗,m′t, then choose server n∗ to offload tasks with the power pm,n∗′t. Else if the results goes to −B~mt·Eml′t, then use the frequency fm′t to locally executing tasks. Otherwise, drop the tasks. Store all the harvestable energy in the battery and update the residual energy Bmt+1 accordingly.WhenB~mt>0, I3≥0, I4≤0, and the sign of I2 is not guaranteed. Hence, the computation offloading decision only can be locally executing or offloading. Solve Em,n′′t=argminV·Lm·costn,mt−B~mt·Em,n′′t and obtain Em,n′′ for all the server n. Em,n′′ can be obtained by using iterative calculation method mentioned above similarly. After that, solve Em,n∗′′t=argminV·Lm·costn∗,mt−B~mt·Em,n∗′′t and obtain pm,n∗′′t, Em,n∗′′t, and n∗. According to (5), using fmmax to execute tasks locally leads the highest energy consumption. Hence, if V·Lm·costn∗,mt−B~mt·Em,n∗′′t<Eml′′t, choose server n∗ and use the transmission power pm,n∗′′t to offloading tasks. Otherwise, use frequency fmmax to execute tasks locally. In terms of energy harvesting, abandon all the harvestable energy.Based on the Lyapunov optimization framework, the computation offloading strategy above can obtain nearly the minimum long time average costs and achieve the minimum costs whenV⟶+∞. However, the strategy always tries to push the energy queue to θm which may lead edge devices to try their best to consume energy when B~mt>0. For example, edge devices will choose the server with the longest distance to offload tasks when the charges of servers (costn,mt, n∈N) are the same and use the largest frequency to execute tasks locally. The harvestable energy also will be discarded to increase energy consumption. In fact, executing tasks locally with fm′t is not only beneficial to save energy but also reduce the service fee of the servers when B~mt≥0. Besides, harvesting all the harvestable energy can efficiently increase the residual energy of edge devices and ability to cope with energy scarcity (e.g., harvesting little energy for a long time). To summarize and improve the computation offloading above, we propose Lyapunov-based computation offloading algorithm (i.e., Algorithm 1) as follows.Algorithm 1
Lyapunov-based computation offloading algorithm.Input:ξt,et,t∈T, G=M,N, costn,mt,dm,nt,γm,nt,m∈M,n∈N,t∈T, σ, κ,G=M,N,g0, Bm0,Bmmax,fmmax,pmmax,Lm,cm,m∈M.Output: The offloading strategy of different edge devices.for each time slot tdofor each device m with ξm=0, harvest all the energy and update Bmt+1.end forfor each device m with ξm=1doobtainBmt and fm′t, then compute B~mt.ifB~mt≥0, use fm′t for local computing.harvest all the energyemt, store it in battery, and update Bmt+1.else compute Eml′t according to (2),(3),(5) and (6).for all the n, device mdosolveEm,n′t=minEm,nts.t.10,11,obtainEm,n′t and pm,n′t accordingly,computecostn,m′t=V·Lm·costn,mt−B~mt·Em,n′t.end forfind minimum element incostn,m′t,V·α,−B~mtEml′t,n∈N, s.t.(13).if the element is costn∗,m′t, choose sever n∗and use pm,n∗′t to offloading tasks.else if the element is −B~mtEml′t, use fm′tfor local computing.else drop the tasks.end ifharvest all the energy, and updateBmt+1.end ifend forend forThe complexity of Algorithm1 is Om∗n in each time slot t. It is very lightweight and can be easily implemented in a distributed manner where each device only needs to know the distance and costs of its neighbor servers and can make offloading decisions locally. In this paper, we do not consider the interface between links. Note that Algorithm 1 will try its best to reduce offloading to achieve a lower service cost; hence, the transmission collision will also be reduced. Moreover, maximal matching-based algorithms [37, 38] can be adapted to our algorithm in the cases when the links interfere with each other.


## 5. Performance Evaluation

To validate the effectiveness of our proposed approach, we conduct simulations in this section. We consider a MEC system with 5 mobile edge devices and 3 edge servers. For simplicity, all the harvestable energy of edge devices is i.i.d and obeys the same distribution. The harvestable energyemt in every time slot t is λt∗4∗10−7 J, where λt is subject to the Poisson distribution with Eλt=5. The task arriving process of each edge devices is assumed to be a Bernoulli process. The task arriving probabilities of device 1 to device 5 are 0.1,0.3,0.5,0.7,0.9. The maximum CPU frequencies of all the edge devices are 2 GHz. Lm=1000 bit for all devices m∈M. The time slot length τ is 4 ms, and Bm0 is 0 J for all m∈M. We also assume κ=10−28 and cm=1000.To embody the mobility sufficiently, we assume that the distance between any edge device and any server takes a random value from10,70 metres in every time slots. We assume that d0=5 meters, σ2=10−13 W, costn,mt=10−6 per bit and γm,nt=1 for m∈M and n∈N, w=1 MHz, pmmin=1 mw and pmmax=50 mw for m∈M, and ψ=4. θm is set to 2∗10−4 J.Figures1 and 2 show the residual energy processes of all 5 edge devices under the condition V=10−8 and V=10−6, respectively. α is set to 2∗10−3, and simulations are run for 500 time slots. From Figure 1, we can see that the residual energy of devices 3, 4, and 5 increases at first and then stabilizes around the perturbation parameters θm, respectively, which exactly keeps the advantages of our algorithm. The reason why the residual energy of devices 1 and 2 is with growing tendencies is that the harvestable energy is enough to sustain all the tasks being executed locally. Figure 2 shows that as Vgrows to 10−6, the residual energy of devices 3, 4, and 5 can still reach a steady state with values which are much lower than that of V=10−8. Note that the average residual energy of edge devices decreases as V increases; we will show that the value of V also influences the total costs of the MEC system and can trade-off energy performances and costs later.Figure 1
Residual energy of edge devices vs. time asV=10−8.Figure 2
Residual energy of edge devices vs. time asV=10−6.Figure3 demonstrates computation offloading processes of devices 2 (D2) and 4 (D4) under V=10−8. At the beginning, both devices keep harvesting energy and dropping tasks to push their residual energy to θm (the residual energy processes are shown in Figure 1). When their residual energy increases to a certain value, both devices stop dropping tasks and begin to offload tasks to servers for remote execution. As time goes on, both devices will begin to execute tasks locally when their residual energy goes to some value (e.g., near by θm when V=10−8). Since the harvestable energy of device 2 is enough to execute all tasks locally, device 2 executes nearly all tasks some time slots later (nearly the 100th time slot). To stabilize the energy queue, part of the tasks of device 4 is executed locally while others are offloaded to servers some time later.Figure 3
Computation offloading processes of devices 2 and 4.According to our energy queue stability definition (showed in equation (15)), the convergence time should be Oθm−ε, where ε is a positive number. Hence, the convergence time is no larger than Oθm which is approximately equal to θm/Eemt. In our simulation, the harvestable energy emt in every slot t is λt∗4∗10−7 J, where λt is subject to the Poisson distribution with Eλt=5 and θm is set to 2∗10-4 J; hence, the convergence time is about 100 time slots. Although the residual energy of device 1 and device 2 seems never converging to a fixed value in Figure 1, the offloading decision processes have reached a stable state at about the 100th time slot. As can be seen from Figure 3, D2 stops dropping and offloading and executes nearly all tasks after the 100th time slot.Figure4 shows the total costs of all the edge devices with different parameter V. We can see that the total costs decrease with the increasement of V. As shown in Figure 1, the long-time average residual energy of edge devices decreases as the parameter V increases. Therefore, parameter V does trade-off energy performances and the total costs.Figure 4
Total costs of edge devices vs.V.To evaluate the performance of our algorithm in terms of reducing the total system costs, we compare our proposed algorithm against three other strategies: strategy where all tasks are executed locally with the optimal frequencyfml′ (local only), strategy where all tasks are offloaded to the serve with the minimum service costs (offloading only), and the strategy where edge devices randomly make choice from locally executing and offloading and choose random server to offloading when they have decided to execute tasks remotely (random). Figure 5 demonstrates the total costs of all the edge devices vs. time under the condition V=10−7. The results show that our algorithm performs significantly better in comparison to other three comparison algorithms.Figure 5
Total costs by different algorithms.Figure6 shows the residual energy dynamic of device 4 by using different strategies which are the proposed algorithm, local only, offloading only, and random strategy. The parameter V is set to 10−7. Since the harvestable energy of devices 1 and 2 is sufficient to execute all computing tasks locally, the residual energy will keep growing until it reaches Bmmax. Devices 3 and 5 have a similar energy process as that of device 4; hence, we only show the results of device 4. Figure 6 demonstrates that our algorithm can use the harvestable energy more effectively and stabilize the residual energy to a preset value.Figure 6
Residual energy processes of different algorithms over device 4.Figure7 shows the effects of the parameter α on computation offloading decisions under the condition V=10−7. Y axis is the total number of execution times of all the edge devices. As α goes larger, the number of task dropping will decrease, and the number of offloading will increase. When the tasks have high intertask dependencies, we can set α to a large value to avoid task dropping.Figure 7
The influence ofα on offloading decisions.


## 6. Conclusions

In this paper, an online and lightweight algorithm has been proposed for solving the computation offloading problems in energy harvesting MEC systems with multiuser and multiserver. Based on stochastic Lyapunov optimization framework, the proposed algorithm can minimize the total system costs and guarantee the devices’ residual energy stabilized to a preset value. It needs no prior knowledge of the harvestable energy and the task arrival rates and can make trade-off between system costs and the residual energy by a parameterV. The algorithm is also light-weighted and can be easily implemented in a distributed manner since each device can make offloading decisions locally only based on the distance and service costs of its neighbor servers. Our evaluation data shows that the proposed algorithm can take fully use of the harvestable energy and effectively reduce the total system costs caused by computing services and task droppings.



---

*Source: 2279362-2022-09-26.xml*