Social network analysis for routing in disconnected delay-tolerant MANETs

By Elizabeth M. Daly, Mads Haahr. ACM Interational Symposium on Mobile Ad Hoc Networking and Computing, 2007

1,289 citations recorded by the source corpus.

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. This paper presents 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.

Subfields: Computer Networks and Communications, Transportation

View Paper: https://www.semanticscholar.org/paper/f533071ab697aed7f46f984ece3d1096e7c36864

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Computer Networks and Communications

1. Zhili Sun
2. Guohong Cao
3. Qinghua Li
4. Cecilia Mascolo
5. Pan Hui
6. Mirco Musolesi
7. Jon Crowcroft
8. Wei Gao

In Transportation

1. Pan Hui
2. Jon Crowcroft
3. Eiko Yoneki
4. Guohong Cao
5. Qinghua Li
6. Mirco Musolesi
7. Cecilia Mascolo
8. Sencun Zhu

Citations in the corpus

• Named Data Networking (NDN) Project (2010, background): “This approach is conceptually similar to emerging “social overlay” routing in a variety of networks [21, 62, 48, 63, 14, 64] where the destination of information propagation is a specific individual or content.”
• Optimal and scalable distribution of content updates over a mobile social network (2009, background): “In the context of DTNs, algorithms taking advantage of the social behavior of mobile users have been proposed for publish/subscribe systems [3], [4], routing [5], [6] and query propagation [6], [7].”
• Social Network Analysis for Information Flow in Disconnected Delay-Tolerant MANETs (2009, methodology): “The number of common neighbours between the current node i and destination nodej can be calculated as the sum of the total overlapping contacts as represented in the n×n matrix (for a worked example please see [10]).”
• Routing in Socially Selfish Delay Tolerant Networks (2010, methodology): “Since SimBet tends to forward packets to socially popular nodes, it overloads more hot sport nodes in the contact-dependent social graph.”
• BUBBLE Rap: Social-Based Forwarding in Delay-Tolerant Networks (2008, methodology): “For exam­ple, SimBet Routing [3] uses ego-centric centrality and its social similarity.”
• Socially-aware routing for publish-subscribe in delay-tolerant mobile ad hoc networks (2008, background): “More recently in [32] the authors use social network analysis to extract communities ties among the individuals carrying the devices.”
• Routing in Delay/Disruption Tolerant Networks: A Taxonomy, Survey and Challenges (2013, background): “SimBet [51] Betweenness, Similarity 1 Not Mentioned Not Mentioned Not Mentioned”
• MobiClique: middleware for mobile social networking (2009, background): “Several recent studies [9, 5, 3] propose to use various properties of the social graph such as node centrality and community structures to make efficient forwarding decisions.”
• A Survey of Social-Based Routing in Delay Tolerant Networks: Positive and Negative Social Effects (2013, background): “For example, SimBet [30] considers estimating centrality only based on local information, but it”
• Multicasting in delay tolerant networks: a social network perspective (2009, methodology): “We also compare our SDM scheme with other social-based data for­warding schemes including SimBet [4] and BUBBLE Rap [9] to show the essential difference between multicast and unicast in DTNs.”
• PeopleRank: Social Opportunistic Forwarding (2010, background): “Using social interaction between people for forwarding has already been proven to reduce the number of message replicas (cost) while increasing the likelihood of a message to reach its destination (success rate) [7], [14].”