Localized topology control for heterogeneous wireless sensor networks

ABSTRACT

This article studies topology control in heterogeneous wireless sensor networks, where different wireless sensors may have different maximum transmission ranges and two nodes can communicate directly with each other if and only if they are within the maximum transmission range of each other. We present several localized topology control strategies in which every wireless sensor maintains logical communication links to only a selected small subset of its physical neighbors using information of sensors within its local neighborhood in a heterogeneous network environment. We prove that the global logical network topologies formed by these locally selected links are sparse and/or power efficient and our methods are communication efficient. Here a structure is power efficient if the total power consumption of the least cost path connecting any two nodes in it is no more than a small constant factor of that in the original heterogeneous communication network. By utilizing the wireless broadcast channel capability, and assuming that a message sent by a sensor node will be received by all sensors within its transmission region with at most a constant number of transmissions, we prove that all our methods use at most O(n) total messages, where each message has O(log n) bits. We also conduct extensive simulations to study the practical performance of our methods.

REFERENCES

• 1: Sunil Arya , Gautam Das , David M. Mount , Jeffrey S. Salowe , Michiel Smid, Euclidean spanners: short, thin, and lanky, Proceedings of the twenty-seventh annual ACM symposium on Theory of computing, p.489-498, May 29-June 01, 1995, Las Vegas, Nevada, United States [doi>10.1145/225058.225191]
• 2: Lali Barriére , Pierre Fraigniaud , Lata Narayanan, Robust position-based routing in wireless Ad Hoc networks with unstable transmission ranges, Proceedings of the 5th international workshop on Discrete algorithms and methods for mobile computing and communications, p.19-27, July 2001, Rome, Italy [doi>10.1145/381448.381451]
• 3: Cheng, X., Thaeler, A., Xue, G., and Chen, D. 2004. TPS: A time-based positioning scheme for outdoor wireless sensor networks. In Proceedings of the 23nd Annual Joint Conference of the IEEE Computer and Communications Societies (INFOCOM).
• 4: Gabriel, K. and Sokal, R. 1969. A new statistical approach to geographic variation analysis. Systematic Zoology 18, 259--278.
• 5: Hu, L. 1993. Topology control for multihop packet radio networks. IEEE Trans. Comm. 41, 10.
• 6: Lingxuan Hu , David Evans, Localization for mobile sensor networks, Proceedings of the 10th annual international conference on Mobile computing and networking, September 26-October 01, 2004, Philadelphia, PA, USA [doi>10.1145/1023720.1023726]
• 7: Kapoor, S. and Li, X.-Y. 2003. Proximity Structures for Geometric Graphs. In Proceedings of Workshop on Algorithms and Data Structures (WADS 2003).
• 8: 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]
• 9: Li Li , Joseph Y. Halpern , Paramvir Bahl , Yi-Min Wang , Roger Wattenhofer, Analysis of a cone-based distributed topology control algorithm for wireless multi-hop networks, Proceedings of the twentieth annual ACM symposium on Principles of distributed computing, p.264-273, August 2001, Newport, Rhode Island, United States [doi>10.1145/383962.384043]
• 10: Li, N., Hou, J. C., and Sha, L. 2004. Topology control in heterogeneous wireless networks: Problems and solutions. In Proceedings of the 23nd Annual Joint Conference of the IEEE Computer and Communications Societies (INFOCOM).
• 11: Li, X.-Y., Calinescu, G., and Wan, P.-J. 2002a. Distributed construction of planar spanner and routing for ad hoc wireless networks. In Proceedings of the 21st Annual Joint Conference of the IEEE Computer and Communications Societies (INFOCOM). Vol. 3.
• 12: Li, X.-Y., Wan, P.-J., and Wang, Y. 2001b. Power efficient and sparse spanner for wireless ad hoc networks. In Proceedings of IEEE Intetnational Conference on Computer Communications and Networks (ICCCN01). 564--567.
• 13: 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
• 14: Lukovszki, T. 1999. New results on geometric spanners and their applications. Ph.D. thesis, University of Paderborn.
• 15: Ravi Prakash, Unidirectional links prove costly in wireless ad hoc networks, Proceedings of the 3rd international workshop on Discrete algorithms and methods for mobile computing and communications, p.15-22, August 20-20, 1999, Seattle, Washington, United States [doi>10.1145/313239.313263]
• 16: Ramanathan, R. and Rosales-Hain, R. 2000. Topology control of multihop wireless networks using transmit power adjustment. In Proceedings of the 20th Annual Joint Conference of the IEEE Computer and Communications Societies (INFOCOM).
• 17: 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]
• 18: Song, W.-Z., Wang, Y., and Li, X.-Y. 2003. Efficient topology control for wireless networks with non-uniform transmission ranges. Manuscript. Enhanced version published at IEEE MASS 2004.
• 19: Toussaint, G. T. 1980. The relative neighborhood graph of a finite planar set. Pattern Recognition 12, 4, 261--268.
• 20: 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]
• 21: Wattenhofer, R., Li, L., Bahl, P., and Wang, Y.-M. 2001. Distributed topology control for wireless multihop ad hoc networks. In Proceedings of the 21st Annual Joint Conference of the IEEE Computer and Communications Societies (INFOCOM).
• 22: Yao, A. C.-C. 1982. On constructing minimum spanning trees in k-dimensional spaces and related problems. SIAM Journal on Computing 11, 721--736.

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:
  C. Computer Systems Organization
  C.2 COMPUTER-COMMUNICATION NETWORKS
      C.2.1 Network Architecture and Design
          Subjects: Network topology

  G. Mathematics of Computing
  G.2 DISCRETE MATHEMATICS
      G.2.2 Graph Theory
          Subjects: Network problems; Graph algorithms

General Terms:
Algorithms, Design, Theory

Keywords:
Graph theory, degree-bounded structure, heterogeneous networks, power consumption, topology control, wireless sensor networks