Towards an Efficient Flooding Scheme Exploiting 2-Hop Backward Information in MANETs

Trong Duc LE  Hyunseung CHOO  

Publication
IEICE TRANSACTIONS on Communications   Vol.E92-B   No.4   pp.1199-1209
Publication Date: 2009/04/01
Online ISSN: 1745-1345
DOI: 10.1587/transcom.E92.B.1199
Print ISSN: 0916-8516
Type of Manuscript: PAPER
Category: Network
Keyword: 
2-hop backward information,  flooding,  broadcasting,  forwarding set propagation,  mobile ad hoc network,  

Full Text: PDF>>
Buy this Article




Summary: 
Flooding is an indispensable operation for providing control or routing functionalities to mobile ad hoc networks (MANETs). Previously, many flooding schemes have been studied with the intention of curtailing the problems of severe redundancies, contention, and collisions in traditional implementations. A recent approach with relatively high efficiency is 1HI by Liu et al., which uses only 1-hop neighbor information. The scheme achieves local optimality in terms of the number of retransmission nodes with time complexity Θ(nlog n), where n is the number of neighbors of a node; however, this method tends to make many redundant transmissions. In this paper, we present a novel flooding algorithm, 2HBI (2-hop backward information), that efficiently reduces the number of retransmission nodes and solves the broadcast storm problem in ad hoc networks using our proposed concept, "2-hop backward information." The most significant feature of the proposed algorithm is that it does not require any extra communication overhead other than the exchange of 1-hop HELLO messages but maintains high deliverability. Comprehensive computer simulations show that the proposed scheme significantly reduces redundant transmissions in 1HI and in pure flooding, up to 38% and 91%, respectively; accordingly it alleviates contention and collisions in networks.