# A Distance-Vector-Based Multi-Path Routing Scheme for Static-Node-Assisted Vehicular Networks
## 4 MP-RDV: The Proposed Scheme
### Designing Delay Metrics for MP-RDV  
To compare the performance of delivery delay metric with RDV's built-in traffic-volume-based metric, we design the mechanism to apply the delay metric to MP-RDV. As a result, in MP-RDV, we can deploy either the traffic-volume metric or the delay metric described in this section. Same as the traffic-volume metric, the delay metric values are measured in cooperation with related nodes. The delivery delay on a path is defined as the sum of the transportation delays between nodes and the waiting delays on nodes on the path. The transportation delay is the time required for packets to travel among nodes, and the waiting delay is the time required for packets to wait on nodes until appropriate vehicles to pass the packet come. We designed the mechanism to collect those two sort of values and advertise them so that the delivery delay of any selected path is known in our distance-vector schemes. Waiting delays are measured by _Hello_ messages of RDV. We let \(W(n_{a},n_{b})\) be the average waiting delay on \(n_{b}\) for packets waiting for vehicles coming from \(n_{a}\). Namely, \(n_{a}\) is the previous-hop node for the packets' destinations. In this case, node \(n_{b}\) measures \(W(n_{a},n_{b})\). With Figure 8, we show the process to measure \(W(n_{a},n_{b})\). Let \(l_{i}(i=1,2,\cdots,k)\) be the time difference of the two sequential vehicles that arrives at \(n_{b}\) from \(n_{a}\). Within the time interval \(T\)  
Figure 7: Example of ADP in MP-RDV: When two relays are available, nodes such as \(n_{1}\) expect the same delivery ratio on both paths and computes the number of duplicated packets on each of them. the vehicles arriving at \(n_{b}\) is denoted by \(c_{i}(i=1,2,\cdots,m)\) sequentially, i.e., the first vehicle in \(T\) arriving at \(n_{b}\) is \(c_{1}\), and the last one is \(c_{m}\). We assume that the time on which packets arrive at \(n_{b}\) follows a uniform distribution. Then, if a packet arrives at \(n_{b}\) within the period of time \(T\), the probability that it appears in \(I_{i}\) is \(\frac{I_{i}}{T}\), and it's average waiting time is \(\frac{I_{i}}{2}\). Thus, the average waiting time \(W(n_{a},n_{b})\) is expressed as follows:  
\[W(n_{a},n_{b})=\sum_{i=1}^{k}\frac{I_{i}}{T}\frac{I_{i}}{2}. \tag{7}\]  
On the other hand, the transportation delay is measured through polling packets. Note that we define a new type of packets and pass a polling packet to every vehicle visiting the node. Every polling packet is carried to a neighbor node and the node gets to know the transportation delay between neighboring nodes. Note that _Hello_ packets are not used for this purpose because the transportation process of RDV allows relaying packets among vehicles. Let \(n_{a}\) be a neighbor of \(n_{b}\). Then, when a vehicle visits \(n_{a}\) and \(n_{b}\) in this sequence, \(n_{b}\) gets to know the transportation delay, denoted by \(D(n_{a},n_{b})\), between those two nodes \(n_{a}\) and \(n_{b}\). The average transportation delay \(\overline{D}(n_{a},n_{b})\) in the period of time \(T\) is computed from all the delay values collected on \(n_{b}\) in \(T\). If we assume time synchronization among every node, we can measure both the waiting and the transportation delays easily. However, even if we do not assume time synchronization among nodes, we can measure the waiting delay with clocks on stationary nodes, and the transportation delay with clocks on vehicles. Note that not so much accuracy is required to measure those delay values. The next step is to sum up those waiting and transportation delays as the routing metric values of links. See Figure 9. We expect a packet forwarded from \(n_{x}\) is relayed by \(n_{b}\) to reach \(n_{d}\). When a vehicle moves from \(n_{d}\) via \(n_{c}\) to \(n_{b}\), the measured average delays \(\overline{D}(n_{b},n_{c})\) and \(\overline{D}(n_{c},n_{d})\) are collected to \(n_{b}\) by RDV messages. On the other hand, \(n_{b}\) can compute the waiting delay for the previous node \(n_{a}\), i.e., \(W(n_{a},n_{b})\).