Near-Optimal Multi-Delivery Drone Scheduling for Wireless Data Collection

In recent years, drone-based wireless data collection has emerged as a significant research hotspot in the Internet of Things (IoT) field. However, most existing studies primarily focus on dedicated drones, which incur high deployment costs. In contrast, reusing existing delivery drones provides a cost-effective alternative. This paper concerns the problem of scheduling delivery drones during their delivery to enable cost-efficient wireless data collection. Specifically, the problem aims to maximize the data collection amount while subject to the constraints of the drone’s battery capacity and package delivery deadlines. Nevertheless, solving this problem is challenging due to the involvement of three coupled variables: collection task allocation, collection time distribution, and flying path planning. To tackle this challenge, we propose MdSche, a multi-delivery drone scheduling scheme for wireless data collection. Specifically, we first design a time slicing-based data collection time discretization algorithm, which transforms the original problem into a Multi-Drone Scheduling Problem (MDSP) involving two variables. Then, an auxiliary graph construction method is employed to decompose MDSP into multiple independent single-drone scheduling subproblems. Finally, we construct a surrogate function to simplify each subproblem into a collection task allocation problem with only one variable. Theoretical analysis verifies that MdSche achieves an approximation ratio of 1/2(1 − (1/e)^1/4 ) in polynomial time. Extensive trace-based simulations show that, compared to five baseline methods, our approach improves the data collection amount by an average of 69.68%.