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