Processing continuous top-k data collection queries in lifetime-constrained wireless sensor networks

We study the processing of continuous top-k data collection (CTKDC) queries in lifetime-constrained wireless sensor networks. A query of this type continuously collects a list of k highest sensor readings into the base station in every epoch and reports to the user. So far, algorithms proposed to process these queries conventionally assume that k is a fixed number and then try to reduce the energy consumption of the sensor nodes or to maximize the lifetime of the network. However, in many practical monitoring applications, the most important user requirement is that the network can collect sensor data effectively for at least a designated amount of time while the value of k can be changed flexibly and only needs to be as high as possible. Therefore, in this paper, we propose an adaptive algorithm to process CTKDC queries in lifetime-constrained wireless sensor networks. Our algorithm works proactively at the sensor nodes and guides each sensor node to compute adaptively the amount of sensor data that it should send to the base station in each sampling interval. By controlling carefully the amounts of sensor data sent, and thus the cost of message transmissions, all sensor nodes together both make sure that the network will run until when the lifetime constraint is satisfied, and maximize the amount of top-k data reported to the user. Through experimental results, we show that the proposed algorithm can effectively ensure the network lifetime requirements when processing CTKDC queries. Moreover, the average amount of top-k data collected by this algorithm in a sampling interval is very close to the one obtained by the offline optimal algorithm in which all sensor readings are assumed to be known a priori.