Constant density spanners for wireless ad-hoc networks

ABSTRACT

An important problem for wireless ad hoc networks has been to design overlay networks that allow time- and energy-efficient routing. Many local-control strategies for maintaining such overlay networks have already been suggested, but most of them are based on an oversimplified wireless communication model.

In this paper, we suggest a model that is much more general than previous models. It allows the path loss of transmissions to significantly deviate from the idealistic unit disk model and does not even require the path loss to form a metric. Also, our model is apparently the first proposed for algorithm design that does not only model transmission and interference issues but also aims at providing a realistic model for physical carrier sensing. Physical carrier sensing is needed so that our protocols do not require <i>any</i> prior information (not even an estimate on the number of nodes) about the wireless network to run efficiently.

Based on this model, we propose a local-control protocol for establishing a constant density spanner among a set of mobile stations (or <i>nodes</i>) that are distributed in an arbitrary way in a 2-dimensional Euclidean space. More precisely, we establish a backbone structure by efficiently electing cluster leaders and gateway nodes so that there is only a constant number of cluster leaders and gateway nodes within the transmission range of any node and the backbone structure satisfies the properties of a topological spanner.

Our protocol has the advantage that it is locally self-stabilizing, i.e., it can recover from <i>any</i> initial configuration, even if adversarial nodes participate in it, as long as the honest nodes sufficiently far away from adversarial nodes can in principle form a single connected component. Furthermore, we only need constant size messages and a constant amount of storage at the nodes, irrespective of the distribution of the nodes. Hence, our protocols would even work in extreme situations such as very simple wireless devices (like sensors) in a hostile environment.

REFERENCES

• 1: M. Adler and C. Scheideler. Efficient communication strategies for ad hoc wireless networks. Theory of Computing Systems, 33:337--391, 2000.
• 2: Khaled Alzoubi , Xiang-Yang Li , Yu Wang , Peng-Jun Wan , Ophir Frieder, Geometric Spanners for Wireless Ad Hoc Networks, IEEE Transactions on Parallel and Distributed Systems, v.14 n.4, p.408-421, April 2003 [doi>10.1109/TPDS.2003.1195412]
• 3: K. Alzoubi P.-J. Wan and O. Frieder. Distributed construction of connected dominating set in wireless ad hoc networks. In IEEE Infocom '02, 2002.
• 4: K. Alzoubi , P.-J. Wan , O. Frieder, New Distributed Algorithm for Connected Dominating Set in Wireless Ad Hoc Networks, Proceedings of the 35th Annual Hawaii International Conference on System Sciences (HICSS'02)-Volume 9, p.297, January 07-10, 2002
• 5: X. Cheng, D. Huang, W. Li, W. Wu, and D. Z. Du. A polynomial-time approximation scheme for the minimum-connected dominating set in ad hoc wireless networks. Networks: An International Journal, 42, 2003.
• 6: S. Choi. IEEE 802.11e MAC-level FEC performance evaluation and enhancement. In GLOBECOM '02, 2002.
• 7: 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]
• 8: Edsger W. Dijkstra, Self-stabilizing systems in spite of distributed control, Communications of the ACM, v.17 n.11, p.643-644, Nov. 1974 [doi>10.1145/361179.361202]
• 9: Devdatt Dubhashi , Alessandro Mei , Alessandro Panconesi , Jaikumar Radhakrishnan , Arvind Srinivasan, Fast distributed algorithms for (weakly) connected dominating sets and linear-size skeletons, Proceedings of the fourteenth annual ACM-SIAM symposium on Discrete algorithms, January 12-14, 2003, Baltimore, Maryland
• 10: K.R. Gabriel and R.R. Sokal. A new statistical approach to geographic variation analysis. Systematic Zoology, 18:259--278, 1969.
• 11: Jie Gao , Leonidas J. Guibas , John Hershberger , Li Zhang , An Zhu, Geometric spanner for routing in mobile networks, Proceedings of the 2nd ACM international symposium on Mobile ad hoc networking & computing, October 04-05, 2001, Long Beach, CA, USA [doi>10.1145/501422.501424]
• 12: P. Gupta and P.R. Kumar. The capacity of wireless networks. IEEE Transactions on Information Theory, IT-46(2):388--404, 2000.
• 13: P. Gupta and P.R. Kumar. Internets in the sky: The capacity of three dimensional wireless networks. Communications in Information and Systems, 1(1):33--50, 2001.
• 14: P. Gupta and P.R. Kumar. Towards an information theory of large networks: An achievable rate region. In IEEE International Symposium on Information Theory (ISIT 2001), 2001.
• 15: Hai Huang , Andréa W. Richa , Michael Segal, Approximation algorithms for the mobile piercing set problem with applications to clustering in ad-hoc networks, Mobile Networks and Applications, v.9 n.2, p.151-161, April 2004 [doi>10.1023/B:MONE.0000013626.53247.1c]
• 16: L. Jia, R. Rajaraman, and R. Suel. An efficient distributed algorithm for constructing small dominating sets. In Proc. of the 20th ACM Symposium on Principles of Distributed Computing (PODC), 2001.
• 17: Tomasz Jurdzinski , Grzegorz Stachowiak, Probabilistic Algorithms for the Wakeup Problem in Single-Hop Radio Networks, Proceedings of the 13th International Symposium on Algorithms and Computation, p.535-549, November 21-23, 2002
• 18: J. Mark Keil , Carl A. Gutwin, The Delauney Triangulation Closely Approximates the Complete Euclidean Graph, Proceedings of the Workshop on Algorithms and Data Structures, p.47-56, August 17-19, 1989
• 19: F. Kuhn, T. Moscibroda, and R. Wattenhofer. Radio network clustering from scratch. In European Symposium on Algorithms (ESA), 2004.
• 20: Fabian Kuhn , Roger Wattenhofer, Constant-time distributed dominating set approximation, Proceedings of the twenty-second annual symposium on Principles of distributed computing, p.25-32, July 13-16, 2003, Boston, Massachusetts [doi>10.1145/872035.872040]
• 21: Fabian Kuhn , Roger Wattenhofer , Yan Zhang , Aaron Zollinger, Geometric ad-hoc routing: of theory and practice, Proceedings of the twenty-second annual symposium on Principles of distributed computing, p.63-72, July 13-16, 2003, Boston, Massachusetts [doi>10.1145/872035.872044]
• 22: 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]
• 23: J. Kuruvila, A. Nayak, and I. Stojmenovic. Hop count optimal position based packet routing algorithms for ad hoc wireless networks with a realistic physical layer. In 1st IEEE International Conference on Mobile Ad-hoc and Sensor Systems (MASS), 2004.
• 24: X.-Y. Li, G. Calinescu, and P.-J. Wan. Distributed construction of planar spanner and routing for ad hoc wireless networks. In IEEE INFOCOM, pages 1268--1277, 2002.
• 25: X.-Y. Li, P.-J. Wan, and Y. Wang. Power efficient and sparse spanner or wireless ad hoc networks. In IEEE International Conference on Computer Communications and Networks (ICCCN), pages 564--567, 2001.
• 26: X.-Y. Li , P.-J. Wan , Y. Wang , O. Frieder, Sparse Power Efficient Topology for Wireless Networks, Proceedings of the 35th Annual Hawaii International Conference on System Sciences (HICSS'02)-Volume 9, p.296.2, January 07-10, 2002
• 27: M Luby, A simple parallel algorithm for the maximal independent set problem, Proceedings of the seventeenth annual ACM symposium on Theory of computing, p.1-10, May 06-08, 1985, Providence, Rhode Island, United States [doi>10.1145/22145.22146]
• 28: IEEE P802.11a/D7.0-1999. Wireless lan medium access control (mac) and physical layer (phy) specification: High speed physical layer in the 6 ghz band. IEEE, New York, July 1999.
• 29: S. Parthasarathy and R. Gandhi. Distributed algorithms for coloring and domination in wireless ad hoc networks. In Proc. of FSTTCS, 2004.
• 30: L. Quin and T. Kunz. On-demand routing in MANETs: The impact of a realistic physical layer model. In Proc. of the 2nd International Conference ADHOC-NOW, pages 37--48, 2003.
• 31: Theodore S. Rappaport, Wireless Communications: Principles and Practice, IEEE Press, Piscataway, NJ, 1996
• 32: Wen-Zhan Song , Yu Wang , Xiang-Yang Li , Ophir Frieder, Localized algorithms for energy efficient topology in wireless ad hoc networks, Proceedings of the 5th ACM international symposium on Mobile ad hoc networking and computing, May 24-26, 2004, Roppongi Hills, Tokyo, Japan [doi>10.1145/989459.989473]
• 33: Yu Wang , Xiang-Yang Li, Localized construction of bounded degree and planar spanner for wireless ad hoc networks, Proceedings of the 2003 joint workshop on Foundations of mobile computing, p.59-68, September 19, 2003, San Diego, CA, USA [doi>10.1145/941079.941088]
• 34: Khaled Alzoubi , Xiang-Yang Li , Yu Wang , Peng-Jun Wan , Ophir Frieder, Geometric Spanners for Wireless Ad Hoc Networks, IEEE Transactions on Parallel and Distributed Systems, v.14 n.4, p.408-421, April 2003 [doi>10.1109/TPDS.2003.1195412]
• 35: R. Wattenhofer, J. Li Li, P. Bahl, and Y.-M. Wang. Distributed topology control for wireless multihop ad-hoc networks. In IEEE INFOCOM '01, pages 1388--1397, 2001.
• 36: Andrew Chi Chih Yao. On constructing minimum spanning trees in k-dimensional spaces and related problems. SIAM Journal on Computing, 11(4):721--736, 1982.

INDEX TERMS

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

Additional Classification:
  F. Theory of Computation
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY
      F.2.2 Nonnumerical Algorithms and Problems
          Subjects: Computations on discrete structures

General Terms:
Algorithms, Theory

Keywords:
ad hoc networks, dominating set, self-stabilization, spanner