With the advancement of wireless communication and UAV (Unmanned Aerial Vehicle) drone technology, UAV Ad Hoc Networks (UAANETs) have become a significant focus for researchers. A UAV drone Ad Hoc network is a dynamic, self-configuring wireless network formed by multiple UAV drones, finding extensive applications in various fields such as precision agriculture for crop spraying, aerial cinematography, search and rescue operations in disaster zones, and reconnaissance and surveillance missions.
In early UAV drone Ad Hoc networks, omnidirectional antennas were predominantly used. However, the emergence of directional antennas has led to their increasing adoption in UAV drone networks. Compared to omnidirectional antennas, directional antennas concentrate their beam in a specific direction, offering longer transmission range, better spatial reuse enabling simultaneous communication between multiple pairs of nodes, reduced interference, and lower probability of packet collisions. Literature shows the use of directional antennas in UAV drone networks for beyond-visual-line-of-sight monitoring and video streaming, as well as for assisting ground user equipment in communicating with cellular networks. Nonetheless, the introduction of directional antennas brings new challenges. Existing Medium Access Control (MAC) protocols designed for omnidirectional antennas are not directly applicable and new issues such as the hidden terminal problem, deafness, and head-of-line blocking arise. Current MAC protocols can be broadly categorized into two types based on access methods: random contention-based access and scheduled allocation, with most based on Carrier Sense Multiple Access (CSMA) and Time Division Multiple Access (TDMA). Contention-based CSMA protocols using directional antennas often lead to packet loss and exacerbate hidden terminal and deafness issues. TDMA protocols, based on time synchronization and slot allocation, can avoid these problems but may introduce significant overhead, delay, and may not adapt well to dynamic network topology changes.
Most existing directional TDMA schemes adopt reservation-based slot allocation. For instance, the DTRA protocol divides a frame into three sub-phases: neighbor discovery, slot reservation, and data transmission. During neighbor discovery, nodes scan space; in the reservation sub-frame, nodes exchange data transmission requirements. However, it does not consider interference from other nodes in space during reservation. The DTDMA protocol improves upon DTRA by dividing neighbor discovery slots into micro-slots, randomly selecting one for sending handshake messages to reduce collisions, and proposes a dynamic slot allocation algorithm based on node buffer queue length to improve fairness. Yet, collisions can still occur at the receiver if micro-slot timing is small. Other protocols propose demand-oriented slot allocation, ring-based TDMA according to link distance, and distributed real-time slot allocation with traffic demand reduction algorithms to improve throughput and fairness, and on-demand mechanisms to release unused reservation slots.
Network Model and Problem Description
The proposed protocol is designed for distributed UAV drone Ad Hoc networks equipped with directional antennas. Each UAV drone node in the network is equal in status and possesses identical functionalities. There is no central node controlling the entire network. Each UAV drone node can autonomously perform network configuration and dynamically achieve data exchange and communication without relying on pre-existing ground network infrastructure.
Every UAV drone node in the network has a unique Node ID. It is assumed all nodes in the network are time-synchronized and operate in half-duplex mode, meaning they can only be in either transmit or receive state at any given moment. Each node is equipped with a single-beam directional antenna with a beamwidth of $\theta$. Communication between nodes uses directional transmission and directional reception mode. The criterion for communication between two nodes is that one node must be in transmit mode and the other in receive mode; their antenna beams must be mutually aligned, and both nodes must be within each other’s communication range. A collision is defined as a node simultaneously receiving two or more data packets, making it impossible to decode the packet contents.
In related literature, most directional TDMA protocol frame structures employ an interleaved process of control and data phases. A frame is divided into multiple periods, typically consisting of a neighbor discovery period, multiple interleaved slot reservation periods, and data transmission periods repeating within one frame. In the Scan Based Algorithm-Directional (SBA-D), the neighbor discovery phase uses a three-way handshake strategy. Theoretically, all nodes in the network can discover each other within $\lceil lb_2N \rceil$ sub-frames. In mobile scenarios, when a discovered neighbor receives a HELLO message again, not replying can reduce collisions, but the node’s position may have changed, altering the sector alignment and reducing network reliability. Conversely, replying directly and reserving slots again leads to unnecessary overhead and slot wastage.
During the slot reservation phase, the process of nodes mutually reserving slots can lead to wasted reservation slots and reservation conflicts. Considering a network topology with N nodes, each node requires at least N slots in the reservation phase to communicate with all other nodes to confirm reservation needs. However, most nodes are not neighbors with all other nodes. For example, a node with k neighbors only needs k reservation slots, leading to significant slot wastage when N is large. Furthermore, when a source node needs to transmit data to a destination, it may fail to reserve sufficient data slots during the reservation phase, causing queue buffer blockage and increased data delay.
The LDO-BFCN Protocol
The LDO-BFCN (Low-delay and overhead based on fully connected one-hop neighbors) protocol is a directional TDMA protocol designed for low delay and overhead. As shown in Table 1, the LDO-BFCN frame structure adds a Neighbor Information Exchange (ND Exchange) period to the existing interleaved reservation and data transmission frame structure and adjusts the number of slots in the reservation phase based on the size of a node’s fully connected one-hop neighbor set, thereby reducing the total number of slots in all reservation phases within a frame.
| Frame Component | Description |
|---|---|
| Neighbor Discovery (ND) | Initial discovery and handshake. |
| ND Exchange | Exchange of neighbor lists between nodes. |
| Reservation Phase (Multiple) | Slot reservation based on fully connected sets. |
| Data Transmission Phase (Multiple) | Actual data packet transmission. |
Table 1: LDO-BFCN Frame Structure Components
Dynamic Sector Information Update Mechanism
In the SBA-D algorithm, each node’s binary code length is determined by the number of nodes N. For a network with N UAV drone nodes, nodes are sequentially assigned IDs {0,1,2…N-1}. The binary code length LEN for each node is the same: $LEN = \lceil lbN \rceil$. Each bit of the binary code represents a complete scan cycle. When the bit is ‘0’, the node is in receive state; when ‘1’, it is in transmit state. The scanning sequence differs for transmit and receive states across predefined sectors.
During scanning, if two nodes point their beams at each other with complementary states (one transmitting, one receiving), they discover each other and add one another to their neighbor tables. In subsequent scans, if already discovered neighbors realign, many protocols either ignore the rediscovery to reduce collision (leading to outdated sector info) or re-initiate the full handshake (causing unnecessary overhead).
To address this, LDO-BFCN introduces a dynamic sector information update mechanism. Upon receiving a HELLO packet, the receiver checks if the sender is in its neighbor table. If not, the standard three-way handshake proceeds. If the sender is already a neighbor, the receiver compares the received sector information with the stored sector for that neighbor. If the sector has changed, the receiver sends a concise FAN-REPLY packet containing only source, destination, and the new sector number. The sender updates its neighbor table accordingly. If the sector is unchanged, the receiver remains silent. This mechanism updates sector information efficiently with minimal overhead, maintaining link stability without unnecessary resource reservation.
Slot Reservation Mechanism Based on Fully Connected One-Hop Neighbors
To mitigate reservation slot wastage and conflicts, LDO-BFCN proposes a reservation mechanism based on the concept of fully connected one-hop neighbor sets. A fully connected one-hop neighbor set of a node is a subset of its one-hop neighbors where every pair of nodes within the subset are also mutual one-hop neighbors.
In LDO-BFCN, after the Neighbor Discovery phase, an ND Exchange period with N slots is added. During ND Exchange, nodes use pre-reserved slots to exchange their complete neighbor lists with each of their neighbors. After this exchange, each node executes an algorithm to compute all its fully connected one-hop neighbor sets. The number of slots L in each subsequent reservation phase is set based on the maximum size of these sets for any node, which is typically much smaller than N. The theoretical upper limit for the size of a fully connected set $K_{ac}$ for a node in a network of N nodes randomly uniformly distributed in an area S with communication radius r can be estimated as:
$$ K_{ac} = \left\lfloor \frac{N}{S} * \pi \left(\frac{r}{2}\right)^2 \right\rfloor $$
This shows that as node density increases, the maximum size of a fully connected set decreases, thus requiring fewer reservation slots.
The core algorithm for finding these sets works recursively, building cliques from the node’s neighbor list and the mutual neighbor relationships learned during ND Exchange. The key parameters for the algorithm are summarized in Table 2.
| Parameter | Meaning |
|---|---|
| Node | The ID of the current node. |
| ND | Set of one-hop neighbor IDs for ‘Node’. |
| $NN_i$ | Set of neighbor IDs for the i-th neighbor in ND. |
| All_Cliques | Collection of all found cliques (candidate sets). |
| max_cliques | Final set of maximal fully connected neighbor sets. |
Table 2: Algorithm Parameters for Fully Connected Set Discovery
During the reservation phase, a node iterates through its list of fully connected sets. In a given reservation slot, it checks the ID in the current position of the currently selected set. If the ID matches its own, the node acts as a transmitter and can initiate a reservation handshake with a neighbor from that set. If the ID does not match, the node acts as a receiver, pointing its beam towards that neighbor and listening for reservation requests. This structured approach ensures that within a fully connected set, only one node transmits at a time while others listen, drastically reducing the probability of collisions during reservation handshakes. Since L is smaller than N, the total number of slots wasted in the reservation phases across a frame is significantly reduced. The number of saved slots $num_{Slot}$ compared to a protocol using N slots per reservation phase over C interleaved reservation/data cycles is:
$$ num_{Slot} = C * N – C * L $$
Relay-Assisted Forwarding Mechanism
Each node maintains a relay forwarding weight value. When a source UAV drone node cannot reserve enough data slots for its destination, leading to buffer congestion, it can select a relay node based on these weights to forward part of its data, thereby reducing delay. The relay weight $w_N$ for a node is calculated dynamically each frame based on three factors:
$$ w_N = 0.3\gamma_1 + 0.4\gamma_2 + 0.3\gamma_3 $$
- $\gamma_1 = L – |All\_Con|$: Where $|All\_Con|$ is the number of fully connected sets the node belongs to. A higher number of sets suggests more neighborhood interactions, potentially making it less suitable as a dedicated relay. If $\gamma_1 < 0$, the node is not considered for relay.
- $\gamma_2 = \frac{\text{Slots Used in Frame}}{\text{Total Data Slots in Frame}}$: The ratio of data slots a node used in the previous frame. If $\gamma_2 \leq \frac{1}{N}$, the node had very few data slots, indicating low activity, making it a potential relay candidate.
- $\gamma_3 = \frac{\text{Required Slots for Buffered Packets}}{\text{Total Data Slots per Frame}}$: The ratio of slots needed for the node’s own buffered packets in the next frame. A lower value indicates more available capacity for relay tasks.
The source node selects the neighbor with the highest $w_N$ value as its auxiliary relay. The relay receives data from the source into a separate relay queue and forwards it to the destination during its own reserved slots with the destination. This mechanism alleviates congestion at the source and helps reduce end-to-end delay.
LDO-BFCN Protocol Operation Flow
The operational workflow of the LDO-BFCN protocol within a frame is as follows:
- Frame K Start & Neighbor Discovery: Nodes initialize their binary code and scanning sequence. Based on the current bit, a node decides to transmit (send HELLO in a random micro-slot) or receive. On receiving a HELLO, the receiver applies the dynamic sector update logic (reply with FAN-REPLY if sector changed, else stay silent; or perform full three-way handshake if sender is a new neighbor). This repeats until the Neighbor Discovery period ends.
- ND Exchange Phase: Nodes communicate with each neighbor in their pre-reserved ND Exchange slots to exchange their complete neighbor lists.
- Fully Connected Set Computation: Each node runs the algorithm to determine its list of fully connected one-hop neighbor sets.
- Reservation Phase: The node selects its first fully connected set. It iterates through the node IDs in this set for the duration of the reservation phase. If its own ID matches the current ID in the iteration, it acts as a transmitter and can send a reservation request to a neighbor. If not, it acts as a receiver, pointing its beam at the node corresponding to the current ID and listening for requests. This process repeats for subsequent reservation phases using other fully connected sets.
- Data Transmission Phase: Nodes transmit data in their reserved slots. If a source node has insufficient reserved slots with the destination, it activates the relay-assisted forwarding mechanism, sending part of its data to the pre-selected best relay node, which then forwards it to the destination.
- Frame End and Weight Update: At the end of the frame, each node calculates its new relay weight $w_N$ based on its activity in the just-completed frame. This weight is included in the HELLO messages of the next frame’s Neighbor Discovery phase, allowing all neighbors to have updated information for relay selection in the subsequent frame.
The process then repeats for frame K+1.
Simulation Results and Analysis
The LDO-BFCN protocol was simulated and compared against the DTDMA protocol using OPNET Modeler 14.5. The key simulation parameters are listed in Table 3. The performance was evaluated in terms of control overhead, average data delay, packet loss rate, and network throughput.
| Simulation Parameter | Value / Scheme |
|---|---|
| Number of UAV Drone Nodes | 32 |
| Packet Size | 256 bytes |
| Simulation Area | 100 km × 100 km |
| Modulation | QPSK |
| Transmission Range per hop | 20 km |
| Basic Slot Duration | 1 ms |
| UAV Drone Speed | 200 m/s |
| Data Rate | 8 Mbps |
Table 3: Protocol Simulation Parameters
Control Overhead Analysis: Figure 1 shows the total control overhead (from neighbor discovery and reservation) versus the number of nodes. Overhead increases with node count for both protocols. For a smaller number of UAV drone nodes, the overhead is similar. As the number grows, the binary code length in SBA-D increases, leading to more scan cycles and repeated alignments. LDO-BFCN’s dynamic sector update mechanism helps reduce some of the rediscovery overhead, resulting in slightly lower control overhead compared to DTDMA at higher node densities.
Delay Analysis: Figure 2 presents the average end-to-end delay for all data packets. Delay increases with node count due to higher traffic. However, LDO-BFCN consistently shows lower delay. The reduction stems from the shorter reservation phase (less wasted slots) and the relay-assisted forwarding mechanism, which alleviates source node congestion. The improvement ranges from approximately 5.3% at 16 nodes to about 12.2% at 24 nodes compared to DTDMA.
Packet Loss Rate Analysis: The packet loss rate comparison is shown in Figure 3. Loss increases for both protocols with more nodes due to a higher probability of collisions. The rates are very close for a low number of UAV drone nodes. However, as the network scales to 32 nodes, LDO-BFCN demonstrates better stability, achieving a packet loss rate about 2.56% lower than DTDMA, indicating more reliable reservation and data transmission.
Throughput Analysis: Network throughput is compared in Figure 4. Throughput increases with node count for both, but LDO-BFCN consistently achieves higher throughput. The increase is attributed to the collision-reducing fully connected set-based reservation mechanism, which improves slot reservation success, and the relay-assisted forwarding, which utilizes network capacity more efficiently. At 32 nodes, LDO-BFCN provides approximately 212 kbps higher throughput than DTDMA.
| Performance Metric | DTDMA Protocol | LDO-BFCN Protocol | Improvement |
|---|---|---|---|
| Control Overhead (32 nodes) | Higher | Lower | Reduced via dynamic updates |
| Average Delay (24 nodes) | Higher | Lower | ~12.2% reduction |
| Packet Loss Rate (32 nodes) | Higher | Lower | ~2.56% reduction |
| Throughput (32 nodes) | Lower | Higher | ~212 kbps increase |
Table 4: Summary of Performance Comparison
Conclusion
This paper presented the LDO-BFCN protocol, a low-delay and low-overhead directional TDMA protocol for UAV drone Ad Hoc networks. Building upon existing directional TDMA protocols like DTDMA, LDO-BFCN introduces three key mechanisms: a dynamic sector information update to handle node mobility efficiently, a slot reservation mechanism based on fully connected one-hop neighbor sets to drastically reduce reservation slot wastage and collisions, and a relay-assisted forwarding mechanism to alleviate source congestion and reduce delay. Simulation results demonstrate that compared to the DTDMA protocol, LDO-BFCN achieves improvements in control overhead, end-to-end delay, packet loss rate, and network throughput. Future work will focus on enhancing the fairness of data slot allocation among UAV drone nodes and further optimizing the protocol to adapt to highly dynamic and large-scale UAV drone network scenarios.