Scoop : an adaptive indexing scheme for stored data in sensor networks

We present the design of Scoop, a system that is designed to efficiently store and query relational data collected by nodes in a bandwidth-constrained sensor network. Sensor networks allow remote environments to be monitored at very fine levels of granularity; often such monitoring deployments generate large amounts of data which may be impractical to collect due to bandwidth limitations, but which can easily stored in-network for some period of time. Existing approaches to querying stored data in sensor networks have typically assumed that all data either is stored locally, at the node that produced it, or is hashed to some location in the network using a predefined uniform hash function. These two approaches are at the extremes of a trade-off between storage and query costs. In the former case, the costs of storing data ate low, since no transmissions are required, but queries must flood the entire network. In the latter case, some queries can be executed efficiently by using the hash function to find the nodes of interest, but storage is expensive as readings must be transmitted to some (likely far away) location in the network. In contrast, Scoop monitors changes in the distribution of sensor readings, queried values, and network connectivity to determine the best location to store data. We formulate this as an optimization problem and present a practical algorithm that solves this problem in Scoop. We have built a complete implementation of Scoop for TinyOS mote [1] sensor network hardware and evaluated its performance on a 60-node testbed and in the TinyOS simulator, TOSSIM. Our results show that Scoop not only provides substantial performance benefits over alternative approaches on a range of data sets, but is also able to efficiently adapt to changes in the distribution and rates of data and queries.

Department dc:contributor.department

Massachusetts Institute of Technology. Dept. of Electrical Engineering and Computer Science.

Grantor dc:publisher

Massachusetts Institute of Technology

Year dc:date.issued

2007

Author dc:creator

• Gil, Thomer M. (Thomer Michael)

Advisor dc:contributor.advisor

• Samuel Madden.

• Electrical Engineering and Computer Science.

Statement dc:rights

• M.I.T. theses are protected by copyright. They may be viewed from this source for any purpose, but reproduction or distribution in any format is prohibited without written permission. See provided URL for inquiries about permission.

Licence dc:rights.uri

• http://dspace.mit.edu/handle/1721.1/7582

Language dc:language.iso

eng

Handle dc:identifier.uri

http://hdl.handle.net/1721.1/42249

OAI identifier oai:identifier

oai:dspace.mit.edu:1721.1/42249