Proceedings
of
2009 12
th
International Conference on Computer and Information Technology (ICCIT 2009)
21-23 December, 2009, Dhaka, Bangladesh
A
Probabilistic
Position-based Routing Scheme
for
Delay-
Tolerant Networks
Farzana Yasmeen, Shigeo urushldanl", Shigeki Yamada!
Department
of
Informatics, The Graduate University for Advanced Studies, Tokyo, Japan
t National Institute
of
Informatics, Tokyo, Japan
bonhomie@niLac.jp,urushi@niLac.jp, shigeki@niLac.jp
Abstract
Observably, participants in realistic scenarios re-
peatedly navigate specific locations based on routine
behavior, leading to inherently structured movement
patterns. In this paper we propose a delay-tolerant
routing scheme, called Probabilistic Routing with
Minimum Proximity
(PRMP),
which aims to utilize
prior movement patterns
of
peers to predict future
probability
of
forwarding messages to a location
proximal to a destinations home address. A source
considers next-hopforwarding based on a probabilis-
tic benefit-metric; which takes into account a nodes
frequented trajectories and current position, its spa-
tial distance from a destinations stationary home lo-
cation and the probability
of
any
of
its immediate
trajectories minimizing the spatial distance to the
destinations home. Delivering a message to a nodes'
home address in the network is synonyms to deliver-
ing mail to an individual's designated mailbox. The
protocol avoids flooding completely in efforts to op-
timize use
of
network resources. Simulations
of
PRMP reflect low buffer occupancy at both high and
low loads in the network. It also maintains resource
optimization in varying node densities compared to
two prominent DTN flooding protocols - Epidemic
and PRoPHET.
Keywords:
DTN, Intermittent Connectivity,
Routing Protocol, Location-based Routing.
I. INTRODUCTION
Delay-tolerant Networking (DTN) [1] is gradually
emerging as the de-facto standard for providing
communication solutions in intermittently connected
networks and challenged environments. These envi-
ronments usually consist
of
wireless, mobile nodes
where there may be frequent, long-duration partitions
in the network causing excessive delivery latency and
high error rates in transmissions. Presumably, in such
scenarios establishment
of
an end-to-end connection
between a traffic source and its destination, prior to
message forwarding is unattainable, rendering many
tested ad hoc routing protocols [2]-[4] impracticable.
DTN networks, therefore, require special attention
considering the problem
of
routing. The DTN archi-
tecture model [5] proposes asynchronous message
switching in a store-and-forward manner along with
978-1-4244-6284-1/09/$26.00 ©2009 IEEE
88
custodial transfer
of
bundles (message aggregates) to
allow for communication in intermittent networks.
Applications such as nomadic networks and connec-
tivity constrained networks can benefit from such an
opportunistic forwarding architecture [6], [7].
Recent studies on the distribution
of
inter-contact
time
of
participants [8] and mobility characteristics
of
nodes [10] in challenged networks provide sound
evidence that routing in constrained environments
may improve performance-wise by considering the
underlying behavior patterns
of
network participants.
In this paper, we introduce a novel DTN routing pro-
tocol for non-random, location-aware contexts. It has
been often quoted "Mobility is two faced"; in our
case message delivery depends on the mobility
of
nodes but successful delivery can also be hampered
due to a destinations constant movement, especially
in disruptive situations where no end-to-end path
exists and the addressing space is flat [11]. To in-
crease reliability
of
message deliverance, an intended
message for the final recipient is forwarded to its'
stationary home location, as obtaining the contempo-
raneous location
of
a roaming destination in remote
situations and without any hierarchical infrastructure
is convoluted. The local decision
of
selecting a for-
warder depends on available information from pre-
vious node roaming and currently achievable space
minimization to the intended destinations home. The
protocol focuses improving network performance by
achieving a steady state
of
resource consumption,
even during very high event generation in the net-
work.
The remainder
of
this paper is organized as follows:
Section II presents an overview
of
related DTN
routing protocols. Section III states the underlying
assumptions
of
our protocol and describes necessary
metrics along with explanation
of
the routing me-
chanism. A quantitative evaluation
of
our protocol is
given in Section IV, comparing with two mainstream
DTN routing protocols - Epidemic and PRoPHET.
Finally, Section V concludes the paper by outlining
future work.
II. RELATED WORKS
In recent years numerous routing protocols have been
proposed for DTNs, each with solutions depending
on, but not limited to, the amount
of
tolerable delay