skip to main content
10.1145/1286380.1286382acmotherconferencesArticle/Chapter ViewAbstractPublication PagesdmsnConference Proceedingsconference-collections
Article

Similarity-aware query allocation in sensor networks with multiple base stations

Published: 24 September 2007 Publication History

Abstract

In this paper, we consider a large scale sensor network comprising multiple, say K, base stations and a large number of wireless sensors. Such an infrastructure is expected to be more energy efficient and scale well with the size of the sensor nodes. To support a large number of queries, we examine the problem of allocating queries across the base stations to minimize the total data communication cost among the sensors. In particular, we examine similarity-aware techniques that exploit the similarities among queries when allocating queries, so that queries that require data from a common set of sensor nodes are allocated to the same base stations. We first approximate the problem of allocating queries to K base stations as a max-K-cut problem, and adapts an existing solution to our context. However, the scheme only works in a static context, where all queries are known in advance. In order to operate in a dynamic environment with frequent query arrivals and termination, we further propose a novel similarity-aware strategy that allocates queries to base stations one at a time. We also propose several heuristics to order a batch of queries for incremental allocation. We conducted experiments to evaluate our proposed schemes, and our results show that our similarity-aware query allocation schemes can effectively exploit the sharing among queries to greatly reduce the communication cost.

References

[1]
Y. Ahmad and U. Çetintemel. Networked query processing for distributed stream-based applications. In VLDB, pages 456--467, 2004.
[2]
S. Arora, C. Lund, R. Motwani, M. Sudan, and M. Szegedy. Proof verification and the hardness of approximation problems. Journal of the ACM (JACM), 45(3):501--555, 1998.
[3]
T. H. Cormen, C. E. Leiserson, and R. L. Rivest. Introduction to Algorithms. MIT Press, 2001.
[4]
A. Deligiannakis, Y. Kotidis, and N. Roussopoulos. Hierarchical in-network data aggregation with quality guarantees. In EDBT, 2004.
[5]
A. Deshpande, C. Guestrin, S. Madden, J. M. Hellerstein, and W. Hong. Model-driven data acquisition in sensor networks. In VLDB, 2004.
[6]
A. Frieze. Improved approximation algorithms for max k-cut and max bisection. Algorithmica, 18(1):67--81, 1997.
[7]
M. Goemans and D. Williamson. Improved approximation algorithms for maximum cut and satisfiability problems using semidefinite programming. Journal of the ACM (JACM), 42(6): 1115--1145, 1995.
[8]
H. Lu and K. Tan. Load-balanced join processing in shared-nothing systems. Journal of Parallel and Distributed Computing, 23(3):382--398, 1994.
[9]
S. Madden, M. J. Franklin, J. M. Hellerstein, and W. Hong. TinyDB: An acquisitional query processing system for sensor networks. ACM TODS, 30(1), November 2005.
[10]
A. Munteanu, J. Beaver, A. Labrinidis, and P. K. Chrysanthis. Multiple query routing trees in sensor networks. In Proc. of the IASTED International Conference on Databases and Applications (DBA), 2005.
[11]
N. Selvakkumaran and G. Karypis. Multiobjective Hypergraph-Partitioning Algorithms for Cut and Maximum Subdomain-Degree Minimization. Computer-Aided Design of Integrated Circuits and Systems, IEEE Transactions on, 25(3):504--517, 2006.
[12]
A. Silberstein and J. Yang. Many-to-many aggregation for sensor networks. In ICDE, 2007.
[13]
X. Tang and J. Xu. Extending network lifetime for precision-constrained data aggregation in wireless sensor networks. In INFOCOM, 2006.
[14]
K.-C. Toh, et al. Sdpt3. http://www.math.nus.edu.sg/~mattohkc/sdpt3.html.
[15]
N. Trigoni, et al. Multi-query optimization for sensor networks. In DCOSS, 2005.
[16]
S. Xiang, et al. Two-tier multiple query optimization for sensor networks. In ICDCS, 2007.
[17]
Y. Xing, S. B. Zdonik, and J.-H. Hwang. Dynamic load distribution in the borealis stream processor. In ICDE, 2005.
[18]
X. Yang, et al. In-network execution of monitoring queries in sensor networks. In SIDMOD, 2007.
[19]
Y. Yao and J. Gehrke. Query processing for sensor networks. In CIDR, 2003.
[20]
Y. Zhou, et al. Efficient dynamic operator placement in a locally distributed continuous query system. In CoopIS, 2006.

Cited By

View all
  • (2019)Bloom filter based processing algorithms for the multi-dimensional event query in wireless sensor networksJournal of Network and Computer Applications10.1016/j.jnca.2013.03.00337(323-333)Online publication date: 25-Nov-2019
  • (2012)New Fuzzy Similarity Measure for Restricted Mobile NetworksAdvanced Engineering Forum10.4028/www.scientific.net/AEF.6-7.10936-7(1093-1097)Online publication date: Sep-2012
  • (2012)A Continuous Query Allocation Scheme with Time-Parameters in Wireless Sensor Networks with Multiple SinksIEICE Transactions on Communications10.1587/transcom.E95.B.1431E95-B:4(1431-1434)Online publication date: 2012
  • Show More Cited By

Recommendations

Comments

Information & Contributors

Information

Published In

cover image ACM Other conferences
DMSN '07: Proceedings of the 4th workshop on Data management for sensor networks: in conjunction with 33rd International Conference on Very Large Data Bases
September 2007
46 pages
ISBN:9781595939111
DOI:10.1145/1286380
  • General Chairs:
  • Amol Deshpande,
  • Qiong Luo
Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]

Sponsors

  • Intel: Intel

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 24 September 2007

Permissions

Request permissions for this article.

Check for updates

Qualifiers

  • Article

Conference

VLDB '07
Sponsor:
  • Intel

Acceptance Rates

Overall Acceptance Rate 6 of 16 submissions, 38%

Contributors

Other Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

  • Downloads (Last 12 months)1
  • Downloads (Last 6 weeks)1
Reflects downloads up to 20 Feb 2025

Other Metrics

Citations

Cited By

View all
  • (2019)Bloom filter based processing algorithms for the multi-dimensional event query in wireless sensor networksJournal of Network and Computer Applications10.1016/j.jnca.2013.03.00337(323-333)Online publication date: 25-Nov-2019
  • (2012)New Fuzzy Similarity Measure for Restricted Mobile NetworksAdvanced Engineering Forum10.4028/www.scientific.net/AEF.6-7.10936-7(1093-1097)Online publication date: Sep-2012
  • (2012)A Continuous Query Allocation Scheme with Time-Parameters in Wireless Sensor Networks with Multiple SinksIEICE Transactions on Communications10.1587/transcom.E95.B.1431E95-B:4(1431-1434)Online publication date: 2012
  • (2009)Query Allocation in Wireless Sensor Networks with Multiple Base StationsProceedings of the 14th International Conference on Database Systems for Advanced Applications10.1007/978-3-642-00887-0_10(107-122)Online publication date: 16-Mar-2009

View Options

Login options

View options

PDF

View or Download as a PDF file.

PDF

eReader

View online with eReader.

eReader

Figures

Tables

Media

Share

Share

Share this Publication link

Share on social media