Integrated coverage and connectivity configuration in wireless sensor networks

ABSTRACT

An effective approach for energy conservation in wireless sensor networks is scheduling sleep intervals for extraneous nodes, while the remaining nodes stay active to provide continuous service. For the sensor network to operate successfully, the active nodes must maintain both sensing coverage and network connectivity. Furthermore, the network must be able to configure itself to any feasible degrees of coverage and connectivity in order to support different applications and environments with diverse requirements. This paper presents the design and analysis of novel protocols that can dynamically configure a network to achieve guaranteed degrees of coverage and connectivity. This work differs from existing connectivity or coverage maintenance protocols in several key ways: 1) We present a Coverage Configuration Protocol (CCP) that can provide different degrees of coverage requested by applications. This flexibility allows the network to self-configure for a wide range of applications and (possibly dynamic) environments. 2) We provide a geometric analysis of the relationship between coverage and connectivity. This analysis yields key insights for treating coverage and connectivity in a unified framework: this is in sharp contrast to several existing approaches that address the two problems in isolation. 3) Finally, we integrate CCP with SPAN to provide both coverage and connectivity guarantees. We demonstrate the capability of our protocols to provide guaranteed coverage and connectivity configurations, through both geometric analysis and extensive simulations.

REFERENCES

• 1: A. Cerpa and D. Estrin, "ASCENT: Adaptive Self-Configuring Sensor Networks Topologies," INFOCOM, June 2002.
• 2: Krishnendu Chakrabarty , S. Sitharama Iyengar , Hairong Qi , Eungchun Cho, Grid Coverage for Surveillance and Target Location in Distributed Sensor Networks, IEEE Transactions on Computers, v.51 n.12, p.1448-1453, December 2002 [doi>10.1109/TC.2002.1146711]
• 3: Benjie Chen , Kyle Jamieson , Hari Balakrishnan , Robert Morris, Span: An energy-efficient coordination algorithm for topology maintenance in Ad Hoc wireless networks, Proceedings of the 7th annual international conference on Mobile computing and networking, p.85-96, July 2001, Rome, Italy [doi>10.1145/381677.381686]
• 4: CMU Monarch Extensions to ns. http://www.monarch.cs.cmu.edu/.
• 5: Thomas Clouqueur , Veradej Phipatanasuphorn , Parameswaran Ramanathan , Kewal K. Saluja, Sensor deployment strategy for target detection, Proceedings of the 1st ACM international workshop on Wireless sensor networks and applications, September 28-28, 2002, Atlanta, Georgia, USA [doi>10.1145/570738.570745]
• 6: T. Clouqueur, P. Ramanathan, K. K. Saluja, and K.-C. Wang. "Value-fusion versus decision-fusion for fault-tolerance in collaborative target detection in sensor networks." In Proceedings of Fourth International Conference on Information Fusion, Aug. 2001.
• 7: A. D'Costa and A. Sayeed, "Collaborative Signal Processing for Distributed Classification in Sensor Networks," The 2nd International Workshop on Information Processing in Sensor Networks (IPSN 2003), April 22-23, 2003, Palo Alto, CA.
• 8: P. Hall, Introduction to the Theory of Coverage Processes. John Wiley & Sons Inc., New York, 1998.
• 9: D. Li, K. Wong, Y. H. Hu, A. Sayeed. "Detection, Classification and Tracking of Targets in Distributed Sensor Networks", IEEE Signal Processing Magazine, Volume: 19 Issue: 2, Mar 2002.
• 10: S. Meguerdichian, F. Koushanfar, M. Potkonjak, and M. Srivastava, "Coverage Problems in Wireless Ad-Hoc Sensor Networks." INFOCOM'01, Vol 3, pp. 1380--1387, April 2001.
• 11: Seapahn Meguerdichian , Farinaz Koushanfar , Gang Qu , Miodrag Potkonjak, Exposure in wireless Ad-Hoc sensor networks, Proceedings of the 7th annual international conference on Mobile computing and networking, p.139-150, July 2001, Rome, Italy [doi>10.1145/381677.381691]
• 12: S. Meguerdichian and M. Potkonjak. "Low Power 01 Coverage and Scheduling Techniques in Sensor Networks." UCLA Technical Reports 030001. January 2003.
• 13: S. Pattem, S. Poduri, and B. Krishnamachari, "Energy-Quality Tradeoffs for Target Tracking in Wireless Sensor Networks," The 2nd Workshop on Information Processing in Sensor Networks (IPSN 2003), April 2003.
• 14: Di Tian , Nicolas D. Georganas, A coverage-preserving node scheduling scheme for large wireless sensor networks, Proceedings of the 1st ACM international workshop on Wireless sensor networks and applications, September 28-28, 2002, Atlanta, Georgia, USA [doi>10.1145/570738.570744]
• 15: Pramod K. Varshney, Distributed Detection and Data Fusion, Springer-Verlag New York, Inc., Secaucus, NJ, 1996
• 16: Y. Xu, J. Heidemann, and D. Estrin, "Adaptive Energy-Conserving Routing for Multihop Ad Hoc Networks," Research Report 527, USCInformation Sciences Institute, October 2000.
• 17: Ya Xu , John Heidemann , Deborah Estrin, Geography-informed energy conservation for Ad Hoc routing, Proceedings of the 7th annual international conference on Mobile computing and networking, p.70-84, July 2001, Rome, Italy [doi>10.1145/381677.381685]
• 18: Fan Ye , Gary Zhong , Jesse Cheng , Songwu Lu , Lixia Zhang, PEAS: A Robust Energy Conserving Protocol for Long-lived Sensor Networks, Proceedings of the 23rd International Conference on Distributed Computing Systems, p.28, May 19-22, 2003

INDEX TERMS

Primary Classification:
  C. Computer Systems Organization
  C.2 COMPUTER-COMMUNICATION NETWORKS
      C.2.2 Network Protocols
          Subjects: Applications (SMTP, FTP, etc.)

Additional Classification:
  C. Computer Systems Organization
  C.3 SPECIAL-PURPOSE AND APPLICATION-BASED SYSTEMS
      Subjects: Real-time and embedded systems

General Terms:
Algorithms, Design, Experimentation

Keywords:
connectivity, coverage, energy conservation, network geometry, sensor network, topology maintenance, wireless ad hoc network