Approximating node-weighted multicast trees in wireless ad-hoc networks

ABSTRACT

Multicast communication in a wireless ad-hoc network can be established using a tree that spans the multicast sender and receivers as well as other intermediate nodes. If the network is modelled as a graph, the multicast tree is a Steiner tree, the multicast sender and receivers correspond to terminals, and other nodes participating in the tree are Steiner nodes. As Steiner nodes are nodes that participate in the multicast tree by forwarding packets but do not benefit from the multicast, it is a natural objective to compute a tree that minimizes the total cost of the Steiner nodes. We therefore consider the problem of computing, for a given node-weighted graph and a set of terminals, a Steiner tree with Steiner nodes of minimum total weight. For graph classes that admit spanning trees of maximum degree at most d, we obtain a 0.775d-approximation algorithm. We show that this result implies a 3.875-approximation algorithm for unit disk graphs, an O(1/α²)-approximation algorithm for α-unit disk graphs, and an O(λ)-approximation algorithm for (λ + 1)-claw-free graphs.

REFERENCES

• 1: Brent N. Clark , Charles J. Colbourn , David S. Johnson, Unit disk graphs, Discrete Mathematics, v.86 n.1-3, p.165-177, Dec. 14, 1990 [doi>10.1016/0012-365X(90)90358-O]
• 2: M. R. Garey and D. S. Johnson. The rectilinear Steiner tree problem is NP-complete. SIAM Journal on Applied Mathematics, 32:826--834, 1977.
• 3: Sudipto Guha , Samir Khuller, Improved methods for approximating node weighted Steiner trees and connected dominating sets, Information and Computation, v.150 n.1, p.57-74, April 10, 1999 [doi>10.1006/inco.1998.2754]
• 4: M. Karpinsky and A. Zelikovsky. New approximation algorithms for the Steiner tree problem. Journal of Combinatorial Optimization, 1:47--66, 1997.
• 5: Philip Klein , R. Ravi, A nearly best-possible approximation algorithm for node-weighted Steiner trees, Journal of Algorithms, v.19 n.1, p.104-115, July 1995 [doi>10.1006/jagm.1995.1029]
• 6: Fabian Kuhn , Roger Wattenhofer , Aaron Zollinger, Ad hoc networks beyond unit disk graphs, Wireless Networks, v.14 n.5, p.715-729, October 2008 [doi>10.1007/s11276-007-0045-6]
• 7: G. M. L. Kou and L. Berman. A fast algorithm for Steiner trees. Acta Informatica, 15(2):141--145, 1981.
• 8: M. V. Marathe, H. Breu, H. B. Hunt III, S. S. Ravi, and D. J. Rosenkrantz. Simple heuristics for unit disk graphs. Networks, 25:59--68, 1995.
• 9: Gabriel Robins , Alexander Zelikovsky, Improved Steiner tree approximation in graphs, Proceedings of the eleventh annual ACM-SIAM symposium on Discrete algorithms, p.770-779, January 09-11, 2000, San Francisco, California, United States
• 10: S. Schmid and R. Wattenhofer. Algorithmic models for sensor networks. In Proceedings of the 20th International Parallel and Distributed Processing Symposium (IPDPS), 2006.
• 11: H. Takahashi and A. Matsuyama. An approximate solution for the Steiner problem in graphs. Mathematica Japonica, 24:573--577, 1980.
• 12: Weili Wu , Hongwei Du , Xiaohua Jia , Yingshu Li , Scott C.-H. Huang, Minimum connected dominating sets and maximal independent sets in unit disk graphs, Theoretical Computer Science, v.352 n.1, p.1-7, 7 March 2006 [doi>10.1016/j.tcs.2005.08.037]
• 13: C. Xu, Y. Xu, and J. Wu. On the minimization of the number of forwarding nodes for multicast in wireless ad hoc networks. In Proceedings of ICCNMC'05, LNCS 3619, pages 286--294. Springer, 2005.
• 14: A. Zelikovsky. An 11/6 approximation algorithm for the network Steiner problem. Algorithmica, 9:463--470, 1993.
• 15: Feng Zou , Xianyue Li , Donghyun Kim , Weili Wu, Two Constant Approximation Algorithms for Node-Weighted Steiner Tree in Unit Disk Graphs, Proceedings of the 2nd international conference on Combinatorial Optimization and Applications, p.278-285, August 21-24, 2008, St. John's, Canada [doi>10.1007/978-3-540-85097-7_26]

INDEX TERMS

Primary Classification:
  C. Computer Systems Organization
  C.2 COMPUTER-COMMUNICATION NETWORKS
      C.2.1 Network Architecture and Design

Additional Classification:
  G. Mathematics of Computing
  G.2 DISCRETE MATHEMATICS
      G.2.2 Graph Theory

General Terms:
Algorithms, Theory

Keywords:
multicasting, steiner tree, wireless ad-hoc networks