## 3 SD-QGrid Routing Platform and Algorithms
### SD-QGrid Online Routing Decision Process
If the calculated LET is not smaller than the minimum time to completely forward a packet from the current node to the adjacent node, this adjacent node is considered as an eligible candidate relay node in the online routing decision process. It is assumed that the clocks of all vehicle nodes in the network are synchronized. At a certain point in time, let (\(x_{i}\), \(y_{i}\)) and (\(x_{j}\), \(y_{j}\)) be the two-dimensional coordinate positions of vehicles \(i\) and \(j\). \(\theta_{i}\), \(\theta_{j}\) (\(0\leq\theta_{i}\), \(\theta_{j}<2\pi\)) and \(v_{i}\), \(v_{j}\) are the moving directions and moving speeds of \(i\) and \(j\), respectively, and r is the transmission range of wireless signals between vehicle nodes. We can use Equation (5) to calculate the \(LET_{ij}\) that vehicles \(i\) and \(j\) can maintain their connections because both of them stay within the wireless communication range:  
\[LET_{ij}=\frac{-(ab+cd)+\sqrt{\left(a^{2}+c^{2}\right)r^{2}-\left(ad-bc\right) ^{2}}}{a^{2}+c^{2}} \tag{5}\]  
where:  
\(a=v_{i}\) cos \(\theta_{i}-v_{j}\) cos \(\theta_{j}\)  
\(b=x_{i}-x_{j}\)  
\(c=v_{i}\) sin \(\theta_{i}-v_{j}\) sin \(\theta_{j}\)  
\(d=y_{i}-y_{j}\)  
if \(v_{i}=v_{j}\) and \(\theta_{i}=\theta_{j}\), \(LET_{ij}=\infty\). 3.4.2. Routing Decision Unit of RSU  
As mentioned above, the routing decision unit of the RSU first selects the grid with the largest Q-value among the eight neighbor grids as the best next-hop grid from the Q-table of this grid. According to the best next-hop grid, Q-tables of the eight neighbor grids, and historical trajectories of the neighbor nodes of the packet-carrying node, the RSU then executes the two-hop trajectory-based routing (THTR) algorithm to select the neighbor node as the relay whose future driving trajectory continues along the best next-hop grid and the best two-hop next grid. The flow of the SD-QGrid routing decision process, shown in Figure 10, is listed as follows:  
Step 1: Determine whether the packet-carrying node \(v_{i}\) is the destination node. If so, go to Step 9; if not, go to Step 2. Step 2: Determine whether \(v_{i}\) has any neighbor node. If so, go to Step 3; if not, go to Step 8. Step 3: For some neighbor node \(v_{j}\) of \(v_{i}\) located in the neighbor grid \(G_{j}\), test whether the Q-value \(Q_{j}\) of the neighbor grid \(G_{j}\) is higher than the Q-value \(Q_{i}\) of grid \(G_{i}\), where the vehicle \(v_{i}\) is located. If so, go to Step 4; if not, go to Step 6. Step 4: If the moving direction of the neighbor node is known and it has a fixed route and schedule (such as a bus), go to Step 5; if not, go to Step 6. Step 5: Execute Algorithm 1. If the best next-hop node \(v_{k}\) exists, go to Step 7; if not, go to Step 8. Step 8: Vehicle \(v_{i}\) continues to hold the packet and waits for the next transmission opportunity. Go to Step 1. Step 9: If the current node is the destination node, the entire routing decision process ends. Figure 10: Flow of the SD-QGrid online routing decision process. Algorithm 1 uses the Q-value to calculate up to nine (next-hop grid, two-hop next grid) combinations based on the grid \(Grid_{A}\) where the current packet is located. It then selects the two-hop next grid combination, depending on the next-hop grids with the top three Q-values in line 5. For all neighbor nodes \(B\) of \(A\), Algorithm 1 uses the link expiration time of adjacent vehicles to filter the candidate relay nodes in line 8. It calls Algorithm 2, i.e., the One-Two-Hop Value (\(A\), \(B\)), in line 9 to obtain \(TwoHopVal_{B}\) and \(OneHopVal_{B}\). Lines 11 and 12 find out which neighbor node owns the maximum \(TwoHopVal\) and \(OneHopVal\) values among all neighbor nodes, respectively. The vehicle with the highest value is selected as the relay node for packet forwarding. In addition, we preferentially select vehicle nodes whose trajectories pass through both the next-hop grid and the two-hop next grid in line 13, and then, select vehicle nodes that only pass through the next-hop grid in line 15 for packet forwarding.