TELKOM
NIKA
, Vol. 11, No. 9, September 20
13, pp.
5352
~53
5
8
ISSN: 2302-4
046
5352
Re
cei
v
ed Fe
brua
ry 27, 20
13; Re
vised
June 12, 20
13;
Accept
ed Ju
ne 22, 201
3
Wireless Senso
r
Network Path Optimization Based on
Hybrid Algorithm
Ze
y
u
Sun*
1
, Zhenping
LI
2
1
Departme
n
t of Computer, Lu
o
y
an
g In
stitute of Science a
n
d
T
e
chnol
og
y, L
u
o
y
a
ng 4
710
2
3
, Hena
n, Chi
n
a
2
Departme
n
t of Mathematics, Luo
ya
n
g
Institute of Science a
nd T
e
c
hnol
og
y, Luo
yamg 4
7
1
023, He
na
n,
Chin
a
*Corres
p
o
ndi
n
g
author, e-ma
i
l
: 1349
29
978
9
@
qq.com
A
b
st
r
a
ct
One merit of g
enetic a
l
g
o
rith
m is fast over
a
ll sear
c
h
in
g, b
u
t this alg
o
rith
m us
ual
ly resu
lts in low
efficiency
b
e
ca
use
of l
a
rge
q
uantiti
e
s
of re
dun
da
nt
co
des
.
T
he adva
n
ta
ges of
a
n
t
co
l
ony alg
o
rith
m are
strong su
itab
ilit
y and
go
od r
o
bustness
w
h
ile
its disa
dva
n
ta
ges ar
e ten
d
e
n
cy to stag
nati
on, slow
sp
ee
d o
f
conver
genc
e. Put forw
ard b
a
sed
on i
m
pr
oved
ant col
o
ny alg
o
rith
m f
o
r w
i
reless se
nsor n
e
tw
ork path
opti
m
i
z
at
ion
ap
proac
h w
ill first
nee
d to
pass
the dat
a in
the
shortest p
a
th
for trans
missi
o
n
, assu
mi
ng th
at
transmissio
n
p
a
th j
a
m, it w
ill
clog
infor
m
atio
n se
nt to
th
e i
n
itial
pos
ition,
s
o
the
foll
ow
-up
ne
ed t
o
p
a
ss
data
can cho
o
se ot
her reas
ona
bl
e
path so as to avoi
d the def
e
c
ts of the tradition
al me
tho
d
. Genetic ant col
ony
is pro
pos
ed t
o
avoi
d the
fau
l
ts of b
o
th a
l
g
o
rit
h
ms
a
bove. T
h
e pr
opos
ed
al
g
o
rith
m d
e
ter
m
i
nes
distrib
u
tio
n
of
pher
o
m
on
es
o
n
p
a
th thr
oug
h
fast searc
h
in
g
an
d ch
an
gin
g
the op
eratio
n of
sel
e
ction
o
p
e
rator, cross
o
v
e
r
oper
ator a
nd
mutati
on
op
er
ator of g
enetic
ant col
ony, a
nd the
n
so
lves
the pro
b
l
e
ms
efficiently thr
o
ug
h
para
lle
lis
m, p
o
s
itive fe
edb
ack
an
d iter
at
ion
o
f
ant col
ony
al
g
o
rith
m. T
her
ef
o
r
e, the fa
ults of
both
al
gorith
m
s
are co
nqu
ere
d
and th
e a
i
m o
f
comb
in
ation
a
l
opti
m
i
z
at
ion
is
achi
eved. At l
a
st, the vali
dity
and fe
asi
b
il
ity is
de
mo
nstrated
by me
ans of si
mu
lati
on exp
e
ri
me
nt of traveli
ng sal
e
s
m
an
p
r
obl
em.
Ke
y
w
ords
: a
n
t
colony
al
gori
t
hm (A
CA), co
mb
in
atoria
l o
p
timi
z
a
tio
n
, trav
elin
g sa
les
m
a
n
pro
b
l
e
m (T
SP),
w
i
reless sens
o
r
netw
o
rk (W
SN)
Copy
right
©
2013 Un
ive
r
sita
s Ah
mad
Dah
l
an
. All rig
h
t
s r
ese
rved
.
1. Introduc
tion
In the 1990
of the 20th centu
r
y, Italy sch
ol
a
r
M.Dorig, who wa
s inspired from the
mech
ani
sm
of biolo
g
ical
evolution, A
n
t ro
uti
ng
b
ehaviou
r
by
simulatin
g
th
e natu
r
al
wo
rld,
prop
osi
ng a
n
e
w
simulate
d
evolution of
Ant Colony
al
gorithm (Ant Colo
ny
algo
rithm
ACA).
Ea
rly
was widely used in the
travelling
sal
e
sman
probl
em (T
ravelling Salesm
an Problem, T
SP)
solutio
n
. Travelling
sale
sm
an p
r
obl
em i
s
a typical
co
mbinato
r
ial o
p
timization
p
r
oblem, b
u
t al
so
a
NP hard prob
lem. As the proble
m
gro
w
s, ant col
ony algorith
m
in a limited num
ber of cy
cle
s
is
difficult to find the exact solution of the proble
m
, and can ea
sily fall into local
optimal sol
u
tion,
cau
s
in
g the system to ru
n the cycle i
s
too
long,
slow converge
nce a
nd the
emerg
e
n
c
e
of
stagn
ation. University of Mi
chiga
n
in 1975, Professor
Joh
n
H. Hollan
d
prop
osed ge
neti
c
algorith
m
(G
enetic Algo
rithm, GA) ca
n be
initia
li
zed from
a
start no
de t
r
a
v
ersal,
to av
oid
initialization
f
r
om
a
singl
e
node
cau
s
ed
the m
o
st
ea
sy to fall
into
local o
p
timal
sol
u
tion
of t
h
e
iterative process that converge
s to a
greater probability of the optimal soluti
on, whi
c
h has a
better ability
to solve th
e global
opti
m
al sol
u
tion.
However, i
n
solving
co
mplex nonlin
ear
probl
em
s there too prem
a
t
ure, conve
r
g
ence is
slo
w
,
resultin
g in a lot of redundant co
de a
nd
other
sho
r
tco
m
ings, thu
s
makin
g
the solution a
c
cu
r
a
cy
is t
oo lo
w
[
1
-3]
.
Wirel
e
ss
sen
s
o
r
net
wor
k
coverage p
r
o
b
lem in the field of wirel
e
ss se
ns
or
netwo
rk
(WS
N) is o
ne of
the focuses of
resea
r
ch
p
r
o
b
lems. Wirele
ss se
nsor net
work ch
ara
c
t
e
risti
c
s
can
b
e
su
mma
rize
d
as: small si
ze,
low
co
st, low ene
rgy con
s
umption, h
a
s a certain
ca
lculatio
n, pro
c
e
ssi
ng a
nd
comm
uni
cati
on
cap
abilities. I
n
the pro
c
e
s
s of wirele
ss
sensor
net
wo
rk cove
rag
e
, need
s to solve
two probl
em
s:
first, the cove
rage, h
o
w to
rea
s
on
ably a
nd effect
ively redu
ce the
n
ode en
ergy consumption,
and
try our
be
st to prolon
g the
netwo
rk life
cycle;
Se
co
n
d
: usin
g mo
b
ile nod
e
sche
duling
strategy
and pa
ram
e
ter dynami
c
chang
e, redu
ce the mobile
node to cove
r the amou
nt of work area,
to
achi
eve the
g
oal of l
o
cal a
r
ea
cove
r effe
ctively,
enha
nce
d
the
topo
logy of the
ne
twork, redu
ci
ng
redu
nda
nt da
ta generated
at the same
time impr
ove the quality of network service. Covered,
Evaluation Warning : The document was created with Spire.PDF for Python.
TELKOM
NIKA
ISSN:
2302-4
046
Wirel
e
ss Sen
s
or
Network
Path Optim
i
zation ba
sed o
n
Hybrid Alg
o
r
ithm
(Zeyu S
un)
5353
therefo
r
e, ho
w to meet ce
rtain
conditio
n
s, the u
s
e o
f
minimum se
nso
r
no
de to spe
c
ify the loca
l
area
cove
red
and effectiv
ely inhibit the
node e
nergy
con
s
um
ption
of too fast is a challe
ngi
ng
topic.
2. Descrip
tio
n
of the
Ant
Colon
y
Algorithm and G
e
netic
Algori
t
hm
2.1.
Desc
ription of the
An
t Colon
y
Algorithm
Ants in natu
r
e after on
e'
s prey du
rin
g
the sh
orte
st
path from th
e food
sou
r
ce to Ant
nest
s
ca
n be
found mai
n
ly rely on a call
ed phe
rom
o
n
e
che
m
icals.
Ants in the fo
ragin
g
process
will relea
s
e
a
ce
rtain
amo
unt of ph
ero
m
one,
in
mot
i
on pe
rceptio
n in p
herom
one of
ants
and
stren
g
th, an
d
to guide th
ei
r o
w
n di
re
ctio
n [4, 5]. Whe
n
a path
me
ssag
e when th
e co
ncentrati
on
of higher, ind
i
cating that th
e path ado
pted by the
ants, the more t
he numb
e
r,
whi
c
h sele
ct the
path, the greater the
probability of
so t
hat they form
ed made up
of
a large
number
of Ant
Colony
colle
ctive b
e
haviours of a
po
siti
ve
feed
back me
cha
n
i
sm of
info
rm
ation
. Wh
en
the path of
t
h
e
pheromo
ne more a
nd for
a long time, while othe
r
p
hero
m
on
e on
a path with the pa
ssage o
f
time
has gradually
declined, the colony
will eventually find an optimal path.
2.2.
Gene
tic Algorithm Descriptio
n
Geneti
c
alg
o
r
ithm i
s
a
ki
nd of Bio
n
ic optim
ization
algo
rithm, i
s
a
natu
r
al
biologi
cal
natural
sele
ct
ion and ge
ne
tic mech
ani
sm of natur
al of rando
m ad
aptive sea
r
ch
algorithm. Act
gene
s o
n
th
e ch
rom
o
so
me to find th
e be
st sol
u
tion of chro
m
o
som
e
s. In
g
enetic
algo
rithms,
mutation
and
cro
s
sover o
perato
r
on
th
e solution
sp
ace
sea
r
ch,
cro
s
s
ope
rat
o
r i
s
th
ro
ugh
a
combi
nation
of the p
a
ren
t
s of in
divid
ual
ch
a
r
a
c
teristics, p
r
odu
ce
s a
ne
w i
ndividual. After
combi
n
ing it
with sel
e
ctio
n
operator, is t
he pr
im
ary m
e
thod of a
c
ce
lerating
genet
ic algo
rithm f
o
r
informatio
n e
x
chan
ge, enh
anced ge
neti
c
algo
rithm
o
f
global search. Fitne
ss f
unctio
n
ca
n then
be used for n
u
meri
cal eval
uation of ea
ch individual
,
on the evoluti
on of ne
w sp
ecie
s for the
next
roun
d. Each
and eve
r
y individual that
we a
s
k a
po
tential implici
t
solution of
probl
em
s, fro
m
gene
ration to
gene
ration in
the geneti
c
manipul
ation e
v
olve an optimal solutio
n
.
2.3.
WSN D
e
scription
Radi
o p
r
obl
e
m
existing
sensor
network n
ode
s
are
the
con
s
trai
nt co
ndition
s at the
distan
ce,
se
ction Point of
ene
rgy, the
nod
es
of
wi
rele
ss po
we
r, environ
men
t
al f
a
ct
or
s,
e
t
c.
Different n
e
twork a
pplication nee
ds
Co
nstrai
nt
co
ndi
tions a
r
e diffe
rent, but the minimum en
e
r
gy
con
s
um
ption
con
s
trai
nt is
one of the m
a
in and m
o
st
important
Constraint
s, a
n
d
the co
nstra
i
n
t
con
d
ition m
a
inly depe
nd
s on
pro
pag
ation di
stan
ce con
s
traint
s and
sectio
n Point
whe
r
e
environ
menta
l
factors con
s
traints a
nd ot
her
con
s
tr
ai
nts are rel
a
ted
to these two
con
d
ition
s
, the
importa
nt link, A wirel
e
ss sen
s
o
r
net
work
mo
d
e
l can be a fig
u
r
e G
(
V,E), V=(v1,v2,v3…v
n
),
Acco
rdi
ng to the netwo
rk ,
E
=(e
1
,e2,e3
…em) Sa
id i
n
the netwo
rk co
mmuni
ca
tion betwe
en
the
node
s[4]. Each ed
ge (i, j)
∈
E have link metrics C
ij
∈
R, at the sa
me time Each node i
∈
V has
a
node
en
ergy
variable
Pi. In
ord
e
r to tra
n
s
mit po
we
r
p
Started fo
r wi
rele
ss tra
n
sm
issi
on, vari
abl
e
s
e
t to p
0
∈
P,
V
i
said a
d
ja
cent n
ode I
R
. If the node
in the no
de
j the maxim
u
m tran
smi
s
sion
range, I will
call node j and i
neighbour node
s, the maximum transmi
ssi
on
range depends on p0.
All meet C
ij
<
P
or les
s
n
o
d
e
j
∈
V
i
, that can be
covere
d by node I. T
herefo
r
e,
such as F
r
uit no
d
e
I
can
sp
re
ad
with maximu
m ene
rgy p
0
,
all bel
ong t
o
the V
i
of
node
s
can
b
e
In orde
r to
be
covered.
3. Algorithm For TSP Problem Definiti
on and Esta
blishment
3.1.
De
finitio
n
of TSP Problem
Given
D
a dire
ct
ed g
r
a
ph
of triples
,,
VE
f
, whic
h
V
is a
n
on-empt
y set, the
ele
m
ent i
s
a dire
cted
graph of n
ode
s;
E
is a
colle
cti
on who
s
e el
e
m
ents fo
r directed
gra
ph
edge
s;
E
from
to
VV
mappin
g
function on
f
.TSP proble
m
refers t
o
the
given di
stan
ce between th
e citie
s
and cities,
t
r
avelling sale
sman
to determine
th
roug
h
the
city if an
d only if o
n
e
of the
sho
r
t
e
st
route. Pu
rpo
s
e
of the TS
P is
sho
w
n i
n
the pi
ct
u
r
e
;
find the le
n
g
th of the
sh
ortest
Ha
milton
circuit, in the
set of point
s
on
12
3
,,
n
Vv
v
v
v
urban traverse an
d
n
minimal cl
osed
curve th
at
traverse
s onl
y once.
Evaluation Warning : The document was created with Spire.PDF for Python.
ISSN: 23
02-4
046
TELKOM
NIKA
Vol. 11, No
. 9, September 201
3: 535
2 – 5358
5354
3.2.
Esta
blishment of
An
t Colon
y
Algorithm
Only
m
Ant random
to pl
ace
d
in
n
on
city, set i
n
itial mome
nts city ea
ch
e
dge
ij
0
c
onst
had inform
ation pigme
n
t,
con
s
t
is a con
s
tant
s,
i
bt
sai
d
t
moments is located in
element
s of
i
Ant
numbe
r,
1
n
i
i
mb
t
,
k
ta
b
u
is taboo ta
bl
e, used to
re
cords
k
Ant by Traverse
City k
not points
,
V
initial m
o
ments
k
ta
b
u
is first a city knot
points,
colle
ction is a
s
evo
l
ution for
dynamic a
d
ju
stment, who
write
s
taboo t
able in the
cit
y
knot points,
Ant is does
not allows th
en
traverse the
city knot poi
n
t
s.
Whe
n
the
cycle i
s
comp
leted,
k
ta
b
u
taboo t
able is
empty, the ants
also
can
cho
o
se
fre
e
ly a
gain. In
path
du
ring
the
sea
r
ch, Ant
based
on
th
e path
h
euri
s
tic
information and
ways to
cal
c
ulate the amount
of
State transition probabilit
y [5,6]. At the
t
moment, ants
k
in
i
urban tran
sition
j
probab
ilities in sel
e
ct cities
k
ij
Pt
:
0
other
w
ise
k
ij
i
j
k
k
is
i
s
ij
s
a
llo
w
e
d
tt
j
allo
wed
tt
Pt
(1)
Whe
r
e
k
al
l
o
w
e
d
0
,
1
,
2
,
n
1
t
ab
u
,
is info
rmation o
n
in
spiration fa
ctor, the rel
a
tive
importa
nce of
the p
a
th.
Are expe
ctation
s
in
spi
r
ed
by
fact
or, rep
r
e
s
ents a relativ
e
ly
impo
rtant
visibility.
ij
d
Re
pre
s
ent
s th
e
dista
n
ce of
the
city, which
ij
t
in
spired
functio
n
i
s
inversely
prop
ortio
nal:
1
ij
ij
td
(2)
Whe
n
the
ant
s after
t
a moment, after
completed a traverse to
n
a c
i
ty, left on a path o
f
pheromo
ne
con
c
e
n
tration
s
will
gradu
ally red
u
ce, this
requi
re
s ma
ke
adj
ustment
s to
the
pheromo
ne o
n
each path, its expre
s
sion
:
1,
1
ij
ij
ij
tt
t
t
(3)
1
,1
,1
m
k
ij
ij
k
tt
t
t
(4)
,1
k
ij
tt
On
beh
alf o
f
k
the Ant
re
mained
,
ij
on
the path
of t
he
stren
g
th
of
information
,1
tt
at all times.
is volatile fa
ct
or p
heromo
n
e,
1
is the
pri
m
e facto
r
s of
resi
dual
information. The
size of
the
direct impact
on the glob
al search
capab
ilities of
Ant
Colo
ny algo
ri
thm and it
s converg
e
n
c
e
rate
1
refle
c
ts t
he ability of
Ant intera
ctio
n between
individual
s.
3.3.
Esta
blishment of G
e
netic Algo
rithms
Length
of
L
binary
n
stri
ng
i
s
formed
a gro
up
1,
2
,
3
in
at the
be
ginnin
g
of th
e
geneti
c
algo
rithm, also
kn
own a
s
the i
n
itial gro
up.
In each se
ri
es, ea
ch bi
n
a
ry digit is t
h
e
individual ge
nes of
the ch
romo
som
e
.
T
he
a
c
tion
s
of
the group th
ere
are th
re
e
:
the first opti
on,
whi
c
h
were
selecte
d
from
a group
rep
r
e
s
entin
g indivi
dual
s to ad
ap
t. These
sel
e
ct individu
als
for
bree
ding th
e
next gene
rati
on. It is also
sometim
e
s
calle
d the op
eration
re
gen
eration. Fitn
e
ss
prop
ortio
nal
sele
ction i
s
selectio
n of the most
ba
si
c method, wh
ere ea
ch in
di
vidual is sele
cted
with its value and the
number of
expected
grou
p avera
ge pro
portio
n
of fitness.
12
3
,,
n
Pa
a
a
a
Grou
ps
su
e for a given
n
size, the indivi
dual
j
aP
the fitn
ess
func
tion is
j
f
a
, its selection probability as:
Evaluation Warning : The document was created with Spire.PDF for Python.
TELKOM
NIKA
ISSN:
2302-4
046
Wirel
e
ss Sen
s
or
Network
Path Optim
i
zation ba
sed o
n
Hybrid Alg
o
r
ithm
(Zeyu S
un)
5355
1
n
sj
j
i
i
pa
f
a
f
a
(5)
A se
con
d
crossover,
whi
c
h a
r
e
sel
e
cted for b
r
e
e
ding the
nex
t gene
ration
of the
individual, ind
i
viduals
of two different g
e
nes
are
exch
ange
d at the
same l
o
catio
n
, whi
c
h resu
lts
in a ne
w in
di
vidual. Crossover o
perator may gen
erall
y
be divided i
n
to thre
e types, respe
c
tively,
is a one
-poi
nt cro
s
sover operato
r
, multiple poi
nt
cro
s
sove
r op
erato
r
, and consi
s
tent cro
s
s-
operating [3]. Con
s
iste
nt cross o
peratio
n is the co
re cro
s
s-cutting operation
s
in the
most
current
resea
r
ch on
e
of the cro
ss.
Con
s
i
s
tent cross-op
eratio
n is that eve
r
y of chromo
somes on th
e
bit
string a
c
co
rdi
ng to the sam
e
prob
ability for ra
ndom u
n
i
form cro
ss.
3.4.
A Net
w
o
r
k Model
Und
e
r n
o
rm
a
l
circum
stan
ces, the coverage di
re
ctly reflect the go
al by the de
gree
of
attention, attention of th
e
target n
ode
a
r
ea
s
with
hig
h
cove
ra
ge,
at the same t
i
me to con
s
id
er
sen
s
o
r
node
i
s
lo
cate
d in
t
he
cove
red
a
r
ea
fun
c
tion
relation
ship
b
e
twee
n exp
e
c
tation
s a
nd
area
covered, in o
r
de
r to study
the pro
b
lem
of c
onveni
ent
, Figure 1
sh
ows the cove
r with unil
a
teral
squ
a
re a
r
ea
as the re
sea
r
ch o
b
je
ct of the r
egion, whi
c
h co
ntai
ns six eight sen
s
o
r
nod
e and
destin
a
tion n
ode, se
nso
r
node an
d the relation
sh
i
p
betwee
n
the target no
de is sh
own
in
Figure 1.
Figure 1. The
Model of the M
onitori
ng Area Net
w
ork Coverag
e
In pro
c
e
ss fo
r sin
g
le squa
re area coverage,
inform
ation coll
ecte
d by sen
s
or
no
des by
gatheri
ng
no
des to b
a
se station, the b
a
s
e
station
after proc
ess
i
ng the data is
trans
mitted to t
he
central co
ntrol terminal [7, 8]. Can be see
n
from
Figure 1 b
e
twee
n each
sen
s
or a
n
d
the
relation
shi
p
b
e
twee
n the
ta
rget
nod
e, se
nso
r
nod
e a
s
the
re
sea
r
ch
obje
c
t, give
n
that
A
(2,
3); B
(1, 2
)
; C
(2,
5); D (5,
6);
E (8);
F (6, 7
)
, on th
e oth
e
r
ha
nd,
with the target n
o
d
e
is
given
as
the
research objec
t is
: 1 (B); 2 (A, B,
C); 3
(A, C);
4 (C);
5 (C, D); 6 (D, F); 7 (D, F); (E). It c
an be
see
n
betwee
n
the sen
s
o
r
node a
nd de
stination nod
e maximum co
rrelation fo
r 3.
4. An Improved Algorithm
Ants are to
complete the
cal
c
ulatio
ns
after this tim
e
throu
gh th
e loop
circuit
distan
ce.
bes
t
L
is
the
s
h
ortest c
i
rc
uit,
worst
L
is th
e long
est
circuit. Update
p
o
licy of thei
r
sho
r
test
and l
onge
st
circuit press formul
as to up
date:
1
11
m
k
ij
ij
k
i
j
k
tt
(6)
Fitness i
s
th
e individu
al
grou
ps the o
pportu
nity to cho
o
se the
only certain
t
y of life
indicator. Ad
aptive functi
on is directl
y
det
ermine
s the evolution of grou
p
behaviou
r
. For
minimizi
ng issue
s
, to esta
blish fun
c
tion
f
x
and
g
x
objective
function of m
appin
g
relatio
n
s:
Evaluation Warning : The document was created with Spire.PDF for Python.
ISSN: 23
02-4
046
TELKOM
NIKA
Vol. 11, No
. 9, September 201
3: 535
2 – 5358
5356
ma
x
m
a
x
0
o
t
h
e
r
w
i
s
e
cg
x
g
x
c
fx
(7)
ma
x
c
is an input or
a theoreti
c
al maximum value.
By adapting function o
n
target sele
ction
and
som
e
kin
d
of evol
ution
a
ry p
r
o
c
e
s
s control
fu
n
c
tion tra
n
sfo
r
mat
i
on in
o
r
de
r t
o
form
ulate
a
n
approp
riate selectio
n policy, evol
ution of hybrid Ant Colony algo
rith
m for maximum capa
city and
the best search re
sult
s [4].
To better evaluate netwo
rk pe
rforman
c
e and
simul
a
ted usin
g M
A
TLAB6.5 si
mulation
experim
ent.
By cha
ngin
g
the
cove
rag
e
rang
e,
rea
lize
th
e different network
cove
ra
ge a
n
d
con
n
e
c
tivity,
and to b
e
tter asse
ss th
e
perfo
rman
ce
of the model
unde
r differe
nt scale, mai
n
ly
reflecte
d in th
e reali
z
atio
n of netwo
rk u
n
der t
he
con
d
i
t
ion of differe
nt coverage
and conn
ecti
vity
rate nee
ds to
be deployed
at least the numbe
r of no
des, an
d ea
ch time simula
tion results a
r
e
the avera
ge
of 100 time
s,
set up th
e si
mulation a
r
e
a
is 10
0 m * 1
00 m, the n
o
de's pe
rcepti
on of
radiu
s
2
m, node
comm
uni
cation
radi
us
is 2 time
s the
radiu
s
of p
e
rceptio
n. Figu
re 2 sho
w
s th
e
initial momen
t
s of the rand
om node lo
ca
l diagra
m
, as
sho
w
n in Fig
u
re 2:
Figure 2. The
Rand
om No
de Lo
cal Coverag
e
Map
Take l
o
wer l
e
ft here, by
1:2 to zoo
m
in, each
nod
e in different
time mobile
map, as
s
h
ow
n
in
F
i
gu
r
e
3
:
Figure 3. Different Time
Node
s for Moni
to
ring the Effica
cy of Regio
nal Cove
rag
e
Evaluation Warning : The document was created with Spire.PDF for Python.
TELKOM
NIKA
ISSN:
2302-4
046
Wirel
e
ss Sen
s
or
Network
Path Optim
i
zation ba
sed o
n
Hybrid Alg
o
r
ithm
(Zeyu S
un)
5357
5. Simulation Experimen
t
This
sh
ows t
hat algo
rithm
has go
od
capab
ility glo
b
a
l se
arch fo
r optimal
sol
u
tions,
accele
rate th
e conve
r
g
e
n
c
e rate of the syst
e
m
, avoiding the
early eme
r
g
ence of itera
t
ive
pro
c
e
s
ses,
suppressio
n
of redun
dant code, makes t
he sol
u
tion m
o
re a
c
curate pre
c
isi
on, whi
c
h
enabl
es dyna
mic optimization of t
he sol
u
tion pro
c
e
ss. In Table 1 and Table 2 in
the paramet
er
of the same three g
r
ou
ps
basi
c
Ant Col
ony al
gorithm
for symmetri
c
TSP algorit
hms comp
ari
s
on
with this
artic
l
e. in order to
verify the effec
t
iv
ene
ss of t
h
is alg
o
rithm,
using Ant
Co
lony algo
rithm
and co
mpa
r
i
s
on
s with
th
is
al
gorith
m
on CHN1
44
expe
riment,
co
ndu
cted
50
com
pari
s
on,
corre
s
p
ondin
g
to the optimal solutio
n
co
nverge
nce cu
rve [9, 10], as sho
w
n in Fig
u
re 4.
Figure 4. Shortest Paths
Curve Co
mpa
r
i
s
on
Cha
r
t
Selec
t
ion in
order to further verify the
effe
ctivene
ss of the
algo
rit
h
m, the
cove
rage
an
d
betwe
en n
o
d
e
s
und
er th
e
different n
e
twork scal
e
cu
rve, and the
conne
ctivity ra
te und
er
different
netwo
rk
scale
and the ch
an
ge cu
rve bet
wee
n
nod
es,
as sho
w
n in
Figure 5 and
Figure 6.
Figure 5. The
Node
Coverage un
der th
e
Different Network Scale Curve
Figure 6. With and With
ou
t Consi
deri
n
g
the
Bounda
ry Effect
Figure 5 sho
w
s the im
ple
m
entation u
n
der the
diffe
rent netwo
rk scale un
de
r different
node covera
ge in a dra
w
i
ng of the number of depl
oyed sen
s
o
r
node
s. Can
get along wit
h
the
expandi
ng of netwo
rk size from
the
cha
r
t,
to
meet
th
e
dem
and
of
certain
net
work
cove
rag
e
,
the
deployme
nt o
f
the numb
e
r
of node
s
will
also i
n
cr
ea
se
, and the
net
work
cove
rag
e
is hi
ghe
r, n
eed
to deploy the
faster i
n
crea
se in th
e n
u
m
ber
of nod
es, so that th
e focu
s of th
e targ
et nod
e to
achi
eve com
p
lete cove
rag
e
.
Figure 6 rea
c
tions a
r
e u
n
d
e
r the
con
d
ition of
with
out
con
s
id
erin
g
the bou
nda
ry effect,
reali
z
e
s
the
different coverag
e
and
conne
ctivit
y rate need to d
eploy the nu
mber of n
o
d
e
s.
Comp
ared wi
th con
s
ide
r
in
g bound
ary u
nder the in
flu
ence of gro
w
th in the number of depl
oyed
Evaluation Warning : The document was created with Spire.PDF for Python.
ISSN: 23
02-4
046
TELKOM
NIKA
Vol. 11, No
. 9, September 201
3: 535
2 – 5358
5358
node
s
slightl
y
, with the increa
se in th
e numb
e
r of
node
s, nod
e den
sity bet
wee
n
so will
get
bigge
r, the bo
unda
ry effect redu
ce
d [11].
6. Conclusio
n
This arti
cle will
genetic Ant
group
al
gorithm
solution most optimization problem of
advantag
e a
pplication Yu
feature
s
sel
e
ct, and
to
out beh
aviou
r
features
se
lect ge
netic
An
t
grou
p al
gorit
hm optimi
z
at
ion p
r
o
c
e
ss,
whil
e for b
a
si
c Ant g
r
o
up al
gorith
m
of limited f
o
r
corre
s
p
ondin
g
of improve
d
, through o
n
heuri
s
tic fu
nction, an
d informatio
n u
pdate poli
c
y, and
cro
s
s
and
sel
e
ct p
o
licy
on
solutio
n
s val
ue fo
r o
p
timization, i
n
m
u
st de
gree Sh
ang
su
ppression
has prematu
r
ely
conve
r
ge
nce phe
nome
non,
imp
r
ove
on glo
bal fo
und
sea
r
ch a
b
ility, effective to
avoid into lo
cal optimal
sol
u
tions,
spe
e
d
up ha
s
co
nverge
nce
spee
d [9]. Set up
the rel
a
tion
sh
ip
betwe
en
sen
s
or no
de
s a
s
soci
ated
wi
th the targe
t
node
mod
e
l. Und
e
r th
e condition
of
con
s
id
erin
g the effects
of bound
ary, a
local
coverage optimi
z
a
t
ion algo
rithm model i
s
put
forwa
r
d.
It can simplify
t
he comp
utational com
p
lex
i
ty
of
netwo
rk cove
rage
and co
nne
cti
v
ity,
improve
s
the
algorith
m
p
e
rform
a
n
c
e,
reali
z
ed i
n
t
he net
work
coverage
an
d co
nne
ctivity
requi
rem
ents,
the more
a
c
curate
sol
u
tion of
the re
quire
d de
plo
y
ment node
the numb
e
r
of
values. Fi
nall
y
, through
the
simul
a
tion ex
perim
ent resu
lts verify the v
a
lidity of the t
heory
sol
u
tion
and the effect
iveness of the algorith
m
.
Referen
ces
[1]
CAI Guo
qi
an
g
,
JIA Li
min,
XI
NG Z
ong
yi.
D
e
sig
n
of
Ant
C
o
lo
n
y
Al
gor
ith
m
bas
ed
F
u
zz
y
Cl
assificati
on
Sy
s
t
e
m
.
F
u
zz
y
Systems an
d Mathe
m
atics
. 2
008; 4(2
2
): 87-
98.
[2]
F
eng Z
u
h
o
n
g
,
XU Z
o
ng
b
en.
A H
y
b
r
id
Ant
Colo
n
y
A
l
g
o
rit
h
m for S
o
lvi
n
g
T
S
P.
Journa
l o
f
Engi
ne
erin
g
Mathem
atics
. 2
002; 4(1
9
): 35-
39.
[3]
Gao Sha
ng, Z
H
ANG Xi
aor
u. Ant Colon
y
Optimizatio
n
Genetic H
y
br
i
d
Algor
ithm.
Mathem
atics i
n
Practice an
d T
heory
. 20
09; 2
4
(39): 93-
96
[4]
Dong D, Liao
X
.
Distributed
coverage in
w
i
re
less Ad Hoc
and sens
or net
w
o
rks by
topogic
a
l graph
appr
oach
e
s.
IEEE Transactons on Com
p
uter
s
. 2011; 61(
10)
:1417-
14
28.
[5]
Liu Yin, MA Li
ang. F
u
zz
y
A
n
t Colon
y
al
gor
i
t
hm and its Applicati
on i
n
T
S
P.
Mathematic
s in Practice
and T
h
e
o
ry
. 20
11; 6(41): 1
50-
153.
[6]
T
ao Li Min, Gao Ju
n e
n
. Ap
plicati
on
of
sol
v
ing T
SP base
d
on
improv
ed
gen
etic al
gor
ithm.
Co
mp
ute
r
Engi
neer
in
g an
d Appl
icatio
ns
. 200
9; 45(3
5
): 45-47.
[7]
Gong Sha
ng B
ao, Guo Yu
C
u
i. Genetic Alg
o
rithm Base
d on F
u
zz
y
Clust
er Anal
ys
is.
Fuzz
y
Systems
and Math
e
m
ati
c
s
. 2010; 6(2
4
)
:
123-12
8.
[8]
Ammari H, Da
s S. Centraliz
e
d
an
d Cl
ustere
d K-cover
age
protoco
l
s for
w
i
reless se
nsor
net
w
o
rk.
IE
EE
T
r
ansactio
n
s o
n
Co
mp
uters
. 201
2; 61(1):1
1
8
-13
3
.
[9]
Z
hang
X. Ada
p
t
ive control a
n
d
re
confi
gurati
on of mobi
le
w
i
reless
se
nsor
net
w
o
rks for d
y
n
a
mic multi-
target tracking.
IEEE Transaction on Autom
a
t
i
c Control
. 201
1; 56(10): 2
429
-244
4.
[10]
Ke W
,
Liu B. Efficient al
gorith
m
for constructi
ng minimum s
i
ze
w
i
reless sens
or net
w
orks
to fully
cov
e
r
critical sq
uare
grids.
IEEE Transactions on
Wireless Comm
unic
ations
. 2
011; 10(
4): 115
4-11
64.
[11]
An W
,
Shao
F
.
T
he covera
ge-co
ntrol
opti
m
iz
atio
n o
n
s
ensor
net
w
o
rk
subj
ect to s
ensi
ng
area.
Co
mp
uter and
Mathe
m
atics w
i
th Appl
icatio
ns
. 2009; 57(
4): 529-5
39.
Evaluation Warning : The document was created with Spire.PDF for Python.