Overview

This project revisits the architectural foundations of the sensor network systems built and deployed by CENS.

Sensor network researchers originally envisioned large networks of tiny wireless nodes with simple gateways to the Internet. Because of energy and network constraints, the tiny nodes themselves would collaboratively process data in-network in complex, application-specific ways.

In reality, though, the sensor networks we deploy mostly perform continuous data acquisition, and incorporate little or no on-mote multi-node data fusion. We believe that two factors can explain this development. First, the introduction of masters: 32-bit CPU-class nodes for which power can be engineered. Masters are an integral part of every network we deploy, and rather than acting as mere Internet gateways, they participate in the functionality of the network. (Yet our current architectural principles take little advantage of them!) Second, the unexpectedly high complexity of mote-based multi-node data fusion makes implementing such functionality a bad tradeoff. By not optimizing for the system as a whole, we are missing the opportunity/have overlooked to build a software architecture that promotes on-board mote processing of its local time series in an adaptive and efficient manner.

Tiered data-collection networks are therefore here to stay. Unfortunately, only the original architectural principles are available to sensor network designers. When designers follow those principles – or even pay them lip service by, for example, assuming that someone might implement multi-node data fusion later – the resulting systems are fragile and overly complex. Even worse, they are difficult to repurpose; and the master nodes on which network health depends remain underutilized.

An architecture is needed to guide the construction of scalable, evolvable, and replicable sensor systems that will serve the vast array of applications currently awaiting deployment. The Tenet project is developing such an architecture.

Approach

Many current large-scale sensor network deployments are tiered. The lower-tier, composed of motes, contains sensing and actuation functionality and enables infrastructure-less instrumentation of physical spaces and artifacts. The upper-tier, consisting of 32-bit nodes, masters, is free of energy constraints and provides increased network and computational capacity, enabling large-scale deployments.

The Tenet architecture prescribes a functional separation between motes and masters, with the goal of reducing overall system complexity. The architecture asserts that it is still desirable for the motes, which should be optimized for low power operation, to do local aggregation, compression, and even filtering of its time series data. However, cross node aggregation, filtering, and processing is best done by the master. This functional separation is captured in the following architectural principle:

The Tenet. Multi-node data fusion functionality and complex application logic should be implemented only in a tier of relatively high-powered Stargate-class nodes, which we call masters. The cost and complexity of implementing this functionality in motes outweighs the performance benefits of doing so.

Figure 1: A Tiered Embedded Network

Fundamentally, then, Tenet constrains collaborative multi-node in-network processing to be performed on the master nodes. In-network aggregation and fusion is inherently somewhat centralized in that data from multiple nodes is sent to a common node to be processed. The masters in a tiered architecture are natural fusion and aggregation points from the perspective of capacity (CPU, storage, bandwidth and energy). Constraining aggregation to be performed at masters results in a simpler architecture relative to one that allows aggregation on topologically convenient, but resource-constrained motes. In Tenet, motes are tasked by applications running on masters, and can implement simple logical elements such as thresholds and compression, but any further computation takes place only on masters. Finally, masters can collaborate with one another to implement distributed applications for tracking, detecting spatio-temporal events, or (as in this proposal) multi-robot coordination (Figure 1).

The Tenet project is currently designing an instance of Tenet, based on the following design principles:

• Addressability. Any master in a Tenet can communicate with any mote or master in that Tenet, as long as there is (possibly multi-hop) physical-layer connectivity between them. Furthermore, any mote in a Tenet can communicate with at least one master in that Tenet, unless no master is reachable.
• Asymmetric Task Communication . Any and all communication from a master to a mote takes the form of a task. Any and all communication from a mote is a response to a task; motes cannot initiate tasks themselves. Together with addressability, this principle ensures a clear functional separation between motes and masters and enables a generic mote layer.
• Task Library. Motes provide a limited library of generic functionality, such as timers, sensors, simple thresholds, data compression, and data transformation. Each task activates a simple subset of this functionality. In addition, tasks may also command actuators such as robots, cameras and structural exciters, and invoke node management functions like setting device parameters or returning node statistics.
• Robustness and Manageability. Finally, a Tenet prototype must be robust to node and link failure, and must provide users with insight into network problems as well as allow automated response to those problems.

Systems/Experiments

The current Tenet prototype consists of the following five components (Figures 2 and 3): At the core of the Tenet framework is the tasking library. A task is described using a linear dataflow tasking language that allows applications to flexibly specify the sensor acquisition and local processing tasks. Motes provide a limited library of generic functionality, such as timers, sensors, simple thresholds, data compression, and transformations. The tasks activate a simple subset of this functionality. On a mote, the task library interprets incoming tasks and schedules the tasklets for execution in the order specified in the task description. The task engine can manage and execute multiple tasks on a single mote. The task engine also manages events and interrupts and delivers them to the tasklets. On the masters, Tenet provides utilities to compose such tasks and interpret the results.

The routing subsystem uses a multi-sink version of a standard tree routing protocol for routing data from motes to masters. IP routing provides reachability on the master tier. Traffic from the masters to the motes follows the reverse path; reverse path routing entries all are dynamically established when the motes send data to the masters. In addition, we have implemented a centralized mote routing protocol. The goal of this new protocol, called Centroute has been to provide a lightweight (in terms of RAM) and robust alternative to existing mote routing protocols such as MintRoute. Centroute uses source routing to achieve both forward and reverse-path unicast routing, as well as avoid routing loops. By being an on-demand protocol, its control overhead is limited compared to the control overhead of proactive protocols.

Figure 4: Per-mote byte overhead as a function of mote Neighbor density for CentRoute, MintRoute and Multihop

Table 1: Average loop occurrence probability as a function of density for CentRoute, MintRoute and Multihop

The task dissemination subsystem ensures the reliable delivery of tasks from any master to all the motes. In the current prototype, this functionality is achieved by a protocol called TRD (Tiered Reliable Dissemination). TRD performs reliable flooding over both tiers of the tiered network. Message losses are recovered locally; when a node hears that a neighbor has received messages with higher sequence numbers from a source then what it has, it requests the missing messages directly from the neighbor. In this manner, tasks are disseminated to all nodes in the network. In general, not all of them may execute a given task. The current Tenet design assumes that task dissemination is relatively infrequent, and that in the common case all nodes execute a task.

The transport subsystem provides end-to-end reliable transmission of sensor data from motes to masters. Tenet supports two kinds of reliable point-to-point delivery: a transactional transport protocol which delivers a single message in a reliable fashion, and a stream transport protocol whose semantics are similar to that of TCP. Depending on the kind of data that tasks expect to generate, a task may use either of these transport protocols.

The time synchronization component ensures that all the motes maintain a globally synchronized time. Tenet uses this global time to schedule executing of tasks at a specified time. This capability, for instance, enables Tenet to start a task on all the motes at the same time. The current Tenet prototype uses the FTSP (Flooding Time Synchronization Protocol) as its time synchronization protocol and exports time interface to the tasking library.

Accomplishments

Software:

We have released the first version of Tenet. This version includes an early prototype of the task engine, a task library with a variety of sensing, computational, and user interface components, reliable delivery and dissemination protocols, and routing on the master and mote tier. The instruction to download and use the software can be found at http://enl.usc.edu/software.html.

Proof-of-concept application:

As a proof-of-concept Tenet application, we have implemented pursuit-evasion on Tenet (Tenet-PEG). Tenet-PEG currently supports a single pursuer and a single evader in an indoor environment. In Tenet-PEG, an evader carries a mote which periodically emits a radio beacon. This beacon serves as a surrogate for a more sophisticated sensor, such as a magnetometer or a PIR sensor. Tenet-PEG consists of a single coordinator program that runs on a master node. It uses Tenet to task all the nodes in the network to report whenever radio beacons from an evader exceed a certain signal strength threshold, and uses these sensor readings to localize the evader to one of the nodes on the map. The coordinator adaptively adjusts the signal strength threshold, based on the number of reports it receives; this mechanism improves network efficiency and prevents local traffic congestion when several nodes attempt to send their readings to the coordinator. Thus, the coordinator effectively performs the kind of data fusion that might be performed on a mote in a flat-network implementation of pursuit-evasion. The Tenet architecture simplifies the programming of such applications. Applications do not need to implement low-level wireless networking components; by contrast, pursuit-evasion on a flat network of motes needs to implement specialized networking mechanisms like landmark routing and leader election.

Framework for high-rate data acquisition:

The VanGo software framework provides data processing algorithms and systems mechanisms to adapt sensor network applications to runtime dynamics. Its operation follows the Tenet architecture. Important applications (in acoustics, imaging, neural impulses, etc.) require that we detect events based on sensing modalities with high-bandwidth signals. Yet, the small wireless sensors required for distribution, wearing, and attachment do not have enough bandwidth to transmit complete waveform data: The data must be reduced. Performing that filtering well requires adaptation to environmental conditions. It relies on the participation of a master device that has the necessary computation capabilities and scope of observation. Since classification and filtering in these domains is much more complex, efficient operation of sophisticated processing is all the more important. VanGo by design acquires high-rate sensor data and improves in-network data processing iteratively. Within this framework, applications have been developed that can adjust to changing environments and user needs, in spite of sensing devices’ stringent constraints: a flexible acoustic collection application for motes and the first neural spike acquisition application capable of supporting a network of more than two nodes.

Future Directions

We are interested in exploring the application space enabled by Tenet to both understand its limitation and to demonstrate its strengths. The design and implementation of each component in the architecture will evolve to make Tenet more robust, manageable, and easy to use. We plan to deploy long running large scale sensor networks using the Tenet software.

People

Faculty: Ramesh Govindan (USC), Eddie Kohler (UCLA), Deborah Estrin (UCLA)

Graduate students: Fang Bian (USC), Omprakash Gnawali (USC), Ben Greenstein (UCLA), Ki-Young Jang (USC), August Joki (UCLA), Jeongyeup Paek (USC), Sumit Rangwala (USC), Thanos Stathopoulos (UCLA), Marcos Vieira (USC)