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

sensing range

Voroni Diagram

Voroni Cell

Sc

Sc Sc

Se

Sa Sa Sa Sa

Sa

Sd

Sd

Sb Sb Sb Sb

Initial state

After hearing Sb After hearing Sc After hearing Sd After hearing Se

Fig. 6.4 Voroni Diagrams, Voroni Cell, constructing Vorioni diagrams

furthest Voronoi vertexes [ 17 ]. Voroni diagrams need to be repeatedly constructed
to reflect the nodal movement. Since the construction of the diagram requires
global computation, this approach has large message overhead. To avoid oscilla-
tions (e.g. moving back and forth between several points), nodes may stop moving
early which can cause coverage redundancy and coverage holes in the network.
The following paragraphs present approaches based on a Voroni-diagram and
“quorum-based” approaches, which are used for coverage improvement in terms of
efficiently covering the coverage holes .
Wang et al. [ 22 ] describe three distributed self-deployment algorithms (VEC,
VOR and min-max) for mobile sensors using Voroni diagrams. Once the Voroni
polygons are constructed, each sensor within the polygon can examine the exis-
tence of possible coverage holes. If such a hole is discovered, the sensors will move
to new positions according VEC, VOR, or min-max protocol.
The Vector-based algorithm (VEC) pushes sensors from densely to sparsely
covered areas. Two sensors exert a repulsive force when they are close to each other.
If d av is the average distance between any two sensors, the virtual force between the
sensors s i and s j will move each of them ( )

( )

d dss distance away from
each other. In case one of the sensor's sensing range completely covers its Voroni
polygon, only the other sensor should move away ( )

− , /2

av i j

( )

d dss distance. In
addition to the mutual repulsive forces between sensors, the boundaries also
apply forces to push sensors inside the boundary. If ( )
bi

− ,

av i j

ds is the distance of a sen-
sor s i from its closest boundary, then the repulsive force would move it a distance
( )

d ds opposite the boundary.The Voroni-based algorithm (VOR) pulls
sensors toward their local maximum coverage holes. If a sensor detects a coverage
hole within its Voroni polygon, it will move toward its farthest Voroni vertex, such
that the distance from its new location to its farthest Voroni vertex ( v - u in the
Fig. 6.5 ) will be equal to the sensor's sensing range. This way, the maximum mov-
ing distance for a sensor is limited to at most half the communication range.

/2 −

av b i