CENS - Center for Embedded Networked Sensing


TinyDiffusion in the Extensible Sensing System at the James Reserve


Manamohan Mysore
Moshe Golan
Eric Osterweil
Deborah Estrin 
Mohammad Rahimi


Table of Contents

1

Introduction

2

Background Information

3

Overview of the One Phase Pull Implementation

4

NesC Interfaces provided by the OnePhasePull Implementation

5

Internals of the One Phase Pull Implementation

6

Installation Instructions

7

Acknowledgments

8

References


Introduction


This document describes the design and implementation of a simplified version of Diffusion [1] (which we call TinyDiffusion) on "mote" devices running TinyOS.  This implementation makes it very convenient for a developer to write applications that request, send or modify data in a sensor network of "mote" devices.   We hope that our implementation and this document will be useful to researchers interested in harnessing a sensor network without having to bother about the fine details involved in ensuring energy-efficient communication.  Any queries, comments or suggestions are welcome and may be directed to the email address mentioned at the every end of this page.

This software is currently in use in the Extensible Sensing System at the James Reserve.  It runs on a network of Mica2 motes having very small memory (4KB) and processing (4MHz Atmel 128L processor) resources.  In addition, these motes run off of batteries (or low capacity solar cells) and are hence energy limited.   The design and implementation of TinyDiffusion has largely been shaped by these constraints.  

Background Information

Diffusion

Diffusion is an  communication scheme for sensor networks that allows easy and energy-efficient tasking of and data retrieval from  a network of sensors.   Diffusion (as proposed in [1]) involves two phases of operation.  In the first phase, a "sink" node broadcasts Exploratory Interest messages that are flooded throughout the sensor network.  Exploratory Interest messages consist of attributes which specify a set of constraints to be met by the data that the sink expects.  Sources with data matching these constraints send Exploratory Data messages back along the "gradients" along which the Exploratory Interests were received (which could involve several neighbors).  In the second phase, the Sink, upon receiving matching Data Messages sends Reinforcement Interest messages to specific neighbors who delivered useful data.   These neighbors in turn "reinforce" the neighbors that provided useful data and this process continues.  The diagram below depicts the operation of "original" Diffusion.

Operation of Diffusion

One Phase Pull: a variant of Diffusion


"Original" Diffusion involves two message intensive "exploratory" phases in addition to the explicity "reinforcement" phase.  In order to reduce the network overhead of Diffusion, the "One Phase Pull" variant has been proposed for single-sink-at-a-time scenarios.    The following diagram illustrates the evidently much simpler operation of One Phase Pull proposed by Silva and Heidemann [2].

Operation of One Phase Pull Diffusion

Now since Data travels back on the same links that delivered the Interests, One Phase Pull requires the use of symmetric links.  In our implementation, we use a module that ensures the characterization and selection of symmetric links.

One Phase Pull in the Extensible Sensing System


The ESS uses One Phase Pull enforcing the constraint that a source sends data towards a single sink at a time.  This makes sense with the ESS because we are interested in data reaching a backend database irrespective of which "sink" ("clusterhead" or "captain" node) the data passed through.  The enforcement of the single-sink-at-a-time constraint is made by including specific attributes in the Interest and Data packets constraining the CLUSTEDHEAD_KEY to a certain chosen node id.


Diffusion Operation in the ESS


Overview of the One Phase Pull Implementation

Location of the Code Base


The current home for our TinyDiffusion implementation is the tinydiff directory of the tos-contrib repository in the cvs.cens.ucla.edu CVS server.  Details about getting access to this server can be found at http://cvs.cens.ucla.edu/.   The directory organization  under tinydiff is the same as that of a contrib directory under the SourceForge TinyOS CVS.  The flexibility of having our code in a contrib-style directory is that it can be linked to any TinyOS (version >= 1.0) tree but simply defining that TOSDIR environment variable to point to the "tos" directory of that TinyOS tree.  

Overall Structure


The following diagram depicts the overall structure of a system using our OPP Diffusion and the Neighborlist implementation.  As mentioned before the use of the Neighborlist module is essential because of OnePhasePull's dependence on symmetric links).  More information about the Neighborlist Implementation can be found in the corresponding design document [3].


OPP - Neighborlist module structure

In the diagram above, the following are the roles played by the various modules:
The code for these modules/configurations can be found in the corresponding ".nc" files.  For example, the code for NeighborBeacon can be found in NeighborBeacon.nc.  Most of these corresponding ".nc" files can be found in tos/lib.  ExtGenericComm has been placed under tos/system.

In practice, the programmer interested in using Diffusion would need to use the configuration "OnePhasePullNlist" and understand the Subscribe, Publish and Filter interfaces (described below).

More information on the design of the One Phase Pull implementation can be found below in the "Design of the OnePhasePull Implementation" section.

NesC Interfaces provided by the OnePhasePull Implementation

The key interfaces provided by OnePhasePull to applications are Subscribe, Publish and Filter.  These interface definitions may be found under the tos/interfaces directory.

The Subscribe interface

interface Subscribe {

  // subscribe for a certain data type:
  // attributes: array of attributes
  // numAttrs: number of attributes contained therein 
  command SubscriptionHandle subscribe(AttributePtr attributes, uint8_t numAttrs);
 
  // unsubscribe a subscription specified by handle...
  command result_t unsubscribe(SubscriptionHandle handle);

  // Serve up data that matched the subscription...
  // handle: subscription handle previously returned...
  // attributes: attributes in matching data message
  // numAttrs: number of attributes in the above array of attributes
  // NOTE: the app is expected to release back attributes array after
  // copying it...  so there's no two way hand-shake here...
  event result_t receiveMatchingData(SubscriptionHandle handle,
                     AttributePtr attributes,
                     uint8_t numAttrs);
}
module OnePhasePullM {
  provides {
    .
    .
    interface Subscribe; // later versions will perhaps support a parameterized interface
  }

    .
    .
}

This interface is for use with applications that want to act as Sinks.  Subscribe.subscribe passes down a list of attributes to OnePhasePull that will comprise the attribute fields of the Interest packet that is consequently sent out.  Upon receiving matching data, the receiveMatchingData event (upcall) is called.   It is important to remember that attribute array passed in the receiveMatchingData event is not for use by the application.  The application is expected to copy out the attribute array into its own data structures and must not hold on to the AttributePtr.


NOTES:The current implementation has a flaw in that there is only one Subscribe interface that is provided by OnePhasePull.  So all "used" Subscribe interfaces that are wired to that interface will receive all events on that interface (due to TinyOS fan-in fan-out capability) -- even if it is meant for one specific subscription... and applications will have to figure out if it's actually meant for them by means of the handle parameter.  This is not an issue at all if there is a single subscriber application.  This will perhaps be addressed in later versions by means of a parameterized "Subscribe" interface.  

This interface might change if and when we introduce support for the "blob" attribute type.

The Publish interface


interface Publish {

    // Pre: numAttrs - number of attributes contained in array
    //      attributes - an array  containing the attribute list
    command PublicationHandle publish(Attribute *attributes,
                                      uint8_t numAttrs);

    // Pre: numAttrs - number of attributes contained in array
    //      attributes - an array  containing the attribute list
    //      handle - PublicationHandle returned by publish...
    //Post: Sends data packet down stream from source to sink.
    //NOTE: the maximum number of attributes that can be sent down is
    //(MAX_ATT - 2) and not MAX_ATT because sendData internally adds the
    //"CLASS IS DATA" and "ESS_CLUSTERHEAD_KEY IS <chosen_clusterhead>"
    //attribute in addition to the data sent down...
    command result_t sendData(PublicationHandle handle,
                                 AttributePtr  attributes, uint8_t numAttrs);

    command result_t unPublish(PublicationHandle handle);
}


module OnePhasePullM {
  provides {
    .
    .
    interface Publish;
// later versions will perhaps support a parameterized interface
  }
    .
    .
}

This interface is used by an application that "publishes" data on the sensornet.  Calling Publish.publish() registers with OnePhasePull the attributes that are common among all calls to Publish.sendData().  Publish.sendData() is the command by which the application actually sends down data in the form of an attribute array.    Publish.publish() is for convenience of applications that need to include certain common attributes (say, sensor type and id for a temperature sensing application) implicitly in each invocation to Publish.sendData().  Multiple data items of the same type are included as separate attributes.   Publish.unpublish() undoes the effect of Publish.publish() by erasing the common attributes.

In the ESS implementation, a call to Publish.sendData() can have at most (MAX_ATT - 2) attributes.  This is because the current OnePhasePull implementation of Publish.sendData() automatically prepends two attributes: "CLASS IS DATA" and "ESS_CLUSTERHEAD_KEY IS <chosen_clusterhead>".  This approach may be reevaulated in later revisions.

NOTES: The current implementation does not quite implement the Publish.publish() command.  Future releases will perhaps address this.  However, the presence of Publish.publish() functionality is an "optimization" of sorts, whose effect can be achieved by including those common attributes as part of the Publish.sendData() command.   In addition, later versions will perhaps support a parameterized Publish interface.

This interface might change if and when we introduce support for the "blob" attribute type.  

The Filter Interface

interface Filter
{
  command result_t addFilter(Attribute *attrArray, uint8_t numAttrs);
  command result_t removeFilter();

  event result_t
receiveMatchingMsg(DiffMsgPtr msg);
  command result_t sendMessage(DiffMsgPtr msg, uint8_t priority);

  command uint8_t getMyPriority();
  // This command is to enable a filter to query the next sequence number
  // in order to build a packet... this is needed because a filter might
  // create new packets and needs to know what sequence number to give them
  // since it is responsible for the whole packet... (all other fields in
  // the packet don't need such explicit querying)...

  command uint16_t getNextSeqNum();
}


module OnePhasePullM {
  provides {
    .
    .
    interface Filter[uint8_t myPriority];
  }

    .
    .
}


The current implementation OnePhasePull provides a parameterized Filter interface.  This is to allow multiple Filter applications, since the parameterized interface inherently maintains a certain "state" for that interface wiring.  It is important to note that the parameterized interface instance is directly linked to the priority of that Filter instance.  The lower the number of the
Filter instance, the higher its priority.  So, the programmer has to make sure that the wiring of Filters takes care of the intended priorities, and that no more than one Filter application is wired to a single parameterized instance.

By means of Filter.addFilter() the application registers its interest in receiving messages matching the attributes passed therein.  The form of these attributes is the same as that of the Subscribe.subscribe() command.  Upon receiveing a new message -- either locally generated or received from a neighboring node -- it is checked against all existing filters.  Matching filters receive the Filter.receiveMatchingMsg() event (callback).  If the callback returns SUCCESS, the message is not forwarded to any other filter; it is now that filter's responsibility to send it to the next filter if it decides to.  The filter that has received a matching message has almost full control over what to do with it.  It must be noted that the receiveMatchingMsg expects the filter to copy out the message into its own buffers and not hold onto a pointer.  The DiffMsg and DiffMsgPtr types are used here instead of TOS_Msg and TOS_MsgPtr to allow a level of indirection that has proved to be very useful in the past.  In particular, we are using Ext_TOS_Msg instead of TOS_Msg due to the need to have an "saddr" field as part of the TOS_Msg (see Implementation Notes section for more information), this is all the more important.  For convenience and code reusability, we provide a whole set of get and set functions to allow access to the DiffMsg.  This is done in order to hide any offset changes that have or will come about.

A filter can send down a modified or new message by means of the sendMessage() command.  This command includes a "priority" field to allow the filter to tell the underlying Diffusion implementation to pass it to the first filter which priority greater than the passed priority.  For this, the application may need to know the priority it has been assigned (via wiring)... so a getMyPriority() command is provided for that reason.  Note that the sendMessage() command is expected to pass down a _complete_ message which is ready for further forwarding.  One of things that the application might need to know in order to complete the message is the sequence number to assign the packet.  For this reason, the getNextSeqNum() command is provided.  If the application sets the "saddr" field to NULL_NODE_ID, the underlying Diffusion implementation assumes that it is supposed to fill in the relevant fields before forwarding the message.  This is the most typical use, and the programmer is urged to use this convention to avoid needless side-effects and confusion.  Further, the application can ask Diffusion to pass the message to the next filter after itself;  in that case, the application uses the reserved priority of F_PRIORITY_SEND_TO_NEXT.

The DiffusionControl Interface


interface DiffusionControl {

  // add a list of nodes that comprise the gradient for a set of attributes
  // NOTE: this *replaces* the gradient list if already in place.
  command result_t addGradientOverride(Attribute *attrList, uint8_t numAttrs,
                                         uint16_t *gradients, uint8_t numGrads);

  // simply remove an override that's already in place
  // We are not allowing partial removal of gradient nodes comprising the
  // gradient override entry in order to keep the code simple... since this
  // is only a very short-term measure... where you would want to add an
  // override and later remove it... and no incremental additions removals
  // would be needed...
  command result_t removeGradientOverride(Attribute *attrList, uint8_t numAttrs);

  // placeholder for future controls...
}


module OnePhasePullM {
  provides {
    .
    .
    interface DiffusionControl;
  }

    .
    .
}

During our development, we wanted to leave the option open for having Diffusion gradients being overriden upon an administrator's request.  This functionality is provided by means of the DiffusionControl interface.   For now, this interface only contains commands to add and remove gradient overrides.  Later versions of this may have additional functionality.  

The addGradientOverride command allows the programmer to specify the gradient to be taken while forwarding a data packet that matches the attributes specified in the command.  The removeGradientOverride command allows the programmer to remove a previously added gradient override entry.  It must be kept in mind that gradient overrides kick in only when the data is being forwarded out of the current node; this means that gradient overrides are consulted after the data message is given to filters and before consulting the gradient information contained in the interest cache.

An Example Application

For an comprehensive example application, the reader is referred to the DiffTestNlist application (in tinydiff/apps/DiffTestNlist) directory.  This application is one that was used to incrementally test the working of Diffusion during development.  In this application, certain nodes are made "sinks" by means of explicit code.  The other nodes are by default "source" nodes.   Both sink and source nodes have filters that they use.  In addition, the gradient overrides can be enabled by an inquisitive programmer if he so desires.  In case of any questions, feel free to contact me  (mmysore AT cens.ucla.edu -- expanded to circumvent email address scanning web-bots).  

Internals of the OnePhasePull Implementation

Attributes and Matching Rules

As mentioned above, One Phase Pull is a communication scheme that uses attribute based naming of data.  More information about this can be found in [1].

In our implementation, an Attribute is a 4-byte three-tuple:

typedef struct {
  uint8_t  key;        // key
  uint8_t  op;         // operator as defined in ..
  uint16_t value;      // Value
} __attribute__ ((packed)) Attribute;

Initially, we had planned to incorporate blobs as well, but that proved to involve major changes over existing code that used arrays of Attributes.

Possible keys (key field) and operators (op field) are defined in tos/lib/OnePhasePull.h.  For convenience, below are the keys and operators (respectively) that are currently defined:

enum {
  CLASS     = 1,
  TEMP      = 2,
  PRESSURE  = 3,
  HUMIDITY  = 4,
  ESS_LOAD_KEY = 10,
  ESS_CLUSTERHEAD_KEY = 11,
  INTERVAL  = 50,          // or whatever...
  LAST        = 255        // last attribute indicator (not used)
};

enum {
  IS      = 1,
  EQ      = 2,
  NE      = 3,
  GT      = 4,
  GE      = 5,
  LT      = 6,
  LE      = 7,
  EQ_ANY  = 8
};

Matching Rules specify whether two sets of attributes are "compatible"; specifically, they are used to match "data" attributes against "interest" or constraint attributes.  Due to this specificity of their use in ESS, we use only a One Way Match, instead of a more general Two Way Match [1].

Packet Format


The following are the packet formats for the Interest and Data messages in our implementation of Diffusion.   As you can notice, the formats for these messages are very similar (except for the expiration field in the Interest message).  Both these have attribute arrays that are central to Diffusion.  

Certain changes to the following packet format are expected:  the use of the "saddr" field in the Ext_TOS_Msg header instead of the "prevHop" field, changes accompanying support for the "blob" attribute type at the moment.


// ============== Interest Message ==================

typedef struct {
  uint16_t seqNum;         // sequence number (32- bits for now...)
  uint16_t sink;           // source of packet
  uint16_t prevHop;        // last hop
  int8_t  ttl;           // time to live in terms of hops
  uint16_t expiration;       // expiration time of interest(or reinforcement)
  uint8_t  numAttrs;       // number of attributes contained in the packet
  Attribute  attributes[MAX_ATT];  // attributes tuples
} __attribute__((packed)) InterestMessage;

// ============= Data Message =======================

typedef struct {
  uint16_t seqNum;         // sequence number (32- bits for now...)
  uint16_t source;         // source of packet
  uint16_t prevHop;        // last hop
  int8_t hopsToSrc;       // number of hops packet has travelled from source
  uint8_t  numAttrs;       // number of attributes contained in the packet
  Attribute  attributes[MAX_ATT];  // attributes tuples

} __attribute__((packed)) DataMessage;

These packet formats are defined in tos/lib/OPPLib/DataStructures.h.

Internal Data Structures

This subsection serves as an overview of the data structures used in the current version.

Implementation Notes (Please read before using Diffusion as your communication protocol)

This subsection summarizes the implementation points that the programmer who plans to use our implementation of OnePhasePull should keep in mind.


Installation Instructions

Installation instructions are being maintained here.

Acknowledgments

The ideas behind OnePhasePull are due to John Heidemann, Fabio Silva and Ramesh Govindan [2].

The first-cut One Phase Pull Diffusion code was designed and written by Moshe Golan as part of his CS213 course project [4].  So, most of this design originates and is built over what Moshe did.  His older design documents and implementation notes can be found under the "doc/OnePhasePull" directory of the "tinydiff" contrib directory (http://cvs.cens.ucla.edu/viewcvs/viewcvs.cgi/tos-contrib/tinydiff/doc/OnePhasePull/outdated/).

The current code was designed and implemented by Mohan Mysore and Eric Osterweil under the supervision of Prof. Deborah Estrin.  We are thankful to several people for their valuable ideas: Fabio Silva, Jerry Zhao, Wei Ye, Alberto Cerpa, Jeremy Elson, Thanos Stathapoulos, Vlad Bychkovskiy, Deepak Ganesan, Naim Busek, Mohammad Rahimi, John Heidemann, and anyone else whose mention we unintentionally omitted.


References

[1] J. Heidemann, F. Silva, C. Intanagonwiwat, R. Govindan, D. Estrin, and D. Ganesan.  Building efficient wireless sensor networks with low-level naming.  In Proceedings of the Symposium on Operating Systems and Principles, pages 146-159, Banff, Alberta, Canada Oct. 2001. [PDF]

[2] F. Silva, J. Heidemann. One Phase Pull Pseudocode. [TXT]

[3] Manamohan Mysore, Eric Osterweil, Deborah Estrin.  Design of the Neighborlist Module.  CENS Design Document [HTML]

[4] Moshe Golan. TinyDiffusion Design. Design Document [PDF]



Updated on 05/29/03 by mmysore AT cens.ucla.edu