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

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