In Network Aggregation with Grouped Queries in multi-hop Wireless Sensor Networks
|
Sponsor |
Ling Liu / Bugra Gedik |
|
Area |
Systems and Databases |
Problem
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.
Deliverables
A report describing your devised algorithm or the stream data query language is
included and a discussion addressing the issues is described above.
Evaluation
You will be graded on the quality of your report.
References
[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