Efficient Flooding Scheme Based on 1-Hop Information in Mobile Ad Hoc Networks
Authors:
- H. LiuHLH. Liu
- P. WanPWP. Wan
- X. JiaXJX. Jia
- X. LiuXLX. Liu
- F. YaoFYF. Yao
- 1 January 2006
- conference paper
- Published by Institute of Electrical and Electronics Engineers (IEEE)
- No. 0743166X,p. 1-12
Abstract
Flooding is one of the most fundamental operations in mobile ad hoc networks. Traditional implementation of flooding suffers from the problems of excessive redundancy of messages, resource contention, and signal collision. This causes high protocol overhead and interference to the existing traffic in the networks. Some efficient flooding algorithms were proposed to avoid these problems. However, these algorithms either perform poorly in reducing redundant transmissions, or require each node to maintain 2-hop (or more) neighbors information. In the paper, we study the sufficient and necessary condition of 100% deliverability for flooding schemes that are based on only 1-hop neighbors information. We further propose an efficient flooding algorithm that achieves the local optimality in two senses: 1) the number of forwarding nodes in each step is the minimal; 2) the time complexity for computing forwarding nodes is the lowest, which is O(nlogn), where n is the number of neighbors of a node. Extensive simulations have been conducted and simulation results have shown that performance of our algorithm is significantly better than the existing message efficient flooding methods. © 2006 IEEE.Keywords
This publication has 20 references indexed in Scilit:
- Double-covered broadcast (DCB): a simple reliable broadcast algorithm in MANETs2004
- Energy efficient broadcast routing in static ad hoc wireless networksIEEE Transactions on Mobile Computing, 2004
- Probabilistic broadcast for flooding in wireless mobile ad hoc networks2004
- BROADCASTING IN AD HOC NETWORKS BASED ON SELF-PRUNINGInternational Journal of Foundations of Computer Science, 2003
- On the construction of energy-efficient broadcast and multicast trees in wireless networks2002
- Dominating sets and neighbor elimination-based broadcasting algorithms in wireless networksIEEE Transactions on Parallel and Distributed Systems, 2002
- Comparison of broadcasting techniques for mobile ad hoc networks2002
- Span2001
- Multicast tree construction and flooding in wireless ad hoc networks2000
- On calculating connected dominating set for efficient routing in ad hoc wireless networks1999