Information Technology Reference
In-Depth Information
Approaches with Square Grid Structure
In [
27
], an algorithm called
SMART
(scan-based movement-assisted sensor deploy-
ment method) is introduced, which partitions the region of interest in a 2D mesh
through clustering. The algorithm is distributed and scan based, nodes are treated as a
load and the objective is to balance the load (number of nodes) in each cell. Each cluster
corresponds to a square region and has a CH that is in charge and which communicates
with adjacent CHs. A hybrid approach is used for load balancing, where the 2D mesh
is partitioned into 1D arrays by row and by column. Two scans are used in sequence:
one for all the rows, followed by the other for all the columns. Within each row and
column, the scan operation is used to calculate the average load and then to determine
the amount of overload and underload in clusters. Load is shifted from overloaded
clusters to underloaded clusters to achieve a balanced state. In areas with holes, a pre-
processing is performed for planting “seeds” in holes at each 1D scan. These seeds will
serve as CHs in the holes. This approach requires the network to be dense enough so
that load balancing can be proceeded in the entire sensory field, what may generate
huge message overhead. A simple example of a 2D scan is presented in Fig.
6.8
.
A grid-quorum approach is considered in [
29
], where the sensor field is evenly par-
titioned into grids, and each cell has a cell head (Fig.
6.7a
). The cells with redundant
nodes advertise to other cells in a row, while the cells that need redundant sensors send
queries to cells in each column. Since there must be an intersection cell between each
row and each column, the intersection cell head will be able to serve the query. To
reduce message complexity, information about already discovered closest redundant
node is piggybacked on the search message and used to restrict the distance that the
message may travel further. Having obtained the location of the redundant sensor, it is
moved towards the destination by cascaded movements. Moving it directly to the des-
tination can be a possible solution, but it may take a longer time and it can consume too
much energy. With the proposed relocation algorithm, sensor relocation time is reduced.
Although the total moving distance may increase, each mobile node moves much less
to balance the energy consumption and hence increase the network lifetime.
Row
balance
Column
balance
7
1
5
5
4
4
7
5
6
6
5
5
Optimal
movement
5
5
5
5
Fig. 6.8
2D SMART algorithm
Search WWH ::
Custom Search