Directed Diffusion

From
Revision as of 11:24, 29 January 2005 by 213.54.193.41 (talk) (→‎naming)
Jump to navigation Jump to search

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


data propagation

reinforcement

evaluating directed diffusion

summary

references