# Link-State Aware Hybrid Routing in the Terrestrial-Satellite Integrated Network +
## 3 System Model
### Link-State Aware Hybrid Routing Algorithm
#### 4.2.1 Time Interval Optimization-Based ISL Selection Algorithm  
To reduce the search space, according to the optimized time interval, the ISL selection algorithm is proposed. Assuming that data of multiple UTs can be transmitted independently, the routing mechanism of communication data for each UT can be designed independently, i.e., for the communication data of \(UT_{k}\), the route between candidate satellites associated with TSE can be determined. Since a TSE can only establish communication link with the covered satellite in the \(t-th\) time interval, we denote the set of association candidate satellite for \(g_{k}\) as \(\Phi_{s}\), thus we have  
\[\Phi_{s}=\{v_{i}^{t}|\omega(v_{i}^{t},v_{j}^{t})=1,\forall v_{i}^{t}\in V_{s},v_{j}^{t}\in V_{g}\}. \tag{21}\]  
For the ISL selection problem of different data flows \(UT_{k}\), the satellite routing selection problem can be presented as  
\[\begin{array}{ll}\underset{\omega}{\text{min}}&\sum\limits_{v_{i}^{t}\in \Phi_{s}}(\frac{d(v_{i}^{t},v_{j}^{t})}{v_{p}}+\frac{q_{i}^{t}(k)}{r(v_{i}^{t},v_{j}^{t})}+\frac{\vartheta(v_{i}^{t},v_{j}^{t})}{r(v_{i}^{t},v_{j}^{t})})} \leavevmode\
obreak\ \leavevmode\
obreak\ \omega(v_{i}^{t},v_{j}^{t})\\ \text{s.t}&C1,C4,C5.\end{array} \tag{22}\]  
This optimization problem is equivalent to determining the shortest path between satellites, based on the dynamic link information, a Time interval optimization-based Satellite Routing (TSR) algorithm is proposed to solve the shortest path problem, which is summarized in Algorithm 1. Firstly, TSR checks that if the destination satellite \(v_{d}\) is an alive neighbor node of source satellite \(v_{0}\) in the initialization phase. If \(v_{d}^{t}\in N_{0}\), the TSR algorithm will be ended and the data packet can be transmitted to the destination \(v_{d}\) directly. If \(v_{d}^{t}\
otin N_{0}\), the corresponding satellites of all alive neighbor satellites in \(v_{0}\) will be added into source set \(\Phi_{0}\). The transmission rate from \(v_{i}\) to the alive neighbor node is used to calculate the transmission delay. Algorithm 2 is in charge of maintaining the link delay, and the greedy approach is used to find the shortest path from source satellite \(v_{0}\) to destination satellite \(v_{d}\).  
```
Input: Space-Time graph \(G_{s}(V_{s},E_{ss})\), source satellite \(v_{0}\in\Phi_{s}\), TTL of data packet, start time \(t\), data packet size \(x(v_{i}^{t},v_{j}^{t},k)\) Output: Router Table \(R_{s}\)
```
1:Initialize: Update router table and searched set \(\Phi_{d}\) by executing Algorithm 1  Let source set \(\Phi_{0}=\{s_{0},N_{s}\}\)  Set termination time \(t_{n}=t+TTL\)  Optimal set \(V_{opt}=\{T(v_{i}^{t}),p(v_{i}^{t})|v_{i}^{t}\in V_{s}\}=\emptyset\)
2:If\(N_{0}==\emptyset\)then
3: Return \(R_{s}\)
4:End
5:While\((V_{opt}\
eq\emptyset)\)do
6:foreach\(v_{i}^{t}\in\Phi_{0}\)do
7:If\(v_{i}^{t}\in\Phi_{d}\)then
8: Continue loop in line 6
9:End
10:\(\Phi_{d}=\Phi_{d}\cup\{v_{i}^{t}\}\)
11:Neighbor\((v_{0}^{t})\leftarrow\) Find all non-empty neighbor set of \(v_{i}^{t}\)
12: Update \(V_{opt}\) by executing Algorithm 1
13:End for
14: Extract \(v_{\min}^{t}\) which has minimum delay \(T_{\min}\) from \(V_{opt}\)
15: Add \(v_{\min}^{t}\) into \(\Phi_{0}\)
16: Add \(\{T_{\min},p_{\min}\}\) into \(R_{s}\)
17:Return\(R_{s}\) ```
**Algorithm 1** Time Interval Optimization-based Satellite Routing