Sage Journals: Discover world-class research

Abstract

Flying ad hoc network is widely used in many military and civilian scenarios. Compared with mobile ad hoc network and vehicular ad hoc network, flying ad hoc network holds some special characteristics such as high mobility, long-distance communication, and sparse node-deployment, which cause an important challenge in the design of routing protocols. In this article, a velocity-aware and stability-estimation–based multi-path routing protocol is proposed for flying ad hoc network. The protocol is mainly composed of two important parts, which are the routing discovery mechanism and routing maintenance mechanism. In routing discovery process, the routing discovery request packet only can be forwarded by the reliable node, which is decided by the calculation of co-direction degree, then the routing overhead is reduced at some extent. Noticeably, the correlation of the survival duration between adjacent links is fully considered, which is very important to the path stability criteria. In routing maintenance progress, a path similarity and path remaining survival duration–based multi-path selection mechanism is proposed. The performance superiority of velocity-aware and stability-estimation–based multi-path routing protocol is also demonstrated by extensive simulations. The results show that velocity-aware and stability-estimation–based multi-path routing protocol is much better than other existing protocols in terms of network throughput, average delay of data transmission, routing overhead, and the convergence time of the routing discovery.

Keywords

Flying ad hoc network multi-path routing protocol stability estimation velocity-aware

Introduction

The development and application of a large number of available low-cost wireless communication technologies and devices have laid the foundation for the development of small intelligent aircraft such as unmanned aerial vehicles (UAVs). Under this background, a new type of technology called flying ad hoc network (FANET) is generated.¹ FANET is widely used in various civil and military scenarios such as shoreline protection monitoring, post-disaster rescue, agricultural and yard monitoring, oilfield leakage monitoring, and aerial photography.^2,3

However, FANET is fundamentally different from traditional mobile ad hoc network (MANET) from the following aspects. First, from the perspective of communication range, the communication distance between the nodes in FANET is usually tens of kilometers, while that between adjacent nodes in MANET is only tens of meters. Noticeably, the distribution of nodes in FANET is usually sparser than that of the traditional MANET. Second, from the perspective of communication effectiveness, more attention should be paid to the efficient processing and fast forwarding for data flow in FANET compared with MANET, which improves data transmission efficiency by minimizing the node data forwarding time. Third, from the perspective of communication reliability, due to the high mobility of the node and the complex and variable operating environment, the transmission link quality and stability are changed frequently and intermittently, which affects the end-to-end transmission of the data flow. Therefore, more accurate robustness and stability estimation of the link between the adjacent nodes is required for the transmission quality of traffic. The above-mentioned significant differences between FANET and MANET indicate that most of the mechanisms and protocols of traditional MANET may be not applicable to FANET directly.^4,5 For example, a large amount of idle time and delay in data transmission will be generated when the RTS/CTS/DATA/ACK multiple handshake mechanism of the carrier sense multiple access with collision avoidance (CSMA/CA) protocol in the traditional short-range communication MANET is used in the FANET, which is unsuitable to long-distance communication and high mobility of FANET.

Routing is a simple term with complex tasks. Routing involves pathfinding, path selection, and decision regarding transmission, receiving, and forwarding of data. There are relatively high relative movements among multiple nodes in the FANET, where the rapid changes of network topology and link status may be caused. It has been shown that the mechanisms specifically designed for MANETs or vehicular ad hoc networks (VANETs) cannot be directly applied in FANETs due to the high mobility, sparse deployment, drastically changing network topology, intermittently connected communication links, and intentional jamming and disruption.

In light of these facts, many methods for link prediction have been proposed by researchers for overcoming the impact of high-speed node mobility on routing of FANET. Link reliability prediction and user mobility prediction have attracted much attention in solving these problems. For example, a simple and efficient link stability prediction model is proposed in J Xie et al.⁶ The core idea of this model is that the stability of the link concerned is predicted through the calculation of the variance for the received data packet signal strength. However, the algorithm cannot be adapted into the fast topological change scenario of high dynamic FANET. The idea of link prediction is applied to the aeronautical communication network in N Baccour et al.,⁷ and packet Doppler shift is used as an index to measure the quality of inter-aircraft links. Although routing protocol operating in the FANET has seen tremendous research and implementation during the last few years, how to design a route suitable for FANET transmission requirement is a crucial task in the development and application of FANET.^8,9

Motivation

Now, the motivation of this article is illustrated with a toy example, that is, the impact of speed perception and link reliability estimation on routing protocol design. The scenario shown in Figure 1 is the most common scenario in FANET applications. It is assumed that some node representing aircraft are deployed in the network randomly. The node that the traffic flow is transmitted is called the source node, the node that the traffic flow is received is called destination node, and other nodes where traffic flow is forwarded are called intermediate nodes. Traffic flows of source node, which is denoted by $nod e_{S}$ , are delivered to the destination node, which is named $nod e_{D}$ . $nod e_{S}$ , $nod e_{A}$ , $nod e_{C}$ , and $nod e_{D}$ are all flying from west to east in the beginning. However, $nod e_{B}$ will fly to the northeast at some moment. The connection from $nod e_{S}$ to $nod e_{D}$ should be established for the efficient data transmission. As can be seen from Figure 1, there are two possible communication connections, that is, $< nod e_{S}, nod e_{C}, nod e_{A}, nod e_{D} >$ and $< nod e_{S}, nod e_{B}, nod e_{D} >$ . Although the duration of the effective connection in paths $< nod e_{S}, nod e_{B}, nod e_{D} >$ is shortened and the probability of path break is increased, $nod e_{B}$ is not within the communication range of $nod e_{S}$ after a period of time because that $nod e_{A}$ continues to fly east while $nod e_{B}$ flies in other directions. In contrast, path $< nod e_{S}, nod e_{C}, nod e_{A}, nod e_{D} >$ has much longer duration and more stability of the connection. It is the best communication link from $nod e_{S}$ to $nod e_{D}$ . Therefore, it can be seen that the velocity direction of the node should be fully considered in routing selection. In other words, the path life is affected directly by the relative velocity of the nodes. On the face of it, $nod e_{B}$ is closest to the destination node $nod e_{D}$ , node $nod e_{B}$ is most likely to be as the optimal forwarding node by $nod e_{S}$ , and the path $nod e_{S} \to nod e_{B} \to nod e_{D}$ is the shortest path. However, the velocity information between the source and neighbor nodes is not taken into account in the routing, which may affect the remaining survival duration of the path at a large extent. To that end, how to analyze link reliability with the information of the velocity and the statistics of the node is an important consideration in routing design.

Figure 1.

Schematic diagram of routing and link lifetime affected by velocity.

Motivated by the toy example, a velocity-aware and stability-estimation–based multi-path routing protocol (VaSe-MRP) is proposed in this article, which is aiming at the achievement of the fast and reliable data transmission.

Contribution

The protocol is mainly composed of two mechanisms, that is, the route discovery mechanism and the path maintenance mechanism. Although the state of the art of routing protocols in FANET is briefly summarized in the form of classification first, comprehensively and systematically reviewing the related work is not the purpose of our article. Our main contributions are four aspects and are emphasized as follows:

First, a velocity-aware-based forwarding mechanism of next hop node is proposed in VaSe-MRP for the enhancement of the traffic forwarding effectiveness. As a result, the neighbor nodes are divided into reliable nodes and non-reliable nodes with the velocity vector information. Only the reliable node is selected as the next hop forwarding node.

Second, the correlation of the survival duration between adjacent links is fully considered from the perspective of the statistical characteristics of the remaining duration. Therefore, the theoretical error of the estimation for the path stability in existing method is eliminated.

Third, the path similarity and path remaining survival duration (PRSD)-based multi-path selection mechanism is proposed for the improvement of the transmission reliability or the effectiveness of the traffic flows. Whether the copy or different packets are transmitted with the selected multi-paths is decided according to the multi-path selection mechanism.

Finally, VaSe-MRP is simulated and compared with other existing protocols in terms of end-to-end throughput (ETH), average transmission delay, routing overhead (ROH), and convergence of the protocol under the situation that the node is moving in high velocity, where the superiority of Vase-MRP is demonstrated.

It should be noted that all the variables symbols and the corresponding physical meanings are summarized in Table 1 for the convenience of the following narration. The rest of the article is organized as follows. Prior routing mechanisms and protocols are summarized and analyzed from two perspectives in section “Related work.” The system model is described in section “System model.” The details of procedures of Vase-MRP are given in section “VaSe-MRP.” Simulation and results analysis are presented in section “Simulation and results.” Finally, the conclusion of this article and the potential improvement point of VaSe-MRP are summarized in section “Conclusion.”

Table 1.

Variables symbols and the corresponding meanings.

Type	Meaning	Symbols
Link layer	Velocity vector of $nod e_{n}$	$V_{n}$
	Co-direction degree between $V_{n}$ and $V_{i}$	$ϑ_{i}^{n}$
	Transmission radius of the node	$R$
	Remaining survival duration of $lin k_{i}$	$T_{i}$
	Azimuth $nod e_{1}$ to $nod e_{2}$	$α$
	Maximum number of links per path	$H$
	Link stability of $lin k_{i}$	$l s_{i} (T)$
	Path stability of $pat h_{p}$ with $H$ links	$p s_{p} (T)$
Routing layer	Number of flying nodes	$N$
	Neighbor node set of $nod e_{n}$	$S_{n}$
	Source routing table	$T_{s}$
	Forwarding routing table	$T_{r}$
	Number of priorities for traffic flow	$M$
	Minimum similarity between two paths	$ω$
	Mode selection of flow transmission	$δ$

Related work

FANET is considered as a subclass from MANET and VANET; therefore, common ideas and strategies could be shared for data delivery. For the right functionality of data delivery, the techniques that are specifically designed for MANET and VANET have to be adapted to specific characteristics and challenges in FANET, for example, high mobility, sparse deployment, drastically changing network topology, intermittently connected communication links, and intentional jamming and disruption. In this section, we categorize and analyze existing routing protocols in FANETs. Previous studies on multi-hop routing of FANET can be divided into two categories, which are location-centered multi-hop routing and node-centered multi-hop routing, according to the selection criterion.

Location-centered routing protocol in FANET

Location-centered routing is also called geocasting routing,¹⁰ and the precise location information of communication nodes should be obtained or predicted. In C Yin et al.,¹¹ an on-demand routing protocol called reliability map routing is proposed. The routing with the longest reliability duration in the space rather than the closest one is quickly found by the protocol because the reliability and trustworthiness of nodes are geocasted in the whole space with low overhead. In Y Wang et al.,¹² a more effective and reliable two-way geocasting protocol is proposed, in which the chances of successful message delivery are improved with two independent paths and a novel authentication mechanism. In H Rutagemwa et al.,¹³ a fountain code–based and greedy queue and location assisted routing protocol is designed. A power allocation and routing strategy is designed for the mitigation of effect on the overall network delay due to queue backlog. In L Gupta et al.,¹⁴ the new location participated in data transmission and path planning of UAV in FANET is modeled as a mixed non-linear integer programming problem, and a Hooke–Jeeves algorithm–based heuristic strategy is proposed to solve the problem. In K Sundar and S Rathinam,¹⁵ a robust and reliable predictive routing protocol, which is based on fast updating mechanism for the estimation of three-dimensional (3D) intermediate nodes, is proposed for FANET. The omni-directional and directional transmission is combined in the protocol, and the unicast and geocasting routing are used synthetically. Consequently, the long-distance transmission and the track of topological changes are realized, the robustness of the protocol is fully guaranteed, and the path reconstruction and service interruption time are reduced. In F Hoffmann et al.,¹⁶ an adaptive communication protocol, which is mainly composed of location prediction–based directional medium access control (MAC) protocol and enhanced learning-based self-organizing routing protocol, is proposed in FANET.

It can be seen from the above-mentioned references that the local decision-making makes position-based routing protocols suitable in scenarios of large and highly mobile networks. Nodes do not have to explore the status of the whole network, store routing tables, or exchange control messages in the entire network.

Node-centered routing protocol in FANET

In a node-centric routing, the next hop can be selected on the basis of historical information and the prediction information. However, relatively few studies have used this type of routing. In Arafat and Moh,¹⁷ the concepts and architecture of FANET, and the challenges of the node-centric routing design in FANET are systematically introduced. In M Hu et al.,¹⁸ a cross-layer architecture–based link-level and network-wide analysis model is proposed for FANET. It is shown in the analysis and the results that the communication performance and the delay-sensitive-supported applications can be significantly improved by the proposed cross-layer protocol architecture, which is based on the fast packet forwarding and multi-hop error control mechanism. In C Pu,¹⁹ an improved optimized link state routing (OLSR), which is called predictive OLSR (P-OLSR), is designed for FANET, and the networking performance of P-OLSR is simulated and tested. In Z Zheng et al.,⁸ two different routing algorithms for ad hoc networks: OLSR and P-OLSR, which is an OLSR extension designed for FANETs, are compared. In G Gankhuyag et al.,²⁰ a multiple QoS parameters–based routing protocol (MQSPR) is proposed for the improvement of the network performance between air nodes and surface nodes. Many factors such as path availability period, residual path load capacity, and path delay are considered in route selection of MQSPR. In addition, a broadcast optimization scheme aimed at minimized flooding is proposed. The main goal of MQSPR is to maintain long link duration, achieve path load balancing, and reduce end-to-end delay. On the basis of G Gankhuyag et al.,²⁰ a protocol called FRUDP is proposed in Q Luo and J Wang.²¹ The reliable user datagram protocol (UDP) and fountain code is combined in FRUDP for reliable and effective data transmission in FANET. In S Rosati et al.,²² a new routing protocol is proposed for FANET, it is shown in the simulation results that the performance of the proposed protocol is better than the typical location-centric routing protocol in terms of the packet delivery rate and end-to-end delay. In Gohari et al.,²³ a jamming-resilient multi-path routing protocol is proposed, so that the overall network performance of FANETs is not interrupted by the intentional jamming and disruption, or isolated and localized failures. The protocol is composed with a combination of three major schemes, which are link quality scheme, traffic load scheme, and spatial distance scheme. In addition, a simple analysis model and numerical results are presented. In A Bujari et al.,²⁴ a comparative analysis of the few node-centric routing protocols in the existing FANET is presented, and the system performance is also verified. A distributed priority tree-based routing protocol (DPTR) is proposed for the FANET in V Sharma et al.²⁵ The protocol uses the properties of a red–black (R-B) tree and formulates distributed routing trees by adding up certain rules in the formation of these trees. However, the protocol focuses more on solving the problem of network partitioning and relay node selection when ground ad hoc network and aerial ad hoc network coexist. In I Mahmud and YZ Cho,²⁶ a novel adaptive hello interval scheme, energy efficient hello (EE-Hello), based on available mission-related information is proposed, where the distance that a UAV needs to travel before sending a hello message is decided.

It can be seen from the above classification and comparison that the node-centric routing mechanism, where the historical information and the prediction information of the node are used, can select next hop node more effectively than the location-centric routing mechanism, where the real-time location information is used. Unfortunately, the effect of node velocity on link quality and the remaining life cycle of the path are not considered in the above node-centric related work. Therefore, a node VaSe-MRP is proposed in this article, so that the performance can be improved significantly in terms of network throughput, data transmission delay, ROH, and reliability of data transmission in case of high node mobility.

System model

In this section, the system-related models are introduced, that is, velocity-aware forwarding probability, path/link remaining survival duration, and path/link stability evaluation criteria, which are important parts for the route discovery mechanism and path selection mechanism described as follows. For the convenience of description, node that want to send traffic flow is called as source node, and the operation performed by the source node in the protocol is called source node operation. Node that is the destination of the traffic flow is called destination node, and the operation performed by the destination node in the protocol is called destination node operation. All other nodes, which are responsible for the data forwarding, are collectively called intermediate node, and the operation performed by intermediate node is called intermediate node operation.

Velocity-aware forwarding

It is assumed that there are $N$ flying nodes distributed in the network randomly. For any node, which is denoted by $nod e_{n}$ in the network, the neighbor node of $nod e_{n}$ is denoted by $nod e_{i} \in S_{n}$ , where $S_{n}$ is the set of neighbor node of $nod e_{n}$ . It is assumed that the velocity vector of $nod e_{n}$ is expressed as $V_{n}$ . $V_{i}$ is the velocity vector of $nod e_{i}$ . Then, the co-direction degree, which is the angle between the velocity vector $V_{n}$ and the velocity vector $V_{i}$ , is defined as

ϑ_{i}^{n} = \arccos \frac{V_{n} \cdot V_{i}}{| V_{n} | | V_{i} |}

(1)

where “ $| |$ ” is the norm of vector and “·” is dot product between vectors. If a packet with the velocity information of $nod e_{n}$ is received by the intermediate node $nod e_{i}$ , then $ϑ_{n}^{i}$ will be calculated by $nod e_{i}$ . If $ϑ_{i}^{n}$ is bigger than the preset threshold, which is denoted by $ϑ_{th}$ , that is, $ϑ_{i}^{n} \geq ϑ_{th}$ , then $nod e_{i}$ belongs to the reliable neighbor node set, which is denoted by $S_{n}^{rns}$ , of $nod e_{n}$ , that is, $nod e_{i} \in S_{n}^{rns}$ . Otherwise, $nod e_{i}$ belongs to the non-reliable neighbor node set, which is denoted by $S_{n}^{nrns}$ , of $nod e_{n}$ , that is, $nod e_{i} \in S_{n}^{nrns}$ . It is affirmed that the link between $nod e_{n}$ and $nod e_{i} \in S_{n}^{rns}$ is more stable than the case of $nod e_{i} \in S_{n}^{nrns}$ . The purpose of the definition is that the routing signaling packet in source routing discovery is prevented to be transmitted by the non-reliable neighbor node of $nod e_{n}$ , so that the risk of route breakage is minimized and the ROH is reduced to a certain extent. In other words, routing packets should be forwarded by reliable neighbor node.

Path/link remaining survival duration

In our article, link remaining survival duration (LRSD) and PRSD are very important to path selection for FANET. For the simple calculation, the assumption of the statistical analysis of LRSD and PRSD for the routing optimization strategy in D Kim and J Lee²⁷ is that multi-hop PRSD, which is denoted by $prsd$ , is a random variable subjected to exponential distribution, and $prsd$ can be expressed with $H$ LRSD, which is denoted as $lrs d_{i}$ , constituting the path as follows

\frac{1}{prsd} = \sum_{h = 1}^{H} \frac{1}{lrs d_{i}}

(2)

However, there are two preconditions for formula (2) to hold. The first precondition is that the remaining survival duration of each link on the path is independent statistically. The second precondition is that the number of hops of the path and the length of each link are large enough. As shown in Figure 2, the link between $nod e_{1}$ and $nod e_{2}$ is denoted by $l_{1}$ , and the link between $nod e_{2}$ and $nod e_{3}$ is denoted by $l_{2}$ . It is easy to see that the link lifetime of $l_{1}$ and $l_{2}$ are affected by the mobility of shared $nod e_{2}$ simultaneously, so there are some correlations between them. The simulation proof of the correlation is given in Z Li and ZJ Haas,²⁸ so the first precondition of formula (2) is not valid. In addition, node transmission range and path hops are usually limited in actual FANET, so the second precondition of formula 2 is also difficult to be satisfied. Therefore, a more accurate statistical definition method for LRSD and PRSD is proposed under full consideration of the correlation between LRSDs. According to the mobility parameters of the multi-hop path given in Figure 2, the transmission radius of the node is set as $R$ . $d_{1}$ is the relative distance between node $nod e_{1}$ and node $nod e_{2}$ at the estimation time of remaining survival duration (RSD). $V_{i}, i \in {1, 2, 3}$ is the norm of the $V_{i}$ in $nod e_{i}$ , and $θ$ is the direction angle of $V_{i}$ in $nod e_{i}$ . The remaining survival duration of the $i th$ link on one path is denoted $T_{i}$ , that is, $lrs d_{i} = T_{i}, (i = 1, 2, \dots)$ , and $V_{i} ~ U (V_{\min}, V_{\max}), V_{\max} > V_{\min} \geq 0, V_{d} = V_{\max} - V_{\min}$ . When $V_{2}$ is fixed, the probability density function (PDF) of $T_{1}$ can be given as equation (15) in Z Li and ZJ Haas²⁸

f_{T_{1} | V_{2}} (t_{1} | v_{2}) = \int_{- π}^{π} \frac{χ^{2}}{2 π V_{d} t_{1}^{2} \sqrt{χ^{2} + v_{2}^{2} t_{1}^{2} + 2 v_{2} t_{1} χ \cos φ}} d φ

(3)

Figure 2.

Relative velocity and spatial position relationship of $nod e_{1}$ to $nod e_{2}$ and $nod e_{3}$ and $nod e_{2}$

where $χ = d_{1} \cos φ + \sqrt{R^{2} - d_{1}^{2} \sin^{2} φ}$ , and PDF of $T_{1}$ can be expressed as

f_{T_{1}} (t_{1}) = \int_{V_{\min}}^{V_{\max}} f_{T_{1} | V_{2}} (t_{1} | v_{2}) \cdot f_{V_{2}} (v_{2}) d v_{2}

(4)

Furthermore, the cumulative distribution function (CDF) of $T_{1}$ can be obtained as

F_{T_{1}} ({t'}_{1}) = P (T_{1} \leq {t'}_{1}) = \int_{0}^{{t'}_{1}} f_{{T'}_{1}} ({t'}_{1}) d t_{1}

(5)

where $F (\cdot)$ and $P (\cdot)$ are CDF and PDF, respectively. Then, $f_{T_{2} | V_{2}} (t_{2} | v_{2})$ and $f_{T_{2}} (t_{2})$ can be obtained in a similar way. The joint PDF of $T_{1}$ and $T_{2}$ , which is denoted by $f_{T_{1}, T_{2}} (t_{2}, t_{2})$ , is solved as follows.

First, the LRSD correlation between adjacent links is considered. In other words, $T_{1}$ and $T_{2}$ are not independent of each other, so the following formula (6) does not hold

f_{T_{1}, T_{2}} (t_{2}, t_{2}) = f_{T_{1}} (t_{1}) \cdot f_{T_{2}} (t_{2})

(6)

However, $T_{1}$ and $T_{2}$ are independent of each other when $V_{2}$ is fixed. In this case, the statistical correlation introduced by the shared nodes is eliminated. It is verified as follows with Figure 2. It is assumed that $α$ is the azimuth $nod e_{1}$ to $nod e_{2}$ at the estimation time of LRSD. $α'$ is the azimuth $nod e_{3}$ to $nod e_{2}$ at the estimation time of LRSD, and $α' = 0$ in Figure 2. $ϑ$ and $ϑ'$ are the co-direction degree for $(V_{1}, V_{2})$ and $(V_{3}, V_{2})$ . $V_{1}$ , $V_{2}$ , $V_{3}$ and the above-mentioned variables are independent of each other. $V$ and $V'$ are the relative velocity of $V_{1}$ to $V_{2}$ and $V_{3}$ to $V_{2}$ . $φ$ is the included angle between $V$ and $V_{2}$ , and $φ'$ is the included angle between $V'$ and $V_{2}$ . For $nod e_{1}$ and $nod e_{2}$ , variables $V$ and $φ$ are functions of $V_{1}$ , $V_{2}$ and $ϑ$ . According to the geometric and topological relationship of two-dimensional (2D) space, $V$ can be given with formula (7) as follows

V = \sqrt{{V_{1}}^{2} + {V_{2}}^{2} - 2 V_{1} V_{2} \cos (ϑ)}

(7)

The functional correspondence between $φ$ and $V_{1}$ , $V_{2}$ and $ϑ$ is mainly depended on the range of the latter three values. In particular, the corresponding situation in Figure 2 is discussed, where $ϑ \in [0, π) \cap (V_{1} \cos ϑ - V_{2} > 0)$ . Here

φ = \arctan (\frac{V_{1} \sin ϑ}{V_{1} \cos ϑ - V_{2}})

(8)

For $nod e_{2}$ and $nod e_{3}$ , the variables $V'$ and $φ'$ can be expressed as the functions of $V_{2}$ , $V_{3}$ and $θ'$ , respectively, in the same way. Further use of known variables can be obtained

T_{1} = \frac{d_{1} \cos (φ + α) + \sqrt{R^{2} - d_{1}^{2} \sin^{2} (φ + α)}}{V}

(9)

T_{2} = \frac{d_{2} \cos (φ + α) + \sqrt{R^{2} - d_{1}^{2} \sin^{2} (φ' + α')}}{V'}

(10)

It is shown from formulas (7)–(10) that although there are multiple random variables contained in the expressions of $T_{1}$ and $T_{2}$ , respectively, the statistical correlation between them is caused by $V_{2}$ only. It can be concluded that $T_{1}$ and $T_{2}$ are independent of each other when $V_{2}$ is fixed. According to this conclusion, we can get

f_{T_{1}, T_{2} | V_{2}} (t_{1}, t_{2} | v_{2}) = f_{T_{1} | V_{2}} (t_{1} | v_{2}) \times f_{T_{2} | V_{2}} (t_{2} | v_{2})

(11)

Furthermore, the joint PDF between $T_{1}$ and $T_{2}$ can be expressed as

f_{T_{1}, T_{2}} (t_{1}, t_{2}) = \int_{V_{\min}}^{V_{max}} f_{T_{1}, T_{2} | V_{2}} (t_{1}, t_{2} | v_{2}) \times f_{V_{2}} (v_{2}) d v_{2}

(12)

It has been proved in Z Li and ZJ Haas²⁸ that formula (12) can give more accurate results than the derivation methods of $f_{T_{1}, T_{2}} (t_{1}, t_{2})$ under independent conditions, that is, formula (6). If it is further assumed that the path $p$ is composed of $H$ links, then

\begin{matrix} f_{T_{1}, T_{2}, \dots, T_{H}} (t_{1}, t_{2}, \dots, t_{H}) \\ = \int_{v_{2}} \dots \int_{v_{H - 1}} f_{T_{1}, T_{2}, \dots, T_{H} | V_{1}, V_{2}, \dots, V_{H}} (t_{1}, t_{2}, \dots, t_{H} | v_{1}, v_{2}, \dots, v_{H}) \times f_{V_{2}} (v_{2}) \dots f_{V_{N - 1}} (v_{H - 1}) d v_{2} \dots d v_{H - 1} \end{matrix}

(13)

The joint CDF of LRSD for each link is given as

\begin{matrix} F_{T_{1}, T_{2}, \dots, T_{H}} ({t'}_{1}, {t'}_{2}, \dots, {t'}_{H}) \\ = P (T_{1} \leq {t'}_{1}, T_{2} \leq {t'}_{2}, \dots, T_{H} \leq {t'}_{H}) \\ = \int_{0}^{{t'}_{1}} \cdot \cdot \cdot \int_{0}^{{t'}_{H}} f_{T_{1}, T_{2}, \dots, T_{H}} (t_{1}, t_{2}, \dots, t_{H}) d t_{1} \dots d t_{H} \end{matrix}

(14)

As can be seen, although the complexity of our theoretical analysis model is increased slightly than the results under the link independent condition, the analytical solution of formula (13) is easily obtained when the unified and simple mobility model (such as $V_{i} ~ U (V_{\min}, V_{\max})$ ) is abided by each node and the number of path hops in the network is small.

Evaluation criteria of path/link stability

Based on the above-mentioned theoretical model, the definition of link stability and path stability are given as follows.

Definition 1

The probability that the LRSD of the link is not less than a specific time interval, which is denoted by $T$ , is called link stability. For the $i th$ link, the link stability, which is denoted by $l s_{i} (T)$ , is given as

l s_{1} (T) = 1 - F_{T_{i}} (T) = P (T_{i} \geq T)

(15)

Definition 2

The probability that the PRSD of the path is not less than the specific time interval, which is denoted by $T$ , is called path stability. For the $p th$ path with $H$ links, the path stability, which is denoted by $p s_{p} (T)$ , is given as

p s_{p} (T) = 1 - F_{T_{1}, T_{1} \dots T_{H}} (T) = P (T_{1}, T_{2} \dots T_{H} \geq T)

(16)

The rationality and advantages of the our definition are mainly embodied from the following two aspects. First, the mobility model is not limited when the mobility complexity of node is low. Second, the ability of validity maintenance for links or paths within a specified time is fully reflected. In addition, high estimation of path stability is leaded due to the neglection of the LRSD correlation between links, which is not conducive to the routing selection. This is also pointed out in Table 1 of Z Li and ZJ Haas.²⁸ Therefore, more accurate criteria of stability evaluation can be provided for the routing protocol with our new definitions.

After the above analysis, the impact of path stability on network performance is explained emphatically. The importance of path stability is mainly reflected in the following two aspects from the perspective of network layer:

First, the probability that the data are successfully transmitted through path $p$ within the expected delay $T$ is represented by $p s_{p} (T)$ . If there are $Q$ data packets received successfully in time $T_{w} (T_{w} > T)$ by the destination node, then network throughput, which is denoted by $th$ , can be defined as

th = \frac{1}{T_{w}} \sum_{q = 1}^{Q} G_{q} \times p s_{p_{q}} (T_{q})

(17)

where $G_{q}$ is size of the data packet, $T_{q}$ is expected transmission delay, and $p_{q}$ is corresponding transmission path. It is shown in formula (17) that the network throughput is proportional to path stability. Therefore, the transmission quality of network can be improved effectively with enhanced path stability.

Second, the average number of transmission times required for a single data stream is obtained as $1 / p s_{p} (T)$ according to Definition 2. Then, the data transmission delay, which is denoted by $td$ , can be expressed as

td = \frac{T}{p s_{p} (T)}

(18)

It is shown in formula (18) that the path stability is inversely proportional to transmission delay. In other words, the stronger the path stability, the smaller transmission delay, which further proves the importance of improving path stability.

VaSe-MRP

The detailed steps and operations of VaSe-MRP are presented in this section. In short, VaSe-MRP is mainly composed of two parts. The first one is the velocity-aware and link stability–based multi-path source route discovery mechanism, which includes the source node operation, the intermediate node operation, and the destination operation. It is corresponded to section “Route discovery.” The second part is the path stability and path similarity based multi-path selection mechanism and the backup path based route repair mechanism, which is corresponded to section “Multi-path maintenance.”

Route discovery

The main routing packets in VaSe-MRP are route discovery request packet (RDR, used for route discovery), route discovery answer packet (RDA, used for route response), route transmission data packet (RTD, used for pure data transmission) and route error packet (RER, used for routing failure report). All the packet formats are shown in Figure 3. The corresponding physical meaning of the field in various packets is explained as follows: $type$ (8 bit) indicates the packet type, and different values of the type indicates different packet. For example when the value equals to 0, it means the packet is RDR, and so on. $lenght$ (16 bit) represents the length of the routing packet. $souid$ (16 bit) indicates the source node address, that is, the address of the node that generating the packet. $desid$ (16 bit) stands for the destination node address. $path_node_list$ $(16 \times H bit)$ stores the intermediate nodes between $nod e_{S}$ and $nod e_{D}$ . $path_mob_list$ $(16 \times H bit)$ stores random parameter information, such as node position, movement model, velocity range and so on, of the nodes in the source route. $link_sta_list$ $(16 \times H bit)$ is the calculated value which stands for link stability with formulas (1) and (15). $qos$ (8 bit) represents the traffic priority. $seq$ (16 bit) stands for the packet sequence number, and each RDR has a unique identification number. $fcs$ (32 bit) is a function extension term, which is left blank in VaSe-MRP. $label$ is the random labels generated by destination nodes for label conversion protocols, which will be used in future protocol functional extensions.

Figure 3.

Various packets format in VaSe-MRP.

Source node operation

There are three types of packets that can be processed by the source node, that is, RER, RDA, and RTD. The flowchart of source node operations is showed as Figure 4.

Figure 4.

Flowchart of source node operation.

When there is any data flow in the source node, which is denoted as $nod e_{S}$ , transmitted to destination node, which is denoted by $nod e_{D}$ . The source routing table, which is denoted by $T_{s} = [t_{i}^{s}]_{c_{1}}$ , of $nod e_{S}$ is checked first. If there is at least one route from $nod e_{S}$ to $nod e_{D}$ in $nod e_{S} . T_{s}$ , the corresponding entry, which is denoted by $t_{i}^{s}, 1 \leq i \leq c_{1}$ is selected from $nod e_{S} . T_{s}$ , according to the multi-path route selection mechanism in subsection “Multi-path maintenance.” Then the assembled RTD is transmitted through the selected paths. If there is no route from $nod e_{S}$ to $nod e_{D}$ in $nod e_{S} . T_{s}$ , the route discovery process is started.

If the route discovery process is started by $nod e_{S}$ , the RDR is generated first. Then, the following key fields of RDR are added, that is, identification number of source node $(rdr . souid = nod e_{S} . id)$ , identification number of destination node $(rdr . desid = nod e_{D} . id)$ , list of intermediate node $(rdr . path_node_list = null)$ , quality-of-service (QoS) level $(rdr . qos = traffic . qos)$ , sequence number ( $rdr . seq = rdr . seq + 1$ , $rdr . seq$ is initialized from 0), transmitting time $(rdr . ttime = current time)$ , mobility information $(rdr . mob_lis t_{[0]} = nod e_{S} . mob)$ , link stability $(rdr . lsflag_lis t_{[0]} = 0)$ . Then, the RDR is broadcasted. At the same time, the timer for waiting RDA, which is denoted by $time r_{rda}$ , is set to $T_{rda}$ , that is, $time r_{rda} = T_{rda}$ .

If the RDA is received by $nod e_{S}$ , it is first confirmed that $time r_{rda}$ is not expired and then canceled. It is determined that the sequence number in the RDA is larger than the sequence number stored in the forwarding routing table, which is denoted by $T_{r} = [t_{i}^{r}]_{c_{2}}$ , that is, $rdr . seq > t_{i}^{r} . seq (1 \leq i \leq c_{2})$ . Then, the found route, which is denoted as $rda . path_node_list$ , in RDA is added in new entry of the $nod e_{S} . T_{s}$ . The key information in RDA is extracted and stored in source routing table $T_{s}$ as follows: identification number of the destination node $(t_{i}^{s} . desid = rda . desid)$ , corresponding labels allocated by the destination node $(t_{i}^{s} . label_id = rda . label_id)$ , identification number of source node $(t_{i}^{s} . souid = rda . souid)$ , sequence number $(t_{i}^{s} . seq = rda . seq)$ , route hops ( $t_{i}^{s} . hops = | rda . path_node_list |$ , |·| is the operator of solving cardinality), the covered intermediate nodes $(t_{i}^{s} . path = rda . path_node_list)$ , path stability ( $t_{i}^{s} . ps = \min_{1 \leq h \leq H} (link_sta_lis t_{h})$ , where $H = | link_sta_list |$ ), node mobility $(t_{i}^{s} . mob_list = rda . path_mob_list)$ . It is noted that the minimum value of the link stability for all links in the source route is defined as the path stability of the source route, which means that the path stability is mainly depended on the lowest link stability on the whole path. Finally, the data packets to $nod e_{D}$ in the queue are fetched and encapsulated as RTDs, then the RTDs are transmitted on the multi-path, which are selected out through the multi-path selection mechanism described in section “Multi-path maintenance.”

Intermediate node operation

There are four types of packets that can be processed by the intermediate node, that is, RTD, RDR, RER, and RDA. The flowchart of the intermediate node operation is shown in Figure 5.

Figure 5.

Flowchart of intermediate node operation.

If RDR is received by the intermediate node, which is denoted by $nod e_{n}$ , it is first confirmed that the sequence number in RDR is larger than the one recorded in the forwarding routing table $nod e_{n} . T_{r}$ , that is, $rdr . seq > t_{i}^{r} . seq (t_{i}^{r} \in T_{r})$ . Second, it is confirmed that its own identification number is not included in the field of intermediate node list, that is, $nod e_{n} \notin rdr . path_node_list$ . The reason for this is that the route loops are avoided. The number of intermediate nodes stored in the domain of the RDR should be ensured not to exceed threshold, which is denoted by $N_{\max}^{INTER}$ , that is, $| rdr . path_node_list | \leq N_{max}^{INTER}$ . In fact, the value of the $N_{\max}^{INTER}$ is related to the value of the average node hops in the whole network. The analysis method in D Kim and J Lee²⁷ can be used to derive the optimal value of $N_{\max}^{INTER}$ . However, in order to prevent route discovery failure caused by too smaller of $N_{\max}^{INTER}$ , value of $N_{\max}^{INTER}$ is set as a larger value. For example, $N_{\max}^{INTER}$ is set as 14 in this article. Third, it is determined that the number of intermediate nodes, which are stored in RDR but are different from the one that recorded in $nod e_{n} . T_{r}$ , does not achieve the preset value, which is denoted by $N_{diff}^{INTER}$ , that is, $| rdr . path_node_list - t_{i}^{s} . path | \leq N_{diff}^{INTER}$ . For example, $N_{diff}^{INTER}$ is set as 2 in this article. The purpose for this is that the number of the broadcasted route packets are controlled, so that the network overhead can be reduced, and disjunction of the multi-paths is improved. Fourth, the velocity and location information of upstream nodes, which is denoted by $nod e_{n - 1}$ , stored in RDR is extracted. It is judged whether $nod e_{n}$ is a reliable node of $nod e_{n - 1}$ according to the calculation of formula (1). If $nod e_{n} \in S_{n - 1}^{nrbs}$ , the RDR is discarded. Otherwise, go to the next step. Fifth, the link stability is calculated in the light of formula (15), if the value is bigger than the preset threshold, which is denoted by $l s_{th}$ , that is, $l s_{n} > l s_{th}$ , then $rdr . lsfla g_{[n]} = l s_{n}$ . Otherwise, the RDR is discarded directly. Through the fourth and fifth steps, the number of the broadcasted RDR is controlled and the quality of the broadcasted RDR is enhanced to a great extent. Finally, other fields in RDR are added. Such as $nod e_{n} . id$ is added to the domain of the intermediate node list in the RDR, that is, $rdr . path_node_list = {rdr . path_node_list, nod e_{n} . id}$ , the mobility information is added to the domain of the list of the node mobility, that is, $rdr . mob = {rdr . mob, nod e_{n} . mob}$ , and so on. Then, the RDR is broadcasted out.

If an RDA is received by $nod e_{n}$ , it is verified that the sequence number in the RDR is larger than the one record in the $nod e_{n} . T_{r}$ , that is, $t_{i}^{r} . seq > rda . seq (t_{i}^{r} \in nod e_{n} . T_{r})$ . Otherwise, all the entries in the route table should be deleted. Then, the new path in the RDA is added into the entry of the $nod e_{n} . T_{r}$ and the corresponding fields are added as follows: routing label $(t_{i}^{r} . label = rda . label)$ , identification number of source node $(t_{i}^{r} . souid = rda . souid)$ , identification number of destination node $(t_{i}^{r} . desid = rda . desid)$ , sequence number $(t_{i}^{s} . seq = rda . seq)$ , QoS priority $(t_{i}^{r} . qos = rda . qos)$ , next hop $(t_{i}^{s} . next_hop = rda . next_hop)$ , link stability $(t_{i}^{r} . link_sta = rdr . lsflag)$ , and node mobility $(t_{i}^{r} . mob = rdr . mob)$ . Then, the RDA is transmitted to the next hop according to the source route stored in RDA.

If the RTD is received by $nod e_{n}$ , then RTD is forwarded to the next hop according to the source route stored in the header of RTD.

If the RER is received by $nod e_{n}$ , the forwarding route table is updated first, then the RER is transmitted to the next hop according to the source route stored in RER.

Destination node operation

There are two types of packets that can be processed by the destination node, which is denoted by $nod e_{D}$ , that is, RTD and RDR. The flowchart of the destination node operation is shown in Figure 6.

Figure 6.

Flowchart of destination node operation.

If RDR is received by $nod e_{D}$ , it is first confirmed that the sequence number in RDR is larger than the one recorded in the $nod e_{D} . T_{r}$ , that is, $rdr . seq > t_{i}^{r} . seq (t_{i}^{r} \in nod e_{n} . T_{r})$ , and then $t_{i}^{r} . seq = rdr . seq$ . Second, RDR waiting timer, which is denoted by $time r_{rdr}$ , is started and set as $time r_{rdr} = T_{rdr}$ . What needs to be specially stated is that the $tim e_{rdr}$ is canceled if the total number of the arrived RDRs is larger than the corresponding reception threshold, which is denoted by $N^{rdr}$ , within timer validity period. However, RDRs are also discarded even if the total number of the arrived RDRs is lower than $N^{rdr}$ when $time r_{rdr}$ is expired. So that the waiting time of RDA in source node is reduced, thus the end-to-end delay is also depressed to a certain extent. Third, the RDA and the corresponding label, which is used for the subsequent fast routing and is denoted by $label$ , is generated randomly for the source route carried in the RDR by $nod e_{D}$ . Then, the value of the key field such as the routing information in the received RDR packet is assigned to the corresponding domain of the RDA packet as follows: identification number of source node $(rda . sourid = rdr . destid)$ , identification number of destination node $(rda . destid = rdr . sourid)$ , intermediate nodes in the source route $(rda . path_node_list = rdr . path_node_list)$ , mobility information of nodes in the source route $(rda . path_mob_list = - rdr . path_mob_list)$ , QoS priority $(rda . qos = rdr . qos)$ , sequence number $(rda . seq = rdr . seq)$ , random label $(rda . label_id = label)$ , and link stability $(rda . link_sta_list = - rda . lin_sta_list)$ . Fourth, the entry $t_{i}^{r}$ of the forwarding route table $nod e_{D} . T_{r}$ is updated as follows: $t_{i}^{r} . label_id = rda . label_id$ , $t_{i}^{r} . sourid = rda . sourid$ , $t_{i}^{r} . destid = rda . destid$ , $t_{i}^{r} . seq = rda . seq$ , $t_{i}^{r} . next_id = rda . path_node_lis t_{[H - 1]}$ , $t_{i}^{r} . qos = rda . qos$ , $t_{i}^{r} . path_mob_list = rda . path_mob_list$ , and $t_{i}^{r} . link_$ $sta_list = rda . link_sta_list$ . Finally, the RDA packet is sent out.

If the RTD is received by $nod e_{D}$ , it is delivered to the application for further processing.

Multi-path maintenance

Source route maintenance and repair

During source route maintenance, there is a lifetime, which is denoted by $T^{S, D}$ , for each source route in $T_{s}$ from source $nod e_{S}$ to destination $nod e_{D}$ . If $T^{S, D}$ is expired, all route entries in $T_{s}$ is cleared. If there is any new traffic flow transmitted to some destination $nod e_{D}$ , then the route discovery process is restarted by the $nod e_{S}$ . The path stability carried in RDA is used as the statistics result for the maintenance of path stability, and the value is updated until the next route discovery process is started. If there is a link fault occurred in the path, a route error packet (RER) is transmitted by the sending end of the link for the failure report to $nod e_{S}$ . When the RER is received by $nod e_{S}$ , the route item, whose label is equal to the one carried in the RER, that is, $t_{i}^{r} . label_id = rer . label_id$ , is deleted.

Multi-path selection

The multi-paths selection mechanism is the comprehensive consideration under the path stability and the path similarity, so that traffic flow with some priority is transmitted according to the selected multi-paths. It is assumed that there are $M$ types of traffic flow priority in FANET, which is the QoS evaluation parameter and is denoted by $p = [p_{1}, p_{2}, \dots, p_{M}]$ . The QoS level of the traffic flow is decremented with the increased value of the traffic priority, that is, the QoS level of the traffic corresponding to the priority 1 is the highest, and the QoS level of the traffic corresponding to the priority $M$ is the lowest. However, low-priority traffic flow should not be “starved” for the consideration of the fairness. It is assumed that there are $K$ paths to $nod e_{D}$ discovered by $nod e_{S}$ , which are denoted by ${P^{1}, P^{2}, \dots, P^{K}}$ , where $P^{k} = {P_{1}^{k}, P_{2}^{k}, \dots, P_{h_{k}}^{k}}, 1 \leq k \leq K, h_{k} = t_{k}^{s} . hops$ . The corresponding path stability vector of the multi-paths is denoted by $PS = [p s_{1}, p s_{2}, . . ., p s_{K}]$ , where $p s_{k}, 1 \leq k \leq K$ is the stability value of the path $P^{k}$ . The similarity, which is denoted by $ω_{1, 2}$ , between any two paths $P^{k_{1}}$ and $P^{k_{2}}$ is defined as the same number of intermediate nodes on both paths. The smaller $ω_{1, 2}$ is, the stronger independence between $P^{k_{1}}$ and $P^{k_{2}}$ is. This also means that the same traffic flow transmitted on $P^{k_{1}}$ and $P^{k_{2}}$ is more reliable, the different traffic flows transmitted on $P^{k_{1}}$ and $P^{k_{2}}$ are more effective. Therefore, the similarity of the two most independent paths in $nod e_{S} . T_{s}$ is given as follows

ω = \min_{\begin{matrix} 1 \leq k_{1} \leq h_{k_{1}} \\ 1 \leq k_{2} \leq h_{k_{2}} \end{matrix}} ω_{k_{1} k_{2}}, k_{1}, k_{2} \in {1, 2, \dots, K}, k_{1} \neq k_{2}

(19)

If the priority of the traffic flow which is waited for transmitting in $nod e_{S}$ is $p_{m}, 1 \leq m \leq M$ , the value for the mode selection of flow transmission is denoted by $δ$ and is defined as

δ = α p_{m} + β ω_{k_{1}, k_{2}} + μ (| p s_{k_{1}} - p s_{\min} | + | p s_{k_{2}} - p s_{\min} |)

(20)

where $α$ , $β$ , and $μ$ are the weighting factor; $p s_{\min} = \min_{1 \leq k \leq K} (p s_{k})$ ; and $α + β + μ = 1$ . The threshold value for the mode selection is denoted by $v$ . If $v > δ$ , the same data flow is transmitted on the two selected paths $P^{k_{1}}$ and $P^{k_{2}}$ , so that the reliability of network communication and the invulnerability of the network topology are improved and enhanced. Then, some malicious attacks, such as low-power attack, selective forwarding attack, and routing attack, in FANET are prevented to a certain extent. If $v \leq δ$ , different traffic flows are transmitted on the two selected paths $P^{k_{1}}$ and $P^{k_{2}}$ , so that the effectiveness of data transmission is improved.

Simulation and results

In this section, the parameters used in protocol simulation and the parameters for the protocol performance analysis are introduced first, which is corresponding to section “Baseline description.” Then, the performance of VaSe-MRP is verified through extensive simulations and comparison with other two representative protocols, which is corresponding to the section “Result analysis.”

Baseline description

For the performance evaluation of the proposed algorithm, other reference protocols, which are called packet redundancy multi-path based on link lifetime estimation (PRMLE) mechanism ²⁹ and link availability estimation based routing (LEBR) protocol,³⁰ were compared with VaSe-MRP on the NS-2 simulator. The core ideas and implementation of the three protocols can be seen from Table 2. The three protocols are mainly compared and analyzed from the perspective of the average convergence time (CT) of routing discovery, ETH of the network, the average transmission delay (ATD) of the data flows and ROH of the data flows, so the effectiveness and superiority of VaSe-MRP can be verified. LEBR is based on ad hoc on-demand distance vector (AODV) protocol. It is noted that there is only one hop information of the forwarding nodes is contained in the RDR and RDA packets of AODV. The local routing repair mechanism in PRMLE means that the data can be cached and the route discovery progress can be initiated by the intermediate node for a new path to the destination node when the stability of a link in the data transmission path is reduced. However, the route repair of the VaSe-MRP is performed by the $nod e_{S}$ in the style of controlling centrally. In addition, it is demonstrated that a large overhead and waste of resources in data transmission will be caused by RTS/CTS/DATA/ACK multiple handshake mechanism of CSMA/CA protocol, which may be unsuitable to FANET, in traditional short-distance communication MANET. To that end, the function of MAC layer is realized by statistic priority-based multiple access (SPMA) of SM Clark et al.³¹ in the simulation platform for supporting the operation of Vase-MRP. In the physical layer of the simulation platform, the Nakagami-m-based radio propagation model proposed in IY Abualhaol and MM Matalgah³² is used in the NS-2 for the supporting FANET communication.

Table 2.

The core ideas and implementation of the three protocols.

Protocol	Link stability criteria	Path stability criteria	Protocol category	Routing repair	Link correlation
PRMLE	Link Lifetime: periodic sampling of received power between adjacent nodes with formulas (1)–(18) in DP Wu et al.²⁹	Path lifetime (PL): P L = min (LL₁, …, LL_N)	Improved DSR, single BP	Local repaired by intermediate nodes	No considered
LEBR	Link validity (L): ratio of link LL to average LL with formulas (29) and (30) in L Lei et al.³⁰	Path validity: $P_{LA} = Π_{i = 1}^{N} L_{i}$	Improve AODV No BP	No	Not considered
VaSe-MRP	Link stability: formula (14)	Path stability: formula (15)	Improve DSR multiple BP	Repaired by source node	Considered

VaSe-MRP: velocity-aware and stability-estimation–based multi-path routing protocol; AODV: ad hoc on-demand distance vector; BP: backup path; DSR: dynamic source routing.

Result analysis

Comparison of the CT in routing discovery

For the verification of the convergence speed of VaSe-MRP, the CT, which is the time that one route from $nod e_{S}$ to $nod e_{D}$ is discovered, of VaSe-MRP, PRMLE, and LEBR is compared, respectively. There are $N_{num}$ node distributed randomly in the area of $500 m \times 500 m$ . The single routing discovery of the three protocols is performed in every period, which is denoted by $T_{0} = 1 s$ , and the progress of routing discovery is performed 100 times in total. The pair $(nod e_{S}, nod e_{D})$ in each period is randomly selected, and the number of the pairs between $nod e_{S}$ and $nod e_{D}$ is set 6 in every period. RDR is broadcasted at the beginning of the period by $nod e_{S}$ , and the progress of routing discovery is finished when the specified number of RDAs is received by $nod e_{S}$ . The moving speed and direction of each node are uniformly distributed, that is, $V_{i} ~ U (0, V_{max})$ and $ϑ ~ U (- π, π)$ , and are remained constantly. The time of routing discovery in the three protocols are counted, and CT is set as the average of 100 output finally. It should be noted that although FANET is usually operated in 3D space, our simulation is performed in 2D space for the convenience of calculation and simulation. In fact, our algorithm is equally applicable to 3D space simulation, and there are only some additional spatial information need to be added in the fields of the relevant routing signaling packets.

The following assumptions is made in simulation for the avoidance of the influence of settings from other layer on protocol performance evaluation. For example, communication back-off between nodes, transmission bandwidth allocation, delay of processing and routing table storage, and so on. First, the update time of RDR in each intermediate forwarding node is set to 10 ms. Second, the transmission time between adjacent nodes is 20 ms. Third, the receiving time, which including the multi-path selection time, of RDA at $nod e_{S}$ in PRMLE and VaSe-MRP is 20 ms, and the time of path selection in LEBR is also set as 30 ms. Purpose for this is that the path whose link availability optimal is selected in one routing decision. Finally, the condition of link rupture is that the distance between two nodes is larger than the transmission radius $R = 50 m$ . If the link that is responsible for RDA transmission is broken at this time, the routing establishment is failed. Then, the RDR is rebroadcasted by $nod e_{S}$ for routing discovery again.

The relationship between CT and $N_{num}$ in the three protocols when $V_{\max} = 6 m / s$ is shown in Figure 7. It can be seen from the figure that the CT of the three protocols generally decreases with the raise of $N_{num}$ . This is because the average distance between nodes is decreased when the node density is increased and the link stability is also increased, which is beneficial to the establishment of high-quality routes. In addition, the CT of VaSe-MRP is significantly smaller than that of the other two protocols when $N_{num}$ is small. The relationship between CT and $V_{\max}$ in the three protocols when $N_{num} = 20$ is shown in Figure 8. As can be seen from Figure 8, the link stability is decreased with the raise in $V_{\max}$ , so that the CT of each protocol is increased. However, the CT curve of VaSe-MRP is increased most gently, and the value of CT in VaSe-MRP is significantly lower than the other two protocols after $V_{\max} > 6 m / s$ .

Figure 7.

Convergence time of routing protocol versus number of nodes.

Figure 8.

Convergence time of routing protocol versus maximum node mobility.

In summary, the convergence speed of the three routing protocols is equivalent when the network state is in a good state, that is, larger $N_{num}$ and smaller $V_{\max}$ . When the connectivity of the network node is reduced or the mobility of the node is increased, the CT of the VaSe-MRP is shorter than that of the other two protocols. Therefore, there are some certain advantages in VaSe-MRP when compared with other two protocols in the same situation. The root reason for this result is that the other two protocols are limited with the path stability criteria, in which statistical correlation between the adjacent link is not considered completely. The path routing decision in the $nod e_{S}$ may be not necessarily optimal, the probability of RTD failing to be transmitted to the $nod e_{D}$ increased substantially due to the link fault. However, two RDAs need to be sent to the $nod e_{S}$ on different paths in PRMLE, which additionally increases the time required for routing discovery. The accurate estimation of LRSD and PRSD is used in VaSe-MRP for the improvement of the selected path stability, in which the routing establishment time is also shortened significantly.

Comparison of network performance parameters

The following settings are made in the simulation when the impact of VaSe-MRP on the overall performance of the network is verified. First, the influence of MAC layer and physical layer, such as transmission errors caused by channel fading or disorder, is not considered in the simulation. It is considered that the data are correct received when the data are transmitted to $nod e_{D}$ . Second, it is assumed that there is sufficient bandwidth in the communication links for the avoidance of network congestion. Third, the RDA should be received by $nod e_{S}$ correctly. Fourth, the continued data retransmission is permitted in the progress of routing repair without restarting the routing discovery. If the routing discovery is restarted, the received part of the data stream is discarded and the retransmission is waited by $nod e_{D}$ . Finally, the random mobility model of each node is the same, that is, $V_{i} ~ U (0, V_{\max}), ϑ ~ U (- π, π)$ .

The detailed simulation parameters used in this case are shown in Table 3. The expected transmission delay, which is denoted $T_{e}$ , of each constant bit rate (CBR) data flow used in the application layer of the simulation is set as $T_{e} = 0.5 s$ . The $prsd (T)$ and $lrsd (T)$ are valued $T = (1 + υ) T_{e}$ . $0 < υ < 1$ is the presupposition factor of the protocol. The purpose of setting $υ$ is that the LRSD (PRSD) value of each link (path) is greater than $T_{e}$ is stipulated and guaranteed in theoretically. Second, six data requests, which including different $nod e_{S}$ and $nod e_{D}$ , are allocated in the system at the initial time of the simulation period, which is denoted by $T_{0}$ and set as $T_{0} = 1 s$ , under each group of parameters. Each performance index in $T_{0}$ is recorded, and the average of all output values of each index is taken as the final statistical result at the end of the simulation, that is, $100 \times T_{0}$ . Finally, if the data transmission cannot be completed after the route discovery process restarting three times, the data will be discarded. The transmission period of the HELLO packet used to sample the power in PRMLE is set as 0.1 s.

Table 3.

Simulation parameters.

Parameter name	Parameter value
Simulation area	$500 m \times 500 m$
Route discovery period, $T_{0}$	1 s
Traffic type	Fixed CBR
Transmission rate	1.024 Mbps
Path selection time limit	30 ms
Minimum rate of nodes	0
$N_{num}$	12–28
Simulation time	$100 T_{0}$
Single data size	1024 bit
Routing protocol	VaSe-MRP, LEBR, PRMLE
Node transmission radius	50 m
Maximum rate of nodes	2–10 m/s

VaSe-MRP: velocity-aware and stability-estimation–based multi-path routing protocol.

Figures 9 –11 are the curves trend of ETH, average data transmission delay, and ROH varied with the number of network nodes, that is, $N_{num}$ , in the three protocols. In this situation, the maximum moving velocity of the nodes is $V_{\max} = 6 m / s$ . Generally speaking, increasing the number of network nodes is equivalent to increasing the density of network nodes when the simulation area is fixed, so the network connectivity and node routing opportunities are also increased, then the network performance is optimized in the whole.

Figure 9.

Throughput versus number of nodes $N_{num}$ .

Figure 10.

Average delay of data transmission versus number of nodes $N_{num}$ .

Figure 11.

Routing overhead versus number of nodes $N_{num}$ .

As can be seen from Figure 9, the ETH of VaSe-MRP is about 12% higher than that of other two protocols. The optimization effect of the ETH is most obvious when $N_{num} \in U (16, 24)$ . When $N_{num} < 22$ , the ETH of LEBR outperforms that of PRMLE. However, performance of PRMLE outperforms that of PRMLE in terms of ETH when $N_{num} > 22$ . This is because that the route repair mechanism of PRMLE shows the obvious advantages when the node density is larger. It is also shown in Figure 10 that the average delay for data transmission of VaSe-MRP and PRMLE is 15% lower than that of LEBR. This contrast is most obvious when the $N_{num}$ is small. When $N_{num} = 12$ and the gain of average delay can be attained 26%. The fundamental reason for this result is that there is the function of fast routing repair mechanism in VaSe-MRP and PRMLE, in which multiple routing discoveries and data retransmissions caused by link breaks between $nod e_{S}$ and $nod e_{D}$ can be effectively avoided, thus better continuity of communication link is guaranteed. In Figure 11, the source ROH of VaSe-MRP is significantly lower than that of PRMLE. When $N_{num} = 12$ and $N_{num} = 28$ , the source ROH of PRMLE is 1.6 and 2 times that of VaSe-MRP, respectively. The results show that although the same effect on average delay of PRMLE is achieved as that of our VaSe-MRP, it is at the expense of more ROH. This is because that except signaling packages such as RDR, RDA, and RER used for source routing discovery are in PRMLE, there are also a large number of routing hello packets (RHEs) used for periodic exchange of the LRSD estimation information, where the ROH is increased to a certain extent.

Figures 12 –14 are the curves trend of ETH, average data transmission delay, and ROH varied with the maximum moving velocity of the network nodes in the tree protocols, where the number of the nodes is given as $N_{num} = 20$ . On the whole, as the stability of links is broken to a great extent with the increase in $V_{\max}$ , the network performance of the three protocols is decreased with the raise of $V_{\max}$ . As can be seen from Figure 12, ETH of LEBR and PRMLE in this scenario is comparable. However, all of their throughput are about 10% lower than the ETH of VaSe-MRP. This trend is obvious under every value of $V_{\max}$ . This is because the correlation of LRSD between links is taken into account in VaSe-MRP, so the selected multi-path for data transmission is more stable than other two protocols, then the ETH improved. In Figure 13, the average delay of VaSe-MRP is the smallest and the corresponding curve is increased most gently. The average delay of PRMLE and LEBR is increased significantly after $V_{\max} = 7 m / s$ and $V_{\max} = 8 m / s$ respectively. It also can be seen that the average delay of LEBR is about 1.1 times than that of VaSe-MRP when $V_{\max} = 2 m / s$ , and the former is about 1.5 times than that of the latter when $V_{\max} = 10 m / s$ . This is because that the link stability and node speed can be accurately estimated and sensed in VaSe-MRP, then the probability of successful route discovery is improved. As a result, the ATD is greatly reduced. The comparison results of the source ROH shown in Figure 14 is in accordance with the changing trend in Figure 13. It is clear that ROH of VaSe-MRP is lower than that of the other two protocols. In particular, in the case of $V_{\max} = 2 m / s$ and $V_{\max} = 10 m / s$ , the ROH of PRMLE is about 1.8 and 2.2 times of that in VaSe-MRP, respectively. This is because frequent interactions of routing signaling based on the AODV framework and frequent route discoveries caused by the lack of awareness of link state and node speed are avoided in VaSe-MRP, so ROH is minimal in VaSe-MRP relative to PRMLE and LEBR.

Figure 12.

Throughput versus node mobility $V_{\max}$ .

Figure 13.

Average delay of data transmission versus node mobility $V_{\max}$ .

Figure 14.

Routing overhead versus node mobility $V_{\max}$ .

In summary, the effectiveness and superiority of VaSe-MRP is fully verified with the simulation results from Figures 7 –14. Compared with the existing protocols, the LRSD correlation between adjacent links is taken into account in VaSe-MRP, which is beneficial to establish more accurate and reliable stability evaluation criteria. As a result, the data flow is transmitted on paths that the duration is longer, and the adverse effects of high-speed mobility on data transmission is reduced effectively. There is much stronger adaptability in VaSe-MRP. Meanwhile, the much lower ROH is ensured significantly with the improved ETH and the shortened average delay of data transmission in VaSe-MRP, so that the reasonable trade-off between stability and resource utilization is obtained commendably.

Conclusion

Based on the analysis of the statistical characteristics of PRSD and the consideration of the LRSD correlation between adjacent links, a path stability evaluation criterion is presented in this article and then a VaSe-MRP is proposed. Compared with the existing related routing protocols, it is shown in the simulation results that the more stable evaluation criteria of the path stability and the faster convergence speed of the routing discovery, where the network topology is changed dynamic, are provided in VaSe-MRP, and the adverse impact of the increased mobility of nodes on data transmission is also reduced effectively. There is some certain reference significance in terms of evaluating the route stability, improving network throughput, shortening data transmission delay, and reducing ROH in VaSe-MRP.

However, the high-speed mobility of nodes and routing security requirements in FANET are not taken account in VaSe-MRP. This is also where the agreement needs to be improved and perfected in the future. The better network robustness and security will be presented in the improved VaSe-MRP. For example, if there is at least one path to destination node $nod e_{D}$ in the forwarding table of the intermediate node $nod e_{n}$ , that is, $nod e_{n} . T_{r}$ , then the corresponding RDA is fed back directly by $nod e_{n}$ to $nod e_{S}$ . The malicious attack nodes in the network will use this mechanism to carry out routing attacks and traffic attraction attacks. When an RDR is received by the malicious node, it is falsely claimed that there is a route to $nod e_{D}$ in itself, and some false RDA are sent to $nod e_{S}$ . When the false RDA is received by $nod e_{S}$ , then the RTD is send sent to the malicious node according to the false path, so that the traffic of $nod e_{S}$ is attracted by malicious nodes. The received RTD is discarded simply by the malicious nodes, which causes that the RTD is not received by the real destination node. For this reason, some security risks such as routing attacks are brought in FANET with the process. The design for the route under the security consideration is our future work.

Footnotes

Handling Editor: Daniel Gutierrez-Reina

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: This work was supported in part by the National Natural Science Foundations of China (grant no. 61461023), Youth Natural Science Foundations of Gansu (grant nos 18JR3RA231, 1610RJYA021, and 1606RJYA271), Gansu University Research Project (grant nos 2016A-98, 2017A-104, and 2018A-124), Lanzhou Science and Technology Plan Project (grant nos 2017-4-101 and 2018-RC-31), Gansu Universities Innovation Ability Promotion Project (grant no. 2019A-144), Research Project of Innovation and Entrepreneurship Education Reform for Gansu Universities (grant no. 2019-26), Cooperative Education Project of Education Ministry (grant no. 201802048017), “Kaiwu” Innovation Team Support Project of Lanzhou Institute of Technology (grant no. 2018KW-01), and “Qizhi” Talent Cultivation Project of Lanzhou Institute of Technology (grant no. 2019QZ-03).

ORCID iD

Zhongyu Ma

References

Bekmezci

Sahingoz

Temel

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

Oubbati

Lakas

Zhou

, et al. A survey on position-based routing protocols for Flying Ad hoc Networks (FANETs). Veh Commun 2017; 10: 29–56.

Jiang

Han

Routing protocols for unmanned aerial vehicles. IEEE Commun Mag 2018; 56(1): 58–63.

Khelifi

Bradai

Singh

, et al. Localization and energy-efficient data routing for unmanned aerial vehicles: fuzzy-logic-based approach. IEEE Commun Mag 2018; 56(4): 129–133.

Luo

Wang

FRUDP: a reliable data transport protocol for aeronautical ad hoc networks. IEEE J Sel Area Comm 2018; 36(2): 257–267.

Xie

Wan

Kim

, et al. A survey and analysis of mobility models for airborne networks. IEEE Commun Surv Tut 2013; 16(3): 1221–1238.

Baccour

Koubâa

Mottola

, et al. Radio link quality estimation in wireless sensor networks: a survey. ACM T Sensor Network 2012; 8(4): 34–41.

Zheng

Sangaiah

Wang

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

Chen

Zhao

, et al. A scheme for improving the communications efficiency between the control plane and data plane of the SDN-enabled airborne tactical network. IEEE Access 2018; 6: 37286–37301.

10.

Lim

Chae

, et al. Active detection in mitigating routing misbehavior for MANETs. Wirel Netw 2019; 25: 1669–1683.

11.

Yin

Xiao

Cao

, et al. Enhanced routing protocol for fast flying UAV network. In: 2016 IEEE international conference on communication systems (ICCS), Shenzhen, China, 14–16 December 2016, pp.1–6. New York: IEEE.

12.

Wang

Ertrk

Liu

, et al. Throughput and delay of single-hop and two-hop aeronautical communication networks. J Commun Netw 2015; 17(1): 58–66.

13.

Rutagemwa

Vigneron

Cross-layer design and performance analysis of tactical radio networks. IEEE T Veh Technol 2015; 64(1): 339–355.

14.

Gupta

Jain

Vaszkun

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

15.

Sundar

Rathinam

Algorithms for routing an unmanned aerial vehicle in the presence of refueling depots. IEEE T Autom Sci Eng 2014; 11(1): 287–294.

16.

Hoffmann

Medina

Wolisz

Joint routing and scheduling in mobile aeronautical ad hoc networks. IEEE T Veh Technol 2013; 62(6): 2700–2712.

17.

Arafat

Moh

Location-aided delay tolerant routing protocol in UAV networks for post-disaster operation. IEEE Access 2018; 6: 59891–59906.

18.

Liu

Peng

, et al. Joint routing and scheduling for vehicle-assisted multi-drone surveillance. IEEE Internet Things 2019; 6: 1781–1790.

19.

Jamming-resilient multipath routing protocol for flying ad hoc networks. IEEE Access 2018; 6: 68472–68486.

20.

Gankhuyag

Shrestha

Yoo

Robust and reliable predictive routing strategy for flying ad-hoc networks. IEEE Access 2017; 5: 643–654.

21.

Luo

Wang

Multiple QoS parameters-based routing for civil aeronautical ad hoc networks. IEEE Internet Things 2017; 4(3): 804–814.

22.

Rosati

Kruzelecki

Heitz

, et al. Dynamic routing for flying ad hoc networks. IEEE T Veh Technol 2016; 65(3): 1690–1700.

23.

Gohari

Pakbaz

Melliar-Smith

, et al. RMR: reliability map routing for tactical mobile ad hoc networks. IEEE J Sel Area Comm 2011; 29(10): 1935–1947.

24.

Bujari

Palazzi

Ronzani

A comparison of stateless position-based packet routing algorithms for FANETs. IEEE T Mobile Comput 2018; 17(11): 2468–2482.

25.

Sharma

Kumar

, et al. DPTR: distributed priority tree-based routing protocol for FANETs. Comput Commun 2018; 22: 129–151.

26.

Mahmud

Cho

YZ.

Adaptive hello interval in FANET routing protocols for green UAVs. IEEE Access 2019; 7: 63004–63015.

27.

Kim

Lee

Integrated topology management in flying ad hoc networks: topology construction and adjustment. IEEE Access 2018; 6: 61196–61211.

28.

Haas

ZJ.

On residual path lifetime in mobile networks. IEEE Commun Lett 2016; 20(3): 582–585.

29.

Wang

Zhen

Link stability aware reliable packet transmitting mechanism in mobile ad hoc network. Int J Commun Syst 2012; 25(12): 1568–1584.

30.

Lei

Wang

Zhou

, et al. Link availability estimation based reliable routing for aeronautical ad hoc networks. Ad Hoc Netw 2014; 20: 53–63.

31.

Clark

Hoback

Zogg

SJF

. Statistical priority-based multiple access system and method. US7680077B1 Patent, 2010.

32.

Abualhaol

Matalgah

MM.

Outage probability analysis in a cooperative UAVs network over Nakagami-m fading channels. In: IEEE conference on vehicular technology, Montreal, QC, Canada, 25–28 September 2006, pp.1–4. New York: IEEE.

VaSe-MRP: Velocity-aware and stability-estimation–based multi-path routing protocol in flying ad hoc network

Abstract

Keywords

Introduction

Motivation

Contribution

Related work

Location-centered routing protocol in FANET

Node-centered routing protocol in FANET

System model

Velocity-aware forwarding

Path/link remaining survival duration

Evaluation criteria of path/link stability

Definition 1

Definition 2

VaSe-MRP

Route discovery

Source node operation

Intermediate node operation

Destination node operation

Multi-path maintenance

Source route maintenance and repair

Multi-path selection

Simulation and results

Baseline description

Result analysis

Comparison of the CT in routing discovery

Comparison of network performance parameters

Conclusion

Footnotes

Declaration of conflicting interests

Funding

ORCID iD

References