Time Routing: a community based routing protocol
for Opportunistic Networks
Xuebin Ma, Zhenchao Ouyang, Jing Bai, Xin Zhan
Department of Computer Sciences
Inner Mongolia University
Hohhot, China
{maxuebin, ouyangkid, bayjing1218, zhanxin0223}@gmail.com
Abstract—Opportunistic Networks are self-organized mobile
ad hoc networks. In this situation, stable end-to-end paths can
hardly exist for message delivering due to the mobility of nodes,
the limited radio range, energy problems, low transporting speed
and other shortcomings. Routing protocols for this situation need
to solve the incurred delays, unpredictable routing hops, high
drop rate, etc, so the “Store-Carry-and-Forward” strategy is
proposed.
Here, we designed Time Routing (TR) on the basis of an
overlapping community detection algorithm which was proposed
in our previous work by analyzing the movement mode of people.
TR can automatically divide the neighbor nodes into different
sub-communities and choose more suitable nodes as candidate
relays. By simulating with real trace data, it shows that the TR
maintains lower delivery cost and keeps higher delivery ratio
than other protocols.
Keywords—Opportunistic Networks, Social based, Overlapping
community, Routing protocol
I. INTRODUCTION
Recently, delay or disruption tolerant networks (DTNs)
have drawn much attention of researchers for its developing
routing protocols, QoS schemes, etc. in this challenging
environment. For lacking of communication infrastructures,
message forwarding in DTNs is mainly based on mobile
devices with short radio range, such as PDAs, smart phones,
tablet PCs. As a result, data forwarding in the DTNs, with low
node density, becomes an extremely arduous work. To address
this problem, the “store-carry-and-forward” strategy is
proposed to utilize the mobility of nodes. Latterly, routing
protocols tend to be designed based on that.
Early routing protocols for DTNs are mainly based on the
following two categories: the opportunity based and the
prediction based protocols. The opportunity based protocols
use uncontrolled or controlled flooding strategies to increase
the message copies, resulting in increasing delivery opportunity.
While the prediction based protocols use different metrics, such
as the similarity, centrality and degree, to predict the behavior
of nodes, and choose the node which is more likely to meet the
destination as relay.
Lately, the utilizing of social characteristics provides great
probability to improve the message forwarding and other
applications in the DTNs. Opportunistic Networks, Pocket
Switch Networks (PSN), and Vehicular Networks are mobile
social networks which consisting of human beings. By taking
advantage of the social characteristics, several social based
DTNs routing schemes have been proposed (such as the Bubble
Rap
[1]
and the SimBet
[2]
).
In this paper, we focus our attention on the social based
routing strategy in Opportunistic Networks. In such networks,
communication devices with short radio range are carried by
people. The study on the mobility of devices becomes the study
of their carriers. In our previous work
[3]
, we proposed an
overlapping community detection algorithm for social structure
analysis in Opportunistic Networks.
By utilizing the overlapping community structures, we
designed the Time Routing (TR). The overlapping community
structure consists of several sub-communities, and they
periodically appear as a time varying social graph. In our
routing protocol, the local node periodically checks its current
and future sub-communities, and chooses the nodes which are
more likely to meet the destination as relays. In this way, we
can avoid ‘blindly forwarding’ and spare network resources.
The rest of the paper is structured as follows: In Section II,
we review related work on routing in DTNs. Then, we
introduce the overlapping community based routing scheme,
the Time Routing in Section III. In Section IV, we setup the
simulation on ONE (Opportunistic Networks Environment)
[6]
simulator and evaluate the results. Finally we summarize the
paper and discuss about future work in the last section.
II.
RELATED WORK
As mentioned above, we divide Opportunistic Networks
routing protocols into three categories based on which property
a strategy uses to find the destination. They are the flooding
based routing protocols, the metrics based routing protocols
and the community based routing protocols. We focus our
attention on the metrics based and community based routing
strategies, because our TR is a combination of the two
techniques.
A. Metric Based Routing Protocol
Traditionally, this kind of protocol uses the geography
information to measure the distance between nodes, and
2014 IEEE International Conference on Computer and Information Technology
978-1-4799-6239-6/14 $31.00 © 2014 IEEE
DOI 10.1109/CIT.2014.28
20