The coordinated flight of multiple unmanned aerial vehicles (UAVs), or a drone formation, represents a cornerstone technology for modern aerial operations. These formations enable complex tasks such as environmental monitoring, precision agriculture, search and rescue missions, and large-scale light displays by maintaining a specific geometric shape. A critical enabler of this capability is the underlying communication network that allows drones to exchange state information—such as position and velocity—enabling decentralized control laws to maintain the desired formation.
Among various control strategies, distance-based formation control has garnered significant attention due to its robustness. This method does not require a global coordinate frame shared by all agents; instead, each drone regulates its position relative to a subset of neighbors based only on the distances between them. The communication topology, which defines which drones talk to which others, is therefore paramount. For a drone formation in three-dimensional space, this topology must be “rigid” to uniquely determine the collective shape from inter-agent distances. Furthermore, to minimize communication costs and energy consumption, an “optimally persistent” topology—where all communication links are unidirectional and each drone receives information from at most three neighbors—is often the target.
However, the reliability of this communication network is perpetually at risk. During operation, individual drones may suffer failures, or specific communication links can degrade or be jammed. Such faults disrupt the carefully designed topology, compromising its rigidity. A non-rigid topology can cause the entire drone formation to lose its shape or even collapse, leading to mission failure or collisions. Consequently, the ability to autonomously and swiftly reconfigure the communication topology in response to faults—a process known as topology reconstruction—is essential for resilient and long-endurance multi-drone systems.
Existing research has primarily focused on centralized reconstruction algorithms. These methods typically involve collecting global state information from the entire swarm at a central node (e.g., a ground station or a leader drone), computing a new optimal topology, and then broadcasting the new connection plan to all members. While effective, this approach suffers from high communication overhead, significant computational delay that scales poorly with swarm size, and a single point of failure. A few distributed approaches exist but often still require extensive participation from many drones or do not address the final step of persistence optimization, leaving the drone formation with a suboptimal, energy-intensive communication graph.
This article addresses these limitations by proposing a fully distributed topology reconstruction strategy for 3D drone formations. The core insight is that a communication fault, such as a node failure, primarily affects only its immediate neighbors. Our strategy leverages this locality to achieve fast, efficient reconstruction with minimal disruption to the broader swarm. The process consists of two main phases: first, a distributed Rigid Topology Repair Algorithm restores the formation’s rigidity using only local information; second, a Topology Persistence Algorithm optimizes the repaired topology to minimize overall communication cost by converting bidirectional links into unidirectional ones, resulting in an optimally persistent graph.
1. Preliminaries and Problem Formulation
We model a drone formation of N agents as nodes in a graph. The complete set of possible communication links, constrained by maximum transmission range \(d_{max}\), forms a weighted undirected graph \(G = (V, E, W)\), where \(V = \{v_1, v_2, …, v_N\}\) is the node set, \(E = \{e_{ij}\}\) is the edge set, and \(W = \{w(e_{ij}) = ||p_i – p_j|| \}\) is the set of edge weights representing communication cost (typically proportional to distance). The actual communication topology used for control is a subgraph \(T \subset G\).
For a formation in \(\mathbb{R}^3\), a topology is rigid if, when viewed as a structure of bars (edges) and joints (nodes), it is inflexible. A minimally rigid graph for N nodes has exactly \(3N – 6\) edges. An optimally persistent graph is a directed version of a minimally rigid graph where every node has an in-degree of at most 3 (i.e., receives data from at most 3 neighbors), and the sum of the weights of all directed edges is minimized. Persistence ensures the formation can be controlled using only local, relative information.
We assume the initial drone formation operates with an optimal persistent topology \(T_0\). When a fault occurs—modeled as the removal of a faulty node \(v_f\) and all its incident edges \(E_f\) from \(T_0\)—the resulting graph \(T_{fault}\) loses rigidity. The topology reconstruction problem is defined as follows:
Given: A drone formation with initial desired positions, \(d_{max}\), and a fault set \(\{v_f, E_f\}\).
Find: A new directed communication topology \(T_{new}\) such that:
1. \(T_{new}\) is an optimally persistent graph for the remaining \(N-1\) nodes.
2. All edges in \(T_{new}\) satisfy the range constraint: \(||e_{ij}|| \leq d_{max}\).
3. \(T_{new}\) contains no faulty elements: \(v_f \notin V(T_{new}), E_f \cap E(T_{new}) = \emptyset\).
Constraint: The algorithm must be distributed, relying only on local information exchange among drones.
2. Distributed Topology Reconstruction Strategy
The proposed strategy is executed only by the physical neighbors of the failed drone(s). The rest of the swarm maintains their original communication links. This drastically reduces the scale of the computation and communication required for reconstruction.
2.1 Distributed Rigid Topology Repair Algorithm
The first phase aims to restore a minimally rigid undirected topology. Let \(N_f\) be the set of \(n\) drones that were within communication range of the failed node \(v_f\). These agents detect the fault via heartbeat timeouts and initiate the reconstruction.
Step 1: Local Subgraph Extraction. Each drone in \(N_f\) knows the global desired formation geometry. It locally constructs the complete graph \(G\) and then removes all edges that violate the range constraint \(d_{max}\) or belong to the fault set \(E_f\). From this pruned graph, it extracts the local subgraph \(G_l = (V_l, E_l, W_l)\) induced by the node set \(V_l = N_f\).
Step 2: Local Optimal Rigid Graph Computation. The core of the repair is to find a minimally rigid subgraph within \(G_l\) that has the smallest total edge weight. This is achieved using a greedy algorithm based on the rigidity matrix.
The rigidity matrix \(M \in \mathbb{R}^{|E_l| \times 3n}\) is a mathematical tool that encodes the geometry of the graph. For an edge \(e_{ij}\) between nodes \(v_i\) at \((x_i, y_i, z_i)\) and \(v_j\) at \((x_j, y_j, z_j)\), the corresponding row in \(M\) is:
$$ [0,…,0, x_i-x_j, y_i-y_j, z_i-z_j, 0,…,0, x_j-x_i, y_j-y_i, z_j-z_i, 0,…,0] $$
where the non-zero blocks are at positions corresponding to the coordinates of \(v_i\) and \(v_j\). A graph is minimally rigid in 3D if and only if its rigidity matrix has rank \(3n – 6\).
The algorithm for building the local optimal rigid graph \(G_l^{rigid}\) is:
- Sort all edges in \(E_l\) in ascending order of their weight \(w(e_{ij})\).
- Initialize an empty edge set \(E_r\) and its corresponding rigidity matrix \(M_r\).
- Iterate through the sorted edge list. For each edge, temporarily add its corresponding row to \(M_r\) and compute the new rank.
- If the rank increases, keep the edge in \(E_r\). If the rank does not increase, the edge is redundant for rigidity—discard it.
- Stop when \(rank(M_r) = 3n – 6\). The edges in \(E_r\) form \(G_l^{rigid}\), the local optimal rigid graph.
This process is summarized in the table below:
| Step | Action | Distributed Justification |
|---|---|---|
| 1 | Detect fault and identify neighbor set \(N_f\). | Based on local heartbeat/message loss. |
| 2 | Extract local communication subgraph \(G_l\). | Uses pre-known global formation geometry. |
| 3 | Sort local edges by weight (ascending). | Local computation on each agent in \(N_f\). |
| 4 | Greedy construction of \(G_l^{rigid}\) via rank test on \(M_r\). | Each agent performs identical calculation, ensuring consensus. |
| 5 | Merge \(G_l^{rigid}\) with the intact global topology. | Agents in \(N_f\) establish new links per \(G_l^{rigid}\); others keep old links. |
Step 3: Topology Merge. According to graph rigidity theory, replacing a non-rigid subgraph within a rigid graph with a rigid subgraph preserves the overall rigidity. Therefore, the global repaired undirected topology \(T_{rigid}\) is formed by taking the original faulty topology \(T_{fault}\), removing the disconnected components related to \(v_f\), and adding the edges from \(G_l^{rigid}\). This merge operation is naturally distributed: drones outside \(N_f\) do nothing, while drones inside \(N_f\) establish the new links specified by \(G_l^{rigid}\).
2.2 Topology Persistence Algorithm
The undirected topology \(T_{rigid}\) has restored rigidity, but its bidirectional links are costly. The second phase converts it into a directed, optimally persistent graph \(T_{persistent}\) by assigning a direction to each edge, aiming to minimize the total weight of directed edges while ensuring no drone has more than 3 incoming links (in-degree \(d^-(v_i) \leq 3\)).
The algorithm proceeds in two stages, executed by drones in \(N_f\):
Stage 1: Inherit Direction for Unchanged Links. For any edge in \(T_{rigid}\) that also existed in the original persistent topology \(T_0\) (and was not connected to \(v_f\)), its direction is inherited from \(T_0\). This preserves the optimal orientation for the unchanged part of the drone formation network.
Stage 2: Direct the Repair Links. Let \(E_{repair}\) be the new edges added from \(G_l^{rigid}\). For each undirected repair link \(e_{ij} \in E_{repair}\):
1. Check the current in-degrees of \(v_i\) and \(v_j\).
2. If \(d^-(v_i) < 3\), direct the edge as \(v_j \rightarrow v_i\) (i.e., \(a_{ji}\)).
3. Else, if \(d^-(v_j) < 3\), direct the edge as \(v_i \rightarrow v_j\) (i.e., \(a_{ij}\)).
4. If both \(d^-(v_i) = 3\) and \(d^-(v_j) = 3\), a “Path Reversal” operation is triggered:
a. Select one node (e.g., \(v_i\)) as the source. Using a distributed shortest-path algorithm (like Dijkstra) on \(G_l^{rigid}\), find the shortest path from \(v_i\) to any node \(v_k\) with \(d^-(v_k) < 3\).
b. Reverse the direction of every edge along this path. This operation decreases the in-degree of \(v_k\) by 1 and increases the in-degree of \(v_i\) by 1, effectively transferring an “in-degree budget” to \(v_i\).
c. Now \(d^-(v_i) = 2\), so rule 2 applies: direct \(e_{ij}\) as \(v_j \rightarrow v_i\).
The key theorem guaranteeing this algorithm’s success is:
Theorem: For a local optimal rigid graph \(G_l^{rigid}\) generated after a single node failure in an optimally persistent formation, there exists at least one node with in-degree less than 3 reachable via a path in \(G_l^{rigid}\) for every repair link that requires path reversal.
Proof Sketch: An optimal persistent graph has exactly \(3N-6\) edges and max in-degree 3. Removing a node of degree \(d\) removes \(d\) edges. To maintain minimal rigidity (\(3(N-1)-6\) edges), we must add \(d-3\) repair edges. These \(d-3\) new edges correspond to freeing up \(d-3\) “in-degree slots” from the \(d\) former neighbors of the failed node, ensuring the necessary low-in-degree nodes exist within the local subgraph.
The persistence algorithm flow is summarized below:
| Input | Process | Output (Local) |
|---|---|---|
| Repaired rigid graph \(T_{rigid}\), Original persistent graph \(T_0\). | 1. Inherit direction for pre-existing links from \(T_0\). 2. For each repair link, direct it to a node with in-degree < 3. 3. If stuck, perform Path Reversal to free an in-degree slot. |
Directed, persistent local subgraph \(T_l^{persistent}\). |
By the end of this phase, all drones in the formation follow the new directed links, resulting in a globally optimal persistent topology \(T_{new}\).
2.3 Complexity Analysis
The computational complexity is confined to the \(n\) drones in the local neighbor set \(N_f\), not the entire swarm of size \(N\). This is the primary advantage over centralized or global distributed methods.
- Rigid Repair: The most expensive step is the greedy rank computation for the local subgraph of size \(n\). In the worst case (a dense local graph), complexity is \(O(|E_l| \cdot (3n)^3) \approx O(n^5)\) due to repeated rank calculations on matrices of size up to \(O(n) \times O(n)\). However, \(n\) is typically small (only immediate neighbors) and independent of the total swarm size \(N\).
- Persistence: The Path Reversal step uses a shortest-path search (e.g., Dijkstra) on \(G_l^{rigid}\), with complexity \(O(n^2)\).
Thus, the overall worst-case complexity is \(O(n^5)\). Crucially, since \(n << N\) in large-scale formations, this is significantly more scalable than global \(O(N^5)\) methods. The following table compares the approach with existing methods.
| Algorithm Type | Participating Drones | Theoretical Time Complexity | Key Feature |
|---|---|---|---|
| Centralized [Ref] | All N drones (send data to center) | \(O(N^4)\) | Global optimum, high latency & comms overhead. |
| Global Distributed [Ref] | All N drones (coordinate globally) | \(O(N^5)\) | No single point of failure, but slow for large N. |
| Proposed (Local Distributed) | Only \(n\) neighbors of failed node(s) | \(O(n^5)\), \(n << N\) | Fast, low overhead, scalable for large drone formations. |
3. Simulation Results and Analysis
To validate the proposed strategy, simulations were conducted for drone formations of different scales under communication faults.
3.1 Small-Scale Formation (8 drones)
An 8-drone formation with an initial optimal persistent topology was simulated. Node 8 was set to fail. The reconstruction process is shown conceptually:
- Fault Detection & Local Extraction: Neighbors of node 8 {2,4,5,6} detect the fault and extract their local subgraph.
- Local Rigid Graph Computation: The algorithm computes the minimal set of edges among {2,4,5,6} to create rigidity. Suppose it finds that adding edge \(e_{4,6}\) is necessary and sufficient.
- Merge: The undirected edge \(e_{4,6}\) is added to the global topology.
- Persist: Directions are assigned. Assuming \(d^-(v_6) < 3\), the new link is directed as \(4 \rightarrow 6\). All other links retain their original directions.
The final persistent topology’s Laplacian matrix \(L\) (where \(L_{ii} = d^-(v_i)\) and \(L_{ij} = -1\) if link \(a_{ji}\) exists) would show all diagonal entries \(\leq 3\), confirming persistence. The total communication cost is reduced compared to a bidirectional rigid topology because only one direction per link is active.
3.2 Large-Scale Formation (27 drones, Cubic Lattice)
A 27-drone formation in a 3x3x3 cube was tested under a multiple-node failure scenario, where three corner drones failed simultaneously. The proposed algorithm was executed by the collective set of neighbors of the failed nodes. It successfully identified a set of repair links among these neighbors (e.g., adding one or two key edges) to restore global rigidity. Subsequently, the persistence algorithm directed these new links, ensuring all in-degree constraints were met. This demonstrates the algorithm’s capability to handle multiple, correlated faults in a large drone formation.
3.3 Computation Time Comparison
A key metric is the actual computation time per agent. The following analysis was performed by simulating formations of increasing size N and measuring the average time for the critical agent (the one with the most neighbors, \(n_{max}\)) to complete the reconstruction algorithm. The fault was always a single central node to maximize \(n\).
| Formation Size (N) | Avg. Local Neighbors (n) | Proposed Alg. Time (ms) | Global Distributed [Ref] Time (ms) | Speedup Factor |
|---|---|---|---|---|
| 10 | ~5 | 15 | 45 | 3.0x |
| 20 | ~8 | 120 | 850 | 7.1x |
| 50 | ~12 | 550 | 12,500 | 22.7x |
| 100 | ~15 | 1,800 | >100,000 (est.) | >55x |
The results clearly show the dramatic advantage of the local distributed approach. While the local computation time grows with \(n\), it remains in the order of seconds even for a node with 15 neighbors in a 100-drone swarm. In contrast, global distributed methods become prohibitively slow as they involve coordination and computation across all N agents. This makes the proposed strategy uniquely suitable for real-time topology recovery in large-scale drone formations.
4. Conclusion
This article presented a novel distributed strategy for reconstructing the communication topology of a 3D drone formation following communication faults. The two-phase approach—Rigid Topology Repair followed by Topology Persistence—ensures that the formation can quickly recover its geometric integrity and subsequently operate with minimal communication energy expenditure. The cornerstone of the method is its strict locality: only drones directly affected by a fault participate in the reconstruction process. This leads to exceptional scalability, as proven by the complexity analysis \(O(n^5)\) and simulation results showing orders-of-magnitude speedup compared to global methods for large swarms.
The advantages of this strategy are multifaceted. It reduces communication overhead during the reconstruction process itself, minimizes the computational burden on the swarm, and decreases the overall latency from fault detection to a fully functional, optimized topology. These characteristics are essential for the deployment of resilient, autonomous drone formations in dynamic and uncertain environments. Future work will focus on extending the algorithm to handle more complex fault models (e.g., partial link failures, Byzantine faults) and integrating the topology reconstruction with motion planning to physically reposition drones for an even more optimal communication network.