Local approximation schemes for ad hoc and sensor networks

ABSTRACT

We present two local approaches that yield polynomial-time approximation schemes (PTAS) for the Maximum Independent Set and Minimum Dominating Set problem in unit disk graphs. The algorithms run locally in each node and compute a (1+ε)-approximation to the problems at hand for any given ε > 0. The time complexity of both algorithms is O(T_MIS + log^*! n/ε^O(1)), where T_MIS is the time required to compute a maximal independent set in the graph, and n denotes the number of nodes. We then extend these results to a more general class of graphs in which the maximum number of pair-wise independent nodes in every r-neighborhood is at most polynomial in r. Such graphs of polynomially bounded growth are introduced as a more realistic model for wireless networks and they generalize existing models, such as unit disk graphs or coverage area graphs.

References

1. I. Abraham and D. Malkhi. Name Independent Routing for Growth Bounded Networks. In Proc. 17th ACM Symposium on Parallelism in Algorithms and Architectures (SPAA), pages 49--55, 2005.
2. K. Alzoubi, P.-J. Wan, and O. Frieder. Message-Optimal Connected Dominating Sets in Mobile Ad Hoc Networks. In Proc. 3rd ACM Int. Symposium on Mobile Ad Hoc Networking and Computing (MobiHOC), pages 157--164, Lausanne, Switzerland, 2002.
3. B. Awerbuch. Complexity of Network Synchronization. Journal of the ACM, 32(4):804--823, 1985.
4. B. Baker. Approximation algorithms for NP-complete problems on planar graphs. Journal of the ACM, 41(1):153--180, 1994.
5. Y. Bartal, J. W. Byers, and D. Raz. Global optimization using local information with applications to flow control. In Proc. 38th IEEE Symposium on the Foundations of Computer Science (FOCS), pages 301--312, 1997.
6. H. Breu and D. G. Kirkpatrick. Unit Disk Graph Recognition is NP-hard. Computational Geometry. Theory and Applications}, 9(1-2):3--24, 1998.
7. X. Cheng, X. Huang, D. Li, W. Wu, and D.-Z. Du. A polynomial-time approximation scheme for the minimum-connected dominating set in ad hoc wireless networks. Networks, 42(4):202--208, 2003.
8. B. N. Clark, C. J. Colburn, and D. S. Johnson. Unit disks graphs. Discrete Mathematics, 86:165--177, 1990.
9. R. Cole and U. Vishkin. Deterministic coin tossing with applications to optimal parallel list rankin. Information and Control, 70(1):32--53, 1986.
10. B. Deb and B. Nath. On the node-scheduling approach to topology control in ad hoc networks. In Proc. 6th ACM International Symposium on Mobile Ad Hoc Networking and Computing (MOBIHOC), pages 14--26, 2005.
11. T. Erlebach, K. Jansen, and E. Seidel. Polynomial-time approximation schemes for geometric graphs. In Proc. 12th {ACM}-{SIAM} symposium on discrete algorithms (SODA}'01, pages 671--679, Washington, DC, 7--9 2001.
12. R. Gandhi and S. Parthasarathy. Distributed Algorithms for Coloring and Connected Domination in Wireless Ad Hoc Networks. In Foundations of Software Technology and Theoretical Computer Science (FSTTCS)}, 2004.
13. H.B. Hunt III, M. Marathe, V. Radhakrishnan, S. S. Ravi, D. Rosenkrantz, and R. Stearns. NC-approximation schemes for NP- and PSPACE-hard problems for geometric graphs. J. Algorithms, 26(2):238--274, 1998.
14. W. R. Heinzelman, A. Chandrakasan, and H. Balakrishnan. Energy-Efficient Communication Protocol for Wireless Microsensor Networks. In Proc. 33rd Hawaii International Conference on System Sciences (HICSS), page 8020. IEEE Computer Society, 2000.
15. D. Hochbaum and W. Maass. Approximation schemes for covering and packing problems. Journal of the ACM, 32(1):130--136, 1985.
16. L. Jia, R. Rajaraman, and R. Suel. An Efficient Distributed Algorithm for Constructing Small Dominating Sets. In Proc. 20th ACM Symposium on Principles of Distributed Computing (PODC), pages 33--42, 2001.
17. D. R. Karger and M. Ruhl. Finding Nearest Neighbors in Growth Restricted Metrics. In Proc. 34th Symposium on Theory of Computing (STOC), 2002.
18. F. Kuhn, T. Moscibroda, and R. Wattenhofer. Initializing Newly Deployed Ad Hoc and Sensor Networks. In Proc. 10th Annual International Conference on Mobile Computing and Networking (MOBICOM), pages 260--274, 2004.
19. F. Kuhn, T. Moscibroda, and R. Wattenhofer. What Cannot Be Computed Locally! In Proc. 23rd ACM Symposium on Principles of Distributed Computing (PODC), pages 300--309, 2004.
20. F. Kuhn, T. Moscibroda, and R. Wattenhofer. On the Locality of Bounded Growth. In Proc. of the 24th ACM Symp. on Principles of Distributed Computing (PODC), pages 60--68, 2005.
21. F. Kuhn, T. Moscibroda, T. Nieberg, and R. Wattenhofer. Fast Deterministic Distributed Maximal Independent Set Computation on Growth-Bounded Graphs. In Proc. 19th Conference on Distributed Computing (DISC), 2005.
22. F. Kuhn, T. Moscibroda, and R. Wattenhofer. Unit Disk Graph Approximation. In Proc. ACM DIALM-POMC Joint Workshop on Foundations of Distributed Computing, 2004.
23. F. Kuhn, T. Moscibroda, and R. Wattenhofer. The Price of Being Near-Sighted. preprint, 2005.
24. F. Kuhn and R. Wattenhofer. Constant-Time Distributed Dominating Set Approximation. In Proc. 22nd ACM Symposium on Principles of Distributed Computing (PODC), pages 25--32, 2003.
25. F. Kuhn, R. Wattenhofer, and A. Zollinger. Ad-Hoc Networks Beyond Unit Disk Graphs. In Proc. 1st ACM DIALM-POMC Joint Workshop on Foundation of Distributed Computing, 2003.
26. M. Marathe, H. Breu, H. Hunt III, S. S. Ravi, and D. Rosenkrantz. Simple heuristics for unit disk graphs. Networks, 25:59--68, 1995.
27. T. Moscibroda and R. Wattenhofer. Maximal Independent Sets in Radio Networks. In Proc. 23rd ACM Symp. on Principles of Distributed Computing (PODC), pages 148--157, 2005.
28. T. Nieberg and J. Hurink. Wireless communication graphs. In Intelligent Sensors, Sensor Networks and Information Processing Conference (ISSNIP), 2004.
29. T. Nieberg and J. Hurink. A PTAS for the minimum dominating set problem in unit disk graphs. In Proc. 3rd Workshop on Approximation and Online Algorithms (WAOA 2005), 2005.
30. T. Nieberg, J. Hurink, and W. Kern. A robust PTAS for maximum independent sets in unit disk graphs. In Proc. 30th Workshop on Graph Theoretic Concepts in Computer Science (WG'04), pages 214--221. LNCS 3353, 2004.
31. V. Rajendran, K. Obraczka, and J. J. Garcia-Luna-Aceves. Energy-efficient collision-free medium access control for wireless sensor networks. In Proc. 1st Int'l Conference on Embedded Networked Sensor Systems (SenSys), pages 181--192, 2003.
32. S. Ramanathan and E. L. Lloyd. Scheduling Algorithms for Multi-Hop Radio Networks. In Conference proceedings on Communications architectures & protocols (SIGCOMM), pages 211--222. ACM Press, 1992.
33. P. Sinha, R. Sivakumar, and V. Bharghavan. Enhancing Ad Hoc Routing with Dynamic Virtual Infrastructures. In Proc. of INFOCOM, pages 1763--1772, 2001.
34. P. Wan, K. Alzoubi, and O. Frieder. Distributed construction of connected dominating set in wireless ad hoc networks. In Proc. INFOCOM, 2002.
35. Y. Wang, W. Wang, and X.-Y. Li. Distributed low-cost backbone formation for wireless ad hoc networks. In Proc. 6th ACM International Symposium on Mobile Ad Hoc Networking and Computing (MOBIHOC), pages 2--13, 2005.
36. J. Wu and H. Li. On Calculating Connected Dominating Set for Efficient Routing in Ad Hoc Wireless Networks. In Proc. 3rd Int. Workshop on Discrete Algorithms and Methods for Mobile Computing and Communications (DIALM), pages 7--14, 1999.

Index Terms

• Mathematics of computing

  • Discrete mathematics

    • Graph theory

      • Network flows

• Theory of computation

  • Design and analysis of algorithms

    • Graph algorithms analysis

      • Network flows

  • Randomness, geometry and discrete structures