Randomized geographic-based routing with nearly guaranteed delivery for three-dimensional ad hoc network

Abstract

Several routing algorithms have been proposed for efficient routing in mobile ad hoc networks, most of them consider mobile nodes embedded in two-dimensional environments. However, in reality, these networks are embedded in three-dimensional environments. Usually, two-dimensional routing algorithms have several assumptions that are not valid for three-dimensional spaces. In this article, we propose four different randomized geographic-based routing algorithms that have the following properties: (1) nearly guaranteed delivery rate, by using randomize route to overcome local minimum problems; (2) low overhead, by extracting a virtual backbone of the network and then conducting the routing algorithms over the extracted backbone to decrease the search space; (3) low path dilation, by hybridizing the new algorithms with progress-based routing which have very low path dilation; and (4) works in three-dimensional environment. The first algorithm 3DRanDom chooses the next neighbor randomly from a dominating set of the network (extracted locally). The second algorithm 3DRanDomProb extracts a dominating set and sends to one of the resulted neighbors randomly with more probability for the nodes closer to the destination. The third algorithm G_3DRanDomProb tries to progress as much as possible to the destination, if the progress is not possible, the algorithm switches to 3DRanDomProb. The fourth algorithm G_3DRanDomProb_G uses progress-based routing as much as possible, then it switches to 3DRanDomProb until it overcomes the local minimum problem and then goes back to progress-based routing. We show experimentally that these hybrid randomized routing algorithms on three-dimensional mobile ad hoc networks can achieve nearly guaranteed delivery while discovering routes significantly closer in length to the shortest path and with low overhead.

Keywords

Localized routing Dominating set Progress-based routing Simulation

Introduction

Mobile ad hoc networks (MANETs) consist of a set of wireless autonomous mobile nodes that can communicate with each other without having any physical infrastructure. A node in the network can communicate directly with all other nodes within its transmission range.^1,2 If a node wishes to transmit a packet to another node outside the transmission range, then a multi-hop routing protocol is needed. Many routing protocols have been proposed for MANETs, each is based on different assumptions and philosophies. MANETs routing protocols can be classified into two core basic categories:³topology-based routing^4–7 and geographic-based routing.^8–11 Topology-based routing protocols make their judgments about routing packets based on the information about the whole network. It can be further classified as proactive and reactive; protective protocols (i.e. destination-sequenced distance vector (DSDV)¹² or optimized link state routing (OLSR)¹³) store and maintain complete up-to-date routing table about each node in network all the time. They always have ready routes from any source to any destination at any time, but they suffer from the huge overhead to keep the routing table up-to-date especially when the nodes are moving frequently.¹⁴ On the other hand, in reactive protocols (i.e. dynamic source routing (DSR)¹⁵ or ad hoc on-demand distance vector (AODV)¹⁶), a node updates its routing table whenever a route is required from that node. This may be very expensive to search the whole network for the optimum route and it may add a delay to the routing process. Topology-based routing can generally find the shortest path between any two nodes in terms of the number of hops. However, it can be difficult for these routing methods to handle large MANETs.

In contrast, topology-based routing needs a global view about the whole network. Geographic-based routing (also referred as position-based routing) protocols use pure local location information about neighbor nodes positions to take routing decisions. Therefore, geographic-based routing protocols eliminate the high overhead by topology-based routing, making them simple, efficient, and scalable for big ad hoc and sensor networks.

In general, a geographic-based routing algorithm has the following assumptions:

Each mobile host in MANET knows its geometric coordinates. This can be obtained through a Global Positioning System (GPS) receiver or other such mechanisms.^17,18

Each mobile host has the means to determine the geometric coordinates of every other mobile host within its transmission range; this can be optioned using a periodical broadcasted hello messages where information about the mobile host like geographical coordinates are usually embedded in these messages.

The source node knows the geometric location of the packet destinations, which can be obtained by location services^19,20 or by receiving the location from a previous packet from that node. The source node adds this location to the packet header. Once a node receives a packet, it can learn the location of the destination.

There is no need for any node to store routing tables. Nodes only maintain the information about their neighbors at most a fixed number of hops (usually one hop) away.

According to the nature of packet forwarding, geographic-based routing can be divided into two types: progress-based forwarding and randomized-based forwarding. In progress-based routing, the node having a packet forwards it to one of its neighbors according to some heuristic, usually the neighbor closer to the destination, Greedy,²¹ Compass,²² and Most-Forward routing²³ algorithms are considered as progress-based routing algorithms, see section “Preliminaries.” Simple versions of these algorithms have been proposed in Abdallah et al.^24,25 The main drawback of the above progress-based routing is the unacceptable low delivery rate because they suffer from the local minimum phenomenon, in which a packet may get stuck at a node, termed a local minimum, which does not have a neighbor that makes progress to the destination, even though the source and the destination are connected in the network. This problem has been solved in two ways:

Using randomized-based routing algorithms, where the next node is chosen randomly from the set of neighbors, for example: Random Progress,²⁶ where a node chooses randomly one of the neighbors that is closer to the destination and forwards the packet. In the AB random algorithm,²⁴ a node holding the packet forwards it randomly to one of two candidate neighbors that are chosen according to some progress-based heuristic.

Using face routing or perimeter routing,^27,28 where each node locally uses their geometric locations to extract a planar sub-graph, the algorithm traverses in a counter clockwise the faces of the sub-graph that cross the virtual line between the source and the destination; the algorithm switches between faces when the packet reaches an edge that crosses the virtual line between the source and the destination at a point closer to the destination than any previously known intersection point. It has been proved that face routing has a guaranteed packet delivery in two-dimensional (2D) spaces, but this algorithm fails to work with three-dimensional (3D) space because it is not possible to extract a straight-line planner sub-graph in 3D.

Another family of MANET routing is flooding-based routing, when a packet reaches a node, it forwards that packet to all its neighbors in the direction to the destination. This can usually find the shortest path between two nodes. However, it can be difficult for these routing protocols to work with large MANETs because of the huge traffic and overhead that can be created around the network. Distance routing effect algorithm for mobility (DREAM)²⁹ and the geocasting-based location-aided routing (LAR)³⁰ are some examples on this strategy. A 3D version of a hybrid routing algorithm that combines randomized routing with flooding-based routing has been proposed in Abdallah et al.²⁵

Most of the geographic-based routing algorithms have been proposed and tested in 2D space. However, these algorithms are not valid in real-world applications, where the networks are embedded in 3D spaces. For example, networks that deployed in buildings with multiple floors and underwater sensor networks need 3D routing algorithms. Some algorithms like 2D Greedy and 2D LAR can be applied easily on 3D environment, but they suffer from the low delivery rate and high overhead. Other algorithms which have high delivery rate and low overhead cannot be used in 3D environment like face routing. Thus, we propose four different randomized 3D geographic-based routing algorithms that have the following properties:

Delivery rate is nearly guaranteed;

Low overhead;

Low path dilation;

Works in 3D environment.

The first algorithm 3DRanDom chooses the next neighbor from a dominating set of the network (extracted locally). The second algorithm 3DRanDomProb extracts a dominating set and sends to one of the resulted neighbors randomly with more probability for the nodes closer to the destination. The third algorithm G_3DRanDomProb tries to progress as much as possible to the destination, if it is not possible, the algorithm switches to 3DRanDomProb. The fourth algorithm G_3DRanDomProb_G uses progress-based routing as much as possible, then it switches to 3DRanDomProb until it overcomes the local minimum problem and then it goes back to progress-based routing. We show experimentally that these hybrid randomized routing algorithms on 3D MANETs can achieve nearly guaranteed delivery while discovering routes close in length to the shortest path and with low overhead.

The rest of this article is organized as follows: in the next section, we define the network model and survey some of the backbone algorithms. We present the related routing algorithm in section “Preliminaries” as well. In section “Proposed routing algorithms,” we give a detailed description of the new routing algorithms. We present simulation results to prove the much enhanced performance of the proposed methods in comparison with existing techniques in section “Empirical results.” Section “Conclusion” summarizes our results.

Preliminaries

The communication network model

Consider a set of n wireless mobile nodes. Each mobile node has a geometric location and a transmission range equal to r (represented as a sphere volume of radius r). MANET in space is usually modeled using unit ball graph (UBG). UBG vertices are the set of mobile host and its edges are straight-line segments, two nodes (u,v) are connected by an edge (undirected) if the Euclidean distance between the points u and v is less than or equal to r. The routing task is to find a path in UBG from any source node s to any destination node d. At each node, the decision of how to choose the next node for the packet is based on local information. Evaluating the new algorithms is done through the following performance measures:

Delivery rate: the percentage of times that the algorithm succeeds in delivering its packet.

Path dilation: the average ratio of the length of the path returned by the algorithm to the length of the shortest path in the UBG.

Overhead: the average ratio of number of nodes participate in the routing process to the number of hops in the shortest path.

Backbone algorithms

Many routing algorithms try to decrease the choices for the next node during the routing process by extracting a connected dominating set. A connected dominating set of a graph is subset of nodes such that each node in the graph is either in the subset or adjacent to at least one node in that subset. During the routing process, a node uses only the dominator nodes (nodes of the connected dominating set). All other nodes communicate via a neighbor in the dominating set. The efficiency of such routing algorithms depends largely on the process of finding these dominating set and the size of the corresponding connected dominating set. In the following, we discuss a couple of the main local algorithms to extract a connected dominating set in 3D space:

Alzoubi et al.^31,32 connected dominating set: assumes that each node has a unique ID. The dominating set algorithm is locally started at a node which needs to know its dominator. If the node ID is less than all neighbors IDs, it considers itself as dominator. Obviously, all neighbors remove themselves from the consideration of the dominating set. Each node repeats the same process, such that the resulting set is a non-connected dominating set. To get a connected dominating set, a second algorithm starts as follows: each node in the resulted set uses local information about UBG, up to three hops away to add gateway nodes to the set until the set becomes a connected dominating set. It has been proved that this algorithm can create a connected dominating set of UBG locally without having information about the whole back end UBG. This algorithm works with 3D environment without update.

Class-based connected dominating set (CBCDS):³³ this algorithm has been proposed specifically for 3D graphs. Similar to Alzoubi algorithm, CBCDS starts locally at a node which needs to know its dominator. It consists of two phases: first phase, using a virtual space tilling system (see Figure 1), each node uses its geometric location to determine its class number; it finds the class number of neighbors as well. Node u adds itself to dominating set if one of the following conditions is true:

u is of class 1 (tile id = 1) and closest to the center of its tile.

u of class other than 1, closest to the center of its tile and some nodes in the same tile have no neighbors of lower class number.

u is of class other than 1, closest to the center of its tile, no nodes in the same tile without neighbors of lower class id, and u is not dominated by a neighbor of lower class id.

Figure 1.

Tilling system used in CBCDS.

The resulted graph is a non-connected dominating set. In the second phase of the algorithm, each node in the non-connected dominating set uses local information about UBG, up to three hops away to add gateway nodes to the set until the set becomes a connected dominating set. It has been proved that the construction time is constant.

Related routing algorithms

Routing protocols for MANETs depend on several issues, for example, the network topology, the information available at each node during routing process, and the characteristics of backbone network that could be used to define a heuristic to find a route efficiently. In this subsection, we review some representative geographic-based routing algorithms that are closely related to the new proposed algorithms:

3DGreedy routing.²¹ When a node u receives a packet and wants to forward it to the destination. It evaluates the Euclidean distance between each neighbor and the destination and then it chooses the closest neighbor to the destination. The same procedure is repeated at each intermediate node. If the packet reaches a local minimum, then the algorithm fails (see Figure 2).

3DCompass routing.²² In this algorithm, the node holding the packet (u) forwards it to one of its neighbors (v) that creates the minimum angle (∠vud), where d is the destination. The same procedure is repeated at each intermediate node. If the packet reaches a local minimum, then the algorithm fails (see Figure 2).

3DLAR algorithm.^25,30 The current node holding the packet forwards it to all neighbors that are located in a cube as follows: using the available information of the destination node d, the source node computes the expected zone for the destination (a sphere centered at d with radius equal to $v * (t_{1} - t_{0})$ , where $t_{1}$ is the current time, $t_{0}$ is the last time stamp known about the destination position, and v is the maximum speed known about the destination node). The cube longest diagonal starts at the source node and ends at the surface of the expected zone. This procedure is done repeatedly at each node to receive a copy of the packet. Obviously, this may increase the overhead around each node in the network and the whole network may get congested with so many copies of the same packets.

3DABLAR algorithm.²⁵ In this algorithm, let the node holding the packet is (u), the destination node is (d), and the closest neighbor to d is (v). The current node u defines a plane $PL 1$ that passes through the nodes $(u, v, d)$ and defines another plane $PL 2$ that is perpendicular to $PL 1$ and the intersection line between the two planes is the line cd. Then, u uses greedy algorithm to select one neighbor from each side of the four regions that result for the intersection between $Pln 1$ and $Pln 2$ . The current node then forwards the packet to each neighbor from these four neighbors if they located inside the flooding area of 3DLAR algorithm.

Figure 2.

Let the node s has a packet and need to send it to node d, 3DGreedy choose b as the next node, and 3DCompass choose c as the next node.

Proposed routing algorithms

Progress-based routing algorithms (3DGreedy and 3DCompass) usually find a path close to the shortest path, but they suffer from the unacceptable low delivery rate. On the other hand, the available randomized routing algorithms (3DABLAR algorithm and random progress) usually increase the delivery rate but with a very long path dilation. To benefit from the advantage of both protocols, we tried to use a backbone sub-graph using CBCDS to decrease the search space and decrease number of loops in randomized routing algorithms. We have four general approaches to hybridizing progress-based routing with randomized routing. The first algorithm (3DRanDom), a connected dominating set is extracted locally using CBCDS protocol and then the current node holding the packet chooses randomly one of the neighbors that belong to the connected dominating set, the same procedure is repeated at each intermediate node until the packet reaches the destination or the hop count of the packet exceed a specific threshold, see Figure 3. Table 1 shows a comparison between the new proposed algorithms and other known routing algorithms.

Figure 3.

3DRanDom routing is done over CBCDS.

Table 1.

Comparison between the new proposed algorithms with other routing algorithms.

	Backbone graph	Randomized algorithm	Overcome local minimum problem	Forwarding process
3DGreedy	UBG	No	No	One neighbor
3DLAR	UBG	No	No effect	All neighbors
Random progress	UBG	Yes	Yes	One neighbor
3DRanDom	Subgraph of UBG	Yes	Yes	One neighbor
3DRanDomProb	Subgraph of UBG	Yes	Yes	One neighbor
G_3DRanDomProb	Subgraph of UBG	Hybrid	Yes	One neighbor
G_3DRanDomProb_G	Subgraph of UBG	Hybrid	Yes	One neighbor

Our second algorithm (3DRanDomProb) uses similar procedure to the previous algorithm where the nodes extract a connected dominating set. In 3DRanDomProb the next node is chosen randomly but with more probability to the node that makes the most progress to the destination. As in 3DRanDom, each intermediate node does the same procedure until the packet reaches the destination or the hop count of the packet exceeds a specific threshold (see Algorithm 1 for more details).

Algorithm 1: 3DRanDomProb(c, d, HC)
// The source node starts by calling 3DRanDomProb (s, d, 0).
// Consider each packet has the following parameters c, d, HC, c is the node holding the packet, d is the destination node, and HC is the current hop count of the packet.
// TH is a constant global threshold (depend on the network size).
begin
ifc = dthen /* packet has reach the destination */
return true
else if HC > THthen /* threshold has been reached */
// Kill the packet and do nothing /* this path fails */
else
c applies CBCDS(G) on its neighbors
Let L(c) is the set of neighbors c that belong to CBCDS(G)
fori← 1 tonumber of neighbors in L(c) do
find the Euclidean distance the edge $(\vec{id})$ , $dist (\vec{id})$
$pro p_{i} = \frac{dist (\vec{id})}{\sum_{j = 1}^{k} d ist (\vec{jd})}$ /* where k is the size of L(c) */
Send the packet to one neighbor through the edge $\vec{ci}$ with probability prop_i (3DRanDomProb (i, d, HC + 1))

The third algorithm (G_3DRanDomProb) tries to benefit from the low path dilation of progress-based routing algorithm using 3DGreedy and 3DCompass as much as possible. If the packet reaches a node that cannot progress to the destination, it switches to 3DRanDomProb to overcome the local minimum, see Algorithm 2.

Algorithm 2: G_3DRanDomProb (c, d)
// The source node starts by calling G_3DRanDomProb(s, d)
// Consider c is the current node holding the packet and d is the destination node
begin
Let L(c) is the set of neighbors c that belong to UBG(G)
fori← 1 tonumber of neighbors in L(c) do
find the Euclidean distance the edge $(\vec{id})$ , $dist (\vec{id})$
let the neighbor m has the shortest distance $dist (\vec{md})$
if $dist (\vec{md}) \leq dist (\vec{cd})$ then /* Can progress to d*/
c forward the packet to the node m
c←m
ifc = dthen /* packet arrives to the destination */
return
else /* continue with 3DGreedy */
G_3DRanDomProb(c, d)
else /* No more progress to d (Local minimum) */
3DRanDomProb (c, d, 0) /* Call the algorithm 1 to pass the Local minimum */

The fourth algorithm (G_3DRanDomProb_G) works as follows, it uses 3DGreedy or 3DCompass on the original UBG as much as possible, and when the packet reaches a local minimum, the algorithm extracts a connected dominating set and tries 3DGreedy or 3DCompass, if the local minimum still there, the algorithm switches to 3DRanDom until it reaches a node closer than the local minimum node to the destination. Then, 3DGreedy or 3DCompass is used again, see Figure 4 and Algorithm 3 for details of the algorithm.

Figure 4.

G_3DRanDomProb_G routing process, to find a route from S to D. (a) 3DGreedy is used S→Y→B, B is a local minimum; (b) the nodes extract CBCDS and use 3DRanDomProb until it reach the node W. W is closer to D than B and (c) Go back to 3DGreedy.

Algorithm 3: G_3DRanDomProb_G (c, d)
// The source node starts by calling G_3DRanDomProb(s, d)
// Consider c is the current node holding the packet and d is the destination node
begin
Let L (c) is the set of neighbors c that belong to UBG(G)
fori← 1 tonumber of neighbors in L (c) do
find the Euclidean distance the edge $(\vec{id})$ , $dist (\vec{id})$
let the neighbor m has the shortest distance $dist (\vec{md})$
if $dist (\vec{md}) \leq dist (\vec{cd})$ then * /* Can progress to d/
c forward the packet to the node m
c←m
ifc = dthen /* packet arrives to the destination */
return
else /* continue with 3DGreedy */
G_3DRanDomProb(c, d)_G
else /* No more progress to d (Local minimum) */
$temp \leftarrow dist (\vec{cd})$
HC = 0
repeat
c applies CBCDS(G) on its neighbors
Let L (c) is the set of neighbors c that belong to CBCDS(G)
fori← 1 tonumber of neighbors in L(c) do
find the Euclidean distance the edge $\vec{id}$ , $dist (\vec{id})$
$pro p_{i} = \frac{dist (\vec{id})}{\sum_{j = 1}^{k} d ist (\vec{jd})}$ /* k is the size of L(c) */
Send the packet to one neighbor through the edge $\vec{ci}$ with probability $pro p_{i}$
$HC = HC + 1$
c←i
until $c = d$ or $dist (\vec{id}) < temp$ or HC > TH
ifc = dthen /* packet arrives to the destination */
return
else if $(dist (\vec{id}) < temp)$ then /* go back to 3DGreedy */
G_3DRanDomProb(c, d)_G
else /* passed the threshold without passing the local minimum */ //
Kill the packet and do nothing /* this path fails */

Empirical results

In the following, we implemented 3DGreedy, 3DLAR, and Random progress to compare them with the new proposed routing algorithms. To evaluate the relative performance of these algorithms, we will consider their packet delivery rates, path dilations, and the total overhead. We first describe our simulation environment and then describe and interpret our results.

Simulation environment

In the simulation experiments, we consider a set of nodes that are randomly distributed in the 3D space. The parameters like node density, transmission range, and threshold are determined experimentally in Fevens et al.⁹ and Kuhn et al.³⁴ In the simulation experiments, a set S of n points (where $n \in 100, 150, 200, 250, 300$ ) is randomly generated on a cube of side length equal to $100 m$ . For the transmission range, it has been set to 25 m. The threshold is set to be equal to the number of nodes. After generating $G = UBG (S)$ , if the resulted UBG is not connected, we calculate the largest connected component (LCC). We randomly choose a source node s and a destination node d from LCC. All routing algorithms are applied in turn on the calculated LCC.

Clearly, an algorithm succeeds if a path to the destination is found. Progress-based routing (3DGreedy) are deemed to fail if the packet reaches a local minimum, while the randomized algorithms are considered to fail when the number of hops in the path computed so far exceeds a threshold. To compute the packet delivery rate, we run all algorithms on 100 random graphs and the percentage of successful deliveries determined. To compute an average packet delivery rate, the packet delivery rate is determined 100 times and an average taken. Additionally, out of the 100 × 100 runs used to compute the average packet delivery rate, the average path (hop count) dilation of successful paths is computed. We also calculated from the 10,000 runs the average overhead.

Discussion of results

A comparison between the new proposed routing algorithms and the other related algorithms in terms of delivery rate is presented in Table 2. The path dilation comparison is presented in Table 3. And finally the overhead of all algorithms is shown in Table 4.

Table 2.

Average packet delivery rate.

Algorithms	n = 100	n = 150	n = 200	n = 250	n = 300
3DGreedy	60	71	89	100	100
3DLAR	100	100	100	100	100
Random progress	77	83	90	95	99
3DRanDom	80	81	85	91	90
3DRanDomProb	88	95	97	100	100
(G)_3DRanDomProb	95	98	100	100	100
(G)_3DRanDomProb_(G)	97	97	100	100	100

Table 3.

Average path dilation.

Algorithms	n = 100	n = 150	n = 200	n = 250	n = 300
3DGreedy	1.3	1.28	1.2	1.12	1.06
3DLAR	1.22	1.12	1.02	1.01	1.01
Random progress	2.1	2.78	3.31	3.54	3.87
3DRanDom	2.23	2.42	2.58	2.4	2.8
3DRanDomProb	1.7	1.73	1.81	1.77	1.85
(G)_3DRanDomProb	1.57	1.48	1.37	1.12	1.06
(G)_3DRanDomProb_(G)	1.42	1.32	1.28	1.12	1.06

Table 4.

Average overhead.

Algorithms	n = 100	n = 150	n = 200	n = 250	n = 300
3DGreedy	1.3	1.28	1.2	1.12	1.06
3DLAR	3.5	5.25	9.5	12	15
Random progress	2.1	2.78	3.31	3.54	3.87
3DRanDom	2.23	2.42	2.58	2.4	2.8
3DRanDomProb	1.7	1.73	1.81	1.77	1.85
(G)_3DRanDomProb	1.57	1.48	1.37	1.12	1.06
(G)_3DRanDomProb_(G)	1.42	1.32	1.28	1.12	1.06

3DLAR has the highest delivery rate, always 100% regardless of the network density. This is due to the flooding used in 3DLAR. If the packet did not arrive to the destination at the first stages, 3DLAR increases the size of the expected range and try again until the packet reaches the destination. This algorithm has a path dilation close to the shortest path as well. But from Table 4, this algorithm has the highest overhead because there are many nodes that receive and forward each packet without being part of the discovered route. Thus, this algorithm is not really usable with large and busy networks.

3DGreedy has the lowest delivery rate less than 75% at regular network density. The low delivery rate can be explained by the local minimum problem, 3DGreedy fails, when the packet reaches a node that has no neighbor closer to the destination than itself. As the network density increases, the delivery rate of 3DGreedy increases as well because there will be less chance for the packet to face local minimum. Because 3DGreedy sends the packet to one neighbor and tries to progress as much as possible to the destination, the path dilation is usually close to the shortest path and this is clear from the results in Table 3.

Random progress delivery rate is more than 3DGreedy because it overcomes the local minimum problem. Still the delivery rate is not acceptable for network with low density. From Table 2, as the number of nodes increases, the delivery rate increases as well because the threshold equals to the number of nodes. Table 3 shows that the path dilation of this algorithm is the highest between all randomized routing algorithms.

Our first proposed routing algorithm 3DRanDom has higher delivery rate more than 3DGreedy and Random progress and it has lower path dilation than Random progress as well. We can explain these results as follows: our algorithm extracts a connected domination set to do the routing process over the resulted backbone. Thus, each node has a lower number of options when it chooses the next node, therefore the right path will be chosen much faster.

In 3DRanDomProb, we tried to give more chance for the nodes that make progress to the destination in the extracted connected dominating set; 3DRanDomProb chooses the next neighbor with more probability to the nodes that make faster progress to the destination. Thus, Tables 2 and 3 show that 3DRanDomProb has a higher delivery rate and less path dilation than 3DRanDom.

G_3DRanDomProb has the second best delivery rate and the second lowest path dilation out of all randomized routing algorithms. To decrease the path dilation, G_3DRanDomProb tried to use the advantage of the low path dilation of 3DGreedy as much as possible. When there is a local minimum, it changes to the random part to pass the local minimum, thus higher delivery rate. From the results, as the density for the network increases, the algorithm results become exactly like 3DGreedy. This is due to the fact that 3DGreedy does not fail at all when the number of nodes equal to 250 and 300, which means that G_3DRanDomProb does not go to the random part at all.

G_3DRanDomProb_G outperforms all other randomized and deterministic non-flooding routing algorithms in terms of delivery rate, it has nearly guaranteed delivery in all network densities. It also outperforms all other randomized algorithms in terms of the path dilation and overall overhead. As G_3DRanDomProb, this algorithm used the advantage of 3DGreedy as much as possible and it uses the randomize phase for only a couple of steps until the local minimum is passed and the it goes back to 3DGreedy to get more benefits from the advantage of all algorithms.

Conclusion

In this article, we present a family of hybrid 3D routing algorithms for MANETs. The new algorithms are based on idea of benefiting from the low path dilation of progress-based routing 3DGreedy and the guarantee delivery of randomized routing algorithms. They also use the idea of routing over backbone network to minimize loops in the random phases. We show experimentally that these hybrid randomized routing algorithms on 3D MANETs can achieve nearly guaranteed delivery while discovering routes significantly closer in length to the shortest path and with low overhead.

Footnotes

Academic Editor: Euisin Lee

Declaration of conflicting interests

The author(s) declared no potential conflicts of interest with respect to the research, authorship, and/or publication of this article.

Funding

The author(s) received no financial support for the research, authorship, and/or publication of this article.

References

Cadger

Curran

Santos

. A survey of geographical routing in wireless ad-hoc networks. IEEE Commun Surv Tutor 2013; 15(2): 621–653.

Huang

Yin

Luo

. Three-dimensional geographic routing in wireless mobile ad hoc and sensor networks. IEEE Network 2016; 30(2): 82–90.

Mauve

Widmer

Hartenstein

A survey of position-based routing in mobile ad-hoc networks. IEEE Netw Mag 2001; 15(6): 30–39.

Basagni

Chlamtac

Syrotiuk

Dynamic source routing for ad hoc networks using the global positioning system. In Proceedings of the IEEE wireless communications and networking conference (WCNC’99), New Orleans, LA, 21–24 September 1999, pp.21–24. New York: IEEE.

Rodoplu

Meng

Minimum energy mobile wireless networks. IEEE J Sel Area Commun 1999; 17(8): 1333–1344.

Royer

Toh

. A review of current routing protocols for ad hoc mobile wireless networks. IEEE Pers Commun 1999; 6(4): 46–55.

Stojmenovic

. Location updates for efficient routing in ad hoc networks. In: Stojmenovic

(ed.) Handbook on wireless networks and mobile computing. New York: John Wiley & Sons, 2002, pp.451–471.

Barriere

Fraigniaud

Narayanan

. Robust position-based routing in wireless ad hoc networks with irregular transmission ranges. Wirel Commun Mob Comput 2003; 3(2): 141–153.

Fevens

Abdallah

Bennani

Randomized ab-face-ab routing algorithms in mobile ad hoc network. In: Proceedings of 4th international conference on AD-HOC networks and wireless (vol. 3738 of LNCS), Cancun, Mexico, 6–8 October 2005, pp.43–56. Berlin: Springer.

10.

Giordano

Stojmenovic

Blazevic

Position based routing algorithms for ad hoc networks for ad hoc networks: a taxonomy. In: Cheng

Huang

(eds) Ad hoc wireless networking. Dordrecht: Kluwer Academic Publishers, 2003, pp.103–136.

11.

Fevens

Liu

Abdallah

. Hybrid position-based routing algorithms for 3-d mobile ad hoc networks. In: Proceedings of the 4th international conference on mobile ad-hoc and sensor networks (MSN), China, 10–12 December 2008, pp.177–186. New York: IEEE.

12.

Perkins

Bhagwat

. Highly dynamic destination sequenced distance-vector routing (DSDV) for mobile computers. In: Proceedings of the SIGCOMM, conference on communications architectures, protocols and applications, London, 31 August–2 September 1994, pp.234–244. New York: ACM.

13.

Clausen

Jacquet

Optimized link state routing protocol (OLSR) (RFC 3626). IETF Network Working Group, 2003.

14.

Chlamtac

Conti

Liu

Mobile ad hoc networking: imperative and challenges. Ad Hoc Netw 2003; 1(1): 13–64.

15.

Johnson

Malts

Chapter 5: dynamic source routing in ad hoc wireless networks. In: Imielinski

Korth

(eds.) Mobile computing. Dordrecht: Kluwer Academic Publishers, 1996, pp.153–181.

16.

Perkins

Royer

Ad hoc on-demand distance vector routing. In: Proceedings of the 2nd IEEE workshop on mobile computing system and application (WMCSA), San Juan, 25–26 February 1999, pp.90–100. Washington, DC: IEEE.

17.

Capkun

Hamdi

Hubaux

JP.

Gps-free positioning in mobile ad-hoc networks. Cluster Comput 2002; 5(2): 118–124.

18.

Kaplan

Understanding GPS. Norwood, MA: Artech house, 1996.

19.

Hightower

Borriello

Location systems for ubiquitous computing. Computer 2001; 34(8): 57–66.

20.

Jannotti

De Couto

. A scalable location service for geographic ad-hoc routing. In: Proceedings of the 6th ACM international conference on mobile computing and networking (MobiCom), Boston, MA, 6–11 August 2000, pp.120–130. New York: ACM.

21.

Chvatal

A greedy heuristic for the set covering problem. Math Oper Res 1979; 4: 233–235.

22.

Kranakis

Singh

Urrutia

. Compass routing on geometric networks. In: Proceedings of the 11th Canadian conference on computational geometry (CCCG ’99), Vancouver, BC, Canada, August 1999, pp.51–54.

23.

Takagi

Kleinrock

Optimal transmission ranges for randomly distributed packet radio terminals. IEEE T Commun 1984; 32(3): 246–257.

24.

Abdallah

Fevens

Opatrny

. Randomized 3-d position-based routing algorithm for ad-hoc networks. In: Proceedings of the 3rd annual international conference on mobile and ubiquitous systems: networks and services (MOBIQUITOUS), San Jose, CA, 17–21 July 2006, pp.1–8. New York: IEEE.

25.

Abdallah

Fevens

Opatrny

Hybrid position-based 3d routing algorithms with partial flooding. In: Proceedings of the Canadian conference on electrical and computer engineering, Ottawa, ON, Canada, 7–10 May 2006, pp.1135–1138. IEEE.

26.

Nelson

Kleinrock

. The spatial capacity of a slotted aloha multihop packet radio network with capture. IEEE T Commun 1984; 32(6): 684–694.

27.

Bose

Morin

Stojmenovic

. Routing with guaranteed delivery in ad hoc wireless networks. Wirel Netw 2001; 7(6): 609–616.

28.

Karp

Kung

. GPSR: greedy perimeter stateless routing for wireless net-works. In: Proceedings of the 6th ACM/IEEE conference on mobile computing and networking (MobiCom 2000), Boston, MA, 6–11 August 2000, pp.243–254. New York: ACM.

29.

Basagni

Chlamtac

Syrotiuk

. A distance routing effect algorithm for mobility (DREAM). In: Proceedings of the 4th annual ACM/IEEE international conference on mobile computing and networking (MobiCom), Dallas, TX, 25–30 October 1998, pp.76–84. New York: ACM.

30.

Vaidya

Location-aided routing (LAR) in mobile ad hoc networks. ACM Baltzer Wirel Netw (WINET) 2000; 6(4): 307–321.

31.

Alzoubi

Wan

Frieder

Distributed heuristics for connected dominating sets in wireless ad hoc networks. J Commun Netw 2002; 4(1): 141–149.

32.

Alzoubi

Wan

Frieder

. Message-optimal connected-dominating-set construction for routing in mobile ad hoc networks. In: Proceedings of the 3rd ACM international symposium mobile ad hoc networking and computing (MobiHoc 02), Lausanne, 9–11 June 2002, pp.157–164. New York: ACM.

33.

Abdallah

Fevens

Opatrny

3D local algorithm for dominating sets of unit disk graphs. Ad Hoc Sens Wirel Netw 2013; 19(1–2): 21–41.

34.

Kuhn

Wattenhofer

Zollinger

Ad-hoc networks beyond unit disk graphs. In: Proceedings of the 2003 joint workshop on the foundation of mobile computing (DIALM-POMC), San Diego, CA, 19 September 2003, pp.69–78. New York: ACM.