# Information Relaying Methods in VANET: Algorithms, Standards and Tests
## 7 Discussion  
One of the important features to evaluate our enhanced K-means-type algorithm is the information relaying delay. In Figure 5a, a local maximum information transmission delay is calculated, i.e., a clustering-led maximum delay is nominated to evaluate the performance. It is well worth noting that our proposed K-means-type1 algorithm keeps a fairly low profile with the ascending number of vehicles on the road, and the end-to-end delay from either source to cluster head or cluster head to the ego vehicle maintains around 10 ms which is sufficiently smaller than two of the algorithms referenced [10; 11].  
To better evaluate the performance of the proposed clustering algorithms, it is necessary to observe the throughput of the system in comparison with the legacy approaches in [10; 11]. In Figure 5b, we evaluate how the algorithms work from a sparse scattering scenario to a dense one. It can be seen that the throughput calculated by implementing our proposed algorithms shows an ascending superiority over two referred algorithms when dropping more vehicles in the layout. The advantage could be greater than 30% in terms of performance gain @300 vehicles scenario. In particular, two proposed algorithms show almost no difference due to the reason that the order of centroids selection contributes little to system performance instead of the algorithm itself.  
Figure 6 investigates a comparison of the convergence speed by implementing the proposed algorithms and typical K-means algorithm under different metrics. The metrics in regards to the distance calculation are derived based on the metric criterion in [6]. The cluster centers calculated via the proposed algorithms become stable after only three to four iterations, in contrast to the eight iterations for the typical K-means algorithm in the case of evaluating the member quantity in each cluster. With more stringent restrictions on the algorithm seeding range, it is well understood that the shrinking search space of the  
Figure 4: Real-world simulation map.  
Figure 5: Proposed algorithms delay and throuput performance evaluation. (**a**) Information broadcasting delay. (**b**) System throughput vs. the number of vehicles.  
proposed algorithms effectively contributes to finding the optimal relay vehicles with a priori information of the real-time topology.  
In Figure 7, without any relays, vehicles alongside the horizontal road achieved the data packet reception rate at 29.5% while vehicles in the vertical road at 75.1%, and vehicles within 50 meters range to the intersection center could achieve 95% above data packet reception if dividing simulation periods and focusing on packet reception rate variance corresponding to location variance. This is a natural consequence since the line-of-sight (LOS) transmission path dominates the scenario when either the sender or the receiver is at the intersection, while NLOS is typical when both sides are far from the center and not in the same section of road. The square area with 100 m side length is specifically selected as the relay selection area, all vehicles within this area could switch their relay function on, and the maximum relay nodes number is applied to minimize redundancy of relayed transmission. Various methods could be used for relay node candidate confirmation, in the Veins simulation we use our proposed K-means type1 algorithm to initially pick the relay vehicles up, after that the announcement message is used to identify the existence of relay nodes to eliminate potential relay redundancy. It is well noted that the candidate node must listen for a period before switching on relay function. With relay switched on in the simulation, the performance increased to 91.3% for horizontal direction vehicles and 98.9% for vertical direction vehicles, at the cost of 1.99 times more transmission budget for relaying data packet.  
Figure 6: Proposed algorithm convergence speed under different evaluation metrics.