# Clustering-Based Data Dissemination Protocol Using the Path Similarity for Autonomous Vehicles
## 3 Proposed Method
### Data Dissemination Protocol  
#### 3.4.1 A Data Dissemination Algorithm  
As described above, this protocol includes a data dissemination process. The main algorithm of the data dissemination process is given in Algorithm 3. Since Algorithm 3 can be described as a callback procedure that processes a message as it is received by each node, the time complexity is O (1).  
```
Parameter \(m\): received message, \(n\): current node
1. If \(n\) is in a cluster, then
2. If the source's cluster ID \(\
eq\)\(n\)'s cluster ID, then
3. Set \(m\)'s source and cluster ID field to \(n\)'s and broadcast \(m\)
4. Else if \(n\) is the cluster head, then
5. Set \(m\)'s source to \(n\)'s and broadcast \(m\)
6. Else then
7. Drop \(m\)
8. Else then
9. Set \(m\)'s source to \(n\)'s and broadcast \(m\)
```  
**Algorithm 3** Data dissemination algorithm  
When node \(n\) receives a dissemination message, it first checks to see if it belongs to a particular cluster. That is, it is verified that \(n\) is an unclustered node.  
If the node is an unclustered node, the message is retransmitted because it is more important to reduce the redundancy than to increase the data propagation rate. When retransmitting, the source ID of the message is changed to itself and the cluster ID is \(-1\), that is, an unclustered node.  
If node \(n\) is a cluster head or a cluster member, we verify that the source cluster ID of message m is equal to itself. If it is not the same and if \(n\) is a head, we broadcast the field by changing the field of \(m\). Additionally, \(m\) is stored in list \(lst\), including the time it was passed. In the case of a message received from the same cluster member, retransmission is performed when there is a neighbor node belonging to another cluster. If not, message \(m\) is dropped.  
The cluster head receives a neighbor attention message when it encounters a new neighbor cluster from its neighboring member nodes. At this time, if a message not previously transmitted is stored in \(lst\), it is broadcasted. It also updates the timestamp of the message.  
If timeout tm has elapsed since the time of the first delivery of the message in \(lst\), the message is deleted from \(lst\). Timeout \(t_{m}\) is calculated as Equation (7).  
Figure 13: PCDP Path Announcement Message.  
\[t_{m}=\frac{2d_{l}}{v} \tag{7}\]  
In Equation (7), \(v\) is the average speed (m/s) measured over the last minute of the head and \(d_{l}\) is the length of the normal block. In other words, this means that the message is stored and transmitted while passing through two blocks. Therefore, more messages are propagated to other clusters, and the information propagation rate of the entire network can be increased.  
As shown in Figure 14, messages are stored in the list with the message specific ID. This field is an ID for internal identification, and it does not matter whether it is a non-overlapping line (such as a hash) using a source cluster ID that is first received and a timestamp of the first received time.  
Next, whenever a member encounters a new cluster, it forwards the cluster attention message to the head. At this time, the head broadcasts the stored message and records it in the forwarded message table.  
Figure 15 shows the forwarded message table, which is described above. A cluster head does not broadcast if there is already a transmission record in the forwarded message table. If the message is timed out, the related record in the forwarded message table is dropped. Through this process, more redundant messages can be reduced.