A Heterogeneous Theoretical Framework for The
Analysis of Delay Tolerant Networks
Lin Bai, Xuebin Ma, ZhenChao Ouyang
Department of Computer Sciences
Inner Mongolia University Hohhot, China
{bamboo20131108, maxuebin, ouyangkid} @gmail.com
Abstract—In this paper, we first present a heterogeneous
theoretical framework for DTNs where the contact between
nodes is based on independent differently distributed assumption.
Moreover, the message forwarding process follows a Gamma
Distribution. Then, we propose a new spray routing scheme
based on this framework. Moreover, we compare our routing
protocol with traditional spray routing (TSR) protocols and
epidemic (EP) routing scheme on the ONE simulator with both
real dataset of Infocom06 and scenario of Working Day
Movement Model. Simulation results show that our scheme is
significantly better than TSR and EP in the following four
aspects: average number of copies, average number of hop
counts, average delivery latency and delivery rate.
Keywords-delay tolerant network; spray scheme; theoretical
framework; ONE simulator
I. INTRODUCTION
Delay Tolerant Networks (DTNs) [1] are mobile wireless
networks where there not exits a complete and stable link from
the source to the destination. In this situation, mobile Ad-Hoc
network routing schemes (e.g. DSR, AODV [2]) cannot work.
Because a stable path between the source and the destination
needs to be established and maintained when data are sent.
To deal with the message delivery in DTNs, several routing
schemes are designed and developed. Such as controlled
replication routing protocols (e.g. single-copy [3, 4, 5], fix
budget L [6,7] and utility-based [8, 9, 10]). In controlled
replication routing protocols, a fix number of message copies
is generated and distributed to different nodes, each node then
carries its copy until it encounters the destination.
In this paper, we first present an analytical framework for
DTNs, where the contact between nodes is based on the
independent differently distributed (IDD) assumption [11, 12].
In the IDD assumption, distributed parameter, such as contact
rate between nodes, is different and independent for different
nodes. Meanwhile, the message forwarding process follows a
Gamma Distribution (GD) [13]. Based on this framework, we
proposed a new spray routing scheme: the Message-Time-To-
Live based probability routing protocol (MTTLP). Then, we
compared our routing scheme with traditional spray routing
protocols (TSR [6, 7]) and epidemic routing protocol (EP [14]).
Simulation results show that our MTTLP is significantly better
than TSR and EP.
The rest of this paper is organized as follows: Section II
describes related work. In Section III and IV, we talk about the
theoretical framework and routing scheme. And then, the
simulation results of the MTTLP, TSR and EP are compared
and showed in Section V. Lastly, we conclude our work.
II. R
ELATED WORK
As mentioned above, the controlled replication routing
protocols were designed and developed for decreasing the
consumption of the network resource in DTNs. Through
different message forwarding control schemes, controlled
replication routing protocols effectively reduced network
resource consumption, and improved the network performance.
The spray routing scheme is one of the typical controlled
replication routing scheme [6 7], and has been widely applied
in DTNs. There are three main categories of spray routing
protocols, including the binary spray & wait (BSW), spray &
wait (SW) and spray & focus (SF) [6, 7]. Although their spray
and wait schemes are different, they all based on the IID
(independent identically distributed) assumption of node
mobility, such as the Random Walk and Random Waypoint. In
[15, 16, 17], several researches based on real scenarios proved
that the IID assumption node mobility was far from real world.
In [11, 12], the heterogeneous network model was
established and analyzed. In this kind of model, the contact
between nodes is based on IDD assumption. What’s more,
more complex behavior between nodes was researched and
proposed for the routing designing for DTNs [8]. In [11, 12],
experimental simulation results showed that heterogeneous
model was more reliable and reasonable than the IID
assumption based models.
In order to make our analysis closer to the real environment,
we establish a theoretical framework in which the contact
between nodes is based on the IDD assumption. And the
message forwarding process follows the GD. Then, we
propose a new spray routing scheme (MTTLP) based on this
framework. In the following section, we describe the detail of
our theoretical framework and MTTLP.
III.
THEORETICAL FRAMEWORK
In this section, we first give some basic assumptions that
help us build our theoretical framework. And then, the
framework is presented. After that, we derive some important
information based on our theory, such as maximum fixed
budget (MFB) and maximum message latency (MML).
____________________________________
978-1-4799-3279-5 /14/$31.00 ©2014 IEEE