Improved Genetic Algorithm based 3-D deployment of UAVs

I. INTRODUCTION

NOWADAYS, unmanned aerial vehicles (UAVs) have attracted great attention as flying base stations (BSs) to provide flexible connectivity and coverage for ground users [1], [2]. Compared with terrestrial BSs, the high altitude of UAVs enables them to establish more reliable connections with the users due to line-of-sight (LoS) links. Furthermore, with the agility and mobility characteristics, UAVs can provide on-the-fly communications and adapt to the service demands of the users. Considering these two above advantages, UAVs have been widely deployed to restore communication services timely in battlefields or disaster areas, as well as offloading the traffic in hotspot areas such as sport stadiums, outdoor event [3]–[5].

A key design challenge of a UAV-assisted communication network is how to optimally deploy UAVs to satisfy the demands of ground users. Recently, many works have focused on the UAV deployment in a static user scenario where the locations of ground users are fixed. For example, the authors in [6] studied the optimal UAV placement and the user assignment to provide coverage for static users in a disaster area. In [7], the authors determined the optimal deployment of UAVs in the Internet of things infrastructure to maximize the covered users with the minimum number of UAVs. To serve static users in a suburban scenario, the authors in [8] proposed a heuristic algorithm based UAV deployment scheme to minimize the power consumption. Nevertheless, the authors in [6]–[8] all assumed that the UAVs are deployed in a two-dimensional (2-D) plane with a fixed height without considering the relation between the coverage area and the UAVs’ altitude, which may impair the quality-ofservice (QoS) of the covered users or even result in coverage holes. Therefore, many researchers have investigated a threedimensional (3-D) UAV deployment problem, in which the height and horizontal locations of UAVs are coupled. Heuristic algorithms, which can find the optimal solution with lower searching overhead, have been adopted in many studies to tackle this NP-hard problem [9]–[14]. The authors in [9] proposed a UAV-artificial bee colony algorithm to jointly optimize the 2-D locations and flying height of UAVs. With the goal of maximizing the coverage probability, the authors in [10] adopted the particle swarm optimization algorithm to find the optimal 3-D positions of UAVs. In [11], the authors employed standard genetic algorithm (SGA) and simulated annealing (SA) algorithms to determine the optimal number and locations of UAVs simultaneously. The simulation results demonstrate that for a wide coverage area, SGA converges faster than SA and is more likely to settle on a global optimal value. In this regard, the authors in [12] proposed a hybrid genetic algorithm (GA) to provide coverage for ground users with the minimum energy consumption of UAVs. Considering the complexity of 3-D UAV deployment, especially when the number of UAVs is large, the authors in [13] and [14] decoupled the UAV deployment problem from the vertical and horizontal dimensions. Specifically, the multi-population GA and the SGA were respectively adopted in [13] and [14] for the 2-D deployment of UAVs. Note that most of the above works do not take the connectivity of UAV networks into consideration. However, when the environment becomes complex such as uneven distribution of users over a large area or LoS disrupted by obstacles, more UAVs need to be deployed to provide coverage. Herein, the deployed UAVs should keep connected to provide end-to-end communications for far-away ground users, which enables the robustness of the UAV network.

On the other hand, the ground users are generally dynamic in a practical scenario, where the number of users may fluctuate or the locations of the users may change. In this case, the deployed locations of UAVs need to be adjusted to provide effective coverage. To fully reap the benefits of the mobility of UAVs, the authors in [15] predicted the mobile users’ locations in a disaster area and deployed an adaptive UAV network to provide coverage for the users with minimum energy. To improve the accuracy of prediction, a deep Q-network based method was proposed in [16] to adjust the locations of UAVs in response to the mobility of ground users. Both [15] and [16] assumed that the power of UAVs was fixed, to further reduce power consumption, the authors in [17] investigated an adaptive UAV deployment scheme. In this scheme, the UAVs can adaptively change transmit power or relocate to new positions to guarantee the QoS of ground users as the users move. However, the aforementioned works will increase the overhead of resource-restrained UAVs due to the real-time deployment, especially when the users move frequently. To reduce the overhead, the authors in [18] redeployed UAVs periodically to serve the mobile users and proposed a UAV moving strategy to minimize the UAV flying distance. While, the proposed strategy simply traversed all possible flying schemes, which will increase the computation complexity. In addition, the above studies do not consider the connectivity of UAV networks as well.

To tackle the connectivity of the UAV network when deploying UAVs in both static and dynamic user scenarios, we propose an improved genetic algorithm (IGA) based 3-D deployment scheme of UAVs in this paper. In practical UAV deployment, the number of deployed UAVs is one of the most important issues concerned by network suppliers and it directly relates to the deployment cost. Hence, for the static user scenario, we aim to deploy the minimum number of UAVs to cover the ground users in a target area. To conduct the UAV deployment with low complexity, we decouple the 3-D UAV deployment problem from the vertical and horizontal dimensions. Specifically, we firstly analyze the optimal flying height of UAVs based on the air-to-ground (A2G) channel model. Then, we propose an IGA to obtain the optimal UAV locations in a 2-D plane. On this basis, when the users move or increase, i.e., the dynamic user scenario, the already deployed UAVs cannot provide effective coverage. In this case, how to maximize the number of covered users by redeployment of UAVs without increasing the number of deployed UAVs is a difficult problem. To reduce the cost of redeployment, we modify the proposed IGA to obtain a feasible set of UAVs’ 2-D redeployed locations and design a backtracking algorithm (BA) based UAV movement strategy to minimize the total flying distance of the UAVs.The main contributions of this paper are summarized as follows.

We formulate the UAV deployment problem as minimizing the number of UAVs under the coverage constraint. Moreover, we formulate the UAV redeployment problem as maximizing the number of covered users under the number of UAVs constraint. Especially, to maintain the robustness of the UAV network, the connectivity of the UAV network is guaranteed in these two problems.

For the static user scenario, we propose a novel heuristic algorithm, i.e., IGA to solve the decoupled 2-D UAV deployment sub-problem. By introducing the checking and modifying mechanism, the proposed IGA can improve the evolution ability and search efficiency, which can avoid the premature convergence of SGA.

For the dynamic user scenario, considering the number of UAVs constraint, we modify the IGA to obtain a feasible 2-D redeployment of the UAVs. Moreover, to reduce the cost of redeployment, we model the UAV movement problem as an optimal match between the initial deployed and redeployed locations of the UAVs. And we design a BA to obtain the optimal solution that can minimize the total flying distance of the UAVs.

The rest of this paper is organized as follows. We describe the system model in Section II. Then, we propose the IGA based UAV deployment scheme and redeployment in Section III and Section IV, respectively. Simulation results are presented in Section V. Section VI concludes this paper.

II. SYSTEM MODEL

As shown in Fig. 1, we consider a multi-UAV network, where [TeX:] $$\mathrm{UAV}_{i}(i=1,2, \cdots, N)$$ deployed at the same height h provides communication services for randomly distributed ground users [TeX:] $$u_{k}(k=1,2, \cdots, K).$$ Each UAV is mounted by a base station (BS) module equipped with a single omnidirectional antenna, and covers a circular area in ground with the radius of R¹. There are two kinds of channels in the network including the air-to-air (A2A) channel of the UAV-to-UAV link and the A2G channel of the UAV-to-User link.

¹ To be more compatible with the existing networks, in this paper we assume that the BS module mounted on each UAV employs Long Term Evolution technology to provide coverage for ground users.

A. A2A Channel Model

Considering the A2A channels among UAVs are mainly dominated by the LoS component, we model the pathloss

between [TeX:] $$\mathrm{UAV}_{i} \text { and } \mathrm{UAV}_{j}$$ as the free space propagation loss (FSPL), i.e.,

where [TeX:] $$d_{i, j}$$ is the distance between [TeX:] $$\mathrm{UAV}_{i} \text { and } \mathrm{UAV}_{j},$$ [TeX:] $$f_{0}$$ is the carrier frequency of the A2A channel and c is the light speed.

B. A2G Channel Model

In this paper, we adopt the A2G channel model proposed in [19], where the LoS and non-line-of-sight (NLoS) components are jointly considered with their corresponding occurrence probabilities. Therefore, the pathloss between [TeX:] $$\mathrm{UAV}_{i}$$ and [TeX:] $$u_{k}$$ can be given by

In (2), [TeX:] $$\mathbb{P}\left(\operatorname{LoS}, \theta_{i, k}\right)$$ denotes the probability of [TeX:] $$\mathrm{UAV}_{i}$$ having a LoS connection to [TeX:] $$u_{k}$$ at an elevation angle, i.e., [TeX:] $$\theta_{i, k}$$ shown in Fig. 1, which can be expressed as

where a and b are S-curve parameters that depend on the environment. Obviously, the probability of NLoS is [TeX:] $$\mathbb{P}\left(\mathrm{NLoS}, \theta_{i, k}\right)=1-\mathbb{P}\left(\operatorname{LoS}, \theta_{i, k}\right).$$ In addition, [TeX:] $$L_{\mathrm{LoS}}^{i, k}$$ and [TeX:] $$L_{\text {NLoS }}^{i, k}$$ are the average path loss for LoS and NLoS links, respectively, and can be obtained as

where f is the carrier frequency of A2G channel, [TeX:] $$d_{i, k}$$ is the distance between [TeX:] $$\mathrm{UAV}_{i} \text { and } u_{k}, \eta_{\mathrm{LoS}} \text { and } \eta_{\mathrm{NLoS}}$$ are the average additional pathloss for LoS and NLoS, respectively.

By substituting (3) and (4) into (2), we have

where [TeX:] $$A=\eta_{\mathrm{LoS}}-\eta_{\mathrm{NLoS}}, B=20 \log (4 \pi f / c)+\eta_{\mathrm{NLoS}},$$ and [TeX:] $$r_{i, k}=d_{i, k} \cos \left(\theta_{i, k}\right) \text { with } r_{i, k}$$ representing the horizontal distance of [TeX:] $$\mathrm{UAV}_{i}-u_{k}$$ link.

III. IGA BASED MINIMUM COST DEPLOYMENT OF UAVS FOR A STATIC USER SCENARIO

Considering the 3-D characteristics of UAV networks, we propose a 3-D UAV deployment scheme to determine the optimal locations of UAVs. Due to the complexity of solving the deployment problem, in this paper, we decouple the 3-D UAV deployment problem into two subproblems, including the optimal vertical height and the optimal horizontal locations of UAVs. Moreover, we design a heuristic algorithm, i.e., IGA to obtain the horizontal locations of the UAVs under both coverage and connectivity constraints.

A. The Optimal Vertical Height of UAVs

As proved in [20], there exists an optimal height denoted as [TeX:] $$h_{\text {opt }}$$ that corresponds to the maximum coverage region radius denoted as [TeX:] $$R_{\max }$$ and can be obtained by solving

Since [TeX:] $$\frac{\partial \theta}{\partial h}=\frac{\theta}{\partial h} \tan ^{-1}\left(\frac{h}{r}\right)=\frac{r}{h^{2}+r^{2}}>0,$$ then we can obtain [TeX:] $$h_{\text {opt }}$$ by solving [TeX:] $$\frac{\partial R}{\partial \theta}=0,$$ i.e.,

where [TeX:] $$\theta_{\mathrm{opt}}$$ is the derived optimal elevation angle for a given a and b.

Considering the transmit power of [TeX:] $$u_{k}$$ is relatively small, the communication between [TeX:] $$\mathrm{UAV}_{i} \text { and } u_{k}$$ is mainly constrained by the uplink transmission. Thus, [TeX:] $$R_{\max }$$ is determined by the maximum allowable pathloss of the [TeX:] $$u_{k} \rightarrow \mathrm{UAV}_{i}$$ uplink denoted as [TeX:] $$L_{\max }^{i, k},$$ which can by given as

where [TeX:] $$P_{u_{k}}$$ denotes the transmit power of [TeX:] $$u_{k}, G_{\Delta}\left(\Delta=u_{k}, \mathrm{UAV}_{i}\right)$$ denotes antenna gain, and [TeX:] $$L_{c}$$ represents feeder loss. [TeX:] $$P_{\text {sens }} \text { and } \gamma \text { th }$$ are receiver sensitivity and signal-to-noise ratio (SNR) threshold of UAVs, respectively.

By substituting [TeX:] $$\theta_{\mathrm{opt}} \text { and } L_{\max }$$ into (5), we can obtain the maximum [TeX:] $$r_{i, k} \text {, i.e., } R_{\max },$$ then the optimal vertical height of UAVs can be derived as [TeX:] $$h_{\mathrm{opt}}=R_{\max } \tan \left(\theta_{\mathrm{opt}}\right).$$

B. The Optimal Horizontal Locations of UAVs

Based on the obtained optimal height [TeX:] $$h_{\mathrm{opt}},$$ we further determine the 2-D locations of the UAVs on the horizontal plane denoted as [TeX:] $$\mathscr{P} .$$

From the perspective of cost, the UAV deployment goal considered in this paper is to find the optimal 2-D locations of UAVs to minimize the number of UAVs on the premise of guaranteeing both the coverage and connectivity constraints. Specifically, the coverage constraint means that all ground users should be covered. Note that if the user can be served by multiple UAVs, we assume that the user chooses to access the UAV with the best link quality. Besides, the connectivity constraints include three folds: (i) The distance between any two connected UAVs should be no less than a safety distance denoted as [TeX:] $$d_{\mathrm{s}}$$ and also not exceed the maximum communication distance denoted as [TeX:] $$d_{\max }. \cdot(i i)$$ Each UAV needs to connect with at least one other UAV. (iii) There exists at least one route between any two UAVs to ensure the robustness of the UAV network. Thus, the 2-D UAV deployment subproblem can be formulated as

where M represents the deployed UAV set, especially [TeX:] $$|M|$$ denotes the number of deployed UAVs. [TeX:] $$u_{i, k} \text { and } c_{i, j}$$ are Boolean variables denoting the association between [TeX:] $$\mathrm{UAV}_{i} \text { and } u_{k}$$ and the connection between [TeX:] $$\mathrm{UAV}_{i} \text { and } \mathrm{UAV}_{j},$$ respectively. [TeX:] $$\mathbf{c}=\left[c_{i, j}\right]_{|M| \times|M|}$$ is the connection matrix. Also, [TeX:] $$\left(x_{i}, y_{i}\right) \text { and }\left(x_{j}, y_{j}\right)$$ denote the coordinates of [TeX:] $$\mathrm{UAV}_{i}$$ and [TeX:] $$\mathrm{UAV}_{j},$$ respectively. [TeX:] $$\left(X_{\min }, X_{\max }\right) \text { and }\left(Y_{\min }, Y_{\max }\right)$$ denote the bounds of plane [TeX:] $$\mathscr{P} .$$ Specifically, [TeX:] $$u_{i, k}=1$$ means that user k associates with [TeX:] $$\mathrm{UAV}_{i} \text {, i.e., }\left(x_{i}-x_{k}\right)^{2}+\left(y_{i}-y_{k}\right)^{2} \leq R_{\max }^{2}, \forall i, k \text {, otherwise } u_{i, k}=0 \text {. And } c_{i, j}=1$$ means that [TeX:] $$\mathrm{UAV}_{i}$$ is within communication range of [TeX:] $$\operatorname{UAV}_{j},$$ i.e., [TeX:] $$\left(x_{i}-x_{j}\right)^{2}+\left(y_{i}-y_{j}\right)^{2} \leq d_{\max }^{2}, \forall i, j, \text { otherwise, } c_{i, j}=0.$$ For the NP-hard UAV deployment problem shown in (9), the SGA can provide a solution with its advantage of rapid search ability due to the crossover and mutation procedures. However, the SGA has the disadvantage of premature convergence, especially when solving problems with complex constraints. Furthermore, the efficiency of the SGA would reduce when the solution space gets large. Therefore, in this paper, we propose an IGA to solve the UAV deployment problem.

The procedures of the proposed IGA are summarized in Algorithm 1, where our improvements are described as follows. It is worth mentioning that our proposed IGA can converge to the global optimum since the best individual in each iteration has been preserved at step 6 of Algorithm 1 [21].

Firstly, we need to construct chromosomes that can capture the 2-D location of each UAV. Considering the deployed locations of UAVs are continuous in practical scenarios, these locations cannot be coded by chromosomes. Hence, we adopt a high-density grid to discretize [TeX:] $$\mathscr{P},$$ where the center of the grid is the candidate deployed location set of UAVs denoted as S. Moreover, we code the chromosome genes by binary symbols, where 1 and 0 represent whether or not deploying UAV at the corresponding location. Herein, the length of the chromosome is equal to [TeX:] $$|S|.$$

Next, the initial population of the SGA is generated by a random generation process, which may increase the probability of unqualified chromosomes in evolution. To cope with this problem, we design a checking and modifying mechanism for each chromosome of the initial population to guarantee the

generated initial population satisfying the connectivity constraints in (9). Specifically, we establish an association matrix between S and [TeX:] $$u_{k}$$ denoted as [TeX:] $$\mathrm{a}=\left[a_{s, k}\right]_{|S| \times K}, \text { where } a_{s, k}=1$$ means that the UAV deployed at location s can associate with [TeX:] $$u_{k},$$ otherwise [TeX:] $$a_{s, k}=0.$$ Based on the established associated matrix, we randomly select an associated UAV for each user when constructing each chromosome so that all users can be covered. Then, to ensure the connectivity of the UAV network, we check whether there exists a route between any two deployed UAVs. If not, we randomly deploy one UAV in the remaining candidate deployed locations from S for each isolated UAV and construct a route between them by deploying other necessary UAVs around them. Herein, this procedure can be implemented by setting the corresponding genes of the newly added UAVs to 1.

Finally, we introduce the checking and modifying mechanism for the next generation in each iteration. For the connectivity constraints, the difference between the initial population and the generated population is that we should check whether the generated chromosomes satisfy the safety distance constraint (9-e). If not, we randomly delete one of the two unsatisfied UAVs and set the corresponding gene to 0. For the coverage constraints, we check deployed UAVs of each chromosome and then can obtain the uncovered user set according to the association matrix a. If the set is nonempty, we randomly add UAVs which can serve these uncovered users based on a and set the corresponding genes to 1. The designed checking and modifying mechanism turns the chromosomes that do not satisfy the constraints in (9) into the qualified ones. In this way, we can avoid the unqualified chromosomes being eliminated by selection operation so that the diversity of the next generation is improved.

IV. MAXIMUM COVERAGE REDEPLOYMENT OF UAVS FOR A DYNAMIC USER SCENARIO

Based on the 3-D UAV deployment in Section III, we can obtain the optimal vertical height and the horizontal locations of the UAVs that can provide coverage for all static users in the given target area [TeX:] $$\mathscr{P}.$$ However, the already deployed UAVs cannot guarantee effective coverage when the users move or increase. Meanwhile, considering the limited deployment cost, i.e., the number of UAVs, we aim to redeploy the existing UAVs to maximize the covered users while ensuring the connectivity of the UAV network. Specifically, we firstly modify the proposed IGA to determine a feasible set of redeployed 2-D locations of the UAVs. Then, we formulate the UAV movement problem as an optimal match to minimize the total flying distance of the UAVs and design a BA to obtain the optimal solution.

To maximize the covered users, we redeploy the obtained UAVs in Section III on the premise of ensuring the connectivity of the UAV network. Therefore, we can formulate the optimal 2-D UAV redeployment problem as

where [TeX:] $$M_{\mathrm{opt}}$$ represents the optimal deployed UAV set in Section III. Note that for a given new distribution of users, the optimization problem (10) has several feasible solutions, i.e., several feasible sets of UAVs’ redeployed locations. In this paper, we aim to determine a feasible solution of problem (10).

Similar to the deployment problem in (9), the redeployment problem in (10) is also NP-hard, which can be solved by modifying the proposed IGA. The differences between the modified IGA and the initial IGA in Section III are:

In the procedure of initializing the population, the number of redeployed UAVs is limited to [TeX:] $$\left|M_{\mathrm{opt}}\right|$$ obtained by the optimal deployment in Section III, which means that the number of genes “1” on each chromosome is [TeX:] $$\left|M_{\mathrm{opt}}\right|.$$ For each chromosome, we firstly deploy a UAV at an arbitrary location in S and set the corresponding gene to 1. Then, based on the connection metric c, we deploy another UAV at the location that can connect to the deployed UAV and set the corresponding gene to 1. Repeating the above steps until the number of genes “1” on each chromosome reaches[TeX:] $$\left|M_{\mathrm{opt}}\right|.$$

Considering that the goal of UAV redeployment is to maximize the covered users, the fitness value in Algorithm 1 should be replaced by [TeX:] $$f i t=\sum_{i, k} u_{i, k}.$$ Furthermore, we establish a new association matrix between S and the corresponding covered users to directly demonstrate the number of covered users for each chromosome.

Finally, in the process of checking and modifying the next generation in each iteration, the constraints needed to be checked and modified are number and connectivity constraints.

² The receiver sensitivity of UAVs can achieve -70 dBm ~ -90 dBm [23]– [25]. Hence, in this paper, we take 􀀀85 dBm receiver sensitivity as an example to investigate our proposed IGA based UAV deployment and redeployment schemes.

For the number constraint, we need to check whether the generated chromosomes satisfy the number constraint (10-b). If the number of UAVs exceeds [TeX:] $$\left|M_{\mathrm{opt}}\right|,$$ we should randomly discard the excess UAVs and set the corresponding genes to 0. Otherwise, we should add UAVs and set the corresponding genes to 1. For the connectivity constraint, the difference from Algorithm 1 is that we should count the deployed UAVs of each chromosome in modifying process. Once the number of deployed UAVs exceeds [TeX:] $$\left|M_{\mathrm{opt}}\right|,$$ we should discard the remaining UAVs and set the corresponding genes to 0.

Through the modified IGA based UAV redeployment scheme, we can obtain one feasible redeployed UAV set denoted as [TeX:] $$\hat{M}_{\text {opt }}.$$ To further improve the efficiency of UAV movement, we aim to minimize the total flying distance of the UAVs. The optimization problem is formulated as

where [TeX:] $$D_{i, j}$$ represents the updating distance between [TeX:] $$\mathrm{UAV}_{i}$$ in[TeX:] $$M_{\mathrm{opt}} \text { and } \mathrm{UAV}_{j} \text { in } \hat{M}_{\mathrm{opt}} \text {, }$$ which can be calculated as

where [TeX:] $$\left(x_{i}, y_{i}\right) \text { and }\left(\hat{x}_{j}, \hat{y}_{j}\right)$$ denote the coordinates of [TeX:] $$\mathrm{UAV}_{i}$$ and [TeX:] $$\mathrm{UAV}_{j},$$ respectively.

Essentially, the optimization problem in (11) is to find the optimal match between the initial deployed UAV set [TeX:] $$M_{\text {opt }}$$ and the redeployed UAV set [TeX:] $$\hat{M}_{\mathrm{opt}}$$ that can minimize the total flying distance. Considering the solution space of (11) is relatively small, we design a BA to solve this problem. Specifically, we firstly establish a matching matrix [TeX:] $$\mathbf{L}=\left[l_{i, j}\right]$$

where [TeX:] $$l_{i, j}=1$$ denotes that [TeX:] $$\mathrm{UAV}_{i} \text { in } M_{\mathrm{opt}}$$ is paired with [TeX:] $$\mathrm{UAV}_{j} \text { in } \hat{M}_{\mathrm{opt}}.$$ Then, we find all forms of L that only one element in any row or column is 1, which means that each UAV in [TeX:] $$M_{\mathrm{opt}}$$ is only paired with one UAV in [TeX:] $$\hat{M}_{\mathrm{opt}}$$ and cannot be paired repeatedly. It is obvious that each L corresponds to a feasible movement scheme, especially the optimal movement scheme minimizing the total flying distance.

The computation complexity of our proposed UAV redeployment can be divided into two parts, i.e., the computation complexity of the modified IGA and that of the BA. Specifically, the computation complexity of the modified IGA mainly lies in the checking and modifying at step 3 and the evolution process from step 4 to step 18, which need O (P) and O (3IP) operations, respectively. Herein, P denotes the population size and I denotes the maximum iterations. Moreover, the BA needs [TeX:] $$O(|M| !)$$ operations. Hence, the computation complexity of our proposed UAV redeployment is [TeX:] $$O(P+3 I P+|M| !).$$

V. RESULTS AND ANALYSIS

In this Section, we evaluate the proposed IGA based UAV deployment and redeployment schemes in static and dynamic user scenarios, respectively. Moreover, for the dynamic user scenario, the designed BA based UAV movement strategy is also studied. In the simulations, the predetermined system parameters are listed in Table I [22]. From the above analysis in Section II, we can derive the optimal flying height and the corresponding coverage region radius of UAVs are [TeX:] $$\left(h_{\mathrm{opt}}, R_{\max }\right)=(1.8 \mathrm{~km}, 2.5 \mathrm{~km}).$$ And the maximum communication distance of the UAV network is derived as [TeX:] $$d_{\max }=6.4 \mathrm{~km}.$$

We firstly conduct simulations to investigate the proposed IGA based UAV deployment scheme in Fig. 2, where the ground users are randomly distributed in a [TeX:] $$10 \mathrm{~km} \times 10 \mathrm{~km}$$ covered area. Fig. 2 shows the initial candidate UAV locations and the final deployed UAV locations, where the associations between each UAV and the corresponding covered users are

shown in red lines and the connections among the deployed UAVs are shown in green lines. From this figure, we can see that all the ground users can be covered by 7 UAVs and the connectivity of the UAV network is guaranteed.

In Fig. 3, we further compare our proposed IGA based deployment scheme with the SGA based deployment scheme and the best random deployment scheme, where the target area is [TeX:] $$10 \mathrm{~km} \times 10 \mathrm{~km}.$$ Specifically, the SGA based deployment scheme does not include the best individual’s preservation and the checking and modifying mechanism proposed in this paper. Moreover, the best random deployment scheme selects the best deployment scheme corresponding to the least number of UAVs among 1000 random deployment trials. From this figure, we can see that both the SGA based and our proposed IGA based deployment schemes outperform the best random deployment scheme. Moreover, our proposed IGA based deployment scheme deploys fewer UAVs than that of the SGA based deployment scheme. This is because that the IGA based deployment scheme introduces the checking and modifying mechanism for the next generation in each iteration to guarantee the safety distance and connectivity constraints of the UAV network. In this way, large overlapping in coverage of the deployed UAVs can be avoided. In addition, we can observe that the number of UAVs deployed by the SGA based deployment scheme dramatically increases when the number of users reaches 250 indicating that the SGA converges to a local optimum. While our proposed IGA can avoid this premature convergence problem by the introduced best individual’s preservation and checking and modifying mechanism. Whereas, due to the limited coverage area, the number of deployed UAVs will no longer increase as the number of users increases to 350 and above. This is because that the deployed UAVs already can provide seamless coverage for the target area. Moreover, the computation complexity of SGA based and IGA based deployment schemes are O (2IP) and O (P + 3IP), respectively, with I = 100 and P = 1200.

It can be seen that compared with SGA, the proposed IGA has higher computation complexity but can achieve better deployment performance. This is because that our proposed IGA introduces the checking and modifying mechanism. While, the computation complexity of the best random deployment scheme is related to its search space. When the search space is small, e.g., 1000 set in our simulation, its computation complexity is relatively low, but the deployment result is not optimal. However, it is difficult to determine the best search space of the best random deployment scheme to obtain the optimal deployment result due to its inherent randomness. Hence, considering the non-optimal deployment result of the best random deployment scheme, it is meaningless to compare its computation complexity with that of SGA and IGA based deployment schemes.

Then, we plot feasible IGA based UAV redeployment schemes and the corresponding BA based movement strategies for the UAVs when users change in Figs. 4 and 5. In Fig. 4, the locations of the users change slightly and the number of

the users increases to 300. Note that the coverage of each initial deployed and redeployed UAV is depicted in black and red circles, respectively. We can observe that the initial deployed UAVs cannot provide coverage for all users. While our designed redeployment scheme can cover all the users. Moreover, the optimal movement strategy of the UAVs is shown in gray lines with the corresponding minimum total flying distance and the longest flying distance being 3:8 km and 1.1 km, respectively.

As shown in Fig. 5, the target area expands to [TeX:] $$12 \mathrm{~km} \times$$ 12 km as the users move dramatically and the number of the users increases to 500. From this figure, we can see that there still exist uncovered users after redeployment. In this situation, the maximum number of covered users increases from 399 to 448 and the coverage rate increases from 79:8% to 89:6%. It is obvious that more UAVs should be deployed to serve uncovered users. Similarly, the optimal movement strategy for the UAVs is shown in gray lines with the corresponding minimum total flying distance is 8.5 km and the longest flying distance being 3.8 km and 2.1 km, respectively.

To verify the effectiveness of our proposed IGA, we plot the fitness values for both deployment and redeployment schemes versus the number of iterations in Fig. 6. Note that the fitness value depends on the number of UAVs and the number of covered users for the deployment scheme and the redeployment scheme, respectively. We can observe that the curves of the fitness values for both these two schemes converge after several iterations. This phenomenon indicates that after the evolution process, both the number of deployed UAVs for the deployment scheme and the number of covered users for the redeployment scheme eventually reach stability, which means that these two schemes converge to the optimum. Moreover, as the number of users increases, the search space of IGA becomes larger resulting in a slower convergence.

VI. CONCLUSIONS

In this paper, we have investigated the UAV deployment and redeployment problems in static and dynamic user scenarios, respectively. In both problems, the connectivity of the UAV network is guaranteed for robustness. Specifically, for the static user scenario, we have decoupled the UAV 3-D deployment problem into optimal vertical height and 2-D deployment subproblems. In view of deployment cost, we have formulated the UAV 2-D deployment to minimize the number of UAVs and propose a heuristic algorithm, i.e., IGA to solve this NPhard problem. Compared with the SGA, our proposed IGA can effectively improve the evolution ability and search efficiency by introducing the checking and modifying mechanism. For the dynamic user scenario, taking the limited deployment cost into account, we have modified the proposed IGA to determine a feasible set of 2-D redeployed locations of the UAVs that can maximize the covered users while guaranteeing the connectivity of the UAV network. Moreover, to reduce the cost of redeployment, we design a BA based UAV movement strategy to minimize the total flying distance of the UAVs. Simulation results have validated the effectiveness of our proposed UAV deployment and redeployment schemes.