UC BERKELEY
EECS technical reports
TECHNICAL REPORTS


CSD-03-1290.pdf
CSD-03-1290.ps
Conditions of Use

Archive Home Page

Trickle: A Self-Regulating Algorithm for Code Propagation and Maintenance in Wireless Sensor Networks

Authors:
Levis, Philip
Patel, Neil
Shenker, Scott
Culler, David
Technical Report Identifier: CSD-03-1290
2003
CSD-03-1290.pdf
CSD-03-1290.ps

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.

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.