PRESTO: feedback-driven data management in sensor networks

ABSTRACT

This paper presents PRESTO, a novel two-tier sensor data management architecture comprising proxies and sensors that cooperate with one another for acquiring data and processing queries. PRESTO proxies construct time-series models of observed trends in the sensor data and transmit the parameters of the model to sensors. Sensors check sensed data with model-predicted values and transmit only deviations from the predictions back to the proxy. Such a model-driven push approach is energy-efficient, while ensuring that anomalous data trends are never missed. In addition to supporting queries on current data, PRESTO also supports queries on historical data using interpolation and local archival at sensors. PRESTO can adapt model and system parameters to data and query dynamics to further extract energy savings. We have implemented PRESTO on a sensor testbed comprising Intel Stargates and Telos Motes. Our experiments show that in a temperature monitoring application, PRESTO yields one to two orders of magnitude reduction in energy requirements over on-demand, proactive or model-driven pull approaches. PRESTO also results in an order of magnitude reduction in query latency in a 1% duty-cycled five hop sensor network over a system that forwards all queries to remote sensor nodes.

REFERENCES

• 1: G. E. P. Box and G. M. Jenkins, Time Series Analysis. Englewood Cliffs, NJ: Prentice Hall, 1991.
• 2: Hui Dai , Michael Neufeld , Richard Han, ELF: an efficient log-structured flash file system for micro sensor nodes, Proceedings of the 2nd international conference on Embedded networked sensor systems, November 03-05, 2004, Baltimore, MD, USA [doi>10.1145/1031495.1031516]
• 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: Peter Desnoyers , Deepak Ganesan , Huan Li , Ming Li , Prashant Shenoy, PRESTO: a predictive storage architecture for sensor networks, Proceedings of the 10th conference on Hot Topics in Operating Systems, p.23-23, June 12-15, 2005, Santa Fe, NM
• 5: Peter Desnoyers , Deepak Ganesan , Prashant Shenoy, TSAR: a two tier sensor storage architecture using interval skip graphs, Proceedings of the 3rd international conference on Embedded networked sensor systems, November 02-04, 2005, San Diego, California, USA [doi>10.1145/1098918.1098923]
• 6: Anish Arora , Rajiv Ramnath , Emre Ertin , Prasun Sinha , Sandip Bapat , Vinayak Naik , Vinod Kulathumani , Hongwei Zhang , Hui Cao , Mukundan Sridharan , Santosh Kumar , Nick Seddon , Chris Anderson , Ted Herman , Nishank Trivedi , Chen Zhang , Mikhail Nesterenko , Romil Shah , Sandeep Kulkarni , Mahesh Aramugam , Limin Wang , Mohamed Gouda , Young-ri Choi , David Culler , Prabal Dutta , Cory Sharp , Gilman Tolle , Mike Grimmer , Bill Ferriera , Ken Parker, ExScal: Elements of an Extreme Scale Wireless Sensor Network, Proceedings of the 11th IEEE International Conference on Embedded and Real-Time Computing Systems and Applications, p.102-108, August 17-19, 2005 [doi>10.1109/RTCSA.2005.47]
• 7: Lewis Girod , Thanos Stathopoulos , Nithya Ramanathan , Jeremy Elson , Deborah Estrin , Eric Osterweil , Tom Schoellhammer, A system for simulation, emulation, and deployment of heterogeneous sensor networks, Proceedings of the 2nd international conference on Embedded networked sensor systems, November 03-05, 2004, Baltimore, MD, USA [doi>10.1145/1031495.1031519]
• 8: J. Hellerstein, F. Zhang, and P. Shahabuddin, "An approach to predictive detection for service management," in Proc. 6th IFIP/IEEE Int. Symp. Integrated Network Management, 1999. Distributed Management for the Networked Millennium, May 1999, pp. 309-322.
• 9: 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
• 10: 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]
• 11: Brad Karp , H. T. Kung, GPSR: greedy perimeter stateless routing for wireless networks, Proceedings of the 6th annual international conference on Mobile computing and networking, p.243-254, August 06-11, 2000, Boston, Massachusetts, United States [doi>10.1145/345910.345953]
• 12: Samuel R. Madden , Michael J. Franklin , Joseph M. Hellerstein , Wei Hong, TinyDB: an acquisitional query processing system for sensor networks, ACM Transactions on Database Systems (TODS), v.30 n.1, p.122-173, March 2005 [doi>10.1145/1061318.1061322]
• 13: Alan Mainwaring , David Culler , Joseph Polastre , Robert Szewczyk , John Anderson, Wireless sensor networks for habitat monitoring, Proceedings of the 1st ACM international workshop on Wireless sensor networks and applications, September 28-28, 2002, Atlanta, Georgia, USA [doi>10.1145/570738.570751]
• 14: Gaurav Mathur , Peter Desnoyers , Deepak Ganesan , Prashant Shenoy, Ultra-low power data storage for sensor networks, Proceedings of the 5th international conference on Information processing in sensor networks, April 19-21, 2006, Nashville, Tennessee, USA [doi>10.1145/1127777.1127833]
• 15: Matthai Philipose , Kenneth P. Fishkin , Mike Perkowitz , Donald J. Patterson , Dieter Fox , Henry Kautz , Dirk Hahnel, Inferring Activities from Interactions with Objects, IEEE Pervasive Computing, v.3 n.4, p.50-57, October 2004 [doi>10.1109/MPRV.2004.7]
• 16: Joseph Polastre , Jason Hill , David Culler, Versatile low power media access for wireless sensor networks, Proceedings of the 2nd international conference on Embedded networked sensor systems, November 03-05, 2004, Baltimore, MD, USA [doi>10.1145/1031495.1031508]
• 17: Joseph Polastre , Robert Szewczyk , David Culler, Telos: enabling ultra-low power wireless research, Proceedings of the 4th international symposium on Information processing in sensor networks, April 24-27, 2005, Los Angeles, California
• 18: J. Polastre, R. Szewczyk, C. Sharp, and D. Culler, "The mote revolution: Low power wireless sensor network devices," in Proc. Hot Chips 16: A Symposium on High Performance Chips, Stanford, CA, 2004.
• 19: Sylvia Ratnasamy , Brad Karp , Li Yin , Fang Yu , Deborah Estrin , Ramesh Govindan , Scott Shenker, GHT: a geographic hash table for data-centric storage, Proceedings of the 1st ACM international workshop on Wireless sensor networks and applications, September 28-28, 2002, Atlanta, Georgia, USA [doi>10.1145/570738.570750]
• 20: Center for Embedded Networked Sensing (CENS)--James Reserve Data Management System, Univ. of California Natural Reserve System [Online]. Available: http://dms.jamesreserve.edu/
• 21: 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]
• 22: W. Ye, J. Heidemann, and D. Estrin, "An energy-efficient MAC protocol for wireless sensor networks," in Proc. IEEE INFOCOM, New York, NY, 2002.
• 23: Jerry Zhao , Ramesh Govindan, Understanding packet delivery performance in dense wireless 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.958493]
• 24: 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]
• 25: D. Tulone and S. Madden, "PAQ: Time series forecasting for approximate query answering in sensor networks," in Proc. 3rd European Workshop on Wireless Sensor Networks (EWSN), Zurich, Switzerland, 2006.
• 26: Saurabh Ganeriwal , Deepak Ganesan , Hohyun Shim , Vlasios Tsiatsis , Mani B. Srivastava, Estimating clock uncertainty for efficient duty-cycling in sensor networks, Proceedings of the 3rd international conference on Embedded networked sensor systems, November 02-04, 2005, San Diego, California, USA [doi>10.1145/1098918.1098933]

INDEX TERMS

Primary Classification:
  C. Computer Systems Organization
  C.2 COMPUTER-COMMUNICATION NETWORKS
      C.2.3 Network Operations
          Subjects: Network management

Additional Classification:
  C. Computer Systems Organization
  C.2 COMPUTER-COMMUNICATION NETWORKS
      C.2.m Miscellaneous
  C.4 PERFORMANCE OF SYSTEMS
      Subjects: Design studies; Performance attributes

  G. Mathematics of Computing
  G.3 PROBABILITY AND STATISTICS
      Subjects: Time series analysis

  I. Computing Methodologies
  I.6 SIMULATION AND MODELING
      I.6.5 Model Development

General Terms:
Design, Management, Performance

Keywords:
data management, model-driven push, sensor networks, time-series models