TinyDiffusion in the Extensible Sensing System at the
James Reserve
Manamohan Mysore
Moshe Golan
Eric Osterweil
Deborah Estrin
Mohammad Rahimi
Table of Contents
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.
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].
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.
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].
In the diagram above, the following are the roles played by the various
modules:
- OnePhasePulM: the module that implements the One Phase Pull variant
of Diffusion
- NeighborBeacon: the module that implements neighborlist heart-beat
exchanges with neighbors and computation of loss rate as seen from missing
heart-beats. The calculation of loss involves EWMA smoothing to lessen
the effect of transcients.
- NeighborStoreM: this is a module that stores information, such as
loss rate and other statistics, link goodness indicator, etc. about each neighbor
- NeighborFilterM: this module is responsible for filtering out neighbors
based on their link goodness. It can be configured with loss thresholds
that comprise the low-water and high-water to implement hysterisis in deciding
the goodness/badness of links. This module is essential because OnePhasePull
uses symmetric links to get data back to the sink.
- TxManC: this module implements a queue for all outgoing packets.
This is necessitated by the asynchronous send() semantics of TinyOS
and also to introduce randomness in the time at which the packet leaves,
so that collisions are avoided.
- ExtGenericComm: more information about this module can be found in
the implementation notes section below.
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.
- The Interest Cache: The function of the Interest Cache
is to (1) eliminate duplicates during Interest flooding, (2) handle ageing
and expiration of interests, and (3) enable matching of arriving data with
existing Interests to forward it either to an application on the current
node or onto another node in the network.
This data structure is an array of "InterestCache" entries that contain
all information pertaining to an interest that was received on or sent from
this node. The definition of the InterestCache data structure can
be found in tos/lib/OPPLib/InterestCache.h. There are a bunch of Interest
Cache manipulation functions such as updateInterestCache that can be found
in tos/lib/OPPLib/InterestCache.c. In the current implementation,
for certain reasons, each arriving interest is given a separate InterestCache
entry and does not replace an older entry from the same sink. If the
total number of arriving interests exceeds the InterestCache size (defined
to be 10 for now), the oldest InterestCache entry is replaced.
- The Data Cache: The responsibility of the data cache in One
Phase Pull is to eliminate duplicates during data forwarding. In One
Phase Pull, a node that sees data packet with sequence number "n" cannot
expect to get packet with sequence number "n + 1" as well, since data packets
travel along gradients determined by the Interests the data matches, and it
might have taken a different route to perhaps a different sink. On the
same token, having received sequence number "m" on a certain path does not
guarantee that sequence "m - 1" will not arrive via a longer, higher delay
path. So, this shows that the simple "monotonically increasing" sequence
number scheme to filter out duplicates can not be used. This is why
the Data Cache in our implementation of One Phase Pull uses a simple circular
buffer of data cache entries which consist very simply of source and sequence
number. If an arriving data item is found in the data cache, it is
a duplicate, otherwise, it is most likely a new entry (there is a chance
that it was a old entry that has been rotated out of the data cache, but
that would be unlikely if the cache is big enough). The effectiveness
of this approach depends upon the number of data cache entries -- greater
the number of entries, better the correctness of duplicate filtering. For
now, the data cache has 25 entries.
The definition of the data structures pertaining to the Data Cache can
be found in tos/lib/OPPLib/DataCache.h and functions to use the data cache
can be found in tos/lib/OPPLib/DataCache.c
- The Filter Table: The Filter Table is a data structure that
is used to maintain the attributes registered by existing Filters. The
way this table is organized, the "i"th parameterized instance of the Filter
interface provided by OnePhasePullM corresponds to the "i"th entry of the
table. At this point there can be at most 5 filters (this has been
kept small to lessen the amount of unused memory, but can be increased if
needed). When a message -- data or interest, irrespective -- is received,
Diffusion goes through the filters in the order of priority (first to
last in the Filter Table) and gives the packet to the first matching filter.
We had talked about these in greater detail while mentioning the "Filter"
interface provided by OnePhasePull.
This data structure can be found in tos/lib/OnePhasePullM.nc.
- The Gradient Override Table: This is a table that specifies
how the matching data should be routed, even overriding the core One Phase
Pull Diffusion mechanism. We had referred to this while talking about
the "DiffusionControl" interface. If a Data packet matches any of the
Gradient Override entries, the gradient contained in the first matching entry
is applied to that packet. There might be multiple entries that a
data packet matches, but their priority is inherent in the order in which
these Gradient Override entries have been added and therefore in their order
in the table.
The GradientOverrideEntry data structure can be found in tos/lib/OnePhasePullM.nc
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.
- The Ext_TOS_Msg format and ExtGenericComm module:
We use our own extended version of TOS_Msg called Ext_TOS_Msg (defined in
tos/system/Ext_AM.h) that is compatible with TOS_Msg but adds an extra 2-byte
field called "saddr" at offset 0 of the data portion in the original TOS_Msg.
Note that the data length of the message as considered by an application
using the Ext_TOS_Msg will be 2 bytes less than if it had used the original
TOS_Msg format. To compensate for this difference, we use an module
called ExtGenericComm instead of GenericComm. This module serves as
a "translation" layer to GenericComm and handles the aforementioned length
translation. It increments the length by 2 for messages going down
the communication stack and decrements the length by 2 for messages coming
up the stack.
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
