Unmanned Aerial ad Hoc Networks: Simulation-Based Evaluation of Entity Mobility Models’ Impact on Routing Performance

Abstract

An unmanned aerial ad hoc network (UAANET) is a special type of mobile ad hoc network (MANET). For these networks, researchers rely mostly on simulations to evaluate their proposed networking protocols. Hence, it is of great importance that the simulation environment of a UAANET replicates as much as possible the reality of UAVs. One major component of that environment is the movement pattern of the UAVs. This means that the mobility model used in simulations has to be thoroughly understood in terms of its impact on the performance of the network. In this paper, we investigate how mobility models affect the performance of UAANET in simulations in order to come up with conclusions/recommendations that provide a benchmark for future UAANET simulations. To that end, we first propose a few metrics to evaluate the mobility models. Then, we present five random entity mobility models that allow nodes to move almost freely and independently from one another and evaluate four carefully-chosen MANET/UAANET routing protocols: ad hoc on-demand distance vector (AODV), optimized link state routing (OLSR), reactive-geographic hybrid routing (RGR) and geographic routing protocol (GRP). In addition, flooding is also evaluated. The results show a wide variation of the protocol performance over different mobility models. These performance differences can be explained by the mobility model characteristics, and we discuss these effects. The results of our analysis show that: (i) the enhanced Gauss–Markov (EGM) mobility model is best suited for UAANET; (ii) OLSR, a table-driven proactive routing protocol, and GRP, a position-based geographic protocol, are the protocols most sensitive to the change of mobility models; (iii) RGR, a reactive-geographic hybrid routing protocol, is best suited for UAANET.

1. Introduction

The movement pattern of unmanned aerial vehicles (UAVs) [1] in UAANET depends on the type of application for which they are being used. For example, a mobility model that allows the nodes to move independently from one another is more suitable in searching missions where a large area has to be scoured.

Mobility models can be classified into two main groups: path-defined mobility models and random mobility models. In path-defined mobility models, a path is predefined for the node to follow. The positions that the nodes are going to go through are set in advance. In random mobility models, the positions are computed “as we go”. Such models are more suitable for searching missions where the information available about the searched area is minimal. Random mobility models can be further classified into two main groups: group mobility models and entity mobility models. In group mobility models, the nodes move as a group, following a group leader. Conversely, in entity mobility models, the nodes move independently from one another. Since our main interest is in searching missions in UAANET, this paper focuses on random entity mobility models.

The deployment of UAANET is still not widespread nowadays. Consequently, real-life measurements for pure research purposes are mostly non-existent and, where available, can be very expensive. Therefore, the research community has to rely on simulations as an alternative in order to develop and evaluate routing protocols. The mobility models used in simulations play a central role in such a context. It actually would be nice to design routing protocols that are insensitive to mobility patterns and that would perform well regardless of the mobility pattern used in the simulation. Since this is mostly not the case, this paper conducts an in-depth experimental study to understand how and why mobility models affect the performance of routing protocols in UAANET in the context of search missions.

An accurate evaluation of the impact of the mobility models on the performance of routing protocols requires testing multiple mobility patterns and different routing protocols. Otherwise, the observations made and the conclusions drawn from the simulation studies may be misleading. For that reason, we are considering five distinct random entity mobility models in this paper: the random waypoint (RWP) [2], the random direction (RD) [2], the smooth-turn (ST) [3,4], the Gauss–Markov (GM) [5] and the enhanced Gauss–Markov (EGM) [6] models. RWP is widely used for simulations of MANET due to its simplicity and its availability in almost all simulators. However, this model is very unrealistic, since it features sudden stops and sharp turns. Due to mechanical and dynamics constraints, UAVs cannot turn abruptly nor stop/accelerate suddenly. RD, which is fairly similar to RWP, is just as unrealistic as RWP for the same reasons. ST and GM were proposed in order to overcome these sharp turns and sudden stops problems. However, they still feature sharp turns at the boundaries. To solve this problem, we proposed EGM as part of our previous work [6].

For the routing protocols, we are considering four very distinct protocols: ad hoc on-demand distance vector (AODV) [7,8], optimized link state routing (OLSR) [7,9], reactive-geographic hybrid routing (RGR) [10,11,12,13] and geographic routing protocol (GRP) [14]. AODV is a reactive on-demand routing protocol, whereas OLSR is a table-driven proactive routing protocol. GRP is a geographic routing protocol, and RGR is a hybrid reactive and geographic routing protocol that we developed in a previous work [10,11,12,13]. We also consider simple packet flooding for further understanding. For our analysis, we first define a set of protocol-independent metrics to characterize and compare the different mobility models. These metrics will also help to explain the different performance shown by the routing protocols under various mobility models. We also define a set of metrics that capture the routing performance and rank the routing protocols based on their observed performance. All of this should tell us, in detail, how and why the mobility patterns affect the routing protocol performance in UAANET.

Our goal in this paper is to investigate how mobility models affect the performance of UAANET in simulations. We perform this investigation in order to come up with conclusions/recommendations that provide a benchmark for future simulations of UAANET. No such benchmark exists in the literature for UAANET. Most of the work presented in the literature is a bit limited in that regard, and it only addresses relatively low mobility MANET. UAANET are very high mobility MANET and need to be addressed more specifically; which is what we are doing in the paper. Our work is based on existing protocols and models. We do not aim to propose a new routing protocol nor mobility model. We do not aim to provide mathematical analyses in the paper either.

The remainder of this paper is organized as follows. Section 2 summarizes the related work. Section 3 presents the five mobility models and the routing protocols that we are considering. The evaluation metrics are presented in Section 4. Simulations and analysis are presented in Section 5, and concluding remarks are made in Section 6.

2. Related Work

An analysis of the impact of mobility models on the performance of MANET is provided in [15]. The main conclusion is that even when setting the same parameters, different mobility models have different impacts on the performance evaluation of protocols. Although they focus on entity mobility models as we do, the speed range is limited in the range of 2–10 m/s, which is way below the range of 50–60 m/s that we are considering for UAANET. Therefore, the work in [15] is for relatively low mobility MANET, and their analysis is limited to the impact of speed and pause time on the performance of MANET. Moreover, they provide no clear comparison between the chosen mobility models per se. Such a comparison would need to be carried out by means of protocol-independent metrics, for instance.

The same problem of non-applicability to UAANET is found in [16]. Here, the authors compare the performance of different routing protocols, namely RWP, reference point group mobility (RPGM) and file-based models. One of the main conclusions is that the performance ranking of the routing protocols changes depending on whether the nodes are moving according to a group mobility model. However, the analysis is done over a hybrid network, where four groups of nodes have different mobility, ranging from static to high UAANET-like mobility. Therefore, the conclusions drawn do not necessarily apply to pure UAANET, which are our main focus.

Prabhakaran and Sankar [17] also carried out experiments to evaluate the impact of entity and group mobility models on the performance of MANET using the AODV routing protocol. Once again, the conclusion is that the MANET performance is affected by the mobility of the nodes; therefore, the mobility model has to be chosen in accordance with the scenario in consideration. Unfortunately, only a single routing protocol (AODV), a reactive one, is considered in the analysis. Moreover, the variation of the nodes’ speed from 5–80 m/s in the scenarios often falls within the range of slow mobility; which is not interesting for UAANET. Similar to [17], yet specifically for vehicular ad hoc networks (VANET), Luo et al. [18] analyzed the performance of a routing protocol over different mobility models, including the RWP, the Simulation of Urban Mobility (SUMO) [19] and the Shanghai Urban Vehicular Network (SUVnet) model. SUMO is an open source, microscopic, space-continuous traffic simulator designed to handle large road networks, whereas SUVnet is a realistic mobility model obtained from the actual GPS data collected from more than 4000 taxis in Shanghai, China. The considered routing protocol is the distance-aware epidemic routing (DAER) protocol, which is also introduced in [18]. The results show that the selection of mobility models heavily influences the routing performance. Moreover, the performance under the SUVnet reality-based mobility model is worse than under the other two models. The conclusion is that even by means of a complex map-based microscopic traffic simulator, care should be taken, as the results obtained with these models might not be as close to reality as expected. This further points out the crucial role of mobility models, as poorly choosing one of them can actually yield misleading conclusions on an actual routing protocol’s performance. However, the analysis in [18] focuses on VANET with speeds of the order of 7 m/s, which is very low compared to our average of 55 m/s for UAANET. The analysis of Simaremare et al. in [20] with respect to our concern is even more simplistic. They proposed an optimized version of AODV and then compared its performance under RWP and RPGM. The results showed higher performance with RWP. In [21], Amnai et al. investigate how the AODV protocol behaves when the number of nodes increases with different mobility models, including RWP, RD and Mobgen steady state. The observation is that AODV performs well under RD compared to the other mobility models, and their major conclusion is that AODV can be used for applications that tolerate a small amount of packet loss. Unfortunately, be it in [20] or in [21], no clear explanation is provided as to what feature or statistical behaviour of a given mobility model actually influences which aspect of the protocol.

The authors in [22] study the impact of mobility patterns on multicast routing protocols for MANET. A better analysis (compared to a few aforementioned papers) is provided that shows that the mobility pattern influences the connectivity graph, which, in turn, influences the protocol performance. It is also found that routing protocols perform better under unrealistic RWP. Yet, among the considered models is the Manhattan grid, which is not applicable to UAANET, not to mention that the speed of the nodes in the models can go as low as zero, which again is a problematic value when considering UAANET. A comparative analysis of various common routing protocols under various mobility models is also provided in [23]. A wide range of routing protocols of different types (reactive, proactive and hybrid) are considered. For mobility, group, file and RWP mobility models are considered. The simulations show that the mobility model has a significant impact on the performance of the routing protocols. Plus, RWP once again shows better performance for the protocols. However, there are a few problems with the simulations. For example, the simulations run for 30 s, which is problematic, since we know that RWP, for instance, needs a certain time in order to reach its steady-state spatial distribution [24]. Therefore, the conclusions drawn in [23] might well be skewed due to a transitory state. From our experience, it takes about 600 s to observe a steady-state-like behaviour in the performance metrics. We might have formulated similar reservations with the analysis in [25], where the simulation only lasts 500 s, but they specifically consider a different version of RWP. In fact, they use the random way point-steady state (RWP-SS) [26], where the initial speed and the stationary distribution location are sampled in order to overcome the problem of discarding the initial simulation data. In [25] also, AODV is used as the underlying routing protocol for simulation. The authors reached the conclusion that a mobility model should be selected based on the type of application scenario. Yet, they recognized the lack of evaluating multiple distinct routing protocols in their analysis. Furthermore, the speed range they used, with a maximum of 25 m/s, is considered relatively low in the context of UAANET. AODV is also the underlying routing protocol in the comparative simulation study of RWP and GM mobility models on the performance of MANET presented in [27]. The results show that both mobility models are not different at speeds representative of human mobility. In this case, which is of no interest for UAANET, the authors advise using RWP, because it has less computational overhead compared to GM. When the speed of the nodes is as high as fast automobiles, the performance result using RWP is significantly different from GM, and the authors advise to use GM instead. Then again, there is no in-depth analysis or comparison of the two mobility models based on routing-protocol-independent metrics. Such an analysis would provide a better understanding of the effects of the models on AODV, for instance. Not to mention that, once again, there is a lack of evaluating multiple routing distinct protocols in [27], as well.

In [28], the performance of DSDV (destination-sequenced distance-vector) and AODV under the realistic mobility model is analysed and compared. The realistic mobility model is obtained based on spatial and temporal information about each and every node in a healthcare environment and based on personal behavior modelling [29]. However, this is about a simulation area of 27 m × 18 m with mobile nodes moving at 0.6 m/s and, therefore, a fairly static MANET. In [30], the impact of random and realistic mobility models on the performance of Bypass-AODV is studied. Bypass-AODV is an optimization of AODV that uses cross-layer MAC-notification. The results show that Bypass-AODV is insensitive to the random mobility models used and has a clear performance improvement compared to AODV. It has a comparable performance under a group mobility model compared to AODV. However, the study is more about a comparison between AODV and Bypass-AODV and less about how mobility models affect the performance of MANET in general. Even so, a considerable range of the speeds they used is not interesting for UAANET.

Unlike the limited analysis in [30] and most of the work cited above, a general analysis framework is presented in [31]. This framework analyzes the impact of mobility on the performance of routing protocols in ad hoc networks (IMPORTANT). The authors try to explain why and how mobility affects routing protocol performance. For that matter, the performance of three different routing protocols (AODV, DSR (dynamic source routing) and DSDV) is observed under four different mobility models. However, first, the mobility patterns are evaluated among themselves by means of predefined protocol-independent mobility metrics. This evaluation helps understand/explain the relative performance of the protocols across the mobility models. This work [31] is similar to what we are doing here in this paper. However, in [31], the diversity of routing protocols is limited as, for instance, AODV and DSR are both reactive protocols. Instead of having two of the three protocols being of the same general approach to routing in MANET, they could have chosen a hybrid protocol or a geographic protocol. Moreover, some of the low speed ranges that they are considering are not applicable for a study in UAANET; not to mention that we are focusing on entity mobility models mostly for searching missions applications, for instance, which is not the case in [31], where group mobility and grid patterns are considered.

Each of the above reviewed related work suffers from one or more of the following shortcomings: lack of a study that targets the typical speed range of UAANET (around 55 m/s), limited diversity on the types of routing protocols, lack of comparison of the mobility models among themselves by means of protocol-independent evaluation metrics that would explain the impact on the routing protocols, non-applicability to UAANET of some of the considered mobility models, no targeted study towards entity mobility models that would more likely be used in search applications of UAANET, for example. Therefore, we feel compelled to conduct an analysis that is directed at UAANET and that resolves all of the aforementioned shortcomings. To the best of our knowledge, this is the first study/analysis of this kind.

3. Summary of the Considered Mobility Models and Routing Protocols

3.1. The Mobility Models

3.1.1. The Random Waypoint Model

The RWP mobility model [2] is frequently used for simulations in MANET, mainly because of its relative simplicity and wide availability in simulators, like NS-2 [32], NS-3 [33] and OPNET [34]. It works as follows. A node randomly picks a location within the simulation area and moves to that location in a straight line, using a randomly-chosen speed. Upon arrival at that location, the node pauses and picks another location. However, the node is subject to sudden stops, sudden accelerations and sudden speed changes. The same applies to direction, where a node can suddenly make a 180° turn. Figure 1 shows the simulation trajectory trace of a UAV under RWP in a 1000 m × 1000 m area.

As mentioned earlier, airborne vehicles have mechanical and aerodynamic constraints that prevent them from making sharp turns like the ones shown in Figure 1. Obviously, despite the widespread usage of this mobility model, it is not very realistic. Therefore, it can lead to deceiving simulation results when used to evaluate the performance of routing protocols.

3.1.2. The Random Direction Model

The RD [2] model is a variant of the RWP model. RD was proposed in order to overcome a certain limitation of RWP. In fact, in RWP, the nodes tend to cluster around the center of the region and move away from the boundaries. This creates a non-uniform spatial node distribution and density wave problem stemming from the fact that the distribution of the movement angles is not uniform in RWP, as shown in [24,27,35]. In order to solve this, RD works as follows: instead of picking a random position, like in RWP, a mobile node (MN) randomly (uniform distribution) chooses a direction in which to move. It moves in that direction until it hits a boundary of the simulation region. It then stops for a time before choosing another direction. Similar to RWP, if the pause time is set to zero, the mobile node never pauses until the simulation is over. As we can see in Figure 2, the direction changes occur only at the boundaries. In [36], the authors claimed that RD results in less fluctuation in node density than RWP.

Figure 1. Trajectory of a UAV under the random waypoint (RWP) model.

Figure 1. Trajectory of a UAV under the random waypoint (RWP) model.

Figure 2. Trajectory of a UAV under the random direction (RD) model.

Figure 2. Trajectory of a UAV under the random direction (RD) model.

3.1.3. The Smooth-Turn Model

The ST mobility model is proposed in [3,4]. The idea is as follows. An MN randomly chooses a point along the line perpendicular to its direction and circles around that point until it chooses another center. The perpendicularity ensures the smoothness of the trajectories. In a nutshell, the MN continuously moves in circular arcs. The choice of the centers is random, as well as the choice of the duration of the movement along the corresponding circular arc. As proposed in [3,4], the duration distribution is exponential. For the selection of the centers, the inverse length of the turning radius follows a Gaussian distribution in order to ensure that straight lines and slight turns are favored over very sharp curvy turns. At the boundary of the movement area, a “reflection” strategy is used. This strategy consists of mirroring the out-of-region trajectory against that boundary. Figure 3 shows a UAV simulation trajectory using the above-described ST mobility model.

Figure 3. Trajectory of a UAV under the smooth-turn (ST) model.

Figure 3. Trajectory of a UAV under the smooth-turn (ST) model.

3.1.4. The Gauss–Markov Model

GM, like ST, is motivated by the need to have a model that is closer to reality in the sense that a node, for instance, would accelerate, decelerate or turn progressively. The model was proposed by Liang and Haas [5]. The current movement of a node (speed and direction) is related to the previous movement through Gaussian equations, using average speed and direction, as well as Gaussian random noise. A parameter α controls the degree of dependency on past speed and direction. The model is therefore said to feature temporal dependency. At a pre-set instant t, the direction and speed of a given node are calculated. The node moves with that direction and speed for a constant time interval T, and the speed and direction are calculated again. Figure 4 shows an example of a GM trajectory in a 2D area.

Figure 4. Trajectory of a UAV under the Gauss–Markov (GM) model.

Figure 4. Trajectory of a UAV under the Gauss–Markov (GM) model.

The behaviour of the model at the boundaries is addressed in different ways. In [2], Bai and Helmy suggest a direction change at the boundary without specifying exactly how this is done. In [37], Amoussou et al. propose a 180° turn. This strategy is problematic, since it goes against one of the main reason why the GM model was proposed in the first place; which was to avoid sharp turns. Furthermore, the temporal dependency of GM is lost here, since the next direction is now unrelated to the previous one in this case. Alenazi et al. [38] propose a strategy to force the MNs away from the simulation boundaries. They define a buffer zone around the boundary. When the MN enters that zone, the mean direction is changed, so that the node is progressively pushed toward the center of the region.

3.1.5. The Enhanced Gauss–Markov Model

The EGM mobility model is proposed in [6]. It is based on the GM mobility model, but the direction is computed slightly differently; most importantly, a progressive mechanism for boundary avoidance is implemented. The key mechanisms of the mobility model are as follows. When the node is far enough from the boundaries, the next speed and the next direction deviation are calculated normally (very similarly to GM) using certain equations. When the node gets close to a boundary (within a distance of 250 m from it), a turning toward the center region is initiated. This is in order to smoothly/gradually avoid hitting the boundary. If, despite the boundary-avoidance scheme, it is still determined that the next position of the node falls outside the region, then “it is brought back in” a little more forcefully. However, the situations where more “force” is used are expected to be rare.

Figure 5 shows the trajectory of a UAV when the EGM mobility is used in a simulation. As we can easily observe, the trajectory is noticeably smoother than the one generated with RWP (Figure 1). There are virtually no sharp turns, and the node does manage to avoid the boundaries in a very smooth and progressive way. This behavior that we observe at the boundaries is an advantage that EGM clearly has over the other mobility models where we observe sharp turns at the boundaries.

3.2. The Routing Protocols

3.2.1. AODV

The ad hoc on-demand distance vector (AODV) protocol [7,8] is a reactive routing protocol. When a source node wants to initiate transmission with a destination node in the network, it first initiates a route discovery by sending out a route request message (RREQ) to its neighbors, and those neighbors, in turn, forward the RREQ to their neighbors’ nodes. Whenever the route to a destination node is located or an intermediate node has a route to destination, a route reply message (RREP) is generated and sent to the source node. Once a route is established, the data packet transmission starts between the source node and the destination node. However, when the data packet is being routed, it can happen that a next hop is unreachable (broken link) due to the mobility of the nodes. The intermediate node where this occurs sends out a route error (RERR) message to the source node and drops the data packet if local repair is not enabled. When local repair is enabled, the intermediate node holds on to the data packet while it tries to repair the route locally by sending out new RREQs in order to establish a new route to the destination.

Figure 5. Trajectory of a UAV under the enhanced GM (EGM) model.

Figure 5. Trajectory of a UAV under the enhanced GM (EGM) model.

3.2.2. Geographic Routing Protocol (GRP)

The geographic routing protocol (GRP) [14] is a position-based routing protocol based on two assumptions: (1) each node is aware of its own geographic location and the location of its immediate neighbors; and (2) the source node is aware of the position of the destination node. Immediate neighbors’ locations are updated periodically by means of HELLO messages. The data packets are routed through the network using the geographic location of the destination. GRP operates without routing tables, and routing to the destination relies on the information each node has about its neighbors. The most commonly-used geographic routing algorithms are greedy forwarding and face routing. In greedy forwarding, the data packet is brought closer to the destination in each step by the holding node forwarding it to the neighbor that reduces the distance to the destination. Greedy forwarding fails if there is no next hop among the neighbors that is closer to the destination. When this happens, the greedy forwarding switches over to perimeter mode, where the next hop is selected to traverse the perimeter of the region where greedy forwarding fails. Perimeter mode forwarding continues as long as there is no better greedy next-hop neighbor. In face routing, the regions are considered to be separated by the edges of a planar graph. The algorithm takes a way around the face; it returns to the point closest to the destination and explores the next face closer to the destination. Face routing always finds a path to the destination.

3.2.3. Reactive–Greedy–Reactive (RGR)

The reactive–greedy–reactive (RGR) [10,11,12,13] routing protocol is obtained by merging AODV with the geographic greedy forwarding (GGF) [13,39] protocol. The very high mobility of the nodes and the limited transmission range lead the routes to break quite often in AODV. When that happens, AODV offers a route repair mode. In RGR, this route repair is replaced by GGF for an improved performance. GGF works as follows. When a link in a route breaks while a packet is trying to be transmitted to the next hop, the packet is sent to the neighbor that is closer to the destination. In RGR, as inherited from AODV, nodes periodically broadcast HELLO messages so that neighbors can update their respective routing tables. This association of AODV and GGF yielded the RGR protocol. A reliability criterion [10] is made use of during the route discovery phase, and a recovery strategy [11] deals with GGF failure. The goal of the reliability criterion is to select the most robust and reliable route from the route discovery. This is achieved by making use of the concept of reliable distance [40]. As far as GGF is concerned, the idea is to forward the data packet to the neighbor whose location is closer to the destination than the forwarding node (the node currently having the packet). If there is no such neighbor, GGF is said to have failed, and the packet is dropped. In order to overcome this failure, a low-complexity and low-overhead recovery strategy consists of forwarding the packet to the best-moving node (BMN) when GGF fails. The BMN is the node, within the transmission range (the forwarding node included), that is deemed to move faster toward the destination. The decision on which node is moving faster toward the destination is based on predictions that are made using the current speed and direction of the nodes.

3.2.4. Optimized Link State Routing Protocol (OLSR)

The optimized link state routing protocol (OLSR) [7,9] is a table-driven protocol. Routes are continuously stored and updated in tables. Therefore, whenever a route is needed, the protocol presents the route immediately without any initial delay. In order to reduce the overhead of packet transmission, candidate nodes, called multipoint relays (MPRs), are selected and responsible for forwarding broadcast packets during the flooding process. OLSR performs hop-by-hop routing, where each node uses its most recent routing information to route packets. The MPR selection is done in such a way that it covers all of the nodes that are two hops away. A node senses and selects its MPRs with HELLO messages. HELLO messages are sent at a regular time interval. MPR selection is signaled through the HELLO messages. The topology control (TC) messages broadcast a subset of the topology information to enable each node to build a (partial) network topology and determine routes based on Dijkstra’s shortest path algorithm, for example [9,41].

3.2.5. Flooding

Flooding indicates that no routing protocol is used. The source node simply broadcasts the data packet to all of its neighbors. Each neighbor receiving the data packet also blindly broadcasts it to its neighbors. This simple receive-and-broadcast mechanism continues until the destination is reached. Obviously, this method is expected to add a high traffic load to the network, and that traffic load can be viewed as overhead. The advantage of this method is that it guarantees the delivery of any data packet unless the network is partitioned and the destination completely unreachable. Therefore, the packet delivery ratio obtained by this method can be viewed as the upper bound for any routing protocol in the given network.

4. Evaluation Metrics

4.1. Mobility Models’ Metrics

We are comparing mobility models and evaluate them by means of seven protocol-independent metrics. Some of these metrics have been used in the literature [3,31] for the same purpose of comparing mobility models. We have added a few here, as we believe that they further describe the dynamics of the network, and knowing them will help explain the performance of the routing protocols later.

4.1.1. Network Diameter

In [42], the network diameter is defined as follows. It is the maximum distance in hops between two nodes. More formally, let lg(a,b) be the minimum number of edges required to find a connected path between a and b in the two-dimensional space V². Then,

Diameter = max{lg(a,b)} ∀ (a,b) ∈ V²

(1)

As claimed in [42], this diameter is representative of the average length of the paths of the network. Thus, a mobility model that creates a low diameter will, for example, improve routing performance and minimize interference. Although this metric can reflect routing performances, it is related only to the mobility model by itself, independent of any particular protocol.

4.1.2. Average Number of Components

A component is a set of nodes that are all reachable to one another through a path of edges. This metric tells us whether the network is partitioned or not. For example, a network that has two components is partitioned into two; three components means that the network is partitioned into three, etc. The less the network is partitioned, the better the routing and flooding of packets will perform.

4.1.3. Average Coverage

Coverage is the percentage of the defined area that has been passed through by a node at any point in time. The area is divided into a virtual grid, represented by a two-dimensional array. During each cycle, each node increases the array value corresponding to its location by one. The coverage percentage is calculated by determining how many parts of the array have a value greater than zero, then dividing that by the total number of parts and multiplying by 100. The final result gives an easy visualization of the node distribution. This visualization allows us to see if the distribution is homogeneous and not concentrated around the center of the simulation area, for instance.

Coverage is important in our analysis because it gives an indication of how suited the mobility model is to the type of application for which we want to use it. Our main concern in this paper is search missions; therefore, a mobility model with a large enough coverage of the entire region without major unbalanced clustering is preferred because it shows that the mobility pattern allows extensive searching of the entire region. Moreover, the faster most of the area is covered, the better the mobility model is.

4.1.4. Average Clustering Coefficient

The clustering coefficient is the ratio of radio links among neighbors and the number of neighbors. It is calculated for each node by determining how many links there are between neighbors of the node, divided by the number of neighbors it has at that point in time. More formally [42], if N(u) is the set of neighbors of node u, then the clustering coefficient is defined as:

$$\frac{{{\displaystyle \sum }}_{v\in N\left(u\right)}\left|\left\{x\in N\left(v\right)\right\}\right|}{N\left(u\right)}$$

(2)

This metric is a measure of the network redundancy. When a node presents a high clustering coefficient, this means that its neighbors have many radio links with each other. Therefore, the node is said to be redundant if a route can, with a high probability, pass through its neighbors without a path length increase.

4.1.5. Average Number of Neighbors

Two nodes are considered neighbors if they directly connect with each other or, in other words, if they are within each other’s transmission range. The average number of neighbors here accounts for the number of neighbors each node is expected to have on average.

4.1.6. Average Path Length

The average path length is the average minimum number of hops that a packet has to go through between any source-destination node pairs in the network.

4.1.7. Average Number of Created/Broken Links

The average number of created/broken links indicates the number of links added/broken on average at every second of the simulation.

4.2. Routing Protocols Metrics

We evaluate the performance of routing protocols and flooding by means of three metrics.

4.2.1. Packet Delivery Ratio

The packet delivery ratio (PDR) is the ratio between the successfully-received packets and the total number of packets sent.

4.2.2. Routing Overhead

Routing overhead represents the number of control packets, such as RREQs, RREPs, RERRs and HELLO messages. Basically, it is the amount of extra traffic that is distributed in the network in order to provide the possibility of sending data packets. However, in the case of flooding, there are no control packets, but there are multiple data packet transmissions. Therefore, in the case of flooding, we will quantify the overhead as the number of data packet transmissions.

4.3.3. End-to-End Delay

The End-to-End delay is the averaged delay over all of the data packets that make it from the source to the destination.

5. Simulation and Analysis

We used OPNET Modeler 16.0 [34] for the simulation of the routing protocols. We set the channel capacity to be 11 Mbps for all mobile hosts. The rest of the simulation settings and parameters are summarized in Table 1.

We have only one source node and one destination node for data packets. The 28 remaining nodes are potential forwarding nodes. For each protocol, and with the above set of parameters, we generate 30 independent scenarios using 30 different seeds of the pseudo-random number generator available in OPNET. By doing so, we have 30 sets of pseudo-independent results for every metric for every protocol. The 30 results are then averaged. Confidence intervals are also calculated.

Table 1. Simulation parameters.

Parameter	Value
Number of simulated nodes	30
Area length	2000 m
Area width	4000 m
Wireless transmission range	1000 m
Packet size	1024 bits
Send rate of traffic	5 pkts/s
Speed	50 to 60 m/s
Pause time at simulation	0 s
Simulation time	1800 s

Table 1. Simulation parameters.

Parameter	Value
Number of simulated nodes	30
Area length	2000 m
Area width	4000 m
Wireless transmission range	1000 m
Packet size	1024 bits
Send rate of traffic	5 pkts/s
Speed	50 to 60 m/s
Pause time at simulation	0 s
Simulation time	1800 s

5.1. Statistical Analysis of the Mobility Models

RWP was initially present in OPNET. We implemented EGM and ST in OPNET ourselves. For RD and GM, we imported them from BonnMotion [43] and used them in OPNET protocol simulations.

Table 2 shows a recap of the mobility models’ statistics according to the metrics discussed in Subsection 4.1. All of the metrics are shown in Table 2, except for coverage, which is shown in Figure 6. Note that the numbers presented are the averages over 30 independent runs. The 95% confidence intervals are presented in the form of “±error” near each average value. These statistics are obtained by means of a C++ Network Analyzer program that we had written specifically for that purpose. The program creates statistics from dynamic and static network simulations of NS-2 and OPNET using the Boost Graph Library [44]. The program also uses MATLAB, GraphViz and Excel to help visualize, organize and interpret the statistics as needed.

In terms of network diameter, we can see that RWP has the lowest and RD has the highest, closely followed by ST. Therefore, it is expected that, overall, routing protocols will perform better under RWP compared to the others and worse under RD and ST. As we already know, a mobility model that creates a low diameter will improve routing performance and minimize interference.

Table 2. Mobility models statistics.

Metric	RWP	EGM	ST	RD	GM
Network diameter	5.0 ± 0.4	5.5 ± 0.4	5.8 ± 0.5	6.0 ± 0.5	5.5 ± 0.3
(hops and meters)	3777 ± 226 m	4146 ± 206 m	4374 ± 403 m	4455 ± 269 m	4159 ± 203 m
Number of components	1.05 ± 0.03	1.10 ± 0.03	1.09 ± 0.03	1.13 ± 0.02	1.09 ± 0.03
Clustering coefficient	3.4 ± 0.2	2.7 ± 0.2	2.3 ± 0.2	2.3 ± 0.2	2.6 ± 0.1
Number of neighbors	10.3 ± 0.4	8.8 ± 0.4	7.7 ± 0.3	7.6 ± 0.5	8.5 ± 0.2
Path length	2.1 ± 0.1	2.3 ± 0.1	2.5 ± 0.4	2.5 ± 0.2	2.3 ± 0.2
(hops and meters)	1461 ± 83 m	1597 ± 62 m	1764 ± 271 m	1796 ± 93 m	1654 ± 119 m
Links created	3.9 ± 0.04	3.2 ± 0.03	2.7 ± 0.04	3.8 ± 0.02	4.3 ± 0.04
Links broken	4.0 ± 0.03	3.2 ± 0.03	2.7 ± 0.05	3.9 ± 0.02	4.4 ± 0.04

Table 2. Mobility models statistics.

Metric	RWP	EGM	ST	RD	GM
Network diameter	5.0 ± 0.4	5.5 ± 0.4	5.8 ± 0.5	6.0 ± 0.5	5.5 ± 0.3
(hops and meters)	3777 ± 226 m	4146 ± 206 m	4374 ± 403 m	4455 ± 269 m	4159 ± 203 m
Number of components	1.05 ± 0.03	1.10 ± 0.03	1.09 ± 0.03	1.13 ± 0.02	1.09 ± 0.03
Clustering coefficient	3.4 ± 0.2	2.7 ± 0.2	2.3 ± 0.2	2.3 ± 0.2	2.6 ± 0.1
Number of neighbors	10.3 ± 0.4	8.8 ± 0.4	7.7 ± 0.3	7.6 ± 0.5	8.5 ± 0.2
Path length	2.1 ± 0.1	2.3 ± 0.1	2.5 ± 0.4	2.5 ± 0.2	2.3 ± 0.2
(hops and meters)	1461 ± 83 m	1597 ± 62 m	1764 ± 271 m	1796 ± 93 m	1654 ± 119 m
Links created	3.9 ± 0.04	3.2 ± 0.03	2.7 ± 0.04	3.8 ± 0.02	4.3 ± 0.04
Links broken	4.0 ± 0.03	3.2 ± 0.03	2.7 ± 0.05	3.9 ± 0.02	4.4 ± 0.04

Figure 6. Coverage for the various mobility models.

Figure 6. Coverage for the various mobility models.

In terms of the number of components, once again, RWP shows the least and RD shows the largest. These are averages over many simulation runs and over a long period of simulation time (1800 s). What we learn from here is that overall RD causes the network to be partitioned more often than all of the other mobility models, especially RWP, which causes the least partitioning. Therefore, we should expect a performance under RD that is distinctively lower than that under RWP.

The clustering coefficient is distinctively higher, once again, with RWP. When a node presents a high clustering coefficient, this means that its neighbors have many radio links with each other. A route can, with high probability, pass through its neighbors without a path length increase. Therefore, we should expect the routing protocols to perform better with RWP and less with RD and ST.

The average number of neighbors is the lowest under RD and ST and highest under RWP. The second highest average number of neighbors is observed under EGM. This should also lead to better protocol performance under RWP; for the higher the number of neighbors, the higher probability of finding a route. Moreover, we observe that the average path length actually follows the reverse classification of the average number of neighbors. This can be explained by the fact that having more neighbors per node increases the chances of neighbors of my neighbors being also my neighbors; which therefore saves one hop right there and reduces the hop-measured path length. These two statistics (number of neighbors and path length) are expected to reflect on the average end-to-end delay with the routing protocols. We should consistently observe lower delay under RWP followed by EGM and the worst delay under RD.

In terms of the fluctuation of the topology measured by means of the average number of links created/broken, we can see that the network topology changes the most under GM and RWP and the least under ST. However, the ratio of broken links over created links is roughly the same for all of the mobility models. There is no mobility model that tends to “accumulate” or “lose” links over time compared to another.

As far as coverage is concerned, Figure 6 depicts it as a function of time. We can infer that EGM, GM and RD provide a better coverage of the entire area (close enough to 100%), compared to RWP and ST. The mobility models present a steady state. By steady state, we mean a state when the coverage ratio remains close to a constant. We see that RD and GM reach the steady-state coverage faster with the highest steady-state value (almost 100%), closely followed by EGM. ST has the slowest convergence towards its steady state (around 95%). In fact, it seems as if it just reaches its steady state towards the end of the simulation (1700 s). RWP converges to its steady-state value almost at the same pace as RD and GM do; however the steady-state value of RWP is the lowest of all (90%). Overall, the main information to take away from Figure 6 is that with some mobility models (ST and the widely-used RWP), the 30 nodes take way more time than others (EGM, GM and RD) to cover the entire region in an acceptable/interesting extent. As a matter of fact, anything between the 90% and 100% range can be seen as satisfactory. We can see that GM, RD and EGM enter that range around halfway through into the simulation, whereas as ST enters the same range towards the end. The widely-used RWP enters the range almost at the end of the simulation; this clearly shows an unsatisfactory coverage overall compared to GM, RD and EGM.

Furthermore, we can see in Figure 7 that with RWP, the nodes cluster around the center of the region and pass by the boundary regions with a very low density. At the other extreme, GM (Figure 8) shows a more uniform node distribution with no specific spikes. We expect EGM to have a similar if not slightly better distribution as GM, since it is an enhanced version of the latter.

Figure 7. Node distribution under RWP.

Figure 7. Node distribution under RWP.

Figure 8. Node distribution under GM.

Figure 8. Node distribution under GM.

All of the above on coverage gives us an idea of the better suitability of one mobility model over another when it comes to a UAANET application, such as search missions. We now know that RD, GM and EGM are better choices than RWP and ST. Coverage does not give us much information about the potential performance of routing protocols. It is more of a measure of suitability to a given UAANET application.

The conjunction of all of the above-mentioned statistics leads us to believe that RWP will provide the best performance among all of the routing protocols. On the other hand, RD should exhibit the worst performance among all of the protocols. Moreover, EGM consistently shows the second best statistics right behind RWP. We expect this ranking to reflect on the routing protocols’ performance, as well.

5.2. Performance of the Routing Protocols with the Mobility Models

The simulation results are presented below with 95% confidence intervals. The confidence intervals, which are represented by small vertical segments along the graphs, help us establish the statistical significance of the differences or gaps between any two curves. We plotted our metrics as a function of time in order to capture their behavior as the simulation runs. Note that at the very beginning of the simulation, all of the nodes are bundled together at the bottom left-hand side corner of the simulation region. That corner is the launching point. The nodes spread out as the simulation proceeds and eventually reach a steady-state distribution. Therefore, we are going to consider the values of our metrics toward the end of the simulation as they represent the values at steady state. The fact that the nodes are initially together typically provides the highest PDR and the lowest delay. Furthermore, note that all of the metrics are averaged over time since the beginning of the simulation. All of the metrics reach a plateau, typically after less than half of the simulation time, with further variance well within the 95% confidence interval. We therefore conclude that these values represent the typical performance of the final steady-state UAV distribution.

For the protocol performance, we mostly focus on the PDR to which we associate the routing overhead for half of the protocols (AODV and GRP) and the end-to-end delay for the other half (RGR and OLSR). For flooding, we only present the PDR, as there are no control packets whatsoever to account for routing overhead here. As a matter of fact the definition of routing overhead changes here. It can be measured in terms of the number of packet transmissions per second, for example. In order not to bother with two definitions of routing overhead or deal with two types of overhead, we rather limit the observation of flooding to PDR.

5.2.1. AODV

Figure 9 and Figure 10 show that AODV clearly performs better under RWP, and the performance under RD is the worst. The PDR ranges from about 73% to about 78%, thus a range length of about five percentage points. We already noted that RD presented a few statistics that suggested that the routing protocols would perform their worst under it. The performance of AODV ranking last under RD therefore comes as no surprise here. Similarly, the performance under RWP ranking first is no surprise either.

Figure 9. The packet delivery ration (PDR) of AODV under various mobility models.

Figure 9. The packet delivery ration (PDR) of AODV under various mobility models.

Figure 10. Routing overhead of ad hoc on-demand distance vector (AODV) under various mobility models.

Figure 10. Routing overhead of ad hoc on-demand distance vector (AODV) under various mobility models.

5.2.2. GRP

Figure 11 shows that GRP performs better with RWP in terms of PDR. The performance with the other mobility models in terms of PDR is almost similar, as the slight differences that are observed are not statistically significant. The PDR here ranges from about 40% to about 55%, thus a range length of about 14 percentage points. This range length (of 15%) is double the one for AODV, and it is at a lower level (from 45%). This PDR being best under RWP can be explained by the factors discussed above. RWP results in the smallest network diameter of all mobility models. The network is on average more connected under RWP (see the lowest average number of components). Moreover, the network presents more redundancy under RWP (highest average clustering coefficient) than under the other mobility models. The conjunction of all of these factors explains why GRP achieves a better performance in terms of PDR under the RWP model.

Figure 11. PDR of the geographic routing protocol (GRP) under various mobility models.

Figure 11. PDR of the geographic routing protocol (GRP) under various mobility models.

In terms of routing overhead (Figure 12), the best performance (least overhead) is observed with ST. We saw earlier that the network topology changes the least or the slowest under ST, and that certainly has an impact on the routing overhead of GRP. More specifically, in GRP, nodes flood control messages in order to communicate their new positions regularly. When a node crosses a quadrant boundary, it floods the control message, and the extent of this flooding is dependent on the distance moved by the node with respect to the quadrant boundary. If a node only moves within its quadrant (1000 m × 1000 m), flooding packets are sent out to nodes only within the quadrant. Therefore, since the nodes are moving smoothly with ST, yielding very slow network topology changes, much of the time, the flooding of control packets is quadrant limited compared to when other mobility models are used; hence, the lowest overhead is observed under ST.

Figure 12. Routing overhead of GRP under various mobility models.

Figure 12. Routing overhead of GRP under various mobility models.

5.2.3. RGR

In terms of PDR (Figure 13), the performance of RGR is distinctive from one mobility model to the next. Once again, the best performance is under RWP, followed by EGM, and the worst performance is under RD followed by GM. The PDR here ranges from about 83% to about 92%, thus a range length of about nine percentage points. This range length is between that of AODV and GRP, and it is at a much higher level (from 83%). RWP also brings about a lower delay (Figure 14) compared to the rest of the models. Most of the statistics presented in Table 2 suggest this ranking. The explanation given for the PDR ranking in the case of GRP also holds here. For the delay, we saw with the statistics that RWP presented the highest average number of neighbors and, thus, the shortest path length; which naturally reduces the end-to-end delay.

Figure 13. PDR of reactive-geographic hybrid routing (RGR) under various mobility models.

Figure 13. PDR of reactive-geographic hybrid routing (RGR) under various mobility models.

Figure 14. End-to-end delay of RGR under various mobility models.

Figure 14. End-to-end delay of RGR under various mobility models.

5.2.4. OLSR

The observations made for RGR also apply to OLSR to a certain extent. We see the highest PDR (Figure 15) and the least end-to-end delay (Figure 16) under RWP. RD once again causes the worst PDR. The explanation for this ranking is the same as for AODV, GRP and RGR. The PDR here ranges from about 61% to about 76%, thus a range length of about 15 percentage points. This range length is the same as that of GRP, and it is higher than that of both RGR and AODV.

Figure 15. PDR of optimized link state routing (OLSR) under various mobility models.

Figure 15. PDR of optimized link state routing (OLSR) under various mobility models.

Figure 16. End-to-end delay of OLSR under various mobility models.

Figure 16. End-to-end delay of OLSR under various mobility models.

Based on these observations about the levels and ranges of the PDR, we can conclude that OLSR, a table-driven proactive routing protocol, and GRP, a position-based geographic routing protocol, are both three-times more sensitive than AODV, an on-demand reactive routing protocol, to the changes induced by the mobility models. Moreover, both OLSR and GRP are also about 67% more sensitive than RGR, a hybrid reactive-geographic routing protocol, to the changes induced by the mobility models. It is now clear that AODV is the less sensitive protocol to the mobility models, followed by RGR. OLSR and GRP are the most sensitive. The fact that RGR ranks right between AODV and GRP comes as no surprise given than RGR is in essence a combination of reactive and geographic protocols. Furthermore, GRP, closely followed by OLSR, presents the worst routing performance over all mobility models considered. This feeble performance points out the non-suitability of both position-based geographic and table-driven proactive protocols for UAANETs. The reasons for this are beyond the scope of this paper. In the meantime, RGR presents the best performance of all; and AODV lies in between.

5.2.5. Flooding

When making use of flooding, the PDR (Figure 17) is again the highest under RWP, followed by EGM and GM. RD causes the worst performance, followed by ST. This performance of flooding is closely related to both the partitioning of the network and the network diameter. As can be seen in Table 2, RWP causes the least amount of partitioning (average number of components), followed by EGM and GM. ST and RD show the most partitioning. The same ranking applies to network diameter, with RD showing the highest (worst) diameter. Therefore, and once again, the ranking in PDR performance that we observe here could have been predicted. Furthermore, the PDR for flooding ranges from about 96% to about 99.2%, thus a range length of about three percentage points. This range length is five-times lower than that of both OLSR and GRP, three-times lower than that of RGR and about half that of AODV.

Figure 17. PDR of flooding under various mobility models.

Figure 17. PDR of flooding under various mobility models.

We can see that flooding is much less sensitive than actual routing protocols to the changes induced by the mobility models. However, we are not suggesting that flooding should be used for UAANET. It brings about an unsustainable amount of bandwidth waste, as we have 10-times (as observed in simulations) more transmissions per seconds than routing protocols. We are presenting flooding here for the sole purpose of establishing certain performance upper bounds. Now, we know for example that the upper bound for PDR for routing protocols to tend to is about 99.2% and that changing mobility models will lead to a PDR fluctuation of at least three percentage points.

Table 3 summarizes the PDR of the protocols over different mobility models. The table ultimately shows that the ranking of the routing protocols with regard to PDR does not change with the mobility model used. The PDR for flooding is the upper bound. We have RGR showing the best PDR of all of the protocols, followed by AODV and OLSR. GRP shows the worst performance. This ranking is expected since we know that RGR can be seen as an enhanced version of AODV combined with a form of GRP.

Table 3. Ranking of routing protocols’ PDR (%) over different mobility models.

Protocol	RWP	EGM	ST	GM	RD
Flooding	99.2	98.2	96.8	98.2	96
RGR	92	90	88	86	83
AODV	78	74	72	75	73
OLSR	76	69	65	68	61
GRP	54	48	45	45	40

Table 3. Ranking of routing protocols’ PDR (%) over different mobility models.

Protocol	RWP	EGM	ST	GM	RD
Flooding	99.2	98.2	96.8	98.2	96
RGR	92	90	88	86	83
AODV	78	74	72	75	73
OLSR	76	69	65	68	61
GRP	54	48	45	45	40

6. Conclusions

In this paper, we have conducted a simulation-based study of the impact of mobility patterns on the performance of routing protocols in UAANET in the context of search missions. Similar studies in the literature had a few limitations: lack of diversity in the considered routing protocols, lack of focus on searching missions-applicable mobility models or, most importantly, relatively low mobility that does not apply to UAANET. In an effort to eliminate the abovementioned limitations in our study, we have considered five random entity mobility models applicable to search missions, namely RWP, RD, ST, GM and EGM. Moreover, we considered four distinct routing protocols: AODV, a reactive protocol, OLSR, a proactive protocol, GRP, a geographic protocol, and RGR, a hybrid reactive-geographic protocol. In addition to those four protocols, we also considered simple packet flooding (i.e., no routing strategy) in order to single out the impact of certain mobility models’ properties on the routing protocols and also to establish certain performance upper bounds.

We have established that in UAANET, mobility models do affect the performance of routing protocols individually to almost the same extent as the ranking between the protocols’ performance does not change when we go from one mobility model to the next. By means of protocol-independent metrics, we have shown that this impact of the mobility models can be explained and predicted. We can actually deduct a few rules with regard to this as follows: (i) a higher average number of neighbors coupled with a shorter average path length will lead to a shorter end-to-end delay; (ii) slow network topology fluctuations lead to lower routing overhead; (iii) a small network diameter coupled with a high clustering coefficient bring about a high PDR and shorter delay; (iv) the lower the average number of components, the higher the PDR.

Finally, we have come up with a few conclusions/recommendations that were not drawn in the literature yet, to the best of our knowledge. These conclusions/recommendations provide a benchmark for future simulations of UAANET. Our main conclusions/recommendations are as follows. (i) We have enough reasons to strongly recommend not using the RWP mobility model for UAANET simulations: not only does it make unrealistic assumptions about the trajectory of a UAV, but also it results in poor coverage (the worst among all mobility models); therefore, it would not be suitable for the simulation of a thorough search mission of an entire region. We highly recommend using the EGM model instead, as it best mimics the movement pattern of UAVs. (ii) OLSR, a table-driven proactive routing protocol, and GRP, a position-based geographic routing protocol, are both three-times more sensitive than AODV, an on-demand reactive routing protocol, to the changes induced by the mobility models. (iii) GRP, a position-based geographic routing protocol, closely followed by OLSR, presents the worst routing performance over all of mobility models considered. This feeble performance points out the non-suitability of position-based geographic protocols and table-driven proactive protocols for UAANET. On the other hand, RGR, a reactive-geographic hybrid routing protocol, is best suited for UAANET. (iv) Based on the results of flooding, the upper bound for PDR for routing protocols to tend to is about 99.2%. Moreover, changing mobility models will lead to a PDR fluctuation of at least three percentage points.

In a future work, we will investigate the effect of increased traffic on the routing performance in UAANET. We will simulate various numbers of traffic flows (source-destination pairs) from 1–30 instead of just one, as we do in this paper.