LEO卫星网络路由算法介绍(一）——概述

0. 写在前面

        笔者学生课题方向涉及卫星路由算法的设计，因此通过阅读相关文献，将学习的内容总结，作为学习笔记记录，如有不对之处欢迎大佬们批评指正。

1. 背景

       6G通信体制下畅想未来网络可以万物互联并提供低延迟、高可靠性数据传输能力来满足用户的多重业务需求。卫星网络由于其覆盖面积广、传输损耗低等优势，成为未来星地一体化网络发展的重要发展趋势。随着大规模LEO卫星星座网络的发展和部署，路由技术作为网络组网技术中的的关键技术之一，随着卫星网络规模的扩大而愈发关键。针对路由算法的研究，对未来的大规模LEO卫星星座网络的组网具有很重要的意义。

2. 卫星路由技术的挑战

      随着LEO卫星星座网络的发射数量增加，路由技术面临着以下挑战：

1. 路由选择和计算复杂：由于LEO卫星星座的特性，卫星高速移动，卫星拓扑动态变化，卫星链路频繁切换；同时卫星的数量众多，卫星间星间链路数量增加，导致卫星到目的节点的跳数增多，可选择的路径增多，导致了路由的选择规划问题和路由表计算的复杂。

2. 卫星载荷有限：LEO卫星体积小，载荷有限，因此计算能力和存储能力有限，无法支撑卫星进行大量的路径计算；卫星的电池能量有限，无法支持大的能量消耗。

3. 节点和链路拥塞：全球用户的流量分配不均匀，大量业务分布在发达国家和地区，大量的业务承载和频繁的数据传输会造成节点和链路的拥塞。

4. 保障业务服务质量：全球用户的业务需求增加，LEO网络中需要传输大量不同的业务，因此需要保证这些业务的服务质量(Quality of Service, QoS)，满足用户的通信需求。

5. 卫星损坏概率增加：由于卫星数量增多，卫星的损坏增加，由于现有技术不可能保证卫星的及时修复和更换，因此需要保证一颗和多颗卫星节点失去工作能力时，保证卫星网络不受到影响。

3. 卫星路由算法分类

       卫星路由算法可以按照多种类型进行分类。分类类型如下：

1. 按照配置方式分类，可以分为静态路由算法和动态路由算法。静态路由算法指网络节点维护固定的路由表，当数据包从源节点发送到目的节点时，节点按照维护的路由表来查找下一跳节点；动态路由算法指节点通过交互信息，按照网络状态构建路由。静态路由算法优点比较稳定，缺点是无法适应网络拓扑变化情况；动态路由算法能够适应网络变化情况，更加灵活，缺点是设计较为复杂，需要适应网络具体情况。因此卫星网络路由算法大部分为动态路由算法。

2. 按照布局分类，可以分为集中式算法和分布式算法。集中式算法将一个节点作为中央控制器收集周围节点信息进行路由规划；分布式路由算法将路由计算分散到每个节点上，来减小计算所带来的开销。

3. 按照网络拓扑分类，可以划分为基于虚拟拓扑和基于虚拟节点的卫星路由算法。基于虚拟拓扑的卫星路由算法的主要原理是根据卫星的运动规律，将卫星周期分为相等时间间隔的时间片，时间片内的网络拓扑结构等效为该时间片内某一时刻的网络拓扑，因此可以近似认为时间片内网络拓扑结构不变，每个时间片内采用最短路径算法计算最短路径。这样就可以避免网络拓扑动态变化带来的不稳定性。基于虚拟节点的卫星路由算法主要原理是假设地球表面被逻辑位置所覆盖，每个逻辑位置上的卫星由<轨道数，卫星数>对来表示，逻辑位置上的卫星变化但其位置不变。路由的数据包传递转化为逻辑位置的跳数进行数据包传递转发，避免了网络拓扑结构变化所带来的不稳定性。

4. 按照业务需求分类，可以分为基于负载均衡的卫星路由算法和基于QoS的卫星路由算法。基于业务需求的卫星路由算法设计需要考虑满足网络中多种业务的QoS，同时合理利用星座网络链路数目众多的特点，舒缓负载大的区域的流量压力，减轻拥塞概率。

5. 基于软件定义网络(SDN)的卫星网络路由算法。SDN技术应用于卫星网络，将控制与数据平面分离，控制平面负责将命令从管理平面分配到数据平面，监控卫星网络的实时状态，然后将其反馈给管理平面。因此LEO卫星将只负责传输数据包，不需要进行路由的发现和计算，这样就降低了计算和信令开销。

6. 基于人工智能的卫星网络路由算法。主要是基于机器学习优化算法和强化学习和深度强化学习的路由算法。LEO卫星星座网络中每个卫星节点可以视为代理，将优化的指标作为状态进行输入，将下一跳卫星作为动作，并根据拥塞情况等条件作为奖励，来输出最短路径。由此卫星路由优化问题就被描述成为一个马尔可夫决策(Markov Decision Process, MDP)问题，运用强化学习即可感知实时网络状态，来进行路由决策，获取优化后的最优路径。

4. 总结

        随着StarLink等低轨卫星星座网络的发射和部署，我国的低轨卫星网络建设计划如火如荼进行，卫星网络路由作为组网关键技术之一，面临着诸多的挑战，对其的研究和算法的设计具有一定的意义和研究价值。