TELKOM
NIKA
, Vol.13, No
.3, Septembe
r 2015, pp. 9
04~921
ISSN: 1693-6
930,
accredited
A
by DIKTI, De
cree No: 58/DIK
T
I/Kep/2013
DOI
:
10.12928/TELKOMNIKA.v13i3.1496
904
Re
cei
v
ed Fe
brua
ry 1, 201
5; Revi
se
d May 19, 20
15; Acce
pted Jun
e
1, 2015
Robust Path Construction for Reliable Data
Transmissions in Node Disjoint Multipath Routing for
Wireless Sensor Network
Abdulale
e
m Ali Almazroi
*, MA Ngadi
Dep
a
rtment of Comp
uter scie
n
ces, F
a
cult
y
o
f
Computin
g, Universiti T
e
chn
o
lo
gi Mal
a
ysia
*Corres
p
o
ndi
n
g
author, e-ma
i
l
: maaaa
l2@
liv
e.utm.m
y
, dr.a
sri@utm.m
y
A
b
st
r
a
ct
W
i
reless
Sens
or N
e
tw
orks (W
SNs) are
pr
one
to
no
de
b
r
eakd
o
w
n
s d
u
e
to
en
ergy
constrai
nts,
w
h
ich contri
but
e to freq
uent to
pol
ogy ch
an
ge
s. Moreov
er, si
nce se
nsor
no
des h
a
ve r
e
stri
cted trans
miss
i
o
n
rang
e, multi
p
le
hops
are
ne
e
ded
by the
no
de i
n
or
der
to f
o
rw
ard the
pac
kets from
on
e
nod
e to th
e ot
her
and th
is ra
ises
very cha
lle
ng
in
g issu
es w
hen
desi
gni
ng
r
outi
ng pr
otoco
l
s. Most of
the pr
o
pose
d
si
ngl
e p
a
th
routin
g sche
m
es use a peri
odic low
-rate fl
ood
ing of dat
a
in order to recover fr
om
path failures, which
causes h
i
gh
er
consu
m
pti
on in sens
or nod
e resources.
So mu
ltipat
h r
outin
g is an o
p
timal ap
pro
a
c
h
to
enh
anc
e the
n
e
tw
ork lifeti
m
e.
In this
p
a
p
e
r,
a ro
bus
t
path
constructio
n
fo
r a r
e
li
abl
e
dat
a trans
missio
n
in
nod
e-dis
j
oi
nt mu
ltip
ath
routi
ng (RNDM
R) i
s
propos
ed for
W
S
Ns.
The propos
ed RN
DM
R has the a
b
il
i
t
y to
provi
de
a low
overh
ead
pat
h
constructio
n
a
s
w
e
ll as
provi
de d
a
ta tra
n
s
m
iss
i
on
rel
i
ab
il
ity by usi
ng
X
O
R-
base
d
cod
i
ng
alg
o
rith
m, w
h
ich entai
ls low
u
t
ili
z
a
tio
n
of res
ources, suc
h
a
s
low
storage
space a
nd l
e
s
s
er
computi
ng p
o
w
er. In the propos
ed R
NDM
R, the proc
ed
ure inv
o
lv
es t
he spl
i
tting
up
of all trans
mi
tted
mess
ag
es into
ma
ny d
i
fferen
t
segments of
equ
al si
z
e
,
b
e
fore a
ddi
ng t
he XOR-b
a
se
d error c
o
rrect
io
n
codes
an
d dist
ributi
ng it a
m
o
ng
mu
ltipl
e
p
a
ths si
mu
lt
ane
ou
sly in
order to
boost re
lia
bl
e
data trans
missi
on
and
to
be
assu
red th
at the
es
sentia
l frag
me
nt of th
e
p
a
cke
t arrives
at th
e
sink
nod
e w
i
th
out a
n
y
add
itio
na
l
consu
m
ption
of ener
gy an
d un
due
del
ay. By usin
g si
mu
latio
n
s, the perfor
m
ance
of RNDM
R w
a
s assess
e
d
and c
o
mpar
es
it w
i
th ReInF
o
r
m
ro
utin
g. T
he
results il
lustrat
e
that RN
DMR
attains l
o
w
ene
rgy cons
u
m
ptio
n,
records low average delay and rout
ing overhead, as well as incr
eased pack
e
t delivery ratio when
compar
ed w
i
th ReInF
o
r
m
Ro
u
t
ing.
Ke
y
w
ords
:
w
i
reless s
enso
r
netw
o
rk, n
o
d
e
-disj
o
i
n
t
multi
path r
outi
ng, r
obust
path
co
nstruction, for
w
ar
d
error correcti
o
n
,
reliab
ility
Copy
right
©
2015 Un
ive
r
sita
s Ah
mad
Dah
l
an
. All rig
h
t
s r
ese
rved
.
1. Introduc
tion
The ra
pid p
r
o
g
re
ssi
on of wirele
ss
sen
s
o
r
netwo
rks
(WSNs) in
re
cent times hav
e led to
sub
s
tantial
re
sea
r
ch intere
st, largely be
cau
s
e of
diffe
rent varietie
s
of application
s
whi
c
h m
a
y not
need
hum
an
interventio
ns, esp
e
ci
ally in the fiel
d
s
of military mi
ssi
on
s an
d a
c
cessin
g ho
stile
environ
ment
s. But for som
e
rea
s
on
s, lot
s
of
inte
rest
s
are
given
to
routi
ng protocols be
cau
s
e
of
the different
types that
e
x
ist, su
ch
a
s
the
archite
c
ture
of the
n
e
twork an
d t
he a
ppli
c
atio
n
.
Senso
r
s a
r
e
disting
u
ished
in
WSNs by
mean
s
of
its
con
s
trai
ned
ene
rgy, me
mory resou
r
ces,
pro
c
e
ssi
ng, u
npre
d
icta
ble
wirel
e
ss lin
ks and hig
her
d
egre
e
of mobi
lity. The appe
aran
ce
of these
cha
r
a
c
teri
stics
in sen
s
o
r
netwo
rks co
ntribute
s
to different chal
lenge
s
for e
v
ery
part
of the
proto
c
ol
sta
c
k, pa
rticula
r
ly
the network laye
r, for in
stan
ce, a
s
su
ran
c
e of
end
-to-e
nd p
a
cket
delivery [1, 2
]. There h
a
ve bee
n several innovativ
e
routing
proto
c
ol
s de
sig
n
e
d
sp
ecifi
c
ally
for
WSNs in
re
cent years. Th
ese i
n
cl
ude
a
n
ene
rgy-awa
r
e routing
pro
t
oc
ol to
prol
o
ng the life
of the
network
[3, 4]
; toleranc
e to faults
in s
ens
ors
be
cau
s
e
of quicker ex
hau
stion of b
a
ttery or errat
i
c
wirel
e
ss lin
ks [5]; and Qu
al
ity of Service
(QoS
) sc
h
e
m
e
s to
stabili
ze the
con
s
um
ption of en
ergy
and
ce
rtain p
r
edete
r
min
e
d
QoS met
r
ics that are
n
e
e
ded by th
e va
riou
s
kind
s of
appli
c
ation
s
[6,
7]. The mo
st existing research
wo
rks
in routin
g p
r
otocol
s h
a
ve
use
d
si
ngle
path routing
to
transmit data
to the destin
a
tion. Most rese
arche
r
s
a
dopt this met
hod be
ca
use
it very simple to
desi
gn a
s
well as p
r
ovidi
ng less en
ergy con
s
umpt
i
on. Unfo
rtun
ately, for sin
g
le path rout
ing,
most of th
e paths
are su
sceptibl
e
to ei
ther node o
r
l
i
nk b
r
ea
kd
o
w
n
s
. The
r
ef
ore,
ackno
w
le
dgm
ents
and
ret
r
ansmi
ssion
s
mech
ani
sm
a
r
e im
pleme
n
ted in
orde
r t
o
re
cove
r
da
ta
lost, whi
c
h
co
ntribute
s
to h
uge a
m
ount
of extra traffic and d
e
lays i
n
the n
e
two
r
k. The p
r
o
c
e
s
se
s
Evaluation Warning : The document was created with Spire.PDF for Python.
TELKOM
NIKA
ISSN:
1693-6
930
Rob
u
st Path Con
s
tru
c
tion
for Relia
ble Data Tr
an
sm
ission
s in Node
… (Abdul
alee
m
Ali Alm
a
zroi)
905
also
entail th
e discove
r
y o
f
new
path
s
required
ev
ery time for
su
stainin
g
tra
n
smissi
on
of da
ta
from the sou
r
ce to
sin
k
and so this
pro
c
ed
ure of path discov
ery co
ntribut
es to additio
nal
messag
e overhe
ad an
d energy co
st. Therefo
r
e,
in orde
r to raise the rel
i
ability of data
transmissio
n, multipath ro
uti
ng protoco
l
s are no
rmal
ly used
a
nd
this event ha
ppen
s wheth
e
r
era
s
u
r
e code
is used or n
o
t [8-10].
To the be
st
of the autho
rs’ knowl
edg
e
,
no
su
ch m
u
tlipath ro
uting exist in
wirel
e
ss
sen
s
o
r
netwo
rk that add
re
sse
s
the the probl
em
s of me
ssage ove
r
he
ad
and en
erg
y
consumptio
n
whi
c
h ema
n
a
te from the path co
n
s
tru
c
tion
ph
ase a
nd da
ta duplicatio
n tran
smissi
on,
respe
c
tively. Therefo
r
e,
in this pap
e
r
we p
r
op
ose a rob
u
st
path co
nst
r
u
c
tion for d
a
ta
transmissio
ns in nod
e-di
sj
oint multiple
paths
r
outin
g
(RNDMR) fo
r WS
Ns th
at aims to p
r
ovi
ed
low ovherad
path con
s
tru
c
tion as
well
as
p
r
ov
ide
data tran
smi
ssi
on
relia
bili
ty by usin
g
XOR
-
based co
ding
algorithm. T
he pro
p
o
s
ed
RNDMR co
mp
ri
se
s of five different feature
s
, nam
ely,
path con
s
tru
c
tion, d
r
a
s
tic decre
ase in
routin
g
ove
r
head, filteri
n
g overl
app
ed
paths,
attaining
multiple nod
e
-
disj
oint routi
ng path
s
, and reliabl
e data transfe
r across multiple
paths. RNDM
R
employs XO
R-b
a
sed cod
i
ng algo
rithm
,
which d
o
e
s
not involve high sto
r
ag
e
spa
c
e o
r
hi
gh
comp
utation
power. RNDMR bre
a
ks u
p
the
tran
sm
itted me
ssag
es i
n
to
seve
ral fra
g
ment
s of
equal
sizes,
add
s XOR-b
a
se
d erro
r correctio
n
co
d
e
s a
nd spre
ads it a
c
ross multiple pat
hs
con
c
u
r
rently in orde
r to en
han
ce the reliab
ility of transmissio
n and
guarantee th
at a fundame
n
tal
segm
ent of th
e pa
cket re
aches th
e
sin
k
node
with
o
u
t
introdu
cin
g
a
n
y extra en
ergy con
s
u
m
pti
on
and del
ays d
u
ring the p
e
ri
od of data ret
r
an
smi
ssi
on.
The rem
a
ind
e
r of the pap
er is o
r
gani
ze
d as follows. Section 2 p
r
o
v
ides a bri
e
f overvie
w
of relate
d works. T
he p
r
opo
sed
RNDMR
routin
g
scheme
is d
e
scrib
ed i
n
Section
3. T
he
simulatio
n
se
tup and discu
ssi
on of simu
lation re
su
lts
are presente
d
in Se
ction 4 and Sectio
n 5,
respe
c
tively.
Finally, the concl
u
si
on of
this work is p
r
ovided in Section 6.
2. Related Work
The ne
ed for fault toleran
c
e em
anate
s
from
the ne
ed to en
su
re
that the system is
alway
s
a
c
ce
ssible
for use without any
f
o
rm of
inte
rru
ption
of se
rvice as
a
re
sult
any type
of fault.
Therefore, fa
ult toleran
c
e
raises th
e rel
i
ab
ility, accessibility and
consequ
ently depe
ndability
of
the system. In fault tolera
nce, the mo
st famous
ap
p
r
oa
ch i
s
multipath ro
uting, whe
r
e a p
a
ir
of
multiple path
s
amon
g the sou
r
ce no
des an
d
the
sink a
r
e de
termine
d
at the expense
o
f
increa
sed
co
nsum
ption of
energy an
d gene
ration of
traffic. Another goo
d featu
r
e for multipa
t
h
routing
i
s
the
provisio
n of
load
b
a
lan
c
i
ng a
n
d
ban
d
w
idth
agg
reg
a
tion. Th
e
categori
z
atio
n
of
routing
proto
c
ol
s bei
ng
recom
m
en
ded
for
WSNs
are
divided i
n
to thre
e g
r
oup
s, which
is
subj
ecte
d to
the pro
c
e
d
u
r
es u
s
e
d
for
discoveri
ng t
he path. In t
he case of p
r
oa
ctive ro
uting,
every path i
s
cal
c
ulate
d
a
nd con
s
e
r
ved
in advan
ce
and
stored in
the ro
uting t
able, for
re
active
routing, eve
r
y path is cre
a
ted on d
e
m
and ba
si
s, a
nd in hybri
d
routing, whi
c
h
is a mix of both
proa
ctive and
reactive routi
ng [11].
There are two tech
nique
s [9] used to
cre
a
te multi
p
le path
s
. In the ca
se of
disjoint
multipath, it b
u
ilds a
numb
e
r of
alternat
e path
s
th
at
can
eithe
r
b
e
nod
e o
r
lin
k
disjoi
nt with
the
prima
r
y path.
Thus, when
brea
kd
own o
c
curs in ei
the
r
a nod
e or li
nk on the
pri
m
ary path, th
e
alternative
p
a
ths
are
u
s
e
d
directly. Th
e creatio
n
of
these alte
rn
ative path
s
i
m
plies that t
here
woul
d be a
n
increa
sed
e
nergy
con
s
u
m
ption a
s
co
mpared to th
at of the pri
m
ary path,
which
results from
their exten
s
i
v
e latency.
Additi
onally, global to
polo
g
y kno
w
le
dg
e is
requi
re
d
to
facilitate the creation of the multiple disjoint pat
hs. Using this mult
ipath techni
que in a network
with
k
node
-di
s
joint route
s
from the
sou
r
ce toward
de
stination
can
usu
a
lly tolera
te a minimum
of
1
k
interm
edi
ate net
work
comp
one
nt b
r
ea
kdo
w
n
s
[1
2]. The
se
co
nd te
chniq
u
e
is b
r
ai
de
d
multipath,
wh
ich
i
n
volves cre
a
ting an alternativ
e
p
a
th for every
nod
e in
the
prim
ary p
a
th. It
implies that t
he alte
rnate
paths in a
braid pa
rtia
lly o
v
erlay with
th
e prim
ary
pat
h. Ho
weve
r, the
con
s
tru
c
tion
of the alterna
t
ive paths are
not costly
in comp
ari
s
o
n
with the prim
ary path, in term
s
of latency an
d overh
ead.
Thoug
h in a
situation
whe
r
e the
whole
or mo
st part
s
of the no
d
e
s
along th
e p
r
i
m
ary path
s
e
n
co
unter any
failure, th
e
d
i
scovery of n
e
w p
a
th b
e
co
mes
ne
ce
ssa
r
y,
whi
c
h
cont
ri
butes to extra ove
r
he
ad
s [13]. Th
e
cla
ssifi
cation
of relia
bility mechani
sm
s in
multipath ro
uting are divid
e
d
into repli
c
at
ion and retra
n
smi
ssi
on types.
2.1. Retr
ans
m
ission Bas
e
d Schemes
It is the
mo
st pop
ular me
chani
sm u
s
e
d
for
re
tran
sm
itting data
pa
ckets to
the
sin
k
o
n
Evaluation Warning : The document was created with Spire.PDF for Python.
ISSN: 16
93-6
930
TELKOM
NIKA
Vol. 13, No. 3, September 20
15 : 904 – 921
906
each multiple
paths by ta
king into a
ccount t
he lea
s
t hop cou
n
t or the lea
s
t con
s
um
ption
of
energy subje
c
ted to th
e
con
d
ition
s
of
the net
work. The p
r
o
c
e
dure
involve
s
the
sin
k
n
ode
sen
d
ing
ackn
owle
dgem
ent
back to the
source a
n
ytim
e a data
pa
cket is succe
s
sfully received
by
sin
k
d
u
rin
g
transmi
ssion. I
n
a
situatio
n
whe
r
e th
e a
c
kno
w
le
dgem
ent was not
delivere
d
to t
h
e
sen
der
and
a timeout occurs, ret
r
an
smissi
on of
the data p
a
cket wo
uld h
a
ve to be d
one.
More
over, th
e rate of pa
cket loss through the
wireless lin
k in
WSNs is m
u
ch g
r
eate
r
in
comp
ari
s
o
n
with othe
r n
e
tworks, so
the most fa
mous
me
cha
n
ism u
s
e
d
i
s
the lin
k le
vel
retra
n
smi
s
sio
n
s. But the negative effect
when u
s
in
g th
is me
cha
n
ism is the rise in netwo
rk traffic,
whi
c
h re
quire
s more co
nsu
m
ption of re
source
s.
By sending a
n
acknowl
edge
me
nt message a
l
so
might rai
s
e
delivery dela
y
s leadin
g
to several loss of packets
becau
se of the likeli
hood
of
colli
sion
s o
c
curri
ng. Anoth
e
r con
s
ide
r
at
ion is
the i
s
sue
of mem
o
ry; more
m
e
mory
spa
c
e
is
requi
re
d by t
he sen
s
o
r
no
des t
o
en
su
re bufferi
ng of
the pa
ckets
till the ackn
o
w
led
geme
n
t from
the destination is receiv
ed [14, 15]. In the subsequent parag
raphs, we
will ex
plain the
rout
ing
proto
c
ol
s ba
sed on ret
r
an
smissi
on me
ch
anism a
nd p
r
ese
n
t the main con
c
e
p
ts of
the proto
c
ols.
The mo
st innovative and well kn
own routing protocol prop
os
ed i
n
WSNs is
Dire
cted
Diffusio
n
routi
ng p
r
oto
c
ol [1
6]. Many othe
r rout
ing
protocol
s
are
no
rmally ba
sed
on the
co
nce
p
ts
of Directe
d
Diffusio
n
o
r
f
o
llow th
e
sa
me con
c
ept.
The b
a
si
c
proce
dure for this
proto
c
ol
i
s
to
ensure th
at the sin
k
b
r
oa
d
c
a
s
ts an i
n
terest pa
ck
et which h
a
s to b
e
peri
odi
cally refre
s
he
d in
side
the netwo
rk.
This pa
cket is a que
ry, which in
clu
des the informati
on that
the si
nk re
que
sts f
r
om
the
se
nsor n
ode
s.
Up
on receivin
g
the query pa
ck
et, the entire no
de in the
net
work
ca
ch
es
the
packet i
n
th
e
i
r respe
c
tive
memori
es b
e
f
ore
attempting to
flood
it to
surro
undi
ng n
e
igh
bors to
ensure th
at a
ll node
s recei
v
ed it. Every singl
e no
de
create
s
a
gra
d
ient, whi
c
h in
clud
es th
e da
ta
rate
as well a
s
the
di
re
ctio
n whe
r
e th
e d
a
ta will
be
tra
n
smitted.
Wh
en a
n
ode
se
nse
s
an
even
t in
the monitori
ng area, it will compare it
with
the information bei
ng main
tained in its cache.
Whe
never
a
match is
di
scovere
d
, the node i
s
consi
dered to
be the so
u
r
ce
nod
e, which
perio
dically b
r
oad
ca
sts a
messag
e at
low
rate i
n
o
r
de
r to fo
rwa
r
d p
a
cket
s.
Whe
n
the
si
n
k
receives n
u
m
ero
u
s d
e
te
ction event
s, meaning th
at
there are
multiple paths existin
g
a
t
the
source at a
given instant, it
will broadcast a
reinfo
rcement on
one of these
paths (norm
a
lly
a
path havin
g the lea
s
t del
a
y
) by increa
si
ng the d
a
ta
rate of the qu
ery pa
cket. In a situatio
n whe
n
failure
occu
rs in the
reinfo
rce
d
p
a
th, th
e sin
k
ca
nnot
dete
c
t any
kind of d
a
ta. It reinitiate
s t
he
reinfo
rcement
messag
e
to use other pat
hs
in ord
e
r
to
reroute the l
o
st data.
Th
e
r
efore, to en
sure
provisi
on for
quicke
r
re
cov
e
ry ari
s
ing
o
u
t of path
failure,
the sink sho
u
ld
pe
riod
ically
broad
cast
reinfo
rcement
message
s to enable fa
ster di
sc
overy of alternative
path, which should b
e
con
s
tru
c
ted
o
n
-de
m
an
d ba
sis. As thi
s
p
r
otocol
is
ba
sed on q
uery
driven d
a
ta d
e
livery, it doe
s
not work
well
in e
n
viro
nme
n
tal mo
nitorin
g
ap
plication
s
, which n
e
e
d
reliable
dat
a delive
r
y to t
h
e
sin
k
. Also, du
e to its ene
rg
y requi
reme
nt in bro
a
d
c
a
s
ting lo
wer
rate
of messag
es,
the proto
c
ol
i
s
not re
garded
as
ene
rgy e
fficient protocol. The
se
n
s
ors mi
ght
contribute
ad
d
i
tional ove
r
he
ad
whe
n
matchi
ng data an
d q
uerie
s.
Another prot
ocol based on Directed Diffusion
routing is the highly-resilient, Energy
Efficient Multipath Ro
uting
Protocol fo
r
WSNs
[17]. The re
se
arch
ers ill
ustrate
how a m
u
ltip
ath
routing te
chni
que discove
r
s partial di
sjo
i
nt paths;
the discovere
d
p
a
ths are
not disjoi
nt paths as
in Di
re
cted
Di
ffusion, b
u
t th
ey are
kno
w
n
as b
r
ai
d
ed
multipath. Thi
s
p
r
oto
c
ol
ma
intains the
co
st
lowe
r by m
a
i
n
taining th
e
multipath a
s
well a
s
re
cov
e
ring
from
pa
th failure
s m
o
re
qui
ckly.
The
protocol al
so avoids the periodi
c flooding that is utilized in Di
rected Diffusion routing. In this
proto
c
ol, the
multipath am
ong the
sou
r
ce node
and t
he sin
k
i
s
co
nstru
c
ted
by the net
work, then
a path i
s
cho
s
en
as th
e primary path to
route t
he
da
ta packet, an
d altern
ative paths
are
ke
pt
alive by
con
s
tantly tran
smi
tting a
“keep
-alive”
data a
m
ong
the pat
hs. Whe
n
th
e
p
r
ima
r
y
pat
h
fails, the n
o
des re
cove
r
quickly throu
gh reinfo
rce
m
ents
of oth
e
r p
a
ths to reroute
the
d
a
ta
packet
s
that have bee
n lo
st. Furthe
rmo
r
e, the ene
rg
y consumptio
n in this prot
ocol results from
all the
path
s
(that i
s
, fro
m
source
to
sin
k
),
which
are
set in
advan
ce
and
sto
r
ed
thou
gh
perio
dically transmitting
a l
o
w d
a
ta rate
data, kn
ow
n
as
“keep
-aliv
e”. Thi
s
p
r
o
c
e
ss i
s
reg
a
rd
e
d
to
be more rob
u
s
t, howeve
r
it incre
a
ses th
e netwo
rk
co
st in terms of
con
s
um
ption
of energy.
Energy
con
s
umption i
s
th
e main
criteri
a
for
Reli
able
Energy Awa
r
e
Routin
g (REAR) i
n
WSNs [18]. It reco
mmen
d
s
an
ene
rgy
reservatio
n schem
e to be
use
d
for
rou
t
ing data to t
he
sink. Additionally, to ensure netwo
rk rel
i
ability, a backup path is
establi
s
hed for every primary
path from
th
e so
urce to
sin
k
. The
ma
in co
ncept of
the protocol
is to e
n
sure
that if the si
nk
receives
an i
n
tere
st thro
u
gh a sou
r
ce node, whic
h
doe
s not bel
ong to its
ro
uting table, it will
cre
a
tes two
d
i
sjoint p
a
ths to the
sou
r
ce
node. A
spe
c
ific path i
s
th
en cho
s
en
a
nd em
ployed
to
Evaluation Warning : The document was created with Spire.PDF for Python.
TELKOM
NIKA
ISSN:
1693-6
930
Rob
u
st Path Con
s
tru
c
tion
for Relia
ble Data Tr
an
sm
ission
s in Node
… (Abdul
alee
m
Ali Alm
a
zroi)
907
transmit the
data pa
cket. Another
path
(the
se
c
ond
path) i
s
al
so
employed to
be the b
a
ckup
path in
the
ev
ent of fail
ure
happ
ening.
Additionally, p
a
r
t of the
e
nergy will
be
con
s
erve
d fo
r
bo
th
paths in all th
e interme
d
iat
e
node
s alo
n
g
these p
a
ths. In the event of a path failure ha
ppe
nin
g
,
the interme
d
i
a
te node tran
smits the d
a
ta packet b
a
ck to the so
urce no
de a
nd
the sin
k
re
cei
v
es
repo
rting e
r
ror. The outcome involves both t
he so
urce nod
e and the sin
k
h
a
ve to delete the
failure path from their ro
uting tabl
e. The
energy con
s
erved for that
spe
c
ific path
is relea
s
e
d
from
every node al
ong that path
.
Lastly, all th
e traffic
is re-dire
c
ted to the backup p
a
th. But when the
prima
r
y
path
(that
is, se
rvice path)
is e
s
tabli
s
he
d
ag
ain, all traffic is q
u
ickly re
-directe
d ag
a
i
n
onto it.
2.2. Replicati
on Bas
e
d Sc
hemes
In WS
Ns,
re
d
unda
ncy i
n
p
a
cket d
e
livery
is
co
nsi
d
e
r
e
d
to b
e
anoth
e
r m
e
chani
sm utilized
to provide re
liable multipl
e
paths routi
ng. R
outing
proto
c
ol
s usually implem
ent a repli
c
a
t
ion
mech
ani
sm to ensure d
e
li
very of origin
al packet
to sink, whi
c
h is
by the transmissi
on of se
veral
copi
es
of ori
g
inal pa
cket a
c
ro
ss
several
path
s
.
The
main
setba
ck whe
n
u
s
in
g this te
chni
que
is
increa
sed
ov
erhe
ad,
norm
a
lly due
to th
e pa
cket
bein
g
sent
by ev
ery n
ode
until
it arrive
s at
the
sin
k
. Thus, in
WSNs, the p
r
ovisio
n of rel
i
ability and load balan
cin
g
can al
so be a
ttained throu
gh
anothe
r tech
n
i
que kno
w
n a
s
co
ding
sche
me [19, 20].
Codi
ng sche
mes split the data packet
s
and tra
n
sm
it them throu
gh diverse di
scovere
d
paths.
This schem
e
con
s
e
r
ves t
r
an
smi
s
sion
an
d re
ce
iving
en
ergy, however
it re
quire
s additio
nal
comp
utation
at every node
and path mai
n
tenan
ce. Th
e su
ccessful impleme
n
tatio
n
of the codin
g
techni
que i
s
also
ba
sed
o
n
the amo
unt
of paths
discovered
and
n
u
mbe
r
of splits receive
d
at
the
destin
a
tion n
ode. Wh
en the delivere
d
numbe
r of data
packet
s
at the destin
a
tio
n
is less than
the
expecte
d (n
e
c
e
s
sary) n
u
m
ber, then th
e origin
al dat
a
can
not be recovered. Also, robu
stne
ss a
n
d
comp
re
ssion
efficien
cy of the codin
g
techniqu
e ar
e th
e main i
s
sue
s
of
con
c
e
r
n.
Thus, t
r
ade
-o
ffs
exists am
ong reliability and energ
y efficiency [21]. In the followi
ng
paragraphs, we descri
be the
routing p
r
oto
c
ols ba
se
d on
repli
c
ation m
e
ch
ani
sm an
d highlight th
eir key ide
a
s.
ReInFo
rM [2
2] has be
en
prop
osed in
multipat
h ro
u
t
ing sen
s
o
r
n
e
tworks. This routing
proto
c
ol em
p
l
oys a metho
d
, kno
w
n a
s
packet dupli
c
ation te
chni
que, to sup
p
l
y desire
d
da
ta
transmissio
n
reliability for
every ap
plica
t
ion. The
pro
c
e
s
s involves an effo
rt to e
nhan
ce
reli
ab
ility
of data tra
n
smissi
on by e
m
ploying the
packet d
upli
c
ation m
e
tho
d
for the
enti
r
e
sen
s
o
r
no
de
s
involved du
ri
ng the p
r
o
c
e
ss
of data transmi
ssi
on without con
s
i
derin
g
pa
cke
t
segme
n
tation
method. Th
e
eminent
relia
bility is attain
ed at hig
her
cost of con
s
u
m
ption of en
e
r
gy and
usag
e of
band
width, which i
s
in co
ntrast
with the ma
in dem
and
s of re
sou
r
ce limited sen
s
o
r
node
s.
H-SPREA
D [23] recogni
zes a multipat
h ext
ension f
l
oodin
g
stag
e, where no
des fro
m
diverse bran
ches
swap the
found path
s
. Con
s
e
quently
, it
finds more
disjoint path
s
at the co
st of
extra me
ssag
es
exch
ang
e, by b
r
ea
kin
g
t
he p
r
op
erty o
f
utilizing
"on
e
me
ssag
e p
e
r
node’’.
Wh
en
a sen
s
o
r
no
d
e
finds a n
e
w
path, it notifies its
nei
gh
bor a
bout it. Freq
uently, this info
rmatio
n is
dissemin
ated
over the n
e
t
work to atta
in more
disj
oint path
s
in
each nod
e. Obviou
sly, this
extensio
n bu
rden
s sen
s
o
r
s with exten
s
ive energy
ut
ilization be
ca
use of the e
x
chan
ge of the
extra messa
g
e
s.
Delay-Co
nst
r
ained Hig
h
-T
hrou
ghp
ut
Protocol
fo
r M
u
l
t
ipath Transmissi
on
(DCHT) [24] is
the enh
an
ce
d versi
on of
Dire
cted
Dif
f
usion
(
DD), whi
c
h advo
c
ate
s
the id
ea of empl
o
y
ing
multipath rou
t
ing. The ro
uting fun
c
tio
n
in the p
r
o
t
ocol b
egin
s
throug
h flo
oding
an int
e
re
st
messag
e to the entire n
e
twork bet
wee
n
the sink
to
source n
ode
con
c
urre
ntly. At any
time, a
sou
r
ce no
de
have the cap
ability to deliver the
data
being d
e
man
ded throug
h the sin
k
n
ode
. It
transmits dat
a packet
s
tha
t
have been
discovered in
t
he dire
ction
of the sink n
ode, in the ini
t
ial
pha
se
by u
s
ing
re
co
gni
zed
gradie
n
ts. When
ever
seve
ral
co
pies of the
occurre
n
ces
are
establi
s
h
ed, reinforcem
ent
messag
es are tran
smi
tted
by the si
nk to
a spe
c
ific n
e
i
ghbo
r d
e
si
rin
g
greate
r
f
r
eq
u
ency f
r
om
a
pa
rticul
ar
n
e
ighb
or.
On
every o
c
ca
si
on, it receives
notificatio
n of
detectio
n
eve
n
ts. In
ca
se
o
f
node
b
r
ea
kdown in
th
e
reinforced
p
a
th, rei
n
forcem
ent is
carrie
d
out
by sink b
e
ca
use of its abili
ty to sense a
n
absen
ce
of detectio
n
eve
n
ts. The main
proble
m
of this
proto
c
ol, with
respe
c
t to energy co
nsumption
a
n
d
messag
e ov
erhe
ad, is th
at reinfo
rcem
ent
messag
es
wil
l
have o
cca
si
onally tran
sm
itted by t
he si
nk throug
h m
any path
s
to
ward the
sou
r
ce
node.
In WSNs, to i
m
prove the reliab
ility of packet delivery, Reed
Solom
o
n algorithm [25], with
Multipath on
Dema
nd Rou
t
ing (MDR), is utilize
d
to code o
r
de
cod
e
and route the data pa
cket
from source
to the sin
k
. In this protocol (t
hat is, M
D
R), the mai
n
con
c
e
p
t en
tails wh
en th
e
Evaluation Warning : The document was created with Spire.PDF for Python.
ISSN: 16
93-6
930
TELKOM
NIKA
Vol. 13, No. 3, September 20
15 : 904 – 921
908
s
o
urce has data to transmit to the
s
i
nk
,
where
it
initiates th
e
pro
c
ed
ures o
f
routing
req
uest
pha
se throug
h flooding in
the netwo
rk. This
floodi
ng me
cha
n
ism comp
ri
se
s the IDs of the
sou
r
ce a
nd t
he si
nk,
re
sp
ectively and
also th
e requ
est ID. At an
y time, the si
nk
re
ceive
s
a
n
y
route
req
u
e
s
t messag
es, i
t
respond
s
a
nd re
se
nd
s a
route
reply
messag
e wit
h
additio
nal f
i
eld
that sig
n
ifies
the total n
u
m
ber
of ho
ps.
So
every
nod
e re
ceivin
g t
he route
re
pl
y messag
e
can
now in
crea
se
the hop
cou
n
t and relay the me
ssage t
o
the nea
re
st
neighb
or. Th
ese p
r
o
c
e
dures
contin
ue
up
till ce
rtain
time
, the
sou
r
ce
node
w
ill
gat
hers
every
ro
ute reply m
e
ssag
e
re
ceive
d
. It
maintain
s the
IDs of it
s ne
ighbo
rs
and
also th
e le
n
g
t
h of the pat
h. In the la
st pro
c
e
dure, the
sou
r
ce n
ode
fragme
n
ts th
e data
pa
cke
t
based o
n
t
he n
u
mbe
r
o
f
paths,
path
length
s
a
nd
the
maximum probability of failure.
3. Descrip
tio
n
of RNDM
R
Rou
t
ing
In this
se
ctio
n, we
pro
p
o
s
e a robu
st p
a
th co
nst
r
u
c
tion for
data transmi
ssion
s
i
n
nod
e-
disjoi
nt multiple path
s
ro
uting for
WSNs,
whi
c
h
is useful to fin
d
node
-di
s
joi
n
t multiple p
a
th
s
betwe
en the
sou
r
ce a
nd t
he de
stinatio
n with l
o
w ov
erhe
ad
as well as attain
data tra
n
smission
reliability by utilized XOR-based coding
algorithm.
3.1. Cost Fu
nction an
d Route Selec
t
i
o
n
The mai
n
co
nce
p
t for
rou
t
e sele
ction i
s
the
ca
pabili
ty of having to ch
oo
se a
n
optimal
path to extend the lifetime of t
he netwo
rk. Thi
s
co
ncept is found
e
d
on path co
st function. T
he
key purpo
se
of path co
st function i
s
to provi
de ad
di
tional weig
ht/co
s
t to the node that has a
lesser
amou
nt of energy
in attempting to exten
d
its lifetime. Let
12
3
,
,
,
.
.
...
.,
jn
PP
P
P
P
rep
r
e
s
ent the
paths
with l
o
w ove
r
he
ad
emanatin
g throu
gh the
source
S
to d
e
stinatio
n
D
by
variou
s intermediate no
de
s
12
3
,
n
,
n
,
.
.
....
,
k
nn
then:
11
2
3
2
456
37
8
9
PS
n
n
n
D
PS
n
n
n
D
PS
n
n
n
D
In attempting
to choo
se th
e optimal pat
h, t
he path cost functio
n
take
s into a
c
count the
total cost of a
ll intermedi
ate node
s on e
v
er
y path, as
rep
r
e
s
ente
d
in Equation (1
):
1
C(
P
)
(
)
k
ii
i
f
c
(1)
Whe
r
e
i
ndicates th
e t
o
tal co
st of all
node
s
on p
a
th by taki
ng in
to con
s
id
eration the
re
sidu
al
energy and
the sum of t
he hop
s
wh
erea
s
denoting th
e path cost
of the path
P
.
Con
s
e
quently
, to choose
the optimal path betw
e
e
n
a pair of paths that h
a
ve founded
on
Equation
(1
) du
ring
ro
ute di
scovery
with lo
w
ove
r
hea
d, the
o
p
timal p
a
th
meant to
be
the
minimum tota
l cost is d
e
si
g
nated a
s
Equ
a
tion (2
):
_pa
t
h
m
i
n
(
)
j
O
p
tim
a
l
C
P
P
P
(2)
Figure 1. Net
w
ork with 1
0
node
s
f(
)
ii
c
()
CP
Evaluation Warning : The document was created with Spire.PDF for Python.
TELKOM
NIKA
ISSN:
1693-6
930
Rob
u
st Path Con
s
tru
c
tion
for Relia
ble Data Tr
an
sm
ission
s in Node
… (Abdul
alee
m
Ali Alm
a
zroi)
909
As sho
w
n in
the Fig
u
re
1
a
bove, there a
r
e th
r
ee
path
s
fro
m
si
nk n
ode to
de
stin
ation no
de
(W).
As p
e
r Equat
ion
(1), P
1
,
P2 an
d P3
d
enote th
e
su
m of
co
sts a
nd the
r
efo
r
e
the cost
of th
ese
paths a
r
e;
,
, and
Hen
c
e, from
Equation (2), the optimal p
a
th for Figu
re
1 is
1
P
.
3.2. Path Co
nstru
c
tion
Any time a sink no
de req
u
ire
s
a spe
c
i
f
ic informatio
n about the
netwo
rk, it verifies it
s
route ta
ble t
o
confirm
ap
proval if th
ere is
an
app
ropriate
ro
ute. Wh
en true,
it transmits t
he
intere
st pa
cket to th
e
best
su
bseq
uent h
op
in
the di
re
ction to
wards the d
e
stin
ation.
Neverth
e
le
ss,
when si
nk va
lid route to the destin
a
tion is ab
sent and
not available
,
it can begin a
route
discove
r
y pro
c
e
s
s. In order to
st
art su
ch a p
r
oce
s
s, the
sink n
ode
co
n
s
tru
c
ts
a RREQ
(Ro
u
te Re
qu
est) me
ssag
e
that compri
ses of explan
a
t
ions for all t
he inform
atio
n need
ed by the
use
r
. The
pa
cket hold
s
pt
ype, SrcID
a
ddre
s
s,
dno
d
e
ID ad
dress, brID, h
c
unt,
Enr_
co
st an
d
Route
_
list fiel
ds a
s
sho
w
n
in Figu
re 2. T
he fiel
d, ptype, denote
s
th
e pa
ck
et type, which is
rou
t
e
requ
est
me
ssage. T
he fiel
d
,
hcu
n
t, indi
cates
hop
cou
n
t and
it i
s
i
n
crea
sed
by
on
e for eve
r
y no
de
throug
h
whi
c
h pa
cket p
a
sse
s
. Th
e b
r
ID field
signifie
s
broad
ca
st ID and
it al
ways incre
a
se
s ea
ch
time the sin
k
node b
egin
s
a RREQ. In
view of th
is
pro
c
e
ss, a di
stinct ide
n
tifier for
RREQ
is
cre
a
ted by th
e bro
a
d
c
a
s
t ID and th
e ad
dre
ss
of
the node, which i
n
itiated the RREQ me
ssag
e.
The En
r_
co
st
field
rep
r
e
s
e
n
ts the
total
energy
co
st. Once a
p
a
cket pa
sses through
a
nod
e, it
s
energy co
st is add
ed to this field (i.e., Enr_cost).
Initially, by de
fault, this field contai
ns
zero
value. The
Route_li
s
t field
is a p
a
th con
s
tru
c
tion li
st of the route
p
a
th. To asce
rtain nod
e-di
sj
oint
multiple path
s
having l
e
sser b
r
oad
ca
st
overhe
ad,
the lea
s
t ene
rgy co
st is u
s
ually asso
cia
t
ed
with difficult
p
r
ocedu
re
s e
s
peci
a
lly if there a
r
e
limite
d
kno
w
le
dge
o
n
the top
o
log
y
of the network
and variatio
n
s
are fre
que
n
t. Therefore, the signifi
cant
purpo
se of RNDM
R is th
e con
s
tru
c
tio
n
of
node
-di
s
joint
multipath that
con
s
i
s
ts
of a
low
routin
g o
v
erhea
d a
nd
the minimu
m
energy path i
n
the pe
rio
d
of
a route
disco
v
ery to e
n
sure mu
ch
g
r
eat
er reali
z
atio
n delivery ratio.
To acco
mpli
sh
this pu
rp
ose, the no
de
hol
ding the
ne
cessary
i
n
form
ation shoul
d
have kno
w
le
dge of th
e e
n
t
ire
routing
path l
i
st of existin
g
route
s
to
all
o
w fo
r
the se
lection of
the
most
suita
b
l
e
nod
e-disj
oi
nt
route
path
s
within the
ex
isting
can
d
id
ate path
s
. When the
RRE
Q
me
ssage
s are
create
d
or
relayed
throu
gh the
si
nk insid
e
the
net
work
as de
scribed
in
Figu
re 2, eve
r
y no
de atta
che
s
i
t
s
own a
ddress
and ad
ds its
energy co
st
to the routing
requ
est me
ssage.
Figure 2. RREQ messag
e
As sh
own in
the Figu
re 2
above, when
a
RREQ me
ssag
e re
ache
s its nod
e havi
ng the
requi
re
d information (de
s
tination n
ode
),
then it is
re
spon
sible fo
r d
e
cidi
ng if the
routing
path i
s
a
node
-di
s
joint
path o
r
oth
e
rwi
s
e.
On
ce a no
de
-di
s
joint p
a
th h
a
ve bee
n ve
rified, the n
ode
prod
uces a
Route Re
ply messag
e, as d
e
scrib
ed in
Fi
gure 3 that h
o
lds the n
ode
list of the entire
route
path
an
d then
u
n
ica
s
ts in
the
direction whe
r
e th
e o
r
iginat
ed
RREQ
me
ssa
ge i
s
eman
atin
g
from. On
ce
an inte
rme
d
i
a
te no
de
re
ceives
a
RRE
P messa
ge,
it update
s
th
e ent
ries in t
he
routing tabl
e usin
g the nod
es list of the entire rout
e p
a
th contai
ned
in the Route
Reply me
ssa
ge.
3
(
)
20
30
40
90
CP
2
(
)
30
20
20
70
CP
1
(
)
20
42
62
CP
Evaluation Warning : The document was created with Spire.PDF for Python.
ISSN: 16
93-6
930
TELKOM
NIKA
Vol. 13, No. 3, September 20
15 : 904 – 921
910
Figure 3. RREP message
Figure 4 de
scrib
e
s
an ex
ample of p
a
th co
ns
tructio
n
and it con
s
ist
s
of four node
s,
namely, Sink,
N, V and W. If
the sink n
ode intend
s to transmit a spe
c
ific ta
sk t
o
node W, an
d if
the Sink no
d
e
ro
ute to
W i
s
n
on-existen
c
e i
n
it
s ro
uting tabl
e, it transmit
s
a
RREQ. If the RREQ
is re
ceive
d
b
y
node
N, it must atta
ch i
t
s add
re
ss,
i
n
crea
se the f
i
eld of
ho
p count by on
e, and
update th
e e
nergy
co
st field of the
RREQ b
e
fo
re f
o
rwarding th
e re
que
st, be
cau
s
e
route
W is
inacce
ssible
and
ha
s no
route to
it. Li
ke
wise, if no
de V
re
ceive
s
the
RREQ,
it attach
es i
t
s
address
and i
t
s ene
rgy
co
st and in
crea
ses the
fiel
d of
hop
co
unt by
one in
the
RREQ me
ssag
e.
Once the req
uest arrives a
t
the target W, node W
exa
m
ines the pat
h con
s
tru
c
tio
n
list (Sink-N-V)
throug
h the
RREQ
an
d reviews if the
routin
g path
is a
no
de-di
sjoint p
a
th o
r
otherwi
se.
Once
true, nod
e W prod
uces a
Route
Reply
messag
e,
wh
ich hol
ds the
path con
s
tru
c
tion list for t
he
entire
path
a
nd forwa
r
d
s
i
t
towards the
dire
ctio
n
of
the si
nk
nod
e, whi
c
h i
n
itiated the
RREQ
messag
e. If not true, node
W reje
ct
s the received RREQ messag
e.
Figure 4. Path c
o
ns
truc
tion proc
es
s
3.3. Route Reques
t
Br
oa
dcas
t
w
i
th L
o
w
Ov
erhead
Whe
n
a no
de
gets a
RRE
Q messa
ge,
whi
c
h ha
ppe
ns to be it
s first one, it exa
m
ines th
e
path co
nst
r
u
c
tion list from the me
ssage
packet, cal
c
ul
ates total hop
s sta
r
ting fro
m
the sou
r
ce
to
itself and the
n
re
co
rd
s the
total resi
dual
energy
in its route table.
W
hen the n
ode
gets the
RRE
Q
identical me
ssag
e for anot
her time, th
e
node
cal
c
ul
ates the
num
b
e
r of
hop
s fro
m
the
sou
r
ce
to
itself an
d co
ntrast
s it to t
he n
u
mbe
r
o
f
the s
horte
st
hop
s, which
is
st
ored i
n
the entry
of the
routing ta
ble.
If the new me
ssage
ha
s smaller
num
b
e
r
of hop
s, the
node
attach
e
s
its a
ddresses,
in ad
dition to
its en
ergy co
st, to the
rout
e path
li
st for
the RREQ
m
e
ssag
e a
nd t
hen t
r
an
smits the
RREQ
me
ssage to
su
rro
undin
g
no
de
s. Othe
rwi
s
e,
the ne
w
RREQ messa
g
e
is reje
cted.
The
pair
(Sou
rce
add
re
ss, B
r
oad
ca
st ID) is utiliz
ed
to different
iate the me
ssage
pa
cke
t
s.
Con
s
e
quently
, for this met
hod, seve
ral
identical RREQ messa
g
e
s
will b
e
rej
e
cted
when
n
e
w
RREQ
has g
r
eater nu
mbe
r
of hops whe
n
comp
ared to the re
cord.
Evaluation Warning : The document was created with Spire.PDF for Python.
TELKOM
NIKA
ISSN:
1693-6
930
Rob
u
st Path Con
s
tru
c
tion
for Relia
ble Data Tr
an
sm
ission
s in Node
… (Abdul
alee
m
Ali Alm
a
zroi)
911
Figure 5. RREQ Propag
ation with the Shorte
st Hop
s
From
the illustration in
Fi
gure 5,
starti
ng
from the
sink node to
node
N, there are a
combi
nation
of five route
paths, n
a
mel
y
: Sink-N
, Sink
-F-N
, Sink-G-N
, Sink-
F
-K-
N
, and Sink
-G-
C-N. The tot
a
l numb
e
r of
the hop
s co
mpri
se
s of 1,
2, 2, 3 and
3, in that ord
e
r, and th
e e
nergy
co
sts involve
d
are 0, 20,
30, 50 and 5
0
, resp
ectivel
y
. If node N gets the RRE
Q
packet du
ri
ng
the initial p
e
ri
od from
Sink-N, it regi
ste
r
s 0 to be
the
energy cost a
nd 1 to
indi
ca
te the smalle
st
total of hops. Once no
de
N gets a RREQ identical
messag
e through the re
m
a
ining fou
r
ro
ute
paths, it
co
m
putes the tota
l of ho
ps an
d
contrast
s it to
the
small
e
st
numbe
r
of ho
ps i
n
its routi
n
g
table. Since the total number of ho
ps of
the route list f
o
r all the fo
ur
route paths exceeds 1,
it
will
reje
ct the four Route Requ
est identi
c
al
messag
es.
3.4. Paths O
v
er
lapped Filtering
Additional m
e
thod d
u
ri
ng
Route
r
Req
uest m
e
ssa
g
e
wa
s to
filter ove
r
lap
p
e
d
ro
uting
paths to mi
nimize the
rout
ing overhea
d
.
Fr
om Figu
re 6, node
R
gets three
RREQ
s and th
at
denote
s
thre
e routin
g pat
hs Sin
k
-F
-K, Sink-N-K a
n
d
S-N-V. The
s
e all have an
equal nu
mb
er of
hop
s, that is 3 hop
s. Ho
wever, the method do
es
not
only forwa
r
d t
hem, but also
examines if the
routing
path
s
are no
de-di
sjoint o
r
oth
e
rwi
s
e
before forwardi
ng.
When th
ere
are ove
r
lap
ped
routing
path
s
, deci
s
io
ns a
r
e ta
ken
to
reject
one
of
them for no
d
e
-di
s
joint. T
h
erefo
r
e, n
ode
R
comp
ares
RREQ
s wh
en
it receive
d
th
e messa
g
e
s
within a
s
p
ec
ific
period. As
a result, the
routing p
a
th, Sink-N-K
-R,
whi
c
h in
clude
s a com
m
on
overlap
ped li
nk K-R wh
en
equate
d
with
that
of path Sin
k
-F-K-R. It also
has
additio
n
a
l overla
ppe
d
link, Sin
k
-N,
whe
n
compa
r
ed with th
e p
a
th,
Sink-N-V
-R.
Con
s
e
quently
, it reject
s th
e ro
ut
ing p
a
th, Sink-N-K-R, having
ex
tra two
co
m
m
on
overlap
ped
li
nks
when
co
mpared
with
the othe
r p
a
ths. Th
erefore
,
the concept
wa
s to j
u
st
re-
broa
dcast two RREQ m
e
ssage
s cont
a
i
ning the ro
u
t
ing paths inf
o
rmatio
n of Sink-F
-K-R a
n
d
Sink-N-V
-R.
Thus,
nod
e R can
be
assu
red of two no
d
e
-di
s
joint
rout
ing path
s
. Li
kewi
se, no
de
Q
transmits two
RRE
Q me
ssage
s, on
ce a
s
sure
d of
two
node
-di
s
joint
paths. Eve
r
y neigh
bor no
de
adapt
s thi
s
method
with
low ro
uting
overh
ead
to tran
smit
RREQ m
e
ssa
ges. Alg
o
rith
m 1
highlight
s the
process of RREQ me
ssag
e with low ov
erhe
ad in inte
rmedi
ate nod
es.
Figure 6. RREQ Propag
ation with no Ov
erlap
ped
Evaluation Warning : The document was created with Spire.PDF for Python.
ISSN: 16
93-6
930
TELKOM
NIKA
Vol. 13, No. 3, September 20
15 : 904 – 921
912
Algorithm 1
:
Algorithm to pro
c
e
ss the
RREQ
with
L
o
w broad
ca
st
routing ove
r
h
ead
Set
myadd
re
ss: ad
dre
s
s interme
d
iate n
ode,
ID: broa
dest id of RREQ, mycost: energy
co
st of interm
ediate no
de
Set
SA: Source Add
r
e
ss,
DA: De
stination A
ddress, h: hop co
unt, RT: Ro
uting Table,
Enr co
st: ene
rgy in path
Step1:
Re
cei
v
e RREQ // Check for no
de
addre
s
s equ
al to target //
if
(
my
addres
s
=
=
RREQ[
D
A]
)
then
Act as de
stin
ation to sen
d
reply;
end if
Step 2:
// if node ad
dre
s
s exists in RRE
Q
of path then drop
RRE
Q
//
if
(
m
y
add
re
ss exit in RRE
Q
[
path]
)
then
Dro
p
RREQ; go to step 6.
end if
Step 3:
//Co
m
pare the pai
r (Sou
rce Addre
ss, ID
) of RREQ
with e
a
ch e
n
try of Route
table (RT)//
if
(
RREQ[SA, ID] not ex
is
t in RT [SA, ID]
)
then
//Reco
r
d the
partial info
rm
ation RREQ into RT by cre
a
ting ne
w ent
ry
RT[SA]=
R
RE
Q[SA];
RT[ID]
=
RREQ[ID];
RT[DA]=RRE
Q[DA];
RT[hop]=
RREQ[hop];
RT[Enr
c
o
s
t]=RREQ[Enr
cos
t];
//Assign the h
op to L1 //
L1=
RREQ[h
op];
//Update the fields of RRE
Q
by addi
ng
node
co
st to co
st field, appendi
ng nod
e
address
to Route_li
s
t field , incre
a
si
ng hop //
RREQ [Enr cos
t]=
RREQ[
E
nr c
o
s
t]+
my
c
o
s
t;
RREQ[
Route
list]=RREQ[
R
oute list]+ my
address;
RREQ [h
op]=
RREQ[h
op]+
1
;
Broad
ca
st the RRE
Q to another inte
rm
ediate no
de
else
Step 4:
if match is fou
nd,
then cu
rre
ntly received
RREQ be
com
e
s ne
w dupli
c
a
t
e
RREQ
say
DRREQ, Assi
gn its ho
p to L2.//
if
(
RREQ[S
A
, ID] ex
is
t in RT [SA, ID]
)
then
L2=
DRREQ
[
hop];
Step
5:
// co
mpare the cu
rre
ntly receiv
ed RREQ
(New du
plicate) with previou
s
RREQ //
if
(
L2 >= L1
)
then
Drop DRREQ; go to step 6.
else
RT[SA]=DRREQ[SA]; R
T
[ID]=D
R
R
EQ[ID];
RT[DA]=DRREQ[
DA]; RT[hop]=DRREQ[hop];
RT[Enr c
o
st]=
DRREQ[E
n
r c
o
s
t];
RREQ [Enr c
o
s
t]=
RRE
Q[Enr c
o
s
t]+
myc
o
s
t
;
RREQ[Rou
t
e list]=RREQ
[Route list]+
myaddress;
RREQ [hop]= RREQ[ho
p
]+1;
//Assign its hop to L1 //
L1=
RREQ[hop];
Broadca
s
t the DRREQ t
o
anothe
r inte
rmedi
ate nod
e
Step 6:
perform
step1 t
o
step5.
end
if
end if
end if
3.5. Selecting Node-Disj
o
int Paths
Within the
set of rule
s f
o
r
choo
sin
g
node
-di
s
join
t paths, the
destin
a
tion
node i
s
respon
sibl
e for ch
oo
sing
node
-di
s
joint
route pat
h
s
. To ensu
r
e redu
ction in o
v
erhea
d of the
routing
table
for eve
r
y no
d
e
, the total
n
u
mbe
r
of
nod
e-di
sjoint
rout
ing p
a
ths
are
re
stri
cted to
the
three path
s
that have the smalle
st ene
rgy cost
path
and less nu
m
ber of hop
s e
v
en though m
o
re
Evaluation Warning : The document was created with Spire.PDF for Python.
TELKOM
NIKA
ISSN:
1693-6
930
Rob
u
st Path Con
s
tru
c
tion
for Relia
ble Data Tr
an
sm
ission
s in Node
… (Abdul
alee
m
Ali Alm
a
zroi)
913
than thre
e no
de-di
sjoi
nt pa
ths are explo
r
ed. Th
erefo
r
e if the RRE
Q messa
g
e
s
are received
by
the sen
s
or n
ode
having
th
e requi
red
inf
o
rmatio
n, it
cach
es the
no
de IDs li
st fo
r the
whol
e
ro
ute
paths i
n
its ro
uting table a
n
d
tran
smits th
ree
RR
EP m
e
ssag
es th
at comp
ri
se the
route p
a
ths i
n
the dire
ction t
o
the si
nk,
which i
n
itially sent t
he RRE
Q
me
ssage
s.
In this in
stan
ce, the fo
rem
o
st
route is the route with the smalle
st ene
rgy cost
and n
u
mbe
r
of hop
s. Whe
n
the destin
a
tion n
ode
receives ano
ther
router reque
st me
ssage, it cont
rasts th
e
enti
r
e route pat
h in the RREQ
messag
e to
a
ll the existin
g
nod
e-di
sjoi
nt route
path
s
i
n
its
routin
g t
able. Th
erefo
r
e, if the
r
e i
s
no
sha
r
ed
no
de
amon
g the
route p
a
th in
the RR
EQ
m
e
ssag
e a
nd
any no
de-disj
oint ro
ute p
a
t
h,
whi
c
h is
ca
ch
ed in the d
e
stination’s
rout
ing tabl
e, the
n
the ro
ute p
a
th en
sures t
he re
quireme
nt
and
con
d
ition
s
of the
no
de
-disj
o
int i
s
re
corded
in
the
de
stination’
s routin
g table
.
Else, the
ro
ute
path i
s
di
sca
r
ded. In
ad
di
tion, the third
nod
e-di
sj
oi
nt path th
at ha
s
smalle
st e
nergy
co
st a
n
d
numbe
r of ho
ps is cho
s
en.
At
the end of this pr
o
c
ed
ure, on-de
man
d
data tran
sm
issi
on
s will take
place whe
n
sen
s
o
r
n
ode
s
d
e
tect an
i
n
tere
sti
ng
event. Algorith
m
2
highlig
hts the
p
r
o
c
e
s
s o
f
cre
a
ting no
de
-disj
o
int path
s
.
Figure 7. Con
s
tru
c
tion of n
ode-disj
oint p
a
ths
Algorithm 2
:
Algorithm for creatin
g nod
e-di
sjoint pat
hs
Let
M is a
set
of m-1 multip
le paths fro
m
excludi
ng pri
m
ary
Let
p
1
, p
2
, p
3
,...,p
m-1
be the m-1 multi
p
le path
s
that are sto
r
ed at
two dimen
s
io
nal
array M.
Let
P
p
is p
r
i
m
ary path sto
r
ed 1
-
D a
r
ray N.
Let
D=set of paths that a
r
e
node-disj
oi
nt
to primary. Initialize D= ø.
min C(P
)
:mini
m
um co
st of the path.
// D is
c
o
mputed as
follows
//
for
(k
=
1 to m-1)
do
Selec
t
p
1
from M and
Check it is mini
mum co
st of
the path an
d it is node di
sjoi
nt to
prima
r
y.
if
(
p
1
==
min C
(
P)
)
then
if
(
p
1
∩
P
p
== ø
)
the
n
add
p
1
to D,
M = M - p
1
;
else
Dro
p
p
1
;
end if
end if
end for
3.6. Data Pa
cket Segm
e
n
ta
tion and
Encoding
The
data
packet i
s
divided i
n
to
N s
ub-pa
ckets
havin
g the
sam
e
si
ze
s
, and
an
overhead
pa
rt of
H+
1
, where
H<
N
. M
o
re
over, it al
so
ap
p
end
s th
e
Evaluation Warning : The document was created with Spire.PDF for Python.