Communications - July 2008

concern by using a combination of hash trees and randomized searches, enabling the maintenance cost to remain O( 1) while imposing a O(log(n) ) discovery cost. ¹⁴

4. DiScuSSion

Wireless sensor networks, like other ad hoc networks, do not know the interconnection topology a priori and are typically not static. Nodes must discover it by attempting to communicate and then observing where communication succeeds. In addition, the communication medium is expected to be lossy. Redundancy in such networks is both friend and foe, but Trickle reinforces the positive aspects and suppresses the negative ones.

Trickle draws on two major areas of prior research. The first area is controlled, density-aware flooding algorithms for wireless and multicast networks. ⁵^, ¹⁷ The second is epidemic and gossiping algorithms for maintaining data consistency in distributed systems. ⁴ Although both techniques— broadcasts and epidemics—have assumptions that make them inappropriate in their pure form to eventual consistency in sensor networks, they are powerful techniques that Trickle draws from. Trickle’s suppression mechanism is inspired by the request/repair algorithm used in Scalable and Reliable Multicast (SRM). ⁵ Trickle adapts to local network density as controlled floods do, but continually maintains consistency in a manner similar to epidemic algorithms. Trickle also takes advantage of the broadcast nature of the wireless channel, employing SRM-like duplicate suppression to conserve precious transmission energy and scale to dense networks.

Exponential timers are a common protocol mechanism. Ethernet, for example, uses an exponential backoff to prevent collisions. While Trickle also has an exponential timer, its use is reversed. Where Ethernet defaults to the smallest time window and increases it only in the case of collisions, Trickle defaults to the largest time window and decreases it only in the case of an inconsistency. This reversal is indicative of the different priorities in ultra-low-power networks: minimizing energy consumption, rather than increasing performance, is typically the more important goal.

In the case of dissemination, Trickle timers spread out packet responses across nodes while allowing nodes to estimate their degree and set their communication interval. Trickle leads to energy efficient, density-aware dissemination not only by avoiding collisions through making collisions rare, but also by suppressing unnecessary retransmissions.

Instead of trying to enforce suppression on an abstraction of a logical group, which can become difficult in multihop networks with dynamically changing connectivity, Trickle suppresses in terms of an implicit group: nearby nodes that hear a broadcast. Correspondingly, Trickle does not impose the overhead of discovering and maintaining logical groups, and effortlessly deals with transient and lossy wireless links. By relying on this implicit naming, the Trickle algorithm remains very simple: implementations can fit in under 2K of code, and require a mere 11 bytes of state.

Routing protocols discover other routers, exchange routing information, issue probes, and establish as well as tear

down links. All of these operations can be rate-controlled by Trickle. For example, in our experiences exploring how wireless sensor networks can adopt more of the IPv6 stack in 6Lo WPAN, Trickle provides a way to support established ICMP-v6 mechanisms for neighbor discovery, duplicate address detection, router discovery, and DHCP in wireless networks. Each of these involves advertisement and response. Trickle mechanisms are a natural fit: they avoid loss where density is large, allow prompt notifications of change and adapt to low energy consumption when the configuration stabilizes. By adopting a model of eventual consistency, nodes can locally settle on a consistent state without requiring any actions from an administrator.

Trickle was initially developed for distributing new programs into a wireless sensornet: the title of the original paper is “Trickle: A Self-Regulating Algorithm for Code Propagation and Maintenance in Wireless Sensor Networks.” ¹³Experience has shown it to have much broader uses. Trickle-based communication, rather than flooding, has emerged as the central paradigm for the basic multihop network operations of discovering connectivity, data dissemination, and route maintenance.

Looking forward, we expect the use of these kinds of techniques to be increasingly common throughout the upper layers of the wireless network stack. Such progress will not only make existing protocols more efficient, it will enable sensor networks to support layers originally thought infeasible. Viewing protocols as a continuous process of establishing and adjusting a consistent view of distributed data is an attractive way to build robust distributed systems.

acknowledgments

This work was supported, in part, by the Defense Department Advanced Research Projects Agency (grants F33615- 01-C-1895 and N6601-99-2-8913), the National Science Foundation (grants No. 0122599, IIS-033017, 0615308, and 0627126), by the California MICRO program, Intel Corporation, DoCoMo Capital, Foundation Capital, and a by Stanford Terman Fellowship. Research infrastructure was provided by the National Science Foundation (grants No. 9802069). We would also like to thank Sylvia Ratnasamy for her valuable insights into the early stages of this research, as well as Jonathan Hui, for his ideas on applying Trickle to new problems.

References

1. Arch Rock Corporation. An IPv6 Network Stack for Wireless Sensor Networks. http://www.archrock.com.

2. Couto, D. D., Aguayo, D., Bicket, J., and Morris, R. A high-throughput path mMetric for multi-hop wireless routing. Proceedings of the Ninth Annual International Conference on Mobile Computing and Networking (MobiCom), 2003.

3. Crossbow, Inc. Mote in Network Programming User Reference. http:// webs.cs.berkeley.edu/tos/tinyos- 1.x/ doc/xnp.pdf.

4. Demers, A., Greene, D., Hauser, C., Irish, W., and Larson, J. Epidemic Algorithms for Replicated Database Maintenance. In Proceedings of the Sixth Annual ACM Symposium on

Principles of Distributed Computing (PODC), 1987.

5. Floyd, S., Jacobson, V., McCanne, S., Liu, C.-G., and Zhang, L. A reliable multicast framework for lightweight sessions and application level framing. Proceedings of the Conference on Applications, Technologies, Architectures, and Protocols for Computer Communication (SIGCOMM), 1995.

6. Fonseca, R., Gnawali, O., Jamieson, K., and Levis, P. Four bit wireless link estimation. Proceedings of the Sixth Workshop on Hot Topics in Networks (HotNets VI), 2007.