# Link-State Aware Hybrid Routing in the Terrestrial-Satellite Integrated Network +
## 3 System Model
### Link-State Aware Hybrid Routing Algorithm
#### 4.2.2 Hybrid Routing Algorithm Based on Bipartite Graph  
Since TSE may choose different candidate satellites as the access satellite for transmitting the k-th data flow, based on the TSR algorithm, the end-to-end hybrid routing problem in TSIN can be constructed as follows  
\[ \begin{array}{ll}\min\limits_{\omega,\vartheta}&\sum\limits_{(s_{i}^{t},s_{ j}^{t})\in\Phi_{s}}[T(v_{i}^{t},v_{j}^{t})\omega(v_{i}^{t},v_{j}^{t})+T_{\min}(s_{i}^{t},s_{ j}^{t})],\\ \text{s.t}&C2-C6.\end{array}  \tag{23}\]The optimization problem can be regarded as a matching problem in the bipartite graph. To solve this problem, the link connection during each time interval \(t(1\leq t\leq D)\) is modeled as a weighted bipartite graph \(G^{{}^{\prime}}(V_{1},V_{2},E^{{}^{\prime}})\), wherein, \(V_{1}\) represents the set of candidate satellites associated with TSE, \(V_{1}\in\Phi_{s}\). \(E^{{}^{\prime}}\) represents the path set between candidate satellites and the link set between UTs and candidate satellites, the weight set of \(E^{{}^{\prime}}\) is represented as follows  
\[\delta(v_{i}^{t},v_{j}^{t})=\left\{ \begin{array}{l}T_{\min}(v_{i}^{t},v_{j}^ {t}),(v_{i}^{t},v_{j}^{t})\in\Phi_{s},\\ T(v_{i}^{t},v_{j}^{t}),\textit{otherwise}.\end{array} \right. \tag{24}\]  
Let \(c(UT_{k}^{t})\) denote the data volume of \(UT_{k}\) through link \((s_{i}^{t},s_{j}^{t})\), then the data volume in the next interval is expressed as:  
\[\vartheta(v_{i}^{t},v_{j}^{t},k)=\vartheta(v_{i}^{t-1},v_{j}^{t-1},k)-c(UT_{k }^{t}). \tag{25}\]  
Based on the constructed bipartite graph, minimum weight matching is modeled to obtain the link connection planning between UTs. Since the Kuhn-Munkres (KM) algorithm is an efficient matching algorithm [40], KM algorithm is used to solve the optimal matching problem on the bipartite graph. Algorithm 3 gives the KM-based link selection algorithm to obtain the best matching of \(G^{{}^{\prime}}(t)\), then the shortest delay hybrid path can be found through Algorithm 4. ```
Input: Bipartite graph, the minimum matching \(H(t)\) of \(G^{0}(t)\) Output: link selection in t-th \(R_{t}\)
1:Initialize:\(l(v_{i}^{t})\)
2:Foreach\(G_{t}(t)\in G^{{}^{\prime}}(t)\)do
3:If\(H(t)\
otin R_{t}\)then
4:\(P=\{v_{j}^{t}\}\), \(Q=\emptyset\), \(N_{p}=G^{{}^{\prime}}(t)\cup\{P\}\)
5:If\(N_{p}\
eq Q\)
6: Continue loop in line 2
7:End
8:If\(N_{p}=Q\)then
9:\(\Delta=\min_{u,v}\{l(v_{i}^{t})|l(v_{i}^{t})+l(v_{j}^{t})-w(v_{i}^{t},v_{j}^{t }),v_{i}^{t}\in P,v_{j}^{t}\in V_{2}-Q\}\)
10:\(l^{{}^{\prime}}(v_{i}^{t})=\left\{ \begin{array}{l}l(v_{i}^{t})-\Delta,v_{i}^ {t}\in P\\ l(v_{j}^{t})+\Delta,v_{i}^{t}\in Q\\ l(v_{i}^{t}),\textit{otherwise}\end{array} \right.\)
11:End
12:End
13: Extract \(H(t)\) in \(R(t)\)
14:End
15:Return\(R_{t}\)
```  
**Algorithm 3** KM-based Link Selection  
In TSHR, the source TSEs will collect the link state and queuing delay information of each satellite to build the routing information table. To collect the real-time status of neighbor nodes, each TSE should periodically broadcast data packets to neighbor satellites and terrestrial nodes. After receiving the response packet, the neighboring relationship is established and link information would be recorded in the routing data table. As shown in Figure 5, for the node's RREP header, the bandwidth and cache packet information would be writen in the reserved domain, then the information is exchanged with their neighbors by the RRER packet. In the beacon protocol, each satellite node will broadcast the beacon packet periodically to collect status (e.g., queuing delay, transmission rate) of neighbor satellites. When the beacon packet is received, the sender will be marked as an alive neighbor and information contained in the beacon packet will be saved. When there are no packets received after three broadcast periods, the link will be regarded as interrupted and the neighbor will no longer be treated as alive. In the following figure, satellite-1, satellite-2, and satellite-3 are neighbors with each other.