# Link-State Aware Hybrid Routing in the Terrestrial-Satellite Integrated Network +
###### Abstract
To the best of our knowledge, the combination of terrestrial and satellite networks is still an open issue, and the hybrid routing design problems jointly considering the practical issues mentioned above are still missing, thus motivating our investigation in this paper. In this work, a link-state aware Terrestrial-Satellite Hybrid Routing (TSHR) algorithm is proposed to find a data transmission path that spans both inter-satellite and terrestrial links for TSIN. Firstly, a space-time topology graph is proposed to analyze the dynamic relationship of network resources in the time and space domain. Then, under the communication link capacity and connection constraints, the hybrid routing problem is modeled as an integer linear programming problem. The inter-satellite link and terrestrial-satellite link connection are time-varying and intermittent in TSIN, which makes the optimal data transmission path planning a challenging issue. By exploiting the space-time topology structure, we propose a Time interval optimization-based Satellite Routing (TSR) algorithm to resolve the optimum inter-satellite link connection problem. Based on the TSR algorithm, with an objective of minimizing the end-to-end delay for most reliable connections, the hybrid TSIN routing problem is formulated and transformed into a weighted bipartite graph matching problem for solution search. Then, the TSHR algorithm is proposed to find the optimal TSE-satellite communication link connection. The contributions of this paper are summarized as below:  
* Link-state aware hybrid routing: Although existing works have already studied the communication link planning according to the network topology information, the intermittent and dynamic nature of the TSE-satellite link selection is still missing. In our work, we propose a link-state aware hybrid routing scheme for data transmission in the dynamic TSIN. The design is under a practical communication scenario that the link connections in satellites and resources are time-varying. By deriving the delay of both inter-satellite and TSE-satellite links, we formulate a hybrid routing problem aimed at minimizing the data transmission delay by optimally selecting the inter-satellite and TSE-satellite links. * Characterization on TSIN topology: The updating time of the topology structure is assumed to be a fixed time interval in existing models, which introduces significant difficulties in balancing the network overhead and accurate transmission delay. To tackle this issue, we propose a space-time topology graph to represent the data transmission process in dynamic TSIN, where the link resources in both the spatial and temporal dimensions are quantified. In particular, we derive the optimal time updating interval of the topology relationship, with which the effectiveness and accuracy of obtaining the hybrid path can be balanced. * Decomposition solution: The inter-satellite link and terrestrial-satellite link connection are time-varying and intermittent in TSIN, which makes the optimal data transmission path planning a challenging issue. By exploiting the space-time topology structure, we propose a satellite link selection algorithm to resolve the optimum inter-satellite link connection problem. Then, a hybrid routing algorithm based on a bipartite graph is proposed to determine the optimal TSE-satellite communication link connection, which can solve the subproblems with smaller sizes. The rest of this paper is organized as follows. Section 2 reviews the related works, then the system model is described together with a space-time topology model, based on which the delay minimization problem is formulated in Section 3. In Section 4, the TSIN hybrid routing scheme is proposed. Finally, we provide our simulation results in Section 5 and conclude this paper in Section 6.