Digital Twin Constructed Spatial Structure for Flexible and Efficient Task Allocation of Drones in Mobile Networks

摘要

Applying the Multiple Drones System (MDS) to perform the repetitive and dangerous tasks for human in many complex environments has become a trend all around the world, due to the increasing capacity of mobile communication and the increasing intelligence of drone robots. However, to fulfill the target with less cost as much as possible, drones need to collaborate deeply with each other to make the optimal decision, which is now important and challenging. In this work, we focus on addressing the efficient task allocation among large-scale drones with the object of minimizing the resource waste and cost, which is proved to be NP-hard. Specifically, we first introduce the Digital Twin (DT) technology to dynamically construct the spatial structure for drones, in which a density clustering based algorithm is proposed to decompose the large-scale task allocation problem among all drones into smaller sub-problems among partial drones. Then, for each sub-problem, we propose an improved auction algorithm to allocate the sub-tasks to local drones according to the task difficulty and drone ability. The experimental results indicate that the proposed method outperforms the state-of-the-art methods in terms of the moving distance, resource utilization and task completion time, etc.