Improved genetic algorithm based 3-D deployment of UAVs

Unmanned aerial vehicles (UAVs) are widely used as aerial base stations (BSs) to provide flexible connectivity and coverage for ground users in various scenarios such as disaster relief, traffic offloading, and so on. Especially, UAV deployment is an important issue that directly affects the coverage performance of the UAV network. In this paper, we propose a novel heuristic algorithm based three-dimensional (3-D) UAV deployment scheme while guaranteeing the connectivity of the UAV network in both static and dynamic user scenarios. For the static user scenario, we aim to deploy the minimum number of UAVs to provide coverage for the users from the perspective of deployment cost. To reduce the deployment complexity, we decouple the 3-D UAV deployment problem from the vertical and horizontal dimensions. Specifically, we firstly determine the optimal vertical height of UAVs based on the air-to-ground (A2G) model. Then, to alleviate the premature convergence of standard genetic algorithm (SGA), we design an improved genetic algorithm (IGA) to obtain the optimal horizontal locations of UAVs. On this basis, when the users move or increase, i.e., the dynamic user scenario, the already deployed UAVs cannot provide effective coverage. For this scenario, we propose a UAV redeployment scheme to maximize the number of covered users without increasing the number of UAVs. To further reduce the cost of redeployment, we firstly modify the proposed IGA to obtain a feasible set of two-dimensional (2-D) redeployed locations of the UAVs. Then, we design a backtracking algorithm (BA) based UAV movement strategy to minimize the total flying distance of the UAVs. The simulation results show that the effectiveness and convergence of our proposed schemes.