## 1 Introduction
### Related Works
In the proposed method the selection of gateway vehicles is based on set covering problem and it ensures optimality in the number of vehicles selected as gateways. [PERSON] et al. [23] designed a protocol named DWCM (Distributed and Weighted Clustering based on Mobility Metrics) based on the d-hop dominating set. Every vehicle exchanges the mobility information among its d-hop neighbors and calculates its priority based on the relative velocity and relative acceleration with its neighborhood vehicles. Each vehicle maintains two lists, one for holding mobility information of its d-hop neighbors from which it calculates its priority and the other for each d-hop neighbor the id of the maximum priority vehicle among its d-hop neighbors. The vehicle will act as a cluster head if it has the highest priority among its d-hop neighborhood or it has the highest priority among the d-hop neighborhood of its d-hop neighbors. The vehicle will act as a cluster gateway if it can hear from more than one cluster head. This gateway selection has the problem of choosing multiple gateways between the same two cluster heads, which is addressed in the proposed scheme by selecting a minimum number of gateways based on set covering. [PERSON] et al. [27] developed a fully distributed, reliable broadcasting protocol named ABSM, an Acknowledged Broadcast from Static to Highly Mobile. It combines Connected Dominating Set (CDS) concept with a Neighbor Elimination Scheme (NES). Each vehicle based on the current network topology information calculates CDS and determines whether it belongs to it or not. Upon receipt of a message for the first time, the vehicle initializes two lists: a list R, containing the list of neighbors that are believed to be received that message, and a list N, containing the list of neighbors that are in need of the message. Then the vehicle sets a waiting timeout period. The vehicles that belong to CDS select a shorter timeout period compared to those that do not belong to CDS. During the timeout period, it monitors the message retransmissions from other neighbors and updates the R and N lists. After the timeout expires if the N list is non-empty, then it retransmits the message otherwise it cancels the retransmission of the message. This protocol also suffers from high message overhead in keeping track of the R and N lists. [PERSON] et al. [11] designed a protocol named SRB (Selective Reliable Broadcast) an opportunistic broadcast protocol in which the source vehicle selects the next forwarder based on the distance. The clusters are detected based on the distance between each pair of vehicles which are less than a threshold value. The source vehicle elects the furthest vehicle inside each cluster detected as the cluster head and the cluster heads will become the source vehicle for the next contention phase. Since the cluster formation is based only on distance, due to differing speed between vehicles the duration of connectivity among vehicles in the same cluster suffers from frequent disconnections. In our proposed technique the cluster formation is based on distance as well as the relative speed of the neighboring vehicles. [PERSON] et al. [12] designed a protocol named VMaSC-LTE (Vehicular Multihop algorithm for Stable Clustering-Long Term Evolution(4G)) which is a hybrid protocol that combines IEEE 802.11p and the 4G cellular system technologies for achieving high packet delivery ratio and low latency. The cluster head selection is based on the relative speed of the neighboring vehicles. A vehicle is allowed to join the cluster head directly (1-hop) or indirectly (multi-hop) through the neighboring vehicle that is already a member of the cluster in order to reduce the connection overhead. [PERSON] et al. [13] proposed a new protocol named CRB (cluster-based recursive routing) where the accident vehicle which is the source of the emergency message, initially acts cluster head and selects the farthest cluster member based on the ACK message received from the receivers of that message.