Complex query optimization in wireless sensor networks
Date
2012
Authors
Chen, Baichen
Journal Title
Journal ISSN
Volume Title
Publisher
Abstract
Recent advances in wireless communication and electronics have enabled large-scale wireless sensor networks (WSNs) to be deployed for a variety of applications in environmental monitoring, intrusion surveillances etc. In these applications, a large volume of data sensed by sensors are collected at the base station or aggregated within the network. The sensor network thus is treated as a virtual database by the database community, and this database is able to return the required results when users interrogate it. Skyline and top-k queries are two fundamental queries for WSNs: the former is essential for multi-preference and decision-making, while the latter returns the most important results among the sensors. Although extensive studies for both queries have been conducted in traditional databases, they are not suitable for WSNs due to the unique characteristics imposed on its tiny sensors that are severely constrained by power, computation capability and storage. This thesis focuses on techniques and approaches for processing skyline and top-k queries in WSNs efficiently and effectively.
Specificallly, we first address skyline query evaluation on snapshot datasets by devising effient algorithms that find the skyline progressively without examining the entire dataset. The key technique adopted is to partition the dataset into disjoint subsets and to retrurn the skyline from each subset. The filter derived from the skyline of those scanned subsets is then used to filter out the unlikely candidates in the unexamined subsets. Also, we deal wth the incremental maintenance of skyline on streaming datasets by designing a novel mechanism to determine when and how to update the filter. We then study top-k query optimization in an energy-efficient manner such that the network lifetime is maximized, for which we devise a scalable, filter-based localized evaluation algorithm that is able to filter out as many unlikely top-k query results as possible from transmission within the network. We also develop an online algorithm for anwering top-k queries with various ks for streaming datasets, through the maintenance of a materialized view containing previous top-k query results. We thirdly investigate the robust protocol design for top-k query in unreliable communication environments. We propose an adaptive, localized approach to return top-k query results meeting a required accuracy, in whch each sensor can determine whether to forward the received data independently, through a nontrivial tradeoff between the energy consumption and the accuracy of query results according to its local information. To evaluate the performance of all the proposed algorithms, we fourthly conduct extensive experiments.
The experimental results indicate that the proposed algorithms outperform the existing algorithms significantly in terms of the prolongation of network lifetime and other performance metrics. We finally conclude our work and discuss several potential research avenues extended from the work in this thesis.
Description
Keywords
Citation
Collections
Source
Type
Thesis (PhD)
Book Title
Entity type
Access Statement
Open Access
License Rights
Restricted until
Downloads
File
Description