Minimum-power multicast routing in static ad hoc wireless networks

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

*Corresponding author for this work

Research output: Contribution to journalArticlepeer-review

89 Scopus citations

Abstract

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.

Original languageEnglish
Pages (from-to)507-514
Number of pages8
JournalIEEE/ACM Transactions on Networking
Volume12
Issue number3
DOIs
StatePublished - 1 Jun 2004

Fingerprint Dive into the research topics of 'Minimum-power multicast routing in static ad hoc wireless networks'. Together they form a unique fingerprint.

Cite this