TY - GEN
T1 - Energy-efficient multiple routing trees for aggregate query evaluation in sensor networks
AU - Liu, Yuzhen
AU - Liang, Weifa
N1 - Publication details (e.g. title, author(s), publication statuses and dates) are captured on an “AS IS” and “AS AVAILABLE” basis at the time of record harvesting from the data source. Suggestions for further amendments or supplementary information can be sent to [email protected].
PY - 2008
Y1 - 2008
N2 - 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. © 2008 Springer-Verlag Berlin Heidelberg.
AB - 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. © 2008 Springer-Verlag Berlin Heidelberg.
UR - https://www.scopus.com/pages/publications/44649111362
UR - https://www.scopus.com/record/pubmetrics.uri?eid=2-s2.0-44649111362&origin=recordpage
U2 - 10.1007/978-3-540-68807-5_17
DO - 10.1007/978-3-540-68807-5_17
M3 - RGC 32 - Refereed conference paper (with host publication)
SN - 3540688056
SN - 9783540688051
VL - 5031 LNCS
T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
SP - 201
EP - 212
BT - Wired/Wireless Internet Communications - 6th International Conference, WWIC 2008, Proceedings
T2 - 6th International Conference on Wired/Wireless Internet Communications, WWIC 2008
Y2 - 28 May 2008 through 30 May 2008
ER -