TELKOM
NIKA Indonesia
n
Journal of
Electrical En
gineering
Vol.12, No.7, July 201
4, pp
. 5484 ~ 54
9
0
DOI: 10.115
9
1
/telkomni
ka.
v
12i7.476
3
5484
Re
cei
v
ed O
c
t
ober 1
4
, 201
3; Revi
se
d Ja
nuary 4, 201
4
;
Accepte
d
Febru
a
ry 1, 20
14
A Survey on Clustering Routing Protocols Based on
PSO in WSN
En
y
a
n
Sun*,
Chua
n
y
un Wang, Feng Ti
an
Schoo
l of Com
puter Scie
nce,
S
hen
ya
n
g
Aer
o
spac
e Univ
er
sit
y
Shen
ya
n
g
, Chi
na (+
86)0
2
4
8
9
723
89
2
*Corres
p
o
ndi
n
g
author, e-ma
i
l
: sunen
ya
n
418
418
@16
3
.com
A
b
st
r
a
ct
LEACH
is
a tra
d
itio
nal
cl
usteri
ng r
outin
g
prot
ocol
in
w
i
rel
e
s
s
sens
or
netw
o
rk. W
hen
se
le
cting th
e
cluster
hea
d, L
each
do
es
not
consi
der s
ens
o
r
no
des
’
en
erg
y
an
d p
o
sitio
n
infor
m
ati
on. It l
eads
to u
nev
e
n
the d
i
stributi
o
n
of cl
uster h
e
ads
and
u
nev
en
ener
gy
c
o
n
s
umptio
n of s
ensor
no
des.
Clusteri
n
g
rout
i
n
g
protoco
l
s w
h
ich are bas
ed o
n
particle sw
ar
m optimi
z
a
t
i
on h
a
ve be
en pr
op
osed to i
m
pr
ov
e the perfor
m
a
n
ce
of clusteri
ng
ro
uting
protoc
ols
.
T
h
is pa
per
in
troduces
an
d c
l
assifies
the
cl
usterin
g
ro
utin
g prot
ocols
w
h
ic
h
are bas
ed o
n
PSO and poi
nts the future dir
e
c
t
ion.
Ke
y
w
ords
: w
i
reless se
nsor n
e
tw
orks, clustering ro
uting
pro
t
ocol, PSO, LEACH
Copy
right
©
2014 In
stitu
t
e o
f
Ad
van
ced
En
g
i
n
eerin
g and
Scien
ce. All
rig
h
t
s reser
ve
d
.
1. Introduc
tion
Wirel
e
ss Sen
s
or
Networks (WSNs) i
s
compo
s
ed of
a large n
u
m
ber of se
nso
r
node
s
whi
c
h are ra
ndomly depl
oyed either i
n
sid
e
the
ph
enome
non o
r
very close t
o
it. WSNs can
perceive am
bient enviro
n
m
ent and
se
nd these informatio
n to end
u
s
ers. WSN work
a
s
the
sen
s
in
g laye
r of Internet
of Thing
s
(Io
T
)
a
nd
have
bro
ad
appli
c
ation d
o
main
s [1
-3]. Routing
proto
c
ol
s a
r
e
in
cha
r
ge
of discove
r
in
g an
d mai
n
taining
the
ro
utes i
n
the
WSNs.
Routi
ng
proto
c
ol
s are
key tech
nol
ogy of WSNs [4]. Clus
te
ring
routing proto
c
ol
s
in wirel
e
ss sen
s
or
netwo
rk can
extend the
netwo
rk life
t
ime thro
u
g
h
data ag
gre
gation at th
e clu
s
te
r he
ad.
Clu
s
terin
g
ro
uting p
r
oto
c
ol
s h
a
ve
beco
m
e the
hot
sp
ot dom
ain
of
WSNs
and
L
EACH [5]
is the
traditional
clu
s
terin
g
ro
utin
g proto
c
ol.
LEACH p
r
oto
c
ol is a dist
ri
buted clu
s
te
r-ba
s
ed p
r
oto
c
ol in whi
c
h
CHs are sele
cted with
some
p
r
ob
abi
lity. LEACH d
i
vides
se
nsor nod
es
into Cluster Head
s (CHs) and
Cl
uster
Me
mbe
r
s
(CM
s
).
CM
s
colle
ct d
a
ta from am
bient
environ
ment and se
nd
th
e
s
e data
to
th
eir CHs. CHs
are
respon
sibl
e for fu
sing th
e
s
e d
a
ta from
CMs within
a
clu
s
ter
and
dire
ctly fused
data to the
sink.
CMs may
be
sle
epin
g
state when
no
ne
wo
rks ne
ed
be d
one.
CHs u
nde
rta
k
e
more
workloa
d
s
and
con
s
um
e ene
rgy mo
re q
u
ickly. CHs
go d
ead
more
qui
ckly.
LEACH rota
tes CHs am
o
ng
different
sen
s
or n
ode
s. LE
ACH
run
s
as a roun
d.
A round
co
nsi
s
t
s
of a
cl
uste
r head
sele
ction,
clu
s
ter format
ion and
stead
-state p
h
ra
se.
Duri
ng the p
e
riod of a cl
uster h
ead
select
io
n, each sen
s
o
r
nod
e prod
uces a
rando
m
numbe
r b
e
tween 0
and
1.
If the numbe
r is l
e
ss tha
n
a thre
sh
old
T(n
)
, the
se
nso
r
n
ode
n
will
become a CH for the curre
n
t round. T
(
n) is
expre
s
sed
as the followi
ng Equation
(1).
else
G
n
P
r
P
P
n
T
0
)
1
mod
(
1
)
(
(1)
P is th
e p
e
rcent of
CHs a
m
ong
all
se
n
s
or n
ode
s
an
d r is the
current runni
ng
round.
G i
s
the set of se
nso
r
no
de
s which
are
not CHs for
th
e current ro
und.
Duri
ng the
pe
riod of a
clu
s
t
e
r
formation, ea
ch CH broad
ca
sts an a
d
vertise
m
ent
m
e
ssag
e (ADV
). Each CM j
o
ins in a nei
g
hbor
c
l
us
ter
acc
o
rding to
RSSI of ADV. Eac
h
CH
build
TDMA
sched
ule an
d notif
y CMs
within
a
clu
s
ter.
Duri
ng the
stead
y state ph
ra
se, CMs
s
e
n
d
their
data
to the CH in
their allo
cat
ed
transmissio
n slot. CH fu
se
s these data
and send
s th
em to the sin
k
. The st
eady
state phrase
is
longe
st in ord
e
r to save the
energy con
s
umption.
Evaluation Warning : The document was created with Spire.PDF for Python.
TELKOM
NIKA
ISSN:
2302-4
046
A Surve
y
on
Clu
s
terin
g
Ro
uting Proto
c
ol
s Base
d on P
S
O in WSN (Enyan Su
n)
5485
2. Rese
arch
Metho
d
2.1. Disadv
a
ntag
e of LE
ACH
LEACH
doe
s not gua
rante
e
the de
sired
numbe
r of CHs
whi
c
h i
s
selecte
d
from
sen
s
o
r
node
s.
Whe
n
selecti
ng CHs, LEACH
doe
s not
con
s
ide
r
se
nso
r
no
de
s’ resid
ual en
erg
y
. Once
these
sen
s
o
r
nod
es who
s
e resi
dual
en
ergy i
s
l
e
ss
become
CHs, these
CHs
may con
s
um
e
energy quickl
y
and be dea
d. It shorten
s
the netwo
rk li
fetime.
Whe
n
sele
cting CHs, LE
ACH
doe
s n
o
t con
s
id
er
sensor
node
s’
positio
n info
rmation.
Those CHs which a
r
e
sele
cted fro
m
se
n
s
or
nod
es
m
a
y dispe
r
se un
evenly. It leads to too mu
ch
comm
uni
cati
on co
st between CHs and
CMs.
The
pro
b
lem
that m
sen
s
o
r
n
ode
s
are
selecte
d
to
be
CHs fro
m
n
sen
s
o
r
node
s is NP
hard
p
r
obl
em
. Particle
Swa
r
m
Optimization
(PSO) ha
s propo
se
d to
solve th
e
abo
ve problem
[6
].
The propo
se
d proto
c
ol
s u
s
ing PSO al
gorithm h
a
ve
highe
r effici
ency an
d ca
n achi
eve be
tter
perfo
rman
ce.
2.2. Particle S
w
arm Opti
miz
a
tion
Particle S
w
arm Optimizati
on (PSO) i
s
an evolution
a
r
y comp
utatio
n techni
que
whi
c
h is
develop
ed by Kenney and Eberh
a
rt [7, 8]. PSO models so
cial be
ha
vior of a flock of birds or fish.
It con
s
ist
s
of
a swa
r
m
of s
can
d
idate
sol
u
tions ca
lled pa
rticl
e
s.
PSO mu
st
have a fitne
s
s
function
which evaluate
s
t
he p
a
rticl
e
s’
positio
n.
The
positio
n with
the b
e
st fitne
s
s fun
c
tion
value
in all parti
cle
s
is call
ed the
global b
e
st (Pg). Each
p
a
r
ticle
kee
p
s track of
its be
st fitness fun
c
tion
calle
d the local best (Pl
)
. PSO is an ite
r
ation
-
ba
se
d optimal algo
ri
thm. The part
i
cle up
date
s
its
velocity usin
g
formula (2
) a
nd its po
sition
using formul
a (3).
))
1
(
(
()
2
))
1
(
(
()
1
)
1
(
)
(
t
X
P
rand
c
t
X
P
rand
c
t
wV
t
V
id
g
id
l
id
id
(2)
)
(
)
1
(
)
(
t
V
t
X
t
X
id
id
id
(3)
Whe
r
e t is th
e numb
e
r
of iteration
s
. Vid i
s
the
velo
city for pa
rticle i
a
nd Xid is th
e
particl
e
positio
n. w is the inertia
weight. c1 a
n
d
c2 a
r
e
two
p
o
sitive co
nst
ants. The fu
n
c
tion rand
()
will
prod
uce ra
nd
om numb
e
rs within ra
ng [0
,1].
3. Taxonomy
of Clusterin
g
Routin
g Protocols
3.1. Conside
r
ation of r
esi
dual energy
of sen
sor no
des
M. J. Handy
et al.
[9] p
r
opo
se
d Lo
w E
nergy Adaptive Cluste
ring Hi
era
r
ch
y with
Determinis
tic Clus
ter-He
a
d
Selectio
n
whi
c
h i
s
mo
dified version
of LEACH.
To incre
a
se
the
netwo
rk lifeti
m
e, the proto
c
ol con
s
ide
r
s the rema
i
n
in
g ene
rgy leve
l available in
each nod
e. T(n)
is cal
c
ul
ated
by Equation (4).
else
G
n
E
E
P
r
P
P
n
T
n
current
n
0
)
1
mod
(
1
)
(
max
_
_
(4)
En_cu
r
rent is the current
ener
gy and
En_max is th
e initial
energ
y
of the sensor nod
e
.
These se
nso
r
node
s who
s
e resid
ual e
nergy is
m
o
re have more
opportu
nity to become CHs.
The m
odifica
tion ma
ke
se
nso
r
n
ode
s
consume
ene
rgy more eve
n
ly and
exte
nd the
net
wo
rk
lifetime. Their simulation
s
sho
w
that su
ch a
modifi
ca
tion can in
crease the net
work lifetime
for
FND
(First Node Di
es) an
d HNA
(Half
of the Node
s
Alive).
3.2. Equal Number of Se
nsor No
des
w
i
thin a Clu
s
ter
Ja
son
Tillett et al. [10] firstly made
use of
pa
rticle swarm optimi
z
ation
to sol
v
e
the
probl
em of
cl
usteri
ng se
nsor node
s.
Fi
rstly,
t
hey use PSO to
fin
d
a li
ne
divid
i
ng the
sen
s
or
node
s i
n
to two re
gion
s
whi
c
h
co
ntain th
e same
num
b
e
r of
sen
s
or
node
s. Th
e p
a
rticle
is defi
ned
as Equatio
n (5).
Evaluation Warning : The document was created with Spire.PDF for Python.
ISSN: 23
02-4
046
TELKOM
NI
KA
Vol. 12, No. 7, July 201
4: 5484 – 54
90
5486
)
,
,
(
y
x
P
(5)
x, y is a point on the line di
viding the two
region
s an
d
is the orie
ntation of the line
.
The ab
ove di
vision continu
e
s recursivel
y unt
il M regi
ons a
r
e
creat
ed. The
s
e M
regio
n
s
contai
n almo
st equal n
u
m
ber of sensor
node
s.
Next, one
CH will
be
sel
e
cted f
r
om e
a
ch
regi
on.
The
CH i
s
t
he seno
r no
de which
minimizes the
mean dista
n
c
e bet
wee
n
the CH and
CMs.
3.3. Conside
r
ation of L
o
c
a
tion and En
erg
y
about Candidates an
d their Neigh
bors
Ying Liang
et al. propo
se
d
PSO-Based
Energy E
ffici
ent Gathe
r
ing
in Senso
r
Networks
[11]. In the beginni
ng, the
y
use LEACH to clu
s
te
r the sen
s
or
no
des. Th
e CH
colle
cts th
e state
informatio
n of CMs. The
s
e
informatio
n are rep
r
e
s
e
n
te
d as the locat
i
on P{p1, p2, … pn} and th
e
resi
dual e
nergy E{e1, e2, … en}. CHs
send
the ab
ove informatio
n to the sink.
The sin
k
u
s
e
PSO
to select next-ro
und optimal CHs.
Th
e
p
o
sition
s
Xi whi
c
h are
cal
c
ulate
d
fro
m
PSO doe
s not equal to
the actual
p
o
sition
s pi of
sen
s
o
r
no
de
s. Xi include
s
x-
locatio
n
com
pone
nt Xxi a
nd y-l
o
catio
n
comp
one
nt X
yi
. Pi also
in
cl
ude
s x-lo
cati
on
com
pone
n
t
p
xi
and y-lo
catio
n
com
pone
nt p
yi
. The absol
ute value of the different b
e
twee
n Xi an
d pi is calcul
a
t
ed
as Equatio
n (6).
2
2
)
(
)
(
yi
yi
xi
xi
p
X
p
X
pi
(6)
The sen
s
o
r
n
ode
k wh
ose
pi
is the le
st is th
e se
archin
g n
ode an
d the a
d
juste
d
value
is
X
xi
p
xk
and X
yi
p
yk
.
The fitne
s
s fu
nction
consi
d
ers the
dista
n
c
e
and
re
sid
u
a
l ene
rgy fa
ct
or a
nd i
s
d
e
fined
as
Equation (7).
n
k
i
i
i
i
i
k
r
r
e
n
e
k
f
1
1
1
)
(
(7)
Whe
r
e
]
1
,
0
[
,
and
1
. k i
s
the
curre
n
t se
nsor no
de a
nd
n i
s
t
he n
u
mbe
r
of
sen
s
o
r
nod
e
s
. ri is the di
stan
ce bet
we
en the cu
rre
nt sen
s
or n
o
de and othe
r sen
s
or n
o
d
e
s.
Select se
nsor node
s whi
c
h
have the bigg
es
t fitness value as the o
p
timal CHs.
N. M. Ab
dul
Latiff et al. p
r
opo
sed
en
ergy-awa
re clu
s
terin
g
fo
r wireless se
nsor netwo
rks
usin
g pa
rticle
swa
r
m o
p
timization [1
2]. At the starting of ea
ch setup pha
se,
all sen
s
o
r
no
de
s
sen
d
inform
ation abo
ut their cu
rrent ene
rgy stat
us a
n
d
location
s to the sin
k
. Base
d upon the
s
e
informatio
n, the sin
k
com
putes the av
erag
e
ene
rgy
level of all node
s. The
s
e sen
s
o
r
no
des
who
s
e
re
sidu
al ene
rgy is a
bove the ave
r
age
ene
rgy level are eli
g
i
b
le to be CHs ca
ndid
a
tes
for
this
round. Next, the s
i
nk
runs
the PSO to
dete
r
mi
ne the
be
st
K CHs
whi
c
h
can
minimi
ze the
fitness fun
c
tio
n
, as define
d
by Equation (8).
2
1
)
1
(
cos
f
f
t
(8)
k
p
i
C
n
k
p
k
p
i
C
CH
n
d
K
k
f
,
,
1
)
,
,
(
,
2
,
1
max
(9)
K
k
k
p
N
i
CH
E
f
1
,
1
i
2
)
(
)
E(n
(10)
Whe
r
e f1 i
s
t
he maximum
avera
ge di
st
ance of sen
s
or n
ode
s to t
heir
asso
ciat
ed CHs
and
k
Cp
,
is the nu
mber of sen
s
or nod
es
whi
c
h bel
ong to
clu
s
ter Ck of
particl
e p.
Evaluation Warning : The document was created with Spire.PDF for Python.
TELKOM
NIKA
ISSN:
2302-4
046
A Surve
y
on
Clu
s
terin
g
Ro
uting Proto
c
ol
s Base
d on P
S
O in WSN (Enyan Su
n)
5487
3.4. Unequ
a
l Size Cluster
s
JIANG
Chan
g-jian
g
et al. propo
se
d Energy
-B
alan
ced Un
equ
al Clu
s
terin
g
protocol fo
r
wirel
e
ss sen
s
or networks (EBUC) [13].
Figure
1 sh
o
w
s
Une
qual
size cl
uste
rs of
EBUC.
Figure 1. Une
qual Size
Clu
s
ters of EBUC
By
using
PSO
alg
o
rithm, EBUC partitio
n
s all sen
s
o
r
node
s
i
n
to cl
usters
of
un
e
qual si
ze,
in whi
c
h th
e
clu
s
ters cl
ose
r
to the
sink
have sm
alle
r size.
The CHs
of
the
s
e clu
s
ters can sav
e
some m
o
re
energy for in
ter-clu
s
ter rel
a
y commu
nication and th
e hotsp
ots p
r
oble
m
ca
n be
avoided.
For i
n
ter-clu
s
ter
communi
catio
n
, EBUC i
s
di
fferent from L
EACH
and
E
B
UC u
s
e
s
m
u
lti-
hop ro
uting.
3.5. Double
CHs
HAN
Don
g
-x
ue et al. p
r
op
ose
d
PSO-ba
s
ed
Do
uble
Clu
s
ter-he
ad
s Cl
uste
ring
Algorithm
for Wirele
ss
Senso
r
Network [14]. By using PSO
alg
o
rithm, two sensor no
de
s are sele
cted from
one clu
s
ter.
The optimal sen
s
o
r
node
serve
s
a
s
the
ma
ster CH
a
nd
sub
-
optim
al sen
s
or n
o
des
serve
s
a
s
the
vice CH. Th
e maste
r
CH
is re
sp
on
sibl
e for colle
ctin
g and fu
sin
g
data. The m
a
ster
CH
sen
d
s f
u
sed d
a
t
a
t
o
t
he v
i
ce C
H
.
The v
i
ce
CH
is re
spo
n
si
bl
e f
o
r co
mmu
nicat
i
o
n
wit
h
t
h
e
sin
k
. The fitness functio
n
is
define
d
as
Equation (11).
m
i
i
m
i
i
H
n
d
m
n
E
H
E
f
1
1
)
,
(
)
1
(
)
1
(
)
(
)
(
(11)
W
h
er
e
is
co
ns
ta
n
t
an
d
]
1
,
0
[
. E(H) i
s
th
e
re
sidual
ene
rgy
of the
CH a
n
d E(ni
) i
s
the re
sid
ual
energy of
se
nso
r
n
ode
ni
. m is th
e n
u
mbe
r
of
se
nso
r
n
ode
s
within
a
cluster.
)
,
(
H
n
d
i
is the distan
ce betwe
en th
e sen
s
o
r
nod
e ni and the
CH
H.
3.6. Optimal Number o
f
Clusters
GUO
Ji
an
et al. p
r
opo
se
d
A Parti
c
le S
w
arm
Clu
s
tering
Protocol for Wirel
e
ss Senso
r
Networks Ba
sed o
n
Opti
mal Num
b
e
r
of Cluste
rs
[15]. There
exists the o
p
timal numbe
r of
clu
s
ters in
wi
rele
ss se
nsor netwo
rks. If the num
be
r of
clu
s
ters i
s
to
o sm
all, the d
i
stan
ce of
CHs
and
CM
s is f
a
r. It lead
s to
con
s
u
m
e to
o mu
ch e
nergy. If the number
of cl
ust
e
r i
s
too bi
g, too
many CHs di
rectly se
nd d
a
ta the sink.
It cannot
sati
sfy the expected purp
o
se of the hierarchy
routing p
r
oto
c
ol.
The optimal n
u
mbe
r
of clu
s
ters i
s
com
p
u
t
ed by Equation (12
)
.
2
2
d
a
N
K
amp
fs
(12)
Whe
r
e
N is t
he total num
ber of sen
s
o
r
node
s. a is t
he edg
e leng
th of squa
re
area. d i
s
the distan
ce
betwe
en the CH an
d the si
nk.
fs
and
amp
is defined as
refe
ren
c
e [5]. The fitness
function i
s
de
fined as Equ
a
t
ion (13
)
.
Evaluation Warning : The document was created with Spire.PDF for Python.
ISSN: 23
02-4
046
TELKOM
NI
KA
Vol. 12, No. 7, July 201
4: 5484 – 54
90
5488
n
j
i
yj
i
xj
i
y
p
x
p
n
e
i
f
1
2
2
)
(
)
(
1
)
(
(13
)
Whe
r
e
1
and
]
1
,
0
[
,
. ei is the re
sid
ual ene
rgy of sen
s
or n
ode
i. (p
xj
,p
yj
) is
the positio
n informatio
n of the sen
s
o
r
no
de j.
3.7. A Ring-b
ased Clu
s
te
r
i
ng Protocol
QIN Zhi-ch
ao et al. p
r
o
posed A
Rin
g
-B
a
s
ed Clu
s
terin
g
Routi
ng
Proto
c
ol
f
o
r WSN
Usi
ng Pa
rticl
e
Swa
r
m
Opti
mization
[16]. The
entire re
gion i
s
divide
d into
a n
u
mb
er of
co
ncent
ric
circle
s
with di
fferent inte
rva
l
s. Each
ring
is di
vid
ed into
many
se
ctors. Th
ese
sect
ors a
r
e
defin
ed
as the ba
sic
units for a CH sele
ction. CHs a
r
e se
le
cted by con
s
id
ering the di
st
ance to the center
of secto
r
and
the sen
s
o
r
no
des’ resi
dual
energy.
Figure 2. The
Diagram of
Ring Routing Protocol
3.8. Discre
t
e
Particle S
w
arm Optimization
ZOU Xueyu
et al. propo
sed DPSO
-Ba
s
ed
Clu
s
terin
g
Routin
g Ap
proa
ch fo
r WSN [17].
DPSOCA
u
s
es discrete p
a
rticle
swarm
optimi
z
at
ion (D
PSO) to
c
l
us
ter
.
The fitnes
s
func
tion
mainly con
s
id
ers lo
catio
n
a
nd re
sidu
al e
nergy of neig
hbor
sen
s
o
r
n
ode
s.
3.9. Chaos
-
P
S
O
LIU Zhi
k
u
n
et
al. propo
se
d
A Clu
s
te
ring
Proto
c
ol fo
r
Wirel
e
ss S
e
n
s
or Netwo
r
ks Base
d
on Chao
s-PSO Optimi
zatio
n
[18]. PSO a
l
gorithm i
s
ea
sy to get the
l
o
cal
optimal
result. To
solv
e
the p
r
obl
em,
cha
o
s theo
ry
is intro
d
u
c
e
to PSO
al
gorithm to im
pro
v
e the
perfo
rmance
of pu
re
PSO.
Chao
s has
the cha
r
acteri
stics
of rand
om,
dete
r
minatio
n an
d reg
u
lation
whi
c
h be
nefits to
optimizatio
n
of PSO. After the algo
rithm
run
s
for
a fixed round,
cha
o
s
sea
r
ch
will be sta
r
ted. T
h
e
current optim
al result gbest w
ill be operated by chaos
cal
c
ul
ation.
The new opt
imal result g’
be
s
t
will be created. Compare t
he fitness value of g
best
with g’
best
. If the
fitness valu
e of g’
best
is better,
g’
best
will be use
s
as the gl
obal optimal
result
an
d iteration ope
ratio
n
s will
contin
ue.
3.10. QoS Routing Proto
c
ol
Xi-hua
ng Z
h
a
ng et al.
prop
ose
d
Q
o
S Base
d
Routing
in
Wirel
e
ss
Senso
r
Net
w
ork with
Particle Swa
r
m Optimization [19]. Quality of
Service (Q
oS) im
portantly
affects the net
work
routing
p
r
oto
c
ol. T
he
pap
er m
a
kes u
s
e of PSO
alg
o
rithm to
sel
e
ct the
optim
al path.
The
QoS
metrics in
clud
es time delay
, energy re
se
rve, Si
gnal Noise
Ratio (S
NR) and Ban
d
width Efficie
n
cy
Ratio (B
WER). The QoS m
e
trics is u
s
ed
as the PSO fitness functio
n
.
3.11. Multi-h
op Rou
t
ing Protocol Ba
sed upon
Weighted G
r
a
ph
Xiangho
ng
Cao et
al. p
r
o
p
o
se
d
Clu
s
ter
Hea
d
s Ele
c
tion An
alysi
s
f
o
r M
u
lti-h
op
Wirel
e
ss
Senso
r
Networks Ba
sed o
n
Weig
hted G
r
aph a
nd Pa
rt
icle Swa
r
m O
p
timization [2
0]. The proto
c
ol
is ba
sed
upo
n multi-ho
p communi
catio
n
. A directi
o
n
a
l, weighte
d
and conn
ecte
d gra
ph G
(
V,E) is
use
d
fo
r d
e
scription
of a
cl
uster of
WSN. V(G)
={V1,V
2, … ,Vn}
de
notes sen
s
or
node
s
and
E(G)
denote
s
the
edge
betwee
n
two
se
nso
r
no
de
s. Th
e protocol p
r
oceed
s to fi
nd the
optim
al
spa
nnin
g
tre
e
s of weig
hte
d
grap
h by using
PSO. Th
e optimal tre
e
s are sele
ct
ed based on
th
e
Evaluation Warning : The document was created with Spire.PDF for Python.
TELKOM
NIKA
ISSN:
2302-4
046
A Surve
y
on
Clu
s
terin
g
Ro
uting Proto
c
ol
s Base
d on P
S
O in WSN (Enyan Su
n)
5489
minimum di
st
ance. The b
e
st ro
uting
can be
se
arched fro
m
the
optimal tre
e
s
by compa
r
i
n
g
energy con
s
u
m
ption.
3.12. H
y
brid
Factor
Yubin Xu et a
l
. propo
se
d A
Clu
s
terin
g
Al
gor
ithm
of Wi
rele
ss S
e
n
s
or Networks Ba
sed
on
PSO [21]. T
o
eq
ualizi
ng
the net
work
con
s
um
pti
on,
the p
r
oto
c
ol
uses the P
S
O algo
rithm
to
optimize
cl
ustering
proc
ess by
co
nsi
d
e
r
ing th
e e
n
e
r
gy, the
com
m
unication
costs, th
e lo
a
d
balan
ce a
nd
other fa
ctors
to determin
e
the CH.
If the parti
cle
s
lo
cation
can
not
corre
s
po
nd
s
to
the sen
s
o
r
node
s locatio
n
,
they can fin
d
a near
e
s
t sensor no
de to repla
c
e. When co
nsi
d
e
r
ing
the main disa
dvantage
s of LEACH, the fitnes
s functio
n
is define
d
a
s
Equation
(1
4).
3
2
1
)
(
f
f
f
i
f
(14)
Whe
r
e
1
and
]
1
,
0
[
,
,
. The fitne
ss
function f
(
i)
mainly co
nsi
s
ts o
f
three pa
rts. F
i
rstly, the higher resi
dual e
nergy
sen
s
o
r
node h
a
s the
prio
rity to become a CH.
num
Head
num
Head
i
i
E
E
f
_
_
1
1
)
(
(15)
Hea
d_n
um i
s
the optimal
n
u
mbe
r
of
clu
s
ters
and
Ei is the resid
ual
energy of the
sen
s
o
r
node i.
E
is the
averag
e ene
rgy of sensor
node
s of the entire net
wo
rk.
Sec
o
ndly, the c
o
mmunication c
o
s
t
is
minimal within a
c
l
us
ter.
num
Head
i
i
i
ce
Dis
Num
f
_
1
2
tan
(16)
Whe
r
e
i
Num
is the numbe
r of se
nso
r
nod
es
a
t
the cluste
r i and
i
ce
Dis
tan
is the
sum
dis
t
anc
e
from the CH to CMs
.
Thirdly, the lo
ad-b
a
lan
c
e of
a cluste
r is i
m
porta
nt to save energy.
num
Head
i
i
N
Num
num
Head
f
_
1
2
3
)
(
_
(17)
Whe
r
e
N
is the averag
e num
ber of nod
es
of the entire n
e
twork.
The g
r
eate
r
value of the fitness fun
c
tion
f(
i) is, the m
o
re o
ppo
rtuni
ty the sen
s
or node
i
has.
4. Conclusio
n
Clu
s
terin
g
ro
uting p
r
oto
c
o
l
whi
c
h
is b
a
s
ed
up
on
PSO alg
o
rithm
can
bal
an
ce
energy
con
s
um
ption
of sen
s
o
r
n
o
des
of the
wh
ole net
wo
rk
a
nd extend t
h
e network life
t
ime. Comp
ared
to LEACH, th
ese p
r
oto
c
ol
s have more
perfo
rman
ce.
This p
ape
r surveys the
cl
usteri
ng routi
n
g
proto
c
ol which is ba
sed u
p
on PSO algorithm and out
li
nes the
cha
r
a
c
teri
stic
s of these proto
c
ol
s.
In the future, comp
arative studie
s
of PSO and
othe
r swarm intellige
n
ce al
gorith
m
s will go o
n
.
Referen
ces
[1]
Ak
y
i
ldiz, Ia
n
F
,
W
e
ilian Su
, Yogesh S
a
n
k
arasu
b
rama
ni
am, Erdal C
a
yirc
i.
A surve
y
on se
nso
r
networks.
Communic
a
tions m
agaz
ine, IEEE.
2002; 4
0
(8): 1
02-1
14.
[2]
Potdar, Vid
y
a
s
agar, Atif Sh
arif, Elizab
eth C
han
g.
W
i
reless
sensor
net
w
o
rks: A surve
y
.
W
A
INA'
09
.
200
9: 636-
641.
[3]
Atzori, Luigi, Antonio Iera
, Giacomo Mora
bit
o
.
T
he internet
of things: A surve
y
.
C
o
mput
er Netw
orks
.
201
0; 54(1
5
): 2787-
280
5.
Evaluation Warning : The document was created with Spire.PDF for Python.
ISSN: 23
02-4
046
TELKOM
NI
KA
Vol. 12, No. 7, July 201
4: 5484 – 54
90
5490
[4]
García Villa
lba
,
Luis Javier,
Ana Luci
l
a
Sand
oval
Oro
zco, Alicia T
r
iviño C
abrer
a, Cláu
d
ia Jac
y
Barenc
o Abb
a
s
. Routing pr
otocols i
n
w
i
re
les
s
sensor net
w
o
rks.
Sensors
. 2009; 9(1
1
): 839
9-84
21.
[5]
Heinz
e
lm
an,
W
endi B, A
n
a
n
tha P
Ch
andr
akasa
n
, Har
i
B
a
lakris
hn
an. A
n
ap
pl
ic
atio
n-s
pecific protoc
ol
architectur
e
fo
r
w
i
rel
e
ss mic
r
osens
or n
e
t
w
orks.
Wireless
Comm
unications, IEEE Transactions on
.
200
2; 1(4): 660
-670.
[6]
Chen, Ching-Yi, Fun Ye.
Particle
sw
ar
m opti
m
i
z
at
ion al
gorith
m
a
nd
its appl
icati
on t
o
clusteri
n
g
analysis.
IEEE International
Conference on Net
w
orki
ng, Sensing and Cont
rol.
2004; 2: 789-794.
[7]
Kulkar
ni, R
a
g
h
a
ven
d
ra
V, Ga
nesh
Kum
a
r V
ena
ya
g
a
moort
h
y
.
Particle s
w
arm optimization
in
w
i
r
e
less-
sensor
n
e
t
w
or
ks: a br
ief s
u
rv
e
y
.
IEEE Transactions
on A
p
plications
and
Reviews
. 2
0
1
1
;
41(2):
26
2-
267.
[8]
Kulkar
ni, R
a
g
h
a
ven
d
ra
V, Ga
nesh
Kum
a
r V
ena
ya
g
a
moort
h
y
.
Particle s
w
arm optimization
in
w
i
r
e
less-
sensor n
e
t
w
or
ks: a brief surve
y
.
IEEE Transactio
n
s on
Systems, Ma
n
,
and Cyber
ne
tics, Part C:
Appl
icatio
ns an
d Revi
ew
s
. 2011; 41(2): 2
62-
267.
[9]
Han
d
y
MJ,
Marc Haas
e, Dirk T
i
mmermann.
L
o
w
energy a
d
a
p
tiv
e
clusteri
ng
hier
archy w
i
t
h
deter
mi
nistic cluster-h
ead
s
e
lecti
o
n
. 4th
Internatio
na
l W
o
rkshop o
n
In Mobil
e
a
nd W
i
rel
e
ss
Commun
i
cati
o
n
s Net
w
ork. 20
02: 368-
37
2.
[10]
T
illett, Jason, Raghuv
eer Rao, Ferat Sahin.
Cluster-he
a
d
identific
atio
n
i
n
ad h
o
c se
ns
or netw
o
rks
usin
g partic
l
e
sw
arm opti
m
i
z
at
io
n.
IEEE International Conf
erenc
e on In Pers
onal Wireless
Commun
i
cati
o
n
s. 2002: 2
01-
205.
[11]
Lia
ng, Yi
ng,
H
a
ibi
n
Y
u
. PSO
-base
d
e
ner
g
y
effici
e
n
t g
a
the
r
ing
in
sens
or
net
w
o
rks. In
M
obil
e
A
d
-h
oc
and Se
nsor N
e
t
w
orks. Spri
ng
er, Berlin, He
id
elb
e
rg. 20
05; 3
62-3
69.
[12]
Latiff NM Abd
u
l, CC T
s
imen
idis, BS Sh
arif
.
Energy-aw
a
r
e
cluster
i
ng fo
r w
i
reless se
n
s
or netw
o
rks
usin
g p
a
rticle
sw
arm o
p
ti
mi
zation.
IEEE 1
8
t
h Internati
ona
l
S
y
m
posi
u
m o
n
In Pers
ona
l, Indoor
an
d
Mobil
e
Ra
dio
Commun
i
cati
o
n
s. 2007: 1-
5.
[13]
Jian
g, Chan
g-
Jian
g, W
e
i-Re
n
Shi, Xi
an-
lun
T
A
NG. Energ
y
-b
al
ance
d
un
equ
al cluster
i
n
g
protoco
l
for
w
i
reless sensor net
w
o
rks.
T
h
e Jo
urna
l of
C
h
in
a U
n
ivers
i
ti
es of P
o
sts an
d T
e
l
e
co
mmu
n
i
catio
n
s
. 20
10;
17(4): 94-
99.
[14]
HAN, Don
g
-
x
ue, Rui-
hu
a
Z
H
ANG, Dan-
hua
LIU.
PSO-based D
o
u
b
le C
l
uster-h
e
ads Cl
usteri
ng
Algorit
hm for W
i
reless Se
ns
or Net
w
ork.
C
o
m
p
u
t
e
r
En
gi
nee
ri
ng
. 201
0; 36
(10): 100-
10
2.
[15] GUO Jian, SUN Li-ju
an, W
A
NG
Ru-chua
n. A Particle S
w
a
rm Clusterin
g Protocol for W
i
reless Se
nso
r
Net
w
orks b
a
s
ed o
n
Optima
l Numb
er of Clusters.
Jour
nal of N
anj
in
g Univ
ersity o
f
Posts an
d
T
e
leco
mmunic
a
tions
. 20
10; 3
0
(2); 36-4
0
.
[16]
QIN Z
h
i-chao,
Z
H
OU Z
heng,
Z
H
AO Xia
o
-ch
uan. A Ri
ng-B
a
sed C
l
uste
r
i
n
g
Routi
ng Pr
otocol for W
S
N
Using P
a
rticle
S
w
a
rm Optimi
zation.
Jo
urna
l
of Beijin
g Un
i
v
ersity of Posts and Tel
e
co
mmu
n
ic
ations
.
201
2; 35(5): 26
-30.
[17]
Z
O
UXue
yu
, C
A
OYang, LIU
X
uxun, Gao
X
un
. DPSO
-Based
Clusteri
ng
Ro
uting A
ppro
a
c
h
for W
S
N.
Journ
a
l of W
u
h
an Un
iversity
. 200
8; 54(1): 99
-103.
[18]
LIU Z
h
iku
n
, LIU Z
hon
g, LI C
hao
xu. A Clust
erin
g Protoco
l
for W
i
reless S
ensor
Net
w
ork
s
Based
o
n
Chaos-PSO Optimization.
Ch
ines
e Journ
a
l o
f
Sensors an
d Actuators
. 201
1; 24(10): 1
459
-146
3.
[19]
Z
hang, Xi-
hua
ng,
W
en-b
o
Xu.
QoS base
d
routin
g in
w
i
r
e
less se
nsor
net
w
o
rk
w
i
t
h
p
a
rticle s
w
a
r
m
optimiz
ation. In
Agent Comp
u
t
ing an
d Multi-
Agent S
y
stems
,
Springer, Ber
lin, Hei
d
e
l
ber
g.
2006; 60
2-
607.
[20]
Cao,
Xi
an
gh
on
g, Hua
Z
h
a
ng,
Jun S
h
i, Gu
a
ngzh
ao
Cui.
Cl
uster h
eads
el
ection
an
alysis
for multi-
ho
p
w
i
reless sens
or netw
o
rks base
d
on w
e
i
ght
ed gr
ap
h and p
a
rticle
sw
arm opti
m
i
z
a
t
i
o
n
. F
ourt
h
Internatio
na
l C
onfere
n
ce o
n
In Natura
l Com
putatio
n, IEEE.
2008; 7: 59
9-6
03.
[21]
Xu, Yu
bin, Yu
n Ji.
A clusteri
ng al
gor
ith
m
o
f
w
i
reless sen
s
or netw
o
rks base
d
on PS
O
. In Artificial
Intelli
genc
e an
d Comp
utatio
n
a
l Intell
ige
n
ce,
Sprin
ger, Berli
n
, Heid
elb
e
rg.
201
1; 187-
194.
Evaluation Warning : The document was created with Spire.PDF for Python.