Connectivity-Enhanced 3D Deployment Algorithm for Multiple UAVs in Space–Air–Ground Integrated Network

Abstract

The space–air–ground integrated network (SAGIN) can provide extensive access, continuous coverage, and reliable transmission for global applications. In scenarios where terrestrial networks are unavailable or compromised, deploying unmanned aerial vehicles (UAVs) within air network offers wireless access to designated regions. Meanwhile, ensuring the connectivity between UAVs as well as between UAVs and ground users (GUs) is critical for enhancing the quality of service (QoS) in SAGIN. In this paper, we consider the 3D deployment problem of multiple UAVs in SAGIN subject to the UAVs’ connection capacity limit and the UAV network’s robustness, maximizing the coverage of UAVs. Firstly, the horizontal positions of the UAVs at a fixed height are initialized using the k-means algorithm. Subsequently, the connections between the UAVs are established based on constraint conditions, and a fairness connection strategy is employed to establish connections between the UAVs and GUs. Following this, an improved genetic algorithm (IGA) with elite selection, adaptive crossover, and mutation capabilities is proposed to update the horizontal positions of the UAVs, thereby updating the connection relationships. Finally, a height optimization algorithm is proposed to adjust the height of each UAV, completing the 3D deployment of multiple UAVs. Extensive simulations indicate that the proposed algorithm achieves faster deployment and higher coverage under both random and clustered distribution scenarios of GUs, while also enhancing the robustness and load balance of the UAV network.

1. Introduction

As an emerging network architecture, the space–air–ground integrated network (SAGIN) supported by B5G and 6G communication technology aims for larger capacity, wider coverage, and better quality of service (QoS) [1,2]. By integrating satellite systems, airborne platforms, and traditional ground networks across systems, technologies, and applications, the SAGIN enables seamless coverage and reliable transmission for global applications. However, in remote or disaster-affected regions, solely depending on ground networks may fail to ensure reliable wireless services [3,4]. Fortunately, unmanned aerial vehicles (UAVs) can adapt to extreme environments and complex geographical conditions due to their flexible mobility and unique features [5,6]. Their three-dimensional (3D) mobility can significantly improve the line-of-sight (LoS) link probability and QoS for GUs. In particular, the combination of UAVs and low-Earth-orbit (LEO) satellites provides a flexible and efficient solution for network coverage and communication support [7,8,9]. Consequently, UAVs have been extensively employed for communication support and disaster recovery in remote areas, playing a vital role in the broader implementation of SAGIN.

The deployment of UAVs is a primary and crucial issue in UAV applications, and it faces several challenges in real-world environments. On the one hand, the 3D mobility of UAVs enables them to establish more reliable connections with GUs and offers greater flexibility. On the other hand, the characteristics of air-to-ground (A2G) channels are more complicated than terrestrial ones, especially under the influence of non-line-of-sight (NLoS) components [10,11]. Furthermore, a robust UAV network is essential due to potential hostile environments and end-to-end communication demands between GUs across various regions. These challenges become more complex with the increase in the number of UAVs and various environments.

In recent years, unlike earlier research focused on the 2D deployment of a single UAV [12,13,14,15], the 3D deployment of multiple UAVs has been extensively studied across various environments. These studies focus on several key objectives, such as minimizing the number of UAVs, maximizing coverage, and optimizing the number of GUs served during deployment [16,17]. The optimization problem of deploying multiple UAVs is clearly more challenging. To simplify the problem, some studies within the existing literature have considered UAV-assisted networks under the assumption of guaranteed LoS connections [18], which may lead to coverage vulnerabilities. Moreover, in UAV deployment, complex mathematical relationships exist between the coverage capacity, service time, and service radius of UAVs. Accurately capturing these relationships is crucial for effective deployment, and several studies have focused on clarifying these connections. The impact of UAV deployment height and path loss compensation factor on UAV coverage performance is discussed in [19]. Circular packing theory is utilized in [20] to investigate UAV deployment, offering insights into the relationship between coverage and service time. In [21], the maximum service radius for each UAV is determined by considering the service capabilities of UAVs and the QoS requirements of GUs. Additionally, heuristic algorithms are widely recognized for their effectiveness in addressing the 3D deployment challenges of UAVs. In [22], the exhaustive search method and particle swarm optimization (PSO) algorithm are applied to optimize the available bandwidth of UAVs, aiming to maximize the number of served GUs and improve coverage. The greedy search algorithm proposed in [23] ensured the robustness of UAV networks and minimized the number of UAVs. However, the algorithm did not account for the height optimization of UAVs. In [24,25], the classical particle swarm optimization algorithm is used to optimize the deployment height of multiple UAVs. In [26], the SGA is introduced to optimize the 3D position of UAVs, with a focus on maximizing coverage while considering different QoS requirements of GUs. However, SGA is prone to premature convergence. Therefore, an IGA is proposed in [27] to solve the deployment problem of multiple UAVs at fixed heights and ensure connectivity between UAVs.

However, most existing studies have focused on the connection between GUs and UAVs, with limited attention to the connectivity and robustness among multiple UAVs in 3D scenarios. In fact, dual connectivity and a robust UAV network can enhance the stability of satellite links, ensuring continuous high-quality data transmission in complex or dynamic environments. This is essential for providing on-demand coverage to GUs in different regions. Additionally, each UAV may show service preference under fixed capacity due to channel conditions. Further research is needed to ensure the load balance among UAVs. Motivated by these challenges, we propose a 3D deployment algorithm that comprehensively considers connectivity between UAVs, QoS guarantees for GUs, and load balance, aiming to maximize the coverage of a finite number of UAVs to GUs. The main contributions of this paper are summarized as follows:

• The 3D deployment problem of multiple UAVs in SAGIN is divided into horizontal and vertical deployment problems. The coverage performance of UAVs under a determined path loss and the optimal deployment elevation angle are both discussed. Considering the limitations in current research, the objective of maximizing GU coverage is formulated as an optimization problem.

• We propose an improved genetic algorithm (IGA) and a height optimization algorithm to determine the optimal horizontal positions and heights of UAVs, respectively. The coverage of UAVs is maximized while ensuring the QoS and load balance for GUs. Additionally, the connectivity of the UAV network is ensured to maintain robustness.

• To ensure the performance of the 3D deployment algorithm, the k-means algorithm is employed to initialize the horizontal positions of multiple UAVs, which are then used as inputs for the improved genetic algorithm (IGA). A strategy based on elitist selection and adaptive crossover mutation is proposed to prevent premature convergence in the standard genetic algorithm (SGA).

• We evaluate the algorithm’s performance in different scenarios to ensure its adaptability. Simulation results show that compared with other deployment schemes, the proposed 3D deployment algorithm achieves higher coverage. Moreover, it significantly enhances the robustness of the UAV network and achieves better load balance performance.

The remainder of this paper is organized as follows. In Section 2, we introduce the system model, discussing the relationship between path loss, UAV coverage radius, and deployment altitude, and propose a multi-UAV coverage maximization problem considering practical constraints. Section 3 provides a detailed explanation of the proposed UAV deployment scheme. In Section 4, we design and present experiments that demonstrate the superiority of the proposed 3D deployment algorithm. Finally, Section 5 concludes this paper.

2. System Model and Problem Formulation

2.1. System Model

As shown in Figure 1, multiple UAVs cooperate with LEO satellites to provide wireless services to GUs after natural disasters. Each UAV is equipped with an identical omnidirectional antenna. $\mathcal{N}=\left\{1,2,3···N\right\}$ and $\mathcal{M}=\left\{1,2,3···M\right\}$ denote the sets of GUs and UAVs, respectively. The GUs are distributed in a 2D rectangular area, and $n_k=\left[x_k,y_k\right],k\in \mathcal{N}$ denotes the initial position of GU k. The position of each UAV $i\in \mathcal{M}$ is represented by $m_i=[x_i,y_i,h_i]$. For each cluster of GUs served by one UAV, orthogonal frequency division multiple access (OFDMA) is employed to avoid the interference. Additionally, each GU has a maximum tolerance path loss to ensure effective communication from it.

2.2. Channel Model

Figure 1 shows two types of wireless channels: one is the air-to-air (A2A) channel between UAVs, and the other is the air-to-ground (A2G) channel between UAVs and GUs. Since UAVs are deployed at a certain height, multipath effects from the ground can be ignored. The channels between UAVs are mainly dominated by the LoS component, so the path loss between UAV i and j is modeled as free-space propagation loss (FSPL):

(1)$P{L}_{\mathrm{LoS}}^{i,j}=20\log d_{i,j}+20\log f_c+20\log (4\pi /c),$

where $d_{i,j}$ is the distance between UAV i and j, $f_c$ is the carrier frequency between UAVs, and c is the speed of light.

The A2G model in [28] is employed to describe the channel coefficients between UAVs and GUs, where both the LoS and NLoS components are jointly considered with their corresponding occurrence probabilities. The probability of LoS link occurrence can be calculated by

(2)$P_{\mathrm{LoS}}={\displaystyle \frac{1}{1+aexp\left(-b\left({\theta }_{i,k}-a\right)\right)}},$

where a and b are modeling parameters related to the environments (urban, suburban, dense urban, etc.). Then, the probability of the NLoS link occurrence can be expressed as

(3)$P_{\mathrm{NLoS}}=1-P_{\mathrm{LoS}},$

${\theta }_{i,k}$ denotes the elevation angle between the UAV i and GU k, which can be represented by

(4)${\theta }_{i,k}={\displaystyle \frac{180}{\pi }}{tan}^{-1}\left({\displaystyle \frac{h_i}{R_{i,k}}}\right),$

where $h_i$ is the height of UAV i, and $R_i{,}_k$ is the horizontal Euclidean distance between UAV i and GU k; thus, the path loss between UAV i and GU k can be expressed as

(5)$P{L}_{i,k}=P_{\mathrm{LoS}}\times P{L}_{\mathrm{LoS}}^{i,k}+P_{\mathrm{NLoS}}\times P{L}_{\mathrm{NLoS}}^{i,k},$

where

(6)$\begin{array}{c}P{L}_{\mathrm{LoS}}^{i,k}=20\log d_{i,k}+20\log f_c+20\log (4\pi /c)+{\eta }_{\mathrm{LoS}},\hfill \\ P{L}_{\mathrm{NLoS}}^{i,k}=20\log d_{i,k}+20\log f_c+20\log (4\pi /c)+{\eta }_{\mathrm{NLoS}},\hfill \end{array}$

$d_{i,k}=\sqrt{{h_i}^2+{R_{i,k}}^2}$ is the distance between UAV i and GU k. ${\eta }_{\mathrm{LoS}}$ and ${\eta }_{\mathrm{NLoS}}$ are the average additional path losses to the FSPL under LoS and NLoS.

According to Equations (5) and (6), path loss can be written as

(7)$P{L}_{i,k}={\displaystyle \frac{A}{1+aexp\left(-b\left(\frac{180}{\pi }{tan}^{-1}\left(\frac{h_i}{R_{i,k}}\right)-a\right)\right)}}+20\log {\displaystyle \frac{R_i}{cos\left(\frac{180}{\pi }{tan}^{-1}\left(\frac{h_i}{R_{i,k}}\right)\right)}}+B,$

where $A={\eta }_{\mathrm{LoS}}-{\eta }_{\mathrm{NLoS}}$ and $B=20\log \left({\displaystyle \frac{4\pi f_c}{c}}\right)+{\eta }_{\mathrm{NLoS}}$, respectively. Figure 2 shows the relationship among path loss between UAVs and GUs, UAV deployment height, and coverage radius in urban environments. An optimal elevation angle and maximum radius exist under the condition of fixed path loss. The optimal elevation can be obtained by [29]

(8)${\displaystyle \frac{\pi }{9\ln \left(10\right)}}tan{\theta }_{opt}+{\displaystyle \frac{abAexp(-b(\frac{180}{\pi }{\theta }_{opt}-a))}{{(aexp(-b(\frac{180}{\pi }{\theta }_{opt}-a))+1)}^2}}=0.$

Equation (8) shows that the optimal elevation angle is solely determined by the environmental factors a and b. Once the values of a and b are determined, the optimal elevation angle ${\theta }_{opt}$ becomes fixed. Given a specific path loss, each UAV achieves its maximum coverage radius when deployed at the optimal elevation angle, allowing it to cover the largest area effectively.

2.3. Problem Formulation

Our goal is to use a fixed number of UAVs to maximize the coverage of GUs. Communication service is provided only when GUs are within the coverage range of UAVs and have established connections with them [30]. Matrices $\mathbf{\gamma }={\left[{\gamma }_{i,k}\right]}_{M\times N}$ and $\mathbf{u}={\left[u_{i,j}\right]}_{M\times M}$ are defined to represent the connections between the UAVs and GUs, and between UAVs, respectively. Specifically, when UAV i is connected to UAV j, $u_{i,j}=1$; otherwise, $u_{i,j}=0$. Similarly, if GU k is connected to UAV i, ${\gamma }_{i,k}=1$; otherwise, ${\gamma }_{i,k}=0$. Due to geographical conditions and regulatory constraints, the deployment height of each UAV is restricted within a certain range. Additionally, a minimum safe distance must be maintained between UAVs to ensure safe flight. Furthermore, the connectivity of the UAV network and the QoS provided to GUs must also be considered. The resulting optimization problem is formulated in Equation (9):

(9)$\begin{array}{c}max{\displaystyle \sum _{i=1}^M}{\displaystyle \sum _{k=1}^N}{\gamma }_{i,k}\hfill \\ s.t.\begin{array}{c}\left\{\begin{array}{c}C1:\left|\right|m_i-{\gamma }_{i,k}{n}_k\left|\right|\le R_i+D(1-{\gamma }_{i,k}),\hfill \\ C2:{\displaystyle \sum _{i=1}^M}{\displaystyle \sum _{j=1,j\ne i}^M}{u}_{i,j}\ge 2,\hfill \\ C3:{\displaystyle \sum _{k=1}^N}{\gamma }_{i,k}\le {\Lambda }_i^{max},\hfill \\ C4:{\displaystyle \sum _{i=1}^M}{\gamma }_{i,k}\le 1,\hfill \\ C5:R_i\le R_i^{max},\hfill \\ C6:d_{min}\le \left|\right|m_i-m_j\left|\right|\le d_{max},\hfill \\ C7:h_{min}\le h_i\le h_{max},\hfill \end{array}\right.\end{array}\hfill \end{array}$

where ${\Lambda }_i^{max}$ and $R_i^{max}$ are the maximum connection capacity and the maximum coverage radius of UAV i, respectively. $d_{min}$, $d_{max}$, $h_{min}$, and $h_{max}$ represent the minimum safety distance, maximum communication distance, minimum deployment height, and maximum deployment height, respectively. Constant D in constraint C1 is a large value that ensures the constraint is applicable in all conditions. C3 ensures that the maximum connection capacity of each UAV is not exceeded. C4 specifies that each GU can be served by at most one UAV. C5 ensures that GUs are within the coverage radius of the UAVs. C6 and C7 define the flight distance between UAVs and the deployment height of each UAV. The problem defined in Equation (9) is evidently NP-hard. Although SGA is an effective approach for solving complex multi-variable optimization problems, they are prone to premature convergence. To address this issue, we propose an IGA along with a height optimization algorithm to solve the 3D deployment problem of multiple UAVs.

3. Connectivity-Enhanced 3D Deployment Algorithm for UAVs

In this section, we propose a 3D deployment algorithm to address the problem defined in Equation (9). First, the k-means algorithm is employed to initialize the horizontal positions of each UAV at the theoretically optimal deployment height, establishing connections based on relevant constraints. Next, an IGA is proposed to update the positions of the UAVs, aiming to maximize the number of connections with GUs. During this stage, a fairness connection strategy is employed to update the connections between UAVs and GUs, aiming to enhance load balance in UAV networks. Finally, considering the actual coverage radius and optimal elevation angle of each UAV, the proposed height optimization algorithm adjusts the deployment height of each UAV. The detailed process of the proposed 3D deployment algorithm is illustrated in Figure 3.

3.1. Initialization

As shown in Figure 3, the 3D positions of the UAVs are first initialized using the k-means algorithm based on the distribution of GUs. Specifically, the GUs are divided into M clusters, and each UAV is placed at the center of its corresponding cluster [31]. Meanwhile, the maximum coverage radius $R_{max}$ and the corresponding height of each UAV are determined based on the maximum path loss. In this paper, the maximum path loss is set to 98 dB. Then, the connections between UAVs are established based on appropriate distances, ensuring that both C2 and C6 are satisfied. When each UAV satisfies all the above constraints, $flag=1$; otherwise, $flag=0$. The details are provided in Algorithm 1.

Meanwhile, each UAV establishes connections with suitable GUs under constraints C1–C6. Specifically, the UAV disconnects from the farthest GU if the maximum connection capacity is exceeded. When the same GU is located within the coverage areas of multiple UAVs, the general random connection strategy is typically based on distance. For example, in Figure 4a, the distances between the GU and two UAVs are $d_1$ and $d_2$, respectively. When $d_1>d_2$, the GU connects with UAV-2, which can easily cause load imbalance. To address this, we propose a fairness-based connection strategy that considers the remaining connection capacity of UAVs. As shown in Figure 4b, UAV-1 currently covers three GUs and has a larger remaining connection capacity; thus, the GU connects with UAV-1. This strategy effectively ensures load balance among UAVs and enhances service fairness.

Algorithm 1 Establish connections between UAVs.

Input:  $m_i$ Output:  $flag$ For  $i,j\in M$  do              Calculate $d_{i,j}$              If $d_{min}\le d_{i,j}\le d_{max}$ then                     $u_{i,j}=1$              Else                     $u_{i,j}=0$              End if              If $\forall i,\sum u_{i,j}\ge 2$                     $flag=1$              Else                     $flag=0$              End if End for

The specific steps are shown in Algorithm 2.

Algorithm 2 Establish connections between UAVs and GUs.

Input: $m_i$, $n_k$, $R_i^{max}$ Output:  $\mathit{\gamma }$ For  $i\in M,k\in N$  do              Calculate $R_i$.              If $0\le R_i\le R_i^{max}$ then                        ${\gamma }_{i,k}=1$              Else                        ${\gamma }_{i,k}=0$              End if End for For  $i\in M$  do              While $\forall k\in N,\sum {\gamma }_{i,k}\ge 2$ do              Fairness strategy              End while              End for For  $k\in N$  do While  $\forall i\in M,\sum {\gamma }_{i,k}\ge 2$  do              Disconnect from the farthest GU.              End while End for

The initial positions of the 10 UAVs are determined using the k-means algorithm, which efficiently clusters GUs and ensures that UAVs are distributed to minimize initial deployment imbalances. This method provides a structured starting point for UAV placement, facilitating a more effective optimization process. Following this, the proposed IGA is employed to update the horizontal positions of the UAVs. The k-means initialization helps the IGA converge faster and achieve better performance by reducing the search space and providing near-optimal initial solutions.

3.2. Horizontal Optimization

Although SGA has been successfully applied in many fields [32,33], it still encounters challenges such as premature convergence and slow convergence speeds when addressing complex practical problems. As the population evolves, individuals become increasingly similar, leading to evolutionary stagnation and ultimately causing the algorithm to converge to a local optimum. To overcome these issues, this paper proposes an IGA that enhances optimization performance through adaptive crossover and mutation mechanisms. Specifically, if an individual’s fitness in a given generation exceeds the average fitness level, this indicates superior performance. In such cases, the probabilities of crossover and mutation are reduced to preserve the individual’s advantageous genes. Conversely, if an individual’s fitness is below average, the probabilities of crossover and mutation are increased to facilitate its elimination. The proposed adaptive process for crossover and mutation probabilities is as follows:

(10)$\begin{array}{c}\hfill \left\{\begin{array}{c}{P}_{cro}={\displaystyle \frac{f_{max}-f}{f_{max}-f_{ave}}}{P}_{cro}^0,f<f_{ave},\hfill \\ P_{mut}={\displaystyle \frac{f_{max}-f}{f_{max}-f_{ave}}}{P}_{mut}^0,f<f_{ave},\hfill \end{array}\right.\end{array}$

where f, $f_{max}$, and $f_{ave}$ represent the current individual’s fitness value, maximum fitness value, and average fitness value, respectively. $P_{cro}^0$ and $P_{mut}^0$ denote the initial crossover probability and mutation probability, respectively. Additionally, the horizontal position, deployment height, and coverage radius of each UAV are considered genes within a chromosome. The total number of GUs connected by UAVs is treated as the fitness of an individual. Under the proposed IGA, UAVs continuously adjust their horizontal positions to maximize the number of connected GUs. Throughout this process, the connections between UAVs, as well as between UAVs and GUs, are continuously updated.

3.3. Height Optimization

The height optimization algorithm aims to refine the actual deployment height of each UAV. Specifically, due to the influence of GUs‘ distribution, the actual coverage radius of each UAV may not necessarily equal its theoretical maximum coverage radius. Within the coverage area of each UAV, the actual coverage radius is determined by the horizontal distance to the farthest GU. Additionally, subject to aviation regulations, UAVs are permitted to operate within a specified altitude range. Moreover, an adequate distance between UAVs must be maintained to ensure safe flight and communication. The detailed steps of this process are presented in Algorithm 3.

Algorithm 3 Height optimization algorithm.

Input: $m_i$, $n_k$ Output:  $h_i$ For  $i\in M,k\in N$  do              Calculate $l_i$ and $h_i=l_i^{max}·{\theta }_{opt}$.                   While $h_i\ge h_{max}$ do                        $h_i=h_{max}$                   End while                   While $h_i\le h_{min}$ do                        $h_i=h_{min}$                   End while End for

4. Simulation Validations and Discussions

In this section, we simulate the proposed algorithm and evaluate its performance. Considering the diverse distribution of GUs following natural disasters, we examine two scenarios: random and clustered distributions of GUs. A total of 200 GUs are distributed over a 4000 × 4000 m area under both distribution patterns. The detailed simulation parameters are shown in Table 1.

4.1. Deployment Examples

To assess the scalability of the proposed algorithm, the deployment results are demonstrated firstly under two distributions scenarios of GUs. Figure 5, Figure 6, Figure 7 and Figure 8 show the deployment results of the proposed 3D deployment algorithm after 100 iterations under the random and clustered scenarios, respectively. The connections between UAVs and GUs are indicated by blue lines, while the connections among UAVs are indicated by thick green lines. Additionally, each UAV is represented by the red solid triangle.

Figure 5a illustrates the initial positions of 10 UAVs determined by the k-means algorithm, followed by the establishment and iterative updating of UAV connections based on the proposed constraints and algorithm. Figure 5b displays the optimal horizontal positions of the UAVs after iterations, demonstrating that a stable connectivity structure has been established among them. It can be seen that the initial positions of the 10 UAVs generated by the k-means algorithm closely aligned with the optimal positions obtained after iterations. This indicates the necessity of utilizing the k-means algorithm, as it provides a robust starting point for UAV positioning, improving convergence and efficiency in the subsequent optimization steps. Notably, each UAV maintains at least two neighboring connections, ensuring the robustness of the UAV network.

Figure 6 shows the deployment heights of UAVs. As shown in Figure 6a, after implementing the height optimization algorithm, each UAV is deployed at different heights while maintaining connectivity. Figure 6b provides a more detailed illustration of the deployment heights for each UAV, where the bold blue dashed line represents the theoretical optimal deployment height calculated using Equation (8). Due to practical constraints, the actual deployment heights of the UAVs are lower than the optimal values. Specifically, the maximum observed deployment height is 310 m, while the minimum height is 275 m. When the received power at the GU’s end is constant, the height optimization algorithm can reduce path loss, thereby lowering the transmission power of each UAV. This is of practical significance for extending the operational time of UAVs.

Figure 7a illustrates a typical scenario of a clustered distribution of GUs. In this scenario, some clusters are clearly delineated from others, while others are not; GUs within different clusters exhibit varied distribution patterns, with some displaying substantial scatter, others more density, and some following a linear distribution. In the clustered scenario, initializing the UAVs’ positions using the k-means algorithm significantly reduces the complexity of the search process. As shown in Figure 7b, the proposed algorithm also maintains the connectivity and robustness of the UAV network.

Moreover, Figure 8a,b illustrate that in the clustered scenario, there is a noticeable discrepancy between the actual optimal deployment height and the theoretical optimal deployment height of the UAVs. This discrepancy arises due to the UAVs’ potential to simultaneously cover GUs in different clusters.

4.2. Performance Metric Statistics

In this section, we first evaluated the robustness and load balance of the UAV network under the proposed 3D deployment algorithm as these are key performance indicators in UAV deployment. We then designed different deployment schemes and compared their coverage performance and convergence with that of the proposed algorithm to demonstrate its superiority. The metric values represent the average of 200 independent experiments.

4.2.1. Load Balance

Load balance affects the fairness of network service time and resource allocation. In this paper, it is represented by the service fairness of UAVs to GUs. Specifically, the load balance index (LBI) can be expressed as

(11)$\begin{array}{c}\hfill J^F={\displaystyle \frac{{\left({\displaystyle \sum _{i=1}^M}{b}_i\right)}^2}{M{\displaystyle \sum _{i=1}^M}{b}_i^2}},\end{array}$

where $b_i$ is the number of GUs connected with UAV i. $J^F\in \left[1/M,1\right]$, the larger the value of $J^F$, the higher the service fairness of UAVs. Moreover, when each UAV reaches the maximum connection capacity, the service fairness reaches the maximum value of 1. At this time, the UAV network achieves excellent load balance performance.

Figure 9a,b show the LBI of two connection strategies under different GU distribution scenarios, respectively. It can be seen that with the increase in iteration times, the LBI under the fairness connection strategy based on the remaining capacity proposed in this paper increases continuously and finally tends to be stable. Particularly in the clustered distribution scenario, the LBI approaches the theoretical maximum value of 1. Under the fairness connection strategy, the UAV network continuously increases the number of covered GUs while ensuring service fairness, which is conducive to maximizing resources within the UAV network. However, under the random connection strategy, the service preference of each UAV damages the service fairness, ultimately leading to the convergence of the UAV network’s LBI to a lower level.

4.2.2. UAV Network Robustness

We use the average number of neighbor nodes of all UAVs to evaluate the robustness of the UAV network [34]. We denote the number of neighboring UAVs of UAV i at l hops $(l\le M-1)$ as $s_i^l$. Here, we focus on the number of neighbors at one hop and two hops of each UAV. Thus, the robustness index (RI) can be expressed as

(12)$\begin{array}{c}\hfill RI={\displaystyle \frac{1}{2M}}\sum _{i=1}^M(s_i^1+s_i^2),i\in M,\end{array}$

In the existing research on 3D deployment of multiple UAVs, either the connectivity of the UAV network is not considered or its robustness is overlooked. The 3D deployment algorithm proposed in this paper ensures that each UAV maintains at least two neighbors while updating its 3D position to guarantee end-to-end communication. Figure 10a,b illustrate the RI in different GUs distribution scenarios. As shown in Figure 10a, as the number of iterations increases, the RI in the clustered scenario continuously decreases and eventually stabilizes. This occurs because the UAVs gradually disperse under connection constraints to cover more GUs. Meanwhile, due to variations in GUs distribution, the RI of the UAV network in the random scenario shows a different trend as iterations increase, ultimately stabilizing at a lower level than in the clustered scenario. Additionally, compared to the non-robust scheme, the proposed method constructs a more stable UAV network under both distribution scenarios, improving robustness by 55% and 16%, respectively.

4.2.3. Coverage Performance

In this section, we select the standard genetic algorithm (SGA)+k-means-based deployment scheme, particle swarm optimization (PSO)+k-means-based deployment scheme, and the optimal deployment scheme as benchmark schemes in the simulation. In the optimal deployment scheme, UAVs can achieve complete coverage of all GUs.

As shown in Figure 11, with the increasing number of iterations, the UAVs in all three deployment schemes continue to optimize their 3D positions to cover more GUs. However, none of them achieves optimal deployment due to practical constraints. The SGA+k-means-based deployment scheme converges after eight iterations, exhibiting premature convergence and covering only 160 GUs. The PSO+k-means-based scheme achieves a maximum coverage of 168 GUs, with a coverage rate of 84%. In contrast, the deployment scheme proposed in this paper, based on IGA+k-means, utilizes an IGA with an elite strategy, adaptive crossover, and mutation probability. This approach allows for the continuous selection of superior individuals and the adjustment of crossover and mutation probabilities, resulting in the highest GU coverage rate of 98%.

As shown in Figure 12, all three schemes achieve higher coverage rates and faster convergence in the clustered scenario. However, the PSO+k-means scheme exhibits the slowest convergence, requiring 22 iterations to reach a stable solution. The SGA+k-means scheme, while faster, covers the fewest GUs. In contrast, the proposed IGA+k-means scheme achieves the fastest convergence, reaching optimal deployment after just eight iterations, as well as providing full coverage of all GUs. Furthermore, the results demonstrate that deployment in the clustered scenario is easier, whereas more UAVs may be needed to achieve complete coverage in the random scenario. These findings offer valuable insights for post-disaster rescue and communication recovery efforts, where efficient UAV deployment can play a critical role.

Additionally, algorithm complexity is a crucial metric for assessing algorithmic efficiency. In this paper, the minimum number of iterations required to reach convergence serves as the indicator of complexity. To ensure consistency in the comparative analysis, both the SGA and the IGA are configured with the same population size. As shown in Figure 11, the SGA+k-means scheme exhibits the lowest complexity among all schemes evaluated in the random scenario. While the adaptive mutation operations in the proposed IGA+k-means scheme slightly increase its computational demands, they enhance convergence quality, leading to a substantial improvement in GU coverage. It can be seen from Figure 12 that the convergence speed of all three deployment schemes is enhanced in the clustered scenario. Due to the reduction in searching complexity, the proposed IGA+k-means scheme achieves optimal deployment results with a convergence performance comparable to that of the SGA+k-means scheme.

5. Conclusions

In this paper, we propose a 3D deployment algorithm for multiple UAVs in SAGIN aimed at maximizing the coverage rate of GUs while considering the QoS requirements of GUs, the service capabilities of UAVs, and the connectivity and robustness of the UAV network. Simultaneously, we reconstructed SAGIN connectivity in the event of ground network failures or deficiencies. Initially, the 3D deployment problem is decoupled into two sub-problems: horizontal position optimization and height optimization. We then present a deployment scheme based on the IGA and the k-means algorithm to optimize the horizontal position of each UAV. Notably, a fairness connection strategy is employed to update the connections between UAVs and GUs. Subsequently, a height optimization algorithm is proposed to adjust the deployment height of each UAV under practical constraints. Finally, simulation results under different GU distribution scenarios are provided. Compared to benchmark schemes, the proposed 3D deployment algorithm demonstrates superior performance in enhancing the coverage rate of a limited number of UAVs, particularly in improving the robustness and service fairness of the UAV network. This is crucial for providing stable end-to-end services to GUs. In a future work, we will focus on evaluating the impact of deployment strategies on user experience, including latency, data rates, and service continuity, as well as addressing deployment challenges in interference environments.

Author Contributions

Conceptualization, L.Z. and S.G.; methodology, S.G. and L.Z.; software, S.G. and Z.S.; validation, S.G. and Z.S.; formal analysis, S.G.; investigation, L.Z. and S.G.; resources, Z.S.; data curation, S.G.; writing—original draft preparation, S.G.; writing—review and editing, L.Z. and S.G.; supervision, S.L. and S.G.; project administration, Z.S. and K.C.; funding acquisition, L.Z. and Z.S. All authors have read and agreed to the published version of the manuscript.

Institutional Review Board Statement

Not applicable.

Informed Consent Statement

Not applicable.

Data Availability Statement

Data are contained within this article.

Conflicts of Interest

Shaoxiong Guo, Zhiqun Song and Shijie Liang are employed by the 54th Research Institute of China Electronics Technology Group Corporation. The remaining authors declare that this research was conducted in the absence of any commercial or financial relationships that could be construed as potential conflicts of interest.

Abbreviations

The following abbreviations are used in this manuscript:

SAGIN	space–air–ground integrated network
UAV	unmanned aerial vehicle
GU	ground user
QoS	quality of service
LEO	low Earth orbit
SGA	standard genetic algorithm
IGA	improved genetic algorithm
PSO	particle swarm optimization
3D	three dimensional
LoS	line of sight
NLoS	non-line of sight
OFDMA	orthogonal frequency division multiple access
A2A	air to air
A2G	air to ground
FSPL	free-space propagation loss
LBI	load balance index
RI	robustness index

Footnotes

Disclaimer/Publisher’s Note: The statements, opinions and data contained in all publications are solely those of the individual author(s) and contributor(s) and not of MDPI and/or the editor(s). MDPI and/or the editor(s) disclaim responsibility for any injury to people or property resulting from any ideas, methods, instructions or products referred to in the content.

Figures and Table

Figure 1. System model.

Figure 2. Relationship between coverage radius and deployment height under different path loss values.

Figure 3. Process of the 3D deployment algorithm.

Figure 4. Connection strategy between GUs and UAVs.

Figure 5. The initial and optimal horizontal positions of UAVs under a random distribution scenario of GUs.

Figure 6. The optimal heights of UAVs under random distribution scenario of GUs.

Figure 7. The initial and optimal horizontal positions of UAVs under clustered distribution scenario of GUs.

Figure 8. The optimal heights of UAVs under a clustered distribution scenario of GUs.

Figure 9. The load balance index (LBI) in different distribution scenarios of GUs.

Figure 10. The robustness index (RI) of UAV network in different distribution scenarios of GUs.

Figure 11. The coverage performance of different deployment schemes in the random scenario of GUs.

Figure 12. The coverage performance of different deployment schemes in the clustered scenario of GUs.

Table 1

Simulation parameters.

Parameter	Symbol	Value
-	a	9.61
-	b	0.43
maximum path loss	$P{L}_{max}$	98 dB
crossover probability	$P_{cro}^0$	0.3
mutation probability	$P_{mut}^0$	0.1
number of GUs	N	200
number of UAVs	M	10
security distance between UAVs	$d_{min}$	100 m
maximum distance between UAVs	$d_{max}$	1500 m
minimum deployment height of UAVs	$h_{min}$	200 m
maximum deployment height of UAVs	$h_{max}$	800 m
carrier frequency of A2G channel	$f_c$	2G Hz
additional path loss under LoS	${\eta }_{\mathrm{LoS}}$	0.1 dB
additional path loss under NLoS	${\eta }_{\mathrm{NLoS}}$	20 dB
maximum connection capacity per UAV	${\Lambda }_{max}$	25

References

1. Jiang, W.; Han, B.; Habibi, M.A. The road towards 6G: A comprehensive survey. IEEE Open J. Commun. Soc.; 2021; 2, pp. 334-366. [DOI: https://dx.doi.org/10.1109/OJCOMS.2021.3057679]

2. Cui, H.; Zhang, J.; Geng, Y. Space-air-ground integrated network (SAGIN) for 6G: Requirements, architecture and challenges. China Commun.; 2022; 2, pp. 90-108. [DOI: https://dx.doi.org/10.23919/JCC.2022.02.008]

3. Liu, Y.; Dai, H.N.; Wang, Q.; Pandey, O.J.; Fu, Y.; Zhang, N.; Niyato, D.; Lee, C.C. Space-Air-Ground Integrated Networks: Spherical Stochastic Geometry-Based Uplink Connectivity Analysis. IEEE J. Sel. Areas Commun.; 2024; 42, pp. 1387-1402. [DOI: https://dx.doi.org/10.1109/JSAC.2024.3365891]

4. Gu, X.; Zhang, G. A survey on UAV-assisted wireless communications: Recent advances and future trends. Comput. Commun.; 2023; 208, pp. 44-78. [DOI: https://dx.doi.org/10.1016/j.comcom.2023.05.013]

5. Liang, S.; Zhao, H.; Zhou, L.; Wang, Z.; Cao, K.; Wang, J. Joint Resource Scheduling of the Time Slot, Power, and Main Lobe Direction in Directional UAV Ad Hoc Networks: A Multi-Agent Deep Reinforcement Learning Approach. Drones; 2024; 8, 478. [DOI: https://dx.doi.org/10.3390/drones8090478]

6. Zhou, L.; Deng, X.; Wang, X.; Li, T.; Yi, L.; Xiong, X.; Tolba, A.; Ning, Z. Data Intelligence for UAV-Assisted Road Inspection in Post-Disaster Scenarios. IEEE Internet Things J.; 2024; Early Access

7. Lin, Y.; Wang, T.; Wang, S. UAV-assisted emergency communications: An extended multi-armed bandit perspective. IEEE Commun. Lett.; 2019; 23, pp. 938-941. [DOI: https://dx.doi.org/10.1109/LCOMM.2019.2906194]

8. Hu, Z.; Zeng, F.; Xiao, Z.; Fu, B.; Jiang, H.; Xiong, H.; Zhu, Y.; Alazab, M. Joint resources allocation and 3D trajectory optimization for UAV-enabled space-air-ground integrated networks. IEEE Trans. Veh. Technol.; 2023; 72, pp. 14214-14229. [DOI: https://dx.doi.org/10.1109/TVT.2023.3244812]

9. Karavolos, M.; Tsipi, L.; Bithas, P.S.; Vouyioukas, D.; Mathiopoulos, P.T. Satellite aerial terrestrial hybrid NOMA scheme in 6G networks: An unsupervised learning approach. Proceedings of the 2022 1st International Conference on 6G Networking (6GNet); Paris, France, 6–8 July 2022; pp. 1-5.

10. Elnabty, I.A.; Fahmy, Y.; Kafafy, M. A survey on UAV placement optimization for UAV-assisted communication in 5G and beyond networks. Phys. Commun.; 2022; 51, 101564. [DOI: https://dx.doi.org/10.1016/j.phycom.2021.101564]

11. Zhou, L.; Mao, H.; Deng, X.; Zhang, J.; Zhao, H.; Wei, J. Real-Time Radio Map Construction and Distribution for UAV-Assisted Mobile Edge Computing Networks. IEEE Internet Things J.; 2024; 11, pp. 21337-21346. [DOI: https://dx.doi.org/10.1109/JIOT.2024.3378217]

12. Lai, C.C.; Chen, C.T.; Wang, L.C. On-demand density-aware UAV base station 3D placement for arbitrarily distributed users with guaranteed data rates. IEEE Wirel. Commun. Lett.; 2019; 8, pp. 913-916. [DOI: https://dx.doi.org/10.1109/LWC.2019.2899599]

13. Chen, Y.; Li, N.; Wang, C. A 3D placement of unmanned aerial vehicle base station based on multi-population genetic algorithm for maximizing users with different QoS requirements. Proceedings of the 2018 IEEE 18th International Conference on Communication Technology (ICCT); Chongqing, China, 8–11 October 2018; pp. 913-916.

14. Zhou, F.; Wu, Y.; Hu, R.Q.; Qian, Y. Computation rate maximization in UAV-enabled wireless-powered mobile-edge computing systems. IEEE J. Sel. Areas Commun.; 2018; 36, pp. 1927-1941. [DOI: https://dx.doi.org/10.1109/JSAC.2018.2864426]

15. Wu, H.; Wei, Z.; Hou, Y.; Zhang, N.; Tao, X. Cell-edge user offloading via flying UAV in non-uniform heterogeneous cellular networks. IEEE Trans. Wirel. Commun.; 2020; 19, pp. 2411-2426. [DOI: https://dx.doi.org/10.1109/TWC.2020.2964656]

16. Han, S.I. Survey on UAV deployment and trajectory in wireless communication networks: Applications and challenges. Information; 2022; 13, 389. [DOI: https://dx.doi.org/10.3390/info13080389]

17. Liao, Z.; Ma, Y.; Huang, J.; Wang, J. Energy-aware 3D-deployment of UAV for IoV with highway interchange. IEEE Trans. Commun.; 2022; 71, pp. 1536-1548. [DOI: https://dx.doi.org/10.1109/TCOMM.2022.3232512]

18. Song, M.; Huo, Y.; Liang, Z. Air-to-ground large-scale channel characterization by ray tracing. IEEE Access; 2022; 10, pp. 125930-125941. [DOI: https://dx.doi.org/10.1109/ACCESS.2022.3224776]

19. Shakoor, S.; Kaleem, Z.; Do, D.T. Joint optimization of UAV 3-D placement and path-loss factor for energy-efficient maximal coverage. IEEE Internet Things J.; 2020; 8, pp. 9776-9786. [DOI: https://dx.doi.org/10.1109/JIOT.2020.3019065]

20. Lyu, J.; Zeng, Y.; Zhang, R. Placement optimization of UAV-mounted mobile base stations. IEEE Commun. Lett.; 2016; 21, pp. 604-607. [DOI: https://dx.doi.org/10.1109/LCOMM.2016.2633248]

21. Zhang, C.; Zhang, L.; Zhu, L. 3D deployment of multiple UAV-mounted base stations for UAV communications. IEEE Trans. Commun.; 2021; 69, pp. 2473-2488. [DOI: https://dx.doi.org/10.1109/TCOMM.2021.3049387]

22. Hayajneh, K.F.; Bani-Hani, K.; Shakhatreh, H. 3D deployment of unmanned aerial vehicle-base station assisting ground-base station. Wirel. Commun. Mob. Comput.; 2021; 2021, 2937224. [DOI: https://dx.doi.org/10.1155/2021/2937224]

23. Wang, H.; Zhao, H.; Wu, W. Deployment algorithms of flying base stations: 5G and beyond with UAVs. IEEE Internet Things J.; 2019; 6, pp. 10009-10027. [DOI: https://dx.doi.org/10.1109/JIOT.2019.2935105]

24. Mao, H.; Liu, Y.; Xiao, Z.; Han, Z.; Xia, X.G. Joint resource allocation and 3D deployment for multi-UAV covert communications. IEEE Internet Things J.; 2023; 11, pp. 559-572. [DOI: https://dx.doi.org/10.1109/JIOT.2023.3287838]

25. Wang, L.; Zhang, H.; Guo, S.; Yuan, D. 3D UAV deployment in multi-UAV networks with statistical user position information. IEEE Commun. Lett.; 2022; 26, pp. 1363-1367. [DOI: https://dx.doi.org/10.1109/LCOMM.2022.3161382]

26. Zhong, X.; Huo, Y.; Dong, X. QoS-compliant 3-D deployment optimization strategy for UAV base stations. IEEE Syst. J.; 2020; 15, pp. 1795-1803. [DOI: https://dx.doi.org/10.1109/JSYST.2020.3015428]

27. Wen, X.; Ruan, Y.; Li, Y. Improved genetic algorithm based 3-D deployment of UAVs. J. Commun. Netw.; 2022; 24, pp. 223-231. [DOI: https://dx.doi.org/10.23919/JCN.2022.000014]

28. Al-Hourani, A.; Kandeepan, S.; Lardner, S. Optimal LAP Altitude for Maximum Coverage. IEEE Wirel. Commun. Lett.; 2014; 3, pp. 569-572. [DOI: https://dx.doi.org/10.1109/LWC.2014.2342736]

29. Alzenad, M.; El-Keyi, A.; Lagum, F.; Yanikomeroglu, H. 3-D placement of an unmanned aerial vehicle base station (UAV-BS) for energy-efficient maximal coverage. IEEE Wirel. Commun. Lett.; 2017; 6, pp. 434-437. [DOI: https://dx.doi.org/10.1109/LWC.2017.2700840]

30. Lee, W.; Lee, H.; Choi, H.H. Deep Learning-Based Network-Wide Energy Efficiency Optimization in Ultra-Dense Small Cell Networks. IEEE Trans. Veh. Technol.; 2023; 72, pp. 8244-8249. [DOI: https://dx.doi.org/10.1109/TVT.2023.3237551]

31. Zhang, S.; Shi, S.; Feng, T. Trajectory Planning in UAV Emergency Networks with Potential Underlaying D2D Communication Based on K-means. J. Wirel. Commun. Netw.; 2021; 356, pp. 260-271. [DOI: https://dx.doi.org/10.1186/s13638-021-01987-3]

32. Rajabi, M.H.; Toloie, E.A.; Motadel, M.R. A comprehensive review on meta-heuristic algorithms and their classification with novel approach. J. Appl. Res. Ind. Eng.; 2021; 8, pp. 63-89.

33. Vinod Chandra, S.S.; Anand, H.S. Nature inspired meta heuristic algorithms for optimization problems. Computing; 2022; 104, pp. 251-269.

34. Morone, F.; Makse, H.A. Influence maximization in complex networks through optimal percolation. Nature; 2015; 524, pp. 65-68. [DOI: https://dx.doi.org/10.1038/nature14604]