A Novel Deployment Method for UAV-mounted Mobile Base Stations

Unmanned aerial vehicles (UAVs) can serve as mobile base stations (MBSs) to provide wireless communication for ground terminals (GTs). This paper proposes a novel polynomial-time method to place MBSs, in order to minimize the number of MBSs ensuring each GT is within the wireless coverage of at least one MBS. The proposed algorithm transforms the deployment problem of MBSs into a minimum clique partition problem with the minimum enclosing circle coverage constraint. Based on the distance between GTs and the coverage radius of MBSs, the algorithm constructs an undirected graph $G(V,E)$ to denote the adjacent information between GTs. In our algorithm, the GT with the minimum degree is given a higher priority to deploy MBSs, and the location of each MBS will be refined gradually to cover as many as possible GTs. Numerical results show that, in the case where there are no capacity constraints for MBSs, the proposed algorithm performs advantageously over other algorithms in terms of the required number of MBSs as well as runtime overhead. Besides, we also analyze the impact of the capacity constraint of MBSs on the number of required MBSs, and compare the proposed algorithm with the Edge-prior algorithm on the case with the capacity constraint, showing that our algorithm requires fewer MBSs especially when the capacity of MBSs is high.