Robust and Efficient Data Dissemination for Data-Centric Storage
Project Overview
Sensornets will provide detailed measurements at fine spatial granularities over large geographic areas. This unprecedented wealth of data will open a new window on the physical world, enabling scientists to monitor, measure, and, hopefully, understand a range of natural phenomena such as ecosystems, microclimates, building dynamics, and seismic events. However, this understanding will only be realized if scientists can easily and flexibly access sensornet data; providing such access is a formidable challenge because the measured data are distributed across the entire sensornet and communication between sensornet nodes requires substantial expenditures of scarce energy. Thus, reaping the tremendous opportunities afforded by sensornets will require energy-efficient data dissemination algorithms.
Since the nature of the data is more important than the identity of
the node that gathers them, data-centric abstractions are now
seen as a fundamental aspect of sensornet design. The first work in
this area focused on data-centric routing methods such as
directed diffusion and TAG.
These techniques, while extremely efficient at conveying data to the
desired location, require flooding the initial query to the entire sensornet. To reduce query cost, an alternative approach to data dissemination,
called data-centric storage, has been
proposed. Data-centric storage methods
do not require flooding of queries, but incur additional costs
while initially storing the data. Data-centric routing and
data-centric storage provide complementary functions, and their union
would give sensornets a broad range of energy-efficient functionality.
However, these approaches differ in one crucial respect: data-centric
routing requires little of the underlying routing system, while
data-centric storage makes exacting demands on its routing
infrastructure. In particular, data-centric storage is predicated on
a robust and efficient routing primitive that allows storing data by
name at a node in the sensornet.
Our project seeks to investigate the design and development of geographic hash tables (GHTs), a routing primitive for data-centric storage. GHTs bring together two technologies, distributed hash tables (DHTs) and geographic ad-hoc routing, that were developed in two completely unrelated contexts, peer-to-peer systems and ad hoc wireless networks. Each technology has been extensively explored in its respective domain, but the combination of these technologies in the new, and more challenging, context of sensor networks raises many new design challenges. Moreover, GHT, and its underlying routing algorithm GPSR, have not been tested in real-world conditions. The proposed work falls into two categories:
- Exploring the design space of the required data dissemination algorithms
- Prototyping these algorithms to obtain a more realistic evaluation of their properties
Faculty
Students and Staff
- Fang Bian
- Rodrigo Fonseca
- Young Jin Kim
- Jerry Zhao (postdoc)
Talks and Publications
Young-Jin Kim, Ramesh Govindan, Brad Karp, Scott Shenker, Geographic Routing Made Practical, In: Proceedings of the USENIX Symposium on Networked Systems Design and Implementation, USENIX, Boston, Massachusetts, USA, May 2005. [PDF]
Fang Bian, Xin Li, Ramesh Govindan, Scott Shenker, Using Hierarchical Location Names for Scalable Routing and Rendezvous in Wireless Sensor Networks, In: International Journal of Ad Hoc and Ubiquitous Computing, special issue on wireless sensor networks, 2005.
Ramakrishna Gummadi, Nupur Kothari, Young-Jin Kim, Ramesh Govindan, Brad Karp, Scott Shenker, Reduced State Routing in the Internet, In: Proceedings of Hotnets-III, 2004. [PDF]