Sage Journals: Discover world-class research

Abstract

Unmanned aerial vehicle is one of the main announced use cases of 5G/IMT2020, which is expected to have various applications in many fields. These devices have limited capabilities in terms of energy and processing. Due to the complex structure of unmanned aerial vehicle networks and the high mobility constraints, design of efficient routing protocol, for supporting such network, is a challenge. Thus, efficient routing of data among unmanned aerial vehicles between source and destination is an important issue in designing unmanned aerial vehicle networks. Proactive routing protocols are one of the main categories of routing protocols developed for mobile ad hoc networks and vehicular ad hoc networks. Optimized link state routing protocol is one of the most common proactive routing protocols that has been modified to support unmanned aerial vehicle networks, considering high mobility feature of the network. In this work, we propose a latency and energy-efficient proactive routing protocol for dense unmanned aerial vehicle networks, with high-density devices, based on optimized link state routing protocol algorithm, referred to as multi-objective optimized link state routing protocol. The proposed routing protocol is topology aware and can be used for low-latency and high-mobility applications. The proposed multi-objective optimized link state routing protocol routing algorithm considers all modified versions of optimized link state routing protocol and introduces a novel method for selecting multipoint relay nodes that considers the traffic load on the communication channel and the load on each unmanned aerial vehicle node. Moreover, the proposed algorithm considers the communication link stability and the energy constraints. The system is simulated over a reliable environment for various scenarios, and it is compared to the original optimized link state routing protocol and its modified versions. Simulation results indicate that the proposed protocol achieves higher efficiency in terms of latency, energy, and reliability.

Keywords

Unmanned aerial vehicle routing protocols latency energy mobility communication link

Introduction

With the recent development of communication systems and recent-developed communication paradigms, unmanned aerial vehicles (UAVs) are expected to have dramatic applications in many fields.¹ The near release of fifth generation cellular system (5G/IMT2020) is expected to assist UAV networks and enable the development of new applications. UAV is defined by the 3rd Generation Partnership Project (3GPP) and International Telecommunication Union (ITU) as a main use case of 5G/IMT2020; this pushes the development, as well as enhances and optimizes the UAV networks to enable such expected applications.^2,3

UAV networks can be classified, based on the network application, into three main categories: UAV–UAV interaction, UAV–ground node interaction, and UAV–VANET (vehicular ad hoc network) interaction.⁴ The first application category is the applications that require the cooperation and interaction between UAVs only, without any communication with any ground nodes. In this kind of applications, the deployed UAVs usually work together to perform a common task.⁵ These applications always require the deployment of high-density UAVs, with limited task duration. These applications include remote sensing, remote localization, target detection, and catastrophic monitoring.⁶ The second class of UAV applications is the applications that require the cooperation and interaction between UAV and ground node. These applications include military applications, mission critical applications, and mobile-assisted applications.⁷ The ground nodes deployed for this category of applications are either fixed stations or mobile nodes. Such kind of applications requires the deployment of medium- to high-density UAVs. The third category is the applications that require the interaction between UAV and VANET. This represents a recent paradigm that considers the use of UAVs to assist ground vehicular communications such as traffic monitoring and route assessment applications.⁸ This kind of applications requires deploying low density of UAVs at low attitudes.

Designing of ad hoc UAV networks (some referred to as flying ad hoc network (FANET)) faces a lot of challenge that faces the design of UAV networks; these challenges include the following:^9,10

Mobility: UAV nodes are always deployed with high mobility that put constraints on designing such networks. The relative speed between deployed UAV nodes and between UAV nodes and ground nodes, either stationary or mobile, must be considered.¹¹

Topology: UAV networks suffer from dynamic topology changing due to high mobility of deployed nodes. Undetermined topology represented a challenge that should be considered while designing such networks.¹²

Energy: UAVs have limited capabilities in terms of energy; this constraint should be considered especially for micro-UAVs. Designing UAV networks and comprised algorithms should be efficient in terms of energy to enable the stable operation of the network for a long time.

Connectivity: This constraint should be considered for low-density UAV networks, since deployed nodes are always distantly separated and the probability that there are unconnected nodes become higher.

For general ad hoc networks, one of the main challenges is the design of routing protocols; in a similar way, designing a reliable routing protocol for ad hoc UAV networks is a challenge, mainly due to high mobility and other introduced features.¹³ Due to high mobility of nodes, routing protocols for UAV networks should be able to support this mobility and introduce alternative routes quickly and efficiently.¹⁴

In this work, we develop a proactive energy and latency efficient routing protocol for ad hoc UAV networks (i.e. FANET). The proposed protocol represents a modified version to one of the common proactive routing protocol, which is the optimized link state routing protocol (OLSR).¹⁵ The proposed protocol considers the high mobility and nature of the UAV networks, and also it considers all modified versions of OLSR. The protocol is referred to as multi-objective OLSR (MO-OLSR) that introduces a novel mechanism while selecting multipoint relay (MPR) nodes. The “Background and related works” section provides a background and literature review of the developed routing protocols for UAV networks. In the “MO-OLSR routing protocol” section, the proposed MO-OLSR routing protocol is introduced, with the proposed novel algorithm of selecting MPRs. The “Performance evaluation” section provides the simulation process and the obtained results, with the analysis of these results.

Background and related works

The current developed routing protocols for MANETs (mobile ad hoc networks) and VANETs cannot be deployed for UAV; instead, new routing protocols or modified versions of the existing protocols for VANETs and MANETs should be deployed.¹⁶ This is because of the very high mobility of the UAVs, which in turn causes a dramatic change in network topology, and also the deployment scenarios. Thus, data forwarding schemes of MANETs and VANETs have to consider the mobility models of UAVs and also the deployment scenarios.¹⁷

Routing protocols for ad hoc UAVs, as well as routing protocols for MANETs and VANETs, can be categorized into two main classes: static routing protocols and dynamic routing protocols.4,16,18 Static routing protocols are single-hop protocols that are developed mainly for static environment with fixed predefined topology and cannot be used for dynamic environments. In this type of routing protocols, UAVs act as packet carriers that forward data packets, while traveling from source point to destination. Static routing protocols employ static routing tables with no available updates. The main features of these protocols are the lightweight and simplicity, while these protocols are dedicated with certain applications that ensure fixed topology.^19,20

Dynamic routing protocols are multi-hop routing protocols that are mainly developed for dynamic environments with high-rate topology changing. Each UAV employs a routing table that is updated based on the network topology and status. Each UAV node, based on multi-hop routing protocol, has to discover the surrounding nodes through a discovery process to build its routing table. Data are forwarded hop by hop from the source until it reaches the destination; however, the main challenge is how to arrange these hops or how to find the optimal next hop route.²¹ There are many criteria and objectives that rule the process of selecting next hop route such as energy, latency, and link budget.²²

Based on the selection process of the next hop, dynamic routing protocols for UAVs can be subcategorized into two subgroups: position aware and topology aware.^16,18 Position aware dynamic routing protocols for UAVs are those protocols that are built based on the information of location of each UAV. Topology aware dynamic routing protocols for UAVs consider the dynamic change of the network topology, which represents a feature of the plurality of UAV’s applications—since most applications consider ultra high-mobility deployment scenario of UAVs. Developed topology aware dynamic routing protocols can be viewed as active routing, passive routing, and hybrid routing.

Active routing—topology aware dynamic routing protocols, also called proactive routing protocols—is used for low-latency applications, since the routing table is updated continuously. Once a source UAV has data to be transmitted, the routing path is extracted instantly. The main problem with these routing protocols is the packet overhead, while this problem, to a satisfied level, has been improved by considering reduction of number and size of control packets such as the mechanism of OLSR routing protocol.^15,23

Unlike active routing, passive routing—topology aware dynamic routing protocols, also called reactive routing protocols—suffers from long delay, since the routing path is estimated only when the source has data to be sent.²⁴ In this way, the number of control packets is reduced and thus the packet overhead is reduced. Hybrid routing—topology aware dynamic routing protocols—employs features of active and passive routing protocols to achieve better performance for moderate mobility and latency applications.²⁵ Table 1 indicates the topology-dedicated routing protocols recommended for applications with heterogeneous key performance indications (KPIs) in terms of latency and mobility.

Table 1.

Subcategories of topology-dedicated dynamic routing protocols for different UAV’s applications.

Topology-dedicated routing protocol	Latency	Mobility
Active routing	Ultra low/low	Low/moderate
Passive routing	High	High
Hybrid routing	Moderate/low	Moderate/high

Many literatures consider the recent-developed routing protocols for ad hoc UAV networks; the recent work, in this context, can be founded in previous studies.^4,16,26 In this work, we consider developing a proactive routing protocol based on OLSR and modified versions, mainly DOLSR (directional optimized link state routing protocol) and ML-OLSR (mobility and load aware OLSR).

MO-OLSR routing protocol

In this part, the proposed multi-hop/multi-objective routing protocol for dense UAV networks is introduced. The proposed algorithm is a proactive routing protocol that is developed on top of the OLSR, which is one of the most common routing protocols used for ad hoc networks. The proposed routing algorithm considers the limitations of the OLSR and also considers the modified algorithms of the OLSR that have been developed.²⁷ The key operation and performance of the OLSR protocol is the selection of intermediate points associated with each node to forward data and control packets; these nodes are defined as MPRs. The performance of the routing algorithm depends mainly on the selection process of MPRs. Thus, all modified versions of OLSR protocol mainly consider enhancing the MPR selection process, by considering new metrics that are ignored by the original OLSR.

The proposed algorithm considers mainly optimizing the selection process of MPR in terms of new objectives (e.g. energy, traffic load, node load, and latency). Table 2 provides a comparison between proposed algorithm, OLSR algorithm, and common modified versions of OLSR, in terms of considered metrics. The proposed algorithm is termed as MO-OLSR. Furthermore, in MO-OLSR, the addresses of both source and destination nodes are considered to be physical addresses instead of logical addresses. In traditional control packets, the plurality of the used addresses are either logical or, for certain applications, both physical and logical; however, the proposed algorithm uses the physical address to overcome the problem of disconnectivity and does not deploy both addresses to avoid packet overhead.

Table 2.

Metrics-based comparison between proposed MO-OLSR algorithm and OLSR with its modified versions.

No.	Protocol	Metrics (for MPR selection)
1	OLSR¹⁵	Packet overhead
2	DOLSR²⁷	Packet overheadEnd-to-end latency
3	ML-OLSR²⁸	Packet overheadMobility (stability of communication link, reachability degree)Traffic load
4	MO-OLSR	Packet overheadEnd-to-end latencyMobility (stability of communication link)Traffic loadNode load (buffer occupancy)Energy

MO-OLSR: multi-objective optimized link state routing protocol; OLSR: optimized link state routing protocol; MPR: multipoint relay; DOLSR: directional optimized link state routing protocol; ML-OLSR: mobility and load aware OLSR.

Metrics considered for MPR selection

Stability of communication link

Due to the mobility of UAV nodes and relative mobility between nodes, there is a dynamic change in network topology and thus, the stability of communication link between nodes should be checked and ensured. In the proposed routing protocol, the communication link stability is estimated based on the methods developed in Yu et al.²² and Li et al.²⁹ Deploying stability check function represents an important method for achieving higher performance of UAV routing protocol, as it allows the routing algorithm to continuously delete and predict the unsuitable links (e.g. links exposed to failure).³⁰

Each UAV node receives the location information of all neighboring nodes and then calculates the distances between the node and all neighboring nodes. The stability of the communication link between node and each neighbor node can be statistically calculated, using Chebyshev inequality, based on the distances to neighboring nodes.³¹ The Chebyshev inequality, for any discrete variable x (e.g. discrete samples or data), ensures that

$P {| x - E (x) | < ε} \geq 1 - \frac{Var (x)}{ε^{2}}$ (1)

where E(x) is the expected value of the discrete random variable x, ε is an arbitrary positive number, and Var(x) is the variance of the discrete variable x. Chebyshev inequality indicates the relation between the current value of the discrete variable x and its expected valued based on the variance of the variable. For small values of variance of the variable x (i.e. Var(x) << 1), the expected value of x tends to be more close to the current value. For zero variance of discrete variable x (i.e. Var(x) = 0), the expected value of x (E(x)) is the same as the current value of x, which represents the most stable case for the random variable x. Thus, the high stability of the discrete variable x can be ensured for low variances of x. The variance of the discrete random variable x, with n samples, can be calculated as following

$Var (x) = E (x^{2}) - E (x)^{2}$ (2)

$Var (x) = (\sum_{i = 1}^{n} \frac{{x_{i}}^{2}}{n}) - {(\sum_{i = 1}^{n} \frac{x_{i}}{n})}^{2}$ (3)

In Chebyshev inequality, if the random variable is set to the distance between UAV and neighbor node, then the current value of distance between node A and B can be compared to the expected value of this distance. Thus, the smaller the value of variance of distance, the less the relative mobility between two considered nodes. This means that the communication link between two considered nodes is more stable. For distance variance, between nodes A and B, of one, the link is considered to be completely unstable and the neighboring node should be deleted from the routing path; this represents the worst case. In the other side, the best case for the link stability is when the distance variance indicates zero value, which means that there is no relative mobility between nodes and the relative speed between the two UAVs is zero; the link between A and B, in this case, is defined to be completely stable.

Thus, the link stability function of the link L_k, between node A and B, is SF_Lk(d_k) and can be calculated as a function of distance variation as following

$S F_{Lk} (d_{k}) = Var (d_{k}) = (\sum_{i = 1}^{n} \frac{{(d_{k})}_{i}^{2}}{n}) - {(\sum_{i = 1}^{n} \frac{{(d_{k})}_{i}}{n})}^{2}$ (4)

where d_K is the distance between UAV node A and UAV node B. The smaller the value of SF_Lk(d_k), the higher the stability of the communication link L_k.

Network congestion

In order to achieve higher network performance, in terms of congestion, the network load should be managed and balanced. Using traditional available routing protocols, for UAV networks, degrades the network congestion performance, because the dynamic nature of the environment due to high mobility of deployed nodes can produce network congestion at high level and may lead to failure. Thus, routing protocols for UAV networks should consider the network congestion and deploy methods to avoid such highly expected performance degradation.

For the proposed routing protocol, a method for avoiding network congestion is considered based on keeping some network congestion metrics at a level that achieves the required congestion performance. The considered metrics are the main metrics that measure the network congestion for heterogeneous ad hoc networks. These metrics include the following:^32,33

Buffer occupancy;

Load balancing:³⁴

Communication channel load;

Node load;

Neighboring nodes’ load.

Buffer occupancy

The buffer occupancy of the UAV, B(t), is a measure of network congestion, and it can be calculated by comparing the MAC (medium access control) layer interface queue length to the maximum MAC layer interface queue length of the node.³⁵ Each node should periodically estimate its buffer occupancy

$B_{n_{i}} (t) = \frac{Q_{n_{i}} (t)}{Q_{\max}}$ (5)

where Q_i(t) is the MAC layer interface queue length of the n_i UAV node and Q_max is the maximum MAC layer interface queue length. The UAV node is considered to be with high buffer occupancy, for B(t) higher than 65%.³⁶ For practical situations, the average buffer occupancy B_av(t) is calculated by averaging buffer occupancy over a certain period of time

$B_{n_{i} - av} (t) = \frac{\sum_{m = 1}^{N} B_{n_{i}} (t_{m})}{N}$ (6)

where N is the total number of measures taken in a certain period of time.

Channel load

The load on the communication channel is also an important metric for the network congestion and thus, for reliable routing protocol with high network congestion performance, the load on the communication channel should be kept at minimum level and should not exceed certain levels that affect the network performance and reliability. In another word, the load should be balanced by distributing traffic among network in an efficient way.³⁷ One of the main challenges in balancing load for UAV networks is the high mobility that features these networks. Channel load can be defined as the acting traffic load on a certain channel that accessed by multiple nodes.³⁸

For ad hoc architecture of UAV networks, in order to avoid conflicts of packets when transmitting messages between distributed nodes, the distributed UAV nodes are assumed to use the common IEEE 802.11 as the MAC protocol.³⁹ IEEE 802.11 works based on the distributed coordination function (DCF) mechanism, which deploys the carrier sense multiple access/collision avoidance (CSMA/CA) technique.⁴⁰ This requires UAV nodes to sense the shared medium to check if another node is transmitting. The sensation of the medium turns the UAV node to transmit if the medium is available or to wait if the medium is recorded to be busy. In the proposed MO-OLSR algorithm, a modified version of IEEE 802.11 that supports smart directional antennas, with reduced packet interval, is considered.⁴¹

When the channel is busy, UAV node cannot transmit and thus, packets have to be buffered. This represents a load on the node, when the waiting period become long and more packets arrive to the buffer. Routing protocol has to consider this load to avoid performance degradation. To calculate the traffic load on a certain communication link, the proposed method in Zheng et al.⁴² is modified for UAV networks. The traffic load on an UAV node (L_T) can be calculated as following

$L_{T} (n_{i}) = \sum_{j = 1}^{z_{ni}} L_{j}$ (7)

where L_T(n_i) is the traffic load on the n_i UAV node, Z_ni is the total number of intermediate links passed through the node n_i, and L is the intermediated link passed through the node n_i. The traffic load on a communication link between two nodes can also be calculated as following

$L_{T} (L_{x, y}) = \sum_{k = n_{x}}^{n_{y}} L_{T} (k)$ (8)

where L_T(L_x,_y) is the load on the communication link between the UAV n_x and the UAV n_y. This load should be managed and kept below a threshold value to maintain high performance and reduce the network congestion level. For this purpose, the proposed routing algorithm defines a new parameter referred to as the link load threshold (LL_th), which represents the maximum load that an active link, between any two UAV nodes in the network, can have. Thus, the control packet of the proposed routing protocol deploys a path counter (PC) to count for the active links passing with an UAV node.

MO-OLSR routing protocol for UAV networks

The proposed routing protocol consists of two main phases: the discovery phase and the topology control (TC) phase. The TC phase consists of two main processes: MPR set selection and the TC message broadcast.

Annotation

Before introducing the proposed processes of the proposed MO-OLSR routing protocol, the considered parameters are first defined. Notion of the considered variables and parameters are presented in Table 3. The set of UAV nodes deployed in the networks is n, n = {n₁, n₂, n₃, …, n_N}. Each UAV node n_i has a set of one-hop neighbor nodes hⁿⁱ, hⁿⁱ = {h₁ⁿⁱ, h₂ⁿⁱ, h₃ⁿⁱ, …, h_Mⁿⁱ}, and a set of two-hop neighbor nodes hsⁿⁱ, hsⁿⁱ = {hs₁ⁿⁱ, hs₂ⁿⁱ, hs₃ⁿⁱ, …, hs_fⁿⁱ}. The set of intermediate links passed through a node ni is Lⁿⁱ, Lⁿⁱ = {L₁ⁿⁱ, L₂ⁿⁱ, L₃ⁿⁱ, …, L_Sⁿⁱ}. The main processes of the MO-OLSR routing protocol is introduced in the simple flowchart presented in Figure 1.

Table 3.

Key notations.

Notation	Description
n	Set of deployed UAVs
N	Total number of deployed UAV nodes
h ⁿⁱ	The set of one-hop neighbor nodes to the UAV n_i
M	Maximum size of hⁿⁱ
hs ⁿⁱ	The set of two-hop neighbor nodes to the UAV n_i
K	Maximum size of hsⁿⁱ
MPR ⁿⁱ	The set of multipoint relay points to the UAV n_i
f	Maximum size of MPRⁿⁱ
L ⁿⁱ	The set of intermediate links passed through the node n_i
S	Maximum size of L_ni
L_T(x, y)	Traffic load on the communication link between nodes x and y
MPR_V ₁ ⁿⁱ	The set of the first version of multipoint relay points to the UAV n_i
MPR_V2ⁿⁱ	The set of the second version of multipoint relay points to the UAV n_i
MPR_V ₃ ⁿⁱ	The set of the third version of multipoint relay points to the UAV n_i
MPR_V ₄ ⁿⁱ	The set of the fourth version of multipoint relay points to the UAV n_i
D_L-T(L(x, y))	Binary decision variable of the type of link between nodes x and y
D_L-E(L(x, y))	Binary decision variable of the existence of a direct communication link between nodes x and y
D_S(L(x, y))	Binary decision variable of the stability of link between nodes x and y
D_C(L(x, y))	Binary decision variable of the load of channel between nodes x and y
D_B(ni)	Binary decision variable of buffer occupancy of the UAV node n_i
D_E(ni)	Binary decision variable of energy of the UAV node n_i
E_th	Threshold level of energy of UAV node
LL_th	Threshold level of communication link load
I	Mode indicator variable
B_ni	Buffer occupancy of the UAV node n_i

UAV: unmanned aerial vehicle.

Figure 1.

Flowchart of the proposed MO-OLSR routing protocol.

To facilitate the proposed algorithm operation, binary decision variables are used for deciding the following

1. Link type

$D_{L - T} = {\begin{matrix} 1, for symmetric link \\ 0, for asymmetric link \end{matrix}$

2. Link existence between two nodes

$D_{L - E} = {\begin{matrix} 1 if direct link exists \\ 0 if no directlink exists \end{matrix}$

3. Energy decision

$D_{E} (n_{i}) = I (E_{ni}, E_{th}) = {\begin{matrix} 1 if E_{ni} \geq E_{th} \\ 0 if E_{ni} < E_{th} \end{matrix}$

4. Node load decision

$D_{B} (n_{i}) = {\begin{matrix} 1, B_{ni} \leq 0.65 \\ 0, B_{ni} > 0.65 \end{matrix}$

5. Channel load decision

$D_{C} (L_{T} (x, y)) = I (L_{T} (x, y), L L_{th}) = {\begin{matrix} 1 if L_{T} (x, y) \leq L L_{th} \\ 0 if L_{T} (x, y) > L L_{th} \end{matrix}$

6. Link stability decision

$D_{S} = {\begin{matrix} 1, for stable link \\ 0, for unstable link \end{matrix}$

Discovery process

Each UAV node has to discover the surrounding neighbors by periodically broadcasting a Hello message to all surrounding nodes to tell them the one-hop neighboring list and update it. The Hello message is broadcasted so that all surrounding neighbor nodes, within the communication range, receive it. Each UAV node uses the received Hello messages to form and update their routing tables, and to select and modify the appropriate MPR sets. If the node receives a message that contains its address, it registers the link to the source node of the message as symmetric and it extracts the other information in the message to update its routing table. However, if the node receives a message that does not contain its address, it indicates that it is moved near to a new neighbor and it registers the dedicated link as asymmetric. The main reason for Hello message is to perform the following:

Neighbor discovery;

Link discovery and sensing;

Selection of MPR sets.

The format of the considered Hello message is illustrated in Figure 2. The proposed message represents a modified version of the original OLSR protocol and its modified versions (e.g. DOLSR and ML-OLSR). The proposed routing protocol assumes that UAVs are heterogeneous and randomly distributed over the network.

Figure 2.

Formats of Hello message.

For better illustration of the proposed discovery process, an example is considered as introduced in Figure 3. Figure 3 illustrates the discovery process for a considered UAV node (n₃) with four old neighbors (F₁, F₂, F₃, F₄) and a new neighbor (F_new). All neighboring UAV nodes to the node n₃ receive its broadcasted message, and the four old neighbors find their address so they are registered as symmetric. While node F_new does not find its address in the received message, it updates its routing table and considers the link to n₃ as asymmetric and as a response it sends a Hello message to n₃ announcing n₃ as asymmetric neighbor. The UAV n₃ receives the Hello message and finds its address, so it considers F_new as a neighbor and registers the link to F_new as symmetric and considers it as F₅. It sends another Hello message with the new information that contains the address of F_new to the F_new that in turn updates it routing table by considering n₃ as a symmetric neighbor.

Figure 3.

Example of the discovery process for UAV network with six nodes.

MPR selection

MPRs are intermediate nodes in the communication path between source and destination nodes; these nodes are selected by other nodes that will transmit their data via these MPRs. MPR nodes are either one or two communication hops away from its selectors. The main objective of selecting MPRs is to relay data packets and control packets. Since the selection of the MPR is the key performance of the proposed routing protocol, we develop a novel method for MPR selection that considers the route stability, network congestion, latency, and energy efficiency.

Based on the OLSR, the UAV n_i considers the neighbor node F_j to be an MPR, if the link between n_i and F_j is registered as symmetric. Thus, for MPR selection, each UAV node should have link state information of all links to all one-hop and two-hop neighbor nodes. The protocol defines two sets of MPRs: one-hop set and two-hop set. The one-hop MPR set is selected so that all set members can reach the two-hop nodes. MPRs are deployed so as to reduce the broadcasted information among network. OLSR did not consider other metrics while selecting MPRs.

Modified versions of OLSR developed for UAV networks consider, at least, one more metric than OLSR as previously introduced. In the proposed routing protocol, various metrics are considered for MPR selection; these metrics represent combination of all metrics considered by OLSR and modified versions with the consideration of energy, latency, and UAV node load as new metrics.

Algorithm 1 introduces the proposed method for MPR selection that represents the most critical step in routing protocol and the main factor that affects its performance. Each UAV node discovers and estimates its one- and two-hop neighbor nodes sets (hⁿⁱ and hsⁿⁱ). Then the UAV node has to select MPR set through the steps introduced in algorithm 1. The first step is to consider only one-hop nodes with only symmetric links with a connection to at least one two-hop node and exclude other neighbor nodes. The selected nodes represent the first version of MPR (MPR_V₁ⁿⁱ) that has to be checked for other metrics validation. For all members of the first version of MPR, the energy and buffer occupancy constraints should be checked. Each member node of MPR_V₁ should has energy level higher than the threshold level of energy that decided by the network operator to maintain the network operation at a high level of energy performance, otherwise the node is excluded from MPR_V₁ set. The remaining members of MPR_V₁ represent the second version of MPR (MPR_V₂).

Algorithm 1. MPR selection algorithm
1:	Initialize UAV network with n_i
2:	While (t ≤ t_max) do
3:	Find hⁿⁱ and hsⁿⁱ sets
4:	C = 1
5:	For (j = 1: j ≤ M) do
6:	For (u = 1: u ≤ K) do
7:	if (D_L-T(L(n_i, h_jⁿⁱ)) == 1 & D_L-E(L(h_jⁿⁱ, hs_uⁿⁱ)) == 1)
8:	MPR_V ₁ ⁿⁱ(C) = h_jⁿⁱ
9:	C++
10:	end if
11:	end for
12:	end for
13:	Reset C
14:	For (j = 1: j ≤ X₁) do
15:	if (E_MPR-V_1(j) ≥ E_th)
16:	MPR_V ₂ ⁿⁱ(C) = MPR_V₁ⁿⁱ(j)
17:	C++
18:	end if
19:	end for
20:	Reset C
21:	For (j = 1: j ≤ X₂) do
22:	if (D_B(MPR_V₂ⁿⁱ(j))) == 1)
23:	MPR_V ₃ ⁿⁱ(C) = MPR_V₂ⁿⁱ(j)
24:	C++
25:	end if
26:	end for
27:	Reset C
28:	For (j = 1: j ≤ X₃) do
29:	if (D_S(L(n_i, MPR_V₃ⁿⁱ(j))) == 1 & D_C(L(n_i, MPR_V₃ⁿⁱ(j))))
30:	MPR_V ₄ ⁿⁱ(C) = MPR_V3ⁿⁱ(j)
31:	C++
32:	end if
33:	end for
34:	MPR ⁿⁱ←MPR_V₄ⁿⁱ
35:	Omit duplicated connections and modify MPRⁿⁱ
36:	t←t + 1
37:	Return MPRⁿⁱ

Members of MPR_V₂ are checked against buffer occupancy to avoid overloading and long delay based on the previous introduced method. Nodes that have negative buffer occupancy decision are excluded from MPR_V₁ set. The remaining members of MPR_V₂ represent the third version of MPR (MPR_V₃). The stability and load of links between each member of MPR_V₃ and the UAV are checked, and nodes with unstable or overloaded links are excluded from MPR_V₃ set. The remaining nodes in MPR_V₃ represent the MPR_V₄ set that is optimized by omitting duplicated connections to two-hop nodes, while the omission process is done in terms of latency performance (i.e. node with higher latency is omitted and the other with lower latency stay as MPR). The remaining nodes of the optimized MPR_V₄ represent the optimal MPR set for the UAV that achieves the following:

High network stability;

High energy performance;

Reduced packet overhead;

Reduced network congestion;

High latency performance.

TC

For building and controlling the topology of the network, considering mobility constraints, each UAV node should periodically broadcast TC message and build the network topology based on the mechanism introduced in the study by Zheng et al.²⁸ The format of the TC message is introduced in Figure 4. The TC message includes the address of the UAV node n_i, addresses of the member nodes of MPRⁿⁱ, and distinct sequence number associated with each message.

Figure 4.

TC message format.

MO-OLSR is an OLSR-based proactive routing protocol that should always have available routing table with routes to all available nodes in the network and periodically update its entries based on the network status. Each UAV node in the network builds its routing table and fills its entries by extracting the required information from the Hello messages and TC messages.

Performance evaluation

In this part, the proposed MO-OLSR is simulated over a reliable environment and compared to the original OLSR and other two benchmark modified versions (DOLSR and ML-OLSR).

Simulation set-up

In previous proposed works, OLSR is deployed for UAV networks and its performance has been compared to other proactive and reactive routing protocol; thus in this work, we consider only comparing the proposed algorithm with OLSR and its modified versions. To this end, we built our own discrete event–based simulator over the MATLAB environment. The considered simulation parameters are introduced in Table 4. For evaluating the performance of the proposed MO-OLSR routing algorithm, various performance metrics and simulation cases are considered. Three simulation cases are considered; in each case, the network is deployed with different number of UAV nodes. Table 5 indicates the number of deployed nodes in each case. The considered metrics for the performance evaluation include the following:

Total number of selected MPRs;

End-to-end latency;

Packet delivery ratio (PDR);

Energy consumption.

Table 4.

Simulation parameters.

Parameter	Value
Simulation time (t_s)	1000 s
Field area (A)	5 km × 5 km
Number of nodes (N)	Based on the simulation case as indicated in Table 5
Channel type	Wireless channel
Traffic type	CBR
MAC protocol	IEEE 802.11
Topology table validity time	15 s
TC message interval	5 s
Hello message interval	2 s
Neighbor table hold time	6 s
Packet size	128 byte
Buffer size	300 packet
Node velocity	€ (10, 50) m/s
Antenna mode	Directional

TC: topology control; MAC: medium access control; CBR: constant bit rate.

Table 5.

Simulation cases.

Case	Case 1	Case 2	Case 3
N	40	60	80

Simulation results and analysis

The number of selected MPR nodes represents an important parameter while considering the performance of OLSR-based routing protocol, since maintaining the same performance with reduced number of MPR is preferred—as it achieves higher efficiency in terms of packet overhead and bandwidth utilization. To this end, the proposed MO-OLSR routing protocol is compared to OLSR and modified versions in terms of average selected number of MPRs during the considered simulation interval. Figure 5 illustrates the average number of selected MPRs for MO-OLSR, OLSR, DOLSR, and ML-OLSR, in each considered simulation case. As presented in the figure, the proposed scheme selects average MPRs less than other considered protocols; this indicates that the proposed protocol achieves higher efficiency in terms of packet overhead and bandwidth utilization.

Figure 5.

Average number of selected MPRS for the considered three cases: (a) case 1, (b) case 2, and (c) case 3.

Table 6 provides the upper confidence limit (UCL), the lower confidence limit (LCL), and the mean value of the selected MPRs introduced in Figure 5, with confidence of 95%. The values of the mean and the confidence intervals are indicated for each considered system in each considered simulation case. Based on the results indicated in Figure 5 and Table 6, the proposed MO-OLSR achieves 50% reduction of the number of selected MPRs than the original OLSR for the network represented in case 1. However, for a dense network that is represented in case 3, MO-OLSR achieves 25% reduction of the number of selected MPRs than the original OLSR.

Table 6.

Confidence intervals and mean values of the selected MPRs.

Simulation case	Algorithm	Mean	UCL	LCL
Case 1	OLSR	22	26	18
	DOLSR	15	17	13
	ML-OLSR	14	15	13
	MO-OLSR	11	13	9
Case 2	OLSR	33	37	29
	DOLSR	26	28	24
	ML-OLSR	25	27	23
	MO-OLSR	22	24	20
Case 3	OLSR	48	51	45
	DOLSR	44	46	42
	ML-OLSR	43	45	41
	MO-OLSR	36	39	33

UCL: upper confidence limit; LCL: lower confidence limit; OLSR: optimized link state routing protocol; DOLSR: directional optimized link state routing protocol; ML-OLSR: mobility and load aware OLSR; MO-OLSR: multi-objective optimized link state routing protocol.

Latency is an important performance metric; the total delay can be measured using end-to-end latency metric. The end-to-end latency can be defined as the total time from the packet generation by the source node to the packet reception by the destination node. The average end-to-end latency can be calculated by averaging end-to-end latency of communicated packets. Figure 6 illustrates the comparison between MO-OLSR, OLSR, and modified versions of OLSR in terms of end-to-end latency for the considered simulation cases. Results indicate that the proposed MO-OLSR routing algorithm achieves higher latency efficiency. This can be interpreted by considering the deployment of directional antennas that achieve lower delay than omnidirectional antennas used by OLSR and the reduction of intermediated points (MPRs) in the overall communication link that reduces the communication delay. Moreover, the proposed MO-OLSR algorithm achieves higher latency efficiency than reactive routing protocols; this is because reactive protocols construct routing table on demand unlike the proposed algorithm and OLSR-based algorithms that are proactive routing protocols that always have available routing table.

Figure 6.

End-to-end latency of the OLSR-based algorithms compared to MO-OLSR, for the considered three cases: (a) case 1, (b) case 2, and (c) case 3.

Table 7 provides the UCL, the LCL, and the mean value of the measured end-to-end latency introduced in Figure 6, with confidence of 95%. The values of the mean and the confidence intervals are indicated for each considered system in each considered simulation case. Based on the results indicated in Figure 6 and Table 7, the proposed MO-OLSR achieves 41% reduction of the end-to-end latency than the original OLSR for the network represented in case 1. However, for a dense network that is represented in case 3, MO-OLSR achieves 53% reduction of the end-to-end latency than the original OLSR.

Table 7.

Confidence intervals and mean values of the measured end-to-end latency.

Simulation case	Algorithm	Mean	UCL	LCL
Case 1	OLSR	9.68	12.35	7.01
	DOLSR	8.25	10.37	6.13
	ML-OLSR	8.04	10.11	5.97
	MO-OLSR	5.76	7.80	3.72
Case 2	OLSR	16.89	19.62	14.16
	DOLSR	14.35	15.89	12.81
	ML-OLSR	13.98	16.81	11.15
	MO-OLSR	7.83	10.38	5.28
Case 3	OLSR	23.10	25.12	21.08
	DOLSR	18.49	20.50	16.48
	ML-OLSR	17.67	20.21	15.13
	MO-OLSR	10.98	13.49	8.47

The third metric that can be considered for performance evaluation and comparison is the PDR that represents the amount of packet received successfully compared to the total transmitted packets. Figure 7 illustrates the value of the average PDR for each considered OLSR-based protocols compared to the proposed MO-OLSR routing protocol, in each considered simulation case; this is for a duration of 700 s. Results indicate that the proposed protocol improves the PDR by 5.5% compared to the ML-OLSR and by 13% compared to the original OLSR.

Figure 7.

The percentage of PDR for OLSR-based algorithms compared to MO-OLSR, for the considered three cases.

The last considered performance metric is the energy consumption, which represents an important metric, especially for micro UAV networks that have restrictions on energy. Proactive routing protocols consume more energy than reactive routing protocols, since these protocols always have available routing tables that need to be updated periodically. To this end, consideration of energy for OLSR and modified versions is an important issue. Figure 8 illustrates the percentage of the average consumed energy, by each OLSR-based protocol and MO-OLSR-proposed protocol during the simulation process for each of the considered simulation case, compared to initial energy at the start of the network; this is for the duration of 700 s. Results indicate that the proposed MO-OLSR routing algorithm achieves higher energy efficiency by factor of around 20% than the original OLSR.

Figure 8.

The percentage of energy consumption of UAV nodes during simulation, for the considered three cases.

Conclusion

Designing of routing protocols for ad hoc UAV networks represents a challenge, since the high mobility of deployed nodes produces frequent changes in network topology and affects the communication links between distributed nodes. In this work, a proactive routing protocol for ad hoc UAV networks has been developed based on the OLSR routing protocol. The proposed MO-OLSR routing protocol is energy and latency efficient one that considers the high mobility of network nodes. The work considers all modified versions of OLSR and introduces a novel mechanism for selecting MPR nodes. MO-OLSR protocol has been simulated and compared with OLSR and its modified versions over a reliable environment for various considered simulation cases. Simulation results indicate that the proposed MO-OLSR protocol achieves higher efficiency in terms of latency, reliability, and energy.

Footnotes

Handling Editor: Honglin Hu

Declaration of conflicting interests

The author(s) declared no potential conflicts of interest with respect to the research,authorship,and/or publication of this article.

Funding

The author(s) disclosed receipt of the following financial support for the research,authorship,and/or publication of this article: The publication was supported by the Ministry of Education and Science of the Russian Federation (project no. 2.3397.2017/4.6).

ORCID iD

Abdelhamied A Ateya

References

Naqvi

Hassan

Pervaiz

et al. Drone-aided communication as a key enabler for 5G and resilient public safety networks. IEEE Commun Mag 2018; 1: 36–42.

3GPP TR 38.913. Study on scenarios and requirements for next generation access technologies (Version 14.3.0), June 2017, http://www.3gpp.org

Recommendation ITU-R M.2083. IMT vision—framework and overall objectives of the future development of IMT for 2020 and beyond, September 2015, https://www.itu.int/dms_pubrec/itu-r/rec/m/R-REC-M.2083-0-201509-I!!PDF-E.pdf

Oubbati

Lakas

Zhou

et al. A survey on position-based routing protocols for flying ad hoc networks (FANETs). Veh Commun 2017; 10: 29–56.

Menouar

Guvenc

Akkaya

et al. UAV-enabled intelligent transportation systems for the smart city: applications and challenges. IEEE Commun Mag 2017; 55(3): 22–28.

Boubeta-Puig

Moguel

Sánchez-Figueroa

et al. An autonomous UAV architecture for remote sensing and intelligent decision-making. IEEE Internet Comput 2018; 22(3): 6–15.

Vidal

Honório

Santos

et al. UAV vision aided positioning system for location and landing. In: 2017 18th international carpathian control conference (ICCC), Sinaia, 28–31 May 2017, pp.228–233. New York: IEEE.

Zhou

Cheng

et al. Multi-UAV-aided networks: aerial-ground cooperative vehicular networking architecture. IEEE Veh Technol Mag 2015; 10(4): 36–44.

Mademlis

Mygdalis

Nikolaidis

et al. Challenges in autonomous UAV cinematography: an overview. In: 2018 IEEE international conference on multimedia and expo (ICME), San Diego, CA, 23 July 2018, pp.1–6. New York: IEEE.

10.

Marconato

Maxa

Pigatto

et al. IEEE 802.11 n vs. IEEE 802.15. 4: a study on communication QoS to provide safe FANETs. In: 2016 46th annual IEEE/IFIP international conference on dependable systems and networks workshop, Toulouse, 28 June–1 July 2016, pp.184–191. New York: IEEE.

11.

Kenter

Wevers

Huijnen

et al. Ad hoc monitoring of vocabulary shifts over time. In: Proceedings of the 24th ACM international on conference on information and knowledge management, Melbourne, VIC, Australia, 18–23 October 2015, pp.1191–1200. New York: ACM.

12.

Zhao

Braun

. Topology control and mobility strategy for UAV ad-hoc networks: a survey. In: Joint ERCIM eMobility and MobiSense workshop, 2012, pp.27–32, http://home.inf.unibe.ch/~rvs/research/pub_files/ZB12.pdf

13.

Gupta

Jain

Vaszkun

. Survey of important issues in UAV communication networks. IEEE Commun Surv Tut 2016; 18(2): 1123–1152.

14.

Paramonov

Nurilloev

Koucheryavy

. Provision of connectivity for (heterogeneous) self-organizing network using UAVs. In: Galinina

Andreev

Balandin

et al. (eds) Internet of Things, smart spaces, and next generation networks and systems. Cham: Springer, 2017, pp.569–576.

15.

Jacquet

Laouiti

Minet

et al. Performance analysis of OLSR multipoint relay flooding in two ad hoc wireless network models. Doctoral Dissertation, INRIA, Paris, 2001.

16.

Bekmezci

Sahingoz

Temel

. Flying ad-hoc networks (FANETs): a survey. Ad Hoc Netw 2013; 11(3): 1254–1270.

17.

Zhang

Zeng

. Preliminary study of routing and date integrity in mobile Ad hoc UAV network. In: 2008 international conference on apperceiving computing and intelligence analysis (ICACIA 2008), Chengdu, China, 13–15 December 2008, pp.347–350. New York: IEEE.

18.

Tareque

Hossain

Atiquzzaman

. On the routing in flying ad hoc networks. In: 2015 federated conference on computer science and information systems (FedCSIS), Lodz, 13–16 September 2015, pp.1–9. New York: IEEE.

19.

Cheng

Hsiao

Kung

et al. Maximizing throughput of UAV-relaying networks with the load-carry-and-deliver paradigm. In: 2007 IEEE wireless communications and networking conference (WCNC 2007), Kowloon, China, 11–15 March 2007, pp.4417–4424. New York: IEEE.

20.

Ding

Zhou

et al. Route planning for unmanned aerial vehicle (UAV) on the sea using hybrid differential evolution and quantum-behaved particle swarm optimization. IEEE T Syst Man Cy-S 2013; 43(6): 1451–1465.

21.

Oubbati

Lakas

Zhou

et al. Intelligent UAV-assisted routing protocol for urban VANETs. Comput Commun 2017; 107: 93–111.

22.

Chi

et al. Ant colony optimization based polymorphism-aware routing algorithm for ad hoc UAV network. Multimed Tools Appl 2016; 75(22): 14451–14476.

23.

Rosati

Kruzelecki

Traynard

et al. Speed-aware routing for UAV ad-hoc networks. In: 2013 IEEE Globecom workshops (GC Wkshps), Atlanta, GA, 9–13 December 2013, pp.1367–1373. New York: IEEE.

24.

Biomo

Kunz

St-Hilaire

Routing in unmanned aerial ad hoc networks: introducing a route reliability criterion. In: 2014 7th IFIP wireless and mobile networking conference (WMNC), Vilamoura, 20–22 May 2014, pp.1–7. New York: IEEE.

25.

Zang

. Mobility prediction clustering algorithm for UAV networking. In: 2011 IEEE Globecom workshops (GC Wkshps), Houston, TX, 5–9 December 2011, pp.1158–1161. New York: IEEE.

26.

Albani

Manoni

Nardi

et al. Dynamic UAV swarm deployment for non-uniform coverage. In: Proceedings of the 17th international conference on autonomous agents and multiagent systems, Stockholm, 10–15 July 2018, pp.523–531. Richland, WA: International Foundation for Autonomous Agents and Multiagent Systems.

27.

Alshabtat

Dong

et al. Low latency routing algorithm for unmanned aerial vehicles ad-hoc networks. Int J Elec Comput Eng 2010; 6(1): 48–54.

28.

Zheng

Wang

et al. A mobility and load aware OLSR routing protocol for UAV mobile ad-hoc networks. In: 2014 international conference on information and communications technologies (ICT 2014), Nanjing, China, 15–17 May 2014, paper no. 1-019. London: IET.

29.

Zheng

Xie

et al. Ad hoc network routing protocol based on location and neighbor sensing. In: 2018 IEEE international conference on computer and communication engineering technology (CCET), Beijing, China, 18–20 August 2018, pp.1–5. New York: IEEE.

30.

Jen

. Method of handling radio link failure in wireless communications system and related device. United States Patent application US 11/902,454, 2008.

31.

Csiszár

Móri

. A Bienaymé-Chebyshev inequality for scale mixtures of the multivariate normal distribution. Math Inequal Appl 2009; 12(4): 839–844.

32.

Yanmaz

Quaritsch

Yahyanejad

et al. Communication and coordination for drone networks. In: Zhou

Kunz

(eds) Ad hoc networks. Cham: Springer, 2017, pp.79–91.

33.

Sahingoz

. Networking models in flying ad-hoc networks (FANETs): concepts and challenges. J Intell Robo Syst 2014; 74(1–2): 513–527.

34.

Mounagurusamy

Eswaramurthy

. A novel load balancing scheme for multipath routing protocol in MANET. J Comput Inf Technol 2016; 24(3): 209–220.

35.

Boero

Cello

Gnecco

et al. A theoretical analysis of buffer occupancy for intermittently-connected networks. Perform Eval 2017; 115: 108–131.

36.

Qiong

Pengfei

Qianbin

et al. A bioinspired adaptive congestion-avoidance routing for mobile ad hoc networks. Math Prob Eng 2014; 2014: 431013.

37.

Rungtaveesak

Chartkajekaew

Thongthavorn

et al. A dynamic routing for load distribution in mobile ad-hoc network. In: Meesad

Sodsee

Unger

. (eds) Recent advances in information and communication technology 2017: proceedings of the 13th international conference on computing and information technology. Cham: Springer, 2017, pp.232–241.

38.

. Link-quality and traffic-load aware routing for UAV ad hoc networks. In: 2018 IEEE 4th international conference on collaboration and Internet computing (CIC), Philadelphia, PA, 18–20 October 2018, pp.71–79. New York: IEEE.

39.

Koucheryavy

. Flying network for emergencies. In: Proceedings of 21st international conference on distributed computer and communication networks, DCCN 2018, vol. 919, Moscow, 17–21 September 2018, p.58. Cham: Springer.

40.

Seliem

Ahmed

Shahidi

et al. Delay analysis for drone-based vehicular ad-hoc networks. In: 2017 IEEE 28th annual international symposium on personal, indoor and mobile radio communications (PIMRC), Montreal, QC, Canada, 8–13 October 2017, pp.1–7. New York: IEEE.

41.

Khan

Qureshi

Khan

et al. On the performance of flying ad-hoc networks (FANETs) with directional antennas. In: 2018 5th international multi-topic ICT conference (IMTIC), Jamshoro, 25–27 April 2018, pp.1–8. New York: IEEE.

42.

Zheng

Sangaiah

Wang

. Adaptive communication protocols in flying ad hoc network. IEEE Commun Mag 2018; 56(1): 136–142.