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. BEAUFOUR, A., LEOPOLD, M., AND BONNET, P. Smart-tag based data dissemination. In proc. WSNA '02 (2002), ACM Press, pp. 68--77.
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. CORSON, S., AND MACKER, J. Mobile ad hoc networking (manet): Routing protocol performance issues and evaluation considerations, rfc 2501, 1999.
6. DUBOIS-FERRIERE, H., GROSSGLAUSER, M., AND VETTERLI, M. Age matters: efficient route discovery in mobile ad hoc networks using encounter ages. In proc. MobiHoc '03 (2003), ACM Press, pp. 257--266.
7. EAGLE, N., AND PENTLAND, A. Reality mining: sensing complex social systems. Personal and Ubiquitous Computing V10, 4 (May 2006), 255--268.
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. GLANCE, N., SNOWDON, D., AND MEUNIER, J.-L. Pollen: using people as a communication medium. Comput. Networks 35, 4 (March 2001), 429--442.
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. JAIN, S., FALL, K., AND PATRA, R. Routing in a delay tolerant network. SIGCOMM Comput. Commun. Rev. 34, 4 (October 2004), 145--158.
17. JOHNSON, D., AND MALTZ, D. Dynamic source routing in ad-hoc wireless networks. Mobile Computing (1996), 152--181.
18. KHELIL, A., MARRON, P. J., AND ROTHERMEL, K. Contact-based mobility metrics for delay-tolerant ad hoc networking. In proc. MASCOTS '05 (2005), IEEE, pp. 435--444.
19. KO, Y.-B., AND VAIDYA, N. H. Location-aided routing (lar) in mobile ad hoc networks. Wirel. Netw. 6, 4 (July 2000), 307--321.
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. LI, Q., AND RUS, D. Sending messages to mobile users in disconnected ad-hoc wireless networks. In proc. MobiCom '00 (2000), ACM Press, pp. 44--55.
23. LIBEN-NOWELL, D., AND KLEINBERG, J. The link prediction problem for social networks. In proc. CIKM '03 (2003), ACM Press, pp. 556--559.
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. MUSOLESI, M., HAILES, S., AND MASCOLO, C. Adaptive routing for intermittently connected mobile ad hoc networks. In proc. WoWMoM '05 (2005), IEEE, pp. 183--189.
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. NI, S.-Y., TSENG, Y.-C., CHEN, Y.-S., AND SHEU, J.-P. The broadcast storm problem in a mobile ad hoc network. In proc. MobiCom '99 (1999), ACM Press, pp. 151--162.
32. PERKINS, C. E., AND BHAGWAT, P. Highly dynamic destination-sequenced distance-vector routing (dsdv) for mobile computers. In proc. SIGCOMM '94 (October 1994), vol. 24, ACM Press, pp. 234--244.
33. PERKINS, C. E., AND ROYER, E. M. Ad-hoc on-demand distance vector routing. In proc. WMCSA '99 (1999), IEEE, pp. 90--100.
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. SPYROPOULOS, T., PSOUNIS, K., AND RAGHAVENDRA, C. S. Spray and wait: an efficient routing scheme for intermittently connected mobile networks. In proc. WDTN '05 (2005), ACM Press, pp. 252--259.
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. ZHAO, W., AMMAR, M., AND ZEGURA, E. A message ferrying approach for data delivery in sparse mobile ad hoc networks. In proc. MobiHoc '04 (2004), ACM Press, pp. 187--198.

Index Terms

• Networks

  • Network types

    • Mobile networks

    • Wireless access networks