Comparing Various Route Discovery Algorithms in Ad Hoc Wireless Networks

Introduction

An ad hoc wireless network is a mobile, wireless network that does not necessitate a pre-existing infrastructure or centralized administration (Lang, 2008). A data packet in ad hoc networks is forwarded to other mobile nodes on the network through a reliable and an efficient route established by routing protocols. A routing protocol is part of the network layer software that is responsible for deciding which output path a packet should be transmitted on. Many routing protocols have been proposed for ad hoc networks (Graziani & Johnson, 2007). These algorithms differ in the approach they use for searching a new route and/or modifying a known route, when nodes move. Each of the available routing algorithms has its own unique characteristic strengths and weaknesses. Routing protocols are classified into different categories according to their properties and applications (Ayub & Garrido, 2008). The most widely used mechanism for categorizing routing protocols is the one that is based on routing information update, which according to it, routing protocols are classified into proactive (static) or reactive (dynamic) or a combination of them (Royer & Toh, 1999).

A Dynamic Routing Protocol (DRP) consists of two main phases: route discovery and route maintenance. Route discovery is the process that allows any node on the network to dynamically discover a route to other nodes on the network (Rahman, et al., 2004). Reactive protocols such as Dynamic Source Routing (DSR) (Johnson & Maltz, 1996), Ad Hoc On-Demand Distance Vector (AODV) (Perkins & Royer, 1999), Zone Routing Protocol (ZRP) (Haas, et al., 2002), and Location Aided Routing (LAR) (Ko & Vaidya, 2000), or variations of them are widely used in MANETs.

It is usually assumed that the cost (in terms of bandwidth and power consumptions and delay) of information exchange during route discovery is higher than the cost of point-to-point data forwarding. Therefore, the process of route discovery should be done with minimum complexity, overhead, and bandwidth and power consumption (Rahman, et al., 2004).

Route discovery is used when a source node desires to send a packet to some destination node and does not already have a valid route to that destination; in which the source node initiates a route discovery process to locate the destination. It broadcasts a Route Request (RREQ) packet to its neighbours, which then forward the request to their neighbours, and so on until the expiration of the RREQ packet. During the forwarding process, the intermediate nodes record in their route tables the address of the node from which the first copy of the broadcast packet is received. Once the RREQ reaches the destination, the destination responds with a Route Reply (RREP) packet back to the source node through the route from which it first received the RREQ (Royer & Toh, 1999).

Pure flooding is one of the earliest, simplest, and reliable mechanisms proposed in the literature for route discovery in MANETs. In pure flooding, each node rebroadcasts the message to its neighbours upon receiving it for the first time, starting at the source node. Although it is simple and reliable, pure flooding is costly where it costs n transmissions in a network of n reachable nodes. In addition, pure flooding in wireless networks, using the IEEE 802.11 protocol, results in serious redundancy, contention, and collisions in the network; such a scenario has often been referred to as the Broadcast Storm Problem (BSP) (Tseng, et al., 2002).