Comparing Various Route Discovery Algorithms in Ad Hoc Wireless Networks

Comparing Various Route Discovery Algorithms in Ad Hoc Wireless Networks

Hussein Al-Bahadili, Abdel Rahman Alzoubaidi, Ali Al-Khalidi
DOI: 10.4018/978-1-4666-0191-8.ch010
(Individual Chapters)
No Current Special Offers


Dynamic (reactive or on-demand) routing protocols used in wireless ad hoc networks suffer from transmitting a huge number of control packets during the route discovery phase of the protocols, which increases the overhead significantly. Therefore, a number of optimization protocols have been developed throughout the years. This chapter compares the performance of various route discovery algorithms in ad hoc wireless networks, namely, pure flooding, probabilistic, Location-Aided Routing scheme 1 (LAR-1), LAR-1-Probabilsitic (LAR-1P), and Optimal Multipoint Relying (OMPR). The results obtained through the different simulations are analyzed and compared. This chapter will help practitioners of various kinds (academics, professionals, researchers, and students) grasp a solid understanding of the behavior of ad hoc wireless network route discovery algorithms and develop an appreciation for flooding optimization mechanisms. It also substantiates the case of experimenting via simulation with such models and shows how the different simulation parameters interplay.
Chapter Preview


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).

Complete Chapter List

Search this Book: