Data Routing in UAV Networks with Multiple Data Sources Using Steiner Tree

Abstract

Unmanned Aerial Vehicles (UAVs) have a plethora of applications in extreme time-sensitive use cases by forming an advantageous structure with low-power devices. In time-sensitive cases, effective communication plays an important role in low-power devices. It is challenging to design a communication protocol if the node poses mobility. In this paper, we propose an energy-efficient communication protocol for data transfer from multiple sources via mobile relay nodes. The paper proposes the use of mobility vector information, such as the location of the nodes, speed, and direction along with the communication range to route the data to the next hop. Once the gateway node detects the presence of multiple sources, a Steiner tree algorithm is used to calculate the best routing path connecting multiple sources to the gateway node via the mobile relay nodes. The proposed algorithm guarantees that the number of nodes participating in routing is minimal and is capable of dynamically selecting the neighboring nodes with respect to the varying topology. The simulation results show that the proposed approach is better in terms of packet delivery ratio and energy efficiency.

1 Introduction

UAVs’ mobility can be based on external stimuli like a dynamic environment or in a controlled manner. Energy-limited UAVs’ have to be very efficient in making the decision for relocation for better communication. In controlled mobility, a node can easily relocate to improve network efficiency. But in the scenario where the UAVs which are enrolled in executing an ongoing application, the node would not have a say in the mobility like maneuvering in a small confined place. For example, a scenario where a swarm of UAVs performs a search operation while a different UAV network can make use of the swarm nodes to relay the data from the source to a gateway node [10].

As an initial step in developing communication protocols with UAV based mobile relays in the networks, we considered a scenario of multi UAVs with the gateway node (ground station) being static while all other nodes (UAVs) are mobile. There are multiple sources present in the network and the mobility of the relay nodes is assumed to be random. The aim is to develop an energy-efficient routing protocol, by considering the multiple sources, so as to calculate the best routing path (with the minimum number of nodes participating in data communication). Since the network topology is dynamic, the probability that the same node participates in routing for a prolonged period of time will be less and hence the network lifetime is extended. The paper proposes to use a Steiner tree algorithm which guarantees that the number of nodes participating in the data communication is less when compared to each source communicating the data directly to the gateway node.

Section 2 brief the background of existing architecture and different routing protocol available. The proposed approach with algorithms is explained in Sect. 3. Implementation details with the results are given in Sect. 4 and Sect. 5 concludes the paper.

2 Background

Deploying a large number of UAVs includes challenges such as building efficient communication protocols and ensuring collision-free and seamless operations [9]. To achieve seamless cooperation and collaboration between UAVs, inter-UAV communication becomes necessary [8]. The most common single Pilot in Command (PIC) application includes a pilot operating a single UAV. Multi-path UAV systems may also include single PIC operations where multiple UAVs may link to each other in addition to the ground station. In Flying Ad-hoc Networks (FANET), the communication between UAVs is called UAV-to-UAV (U2U) link whereas the communication with UAV to the ground station is UAV-to-Infrastructure (U2I) U2G link respectively.

The dynamic topology of UAV networks makes it challenging to build a routing protocol. The uneven distribution of the node along with the mobility makes it more difficult to have a long-term multi-hop routing in FANET. Due to these factors, the communication protocols built for Mobile Ad hoc Networks (MANET) and Vehicle Ad hoc Networks (VANET) cannot be directly adapted. The design of the communication protocol has to be made based on the frequent topology changes owing to their high mobility [3].

Localization is one critical aspect in designing communication protocol. The network topology is determined by the accuracy of the UAV location in the system estimate. For example, if the node mobility is high and the GPS sampling time is less, then this may degrade the performance of the communication protocol in use. The use of advanced Kalman filter [12] with the help of GPS and Inertial measurement units can help in improving the localization accuracy. The presence of electromagnetic radiation and multipath reception can degrade the performance of location estimation [6].

Different routing protocols applicable to UAV networks were proposed in various literature. Arafat, M.Y. and Moh, S. [2] classified this into position-based, topology-based, cluster-based, deterministic, stochastic, and social-network-based touting protocols. The node mobility model plays a major role in designing an efficient routing protocol. The mobility model depends on the type of application the UAV is used for. In the scenario where the UAV paths are predefined, the mobility model is regular. UAV’s such as Swarms or multi-UAV systems performing autonomous operations without a central control will come under the group mobility model. Random direction and Random way-point are the most commonly used, random mobility models. The efficiency of a wireless link depends on the mobility model. It is challenging to design a routing protocol with a random mobility model when compared with a deterministic mobility model. Routing protocol should be designed with the consideration of the mobility model to ensure end-to-end data delivery.

Few routing algorithms have been studied in the literature for this scenario, such as Greedy Perimeter Stateless Routing (GPSR) [5], and Receiver-based Opportunistic Forwarding Protocol (ROF) [7]. GPSR algorithm [5] consists of two methods to send a packet from the source to the destination. The first method, greedy forwarding, is when the node forwards it’s a packet to its’ geometrically closest neighbour node to the destination. When none of the node’s neighbors are closer to the destination than the node itself, then the second method, perimeter forwarding, is used, where the packet is forwarded to a node on its perimeter. Even though this causes the packet to move farther in geometric distance from the destination temporarily, it improves reachability, as the perimeter node could forward the packet to the destination, and so there is a greater chance of the packet reaching the destination.

Mobility Management UAV-based Grouping routing protocol (MMUG) [1] creates an optimal path based on path length, bandwidth, distance, and broadcast message in three phases. The first phase ground station transmits the sensed data to the UAV. In the second phase, the UAVs vehicle groups the nodes based on the coverage range of the Group Head (GH). The group node which is close to the ground station collects the location of all nodes and if any UAV moves away within the range of GH or comes in the range of GH, the information of those nodes will be updated to the group node. The routing Metric is calculated for the selection of optimal paths based on minimum bandwidth, minimum delay, and minimum path length and selected by prioritizing length, bandwidth, and delay in an ordered manner which reduces the control overhead and routing overhead. In phase three, the GH communicates with the ground base station.

ROF protocol [7] uses a dual-channel based forwarding mechanism to send a packet from the source to the destination. The sender broadcasts the data packet to all its neighbors, and the neighbor nodes contend for forwarding rights with two steps. First, the neighbors which are farther away from the sender eliminate themselves. Then, the remaining nodes contend for the forwarding right according to a certain mechanism, and whichever node wins, starts to forward the data packet. Re-transmitting happens in overstep mode if there are no nodes attending the forwarding right contention.

The paper proposes a routing protocol for a scenario where multiple UAVs are used to sense the environmental data such as streaming a video of a specific incident or capturing an acoustic signal from a location and hence communicating to a common gateway node with the help of other UAVs present in the communication range.

3 Proposed Approach

Problem Statement: The network is composed of K static nodes which are capable of capturing the environmental data, gateway nodes, and dense deployment of N UAV nodes. All nodes have a communication coverage of radius $R_c$. The multiple sources in the network have data to transmit to the gateway. The aim is to relay the data from multiple sources o the gateway node via the UAV nodes available. This need to be done by selecting the best possible path for forwarding the packets and thereby enhancing network efficiency. Figure 1 shows the scenario of a UAV network with multiple data sources and UAV nodes deployed.

Assumptions: We assume that the nodes deployed in the network know their location using GPS or a similar localization technique. Also, the location of the gateway node is known to all the nodes in the network. The paper also assumes to use of a wireless communication protocol Zigbee which uses a cross-layered architecture is used to establish communication in the UAV network. Since the end-to-end connection establishment is not possible due to the dynamic topology, an approach very similar to a disruption tolerance network (DTN) is considered for data transferring. This means the intermediate nodes are capable of storing the data and the forward the data once the next hop neighbor is identified.

The proposed approach is presented below. The protocol has three phases: i) Network Initialization, ii) Steiner Vertex calculation and iii) Data Communication.

3.1 Phase I: Network Initialization

Network initialization is the first phase and is executed after the network deployment. The aim of the network initialization phase is to transfer the data from a source node and the gateway node. First, the node which has data broadcasts a discovery packet, $P_{disc}$ containing its location information to all its neighbors. A node which receives the $P_{disc}$ packet will reply with a $P_{rep}$ packet. This is done after a small time interval $\rho _t$, after receiving the $P_{disc}$ packet. The value of $\rho _t$ is different for different nodes even though $P_{disc}$ packet is received at the same time. The value of $\rho _t$ is calculated based on two factors which are i) the location of the gateway node and ii) contact time ($\hat{t}$). Contact time is the time of contact with respect to the communication range and with the mobility vector information. The value of $\rho _t$ is lesser for a UAV relay neighbor whose contact time, $\hat{t}$ is maximum and also which lies Euclidean distance close to the gateway node.

Fig. 1.

Scenario: A multi UAV with multiple Sources

The calculation of $\hat{t}$ is given in Sect. 3.1. The varying $\rho _t$ is introduced in order to set high priority for a relay node which is in communication range of the sender for a longer time. The nodes whose location is between the source and the gateway nodes will have priority in communicating the data back to the gateway node.

$$ \rho _t \propto \frac{d_{(i,bs)}}{\hat{t}} $$

where $d_{(i,bs)}$ is the Euclidean distance between a node i and the gateway node. A node with a high value of $\hat{t}$ and with minimum Euclidean distance close to the gateway nodes will send $P_{rep}$ packet to the sender at the earliest. All neighbors that overhear the reply message refrain from sending a $P_{rep}$ message. The node from which the $P_{rep}$ is received first is treated as the immediate next hop for routing the data packet. The source continues to transmit the data for $\hat{t}$ units of time, which is the contact time for which the two nodes will remain within the transmission range of each other.

Contact Time Calculation. The contact time of the two mobile nodes $n_1$ and $n_2$ is the time for which the two nodes remain in transmission range r. Let $\overrightarrow{X_1(t)}$ is the position vector for node $n_1$. Similarly $\overrightarrow{X_2}(t)$ is the position vector of node $n_2$. The scenario is shown in Fig. 2.

Let $t_0$ be the instance from which the value $\hat{t}$ is to be calculated. Then,

$$|\overrightarrow{X_1}(t_0) - \overrightarrow{X_2}(t_0)|$$

is the distance between the nodes initially and this will be lesser than the transmission range r of the nodes. Let $t^{\prime }$ be the time when the nodes move beyond the communication range. That is

$$\begin{aligned} |\overrightarrow{X_1}(t^{\prime }) - \overrightarrow{X_2}(t^{\prime })| \end{aligned}$$

(1)

$$\begin{aligned} t^\prime = \min t \quad | \quad | \overrightarrow{X_1}(t) -\overrightarrow{X_1}(t) | >r \end{aligned}$$

(2)

Then, $t^\prime - t_0$ is the contact time $\hat{t}$, for nodes $n_1$ and $n_2$.

Fig. 2.

Scenario of two mobile nodes moving with velocity $v_1$, $v_2$

Thus, relative velocity $v_r$ of the two nodes is $\overrightarrow{v_r} = \overrightarrow{v_1}-\overrightarrow{v_2}$

From [11] the contact time $\hat{t}$ can be obtained using the equation

$$\begin{aligned} \hat{t} = \left( \frac{r-\sqrt{{(x_1 - x_2)^2} + {(y_1 - y_2)^2}}}{\sqrt{(v_1\cos \theta _1 - v_2\cos \theta _2)^2+(v_1\sin \theta _1 - v_2\sin \theta _2)^2}}\right) \end{aligned}$$

(3)

where $(x_1,y_1)$ and $(x_2,y_2)$ are the coordinate of $n_1$ and $n_2$ respectively. The relay nodes also forward it in the same way till the packet reaches the gateway node. When the gateway node receives the initial packets containing the locations from all of the source nodes, it moves to the next phase.

3.2 Phase II: Steiner Vertex Calculation

Phase II is initiated by the gateway node when it starts receiving data from the source node. When the gateway node receives data from more than one source node, it locally calculates the Steiner vertex set, $\mathbb {V}_{st}$. For Steiner set calculation, the location of the source node and the gateway node is used as input.

Steiner Vertex Set Calculation. The set of source nodes is defined as:

$$\begin{aligned} S = \{ S_0, S_1, ..., S_{n-1} \} \end{aligned}$$

(4)

Since there is only one gateway node (BS) to which the data finally needs to be transferred, the cumulative set of all vertices used for the Steiner point calculation is defined as $\mathbb {V}$, where $|\mathbb {V}|=n$.

$$\begin{aligned} \mathbb {V} = S \cup \{BS\} \end{aligned}$$

(5)

The gateway node then calculates the $n-2$ Steiner points according to a modified version of the iterative I approach [4]. The aim is to find a near-optimal value of the Steiner vertex set $\mathbb {V}_{st}$. To do this, a virtual area A is created, which contains all points in $\mathbb {V}$, and then consider a mesh with vertical and horizontal lines, each separated by a distance $\gamma$. A helper function $\Delta MST(V,v)$ is defined as:

$$\begin{aligned} \Delta MST(V,v) = c(MST(V)) - c(MST(V \cup \{v\})) \end{aligned}$$

(6)

In the Eq. 6, MST(V) represents the Minimum Spanning Tree for the set of vertices V, and c(T) represents the sum of all edges of the tree T, where each edge is the distance between the two points it connects.

$\mathbb {C}$ is the candidate set containing all intersection points on the mesh. The aim is to find an element $v \in \mathbb {C}$ such that $\Delta MST(\mathbb {V} \cup \mathbb {V}_{st}, v)$ is maximized.

Initially, a large value of $\gamma$ is chosen for the candidate set $\mathbb {C}$, and once the element $v = (p, q)$ is identified, the process is repeated for a smaller value of $\gamma ^\prime$ for a smaller area $A^\prime$. The area $A^\prime$ is the area between the coordinates $(p-\gamma , q-\gamma )$ and $(p+\gamma , q+\gamma )$. Again, from the candidate set $C^\prime$, a value $v^\prime$ is chosen such that it maximizes Eq. 6. The Steiner vertex set is updated as $\mathbb {V}_{st} = \mathbb {V}_{st} \cup \{v\}$, and the entire procedure is repeated $n-2$ times. The Steiner node calculation is shown in Algorithm 1.

After calculating the Steiner vertex set, the gateway node creates a packet containing all the Steiner vertices and forwards it to all the source nodes. When a source node receives a list of the Steiner points from the gateway node, it selects the closest Steiner point to itself as the location to which all future packets from that source will be forwarded, and begins the third phase.

3.3 Phase III: Data Communication

In this phase, all source nodes send their packets to their closest Steiner point, which is a UAV node in the location identified. The UAV nodes forward the packet to the geographical area of the Steiner points.

At each Steiner point, a virtual area of radius $r_s$ is imagined. A UAV node present in this area is chosen as the Steiner node based on the amount of time the node will be present in the area. All packets destined for the geographic location of the Steiner point will be received by this Steiner node. When the Steiner node is about to leave the area, it designates another node in that area as the Steiner node. If the network supports a subset of UAV nodes that are in the controlled mobility category, a dedicated UAV (or a set of UAVs) can be assigned as a Steiner point to relay the data.

When a packet reaches the Steiner node v, the next closest Steiner point $v^\prime$ to v is calculated. The packet is forwarded to $v^\prime$, if the gateway node is closer to $v^\prime$ than to v. Otherwise, the packet is forwarded to the gateway node.

Thus, all communication is done as per the calculated Steiner tree of the network. Routing via Steiner nodes will guarantee that a minimum number of nodes will be participating in data communication connecting all the source nodes. A scenario of data communication using three sources is shown in Fig. 3.

Fig. 3.

Scenario of three sources communicating with Gateway via a Steiner Node

4 Performance Evaluation

The proposed approach is simulated using Castalia, a network simulation framework in OMNET++. The performance evaluation is done by comparing the proposed approach with GPSR and ROF. The parameters chosen for the simulation are listed in Table 1. The simulation is done by varying the number of sources and packet rate. For simulation, the mobility model used is a random way-point model.

Table 1. Simulation Parameters

Fig. 4.

PDR vs Velocity

Fig. 5.

PDR vs Number of Sources

Fig. 6.

Energy vs Packets per second

Multiple iterations of the simulation are done to compare the proposed approach with GPSR and ROF. Simulation is done by varying the velocity of the mobile nodes with four sources to compare the packet delivery ratio (PDR). From Fig. 4 it is clear that as the velocity increases, the PDR value decreases for all routing approaches. This is because of the dynamic topology, the nodes get disconnected and hence affect the overall network performance. It is clear from the graph that Steiner tree-based routing performs better than the GPRS and ROF. For Steiner tree-based routing approach, the overall hops connecting the nodes are fewer which in turn improves the packet delivery. The proposed approach performs better because of the best neighbor selection based on the contact time calculation.

Simulations are done by varying the number of sources with fixed velocity. The velocity, in that case, is assumed to be $10\,knots$ (5 m/s). Sources are placed randomly. Simulations are done with Multiple iterations to calculate the PDR rate with different sources. Figure 5 shows how the PDR value changes with the different numbers of sources. From Fig. 5, it is clear that the proposed approach performs better even though the initial case with two sources performs slightly below GPRS. It is also clear from the results that when the number of sources increases, the PDR values also reduce. This is because, with a higher number of sources in the network, overall traffic increases and hence results in the collision of packets. Network interference is another reason for reduced PDR.

Simulations are done to verify the energy spent in the network by increasing the sending rate. This is done by fixing the number of sources to four. Multiple iterations are done with sources starting with random locations for each iteration. Similar to the above results, the average values are plotted and are shown in Fig. 6. Results indicate that the proposed approach and ROF perform equally better when compared to GPSR. This is mainly due to node mobility and with less number of nodes participating in the network.

5 Conclusion

The paper proposes an energy-efficient routing protocol for UAV networks with multiple sources. In this paper, we propose the use of mobility vector information to calculate the best neighbor to transfer the data. The paper also considers the case where multiple sources communicate with the gateway node. A Steiner tree-based routing protocol is proposed to calculate the best path for routing the data with a minimum number of nodes participating. The simulation results indicate that the proposed approach is efficient in terms of energy and packet delivery ratio compared to GPRS and ROF routing protocol. Future Research would focus on covering more scenarios based on different dynamic topologies and improving the efficiency of data transmission between multiple mobile data sources and the gateway.