Indonesian
Journal
of
Electrical
Engineering
and
Computer
Science
V
ol.
4,
No
.
3,
December
2016,
pp
.
486
498
DOI:
10.11591/ijeecs
.v4.i3.pp486-498
486
GRPW
-MuS:
Geographic
Routing
to
Multiple
Sinks
in
connected
wireless
sensor
netw
orks
Y
assine
Sabri
STIC
Labor
ator
y
,Chouaib
Doukkali
Univ
ersity
,
B
.P:
20,El
J
adida
Morocco
e-mail:
sabr
iy
assino@gmail.com
Abstract
Multiple
sinks
routing
is
en
visioned
as
a
possib
le
solution
to
the
bottlenec
k
research
prob
lem
in
Wireless
Sensor
Netw
or
ks
(WSN).
In
addition
to
f
ocusing
on
minimizing
the
energy
consumption
in
a
WSN,
it
is
also
equally
impor
tant
to
design
routing
protocols
that
f
air
ly
and
e
v
enly
distr
ib
ute
the
netw
or
k
tr
affic;
in
order
to
prolong
the
netw
or
k
lif
e
time
and
impro
v
e
its
scalability
.In
this
paper
w
e
present
an
enhancement
to
the
GRPW
a
lgor
ithm
f
or
wireless
sensor
netw
or
ks
.
P
erf
or
mance
of
GRPW
algor
ithm
algor
ithm
depends
hea
vily
on
single
sink
position
,
w
e
propose
a
protocol
called
GRPW
-MuS
(
Geog
r
aphic
Routing
to
Multiple
Sinks
in
connected
wireless
sen
sor
netw
or
ks)
based
on
Multiple
Static
Sinks
,
w
e
modified
the
e
xisting
sink
location
pr
iv
acy
protection
scheme
b
y
dividing
nodes
in
the
netw
or
k
containing
m
ultiple
sink
into
diff
erent
le
v
els
in
which
real
pac
k
ets
are
f
orw
arded
to
sink
belong
to
corresponding
logical
le
v
els
and
the
inter
mediate
node
gener
ating
f
ak
e
pac
k
ets
and
sending
it
to
f
ak
e
sinks
.
Usin
g
OMNET++
sim
ulation
and
the
MiXiM
fr
ame
w
or
k,
it
is
sho
wn
that
proposed
protocol
significantly
impro
v
es
the
rob
ustness
and
adapts
to
r
apid
topological
changes
with
m
ultiple
mobile
sinks
,
while
efficiently
reducing
the
comm
unication
o
v
erhead
and
the
energy
consumption.
K
e
yw
or
ds:
Wireless
Sensor
Netw
or
k
(WSN),
Routing,
Multiple
Sink,
Localization,
Geog
r
ap
hic
Routing
Cop
yright
c
2016
Institute
of
Ad
v
anced
Engineering
and
Science
.
All
rights
reser
v
ed.
1.
Intr
oduction
A
Wireless
Sensors
Netw
or
k
(WSN)
contains
a
set
of
sensors
wh
ich
comm
unicate
to
tr
ansmit
inf
or
mation
about
specific
detections
.
A
wide
r
ange
of
monitor
ing
applications
ha
v
e
al-
ready
been
identified
such
as
r
isk
detection
on
industr
ial
sites
,
protected
and
reser
v
e
areas
,
intelligent
tr
anspor
tation
,
and
underw
ater
monitor
ing
[1,
2,
3]
.
Designing
a
WSN
in
v
olv
es
tw
o
main
le
v
els
of
decisions:
oper
ational
and
str
ategic.
In
the
conte
xt
of
WSN,
the
oper
at
ional
le
v
el
is
usually
related
to
protocols
,
netw
or
k
issues
,
comm
unication
policies
,
and
tr
affic
loads
and
their
distr
ib
ution;
while
the
str
ategic
le
v
el
addresses
decisions
ab
le
to
better
cope
with
some
issues
lik
e
minimizing
the
energy
consumption,
reducing
the
tr
affic
,
balancing
the
netw
or
k
load,
enhancing
the
reliability
,
maximizing
the
netw
or
k
lif
etime
,
f
or
instance
.
In
this
study
,
w
e
f
ocus
on
a
str
ategic
and
theoretical
optimization
prob
lem
occurr
ing
in
the
design
of
WSN.
Data
to
the
sink
can
be
tr
ansmitted
via
single
hop
or
m
ulti
hop
comm
unication.
All
the
sensor
nodes
can
use
single
hop
comm
unication
b
ut
in
long
distance
tr
ansmission,
the
energy
consumption
is
m
uch
higher
in
tr
ansmission
as
compare
to
processing
and
sensing
tasks
.
T
r
ans-
mission
energy
dominates
the
o
v
er
all
energy
used
in
comm
unication
process
.
The
requirement
of
energy
goes
on
increasing
with
the
increase
of
distance
[4,
5].
Theref
ore
,
it
becomes
necessar
y
to
reduce
the
energy
consumption
and
to
enhance
the
netw
or
k
lif
etime
.
Theref
ore
,
it
is
pref
er
ab
le
to
use
shor
t-r
ange
m
ultihop
comm
unication.
In
m
ulti
hop
comm
unication,
all
nodes
comm
unicate
with
each
other
using
wireless
channels
without
need
of
an
y
control
str
ucture
and
common
infr
as-
tr
ucture
.
Nodes
cooper
ate
with
each
other
to
f
orw
ard
the
data
and
one
or
more
nodes
ma
y
pla
y
the
role
of
re
la
y
nodes
(RN)
[35].
Multi
hop
comm
unication
is
the
promising
solution
to
increase
netw
or
k
co
v
er
age
and
throughput.
T
r
ansmission
po
w
er
of
the
senor
nodes
can
be
reduced
to
tr
ansmit
the
data
at
the
shor
t
distance
and
to
reduce
the
interf
erence
among
the
signals
.
This
is
adv
antageous
in
ter
ms
of
spatial
reuse
of
frequency
.
But
a
node
pla
ying
the
role
of
RN
can
Receiv
ed
J
uly
9,
2016;
Re
vised
October
21,
2016;
Accepted
No
v
ember
12,
2016
Evaluation Warning : The document was created with Spire.PDF for Python.
IJEECS
ISSN:
2302-4046
487
deplete
its
energy
ear
lier
than
other
nod
es
so
this
prob
lem
should
be
e
xamined
and
tac
kled
b
y
the
routing
protocols
.
Man
y
diff
erent
technologies
are
under
e
xplor
ation
lik
e
fix
ed
rela
ys
(Rela
ys
that
are
not
connected
to
the
bac
kbone
of
the
netw
or
k),
mo
v
ab
le
rela
ys
(Rela
ys
,
which
ag
ree
to
tr
ansmit
the
pac
k
ets
of
each
others)
and
h
ybr
id
rela
ys
(Rela
ys
,
which
are
fix
ed
b
ut
are
situated
on
the
body
of
mobile
objects).
The
use
of
rela
y
nodes
is
v
er
y
beneficial
in
ter
ms
of
scheduling,
interf
erence
management,
netw
or
k
lif
etime
,
adaptiv
e
modulation
etc.
Due
to
adv
antages
of
m
ulti
hop
comm
unicatio
n,
man
y
researchers
ha
v
e
de
v
eloped
rela
y
based
routing
protocols
and
in
fu-
ture
,
it
can
be
considered
vital
to
giv
e
attention
to
shor
t-r
ange
comm
unication
where
po
w
er
le
v
els
of
nodes
can
be
controlled.
Man
y
protocols
f
alls
under
the
categor
y
of
m
ulti
hop
comm
unication.
Se
v
er
al
w
or
ks
in
the
liter
ature
b
ur
y
the
optimization
issues
into
sim
ulations
which
are
done
to
solv
e
oper
ational
issues
,
with
no
f
or
mal
definition
of
the
corresponding
optimization
prob-
lem.
As
a
co
nsequence
,
the
proposed
solutions
ma
y
not
proper
ly
handle
the
core
of
the
opti-
mization
prob
lem
since
optimization
is
a
desired
f
eature
and
not
the
main
f
ocus
.
In
v
estigating
the
optimization
prob
lems
in
v
olv
ed
in
WSN
allo
ws
to
understand
its
comple
xity
and
impro
v
e
the
control,
the
management
and
the
design
of
WSN.
Here
,
the
bib
liog
r
aphical
re
vie
w
main
ly
f
ocuses
on
the
w
or
ks
dedicated
to
optimization
prob
lems
f
or
WSN
using
m
ulti-sin
k
.
Rather
than
being
e
xhaustiv
e
,
w
e
descr
ibe
w
or
ks
strongly
related
to
our
main
concer
ns
,
i.e
.
to
better
understand
the
core
of
optimization
prob
lems
in
v
olv
ed
in
a
WSN.
2.
RELA
TED
W
ORK
AND
B
A
CKGR
OUND
Wireless
sensor
netw
or
ks
(WSNs)
ha
v
e
receiv
ed
significant
attention
due
to
their
poten-
tial
use
in
se
v
er
al
diff
erent
real-w
or
ld
application
s
[6,
7,
8].
T
o
increase
the
capabilities
of
such
applications
,
the
under
lying
WSNs
are
being
enhanced
with
m
ultiple
sinks
sensors
that
can
to
collect
data
from
diff
erent
sensor
nodes
,
theref
ore
data
collection
is
impo
r
tant
issue
in
wireless
sensor
netw
or
k.
This
ne
w
f
or
m
of
WSNs
is
kno
wn
as
Routing
Wireless
Sensor
Netw
or
ks
with
Multiple
Sink
[9].
The
most
widely
kno
wn
proposal
is
[10][11],
b
ut
se
v
er
al
other
geog
r
aphic
rout-
ing
schemes
ha
v
e
been
proposed
[12]
One
of
the
k
e
y
challenges
in
geog
r
aphic
routing
is
ho
w
to
deal
with
dead-ends
,
where
g
reedy
routing
f
ails
because
a
node
has
no
neighbor
closer
to
the
destination;
a
v
ar
iety
of
methods
(such
as
per
imeter
routing
in
GP
SR/GFG)
ha
v
e
been
proposed
f
or
this
.
More
recently
,
GO
AFR
[13]
proposes
a
method
f
or
routing
appro
ximately
the
v
oids
that
is
some
asymptotically
w
orst
case
optimal
as
w
ell
as
a
v
er
age
case
efficient.
Geog
r
aphic
routing
is
scalab
le
,
as
nodes
e
xclusiv
ely
maintain
state
f
or
their
neighbors
,
and
suppor
ts
a
full
gener
al
an
y-
to-an
y
comm
unication
patter
n
without
e
xplicit
route
estab
lishment.
Ho
w
e
v
er
,
geog
r
aphic
routing
requires
that
nodes
kno
w
their
location.
While
this
is
a
natur
al
assumption
in
so
me
settings
(e
.g.,
sensor
net
nodes
with
GPS
de
vices),
there
are
man
y
circumstances
where
such
position
inf
or
ma-
tion
isn’t
a
v
ailab
le
.are
most
often
require
inf
or
mation
about
the
position
of
their
v
oisins
to
function
eff
ectiv
ely
.Or
,
this
assumption
is
f
ar
from
the
reality
.The
other
,
the
localization
of
protocols
,
used
as
a
preliminar
y
step
b
y
geog
r
aphical
routing
protocol
are
not
necessar
il
y
precise
.
F
or
e
xample
,
in
[14],the
authors
proposed
localization
methods
with
which
sensors
deter
mine
their
positions
with
a
r
ate
of
less
than
about
90%
positioning
in
large
scale
.
or
,
if
a
node
that
does
not
kno
w
its
location,
the
node
r
isk
of
ne
v
er
comm
unicate
with
other
node
of
netw
or
ks
,and
no
inf
or
mation
will
be
tr
ansmitted
to
the
user
and
the
base
station
ne
v
er
kno
ws
that
node
.
As
a
gener
al
wireless
comm
unication
pr
inciple
,
sensor
nodes
ha
v
e
a
maxim
um
tr
ansmis-
sion
r
ange
.
Theref
ore
,
to
route
data
to
the
sink
node
,
a
m
ultihop
tr
ansmission
str
ategy
is
adopted.
In
gener
al,
the
energy
consumption
of
sensor
nodes
ne
xt
to
the
sink
is
higher
compared
to
the
one
of
other
sensor
nodes
in
the
netw
or
k.
This
is
due
to
the
f
act
that
the
netw
or
k
tr
affic
is
un-
e
v
enly
distr
ib
uted.
Consider
ing
their
position
ne
xt
to
the
sink
node
,
most
of
the
netw
or
k
tr
affic
passes
through
the
sinks
neighbour
nodes
.
This
eff
ect
consider
ab
ly
reduces
the
netw
or
k
lif
etime
as
the
energy
of
the
sensor
nodes
ne
xt
to
the
sink
r
apidly
depletes
resul
ting
in
no
possibility
to
reach
the
sink2.
This
eff
ect
is
ref
erred
to
as
the
bottlenec
k
prob
lem
and
is
accentuated
as
the
netw
or
ks
scalability
increases
in
ter
ms
of
n
umber
of
nodes
.
The
bottlenec
k
prob
lem
is
accentu-
ated
in
large-scale
netw
or
ks
because
of
the
man
y-toone
netw
or
k
tr
affic
patter
n
which
increases
GRPW
-MuS:
Routing
to
Multiple
Sinks
in
WSNs
(SABRI
Y
assine)
Evaluation Warning : The document was created with Spire.PDF for Python.
488
ISSN:
2302-4046
the
energy
unbalance
in
WSNs
with
a
single
sink
node
.
T
o
pro
vide
a
longer
lif
etime
while
increasing
m
ulti-sensor
y
data
collection
r
ates
in
WSNs
,
the
research
comm
unity
has
e
xploited
the
use
of
m
ultiple
sinks
[15,
16,
17,
18].
m
ultiple
sinks
can
pro
vide
m
ultiple
alter
nativ
e
routes
from
a
source
node
to
one
of
the
interconnected
sink
nodes
.
This
can
shor
te
n
tr
ansmission
distances
and
theref
ore
reduce
the
netw
or
k
energy
cost.
Since
sensor
nodes
pla
y
the
dual
role
of
both
e
v
ent
detectors
and
data
routers
,
the
larger
the
n
umber
of
hops
in
v
olv
ed
in
the
routing
of
data
pac
k
ets
to
the
sink,
the
g
reater
are
the
o
v
erheads
e
xper
ienced,
leading
to
higher
energy
cost.
Ho
w
e
v
er
,
there
are
still
se
v
er
al
challenging
issues
that
need
to
be
fur
ther
in
v
estigated
in
the
conte
xt
of
v
ar
ious
applications
of
Routing
Wireless
Sensor
Netw
or
ks
with
Multiple
Sink
[19].
One
impor
t
ant
implied
assumption
behind
the
data
collection
mechanisms
using
mobile
sinks
is
that
the
collected
data
m
ust
be
dela
y-toler
ant
as
the
collection
dela
y
is
bounded
b
y
the
ph
ysical
distances
and
the
speed
of
the
mobile
sinks
.
Clear
ly
,
this
whole
approach
w
ould
not
be
appropr
iate
when
w
e
need
to
collect
real-time
data,
f
or
which
ne
w
approaches
need
to
be
de
v
eloped
as
w
e
are
currently
in
v
estigating
in
a
related
w
or
k
[20,
21].
F
or
monitor
ing
applications
that
are
ab
le
to
perf
or
m
their
e
xpected
functionalities
as
long
as
the
data
tr
ansmission
is
done
within
hours
or
min
utes
,
then
w
e
can
consider
mobile
sinks
.
In
such
applications
,
to
mak
e
better
analysis
and
decisions
,
w
e
need
to
get
almost
all
of
the
data
from
sen
s
o
r
nodes
to
the
base
station
(i.e
.,
pro
vide
a
high
deliv
er
y
r
ate)
while
minimizing
the
collection
dela
y
as
m
uch
as
possib
le
.
In
dense
netw
or
ks
,
lif
etime
can
be
maximiz
ed
b
y
creat
ing
co
v
ers
,
i.e
.,
g
roups
of
sensors
that
are
activ
e
at
the
same
time
.
This
str
ategy
has
been
pro
v
en
to
be
efficient
in
se
v
er
al
applica-
tions
of
WSN
[22,
23].
F
ollo
wing
this
id
ea,
decomposition
approaches
as
column
gener
ation
(CG)
ha
v
e
been
largely
used
to
identify
and
create
schedules
f
or
the
co
v
ers
.
As
w
ell
as
in
the
classi-
cal
implementation,
CG
decomposes
the
prob
lem
into
a
restr
icted
master
prob
lem
(RMP)
and
an
auxiliar
y
prob
lem
(AP).
The
f
or
mer
optimiz
es
the
lif
etime
using
an
incomplete
set
of
columns
,
and
the
latter
is
used
to
identify
profitab
le
columns
.
In
this
paper
w
e
propose
an
enhancement
to
the
GRPW
algor
ithm
based
on
scheduling
techniques
that
allo
w
the
sink
node
to
send
its
position
in
a
planned
manner
to
suppor
t
a
m
ulti
sinks
ba
sed
on
a
logical
par
tition.
W
e
propose
a
m
ulti
sinks
with
limit
path
in
the
edge
of
site
which
sensor
nodes
are
scattered
there
.
2.1.
Motiv
ation
In
this
paper
w
e
present
a
ne
w
method
f
or
m
ultiple
sinks
enhancement
based
on
the
pre-
vious
GRPW
a
lgor
ithm
(Geog
r
aphic
Routing
Protocol
W
ashbasin).
as
basis
f
or
an
in
v
estigation
on
impro
ving
the
deplo
yment
of
a
netw
or
k.
GRPW
is
a
geog
r
aphical
routing
protocol
f
or
Wireless
Sensor
Netw
or
ks
(WSN)
ensures
a
load
balancing,
minimizing
energy
consumption
and
the
r
ate
of
message
deliv
er
y
f
or
v
er
y
lo
w
po
w
er
netw
or
ks
and
uses
a
routing
policy
with
logical
le
v
els
,
inspired
fr
om
the
w
ater
flo
w
in
a
w
ashbasin
.
GRPW
requires
kno
wledge
the
static
single
sink
position
which
is
considered
as
par
ameter
f
or
initialization
of
the
netw
or
k
to
constr
uct
the
logical
le
v
els
topology
.
By
changing
these
par
ameter
a
tr
ade
off
is
made
betw
een
an
o
v
erhead
in
the
n
umber
of
tr
ansmissions
used
to
setup
routing
inf
or
mation
in
the
netw
or
k
and
an
o
v
erhead
in
the
n
umber
of
tr
ansmissions
used
f
or
sending
the
quer
ies
.
In
order
to
set
these
par
ameter
,
the
single
sink
node
position
has
to
be
kno
wn
bef
ore
deplo
yment.
If
GRPW
is
initializ
ed
with
m
ultiple
sink
par
ameter
then
it
will
not
be
efficient
and
can
in
some
cases
be
outperf
or
med
b
y
a
simple
protocol
such
as
classic
flooding.
In
man
y
cases
the
n
umber
of
e
v
ents
or
quer
ies
cannot
be
e
xpected
to
be
kno
wn
in
adv
ance
.
As
a
consequence
,
GRPW
will
not
alw
a
ys
be
an
at
tr
activ
e
routing
protocol.
2.2.
Or
ganization
W
e
ha
v
e
organiz
ed
this
paper
in
the
f
ollo
wing
w
a
y:
Section
II
descr
ibes
the
pre
vious
w
or
k.
In
this
section
w
e
will
f
ocus
on
GRPW
which
is
t
he
basis
f
or
our
e
xtension.
In
Section
III
w
e
descr
ibe
our
algor
ithm
and
the
implementation
of
it.
Section
IV
descr
ibes
the
sim
ulation
details
of
our
algor
ithm
and
the
results
obtained
are
presented
in
Section
V
.
In
Section
VI
results
are
discussed
and
conclusions
presented.
IJEECS
V
ol.
4,
No
.
3,
December
2016
:
486
498
Evaluation Warning : The document was created with Spire.PDF for Python.
IJEECS
ISSN:
2302-4046
489
3.
GRPW
algorithm
Se
v
er
al
papers
ha
v
e
been
pub
lished
about
routing
in
WSN.
In
this
section
w
e
will
f
ocus
on
introducing
the
GRPW
Routing
approach
as
this
is
the
f
oundation
f
or
our
w
or
k.
F
or
a
more
elabor
ate
descr
iption
to
GRPW
please
ref
er
to
[24].
GRPW
that
ea
c
h
node
can
get
its
o
wn
location
inf
or
mation
either
b
y
GPS
or
other
location
ser
vices
[25][26]
.
Each
node
can
get
its
one-hop
neighbor
list
and
their
locations
b
y
beacon
messages
.
W
e
consider
the
topologies
where
the
wireless
sensor
nodes
are
roughly
in
a
plane
.
Our
approach
in
v
olv
es
three
steps:
Lev
el
0
Lev
el
1
Lev
el
2
Lev
el
3
Lev
el
4
SB
(
sink
)
Figure
1.
Illustr
ation
of
GRPW
routing
netw
or
k
le
v
els
1.
The
distrib
ution
the
immobile
sink
posi
tion
to
all
sensor
s
netw
orks:
In
the
first
step
,The
comm
unications
in
this
step
are
made
in
three
steps:
When
a
node
w
ants
to
tr
ansmit
the
sink
position
to
its
neighbors
,it
first
emits
AD
V
message
containing
the
location
of
sink.
A
node
receiving
a
message
AD
V
.
If
interested
b
y
this
inf
or
mation,
it
sends
a
message
REQ
to
its
neighbor
.
In
Receiving
a
message
REQ,
the
tr
ansmitter
tr
ansmitted
to
the
node
concer
ned
the
sink
position
in
a
D
A
T
A
message
.
2.
Construction
of
logical
le
vels:
In
this
step
the
node
netw
or
ks
deter
mine
its
le
v
el
of
be-
longing
through
the
sink
node
position,each
node
u
w
ell
localiz
ed,
calculate
its
le
v
el
based
on
the
receiv
ed
position
of
sink
in
the
Phase
1
,with
which
u
calculates
the
distance
d
uS
ink
which
separ
ates
him
with
the
sink
node
.the
le
v
els
is
calculated
so
that
the
width
le
v
el
be
constant
is
less
than
and
in
v
ersely
propor
tional
to
the
density
of
netw
or
ks
.
The
le
v
el
l
of
the
node
u
defined
b
y:
Lev
el
u
=
f
l
2
N
=
d
uS
ink
l
d
uS
ink
+
1
g
Set
of
the
neighbor
nodes
that
are
w
ell
localiz
ed
and
which
belongs
to
the
same
le
v
el
as
u
:
L
N
(
u
)
=
f
v
2
N
(
u
)
=Lev
el
u
=
Lev
el
v
g
Set
of
the
neighbor
nodes
that
are
w
ell
localiz
ed
and
which
belongs
to
the
higher
le
v
el
than
u
:
L
+
N
(
u
)
=
f
v
2
N
(
u
)
=Lev
el
u
=
Lev
el
v
1
g
GRPW
-MuS:
Routing
to
Multiple
Sinks
in
WSNs
(SABRI
Y
assine)
Evaluation Warning : The document was created with Spire.PDF for Python.
490
ISSN:
2302-4046
Set
of
the
neighbor
nodes
that
are
w
ell
localiz
ed
and
which
belongs
to
the
lo
w
er
le
v
el
than
u
:
L
N
(
u
)
=
f
v
2
N
(
u
)
=Lev
el
u
1
=
Lev
el
v
g
3.
Data
f
orwar
ding
:
The
routing
decisio
n
is
done
in
our
approach
in
three
modes
,
depending
on
dispoinibilites
neighbor
ing
nodes
and
of
their
le
v
el
of
belonging:
the
Ev
en
F
orw
arding
,
Anter
ior
F
orw
arding
and
the
Rear
F
orw
arding
(respectiv
ely
called
EF
,
AF
and
RF).
In
the
first
mode
AF
,GRPW
constr
ucts
a
route
tr
a
v
ersing
the
nodes
of
the
source
to
the
destination
which
each
node
receiving
a
pac
k
et
DataP
ac
k
et
with
the
mode
of
tr
anspor
t
AN-
TERIOR
FOR
W
ORD
,
will
mo
v
e
to
w
ard
the
inter
mediate
node
in
its
co
v
er
age
area
what
in
bef
ore
,
the
inter
mediate
node
select
among
the
neighbor
ing
node
using
a
lookup
function.
Lookup
function
is
used
b
y
a
node
in
order
that
he
can
deter
mine
the
ne
xt
hop
to
reach
the
ne
xt
le
v
el,
to
deter
mine
the
ne
xt
hop
function,
lookup
based
on
the
pr
inciple
of
Round
Robin
(RR).
In
the
second
mode
EF
,
on
account
of
the
frequent
f
ailures
of
nodes
,
the
mobility
of
nodes
or
policy
scheduling
of
activities
used,
disconnecti
ons
can
occur
in
the
netw
o
r
k
gen-
er
ates
,
so
,
what
are
called
holes
in
this
situation,
GRPW
will
change
the
routing
mode
to
EVEN
FOR
W
ORD
to
reroute
the
pac
k
et
in
EF
mode
and
to
o
v
ercome
the
v
oid
case
.
In
the
third
mode
RF
,
GRPW
reroute
the
pac
k
et
DataP
ac
k
et,
who
w
as
f
ailed
in
AF
and
EF
,
RF
f
act
sends
a
pac
k
et
to
the
lo
w
le
v
el
L
N
()
b
y
seeking
the
ne
xt
hop
among
neighbor
ing
based
on
the
lookup
function.
RF
is
leaning
on
same
techn
ique
used
in
EF
,
f
or
a
v
oids
the
routing
loop
w
e
saf
eguard
the
sets
of
node
tr
a
v
ersed
b
y
the
pac
k
et
DataP
ac
k
et
in
a
v
ector-type
str
ucture
4.
GRPW
-MS:
Adaptive
Routing
a
Mobile
Sink
in
WSNs
Let
us
no
w
consider
the
use
of
GRPW
in
a
sensor
netw
or
k
with
static
nodes
and
a
single
static
sink.
If
the
sink
mo
v
es
,
its
vir
tual
le
v
el
will
change
,
and
the
messages
routed
to
the
old
coordinates
will
not
reach
the
sink.
A
simple
solution
w
ould
be
to
no
tify
each
nodes
about
the
sinks
ne
w
coordinates
.
This
solution,
ho
w
e
v
er
is
e
xpensiv
e
in
ter
ms
of
the
n
umber
of
messages
,
and
the
corresponding
energy
consumption.
The
GRPW
-MS
algor
ithm
tak
es
an
idea
which
had
been
successfully
applied
to
geog
r
aphical
routing
to
reduce
the
n
umber
of
update
messages
necessar
y
to
maintain
routability
in
conte
xt
of
m
ultiple
sinks
.
The
gener
al
idea
is
that
as
long
as
the
sink
mo
v
es
inside
a
limited
local
le
v
el
area,
the
nodes
outside
that
le
v
el
area
will
not
be
notified
about
the
sinks
mo
v
ement.
The
routing
will
rely
on
the
nodes
at
the
per
ipher
y
of
the
le
v
el
area
to
f
orw
ard
the
messages
to
the
the
closest
sink
which
belongs
to
its
area.
4.1.
GRPW
-MuS
defines
the
f
ollo
wing
o
verlapping
categories
of
nodes
In
Figure
2
GRPW
-MuS
defines
se
v
er
al
special
nodes
and
area
types:
An
inter
nal
nodes
has
all
its
logical
address
belonging
to
the
same
area
sink
.
An
area
border
noeud
is
a
noeud
that
connected
at
one
or
more
areas
sink
.
It
is
considered
a
member
of
all
areas
sink
it
is
connected
.
An
ABN
k
eeps
address
of
all
sink
where
it
belongs
in
memor
y
,
one
f
or
each
area
to
which
that
node
is
connected.
An
area
border
noeud
(ABN)
is
a
noeud
that
connected
at
one
or
more
areas
sink
.
It
is
considered
a
member
of
all
areas
sink
it
is
connected
.
An
ABN
k
eeps
address
of
all
sink
where
it
belongs
in
memor
y
,
one
f
or
each
area
to
which
that
node
is
connected.
A
bac
kbone
area
sink
has
a
link
to
the
bac
kbone
area.
Each
node
has
an
identifier
.
This
identifier
m
ust
be
estab
lished
in
e
v
er
y
GRPW
-MuS
in-
stance
.
If
not
e
xplicitly
configured,
the
highest
logical
address
will
be
duplicated
as
the
IJEECS
V
ol.
4,
No
.
3,
December
2016
:
486
498
Evaluation Warning : The document was created with Spire.PDF for Python.
IJEECS
ISSN:
2302-4046
491
Lev
el
0
Lev
el
1
Lev
el
2
Lev
el
3
Lev
el
4
Source
Designated
Sink
(DS)
S
I
N
K
secondar
y
S
I
N
K
secondar
y
inter
nal
node
Bac
kbone
area
sink
Area
border
noeud
Area
border
noeud
Figure
2.
Illustr
ation
of
GRPW
-MuS
routing
netw
or
k
le
v
els
router
identifier
.
Ho
w
e
v
er
,
since
the
router
identifier
is
not
a
logical
address
,
it
does
not
ha
v
e
to
be
a
par
t
of
an
y
area
in
the
netw
or
k,
and
often
isn’t
to
a
v
oid
confusion.
4.2.
GRPW
-MuS
Algorithm
A
designated
Sink
(DS)
is
the
sink
node
elected
among
all
nodes
,
ge
ner
ally
assumed
to
be
a
m
ultihop
netw
or
k.
The
basic
neighbor
disco
v
er
y
process
(Hello),
DS
election
(pr
ior
ity).
The
DR
is
elected
based
on
the
f
ollo
wing
def
ault
cr
iter
ia:
If
the
pr
ior
ity
setting
on
an
GRPW
-MuS
node
is
set
to
0,
that
means
it
can
NEVER
become
a
DS
When
a
DS
f
ails
and
the
BDS
(Bac
kup
Designated
Sink).
tak
es
o
v
er
,
t
here
is
another
election
to
see
who
becomes
the
replacement
BDS
.
The
node
sending
the
Hello
pac
k
ets
with
the
highest
pr
ior
ity
wins
the
election.
If
tw
o
or
more
nodes
tie
with
t
he
highest
pr
ior
ity
setting,
the
router
sending
the
Hello
with
the
highest
NID
(node
ID)
wins
.
Usually
the
node
with
the
second
highest
pr
ior
ity
n
umber
becomes
the
BDS
.
The
pr
ior
ity
v
alues
r
ange
betw
een
0
-
255,[14]
with
a
higher
v
alue
increasing
its
chances
of
becoming
DS
or
BDS
.
If
a
hig
her
pr
ior
ity
GRPW
node
comes
online
after
the
election
h
as
tak
en
place
,
it
will
not
become
DS
or
BDS
until
(at
least)
the
DS
and
BDS
f
ail.
If
the
current
DS
’goes
do
wn’
the
current
BDS
becomes
the
ne
w
DS
and
a
ne
w
election
tak
es
place
to
find
another
BDS
.
If
the
ne
w
DS
then
’goes
do
wn’
and
the
or
iginal
DS
is
no
w
a
v
ailab
le
,
still
pre
viously
chosen
BDS
will
become
DR.
In
GRPW
algor
ithm,
SINK
secondar
y
cannot
compute
distances
when
a
designated
Sink
(DS)
sends
a
message
b
y
using
distance
estimation
techniques
SumDIST
.
This
method
is
the
most
simple
solution
f
or
estimating
distances
to
DS
.
It
adds
r
anges
encountered
at
each
hop
dur
ing
the
netw
or
k
flood.
Each
DS
sends
a
message
including
its
identity
,
coordinates
and
path
length
initializ
ed
to
z
ero
.
Whe
n
a
node
receiv
es
this
message
,
it
calculates
the
r
ange
from
the
sender
,
adds
it
to
the
path
length
and
broadcasts
the
message
.
Thus
,
each
SS
obtains
a
distance
estimation
and
posit
ion
of
anchors
.
Of
course
,
only
the
shor
test
distance
will
be
conser
v
ed.
Sum-dist
is
v
er
y
simple
and
f
ast.
Moreo
v
er
,
little
computations
is
required.
A
dr
a
wbac
k
of
Sum-
dist
is
that
r
ange
errors
are
accum
ula
ted
when
distance
inf
or
mation
is
propagate
d
o
v
er
m
ultiple
hops
.
After
this
phase
,
Second
calibr
ation
allo
ws
to
con
v
er
t
distances
into
a
r
adius
of
the
area
representing
its
siz
e
.
This
con
v
ersion
consists
t
o
divide
the
estimated
distance
with
the
n
umber
of
all
sinks
.
GRPW
-MuS:
Routing
to
Multiple
Sinks
in
WSNs
(SABRI
Y
assine)
Evaluation Warning : The document was created with Spire.PDF for Python.
492
ISSN:
2302-4046
After
this
logical
netw
or
ks
reconstr
uction
,each
sin
k
estab
lishes
its
area
based
on
the
sink
DS
position.
The
routing
of
captured
data
be
perf
or
med
within
each
z
one
belonging
to
each
node
using
the
GRPW
method
f
or
each
Area
Sink
.
5.
Sim
ulation
The
perf
or
mance
e
v
aluations
w
ere
conducted
using
the
OMNET++
discrete
e
v
ent
sim
u-
lator
and
making
use
of
the
MiXiM
fr
ame
w
or
k.
The
obtained
results
are
presented
and
compared
to
GRPW
protocol
in
ter
ms
of
netw
or
k
lif
etime
as
w
ell
as
the
a
v
er
age
remaining
energy
and
the
energy
consumption.
The
beha
viour
of
the
netw
or
k
lif
espan
is
also
e
v
aluated
and
analysed
as
the
netw
or
k
scalability
is
increased
in
order
to
study
its
eff
ect
on
the
perf
or
mance
.
The
idea
of
using
f
our
interconnected
sinks
is
also
to
allo
w
m
uch
more
distr
ib
uted
energy
consumption
throughout
the
netw
or
k
as
a
mechanism
to
f
acilitate
energy
balance
.
5.1.
Sim
ulation
Results
5.1.1.
Number
of
Dead
Nodes
20
40
60
80
100
120
140
160
0
10
20
30
40
50
Sim
ulation
Time
(min)
Dead
Nodes
GRPW
GRPW
-MS
Figure
3.
Number
of
Dead
Nodes
F
rom
Figure
3
,
w
e
see
that
GRPW
-MuS
outperf
or
ms
other
protocols
significantly
,
with
GRPW
-MuS
close
to
doub
ling
or
tr
ipling
the
time
to
first
sensor
nod
e
f
ailure
in
some
cases
.
In
GRPW
,
the
first
node
dies
quic
k
er
than
the
other
protocols
,
because
all
pac
k
ets
are
sent
to
only
one
sink
and
there
is
no
m
ultiple
sink
nodes
le
v
els
reconstr
uction
and
path
s
witching.
The
GRPW
-
MuS
Algor
ithm
decrease
energy
consumption
which
ca
n
impro
v
e
the
lif
etime
of
sensor
nodes
and
the
GRPW
-MuS
Algor
ithm
uses
the
m
ultiple
sink
nodes
which
impro
v
e
the
load-balance
of
data
which
is
sent
to
sink
nodes
.
Ho
w
e
v
er
,
GRPW
-MuS
b
y
combining
m
ultiple
sink
nodes
,
le
v
els
reconstr
uction
and
pa
th
s
witching,
can
best
bala
nce
sensor
energy
consumption
and
prolong
the
dur
ation
f
or
sensor
netw
or
k
which
is
fully
functional.
5.1.2.
A
vera
g
e
Ener
gy
Consumption
In
Figure
4
and
Figure
5,
This
can
be
seen
where
the
hop
count
and
distance
decreases
with
time
f
or
most
algor
ithms
.
GRPW
,
ho
w
e
v
er
,
beha
v
es
a
bit
diff
erently
in
that
its
a
v
er
age
dis-
tance
to
sink
does
not
decrease
m
uch
o
v
er
time
,
meaning
that
it
is
still
ab
le
to
k
eep
some
of
the
outlying
sensors
aliv
e
(and
hence
the
higher
a
v
er
age
distance).
Despite
the
longer
actual
dis-
tance
from
the
sinks
(which
g
reatly
aff
ects
the
energy
consumption
of
the
pac
k
et),
GRPW
-MuS
IJEECS
V
ol.
4,
No
.
3,
December
2016
:
486
498
Evaluation Warning : The document was created with Spire.PDF for Python.
IJEECS
ISSN:
2302-4046
493
0
20
40
60
80
100
120
140
2
3
4
Sim
ulation
Time
(min)
A
v
er
age
Hop
Counts
F
or
P
ac
k
et
to
Sink
GRPW
GRPW
-MS
Figure
4.
A
v
er
age
Hop
Count
vs
Time
0
20
40
60
80
100
120
140
1
1
:
5
2
2
:
5
3
10
3
Sim
ulation
Time
(min)
A
v
er
age
energy
consumption
f
or
one
pac
k
et
(j)
GRPW
GRPW
-MS
Figure
5.
A
v
er
age
Energy
Consumption
f
or
pac
k
et
still
maintains
the
best
a
v
er
age
energy
consumption
per
pac
k
et,
which
is
a
tr
ib
ute
to
the
le
v
el
maintenance
and
path
s
witching
mechanisms
.
5.1.3.
Saf
e
time
Here
the
saf
e
time
is
denoted
as
a
n
umber
of
hopes
the
adv
ersar
y
ha
s
to
tr
a
v
el
to
find
the
location
of
the
sink.
The
total
n
umber
of
hopes
includes
a
n
umber
of
hope
at
the
f
ak
e
path
and
n
umber
of
hopes
at
the
real
path
the
adv
ersar
y
has
to
mo
v
e
to
locate
the
sink.
Figure
6
sho
ws
saf
e
time
as
a
function
of
a
n
umber
of
sinks
.
The
saf
e
time
f
or
GRPW
-MuS
and
GRPW
go
on
increasing
the
n
umber
of
sink
is
increased.
The
perf
or
mance
of
GRPW
-MuS
is
better
compared
to
GRPW
as
in
GRPW
-MuS
the
node
are
divided
into
the
n
umber
of
z
ones
and
hence
m
ultiple
paths
are
gener
ated
sim
ultan
eously
in
the
netw
or
k
and
hence
saf
e
time
is
more
while
GRPW
-MuS:
Routing
to
Multiple
Sinks
in
WSNs
(SABRI
Y
assine)
Evaluation Warning : The document was created with Spire.PDF for Python.
494
ISSN:
2302-4046
2
4
6
8
40
60
80
100
120
140
Number
of
Sinks
Saf
e
time
(Denoted
b
y
hops)
GRPW
GRPW
-MS
Figure
6.
Saf
e
time
as
a
function
of
n
umber
of
sinks
using
GRPW
-MuS
.
5.1.4.
P
ac
ket
Deliver
y
Ratio
2
4
6
8
80
90
100
Number
of
Sinks
P
ac
k
et
Deliv
er
y
Ratio
(%)
GRPW
GRPW
-MS
Figure
7.
P
ac
k
et
Deliv
er
y
Ratio
(%)
as
a
function
of
n
umber
of
sinks
Figure
7
sho
ws
the
pac
k
et
deliv
er
y
r
atio
as
a
function
of
a
n
umber
of
sinks
.
The
pac
k
et
deliv
er
y
r
atio
in
GRPW
and
GRPW
-MuS
initially
decrease
up
to
a
n
umber
of
sink
2,
after
which
it
increases
with
increasing
n
umber
of
sink.
The
pac
k
et
deliv
er
y
r
atio
f
or
GRPW
and
GRPW
-MuS
almost
remains
identical
as
a
function
of
n
umber
of
sinks
.
5.1.5.
A
vera
g
e
Thr
oughput
(kbps)
Figure
8
sho
ws
that
perf
or
mance
of
GRP
W
-M
uS
is
slightly
better
f
or
the
a
v
er
age
through-
put
as
compared
to
GRPW
.
P
erf
or
mance
GRPW
and
GRPW
-MuS
are
increases
in
a
v
er
age
throughput
as
a
function
of
n
umber
of
sinks
.
Due
to
z
one
par
titioning
done
b
y
GRPW
-MuS
,
It
increases
perf
or
mance
f
or
an
a
v
er
age
throughput.
IJEECS
V
ol.
4,
No
.
3,
December
2016
:
486
498
Evaluation Warning : The document was created with Spire.PDF for Python.
IJEECS
ISSN:
2302-4046
495
2
4
6
8
4
6
8
10
12
Number
of
Sinks
Throughput
(Kbps)
GRPW
GRPW
-MS
Figure
8.
A
v
er
age
Throughput
(kbps)
as
a
function
of
n
umber
of
sinks
5.1.6.
Normaliz
ed
Routing
Load
2
4
6
8
2
4
6
8
10
12
Number
of
Sinks
Nor
maliz
ed
Routing
Load
(Pkt
sent/recvs)
GRPW
GRPW
-MS
Figure
9.
Nor
maliz
ed
Routing
Load
as
a
function
of
n
umber
of
sinks
Figure
9
sho
ws
that
perf
or
mance
of
GRPW
is
slightly
better
f
or
nor
maliz
ed
routing
load
as
compared
GRPW
-MuS
.
The
routing
load
dr
astically
increases
f
or
both
GRPW
and
GRPW
-MuS
up
to
a
n
umber
of
sink-2
and
then
decreases
linear
ly
with
increasing
n
umber
of
sink.
6.
CONCLUSION
AND
FUTURE
W
ORK
In
this
paper
,
w
e
designed
the
ne
w
scheme
to
pro
vide
the
Multiple
Si
nk
location
pr
iv
acy
in
WSNs
.
W
e
use
the
GRPW
-MuS
routing
p
rotocol
based
on
le
v
el
par
titioning
without
relying
on
geog
r
aphical
inf
or
mation
about
the
sensors
and
the
sinks
.
Using
le
v
els
par
titioning,
the
n
umbers
of
nodes
are
divided
into
se
v
er
al
le
v
els
.
The
f
ak
e
pac
k
et
injection
scheme
is
used
to
protect
the
location
pr
iv
acy
in
which
the
real
tr
affic
is
routed
through
the
shor
test
path.
Moreo
v
er
,
The
v
ar
ious
f
ak
e
paths
are
gener
ated
b
y
gener
ating
f
ak
e
pac
k
ets
to
f
ak
e
sinks
.
It
is
seen
that
GRPW
-
GRPW
-MuS:
Routing
to
Multiple
Sinks
in
WSNs
(SABRI
Y
assine)
Evaluation Warning : The document was created with Spire.PDF for Python.