Asynchronous in-network prediction: Efficient aggregation in sensor networks

ABSTRACT

Given a sensor network and aggregate queries over the values sensed by subsets of nodes in the network, how do we ensure that high quality results are served for the maximum possible time? The issues underlying this question relate to the fidelity of query results and lifetime of the network. To maximize both, we propose a novel technique called asynchronous in-network prediction incorporating two computationally efficient methods for in-network prediction of partial aggregate values. These values are propagated via a tree whose construction is cognizant of (a) the coherency requirements associated with the queries, (b) the remaining energy at the sensors, and (c) the communication and message processing delays. Finally, we exploit in-network filtering and in-network aggregation to reduce the energy consumption of the nodes in the network. Experimental results over real world data support our claim that, for aggregate queries with associated coherency requirements, a prediction-based, asynchronous scheme provides higher quality results for a longer amount of time than a synchronous scheme. Also, whereas aggregate dissemination techniques proposed so far for sensor networks appear to have to trade-off quality of data for energy efficiency, we demonstrate that this is not always necessary.

REFERENCES

• 1: David Chu , Amol Deshpande , Joseph M. Hellerstein , Wei Hong, Approximate Data Collection in Sensor Networks using Probabilistic Models, Proceedings of the 22nd International Conference on Data Engineering, p.48, April 03-07, 2006 [doi>10.1109/ICDE.2006.21]
• 2: Graham Cormode , Minos Garofalakis , S. Muthukrishnan , Rajeev Rastogi, Holistic aggregates in a networked world: distributed tracking of approximate quantiles, Proceedings of the 2005 ACM SIGMOD international conference on Management of data, June 14-16, 2005, Baltimore, Maryland [doi>10.1145/1066157.1066161]
• 3: Amol Deshpande , Carlos Guestrin , Samuel R. Madden , Joseph M. Hellerstein , Wei Hong, Model-driven data acquisition in sensor networks, Proceedings of the Thirtieth international conference on Very large data bases, p.588-599, August 31-September 03, 2004, Toronto, Canada
• 4: Samir Goel , Tomasz Imielinski, Prediction-based monitoring in sensor networks: taking lessons from MPEG, ACM SIGCOMM Computer Communication Review, v.31 n.5, October 2001 [doi>10.1145/1037107.1037117]
• 5: Jason L. Hill , David E. Culler, Mica: A Wireless Platform for Deeply Embedded Networks, IEEE Micro, v.22 n.6, p.12-24, November 2002 [doi>10.1109/MM.2002.1134340]
• 6: Jason Hill , Robert Szewczyk , Alec Woo , Seth Hollar , David Culler , Kristofer Pister, System architecture directions for networked sensors, Proceedings of the ninth international conference on Architectural support for programming languages and operating systems, p.93-104, November 2000, Cambridge, Massachusetts, United States
• 7: Chalermek Intanagonwiwat , Ramesh Govindan , Deborah Estrin, Directed diffusion: a scalable and robust communication paradigm for sensor networks, Proceedings of the 6th annual international conference on Mobile computing and networking, p.56-67, August 06-11, 2000, Boston, Massachusetts, United States [doi>10.1145/345910.345920]
• 8: Inventory of U.S. Globec Georges Bank Data, Project: AL9508. 1995. http://jgof.wh.whoi.edu/jg/serv/globec/gb/brdscale/al_shipdata.html1%7Bdir=globec.whoi.edu/jg/dir/globec/gb/broadscale/, info=globec.whoi.edu/jg/info/globec/gb/broadscale/alongtrack%7D?cruise_id%20eq%20al9508.
• 9: Kaiser, W. J. 2000. WINS NG 1.0 Transceiver Power Dissipation Specifications. Sensoria Corp.
• 10: Philip Levis , Nelson Lee , Matt Welsh , David Culler, TOSSIM: accurate and scalable simulation of entire TinyOS applications, Proceedings of the 1st international conference on Embedded networked sensor systems, November 05-07, 2003, Los Angeles, California, USA [doi>10.1145/958491.958506]
• 11: Ming Li , Deepak Ganesan , Prashant Shenoy, PRESTO: feedback-driven data management in sensor networks, Proceedings of the 3rd conference on Networked Systems Design & Implementation, p.23-23, May 08-10, 2006, San Jose, CA
• 12: Samuel Madden , Michael J. Franklin , Joseph M. Hellerstein , Wei Hong, TAG: a Tiny AGgregation service for ad-hoc sensor networks, ACM SIGOPS Operating Systems Review, v.36 n.SI, Winter 2002 [doi>10.1145/844128.844142]
• 13: Amit Manjhi , Suman Nath , Phillip B. Gibbons, Tributaries and deltas: efficient and robust aggregation in sensor network streams, Proceedings of the 2005 ACM SIGMOD international conference on Management of data, June 14-16, 2005, Baltimore, Maryland [doi>10.1145/1066157.1066191]
• 14: Suman Nath , Phillip B. Gibbons , Srinivasan Seshan , Zachary R. Anderson, Synopsis diffusion for robust aggregation in sensor networks, Proceedings of the 2nd international conference on Embedded networked sensor systems, November 03-05, 2004, Baltimore, MD, USA [doi>10.1145/1031495.1031525]
• 15: Chris Olston , Jing Jiang , Jennifer Widom, Adaptive filters for continuous queries over distributed data streams, Proceedings of the 2003 ACM SIGMOD international conference on Management of data, June 09-12, 2003, San Diego, California [doi>10.1145/872757.872825]
• 16: Chris Olston , Boon Thau Loo , Jennifer Widom, Adaptive precision setting for cached approximate values, ACM SIGMOD Record, v.30 n.2, p.355-366, June 2001
• 17: Spiros Papadimitriou , Anthony Brockwell , Christos Faloutsos, Adaptive, hands-off stream mining, Proceedings of the 29th international conference on Very large data bases, p.560-571, September 09-12, 2003, Berlin, Germany
• 18: Shetal Shah , Shyamshankar Dharmarajan , Krithi Ramamritham, An efficient and resilient approach to filtering and disseminating streaming data, Proceedings of the 29th international conference on Very large data bases, p.57-68, September 09-12, 2003, Berlin, Germany
• 19: Mohamed A. Sharaf , Jonathan Beaver , Alexandros Labrinidis , Panos K. Chrysanthis, TiNA: a scheme for temporal coherency-aware in-network aggregation, Proceedings of the 3rd ACM international workshop on Data engineering for wireless and mobile access, September 19-19, 2003, San Diego, CA, USA [doi>10.1145/940923.940937]
• 20: TinyOS Website. http://www.tinyos.net.
• 21: Trigoni, N., Yao, Y., Demers, A. J., Gehrke, J., and Rajaraman, R. 2005. Multi-query optimization for sensor networks. In Proceedings of the 1st IEEE International Conference on Distributed Computing in Sensor Systems (DCOSS'05). 307--321.
• 22: Alec Woo , Terence Tong , David Culler, Taming the underlying challenges of reliable multihop routing in sensor networks, Proceedings of the 1st international conference on Embedded networked sensor systems, November 05-07, 2003, Los Angeles, California, USA [doi>10.1145/958491.958494]
• 23: Yong Yao , Johannes Gehrke, The cougar approach to in-network query processing in sensor networks, ACM SIGMOD Record, v.31 n.3, September 2002 [doi>10.1145/601858.601861]
• 24: Peter Young, Recursive estimation and time-series analysis: an introduction, Springer-Verlag New York, Inc., New York, NY, 1984

INDEX TERMS

Primary Classification:
  H. Information Systems
  H.2 DATABASE MANAGEMENT
      H.2.4 Systems
          Subjects: Query processing

General Terms:
Algorithms, Performance, Reliability

Keywords:
Aggregation, coherency, energy efficient, prediction, query processing