Database Reference
In-Depth Information
of devices). For these reasons our solution does not rely on GPS or any other
positioning system. The routing problem has also been addressed in cases of
both total absence and partial availability of geographic location information by
generating virtual coordinates to approximate real ones. Our solution may be
classified within this set of approaches in that it also uses virtual coordinates,
but it is different in that it does not aim to approximate real coordinates, but
rather it
simulates
them.
W-Grid [1,2] is a distributed binary tree index cross-layering both routing and
data management features, in that (1) it allows ecient message routing and,
at the same time, (2) the virtual 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 by content occurs; each virtual coordinate represents a portion of the
data indexing space for which a device is assigned the management responsibility.
A consequence of this approach is that nodes which are close in the physical
network topology are also close in the logical overlay network.
In this paper we focus on data management aspects of W-Grid, and we in-
troduce (i) a new recovery method that does not require broadcast messages
and (ii) a new routing approach based on a local learning method that improves
also the trac balancing among nodes without affecting energy consumptions.
The solution does not require GPS because each device receives a virtual co-
ordinate reflecting its local connectivity with other neighbor devices and each
of them uses this information to perform routings and to search for data; the
data management is performed natively, namely in a cross-layer fashion, thanks
to the fact that each device receives a set of unique virtual coordinates, each of
which represents also a portion of the data indexing space for which a device is
assigned the management responsibility. We also show that W-Grid is at some
extent robust to sensor failures, meaning that if a sensor or a link crashes or
turns off, neighbor sensors are able to recover the network failure without using
local broadcasting, when physically possible, i.e. when the failure does not cause
the partition into unconnected subnetworks. In this work we consider W-Grid to
be used in wireless ad-hoc and sensor networks, therefore nodes disconnections
are basically represented by failures (e.g. power exhaustion).
With respect to previous work, in [17] we described a preliminary W-Grid
version with routing and data management features, in [22] we introduced data
replication to allow faster content location while in [2] we presented the range
query capability of W-Grid. In [1] we introduced a lazy recovery algorithm to
resolve in background possible routing problems while in [2] the infrastructure
has been extended with reactive recovery capabilities to solve node failures as
soon as they are detected; however, differently from the solution presented in
this paper, both recovery solutions required some broadcast operations. Finally
a preliminary version of routing with learning capability is reported in [23].
Search WWH ::
Custom Search