Single- and Multi-Depot Optimization for UAV-Based IoT Data Collection in Neighborhoods

In this paper, we investigate the problem of deploying the minimum number of Unmanned Aerial Vehicles (UAVs) and determining their flying tours to collect data from all Internet of Things (IoT) sensors. We study this problem in a scenario with neighborhoods where a UAV can collect data from an IoT sensor if the distance between them is less than the wireless communication range of the IoT sensor. Since UAVs are powered by batteries with a limited amount of energy, we assume that the total energy consumed during the flying tour of each UAV is bounded by a given budget. We present the Minimum rooted drone Deployment Problem with Neighborhoods (MDPN), which is NP-hard, and propose two approximation algorithms for the single-depot case, where one of them is a bi-criteria approximation algorithm that returns a solution whose tour’s cost is violated by a factor of 1 + ε. Furthermore, we extend these two algorithms to the multi-depot scenario. Finally, we evaluate our algorithms in three different scenarios: the ideal one where the communication range is a circle and the data transfer rate is constant, and two more realistic scenarios where we introduce some degree of irregularity in the communication range and a non-constant rate in data transfer.