期刊
MOBILE NETWORKS & APPLICATIONS
卷 9, 期 2, 页码 101-111出版社
SPRINGER
DOI: 10.1023/B:MONE.0000013622.63511.57
关键词
wireless ad hoc networks; broadcast; approximation algorithms; unit-disk graphs; disk cover
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.
作者
我是这篇论文的作者
点击您的名字以认领此论文并将其添加到您的个人资料中。
推荐
暂无数据