# A Distance-Vector-Based Multi-Path Routing Scheme for Static-Node-Assisted Vehicular Networks
## 3 RDV: The Base Scheme
### Distance-Vector Based Routing Strategy  
RDV is designed for vehicular networks to work based on a traditional distance-vector based routing strategy. RDV autonomously detects neighborhoods via control messages to build the shortest-paths so that it does not require map information. Since RDV is independent from maps, RDV is free from maintenance and synchronization cost of map information. Based on the distance-vector routing strategy, nodes in RDV exchange messages periodically to build their routing tables. In the routing table of each static node, a static node in 1-_carry_ distance is specified as the _next-relay_ for each destination. Since packets are delivered according to routing tables, a packet forwarding path is defined as a chain of static nodes within 1-_carry_ distance.  
When a node A is going to forward a packet to a 1-_carry_ neighbor B, A finds a vehicle that will visit B with high probability, and pass the packet to it. To find a suitable vehicle to pass packets, RDV has a mechanism called SVS (Statistic-based Vehicle Selection), which predicts vehicles that will visit the specified neighbor from the statistical measurements. In SVS, _Hello_ messages are sent from each static node to its 1-_hop_ and 2-_hop_ neighbors by storing a _Hello_ message on each vehicle that visits the node. Each node obtains local trajectory information via _Hello_ messages. By sharing the information among neighborhoods using _Statistic_ messages, every node is ready to compute the best \"previous-hop\" neighbor node, i.e., the vehicles coming from which will with high probability go to the specified _next-relay_ node.  
To build a routing table, each node must know the neighbors within 1-_carry_ distance. To find 1-_carry_ neighbors, RDV uses _Single-carry_ messages. Each vehicle distributes the statistical information of SVS with _Single-carry_ messages along the roads that the vehicle goes through. As a result, static nodes discover all of their 1-_carry_ neighbors, to which packets are delivered with a single vehicle with high probability. The probability of packets to reach a 1-_carry_ neighbor is computed as the product of 1-_hop_ delivery ratios collected along with the path to the neighbor.  
Each node propagates its 1-_carry_ neighbors with _Multi-carry_ messages in the manner of distance-vector routing. Specifically, a _Multi-carry_ message propagates a set of distance-vectors (i.e., basically a set of destinations and the distances for them) to sender's 1-_carry_ nodes. As a result of repeated message propagation, all static nodes finally find the shortest paths for all destinations, and their routing tables have entries for every reachable static node.  
With the routing tables computed above, a packet is forwarded to its destination via several intermediate nodes. The next intermediate node for a destination is called _next-relay_, which is retrieved from the routing table at each node. Note that the routing table includes the best _previous-hop_ node, the vehicle from which will visit the next-relay with high probability. Thus, when a static node is to forward a packet, it consults with its routing table and find the _previous-hop_ node, and passes the  
Figure 1: Definitions of Distance Units: The unit _hop_ represents the number of static nodes on the path. The unit _carry_ represents the number of vehicles required to forward packets on the path.  
packet to the vehicle that comes from the _previous-hop_ node. By repeating this forwarding process at each intermediate node, packets finally reach their destinations.