# Dynamic Service Request Scheduling for Mobile Edge Computing Systems

Authors: Ying Chen; Yongchao Zhang; Xin Chen
Journal: Wireless Communications and Mobile Computing
 (2018)

---

## Abstract

Nowadays, mobile services (applications) running on terminal devices are becoming more and more computation-intensive. Offloading the service requests from terminal devices to cloud computing can be a good solution, but it would put a high burden on the network. Edge computing is an emerging technology to solve this problem, which places servers at the edge of the network. Dynamic scheduling of offloaded service requests in mobile edge computing systems is a key issue. It faces challenges due to the dynamic nature and uncertainty of service request patterns. In this article, we propose a Dynamic Service Request Scheduling (DSRS) algorithm, which makes request scheduling decisions to optimize scheduling cost while providing performance guarantees. The DSRS algorithm can be implemented in an online and distributed way. We present mathematical analysis which shows that the DSRS algorithm can achieve arbitrary tradeoff between scheduling cost and performance. Experiments are also carried out to show the effectiveness of the DSRS algorithm.


---

## Body

## 1. Introduction

With the rapid development of Information Technology and increasing promotion of terminal devices [1], the mobile services (applications) running on terminal devices are becoming more and more complex and computation-intensive [2, 3]. However, the computing capacity and battery life of terminal devices are generally limited, and these devices cannot afford to process all these service requests locally on devices. To solve this problem, some researches propose to offload the service requests from terminal devices to cloud computing, which has more computing resources and larger capacity [4–8]. Nevertheless, cloud computing is usually located remotely that is far away from terminal devices. Besides, with the increasing popularity of mobile services running on terminal devices, scheduling all the offloaded service requests to cloud computing can put a significant burden on the networks [9, 10]. To meet this challenge, recent researches have been proposed to put edge servers with computing capacities at the edge of the networks in close proximity to terminal devices. Mobile Edge Computing (MEC) is an emerging technology based on this idea [11–14], and it has drawn extensive attention from both academy and industry [15–18].One of the key issues in MEC research is how to schedule service requests [2, 19, 20]: when a large number of service requests are offloaded, how to schedule service requests among multiple MEC systems in order to reduce scheduling cost while providing performance guarantees. It is intuitive that there exist tradeoffs between scheduling cost and performance. Besides, the service request scheduling problem among multiple MEC systems is challenging due to several reasons. Firstly, as terminal devices are moving and the service environment varies over time [21, 22], how to make dynamic request scheduling decisions in accordance with the uncertainty of request patterns and changing environment is a great challenge [23]. Secondly, with the increasing promotion of terminal devices and mobile services, both the number of terminal devices and mobile services are rising dramatically, making the service request scheduling problem more complicated.Some existing researches have studied the service request scheduling problem in MEC systems. Reference [24] modelled the server in the MEC as one M/M/1 queue. Reference [2] assumed the offloaded service requests arrived at the MEC system according to a Poisson process. These works assumed the request arrival followed certain distribution. However, in reality, the request arrival process is highly dynamic, and the statistical information of request arrival can hardly be obtained or precisely predicted [25, 26]. Besides, with the number of terminal devices and mobile services increasing, traditional centralized optimization techniques such as combination optimization and dynamic programming may suffer from high-complexity and result in long execution time.In this article, we introduce a dynamic online service request scheduling mechanism which requires no prior information of the statistical information of request arrivals. Specifically, the request scheduling among multiple MEC systems is formulated as an optimization problem, and the goal is to minimize request scheduling cost while providing performance guarantees. Based on Lyapunov optimization techniques, we propose a Dynamic Service Request Scheduling (DSRS) algorithm. DSRS uses a parameterV to control the tradeoff between scheduling cost and queue length. Mathematical analysis is presented which proves that DSRS is O(1/V)-optimal with respect to the average scheduling cost while still bounding the average queue length by O(V). Experiments are also conducted which demonstrate that DSRS can make dynamic control decisions to adjust to variable environments and achieve the tradeoff between scheduling cost and queue length.The remainder of this article is organized as follows. In Section2, we present the system model for dynamic request scheduling among multiple MEC systems and formulate the optimization problem. In Section 3, based on Lyapunov optimization techniques, we propose an online and Dynamic Service Request Scheduling algorithm. Theoretical analysis of the scheduling algorithm is presented in Section 4. Experiments are conducted to evaluate the efficiency and effectiveness of the scheduling algorithm in Section 5. We conclude this article in Section 6.


## 2. System Model

### 2.1. Overview

Considern mobile edge computing (MEC) systems. Each MEC system has an edge server virtualized to m virtual machines to process offloaded requests of m types of services from the terminal devices [25, 27]. More specifically, the i-th virtual machine on each edge server in the MEC system serves the offloaded requests for the i-th type of service. Let I be the collection of indexes for applications and J be the collection of indexes for edge server in the MEC systems. Without loss of generality, the edge servers in different MEC systems are supposed to be heterogeneous. We consider a time-slotted model and the length of time slot is denoted by τ. The main notations in this section are listed in Table 1.Table 1
Notations and definitions.
Notation Definition I Services set. J MEC systems set. Ai(t) Number of requests for servicei in time slot t. aij(t) Number of requests for servicei that are scheduled to the j-th MEC system in time slot t. bij(t) Number of requests for servicei that can be served by the j-th MEC system in time slot t. γij(t) Unit cost of scheduling requests for servicei to the j-th MEC system. Qij(t) Queue length of servicei on the j-th MEC system in time slot t. g(t) Scheduling cost for all the services in time slott.


### 2.2. Problem Formulation

#### 2.2.1. Service Request Scheduling

In each time slott∈{0,1,…,T-1}, a number of service requests for the m types of services are offloaded. Let Ai(t) be the number of requests for service i offloaded to the MEC systems in time slot t. In our article, we require no prior knowledge of the statistics of Ai(t), which is generally hard to obtain or precisely predict in real-life. aij(t) represents the number of requests for service i that are scheduled to the edge server in the j-th MEC system in time slot t. aij(t) is the request scheduling control variable. It should be satisfied that(1)∑j∈Jaijt=Ait,∀i∈I.The request scheduling method in our article will make use of the diversity of different MEC systems to provide service in order to reduce scheduling cost while providing performance guarantees.


#### 2.2.2. Scheduling Cost

Letγij(t) be the unit cost of scheduling requests for service i to the j-th MEC system. γij(t) can be different among different services i and different MEC systems j. It can also vary across time for other factors such as traffic, wireless fading, the available resources, etc. The request scheduling cost of service i in time slot t can be calculated as ∑j∈Jγij(t)aij(t). The total scheduling cost for all the services can be expressed as(2)gt=∑i∈I∑j∈Jγijtaijt.Instead of studying the instantaneous scheduling cost, we focus on the long-term average cost. The time-average scheduling cost across time slotst∈{0,1,…,T-1} can be expressed as(3)g=limT→∞1T∑t=0T-1Egt.g is the minimization objective of the request scheduling problem in this article.


#### 2.2.3. Performance

Queueing delay is one of the most important performance metrics. According toLittle’s Law, queueing delay is in proportion to the number of requests waiting in the queue. Thus, we seek to reduce queue length and maintain low congestion states. Let Qij(t) represent the queue length of service i in the j-th MEC system in time slot t. bij(t) denotes the number of requests for service i that can be served by the j-th MEC system. Thus, the queue length Qij(t) evolves as(4)Qijt+1=max⁡Qijt-bijt,0+aijt.To reduce queueing delay and maintain system stability, we seek to bound the average queue length. Let the time-average queue length across thet∈{0,1,…,T-1} slots represented by qij. The service request scheduling method in this article bounds the average queue length as(5)qij=limT→∞1T∑t=0T-1EQijt<ζ,∃ζ∈R+.


#### 2.2.4. Unified Framework

To combine scheduling cost and performance, the request scheduling problem in this article is formulated as(6)minimizeg=limT→∞1T∑t=0T-1Egt;subject to constraints (1), (5).Solving problem (6) offline requires the future information (such as requests arrival information, scheduling cost information) which is generally hard to obtain or precisely predict in practice. Thus, we propose an online Dynamic Service Request Scheduling algorithm to solve the problem, which will be shown in Section 3.


## 2.1. Overview

Considern mobile edge computing (MEC) systems. Each MEC system has an edge server virtualized to m virtual machines to process offloaded requests of m types of services from the terminal devices [25, 27]. More specifically, the i-th virtual machine on each edge server in the MEC system serves the offloaded requests for the i-th type of service. Let I be the collection of indexes for applications and J be the collection of indexes for edge server in the MEC systems. Without loss of generality, the edge servers in different MEC systems are supposed to be heterogeneous. We consider a time-slotted model and the length of time slot is denoted by τ. The main notations in this section are listed in Table 1.Table 1
Notations and definitions.
Notation Definition I Services set. J MEC systems set. Ai(t) Number of requests for servicei in time slot t. aij(t) Number of requests for servicei that are scheduled to the j-th MEC system in time slot t. bij(t) Number of requests for servicei that can be served by the j-th MEC system in time slot t. γij(t) Unit cost of scheduling requests for servicei to the j-th MEC system. Qij(t) Queue length of servicei on the j-th MEC system in time slot t. g(t) Scheduling cost for all the services in time slott.


## 2.2. Problem Formulation

### 2.2.1. Service Request Scheduling

In each time slott∈{0,1,…,T-1}, a number of service requests for the m types of services are offloaded. Let Ai(t) be the number of requests for service i offloaded to the MEC systems in time slot t. In our article, we require no prior knowledge of the statistics of Ai(t), which is generally hard to obtain or precisely predict in real-life. aij(t) represents the number of requests for service i that are scheduled to the edge server in the j-th MEC system in time slot t. aij(t) is the request scheduling control variable. It should be satisfied that(1)∑j∈Jaijt=Ait,∀i∈I.The request scheduling method in our article will make use of the diversity of different MEC systems to provide service in order to reduce scheduling cost while providing performance guarantees.


### 2.2.2. Scheduling Cost

Letγij(t) be the unit cost of scheduling requests for service i to the j-th MEC system. γij(t) can be different among different services i and different MEC systems j. It can also vary across time for other factors such as traffic, wireless fading, the available resources, etc. The request scheduling cost of service i in time slot t can be calculated as ∑j∈Jγij(t)aij(t). The total scheduling cost for all the services can be expressed as(2)gt=∑i∈I∑j∈Jγijtaijt.Instead of studying the instantaneous scheduling cost, we focus on the long-term average cost. The time-average scheduling cost across time slotst∈{0,1,…,T-1} can be expressed as(3)g=limT→∞1T∑t=0T-1Egt.g is the minimization objective of the request scheduling problem in this article.


### 2.2.3. Performance

Queueing delay is one of the most important performance metrics. According toLittle’s Law, queueing delay is in proportion to the number of requests waiting in the queue. Thus, we seek to reduce queue length and maintain low congestion states. Let Qij(t) represent the queue length of service i in the j-th MEC system in time slot t. bij(t) denotes the number of requests for service i that can be served by the j-th MEC system. Thus, the queue length Qij(t) evolves as(4)Qijt+1=max⁡Qijt-bijt,0+aijt.To reduce queueing delay and maintain system stability, we seek to bound the average queue length. Let the time-average queue length across thet∈{0,1,…,T-1} slots represented by qij. The service request scheduling method in this article bounds the average queue length as(5)qij=limT→∞1T∑t=0T-1EQijt<ζ,∃ζ∈R+.


### 2.2.4. Unified Framework

To combine scheduling cost and performance, the request scheduling problem in this article is formulated as(6)minimizeg=limT→∞1T∑t=0T-1Egt;subject to constraints (1), (5).Solving problem (6) offline requires the future information (such as requests arrival information, scheduling cost information) which is generally hard to obtain or precisely predict in practice. Thus, we propose an online Dynamic Service Request Scheduling algorithm to solve the problem, which will be shown in Section 3.


## 2.2.1. Service Request Scheduling

In each time slott∈{0,1,…,T-1}, a number of service requests for the m types of services are offloaded. Let Ai(t) be the number of requests for service i offloaded to the MEC systems in time slot t. In our article, we require no prior knowledge of the statistics of Ai(t), which is generally hard to obtain or precisely predict in real-life. aij(t) represents the number of requests for service i that are scheduled to the edge server in the j-th MEC system in time slot t. aij(t) is the request scheduling control variable. It should be satisfied that(1)∑j∈Jaijt=Ait,∀i∈I.The request scheduling method in our article will make use of the diversity of different MEC systems to provide service in order to reduce scheduling cost while providing performance guarantees.


## 2.2.2. Scheduling Cost

Letγij(t) be the unit cost of scheduling requests for service i to the j-th MEC system. γij(t) can be different among different services i and different MEC systems j. It can also vary across time for other factors such as traffic, wireless fading, the available resources, etc. The request scheduling cost of service i in time slot t can be calculated as ∑j∈Jγij(t)aij(t). The total scheduling cost for all the services can be expressed as(2)gt=∑i∈I∑j∈Jγijtaijt.Instead of studying the instantaneous scheduling cost, we focus on the long-term average cost. The time-average scheduling cost across time slotst∈{0,1,…,T-1} can be expressed as(3)g=limT→∞1T∑t=0T-1Egt.g is the minimization objective of the request scheduling problem in this article.


## 2.2.3. Performance

Queueing delay is one of the most important performance metrics. According toLittle’s Law, queueing delay is in proportion to the number of requests waiting in the queue. Thus, we seek to reduce queue length and maintain low congestion states. Let Qij(t) represent the queue length of service i in the j-th MEC system in time slot t. bij(t) denotes the number of requests for service i that can be served by the j-th MEC system. Thus, the queue length Qij(t) evolves as(4)Qijt+1=max⁡Qijt-bijt,0+aijt.To reduce queueing delay and maintain system stability, we seek to bound the average queue length. Let the time-average queue length across thet∈{0,1,…,T-1} slots represented by qij. The service request scheduling method in this article bounds the average queue length as(5)qij=limT→∞1T∑t=0T-1EQijt<ζ,∃ζ∈R+.


## 2.2.4. Unified Framework

To combine scheduling cost and performance, the request scheduling problem in this article is formulated as(6)minimizeg=limT→∞1T∑t=0T-1Egt;subject to constraints (1), (5).Solving problem (6) offline requires the future information (such as requests arrival information, scheduling cost information) which is generally hard to obtain or precisely predict in practice. Thus, we propose an online Dynamic Service Request Scheduling algorithm to solve the problem, which will be shown in Section 3.


## 3. Dynamic Request Scheduling Algorithm Design

In this section, based on the Lyapunov optimization framework [28], we decompose the original optimization problem into a series of independent subproblems. Then, we design a Dynamic Service Request Scheduling algorithm to solve these subproblems in a distribute way.


### 3.1. Problem Transformation Using Lyapunov techniques

Based on Lyanuov optimization techniques, we defineΘ(t)=(Qij(t)) as the queue length matrix of the MEC systems. Then, we denote L(Θ(t)) as the Lyanuov function as follows, which is a scalar measure of the queue congestion state in the system,(7)LΘt=12∑i∈I∑j∈JQij2t.A small value ofL(Θ(t)) indicates that the queue lengths of all MECs are small, which represents a low congestion state of the MEC systems according to theLittle’s Law. In order to reduce queue length and maintain system stability, we seek to keep the Lyanuov function at a small value. Then, we define theconditional Lyapunov driftΔ(Θ(t)),(8)ΔΘt=ELΘt+1-LΘt∣Θt.By reducing the value ofΔ(Θ(t)), we can push the Lyanuov function towards to a small value. To integrate scheduling cost and queue length in the MEC systems, we define thedrift plus cost according to Lyapunov optimization framework, which is expressed as (9)ΔΘt+VEgt∣Θt.The parameterV can be considered as the tradeoff parameter between the scheduling cost and queue length, which can be determined by service providers or users according to their requirements in real applications. Next in Theorem 1, we show that thedrift plus cost is upper bounded if the service arrival rate can be upper bounded.Theorem 1 (bounding drift plus cost).
In each time slott, under any algorithm, for all possible values of Θ(t) and any parameter value of V, if there exits a peak value Aimax that upper bounds the number of requests arrived in each time slot, the drift plus cost can be upper bounded by(10)ΔΘt+VEgt∣Θt≤B+∑i∈I∑j∈JQijtEaijt-bijt∣Θt+V∑i∈I∑j∈JEaijtγijt∣Θt,where B=1/2[∑i∈I(Aimax)2+∑i∈I∑j∈Jb^ij2] is a constant.Proof.
By squaring the both sides of (4) and applying the inequality that (max[Qij(t)-bij(t),0])2≤(Qij(t)-bij(t))2, we have(11)Qij2t+1≤Qijt-bijt2+aij2t+2aijtmaxQijt-bijt,0.
Then, we defineb-ij(t) as the actual number of requests for service i served by the j-th MEC system in time slot t,(12)b-ijt=bijt,bijt≤QijtQijt,otherwise.We can obtain that max[Qij(t)-bij(t),0]=Qij(t)-b-ij(t) and rewrite (11) as follows:(13)Qij2t+1≤Qij2t+aij2t+bij2t+2Qijtaijt-bijt-2aijtb-ijt.Because aij(t)b-ij(t)≥0, we have(14)12Qij2t+1-Qij2t≤12aij2t+bij2t+Qijtaijt-bijt.
Taking the expectations on the condition ofΘ(t) to both sides in (14) and summing over i∈I and j∈J, it can be obtained that(15)ΔΘt≤12∑i∈I∑j∈JEaij2t+bij2t∣Θt+∑i∈I∑j∈JQijtEaijt-bijt∣Θt.
Since it holds that∑j∈Jaij(t)=Ai(t) and Ai(t)≤Aimax, we have(16)∑j∈JEaij2t∣Θt≤EAi2t∣Θt≤Aimax2.In addition, we define b^ij as the upper bound of bij(t) over all the time slots. We can obtain that(17)∑i∈I∑j∈JEaij2t+bij2t∣Θt≤∑i∈IAimax2+∑i∈I∑j∈Jb^ij2.
By addingVE{g(t)∣Θ(t)} to both sides and letting B take the value of 1/2[∑i∈I(Aimax)2]+∑i∈I∑j∈Jb^ij2, it can be obtained that(18)ΔΘt+VEgt∣Θt≤B+VEgt∣Θt+∑i∈I∑j∈JQijtEaijt-bijt∣Θt.
Substituting (2) into the right-hand-side (R.H.S.) of (18), we can obtain (10).


### 3.2. Dynamic Request Scheduling Algorithm

Following the design principles of Lyapunov optimization techniques, we design an efficient Dynamic Service Request Scheduling (DSRS) algorithm to minimize the upper bound ofdrift plus cost in each time slot t. By decomposing the minimization of upper bound problem into a series of independent subproblems, our DSRS algorithm optimizes the average scheduling cost concurrently in a distributed way. In addition, it will be proven that DSRS algorithm can achieve a long-term time-average scheduling cost that is arbitrarily close to the optimal value while maintaining the stability of the MEC systems.In each time slott, based on the current queue length matrix Θ(t) of the MEC systems, the DSRS algorithm makes request scheduling decisions aij(t) to minimize the upper bound of R.H.S. of (10). Since B and bij can be considered as constant in the optimization problem, we can rewrite the minimization of upper bound as(19)minaijt∑i∈I∑j∈JaijtQijt+Vaijtγijt.subject to(20)∑j∈Jaijt=Ait,∀i∈I.As the request scheduling decisionsaij(t) are independent among different services, the above centralized minimization problem (19) can be decomposed into the following subproblem (21) for each service i∈I, i.e.,(21)minaijt∑j∈JaijtQijt+Vγijt.subject to(22)∑j∈Jaijt=Ait.Problem (21) can be regarded as a generalized min-weight problem, where the number of requests scheduled to the MEC systems is weighted by the value of Qij(t)+Vγij(t). Therefore, for each service i∈I, the optimal solution is to schedule all the requests to the MEC system with the minimum value of Qij(t)+Vγij(t); i.e.,(23)aijt=Ait,j=j∗0,otherwisewhere j∗∈argmin⁡(Qij(t)+Vγij(t)) for all j∈J.Remark.There exist tradeoffs between the scheduling cost and queue length of the MEC systems. Scheduling all the service requests to the MEC system with low cost can reduce the overall scheduling cost; however, the queue length of the MEC system can be very large. The DSRS algorithm combines scheduling cost and queue length, and Qij(t)+Vγij(t) can be regarded as the penalty factor for each MEC system. Recall that V represents the tradeoff between scheduling cost and queue length. The intuition of the optimal scheduling policy obtained by the DSRS algorithm is to minimize the penalty function of the MEC systems in each time slot. In this way, the DSRS algorithm can reduce both the scheduling cost and the queue length. In addition, by changing the value of V, the DSRS algorithm can achieve the arbitrary tradeoff between scheduling cost and queue length.After the scheduling decisionsaij(t) are determined, the queue length Qij(t) updates according to (4). The detailed algorithm is shown in Algorithm 1.Algorithm 1:Dynamic Service Request Scheduling (DSRS).
1:  In the beginning of each time slott, observe the current queue length Qij(t). 2:for all  i∈I  do 3:Set auxiliary variable MinWeight=-∞; 4:Set j∗=1; 5:for all  j∈J  do 6:Calculate the penalty factor pfj=Qij(t)+Vγij(t); 7:if  pfj<MinWeight  then 8: j∗=j; 9:end if 10:end for 11:for all  j∈J  do 12:ifj==j∗  then 13:Set aij(t)=Ai(t); 14:else 15:Set aij(t)=0; 16:end if 17:end for 18:end for


## 3.1. Problem Transformation Using Lyapunov techniques

Based on Lyanuov optimization techniques, we defineΘ(t)=(Qij(t)) as the queue length matrix of the MEC systems. Then, we denote L(Θ(t)) as the Lyanuov function as follows, which is a scalar measure of the queue congestion state in the system,(7)LΘt=12∑i∈I∑j∈JQij2t.A small value ofL(Θ(t)) indicates that the queue lengths of all MECs are small, which represents a low congestion state of the MEC systems according to theLittle’s Law. In order to reduce queue length and maintain system stability, we seek to keep the Lyanuov function at a small value. Then, we define theconditional Lyapunov driftΔ(Θ(t)),(8)ΔΘt=ELΘt+1-LΘt∣Θt.By reducing the value ofΔ(Θ(t)), we can push the Lyanuov function towards to a small value. To integrate scheduling cost and queue length in the MEC systems, we define thedrift plus cost according to Lyapunov optimization framework, which is expressed as (9)ΔΘt+VEgt∣Θt.The parameterV can be considered as the tradeoff parameter between the scheduling cost and queue length, which can be determined by service providers or users according to their requirements in real applications. Next in Theorem 1, we show that thedrift plus cost is upper bounded if the service arrival rate can be upper bounded.Theorem 1 (bounding drift plus cost).
In each time slott, under any algorithm, for all possible values of Θ(t) and any parameter value of V, if there exits a peak value Aimax that upper bounds the number of requests arrived in each time slot, the drift plus cost can be upper bounded by(10)ΔΘt+VEgt∣Θt≤B+∑i∈I∑j∈JQijtEaijt-bijt∣Θt+V∑i∈I∑j∈JEaijtγijt∣Θt,where B=1/2[∑i∈I(Aimax)2+∑i∈I∑j∈Jb^ij2] is a constant.Proof.
By squaring the both sides of (4) and applying the inequality that (max[Qij(t)-bij(t),0])2≤(Qij(t)-bij(t))2, we have(11)Qij2t+1≤Qijt-bijt2+aij2t+2aijtmaxQijt-bijt,0.
Then, we defineb-ij(t) as the actual number of requests for service i served by the j-th MEC system in time slot t,(12)b-ijt=bijt,bijt≤QijtQijt,otherwise.We can obtain that max[Qij(t)-bij(t),0]=Qij(t)-b-ij(t) and rewrite (11) as follows:(13)Qij2t+1≤Qij2t+aij2t+bij2t+2Qijtaijt-bijt-2aijtb-ijt.Because aij(t)b-ij(t)≥0, we have(14)12Qij2t+1-Qij2t≤12aij2t+bij2t+Qijtaijt-bijt.
Taking the expectations on the condition ofΘ(t) to both sides in (14) and summing over i∈I and j∈J, it can be obtained that(15)ΔΘt≤12∑i∈I∑j∈JEaij2t+bij2t∣Θt+∑i∈I∑j∈JQijtEaijt-bijt∣Θt.
Since it holds that∑j∈Jaij(t)=Ai(t) and Ai(t)≤Aimax, we have(16)∑j∈JEaij2t∣Θt≤EAi2t∣Θt≤Aimax2.In addition, we define b^ij as the upper bound of bij(t) over all the time slots. We can obtain that(17)∑i∈I∑j∈JEaij2t+bij2t∣Θt≤∑i∈IAimax2+∑i∈I∑j∈Jb^ij2.
By addingVE{g(t)∣Θ(t)} to both sides and letting B take the value of 1/2[∑i∈I(Aimax)2]+∑i∈I∑j∈Jb^ij2, it can be obtained that(18)ΔΘt+VEgt∣Θt≤B+VEgt∣Θt+∑i∈I∑j∈JQijtEaijt-bijt∣Θt.
Substituting (2) into the right-hand-side (R.H.S.) of (18), we can obtain (10).


## 3.2. Dynamic Request Scheduling Algorithm

Following the design principles of Lyapunov optimization techniques, we design an efficient Dynamic Service Request Scheduling (DSRS) algorithm to minimize the upper bound ofdrift plus cost in each time slot t. By decomposing the minimization of upper bound problem into a series of independent subproblems, our DSRS algorithm optimizes the average scheduling cost concurrently in a distributed way. In addition, it will be proven that DSRS algorithm can achieve a long-term time-average scheduling cost that is arbitrarily close to the optimal value while maintaining the stability of the MEC systems.In each time slott, based on the current queue length matrix Θ(t) of the MEC systems, the DSRS algorithm makes request scheduling decisions aij(t) to minimize the upper bound of R.H.S. of (10). Since B and bij can be considered as constant in the optimization problem, we can rewrite the minimization of upper bound as(19)minaijt∑i∈I∑j∈JaijtQijt+Vaijtγijt.subject to(20)∑j∈Jaijt=Ait,∀i∈I.As the request scheduling decisionsaij(t) are independent among different services, the above centralized minimization problem (19) can be decomposed into the following subproblem (21) for each service i∈I, i.e.,(21)minaijt∑j∈JaijtQijt+Vγijt.subject to(22)∑j∈Jaijt=Ait.Problem (21) can be regarded as a generalized min-weight problem, where the number of requests scheduled to the MEC systems is weighted by the value of Qij(t)+Vγij(t). Therefore, for each service i∈I, the optimal solution is to schedule all the requests to the MEC system with the minimum value of Qij(t)+Vγij(t); i.e.,(23)aijt=Ait,j=j∗0,otherwisewhere j∗∈argmin⁡(Qij(t)+Vγij(t)) for all j∈J.Remark.There exist tradeoffs between the scheduling cost and queue length of the MEC systems. Scheduling all the service requests to the MEC system with low cost can reduce the overall scheduling cost; however, the queue length of the MEC system can be very large. The DSRS algorithm combines scheduling cost and queue length, and Qij(t)+Vγij(t) can be regarded as the penalty factor for each MEC system. Recall that V represents the tradeoff between scheduling cost and queue length. The intuition of the optimal scheduling policy obtained by the DSRS algorithm is to minimize the penalty function of the MEC systems in each time slot. In this way, the DSRS algorithm can reduce both the scheduling cost and the queue length. In addition, by changing the value of V, the DSRS algorithm can achieve the arbitrary tradeoff between scheduling cost and queue length.After the scheduling decisionsaij(t) are determined, the queue length Qij(t) updates according to (4). The detailed algorithm is shown in Algorithm 1.Algorithm 1:Dynamic Service Request Scheduling (DSRS).
1:  In the beginning of each time slott, observe the current queue length Qij(t). 2:for all  i∈I  do 3:Set auxiliary variable MinWeight=-∞; 4:Set j∗=1; 5:for all  j∈J  do 6:Calculate the penalty factor pfj=Qij(t)+Vγij(t); 7:if  pfj<MinWeight  then 8: j∗=j; 9:end if 10:end for 11:for all  j∈J  do 12:ifj==j∗  then 13:Set aij(t)=Ai(t); 14:else 15:Set aij(t)=0; 16:end if 17:end for 18:end for


## 4. Algorithm Analysis

In this section, we present mathematical analysis of the boundary of the time-average queue length and scheduling cost of our DSRS algorithm. It can be proven that our algorithm can achieve the scheduling cost arbitrarily close to the optimal value while maintaining the stability of the MEC systems. LetQ- denote the long-term time-average queue length,(24)Q-=limT→∞1T∑t=0T-1∑i∈I∑j∈JEQijt.We present in Lemma2 that if the arrival Ai(t) is independent and identically distributed (i.i.d.) over time slots, there exists a randomized policy π∗ which can achieve the minimum cost g∗ defined in (3), where the control decision aij(t) follows certain fixed probability distribution independent of the queue length matrix Θ(t).Lemma 2.
For any service request arrival rateλ∈Λ, where Λ is the capacity region of the system, if the arrival Ai(t) is i.i.d. over time slots, there exists a randomized policy π∗ that determines the control decision aij(t) in each time slot t and achieves the following:(25)Egπ∗t=g∗λ;E∑j∈Jaijπ∗t≤E∑j∈Jbijt.where g∗(λ) denotes the minimum time-average cost under the arrival rate λ.Proof.
Lemma2 can be proven by Caratheodory’s theorem in [28], we omit the detailed proof here for simplicity and brevity.Since it is assumed that there exists upper boundAimax of the service request arrival rate, there also exists upper bound g^ and lower bound gˇ of the objective g. Then, we derive the boundary of queue length and scheduling cost of the DSRS algorithm based on Lemma 2.Theorem 3.
Assume that there existsε satisfying λ+ε∈Λ, then, under our DSRS algorithm, for any value of the parameter V, the time-average queue length defined in (24) is bounded as (26)Q-≤B+Vg^-gˇε.
Furthermore, the time-average system scheduling cost can be bounded by (27), which shows the cost derived by our DSRS algorithm can approach the optimal value by increasing the parameter V. Here, B is the constant defined in Theorem 1.(27)gDSRS≤g∗+BV.Proof.
Since it holds thatλ+ε∈Λ, we can obtain that there exists a randomized policy π′ which satisfies (28) and (29) according to Lemma 2.(28)Egπ′t=g∗λ+ε;(29)E∑j∈Jaijπ′t≤E∑j∈Jbijt-ε.
As our DSRS algorithm can achieve the minimum value of the R.H.S of (10) among all feasible policies (including policy π′), it can be obtained that(30)ΔΘt+VEgt∣Θt≤B+VEgπ′t∣Θt+∑i∈I∑j∈JQijtEaijπ′t-bijt∣Θt.
Substituting (28) and (29) into the R.H.S. of (30), taking expectations on both sides, and then using iterated expectations, we can yield(31)ELΘt+1-LΘt+VEgt≤B+Vg∗λ+ε-ε∑i∈I∑j∈JEQijt.
MovingVE{g(t)} to the R.H.S. of (31), it can be obtained that(32)ELΘt+1-LΘt≤B+Vg∗λ+ε-Egt-ε∑i∈I∑j∈JEQijt≤B+Vg^-gˇ-ε∑i∈I∑j∈JEQijt.
To be general, we assume the queue length is empty whent=0. By summing both sides of (32) over t∈{0,1,…T-1} and applying the fact that L(Θ(t))≥0, we can obtain(33)ε∑t=0T-1∑i∈I∑j∈JEQijt≤B+Vg^-gˇT-ELΘT≤B+Vg^-gˇT.
Dividing both sides of (33) by εT and taking a lim as T→∞ yield (26).
By summing both sides of (31) over t∈{0,1,…T-1} and applying the fact that E{Qij(t)}≥0, it can be obtained(34)V∑t=0T-1Egt≤Vg∗λ+ε+BT.
Dividing both sides of (34) by VT, we have(35)1T∑t=0T-1Egt≤g∗λ+ε+BV.
Taking a lim of (35) as T→∞, applying Lebesgue’s dominated convergence theorem, and letting ε→0 yield (27).Remark.Theorem 3 shows that our DSRS algorithm can achieve a [O(1/V),O(V)] tradeoff between the time-average scheduling cost and queue length. According to (27), the gap between the time-average scheduling cost obtained by our DSRS algorithm and the optimal value is within O(1/V). By setting the value of V sufficiently large, the DSRS algorithm can approach the optimal scheduling cost. However, a large V will cause a large queue backlog of the MEC systems. Nevertheless, the queue length obtained by our DSRS algorithm is also bounded according to (26). And constraint (5) can be satisfied by letting ζ take the value of B+V(g^-gˇ)/ε.Then, we analyze the time complexity of the DSRS algorithm. According to Algorithm1, for the two inner loops (line 5-10 and line 11-17), DSRS algorithm traverses each edge server once. Therefore, each loop terminates in O(n) operations, where n is the number of edge servers. For the outer loop (line 1-18), since the request scheduling of different service applications is independent, it terminates in O(n) operations. Thus, the time complexity of the DSRS algorithm is O(n).


## 5. Evaluation

In this section, we conduct experiments to evaluate our DSRS algorithm. First, we analyze the impact of parameters. Then, we present comparison experiments which show the effectiveness of our DSRS algorithm.In the experiments, we consider 4 MEC systems, each with an edge server providing services for the offloaded requests. There are two types of heterogeneous services. For each servicei∈I, the request arrival process is generated according to Poisson distribution with arrival rate λi [29]. Note that the DSRS algorithm actually requires no knowledge of the statistical information of request arrivals. The computing capacity of the MEC systems is set as βi·λi where βi>1. Without loss of generality, we assume the MEC systems are heterogeneous with different computing capacities. And the unit scheduling costs of different MEC systems are set to be positively related to its computing capacity.


### 5.1. Parameter Analysis

#### 5.1.1. Effect of Tradeoff Parameter

Figures1 and 2 show the time-average scheduling cost and queue length of the MEC systems with different values of V. In Figure 1, it can be seen that the scheduling cost decreases as the value of V increases, which is in accordance with (27) in Theorem 3. This is because as V increases, more weight is put on scheduling cost, and the DSRS algorithm would schedule more service requests to the MEC system with lower unit cost in order to reduce the overall scheduling cost. However, Figure 2 shows that the queue length also rises with the increase of V, which is consistent with (26) in Theorem 3. Nevertheless, the queue length would stabilize gradually with far more increase of V. Together with Figures 1 and 2, we can see that the DSRS algorithm can make a tradeoff between scheduling cost and queue length by adjusting the value of V.Figure 1
Scheduling cost with different values ofV.Figure 2
Queue length with different values ofV.


#### 5.1.2. Effect of Service Request Arrival Rate

We analyze the effect of service request arrival rate on the scheduling cost and queue length. In the experiments, for each applicationi∈I, we scale the service request arrival rate up or down to p·λi. We consider three different cases, where p = 1, 1.2 and 1.4, respectively. Figures 3 and 4 show that both of the scheduling cost and queue length increase as the request arrival rate increases. Nevertheless, the queue length can stabilize quickly with the increase of service request arrival rate. This shows that our DSRS algorithm can dynamically adjust the request scheduling decisions according to different service request arrivals and maintain the stability of the MEC systems.Figure 3
Scheduling cost with different arrival rates.Figure 4
Queue length with different arrival rates.


#### 5.1.3. Effect of Unit Scheduling Cost

To analyze the effect of unit scheduling cost on the MEC systems, we scale the unit scheduling cost up or down toq·γij. We consider three different cases, where q = 1, 1.2 and 1.4, respectively. We can see from Figure 5 that the overall scheduling cost rises as the unit scheduling cost increases, since the scheduling cost of each request increases. In Figure 6, we can see that the queue length of the MEC systems also increases with the increase of unit scheduling cost. The reason is that our DSRS algorithm tries to achieve low scheduling cost by scheduling more requests to the MEC with smaller unit scheduling cost. However, this will lead to the larger queue backlog in some MEC systems.Figure 5
Scheduling cost with different unit scheduling costs.Figure 6
Queue length with different unit scheduling costs.


### 5.2. Comparison Experiment

We conduct comparison experiment and compare our DSRS algorithm with Randomized algorithm to evaluate the effectiveness of the DSRS algorithm. The Randomized algorithm schedules all the service requests to each MEC system randomly. The scheduling costs and queue lengths of the two algorithms are shown in Figures7 and 8, respectively.Figure 7
Scheduling cost under different algorithms.Figure 8
Queue length under different algorithms.We can see from Figure7 that the scheduling cost of our DSRS algorithm is smaller than that of Randomized algorithm, which shows the effectiveness of our DSRS algorithm in reducing cost. In Figure 8, we can observe that the queue length of the Randomized algorithm is slightly smaller than our DSRS algorithm at the very beginning. However, as time goes by, the queue length of the Randomized algorithm increases continuously along with the time. The queue length of our DSRS algorithm stabilizes quickly and maintains at a small level. The reason is that our DSRS algorithm can adjust scheduling decisions dynamically according to the current queue backlog and maintain low congestion state in the MEC systems. Together with Figures 7 and 8, we can see the effectiveness of our DSRS algorithm in optimizing both scheduling cost and queue length.


## 5.1. Parameter Analysis

### 5.1.1. Effect of Tradeoff Parameter

Figures1 and 2 show the time-average scheduling cost and queue length of the MEC systems with different values of V. In Figure 1, it can be seen that the scheduling cost decreases as the value of V increases, which is in accordance with (27) in Theorem 3. This is because as V increases, more weight is put on scheduling cost, and the DSRS algorithm would schedule more service requests to the MEC system with lower unit cost in order to reduce the overall scheduling cost. However, Figure 2 shows that the queue length also rises with the increase of V, which is consistent with (26) in Theorem 3. Nevertheless, the queue length would stabilize gradually with far more increase of V. Together with Figures 1 and 2, we can see that the DSRS algorithm can make a tradeoff between scheduling cost and queue length by adjusting the value of V.Figure 1
Scheduling cost with different values ofV.Figure 2
Queue length with different values ofV.


### 5.1.2. Effect of Service Request Arrival Rate

We analyze the effect of service request arrival rate on the scheduling cost and queue length. In the experiments, for each applicationi∈I, we scale the service request arrival rate up or down to p·λi. We consider three different cases, where p = 1, 1.2 and 1.4, respectively. Figures 3 and 4 show that both of the scheduling cost and queue length increase as the request arrival rate increases. Nevertheless, the queue length can stabilize quickly with the increase of service request arrival rate. This shows that our DSRS algorithm can dynamically adjust the request scheduling decisions according to different service request arrivals and maintain the stability of the MEC systems.Figure 3
Scheduling cost with different arrival rates.Figure 4
Queue length with different arrival rates.


### 5.1.3. Effect of Unit Scheduling Cost

To analyze the effect of unit scheduling cost on the MEC systems, we scale the unit scheduling cost up or down toq·γij. We consider three different cases, where q = 1, 1.2 and 1.4, respectively. We can see from Figure 5 that the overall scheduling cost rises as the unit scheduling cost increases, since the scheduling cost of each request increases. In Figure 6, we can see that the queue length of the MEC systems also increases with the increase of unit scheduling cost. The reason is that our DSRS algorithm tries to achieve low scheduling cost by scheduling more requests to the MEC with smaller unit scheduling cost. However, this will lead to the larger queue backlog in some MEC systems.Figure 5
Scheduling cost with different unit scheduling costs.Figure 6
Queue length with different unit scheduling costs.


## 5.1.1. Effect of Tradeoff Parameter

Figures1 and 2 show the time-average scheduling cost and queue length of the MEC systems with different values of V. In Figure 1, it can be seen that the scheduling cost decreases as the value of V increases, which is in accordance with (27) in Theorem 3. This is because as V increases, more weight is put on scheduling cost, and the DSRS algorithm would schedule more service requests to the MEC system with lower unit cost in order to reduce the overall scheduling cost. However, Figure 2 shows that the queue length also rises with the increase of V, which is consistent with (26) in Theorem 3. Nevertheless, the queue length would stabilize gradually with far more increase of V. Together with Figures 1 and 2, we can see that the DSRS algorithm can make a tradeoff between scheduling cost and queue length by adjusting the value of V.Figure 1
Scheduling cost with different values ofV.Figure 2
Queue length with different values ofV.


## 5.1.2. Effect of Service Request Arrival Rate

We analyze the effect of service request arrival rate on the scheduling cost and queue length. In the experiments, for each applicationi∈I, we scale the service request arrival rate up or down to p·λi. We consider three different cases, where p = 1, 1.2 and 1.4, respectively. Figures 3 and 4 show that both of the scheduling cost and queue length increase as the request arrival rate increases. Nevertheless, the queue length can stabilize quickly with the increase of service request arrival rate. This shows that our DSRS algorithm can dynamically adjust the request scheduling decisions according to different service request arrivals and maintain the stability of the MEC systems.Figure 3
Scheduling cost with different arrival rates.Figure 4
Queue length with different arrival rates.


## 5.1.3. Effect of Unit Scheduling Cost

To analyze the effect of unit scheduling cost on the MEC systems, we scale the unit scheduling cost up or down toq·γij. We consider three different cases, where q = 1, 1.2 and 1.4, respectively. We can see from Figure 5 that the overall scheduling cost rises as the unit scheduling cost increases, since the scheduling cost of each request increases. In Figure 6, we can see that the queue length of the MEC systems also increases with the increase of unit scheduling cost. The reason is that our DSRS algorithm tries to achieve low scheduling cost by scheduling more requests to the MEC with smaller unit scheduling cost. However, this will lead to the larger queue backlog in some MEC systems.Figure 5
Scheduling cost with different unit scheduling costs.Figure 6
Queue length with different unit scheduling costs.


## 5.2. Comparison Experiment

We conduct comparison experiment and compare our DSRS algorithm with Randomized algorithm to evaluate the effectiveness of the DSRS algorithm. The Randomized algorithm schedules all the service requests to each MEC system randomly. The scheduling costs and queue lengths of the two algorithms are shown in Figures7 and 8, respectively.Figure 7
Scheduling cost under different algorithms.Figure 8
Queue length under different algorithms.We can see from Figure7 that the scheduling cost of our DSRS algorithm is smaller than that of Randomized algorithm, which shows the effectiveness of our DSRS algorithm in reducing cost. In Figure 8, we can observe that the queue length of the Randomized algorithm is slightly smaller than our DSRS algorithm at the very beginning. However, as time goes by, the queue length of the Randomized algorithm increases continuously along with the time. The queue length of our DSRS algorithm stabilizes quickly and maintains at a small level. The reason is that our DSRS algorithm can adjust scheduling decisions dynamically according to the current queue backlog and maintain low congestion state in the MEC systems. Together with Figures 7 and 8, we can see the effectiveness of our DSRS algorithm in optimizing both scheduling cost and queue length.


## 6. Conclusion

In this article, we study dynamic request scheduling for MEC systems. We formulate it as an optimization problem, and the goal is to optimize scheduling cost while providing performance guarantee. We propose the DSRS algorithm to solve the optimization problem, which transforms it to a series of subproblems and solves each one efficiently in a distributed way. Mathematical analysis is presented which demonstrates that the DSRS algorithm can approach the optimal scheduling cost while bounding the queue length. Parameter analysis experiments and comparison experiments are both conducted to verify the effectiveness of the DSRS algorithm.



---

*Source: 1324897-2018-09-13.xml*