On deriving the upper bound of α-lifetime for large sensor networks

ABSTRACT

In this paper, we explore the fundamental limits of sensor network lifetime that all algorithms can possibly achieve. Specifically, under the assumptions that nodes are deployed as a Poisson point process with density λ in a square region with side length l and each sensor can cover a unit-area disk, we first derive the necessary and sufficient condition of the node density in order to maintain complete k-coverage with probability approaching 1. With this result, we obtain that if #955; = log l² + (k+2)log log l² + c(l), c(l) → -∞, as l → +∞, the sensor network lifetime (for maintaining complete coverage) is upper bounded by kT with probability approaching 1 as l → +∞, where T is the lifetime of each sensor. Second, we derive, given a fixed node density in a finite (but reasonably large) region, the upper bounds of lifetime when only α-portion of the region is required to be covered at any time. We also carry out simulations to validate the derived results. Simulation results indicate that the derived upper bounds apply not only to networks of large areas but also to small-area networks.

REFERENCES

• 1: I. F. Akyildiz , W. Su , Y. Sankarasubramaniam , E. Cayirci, Wireless sensor networks: a survey, Computer Networks: The International Journal of Computer and Telecommunications Networking, v.38 n.4, p.393-422, 15 March 2002 [doi>10.1016/S1389-1286(01)00302-4]
• 2: KEYENCE America. http://www.keyence.com/products/sensors.html.
• 3: M. Bhardwaj and A. P. Chandrakasan. Bounding the lifetime of sensor network via optimal role assignments. In Proc. of IEEE Infocom 2002.
• 4: M. Bhardwaj and A. P. Chandrakasan. Upper bounds on the lifetime of wireless sensor networks. In Proc. of IEEE International Conference on Communications (ICC) 01.
• 5: Douglas M. Blough , Paolo Santi, Investigating upper bounds on network lifetime extension for cell-based energy conservation techniques in stationary ad hoc networks, Proceedings of the 8th annual international conference on Mobile computing and networking, September 23-28, 2002, Atlanta, Georgia, USA [doi>10.1145/570645.570668]
• 6: B. Chen, K. Jamieson, H. Balakrishnan, and R. Morris. Span: An energy-efficient operation in multihop wireless ad hoc networks. In Proc. of ACM MobiCom'01, 2001.
• 7: Sinem Coleri , Mustafa Ergen , T. John Koo, Lifetime analysis of a sensor network with hybrid automata modelling, Proceedings of the 1st ACM international workshop on Wireless sensor networks and applications, September 28-28, 2002, Atlanta, Georgia, USA [doi>10.1145/570738.570752]
• 8: Deborah Estrin , Ramesh Govindan , John Heidemann , Satish Kumar, Next century challenges: scalable coordination in sensor networks, Proceedings of the 5th annual ACM/IEEE international conference on Mobile computing and networking, p.263-270, August 15-19, 1999, Seattle, Washington, United States [doi>10.1145/313451.313556]
• 9: L. Feeney and M. Nilsson. Investigating the energy consumption of a wireless network interface in an ad hoc networking environment. In Proc. of IEEE Infocom 2001.
• 10: Himanshu Gupta , Samir R. Das , Quinyi Gu, Connected sensor cover: self-organization of sensor networks for efficient query execution, Proceedings of the 4th ACM international symposium on Mobile ad hoc networking & computing, June 01-03, 2003, Annapolis, Maryland, USA [doi>10.1145/778415.778438]
• 11: P. Hall. Introduction to the Theory of Coverage Processes. John Wiley and Sons, 1988.
• 12: Crossbow Technology Inc. http://www.xbow.com/support/support_pdf_files/mts-mda_series_user_manua_revb.pdf.
• 13: J. M. Kahn , R. H. Katz , K. S. J. Pister, Next century challenges: mobile networking for “Smart Dust”, Proceedings of the 5th annual ACM/IEEE international conference on Mobile computing and networking, p.271-278, August 15-19, 1999, Seattle, Washington, United States [doi>10.1145/313451.313558]
• 14: Alan Mainwaring , David Culler , Joseph Polastre , Robert Szewczyk , John Anderson, Wireless sensor networks for habitat monitoring, Proceedings of the 1st ACM international workshop on Wireless sensor networks and applications, September 28-28, 2002, Atlanta, Georgia, USA [doi>10.1145/570738.570751]
• 15: M.D. Penrose. The longest edge of the random minimal spanning tree. Annals of Applied Probability, 7:340--361, 1997.
• 16: S. G. Samko, A. A. Kilbas, and O. I. Marichev. Fractional Integrals and Derivatives, page 9. Yverdon, Switzerland: Gordon and Breach, 1993.
• 17: Infrared Sensor. http://www.interq.or.jp/japan/se-inoue/e_pyro.htm.
• 18: Eugene Shih , Seong-Hwan Cho , Nathan Ickes , Rex Min , Amit Sinha , Alice Wang , Anantha Chandrakasan, Physical layer driven protocol and algorithm design for energy-efficient wireless sensor networks, Proceedings of the 7th annual international conference on Mobile computing and networking, p.272-287, July 2001, Rome, Italy [doi>10.1145/381677.381703]
• 19: 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]
• 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: 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]
• 22: F. Ye, G. Zhong, S. Lu, and L. Zhang. Energy efficient robust sensing coverage in large sensor networks. Technical report, UCLA, 2002.
• 23: 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
• 24: H. Zhang and J. Hou. On deriving the upper bound of alpha-lifetime for large sensor networks. Technical Report UIUCDCS-R-2004-2410, Department of Computer Science, University of Illinois at Urbana-Champaign, Mar 2004.
• 25: H. Zhang and J. C. Hou. Maintaining sensing coverage and connectivity in large sensor networks. Technical Report UIUCDCS-R-2003-2351, Department of Computer Science, University of Illinois at Urbana-Champaign, June 2003.

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:
  G. Mathematics of Computing
  G.3 PROBABILITY AND STATISTICS
      Subjects: Stochastic processes

General Terms:
Performance, Reliability, Theory

Keywords:
coverage, fundamental limits, k-coverage, lifetime, poisson point process, sensor networks