Network coverage using low duty-cycled sensors: random & coordinated sleep algorithms

ABSTRACT

This paper investigates the problem of providing network coverage using wireless sensors that operate on low duty cycles (measured by the percentage time a sensor is on or active), i.e., each sensor alternates between active and sleep states to conserve energy with an average sleep period (much) longer than the active period. The dynamic change in topology as a result of such duty-cycling has potentially disruptive effect on the operation and performance of the network. This is compensated by adding redundancy in the sensor deployment. In this paper we examine the fundamental relationship between the reduction in sensor duty cycle and the required level of redundancy for a fixed performance measure, and explore the design of good sensor sleep schedules. In particular, we consider two types of mechanisms, the random sleep type where each sensor keeps an active-sleep schedule independent of another, and the coordinated sleep type where sensors coordinate with each other in reaching an active-sleep schedule. Both types are studied within the context of providing network coverage. We present specific scheduling algorithms within each type, and illustrate their coverage and duty cycle properties via both analysis and simulation. We show with either type of sleep schedule the benefit of added redundancy saturates at some point in that the reduction in duty cycles starts to diminish beyond a certain threshold in deployment redundancy. We also show that at the expense of extra control overhead, a coordinated sleep schedule is more robust and can achieve higher duty cycle reduction with the same amount of redundancy compared to a random sleep schedule.

REFERENCES

• 1: Curt Schurgers , Vlasios Tsiatsis , Saurabh Ganeriwal , Mani Srivastava, Optimizing Sensor Networks in the Energy-Latency-Density Design Space, IEEE Transactions on Mobile Computing, v.1 n.1, p.70-80, January 2002 [doi>10.1109/TMC.2002.1011060]
• 2: Curt Schurgers , Vlasios Tsiatsis , Saurabh Ganeriwal , Mani Srivastava, Topology management for sensor networks: exploiting latency and density, Proceedings of the 3rd ACM international symposium on Mobile ad hoc networking & computing, June 09-11, 2002, Lausanne, Switzerland [doi>10.1145/513800.513817]
• 3: Elson, J., Romer, K.: Wireless sensor networks: A new regime for time synchronization. In: The First Workshop on Hot Topics In Networks (HotNets-I). (2002).
• 4: Feng Xue , P. R. Kumar, The number of neighbors needed for connectivity of wireless networks, Wireless Networks, v.10 n.2, p.169-181, March 2004 [doi>10.1023/B:WINE.0000013081.09837.c0]
• 5: Cox, D.: Renewal Theory. Methuen and Co. LTD Science Paperbacks (1970).
• 6: Khaled M. Faud Elsayed , Harry G. Perros, The superposition of discrete-time Markov renewal processes with an application to statistical multiplexing of bursty traffic sources, Applied Mathematics and Computation, v.115 n.1, p.43-62, Oct. 6, 2000 [doi>10.1016/S0096-3003(99)00134-4]
• 7: Stoyan, D., Kendall, W.S., Mecke, J.: Stochastic Geometry and Its Applications, Second Edition. Wiley Series in Probability and Statistics (1995).
• 8: Rex Min , Manish Bhardwaj , Seong-Hwan Cho , Eugene Shih , Amit Sinha , Alice Wang , Anantha Chandrakasan, Low-Power Wireless Sensor Networks, Proceedings of the The 14th International Conference on VLSI Design (VLSID '01), p.205, January 03-07, 2001
• 9: Amit Sinha , Anantha Chandrakasan, Operating System and Algorithmic Techniques for Energy Scalable Wireless Sensor Networks, Proceedings of the Second International Conference on Mobile Data Management, p.199-209, January 08-10, 2001
• 10: 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]
• 11: Slijepcevic, S., Potkonjak, M.: Power efficient organization of wireless sensor networks. In: IEEE INternational Conference on Communications (ICC). (2001).
• 12: Ting Yan , Tian He , John A. Stankovic, Differentiated surveillance 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.958498]
• 13: Fan Ye , Gary Zhong , Songwu Lu , Lixia Zhang, PEAS: A Robust Energy Conserving Protocol for Long-lived Sensor Networks, Proceedings of the 10th IEEE International Conference on Network Protocols, p.200-201, November 12-15, 2002
• 14: Bhardwaj, M., Chandrakasan, A.P.: Bounding the lifetime of sensor networks via optimal role assignments. In: Joint Conference of the IEEE Computer and Communications Societies (INFOCOM). (2002).
• 15: Chalermek Intanagonwiwat , Deborah Estrin , Ramesh Govindan , John Heidemann, Impact of Network Density on Data Aggregation in Wireless Sensor Networks, Proceedings of the 22 nd International Conference on Distributed Computing Systems (ICDCS'02), p.457, July 02-05, 2002
• 16: Liu, B., Towsley, D.: On the coverage and detectability of large-scale wireless sensor networks. In: In Proc. of the Modeling and Optimization in Mobile, Ad Hoc and Wireless Networks Conference (WiOpt). (2003).
• 17: Shakkottai, S., Srikant, R., Shroff, N.: Unreliable sensor grids: Coverage, connectivity and diameter. In: Joint Conference of the IEEE Computer and Communications Societies (INFOCOM). (2003).
• 18: 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]
• 19: 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]
• 20: Mequerdichian, S., Koushanfar, F., Potkonjak, M., Srivastava, M.B.: Coverage problems in wireless ad-hoc sensor networks. In: Joint Conference of the IEEE Computer and Communications Societies (INFOCOM). (2001).
• 21: Li, X.Y., Wan, P.J., Frieder, O.: Coverage in wireless ad hoc sensor networks. IEEE Transactions on Cumputers 52 (2003).
• 22: 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]
• 23: Ye, W., Heidemann, J., Estrin, D.: An energy-efficient mac protocol for wireless sensor networks. In: Joint Conference of the IEEE Computer and Communications Societies (INFOCOM). (2002).
• 24: Nagpal, R., Shrobe, H., Bachrach, J.: Organizing a global coordinate system from local information on an ad hoc sensor network. In: The 2nd International Workshop on Information Processing in Sensor Networks (IPSN). (2003).
• 25: Andreas Savvides , Heemin Park , Mani B. Srivastava, The bits and flops of the n-hop multilateration primitive for node localization problems, Proceedings of the 1st ACM international workshop on Wireless sensor networks and applications, September 28-28, 2002, Atlanta, Georgia, USA [doi>10.1145/570738.570755]
• 26: Niculescu, D., Nath, B.: Ad hoc positioning system (aps) using aoa. In: Joint Conference of the IEEE Computer and Communications Societies (INFOCOM). (2003).
• 27: Tian He , Chengdu Huang , Brian M. Blum , John A. Stankovic , Tarek Abdelzaher, Range-free localization schemes for large scale sensor networks, Proceedings of the 9th annual international conference on Mobile computing and networking, September 14-19, 2003, San Diego, CA, USA [doi>10.1145/938985.938995]

INDEX TERMS

Primary Classification:
  C. Computer Systems Organization
  C.4 PERFORMANCE OF SYSTEMS
      Subjects: Reliability, availability, and serviceability

General Terms:
Algorithms, Design, Performance

Keywords:
coverage, energy efficiency, sensor networks, superposition of alternating renewal processes