Directed Diffusion

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)

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")"