DIM for sensor networks
Overview
In wireless sensor networks, data or events will be named by attributes. Many of these attributes will have scalar values such as temperature, light levels, soil moisture conditions, to name a few. In these systems, one natural way to query for events of interest will be to use multi-dimensional range queries on these attributes. For example, scientists analyzing the growth of marine micro-organisms might be interested in events that occurred within certain temperature and light conditions: ``List all events that have temperatures between 50° F and 60° F , and light levels between 10 and 20''. Such range queries can be used in two distinct ways. They can help users efficiently drill-down their search for events of interest. The query described above illustrates this, where the scientist is presumably interested in discovering, and perhaps mapping the combined effect of temperature and light on the growth of marine micro-organisms. More importantly, they can be used by applications running within a sensor network for correlating events and triggering actions. For example, if in a habitat monitoring application, a bird alighting on its nest is indicated by a certain range of thermopile sensor readings, and a certain range of microphone readings, a multi-dimensional range query on those attributes enables higher confidence detection of the arrival of a flock of birds, and can trigger a system of cameras.
In traditional database systems, such range queries are supported using pre-computed indices. Indices trade-off some initial pre-computation cost to achieve a significantly more efficient querying capability. For sensor networks, a centralized index for multi-dimensional range queries may not be feasible for reasons such as energy-efficiency, network capacity, fault tolerance, etc. Rather, there will be situations when it is appropriate to build an in-network distributed data structure for efficiently answering multi-dimensional range queries.
In this project we are working on the design and implementation of a Distributed Index for Multi-dimensional data or DIM, as we call it. DIM leverages two key ideas: in-network data centric storage and locality-preserving geographic hashing.
Papers
- Xin Li, Young Jin Kim, Ramesh Govindan, and Wei Hong. Multi-dimensional Range Queries in Sensor Networks. In: Proceedings of the ACM Conference on Embedded Networked Sensor Systems. Los Angeles, CA. 5-7 November 2003.
- Ramakrishna Gummadi, Xin Li, Ramesh Govindan, Cyrus Shahabi, and Wei Hong. Energy-efficient Data Organization an Query Processing in Sensor Networs. In: SIGBED Review, Vol. 2, No. 1. January 2005.
- Xin Li, Fang Bian, Ramesh Govindan, and Wei Hong. Rebalancing Distributed Data Storage in Sensor Networks. Technical Report USC CS 05-852.
Posters
- Xin Li, Young Jin Kim, Ramesh Govindan, and Wei Hong. Distributed Indexing for Multi-dimensional data in sensor networks. In: Posters of the Open House of Intel Research Berkeley. Berkeley, CA. 30 September 2003.
- Xin Li, Young Jin Kim, Ramesh Govindan, and Wei Hong. Distributed Indexing for Multi-dimensional data in sensor networks. In: Posters of the 1st Annual Research Review of CENS. Los Angeles, CA. 10 October 2003.
- Xin Li, Young Jin Kim, Ramesh Govindan, and Wei Hong. Distributed Indexing for Multi-dimensional data in sensor networks. In: Posters of the ACM Conference on Embedded Networked Sensor Systems. Los Angeles, CA. 5 November 2003.
- Ramakrishna Gummadi, Xin Li, Ramesh Govindan, Cyrus Shahabi, and Wei Hong. Energy-efficient Data Organization an Query Processing in Sensor Networs. In: Posters of the ACM Conference on Embedded Networked Sensor Systems. Baltimore, MD. 3-5 November 2004.
Talks
- Xin Li. Sensys'03 conference talk. Los Angeles, CA. 5 November 2003.
Software
ns-2 Simulation Code
This package contains the source DIM simulation code including DIM, GHT, TREE (flooding), and corresponding changes the user need to make to the original ns-2 distribution. The code presented here works with ns-2.26, ns-2.27, and ns-2.29.A simulation scenario can be found here.
Mote Implementation Code
Contact
Please email to
Last Modified: 28 Feb 2006