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

Introduction

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 p_t. There are two approaches that can be used to set a satisfactory p_t for intermediate nodes on the network: static and dynamic. In the former, a pre-determined p_t is set for each node on the networks, while for the later, each node locally and dynamically calculates its p_t according to k and it can be expressed as: p_t= 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 (p_c), and then the effect of noise can be determined randomly by generating a random number ξ (Al-Bahadili & Jaradat, 2007). If ξ≤p_c, then the packets is successfully delivered to the receiving node, otherwise, it is undelivered.