Energy-efficient multihop reprogramming for sensor networks

ABSTRACT

Reprogramming of sensor networks is an important and challenging problem, as it is often necessary to reprogram the sensors in place. In this article, we propose MNP, a multihop reprogramming service designed for sensor networks. One of the problems in reprogramming is the issue of message collision. To reduce the problem of collision, we propose a sender selection algorithm that attempts to guarantee that in a given neighborhood there is at most one source transmitting the program at a time. Furthermore, our sender selection is greedy in that it tries to select the sender that is expected to have the most impact. We use pipelining to enable fast data propagation. MNP is energy efficient because it reduces the active radio time of a sensor node by putting the node into “sleep” state when its neighbors are transmitting a segment that is not of interest. We call this type of sleep contention sleep. To further reduce the energy consumption, we add noreq sleep, where sensor node goes to sleep if none of its neighbors is interested in receiving the segment it is advertising. We also introduce an optional init sleep to reduce the energy consumption in the initial phase of reprogramming. Finally, we investigate the performance of MNP in different network settings.

REFERENCES

• 1: A. Arora , P. Dutta , S. Bapat , V. Kulathumani , H. Zhang , V. Naik , V. Mittal , H. Cao , M. Demirbas , M. Gouda , Y. Choi , T. Herman , S. Kulkarni , U. Arumugam , M. Nesterenko , A. Vora , M. Miyashita, A line in the sand: a wireless sensor network for target detection, classification, and tracking, Computer Networks: The International Journal of Computer and Telecommunications Networking, v.46 n.5, p.605-634, 5 December 2004 [doi>10.1016/j.comnet.2004.06.007]
• 2: Crossbow Technology, Inc. 2003. Mote In-Network Programming User Reference Version 20030315. Crossbow Technology, Inc. http://webs.cs.berkeley.edu/tos/tinyos-1.x/doc/Xnp.pdf.
• 3: Prabal Dutta , Mike Grimmer , Anish Arora , Steven Bibyk , David Culler, Design of a wireless sensor network platform for detecting rare, random, and ephemeral events, Proceedings of the 4th international symposium on Information processing in sensor networks, April 24-27, 2005, Los Angeles, California
• 4: Sally Floyd , Van Jacobson , Ching-Gung Liu , Steven McCanne , Lixia Zhang, A reliable multicast framework for light-weight sessions and application level framing, IEEE/ACM Transactions on Networking (TON), v.5 n.6, p.784-803, Dec. 1997 [doi>10.1109/90.650139]
• 5: 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
• 6: Jason L. Hill , David E. Culler, Mica: A Wireless Platform for Deeply Embedded Networks, IEEE Micro, v.22 n.6, p.12-24, November 2002 [doi>10.1109/MM.2002.1134340]
• 7: Jonathan W. Hui , David Culler, The dynamic behavior of a data dissemination protocol for network programming at scale, Proceedings of the 2nd international conference on Embedded networked sensor systems, November 03-05, 2004, Baltimore, MD, USA [doi>10.1145/1031495.1031506]
• 8: 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]
• 9: Joanna Kulik , Wendi Heinzelman , Hari Balakrishnan, Negotiation-based protocols for disseminating information in wireless sensor networks, Wireless Networks, v.8 n.2/3, p.169-185, March-May 2002 [doi>10.1023/A:1013715909417]
• 10: Kulkarni, S. S. and Arumugam, M. 2005. SS-TDMA: A self-stabilizing MAC for sensor networks. In Sensor Network Operations. IEEE Press.
• 11: Kulkarni, S. S. and Arumugam, M. 2006. Infuse: A TDMA based data dissemination protocol for sensor networks. Int. J. Distrib. Sensor Netw.
• 12: Sandeep S. Kulkarni , Limin Wang, MNP: Multihop Network Reprogramming Service for Sensor Networks, Proceedings of the 25th IEEE International Conference on Distributed Computing Systems, p.7-16, June 06-10, 2005 [doi>10.1109/ICDCS.2005.50]
• 13: Philip Levis , David Culler, Maté: a tiny virtual machine for sensor networks, Proceedings of the 10th international conference on Architectural support for programming languages and operating systems, October 05-09, 2002, San Jose, California
• 14: Philip Levis , David Culler, The firecracker protocol, Proceedings of the 11th workshop on ACM SIGOPS European workshop, September 19-22, 2004, Leuven, Belgium [doi>10.1145/1133572.1133589]
• 15: Philip Levis , Nelson Lee , Matt Welsh , David Culler, TOSSIM: accurate and scalable simulation of entire TinyOS applications, Proceedings of the 1st international conference on Embedded networked sensor systems, November 05-07, 2003, Los Angeles, California, USA [doi>10.1145/958491.958506]
• 16: Philip Levis , Neil Patel , David Culler , Scott Shenker, Trickle: a self-regulating algorithm for code propagation and maintenance in wireless sensor networks, Proceedings of the 1st conference on Symposium on Networked Systems Design and Implementation, p.2-2, March 29-31, 2004, San Francisco, California
• 17: 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]
• 18: Vinayak Naik , Anish Arora , Prasun Sinha , Hongwei Zhang, Sprinkler: A Reliable and Energy Efficient Data Dissemination Service for Wireless Embedded Devices, Proceedings of the 26th IEEE International Real-Time Systems Symposium, p.277-286, December 05-08, 2005 [doi>10.1109/RTSS.2005.37]
• 19: Sze-Yao Ni , Yu-Chee Tseng , Yuh-Shyan Chen , Jang-Ping Sheu, The broadcast storm problem in a mobile ad hoc network, Proceedings of the 5th annual ACM/IEEE international conference on Mobile computing and networking, p.151-162, August 15-19, 1999, Seattle, Washington, United States [doi>10.1145/313451.313525]
• 20: Niels Reijers , Koen Langendoen, Efficient code distribution in wireless sensor networks, 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.941359]
• 21: Shen, C.-C., Srisathapornphat, C., and Jaikaeo, C. 2001. Sensor information networking architecture and applications. IEEE Personel Commun. Mag. 8, 4, 52--59.
• 22: Stathopoulos, T., Heidemann, J., and Estrin, D. 2003. A remote code update mechanism for wireless sensor networks. Tech. rep., University of California at Los Angeles.
• 23: Team, T. O. S. U. N. 2004. ExScal: Extreme scaling in sensor networks for target detection, classification, tracking. DARPA, http://www.cse.ohio-state.edu/exscal.
• 24: van Hoesel, L. F. W., Nieberg, T., Kip, H. J., and Havinga, P. J. M. 2004. Advantages of a tdma-based, energy-efficient, self-organizing mac protocol for wsns. IEEE VTC (spring).
• 25: Ye, W., Heidemann, J., and Estrin, D. 2002. An energy-efficient MAC protocol for wireless sensor networks. In Proceedings of the 21st International Annual Joint Conference of the IEEE Computer and Communications Societies (INFOCOM), 1567--1576.

INDEX TERMS

Primary Classification:
  C. Computer Systems Organization
  C.2 COMPUTER-COMMUNICATION NETWORKS
      C.2.0 General
          Subjects: Data communications

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

General Terms:
Algorithms, Experimentation, Performance

Keywords:
Sensor networks, energy efficiency, network reprogramming