Load-balanced data-management protocols for sensor networks

MOHAMED ALY (Pitt/CS)

PhD Defense

Monday, June 18th, 2007
2:00pm - SENSQ 5317

Abstract

Sensor networks will shortly consist of globally deployed sensors providing real-time information, e.g. traffic information and restaurant occupancies, to Internet and mobile users. Particularly, users with mobile devices will issue ad-hoc queries usually from within, or nearby, the queried area. The emergence of this type of queries will increase the popularity of in-network Data-Centric Storage (DCS), where sensor readings are temporarily stored in the sensor caches and directly used to answer ad-hoc queries. Two main problems arising in this network model
are: storage hotspots and query hotspots. Storage hotspots are formed when many sensor readings are mapped for storage to a relatively small number of sensors. Similarly, query hotspots occur when many user queries target a small number of sensors. Both types of hotspots are hard to expect due to the difficulty of anticipating the distributions of both, the sensor readings and the user queries, prior to the network operation.
Both problems result in decreasing the Quality of Data (QoD) of the sensor network and increasing node deaths, lead to network partitioning, and subsequently reducing the network lifetime.

In this work, we present a variety of load-balancing schemes to deal with storage and query hotspots for different sensor network settings. Our schemes balance load among sensors on three levels: the packet level, the sensor-readings level, and the user-queries level. For the packet level load-balancing, we present the concept of oblivious routing and use it to design a packet-level load-balancing scheme to run on top of any point-to-point routing protocol. On the sensor-readings level, we first present Zone Sharing (ZS), a local storage hotspot detection and decomposition scheme and then present the K-D tree based Data-Centric Storage (KDDCS), a fully load-balanced DCS scheme. For query hotspots arising in DCS schemes, we present Zone Partitioning/Zone Partial Replication (ZP/ZPR), two local query hotspot detection and decomposition schemes. To decompose query hotspots in general sensor networks, we propose the Content-Based Load-Balancing scheme (CBLB) working on the user-queries level. Furthermore, we propose a Spatio-Temporal DCS scheme (STDCS) that load-balances query hotspots by working on both, the sensor-readings and the user-queries levels, and exploiting the spatio-temporal characteristics of sensor readings and queries, respectively. We have experimentally evaluate the performance of our protocols using simulations in terms of energy saving and QoD.

Dissertation CO-AdviserS

Prof. Panos K. Chrysanthis, Department of Computer Science
Prof. Kirk Pruhs, Department of Computer Science

Committee Members

Prof. Phillip Gibbons, Intel Research Pittsburgh
Prof. Taieb Znati, Department of Computer Science