Welcome to the ADMT Publication Server

KDDCS: a load-balanced in-network data-centric storage scheme for sensor networks

DocUID: 2006-016 Full Text: PDF

Author: Mohamed Aly, Kirk Pruhs, Panos K. Chrysanthis

Abstract: We propose an In-Network Data-Centric Storage (INDCS) scheme for answering ad-hoc queries in sensor networks. Previously proposed In-Network Storage (INS) schemes suffered from Storage Hot-Spots that are formed if either the sensors' locations are not uniformly distributed over the coverage area, or the distribution of sensor readings is not uniform over the range of possible reading values. Our K-D tree based Data-Centric Storage (KDDCS) scheme maintains the invariant that the storage of events is distributed reasonably uniformly among the sensors. KDDCS is composed of a set of distributed algorithms whose running time is within a poly-log factor of the diameter of the network. The number of messages any sensor has to send, as well as the bits in those messages, is poly-logarithmic in the number of sensors. Load balancing in KDDCS is based on defining and distributively solving a theoretical problem that we call the Weighted Split Median problem. In addition to analytical bounds on KDDCS individual algorithms, we provide experimental evidence of our scheme's general efficiency, as well as its ability to avoid the formation of storage hot-spots of various sizes, unlike all previous INDCS schemes.

Keywords: Sensor Network, Power-Aware, Distributed Algorithms

Published In: Proc. of Conference on Information and Knowledge Management

ISBN: 1-59593-433-2

Pages: pp. 317-326

Place Published: Arlington, VA

Year Published: 2006

Note: DOI:10.1145/1183614.1183662

Project: QSense Subject Area: Sensor Databases

Publication Type: Conference Paper

Sponsor: NSF ITR ANI-0325353

Citation:Text Latex BibTex XML Mohamed Aly, Kirk Pruhs, and Panos K. Chrysanthis. KDDCS: a load-balanced in-network data-centric storage scheme for sensor networks. Proc. of Conference on Information and Knowledge Management. pp. 317-326. 2006. Arlington, VA. (Note: DOI:10.1145/1183614.1183662).