Management and routing algorithms for ad-hoc and sensor networks
Creators: name: Monti, Gabriele <1978>
Publisher: name: Alma Mater Studiorum - Università di Bologna
Year: 2008
Subjects: ING-INF/05 Sistemi di elaborazione delle informazioni

description: Large scale wireless adhoc
networks of computers, sensors, PDAs etc. (i.e. nodes) are
revolutionizing connectivity and leading to a paradigm shift from centralized systems to highly
distributed and dynamic environments. An example of adhoc
networks are sensor networks, which
are usually composed by small units able to sense and transmit to a sink elementary data which are
successively processed by an external machine. Recent improvements in the memory and
computational power of sensors, together with the reduction of energy consumptions, are rapidly
changing the potential of such systems, moving the attention towards datacentric
sensor networks.
A plethora of routing and data management algorithms have been proposed for the network path
discovery ranging from broadcasting/floodingbased
approaches to those using global positioning
systems (GPS).
We studied WGrid,
a novel decentralized infrastructure that organizes wireless devices in an adhoc
manner, where each node has one or more virtual coordinates through which both message routing
and data management occur without reliance on either flooding/broadcasting operations or GPS.
The resulting adhoc
network does not suffer from the deadend
problem, which happens in
geographicbased
routing when a node is unable to locate a neighbor closer to the destination than
itself.
WGrid
allow multidimensional
data management capability since nodes' virtual coordinates can
act as a distributed database without needing neither special implementation or reorganization. Any
kind of data (both single and multidimensional)
can be distributed, stored and managed. We will
show how a location service can be easily implemented so that any search is reduced to a simple
query, like for any other data type.
WGrid
has then been extended by adopting a replication methodology. We called the resulting
algorithm WRGrid.
Just like WGrid,
WRGrid
acts as a distributed database without needing
neither special implementation nor reorganization and any kind of data can be distributed, stored
and managed. We have evaluated the benefits of replication on data management, finding out, from
experimental results, that it can halve the average number of hops in the network. The direct
consequence of this fact are a significant improvement on energy consumption and a workload
balancing among sensors (number of messages routed by each node). Finally, thanks to the
replications, whose number can be arbitrarily chosen, the resulting sensor network can face sensors
disconnections/connections, due to failures of sensors, without data loss.
Another extension to {WGrid}
is {W*Grid}
which extends it by strongly improving network
recovery performance from link and/or device failures that may happen due to crashes or battery
exhaustion of devices or to temporary obstacles.
W*Grid
guarantees, by construction, at least two disjoint paths between each couple of nodes. This
implies that the recovery in W*Grid
occurs without broadcasting transmissions and guaranteeing
robustness while drastically reducing the energy consumption. An extensive number of simulations
shows the efficiency, robustness and traffic road of resulting networks under several scenarios of
device density and of number of coordinates. Performance analysis have been compared to existent
algorithms in order to validate the results.