

Mobile ad-hoc Networks (MANET) are self-managing wireless networks without requiring any central administration. Each MANT node can connect to its neighbors on ad-hoc basic and communicate with other nodes through its neighbors over multi-hop wireless links. The routes to destinations are discovered by broadcasting customized message which are re-broadcasted by the receiving nodes again and again until the message reaches the ultimate destination node. Continuous mobility of nodes and wireless nature of the communication links challenge to achieve efficient and smart broadcasting and hence efficient routing. A node receiving a broadcast message should be cautious on re-broadcasting to avoid BSP (Broadcast Storm Problem) while ensuring the reachability of the message to the final destination. This paper presents a distributed algorithm to decide the re-broadcasting for individual MANET nodes. The algorithm takes into account the neighboring node density and SINR (Signal to Interference plus Noise Ratio), and adapts accordingly. The proposed algorithm has been implemented in standard AODV using ns-2 simulator. The simulation results have shown that the proposed algorithm outperforms the standard AODV and two competitor schemes in terms of routing overhead, throughput, end-to-end delay and energy consumption significantly. This helps not only network performance but greener computing as well.

Index Terms— MANET; Routing AODV; Probabilistic Broadcast; green computing;

I.     INTRODUCTION

He proliferation of handheld devices (like electronic gadgets, laptops and smartphones) that are developed based on the IEEE 802.11 standard of wireless protocol have kept Mobile Ad-hoc Networks (MANETs) an active area of research over the past two decades. A MANET is a self-configuring, self-healing and infrastructure-less network of mobile nodes connected to each other over single-hop or multi-hop wireless links on ad-hoc basis [1].These characteristics of MANETs make them an ideal choice for a number of applications e.g., communications in battlefield, rescue operation in disaster areas or quick deployment of networks without requiring huge infrastructure.

MANET nodes can be located arbitrarily within an area and are free to move. The movement of MANET nodes changes the network topology dynamically. MANET nodes adapt to the changing topology by discovering new neighbours and establishing new routes to destination nodes [2]. A node may not communicate directly with a distant node due to limited transmission range, and may have to rely on other nodes to relay the message along the route to the final destination node. In this way, each node acts as a host node as well as a relay node to extend the reachability of other nodes.

When a node wants to send data to a remote node, first, it finds out a set of relay nodes between itself and the remote node. The process of finding the optimal set of relay nodes between the source node and the destination node is called route discovery. Node mobility, limited battery power and the error-prone nature of wireless links are the main challenges in designing an efficient rout discovery process in MANETs.

A number of routing protocols have been proposed in the literature [3][4]. These protocols generally fall into three categories namely table-driven (proactive), on-demand (reactive) and hybrid routing protocols. Table-driven routing protocols aim to maintain routes to all possible destinations in the network at all times. Examples of table-driven routing protocols include OLSR (Optimized Link State Routing) [5] and DSDV (Destination-Sequenced Distance-Vector) routing  [6]. In contrast to table-driven approach, on-demand routing protocols, e.g., AODV (Ad-hoc On-demand Distance Vector) routing [7], DSR (Dynamic Source Routing) [3], and ABR (Associativity-Based Routing) [8], discover a route only when it is needed. Hybrid routing protocols, e.g., ZRP (Zone Routing Protocol) [9] and CEDAR (Core-Extraction Distributed Ad-hoc Routing) [10] combine the features of both proactive and reactive routing protocols. Interested reader can find a survey in [11].

In on-demand routing protocols, the routing process consists of two phases namely route-discovery and route-maintenance. These protocols rely on broadcasting for route discovery. For example, in case of AODV routing protocol, a source node that needs to send data to a destination node triggers route discovery mechanism by broadcasting a special control packet, called Route Request (RREQ), to its neighbours who then rebroadcast the RREQ packet to their neighbours. The process continues until the RREQ packet arrives at the destination node. The destination node sends a control packet called Route Reply (RREP) that follows the path of RREQ in reverse direction and informs the source node that a route has been established. Since every node on receiving the RREQ for the first time rebroadcasts it, it requires T-2 rebroadcasts in a network of T nodes assuming the destination is reachable. This kind of broadcasting is called pure flooding and is depicted briefly in Figure 1 while details can be found in [7].

Pure flooding often results in substantial redundant transmissions because a node may receive the same packet from multiple other nodes. This phenomenon, commonly known as the broadcast storm problem (BSP) [12], causes frequent contention and packet collisions leading to increased communication overhead and serious performance complications in densely populated MANETs. BSP equally affects the route maintenance phase during which routes are refreshed by triggering new route discovery requests to replace the broken routes.

A number of probabilistic broadcasting schemes have been proposed in the literature to address BSP. However, the performance of these schemes can be argued for real MANETs because these schemes either ignored thermal noise and interference at all [13] [14] [15]or they used the noise drawn from a distribution rather than measuring it at lower layers [16]. Real life MANETs are noisy and the communication is not error free. A number of channel impairments like noise, co-channel interference, signal attenuation, fading and user mobility affect the transmission and should be taken into account. This paper presents a novel Channel Adaptive Probabilistic Broadcasting (CAPB) scheme that adapts the probability of rebroadcasting RREQ packets dynamically according to the thermal noise, co-channel interference and node density in the neighbourhood. The proposed scheme is implemented in the network simulator ns-2 and its performance has been compared with SoA schemes in terms of routing overhead, throughput, end-to-end delay and energy consumption. Simulation results showed that the proposed scheme outperforms the SoA broadcast schemes significantly. The proposed scheme is light and does not require any extra information to be exchanged among the neighbours. This paper is an extension of our work presented in 25th International Conference on Software, Telecommunications and Computer Networks SoftCOM 2017 [17].

The rest of the paper is organized as follows: Section II presents the related work, Section III presents the proposed efficient broadcast scheme, and Section IV presents simulation results and analysis followed by conclusions in Section V.

II.   Related work

To elevate the damaging impact of pure flooding, a number of improved broadcasting techniques have been proposed in the literature, [6]. These schemes generally fall in two categories namely deterministic and probabilistic broadcasting. Deterministic schemes (e.g., MPR [18] and Self Pruning Scheme [19]) exploit network information to make more informed decisions. However, these schemes carry extra overhead to exchange location and neighborhood information among the nodes. On the other hand, the probabilistic schemes e.g., Fixed Probabilistic [20], and Counter Based Scheme [14] take local decisions to broadcast or not to broadcast a RREQ packet according to a predetermined probability.

A fixed probabilistic scheme is similar to pure flooding except that nodes rebroadcast with a predetermined probability. Cartigny and Simplot [15] presented an improved probabilistic scheme combination where the rebroadcast probability is calculated from the number of neighbors which are considering retransmission. This scheme was shown to achieve significant reduction in the number of rebroadcasts. However, this scheme did not consider thermal noise and co-channel interference.

Zhang and Zhou  [13] proposed an algorithm of load balancing based on history information. In their algorithm mobile nodes use history load information and judge route access by probability. They combined the algorithm with DSR, and they named HPDSR (Historical Probability Dynamic Source Routing). Their computer simulation results showed that HPDSR protocol improves network throughput and reduces the end-to- end delay effectively without extra route overhead. However, they did not consider noise effect at all.

Ali, et al [21] proposed a routing protocol, called  neighbor-based Dynamic Connectivity Factor routing Protocol (DCFP), that dynamically probe the status of the underlying network without the intervention of a system administrator, while reducing the RREQ overhead using a new connectivity factor. Their results revealed that the suggested protocol showed better performance than AODV in terms of end-to-end delay, normalized routing overhead, MAC collision, energy consumption, network connectivity, and packet delivery ratio.

Zhang and Agrawal [22] suggested a probabilistic scheme that dynamically modifies the rebroadcasting probability based on the node distribution and the node movement by considering local information but without needing any distance measurements or exact location determination devices. Their results showed an improvement in performance when compared to both pure flooding and static probabilistic schemes. However, the effects of noise and interference were ignored. The same authors (in another work [23]) suggested a levelled probabilistic routing scheme for MANETs. In this scheme, mobile hosts are divided into four groups and different rebroadcast probabilities are assigned to each group. The results showed gains in throughput.

Mohammed et al. [14] suggested a probabilistic counter-based scheme that reduces the retransmission of RREQ packets during the route discovery phase. The results revealed an enhancement in the performance of AODV in terms of routing overhead, MAC collisions, and end-to-end delay while still achieving a good throughput. However, this approach did not consider thermal noise plus interference.

Al-Bahadili and Sabri [16] proposed a probabilistic algorithm for route discovery based on  the noise-level called Dynamic Noise-Dependent Probabilistic (DNDP) scheme. In this scheme the noise-level value is drawn from a distribution rather than measuring it at lower layers. The simulation results showed that the suggested algorithm presented higher network reachability than the dynamic probabilistic algorithm with a reasonable increase in the number of retransmissions for a wide range of noise-levels.

Linfoot, et al.[22] studied the effects of physical and virtual carrier sensing on the AODV routing protocol and showed that the route discovery mechanism is affected by the interference when the number of nodes increases.

In wireless networks, physical layer characteristics affect the higher layer protocols. This shows a great potential of exploiting cross layer optimization approaches. Takai et al. [24] studied the role of physical layer modelling in evaluating the performance of higher layer protocols and showed that the physical layer modelling plays a key role even though the higher layer protocols do not interact with the physical layer directly.

Alnajjar and Chen [25] stated a cross-layer mechanism wherein the routing protocols adapt to the current Signal to Noise Ratio (SNR). This approach was implemented in DSR protocol and was shown to enhance the performance.

To the best of the authors’ knowledge, no previous work on probabilistic broadcast in route discovery mechanism has considered the effects of thermal noise, co-channel interference, and node density in the neighbourhood simultaneously to address the BSP.

III. Proposed broadcast scheme

The proposed CAPB scheme adjusts the probability of rebroadcasting RREQ packets dynamically by taking into account two factors. The first factor is the measured co-channel interference plus thermal noise, and the second factor is the node density in the neighbourhood. These two factors affect the efficacy of disseminating RREQ packets as discussed below.

A.      Effect of Co-Channel Interference & Thermal Noise

Consider Figure 2 where node A broadcasts a RREQ message to find the route to node G. In Figure 2(a), using pure flooding in absence of co-channel interference and thermal noise, the destination node (G) receives the RREQ packet from node B as well as node C. The destination node (G) however, will only send one RREP packet to either node B or C whichever forwards the RREQ first. Using probabilistic broadcast, there are three possibilities (i) both B and C, (ii) either B or C and (iii) neither of the two nodes will rebroadcast the RREQ packet. As exemplified in Figure 2b, using probabilistic broadcast in absence of co-channel interference and thermal noise, only node B manages to rebroadcast the RREQ. By considering the effects of thermal noise and co-channel interference (Figure 2c), assuming that node A fails to deliver the RREQ packet to node B (because of thermal noise plus interference in the area), but is able to deliver the same packet to node C, the RREQ packet is therefore undelivered to node G. Node G will thus be declared unreachable.

Packet Error Rate (PER) is closely related to SINR (Signal to Interference plus Noise Ratio) and packet size as shown in Figure 3 [26]. In the proposed CAPB scheme, when a node receives a RREQ packet, it obtains the SINR value, as measured at the physical layer and infers the PER using the relationship shown in Figure 3. If the PER is higher, then the probability of receiving the same RREQ packet by the neighbouring nodes is low. In this case, naturally the lucky node that has received the RREQ should rebroadcast the RREQ with high probability to increase the dissemination of this particular RREQ packet. On the other hand, a low PER implies that many nodes in the neighbourhood have also received the RREQ packet with high probability, therefore the rebroadcast probability should be relatively low to avoid the BSP.

B.      Effect of Node Density in Neighbourhood

When a node receives a RREQ packet, the decision of rebroadcasting should take into account the number of neighbouring nodes and their geographic distribution to make a wise decision. In a densely populated area, not all nodes need to rebroadcast to avoid redundancy and the risk of increased collision leading to packet loss and energy wastage. On the other hand, in a sparsely populated area relatively more nodes should rebroadcast the RREQ packet to ensure dissemination of the RREQ packet. Here we consider only the number of nodes in the transmission range of the node receiving the RREQ packet to determine the rebroadcast probability.

C.     The Proposed CAPB Algorithm