A coverage-preserving node scheduling scheme for large wireless sensor networks

ABSTRACT

In wireless sensor networks that consist of a large number of low-power, short-lived, unreliable sensors, one of the main design challenges is to obtain long system lifetime, as well as maintain sufficient sensing coverage and reliability. In this paper, we propose a node-scheduling scheme, which can reduce system overall energy consumption, therefore increasing system lifetime, by turning off some redundant nodes. Our coverage-based off-duty eligibility rule and backoff-based node-scheduling scheme guarantees that the original sensing coverage is maintained after turning off redundant nodes. We implement our proposed scheme in NS-2 as an extension of the LEACH protocol. We compare the energy consumption of LEACH with and without the extension and analyze the effectiveness of our scheme in terms of energy saving. Simulation results show that our scheme can preserve the system coverage to the maximum extent. In addition, after the node-scheduling scheme turns off some nodes, certain redundancy is still guaranteed, which we believe can provide enough sensing reliability in many applications.

REFERENCES

• 1: 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]
• 2: 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]
• 3: Alberto Cerpa , Jeremy Elson , Michael Hamilton , Jerry Zhao , Deborah Estrin , Lewis Girod, Habitat monitoring: application driver for wireless communications technology, Workshop on Data communication in Latin America and the Caribbean, p.20-41, April 2001, San Jose, Costa Rica [doi>10.1145/371626.371720]
• 4: 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]
• 5: 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]
• 6: A. Porret, T. Melly, C. C. Enz, and E. A.Vittoz, A Low-Power Low-Voltage Transceiver Architecture Suitable for Wireless Distributed Sensors Network, IEEE International Symposium on Ciruits and Systems'00, Geneva, 2000.
• 7: Michael J. Dong , K. Geoffrey Yung , Wiliam J. Kaiser, Low power signal processing architectures for network microsensors, Proceedings of the 1997 international symposium on Low power electronics and design, p.173-177, August 18-20, 1997, Monterey, California, United States [doi>10.1145/263272.263320]
• 8: Jan M. Rabaey , M. Josie Ammer , Julio L. da Silva , Danny Patel , Shad Roundy, PicoRadio Supports Ad Hoc Ultra-Low Power Wireless Networking, Computer, v.33 n.7, p.42-48, July 2000 [doi>10.1109/2.869369]
• 9: G. Asada, M. Dong, T. S. Lin, F. Newberg, G. Pottie, W. J. Kaiser, Wireless Integrated Network Sensors: Low Powers Systems on a Chip, Proc of the 24th IEEE European Solid-State Circuits Conference, Elsevier, 1998.
• 10: Wendi Rabiner Heinzelman , Anantha Chandrakasan , Hari Balakrishnan, Energy-Efficient Communication Protocol for Wireless Microsensor Networks, Proceedings of the 33rd Hawaii International Conference on System Sciences-Volume 8, p.8020, January 04-07, 2000
• 11: Chalermek Intanagonwiwat , Ramesh Govindan , Deborah Estrin, Directed diffusion: a scalable and robust communication paradigm for sensor networks, Proceedings of the 6th annual international conference on Mobile computing and networking, p.56-67, August 06-11, 2000, Boston, Massachusetts, United States [doi>10.1145/345910.345920]
• 12: F. Ye, G. Zhong, S. Lu, L. Zhang, Energy Efficient Robust Sensing Coverage in Large Sensor Networks, Technical Report.
• 13: 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]
• 14: Y. Xu, J. Heidemann, D. Estrin, Adaptive Energy-Conserving Routing for Multihop Ad hoc Networks, Technical Report 527, USC/ISI, Oct.2000.
• 15: 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]
• 16: Chalermek Intanagonwiwat , Ramesh Govindan , Deborah Estrin, Directed diffusion: a scalable and robust communication paradigm for sensor networks, Proceedings of the 6th annual international conference on Mobile computing and networking, p.56-67, August 06-11, 2000, Boston, Massachusetts, United States [doi>10.1145/345910.345920]
• 17: V. Rodoplu and T.H.Meng, Minimum Energy Mobile Wireless Networks, IEEE JSAC, Vol. 17, No.8, August 1999.
• 18: L. Li, and J.Y.Halpern, Minimum-Energy Mobile Wireless Networks Revisited, IEEE International Conference on Communications ICC'01, Helsinki, Finland, June 2001.
• 19: R. Wattenhofer, L.Li, P.Bahl, Y.-M.Wang, Distrbuted Topology Control for Power Efficient Operation in Multihop Wireless Ad Hoc Networks, Proc. of the Third Workshop on Mobile Multimedia Communications (MoMuC-3), Princeton, NJ, 1996.
• 20: W.Heinzelman, A.Chandrakasan, and H.Balakrishnan, uAMPS ns Code Extensions, http://www-mtl.mit.edu/research/icsystems/ uamps/leach.
• 21: Wendi Beth Heinzelman , Anantha P. Chandrakasan , Hari Balakrishnan, Application-specific protocol architectures for wireless networks, 2000

INDEX TERMS

Primary Classification:
  F. Theory of Computation
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY
      F.2.2 Nonnumerical Algorithms and Problems
          Subjects: Geometrical problems and computations

Additional Classification:
  F. Theory of Computation
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY
      F.2.2 Nonnumerical Algorithms and Problems
          Subjects: Routing and layout

General Terms:
Algorithms, Experimentation, Measurement, Performance, Reliability, Theory

Keywords:
coverage, node scheduling, wireless sensor networks