In-network execution of monitoring queries in sensor networks

ABSTRACT

Sensor networks are widely used in many applications for collecting information from the physical environment. In these applications, it is usually necessary to track the relationships between sensor data readings within a time window to detect events of interest. However, it is difficult to detect such events by using the common aggregate or selection queries. We address the problem of processing window self-join in order to detect events of interest. Self-joins are useful in tracking correlations between different sensor readings, which can indicate an event of interest. We propose the Two-Phase Self-Join (TPSJ) scheme to efficiently evaluate self-join queries for event detection in sensor networks. Our TPSJ scheme takes advantage of the properties of the events and carries out data filtering during in-network processing. We discuss TPSJ execution with one window and we extend it for continuous event monitoring. Our experimental evaluation results indicate that the TPSJ scheme is effective in reducing the amount of radio transmissions during event detection.

REFERENCES

• 1: D. J. Abadi, S. Madden, and W. Lindner. Reed: Robust, efficient filtering and event detection in sensor networks. In VLDB, 2005.
• 2: B. Babcock, S. Babu, M. Datar, R. Motwani, and J. Widom. Models and issues in data stream systems. In PODS, 2002.
• 3: S. Babu, J. W. Kamesh Munagala, and R. Motwani. Adaptive caching for continuous queries. In ICDE, 2005.
• 4: V. Chowdhary and H. Gupta. Communication-efficient implementation of join in sensor networks. In DASFAA, 2005.
• 5: J. Considine, F. Li, G. Kollios, and J. Byers. Approximate aggregation techniques for sensor databases. In ICDE, 2004.
• 6: A. Deligiannakis, Y. Kotidis, and N. Roussopoulos. Hierarchical in-network data aggregation with quality guarantees. In EDBT, 2004.
• 7: A. Deshpande, C. Guestrin, S. Madden, J. M. Hellerstein, and W. Hong. Model-driven data acquisition in sensor networks. In VLDB, 2004.
• 8: L. Golab and M. T. Özsu. Processing sliding window multi-joins in continuous queries over data streams. In VLDB, 2003.
• 9: M. A. Hammad, W. G. Aref, and A. K. Elmagarmid. Stream join: Tracking moving objects in sensor-network databases. In SSDBM, 2003.
• 10: I. Lazaridis and S. Mehrotra. Capturing sensor-generated time series with quality guarantees. In ICDE, 2003.
• 11: Q. Li and D. Rus. Global clock synchronization in sensor networks. In INFOCOM, 2004.
• 12: S. Madden, M. Franklin, J. Hellerstein, and W. Hong. Tinydb: An acquisitional query processing system for sensor networks. In TODS, 2005.
• 13: S. R. Madden, M. A. Shah, J. M. Hellerstein, and V. Raman. Continuously adaptive continuous queries over streams. In SIGMOD, 2002.
• 14: U. Srivastava, K. Munagala, and J. Widom. Operator placement for in-network stream query processing. In PODS, 2005.
• 15: S. Xiang, H. Lim, K. L. Tan, and Y. Zhou. Two-tier multiple query optimization for sensor networks. In ICDCS, 2007.
• 16: Y. Yao and J. Gehrke. Query processing for sensor networks. In CIDR, 2003.

INDEX TERMS

Primary Classification:
  H. Information Systems
  H.3 INFORMATION STORAGE AND RETRIEVAL
      H.3.3 Information Search and Retrieval
          Subjects: Information filtering

General Terms:
Experimentation, Performance

Keywords:
self-join queries, sensor networks