On k-coverage in a mostly sleeping sensor network

ABSTRACT

Sensor networks are often desired to last many times longer than the active lifetime of individual sensors. This is usually achieved by putting sensors to sleep for most of their lifetime. On the other hand, surveillance kind of applications require guaranteed k-coverage of the protected region at all times. As a result, determining the appropriate number of sensors to deploy that achieves both goals simultaneously becomes a challenging problem. In this paper, we consider three kinds of deployments for a sensor network on a unit square - a √n x √n grid, random uniform (for all n points), and Poisson (with density n). In all three deployments, each sensor is active with probability p, independently from the others. Then, we claim that the critical value of the function npπr²/log(np) is 1 for the event of k-coverage of every point. We also provide an upper bound on the window of this phase transition. Although the conditions for the three deployments are similar, we obtain sharper bounds for the random deployments than the grid deployment, which occurs due to the boundary condition. In this paper, we also provide corrections to previously published results for the grid deployment model. Finally, we use simulation to show the usefulness of our analysis in real deployment scenarios.

REFERENCES

• 1: N. Alon and J. H. Spencer. The Probabilistic Method. John Wiley & Sons, 2000.
• 2: A. Arora and et al. Line in the sand: A wireless sensor network for target detection, classification, and tracking. Technical report, OSU-CISRC-12/03-TR71, Ohio State University, 2003.
• 3: Christian Bettstetter, On the minimum node degree and connectivity of a wireless multihop network, Proceedings of the 3rd ACM international symposium on Mobile ad hoc networking & computing, June 09-11, 2002, Lausanne, Switzerland [doi>10.1145/513800.513811]
• 4: B. Bollobas. Random Graphs. Cambridge University Press, 2001.
• 5: Crossbow. Power management and batteries. Application Notes, Available at http://www.xbow.com/Support/appnotes.htm, 2004.
• 6: Jeremy Elson , Lewis Girod , Deborah Estrin, Fine-grained network time synchronization using reference broadcasts, Proceedings of the 5th symposium on Operating systems design and implementation

  Due to copyright restrictions we are not able to make the PDFs for this conference available for downloading

  , December 09-11, 2002, Boston, Massachusetts [doi>10.1145/1060289.1060304]
• 7: Saurabh Ganeriwal , Ram Kumar , Mani B. Srivastava, Timing-sync protocol for sensor networks, Proceedings of the 1st international conference on Embedded networked sensor systems, November 05-07, 2003, Los Angeles, California, USA [doi>10.1145/958491.958508]
• 8: P. Gupta and P. R. Kumar. Critical power for asymptotic connectivity in wireless networks. In IEEE 37th Conference on Decision and Control, pages 1106--1110, Tampa, FL, 1998.
• 9: D. L. Hall and J. Llinas. Handbook of Multisensor Data Fusion. CRC Press, 2001.
• 10: P. Hall. Introduction to the Theory of Coverage Processes. John Wiley & Sons, 1988.
• 11: Tian He , Sudha Krishnamurthy , John A. Stankovic , Tarek Abdelzaher , Liqian Luo , Radu Stoleru , Ting Yan , Lin Gu , Jonathan Hui , Bruce Krogh, Energy-efficient surveillance system using wireless sensor networks, Proceedings of the 2nd international conference on Mobile systems, applications, and services, June 06-09, 2004, Boston, MA, USA [doi>10.1145/990064.990096]
• 12: M. Horton, D. E. Culler, K. Pister, J. Hill, R. Szewczyk, and A. Woo. The commercialization of microsensor motes, In Sensors, volume 19, no. 4, pages 40--48, April 2002.
• 13: Chi-Fu Huang , Yu-Chee Tseng, The coverage problem in a wireless sensor network, Proceedings of the 2nd ACM international conference on Wireless sensor networks and applications, September 19-19, 2003, San Diego, CA, USA [doi>10.1145/941350.941367]
• 14: J. Hui, Z. Ren, and B. H. Krogh. Sentry-based power management in wireless sensor networks. In Proceedings of IPSN, pages 458--472, Palo Alto, CA, 2003.
• 15: Xiang-Yang Li , Peng-Jun Wan , Yu Wang , Chih-Wei Yi, Fault tolerant deployment and topology control in wireless networks, Proceedings of the 4th ACM international symposium on Mobile ad hoc networking & computing, June 01-03, 2003, Annapolis, Maryland, USA [doi>10.1145/778415.778431]
• 16: R. Meester and R. Roy. Continuum Percolation. Cambridge University Press, 1996.
• 17: S. M. Ross. Introduction to Probability Models. Academic Press, 2000.
• 18: S. Shakkottai, R. Srikant, and N. B. Shroff. Unreliable sensor grids: Coverage, connectivity and diameter. In Proceedings of IEEE INFOCOM, volume 2, pages 1073--1083, San Francisco, CA, 2003.
• 19: R. Szewczyk, J. Polastre, A. M. Mainwaring, and D. E. Culler. Lessons from a sensor network expedition. In EWSN, Berlin, Germany, 2004.
• 20: Xiaorui Wang , Guoliang Xing , Yuanfang Zhang , Chenyang Lu , Robert Pless , Christopher Gill, Integrated coverage and connectivity configuration in wireless sensor networks, Proceedings of the 1st international conference on Embedded networked sensor systems, November 05-07, 2003, Los Angeles, California, USA [doi>10.1145/958491.958496]
• 21: Honghai Zhang , Jennifer Hou, On deriving the upper bound of α-lifetime for large sensor 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.989475]
• 22: Jerry Zhao , Ramesh Govindan, Understanding packet delivery performance in dense wireless sensor networks, Proceedings of the 1st international conference on Embedded networked sensor systems, November 05-07, 2003, Los Angeles, California, USA [doi>10.1145/958491.958493]

INDEX TERMS

Primary Classification:
  G. Mathematics of Computing
  G.3 PROBABILITY AND STATISTICS
      Subjects: Stochastic processes

Additional Classification:
  C. Computer Systems Organization
  C.2 COMPUTER-COMMUNICATION NETWORKS
      C.2.1 Network Architecture and Design
          Subjects: Network topology

General Terms:
Theory

Keywords:
connectivity, coverage, deterministic deployment, power management, random deployment, sensor network