I Introduction
Unmanned Aerial Vehicles (UAV) have recently attracted significant interest in many civilian, commercial and military applications. The popularity of UAVs emanate from their low cost, rapid deployment, and ability to fly above obstacles. It is anticipated that the global market revenue of UAVs reach $11.2 billion by 2020 [1]. Some applications require deployment of a large number of UAVs to complete designated tasks [2, 3, 4]. A network of autonomous UAVs form a flying Adhoc network (FANET), which provides more sensing and actuation capabilities. However, it also poses many challenges in designing networking protocols.
One of the main challenges in FANETs is the high degree of mobility which causes frequent changes in network topology. As such, conventional communication protocols face a considerable performance degradation [5, 6, 7]. In routing, for instance, link breakage and frequent topology changes can lead to packet loss, excessive retransmissions and eventually increased delay.
For environments with low degrees of mobility or with geographically confined movements, several routing protocols have been proposed recently. For instance, in vehicular AdHoc networks (VANETs), a routing protocol based on the Dijkstra’s algorithm [8] and an optimized multicast routing protocol [9] have been developed. In [10], a stable routing protocol is presented which finds the most stable path by considering velocity, direction and the link expiration time using fuzzy logic. In addition, learningbased routing protocols (e.g. Qrouting) have been proposed to learn the link states based on the current transmission experience [11]. Such algorithms rely on the assumption of low speed vehicles moving in a confined two dimensional space with limited and predefined movement patterns dictated by obstacles and roads. These assumptions, however, are not realistic in FANETs with UAVs moving freely in space with potentially high speeds.
For dynamic UAV networks, however, there have been few efforts on routing algorithm design. For instance, the authors in [12]
, presented the RARP protocol which utilizes GPS information to estimate the duration of a path. This algorithm is based on AODV
[13] and requires a route setup phase before transmission. To avoid repeated route setups the algorithm assumes that nodes keep their current movement patterns for some period of time which is a typical assumption in mobile AdHoc networks (MANETs). This assumption is not valid for network of autonomous UAVs. This protocol is also evaluated using a mobility model primarily developed for lowspeed terrestrial nodes, hence not suited for freely flying drones. Another recently proposed routing protocol for UAV networks is the PredictiveOLSR [14] which utilizes GPS coordinates to estimate the quality of a link. However, they adopt a restrictive assumption that only the source node is mobile.In this paper, we present a distance greedy routing algorithm for dynamic UAV networks. This algorithm relies on local forwarding decisions and does not require a route setup phase. This lowcomplexity algorithm imposes no additional signaling overhead to the system, hence well suited to dynamic UAV networks. In order to analyze the performance of the greedy routing, we derive analytical lower and upper bounds for the expected number of hops that a packet traverses. Using this result, we find the expected endtoend distance that a packets travels using the greedy algorithm, which can be a ground to optimize distancebased performance metrics such as endtoend delay and transmission power consumption. We also derive the probability of successful delivery which is the probability that all intermediate nodes along the path can forward the packet to a node closer to the destination. Finally, simulation results verify the accuracy of the derived analytical results and also indicate superior performance of the greedy routing compared to the conventional shortest path routing based on Dijkstra’s algorithm [15].
Ii System Model
We consider a FANET with UAV nodes (), distributed uniformly in a rectangular area. Let denote the radius of the circular communication range of a UAV node, then the set of neighbors for node is defined as:
where denotes the Euclidean distance between nodes and . Also, we use the popular mobility model for UAV nodes which integrates linear and circular motions [16]
. Transition between two mobility modes occur based on an underlying Markov process with adjustable transition probabilities. The mobility parameters include speed and direction of linear motion, and initial phase, angular speed, and radius of circular motion. Speed and radii are drawn from exponential distributions and the rest of parameters are uniformly distributed. The parameters are initialized when transition occurs between the two states and remain constant until the next transition.
UAV nodes do not keep track of entire network topology, but each node needs to know the location of its neighbors. We assume the anticipated locations of neighbors can be predicted by a node, either through a modelbased motion trajectory prediction method [17] or exploiting online pathplanning information by UAVs [18]. Also, since the algorithm works based on the remaining distance to the destination, the source node needs to know the location of the destination. This information can be embedded into the packet to inform the intermediate nodes about the destination’s location.
Iii The Distance Greedy Routing Algorithm
Consider a source node who wants to send a packet to a destination node which is located at distance . The distance greedy algorithm works based on a simple forwarding rule. At each step, , the packet is passed by the current node to a neighbor node which is closest to the destination, i.e. . The packet is passed only if the next node makes a progress, (i.e. if the next node is closer to the destination than the current node: ). If such a neighbor does not exist the current session fails and the packet journey is reinitiated. This algorithm continues until the packet is delivered to the destination. This constraint is required to ensure a loopfree path towards the destination. In this way, we guarantee a progress at each step provided that there is at least one neighbor in the progress area.
Fig. 1, represents one iteration of this algorithm. The shaded area represent the valid locations for the next node. This progress area is the intersection of two circles centered at and with radii and , respectively. Here, is the remaining distance to the destination, once the packet reaches node . The algorithm chooses a node which makes the highest progress towards the destination (here ).
Iv Analysis of The Greedy Routing Algorithm
In this section, we evaluate the performance of the greedy routing algorithm through several steps. We first bound the expected number of hops a packet travels from source to destination. Next, using the results we find the expected endtoend distance traversed by the greedy algorithm. Finally, we find the probability of successful delivery in terms of transmission range, number of nodes and the size of the area through finding the probability of having at least one node in the progress area throughout the selected path.
Iva Analysis of The Number of Hops
In order to bound the expected number of hops for sending a packet from source to destination, we first find the probability distribution of the progress made at each hop.
Let denote the area of the shaded region in Fig. 1 which is the intersection of two circles with centers at , and with radii and , respectively. Also, let
be a random variable representing the remaining distance to the destination at the
hop. In fact, represents the distance from destination to its closest node in the shaded area. The probability of being at least equals the probability that there are no nodes in the area which is the overlap of two circles with centers at and , which are at distance of each other, and with radii and , respectively. Since, nodes are distributed uniformly, the number of nodes in any region with areafollows a Binomial distribution with
trials and success probability of . Thus, we find(1) 
where and we can use geometric analysis to find the area as
(2) 
Now, we can find the probability distribution of the progress made at each hop. Let denote the progress the hop, we have:
(3) 
The probability density function (PDF) of
can be computed by taking the derivative of its distribution function in (3). Note that there is a discontinuity point at , therefore we can write the PDF as:(4) 
where denotes the continuous part conditioned on progress, which is the derivative of the distribution function for between 0 and . Knowing the PDF, we can find the expected progress at the hop as follows:
Using integration by parts, we have:
(5)  
where the first term equals since as there is no intersection between two circles with centers at , , which are at distance of each other, and with radii and , respectively.
Now that we have the average progress at each hop, we find the number of hops that a packet traverses to reach a destination located at distance of the source node. The number of hops is of this form; where is the number of hops needed to reach the communication range of the destination. That means, the first hops takes the packet to the destination’s communication range where there is only one hop left to the destination node. We have:
(6) 
It should be noted that is a stopping time step with respect to the sequence . That means, at time we have enough information to stop and we do not need any future information to decide. For a special case of stopping times when the sequence of random variables are independent and identically distributed (i.i.d.), we can utilize the Wald’s equation [19] to find the sum of random variables up to time .
Lemma 1 (Wald’s Equation [19])
If is a stopping time with respect to an i.i.d. sequence , and if and , then
In our case, however, the sequence is not i.i.d., therefore, we cannot directly use the Wald’s equation. For this reason, we first find the number of hops using some i.i.d. random variables . Next, we replace with i.i.d. random variables that upper bound and lower bound . Thereby, we conclude about the bounds on the number of hops a packet travels. Using Lemma 1 for i.i.d. random variables , we have
To find an upper bound for we use the left inequality in (6) and the fact that the progress at each hop is at most ,
taking expectation we have
using (7), we get:
(10) 
As mentioned earlier the random variables are not i.i.d. and we need to bound them using i.i.d. random variables to be able to use the result in (11).
For this purpose, let us define the progress at each hop as a function of the remaining distance to the destination, as . It is worth noting that the is a nondecreasing function of the remaining distance . More precisely, for we have . Intuitively, if there is more distance to the destination it is more likely that we make more progress than the case of having less distance to the destination. This can be shown formally using (3), as follows
(12)  
where the inequality follows from the fact that if we have .
Now, observe that at any of the hops, the distance between the intermediate node and the destination is between and . Using (12), we get
(13)  
Thus, in (11) we can replace with i.i.d. random variables to find a lower bound for the number of hops. Similarly, we can use i.i.d. random variables to find an upper bound.
(14) 
where can be computed using (5) and is an indicator to account for the case where source and destination are immediate neighbors.
IvB Analysis of The EndtoEnd Delay
In this section, we analyze the total distance a packet travels from source to destination using the distance greedy routing. Considering the delay is proportional to the distance, this will give us the endtoend delay metric.
Consider the forwarding scenario at the hop, depicted in Fig. 2, where node has been chosen by the intermediate node and we make a progress of towards the destination. We want to find the distance traveled at the hop (i.e. the length of the line in Fig. 2), which we denote it by . Given the progress , we know that node should be on the arc . Considering the fact that nodes are uniformly distributed, node can be anywhere on the arc with equal probability. Also, the distance of any node on the arc from the transmitting node ranges between and . Therefore, we can roughly estimate that the distance from node to node is uniformly distributed between . That is for the hop.
Now, we can find the expected endtoend distance traveled by a packet as
(15) 
where is the number of hops whose expectation is characterized in (14). Also, we have used the fact that the progresses at each hop sum up to the distance between source and destination, .
IvC Analysis of Network Density for Successful Delivery
In the greedy routing algorithm, we assume that there is always a neighbor to forward the packet towards the destination and thereby we ignore the possibility of the packet reaching an isolated node (more precisely, a node without any progressmaking neighbors). In fact, if the network is dense enough or if the transmission range of nodes are large enough, such a situation can be avoided.
In this section, we find the probability of successful delivery^{1}^{1}1It is worth noting that by successful delivery we mean the packet travels from source to destination without facing an isolated node.. First, we find the probability of a node being isolated which equals the probability of having no node in its progress area. To simplify the analysis, we estimate the progress area of a node by the half of its transmission region which faces the destination. Then, we can write the probability of a node’s isolation, , as
(16) 
we can now solve (16) for and find the minimum transmission range such that the probability of node isolation is less than
(17) 
The probability of success equals the probability of no node along the path being isolated which is , where denotes the number of hopes that is bounded in expectation by (14)
(18) 
V Simulation Results
To test simulations results and prove the efficacy of the analysis work, random networks are generated using uniform distributions for the initial real positions in a grid. We use the mobility model explained in Section II to generate motion trajectories for
nodes. We use the actual positions for all nodes when quantifying the performance metric, but use the predicted positions when finding the optimal path. The predicted locations are the actual locations mixed with Normally distributed prediction noise of variance
.We use dynamic contact graph by making connections between nodes with pairwise distances below . The rest of simulation parameters include number of nodes: , the grid size: , communication range: , average node velocities: , and average waiting time: , unless specified otherwise. Also the transition probability between the circular and linear motions is 20%. Finally, we note that for all figures, we take average over runs of the algorithm with different initializations.
We first, verify the accuracy of the derived upper and lower bounds for two important performance metrics, namely the endtoend delay per packet and the probability of success.
In Fig.3, we present the expected endtoend distance per packet vs . The upper and lower bounds are presented based on 15, where the bounds on the expected number of hops, is obtained from (14). We note that the lower bound is tighter, which is due to the tightness of the lower bound in (14). The fluctuation in the results is due to the average distance between the source and destination (D), which is a probabilistic value.
Another important performance indicator of the proposed algorithm is the probability of success, which means possibility of progress at all intermediate nodes (having at least one node in the current node’s progress area), as characterized in (18) based on the average number of hops per packet in (14). Fig 4 suggests that as we increase the number of nodes, the network density increases and therefore the probability of getting stuck in an intermediate node with empty progress area diminishes. Similar to Fig. 3, the obtained lower bound is more accurate.
Now, we compare the performance of the proposed greedy algorithm with the conventional Dijkstra’s shortest path algorithm in Fig. 5. We also evaluate the proposed algorithm with and without including predictive location information under different average node velocities. The results show that the probability of delivery success for the greedy method is higher than that of the conventional shortest path algorithm consistently for all average node velocities. Also, the predictive greedy method outperforms the static greedy algorithm, which shows including predictive location information decreases the probability of selecting nodes with empty progress area, as was expected. Finally, when the network is more dynamic, more nodes are subject to getting out of the communication ranges of their neighbors, and hence the probability of success declines.
Lastly, in Fig. 6 we present the average power consumption per packet to complete the path for the proposed predictive greedy algorithm and the standard Dijkstra’s algorithm without including predictive information in order to show the practical utility of the proposed method. Since the power consumption is proportional to the sum of all link distances squared, considering predictive information provides a significant gain for our suboptimal algorithm. This gain is higher for more dynamic networks, since the inclusion of predictive locations is more beneficial for higher average node velocities.
Vi Conclusion
In this paper, we studied the routing problem in dynamic UAV networks. Prior approaches fail to perform well in such dynamic environments due to the requirement of maintaining information about the network topology or using frequent routeestablishment phases. We studied an agile distancegreedy routing algorithm which is lowcomplexity and the intermediate nodes take decisions solely based on the predicted locations of their neighbors. This algorithm is fully distributed and incorporates predicted locations into the algorithm, hence outperforms the centralized shortest algorithm. We characterized the number of hops, the probability of success delivery and the expected distance a packet travels based on system parameters. We plan to characterize the impact of the prediction uncertainty on the optimality of the selected path as an extension of this work.
References
 [1] “Gartner says almost 3 million personal and commercial drones will be shipped in 2017,” Feb 2017. [Online]. Available: http://www.gartner.com/newsroom/id/3602317
 [2] A. Razi, F. Afghah, and J. Chakareski, “Optimal measurement policy for predicting uav network topology,” in 51th Asilomar Conference on Signals, Systems and Computers (Asilomar’17), November 2017.
 [3] S. Mousavi, F. Afghah, J. Ashdown, and K. Truck, “Leaderfollower based coalition formation in largescale uav networks, a quantum evolutionary approach,” in IEEE INFOCOM, Workshop on Wireless Sensor, Robot, and UAV Networks, April 2018.
 [4] F. Afghah, M. ZaeriAmirani, A. Razi, J. Chakareski, and E. Bentley, “A Coalition Formation Approach to Coordinated Task Allocation in Heterogeneous UAV Networks,” ArXiv eprints, Nov. 2017.
 [5] A. RoviraSugranes and A. Razi, “Predictive routing for dynamic uav networks,” in 2017 IEEE International Conference on Wireless for Space and Extreme Environments (WiSEE), Oct 2017, pp. 43–47.
 [6] A. Razi, C. Wang, F. Almaraghi, Q. Huang, Y. Zhang, H. Lu, and A. RoviraSugranes, “Predictive routing for wireless networks: Roboticsbased test and evaluation platform,” in 2018 IEEE 8th Annual Computing and Communication Workshop and Conference (CCWC), Jan 2018, pp. 993–999.
 [7] F. Afghah, A. Razi, and A. Abedi, “Stochastic game theoretical model for packet forwarding in relay networks,” Springer Telecommunication Systems journal, Special Issue on Mobile Computing and Networking Technologies, vol. 54, no. 2, pp. 1877–1893, 2013.
 [8] J. d. Zhang, Y. j. Feng, F. f. Shi, G. Wang, B. Ma, R. s. Li, and X. y. Jia, “Vehicle routing in urban areas based on the oil consumption weight dijkstra algorithm,” IET Intelligent Transport Systems, vol. 10, no. 7, pp. 495–502, 2016.
 [9] W. Farooq, M. A. Khan, and S. Rehman, “Amvr: A multicast routing protocol for autonomous military vehicles communication in vanet,” in 2017 14th International Bhurban Conference on Applied Sciences and Technology (IBCAST), Jan 2017, pp. 699–706.
 [10] H. C. Premkumar, V. R. Budyal, and M. S. Kakkasageri, “Cognitive agent based stable routing protocol for vehicletovehicle communication,” in 2016 IEEE Annual India Conference (INDICON), Dec 2016, pp. 1–5.

[11]
S. P. Choi and D.Y. Yeung, “Predictive qrouting: A memorybased reinforcement learning approach to adaptive traffic control,” in
Advances in Neural Information Processing Systems, 1996, pp. 945–951.  [12] G. Gankhuyag, A. P. Shrestha, and S. J. Yoo, “Robust and reliable predictive routing strategy for flying adhoc networks,” IEEE Access, vol. 5, pp. 643–654, 2017.

[13]
C. Perkins and E. Royer, “Adhoc ondemand distance vector routing,” in
Mobile Computing Systems and Applications, 1999. Proceedings. WMCSA’99. Second IEEE Workshop on. IEEE, 1999, pp. 90–100.  [14] S. Rosati, K. Krużelecki, G. Heitz, D. Floreano, and B. Rimoldi, “Dynamic routing for flying ad hoc networks,” IEEE Transactions on Vehicular Technology, vol. 65, no. 3, pp. 1690–1700, March 2016.
 [15] E. W. Dijkstra, “A note on two problems in connexion with graphs,” Numer. Math., vol. 1, no. 1, pp. 269–271, Dec. 1959.
 [16] O. Bouachir, A. Abrassart, F. Garcia, and N. Larrieu, “A mobility model for uav ad hoc network,” in 2014 International Conference on Unmanned Aircraft Systems (ICUAS), May 2014, pp. 383–388.
 [17] G. Aoude, J. Joseph, N. Roy, and J. How, “Mobile agent trajectory prediction using bayesian nonparametric reachability trees,” Proc. of AIAA Infotech@ Aerospace, pp. 1587–1593, 2011.
 [18] G. D. Goez, R. A. V. Velez, and J. S. B. Valencia, “Uav route planning optimization using pso implemented on microcontrollers,” IEEE Latin America Transactions, vol. 14, no. 4, pp. 1705–1710, April 2016.
 [19] A. Wald, “Sequential tests of statistical hypotheses,” Ann. Math. Statist., vol. 16, no. 2, pp. 117–186, 06 1945.
Comments
There are no comments yet.