Multi-dimensional range queries in sensor networks

ABSTRACT

In many sensor networks, data or events are named by attributes. Many of these attributes have scalar values, so one natural way to query events of interest is to use a multi-dimensional range query. An example is: "List all events whose temperature lies between 50° and 60°, and whose light levels lie between 10 and 15." Such queries are useful for correlating events occurring within the network.In this paper, we describe the design of a distributed index that scalably supports multi-dimensional range queries. Our distributed index for multi-dimensional data (or DIM) uses a novel geographic embedding of a classical index data structure, and is built upon the GPSR geographic routing algorithm. Our analysis reveals that, under reasonable assumptions about query distributions, DIMs scale quite well with network size (both insertion and query costs scale as O(√N)). In detailed simulations, we show that in practice, the insertion and query costs of other alternatives are sometimes an order of magnitude more than the costs of DIMs, even for moderately sized network. Finally, experiments on a small scale testbed validate the feasibility of DIMs.

References

1. James Aspnes and Gauri Shah. Skip Graphs. In Proceedings of 14th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), Baltimore, MD, January 2003.]]
2. J. L. Bentley. Multidimensional Binary Search Trees Used for Associative Searching. Communicaions of the ACM, 18(9):475--484, 1975.]]
3. P. Bonnet, J. E. Gerhke, and P. Seshadri. Towards Sensor Database Systems. In Proceedings of the Second International Conference on Mobile Data Management, Hong Kong, January 2001.]]
4. I. Clarke, O. Sandberg, B. Wiley, and T. W. Hong. Freenet: A Distributed Anonymous Information Storage and Retrieval System. In Designing Privacy Enhancing Technologies: International Workshop on Design Issues in Anonymity and Unobservability. Springer, New York, 2001.]]
5. D. Comer. The Ubiquitous B-tree. ACM Computing Surveys, 11(2):121--137, 1979.]]
6. R. A. Finkel and J. L. Bentley. Quad Trees: A Data Structure for Retrieval on Composite Keys. Acta Informatica, 4:1--9, 1974.]]
7. D. Ganesan, D. Estrin, and J. Heidemann. DIMENSIONS: Why do we need a new Data Handling architecture for Sensor Networks? In Proceedings of the First Workshop on Hot Topics In Networks (HotNets-I), Princeton, NJ, October 2002.]]
8. A. Gionis, P. Indyk, and R. Motwani. Similarity Search in High Dimensions via Hashing. In Proceedings of the 25th VLDB conference, Edinburgh, Scotland, September 1999.]]
9. R. Govindan, J. Hellerstein, W. Hong, S. Madden, M. Franklin, and S. Shenker. The Sensor Network as a Database. Technical Report 02-771, Computer Science Department, University of Southern California, September 2002.]]
10. B. Greenstein, D. Estrin, R. Govindan, S. Ratnasamy, and S. Shenker. DIFS: A Distributed Index for Features in Sensor Networks. In Proceedings of 1st IEEE International Workshop on Sensor Network Protocols and Applications, Anchorage, AK, May 2003.]]
11. A. Guttman. R-trees: A Dynamic Index Structure for Spatial Searching. In Proceedings of the ACM SIGMOD, Boston, MA, June 1984.]]
12. M. Harren, J. M. Hellerstein, R. Huebsch, B. T. Loo, S. Shenker, and I. Stoica. Complex Queries in DHT-based Peer-to-Peer Networks. In P. Druschel, F. Kaashoek, and A. Rowstron, editors, Proceedings of 1st International Workshop on Peer-to-Peer Systems (IPTPS'02), volume 2429 of LNCS, page 242, Cambridge, MA, March 2002. Springer-Verlag.]]
13. P. Indyk and R. Motwani. Approximate Nearest Neighbors: Towards Removing the Curse of Dimensionality. In Proceedings of the 30th Annual ACM Symposium on Theory of Computing, Dallas, Texas, May 1998.]]
14. P. Indyk, R. Motwani, P. Raghavan, and S. Vempala. Locality-preserving Hashing in Multidimensional Spaces. In Proceedings of the 29th Annual ACM symposium on Theory of Computing, pages 618--625, El Paso, Texas, May 1997. ACM Press.]]
15. C. Intanagonwiwat, R. Govindan, and D. Estrin. Directed Diffusion: A Scalable and Robust Communication Paradigm for Sensor Networks. In Proceedings of the Sixth Annual ACM/IEEE International Conference on Mobile Computing and Networking (Mobicom 2000), Boston, MA, August 2000.]]
16. B. Karp and H. T. Kung. GPSR: Greedy Perimeter Stateless Routing for Wireless Networks. In Proceedings of the Sixth Annual ACM/IEEE International Conference on Mobile Computing and Networking (Mobicom 2000), Boston, MA, August 2000.]]
17. S. Madden, M. Franklin, J. Hellerstein, and W. Hong. The Design of an Acquisitional Query Processor for Sensor Networks. In Proceedings of ACM SIGCMOD, San Diego, CA, June 2003.]]
18. S. Madden, M. J. Franklin, J. M. Hellerstein, and W. Hong. TAG: a Tiny AGregation Service for Ad-Hoc Sensor Networks. In Proceedings of 5th Annual Symposium on Operating Systems Design and Implementation (OSDI), Boston, MA, December 2002.]]
19. S. Ratnasamy, P. Francis, M. Handley, R. Karp, and S. Shenker. A Scalable Content-Addressable Network. In Proceedings of the ACM SIGCOMM, San Diego, CA, August 2001.]]
20. S. Ratnasamy, B. Karp, L. Yin, F. Yu, D. Estrin, R. Govindan, and S. Shenker. GHT: A Geographic Hash Table for Data-Centric Storage. In Proceedings of the First ACM International Workshop on Wireless Sensor Networks and Applications, Atlanta, GA, September 2002.]]
21. H. Samet. Spatial Data Structures. In W. Kim, editor, Modern Database Systems: The Object Model, Interoperability and Beyond, pages 361--385. Addison Wesley/ACM, 1995.]]
22. Karim Sead, Ahmed Helmy, and Ramesh Govindan. On the Effect of Localization Errors on Geographic Face Routing in Sensor Networks. In Under submission, 2003.]]
23. Scott Shenker, Sylvia Ratnasamy, Brad Karp, Ramesh Govindan, and Deborah Estrin. Data-Centric Storage in Sensornets. In Proc. ACM SIGCOMM Workshop on Hot Topics In Networks, Princeton, NJ, 2002.]]
24. I. Stoica, R. Morris, D. Karger, M. F. Kaashoek, and H. Balakrishnan. Chord: A Scalable Peer-To-Peer Lookup Service for Internet Applications. In Proceedings of the ACM SIGCOMM, San Diego, CA, August 2001.]]
25. F. Ye, H. Luo, J. Cheng, S. Lu, and L. Zhang. A Two-Tier Data Dissemination Model for Large-scale Wireless Sensor Networks. In Proceedings of the Eighth Annual ACM/IEEE International Conference on Mobile Computing and Networking(Mobicom'02), Atlanta, GA, September 2002.]]

Index Terms

• Computer systems organization

  • Architectures

    • Distributed architectures

  • Embedded and cyber-physical systems

  • Real-time systems

• Software and its engineering

  • Software organization and properties

    • Software system structures

      • Distributed systems organizing principles