In Network Aggregation with Grouped Queries in multi-hop Wireless Sensor Networks


Ling Liu / Bugra Gedik
{lingliu, bgedik}
CCB 216 / CCB 260


Systems and Databases

This project is about supporting aggregate queries in wireless sensor networks. Aggregate queries are queries of type MAX, MIN, AVG and SUM. The wireless sensor network here refers to a set of sensor nodes forming a multi-hop wireless network. In a multi-hop wireless network, each node is able to communicate with a subset of other nodes which are inside its wireless radio's range. The sensor nodes have processors and memories to carry out computation and are able to communicate with a subset of other nodes. Sensors also have various sensing abilities to measure highly changing physical world properties (such as temperature, humidity, noise level, motion, light, etc.). An important characteristics of the sensor networks is that the sensors have limited battery power, and communication is expensive (in terms of power consumption) when compared to computation. Therefore, it is desirable to save power by doing more computation in order to have less communication.

The aim of this project is to support aggregate queries over a wireless sensor network. We assume that there are more than one outside nodes, called front ends, from which the queries are posted. These front ends could be connected to the wireless network through one or more sensor nodes (See Figure 1). The types of queries we are interested in are standing queries with aggregate functions. This means that the queries are not one time queries, the output of a query is basically a stream of values. We want to process these queries inside the network to reduce communication cost, namely no outside processing (on the front ends) should occur. Some standing query examples are as follows:
Give me the average of last 10 seconds temperature readings, every 2 seconds
Give me the maximum of last 1 minutes temperature readings, every 5 seconds

Give me the average of last 10 seconds temperature readings for which the noise level was greater than 10db, every 2 seconds

Figure 1


Students are expected to get familiar with the topic through reading references [1],[2],[3]. Then you can choose one of the following tasks to be one of your 7001 mini-projects.

(1)   Design a basic SQL like query language with the extension of windows (time series windows) in order to formalize the type of queries we have described above. The language should include stream data processing specific operators.

(2)   Design and develop an algorithm that supports the in-network processing of a standing query of the given type. The algorithm should use in-network aggregation to reduce the number of messages used. At this level the student can get ideas from [3]. The student is also expected to discuss whether the pipelined execution of queries (as described in [3]) is adequate for processing the type of queries we have described above. As an option, the student may improve the algorithm through supporting multiple queries and grouping of queries.

A report describing your devised algorithm or the stream data query language is included and a discussion addressing the issues is described above.

You will be graded on the quality of your report.

[1] Towards Sensor Database Systems
[2] Directed Diffusion: A Scalable and Robust Communication Paradigm for Sensor Networks
[3] Supporting Aggregate Queries Over Ad-Hoc Wireless Sensor Networks
more available on request