A Heuristic Route Planning Scheme in Scalable VANET-Oriented Evolving Grid Graph (S-VoEGG)

Clustering is an excellent solution to divide the network into manageable groups to reduce the excessive overhead. However, the number of clusters can lead to MAC contention (in dense clusters) and network disconnection (in sparse clusters) problems. This paper proposes a heuristic and scalable route planning scheme for traffic congestion avoidance and optimal data communications. The contributions are two-fold: (i) Heuristic Street Planning Scheme (H-SPS) and (ii) Heuristic Scalable Reliable Ad hoc on Demand Distance Vector (HS-RAODV). H-SPS utilizes A-Star ( <tex-math notation="LaTeX">A^*</tex-math> ) for traffic control, outperforming the conventional Dijkstra algorithm regarding street discovery time and overhead. HS-RAODV, an extension of CEG-RAODV, introduces scalability and <tex-math notation="LaTeX">A^*</tex-math> as the route planning algorithm. It operates in linear mode (A*-RAODV) for sparse VANETs, discovering reliable routes without forming extra clusters. In congested VANETs, clustering mode (CA*-RAODV) leverages spectral clustering for optimal grouping. Compared to previous schemes, the proposed protocol achieves superior performance in route reliability, discovery messages, packet delivery ratio, end-to-end delay, throughput, and route scalability.