1. Introduction
The increasing number of mobile devices brings about a large increase in data traffic, which poses a great challenge to the performance of traditional networks [1]. MEC technology can well alleviate the computational pressure on the center server by deploying the server at the edge of the network. As it is closer to the mobile devices, it can better fulfill the demand of low latency. Most of the existing research work relies on fixing MEC servers in terrestrial base stations (BS) [2], [3], however, terrestrial BSs are expensive to deploy, fixed in location, and have limited coverage, which prevents them from providing reliable communication services in remote areas as well as emergency scenarios such as large-scale concerts. With low deployment cost, easy maneuvering, high mobility and flexibility, UAV can be rapidly deployed as a service node in the network to guarantee communication services in emergency scenarios [4]. UAV-assisted MEC can reduce the connection latency of the edge network, and improve the flexibility and robustness of the edge network [5]. UAV can be used as both a relay node in the edge network to help IoT devices that cannot access the edge server directly to forward computations. The UAV can either act as a relay node to help IoT devices forward computational tasks [6] or carry MEC servers to provide computational services for mobile MU terminals with limited computational capabilities [7].
The use of game theory to incentivize parties to participate in computation offloading has been widely studied. Wang M et al. [8] considered a scenario in which a terrestrial BS is damaged and unable to provide computation services, and by overlaying UAVs into the network of the damaged BSs, they constructed a Stackelberg game model to solve the problem of minimising energy consumption. Zhou H et al. [9] modeled the interaction between a mobile MU and an edge interaction between mobile MUs and service providers modeled as a Stackelberg game model and proposed a gradient-based iterative search algorithm to obtain an approximate optimal solution with the objective of maximizing their utility. Although the combined air-ground edge computing approach has received a lot of attention, the limitation of computational resources and energy supply for UAVs is a challenge for existing work [10], [11]. In addition, the research on multi-UAV resource allocation in complex environments in existing work needs to be further deepened and improved.
We consider a layered system for UAV-assisted edge computing in multi-MU, multi-UAV, and multi-BS scenarios and model it as a multi-leader, multi-follower Stackelberg bilayer game model, where the UAVs act as leader and follower, respectively, in the bilayer game. An alternating iteration algorithm is then proposed to solve the problem of minimising the total cost of the system. The main contributions of this paper are as follows: (1) We study the joint optimisation problem of computational offloading and resource allocation for UAV-assisted MEC in a complex scenario with multiple MUs, multiple UAVs, and BSs hosting MEC servers. (2) We develop a bilayer model of the multi-leader, multi-follower Stackelberg game with the optimisation objective of minimising the total system cost of task execution. We utilise the Lagrange duality method to transform the complex, constrained problem. (3) We prove that the established game model has a unique Nash equilibrium point. In order to obtain an approximate optimal solution to the proposed problem, a TASR algorithm is proposed. (4) Simulation results show that the TASR algorithm can make the bilayer game converge to a Nash equilibrium with some robustness. In addition, compared with the benchmark method, TASR has certain superiority under different numbers of MUs.
2. System Model
We consider a UAV-assisted MEC task offloading system. As shown in Fig. 1, the system consists of MUs and BSs located on the ground and UAVs located in the air. The UAV and BS are equipped with MEC servers from different service providers with independent internal communication and computation modules. Considering the situation that the user and the BS cannot communicate effectively with each other due to factors such as obstacle blockage, the UAV can be used as a relay node and computation server for forwarding tasks. When the MU has a demand for task computation, a partial offloading mode is used to offload a part of the task to the UAV and the other part is computed locally by the MU. The UAV subdivides the received task into two parts: one part is offloaded to the BS for computation and paid to the BS for computation of rewards; the other part is computed locally by the UAV and receives rewards paid by the MU.
 |
Fig. 1 System model |
2.1 Computational Model
The UAV-assisted MEC system contains B BS (\(B=\{1,2,\ldots ,B\}\)), K UAVs (\(K=\{1,2,\ldots ,K\}\)), and N MUs (\(N=\{1,2,\ldots ,N\}\)). Denote the task size of the \(M{{U}_{i}}\) by \({{D}_{i}}\) (\(i\in \{1,2,\ldots ,N\}\)), and \(T_{i}^{\max }\) denotes the maximum tolerance time of the task, assuming that there is one and only one task demanded by an MU during the time of \(T_{i}^{\max }\). C denotes the number of CPU cycles required by the device to compute the 1-bit data.
The latency and energy consumption of a task computed locally are expressed as
| \[\begin{align} & t_{i}^{MU}=\frac{(1-{{\alpha }_{i}})C{{D}_{i}}}{f_{i}^{MU}} \tag{1} \\ & e_{i}^{MU}={{\gamma }^{MU}}(1-{{\alpha }_{i}})C{{D}_{i}}{{(f_{i}^{MU})}^{2}} \tag{2} \end{align}\] |
Where \(f_{i}^{MU}\) denotes the local computational capacity, \({{\alpha }_{i}}\) denotes the ratio of tasks offloading processing, and \({{\gamma }^{MU}}\) denotes the hardware-related coefficient. \({{\beta }_{i,j}}\) denotes the percentage of received tasks that the UAV offloads to the BS. The latency and energy consumption required by the UAV to compute the task are denoted by
| \[\begin{align} & t_{i,j}^{UAV}=\frac{{{\alpha }_{i}}(1-{{\beta }_{i,j}})C{{D}_{i}}}{f_{i,j}^{UAV}} \tag{3} \\ & e_{i,j}^{UAV}={{\gamma }^{UAV}}{{\alpha }_{i}}(1-{{\beta }_{i,j}})C{{D}_{i}}{{(f_{i,j}^{UAV})}^{2}} \tag{4} \end{align}\] |
Where \(f_{i,j}^{UAV}\) denotes the computational resources allocated to the task by UAV. Let the computational resource assigned to the task by BS be \(f_{i,j,b}^{BS}\) (\(b\in \{1,2,\ldots ,B\}\)), then the latency and energy consumption of the task computed by the BS are
| \[\begin{align} & t_{i,j,b}^{BS}=\frac{{{\alpha }_{i}}{{\beta }_{i,j}}C{{D}_{i}}}{f_{i,j,b}^{BS}} \tag{5} \\ & e_{i,j,b}^{BS}={{\gamma }^{BS}}{{\alpha }_{i}}{{\beta }_{i,j}}C{{D}_{i}}{{(f_{i,j,b}^{BS})}^{2}} \tag{6} \end{align}\] |
2.2 Transmission Model
There may be obstacle occlusion between the UAV and the MU or BS, resulting in additional path loss. According to the 3rd Generation Partnership Project (3GPP) technical specification [12], the probability that the UAV communicates with the user with a line-of-sight (LoS) link is
| \[\begin{align} P_{i,j}^{LOS}=\left\{ \begin{matrix} 1, & d_{i,j}^{2D}\le {{d}_{1}} \\ \frac{{{d}_{1}}}{d_{i,j}^{2D}}+\exp \left( \frac{-d_{i,j}^{2D}}{{{p}_{1}}} \right)\left( 1-\frac{{{d}_{1}}}{d_{i,j}^{2D}} \right), & d_{i,j}^{2D}>{{d}_{1}} \\ \end{matrix} \right. \tag{7} \end{align}\] |
Where \(d_{i,j}^{2D}\) denotes the two-dimensional distance between the UAV and the user or the base station,\({{p}_{1}}=233.98\,{{\log }_{10}}(h_{j}^{uav})-0.95\) and \({{d}_{1}}=\max ( 294.05\,{{\log }_{10}} (h_{j}^{uav}) -432.94,18 )\) are the modelling parameters of the 3GPP specifications. The \(h_{j}^{uav}\) denotes the height of the UAV. Therefore, the transmission speed of the offloading task from the MU to the UAV can be obtained as
| \[\begin{align} R_{i,j}^{M-U}=B_{i,j}^{M-U}{{\log }_{2}}(1+\frac{p_{i,j}^{M-U}g_{i,j}^{M-U}}{{{N}_{0}}^{2}+(1-P_{i,j}^{LoS}){{N}_{NL}}}) \tag{8} \end{align}\] |
Where \(B_{i,j}^{M-U}\) denotes the channel bandwidth between the MU and the UAV, \(g_{i,j}^{M-U}={{(d_{i,j}^{M-U})}^{-\eta }}\) denotes the channel gain, and \(d_{i,j}^{M-U}\) is the 3D distance between the MU and the UAV. \(\eta\) is the path loss exponent, \({{N}_{NL}}\) denotes the additional loss due to the non-line-of-sight (NLoS) link, and \({{N}_{0}}^{2}\) denotes the noise power. Similarly, the transmission rate of the UAV to the BS offloading task is denoted as
| \[\begin{align} R_{j,b}^{U-B}=B_{j,b}^{U-B}{{\log }_{2}}(1+\frac{p_{j,b}^{U-B}g_{j,b}^{U-B}}{{{N}_{0}}^{2}+(1-P_{j,b}^{LoS}){{N}_{NL}}}) \tag{9} \end{align}\] |
The latency and energy consumption incurred during task transmission can be calculated
| \[\begin{align} & t_{i,j}^{M-U}=\frac{{{\alpha }_{i}}{{D}_{i}}}{R_{i,j}^{M-U}} \tag{10} \\ & e_{i,j}^{M-U}=p_{i,j}^{M-U}t_{i,j}^{M-U} \tag{11} \\ & t_{i,j,b}^{U-B}=\frac{{{\alpha }_{i}}{{\beta }_{i,j}}{{D}_{i}}}{R_{j,b}^{U-B}} \tag{12} \\ & e_{i,j,b}^{U-B}=p_{j,b}^{U-B}t_{i,j,b}^{U-B} \tag{13} \end{align}\] |
In general, the amount of data in the result download phase is much smaller than the amount of data unloaded by the task, so the latency and energy consumption incurred in the result download phase are ignored. The specific formulas for the task offloading time \(t_{i}^{off}\) and the total task completion time \(t_{i}^{all}\) are as follows:
| \[\begin{align} & t_{i}^{off}=t_{i,j}^{M-U}+\max \left\{ t_{i,j}^{UAV},t_{i,j,b}^{U-B}+t_{i,j,b}^{BS} \right\} \tag{14} \\ & t_{i}^{all}=\max \left\{ t_{i}^{MU},t_{i}^{off} \right\} \tag{15} \end{align}\] |
3. Stackelberg Game Model
In the three-party game, the revenue of UAV is not only limited by the offloading decision of MU but also by the resource pricing of BS. In order to effectively utilize the computational resources of the UAV, the overall game problem is decoupled into the MU-UAV game problem and the UAV-BS game problem.
3.1 MU-UAV Game Model
In the MU-UAV game model, the UAV serves as the leader and provides resource allocation and pricing strategies to the MU, which functions as the follower and offers offloading strategies to the UAV. The MU is focused on minimising the latency and integrated cost of task execution, while the UAV aims to maximise revenue with its limited computing resources. The cost of MU is expressed as follows:
| \[ \begin{align} & P1:\min U_{mu}^{M-U}={{M}_{i}}+{{\mu }_{1}}t_{i}^{all}+{{\mu}_{2}}(e_{i}^{MU}+e_{i,j}^{M-U}) \tag{16} \\ & s.t.~0\le t_{i}^{all}\le T_{i}^{\max } \tag{16a} \\ & 0\le {{\alpha }_{i}}\le 1 \tag{16b} \end{align}\] |
Where \({{\mu }_{1}}\) and \({{\mu }_{2}}\) are weight parameters to eliminate the difference in the values of latency cost, energy consumption costs, and monetary cost. \({{M}_{i}}\) denotes the monetary cost of the MU. Constraint (16a) indicates that the time to complete the task should satisfy the maximum time latency requirement of the task. Constraint (16b) denotes that the task offloading ratio should be between 0 and 1. The utility of UAV is expressed as follows:
| \[ \begin{align} & P2:\max U_{uav}^{M-U}=\sum\limits_{i=1}^{N}{({{m}_{j}}f_{i,j}^{UAV}-{{\mu }_{2}}e_{i,j}^{UAV})} \tag{17} \\ & s.t.~{{m}_{j}}f_{i,j}^{UAV}={{M}_{i}} \tag{17a} \\ &\text{0}\le f_{i,j}^{UAV}\le F_{\max }^{UAV} \tag{17b} \\ &{{m}_{j}}>0 \tag{17c} \end{align}\] |
Where \({{m}_{j}}\) denotes the uniform unit price established by \(\text{UA}{{\text{V}}_{\text{j}}}\) (\(j\in K\)) for the computational resource. Constraint (17a) represents the monetary cost of the MU in relation to the computational resources and unit prices. Constraint (17b) indicates that the computational resources allocated by the UAV for a task should be less than the maximum computational resources of the UAV. Constraint (17c) indicates that resource pricing should be positive.
3.2 UAV-BS Game Model
In the UAV-BS game model, BS as a leader provides resource allocation strategy and resource pricing strategy to UAV, and UAV as a follower provides offloading strategy to BS. The cost of a UAV is represented as follows:
| \[ \begin{align} & P3:\min U_{uav}^{U-B}=\sum\limits_{i=1}^{N}{({{q}_{b}}f_{i,j,b}^{BS}+{{\mu }_{2}}e_{i,j,b}^{U-B})} \tag{18} \\ & s.t.0\le {{\beta }_{i,j}}\le 1 \tag{18a} \end{align}\] |
Where \({{q}_{b}}\) denotes the uniform unit price established by \(B{{S}_{b}}\) (\(b\in B\)) for the computational resources, and the constraint (18a) indicates that the task offloading ratio should be between 0 and 1. The BS needs a reasonable pricing strategy and resource allocation strategy to incentivize UAVs to offload tasks to it, and the BS utility is expressed as follows:
| \[ \begin{align} & P4:\max U_{bs}^{U-B}=\sum\limits_{i=1}^{N}{\sum\limits_{j=1}^{K}{({{q}_{b}}f_{i,j,b}^{BS}-{{\mu }_{2}}e_{i,j,b}^{BS})}} \tag{19} \\ & s.t.~{{\mu }_{2}}e_{i,j,b}^{U-B}+{{q}_{b}}f_{i,j,b}^{BS}\le {{\mu }_{2}}{{\gamma }^{UAV}}{{\alpha }_{i}}{{\beta }_{i,j}}{{D}_{i}}C{{(f_{i,j}^{UAV})}^{2}} \tag{19a} \\ & \text{0}\le f_{i,j,b}^{BS}\le F_{\max }^{BS} \tag{19b} \\ & {{q}_{b}}>0 \tag{19c} \end{align}\] |
Where constraint (19a) ensures that the UAV’s own interests are not jeopardised. The constraint (19b) indicates that the computational resources allocated by the BS for the task should not be greater than the maximum amount of computational resources. Constraint (19c) indicates that the unit price of resources should be positive.
Problem P4 is a standard convex optimisation problem when the offloading policy of the MU is known as well as the offloading policy and resource allocation policy of the UAV. However, in the actual solution, the limitations of constraint (19a) must be considered. In order to obtain a more efficient solution design, we transform problem P4 using the Lagrange duality method. Let \({{\lambda }_{i,j}}\ge 0\) (\(i\in N,j\in K\)) denote the duality variables corresponding to the constraint (19a), and the partial Lagrange expression for problem P4 is as follows:
| \[\begin{align} & L({\lambda_{i,j}}, {q_{b}}, f_{i,j,b}^{\text{BS}}) \nonumber \\ &\!\quad = \sum_{i=1}^{N} \sum_{j=1}^{K} \big[ {q_{b}}f_{i,j,b}^{\text{BS}} - {\mu_{2}}e_{i,j,b}^{\text{BS}} \nonumber \\ &\!\qquad - {\lambda_{i,j}}({\mu_{2}}e_{i,j,b}^{\text{U$-$B}} + {q_{b}}f_{i,j,b}^{\text{BS}} \nonumber \\ &\!\qquad - {\mu_{2}}{\gamma^{\text{UAV}}}{\alpha_{i}}{\beta_{i,j}}{D_{i}}C{(f_{i,j}^{\text{UAV}})^{2}} \big] \tag{20} \end{align}\] |
Problem P4 can be rephrased as
| \[\begin{align} & P4.1:~\underset{{{q}_{b}},f_{i,j,b}^{BS}}{\mathop{\max }}\,\underset{\lambda }{\mathop{\min }}\,L({{\lambda }_{i,j}},{{q}_{b}},f_{i,j,b}^{BS}) \tag{21} \\ & s.t.~{{\lambda }_{i,j}}\ge 0,\mathrm{(19b)},\mathrm{(19c)} \nonumber \end{align}\] |
The duality function of problem P4 is expressed as
| \[\begin{align} g({{\lambda }_{i,j}},{{q}_{b}},f_{i,j,b}^{BS})=\underset{{{q}_{b}},f_{i,j,b}^{BS}}{\mathop{\max }}\,L({{\lambda }_{i,j}},{{q}_{b}},f_{i,j,b}^{BS}) \tag{22} \end{align}\] |
Further, the duality problem for P4 can be obtained
| \[\begin{align} & P4.2:~\underset{\lambda }{\mathop{\min }}\,g({{\lambda }_{i,j}},{{q}_{b}},f_{i,j,b}^{BS}) \tag{23} \\ & s.t.~{{\lambda }_{i,j}}\ge 0,\mathrm{(19b)},\mathrm{(19c)} \nonumber \end{align}\] |
As long as \({{q}_{b}}\) and \(f_{i,j,b}^{BS}\) are set to sufficiently small positive values so that the constraints (19a) satisfy the strict inequality, there is always a feasible interior solution to Problem P4, and thus the slater condition holds [13], i.e., the original Problem P4 has strong duality with the duality Problem P4.2, and solving the duality Problem P4.2 is equivalent to solving problem P4. Therefore, we first maximize the Lagrange function given the value of \({{\lambda }_{i,j}}\) to obtain the expression of the duality function, and then obtain the optimal solution of the duality variable \(\lambda _{i,j}^{*}\) by minimizing the duality function. An approximate optimal solution to the original problem can be obtained based on the optimal duality variables.
4. Nash Equilibrium Analysis of Games
4.1 Analysis of the UAV-BS Game
Theorem 1: For each fixed \({{q}_{b}}\), the Nash equilibrium of the UAV-BS game always exists and is unique. The optimal strategy is denoted as
| \[\begin{align} & f{{_{i,j,b}^{BS*}}}=\frac{(1+\lambda ){{q}_{b}}}{2{{\mu }_{2}}{{\gamma }^{BS}}{{\alpha }_{i}}{{\beta }_{i,j}}C{{D}_{i}}} \tag{24} \\ & {{\beta }^{*}_{i,j}}=\frac{{{q}_{b}}}{{{\mu }_{2}}{{\alpha }_{i}}{{D}_{i}}}\sqrt{\frac{(1+\lambda )R_{j,b}^{U-B}}{2{{\gamma }^{BS}}Cp_{j,b}^{U-B}}} \tag{25} \end{align}\] |
Proof: Using the KKT condition, the optimal closed-form analytic form of the optimization variable \(f_{i,j,b}^{BS}\) in the duality problem P4.2 is obtained by making the first-order partial derivatives of Eq. (20) with respect to \(f_{i,j,b}^{BS}\) to be zero while fixing \(\lambda\), i.e., Eq. (24). Bringing \(f{{_{i,j,b}^{BS*}}}\) into the utility function in Eq. (18) yields \(\frac{{{\partial }^{2}}U}{\partial {{({{\beta }_{i,j}})}^{2}}}>0\), which indicates that the utility function is a convex function on \({{\beta }_{i,j }}\) as a convex function. Let \(\frac{\partial U}{\partial {{\beta }_{i,j}}}=0\) to obtain the optimal offloading policy for UAV, i.e., Eq. (25).
Moreover, Eq. (20) is continuous with respect to \({{q}_{b}}\) and has zero second-order partial derivatives. Since the set of players involved in the game is finite and the strategy space of the game belongs to a bounded, nonempty convex set on the Euclidean space. Therefore, for each fixed \({{q}_{b}}\), the UAV-BS game is a convex multi-player game [13] with a unique Nash equilibrium [14]. With fixed \({{\lambda }_{i,j}}\), the optimal set of strategies \(\{{{\beta }^{*}_{i,j}},{{q}^{*}_{b}},f{{{_{i,j,b}^{BS*}}}\\}\}\) brings the UAV-BS game to the Nash equilibrium.
4.2 Analysis of the MU-UAV Game
Theorem 2: For each fixed \({{m}_{j}}\), the Nash equilibrium of the MU-UAV game always exists and is unique. The optimal strategy is denoted as
| \[\begin{align} & f{{_{i,j}^{UAV}}^{*}}=\frac{{{m}_{j}}}{2{{\mu }_{2}}{{\gamma }^{UAV}}{{\alpha }_{i}}(1-{{\beta }_{i,j}})C{{D}_{i}}} \tag{26} \\ & \alpha _{i}^{*}=\left\{ \begin{array}{*{35}{l}} \alpha _{i}^{(1)} & t_{i,j}^{UAV}\ge t_{i,j}^{U-B}+t_{i,j}^{BS} \\ \max \{\alpha _{i}^{(2)},\alpha _{i}^{(3)}\} & t_{i,j}^{UAV}<t_{i,j}^{U-B}+t_{i,j}^{BS} \\ \end{array} \right. \tag{27} \end{align}\] |
Proof: Solving for the second-order partial derivative of \(U_{uav}^{M-U}\) with respect to \(f_{i,j}^{UAV}\) yields \(\frac{{{\partial }^{2}}U}{\partial {{(f_{i,j}^{UAV})}^{2}}}<0\). It shows that there exists a unique \(f{{_{i,j}^{UAV}}^{*}}\) that maximises \(U_{uav}^{M-U}\), such that \(\frac{\partial U}{\partial f_{i,j}^{UAV}}=0\), and obtains the optimal resource allocation policy, i.e., Eq. (26).
According to Eq. (15), the total task execution time \(t_{i}^{all}=t_{i}^{MU}\) when \(t_{i}^{MU}\ge t_{i}^{off}\). At this point, calculating the first-order partial derivative of \(U_{mu}^{M-U}\) with respect to \({{\alpha }_{i}}\) yields
| \[\begin{align} & \frac{\partial U}{\partial {{\alpha }_{i}}} = \frac{{{\mu }_{2}}p_{i,j}^{M-U}{{D}_{i}}}{R_{i,j}^{M-U}}-\frac{m_{j}^{2}}{2{{\alpha }_{i}}^{2}{{\mu }_{2}}{{\gamma }^{UAV}}(1-{{\beta }_{i,j}})C{{D}_{i}}} \tag{28} \\ & \hphantom{\frac{\partial U}{\partial {{\alpha }_{i}}}=} - \frac{{{\mu }_{1}}C{{D}_{i}}}{f_{i}^{MU}}-{{\mu }_{2}}{{\gamma }^{MU}}C{{D}_{i}}{{(f{{_{i}^{MU}}^{*}})}^{2}} \nonumber \end{align}\] |
Since the transmission energy consumption of a task with the same number of tasks is less than the computation energy consumption, \(\frac{\partial U}{\partial {{\alpha }_{i}}}<0\). It shows that \(U_{mu}^{M-U}\) is monotonically decreasing with respect to \({{\alpha}_{i}}\), so that \(U_{mu}^{M-U}\) obtains a minimum at \(t_{i}^{MU}=t_{i}^{off}\) when \(t_{i}^{MU}\ge t_{i}^{off}\).
Let \(t_{i}^{MU}=t_{i}^{off}=t_{i,j}^{M-U}+t_{i,j}^{UAV}\) and solve the offloading strategy as follows:
| \[\begin{align} \alpha _{i}^{(1)}=\frac{{{m}_{j}}}{2{{\mu }_{2}}D}(\sqrt{\frac{4{{\mu }_{2}}}{{{m}_{j}}}(\frac{C}{f_{i}^{MU}}-\frac{{{K}^{2}}}{{{\mu }_{2}}D{{m}_{j}}})+H_{1}^{2}})+{{H}_{1}}) \tag{29} \end{align}\] |
Where \(H1=\frac{2\Phi }{{{m}_{j}}}-\frac{C}{f_{i}^{MU}}-\frac{1}{R_{i,j}^{M-U}}\),\(\Phi ={{q}_{b}}\sqrt{\frac{(1+\lambda )R_{j,b}^{U-B}}{2{{\gamma }^{BS}}Cp_{j,b}^{U-B}}}\).
Let \(t_{i}^{MU}=t_{i}^{off}=t_{i,j}^{M-U}+t_{i,j}^{U-B}+t_{i,j}^{BS}\) and solve the offloading strategy as follows:
| \[\begin{align} \alpha _{i}^{(2)}=\frac{f_{i}^{MU}R_{j,b}^{U-B}}{f_{i}^{MU}+CR_{j,b}^{U-B}}(H2-\frac{2{{q}_{b}}CR_{j,b}^{U-B}}{{{\mu }_{2}}DP_{j,b}^{U-B}}) \tag{30} \end{align}\] |
Where \(H2=\frac{C}{f_{i}^{MU}}-\frac{\Phi }{{{\mu }_{2}}DR_{j,b}^{U-B}}\).
When \(t_{i}^{MU}\le t_{i}^{off}\) and \(t_{i,j}^{UAV}\ge t_{i,j}^{U-B}+t_{i,j}^{BS}\), \(t_{i}^{all}=t_{i,j}^{M-U}+t_{i,j}^{UAV}\). Bring the constraint (17a) to \(U_{mu}^{M-U}\) and then compute the second-order partial derivative with respect to \({{M}_{i}}\) to obtain \(\frac{{{{\partial }^{2}}}U}{\partial {{({{M}_{i}}})}^{2}}>0\). Making the first-order partial derivative equal to zero yields \(M_{i}^{*}=\sqrt{{{{\mu }_{1}}{{\alpha }_{i}}(1-{{\beta }_{i,j}}})C{{{D}_{i}}{{m}_{j}}}}\). Bringing \(M_{i}^{*}\) into the utility function and then computing the first-order partial derivative with respect to \({{\alpha }_{i}}\) yields
| \[\begin{align} \frac{\partial U}{\partial {{\alpha }_{i}}}=\sqrt{\frac{{{\mu }_{1}}(1-{{\beta }_{i,j}})C{{D}_{i}}{{m}_{j}}}{{{\alpha }_{i}}}}+H3 \tag{31} \end{align}\] |
Where \(H3=\frac{({{\mu }_{1}}+{{\mu }_{2}}p_{i,j}^{M-U}){{D}_{i}}}{R_{i,j}^{M-U}}-{{\mu }_{2}}{{\gamma }^{MU}}C{{D}_{i}}{{(f_{i}^{MU})}^{2}}\).
Then computing the second-order partial derivatives yields \(\frac{{{\partial }^{2}}U}{\partial {{({{\alpha }_{i}})}^{2}}}<0\). It means that the first-order partial derivatives of \(U_{mu}^{M-U}\) are \(\frac{\partial U}{\partial {{\alpha }_{i}}}\) monotonically decreasing. When \({{\alpha }_{i}}\) takes small enough positive values, \(\frac{\partial U}{\partial {{\alpha }_{i}}}>0\). When \({{\alpha }_{i}}\) tends to a value of 1, \(\frac{\partial U}{\partial {{\alpha }_{i}}}\) tends to \(\sqrt{{{\mu }_{1}}(1-{{\beta }_{i,j}})C{{D}_{i}}{{m}_{j}}}+H3\). Where \(\sqrt{{{\mu }_{1}}(1-{{\beta }_{i,j}})C{{D}_{i}}{{m}_{j}}}\) is equivalent to \({M_{i}^{*}}\) when \({\alpha }_{i}\) tends to 1 because the sum of the monetary cost and the transmission cost is greater than the computational cost with the same task size, so that \(\frac{\partial U}{\partial {{\alpha }_{i}}}>0\). Thus, \({U_{mu}^{M-U}}\) is monotonically increasing with respect to \({{\alpha }_{i}}\) and obtains a minimum at \({t_{i}^{MU}=t_{i,j}^{M-U}+t_{i,j}^{UAV}}\).
When \(t_{i}^{MU}\le t_{i}^{off}\) and \(t_{i,j}^{UAV}<t_{i,j}^{U-B}+t_{i,j}^{BS}\), \(t_{i}^{all}=t_{i,j}^{M-U}+t_{i,j}^{U-B}+t_{i,j}^{BS}\). Equation (24) and Eq. (25) are brought into \(U_{mu}^{M-U}\), and then the first-order partial derivatives and second-order partial derivatives with respect to \({{\alpha }_{i}}\)] are calculated:
| \[\begin{align} & \frac{\partial U}{\partial {{\alpha }_{i}}}=H3-\frac{{{\mu }_{2}}Dm_{j}^{2}}{2C{{\gamma }^{UAV}}{{({{\mu }_{2}}D{{\alpha }_{i}}-\Phi )}^{2}}} \tag{32} \\ & \frac{{{\partial }^{2}}U}{\partial {{({{\alpha }_{i}})}^{2}}}=\frac{{{({{\mu }_{2}}D{{m}_{j}})}^{2}}}{C{{\gamma }^{UAV}}{{({{\mu }_{2}}D{{\alpha }_{i}}-\Phi )}^{3}}} \tag{33} \end{align}\] |
Based on constraint (18a) and Eq. (25), it can be concluded that \({{\mu }_{2}}D{{\alpha }_{i}}>\Phi\), and therefore \(\frac{{{{\partial }^{2}}}U}{\partial {{{({{\alpha }_{i}})}^{2}}}}>0\). So when \(t_{i}^{all}=t_{i,j}^{M-U}+t_{i,j}^{U-B}+t_{i,j}^{BS}\), \(U_{mu}^{M-U}\) is a convex function with respect to \({{\alpha }_{i}}\), and the first-order partial derivative is made equal to zero to obtain the offloading strategy
| \[\begin{align} \alpha _{i}^{(3)}=\frac{1}{{{\mu }_{2}}D}(\sqrt{\frac{{{\mu }_{2}}Dm_{j}^{2}}{2C{{\gamma }^{UAV}}H3}}+\Phi ) \tag{34} \end{align}\] |
At this point, there are two cases: (i) When \(\alpha _{i}^{(2)}\ge \alpha _{i}^{(3)}\), \(U_{mu}^{M-U}\) is monotonically increasing in the range of \({{\alpha }_{i}}\in [\alpha _{i}^{(2)},1]\), the optimal offloading strategy is \(\alpha _{i}^{*}=\alpha _{i}^{(2)}\). (ii) When \(\alpha _{i}^{(2)}<\alpha _{i}^{(3)}\), \(U_{mu}^{M-U}\) is a strictly convex function in the range of \({{\alpha }_{i}}\in [\alpha _{i}^{(2)},1]\), the optimal offloading strategy is \(\alpha _{i}^ {*}=\alpha _{i}^{(3)}\).
Moreover, \(U_{uav}^{M-U}\) is continuous with respect to \({{m}_{j}}\) and has zero second order partial derivatives. Therefore, for each fixed \({{m}_{j}}\), there exists a unique Nash equilibrium point for the MU-UAV game [13], [14], i.e., the set of optimal strategies \(\{{{\alpha }^{*}_{i}},m_{j}^{*},f{{_{i,j}^{UAV}}^{*}}\}\).
Since UAV’s set of strategies in the MU-UAV game and the UAV-BS game do not interfere with each other, there exists a unique Nash equilibrium for the Stackelberg bilayer game.
5. Algorithm Design
In order to obtain an approximate optimal solution to the proposed problem, as shown in Algorithm 1, we propose a multi-leader, multi-follower Stackelberg bilayer game TASR algorithm.
 |
Since the duality variable \({{\lambda }_{i,j}}\) introduced in Problem P4.2 is a variable outside the set of game strategies, \({{\lambda }_{i,j}}\) and the set of game strategies need to be iterated alternately in order to obtain the near-optimal solution. In each iteration, the game strategy is first updated with \({{\lambda }_{i,j}}\) fixed, and then \({{\lambda }_{i,j}}\) is updated with the game strategy fixed. The optimal duality solution and the optimal set of strategies are obtained when the iterative algorithm converges. Algorithm 1 describes the detailed algorithmic procedure.
For the duality variable \({{\lambda}_{i,j}}\), the subgradient method is used to update the variable values at each iteration, and the update expression is denoted as
| \[\begin{align} & {{\lambda }^{\tau +1}_{i,j}}={{[{{\lambda }^{\tau }_{i,j}}+{{\theta }^{\tau }}\Delta {{\lambda }^{\tau }_{i,j}}]}^{+}} \tag{35} \\ & \Delta {{\lambda }^{\tau }_{i,j}}={{\mu }_{2}}*e_{i,j,b}^{U-B}+{{q}_{b}}f_{i,j,b}^{BS} \nonumber \\ & \hphantom{\Delta {{\lambda }^{\tau }_{i,j}}=} - {{\mu }_{2}}{{\gamma }^{UAV}}{{\alpha }_{i}}{{\beta }_{i,j}}{{D}_{i}}C{{(f_{i,j}^{UAV})}^{2}} \tag{36} \end{align}\] |
Where \(\Delta {{\lambda }^{\tau}_{i,j}}\) denotes the corresponding subgradient, and \({{\theta }^{\tau }}\) denotes the step size of the first \(\tau\) iteration.
Although increasing the amount of computing resources allocated increases the monetary gain of the server, it is accompanied by a quadratic increase in energy cost, which is consistent with the principle of diminishing marginal returns in economics [15], [16]. Using the marginal revenue formula, the server price update expression is expressed as
| \[\begin{align} & {{m}^{\tau +1}_{j}}={{m}^{\tau }_{j}}+\delta M{{R}^{\tau }_{UAV}} \tag{37} \\ & {{q}^{\tau +1}_{b}}={{q}^{\tau }_{b}}+\delta M{{R}^{\tau }_{BS}} \tag{38} \end{align}\] |
Where \(\delta\) is the iterative step adjustment factor, and \(M{{R}^{\tau }_{UAV}}\) and \(M{{R}^{\tau }_{BS}}\) denote the marginal returns of UAV and BS, respectively. Introducing a very small price change factor \(\varepsilon\), \(M{{R}^{\tau }_{UAV}}\) and \(M{{R}^{\tau }_{BS}}\) can be specified as
| \[\begin{align} & M{{R}^{\tau }_{UAV}}=\frac{U_{uav}^{M-U}({{m}^{\tau }_{j}}+\varepsilon )-U_{uav}^{M-U}({{m}^{\tau }_{j}}-\varepsilon )}{\sum\limits_{i=1}^{N}{[f_{i,j}^{UAV*}({{m}^{\tau }_{j}}+\varepsilon )-f_{i,j}^{UAV*}({{m}^{\tau }_{j}}-\varepsilon )]}} \tag{39} \\ & M{{R}^{\tau }_{BS}}=\frac{L({{q}^{\tau }_{b}}+\varepsilon )-L({{q}^{\tau }_{b}}-\varepsilon )}{\sum\limits_{i=1}^{N}{\sum\limits_{j=1}^{K}{[f_{i,j,b}^{BS*}({{q}^{\tau }_{b}}+\varepsilon )-f_{i,j,b}^{BS*}({{q}^{\tau }_{b}}-\varepsilon )]}}} \tag{40} \end{align}\] |
In addition, a server selection algorithm based on the principle of least cost is designed in order to ensure competitiveness among multi-leaders. As shown in Algorithm 2, the MUs and UAVs select the service that minimises their offloading cost as the new task offloading destination after each iteration.
 |
6. Simulation Results
In this section, a detailed simulation experiment of the proposed algorithm is carried out using the MATLAB tool, and the simulation results are compared with the benchmark scenario. The parameters used in the simulation are based on the experimental simulation of the real scenario, as shown in Table 1 [6], [17]. The 2D coordinates of the BS, UAV, and MU are randomly generated in a range of 1000m \(\times\) 1000m, where the heights of the UAV, BS, and MU are fixed at 100m, 2m, and 0m, respectively.
Table 1 Simulation parameters. |
 |
Figure 2 shows the iterative process of task offloading ratio. In the initial stage of the game, the task offloading proportion in the MU-UAV game shows an increasing trend. In contrast, the proportion of task offloading in the UAV-BS game has a decreasing trend. After about 90 iterations, the offloading strategies in the bilayer game begin to fluctuate in a small range until they finally converge. In Fig. 2, the offloading ratio of task 3 showed a wide range of changes after about 90 iterations. It indicates that \(\text{M}{{\text{U}}_{\text{3}}}\) changed its task offloading destination after this iteration, i.e., another UAV was selected as the server, which also implies that the BS serving Task 3 also changed.
 |
Fig. 2 Variation in offloading ratio |
Figure 3 shows how the MU cost changes as the number of iterations increases. At the beginning of the iteration, the cost of each MU shows an increasing trend. As the number of iterations increases, the cost of MUs starts to show a decreasing potential and reaches a converged state at the end. When the costs of all MUs are in the converged state, the system reaches Nash equilibrium. Jointly observing task 3 in Fig. 2 and \(\text{M}{{\text{U}}_{\text{3}}}\) in Fig. 3, the cost of \(\text{M}{{\text{U}}_{\text{3}}}\) shows a small fluctuation near the 90th iteration and then continues to show a decreasing trend, indicating that the change of a single node does not affect the performance of the proposed algorithm, which confirms that the TASR algorithm has a certain degree of robustness.
 |
Fig. 3 Variations in the cost of MUs |
Next, to verify the superior performance of TASR, we introduce three benchmark schemes for comparison. (1) Full offloading of distribution scheme (FODS): MU offloads all the tasks to the UAV for processing [18], and a single-layer game is played between the UAV and the BS to determine the offloading policy. (2) Uniform offloading distribution scheme (UODS): The same proportion of data is computed by BS, UAV, and MU for each task. The other strategies are solved in the same way as TASR. (3) Randomised offloading ratio scheme (RORS): The task offloading ratio is randomly generated between \([0,1]\).
Figure 4 compares the impact of different offloading schemes on the total system cost. TASR achieves the joint optimization of offloading strategies and computational resources by solving the Nash equilibrium of the bilayer game, which reduces the total system cost. UODS is unable to take into account the differences in the resources of different nodes, which leads to the imbalance in the utilization of the resources. The decision-making of RODS is stochastic and the optimization is inefficient. FODS in the case of only a single-layer game lacks dynamic analysis of user requirements and is completely dependent on server resources. Therefore, under the same conditions TASR can obtain the minimum system cost and always has better performance. This proves the superiority of TASR. Moreover, TASR converges after about 360 iterations, which proves the existence of Nash equilibrium from an experimental point of view.
 |
Fig. 4 Total system cost for different offloading schemes |
In addition, we conduct simulation experiments for different numbers of MUs. Figure 5 and Fig. 6 compare the effects of the number of MUs on the average latency and the total system cost of executing tasks under different offloading scenarios, respectively. Figure 5 shows that TASR obtains the lowest average latency, and the increase in the number of MUs does not cause significant fluctuations in the average latency. Figure 6 indicates that TASR obtains the lowest total system cost in the different number of MUs in an environments, TASR obtains the lowest total system cost. When the number of users is high, TASR reduces the energy consumption by about 7% compared to UODS and about 16% compared to FODS. The results validate the robustness and superiority of TASR.
 |
Fig. 5 Average latency with different number of MUs |
 |
Fig. 6 Total energy consumption with different number of MUs |
7. Conclusion
In this paper, we study MEC systems that contain multiple MEC server-equipped UAVs and BSs and multiple MUs. We model the interaction process between MEC servers and MUs as a multi-leader, multi-follower Stackelberg bilayer game and prove the existence and uniqueness of Nash equilibrium. We propose the TASR algorithm to obtain an approximate optimal solution to the proposed problem and evaluate the effectiveness of the proposed algorithm through detailed simulation experiments. Results show that the TASR algorithm is significantly superior and robust compared to other benchmark schemes. Due to the variability of hotspot areas for task requirements, we will consider UAV location deployment and path planning in future research.
References
[1] X. Lyu, W. Ni, H. Tian, R.P. Liu, X. Wang, G.B. Giannakis, and A. Paulraj, “Optimal Schedule of Mobile Edge Computing for Internet of Things Using Partial Information,” IEEE J. Sel. Areas Commun., vol.35, no.11, pp.2606-2615, Nov. 2017.
CrossRef
[2] G. Xie, Z. Wang, and Y. Liu, “Joint Task Partition and Resource Allocation for Multiuser Cooperative Mobile Edge Computing,” Wirel. Commun. Mob. Comput., vol.2022, pp.1-13, 2022.
CrossRef
[3] Y. Mao, C. You, J. Zhang, K. Huang, and K.B. Letaief, “A Survey on Mobile Edge Computing: The Communication Perspective,” IEEE Commun. Surv. Tutor., vol.19, no.4, pp.2322-2358, 2017.
CrossRef
[4] Z. Shah, U. Javed, M. Naeem, S. Zeadally, and W. Ejaz, “Mobile Edge Computing (MEC)-Enabled UAV Placement and Computation Efficiency Maximization in Disaster Scenario,” IEEE Trans. Veh. Technol., vol.72, no.10, pp.13406-13416, Oct. 2023.
CrossRef
[5] G. Mitsis, E.E. Tsiropoulou, and S. Papavassiliou, “Data Offloading in UAV-Assisted Multi-Access Edge Computing Systems: A Resource-Based Pricing and User Risk-Awareness Approach,” Sensors, vol.20, no.8, p.2434, Jan. 2020.
CrossRef
[6] Z. Yu, Y. Gong, S. Gong, and Y. Guo, “Joint Task Offloading and Resource Allocation in UAV-Enabled Mobile Edge Computing,” IEEE Internet Things J., vol.7, no.4, pp.3147-3159, April 2020.
CrossRef
[7] S. Jeong, O. Simeone, and J. Kang, “Mobile Edge Computing via a UAV-Mounted Cloudlet: Optimization of Bit Allocation and Path Planning,” IEEE Trans. Veh. Technol., vol.67, no.3, pp.2049-2063, March 2018.
CrossRef
[8] M. Wang, L. Zhang, P. Gao, X. Yang, K. Wang, and K. Yang, “Stackelberg-Game-Based Intelligent Offloading Incentive Mechanism for a Multi-UAV-Assisted Mobile-Edge Computing System,” IEEE Internet Things J., vol.10, no.17, pp.15679-15689, 2023.
CrossRef
[9] H. Zhou, Z. Wang, G. Min, and H. Zhang, “UAV-aided computation offloading in mobile-edge computing networks: A stackelberg game approach,” IEEE Internet Things J., vol.10, no.8, pp.6622-6633, April 2023.
CrossRef
[10] H. Lu, X. He, M. Du, X. Ruan, Y. Sun, and K. Wang, “Edge QoE: Computation Offloading With Deep Reinforcement Learning for Internet of Things,” IEEE Internet Things J., vol.7, no.10, pp.9255-9265, Oct. 2020.
CrossRef
[11] F. Costanzo, P.D. Lorenzo, and S. Barbarossa, “Dynamic Resource Optimization and Altitude Selection in Uav-Based Multi-Access Edge Computing,” ICASSP 2020 - 2020 IEEE International Conference on Acoustics, Speech and Signal Processing (ICASSP), pp.4985-4989, May 2020.
CrossRef
[12] Technical Specification Group Radio Access Network, “Study on enhanced LTE support for aerial vehicles,” document 3GPP TR 36.777 V15.0.0, Dec. 2017.
[13] Y. Chen, Z. Li, B. Yang, K. Nai, and K. Li, “A Stackelberg game approach to multiple resources allocation and pricing in mobile edge computing,” Future Gener. Comput. Syst., vol.108, pp.273-287, July 2020.
CrossRef
[14] J.B. Rosen, “Existence and Uniqueness of Equilibrium Points for Concave N-Person Games,” Econometrica, vol.33, no.3, p.520, July 1965.
CrossRef
[15] P.J. Coughlin, “Changes in Marginal Revenue and Related Elasticities,” South. Econ. J., vol.51, no.2, pp.568-573, 1984.
CrossRef
[16] X. He, A. Prasad, and S.P. Sethi, “Cooperative advertising and pricing in a dynamic stochastic supply chain: Feedback Stackelberg strategies,” PICMET ’08 - 2008 Portland International Conference on Management of Engineering & Technology, pp.1634-1649, July 2008.
CrossRef
[17] L. Zhang and N. Ansari, “Latency-Aware IoT Service Provisioning in UAV-Aided Mobile-Edge Computing Networks,” IEEE Internet Things J., vol.7, no.10, pp.10573-10580, Oct. 2020.
CrossRef
[18] S. Bi and Y.J. Zhang, “Computation Rate Maximization for Wireless Powered Mobile-Edge Computing With Binary Computation Offloading,” IEEE Trans. Wirel. Commun., vol.17, no.6, pp.4177-4190, June 2018.
CrossRef
Authors
Changchun University of Science and Technology
is pursuing a master’s degree in information and communication engineering at Changchun University of Science and Technology. His main research interests are mobile edge computing, service caching, and the IoT.
 |
Changchun University of Science and Technology
is a professor and doctoral supervisor in the field of information and communication engineering. Her main research interests are optical communication and communication technology. In recent years, Prof. Chen has completed more than ten national, provincial and horizontal projects.
 |
Changchun University of Science and Technology
is pursuing her PhD in Information and Communication Engineering. She participated in and completed several national, provincial and horizontal projects during her PhD program. Her main research interests are mobile edge computing, heterogeneous networks, and optical communication technologies.
 |
