DIST: a distributed spatio-temporal index structure for sensor networks

ABSTRACT

We consider the general problem of tracking moving objects in sensor networks. The specific application we consider is that of tracking a chemical plume moving over a large infrastructure network. We present a distributed index structure DIST that stores and updates distributed summaries as the plume moves. We present algorithms for range queries on the history of the plume. DIST localizes information with respect to time and space using a hierarchy that scales with the plume size. The highlight of our work is an analytical model to predict the cost of query algorithms based on the query location, query size, and plume's spatio-temporal distribution. Using this model, our adaptive scheme chooses the optimal scheme. Experimental results show that DIST outperforms alternative techniques in query, update, and storage costs, and scales well with the number of plumes.

REFERENCES

• 1: Crossbow Inc. Wireless sensor networks, http://www.xbow.com/.
• 2: V. M. Chernousenko. Chernobyl, Insight from the Inside. Springer-Verlag, 1991.
• 3: K. K. Chintalapudi and R. Govindan. Localized edge detection in a sensor field. SNPA, 2003.
• 4: Adina Crainiceanu , Prakash Linga , Johannes Gehrke , Jayavel Shanmugasundaram, Querying peer-to-peer networks using P-trees, Proceedings of the 7th International Workshop on the Web and Databases: colocated with ACM SIGMOD/PODS 2004, June 17-18, 2004, Paris, France [doi>10.1145/1017074.1017082]
• 5: H. V. Dop, F. T. M. Nieuwstadt, and J. C. R. Hunt. Random walk models for particle displacements in inhomogeneous unsteady turbulent flows. Physics Fluids, 1985.
• 6: R. R. Draxler. Forty-eight hour atmospheric dispersion forecasts at selected locations in the united states. NOAA ERL ARL-100, 1981.
• 7: Deborah Estrin , Ramesh Govindan , John Heidemann , Satish Kumar, Next century challenges: scalable coordination in sensor networks, Proceedings of the 5th annual ACM/IEEE international conference on Mobile computing and networking, p.263-270, August 15-19, 1999, Seattle, Washington, United States [doi>10.1145/313451.313556]
• 8: Bugra Gedik , Kun-Lung Wu , Philip Yu , Ling Liu, Motion adaptive indexing for moving continual queries over moving objects, Proceedings of the thirteenth ACM international conference on Information and knowledge management, November 08-13, 2004, Washington, D.C., USA [doi>10.1145/1031171.1031255]
• 9: 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
• 10: B. Karp and H. T. Kung. GPSR: greedy perimeter stateless routing for wireless networks. MOBICOM, 2003.
• 11: Young-Bae Ko , Nitin H. Vaidya, Geocasting in Mobile Ad Hoc Networks: Location-Based Multicast Algorithms, Proceedings of the Second IEEE Workshop on Mobile Computer Systems and Applications, p.101, February 25-26, 1999
• 12: H. T. Kung and D. Vlah. Efficient location tracking using sensor networks. WCN, 2003.
• 13: J. Li, J. Jannotti, D. DeCouto, D. Karger, and R. Morris. Geographic ad hoc routing. MOBICOM, 2000.
• 14: Qun Li , Michael De Rosa , Daniela Rus, Distributed algorithms for guiding navigation across a sensor network, Proceedings of the 9th annual international conference on Mobile computing and networking, September 14-19, 2003, San Diego, CA, USA [doi>10.1145/938985.939017]
• 15: Xin Li , Young Jin Kim , Ramesh Govindan , Wei Hong, Multi-dimensional range queries in 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.958500]
• 16: 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]
• 17: A. Meka and A. K. Singh. DIST: A Distributed index structure for tracking plumes in sensor networks. UCSB-TechReport, 2005.
• 18: Sylvia Ratnasamy , Paul Francis , Mark Handley , Richard Karp , Scott Schenker, A scalable content-addressable network, Proceedings of the 2001 conference on Applications, technologies, architectures, and protocols for computer communications, p.161-172, August 2001, San Diego, California, United States
• 19: Simonas Šaltenis , Christian S. Jensen , Scott T. Leutenegger , Mario A. Lopez, Indexing the positions of continuously moving objects, Proceedings of the 2000 ACM SIGMOD international conference on Management of data, p.331-342, May 15-18, 2000, Dallas, Texas, United States
• 20: 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]
• 21: Ion Stoica , Robert Morris , David Karger , M. Frans Kaashoek , Hari Balakrishnan, Chord: A scalable peer-to-peer lookup service for internet applications, Proceedings of the 2001 conference on Applications, technologies, architectures, and protocols for computer communications, p.149-160, August 2001, San Diego, California, United States
• 22: Jimeng Sun , Dimitris Papadias , Yufei Tao , Bin Liu, Querying about the Past, the Present, and the Future in Spatio-Temporal Databases, Proceedings of the 20th International Conference on Data Engineering, p.202, March 30-April 02, 2004
• 23: Ouri Wolfson , Bo Xu , Sam Chamberlain , Liqin Jiang, Moving Objects Databases: Issues and Solutions, Proceedings of the 10th International Conference on Scientific and Statistical Database Management, p.111-122, July 01-03, 1998

INDEX TERMS

Primary Classification:
  H. Information Systems
  H.2 DATABASE MANAGEMENT
      H.2.4 Systems
          Subjects: Distributed databases

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

General Terms:
Algorithms, Design

Keywords:
sensor networks, spatio-temporal indexing