High delivery rate position-based routing algorithms for 3D ad hoc networks

Abstract

Position-based routing algorithms use the geographic position of the nodes in a network to make the forwarding decisions. Recent research in this field primarily addresses such routing algorithms in two dimensional (2D) space. However, in real applications, nodes may be distributed in three dimensional (3D) environments. In this paper, we propose several randomized position-based routing algorithms and their combination with restricted directional flooding-based algorithms for routing in 3D environments. The first group of algorithms AB3D are extensions of previous randomized routing algorithms from 2D space to 3D space. The second group ABLAR chooses m neighbors according to a space-partition heuristic and forwards the message to all these nodes. The third group T-ABLAR-T uses progress-based routing until a local minimum is reached. The algorithm then switches to ABLAR for one step after which the algorithm switches back to the progress-based algorithm again. The fourth group AB3D-ABLAR uses an algorithm from the AB3D group until a threshold is passed in terms of number of hops. The algorithm then switches to an ABLAR algorithm. The algorithms are evaluated and compared with current routing algorithms. The simulation results on unit disk graphs (UDG) show a significant improvement in delivery rate (up to 99%) and a large reduction of the traffic.

Introduction

Mobile ad hoc networks (MANETs) consist of wireless mobile hosts that communicate with each other in the absence of a fixed infrastructure. Two nodes can communicate in a bidirectional manner if and only if the distance between them is at most the minimum of their transmission ranges. If one node wishes to communicate with another node outside its transmission range, multi-hop routing is used utilizing intermediate communicating nodes. Since mobile ad hoc networks may change their topology frequently and without notice, routing in such networks is a challenging problem. Mauve et al. [28] classified the routing algorithms in MANETs as being of two basic types: topology-based [34], [17], [32], [33], [36] and position-based [3], [13], [28].

Topology-based routing algorithms use the information about the links in the network to perform packet forwarding. These algorithms can be classified as proactive or reactive. In a proactive protocol, i.e. DSDV [30] or OLSR [8], a complete routing table is used at each node which has to be updated when any node moves. The main drawback of this approach is the unacceptable overhead when data traffic is lower than the mobility rate. In a reactive approach, i.e. DSR [19] or AODV [31], the nodes maintain only the routes that are currently in use. In this strategy, if the route is not available, the current node holding the packet issues a destination search request which is performed by flooding a short control message. Although reactive protocols discover routes only when they are needed, these protocols may still generate a huge amount of traffic when the network changes frequently [7].

Topology-based routing can usually find the shortest path, in terms of the number of hops, between a pair of nodes. However, it can be difficult for these routing methods to handle large ad hoc networks with many nodes or with frequently changing connectivity among nodes [16].

Position-based routing algorithms or online routing [5], [28] use the position information to make routing decisions. In general, a position-based routing algorithm has the following characteristics:

• Each node in the network has the means to determine their coordinates. This can be obtained through a GPS receiver, or another such mechanism [35], [22].

• Each node can find the position of a node with which it wishes to communicate by making use of a location service [14], [27], receiving the position from a previous packet from that node, or some other mechanism.

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

• A node in the network knows the position of the nodes with which it can communicate directly, simply by using a periodical broadcast beacon containing information such as node identifier and geographic coordinates.

• The routing decision at each hop in the route can be made based on the locations of the current node, its neighbors’ nodes and the destination node.

In this paper, we assume that the nodes are static during the routing process. This is a practical assumption because most of the time the speed of the nodes is slower than the speed of the radio signal (wireless transmission) between any two nodes.

Position-based routing is scalable to a large number of network nodes and is efficient when nodes move frequently. There are two main types of packet-forwarding strategies for position-based routing [28], one neighbor forwarding and restricted directional flooding.

With one neighbor forwarding, the algorithm forwards the packet in every step to one of its neighbors. We can consider two types of algorithms, progress-based and randomized progress-based routing algorithms.

With progress-based routing algorithms, the current node (the node holding the packet) forwards the packet at every step to one of its neighbors that makes progress to the destination. Greedy [11], Compass [25], NFP [15] and Nearest Closer [38] belong to the progress-based strategy. Progress-based routing methods suffer from the so-called 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.

Randomized progress-based routing algorithms try to solve the local minimum problem described above by choosing the next node randomly from a subset of the current node’s neighbors. In the Random Progress Method [29], the current node forwards the packet to a node randomly chosen from the neighbors that makes progress to the destination. In Random-Compass [5], a randomized version of Compass is used. In the AB [10] algorithm the current node forwards the packet randomly, using a probability distribution, to one of two candidate neighbors that are chosen according to some progress-based heuristic, see Section 3.

In restricted directional flooding, the node may forward the packet to more than one of the neighbors that are located closer to the destination than the forwarding node itself. Distance Routing Effect Algorithm for Mobility (DREAM) [4] and the geocasting based Location-Aided Routing (LAR) [24] are examples of this strategy.

In this paper, several routing algorithms are proposed which combine randomized progress-based routing with restricted directional flooding algorithms for routing in 3D environments. The first group proposed AB3D are extensions of the randomized AB routing algorithms from 2D space to 3D space. The second group ABLAR, a combination between the AB algorithms and a 3D version of the LAR algorithm, chooses m neighbors according to a space-partition heuristic and forwards the message to all these nodes. The third group T-ABLAR-T uses progress-based routing (one of Greedy, Compass or MRF, the choice represented by the symbol T), until a local minimum is reached. The algorithm then switches to ABLAR for one step, and after this step resumes with the progress-based algorithm again. The fourth group AB3D-ABLAR uses one of the AB3D routing algorithms until a threshold is passed in terms of number of hops. The algorithm then permanently switches to one of the ABLAR algorithms.

To help motivate the development of these new routing algorithms in Section 4, we will mention for initial comparison purposes the delivery rates (and in some cases the routing traffic) determined by representative simulations for unit disk graphs of 75 nodes, with transmission ranges of 25 units, randomly distributed in a cube with sides of length 100 units. These sample experimental results show that the delivery rates and routing traffic of the new algorithms are significantly better than previously studied routing algorithms. For example, the delivery rates for selected algorithms in the fourth group of AB3D-ABLAR algorithms are comparable to a straightforward 3D version of LAR algorithm, LAR3D (which is described in more detail in Section 3), but with more than 55% less routing traffic. These experimental results are expanded upon in detail when the full simulation set-up and results are presented in Section 5.

The rest of this paper is organized as follows. Section 2 is devoted to background material. In Section 3, we briefly review some directly related position-based routing algorithms. In Section 4 we give detailed descriptions of the new proposed routing algorithms. In Section 5, we present experimental results to demonstrate the much improved performance of the proposed methods in comparison with existing techniques. Finally, Section 6 discusses the conclusions drawn in this paper.