TELKOM
NIKA
, Vol.13, No
.2, June 20
15
, pp. 460 ~ 4
6
8
ISSN: 1693-6
930,
accredited
A
by DIKTI, De
cree No: 58/DIK
T
I/Kep/2013
DOI
:
10.12928/TELKOMNIKA.v13i2.132
460
Re
cei
v
ed Au
gust 18, 20
14
; Revi
sed Ma
rch 1
2
, 2015;
Acce
pted Ma
rch 2
9
, 2015
The Implementation of One Opportunistic Routing in
Wireless Networks
Li Han
1,2
*, Huan-y
an Qia
n
1
1
School of Co
mputer Scie
nc
e &
T
e
chnol
og
y, Na
nji
ng Un
iv
ersit
y
of Sci
enc
e &
T
e
chnol
og
y,
Nanj
in
g, Chin
a
,
21009
4
2
School of Co
mputer Scie
nc
e &
T
e
chnol
og
y,
Anh
u
i Un
iver
sit
y
, Hefei, C
h
i
na, 230
03
9
*Corres
p
o
ndi
n
g
author, e-ma
i
l
: liha
n_n
ust@
163.com
A
b
st
r
a
ct
In the
pap
er, i
t
prop
oses
an
opti
m
i
z
at
ion
framew
ork a
ddr
essin
g
fair
ness
issues
for o
p
portun
i
ty
routin
g in w
i
re
l
e
ss mesh
netw
o
rks, w
here w
e
use n
e
tw
ork codi
ng to e
a
se t
he ro
uting
pro
b
l
e
m
. W
e
prop
o
s
e
a d
i
stribute
d
h
euristic
al
gorit
hm in
the
cas
e
w
hen
sch
ed
ulin
g
is d
e
ter
m
i
n
e
d
by
MA
C, an
d d
i
scus
s
the
suitab
ility of o
u
r
algor
ith
m
thr
oug
h si
mu
latio
n
s. It is
found that
in most
sit
uatio
ns our
alg
o
rith
m has
bett
e
r
perfor
m
a
n
ces t
han th
e sin
g
le-
path a
l
gor
ith
m
and th
e cl
ass
i
c
a
l netw
o
rk cod
i
ng w
h
ich is
ba
sed o
pportu
nit
y
algorithm
MORE.
Ke
y
w
ords
:
Op
portun
i
stic Rou
t
ing, Netw
or
k Codi
ng, Util
ity, Suitab
ility
1. Introduc
tion
The
appli
c
ati
on of
wi
rele
ss
cha
nnel
s
p
r
esents
som
e
uni
que
op
p
o
rtunitie
s
th
a
t
can
b
e
use
d
to im
prove the p
e
rf
orma
nce. Fo
r example,
th
e broad
ca
st
nature
of the
mediu
m
can
be
use
d
to p
r
ovi
de op
po
rtunistic tran
smi
ssi
ons j
u
st
as
sugge
sted i
n
t
he pa
pe
r [1]. Also, in
wirel
e
ss
netwo
rks, the
r
e are typicall
y mult
iple paths conn
ectin
g
each sour
ce destin
a
tion
pair; u
s
ing
so
me
of these p
a
th
s in
pa
rallel
can imp
r
ove
p
e
rfor
m
a
n
c
e [
2
]-[4].We
ado
pt an
optimization fra
m
e
w
ork
to de
sign
a
di
stribute
d
m
a
ximization
alg
o
r
ithm.
We
ad
dre
s
s q
u
e
s
tio
n
s
of fairne
ss by maximi
zin
g
the aggregate utility of the end-t
o-end flows,
where we associat
e a utility function
U (·)
wi
th a
flow. We
use network
c
oding [5] to s
i
mplify t
he p
r
oblem
of
sch
edulin
g p
a
cket tran
smi
ssi
ons
across multipl
e
paths, which are si
milarl
y to papers [1
],[3],[4],[6],[7].
Ho
wever, the
traffic alon
g the multiple p
a
ths may inte
rfere
n
ce alon
g with adj
ace
n
t path
s
in wi
rele
ss ne
twork. Some
way is nee
de
d to allevi
ate
the sid
e
-effect of ex
tensive
exploration. In
MORE [6] ,ea
c
h n
ode
ke
ep
s a
pre
-
st
atist
i
cs va
ria
b
le T
X
cre
d
it and
a credit
cou
n
ter. When
nod
e
i
re
ceive
s
a
packet from
a nod
e u
p
stream, it in
cr
ea
s
e
s
th
e co
un
te
r
b
y
its
TX c
r
e
d
i
t. W
h
e
n
the
802.11
MAC
allows the
no
de u
s
ed
for t
r
an
smitting, t
he no
de
will
che
c
k
wheth
e
r the
counte
r
i
s
positive. If yes, the n
ode
will create
a co
ded
pa
cket, and
bro
adcast
s
it, then con
s
ume
the
cou
n
ter. If th
e counte
r
is
negative, the node
ca
n not be used i
n
the transmi
tting. NCMR
[7]
allowin
g
a
forwarde
r b
r
oa
d
c
a
s
t code
d p
a
cket of
a
ge
neratio
n o
n
ly
whe
n
it ha
s
g
o
t all pa
ckets of
the gene
ratio
n
, but it does not work we
ll in most
situ
ations. Both of the two algorithm
s do
not
give any guid
ance to handl
e multiple flows. Th
e
main
contrib
u
tion
s of the paper
are a
s
follows:
(1)
We p
r
op
ose
a network wi
de optimi
z
ati
on alg
o
rithm
that maximizes rate-ba
s
e
d
glob
al net-
work
pe
rform
ance, an
d p
r
opo
se
a p
r
im
al-du
a
l
con
g
e
stion
control
mechani
sm
that ca
n b
e
impleme
n
ted
in a decentral
i
zed fa
shio
n for ea
ch flow.
(2)
It uses the di
stan
ce from t
he se
nding n
ode
s to desti
nation
s
as m
ean
s to alleviate the side
-
effect of extensive explo
r
a
t
ion.
(3)
Comp
ari
s
o
n
s of our algorit
hm with MO
RE and a singl
e-path
routin
g algorith
m
used the
sam
e
kind
of jointly-optimal routin
g and flo
w
-co
n
trol
ap
pro
a
ches
are m
ade
. Simulation result
s sho
w
that our algo
ri
thm outperfo
rms the othe
r two protocols i
n
most situ
ations.
(4)
Analysis
of the appli
c
atio
n occa
sion a
nd ch
oice of param
eters
of netwo
rk
coding b
a
sed
oppo
rtunity algorithm a
r
e al
so mad
e
.
Evaluation Warning : The document was created with Spire.PDF for Python.
TELKOM
NIKA
ISSN:
1693-6
930
The Im
plem
e
n
tation of On
e Oppo
rtuni
stic
Ro
uting in
Wirel
e
ss Network (Li Ha
n)
461
2. Model
2.1. PHY and MAC Chara
c
teris
t
ics
We con
s
ide
r
a network
comp
ri
sing o
f
a set of node
s
N
,
nN
, with the set L of
comm
uni
cati
on links bet
ween them tha
t
are fixed or
time-varying
according to
some
spe
c
ifi
ed
pro
c
e
s
ses. T
here
is
a set of multica
s
t
se
ssi
on
s
C
sharin
g the
ne
twork. Each
se
ssi
on
cC
is
asso
ciated
wi
th the set
c
SN
of
sou
r
ce nod
es, and set
cc
TN
S
of sink no
de
s.
The chan
nel
state vecto
r
()
St
is assu
med t
o
be con
s
tan
t
in each tim
e
slot
t
i.e., s
t
ate
transitio
ns occur only o
n
slot boun
dari
e
s, wh
ere time
t
is
an
in
teg
e
r
.
W
e
ass
u
me
th
a
t
in
eac
h
time slot the value of
S(t)
is
tak
en i.i.d. from a finite set; Let
S
be the s
e
t of
S
.
Den
o
te
R
R
is the vector of link rate,
R
is the physically admissibl
e ra
te.
is the
uppe
r bo
und
of
i
RR
. Let
1
ij
T
if a
packet i
s
succe
ssfully tran
smitted fro
m
i
to
j
. We define
(,
)
(
(,
)
1
)
ij
i
i
j
i
pR
S
p
r
o
b
T
R
S
to be the proba
bility that the
node can su
cce
ssfu
lly transmit a
pack
e
t from
i
to
j
. We also
assume th
at
ij
T
and
kl
T
are ind
e
pend
ent. Wh
enever
a no
d
e
is a
c
tive,
it need
s to
deci
de
whi
c
h
flow it will
be tra
n
smitte
d thro
ugh. It is defin
ed t
h
rou
gh a
flo
w
scheduling profile m
a
trix
A
. If node
i
tra
n
smit
s
a pa
cket fro
m
flow
c
, we
s
e
t
1
ic
A
,
otherwise
0
ic
A
. We say that a
flow
scheduli
ng p
r
ofile i
s
valid if for
ea
ch
iN
, there
exi
s
t
s
only one
cC
s
u
ch that
1
ic
A
. Let
A
be
the set of all valid flow sch
edulin
g profil
es.
2.2. Feasible
Rate Se
t
We furthe
r a
s
sume the system is slot
ted in time. In each slot
0
,
1
,
..
..
t
, a medium
acce
ss p
r
oto
c
ol assig
n
s a
n
activation profile
()
St
and a flow-sched
uling profile
()
A
t
, and to
each tran
smit
ter
c
iS
, we ass
i
gn transmit rat
e
()
i
Rt
.
Let
()
c
f
t
be the
n
u
mbe
r
of pa
ckets
creat
ed
at the so
urce
of flow
c
. The rate vec
t
or
I
S
determi
ned b
y
()
c
cC
ff
t
. Let
()
c
ij
y
t
be the potential nu
mber of pa
ckets that are d
e
stine
d
for
destin
a
tion of
flow
c
out
i
and into
j
;
()
c
ij
y
t
=0,
if
(,
)
ij
L
.
c
i
q
is the nu
mber of pa
ckets that are
destin
ed to
d
e
stinatio
n of f
l
ow
c
. Th
e
system i
s
stabl
e if every
qu
eue
si
ze i
s
b
ound
ed. Th
e
rate
vec
t
or
f
is valid under the foll
owin
g three
condition
s:
()
0
c
Ds
t
c
j
y
(1)
()
cc
ji
c
i
r
c
i
j
jj
yf
l
s
c
y
(2)
,,
,
,
,,
(,
)
(
,
)
c
ij
S
R
A
i
c
i
i
j
cS
R
A
ya
A
R
S
R
p
S
R
(3)
Whe
r
e
con
l
= 1
whe
n
con
is
true, otherwise
0
con
l
.
,,
SR
A
a
≥
0
and
,,
SR
A
a
≤
1. Eq. (3)
implies
c
ij
c
ij
y
belo
ngs to the
,
(,
)
ij
c
ij
Hull
R
S
R
. Definition 1
.
Vector
f
is said to be
feasibl
e
if each flow
c
can tran
spo
r
t information from
cc
s
S
to
cc
tT
at rate
c
f
. Theorem 1. Let
F
be the set of
end-to
-en
d
rate vector
()
cc
C
ff
su
ch that there exists vecto
r
s
,,
()
c
ij
i
j
N
c
C
yy
and
,,
,,
()
SR
A
S
S
RR
AA
aa
that s
a
tis
f
y Eq. (1,2,3) is
s
u
bjec
ted to
,,
0
SR
A
a
and
..
..
1
SR
A
SR
A
a
a
. The
vec
t
or
f
is fe
asibl
e
, whe
n
codi
ng ge
ne
ration si
ze g
o
e
s to infinity if and only if it belong
s to
F
.
More
over, the set of feasi
b
le end
-to-en
d rates
F
is co
nvex.
Proof: Follows
direc
t
ly from [1]
Evaluation Warning : The document was created with Spire.PDF for Python.
ISSN: 16
93-6
930
TELKOM
NIKA
Vol. 13, No. 2, June 20
15 : 460 – 46
8
462
3. Optimal Flo
w
Sc
hedule
3.1. Maximiz
a
tion of
Utility
For ea
ch
flo
w
cC
, we define a
utility function
()
c
Uf
t
o
b
e
a
st
ri
ct
ly
con
c
av
e,
increa
sing
fu
nction
of e
n
d
-
to-e
nd flo
w
rate
c
f
. The
goal of
utility maximization is to achiev
e
trade
-off bet
wee
n
efficien
cy and fairne
ss.
We c
an
write the n
e
twork-wi
de op
timization p
r
o
b
lem
as:
max
(
),
c
cC
Uf
f
F
(4)
Since set of
F
is convex a
nd the obje
c
t
i
ve is stri
ctly con
c
ave, the
r
e exist
s
a u
n
ique
solut
i
o
n
f
of the maximization problem.
Corre
s
p
ondin
g
y
also exi
s
t but are n
o
t n
e
ce
ssarily
uniqu
e. We can write the K
K
T conditio
n
s at the optimal point:
()
()
0
cc
c
ii
j
j
i
j
i
i
S
r
c
c
jj
yy
f
l
(5)
()
('
(
)
)
0
c
cc
S
r
c
c
fU
f
(6)
Hen
c
e i
n
tuitively we
can
relate
c
i
to
c
i
q
, th
e numb
e
r
of packet
s
that
are d
e
stin
ed
to
destin
a
tion
of flo
w
c
. As a
co
nsequ
en
ce of KKT,
using
som
e
el
e
m
entary
alge
bra
on
e
can
derive:
(,
)
a
r
g
m
ax
m
a
x
m
ax
(
)
cc
ij
i
i
j
RR
ci
j
L
i
RR
p
(7)
3.2. 802.11-compatible
Scheduling
It can be f
ound th
at the optimal
scheduli
ng rule
(7) i
s
a
n
NP-h
ard
ce
n
t
ralize
d
optimizatio
n
probl
em. It sh
ould con
s
ide
r
a more
r
eali
s
tic,
subo
ptim
al
sched
uling pro
c
e
ss and we
will show how our algorithm
can be a
ppli
ed as a di
stri
buted heuri
s
tic.
A
back-pre
ssure betwe
en node
s
i
and
j
is defined as
cc
c
ij
i
j
zq
q
,
i
can
se
nd p
a
cket
s
to
j
only whe
n
0
c
ij
z
.We call a se
t of feasible a
c
tivation profiles
S
802.11
-compatible if f
o
r al
l
SS
and for all
11
(,
)
iJ
S
, there i
s
no
22
(,
)
iJ
S
such t
hat
1,
2
0
ii
p
, or
1,
0
ij
p
and
2,
0
ij
p
in
whi
c
h
12
jJ
J
. Furthermore,
we
will assume that t
he underlying scheduli
ng process
is not
unde
r ou
r co
ntrol. We
can
simplify the sche
dule to th
e Eq (8).
(,
)
(
)
()
a
r
g
m
a
x
m
a
x
cc
ji
cc
c
i
ij
ij
ij
L
d
d
ct
d
z
p
(8)
Whe
r
e
z
ij
>
0, and Multipli
e
r
c
i
d
is used to p
r
event the
sh
orte
r flo
w
fro
m
occupyin
g
more
resou
r
ces. Condition
cc
ji
dd
is u
s
ed to
allevia
t
e the sid
e
-e
f
f
ect of extensive exploratio
n.
c
i
d
is
update
d
as
(,
)
1
mi
n
(
)
cc
ij
ij
L
ij
dd
p
.We can get
ij
p
throu
gh stati
s
tics.
Flow control: The optimal flow rate at th
e sou
r
ce
()
c
f
t
ca
n be cal
c
ulat
ed throu
gh u
s
ing
a primal
-du
a
l approa
ch a
s
in the pape
r [8]:
,
()
1[
]
(
(
[
]
[
]
)
M
cc
c
c
fs
r
c
c
m
f
t
ft
K
U
ft
q
t
(9)
Whe
r
e the
n
o
tation
b
a
x
proje
c
ts the val
ue
of
x
to the clo
s
e
s
t point in t
he interval [a
,b].
We a
s
sume t
hat
m
is a fixed po
sitive valued q
uantit
y that can be
arbitra
r
ily sm
all, and
M
is at
Evaluation Warning : The document was created with Spire.PDF for Python.
TELKOM
NIKA
ISSN:
1693-6
930
The Im
plem
e
n
tation of On
e Oppo
rtuni
stic
Ro
uting in
Wirel
e
ss Network (Li Ha
n)
463
least t
w
o tim
e
s of th
e ma
x link rate
.
2
1
K
,
()
()
c
sr
c
c
qt
is th
e nu
m
ber
of pa
cket
s qu
eue
d for
destin
a
tion of
flow
c
on sou
r
ce no
de of flow
c
.
4. Practical Issues
In this
se
ctio
n we con
s
ide
r
some
practi
cal i
s
sue
s
th
at co
ncern
i
m
pleme
n
tatio
n
of the
Algorithm p
r
o
posed in Sect
ion 3. Table 1
defi
nes the t
e
rm
s used in
the rest of the
paper.
Table 1. Defi
nitions u
s
e
d
in the pape
r
Term
Definition
Native Packet
Uncoded packet
Coded Packet
Random linear c
o
mbination of nat
ive or coded packets
Innovative
Packet
A packet is inno
vative to a node if
it is
linearly
in
dependent f
r
om
its previously
rec
e
ived
packets
Do
w
n
stream No
de
Let
c
i
d
be the
distance to destinatio
n of flo
w
c
; the v
a
lue of
c
i
d
is defined as ETX m
e
tric
of the best path f
r
om
i
to the destination of flow
c
. We
say
j
is dow
n
s
tream node of
i
, if
(,
)
ij
L
and
cc
ij
dd
.
Sending threshold :
thresh
Onl
y
when fo
r
w
a
r
ders accept at l
east
thred
n
a
tive packets of a ge
neration, it can r
e
la
y
re
-
encoded packets of the gene
ratio
n
.
4.1. Net
w
o
r
k
Coding
Previou
s
re
sults assu
me that gene
ratio
n
size
u
s
ed f
o
r net
work
coding ten
d
s t
o
infinity.
Practi
cal re
a
s
on
s, su
ch a
s
co
mplexity and pe
rform
a
nce of de
co
di
ng, and he
ad
er overhea
d for
storin
g the co
efficient vecto
r
, requi
re u
s
to limit the size of the head
er.
With
ran
dom
linear
code
s,
data to
be
di
sseminate
d
i
s
divid
ed i
n
to
l
pa
ck
e
t
s
12
,.
.
.
l
bb
b
,
whe
r
e ea
ch b
l
ock
i
b
has a fix
ed n
u
mbe
r
of bytes
h
(referred to
as the
packet
si
ze).
In ord
e
r to
cod
e
a
n
e
w coded
pa
ckets
j
X
in
network
coding,
a
network n
ode
sho
u
ld first in
dep
ende
ntly an
d
rand
omly cho
o
se
a set of coding
co
effici
ents
12
,.
.
.
j
jj
l
cc
c
in GF(2
8
), one fo
r ea
ch
re
ceived p
a
cket
(or
ea
ch o
r
igi
nal pa
cket on
the data
sou
r
ce
). It then p
r
odu
ce
s o
ne
cod
ed blo
c
k
j
X
of
h
bytes:
1
l
j
ji
i
i
X
cb
. Note that a linear
combi
n
ation of code
d pac
kets i
s
also a linea
r
combi
nation
of the
corre
s
p
ondin
g
native packets.
Since e
a
ch
cod
ed p
a
cke
t
is a linea
r combi
nation
of the native pa
ckets, it can
be
uniqu
ely iden
tified by the
set of
co
efficients th
at ap
peared i
n
th
e line
a
r
co
m
b
ination. A
p
eer
decode
s a
s
soo
n
a
s
it
has
re
ceived
l
linea
rly in
depe
ndent
coded
blo
c
ks
12
,.
.
.
l
X
XX
, let
1
,
...
l
XX
X
. It
firs
t forms a
ll
matrix
C
, using the
co
efficients of e
a
ch bl
ock
i
X
. E
a
c
h
row
in
C
is
co
rrespond
with the
coeffici
ents o
f
one coded
b
l
ock. It then recove
rs th
e o
r
iginal
blo
ck
b
,
12
,,
.
.
l
bb
b
b
as
1
T
bC
X
. It should
be noted tha
t
a network n
ode do
es not
have to wait for all
l
linea
rly ind
e
pend
ent
code
d blo
c
ks befo
r
e d
e
codin
g
a
gen
eratio
n. In fact, it
can
start to
de
cod
e
as
so
on
as t
he first
cod
e
d
blo
c
k i
s
re
ceived, an
d th
en p
r
og
re
ssively de
cod
e
s
each of th
e
n
e
w
coded bl
ocks, as they are rece
ived through the net
work. In this
process, the decoding time
overlap
s
with
the time required to re
cei
v
e the or
igin
al block, and
thus hidde
n from the tally of
overhe
ad
ca
use
d
by
en
coding
an
d d
e
co
ding
time
s. We use Gau
s
s-Jorda
n
elimi
nation
to
impleme
n
t such
a progre
ssive
de
codi
ng proces
s rather tha
n
th
e more tradit
i
onal Ga
ussi
an
elimination, which i
s
also u
s
ed a
s
an eff
e
ctive metho
d
of innovative packet jud
g
m
ents.
4.2. Stoppin
g
Rule
In our p
r
oto
c
ol traffic is pu
mped into th
e netwo
rk by the sou
r
ce. The forwa
r
de
rs d
o
not
gene
rate traf
fic unle
ss th
ey receive
th
r
e
s
h
+1 inn
o
v
ative packets of a gene
ration. A source
flushe
s o
u
t
a gen
eration
whe
n
it a
c
cept
s AC
K f
r
om
destin
a
tion that it h
a
s
decode
d
the
gene
ration. T
he forwarders stop tran
smit
ting packet
s
fr
om a pa
rticul
ar gen
eration
in four ca
se
s:
Evaluation Warning : The document was created with Spire.PDF for Python.
ISSN: 16
93-6
930
TELKOM
NIKA
Vol. 13, No. 2, June 20
15 : 460 – 46
8
464
(a) O
n
c
e
t
h
e
sou
r
c
e
st
op
s doin
g
so.
(b)
T
he do
wnstre
am no
d
e
s of it have
got all
packet
s
of the gen
eratio
n.
Eventually the generation will be
ti
meout and b
e
flushe
d fro
m
memory. (c)
Additionally, forwarder
s th
at hear the A
C
K while it is being tra
n
smitted toward
s the
sen
der imm
e
diately stop transmitting packet
s
fr
om
that genera
t
ion and pu
rge it from their
memory.
(d)F
inally, the arri
val of a pa
cket of a ne
w
g
eneration
will
cau
s
e
a fo
rwarde
r to flu
s
h
all
buffered p
a
ckets with ge
ne
ration IDs whi
c
h is lo
we
r than the active
gene
ration.
In simul
a
tion
s, we fin
d
th
e timeout p
e
r
iod of
a ge
neratio
n on
sou
r
ce no
de
impa
ct
perfo
rman
ce
signifi
cantly. We use an algorith
m
si
milar to
T
C
P
protocol o
n
ea
ch
source to
comp
ute an
d
manag
e time
out timer. Ho
wever,
we
do
not co
mpute
timeout timer
for ea
ch
pa
cket
but for ea
ch g
eneration. We can
cal
c
ulat
e the timeout perio
d
RT
O
like this:
(
1
)
,
0.12
5
s
S
Sample
RTT
R
T
T
R
T
T
a
(10)
(
1
)
,
0.
25
D
D
S
Sam
p
l
e
S
R
T
T
R
TT
R
T
T
R
TT
R
T
T
(11)
4
SD
RTO
R
T
T
RTT
(12)
RTT
Sam
p
le
is curre
n
tly
measu
r
ed
RTT
,
whi
c
h is
defi
ned a
s
the p
e
riod from th
e sou
r
ce
sending the
first packet
of a
generat
i
on till it acc
epting ACK
of the generation from
its
destin
a
tion. Whe
r
e
RTT
S
is the smo
o
t
hed
RTT
of
a gene
ration;
RTT
D
is the
smooth
ed
RTT
deviation. When a g
ene
ra
tion is timeo
u
t
on a so
ur
ce
, it will be flushe
d from th
e memo
ry, and
next generation sh
ould b
e
sent.
In ord
e
r to
si
mplify the im
plementatio
n
and
re
d
u
ci
ng
co
ntrol overhead, we assume
o
n
ly
one
gen
erati
on i
s
tran
smi
tted for a flo
w
at
on
ce.
O
n
ly gen
erations
having
go
t at
least
thred
+1
innovative pa
ckets an
d not
meeti
ng sto
pping rule
s, it can comp
ete for sche
duli
ng ch
an
ce wi
th
Eq (8). We ca
ll the resultin
g gene
ration,
if it exists, scheduli
ng gen
eration.
4.3 Con
t
rol Flo
w
Figure 1 sho
w
s the a
r
chitecture of our prot
ocol. The control flow re
spo
n
d
s
to packe
t
reception a
n
d
transmissio
n oppo
rtunity signal
ed
by
the 802.11
driver. On th
e sen
d
ing
si
de,
whe
never th
e
MAC sig
nal
s has a
n
opp
o
r
tunity to
tran
smit, the nod
e sele
cts
a b
a
cklog
ged flo
w
as
mention
e
d
in
se
ction
3.2 an
d p
u
sh
es it
s p
r
e
-
co
ded
pa
cket to the
network inte
rfa
c
e. If the
node i
s
a
sou
r
ce, it shoul
d
update it
s flow rate
and
qu
eue len
g
th a
c
cording to Eq
.(9) first, and
at
the same tim
e
it should check whethe
r current
gen
eration i
s
timeout. On the
receivin
g si
de,
whe
n
a pa
cket is arrivin
g
, the node
che
c
ks if t
he gen
eration ID i
n
the pa
cket is highe
r than t
h
e
node’
s
cu
rre
n
t gen
eration
,
the n
ode
sets
cu
rre
nt
generation to the more rece
nt generation
ID
and flushe
s p
a
ckets of old
e
r gen
eration
s
from it
s g
e
neratio
n buffer. If the generation I
D
on
the
packet i
s
the
same
a
s
its
current ge
ne
ra
tion,
the no
de
perfo
rm
s a li
near inde
pen
den
ce
che
c
k
to
determi
ne
whether the
p
a
cket i
s
in
no
vative. I
nnovative pa
ckets are
ad
ded
to the
gen
era
t
ion
buffer
whil
e n
on-in
novative
pa
cket
s are
discarded.
If the p
a
cket
wa
s tran
smitted
from
upst
r
ea
m,
the node
will increa
se
s its queu
e length
by one.
Furthe
r proce
ssi
ng dep
end
s on wh
ethe
r the node
is the final desti
nation of packets. If
the no
de i
s
t
he d
e
stinatio
n of the flo
w
,
it ch
ecks
wh
ether it
ha
s receive
d
a full
gen
eratio
n (i
.e.,
l
native packet
s
). If so, it queue
s an A
C
K for the
g
eneration. ACK pa
cket
s
are routed to
the
sou
r
ce al
ong
the
sho
r
te
st ETX path. I
n
ad
diti
on, al
l nod
es that
over
he
ar a
g
eneration A
C
K
update thei
r curre
n
t gene
ration variabl
e
and flush p
a
ckets of the
acked ge
neration from th
eir
gene
ration b
u
ffer.
Evaluation Warning : The document was created with Spire.PDF for Python.
TELKOM
NIKA
ISSN:
1693-6
930
The Im
plem
e
n
tation of On
e Oppo
rtuni
stic
Ro
uting in
Wirel
e
ss Network (Li Ha
n)
465
Figure 1. A flow chart of
o
u
r protocol implementatio
n
5. Simulation Resul
t
s
We
com
pare
d
ou
r alg
o
rith
m with a
sh
ortest-
pat
h, sin
g
le path
ro
uting alg
o
rithm,
and
with
the MO
RE al
gorithm. In
o
r
de
r to m
a
ke
the
comp
ari
s
on
fair, we assume
that the
si
ngle
-
pa
th
routing
algo
rit
h
m u
s
ed th
e
same
ki
nd of
jointly-optimal
routin
g an
d f
l
ow-co
n
trol
a
ppro
a
ch in
o
u
r
scheme. In
contra
st, MO
RE doe
s not i
n
tegrate flo
w
control or
flo
w
sched
uling
with
the routi
n
g
algorith
m
. In the simulatio
n
of the MORE algo
ri
thm
s
, we a
s
sum
e
that each
source ha
d a large
backlo
g
of pa
ckets to tran
sm
it, and that
each relay pe
rforme
d FIFO
sched
uling
a
m
ong
pa
ckets
from diffe
rent
flows. Alg
o
rithms
assig
n
the same
si
ze of
buffer
o
n
ea
ch
no
de.
We
n
a
me th
e
singl
e path protocol
with SinglePro and
our al
g
o
rithm
with MulPro i
n
this se
ction.
We devel
ope
d a discrete-event simulat
o
r that
imple
m
ents the three routin
g, flow an
d
rate co
ntrol al
gorithm
s.
In
t
he simulatio
n
s
,
the
foll
owi
n
g settings a
r
e
ado
pted:
(a)
The
Di
stribut
ed
Coordination Function
(DCF) of
IEEE 802.11 for
wirel
e
ss
LANs i
s
used as the MA
C layer
proto
c
ol
s. (b
) 40 no
de
s; Packet d
r
op
probability aver
age
s is
0.2 o
n
ea
ch lin
k; L
i
nk b
and
widt
h is
4Mbp
s; Packet size is 1
0
00 Bytes. (c) Pa
ramete
rs
use
d
in Eq(9
) are
define
d
as
K
=256,
m
=
0.05,
M
= 2.5.
We u
s
e
()
l
o
g
(
)
cc
Uf
f
, hence the
rate
allocation tha
t
maximizes
Eq (4) i
s
the
prop
ortio
nally fair rate allo
cation.
We l
o
o
k
ed
at
four
pe
rform
ance met
r
ics.
(a
) Total
utili
ty
()
c
c
Uf
: Alloc
a
tion
f'
is
better
than
f
if
,
()
(
)
cc
cc
Uf
Uf
is po
sitive. The proportio
nal fai
r
rate m
a
ximize
s the opti
m
izati
o
n
probl
em
(4)
hen
ce h
a
s th
e high
est
utility. (b)Rat
e:Average
rate
o
f
one flo
w
. (c) Cost: Avera
g
e
numbe
r of
packet
s
tran
smitted by
node
s in
ne
twork for
ea
ch p
a
cket receive
d
by
the
destin
a
tion
s.
(d) Delivery
ratio: the
rati
o bet
wee
n
t
he n
u
mbe
r
o
f
valid pa
cke
t
s a
c
cepted
b
y
destin
a
tion
s and the num
b
e
r of pa
cket
s
transmitted from uppe
r lay
e
r on sou
r
ce.
Evaluation Warning : The document was created with Spire.PDF for Python.
ISSN: 16
93-6
930
TELKOM
NIKA
Vol. 13, No. 2, June 20
15 : 460 – 46
8
466
Figure 2. Performa
nce with
various g
ene
ration si
ze
l
in
a network wit
h
averag
e 10
neigh
bors an
d 8 rando
mly sele
cted flows
We first di
scuss the i
n
flue
nce
of ge
ne
ration
size
l
.
Figure 2 ill
ustrates
pe
rformance of
MulPro a
nd
MORE
with variou
s ge
ne
ration
size
l
, where
thred
equal
s
1
l
. We can
see
all
perfo
rman
ce
metrics are
i
n
crea
sed
co
mpared
to
M
O
RE.
We
fo
und th
at g
e
n
e
ration
size
has
signifi
cant im
pact on the
perfo
rman
ce
of MulP
ro, but that’s no
t the case for MO
RE. The
negative influ
ence of larg
e
size
gene
rati
on in MulP
ro is ca
used by
the timeout m
e
ch
ani
sm u
s
ed
in sou
r
ce nod
es, whi
c
h ne
eds qui
ck de
codi
ng on de
stination
s
. Th
is feature
can
help us re
du
ce
the overhe
ad
of network
co
ding.
Figure 3. End-to-e
nd rate a
llocatio
n
exa
m
ple:
eight flows amon
g r
andomly sele
cted source
-
destin
a
tion p
a
irs o
n
one n
e
twork with a
v
erage 1
5
nei
ghbo
rs fo
r ea
ch no
de. Small bars den
ote
rates
per flow.(
l
= 4,
thred
= 3 )
Figure 3
illu
strates the
opt
imal rate
allo
cation
s
obtai
ned th
ro
ugh
our alg
o
rithm
,
Whe
r
e
()
4
5
Mulpro
c
c
Uf
,
()
3
6
MO
R
E
c
c
Uf
,
Pr
()
4
0
Single
o
c
c
Uf
. In this
c
a
s
e
, we
c
a
n s
ee that both
utility
and
th
rough
out will be increa
sed
if we use
utility maximization. We ca
n see that MO
RE
behave
s
worse than the
si
ngle-path rou
t
i
ng whe
n
the
r
e are multipl
e
flows.
Evaluation Warning : The document was created with Spire.PDF for Python.
TELKOM
NIKA
ISSN:
1693-6
930
The Im
plem
e
n
tation of On
e Oppo
rtuni
stic
Ro
uting in
Wirel
e
ss Network (Li Ha
n)
467
Figure 4. Cu
mulative perf
o
rma
n
ce improvement of
our algo
rithm o
v
er SinglePro
with variou
s
numbe
r of nei
ghbo
rs
The curve "Percent_utility" is
t
he percentage of
runs, i
n
whi
c
h
Pr
Pr
()
(
)
0
M
u
l
o
Single
o
cc
c
c
cc
Uf
Uf
. And the cu
rve " Percen
t_rate"
is p
e
rcenta
ge of flows that
sat
i
sf
y
Pr
Pr
1
Mu
l
o
c
Si
ng
le
o
c
rate
rate
We th
en
ma
ke th
e p
r
evi
ous expe
rim
ents
with
30
ra
ndom
traf
fic matri
c
e
s
for e
a
ch
netwo
rk with
variou
s
num
bers of
neig
hbors, a
nd
compa
r
e M
u
lp
ro to Si
ngleP
ro
with the
two
performance
metrics which is illust
rated
in Figure 4. We can see
Singlepro performs better
with
less nu
mbe
r
of neigh
bo
rs,
for MulP
ro
can
not ta
ke
advantag
e
of multiple p
a
ths in
a
sp
arse
network.
When the
num
ber of nei
ghbor
s is
between 6 to
18,
it
is
observed that network utility of
Mulpro win
s
in about 85%
runs a
nd through
put win
s
in about 70%
flows.
We no
w loo
k
at the influen
ce of the numbe
r of flows, with t
he simul
a
tio
n
results
illustrate
d in figure 5. We can
see fro
m
figure 5(
a) that the rate allocation obt
ained by Mul
P
ro
alway
s
maxi
mize
s the
util
ity with the
a
v
erage
de
live
r
y ratio
over
90%. Fig
u
re
5(c) sho
w
s that
the in
cre
a
si
n
g
num
be
r of f
l
ows h
a
s little
neg
ative effe
ct on
the
co
st
of MulPro, b
u
t that’s
not true
for SinglePro.
Figure 5. Performa
nce improvement
of our algo
rithm o
v
er SinglePro
with variou
s numbe
r of
flows in a 8
-
n
e
ighb
or-network
6. Conclusio
n
s
This pa
pe
r prop
oses a
n
optimization
fr
amework addre
s
sing
fairness i
s
sue
s
for
oppo
rtunity routing in wire
less mesh ne
tworks. Im
pli
c
it in our app
roa
c
h is the
usin
g of network
Evaluation Warning : The document was created with Spire.PDF for Python.
ISSN: 16
93-6
930
TELKOM
NIKA
Vol. 13, No. 2, June 20
15 : 460 – 46
8
468
codi
ng,
whi
c
h hel
p u
s
to
solve th
e
rou
t
ing proble
m
. We
get
a
distribute
d
h
e
u
r
istic alg
o
rith
m in
the case whe
n
sch
edulin
g
is d
e
termin
ed
by MAC,
whi
c
h i
s
especi
al
ly well-suited
for multimedi
a
appli
c
ation
s
with low-lo
ss, low-late
ncy
con
s
trai
nts
su
ch a
s
au
d
i
o/video stre
aming. Th
ro
ugh
simulatio
n
s,
we have sho
w
n ou
r app
roach signi
fi
cantly outperf
o
rm
s si
ngl
e-path routin
g and
MORE i
n
m
o
st situ
ation
s
. We
al
so
in
spect th
e
influ
ence of
different
network co
ndition
s
with
experim
ents.
The p
e
rfo
r
ma
nce
of a
ppli
c
ations that
ru
n on
the to
p
of our
system
is
an i
n
tere
st
ing
open p
r
obl
em
.
Conflict of Interests
The autho
rs decl
a
re that there i
s
no co
nflict of
intere
sts rega
rdin
g the publi
c
atio
n of this
article.
Referen
ces
[1]
T
Ho, H Vis
w
anath
an.
Dyn
a
m
ic a
l
g
o
rith
ms
for multic
ast w
i
th intra-sess
ion n
e
tw
ork codi
ng.
43r
d
Allerto
n
Ann
ual
Confere
n
ce o
n
Commu
ni
cati
on, Contro
l, an
d Comp
uting. 2
005.
[2]
Eny
a
n S, C
hua
ny
un
W. A Su
rvey
on
Mu
l
t
i-p
a
t
h
R
outi
ng
Protocols
in
W
i
reless
Multim
edi
a Se
nso
r
Net
w
orks.
T
E
L
K
OMNIKA Indones
ian J
ourn
a
l of Electrica
l
Engi
neer
in
g
. 2014; 12(
9): 697
8-69
83.
[3]
B Radu
nov
ic, C Gkantsidis,
P Ke
y
,
S Ghe
o
rgi
u
, W
Hu,
P Rodri
guez.
Multip
ath cod
e
casting for
w
i
reless mesh
net
w
o
rks.
MSR-T
R
-200
7-6
8
. 2007.
[4]
Z
hao W
,
T
ang
Z
.
Net
w
ork
C
odi
ng
bas
ed
R
e
lia
bl
e Mu
lti-p
a
th R
outi
ng
in
W
i
reless
Se
n
s
or N
e
t
w
ork.
T
E
LKOMNIKA Indon
esi
an Jou
r
nal of Electric
al Eng
i
ne
eri
n
g
.
2013; 1
1
(12):
775
4-77
61.
[5]
R Ahls
w
e
de, N
Cai, SR Li, RW
Yeung. Net
w
o
r
k informati
on flo
w
.
IEEE Transactions on Inform
ation
T
heory
. 200
0.
[6]
S Ch
achu
lski,
M Jen
n
in
gs, S
Katti, D K
a
ta
bi. MORE: A
net
w
o
rk
cod
i
n
g
a
ppro
a
ch
to
op
portu
nisti
c
routin
g.
MIT
-
C
SAIL-T
R
-200
6-
049
. 20
06.
[7]
Baol
in S,
Yin
g
S, Ch
ao
G, T
i
ng Z
.
Performance
of N
e
t
w
o
r
k C
o
d
i
ng
Based
Multi
p
a
t
h Ro
uting
i
n
W
i
reless Se
ns
or Net
w
orks
. IJCSI Internatio
n
a
l Jour
nal of C
o
mputer Sci
e
n
c
e Issues
. 201
2; 9(6).
[8]
Er
y
i
lmaz, R Sr
ikant. Joi
n
t co
ngesti
on co
ntrol, routi
ng a
n
d
mac for stabil
i
t
y
a
nd fair
nes
s in
w
i
r
e
les
s
net
w
o
rks. I
EEE Journal on S
e
lected Ar
eas in Comm
unications.
200
6; 24(
8): 1514-
15
24.
Evaluation Warning : The document was created with Spire.PDF for Python.