International Journal of Interactive Mobile Technologies(iJIM) – eISSN: 1865-7923 – Vol 16 No 10 (2022) Paper—Clustering Review in Vehicular Ad hoc Networks: Algorithms, Comparisons, Challenges and… Clustering Review in Vehicular Ad hoc Networks: Algorithms, Comparisons, Challenges and Solutions https://doi.org/10.3991/ijim.v16i10.29973 Mays Kareem Jabbar1,2(), Hafedh Trabelsi1 1CES_Lab, ENIS, Sfax University, Sfax, Tunisia 2Faculty of Engineering, University of Misan, Misan Province, Iraq m_mays85@uomisan.edu.iq Abstract—The Vehicular Ad-hoc Network (VANET) represents a new future for dynamic information dissemination between societies. VANET has a wide range of applications in a variety of aspects, including Intelligent Transportation Systems (ITS). VANET has some characteristics, like highly dynamic topology and intermittent connections. These characteristics lead to untrustworthy infor- mation transmission in VANET. Vehicle clustering is an efficient approach to improve the scalability of the network and connection reliability. The perfor- mance of the clustering is also affected by VANET characteristics. This article provides a comprehensive description of VANET clustering algorithms. The most notable clustering algorithms introduced between 2010 and 2021 are reviewed. A complete survey on clustering in VANETs is provided based upon the cluster- ing process. The clustering process in most algorithms is explored in the aspects of CH selection metrics, cluster formation, and cluster maintenance. The cluster- ing techniques based on some parameters like stability, convergence, overhead, and latency are compared. Some of the most common problems, as well as the approaches employed to solve them, are also discussed. Also, the performance parameters which evaluate the clustering approaches are summarized. Keywords—VANET, clustering algorithms, performance parameters 1 Introduction An important next-generation transportation technology is the Intelligent Transpor- tation System (ITS), which includes all types of vehicle communications. ITS provides a variety of services to passengers including driving assistance, safety applications, emergency warnings, congestion control, and so on [1]. A VANET is a self-organizing network made up of moving vehicles. Because of the expanding number of applica- tions aimed at passenger safety, VANET is garnering a lot of interest from wireless network manufacturers and academics. VANET is a subset of Mobile Ad Hoc Network iJIM ‒ Vol. 16, No. 10, 2022 25 https://doi.org/10.3991/ijim.v16i10.29973 mailto:m_mays85@uomisan.edu.iq Paper—Clustering Review in Vehicular Ad hoc Networks: Algorithms, Comparisons, Challenges and… (MANET). MANET is a network of mobile nodes connected via wireless communi- cation that does not have a fixed infrastructure and is self-configuring. The network becomes a VANET when the mobile nodes in MANETs are exchanged by cars and then begin to follow fixed routes, like roads. The major advantage of VANET is to provide congestion control and road safety to the vehicles by making communication among them to share the information. The average speed and mobility of nodes in VANET are quite high, resulting in a rapid change in the network structure; these are its distinguish- ing features [2]. In the early 1990s, people began to pay greater attention to VANET technologies, and it has grown in importance in subsequent years. VANET’s components are; Road side units (RSUs) and On-Board Units (OBUs). The RSUs are put alongside the road, and saved all information of the vehicle then forwarded to other OBUs. RSUs have complete control over the transmission of infor- mation jobs in OBUs or vehicles. Moreover, OBUs are devices that are installed in dynamic vehicles to facilitate information sharing between the cars and RSUs. Vehicle to Vehicle (V2V) and Vehicle to Infrastructure (V2I) communication are the two types of VANET communications. In V2V communications, Vehicles equipped with OBUs can communicate directly with each other inside their radio ranges, whereas V2I communication, as well as the deployment of infrastructure along roadsides and the various applications that can increase the quality of service provided by infrastruc- tures to vehicles. V2V and V2I can be included as Vehicle to X (V2X) communications. It is the communications between vehicles and communications between vehicles and other terminals, such as RSUs [3], [4]. A Dedicated Short-Range Communication (DSRC) is a communications system designed specifically for use in automobiles. It is proposed for transmission informa- tion and communication among vehicles with a transition range of 100 to 1000m [3]. The DSRC system works in a similar way to how Wi-Fi works. The Federal Commu- nication Commission (FCC) of the United States has assigned a higher spectrum band with a range of 75 MHz [5], [6]. Both V2V and V2I communications are supported by DSRC. 26 http://www.i-jim.org Paper—Clustering Review in Vehicular Ad hoc Networks: Algorithms, Comparisons, Challenges and… Fig. 1. Vehicular communications types [6] Vehicle safety, traffic management, and accurate vehicle information communica- tion are the main functions of VANET. The topology of VANET is dynamic and can be anticipated using GPS because of the high speed of vehicles. In order to supply ad hoc connectivity in VANET, a wireless communication facility equips in the vehicles. Scalability issues are caused by the dynamic nature of the VANET. In VANET architec- ture, data distribution requires an effective and efficient routing strategy. The VANET environment is evolving to provide vehicle safety and security [7], [8]. Cluster stabil- ity is important for the VANET’s reliability and scalability, as it guarantees minimal intra- and inter-cluster communication, lowering the overhead associated with these issues [6]. To achieve the best information of communication in VANET, the most recent clustering algorithms are described. We also concentrate on VANET’s intelli- gent clustering algorithms. This leads us to explore different clustering strategies. This study is an extended survey for the previous study which has introduced in [6]. The main contributions of this work; firstly, we provide an overview of the development iJIM ‒ Vol. 16, No. 10, 2022 27 Paper—Clustering Review in Vehicular Ad hoc Networks: Algorithms, Comparisons, Challenges and… of clustering algorithms in VANETs from 2010 to 2022, which have been observed and studied. Also, most of these algorithms have never been summarized in previous research. Secondly, the existing clustering techniques are summarized and classified in terms of clustering procedure: CH selection, cluster formation, and cluster maintenance, and then we compare these algorithms using different key parameters. Thirdly, different challenges are introduced and the techniques used to solve them. Finally, a compre- hensive analysis of the most common parameters used for evaluating the performance of clustering algorithms is introduced. The performance parameters are cluster perfor- mance parameters and network performance parameters. Also, simulation tools of each clustering algorithm are presented. The following is our study’s structure: Section 2 focuses on VANET clustering, including its algorithms, history, and process, followed by a comparison of clustering algorithms based on some key parameters. Section 3 discusses various problems and the clustering approaches utilized to resolve them, as well as each cluster technique performance. In Section 4, we describe the performance evaluation parameters for some clustering techniques. The survey’s conclusion and our future work are reported in Section 5. 2 Clustering in VANET Clustering is a common VANET technology that offers an appealing approach for simplifying and optimizing network functions and services. When compared to the traditional flat structure, it has dramatically improved performance in a variety of appli- cations. Clustering is a technique for organizing network nodes into small groupings called clusters. Typically, vehicles in close proximity are grouped together in a cluster based on various key parameters and metrics. The vehicles present in the cluster are known as [9]: 1. Cluster Head (CH) – This is the node that is the coordinator or head of the cluster. The CH is selected according to different criteria and its main task is allowing cluster members to communicate and share information with other members and CHs. 2. Cluster Member (CM) – The remaining nodes in the cluster are the CMs. These nodes exchange information by broadcasting messages to each other. 3. Gateway Node (GW) – This node helps to communicate with RSU, it does not need to present it to every cluster. Figure 2 illustrates the VANET’s cluster-based communication structure. Internal cluster communication is handled entirely by the CH. There are two specific rout- ings that divide a cluster internal communication; intra-cluster communication and inter-cluster communication. The cluster’s stability is increased during cluster mainte- nance by forecasting node-to-node failure links [6]. 28 http://www.i-jim.org Paper—Clustering Review in Vehicular Ad hoc Networks: Algorithms, Comparisons, Challenges and… Fig. 2. The cluster architecture [10] 2.1 VANETs clustering algorithms history In the early 1990s, the clustering techniques for VANETs began to be developed and have expanded in recent years. Researchers discovered that prior clustering algorithms in MANETs were no longer appropriate for VANETs due to their predictable mobility and specified route topology. Additional control overheads may be imposed due to the time it takes to complete the clustering phases. As a result, a good clustering method should construct a small number of clusters and dynamically maintain the cluster structure without creating sig- nificant network overhead. Furthermore, to avoid wasteful cluster re-formations, an effective cluster maintenance plan is required. Some clustering algorithms of MANETs were introduced to fit the specific characteristics of vehicular communications such as Mobility Based Clustering (MOBIC) in [11], Weighted Clustering Algorithm (WCA) in [12], and Distributed and Mobility Adaptive Clustering (DMAC) in [13]. Also, most of the VANET clustering algorithms were derived from the previous MANETs. Several clustering techniques for VANETs have been proposed, particularly after 2010 as a result of the expansion and development of the VANET. In Table 1, several VANET clustering algorithms and the number of citations for each algorithm are highlighted, which have been presented from 2010 to 2022. We can note that the Passive Multi-hop Clustering (PMC) in [14] has the highest mean citations. iJIM ‒ Vol. 16, No. 10, 2022 29 Paper—Clustering Review in Vehicular Ad hoc Networks: Algorithms, Comparisons, Challenges and… Table 1. Clustering algorithms citations Reference Year Algorithm Abbreviations Citation Mean [15] 2010 Aggregate Local Mobility ALM 127 10.6 [16] 2010 Cluster-Based Directional Routing Protocol CBDRP 68 5.7 [17] 2010 Proposed in [17] – 104 8.6 [18] 2011 Vehicular clustering based on the Weighted Clustering Algorithm VWCA 141 12.8 [19] 2012 Distributed Medium Access Control DMMAC 7 0.7 [20] 2012 Fuzzy Logic Based clustering Algorithm FLBA 78 7.8 [21] 2012 Trust dependent Ant Colony Routing TACR 49 4.9 [22] 2012 Threshold Based algorithm TB 119 11.9 [23] 2012 Mobility-Aware Clustering Algorithm based on Destination positions AMACAD 74 7.4 [24] 2012 Spring-Clustering SP-Cl 53 5.3 [25] 2012 Stability-Based Clustering Algorithm SBCA 57 5.7 [26] 2013 Agent Learning–based Algorithm ALCA 77 8.6 [27] 2014 Adaptive K-Harmonic Means AKHM 21 2.6 [28] 2015 Aggregate Relative Velocity ARV 31 4.4 [29] 2015 Distributed Multi-hop Clustering based on Neighborhood Follow DMCNF 94 13.4 [30] 2015 Adaptive Weighted Clustering Protocol AWCP 54 7.7 [31] 2015 Neighbor Mobility-Based Clustering Scheme NMCS 11 1.6 [32] 2015 Direction based clustering and multi- channel medium access control DA-CMAC 11 1.6 [33] 2016 Vehicular Multi-hop algorithm for Stable Clustering-LTE VMaSC-LTE 255 42.5 [34] 2016 Neighbor stability-based VANET clustering algorithm NSVC 24 4 [35] 2016 MObility-aware and SIngle-hop Clustering scheme MOSIC 10 1.7 [36] 2016 New Clustering Algorithm Based on Agent Technology NCABAT 9 1.5 [37] 2016 Clustering-Based VANET Routing algorithm Protocol CBVRP 28 4.7 [38] 2018 Proposed [38] – 12 3 [39] 2018 Deep Reinforcement Learning DRL 17 4.25 [40] 2018 Unified Framework of Clustering approach UFC 62 15.5 [14] 2018 Passive Multi-hop Clustering PMC 180 45 [41] 2018 Link Reliability-based Clustering Algorithm LRCA 29 7.25 [42] 2018 Proposed in [42] – 33 8.25 [43] 2018 Proposed in [43] – 26 6.5 (Continued) 30 http://www.i-jim.org Paper—Clustering Review in Vehicular Ad hoc Networks: Algorithms, Comparisons, Challenges and… Reference Year Algorithm Abbreviations Citation Mean [44] 2019 Enhanced Weight-based Clustering Algorithm EWCA 16 5.3 [45] 2019 Center-Based Clustering algorithm CBSC 35 11.6 [46] 2019 Hybrid Clustering Algorithm based on Roadside HCAR 16 5.3 [47] 2019 Double-Head Clustering DHC 36 12 [48] 2019 Proposed in [48] – 1 0.33 [49] 2019 Enhanced Distributed Channel Access EDCA 6 2 [50] 2019 Probabilistic-Direction-Aware Cooperative Collision Avoidance P-DACCA 13 4.3 [51] 2019 Fuzzy-based Cluster Management Scheme FCMS 23 7.7 [52] 2019 Mobility Based Clustering Algorithm MBCA 2 0.7 [53] 2020 Naive Bayes Prediction Scheme NBP 1 0.5 [54] 2021 Junction-based Clustering for VANET JCV 0 0 [55] 2022 Proposed in [55] – 3 3 [56] 2022 Region-based Collaborative Management Scheme RCMS 0 0 2.2 Clustering process in VANETs The cluster establishment in the VANET communication process is the most import- ant part. There are two phases to complete this process: • First phase- (Cluster Generation): cluster formation process and CH selection process; during this phase, nodes send advertisement messages to pick the primary CH and CM, and subsequently regular data packets are transmitted between them. In order to create a stable cluster, there may be a few techniques added between the advertisement message transmission and CH selection. • Second phase- (Cluster Maintenance): Stable cluster merging, selection of second- ary CH, re-clustering, and cluster splitting occur at this phase. Some researchers in the literature had discussed these phases separately. This section provides an overview of the algorithms and criteria used in each clustering step, includ- ing CH selection, cluster formation according to the hop count, and cluster maintenance. Cluster generation phase. This phase goes through two processes to complete the generated of clusters; the cluster formation process and the CH selection process. Some clustering algorithms elect the CHs first, on the basis of which the clusters are formed to complete the clustering process and others vice versa. Cluster head selection. The network’s robustness and scalability are strongly influenced by CH stability. The stable CH guarantees that intra- and inter-cluster communications are kept. To improve VANET stability, a reliable vehicle only can be a CH. The researchers considered various parameters for selecting the CH, such as received signal strength, relative speed, position, direction, and link lifetime. Many clustering approaches are relying on a combination of multiple metrics rather than a Table 1. Clustering algorithms citations (Continued) iJIM ‒ Vol. 16, No. 10, 2022 31 Paper—Clustering Review in Vehicular Ad hoc Networks: Algorithms, Comparisons, Challenges and… single metric for selecting the CH, like DHC in [47], CBSC in [45], TCAR in [21], AWCP in [30], and EWCA in [44]. Some of these algorithms and their metrics used for CH selection are tabulated in Table 2: Table 2. CH selection metrics Reference Algorithm CH Selection Metric [15] ALM Priorities associated with each vehicle [16] CBDRP Moving direction [18] VWCA Distrust Level, Degree, Velocity, Direction [19] DMMAC Speed and direction based [20] FLBA Relative velocity [21] TACR Relative velocity, packet forwarding reputation [22] TB Distance, Relative velocity [23] AMACAD Destination, Distance, Relative velocity [24] SP-Cl Relative velocity, distance [25] SBCA Relative Speed, RSS [26] ALCA Velocity [27] AKHM Transmission bandwidth [28] ARV Relative velocity [29] DMCNF The propagation delay ratio, Number of the following car [30] AWCP Highway ID, direction, position, speed [31] NMCS Change in degree [33] VMaSC-LTE Lowest average speed [34] NSVC Rate of change of the number of neighbors [35] MOSIC Relative speed, Relative distance, and Relative mobility [36] NCABAT Lowest ID [38] Proposed in [38] Speed, Position [39] DRL Q-learning based routing [40] UFC UFC relative position, relative velocity, and link lifetime [14] PMC Speed, Neighbors, Link lifetime, Position [41] LRCA link reliability [42] Proposed in [42] Mobility, direction, degree, and reputation [44] EWCA Speed, Position [45] CBSC Position, Relative Speed [46] HCAR Lowest ID [47] DHC Signal Strength, Relative Speed, Link Lifetime [48] Proposed in [48] Trust, relative speed, and position [54] JCV Relative position, movement at the junction, degree of a node, and time. [55] Proposed in [55] Using PSO mechanism. [56] RCMS Using SRP model and feature relevance between vehicles 32 http://www.i-jim.org Paper—Clustering Review in Vehicular Ad hoc Networks: Algorithms, Comparisons, Challenges and… Cluster formation. Cluster formation in VANET has various types and categories: center-based vs. distributed-based, single-hop vs. multi-hop, location service-based vs. user information-based, etc. This section discusses cluster formation on the basis of topology. This means a cluster structure in VANETs can be modeled according to a hop distance that separates the CH and its members, transmission range, and cluster radius. Accordingly, only two main categories of algorithms are distinguished: single-hop and multi-hop algorithms as in Figure 3. Fig. 3. Clustering model [10] 1. Single-hop Clustering Algorithm It is the algorithm that creates clusters with a single-hop distance between each node and its CH. That means every node connects directly with the CH [55]. Many clustering algorithms form directly single-hop clusters based on the transmission range of the CH or the limited cluster radius. Some of the single-hop clustering algorithms are: In [18], the VWCA was proposed. It is a single-hop clustering algorithm, and it improves the security, connectivity, and stability performance. The connectivity can be increased using the adaptive transmission range algorithm (AART) which is based on detected short-range communication standards. The AART helps to extend the trans- mission range dynamically from 100m to 1000m based on the vehicles’ density. Another single-hop clustering algorithm for VANETs was proposed in [23], it is called an AMACAD. Speed distance and position are the parameters used to elect the CH. The stability of the CH in VANET was enhanced by designing a SBCA [25]. This algorithm is provided a more stable structure according to vehicle mobility and a num- ber of neighbors. The cluster formation procedure does not take the vehicle’s direction into account, which has an impact on the VANET system’s performance. In [31], the authors proposed a novel single-hop clustering algorithm for VANET named NMCS. The vehicle which has the lowest “neighbor vehicles mobility” value is selected as a CH. This algorithm provides reliable network topology. MOSIC was proposed in [35]. Gauss Markov mobility (GMM) model is used by this proposed for mobility prediction that makes vehicle able to prognosticate its mobility relative to its neighbors. iJIM ‒ Vol. 16, No. 10, 2022 33 Paper—Clustering Review in Vehicular Ad hoc Networks: Algorithms, Comparisons, Challenges and… NCABAT was introduced in [36]. The objective of this algorithm is to describe agent properties to vehicles with the purpose of improving traditional schemes in terms of performance. Creating a stable cluster is the main goal of a distributed system-based passive data dissemination technique [38] that can overcome the VANET’s communication delay. The message is efficiently transmitted using the passive cluster formation approach. LRCA was proposed in [41] to grant reliable and efficient data transmission in urban VANET. LLT-based neighbor sampling scheme is used to select a group of vehicles with stable neighbor vehicles. In this proposed, the routing approach is prepared to sup- port infotainment services in VANET which are not strict in delay constraints. In [42], a new single-hop clustering scheme was presented that elects trustworthy CHs based on a hybrid approach combining trust factors and stability. Also, this research proposed a new adaptive trust function to assess the data trust between nodes according to the reported event’s requirement in terms of trust severity, unlike other schemes which use a static trust function. The proposed scheme increases the reliability of sharing data compared with other recently proposed. In [44], the authors proposed EWCA which is a single-hop clustering algorithm. In an emergency message transmission case, this technique reduces the formation of unstable clusters and enhances the clustering stability. CBSC was proposed in [45] to help self-organized VANETs form stable clusters and decrease the status change frequency of vehicles on highways and two metrics. Also, a new CH selection algorithm was presented to minimize the impact of vehicle motion differences. In this proposed, two metrics are introduced to enhance VANETs security. In [46], HCAR is a Hybrid Clustering Algorithm. It was designed on the basis of the RSUs for the Internet of Vehicles (IoV), and it is a single-hop clustering algorithm. The distributed RSUs are where the HCAR algorithm is centralized. After the RSUs have been controlled, a graph theory-based approach is used to form the clusters. The selection of secondary CH resolves the unavailability problem of CH. This proposed enhanced the stability of CH. DHC algorithm for VANET was proposed in [47] with a focus on rising clusters stability and reducing the number of clusters in the network under different conditions and scenarios. The proposed scheme performed better than other algorithms in terms of efficiency and cluster stability, under different channel models, vehicles density, and traffic scenarios, especially in dynamic mobility environments. In [54], the authors suggested a robust and dynamic mobility-based clustering approach JCV. It takes into account the moving direction at the next junction in the cluster formation process. This technique provided high stability, preventing clusters from breaking at the junction frequently. Single-hop clustering algorithms provide more reliable intra-cluster communication and highly effective coordination to CHs. The coverage area of this type of cluster is small, which leads to high maintenance overhead and a large number of clusters. Also, in single-hop clustering algorithms, when the density of vehicles is very high, collisions can occur and can lead to a low packets delivery ratio. Also, when the density of vehicles is low, the vehicle may not find any member and stay single, so it cannot form a cluster. These two situations should be avoided because the cluster performance will be decreased. We can summarize that the single-hop algorithms provide good 34 http://www.i-jim.org Paper—Clustering Review in Vehicular Ad hoc Networks: Algorithms, Comparisons, Challenges and… cluster stability and low latency, but clustering coverage requires further improvement. Also, to solve the problem of high and low density, the maximum and the minimum number of vehicles can be limited in a cluster. 2. Multi-hop Clustering Algorithm Clusters are generated with multi-hop distance, where every node is at a distance of at most multi-hop from its CH. Some multi-hop clustering algorithms are presented in this section. In [29], DMCNF was proposed; it allows vehicles to periodically select their tar- gets from one-hop neighbors in a distributed manner. The CH selected depends on the relationship of neighborhood among vehicles. This algorithm improves the cluster’s stability. A hybrid backbone-based clustering algorithm was proposed in [15], also, it is a multi-hop clustering algorithm. The concept of a number of links and vehicular mobil- ity are used for cluster formation and CH selection. During cluster formation, nodes with a relatively higher degree of connectivity initially form a backbone that is desig- nated as leadership. The leadership then participates in CH election and efficient cluster re-organization using an aggregate relative velocity of vehicles in the leadership. A multi-hop clustering approach was also presented in [22] called TB with the goal of maximizing the stability of the network topology and decreasing network dynamics. The speed difference among vehicles as well as the position and the direction were taken into account in this proposed during the cluster formation process. This algorithm increases CH lifetime and minimizes vehicle transition between clusters. The multi-hop clustering algorithm was introduced in [33]. It is called VMaSC- LTE, and it is based on the amalgamation of a 4G cellular system with IEEE 802.11p to improve the VANET communication performance. The multi-hop technique ensures that CH selection and clustering are both stable. With the decrease in CH, the stability improves. An AWCP was introduced by taking into account the speed information, direction, position, and highway ID to select the most stable vehicles among current vehicles to operate as CHs [30]. To maximize cluster structure stability, highway ID informa- tion is used. This technique improves cluster lifetime and minimizes communication overhead. PMC algorithm in VANET was proposed in [14] to solve the lack in clustering algo- rithms performance in terms of stability and reliability. In this algorithm, the clustering is introduced depending on the priority neighbor following strategy, and the CH select- ing technique is adopted to select the optimal CH. In [48], the author introduced a heuristic algorithm for electing a vehicle as a CH in a cluster. In this method, weighted fitness values are used for electing a CH vehicle based on three parameters; trust value, absolute relative average speed, and position from the cluster boundary. Multi-hop clustering algorithms can reduce the number of clusters; expand clus- ter coverage area, and enhance cluster stability. We can summarize that the multi-hop algorithms provide high clustering coverage, and good cluster stability, especially with regard to the number of CM re-affiliation, CH changes, and cluster lifetime. However, multi-hop cluster formation is more complex, which will take a long cluster formation iJIM ‒ Vol. 16, No. 10, 2022 35 Paper—Clustering Review in Vehicular Ad hoc Networks: Algorithms, Comparisons, Challenges and… time, and this may cause a delay in transmitting the information. Also, the cluster over- head requires more improvement. Also, according to some simulation results, the cluster performance degrades when the number of hops is more than three. This means when the hop count increases the cluster performance will decrease. A comparison between the clustering algorithms is shown in Table 3 in terms of transmission range, vehicle density, vehicle velocity, hop count, and traffic scenario. Table 3. Clustering algorithms comparison Algorithm Transmission Range Vehicle Density Vehicle Velocity Hop Count Traffic Scenario EWCA 300m 50–150 30m/s Single Highway Proposed in [38] 300m 80–510 5.5–33.3m/s Single Highway VWCA Dynamic 100–1000m 10–350 19–33.3m/s Single Highway UFC 300m 200 10–35m/s Single Highway FLBA 200m 0.05–0.4/m 22–33.3m/s Single Highway NMCS – – – Single – AMACAD 100–200m 50 11–31 m/s Single Urban SBCA 300m 50–150 25–35m/s Single Highway CBSC – – 55.55m/s Single Highway HCAR 100m–300m 100 10–40m/s Single Highway MOSIC 200m 100 10–35m/s Single Highway LRCA 200, 500m 1500 10–30m/s Single Urban DHC 300m 50–200 13.830m/s Single Highway, urban NCABAT 150m 60 – Single Random Proposed in [42] – 10–60 10–120m/s Single Highway JCV 200m 100 10–35m/s Single Highway DMAC – 30–200 2, 5, 10m/s Multi Random ALM – 50–1000 10–30m/s Multi Highway DMCNF 100–300m 100 10–35m/s Multi Highway DMMAC 200m 100–800 22–33.3m/s Multi Highway VMaSC-LTE 200m 100 10–35m/s Multi Highway Sp-Cl 80m, 125m 20–150 22–44m/s Multi Highway TB 150–300m, 800, 1000m 400 19, 25, 30m/s Multi Highway AWCP 1000m 25–200 33.3–41.6m/s Multi Highway PMC 100–300m 100 10–35m/s Multi Random CBDRP – 60 25–35m/s Multi Highway Proposed in [48] 600m 200 11m/s Multi Urban Proposed in [55] – 100 20–60m/s Multi Urban RCMS 250m 1200 10–30m/s Multi Urban 36 http://www.i-jim.org Paper—Clustering Review in Vehicular Ad hoc Networks: Algorithms, Comparisons, Challenges and… Cluster maintenance. Because of VANETs dynamic topology, severe packet loss occurs due to frequent vehicle re-connection and disconnection. The cluster maintenance process ensures strong connectivity by reducing frequent vehicle re-clustering and also achieves a stable link lifetime through CH. Cluster maintenance involves vehicle joining, vehicle leaving, cluster merging, and other cluster maintenance methods. There are a lot of maintenance methods introduced in the literature; we discuss some of them in this section. In vehicle joining and vehicle leaving process, the CH sends frequent signals and if it receives any signal from a vehicle, this new vehicle is assigned to that cluster and becomes CM of that particular cluster. Then the CH will update its local database. When the CH loses the connection with a member vehicle, the information for that member is deleted from the CH’s local database. AWCP in [30], and DMCNF in [29] are an example of the algorithms which used this method. The second method is the cluster merging process; it is more complex than the first one. Cluster merging takes place when two or more clusters can be represented by a single merged cluster, which can minimize the clusters’ number and improve the clus- tering efficiency. The conditions of the cluster merging are different for each algorithm. For example, in the ALM algorithm [15], cluster merging occurs if two CHs are in each other’s transmission range. The VMaSC-LTE in [33], the averaged relative speed of the two neighboring CHs, referred to as AVGREL-SPEED, is compared. The CH with the higher average relative speed relinquishes his CH job and becomes a CM for the CH with the lower average relative speed. Also, the PMC algorithm in [14] used the cluster merging method in the cluster maintenance phase, the CH node sends merge request packets to other neighboring CH to request cluster merging. If one of these two CHs has smaller following vehicles and high relative speed, the merging process is performed. Other algorithms addressed the two processes (cluster merging and vehicle leaving or joining) in the cluster maintenance phase like TB [22], SP-CI in [24], DA-CMAC in [32], LRCA in [41], UFC in [40], and JCV in [54]. A selected of secondary CH is another approach used in the cluster maintenance phase. Some algorithms like EWCA proposed in [44], SBCA in [25], CBRDP in [16], and HCAR in [46] used this method. The secondary CH is selected by the CH accord- ing to different criteria. It resolves the unavailability of CH to increase the clustering stability. Some algorithms used another cluster maintenance method; like Deep Reinforce- ment Learning (DRL) scheme in [39]. This scheme was designed for VANET and enhanced the safety and the QoS in the transmission of data. Q-learning tables deter- mine the best route for data transfer. In the maintenance phase, the performance can be improved in terms of predicting connection failure and reducing overhead delays by updating Q-learning tables. While in [20], the maintenance phase in the FLBA algo- rithm is adjustable to drivers’ behavior on the way and has a learning technique for predicting the future position and speed of all CMs using fuzzy logic inference system. iJIM ‒ Vol. 16, No. 10, 2022 37 Paper—Clustering Review in Vehicular Ad hoc Networks: Algorithms, Comparisons, Challenges and… 2.3 Clustering algorithms comparison Various parameters are typically used to compare clustering techniques. These parameters are used to generate and characterize any clustering algorithm [6]. Cluster stability, latency, convergence, and overhead are some of these key parameters. The benchmark algorithms are compared in Table 4 based on these parameters. A good clus- tering algorithm achieves high stability and low latency, overhead, and convergence. Table 4. Clustering algorithms comparison Algorithm Cluster Stability Latency Overhead Convergence EWCA High Stability Low Latency High overhead Medium VWCA High Stability – – Low DRL – Low Latency Low overhead – AWCP Low Stability Medium Latency Low overhead Medium DMMAC High Stability Low Latency – High VMaSC-LTE High Stability Low latency High overhead Low ALM Low stability Low latency Low overhead Low UFC High stability – Low overhead – ALCA Improves stability High latency High overhead – FLBA High Stability – – – TACR Improves stability – Low overhead Low TB Improves stability – Low overhead High AMACAD Medium Stability High latency – Low DMCNF Improves Stability – Low overhead Low NMCS Improves Stability – – Low Sp-Cl Improves Stability – Low overhead Low SBCA Improves stability – Low overhead Low CBSC High Stability – – – PMC High stability Low Latency Low overhead Low CBDRP High stability Low Latency Low overhead High HCAR Improves stability High latency Low overhead Medium MOSIC Improves stability Low overhead High LRCA Improves Stability Low Latency Low overhead – DHC High stability – Low overhead Low NCABAT Low Stability Low Delay in High Density – – Proposed in [42] High Stability – Low overhead Low Proposed in [48] Improves stability Low latency Low overhead – JCV High stability Low latency Low overhead – RCMS High stability Low latency – High 38 http://www.i-jim.org Paper—Clustering Review in Vehicular Ad hoc Networks: Algorithms, Comparisons, Challenges and… 3 Challenges and techniques used for solution Many researches with several clustering algorithms are available in order to enhance the performance of the wireless network. The researchers have examined various issues and used various clustering algorithms to find solutions to them; in this section, we present some of these challenges as well as the approaches utilized to solve them as in Table 5. For cluster formation in VANET, a DMCNF algorithm in [29] solved the network weaknesses that occur as a result of a dynamic topology. For highways, a CBDRP in [16] solved the problem of fast data transmission and link connectivity. In order to increase the VANET’s stability in an urban area, a lane-based clustering algorithm was introduced in [17]. Clustering reduces the overhead and provides a hier- archical network topology that is efficient. The CH improves the network’s lifetime. The hybrid backbone-based clustering algorithm in VANET uses the aggregate rel- ative velocity to select the CH [28]. The nodes carry out an effective CH selection task with a minimum relative speed and high connection. In [37], for desert and rugged situations, a VANET-based clustering routing proto- col was introduced. The source and destination vehicles work to keep the stability of cluster architecture. The designed algorithm’s tasks are CH selection, cluster structure formation, and routing protocols. The overhead delay and cluster stability problems have been solved using the pas- sive approach in [38], also, the message is transmitted efficiently using this approach. In [32], For VANET, a DA-CMAC algorithm was implemented. The rearrangement cost for short-period connections is reduced using clustering. The CH manages the channel access and the time slots are assigned to the CM. Clustering the time slots into two groups depending on the direction of movement achieves the merging collision and channel access. To improve the MAC routing protocol, an EDCA was introduced [49]. A fixed con- trol channel interval (CCHI) and a variable CCHI are two problems of message trans- mission communication for safety. The EDCA scheme achieves optimal MAC routing parameters with priority given to the emergency message. In [43], to address the problem of network connectivity failure, an intelligent forwarding-based stable and reliable data dissemination approach was proposed. Vehi- cles choose the next forwarding node based on the mathematical formula that represents link stability. The data transfer is handled by the greedy approach, and a separate algo- rithm is used to beat the network connection failure. To recover the information con- nection’s break links, the edge weights are utilized. The behavior of driver prediction has an impact on the cluster’s stability in VANET. In [53], for efficient VANET clustering, machine learning based on a prediction of a driver behavior technique was proposed. The NBP algorithm estimates the behavior of the driver based on 2 factors: overtaking decisions and driving speed. The NBP clas- sifiers divide a driver’s habit into three categories: vehicle type, relative speed, and a number of traveled lanes. The VANET’s optimum driving model is intended to obtain a stable clustering. iJIM ‒ Vol. 16, No. 10, 2022 39 Paper—Clustering Review in Vehicular Ad hoc Networks: Algorithms, Comparisons, Challenges and… A major issue in VANET is Cooperative collision avoidance (CCA) which has an impact on cluster stability. In various two directions real traffic scenarios, a probabi- listic direction aware (PDA) algorithm was proposed to dominance CCA [50]. Cluster formation is handled using a modified k-medoids method that integrates the Hamming distance metric for direct knowledge. The distance and speed of nodes are used to calculate a collision’s probability between the vehicles. The benign factor is used to determine the vehicles’ optimal safe speed, which is compared to the threshold range and delivers a collision warning. The communication overhead and collision latency are decreased. One of the major issues in the VANET is security because of its impact on the per- formance of the network. It is done in [26] and [51]. The authors in [51] implemented a FCMS for detecting a reliable vehicle. For clustering in VANET, FCMS1 and FCMS2 models are compared. Three input factors are for FCMS1. Vehicle trustworthiness (VT) is the fourth input factors to the FCMS2 model. The FCMS2 model improves cluster stability over the FCMS1 model. In [52], the MBCA was used to solve the problem of multimedia broadcasting con- tent in a hybrid VANET topology. Cluster formation and CH selection are based on mobility measurements, which are utilized to determine the vehicles’ relative speed. The cluster’s stability is improved using the handshake process. Table 5. Problem and solution technique Reference Problem Techniques Used Performance [14] Lack in reliability and stability of clustering algorithms PMC approach Improve the performance in terms of in reliability and stability. [16] Rapid data transmission, link stability and realizing reliable CBDRP Reduces latency and increases the packet delivery ratio and link stability [17] Cluster stability A lane-based clustering algorithm Improves the stability by increasing the CH Lifetime [25] Vehicles frequently joint and leave the clusters. SBCA Improves the stability of the network by reducing the overhead and the cluster lifetime [29] Weakness in the network because of high dynamic Multi-hop clustering algorithm (DMCNF) Improves the stability [33] Delay and delivering of the safety messages problems. Hybrid architecture called VMaSC-LTE companies LTE and IEEE802.11P Achieves low delay and high packet delivery ratio [26] Security ALCA Performing fast clustering, increases efficiency. [28] Frequent CH changing Hybrid backbone based clustering algorithm Improves cluster stability by forming the cluster leadership [32] Short communication period DA-CMAC Reduces collision and increases reliability of packets (Continued) 40 http://www.i-jim.org Paper—Clustering Review in Vehicular Ad hoc Networks: Algorithms, Comparisons, Challenges and… Reference Problem Techniques Used Performance [34] Problem of delivering data in urban vehicular environments NSVC Guarantees the reliability of delivering emergency messages, increases clustering stability. [37] Route selection, stable clustering suitable for desert CBVRP Increases communication efficiency, delivers information with ensures reliability, and decreases the routing cost. [38] Cluster stability and Overhead delay. Passive data dissemination approach Improves cluster stability, reduces the communication overhead, and increases the efficiency of transmission messages. [41] Cluster stability Reliability-based clustering algorithm (LRCA) Provides efficient and reliable data transmission in VANETs [43] Failure in data delivery and communication Link Algorithm based on intelligent forwarding Minimizes delay, Improves cluster stability and communication Safety [44] CH Stability. EWCA A better cluster stability and overhead delay reduction performance [46] High mobility, big data clustering RSU based Multi-Hop Clustering Improves cluster stability, and proves the efficiency of the algorithm in theoretical way. [49] Transmission message delay EDCA for transmitting emergency message Reduces average delay and increases the probability of successful delivery [50] Clustering and cooperative collision avoidance P-DACCA with K-medoids and Bengn factors Reduces overhead delay, and collision Efficient stability [51] Security and trustworthiness detection FCMS1 and FCMS2 Efficient vehicles’ management in the cluster [53] Cluster stability, and behavior prediction of driver NBP clustering Increases cluster stability in real environments [52] Stability of Link MBCA Multimedia broadcasting has been improved. 4 Performance evaluation metrics Any clustering algorithm’s performance can be assessed and evaluated using a variety of parameters; Cluster performance and network performance are the most common metrics used for evaluating the performance of clustering algorithms: Table 5. Problem and solution technique (Continued) iJIM ‒ Vol. 16, No. 10, 2022 41 Paper—Clustering Review in Vehicular Ad hoc Networks: Algorithms, Comparisons, Challenges and… 4.1 Cluster performance parameters Cluster performance parameters represent how well clustering techniques perform and mirror how stable the network’s backbone nodes are. The overall cluster perfor- mance and stability are described using these parameters. Some of Cluster performance parameters are: • Cluster/CH Stability: It is the number of times the same vehicle is elected as a CH out of all times. • Cluster number: It refers to the number of clusters that form during network operation. The clustering algorithm is more efficient when there are few cluster numbers [6]. • Cluster/CH lifetime: It is the maximum time for a vehicle that has played the head’s task in a cluster. It is computed by dividing the overall lifetime by the time spent in the head’s role [57]. • CM lifetime: It is the maximum amount of time a node can be CM for. To get its average, we divide the total lifetime of the CM by the total number of state changes from CM to another state [57]. • CH change rate: It is the average CH’s number change per time [57]. • Cluster change rate: Average cluster’s number changes for each vehicle in a unit of time. • Cluster size: Vehicles’ number in one cluster. A good and stable clustering algorithm should have a large cluster size, high CH and CM lifetime, few cluster numbers, and low cluster and CH change rate. However, these parameters only can’t describe communication links’ details between vehicles in the network. 4.2 Network performance parameters The overall network performance is described by these parameters, which include: • Throughput: It is the number of bits transmitted per second in any network. The higher value of throughput provides better performance of the network designed [6]. • Packet loss ratio or collision ratio: The rate of packets’ loss during the transmission process. • Packet Delivery Ratio (PDR): It is the ratio of the number of packets received by the destination to the total number of packets [57]. • Overhead: The average number of control messages is received by the vehicle. • End to End Delay (E2E Delay) or Latency: It is the time taken for transmitting a packet from a source to a destination. All these parameters are utilized to estimate the context-based clustering approaches, like traffic prediction, routing, and information dissemination. A good and efficient clustering algorithm leads to large throughput, short E2E delay, low packet loss rate, high PDR, and small overhead. Table 6 presents the evaluated parameters and the sim- ulator tools used for each algorithm [58], [59], [60]. 42 http://www.i-jim.org Paper—Clustering Review in Vehicular Ad hoc Networks: Algorithms, Comparisons, Challenges and… Table 6. Clustering algorithms evaluation parameters Reference Algorithm Simulator Tool Evaluation Parameters [15] ALM SUMO, SIDE/ SMURPH CH lifetime, Status changes per Node, CH density. [16] CBDRP NS2 Latency, PDR, Average Routing Overhead [18] VWCA MATLAB CH and CM lifetime, PDR. [19] DMMAC SUMO, MOVE, NS2 Average cluster size, probability of received CH SMS, Probability of successful transmission, average travel time for an emergency SMS [20] FLBA NS2, MOVE, SUMO Average CH time, Average CM’s dwell time, Average cluster size. [21] TACR – Routing Overhead, CH Selection Time, Cluster Creation Time, and Probability of message Transmission. [22] TB C++ Average cluster change, Average cluster lifetime [23] AMACAD Java CH lifetime, Membership lifetime, Re-affiliation rate [24] Sp-Cl – Average cluster change, Number of clusters, and average cluster lifetime. [25] SBCA NS2 Average cluster lifetime, overhead, and packet delivery. [26] ALCA VANET MobiSim Node participation time, Throughput, Efficiency, CH duration, Connectivity ratio [27] AKHM C/C++ Clustering performance for crossroad scenario, Clustering performance for rectangle road scenario. [28] ARV SUMO Average Cluster-Head lifetime, Percentage of CHs. [29] DMCNF NS2, VanetMobiSim Average CH/CM durations, Average number of clusters, Average CH change number, and average overhead. [30] AWCP NS2, JOSM, SUMO, MOVE Average Cluster Lifetime, PDR, overhead. [32] DA-CMAC NS3 PDR, CH Changes, Access collision. [33] VMaSC- LTE NS3 & (SUMO) CH/CM Duration, CH Change Rate, Overhead, Number of Vehicles in SE state. [34] NSVC – CH lifetime, CH change, throughput. [35] MOSIC NS3 Average CH/CM Duration, Average Number of clusters, Average Control Message Overhead, Average CH Changes Rate. [36] NCABAT JADE Throughput, E2E Delay, and PDR. [37] CBVRP – PDR, E2E delay, Number of cluster reconstruction, Routing cost. [38] Proposed in [38] OMNET++, SUMO Overhead. [39] DRL QualNet7.1, VanetMobiSim Average E2E delay, and average PDR. (Continued) iJIM ‒ Vol. 16, No. 10, 2022 43 Paper—Clustering Review in Vehicular Ad hoc Networks: Algorithms, Comparisons, Challenges and… Reference Algorithm Simulator Tool Evaluation Parameters [40] UFC SUMO CH duration, CM duration, Clustering efficiency, Number of initial CHs, CM disconnection rate, CM re-clustering delay, and CM re-clustering success ratio. [14] PMC NS2, VanetMobiSim Average CH/CM Duration Time, Number of Average Cluster Head Changes, Clustering Overhead. [41] LRCA NS2, SUMO CH/CM duration, CH change rate, PDR,E2E delay, overhead [42] Proposed in [42] OMNET++, SUMO CH/CM duration, Overhead, CH selected time, PDR, Trust/Untrust packets delivery rate. [43] Proposed in [43] NS2, SUMO Latency, throughput, PDR. [44] EWCA NS2, SUMO Cluster stability, number of clusters, and E2E. [45] CBSC OMNeT++, SUMO Average CH/CM Lifetime, Average Number of Re-affiliation Times, Packet Loss Rate. [46] HCAR NS2, VANET MobiSim CH lifetime, average overhead, and number of cluster [47] DHC SUMO CH/CM lifetime, Number of changed states, packet overhead, Cluster formation rate, CH Alienation. [48] Proposed in [48] OMNET++, SUMO Throughput, Delay, No. of packets generated, PDR, No. of clusters [49] EDCA MATLAB Control channel interval, service channel interval. [50] P-DACCA NS2 Cluster stability, overhead, and collision probability. [51] FCMS1, FCMS2 – Vehicle speed, vehicle cluster, degree of centrality, and trustworthiness. [52] MBCA OMNET++, SUMO, and VIENS Average CH duration, average CM duration, PDR, network delay, and overhead. [53] NBP SUMO CH election, CM election, and lifetime of CH. [54] JCV SUMO, CVANETSIM, JAVA CH duration, CM duration, CH change rate, number of cluster, cluster participation, number of CM. number of EN, ratio of CM, EN duration, overhead, delay [55] Proposed in [55] NS2 PDR, Throughput. [56] RMCS OMNET++, SUMO Cluster lifetime, PDR, delay, overlap rate, reconstruction time 5 Conclusion and future work In recent years, VANETs have been used in a variety of applications. Vehicle safety, traffic management, and accurate vehicle information communication are the main functions of VANET. Due to the high speed of vehicles, the VANET topology is dynamic. Scalability issues are caused by the dynamic nature of the VANET and the clustering represents one of the reliable solutions. This work presented an intensive sur- vey for the most clustering techniques to solve different VANETs issues. We provided Table 6. Clustering algorithms evaluation parameters (Continued) 44 http://www.i-jim.org Paper—Clustering Review in Vehicular Ad hoc Networks: Algorithms, Comparisons, Challenges and… an overview of the clustering technique in VANETs. At first, a history of 51 cluster- ing algorithms for two decades with the number of their citations was highlighted. Then, we have introduced the algorithms and the criteria of each of the clustering steps, including the metrics used for selecting the CH for each algorithm, cluster formation according to the hop distance, and cluster maintenance. Also, to see the performance of these algorithms, we have made comparisons between them based on some key parameters. Then, we presented some of VANET’s challenges as well as the clustering approaches utilized to solve them and see the performance of these approaches. Finally, we introduced some of the most common metrics used for evaluating the performance of clustering algorithms. From our survey, we can see most clustering algorithms are designed for highways, and cluster stability is one of the major issues in VANET. In future work, we will design a new clustering algorithm for VANET suitable for urban environments using hyper- graph theory, and our approach will aim to increase the clustering stability. 6 References [1] J. Barrachina, J. A. Sanguesa, M. Fogue and P. Garrido, “V2X-d: A Vehicular Density Estimation System that Combines V2V and V2I Communications,” Nov 2013. https://doi. org/10.1109/WD.2013.6686518 [2] B. Marzak, H. Toumi and K. E. Guemmat, “A Survey on Routing Protocols for Vehicular Ad-Hoc Networks,” Indian Journal of Science and Technology, Dec 2016. https://doi. org/10.17485/ijst/2016/v9iS1/86524 [3] R. Naja, Wireless Vehicular Networks for Car Collision Avoidance, New York, 2013. https://doi.org/10.1007/978-1-4419-9563-6 [4] P. Panse, T. Shrimali and M. Dave, “An Approach for Preventing Accidents and Traffic Load Detection on Highways,” January 2016. [5] Y. Shi, “An Efficient Cluster-based Service Model for Vehicular Ad-Hoc Networks on Motorways,” Aston University, 2017. [6] M. K. J. Alsabah, H. Trabelsi and W. Jerbi, “Survey on Clustering in VANET Networks,” in 18th International Multi-Conference on Systems, Signals & Devices (SSD), Monastir, Tunisia, 2021. https://doi.org/10.1109/SSD52085.2021.9429353 [7] Venkatesh, A. Indra and R. Murali, “Routing Protocols for Vehicular Adhoc Networks (VANETs): A Review,” CIS Journal, January 2014. [8] K. N. Qureshi, H. Abdullah, F. Ullah and R. W. Anwar, “Vehicular Ad Hoc Networks Routing Protocols: Survey,” Sci. Int.(Lahore), November 2015. [9] P. Thakur and A. Ganpati, “A Comparative Study of Cluster-Head Selection Algorithms in VANET,” December 2019. [10] M. Mukhtaruzzaman and M. Atiquzzaman, “Clustering in VANET: Algorithms and Challenges,” Journal of Computers & Electrical Engineering, September 2020. [11] P. Basu, N. Khan and T. D. Little, “A Mobility Based Metric for Clustering in Mobile Ad Hoc Networks,” in international conference on distributed computing systems workshop, 2001. [12] M. Chatterjee, S. K. Das and D. Turgut, “WCA: A Weighted Clustering Algorithm for Mobile,” Cluster Computing, 5, pp. 193–204, 2002. https://doi.org/10.1023/A:1013941929408 [13] S. Basagni, “Distributed Clustering for Ad Hoc Networks,” 1999. [14] D. Zhang and Y.-Y. Cui, “New Multi-Hop Clustering Algorithm for Vehicular Ad Hoc Networks,” 2018. https://doi.org/10.1109/VTCFall.2019.8891285 iJIM ‒ Vol. 16, No. 10, 2022 45 https://doi.org/10.1109/WD.2013.6686518 https://doi.org/10.1109/WD.2013.6686518 https://doi.org/10.17485/ijst/2016/v9iS1/86524 https://doi.org/10.17485/ijst/2016/v9iS1/86524 https://doi.org/10.1007/978-1-4419-9563-6 https://doi.org/10.1109/SSD52085.2021.9429353 https://doi.org/10.1023/A:1013941929408 https://doi.org/10.1109/VTCFall.2019.8891285 Paper—Clustering Review in Vehicular Ad hoc Networks: Algorithms, Comparisons, Challenges and… [15] E. Souza, I. Nikolaidis and P. Gburzynski, “A New Aggregate Local Mobility (ALM) Clus- tering Algorithm for VANETs,” in Communications (ICC), 2010. https://doi.org/10.1109/ ICC.2010.5501789 [16] W. Xia, T. Song and L. Shen, “A Cluster-based Directional Routing Protocol in VANET,” in the 2010 12th IEEE International Conference on Communication Technology (ICCT), 2010. https://doi.org/10.1109/ICCT.2010.5689132 [17] M. S. Almalag and M. C. Weigle, “Using Traffic Flow for Cluster Formation in Vehicular Ad-hoc Networks.” [18] A. Daeinabi, A. G. Pour Rahbar and A. Khademzadeh, “VWCA: An Efficient Clustering Algorithm in Vehicular Ad Hoc Networks,” Journal of Network and Computer Applications, vol. 34, pp. 207–222, 2011. https://doi.org/10.1016/j.jnca.2010.07.016 [19] K. Hafeez, L. Zhao, Z. Liao and B. N.-W. Ma, “Reliability of Cluster-based Multichan- nel MAC Protocols in VANETs,” in IEEE International Conference, June 2012. https://doi. org/10.1109/ICC.2012.6363838 [20] K. Hafeez, L. Zhao, Z. Liao and B.-W. Ma, “A Fuzzy-logic-based Cluster Head Selection Algorithm in Vanets,” in Communications (ICC), 2012 IEEE International Conference on, 2012. https://doi.org/10.1109/ICC.2012.6363839 [21] R. Sahoo, R. Panda, D. Behera and M. Naskar, “A Trust Based Clustering with Ant Colony Routing in VANET,” in Computing CommunicationNetworking Technologies (ICCCNT), 2012. https://doi.org/10.1109/ICCCNT.2012.6395939 [22] Z. Y. Rawashdeh and S. Mahmud, “A Novel Algorithm to Form Stable Clusters in Vehicular Ad Hoc Networks on Highways,” 2012. https://doi.org/10.1186/1687-1499-2012-15 [23] M. Morales, E. J. Cho, C. S. Hong and S. Lee, “An Adaptable Mobility-aware Cluster- ing Algorithm in Vehicular Networks,” Journal of Computing Science and Engineering, Sep 2012. https://doi.org/10.1109/APNOMS.2011.6077004 [24] L. Maglaras and D. Katsaros, “Distributed Clustering in Vehicular Networks,” 2012. https:// doi.org/10.1109/WiMOB.2012.6379136 [25] A. Ahizoune and A. Hafid, “A New Stability Based Clustering Algorithm (SBCA) for VANETs,” October 2012. https://doi.org/10.1109/LCNW.2012.6424072 [26] N. Kumar, N. Chilamkurti and J. Park, “ALCA: Agent Learning-based Clustering Algorithm in Vehicular Ad Hoc Networks,” Personal and Ubiquitous Computing, 2013. https://doi. org/10.1007/s00779-012-0600-8 [27] R. Chai, X. Ge and Q. Chen, “Adaptive K-Harmonic Means Clustering Algorithm for VANETs,” September 2014. https://doi.org/10.1109/ISCIT.2014.7011907 [28] J. P. Singh and R. S. Bali, “A Hybrid Backbone Based Clustering Algorithm for Vehicu- lar Ad-Hoc Networks,” in International Conference on Information and Communication Technologies (ICICT 2014), 2015. https://doi.org/10.1016/j.procs.2015.01.011 [29] Y. Chen, M. Fang, S. Shi, W. Guo and X. Zheng, “Distributed Multihop Clustering Algorithm for VANETs Based on Neighborhood Follow,” 1999. [30] M. Hadded, R. Zagrouba, A. Laouiti, P. Muhlethaler and A. S. Leila, “A Multi-Objectif Genetic Algorithm-Based Adaptive Weighted Clustering Protocol in VANET,” 2015. https:// doi.org/10.1109/CEC.2015.7256998 [31] J.-H. Kwon, C. Kwon and E.-J. Kim, “Neighbor Mobility-based Clustering Scheme for Vehicular Ad Hoc Networks,” 2015. https://doi.org/10.1109/PlatCon.2015.19 [32] A. S. K. Mammu, U. Hernandez-Jayo and N. Sainz, “Direction Aware Cluster-Based Multi Channel MAC Protocol for Vehicular Ad Hoc Networks,” in 2015 IEEE 11th International Conference on Wireless and Mobile Computing, Networking and Communications (WiMob). https://doi.org/10.1109/WiMOB.2015.7348010 [33] S. Ucar, S. C. Ergen and O. Ozkasap, “VMaSC: Vehicular Multi-hop Algorithm for Stable Clustering in Vehicular Ad Hoc Networks,” in 2013 IEEE Wireless Communications and Net- working Conference (WCNC): NETWORKS. https://doi.org/10.1109/WCNC.2013.6554933 46 http://www.i-jim.org https://doi.org/10.1109/ICC.2010.5501789 https://doi.org/10.1109/ICC.2010.5501789 https://doi.org/10.1109/ICCT.2010.5689132 https://doi.org/10.1016/j.jnca.2010.07.016 https://doi.org/10.1109/ICC.2012.6363838 https://doi.org/10.1109/ICC.2012.6363838 https://doi.org/10.1109/ICC.2012.6363839 https://doi.org/10.1109/ICCCNT.2012.6395939 https://doi.org/10.1186/1687-1499-2012-15 https://doi.org/10.1109/APNOMS.2011.6077004 https://doi.org/10.1109/WiMOB.2012.6379136 https://doi.org/10.1109/WiMOB.2012.6379136 https://doi.org/10.1109/LCNW.2012.6424072 https://doi.org/10.1007/s00779-012-0600-8 https://doi.org/10.1007/s00779-012-0600-8 https://doi.org/10.1109/ISCIT.2014.7011907 https://doi.org/10.1016/j.procs.2015.01.011 https://doi.org/10.1109/CEC.2015.7256998 https://doi.org/10.1109/CEC.2015.7256998 https://doi.org/10.1109/PlatCon.2015.19 https://doi.org/10.1109/WiMOB.2015.7348010 https://doi.org/10.1109/WCNC.2013.6554933 Paper—Clustering Review in Vehicular Ad hoc Networks: Algorithms, Comparisons, Challenges and… [34] J. Kwon, H. Chang, T. Shon, J. Jung and E. Kim, “Neighbor Stability-based VANET Cluster- ing for Urban Vehicular Environments,” 2016. https://doi.org/10.1007/s11227-015-1517-6 [35] Amin Ziagham Ahwazi and MohammadReza NooriMehr, “MOSIC: Mobility-Aware Single-Hop Clustering Scheme for Vehicular Ad hoc Networks on Highways,” (IJACSA) International Journal of Advanced Computer Science and Applications, vol. 7, 2016. https://doi.org/10.14569/IJACSA.2016.070957 [36] Samira Harrabi, “A Novel Clustering Algorithm Based on Agent Technology for VANET,” Network Protocols and Algorithms, vol. 8, 2016. https://doi.org/10.5296/npa.v8i2.8434 [37] M. M. Mohammed Nasr, A. M. Salih Abdelgader, Z.-G. Wang and L.-F. Shen, “VANET Clustering Based Routing Protocol Suitable for Deserts,” 2016. https://doi.org/10.3390/ s16040478 [38] A. Touila and F. Ghadia, “Efficient Dissemination Based on Passive Approach and Dynamic Clustering for VANET,” 2018. https://doi.org/10.1016/j.procs.2018.01.134 [39] J. Wu, M. Fang and X. Li, “Reinforcement Learning Based Mobility Adaptive Routing for Vehicular Ad-Hoc Networks,” 2018. https://doi.org/10.1007/s11277-018-5809-z [40] M. Ren, J. Zhang, L. Khoukhi and H. Labiod, “A Unified Framework of Clustering Approach in Vehicular Ad Hoc Networks,” May 2018. https://doi.org/10.1109/TITS.2017.2727226 [41] X. Ji, H. Yu, G. Fan, H. Sun and L. Chen, “Efficient and Reliable Cluster-Based Data Transmis- sion for Vehicular Ad Hoc Networks,” Hindawi, 2018. https://doi.org/10.1155/2018/9826782 [42] S. Oubabas, R. Aoudjit, Joel J. P. C. Rodrigues and S. Talbi, “Secure and Stable Vehicular Ad Hoc Network Clustering Algorithm Based on Hybrid Mobility Similarities and Trust Management Scheme,” 2018. https://doi.org/10.1016/j.vehcom.2018.08.001 [43] M. Chahal and S. Harit, “A Stable and Reliable Data Dissemination Scheme Based on Intelligent Forwarding in VANETs,” October 2018. https://doi.org/10.1002/dac.3869 [44] A. Bello Tambawal, R. Md Noor, R. Salleh, C. Chembe and M. Oche, “Enhanced Weight- based Clustering Algorithm to Provide Reliable Delivery for VANET Safety Applications,” 4 April 2019. https://doi.org/10.1371/journal.pone.0214664 [45] X. Cheng and B. Huang, “A Center-Based Secure and Stable Clustering Algorithm for VANETs on Highways,” Hindawi Wireless Communications and Mobile Computing, 2019. https://doi.org/10.1155/2019/8415234 [46] O. Senouci, S. Harous and Z. Aliouat, “A New Heuristic Clustering Algorithm Based on RSU for Internet of Vehicles,” Arabian Journal for Science and Engineering, 2019. https:// doi.org/10.1007/s13369-019-03854-2 [47] Ghada H. Alsuhli, A. Khattab and Yasmine A. Fahmy, “Double-Head Clustering for Resil- ient VANETs,” Hindawi Wireless Communications and Mobile Computing, 2019. https:// doi.org/10.1155/2019/2917238 [48] M. A. Shahid, “Fixed Cluster Based Cluster Head Selection Algorithm in Vehicular Adhoc Network,” University of Windsor, 2019. [49] J. Choi and Y. Yi, “Joint Optimization of Message Transmissions with Adaptive Selection of CCH Interval in VANETs,” 2019. https://doi.org/10.1109/ACCESS.2019.2920002 [50] S. Haider, G. Abbas, Z. H. Abbas, S. Boudjit and Z. Halim, “P-DACCA: A Probabilistic Direction-Aware Cooperative Collision Avoidance Scheme for VANETs,” 2019. https://doi. org/10.1016/j.future.2019.09.054 [51] K. Bylykbashi, D. Elmazi, K. Matsuo, M. Ikeda and L. Barolli, “Effect of Security and Trustworthiness for a Fuzzy Cluster Management System,” 30 January 2019. https://doi. org/10.1016/j.cogsys.2019.01.008 [52] M. Syfullah, J. M.-Y. Lim and F. Lu Siaw, “Mobility-Based Clustering Algorithm for Multimedia Broadcasting over IEEE 802.11p-LTE-enabled VANET,” March 2019. iJIM ‒ Vol. 16, No. 10, 2022 47 https://doi.org/10.1007/s11227-015-1517-6 https://doi.org/10.14569/IJACSA.2016.070957 https://doi.org/10.5296/npa.v8i2.8434 https://doi.org/10.3390/s16040478 https://doi.org/10.3390/s16040478 https://doi.org/10.1016/j.procs.2018.01.134 https://doi.org/10.1007/s11277-018-5809-z https://doi.org/10.1109/TITS.2017.2727226 https://doi.org/10.1155/2018/9826782 https://doi.org/10.1016/j.vehcom.2018.08.001 https://doi.org/10.1002/dac.3869 https://doi.org/10.1371/journal.pone.0214664 https://doi.org/10.1155/2019/8415234 https://doi.org/10.1007/s13369-019-03854-2 https://doi.org/10.1007/s13369-019-03854-2 https://doi.org/10.1155/2019/2917238 https://doi.org/10.1155/2019/2917238 https://doi.org/10.1109/ACCESS.2019.2920002 https://doi.org/10.1016/j.future.2019.09.054 https://doi.org/10.1016/j.future.2019.09.054 https://doi.org/10.1016/j.cogsys.2019.01.008 https://doi.org/10.1016/j.cogsys.2019.01.008 Paper—Clustering Review in Vehicular Ad hoc Networks: Algorithms, Comparisons, Challenges and… [53] T. Liu, S. Shi and X. Gu, “Naive Bayes Classifier Based Driving Habit Prediction Scheme for VANET Stable Clustering,” Mobile Networks and Applications, 20 July 2020. https:// doi.org/10.1007/s11036-020-01580-w [54] M. Mukhtaruzzaman and M. Atiquzzaman, “Junction-based Stable Clustering Algorithm for Vehicular Ad Hoc Network,” Annals of Telecommunications, 2021. https://doi.org/10.1007/ s12243-021-00881-9 [55] A.Temurnikar, P. Verma and G. Dhiman, “A PSO Enable Multi-Hop Clustering Algorithm for VANET,” International Journal of Swarm Intelligence Research (IJSIR), p. 14, 2022. https://doi.org/10.4018/IJSIR.20220401.oa7 [56] B. Liu, Z. Fang, W. Wang, X. Shao, W. Wei, D. Jia, E. Wang and S. Xiong, “A Region- based Collaborative Management Scheme for Dynamic Clustering in Green VANET,” IEEE Transactions on Green Communications and Networking, 2022. https://doi.org/10.1109/ TGCN.2022.3158525 [57] Oussama Senouci, Saad Harous and Zibouda Aliouat, “Survey on Vehicular Ad Hoc Net- works Clustering Algorithms: Overview, Taxonomy, Challenges, and Open Research Issues,” WILEY, March 2020. https://doi.org/10.1002/dac.4402 [58] T. A. Kareem, M. A. Hussain and M. K. Jabbar, “Particle Swarm Optimization Based Beam- forming in Massive MIMO Systems,” International Journal of Interactive Mobile Technol- ogies (iJIM), 2020. https://doi.org/10.3991/ijim.v14i05.13701 [59] A. Bengag, A. Bengag and M. Elboukhari, “A Novel Greedy Forwarding Mechanism Based on Density, Speed and Direction Parameters for Vanets,” International Journal of Interac- tive Mobile Technologies (iJIM), 2020. https://doi.org/10.3991/ijim.v14i08.12695 [60] K. G and P. E, “Performance Analysis of Stationary and Deterministic AODV Model,” International Journal of Interactive Mobile Technologies (iJIM), 2020. 7 Authors Mays Kareem Jabbar received the B.Eng. degree in computer and information technology engineering from the University of Technology, Baghdad, Iraq, in 2007, and the master’s degree in wireless communications networks from Computer Engi- neering Department/Eastern Mediterranean University/Cyprus 2014. She is working as a lecturer at the College of Engineer, Misan University, Misan, Iraq. She is cur- rently a Ph.D. student at ENIS/Sfax University/Tunisia. She can be contacted at email: m_mays85@uomisan.edu.iq. Hafedh Trabelsi studied in Ecole National d’Ingénieurs de Sfax ENIS from 1983 to 1989, In 1990, M.S. degree received from the Ecole Centrale de Lyon, France, in 1994 the PhD degree at the University of Paris XI, Orsay, France, and in 2008 the Research Management Ability degree from ENIS, All in electrical engineering. He joined the Tunisian University in 1995; He is currently a Professor of Electric Power Engineering at ENIS. Since 2013 he is full professor at University of Sfax, Tunisia, holding the chair for Smart Electric Vehicle group in Computer Embedded System laboratory at ENIS. In his research he focuses on the design of new electric machines by using Finite Element Method and the implementation of advanced control system for electric vehi- cle. On-going research is focusing on smart city & secure system. He can be contacted at email: hafedh.trabelsi@enis.tn. Article submitted 2022-02-04. Resubmitted 2022-03-19. Final acceptance 2022-04-06. Final version published as submitted by the authors. 48 http://www.i-jim.org https://doi.org/10.1007/s11036-020-01580-w https://doi.org/10.1007/s11036-020-01580-w https://doi.org/10.1007/s12243-021-00881-9 https://doi.org/10.1007/s12243-021-00881-9 https://doi.org/10.4018/IJSIR.20220401.oa7 https://doi.org/10.1109/TGCN.2022.3158525 https://doi.org/10.1109/TGCN.2022.3158525 https://doi.org/10.1002/dac.4402 https://doi.org/10.3991/ijim.v14i05.13701 https://doi.org/10.3991/ijim.v14i08.12695 mailto:m_mays85@uomisan.edu.iq mailto:hafedh.trabelsi@enis.tn