Directed Diffusion: Difference between revisions

From
Jump to navigation Jump to search
 
(10 intermediate revisions by the same user not shown)
Line 117: Line 117:
===data propagation===
===data propagation===


* sensor node that's in specified rect processes interests
Direct Diffusion
* 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
data propagation
* 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
sensor node that's in specified rect processes interests
* 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:
node tasks its local sensors to begin collecting samples
** e.g.
.
*** type = Tour-legged animal - type of animal Seen
algorithms simply match sampled waveforms against a
*** instance = elephant - instance of this type
library of presampled, stored waveforms
*** location = [125, 220] - node location
.
*** intensity = 0.6 - Signal amplitude measure
the algorithms usually associate a degree of confidence
*** confidence = 0.85 - confidence in the match
with the match
*** timestamp = 01:20:40 - local time rohen event was generated
.
* this data message is, unicast individually to the relevant neighbors
a sensor node that detects a target searches its interest
cache for a matching interest entry
* 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 associated with the matching interest entry
when it finds one, it computes the highest requested
* this cache keeps track of recently seen data items
event rate among all its outgoing gradients
* it has several potential uses, one of which is loop prevention
.
* if a received data message has a matching data cache entry, the data message is silently dropped
the node tasks its sensor subsystem to generate event
* the received message is added to the data cache and the data message is resent to the node's neighbors
samples at this highest data rate
* 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
Direct Diffusion
* if some gradients have a lower data rate than others, then the node may downconvert to the appropriate gradient

* 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
data propagation
* 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
in our example, this data rate is initially 1 event per
* it can significantly improve network performance
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===
===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)
Direct Diffusion
* 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
* to reinforce this neighbor, the sink resends the original interest message but with a smaller interval (higher data rate)
** e.g.
*** 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
* 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


* 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
reinforcement
* 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
in the scheme we have described so far, the sink initially
** e.g.: if the sink reinforces neighbor A, but then receives a new event from neighbor B, it will reinforce the path through B
diffuses an interest for a low event-rate notification (1
* one mechanism for negative reinforcement is to time out all high data rate gradients in the network unless they are explicitly reinforced
event per second)
* 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
once sources detect a matching target (send low-rate
* 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
events)
* this sequence of local interactions ensures that the path through A is degraded rapidly, but at the tost of increased resource utilization
.
* we need to specify what local rule a node uses in order to decide whether to negatively reinforce a neighbor or not
after the sink starts receiving these low data rate events,
* this rule is orthogonal to the choice of mechanism for negative reinforcement
it reinforces one particular neighbor in order to "draw
* 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
down" higher quality (higher data rate) events
* 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
one example of such a rule is to reinforce any neighbor
* describe a single-source scenario
from which a node receives a previously unseen event
** 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
Direct Diffusion
** 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

.
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===
===discussion===
* we implicitly described a particular usage-interests set up gradients drawing down data
* 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
the directed diffusion paradigm itself does not limit the
* 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
designer to this particular usage
* a sensor node can use this to warn other sensor nodes of impending activity
.
* key features of diffusion, and how it differs from traditional networking
other usages are also possible
* diffusion is data-centric
.
* all communication in a diffusion-based sensor network uses interests to specify named data
nodes may propagate data in the absente of interests,
* 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
implicitly setting up gradients when doing so
* there are no "routers" in a sensor network
.
* each sensor node can interpret data and interest messages
to spontaneously propagate an important event to some
section of the sensor field
* justified by the task-specificity of sensor networks
* not general-purpose communication networks
.
* no globally unique id's or globally unique addresses
a sensor node can use this to warn other sensor nodes
* nodes, do need to distinguish between neighbors
of impending activity
* it is possible to perform coordinated sensing close to the sensed phenomena, because every node can cache, aggregate, and more generally, process messages

* 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
Direct Diffusion
* 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
discussion
* '''why this peculiar choice of design?'''
.
** path setup algorithms that establish network paths using strictly local (neighbor-to-neighbor) communication
key features of diffusion, and how it differs from tradi
** build up transmission paths using such communication scale well and are extraordinarily robust

** cannot use global topology metrics
tional networking
** local communication implies that the data that it received from a neighbor came from that neighbor
.
** energy efficient in highly dynamic networks
diffusion is data-centric
** the resulting communication paths may be sub-optimal
.
** this approach trades off some energy efficiency for increased robustness and scale
all communication in a diffusion-based sensor network
* 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
uses interests to specify named data
* much experimentation and evaluation of the various mechanisms is necessary before we fully understand the robustness, scale and performance implications of diffusion in general

.
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 directed diffusion===


* we use packet-level simulation to explore, in some detail, the implications of some of our design choices
evaluating
* goals in conducting this evaluation study
.
* place the performance of diffusion in the context of idealized schemes (flooding and omniscient multicast)
we use packet-level simulation to explore, in some detail, the implications of some of our design choices
* understand the impact of dynamics-such as node failures-on diffusion
.
* explore the influence of the radio MAC layer on diffusion performance
goals in conducting this evaluation study
* study the sensitivity of directed diffusion performance to the choice of parameters
.
place the performance of diffusion in the context of
* 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
idealized schemes (flooding and omniscient multicast)
* 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
understand the impact of dynamics-such as node failures-on diffusion
* 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
explore the influence of the radio MAC layer on diffusion performance
* 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
study the sensitivity of directed diffusion performance
* to study the performance of diffusion as a function of network size, we generate a variety of sensor fields of different sizes
to the choice of parameters
* 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
Direct Diffusion
* 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
evaluating
* 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
two metrics to analyze the performance of directed diffusion and to compare it to other schemes:
* sinks are uniformly scattered across the sensor field
.
* each source generates two events per second
average dissipated energy measures the ratio of
* the low data rate for directed diffusion was chosen to be one event in 50 seconds
total dissipated energy per node in the network to the
* events were modeled as 64 byte packets, interests as 36 byte packets
number of distinet events seen by sinks
* interests were periodically generated every 5 seconds
.
* and the interest duration was 15 seconds
average delay measures the average one-way
* the window for negative reinforcement to be 2 seconds
latency observed between transmitting an event and
* first experiment compares diffusion to two idealized schemes for data dissemination in networks
receiving it at each sink
* in the flooding scheme, sources flood all events to every node in the network
.
* flooding is a watermark for directed diffusion
we operate the sensor network far from overload
* 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
exploring the behavior of diffusion under congestion is
* we do not simulate the tree construction protocols
the subject of future research
* omniscient multicast approximately indicates the performance achievable in an IP-based sensor network
.
* omniscient multicast dissipates a little less than a half as much energy per packet per node than flooding
we note that there exist plausible approaches for dealing
* directed diffusion has noticeably better energy efficiency than omniscient multicast
with congestion in diffusion-based sensor networks
* 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?
Direct Diffusion
* our choice of reinforcement and negative reinforcement is very conservative

* 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
evaluating
* the delay experienced by flooding is almost an order of magnitude higher than other schemes
.
despite this focus an uncongested operating regimes,
* 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
directed diffusion can incur event losses, particularly
* we simulated node failures as follows:
under dynamics
** for each sensor field, repeatedly turned off a fixed fraction of nodes for 30 seconds
.
** each source sends different location estimates
in these situations, another metric for the performance
** the average dissipated energy actually improves in the presence of node failures
of diffusion, is the event delivery ratio
** 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
* 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
evaluating
* 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)
.
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==
==summary==
Line 841: Line 304:
==references==
==references==


* 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: ”("[http://www-csag.ucsd.edu/teaching/cse291s03/Readings/directed_diffusion.pdf 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: ("[http://www.inf.ethz.ch/vs/publ/papers/sensornetze.pdf Drahtlose Sensornetze]")"

Latest revision as of 12:00, 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
  • 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
  • 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

  • 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
  • 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:
    • e.g.
      • type = Tour-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 - local time rohen event was generated
  • 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 associated with the matching interest entry
  • this cache keeps track of recently seen data items
  • it has several potential uses, one of which is loop prevention
  • if a received data message has a matching data cache entry, the data message is silently dropped
  • 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
  • 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

  • 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
  • to reinforce this neighbor, the sink resends the original interest message but with a smaller interval (higher data rate)
    • e.g.
      • 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
  • 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
  • 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
  • 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
  • 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
  • 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
  • key features of diffusion, and how it differs from traditional 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
  • each sensor node can interpret data and interest messages
  • 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
  • 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
  • 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 received 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 increased robustness and scale
  • 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

  • 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
  • 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
  • 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
  • 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
  • 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
  • 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
  • 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
  • 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
  • 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