Minimum-power multicast routing in static ad hoc wireless networks

Peng Jun Wan*, Gruia Cǎlinescu, Tsi-Ui Ik

*此作品的通信作者

研究成果: Article同行評審

89 引文 斯高帕斯(Scopus)

摘要

Wieselthier et al. (2000) proposed three greedy heuristics for Min-Power Asymmetric Broadcast Routing: SPT (shortest-path tree), MST (minimum spanning tree), and BIP (broadcasting incremental power). Wan et al. (2001) proved that SPT has an approximation ratio of at least (n/2) where n is the total number of nodes, and both MST and BIP have constant approximation ratios. Based on the approach of pruning, Wieselthier et al. also proposed three greedy heuristics for Min-Power Asymmetric Multicast Routing: P-SPT (pruned shortest-path tree), P-MST (pruned minimum spanning tree), and P-BIP (pruned broadcasting incremental power). In this paper, we first prove that the approximation ratios of these three heuristics are at least (n - 1/2), n - 1, and n - 2 - o(1), respectively. We then present constant-approxiation algorithms for Min-Power Asymmetric Multicast Routing. We show that any ρ-approximation Steiner tree algorithm gives rise to a cρ-approximation heuristic for Min-Power Asymmetric Multicast Routing, where c is a constant between 6 and 12. In particular, the Takahashi-Matsuyama Steiner tree heuristic leads to a heuristic called SPF (shortest-path first), which has an approximation ratio of at most 2c. We also present another heuristic, called MIPF (minimum incremental path first), for Min-Power Asymmetric Multicast Routing and show that its approximation ratio is between (13/3) and 2c. Both SPF and MIPF can be regarded as an adaptation of MST and BIP, respectively, in a different manner than pruning. Finally, we prove that any ρ-approximation Steiner tree algorithm also gives rise to a 2ρ-approximation algorithm for Min-Power Symmetric Multicast Routing.

原文English
頁(從 - 到)507-514
頁數8
期刊IEEE/ACM Transactions on Networking
12
發行號3
DOIs
出版狀態Published - 1 六月 2004

指紋

深入研究「Minimum-power multicast routing in static ad hoc wireless networks」主題。共同形成了獨特的指紋。

引用此