Baljeet Malhotra
ABSTRACT
Finding an aggregation of observed values, in particular the maximum value, is an important type of query in wireless sensor networks. Previous proposals to find the maximum value, the so-called MAX query, relied on a given underlying logical tree topology for data aggregation/forwarding, but did not pay due attention to the role of such topology. Focusing on the MAX queries we first argue that the underlying tree topology plays a very important role in the query processing cost. We then propose the use of a particular tree topology, based on Dominating Sets that is well suited to explore the network's physical topology for processing MAX queries efficiently. Experimental results obtained using real and synthetic datasets confirm that by simply replacing the tree topologies used in previous proposals with the Dominating Set-based Tree (DST) one can reduce the transmission cost of MAX queries by up to 70% and overall energy consumption by up to 53%.
- http://db.csail.mit.edu/labdata/labdata.html.Google Scholar
- B. Babcock and C. Olston. Distributed top-k monitoring. Proc. of the ACM SIGMOD'03, pages 28--39, 2003. Google ScholarDigital Library
- J. Blum, et. al. Connected dominating set in sensor networks and manets. D.-Z. Du, P. Pardalos (Eds.), Handbook of Combinatorial Optimization, pages 329--369, 2005.Google ScholarCross Ref
- J. J. Garcia-Luna-Aceves and E. L. Madruga. The core assisted mesh protocol. IEEE Journal on Selected Areas in Communications, 17(8):1380--1394, 1999. Google ScholarDigital Library
- C. R. Lin and M. Gerla. Adaptive clustering for mobile wireless networks. IEEE Journal on Selected Areas in Communications, 15(7):1265--1275, 1997. Google ScholarDigital Library
- S. Madden, et. al. TAG: A tiny aggregation service for ad-hoc sensor networks. Proc. of the OSDI'02, 36:131--146, 2002. Google ScholarDigital Library
- A. Silberstein, et. al. A sampling-based approach to optimizing top-k queries in sensor networks. Proc. of the IEEE ICDE'06, pages 68--78, 2006. Google ScholarDigital Library
- A. Silberstein, R. Braynard, and J. Yang. Constraint-chaining: On energy-efficient continuous monitoring in sensor networks. Proc. of the ACM SIGMOD'06, pages 157--168, 2006. Google ScholarDigital Library
- A. Silberstein, K. Munagala, and J. Yang. Energy-efficient monitoring of extreme values in sensor networks. Proc. of the ACM SIGMOD'06, pages 169--180, 2006. Google ScholarDigital Library
- P. J. Wan, K. M. Alzoubi, and O. Frieder. Distributed construction of connected dominating set in wireless ad hoc networks. Discrete algorithms and methods for mobile computing and communications, 9(2):141--149, 2004. Google ScholarDigital Library
- M. Wu, et. al. Top-k monitoring in wireless sensor networks. IEEE Trans. on Knowledge and Data Engineering, 19(7):962--976, 2007. Google ScholarDigital Library
- D. Zeinalipour-Yazti, et. al. The threshold join algorithm for top-k queries in distributed sensor networks. Proc. of the VLDB workshop DMSN'05, pages 61--66, 2005. Google ScholarDigital Library
- Y. Zhao, L. Xu, and M. Shi. On-demand multicast routing protocol with multipoint relay (ODMRP-MPR) in mobile ad-hoc network. Proc. of the ICCT'03, 2(2):1295--1300, 2003.Google ScholarCross Ref
Index Terms
- Better tree - better fruits: using dominating set trees for MAX queries
Recommendations
A Better Constant-Factor Approximation for Selected-Internal Steiner Minimum Tree
The selected-internal Steiner minimum tree problem is a generalization of original Steiner minimum tree problem. Given a weighted complete graph G=(V,E) with weight function c, and two subsets RźźR⊆V with |RźRź|ź2, selected-internal Steiner minimum tree ...
A Better Constant-Factor Approximation for Selected-Internal Steiner Minimum Tree
Special Issue: Computation and Combinatorial Optimization; Guest Editors: Xiaodong Hu and Jie WangThe selected-internal Steiner minimum tree problem is a generalization of original Steiner minimum tree problem. Given a weighted complete graph G=(V,E) with weight function c, and two subsets R ′ ⊊ R⊆V with |R−R ′|≥2, selected-internal Steiner minimum ...
Depth First Search-based and power-aware geo-routing in ad hoc and sensor wireless networks
Depth First Search (DFS) and position-based routing algorithms were proposed in literature. These are localised algorithms that guarantee the delivery for connected ad hoc and sensor wireless networks modelled by arbitrary graphs, including inaccurate ...
Comments