Design and Analysis of k-Connectivity Restoration Algorithms for Fault-Tolerant Drone Swarms in Harsh Civil Environments
Makaleler > Tam Makale · 2025
Yazarlar: ORHAN CEYLAN, Züleyha AKUSTA DAĞDEVİREN, MOHARRAM CHALLENGER, Orhan DAĞDEVİREN
DRONES, SCI Expanded İndekslerine Giren Dergi, Uluslararası, Wos, 2025, cilt 10, ss 1-24
Özet
Drone swarms are increasingly used in critical civil applications like agriculture, machine maintenance and search-and-rescue, where maintaining network connectivity is essential for effective coordination. However, harsh environmental conditions can lead to drone failures, risking network fragmentation. To improve resilience, designing k-connected networks, where up to k−1 drone failures can be tolerated without losing connectivity, offers a practical solution by providing multiple independent communication paths between drones. The k-connectivity restoration problem is repositioning drones to achieve k-connectivity with minimal movement. In this study, we address this NP-Hard problem and propose novel solutions. Unlike existing k-connectivity restoration algorithms that constrain drones to predefined points, our model allows free repositioning within the mission area, increasing flexibility but also expanding the solution space and complexity. To address this problem, we propose three center-based algorithms that guide drones toward different central points computed from the network layout: in the first algorithm (ORIGIN), the center point is the geometric origin of the mission area; in the second algorithm (CENTROID), nodes move toward the centroid of all drone positions; and in the third algorithm, the center position is defined as the CENTer of the FARthest nodes (CENTFAR). We also introduce a Minimum Spanning Tree-based (MST) algorithm that moves drones along a minimum spanning tree to achieve and theoretically guarantee k-connectivity. Besides checking k-connectivity after each individual move, we also develop group-based variants where all drones move simultaneously and k-connectivity is checked afterward. We conduct comprehensive simulations under varying drone counts, network sizes, k values, and transmission ranges to evaluate the effectiveness and scalability of the proposed algorithms. CENTFAR provides the best movement efficiency among the center-based algorithms, slightly outperforming CENTROID and ORIGIN and achieving up to 21% lower total and 29% lower maximum movement than MST in smaller areas and higher k values. MST, however, performs best under low k and high transmission ranges, offering up to 57% lower total movement and 20% lower execution time than CENTFAR. Group-based variants accelerate convergence (up to a tenfold speedup) at the cost of a slight increase in movement. Our findings reveal that MST is ideal for low-k settings, while CENTFAR is better suited for high-connectivity deployments.