信息与智能研究生学术论坛（第2讲）：大规模卫星网络实时应用的在线切片方法
Date:
得益于星间链路、星上计算资源与网络虚拟化技术的部署，大规模卫星网络有望为地面实时应用提供低时延、高带宽、多功能、全球覆盖的服务。然而，在链路断续连通的卫星网络中支持指定功能的实时通信服务，需要设计高效的路由方法。我们发现卫星网络上的实时应用端到端切片问题可以建模为整数线性规划问题。采用标准的分支定界方法求解面临指数的复杂度。通过设计基于K-最短路径的方法，大部分情况下算法运行速度很快，但性能不稳定，而且会产生次优解。因此，我们进一步通过利用解空间的特殊结构，设计了另一种图论算法，可以在多项式时间内得到问题的最优解。在包含上千颗卫星的Starlink 星座上进行仿真，验证了所提图论算法的有效性。
In this work, we investigate resource allocation strategy for real time communication (RTC) over satellite networks with virtual network functions. Enhanced by inter-satellite links (ISLs), in-orbit computing and network virtualization technologies, large-scale satellite networks promise global coverage at low-latency and high-bandwidth for RTC applications with diversified functions. However, realizing RTC with specific function requirements using intermittent ISLs, requires efficient routing methods with fast response times. We identify that such a routing problem over time-varying graph can be formulated as an integer linear programming problem. The branch and bound method incurs exponential time complexity. By adopting a k-shortest path-based algorithm, the theoretical worst-case complexity becomes lower. Although it runs fast in most cases, its solution can be sub-optimal and may not be found, resulting in compromised acceptance ratio in practice. To overcome this, we further design a graph-based algorithm by exploiting the special structure of the solution space, which can obtain the optimal solution in polynomial time. Simulations conducted on Starlink constellation with thousands of satellites corroborate the effectiveness of the proposed algorithm.