Energy-efficient monitoring of extreme values in sensor networks

ABSTRACT

Monitoring extreme values (MAX or MIN) is a fundamental problem in wireless sensor networks (and in general, complex dynamic systems). This problem presents very different algorithmic challenges from aggregate and selection queries, in the sense that an individual node cannot by itself determine its inclusion in the query result. We present novel query processing algorithms for this problem, with the goal of minimizing message traffic in the network. These algorithms employ a hierarchy of local constraints, or thresholds, to leverage network topology such that message-passing is localized. We evaluate all algorithms using simulated and real-world data to study various trade-offs.

REFERENCES

• 1: Brain Babcock , Mayur Datar , Rajeev Motwani , Liadan O'Callaghan, Maintaining variance and k-medians over data stream windows, Proceedings of the twenty-second ACM SIGMOD-SIGACT-SIGART symposium on Principles of database systems, p.234-243, June 09-11, 2003, San Diego, California [doi>10.1145/773153.773176]
• 2: Reynold Cheng , Ben Kao , Sunil Prabhakar , Alan Kwan , Yicheng Tu, Adaptive stream filters for entity-based queries with non-value tolerance, Proceedings of the 31st international conference on Very large data bases, August 30-September 02, 2005, Trondheim, Norway
• 3: Chuck Conner. Modeling Heat Transfer in Parallel. http://www.cas.usf.edu/~cconnor/parallel/2dheat/2dheat.html.
• 4: 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
• 5: Crossbow Inc. MPR-Mote Processor Radio Board User's Manual.
• 6: A. Deligannakis, Y. Kotidis, and N. Roussopoulos. Hierarchical In-Network Data Aggregation with Quality Guarantees. In Proc. of the 2004 Intl. Conf. on Extending Database Technology, Heraklion, Crete, Mar. 2004.
• 7: Intel Berkeley Research Lab. http://berkeley.intel-research.net/labdata/.
• 8: Zhenyu Liu , Ka Cheung Sia , Junghoo Cho, Cost-efficient processing of MIN/MAX queries over distributed sensors with uncertainty, Proceedings of the 2005 ACM symposium on Applied computing, March 13-17, 2005, Santa Fe, New Mexico [doi>10.1145/1066677.1066823]
• 9: Samuel Madden , Michael J. Franklin , Joseph M. Hellerstein , Wei Hong, TAG: a Tiny AGgregation service for Ad-Hoc sensor networks, Proceedings of the 5th symposium on Operating systems design and implementation

  Due to copyright restrictions we are not able to make the PDFs for this conference available for downloading

  , December 09-11, 2002, Boston, Massachusetts [doi>10.1145/1060289.1060303]
• 10: Samuel Madden , Robert Szewczyk , Michael J. Franklin , David Culler, Supporting Aggregate Queries Over Ad-Hoc Wireless Sensor Networks, Proceedings of the Fourth IEEE Workshop on Mobile Computing Systems and Applications, p.49, June 20-21, 2002
• 11: Chris Olston , Boon Thau Loo , Jennifer Widom, Adaptive precision setting for cached approximate values, Proceedings of the 2001 ACM SIGMOD international conference on Management of data, p.355-366, May 21-24, 2001, Santa Barbara, California, United States
• 12: Sundeep Pattem , Bhaskar Krishnamachari , Ramesh Govindan, The impact of spatial correlation on routing with compression in wireless sensor networks, Proceedings of the third international symposium on Information processing in sensor networks, April 26-27, 2004, Berkeley, California, USA [doi>10.1145/984622.984627]
• 13: D. Petrovic, R. Shah, K. Ramchandran, and J. Rabaey. Data Funneling: Routing with Aggregation and Compression for Wireless Sensor Networks. In Proc. of the 2003 IEEE Sensor Network Protocols and Applications, Anchorage, Alaska, USA, May 2003.
• 14: Nisheeth Shrivastava , Chiranjeeb Buragohain , Divyakant Agrawal , Subhash Suri, Medians and beyond: new aggregation techniques for sensor networks, Proceedings of the 2nd international conference on Embedded networked sensor systems, November 03-05, 2004, Baltimore, MD, USA [doi>10.1145/1031495.1031524]
• 15: Adam Silberstein Silberstein , Rebecca Braynard , Carla Ellis , Kamesh Munagala , Jun Yang, A Sampling-Based Approach to Optimizing Top-k Queries in Sensor Networks, Proceedings of the 22nd International Conference on Data Engineering (ICDE'06), p.68, April 03-07, 2006 [doi>10.1109/ICDE.2006.10]

INDEX TERMS

Primary Classification:
  H. Information Systems
  H.4 INFORMATION SYSTEMS APPLICATIONS
      H.4.0 General

General Terms:
Algorithms, Design

Keywords:
aggregate, continuous queries, max, sensor networks