Social network analysis for routing in disconnected delay-tolerant MANETs

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. 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.

REFERENCES

• 1: http://reality.media.mit.edu/.
• 2: Allan Beaufour , Martin Leopold , Philippe Bonnet, Smart-tag based data dissemination, Proceedings of the 1st ACM international workshop on Wireless sensor networks and applications, September 28-28, 2002, Atlanta, Georgia, USA [doi>10.1145/570738.570749]
• 3: BORGATTI, S. P., EVERETT, M. G., AND FREEMAN, L. C. Ucinet 6 for windows: Software for social network analysis, 2002.
• 4: BURGESS, J., GALLAGHER, B., JENSEN, D., AND LEVINE, B. N. Maxprop: Routing for vehicle-based disruption-tolerant networking. In proc. Infocom 2006 (April 2006), vol. 4, IEEE, pp. 1688--1698.
• 5: S. Corson , J. Macker, Mobile Ad hoc Networking (MANET): Routing Protocol Performance Issues and Evaluation Considerations, RFC Editor, 1999
• 6: Henri Dubois-Ferriere , Matthias Grossglauser , Martin Vetterli, Age matters: efficient route discovery in mobile ad hoc networks using encounter ages, Proceedings of the 4th ACM international symposium on Mobile ad hoc networking & computing, June 01-03, 2003, Annapolis, Maryland, USA [doi>10.1145/778415.778446]
• 7: Nathan Eagle , Alex (Sandy) Pentland, Reality mining: sensing complex social systems, Personal and Ubiquitous Computing, v.10 n.4, p.255-268, March 2006 [doi>10.1007/s00779-005-0046-3]
• 8: EVERETT, M., AND BORGATTI, S. P. Ego network betweenness. Social networks (Soc. networks) 27, 1 (2005), 31--38.
• 9: FREEMAN, L. C. A set of measures of centrality based on betweeness. Sociometry (1977), 35-41.
• 10: FREEMAN, L. C. Centrality in social networks conceptual clarification. Social networks (Soc. networks) (1979), 215--239.
• 11: FRENKIEL, R. H., BADRINATH, B. R., BORRES, J., AND YATES, R. D. The infostations challenge: balancing cost and ubiquity in delivering wireless data. Personal Communications, IEEE 7, 2 (2000), 66--71.
• 12: Natalie Glance , Dave Snowdon , Jean-Luc Meunier, Pollen: using people as a communication medium, Computer Networks: The International Journal of Computer and Telecommunications Networking, v.35 n.4, p.429-442, March 2001 [doi>10.1016/S1389-1286(00)00183-3]
• 13: GROSSGLAUSER, M., AND VETTERLI, M. Locating nodes with ease: last encounter routing in ad hoc networks through mobility diffusion. In proc. INFOCOM '03 (2003), vol. 3, IEEE, pp. 1954--1964 vol.3.
• 14: HANDOREAN, R., GILL, C., AND ROMAN, G.-C. Accommodating transient connectivity in ad hoc and mobile settings. Lecture Notes in Computer Science 3001 (March 2004), 305--322.
• 15: HSU, W., AND HELMY, A. On nodal encounter patterns in wireless LAN traces. In proc. WiNMee '06 (2006), IEEE.
• 16: Sushant Jain , Kevin Fall , Rabin Patra, Routing in a delay tolerant network, ACM SIGCOMM Computer Communication Review, v.34 n.4, October 2004
• 17: JOHNSON, D., AND MALTZ, D. Dynamic source routing in ad-hoc wireless networks. Mobile Computing (1996), 152--181.
• 18: Abdelmajid Khelil , Pedro Jose Marron , Kurt Rothermel, Contact-Based Mobility Metrics for Delay-Tolerant Ad Hoc Networking, Proceedings of the 13th IEEE International Symposium on Modeling, Analysis, and Simulation of Computer and Telecommunication Systems, p.435-444, September 27-29, 2005 [doi>10.1109/MASCOT.2005.20]
• 19: Young-Bae Ko , Nitin H. Vaidya, Location-aided routing (LAR) in mobile ad hoc networks, Wireless Networks, v.6 n.4, p.307-321, July 2000 [doi>10.1023/A:1019106118419]
• 20: LEBRUN, J., CHUAH, C.-N., GHOSAL, D., AND ZHANG, M. Knowledge-based opportunistic forwarding in vehicular wireless ad hoc networks. In proc. VTC '05 (2005), vol. 4, pp. 2289--2293.
• 21: LEGUAY, J., FRIEDMAN, T., AND CONAN, V. Evaluating mobility pattern space routing for DTNs. In proc. IEEE Infocom 2006, vol. 5, IEEE, pp. 2540--2549.
• 22: Qun Li , Daniela Rus, Sending messages to mobile users in disconnected ad-hoc wireless networks, Proceedings of the 6th annual international conference on Mobile computing and networking, p.44-55, August 06-11, 2000, Boston, Massachusetts, United States [doi>10.1145/345910.345918]
• 23: David Liben-Nowell , Jon Kleinberg, The link prediction problem for social networks, Proceedings of the twelfth international conference on Information and knowledge management, November 03-08, 2003, New Orleans, LA, USA [doi>10.1145/956863.956972]
• 24: LINDGREN, A., DORIA, A., AND SCHELÉN, O. Probabilistic routing in intermittently connected networks. Lecture Notes in Computer Science 3126(2004), 239--254.
• 25: MARSDEN, P. V. Egocentric and sociocentric measures of network centrality. Social networks (Soc. networks) 24 (October 2002), 407--422.
• 26: MERUGU, S., AMMAR, M., AND ZEGURA, E. Routing in space and time in networks with predictable mobility. Technical Report GIT-CC-04-7, Georgia Institute of Technology.
• 27: MILGRAM, S. The small world problem. Psychology Today 1 (May 1967), 60--67.
• 28: Mirco Musolesi , Stephen Hailes , Cecilia Mascolo, Adaptive Routing for Intermittently Connected Mobile Ad Hoc Networks, Proceedings of the Sixth IEEE International Symposium on World of Wireless Mobile and Multimedia Networks, p.183-189, June 13-16, 2005 [doi>10.1109/WOWMOM.2005.17]
• 29: NEWMAN, M. E. J. A measure of betweenness centrality based on random walks. Technical Report cond-mat/0309045, arXiv..
• 30: NEWMAN, M. E. J. Clustering and preferential attachment in growing networks. Phys. Rev. E, 64(025102) (2001).
• 31: Sze-Yao Ni , Yu-Chee Tseng , Yuh-Shyan Chen , Jang-Ping Sheu, The broadcast storm problem in a mobile ad hoc network, Proceedings of the 5th annual ACM/IEEE international conference on Mobile computing and networking, p.151-162, August 15-19, 1999, Seattle, Washington, United States [doi>10.1145/313451.313525]
• 32: Charles E. Perkins , Pravin Bhagwat, Highly dynamic Destination-Sequenced Distance-Vector routing (DSDV) for mobile computers, Proceedings of the conference on Communications architectures, protocols and applications, p.234-244, August 31-September 02, 1994, London, United Kingdom
• 33: Charles E. Perkins , Elizabeth M. Royer, Ad-hoc On-Demand Distance Vector Routing, Proceedings of the Second IEEE Workshop on Mobile Computer Systems and Applications, p.90, February 25-26, 1999
• 34: SHAH, R. C., ROY, S., JAIN, S., AND BRUNETTE, W. Data mules: modeling a three-tier architecture for sparse sensor networks. In proc. SNPA '03 (2003), IEEE, pp. 30--41.
• 35: SPYROPOULOS, T., PSOUNIS, K., AND RAGHAVENDRA, C. S. Single-copy routing in intermittently connected mobile networks. In proc. SECON '04 (2004), IEEE, pp. 235--244.
• 36: Thrasyvoulos Spyropoulos , Konstantinos Psounis , Cauligi S. Raghavendra, Spray and wait: an efficient routing scheme for intermittently connected mobile networks, Proceedings of the 2005 ACM SIGCOMM workshop on Delay-tolerant networking, p.252-259, August 26-26, 2005, Philadelphia, Pennsylvania, USA [doi>10.1145/1080139.1080143]
• 37: TAN, K., ZHANG, Q., AND ZHU, W. Shortest path routing in partially connected ad hoc networks. In proc. GLOBECOM '03 (2003), vol. 2, IEEE, pp. 1038--1042 Vol.2.
• 38: VAHDAT, A., AND BECKER, D. Epidemic routing for partially connected ad hoc networks. Technical Report CS-200006, Duke University (2000).
• 39: WATTS, D. J., AND STROGATZ, S. H. Collective dynamics of 'small-world' networks. Nature 393, 6684 (June 1998), 440--442.
• 40: W. Zhao , M. Ammar , E. Zegura, A message ferrying approach for data delivery in sparse mobile ad hoc networks, Proceedings of the 5th ACM international symposium on Mobile ad hoc networking and computing, May 24-26, 2004, Roppongi Hills, Tokyo, Japan [doi>10.1145/989459.989483]

INDEX TERMS

Primary Classification:
  C. Computer Systems Organization
  C.2 COMPUTER-COMMUNICATION NETWORKS
      C.2.1 Network Architecture and Design
          Subjects: Store and forward networks

Additional Classification:
  C. Computer Systems Organization
  C.2 COMPUTER-COMMUNICATION NETWORKS
      C.2.1 Network Architecture and Design
          Subjects: Wireless communication

General Terms:
Algorithms, Design, Performance

Keywords:
MANETs, delay & disruption tolerant networks, ego networks, social network analysis, sparse networks