# A Two-Way Update Resource Allocation Strategy in Mobile Edge Computing

Authors: Zhe Yang; Yi-peng Chen; Fei Gu; Jin Wang; Lei Zhao
Journal: Wireless Communications and Mobile Computing
 (2022)

---

## Abstract

Existing studies of mobile edge computing resource allocation strategy problem merely optimize delay and energy cost, seldom considering the benefit of edge servers. So, a two-way update strategy based on game theory (TUSGT) was proposed. TUSGT converts the task competition relationship among edge servers into a noncollaborative game issue and adopts a potential game-based joint optimization strategy, allowing edge servers to determine task selection preference by maximizing their own benefit as the objective. At mobile device side, the EWA algorithm of online learning was used to update parameters, exerting impact on edge server’s task selection preference from a global perspective and improving overall deadline hit rate. The simulation test results show that, compared to BGTA, MILP, greedy strategy, random strategy, and ideal strategy, TUSGT promotes deadline hit rate by up to 30% and increases edge server’s average benefit by up to 65%.


---

## Body

## 1. Introduction

With the increased network bandwidth and popularized mobile smart devices, the number of computation intensive applications based on mobile devices is also growing rapidly [1]. These applications have large computational work and high requirement for real time [2, 3]. But restricted by computation capability and energy cost, it is difficult to complete computing tasks solely on mobile devices. So the mobile cloud computing architecture emerges, aimed at using cloud resources to carry out computation-intensive tasks, so as to optimize user experience [4, 5] and relieve insufficient computation capability of mobile device. However, due to long distance between cloud resources and mobile devices, the transmission of large amount of data leads to time delay requirement hard to be met. Thus, in 2014, the European Telecommunication Standards Institute put forward a Mobile Edge Computing (MEC) architecture [6], providing nearby computing resource-edge server for mobile devices. These edge servers own more computing resources compared to mobile devices, so mobile devices download computation-intensive tasks to nearby edge server, greatly reducing task completion delay and mobile devices’ energy cost [7].Nevertheless, MEC’s computing resources are not unlimited, and an edge server is also hard to meet the computing need of all mobile devices surrounding it; thereby, the studies on task offloading and resource allocation strategy are of great significance to promote overall MEC performance [8–10] and it is also one of the hot spots in MEC research field [11]. Most of existing task offloading and resource allocation strategies take task delay and mobile devices’ energy cost as the primary optimization objective, rarely considering the benefit of edge servers, i.e., the cost benefit of edge servers. It is an idealized hypothesis to let edge server complete mobile devices’ computing tasks regardless of benefit, and this is impossible to realize in real application scenarios. As letting edge server to perform a task will inevitably produce energy cost overhead, if an edge server is made to perform a task without any benefit, it will choose to not perform any task so as to reduce overhead.By introducing benefit factor into MEC system, edge servers will only make the best choice for themselves, since their goal is to maximize their own benefit. But for mobile devices, MEC system is expected to ensure that more tasks can be completed on time by task offloading and resource allocation. Therefore, how to guarantee edge server benefit while getting more mobile device tasks to be completed on time as possible is a crucial target.In this paper, a two-way update strategy based on game theory (TUSGT) was proposed to solve the above problem. The main work of this paper is as follows:(1)
In a multiuser and multiedge server MEC system, a new TUSGT resource allocation strategy was raised. It converts task competition relationship between edge servers into a noncollaborative game problem and designs a corresponding strategy according to the game characteristics to solve the problem, in which every edge server takes maximizing its own benefit as objective to determine task selection preference. Meanwhile, the system uses exponent weight algorithm (EWA) and integrates with task completion condition to update parameters, so as to further increase overall deadline hit rate; that is to say, make more mobile device tasks be completed on time(2)
We analyzed and proved the existing of unique Nash equilibrium in noncollaborative game problem of edge server, enabled different edge servers to eventually reach to Nash equilibrium steady state through strategy design, and testified its convergence(3)
Through a simulation test, we verified the convergence of TUSGT strategy and proved its validity by comparing the deadline hit rate of five datum strategies and the average benefit of edge serversIn this paper, Section2 introduces the related work of resource allocation in MEC; Section 3 describes the system model in MEC; Section 4 provides the idea and relevant certificate of TUSGT; Section 5 shows the result of simulation test and evaluates TUSGT performance in details.


## 2. Related Work

In existing studies of resource allocation strategies, the main optimization objectives are task delay and systematic energy cost.Regarding the research of task processing delay optimization, the literature [11] designed a vertically and horizontally synergistic network architecture based on vehicle-mounted edge computing network architecture. Then, by analyzing the relationship between communication, cache, and computing resources, a joint optimization model of the three was proposed, and the asynchronous distributed reinforcement learning was used to realize the solution to task offloading and resource management strategy. This model can obviously reduce overall time delay. The literature [12] expresses the heterogeneous task offloading problem in distributed edge computing environment as a multiperson game problem, and every participator makes offloading decision according to incomplete information. Based on this, the authors designed a heterogeneous edge computing task offloading strategy based on minority game. In this strategy, subtasks are grouped to compete with other tasks for resources. This strategy can reduce more task processing delay.Regarding the research of systematic energy cost optimization, the literature [13] put forward a convex optimization problem and used offloading priority function to solve the problem. This function sets priority for users, which relies on their own channel gains and local computing energy cost. The author also proposed a low-complexity suboptimal strategy, utilizing average subchannel gains to solve the corresponding mixed integer optimization problem. This strategy can significantly optimize energy cost. The literature [14] considered two different resource allocation strategies for joint optimization: the first strategy paid attention to fairness between users, and the second one paid attention to systematic energy efficiency. Besides, the author expressed energy cost optimization problem as a nonconcave fraction programming problem in collaborative strategies and used a low-complexity optimization strategy to realize optimal allocation. This scheme improves the energy efficiency of wireless mobile edge computing system. According to the problems of high time delay, high energy cost, and low reliability, the literature [15] proposed an offloading model considering time delay and energy cost as well as a dynamic game allocation model based on mobile terminal’s reputation value. The improved particle swarm optimization algorithm and Lagrange multiplier method were used to solve this model, respectively. This scheme can effectively reduce total systematic energy cost and enhance offloading and allocation reliability.All the above research work assume that edge servers would complete any computing tasks from mobile devices unconditionally, without considering their own benefits. This is an idealistic situation and cannot be realized in real application scenarios.In recent years, some researchers have started to take the edge server benefit into consideration. The literature [16] put forward an auction-based edge computing resources market. This auction mechanism can guarantee authenticity and computing efficiency while maximizing overall benefit, and edge servers will be allocated to the device willing to pay the highest cost. This auction strategy can effectively solve the problem of maximizing the benefit of edge computing service provider. The literature [17] developed a deep learning-based optimal auction strategy for edge resource allocation. It utilized neural network to convert bids and used their own estimation as training data to adjust neural network parameters, so as to optimize loss function. Finally, edge servers were allocated to corresponding devices according to obtained allocation strategy and acquired corresponding benefits. This strategy can effectively promote total benefit of system. The literature [18] designed multi-item auction and data offloading strategy based on congestion game, aiming to maximize the income of mobile operator and reduce the payment of mobile users. This strategy can effectively increase total income of mobile operator and bring down the payment of mobile users to a certain extent. Though above research work have considered the benefit of edge server, they have not taken task delay requirement into full account.The current research focuses on optimization of delay and energy consumption, but not enough consideration for the benefits of edge servers. Therefore, the starting point of this paper is to optimize the benefits of edge servers. The delay is an important performance evaluation index of the MEC system. Because the mobile device unloads the task, it must return the calculation result within a certain period of time. And while optimizing the revenue of the edge server, it will have a certain impact on the delay, so this paper selects these two indicators as the optimization goals.The benefit includes a delay factor, which is to allow the edge server to choose the tasks that it can complete as soon as possible. However, if the strategy is only determined according to the initial conditions, limited by the incomplete information of the edge server, there must be a lot of selection conflicts. At this time, the adjustment of the penalty coefficient is to balance the conflict and the benefits of the edge server. And solving the conflict of choice of tasks can significantly improve the overall task completion rate and the overall average benefit of the MEC system. The proposed TUSGT considers task delay requirement and edge server benefit need simultaneously, converts the natural competition relationship between edge servers into a noncollaborative game problem, and designs a game theory-based strategy to solve the problem, maximizing edge server benefit and making more computing tasks be completed as possible.


## 3. System Model

### 3.1. Network Architecture

The proposed MEC network architecture is shown in Figure1. Mobile devices transmit task information require to offload into management server; edge server obtains task information from management server and then sends its choice to the latter. Management server takes charge in collecting edge server choice, updating resource allocation strategies, and updating subsequent parameters. After resource allocation strategy is determined, an edge server starts to perform tasks and transmits the results to corresponding mobile devices.Figure 1
MEC network architecture.


### 3.2. Task Model

In the proposed system model, a group ofM mobile devices is represented by MD=MD1,MD2,⋯,MDM; a group of N edge servers is represented by ES=ES1,ES2,⋯,ESN. Therein, every mobile device only holds one atomic task, and all mobile devices’ task set is expressed as Task=T1,T2,⋯,TM. Set the information cell group of the mth task as Tm=VIm,VOm,Lm,Ωm,Rm, in which VIm denotes to the input data size of task m, VOm denotes to the output data size of task m, Lm denotes to the required operand of task m, Ωm denotes to the time delay requirement of task m, and Rm denotes to the reward paid by task m.


### 3.3. Communication Model

The paper supposes a mobile device only communicates with one edge server, so when uploading or downloading data, there is no interference from other device transmission. Define the transmission rate between mobile devicem and edge server n as shown in Equation (1) [19]:
(1)dm,n=Blog21+pmgm,nσ2,in which B is the bandwidth, pm is the transmission rate, gm,n represents the channel gains, and σ2 is the noise power. The calculation formula of channel gain gm,n is shown in Equation (2) [19]:
(2)gm,n=G3×1084πFcdistm,nPL,in which G is the antenna gain, Fc is the carrier frequency, distm,n represents the distance between mobile device m and edge server n, and PL is the path loss factor. According to Equations (1) and (2), the data transmission rate can be calculated by the distance between mobile device and edge server.


### 3.4. Time Delay and Energy Cost Model

The local computing delay of task is shown in Equation (3), in which fm is the computing rate of mobile device m.
(3)Dmlocal=Lmfm.In case that taskm is offloaded to edge server n, then the corresponding task delay is shown in
(4)Dm,noff=Dm,nu+Dm,nd+Dm,nc,(5)Dm,nu=VImdm,n,(6)Dm,nd=VOmdm,n,(7)Dm,nc=Lmfn,in which Dm,nu is the task uploading time, Dm,nd is the result downloading time, Dm,nc is the task computing time on edge server, and fn is the computing rate of edge server.On account of the benefit of edge server, it is necessary to figure out the energy cost overhead of edge server, and the greater the energy cost overhead is, the smaller the benefit will be. The energy cost overhead of edge server is shown in(8)cm,n=Pcom,n×Dm,nc+Ptra,n×Dm,nu+Dm,nd,in which Pcom,n is the computing power of edge server n and Ptra,n is the transmission power of edge server n.


### 3.5. Benefit and Overhead Model

The cost overhead that an edge servern completes the offloading task of mobile device m is shown in
(9)πm,n=cm,n,dm,n>0,∞,dm,n<0.That is to say, when the communication rate between edge servern and mobile device m is normal, the overhead is the cost of edge server; when edge server n cannot communicate with mobile device m, the overhead of edge server is infinite.Edge servers compete for task according to overhead function (9), and ever edge server attempts to find the optimal strategy, minimizing its overhead. This causes all edge servers do not receive any task to save overhead (not receiving any task means no cost overhead to be paid). However, this result clearly contradicts the purpose of MEC system, and it makes no sense for mobile device to offload task, so mobile devices need to provide certain rewards. The specific benefit obtained by an edge server can be calculated by the initial reward Rm of mobile device task and a penalty function punishm,n [20]. The computing method of penalty function is shown in
(10)punishm,n=λmΩmΩm−Dm,noff+ω,Dm,noff≤Ωm,∞,Dm,noff>Ωm,in which Ωm is the required deadline of task m and Dm,noff is the completion time for the server n to complete the offloaded task. ω is a very small nonzero positive number, used to prevent denominator as zero when offloading task completion delay just satisfies task delay requirement. λ is the penalty coefficient, used for dynamic adjustment by reverse update method (see details in Section 4.2). This penalty function is set to give different penalties based on the speed at which edge server completes the task; i.e., the more time intervals left for edge server to complete task, the smaller the penalty will be. Next, it is needed to set a benefit indicator function um,n, by computing which an edge server can make its decision. The benefit indicator function um,n is defined as shown in
(11)um,n=Rm×Ωm−Dm,noff+ωλm×Ωm×Nm×cm,n,πm,n≠∞,0,πm,n=∞,in which Nm represents the number of edge servers choosing the task m; i.e., the more tasks are selected, the lower the value of the reward indicator function. Benefit refers to what the edge server can ultimately get. The benefit contains multiple factors; the purpose is to allow multiple factors to affect the edge server comprehensively. These factors are of similar importance and can affect the selection of edge servers.


### 3.6. Task Offloading Model

The system model in this paper is referred to [21, 22]. In order to verify the effect of the scheme, it is considered that the task of the mobile device is inseparable; that is, the task cannot be divided into multiple edge servers for completion. And if the edge server selects the mobile device task, it uses all its computing resources for computing, so one edge server can receive at most one task at the same time. On the basis of above agreement, the paper expresses the allocation strategy of mobile device m as am=am,0,am,1,⋯,am,N, in which am,n=0,1; the value of am,0 represents whether to calculate locally. Therefore, the total strategy configuration of MEC system can be obtained as A=a1,a2,⋯,aM, satisfying ∑i=1Mai,n≤1,∀n∈ES and∑i=1Nam,i≤1,∀m∈Task.


### 3.7. Objective Function

In the competition game on edge server side, the objective of every edge server is to maximize its own benefit. So, the general objective on edge server side is shown in(12)benefitm,n=Rm×Ωm−Dm,noff+ωΩm×cm,n,πm,n≠∞,0,πm,n=∞,(13)maximize:∑i=1N∑m∈Sibenefitm,i,in which Si represents the task set selected by edge server i, which is the subset of Task, and benefitm,i represents the benefit obtained by edge server i to complete mobile device m task. This objective function represents maximizing the total edge server benefit on the edge server side.On mobile device side, every mobile device needing to offload tasks expects its task to be completed. Thus, the total objective function on mobile device side is shown in(14)maximize:∑i=1Mθi.θi is a binary variable. If the task of mobile device i can be completed within required time delay, then its value is 1; otherwise, it is 0. This objective function represents making more offloading tasks to be completed on time as possible.


## 3.1. Network Architecture

The proposed MEC network architecture is shown in Figure1. Mobile devices transmit task information require to offload into management server; edge server obtains task information from management server and then sends its choice to the latter. Management server takes charge in collecting edge server choice, updating resource allocation strategies, and updating subsequent parameters. After resource allocation strategy is determined, an edge server starts to perform tasks and transmits the results to corresponding mobile devices.Figure 1
MEC network architecture.


## 3.2. Task Model

In the proposed system model, a group ofM mobile devices is represented by MD=MD1,MD2,⋯,MDM; a group of N edge servers is represented by ES=ES1,ES2,⋯,ESN. Therein, every mobile device only holds one atomic task, and all mobile devices’ task set is expressed as Task=T1,T2,⋯,TM. Set the information cell group of the mth task as Tm=VIm,VOm,Lm,Ωm,Rm, in which VIm denotes to the input data size of task m, VOm denotes to the output data size of task m, Lm denotes to the required operand of task m, Ωm denotes to the time delay requirement of task m, and Rm denotes to the reward paid by task m.


## 3.3. Communication Model

The paper supposes a mobile device only communicates with one edge server, so when uploading or downloading data, there is no interference from other device transmission. Define the transmission rate between mobile devicem and edge server n as shown in Equation (1) [19]:
(1)dm,n=Blog21+pmgm,nσ2,in which B is the bandwidth, pm is the transmission rate, gm,n represents the channel gains, and σ2 is the noise power. The calculation formula of channel gain gm,n is shown in Equation (2) [19]:
(2)gm,n=G3×1084πFcdistm,nPL,in which G is the antenna gain, Fc is the carrier frequency, distm,n represents the distance between mobile device m and edge server n, and PL is the path loss factor. According to Equations (1) and (2), the data transmission rate can be calculated by the distance between mobile device and edge server.


## 3.4. Time Delay and Energy Cost Model

The local computing delay of task is shown in Equation (3), in which fm is the computing rate of mobile device m.
(3)Dmlocal=Lmfm.In case that taskm is offloaded to edge server n, then the corresponding task delay is shown in
(4)Dm,noff=Dm,nu+Dm,nd+Dm,nc,(5)Dm,nu=VImdm,n,(6)Dm,nd=VOmdm,n,(7)Dm,nc=Lmfn,in which Dm,nu is the task uploading time, Dm,nd is the result downloading time, Dm,nc is the task computing time on edge server, and fn is the computing rate of edge server.On account of the benefit of edge server, it is necessary to figure out the energy cost overhead of edge server, and the greater the energy cost overhead is, the smaller the benefit will be. The energy cost overhead of edge server is shown in(8)cm,n=Pcom,n×Dm,nc+Ptra,n×Dm,nu+Dm,nd,in which Pcom,n is the computing power of edge server n and Ptra,n is the transmission power of edge server n.


## 3.5. Benefit and Overhead Model

The cost overhead that an edge servern completes the offloading task of mobile device m is shown in
(9)πm,n=cm,n,dm,n>0,∞,dm,n<0.That is to say, when the communication rate between edge servern and mobile device m is normal, the overhead is the cost of edge server; when edge server n cannot communicate with mobile device m, the overhead of edge server is infinite.Edge servers compete for task according to overhead function (9), and ever edge server attempts to find the optimal strategy, minimizing its overhead. This causes all edge servers do not receive any task to save overhead (not receiving any task means no cost overhead to be paid). However, this result clearly contradicts the purpose of MEC system, and it makes no sense for mobile device to offload task, so mobile devices need to provide certain rewards. The specific benefit obtained by an edge server can be calculated by the initial reward Rm of mobile device task and a penalty function punishm,n [20]. The computing method of penalty function is shown in
(10)punishm,n=λmΩmΩm−Dm,noff+ω,Dm,noff≤Ωm,∞,Dm,noff>Ωm,in which Ωm is the required deadline of task m and Dm,noff is the completion time for the server n to complete the offloaded task. ω is a very small nonzero positive number, used to prevent denominator as zero when offloading task completion delay just satisfies task delay requirement. λ is the penalty coefficient, used for dynamic adjustment by reverse update method (see details in Section 4.2). This penalty function is set to give different penalties based on the speed at which edge server completes the task; i.e., the more time intervals left for edge server to complete task, the smaller the penalty will be. Next, it is needed to set a benefit indicator function um,n, by computing which an edge server can make its decision. The benefit indicator function um,n is defined as shown in
(11)um,n=Rm×Ωm−Dm,noff+ωλm×Ωm×Nm×cm,n,πm,n≠∞,0,πm,n=∞,in which Nm represents the number of edge servers choosing the task m; i.e., the more tasks are selected, the lower the value of the reward indicator function. Benefit refers to what the edge server can ultimately get. The benefit contains multiple factors; the purpose is to allow multiple factors to affect the edge server comprehensively. These factors are of similar importance and can affect the selection of edge servers.


## 3.6. Task Offloading Model

The system model in this paper is referred to [21, 22]. In order to verify the effect of the scheme, it is considered that the task of the mobile device is inseparable; that is, the task cannot be divided into multiple edge servers for completion. And if the edge server selects the mobile device task, it uses all its computing resources for computing, so one edge server can receive at most one task at the same time. On the basis of above agreement, the paper expresses the allocation strategy of mobile device m as am=am,0,am,1,⋯,am,N, in which am,n=0,1; the value of am,0 represents whether to calculate locally. Therefore, the total strategy configuration of MEC system can be obtained as A=a1,a2,⋯,aM, satisfying ∑i=1Mai,n≤1,∀n∈ES and∑i=1Nam,i≤1,∀m∈Task.


## 3.7. Objective Function

In the competition game on edge server side, the objective of every edge server is to maximize its own benefit. So, the general objective on edge server side is shown in(12)benefitm,n=Rm×Ωm−Dm,noff+ωΩm×cm,n,πm,n≠∞,0,πm,n=∞,(13)maximize:∑i=1N∑m∈Sibenefitm,i,in which Si represents the task set selected by edge server i, which is the subset of Task, and benefitm,i represents the benefit obtained by edge server i to complete mobile device m task. This objective function represents maximizing the total edge server benefit on the edge server side.On mobile device side, every mobile device needing to offload tasks expects its task to be completed. Thus, the total objective function on mobile device side is shown in(14)maximize:∑i=1Mθi.θi is a binary variable. If the task of mobile device i can be completed within required time delay, then its value is 1; otherwise, it is 0. This objective function represents making more offloading tasks to be completed on time as possible.


## 4. Two-Way Update Resource Allocation Strategy

The TUSGT designed in this paper optimizes resource allocation strategies from objective functions (13) and (14), respectively. One is to optimize on edge server side, and the other is to update parameters on mobile device side, as shown in Figure 1.On edge server side, the edge servers do not know each other’s configuration and state information, which is a noncollaborative game problem. Since a large number of edge servers may not belong to the same manufacturer in practice, each of them needs to consider their own interests, so it will not be a complete cooperative game problem. In order to obtain higher benefits for itself, the edge server will not hand over all its configuration information to the management server but will only select the most suitable task according to its own configuration. The management server only receives the task selection of the edge server but does not have the configuration information of the edge server. So, the paper designed a game-based joint optimization strategy (GBJOS) to solve this problem. When the GBJOS converges, all edge servers will not actively apply for strategy modification. On mobile device side, the classic EWA algorithm [20] in online learning can be used for updating, to satisfy the objectives on mobile device side.


### 4.1. Game-Based Joint Optimization Strategy

#### 4.1.1. Game Model

This paper established a game model of multiuser and multiedge server resource allocation in MEC and then made definition for it, as so to analyze this game model.Definition 1.
The offloading task set isTask=T1,T2,⋯,TM. When mobile device m does not have enough local resources to complete the task, i.e., Dmlocal≥Ωm, the mobile device m will decide to offload the task. At this moment, this mobile device will be added to MD set; its task and task-related information will be added in the Task set.Definition 2.
After completing the taskm, if edge server n′ obtains higher benefit than edge server n, then task m will be allocated to edge server n′.Definition 3.
If in current resource allocation strategy of MEC system, the taskm has been allocated to edge server n, then edge server n calculates the value of benefit indicator function (11) for task m; its Nm value is 1. Otherwise, when this server performs calculation, the Nm value should be a normal accumulated value.Definition 4.
Task selection thresholdN_TO. When the number of mobile device m task selected reaches to the threshold N_TO, that’s to say, Nm≥N_TO, other edge servers are not allowed to choose the task.From Definition1, it is known that now all tasks in Task set need to perform offloading computing, and edge servers will compete for tasks in Task set to gain benefit. Definition 2 ensures to maximize the total benefit of edge servers, that’s to say, if the selection of different edge servers conflicts, the task will be allocated to the one with greater benefit. Definition 3 is set to increase the cost of selection conflict between different edge servers, so that the selection of edge servers can be dispersed as possible. Definition 4 is to prevent this game from falling into an infinite loop and guarantee every edge server must complete the final selection within a certain number of times. The specific value of threshold N_TO 的shall be adjusted according to real data setup.According to the above definitions, the following lemma is given:Lemma 5.
After all edge servers hold tasks, they will tend to keep the currently selected task in subsequent selections.Proof.
Suppose that the servern currently chooses task k and have held it. In the next round of selection, if the server n selects the task k′, then there must be:
(15)uk,n<uk′,nCombined with Eq.(11) and Definition 3, it is obtained that:
(16)Rk×Ωk−Dk,noff+ωλk×Ωk×1×ck,n<Rk′×Ωk′−Dk′,noff+ωλk′×Ωk′×Nk′×ck′,n
Since the current selection is taskk, it is proved the following result appears in the last round of calculation:
(17)max∀m∈1,2,⋯,MRm×Ωm−Dm,noff+ωλm×Ωm×Nm×cm,n=Rk×Ωk−Dk,noff+ωλk×Ωk×Nk×ck,n
It is certainly that:(18)Rk×Ωk−Dk,noff+ωλk×Ωk×Nk×ck,n≥Rk′×Ωk′−Dk′,noff+ωλk′×Ωk′×Nk′×ck′,nin which, Nk≥1, then,
(19)Rk×Ωk−Dk,noff+ωλk×Ωk×1×ck,n≥Rk×Ωk−Dk,noff+ωλk×Ωk×Nk×ck,n
It is obtained that(20)Rk×Ωk−Dk,noff+ωλk×Ωk×1×ck,n≥Rk′×Ωk′−Dk′,noff+ωλk′×Ωk′×Nk′×ck′,n
Thus, the contradiction between Equations (20) and (16) is proved.Based on above lemmas and definitions, the model is analyzed by game theory. We usea‐n=a1,⋯,an‐1,an+1,⋯,aN to represent all resource allocation strategies for edge serves other than edge server n. Providing the selection a‐n of all other edge servers, the edge server n will make current round of selection according to a‐n and by figuring out the value of Eq.(11). It can be seen that in Eq.(11), for each edge server, only the parameter Nm is unknown, so edge servers can make strategy selection only if they get the value of Nm, with no need to know the configuration and state information of remaining edge servers.


#### 4.1.2. Model Analysis

This section firstly defines Nash equilibrium and potential game, and then uses potential game to prove the existence of Nash equilibrium in the game [21].Definition 6.
If a resource allocation strategyA∗=a1∗,⋯,aN∗ is a Nash equilibrium in resource allocation game for multiuser and multiedge server; then, in the case of resource allocation strategy A∗, no edge server can further improve its benefit by unilaterally changing its selection strategy. That is,
(21)unan∗,a−n∗≥unan,a−n∗,∀an∈Task,n∈ES.Definition 7.
If a game has the following properties, it is called an ordinal potential game:∃ϕA, for each n∈ES,an,an′∈Task, if
(22)uyan′,a−n>unan,a−n,then
(23)ϕan′,a−n>ϕan,a−n.Ordinal potential game has a property, i.e., the existence of a Nash equilibrium as well as finite improvement properties. In this way, any asynchronous optimal response updating process (no more than one participator maximizes its benefit by updating strategy) must be finite and will eventually result in Nash equilibrium [21]. In order to prove that the game in this paper is an ordinal potential game, the potential function of the paper is constructed as
(24)ϕA=∑i=1N∑j=1MRj×Ωj−Dj,ioff+ωΩj×cj,iIaj,i=1,in which IU is an indicator function. If U expression is correct, then IU=1; otherwise, IU=0.Theorem 8.
The resource allocation game model between edge servers in the paper is a finite ordinal potential game with potential function (24).Proof.
Assume that a servern∈ES changes its selection k to k′, and the allocation strategy will be updated from A to A′. This will cause an increase of its benefit indicator function value, i.e., uk′,n>uk,n. According to the definition of potential function, it can be discovered this will result in higher potential function value, i.e., ϕA′>ϕA. From the lemma, it can be obtained when selection update occurs, there must be k=0, i.e., not selecting the task uk,n=0. Thus, there are only two situations to consider: (1) ak′,n=0 and (2) ak′,n≠0.
Becausek=0, then uk,n=0, that is to say,
(25)Rk×Ωk−Dk,noff+ωΩk×ck,n=0.(1)
In caseak′,n=0, then uk′,n>uk,n=0, it can be obtained by Equation (11) that(26)Rk′×Ωk′−Dk′,noff+ωλk′×Ωk′×Nk′×ck′,n>0
Asλk′>0,Nk′>0, the above equation can be reduced to
(27)Rk′×Ωk′−Dk′,noff+ωΩk′×ck′,n>0.
According to Definition7, it is needed to compare the potential function under different strategies, and their size can be expressed by the difference of the two. The specific calculation process is as follows:
(28)ϕA′−ϕA=∑i=1N∑j=1MRj×Ωj−Dj,ioff+ωΩj×cj,iIaj,i′=1Ii≠n+∑j=1MRj×Ωj−Dj,noff+ωΩj×cj,nIaj,i′=1−∑i=1N∑j=1MRj×Ωj−Dj,ioff+ωΩj×cj,iIaj,i=1Ii≠n−∑j=1MRj×Ωj−Dj,noff+ωΩj×cj,nIaj,i=1=∑j=1MRj×Ωj−Dj,noff+ωΩj×cj,nIaj,i′=1−Rk×Ωk−Dk,noff+ωΩk×ck,n=Rk′×Ωk′−Dk′,noff+ωΩk′×ck′,n>0.(2)
In caseak′,n≠0, it can be obtained by Definition 3 that, if strategy update occurs at this time, there must be the following inequation:(29)Rk′×Ωk′−Dk′,noff+ωΩk′×ck′,n>Rk′×Ωk′−Dk′,n′off+ωΩk′×ck′,n′
Integrating with Definition7, the potential function under different strategies is compared. The specific calculation process is as follows:
(30)ϕA′−ϕA=∑i=1N∑j=1MRj×Ωj−Dj,ioff+ωΩj×cj,iIaj,i′=1Ii≠nIi≠n′+∑j=1MRj×Ωj−Dj,noff+ωΩj×cj,nIaj,n′=1+∑j=1MRj×Ωj−Dj,n′off+ωΩj×cj,n′Iaj,n′′=1−∑i=1N∑j=1MRj×Ωj−Dj,ioff+ωΩj×cj,iIaj,i=1Ii≠nIi≠n′−∑j=1MRj×Ωj−Dj,noff+ωΩj×cj,nIaj,n=1−∑j=1MRj×Ωj−Dj,n′off+ωΩj×cj,n′Iaj,n′=1=Rk′×Ωk′−Dk′,noff+ωΩk′×ck′,n−Rk′×Ωk′−Dk′,n′off+ωΩk′×ck′,n′>0.
Combing with the results of Equations (28) and (30) as well as Definition 4, it is concluded that the MEC multiuser and multiedge server resource allocation game proposed in the paper is a finite ordinal potential game. Therefore, the game has the characteristics of a finite ordinal potential game, including limited improvement properties.


#### 4.1.3. Game Strategy Design

The above section verifies the MEC multiuser and multiedge server resource allocation game has Nash equilibrium, and this section introduces the strategy to solve Nash equilibrium in details. There are some classical algorithms for finding the existence of Nash equilibrium, such as optimum response [18] and reinforcement learning [22]. However, the problem of finding Nash equilibrium in the model of this paper is incomplete information; that is to say, all configuration information for each edge server is held only by itself. Thus, an edge server cannot make its own optimal response according to the optimal selection of other edge servers. So this paper chose to use game theory for problem solution. Through the above proof, this paper designed a game-based joint optimization strategy (GBJOS) to solve the competition problem of edge server, as shown in Strategy 9.Strategy 9.
Iteration-based optimal energy efficiency update algorithm.
Input Mobile device’s task information
Output Resource allocation strategy A
Initialization Initialize the resource allocation strategy of system, set task selection threshold as N_TO=M/2, set maximum iteration times maxIter=100
1)whileconverge≠True and iter<maxIterdo
2)iter⟵iter+1
3) administrative server transmitsTask, A, Nm, N_TO, λm to each edge server
receive parameter information
6)  based on Definitions3 and 4, maximize the value of Eq. (11), select the optimal strategy brn for them
7)  transmit the strategybrn to administrative server
8)ifbrn is not null, and currently do not hold brnthen
9)  request strategy change from administrative server
10)end if
11)end for
12)if administrative server does not receive any request then
13)converge⟵True
14)else
15)  randomly choose an edger serve and allow it to update strategy
16)  based on this round of received strategybrn, update A
17)  based on this round of strategy update of all edge servers
18)end if
19)end while
20)ReturnAGBJOS mainly includes two parts: strategy selection of edge server and collection of strategy update information from administrative server.(i)
Strategy selection of edge server: edge servers obtain the related parameters of Equation (11) from administrative server, for calculating the benefit of all tasks unan,a−n,n∈ES,an,a′n∈Task, choose the task with the largest benefit as this round of strategy selection. In case an edge server does not hold the task selected for this round, it can send a request to administrative server for strategy modification.(ii)
Collection of strategy update information from administrative server: in each round of iteration, the administrative server can receive the current strategy selection of all edge servers as well as the request of some edge servers for modification. If no request for modification is received, it is judged as convergence; otherwise, administrative server shall gather current strategies, then randomly choose an edge server having send request for modification and permit it to change current resource allocation strategy [23]. Meanwhile, the administrative server updates resource allocation strategy and transmits collected parameters to each edge server.


#### 4.1.4. Convergence Analysis

In Theorem8, we have proved this game is a finite ordinal potential game, so this strategy will converge to Nash equilibrium within in limited number of iteration times. In practical strategy execution, when the administrative server does not receive any request for modification, it is judged as strategy convergence; at this time, the update of resource allocation strategy will be ended.Next, the time complexity of GBJOS will be analyzed. Within each iteration, every edge server performs task selection in parallel. Therein, some sorting operation and basic operations are involved, so the time complexity of this part isONlogN. It is assumed that this strategy will go through C times of iteration before reaching to termination, so the overall time complexity of GBJOS is OCNlogN. It is clear whether this strategy can converge within limited times relies on whether iteration time C has a upper bound or not.Theorem 10.
When for∀m∈1,2,⋯,M, ∀n∈1,2,⋯,N,Dm,noff≤Ωm, Rm>cm,n occurs, GBJOS will terminate after iterating for maxN∗Q∗Ωmax/ω,M∗N_TO times at most, i.e., C<maxN∗Q∗Ωmax/ω,M∗N_TO.Proof.
During iteration, it is assumed that edge servern updates current task selection k to k′, and updates allocation strategy A to A′. Based on Definition 4 and lemma, it is obtained that k=0; then there are two main scenarios to consider: (1) ak′,n=0 and (2) ak′,n≠0(1)
ak′,n=0: the theoretical maximal benefit is expressed as(31)Q=max∀m∈1,2,⋯,M,∀n∈1,2,⋯,NRm×Ωm−Dm,noff+ωΩm×cm,n
According to potential function (24), it can be obtained that
(32)0≤ϕA≤∑i=1N∑j=1MQIaj,i=1<NQ.
According to the nature of potential game, strategy change will lead to the increase of potential function value. Suppose the minimal granularity of potential game increase to beQmin, that is to say,
(33)ϕA′≥ϕA+Qmin.
According to Equation (28), it can be obtained that
(34)ϕA′−ϕA≥ωΩk′.
Define the maximal time delay as(35)Ωmax=max∀m∈1,2,⋯,MΩm.
There must be(36)Ωk′≤Ωmax.
That is to say,(37)ϕA′−ϕA≥ωΩmax>0,ak′,n≠0.If the strategy selection of edge servers contradicts, it can be known from Definitions3 and 4 that for a task, whether a server can successfully snatch it or not, the upper bound of conflict times is N_TO. So, in this case, the upper bound of strategy conflict times is M∗N_TO.Through the analysis of above two cases, it can be concluded that: iteration timesC<maxN∗Q∗Ωmax/ω,M∗N_TO.


### 4.2. Reverse Update of Parameters

The above-mentioned GBJOS strategy makes edge server to maximize its benefit; finally, all edge servers can reach an agreement. In this section, the penalty coefficientλ in Equation (10) was dynamically adjusted by setting loss function. The penalty coefficient is designed to give different significance scoring to the tasks of different size, and edge servers determine their own strategy selection by working out Equation (11). So, penalty coefficient λ plays an important role in guiding edge server to make strategy selection. If different tasks have great difference in λ, it would be unfair to some tasks, making λ to exert large impact on the value of Equation (11), while ignoring the influence of other parameters; but if different tasks have too small difference in λ, the gap between task priority is too small, then edge server would still make strategy selection according to the initial condition of a task, and the updates do not work as it is expected to be.In the TUSGT of this paper, penalty coefficient is updated dynamically through online learning framework. The paper sets a loss functionφ; each task will be updated to varied extent according to its own data characteristics. By virtue of such automatic dynamic adjustment, tasks are given different priorities, reaching the purpose of improving deadline hit rate. The loss function φm for task m is calculated as shown in
(38)φm=VIm−∑i=1MVIi×θi∑i=1Mθi,∑i=1Mθi≠0,in which θi refers to whether task i is completed on time or not (see details in Section 3.7). The penalty coefficient λ is updated by EWA algorithm [24], as shown in
(39)λmnew=λmold×e−ηφm,∑i=1Mθi≠0,λmold×12,∑i=1Mθi=0.When no task is completed on time, the penalty coefficient of all tasks is halved, to increase task attraction. It can be seen from Equation (39) that, in general condition, the priority of the task with large volume of data will be elevated, while the update extent relies on the task completion of current strategy. Therein, the update extent of penalty coefficient also depends on the value of learning rate η, which should be set artificially according to actual initial task information. The value of η also decides the update times of TUSGT; the smaller the update extent is, the more times it will be updated. While updating too much will result in unsatisfactory result, so it needs to be weighed against actual data. The penalty coefficient needs to be adjusted according to the actual task size and the computing power of the edge server. It is only necessary to use the parameters expected in the scene as input and make multiple adjustments. The variation of this coefficient is also affected by the size of the task, but in general, the edge server can be guided to make a choice that is more conducive to the overall task completion rate of the MEC system.


## 4.1. Game-Based Joint Optimization Strategy

### 4.1.1. Game Model

This paper established a game model of multiuser and multiedge server resource allocation in MEC and then made definition for it, as so to analyze this game model.Definition 1.
The offloading task set isTask=T1,T2,⋯,TM. When mobile device m does not have enough local resources to complete the task, i.e., Dmlocal≥Ωm, the mobile device m will decide to offload the task. At this moment, this mobile device will be added to MD set; its task and task-related information will be added in the Task set.Definition 2.
After completing the taskm, if edge server n′ obtains higher benefit than edge server n, then task m will be allocated to edge server n′.Definition 3.
If in current resource allocation strategy of MEC system, the taskm has been allocated to edge server n, then edge server n calculates the value of benefit indicator function (11) for task m; its Nm value is 1. Otherwise, when this server performs calculation, the Nm value should be a normal accumulated value.Definition 4.
Task selection thresholdN_TO. When the number of mobile device m task selected reaches to the threshold N_TO, that’s to say, Nm≥N_TO, other edge servers are not allowed to choose the task.From Definition1, it is known that now all tasks in Task set need to perform offloading computing, and edge servers will compete for tasks in Task set to gain benefit. Definition 2 ensures to maximize the total benefit of edge servers, that’s to say, if the selection of different edge servers conflicts, the task will be allocated to the one with greater benefit. Definition 3 is set to increase the cost of selection conflict between different edge servers, so that the selection of edge servers can be dispersed as possible. Definition 4 is to prevent this game from falling into an infinite loop and guarantee every edge server must complete the final selection within a certain number of times. The specific value of threshold N_TO 的shall be adjusted according to real data setup.According to the above definitions, the following lemma is given:Lemma 5.
After all edge servers hold tasks, they will tend to keep the currently selected task in subsequent selections.Proof.
Suppose that the servern currently chooses task k and have held it. In the next round of selection, if the server n selects the task k′, then there must be:
(15)uk,n<uk′,nCombined with Eq.(11) and Definition 3, it is obtained that:
(16)Rk×Ωk−Dk,noff+ωλk×Ωk×1×ck,n<Rk′×Ωk′−Dk′,noff+ωλk′×Ωk′×Nk′×ck′,n
Since the current selection is taskk, it is proved the following result appears in the last round of calculation:
(17)max∀m∈1,2,⋯,MRm×Ωm−Dm,noff+ωλm×Ωm×Nm×cm,n=Rk×Ωk−Dk,noff+ωλk×Ωk×Nk×ck,n
It is certainly that:(18)Rk×Ωk−Dk,noff+ωλk×Ωk×Nk×ck,n≥Rk′×Ωk′−Dk′,noff+ωλk′×Ωk′×Nk′×ck′,nin which, Nk≥1, then,
(19)Rk×Ωk−Dk,noff+ωλk×Ωk×1×ck,n≥Rk×Ωk−Dk,noff+ωλk×Ωk×Nk×ck,n
It is obtained that(20)Rk×Ωk−Dk,noff+ωλk×Ωk×1×ck,n≥Rk′×Ωk′−Dk′,noff+ωλk′×Ωk′×Nk′×ck′,n
Thus, the contradiction between Equations (20) and (16) is proved.Based on above lemmas and definitions, the model is analyzed by game theory. We usea‐n=a1,⋯,an‐1,an+1,⋯,aN to represent all resource allocation strategies for edge serves other than edge server n. Providing the selection a‐n of all other edge servers, the edge server n will make current round of selection according to a‐n and by figuring out the value of Eq.(11). It can be seen that in Eq.(11), for each edge server, only the parameter Nm is unknown, so edge servers can make strategy selection only if they get the value of Nm, with no need to know the configuration and state information of remaining edge servers.


### 4.1.2. Model Analysis

This section firstly defines Nash equilibrium and potential game, and then uses potential game to prove the existence of Nash equilibrium in the game [21].Definition 6.
If a resource allocation strategyA∗=a1∗,⋯,aN∗ is a Nash equilibrium in resource allocation game for multiuser and multiedge server; then, in the case of resource allocation strategy A∗, no edge server can further improve its benefit by unilaterally changing its selection strategy. That is,
(21)unan∗,a−n∗≥unan,a−n∗,∀an∈Task,n∈ES.Definition 7.
If a game has the following properties, it is called an ordinal potential game:∃ϕA, for each n∈ES,an,an′∈Task, if
(22)uyan′,a−n>unan,a−n,then
(23)ϕan′,a−n>ϕan,a−n.Ordinal potential game has a property, i.e., the existence of a Nash equilibrium as well as finite improvement properties. In this way, any asynchronous optimal response updating process (no more than one participator maximizes its benefit by updating strategy) must be finite and will eventually result in Nash equilibrium [21]. In order to prove that the game in this paper is an ordinal potential game, the potential function of the paper is constructed as
(24)ϕA=∑i=1N∑j=1MRj×Ωj−Dj,ioff+ωΩj×cj,iIaj,i=1,in which IU is an indicator function. If U expression is correct, then IU=1; otherwise, IU=0.Theorem 8.
The resource allocation game model between edge servers in the paper is a finite ordinal potential game with potential function (24).Proof.
Assume that a servern∈ES changes its selection k to k′, and the allocation strategy will be updated from A to A′. This will cause an increase of its benefit indicator function value, i.e., uk′,n>uk,n. According to the definition of potential function, it can be discovered this will result in higher potential function value, i.e., ϕA′>ϕA. From the lemma, it can be obtained when selection update occurs, there must be k=0, i.e., not selecting the task uk,n=0. Thus, there are only two situations to consider: (1) ak′,n=0 and (2) ak′,n≠0.
Becausek=0, then uk,n=0, that is to say,
(25)Rk×Ωk−Dk,noff+ωΩk×ck,n=0.(1)
In caseak′,n=0, then uk′,n>uk,n=0, it can be obtained by Equation (11) that(26)Rk′×Ωk′−Dk′,noff+ωλk′×Ωk′×Nk′×ck′,n>0
Asλk′>0,Nk′>0, the above equation can be reduced to
(27)Rk′×Ωk′−Dk′,noff+ωΩk′×ck′,n>0.
According to Definition7, it is needed to compare the potential function under different strategies, and their size can be expressed by the difference of the two. The specific calculation process is as follows:
(28)ϕA′−ϕA=∑i=1N∑j=1MRj×Ωj−Dj,ioff+ωΩj×cj,iIaj,i′=1Ii≠n+∑j=1MRj×Ωj−Dj,noff+ωΩj×cj,nIaj,i′=1−∑i=1N∑j=1MRj×Ωj−Dj,ioff+ωΩj×cj,iIaj,i=1Ii≠n−∑j=1MRj×Ωj−Dj,noff+ωΩj×cj,nIaj,i=1=∑j=1MRj×Ωj−Dj,noff+ωΩj×cj,nIaj,i′=1−Rk×Ωk−Dk,noff+ωΩk×ck,n=Rk′×Ωk′−Dk′,noff+ωΩk′×ck′,n>0.(2)
In caseak′,n≠0, it can be obtained by Definition 3 that, if strategy update occurs at this time, there must be the following inequation:(29)Rk′×Ωk′−Dk′,noff+ωΩk′×ck′,n>Rk′×Ωk′−Dk′,n′off+ωΩk′×ck′,n′
Integrating with Definition7, the potential function under different strategies is compared. The specific calculation process is as follows:
(30)ϕA′−ϕA=∑i=1N∑j=1MRj×Ωj−Dj,ioff+ωΩj×cj,iIaj,i′=1Ii≠nIi≠n′+∑j=1MRj×Ωj−Dj,noff+ωΩj×cj,nIaj,n′=1+∑j=1MRj×Ωj−Dj,n′off+ωΩj×cj,n′Iaj,n′′=1−∑i=1N∑j=1MRj×Ωj−Dj,ioff+ωΩj×cj,iIaj,i=1Ii≠nIi≠n′−∑j=1MRj×Ωj−Dj,noff+ωΩj×cj,nIaj,n=1−∑j=1MRj×Ωj−Dj,n′off+ωΩj×cj,n′Iaj,n′=1=Rk′×Ωk′−Dk′,noff+ωΩk′×ck′,n−Rk′×Ωk′−Dk′,n′off+ωΩk′×ck′,n′>0.
Combing with the results of Equations (28) and (30) as well as Definition 4, it is concluded that the MEC multiuser and multiedge server resource allocation game proposed in the paper is a finite ordinal potential game. Therefore, the game has the characteristics of a finite ordinal potential game, including limited improvement properties.


### 4.1.3. Game Strategy Design

The above section verifies the MEC multiuser and multiedge server resource allocation game has Nash equilibrium, and this section introduces the strategy to solve Nash equilibrium in details. There are some classical algorithms for finding the existence of Nash equilibrium, such as optimum response [18] and reinforcement learning [22]. However, the problem of finding Nash equilibrium in the model of this paper is incomplete information; that is to say, all configuration information for each edge server is held only by itself. Thus, an edge server cannot make its own optimal response according to the optimal selection of other edge servers. So this paper chose to use game theory for problem solution. Through the above proof, this paper designed a game-based joint optimization strategy (GBJOS) to solve the competition problem of edge server, as shown in Strategy 9.Strategy 9.
Iteration-based optimal energy efficiency update algorithm.
Input Mobile device’s task information
Output Resource allocation strategy A
Initialization Initialize the resource allocation strategy of system, set task selection threshold as N_TO=M/2, set maximum iteration times maxIter=100
1)whileconverge≠True and iter<maxIterdo
2)iter⟵iter+1
3) administrative server transmitsTask, A, Nm, N_TO, λm to each edge server
receive parameter information
6)  based on Definitions3 and 4, maximize the value of Eq. (11), select the optimal strategy brn for them
7)  transmit the strategybrn to administrative server
8)ifbrn is not null, and currently do not hold brnthen
9)  request strategy change from administrative server
10)end if
11)end for
12)if administrative server does not receive any request then
13)converge⟵True
14)else
15)  randomly choose an edger serve and allow it to update strategy
16)  based on this round of received strategybrn, update A
17)  based on this round of strategy update of all edge servers
18)end if
19)end while
20)ReturnAGBJOS mainly includes two parts: strategy selection of edge server and collection of strategy update information from administrative server.(i)
Strategy selection of edge server: edge servers obtain the related parameters of Equation (11) from administrative server, for calculating the benefit of all tasks unan,a−n,n∈ES,an,a′n∈Task, choose the task with the largest benefit as this round of strategy selection. In case an edge server does not hold the task selected for this round, it can send a request to administrative server for strategy modification.(ii)
Collection of strategy update information from administrative server: in each round of iteration, the administrative server can receive the current strategy selection of all edge servers as well as the request of some edge servers for modification. If no request for modification is received, it is judged as convergence; otherwise, administrative server shall gather current strategies, then randomly choose an edge server having send request for modification and permit it to change current resource allocation strategy [23]. Meanwhile, the administrative server updates resource allocation strategy and transmits collected parameters to each edge server.


### 4.1.4. Convergence Analysis

In Theorem8, we have proved this game is a finite ordinal potential game, so this strategy will converge to Nash equilibrium within in limited number of iteration times. In practical strategy execution, when the administrative server does not receive any request for modification, it is judged as strategy convergence; at this time, the update of resource allocation strategy will be ended.Next, the time complexity of GBJOS will be analyzed. Within each iteration, every edge server performs task selection in parallel. Therein, some sorting operation and basic operations are involved, so the time complexity of this part isONlogN. It is assumed that this strategy will go through C times of iteration before reaching to termination, so the overall time complexity of GBJOS is OCNlogN. It is clear whether this strategy can converge within limited times relies on whether iteration time C has a upper bound or not.Theorem 10.
When for∀m∈1,2,⋯,M, ∀n∈1,2,⋯,N,Dm,noff≤Ωm, Rm>cm,n occurs, GBJOS will terminate after iterating for maxN∗Q∗Ωmax/ω,M∗N_TO times at most, i.e., C<maxN∗Q∗Ωmax/ω,M∗N_TO.Proof.
During iteration, it is assumed that edge servern updates current task selection k to k′, and updates allocation strategy A to A′. Based on Definition 4 and lemma, it is obtained that k=0; then there are two main scenarios to consider: (1) ak′,n=0 and (2) ak′,n≠0(1)
ak′,n=0: the theoretical maximal benefit is expressed as(31)Q=max∀m∈1,2,⋯,M,∀n∈1,2,⋯,NRm×Ωm−Dm,noff+ωΩm×cm,n
According to potential function (24), it can be obtained that
(32)0≤ϕA≤∑i=1N∑j=1MQIaj,i=1<NQ.
According to the nature of potential game, strategy change will lead to the increase of potential function value. Suppose the minimal granularity of potential game increase to beQmin, that is to say,
(33)ϕA′≥ϕA+Qmin.
According to Equation (28), it can be obtained that
(34)ϕA′−ϕA≥ωΩk′.
Define the maximal time delay as(35)Ωmax=max∀m∈1,2,⋯,MΩm.
There must be(36)Ωk′≤Ωmax.
That is to say,(37)ϕA′−ϕA≥ωΩmax>0,ak′,n≠0.If the strategy selection of edge servers contradicts, it can be known from Definitions3 and 4 that for a task, whether a server can successfully snatch it or not, the upper bound of conflict times is N_TO. So, in this case, the upper bound of strategy conflict times is M∗N_TO.Through the analysis of above two cases, it can be concluded that: iteration timesC<maxN∗Q∗Ωmax/ω,M∗N_TO.


## 4.1.1. Game Model

This paper established a game model of multiuser and multiedge server resource allocation in MEC and then made definition for it, as so to analyze this game model.Definition 1.
The offloading task set isTask=T1,T2,⋯,TM. When mobile device m does not have enough local resources to complete the task, i.e., Dmlocal≥Ωm, the mobile device m will decide to offload the task. At this moment, this mobile device will be added to MD set; its task and task-related information will be added in the Task set.Definition 2.
After completing the taskm, if edge server n′ obtains higher benefit than edge server n, then task m will be allocated to edge server n′.Definition 3.
If in current resource allocation strategy of MEC system, the taskm has been allocated to edge server n, then edge server n calculates the value of benefit indicator function (11) for task m; its Nm value is 1. Otherwise, when this server performs calculation, the Nm value should be a normal accumulated value.Definition 4.
Task selection thresholdN_TO. When the number of mobile device m task selected reaches to the threshold N_TO, that’s to say, Nm≥N_TO, other edge servers are not allowed to choose the task.From Definition1, it is known that now all tasks in Task set need to perform offloading computing, and edge servers will compete for tasks in Task set to gain benefit. Definition 2 ensures to maximize the total benefit of edge servers, that’s to say, if the selection of different edge servers conflicts, the task will be allocated to the one with greater benefit. Definition 3 is set to increase the cost of selection conflict between different edge servers, so that the selection of edge servers can be dispersed as possible. Definition 4 is to prevent this game from falling into an infinite loop and guarantee every edge server must complete the final selection within a certain number of times. The specific value of threshold N_TO 的shall be adjusted according to real data setup.According to the above definitions, the following lemma is given:Lemma 5.
After all edge servers hold tasks, they will tend to keep the currently selected task in subsequent selections.Proof.
Suppose that the servern currently chooses task k and have held it. In the next round of selection, if the server n selects the task k′, then there must be:
(15)uk,n<uk′,nCombined with Eq.(11) and Definition 3, it is obtained that:
(16)Rk×Ωk−Dk,noff+ωλk×Ωk×1×ck,n<Rk′×Ωk′−Dk′,noff+ωλk′×Ωk′×Nk′×ck′,n
Since the current selection is taskk, it is proved the following result appears in the last round of calculation:
(17)max∀m∈1,2,⋯,MRm×Ωm−Dm,noff+ωλm×Ωm×Nm×cm,n=Rk×Ωk−Dk,noff+ωλk×Ωk×Nk×ck,n
It is certainly that:(18)Rk×Ωk−Dk,noff+ωλk×Ωk×Nk×ck,n≥Rk′×Ωk′−Dk′,noff+ωλk′×Ωk′×Nk′×ck′,nin which, Nk≥1, then,
(19)Rk×Ωk−Dk,noff+ωλk×Ωk×1×ck,n≥Rk×Ωk−Dk,noff+ωλk×Ωk×Nk×ck,n
It is obtained that(20)Rk×Ωk−Dk,noff+ωλk×Ωk×1×ck,n≥Rk′×Ωk′−Dk′,noff+ωλk′×Ωk′×Nk′×ck′,n
Thus, the contradiction between Equations (20) and (16) is proved.Based on above lemmas and definitions, the model is analyzed by game theory. We usea‐n=a1,⋯,an‐1,an+1,⋯,aN to represent all resource allocation strategies for edge serves other than edge server n. Providing the selection a‐n of all other edge servers, the edge server n will make current round of selection according to a‐n and by figuring out the value of Eq.(11). It can be seen that in Eq.(11), for each edge server, only the parameter Nm is unknown, so edge servers can make strategy selection only if they get the value of Nm, with no need to know the configuration and state information of remaining edge servers.


## 4.1.2. Model Analysis

This section firstly defines Nash equilibrium and potential game, and then uses potential game to prove the existence of Nash equilibrium in the game [21].Definition 6.
If a resource allocation strategyA∗=a1∗,⋯,aN∗ is a Nash equilibrium in resource allocation game for multiuser and multiedge server; then, in the case of resource allocation strategy A∗, no edge server can further improve its benefit by unilaterally changing its selection strategy. That is,
(21)unan∗,a−n∗≥unan,a−n∗,∀an∈Task,n∈ES.Definition 7.
If a game has the following properties, it is called an ordinal potential game:∃ϕA, for each n∈ES,an,an′∈Task, if
(22)uyan′,a−n>unan,a−n,then
(23)ϕan′,a−n>ϕan,a−n.Ordinal potential game has a property, i.e., the existence of a Nash equilibrium as well as finite improvement properties. In this way, any asynchronous optimal response updating process (no more than one participator maximizes its benefit by updating strategy) must be finite and will eventually result in Nash equilibrium [21]. In order to prove that the game in this paper is an ordinal potential game, the potential function of the paper is constructed as
(24)ϕA=∑i=1N∑j=1MRj×Ωj−Dj,ioff+ωΩj×cj,iIaj,i=1,in which IU is an indicator function. If U expression is correct, then IU=1; otherwise, IU=0.Theorem 8.
The resource allocation game model between edge servers in the paper is a finite ordinal potential game with potential function (24).Proof.
Assume that a servern∈ES changes its selection k to k′, and the allocation strategy will be updated from A to A′. This will cause an increase of its benefit indicator function value, i.e., uk′,n>uk,n. According to the definition of potential function, it can be discovered this will result in higher potential function value, i.e., ϕA′>ϕA. From the lemma, it can be obtained when selection update occurs, there must be k=0, i.e., not selecting the task uk,n=0. Thus, there are only two situations to consider: (1) ak′,n=0 and (2) ak′,n≠0.
Becausek=0, then uk,n=0, that is to say,
(25)Rk×Ωk−Dk,noff+ωΩk×ck,n=0.(1)
In caseak′,n=0, then uk′,n>uk,n=0, it can be obtained by Equation (11) that(26)Rk′×Ωk′−Dk′,noff+ωλk′×Ωk′×Nk′×ck′,n>0
Asλk′>0,Nk′>0, the above equation can be reduced to
(27)Rk′×Ωk′−Dk′,noff+ωΩk′×ck′,n>0.
According to Definition7, it is needed to compare the potential function under different strategies, and their size can be expressed by the difference of the two. The specific calculation process is as follows:
(28)ϕA′−ϕA=∑i=1N∑j=1MRj×Ωj−Dj,ioff+ωΩj×cj,iIaj,i′=1Ii≠n+∑j=1MRj×Ωj−Dj,noff+ωΩj×cj,nIaj,i′=1−∑i=1N∑j=1MRj×Ωj−Dj,ioff+ωΩj×cj,iIaj,i=1Ii≠n−∑j=1MRj×Ωj−Dj,noff+ωΩj×cj,nIaj,i=1=∑j=1MRj×Ωj−Dj,noff+ωΩj×cj,nIaj,i′=1−Rk×Ωk−Dk,noff+ωΩk×ck,n=Rk′×Ωk′−Dk′,noff+ωΩk′×ck′,n>0.(2)
In caseak′,n≠0, it can be obtained by Definition 3 that, if strategy update occurs at this time, there must be the following inequation:(29)Rk′×Ωk′−Dk′,noff+ωΩk′×ck′,n>Rk′×Ωk′−Dk′,n′off+ωΩk′×ck′,n′
Integrating with Definition7, the potential function under different strategies is compared. The specific calculation process is as follows:
(30)ϕA′−ϕA=∑i=1N∑j=1MRj×Ωj−Dj,ioff+ωΩj×cj,iIaj,i′=1Ii≠nIi≠n′+∑j=1MRj×Ωj−Dj,noff+ωΩj×cj,nIaj,n′=1+∑j=1MRj×Ωj−Dj,n′off+ωΩj×cj,n′Iaj,n′′=1−∑i=1N∑j=1MRj×Ωj−Dj,ioff+ωΩj×cj,iIaj,i=1Ii≠nIi≠n′−∑j=1MRj×Ωj−Dj,noff+ωΩj×cj,nIaj,n=1−∑j=1MRj×Ωj−Dj,n′off+ωΩj×cj,n′Iaj,n′=1=Rk′×Ωk′−Dk′,noff+ωΩk′×ck′,n−Rk′×Ωk′−Dk′,n′off+ωΩk′×ck′,n′>0.
Combing with the results of Equations (28) and (30) as well as Definition 4, it is concluded that the MEC multiuser and multiedge server resource allocation game proposed in the paper is a finite ordinal potential game. Therefore, the game has the characteristics of a finite ordinal potential game, including limited improvement properties.


## 4.1.3. Game Strategy Design

The above section verifies the MEC multiuser and multiedge server resource allocation game has Nash equilibrium, and this section introduces the strategy to solve Nash equilibrium in details. There are some classical algorithms for finding the existence of Nash equilibrium, such as optimum response [18] and reinforcement learning [22]. However, the problem of finding Nash equilibrium in the model of this paper is incomplete information; that is to say, all configuration information for each edge server is held only by itself. Thus, an edge server cannot make its own optimal response according to the optimal selection of other edge servers. So this paper chose to use game theory for problem solution. Through the above proof, this paper designed a game-based joint optimization strategy (GBJOS) to solve the competition problem of edge server, as shown in Strategy 9.Strategy 9.
Iteration-based optimal energy efficiency update algorithm.
Input Mobile device’s task information
Output Resource allocation strategy A
Initialization Initialize the resource allocation strategy of system, set task selection threshold as N_TO=M/2, set maximum iteration times maxIter=100
1)whileconverge≠True and iter<maxIterdo
2)iter⟵iter+1
3) administrative server transmitsTask, A, Nm, N_TO, λm to each edge server
receive parameter information
6)  based on Definitions3 and 4, maximize the value of Eq. (11), select the optimal strategy brn for them
7)  transmit the strategybrn to administrative server
8)ifbrn is not null, and currently do not hold brnthen
9)  request strategy change from administrative server
10)end if
11)end for
12)if administrative server does not receive any request then
13)converge⟵True
14)else
15)  randomly choose an edger serve and allow it to update strategy
16)  based on this round of received strategybrn, update A
17)  based on this round of strategy update of all edge servers
18)end if
19)end while
20)ReturnAGBJOS mainly includes two parts: strategy selection of edge server and collection of strategy update information from administrative server.(i)
Strategy selection of edge server: edge servers obtain the related parameters of Equation (11) from administrative server, for calculating the benefit of all tasks unan,a−n,n∈ES,an,a′n∈Task, choose the task with the largest benefit as this round of strategy selection. In case an edge server does not hold the task selected for this round, it can send a request to administrative server for strategy modification.(ii)
Collection of strategy update information from administrative server: in each round of iteration, the administrative server can receive the current strategy selection of all edge servers as well as the request of some edge servers for modification. If no request for modification is received, it is judged as convergence; otherwise, administrative server shall gather current strategies, then randomly choose an edge server having send request for modification and permit it to change current resource allocation strategy [23]. Meanwhile, the administrative server updates resource allocation strategy and transmits collected parameters to each edge server.


## 4.1.4. Convergence Analysis

In Theorem8, we have proved this game is a finite ordinal potential game, so this strategy will converge to Nash equilibrium within in limited number of iteration times. In practical strategy execution, when the administrative server does not receive any request for modification, it is judged as strategy convergence; at this time, the update of resource allocation strategy will be ended.Next, the time complexity of GBJOS will be analyzed. Within each iteration, every edge server performs task selection in parallel. Therein, some sorting operation and basic operations are involved, so the time complexity of this part isONlogN. It is assumed that this strategy will go through C times of iteration before reaching to termination, so the overall time complexity of GBJOS is OCNlogN. It is clear whether this strategy can converge within limited times relies on whether iteration time C has a upper bound or not.Theorem 10.
When for∀m∈1,2,⋯,M, ∀n∈1,2,⋯,N,Dm,noff≤Ωm, Rm>cm,n occurs, GBJOS will terminate after iterating for maxN∗Q∗Ωmax/ω,M∗N_TO times at most, i.e., C<maxN∗Q∗Ωmax/ω,M∗N_TO.Proof.
During iteration, it is assumed that edge servern updates current task selection k to k′, and updates allocation strategy A to A′. Based on Definition 4 and lemma, it is obtained that k=0; then there are two main scenarios to consider: (1) ak′,n=0 and (2) ak′,n≠0(1)
ak′,n=0: the theoretical maximal benefit is expressed as(31)Q=max∀m∈1,2,⋯,M,∀n∈1,2,⋯,NRm×Ωm−Dm,noff+ωΩm×cm,n
According to potential function (24), it can be obtained that
(32)0≤ϕA≤∑i=1N∑j=1MQIaj,i=1<NQ.
According to the nature of potential game, strategy change will lead to the increase of potential function value. Suppose the minimal granularity of potential game increase to beQmin, that is to say,
(33)ϕA′≥ϕA+Qmin.
According to Equation (28), it can be obtained that
(34)ϕA′−ϕA≥ωΩk′.
Define the maximal time delay as(35)Ωmax=max∀m∈1,2,⋯,MΩm.
There must be(36)Ωk′≤Ωmax.
That is to say,(37)ϕA′−ϕA≥ωΩmax>0,ak′,n≠0.If the strategy selection of edge servers contradicts, it can be known from Definitions3 and 4 that for a task, whether a server can successfully snatch it or not, the upper bound of conflict times is N_TO. So, in this case, the upper bound of strategy conflict times is M∗N_TO.Through the analysis of above two cases, it can be concluded that: iteration timesC<maxN∗Q∗Ωmax/ω,M∗N_TO.


## 4.2. Reverse Update of Parameters

The above-mentioned GBJOS strategy makes edge server to maximize its benefit; finally, all edge servers can reach an agreement. In this section, the penalty coefficientλ in Equation (10) was dynamically adjusted by setting loss function. The penalty coefficient is designed to give different significance scoring to the tasks of different size, and edge servers determine their own strategy selection by working out Equation (11). So, penalty coefficient λ plays an important role in guiding edge server to make strategy selection. If different tasks have great difference in λ, it would be unfair to some tasks, making λ to exert large impact on the value of Equation (11), while ignoring the influence of other parameters; but if different tasks have too small difference in λ, the gap between task priority is too small, then edge server would still make strategy selection according to the initial condition of a task, and the updates do not work as it is expected to be.In the TUSGT of this paper, penalty coefficient is updated dynamically through online learning framework. The paper sets a loss functionφ; each task will be updated to varied extent according to its own data characteristics. By virtue of such automatic dynamic adjustment, tasks are given different priorities, reaching the purpose of improving deadline hit rate. The loss function φm for task m is calculated as shown in
(38)φm=VIm−∑i=1MVIi×θi∑i=1Mθi,∑i=1Mθi≠0,in which θi refers to whether task i is completed on time or not (see details in Section 3.7). The penalty coefficient λ is updated by EWA algorithm [24], as shown in
(39)λmnew=λmold×e−ηφm,∑i=1Mθi≠0,λmold×12,∑i=1Mθi=0.When no task is completed on time, the penalty coefficient of all tasks is halved, to increase task attraction. It can be seen from Equation (39) that, in general condition, the priority of the task with large volume of data will be elevated, while the update extent relies on the task completion of current strategy. Therein, the update extent of penalty coefficient also depends on the value of learning rate η, which should be set artificially according to actual initial task information. The value of η also decides the update times of TUSGT; the smaller the update extent is, the more times it will be updated. While updating too much will result in unsatisfactory result, so it needs to be weighed against actual data. The penalty coefficient needs to be adjusted according to the actual task size and the computing power of the edge server. It is only necessary to use the parameters expected in the scene as input and make multiple adjustments. The variation of this coefficient is also affected by the size of the task, but in general, the edge server can be guided to make a choice that is more conducive to the overall task completion rate of the MEC system.


## 5. Experiment and Result Analysis

In the MEC multiuser and multiedge server resource allocation scenarios set in the simulation test of this paper, all mobile devices and edge servers are evenly distributed in a region of1000m×1000m. The performance of different strategies is evaluated by deadline hit rate and the average benefit of edge servers. Finally, the convergence of TUSGT strategy and the growth of operation time are analyzed.


### 5.1. Experimental Parameter Setting

In the simulation test of the paper, there are 30 edge servers, and the performance of TUSGT is evaluated by setting different number of mobile devices. Both task input volumeVIm and computing amount Lm conform to uniform distribution within the range of values, and the output data volume VOm of mobile device tasks is set to be 0.2 times of VIm [25]. This initial reward value is proportional to the amount of task data. The reward value will not change during the experiment. If the mobile device is not allocated computing resources, it will miss the opportunity to be calculated in this round. When the edge server completes the calculation of the current task, it can update its reward value to participate in a new round of allocation. This paper refers to the experimental parameter data in literature [19] to set the CPU processing capacity fm and fn of mobile device and edge server, which also conform to even distribution within the range of values, aimed at simulating a real environment with various devices of different computing power. The transmission rate of mobile device conforms to even distribution within the range of values, and communication-related parameters such as antenna gain are fixed value [19]. Regarding task delay requirement Ωm, the time delay requirement of task set in this paper is consistent with even distribution within time interval Z±0.3Z, in which, Z is the time delay granularity [25]. The smaller the time delay granularity is, the more strict the time delay requirement of task will be. The learning rate is affected by the amount of task data. In the parameter environment of this paper, setting the learning rate to 0.1 has a better effect. In practical applications, multiple adjustments need to be made according to the estimated amount of task data, and a value with better effect is selected. This value is not adjusted during operation. The specific parameter settings are shown in Table 1.Table 1
Experimental parameters.
ParametersValueNumber of edge serversN30Number of mobile devicesM[20, 80]Input volume of taskVIm[20, 100] MBCalculation amount of taskLm[500, 1500] Mcycles/MBDelay requirement granularity of taskZ[100, 300] sCPU processing capability of mobile devicefm[1, 5] Mcycles/sCPU processing capability of edge serverfn[200, 400] Mcycles/sBandwidthB2 MHzNoise powerσ210-10  WAntenna gainG4.11Carrier frequencyFc915 MHzPath loss factorPL3Transmission power of mobile devicepm[0.1, 0.8] WLearning rateη0.1


### 5.2. Evaluation Metrics

TUSGT considers edge server benefit and deadline hit rate at the same time. Edge server benefit embodies its initiative to perform task; the higher the benefit is, the more the edge server is willing to perform task. Deadline hit rate embodies the performance of allocation strategy, because the MEC system is aimed at completing the task offloaded by mobile deice; the higher the deadline hit rate is, the better the performance of allocation strategy is. So this paper evaluates the performance of different strategies from two aspects: deadline hit rate of MEC system and average benefit of edge server. First, these two indexes are defined as follows:(1)
Deadline hit rate (DHR):(40)DHR=M−∑i=1MθiM,in which θi represents whether the task i is completed on time or not and M represents total number of tasks.
(2)
Average benefit (AB):The benefit of edge servern is
(41)∑m∈Snbenefitm,n,in which, Sn represents the final strategy set of edge server n. The average benefit of edge server is obtained as
(42)AB=∑i=1N∑m∈Sibenefitm,iN,in which N represents the number of edge servers.


### 5.3. Comparison of Strategies

The paper selected five allocation strategies to compare with the TUSGT strategy proposed. The five comparison strategies are as follows:(1)
BGTA strategy: a game theory-based task allocation scheme, allowing the player to selfishly compete for task so as to maximize its own benefit [26].(2)
MILP strategy: adopts mixed integer linear programming (MILP) to formulate joint task offloading and resource allocation strategy [27].(3)
Greedy Strategy (GS): a greedy resource allocation strategy, making edge server to always select the task with highest benefit(4)
Random Strategy (RS): a random allocation strategy, making edge server to randomly select task for computing(5)
Ideal strategy: an ideal situation, in which the administrative server performs a global and integrated allocation based on the information of all edge servers and mobile device tasks and takes maximizing the deadline hit rate of system as objective. In this case, all edge servers and mobile devices completely listen to the arrangement of administrative server, without the ability to chooseIn the BGTA strategy, the author considers the revenue problem of edge servers, constructs a revenue function, allows edge servers to select the task with the highest benefit at present, and then uses game theory to build an allocation algorithm to solve the conflict problem of task selection and finally solves the allocation strategy. In the MILP strategy, the author takes the monetary cost and task completion delay of the edge server as the optimization goal, constructs it as a MILP problem, and then uses the branch and bound algorithm (The Branch and Bound Algorithm) to solve the approximate optimal solution of the target problem; namely, the optimization problem is regarded as a search tree to search, so as to obtain the final resource allocation strategy.GS adopts the classical greedy algorithm to construct resource allocation strategy, which is a classical solution method. RS reflects the performance of resource allocation problem under unstable strategies, normally the lower bound of allocation strategy performance. Ideal strategy assumes all devices follows the management and do not pursue for any self-interest, and the strategy maker owns the information of all devices and tasks in current environment. But this is not practical, so the performance of ideal strategy is only taken as an upper bound in the comparison of deadline hit rate, to measure the difference between various strategies and ideal upper bound.


### 5.4. Experimental Results

#### 5.4.1. Deadline Hit Rate

Figure2 provides the influence of task number on DHR for different resource allocation strategies. In this experiment, due to the number of edge server being fixed as 30, in the process of increasing task number, the overall DHR must show a declining trend, and the fluctuation of effect is caused by the heuristic operation in strategy and the randomness of task generation. It can be seen from the chart that, for the TUSGT proposed in the paper, its deadline hit rate is very close to that of ideal strategy under different number of tasks. But in the case of 60 tasks, only TUSGT and ideal achieve the highest DHR of 0.5. Among them, the effect of RS is not stable, but it can be observed from an overall trend that its effect is far less than TUSGT. The poorest effect of GS contributes to the short sight of edge server. Under these five different number of tasks, as DHR performance is concerned, TUSGT is improved by 22% on average compared to BGTA and by 27% on average compared to MILP.Figure 2
Impact of the number of tasks on DHR.Figure3 shows the impact of changing task delay requirement on DHR for different strategies. In the experiment as shown in Figure 3, the number of both edge server and task is set as 30, so DHR is within the range of [0,1]. The increase of delay granularity means the task delay requirement gradually becomes loose, and overall DHR is also rising. Similar to the experiment in Figure 2, RS performance is not stable and its DHR is lower than TUSGT. It can be observed from Figure 3 that, in difference scenarios, TUSGT is slightly lower than Ideal, and the remaining strategies are all lower than TUSGT, which is due to the reverse update penalty coefficient in TUSGT. Under these five different task delay requirements, as DHR performance is concerned, TUSGT is improved by 20% on average compared to BGTA and by 30% on average compared to MILP.Figure 3
Impact of delay granularity on DHR.


#### 5.4.2. Average Benefit of Edge Server

Figure4 shows the impact of changing task number on edge server AB for different strategies. In this experiment, there are 30 edge servers, and the number of task is changed to simulate different scenarios. It can be seen from Figure 4 that, in scenarios with different task number, all average benefits of TUSGT are the highest, due to that the game theory-based strategy allows edge servers to compete for task. It is also observed that ideal strategy lags far behind on AB index, because ideal only cares about overall DHR of the system, without considering the competition relationship and benefit of edge servers. Both RS and GS have a poor effect. RS effect fluctuates greatly due to its instability, and GS sacrifices much DHR, resulting in low AB. Under these five different number of task, as edge server AB is concerned, TUSGT is improved by 22% on average compared to BGTA and by 65% on average compared to MILP.Figure 4
Impact of the number of tasks on AB.


#### 5.4.3. Convergence and Overhead Analysis

Figure5 displays the convergence when task number is 20, 40, 60, and 80, and its vertical axis is the percentage of request instruction number which represents the convergence of TUSGT. From the introduction in section 4, it is known that TUSGT convergence mainly lies on the convergence of GBJOS strategy. When there is edge server requesting for strategy modification, it represents convergence. It is observed in the figure that, as the iteration times increase, all the numbers of edge servers applying for modifying resource allocation strategy are decreasing under four scenarios, so TUSGT reaches to convergence state after less iteration times. With the increase of task number, TUSGT convergence tends to be smooth, because the more the task number is, the smaller the competition between edge servers will be, and the easier it is to converge.Figure 5
TUSGT convergence curves.Figure6 shows the change of TUSGT execution time as the task number in MEC system increases. The main time overhead of TUSGT is from GBJOS, because the time complexity of reversely updating parameters is very small [25], while GBJOS requires edge server to iterate many times and compete for selection task. Therefore, GBJOS with fast convergence makes TUSGT to have very small time overhead, as shown in Figure 6, the TUSGT time overhead is merely 350 ms in the case of 80 tasks, which would not produce too great influence on task execution. It is also observed from Figure 6 that, as task number increases, the overall TUSGT time overhead tends to increase smaller and smaller. This means even if more tasks are added, TUSGT time overhead would not be elevated too much suddenly.Figure 6
Impact of task number on time overhead.The above experimental results indicate that the TUSGT proposed in the paper can effectively promote edge server benefit and MEC system DHR. TUSGT has a good convergence, and execution time overhead would not affect the real-time requirement of offloading task in MEC system.


## 5.1. Experimental Parameter Setting

In the simulation test of the paper, there are 30 edge servers, and the performance of TUSGT is evaluated by setting different number of mobile devices. Both task input volumeVIm and computing amount Lm conform to uniform distribution within the range of values, and the output data volume VOm of mobile device tasks is set to be 0.2 times of VIm [25]. This initial reward value is proportional to the amount of task data. The reward value will not change during the experiment. If the mobile device is not allocated computing resources, it will miss the opportunity to be calculated in this round. When the edge server completes the calculation of the current task, it can update its reward value to participate in a new round of allocation. This paper refers to the experimental parameter data in literature [19] to set the CPU processing capacity fm and fn of mobile device and edge server, which also conform to even distribution within the range of values, aimed at simulating a real environment with various devices of different computing power. The transmission rate of mobile device conforms to even distribution within the range of values, and communication-related parameters such as antenna gain are fixed value [19]. Regarding task delay requirement Ωm, the time delay requirement of task set in this paper is consistent with even distribution within time interval Z±0.3Z, in which, Z is the time delay granularity [25]. The smaller the time delay granularity is, the more strict the time delay requirement of task will be. The learning rate is affected by the amount of task data. In the parameter environment of this paper, setting the learning rate to 0.1 has a better effect. In practical applications, multiple adjustments need to be made according to the estimated amount of task data, and a value with better effect is selected. This value is not adjusted during operation. The specific parameter settings are shown in Table 1.Table 1
Experimental parameters.
ParametersValueNumber of edge serversN30Number of mobile devicesM[20, 80]Input volume of taskVIm[20, 100] MBCalculation amount of taskLm[500, 1500] Mcycles/MBDelay requirement granularity of taskZ[100, 300] sCPU processing capability of mobile devicefm[1, 5] Mcycles/sCPU processing capability of edge serverfn[200, 400] Mcycles/sBandwidthB2 MHzNoise powerσ210-10  WAntenna gainG4.11Carrier frequencyFc915 MHzPath loss factorPL3Transmission power of mobile devicepm[0.1, 0.8] WLearning rateη0.1


## 5.2. Evaluation Metrics

TUSGT considers edge server benefit and deadline hit rate at the same time. Edge server benefit embodies its initiative to perform task; the higher the benefit is, the more the edge server is willing to perform task. Deadline hit rate embodies the performance of allocation strategy, because the MEC system is aimed at completing the task offloaded by mobile deice; the higher the deadline hit rate is, the better the performance of allocation strategy is. So this paper evaluates the performance of different strategies from two aspects: deadline hit rate of MEC system and average benefit of edge server. First, these two indexes are defined as follows:(1)
Deadline hit rate (DHR):(40)DHR=M−∑i=1MθiM,in which θi represents whether the task i is completed on time or not and M represents total number of tasks.
(2)
Average benefit (AB):The benefit of edge servern is
(41)∑m∈Snbenefitm,n,in which, Sn represents the final strategy set of edge server n. The average benefit of edge server is obtained as
(42)AB=∑i=1N∑m∈Sibenefitm,iN,in which N represents the number of edge servers.


## 5.3. Comparison of Strategies

The paper selected five allocation strategies to compare with the TUSGT strategy proposed. The five comparison strategies are as follows:(1)
BGTA strategy: a game theory-based task allocation scheme, allowing the player to selfishly compete for task so as to maximize its own benefit [26].(2)
MILP strategy: adopts mixed integer linear programming (MILP) to formulate joint task offloading and resource allocation strategy [27].(3)
Greedy Strategy (GS): a greedy resource allocation strategy, making edge server to always select the task with highest benefit(4)
Random Strategy (RS): a random allocation strategy, making edge server to randomly select task for computing(5)
Ideal strategy: an ideal situation, in which the administrative server performs a global and integrated allocation based on the information of all edge servers and mobile device tasks and takes maximizing the deadline hit rate of system as objective. In this case, all edge servers and mobile devices completely listen to the arrangement of administrative server, without the ability to chooseIn the BGTA strategy, the author considers the revenue problem of edge servers, constructs a revenue function, allows edge servers to select the task with the highest benefit at present, and then uses game theory to build an allocation algorithm to solve the conflict problem of task selection and finally solves the allocation strategy. In the MILP strategy, the author takes the monetary cost and task completion delay of the edge server as the optimization goal, constructs it as a MILP problem, and then uses the branch and bound algorithm (The Branch and Bound Algorithm) to solve the approximate optimal solution of the target problem; namely, the optimization problem is regarded as a search tree to search, so as to obtain the final resource allocation strategy.GS adopts the classical greedy algorithm to construct resource allocation strategy, which is a classical solution method. RS reflects the performance of resource allocation problem under unstable strategies, normally the lower bound of allocation strategy performance. Ideal strategy assumes all devices follows the management and do not pursue for any self-interest, and the strategy maker owns the information of all devices and tasks in current environment. But this is not practical, so the performance of ideal strategy is only taken as an upper bound in the comparison of deadline hit rate, to measure the difference between various strategies and ideal upper bound.


## 5.4. Experimental Results

### 5.4.1. Deadline Hit Rate

Figure2 provides the influence of task number on DHR for different resource allocation strategies. In this experiment, due to the number of edge server being fixed as 30, in the process of increasing task number, the overall DHR must show a declining trend, and the fluctuation of effect is caused by the heuristic operation in strategy and the randomness of task generation. It can be seen from the chart that, for the TUSGT proposed in the paper, its deadline hit rate is very close to that of ideal strategy under different number of tasks. But in the case of 60 tasks, only TUSGT and ideal achieve the highest DHR of 0.5. Among them, the effect of RS is not stable, but it can be observed from an overall trend that its effect is far less than TUSGT. The poorest effect of GS contributes to the short sight of edge server. Under these five different number of tasks, as DHR performance is concerned, TUSGT is improved by 22% on average compared to BGTA and by 27% on average compared to MILP.Figure 2
Impact of the number of tasks on DHR.Figure3 shows the impact of changing task delay requirement on DHR for different strategies. In the experiment as shown in Figure 3, the number of both edge server and task is set as 30, so DHR is within the range of [0,1]. The increase of delay granularity means the task delay requirement gradually becomes loose, and overall DHR is also rising. Similar to the experiment in Figure 2, RS performance is not stable and its DHR is lower than TUSGT. It can be observed from Figure 3 that, in difference scenarios, TUSGT is slightly lower than Ideal, and the remaining strategies are all lower than TUSGT, which is due to the reverse update penalty coefficient in TUSGT. Under these five different task delay requirements, as DHR performance is concerned, TUSGT is improved by 20% on average compared to BGTA and by 30% on average compared to MILP.Figure 3
Impact of delay granularity on DHR.


### 5.4.2. Average Benefit of Edge Server

Figure4 shows the impact of changing task number on edge server AB for different strategies. In this experiment, there are 30 edge servers, and the number of task is changed to simulate different scenarios. It can be seen from Figure 4 that, in scenarios with different task number, all average benefits of TUSGT are the highest, due to that the game theory-based strategy allows edge servers to compete for task. It is also observed that ideal strategy lags far behind on AB index, because ideal only cares about overall DHR of the system, without considering the competition relationship and benefit of edge servers. Both RS and GS have a poor effect. RS effect fluctuates greatly due to its instability, and GS sacrifices much DHR, resulting in low AB. Under these five different number of task, as edge server AB is concerned, TUSGT is improved by 22% on average compared to BGTA and by 65% on average compared to MILP.Figure 4
Impact of the number of tasks on AB.


### 5.4.3. Convergence and Overhead Analysis

Figure5 displays the convergence when task number is 20, 40, 60, and 80, and its vertical axis is the percentage of request instruction number which represents the convergence of TUSGT. From the introduction in section 4, it is known that TUSGT convergence mainly lies on the convergence of GBJOS strategy. When there is edge server requesting for strategy modification, it represents convergence. It is observed in the figure that, as the iteration times increase, all the numbers of edge servers applying for modifying resource allocation strategy are decreasing under four scenarios, so TUSGT reaches to convergence state after less iteration times. With the increase of task number, TUSGT convergence tends to be smooth, because the more the task number is, the smaller the competition between edge servers will be, and the easier it is to converge.Figure 5
TUSGT convergence curves.Figure6 shows the change of TUSGT execution time as the task number in MEC system increases. The main time overhead of TUSGT is from GBJOS, because the time complexity of reversely updating parameters is very small [25], while GBJOS requires edge server to iterate many times and compete for selection task. Therefore, GBJOS with fast convergence makes TUSGT to have very small time overhead, as shown in Figure 6, the TUSGT time overhead is merely 350 ms in the case of 80 tasks, which would not produce too great influence on task execution. It is also observed from Figure 6 that, as task number increases, the overall TUSGT time overhead tends to increase smaller and smaller. This means even if more tasks are added, TUSGT time overhead would not be elevated too much suddenly.Figure 6
Impact of task number on time overhead.The above experimental results indicate that the TUSGT proposed in the paper can effectively promote edge server benefit and MEC system DHR. TUSGT has a good convergence, and execution time overhead would not affect the real-time requirement of offloading task in MEC system.


## 5.4.1. Deadline Hit Rate

Figure2 provides the influence of task number on DHR for different resource allocation strategies. In this experiment, due to the number of edge server being fixed as 30, in the process of increasing task number, the overall DHR must show a declining trend, and the fluctuation of effect is caused by the heuristic operation in strategy and the randomness of task generation. It can be seen from the chart that, for the TUSGT proposed in the paper, its deadline hit rate is very close to that of ideal strategy under different number of tasks. But in the case of 60 tasks, only TUSGT and ideal achieve the highest DHR of 0.5. Among them, the effect of RS is not stable, but it can be observed from an overall trend that its effect is far less than TUSGT. The poorest effect of GS contributes to the short sight of edge server. Under these five different number of tasks, as DHR performance is concerned, TUSGT is improved by 22% on average compared to BGTA and by 27% on average compared to MILP.Figure 2
Impact of the number of tasks on DHR.Figure3 shows the impact of changing task delay requirement on DHR for different strategies. In the experiment as shown in Figure 3, the number of both edge server and task is set as 30, so DHR is within the range of [0,1]. The increase of delay granularity means the task delay requirement gradually becomes loose, and overall DHR is also rising. Similar to the experiment in Figure 2, RS performance is not stable and its DHR is lower than TUSGT. It can be observed from Figure 3 that, in difference scenarios, TUSGT is slightly lower than Ideal, and the remaining strategies are all lower than TUSGT, which is due to the reverse update penalty coefficient in TUSGT. Under these five different task delay requirements, as DHR performance is concerned, TUSGT is improved by 20% on average compared to BGTA and by 30% on average compared to MILP.Figure 3
Impact of delay granularity on DHR.


## 5.4.2. Average Benefit of Edge Server

Figure4 shows the impact of changing task number on edge server AB for different strategies. In this experiment, there are 30 edge servers, and the number of task is changed to simulate different scenarios. It can be seen from Figure 4 that, in scenarios with different task number, all average benefits of TUSGT are the highest, due to that the game theory-based strategy allows edge servers to compete for task. It is also observed that ideal strategy lags far behind on AB index, because ideal only cares about overall DHR of the system, without considering the competition relationship and benefit of edge servers. Both RS and GS have a poor effect. RS effect fluctuates greatly due to its instability, and GS sacrifices much DHR, resulting in low AB. Under these five different number of task, as edge server AB is concerned, TUSGT is improved by 22% on average compared to BGTA and by 65% on average compared to MILP.Figure 4
Impact of the number of tasks on AB.


## 5.4.3. Convergence and Overhead Analysis

Figure5 displays the convergence when task number is 20, 40, 60, and 80, and its vertical axis is the percentage of request instruction number which represents the convergence of TUSGT. From the introduction in section 4, it is known that TUSGT convergence mainly lies on the convergence of GBJOS strategy. When there is edge server requesting for strategy modification, it represents convergence. It is observed in the figure that, as the iteration times increase, all the numbers of edge servers applying for modifying resource allocation strategy are decreasing under four scenarios, so TUSGT reaches to convergence state after less iteration times. With the increase of task number, TUSGT convergence tends to be smooth, because the more the task number is, the smaller the competition between edge servers will be, and the easier it is to converge.Figure 5
TUSGT convergence curves.Figure6 shows the change of TUSGT execution time as the task number in MEC system increases. The main time overhead of TUSGT is from GBJOS, because the time complexity of reversely updating parameters is very small [25], while GBJOS requires edge server to iterate many times and compete for selection task. Therefore, GBJOS with fast convergence makes TUSGT to have very small time overhead, as shown in Figure 6, the TUSGT time overhead is merely 350 ms in the case of 80 tasks, which would not produce too great influence on task execution. It is also observed from Figure 6 that, as task number increases, the overall TUSGT time overhead tends to increase smaller and smaller. This means even if more tasks are added, TUSGT time overhead would not be elevated too much suddenly.Figure 6
Impact of task number on time overhead.The above experimental results indicate that the TUSGT proposed in the paper can effectively promote edge server benefit and MEC system DHR. TUSGT has a good convergence, and execution time overhead would not affect the real-time requirement of offloading task in MEC system.


## 6. Conclusions

This paper built a model for multiuser and multiedge server resource allocation problem in MEC system at first, considered the benefit of edge server, and proposed a two-way update strategy based on game theory (TUSGT) to solve this problem. It is proved that the task competition relationship between edge servers is a finite ordinal potential game and the Nash equilibrium exists; then parameters are updated reversely to adjust task weight, so as to improve overall deadline hit rate. Finally, through simulation test, we verified the convergence nature and time performance of TUSGT. Compared to other datum strategies, TUSGT significantly promotes edge server benefit and overall deadline hit rate. However, TUSGT only solves problem in static scenario, but does not consider decomposable task or that one edge server can receive multiple tasks. The further study will consider dynamic offloading strategy and user movability factors and extend TUSGT solution scenario, to adapt to more general situations.



---

*Source: 1117597-2022-07-13.xml*