Efficient Broadcasting in Mobile Ad Hoc Networks
Authors:
- 27 June 2008
- journal article
- Published by Institute of Electrical and Electronics Engineers (IEEE) in IEEE Transactions on Mobile Computing
- Vol. 8 (2) , 231-245
Abstract
This paper presents two efficient flooding algorithms based on 1-hop neighbor information. In the first part of the paper, we consider sender-based flooding algorithms, specifically the algorithm proposed by Liu et al. In their paper, Liu et al. propose a sender-based flooding algorithm that can achieve local optimality by selecting the minimum number of forwarding nodes in the lowest computational time complexity O(n logn), where n is the number of neighbors. We show that this optimality only holds for a subclass of sender-based algorithms. We propose an efficient sender-based flooding algorithm based on 1-hop neighbor information that reduces the time complexity of computing forwarding nodes to O(n). In Liu's algorithm, n nodes are selected to forward the message in the worst case, whereas in our proposed algorithm, the number of forwarding nodes in the worst case is 11. In the second part of the paper we propose a simple and highly efficient receiver-based flooding algorithm. When nodes are uniformly distributed, we prove that the probability of two neighbor nodes broadcasting the same messageneighbor nodes broadcasting the same message exponentially decreases when the distance between them decreases or when the node density increases. The analytical results are confirmed using simulation.Keywords
This publication has 19 references indexed in Scilit:
- Localized Broadcasting with Guaranteed Delivery and Bounded Transmission RedundancyIEEE Transactions on Computers, 2008
- DRB and DCCB: Efficient and Robust Dynamic Broadcast for Ad Hoc and Sensor Networks2007
- Efficient Flooding Scheme Based on 1-Hop Information in Mobile Ad Hoc Networks2006
- Probabilistic broadcast for flooding in wireless mobile ad hoc networks2004
- Range-free localization schemes for large scale sensor networks2003
- Distributed construction of connected dominating set in wireless ad hoc networks2003
- On calculating connected dominating set for efficient routing in ad hoc wireless networks1999
- The broadcast storm problem in a mobile ad hoc network1999
- Unit disk graphsDiscrete Mathematics, 1990
- On the average length of Delaunay triangulationsBIT Numerical Mathematics, 1984