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

Approaches with Hexagonal Grid Structure

Partitioning the sensor field in hexagonal grid structure is considered in [ 1, 16 ].
SNAP & SPREAD is an algorithm for mobile sensor self-deployment, which uses
network self-configuration and self-adaptation [ 16 ]. The protocol constructs hexagonal
grid structure and arranges sensors at centers of thus constructed hexagons. The
hexagon edge length is equal to R s (sensing range) and the proposed deployment
strategy guarantees coverage when ≤ , and t R is the transmitting range of

the sensors. In this algorithm, each mobile sensor spontaneously starts to construct
a hexagonal tiling; it chooses its current position as the center of the first hexagon
of the tiling and becomes snapped. A snapped sensor learns the status of its neigh-
bors, and selects at most six of the neighbors, and snaps them to the centers of
adjacent empty hexagons. The new snapped sensors continue with an analogous
process until no other snaps are possible. After the snap activity, if there are still
spare sensors, a spread process is established where un-spread sensors are pushed
toward low-density zones (Fig. 6.9 ). Each sensor needs locally available informa-
tion to decide about its movements. The proposed algorithm quickly converges to
a uniform and regular sensor deployment over the region of interest, independently
of its shape and of the initial sensor deployment. It makes the sensors traverse small
distances, avoiding useless movements, and thus the algorithm ensures low-energy
consumption and stability. The algorithm can cause network partitioning through
constructing separate clusters in sparse networks.
A deterministic approach for deploying sensor nodes into the sensor field is pro-
posed in [ 1 ], where hexagonal grid positioning is used to address and locate each
sensor node. The dynamic relocation algorithm is called MaxNetLife , and is mainly
based on utilizing the remaining power of individual sensor nodes as well as prop-
erly relocating sensor nodes so that all sensor nodes can transmit the data they sense
to the sink. The sensor field is divided into clusters, and clusters are further divided
into hexagonal cells. Each CH calculates the energy level of the nodes in its cell and
sends the report to the sink node. The sink node then determines if there is a require-
ment for the nodes to move toward certain locations and which nodes are appropriate
for the movement. Then the sink sends mitigation instructions to the CHs, which
resend appropriate mitigation instructions to the sensor nodes. Then the actual

R 3 R

s tx

Fig. 6.9 SNAP & SPREAD algorithm