Research Abstracts - 2006

WaveScope: A Wireless Sensor Computing System for High Data Rate Applications

Lewis Girod, Kyle Jamieson, Yuan Mei, Stan Rost, Arvind Thiagarajan, Timur Tokmouline, Hari Balakrishnan & Sam Madden

Collaborators: Kevin Amaratunga (Metis), Ivan Stoianov (Intel)

Project Overview

The WaveScope project is developing a software platform to make it easy to develop, deploy, and operate wireless sensor networks that exhibit high data rates. In contrast to the "first generation" of wireless sensor networks that are characterized by relatively low sensor sampling rates, there are several important emerging applications in which high rates of hundreds to tens of thousands of sensor samples per second are common. These include:

1. Civil and structural engineering applications, including continuous monitoring of physical structures, industrial equipment, and fluid pipelines. The goal is to reduce maintenance costs, improve diagnostics, and assist with trouble-shooting.
2. "Smart space" applications that continuously monitor sensors in a a space to support ubiquitous computing or security applications. For example, large-scale acoustic tracking of children in a crowded museum.
3. Scientific data gathering applications, such as outdoor acoustic monitoring systems for continuous habitat monitoring and the tracking of species or individual animals and phenomena.

Our target applications use many embedded vibration, seismic, pressure, magnetic, acoustic, and image sensors that sample at fine resolutions and high rates. For example, pressure transient monitoring of water transmission pipelines requires sampling rates of approximately 1-2 kHz [1,2], vibration monitoring of airplane wings and industrial equipment requires sampling at tens of kHz, etc.

These applications are generally continuously vigilant, processing the data streams in real time, and triggering more sophisticated processing or actuation when particular events are detected.

Questions and analyses applied in a WaveScope system might include:

1. Are vibrations in component A in the frequency band [x,y] larger than k millimeters? Particular resonant frequencies are often known to indicate specific problems.
2. Categorize the vibrations observed in component A based on stored signatures that match particular symptoms. Are there any symptom filters registering more than 3 standard deviations above a running average?
3. What is the phase relationship between the vibrations at locations A and B? Sudden changes in phase, used to track signal propagation, can indicate imminent equipment failure.

Answering these questions requires both signal processing and relational database operations over "real-time" data samples as well as data from the recent past. They also require efficient wireless data delivery protocols for large "blobs" of signal data.

WaveScope Objectives

Our research focuses on two novel directions:

1. A high-performance declarative programming system for joint data stream and signal processing.
2. Efficient wireless network protocols for delivering large application data units (the signal samples) and processing them "in-the-net".

WaveScope will enable users and developers to compose systems from modular building blocks that analyze the source data to produce information and to ask questions at different levels of abstraction. One of the implications is to allow deployment of monitoring applications without requiring the user to write code for an embedded platform. Our declarative programming system and optimized network protocols will free application writers from these gory details (which are hard to get right).

We are developing a high-level, declarative application description language that enables automated design-time optimizations through compilation to an intermediate representation. This language and optimization algorithms will enable developers to compose systems from high-level operators while ensuring good performance. Through compilation, WaveScope can perform computational optimizations including common subexpression elimination, factoring, and elimination of redundant operators. This language will also enables WaveScope to automate the process of distributing the processing components into a network of sensor devices. By pushing processing towards the data, it is possible to substantially reduce network overhead.

WaveScope's goal is to provide a clean and readily understood model of operation, to enable new users to get started quickly and run it out-of-the-box on the most common platforms. As a result, we aim to identify and include the most commonly used signal processing operations (such as the Fourier and Wavelet Transforms and Filtering) as a complete set of primitive operators. Where possible, we are working to integrate external packages and signal processing code (e.g., e.g. Matlab, Octave, Ptolemy, etc.) into WaveScope.

Initial Progress

Experience with Hydraulic Transients: Implementations in Matlab, Java Simulator, and the Borealis stream processing system

We have experimented with leak localization on a water transmission pipeline by analysis of hydraulic transients. Generated by a sudden change in water velocity, a hydraulic transient is a pressure wave that reflects from leaks. We have outlined a set of operators needed for analyzing hydraulic transients in pressure data.

We have also devised a distributed algorithm for in-network leak localization. The distributed approach combines locations of leak signatures from several sensors to create an improved estimate of the leak location. We also found that in some cases, selecting the sensors to be included in this estimation process increased the accuracy of the final leak location estimate.

Besides Matlab and Java-based simulations, we have also implemented leak detection using Borealis stream processing system. In this evaluation, we added two new operators to the original Borealis system: a wavelet transformation operator, and a range selection operator for peak extraction.

Our initial evaluation of Borealis suggested two limitations that make traditional stream processors (like Borealis) an inappropriate starting place for WaveScope:

1. They do not support cyclic query plan networks, and
2. They are not tuned to support the kinds of data rates (40+kHz) needed in Borealis); in particular, they have a high input and output overhead.

The initial experiences mentioned above, including Borealis and leak detection, and other signal-processing sensor systems like acoustic localization, bird chirp identification and audio-based tracking have led us towards our current goal of designing a high level data processing language: the Wavescope HDL. This language is designed for a system that supports high data rates (hundreds of kHz), includes a library of signal processing operators, and will permit more interesting constructs for data flow including cycles, delays, and other logic not available in existing stream processors like Borealis.

We have designed new protocols for disseminating and processing large application data units, corresponding to thousands of samples collected at high rates. The main challenge is dealing with variable wireless channel conditions and packet losses. To perform efficient "in-the-net" processing, nodes create state. Unfortunately, packet losses and topology changes make it hard to keep this state consistent. We are developing algorithms to address these problems.

The main difference between our protocols and previous work is that most previoous work has dealt with small chunks of application data, while our domain mandates large data chunks that are considerably larger than the size of a network packet.

Related Work

Ptolemy II

Ptolemy II [4,5] is a Java-based framework for dataflow software and modeling that has been under development at UC Berkeley in various forms since 1987. Using Ptolemy, dataflow systems are implemented through a combination of reusable Java components and an XML-based high level description language that defines how the components are linked together. Ptolemy supports a wide variety of different dataflow models, called "Domains", including finite state machines, synchronous signal processing, circuit emulation, and hybrids that combine elements of different domains. This framework has been used to support various forms of optimization [6] as well as automated synthesis of embedded signal processing systems [7].

Relative to Ptolemy, WaveScope's framework targets the embedded sensor network more directly, and focus on providing a framework for implementing systems, whereas Ptolemy is more commonly used as a modeling or instructional tool. WaveScope directly addresses the problem of distributing a workflow into a network, distributing some computation to the sensors while centralizing other computation at the server. WaveScope also places greater emphasis on enabling automatic optimization of computational, buffering and network resources. Finally, many WaveScope applications involve forms of conditional processing that are not conveniently implemented using the existing Ptolemy domains.

Borealis

Borealis [8] is an event-driven stream processing engine designed to support streams of data from sensor networks, following on from work on the previous systems Aurora and Medusa. Borealis is configured using a high-level description language based on XML that links together modules implemented in C++. It supports distribution of processing throughout the network by an RPC-like mechanism that enables local-remote transparency for connections between modules. Relative to other stream processing engines, Borealis provides better support for dynamics: query results can be revised dynamically in the event that corrections are made to the input stream, and the queries themselves can be dynamically selected based on detected events. We have used Borealis to build some initial WaveScope prototypes, although it is still not clear whether it will be a good fit in the long run.

Telegraph CQ

TelegraphCQ [33] is one of the first engines to process data continuously as it arrives instead of storing it first. In TelegraphCQ, users express queries in SQL, except that each query has an extra clause defining the input windows over which the results should be computed. The main emphasis of TelegraphCQ is on adaptive processing, in which tuples can be routed to different modules based on changing conditions. This adaptivity enables better performance in the face of variable conditions during query execution, but introduces greater overhead.

Stanford Stream

The STREAM [9] project explores several aspects of stream processing: a new data model and query language for streams, resource management, and some distributed operation. STREAM processes data as it arrives, converting the stream to a relation that changes over time. These relations are processed and converted back to an output stream. This arrangement allows STREAM applications to be composed of a mix of operations on streams and relations.

Relative to both STREAM and TelegraphCQ, WaveScope proposes more sophisticated network capabilities, especially the ability to push signal processing components close to the sensor to limit network overhead. WaveScope also proposes a more sophisticated buffer management scheme that enables the system to store data that may be needed later as a result of conditional processing.

LabView and Matlab

LabView is a commercial product that is similar in functionality to Ptolemy, but is noted for its extensive compatibility with industrial equipment. Matlab serves as a source of inspiration for WaveScope development, because of its wide acceptance and high degree of expressiveness.

WaveScope intends to provide users with an interface that supports tinkering and exploration of data streams with similar ease to Matlab and LabView.

References:

[1] Stoianov, I., Dellow, D., Maksimovic, C. and Graham, N.J.D. Field Validation of the Application of Hydraulic Transients for Leak Detection in Transmission Pipelines. In The Proceedings of CCWI 2003 Advances in Water Supply Management Conference, London, UK, September 2003.

[2] Stoianov, I., Maksimovic, C. and Graham, N.J.D. Designing a Continuous Monitoring System for Transmission Pipelines, In The Proceedings CCWI 2003 Advances in Water Supply Management Conference, London, UK, September 2003.

[3] http://db.csail.mit.edu/dcnui

[4] Buck, J.T., Ha, S., Lee, E.A., and Messerschmitt, D.G., Ptolemy: A Framework for Simulating and Prototyping Heterogeneous Systems. In Int. Journal of Computer Simulation, special issue on Simulation Software Development, vol. 4, pp. 155-182, April, 1994.

[5] http://ptolemy.berkeley.edu/ptolemyII/main.htm

[6] Ha, S. and Lee, E.A., Compile-Time Scheduling of Dynamic Constructs in Dataflow Program Graphs. In IEEE Trans. on Computers, Vol. 46, No. 7, July 1997.

[7] Bhattacharyya, S.S., Murthy, P.K., and Lee, E.A., Synthesis of Embedded Software from Synchronous Dataflow Specifications. In Journal of VLSI Signal Processing Systems, Vol. 21, No. 2, June 1999.

[8] Abadi, D.J., Ahmad, Y., Balazinska, M., Centintemel, U., Cherniack, M., Hwang, J-H., Lindner, W., Maskey, A.S., Rasin, A., Ryvkina, E., Tatbul, N., Xing, Y., and Zdonik, S., The Design of the Borealis Stream Processing Engine CIDR 2005 - Second Biennial Conference on Innovative Data Systems Research, Asilomar, California, January 2005.

[9] Arasu, A., Babcock, B., Babu, S., Cieslewicz, J., Datar, M., Ito, K., Motwani, R., Srivastava, U., and Widom, J.. STREAM: The stanford data stream management system. To appear in a book on data stream management edited by Garofalakis, Gehrke, and Rastogi.

[10] Chandrasekaran, S., Cooper, O., Deshpande, A., Franklin, M.J., Hellerstein, J.M., Hong, W., Krishnamurthy, S., Madden, S., Raman, V., Reiss, F., and Shah, M. TelegraphCQ: Continuous dataflow processing for an uncertain world. In Proc. of the First Biennial Conference on Innovative Data Systems Research (CIDR), January 2003.

Acknowledgments

This work is funded by the National Science Foundation under Award Number CNS-0520032.