Workshop on Online Social
Networks
Participation by
invitation only
Microsoft Research
Cambridge, UK.
December 7, 2007.
Social Network Analysis for Routing in
Disconnected Delay-Tolerant MANETs
Elizabeth Daly (University
of Dublin)
Abstract:
Message delivery
in sparse Mobile Ad hoc Networks (MANETs) is
difficult due to the fact that the network graph is rarely (if ever)
connected. A key challenge is to find a route that can provide good delivery
performance and low end-to-end delay in a disconnected network graph where
nodes may move freely.We present a
multidisciplinary solution based on the consideration of the so called small
world dynamics which have been proposed for economy and social studies and
have recently revealed to be a successful approach to be exploited for
characterising information propagation in wireless networks. To this purpose,
some bridge nodes are identified based on their centrality characteristics,
i.e., on their capability to broker information exchange among otherwise
disconnected nodes. Due to the complexity of the centrality metrics in
populated networks the concept of ego networks is exploited where nodes are
not required to exchange information about the entire network topology, but
only locally available information is considered. Then SimBet
Routing is proposed which exploits the exchange of pre-estimated 'betweenness' centrality metrics and locally determined
social 'similarity' to the destination node. We present simulations using
real trace data to demonstrate that SimBet Routing
results in delivery performance close to Epidemic Routing but with
significantly reduced overhead. Additionally, we show that SimBet Routing outperforms PRoPHET
Routing, particularly when the sending and receiving nodes have low
connectivity.
|