期刊
IEEE TRANSACTIONS ON COMPUTERS
卷 55, 期 3, 页码 334-347出版社
IEEE COMPUTER SOC
DOI: 10.1109/TC.2006.40
关键词
approximation ratio; broadcasting; connected dominating set (CDS); heuristic solutions; mobile ad hoc networks (MANETs); multipoint relays (MPR)
Multipoint relays (MPR) [18] provide a localized and optimized way of broadcasting messages in a mobile ad hoc network (MANET). Using partial 2-hop information, each node chooses a small set of forward neighbors to relay messages and this set covers the node's 2-hop neighbor set. These selected forward nodes form a connected dominating set (CDS) to ensure full coverage. Adjih et al. [ 1] later proposed a novel extension of MPR to construct a small CDS and it is source-independent. In this paper, we provide several extensions to generate a smaller CDS using complete 2-hop information to cover each node's 2-hop neighbor set. We extend the notion of coverage in the original MPR. We prove that the extended MPR has a constant local approximation ratio compared with a logarithmic local ratio in the original MPR. In addition, we show that the extended MPR has a constant global probabilistic approximation ratio, while no such ratio exists in the original MPR and its existing extensions. The effectiveness of our approach is confirmed through a simulation study.
作者
我是这篇论文的作者
点击您的名字以认领此论文并将其添加到您的个人资料中。
推荐
暂无数据