# Modeling and Analysis of New Hybrid Clustering Technique for Vehicular Ad Hoc Network
## 3 Clustering Model
### Covering Rough Set Model
#### 3.1.2 Group Implementation
* **Compute the final value of K.** Finally, the clustering K-value is obtained as in (14) by selecting the minimum value of K. The initial \(K^{*}\) value and the second \(K^{**}\) value are compared, and the optimal value is computed. Algorithm 2 shows the K value of the proposed model for a VANET in a highway scenario. \[K=min(K^{*},K^{**})\] (14)
```
Initialize G, N, X, Y, R //G: a group of vehicles, n: number of vehicles in each group, X, Y: vehicle locations, CR: vehicle coverage area. begin for all nodes do  Calculate the distance among all vehicles groups; \(d_{Max}\).\(\leftarrow\) maximum distance//Calculate the group length endfor Calculate K\({}^{*}\) as the nearest integer greater value using equation (11)  Select a random number of \(k\) for S = 1 to K do  K\({}^{**}\) = S + 1; for i = 1 to n do  Initialize centroid C\({}_{i}\) based on K\({}^{**}\) Assign other vehicles to C\({}_{i}\)  Apply Equations (12) and (13) to calculate SSE endfor  SSE(s) = SSE;// calculate SSE for each group. endfor for S = 1 to K do  Compute the minim value of SSE  K\({}^{**}\) \(\leftarrow\) S; endfor Use Equation (14) to select K Export K;
```

**Algorithm 2** K-value calculation

### K-Means Model

The K-Means algorithm is the most important algorithm in the clustering steps and is used in various fields, such as data mining, wireless sensor networks, and ad hoc networks. An unsupervised machine learning (ML) technique classifies the dataset as a group of fixed K clusters at the start of the algorithm procedure. The main objective is to minimize the member distance and the CHs. As mentioned in Figure 7A, the algorithm chooses the initial K value (for example, three clusters), and the blue node represents the cluster member with a yellow centroid location that was initially selected. The objective is to assign the set of vehicles \(v_{j}\) with \(1\leq j\leq N\) into K clusters. K-Means randomly chooses K points

Figure 6: K\({}^{**}\) calculation flowchart. \(v_{i}\) with \(1\leq i\leq K\) of data in the vehicle dataset as cluster centroids, where each cluster centroid belongs to cluster C. Then, the algorithm collects each point in the vehicle dataset to the nearest cluster centroid. This process is conducted according to an objective function, which computes the sum of all squared distances between the CMs and the centroids in all clusters, as shown in Figure 7b. This is the second iteration to choose an optimal centroid location for each cluster, and the calculation is applied using the objective function (15):

\[avgmin_{c}\sum_{i=1}^{k}\sum_{v_{j}\in C_{i}}d(v_{j},u_{i})=avgmin_{c}\sum_{i=1 }^{k}\sum_{v_{j}\in C_{i}}\left|v_{j}-u_{i}\right|^{2} \tag{15}\]

where \(d(v_{j},u_{i})\) is the vehicle to cluster centroid Euclidean distance; \(v_{j}\) is the vehicle position and \(u_{i}\) is the cluster centroid position with \(i=1,\,\ldots,\,\mathrm{K}\); and \(\mathrm{K}\) is the number of clusters. After assigning the vehicles in each cluster with the optimal centroid location, as shown in Figure 7c, the K-Means algorithm updates the position of each cluster centroid as the average distance between each node and cluster centroid using (16):

\[u_{i}=\frac{1}{\left|C_{i}\right|}\sum_{j\in C_{i}}v_{j}\;,\;\;\;\;\;\forall i \tag{16}\]

Finally, the clusters are formed with the minimum within-cluster distance, as shown in Figure 7d. When the final centroid location has been calculated and the minimum distance has been computed, and all nodes are in the centroid region. The global algorithm is illustrated in Algorithm 3; the main goal of this algorithm is to create clusters using the optimal \(\mathrm{K}\) value. The main steps of this algorithm can be summarized as follows:

Import the value of \(\mathrm{K}\) from Algorithm 2. Select the initial centroid for each cluster. Assign all vehicles to the nearest centroid to create clusters. Compute a new cluster centroid based on (16). Repeat steps 3 and 4 to obtain the optimal centroid location. Ensure that all vehicles have been assigned to clusters.