Journal
MOBILE NETWORKS & APPLICATIONS
Volume 9, Issue 2, Pages 101-111Publisher
SPRINGER
DOI: 10.1023/B:MONE.0000013622.63511.57
Keywords
wireless ad hoc networks; broadcast; approximation algorithms; unit-disk graphs; disk cover
Ask authors/readers for more resources
Broadcasting is a fundamental operation which is frequent in wireless ad hoc networks. A simple broadcasting mechanism, known as flooding, is to let every node retransmit the message to all its 1-hop neighbors when receiving the first copy of the message. Despite its simplicity, flooding is very inefficient and can result in high redundancy, contention, and collision. One approach to reducing the redundancy is to let each node forward the message only to a small subset of 1-hop neighbors that cover all of the node's 2-hop neighbors. In this paper we propose two practical heuristics for selecting the minimum number of forwarding neighbors: an O(n log n) time algorithm that selects at most 6 times more forwarding neighbors than the optimum, and an O(n log(2) n) time algorithm with an improved approximation ratio of 3, where n is the number of 1- and 2-hop neighbors. The best previously known algorithm, due to Bronnimann and Goodrich [2], guarantees O(1) approximation in O(n(3) log n) time.
Authors
I am an author on this paper
Click your name to claim this paper and add it to your profile.
Reviews
Recommended
No Data Available