Geographic Management of Data in Infrastructureless Environments

NSF Grant 0209190

PI: Ouri Wolfson

University of Illinois, Chicago

Project Summary

In this project we propose to study databases that are distributed among a set of possibly mobile sensors that communicate without a fixed network infrastructure. This architecture is motivated by new types of emerging wireless broadcast networks such as Mobile Ad-hoc Networks, and "smart dust" and sensor networks. Smart dust and sensor networks consist of processors that may be the size of a dust particle, and the processors may be parachuted or sprayed from an airplane.

We consider two environments. The first is a database distributed among a set of static sensors. The database may render a global picture of an unknown terrain from local images collected by individual sensors. The problem that arises here in processing queries is that a node in the network doesn't know exactly what other nodes are alive, their id, or their location. The second environment is a MANET, where the nodes' identifications are known, but the location of each node is unknown at any point in time. Our idea of processing queries in each one of the two cases is captured by the following "geographic dissemination of data" paradigm. It calls for partitioning the geographic area into cells. Each data item in the database is associated with a cell, and resides in that cell, i.e. in the processors that are located in the cell at a particular time. Each grid cell is considered a node of the distributed database, and queries are processed by sending them to the appropriate grid cell. In static sensor networks the sensors responding are the sensors in the cell. In MANET's each data item is associated with a grid cell, and is stored at some or all of the mobile nodes that are currently in the cell. Nodes are mobile, thus they may enter and exit a cell. Since the data belongs to a cell, a node that exits a cell hands-off the cell data to other mobile nodes that are currently in the cell. The nodes that are responding to a query arriving in a cell are the ones that are currently in the cell.

We evaluate this geographic partitioning idea on an application/database for each environment. In the static environment the database consists of sensor data (e.g. images) of the whole geographic area covered by the sensors, and a query may arrive at any sensor and request to view any part of the area. In the dynamic environment each mobile node stores its motion plan, or trajectory, and the queries issued by the mobile nodes are spatio-temporal range queries such as: "Display the mobile units (e.g. friendly helicopters) that are expected to enter region R within the next ten minutes".