Trickle: A Self-Regulating Algorithm for Code Propagation and Maintenance in Wireless Sensor Networks
Best paper award, NSDI 2004; Test of time award, NSDI 2004 (awarded 2014)
Philip Levis, Neil Patel, David Culler, and Scott Shenker
Published in Proceedings of the First USENIX/ACM Symposium on Networked Systems Design and Implementation (NSDI), March 2004.
Abstract
We present Trickle, an algorithm for propagating and maintaining code updates in wireless sensor networks. Borrowing techniques from the epidemic/gossip, scalable multicast, and wireless broadcast literature, Trickle uses a 'polite gossip' policy, where motes periodically broadcast a code summary to local neighbors but stay quiet if they have recently heard a summary identical to theirs. When a mote hears an older summary than its own, it broadcasts an update. Instead of flooding a network with packets, the algorithm controls the send rate so each mote hears a small trickle of packets, just enough to stay up to date. We show that with this simple mechanism, Trickle can scale to thousand-fold changes in network density, propagate new code in the order of seconds, and impose a maintenance cost on the order of a few sends an hour.
Talk (1MB), Paper (3MB)
BibTeX entry
@inproceedings{nsdi04levistrickle, author = "Philip Levis and Neil Patel and David Culler and Scott Shenker", title = "{Trickle: A Self-Regulating Algorithm for Code Propagation and Maintenance in Wireless Sensor Networks}", booktitle = "{Proceedings of the First USENIX/ACM Symposium on Networked Systems Design and Implementation (NSDI)}", year = {2004}, month = {March} }





Login