This paper proposes different local\hyph search heuristics to improve the performance of geographical routing protocols in VANET networks, which typically relies the selection of the next node only on the best candidate. The presented algorithms are based on modifications of well-known metaheuristics such as simulated annealing, metropolis and tabu. We divided our heuristics according to their operation in forwarding and recovery algorithms. However, a simultaneous use of some of them is also possible to improve the overall performance of the system. Simulation results of the proposed implementation of tabu-search in our routing proposal show a promising increment in the packet delivery ratio.

Peer Reviewed