3.5 Attribute-Based Routing 91
the region. One of two different strategies can be used here. Recursive
geographic forwarding refers to a process of recursively partitioning
the region R into quadrants and then forwarding the packet from x
to the centroid of each quadrant. Restricted flooding refers to initiating
a broadcast flooding process from x that is clipped at the boundary
of R. While restricted flooding has the “wireless multicast advantage”
mentioned earlier, it may still prove wasteful when the region R is
densely populated by nodes and the same packet reaches a node mul-
tiple times. The issue of determining the best strategy for distribution
within R needs further study.
3.5 Attribute-Based Routing
The previous section focused on routing algorithms based on prior
knowledge about the geographic destination of a packet. In more
general settings of data-centric routing, however, we cannot assume
that we know either the network address or the geographic location
of the node we wish to communicate with. Geographic location ser-
vices can be used to map from node IDs to locations, as discussed
in Section 4.4.4. In this section, we present more general protocols,
whose goal is to enable nodes desiring certain types of information
and nodes having that information to find each other in the net-
work and maintain good communication paths between them. To
perform this kind of matching, we will assume that data is described
by attribute-value pairs that characterize the information that a node
holds or seeks. For instance, a node tasked to look for animals in an
environmental monitoring setting might detect a horse, based on
its sensor readings (the details of how this is done do not concern
us here). At that point, this node might generate an attribute-value
event record of the following type:
type = animal // named record type
instance = horse // instance of this type
location = [89, 154] // location of horse
time = 02:45:23 // time of detection
92 Chapter 3 Networking Sensors
Each line in this record is an (attribute, value) pair. Correspondingly,
a node seeking information about horses in a certain region might
create an information request record of the form:
type = animal // named record type
instance = horse // instance of this type
rect = [0, 200, 0 200] // a spatial range of interest
This record specifies a rectangular range indicating that the request-
ing node is interested in horse detections in the specified rectangle
(here, for simplicity, taken to be parallel to the axes and specified
by an x and y interval). In general, ranges can be specified for any
type of continuous value that can be stored in a record, thus allowing
general range queries as information requests.
We now discuss a number of techniques aimed at allowing the
network to discover which event records and information requests
match and maintain communication paths between information
sources and sinks.
3.5.1 Directed Diffusion
Directed diffusion [104] is a very general approach toward problems
of this type. Nodes requesting information are called sinks, while
those generating information are called sources. Records indicating
a desire for certain types of information are called interests. Interests
are propagated across the network, looking for nodes with match-
ing event records. Key to directed diffusion is the assumption that
interests are persistent—that is, if a source has information relevant
to a sink, then the sink will be interested in repeated measurements
from that source for some period of time. A typical interest record
contains an interval attribute field, indicating the frequency with
which the sink wishes to receive information about objects matching
the other record attributes. This longevity of communication pat-
terns allows the directed diffusion protocols to learn which are good
paths between sources and sinks and amortize the cost of finding

Get Wireless Sensor Networks now with O’Reilly online learning.

O’Reilly members experience live online training, plus books, videos, and digital content from 200+ publishers.