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 3 45614

Text preview


Energies 2018,
2018, 11,
11, 3526
x FOR PEER REVIEW
Energies
Energies 2018, 11, x FOR PEER REVIEW

44 of
of 14
14
4 of 14

3.1. Distributed Framework of DGA
3.1. Distributed
of DGA
DGA
3.1.
Distributed Framework
Framework of
In DGA, the master-slave distributed model is used. The processor whose role is to control the
In DGA,
DGA, the
the master-slave
master-slave distributed
distributed model
model is
used. The
whose
role
to control
control the
the
In
is used.
The processor
processor
whoseoperations,
role is
is to
whole
evolutionary
process including crossover,
mutation,
and selection
is called
whole
evolutionary
process
including
crossover,
mutation,
and
selection
operations,
is
called
whole
evolutionary
including
crossover,
mutation,for
and
selection operations,
is called
MASTER.
MASTER.
The otherprocess
processors,
which
are responsible
chromosomes’
evaluation
to reduce
the
MASTER.
The
other
processors,
which
are
responsible
for
chromosomes’
evaluation
to
reduce
the
The
other processors,
are responsible
foran
chromosomes’
evaluation
to reduce
the computational
computational
costs, which
act as SLAVEs.
To give
overview of the
DGA, the
master-slave
distributed
computational
costs, actToasgive
SLAVEs. To give of
anthe
overview
of the
DGA, the master-slave
distributed
costs,
act is
asdepicted
SLAVEs.
DGA,
the
master-slave
distributed
structure
is
structure
in Figure 1.anInoverview
each generation,
the master
sends chromosomes
to slaves,
while
structure
is
depicted
in
Figure
1.
In
each
generation,
the
master
sends
chromosomes
to
slaves,
while
depicted
in
Figure
1.
In
each
generation,
the
master
sends
chromosomes
to
slaves,
while
the
slaves
the slaves evaluate the chromosomes and return their corresponding fitness values back to the master
the slavesthe
evaluate
the chromosomes
return
their corresponding
fitness
values
back
to the
master
evaluate
chromosomes
and returnand
their
corresponding
fitness values
back
to the
master
[38].
[38].
[38].
MASTER
MASTER

SLAVE1
SLAVE1

SLAVE2
SLAVE2

...
...

SLAVEn
SLAVEn

Figure 1. The distributed framework of the distributed genetic algorithm (DGA).
Figure 1. The distributed framework of the distributed genetic algorithm (DGA).

3.2.
Chromosome Representation
Representation
3.2. Chromosome
3.2. Chromosome Representation
The
aim of
of the
the EEC
EEC problem
problem is
is to
to maximize
maximize the
the number
number of
of disjoint
disjoint sets.
sets. Therefore,
Therefore, the
the first
first thing
thing
The aim
The aim of how
the EEC
problem
is nodes
to maximize
the
number
ofatdisjoint
sets.
Therefore,
the
firstbound
thing
is
to
determine
many
sets
the
can
be
divided
into
most.
This
is
also
the
upper
is to determine how many sets the nodes can be divided into at most. This is also the upper bound of
is to determine
hownumber
many sets
the nodes
can area
be divided
intodivided
at most.into
Thismany
is also
the upper
bound ofi,
of
disjoint
K [23].
Since
been
grids,
for each
thethe
disjoint
setssets
number K [23].
Since
the the
area hashas
been
divided
into many
grids,
for each
gridgrid
i, we
the
disjoint
sets
number
K
[23].
Since
the
area
has
been
divided
into
many
grids,
for
each
grid
i, we
we
find
out
the
number
of
sensors
k
that
cover
the
grid
i.
Then,
the
minimal
k
is
the
upper
bound
i
i
find out the number of sensors ki that cover the grid i. Then, the minimal ki is the upper bound number
find out the
numbersets,
of sensors
that cover
the grid i. Then, the minimal ki is the upper bound number
number
of sets,
disjoint
i.e., Ki}.=kimin{k
i }.
of disjoint
i.e., K = min{k
of disjoint
sets,upper
i.e., Kbound
= min{k
i}.
With
the
K
determined,
we
the chromosome
in a very
intuitive
manner
With the upper bound K determined,can
we encode
can encode
the chromosome
in a very
intuitive
With
the
upper
bound
K
determined,
we
can
encode
the
chromosome
in
a
very
intuitive
that
each that
geneeach
is angene
integer
the range
of range
[1, K].of
Therefore,
the chromosome
is a string
integers
manner
is anininteger
in the
[1, K]. Therefore,
the chromosome
is aofstring
of
manner
that each
gene
is an
integer
in the range
of [1,nodes.
K]. Therefore,
the chromosome
is a string of
with
the
length
of
D,
where
D
is
the
number
of
sensor
The
representation
is
integers with the length of D, where D is the number of sensor nodes. The representation is
integers with the length of D, where D is the number of sensor nodes. The representation is
KK
(3)
X =X=
[x [x, 1x, x, 2., .…,
. , xxD], where xi ∈
∈ ZZ and
and 11 ≤≤xix≤ ≤
(3)
X= 1[x1,2x2, …, xDD], where xii ∈ Z and 1 ≤ xi ≤i K
(3)
In (3), the value of xi denotes which set the ith sensor belongs to. Figure 2 gives two examples of
In (3), the value
value of
of xxi idenotes
denoteswhich
whichset
setthe
theith
ithsensor
sensorbelongs
belongsto.to.
Figure
2 gives
two
examples
Figure
2 gives
two
examples
of
the chromosome representation.
In the examples, D is 4 and K is 2. In Figure 2a, the chromosome is
of
the
chromosome
representation.
In
the
examples,
D
is
4
and
K
is
2.
In
Figure
2a,
the
chromosome
the
chromosome
representation.
In
the
examples,
D
is
4
and
K
is
2.
In
Figure
2a,
the
chromosome
is
Xaa =a[1, 2, 1, 2], meaning that the first and the third sensors belong to the 1st set while the second and
is
X
=
[1,
2,
1,
2],
meaning
that
the
first
and
the
third
sensors
belong
to
the
1st
set
while
the
second
X = [1, 2, 1, 2], meaning that the first and the third sensors belong to the 1st set while the second and
the fourth sensors belong to the 2nd set. In this case, it can be observed that both the 1st and the 2nd
and
the fourth
sensors
belong
to2nd
the 2nd
set.this
In case,
this case,
canobserved
be observed
theand
1st and
the
the fourth
sensors
belong
to the
set. In
it canit be
that that
bothboth
the 1st
the 2nd
sets can provide full coverage for the monitored area. However, in Figure 2b, the chromosome is Xbb
2nd
can provide
full coverage
for monitored
the monitored
area.
However,
in Figure
chromosome
sets sets
can provide
full coverage
for the
area.
However,
in Figure
2b, 2b,
thethe
chromosome
is Xis
= b[1, 2, 1, 1], meaning that the first, the third, and the fourth sensors belong to the 1st set while only
X
= 2,
[1,1,2,1],
1, 1],
meaning
that
first,
third,
andthe
thefourth
fourthsensors
sensorsbelong
belongto
tothe
the1st
1st set
set while
while only
= [1,
meaning
that
thethe
first,
thethe
third,
and
the second sensor belongs to the 2nd set. In this case, only the 1st set can provide full coverage for
the second
case,
only
thethe
1st1st
setset
cancan
provide
fullfull
coverage
for the
second sensor
sensorbelongs
belongstotothe
the2nd
2ndset.
set.InInthis
this
case,
only
provide
coverage
for
the monitored area, but the 2nd set cannot.
monitored
area,area,
but but
the 2nd
set cannot.
the monitored
the 2nd
set cannot.

Figure 2. Illustration of the chromosome representation.
Figure 2. Illustration of the chromosome representation.