OPAR: Optimized Predictive and Adaptive Routing for Cooperative UAV Networks

Cooperative unmanned aerial vehicle (UAV) networks, also known as flying ad hoc networks (FANETs), are easy to deploy, low cost, and flexible networks [1, 2]. In many applications, the network is considered for surveillance missions where the UAVs are tasked with sending high volume data (video, images, and other sensory data) to other UAVs or a ground station. Critical UAV missions such as patrolling, where the UAVs are tasked with monitoring a wide area or performing reconnaissance missions in a region, is an application instance. In such applications, the UAVs may not follow pre-defined paths, and their motion should be randomized to some extent [3, 4]. Such applications involve reliable delivery of information and cannot afford to lose information as a likely case in common routing protocols. Multi-hop communication has been recognized as a common communication technique to transfer UAVs’ observed information to the base station noting the limited communication range and bandwidth of the UAVs, particularly in large-scale UAV networks or in areas where communication infrastructure is not available.

The majority of currently deployed cooperative routing protocols in UAV networks are borrowed from mobile ad hoc networks (MANET) and vehicular ad hoc networks (VANET). They target finding the shortest path between the source and destination nodes. Ad-hoc on-demand distance vector (AODV), destination sequenced distance vector (DSDV), and optimized link state routing (OLSR) are some instances. However, these routing algorithms are deemed inefficient in UAV networks as they are not customized to these networks’ specific attributes. The main difference between the UAV networks and other typical multi-hop networks is their highly dynamic nature due to the higher speed and speed variability of nodes. The free movement in the three-dimension space and energy constraints are the other reasons which impact the link quality and cause link outages. Consequently, the network experiences multiple reroute processes, which impose a high volume of routing traffic overhead. This overhead causes failures in many communication flows, significantly degrades the network performance, dramatically decreases the throughput, and increases the flow completion time (FCT). Furthermore, due to the limited queue size of cooperative nodes, the TCP protocol has to deal with a large number of packets arriving out-of-order as being dropped and order a re-transmission for them. A large amount of such out-of-order packet delivery is caused by the packets belonging to the same flow transferred from different paths due to the multiple reroute processes. This fact results in a noticeable network performance degradation. Hence, in highly dynamic networks with high mobility, the routing protocols based on the shortest path are not always the ideal solution [5].

To minimize the number of rerouting processes in UAV multi-hop communications, we propose to consider path lifetime. We define the path lifetime as the minimum link lifetime for the links that form a path. Since the path with the longest lifetime can be much longer than the shortest path, it might not be the ideal solution too. Therefore, in this work, we aim to find a path that optimizes the network performance in terms of throughput, flow completion time, and flow success rate by taking both the path length and path lifetime into account.

Several research efforts have recently focused on developing routing solutions for cooperative UAV networks. Some of them are designed to support mission-specific UAV networks, and hence their solution cannot be generally used [6, 7, 8]. Just a couple of the proposed routing algorithms have accounted for the link reliability [9, 10, 11]. Alas, none of the previously reported works optimizes their routes to achieve the highest performance in terms of throughput, FCT, and flow success rate. This fact motivates us to generalize the routing problem of highly dynamic cooperative UAV networks by proposing OPAR, a general routing algorithm that takes both the path lifetime and path length into consideration to offer a reliable information flow delivery in highly dynamic networks.

We first define a general Boolean LP problem that optimizes the path length and path lifetime altogether. The LP problem relies on the link lifetime prediction. Thus, we propose a precise link lifetime prediction algorithm that considers the movement direction in polar and azimuthal directions, the speed, and the acceleration of the nodes. The proposed algorithm is lightweight and needs only three consecutive locations of the UAVs. We further propose a polynomial-time algorithm that finds the optimization problem’s solution in a low time complexity with the worst-case complexity of $O(|E|^{2})$.

We assume that the UAVs have a reliable low bandwidth communication channel with the ground station. The UAVs send their locations to the ground station via a control message. The ground station is responsible for gathering this data and making the decision about the routes. Since the OPAR algorithm is lightweight, the ground station’s role can be easily distributed among the UAVs. However, since there might not be a path between some network nodes, finding the optimal path may not be feasible in some cases, in the absence of the ground station. To show the effect of the proposed analytical model, in this work, we assume such a ground station.

To evaluate the performance of OPAR, we use the network simulator ns-3 [12]. We compare OPAR with three well-known routing algorithms, AODV, OLSR, and DSDV, through extensive simulations. We choose them to cover different types of routing algorithms, including both categories of proactive and reactive protocols as well as distance vector and link-state methodologies. As the performance metrics, we calculate the delivery success rate, the routing traffic, network throughput, and FCT. This evaluation shows that OPAR prevents the massive volume of routing overhead caused by the typical cooperative routing algorithms. It decreases the FCT by an average of $25\%$ and improves the throughput of the network by up to three times the throughput of other routing algorithms. More importantly, the successful flow completion rate of OPAR is, in the worst case, $20\%$ more than other algorithms.

Contributions: The main contribution of this work is to optimize the route selection in cooperative UAV networks to maximize the network performance in terms of throughput, FCT, and flow success rate. More specifically, this work $i)$ analytically models the routing problem in UAV networks by jointly maximizing the path lifetime and minimizing the path length; $ii)$ precisely predicts the link lifetime of the entire network; $iii)$ finds a lightweight algorithm to solve the optimization problem in polynomial time complexity; and $iv)$ extensively evaluates the proposed algorithms’ performance by comparing it with the state-of-the-art through ns-3 simulations.

System model: We model this network with a graph $G(V,E)$, where $V$ and $E$ represent the set of graph vertices and graph edges, respectively. Each vertex in graph $G$ represents a UAV node, where each edge represents the direct communication between the corresponding vertices. The edge $e_{(i,j)}\in E$ means that node $n_{j}$ is in the communication range of node $n_{i}$. Since the nodes’ communication range may differ from one to another, the graph links are directed. The UAV nodes are mobile; thus, each graph link has a lifetime, limited by the node’s transmission range and distance from the neighbor. For the model to be general, the nodes can move randomly in any direction, hover to complete their tasks, land to recharge their battery or change their payload or move according to a pre-defined path. Indeed, less movement makes the problem more tractable. However, we consider the problem in its most general form.

The goal is to find a path that maximizes the network’s performance, knowing that the path length is not the only effective metric. Path lifetime is the other impacting factor that should be taken into account. Assuming that we have a precise link lifetime prediction matrix $\mathcal{T}$, where $\tau_{(i,j)}\in\mathcal{T}$ is the lifetime of the edge $e_{(i,j)}$. Let us consider the variable $x_{(i,j)}$ as a Boolean variable specifying whether the link $e_{(i,j)}$ participates in the optimized path or not. On the one hand, the objective function of minimizing $\sum x_{(i,j)}$, such that the chosen edges form a path from the source to the destination, guarantees the shortest path. On the other hand, maximizing $\tau$ where $\tau$ is the path lifetime guarantees the path with the longest lifetime. If we design a multi-objective optimization problem that considers both of the mentioned metrics together, the solution will be an area of feasible solutions. Based on the priority of the objectives, the solution could be any points in this area. However, we designed the following Boolean LP that considers both metrics of interest, simultaneously. In the proposed optimization problem, parameters $w_{1}$ and $w_{2}$ are the weights defining the trade-off between the longer lifetime and shorter path where $w_{1}+w_{2}=1$, $0<w_{1}\leq 1$, and $0\leq w_{2}\leq 1$. The higher value of these parameters leads to their higher impact on the optimization. The weights $w_{1}$ and $w_{2}$ are network setting parameters affected by many parameters, including but not limited to, the network area, network density, transmission range, and network load. In this optimization problem, variable $T$ represents the inverse of path lifetime, Constraints (8) and (8) guarantee that the source node has one outgoing edge and no ingoing edge, Similarly, Constraints (8) and (8) guarantee that the destination node has one ingoing edge and no outgoing. Constraint (8) guarantees that every vertex that has an ingoing edge has to have an outgoing edge, except for the source and the destination nodes. Constraint (8) is the main constraint that maximizes path lifetime. In the rest of this section, we describe how to find the solution to the proposed Boolean LP problem and how to form the matrix $\mathcal{T}$.

Optimization problem solution: The defined optimization problem is a Boolean LP (BLP), which is well-known to be an NP-complete problem [13]. However, it is a special BLP case, where the following proposed algorithmic method can find its solution, i.e. the optimized path.

Assuming that we have a precise link lifetime prediction, we first sort the matrix of edge lifetimes in descending order. We then perform a breadth-first search (BFS) in the graph $G(V,E)$ to find the shortest path, without considering the link lifetimes. Let us refer to the shortest path as $p_{0}$. We then calculate the value of the objective function for the shortest path. Considering the link with the shortest link lifetime in path $p_{0}$ as $e_{(i^{\prime},j^{\prime})}$, we remove all the links with the lifetime lower or equal to the $\tau_{(i^{\prime},j^{\prime})}$. We then perform a BFS again, on the new graph and calculate the objective value for the new path. If the new objective value is less than the previous one, we replace the previous path with the new one and remove the edges with the lowest lifetime. We repeat this procedure until the BFS algorithm fails in finding a new path. We show in Lemma (1) that the output of this algorithm is the path with the optimized objective function. We further show that the computational complexity of this algorithm is on the order $O(|E||V|+|E|^{2})$, in Lemma (2).

It is worthy to mention that since in UAV networks usually $|E|>|V|$, the complexity of this algorithm could be considered as $O(|E|^{2})$. Furthermore, although we proved that the worst-case complexity is $O(|E||V|+|E|^{2})$, in practice the average-case complexity is much lower than the worst case, due to removing a large number of edges at the first iteration.

Link lifetime prediction: While OPAR can generally work with any link lifetime prediction algorithm, we utilize three-dimensional geometry to predict the link lifetime by knowing the UAV nodes’ positions. We then form a $n\times n$ matrix $\mathcal{T}$ which contains the LLT prediction for each link $e_{(i,j)}$, i.e. $\tau_{(i,j)}$. Considering a three-dimensional sphere, the position of node $i$ at time $t_{0}$ is defined by the tuple $p_{i}(t_{0})=(x_{i},y_{i},z_{i})_{t_{0}}$. Accordingly, the direction of each node in a three-dimensional sphere is defined by two angles azimuthal $\alpha$ and polar $\theta$. Having two consecutive positions of the same UAV node, $p_{i}(t_{1})$ and $p_{i}(t_{2})$, these angles could be calculated by Equation (9). To calculate the velocity of node $i$ having its position in two consecutive times $t_{1}$ and $t_{2}$, Equation (10) has to be used.

To consider the acceleration of the node, we need three consecutive positions of the nodes, to calculate node speed in two consecutive times, i.e. $v_{i}(t_{1})$ and $v_{i}(t_{2})$, using Equation (10). Thereby, the acceleration could be easily calculated using equation (11). Accordingly, to calculate the new node position after time $\Delta t$, equation (12) could be used.

The euclidean distance between UAV $i$ and UAV $j$ at time $t_{2}+\Delta t$ could be calculated using Equation (13). Let us assume, without loss of generality, the transmission range of all UAV nodes is the constant $R$. For each pair of nodes, if the distance is greater than $R$, we consider the LLT equal to zero. Now, our goal is to find the value of the maximum $(\tau_{(i,j)}=\Delta t)$ that keeps the $d_{(i,j)}(t_{2}+\Delta t)$ less than $R$ for all the remaining links. Hence, we have to find the maximum positive root of Equation (14). The positions of nodes $i$ and $j$ in this equation for the time $(t_{2}+\Delta t)$ could be calculated using Equation (12). In Equation (14), all the values except $\Delta t$ are known. This equation has two roots, a positive and a negative root. Any low complexity numerical methods such as the Bisection method could be used to find the positive root.

To show the superiority of OPAR, we evaluate its performance and compare it with three well-known routing protocols, AODV, OLSR, and DSDV. We use a wide range of routing protocols, including both distance vector and link-state techniques, as well as reactive and proactive protocols to show the superiority of OPAR in comparison with different routing protocols. We use network simulator ns-3 to implement OPAR and make the comparison. We measure flow success rate, routing traffic overhead, network throughput, and flow completion time (FCT) as performance evaluation metrics. The UAV nodes move randomly according to the 3D random waypoint (RWP) model, as well as the 3D Gauss-Markov (G-M) model. While RWP generates completely random movements in the area, the Gauss-Markov is a memory-based model and prevents the UAV from significantly changing its angle of movement. Table (I) represents the summary of simulation setting.

In each communication flow, a file of $5$ $MB$ is sent from the source UAV to the destination. We simulate each instance for 500 seconds and consider the flow status as a failure if the network fails at delivering the total file at the given simulation time. Each simulation instance has been simulated 10 times, with different randomized seed, and the average values of the results are reported. In the OPAR algorithm, each UAV records its own location every 0.3 sec and sends the three consequent locations via a message to the ground station.

We first analyze the OPAR performance for different network loads and densities by varying the path length-weight, i.e. $w_{1}$. The aim is to find the effect of path length versus the effect of path lifetime in different loads and densities. Fig. (1) shows the network throughput for a different number of flows and different number of UAVs. For better representation, we show the results only for a network with one, five, and ten concurrent flows and for the network with 50, 75, and 100 UAV nodes. Network throughput is calculated as the ratio of successful delivery over the network bandwidth over time and measured in Mbps. It is worth mentioning that if there does not exist a path between the source and the destination nodes, the source node stops sending. As an instance, in a network with ten concurrent flows, if two of the destination nodes are physically unreachable, the corresponding source nodes stop sending their packets which leads to mistakenly reporting the throughput for the network with eight flows, instead of the network with ten concurrent flows. To report fair throughput results, the throughput has to be considered in accordance with the flow failure rate. Hereupon, we weighted the throughput with the corresponding failure rate.

As Fig. (1a) shows, in the simulated settings, $w_{1}=0.6$ for the network with the lowest load leads to the highest throughput. This value of $w_{1}$ for the network with the highest load is between 0.8 and 0.9. Fig. (1b) shows that in the dense network, the weight close to one shows the highest throughput where this value for the network with medium density and low density is around 0.5 and 0.7, respectively. As it is clear, the optimal point between the path length weight and the path lifetime differs based on the network setting. However, the shortest path, in most cases, is not the ideal solution.

Next, we investigate the effect of varying the path length-weight on the FCT, in a network with different loads and different densities. We measure this metric in seconds and calculate it as the average FCT of flows in each simulation scenario. We consider the simulation time, i.e., 500 sec, as the lower bound for the flows which failed to deliver their files in the simulation time. Fig. (2) shows the results. In accordance with the results of Fig. (1), for the network with each specific load and specific density, a certain value of the path length-weight leads to the highest performance. By comparing Fig. (2) with Fig. (1), we find that, in most cases, the same values for the path length-weight that lead to higher throughput, also lead to lower FCT and consequently better overall performance. While not shown here, the OPAR success rate is not affected seriously by increasing the load and the density of the network, which shows its stability and reliability.

Now, we compare the performance of OPAR with that of AODV, OLSR, and DSDV for both RWP and G-M mobility models. Fig. (3) compares the results of the flow success rate. We note that the overhead of conventional routing algorithms prevents them from successfully delivering their files, in highly dynamic networks. As Fig. (3) shows, the flow success rate of OPAR is on average $30\%$ higher than that of AODV and much higher than other routing protocols. This figure shows that the flow success rate decreases slightly by increasing the network load and network density. It also shows that the flow success rate in the scenarios under the RWP mobility model is higher than that of G-M. The main reason is that the randomness of the RWP model increases the chance of connectivity.

Fig. (4) shows the routing traffic in MB generated by different routing algorithms. For OPAR, since the routing operation is performed by the ground station, and the communication of UAVs with the ground station is on a channel other than the UAVs communicating channel, it might not be fair to compare its routing overhead with that of conventional routing algorithms. However, it is worth noting that the average OPAR routing overhead is only $0.83$ MB for a network with 50 UAVs which is less than $10\%$ of AODV routing overhead. This figure shows that OLSR has the highest routing traffic overhead, where AODV shows a better performance than DSDV. It shows that by increasing the network load, the routing traffic overhead increases slightly. However, increasing the number of nodes increases the routing traffic exponentially, even for a moderate network load. In this figure, we see how much the highly dynamic nature of the network plays a role in the dramatic increment of routing overhead, especially for OLSR. Furthermore, the routing traffic generated by conventional routing algorithms in the scenarios under the RWP mobility model is significantly less than that of G-M, owing to the higher network connectivity under RWP mobility.

Fig. (5) shows the comparison of network throughput for different network loads and densities. As it is shown in Fig. (5), on average, OPAR gains $25\%$ higher throughput in comparison with AODV, which outperforms DSDV and OLSR. This Figure shows that the increment in network load affects the throughput negatively due to a higher congestion rate. It further shows that the increment in the number of nodes degrades the throughput of the network. We observed that this performance degradation has two main reasons. First, by increasing the density of the network, the routing traffic of conventional routing algorithms increases dramatically. Second, by increasing the network density some paths with longer lengths are appeared and considered for data transfer. The longer paths generally increase congestion and lead to performance degradation. Comparing Fig. (5a) with Fig. (5b) and also Fig. (5c) with Fig. (5d), we can conclude that using longer paths has more of a negative effect than that of routing overhead. In the presence of the G-M model, the routing overhead is less than that of RWP which is supposed to improve the throughput. However, in the same case, some longer paths are used due to the lower connectivity in the network which degrades the throughput. We see that the throughput of the network under the G-M mobility model is lower than that of RWP. However, OPAR shows stable throughput for both G-M and RWP models.

Finally, we show the results of FCT in Fig. (6). This figure shows that OPAR needs $15\%$ less time, on average, in comparison with AODV, and around $50\%$ less in comparison with DSDV and OLSR. While the increase in the network load does not show a significant increase in FCT, increasing the network density significantly increases the FCT. The negative effect of using the G-M model is also obvious where the number of concurrent flows is increased which arises from the increment in the number of failed flows in the G-M model.

The high dynamicity of FANETs, along with their other specific characteristics, leads to the incompetence of the conventional routing algorithms. While we showed that the routing traffic overhead of such algorithms could be even higher than the transferred data in highly dynamic networks, they are very likely to fail in delivering the flow of data. To face this shortcoming, we proposed OPAR, an optimized predictive and adaptive routing solution that optimizes the network performance by considering the path lifetime and the path length. We exhaustively evaluated the network’s performance using RWP and G-M mobility models for different loads and densities. All the combinations show the superiority of OPAR for the measured flow success rate, throughput, and flow completion time. As the future directions, we aim at adding the load balancing module to the proposed OPAR and develop the fully distributed version of the algorithm.

This material is in part based upon work funded by AFRL Grant #FA8750-20-1-1000. Any opinions, findings and conclusions or recommendations expressed in this material are those of the author(s) and do not necessarily reflect the views of the US government or AFRL.