# A Hybrid Reactive Routing Protocol for Decentralized UAV Networks

Shivam Garg S. Garg is with the Computational Science Research Center at San
Diego State University (SDSU), USA<EMAIL_ADDRESS>Alexander Ihler A.
Ihler is with the Donald Bren Hall School of Information and Computer
Sciences, University of California, Irvine, USA<EMAIL_ADDRESS>Elizabeth
Serena Bentley E. S. Bentley is with the Air Force Research Laboratory, Rome,
NY, USA<EMAIL_ADDRESS>Sunil Kumar S. Kumar is with the
Electrical and Computer Engineering Department, SDSU, San Diego, USA,
<EMAIL_ADDRESS>
###### Abstract

Wireless networks consisting of low SWaP (size, weight, and power), fixed-wing
UAVs (unmanned aerial vehicles) are used in many applications, such as
monitoring, search and surveillance of inaccessible areas. A decentralized and
autonomous approach ensures robustness to failures; the UAVs explore and sense
within the area and forward their information, in a multihop manner, to nearby
aerial gateway nodes. However, the unpredictable nature of the events,
relatively high speed of the UAVs, and dynamic UAV trajectories cause the
network topology to change significantly over time, resulting in frequent
route breaks. A holistic routing approach is needed to support multiple
traffic flows in these networks to provide mobility- and congestion-aware,
high-quality routes when needed, with low control and computational overheads,
using the information collected in a distributed manner. Existing routing
schemes do not address all the mentioned issues.

We present a hybrid reactive routing protocol for decentralized UAV networks
called H-AODV. Our scheme searches routes on-demand (using a multi-metric
route selection), monitors a region around the selected route (the “pipe”),
and proactively switches to an alternative route before the current route’s
quality degrades below a threshold. We empirically evaluate the impact of pipe
width and node density on our ability to find alternate high-quality routes
within the pipe and the overhead required to maintain the pipe. We also
incorporate a queue management scheme to prioritize transmission of packets
based on their age of information (AoI). Compared to existing reactive routing
schemes, our approach achieves higher throughput and reduces the number of
route discoveries, overhead, and resulting flow interruptions at different
traffic loads, node densities and speeds. Despite having limited network
topology information, and low overhead and route computation complexity, our
proposed scheme achieves superior throughput to proactive optimized link state
routing (OLSR) scheme at different network and traffic settings. We also
evaluate the relative performance of reactive and proactive routing schemes.

###### Index Terms:

UAV network, decentralized network, reactive routing, hybrid reactive routing,
ad-hoc on-demand distance vector (AODV).

##  I Introduction

Applications of flying ad-hoc networks (FANETs) include environment sensing,
disaster management, surveillance, relay networks, and more [1, 2, 3, 4, 5].
Increasingly, unmanned aerial vehicles (UAVs) form a core part of FANETs,
thanks to their relatively low cost, rapid deployment, and device autonomy. A
UAV network can easily adapt to dynamic mission requirements, with high
reliability and fault tolerance [2, 3]. Fig. 1 shows an example of remote
monitoring in an inaccessible area, where a communication infrastructure is
not available. A decentralized network of low SWaP (size, weight and power)
UAVs, equipped with self-localization and sensing capabilities, can provide
reliable sensing and communication for area monitoring and information
gathering [4, 6]. We assume the information is time-sensitive, and must be
transmitted in real time to a remote ground control station (GCS) for
coordinating the mission. However, low SWaP UAVs cannot directly reach the GCS
due to their limited signal transmission range. Therefore, information is
forwarded along a multi-hop route to gateway nodes, which can be airborne for
longer duration and have a higher transmission range. This enables them to
relay the data to the GCS to make informed decisions in real time. In an area
being monitored, it is difficult to predict when and where events may occur
(e.g., fire breakouts, damaged infrastructure, or people needing rescue).
Moreover, the UAV trajectories vary as they search for events. Therefore, the
source UAV and destination (gateway) pairs change with time. Combined with
high UAV speeds, this results in a highly dynamic network topology, in which
existing links break frequently and new links are formed. As a result, the
routes between source-destination pairs and network traffic conditions change
often. To ensure uninterrupted, reliable and low-latency communication, a
source UAV node should maintain stable, uncongested, and high quality multi-
hop route(s) to its gateway node.

Figure 1: Illustration of autonomous UAV ad-hoc network for remote monitoring
of an inaccessible area, where a communication infrastructure is not
available.

Existing routing protocols for ground-based mobile ad hoc networks (MANET) are
not suitable for decentralized (no supervisory node) UAV networks due to the
highly dynamic network topology and frequent link disruptions [1, 3, 7, 8, 9,
10]. Therefore, a number of FANET-specific routing protocols have been
proposed in the literature [1, 3, 7, 8, 9, 2, 11, 6, 10, 5]. In topology-based
routing schemes, nodes recompute the routes periodically (proactive routing
schemes) or on-demand (reactive routing schemes) [2, 3]. The routing schemes
must quickly adapt to topology changes in UAV networks, lest broken routes
degrade the flow throughput [2]. Since high node speeds in FANETs result in
frequent changes to network topology, a source node should ideally monitor the
route quality in terms of route lifetime ($RLT$), path latency, congestion and
route capacity (i.e., data throughput). The selected route should adapt to
these varying network and traffic conditions by taking preemptive measures,
such as switching to an alternate route (e.g., when the quality of the current
route degrades) and decrease congestion along the route.

However, designing a routing protocol with this level of adaptability requires
collecting a variety of node and link statistics, such as the number of flows,
interference, connectivity to 1-hop neighbors, link capacity, queuing delay,
and bit error rates (BER). These time-varying metrics should be updated
periodically, as in proactive routing protocols (e.g., optimized link state
routing (OLSR) [12], and its variants [11, 10, 7]). However, this increases
the control overhead and computational complexity (c.f., [11]). In addition,
proactive routing schemes are vulnerable to security threats, since breaching
one node can reveal the entire network topology, including the relative node
locations and their IP addresses [13].

On the other hand, reactive routing schemes (e.g., [5, 14, 15, 16, 17, 18, 19,
20, 21, 22, 13, 23, 24, 8, 25, 26, 27, 28]) search routes on-demand, and so
have low control and computation overhead. A new route is discovered only when
the current route breaks. However, on-demand route discovery incurs delays or
risks selecting low-quality routes: since reactive routing schemes do not
track changes in the network topology, a source node must either discover it,
or risk selecting a sub-optimal route for packet transmission [29].

Desired Routing Protocol Characteristics: As discussed in [11], a routing
protocol for decentralized UAV networks should have the following
characteristics: (i) Achieve stable route(s) with high throughput to ensure
reliable data communication; (ii) Low route signaling overhead, delay, and
computational complexity; and (iii) Monitor the route quality to estimate
packet drops due to node mobility and congestion, and take proactive measures
to maintain quality.

We recently designed a proactive routing scheme, called mobility and
congestion-aware OLSR (MCA-OLSR) [11], for decentralized UAV networks.
However, it can incur higher control (signaling) overhead and route
computation complexity in settings with few traffic flows, since each node
tries to determine a route to all other nodes in the network. For our
application scenario as in Fig. 1, source nodes only need to find suitable
routes to a limited number of gateway nodes. In this paper, we present a
novel, hybrid, reactive, ad-hoc on-demand distance vector (H-AODV) routing
protocol for decentralized UAV networks to address the issues discussed above.
Our protocol also adopts certain proactive routing features to track limited
network topology around the selected route.

Major contributions of our proposed routing protocol include:

  1. 1.

Multi-metric route selection: We use the hop count ($HC$), $RLT$, estimated
route latency and the inter- and intra-flow interference to select a stable,
longer-lasting and congestion-aware route.

  2. 2.

Pipe formation: A 2-hop node region (pipe) is formed around a selected route;
it enables a source node to monitor the current route and find a better
quality route within the pipe.

  3. 3.

Unlike most existing schemes, our routing scheme distinguishes whether a
packet may be lost due to a link break or congestion. It addresses congestion
buildup through AoI-based queue management (discussed next), followed by
preemptive route switching to select a new, better quality route to both
alleviate congestion and avoid broken links, improving the overall quality of
service (QoS).

  4. 4.

AoI-based queue management: The age-of-information (AoI) [30] refers to the
time the packet has spent in the network. For latency sensitive applications
(e.g., video streaming), a higher AoI value for a packet indicates a lower
time-to-expiry. Our AoI-based queue management scheme proactively discards
packets with too-high AoI values, while prioritizing packets with low
survivability scores (a lower time-to-expiry and/or higher estimated time-to-
destination) to improve timely packet arrivals.

  5. 5.

Superior performance: Despite using limited network topology information, our
scheme achieves higher throughput, outperforming the AODV, link stability
estimation-based preemptive routing (LEPR) [14], and OLSR schemes, while
incurring few route discoveries and low control overhead and computational
complexity.

  6. 6.

Compared to existing literature [31, 32, 33, 29, 34], we perform a more
detailed evaluation of the relative performance of reactive and proactive
routing schemes in a range of network and traffic settings (see Section IV-C).

We use a customized, discrete event driven simulation framework using ns-3 to
evaluate routing performance across extensive simulations, measuring packet
delivery ratio (PDR), number of route discoveries, control overhead, and route
computation complexity.

Paper organization: In Section II, we review existing reactive routing schemes
for finding a stable, mobility-aware and congestion-free route in FANETs.
Next, we describe our proposed hybrid reactive routing scheme in Section III.
We compare the performance of our proposed scheme with existing reactive and
proactive routing schemes in Section IV, followed by a discussion of key
observations in Section V and conclusions in Section VI.

##  II Related Work

In this section, we review existing reactive routing schemes, followed by an
overview of the AODV [16] and LEPR [14] schemes. These two schemes are used as
benchmarks in the sequel to evaluate the performance of our proposed H-AODV
scheme.

Traditional reactive routing protocols suffer from the “broadcast storm”
problem arising from a flood of route request (RREQ) packets in the network
[8, 17, 18, 25]. This introduces control overhead and delay due to frequent
route rediscoveries in a dynamic network topology. Several methods attempt to
ameliorate the problem. Nodes in [17] reduce their RREQ forwarding probability
as their queue occupancy increases, reducing the number of congested nodes
contesting for the channel to forward control packets. In [18], instead of
triggering a new network-wide route discovery, the source node requests that
the intermediate nodes of the broken route search for an alternate route in
their $k$-hop neighborhood to reduce the control overhead. In [19], a node
identifies the RREQ forwarding node(s) for each of its different zones based
on its neighbor nodes’ directions and their local connectivity. However, these
schemes [17, 18, 19] can result in poor route selection.

In [25], the source and intermediate nodes of the route periodically identify
the alternate shortest $HC$ route(s) passing through their 1-hop neighbor
nodes. A node switches to a new route when the link with its downstream node
breaks due to mobility. This mechanism reduces the number of route discoveries
and their resulting delay and control overhead. However, it does not predict
the link break and/or congestion buildup, and therefore may transmit packets
over an obsolete or congested route. In contrast, our proposed H-AODV scheme
proactively switches to a new route before it breaks, and uses multiple
metrics (such as $RLT$, route latency and the inter- and intra-flow
interference along the route, in addition to $HC$) to select a stable, longer-
lasting and less-congested route.

QoS-aware variants [20, 21] of reactive routing use a subset of statistics
which may include congestion, traffic load, delay, node mobility, link
stability, signal strength and remaining battery life. For example, nodes in
[20] rebroadcast the RREQ packets only when they can satisfy the flow QoS
requirements, such as time-to-live (TTL), minimum bandwidth and jitter.
However, this scheme does not track the node mobility and link stability that
cause frequent route discoveries in FANETs. In [21], an intermediate node
adjusts to the changes in network topology and traffic conditions by
reselecting its downstream node based on its neighbor distance, latency, load
and reliability. However, changing routes locally at intermediate nodes can
result in longer, sub-optimal routes [16].

The multipath reactive routing schemes [15, 22, 5] find multiple link- or
node-disjoint paths at the time of route discovery and use them when the
current route quality degrades, decreasing the number of route discoveries
[13]. However, the quality of the remaining routes may also degrade by the
time the primary route breaks, causing flow interruptions and large route
switchover overhead and delay [23, 14]. Schemes in [23, 24] prevent the
selection of broken routes by periodically monitoring the quality of the
remaining routes. A fuzzy-logic based multipath routing scheme is proposed in
[8] to select a short, low-latency route based on node mobility, residual
energy, link quality and stability. It also repairs broken routes using local
node information, and initiates a new route discovery if no suitable route is
found.

However, the schemes in [23, 24, 8] incur large control overhead. To address
this issue, a semi-proactive route maintenance mechanism is proposed in LEPR
[14], in which the intermediate nodes of the primary route notify the source-
destination pair node whenever their link quality degrades. The source node
then switches to an alternate route without incurring a large overhead.

Like our H-AODV scheme, a few other reactive routing schemes (e.g., [26, 27,
28]) also use various route quality metrics for route selection and/or
switching. The scheme in [26] creates a fixed cylindrical virtual tunnel for a
given source-destination pair to limit the number of nodes participating in
the route discovery and selection. However, its rigidity prevents it from
supporting network topologies that require flexible tunnels. In [27], a
reinforcement-learning (RL)-based strategy is implemented in GCS to
dynamically adjust clusters and their heads in response to frequent changes in
the network topology. Note that route selection at GCS is not suitable for an
autonomous, decentralized UAV network. An application-aware routing scheme is
presented in [28], where the source node distributes its traffic load across
multiple node-disjoint routes. However, unlike our proposed H-AODV scheme, it
does not preemptively switch to new better-quality routes that may become
available due to changes in the network topology or traffic conditions.

We have selected LEPR [14] as a representative of reactive routing schemes for
experimental comparison since: (i) it incorporates link quality in both route
selection and switching, and (ii) it has been evaluated across a range of
network and traffic parameters in the literature, including different node
speeds and traffic loads. An overview of the LEPR scheme is given below in
Section II-B.

###  II-A Overview of Standard AODV Protocol

AODV [16] is a widely used reactive routing protocol. It uses four types of
control packets: RREQ (route request), RREP (route reply), RERR (route error),
and Hello packets. The RREQ messages are broadcast in the entire network,
while RREP and RERR messages are transmitted using unicast communication, and
Hello packets are broadcast in the respective 1-hop neighborhood of each node.

The source node searches for a route on-demand by flooding the network with
RREQ packets. An RREQ packet includes the IP addresses of its source and
destination nodes, the sequence number of the source node, the last known
sequence number of the destination node, and the Hop Count. The intermediate
node(s) rebroadcasts the RREQ packet if it does not know a route to the
destination node. When the destination node receives the first RREQ packet, it
transmits an RREP packet towards the source node. The source node then selects
the shortest hop count route to the destination node from among the received
RREP packets.

Each node broadcasts its Hello packet after the Hello interval (default value:
1 s). The Hello packet structure is similar to the RREP packet, except the IP
address of the RREQ originator node. When a node does not receive any control
packet from its 1-hop neighbor node for the Allowed_Hello_Loss $\times$ Hello
Interval duration (default value: 3 s), it assumes a link break with that
1-hop neighbor node. When an intermediate node of the route detects a link
break, it generates an RERR packet for the source node. Upon receiving an RERR
packet, the source node starts a new route discovery.

###  II-B Overview of LEPR Protocol

The LEPR protocol [14] modifies the AODV protocol [16] by computing multiple
stable link-disjoint routes during route discovery and proactively switching
to an alternative route before the primary route breaks. Its two main
components are reactive route discovery and semi-proactive route maintenance.

To compute the link-disjoint routes, the RREQ and RREP packets carry the
information of the first hop and last hop node on the route, respectively.
Each node computes a link stability metric with each of its 1-hop neighbor
nodes by using the locally available information (their link quality, relative
distance and mobility) and updates the link stability metric field in the RREQ
and RREP packets. The path stability of a route is the minimum of all the link
stability metrics along the route. Both the source and destination nodes thus
know the link-disjoint routes and their stability.

The source node then selects a route with the highest path stability value and
caches the remaining routes. When the link stability value at an intermediate
node drops below a threshold $k$, the node notifies the destination node by
sending a route switch (RSWT) packet. The destination node then transmits a
new RREP packet towards the source node on each cached route, which carries
the updated path stability metric value of the route. The source node switches
to a cached route if its path stability value is greater than a threshold
$k^{\prime}$. Otherwise, it triggers a new route discovery. The value of
thresholds $k$ and $k^{\prime}$ can vary between 0 and 1.

Limitations: LEPR [14] does not consider the effect of congestion in route
selection. Note that nodes in reactive routing schemes rely on the timely
reception of their neighbor’s control packets; otherwise, a link break is
assumed. As the number of packet collisions increases with traffic load, a
‘false’ link break can be assumed at a node when it misses its 1-hop
neighbor’s control packets. In response, the source node either switches to
one of its cached routes or initiates a new route discovery. In contrast, our
proposed H-AODV scheme incorporates mechanisms to address congestion buildup,
including congestion-aware route selection (Section III-C), queue management
to postpone congestion buildup (Section III-E), and preemptively switching to
another high-quality route within the pipe (Section III-D4). In addition, each
node receives the neighborhood information from other nodes in the pipe, which
reduces the probability of flagging a false link break. As a result, the
number of route discoveries in our H-AODV scheme is much lower compared to
LEPR (see, e.g., Fig. 7).

When the route quality degrades, the source node in LEPR switches to one of
its cached routes, which were found during the last route discovery. Although
new and better-quality routes may have become available due to network
topology changes, LEPR does not find or use them in its semi-proactive route
maintenance mechanism. In contrast, our H-AODV scheme proactively finds new
better quality routes within the pipe as discussed in Section III-D4.

Figure 2: Modules used in our H-AODV scheme.

##  III Description of Proposed H-AODV Protocol

Our H-AODV routing protocol searches the route(s) on-demand, and then
proactively switches to an alternative route before the quality of current
route degrades below a threshold. It reduces the number of route discoveries,
and the resulting overhead and flow interruptions, compared to existing on-
demand schemes such as LEPR and standard AODV.

Fig. 2 shows the modules of our proposed H-AODV routing scheme. A source node
triggers a route discovery by broadcasting an RREQ message if it does not
already have a high quality route to its destination node. The destination
node responds to the received RREQ messages by transmitting RREP messages
towards the source node. Each RREP carries the $HC$, estimated time-to-
destination ($ETD$) and number of interfering links ($IL$) statistics of the
route. The source node evaluates all the received RREPs and selects a long-
lasting and congestion-free (or less-congested) route.

The neighborhood information of the intermediate nodes of the selected route
is periodically sent to the source node. We use the term ‘pipe’ to refer to
this neighborhood information around the selected route. The source node
reevaluates the current route and switches to an alternative high quality
route within the pipe when needed. If no route within the pipe has the
required route quality, the source node proactively triggers a new route
discovery. Like MCA-OLSR [11], our proposed H-AODV scheme uses a proactive
queue management mechanism, discussed in Section III-E.

We discuss the network modeling and assumptions in Section III-A, and the
modules of Fig. 2 in Sections III-C–III-D, followed by a discussion of control
overhead and computational complexity in Section III-F. The procedure of our
proposed H-AODV scheme is given in Algorithm 1.

Algorithm 1 Overview of our H-AODV Scheme

1\. Route discovery: Source node starts a network-wide route discovery with
controlled RREQ flooding (see Section III-C)
Destination node sends RREP packet(s), which carries the $HC$, $ETD$ and $IL$
values of the route
2\. Route selection: Select a stable and less-congested route $R^{*}$ from all
the received RREPs using (4a), (4b) and (5) in [11]
3\. Pipe formation: Intermediate nodes of the selected route $R^{*}$ collect
their 2-hop neighborhood information to create a virtual pipe (see Fig. 3)
4\. Network topology update: Periodically send the pipe information to the
source node
5\. Route reevaluation and switching: Source node checks if any of the three
conditions of Eq. (6) in [11] occurred
if  _any of the three conditions occurred_ then

if  _an alternative route $R$ with quality $>$ threshold exists within the
pipe_ then

Switch to route R (i.e., $R^{*}$ = $R$)
Go to the pipe formation step

else

Go to the route discovery step

end if

end if

###  III-A Network Modeling and Assumptions

We consider a network of low SWaP fixed-wing (FW) UAVs. Since FW-UAVs cannot
make sharp turns due to their aerodynamics and high speeds, a smooth-turn (ST)
mobility model is used, in which each node independently selects a center and
radius, and rotates around the center in a clockwise or counter-clockwise
direction for a randomly selected duration, until its trajectory changes again
[35, 9]. Each node broadcasts its trajectory information (i.e., GPS location,
center, radius, and movement: clockwise, counter-clockwise, or straight) to
its 1-hop neighbors via its Hello messages. A node computes the link lifetime
($LLT$) value for each of its 1-hop neighbor nodes using the mathematical
formulation described in [9, 36]. A UAV pair uses the current trajectory
information to compute its $LLT$ value when the link is first established,
updating when either UAV in the pair changes its trajectory. In our scheme,
the $LLT$ value of a link is included in the Hello message, which is broadcast
periodically in the network [11].

###  III-B Selection of Routing Metrics

Besides $HC$, the received signal strength indicator (RSSI), $RLT$, buffer
occupancy ($BO$) and $ETD$ metrics have been used for route cost computation
in the literature [7, 6, 8]. However, these routing metrics are not
sufficiently reliable. For example, significant interference from neighbor
nodes in a dense network can cause inaccurate computation of RSSI values [19].
The $RLT$ value can change as the UAVs alter their trajectories [9], and the
values of $BO$ and $ETD$ can increase significantly after the source node
starts data transmission along the selected route [11].

Like our recent MCA-OLSR scheme [11], our proposed scheme computes a longer-
lasting and low congestion route by using the $HC$ (hop count) and $IL$
(interfering links) for its route cost computation, and $RLT$ and $ETD$ for
route evaluation and switching after data transmission starts on the selected
route. An advantage of using the $IL$ metric is that its value for a route
changes only when the local topology changes. As a result, the route quality
in our scheme changes less frequently than existing multi-metric schemes. $HC$
represents the route length in terms of the number of links between the source
and destination nodes. The $IL$ value at a node is the number of active links
in its 1-hop neighborhood that contend for channel access. The interfering
link value for a route ($IL_{R}$) is the sum of the number of interfering
links at all nodes (from the source to destination node) on the route, and is
computed as [7, 11],

$IL_{R}=\sum_{j\in N_{R}}\bigg{(}IL^{\theta}_{j}+IL^{\phi}_{j}\bigg{)},$ (1)

where $N_{R}$ is the set of nodes on route $R$ from the source node to the
destination. Here, $IL^{\theta}_{j}$ represents the recent $IL$ value of node
$j$ received via its control packet, and $IL^{\phi}_{j}$ represents the new
intra-flow interfering links that will be created at node $j$ when data
transmission starts on route $R$.

The $RLT$ (route lifetime) of a route is the time duration after which the
route is likely to break. It is the minimum link lifetime, $LLT$, of the links
along the route, computed at the source node as [6, 11],

$RLT_{R}=\min_{l\in L_{R}}{(LLT_{l})},$ (2)

where $L_{R}$ represents the set of links on route $R$ that connect the source
node to the destination via intermediate nodes, and the lifetime of each link
$l$, $LLT_{l}$, is computed by using the node location (GPS coordinates) and
trajectory [9, 36].

The $ETD$ is the total estimated delay a packet will experience while
traveling from the source to destination node on route $R$ [8]. It is the sum
of the packet service time ($PST$) of each node on the route, where the $PST$
of a node is the total duration for which its packets stay in its medium
access control (MAC) queue during the current Hello interval. The $ETD$ value
at the source node is computed as [8, 11],

$ETD_{R}=\sum_{j\in N_{R}}\bigg{(}\frac{1}{P_{j}}\sum_{p\in
P_{j}}{(PST)_{p}}\bigg{)}_{j},$ (3)

where $N_{R}$ is the set of nodes on route $R$ and $P_{j}$ is the set of data
packets successfully transmitted by node $j$ during the previous Hello
interval.

Each node includes its $PST$ and $IL$ values in the Hello packet. An increase
in the data generation rate, route length or $IL$ in the neighborhood of a
node can cause congestion buildup. This sharply increases the packet queuing
delay and reduces its survivability score, which causes packet drops due to
expiry [11]. Therefore, we track the route quality using the $HC$, $RLT$, and
$ETD$ metrics, and use a preemptive route switching mechanism when the
topology changes or congestion buildup reduces the route quality (see Section
III-D4 for details).

###  III-C Low-Overhead Route Discovery

When a node receives a control packet (e.g., RREQ, RREP or RERR) in the
standard AODV protocol, it stores its originator node, destination node and
sequence number to avoid reprocessing the same packet. A destination node
knows about different routes to the source node through RREQ packets that
traverse different routes to reach it. However, it originates an RREP packet
only when an RREQ packet is received via a shorter hop route than the
previously known route or when the sequence number of the received RREQ packet
is higher.

Instead of blindly forwarding the RREQ packets, a receiver node $i$ in our
H-AODV scheme broadcasts an RREQ packet only when the following link stability
condition is satisfied for transmitter node $j$:

$\centering LLT_{i,j}(i)~{}>~{}TTL~{}+~{}\delta(i)\@add@centering$ (4)

Here, $TTL$ represents the time-to-live value of the flow (determined by the
application and included in RREQ packets) and $\delta$ is a control parameter,
which can be tuned locally at each node depending on its speed and how quickly
its neighborhood changes.

Thus, the RREQ packets traverse towards destination node on longer-lasting
routes, reducing the number of control packet transmissions. In order to
obtain the HC, ETD and IL statistics of the complete route, only the
destination node originates the RREP packet in our scheme. Note that the Hop
Count field in an RREP packet represents the hop length of the route from the
current node to the destination node. When a node along the reverse route
(towards the source node) receives the RREP packet, it adds its own PST and IL
values in the RREP packet’s ETD and IL fields, respectively. When a source
node receives multiple RREPs, it selects the best route using Eq. (5) in [11].

###  III-D Pipe Formation and Proactive Route Switching

Due to frequent changes in the network topology, the quality of the current
route can degrade with time, while new and better-quality routes may become
available. In order to improve the flow throughput and reduce interruptions,
the source node can proactively switch to the highest quality route when the
quality of the current route drops below a threshold. However, since the
future node trajectories are unknown, predicting a high quality route based on
the current network topology information is difficult. That is why the nodes
in proactive routing schemes broadcast their information periodically in the
entire network to update the topology information. To find a better quality
route without high control overhead, the source node in our scheme collects
some limited network topology information (the 2-hop neighborhood) around the
currently active route, forming a ‘pipe’ that can be used for route switching.

####  III-D1 Pipe Formation

In typical reactive routing protocols, nodes do not know their 2-hop
neighborhoods. Thus, when a node receives a data packet it informs its 1-hop
neighbor nodes about its participation in the packet forwarding process by
including an ‘isActive’ flag in its Hello packet111Note that a node can also
find its active neighbors by passively listening to the channel.. Upon
receiving a Hello packet with ‘isActive’ set, the node includes its 1-hop
neighborhood information (i.e., the nodes’ IP addresses and links) in its
Hello packet. Since the Hello packet includes the sender’s GPS coordinates, a
node can identify which of its 1-hop neighbors are within transmission range
of each other. As a result, the intermediate nodes of the selected route can
determine their 2-hop neighborhood information to form the pipe (see Fig. 3).
If a node does not receive a data packet within the Active_Route_Timeout
duration (the default value in the standard AODV protocol is 3 s [16]), it
turns off the ‘isActive’ flag. Note that the pipe width can also be varied:
increasing its width would increase the known fraction of network topology,
providing more high-quality route(s) but at the cost of a higher control
overhead and computational complexity, as discussed in the sequel (Section
III-D3).

Figure 3: Pipe formation in our H-AODV scheme. Figure 4: Possible situations
to connect two nodes in a network. As the pipe width $w$ increases, more route
segments become available to connect the nodes. TABLE I: Overhead vs.
Alternate high-Quality Routes for different Pipe Widths

Pipe Width |  50 Nodes |  100 Nodes
---|---|---
| Neighbors Tracked* |  No. of High-Quality Routes Found within Pipe | Neighbors Tracked* |  No. of High-Quality Routes Found within Pipe
| Mean | 95% $CI^{\\#}$ |  |  New Route Length $\leq$
---
Current Route Length
| New Route Length >
---
Current Route Length
Mean | 95% $CI^{\\#}$ |  |  New Route Length $\leq$
---
Current Route Length
| New Route Length >
---
Current Route Length
1 | 5 | [4.7, 5.2] | 1 | 3  | 8 | [7.2, 8.6] | 5 | 13
2 | 9 | [8.6, 9.8] | 4 | 6  | 17 | [15.2, 19.1] | 13 | 15
3 | 13 | [11.5, 13.6] | 14 | 18  | 28 | [26.1, 30.5] | 45 | 79
4 | 16 | [14.4, 17.4] | 24 | 22  | 43 | [39.8, 46.3] | 71 | 92

* Shows total neighbors tracked per node. $CI^{\textbf{\\#}}$ represents confidence interval.

####  III-D2 Sending Pipe Information to the Source Node

After the destination node receives the first data packet, it schedules an
interrupt to send a Notify_Source control packet to the source node after each
Hello interval. When the Notify_Source packet passes through the intermediate
nodes of the route, they append their 2-hop neighborhood information along
with the PST, LLT and IL values. If the destination node does not receive a
data packet for Active_Route_Timeout duration, it suspends the Notify_Source
interrupt.

To reduce the control overhead, an intermediate node constructs a graph using
the 2-hop neighborhood information received from its downstream node and
includes its own information to compute the cliques [37]. Then, it includes
both the node statistics (PST and IL values) and link statistics (LLT value
and isLinkActive flag) only once, and forwards to its upstream node.

####  III-D3 Analysis of Pipe Width

Fig. 4 shows different scenarios which connect two nodes A and B on a route,
either directly or through their neighbors, for different pipe widths $W$
(i.e., route length $w\in[0,W]$). Many existing reactive routing schemes [25,
23, 13, 21] use only the 1-hop neighborhood information to locally repair a
broken link. If the 1-hop neighbors cannot find an alternative route to the
downstream node, a new route discovery is initiated. As shown in Fig. 4, more
route segments can become available for local link repair when a node collects
$W$-hop neighborhood information. For example, Fig. 4(a)-(e) shows five
possibilities for connecting nodes A and B when $w=2$. However, simply
repairing the link using this connection may increase the route length
significantly: for example, route length can increase by up to 2$W$ to repair
link A-B in Fig. 4(g). To avoid unnecessary increases, in our scheme the
source node instead forms a new route within the pipe.

As shown in Table I, both the overhead (measured by the number of neighbors
tracked by each node) and the number of high-quality routes available within
the pipe increase significantly with pipe width. A source node can obtain on
average four or more routes within the pipe when $w=1$. However, due to
limited neighborhood information, these routes often include edge nodes, which
cause link breaks at high node speeds. We observed a decrease in the number of
new route discoveries (initiated when a high quality route cannot be found
within the pipe) with higher pipe width. Therefore, we selected $w=2$ for our
simulation which gives sufficient high-quality routes while keeping the
overhead low.

####  III-D4 Route Switching Mechanism

When the quality of the current route degrades below a threshold
(corresponding to Constraints (6a) and (6b) in [11]), the source node uses a
breadth first search (BFS) algorithm to find all routes within the pipe. If a
new better-quality route is found, the source node switches to the new route;
otherwise it triggers a new route discovery. When the source node switches to
a new route, the existing pipe is abandoned and a new pipe is formed around
the new route. The route switching mechanism, therefore, reduces the number of
route discoveries and the resulting discovery overhead and delay. It also
minimizes the interruption in flow throughput.

###  III-E AoI-Aware Queue Management

The congestion at a node can increase due to a high data rate, inter- and
intra-flow interference, and frequent link breaks, which increase the number
of packets in the queue and their queuing delay. To mitigate these issues,
each node in our scheme periodically reevaluates its queue using an AoI-based
queue management policy [11], where AoI measures the time each packet has
spent in the network:

  1. (i)

Instead of the FIFO order, rearrange the packets of the queue at a node in
ascending order of their survivability score, $\frac{(TTL-AoI)}{ETD}$.

  2. (ii)

Drop any packets with a survivability score lower than a threshold (we use
0.7), as they are not likely to be delivered to the destination before their
expiry.

This prioritizes sending packets with lower (but not too low) survivability
scores, increasing their chances of reaching the destination node before their
TTL expiry.

###  III-F Control Overhead and Computational Complexity

####  III-F1 Control Overhead

In addition to the information sent in the RREQ, RREP, RERR and Hello packets
in the standard AODV protocol, each node in the proposed H-AODV scheme
includes the following information in its Hello packet:

  * •

Its GPS location (using 6 bytes for ($x$,$y$,$z$) coordinates) and trajectory
information, which includes the center coordinates (6 bytes), radius and node
movement direction in the ST mobility model (2 bytes) [35]. Note that a node
sends its trajectory information only when it forms a new link or changes its
current trajectory.

  * •

Its $PST$ and $IL$ values (up to 2 bytes).

  * •

If the node is a 1-hop neighbor of an active node on the route, it broadcasts
the $LLT$, $PST$, $IL$ and $isLinkActive$ values for each of its 1-hop
neighbor nodes (variable size).

In addition, the destination node periodically sends a Notify_Source packet to
the source node, which carries the 2-hop neighborhood information (i.e., node
IP address and their $PST$, $IL$ and $LLT$ values) of all intermediate nodes
on the route (variable size).

####  III-F2 Route Computation Complexity

In this scheme, a source node finds all routes to the destination node within
the pipe using the BFS algorithm, which has a worst time complexity of
$O(T{V_{p}}^{2}(E_{p}+V_{p}))$, where $T$ is the number of times routes are
recomputed, and $V_{p}$ and $E_{p}$ are the number of nodes and links,
respectively, within the pipe. In addition, the intermediate nodes compute the
cliques of their 2-hop neighborhood using the Bron-Kerbosch algorithm [37],
which has a worst time complexity of $O(3^{V_{p}/3})$. Note that the clique
computation is optional but helps in reducing the control overhead.

Figure 5: Instantaneous PDR for H-AODV, LEPR and AODV schemes.

##  IV Simulation Setup and Results

We implemented our H-AODV scheme in the discrete event simulator, ns-3 version
3.29. Our simulation and network parameters are summarized in Table II. In our
simulation, fixed-wing, low SWaP UAVs fly in an 8$\times$8 km2 area (in which
fixed communication infrastructure, such as a cellular network, is not
available) following the ST mobility model of [35, 9, 11, 33, 36]. We assume
that the UAVs fly in the X-Y plane at a constant altitude, about 1 km above
the ground [38, 39]. UAVs perform collision avoidance through trajectory
modifications [40]. Performance is evaluated at multiple network settings,
including node density (50 and 100 UAVs), low to high node speeds (20 m/s and
50 m/s), and low to high traffic loads (40 kbps to 3 Mbps bit rate).

The UAVs are equipped with GPS and have a signal transmission range of 1 km
(e.g., [11, 41, 42]). Since there are no reflections or obstacles in the air,
we assume a free space line-of-sight propagation with path loss for the air-
to-air (A2A) channel between UAVs (e.g., [42, 41]). The packet size and TTL
values are 1 kB and 3 s, respectively, and the MAC queue stores up to 1000
packets. The carrier sense multiple access with collision avoidance (CSMA/CA)
protocol is used in the MAC layer. Each simulation is run for 600 s and each
experiment is repeated 40 times, with the source-destination pair(s) of a flow
selected randomly in each run.

TABLE II: Simulation Parameters

Parameters | Values
---|---
Simulation Area | $8\times~{}8~{}km^{2}$
Channel Rate | 11 Mbps
Transmission Range | 1 km
Node Density | 50, 100
Node Speed (in m/s) | 20, 50
Number of Traffic Flows | 1, 3, 10
Flow Rate | 40 kbps to 3 Mbps
Packet Size | 1 kB
Time-to-Live (TTL) | 3 s

We compare the performance of our H-AODV scheme to the standard AODV and LEPR
schemes in Section IV-B, followed by proactive routing schemes (i.e., standard
OLSR and MCA-OLSR) in Section IV-C.

###  IV-A Performance Metrics

We use the following four performance metrics:

  1. 1.

Packet delivery ratio (PDR) of a flow is the ratio of total data packets
received at the destination node to the total data packets generated at the
source node. The _flow throughput_ can be computed as PDR $\times$ data rate,
while the _packet loss ratio_ equals (1-PDR). When plotting average PDR, we
also indicate the 95% confidence interval (shaded region).

  2. 2.

Number of routes computed is the total number of routes computed during the
simulation.

  3. 3.

Number of route discoveries is the number of RREQ packets generated per flow
at the source node. A lower value signifies a more stable route(s).

  4. 4.

Number of route control packets is the total number of route setup, update and
maintenance packets (i.e., RREQ, RREP, RERR and Hello) transmitted over the
network during the simulation duration. This metric also includes the
Notify_Source packets in H-AODV scheme and RSWT packets in LEPR scheme.

  5. 5.

Control (signaling) overhead is the total size (in MB) of the route control
packets transmitted during the simulation duration.

Experimental results are averaged over 40 runs of 600 s duration each.

###  IV-B Comparison with Reactive Routing Schemes

Here, we evaluate performance of our H-AODV scheme in terms of PDR, number of
route discoveries, and route control overhead.

Figure 6: Average PDR for H-AODV, LEPR and AODV schemes for different number
of data flows and data rates, at varying node densities and speeds.

####  IV-B1 PDR Performance Comparison

First, we compare the instantaneous PDR performance of H-AODV with AODV and
LEPR schemes. Then, we discuss the impact of number of data flows and data
rate on the average PDR performance, followed by the impact of node densities
and speeds.

##### Instantaneous PDR Performance

Fig. 5 shows the instantaneous PDR values for each scheme for 100 nodes flying
at 20 m/s speed and a data flow rate of 2.5 Mbps. Performance is shown for the
first 100 s, where the initial 25 s are used for network stabilization. Unlike
AODV and LEPR, our H-AODV scheme provides a consistently higher instantaneous
PDR because it quickly adapts to dynamic network topology by predicting the
congestion buildup and link breaks. As a result, our scheme can achieve
uninterrupted communication throughout the simulation duration despite a
dynamic network topology. Although not shown here, the instantaneous PDR plots
for other simulation settings also showed superior performance over AODV and
LEPR.

##### Impact of Traffic Rates

Fig. 6 shows the average PDR of each scheme for one and three flows across
varying data rates until the network becomes congested. The PDRs of all the
schemes decrease as the traffic load increases. Since our proposed H-AODV
scheme incurs a lower RREQ flooding overhead, selects stable and congestion-
free (or less congested) routes, and preemptively switches to a new route when
the quality of current route degrades, it provides a higher average PDR than
the standard AODV and LEPR schemes.

For 50 nodes at 20 m/s speed, our H-AODV achieves up to 29% and 14% higher PDR
compared to the AODV and LEPR schemes, respectively, in Fig. 6(a). For a
higher node density (100 nodes) at 20 m/s, H-AODV achieves up to 63% and 33%
higher PDR compared to AODV and LEPR schemes, respectively (see Fig. 6(b)).
Although more routes become available for a source-destination pair in the
higher density network, AODV continues to use the current route until a new
route discovery is triggered. Since a source node tracks the nodes within the
pipe around the active route (in H-AODV) or caches different link-disjoint
routes (in LEPR), it switches to a less-congested route, whenever needed.
Therefore, the PDR performance of H-AODV and LEPR is improved.

Fig. 6(c) shows the PDR for 50 nodes flying at 50 m/s speed. Since the links
break more frequently at 50 m/s, which require a higher number of route
discoveries, the PDR performance degrades for all the three schemes as
compared to node speed of 20 m/s in Fig. 6(a). However, PDR performance of
H-AODV is still up to 12% and 11% higher compared to AODV and LEPR schemes,
respectively.

TABLE III: Average PDR for 10 Low Data Rate Flows

Data Rate per Flow | Scheme | 50 Nodes @ 20 m/s | 100 Nodes @ 20 m/s | 50 Nodes @ 50 m/s |  100 Nodes @ 50 m/s
---|---|---|---|---|---
40 kbps | AODV | 0.92 | 0.88 | 0.56 | 0.55
| LEPR | 0.92 | 0.88 | 0.56 | 0.65
| H-AODV | 0.95 | 0.99 | 0.6 | 0.75
| OLSR | 0.85 | 0.85 | 0.37 | 0.42
| MCA-OLSR | 0.97 | 1 | 0.56 | 0.81
200 kbps | AODV | 0.85 | 0.7 | 0.47 | 0.44
| LEPR | 0.87 | 0.79 | 0.47 | 0.48
| H-AODV | 0.92 | 0.93 | 0.52 | 0.64
| OLSR | 0.78 | 0.81 | 0.33 | 0.39
| MCA-OLSR | 0.95 | 0.99 | 0.55 | 0.77

Fig. 6(d) shows the PDR performance for 100 nodes at 50 m/s. The PDR
performance of H-AODV is up to 56% and 21% higher than AODV and LEPR,
respectively. Although the route discoveries increase at 50 m/s, the number of
available routes also increases with an increase in the node density. As a
result, the source node in both H-AODV and LEPR schemes successfully switches
to an alternate route before the primary route breaks. Therefore, the PDR
values in both these schemes improve at 100 nodes as compared to 50 nodes.
However, as discussed earlier in this subsection, our proposed H-AODV scheme
incurs a lower RREQ overhead, selects stable and congestion-free (or less
congested) routes, and preemptively switches to a new route when the quality
of current route degrades and, therefore, provides a higher average PDR than
LEPR scheme.

##### Impact of Node Density

When the node density increases from 50 to 100 nodes, the PDR performance of
H-AODV and LEPR schemes at 50 m/s improves by up to 28% and 31%, respectively.
Although routes break more frequently at 50 m/s than at 20 m/s, the fact that
more routes are available at higher node density enables both schemes to
switch to an alternate route when the current route breaks.

##### Impact of Node Speed

At higher speed, the network topology changes faster and creates more frequent
route breaks, decreasing the PDR performance. Our H-AODV scheme selects a
longer-lasting and congestion-free (or less-congested) route, and performs
route switching within the pipe when the current route degrades. It thus
spends less time finding a new route as compared to the AODV and LEPR schemes.
AODV does not monitor the route quality and so needs extra time to detect a
route break; on the other hand, LEPR evaluates the stability of all cached
routes before initiating a new route discovery, which incurs delay when links
break frequently. Thus, H-AODV achieves up to 58% and 21% higher PDR compared
to AODV and LEPR, respectively, for three flows at the higher speed of 50 m/s
in Fig. 6(d).

##### Performance for 10 Sensor Data Flows

Table III shows the PDR performance comparison for 10 sensor data flows at two
different data rates for two node densities and two speeds. Here, the per flow
data rates are 40 kbps and 200 kbps, which correspond to a total of 400 kbps
and 2 Mbps data traffic generated per second, respectively. Our H-AODV scheme
achieves higher PDR as compared to the AODV and LEPR schemes at each setting.
Since the number of alternative routes formed within the pipe for each traffic
flow increases at a higher node density, the PDR performance of H-AODV scheme
improves significantly when the node density increases from 50 to 100 nodes at
node speed of 50 m/s.

####  IV-B2 Comparing the Number of Route Discoveries

Fig. 7 shows the number of route discoveries in the three reactive routing
schemes for one and three traffic flows at two data rates, and two different
node speeds and densities. We see that H-AODV has fewer route discoveries than
AODV and LEPR, because it searches for an alternate route within the pipe
before initiating a new route discovery.

The route discoveries increase with traffic load. Since the network becomes
congested and the packet collisions and channel access time increase at higher
traffic loads, the Hello and other control packets are delayed. When a node
does not hear from its 1-hop neighbor node(s) within a set duration, it
assumes a link break, which can trigger a new route discovery in AODV or route
switching in LEPR. In H-AODV, each intermediate node on the route receives the
neighborhood information from all of its neighbor nodes within the pipe. This
increases redundancy in the received information, which reduces the
probability of falsely flagging a link break and prevents triggering route
discovery or switching in H-AODV when the network is congested.

Figure 7: Performance comparison of H-AODV, LEPR and AODV schemes in terms of
average route discoveries, route control packets and control overhead at
different traffic loads, node speeds, and densities.

The number of route discoveries increases in both AODV and LEPR as the node
density increases from 50 to 100 nodes, but decreases for our H-AODV scheme,
since more alternate routes become available within the pipe at a higher node
density.

Figure 8: Average PDR for MCA-OLSR, H-AODV, and standard OLSR and AODV schemes
for different number of data flows and data rates, at varying node densities
and speeds.

####  IV-B3 Comparison of Route Control Packets

As compared to AODV, the number of route control packets is generally lower in
LEPR and H-AODV schemes at different node densities, speeds and traffic loads
in Fig. 7. At higher node density and traffic loads, it increases
significantly in AODV as compared to LEPR and H-AODV schemes. When the node
speed increases from 20 m/s to 50 m/s, the number of route control packets
decreases significantly in AODV due to network partitioning. However, the
number of route control packets changes only moderately in LEPR and H-AODV
schemes because majority of control packets (e.g., Notify_Source in H-AODV
scheme and RSWT in LEPR scheme) are generated and forwarded along the active
route(s).

####  IV-B4 Control Overhead Comparison

As compared to AODV, the control overhead is generally lower in LEPR and
H-AODV at different node densities, speeds and traffic loads in Fig. 7. At
higher traffic load and node density, it increases for all three schemes.
However, the increase at node density of 100 nodes is much higher for the AODV
scheme. At higher node speed, it decreases for all the three schemes, due to
the network partitioning into multiple components.

###  IV-C Comparison with Proactive Routing Schemes

The choice between proactive and reactive routing protocols depends on many
factors, including the network size, node mobility, and traffic
characteristics. However, existing literature comparing proactive and reactive
routing schemes (e.g., [34, 31, 32, 29, 33]) offers limited and inconclusive
insights. For example, [34] compares the performance of the standard AODV and
OLSR schemes, showing the PDR and control overhead in AODV are superior to
OLSR for latency-agnostic, low-throughput traffic scenarios in MANETs. But, as
the traffic load increases, OLSR outperforms AODV in terms of PDR, delay and
control overhead. In some FANET-based comparative studies, such as [31, 32],
AODV outperforms OLSR in terms of PDR at all node speeds and/or traffic loads,
contradicting the results in [29]. Furthermore, in [31], control overhead in
OLSR exceeds that in AODV when the number of traffic flows is high; this is
inconsistent with the findings in [34]. Both AODV and OLSR schemes in [33]
experience lower PDR with increasing node density, yet the PDR remains
consistent across various node speeds, contrary to expectations. None of the
cited studies consider latency-sensitive flows with varying data rates, which
can result in packet loss due to expiration or buffer overflow.

In this paper, we delineate situations where proactive (OLSR and MCA-OLSR) and
reactive (AODV and our proposed H-AODV) routing schemes exhibit relative
superiority, in terms of PDR, control overhead and route computations, at
different network and traffic settings.

####  IV-C1 PDR Comparison

Fig. 8 shows the average PDR of each scheme for 1 and 3 latency-sensitive
flows across varying data rates (up to the point that the network becomes
congested) at different node densities and speeds. Although H-AODV uses only a
fraction of the network topology within the pipe, its PDR performance is
better than standard OLSR and approaches that of MCA-OLSR.

Since fewer routes are available at lower density (50 nodes), the PDR
performance of these proactive and reactive routing schemes decreases
significantly when node speed increases from 20 m/s to 50 m/s (see Figs. 8(a)
and 8(c)). We see that the PDR of H-AODV and MCA-OLSR are comparable to each
other at 50 m/s, in Fig. 8(c). On the other hand, when node density is
increased to 100 nodes at 50 m/s, the PDR of H-AODV and MCA-OLSR increases
significantly because more stable high-quality routes become available; see
Fig. 8(d). At high node speed, the route breaks more frequently, resulting in
a higher number of route discoveries in H-AODV. Whereas, MCA-OLSR can select a
new route in the entire network instead of being limited to the nodes in the
pipe. Thus, it achieves higher PDR than H-AODV when the node speed increases
from 20 m/s to 50 m/s in Figs. 8(b) and 8(d).

The PDR performance of the standard AODV protocol is comparable to standard
OLSR on 50 nodes at 20 m/s; see Fig. 8(a). Fig. 8(b) shows the PDR performance
for 100 nodes at 20 m/s. Due to higher node density (100 nodes) and low node
speed (20 m/s), more stable routes are available between the source-
destination pairs, improving the PDR performance of standard OLSR compared to
the lower node density. However, the PDR performance of standard AODV
decreases due to the increased control overhead for more nodes; see Fig. 7.

Since standard OLSR selects a shortest hop route and uses the edge nodes, it
experiences frequent link breaks at high node speed (50 m/s), giving short-
lived routes. In contrast, standard AODV experiences fewer route breaks
because it may not select the shortest hop route available in the
network222The source node selects the shortest hop route to the destination
node only from among the received RREP packets, as discussed in Section
II-A..This property enables AODV to achieve a higher PDR than standard OLSR at
higher speeds; see Figs. 8(c) and 8(d).

TABLE IV: Comparison of Average Control (Signaling) Overhead (in MB)

Scenario | OLSR | MCA-OLSR | AODV | H-AODV
---|---|---|---|---
1 Flow | 3 Flows | 1 Flow | 3 Flows
50 Nodes | 20 m/s | 61.3 | 115.9 | 1.9 | 6.7 | 1.1 | 1.7
50 m/s | 5.9 | 40.9 | 1.1 | 2.1 | 0.7 | 0.9
100 Nodes | 20 m/s | 465.8 | 1,341.6 | 33.1 | 49.6 | 3.8 | 8.7
50 m/s | 241.7 | 588.2 | 10.5 | 19.4 | 2.8 | 4.9

TABLE V: Comparison of Average Number of Routes Computed

Scenario | OLSR | MCA-OLSR | H-AODV
---|---|---|---
1 Flow | 3 Flows | 1 Flow | 3 Flows | 1 Flow | 3 Flows
50 Nodes | 20 m/s | 340,037 | 348,717 | 188 | 776 | 16 | 52
50 m/s | 252,844 | 277,721 | 713 | 2,606 | 65 | 106
100 Nodes | 20 m/s | 2,033,978 | 1,992,317 | 131 | 722 | 17 | 81
50 m/s | 1,053,313 | 1,065,282 | 3,274 | 8,928 | 103 | 265

####  IV-C2 Performance for 10 Sensor Data Flows

Table III shows the PDR performance comparison for 10 sensor data flows at two
different data rates for both node densities and speeds. Here, the PDR trends
are similar to those observed for one and three flows discussed previously:
our H-AODV scheme significantly outperforms standard OLSR and is comparable to
MCA-OLSR except at high node density and speed.

####  IV-C3 Control Overhead Comparison

The control overhead includes the Hello and TC packets in OLSR, and RREQ, RREP
and RERR packets in AODV, besides the Notify_Source packets in H-AODV and MCA-
OLSR schemes. The control overhead in both AODV and H-AODV schemes is
significantly lower than the standard OLSR and MCA-OLSR schemes for both node
densities and speeds in Table IV. While the control overhead for proactive
routing schemes is independent of the number of traffic flows, it increases
with traffic load for both AODV and H-AODV schemes. Due to network
partitioning into multiple components at 50 m/s, the control overhead for all
the schemes is lower as compared to 20 m/s.

####  IV-C4 Average Number of Route Computations

Table V shows the average number of routes computed by both proactive and
reactive routing schemes. Since standard AODV does not compute routes at the
source node (instead, it simply selects the route conveyed by the RREP
packet(s)), it is not included in the table. Both MCA-OLSR and H-AODV
recompute the routes only when a new, better quality route becomes available,
while the standard OLSR protocol recomputes the route whenever a new control
packet is received. Since H-AODV monitors the routes only within the pipe,
which is a fraction of the network topology, the total number of routes
computed ($T$) is significantly lower than for MCA-OLSR and standard OLSR.
This results in lower computational complexity of
$O(T{V_{p}}^{2}(E_{p}+V_{p}))$ (see Section III-F2). Here, the number of nodes
$V_{p}$ and edges $E_{p}$ within the pipe are significantly less than the
total number of nodes $V$ and edges $E$ in the network.

##  V Discussion

Our H-AODV scheme achieves higher instantaneous as well as average PDR than
the AODV, OLSR and LEPR schemes. It selects stable and less congested routes,
preemptively switches to a better route when the current route quality
degrades, and uses a proactive queue management policy. Despite using only
limited network topology information, H-AODV often provides PDR that is
comparable or only slightly below that of MCA-OLSR.

At higher node speed, the network experiences frequent topology changes and
network partitioning, resulting in situations where no route may be available
for a flow, decreasing the PDR of all the evaluated routing schemes. H-AODV
uses the $RLT$ metric in route selection and switching, while AODV does not
track $RLT$ and OLSR often selects edge nodes in its shortest $HC$ route.
Thus, H-AODV achieves higher PDR than AODV and OLSR at higher node speeds.
Since LEPR triggers a new route discovery after its cached route(s), found
during the previous route discovery, become obsolete, it often incurs delays.

A higher node density increases the number of available stable routes,
improving the PDR of H-AODV, MCA-OLSR and LEPR, especially at higher node
speeds. Since the network topology stays more connected at lower speeds, the
PDR gain from higher density is slight.

H-AODV has fewer route discoveries than AODV and LEPR because it searches for
an alternate route only within the pipe before initiating a new route
discovery. The route discoveries increase with traffic load in all three
reactive routing schemes (H-AODV, AODV and LEPR). The number of route control
packets transmitted by H-AODV and LEPR are much lower than in standard AODV.
However, because of the additional fields introduced for both H-AODV and LEPR,
their total control (signalling) overhead (in MB) are only somewhat lower than
AODV at lower node density. At higher density, the control overhead in AODV is
much higher than for H-AODV and LEPR. However, the control overhead in all
three reactive routing schemes is much lower than in the proactive routing
schemes, OLSR and MCA-OLSR.

Since H-AODV computes a route only using the pipe information, its route
computation overhead and the resulting complexity are much lower than for OLSR
and MCA-OLSR.

We did not consider the energy consumed since (per experimental studies [43,
44]) the energy for communication is several orders of magnitude smaller than
for keeping the UAV aloft. However, UAVs can fail due to battery depletion or
malfunction. In the event of such node failures, the availability of enough
alternate routes (see Table I) means that our proposed scheme can easily
switch to a new high-quality route.

##  VI Conclusion

In this paper, we presented a mobility and congestion-aware, hybrid reactive
routing protocol for decentralized UAV networks. The proposed H-AODV scheme
searches high-quality route(s) on-demand (using a multi-metric route
selection), monitors the dynamic region (called the pipe) around the selected
route(s), and proactively switches to an alternative route (within the pipe)
before the quality of the current route degrades below a threshold. We studied
the impact of pipe width and node density on our ability to find alternate
high-quality routes within the pipe, and the required overhead. An AoI-aware
queue management scheme was also incorporated to prioritize the transmission
of packets.

Our scheme achieves superior performance, in terms of throughput, number of
route discoveries, overhead, and flow interruptions, compared to the standard
AODV and LEPR routing schemes. Despite using only limited network topology
information, the flow throughput performance of our H-AODV scheme was superior
to standard OLSR and close to MCA-OLSR on a range of network and traffic
settings, while incurring significantly lower control (signalling) overhead
and computational complexity. Compared to existing literature, we provide a
far more detailed evaluation of the relative performance of reactive and
proactive routing schemes across different network and traffic settings. In
the future, we plan to integrate our H-AODV routing protocol with other UAV
swarm mobility models (e.g., pheromone-based) and topology control mechanisms.

Acknowledgment of Support and Disclaimer:  The authors acknowledge the U.S.
government’s support in the publication of this paper. This material is based
on work funded by the U.S. AFRL (Air Force Research Laboratory), under
Contract No. FA8750-20-1-1005 and FA8750-23-C-0521. Any opinions, findings and
conclusions or recommendations expressed in this material are those of the
author(s) and do not necessarily reflect the views of AFRL or the US
government.

## References

  * [1] N. Mansoor, M. I. Hossain, A. Rozario, M. Zareei, and A. R. Arreola, “A fresh look at routing protocols in unmanned aerial vehicular networks: A survey,” _IEEE Access_ , vol. 11, pp. 66 289–66 308, 2023.
  * [2] M. M. Alam and S. Moh, “Survey on Q-learning-based position-aware routing protocols in flying ad hoc networks,” _Electron._ , vol. 11, no. 7, Art. no. 1099, 2022.
  * [3] A. Rovira-Sugranes, A. Razi, F. Afghah, and J. Chakareski, “A review of AI-enabled routing protocols for UAV networks: Trends, challenges, and future outlook,” _Ad Hoc Netw._ , vol. 130, Art. no. 102790, 2022.
  * [4] B. Alzahrani, O. S. Oubbati, A. Barnawi, M. Atiquzzaman, and D. Alghazzawi, “UAV assistance paradigm: State-of-the-art in applications and challenges,” _J. Netw. Comput. Applications_ , vol. 166, p. 102706, 2020.
  * [5] S. Devaraju, M. Parsinia, E. S. Bentley, and S. Kumar, “A multipath local route repair scheme for bidirectional traffic in an airborne network of multibeam FDD nodes,” _IEEE Trans. Aerosp. Electron. Syst._ , vol. 58, no. 4, pp. 2983–2995, 2022.
  * [6] M. Gharib, F. Afghah, and E. S. Bentley, “LB-OPAR: Load balanced optimized predictive and adaptive routing for cooperative UAV networks,” _Ad Hoc Networks_ , vol. 132, Art. no. 102878, 2022.
  * [7] A. A. Ateya, A. Muthanna, I. Gudkova, Y. Gaidamaka, and A. D. Algarni, “Latency and energy-efficient multi-hop routing protocol for unmanned aerial vehicle networks,” _Int. J. Distr. Sensor Netw._ , vol. 15, no. 8, 2019. doi/10.1177/1550147719866392.
  * [8] S.-W. Lee _et al._ , “An energy-aware and predictive fuzzy logic-based routing scheme in flying ad hoc networks (FANETs),” _IEEE Access_ , vol. 9, pp. 129 977–130 005, 2021.
  * [9] S. Garg, A. Ihler, and S. Kumar, “Accurate link lifetime computation in autonomous airborne UAV networks,” _arXiv:2202.00056 [cs.NI]_ , 2022.
  * [10] A. M. Rahmani _et al._ , “OLSR+: A new routing method based on fuzzy logic in flying ad-hoc networks (FANETs),” _Veh. Commun._ , p. 100489, 2022.
  * [11] S. Garg, A. Ihler, E. S. Bentley, and S. Kumar, “A cross-layer, mobility and congestion-aware routing protocol for UAV networks,” _IEEE Trans. Aerosp. Electron. Syst._ , 2022. doi: 10.1109/TAES.2022.3232322.
  * [12] T. Clausen and P. Jacquet, “Optimized link state routing protocol (OLSR),” _RFC 3626_ , 2003.
  * [13] T. K. Saini and S. C. Sharma, “Recent advancements, review analysis, and extensions of the AODV with the illustration of the applied concept,” _Ad Hoc Netw._ , vol. 103, Article No. 102148, 2020.
  * [14] X. Li and J. Yan, “LEPR: Link stability estimation-based preemptive routing protocol for flying ad hoc networks,” in _IEEE Symp.Comput. Commun._ IEEE, 2017, pp. 1079–1084.
  * [15] M. K. Marina and S. R. Das, “Ad hoc on-demand multipath distance vector routing,” _Wireless Commun. Mobile Comput._ , vol. 6, no. 7, pp. 969–988, 2006.
  * [16] C. Perkins, E. Belding-Royer, and S. Das, “Ad hoc on-demand distance vector (AODV) routing,” _RFC 3561_ , 2003.
  * [17] A. K. Dogra _et al._ , “Q-AODV: A flood control ad-hoc on demand distance vector routing protocol,” in _Int. Conf. Secure Cyber Comput. Commun._ IEEE, 2018, pp. 294–299.
  * [18] N. Ahmad, S. Sethi, and M. Ahmed, “Cache-aware query-broadcast to improve QoS of routing protocols in MANETs,” _Wireless Pers. Commun._ , vol. 113, no. 1, pp. 481–498, 2020.
  * [19] B. H. Khudayer, M. Anbar, S. M. Hanshi, and T.-C. Wan, “Efficient route discovery and link failure detection mechanisms for source routing protocol in mobile ad-hoc networks,” _IEEE Access_ , vol. 8, pp. 24 019–24 032, 2020.
  * [20] C. E. Perkins and E. M. Belding-Royer, “Quality of service for ad hoc on-demand distance vector routing,” 2003.
  * [21] D. Jinil Persis and T. Paul Robert, “Review of ad-hoc on-demand distance vector protocol and its swarm intelligent variants for mobile ad-hoc network,” _IET Netw._ , vol. 6, no. 5, pp. 87–93, 2017.
  * [22] A. O. Fapojuwo, O. Salazar, and A. B. Sesay, “Performance of a QoS-based multiple-route ad hoc on-demand distance vector protocol for mobile ad hoc networks,” _Canadian J. Elect. Comput. Eng._ , vol. 29, no. 1/2, pp. 149–155, 2004.
  * [23] S. Kumar, S. Khimsara, K. Kambhatla, K. Girivanesh, J. D. Matyjas, and M. Medley, “Robust on-demand multipath routing with dynamic path upgrade for delay-sensitive data over ad hoc networks,” _J. Comput. Netw. Commun._ , vol. 2013, Art. no. 791097, 2013.
  * [24] P. Li, L. Guo, and F. Wang, “A multipath routing protocol with load balancing and energy constraining based on AOMDV in ad hoc network,” _Mobile Netw. Appl._ , pp. 1–10, 2019.
  * [25] H.-H. Choi and J.-R. Lee, “Local flooding-based on-demand routing protocol for mobile ad hoc networks,” _IEEE Access_ , vol. 7, pp. 85 937–85 948, 2019.
  * [26] M. Hosseinzadeh _et al._ , “An energy-aware routing scheme based on a virtual relay tunnel in flying ad hoc networks,” _Alexandria Eng. J._ , vol. 91, pp. 249–260, 2024.
  * [27] J. Guo _et al._ , “ICRA: An intelligent clustering routing approach for UAV ad hoc networks,” _IEEE Trans. Intell. Transp. Syst._ , vol. 24, no. 2, pp. 2447–2460, 2022.
  * [28] C. Singhal and S. Barick, “ECMS: Energy-efficient collaborative multi-UAV surveillance system for inaccessible regions,” _IEEE Access_ , vol. 10, pp. 95 876–95 891, 2022.
  * [29] W. J. Lau _et al._ , “AQR-FANET: An anticipatory Q-learning-based routing protocol for FANETs,” in _IEEE Malaysia Int. Conf. Commun._ IEEE, 2023, pp. 6–11.
  * [30] J. Lou, X. Yuan, S. Kompella, and N.-F. Tzeng, “Boosting or hindering: AoI and throughput interrelation in routing-aware multi-hop wireless networks,” _IEEE/ACM Trans. Netw._ , vol. 29, no. 3, pp. 1008–1021, 2021.
  * [31] A. V. Leonov and G. A. Litvinov, “Considering AODV and OLSR routing protocols to traffic monitoring scenario in FANET formed by mini-UAVs,” in _Int. Sci.-Tech. Conf. Actual Problems Electron. Instrum. Eng._ IEEE, 2018, pp. 229–237.
  * [32] A. AlKhatieb, E. Felemban, and A. Naseer, “Performance evaluation of ad-hoc routing protocols in FANETs,” in _IEEE Wireless Commun. Netw. Conf. Workshops_. IEEE, 2020, pp. 1–6.
  * [33] T. Kim, S. Lee, K. H. Kim, and Y.-I. Jo, “FANET routing protocol analysis for multi-UAV-based reconnaissance mobility models,” _Drones_ , vol. 7, no. 3, p. 161, 2023.
  * [34] T. Clausen, P. Jacquet, and L. Viennot, “Comparative study of routing protocols for mobile ad hoc networks,” in _Med-hoc-Net_ , 2002.
  * [35] Y. Wan, K. Namuduri, Y. Zhou, and S. Fu, “A smooth-turn mobility model for airborne networks,” _IEEE Trans. Veh. Tech._ , vol. 62, no. 7, pp. 3359–3370, 2013.
  * [36] S. Garg, “An adaptive and low-complexity routing protocol for distributed airborne networks,” in _EWSN_ , 2021, pp. 187–191.
  * [37] H. Johnston, “Cliques of a graph-variations on the Bron-Kerbosch algorithm,” _Int. J. Comput. Inf. Sciences_ , vol. 5, no. 3, pp. 209–238, 1976.
  * [38] Wikipedia. Aerovironment switchblade. https://en.wikipedia.org/wiki/AeroVironment_Switchblade. Accessed May 17, 2024.
  * [39] Wikipedia . Raytheon coyote. https://en.wikipedia.org/wiki/Raytheon_Coyote. Accessed May 17, 2024.
  * [40] J. N. Yasin _et al._ , “Unmanned aerial vehicles (UAVs): Collision avoidance systems and approaches,” _IEEE Access_ , vol. 8, pp. 105 139–105 155, 2020.
  * [41] O. S. Oubbati, M. Atiquzzaman, A. Baz, H. Alhakami, and J. Ben-Othman, “Dispatch of UAVs for urban vehicular networks: A deep reinforcement learning approach,” _IEEE Transactions on Vehicular Technology_ , vol. 70, no. 12, pp. 13 174–13 189, 2021.
  * [42] M. Alam, N. Ahmed, R. Matam, and F. A. Barbhuiya, “IEEE 802.11ah-enabled internet of drone architecture,” _IEEE Internet of Things Magazine_ , vol. 5, no. 1, pp. 174–178, 2022.
  * [43] H. V. Abeywickrama, B. A. Jayawickrama, Y. He, and E. Dutkiewicz, “Comprehensive energy consumption model for unmanned aerial vehicles, based on empirical studies of battery performance,” _IEEE Access_ , vol. 6, pp. 58 383–94, 2018.
  * [44] Y. Zeng and R. Zhang, “Energy-efficient UAV communication with trajectory optimization,” _IEEE Trans. Wireless Commun._ , vol. 16, no. 6, pp. 3747–3760, 2017.