research-article

Energy-efficient multihop reprogramming for sensor networks

Authors:

Sandeep Kulkarni,

Limin WangAuthors Info & Claims

ACM Transactions on Sensor Networks (TOSN), Volume 5, Issue 2

Article No.: 16, Pages 1 - 40

https://doi.org/10.1145/1498915.1498922

Published: 03 April 2009 Publication History

Get Access

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]

Arora, A., Dutta, P., Bapat, S., Kulathumani, V., Zhang, H., Naik, V., Mittal, V., Cao, H., Demirbas, M., Gouda, M., Choi, Y.-R., Herman, T., Kulkarni, S. S., Arumugam, U., Nesterenko, M., Vora, A., and Miyashita, M. 2004. A line in the sand: A wireless sensor network for target detection, classification, and tracking. Comput. Netw. 46, 5, 605--634.

Digital Library

Google Scholar

[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.

Google Scholar

[3]

Dutta, P., Grimmer, M., Arora, A., Bibyk, S., and Culler, D. 2005. Design of a wireless sensor network platform for detecting rare, random, and ephemeral events. In Proceedings of the International Conference on Information Processing in Sensor Networks (IPSN), Special track on Platform Tools and Design Methods for Network Embedded Sensors (SPOTS).

Digital Library

Google Scholar

[4]

Floyd, S., Jacobson, V., Liu, C.-G., McCanne, S., and Zhang, L. 1997. A reliable multicast framework for light-weight sessions and application level framing. IEEE/ACM Trans. Netw. 5, 6, 784--803.

Digital Library

Google Scholar

[5]

Heinzelman, W. R., Chandrakasan, A., and Balakrishnan, H. 2000. Energy-Efficient communication protocol for wireless microsensor networks. In Proceedings of the 33rd Hawaii International Conference on System Sciences.

Digital Library

Google Scholar

[6]

Hill, J. and Culler, D. 2002. Mica: A wirleess platform for deeply embedded networks. IEEE Micro 22, 6, 12--24.

Digital Library

Google Scholar

[7]

Hui, J. W. and Culler, D. 2004. The dynamic behavior of a data dissemination protocol for network programming at scale. In Proceedings of the 2nd International Conference on Embedded Networked Sensor Systems (SenSys'04).

Digital Library

Google Scholar

[8]

Intanagonwiwat, C., Govindan, R., and Estrin, D. 2000. Directed diffusion: A scalable and robust communication paradigm for sensor networks. In Mobile Computing and Networking,56--67.

Digital Library

Google Scholar

[9]

Kulik, J., Heinzelman, W., and Balakrishnan, H. 2002. Negotiation-Based protocols for disseminating information in wireless sensor networks. Wireless Netw. 8, 169--185.

Digital Library

Google Scholar

[10]

Kulkarni, S. S. and Arumugam, M. 2005. SS-TDMA: A self-stabilizing MAC for sensor networks. In Sensor Network Operations. IEEE Press.

Google Scholar

[11]

Kulkarni, S. S. and Arumugam, M. 2006. Infuse: A TDMA based data dissemination protocol for sensor networks. Int. J. Distrib. Sensor Netw.

Google Scholar

[12]

Kulkarni, S. S. and Wang, L. 2005. MNP: Multihop network reprogramming service for sensor networks. In Proceedings of the 25th International Conference on Distributed Computing Systems (ICDCS), 7--16.

Digital Library

Google Scholar

[13]

Levis, P. and Culler, D. 2002. Maté: A tiny virtual machine for sensor networks. In the 10th International Conference on Architectural Support for Programming Languages and Operating Systems (ASPLOS-X).

Digital Library

Google Scholar

[14]

Levis, P. and Culler, D. 2004. The firecracker protocol. In Proceedings of the 11th ACM SIGOPS European Workshop.

Digital Library

Google Scholar

[15]

Levis, P., Lee, N., Welsh, M., and Culler, D. 2003. Tossim: Accurate and scalable simulation of entire TinyOS applications. In Proceedings of the 1st ACM Conference on Embedded Networked Sensor Systems (SenSys'03).

Digital Library

Google Scholar

[16]

Levis, P., Patel, N., Culler, D., and Shenker, S. 2004. Trickle: A self-regulating algorithm for code propagation and maintenance in wireless sensor networks. In Proceedings of the 1st USENIX/ACM Symposium on Networked Systems Design and Implementation (NSDI).

Digital Library

Google Scholar

[17]

Mainwaring, A., Polastre, J., Szewczyk, R., Culler, D., and Anderson, J. 2002. Wireless sensor networks for habitat monitoring. In Proceedings of the ACM International Workshop on Wireless Sensor Networks and Applications (WSNA'02).

Digital Library

Google Scholar

[18]

Naik, V., Arora, A., Sinha, P., and Zhang, H. 2005. Sprinkler: A reliable and energy efficient data dissemination service for wireless embedded devices. In Proceedings of the 26th IEEE Real-Time Systems Symposium.

Digital Library

Google Scholar

[19]

Ni, S.-Y., Tseng, Y.-C., Chen, Y.-S., and Sheu, J.-P. 1999. The broadcast storm problem in a mobile ad hoc network. In the 5th Annual ACM/IEEE International Conference on Mobile Computing and Networking.

Digital Library

Google Scholar

[20]

Reijers, N. and Langendoen, K. 2003. Efficient code distribution in wireless sensor networks. In the 2nd ACM International Conference on Wireless Sensor Netowrks and Applications.

Digital Library

Google Scholar

[21]

Shen, C.-C., Srisathapornphat, C., and Jaikaeo, C. 2001. Sensor information networking architecture and applications. IEEE Personel Commun. Mag. 8, 4, 52--59.

Crossref

Google Scholar

[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.

Google Scholar

[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.

Google Scholar

[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).

Google Scholar

[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.

Google Scholar

Cited By

View all

Gu JLee SKang H(2024)DSME-FOTA: Firmware over-the-air update framework for IEEE 802.15.4 DSME MAC to enable large-scale multi-hop industrial IoT networksInternet of Things10.1016/j.iot.2024.10123927(101239)Online publication date: Oct-2024
https://doi.org/10.1016/j.iot.2024.101239
Yang PMa RYi MZhang YLi BBai Z(2024)A computation offloading strategy for multi-access edge computing based on DQUIC protocolThe Journal of Supercomputing10.1007/s11227-024-06176-980:12(18285-18318)Online publication date: 1-Aug-2024
https://dl.acm.org/doi/10.1007/s11227-024-06176-9
Mao WWang ZZhao ZMin GLiu YXing GHe YPicco G(2019)Priority-Aware Bulk Data Transfer in Low-power IoT NetworksProceedings of the 2019 International Conference on Embedded Wireless Systems and Networks10.5555/3324320.3324400(318-323)Online publication date: 25-Feb-2019
https://dl.acm.org/doi/10.5555/3324320.3324400
Show More Cited By

Index Terms

Energy-efficient multihop reprogramming for sensor networks
1. Hardware
  1. Communication hardware, interfaces and storage
2. Networks
  1. Network types
    1. Mobile networks
    2. Wireless access networks

Recommendations

An efficient cluster-based communication protocol for wireless sensor networks

A wireless sensor network is a network of large numbers of sensor nodes, where each sensor node is a tiny device that is equipped with a processing, sensing subsystem and a communication subsystem. The critical issue in wireless sensor networks is how ...
Energy-efficient on-demand reprogramming of large-scale sensor networks

As sensor networks operate over long periods of deployment in difficult to reach places, their requirements may change or new code may need to be uploaded to them. The current state-of-the-art protocols (Deluge and MNP) for network reprogramming perform ...
Efficient wireless reprogramming through reduced bandwidth usage and opportunistic sleeping

Wireless reprogramming of a sensor network is useful for uploading new code or for changing the functionality of existing code. Reprogramming may be done multiple times during a node's lifetime and therefore a node has to remain receptive to future code ...

Reviews

Reviewer: John W. Fendrich

Because of acquired understanding of the sensor network environment and continual technological advancement, the software running on sensor nodes needs to be changed; that is, the sensor network needs to be reprogrammed. This paper discusses the issues involved: 100 percent delivery, relatively high bandwidth requirements, message collisions and congestion, concurrent senders, and the importance of energy efficiency for low-powered sensor nodes. It presents a code dissemination protocol, multihop network reprogramming protocol (MNP), to provide "a reliable and energy-efficient service to propagate new program code to all sensor nodes in the network, over wireless radio." Contributions include a sensor selection algorithm, "pipelining to enable fast data propagation," and three innovative sleep strategies for energy conservation: contention sleep, noreq sleep, and init sleep. Another contribution is implementation and performance evaluations using the TinyOS platform and "TOSSIM, a discrete event simulator for TinyOS wireless sensor networks." This includes the identification of optimal values of the three sleep parameters in different network densities, network sizes, and base station locations, and the use of these optimal values to observe the performance of MNP. This report is on experiments done on a preliminary version of MNP, not the latest version. This analysis goes on to identify and discuss more MNP-related issues. Kulkarni and Wang present a perspective on the related work of others, enabling readers to see how this work fits in with other sensor network reprogramming research. The authors also determine that investigation is needed on the use of MNP in the dissemination of any data. Online Computing Reviews Service

Access critical reviews of Computing literature here

Become a reviewer for Computing Reviews.

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Transactions on Sensor Networks

ACM Transactions on Sensor Networks Volume 5, Issue 2

March 2009

284 pages

ISSN:1550-4859

EISSN:1550-4867

DOI:10.1145/1498915

Issue’s Table of Contents

Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]

Publisher

Association for Computing Machinery

New York, NY, United States

Journal Family

ACM Journals for the Design of Smart and Connected Systems

Publication History

Published: 03 April 2009

Accepted: 01 May 2008

Revised: 01 March 2008

Received: 01 August 2006

Published in TOSN Volume 5, Issue 2

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Research-article
Research
Refereed

Funding Sources

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

28
Total Citations
View Citations
839
Total Downloads

Downloads (Last 12 months)3
Downloads (Last 6 weeks)1

Reflects downloads up to 09 Jan 2025

Other Metrics

View Author Metrics

Citations

Cited By

View all

Gu JLee SKang H(2024)DSME-FOTA: Firmware over-the-air update framework for IEEE 802.15.4 DSME MAC to enable large-scale multi-hop industrial IoT networksInternet of Things10.1016/j.iot.2024.10123927(101239)Online publication date: Oct-2024
https://doi.org/10.1016/j.iot.2024.101239
Yang PMa RYi MZhang YLi BBai Z(2024)A computation offloading strategy for multi-access edge computing based on DQUIC protocolThe Journal of Supercomputing10.1007/s11227-024-06176-980:12(18285-18318)Online publication date: 1-Aug-2024
https://dl.acm.org/doi/10.1007/s11227-024-06176-9
Mao WWang ZZhao ZMin GLiu YXing GHe YPicco G(2019)Priority-Aware Bulk Data Transfer in Low-power IoT NetworksProceedings of the 2019 International Conference on Embedded Wireless Systems and Networks10.5555/3324320.3324400(318-323)Online publication date: 25-Feb-2019
https://dl.acm.org/doi/10.5555/3324320.3324400
Li PYang LYang XZhong XWen JXiong Q(2019)Energy-Efficient Patching Strategy for Wireless Sensor NetworksSensors10.3390/s1902026219:2(262)Online publication date: 10-Jan-2019
https://doi.org/10.3390/s19020262
Wang ZXu ZDong BXu WYang J(2019)Dandelion: An Online Testbed for LoRa Development2019 15th International Conference on Mobile Ad-Hoc and Sensor Networks (MSN)10.1109/MSN48538.2019.00089(439-444)Online publication date: Dec-2019
https://doi.org/10.1109/MSN48538.2019.00089
Roohitavaf MZhu LKulkarni SBiswas STakadama K(2018)Synthesizing customized network protocols using genetic programmingProceedings of the Genetic and Evolutionary Computation Conference Companion10.1145/3205651.3208272(1616-1623)Online publication date: 6-Jul-2018
https://dl.acm.org/doi/10.1145/3205651.3208272
Zhao ZDong WBu JGu TMin G(2017)Accurate and Generic Sender Selection for Bulk Data Dissemination in Low-Power Wireless NetworksIEEE/ACM Transactions on Networking10.1109/TNET.2016.261412925:2(948-959)Online publication date: 1-Apr-2017
https://dl.acm.org/doi/10.1109/TNET.2016.2614129
Montuschi P(2017)State of the JournalIEEE Transactions on Computers10.1109/TC.2016.262091966:1(1-2)Online publication date: 1-Jan-2017
https://dl.acm.org/doi/10.1109/TC.2016.2620919
Li JLi SZhang YGu TLaw YYang ZZhou XPalaniswami M(2017)An Analytical Model for Coding-Based Reprogramming Protocols in Lossy Wireless Sensor NetworksIEEE Transactions on Computers10.1109/TC.2016.256080566:1(24-37)Online publication date: 1-Jan-2017
https://dl.acm.org/doi/10.1109/TC.2016.2560805
Kim DNam HKim D(2017)Adaptive Code Dissemination Based on Link Quality in Wireless Sensor NetworksIEEE Internet of Things Journal10.1109/JIOT.2016.26436594:3(685-695)Online publication date: Jun-2017
https://doi.org/10.1109/JIOT.2016.2643659
Show More Cited By

View Options

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Cited By

Index Terms

Recommendations

An efficient cluster-based communication protocol for wireless sensor networks

Energy-efficient on-demand reprogramming of large-scale sensor networks

Efficient wireless reprogramming through reduced bandwidth usage and opportunistic sleeping

Reviews

Access critical reviews of Computing literature here