Improved Recovery Management and Routing in W-Grid, a Distributed Infrastructure for Effective and Efficient Multidimensional Data Management over Wireless Ad-Hoc Sensor Networks - Data Management in Cloud, Grid and P2P Systems - page 75

Fig. 1. Correspondence Among Coordinates and Multi-Dimensional Data Space Par-
titions
2 W-Grid Overview
From now on we will refer at devices with the terms sensors or nodes indis-
tinctly. Basically W-Grid can be viewed as a binary tree index cross-layering
both routing and data management features in that, (1) implicitly generating
coordinates and relations among nodes allows ecient message routing and, at
the same time, (2) the coordinates determine a data indexing space partition for
the management of multi-dimensional data. Each node has one or more virtual
coordinates on which an order relation is defined and through which the routing
occurs, and at the same time each virtual coordinate represents a portion of the
data indexing space for which a device is assigned the management responsi-
bility. Differently from algorithms based on geographic routing, W-Grid routing
is not affected by dead-ends. Since in sensor networks the most important op-
erations are data gathering and querying it is necessary to guarantee the best
eciency during these tasks.
While W-Grid architecture and main functionalities have extensively be pre-
sented in [1,2], in this paper we further focus on data management aspects of
W-Grid.
W-Grid distributes data (represented as tuples of attributes) gathered by
sensors or shared by nodes among them in a data-centric manner. Values are
linearized into binary strings (see [24]) and are each stored at the nodes/sensors
whose W-Grid coordinates have the longest common prefix with the resulting
strings. Thus, a W-Grid network acts directly as a distributed database and
coordinates c are used as a roadmap to data repository. This means that each
coordinate represent a portion (i.e. region) of the global data space as depicted
in Figure 1. Regions are generated according to data distribution and the use
of a bucket size for each data region, together with a load balancing algorithm,
allow to balance nodes storage load [17].
Let us describe a brief example of an environment monitoring application in
which sensors survey temperature ( T ) and pressure ( P ), to which we refer as d 1