# A Distance-Vector-Based Multi-Path Routing Scheme for Static-Node-Assisted Vehicular Networks
## 4 MP-RDV: The Proposed Scheme
### Extending APD for Multiple Paths  
The next problem in designing MP-RDV is how to distribute the duplicated copies of a packet into multiple paths while preserving the expected packet delivery ratio. This is solved by extending the APD mechanism of RDV to fit to the multi-path case.  
Similar to the discussion of APD in RDV, let \(P\) be the preconfigured end-to-end expected delivery ratio to suffice. A node has two next-relays \(n_{p}\) and \(n_{s}\), which are the primary and the secondary ones. Let \(p_{p}\) and \(p_{s}\) be the corresponding paths to the destination, and we let the distance in carry of each be \(\delta_{p}\) and \(\delta_{s}\), respectively. Since MV-RDV forks delivery paths at every node in the forwarding paths, we further define variables related to the expected delivery ratio. Let \(P_{x}\) be the expected delivery ratio from node \(x\) to the destination. Note that \(P_{x}=P\) if \(x\) is the source node of the packet.  
A node \(x\) about to forward a packet first computes the expected delivery ratio for each path to the destination. If \(x\) has two paths \(p_{p}\) and \(p_{s}\) to deliver packets, we let the expected delivery ratio for each of them be the same value \(P_{x}^{\prime}\). To achieve the expected delivery ratio \(P_{x}\) using those two paths, \(P_{x}^{\prime}\) must hold the following equation:  
\[1-P_{x}=(1-P_{x}^{\prime})^{2}, \tag{5}\]  
Figure 6: The flowcharts of routing-table updates in RDV and MP-RDV (Multi-Path RDV): MP-RDV maintains both the primary and secondary relays in the routing tables, and makes decisions on activating the secondary relay.  
which means that the packet loss probability from \(x\) to the destination is the same as the product of packet loss probability of two paths. From this, we obtain the following:  
\[P_{x}^{\prime}=1-\sqrt{1-P_{x}}. \tag{6}\]  
By applying \(P_{x}^{\prime}\) into the Formulas (1)-(3), we can obtain the number of duplicated packet copies \(D_{l}\) required for each path \(p_{p}\) and \(p_{s}\) to suffice \(P_{x}\).  
An example of APD in MP-RDV is shown in Figure 7. Suppose that a packet is generated at \(n_{1}\) and destines \(n_{4}\). Since \(P_{1}=P=99\%\), we obtain the expected delivery ratio for each path from Formula (6) as \(P_{1}^{\prime}=90\%\). From Formula (1), the expected delivery ratio \(E_{l}\) for each link \(l\) in \(p_{p}\) and \(p_{s}\) is computed as 96.54%. Thus, from Formula (3), and provided that the delivery ratio estimated by SVS is \(R_{(n_{1},n_{2})}=80\%\), \(n_{1}\) forwards \(D_{(n_{1},n_{2})}=2\) packets for the relay node \(n_{2}\). Similarly, for \(R_{(n_{1},n_{5})}=70\%\), \(n_{1}\) forwards \(D_{(n_{1},n_{5})}=3\) packets for \(n_{5}\).  
Note that the intermediate nodes such as \(n_{2}\) and \(n_{5}\) again fork paths. The required delivery ratio on \(n_{2}\), which is \(P_{2}\), is computed by the aggregation of expected delivery ratios in the primary path. Namely, in Figure 7, \(P_{2}=E_{(n_{2},n_{3})}E_{(n_{3},n_{4})}=93.20\%\). Note that \(E_{(n_{2},n_{3})}\) and \(E_{(n_{3},n_{4})}\) take the same value and the value is notified by the parent node \(n_{1}\) using the header space of data packets. This is formally written as follows. Let \(x\) be the parent node of \(y\) and \(\delta_{p}\) be the distance in carry from \(y\) to the destination. Then, the expected delivery ratio on \(y\) is computed as \(P_{y}=\delta_{p}E_{l}\), where \(E_{l}\) is notified by \(x\). Once the value \(P_{y}\) is computed, \(y\) again distributes packet copies using multiple next-relays in the same process as described above.