Ensuring Continuous Connected Movement for a Swarm of Relocating Drones

Collaboration among drone swarms in various applications often requires dynamic data exchange to optimize their missions. When employing device-to-device (D2D) communications, drones must form connected topologies enabling multi-hop communication. Maintaining a connected topology during their movement to new locations is a major challenge that has not been tackled in the literature. In this paper, we first formalize this problem, proving the decision version is NP-Hard, and break it into sub-problems, detailing their complexity under certain constraints. We then propose polynomial time solutions to these subproblems. Our proposed approach first makes a location assignment for each drone to determine where to move as their next locations. Next, our approach relocates each drone to their designated target location without losing in-network connectivity of the drone topology. We achieve this by leveraging a two-step approach: contraction and re-expansion. In the contraction phase, drones converge towards a specific location, reducing network diameter and increasing connectivity. In the expansion phase, drones disperse to their new target positions. Mathematical proofs and extensive simulations validate our method’s effectiveness in maintaining connectivity during drone relocations.