Time-slotted routing technique enhances wireless communication

Wireless communication within a mobile ad-hoc network (MANET) system is prone to network congestion and susceptible to interference. A recent study by the US National Institute of Standards and Technology (NIST) has demonstrated that wireless devices can adversely affect the coordination of robots in an urban search and rescue scenario.¹ This has also been shown to affect the coordination of formation flight within a cluster of unmanned aerial vehicles (UAVs).²

Many protocols have been developed and studied in an effort to alleviate network congestion in a MANET. Some examples include demand source routing (DSR), optimized link state routing (OLSR), and the ad-hoc on-demand distance vector (AODV) protocol. All of these provide a reasonable solution for a MANET when the nodes exhibit low mobility. However, when the nodes in the network move at a high rate of speed or are peer aware, as in UAV formation flight, the inner node communication increases network congestion. We have developed a hybrid protocol to decrease the inner node communication and so limit the number of collisions that occur during the route seeking process.

Figure 1 illustrates the simple star network topology of a small cluster. All traffic is routed through the head node, and the source is no more than one hop from the destination. This is based on the AODV protocol,³ but introduces a time component into it, similar to that of the slotted ALOHA protocol.^4,5 A particular time slot is set aside for each node to communicate data to the designated head node.

To implement a time-slotted protocol, the time increments must be large enough to support the aggregate of all routing packets. In other words, C = Σ size (route replies, route requests, route error, data) for all messages required in both the route discovery process and the payload or data transmission process. Using a back-off period allows the messages to either be sent in the first instance of the time slot or to use a random send time in each slot. The time slot is defined to be:

where B is the back-off period, C is the largest control packet length, D is the data rate, ρ is the maximum clock skew, and τ is the time slot size.

To maximize network bandwidth usage, τ must be as small as possible while still allowing time for route discovery and payload traffic transmission to occur. The choice of a minimum value of τ must provide for a reasonable maximum clock skew.

Figure 1. In the star cluster network topology, all traffic goes through the head node, and the source is no more than one hop from the destination.

The average ratios of dropped packets to sent packets (drops-to-sends ratios) for both the AODV and time-slotted protocols are shown in Table 1. Notice that the ratios for the time-slot-managed network are better than the AODV in all but the two-node case. While the total network traffic decreases with the time-slotted method, a consistent level of reliability and scalability are provided over a broader range of network sizes. It should also be noted that the transmission capacity for individual nodes is inversely proportional to the number of nodes in the network.

Table 1. AODV and time-slotted drops-to-sends ratios

The use of time slot allocation to coordinate communication between nodes in a MANET is shown to improve the quality of service (QoS) of node communication by minimizing data packet drops. Adjusting the time-slot duration to facilitate the transfer of the largest packet and routing message requirements, while at the same time avoiding data packet collisions, maximizes the reliability of communication over the network. The data transfer rate is lowered by this method, but the communication throughput sustained by the time-slotted routing protocol is sufficient to maintain formation flight in a UAV. The important results to note are the reliability of the communication, the scalability of the nodes in the formation, and the hazards of a dropped navigation packet that may potentially disrupt or alter the mission beyond recovery.

The results suggest several additional enhancements to the use of the time-slot method, including a two-stage time-slot window to increase the size of τ when the route discovery process is required or requested, and a dynamic time-slot window for clock skew. Other approaches include allocating time slots based on message type, and relaxing the time-slot node allocation constraint and allowing more than one node in the network to transmit. Other future efforts include intrusion detection schemes based on time-slotted communication with predetermined frequency hopping strategies. This additional security, coupled with enhanced reliability, is applicable not only to UAV formation flight, but to first-responder/urban search and rescue missions, rapid military deployment, and contaminated sensor network scenarios.

This work was supported through the Laboratory Directed Research and Development program of the Idaho National Laboratory (INL) under DOE Idaho Operations Office Contract DE-AC07-051D14517.