Applying Connected Dominating Set to Broadcasting in Vehicular Ad Hoc Networks

This paper proposes a Connected Dominating Set (CDS) based clustering algorithm to prevent the broadcast storm problem in Vehicular Ad-hoc Networks (VANETs). The proposed algorithm accounts for the mobility and degrees of vehicles, and matches the highly dynamic nature of VANETs. VANETs are infrastructure less multihop wireless networks. Routing in VANETs is a one of the challenging task to accomplish. Broadcasting is a typical message dissemination mechanism for various VANETs applications such as emergency notifications, traffic information, notice and advertisement messages, etc. Even though VANETs have no physical backbone, a virtual backbone can be constructed by finding a CDS in the network graph. Clustering using a CDS-based virtual backbone can help in improving network scalability. Therefore CDS-based broadcasting can prevent the broadcast storm problem in VANETs.