Exploring social properties in vehicular ad hoc networks

ABSTRACT

Vehicular Ad Hoc Networks (VANETs) enable car-to-car communication without the support of network infrastructure, which introduce diverse application possibilities and have drawn much attention from academy and industry in the past years. Unlike other ad hoc networks, nodes in VANETs are restricted to move in streets and have limited communication ranges. Intuitively, vehicle-to-vehicle communication somehow has similarity to human-to-human interaction, which lead to an interesting question of exploring the social properties of VANET nodes. To address the question, we consider encounters of vehicles as their social relationships and model VANETs as social graphs. Based on the social graph model, we use two traces of mobile vehicles from San Francisco and Shanghai to explore their social properties. Our analysis show that several universal laws of social network are hold for VANETs. The social graphs forming by vehicles are scale-free networks with power-law like distribution of node degrees. Small world phenomenon is also observed in our experiments: the nodes in VANETs have high cluster coefficient and there exist short paths between node pairs less than 3 hops on average. The implication of our analytical results is of benefit to develop large scale software system for mobile applications such as VANETs, as well as helps to facilitate inter-device wireless communications in pervasive environment.

References

1. L. A. Adamic and E. Adar. How to search a social network. Social Networks, 27:2005, 2005.
2. N. Balon and J. Guo. Increasing broadcast reliability in vehicular ad hoc networks. In Proceedings of the 3rd international workshop on Vehicular ad hoc networks, VANET '06, pages 104--105, New York, NY, USA, 2006. ACM.
3. B. Bollobás. Random Graphs. Academic Press, London, 1985.
4. S. Burleigh, A. Hooke, L. Torgerson, K. Fall, V. Cerf, B. Durst, K. Scott, and H. Weiss. Delay-tolerant networking: an approach to interplanetary internet. IEEE Communications Magazine, 41(6):128--136, June 2003.
5. C. Chen, D. Zhang, P. S. Castro, N. Li, L. Sun, and S. Li. Real-time detection of anomalous taxi trajectories from gps traces. In In MobiQuitous '12, 2011.
6. J. Cranshaw, E. Toch, and J. H. A. Kittur. Bridging the gap between physical location and online social networks. In In Ubicomp '10, 2010.
7. D. Easley and J. Kleinberg. Networks, Crowds, and Markets: Reasoning about a Highly Connected World. Cambridge University Press, Cambridge, MA, USA, 2010.
8. P. Erdős and A. Rényi. On random graphs. I. Publ. Math. Debrecen, 6:290--297, 1959.
9. W. Gao, Q. Li, B. Zhao, and G. Cao. Multicasting in delay tolerant networks: a social network perspective. In Proceedings of the tenth ACM international symposium on Mobile ad hoc networking and computing, MobiHoc '09, pages 299--308, New York, NY, USA, 2009. ACM.
10. P. Hui, J. Crowcroft, and E. Yoneki. Bubble rap: social-based forwarding in delay tolerant networks. In Proceedings of the 9th ACM international symposium on Mobile ad hoc networking and computing, MobiHoc '08, pages 241--250, New York, NY, USA, 2008. ACM.
11. L. Jian, X. Ma, and X. Tao. Research and progress of internetware. Science in China, 36(10):1037ĺC1080, 2006.
12. T. Karagiannis, J.-Y. Le Boudec, and M. Vojnović. Power law and exponential decay of inter contact times between mobile devices. In Proceedings of the 13th annual ACM international conference on Mobile computing and networking, MobiCom '07, pages 183--194, New York, NY, USA, 2007. ACM.
13. R. Khokhar, R. M. Noor, K. Ghafoor, C.-H. Ke, and M. A. Ngadi. Fuzzy-assisted social-based routing for urban vehicular environments. EURASIP J. Wireless Comm. and Networking, 2011:178, 2011.
14. T. Kosch, C. Adler, S. Eichler, C. Schroth, and M. Strassberger. The scalability problem of vehicular ad hoc networks and how to solve it. IEEE Wireless Communications, 13(5):22--28, october 2006.
15. J. Leskovec and E. Horvitz. Planetary-scale views on an instant-messaging network, 2007.
16. K. Lewis, J. Kaufman, M. Gonzalez, A. Wimmer, and N. Christakis. Tastes, ties, and time: A new social network dataset using facebook.com, 2009.
17. Q. Li, Y. Zheng, X. Xie, Y. Chen, W. Liu, and W.-Y. Ma. Mining user similarity based on location history. In Proceedings of the 16th ACM SIGSPATIAL international conference on Advances in geographic information systems, GIS '08, pages 34:1--34:10, New York, NY, USA, 2008. ACM.
18. W. Li, E. Chan, M. Hamdi, S. Lu, and D. Chen. Communication cost minimization in wireless sensor and actor networks for road surveillance. IEEE Transactions on Vehicular Technology, 60(2):618--631, 2011.
19. X. Li, G. Pan, Z. Wu, G. Qi, S. Li, D. Zhang, W. Zhang, and Z. Wang. Prediction of urban human mobility using large-scale taxi traces and its applications. Front. Comput. Sci China, 6(1):111--121, Feb. 2012.
20. B. Mark. Nexus: Small Worlds and the Groundbreaking Theory of Networks. Norton, W. W. & Company, Inc., 2003.
21. H. Mei. Internetware: Challenges and future direction of software paradigm for internet as a computer. In Proc. 34 Ann. Conf. Computer, Software, and Applications, page 14ĺC16, 2012.
22. H. Mei, G. Huang, and T. Xie. Internetware: A software paradigm for internet computing. IEEE Computer, 45(6):26--31, june 2012.
23. A. G. Miklas, K. K. Gollu, K. W. Chan, K. P. Gummadi, and E. D. Lara. Exploiting social interactions in mobile systems. In In UbiComp, 2007.
24. M. Piorkowski, N. Sarafijanovic-Djukic, and M. Grossglauser. CRAWDAD data set epfl/mobility (v. 2009-02-24). http://crawdad.cs.dartmouth.edu/epfl/mobility, Feb 2009.
25. S. Qian, Y. Zhu, and M. Li. Smart recommendation by mining large-scale gps traces. In In WCNC '12, 2012.
26. H. report. http://www.hitwise.com/us/press-center/press-releases/facebook-was-the-top-search-term-in-2010-for-sec/, 2011.
27. J. Travers, S. Milgram, J. Travers, and S. Milgram. An experimental study of the small world problem. Sociometry, 32:425--443, 1969.
28. S. J. T. University. Suvnet-trace data. http://wirelesslab.sjtu.edu.cn/download.html, 2007.
29. D. J. Watts and S. H. Strogatz. Collective dynamics of 'small-world' networks. Nature, 393:440--442, June 1998.
30. H. Wu, R. Fujimoto, R. Guensler, and M. Hunter. Mddv: a mobility-centric data dissemination algorithm for vehicular networks. In Proceedings of the 1st ACM international workshop on Vehicular ad hoc networks, VANET '04, pages 47--56, New York, NY, USA, 2004. ACM.
31. J. Yuan, Y. Zheng, L. Zhang, X. Xie, and G. Sun. Where to find my next passenger. In Proceedings of the 13th international conference on Ubiquitous computing, UbiComp '11, pages 109--118, New York, NY, USA, 2011. ACM.
32. D. Zhang, N. Li, Z.-H. Zhou, C. Chen, L. Sun, and S. Li. ibat: detecting anomalous taxi trajectories from gps traces. In Proceedings of the 13th international conference on Ubiquitous computing, UbiComp '11, pages 99--108, New York, NY, USA, 2011. ACM.
33. Y. Zheng, Y. Liu, J. Yuan, and X. Xie. Urban computing with taxicabs. In Proceedings of the 13th international conference on Ubiquitous computing, UbiComp '11, pages 89--98, New York, NY, USA, 2011. ACM.
34. H. Zhu, M. Li, L. Fu, G. Xue, Y. Zhu, and L. M. Ni. Impact of traffic influxes: Revealing exponential intercontact time in urban vanets. IEEE Trans. Parallel Distrib. Syst., 22(8):1258--1266, Aug. 2011.
35. K. Zhu, P. Hui, Y. Chen, X. Fu, and W. Li. Exploring user social behaviors in mobile social applications. In the fourth workshop on Social Network Systems (SNS 2011), 2011.

Index Terms

• Applied computing

  • Law, social and behavioral sciences

    • Sociology

• Networks

  • Network properties

    • Network structure