Trickle: a self-regulating algorithm for code propagation and maintenance in wireless sensor networks

TLDR

Trickle is an algorithm designed to propagate and maintain code updates in wireless sensor networks. Trickle employs a polite gossip policy that broadcasts code summaries only when a mote has not recently heard an identical summary, and updates when it hears an older summary, thereby controlling packet rate to keep each mote up to date with minimal traffic. Experiments show Trickle scales to thousand‑fold density changes, propagates code in seconds, and requires only a few sends per hour for maintenance.

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.