An evolving graph-based reliable routing scheme for VANETs

Abstract

Vehicular ad hoc networks (VANETs) are a special form of wireless networks made by vehicles communicating among themselves on roads. The conventional routing protocols proposed for mobile ad hoc networks (MANETs) work poorly in VANETs. As communication links break more frequently in VANETs than MANETs, the routing reliability of such highly dynamic networks needs to be paid special attention. To date very little research has focused on the routing reliability of VANETs on highways. In this paper, we use evolving graph theory to model the VANET communication graph on a highway. The extended evolving graph helps to capture the evolving characteristics of the vehicular network topology and determines the reliable routes preemptively. This research is the first to propose an evolving graph-based reliable routing scheme for VANETs to facilitate Quality of Service (QoS) support in the routing process. A new algorithm is developed to find the most reliable route in the VANET evolving graph from the source to the destination. We demonstrate through the simulation results that our proposed scheme outperforms significantly the related protocols in the literature.