## 3 Vehicle Clustering Algorithms
### Vehicle Clustering Method Based on DBSCAN Algorithm  
The DBSCAN algorithm is a density-based spatial clustering algorithm, which describes the distribution tightness of the sample set based on a group of neighborhoods and determines if the sample points belong to the same cluster by whether they are closely connected. The algorithm divides the region with sufficient density into a cluster, and clusters of any shape can be clustered in the sample space with noise. The algorithm defines a cluster as the maximum set of density connecting points; it does not need to specify the number of clusters in advance but instead relies on setting the neighborhood distance threshold \(\epsilon\) and the threshold for the number of samples \(Min\)_Pts_ within the neighborhood distance \(\epsilon\). The algorithm categorizes data points within the sample set into three types: core points, boundary points, and noise points. A core point is a point where the number of samples within its neighborhood radius \(\epsilon\) exceeds \(Min\)_Pts_. A boundary point is a point where the number of samples within its neighborhood radius \(\epsilon\) does not exceed \(Min\)_Pts_ but is located within the neighborhood of a core point. Noise points are points that are neither core nor boundary points. For a given set \(X\), the DBSCAN algorithm has the following definitions:  
**Definition 1**. : _Directly Density Reachable. If \(p\) is a core point, and \(q\) lies within the neighborhood of point \(p\), then \(p\) to \(q\) is said to be directly density reachable. Directly density reachability is not symmetrical, meaning that if \(p\) to \(q\) is directly density reachable, this does not imply that \(q\) to \(p\) is directly density reachable._  
**Definition 2**. : _Density Reachable. If there exist core points \(p_{1}\), \(p_{2}\), \(p_{3}\),..., \(p_{n}\), and \(p_{1}\) to \(p_{2}\), \(p_{2}\) to \(p_{3}\),..., and \(p_{n-1}\) to \(p_{n}\) are directly density reachable, then \(p_{n}\) to \(q\) is said to be density reachable. Density reachability is also not symmetrical._  
**Definition 3**. : _Density Connected. If there exists a core point \(s\), and \(s\) to both \(p\) and \(q\) are density reachable, then \(p\) and \(q\) are density connected. Density connectivity is symmetrical. If \(p\) and \(q\) are density connected, then \(q\) and \(p\) must also be density connected. Two points that are density connected belong to the same clustering cluster._  
The vehicle clustering process in the algorithm is described in Algorithm 1. ```
1 Mark all vehicle nodes as \"unvisited\". 2 While there are still unvisited nodes: * Randomly select an unvisited node, \(p\). * Mark \(p\) as \"visited\". * If there are at least \(Min\)_Pts_ objects within the \(p\)'s neighborhood \(\epsilon\) * Create a new cluster, C, and add \(p\) to C. * Let N be the set of points in the \(p\)'s neighborhood \(\epsilon\). For each point \(p\) in N: * If \(p\) is unvisited: * Mark \(p\) as \"visited\". * If there are at least MinPts objects within \(p\)'s neighborhood \(\epsilon\), add those points to N. * If \(p\) is not a member of any cluster yet, add \(p\) to C. * Save C. * Otherwise, mark \(p\) as \"noise\". In the LEACH protocol, the selection of cluster heads is based on random selection. On one hand, the number of cluster heads cannot be determined, resulting in potential issues of too many or too few cluster heads, leading to imbalanced energy consumption. On the other hand, from the network energy model of the LEACH routing algorithm, it can be observed that there is a threshold for the distance \(d\) between the RSU and the cluster head. When the distance exceeds the threshold, the energy consumption for message transmission by the cluster heads will be proportional to the distance \(d^{4}\), causing cluster heads located far from the RSU to deplete their energy rapidly and prematurely. In this paper, we propose replacing the clustering formation module in the LEACH protocol with density-based clustering Algorithm 1: the DBSCAN algorithm.