work. A node that is disconnected for several minutes
will still receive the most recent command when it reconnects, however.
Dissemination protocols succeed where flooding and its
derivatives fail because they cast the problem of delivering
data into maintaining data consistency among neighbors.
This allows them to provide a very useful form of reliability in arbitrary topologies with no a priori topology knowledge or configurati on. An effective dissemination protocol, however, needs to bring nodes up to date quickly while
sending few packets when every node has the most recent
version: this is correspondingly a requirement for the underlying consistency mechanism.
2. 2. Pulling data out: collection
As the typical sensor network goal is to report observations
on a remote environment, it is not surprising that data collection is the earliest and most studied class of protocol.
There are many collection protocol variations, similar to
how there are many versions of TCP. These differences
aside, all commonly used collection protocols provide
unreliable datagram delivery to a collection point using
a minimum-cost routing tree. Following the general goal
of layer 3 protocols, cost is typically measured in terms of
expected transmissions, or ETX: 2 nodes send packets on
the route that requires the fewest transmissions to reach
a collection point.
The earliest collection protocol, directed diffusion, proposed dynamically setting up collection trees based on data-specific node requests. 10 Early experiences with low-power
wireless, however, led many deployments to move towards a
much simpler and less general approach, where each node
decides on a single next hop for all forwarded data traffic,
thereby creating routing trees to fixed collection points. The
network builds this tree by establishing a routing cost gradient. A collection point has a cost of 0. A node calculates
the cost of each of its candidate next hops as the cost of that
node plus the cost of the link to it. Inductively, a node’s cost
is the sum of the costs of the links in its route. Figure 2 illustrates an example topology.
Collection variations boil down to how they quantify and
calculate link costs, the number of links they maintain, how
they propagate changes in link state amongst nodes, and
how frequently they re-evaluate link costs and switch parents. Early protocols used hop-counts8 as a link cost metric, similar to MANET protocols such as AODV and DSDV;
second-generation protocols such as MintRoute24 and Srcr2
estimated the transmissions per delivery on a link using periodic broadcasts; third-generation protocols, such as Mul-tiHopLQI, added physical layer signal quality to the metric;
current generation collection protocols, such as Collection
Tree Protocol (CTP), unify these approaches, drawing on information from multiple layers. 6
Most collection layers operate as anycast protocols. A network can have multiple data collection points, and collection automatically routes to the closest one. As there is only
one destination—any collection point—the required routing state can be independent of network density and size.
Most protocols use a small, fixed-size table of candidate next
figure 2: Sample collection tree, showing per-link and node costs.
the cost of a node is its next hop’s cost plus the cost of the link.
36
35
22
14
12
22
10
23
10
24
12
23
12
12
10
0
10
20
10
15
15
18
18
hops. They also attempt to strike a balance between route
stability and churn to discover new, possibly better parents
by switching parents infrequently and using damping mechanisms to limit the rate of change.
As collection protocols have improved and become better at choosing routes, reducing control traffic has become
an increasingly important component of efficiency. While
nodes can piggyback some control information on data
packets, they need to send link-layer broadcasts to their local neighbors to advertise their presence and routing cost.
Choosing how often to send these advertisements introduces a difficult design tension. A slow rate imposes a low overhead, but limits how quickly the tree can adapt to failures or
link changes, making its data traffic less efficient. A fast rate
imposes a higher overhead, but leads to an agile tree that
can more accurately find the best route to use.
This tension is especially challenging when a network
only collects data in response to events, and so can go
through periods of high and low data rates. Having a high
control rate during periods of low traffic is highly inefficient, while having a low control rate during periods of
high traffic makes the tree unable to react quickly enough
to changes. When starting a burst of transmissions, a node
may find that link costs have changed substantially necessitating a change in its route and, as a result, advertised
routing cost. Changes in costs need to propagate quickly, or
the topology can easily form routing loops. For example, if a
link’s cost increases significantly, then a node may choose
one of its children as its next hop. Since the protocol state
must be independent of the topology, a node cannot avoid
this by simply enumerating its children (constraining tree
in-degree to a constant leads to inefficient, circuitous topologies in dense networks).
Current protocols, such as CTP21 and ArchRock’s routing
layer, 1 resolve this tension by reducing the routing gradient
as a data consistency problem. The gradient is consistent as
long as children have a higher cost than their parent. An inconsistency can arise when costs change enough to violate
