Directed Diffusion: Difference between revisions
Line 842: | Line 842: | ||
* Intanagonwiwat, Chalermek; Govindan, Ramesh; Estrin, Deborah: ”Directed Diffusion: A Scalable and Robust Communication Paradigm for Sensor Networks“. Boston MA USA |
* Intanagonwiwat, Chalermek; Govindan, Ramesh; Estrin, Deborah: ”Directed Diffusion: A Scalable and Robust Communication Paradigm for Sensor Networks“. Boston MA USA |
||
* Mattern, Friedemann; Röomer, Kay: ”Drahtlose Sensornetze“ (http://www.inf.ethz.ch/vs/publ/papers/sensornetze.pdf |
* Mattern, Friedemann; Röomer, Kay: ”Drahtlose Sensornetze“ (http://www.inf.ethz.ch/vs/publ/papers/sensornetze.pdf) |
Revision as of 11:40, 29 January 2005
Introduction
sensor networks
- small and cheap nodes
- addition of sensing capability
- can coordinate to perform distributed sensing of environmental phenomena
- enable low maintenance sensing in more benign, but less accessible, environments
2 categories of sensor networks today
- large, complex sensor systems usually deployed very far away from the phenomena to be sensed, and employ complex signal processing algorithms to separate targets from environmental noise
- a carefully engineered network of sensors is deployed in the field, but individual sensors do not posses computation capability, instead transmitting time series of the sensed phenomena to one er more nodes which perform the data reduction and filtering
expected architectures
- a matchbox sized form factor
- battery power source
- power-conserving processor clocked at several 100 Mhz
- program and data memory amounting to several tens of Mbytes
- a radio modem
- analog-to digital conversion system on such nodes
- a sensor node may possess a GPS receiver
directed diffusion
- consists of several elements
- data is named using attribute-value pairs
- a sensing task is disseminated throughout the sensor network as an interest for named data
- this dissemination sets up gradients within the network designed to "draw" events
- events start flowing towards the originators of interests along multiple paths
- sensor network reinforces one, or a small number of these paths
naming
- task descriptions are named by, for example, a list of attribute-value pairs that describe a task
- e.g.: animal tracking task:
- type = four-legged animal - detect animal location
- interval = 20 ms - send back events every 20 ms
- duration = 10 seconds - ... for the next 10 seconds
- rect = [-100, 100, 200, 400] - from sensors within rectangle
- choose the subregion representation to be a rectangle defined on some coordinate system
- in practice, this might be based an GPS coordinates
- e.g.: animal tracking task:
- intuitively, the task description specifies an interest for data matching the attributes (called an interest)
- data sent in response to interests are also named using a similar naming scheme
- for example, a sensor that detects an animal might generate the following data:
- type = four-legged animal - type of animal Seen
- instance = elephant - instance of this type
- location = [125, 220] - node location
- intensity = 0.6 - signal amplitude measure
- confidence = 0.85 - confidence in the match
- timestamp = 01:20:40 - event generation time
- for example, a sensor that detects an animal might generate the following data:
- given a set of tasks supported by a sensor network
- selecting a naming scheme is the first step in designing directed diffusion for the network
- each attribute has an associated value range
- value of an attribute can be any subset of its range
- there are other choices for attribute value ranges (e.g., hierarchical) and other namingschemes (such as intentional names)
- the choice of naming scheme can affect the expressivity of tasks, and may impact performance of a diffusion algorithm
interests and gradients
- an interest is injected into the network at some (possibly arbitrary) node in the network (sink)
- for each active task, the sink periodically broadcasts an interest message to each of its neighbors
- the initial interest contains a larger interval attribute
- this initial interest may be thought of as exploratory
- type = four-legged animal
- interval = ls
- Rect = [-100, 200, 200, 400]
- timestamp = 01:20:40 - hh:mm:ss
- expiresAt = 01:30:40
- how interests are processed?
- interest is periodically refreshed by the sink
- the refresh rate is a protocol design parameter that trades off overhead for increased robustness to lost interests
- every node maintains an interest cache
- two interests are distinct, if their type attribute differs, their interval attribute differs, or their rect attributes are (possibly partially) disjoint
- interest entries in the cache do not contain information about the sink
- our definition of distinct interests also allows interest aggregation
- an entry in the interest cache has several fields
- a timestamp field indicates the timestamp of the last received matching interest
- the interest entry also contains several gradient fields, up to one per neighbor
- each gradient contains a data rate field requested by the specified neighbor and a duration field
- when a node receives an interest, it checks to see if the interest exists in the cache
- if no matching entry exists, the node creates an interest entry
- this entry has a single gradient towards the neighbor from which the interest was received
- individual neighbors, so any locally unique neighbor identifier may be used (802.11 MAC or Bluetoothcluster addresses)
- if there exists an interest entry, but no gradient for the sender of the interest, the node adds a gradient with the specified value
- it also updates the entry's timestamp and duration fields appropriately
- if there exists both the node simply updates the timestamp and duration fields
- when a gradient expires, it is removed from its interest entry
- when all gradients for an interest entry have expired, the interest entry itself is removed from a cache
- after receiving an interest, a node may decide to resend the interest to some subset of its neighbors
- to its neighbors, this interest appears to originate from the sending node
- interests diffuse throughout the network
- there are several possible choices for neighbors
- simplest is to rebroadcast the interest to all neighbors
- in the absence of information about which sensor
- nodes are likely to be able to satisfy the interest, this is the only choice
- when a node receives an interest from its neighbor, it has no way of knowing whether that interest was in response to one it sent out earlier, or is an identical interest from another sink an the "other side" of that neighbor
- such two-way gradients can cause a node to receive one copy of low data rate events from each of its neighbors
- this technique can enable fast recovery from failed paths or reinforcement of empirically better paths, and does not incur persistent loops
- a gradient specifies both a data rate and a direction in which to send events (value and direction)
- the directed diffusion paradigm gives the designer the freedom to attach different semantics to gradient values
- gradient values might be used to probabilistically forward data along different paths, achieving some measure of load balancing
- interest propagation sets up state in the network to facilitate "pulling down" data towards the sink
- the interest propagation rules are local
- a sensor network may support many different task types
- interest propagation rules may be different for different task types
- some elements of interest propagation are similar:
- the form of the cache entries, the interest re-distribution rules etc..
- we hope to cull these similarities into a diffusion substrate at each node, so that sensor network designers can use a library of interest propagation techniques for different task types
data propagation
Direct Diffusion
.
data propagation
.
sensor node that's in specified rect processes interests
.
node tasks its local sensors to begin collecting samples
.
algorithms simply match sampled waveforms against a
library of presampled, stored waveforms
.
the algorithms usually associate a degree of confidence
with the match
.
a sensor node that detects a target searches its interest
cache for a matching interest entry
.
when it finds one, it computes the highest requested
event rate among all its outgoing gradients
.
the node tasks its sensor subsystem to generate event
samples at this highest data rate
Direct Diffusion
.
data propagation
.
in our example, this data rate is initially 1 event per
second
. the source then sends to each neighbor for whom it has a gradient, an event description every second of the form:
. type = Tour-legged animal II type of animal Seen . instance = elephant II instance of this type . location = [125, 220] II node location . intensity = 0.6 II Signal amplitude measure . confidence = 0.85 II confidence in the match . timestamp = 01:20:40 II local time rohen event was generated
Direct Diffusion
.
data propagation
.
this data message is, unicast individually to the relevant
neighbors
.
a node that receives a data message from its neighbors
attempts to find a matching interest entry in its cache . if no match exists, the data message is silently dropped . if a match exists, the node checks the data cache asso
ciated with the matching interest entry . this cache keeps track of recently seen data items . it has several potential uses, one of which is loop pre
vention . if a received data message has a matching data cache entry, the data message is silently dropped
Direct Diffusion
.
data propagation
.
the received message is added to the data cache and
the data message is resent to the node's neighbors
.
by examining its data cache, a node can determine the
data rate of received events
.
to resend a received data message, a node needs to
examine the matching interest entry's gradient list
.
if all gradients have a data rate that is greater than or
equal to the rate of incoming events, the node may
simply send the received data message to the appropriate neighbors
.
if some gradients have a lower data rate than others,
then the node may downconvert to the appropriate
gradient
Direct Diffusion
.
data propagation
.
a node that has been receiving data at 100 events per
second, but one of its gradients is at 50 events per
second
.
the node may only transmit every alternate event towards the corresponding neighbor
.
it might interpolate two successive events in an application-specific way
.
loop prevention and downconversion illustrate the power
of embedding application semantics in all nodes
.
this design is not pertinent to traditional networks, it is
feasible with application-specific sensor networks
.
it can significantly improve network performance
reinforcement
Direct Diffusion
.
reinforcement
.
in the scheme we have described so far, the sink initially
diffuses an interest for a low event-rate notification (1
event per second)
.
once sources detect a matching target (send low-rate
events)
.
after the sink starts receiving these low data rate events,
it reinforces one particular neighbor in order to "draw
down" higher quality (higher data rate) events
.
one example of such a rule is to reinforce any neighbor
from which a node receives a previously unseen event
Direct Diffusion
.
reinforcement
.
to reinforce this neighbor, the sink resends the original
interest message but with a smaller interval (higher data
rate):
.
type = four-legged animal
.
interval = 10ms
.
rect = [-100, 200, 200, 400]
.
timestamp = 01:22:35
.
ExpiresAt = 01:30:40
.
when the neighboring node receives this interest, it notices that it already has a gradient towards this neighbor
and that the sender's interest specifies a higher data
rate than before
Direct Diffusion
.
reinforcement
.
if this new data rate is also higher than existing gradient,
the node must also reinforce at least one neighbor
.
how does it do this?
.
the node uses its data cache for this purpose (again
local rule choices)
.
this node might choose that neighbor from whom it first
received the latest event matching the interest
.
through this sequence of local interactions, a path is established from source to sink transmission for high data
rate events
.
the local rule we described above, then, selects an empirically low delay path
.
it is very reactive to changes in path quality
Direct Diffusion
.
reinforcement
.
one path delivers an event faster than others, the sink
attempts to use this path to draw down high quality data
.
because it is triggered by receiving one new event, this
could be wasteful of resources
.
these choices trade off reactivity for increased stability
.
exploring this tradeoff requires significant experimentation and is the subject of future work
.
the algorithm described above can result in more than
one path being reinforced
.
e.g.: if the sink reinforces neighbor A, but then receives
a new event from neighbor B, it will reinforce the path
through B
Direct Diffusion
.
reinforcement
.
one mechanism for negative reinforcement is to time out
all high data rate gradients in the network unless they
are explicitly reinforced
.
another approach is to explicitly degrade the path
through A by resending the interest with the lower data
rate
.
when A receives this interest, it degrades its gradient
towards the sink
.
if all its gradients are now low data rate a negatively reinforces those neighbors that have been sending data to
it at a high data rate
.
this sequence of local interactions ensures that the path
through A is degraded rapidly, but at the tost of increased resource utilization
Direct Diffusion
.
reinforcement
.
we need to specify what local rule a node uses in order
to decide whether to negatively reinforce a neighbor or
not
.
this rule is orthogonal to the choice of mechanism for
negative reinforcement
.
one plausible choice for such a rule is to negatively reinforce that neighbor from which no new events have
been received within a window of N events or time
T
.
such a rule is a bit conservative and energy inefficient
.
significant experimentation is required before deciding
which local rule achieves an energy efficient global behavior
Direct Diffusion
.
reinforcement
.
describe a single-source scenario
.
the rules we have described work with multiple
sources
. internodes on a previously reinforced path can apply the
reinforcement rules . useful to enable local repair of failed or degraded paths . our description so far has glossed over the fact that a
straightforward application of reinforcement rules will cause all nodes downstream of the lossy link to also initiate reinforcement procedures
. this will eventually lead to the discovery of one empirically good path, but may result in wasted resources
discussion
- we implicitly described a particular usage-interests set up gradients drawing down data
. the directed diffusion paradigm itself does not limit the
designer to this particular usage . other usages are also possible . nodes may propagate data in the absente of interests,
implicitly setting up gradients when doing so . to spontaneously propagate an important event to some section of the sensor field . a sensor node can use this to warn other sensor nodes of impending activity
Direct Diffusion
.
discussion
.
key features of diffusion, and how it differs from tradi
tional networking . diffusion is data-centric . all communication in a diffusion-based sensor network
uses interests to specify named data
. all communication in diffusion is neighbor-to-neighbor, unlike the end-to-end communication in traditional data networks
. every node is an "end" in a sensor network . there are no "routers" in a sensor network
Direct Diffusion
.
discussion
.
each sensor node can interpret data and interest mes
sages . justified by the task-specificity of sensor networks . not general-purpose communication networks . no globally unique id's or globally unique addresses . nodes, do need to distinguish between neighbors . it is possible to perform coordinated sensing close to the
sensed phenomena, because every node can cache, aggregate, and more generally, process messages
Direct Diffusion
.
discussion
.
diffusion is clearly related to traditional network data
routing algorithms
.
it is a reactive routing technique, but it differs from other
ad-hoc reactive routing techniques in several ways . no loopfree path between source and sink . reinforcement attempts to reduce this multiplicity of
paths to a small number, based an empirically observed
path performance . a message cache is used to perform loop avoidance . the interest and gradient setup mechanisms themselves
do not guarantee loop-free paths between source and sink.
Direct Diffusion
.
discussion
. why this peculiar choice of design?
. path setup algorithms that establish network paths using
strictly local (neighbor-to-neighbor) communication
.
build up transmission paths using such communication
scale well and are extraordinarily robust
. cannot use global topology metrics
. local communication implies that the data that it re
ceived from a neighbor came from that neighbor
. energy efficient in highly dynamic networks
. the resulting communication paths may be sub-optimal
.
this approach trades off some energy efficiency for in
creased robustness and scale
Direct Diffusion
.
discussion
.
it might appear that the particular instantiation that we
chose, location tracking, has limited applicability
.
location tracking captures many of the essential features
of a large class of remote surveillance sensor networks
. much experimentation and evaluation of the various mechanisms is necessary before we fully understand the robustness, scale and performance implications of diffusion in general
evaluating directed diffusion
evaluating . we use packet-level simulation to explore, in some detail, the implications of some of our design choices . goals in conducting this evaluation study . place the performance of diffusion in the context of idealized schemes (flooding and omniscient multicast) . understand the impact of dynamics-such as node failures-on diffusion . explore the influence of the radio MAC layer on diffusion performance . study the sensitivity of directed diffusion performance to the choice of parameters
Direct Diffusion
.
evaluating
.
two metrics to analyze the performance of directed diffusion and to compare it to other schemes:
.
average dissipated energy measures the ratio of
total dissipated energy per node in the network to the
number of distinet events seen by sinks
.
average delay measures the average one-way
latency observed between transmitting an event and
receiving it at each sink
.
we operate the sensor network far from overload
.
exploring the behavior of diffusion under congestion is
the subject of future research
.
we note that there exist plausible approaches for dealing
with congestion in diffusion-based sensor networks
Direct Diffusion
.
evaluating
.
despite this focus an uncongested operating regimes,
directed diffusion can incur event losses, particularly
under dynamics
.
in these situations, another metric for the performance
of diffusion, is the event delivery ratio
Direct Diffusion
.
evaluating
. to study the performance of diffusion as a function of network size, we generate a variety
of sensor fields of different sizes
. five different sensor fields, ranging from 50 to 250 nodes in increments of 50 nodes
. our 50 node sensor field generated by randomly placing the nodes in a 160m by 160m
square
. each node has a radio range of 40m
. other sizes are generated by scaling the square and keeping the radio range constant in
order to approximately keep the average density sensor nodes constant
. for each network size, our results are averaged over three different generated fields
. the ns-2 simulator implements a 1.6 Mbps 802.11 MAC layer
. this is not a completely satisfactory choice of MAC layer
. a fixed workload which consists of five sources and five sinks
. all sources are randomly selected from nodes in a 70m by 70m square within the sensor
field
. sinks are uniformly scattered across the sensor field
. each source generates two events per second
. the low data rate for directed diffusion was chosen to be one event in 50 seconds
. events were modeled as 64 byte packets, interests as 36 byte packets
. interests were periodically generated every 5 seconds
. and the interest duration was 15 seconds
. the window for negative reinforcement to be 2 seconds
Direct Diffusion
.
evaluating
.
first experiment compares diffusion to two idealized
schemes for data dissemination in networks
.
in the flooding scheme, sources flood all events to
every node in the network
.
flooding is a watermark for directed diffusion
.
if the latter is not significantly more energy efficient than flooding, it
cannot be considered viable for sensor networks
. in the omniscient multicast scheme, each source transmits its events along a shortest-path multicast tree to all sinks
. we do not simulate the tree construction protocols . omniscient multicast approximately indicates the performance achievable in an IP-based sensor network
Direct Diffusion
.
evaluating
.
omniscient multicast dissipates a little less than a half as
much energy per packet per node than flooding
.
directed diffusion has noticeably better energy efficiency
than omniscient multicast
.
for some sensor fields, its dissipated energy is only 60%
that of omniscient multicast
.
it achieves significant energy savings by reducing the
number of paths over which redundant data is delivered
.
why is diffusion not nearly five times more energy efficient than omniscient multicast?
.
our choice of reinforcement and negative reinforcement
is very conservative
Direct Diffusion
.
evaluating
.
average delay observed as a function of network size
.
directed diffusion has a delay comparable to omniscient
multicast . our reinforcement rules seem to be finding the low delay paths . the delay experienced by flooding is almost an order of
magnitude higher than other schemes . this is an artifact of the MAC layer . on a sensor radio that employs a TDMA MAC-layer, we
might expect flooding to exhibit a delay comparable to the other schemes
Direct Diffusion
.
evaluating
.
we simulated node failures as follows:
.
for each sensor field, repeatedly turned off a fixed
fraction of nodes for 30 seconds
.
each source sends different location estimates
.
the average dissipated energy actually improves in the
presence of node failures
. as it turns out, our negative reinforcement rules are conservative enough that several high-quality paths are kept alive in normal operation
. the lower energy dissipation results from the failure of some high-quality paths . we take these results to indicate that the mechanisms in diffusion are relatively stable at the levels of dynamics
Direct Diffusion
.
evaluating
.
directed diffusion's energy efficiency -quantify negative
reinforcement
.
we selectively turn off negative reinforcement and compare the performance of directed diffusion with and
without reinforcement
.
one would expect negative reinforcement to contribute
significantly to energy savings
.
diffusion without negative reinforcement expends nearly
twice as much energy as when negative reinforcement
is employed
.
our conservative negative reinforcement rules prune off
paths which deliver consistently higher latency
.
diffusion's delay increases by factors of three to eight
(artifact of the 802.11 MAC layer)
summary
references
- Intanagonwiwat, Chalermek; Govindan, Ramesh; Estrin, Deborah: ”Directed Diffusion: A Scalable and Robust Communication Paradigm for Sensor Networks“. Boston MA USA
- Mattern, Friedemann; Röomer, Kay: ”Drahtlose Sensornetze“ (http://www.inf.ethz.ch/vs/publ/papers/sensornetze.pdf)