Approximation schemes for wireless networks

ABSTRACT

Wireless networks are created by the communication links between a collection of radio transceivers. The nature of wireless transmissions does not lead to arbitrary undirected graphs but to structured graphs which we characterize by the polynomially bounded growth property. In contrast to many existing graph models for wireless networks, the property of polynomially bounded growth is defined independently of geometric data such as positional information.

On such wireless networks, we present an approach that can be used to create polynomial-time approximation schemes for several optimization problems called the local neighborhood-based scheme. We apply this approach to the problems of seeking maximum (weight) independent sets and minimum dominating sets. These are two important problems in the area of wireless communication networks and are also used in many applications ranging from clustering to routing strategies. However, the approach is presented in a general fashion since it can be applied to other problems as well.

The approach for the approximation schemes is robust in the sense that it accepts any undirected graph as input and either outputs a solution of desired quality or correctly asserts that the graph presented as input does not satisfy the structural assumption of a wireless network (an NP-hard problem).

REFERENCES

• 1: Ambuehl, C., Erlebach, T., Mihalak, M., and Nunkesser, M. 2006. Constant-factor approximation for minimum-weight (connected) dominating sets in unit disk graphs. In Proceedings of the 9th Workshop on Approximation Algorithms for Combinatorial Optimization Problems. To appear.
• 2: Assouad, P. 1983. Plongements Lipschitziens dans Rⁿ. Bull. Soc. Math. France 111, 4, 567--583.
• 3: Heinz Breu , David G. Kirkpatrick, Unit disk graph recognition is NP-hard, Computational Geometry: Theory and Applications, v.9 n.1-2, p.3-24, Jan. 1998 [doi>10.1016/S0925-7721(97)00014-X]
• 4: Timothy M. Chan, Polynomial-time approximation schemes for packing and piercing fat objects, Journal of Algorithms, v.46 n.2, p.178-189, February 2003 [doi>10.1016/S0196-6774(02)00294-8]
• 5: Cheng, X., Huang, X., Li, D., Wu, W., and Du, D.-Z. 2003. A polynomial-time approximation scheme for the minimum-connected dominating set in ad hoc wireless networks. Networks 42, 202--208.
• 6: 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]
• 7: Thomas Erlebach , Klaus Jansen , Eike Seidel, Polynomial-Time Approximation Schemes for Geometric Intersection Graphs, SIAM Journal on Computing, v.34 n.6, p.1302-1323, 2005 [doi>10.1137/S0097539702402676]
• 8: Anupam Gupta , Robert Krauthgamer , James R. Lee, Bounded Geometries, Fractals, and Low-Distortion Embeddings, Proceedings of the 44th Annual IEEE Symposium on Foundations of Computer Science, p.534, October 11-14, 2003
• 9: Harry B. Hunt, III , Madhav V. Marathe , Venkatesh Radhakrishnan , S. S. Ravi , Daniel J. Rosenkrantz , Richard E. Stearns, NC-approximation schemes for NP- and PSPACE-hard problems for geometric graphs, Journal of Algorithms, v.26 n.2, p.238-274, feb. 1998 [doi>10.1006/jagm.1997.0903]
• 10: Jan Kratochvíl, Intersection Graphs of Noncrossing Arc-Connected Sets in the Plane, Proceedings of the Symposium on Graph Drawing, p.257-270, September 18-20, 1996
• 11: Fabian Kuhn , Aaron Zollinger, Ad-hoc networks beyond unit disk graphs, Proceedings of the 2003 joint workshop on Foundations of mobile computing, p.69-78, September 19, 2003, San Diego, CA, USA [doi>10.1145/941079.941089]
• 12: Li, X. 2003. Algorithmic, geometric and graphs issues in wireless networks. Wirel. Comm. Mobile Comput. 3, 119--140.
• 13: Nieberg, T., and Hurink, J. 2004. Wireless communication graphs. In Proceedings of the Intelligent Sensors, Sensor Networks and Information Processing Conference. 367--372.
• 14: Nieberg, T., and Hurink, J. 2005. A PTAS for for the minimum dominating set problem in unit disk graphs. In Proceedings of the 3rd Workshop on Approximation and Online Algorithms. Springer, Lecture Notes in Computer Science, vol. 3879, 296--306.
• 15: Nieberg, T., Hurink, J., and Kern, W. 2004. A robust PTAS for maximum independent sets in unit disk graphs. In Proceedings of the 30th Workshop on Graph Theoretic Concepts in Computer Science. Springer, Lecture Notes in Computer Science, vol. 3353, 214--221.
• 16: Vijay Raghavan , Jeremy Spinrad, Robust algorithms for restricted domains, Journal of Algorithms, v.48 n.1, p.160-172, August 2003 [doi>10.1016/S0196-6774(03)00048-8]

INDEX TERMS

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

General Terms:
Algorithms

Keywords:
PTAS, Wireless ad-hoc networks, bounded growth, maximum independent set, minimum dominating set