Joint Dynamic Routing and Resource Allocation in Large-Scale Small Satellite Networks

小卫星网络在现代通信中有着重要的作用，普遍应用于各种现代通信场景。由于随机传输需求和随机分组产生/到达，大规模小卫星网络中的流量模式变得复杂，而由于网络规模极大和小卫星资源有限，路由面临更大的挑战。传统的卫星路由算法试图利用时间离散图模型来利用可预测的卫星轨迹，无法应对这些挑战。动态路径路由成为提高网络性能和鲁棒性的关键路由技术之一，本文利用动态网络特性对信息路由问题进行三维建模，将端到端的带跳数约束的最短路径问题建模为0~1整数规划问题。由于难以刻画动态拓扑下的全局信息，我们采用时间切片对卫星位置和星间链路状态进行精确刻画，得到信息路由所需的网络拓扑。同时，我们采用基于“路由–切换”机制的路由算法对三维网络拓扑中的端到端问题进行求解，求解过程涉及一个带有跳数约束的最短时延路径问题，由于该问题为NP-hard，多数已有研究采用启发式算法进行近似求解，以牺牲求解精度来换取求解效率。我们采用基于拉格朗日对偶理论的BiLAD算法对该单约束最短路径问题进行求解，既能保证求解效率，又可以保证求解结果的最优性。在数值实验中，我们随机生成200个测试实例，实验结果显示，本文所提信息路由算法可以成功求解191个测试实例，和贪心算法相比求解成功率提高了约18%。Small satellite networks play an important role in modern communications and are widely used in various modern communication scenarios. Due to random transmission requirements and random packet generation/arrival, the traffic pattern in large-scale small satellite networks becomes complex, and routing faces greater challenges due to the extremely large network scale and limited small satellite resources. Traditional satellite routing algorithms attempt to use time-discrete graph models to exploit predictable satellite trajectories, but cannot cope with these challenges. Dynamic path routing has become one of the key routing technologies to improve network performance and robustness. This paper uses the characteristics of dynamic networks to model the information routing problem in three dimensions, and models the end-to-end shortest path problem with hop count constraints as a 0~1 integer programming problem. Since it is difficult to characterize the global information under dynamic topology, we use a combination of time slicing and dynamic grid models to accurately characterize the satellite position and intersatellite link status, and obtain the network topology required for information routing. At the same time, we use a routing algorithm based on the “routing-switching” mechanism to solve the end-to-end problem in the three-dimensional network topology. The solution process involves a shortest delay path problem with hop count constraints. Since this problem is NP-hard, most existing studies use heuristic algorithms for approximate solutions, sacrificing solution accuracy in exchange for solution efficiency. We use the BiLAD algorithm based on Lagrangian duality theory to solve the single-constrained shortest path problem, which can ensure both the efficiency of the solution and the optimality of the solution. In the numerical experiment, we randomly generated 200 test instances. The experimental results show that the information routing algorithm proposed in this paper can successfully solve 191 test instances, and the success rate of the solution is increased by about 18% compared with the greedy algorithm.