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

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

DOI: 10.4018/jbdcn.2011010103
(Individual Articles)
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 pt is 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.
Article 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.

Complete Article List

Search this Journal:
Volume 19: 1 Issue (2023): Forthcoming, Available for Pre-Order
Volume 18: 2 Issues (2022): 1 Released, 1 Forthcoming
Volume 17: 2 Issues (2021)
Volume 16: 2 Issues (2020)
Volume 15: 2 Issues (2019)
Volume 14: 2 Issues (2018)
Volume 13: 2 Issues (2017)
Volume 12: 2 Issues (2016)
Volume 11: 2 Issues (2015)
Volume 10: 4 Issues (2014)
Volume 9: 4 Issues (2013)
Volume 8: 4 Issues (2012)
Volume 7: 4 Issues (2011)
Volume 6: 4 Issues (2010)
Volume 5: 4 Issues (2009)
Volume 4: 4 Issues (2008)
Volume 3: 4 Issues (2007)
Volume 2: 4 Issues (2006)
Volume 1: 4 Issues (2005)
View Complete Journal Contents Listing