Mobility Aspects in WSN - Application and Multidisciplinary Aspects of Wireless Sensor Networks - page 119

DSSA is to maximize coverage and to maintain uniformity of node distribution.
Similar to VFA, it uses the concept of virtual force that depends on the internodes
separation distance and local current density ( D n ). In the beginning of the algo-
rithm, the initial density for each node is equal to the number of its neighbors. The
algorithm defines the concept of expected density ( m ) as the average number of
nodes required to cover the entire area, when the nodes are deployed uniformly.
Depending on the forces from the neighboring nodes, a node can decide on its next
movement location. The algorithm works iteratively, and the force of the i -th node
as a result of the j -th node in the n -th step is:

D

i

pp

j

−

i

( )

f

ij ,

=

n

cR p

i

− p

j n n

(6.4)

n 2 n n

µ

j i

pp −

n n

p is location of the i -th
node in the time stamp n . The algorithm terminates when a node moves an infi-
nitely small distance over a period of time or when it moves back and forth between
two same locations (performing stability and oscillation check). DSSA brings the
advantages over the previous two approaches in overcoming the problem of possi-
ble oscillatory sensor behavior. But, it does not consider the possible obstacles, and
assumes that each node knows its location.
One of the techniques that will help terminate the nodes movement in a desirable
fashion (achieving coverage effectiveness) is a Voronoi diagram approach, intro-
duced in [ 22 ]. Here, the nodes move toward coverage holes in the network, thus
providing high coverage with short deploying time and limited movement from
densely to sparsely deployed areas.

i

where cR is the communication range of the sensor, and

6.3.1.2 Voroni Approaches

Many research groups utilize the idea of partitioning the area of interest into Voroni
polygons when building algorithms for sensors self-deployment and relocation.
The Voronoi diagram of a collection of nodes partitions the space into polygons,
where every node (sensor) is enclosed in its own polygon. Every point in a given
polygon is closer to the node in its polygon than the sensors positioned elsewhere.
Thus, if a sensor cannot detect the expected phenomenon, no other sensor can
detect it, and then each sensor is responsible for the sensing task in its Voronoi
polygon. In this way, each sensor can examine the coverage hole locally (Fig. 6.4 ).
The objective of the approaches for sensor movements, which use Voroni
diagrams, is to minimize the sensors' local uncovered areas. This is executed by
iteratively aligning their Voronoi regions with their sensing range. The Voronoi-
based algorithms differ in their arrangement methods. In [ 21 ], a node moves to the
point that maximizes a utility metric defined as the product of the node's effective
area and the node's estimated lifetime, while in [ 22 ], the best possible improvements
are achieved when the nodes move half of the communication range toward their