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

Se

Sa

Si Si

ν

Sd

ν

Sb

u u

Sc

Fig. 6.5 VOR and min-max strategy

The min-max algorithm is very similar to VOR, but it moves a sensor inside its
Voroni polygon to a point where the distance from its farthest Voroni vertex is mini-
mized. Since moving to the farthest Voroni vertex might lead to a situation for the
vertex that was originally close to becoming a new farthest vertex, the algorithm
positions each sensor in a manner that no vertex is too far away from the sensor.
Utilizing local movements and communications, the proposed protocols are
extensible for large deployment scenarios, but they perform better if initial deploy-
ment is random rather than clustered and does not perform well in case of insuffi-
cient communication range.
Bidding and proxy- based sensor deployment are protocols proposed by the
authors in [ 22 ], which are based on Voroni diagrams and are created for handling
coverage holes in a hybrid network structure composed of static and mobile nodes.
In [ 23 ], each static sensor is location aware and can detect a possible hole,
based on the constructed Voroni diagram. Mobile sensors are used to cover the
holes after the static sensors, which have discovered a hole, have sent requests
( bids ) to the nearest mobile sensors. If a hole is found, a static sensor chooses the
location of the farthest Voroni vertex as the target location of the mobile sensor
and calculates the bid as ( ) 2
s

π − , where d is the distance between the sensor
and the farthest Voroni vertex and R s is the sensing range. A static sensor then
finds the closest mobile sensor whose base price (each mobile sensor has an asso-
ciated base price that is initialized to zero) is lower than its bid and sends a bidding
message to this mobile sensor. The mobile sensor receives all such bids from its
neighboring static sensors and chooses the highest bid and moves to heal that
coverage hole. The accepted bid becomes the mobile sensor's new base price.
Possible disadvantages of the protocol are energy consumption when nodes move
necessarily (applying iterative movements) and the possibility of moving exces-
sive number of nodes toward the same hole (duplicate healing problem).
To overcome the disadvantages of the bidding protocol, and additionally to
handle with multiple holes, the authors have proposed proxy-based sensor reloca-
tion protocol in [ 24 ]. Instead of moving iteratively (Fig. 6.6a ), the sensors calculate
their target location in each step while moving logically and exchanging their logical
information with the logical neighbor nodes. The movement occurs only after the

dR