# Modeling and Analysis of New Hybrid Clustering Technique for Vehicular Ad Hoc Network
## 3 Clustering Model  
In this section, we present the proposed RK-Means clustering algorithm model, which comprises the following three main stages:  
* **Stage 1:** The preparation of the datasets using SUMO software to collect the vehicle parameters at different timestamps. The XML file of the dataset describes the location, speed, direction, and steering angle. This study focused on a highway scenario, so the steering angle could not be used. To update this model for another scenario such as a city map, the steering angle would be a more important parameter to consider  
\begin{table}
\begin{tabular}{c c c c c c c c} \hline \hline \multirow{2}{*}{**Proposed Model**} & \multirow{2}{*}{**Algorithm Type**} & \multirow{2}{*}{**Network Scenario**} & \multicolumn{6}{c}{**Effective Parameters**} \\ \cline{3-8}  & & & **Location** & **Speed** & **Direction** & **Distance** & **Transmission Range** \\ \hline CBL [16] & Single & Highway & \(\surd\) & \(\surd\) & \(\times\) & \(\surd\) & \(\times\) \\ K-Means [17] & Single & Satellite image & \(\surd\) & \(\times\) & \(\times\) & \(\surd\) & \(\times\) \\ Radio Resource [18] & Single & Highway & \(\surd\) & \(\surd\) & \(\times\) & \(\surd\) & \(\surd\) \\ Modified K-Means [21] & Hybrid & Highway & \(\surd\) & \(\times\) & \(\times\) & \(\surd\) & \(\surd\) \\ K-Means++ [22] & Single & UAV & \(\surd\) & \(\times\) & \(\surd\) & \(\surd\) & \(\surd\) \\ OK-Means [23] & Single & Highway & \(\surd\) & \(\times\) & \(\surd\) & \(\surd\) & \(\surd\) \\ RK-Means (proposed herein) & Hybrid & Highway & \(\surd\) & \(\surd\) & \(\surd\) & \(\surd\) & \(\surd\) \\ \hline \hline \end{tabular}
\end{table}
Table 2: RK-Means effective parameters compared with other clustering schemes in VANETs.  
for covering table construction and clustering initialization. In this stage, the CRS algorithm works by considering all the vehicle parameters presented in the above table to initialize the covering groups. The covering groups divide the VANET datasets into multi-groups according to the approximation type. The output of the covering groups is CG1, CG2, CG3,..., and CGn. The number of covering groups depends on the vehicle status table and approximation types; in this paper, the number of groups was 10. The CRS model with descriptions of each step is illustrated in more detail in Section 3.1, where the main CRS algorithm includes the approximation calculation steps.
* **Stage 2:** In this stage, each covering group generated in stage 1 is input into the k-value calculation model to compute the number of clusters. At this stage, the optimal number of clusters is calculated based on two different models, and the minimum number of clusters is selected at the end. When the number of clusters has been calculated, the output represents the number of clusters in each covering group calculated in stage 1. The value of k1 represents the number of clusters in CG1, and the value of k2 is the number of clusters in CG2. For all covering groups in this work, the model generated the number of clusters. The cluster number calculation model is presented in detail in Section 3.2, with a description of the algorithm and each step.
* **Stage 3:** Finally, the cluster generation process is carried out by applying the classical K-Means clustering algorithm. The K-Means clustering algorithm creates the clusters of each covering group generated in stage 1 using the optimal cluster number calculated in stage 2. For example, if the value of k1 is 4, the K-Means algorithm creates four clusters from the CG1 datasets; if the k2 value is 6, it creates six clusters from CG2, and so on. This stage is explained in detail and the clustering algorithm is presented in Section 3.3.  
The complete clustering model proposed in this work for vehicular ad hoc networks is shown in Figure 2.  
Figure 2: Proposed clustering stages.