Planning while flying: A measurement-aided dynamic planning of drone small cells

The deployment of drone small cells has emerged as a promising solution to agile provisioning of Internet backbone access for Internet of Things devices, and many other types of users/devices. In this paper, we consider the problem of deploying a set of drone cells operating on multiple channels in a target area to provide access to the backbone/core network, which is formulated as a combinatorial network utility maximization problem. Since an offline and centralized solution to such a problem is not feasible, a low-complexity and distributed online algorithm is highly desired. Therefore, we propose a measurement-aided dynamic planning (MAD-P) algorithm, where the dispatched drones perform position and channel configurations autonomously on the fly based on the real-time measurement of network throughput to solve the problem in a distributed fashion during flight with minimal centralized control. We prove that the proposed MAD-P algorithm is asymptotically optimal, and investigate how long it takes for the convergence to stationarity under the MAD-P algorithm by giving a mixing time analysis. We also derive an upper bound of the performance gap in presence of measurement errors. Simulation results are provided to validate our analytic results and demonstrate the effectiveness of our algorithm.