# Optimal Path Routing Protocol for Warning Messages Dissemination for Highway VANET
## 3 Proposed Protocol
### Cluster Formation Phase
#### 3.2.2 Node Joining a Cluster  
When different nodes come in, a highway becomes crowded with clusters. The highway's first node forms its cluster and deputizes itself as a CH. The CH is re-selected for every cluster when the number of nodes within cluster grows, as explained in Section 3.2.3. A candidate node, a node that wants to join the cluster, sends out a Hello message. The OVs ignore this communication, but all CHs in the vicinity acknowledge it. The number of acknowledgments a candidate node receives is the number of available clusters (k) for the k-medoids algorithm. The distance betwixt this candidate node and every CH is calculated when the position information is shared. The nearest CH is found, so this applicant node joins that cluster to which it belongs. Suppose a candidate node cannot find a cluster--i.e., it receives no acknowledgment in reply to a Hello message. The candidate node builds its cluster and deputizes itself as the CH. The main k-medoids algorithm [20] uses Manhattan distance for clustering. In contrast, the modified k-medoids algorithm presented in this paper for OPRP employs two metrics, Euclidean distance, and Hamming distance, to create clusters. The first metric, Euclidean distance, calculates the distance between a candidate node and all of the CHs nearby. Hence,  
\[\eta(x,y)=\sqrt{\left(x_{1}-x_{2}\right)^{2}+\left(y_{1}-y_{2}\right)^{2}}, \tag{1}\]where \(\eta\) denotes the Euclidean distance calculated between the CHs and applicant node with coordinates (\(x_{1}\), \(y_{1}\)) and (\(x_{2}\), \(y_{2}\)), respectively. The Hamming distance function, which includes the bi-directional aspect of a road traffic flow, is the next metric computed after the Euclidean distance. The nodes on the highway can move in opposite directions because the bi-directional heterogeneous traffic allows it. Hamming distance function calculates in light of the difference in travel directions between an applicant node and a CH. The result is 1 if a candidate node and the CH have the same direction and 0 if they have the opposite direction [33]; i.e.,  
\[\kappa= \begin{cases}1&if~{}=~{}\text{same}\\ 0&if~{}=~{}\text{opposite},\end{cases}  \tag{2}\]  
here, the Hamming distance is denoted by \(\kappa\), and the direction is represented by regardless of the node type (i.e., OV or CH). It is essential to rely on the two metrics described above when connecting nodes to a cluster. Assume, for instance, that Node A is located 3 m from C2: CH and 4 m from C3: CH in Figure 3. This node will connect to C2 using simply the distance factor. This should not occur, since Node A and the members of C2 are traveling in opposing directions, and Node A joining C2 would destabilize the cluster rather than serve a proper function. OPRP suggests Equation (3) to solve this problem, which determines the ultimate distance by adding the directional components and relative components. By applying this criterion, the distance between Node A and C2: CH increases to infinity while the distance between Node A and C3: CH stays at 4 m. As a result, Node A will join C3. As a result, by associating the node with the cluster in the same direction, a node equation used in a modified k-medoids algorithm for OPRP favorably and efficiently contributes to the definition of stable clusters. Hence,  
\[\delta=\frac{\eta}{\kappa} \tag{3}\]  
where \(\delta\) stands for the relative distance between two adjacent nodes. The distance with all neighboring CHs is calculated by Equation (3) because OPRP considers the attachment of the candidate node to the cluster upon the shortest distance from the appropriate CH. Additionally, Equation (4) locates a CH with the smallest distance  
Figure 3: Cluster formation in bi-directional. and links the node to the relevant cluster, converting that candidate node's position to that of the member node.