Supporting spatial aggregation in sensor network databases

ABSTRACT

Sensor networks are unattended deeply distributed systems whose schema can be conceptualized using the relational model. Aggregation queries on the data sampled at each sensor node are the main means to extract the abstract characteristics of the surrounding environment. However, the non-uniform distribution of the sensor nodes in the environment leads to inaccurate results generated by the aggregation queries. In this paper, we introduce "spatial aggregations" that take into consideration the distribution of the values generated by the sensor nodes. We propose the use of spatial interpolation methods derived from the fields of spatial statistics and computational geometry to answer spatial aggregations. In particular, we study Spatial Moving Average (SMA), Voronoi Diagram and Triangulated Irregular Network (TIN). Investigating these methods for answering spatial average queries, we show that the average value on the data samples weighted by the area of the Voronoi cell of the corresponding sensor node, provides the best precision. Consequently, we introduce an incremental algorithm to compute and maintain the Voronoi cell at each sensor node. To demonstrate the performance of in-network implementation of our algorithm, we have developed prototypes of two different approaches to distributed spatial aggregate processing.

REFERENCES

• 1: Philippe Bonnet , Johannes Gehrke , Praveen Seshadri, Towards Sensor Database Systems, Proceedings of the Second International Conference on Mobile Data Management, p.3-14, January 08-10, 2001
• 2: Ralf Hartmut Güting, An introduction to spatial database systems, The VLDB Journal — The International Journal on Very Large Data Bases, v.3 n.4, October 1994
• 3: 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]
• 4: N. Lam. Spatial Interpolation Methods: A Review. The American Cartographer, 10(2):29--149, 1983.
• 5: 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]
• 6: Atsuyuki Okabe , Barry Boots , Kokichi Sugihara, Spatial tessellations: concepts and applications of Voronoi diagrams, John Wiley & Sons, Inc., New York, NY, 1992
• 7: Ioana Stanoi , Mirek Riedewald , Divyakant Agrawal , Amr El Abbadi, Discovery of Influence Sets in Frequently Updated Databases, Proceedings of the 27th International Conference on Very Large Data Bases, p.99-108, September 11-14, 2001
• 8: W. Tobler. Cellular Geography. In Olsson and Gale, editors, Philosophy in Geography, pages 379--386. D. Reidel Publishing Company, 1979.
• 9: J. Zhao, R. Govindan, and D. Estrin. Computing Aggregates for Monitoring Wireless Sensor Networks. In Proceedings of the First IEEE International Workshop on Sensor Net Protocols and Applications (SNPA'03), 2003.
• 10: Jun Zhang , Manli Zhu , Dimitris Papadias , Yufei Tao , Dik Lun Lee, Location-based spatial queries, Proceedings of the 2003 ACM SIGMOD international conference on Management of data, June 09-12, 2003, San Diego, California [doi>10.1145/872757.872812]

INDEX TERMS

Primary Classification:
  H. Information Systems
  H.2 DATABASE MANAGEMENT
      H.2.8 Database applications
          Subjects: Spatial databases and GIS

Additional Classification:
  H. Information Systems
  H.2 DATABASE MANAGEMENT
      H.2.4 Systems
          Subjects: Distributed databases; Query processing

General Terms:
Algorithms, Design, Performance

Keywords:
aggregation, sensor networks, spatial data stream, spatial interpolation, voronoi cell