International Journal of Computer Networks and Applications

Open Access Open Access  Restricted Access Subscription Access

A Comparative Study on Efficient Path Finding Algorithms for Route Planning in Smart Vehicular Networks


Affiliations
1 School of Computer Science and Engineering, Lovely Professional University, Punjab, India
2 Department of Computer Science and Information Technology, La Trobe University, Victoria, Australia
 

With the rise in the economy and population of various developing and developed nations leads to an increase in the number of vehicles on the road to manifolds recently. In the smart vehicular networks, there are numerous vehicle transportation problems (VTP) exists. The main or the most common problem is the congestion occurrence due to traffic jams and road accidents, especially in urban areas. So route planning to find the optimal route for a vehicle that is moving from source to destination is an important and challenging task as the route conditions change with the traffic conditions, hence the shortest and optimal route needs to be re-evaluated. This manuscript presents a study and comparison of various pathfinding algorithms which include Dijkstra, A Star, CH, and Floyd Warshall algorithms which are available as optimal route finding algorithms. The simulation of working algorithms with comparison has been performed using SUMO with TRACI and using python coding. The simulation is performed on real maps of urban areas. The parameters used for the comparative study are travel time, distance travelled, and speeds of vehicles.

Keywords

Smart Vehicular Networks, Guidance Systems, Vehicle Transportation Problem, Routing Algorithms.
User
Notifications
Font Size

  • Rafsanjani, Marjan Kuchaki, Hamideh Fatemidokht, Valentina Emilia Balas, and Ranbir Singh Batth. "An Anomaly Detection System Based on Clustering and Fuzzy Set Theory in VANETs." In International Workshop Soft Computing Applications, pp. 399-407. Springer, Cham, 2018.

  • Conti, M., Boldrini, C., Kanhere, S. S., Mingozzi, E., Pagani, E., Ruiz, P. M., & Younis, M. (2015). From MANET to people-centric networking: Milestones and open research challenges. Computer Communications, 71, 1-21.

  • M.iZhou,i"InternetiofiThings:iRecentiadvancesiandiapplications",iProceedingsiofithei2013iIEEEi17thiInternationaliConferenceioniComputeriSupportediCooperativeiWorkiiniDesigni(CSCWD), i2013. I

  • L.iAtzori,iA.iIeraiandiG.iMorabito,i"Introduction,"iTheiInternetiofiThings:iAisurvey,iComputeriNetworks,ivol.i54,ino.i15,ipp.i2787-i2788, 2010.i

  • G. Owojaiye and Y. Sun, “Focal design issues affecting the deployment of wireless sensor networks for intelligent transport systems,” IET Intelligent Transport Systems, vol. 6, no. 4, pp. 421–432, 2012.

  • S. Wang, S. Djahel, Z. Zhang, and J. Mcmanis, “Next Road Rerouting: A Multiagent System for Mitigating Unexpected Urban Traffic Congestion,” IEEE Transactions on Intelligent Transportation Systems, vol. 17, no. 10, pp. 2888–2899, 2016.

  • S. G. Manyam, S. Rathinam, S. Darbha, D. Casbeer, and P. Chandler, “Routing of two Unmanned Aerial Vehicles with communication constraints,” 2014 International Conference on Unmanned Aircraft Systems (ICUAS), 2014.

  • N. Akhtar, S. C. Ergen, and O. Ozkasap, “Vehicle Mobility and Communication Channel Models for Realistic and Efficient Highway VANET Simulation,” IEEE Transactions on Vehicular Technology, vol. 64, no. 1, pp. 248–262, 2015.

  • Shahi, G. S., Batth, R. S., & Egerton, S. (2020). MRGM: An Adaptive Mechanism for Congestion Control in Smart Vehicular Network. International Journal of Communication Networks and Information Security, 12(2), 273-280.

  • A. Nayar, R. S. Batth, D. B. Ha, and G. Sussendran, G. “Opportunistic networks: Present scenario-A mirror review”InternationalJournal of Communication Networks and Information Security,” 10 (1), pp. 223-241, 2018.

  • R. S. Batth, M. Gupta, K. S. Mann, S. Verma, and A. Malhotra, “Comparative Study of TDMA-Based MAC Protocols in VANET: A Mirror Review,” Advances in Intelligent Systems and Computing International Conference on Innovative Computing and Communications, pp. 107–123, 2019.

  • Chabini, Ismail, and Shan Lan. ”Adaptations of the A* algorithm for the computation of fastest paths in deterministic discrete-time dynamic networks.” Intelligent Transportation Systems, IEEE Transactions on 3.1 (2002): 60-74

  • Bell, M. G., Trozzi, V., Hosseinloo, S. H., Gentile, G., & Fonzone, A. (2012). Time-dependent Hyperstar algorithm for robust vehicle navigation. Transportation Research Part A: Policy and Practice, 46(5), 790-800.

  • P.Khan, G.Konar, &N.Chakraborty (2014). Modification of Floyd-Warshall's algorithm for Shortest Path routing in wireless sensor networks.2014 Annual IEEE India Conference (INDICON). doi:10.1109/indicon.2014.7030504

  • Hamrioui, Sofiane, Camil Adam Mohamed Hamrioui, Jaime Lioret, and Pascal Lorenz. "Smart and self-organised routing algorithm for efficient IoT communications in smart cities." IET Wireless Sensor Systems 8, no. 6 (2018): 305-312.

  • Zahedi, Khalid, Yasser Zahedi, and Abdul Samad Ismail. "CJBR: connected junction-based routing protocol for city scenarios of VANETs." Telecommunication Systems 72, no. 4 (2019): 567-578.

  • Haider, Shahab, Ghulam Abbas, ZiaulHaq Abbas, and Thar Baker. "DABFS: A robust routing protocol for warning messages dissemination in VANETs." Computer Communications 147 (2019): 21-34.

  • Ye, Mao, Lin Guan, and Mohammed Quddus. "MPBRP-Mobility Prediction Based Routing Protocol in VANETs." In CommNet, pp. 1-7. 2019.

  • R. H. Jhaveri, N. M. Patel, Y. Zhong, & A. K. Sangaiah, “Sensitivity analysis of an attack-pattern discovery based trusted routing scheme for mobile ad-hoc networks in industrial IoT,” IEEE Access, vol. 6, pp. 20085-20103, 2018.

  • J. Zhang, J. Yin, T. Xu, Z. Gao, , H. Qi, & H. Yin, “The optimal game model of energy consumption for nodes cooperation in WSN. Journal of Ambient Intelligence and Humanized Computing, pp. 1-11, 2018.

  • Sunita, &D.Garg, (2018). DynamizingDijkstra: “A solution to dynamic shortest path problem through retroactive priority queue”. Journal of King Saud University - Computer and Information Sciences. doi:10.1016/j.jksuci.2018.03.003.

  • Huang, Bo, Q.Wu, and F. B. Zhan. ”A shortest path algorithm with novel heuristics for dynamic transportation networks.” International Journal of Geographical Information Science 21.6 (2007): 625-644.

  • Koenig, Sven, Maxim Likhachev, and David Furcy. ”Lifelong planningA*.”Artificial Intelligence 155.1 (2004): 93-146.

  • Ramadiani, D.Bukhori, Azainil, &N.Dengen, (2018). Floyd-warshall algorithm to determine the shortest path based on android. IOP Conference Series: Earth and Environmental Science,144, 012019. doi:10.1088/1755-1315/144/1/012019.

  • R. Singh and K. S. Mann, “Improved TDMA Protocol for Channel Sensing in Vehicular Ad Hoc Network Using Time Lay,” Proceedings of 2nd International Conference on Communication, Computing and Networking Lecture Notes in Networks and Systems, pp. 303–311, 2018.

  • Fu, Liping, D. Sun, and Laurence R. Rilett. ”Heuristic shortest path algorithms for transportation applications: state of the art.” Computers & Operations Research 33.11 (2006): 3324-3343.


Abstract Views: 468

PDF Views: 0




  • A Comparative Study on Efficient Path Finding Algorithms for Route Planning in Smart Vehicular Networks

Abstract Views: 468  |  PDF Views: 0

Authors

Gurpreet Singh Shahi
School of Computer Science and Engineering, Lovely Professional University, Punjab, India
Ranbir Singh Batth
School of Computer Science and Engineering, Lovely Professional University, Punjab, India
Simon Egerton
Department of Computer Science and Information Technology, La Trobe University, Victoria, Australia

Abstract


With the rise in the economy and population of various developing and developed nations leads to an increase in the number of vehicles on the road to manifolds recently. In the smart vehicular networks, there are numerous vehicle transportation problems (VTP) exists. The main or the most common problem is the congestion occurrence due to traffic jams and road accidents, especially in urban areas. So route planning to find the optimal route for a vehicle that is moving from source to destination is an important and challenging task as the route conditions change with the traffic conditions, hence the shortest and optimal route needs to be re-evaluated. This manuscript presents a study and comparison of various pathfinding algorithms which include Dijkstra, A Star, CH, and Floyd Warshall algorithms which are available as optimal route finding algorithms. The simulation of working algorithms with comparison has been performed using SUMO with TRACI and using python coding. The simulation is performed on real maps of urban areas. The parameters used for the comparative study are travel time, distance travelled, and speeds of vehicles.

Keywords


Smart Vehicular Networks, Guidance Systems, Vehicle Transportation Problem, Routing Algorithms.

References





DOI: https://doi.org/10.22247/ijcna%2F2020%2F204020