CCS-DTN:Efficient Routing in Social DTNs
Based on Clustering and Network Coding
Zhenjing Zhang
1
, Maode Ma
2
, Zhigang Jin
3
1
School of Computer Science and Technology, Tianjin University, China
2
School of Electrical and Electronic Engineering, Nanyang Technological University, Singapore
3
School of Electronic Information Engineering, Tianjin University, China
ABSTRACT
—
With the development of mobile internet, wireless
communications via mobile devices, which is typically in the form
of Delay Tolerant Networks (DTNs), becomes a hot research topic.
One critical issue in the development of DTNs is the routing.
Although there are a lot research works addressing routing issues
in DTNs, they handle routing problem from only one or two
aspects, which cannot produce an advanced solution to this
comprehensive challenge. In view of these defects in the existing
works, we propose a novel solution to address the routing issue of
one type of DTNs in which mobile nodes can be divided into
different clusters. A simple routing protocol can be used for the
intra-cluster communication, while, for the inter-cluster one,
messages will be forwarded to a relay node, which is selected by a
new selection policy, supported by the network coding technique.
The simulation results show that our proposed scheme can
significantly improve the performance of the routing in DTNs.
KEYWORDS
—
Delay Tolerant Network; Routing; Clustering;
Social; Delivery Probability
I
.
I
NTRODUCTION
With the development of mobile internet, communications
via mobile devices becomes a hot research topic which is over a
typical Delay Tolerant Network (DTN) network. DTNs hold a
new network architecture which uses a store-carry-forward
communication model to forward messages because there is not
a persistent end-to-end path from the source to the destination.
A lot of research works have been done on the efficient routing
and transmission of messages in a DTN environment. Pioneer
studies on the routing in DTNs mainly focused on the actions to
do for the next hop transmission with consideration of history
information. Typical protocols include Epidemic [1], PREP [2],
Spray and Wait [3], Probabilistic Routing Protocol using
History of Encounters and Transitivity (PROPHET) [4] and
some other improvements and variations proposed. Although
they work well to be able to achieve high message delivery
ratio, messages are delivered with high latency. To reduce the
delay, other properties such as mobility model and the
relationship among mobile nodes are considered. In some
particular DTN environments, clustering and hierarchical
technologies have been proposed to reduce the delay, such as
the ones in [5, 6]. By these protocols, the mobile nodes with
frequent contact and the mobile nodes with less contact are
treated differently. By these mechanisms, the efficiency of
message transmission can be improved. However, the
destination of messages may not be able to receive all the
messages due to the unreliability of the wireless
communication channels.
It is clear that messages loss can be reduced if the
destination of the message can receive enough coded messages
when network coding technique is used. Some existing
researches show that applying network coding technique to the
DTN environments can obtain the performance improvements.
In [7], based on the fact that there are some mobile nodes,
denoted as HUBs, which have frequent contacts with other
mobile nodes, a new mechanism, HUBCODE, is proposed to
use the random linear network coding scheme to address the
routing issue, which can obtain 20% improvement.
By the above-mentioned routing schemes, good
performance may not be obtained in some DTNs which have
the characteristics of social networks. Existing studies show
that in such scenarios, there are some active nodes which can
transmit messages to their destinations with less hops. For
example, in a campus scenario, students in the same group
contact frequently while students in different groups have less
contact. But group leaders have more contacts between
different groups. A new scheme in [8] have been proposed to
address routing issue in such DTNs. A more efficient
combination of the social characteristics of mobile nodes and
the relationship among nodes is expected to achieve better
performance.
In general, considering the characteristics of DTN and the
properties of social networks, we propose a new routing
scheme, named as Social Delay Tolerant Network based on
Clustering and Coding (CCS-DTN) which divides mobile
nodes into different clusters. The scheme, Spray and Wait, is
used for the intra-cluster routing. For the inter-cluster routing,
messages will be transmitted by active nodes which move
among clusters. To reduce message loss, these messages are
coded by the random linear network coding scheme. By using
the network coding technique with the consideration of the
properties of social networks, our proposal can improve the
message delivery rate and reduces end-to-end delay greatly.
The remainder of this paper is organized as follows. In
Section II, system model is introduced. The proposed routing
mechanism is presented in Section III. And in Section IV, the
performance is analyzed. Finally, the conclusion of the paper is
summarized in section V.
II
.
S
YSTEM MODEL
A
.
Characteristics of DTNs
The communication in DTNs is a type of asynchronous
communication without requiring an end-to-end path at any
moment. One of its main characteristics is that the links
between mobile nodes are volatile and may break down for a
long period of time at any time, which makes the DTNs always
suffering from partitioning from time to time. The partitioning
in DTNs may last a long period of time so that it cannot be
assumed that a path exists between the source and the
destination. The other characteristics of the DTNs include
sparse of network nodes, high packet loss rate and high latency.
Moreover, the strong mobility of the DTN nodes leads to that
the network topology is easily changeable.
There are ubiquitous scenarios of the DTNs including
mobile sensor networks, disaster recovery, military deployment
and interstellar communications to hold those characteristics.
And there are some scenarios which are formed by several
clusters. In such scenarios, the mobile nodes in the same cluster
contact frequently and several active nodes communicate
between different clusters. These active mobile nodes show
same characteristics as some nodes in the social networks.
Therefore, the characteristics of social networks can be
borrowed to design the routing protocols in such scenarios.
B
.
Characteristics of Social Networks
A social network is one type of network formed by
cooperations among people. Due to different characteristics of
Globecom 2013 - Ad Hoc and Sensor Networking Symposium
978-1-4799-1353-4/13/$31.00 ©2013 IEEE 60