## 3 SD-QGrid Routing Platform and Algorithms
### SD-QGrid Online Routing Decision Process  
The SD-QGrid has to execute the online routing decision process when a vehicle node \(v_{i}\) carrying a packet intends to transmit a certain packet in grid \(G_{i}\) to the destination vehicle node \(v_{d}\) located in the destination grid \(G_{d}\). As the offline process has been completed, each grid has a precalculated Q-table stored in the Q-table database of the SDN CN. Assume each vehicle \(v_{i}\) knows its GPS location \((X_{i},~{}Y_{i})\), its neighbor nodes within a range \(\big{(}V_{0},~{}V_{1},~{}\ldots,~{}V_{j}\big{)}\), and vehicle future movement trajectories. As shown in Figure 8, the associated RSU of the packet-carrying node will perform the online routing decision process, which contains the following steps:  
1. The packet-carrying node issues a _Neighbor Query_ packet to its RSU. This Neighbor Query packet contains vehicle IDs of the packet-carrying node, its neighbor nodes, and the destination node. 2. As the RSU receives the Neighbor Query packet, it stores those vehicle IDs first. Then, it uses them to check whether historical trajectories of neighbor nodes of the packet-carrying node can be found on its trajectory cache and whether Q-tables of the grid where this RSU belongs to and the eight neighbor grids have been cached in it. If yes, it proceeds to Step 3. If not, it will notify the SDN CN to sends back only the missing historical trajectories of neighbor nodes and Q-tables of its associated grid and eight neighbor grids from the trajectory database and Q-table database, respectively. Then, these missing data are cached on the trajectory cache and Q-table cache of the RSU. 3. From the Q-table of this grid, 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. 4. 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 as the relay the  
Figure 7: SD-QGrid learning process executed by the SDN CN. neighbor node whose future driving trajectory continues along the best next-hop grid and the best two-hop next grid. 5. Finally, the RSU issues the _Neighbor Response_ packet containing the vehicle ID of the selected neighbor node to inform the packet-carrying node to forward the packet to this neighbor node. Hence, THTR finds a better packet transmission route, improves the packet delivery ratio, and reduces the end-to-end delay in the V2X environment. Figure 9 shows that the best next-hop grid of \(Grid_{A}\) is \(Grid_{A,1}\) and the two-hop next-grids of \(Grid_{A,1}\) are \(Grid_{A,1,1}\) and \(Grid_{A,1,2}\). If a node's driving trajectory passes through the best next-hop grid and the best two-hop next grid in the left picture, i.e., from \(Grid_{A,1}\) to \(Grid_{A,1,1}\), which is more in line with the overall directionality of packet transmission from the start point \(v_{s}\) to the end point \(v_{d}\), then this node is a better next-hop packet-forwarding node. Conversely, if the driving trajectory of a node passes through the best next-hop grid \(Grid_{A,1}\) and the two-hop next grid \(Grid_{A,1,2}\), which is not the best two-hop next grid of \(Grid_{A,1}\) in the right figure, it can be seen that the vehicle node deviates from the overall directionality of the packet transmission, as compared to the vehicle on the left. Hence, this vehicle is not a good relay node. Figure 8: The online routing decision process of SD-QGrid. Figure 9: An example of the two-hop next grid in SD-QGrid. 3.4.1. The Link Expiration Time (LET) between Two Nodes  
Additionally, we use the location prediction mechanism to calculate the _link expiration time_ (LET) [31] of the adjacent vehicle, that is, the possible connection time between the current node and the adjacent node.