30-10-2012, 04:56 PM
Conditional Shortest Path Routing in Delay Tolerant Networks
Conditional Shortest Path.pdf (Size: 134.79 KB / Downloads: 16)
Abstract
Delay tolerant networks are characterized by the
sporadic connectivity between their nodes and therefore the lack
of stable end-to-end paths from source to destination. Since the
future node connections are mostly unknown in these networks,
opportunistic forwarding is used to deliver messages. However,
making effective forwarding decisions using only the network
characteristics (i.e. average intermeeting time between nodes)
extracted from contact history is a challenging problem. Based
on the observations about human mobility traces and the findings
of previous work, we introduce a new metric called conditional
intermeeting time, which computes the average intermeeting time
between two nodes relative to a meeting with a third node
using only the local knowledge of the past contacts. We then
look at the effects of the proposed metric on the shortest path
based routing designed for delay tolerant networks. We propose
Conditional Shortest Path Routing (CSPR) protocol that routes
the messages over conditional shortest paths in which the cost
of links between nodes is defined by conditional intermeeting
times rather than the conventional intermeeting times. Through
trace-driven simulations, we demonstrate that CSPR achieves
higher delivery rate and lower end-to-end delay compared to the
shortest path based routing protocols that use the conventional
intermeeting time as the link metric.
INTRODUCTION
Routing in delay tolerant networks (DTN) is a challenging
problem because at any given time instance, the probability
that there is an end-to-end path from a source to a destination
is low. Since the routing algorithms for conventional networks
assume that the links between nodes are stable most of the
time and do not fail frequently, they do not generally work
in DTN’s. Therefore, the routing problem is still an active
research area in DTN’s [1].
Routing algorithms in DTN’s utilize a paradigm called
store-carry-and-forward. When a node receives a message
from one of its contacts, it stores the message in its buffer and
carries the message until it encounters another node which is
at least as useful (in terms of the delivery) as itself. Then the
message is forwarded to it.
CONDITIONAL INTERMEETING TIME
An analysis of real mobility traces has been done in
different environments (office [13], conference [20], city [23],
skating tour [14]) with different objects (human [11], bus [12],
zebra [24]) and with variable number of attendants and led to
significant results about the aggregate and pairwise mobility
characteristics of real objects. Recent analysis [13] [14] [20]
on real mobility traces have demonstrated that models assuming
the exponential distribution of intermeeting times between
pairs of nodes do not match real data well. Instead up to
99% of intermeeting times in many datasets is log-normal
distribution. This makes the pairwise contacts between nodes
depend on their pasts. Such a finding invalidates a common
assumption [8] [17] [25] that the pairwise intermeeting times
are exponentially distributed and memoryless.
SIMULATIONS
To evaluate the performance of our algorithm, we have built
a discrete event simulator in Java. In this section, we describe
the details of our simulations through which we compare the
proposed Conditional Shortest Path Routing (CSPR) algorithm
with standard Shortest Path Routing (SPR). Moreover, in our
results we also show the performance of upper and lower
performance boundaries with Epidemic Routing [4] and Direct
Delivery.
We used two different data sets: 1) RollerNet traces [14]
which includes the opportunistic contacts of 62 iMotes which
are distributed to the rollerbladers during a 3 hour skating tour
of Paris on August 20, 2006, 2) Cambridge Dataset [23] which
includes the Bluetooth contacts of 36 students from Cambridge
University carrying iMotes around the city of Cambridge, UK
from October 28, 2005 to December 21, 2005.
To collect several routing statistics, we have generated traffic
on the traces of these two data sets. For a simulation run,
we generated 5000 messages from a random source node to
a random destination node at each t seconds. In RollerNet,
since the duration of experiment is short, we set t = 1s, but
for Cambridge data set, we set t = 1 min. We assume that
the nodes have enough buffer space to store every message
they receive, the bandwidth is high and the contact durations
of nodes are long enough to allow the exchange of all
messages between nodes.
CONCLUSION AND FUTURE WORK
In this paper, we introduced a new metric called conditional
intermeeting time inspired by the results of the recent studies
showing that nodes’ intermeeting times are not memoryless
and that motion patterns of mobile nodes are frequently
repetitive. Then, we looked at the effects of this metric on
shortest path based routing in DTN’s. For this purpose, we
updated the shortest path based routing algorithms using conditional
intermeeting times and proposed to route the messages
over conditional shortest paths. Finally, we ran simulations
to evaluate the proposed algorithm and demonstrated the
superiority of CSPR protocol over the existing shortest path
routing algorithms.
In future work, we will look at the performance of the
proposed algorithm in different data sets to see the effect
of conditional intermeeting time in different environments.
Moreover, we will consider extending our CSPR algorithm by
using more information (more than one known meetings) from
the contact history while deciding conditional intermeeting
times. For this, we plan to use probabilistic context free grammars
(PCFG) and utilize the construction algorithm presented
in [26]. Such a model will be able to hold history information
concisely, and provide further generalizations for unseen data.