# A Computing Offloading Game for Mobile Devices and Edge Cloud Servers

Authors: Meiwen Li; Qingtao Wu; Junlong Zhu; Ruijuan Zheng; Mingchuan Zhang
Journal: Wireless Communications and Mobile Computing
 (2018)

---

## Abstract

Computing offloading of mobile devices (MDs) through cloud is a greatly effective way to solve the problem of local resource constraints. However, cloud servers are usually located far away from MDs leading to a long response time. To this end, edge cloud servers (ECSs) provide a shorter response time due to being closer to MDs. In this paper, we propose a computing offloading game for MDs and ECSs. We prove the existence of a Stackelberg equilibrium in the game. In addition, we propose two algorithms, F-SGA and C-SGA, for delay-sensitive and compute-intensive applications, respectively. Moreover, the response time is reduced by F-SGA, which makes decisions quickly. An optimal decision is obtained by C-SGA, which achieves the equilibrium. Both algorithms above proposed can adjust the computing resource and utility of system users according to parameters control in computing offloading. The simulation results show that the game significantly saves the computing resources and response time of both the MD and the ECSs during the computing offloading process.


---

## Body

## 1. Introduction

The popularity of the Internet of Things (IoT) allows people to enjoy the convenience of the Internet in most scenarios of daily life. Especially for mobile devices (MDs), network services provide convenience and functional possibilities. However, functional and computationally intensive applications consume a large amount of energy and computing time on MDs, such as augmented reality [1] and face recognition [2]. Moreover, the MD is characterized by its mobility and portability with the poor CPU performance and limited battery power. To this end, the mobile cloud computing (MCC) is seen as an effective way to solve the problem of a shortage of local resources by offloading the computations to cloud infrastructure with remarkable computational power [3–5]. The popular approach is for offloading computing tasks to the public clouds such as Windows Azure and Amazon EC2. Although MCC provides considerable cloud resources, it cannot guarantee a low response time. Furthermore, the user experience is reduced due to the delay.Edge cloud computing (ECC) is promising for mobile computing offloading, which also considers a promoter of 5G mobile networks because they are located near the edge of the network [6, 7], and has been extensively studied in recent years [8, 9]. As illustrated in Figure 1, edge cloud servers (ECSs) are closer to users, which greatly reduces the time for data transmission. Therefore, offloading computations to less resource ECSs is considered a more advantageous solution. Some previous works on ECC focus on reducing energy consumption such as [10, 11]. Although [12] considers the energy consumption of MDs and cloud servers in computing offloading, it does not analyze the computing performance of MDs and cloud servers. Refs. [13, 14] focus on computing performance enhancement. However, ECSs usually leased in real life scenarios rarely attract attention of researchers.Figure 1
Edge cloud network.In this paper, we consider the equilibrium problem during the computing offloading process, which not only considers the needs of MDs, but also considers the maximum benefits of service providers. For this reason, we propose a strategy for computing offloading by computing the equilibrium between a MD and ECSs. Liuet al. [15] considered the computing offloading process between a remote cloud server and several ECSs, which concerned the benefits of different levels of service providers. However, they did not pay attention to the needs of mobile users, which also should be taken seriously because of its mobility and portability with limited resource [3]. Ref. [16] considered the mobile user that maximized their performance by choosing of the wireless access points for computing offloading. But they did not consider the benefit of mobile users. In this paper, we mainly focus on the features of mobile users, which concludes the issues of mobility, cost, and so on. We designed an efficient computing offloading strategy considering the scenario that a MD executes computing offloading through ECSs. Suppose a MD needs to offload its computing tasks to one of the sets of ECSs. The MD needs to negotiate an offloading policy with the ESCs to optimize the offloading efficiency of both the MD and the ECSs. For this reason, we propose a strategy among a MD and ECSs. Furthermore, we formulate the computing offloading process among the MD and the ECSs as a Stackelberg game. In particular, the MD increases computing efficiency by offloading complicated computation to the ECSs, and the ECSs obtain certain revenue by performing the computations which are offloaded by the MD. An equilibrium between the benefits of the MD and the ECSs is achieved through our proposed strategy. We make three important contributions in this paper.(i)
Realistically considering the real offloading scenario, we formulate the interaction of the MD and the ECSs during the computing offloading process as a Stackelberg game.(ii)
We prove the existence of equilibrium in the Stackelberg game. Furthermore, we propose the C-SGA for computing the equilibrium. And we also design the F-SGA for delay-sensitive applications, which greatly reduces response time.(iii)
We verify the performance of the proposed algorithms via the simulation experiments. The results show that the proposed algorithms increase the efficiency of computing offloading. In addition, we performed a detailed analysis of the performance of the strategy for the changes in the values of the different parameters.The rest of the paper is organized as follows. We present the related work in Section2. We present our system model and formulate the problem in Section 3. We analyze the Stackelberg game of our model in Section 4. We present our algorithms in Section 5. Performance evaluation is provided in Section 6. We conclude this paper in Section 7.


## 2. Related Work

Most previous works have been done on computing offloading [17–19]. The emergence of computing offloading techniques can be traced back to the concept of Cyber Foraging [20], which reduces the computation, storage, and energy of MDs by offloading tasks of MDs to nearby servers with sufficient resources. The main goal of computing offloading includes expanding CPU capacity, saving energy consumption of MDs, reducing service delays, and saving computational cost. Most of the early computing offloading techniques used static partitioning schemes, relying on programmers to statically divide the application into two parts: one part is executed on the MD; the other part is executed on the server. Liet al. [21] proposed a partitioning approach based on energy consumption. The communication energy consumption depends on the size of the transmitted data and the network bandwidth. The computational energy consumption depends on the number of instructions of the program. They obtain optimized program partitioning based on the consumption of computation and communication. Yanget al. [22] proposed a comprehensive consideration of the use of multiple resources, including CPU, memory, and communication costs. They offloaded some tasks on the MD to a nearby laptop with adequate resources.Proposition of MAUI [23] is to provide a common dynamic computing offloading solution and minimize the burden on developers. The programmer only needs to divide the application into local methods and remote methods without having to make an offloading decision set for each program. In order to solve the problem of excessive transmission delay in wide area network (WAN), researchers have considered offloading tasks of MDs to infrastructure that are closer to the information source. Then, Satyanarayananet al. [24] first proposed the concept of Cloudlet, which is defined as a trusted, resource-rich computing device or a group of computing devices to provide computing to nearby mobile terminals. Patelet al. [25] proposed the concept of MEC, which provides powerful computing capability in the wireless access network close to mobile users. MEC runs at the edge of the network and is logically independent of the rest of the network, which is important for applications with high security requirements [26, 27]. In addition, ECSs are particularly suited for dealing with massive analyses and mass data. At the same time, since the ECSs are geographically close to users, the delay of the network responding to the user request is greatly reduced, and the possibility of network congestion in the transmission network and the core network portion is also reduced [28]. There have been some previous studies on computing offloading using ECSs [29–31]. Wanget al. [32] propose a MEC-WPT design for computing offloading by considering multiuser mobile edge cloud system. Ref. [33] explored how infrastructure of edge computing can improve latency and energy consumption relative to the cloud by analyzing multiple types of mobile applications. They demonstrate that the use of edge computing platforms in WIFI and LTE networks can significantly improve the latency of interactive and intensive computing applications. Sardellittiet al. [34] proposed a QoS-based incentive mechanism for mobile data offloading. The incentive mechanism is used in the quality-aware system to stimulate the users’ participation and enhance the robustness of the system [35]. Netoet al. [36] designed a mobile offloading framework with an original decision engine, which can significantly reduce energy consumption.Some of previous work conducted extensive research on game theory. There has been some research on the game that can be used in computing offloading [37, 38]. Chenet al. [39] proposed an approach for computing offloading for mobile cloud computing. In addition, they designed a computation offloading mechanism to achieve a Nash equilibrium of the game. Wanget al. [40] proposed an analysis framework based on evolutionary game theory. Xuet al. [41] designed a security-aware incentive mechanism for computation offloading by using game theory and epidemic theory.


## 3. System Model

As the primary deployment method for MEC [25], we consider the edge system in this paper consisting of a set of ECSs and several MDs. We assume that a MD decides to offload its computations to a set S=1,2,…,S of ECSs. Xi denotes the total computation of ECS i for all ∀i∈S. xi denotes the computation offloaded from the MD to ECS i,xi∈[0,Xi].


### 3.1. Mobile Device

We assume that computation offloaded profile isx=(x1,…,xS); given x, the local remaining unoffloaded computation is given by(1)φx=∑i=1SXi-xi, and computations performed locally completely without offloading is given by(2)φ0=∑i=1SXi. The cost of local computing for the mobile device is given by(3)Fx=eαφx, where α is the modeling parameter. The payment profile is m=(m1,…,mS). Given m, the payment for offloading is given by(4)Mx=∑i=1Smi, where the payment mi is determined by offloading unit price pi and computation amount xi, i.e.,(5)mi=pi·xi. We consider the consumption of performing computing offloading time as part of the offloading cost, which includes the time to compute local remaining computations and the time to transfer the data needed by computing offloading. Kd denotes the computational capability of the MD, and L denotes the transmission capacity of the MD. The total consumption of performing offloading time is given by(6)Tx=∑i=1STiexe+Tioff, where Tiexe represents the time of computing local remaining computations and is given by(7)Tiexe=β·xiKd, where β represents the complexity of the computation. Tioff represents the time taken to transfer the data needed by computing offloading and is given by(8)Tioff=γ·xiL, where γ represents the coefficient of the amount of data required by transferring computations.Therefore, the cost of the MD for performing computing offloading is determined by the computing time, the transmission time, and the payment for the ECSs, i.e.,(9)Cx=Fx+Mx+Tx=eαφx+∑i=1Smi+∑i=1STiexe+Tioff. We define the local utility Γ as the cost reduction from performing offloading, i.e.,(10)Γ=C0-Cx=C0-Fx-Mx-Tx.


### 3.2. Edge Servers

ECSs usually have their own computations to compute as shown in Figure1. When the ECSs decide whether to perform the computing offloading for the MD, they must take their own computations into account. wi denotes the revenue for one unit of ECS i to perform its own computations, and Kis the computational capability of the ECS i. Similar to previous work [42], we ignore the time for transmitting the computation results.The profit of the ECSi is given by(11)Gixi=wi·Xi-xi+mi-eαXi-xi-eαxi-β·xiKis, where Xi-xi is the computation for its own users, and eαxi denotes the cost of computing xi.The utility of each ECSi, which is the profit improvement by performing computing offloading, is defined as(12)Ψixi=Gixi-Gi0=wi·Xi-xi+mi-eα·Xi-xi-eαxi-β·xiKis-wi·Xi+eαXi+1.


### 3.3. Problem Formulation

The strategy among the MD and the ECSs is formulated as a Stackelberg game. Our strategy has two steps as shown in Figure2. In the first step, the MD proposes a payment profile, denoted by p=(p1,…,pS). In the second step, the ECSs respond with corresponding amount of computation for offloading, denoted by x=(x1(p1),…,xS(pS)).Figure 2
Two-step Stackelberg game.We assume that the MD gives a first initial payment; then the optimal decision of each ECSi is obtained by solving the following optimization problem:(13)maxΨixis.t.xi∈0,Xi.Next, we obtain the optimal strategy by maximizing the utility of the MD after receiving the decision of the ECS, i.e.,(14)maxΓx,ps.t.pi≥0,∀i=1,…,S,xipi≤Xi,where Γx,p is the utility of the MD in (10).


## 3.1. Mobile Device

We assume that computation offloaded profile isx=(x1,…,xS); given x, the local remaining unoffloaded computation is given by(1)φx=∑i=1SXi-xi, and computations performed locally completely without offloading is given by(2)φ0=∑i=1SXi. The cost of local computing for the mobile device is given by(3)Fx=eαφx, where α is the modeling parameter. The payment profile is m=(m1,…,mS). Given m, the payment for offloading is given by(4)Mx=∑i=1Smi, where the payment mi is determined by offloading unit price pi and computation amount xi, i.e.,(5)mi=pi·xi. We consider the consumption of performing computing offloading time as part of the offloading cost, which includes the time to compute local remaining computations and the time to transfer the data needed by computing offloading. Kd denotes the computational capability of the MD, and L denotes the transmission capacity of the MD. The total consumption of performing offloading time is given by(6)Tx=∑i=1STiexe+Tioff, where Tiexe represents the time of computing local remaining computations and is given by(7)Tiexe=β·xiKd, where β represents the complexity of the computation. Tioff represents the time taken to transfer the data needed by computing offloading and is given by(8)Tioff=γ·xiL, where γ represents the coefficient of the amount of data required by transferring computations.Therefore, the cost of the MD for performing computing offloading is determined by the computing time, the transmission time, and the payment for the ECSs, i.e.,(9)Cx=Fx+Mx+Tx=eαφx+∑i=1Smi+∑i=1STiexe+Tioff. We define the local utility Γ as the cost reduction from performing offloading, i.e.,(10)Γ=C0-Cx=C0-Fx-Mx-Tx.


## 3.2. Edge Servers

ECSs usually have their own computations to compute as shown in Figure1. When the ECSs decide whether to perform the computing offloading for the MD, they must take their own computations into account. wi denotes the revenue for one unit of ECS i to perform its own computations, and Kis the computational capability of the ECS i. Similar to previous work [42], we ignore the time for transmitting the computation results.The profit of the ECSi is given by(11)Gixi=wi·Xi-xi+mi-eαXi-xi-eαxi-β·xiKis, where Xi-xi is the computation for its own users, and eαxi denotes the cost of computing xi.The utility of each ECSi, which is the profit improvement by performing computing offloading, is defined as(12)Ψixi=Gixi-Gi0=wi·Xi-xi+mi-eα·Xi-xi-eαxi-β·xiKis-wi·Xi+eαXi+1.


## 3.3. Problem Formulation

The strategy among the MD and the ECSs is formulated as a Stackelberg game. Our strategy has two steps as shown in Figure2. In the first step, the MD proposes a payment profile, denoted by p=(p1,…,pS). In the second step, the ECSs respond with corresponding amount of computation for offloading, denoted by x=(x1(p1),…,xS(pS)).Figure 2
Two-step Stackelberg game.We assume that the MD gives a first initial payment; then the optimal decision of each ECSi is obtained by solving the following optimization problem:(13)maxΨixis.t.xi∈0,Xi.Next, we obtain the optimal strategy by maximizing the utility of the MD after receiving the decision of the ECS, i.e.,(14)maxΓx,ps.t.pi≥0,∀i=1,…,S,xipi≤Xi,where Γx,p is the utility of the MD in (10).


## 4. Stackelberg Game Analysis

As discussed above, the MD determines the payment profile of computation offloading to the ECSs, while the ECSs provide corresponding amount of computation. We model the problem as a two-step Stackelberg game among the MD and the ECSs based on the noncooperative game theory. Explicitly, as shown in Figure2, the MD acts as a leader proposing the payment profile. As followers of the MD, the ECSs can adjust the corresponding decisions.


### 4.1. Stackelberg Game Design

In this work, we denote byxi⋆ the optimal strategy of the ECS i, which is the optimal problem of (13), and x⋆ the optimal strategy profile. In addition, pi⋆ denotes the optimal payment for the ECS i. A Nash equilibrium of the Stackelberg game is defined as (x⋆,p⋆), in which none of the ECSs can further improve its profit by changing strategy.Definition 1.
A Nash equilibrium of the Stackelberg game is a strategy profile(x⋆,p⋆), if the strategy satisfies the following conditions:(15)Ψx⋆≥Ψx′Γx⋆,p⋆≥Γx⋆,p′s.t.xi∈0,Xi,∀i=1,…,S,pi∈piˇ,pi^,∀i=1,…,S,wherepi^ is the upper bound of the payment pi, and piˇ is the lower bound.


### 4.2. Nash Equilibrium Analysis

In this part, we will analyze the equilibrium in the Stackelberg game that we proposed and prove the existence of Nash equilibrium in the Stackelberg game. In order to confirm the existence of Nash equilibrium in our Stackelberg game, we have made the following proofs. We first discuss the existence and uniqueness of Nash equilibrium of the Stackelberg game.Lemma 2.
The strategy profile set of the ECSs is nonempty, convex, and compact.Proof.
First, according to the characteristics of ECSs, we calculate the first-order derivative ofΨi to xi that is(16)∂Ψi∂xi=α·eXi-xi-eαxi-wi-βKis+pi. According to the first-order derivative, we calculate the second-order derivative of Ψi to xi that is(17)∂2Ψi∂xi2=-α2·eαXi-xi+eαxi.We can obtain the optimal strategy of ECS i by taking (16) to zero(18)xi⋆pi=12·Xi-1α·ln⁡1αwi+βKis-pi. Then we can obtain the payment’s lower bound of ECS i by taking xi to zero,(19)piˇ=wi+βKis-α·eαXi, and we can obtain the payment’s upper bound of ECS i by taking xi to Xi,(20)pi^=wi+βKis-α·e-αXi. Therefore, Lemma 2 is proved completely.Lemma 3.
The ECSi has a unique optimal strategy after receiving the mobile’s strategy.Proof.
Obviously, if the MD gives api that pi>pi^, the ECS i will perform all of its computation for the MD. However, if pi<piˇ, the ECS i does not perform the offloading.
Whenpiˇ<pi<pi^, the expression of the strategy is given by (18), and we have(21)∂xi⋆∂pi=12α·wi+β/Kis-pi,(22)∂2xi⋆∂pi2=12·αwi+β/Kis-pi2. Evidently, the relation (21) implies that xi⋆ is an increasing function of pi, which means that the higher payment the MD offers, the more computation the ECS i provides. Equation (22) implies that xi⋆ is a concave function of pi. Since xi∈[0,Xi], Ψi(xi) is strictly concave in x⋆, and thus the strategy is unique and optimal. Lemma 3 is proved.Lemma 4.
For the optimal strategies of ECSs, the MD has a unique optimal strategy.Proof.
The first-order partial derivative ofΓ to pi is(23)∂Γ∂pi=C′φx⋆·∂xi⋆∂pi-xi⋆-pi·βKd+γL·∂xi⋆∂pi=C′φx⋆·∂xi⋆∂pi-xi⋆-pi+βKd+γL·∂xi⋆∂pi. The second-order partial derivative of Γ to pi is(24)∂2Γ∂pi2=-C′′φx⋆·∂xi⋆∂pi2+C′φx⋆·∂2xi⋆∂pi2-2·∂xi⋆∂pi-pi+βKd+γL·∂2xi⋆∂pi2,(25)∂2Γ∂pi∂pj=-C′′φx⋆·∂xi⋆∂pi·∂xj⋆∂pj. We define two auxiliary matrices as follows,(26)Hi=diagC′φx⋆-p1+βKd+γL·∂2x1⋆∂p12-2·∂x1⋆∂p1,…,C′φx⋆-pS+βKd+γL·∂2xS⋆∂pS2-2·∂xS⋆∂pS,(27)H2=-C′′φx⋆∂x1⋆∂p1∂x2⋆∂p2⋮∂xS⋆∂pS∂x1⋆∂p1∂x2⋆∂p2⋯∂xS⋆∂pS, and thus, the Hessian matrix of Γx⋆,p⋆ is given by(28)H=H1+H2. Furthermore, for any nonzero column vector z, we have(29)zTHz=zTH1z+zTH2z.
From (23), we have pi<C′φx⋆. Since ∂xi⋆/∂pi≥0, ∂2xS⋆/∂pS2≤0, C′′φx⋆≥0, we have(30)zTH1z≤0,(31)zTH2z≤0. Thus, we obtain(32)zTHz≤0. From the inequality (32), Γx,p is strictly concave, and then (15) is a convex optimization problem. Since H is strictly negative, p⋆ is unique, which is the optimal strategy of MD. Lemma 4 is proved.With Lemmas2, 3, and 4 in place, we prove the following theorem.Theorem 5.
A unique Nash equilibrium exists among the MD and the ECSs in our proposed Stackelberg game.


## 4.1. Stackelberg Game Design

In this work, we denote byxi⋆ the optimal strategy of the ECS i, which is the optimal problem of (13), and x⋆ the optimal strategy profile. In addition, pi⋆ denotes the optimal payment for the ECS i. A Nash equilibrium of the Stackelberg game is defined as (x⋆,p⋆), in which none of the ECSs can further improve its profit by changing strategy.Definition 1.
A Nash equilibrium of the Stackelberg game is a strategy profile(x⋆,p⋆), if the strategy satisfies the following conditions:(15)Ψx⋆≥Ψx′Γx⋆,p⋆≥Γx⋆,p′s.t.xi∈0,Xi,∀i=1,…,S,pi∈piˇ,pi^,∀i=1,…,S,wherepi^ is the upper bound of the payment pi, and piˇ is the lower bound.


## 4.2. Nash Equilibrium Analysis

In this part, we will analyze the equilibrium in the Stackelberg game that we proposed and prove the existence of Nash equilibrium in the Stackelberg game. In order to confirm the existence of Nash equilibrium in our Stackelberg game, we have made the following proofs. We first discuss the existence and uniqueness of Nash equilibrium of the Stackelberg game.Lemma 2.
The strategy profile set of the ECSs is nonempty, convex, and compact.Proof.
First, according to the characteristics of ECSs, we calculate the first-order derivative ofΨi to xi that is(16)∂Ψi∂xi=α·eXi-xi-eαxi-wi-βKis+pi. According to the first-order derivative, we calculate the second-order derivative of Ψi to xi that is(17)∂2Ψi∂xi2=-α2·eαXi-xi+eαxi.We can obtain the optimal strategy of ECS i by taking (16) to zero(18)xi⋆pi=12·Xi-1α·ln⁡1αwi+βKis-pi. Then we can obtain the payment’s lower bound of ECS i by taking xi to zero,(19)piˇ=wi+βKis-α·eαXi, and we can obtain the payment’s upper bound of ECS i by taking xi to Xi,(20)pi^=wi+βKis-α·e-αXi. Therefore, Lemma 2 is proved completely.Lemma 3.
The ECSi has a unique optimal strategy after receiving the mobile’s strategy.Proof.
Obviously, if the MD gives api that pi>pi^, the ECS i will perform all of its computation for the MD. However, if pi<piˇ, the ECS i does not perform the offloading.
Whenpiˇ<pi<pi^, the expression of the strategy is given by (18), and we have(21)∂xi⋆∂pi=12α·wi+β/Kis-pi,(22)∂2xi⋆∂pi2=12·αwi+β/Kis-pi2. Evidently, the relation (21) implies that xi⋆ is an increasing function of pi, which means that the higher payment the MD offers, the more computation the ECS i provides. Equation (22) implies that xi⋆ is a concave function of pi. Since xi∈[0,Xi], Ψi(xi) is strictly concave in x⋆, and thus the strategy is unique and optimal. Lemma 3 is proved.Lemma 4.
For the optimal strategies of ECSs, the MD has a unique optimal strategy.Proof.
The first-order partial derivative ofΓ to pi is(23)∂Γ∂pi=C′φx⋆·∂xi⋆∂pi-xi⋆-pi·βKd+γL·∂xi⋆∂pi=C′φx⋆·∂xi⋆∂pi-xi⋆-pi+βKd+γL·∂xi⋆∂pi. The second-order partial derivative of Γ to pi is(24)∂2Γ∂pi2=-C′′φx⋆·∂xi⋆∂pi2+C′φx⋆·∂2xi⋆∂pi2-2·∂xi⋆∂pi-pi+βKd+γL·∂2xi⋆∂pi2,(25)∂2Γ∂pi∂pj=-C′′φx⋆·∂xi⋆∂pi·∂xj⋆∂pj. We define two auxiliary matrices as follows,(26)Hi=diagC′φx⋆-p1+βKd+γL·∂2x1⋆∂p12-2·∂x1⋆∂p1,…,C′φx⋆-pS+βKd+γL·∂2xS⋆∂pS2-2·∂xS⋆∂pS,(27)H2=-C′′φx⋆∂x1⋆∂p1∂x2⋆∂p2⋮∂xS⋆∂pS∂x1⋆∂p1∂x2⋆∂p2⋯∂xS⋆∂pS, and thus, the Hessian matrix of Γx⋆,p⋆ is given by(28)H=H1+H2. Furthermore, for any nonzero column vector z, we have(29)zTHz=zTH1z+zTH2z.
From (23), we have pi<C′φx⋆. Since ∂xi⋆/∂pi≥0, ∂2xS⋆/∂pS2≤0, C′′φx⋆≥0, we have(30)zTH1z≤0,(31)zTH2z≤0. Thus, we obtain(32)zTHz≤0. From the inequality (32), Γx,p is strictly concave, and then (15) is a convex optimization problem. Since H is strictly negative, p⋆ is unique, which is the optimal strategy of MD. Lemma 4 is proved.With Lemmas2, 3, and 4 in place, we prove the following theorem.Theorem 5.
A unique Nash equilibrium exists among the MD and the ECSs in our proposed Stackelberg game.


## 5. Algorithm Design

In this section, the process of strategy is shown in Figure3. We propose two algorithms, F-SGA and C-SGA, for delay-sensitive services and compute-intensive services, respectively. Generally, delay-sensitive services require strict response time, which requires the system to make decisions quickly. Compute-intensive services require a large amount of computing by the servers. F-SGA, a fast Stackelberg game algorithm, can make decisions quickly due to its simple decision mechanism. C-SGA, a complex Stackelberg game algorithm, is slower than F-SGA in decision making speed, but it provided more accurate price and computation to maximize the benefit of MD and ECSs. F-SGA and C-SGA are described in detail as follows.Figure 3
The game process of our Stackelberg game.


### 5.1. F-SGA

We propose F-SGA to quickly achieve equilibrium as shown in Algorithm1. Because the algorithm can quickly obtain the optimal objective for the MD and the ECSs, it is suitable for computing offloading of latency-sensitives applications.Algorithm 1:F-SGA.
Input:  pmin=mini∈Spiˇ,pmax=maxi∈S⁡pi^. Output:  x,p. 1: if  pmax-pmin≥ξ  then 2:Let pd=2pmin/3+pmax/3; 3:Let pu=pmin/3+2pmax/3; 4:Let pi=(pd+pu)/2; 5: else 6:Let pi=(pmax+pmin)/2; 7: end if 8: for all  i such that i∈S  do 9:Calculate xi(pi) according to (18); 10: end for 11: Calculate Γx,p according to (10);As discussed before, we set two points, denoted aspmin and pmax. Initially, we set pmin=0, pmax=maxi∈S⁡pi^. Then we describe F-SGA in detail. The ECSs first send their payment to the MD. After receiving the payment of ECSs, F-SGA proceeds to the next step by comparing the difference between pmin and pmax. It means that when the difference of payment from the ECSs is small, we simply compromise the payment of computing offloading. But when the different of payment is large, F-SGA will also quickly determine the payment of computing offloading, but more detailed.


### 5.2. C-SGA

The algorithm proposed in Algorithm1 needs less time and has a faster response speed, but it directly determines the payment, which leads to an increase in the cost of computing offloading. We next propose C-SGA, which uses the fine iteration to obtain the optimal strategy. C-SGA are shown in Algorithm 2.Algorithm 2:C-SGA.
Input:  pmin=0,pmax=maxi∈Spi^. Output:  x,p. 1: Let pd=2pmin/3+pmax/3; 2: Let pu=pmin/3+2pmax/3; 3: while  pmax-pmin≥ξ  do 4:for all  i such that i∈S  do 5:Calculate xi(pd) according to (18); 6:end for 7:Calculate Γx,pd according to (10); 8:for all  i such that i∈S  do 9:Calculate xi(pu) according to (18); 10:end for 11:Calculate Γx,pu according to (10); 12:if  Γx,pd<Γx,pu  then 13:Let pmin=pd; 14:else 15:Let pmax=pu; 16:end if 17: end while 18: Let pi=pmin; 19: for all  i such that i∈S  do 20:Calculate xi(pi) according to (18); 21: end for 22: Calculate Γx,p according to (10);In contrast, C-SGA only needs the ECSs to compare the the bound of payment, which not only greatly reduces the computation of the ECSs, but also obtains more optimized payment. Therefore, C-SGA is suitable for situations where the ECSs have less computation resources. The process of C-SGA is summarized as follows.(1)
The MD first sends the initial value of payment. With the strategy(x⋆,p⋆), the ECSs compute the optimal computation for offloading based on (18) and send the computing results to the MD.(2)
After receiving the results, the MD calculates the utility functionΓx,pd and Γx,pu of the strategy. Then we compare Γx,pd and Γx,pu. If Γx,pd<Γx,pu, this implies that the optimal value must be located between pd and pu, and thus we set pmin=pd, pmax=pu.(3)
Then the MD and the ECSs continue to perform procedures (1) and (2) untilpmax-pmin<ξ, where ξ is supposed to make our algorithm more accurate.Theorem 6.
The proposed Algorithm2 can reach a unique Nash equilibrium.Proof.
SinceΓ is strict convex, the optimal strategy p⋆ is unique. We can obtain p⋆ by Algorithm 2 to maximize Γ. Then, ECS i can determine corresponding x⋆ to maximize its utility. Consequently, the MD can also obtain a definitive optimal utility with p⋆. Therefore, Algorithm 2 can reach a unique Nash equilibrium.


## 5.1. F-SGA

We propose F-SGA to quickly achieve equilibrium as shown in Algorithm1. Because the algorithm can quickly obtain the optimal objective for the MD and the ECSs, it is suitable for computing offloading of latency-sensitives applications.Algorithm 1:F-SGA.
Input:  pmin=mini∈Spiˇ,pmax=maxi∈S⁡pi^. Output:  x,p. 1: if  pmax-pmin≥ξ  then 2:Let pd=2pmin/3+pmax/3; 3:Let pu=pmin/3+2pmax/3; 4:Let pi=(pd+pu)/2; 5: else 6:Let pi=(pmax+pmin)/2; 7: end if 8: for all  i such that i∈S  do 9:Calculate xi(pi) according to (18); 10: end for 11: Calculate Γx,p according to (10);As discussed before, we set two points, denoted aspmin and pmax. Initially, we set pmin=0, pmax=maxi∈S⁡pi^. Then we describe F-SGA in detail. The ECSs first send their payment to the MD. After receiving the payment of ECSs, F-SGA proceeds to the next step by comparing the difference between pmin and pmax. It means that when the difference of payment from the ECSs is small, we simply compromise the payment of computing offloading. But when the different of payment is large, F-SGA will also quickly determine the payment of computing offloading, but more detailed.


## 5.2. C-SGA

The algorithm proposed in Algorithm1 needs less time and has a faster response speed, but it directly determines the payment, which leads to an increase in the cost of computing offloading. We next propose C-SGA, which uses the fine iteration to obtain the optimal strategy. C-SGA are shown in Algorithm 2.Algorithm 2:C-SGA.
Input:  pmin=0,pmax=maxi∈Spi^. Output:  x,p. 1: Let pd=2pmin/3+pmax/3; 2: Let pu=pmin/3+2pmax/3; 3: while  pmax-pmin≥ξ  do 4:for all  i such that i∈S  do 5:Calculate xi(pd) according to (18); 6:end for 7:Calculate Γx,pd according to (10); 8:for all  i such that i∈S  do 9:Calculate xi(pu) according to (18); 10:end for 11:Calculate Γx,pu according to (10); 12:if  Γx,pd<Γx,pu  then 13:Let pmin=pd; 14:else 15:Let pmax=pu; 16:end if 17: end while 18: Let pi=pmin; 19: for all  i such that i∈S  do 20:Calculate xi(pi) according to (18); 21: end for 22: Calculate Γx,p according to (10);In contrast, C-SGA only needs the ECSs to compare the the bound of payment, which not only greatly reduces the computation of the ECSs, but also obtains more optimized payment. Therefore, C-SGA is suitable for situations where the ECSs have less computation resources. The process of C-SGA is summarized as follows.(1)
The MD first sends the initial value of payment. With the strategy(x⋆,p⋆), the ECSs compute the optimal computation for offloading based on (18) and send the computing results to the MD.(2)
After receiving the results, the MD calculates the utility functionΓx,pd and Γx,pu of the strategy. Then we compare Γx,pd and Γx,pu. If Γx,pd<Γx,pu, this implies that the optimal value must be located between pd and pu, and thus we set pmin=pd, pmax=pu.(3)
Then the MD and the ECSs continue to perform procedures (1) and (2) untilpmax-pmin<ξ, where ξ is supposed to make our algorithm more accurate.Theorem 6.
The proposed Algorithm2 can reach a unique Nash equilibrium.Proof.
SinceΓ is strict convex, the optimal strategy p⋆ is unique. We can obtain p⋆ by Algorithm 2 to maximize Γ. Then, ECS i can determine corresponding x⋆ to maximize its utility. Consequently, the MD can also obtain a definitive optimal utility with p⋆. Therefore, Algorithm 2 can reach a unique Nash equilibrium.


## 6. Performance Evaluation

We use extensive simulations to verify our proposed strategy and algorithms. We set up 3 ECSs as the initial default settings for our simulations. The total computationXi of ECSs is 100. We consider that the MD and the ECSs are placed over a 1km×1km region. The ECSs are located at grid points in the region, while the MDs are placed uniformly at random. In the simulations, we set the modeling parameter α=1.5 and the computation complexity parameter β=1.


### 6.1. The Utility of the Mobile Device

In this part, we analyze the changes in the utility of MD as a function of different conditions. First we analyze the relationship between the utility of a MD and the revenue of the ECSs. Figure4 shows the utility of the MD by varying the value of revenue of the ECSs from their own users. As shown in the figure, regardless of the parameter α being 0.4, 0.6, or 0.8, with the increase of the unit revenue, the ECSs prefer providing the computation to their own users. As a result, the amount of computation provided to computing offloading is reduced. Therefore, the utility of the MD decreases.Figure 4
The utility of the MD with different unit reward.Then we analyze how the payment of a MD affects the utility of the MD. Figure5 shows the correlation between the payment form the MD and the utility of the MD under different value of parameter α. With the increase of the payment from the MD, the utility of it increases at first. But after reaching a peak, the utility of the MD has dropped. This is because as the payment increases, the ECS provides more computation. However, the payment continues to increase, resulting in an increase in the cost of MD, so the utility is reduced.Figure 5
The utility of the MD with different payment.


### 6.2. The Utility of the Edge Servers

Figure6 shows the average utility of the ECSs by varying the unit revenue. With the increase of the unit revenue, the utility of the ECSs increases. The high utility of ECSs is attributed to the fact that ECSs are willing to provide computation to their own users, leading to efficient computation offloading. Interestingly, the ECSs achieve less utility when the revenue is large enough. As we know, ECSs are profit driven to provide computation for their users. However, large unit revenue is a double-edged sword for ECSs. Although edge servers are more willing to serve their users, it may result in fewer computing offloading.Figure 6
The utility of the ECSs with different unit reward.Figure7 shows the trend of ESCs’ utility as a function of payment for a MD. We set α=0.4, α=0.6, and α=0.8, respectively. As the figure shows, the utility of ECSs begins to increase as the payment of the MD increases, and the utility of ECSs begins to decrease after reaching a peak. At the beginning, due to the increase in the payment, the utility of ECSs increases, but this will increase the cost of the MD, so it will not continue to increase.Figure 7
The utility of the ECSs with different revenue.


### 6.3. Offloading Computations

In order to evaluate how the unit revenue impacts computation for offloading, we set three different unit revenues for simulation. We setw=0.2, w=0.4, and w=0.6, respectively. As can be seen from Figure 8, the trends of different w are similar, and their computation for offloading increases as the payment increases. In other words, in the case of the above three unit revenues, the computation increases as the payment from the MD increases. Note that when the unit revenue is greater than the MD’s given payment, the ECSs will not perform any offloading.Figure 8
Payment of MD.Figure9 shows the relationship between the computation of offloading and the utility of MD. It also shows the relationship between the computation and the utility of ECSs. Through the simulation results, we see that, within a certain range, the greater the computation of offloading, the higher the utility of the MD. At the same time, the utility of ECSs increases. It is well understood that, due to the strategy, when the computation of offloading increases, the utility of the MD will increase accordingly. Of course ECSs will also benefit. We can say with certainty that, within a certain range bound, the more computation performed, the more beneficial to both sides.Figure 9
Offloading quantity.


### 6.4. The Impact of the Utility and Response Time

We are interested in the impact ofξ that represents the value of accuracy for the proposed strategy. So we set a series of ξ values in the range of 0.2 to 1.5. Figure 10 shows the simulation results. As the value of ξ increases, the accuracy of our strategy increases, and the utility of MD and the profit of ECSs increase. It will be more beneficial to both the MD and the ECSs to calculate the benefits of offloading.Figure 10
The impact of computational accuracy.Figure11 shows the response time of F-SGA and C-SGA using the same conditions during the computing offloading. As can be seen from the figure, as the parameter ξ increases, the response time of C-SGA decreases. However, the response time of the F-SGA remains the same and has been at a low level. This is because as the parameter ξ increases, the C-SGA needs to make more rounds of judgment and iteration, resulting in an increase in response time. But F-SGA can always make decisions quickly, regardless of the value of the parameter ξ.Figure 11
Response time of F-SGA and C-SGA.


## 6.1. The Utility of the Mobile Device

In this part, we analyze the changes in the utility of MD as a function of different conditions. First we analyze the relationship between the utility of a MD and the revenue of the ECSs. Figure4 shows the utility of the MD by varying the value of revenue of the ECSs from their own users. As shown in the figure, regardless of the parameter α being 0.4, 0.6, or 0.8, with the increase of the unit revenue, the ECSs prefer providing the computation to their own users. As a result, the amount of computation provided to computing offloading is reduced. Therefore, the utility of the MD decreases.Figure 4
The utility of the MD with different unit reward.Then we analyze how the payment of a MD affects the utility of the MD. Figure5 shows the correlation between the payment form the MD and the utility of the MD under different value of parameter α. With the increase of the payment from the MD, the utility of it increases at first. But after reaching a peak, the utility of the MD has dropped. This is because as the payment increases, the ECS provides more computation. However, the payment continues to increase, resulting in an increase in the cost of MD, so the utility is reduced.Figure 5
The utility of the MD with different payment.


## 6.2. The Utility of the Edge Servers

Figure6 shows the average utility of the ECSs by varying the unit revenue. With the increase of the unit revenue, the utility of the ECSs increases. The high utility of ECSs is attributed to the fact that ECSs are willing to provide computation to their own users, leading to efficient computation offloading. Interestingly, the ECSs achieve less utility when the revenue is large enough. As we know, ECSs are profit driven to provide computation for their users. However, large unit revenue is a double-edged sword for ECSs. Although edge servers are more willing to serve their users, it may result in fewer computing offloading.Figure 6
The utility of the ECSs with different unit reward.Figure7 shows the trend of ESCs’ utility as a function of payment for a MD. We set α=0.4, α=0.6, and α=0.8, respectively. As the figure shows, the utility of ECSs begins to increase as the payment of the MD increases, and the utility of ECSs begins to decrease after reaching a peak. At the beginning, due to the increase in the payment, the utility of ECSs increases, but this will increase the cost of the MD, so it will not continue to increase.Figure 7
The utility of the ECSs with different revenue.


## 6.3. Offloading Computations

In order to evaluate how the unit revenue impacts computation for offloading, we set three different unit revenues for simulation. We setw=0.2, w=0.4, and w=0.6, respectively. As can be seen from Figure 8, the trends of different w are similar, and their computation for offloading increases as the payment increases. In other words, in the case of the above three unit revenues, the computation increases as the payment from the MD increases. Note that when the unit revenue is greater than the MD’s given payment, the ECSs will not perform any offloading.Figure 8
Payment of MD.Figure9 shows the relationship between the computation of offloading and the utility of MD. It also shows the relationship between the computation and the utility of ECSs. Through the simulation results, we see that, within a certain range, the greater the computation of offloading, the higher the utility of the MD. At the same time, the utility of ECSs increases. It is well understood that, due to the strategy, when the computation of offloading increases, the utility of the MD will increase accordingly. Of course ECSs will also benefit. We can say with certainty that, within a certain range bound, the more computation performed, the more beneficial to both sides.Figure 9
Offloading quantity.


## 6.4. The Impact of the Utility and Response Time

We are interested in the impact ofξ that represents the value of accuracy for the proposed strategy. So we set a series of ξ values in the range of 0.2 to 1.5. Figure 10 shows the simulation results. As the value of ξ increases, the accuracy of our strategy increases, and the utility of MD and the profit of ECSs increase. It will be more beneficial to both the MD and the ECSs to calculate the benefits of offloading.Figure 10
The impact of computational accuracy.Figure11 shows the response time of F-SGA and C-SGA using the same conditions during the computing offloading. As can be seen from the figure, as the parameter ξ increases, the response time of C-SGA decreases. However, the response time of the F-SGA remains the same and has been at a low level. This is because as the parameter ξ increases, the C-SGA needs to make more rounds of judgment and iteration, resulting in an increase in response time. But F-SGA can always make decisions quickly, regardless of the value of the parameter ξ.Figure 11
Response time of F-SGA and C-SGA.


## 7. Conclusion

In this paper, we proposed a game for the computing offloading between a MD and ECSs. We provided a Stackelberg game theoretic analysis and proved the existence of the equilibrium in the Stackelberg game. Furthermore, we proposed two algorithms for different scenarios and provided the upper and lower boundary of the payment. Moreover, multiple optimization results were obtained by regulating model parameters. The simulation results showed that the game is effective in improving the utility of both the MD and the ECSs.



---

*Source: 2179316-2018-12-02.xml*