# Information Relaying Methods in VANET: Algorithms, Standards and Tests
## 4 Enhanced K-Means-Type Algorithm
### Real Center Mean Exploration  
The center mean \(\mu(C_{i})=\lvert C_{i}\rvert^{-1}\sum_{x\in C_{i}}x\) is well defined in [9], and the intermediate consequence keeps updating until the mean squared error (MSE) of two consecutive mean centers is smaller than a given threshold. By an analysis of the iterative procedure, it is not difficult to find that the cluster center selected is not a real data point in the set but a statistical mean value, which we call a virtual center. To make the algorithm fit the system model proposed in the VANET, the closest vehicle to the virtual mean center vehicle in the set should be chosen as the cluster center for the information rebroadcasting. In this regard, we provide two candidate enhanced K-means-type algorithms with consideration of the update timing of different real centers. The K-means-type1 algorithm given in Algorithm 1 shows a virtual-to-real centroid transition in each iteration via the centroid recalculation once the subspace (cluster) has changed. Specifically, step 4 to step 6, which we designed for the VANET, differentiate this algorithm from the typical K-means algorithm. It is well worth noting that \(\theta_{\text{th}}\) is a numerical threshold to assure two nodes selected adjacent in time are close enough. Figure 2: Information broadcasting relaying in a four-lane and two-direction highway. ```
0: Number of clusters required for the network; The set of initialized cluster centers, \(c_{i}\);
0: Real cluster center closest to the virtual center mean, \(v_{i}\); Connecting vehicle, \(v_{j}\);
1: Arbitrarily select \(k\) clusters with the center initialization \(C=\{c_{1},c_{2},...,c_{k}\}\);
2: Partition the vehicle set via \(\phi\) by calculating the distance between each individual vehicle and all centers to find the nearest cluster;
3: Update the centroid \(c_{i}\) via the mean center calculation function \(\mu(C_{i})=|C_{i}|^{-1}\sum_{x\in C_{i}}x\) in each cluster \(C_{i}\);
4: Map the mean center \(\mu(C_{i})\) to the closest vehicle \(v_{i}\in V\) within each cluster \(C_{i}\);
5: Repeat 3 and 4 until \(\|v_{i}(t)-v_{i}(t+1)\|^{2}\leq\theta_{\text{th}}\) is satisfied;
6: Pick \(v_{j}\in V(j\
eq i)\) that is closest to the center of two sequential centroid vehicles;
7:return\(v_{i}\) and \(v_{j}\);
```  
**Algorithm 1** K-means-type1 Algorithm for the VANET  
The other enhanced K-means type algorithm, called K-means-type2, which is shown in Algorithm 2 in parallel, calculates the real vehicle center after the algorithm converges in the form of virtual center means. Similar to the Type1 algorithm, a numerical threshold \(\lambda_{\text{th}}\) is set for the convergence of a virtual center mean. The two algorithms theoretically share many similarities, with the only difference being the order of step 4 and step 5 and the parameters therein. It is also well noted that the algorithm selects the connecting vehicle \(v_{j}\) by finding the closest approximation to the midpoint of the distance between two selected consecutive real center vehicles, and this procedure fits for both algorithms. The outcome achieved via the enhanced K-means algorithms matches the actual network layout better, even though a double approximation on the cluster centers and connected relay vehicles is implemented.