卫星互联网资源调度技术研究与国家的重大战略发展需求相一致。2020年，我国正式明确新基建的概念范围，其中信息基础设施部分主要包括“以5G、物联网、工业互联网、卫星互联网为代表的通信网络基础设施”，卫星互联网首次被纳入新基建范畴。与传统地面通信网络相比，卫星互联网具有全球覆盖、链路鲁棒以及端到端传播时延短的特征，可广泛应用于数据传输、对地观测以及移动边缘计算等场景，具有重要的战略发展意义。然而，卫星互联网面临多维资源难表征、难调度的挑战。一方面，卫星互联网网络拓扑时变、网络资源多维异质且相互耦合，难以精准刻画网络中的资源状态，同时，地面静态网络资源调度技术在时变的卫星网络中不适用；另一方面，传统互联网中数据传输仅需要链路资源，卫星互联网中应用往往有着复杂的多维资源需求。例如，对地观测应用对观测、传输以及存储资源有着耦合需求；计算应用对存储、传输以及计算资源有耦合需求。现有资源调度方法往往忽略应用耦合的资源需求，将应用分阶段独立调度，例如对地观测应用调度往往被拆分成独立的观测卫星的调度与观测数据的回传调度，导致网络资源利用率低。此外，现有资源调度问题往往采用数学规划方法进行建模求解，该类代数域方法在网络规模较大时具有算法运行时间长以及内存占用高的弊端，难以即时调度多维资源。因此，亟需设计应用驱动的多维资源快速调度方法，以提升网络资源利用率。为满足卫星互联网中应用的多维资源即时调度需求并提升网络的资源利用率，需研究应用需求与网络多维资源的统一表征方法，并基于该方法设计应用驱动的高效调度方法。基于此，本文基于时变图理论，分别研究卫星互联网3 种典型应用驱动下的多维资源调度方法，以降低应用的完成时延并提升网络的资源利用率。本文的主要研究内容及成果如下：1. 针对卫星互联网中数据传输问题求解算法可扩展性差的问题，提出基于时变图的增量数据最短时延多路径路由算法。所提方法通过动态配置存储资源，可增量求解通信和存储资源联合调度问题。具体地，提出一种基于最大流算法的增量算法，该方法在计算过程中逐步增大作为问题输入的网络规模，并求解不同网络规模下的端到端传输容量，直到所求解网络容量不小于业务数据量。算法在求解过程基于历史的计算结果进行增量求解，避免在网络规模增大后从头计算网络流。最大流算法的增量特性保障了该算法的正确性。所提算法复杂度仅需( · g)，相比于经典算法的复杂度―― ( · log() · g)，降低了(log())。基于该最短时延方法，进一
步提出基于时间扩展图的增量最大流算法，该算法复杂度低于传统最大流算法。最后，为验证所提方法的性能，提出经典算法的2 种变形方法进行比较。实验结果表明，所提方法运行时间在网络规模或任务量增加时均具有良好的可扩展性，证明存储与通信资源联合计算可有效提升算法的运行速度。2. 卫星互联网中对地观测应用中观测、通信与存储资源独立调度，导致网络资源利用率低以及数据回传时延长。针对该问题，提出高资源利用率的观测传输按需调度方法。首先，首次将观测与传输存储联合调度问题建模成一个线性规划问题，该问题支持网络拓扑的按需配置以最大化观测任务的回传数据量。然而，求解该线性规划问题在网络规模很大时内存占用大且运行时间长。为解决该问题，进一步采用时间扩展图表征卫星网络的节点与通信链路，并引入了辅助顶点和边以表征该线性规划问题中特殊的约束。基于该表征方法，可将观测、传输与存储联合调度问题转化为最大流问题，可采用所提增量最大流算法高效求解该问题。仿真实验采用真实的星链与高分卫星轨迹构建网络拓扑，作为问题的输入。实验结果表明，在网络中的业务负载较重时，网络拓扑按需规划后的网络吞吐量相比于网络拓扑提前规划可提升180%。此外，在网络中负载较轻时，观测任务与传输任务联合调度相比于观测传输独立调度可将网络吞吐量提升100%，证明对地观测应用中观测资源与通信资源联合调度的必要性。3. 针对卫星互联网中计算应用的计算需求难表征和存储资源受限下多维资源难调度导致的计算应用完成时延长的问题，提出基于时变图的传输、计算与存储资源联合调度算法。首先面向数据包，将存储受限下任务的传输和计算联合调度建模为整数规划问题，该问题首次给出计算任务需求的数学表达式。为进一步降低该问题的变量与规划个数，基于约束转化策略，构建面向流的混合整数线性规划问题。然而该问题的标准求解方法在网络规模较大时运行时间过长。基于此，提出增强存储时间聚合图模型，联合表征存储、计算以及传输资源。基于该图模型，提出缓存受限下计算应用的单路径最短时延路由方法。相比于传统路由策略，该方法允许多节点存储资源联合利用，从而降低业务端到端传输时延。仿真结果表明所提方法相比于标准的混合整数线性规划求解算法，运行速度可提升上千倍，同时应用完成时延比最优解增加不到10%。此外，相比于经典的路由方法，所提方法可将应用时延降低20% 并将网络吞吐量提升40%。证明计算应用中存储资源、传输资源与计算资源联合调度的必要性。

The research on resource scheduling technology over Satellite Internet is consistent with the major needs of strategic development in China. In 2020, China officially clarified the scope of “ New Infrastructure” concept，where the “Information Infrastructure” mainly includes “communication network  infrastructure represented by 5G, Internet of Things, Industrial Internet, and Satellite Internet”. Particularly, Satellite Internet was included in the category of “New Infrastructure” for the first time. Compared with traditional terrestrial communication networks, Satellite Internet is characterized by global coverage, robust links, and short end-to-end propagation delay. It can be widely applied to scenarios such as data transmission, earth observation, and mobile edge computing. It has great significance
in strategic development. However, Satellite Internet encounters the challenges that representing and scheduling the multi-dimensional resources are difficult. On the one hand, the topology of Satellite
Internet changes with time and the resources are multi-dimensional, heterogeneous and coupling with each other, causing the resources state difficult to represent. Meanwhile, the resource scheduling technology of terrestrial static networks does not apply to Satellite Internet. On the other hand, data transfer only requires link resources in traditional Internet,
while applications have integrated requirements for multi-dimensional resources in Satellite Internet. For instance, earth observation application has the coupled requirements for observation, transmission and storage resources, while the computing applications requires the simultaneous involvement of storage, transmission and computing resources. Existing resource scheduling methods often ignore the complex resource requirements of applications, and split the applications into stages which are scheduled independently. For instance, the earth observation scheduling is always separated into independent earth observation satellites scheduling and data transmission scheduling, causing low utilization of network resources. In addition, existing resource scheduling problems are modeled and solved via mathematical programming methods. This type of methods fall into the algebraic domain, which have disadvantages of long running time and high memory requirements when the network scale is large, unable to schedule resources in real time. Therefore, it is urgent to design an application-driven fast scheduling method for multi-dimensional resources for improving network resources utilization. To satisfy the requirements of real-time multi-dimensional resources scheduling from applications and enhance the network resource utilization in Satellite Internet, we need to study the methods for joint representation of multi-dimensional resource requirements from applications and multi-dimensional resources, and using these methods to design applicationdriven efficient scheduling methods. Towards this, based on time-varying graph theory, this thesis studies the multi-dimensional resources scheduling methods driven by three typical
satellite network applications, to reduce the application completion delay and improve the resource utilization. The main research contents and results of this thesis are as follows: 1. In regards to poor scalability of algorithms for solving data transmission problems over Satellite Internet, this thesis proposed a minimum delay data transfer algorithm in an incremental manner based on time-varying graph theory. The proposed method incrementally solves the problem of joint scheduling of  communication and storage resources, via dynamically configuring storage resources. Specifically, this work proposes an incremental minimum delay data transfer algorithm based on the maximum flow algorithm. This method
progressively expands the network scale, taken as input of the problem, during the calculation process, and keeps identifying the network capacity under different network scale until the identified network capacity is no less than the data amount of the task. During the process, the method incrementally solves the problem based on the historical calculation results,
avoiding calculating the network capacity from scratch when network scale increases. The incremental nature of maximum flow algorithms ensures the correctness of proposed method. The time complexity of proposed algorithm is ( · g), reducing (log()) as compared to ( · log() · g) of a classical method. Based on the proposed method, this work further proposed an incremental maximum flow algorithm based on time-expanded
graph, whose time complexity is lower than that of the traditional maximum flow algorithm. Finally, in order to verify the performance of the proposed method, we proposed two variants of the classic minimum delay of data transfer algorithm to compare. Simulation experiments show that the proposed method is highly scalable as the network scale increases or task data amount increases, demonstrating that the joint scheduling of storage and communication resources can effectively improve the algorithm running speed. 2. The earth observation applications in Satellite Internet independently schedule observation, communication and storage resources, causing low resource utilization and long data transfer delay. Regarding this, this thesis proposes an on-demand method for joint
scheduling of transmission and observation resources with high resource utilization. First, this thesis models a generic problem of jointly scheduling observation, transmission and storage resources as a linear programming, which supports on-demand network topology configuration to maximize the amount of successfully transmitted observed data. However, solving this linear programming problem requires a lot of memory and long running
time when network scale becomes large. To tackle this issue, this thesis further used timeexpanded graph to represent the nodes and  communication links of the Satellite Internet, and introduced auxiliary vertices and edges to represent the special constraints in the linear
programming problem. Based on this proposed graph, the problem of jointly scheduling observation, transmission and storage resources can be transformed into a maximum flow problem, which can be solved using the proposed incremental maximum flow algorithm. Simulation experiment uses the real trace of the trajectory of Starlink and Gaofen satellites
to construct the network topology, which is the input of the studied problem. The experimental results show that when the traffic load in the network is heavy, configuring the network topology on demand can increase the network throughput by 180%, as compared to predetermined network topology configuration. In addition, when the load in the network is light, the joint scheduling of observation tasks and transmission tasks can increase the network throughput by 100%, as compared with the independent  scheduling of observation and transmission tasks. This work proves the necessity of joint scheduling of observation resources and communication resources for earth observation applications. 3. In regards to the difficulty in representing the computing requirements of computing applications in Satellite Internet and the difficulty in scheduling multi-dimensional resources when storage resources are insufficient, computing application completion delay will be long. Thus, this thesis proposes an algorithm to jointly schedule the transmission, computing and storage resources based on a time-varying graph. First, using packets to create decision variables, this thesis models the problem of jointly scheduling transmission tasks and computing tasks under storage constraints as an integer programming problem. This problem first formally gives the mathematical expression of computing applications requirements. To reduce the number of constraints and variables, this thesis integrates multiple packet-oriented variables into a single flow-oriented variable and further proposes a mixed integer linear programming problem based on the constraint transformation method.
However, when the network scale is large, the running time of standard solver is too long to solve the problem. Therefore, an enhanced storage-time aggregation graph model is proposed to jointly represent storage, computing, and transmission resources. Based on this graph model, an application-oriented single-path shortest-delay routing method under storage constraints is proposed. Compared with the traditional routing strategy, this method allows the joint use of storage resources of multiple nodes, thereby reducing the end-to-end transmission delay of applications. The simulation results show that the proposed method can run thousands of times faster as compared to the standard mixed integer linear programming solver, while application delay is less than 10% higher than the theoretical shortest delay. In addition, compared with the classic routing method, the proposed method can reduce the application delay by 20% and increase the network throughput by 40%. It proves the necessity of jointly scheduling storage resources, transmission resources and computing resources for computing applications.