Sleep scheduling and lifetime maximization in sensor networks: fundamental limits and optimal solutions

ABSTRACT

Energy efficiency is a very critical consideration in the design of low cost sensor networks which typically have fairly low node battery life. This raises the need for providing periodic sleep cycles for the radios in the sensor nodes. Keeping sensors in sleep state also implies that node to sink communication incurs certain delays and there exists a threshold on the duty cycling for the communication delay to be bounded, giving rise to an upperbound on the lifetime of the network i.e., the time until at least one node in the network is able to communicate its sensed data to the sink. This paper aims at establishing tight analytical bounds on the sleeping probabilities of nodes and on the achievable lifetime of wireless sensor networks in a very generic setting. Bounds on the sleeping probability need to be satisfied for proper network functionality. Further, an energy efficient deployment scheme is suggested wherein the battery power depletion is fairly uniformly deployed throughout the network. This scheme makes use of the availability of low power auxiliary channel listening radio. With this scheme, we shown that an improvement in lifetime by a factor of O(√n overlog n) over uniform distribution of nodes is achievable, where n is the number of nodes in the network. We also show that the throughput capacity of the network is also improved by the same factor. We show also that the maximum lifetime of the network is bounded above by O(n^3/2 over √log n). Further, the accuracy of our analysis is verified by the simulation results presented.

REFERENCES

• 1: I. F. Akyildiz, W. Su, Y. Sankarasubramaniam, and E. Cayirci, "A survey on sensor networks," IEEE Communications Magazine, pp. 102--114, August 2002.
• 2: W. Ye, J. Heidemann, and D. Estrin, "An energy-efficient mac protocol for wireless sensor networks," in INFOCOM 2002: Proceedings of the Twenty-First Annual Joint Conference of the IEEE Computer and Communications Societies, vol. 3, IEEE, June 2002.
• 3: Tijs van Dam , Koen Langendoen, An adaptive energy-efficient MAC protocol for 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.958512]
• 4: R. Zheng and R. Kravets, "On-demand power management for ad hoc networks," in INFOCOM 2003. Twenty-Second Annual Joint Conference of the IEEE Computer and Communications Societies, vol. 1, (San Francisco), IEEE, March 2003.
• 5: Wei Ye , John Heidemann , Deborah Estrin, Medium access control with coordinated adaptive sleeping for wireless sensor networks, IEEE/ACM Transactions on Networking (TON), v.12 n.3, p.493-506, June 2004 [doi>10.1109/TNET.2004.828953]
• 6: J. Deng, Y. S. Han, W. B. Heinzelman, and P. K. Varshney, "Balanced-energy sleep scheduling scheme for high density cluster-based sensor networks," Computer Communications: special issue on ASWN04, pp. 1631--1542, September 2005.
• 7: G. Lu, N. Sadagopan, B. Krishnamachari, and A. Goel, "Delay efficient sleep scheduling in wireless sensor networks," in INFOCOM 2005. 24th Annual Joint Conference of the IEEE Computer and Communications Societies, vol. 4, pp. 2470--2481, IEEE, March 2005.
• 8: Qing Cao , Tarek Abdelzaher , Tian He , John Stankovic, Towards optimal sleep scheduling in sensor networks for rare-event detection, Proceedings of the 4th international symposium on Information processing in sensor networks, April 24-27, 2005, Los Angeles, California
• 9: Arvind Giridhar , P. R. Kumar, Maximizing the functional lifetime of sensor networks, Proceedings of the 4th international symposium on Information processing in sensor networks, April 24-27, 2005, Los Angeles, California
• 10: M. J. Miller and N. H. Vaidya, "Minimizing energy consumption in sensor networks using a wakeup radio," in Wireless Communications and Networking Conference (WCNC 2004)), vol. 4, pp. 2335--2340, IEEE, March 2004.
• 11: L. C. Z. C. Guo and J. M. Rabaey, "Low power distributed mac for ad hoc sensor radio networks," in Proceedings of IEEE GlobeCom 2001, vol. 5, (San Antonio), pp. 2944--2948, IEEE, November 2001.
• 12: M. Penrose, Random Geometric Graphs. Oxford University Press, 2003.
• 13: K. C. H. Pishro-Nik and F. Fekri, "On connectivity properties of large-scale wireless sensor networks," in Proc. First Annual Communications Society Conf. on Sensor Communications and Networks Santa Clara, pp. 498--507, IEEE, 4--7 October 2004.
• 14: P. Gupta and P. R. Kumar, "The capacity of wireless networks," IEEE Trans. Inform. Theory, vol. 46, no. 2, pp. 388--404, 2000.
• 15: Brad Karp , H. T. Kung, GPSR: greedy perimeter stateless routing for wireless networks, Proceedings of the 6th annual international conference on Mobile computing and networking, p.243-254, August 06-11, 2000, Boston, Massachusetts, United States [doi>10.1145/345910.345953]

INDEX TERMS

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

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

General Terms:
Design, Performance, Theory

Keywords:
MAC, efficient deployment, energy efficiency, lifetime, power management, random deployment, sensor networks, sleep scheduling