Spatial queries in sensor networks

ABSTRACT

Recent advances in low-power sensing devices coupled with the widespread availability of wireless ad-hoc networks have fueled the development of sensor networks. These are typically deployed over wide areas to gather data in the environment and monitor events of interest. The ability to run spatial queries is extremely useful for sensor networks. Spatial query execution has been extensively studied in the context of centralized spatial databases; however because of the energy and bandwidth limitation of sensor nodes these solutions are not directly applicable to the sensor network. In this paper we propose a scalable and distributed way of spatial query execution in sensor networks. We develop a distributed spatial index over the sensor nodes that is used in processing spatial queries in a distributed fashion. We evaluate the behavior of our approach and show that our mechanism provides an efficient and scalable way to run spatial queries over sparse and dense sensor networks.

REFERENCES

• 1: Chalermek Intanagonwiwat , Ramesh Govindan , Deborah Estrin , John Heidemann , Fabio Silva, Directed diffusion for wireless sensor networking, IEEE/ACM Transactions on Networking (TON), v.11 n.1, p.2-16, February 2003 [doi>10.1109/TNET.2002.808417]
• 2: O. D. Sahin , A. Gupta , D. Agrawal , A. El Abbadi, A Peer-to-peer Framework for Caching Range Queries, Proceedings of the 20th International Conference on Data Engineering, p.165, March 30-April 02, 2004
• 3: Murat Demirbas , Hakan Ferhatosmanoglu, Peer-to-Peer Spatial Queries in Sensor Networks, Proceedings of the 3rd International Conference on Peer-to-Peer Computing, p.32, September 01-03, 2003
• 4: B. Zheng, J. Xu, W. C. Lee, and D. L. Lee: Grid-Partition Index: A Hybrid Ap-proach to Nearest-Neighbor Queries in Wireless Location-Based Services, VLDB Journal, 2004.
• 5: 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]
• 6: Haibo Hu , Jianliang Xu , Wing Sing Wong , Baihua Zheng , Dik Lun Lee , Wang-Chien Lee, Proactive Caching for Spatial Queries in Mobile Environments, Proceedings of the 21st International Conference on Data Engineering (ICDE'05), p.403-414, April 05-08, 2005 [doi>10.1109/ICDE.2005.113]
• 7: 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]
• 8: 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
• 9: Wendi Rabiner Heinzelman , Anantha Chandrakasan , Hari Balakrishnan, Energy-Efficient Communication Protocol for Wireless Microsensor Networks, Proceedings of the 33rd Hawaii International Conference on System Sciences-Volume 8, p.8020, January 04-07, 2000
• 10: Anirban Mondal , Masaru Kitsuregawa , Beng Chin Ooi , Kian Lee Tan, R-tree-based data migration and self-tuning strategies in shared-nothing spatial databases, Proceedings of the 9th ACM international symposium on Advances in geographic information systems, November 09-10, 2001, Atlanta, Georgia, USA [doi>10.1145/512161.512169]
• 11: Nick Koudas , Christos Faloutsos , Ibrahim Kamel, Declustering Spatial Databases on a Multi-Computer Architecture, Proceedings of the 5th International Conference on Extending Database Technology: Advances in Database Technology, p.592-614, March 25-29, 1996
• 12: B. Schnitzer and S.T. Leutenegger. Master-client T-trees: A new parallel R-tree architecture. Technical Report COMP -98-01, Univeristy of Denver, 1998.
• 13: Yi-Min Wang , Wilf Russell , Anish Arora , Rajesh Jagannathan , Jun Xu, Towards Dependable Home Networking: An Experience Report, Proceedings of the 2000 International Conference on Dependable Systems and Networks (formerly FTCS-30 and DCCA-8), p.43-48, June 25-28, 2000
• 14: Ben Y. Zhao , John D. Kubiatowicz , Anthony D. Joseph, Tapestry: An Infrastructure for Fault-tolerant Wide-area Location and, University of California at Berkeley, Berkeley, CA, 2001
• 15: Antonin Guttman, R-trees: a dynamic index structure for spatial searching, Proceedings of the 1984 ACM SIGMOD international conference on Management of data, June 18-21, 1984, Boston, Massachusetts
• 16: Norbert Beckmann , Hans-Peter Kriegel , Ralf Schneider , Bernhard Seeger, The R*-tree: an efficient and robust access method for points and rectangles, Proceedings of the 1990 ACM SIGMOD international conference on Management of data, p.322-331, May 23-26, 1990, Atlantic City, New Jersey, United States
• 17: Timos K. Sellis , Nick Roussopoulos , Christos Faloutsos, The R+-Tree: A Dynamic Index for Multi-Dimensional Objects, Proceedings of the 13th International Conference on Very Large Data Bases, p.507-518, September 01-04, 1987
• 18: Artur Andrzejak , Zhichen Xu, Scalable, Efficient Range Queries for Grid Information Services, Proceedings of the Second International Conference on Peer-to-Peer Computing, p.33, September 05-07, 2002
• 19: A. Gupta, D. Agrawal and A. El Abbadi. Approximate range selection queries in peer-to-peer systems. CIDR 2003, Asilomar, CA.
• 20: D. A. Coffin, D. J. Van Hook, S. M. McGarry, and S. R. Kolek. Declarative ad hoc sensor networking. SPIE Integrated Command Environments Conf., San Diego, CA 2000.
• 21: Young-Bae Ko , Nitin H. Vaidya, Location-aided routing (LAR) in mobile ad hoc networks, Proceedings of the 4th annual ACM/IEEE international conference on Mobile computing and networking, p.66-75, October 25-30, 1998, Dallas, Texas, United States [doi>10.1145/288235.288252]
• 22: Victor Shnayder , Mark Hempstead , Bor-rong Chen , Geoff Werner Allen , Matt Welsh, Simulating the power consumption of large-scale sensor network applications, Proceedings of the 2nd international conference on Embedded networked sensor systems, November 03-05, 2004, Baltimore, MD, USA [doi>10.1145/1031495.1031518]
• 23: Yufei Tao , Dimitris Papadias, Spatial queries in dynamic environments, ACM Transactions on Database Systems (TODS), v.28 n.2, p.101-139, June 2003 [doi>10.1145/777943.777944]

INDEX TERMS

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

General Terms:
Algorithms

Keywords:
sensor networks, spatial indices, spatial queries