Top-k Query Evaluation in Sensor Networks with the Guaranteed Accuracy of Query Results

Abstract

In many applications of sensor networks including environmental monitoring and surveillance, a large volume of sensed data generated by sensors needs to be either collected at the base station or aggregated within the network to respond to user queries. However, due to the unreliable wireless communication, robust query processing in such networks becomes a great challenge in the design of query evaluation algorithms for some mission-critical tasks. In this paper we propose an adaptive, localized algorithm for robust top-k query processing in sensor networks, which trades off between the energy consumption and the accuracy of query results. In the proposed algorithm, whether a sensor is to forward the collected data to the base station is determined in accordance with the calculation of a proposed local function, which is the estimation of the probability of transmitting the data successfully. We also conduct extensive experiments by simulations on real datasets to evaluate the performance of the proposed algorithm. The experimental results demonstrate that the proposed algorithm is energy-efficient while achieving the specified accuracy of the query results.