Energy-efficient multiple routing trees for aggregate query evaluation in sensor networks

In this paper we consider the problem of finding multiple routing trees in sensor networks for the evaluation of a class of aggregate queries including AVG, MIN, MAX, and COUNT with an objective to maximizing the network lifetime. Due to the NP hardness of the problem, we instead devise a heuristic algorithm for it. Unlike the previous work that focused on finding a single routing tree for query evaluation, we introduce the concept of multiple routing trees, and use these trees to evaluate aggregate queries, provided that different routing trees are used at different stages of the network lifetime. To evaluate the performance of the proposed algorithm, we conduct extensive experiments by simulation. The experimental results show that the proposed algorithm outperforms existing algorithms based on a single routing tree. We also prove that the approximation ratio of a known approximation algorithm for the identical energy case is a constant, and provide tighter lower and upper bounds on the optimal network lifetime for the non-identical energy case.