The Emergence of a
Networking Primitive in
Wireless Sensor Networks
by philip levis, Eric brewer, david Culler, david Gay, sam Madden, neil patel,
Joe polastre, scott shenker, robert szewczyk, and Alec Woo
abstract
The wireless sensor network community approached networking abstractions as an open question, allowing answers
to emerge with time and experience. The Trickle algorithm
has become a basic mechanism used in numerous protocols and systems. Trickle brings nodes to eventual consistency quickly and efficiently while remaining remarkably
robust to variations in network density, topology, and dynamics. Instead of flooding a network with packets, Trickle
uses a “polite gossip” policy to control send rates so each
node hears just enough packets to stay consistent. This
simple mechanism enables Trickle to scale to 1000-fold
changes in network density, reach consistency in seconds,
and require only a few bytes of state yet impose a maintenance cost of a few sends an hour. Originally designed for
disseminating new code, experience has shown Trickle to
have much broader applicability, including route maintenance and neighbor discovery. This paper provides an overview of the research challenges wireless sensor networks
face, describes the Trickle algorithm, and outlines several
ways it is used today.
1. WiReLeSS SenSoR net WoRKS
Although embedded sensing applications are extremely
diverse, ranging from habitat and structural monitoring to
vehicle tracking and shooter localization, the software and
hardware architectures used by these systems are surprisingly similar. The typical architecture is embodied by the
mote platforms, such as those shown in Figure 1. A microcontroller provides processing, program ROM, and data
RAM, as well as analog-to-digital converters for sensor inputs, digital interfaces for connecting to other devices, and
control outputs. Additional flash storage holds program
images and data logs. A low-power CMOS radio provides
a simple link layer. Support circuitry allows the system to
enter a low-power sleep state, wake quickly, and respond to
important events.
Four fundamental constraints shape wireless embedded
system and network design: power supply, limited memory,
the need for unattended operation, and the lossy and transient behavior of wireless communication. A typical power
envelope for operating on batteries or harvesting requires a
600 µ W average power draw, with 1%% of the time spent in
a 60 mW active state and the remainder spent in a very low
power 6 µ W passive state.
Maintaining a small memory footprint is a major requirement of algorithm design. Memory in low-cost, ultra-low-power devices does not track Moore’s Law. One indication
of this is that microcontroller RAM costs three orders of
magnitude more than PC SRAM and five orders more than
PC DRAM. More importantly, SRAM leakage current, which
grows with capacity, dictates overall standby power consumption and, hence, lifetime. Designs that provide large
RAMs in conjunction with 32-bit processors go to great
lengths to manage power. One concrete example of such
nodes is the Sun SPOT, 20 which enters a low-power sleep
state by writing RAM contents to flash. Restoring memory
from flash on wakeup uses substantial power and takes considerable time. The alternative, taken in most sensor node
designs, is to have just a few kilobytes of RAM. This, in turn,
imposes limits on the storage complexity of network (and
other) protocols, requiring routing tables, buffering, and
caches be kept small. The historical trends of monetary and
energy costs suggest these constraints are likely to last.
Wireless sensors are typically embedded in the physical environment associated with their application. Com-
figure 1: ePic, Kmote, and telos motes. each has an 8mhz
microcontroller, 10kB of Ram, 48kB of program flash, and a
250kbps radio.
