OVERVIEW

A key aspect that makes wireless ad-hoc sensor networks different from traditional networks is their strong link to the physical world. Wireless sensor networks are typically deployed for monitoring spatially continuous physical process statistics. However, we only have knowledge about a few samples of this process in terms of sensor node measurements. For a continuous physical process and a random deployment of sensor nodes, the conventional approach of doing nodal aggregation over these discrete sets of measurements produces inaccurate results when compared to the true aggregates that we call spatial aggregates.

APPROACHes

We propose a Voronoi-based approach, nearest neighbor interpolation to calculate spatial aggregates in wireless sensor networks. The area of the Voronoi cell is used as a parameter to reflect the “space” being monitored by a sensor node. We illustrate the distinction between nodal and spatial aggregation by specifically studying two aggregate functions – average and histogram. We present both a centralized and a completely localized-distributed version of our algorithm.

Closed form expressions for the energy consumption are derived for each mode and a detailed analysis is presented to determine energy efficient scenarios for each individual mode of the algorithm. We compare the performance of our algorithm with the conventional approach of nodal aggregation via extensive simulation on both fabricated as well as real precipitation data acquired over a span of past 50 years.

SYSTEMS / EXPERIMENTS

The algorithm gives a 2-4 times performance gain as compared to the conventional approach of doing nodal aggregation. Our first prototype implementation on Mica motes, termed as Voronoi Interpolated Spatial Aggregation (VISA), can be easily integrated with available frameworks for doing aggregation over a network of motes. Although not 100% accurate, our approach is a simple, efficient and a practical solution for calculating spatial aggregates in wireless sensor networks.

To demonstrate the feasibility of our algorithm, we implement it on Berkeley motes. Our algorithm is packaged in the form of an API, termed as VISA (Voronoi Interpolated Spatial Aggregation). VISA occupies less than 7.5K flash ROM and imposes no requirement on the run-time memory. VISA is architecturally compatible with the existing frameworks for doing aggregation in wireless sensor networks such as TinyDB, thus highlighting its portability.

ACCOMPLISHMENTS

VISA is available as a plug-in that provides a service for calculating the voronoi cell for every node. It is available in both nesc and C. The code is portable to Linux, TinyOS, and SOS. The efficacy of the implementation has been tested on both stargates and motes.

FUTURE DIRECTIONS

• Port VISA to Emstar environment.
• Incorporate localization into VISA and study the effect of error in localization.
• Breach detection is a challenging problem to solve in the context of sensor networks. If some area of the monitored area is left uncovered by the sensor nodes, it becomes a target of potential malicious activities by the intruders. We note that their exist literature that tries to focus on solving coverage and exposure problems in the context of sensor networks; albeit the focus has been on algorithmic development and most of the proposed implementations assume the presence of global knowledge at every node in the network. The crux of the problem is to develop a notion of the area monitored by the network. As we noted earlier, voronoi polygon efficiently provides this abstraction. Thereby, efficient breach detection algorithms can be developed coupled with the abstraction provided by VISA. The simplest of the algorithm simply checks if the sensing terrain of a node completely lies within its voronoi polygon. It can be shown that this simple condition, if satisfied by every node in the network, will make sure that no breaches exist in the network. As VISA is a completely localized and distributed algorithm, this simple algorithm for breach detection will also be localized and distributed.
  
  We are currently working towards developing more sophisticates solutions for breach detection. In general, we would like to answer the probabilities of false positives and false negatives, given that this condition is not satisfied for some nodes. This might provide the guidelines to the network designer to deploy some extra nodes or to provide the end-user with a quantitative analysis of the inherent fidelity in the network.

PEOPLE

FACULTY

Mani Srivastava

GRADUATE STUDENTS

Chih-Chieh Han
Saurabh Ganeriwal