TELKOM
NIKA
, Vol.13, No
.1, March 2
0
1
5
, pp. 269~2
7
6
ISSN: 1693-6
930,
accredited
A
by DIKTI, De
cree No: 58/DIK
T
I/Kep/2013
DOI
:
10.12928/TELKOMNIKA.v13i1.1190
269
Re
cei
v
ed O
c
t
ober 2
9
, 201
4; Revi
se
d Ja
nuary 7, 201
5
Accept
ed Ja
nuary 20, 20
1
5
Grid Based Cluster Head Selection Mechanism for
Wireless Sensor Network
Khalid Ha
se
eb
1
, Kamalru
l
nizam Abu
Bak
a
r*
2
, Abdul Hanan
Abdullah
3
, Adnan Ahmed
4
F
a
cult
y
of Com
putin
g, Univ
ersiti T
e
knologi M
a
la
ysi
a
UT
M Skudai, 8131
0 Joh
o
r, Mala
ysi
a
*Corres
p
o
ndi
n
g
author, e-ma
i
l
:
khalidutm.pcrg@gmail.com
1
, k
n
iz
am@utm.my
2
, hanan@utm.my
3
,
adna
n.ahme
d
03@ya
hoo.
com
4
A
b
st
r
a
ct
W
i
reless s
ens
or netw
o
rk (W
SN) cons
ists of hun
dre
d
to th
ousa
nds s
enso
r
nod
es to g
a
th
ered th
e
infor
m
ati
on fro
m
phys
i
ca
l en
viron
m
e
n
t. Different cluster
i
n
g
base
d
al
gor
ithms h
a
ve b
e
en pro
pos
ed to
improve
netw
o
rk lifeti
m
e a
n
d
ener
gy e
fficie
n
cy. Practical
l
y
it is not fea
s
ible t
o
rech
ar
ge the
battery
of
sensor
no
des
w
hen they
are
sensi
ng th
e d
a
ta. In such
situa
t
ion e
ner
gy is c
r
ucial
reso
urce
and
it sh
oul
d
b
e
improve
d
for
li
fe spa
n
of WS
N. Cluster
he
a
d
(CH)
has
an
i
m
porta
nt rol
e
in
hier
arch
ical
en
ergy
efficie
n
t
routin
g pr
otoco
l
s bec
aus
e it r
e
ceiv
es d
a
ta fr
om no
des
an
d
sends t
o
w
a
rds
base
statio
n (
BS) or si
nk n
o
de.
T
h
is pa
per
pre
s
ents a
grid
ba
sed cl
uster h
e
a
d
sel
e
ct
io
n (GBCHS)
mec
h
a
n
is
m by
divi
di
n
g
the
netw
o
rk fie
l
d
into MXN
unif
o
rm s
i
z
e
parti
tions that
ai
ms to mi
ni
mi
z
e
the en
ergy
d
i
ssipat
i
on of
s
ensor no
des and
enh
anci
n
g
net
w
o
rk lifeti
m
e.
Simulati
on
exp
e
ri
ments
hav
e
bee
n p
e
rfor
me
d i
n
n
e
tw
ork si
mu
lator (
N
S2)
that
show
our prop
osed GBCHS
appr
oach
outp
e
rformed tha
n
standar
d cluste
ring h
i
erarc
h
y LEACH pr
otoc
ol.
Ke
y
w
ords
: clu
s
ter head, n
e
tw
ork lifetime, e
nergy re
s
ource
, base station,
grid co
nstructio
n
1. Introduc
tion
WSN
con
s
i
s
ts of several
sensor n
ode
s
with
on
e or
many sin
k
n
o
des th
at are
scattere
d
in a physi
cal
environm
ent
to sense the event
s an
d
gatherin
g d
a
ta. Senso
r
node
s sen
s
e
the
environ
ment
gatheri
ng i
n
fo
rmation, inte
g
r
ate th
e
data and sen
d
to
ward
s
BS
o
r
si
nk node.
Th
e
sin
k
in turn
queri
e
s the
sensor no
de
s for
informatio
n [1]. Manage con
n
e
c
tivity and detecti
ng
node
s o
r
lin
k failure
s i
s
dif
f
icult in u
n
st
ructured
WS
N be
cau
s
e th
e
r
e i
s
la
rge
nu
mber of no
de
s.
The
sen
s
o
r
node
s
are
tin
y
device
s
with limited
co
n
s
traint
s a
nd i
t
is n
o
t feasi
b
le in
depl
oyed
scena
rio
s
to rech
arging
the batteries. The
r
efore to decrea
s
e en
ergy consumption
an
d
prolo
ngin
g
the WSN lifeti
m
e is mai
n
desi
gn obj
ective for sen
s
or ba
se
d ap
plicatio
ns a
n
d
mech
ani
sm
s [2]. Cluster
b
a
se
d ro
uting
proto
c
ol
s de
crea
se
s net
wo
rk
com
p
lexity and give b
e
tter
routing
efficie
n
cy .That’s
why these p
r
ot
ocol
s a
r
e mo
re attractive in
the area
of WSN.
Ba
sed on
the role of se
nso
r
nod
es in
cluste
r ba
se
d netwo
rk
s can be divide
d
into four different cat
ego
rie
s
.
1)
Clu
s
ter h
ead
(CH): It is coordi
nation o
f
a group of
node
s lo
cate
d within the
boun
dari
e
s o
f
the clu
s
ter. It receive
s
, co
mpre
ss and
aggregat
e th
e sen
s
ed d
a
ta by the cluster membe
r
s
and tran
smit to next hop.
2)
Base
station (BS): It has high pro
c
e
s
sin
g
ca
p
abilitie
s and unlimite
d
sou
r
ce
of en
ergy. All the
aggregate
d
d
a
ta pro
c
e
s
se
d here a
nd th
en forward to end u
s
er.
3)
Relay n
ode
(RN): Also ca
lled gate
w
ay
node
an
d it
is
re
spo
n
sib
l
e for
relayin
g
sen
s
ed
or
aggregate
d
d
a
ta by other n
ode
s towa
rd
s the destinati
on.
4)
Gene
ral
nod
e (G
N):
The
s
e are commo
n nod
es
that
sen
s
e
d
the
p
h
ysical envi
r
onment
and
forwa
r
d the d
a
ta to their cl
uster h
ead
s (CHs).
Minimize en
ergy con
s
u
m
ption, ro
uting
overhea
d
s
an
d colli
si
ons
are
so
me main
advantag
es o
f
clu
s
ter ba
se
d routin
g
protocol
s. In
clu
s
t
e
ring
me
ch
an
ism th
e role
o
f
sen
s
o
r
nod
e
s
are divid
ed in
to CH,
relay
node, g
ene
ra
l node
and B
S
catego
rie
s
.
The two mai
n
cate
gori
e
s
of
clu
s
terin
g
m
e
ch
ani
sms in
WS
N a
r
e
st
atic a
nd
dyn
a
mic.
Wh
en
clu
s
ters
are
formed
in
st
atic
mech
ani
sm then they rem
a
in sam
e
through
out of
WSN lifetime but in dynamic the role of CHs
are rotated
among
sen
s
or nod
es to
prolon
g the
network life
t
ime and bal
ance the en
ergy
con
s
um
ption.
Clu
s
ter b
a
se
d routin
g protocol
s u
s
e
s
single a
nd mult
i hop me
ch
an
isms. M
u
lti h
op
comm
uni
cati
on p
r
olon
gs e
nergy
efficien
cy and
net
wo
rk lifetime
so
it shoul
d be
a
dopted [3].
Due
to sen
s
o
r
n
ode’
s limited
con
s
traints adho
c
r
outi
ng p
r
oto
c
ol
s are
not fe
asibl
e
for
WSN
Evaluation Warning : The document was created with Spire.PDF for Python.
ISSN: 16
93-6
930
TELKOM
NIKA
Vol. 13, No. 1, March 2
015 : 269 – 2
7
6
270
appli
c
ation. Limited
co
nstraint
s of se
nso
r
nod
es
have po
sed
many re
sea
r
ch proble
m
s for
prolo
ngin
g
WSN lifetime.
WSN
con
s
i
s
t numbe
r of node
s with li
mited memo
ry, proce
s
sing
, powe
r
and
energy
resou
r
ces.
Due to
su
ch
li
mited resource
s mo
ni
tori
n
g
the i
n
tere
sted phy
sical
environ
ment
by
nume
r
ou
s
se
nsin
g devi
c
e
s
for a lo
ng p
e
r
iod of time
make
s it a
ch
allengin
g
ta
sk. Saving e
n
e
rgy
to enh
an
ce t
he n
e
two
r
k’
s
lifetime is
a
critical
proble
m
in
WSN an
d therefore “h
ow to
en
han
ced
and imp
r
ove
the WSN lif
etime” is
a cruci
a
l qu
estio
n
. The pri
m
a
r
y obje
c
tive of WSN i
s
d
a
ta
colle
ction an
d transmissio
n. Free spa
c
e and mult
ip
ath fading are two types
of models in
for
WSN.
The
r
e i
s
a
n
online
a
r
relation
shi
p
b
e
twee
n e
a
ch
node
in
term
s of the
en
erg
y
con
s
u
m
ptio
n
of wireless
communi
catio
n
. The e
nerg
y
con
s
um
ptio
n of free
sp
a
c
e m
odel i
s
much
sm
aller than
that of multip
ath fadin
g
m
odel.
Whe
n
sensor
nod
e i
s
fa
r a
w
ay from BS, it ma
y be run
out
of
energy sho
r
tl
y that would lead to quality
redu
ction of netwo
rk [4].
Dynami
c
hierarchical routi
ng proto
c
ol L
EA
CH [5] co
nsi
s
ts of sev
e
ral round
s a
nd ea
ch
singl
e ha
s se
tup and
stead
y phase
s
. All sen
s
o
r
no
de
s con
s
ist of ho
mogen
eou
s
structu
r
e. CH i
s
sele
cted in
setup pha
se a
nd then dyna
mically differ
ent clu
s
ters a
r
e form
ed. Ea
ch cl
uste
r ha
s its
local CH an
d sen
s
o
r
nod
es. Selected CH sen
d
s a
n
advertise
d me
ssage to all node
s and no
d
e
s
respon
se o
n
that receive
d
messag
e. After
re
ceiving a
ll the data from node
s CH
aggregate a
n
d
comp
re
ss the
m
and tran
sf
er to sin
k
nod
e. LEACH sel
e
cts the
CH
perio
dically. Ran
dom nu
m
ber
is ge
nerated
by each nod
e
and the
node
will be
sele
ct
ed a
s
CH if this ra
ndo
m nu
mber i
s
small
e
r
than predefin
e thre
shol
d value. The p
r
e
define val
ue
set to ze
ro if this sa
me no
de ha
s ele
c
t
e
d
again
a
s
a
CH fo
r
same
round.
In
ste
ady ph
ase T
D
MA i
s
u
s
e
d
so
that eve
r
y membe
r
no
de
sen
d
data to
CH
wh
en receive its o
w
n t
i
me slot. Th
e
threshold fo
rmula for
LEACH i
s
sho
w
n
in
eq 1.
0
∈
(1)
P shows the
desi
r
ed p
e
rce
n
tage of CHs,
r denote
s
the
current roun
d, and G is th
e set of
node
s that ha
ve not been e
l
ected a
s
CHs in the last 1
/
p round.
LEACH-B propo
sed that
the proto
c
ol
need
s to
en
sure that the
partition of
cl
uster i
s
balan
ce a
nd
uniform to
sa
ve the ene
rg
y con
s
um
ptio
n amon
g nod
es a
nd to pro
l
ong the lifeti
m
e
of the netwo
rk. To accom
p
lish this o
b
je
ctive,
the number of CHs n
eed
s to be do
minated an
d the
network needs an
optimal
CHs. Authors in [6] have proved
that WSN will be energy efficient
if
the net
work
has bet
ween
3 an
d 5
cl
u
s
ters from th
e total 10
0
sensor
no
de
s. It mean
s t
he
optimal percentage of CHs rang
e fro
m
3% to
5%. LEACH-B improve
d
the
original LEA
C
H
algorith
m
by takin
g
the nod
e’s re
sid
ual e
nergy
into co
nsid
eratio
n a
nd ke
eping th
e con
s
tant an
d
near o
p
timal
numbe
r of CHs at ea
ch
ro
und.
Powe
r efficie
n
t Gatheri
ng i
n
Sensor Info
rm
ation Syst
ems
(PEGASIS) [7] is an i
m
prove
d
versio
n of LEACH. It forms a ch
ain
of group
of sensor no
de
s and ea
ch n
o
de tran
smits
and
receives d
a
ta
from its nei
ghbo
r nod
es and take
s turn bei
ng a l
eade
r for tra
n
smi
ssi
on to
the
destin
a
tion. Only one no
de ca
n send
the data to
destinatio
n at a time. Gathere
d
data
i
s
aggregate
d
a
t
the se
nsor
node
s
whe
n
it move
s fro
m
nod
e to n
ode. PEGASIS works o
n
two
step
s to con
s
tru
c
t the ch
ain. Firstly sensor
no
de
s and BS are
self org
ani
zed with g
r
ee
dy
algorith
m
an
d se
co
ndly af
ter the
chai
n
con
s
tru
c
tion
BS broa
dcast
the informati
on to all
se
n
s
or
node
s.
Authors p
r
op
ose
d
[8]
clu
s
ter
ba
sed
k-m
ean
s p
r
otoc
ol to form the
k
-
c
l
us
ters
of
objec
ts
based o
n
the
eu
clidea
n di
stan
ce. Initiall
y the CH
s are selecte
d
o
n
the ba
si
s of
rand
om n
u
m
ber
as
in
LEACH to form the
i
n
itial cl
uste
rs. Then
after the fo
rmat
ion of
initial clusters,
centroi
d
is
determi
ned t
o
find the
ce
nter lo
catio
n
of ea
ch
clu
s
ter a
nd th
e n
ode i
s
sele
ct
ed a
s
a
ne
w CH
whi
c
h i
s
cl
oser to
cent
roi
d
. The
role
o
f
CH i
s
rotated when
ene
rgy is
drai
n
out from
ce
rtain
energy thre
shold. It prolo
ngs n
e
two
r
k
lifetim
e and energy efficiency of WS
N than prop
ose
d
s
c
hemes
[5],[9].
Hybrid
Ene
r
gy-Efficient
Distri
buted
cl
uste
ri
ng
(HEED) [9] i
s
a
nother cl
uste
r ba
se
d
routing
p
r
oto
c
ol
and
ba
se
d on
multi h
o
p
ap
pro
a
ch t
o
prolon
g the
ene
rgy effici
ency
and
WSN
lifetime. Resi
dual e
nergy of node
s a
n
d
intra
co
mmu
nicatio
n
cost
are m
a
inly two p
a
ra
mete
rs
have been u
s
ed in this app
roa
c
h for the
sele
cti
on of CH am
ong
sensor no
de
s. HEED provi
des
Evaluation Warning : The document was created with Spire.PDF for Python.
TELKOM
NIKA
ISSN:
1693-6
930
Grid Ba
sed
Cluster
Hea
d
Selectio
n Mechani
sm
for Wirele
ss Se
nsor Netwo
r
k
(Kh
a
lid Ha
se
eb)
271
even dist
ribut
ion of CHs a
nd the chan
ces for tw
o
no
des within sa
me
com
m
uni
cation ran
ge can
be sel
e
ct
e
d
a
s
C
H
s i
s
v
e
ry
low.
Grid
ro
uting
proto
c
ol
(G
ROUP
) [10] provides
scalab
ility and
efficient packet
s
d
e
livery in
large
re
gion
of WSN. It a
r
rang
es all th
e nod
es
dyn
a
mically i
n
di
fferent region
s
called
cl
ust
e
rs
and ea
ch
clu
s
ter h
a
s its
o
w
n CH. Virtu
a
l grid i
s
ma
de by all sel
e
cted
CH
s.
One of the si
nks
proa
ctively a
nd dyn
a
mical
l
y build
s g
r
id
s fo
r forwa
r
di
ng q
uery
me
ssage
s
and
data p
a
cket
s. It
improve
d
net
work lifetime
and en
ergy
efficien
cy by balance th
e ene
rgy loa
d
amon
g se
nso
r
node
s a
s
co
mpare to LEACH.
A Ne
w
Routi
ng Protocol f
o
r Efficie
n
t a
nd Se
cu
re
WSN [11] im
proves
network lifetime
and ene
rgy e
fficiency . It is rou
nd ba
se
d scheme a
n
d
netwo
rk a
r
ea is divided
into a numbe
r of
squ
a
re
s,
e
a
ch
ha
s sam
e
numbe
r node
s.
Squa
re
s remain sa
me and do not chang
e
in
eve
r
y
roun
d. A sq
u
a
re i
s
a
clu
s
t
e
r an
d all
clu
s
ters d
o
not
cha
nge i
n
all
roun
ds. A
cl
uster con
s
ist
s
of
four c
e
lls
.
CHs
are
elec
ted in
eac
h
c
e
ll at
the s
t
art
of new
round.
Data is send towards
s
i
nk
node
in multi h
op
manne
r. To
p
r
ovide
se
cu
re
com
m
uni
cati
on am
ong
no
des,
setu
p se
rver
distri
bute
s
different m
a
n
ageme
n
t keys in
ea
ch
rou
nd. It balan
ces th
e en
erg
y
con
s
um
ptio
n amo
ng
sen
s
o
r
node
s an
d gi
ves se
cu
re communi
catio
n
mech
ani
sm
for WSN.
In energy efficient
clu
s
teri
ng sch
e
me
(EEC
S) [12] candid
a
tes
no
des
com
pete
for the
ability to elevate to CH for a current round. Each
round has fixed time inte
rval and re-clusteri
n
g
occurs at the
start of next round. In this app
roa
c
h
candid
a
te nod
es broad
ca
st
their re
sidu
a
l
energy to neighbo
ring no
d
e
s. If a given
node do
es n
o
t
find a node with more residual ene
rgy, it
become
s
a
CH. EE
CS u
s
e
different
way for cl
ust
e
r fo
rmation
than LEA
CH.
LEACH pe
rf
orm
s
clu
s
ter form
ul
ation based o
n
the minimu
m distan
ce
of
sen
s
or n
ode
s to their co
rresp
ondi
ng CH.
EECS extend
s LEA
C
H p
r
ot
ocol
by dyn
a
m
ic
si
zing
of
clu
s
ters
base
d
on
cl
uste
r
d
i
stan
ce f
r
om t
h
e
BS.
Authors in [1
3] prop
osed
clu
s
ter b
a
sed
energy
effici
ent routin
g p
r
otocol (CBE
RP) fo
r
prolo
ngin
g
n
e
twork lifeti
m
e an
d e
n
e
rgy e
ffici
en
cy by
comb
ining LEA
C
H a
nd PEG
ASIS
approa
che
s
.
Clu
s
terin
g
p
r
oce
dure i
s
same a
s
i
n
L
EACH i.e
ba
sed
on
ra
ndo
m num
ber CH i
s
sele
cted am
o
ng se
nsor no
des
while
ch
ain is co
n
s
tru
c
ted u
s
ing P
E
GASIS. All
node
s send t
heir
energy info
rmation to BS
for
CHs
sel
e
ction. Ba
sed
on the
hig
h
e
s
t en
ergy l
e
vel BS sele
cts four
CHs. The
hi
ghe
st ene
rgy
level node
is consi
d
e
r
e
d
as first CH and th
e rest a
s
sumed
as
can
d
idate no
des. Whe
n
e
nergy
level of
sele
cted
CH is d
r
ain d
o
wn by define
d
energy limit the
next ca
ndidat
e no
de i
s
sel
e
cted
a
s
n
e
w CH. To fo
rward th
e d
a
ta t
o
BS greedy
algorith
m
i
s
u
s
ed
to form
chain.
Ta
ble
1
pre
s
ent
s the
su
mmary
of
cl
u
s
terin
g
ba
sed
ene
rgy
effici
ent sch
e
me
s
that
have discu
ssed in this sect
ion.
Table 1. Meth
odolo
g
y and
Problem
s of Different
Cl
ustering Ba
sed
Energy Efficient Schem
es
Energ
y
Ef
ficient
Protocols in WS
N
Methodolog
y
of CH Election
Issues
LEACH
Probabilistic bas
ed
Predefined C
H
s and residual
energ
y
is not considered for C
H
selection
LEACH-B
Random num
ber
and
residual energ
y
High Energ
y
con
s
umption due to
single hop.
PEGASIS
Gree
d
y
me
thod
Long latenc
y
,no
energ
y
and BS
location consideration while
electing the CH
K-means CH
selection
Euclidean
Single hop and clustering
overheads
HEED Residual
energ
y
and
intra communication
cost.
Energ
y
dissipatio
n
overheads
GR
OUP
Distance
Periodically
reco
nstruct data
aggregation t
r
ee
Routing Protocol
for Efficient and
Secure WSN
Random num
ber
Overhea
ds due t
o
ke
y
s
distribution
EECS Node
residual
energ
y
Energ
y
dissipatio
n ,Overhe
ads on
nodes due to glo
bal information
aggregation
CBERP
Residual energ
y
Overhea
ds and n
o
t suitable for
lar
ge scale WSN
Evaluation Warning : The document was created with Spire.PDF for Python.
ISSN: 16
93-6
930
TELKOM
NIKA
Vol. 13, No. 1, March 2
015 : 269 – 2
7
6
272
It is
diffic
u
lt for
s
e
ns
or nodes
to maint
a
in
their en
e
r
gy level u
n
iformly thu
s
it
redu
ce
s
netwo
rk lifetime a
nd
ene
rgy efficien
cy. Becau
s
e ne
twork’s
life
c
ycle dep
end
s on
the
alive of
node
s
so to
cho
o
se the
suitable
CHs
among
se
nso
r
no
de i
s
the
main resea
r
ch
chall
eng
e
for
c
l
us
tering protoc
ols
.
Sev
e
ral
propos
ed c
l
us
ter based routing
protoc
ols
for
WSN [5],[7],[9],
[14]
empha
si
ze
s
on minimi
zin
g
the ro
uting o
v
erhea
ds and
ene
rgy u
s
ag
e of the
sen
s
or n
ode
s b
u
t still
the issue is unable to p
r
event co
mpl
e
tely [
15]-[17]. Design of
energy ware clu
s
ter ba
se
d
mech
ani
sm is an key re
sea
r
ch p
r
o
b
lem for prolon
g WSN lifetime and efficien
cy [18]. The rest
of
the re
se
arch
pape
r i
s
o
r
ga
nize
d a
s
follo
ws.
Our GB
CHS
app
roa
c
h i
s
p
r
e
s
e
n
ted in
se
ction
2
.
Re
sea
r
ch m
e
thod i
s
sho
w
n in
sectio
n 3. Simulati
on results a
n
d
discu
s
sion
s a
r
e
cove
re
d in
se
ction 4. Section 5 con
c
lu
des the p
ape
r and su
gge
st
s for future
work.
2. Proposed
Metho
d
In this
se
ctio
n we p
r
e
s
ent
detaile
d de
scriptio
n of
ou
r p
r
op
osed
G
B
CHS, in
clu
d
i
ng h
o
w
to pa
rtition th
e sen
s
ing
fiel
d into
unifo
rm
si
ze
sq
ua
re
grid
s a
n
d
ho
w to
sel
e
ct
CH in
ea
ch
g
r
i
d
for
prolo
ngin
g
life spa
n
of network an
d ene
rgy efficien
cy
. Proposed
m
e
ch
ani
sm
is divided into two
main p
h
a
s
e
s
. One i
s
i
n
itial
clu
s
teri
ng
a
nd the
othe
r
one i
s
d
a
ta transmi
ssion. I
n
itial clu
s
te
ri
ng
con
s
i
s
ts of g
r
ids
co
nstruct
i
on,
CHs
sel
e
ction a
nd T
D
MA sch
edul
ing whil
e pa
ckets fo
rwarding
from CHs to
wards
de
stin
ation o
c
curs i
n
data tra
n
smissi
on p
h
a
s
e. Before g
o
i
ng to de
scrib
e
our
GBCHS, we highlight the
variou
s assu
mp
tions fo
r WSN that are
as follows.
i.
All nodes a
r
e
deploye
d
ran
domly and re
main static.
ii.
Senso
r
no
de
s have same
initial energy level.
iii.
BS has location inform
atio
n of all sen
s
o
r
node
s.
iv.
CHs are re
sp
onsi
b
le to se
nd
their mem
bers data toward
s BS.
v.
All nodes
will use the
same
radio chan
ne
l for comm
uni
cation
with ea
ch othe
r.
vi.
All the nodes
comm
uni
cate
via a share
d
bidire
ction
a
l wirel
e
ss chan
nel.
The algo
rithm
of our pro
p
o
s
ed GB
CHS i
s
discu
s
sed i
n
detail as foll
ows:
Step 1:
Sup
pose
that
n numbe
r of sensor
no
de
s is ra
ndo
mly depl
oyed i
n
network
sen
s
in
g field.
At the
start o
f
simulatio
n
round,
every
sensor
nod
e
send it
s lo
cati
on info
rmatio
n to
BS and prop
ose
d
sche
me
initiates the
pro
c
ed
ure
to dynamically d
i
vide the entire netwo
rk field
into K uniform size
squa
re grid
s base
d
on numbe
r of deployed
nodes a
nd netwo
rk
size. BS
stru
ctures th
e sen
s
or fiel
d into e
qual
size of
ro
ws
and
colu
mn
s in o
r
de
r to f
o
rm
uniform
size
grid
s. All con
s
tru
c
ted g
r
id
s are of
same
size and
ea
ch one i
s
con
s
idere
d
a
s
a si
ngle
cluste
r.
To
control the communi
catio
n
within g
r
id
s and re
du
ce
s energy dissi
pation am
on
g sen
s
o
r
no
d
e
s,
one no
de is
sele
cted a
s
CH to forwa
r
d the aggreg
ated data to
wards
sin
k
n
ode or BS.T
h
e
p
r
oc
es
s o
f
g
r
id
co
ns
tr
uc
tion
a
n
d
c
l
us
te
rs
for
m
a
t
ion
i
s
executed
onl
y once time
i
n
enti
r
e lifeti
m
e
of WSN in order to minimi
ze the en
ergy
con
s
umptio
n
and re
-cl
u
ste
r
ing ove
r
he
ad
s.
Step 2:
After the con
s
tru
c
tion of unifo
rm si
zed
sq
u
a
re
grid
s, o
u
r
p
r
opo
se
d
GBCHS
initiate the CHs ele
c
tion
procedu
re
within
gri
d
s.
It prolong
s network life
t
ime and en
ergy
efficien
cy because only few node
s com
e
for electio
n
proce
s
s due to
grid con
s
tru
c
t
i
on.
Step 3:
BS
d
e
termin
es th
e centre p
o
in
t for e
a
ch g
r
i
d
an
d all
sen
s
or n
ode
s
de
termine
their di
stan
ce
from it. Based on the mi
nimum di
stan
ce fro
m
gri
d
centre, GBCHS assig
ned
a
prio
rity ID to
all nodes a
nd arrang
e them in li
near fashion. Fin
a
lly, in each grid the nod
e is
sele
cted a
s
a
CH who
s
e di
stan
ce is very
closest to ce
ntre point.
Step 4:
In
order to
re
ceive
and
agg
reg
a
t
e the dat
a
from sen
s
or no
des,
all sele
cted CHs
anno
un
ce th
e
i
r lo
cal
TDMA sche
dule. E
a
ch
se
ns
or no
de
sen
d
s its sense d
a
ta to
wards
CH wh
en
it rec
e
ives
time s
l
ot.
Step 5:
Seve
ral p
r
op
osed
energy efficie
n
t schem
es
consi
s
t of rou
nds
and
pe
ri
odically
perfo
rmed
re
-clu
sterin
g me
cha
n
ism to
ro
tate the role
of CHs amo
n
g
sen
s
o
r
no
d
e
s for b
a
lan
c
i
n
g
the ene
rgy
consumption.
But due to
re-cl
u
st
e
r
in
g pha
se, su
ch approa
che
s
degrade
net
work
lifetime and
i
n
crea
sing
co
mmuni
cation
overhe
ad
s.
In
our propo
se
d GBCHS, we rotate
the
role
of CH by usi
n
g roun
d ro
bin
method.
Step 6:
Each
CH
ha
s give
n p
r
e
s
et time
pe
riod
an
d
whe
n
it
expires, BS
ele
c
ts the
next
node
as
ne
w CH th
at ha
s
highe
st pri
o
rit
y
i.e relative
ly closer to g
r
id ce
ntre. In t
h
is
way eq
ua
lly
energy co
nsumption i
s
di
stribut
e
d
am
ong
sen
s
o
r
node
s. To
synch
r
oni
ze th
e com
m
uni
cation
Evaluation Warning : The document was created with Spire.PDF for Python.
TELKOM
NIKA
ISSN:
1693-6
930
Grid Ba
sed
Cluster
Hea
d
Selectio
n Mechani
sm
for Wirele
ss Se
nsor Netwo
r
k
(Kh
a
lid Ha
se
eb)
273
among
sen
s
o
r
no
de
s, prop
ose
d
scheme
upd
ates
th
e
TDMA
sched
ule eve
r
y time when it
ele
c
t
s
new
CH a
nd
all node
s are informe
d
.
Step 7:
En
ergy is hi
gh
ly consume
d
in singl
e hop a
s
co
mpare to m
u
lti hop
comm
uni
cati
on. So dista
n
c
e i
s
the on
e
of main
fact
or that re
du
ces n
ode’
s en
ergy rapidly
and
degrade
s life
span of WSN. Therefo
r
e to ov
erco
me this issu
e, GBCHS adopt multi hop
comm
uni
cati
on mode fo
r data forwardi
ng towa
rd
s BS.
Step 8:
Wh
enever
CH
need
s to se
nd data the
n
determi
ne
the node
s arou
nd its
surro
undi
ng. It finds the distan
ce with BS and
closest surroundi
ng
CH. Based
on the minim
u
m
distan
ce,
dat
a is fo
rward t
o
wa
rd
s d
e
sti
nation i.
e either
th
ro
ugh clo
s
e
s
t
next hop or dire
ctl
y
to
BS.
3. Rese
arch
Metho
d
In this secti
on we prese
n
t our
simul
a
tion mod
e
l
that has
be
en u
s
ed in
different
experim
ents
by usin
g well
kno
w
n to
ol n
e
twork
si
mul
a
tor (NS2) [19]
. We rand
oml
y
deployed
1
0
0
sen
s
o
r
no
de
s within sen
s
o
r
field of 10
0
X 100 dime
nsio
ns. Ene
r
gy model a
s
sume
d a
s
be
ing
use
d
in [5]
a
nd a
co
nsi
d
e
r
ed f
r
ee
sp
ace ra
dio
p
r
o
p
a
gation m
odel.
The
system
para
m
eters t
hat
have be
en u
s
ed in expe
rim
ents a
r
e
sho
w
n in T
able
2
.
We compa
r
ed ou
r p
r
opo
sed
GBCHS
with
LEACH p
r
oto
c
ol with resp
ect to numbe
r of alive sen
s
or n
ode
s, total network remainin
g ene
rgy
and net
work throu
ghp
ut pe
rforma
nce pa
ramete
rs.
Table 2. System Param
e
te
rs
Parameter Value
Net
w
ork a
r
ea
100*100m
Nodes 100
Initial energ
y
5J
Deplo
y
ment
Randoml
y
Data packet size
512 b
y
t
e
s
Position
Static
Channel T
y
pe
Wireless
Communication Bi
directional
Base station energ
y
100
Energ
y
Model
Batter
y
Transpo
rt la
y
e
r p
r
otocol
UDP
Simulation time
600sec
4. Results a
nd Discu
ssi
on
In this se
ction we u
s
ed
different pa
ramete
rs to
evaluate the
perform
an
ce of our
prop
osed G
H
CHS ap
proa
ch with stan
da
rd hie
r
ar
chy
clusteri
ng LEA
CH p
r
oto
c
ol.
The sim
u
lation
results of ou
r perfo
rmed ex
perim
ents a
r
e
sho
w
n a
s
follows.
4.1. Number
of Aliv
e Sen
s
or Nod
es
Network lifetime is an im
port
ant fa
ctor to evaluate the perfo
rma
n
ce of
clu
s
te
r ba
se
d
energy efficie
n
t scheme. T
he no
de can
sen
s
e
and
s
end d
a
ta toward
s its d
e
sti
nation until it
is
alive and
sta
b
le. We
pe
rfo
r
med
expe
ri
ment to
dete
r
mine the
num
ber
of stabl
e
node
s o
n
reg
u
lar
interval b
a
si
s i.e at the
e
nd of 1
00
se
con
d
s and
Fi
gure
1
sh
ows that
our propo
sed
GBCHS
m
e
chani
sm
gives b
e
tter perce
ntage
of alive n
o
des a
s
com
pare
to LEA
C
H be
cau
s
e
of
distrib
u
ting th
e CHs i
n
unif
o
rmly way an
d avoid t
he
re-cl
u
ste
r
in
g p
r
ocess to
rot
a
te the role
of
CHs am
ong
sen
s
o
r
nod
e
s
thus in
crea
sing n
e
tw
o
r
k stability peri
od and life span of netwo
rk.
Duri
ng sim
u
l
a
tion experim
ent, we con
s
i
dere
d
nod
e a
s
dea
d and u
n
stabl
e whe
n
its energy le
vel
reac
hes
to 0J.
Evaluation Warning : The document was created with Spire.PDF for Python.
ISSN: 16
93-6
930
TELKOM
NIKA
Vol. 13, No. 1, March 2
015 : 269 – 2
7
6
274
Figure 1. Nu
mber of alive
sen
s
o
r
nod
es over simul
a
tion time
4.2 Net
w
o
r
k
Remaining E
n
erg
y
Energy is ve
ry restri
cted a
nd main
re
so
urce
in
WSN.
Therefore to
minimize th
e
energy
con
s
um
ption
among
sen
s
or n
ode
s i
s
one
of the
m
a
in o
b
je
ctives fo
r d
e
sig
n
i
ng
clu
s
ter
ba
sed
scheme
s
.
We pe
rformed
sim
u
lation
experim
ent f
o
r m
onitori
n
g
the
statu
s
of total
net
work
remai
n
ing
en
ergy at th
e e
nd of
reg
u
lar
time in
terval
s and it i
s
p
r
o
v
en in Fi
gure
2 that p
r
op
o
s
ed
GBCHS
m
e
chani
sm
gives better outco
me to balan
ce the energy usa
ge betwe
en se
nso
r
no
des
as compa
r
e t
o
LEACH p
r
o
t
ocol.
Figure 2. Net
w
ork remaini
ng ene
rgy over sim
u
lation
time
4.3
Net
w
o
r
k Through
put
Network thro
ughp
ut mean
s
ho
w ma
ny data pa
ckets have bee
n send by CHs towa
rd
s
destin
a
tion i.
e si
nk no
de
or BS. In
sin
g
le h
op,
CHs directly
sen
d
their ag
gre
g
a
ted d
a
ta to
sin
k
node
an
d du
e to di
stan
ce
facto
r
they
con
s
um
e
e
n
e
rgy
rapi
dly thus mo
stly d
a
ta pa
ckets
are
drop
ped. To i
n
crea
se the netwo
rk th
ro
ughp
ut, our propo
se
d GBCHS
m
e
cha
n
i
sm
has ado
pted
10
0
15
0
20
0
25
0
30
0
35
0
40
0
45
0
50
0
55
0
600
65
70
75
80
85
90
95
10
0
N
u
m
ber
o
f
A
l
i
v
e
N
o
de
s
S
i
mu
la
t
i
o
n
T
i
me
(
S
e
c
s
)
S
e
n
s
or
N
o
de
s
L
EAC
H
GB
C
H
S
100
150
200
250
300
350
400
450
500
55
0
600
150
200
250
300
350
400
450
500
T
o
t
a
l
N
e
t
w
or
k
R
e
m
a
i
n
i
ng E
n
er
gy
S
i
mu
la
t
i
o
n
T
i
me
(
S
e
c
s
)
E
nergy
(J
ou
l
e
s
)
LE
A
C
H
GB
C
H
S
Evaluation Warning : The document was created with Spire.PDF for Python.
TELKOM
NIKA
ISSN:
1693-6
930
Grid Ba
sed
Cluster
Hea
d
Selectio
n Mechani
sm
for Wirele
ss Se
nsor Netwo
r
k
(Kh
a
lid Ha
se
eb)
275
multi hop co
mmuni
cation
and data i
s
transfe
rri
ng by
closest CH t
o
sin
k
nod
e. Figure 3 sh
o
w
s
that prop
ose
d
app
roa
c
h
gives b
e
tter
data delive
r
y rate at de
stination en
d
as
comp
are
to
LEACH.
Figure 3. Nu
mber of sendi
ng pa
ckets to
wards BS
5. Conclusio
n
Energy
dissip
ation i
s
m
a
in
factor in
WS
N fo
r p
r
ol
ong
ing lifetime.
Clu
s
terin
g
te
chni
qu
e
s
are mainly
used to effectiv
ely utilize the energy
resource. GB
CHS
divides
the network field i
n
to
uniform
squ
a
re si
zed g
r
id
s
and ea
ch
grid
is co
nsi
dere
d
as a
sin
g
le
clu
s
ter. On
e
node i
s
sele
cted
as
CH in
ord
e
r to
agg
reg
a
t
e the me
mb
er’s data
a
n
d
forward towa
rds BS. Ro
le
o
f
CH
is
ro
ta
te
d
among
sen
s
or nod
es by
round
robi
n fashio
n inside e
a
ch grid to balan
ce the en
ergy
con
s
um
ption.
Ou
r p
r
op
osed
scheme
h
a
s
eliminat
ed r
e
-
c
lu
s
t
er
in
g p
r
oc
ed
ur
e
afte
r
th
e
e
n
d
o
f
regul
ar interval thus it red
u
ces communi
catio
n
overhea
ds and
ene
rg
y con
s
um
ption
.
Furthe
rmo
r
e
based o
n
mi
nimum di
sta
n
ce, m
u
lt
i h
op route i
s
adopte
d
for
data forwa
r
di
ng
towards d
e
sti
nation. Simul
a
tion re
sults
sho
w
that propo
sed GB
CHS mechani
sm outperfo
rm
ed
than stand
ard LEACH pro
t
ocol in te
rm
s of different para
m
eters. In
future wo
rk, we will further
improve th
e
perfo
rman
ce
of GBCHS m
e
ch
ani
sm by
grou
ping th
e
sen
s
o
r
no
de
s to form en
ergy
awa
r
e an
d ba
lanced cl
uste
rs.
Referen
ces
[1]
Potdar V,
Shar
if A, Ch
an
g E.
W
i
reless s
ens
o
r
netw
o
rks: A s
u
rvey
. Adv
anc
ed Inform
atio
n
Net
w
orki
n
g
and Ap
plic
atio
ns Workshops,
2009 WAINA'0
9
Internatio
na
l Confer
ence
on
, IEEE, 2009.
[2]
Lu Z
Q, W
ang
LG, Shan J.
R
e
searc
h
o
n
a
n
Improved W
i
r
e
l
e
ss Sens
or N
e
t
w
orks
Cl
usteri
ng Prot
ocol.
T
E
LKOMNIKA Indon
esi
an Jou
r
nal of Electric
al Eng
i
ne
eri
n
g
.
2013; 1
1
(10):
598
0-5.
[3]
Mhatre V, Rosenb
erg C. Des
i
gn g
u
id
eli
nes
fo
r
w
i
r
e
less sensor net
w
o
rks: communication, clustering
and a
ggr
egati
o
n.
Ad hoc netw
o
rks
. 2004; 2(
1
)
: 45-63.
[4]
Che
n
Z
,
Xia
o
Y, Li X, Li R.
A Clusteri
ng
P
r
otocol for W
i
r
e
less Se
nsor
Net
w
orks Bas
ed on E
nerg
y
Potentia
l F
i
eld.
T
he Scientific
W
o
rld Jour
nal
. 201
3.
[5]
Heinz
e
lm
an W
R
, Cha
ndr
aka
s
an A, Ba
lakri
s
hna
n H.
En
erg
y
-e
ffi
ci
en
t comm
un
i
c
a
t
io
n pro
t
o
c
o
l
fo
r
w
i
reless micro
s
ensor n
e
tw
orks
. Sy
st
em Scienc
es, 200
0
Proceed
in
gs of the 33rd A
nnu
al Ha
w
a
i
i
Internatio
na
l C
onfere
n
ce o
n
, IEEE. 2000.
[6]
Heinz
e
lm
an W
B
, Cha
ndrak
as
an AP, B
a
lakr
i
s
hna
n H.
A
n
a
pplic
atio
n-sp
ec
ific protoc
ol
arc
h
itecture
for
w
i
reless microsensor net
w
or
ks.
Wireless Communic
a
tions
,
IEEE Transactions on
. 200
2; 1(4): 660-
70.
[7]
Lin
d
se
y S, Ra
ghav
en
dra CS
.
PEGASIS: Power-efficient
gather
ing
in s
ensor infor
m
ation system
s
.
Aerosp
ace co
n
f
erence pr
oce
e
d
in
gs, 200
2 IEEE. 2002.
0
50000
100000
150000
200000
250000
300000
350000
LEACH
G
BCHS
Data
(bps)
Data
Delivery
Rate
at
BS
Evaluation Warning : The document was created with Spire.PDF for Python.
ISSN: 16
93-6
930
TELKOM
NIKA
Vol. 13, No. 1, March 2
015 : 269 – 2
7
6
276
[8]
Park GY, Kim H, Jeon
g HW
,
Youn
HY.
A
N
o
vel Cluster H
ead
S
e
l
e
ction Method bas
ed on
K-Me
an
s
Algorit
h
m
for Energy Effici
e
n
t W
i
reless S
ensor N
e
tw
ork.
Ad
va
n
c
ed
Info
rma
ti
o
n
Ne
tw
orki
ng
an
d
Appl
icatio
ns Worksho
p
s (WAINA), 2013 2
7
th
Internation
a
l C
onfere
n
ce o
n
, IEEE. 2013.
[9]
Youn
is O, F
a
h
m
y
S.
HEED:
a h
y
b
r
id,
en
er
g
y
-
e
fficie
n
t, di
stributed
cl
usterin
g
a
ppr
oac
h for
ad
h
o
c
sensor n
e
t
w
ork
s
.
Mobile Computing, IEEE Tr
ansactions on
. 200
4; 3(4): 366
-79.
[10]
Yu L, W
a
ng
N, Z
han
g W
,
Z
h
e
ng C.
GROUP:
A Grid-C
luster
ing
Ro
uting
Pr
otocol
for W
i
rel
e
ss Se
nso
r
Netw
orks
. W
i
reless C
o
mmu
nicati
ons, Net
w
o
r
kin
g
an
d
Mobil
e
Com
p
uting, 20
06
W
iCOM 2006
Internatio
na
l C
onfere
n
ce o
n
, IEEE. 2006.
[11]
Yu-Quan
Z
,
L
e
i W
.
A
Ne
w
Routi
ng Pr
otoc
ol for
Efficie
n
t an
d S
e
cure
W
i
reless S
ens
or N
e
t
w
orks.
T
E
LKOMNIKA Indon
esi
an Jou
r
nal of Electric
al Eng
i
ne
eri
n
g
.
2013; 1
1
(11):
679
4-80
1.
[12]
Ye M, Li C,
Ch
en G, W
u
J.
EECS: an
ener
g
y
efficient cl
ust
e
rin
g
sche
m
e i
n
w
i
reless s
e
n
s
or netw
o
rks
.
Performanc
e,
Comp
uting, and Commu
ni
cations Conf
e
r
ence,
2
0
0
5
IPCCC
2
005
24th
IEEE
Internatio
na
l, IEEE. 2005.
[13]
Lee
YH, L
ee K
O, Lee HJ, K
u
sdar
yo
no A.
C
BERP: Clust
er
base
d
e
ner
gy
efficient r
outin
g
protoc
ol for
w
i
reless sens
o
r
netw
o
rk
. Pro
c
12th Int l Conf Net
w
o
r
kin
g
,
VLSI and Sig
nal Proc
essin
g
Universit
y
of
Cambri
dg
e UK
. 2010.
[14]
Nam CS, Jeong HJ, Shin DR.
T
he ada
pti
v
e cluster h
e
a
d
selecti
on i
n
w
i
reless sens
o
r
netw
o
rks.
Semantic C
o
mputin
g an
d
Appl
ic
atio
ns, 2
008 IWSCA'08
IEEE Inte
rnation
a
l Worksh
o
p
on, IEEE.
200
8.
[15]
W
a
jgi
D, T
hakur NV. L
oad
B
a
la
ncin
g Al
gori
t
hms in W
i
re
le
ss Sensor
Net
w
o
r
k: A Surv
e
y
.
Internatio
nal
Journ
a
l of Co
mputer Netw
orks
and
W
i
rel
e
ss Co
mmun
icati
o
ns (IJCNW
C)
. 2: 456-6
0
.
[16]
Goli
SA,
Yous
efi H, Movagh
ar A.
An efficient distrib
u
ted
cluster-he
ad
electi
on tech
ni
que for load
bal
anci
ng i
n
w
i
reless sens
or netw
o
rks
. Intelli
ge
nt Sen
s
ors, Sensor
Net
w
orks a
n
d
Informati
o
n
Processi
ng (ISSNIP), 2010 Si
x
t
h Intern
atio
n
a
l Co
nferenc
e
on, IEEE. 2010
.
[17]
Rad
hama
n
i
G.
Clusteri
ng sch
emes for mobi
l
e
adh
oc netw
o
rks: A review
. Comp
uter
Co
mmunicati
o
n
and Informatic
s
(ICCCI), 2012 Inter
natio
na
l Confer
ence
on
, IEEE, 2012.
[18]
Naru
eph
ip
hat W
,
Charnsrip
i
n
y
o C. An En
er
g
y
-a
w
a
re C
l
u
sterin
g T
e
chniq
ue for W
i
re
less Sens
or
Net
w
orks.
ISBN: 978-9
53-
30
7-29
7-5, Pub
lis
her: InT
e
ch
. 20
10.
[19]
Issariy
a
kul T,
Hossain E.
An introd
uction to
netw
o
rk simula
tor NS2.
Sprin
ger. 201
2.
Evaluation Warning : The document was created with Spire.PDF for Python.