Approximate Querying in Wireless Sensor Networks

In this paper, we study the maximization problem of network lifetime for answering a sequence of aggregate queries based on snapshot data. We build a series of nearly optimal representative routing trees for query evaluation, where a representative routing tree is such a tree rooted at the base station that each node in it represents a set of non-tree nodes by holding their historical data (snapshot data). A representative routing tree is optimal if the minimum residual energy among its nodes is maximized, and the number of nodes in the tree is minimized. Due to the unpredictability of future queries, we will focus on the construction of individual optimal representative routing trees in order to solve the maximization problem of network lifetime. We first show the optimal representative routing tree problem is NP-complete. Instead, we then devise two heuristic algorithms for it. We finally conduct extensive experiments by simulations to evaluate the performance of the proposed algorithms in terms of the network lifetime and the average size of representative routing trees. The experimental results showed the proposed algorithms outperform an existing algorithm significantly.