TY - JOUR

T1 - Minimum-power multicast routing in static ad hoc wireless networks

AU - Wan, Peng Jun

AU - Cǎlinescu, Gruia

AU - Ik, Tsi-Ui

PY - 2004/6/1

Y1 - 2004/6/1

N2 - 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.

AB - 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.

UR - http://www.scopus.com/inward/record.url?scp=4344622572&partnerID=8YFLogxK

U2 - 10.1109/TNET.2004.828940

DO - 10.1109/TNET.2004.828940

M3 - Article

AN - SCOPUS:4344622572

VL - 12

SP - 507

EP - 514

JO - IEEE/ACM Transactions on Networking

JF - IEEE/ACM Transactions on Networking

SN - 1063-6692

IS - 3

ER -