Philip Levis, Neil Patel, Scott Shenker and David Culler

EECS Department
University of California, Berkeley
Technical Report No. UCB/CSD-03-1290
2003

http://www2.eecs.berkeley.edu/Pubs/TechRpts/2003/CSD-03-1290.pdf

We present Trickle, an algorithm for propagating and maintaining code updates in wireless sensor networks. Trickle uses a "polite gossip" policy, where nodes periodically broadcast a code summary to local neighbors but stay quiet if they have recently heard a summary identical to theirs. When a node 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 node hears a small trickle of packets, just enough to stay up to date.

We first analyze Trickle using an idealized single-cell network model, with perfect synchronization and no packet loss. Progressively relaxing these assumptions, we evaluate the algorithm in simulation, first without synchronization, then in the presence of loss, and finally in the multi-cell case. We validate these simulation results with empirical data from a real-world deployment. We show that Trickle scales well, with the aggregate network transmission count increasing as a logarithm of cell density. We show that by dynamically adjusting listening periods, Trickle can rapidly propagate new code, taking on the order of seconds, while keeping maintenance costs on the order of a few sends per hour per node.

BibTeX citation:

@techreport{Levis:CSD-03-1290,
    Author = {Levis, Philip and Patel, Neil and Shenker, Scott and Culler, David},
    Title = {Trickle: A Self-Regulating Algorithm for Code Propagation and Maintenance in Wireless Sensor Networks},
    Institution = {EECS Department, University of California, Berkeley},
    Year = {2003},
    URL = {http://www2.eecs.berkeley.edu/Pubs/TechRpts/2003/5697.html},
    Number = {UCB/CSD-03-1290},
    Abstract = {We present Trickle, an algorithm for propagating and maintaining code updates in wireless sensor networks. Trickle uses a "polite gossip" policy, where nodes periodically broadcast a code summary to local neighbors but stay quiet if they have recently heard a summary identical to theirs. When a node 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 node hears a small trickle of packets, just enough to stay up to date. <p>We first analyze Trickle using an idealized single-cell network model, with perfect synchronization and no packet loss. Progressively relaxing these assumptions, we evaluate the algorithm in simulation, first without synchronization, then in the presence of loss, and finally in the multi-cell case. We validate these simulation results with empirical data from a real-world deployment. We show that Trickle scales well, with the aggregate network transmission count increasing as a logarithm of cell density. We show that by dynamically adjusting listening periods, Trickle can rapidly propagate new code, taking on the order of seconds, while keeping maintenance costs on the order of a few sends per hour per node.}
}

EndNote citation:

%0 Report
%A Levis, Philip
%A Patel, Neil
%A Shenker, Scott
%A Culler, David
%T Trickle: A Self-Regulating Algorithm for Code Propagation and Maintenance in Wireless Sensor Networks
%I EECS Department, University of California, Berkeley
%D 2003
%@ UCB/CSD-03-1290
%U http://www2.eecs.berkeley.edu/Pubs/TechRpts/2003/5697.html
%F Levis:CSD-03-1290