Routing in VANET’s City Scenario using Back-bone Node Hop Greedy Algorithm

  IJETT-book-cover  International Journal of Engineering Trends and Technology (IJETT)
© 2014 by IJETT Journal
Volume-15 Number-9
Year of Publication : 2014
Authors : S. B. Kulkarni , U. P. Kulkarni , Sunil Begumpur


S. B. Kulkarni , U. P. Kulkarni , Sunil Begumpur. "Routing in VANET’s City Scenario using Back-bone Node Hop Greedy Algorithm", International Journal of Engineering Trends and Technology (IJETT), V15(9),466-476 Sep 2014. ISSN:2231-5381. published by seventh sense research group


Using advanced WLAN technologies; vehicular ad hoc networks (VANETs) have become useful and valuable for their wide variety of unique applications, such as safety on roads, multimedia content sharing, etc. VANETs are constrained by the high mobility of vehicles and the frequent connectivity problems. Destination positions can be found using flooding in most of the protocols in city environments. Further, in the case of sparse and void regions, recovery strategies are used which increases hop count. The minimum weighted algorithm based on distance or connectivity to select intermediate intersections are adopted in some geographic routing protocols. However, the shortest path or the path with higher connectivity may include numerous intermediate intersections. The path with higher hop counts has maximum hop counts. In this paper, we hereby propose a hop greedy routing scheme that yields a routing path with the minimum number of intermediate intersection nodes while taking connectivity into consideration. Moreover, we introduce back-bone nodes that play a key role in providing connectivity status around an intersection. Apart from this, by tracking the movement of source as well as destination, the back-bone nodes enable a packet to be forwarded in the changed direction. Simulation result shows the benefits of the proposed routing strategy in terms of high packet delivery ratio, low packet failure ratio and shorter end-to-end delay.


[1] J. Bernsern and D. Manivannan, “Unicast routing protocols for vehicular ad hoc networks: A critical comparison and classification,” Pervasive Mob. Comput., vol. 5, no. 1, pp. 1–18, Feb. 2009.
[2] Q. Yang, A. Lim, S. Li, J. Fang, and P. Agrawal, “ACAR: Adaptive connectivity aware routing for vehicular ad hoc networks in city scenarios,” Mob. Netw. Appl., vol. 15, no. 1, pp. 36–60, Feb. 2010.
[3] V. Naumov and T. R. Gross, “Connectivity-aware routing (CAR) in vehicular ad hoc networks,” in Proc. IEEE INFOCOMM, 2007, pp. 1919–1927.
[4] C. Lochert, H. Hartenstein, J. Tian, H. Füßler, D. Hermann, and M. Mauve, “A routing strategy for vehicular ad hoc networks in city environments,” in Proc. IEEE Intell. Veh. Symp., 2003, pp. 156–161.
[5] B. Karp and H. T. Kung, “GPSR: Greedy perimeter stateless routing for wireless networks,” in Proc. ACM MOBICOM, 2000, pp. 243–254.
[6] C. Lochert, M. Mauve, H. Füßler, and H. Hartenstein, “Geographic routing in city scenarios,” ACM SIGMOBILE Mobile Comput. Commun. Rev., vol. 9, no. 1, pp. 69–72, Jan. 2005.
[7] H. Menouar, M. Lenardi, and F. Filali, “Movement prediction-based routing (MOPR) concept for position-based routing in vehicular networks,” in Proc IEEE VTC, 2007, pp. 2101–2105.
[8] G. Liu, B. S. Lee, B. C. Seet, C. H. Foh, K. J. Wong, and K. K. Lee, “A routing strategy for metropolis vehicular communications,” in Proc. ICOIN, LNCS, Aug. 2004, pp. 134–143.
[9] C. C. Hung, H. Chan, and E. H. K. Wu, “Mobility pattern aware routing for heterogeneous vehicular networks,” in Proc. IEEE WCNC, 2008, pp. 2200–2205.
[10] K. C. Lee, J. Häerri, U. Lee, and M. Gerla, “Enhanced perimeter routing for geographic forwarding protocols in urban vehicular scenarios,” in Proc. IEEE GlobeCom Workshops, 2007, pp. 1–10.
[11] W. Kieß, H. Füßler, and J. Widmer, “Hierarchical location service for mobile ad-hoc networks,” ACM SIGMOBILE Mob. Comput. Commun. Rev., vol. 8, no. 4, pp. 47–58, Oct. 2004.
[12] M. Käsemann, H. Füßler, H. Hartenstein, and M. Mauve, “A reactive location service for mobile ad hoc networks,” Dept. Comput. Sci., Univ. Mannheim, Mannheim, Germany, Tech. Rep. TR-14-2002, Nov. 2002.
[13] X. Jiang and T. Camp, “An efficient location server for an ad hoc networks,” Colorado School Mines, Golden, CO, Tech. Rep., MCS-03-06, May 2003.
[14] J. Li, J. Jannotti, D. S. J. De Couto, D. R. Karger, and R. Morris, “Ascalable location service for geographic ad hoc routing,” in Proc. ACM MOBICOM, 2000, pp. 120–130.
[15] J. Zhao and G. Cao, “VADD: Vehicle-assisted data delivery in vehicular ad hoc networks,” IEEE Trans. Veh. Technol., vol. 57, no. 3, pp. 1910– 1922, May 2008.
[16] D. B. Johnson, D. A. Maltz, and J. Broch, “DSR: The dynamic source routing protocol for multi-hop wireless ad hoc networks,” in Ad Hoc Networking, C. E. Perkins, Ed. Reading, MA: Addison-Wesley, 2001, ch. 5.
[17] C. E. Perkins and E. M. Royer, “Ad-hoc on-demand distance vector routing,” in Proc. 2nd IEEE Workshop Mob. Comput. Syst. Appl., 1999, pp. 90–100.
[18] H. Menouar, M. Lenardi, and F. Filali, “Improving proactive routing in VANETs with the MOPR movement prediction framework,” in Proc. ITST, 2007, pp. 1–6.
[19] H. Menouar, M. Lenardi, and F. Filali, “A movement prediction-based routing protocol for vehicle-to-vehicle communications,” in Proc. 1st Int. V2VCOM, San Diego, CA, Jul. 2005.
[20] S. Y. Ni, Y. C. Tseng, Y. S. Chen, and J. P. Sheu, “The broadcast storm problem in a mobile ad hoc network,” in Proc. ACM/IEEE MOBICOM, 1999, pp. 151–162.
[21] Y. Ding, C. Wang, and L. Xiao, “A static-node assisted adaptive routing protocol in vehicular networks,” in Proc. ACM VANET, 2007, pp. 59–68.
[22] H. Füßler, M. Mauve, H. Hartenstein, and D. Vollmer, “A comparison of routing strategies for vehicular ad-hoc networks,” Dept. Comput. Sci., Univ. Mannheim,Mannheim, Germany, Tech. Rep. TR-02-003, Jul. 2002.
[23] The Network Simulator-ns-2. [Online]. Available: nsnam/ns/
[24] M. Jerbi, S. M. Senouci, T. Rasheed, and Y. Ghamri-Doudane, “Towards efficient geographic routing in urban vehicular networks,” IEEE Trans. Veh. Technol., vol. 58, no. 9, pp. 5048–5059, Nov. 2009.
[25] P. K. Sahu, E. H. Wu, J. Sahoo, and M. Gerla, “DDOR: Destination discovery oriented routing in highway/freeway VANETs,” in Springer Telecommun. Syst.––Special Issue Vehicular Communications, Networks, Applications, 2010, pp. 1–18.
[26] U. Lee, J. Lee, J. S. Park, and M. Gerla, “FleaNet: A virtual market place on vehicular networks,” IEEE Trans. Veh. Technol., vol. 59, no. 1, pp. 344–355, Jan. 2010.
[27] The CitySense Sensor Network Project. [Online]. Available: [28] J. Nzouonta, N. Rajgure, G. Wang, and C. Borcea, “VANET routing on city roads using real-time vehicular traffic information,” IEEE Trans. Veh. Technol., vol. 58, no. 7, pp. 3609–3626, Sep. 2008.
[29] T. H. Cormen, C. E. Leiserson, R. L. Rivest, and C. Stein, “Section 24.3: Dijkstra’s algorithm,” in Introduction to Algorithms, 2nd ed. Cambridge, MA: MIT Press, 2001, pp. 595–601.
[30] N.Wisitpongphan, F. Bai, P. Mudalige, V. Sadekar, and O. Tonguz, “Routing in sparse vehicular ad hoc wireless networks,” IEEE J. Sel. Areas Commun., vol. 25, no. 8, pp. 1538–1556, Oct. 2007.
[31] M. M. Artimy, W. Robertson, and W. J. Phillips, “Connectivity in inter-vehicle ad hoc networks,” in Proc. IEEE CCECE, May 2004, pp. 293–298.
[32] Q. Song and X. Wang, “Efficient routing on large road networks using hierarchical communities,” IEEE Trans. Intell. Transp. Syst., vol. 12, no. 1, pp. 132–140, Mar. 2011.
[33] Z. C. Taysi and A. G. Yavuz, “Routing protocols for GeoNet: A survey,” IEEE Trans. Intell. Transp. Syst., vol. 13, no. 2, pp. 939–954, Jun. 2012.

Back-bone Assisted Hop Greedy (BAHG), Destination discovery, greedy routing, unicast routing, Vehicular ad hoc network (VANET).