Lead Investigators:

Ramesh Govindan, Eddie Kohler, Deborah Estrin

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.

Figure 1: A Tiered Sensor Network

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.
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

Figure 2: Stack on a mote node

Figure 3: Stack on a master node

The current Tenet system 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.
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.
We implemented a simplified version of Pursuit Evasion Game (PEG) in Tenet (Tenet-PEG) as an application case study to demonstrate that an application as complex as target tracking can be built using Tenet. PEG consists of a few mobile robots (pursuers) collectively determine the location of one or more evaders. We also implemented PEG using a mote-only architecture (Mote-PEG) that used in-network data fusion to localize an evader to compare its performance with Tenet-PEG. PEG represents a stress test for Tenet because in-network data fusion in Mote-PEG seems more efficient than collecting sensor readings in a master to determine the location of the evader. Our experimental setup consisted of 56 Tmotes sensing the position of a mobile evader (a Pioneer robot) and 6 Stargates as masters (Figures 4 and 5).

Figure 4: A Pioneer robot that can linux and Tenet master stack.

Figure 5: Map of a floor in which PEG experiment was done. Red dots are topological markers.

Our experimental results show that a Tenet-PEG can estimate the position of the evader with accuracy, message cost, and evader detection latency compared to Mote-PEG. (Figures 6, 7, 8).

Figure 6: Accuracy of Evader localization

Figure 7: Message overhead for Evader detection

Figure 8: Cumulative distribution of evader detection latency

 

In addition to the systems described above, we also explored other routing and transport related issues that arise in a tiered sensor network. We have designed and studied 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.

Tenet could easily become congested when a large number of nodes, for example, respond to a task with their sensor readings. Thus, rate control for congestion mitigation and avoidance is important in Tenet. Our approach is to leverage the computation resource of masters and use a relatively simple, lightweight rate allocation heuristic that uses topology and loss rate information, and adapts at relatively long time-scales to channel variability. This rate allocation heuristic is essentially a coarse-grain centralized scheduling for TDMA. Our result suggests that a near-optimal centralized rate allocation is feasible for wireless sensor networks in the absence of rapid topology changes in the network.

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.

Deployment:
We deployed a Tenet system of 20 motes and 5 masters running a data acquisition application on a 570 ft span of a 6,000 ft long suspension bridge (Figure 9). The goal of the application is to record the vibrations seen on the bridge for 24 hours. Tenet's architecture is a good match for an application like this: the small form factor and low cost of the motes allow them to be flexibly deployed in large numbers while the computation, energy, and storage resources on the masters can be used for orchestrating the data collection tasks, monitoring the network, and storing a large amount of data for extended period of time.

Figure 9: Tenet deployment topology on a suspension bridge.

Future Directions

We plan to deploy long running large scale sensor networks using the Tenet software. 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 briefly describe ongoing research efforts in routing, rate controlled and fair transport, scheduling for throughput maximization, and sleep scheduling.

We plan to enable Tenet to use Centroute as an alternative routing protocol. Towards this end, we have already taken some initial steps towards de-coupling the Centroute implementation from Emstar to enable easier integration into the Tenet code base. This activity is an important first step towards a long-term goal of implementing the Extensible Sensing System in Tenet.

We plan to investigate the feasibility of a transport protocol that uses centralized rate allocation with end-to-end explicit loss recovery. In Tenet, data sinks reside at the resourceful masters and all data streams end at the masters. Centralized control at the sink can recover lost packets and perform rate control by informing the motes the rates at which they should send data so that fair and reliable delivery of data packets is provided and the best achievable rate can be known to the user at the sink.

When Tenet is used in an application such as vibration monitoring on a bridge, the motes generate a large amount of data which must be sent to a masters along a multi-hop mote network. This scenario can give rise to increased contention of the wireless channel which results in degraded performance. We plan to design a system that maximizes the network throughput. Our approach is based on Time-Division Multiplexing (TDM) in which we compute the transmission schedule for the nodes based on the topology. Given the routing tree and the neighbors list of every node, and the amount of data to collect from each node, we model the problem as a vertex coloring problem - each color corresponds to the transmission schedule of a node.

We plan to enable Tenet to run with radio duty-cycling. The mote tier in Tenet consists of nodes with limited energy resources. Radio hardware consumes a large portion of the energy on the motes. Turning a radio off when a node does not need to transmit or receive messages is critical to saving energy and enabling long term Tenet deployments. Our approach is to analyze the tasks to determine the amount of data that the task would generate and use that information in a distributed sleep schedule slot assignment algorithm to compute the transmission and reception schedule for each node. Such schedules can adapt to task injection and termination thereby offering consistent performance across a wide range of workload in a duty cycled network.

People

Faculty:

• Ramesh Govindan (USC)
• Eddie Kohler (UCLA)
• Deborah Estrin (UCLA)

Staff:

• Karen Chandler (UCLA)

Graduate Students:

• Fang Bian (USC)
• Omprakash Gnawali (USC)
• Ben Greenstein (UCLA)
• Ki-Young Jang (USC)
• August Joki (UCLA)
• Jeongyeup Paek (USC)
• Thanos Stathopoulos (UCLA)
• Marcos Vieira (USC)