research-article

Free access

The emergence of a networking primitive in wireless sensor networks

Authors:

Robert Szewczyk,

Alec WooAuthors Info & Claims

Communications of the ACM, Volume 51, Issue 7

Pages 99 - 106

https://doi.org/10.1145/1364782.1364804

Published: 01 July 2008 Publication History

All formats PDF

Abstract

The wireless sensor network community approached networking abstractions as an open question, allowing answers to emerge with time and experience. The Trickle algorithm has become a basic mechanism used in numerous protocols and systems. Trickle brings nodes to eventual consistency quickly and efficiently while remaining remarkably robust to variations in network density, topology, and dynamics. Instead of flooding a network with packets, Trickle uses a "polite gossip" policy to control send rates so each node hears just enough packets to stay consistent. This simple mechanism enables Trickle to scale to 1000-fold changes in network density, reach consistency in seconds, and require only a few bytes of state yet impose a maintenance cost of a few sends an hour. Originally designed for disseminating new code, experience has shown Trickle to have much broader applicability, including route maintenance and neighbor discovery. This paper provides an overview of the research challenges wireless sensor networks face, describes the Trickle algorithm, and outlines several ways it is used today.

References

[1]

Arch Rock Corporation. An IPv6 Network Stack for Wireless Sensor Networks. http://www.archrock.com.

[2]

Couto, D.D., Aguayo, D., Bicket, J., and Morris, R. A high-throughput path mMetric for multi-hop wireless routing. Proceedings of the Ninth Annual International Conference on Mobile Computing and Networking (MobiCom), 2003.

Digital Library

[3]

Crossbow, Inc. Mote in Network Programming User Reference. http://webs.cs.berkeley.edu/tos/tinyos-1.x/doc/Xnp.pdf.

[4]

Demers, A., Greene, D., Hauser, C., Irish, W., and Larson, J. Epidemic Algorithms for Replicated Database Maintenance. In Proceedings of the Sixth Annual ACM Symposium on Principles of Distributed Computing (PODC), 1987.

Digital Library

[5]

Floyd, S., Jacobson, V., McCanne, S., Liu, C.-G., and Zhang, L. A reliable multicast framework for lightweight sessions and application level framing. Proceedings of the Conference on Applications, Technologies, Architectures, and Protocols for Computer Communication (SIGCOMM), 1995.

Digital Library

[6]

Fonseca, R., Gnawali, O., Jamieson, K., and Levis, P. Four bit wireless link estimation. Proceedings of the Sixth Workshop on Hot Topics in Networks (HotNets VI), 2007.

[7]

Gnawali, O., Greenstein, B., Jang, K.-Y., Joki, A., Paek, J., Vieira, M., Estrin, D., Govindan, R., and Kohler, E. The TENET architecture for tiered sensor networks. Proceedings of the Fourth International Conference on Embedded Networked Sensor Systems (Sensys), 2006.

Digital Library

[8]

Hill, J., Szewczyk, R., Woo, A., Hollar, S., Culler, D.E., and Pister, K.S.J. System architecture directions for networked sensors. Proceedings of the Ninth International Conference on Architectural Support for Programming Languages and Operating Systems (ASPLOS), 2000.

Digital Library

[9]

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

Digital Library

[10]

Intanagonwiwat, C., Govindan, R., and Estrin, D. Directed diffusion: a scalable and robust communication paradigm for sensor networks. Proceedings of the Sixth Annual International Conference on Mobile Computing and Networking (MobiCom), 2000.

Digital Library

[11]

Levis, P., Gay, D., and Culler, D. Active sensor networks. Proceedings of the Second USENIX/ACM Symposium on Network Systems Design and Implementation (NSDI), 2005.

Digital Library

[12]

Levis, P., Lee, N., Welsh, M., and Culler, D. TOSSIM: accurate and scalable simulation of entire TinyOS applications. Proceedings of the First ACM Conference on Embedded Networked Sensor Systems (SenSys), 2003.

Digital Library

[13]

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

Digital Library

[14]

Lin, K. and Levis, P. Data discovery and dissemination with DIP. Proceedings of the Seventh International Symposium on Information Processing in Sensor Networks (IPSN), 2008.

Digital Library

[15]

Madden, S., Franklin, M.J., Hellerstein, J.M., and Hong, W. Tiny DB: an acquisitional query processing system for sensor networks. Transactions on Database Systems (TODS), 2005.

Digital Library

[16]

Mao, Y., Wang, F., Qiu, L., Lam, S., and Smith, J. S4: small state and small stretch routing protocol for large wireless sensor networks. Proceedings of the Fourth USENIX Symposium on Networked Systems Design and Implementation (NSDI), 2007.

Digital Library

[17]

Ni, S.-Y., Tseng, Y.-C., Chen, Y.-S., and Sheu, J.-P. The broadcast storm problem in a mobile ad hoc network. Proceedings of the Fifth Annual International Conference on Mobile Computing and Networking (MobiCom), 1999.

Digital Library

[18]

Paek, J. and Govindan, R. RCRT: rate-controlled reliable transport for wireless sensor networks. Proceedings of the Fifth International Conference on Embedded Networked Sensor Systems (SenSys), 2007.

Digital Library

[19]

Rangwala, S., Gummadi, R., Govindan, R., and Psounis, K. Interference-aware fair rate control in wireless sensor networks. Proceedings of the Conference on Applications, Technologies, Architectures, and Protocols for Computer Communications (SIGCOMM), 2006.

Digital Library

[20]

Sun Microsystems Laboratories. Project Sun SPOT: Small Programmable Object Technology. http://www.sunspotworld.com/.

[21]

TinyOS Network Protocol Working Group. TEP 123: The Collection Tree Protocol. http://www.tinyos.net//tinyos-2.x/doc/txt/tep123.txt, 2007.

[22]

Tolle, G. and Culler, D. Design of an application-cooperative management system for wireless sensor networks. Proceedings of the Second European Workshop of Wireless Sensor Netw orks (EWSN), 2005.

[23]

Wang, L. MNP: Multihop network reprogramming service for sensor networks. Proceedings of the Second International Conference on Embedded Networked Sensor Systems (SenSys), 2004.

Digital Library

[24]

Woo, A., Tong, T., and Culler, D. Taming the underlying challenges of multihop routing in sensor etworks. Proceedings of the First ACM Conference on Embedded Networked Sensor Systems (SenSys), 2003.

Digital Library

[25]

Yang, J., Soffa, M.L., Selavo, L., and Whitehouse, K. Clairvoyant: a comprehensive source-level debugger for wireless sensor networks. Proceedings of the Fifth International Conference on Embedded Networked Sensor Systems (SenSys). 2007.

Digital Library

Cited By

Elhabbash AElkhatib YNundloll VSanz Marco VBlair G(2024)Principled and automated system of systems composition using an ontological architectureFuture Generation Computer Systems10.1016/j.future.2024.03.034157:C(499-515)Online publication date: 18-Jul-2024
https://dl.acm.org/doi/10.1016/j.future.2024.03.034
Xie YLi WSun YBertino EGong B(2022)Subspace Embedding Based New Paper Recommendation2022 IEEE 38th International Conference on Data Engineering (ICDE)10.1109/ICDE53745.2022.00178(1767-1780)Online publication date: May-2022
https://doi.org/10.1109/ICDE53745.2022.00178
Dubrulle JQuoitin BGallais A(2021)Opportunities and limitations of multi-instance RPL2021 17th International Conference on Distributed Computing in Sensor Systems (DCOSS)10.1109/DCOSS52077.2021.00015(10-17)Online publication date: Jul-2021
https://doi.org/10.1109/DCOSS52077.2021.00015
Show More Cited By

Index Terms

The emergence of a networking primitive in wireless sensor networks
1. Computer systems organization
  1. Embedded and cyber-physical systems
  2. Real-time systems
2. Networks
  1. Network protocols
  2. Network types
    1. Mobile networks
    2. Wireless access networks

Recommendations

Networking issues in wireless sensor networks

The emergence of sensor networks as one of the dominant technology trends in the coming decades (Technol. Rev. (February 2003)) has posed numerous unique challenges to researchers. These networks are likely to be composed of hundreds, and potentially ...
Design tradeoffs in wireless sensor networks
Relay Node Placement in Wireless Sensor Networks

A wireless sensor network consists of many low-cost, low-power sensor nodes, which can perform sensing, simple computation, and transmission of sensed information. Long distance transmission by sensor nodes is not energy efficient since energy ...

Reviews

Reviewer: Bayard Kohlhepp

According to the authors, wireless embedded networks are limited by four fundamental constraints: low power, small memory, unattended operation, and lossy network behavior. Historically, network protocol designers had to choose between two extremes: efficiency or robust behavior. Over the past several decades, however, the Trickle algorithm has evolved to satisfy both requirements via a "polite, density-aware, local retransmission" scheme. Originally developed to spread new code across a network of sensors, Trickle is finding its way into connectivity discovery, data dissemination, and route maintenance applications. This paper is eight pages long, including an extensive two-page bibliography that goes all the way back to 1987. It's an easy read, and the bibliography is a great source for further reading or study. Online Computing Reviews Service

Access critical reviews of Computing literature here

Become a reviewer for Computing Reviews.

Comments

Information & Contributors

Information

Published In

cover image Communications of the ACM

Communications of the ACM Volume 51, Issue 7

Web science

July 2008

100 pages

ISSN:0001-0782

EISSN:1557-7317

DOI:10.1145/1364782

Issue’s Table of Contents

Copyright © 2008 ACM.

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

Publication History

Published: 01 July 2008

Published in CACM Volume 51, Issue 7

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Qualifiers

Research-article
Popular
Refereed

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

52
Total Citations
View Citations
24,105
Total Downloads

Downloads (Last 12 months)899
Downloads (Last 6 weeks)64

Reflects downloads up to 09 Jan 2025

Other Metrics

View Author Metrics

Citations

Cited By

Elhabbash AElkhatib YNundloll VSanz Marco VBlair G(2024)Principled and automated system of systems composition using an ontological architectureFuture Generation Computer Systems10.1016/j.future.2024.03.034157:C(499-515)Online publication date: 18-Jul-2024
https://dl.acm.org/doi/10.1016/j.future.2024.03.034
Xie YLi WSun YBertino EGong B(2022)Subspace Embedding Based New Paper Recommendation2022 IEEE 38th International Conference on Data Engineering (ICDE)10.1109/ICDE53745.2022.00178(1767-1780)Online publication date: May-2022
https://doi.org/10.1109/ICDE53745.2022.00178
Dubrulle JQuoitin BGallais A(2021)Opportunities and limitations of multi-instance RPL2021 17th International Conference on Distributed Computing in Sensor Systems (DCOSS)10.1109/DCOSS52077.2021.00015(10-17)Online publication date: Jul-2021
https://doi.org/10.1109/DCOSS52077.2021.00015
Bannour BLapitre AGall P(2021)Deriving Interaction Scenarios for Timed Distributed Systems by Symbolic ExecutionAdvances in Model and Data Engineering in the Digitalization Era10.1007/978-3-030-87657-9_4(46-60)Online publication date: 7-Oct-2021
https://doi.org/10.1007/978-3-030-87657-9_4
Lachowski RPellenz MJamhour EPenna MBrante GMoritz GSouza R(2019)ICENET: An Information Centric Protocol for Big Data Wireless Sensor NetworksSensors10.3390/s1904093019:4(930)Online publication date: 22-Feb-2019
https://doi.org/10.3390/s19040930
(2019)Fault Tolerant Reliable Protocol (FTRP) Performance Evaluation in Wireless Sensor Networks: An Extensitive StudyJournal of Electronics and Sensors10.31829/2689-6958/jes2019-2(1)-107(1-36)Online publication date: 8-Nov-2019
https://doi.org/10.31829/2689-6958/jes2019-2(1)-107
Mottola LPicco GOppermann FEriksson JFinne NFuchs HGaglione AKarnouskos SMontero POertel NRomer KSpies PTranquillini SVoigt T(2019) make Sense : Simplifying the Integration of Wireless Sensor Networks into Business Processes IEEE Transactions on Software Engineering10.1109/TSE.2017.278758545:6(576-596)Online publication date: 1-Jun-2019
https://doi.org/10.1109/TSE.2017.2787585
Shimly SSmith DMovassaghi S(2019)Experimental Analysis of Cross-Layer Optimization for Distributed Wireless Body-to-Body NetworksIEEE Sensors Journal10.1109/JSEN.2019.293735619:24(12494-12509)Online publication date: 15-Dec-2019
https://doi.org/10.1109/JSEN.2019.2937356
Nguyen NBannour BLapitre ALe Gall P(2019)Behavioral Models and Scenario Selection for Testing IoT Trickle-Based Lossy Multicast Networks2019 IEEE International Conference on Software Testing, Verification and Validation Workshops (ICSTW)10.1109/ICSTW.2019.00047(168-175)Online publication date: Apr-2019
https://doi.org/10.1109/ICSTW.2019.00047
Pope JSimon RLassous IBarba CRazafindralambo T(2016)A Distributed Algorithm for Maximizing Linear Tree Density for One to Many Wireless CommunicationProceedings of the 13th ACM Symposium on Performance Evaluation of Wireless Ad Hoc, Sensor, & Ubiquitous Networks10.1145/2989293.2989296(73-82)Online publication date: 13-Nov-2016
https://dl.acm.org/doi/10.1145/2989293.2989296
Show More Cited By

View Options

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Digital Edition

View this article in digital edition.

Digital Edition

Magazine Site

View this article on the magazine site (external)

Login options

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

Full Access

Get this Article

Media

Figures

Other

Tables

View Issue’s Table of Contents