{'fraction_non_alphanumeric': 0.03144445671784676, 'fraction_numerical': 0.009904635664052431, 'mean_word_length': 4.91592245698105, 'pattern_counts': {'":': 0, '<': 0, '<?xml version=': 0, '>': 0, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 0, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
Clustering in VANET: Algorithms and Challenges

Clustering is an important concept in vehicular ad hoc network (VANET) where several vehicles join to form a group based on common features. Mobility-based clustering strategies are the most common in VANET clustering; however, machine learning and fuzzy logic algorithms are also the basis of many VANET clustering algorithms. Some VANET clustering algorithms integrate machine learning and fuzzy logic algorithms to make the cluster more stable and efficient. Network mobility (NEMO) and multi-hop-based strategies are also used for VANET clustering. Mobility and some other clustering strategies are presented in the existing literature reviews; however, extensive study of intelligence-based, mobility-based, and multi-hop-based strategies still missing in the VANET clustering reviews. In this paper, we presented a classification of intelligence-based clustering algorithms, mobility-based algorithms, and multi-hop-based algorithms with an analysis on the mobility metrics, evaluation criteria, challenges, and future directions of machine learning, fuzzy logic, mobility, NEMO, and multi-hop clustering algorithms.

VANET CLUSTERING dissemination among the vehicles for V2V communication.
VANET also suffers from issues such as the hidden terminal problem, high latency for safety message transmission, message security, broadcast storm problem, quality of service (QoS), packet routing, congestion control, and resource management.
To solve these issues, a hierarchical structure has been investigated in the literature [2]. In a hierarchical structure, two or more nearby vehicles, who have some common features, join in a group which is called clustering. Clustering concept is widely used in data mining, and machine learning [3]. Clustering is also used in MANET, which is the predecessor of VANET, to cluster the mobile nodes. In a clustered vehicular environment, a large network of vehicles is considered as a network of some small networks or clusters.

Clustering Concept in VANET
In VANET clustering, cluster head (CH) plays a key role in the formation process of a cluster, as shown in Fig. 1  and the vehicle will lose connection with the CH more frequently. As a result, data loss will be very high when a vehicle remains at the edge of a cluster. For this reason, some algorithms prefer a geographically center vehicle as the CH for reliability.

Multi-hop Clustering
Generally, a cluster of vehicles means a 1-hop cluster where a CH can reach all its CMs directly because the CMs are within the range of the CH; however, some clustering algorithms are based on multi-hop strategy. When a vehicle cannot reach the CH of a cluster directly but can reach a member of the cluster, then the new vehicle joins to the cluster through a CM. Hence, a CH can cover CMs in a multi-hop manner which is termed as multi-hop clustering, or N-hop clustering, or k-hop clustering.
The value of N or k depends on the number of hops the CH can cover. In the Fig. 3, the 2-hop CM cannot reach the CH but can reach a CM of the CH. As a result, the 2-hop CM joins the cluster through a CM of the CH creating a multi-hop cluster.

Objective and Motivation
In machine learning and data mining, many algorithms have Additionally, multi-hop clustering strategies are also used in VANET clustering where the CH can cover more than one hop area to reduce the number of clusters. Therefore, our aim is to classify all three major types of VANET clustering algorithms: intelligence, mobility, and multi-hop to stimulate the research of efficient and stable clustering algorithms for VANET.

Literature Survey on Clustering
The first attempt to study clustering algorithms for VANET is [4]; however, only a few clustering techniques have been presented without any classification. The first classification of the VANET clustering techniques is presented in [5].
Classification is performed based on position, destination, and medium access, etc. Few of the algorithms presented are based on intelligence, vehicle mobility, and multi-hop strategies; however, the absence of NEMO strategies and presentation of a

Contributions
The contributions of this paper can be summarized as follows: 1. The paper studied intelligence-based VANET clustering extensively, classifying them into machine learningbased and fuzzy logic-based along with a comparison among the algorithms in terms of strengths and weaknesses.
2. Comparison among hybrid architectures which combine machine learning and fuzzy logic algorithms to exploit the advantages of both the schemes presented.
3. Apart from vehicle mobility-based strategies, network mobility-based strategies studied separately.
4. Details study of multi-hop strategies presented in a separate section.

Structure
The rest of the paper is organized as follows. In Section 2, we presented the classification of VANET clustering. Intelligencebased VANET clustering algorithms are presented in Section 3.
Mobility-base algorithms are classified in Section 4, where multi-hop-based algorithms are presented in Section 5. Present challenges and future research directions are presented in Section 6 with a conclusion in Section 7.

INTELLIGENCE BASED STRATEGIES
Clustering is an important concept in machine learning and data mining [3] and many clustering algorithms are developed over the years such as k-means and hierarchical clustering. The clustering algorithms from machine learning are used in VANET for vehicle clustering. Fuzzy logic is also used for VANET clustering. Supervised learning, such as Q-learning, and other machine learning clustering algorithms are used along with fuzzy logic to create a hybrid strategy for VANET. The difference between our works with the other works is, we classified and analyzed machine learning algorithms and fuzzy logic-based algorithms separately. We also analyzed the hybrid architecture of machine learning and fuzzy logic in a separate section. In Section 3.1, we discussed machine learning algorithms for VANET clustering strategies. Next, fuzzy logic algorithms described in Section 3.2 and hybrid clustering strategies placed in Section 3.
3. An analysis of intelligence-based strategies presented in Section 3.4.

Machine Learning Algorithms
Clustering algorithms are used in data mining and machine learning to cluster similar types of objects. K-means algorithm is the most frequently used machine learning algorithm in VANET where k number of clusters are created dividing the vehicles.
Initial centroids are assumed and coordinates of the vehicle are given as input. In the next step, Euclidean distances are calculated to determine the new centroid, and the centroids are elected as the CH. Whenever a CM joins into a cluster, or leave a cluster, the mean of the cluster is susceptible to change in kmeans algorithm and need to re-calculate the new mean of the cluster to reflect the change that can lead to elect a new vehicle as the CH. In hierarchical clustering, Euclidean distances of all vehicles are calculated and the vehicles connect with each other sequentially starting from the minimum distance.

K-means Clustering Algorithms
A k-means-based clustering algorithm is proposed by Bansal et al. [11] to divide the vehicles into clusters. Three parameters: x dimension and y dimension, i.e., the position of the vehicles is considered to form the clusters. Additionally, if any vehicle joins or leaves the cluster, the mean VANET CLUSTERING of the entire cluster can be changed with the change of the CH itself that reduces the cluster lifetime and cluster stability.
Instead of enhancing security measure as in [11], k-means is used to solve data congestion problem [12] to decrease packet loss and end-to-end delay. Clustering is performed using kmeans algorithm based on distance and direction along with message size, the validity of messages, and type of messages. K-means [13] is used to increase the stability of the clusters.
The distances of the vehicles are calculated to find the minimum average distance to form a cluster. The center vehicle is selected as the CH. Distance is measured by Euclidean distance and all pair shortest path is calculated within a cluster using the Floyd-Warshall algorithm to choose the CH. However, the limitation of the number of clusters persists, as was in [11][12].
One limitation is common for [11][12][13], which is sensitivity to the initial centroids. To overcome this drawback adaptive kharmonic means is proposed [14] where a vehicle must meet the minimum bandwidth requirement to be elected as the CH.
Traditional k-harmonic means, where relative distance and centroids are measured, is modified to make compatible with the mobility of vehicles. The velocity of the vehicles is considered along with their position to form the clusters. However, the limitation of the fixed number of clusters is continued that can cause a problem in v2v communication with many vehicles.

Hierarchical Clustering Algorithms
To overcome the limitations of the k-means algorithm, an agglomerative hierarchical clustering approach is used in [15], where the direction and speed of the vehicles are considered to form a cluster along with some quality of service (QoS) parameters. The past duration of the node acting as a CH, PDR, and TR are considered for CH. In hierarchical clustering, Euclidean distances of all the vehicles are calculated and the vehicles connect with each other sequentially starting from the minimum distance and do not require the number of clusters as the input unlike k-means [11][12][13][14]. The vehicles in [15] are considered as two clusters based on their direction and CH is selected based on the duration of acting as a CH in the past.
However, while the implementation of k-means is simple, the hierarchical approach requires a proximity matrix calculation which leads to O(n 2 ) space complexity and O(N 2 log(n)) to O (N 3 ) time complexity. Moreover, once a CM joins to a cluster, it cannot be undone, but topology can change any time in VANET and requires a change in the cluster also.

Ref.
Algorithm Evaluation parameters [11] K-means PDR, throughput, overhead [12] K-means PDR, throughput, delay [13] K-means CH Duration, signal quality, TR [14] K-Harmonic means Coverage [15] Hierarchical PDR, throughput, delay, degree of node [16] MFO No. of Clusters, TR [17] MFO No. of Clusters, grid size VANET CLUSTERING optimization (MFO). The MFO algorithm depends on the navigation method of moths, which follow a spiral flying path, called transverse orientation. Moth can fly maintaining a fixed angle with the moon that can be considered as a straight path for a long distance. The same concept is used [16,17] to cluster the vehicles in a highway environment to optimize cluster considering speed, direction, grid size, the degree of a node, and transmission range of the vehicles, however, no result is provided to prove the optimization of performances in terms of PDR, endto-end delay, number of hops, and throughput.

Stability Algorithms
A fuzzy logic-based CH selection algorithm is proposed by Hafeez et al. [18], the first instance of introducing fuzzy logic system in VANET scenario. In this earlier work, relatively simple fuzzy system developed where two metrics such as relative speed and distance are given as input to the fuzzifier to start the clustering formation process. The fuzzy logic inference system is used to learn the driver's behaviors, and to predict future speed and position. Based on the predicted speed and position, the CH is selected by the defuzzifier. If the stability factor of the CH falls below a predefined threshold value, a new member is selected as the CH. Merging of two clusters are allowed in this scheme. If the second CH reaches to half of the TR of the first CH, the second CH will merge with the first CH; however, considering only two input parameters in the fuzzy input sets affects the performance of the selection of the CH.
The work in [18] is improved in [19] adding acceleration as the input parameter along with speed and distance to create more stable clusters. Fuzzy logic inference system is integrated with an adaptive learning mechanism to provide a more stable cluster by predicting the future speed and the positions of the CMs. Like VANET CLUSTERING [18], the stability of the vehicle compared to the neighbor vehicles is given preference to be selected as the CH. Similarly, merging of two clusters are allowed and follow the same process as in [18]; however, three input parameters are also proved insufficient for the highly dynamic nature in VANET. To further improve the performance of [19], the direction of the vehicles is also considered [20] along with the speed, distance, and acceleration. However, previous history of acting as CH and QoS issues are not considered in this approach.

QoS Algorithms
Stability is given priority in [18][19][20] without considering QoS issue. In [21], a hybrid network architecture of V2V and LTE advanced cellular network is proposed where quality-of-service is improved using a fuzzy logic-based gateway selection technique. Cluster is formed considering traffic type of the vehicle and the CH is selected using received signal strength and load. The CH is the leader of the cluster but may not work as the gateway to communicate with the LTE advanced cellular network [21] which is a unique concept for RSU assisted VANET clustering strategies while CH or CG is generally selected as the LTE gateway in VANET. However, dynamic clustering at higher speed will cause frequent CH change as well as frequent change of CG candidates and will increase the complexity selecting the gateway node that can increase packet loss and end-to-end delay.
To solve the limitation of resources in dynamic vehicular cloud architecture, a fuzzy-based CH selection process is proposed [22]. To improve reliability and QoS, a CH works as a cloud controller who can create, delete and update the vehicular cloud. The average speed, degree of node, and link quality are considered to form the clusters and the CH is selected based on a fit factor; however, reliability and quality-of-service of such strategy is questionable, because the increase in degree of node can decrease the performance of the CH by allocating resources to a large number of members. Moreover, performance of the scheme degraded in the absence of RSU.

Hybrid Algorithms
Machine learning algorithms are integrated with fuzzy logic system to make the cluster formation process and CH selection process more efficient in a hybrid manner.

Reinforcement Learning Algorithms with Fuzzy Logic
To improve efficiency, stability, and reliability of cloud services in a vehicular environment, a new architecture is proposed [23] using a reinforcement learning algorithm, Qlearning, along with the fuzzy logic algorithm used in [22]. The CH is selected based on fuzzy logic and resource management is improved using Q-learning based service provider selection  as first in first out, bandwidth aware, and resource-aware are used [23] that were not present in [22]. However, among the mobility parameters, the relative speed is only considered to select the CH, other parameters such as acceleration and direction are ignored.
Moreover, the algorithm is RSU dependent.
A data storage scheme is proposed [24] that store the data employing a fuzzy logic-based protocol considering multiple metrics such as throughput, stability, and bandwidth efficiency.
To increase the stability of the fuzzy decision, Q-learning is used.
The slow vehicles are selected as the CH to avoid frequent change of cluster heads to make the cluster more stable considering vehicle velocity, degree of node, and channel condition. However, slow vehicles cannot be the most suitable candidate to become a CH because the faster cars will cross the slow vehicles in a relatively short period of time that will further destabilize the clusters. Similar to [24], for a vehicle to RSU communication, a reinforcement learning algorithm is used [25] to create clusters and fuzzy logic is used to make the clusters more stable considering vehicle mobility, vehicle distribution, and channel condition; however, the QoS is an issue when vehicle density grows faster.

K-means with Fuzzy Logic
Authors in [23][24][25] are using Q-learning algorithm where [26] addresses the issue of traffic congestion in a dynamic vehicle environment using k-means clustering algorithm integrated with Arduino controller and a PHP web server. A fuzzy rule-based inference system is proposed considering four attributes: vehicle speed, rain, fog, and brake frequency. For all the vehicles, the fuzzy congestion output is sent to a PHP cloud server through an ESP8266 wi-fi module. This module also generates a twodimensional position of the vehicles as an alternate of GPS. The PHP server uses K-means clustering algorithm to form the clusters without any assistance from RSUs. However, the time to connect to the PHP server and to send or receive information from an external server is required that can cause additional delay. Moreover, k-means always choose the centroid as the CH and for any change in the cluster may cause to change the CH every time.

Dolphin Swarm Algorithms with Fuzzy Logic
Authors in [11][12][13][14][15][16][17][18][19][20][21][22][23][24][25] use a single CH for a cluster where the CH acts as the leader of the cluster. To reduce the overload of the CH in the cluster, a multiple CH scheme is proposed in the Hybrid fuzzy multi-criteria decision making (HF-MCDM) [27] where fuzzy analytic hierarchy process and TOPSIS methods are combined together to form a cluster making the fuzzy decision optimal. The load of the leader of a cluster is distributed among   The stability of the clusters highly depends on the lifetime of the clusters. Generally, k-means-based algorithms [11][12][13][14] cannot provide high lifetime to the clusters, because if a single vehicle joins or leave the cluster, the entire algorithms is reset, and the CH can be changed frequently. Consequently, the stability is also affected. Hierarchical clustering algorithms [15] do not suffer this problem and can provide higher lifetime and higher stability compare to k-means algorithms. Fuzzy logic algorithms [18][19][20][21][22][23][24][25][26][27] consider the prediction of future movement that provide more flexibility compare to k-means. As a result, fuzzy logic algorithms can provide higher lifetime and more stability. Similarly, hybrid strategies can also provide higher lifetime and better stability compare to k-means algorithms.

MOBILITY BASED STRATEGIES
The most common clustering strategies in VANET is mobility-based strategies. The movement of the vehicle, such as relative speed, moving direction, acceleration, position etc., are the basic metrics used for mobility-based clustering. Due to the high mobility of the vehicles, clusters frequently break down in VANET. Therefore, instead of the efficiency of the clustering algorithms, stability of the clusters is the main concern in the vehicle mobility-based algorithms. The classification of mobility-based algorithms is presented in the Fig. 9.
In Section 4.  [30], acceleration is also considered in [31] to provide more stability and security, however, the scheme is optimized for highway only. Additionally, average CH duration achieved in this scheme is not significant which decreases cluster lifetime.
Traffic pattern of buses is used to improve stability in [32] by decreasing the number of CH change. Velocity, position, and direction of the vehicles are used as the mobility metric along with fixed-route pattern of buses in urban area. The number of CH changes is evaluated only; however, stability and lifetime of the clusters do not depend on a single parameter of the CH.
Moreover, CM related parameters are ignored.
Moving direction, relative vehicle position, and link lifetime are considered to form a cluster in [37]. A temporary state for the CHs and a safe distance threshold have been introduced to increase the stability of the clusters. CH is chosen from the vehicles which is nearest to the center of a cluster so that its neighbor can spend more travel time to leave the cluster. Consequently, cluster stability will decrease, and cluster lifetime will become low. Moreover, in some cases, many vehicles can have no cluster to join.

Data Dissemination/ Routing Algorithms
In [38], a clustering-based data dissemination protocol is

QoS Algorithms
To

MAC Algorithms
Clustering-based MAC protocol is proposed in [44][45] for faster delivery of safety messages, and in [46] for efficient resource management. [44] introduces three new control packets instead of RTS/CTS (request to send/clear to send) packet for the cluster formation process. When an isolated vehicle does not get any response, it becomes CH. If the number of vehicles is less than the delay will be the less and CH will broadcast the CM list to all CMs. [45] and [46] deal with the hidden terminal problem. [46] tries to reduce the packet conflict due to hidden terminal problem, and [45] tries to solve the hidden terminal problem using a reserve channel that can be used by safety messages even during the congestion. [45] uses velocity, and acceleration to form the cluster where [46] uses relative speed to form the cluster and to choose the CH. None of these algorithms [44][45][46] evaluated the stability parameter that can affect the lifetime of the clusters. These clustering-based MAC protocols are working as evidence that clustering not only solves the scalability VANET CLUSTERING problem but also can be utilized for various purposes in VANET.

General-purpose Algorithms
A general-purpose clustering algorithm is proposed in [47] to provide a more stable and efficient cluster considering velocity, position, direction, and link quality. Double-head cluster is used, so that a CM does not get disconnected from its cluster even it loses connection with the primary CH. Four states of vehicles are used like [37] where one vehicle acts as a mirror of the CH and works as the backup CH when a CM loses connection with its primary CH. Four states of vehicles are used like [37] where one vehicle acts as a mirror of the CH and works as the backup CH when a CM loses connection with its primary CH. The relative position in the cluster, relative speed, average signal-to-noise ratio, and average link expiration time are considered to become the CH; however, performance comparison with the recent clustering algorithms need to be presented. Also, how the two CHs handle PDR, delay, and throughput is not evaluated. A weighted clustering algorithm is proposed in [48] where the reputation of the vehicles is

NEMO Algorithms
Some of the clustering algorithms adopted the NEMO concept in the VANET environment. NEMO-based clustering techniques mainly developed for faster handoff, i.e., to reduce the total number of handoffs and handoff latency. Table VII evaluates NEMO-based algorithms.

Handoff Algorithms
To reduce the number of handoffs as well as handoff latency, clustering strategy is applied in [49] for NEMO-based VANET.
The MR is considered as the CH of the cluster. The MR and mobile nodes connected with the MR are treated as a cluster.
Since CH handles the routing procedure in clustering strategies, To solve the handoff and packet loss problem in high-speed VANET, NEMO-based protocol [50] is proposed for highway.
The MR is the CH and the network is treated as the cluster. In this protocol, the car can acquire IP address from the VANET through a V2V communications to achieve network mobility.
To execute the pre-handoff procedure, the vehicle relies on the assistance of the front vehicle to acquire its care-of address, or it may acquire its new IP address through multi-hop relays from the vehicle on the lanes of the same or opposite direction. Hence, it reduces the handoff delay and maintains the connectivity to the Internet; however, comparison with other clustering algorithms are absent.

Auto-addressing Algorithms
Mobile IPv6 (MIP) based dynamic auto-addressing protocols have been investigated in the VANET scenario in cluster-based addressing scheme (CBAS) [51]. The MR is the CH and the network is worked as the cluster. In this MIP-based scheme, incoming vehicles are assigned unique IP address and clustering is used to overcome the problem of maintaining the unique IP address since vehicle communicate through its CH.
Vehicles are clustered based on their relative speed and the CH assigns the IP address to its member and ensures that the assigned IP addresses in its vicinity are unique. However, no simulation result is provided that can show the effectiveness of the scheme.

Security Algorithms
NEMO-based solution for VANET clustering discussed in [49][50][51] are mainly to solve the handoff problem, while [52] applies clustering for NEMO to increase the security for

MULTI-HOP BASED STRATEGIES
Reducing the number of clusters is one of the challenges for can implement any number of hops. Fig. 10 shows the classification of multi-hop VANET clustering algorithms.

2-hop Algorithms
In in cluster is also evaluated in [54]. No significant clustering stability or clustering efficiency-related parameters are evaluated.
Network criticality is used as the metric in a robust multihop-based algorithm, presented in [55].  A distributed multi-hop clustering algorithm for VANETs based on neighborhood follow (DMCNF) is proposed in [57] where relative mobility is given preference. It considers the

CHALLENGES AND FUTURE DIRECTIONS
The most important parts in VANET clustering are the cluster formation and the CH selection process. CMs join the cluster in the cluster formation process. Clustering algorithms in VANET are dynamic in nature and logically applied in application level.
No vehicle changes its position physically based on clustering, rather the vehicles join into the cluster based on its physical position. Joining in a cluster is an optional choice for the vehicles. Efficiency of clusters largely depends on the cluster formation process where stability of the clusters depends on the CH selection process. The efficiency of the clusters is evaluated in terms of packet loss, end-to-end delay, and throughput more frequently while the stability of the clusters is evaluated based on average CH duration, average CM duration, number of clusters, and number of state changes, etc.

CONCLUSION
Detailed analysis of VANET clustering strategies is presented in this paper from intelligence, mobility, and multi-hop perspective with an intensive discussion on machine learningbased strategies, fuzzy logic-based strategies, hybrid strategies, mobility strategies, NEMO strategies, and multi-hop strategies.
According to our findings, machine learning-based algorithms can create efficient cluster but cannot provide clustering stability because the clusters break frequently. Fuzzy logic-based algorithms can provide better stability compared to machine learning algorithms predicting the future movement of the