Trickle: a self-regulating algorithm for code propagation and maintenance in wireless sensor networks
Philip A. Levis, Neil Patel, David Culler et al. · 2004
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
Cited by 1,129 works.
Authors
References
- System architecture directions for networked sensors
- Adaptive protocols for information dissemination in wireless sensor networks
- The broadcast storm problem in a mobile ad hoc network
- TAG
- A reliable multicast framework for light-weight sessions and application level framing
- Building efficient wireless sensor networks with low-level naming
- Mica: a wireless platform for deeply embedded networks
- Epidemic algorithms for replicated database maintenance
- Maté
- Understanding packet delivery performance in dense wireless sensor networks