Analyzing the Effect of Node Density on the Performance of the LAR-1P Algorithm

Introduction

A mobile ad hoc network (MANET) is a self-configuring infrastructureless network of low-battery powered mobile devices (nodes) connected by wireless links. Each node in a MANET is free to move independently in any direction, and will therefore change its links to other nodes on the network frequently (Al-Bahadili, 2012). Each node usually acts as a router forwarding traffic unrelated to its own use. One of the main challenges in building a MANET is equipping each node to continuously maintain the information required for efficient and reliable traffic routing (Land, 2008).

The data packets in MANETs are forwarded to other mobile nodes in the network through reliable and efficient dynamic routing protocols, which are part of the network layer software (Land, 2008). These protocols are responsible for deciding which output route a packet should be transmitted on. Dynamic routing protocols (e.g., the dynamic source routing (DSR), ad hoc on-demand distance vector (AODV), zone routing protocol (ZRP)) consist of two main phases; these are: route discovery and route maintenance.

Route discovery is used when a source node desires to send a packet to some destination and does not already have a valid route to that destination; in which the source 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 packet. During the forwarding process, the intermediate nodes record the address of the node from which first copy of the broadcast packet is received in their routing tables. Once the RREQ reaches the destination, it responds with a route reply (RREP) packet back to the source through the route from which it first received the RREQ. Otherwise, if the RREQ packet expired before reaching its destination, then the node, at which it expires, sends a route error (RERR) packet back to the source to initiate a new route discovery process.

Pure flooding is the earliest, simplest, and most reliable mechanism proposed in the literature for route discovery in MANETs (Bani-Yassein & Ould-Khaoua, 2007; Bani-Yassein et al., 2006). 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 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).

A variety of flooding optimization algorithms have been developed to alleviate the effects of BSP during route discovery in MANETs aiming at reducing the number of redundant retransmissions without significantly affecting network reachability. Examples of such algorithms include the LAR-1 (Ko & Vaidya, 2000; Belong & Camp, 2004) and probabilistic (Al-Bahadili, 2010a; Haas et al., 2006) algorithms.

The performance of the LAR-1 algorithm significantly suffers from the large number of redundant retransmissions in high-density networks (zones) (Ko & Vaiyda, 2000). In contrast, the probabilistic algorithm usually provides excellent performance in high-density zones, by appreciably reducing the number of retransmissions with almost no effect on network reachability. Of course, that is subject to proper retransmission probability (p_t) adjustment (Bani-Yassein & Ould-Khaoua, 2007; Bani-Yassein et al., 2006; Al-Bahadili, & Kaabneh, 2010).