3D urban UAV relay placement: Linear complexity algorithm and analysis

Optimal unmanned aerial vehicle (UAV) placement in a 3-dimensional (3D) space to build a connection between a base station (BS) and a ground user is studied herein. A key challenge is to avoid signal propagation blockage due to obstacles. Much prior work uses probabilistic terrain models with model parameters learned from the statistics over a large area, and therefore, the optimization for a specific user in a small local area is poor. In contrast, this paper seeks the optimal UAV position over actual and fine-grained terrain, and develops efficient UAV positioning strategy adaptive to the degree of location-dependent line-of-sight (LOS) condition measured on the fly. It is proven that the globally optimal UAV position in 3D can be determined from the proposed search trajectory which has merely linear length in the diameter of the target area. Therefore, the proposed strategy can be practically implemented. Numerical experiments are performed over a real-world urban topology and demonstrate superior performance gain over existing strategies based on probabilistic models.