Air–ground integrated deployment for UAV-enabled mobile edge computing: A hierarchical game approach
无人机赋能移动边缘计算的空地一体化部署：一种分层博弈方法

1 Introduction 1 引言

Mobile edge computing (MEC) technology is seen as a promising technology in the fifth generation (5G) communication networks due to the computation-intensive and delay-sensitive requirement [1, 2]. In the urban environment, computing devices are mainly deployed in base stations or Wi-Fi systems, which are constrained by fixed locations. Aiming at the MEC service in the cellular coverage area, unmanned aerial vehicles (UAVs) are drawing increasing attention for the advantage of flexibility and manoeuvrability [3–5]. Recent research work had used it for complex computing environments with a large range, high urgency, and multiple tasks [6–10].
移动边缘计算（MEC）技术因其计算密集型和时延敏感性要求，被视为第五代（5G）通信网络中一种有前途的技术[1,2]。 在城市环境中，计算设备主要部署在基站或Wi-Fi系统中，这些系统受到固定位置的限制。针对蜂窝覆盖区域的MEC业务，无人机（UAV）因其灵活性和机动性的优势而受到越来越多的关注[3\u20125]。最近的研究工作将其用于大范围、高紧急性和多任务的复杂计算环境[6\u201210]。

In [7], the sum of the maximum delay among ground nodes was minimised by the UAV trajectory optimising and task scheduling. In [8], a moving UAV was used to help the multi-user wireless charging and computing task, where the trajectory and computing frequency of the UAV are optimised to minimise the power consumption. In [9], the authors studied the scenario of single UAV carrying out computation offloading for multiple users. By optimising the flight path of the UAV and the transmission power of ground nodes, the energy consumption of the users can be minimised. Similarly, the authors in [10] took the fairness-aware task data allocation into consideration, and optimised the trajectory of the UAV to reduce the maximum energy consumption.
在[7]中，通过无人机轨迹优化和任务调度，使地面节点间最大时延之和最小化。在[8]中，使用移动的无人机来帮助多用户无线充电和计算任务，其中优化了无人机的轨迹和计算频率以最小化功耗。在[9]中，作者研究了单架无人机为多个用户进行计算卸载的场景。通过优化无人机的飞行路径和地面节点的发射功率，可以最大限度地降低用户的能耗。同样，作者在[10]中考虑了公平意识的任务数据分配，并优化了无人机的轨迹以降低最大能耗。

The above literature verified that UAVs are suitable to serve the MEC technology. They mainly unilaterally changed the trajectory of the UAV so that it could receive the computing data from ground nodes in sequence efficiently. Several defects can be noted when implementing such models. On the one hand, uncertain data generation of ground nodes makes the UAV adjustment more difficult. If the ground node is just far away from the UAV, the link quality between them will be poor for the computing data offloading. On the other hand, to avoid the resource competition, multiple UAVs may be needed to deployed for a large-scale system, which will consume excessive propulsion energy of the flight.
上述文献验证了无人机适合服务于MEC技术。他们主要是单方面改变了无人机的轨迹，使其能够有效地按顺序接收来自地面节点的计算数据。在实现此类模型时，可以注意到几个缺陷。一方面，地面节点数据生成的不确定性使得无人机的调整更加困难。如果地面节点距离无人机刚好远，那么对于计算数据卸载来说，它们之间的链路质量会很差。另一方面，为了避免资源竞争，可能需要部署多架无人机进行大规模系统，这将消耗飞行的过度推进能量。

To solve the problem of UAV-enabled edge computing service for the large-scale ground network, a novel air-ground integrated optimising structure is proposed. Different from the existing work where the ground nodes receive the service of UAV passively, a collaborative scheme among ground nodes is designed in this study. Specifically, ground nodes form data gathered coalitions according to the air position of the UAV. The nodes close to the UAV will be the coalition header and is responsible for the computing data offloading. The coalition formation of ground nodes improves the efficiency of data transmission between the UAV and whole ground networks, thus solving the problem of limited coverage of UAV.

The rest of this paper is arranged as follows. In Section 2, we review the related work. In Section 3, the joint optimisation problem of ground–air transmission rate is modelled. A hierarchical game model is proposed and analysed to prove the existence of SE in Section 4. In Section 5, a distributed dynamic coalition formation algorithm to obtain the optimal solution of the above game model is presented. Section 6 shows the simulation results and analysis. In the end, we conclude.

2 Related work

The existing work mainly optimised the coverage and energy consumption of UAV-assisted communications by the location deployment of UAVs [15–19]. For example, in [15], an efficient game model of multi-UAV coverage deployment was constructed. The joint optimisation of position and power was carried out considering the cooperative relationship between drones. In [16], the authors proposed an optimal deployment algorithm for UAV base stations to find the optimal position to cover more users with the minimum transmission power. In [17], the probability of the line-of-sight (LoS) link was derived according to different elevation angles, then an air-to-ground path loss model was used to improve the coverage performance. In [18], the authors designed a game theory model of the cooperative search for multiple UAVs. Therefore, how to deploy the UAV to improve the throughput of data transmission is a problem worthy of attention. In [19], a cooperative UAV clustering scheme is proposed to offload ground mobile terminals from ground cellular base stations to cooperative UAV clusters.

At present, the research of CFG mainly focuses on communication connection enhancement, data transmission, and routing mechanism improvement [20, 21]. The design of the group-buying mechanism [20] provided a win–win situation and effective resource allocation, which was very suitable for solving the transmission optimisation problem in our work. The CFG framework is modelled to solve the problem of resource allocation and data transmission in [21]. Motivated by this CFG model, if ground nodes form effective coalitions, the data of remote nodes can be gathered to the coalition header, which will greatly reduce the transmission delay and improve the transmission efficiency. Meanwhile, by adjusting the position, the UAV can improve the coverage ability to the ground coalition header.

However, it is also a great challenge to describe the complex relationship between the UAV and ground nodes [22]. The location deployment of the UAV directly affects the formation of the coalition and the transmission delay. Ground nodes make corresponding coalition selection according to the position of the UAV, improve the network performance, and assist the optimisation effectiveness of UAV coverage. Owing to the significant difference in hierarchy and priority between UAV and ground nodes in the network, it is most appropriate to use the Stackelberg game model to describe the hierarchical interaction between the UAV and ground nodes [23, 24]. Stackelberg game equilibrium solution can be obtained through the mixed strategy analysis of the leader and follower utility functions.

Note that this study refers to the coalition formation mechanism in [21]. The differences are that (i) the system model of [21] is data transmission optimisation among UAVs, while we consider the air to ground joint transmission optimisation. (ii) We consider the effect of ground nodes on UAV coverage utility and construct a hierarchical game framework to describe this effect.

3 System model and problem formulation

3.1 System model

This study considers a UAV-enabled MEC model consisting of single UAV and N static ground nodes randomly deployed in the mission area , where R is the side length of the network. The ground node set is defined as , . The position of the UAV is denoted by , where we assume that the height of the UAV remains fixed.

As shown in Fig. 1, a rotor drone serves as an edge computing carrier. Owing to the limited antenna beam width and transmission energy, it covers only a small number of users in the mission area I. The users outside the coverage of UAV cannot connect to it directly. To effectively extend the coverage of UAV, external and internal devices are connected with the device to device (D2D) transmission model. To ensure that the drone can collect information from ground nodes in all directions, ground nodes are divided into several clusters. Cluster members communicate with the cluster head by D2D link. The LoS link is used for data transmission between the cluster head and the UAV. In addition, we assume that there is no interference between clusters.

The distance between ground nodes determines the quality of the D2D channel [25]. The farther the distance, the worse the communication quality. Considering the influence of the distance between ground nodes on D2D channel quality, we find a probability function to describe the relationship between distance and communication quality. According to [25], a transmission probability model of D2D communication is obtained by calculating the signal-to-noise ratio threshold, which is very suitable for our expectation. Given the distance between two ground nodes, the accessibility probability of the data can be well predicted. In the scenario of our work, the general form of the probability is

(1)

where d is the distance between two nodes, , is the gamma function. The general form is . is the node density, is the signal-to-noise ratio threshold, is the path loss exponent. represents the data transmission probability of two nodes with a distance of d under the D2D communication link, . Obviously, the closer the distance, the greater the probability of successful communication. When the distance is 0, the transmission probability is 1. When the distance is very far, the probability is almost 0. In general, we define the distance between two nodes as . The probability of successful transmission of data from the cluster head node to its members n can be deduced as .

Note that the above channel model is only for the ground-to-ground transmission. The air-to-ground channel model should also be considered. It will be affected by antenna gain, LoS link probability, shadow fading, and path loss due to the flight characteristics of the drone. Once the above parameters are changed, the air-to-ground transmission effect will be changed immediately. UAV antenna gain is [26]

(2)

When the signal is within the antenna beam width , the antenna gain of the UAV is the main lobe gain . is the number of antennas. Otherwise, antenna gain is the side-lobe gain. The path loss model of air-to-ground communication transmission is described as follows [27]:

(3)

where is the path loss parameter, is the working carrier frequency of the UAV, is the straight-line distance between the ground user n and the UAV, c is the speed of electromagnetic wave. According to [28], the probability of LoS link is

(4)

where and are environment constants, is the elevation angle between the UAV and ground node n. Correspondingly, the non-line-of-sight (NLoS) link is expressed as: . Finally, the coverage probability [29] for the ground node n is

(5)

where represents UAV position, is the carrier transmission power of the UAV, is the minimum transmission power required for a successful detection of the UAV. and are the mean and variance of shadow fading under LoS and NLoS link, respectively. We set , . are the variance coefficients. is the right tail function of a standard normal distribution.

3.2 Problem formulation

In most deployment optimisation problems of the UAV, the ground nodes are just covered passively. If a node is in a remote location, the communication with the UAV is usually cut off, which is not conducive to the efficiency of UAV coverage. To realise the data offloading requirements, our work makes the ground nodes form coalitions to improve the possibility of communication access. Considering the influence of the UAV position on the transmission quality of the air–ground channel and the coalition formation structure, the integrated optimisation of ground coalition formation and UAV position deployment is carried out.

As for ground nodes, the number of available coalitions is denoted by W, , which means the ground nodes can form no more than N coalitions. The coalition selection of node n is denoted by . The coalition set is expressed as . For any coalition , is the head of coalition w. It is expected to reduce transmission delay by optimising coalition selection . In the practical scenario, due to the unknown calculation task of the ground node and the dynamic change of the data amount, the accurate transmission time cannot be predicted. As is known to all, the delay is the quotient of the total amount of data and the transmission rate. After the normalisation of the total amount of data, the delay is inversely proportional to the transmission throughput. Therefore, as long as the transmission rate can be maximised, the delay can be effectively reduced. Then, our optimisation objective is to maximise the throughput of ground user n

(6)

where is an indicator function, representing that node n selects coalition w if , otherwise, does not select w. means that node n can only select one coalition. represents the set of coalition selection strategies for all nodes. represents the transmission throughput of node n.

According to the above modelling of the air-to-ground channel and ground-to-ground channel, we obtained two probability formulas. One is the successful probability of the UAV covering ground node, the other is the successful probability of transmission of ground coalition nodes. Assuming the average data transmission rate is , therefore, for the ground user , is defined as the set of all the nodes that selected coalition w. In other words, , then the throughput of node n is as follows:

(7)

where represents the successful probability of the UAV covering the coalition head . represents the transmission successful probability of the coalition head and the coalition member n. The total throughput of data transmission of coalition w is

(8)

then, the sum of the data throughput of all the ground nodes is deduced as follows:

(9)

According to formula (6), .

4 Hierarchical game and equilibrium analysis

4.1 Hierarchical game framework

The proposed complicated problem involves the UAV position deployment and ground data coalition, where two parts of the optimising process will interact with each other. As for the UAV, the location of the UAV determines the quality of air-to-ground data transmission. It is expected to improve coverage effectiveness by optimising location deployment and the corresponding optimisation problems are as follows:

(10)

It is noted that the coverage range of the UAV is limited. Ground nodes in poor positions will have a limited data connection and the computation offloading may fail. Therefore, motivated by the cooperation mechanism, the ground nodes are no longer in a separate combat state, but form a stable coalition according to the position of the drone, to improve its launch efficiency and thus improve the coverage performance of the UAV. By optimising the position deployment of the UAV, the ground nodes can form a better coalition and improve the data transmission performance of the whole network, i.e.

(11)

However, the UAV is hard to know the coalition formation result in advance, and it is also difficult for ground nodes to obtain the position adjustment strategy of the UAV. To solve the air-ground deployment problem, a hierarchical game model is designed to describe the interaction relationship between the UAV and ground nodes. Game theory is a powerful theoretical tool to model the influence relationships between players in a distributed environment [30], which is promising to be applied in several distributed wireless networks [31–34]. Based on the existing game theories including CFG [11] and Stackelberg game [12], the specific hierarchical framework is introduced as follows.

As illustrated in Fig. 2, the air–ground cooperative model is modelled as a Stackelberg game, where the UAV is the leader and the ground network is the follower. For the time delay optimisation problem of followers (ground nodes), we construct a CFG to analyse the data gathering relationship. We prove that multiple ground nodes can form as stable coalitions namely NE, according to the deployment of the UAV. Moreover, the strategies of the ground coalitions and the UAV can achieve a SE. Thus, the proposed distributed UAV-enabled MEC system can converge the stable results by the self-decision among users and the UAV by the proposed hierarchical game model. Through the joint optimisation of ground and air, the data transmission rate of the whole network is maximised.

4.2 Coalition formation game (CFG)

In most deployment optimisation problems of the UAV, the ground nodes are just covered passively. If one node is in a remote location, the connection between the node and the UAV will usually cut off, which is not conducive to the efficiency of UAV coverage. In other words, if the ground node is in an unfavourable location, the mode that has the direct communication with the UAV is not applicable. To enable more nodes to realise the data offloading requirements, an efficient data collection scheme needs to be designed. Since CFG is widely used in data collection [35], our work makes the ground nodes form coalitions to improve the possibility of communication access. Considering the influence of the UAV position on the transmission quality of the air–ground channel and the coalition formation structure, the integrated optimisation of ground coalition formation and UAV position deployment is carried out. Since the UAV generally has an initial position, we first analyse the coalition formation model based on the known UAV position. To optimise the overall performance of our model, the following section will introduce the features of CFG.

Definition 1 (CFG).A CFG is given by a set of mixed strategies , where represents the preferences set, for each participant , is the preference relation.

Aiming at the problem , namely the throughput maximisation of the ground nodes, we modify the tuple expression of the CFG as . The coalition set represents the strategy space of the ground nodes. represents the utility function, usually written as , represents the coalition selection of all nodes except node n. The local utility function of the ground node n is constructed as follows:

(12)

Given the current position state of the leader UAV, the utility function of the ground node n can be rewritten as

(13)

In the CFG, the coalition partition is expressed as , which partitions all the nodes. is defined as the set of all the nodes that selected coalition w. As is known from Definition 1, preference relationship determines the coalition selection strategy of ground nodes n. How to define the preference relationship is the key to coalition formation. Therefore, based on the preference relationship, we design a coalition formation rule, which can well constrain the coalition selection of ground nodes. Inspired by [35], we adopt coalition order to optimise the global utility . Note that the selection process of coalition head is as follows: when the coalitions form, each member in the same coalition takes turns to be the coalition head. The proposed algorithm calculates the total utility of the coalition, respectively, when different ground nodes are used as the coalition head. The ground node that can maximise the total utility of the coalition is selected as the coalition head.

Definition 2 (coalition order).In CFG, preference relation satisfies coalition order if and only if for the arbitrary participant and the arbitrary two coalition partitions , , the following equation exists:

(14)

where means node n prefers . represents the overall utility of all nodes except n in the coalition. Based on the coalition order, ground nodes select coalition by comparing the total utility of the current coalition w and the expected coalition . Therefore, it can bring the maximum utility to the whole network, which is also shown in the following simulation. Stable property is very important for the distributed game model, which directly determines whether the model can achieve stable results through self-organising decision of the ground nodes. Therefore, it is crucial to prove the stability of the above definition CFG model based on coalition order. Before proving the stability, we introduce the concept of EPG to facilitate the proof process.

Definition 3 (coalition selection mechanism).For ground node , it will choose a new coalition , when this coalition can make node n obtain higher utility, the formula is as follows:

(15)

The above formula stipulates that the ground node selects the coalition by considering the total utility of the initial coalition and the new coalition.

Definition 4 (EPG).With the given position of the UAV , the utility function is , if there is a potential function that changes from any strategy to , the following equation is true:

(16)

Based on [36], the conclusion that one EPG has at least one NE point can be given.

Definition 5 (NE [37]).With the given position of the UAV , a state selection strategy is a pure strategy NE if and only if no player n can improve its utility by changing the state.

(17)

It is noted that the concept of NE is equivalent to the stable coalition partition [38] of the CFG. Therefore, the theoretical proof of the proposed model is given as follows.

Theorem 1.The proposed CFG has at least one stable coalition partition under the coalition order.

Proof.The game model is analysed under the coalition order and introduce the EPG as a theoretical tool. With the given position of the UAV , in this constraint, is a constant. Based on the global utility , we construct a potential function

(18)

which represents the sum of the transmission rates of ground nodes. Assuming that the ground node changes from strategy to , the derivation process of change of potential function is as follows:

(19)

Obviously, according to formulas (13) and (19), the following equation is given:

(20)

According to Definition 3, (20) shows that the current game model is an EPG. Therefore, the CFG model built for exists stable coalition partition under the coalition order. Since the potential function refers to the total throughput of the whole network, the game model still has a stable optimal solution with the given UAV position and coalition order. □

4.3 Stackelberg game model

According to the coalition formation results, the UAV can further adjust the position to improve global service quality. The interaction process is modelled as the Stackelberg game [12]. Stackelberg game model is a typical dynamic multi-stage game model, where the leader has a high priority and its decisions affect the decision-making of followers. Therefore, the UAV is modelled as a leader to perform communication coverage tasks, and ground nodes are modelled as followers. Mathematically, the Stackelberg game can be defined as follows:

(21)

where represents the single drone, and represent the strategic space for ground nodes (followers) and drone (leader), respectively. and are the utility functions of ground nodes and the UAV, respectively. .

Definition 6 ((SE)).A strategy combination is called the SE point of a Stackelberg game if maximises the utility value of the drone and is the best response for all ground nodes. Mathematically, the following conditions are always true for any combination of strategies :

(22)

(23)

where represents the best response strategy selection of node n. represents the best response strategy selection of the ground nodes except for node n.

From the definition of the SE, it is impossible for any participant to gain utility improvement by unilaterally changing his or her strategy. SE is an extension of traditional NE. Solving a Stackelberg game is to find SE.

Theorem 2.The defined Stackelberg game always exists in SE point.

Proof.Firstly, this study analyses the game equilibrium of the lower level. For a given , Stackelberg game degrades to this game: . By analysis, this game model is the CFG model described in the previous section. Therefore, Theorem 1 proves that, given the leader UAV strategy, there must be a stable optimal solution in the follower sub-game. is the optimal dynamic response of all ground nodes with a given UAV position , then SE can be equivalent to the following form:

(24)

therefore, there is always that meets the following conditions:

(25)

The utility function must have an upper bound when the drone has traversed a finite number of position states . Equation (25) indicates that SE always exists in the defined Stackelberg game. □

This section is a joint optimisation for the throughput maximisation of UAV and ground nodes. By constructing a Stackelberg game model with a single leader and multiple followers to describe the interaction relationship between the upper and lower levels. A CFG model based on transmission distance and coalition order is constructed. It is deduced that the model is an EPG and the stable coalition partition in the lower level exist. The mixed strategy analysis of the hierarchical game model proves the existence of the optimal stable position solution of UAV.

5 Algorithm design

In this section, a distributed air–ground integrated deployment algorithm is proposed based on the learning schemes. Compared with the traditional search algorithm, the learning algorithm can significantly improve the optimisation efficiency with diverse strategy sets [21, 37]. Learning algorithms can help the strategy selection avoid falling into the local optimal to achieve a global stable equilibrium. The proposed deployment algorithm is composed of two stages. Specifically, the ground coalition formation model is solved based on the log-linear learning [13]. The SAP [14] is used for the position adjustment of the UAV.

The log-linear learning-based coalition formation is shown in Stage I of Algorithm 1 (see Fig. 3). The proposed coalition formation mechanism focuses on the coalition selection of ground nodes. The coalition selection probability function of the ground node n is expressed as follows:

(26)

where represents the utility value of node n when its coalition selection is . is the learning coefficient. By introducing , the proposed algorithm can make exploration and selection according to the probability, which makes the strategy selection avoid falling into local optimisation. The convergence of the log-linear learning algorithm under the potential game model has been proved in [39]. The conclusion also helps the proposed algorithm in this study to achieve the NE point.

As for the UAV position deployment problem, a SAP [14] is adopted in Stage II of Algorithm 1 (Fig. 3). In each iteration j, only one node is randomly selected to update its selection strategy. This process is repeated until the stopping rule is satisfied. The UAV performs position detection according to the probability function of position selection, i.e.

(27)

where shows the coverage utility of UAV after the iteration j. represents that the position strategy after excluding in the UAV position strategy set . is the learning parameter, reflecting the trade-off between detection and utilisation. A smaller means that the UAV is more likely to choose the current sub-optimal strategy, while a larger means that the UAV is more likely to choose the current strategy that achieves the highest utility. Therefore, to achieve better learning performance, a small value of is set at the beginning of the algorithm iteration and the value of can be incrementally increased as the algorithm iterates.

Overall, the coalition formation of ground nodes is implemented in Stage I. In Stage II, the position deployment of UAV is completed. After performing Stage I, we can obtain the optimal coalition selection according to the coalition selection probability . Then, inputting this result in Stage II, the position deployment of UAV is adjusted. After that, entering the new position into Stage I to form the better coalitions. By iterating, both UAV and ground nodes can reach a stable and optimal solution after two stages of continuous iterations. According to Theorem 2, the process can converge to the solution of the problem.

6 Simulation results and analysis

This section verifies the validity of the proposed model by performing the above algorithm simulation. The distribution of the simulation scenario in detail was randomly generated by Matlab 2016a. In addition, each algorithm is run 600 times and averaged to avoid contingency. The environmental parameters are set in [25, 29]. Aiming at the coverage success probability , the number of antennas is set to 16. The key parameters of the simulation are shown in Table 1.

Table 1. Parameter settings in simulations

Parameter	Description	Value
	the signal-to-noise ratio threshold	2 dB
	the path loss exponent	4
	the node density	0.00003
	the carrier frequency of the UAV	2 GHz
	the transmission power of the UAV	51 dBm
	the minimum detection power of the UAV
	the path loss coefficient	2.5
c	the speed of electromagnetic wave
	the environment constants	11.9, 0.13
	the coefficient of variance	10.39, 0.05
	the coefficient of variance	29.06, 0.03
	the mean of shadow fading	1, 20 dB

As shown in Fig. 4, the square terrain is divided into grids, each grid is 50 m. The UAV is flying at a fixed altitude of 400 m. Fig. 4a shows the initial distribution of the UAV and ground node, the green points are the distribution of ground nodes, the red five-pointed star is the projection of the UAV on the ground. Fig. 4b shows the air–ground joint deployment diagram after performing the proposed algorithm. 14 ground nodes eventually form four coalitions. As can be seen from the figure, affected by the coverage probability, the UAV tends to cover areas with more dense points and the nodes close to the UAV tend to be the coalition header and be responsible for the computing data offloading. In this way, the coverage probability is higher. The data transmission rate obtained by members in the coalition is larger, the time delay is shorter.

To verify the effect of the algorithm on coalition formation in different terrains. The elongated topographic map with grids is constructed, each grid is 50 m, shown in Fig. 5a. The effectiveness of the algorithm can be seen from the coalition structure formed in Fig. 5b. Three coalitions are formed and the UAV implemented the position detection algorithm, which successfully covered the node dense area and obtained the best coverage utility.

To show the superiority of the air–ground joint optimisation method, the proposed deployment algorithm is compared with the other two deployment schemes, respectively, named UAV deployment without coalition formation [15] and UAV deployment without a hierarchical game. The UAV deployment without a coalition formation algorithm does not consider the coalition formation of ground nodes. All ground nodes communicate directly with the UAV. There is no intra-coalition forwarding mechanism. It is to find the best coverage position only through the iteration of the UAV position detection algorithm. In the UAV deployment without a hierarchical game algorithm, the decisions of the upper and lower levels do not iterate with each other. In advance, the ground nodes are divided into several coalition partitions. The coalition partitions do not change with the position of the UAV, which means that the ground nodes do not iterate to form the coalition dynamically according to the position of the UAV. Next, the three algorithms are compared by simulation.

As can be seen from Fig. 6, the total data throughput achieved by the proposed deployment algorithm is far higher than that of the other two deployment schemes and its convergence performance is better than that of the other two deployment schemes. The UAV deployment without a hierarchical game scheme performs a little better than the UAV deployment without a coalition formation scheme. It is noted that even in the initial position, the utility of the proposed algorithm is much higher than the other two deployment schemes, which indirectly reflects the efficiency of the proposed air–ground integrated deployment model. With the continuous position detection of the UAV, the gap in total throughput becomes more and more obvious.

As is shown in Fig. 7, with the increase in the number of nodes, all the algorithms can effectively increase the data throughput of the entire network. The main reason is that the increase in the number of nodes will directly lead to an increase in the total data transmission, which makes the data throughput of the whole network increase accordingly. However, compared with the other two deployment schemes, the proposed algorithm can achieve higher data throughput under the same conditions (at least improve 32.3 and 53.8%, respectively).

The relationship between throughput and network area is also considered with other parameters unchanged. As shown in Fig. 8, when the boundary length of the scenario is small, the designed deployment algorithm can achieve high data throughput. However, when the boundary length of the scene continues to expand, the performance of the proposed algorithm decreases sharply, but it is still much higher than that of the other two deployment schemes. This phenomenon is explained by analysing the characteristics of the channel model. Under the set parameters, when the boundary length increases, the coverage probability of the UAV to the ground node will decrease. The distance between nodes in the ground coalition is also expanding accordingly, which leads to the decrease of transmission success probability. Therefore, on the premise of a fixed number of nodes, the increase of boundary length makes the space between ground nodes expands. The distance between the coalition head and the UAV almost exceeds the maximum limit of data transmission, resulting in the overload of the system model.

Next, the convergence performance of the three algorithms is compared. A cumulative distribution function (CDF) graph is chosen to show the statistical convergence times. The maximum number of iterations is set to 100. Since the operation results are similar for the different number of nodes, the CDF graph of the algorithm with a fixed number of 14 nodes and a boundary length of 100 is only considered. To avoid contingency, the position of the UAV and the distribution of 14 nodes are generated randomly. Each algorithm is run 600 times and averaged. As shown in Fig. 9, the proposed algorithm converges at about 45 iterations, while the iterations of the UAV deployment without coalition formation and the UAV deployment without hierarchy game are about 70 and 40, respectively. This is because in the UAV deployment without a coalition formation scheme, the ground nodes directly communicate with the UAV. The UAV needs to coordinate the data throughput obtained by each node, so the position detection is more frequent so that the convergence is slow. On the other hand, in the UAV deployment without a hierarchical game scheme, ground nodes are divided into several coalition partitions in advance. The UAV still only communicates with the coalition head, omitting the coalition formation process of the ground nodes. Therefore, the convergence speed is faster than the proposed algorithm, but it brings a certain performance loss because the initial coalition partition may not be the optimal coalition structure. On the contrary, in the proposed method, since the ground nodes can form the optimal coalition partition for a given UAV position, the UAV only needs to coordinate the utility between various coalition heads, greatly improving the efficiency of position detection.

7 Conclusion

In this study, air–ground joint optimisation was carried out for UAV deployment and user transmission delay for UAV-enabled MEC. Considering the interaction between UAV and ground nodes, a hierarchical game framework was constructed to characterise the air–ground integrated model. A CFG was built to solve the follower (ground nodes) delay optimisation problem. It was proved that it is an EPG and there must be a stable coalition partition. For the leader (UAV) position deployment problem, the mixed strategy analysis was given to prove the SE of the hierarchical game model. According to the designed coalition formation order, a distributed air–ground integrated deployment algorithm based on log-linear learning and SAP was designed. Simulation results showed that the proposed algorithm could achieve higher data throughput, faster convergence than that of the deployment algorithm without coalition formation, and the deployment algorithm without a hierarchy game. This work effectively improved the information transmission efficiency of UAV communication and was of great significance for the location deployment and time delay optimisation for UAV-enabled MEC.