Building Efficient Wireless Sensor Networks with LowLevel Naming - 4

4. IMPLEMENTATIONS

There are currently three implementations of all or part of this

architecture. Our current reference implementation SCADDS diffusion

version 3 provides all components. MIT-Lincoln Labs has

implemented “declarative routing” that provides attribute matching

but no filters [14]. Both of these implementations run on Linux

on desktop PCs and PC/104-based sensor nodes [11] (embedded

x86 machines, ours with a 66MHz CPU and 16MB of RAM and

flash disk, Figure 3(a)), and on WINSng 1.0 sensor nodes [29]

(Windows-CE-based nodes with custom low-power radios, Figure

3(b)). We have also implemented micro-diffusion, a bare subset

of these services designed to run on Motes with tiny 8-bit processors

and only 8KB of memory (Figure 3(c)).

Source code to our implementations can be found on our web

site http://www.isi.edu/scadds.

All of our implementations build upon a simple radio API that

supports broadcast or unicast to immediate neighbors. Neighbors

must have some kind of identifier, but it is not required to be

persistent. We can use persistent identifiers (for example, Ethernet

MAC addresses) or operate with ephermally assigned identifiers

[16].

4.1 Basic diffusion APIs

Our reference implementation includes C++ Network Routing

APIs summarized in Figure 4 (see [13] for a complete specification

and example source code). The APIs define a publish/subscribe

approach to data handling. To receive data, nodes subscribe to particular

set of attributes. A subscription results in interests being

sent through the network and sets up gradients. A callback function

is then invoked whenever relevant data arrives at the node.

Applications that generate information publish that fact, and

then send specific data. The attributes specified in the publish call

must match the subscription. If there are no active subscriptions,

published data does not leave the node. As a further optimization

sensor nodes may wish to avoid generating data that has no takers.

In this case the application would subscribe for subscriptions and

would be informed when subscriptions arrive or terminate.

Filter-specific APIs are shown in Figure 5. A filter is primarily

a callback procedure (the cb specified in addFilter) that is called

when matching data arrives. Rather than operate only on attribute

vectors, filters are given direct access to messages that include

identifiers for the previous and next immediate destinations. We

(a) Our PC/104 node (b) WINSng 1.0 node (c) UCB Rene Mote

Figure 3: Diffusion operational platforms.

handle NR::subscribe(NRAttrVec *subscribeAttrs,

const NR::Callback * cb);

int NR::unsubscribe(handle subscription_handle);

handle NR::publish(NRAttrVec *publishAttrs);

int NR::unpublish(handle publication_handle);

int NR::send(handle publication_handle,

NRAttrVec *sendAttrs);

Figure 4: Basic diffusion API.

handle addFilter(NRAttrVec *filterAttrs,

int16_t priority, FilterCallback *cb);

int NR::removeFilter(handle filter_handle);

void sendMessage(Message *msg, handle h,

int16_t agent_id = 0);

void sendMessageToNext(Message *msg, handle h);

Figure 5: Filter APIs.

are currently evaluating using this additional level of control to

optimize diffusion, for example using geographic information to

avoid flooding exploratory interests. We expect these interfaces to

be extended as we gain more experience with how filters are used

and what information they require.

Finally, these APIs have been designed to favor an event-driven

programming style, although they have been successfully used in

multi-threaded environments such as WINSng 1.0. We have targeted

event-driven programming to avoid synchronization errors

and to avoid the memory and performance overheads of multithreading.

Evidence is growing that event-driven software is well

suited to embedded programming, particularly on very memoryconstrained

platforms [21].

Also we allow filters and applications to run in the same or different

memory address spaces from each other and the diffusion

core. Single-address space operation is necessary for very small

sensor nodes that lack memory protection and as a performance

optimization. Multiple address spaces may be desired for robustness

to isolate filters of different applications from each other.

4.2 MITLL

declarative routing

Dan Coffin helped define the basic diffusion APIs (Figure 4

and [13]) and developed an independent implementation in MITLincoln

Lab’s Declarative Routing system [14]. In principle all

applications that do not depend on filters will run over either implementation.

This level of portability has been demonstrated with

Cornell’s query proxy [5] that runs over both implementations.1

Declarative routing and data diffusion are far more similar than

they are different. Both name data rather than end-nodes. Differences

are in how routes and transmission are optimized, both by

applications and the core system. The primary difference is that

declarative routing does not include filters to allow applications

to directly influence diffusion. We see filters as a critical necessary

component to enable general in-network data processing.

Second, Lincoln Lab’s declarative routing includes direct support

for energy and geography-aided routing so that routes are selected

to avoid energy-poor nodes and generally move “towards” a target

geographic area. In our current implementation interests and

exploratory messages are flooded through the network before gradients

are set up for direct communication. We are currently exploring

using filters to optimize diffusion (avoiding flooding) with

geographic information [39].

4.3 Microdiffusion

Micro-diffusion is a subset of our approach implemented on

very small processors (8-bit CPU, 8KB memory). It is distinguished

by its extremely small memory footprint and a complementary

approach for deployment to our full system.

Micro-diffusion is a subset of our full system, retaining only

gradients, condensing attributes to a single tag, and supporting

only limited filters. As a result it adds only 2050 bytes of code and

106 bytes of data to its host operating system. (By comparison,

our full system requires a daemon with static sizes of 55KB code,

8KB data, and a library at 20KB code, 4KB data.) Micro-diffusion

is implemented as a component in TinyOS [21] that adds 3250B

code and 144B of data (including support for radio and a photo

sensor), so the entire system runs in less than 5.5KB of memory.

Micro-diffusion is statically configured to support 5 active gradients

and a cache of 10 packets of the 2 relevant bytes per packet.

No changes were required to our diffusion implementation, although

the port required one change to the application to accommodate

a case where MIT’s implementation was less strict about

attribute matching.

Although



reduced in size, the logical header format is compatible

with that of the full diffusion implementation and we are implementing

software to gateway between the implementations. Although

we do not currently provide filters in micro-diffusion, they

are an essential component of enabling in-network aggregation in

diffusion, and we plan to add them. We intend to leverage on the

ability to reprogram motes over the air [21] to program filters dynamically.

Motes and micro-diffusion can be used in regions where there is

need for dense sensor distribution, such as distributing photo sensors

in a room to detect change in light or temperature sensors for

fine grained sensing. They provide the necessary sensor data processing

capability, with the ability to use diffusion to communicate

with less resource-constrained nodes (for example, PC/104-class

nodes). Motes can also be used to provide additional multi-hop

capability under adverse wireless communication conditions.

We thus envisage deployment of a tiered architecture with both

larger and smaller nodes. Less resource-constrained nodes will

form the highest tier and act as gateways to the second tier. The

second tier will be composed of motes connected to low-power

sensors running micro-diffusion. Most of the network “intelligence”

is programmed into the first tier. Second-tier nodes will

be controlled and their filters programmed from these more capable

nodes.

4.4 Implementation discussion

We draw two observations from our experiences with these implementations.

First, the range of diffusion implementations suggests

that both the ideas and the code are portable since there

are three independent implementations (our main implementation,

micro-diffusion, and MIT-LL’s declarative routing) and our primary

implementation runs on multiple platforms (PC/104s and

WINSng 1.0 as of June 2001, with ports in progress to two new

radios and platforms). The requirements for diffusion are quite

modest in terms of CPU speed (a 15MHz 32-bit processor is sufficient),

memory (a few megabytes supports diffusion, an OS, and

applications), and radio (10–20kb/s bandwidth is sufficient). Several

low-power radio designs have packet sizes as small as 30B.

We require moderate size packets (100B or more) and use code

for fragmentation and reassembly when necessary. Second, microdiffusion

demonstrates that it is possible to implement a subset of

diffusion on an embedded processor. A common preconception

is that fully custom protocols are needed for embedded systems;

these observations suggest that use of diffusion should not be precluded

due to size or complexity.