Contour map matching for event detection in sensor networks

ABSTRACT

Many sensor network applications, such as object tracking and disaster monitoring, require effective techniques for event detection. In this paper, we propose a novel event detection mechanism based on matching the contour maps of in-network sensory data distribution. Our key observation is that events in sensor networks can be abstracted into spatio-temporal patterns of sensory data and that pattern matching can be done efficiently through contour map matching. Therefore, we propose simple SQL extensions to allow users to specify common types of events as patterns in contour maps and study energy-efficient techniques of contour map construction and maintenance for our pattern-based event detection. Our experiments with synthetic workloads derived from a real-world coal mine surveillance application validate the effectiveness and efficiency of our approach.

REFERENCES

• 1: Daniel J. Abadi , Samuel Madden , Wolfgang Lindner, REED: robust, efficient filtering and event detection in sensor networks, Proceedings of the 31st international conference on Very large data bases, August 30-September 02, 2005, Trondheim, Norway
• 2: Rakesh Agrawal , Giuseppe Psaila , Edward L. Wimmers , Mohamed Zaït, Querying Shapes of Histories, Proceedings of the 21th International Conference on Very Large Data Bases, p.502-514, September 11-15, 1995
• 3: Bonnet, P., Gehrke, J., and Seshadri, P. Querying the physical world. IEEE Personal Communications, 7(5), 2000.
• 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: Contour Map. http://en.wikipedia.org/wiki/Contour_map.
• 6: Crossbow Inc. www.xbow.com.
• 7: Antonios Deligiannakis , Yannis Kotidis , Nick Roussopoulos, Compressing historical information in sensor networks, Proceedings of the 2004 ACM SIGMOD international conference on Management of data, June 13-18, 2004, Paris, France [doi>10.1145/1007568.1007628]
• 8: Deshpande, A., Guestrin, C., and Madden, S. Model-driven data acquisition in sensor networks. VLDB, 2004.
• 9: Prabal Dutta , Mike Grimmer , Anish Arora , Steven Bibyk , David Culler, Design of a wireless sensor network platform for detecting rare, random, and ephemeral events, Proceedings of the 4th international symposium on Information processing in sensor networks, April 24-27, 2005, Los Angeles, California
• 10: GPCJ. http://www.seisw.com/GPCJ/GPCJ.html.
• 11: Valery Guralnik , Jaideep Srivastava, Event detection from time series data, Proceedings of the fifth ACM SIGKDD international conference on Knowledge discovery and data mining, p.33-42, August 15-18, 1999, San Diego, California, United States [doi>10.1145/312129.312190]
• 12: Hellerstein, J. M., Hong, W., Madden, S., and Stanek, K. Beyond average: Towards sophisticated sensing with queries. IPSN, 2003.
• 13: 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]
• 14: Intel Lab Data. http://berkeley.intel-research.net/labdata/.
• 15: Kaplan, W. Advanced Calculus. Addison-Wesley, Boston, MA, USA.
• 16: Yannis Kotidis, Snapshot Queries: Towards Data-Centric Sensor Networks, Proceedings of the 21st International Conference on Data Engineering (ICDE'05), p.131-142, April 05-08, 2005 [doi>10.1109/ICDE.2005.134]
• 17: Li, S., Lin, Y., Son, S., Stankovic, J., and Wei, Y. Event detection services using data service middleware in distributed sensor networks. Telecommunication Systems, 26(2--4), 2004.
• 18: 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]
• 19: Samuel Madden , Michael J. Franklin , Joseph M. Hellerstein , Wei Hong, The design of an acquisitional query processor for sensor networks, Proceedings of the 2003 ACM SIGMOD international conference on Management of data, June 09-12, 2003, San Diego, California [doi>10.1145/872757.872817]
• 20: 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]
• 21: Lionel M. Ni , Yunhao Liu , Yiu Cho Lau , Abhishek P. Patil, LANDMARC: indoor location sensing using active RFID, Wireless Networks, v.10 n.6, p.701-710, November 2004 [doi>10.1023/B:WINE.0000044029.06344.dd]
• 22: Joseph O'Rourke, Computational Geometry in C, Cambridge University Press, New York, NY, 1998
• 23: Papadimitriou, S., Brockwell, A., and Faloutsos, C. Adaptive, hands-off stream mining. VLDB, 2003.
• 24: Rahimi, M., Pon, R., Kaiser, W., Sukhatme, G., Estrin, D., and Srivastava, M. Adaptive sampling for environmental robotics. ICRA, 2004.
• 25: Ruppert, D., Wand, M. P., and Carroll, R. J. Semiparametric Regression. Cambridge University Press, New York, NY, USA.
• 26: Ignacio Solis , Katia Obraczka, Ef.cient Continuous Mapping in Sensor Networks Using Isolines, Proceedings of the The Second Annual International Conference on Mobile and Ubiquitous Systems: Networking and Services, p.325-332, July 17-21, 2005 [doi>10.1109/MOBIQUITOUS.2005.26]
• 27: Szewczyk, R., Mainwaring, A., Polastre, J., Anderson J., and Culler, D. Lessons from a sensor network expedition. EWSN, 2004.
• 28: Huanmei Wu , Betty Salzberg , Donghui Zhang, Online event-driven subsequence matching over financial data streams, Proceedings of the 2004 ACM SIGMOD international conference on Management of data, June 13-18, 2004, Paris, France [doi>10.1145/1007568.1007574]
• 29: Yao, Y., and Gehrke, J. Query processing for sensor networks. CIDR, 2003.

INDEX TERMS

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

General Terms:
Algorithms, Design, Experimentation, Performance

Keywords:
contour maps, event detection, patterns, sensor networks