23-08-2013, 04:24 PM
Multicasting in Delay Tolerant Networks: A Social Network Perspective
Multicasting in Delay Tolerant .pdf (Size: 959.69 KB / Downloads: 29)
ABSTRACT
Node mobility and end-to-end disconnections in Delay Tolerant
Networks (DTNs) greatly impair the effectiveness of data dissem-
ination. Although social-based approaches can be used to address
the problem, most existing solutions only focus on forwarding data
to a single destination. In this paper, we are the first to study multi-
cast in DTNs from the social network perspective. We study mul-
ticast in DTNs with single and multiple data items, investigate the
essential difference between multicast and unicast in DTNs, and
formulate relay selections for multicast as a unified knapsack prob-
lem by exploiting node centrality and social community structures.
Extensive trace-driven simulations show that our approach has sim-
ilar delivery ratio and delay to the Epidemic routing, but can sig-
nificantly reduce the data forwarding cost measured by the number
of relays used.
INTRODUCTION
In Delay Tolerant Networks (DTNs) [6], mobile users contact
each other opportunistically in corporate environments, such as con-
ference sites and university campuses. Due to low node density
and unpredictable node mobility, end-to-end connections are hard
to maintain. Alternatively, node mobility is exploited to let mo-
bile nodes physically carry data as relays, and forward data oppor-
tunistically upon contacts. The key problem is how to determine
appropriate relay selection strategy and data forwarding criteria.
Experimental Traces
We use two experimental traces collected from realistic DTNs
to validate our social network modeling, and to evaluate the per-
formance of our multicast scheme. These traces record contacts
among users in corporate environments carrying Bluetooth devices.
The Bluetooth devices periodically discover their peers in the neigh-
borhood and record contacts. We believe that the chosen traces
cover a large diversity of environments, from university campuses
(MIT Reality) to conference sites (Infocom), with experimental pe-
riods from a few days (Infocom) to several months (MIT Reality).
The two traces are summarized in Table. 1.
Centrality Metric
Currently, the “betweenness” centrality metric is widely used in
social-based data forwarding [4, 9]. Betweenness measures the ex-
tent to which a node lies on the shortest paths linking other nodes,
and a node with higher betweenness has better capability of fa-
cilitating communication between other nodes. For utilization in
distributed environments, the localized version of betweenness is
proposed by Marsden [14] in the “ego-centric” network for each
node, which only includes the contacted neighbors of that node.
Unfortunately, betweenness is defined and calculated based on
the topology of network contact graph, and is not sufficient to ana-
lytically represent the probabilities for a node to contact others. To
analytically model the relay selection process in SDM, we propose
a new centrality metric based on the Poisson modeling of social
networks, in the ego-centric network of a mobile node:
Edge Splitting Process
Generally, the probabilities for various relays to forward a data
item to the same destination are not independent, due to the pos-
sible overlap of their social forwarding paths on some common
edges. For example, in Figure 5(a), paths from S to D via different
relays A1 , ..., Ar share the edge e0 = (C, E) in common2 . Such
overlap makes it difficult to calculate the cumulative data forward-
ing probabilities for multiple relays, and we eliminate such overlap
by exploiting an edge splitting process.
RELATED WORK
In [22], the authors studied Epidemic routing in DTNs. The ba-
sic idea is to select all nodes in the network as relays. Some later
work studied relay selection strategies based on node mobility pat-
terns. For example, PROPHET [13] calculates the delivery pre-
dictability at each node by using encounter history, [25] employs
some nodes with desirable mobility patterns as message ferries,
[20, 3] analyze the performance of mobility-assisted schemes the-
oretically, and [5] provides a unified approach on mobility-based
metrics. Some works make efforts on improving data forwarding
performance by either determining the data delivery likelihood [2]
or spraying data to relays waiting for contacts with destinations
[19], which is similar with our SDM scheme. However, only sim-
ple heuristics are provided for selecting relays in these approaches
CONCLUSIONS
In this paper, we studied multicast in DTNs from the social net-
work perspective, and exploited social network concepts, including
centrality and social community, to improve the cost-effectiveness
of multicast in DTNs. We investigated the essential difference be-
tween multicast and unicast in DTNs, and developed relay selection
schemes considering the forwarding probabilities to multiple des-
tinations simultaneously. Trace driven simulation results show that
our approach achieves similar delivery ratio and delay to Epidemic
routing, but significantly reduces the forwarding cost. We believe
that this paper presents the first step in exploiting social network
methods for efficient multi-party communication in DTNs. Further
research can benefit from our results by developing specific appli-
cations based on the provided multicast architecture.