# Optimal Path Routing Protocol for Warning Messages Dissemination for Highway VANET
## 3 Proposed Protocol
### Cluster Formation Phase  
The following assumptions are taken into account by OPRP:  
* Each node starts in a safe state, with no probability of crashing.
* Each node has the on-board unit (OBU) for communication and a Global Positioning System (GPS) for positioning.
* Each node can determine its direction, speed, location, and deceleration or acceleration.
* Each node may calculate its maximum average radio range based on its surroundings, which can be utilized to connect and communicate with the other nodes.  
Ordinary vehicles (OV) and CHs are the two types of nodes that the suggested OPRP applies to. A CH is in charge of the cluster and keeps a record of all nodes that make up the cluster. An OV represents a non-CH member node. A CH constructs a list of each of its member nodes, which includes current location, current speed, node-id, expected state, and acceleration/deceleration. The following are possible states for a node:  
* The node moves forward from a standstill to enter the highway. In this circumstance, it will either join an established cluster or establish its cluster.
* The node maintains the same direction and speed on the highway. In this situation, it continues to move with the same cluster. During the travels, its speed may alter as it accelerates or decelerates with time, resulting in a change in its cluster.
* While moving with the highway, a node may reverse its heading and begin moving in the opposite direction. This will result in a cluster change for this particular node.  
This subsection of the suggested OPRP describes cluster creation, including how nodes can find their neighbors and enter or depart a cluster. The k-medoids algorithm is possibly a better option for clustering based on the benefits stated in the previous section. The simple k-medoids approach, on the other hand, is insufficient for clustering bi-directional road traffic. The direction parameter is considered to accommodate bi-directional road traffic. To that end, in the suggested OPRP, we present a variation to the fundamental k-medoids algorithm and employ the modified form for clustering. The rest of this section explains the various phases required in clustering in a bi-directional environment using the revised k-medoids algorithm.  
\begin{table}
\begin{tabular}{l l} \hline \hline
**Notation** & **Description** \\ \hline \(E_{p}\) & End-to-end delay for packet \\ \hline \(E_{r}\) & End-to-end delay ratio \\ \hline \(\eta\) & Euclidean distance \\ \hline \(\kappa\) & Hamming distance \\ \hline \(n\) & A member node \\ \hline \(N\) & Set of all nodes \\ \hline \(NG\) & Neighboring table for a node \\ \hline \(NID\) & Node identity \\ \hline \(p_{l}\) & Packet dropped \\ \hline \(Pr\) & Packet loses rate \\ \hline \(Pt\) & Total packet transmitted across the network \\ \hline \(R_{p}\) & Total received packet \\ \hline \(S\) & Source node \\ \hline \(\tau\) & Timestamp for the last received \(ACK\) \\ \hline \(T_{r}\) & Network throughput \\ \hline \(\gamma\) & The direction of the node \\ \hline \hline \end{tabular}
\end{table}
Table 2: _Cont._