## 3 SD-QGrid Routing Platform and Algorithms
### SD-QGrid Online Routing Decision Process
For example, as shown in Figure 11, the source vehicle \(v_{s}\) located in \(Grid_{A}\) carries the packet in the beginning. First, the associated RSU of \(v_{s}\) queries the SDN CN to retrieve the Q-table of \(Grid_{A}\) and those of neighbor grids, which are stored in the Q-table cache of the RSU. Then, the routing decision unit of the RSU finds the next-hop grids, i.e., \(Grid_{1,1}\), \(Grid_{1,2}\), and \(Grid_{1,3}\), with the top three large Q-values in the Q-table of \(Grid_{A}\). As shown in Figure 12, take the next-hop grid \(Grid_{1,1}\) as an example. The routing decision unit of the RSU further queries the Q-table of \(Grid_{1,1}\) to find the next-hop grid of \(Grid_{1,1}\) with the top three large Q-values of \(Grid_{1,1,1}\), \(Grid_{1,1,2}\), and \(Grid_{1,1,3}\), which constitute the two-hop next grid of \(Grid_{A}\). ``` Input:
1. The three next-hop grids, i.e., \(Grid_{1,1}\), \(Grid_{1,2}\), and \(Grid_{1,3}\) of \(Grid_{A}\). 2. The three two-hop next grids, i.e., \(Grid_{1,1,1}\), \(Grid_{1,1,2}\), and \(Grid_{1,1,3}\) of \(Grid_{1,1}\); \(Grid_{1,2,1}\), \(Grid_{1,2,2}\), and \(Grid_{1,2,3}\) of \(Grid_{1,2}\); \(Grid_{1,3,1}\), \(Grid_{1,3,2}\), and \(Grid_{1,3,3}\) of \(Grid_{1,3}\). 3. The next-hop candidate node x of node \(A\). Output:
1. \(TwoHopVal_{X}\)
2. \(OneHopVal_{X}\)
3. Definition:
1. \(TimeDiff^{X}_{X\to X^{\prime}}\) is the difference between the time when node \(X\) first enters \(Grid_{X}\) and the time when \(x\) first enters \(Grid_{X^{\prime}}\), according to its trajectory. Please note this notation indicates that node x does not pass through any other grid between \(Grid_{X}\) and \(Grid_{X^{\prime}}\). If \(Grid_{X}=Grid_{X^{\prime}}\), then the value of \(TimeDiff^{X}_{X\to X^{\prime}}\) is the minimum value 1. If node X does not pass through \(Grid_{X^{\prime}}\) in its trajectory, then the value of \(TimeDiff^{X}_{X\to X^{\prime}}\) is 0. 1 for\(t=\) (1, 2, 3) // Time difference between the current time in the current grid and the first position in the next-hop grid. If \(Grid_{X}=Grid_{A}\), calculate \(TimeDiff^{X}_{X\to 1,1}\) of node X from \(Grid_{X}\) to \(Grid_{1,1}\) If \(Grid_{X}=Grid_{1,1}\), \(TimeDiff^{X}_{X\to 1,1}=1\). // node x in the next - hop grid \(Grid_{1,1}\). for s = (1, 2, 3) //Calculate the time difference between the current time in the current grid and the first position in the first position in the two-hop next grid. If \(Grid_{X}=Grid_{1,s}\), \(TimeDiff^{X}_{X\to 1,s}=1\). // node x in the two - hop next grid \(Grid_{1,s}\). else // node x in the next-hop grid. Calculate \(TimeDiff^{X}_{X\to 1,s}\) of node x from \(Grid_{X}\) to \(Grid_{1,s}\) via \(Grid_{1,s}\). \(Find_{1,s}\) // node x first moves to \(Grid_{1,s}\), and then to \(Grid_{1,1,s}\). \(TimeDiff^{X}_{X\to 1,s}\) \(TimeDiff^{X}_{X\to 1,s}=TimeDiff^{X}_{X\to 1,s}-TimeDiff^{X}_{X\to 1,s}\) // \(TimeDiff^{X}_{X\to 1,s}\) of node x is the _TimeDiff_ from \(Grid_{1,s}\) to \(Grid_{1,s}\). 2 dst_grid = false
3 for\(t=\) (1, 2, 3) //calculate the one-hop weight \(V^{X}_{X\to 1,t}\), when node x is in the next-hop grid \(Grid_{1,t}\). if \(TimeDiff^{X}_{X\to 1,t}>0\): \(V^{X}_{X\to 1,t}=\) [ \(\frac{1}{Distance(X,D)}\times\frac{Qvalue^{D}_{t,s}}{TimeDiff^{X}_{X\to 1,t}}\) ] if \(Grid_{1,t}\) is the grid where the destination node is located: \(V^{X}_{X\to 1,t}=V^{X}_{X\to 1,t}\) *100 // let the weight \(V^{X}_{X\to 1,t}\) become much higher. dst_grid = true for s = (1, 2, 3) //calculate the one-hop weight \(V^{X}_{X\to 1,s}\), when node x is in the two - hop next grid \(Grid_{1,t,s}\). if \(TimeDiff^{X}_{X\to 1,t,s}>0\): \(V^{X}_{X\to 1,t,s}=\) [ \(\frac{1}{Distance(X,D)}\times\frac{Qvalue^{D}_{t,s}}{TimeDiff^{X}_{X\to 1,t,s}}\) ] if \(Grid_{1,t,s}\) is the grid where the destination node is located: \(V^{X}_{X\to 1,t,s}=V^{X}_{X\to 1,t,s}\) *100 // dst_grid = true \(OneHopVal_{X}=Max\left\{V^{X}_{X\to 1,t},\ V^{X}_{X\to 1,t,s}\right\}\) // the maximum weight among the one-hop weight \(V^{X}_{X\to 1,t}\) and the one-hop weight \(V^{X}_{X\to 1,t,s}\).