It is very difficult to develop an efficient protocol for message broadcast in vehicular ad-hoc network that supports communication between vehicles and road side units with minimum delay, minimum overhead and maximum reachability. In this paper we show that if we study graph theoretic characteristics of VANETs because they don’t follow scale free and small world network properties, we can improve message broadcast in VANETs. We study urban and highway VANETs graph scenario for different capacities and different network densities. We study properties of graph like average shortest path length, node degree distribution, clustering coefficient and connectivity. For different parameters we develop separate analytical model for both urban and highways VANETs and study VANETs from graph structure point of view. After that we observe that clustering coefficient do not depend upon network density and network size. We study the impact of network density on connectivity and also study VANETs node degree distribution. We then show how this information can be used to reduce overhead in urban vehicular broadcasting protocol (UVCAST) with no major reduction in performance of existing protocol.

Connectivity, Node Degree, Vehicular Adhoc Networks, Routing Protocols

[1] Amit Dua, Neeraj Kumar and Seema Bawa, “Systematic review of vanet routing protocols” Elsevier vehicular communications pages 33-52, 2014.
[2] Costa, P., Frey, D., Migliavacca, M., & Mottola, L. (2006). Towards lightweight information dissemination in inter-vehicular networks. In ACM workshop on vehicular ad-hoc networks (VANET), pp. 20–29.
[3] Romeu Monteiro, Wantanee Viriyasitavat, Susana Sargento,Ozan K. Tonguz,” A graph structure approach to improving message dissemination in vehicular networks” Springer Science+Business Media New York 2016.
[4] Ros, F.J., Ruiz, P.M., & Stojmenovic, I. (2009). Reliable and efficient broadcasting in vehicular ad-hoc networks. In IEEE vehicular technology conference (VTC), April.
[5] Viriyasitavat, W., Bai, F., & Tonguz, O. (2010). UV-CAST: An urban vehicular broadcast protocol. In Proceedings of the IEEE vehicular networking conference (VNC), December, pp. 25–32.
[6] Busanelli, S., Ferrari, G., & Panichpapiboon, S. (2009). Efficient broadcasting in IEEE 802.11 networks through irresponsible forwarding. In Proceedings of IEEE ‘‘GLOBECOM’’.
[7] Panichpapiboon, S., & Cheng, L. (2013). Irresponsible forwarding under real inter-vehicle spacing distribution. IEEE Transactions on Vehicular Technology, 62, 2264–2272.
[8] Mostafa, A., Vegni, A. M., & Agrawal, D. P. (2014). A probabilistic routing by using multi-hop retransmission forecast with packet collisionaware constraints in vehicular networks. Ad Hoc Networks, 14, 118–129.
[9] Watts, D. J., & Strotgatz, S. H. (1998). Collective dynamics of ‘small-world’ networks. Nature, 393, 440–442.
[10] Zhang, H., & Li, J. (2015). Topology analysis of VANET based on complex network. In LISS. Springer, Heidelberg, Berlin.
[11] Tonguz, O. K., Viriyasitavat, W., & Bai, F. (2009). Modeling urban traffic: A cellular automata approach. IEEE Communications Magazine, Topics in Automotive Networking, 47(5), 142–150. May.
[12] Berkeley Highway Lab (BHL). http://sprocket.ccit.berkeley.edu/bhl.
[13] X. F. Wang and G. Chen, "Complext Networks: Small-World, Scale-Free and Beyond," in IEEE Circuits and Systems Magazine, First Quarter 2003.
[14] S. H. Strotgatz, "Exploring complex networks," Nature, Vol. 410 (8 March 2010).
[15]A. Barabási and R. Albert, "Emergence of Scaling in Random Networks," Science, vol. 286, October 1999.
[16] N. Garg, S.Singla and S.Jangra, “Challenges and Techniques for Testing of Big” published in the Journal, “Procedia Computer Science (Elsevier)”, 85 (2016), Pg. 940-948, DOI:10.1016/j.procs.2016.05.285, ISSN: 1877-0509.
[17] Ritesh Gupta and Parimal Patel, “An Improved Performance of Greedy Perimeter Stateless Routing protocol of Vehicular Adhoc Network in Urban Realistic Scenarios” published inInternational Journal of Scientific Research in Computer Science, Engineering and Information Technology Volume 1, Issue 1,ISSN : 2456-3307, 2016.
[18] Lubdha M. Bendale, Roshani. L. Jain and Gayatri D. Patil, “Study of Various Routing Protocols in Mobile Ad-Hoc Networks” published in International Journal of Scientific Research in Network Security and Communication Vol.06 , Special Issue.01 , pp.1-5, Jan-2018.