Reliable And Efficient Cluster-based Routing Schemes For Vehicular Ad-hoc Networks(VANETs)

In the absence of an efficient routing scheme,vehicles may not be able to exchange information and will lose all the advantages offered by advanced vehicular ad-hoc networks（VANETs）technology.Routing scalability,stability,reliability,and latency are prominent issues due to high mobility and large-sized networks.Cluster-based routing schemes aim to improve the scalability and reduce the computational cost.However,high relative-speed,frequent topological changes,broadcast storm（due to high traffic density）,network disconnection（due to low traffic density）,and VANETs communication patterns（V2V,V2I,V2P,and V2X）inflict many new challenges to the stability of cluster-based routing scheme.In this thesis,the aforementioned issues are addressed properly by introducing cluster-based routing schemes based on V2V and cellular C-V2X technologies.Firstly,a novel Triple Cluster-based Routing Protocol（TCRP）is proposed,aiming at dividing the highway traffic scenario into three optimal clusters.In TCRP,the cluster formation is performed with modified K-means algorithm using inter-vehicle distances and vehicles‘speed（Truncated Normal Distribution）.The dynamic algorithm（Floyd-Warshall）calculates the shortest distance for all pair of vehicles and selects cluster head（CH）based on two metrics,i.e.,smallest average distance and least variance in speed.From simulation results,it is concluded that the proposed TCRP forms consistent clusters and avoid frequent reselection of CH in further rounds,thus forming quite stable groups of vehicles.Moreover,this thesis also proposed another Cluster-based VANET-oriented Evolving Graph（CVo EG）model by extending the existing Vo EG model to improve the reliability of vehicular communications.The proposed CVo EG model used link reliability as a metric for cluster formation and CH selection.Since TCRP divides the network into pre-defined number of clusters,which is inappropriate in evolving networks.Therefore,CVo EG cope the problem by dividing the VANETs into optimal number of cluster（ONC）using eigen-gap heuristic.Based on the CVo EG model,a reliable routing scheme CEG-RAODV is proposed to find the most reliable journey（MRJ）from source to destination.Our simulation results show that the proposed scheme significantly outperforms than existing schemes in terms of reliability,reliable routing request（RRR）,packet delivery ratio（PDR）,end-to-end（E2E）delay,and throughput.The first two contributions were based on pure V2V communications,which causesa broadcast storm and network disconnection issues.To address these concerns,a Multi-hop Moving Zone（MMZ）clustering scheme is proposed by combining IEEE 802.11p with the3^rdGeneration Partnership Project（3GPP）5G cellular technology.The proposed MMZ reduces the excessive cellular hand-off cost by three hops clustering using V2V communications based on IEEE 802.11p.The zonal heads（ZHs）,i.e.,cluster heads（CHs）are selected by cellular-V2X（C-V2X）using multi-metrics,i.e.,relative speed,distance,and link lifetime（LLT）.The simulation results using ns3 show that,5G wide range technology significantly improves the stability of MMZ in term of ZH/CH duration and change rate.The average Data Packet Delivery Ratio（DPDR）and E2E latency are also improved as compared to existing clustering schemes.Next,a new mobility metric Generalized Speed Factor（GSF）is proposed for CH selection criterion.The GSF defines an actual relationship between the inter-vehicle spacing and the relative speed of consecutive vehicles.The vehicle connectivity in three different mobile environments based on GSF is analyzed,i.e.,temporal static connectivity,low mobility connectivity,and high mobility connectivity.The proposed network connectivity metric is also extended to the best route selecting metric for the Most Strongly Connected（MSC）route.Simulation results show that,a congested network is strongly connected as compare to sparse VANET.Furthermore,a two-level clustering scheme is proposed for efficient data dissemination utilizing GSF metric.Where level-1 cluster heads（L1CHs）are selected by a Fuzzy logic algorithm using three factors,i.e.,relative velocity factor,k-connectivity factor（GSF）,and link reliability factor.However,level-2 cluster heads（L2CHs）are selected by an improved Q-learning aiming to reduce the number of iterations in the gateway selection to LTE base station.Simulation results demonstrate that the proposed clustering scheme and GSF metric significantly improve the reliability,latency,stability,and scalability of VANETs in different environments.Lastly,this thesis proposed a clustering scheme for bus relayed VANET,where the selection of an optimal route and forwarding relay-bus is addressed.First,a multipath routing scheme using two metrics,i.e.,the probability of street consistency（PSC）and the probability of path consistency（PPC）is proposed to improve the performance of routing in term of load balancing.Secondly,to improve the selection of bus forwarding probability,a novel primary relay bus（PRB）selection mechanism is introduced by Ant Colony Optimization（ACO）-based clustering.The PRB aims to transmit packets to the next forwarding relay or destination.Here,the link reliability is used as a metric for PRB selection.The adaptation of clustering in the ACO algorithm enhanced the PRB selection process by decreasing the computational cost,end-to-end delay,and unnecessary beacon messages.Simulation results show that the employment of multipath and clustering significantly improved the performance of bus relayed VANET.