PDF Archive

Easily share your PDF documents with your contacts, on the Web and Social Networks.

Share a file Manage my documents Convert Recover PDF Search Help Contact

Solving the Energy Efficient Coverage Problem in Wireless Sensor Networks A Distributed Genetic Algorithm Approach with Hierarchical Fitness Evaluation.pdf

Preview of PDF document untitled-pdf-document.pdf

Page 1 2 34514

Text preview

Energies 2018, 11, 3526

3 of 14

many grids and the coverage issue can be transformed to check whether each grid is covered by at
least one active sensor node [19].
All the D sensors form the sensors set S = {s1 , s2 , . . . , sD }, where each sensor node si is with the
location (xi , yi ) and the sensor radius R. For any grid g(x, y) ∈ A in the monitored area, the relationship
between the si and the g is defined as:
P ( si , g ) =

1, if ( x − xi )2 + (y − yi )2 ≤ R2
0, otherwise


where 1 means that the grid g is covered by the sensor si while 0 means the sensor si does not cover the
grid g. Therefore, for any grid g in the monitored area, if there exist at least one sensor si (1 ≤ i ≤ D)
that makes P(si , g) = 1, we say that A is fully covered by the sensor network.
In the EEC, the set S is divided into M subsets Sj (1 ≤ j ≤ M), and with the objective of maximizing
the value of M, as:
f = max K
subject to (i) ∪iK=1 Si ⊆ S
(ii) S i ∩ S j = Φ

(iii) ⊕s j ∈Si P(s j , g)) = 1,

∀g ∈ A

Here, the constraint (i) means that the unitization of all the subsets Sj must belong to the original
set S. The (ii) indicates that there is no intersection between any two different subsets Sj1 and Sj2 .
The (iii) represents that for any grid g in area A, there exists at least one sensor si in Sj which can
cover the grid g. Obviously, these constraints can guarantee that each subset Sj can fully cover the
monitored area.
2.2. Related Work
With the development of evolutionary computations (ECs) like GA [25,26], ant colony
optimization (ACO) [27,28], particle swarm optimization (PSO) [29,30], and differential evolution
(DE) [31,32], many researchers have applied ECs into solving the EEC problems in WSN, such as
PSO-based [33] and ACO-based [34] approaches. Specifically, in [33], Zhan et al. extended the
binary PSO (BPSO) to solve the EEC problem by finding a minimal set of nodes again and again to
maximize the number of disjoint sets. Lin et al. [34] proposed the ACO-based approach to maximize
the number of connected covers, called ACO-MNCC, to maximize the lifetime of heterogeneous WSNs
by transforming the search space of the problem into a construction graph. Besides, in [35], Yang et al.
proposed a probabilistic model to tackle the EEC problem in WSN, which transforms the area converge
into point converge. It greatly reduces the dimension of problem. Lee et al. [36] also tried to solve the
EEC problem in the WSN by using the ACO, which designs three pheromones to balance the local
exploitation and global exploration. Meanwhile, they also introduced a probabilistic sensor detection
model, which makes the algorithms more realistic [37].
Some researchers have also used GA for solving the EEC in the WSN recently. For example,
Lai et al. [25] proposed a GA-based method to maximize the disjoint sensor covers called GAMDSC.
However, there is still much room for improvement. First, their works only solved the small-scale
problems (up to 140 sensors). When the scales of problems increase, their performance often face
difficulties. Second, parallel or distributed methods can further improve the performance and save the
computational time.
3. Methodology: DGA for the EEC Problem
In this section, the DGA for solving the EEC problem in WSN is implemented and described.
The master-slave distributed framework is first given. Then the chromosome representation and the
hierarchical fitness evaluation mechanism are described. After that, the genetic operators, including
the selection, crossover, and mutation are proposed. At last, the overall algorithm is presented.