# Markov Approximation for Task Offloading and Computation Scaling in Mobile Edge Computing

Authors: Wenchen Zhou; Weiwei Fang; Yangyang Li; Bo Yuan; Yiming Li; Tian Wang
Journal: Mobile Information Systems
 (2019)

---

## Abstract

Mobile edge computing (MEC) provides cloud-computing services for mobile devices to offload intensive computation tasks to the physically proximal MEC servers. In this paper, we consider a multiserver system where a single mobile device asks for computation offloading to multiple nearby servers. We formulate this offloading problem as the joint optimization of computation task assignment and CPU frequency scaling, in order to minimize a tradeoff between task execution time and mobile energy consumption. The resulting optimization problem is combinatorial in essence, and the optimal solution generally can only be obtained by exhaustive search with extremely high complexity. Leveraging the Markov approximation technique, we propose a light-weight algorithm that can provably converge to a bounded near-optimal solution. The simulation results show that the proposed algorithm is able to generate near-optimal solutions and outperform other benchmark algorithms.


---

## Body

## 1. Introduction

In recent years, mobile devices (MDs) have become an indispensable tool for communication, information, and entertainment in our daily life. However, finite battery capacities and limited computation resources pose intractable challenges for satisfying user-experience requirements. Computation offloading is recognized as a promising solution to cope with such a problem, by migrating computation tasks from mobile devices via wireless access to more powerful servers [1]. Mobile cloud computing (MCC) has been considered as one of the potential solutions. It is commonly assumed that the implementation of MCC relies on data exchange with a centralized cloud through wide area networks [2]. Nevertheless, MCC imposes huge traffic load on mobile networks and brings high communication latency due to the long distance from MDs to the cloud.Mobile edge computing (MEC), which deploys MEC servers directly at the base stations using generic-computing platforms, is a newly proposed solution for the above problem. In this paradigm, IT and cloud-computing services are provided in close proximity to mobile devices [3]. By endowing ubiquitous wireless access networks (e.g., macrocell and small-cell base stations) with resource-rich computing infrastructures, MEC is envisioned to provide pervasive and agile computation augmenting services when and where are needed. Since the concept of MEC was proposed by European Telecommunications Standards Institute (ETSI), it has attracted increasing attentions from academic researchers. In particular, one of the key design issues in MEC is resource allocation [3]: should a computation task be processed locally by a MD’s CPU or remotely by a MEC server, and if the latter is chosen, how many resources should be allocated to this task? This question stems from the basic tradeoff between the cost of task offloading and the reduction in task execution time brought by offloading. While conceptually simple, it is challenging to make optimal decisions since many factors are coupled and the solution space is very large. Various approaches have been proposed to tackle this resource allocation problem in many kinds of scenarios [3, 4]. Some of them focused on single-user cases, while the others focused on multiuser cases. However, in these studies, the MD is assumed to be associated with only a single MEC server. With the expectation of small-cell/femtocell base stations been massively deployed in future networks, a MD can choose to offload its tasks to multiple nearby MEC servers with computational capabilities, other than only one MEC server [5].This paper focuses on system optimization in scenarios where a single MD is capable of scaling its CPU frequency and allocating computation tasks to multiple MEC servers. Specifically, we exploit the diversity in terms of task assignment and CPU frequency to make optimal control decisions so as to minimize the tradeoff between task execution time and mobile energy consumption. We formulate such a problem as a combinatorial optimization, NP-hard problem. Inspired by the Markov approximation framework proposed in [6], we have devised an efficient approximation algorithm with near-optimal performance. In summary, the main contributions of this paper are as follows:(1)
We propose to exploit the task assignment decision and the computation scaling capability to jointly optimize the tradeoff between latency and energy in a multiserver MEC system and then formulate this as a nonlinear combinatorial optimization problem.(2)
We devise an approximation algorithm based on the Markov approximation framework [6] to solve the proposed problem efficiently. This algorithm can find the near-optimal solution by implementing a Markov chain over all feasible configurations and performing state transitions [6–8]. Then, we investigate key characteristics of the designed Markov chain and analyze the algorithm in terms of performance optimality, approximation gap, and error robustness.(3)
We conduct simulation experiments to demonstrate performance of our Markov approximation-based algorithm under various parameter settings. The simulation results show that this algorithm can generate near-optimal solutions and remarkably outperforms other benchmark algorithms.The rest of this paper is organized as follows. Section2 reviews related work. Section 3 presents the system model and the problem definition. Then, the proposed Markov approximation-based algorithm is introduced in Section 4. Section 5 demonstrates the simulation results. Finally, Section 6 summarizes the conclusions and outlines future work.


## 2. Related Work

From the computation perspective, MEC offers a new service environment characterized by proximity, efficiency, low latency, and high availability, making computation offloading a promising paradigm for MDs [3]. To this end, three important issues have to be taken into account, namely, resource allocation, data partition, and optimization objective.Since offloading introduces additional communication overhead, a key technique challenge is how to allocate computation and communication resources so as to balance the energy-performance tradeoff and support the user-experience demands [4]. Recent years have seen increasing research progresses on resource allocation for both single-user [9–11] and multiuser MEC systems [12–14]. Wang et al. [9] investigated computation offloading in MEC by jointly optimizing a MD’s CPU speed, transmit power, and offloading ratio to achieve two different design objectives, i.e., minimizing energy consumption and minimizing execution time, of the MD. Liu et al. [10] adopted a Markov decision process approach to solve the power-constrained latency minimization problem in MEC, where a MD schedules its computation tasks based on queue size, execution state, and channel information. You et al. [11] proposed a framework in which a MD can not only process computations tasks at local CPU or offload them to the MEC server but also harvest energy from the base station by microwave power transfer (MPT). The offloading problem in multiuser cases is more complex than that in single-user cases. You et al. [12] studied the optimal resource allocation for a multiuser MEC system with both time division multiple access (TDMA) and orthogonal frequency division multiple access (OFDMA). Chen et al. [13] proposed a game theoretic scheme for the computation offloading decision making problem in multiuser scenarios and demonstrated that the designed game always admits a Nash equilibrium. Sardellitti et al. [14] designed an iterative algorithm based on successive convex approximation techniques to minimize the overall users’ energy consumption with latency constraints in a MIMO multicell system. However, the work introduced above only considered the scenario where a MD only associates with a single edge server. Since the future mobile networks will be heterogeneous due to dense deployment of base stations with different capabilities [3], we can exploit such a diversity to provide more offloading options and sufficient resource capacities to MDs for guaranteeing low service latency and satisfactory user experience [15].Generally, computation offloading could be performed in two fashions, i.e., full offloading and partial offloading [9]. In full offloading, the mobile application has to be executed as a whole either locally at the MD or remotely at the MEC server [14]. Compared with full offloading, partial offloading takes advantage of parallelism between the MD and the MEC server, so it is much more capable to satisfy stringent latency requirement. However, existing work [9, 16] often assumed full granularity of data partition, i.e., the offloaded data could be partitioned as small as possible. In practice, a mobile application may contain some indivisible tasks or files that cannot be separated into parts of any size [5].Computation offloading affects both mobile energy consumption and task execution time. On the one hand, in situations where the MD with latency-sensitive applications has a stringent requirement on energy consumption, it is essential to apply latency-oriented solutions [9, 10, 17] to utilize limited energy efficiently, so as to shorten the execution time as much as possible. On the other hand, in order to prolong the MD’s lifetime, energy-oriented solutions [9, 11, 12, 14] are proposed to minimize the overall energy consumption of MDs while guaranteeing the latency requirement of mobile applications. As far as we know, only a few studies [5, 13, 15] have focused on optimizing these two metrics simultaneously.While recognizing their significance, our work is different from and complementary to existing studies. We investigate a joint optimization of task offloading and computation scaling problem in a multiserver MEC system, with the objective to minimize the tradeoff between latency and energy. Besides, in system modeling, we take into account many practical aspects that were missing or unconsidered in previous work investigating relevant problems. To our best knowledge, the proposed problem has not been explored by prior work.


## 3. System Model and Problem Formulation

### 3.1. System Model

Let us consider a MD that has a set of tasksM to be processed. It can choose to either process these tasks at local CPU or offload them to any one among the nearby MEC servers N. We assume that the wireless base stations operate on orthogonal wireless channels so that any two of them will not interfere each other. We leverage the binary variables xm,ym,n∈0,1, ∀m∈M, and ∀n∈N, to represent the task assignment, i.e.,(1)xm=1,if  taskmis processed  at  local  CPU,0,if  taskmis  processed  at  a  MEC  server,ym,n=1,if taskmis assigned  to   MEC  servern,0,otherwise.A task must be processed locally or remotely, i.e., the aforementionedM tasks could be separated into N+1 disjoint sets. To ensure this, we impose the following constraint:(2)xm+∑n∈Nym,n=1,∀m∈M.A computation taskm is characterized by a three-tuple of parameters, am,bm,cm, where am denotes the total number of CPU cycles needed to accomplish the task m, while bm and cm denote the size of computation input data (in bits) and output data (in bits), respectively. In this work, we assume that the MD can apply the methods such as offline measurements [18] and call-graph analysis [13] to obtain the values of am, bm, and cm. We now analyze the computation overhead in terms of both execution time and energy consumption for both local and offloading approaches.(1)
Local computing: If the MD chooses the local computing approach, it will execute the computation task m locally using its own CPU. Let ψMD be the computation capability (i.e., CPU cycles per second) of the MD. Given the decision profile x=xm∈0,1M and ψMD, the execution time of computing a batch of tasks at local CPU is given by(3)TMDx,ψMD=∑m∈MxmamψMD.For the computational energy, we have that(4)EMDx,ψMD=ϒ1ψMDθ+ϒ2TMDx,ψMD,where ϒ1ψMDθ+ϒ2 denotes the computational power of the MD. As in [19], θ ranges from 2 to 3, while ϒ1 and ϒ2 are parameters depending on chip architecture. Their values can be obtained by the measurement approach in [19]. Using dynamic voltage frequency scaling (DVFS) technology [4, 14, 19], the MD could adaptively adjust ψMD to shorten execution time or reduce energy consumption. For example, the Nexus S smartphone has six levels of CPU speeds, each of which matches with some specific voltage [19]. In this work, we assume that ψMD takes value in some finite and discrete set Ψ=ψψmin≤ψ≤ψmax, where ψmin and ψmax are minimum and maximum CPU frequency of the MD, respectively.(2)
MEC offloading: If the MD chooses the MEC offloading approach, it will offload the computation task m to one of the MEC servers via wireless access. This chosen server will execute task m on behalf of the MD. Such computation offloading would incur extra overhead in terms of time and energy for transmitting the computation input and output data. We assume that each MEC server n can provide the MD with fixed service rate (i.e., CPU cycles per second) ψn, which is determined according to the MEC computing service contract subscribed by the MD from its mobile operator [13]. The average uplink and downlink data rates, denoted by rnUL and rnDL, are also assumed to be known by the MD before task processing by applying the methods in [1, 5]. For simplicity, the data transmission and the task processing are assumed to be nonoverlapping and noninterfering with each other, which means the uploading, computing, and downloading steps are carried out sequentially [5]. Given the decision profile y=ym,n∈0,1M×N, the total execution time of computing a batch of tasks at MEC server n can be given as(5)Tny=∑m∈Mym,namψn+bmrnUL+cmrnDL.The MD’s energy consumption on wireless transmission can be calculated as(6)EMECy=Ptx∑m∈M∑n∈Nym,nbmrnUL+Prx∑m∈M∑n∈Nym,ncmrnDL,where Ptx and Prx denote the transmitting and receiving power, respectively.


### 3.2. Problem Formulation

In this work, we hope to optimize two metrics, i.e., the tasks’ execution time and the MD’s energy consumption. Because the MD and MEC servers process tasks in parallel, the time metric can be given by(7)Tx,y,ψMD=maxTMDx,ψMD,maxn∈NTny.The energy consumption metric can be given by(8)Ex,y,ψMD=EMDx,ψMD+EMECy.However, these two objectives are coupled byxm, ym,n, and ψMD, so they cannot be optimized independently and contemporaneously. To investigate the tradeoff between them, we construct a unified objective function (or system utility) as(9)Ux,y,ψMD=ξTTx,y,ψMD+ξEEx,y,ψMD,where ξT,ξE∈0,1 denote the weighting parameters of execution time and energy consumption for the MD. In this way, the latency and energy metrics can be taken into the decision making at the same time, while ξT and ξE reflect the relative importance between them. If the MD is running some application that is sensitive to the latency, it can set ξT⟶1 and ξE⟶0 when making decision. If the MD is at a low battery state and cares more about the energy consumption, it can set ξT⟶0 and ξE⟶1 when making decision. Such a weighted sum approach has been extensively used for modeling similar multiobjective optimization problems [2].In conclusion, the optimization problem is formulated as(10)P1:minUx,y,ψMD.s.t. constraint (2),(11)var:ψMD∈Ψ,xm,ym,n∈0,1,∀m∈M,∀n∈N.The problemP1 is essentially a mixed-integer nonlinear programming, which is known as NP-hard. Furthermore, this problem is also a combinatorial optimization, in which the global optimal solution consists of decisions for each computation task and the MD’s CPU. Since there is no computationally efficient way to get the exact optimal solution, we propose to develop a fast polynomial approximated algorithm that solves problem P1 based on the Markov approximation framework [6].


## 3.1. System Model

Let us consider a MD that has a set of tasksM to be processed. It can choose to either process these tasks at local CPU or offload them to any one among the nearby MEC servers N. We assume that the wireless base stations operate on orthogonal wireless channels so that any two of them will not interfere each other. We leverage the binary variables xm,ym,n∈0,1, ∀m∈M, and ∀n∈N, to represent the task assignment, i.e.,(1)xm=1,if  taskmis processed  at  local  CPU,0,if  taskmis  processed  at  a  MEC  server,ym,n=1,if taskmis assigned  to   MEC  servern,0,otherwise.A task must be processed locally or remotely, i.e., the aforementionedM tasks could be separated into N+1 disjoint sets. To ensure this, we impose the following constraint:(2)xm+∑n∈Nym,n=1,∀m∈M.A computation taskm is characterized by a three-tuple of parameters, am,bm,cm, where am denotes the total number of CPU cycles needed to accomplish the task m, while bm and cm denote the size of computation input data (in bits) and output data (in bits), respectively. In this work, we assume that the MD can apply the methods such as offline measurements [18] and call-graph analysis [13] to obtain the values of am, bm, and cm. We now analyze the computation overhead in terms of both execution time and energy consumption for both local and offloading approaches.(1)
Local computing: If the MD chooses the local computing approach, it will execute the computation task m locally using its own CPU. Let ψMD be the computation capability (i.e., CPU cycles per second) of the MD. Given the decision profile x=xm∈0,1M and ψMD, the execution time of computing a batch of tasks at local CPU is given by(3)TMDx,ψMD=∑m∈MxmamψMD.For the computational energy, we have that(4)EMDx,ψMD=ϒ1ψMDθ+ϒ2TMDx,ψMD,where ϒ1ψMDθ+ϒ2 denotes the computational power of the MD. As in [19], θ ranges from 2 to 3, while ϒ1 and ϒ2 are parameters depending on chip architecture. Their values can be obtained by the measurement approach in [19]. Using dynamic voltage frequency scaling (DVFS) technology [4, 14, 19], the MD could adaptively adjust ψMD to shorten execution time or reduce energy consumption. For example, the Nexus S smartphone has six levels of CPU speeds, each of which matches with some specific voltage [19]. In this work, we assume that ψMD takes value in some finite and discrete set Ψ=ψψmin≤ψ≤ψmax, where ψmin and ψmax are minimum and maximum CPU frequency of the MD, respectively.(2)
MEC offloading: If the MD chooses the MEC offloading approach, it will offload the computation task m to one of the MEC servers via wireless access. This chosen server will execute task m on behalf of the MD. Such computation offloading would incur extra overhead in terms of time and energy for transmitting the computation input and output data. We assume that each MEC server n can provide the MD with fixed service rate (i.e., CPU cycles per second) ψn, which is determined according to the MEC computing service contract subscribed by the MD from its mobile operator [13]. The average uplink and downlink data rates, denoted by rnUL and rnDL, are also assumed to be known by the MD before task processing by applying the methods in [1, 5]. For simplicity, the data transmission and the task processing are assumed to be nonoverlapping and noninterfering with each other, which means the uploading, computing, and downloading steps are carried out sequentially [5]. Given the decision profile y=ym,n∈0,1M×N, the total execution time of computing a batch of tasks at MEC server n can be given as(5)Tny=∑m∈Mym,namψn+bmrnUL+cmrnDL.The MD’s energy consumption on wireless transmission can be calculated as(6)EMECy=Ptx∑m∈M∑n∈Nym,nbmrnUL+Prx∑m∈M∑n∈Nym,ncmrnDL,where Ptx and Prx denote the transmitting and receiving power, respectively.


## 3.2. Problem Formulation

In this work, we hope to optimize two metrics, i.e., the tasks’ execution time and the MD’s energy consumption. Because the MD and MEC servers process tasks in parallel, the time metric can be given by(7)Tx,y,ψMD=maxTMDx,ψMD,maxn∈NTny.The energy consumption metric can be given by(8)Ex,y,ψMD=EMDx,ψMD+EMECy.However, these two objectives are coupled byxm, ym,n, and ψMD, so they cannot be optimized independently and contemporaneously. To investigate the tradeoff between them, we construct a unified objective function (or system utility) as(9)Ux,y,ψMD=ξTTx,y,ψMD+ξEEx,y,ψMD,where ξT,ξE∈0,1 denote the weighting parameters of execution time and energy consumption for the MD. In this way, the latency and energy metrics can be taken into the decision making at the same time, while ξT and ξE reflect the relative importance between them. If the MD is running some application that is sensitive to the latency, it can set ξT⟶1 and ξE⟶0 when making decision. If the MD is at a low battery state and cares more about the energy consumption, it can set ξT⟶0 and ξE⟶1 when making decision. Such a weighted sum approach has been extensively used for modeling similar multiobjective optimization problems [2].In conclusion, the optimization problem is formulated as(10)P1:minUx,y,ψMD.s.t. constraint (2),(11)var:ψMD∈Ψ,xm,ym,n∈0,1,∀m∈M,∀n∈N.The problemP1 is essentially a mixed-integer nonlinear programming, which is known as NP-hard. Furthermore, this problem is also a combinatorial optimization, in which the global optimal solution consists of decisions for each computation task and the MD’s CPU. Since there is no computationally efficient way to get the exact optimal solution, we propose to develop a fast polynomial approximated algorithm that solves problem P1 based on the Markov approximation framework [6].


## 4. Markov Approximation and Algorithm Design

Markov approximation is a recently proposed technique for solving combinatorial network optimization problems [6]. Generally, this framework is consisted of two steps: log-sum-exp approximation and constructing problem-specific Markov chains that yield efficient parallel implementation for solving problem approximately. The proofs on optimality and convergence for Markov approximation have been presented in [6].


### 4.1. Log-Sum-Exp Approximation

Letf=x,y,ψMD∈F be a feasible solution to problem P1, where F denotes the set of all feasible solutions that satisfy the constraints (2). Furthermore, we denote utility Uf as the system’s objective function corresponding to a given configuration f, so problem P1 can be represented by minf∈FUf. Therefore, the equivalent minimum weight independent set (MWIS) problem of P1 is(12)minp≥0∑f∈FpfUf,s.t.∑f∈Fpf=1,where the probability pf indicates the percentage of time that the system is in configuration f. Regarding Uf as the weight of f, the problem is to search for a minimum weighted configuration. Following the Markov approximation framework [6], the log-sum-exp approximation of minf∈FUf yields(13)Umin≈−1βlog∑f∈Fexp−βUf,where β is a positive constant that affects the approximation performance. Let F be the size of set F, the approximation accuracy is known as follows:(14)minf∈FUf−1βlogF≤−1βlog∑f∈Fexp−βUf≤minf∈FUf.It is clear that, asβ⟶∞, the approximation gap approaches 0 and thus the approximation becomes exact.According to [6], the log-sum-exp approximation in (13) is equivalent to solve the following problem P2:(15)P2:minp≥0∑f∈FpfUf+1β∑f∈Fpflogpf,s.t.∑f∈Fpf=1.SinceP2 is a convex problem, we can solve the Karush–Kuhn–Tucker (KKT) conditions [20] and obtain the optimal solution as(16)pf∗=exp−βUf∑f′∈Fexp−βUf′,∀f∈F.However, it is difficult to solve problemP2 directly because this requires complete information on F which is typically unknown due to the large solution space. However, if we can sample the configuration space F from the distribution pf∗ in (16), i.e., time-sharing among different configurations f according to their portions pf∗, we actually solve problem P2 and thus problem P1 approximately [7]. Toward this, the key is to design a problem-specific Markov chain, which models feasible configurations as states, achieves stationary distribution pf∗, and allows parallel construction among the M tasks.


### 4.2. Markov Chain Design

It has been proved that there exists at least one continuous-time time-reversible ergodic Markov chain with stationary distributionpf∗ in (16) and [6]. To construct such a time-reversible Markov chain, we let f,f′∈F be two states of the Markov chain and use qf,f′ as the transition rate from state f to f′. It suffices to design qf,f′ to ensure the following two conditions: (a) any two states are reachable from each other, and (b) the detailed balance equation is satisfied, i.e., pf∗qf,f′=pf′∗qf′,f, ∀f,f′∈F. The above two sufficient requirements allow a large space to design a Markov chain in terms of the state-space structure and transition-matrix design.First, the transition rate between any two states can be set to zero, if they are still reachable from any other states. That is, we only allow direct links between two states that can be reached by performing only one task migration.Second, for two assignments with direct transitions, e.g.,f and f′, we design the transition rate between them as(17)qf,f′=1Mγexp−βUf′maxexp−βUf′,exp−βUf,where γ>0 is a constant denoting the mean time of state transition [6].


### 4.3. Markov Approximation-Based Algorithm

According to Markov approximation [6], in our system, a configuration f consists of M computation tasks using one of its local configurations. If all tasks run individual continuous-time clocks and wait for performance-dependent amounts of time before switching their local configurations, we can implement the target Markov chain such that transitions only happen between two configurations f and f′ when they differ from each other by only one task’s local configuration.The implementation based on our designed Markov chain is shown in Algorithm1. This algorithm is explained as follows. The MD initializes a dedicated thread for each of its computation tasks. At first, each thread randomly selects a feasible target device that satisfies constraint (2) for m∈M. Besides, the CPU frequency ψMD is also randomly picked from the candidate set Ψ. In stage 1, each thread is associated with an exponentially distributed random number with a mean equal to γ and counts down according to this number. In stage 2, when the timer of task m expires, the dedicated thread first sends RESET signals to other threads for notifying them the upcoming potential transition f′ and then randomly generates a new configuration f′ on task assignment and frequency scaling. The thread m will transit to f′ with the probability pf,f′ or stay at the current configuration f with the probability 1−pf,f′. In stage 3, when the dedicated thread serving for a task receives a RESET signal, it terminates its current countdown process and then transits to stage 1 again. Due to the properties of the underlying Markov chain, this algorithm will converge to near-optimal configuration in probability after a sufficient number of time periods.Algorithm 1:The Markov approximation-based algorithm.
(1)
The following procedures execute on the MD.
(2)
procedure
Initialization
(3)
for m∈M do
(4)
xm⟵0, and ym,n⟵0, ∀n∈N
(5)
Randomly assignm to the MD (i.e., xm⟵1) or a MEC server n∈N (i.e., ym,n⟵1)
(6)
end for
(7)
Randomly pick a feasibleψMD from Ψ
(8)
Transit toSTAGE 1
(9)
end procedure
(10)
procedure
Stage 1: Wait (m)
(11)
Generate an exponentially distributed timertm with mean equal to γ
(12)
Begin counting down bytm
(13)
end procedure
(14)
procedure
Stage 2: Hop (m)
(15)
If tm expires then
(16)
SendRESET signals to m′, ∀m′∈M\m.
(17)
Generate a new configurationf′ by randomly selecting another feasible device for m
(18)
if the target device is the MD then
(19)
xm⟵1, and ym,n⟵0, ∀n∈N
(20)
Randomly pick another feasibleψMD′ from Ψ
(21)
elseif the target device is a MEC server n′ then
(22)
xm⟵0, ym,n′⟵1, and ym,n⟵0, ∀n∈N\n′
(23)
end if
(24)
Migrate to the new configurationf′ by the probability of pf,f′=exp−βUf′/maxexp−βUf′,exp−βUf
(25)
end if
(26)
end procedure
(27)
procedure
Stage 3: Reset (m)
(28)
if tm does not expire andm receives a RESET message then
(29)
Terminate its current countdown timer
(30)
Transit toSTAGE 1
(31)
end if
(32)
end procedureAccording topf,f′ in Algorithm 1, we have two typical transition scenarios as follows. First, if Uf≥Uf′, then qf,f′=1. Second, if Uf<Uf′ and β⟶∞, then qf,f′⟶0. Therefore, the design of pf,f′ in (17) is likely to lead the system to a configuration that minimizes the objective in problem P1.Theorem 1.
Algorithm1 realizes a time-reversible Markov chain with the stationary distribution shown in (16).Proof.
From the construction rule for the state-space structure of a Markov chain, we can know that all configurations can reach each other within a finite number of transitions, so the generated Markov chain is irreducible. Moreover, it is a finite-state ergodic Markov chain with a unique stationary distribution. Now we show that the stationary distribution of this Markov chain is exactly (16).
In Algorithm1, the transition probability of task m from f to f′ is pf,f′. Then from a system-wide view, the probability of transition due to the selection of a single task m from the task set M is pf,f′/M. Furthermore, because task assignment is activated according to the countdown timer mechanism with a rate of γ, it follows that the transition rate from state f to f′ is(18)qf,f′=pf,f′Mγ=1Mγexp−βUf′maxexp−βUf′,exp−βUf.
Using (16) and (18), we can obtain that pf∗qf,f′=pf′∗qf′,f, ∀f,f′∈F; that is, the detailed balance equations hold. Finally, we know that the constructed Markov chain is time-reversible, and its stationary distribution is exactly (16) according to Theorem 1.3 and Theorem 1.14 in [21].


### 4.4. Performance Guarantee

In practice, it is possible that we can obtain only an inaccurate measurement or estimate ofUf for any f∈F, due to imprecise measurements or local estimates [8]. As a result, the perturbed Markov chain may not converge to the desired stationary distribution pf∗, but a suboptimal steady-state distribution. This observation motivates us to study on the performance gap in the presence of the perturbation errors.For each configurationf∈F with Uf, we assume that the corresponding perturbation error belongs to the bounded region −Θf,Θf, where Θf is the inaccuracy bound. Then, the perturbed Uf takes only one from the 2nf+1 discrete values Uf−Θf,…,Uf−1/nfΘf,Uf,Uf+1/nfΘf,…,Uf+Θf, where nf is a positive constant. Moreover, with probability δf,j, the perturbed Uf takes the value Uf+1/nfΘf, ∀j∈−nf,…,nf and ∑j=−nfnfδf,j=1.Based on the analysis on perturbation errors in [22], we have the following results.Theorem 2(a).
The stationary distribution of the perturbed Markov chain is(19)p¯f=φfexp−βUf∑f′∈Fφf′exp−βUf′,where φf=∑j=−nfnfδf,jexpβjΘf/nf.Theorem 2(b).
The optimality gaps without and with perturbation errors are shown as follows:(20)0≤Uavg−Umin≤logΨ+MlogN+1β,(21)0≤U¯avg−Umin≤logΨ+MlogN+1β+Θmax,where Umin=minf∈FUf is the optimal system utility for problem P1, Uavg=∑f∈Fpf∗Uf is the expected system utility with the original perfect Markov chain, U¯avg=∑f∈Fp¯fUf is the expected system utility with the perturbed Markov chain, and Θmax=maxf∈FΘf is the maximum perturbation error.Proof (a).
We consider an extended Markov chain in which each statef is expanded to 2nf+1 states f,j, ∀j=−nf,…,0,1,…,nf with the following transition rates:(22)q¯f,j,f′,j′=δf′,j′Mγexp−βUf′+j′/nf′Θf′maxexp−βUf′+j′/nf′Θf′,exp−βUf+j/nfΘf,where δf′,j′, ∀j′=−nf′,…,0,1,…,nf′ is the probability scale on expanded states and ∑j=−nf′nf′δf′,j′=1. This extended Markov chain has a unique stationary distribution since it is irreducible and only has a finite number of states. Denote by pf,j, ∀j=−nf,…,0,1,…,nf, f∈F is the stationary distribution of the states in this extended Markov chain. According to (22) and the detailed balance equations pf,jq¯f,j,f′,j′=pf′,j′q¯f′,j′,f,j, we have:(23)pf,0δf,0exp−βUf=pf′,j′δf′,j′exp−βUf′+j′/nf′Θf′=constant,where f,0 refers to state f with no error.
Using∑f∈F∑j=−nfnfpf,j=1, it follows that(24)pf,j=δf,jexp−βUf+j/nfΘf∑f′∈F∑j′=−nf′nf′δf′,j′exp−βUf′+j′/nf′Θf′.
Denote byφf=∑j=−nfnfδf,jexpβjΘf/nf=∑j=−nfnfδf,jexp−βjΘf/nf. Using (24), we finally have(25)p¯f=∑j=−nfnfpf,j=∑j=−nfnfδf,jexp−βj/nfΘfexp−βUf∑f′∈F∑f′=−nf′nf′δf′,j′exp−βj′/nf′Θf′exp−βUf′,=φfexp−βUf∑f′∈Fφf′exp−βUf′.Proof (b).
First, we prove the bounds on optimality gap for the original Markov chain. Letfmin∈argminf∈FUf, and by the Dirac distribution, we have(26)p˜f=1,iff=fmin,0,otherwise.
Sincepf∗ in (16) is the optimal distribution for problem P2, we have(27)∑f∈Fpf∗Uf+1β∑f∈Fpf∗logpf∗≤∑f∈Fp˜fUf+1β∑f∈Fp˜flogp˜f=Umin.
With Jensen’s inequality, we can obtain(28)∑f∈Fpf∗logpf∗=−∑f∈Fpf∗log1pf∗≥−log∑f∈Fpf∗1pf∗=−logF.
Combining (27) and (28) yields(29)Uavg=∑f∈Fpf∗Uf≥∑f∈Fpf∗Umin=Umin≥Uavg+1β∑f∈Fpf∗logpf∗≥Uavg−1βlogF.
Thus,(30)0≤Uavg−Umin≤1βlogF.
Next, we prove the bounds on optimality gap for the perturbed Markov chain. By part (a), probability distributionp¯ can be regarded as the optimal solution to problem P1 by replacing the utility function Uf by Uf′=Uf−logφf/β. From (20), we have(31)∑f′∈Fp¯f′Uf′−minf′∈FUf′≤1βlogF.
Plugging the values ofUf′ into (31), we obtain(32)∑f∈Fp¯fUf−logφfβ−minf∈FUf−logφfβ≤1βlogF.
According to the definition ofφf, it is easy to know that(33)exp−βΘf≤φf≤expβΘf,∀f∈F.
Therefore,(34)−Θf≤−logφfβ≤Θf.
Combining (32) and (34) yields(35)Umin=minf∈FUf≥minf∈FUf−logφfβ≥∑f∈Fp¯fUf−logφfβ−1βlogF≥∑f∈Fp¯fUf−Θf−1βlogF.
ForU¯avg, we have(36)U¯avg=∑f∈Fp¯fUf≥∑f∈Fp¯fUmin=Umin≥U¯avg−Θf−1βlogF.
Thus,(37)0≤U¯avg−Umin≤1βlogF+Θf≤1βlogF+Θmax.
In general, givenM computation tasks, N MEC servers, and the MD’s local CPU with Ψ frequency levels, the total number of available configurations is bounded by(38)F≤ΨN+1M.
Finally, by plugging (38) into (30) and (37), we prove part (b) of Theorem 2.


## 4.1. Log-Sum-Exp Approximation

Letf=x,y,ψMD∈F be a feasible solution to problem P1, where F denotes the set of all feasible solutions that satisfy the constraints (2). Furthermore, we denote utility Uf as the system’s objective function corresponding to a given configuration f, so problem P1 can be represented by minf∈FUf. Therefore, the equivalent minimum weight independent set (MWIS) problem of P1 is(12)minp≥0∑f∈FpfUf,s.t.∑f∈Fpf=1,where the probability pf indicates the percentage of time that the system is in configuration f. Regarding Uf as the weight of f, the problem is to search for a minimum weighted configuration. Following the Markov approximation framework [6], the log-sum-exp approximation of minf∈FUf yields(13)Umin≈−1βlog∑f∈Fexp−βUf,where β is a positive constant that affects the approximation performance. Let F be the size of set F, the approximation accuracy is known as follows:(14)minf∈FUf−1βlogF≤−1βlog∑f∈Fexp−βUf≤minf∈FUf.It is clear that, asβ⟶∞, the approximation gap approaches 0 and thus the approximation becomes exact.According to [6], the log-sum-exp approximation in (13) is equivalent to solve the following problem P2:(15)P2:minp≥0∑f∈FpfUf+1β∑f∈Fpflogpf,s.t.∑f∈Fpf=1.SinceP2 is a convex problem, we can solve the Karush–Kuhn–Tucker (KKT) conditions [20] and obtain the optimal solution as(16)pf∗=exp−βUf∑f′∈Fexp−βUf′,∀f∈F.However, it is difficult to solve problemP2 directly because this requires complete information on F which is typically unknown due to the large solution space. However, if we can sample the configuration space F from the distribution pf∗ in (16), i.e., time-sharing among different configurations f according to their portions pf∗, we actually solve problem P2 and thus problem P1 approximately [7]. Toward this, the key is to design a problem-specific Markov chain, which models feasible configurations as states, achieves stationary distribution pf∗, and allows parallel construction among the M tasks.


## 4.2. Markov Chain Design

It has been proved that there exists at least one continuous-time time-reversible ergodic Markov chain with stationary distributionpf∗ in (16) and [6]. To construct such a time-reversible Markov chain, we let f,f′∈F be two states of the Markov chain and use qf,f′ as the transition rate from state f to f′. It suffices to design qf,f′ to ensure the following two conditions: (a) any two states are reachable from each other, and (b) the detailed balance equation is satisfied, i.e., pf∗qf,f′=pf′∗qf′,f, ∀f,f′∈F. The above two sufficient requirements allow a large space to design a Markov chain in terms of the state-space structure and transition-matrix design.First, the transition rate between any two states can be set to zero, if they are still reachable from any other states. That is, we only allow direct links between two states that can be reached by performing only one task migration.Second, for two assignments with direct transitions, e.g.,f and f′, we design the transition rate between them as(17)qf,f′=1Mγexp−βUf′maxexp−βUf′,exp−βUf,where γ>0 is a constant denoting the mean time of state transition [6].


## 4.3. Markov Approximation-Based Algorithm

According to Markov approximation [6], in our system, a configuration f consists of M computation tasks using one of its local configurations. If all tasks run individual continuous-time clocks and wait for performance-dependent amounts of time before switching their local configurations, we can implement the target Markov chain such that transitions only happen between two configurations f and f′ when they differ from each other by only one task’s local configuration.The implementation based on our designed Markov chain is shown in Algorithm1. This algorithm is explained as follows. The MD initializes a dedicated thread for each of its computation tasks. At first, each thread randomly selects a feasible target device that satisfies constraint (2) for m∈M. Besides, the CPU frequency ψMD is also randomly picked from the candidate set Ψ. In stage 1, each thread is associated with an exponentially distributed random number with a mean equal to γ and counts down according to this number. In stage 2, when the timer of task m expires, the dedicated thread first sends RESET signals to other threads for notifying them the upcoming potential transition f′ and then randomly generates a new configuration f′ on task assignment and frequency scaling. The thread m will transit to f′ with the probability pf,f′ or stay at the current configuration f with the probability 1−pf,f′. In stage 3, when the dedicated thread serving for a task receives a RESET signal, it terminates its current countdown process and then transits to stage 1 again. Due to the properties of the underlying Markov chain, this algorithm will converge to near-optimal configuration in probability after a sufficient number of time periods.Algorithm 1:The Markov approximation-based algorithm.
(1)
The following procedures execute on the MD.
(2)
procedure
Initialization
(3)
for m∈M do
(4)
xm⟵0, and ym,n⟵0, ∀n∈N
(5)
Randomly assignm to the MD (i.e., xm⟵1) or a MEC server n∈N (i.e., ym,n⟵1)
(6)
end for
(7)
Randomly pick a feasibleψMD from Ψ
(8)
Transit toSTAGE 1
(9)
end procedure
(10)
procedure
Stage 1: Wait (m)
(11)
Generate an exponentially distributed timertm with mean equal to γ
(12)
Begin counting down bytm
(13)
end procedure
(14)
procedure
Stage 2: Hop (m)
(15)
If tm expires then
(16)
SendRESET signals to m′, ∀m′∈M\m.
(17)
Generate a new configurationf′ by randomly selecting another feasible device for m
(18)
if the target device is the MD then
(19)
xm⟵1, and ym,n⟵0, ∀n∈N
(20)
Randomly pick another feasibleψMD′ from Ψ
(21)
elseif the target device is a MEC server n′ then
(22)
xm⟵0, ym,n′⟵1, and ym,n⟵0, ∀n∈N\n′
(23)
end if
(24)
Migrate to the new configurationf′ by the probability of pf,f′=exp−βUf′/maxexp−βUf′,exp−βUf
(25)
end if
(26)
end procedure
(27)
procedure
Stage 3: Reset (m)
(28)
if tm does not expire andm receives a RESET message then
(29)
Terminate its current countdown timer
(30)
Transit toSTAGE 1
(31)
end if
(32)
end procedureAccording topf,f′ in Algorithm 1, we have two typical transition scenarios as follows. First, if Uf≥Uf′, then qf,f′=1. Second, if Uf<Uf′ and β⟶∞, then qf,f′⟶0. Therefore, the design of pf,f′ in (17) is likely to lead the system to a configuration that minimizes the objective in problem P1.Theorem 1.
Algorithm1 realizes a time-reversible Markov chain with the stationary distribution shown in (16).Proof.
From the construction rule for the state-space structure of a Markov chain, we can know that all configurations can reach each other within a finite number of transitions, so the generated Markov chain is irreducible. Moreover, it is a finite-state ergodic Markov chain with a unique stationary distribution. Now we show that the stationary distribution of this Markov chain is exactly (16).
In Algorithm1, the transition probability of task m from f to f′ is pf,f′. Then from a system-wide view, the probability of transition due to the selection of a single task m from the task set M is pf,f′/M. Furthermore, because task assignment is activated according to the countdown timer mechanism with a rate of γ, it follows that the transition rate from state f to f′ is(18)qf,f′=pf,f′Mγ=1Mγexp−βUf′maxexp−βUf′,exp−βUf.
Using (16) and (18), we can obtain that pf∗qf,f′=pf′∗qf′,f, ∀f,f′∈F; that is, the detailed balance equations hold. Finally, we know that the constructed Markov chain is time-reversible, and its stationary distribution is exactly (16) according to Theorem 1.3 and Theorem 1.14 in [21].


## 4.4. Performance Guarantee

In practice, it is possible that we can obtain only an inaccurate measurement or estimate ofUf for any f∈F, due to imprecise measurements or local estimates [8]. As a result, the perturbed Markov chain may not converge to the desired stationary distribution pf∗, but a suboptimal steady-state distribution. This observation motivates us to study on the performance gap in the presence of the perturbation errors.For each configurationf∈F with Uf, we assume that the corresponding perturbation error belongs to the bounded region −Θf,Θf, where Θf is the inaccuracy bound. Then, the perturbed Uf takes only one from the 2nf+1 discrete values Uf−Θf,…,Uf−1/nfΘf,Uf,Uf+1/nfΘf,…,Uf+Θf, where nf is a positive constant. Moreover, with probability δf,j, the perturbed Uf takes the value Uf+1/nfΘf, ∀j∈−nf,…,nf and ∑j=−nfnfδf,j=1.Based on the analysis on perturbation errors in [22], we have the following results.Theorem 2(a).
The stationary distribution of the perturbed Markov chain is(19)p¯f=φfexp−βUf∑f′∈Fφf′exp−βUf′,where φf=∑j=−nfnfδf,jexpβjΘf/nf.Theorem 2(b).
The optimality gaps without and with perturbation errors are shown as follows:(20)0≤Uavg−Umin≤logΨ+MlogN+1β,(21)0≤U¯avg−Umin≤logΨ+MlogN+1β+Θmax,where Umin=minf∈FUf is the optimal system utility for problem P1, Uavg=∑f∈Fpf∗Uf is the expected system utility with the original perfect Markov chain, U¯avg=∑f∈Fp¯fUf is the expected system utility with the perturbed Markov chain, and Θmax=maxf∈FΘf is the maximum perturbation error.Proof (a).
We consider an extended Markov chain in which each statef is expanded to 2nf+1 states f,j, ∀j=−nf,…,0,1,…,nf with the following transition rates:(22)q¯f,j,f′,j′=δf′,j′Mγexp−βUf′+j′/nf′Θf′maxexp−βUf′+j′/nf′Θf′,exp−βUf+j/nfΘf,where δf′,j′, ∀j′=−nf′,…,0,1,…,nf′ is the probability scale on expanded states and ∑j=−nf′nf′δf′,j′=1. This extended Markov chain has a unique stationary distribution since it is irreducible and only has a finite number of states. Denote by pf,j, ∀j=−nf,…,0,1,…,nf, f∈F is the stationary distribution of the states in this extended Markov chain. According to (22) and the detailed balance equations pf,jq¯f,j,f′,j′=pf′,j′q¯f′,j′,f,j, we have:(23)pf,0δf,0exp−βUf=pf′,j′δf′,j′exp−βUf′+j′/nf′Θf′=constant,where f,0 refers to state f with no error.
Using∑f∈F∑j=−nfnfpf,j=1, it follows that(24)pf,j=δf,jexp−βUf+j/nfΘf∑f′∈F∑j′=−nf′nf′δf′,j′exp−βUf′+j′/nf′Θf′.
Denote byφf=∑j=−nfnfδf,jexpβjΘf/nf=∑j=−nfnfδf,jexp−βjΘf/nf. Using (24), we finally have(25)p¯f=∑j=−nfnfpf,j=∑j=−nfnfδf,jexp−βj/nfΘfexp−βUf∑f′∈F∑f′=−nf′nf′δf′,j′exp−βj′/nf′Θf′exp−βUf′,=φfexp−βUf∑f′∈Fφf′exp−βUf′.Proof (b).
First, we prove the bounds on optimality gap for the original Markov chain. Letfmin∈argminf∈FUf, and by the Dirac distribution, we have(26)p˜f=1,iff=fmin,0,otherwise.
Sincepf∗ in (16) is the optimal distribution for problem P2, we have(27)∑f∈Fpf∗Uf+1β∑f∈Fpf∗logpf∗≤∑f∈Fp˜fUf+1β∑f∈Fp˜flogp˜f=Umin.
With Jensen’s inequality, we can obtain(28)∑f∈Fpf∗logpf∗=−∑f∈Fpf∗log1pf∗≥−log∑f∈Fpf∗1pf∗=−logF.
Combining (27) and (28) yields(29)Uavg=∑f∈Fpf∗Uf≥∑f∈Fpf∗Umin=Umin≥Uavg+1β∑f∈Fpf∗logpf∗≥Uavg−1βlogF.
Thus,(30)0≤Uavg−Umin≤1βlogF.
Next, we prove the bounds on optimality gap for the perturbed Markov chain. By part (a), probability distributionp¯ can be regarded as the optimal solution to problem P1 by replacing the utility function Uf by Uf′=Uf−logφf/β. From (20), we have(31)∑f′∈Fp¯f′Uf′−minf′∈FUf′≤1βlogF.
Plugging the values ofUf′ into (31), we obtain(32)∑f∈Fp¯fUf−logφfβ−minf∈FUf−logφfβ≤1βlogF.
According to the definition ofφf, it is easy to know that(33)exp−βΘf≤φf≤expβΘf,∀f∈F.
Therefore,(34)−Θf≤−logφfβ≤Θf.
Combining (32) and (34) yields(35)Umin=minf∈FUf≥minf∈FUf−logφfβ≥∑f∈Fp¯fUf−logφfβ−1βlogF≥∑f∈Fp¯fUf−Θf−1βlogF.
ForU¯avg, we have(36)U¯avg=∑f∈Fp¯fUf≥∑f∈Fp¯fUmin=Umin≥U¯avg−Θf−1βlogF.
Thus,(37)0≤U¯avg−Umin≤1βlogF+Θf≤1βlogF+Θmax.
In general, givenM computation tasks, N MEC servers, and the MD’s local CPU with Ψ frequency levels, the total number of available configurations is bounded by(38)F≤ΨN+1M.
Finally, by plugging (38) into (30) and (37), we prove part (b) of Theorem 2.


## 5. Simulation Results and Analysis

### 5.1. Simulation Setup

In this section, we evaluate the performance of our Markov approximation-based algorithm (denoted by MA) by simulations based on parameters from references [5, 23, 24]. Table 1 lists the default values for simulation parameters in our experiments, if not otherwise specified.Table 1
Simulation parameters.
Parameter
Definition
Default value
M
Total number of computation tasks
100
N
Total number of MEC servers
4
a
m
Required number of CPU cycles for processing taskm
330
×
b
m cycles
b
m
Size of the input data of taskm
0.5 MB
c
m
Size of the output data of taskm
0.2
×
b
m
θ
Power parameter in CPU energy consumption model
3
ϒ
1
,
ϒ
2
Power parameter in CPU energy consumption model
1.25
×
10
−
26
,
0
ψ
min
,
ψ
max
CPU frequency range of the MD
2.0
,
8.0
×
10
8 cycles/sec
Ψ
Total number of CPU DVFS levels
7
ψ
n
Service rates provided by MEC servers
2,2.2
,
2.4
,
2.6
×
10
9 cycles/sec
r
n
UL
Uplink data rate between the MD and MEC servern
10
∼
20 Mbps
r
n
DL
Downlink data rate between the MD and MEC servern
10
∼
20 Mbps
P
tx
Transmitting power of MD
1.26 Watt
P
rx
Receiving power of MD
1.18 Watt
ξ
T
Scalar weight of tasks’ execution time
0.5
ξ
E
Scalar weight of the MD’s energy consumption
1
−
ξ
T
β
Positive constant that controls approximation accuracy
50
γ
Mean value for the countdown timer
200In order to evaluate the MA algorithm performance, we compare it with the following three baseline approaches:(1)
Exhaustive Search (ES): the optimal solution is found by enumerating all possible configurations, which leads to high computation complexity and only feasible for small-sized problems.(2)
Random Assignment (RA): the solutions are obtained by randomly assigning computation tasks and setting CPU frequency.(3)
Local Processing (LP): all computation tasks are processed by the CPU of MD, and the frequency is optimal to the assignment.To eliminate the influence of randomness, the experiments of MA, RA, and LP are independently carried out multiple times for each given setting. For clear comparison, we choose to show either the average of results or the range of results in the figures. Similar to [7], the convergence time of MA is defined as the time at which the difference between two consecutive values does not exceed 0.5%.


### 5.2. Performance Evaluation

#### 5.2.1. Convergence of the MA Algorithm

At first, we examine the convergence of MA under different settings. Figure1 shows the convergence of our MA approach in a low-load scenario with the number of tasks M=10. The results show that MA converges quickly to near optimal after 50 iterations, independent of problem size. The computation complexity is far less than that of enumerating all 7×510 combinatorial possibilities in the ES approach. We further investigate the performance of MA under different ratios of ξE and ξT. The value of ξE is chosen such that ξE=10ω×ξT, where ω∈0,±0.4,±0.8,±1.2,±1.6,±2. Figure 2 shows that changing these two scalar weights has little impact on the convergence of MA and confirms the existence of approximation gap in (14).Figure 1
Convergence of MA algorithm in a low-load scenario.Figure 2
Impact ofξE/ξT on convergence of MA algorithm.Figure 3
System utilities of different algorithms.As the problem size becomes even larger (e.g,M=100), ES will take considerable time (e.g., several hours or even more) to search for the optimal solution from 7×5100 options, while MA converges after about 1100 iterations. In such a high-load scenario, we compare MA with ES, as well as the best results obtained by RA and LP from multiple independent runs. As shown in Figure 3, no matter how many MEC servers are used (i.e, N=2 or 4), MA can gradually converge to optimal as iteration grows. It is obvious that more MEC servers can provide more offloading options and further improve the energy and latency performance. Although the best result of RA in Figure 3 approaches the optimal utility found by ES, RA is of no practical value because it is generally not able to guarantee deterministic outputs. Among the four approaches, LP has the largest utility value, indicating that MEC offloading is essential for shortening execution time and reducing energy consumption in such a case.


#### 5.2.2. Impact of Link Rates

In Figure4, we compare the performance of algorithms with regard to different data transmission conditions. The link rates are controlled in three distinct ranges, namely, low rate (0.5 Mbps∼1 Mbps), medium rate (2 Mbps∼10 Mbps), and high rate (20 Mbps∼50 Mbps). From Figure 4, the MA algorithm can always converge, and its convergence time decreases as the link rates increase. We can also observe from Figure 4(a) that MA converges to the same result as that of LP, no matter how many MEC servers are used. That is because when the link rates are low, almost all tasks are processed locally by the MD’s CPU since the offloading costs on energy and latency are much higher than those of local computation. As the link rates increase, the offloading costs decreases because of lower transmission duration, making it more preferable to offload tasks to MEC servers by using our MA algorithm (as shown in Figures 4(b) and 4(c)).Figure 4
Algorithm comparison under different link rates. (a) 0.5 Mbps∼1 Mbps. (b) 2 Mbps∼10 Mbps. (c) 20 Mbps∼50 Mbps.
(a)
(b)
(c)


#### 5.2.3. Impact of Parameterβ

Figure5 demonstrates the impact of β on system utility and convergence time. The dashed arrows with different colors in Figure 5 indicate the iterative time when the convergence is achieved by MA with a given parameter β. It is shown that as β increases from 4 to 50, and MA will eventually obtain an approximate utility closer to the optimal value obtained by ES, but the corresponding convergence time will become longer. This allows us to make flexible choices among various tradeoff points between system optimization and convergence time. These observations in Figure 5 are consistent with (20) in Theorem 2.Figure 5
Impact ofβ on system utility and convergence time.Figure 6
Impact of perturbation errors on optimality gap.


#### 5.2.4. Impact of Perturbation Errors

As mentioned in Section4.4, in practice, we usually obtain inaccurate Uf due to estimation errors. To verify (21) in Theorem 2, we carry out experiments to study the impact of perturbation errors on the performance of MA. To do this, we add different degrees of random errors (±10%∼±50%, uniformly distributed) to rnUL and rnDL for all n. In the experiments, we let MA make all control decisions based on the perturbed link rates but use the actual values to calculate the objective utility. We find that MA can indeed converge to a suboptimal solution even when perturbation errors exist. To characterize the optimality gap, we choose the optimal result obtained by ES without perturbation errors as the baseline and use this baseline to examine the worst-case (i.e., maximum) utility achieved by MA in multiple independent runs. Figure 6 shows the difference ratios of utilities under different error rates. From the figure, we find that as the error rate varies from 10% to 50%, the optimal gap keeps increasing from 2.15% to 33.0%. These results corroborate Theorem 2 that the further the estimations are from the true values, the poorer the performance MA achieves. However, when the error rate is smaller than some threshold value (e.g., 20%), the optimal gap is very small.


#### 5.2.5. Tradeoff between Latency and Energy

In Figure7, we study the tradeoff between task execution time and mobile energy consumption in the MA algorithm. As we did in the case of Figure 2, totally 11 different combinations of ξE and ξT are chosen for comparison in Figure 7. For each curve in Figure 7, the markers are laid out from left to right in the order of ω. Correspondingly, the left-most marker corresponds to the condition ω=−2, and the right-most marker corresponds to the condition ω=2. From this figure, it is feasible to tune the two scalar weights for achieving a desirable tradeoff between latency and energy. However, we can notice that when ω grows greater than some threshold (e.g., ω>0 when N=2), the decreasing trend of energy consumption becomes smooth while execution latency keeps increasing. Therefore, the values of ξE and ξT should be carefully chosen to achieve a satisfactory energy-latency tradeoff. On the other hand, increasing N leads to significant reductions in both latency and energy, as the curve shifts down to the bottom-left corner of the plot. This observation confirms again that it is beneficial to provide more than one MEC server to the MD for task offloading. Nevertheless, the performance improvement gradually diminishes when N becomes larger.Figure 7
Energy-latency tradeoff under different values ofω and N.


## 5.1. Simulation Setup

In this section, we evaluate the performance of our Markov approximation-based algorithm (denoted by MA) by simulations based on parameters from references [5, 23, 24]. Table 1 lists the default values for simulation parameters in our experiments, if not otherwise specified.Table 1
Simulation parameters.
Parameter
Definition
Default value
M
Total number of computation tasks
100
N
Total number of MEC servers
4
a
m
Required number of CPU cycles for processing taskm
330
×
b
m cycles
b
m
Size of the input data of taskm
0.5 MB
c
m
Size of the output data of taskm
0.2
×
b
m
θ
Power parameter in CPU energy consumption model
3
ϒ
1
,
ϒ
2
Power parameter in CPU energy consumption model
1.25
×
10
−
26
,
0
ψ
min
,
ψ
max
CPU frequency range of the MD
2.0
,
8.0
×
10
8 cycles/sec
Ψ
Total number of CPU DVFS levels
7
ψ
n
Service rates provided by MEC servers
2,2.2
,
2.4
,
2.6
×
10
9 cycles/sec
r
n
UL
Uplink data rate between the MD and MEC servern
10
∼
20 Mbps
r
n
DL
Downlink data rate between the MD and MEC servern
10
∼
20 Mbps
P
tx
Transmitting power of MD
1.26 Watt
P
rx
Receiving power of MD
1.18 Watt
ξ
T
Scalar weight of tasks’ execution time
0.5
ξ
E
Scalar weight of the MD’s energy consumption
1
−
ξ
T
β
Positive constant that controls approximation accuracy
50
γ
Mean value for the countdown timer
200In order to evaluate the MA algorithm performance, we compare it with the following three baseline approaches:(1)
Exhaustive Search (ES): the optimal solution is found by enumerating all possible configurations, which leads to high computation complexity and only feasible for small-sized problems.(2)
Random Assignment (RA): the solutions are obtained by randomly assigning computation tasks and setting CPU frequency.(3)
Local Processing (LP): all computation tasks are processed by the CPU of MD, and the frequency is optimal to the assignment.To eliminate the influence of randomness, the experiments of MA, RA, and LP are independently carried out multiple times for each given setting. For clear comparison, we choose to show either the average of results or the range of results in the figures. Similar to [7], the convergence time of MA is defined as the time at which the difference between two consecutive values does not exceed 0.5%.


## 5.2. Performance Evaluation

### 5.2.1. Convergence of the MA Algorithm

At first, we examine the convergence of MA under different settings. Figure1 shows the convergence of our MA approach in a low-load scenario with the number of tasks M=10. The results show that MA converges quickly to near optimal after 50 iterations, independent of problem size. The computation complexity is far less than that of enumerating all 7×510 combinatorial possibilities in the ES approach. We further investigate the performance of MA under different ratios of ξE and ξT. The value of ξE is chosen such that ξE=10ω×ξT, where ω∈0,±0.4,±0.8,±1.2,±1.6,±2. Figure 2 shows that changing these two scalar weights has little impact on the convergence of MA and confirms the existence of approximation gap in (14).Figure 1
Convergence of MA algorithm in a low-load scenario.Figure 2
Impact ofξE/ξT on convergence of MA algorithm.Figure 3
System utilities of different algorithms.As the problem size becomes even larger (e.g,M=100), ES will take considerable time (e.g., several hours or even more) to search for the optimal solution from 7×5100 options, while MA converges after about 1100 iterations. In such a high-load scenario, we compare MA with ES, as well as the best results obtained by RA and LP from multiple independent runs. As shown in Figure 3, no matter how many MEC servers are used (i.e, N=2 or 4), MA can gradually converge to optimal as iteration grows. It is obvious that more MEC servers can provide more offloading options and further improve the energy and latency performance. Although the best result of RA in Figure 3 approaches the optimal utility found by ES, RA is of no practical value because it is generally not able to guarantee deterministic outputs. Among the four approaches, LP has the largest utility value, indicating that MEC offloading is essential for shortening execution time and reducing energy consumption in such a case.


### 5.2.2. Impact of Link Rates

In Figure4, we compare the performance of algorithms with regard to different data transmission conditions. The link rates are controlled in three distinct ranges, namely, low rate (0.5 Mbps∼1 Mbps), medium rate (2 Mbps∼10 Mbps), and high rate (20 Mbps∼50 Mbps). From Figure 4, the MA algorithm can always converge, and its convergence time decreases as the link rates increase. We can also observe from Figure 4(a) that MA converges to the same result as that of LP, no matter how many MEC servers are used. That is because when the link rates are low, almost all tasks are processed locally by the MD’s CPU since the offloading costs on energy and latency are much higher than those of local computation. As the link rates increase, the offloading costs decreases because of lower transmission duration, making it more preferable to offload tasks to MEC servers by using our MA algorithm (as shown in Figures 4(b) and 4(c)).Figure 4
Algorithm comparison under different link rates. (a) 0.5 Mbps∼1 Mbps. (b) 2 Mbps∼10 Mbps. (c) 20 Mbps∼50 Mbps.
(a)
(b)
(c)


### 5.2.3. Impact of Parameterβ

Figure5 demonstrates the impact of β on system utility and convergence time. The dashed arrows with different colors in Figure 5 indicate the iterative time when the convergence is achieved by MA with a given parameter β. It is shown that as β increases from 4 to 50, and MA will eventually obtain an approximate utility closer to the optimal value obtained by ES, but the corresponding convergence time will become longer. This allows us to make flexible choices among various tradeoff points between system optimization and convergence time. These observations in Figure 5 are consistent with (20) in Theorem 2.Figure 5
Impact ofβ on system utility and convergence time.Figure 6
Impact of perturbation errors on optimality gap.


### 5.2.4. Impact of Perturbation Errors

As mentioned in Section4.4, in practice, we usually obtain inaccurate Uf due to estimation errors. To verify (21) in Theorem 2, we carry out experiments to study the impact of perturbation errors on the performance of MA. To do this, we add different degrees of random errors (±10%∼±50%, uniformly distributed) to rnUL and rnDL for all n. In the experiments, we let MA make all control decisions based on the perturbed link rates but use the actual values to calculate the objective utility. We find that MA can indeed converge to a suboptimal solution even when perturbation errors exist. To characterize the optimality gap, we choose the optimal result obtained by ES without perturbation errors as the baseline and use this baseline to examine the worst-case (i.e., maximum) utility achieved by MA in multiple independent runs. Figure 6 shows the difference ratios of utilities under different error rates. From the figure, we find that as the error rate varies from 10% to 50%, the optimal gap keeps increasing from 2.15% to 33.0%. These results corroborate Theorem 2 that the further the estimations are from the true values, the poorer the performance MA achieves. However, when the error rate is smaller than some threshold value (e.g., 20%), the optimal gap is very small.


### 5.2.5. Tradeoff between Latency and Energy

In Figure7, we study the tradeoff between task execution time and mobile energy consumption in the MA algorithm. As we did in the case of Figure 2, totally 11 different combinations of ξE and ξT are chosen for comparison in Figure 7. For each curve in Figure 7, the markers are laid out from left to right in the order of ω. Correspondingly, the left-most marker corresponds to the condition ω=−2, and the right-most marker corresponds to the condition ω=2. From this figure, it is feasible to tune the two scalar weights for achieving a desirable tradeoff between latency and energy. However, we can notice that when ω grows greater than some threshold (e.g., ω>0 when N=2), the decreasing trend of energy consumption becomes smooth while execution latency keeps increasing. Therefore, the values of ξE and ξT should be carefully chosen to achieve a satisfactory energy-latency tradeoff. On the other hand, increasing N leads to significant reductions in both latency and energy, as the curve shifts down to the bottom-left corner of the plot. This observation confirms again that it is beneficial to provide more than one MEC server to the MD for task offloading. Nevertheless, the performance improvement gradually diminishes when N becomes larger.Figure 7
Energy-latency tradeoff under different values ofω and N.


## 5.2.1. Convergence of the MA Algorithm

At first, we examine the convergence of MA under different settings. Figure1 shows the convergence of our MA approach in a low-load scenario with the number of tasks M=10. The results show that MA converges quickly to near optimal after 50 iterations, independent of problem size. The computation complexity is far less than that of enumerating all 7×510 combinatorial possibilities in the ES approach. We further investigate the performance of MA under different ratios of ξE and ξT. The value of ξE is chosen such that ξE=10ω×ξT, where ω∈0,±0.4,±0.8,±1.2,±1.6,±2. Figure 2 shows that changing these two scalar weights has little impact on the convergence of MA and confirms the existence of approximation gap in (14).Figure 1
Convergence of MA algorithm in a low-load scenario.Figure 2
Impact ofξE/ξT on convergence of MA algorithm.Figure 3
System utilities of different algorithms.As the problem size becomes even larger (e.g,M=100), ES will take considerable time (e.g., several hours or even more) to search for the optimal solution from 7×5100 options, while MA converges after about 1100 iterations. In such a high-load scenario, we compare MA with ES, as well as the best results obtained by RA and LP from multiple independent runs. As shown in Figure 3, no matter how many MEC servers are used (i.e, N=2 or 4), MA can gradually converge to optimal as iteration grows. It is obvious that more MEC servers can provide more offloading options and further improve the energy and latency performance. Although the best result of RA in Figure 3 approaches the optimal utility found by ES, RA is of no practical value because it is generally not able to guarantee deterministic outputs. Among the four approaches, LP has the largest utility value, indicating that MEC offloading is essential for shortening execution time and reducing energy consumption in such a case.


## 5.2.2. Impact of Link Rates

In Figure4, we compare the performance of algorithms with regard to different data transmission conditions. The link rates are controlled in three distinct ranges, namely, low rate (0.5 Mbps∼1 Mbps), medium rate (2 Mbps∼10 Mbps), and high rate (20 Mbps∼50 Mbps). From Figure 4, the MA algorithm can always converge, and its convergence time decreases as the link rates increase. We can also observe from Figure 4(a) that MA converges to the same result as that of LP, no matter how many MEC servers are used. That is because when the link rates are low, almost all tasks are processed locally by the MD’s CPU since the offloading costs on energy and latency are much higher than those of local computation. As the link rates increase, the offloading costs decreases because of lower transmission duration, making it more preferable to offload tasks to MEC servers by using our MA algorithm (as shown in Figures 4(b) and 4(c)).Figure 4
Algorithm comparison under different link rates. (a) 0.5 Mbps∼1 Mbps. (b) 2 Mbps∼10 Mbps. (c) 20 Mbps∼50 Mbps.
(a)
(b)
(c)


## 5.2.3. Impact of Parameterβ

Figure5 demonstrates the impact of β on system utility and convergence time. The dashed arrows with different colors in Figure 5 indicate the iterative time when the convergence is achieved by MA with a given parameter β. It is shown that as β increases from 4 to 50, and MA will eventually obtain an approximate utility closer to the optimal value obtained by ES, but the corresponding convergence time will become longer. This allows us to make flexible choices among various tradeoff points between system optimization and convergence time. These observations in Figure 5 are consistent with (20) in Theorem 2.Figure 5
Impact ofβ on system utility and convergence time.Figure 6
Impact of perturbation errors on optimality gap.


## 5.2.4. Impact of Perturbation Errors

As mentioned in Section4.4, in practice, we usually obtain inaccurate Uf due to estimation errors. To verify (21) in Theorem 2, we carry out experiments to study the impact of perturbation errors on the performance of MA. To do this, we add different degrees of random errors (±10%∼±50%, uniformly distributed) to rnUL and rnDL for all n. In the experiments, we let MA make all control decisions based on the perturbed link rates but use the actual values to calculate the objective utility. We find that MA can indeed converge to a suboptimal solution even when perturbation errors exist. To characterize the optimality gap, we choose the optimal result obtained by ES without perturbation errors as the baseline and use this baseline to examine the worst-case (i.e., maximum) utility achieved by MA in multiple independent runs. Figure 6 shows the difference ratios of utilities under different error rates. From the figure, we find that as the error rate varies from 10% to 50%, the optimal gap keeps increasing from 2.15% to 33.0%. These results corroborate Theorem 2 that the further the estimations are from the true values, the poorer the performance MA achieves. However, when the error rate is smaller than some threshold value (e.g., 20%), the optimal gap is very small.


## 5.2.5. Tradeoff between Latency and Energy

In Figure7, we study the tradeoff between task execution time and mobile energy consumption in the MA algorithm. As we did in the case of Figure 2, totally 11 different combinations of ξE and ξT are chosen for comparison in Figure 7. For each curve in Figure 7, the markers are laid out from left to right in the order of ω. Correspondingly, the left-most marker corresponds to the condition ω=−2, and the right-most marker corresponds to the condition ω=2. From this figure, it is feasible to tune the two scalar weights for achieving a desirable tradeoff between latency and energy. However, we can notice that when ω grows greater than some threshold (e.g., ω>0 when N=2), the decreasing trend of energy consumption becomes smooth while execution latency keeps increasing. Therefore, the values of ξE and ξT should be carefully chosen to achieve a satisfactory energy-latency tradeoff. On the other hand, increasing N leads to significant reductions in both latency and energy, as the curve shifts down to the bottom-left corner of the plot. This observation confirms again that it is beneficial to provide more than one MEC server to the MD for task offloading. Nevertheless, the performance improvement gradually diminishes when N becomes larger.Figure 7
Energy-latency tradeoff under different values ofω and N.


## 6. Conclusion

This paper addresses the computation offloading issue in a multiserver mobile edge computing scenario, where a MD can offload its computation tasks to multiple MEC servers. We formulate this problem as the joint optimization of task assignment and frequency scaling, aimed at minimizing the tradeoff between the MD’s energy consumption and total tasks’ execution time. In order to solve this NP-hard problem, a Markov approximation-based algorithm is devised to find a near-optimal solution, where the result has only a small and bounded gap with the optimal one. Through simulation experiments with many practical concerns, we verify that our algorithm can converge to near-optimal performance and ensure desirable robustness and scalability. Furthermore, this algorithm significantly outperforms other benchmark algorithms such as exhaustive search and local processing.For the future work, we are going to examine our Markov approximation-based approach with multiple MDs to obtain more general conclusions. Further, we shall extend our approach to an online case, where the problem can be solved with dynamic arrival and leave of MDs. It is also worthwhile to evaluate the work in a real test-bed of mobile edge computing.



---

*Source: 8172698-2019-01-23.xml*