A Novel Dynamic Noise-Dependent Probabilistic Algorithm for Route Discovery in MANETs

A Novel Dynamic Noise-Dependent Probabilistic Algorithm for Route Discovery in MANETs

Hussein Al-Bahadili (Petra University, Jordan) and Alia Sabri (Applied Sciences Private University, Jordan)
DOI: 10.4018/978-1-4666-2026-1.ch003
OnDemand PDF Download:
No Current Special Offers


In mobile ad hoc networks (MANETs), broadcasting is widely used in route discovery and other network services. The most widely used broadcasting algorithm is simple flooding, which aggravates a high number of redundant packet retransmissions, causing contention and collisions. Proper use of dynamic probabilistic algorithm significantly reduces the number of retransmissions, which reduces the chance of contention and collisions. In current dynamic probabilistic algorithm, the retransmission probability (pt) is formulated as a linear/non-linear function of a single variable, the number of first-hop neighbors (k). However, such algorithm is suffers in the presence of noise due to increasing packet-loss. In this paper, the authors propose a new dynamic probabilistic algorithm in which ptis determined locally by the retransmitting nodes considering both k and the noise-level. This algorithm is referred to as the dynamic noise-dependent probabilistic (DNDP) algorithm. The performance of the DNDP algorithm is evaluated through simulations using the MANET simulator (MANSim). The simulation results show that the DNDP algorithm presents higher network reachability than the dynamic probabilistic algorithm at a reasonable increase in the number of retransmissions for a wide range of noise-level. The effects of nodes densities and nodes speeds on the performance of the DNDP algorithm are also investigated.
Chapter Preview


A MANET is defined as a collection of low-power wireless mobile nodes forming a temporary network without the aid of any established infrastructure or centralized administration (Bani-Yassin et al., 2006; Scott & Yasinsac, 2004). A data packet in a MANET is forwarded to other mobile nodes within the network through a reliable and efficient route established by routing protocols. The most widely used routing protocols in MANETs are known as dynamic routing protocols (DRPs), such as the ad hoc on-demand distance vector routing (AODV) (Perkins & Royer, 2000), the dynamic source routing (DSR) (Johnson & Maltz, 1995), and the location-aided routing (LAR) (Ko & Vaidya, 2000). DRPs consist of two major phases: (i) route discovery in which a route between source and destination nodes is established for the first time, and (ii) route maintenance in which the route is maintained; and if it is broken for any reason, then the source node either finds other known route on its routing table or initiates new route discovery procedure (Royer & Toh, 1999). The cost of information exchange during route discovery is higher than the cost of point-to-point data forwarding after the route is established (Rahman et al., 2004).

Broadcasting is a fundamental communication primitive for route discovery in DRPs in MANETs. One of the earliest broadcast mechanisms proposed in the literature is simple flooding, which is also called pure or blind flooding. Although it is simple and reliable, simple flooding is costly where it costs n retransmissions in a network of n reachable nodes. Simple flooding in wireless networks results in serious redundancy, contention, and collisions; such a scenario has often been referred to as the broadcast storm problem (BSP) (Tseng et al., 2002).

To eliminate the effects of the BSP during route discovery in MANETs, a variety of flooding optimization techniques have been developed to reduce the number of retransmission for the route request (RREQ) messages. As the number of retransmissions required for broadcasting is decreased, the bandwidth is saved and contention and node power consumption are reduced, and this will improve the overall network performance. Examples of flooding optimization techniques algorithms: probabilistic (Bani-Yassin et al., 2006), LAR (Ko & Vaidya, 2000), multipoint relaying (Al-Bahadili & Jaradat, 2010; Qayyum et al., 2002), counter-based and distance-based (Tseng et al., 2002), cluster-based (Bettstetter, 2004).

In this paper, our main concern is the probabilistic flooding algorithm. In this algorithm, each intermediate node (any node on the network except the source and the destination) is assigned a certain pt. There are two approaches that can be used to set a satisfactory pt for intermediate nodes on the network: static and dynamic. In the former, a pre-determined pt is set for each node on the networks, while for the later, each node locally and dynamically calculates its pt according to k and it can be expressed as: pt= f(k), where f(k) is a linear/non-linear function of k.

In reality, communication channels in MANETs are unreliable due to many types of impairments, such as: signal attenuation, free space loss, noise, atmospheric absorption, etc. In addition, in MANETs, error in reception may occur due to rapidly changing topologies that are caused by nodes movement. All of these impairments and changing topologies may cause an error in reception and are represented by a generic name, noise. The effect of noise in MANET can be simulated through introducing a probability factor that is the probability of reception (pc), and then the effect of noise can be determined randomly by generating a random number ξ (Al-Bahadili & Jaradat, 2007). If ξpc, then the packets is successfully delivered to the receiving node, otherwise, it is undelivered.

Complete Chapter List

Search this Book: