Dynamic Routing in Flying Ad-Hoc Networks Using Topology-Based Routing Protocols

Abstract

The ever-increasing demand for flexible and portable communications has led to a rapid evolution in networking between unmanned aerial vehicles (UAVs) often referred to as flying ad-hoc networks (FANETs). However, due to the exclusive characteristics of UAVs such as high mobility, frequent topology change and 3D space movement, make routing a challenging task in FANETs. Due to these characteristics, designing new routing protocols for FANETs is quite difficult. In the literature study of FANETs, a variety of traditional ad-hoc networking protocols have been suggested and tested for FANETs to establish an efficient and robust communication among the UAVs. In this context, topology-based routing is considered the most significant approach for solving the routing issues in FANETs. Therefore, in this article we specifically focus on topology-based routing protocols with the aim of improving the efficiency of the network in terms of throughput, end-to-end delay, and network load. We present a brief review of the most important topology-based routing protocols in the context of FANETs. We provide them with their working features for exchanging information, along with the pros and cons of each protocol. Moreover, simulation analyses of some of the topology-based routing protocols are also evaluated in terms of end-to-end delay, throughput and network load the using optimized network engineering tools (OPNET) simulator. Furthermore, this work can be used as a source of reference for researchers and network engineers who seek literature that is relevant to routing in FANETs.

1. Introduction

During the past few years, the exponential progress in the making of small unmanned aerial vehicles (UAVs) has helped create the foundation of a new kind of network, referred to as flying ad-hoc networks (FANETs). Due to their versatility, adaptability, and easy deployment, FANETs are becoming a promising solution for various military and civilian applications, such as disaster inspection [1], search and rescue operations [2], border surveillance [3], forest fire detection [4], relaying networks [5,6], wind estimation [7], civil security [8], agricultural purposes [9], and traffic monitoring [10]. FANETs are essentially an ad-hoc network created by multiple small UAVS, which allows portable and flexible communication solutions in areas without infrastructure. The UAVs are hereby equipped with sensors, an on-board monitor, and a GPS module that may operate autonomously or via remote control. In order to avoid the limitations imposed by the conventional infrastructure-based communication architecture in a disastrous situation, FANETs are quickly deployable, self-configured, and offer a cost-effective communication data network [11]. While FANETs have the ability to collect and share the gathered information among the UAVs, they can also deliver it to the ground station. In addition, if some of the UAVs are disconnected during the mission due to weather conditions, they still have the ability to stay connected to the network through the other UAVs. With the help of multi-hop ad-hoc networking schema, it can remove obstacles such as network failure, limited guidance and short-range communication, which normally arise in a single UAV system [12]. On the one hand, such unique characteristics make FANETs a suitable solution for diverse application scenarios; but on the other hand, it also creates some challenging communication and networking issues between the multiple UAVs [13]. The basic problem with FANETs is the cooperative communication among the UAVs. Therefore, routing becomes an important and compulsory task to better assist the transmission of packets between the UAVs.

The FANETs applications are mostly supported by multi-hop communications, where the average speed of a UAV can span from almost 30–460 km/h in a three-dimensional environment [14]. In essence, the topology of the network changes quickly, which results in a link variation problem [15]. Additionally, frequent topology changes also enhance the latency, packet loss, and signaling overhead. Furthermore, FANETs are deployed for highly sensitive applications that demand guaranteed data transmission in a reliable, robust and cost-effective manner. Under these circumstances, designing and choosing appropriate routing protocols are essential in order to keep FANET applications and services more stable and active. To formulate solutions for routing issues in FANETs, the existing mobile ad-hoc network (MANETs) and vehicular ad-hoc network (VANETs) routing protocols are tested. These are mainly characterized into topology-based, swarm-based, and position-based protocols.

Topology-based routing protocols exploit IP addresses to use the existing link information to forward data packets on the optimal path. These protocols require topological information from the communicating UAVs in order to establish and maintain the optimal path. Swarm-based routing is inspired by the natural behavior of social insect communities, such as being self-organized, self-adaptive and cooperative, in order to find the optimal path. However, the main failing of swarm-based routing is high latency due the high mobility of UAVs. In position-based routing protocols, packet forwarding is done on the basis of the geographic position of the UAVs. The main disadvantage of position-based routing is the transmission of stale information about the route during the frequently changing positions of the UAVs. Therefore, we explicitly focus on topology-based routing protocols in this article. These protocols are considered the most significant approach for solving the routing issues in FANETs [16]. Topology-based routing primarily aims to provide an optimal path between UAVs by reducing the control overhead. Thus, this article aims to present a state-of-the art review, based on the simulation analysis among different topology-based routing protocols. This study will help in choosing efficient routing protocols for FANET deployment. Our work is based on the investigation of existing topology-based routing protocols. We do not aim to design new routing protocols. We also do not aim to provide mathematical analysis in this article.

The rest of this paper is arranged as follows. In Section 2, we present an extensive review of the existing topology-based routing protocols, followed by simulation environments and performance evaluation using the OPNET simulator in Section 3. The simulation results and analysis are provided in Section 4. Finally, we present concluding comments in Section 5.

2. Dynamic Routing Protocols in FANETs

In the literature, a wide range of routing protocols exist in traditional ad-hoc networks, which have been suggested for FANETs in order to establish an efficient and reliable communication among the UAVs. However, due to the UAVs explicit characteristics, such as link quality variations and fast movement in the 3D space, most of these routing protocols cannot directly address the requirements of FANETs [17,18]. Routing protocol plays a vital role in consistent end-to-end data delivery and reducing signaling overhead. The challenge of designing an optimal routing protocol is difficult and still being researched, due to the complexity of FANET networks. For this reason, some previous dynamic routing protocols have been implemented and some new ones have been modified for FANETs. These protocols are broadly placed into three major categories: (i) topology-based routing protocols; (ii) swarm-based routing protocols; and (iii) position-based routing protocols. This article is dedicated to the most important topology-based routing protocols, which are assumed to be the most appropriate for this new ad-hoc network family.

Recently, an important number of approaches have been proposed for topology-based routing protocols. This class of routing protocols exploits IP addresses to use the existing link information to forward data packets on the optimal path. These protocols also require topology information for all communicating nodes in order to establish and maintain the optimal route before data transmission. Topology-based routing protocols are furthermore divided into three classes: proactive, reactive and hybrid routing, as shown in Figure 1. All of these routing protocols are intended to improve FANET performance with regard to throughput, minimized delay and resource consumption. In the following subsections, different classes of topology-based routing protocols are presented in detail.

2.1. Proactive Routing Protocols

The proactive routing protocols (PRPs) are also called table driven or active routing protocols. In this kind of routing protocol, the routing table is periodically updated and stored on each UAV, which indicates the whole topology of the network. Thus, the routing paths can be promptly available for transmitting data packets when required. The main advantage of proactive routing protocols is that they contain the most recent information about the routes. However, they introduces additional signaling overhead due to their maintaining up-to-date information about the network. As a result, the throughput of the network may be affected, as control messages are transmitted throughout unnecessarily. Consequently, proactive routing protocols are not suitable for high-mobility and large networks. Moreover, when the connection fails or topological change occurs, PRPs show slow reactions. There are various protocols that represent this class [19].

2.1.1. Destination-Sequenced Distance Vector (DSDV)

This routing protocol is based on the Bellman–Ford–Moore algorithm, with a little modification to render it more suitable for FANETs. In DSDV, each UAV must know absolutely everything about all of the other UAVs connected to the network, due to the up-to-date routing information [20]. This is due to their proactive nature, where the routing table is periodically updated about the complete network. However, these periodic updates can result in routing loops. To solve this problem, DSDV adds sequence numbers with the data packets [21]. The most recently used path with the highest sequence number receives preference over a path with a lower sequence number. The main advantages of DSDV are the practice of sequence numbers and the simplicity, which guarantees the loop-free data transmission among the UAVs [22]. However, the main drawback of this routing protocol is the periodic updates, which create extra signaling overhead during the data transmission. This protocol is not suitable for highly vibrant networks, where the network topology changes more frequently. In addition, it supports single path routing but does not have a multipath routing capability.

2.1.2. Optimized Link State Routing (OLSR)

Optimized link state routing is well known, and one of the most frequently proposed routing protocols for the FANET system, where routing paths are constantly stored and updated in the routing table [23]. Hence, whenever a path is required for data transmission, the protocol immediately determines the path to all the possible destination UAVs without a long wait time [24]. OLSR uses a unique packet, which comprises more than one message to establish a communication process between the UAVs in a network. This unique packet can carry three different type of messages, each one for a specific task: (i) a HELLO message, which is used to transmit periodically to find the neighboring UAVs; (ii) a topology control (TC) message, which is advertised to maintain topological information; or a (iii) multiple interface declaration (MID) message, which accomplishes the multiple interface declaration on a UAV [25]. Hence, the periodic flooding behavior capability of this specific protocol results in a large control overhead.

Compared to the other routing protocols (e.g., flooding routing), OSLR uses the multipoint relay (MPR) mechanism to reduce routing overheads and improve the latency of the network. Therefore, effectively selecting the MPR-UAV becomes one of the most important factors that affects the OLSR’s performance, because during the flooding process, only the MPR-UAV can forward the data packets. The sender UAV selects a set of MPR-UAVs so that it can span two hop neighbors. A source UAV, which selects another UAV as a member MPR-UAV, is called the MPR selector. Figure 2a shows MPR selection by the source UAV. However, one of the most substantial design parameters that affects delays drastically is the number of MPRs. If the number of MPRs shrink, the signaling overhead will reduce consequently. In this context, a new forwarding mechanism is suggested to decrease the number of member MPRs, as shown in Figure 2b. For each MPR sending data packets, the source UAV first tests the distance to the receiver UAV [26]. If the distance is greater than (Dmax/2), which is the maximum distance that can be attained by utilizing a directional antenna, DOLSR is chosen for data transmission. This also occurs if the destination is beyond the omni-directional approach of. Otherwise, OLSR will usually be used.

2.2. Reactive Routing Protocols

Reactive routing protocols (RRP) are also known as on-demand or passive routing protocols, which can be used to discover or maintain a routing path on demand for data transmission. The routing table here is updated only if there is some data to send. As a result, there is no need to calculate a route if there is no connection between the two UAVs. Thus, these routing protocols update routing tables only for those paths that are presently in use [27]. Consequently, it overcomes the overhead issues regarding proactive routing protocols. In this routing model, two type of message are generated: (i) RouteRequest; and (ii) RouteReply messages. A RouteRequest message is initiated from the source UAV to all adjacent UAVs, using the flooding process to calculate the optimal route. Alternatively, a RouteReply message is originated by the receiving UAV and transmits to the sending UAV in a unicast communication manner. There is no compulsion to refresh all the routing tables of the network in this routing approach. RRP is bandwidth efficient, due to the absence of periodic updates. The main failing of RRP is the high latency during the optimal path finding phase.

2.2.1. Dynamic Source Routing (DSR)

This routing protocol is a representative of reactive routing, which allows a network to be self-configured, self-organized and without infrastructure [28]. The main objective when choosing DSR is its reactive nature, and it is mainly designed for multi-hop wireless mesh networks. In DSR, the source UAV only builds routing paths towards the destination UAV when needed. This depends mainly on two processes: (i) route discovery; and (ii) route maintenance. Route discovery is the process used at the source UAV to discover a route, whereas route maintenance is needed when link failures occur. Brown et al. developed first test bed for UAV ad-hoc networks with the dynamic source routing (DSR) protocol [29]. Khare et al. also suggested that DSR is more suitable for FANETs than proactive routing protocols, due to the high mobility of the network [30]. However, due to the repetitive mechanism, reactive path finding before each packet delivery can also be exhaustive. Therefore, this routing protocol is not suitable for scenarios where the topology of the network is highly dynamic.

2.2.2. Ad-Hoc On-Demand Distance Vector (AODV)

An AODV is the improved version of both the DSDV and DSR routing protocols. AODV basically inherits hop-to-hop routing from the DSR protocol and periodic updates from DSDV. Owing to its reactive nature, it discovers a route only when it is needed. AODV does not retain the routes to destinations which are not active during the communication process [31]. This routing protocol basically assigns dedicated time slots to packet transmissions in order to avoid network congestion and improve the packet delivery ratio. Routing with the AODV protocol includes three phases: (i) route discovery; (ii) packet transmitting; and (iii) route maintaining. Whenever a source UAV wishes to send a packet, it first initiates a route discovery phase to locate the position of the intended UAVs. In the packet transmitting phase, it forwards packets over a determined path without routing loops. A route maintenance phase takes place to restore link failure issues. It uses a sequence number to find an updated routing path towards the destination UAV. Moreover, the route’s freshness is maximized with the help of an expiration time. In AODV, the intermediate UAVs also refresh their routing tables. However, because of the vibrant nature of the FANET system, network congestion is an issue with AODV.

2.2.3. Time-Slotted On-Demand Routing

The time-slotted on-demand routing protocol is also recommended for FANETs in the literature [32]. This routing algorithm is basically a time-slotted form of AODV [33]. The time-slotted on-demand protocol sends control packets during dedicated time slots, where only one UAV can transmit its data packets. This routing method not only utilizes bandwidth efficiently, but also has the ability to avoid packet collisions, and as a result the proportional packet delivery ratio is increased.

2.3. Hybrid Routing Protocols

The hybrid routing protocol (HRP) is a combination of both proactive and reactive routing methods. HRP is designed to take the best features from both routing methods and overcome the limitations of both classes. As mentioned in the literature, the reactive routing protocol generally requires additional time to discover the optimal route, and the proactive routing protocol has a massive overhead of control messages. The problems of the large overheads in proactive routing and long end-to-end delay by reactive routing can be overcome. This routing protocol is basically based on the concept of zones. In HRP, intra-zone routing is executed with the help of proactive routing, and inner-zone routing is achieved by means of reactive routing. Hybrid protocols are especially unsuitable for more than 100 UAVs within the zone, because of overlapping.

2.3.1. Zone Routing Protocol (ZRP)

This routing protocol is best suited for the dissimilar mobility patterns of UAVs and is basically based on the concept of “zones” [34]. In the ZRP, each UAV is placed into a zone, and the zones of the neighboring UAVs intersect. The size of the zone is measured by a radius “R” which is the number of UAVs to the perimeter of the zone. By fine-tuning the transmission power of the UAVs, the number of UAVs in the zone can be controlled. The routing of the data packets within the zone is called intra-zone routing, whereas the inter-zone routing is used to send data packets outside of the zone. Intra-zone routing is carried out through proactive routing to maintain the paths, and inter-zone routing utilizes reactive routing mechanisms in order to maintain and find the optimal paths. The delay introduced with the route discovery process is reduced by using border-casting [35]. The border UAVs in a zone only generate reply messages. Inter- or intra-zone routing is decided by the selection of the border UAVs.

2.3.2. Temporarily Ordered Routing Algorithm (TORA)

TORA is highly adaptive and the most suitable on-demand routing protocol for multi-hop networks. Here, each UAV can only update routing tables about the neighboring UAVs. The key feature of using this protocol is to cater the transmission of signaling overhead t highly mobile scenarios and thus minimize the response to topological changes [36]. Moreover, it removes invalid paths and searches for new ones in a single-pass of the distributed algorithm. TORA mostly uses reactive routing, but it also uses a proactive approach in some cases. These routing protocols construct and maintain a directed acyclic graph (DAG) from the source UAV to the destination. Multiple paths are created among the UAVs, based on the DAG, to transmit packets. TORA is selected for the fast computation of updated paths in the case of disconnected paths, and to enhance adaptability [36]. TORA does not use the shortest path algorithm, and lengthy paths are normally selected to minimize signaling overhead. In this routing protocol, each UAV has a parametric value known as “height” and no two UAVs have similar height values in DAG. Data packets move from the upper UAVs to lower UAVs in a top-down approach. In TORA, data packets flow towards the higher-placed UAVs, offering loop-free routing. In the route discovery phase, this height parameter is reverted to the requesting UAV, and in this approach the central UAVs maintain their routing tables according to the incoming path and height information.

Table 1. Comparison of the various topology-based routing protocols for FANETs.

Routing Protocol	Protocol Type	Route Updates	Topology Size	Signaling Overhead	Communication Latency	Bandwidth Utilization
DSDV	Proactive	Periodic	Small	Large	Low	Minimum
OLSR	Proactive	Periodic	Small	Large	Low	Minimum
DOLSR	Proactive	Periodic	Small	Large	Low	Minimum
DSR	Reactive	On need	Large	Small	High	Maximum
AODV	Reactive	On need	Large	Small	High	Maximum
TSODR	Reactive	On need	Large	Small	High	Maximum
ZRP	Hybrid	Hybrid	Both	Average	Low	Medium
TORA	Hybrid	Hybrid	Both	Average	Low	Medium

shows the comparative characteristics of all the aforementioned topology-based routing protocols.

3. Simulation Setup and Performance Metrics

3.1. Simulation Setup

To demonstrate the performance of the topology-based routing protocols presented above, we chose one reactive routing protocol (i.e., OLSR), two proactive routing protocols (i.e., DSR, and AODV) and one hybrid routing protocol (i.e., ZRP). These routing protocols were selected on the basis of having the best performances mentioned in the literature study for FANETs, and to test the basic features of each class of topology-based routing. We used OPNET Modeler 14.1 [37] for the modeling and simulation of our work. We modified the node model of the MANET node for FANETs in the node editor, as shown in Figure 3. We set the data rate to be 11 Mbps and 54 Mbps for all the UAVs, according to the IEEE 802.11 g standard. Their working was implemented in the function block of the process model editor. We simulated various scenarios in which the quantity of UAVs was selected to be 30 and 100 nodes. The speed of the UAVs was set to be 25 m/s and 60 m/s, respectively, with the random waypoint mobility model. The UAVs were placed in the area of 1000 m × 1000 m and 2000 m × 2000 m. The altitude of the UAVs was kept constant to 40 m for all the varying scenarios. All metrics are displayed in averages. The rest of the parameters are enlightened in

Table 2. Simulation parameters.

Parameter	Value
Area Dimensions	1 km × 1 km, 2 km × 2 km
Altitude of UAVs	40 m
Number of UAVs	30, 100
Directional Gain	10 dBi
Frequency	2.4 GHz
Physical Characteristics	IEEE 802.11 g
Data Rates	54 Mbps
Packet Interval (s)	Exponential (1)
Packet Size (byte)	1024
Simulation Time	200 s, 1200 s
Node Type	Mobile
Mobility Model	Random Way point
Speed of UAVs	25 m/s, 60 m/s
Reception Power Threshold	−95 dBm
Transmission Power	0.005 W

for further details.

3.2. Performance Metrics

This section describes the performance of the topology-based routing protocols on the basis of the following performance metrics:

3.2.1. Throughput (bits/s)

The average data rate of the successful data packets or message delivery from the source flying node to the destination flying node over a communication link in a particular unit of time is called throughput. Mathematically, throughput can be determined using the following Equation (1):

$$\mathrm{Throughput}= \frac{ \mathrm{N} \times \mathrm{S} \times 8}{\mathrm{T}}$$

(1)

where N is assumed to be the number of successful packets transferred, S is the size of the packet, and time duration is the existing higher throughput, which is a requirement and characteristic of any network.

3.2.2. Delay (s)

Delay is the average time taken for data packets to be transmitted from the source flying node to the destination flying node across the network. Delay is an important design factor and performance characteristic of a communications network. End-to-end delays contain the processing, queuing and transmission delay of the link in a network. The average end-to-end delay can be shown mathematically, as in Equation (2):

$${ \mathrm{D}}_{\mathrm{end}-\mathrm{to}-\mathrm{end} }={\displaystyle \sum }_{\mathrm{t}=1}^{\mathrm{N}}\left({\mathrm{T}}_{\mathrm{t}}+{\mathrm{R}}_{\mathrm{t}}+{\mathrm{B}}_{\mathrm{t}}+{\mathrm{P}}_{\mathrm{rt}}\right)$$

(2)

where,

• T_t = Transmission time.
• R_t = Retransmission time.
• B_t = Buffer time.
• P_rt =Processing time.

3.2.3. Load (bits/s)

Network load is the total number of packets transferred from the upper layer to the MAC layer. FANETs routing traffic are affected by the high network load, and by increasing the collisions of the control packets, hence slowing down the packet delivery ratio in the channel. The exploited bandwidth, processing time, and buffer availability at intermediate nodes results in the network load.

4. Results and Analysis

4.1. Throughput (bits/s)

Figure 4a–f illustrates the performance of a network in terms of throughput, by varying the number of UAVs, speed, and area dimensions. The X-axis represents simulation time and the Y-axis indicates the throughput in bits per second. When the number of UAVs increased, the throughput also increased, and the performance of the network rose. When comparing the throughput by each of these protocols, DSR had high throughput when the number of UAVs was lower (i.e., 30) in both cases, when the speed of the UAVs was 25 m/s and 60 m/s as shown in Figure 4a,b respectively. This is due to their reactive nature, which renders DSR more suitable for FANETs in a highly mobile network, and also due to the use of a route cache and overhearing features. The AODV outperformed DSR, OLSR and ZRP, with the number of UAVs increasing to 100 in both scenarios, when the speed of the UAVs was set to be 25 m/s and 60 m/s, respectively, as shown in Figure 4c–f. This is due to the fact that AODV assigns dedicated time slots for packet transmissions in order to avoid network congestion. Moreover, by decreasing the area dimensions (i.e., 1 km × 1 km), high throughput was achieved, as shown in Figure 4c,f. OLSR had average performance in all scenarios, whereas ZRP had the worst throughput because of extra routing overhead.

4.2. Delay (s)

Figure 5a–f demonstrates the performance of a network in terms of end-to-end delay by varying the number of UAVs, speed, and area dimensions. The X-axis represents the simulation time and the Y-axis indicates the delay in seconds. When the number of UAVs increased, the end-to-end delay decreased. This is due to the increased probability of packets being routed instead of being apprehended in suspension buffer. When comparing the delay for each of these protocols, DSR had the highest delay in all scenarios except when the area was smaller (i.e., 1 km × 1 km). This was because when a route request (RREQ) was sent, the destination replied to all RREQs that it delivered, which made it slower when determining the least congested route. AODV also exhibited a higher delay due to its reactive nature, where routes were assigned on-demand. OLSR had average performance in terms of delay in all scenarios, due to its proactive characteristics. ZRP had the lowest delay because of the use of the border-casting mechanism.

4.3. Network Load (bits/s)

In Figure 6a–f, the graph represents the performance of a network in terms of network load by varying the number of UAVs, speed, and area dimensions. The X-axis represents simulation time and Y-axis indicates the load in bits per second. DSR had the highest network load in scenarios where the speed of the UAVs was high. This was due to the repetitive path finding by the reactive manner before each packet delivery in a highly dynamic network. ZRP had the lowest network load for the scenarios, where the nodes were placed in the area of 2 km × 2 km. AODV had a constant network load for the same number of UAVs, despite the fact of changing speeds and area dimensions of the UAVs. OLSR consistently had the minimum network load in all scenarios, due to the advantage of the multi-point relay mechanism.

5. Conclusions

Recently, FANETs have evolved into an emerging area of research. Such networks are characterized by high mobility, frequent topology changes, and 3D-spatial movement of the UAVs, which constitutes a challenge to the routing protocol. For this reason, choosing suitable and reliable routing protocols is essential to authenticate robust communication amongst the UAVs.

In this paper, we investigated various topology-based routing protocols in the context of FANETs. We discussed them along with their method of working and limitations. We also provided a brief qualitative review of the aforementioned routing protocols on the basis of important parameters such as mobility, traffic density, routing overhead and the packet forwarding mechanism. All of these factors affect the performance of the flying ad-hoc networks. We also provided a simulation-based study of the various most-significant topology-based routing protocols in terms of throughput, end-to-end delay, and network load. We hope this study will help network engineers when choosing appropriate routing protocols in different kinds of scenarios for FANET deployment. We also believe that FANETs will be a ubiquitous technology in the future.