Inter
national
J
our
nal
of
Electrical
and
Computer
Engineering
(IJECE)
V
ol.
6,
No.
6,
December
2016,
pp.
3205
–
3216
ISSN:
2088-8708
3205
Fibonary
Spray
and
W
ait
Routing
in
Delay
T
olerant
Netw
orks
Priyanka
Das
1
,
Pr
osenjit
Cho
wdhury
2
,
Bikash
P
oudel
3
,
and
T
anmay
De
4
1
Department
of
Computer
Science
&
Engineering,
NSHM
Kno
wledge
Campus
Dur
g
apur
,
India
2
Softw
are
Engineer
,
o9
Solutions,
Bang
alore,
India.
3
Softw
are
Engineer
,
Meru
Netw
orks,
India
4
Department
of
Computer
Science
&
Engineering,
National
Institute
of
T
echnology
Dur
g
apur
,
India
Article
Inf
o
Article
history:
Recei
v
ed
Mar
2,
2016
Re
vised
Aug
18,
2016
Accepted
Sep
5,
2016
K
eyw
ord:
Delay
T
olerant
Netw
ork
(DTN)
fibonary
latenc
y
deli
v
ery
ratio
ABSTRA
CT
Although
there
has
been
a
tremendous
rise
in
places
being
connected
through
the
In-
ternet
or
an
y
other
netw
ork
protocol,
there
still
lie
areas,
which
remain
out
of
reach
due
to
v
arious
reasons.
F
or
all
such
places
the
ans
wer
is
a
Delay
T
olerant
Netw
ork
(DTN).
A
DTN
is
such
a
netw
ork
where
there
is
no
fix
ed
or
predefined
route
for
messages
and
no
such
guarantee
whats
oe
v
er
of
all
messages
being
correctly
routed.
DTN
can
be
considered
as
a
superset
of
netw
orks
wherein
other
netw
orks
such
as
adhoc,
mo-
bile,
v
ehicular
etc.
form
the
subset.
Therefore
routing
in
DTN
is
a
v
ery
chanc
y
af
f
air
where
one
has
to
maximize
on
the
present
netw
ork
scenarios
to
get
an
y
fruitful
result
other
than
depending
on
past
information.
Also
protocols
here
need
to
be
less
com-
ple
x
and
not
increase
the
already
high
nodal
o
v
erhead.
In
this
paper
we
propose
a
ne
w
approach,
the
Fibonary
Spray
and
W
ait,
which
does
e
xactly
this.
It
forw
ards
copies
of
a
message
in
a
modified
Binary
Spray
and
W
ait
manner
so
that
it
performs
well
e
v
en
in
non
independent
and
identically
distrib
uted
node
structure.
W
e
ha
v
e
supported
our
statements
with
mathematical
as
well
as
simulation
analysis.
Copyright
c
2016
Institute
of
Advanced
Engineering
and
Science
.
All
rights
r
eserved.
Corresponding
A
uthor:
Name
Priyanka
Das
Af
filiation
NSHM
Kno
wledge
Campus
Dur
g
apur
Address
Behind
Clinic,
Samdi
Road,
P
.O.
Rupnarayanpur
Bazaar
,
W
est
Beng
al-713386,
India
Phone
+91
8900596423
Email
priyanka.das.2206@gmail.com
1.
INTR
ODUCTION
The
idea
for
a
Delay
T
olerant
Netw
ork
to
e
xist,
e
v
olv
ed
while
conceptualizing
the
InterPla
Netary
(IPN)
Internet
project
(1).
The
project’
s
aim
w
as
t
o
establish
an
ef
ficient
means
of
communication
between
planets
and
satellites
k
eeping
in
mind
their
enormous
dif
ference
in
distance
as
well
as
una
v
ailability
of
message
routers
(usually
satellites)
at
all
times.
Hence
the
concept
(and
a
need)
for
a
ne
w
netw
ork
emer
ged
wherein
messages
w
ould
be
passed
around
the
netw
ork
based
on
scheduled
contacts
(as
satellite
contact
periods
are
usually
fix
ed).
On
further
research,
it
w
as
seen
that
not
only
interplanetary
b
ut
man
y
ne
w
terrestrial
netw
orks
too
needed
something
more
than
what
w
as
pro
vided
by
the
TCP/IP
.
The
TCP/IP
w
orks
on
some
assumptions
(2)
which
are
lik
e
inability
to
support
long
link
delay
,
Necessity
of
end-to-end
routing
paths,
data
pack
ets
ha
v
e
lo
w
time-to-li
v
e
etc.
Abiding
by
these
strict
prerequisites
is
not
feasible
for
some
ne
w
netw
orks
lik
e
T
errestrial
ci
vilian
netw
orks
(connecting
mobile
wireless
de
vices,
including
personal
communicators,
intelligent
high-
w
ays,
and
remote
Earth
outposts),
W
ireless
Military
Ad-Hoc
battlefield
netw
orks
(connecting
troops,
aircraft
and
satellites),
Sensor
Netw
orks
(both
on
land
and
in
w
ater),
W
ar
torn
or
Disas
ter
struck
areas
(lik
e
a
place
hit
by
some
natural
calamity
whose
connection
with
the
outs
ide
w
orld
has
disrupted
resulting
into
a
netw
ork
par
-
tition)
etc.
These
netw
orks
on
the
other
hand
are
characterised
by
Intermittent
connecti
vity
,
Po
wer
limitations,
Netw
ork
partitions,
Arbitrarily
long
periods
of
link
disconnection,
High
error
rates
and
l
ar
ge
bidirectional
data-
J
ournal
Homepage:
http://iaesjournal.com/online/inde
x.php/IJECE
,
DOI:
10.11591/ijece.v6i6.10361
Evaluation Warning : The document was created with Spire.PDF for Python.
3206
ISSN:
2088-8708
rate
asymmetries.
The
answer
to
all
these
is
the
Delay
T
olerant
Netw
ork
(DTN)
(1).
A
DTN
is
an
o
v
erlay
on
top
of
re
gional
netw
orks,
including
the
Internet.
DTNs
support
interoperability
of
re
gional
netw
orks
by
han-
dling
enormous
propag
ation
delays
between
and
within
re
gional
netw
orks,
and
by
translating
between
re
gional
netw
ork
communication
characteristics.
In
pro
viding
these
functions,
DTNs
accommodate
the
mobility
and
limited
po
wer
of
e
v
olving
wireless
communication
de
vices
and
co
v
er
up
for
their
incon
v
eniences.
T
o
accom-
modate
these
features
onto
the
e
xisting
TCP/IP
layer
,
DTN
adds
the
Bundle
layer
which
most
importantly
does
persistent
storage.
It
is
an
additional
layer
on
top
of
the
transport
layer
where
the
‘delay
is
tolerated’.
Actually
it
is
the
layer
in
between
the
application
layer
and
heterogeneous
re
gion
specific
lo
wer
layers
which
will
act
as
a
bridge
between
incompatible
netw
orks.
F
or
routing
messages
in
such
scenarios
message
replication
seems
the
solution,
b
ut
we
need
to
k
eep
in
mi
nd
the
v
arious
netw
ork
limitations
of
DTN
lik
e
ener
gy
,
cost
and
lo
w
bandwidth.
More
replication
means
increasing
all
these
f
actors
and
hence
pure
replication
w
ould
not
gi
v
e
a
desirable
result
here.
Thus
we
need
to
w
ork
on
mechanisms
which
can
pro
vide
a
netw
ork
with
a
balanced
solution
without
testing
its
limitations
too
se
v
erely
.
In
this
paper
we
first
look
into
some
related
w
ork
in
the
routing
domain.
W
e
then
state
our
mot
i
v
ation
for
conceptualising
a
ne
w
scheme
for
DTN.
Ne
xt
we
put
forw
ard
our
proposed
approach
and
then
pro
v
e
its
soundness
by
a
mathematical
analysis.
Ne
xt
we
elucidate
the
simulator
we
ha
v
e
used
for
our
simulation
pur
-
pose.
Then
we
compar
e
our
algorithm
to
pre
vious
other
algorithms
sho
wing
results
with
dif
ferent
parameters.
Lastly
we
dra
w
the
conclusion.
1.1.
Pr
e
vious
W
ork
Routing
protocols
in
DTN
can
be
broadly
classified
into
tw
o
groups
on
the
nature
of
their
strate
gy
chosen
to
forw
ard
a
messa
g
e
.
This
strate
gy
itself
can
be
either
replication
based
(which
relies
on
more
number
of
copies
to
increase
the
chances
of
a
message
being
deli
v
ered)
or
kno
wledge
based
(which
uses
netw
ork
in-
formation
to
route
data).
Based
on
these
strate
gies
the
classification
are
namely
,
flooding
based
and
forw
arding
based
routing.
In
flooding
based
protocols,
a
node
mak
es
numerous
copies
(or
replicas)
of
a
single
message
in
an
attempt
to
increase
the
chance
of
it
being
deli
v
ered.
One
such
popular
routing
protocol
(and
also
one
of
the
earliest
protocol
for
routing
in
DTN)
is
the
Epidemic
routing
(3)
which
w
as
originally
proposed
for
v
ehicular
netw
orks
(4;
5).
Epidemic
routing
simply
replicates
messages
from
one
node
to
another
as
and
when
a
connection
is
established
between
them.
In
this
w
ay
the
chances
of
message
deli
v
ery
increases
b
ut
a
lot
of
netw
ork
resources
(lik
e
bandwidth,
b
uf
fer
storage,
ener
gy
and
cost)
are
w
asted
in
return.
An
impro
v
ement
on
this
protoc
o
l
is
the
Credit
Based
strate
gies
(6;
7)
which
assign
a
credit
v
alue
to
e
v
ery
node
connected
on
their
time
of
connection
and
gi
v
es
them
the
po
wer
to
replicate
based
on
that
credit.
These
strate
gies
greatl
y
reduce
number
of
replicas.
Another
protocol
in
this
f
amily
is
the
Spray
&
W
ait
(8).
Spray
&
W
ait
is
composed
of
tw
o
phases.
The
first
phase
is
kno
wn
as
the
Spray
phase
in
which
the
source
of
the
message
sprays
one
cop
y
to
L
(predefined)
distinct
nodes.
After
a
node
recei
v
es
the
cop
y
it
enters
the
w
ait
phase
(the
second
phase)
where
it
holds
the
message
until
it
meets
its
destination
directly
.
Spray
&
W
ait
has
a
v
ariant
kno
wn
as
Binary
Spray
&
W
ait
(8)
in
which
a
node
tha
t
has
n
>
1
message
copies
(source
or
relay),
and
encounters
another
node
B
(with
no
copies),
hands
o
v
er
to
B
ceil
[
n=
2]
copies
and
k
eeps
f
l
oor
[
n=
2]
copies
for
itself;
when
it
is
left
with
only
one
cop
y
,
it
switches
to
direct
transmission.
Spray
and
focus
(9)
has
the
same
1
st
phase
as
Spray
and
W
ait
(8).
In
its
2
nd
phase
a
node
forw
ards
the
message
based
on
an
utility
criteria.
MaxProp
(10)
maintains
an
ordered-
queue
based
on
the
destination
of
each
message,
ordered
by
the
estimated
lik
elihood
of
a
future
transiti
v
e
path
to
that
destination.
PRoPHET
(11)
too
uses
pre
vious
performance
records
of
nodes
and
routes
data
based
on
its
findings.
Incenti
v
e
a
w
are
routing
(12)
uses
the
pair
-wise
tit-for
-tat
(TFT)
mechanism
for
routing.
The
Optimal
Probabilistic
F
orw
arding
Protocol
(13),
uses
an
optimal
probabilistic
forw
arding
metric
deri
v
ed
by
modeling
each
forw
arding
as
an
optimal
stopping
rule
problem.
The
performance
of
these
methods
may
deteriorate
when
the
netw
ork
beha
v
es
dif
ferently
from
what
the
y
had
anticipated
(an
usual
phenomena
in
DTNs).
The
best
method
to
combat
increase
in
numerous
replication
of
messages
is
the
forw
arding
based
routing
mechanism
of
forw
arding
a
single
cop
y
of
a
me
ssage
through
the
netw
ork
(14).
In
this
approach
a
node
will
pass
the
message
it
has
to
only
one
of
the
nodes
it
connects
t
o
according
t
o
some
m
etric
acquired
on
observing
the
netw
ork.
One
such
algorithm
is
the
Store
and
F
orw
ard
on
First
Contact
which
routes
the
message
to
the
first
node
it
connects
to
(15).
K
eeping
in
mind
the
rarity
of
an
y
node-to-node
connection
it
is
v
ery
e
vident
that
although
this
algorithm
incurs
minimum
replication
am
ong
all
algorithms,
it
is
v
ery
dubitable
that
it
will
be
able
to
deli
v
er
man
y
messages.
Another
v
ariant
of
this
is
the
Direct
Deli
v
ery
protocol
(16)
which
forw
ards
a
mes
sage
only
to
its
d
e
stination
node
directly
when
it
comes
in
contact
with
it.
This
algorithm
can
IJECE
V
ol.
6,
No.
6,
December
2016:
3205
–
3216
Evaluation Warning : The document was created with Spire.PDF for Python.
IJECE
ISSN:
2088-8708
3207
be
defined
as
de
generati
v
e
cases
of
both
Flooding
based
as
well
as
F
orw
arding
based
schemes.
It
has
the
least
o
v
erhead
of
all
b
ut
suf
fers
greatly
in
deli
v
ery
and
delay
performances
due
to
ob
vious
reasons.
There
are
man
y
protocols
belonging
to
this
f
amily
of
forw
arding
based
algorithms
where
the
messages
are
forw
arded
using
some
netw
ork
oracle
or
where
routing
completely
tak
es
place
according
to
some
opportunistic
or
probabilistic
metric.
Practical
routing
(17)
uses
observ
ed
information
about
the
netw
ork
for
calculating
minimum
estimated
e
xpected
delay
(MEED)
for
routing.
Conditional
shortest
path
routing
(18)
routes
messages
with
the
help
of
a
metric
called
conditional
intermeeting
time
based
on
t
he
observ
ations
about
human
mobility
traces.
These
techniques
mainly
thri
v
e
on
netw
ork
oracles
such
as
future
contact
arri
v
al
time,
last
encounter
time
etc
and
as
a
result
f
ail
to
utilize
the
opportunity
presented
by
the
present
netw
ork
configuration.
1.2.
Moti
v
ation
Finding
an
optimal
routing
algorithm
for
DTN
in
the
general
case
has
been
pro
v
ed
to
be
an
NP
hard
problem
(19).
Thus
we
can
only
focus
on
specific
scenarios
and
objecti
v
es
and
find
w
ays
to
maximise
its
performance
v
alue.
Hence
we
need
to
do
topical
optimization.
In
Binary
Spray
&
W
ait
the
source
of
a
message
initially
starts
with
n
copies;
an
y
node
A
that
has
n
>
1
message
copies
(source
or
relay),
and
encounters
another
node
B
(with
no
copies),
hands
o
v
er
to
B
ceil
[
n=
2]
copies
and
k
eeps
f
l
oor
[
n=
2]
copies
for
its
elf;
when
it
is
left
with
only
one
cop
y
,
it
switches
to
direct
transmission.
The
follo
wing
theorem
put
forw
ard
in
(8),
states
that
Binary
Spray
and
W
ait
is
optimal
in
terms
of
minimum
e
xpected
delay
,
when
node
mo
v
ement
is
IID
(Independent
and
Identically
Distrib
uted),
referring
to
IID
random
v
ariables,
i.e.
when
each
random
v
ariable
has
the
same
probability
distrib
ution
as
the
others
and
all
are
mutually
independent.
The
Theorem:
When
all
nodes
mo
v
e
in
an
IID
manner
,
Binary
Spray
&
W
ait
routing
is
optimal,
that
is,
has
the
minimum
e
xpected
delay
among
all
proposed
v
ariants
of
the
Spray
&
W
ait
routing
scheme.
The
approach
for
this
algorithm
can
be
used
in
a
more
ef
ficient
manner
for
non
IID
nodal
mo
v
ement
wherein
the
latenc
y
and
o
v
erhead
performance
can
be
impro
v
ed
upon.
It
is
not
a
frequent
occurrence
that
all
node
mo
v
ement
is
IID.
So
we
aim
for
this
impro
v
ement
and
choose
Binary
Spray
&
W
ait
algorithm
for
further
modification,
it
being
already
good
in
one
aspect
we
just
need
to
de
vise
a
w
ay
to
decrease
its
o
v
erhea
d
and
latenc
y
for
non
IID
node
mo
v
ement.
On
analysis
we
find
that
the
loophole
of
this
algorithm
in
terms
of
latenc
y
occurs
due
to
its
reaching
the
w
ait
phase
a
bit
later
(longer
tree).
It
gets
totally
dependent
on
the
initial
v
alue
of
L
.
More
the
v
alue,
more
is
the
delay
to
reach
w
ait
phase
and
hence
more
o
v
erhead.
A
high
priority
message
is
bound
to
ha
v
e
lar
ger
v
alue
of
L
b
ut
it
also
means
with
this
system
(no
matter
what),
its
w
ait
phase
will
also
get
delayed.
Its
true,
though,
that
more
replication
are
being
made,
hence
more
chances
of
message
deli
v
ery
is
being
created
b
ut
can’
t
their
be
a
w
ay
to
de
vise
a
method
wherein
this
number
of
repli
cations
are
not
reduced
b
ut
at
the
same
time
a
chance
is
created
to
reach
the
w
ait
phase
earlier
and
reduce
latenc
y
and
o
v
erhead.
Making
this
our
moti
v
ation
and
k
eeping
these
k
e
y
points
into
considerations
we
de
vise
our
ne
w
algorithm,
the
Fibonary
Spray
&
W
ait.
2.
THE
PR
OPOSED
METHOD
Our
proposed
routing
protocol
f
alls
under
the
replication
based
strate
gies
and
do
not
use
an
y
netw
ork
oracle
for
routing.
F
or
this
routi
ng
algorithm,
we
will
w
ork
with
the
f
amous
Fibonacci
sequence
in
mathemat-
ics:
0
;
1
;
1
;
2
;
3
;
5
;
8
;
13
;
21
;
34
;
55
;
89
;
144
.
By
definition,
the
first
tw
o
numbers
in
the
Fibonacci
sequence
are
0
and
1
,
and
each
subsequent
number
is
the
sum
of
the
pre
vious
tw
o.
In
mathematical
terms,
the
sequence
F
n
of
Fibonacci
numbers
is
defined
by
the
recurrence
relation:
F
n
=
F
n
1
+
F
n
2
Let
us
assume,
that
our
starting
node
had
N
copies
of
a
message
to
be
gin
with.
No
w
,
at
an
y
instant,
let
a
node
A
ha
v
e
n
(where
n
>
1
)
message
copies.
W
e
first
determine
if
n
is
a
Fibonacci
number
or
not.
So
there
are
tw
o
cases
that
may
arise:
1.
If
n
,
is
NO
T
a
Fibonacci
number:
Then
our
node
A
,
forw
ards
m
copies
to
B
(a
recipient
node
with
no
copies),
where
m
is
the
highes
t
Fibonacci
number
not
greater
than
n
.
That
is,
m
is
the
immediate
predecessor
of
n
in
the
Fibonacci
series.
As
a
result,
our
parent
node
A
,
no
w
retains
(
n
m
)
copies
of
the
message
for
itself.
2.
If
n
,
is
a
Fibonacci
number:
The
parent
node
A
,
no
w
simply
follo
ws
Binary
Spray
&
W
ait
algorithm,
i.e.,
it
forw
ards
ceil
(
n=
2)
number
of
copies
to
B
,
and
k
eeps
floor
(
n=
2)
for
itself.
F
ibonary
Spr
ay
and
W
ait
Routing
in
Delay
T
oler
ant
Networks
(Priyanka
Das)
Evaluation Warning : The document was created with Spire.PDF for Python.
3208
ISSN:
2088-8708
5
5
2
3
2
3
1
1
1
2
1
1
1
2
1
1
1
1
1
2
3
4
5
10
Figure
1:
Message
replica
distrib
ution
through
Binary
Spray
and
W
ait
8
2
4
3
1
1
4
2
2
1
10
1
1
1
1
1
2
3
5
6
1
1
1
3
4
Figure
2:
Message
replica
distrib
ution
through
Fi-
bonary
Spray
and
W
ait
When
a
node
is
left
with
only
1
cop
y
,
it
switches
to
direct
transmission.
Thi
s
tri
vial
case
can
be
summed
up
as
a
consequence
of
1
being
a
Fibonacci
number
,
so
in
accordance
with
clause
2
of
our
Fibonary
Spray
&
W
ait
algorit
h
m
,
direct
transmission
happens
.
Thus,
our
spraying
algorithm
in
Fibonary
Spray
&
W
ait
routing
is
actually
determined
alternately
by
the
Fibonacci
series,
and
Binary
Spray
&
W
ait
algorithm.
One
distinct
adv
antage
of
Fibonary
Spray
&
W
ait
o
v
er
Binary
Spray
&
W
ait
is
that,
in
Fi
bonary
Spray
&
W
ait,
the
direct
transm
ission
case
is
reached
earlier
than
the
corresponding
Binary
Spray
&
W
ait
Routing
with
the
same
number
of
copies.
In
other
w
ords,
Fibonacci
distrib
ution
is
more
asymmetric
compared
to
the
perfectly
symmetric
(half)
di
vision
of
message
copies
in
Binary
Spray
&
W
ait.
F
or
e
xample,
let
us
consider
the
case
of
10
copies
with
our
starting
node:
Binary
Spray
&
W
ait
di
vides
10
into
5
and
5
,
whereas
our
Fibonary
algorithm
di
vides
it
into
8
and
2
number
of
copies
(see
Figure
2).
No
w
8
may
be
further
di
vided
into
4
and
4
in
subsequent
iterations;
b
ut
on
the
other
hand
2
gets
di
vided
into
1
and
1
,
and
hence
direct
transmission
is
reached
in
the
3
r
d
le
v
el
itself.
F
or
Binary
Spray
&
W
ait
to
reach
direct
transmiss
ion
for
initial
number
of
copies
as
10
,
it
will
need
to
go
do
wn
to
the
4
th
le
v
el
in
the
spray-tree
(Figure
1).
Ho
we
v
er
,
the
best
case
may
be
impro
v
ed
in
Fibonary
Spray
&
W
ait,
when
we
compare
it
with
Binary
for
the
same
initial
number
of
copies.
This
is
actually
a
consequence
of
direct
transmission
being
reached
earlier
,
or
in
other
w
ords,
the
spray
phase
getting
o
v
er
earlier
in
one
branch
of
the
spray-tree.
The
Algorithm
for
the
same
is
illustrated
ne
xt.
In
the
algorithm,
ttl
g
=
time
to
li
v
e
of
message
g
.
Algorithm
1:
AtNode
A
1
f
or
eac
h
messa
g
e
g
with
n
copies
at
node
A
in
the
network
do
2
while
ttl
g
>
0
do
3
if
a
connection
e
xists
between
curr
ent
node
A
carrying
messa
g
e
g
and
any
other
node
B
then
4
if
n
is
NO
T
a
F
ibonacci
number
then
5
forw
ard
m
copies
of
g
to
B
6
k
eep
n
m
copies
of
g
for
itself
7
if
n
is
a
F
ibonacci
number
then
8
forw
ard
ceil
(
n=
2)
copies
of
g
to
B
9
k
eep
floor
(
n=
2)
copies
of
g
for
itself
10
if
n
=
1
then
11
forw
ard
g
to
B
if
f
B
is
the
destination
of
g
12
if
g
has
not
been
r
eceived
by
node
B
earlier
then
13
accept
g
14
mark
g
as
deli
v
ered
15
del
iv
er
ed
=
del
iv
er
ed
+
1
16
else
17
discard
g
IJECE
V
ol.
6,
No.
6,
December
2016:
3205
–
3216
Evaluation Warning : The document was created with Spire.PDF for Python.
IJECE
ISSN:
2088-8708
3209
2.1.
Mathematical
Analysis
W
e
assume
that
there
are
n
nodes
randomly
distrib
uted
with
a
uniform
distrib
ution.
Each
message
picks
one
of
the
remaining
n
1
nodes
as
its
destination
with
an
equal
probability
.
F
or
our
algorithm,
e
v
ery
message
can
ha
v
e
a
maximum
of
`
L
0
copies
b
ut
these
`
L
0
copies
are
to
be
distrib
uted
am
ong
other
nodes
on
the
occurrence
of
a
connection
based
on
a
predefined
maxim.
This
maxim
as
already
discussed
earlier
states
that
there
are
tw
o
possibilities
for
message
distrib
ution
at
e
v
ery
branching
turn.
The
tw
o
cases
that
may
arise
are:
1.
When
`
L
0
is
a
fibonacci
number:
then
tree
distrib
ution
remains
same
as
in
Binary
Spray
&
W
ait.
2.
When
`
L
0
is
not
a
fibonacci
number:
then
suppose
L
=
x
such
that,
0
;
1
;
1
;
2
;
:::a;
b;
c:::n
is
the
fibonacci
series
where
b
<
x
<
c
.
)
in
inte
ger
series,
the
position
of
x
with
respect
to
fibonacci
numbers
a;
b
and
c
w
ould
be
:::a;
b;
x;
c:::
No
w
,
in
Binary
Spray
&
W
ait,
this
x
w
ould
gi
v
e
rise
to
tw
o
di
visions
of
ceil
[
n=
2]
and
f
l
oor
[
n=
2]
.
In
Fibonary
Spray
&
W
ait,
it
w
ould
be
b
and
(
x
b
)
.
T
o
get
a
shorter
branch
we
ha
v
e
to
sho
w
that
this
dif
ference
(
x
b
)
is
less
than
x=
2
.
Note
that,
b
<
x
<
c
....................(1)
also,
c
b
=
a
....................(2)
Let
x
b
=
d
....................(3)
W
e
ha
v
e
to
pro
v
e
that
this
dif
ference
(
d
)
is
al
w
ays
less
than
x=
2
.
As
`
d
0
is
used
in
Fibonary
Spray
&
W
ait
and
x=
2
is
used
in
Binary
Spray
&
W
ait,
the
one
with
smaller
v
alue
will
gi
v
e
earlier
w
ait
phase.
W
e
kno
w
that
d
<
a
....................(4)
So
if
we
can
sho
w
a
6
x=
2
,
d
<
x=
2
can
be
deduced.
Let
us
pro
v
e
this
using
mathematical
induction.
‘
d
’
has
to
be
greater
than
1
for
x
to
be
a
non
fibonacci
number
.
)
d
>
1
)
a
>
1
)
a
is
a
minimum
of
2
,
)
b
is
a
minimum
of
3
,
)
c
is
a
minimum
of
5
,
)
x
is
a
minimum
of
4
,
So
the
first
possible
v
alue
of
x
is
4
.
F
or
x=4,
2
6
4
=
2
)
2
6
2
(true)
....................(5)
Let
this
be
true
for
x
=
n
,
a
6
n=
2
....................(6)
No
w
for
x
=
(
n
+
1)
=
2
,
we
ha
v
e
to
sho
w
that,
F
ibonary
Spr
ay
and
W
ait
Routing
in
Delay
T
oler
ant
Networks
(Priyanka
Das)
Evaluation Warning : The document was created with Spire.PDF for Python.
3210
ISSN:
2088-8708
a
6
(
n
+
1)
=
2
W
e
kno
w
,
a
6
n=
2
)
a
6
n=
2
+
1
=
2
)
a
6
(
n
+
1)
=
2
....................(7)
Hence
pro
v
ed
by
mathematical
induction.
From
(4)
,
d
<
a
,
and
a
6
(
n
+
1)
=
2
from
(7)
)
d
<
x=
2
.
)
W
e
are
bound
to
get
a
branch
in
Fibonary
Spray
&
W
ait
which
renders
quick
er
w
ait
phase
than
the
corresponding
branch
in
Binary
Spray
&
W
ait.
3.
RESUL
TS
AND
DISCUSSION
3.1.
Simulation
Setup
W
e
ha
v
e
done
our
simulation
using
the
Opportunistic
Netw
ork
En
vironment
(ONE)
simulator
(20),
which
is
specifically
designed
for
DTNs.
A
time
step
of
0
:
1
s
has
been
considered,
i.e.
an
y
e
v
ent
recording
is
done
after
a
time
step
of
0
:
1
s
.
A
ne
w
message
is
created
e
v
ery
25
to
35
seconds
with
message
sizes
v
arying
between
500
k
B
and
1
M
B
.
The
simulation
w
orld
size
is
4500
3400
meter
s
.
The
mo
v
ement
model
that
we
ha
v
e
chosen
for
all
hosts
in
our
simulation
is
the
Shortest
P
ath
Map-Based
Mo
v
ement
(SPMBM)
model.
The
reason
for
this
choice
is
that
among
the
v
arious
mo
v
ement
models
present
this
is
the
more
realistic
one
wherein
instead
of
a
completely
random
w
alk,
the
nodes
choose
a
random
point
on
the
map
and
then
follo
w
the
shortest
route
to
that
point
from
their
current
location.
Further
details
of
t
he
simulation
parameters
tak
en
into
consideration
are
discussed
in
T
able
1.
F
or
f
air
comparison
purposes
we
ha
v
e
compared
our
algorithm
with
dif
ferent
routing
schemes
in
this
genre
namely
the
Spray
&
W
ait
(also
called
the
V
anilla
Spray
&
W
ait)
(8),
Binary
Spray
&
W
ait
(8)
and
Epidemic
(3)
(these
schemes
ha
v
e
already
been
discussed
in
Section
II
Pre
vious
W
ork).
The
results
ha
v
e
been
obtained
after
a
rigorous
simulation
by
v
aryi
ng
the
number
of
copies
(
L
)
o
v
er
a
period
of
2
days.
In
addition,
a
comprehensi
v
e
comparison
of
some
of
the
popular
e
xisting
routing
protocols
is
sho
wn
in
T
able
2.
The
results
are
based
on
a
simulation
run
for
24
hours
in
the
ONE
Simulator
.
The
simulation
parameters
used
are
as
discussed
in
T
able
1.
The
initial
number
of
messages
L
for
Spray
&
W
ait
,
Binary
Spray
&
W
ait
and
Fibonary
Spray
&
W
ait,
has
been
tak
en
as
12
for
the
simulations
in
T
able
2.
The
graphs
ha
v
e
been
plotted
using
gnuplot.
T
able
1:
Simulation
P
arameters
P
arameters
Node
T
ype
Pedestrian
Cars
T
rams
No.
of
Nodes
58
30
2
Speed
0.5
to
1.5
m/s
10
to
50
km/h
7
to
10
m/s
Buf
fer
Size
5
MB
5
MB
50
MB
Message
T
ime
T
o
Li
v
e
300
minutes
300
minutes
300
minutes
3.2.
Effect
of
V
arying
Number
of
Copies
(
L
)
The
number
of
copies(
L
)
is
by
f
ar
the
most
important
metric
to
be
t
ested
by
v
ariation
for
an
y
v
ariant
of
the
Spray
&
W
ait
scheme
(including
our
Fibonary).
Hence
we
ha
v
e
compared
the
three
v
ariants
of
the
Spray
&
W
ait
(V
anilla,
Binary
and
Fibonary)
by
v
arying
the
v
alue
of
L
on
a
di
v
erse
range.
A
v
alue
of
7
for
L
has
been
considered
as
the
lo
west
and
26
the
highest.
These
simulations
ha
v
e
been
done
on
a
constant
time
scale
IJECE
V
ol.
6,
No.
6,
December
2016:
3205
–
3216
Evaluation Warning : The document was created with Spire.PDF for Python.
IJECE
ISSN:
2088-8708
3211
of
1
day
i.e.
24
hour
s
.
Since
Epidemic
Routing
has
no
concept
of
maximum
number
of
copies
(
L
),
we
omit
it
in
the
comparison
charts.
F
ollo
wing
is
the
detailed
analysis
of
the
ef
fect
of
v
arying
number
of
copies
(
L
)
on
some
selected
performance
parameters.
3.2.1.
Impact
on
Message
Deli
v
ery
pr
obability
From
the
plot
of
Figure
3
it
is
prominent
that
for
lo
wer
v
alues
of
L
,
Fibonary
S
pray
&
W
ait
gi
v
es
best
message
deli
v
ery
probability
among
the
considered
schemes.
F
or
higher
v
alues
of
L
,
though
not
the
best
b
ut
Fibonary
Spray
&
W
ait
sho
ws
consistent
performance
and
is
al
w
ays
better
than
V
anilla
Spray
&
W
ait
(results
say
the
message
deli
v
ery
probability
of
V
anilla
Spray
&
W
ait
is
on
an
a
v
erage
3%
less
than
that
of
Fibonary
Spray
&
W
ait).
All
in
all
it
gi
v
es
quite
an
impressi
v
e
performance
and
good
message
deli
v
ery
probability
on
all
v
ariations
of
L
.
3.2.2.
Impact
on
Ov
erhead
Ratio
The
o
v
erhead
ratio
is
defined
as
the
ratio
of
(Number
of
Messages
Relayed
-
Number
of
Mes
sages
Deli
v
ered)
to
(Number
of
Messages
Deli
v
ered).
The
o
v
erhead
ratio
of
both
Binary
Spray
&
W
ait
and
Fibonary
Spray
&
W
ait
is
understandably
more
than
v
anilla
as
the
y
are
more
ambitious
schemes,
b
ut
out
of
the
tw
o
the
o
v
erhead
of
Fibonary
Spray
&
W
ait
is
less
for
lo
wer
v
alues
of
L
.
Though
it
increases
for
higher
v
alues
of
L
,
it
still
gi
v
es
a
respectable
performance.
Hence
this
scheme
w
orks
superfine
for
netw
orks
with
lo
wer
v
alues
of
L
(usually
small
netw
orks)
and
also
for
higher
v
alues
of
L
as
o
v
erhead
is
just
a
tad
more
than
that
of
Binary
Spray
&
W
ait
(see
Figure
4).
3.2.3.
Impact
on
Message
Latency
The
a
v
erage
mess
age
latenc
y
for
both
Binary
Spray
&
W
ait
and
Fibonary
Spray
&
W
ait
is
more
than
V
anilla
Spray
&
W
ait
on
most
occasions.
From
Figure
5,
one
can
deduce
that
e
xcept
when
L
=
7
,
a
v
erage
message
latenc
y
in
case
of
Fibonary
Spray
&
W
ait
is
much
less
than
Binary
Spray
&
W
ait.
On
an
a
v
erage,
the
a
v
erage
message
latenc
y
of
Fibonary
Spray
&
W
ait
is
1
:
2%
less
than
that
of
Binary
Spray
&
W
ait.
The
results
of
message
latenc
y
median
though
tell
a
dif
ferent
story
.
F
or
lo
wer
v
alues
of
L
,
Fibonary
Spray
&
W
ait
w
orks
the
best
(see
Figure
6)
among
all
schemes
considered.
3.2.4.
Impact
on
Message
Hopcount
Message
hopcount
is
the
number
of
nodes
that
a
message
has
to
pass
by
before
reaching
its
desi
gnated
destination.
Hence
if
hopcount
can
be
k
ept
to
a
bare
minimum,
one
can
cash
on
a
number
of
things
lik
e
sa
ving
b
uf
fer
space,
replica,
route
congestion
etc.
Simulation
results
sho
w
that
though
V
anilla
Spray
&
W
ait
outperforms
yet
ag
ain,
among
the
other
tw
o,
Fibonary
Spray
&
W
ait
performs
better
in
most
situations
(see
Figure
7
and
Figure
8).
Especially
for
L
=
7
,
Fibonary
Spray
&
W
ait
performs
as
good
as
V
anilla
Spray
&
W
ait
(see
Figure
8).
3.2.5.
Impact
on
Message
Buffertime
The
time
a
message
spends
on
a
b
uf
fer
(source
or
intermediate)
gi
v
es
a
clearer
and
more
com
pact
vie
w
of
the
delay
incurred
as
well
as
the
congestion
created
due
to
message
replications.
Thus
this
metric
is
of
utmost
importance
and
is
one
of
the
tw
o
most
important
things
to
be
considered
for
e
v
ery
routing
scheme
in
DTN
(the
other
metric
being
message
deli
v
ery
probability).
The
plots
of
Figure
9
and
Figure
10
sho
w
that
in
both
cases
of
a
v
erage
message
b
uf
fertime
and
b
uf
fertime
median,
Fibonary
Spray
&
W
ait
performs
w
ay
better
than
V
anilla
Spray
&
W
ait.
In
f
act
here
the
V
anilla
Spray
&
W
ait
incurs
huge
delay
,
w
ay
abo
v
e
than
the
other
tw
o.
Also
Fibonary
Spray
&
W
ait
performs
better
than
Binary
Spray
&
W
ait.
Speaking
in
numbers,
on
an
a
v
erage
the
a
v
erage
message
b
uf
fertime
of
Fibonary
Spray
&
W
ait
is
19%
less
than
that
of
V
anilla
Spray
&
W
ait
and
2
:
133%
less
than
that
of
Binary
Spray
&
W
ait.
Also
the
a
v
erage
message
b
uf
fertime
median
of
Fibonary
Spray
&
W
ait
is
30%
less
than
that
of
V
anilla
Spray
&
W
ait.
So
if
we
consider
delay
due
to
b
uf
fertime
then
our
scheme
w
orks
the
best
in
the
Spray
&
W
ait
genre.
F
ibonary
Spr
ay
and
W
ait
Routing
in
Delay
T
oler
ant
Networks
(Priyanka
Das)
Evaluation Warning : The document was created with Spire.PDF for Python.
3212
ISSN:
2088-8708
0.3
0.32
0.34
0.36
0.38
0.4
0.42
0.44
5
10
15
20
25
30
Message Delivery Probability
No.of Copies (L)
Binary SnW
Vanilla SnW
Fibonary
Figure
3:
Message
Deli
v
ery
probability
(Simula-
tion
time
for
each
is
24hours)
10
12
14
16
18
20
22
24
5
10
15
20
25
30
Overhead Ratio
No.of Copies (L)
Binary SnW
Vanilla SnW
Fibonary
Figure
4:
Ov
erhead
ratio
(Simulation
T
ime
=
24
hour
s
)
3000
3100
3200
3300
3400
3500
5
10
15
20
25
30
Average Message Latency(s)
No.of Copies (L)
Binary SnW
Vanilla SnW
Fibonary
Figure
5:
A
v
erage
Message
Latenc
y
(Simulation
T
ime
=
24
hour
s
)
2400
2450
2500
2550
2600
2650
2700
2750
2800
5
10
15
20
25
30
Message Latency Median(s)
No.of Copies (L)
Binary SnW
Vanilla SnW
Fibonary
Figure
6:
Message
Latenc
y
Median
(Simulation
T
ime
=
24
hour
s
)
1.5
2
2.5
3
3.5
5
10
15
20
25
30
Average Message Hopcount
No.of Copies (L)
Binary SnW
Vanilla SnW
Fibonary
Figure
7:
A
v
erage
Message
Hopcount
(Simula-
tion
T
ime
=
24
hour
s
)
1.5
2
2.5
3
3.5
5
10
15
20
25
30
Message Hopcount Median
No.of Copies (L)
Binary SnW
Vanilla SnW
Fibonary
Figure
8:
Message
Hopcount
Median
(Simulation
T
ime
=
24
hour
s
)
2000
2200
2400
2600
2800
3000
3200
5
10
15
20
25
30
Average Message Buffertime(s)
No.of Copies (L)
Binary SnW
Vanilla SnW
Fibonary
Figure
9:
A
v
erage
Message
Buf
fertime
(Simula-
tion
T
ime
=
24
hour
s
)
1600
1800
2000
2200
2400
2600
10
15
20
25
30
Message Buffertime Median(s)
No.of Copies (L)
Binary SnW
Vanilla SnW
Fibonary
Figure
10:
Message
Buf
fertime
Median
(Simula-
tion
T
ime
=
24
hour
s
)
3.3.
Effect
of
V
arying
Simulation
T
ime
These
simulation
results
sho
w
a
candid
performance
which
ha
v
e
been
tested
for
short
as
well
as
long
periods
of
time.
F
or
this
ef
fect
we
v
aried
the
time
from
24
hour
s
(lo
w)
to
48
hour
s
(high).
When
v
arying
the
time
quotient
we
ha
v
e
k
ept
the
number
of
copies
(
L
)
at
a
constant
v
alue
of
26
.
This
we
do
to
sho
w
that
e
v
en
for
IJECE
V
ol.
6,
No.
6,
December
2016:
3205
–
3216
Evaluation Warning : The document was created with Spire.PDF for Python.
IJECE
ISSN:
2088-8708
3213
high
v
alue
of
L
,
our
scheme
w
orks
just
as
fine
as
we
ha
v
e
already
se
en
ho
w
we
ll
it
performs
for
lo
wer
v
alues
of
L
.
3.3.1.
Impact
on
Message
Deli
v
ery
pr
obability
The
bar
graphs
of
Figure
11
depicts
that
Fibonary
Spray
&
W
ait
has
more
message
deli
v
ery
probabil
ity
than
either
V
anilla
or
Epidemic
routing
(Epidemic
has
on
an
a
v
erage
43
:
1%
lo
wer
deli
v
ery
probability
than
Fibonary)
o
v
er
all
periods
of
time
tested.
It
though
lags
behind
a
little
o
v
er
Binary
Spray
&
W
ait
b
ut
the
dif
ference
is
not
much
considering
other
metrics.
3.3.2.
Impact
on
Ov
erhead
Ratio
As
e
xpected,
Figure
12
portrays
that
V
anilla
Spray
&
W
ait
and
Epidemic
routing
form
the
tw
o
oppos
ite
ends
in
the
spectrum
for
o
v
erhead
ratio.
Our
algorithm,
Fibonary
Spray
&
W
ait
is
mezzo
between
the
tw
o
techniques
and
gi
v
es
a
pretty
impressi
v
e
performance.
In
f
act
our
scheme
creates
97%
lesser
o
v
erhead
as
compared
to
Epidemic
routing.
3.3.3.
Impact
on
Message
Latency
The
a
v
erage
message
latenc
y
readings
from
the
plot
of
Figure
13
sho
ws
that
in
terms
of
latenc
y
,
Fibonary
Spray
&
W
ait
performs
better
than
Binary
Spray
&
W
ait
(it
incumbers
a
v
eragely
1
:
232%
lesser
latenc
y)and
Epidemic
routing
(on
an
a
v
erage
32
:
243%
lesser)
and
compensates
for
its
slightly
lo
wer
message
deli
v
ery
probability
than
Binary
Spray
&
W
ait.
Ev
en
if
we
consi
der
the
message
latenc
y
median
results,
(see
Figure
14),
Fibonary
Spray
&
W
ait
ag
ain
sho
ws
better
performance
than
Binary
Spray
&
W
ait
and
Epidemic
routing
(
21
:
83%
lesser)
especially
when
running
for
longer
stretches
of
time.
3.3.4.
Impact
on
Message
Hopcount
The
graphs
of
Figure
15
and
Figure
16
sho
ws
a
v
ery
interesting
result,
that
at
higher
v
alue
of
L
(=
26)
,
Binary
and
Fibonary
Spray
&
W
ait
almost
ha
v
e
the
same
a
v
erage
hopcount
and
along
with
Epidemic
ha
v
e
similar
hopcount
medians
for
v
aried
periods
of
simulation
time.
Furthermore,
Fibonary
Spray
&
W
ait
requires
24
:
4%
lesser
hopcounts
than
Epidemic
routing.
3.3.5.
Impact
on
Message
Buffertime
Figure
17
and
Figure
18
ag
ain
sho
w
that
Fibonary
Spray
&
W
ait
is
a
mezzo
between
the
lo
w
b
uf
ferti
me
of
Epidemic
and
high
b
uf
fertime
of
V
anilla
Spray
&
W
ait.
Fibonary
Spray
&
W
ait
performs
quite
decently
with
respect
to
both
a
v
erage
as
well
as
b
uf
fertime
median
gi
ving
29
:
3%
lesser
message
b
uf
ferti
me
than
Epidemic
routing
and
41
:
003%
lesser
b
uf
fertime
median
than
V
anilla
Spray
&
W
ait.
3.4.
Extensi
v
e
Comparison
T
able
2
and
T
able
3
pro
vide
further
comparison
of
Fibonary
Spray
&
W
ait
with
some
more
e
xisting
protocols.
One
can
analyse
from
these
tables
ho
w
our
proposed
algorithm,
Fibonary
Spray
&
W
ait,
stands
in
comparison
to
the
other
established
protocols
present.
W
e
did
not
include
the
lik
es
of
MaxProp,
PRoPHET
etc
in
the
pre
vious
detailed
comparisons
as
the
y
are
part
of
a
dif
ferent
cate
gory
of
protocols
and
are
not
af
fected
by
the
parameters
which
af
fect
Fibonary
Spray
&
W
ait
(
lik
e
the
v
ariable
L
).
From
T
able
2
we
observ
e
that
among
the
v
arious
routing
protocols,
the
Fibonary
Spray
&
W
ait
maintains
a
good
balance
between
Deli
v
ery
Probability
,
Ov
erhead
Ratio
and
Latenc
y
.
In
f
act
it
comes
second
only
to
MaxProp
in
terms
of
Deli
v
ery
Prob-
ability
b
ut
beats
it
in
all
other
metrics
by
a
huge
mar
gin.
Its
Ov
erhead
Ratio
is
also
on
the
lesser
side
and
in
Latenc
y
readings
beats
all
other
protocols
b
ut
Spray
&
W
ait.
4.
CONCLUSION
In
this
w
ork
we
ha
v
e
delv
ed
into
the
propitious
routing
problem
of
Delay
T
olerant
Netw
orks.
Though
a
considerable
amount
of
research
has
been
done
in
this
field,
there
still
is
a
huge
scope
for
impro
v
ement
as
dif
ferent
kinds
of
DTNs
can
benefit
from
these
schemes.
Al
so
optimal
routing
in
DTNs
being
an
NP
hard
F
ibonary
Spr
ay
and
W
ait
Routing
in
Delay
T
oler
ant
Networks
(Priyanka
Das)
Evaluation Warning : The document was created with Spire.PDF for Python.
3214
ISSN:
2088-8708
T
able
2:
A
Comparison
Between
Some
Existing
Routing
Protocols
and
Fibonary
Spray
&
W
ait
Routing
Protocols
Simulation
Results
Deli
v
ery
Probability
Ov
erhead
Ratio
Latenc
y
A
v
erage
Latenc
y
Median
Epidemic
Router
0.2491
42.2223
4509.5733
3404.1000
Spray
&
W
ait
Router
0.3461
14.0375
3143.7860
2579.0000
Binary
Spray
&
W
ait
Router
0.3621
17.6189
3264.9631
2580.3000
Fibonary
Spray
&
W
ait
Router
0.3703
17.1993
3220.5839
2580.3000
MaxProp
Router
0.4305
23.0405
6942.4543
5952.8000
PRoPHET
Router
0.2518
38.0258
4709.0958
3778.6000
First
Contact
Router
0.1896
34.7712
4944.5386
3801.8000
Direct
Deli
v
ery
Router
0.3184
0.0000
6549.6077
5725.0000
0.2
0.25
0.3
0.35
0.4
24
36
48
Message Delivery Probability
Simulation Time(h)
Binary SnW
Vanilla SnW
Fibonary
Epidemic
Figure
11:
Message
Deli
v
ery
probability
(No.
of
Copies
(
L
)
=
26
)
15
20
25
30
35
40
24
36
48
Overhead Ratio
Simulation Time(h)
Binary SnW
Vanilla SnW
Fibonary
Epidemic
Figure
12:
Ov
erhead
Ratio
(No.
of
Copies
(
L
)
=
26
)
3000
3200
3400
3600
3800
4000
4200
4400
4600
24
36
48
Average Message Latency(s)
Simulation Time(h)
Binary SnW
Vanilla SnW
Fibonary
Epidemic
Figure
13:
A
v
erage
Message
Latenc
y
(No.
of
Copies
(
L
)
=
26
)
2400
2600
2800
3000
3200
3400
24
36
48
Message Latency Median(s)
Simulation Time(h)
Binary SnW
Vanilla SnW
Fibonary
Epidemic
Figure
14:
Message
Latenc
y
Median
(No.
of
Copies
(
L
)
=
26
)
1
1.5
2
2.5
3
3.5
4
24
36
48
Average Message Hopcount
Simulation Time(h)
Binary SnW
Vanilla SnW
Fibonary
Epidemic
Figure
15:
A
v
erage
Message
Hopcount
(No.
of
Copies
(
L
)
=
26
)
1
1.5
2
2.5
3
3.5
4
24
36
48
Message Hopcount Median
Simulation Time(h)
Binary SnW
Vanilla SnW
Fibonary
Epidemic
Figure
16:
Message
Hopcount
Median
(No.
of
Copies
(
L
)
=
26
)
problem,
one
can
only
aim
to
w
ork
to
w
ards
a
particular
specific
goal.
Hence
we
proposed
our
algorithm
which
w
orks
on
the
good
points
of
the
alre
ady
established
Binary
Spray
&
W
ait
and
yet
impro
v
es
on
it
by
pro
viding
a
IJECE
V
ol.
6,
No.
6,
December
2016:
3205
–
3216
Evaluation Warning : The document was created with Spire.PDF for Python.