PAR: A Power-Aware Routing Algorithm for UAV Networks

Abstract

Unmanned Aerial Vehicles (UAVs) have been widely used in both military and civilian scenarios since they are low in cost and flexible in use. They can adapt to a wide variety of dangerous scenarios and complete many tasks the Manned Aerial Vehicles (MAVs) can not undertake. In order to establish connectivity and collect data in large areas, numerous UAVs often cooperate with each other and set up a UAV wireless network. Many multi-hop routing protocols have been proposed to efficiently deliver messages with high delivery ratio and low energy consumption. However, most of them do not consider that the power level of UAVs is adjustable. In this paper, we propose a Power-Aware Routing (PAR) algorithm for UAV networks. PAR utilizes the pre-planned trajectory information of UAVs to compute the encounters at different power levels, and then constructs a power-aware encounter tree to calculate the transmission path with minimum energy consumption from the source to the destination within the delay constraint. Through extensive simulations, we demonstrate that compared with three classic algorithms, PAR significantly reduces the energy consumption and improves the network performance on the basis of ensuring timely delivery of packets.

1 Introduction

In recent years, with the development of sensors, navigation systems and wireless communication technologies, Unmanned Aerial Vehicle (UAV) networks achieve significant performance improvements and have been widely used in both military and civilian scenarios, such as battlefield surveillance, disaster response, farmland monitoring, etc. Due to the agility, versatility, ease of installation and simplicity of operation, UAVs can adapt to a wide variety of dangerous scenarios and complete many tasks that Manned Aerial Vehicles (MAVs) can not undertake.

To establish connectivity in large areas, a great number of UAVs cooperate with each other in the form of clusters and establish a multi-hop UAV network. Compared with single-hop UAV networks, multi-hop UAV networks can cover a wider range and undertake more complex tasks. Meanwhile, multi-hop UAV networks have many other advantages, such as low cost, low mission completion time, better survivability and better scalability. Many multi-hop routing protocols in UAV networks [10] are proposed to efficiently deliver messages to the destination, which have become a research hotspot in recent years.

Due to the unique characteristics of UAV networks, such as high mobility, sparse distribution, intermittent connectivity and unstable link quality, multi-hop routing in UAV networks faces many challenges, such as low delivery ratio, high delay and expensive energy consumption. In order to address these issues, a mechanism called store-carry-forward (SCF) [1] has been proposed to improve the delivery ratio of packets. With the SCF mechanism, if there is a suitable forwarding node within the communication range, the current message-holder UAV will forward the packet to this forwarding node, otherwise it will store and carry the packet until it encounters a suitable forwarding UAV.

Many routing protocols [1, 8] have been proposed on the basis of the SCF mechanism. However, most of them focus on improving the delivery ratio, but ignoring the delivery delay and energy consumption. In many time-sensitive or delay-constrained applications for UAV networks, such as forest surveillance, disaster rescue and battlefield networks, messages need to be delivered in time, otherwise, their values will be greatly reduced or even invalid. Meanwhile, UAVs are energy-constrained and required to work for a long time. Therefore, routing protocols for UAV networks need to reduce the energy consumption on the basis of ensuring the timely delivery of messages.

Energy-efficient routing has attracted considerable attention and many methods have been proposed to minimize the total energy consumption. However, most of them [4] assume that the power level of UAVs is fixed. In fact, the transmission power of many UAVs is now adjustable [2, 12], and the performance of existing routing protocols is inefficient because they do not utilize the power-adjustable characteristic of UAVs to optimize routing.

Meanwhile, in many military and civilian application scenarios for UAV networks, the trajectories of UAVs are pre-planned and can be obtained in advance through mission planning and path planning [3, 7]. Furthermore, if trajectories of UAVs need to be dynamically adjusted, the ground station can broadcast the updated global trajectory information through the out-of-band channel to ensure that all UAVs have the latest global trajectory information [9, 12]. We can use this pre-planned trajectory information to reduce the energy consumption and ensure the delivery delay.

Therefore, in this paper, we design a Power-Aware Routing (PAR) algorithm for UAV networks which takes the delivery ratio, energy consumption and delay constraint into consideration. The main idea of PAR is to utilize the power-adjustable characteristic and pre-planned trajectory information of UAVs to optimize routing protocols. First, PAR utilizes the pre-planned trajectory information to compute encounters between UAVs at different power levels. Then, a power-aware encounter tree (PET) is constructed according to the encounter information, based on which PAR can calculate an efficient transmission path with minimum energy consumption within the delay constraint. It is worth noting that, in PAR, each UAV selects the appropriate power level for each packet transmission dynamically and individually. The main contributions of this paper are twofold:

• A power-aware routing algorithm for UAV networks called PAR is proposed to find the efficient transmission path with minimum energy consumption within the delay constraint. Different from existing routing protocols using a fix-power model, for each packet transmission, PAR dynamically selects an appropriate power level for each UAV to reduce the energy consumption on the basis of ensuring timely delivery of the packet.

• Extensive simulations are conducted by using the Opportunistic Network Environment (ONE) simulator [6]. The results show the superior performance of PAR compared to three classic algorithms in terms of the delivery ratio, energy consumption and overhead ratio.

The reminder of the paper is organized as follows. Section 2 summarizes state-of-art on routing protocols in mobile ad-hoc networks (MANETs). In Sect. 3, we describe the problem formulation. Then, in Sect. 4, the design of PAR is provided in detail. Finally, we provide the performance evaluation of PAR through extensive simulations in Sect. 5, and conclude this paper in Sect. 6.

2 Related Work

In this section, we introduce the latest progress of related work. There is a considerable research effort for the development of routing protocols in MANETs, which can be divided into topology-based or geographic routing protocols.

Topology-based routing protocols rely on the current network topology, based on which routing-related information can be obtained and utilized for message forwarding. The authors in [13] propose a new neighbor discovery mechanism and a social network-based relay selection scheme to help make routing decisions. The authors in [5] combine the blockchain with traditional Optimized Link State Routing Protocol to encourage cooperation between nodes. Moreover, a relay selection game model is improved and further applied to select the appropriate relay node. However, the high mobility of nodes and high dynamic of topology in UAV networks make the current topology information out of date frequently and quickly, thereby making the routing inefficient or even unavailable.

Geographic routing protocols exploit local location information instead of global topology information to route data. The pure idea is to forward packets to the neighbor node nearest to the destination. The authors in [4] adaptively utilize the location information and the characteristics of energy consumption to make routing decisions for better route recovery from routing holes. The authors in [8] further consider the transmission direction of data packets while using geographic location information to improve the routing efficiency in similar strip networks. However, due to the sparse distribution of nodes and intermittent connectivity of communications, pure geographic routing protocols are not enough to cope with UAV networks.

In order to address the above challenges, a promising approach called store-carry-forward mechanism is proposed and widely used due to its simplicity and effectiveness. In [2], the minimum energy routing problem is converted into a directed Steiner tree problem and then map the computed tree back into a transmission scheme. Meanwhile, the authors in [1] further take the prediction of trajectory and the load of UAVs into consideration to optimize data packet forwarding. However, due to the highly dynamic nature of UAV networks, geographic routing protocols inevitably falls into local optimum.

3 Problem Formulation

The application scenarios we consider in this paper are search and rescue missions. Many UAVs search in an area and will send messages as needed. Without loss of generality, we abstract the three-dimensional space into a Euclidean space ignoring the vertical space [2]. The ground station calculates the trajectories of UAVs in advance according to the path planning algorithm [7, 9, 10].

The UAV network model can be denoted as a weighted directed graph $G = (V, E, P)$ where $V = \{u_1, u_2, \dots , u_N\}$ stands for the N nodes, each node represents a UAV or a ground station. Each node has L adjustable power levels, $P = \{p_1, p_2, \dots , p_k, \dots , p_L\}$, and $E = \{e_1, e_2, \dots , e_G\}\subseteq V \times V$ denotes the edge set. Time is divided into discrete T time slots and nodes remain static within a time slot [2]. An edge $e = (u_i, u_j, t, p_k)$, where $1 \le i,j \le N , 0 \le t \le T, 1 \le k \le L$ and $i \ne j$, means that $u_i$ will encounter $u_j$ and $u_i$ can communicate with $u_j$ with the power level $p_k$ in the time slot t. Moreover, the energy consumption that $u_i$ transmits a packet m to $u_j$ with the power level $p_k$ is denoted as $E_{e}(p_k)$.

Given a UAV network, every time a real-time message m is generated, it will be associated with a delay constraint T based on its urgency. Taking the power-adjustable characteristic of UAVs into consideration, the objective of this paper is to find an efficient transmission path with minimum energy consumption while satisfying the delay constraint for each message.

4 Power-Aware Routing Algorithm

4.1 Basic Idea

Our basic idea is to utilize the power-adjustable characteristic and pre-planned trajectory information of UAVs to optimize routing in UAV networks. First, the pre-planned trajectory information is used to predict encounters at different power levels between UAVs. As depicted in Fig. 1, there are five UAVs $u_1, u_2, u_3, u_4, u_5$ and a ground station $g_0$. UAVs are flying along with their pre-planned trajectories and collecting data. We assume that each UAV has two different power levels (i.e., $p_1$ and $p_2$), and Fig. 1 shows the encounters between UAVs at different power levels (i.e., $e_i$ and $c_i$). For ease of differentiation, we abstract encounters at the power level $p_1$ as points [9]. For instance, at position $e_1$, UAV $u_1$ and $u_2$ encounter at 10s with the power level $p_1$. Moreover, at position $c_1$, UAV $u_2$ and $u_3$ encounter at 25s with the power level $p_2$; at position $c_2$, UAV $u_2$ and $u_5$ encounter at 25s with the power level $p_2$; at position $c_3$, UAV $u_5$ and $u_2$ encounter at 45s with the power level $p_2$.

Then, for the message that need to be delivered, we construct a power-aware encounter tree (see in Sect. 4.2) according to the encounter information of UAVs. Based on the power-aware encounter tree, we can find the efficient transmission path with minimum energy consumption within the delay constraint for the message. In PAR, each UAV can select the appropriate power level for each packet transmission dynamically and individually according to its respective encounter situation.

Fig. 1.

An example of encounters between UAVs when UAVs have two power levels.

For example, in Fig. 1, a data packet m with a delay constraint T is generated by UAV $u_1$ at 0s, and $u_1$ wants to send m to the ground station $g_0$. For convenience, in this paper, we use a sublinear energy model in [11], that is $2E_{e}(p_{1}) > E_{e}(p_{2})$. It is worth nothing that PAR is not restricted by a specific energy model. According to the pre-planned trajectory information and encounter information, we can deduce that there are at least three transmission paths:

• 1. $pa_1: u_1 \xrightarrow {e_2} u_3 \xrightarrow {e_4} g_0$. The transmission path is $(u_1,u_3,5s,p_1)$, $(u_3,g_0,60s,p_1)$. The delivery time of m along this path is 60s and the energy consumption is $2E_{e}(p_1)$.

• 2. $pa_2: u_1 \xrightarrow {e_1} u_2 \xrightarrow {e_3} u_4 \xrightarrow {e_5} u_5 \xrightarrow {e_6} g_0$. The transmission path is $(u_1,u_2,10s,p_1)$, $(u_2,u_4,25s,p_1)$, $(u_4,u_5,35s,p_1)$, $(u_5,g_0,45s,p_1)$. The delivery time of m along this path is 45s and the energy consumption is $4E_{e}(p_1)$.

• 3. $pa_3: u_1 \xrightarrow {e_1} u_2 \xrightarrow {c_2} u_5 \xrightarrow {e_6} g_0$. The transmission path is $(u_1,u_2,10s,p_1)$, $(u_2,u_5,25s,p_2)$, $(u_5,g_0,45s,p_1)$. The delivery time of m along this path is 45s and the energy consumption is $2E_{e}(p_1) + E_{e}(p_2)$.

When the delay constraint T $\ge$ 60s, all three transmission paths mentioned above can deliver the message m in time, but the first transmission path $pa_1$ is the best choice, since it has the least energy consumption while ensuring the timely delivery of m. However, when 45s $\le$ T < 60s, $pa_1$ can not satisfy the requirement because the delivery time along it is 60s which exceeds the delay constraint. In this situation, if we do not consider the power-adjustable characteristic of UAVs, the suitable transmission path will be $pa_2$, the delivery time of m along $pa_2$ is 45s and the energy consumption is $4E_{e}(p_1)$. On the contrary, if we take the adjustable power levels into consideration, we can find out a better transmission path, that is, $pa_3$. The delivery time of m along this path is also 45s. Both $pa_2$ and $pa_3$ can ensure the timely delivery of m, however, the energy consumption of $pa_3$ is $2E_{e}(p_1)+E_{e}(p_2)$, which is less than that of $pa_2$ which does not consider the adjustable power level.

4.2 Power-aware Encounter Tree Construction

In order to find an efficient transmission path with minimum energy consumption within the delay constraint for the packet m, we propose a power-aware encounter tree (PET) based on the encounter information of UAVs at different power levels within the delay constraint. Before describing the construction procedure of PET, we first introduce some basic definitions and terms of PET:

• PET is a directed tree that originates from the source node s that sends m to the destination node d.

• For a node n in PET, it represents a UAV or a ground station in the network. Each node can appear repeatedly in PET.

• Each edge e between nodes in PET is a directed edge, which represents an encounter between the two parties. The direction of the edge indicates the direction of the packet transmission. Each encounter can only be added to PET once.

• The child nodes of n are the nodes which n will encounter at different power levels after encountering its parent node within the delay constraint. For the same node that encounters at different power levels, we regard it as different child nodes. The child nodes of n are denoted as $n.C = \bigcup _{k=1}^{L} N(n, n.t, T, p_k)$, where n.t indicates the encounter time between n and its parent node, T represents the delay constraint of m, and $N(n, n.t, T, p_k)$ represents the nodes that n will encounter between n.t and T with the power level $p_k$.

• For each child node of n, denoted as $c \in n.C$, and its encounter $e_c$ with n, represented as $(n, c, c.t, p_k)$, the transmission path from the source node s to c consists of the transmission path from s to n and the transmission path from n to c, denoted as $c.pa = n.pa \rightarrow (n, c, c.t, p_k)$.

• The total energy consumption to transmit m from s to c along c.pa is denoted as $E_{t}(c.pa)$, and $E_{t}(c.pa) = E_{t}(n.pa) +E_{e}(p_k)$, where $E_{e}(p_k)$ indicates the energy consumption that the node n transmits m to its child node c with the power level $p_k$.

• PET only contains the source node s when it is initialized. For the source node s, $s.t = 0, E_{t}(s.pa) = 0$.

Then, we describe the construction procedure of a power-aware encounter tree. The construction of PET is a process of expanding the tree by adding new pairs of nodes and edges into it one by one until a transmission path that satisfies the requirements is found. Each pair of added node n and edge $e_n$ is associated with an energy consumption metric (ECM) and encounter time (ET), where $ECM = E_{t}(n.pa)$ and $ET = n.t$. We use a priority queue (PQ) to assist the insertion of nodes and edges in PET. When each node is added into PQ, its parent node and the encounter (i.e., the associated edge) have been determined. Nodes with their edges are sorted by the associated ECM and ET to ensure that the head node in PQ has the smallest ECM. Meanwhile, in order to ensure the uniqueness of the encounters in PET, we use a bitmap V to mark whether an encounter has been added to PET. The algorithm is expressed as follows:

• 1. Insert the message source UAV into PQ; all the elements of V are initialized with 0, indicating that all encounters have not been added into PET yet.

• 2. If PQ is empty, the construction process of PET is done; otherwise, take out the first node (denoted as u) from PQ. If u is the source UAV, go to Step 4; otherwise, get the encounter $e_u$ between u and its parent node, and then go to Step 3. Note that u is the node with the smallest ECM.

• 3. If $e_u$ has been added into PET before (i.e., $V[e_u] = 1$), discard it and go to Step 2; otherwise go to Step 4.

• 4. Based on the pre-planned trajectory information, calculate the child nodes of u (i.e., u.C). Note that the child nodes of u are the UAVs that u will encounter at different power levels (i.e., from $p_1$ to $p_L$) within the delay constraint T after encountering its parent node (i.e., between u.t and T).

• 5. For each child node c of u (i.e., $c \in u.C$), compute its ECM and ET based on the encounter $e_c$ between u and c. If $e_c$ has been added to PET, then discard it; otherwise, node c along with $e_c$ is added to PQ. The priority queue PQ can ensure that the ECM of the head node is the smallest.

• 6. If u is the source node, it will be the root node of PET; otherwise, add u into PET by inserting it into its parent’s corresponding child-list as a child node. The edge represents the encounter between u and its parent node (i.e., $e_u$). Then, set the corresponding bitmap element $V[e_u]$ to 1, indicating that encounter $e_u$ has been added into PET.

• 7. If the destination node d is added into PET, the construction process of PET will be done, which means a qualified transmission path is found; otherwise, go to Step 2.

After describing the main stages of the construction of the power-aware encounter tree, we summarize PAR in Algorithm 1.

4.3 Proof of Optimality

In this section, we provide a theoretical proof of the optimality of PAR.

Theorem 1

When the destination node d is added into PET for the first time, its associated transmission path (i.e., d.pa) will be the transmission path with minimum energy consumption while satisfying the delay constraint.

Proof

We suppose that there is another transmission path $d.pa_1$, which consumes less energy than d.pa (i.e., $E_{t}(d.{pa_1}) < E_{t}(d.{pa})$) while satisfying the delay constraint. There will be two cases:

• 1. $d.pa_1$ has been added to PET. It contradicts the condition that the destination node d is added into PET for the first time.

• 2. Part or all of $d.pa_1$ is still in PQ. We assume that the part of $d.pa_1$ in PQ is $u.{pa_1'}$, so $E_{t}(u.{pa_1'})< E_{t}(d.{pa_1}) < E_{t}(d.{pa})$. However, based on the rule of PAR, the ECM of the head node of PQ is the smallest. When d is taken out from PQ and added into PET, the ECM of its associated transmission path (i.e., d.pa) is the smallest, namely $E_{t}(d.{pa})< E_{t}(u.{pa_1'}) < E_{t}(d.{pa_1})$. Contradiction.

Therefore, there is no other transmission path with lower energy consumption, namely d.pa is the transmission path with minimum energy consumption while satisfying the delay constraint.

Based on the above analysis, we can prove that if there is a transmission path that satisfies the requirements, PAR can always find it. This ensures the correctness and optimality of PAR.

5 Performance Evaluation

In this section, we evaluate the performance of PAR along with three classic routing algorithms in [1]: $DTN_{geo}$, $DTN_{close}$ and $DTN_{load}$. $DTN_{geo}$ utilizes the current location and trajectory information for packet forwarding. Then on the basis of the $DTN_{geo}$ algorithm, $DTN_{close}$ further predicts the future location of UAVs, and $DTN_{load}$ considers the load of UAV networks to optimize routing. We implement them on the Opportunistic Network Environment (ONE) simulator [6] and extend the ONE simulator to support multiple power levels.

5.1 Simulation Setup and Scenarios

Referring to the simulation scenarios in [1, 9, 10], we design a power-adjustable simulation scenario inspired by search and rescue missions. In the scenario, one stationary ground station is placed together with nine search UAVs and four ferry UAVs. Each search UAV uses a typical search zigzag movement pattern to cover the mission region efficiently, and each ferry UAV moves back and forth along specified trajectory to assist search UAVs in transmitting packets. Table 1 summarizes the detailed experimental parameters. We use the following metrics to evaluate the performance of the packet forwarding algorithms:

• Delivery ratio. The fraction of messages that have been successfully delivered to the destination out of the messages that have been generated.

• Energy consumption. The average energy consumed by messages successfully delivered to their destinations.

• Overhead ratio. $Overhead = \tfrac{Sum_{relay} - Sum_{dely}}{Sum_{dely}}$, where $Sum_{relay}$ is the total times that all messages were forwarded, and $Sum_{dely}$ is the total number of messages that have been successfully delivered to the destination.

Table 1. Simulation settings

To avoid bias, we run each experiment with 10 rounds and calculate the average value as the final experimental result. In addition, for $DTN_{geo}$, $DTN_{close}$ and $DTN_{load}$, we run the simulation separately at each fixed power level and select the best simulation value as the final experimental result.

5.2 Analysis of Simulation Results

Impact of the Message Creation Rate. As shown in Fig. 2(a), PAR achieves the maximal delivery ratio and outperforms the three algorithms especially when the message creation rate becomes very high. This is because PAR utilizes the pre-planned trajectory information and power-adjustable characteristic of UAVs to calculate the transmission path in advance which improves the delivery ratio of data packets. Meanwhile, as depicted in Fig. 2(b), the energy consumption of PAR is much lower than $DTN_{geo}$ and $DTN_{load}$, but higher than $DTN_{close}$. However, $DTN_{close}$ is at the expense of the delivery ratio, while PAR firstly guarantees the timely delivery of messages, and then minimizes the energy consumption. PAR can improve the power level and increase the energy consumption to ensure the timely delivery of messages. For the overhead ratio, as Fig. 2(c) shows, PAR achieves the minimum overhead ratio and there is almost no fluctuation in PAR. This is because PAR calculates the transmission paths in advance, and then forwards the messages according to these calculated paths without redundant forwarding, thereby reducing the number of message forwarding.

Fig. 2.

The impact of the message creation rate on the delivery ratio, energy consumption and overhead ratio.

Impact of the UAV Speed. As depicted in Fig. 3(a), the delivery ratios of all algorithms increase with the increasing of the UAV speed. This is because with the increasing of the UAV speed, the current message holder can have more opportunities to choose a suitable forwarding node before the delay constraint expires due to more encounters in the same time window. The energy consumption of PAR is always lower than $DTN_{geo}$ and $DTN_{load}$, but higher than $DTN_{close}$ when the UAV speed is slower than 8m/s, as Fig. 3(b) shows. This is because PAR dynamically adjust the power of UAVs to find an efficient transmission path to the destination. On the contrary, $DTN_{close}$ does not guarantee the timely delivery of packets. When the delivery ratios of PAR and $DTN_{close}$ are the same, we can find that the energy consumption of PAR is much smaller than $DTN_{close}$. As shown in Fig. 3(c), the overhead ratios of all algorithms decrease with the increasing of the UAV speed, and PAR achieves the minimum overhead ratio.

Fig. 3.

The impact of the UAV speed on the delivery ratio, energy consumption and overhead ratio.

Impact of the Delay Constraint $\boldsymbol{T}$. As Fig. 3(a) and 3(b) shows, even when the delay constraint is small, PAR can still maintain a perfect delivery ratio. The reason is that PAR adjusts (i.e., increases) the power level to ensure the timely delivery of messages. Meanwhile, as the delay constraint tends to be relaxed, PAR gradually adjusts (i.e., decreases) the power level to minimize the energy consumption. For the overhead ratio, as depicted in Fig. 3(c), PAR achieves the minimum overhead ratio, and as the delay constraint increases, the overhead ratio of PAR gradually decreases. This is because PAR always chooses the transmission path with minimum energy consumption within the delay constraint (Fig. 4).

Fig. 4.

The impact of the delivery constraint on the delivery ratio, energy consumption and overhead ratio.

6 Conclusion

In this paper, we propose an efficient Power-Aware Routing (PAR) algorithm for UAV networks. PAR takes the adjustable power into consideration. Based on the pre-planned trajectory information of UAVs, PAR computes encounters between UAVs at different power levels and constructs a power-aware encounter tree to find an efficient transmission path. Then according to the found transmission path, it selects the appropriate power level for each forwarding UAV to minimize the energy consumption and ensure timely delivery of the packet. The simulation results show that PAR significantly improves the network performance and has a better delivery ratio, energy consumption and overhead ratio than three classic algorithms.