Take a look at the new version of this page: [ beta version ]. Tell us what you think.

ABSTRACT

The rapid development in micro-sensors and wireless networks has made large-scale sensor networks possible. However, the wide deployment of such systems is still hindered by their limited energy which quickly runs out in case of massive communication. In this paper, we study the cost-efficient processing of aggregate queries that are generally communication-intensive. In particular, we focus on MIN/MAX queries that require both identity and value in the answer. We study how to provide an error bound to such answers, and how to design an "optimal" sensor-contact policy that minimizes communication cost in reducing the error to a user-tolerable level.

REFERENCES

• 1: G. J. Pottie , W. J. Kaiser, Wireless integrated network sensors, Communications of the ACM, v.43 n.5, p.51-58, May 2000 [doi>10.1145/332833.332838]
• 2: Hüseyin Özgür Tan , Ibrahim Körpeoǧlu, Power efficient data gathering and aggregation in wireless sensor networks, ACM SIGMOD Record, v.32 n.4, December 2003 [doi>10.1145/959060.959072]
• 3: Bhaskar Krishnamachari , Deborah Estrin , Stephen B. Wicker, The Impact of Data Aggregation in Wireless Sensor Networks, Proceedings of the 22nd International Conference on Distributed Computing Systems, p.575-578, July 02-05, 2002
• 4: S. Lindsey and C. S. Raghavendra. Pegasis: Power-effi cient gathering in sensor information systems. In Proceedings of IEEE Aerospace Conference, 2002.
• 5: Wendi Rabiner Heinzelman , Anantha Chandrakasan , Hari Balakrishnan, Energy-Efficient Communication Protocol for Wireless Microsensor Networks, Proceedings of the 33rd Hawaii International Conference on System Sciences-Volume 8, p.8020, January 04-07, 2000
• 6: D. D. Wackerly, W. Mendenhall III, and R. L. Scheaffer. Mathematical Statistics with Applications. Duxbury, 6th edition, 2002.
• 7: K. Kalpakis, V. Puttagunta, and P. Namjoshi. Accuracy vs. lifetime: Linear sketches for approximate aggregate range queries in sensor networks. Technical report, Computer Science and Eletrical Engineering Department, University of Maryland Baltimore County, 2004.
• 8: Jeffrey Considine , Feifei Li , George Kollios , John Byers, Approximate Aggregation Techniques for Sensor Databases, Proceedings of the 20th International Conference on Data Engineering, p.449, March 30-April 02, 2004
• 9: Reynold Cheng , Dmitri V. Kalashnikov , Sunil Prabhakar, Evaluating probabilistic queries over imprecise data, Proceedings of the 2003 ACM SIGMOD international conference on Management of data, June 09-12, 2003, San Diego, California [doi>10.1145/872757.872823]
• 10: A. Deshpande, C. Guestrin, S. Madden, J. Hellerstein, and W. Hong. Model-driven data acquisition in sensor networks. 2004.
• 11: Chris Olston , Jennifer Widom, Offering a Precision-Performance Tradeoff for Aggregation Queries over Replicated Data, Proceedings of the 26th International Conference on Very Large Data Bases, p.144-155, September 10-14, 2000
• 12: Tomas Feder , Rajeev Motwani , Rina Panigrahy , Chris Olston , Jennifer Widom, Computing the median with uncertainty, Proceedings of the thirty-second annual ACM symposium on Theory of computing, p.602-607, May 21-23, 2000, Portland, Oregon, United States [doi>10.1145/335305.335386]
• 13: Sanjeev Khanna , Wang-Chiew Tan, On computing functions with uncertainty, Proceedings of the twentieth ACM SIGMOD-SIGACT-SIGART symposium on Principles of database systems, p.171-182, May 2001, Santa Barbara, California, United States [doi>10.1145/375551.375577]
• 14: Z. Liu, K. C. Sia, and J. Cho. Cost-effi cient processing of min/max queries over distributed sensors with uncertainty. Technical report, Computer Science Department, UCLA, 2004.

INDEX TERMS

Primary Classification:
  F. Theory of Computation
  F.0 GENERAL

General Terms:
Theory

Keywords:
MIN/MAX query processing, query answering with uncertainty