Energy-efficient query processing in sensor networks

Abstract

A sensor network is a network of many small wireless sensor device nodes (called nodes, for short) embedded in the physical world. Owing to the dramatic advances of related technologies, sensor nodes themselves become smaller and cheaper as well as stronger in the aspect of computing power. As a result, sensor networks can be applied to diverse application areas demanding various query capabilities. Continuous query processing has been extensively discussed in many papers because the most common function of sensor networks is to report continuously sensed values through successive monitoring of environmental phenomena. Performance improvement for continuous query processing is important because continuous queries are processed many times, e.g., hundreds of thousands of times. In sensor networks, continuous query processing consists of two phases; $\It{query transmission and routing tree construction}$ and $\It{query result transmission}$. In the former, a user query is transmitted to all nodes in the region specified by the query, and, at the same time, each nodes select its parent node to report its data. In this manner, both query transmission and routing tree construction are performed simultaneously. In the latter, each node in the routing tree periodically reports its result to its parent in a bottom up fashion. Generally, query transmission and routing tree construction is performed once while query result transmission is perform repeatedly. In this dissertation, we propose efficient methods for above both phases. For query transmission and routing tree construction phase, we considers a continuous query whose query region is specified by a KNN(K Nearest Neighbor) predicate. We proposed an efficient method to find the region specified by KNN predicate and to construct a more message-efficient routing tree. For query result transmission phase, we propose an efficient method to process continuous aggregation queries with tolerable erro...