The era of ubiquitous connectivity and intelligent systems has ushered in a new wave of technological advancements, with Unmanned Aerial Vehicles (UAVs) emerging as a cornerstone of integrated air-space-ground strategies. Among the most captivating applications is the formation drone light show, where a swarm of UAVs operates in tight coordination to create complex, dynamic aerial displays. Beyond entertainment, such coordinated formations are vital for missions like disaster response, surveillance, precision agriculture, and establishing temporary communication networks. These applications rely fundamentally on reliable and efficient multi-hop communication within the UAV fleet, forming what is known as a Flying Ad-Hoc Network (FANET). A formation drone light show is a specific and highly demanding type of FANET.
However, the unique characteristics of UAV formations—such as high and variable mobility, limited onboard energy, and the frequent breakage of communication links—pose significant challenges to maintaining reliable data routing. The network topology is highly dynamic and time-varying. Traditional mobile ad-hoc network routing protocols, like the Ad-hoc On-Demand Distance Vector (AODV) protocol, often struggle in this environment. They typically rely on reactive route discovery through flooding Route Request (RREQ) packets and periodic “hello” messages for link maintenance. This approach generates substantial control overhead, increases latency, and fails to leverage a critical feature of planned formation drone light show operations: the predictability of node trajectories and, consequently, network topology changes.
This article addresses these shortcomings by introducing a time-varying graph model to capitalize on this predictability. We propose a Shortest Delay Routing Protocol based on a Discrete Time Aggregate Graph (DTAG-MD) for UAV formations. The core idea is to use a priori knowledge—the pre-planned flight paths for a formation drone light show or other coordinated mission—to model the network’s evolution over time. This model then enables the pre-computation of optimal, delay-minimizing routes before any data transmission request occurs, eliminating the need for costly on-demand route discovery floods.
1 Introduction and Challenges in UAV Formation Routing
UAV formations, especially as seen in large-scale formation drone light show performances, represent a specialized subclass of FANETs. Unlike general mobile ad-hoc networks (MANETs) or vehicular ad-hoc networks (VANETs), these formations exhibit extreme dynamics. Nodes move at high speeds along predefined but potentially complex paths, leading to rapid and predictable changes in which UAVs are within communication range of each other. The primary communication modes within a formation are “broadcast” for command dissemination and task allocation, and “point-to-point” for dedicated data flows and acknowledgments.
Traditional routing protocols fall into three categories: proactive (e.g., OLSR), reactive (e.g., AODV, DSR), and hybrid. Their applicability to formation drone light show networks is limited:
- Proactive protocols maintain routing tables for all nodes, incurring high overhead and storage costs unsuitable for resource-constrained UAVs.
- Reactive protocols (like AODV), while more efficient in storage, introduce significant latency during the route discovery phase. The frequent flooding of RREQ packets in a highly dynamic topology leads to control packet redundancy, congestion, and wasted energy. Furthermore, their performance is highly sensitive to accurate location information, which can be unreliable in real-world conditions with interference.
- Hybrid protocols have complex zoning requirements and high computational demands.
The key insight is that in a planned formation drone light show, the motion of every drone is known in advance. This allows us to predict the future state of the network—a capability traditional protocols ignore. Therefore, the research challenge is to design a routing strategy that exploits this network priori information to achieve high Packet Delivery Ratio (PDR), low end-to-end delay, and minimal control overhead.
2 The Discrete Time Aggregate Graph (DTAG) Model
To model the predictable time-varying topology of a UAV formation, we adopt the Discrete Time Aggregate Graph. The DTAG is a compact representation that aggregates the network’s topological states across a discretized timeline into a single graph, avoiding the high memory cost of replicating nodes for each time slot (as in Time-Expanded Graphs).
Consider the total operation time $T$ of a formation drone light show. We divide $T$ into $K$ equal, discrete time slots: $[t_0, t_1), [t_1, t_2), …, [t_{K-1}, t_K]$. The network is represented as a graph $G = (V, E)$, where $V$ is the set of UAV nodes, and $E$ is the set of potential communication links. For each link $e = (u, v) \in E$, we associate a Link Delay Series (LDS), not just a single static weight. The LDS is a time-indexed sequence representing the propagation delay over that link during each time slot.
Let $\sigma_{uv}(t_k)$ denote the propagation delay on link $(u,v)$ during the $k$-th time slot (starting at time $t_k$). If the link is disconnected in that slot, $\sigma_{uv}(t_k) = \infty$. The LDS for link $(u,v)$ is the vector:
$$\overrightarrow{\sigma_{uv}} = [\sigma_{uv}(t_0), \sigma_{uv}(t_1), …, \sigma_{uv}(t_{K-1})]$$
The accuracy of the DTAG model depends on the granularity $K$. Finer time slots yield a more precise approximation of the continuous network dynamics, which is crucial for a high-speed formation drone light show.
The key advantage of DTAG is its compactness and suitability for solving temporal shortest-path problems. However, it traditionally assumes a First-In-First-Out (FIFO) property, where a data packet cannot arrive earlier by waiting at a node. In UAV networks, intelligent packet holding (non-FIFO behavior) can sometimes reduce total travel time. For example, if a link currently has high delay but will improve shortly, it may be beneficial to buffer the packet. Our algorithm must account for this possibility.
3 DTAG-MD: Shortest Delay Routing Algorithm
Our proposed DTAG-MD protocol operates in two phases: (1) Offline Pre-computation and (2) Online Route Look-up.
3.1 Offline Pre-computation: Solving the Temporal Shortest Path
Given the pre-planned trajectories for a formation drone light show, we first construct the DTAG model for the entire mission duration $T$. The objective is to find, for any given start time $t_s$ and source-destination pair $(s, d)$, the route that minimizes the total end-to-end delay, potentially leveraging non-FIFO waiting.
The core challenge is that standard shortest-path algorithms (e.g., Dijkstra) do not apply directly to time-varying graphs with non-FIFO links. We employ an Arrival Time Series Transformation (ATST) to convert link delay series into Node Arrival Time Series. For a link $(u,v)$, the ATST transforms the departure time from $u$ into the earliest possible arrival time at $v$, considering optimal waiting.
Let $c_u(t)$ be the earliest arrival time at node $u$ for a packet departing from source $s$ at time $t_s$. For a neighbor $v$ of $u$, the earliest arrival time at $v$ when leaving $u$ at time $t$ is calculated by examining the link delay series $\sigma_{uv}$:
$$T_{uv}(t) = \min_{\tau \ge t} \{ \tau + \sigma_{uv}(\tau) \}$$
where the minimization over $\tau \ge t$ allows for waiting at node $u$ for a more favorable link condition (non-FIFO).
The algorithm, based on a modified temporal Dijkstra approach, is detailed below. It computes the earliest arrival time $c_d(t_s)$ for all destinations from source $s$ starting at $t_s$, and records the predecessor nodes to reconstruct the optimal path.
| Algorithm 1: DTAG-MD Shortest Delay Path Computation |
|---|
|
Input: DTAG $G=(V,E)$ with LDS $\sigma_{uv}(t)$ for all links; Source node $s$; Start time $t_s$. Output: Earliest arrival time $c_v$ and predecessor $p_v$ for all $v \in V$. 1: Initialize: $c_s = t_s$; $c_v = \infty$ for all $v \neq s$; $p_v = \text{null}$ for all $v \in V$; Priority queue $Q = \{s\}$. 2: while $Q$ is not empty do 3: Extract node $u$ with smallest $c_u$ from $Q$. 4: for each neighbor $v$ of $u$ in $G$ do 5: Calculate earliest arrival: $t_{arrival} = T_{uv}(c_u) = \min_{\tau \ge c_u} \{ \tau + \sigma_{uv}(\tau) \}$. 6: if $t_{arrival} < c_v$ then 7: $c_v = t_{arrival}$ 8: $p_v = u$ 9: Insert/update $v$ in $Q$ with key $c_v$. 10: end if 11: end for 12: end while |
This algorithm runs offline for multiple start times $t_s$ to populate a global Time-Slotted Routing Table (TSRT). The TSRT is distributed to all UAVs before the mission, such as during the pre-flight synchronization of a formation drone light show.
3.2 Online Route Look-up and Forwarding
During the mission, when a source UAV $s$ has data to send to destination $d$ at the current time $t_{now}$, it simply consults its local TSRT. It looks up the entry for the time slot containing $t_{now}$ and retrieves the pre-computed next-hop for destination $d$. The packet is forwarded accordingly. No network-wide RREQ flood is needed. If a link breaks unexpectedly due to an unpredicted event (e.g., wind gust), a local route error message is sent upstream toward the source. The source node then queries its TSRT for a new route starting from the current time, which is likely still valid due to the robustness of the pre-computed paths against minor deviations.
4 Performance Evaluation and Simulation
We evaluated the DTAG-MD protocol against the standard AODV protocol using the NS-3 simulator. The simulation scenarios mimicked a formation drone light show operating in a 1000m x 1000m area, with UAVs following a Reference Point Group Mobility Model. Key simulation parameters are summarized below:
| Parameter | Value |
|---|---|
| Simulation Area | 1000 m × 1000 m |
| Mobility Model | Reference Point Group Mobility |
| MAC Protocol | IEEE 802.11g |
| Transmission Range | 250 m |
| Simulation Time | 200 s |
| Number of CBR Flows | 10 |
| Data Packet Size | 512 Bytes |
| Data Rate | 4 packets/s |
We analyzed two key scenarios impacting a formation drone light show:
Scenario 1: Effect of Node Density. UAV speed fixed at 30 m/s, number of UAVs varied from 20 to 100.
Scenario 2: Effect of Mobility Speed. Number of UAVs fixed at 100, speed varied from 10 to 80 m/s.
Metrics: Average End-to-End Delay, Packet Delivery Ratio (PDR), Normalized Routing Overhead (Control Packets / Delivered Data Packets).
4.1 Simulation Results Analysis
4.1.1 Impact of Node Density
The results are summarized in the table below and show clear advantages for DTAG-MD in dense formations typical of a large formation drone light show.
| Metric | Trend with Increasing Density | DTAG-MD vs. AODV | Explanation |
|---|---|---|---|
| Avg. Delay | Decreases then stabilizes | Lower (40-60% reduction) | DTAG-MD uses pre-known optimal paths. AODV suffers from flooding latency in dense networks. |
| PDR | Increases then stabilizes | Higher (15-30% improvement) | Pre-computed paths are more stable and reliable than on-demand paths in dynamic, dense topologies. |
| Routing Overhead | Increases | Drastically Lower (70-90% reduction) | DTAG-MD eliminates RREQ/RREP floods. AODV control overhead scales poorly with density. |
4.1.2 Impact of Mobility Speed
This scenario tests protocol robustness in high-speed maneuvers, a hallmark of dynamic formation drone light show patterns.
| Metric | Trend with Increasing Speed | DTAG-MD vs. AODV | Explanation |
|---|---|---|---|
| Avg. Delay | Increases | Significantly Lower and more stable | DTAG-MD delay is less sensitive to speed as paths are pre-optimized over time. AODV route discovery fails more often, increasing latency. |
| PDR | Decreases | Consistently Higher | At high speeds, AODV routes break frequently before discovery completes. DTAG-MD’s globally-optimized paths are more resilient. |
| Routing Overhead | Increases sharply for AODV | Negligible for DTAG-MD | High speed causes constant route breaks and re-discovery floods in AODV. DTAG-MD has minimal online control traffic. |
The mathematical relationship for end-to-end delay $D_{ete}$ can be modeled as a function of path length $H$ and per-hop delay $d_{hop}$, which itself depends on congestion and link quality. For DTAG-MD, the per-hop delay is near-optimal:
$$D_{ete}^{DTAG} \approx \sum_{i=1}^{H_{opt}} d_{hop}^{opt}(i)$$
For AODV, additional terms for route discovery latency $L_{disc}$ and potential route repair latency $L_{rep}$ must be included, which grow with network dynamics:
$$D_{ete}^{AODV} \approx L_{disc} + \sum_{i=1}^{H_{react}} d_{hop}^{react}(i) + \mathbb{E}[L_{rep}]$$
where $\mathbb{E}[L_{rep}]$ is the expected latency due to route repairs. Our simulations confirm that $D_{ete}^{DTAG} < D_{ete}^{AODV}$ across all tested conditions.
5 Conclusion and Future Work
This article presented the DTAG-MD routing protocol, a novel solution for reliable and efficient communication in predictable UAV formations such as formation drone light show networks. By leveraging the a priori knowledge of node trajectories through the Discrete Time Aggregate Graph model, DTAG-MD shifts the complex routing computation to an offline phase. This fundamental shift eliminates the large control overhead and high latency associated with traditional reactive route discovery protocols like AODV.
Simulation results demonstrate that DTAG-MD significantly outperforms AODV in key metrics: it achieves a higher Packet Delivery Ratio, lower average end-to-end delay, and dramatically reduced routing overhead. These improvements are especially pronounced in dense, high-speed scenarios characteristic of complex formation drone light show choreographies.
The current work focuses on minimizing delay as the sole metric. Future research will extend this framework to multi-objective optimization. A more comprehensive routing cost function $C_{link}(t)$ for each link at time $t$ could integrate factors like predicted link lifetime $L(t)$, node residual energy $E_{res}(t)$, and queueing delay $Q(t)$:
$$C_{link}(t) = \alpha \cdot \sigma_{link}(t) + \beta \cdot \frac{1}{L(t)} + \gamma \cdot \frac{1}{E_{res}(t)} + \delta \cdot Q(t)$$
where $\alpha, \beta, \gamma, \delta$ are weighting coefficients. Finding the optimal path based on this composite metric would further enhance the robustness and longevity of the formation drone light show network. Additionally, adapting the protocol to handle moderate deviations from the pre-planned paths using real-time local updates remains an important area for investigation.