一种基于强化学习的低轨卫星网络智能路由算法*

左珮良 王 晨 蒋 华，2

1.北京电子科技学院，北京市 100070

2.西安电子科技大学，西安市 710071

随着5G 通信技术逐步融入人类社会生活并为后者提供不可或缺的服务体验，6G 通信技术以及空天地一体化技术已经进入研究人员的视野[1]，其中具备探测、导航或通信功能的卫星网络是重要的组成部分[2]。

相比于一般的高、中轨道卫星网络，由于距离地面更近，低轨卫星网络具备明显更低的服务延迟，且在执行相关任务时具备更好的机动性。

与此同时，大量低轨卫星的高效合作能够实现对地球表面的全天候低时延覆盖，以上优势使得低轨卫星网络的快速构建成为世界各大国的工作重点。

低轨卫星网络在空天地一体化技术中扮演的角色示意可以参见图1，得益于星间链路和低时延广覆盖特性[3]，低轨卫星网络在提供自身基本的探测、导航和通信三项服务的同时，其能够很好的实现承载异构网络互通融合的目标。

图1 空天地一体化场景中低轨卫星网络的应用示意图

国内外典型的低轨卫星星座系统有铱星二代、OneWeb、Starlink(星链)等，其中铱星二代系统具备全星间链路，能够基于星上路由功能实现数据交换，但受限于通信频段的带宽，其星间链路通信容量较低[3]。

OneWeb 星座系统则不具备星间通信功能，其依靠弯管载荷实现宽带业务。

Starlink 卫星互联网计划由美国SpaceX 投入实施，旨在最终依靠成千上万颗低轨卫星组网实现全球范围内的宽带互联网接入，截止目前，Starlink 还不能够支持星间链路，其服务范围还相对有限，但其为用户提供的平均服务速率已经是地球同步轨道卫星Viasat 的三倍多，达到79.5Mbps，而平均时延却仅为后者的十六分之一(42ms)。

我国计划于2023 年前完成“鸿雁”低轨卫星星座的构建工作，并最终实现全球互联网用户的接入和监测服务。

虽然低轨卫星网络具备不可替代的优势，但由于低轨卫星高速移动、数量众多、轨道交错多样所导致的星间拓扑频繁变动、星间链路持续性不强等现象，使得低轨卫星路由算法的可靠性和高效性受到不小的挑战。

文献[4]依据卫星三种典型的业务类型(即时延敏感业务、带宽敏感业务和丢包率敏感业务)对QoS 的需求，设定了多约束条件下的路由优化目标，并通过蚁群优化算法进行求解。

以均衡动态低轨卫星网络的负载为目的，文献[5]提出了一种基于事件触发的路由算法，该算法由链路信息更新、多径路由和负载判决三步组成，一定程度上提高了网络的负载均衡和抗毁性。针对中心式路由决策具备策略重构时延长的问题，文献[6]提出了一种基于星间链路持续时长预测的路径切换机制，该机制在一定程度上提升了网络的吞吐量水平。

相比于需要控制中心统一搜集路由决策依据信息的集中式路由决策方法，发挥局部信息感知和路径策划的分布式路由方法虽然决策结果不具备全局最优的特点，但其规划结果具备更好的实时性，能够适应于网络高动态变化的场景。

文献[7]提出的ELB 算法能够分布式的感知网络状态并定期监控本地拥塞情况，设定拥塞阈值，待拥塞超标后，进行路径切换。

受交通灯启发，文献[8]提出了TLR 方法，方法将下一节点的网络拥塞状态用红、黄、绿颜色描述，以便动态的调整数据流的走向。

文献[9]将网络节点拥塞状态进行了简单的二元(优、良)描述，以此作为数据流选路的依据，该种方法简单且易实施。

不同于以上需要人工设定阈值并划分卫星节点类型的分布式路由决策方法，本文关注于探索提出一种能够依靠深度强化学习模型自适应选路的智能路由算法，所提算法不需要额外设定节点分类阈值，避免了由于该操作所引入的误差。

在论文接下来的内容里，第1 章给出了路由模型，第2 章具体说明了所提算法，第3 章对路由算法的性能进行了仿真验证，第4 章对全文进行了总结。

本文所关注的路由决策场景如图2 所示，不失一般性，我们假定极轨道卫星星座中每颗低轨卫星的通信可达范围内包含了四颗相邻的卫星节点，其中与当前卫星节点处于同一轨道的卫星为两颗，处于东西相邻轨道的卫星各为一颗。

随着通信和计算技术的迅猛发展，在模型的同一星座中，每颗卫星由于发送上天的时间存在差异，卫星的大小、通信能力、处理能力及能源获取和消耗水平都存在明显的差异。

与此同时，受实际工作环境(如非均衡链路负载)的影响，每颗卫星的可用资源也存在区别。

作为低轨卫星网络智能路由技术初探，本文考虑分布式场景下的卫星路由决策，特别地，我们设定每颗待发送数据的卫星(源卫星)仅能够依靠信息交互获取到周围四颗卫星的实际状态，显而易见，这种假定在很大程度上节省了通信交互的开销和卫星的存储空间。

如图2 所示，源卫星的智能选路过程可以用三步进行描述:①源卫星依靠通信交互获得周围四颗卫星的可用带宽、信道信噪比、间距、空间位置等决策参考信息；
②源卫星依靠接收到的决策参考信息以及自身状态如发送功率、天线调整速率等，结合智能算法得到预测输出；
③源卫星完成算法预测输出与节点选择的映射，并将待发送数据传送给下一卫星节点。

图2 智能路由模型示意图

2.1 强化学习与深度强化学习

如图3 所示，在强化学习过程中，智能体(Agent)和环境(Environment)在一系列离散时间内相互作用，完成一个任务。

强化学习的过程可使用马尔可夫决策过程(MDP)进行建模，一般使用五元组＜S，A，P，R，γ ＞进行描述[11]，其中S与A分别代表状态空间和动作空间，P为状态转移概率，p(s′|s，a) 表示在状态s下采取动作a后环境转移到状态s′ 的概率，R为奖励函数，γ∈[0，1] 为折扣率，R表明了智能体的当前动作是好动作还是坏动作。

强化学习智能体的策略使用π表示，智能体根据策略π选择动作。

图3 强化学习原理图

智能体与环境交互过程包括以下几个过程:在t时刻，智能体观察环境的状态st∈S，智能体根据策略π(st) 选择动作at， 动作at作用于环境，随后环境转变为状态st+1， 此时环境会给予智能体相应的奖励rt， 之后智能体会依据新的环境状态和策略做出新的决策，该交互过程不断重复，直至智能体完成相应的目标任务。

强化学习智能体的目标即为最大化累计奖励的期望E(∑γtrt)，其中，γ∈(0，1) 是折扣率，当γ接近0 时，智能体更注重短期回报，当γ接近1 时，智能体更注重长期回报。

Q 学习是强化学习典型算法之一[12]。

Q 学习算法是一种离线策略的差分学习方法。

在策略π、环境状态s下采取动作a时，基于Q 学习的智能体会学习动作值函数Qπ(s，a) :

最佳动作值函数Q*(s，a) ≜maxπQπ(s，a)，由贝尔曼最优方程可知:

其中s′是在状态s下做出动作a之后的新状态。

Q 学习的主要思想是迭代地估计每个状态-动作对(s，a) 出现时的Q*(s，a)。

设q(s，a) 为迭代过程中的动作值函数，则根据t时刻状态-动作对(st，at) 和奖励rt+1， Q 学习更新q(st，at) 的过程如下:

其中β∈(0，1] 是学习速率。

Q 学习在更新q(s，a) 的同时，也会根据q(s，a) 进行动作决策。

为避免局部收敛，智能体会以一定概率随机选择动作，这种方式称为ε-贪婪策略，即:

随机选择一个动作是为了智能体避免陷入尚未收敛到Q*(s，a) 的q(s，a) 函数中。

传统的强化学习使用存储表的方法记录表示策略π， 然而当状态-动作空间较大时，传统强化学习方法变得不再实用。

在低轨卫星网络中，网络规模的增长及监控粒度的不断细化，导致低轨卫星网络的状态空间维度爆炸，依靠传统强化学习实现低轨卫星的路由算法愈发困难。例如在本文的仿真设置中，状态空间由四项时延、一项距离和一项终点指示所组成，则状态空间大小为104× 12× 2= 240000，该值远远超出了传统强化学习能够高效处理的空间范围。

深度强化学习将深度学习的智能感知能力和强化学习的快速决策能力相结合，通过充分发挥二者各自的优势使得智能体能够直接从高维输入数据中获得感知信息，并使用获得的感知信息进行模型训练，得到最优策略并做出决策，实现对智能体的行为进行合理有效的控制[14][15]。

在强化学习中引入深度学习有三种方法，分别为基于值的深度强化学习、基于策略的深度强化学习和基于模型的深度强化学习[13]。

其中，基于值的深度强化学习方法，即DQN(深度Q 学习)，使用神经网络来估计状态-动作值函数(即Q 值)，DQN 与Q 学习类似，仍然通过差分学习的方式更新Q 值。

DQN 的优化目标为最小化损失函数Loss，Loss 表示的是现实值与估计值的偏差大小，定义为:

在常规DQN 中，选择动作和评估选择的动作使用相同的网络参数，这导致Q 值被过高估计，为解决这个问题，可以使用两个结构相同但参数不同的神经网络，分别称为Q 网络和目标网络，以减少Q 值的过度估计，同时降低训练时震荡发生的可能性。

2.2 智能路由算法

由于卫星节点的可用频谱资源可能不相同，不同卫星节点间可用于通信的共同频谱资源可能不同，即不同卫星链路的带宽可能不同，因此在t时刻，路由节点i与路由节点j之间的星间链路可实现的数据传输最大速率为:ri，j(t)=Bi，jlog2(1 +γi，j(t))，其中Bi，j表示路由节点i与路由节点j之间用于通信的共同频谱资源。

由以上描述我们可以得到Ti，j(t) 的具体表达式:Ti，j(t)=Ri，j(t)/ri，j(t)+m，其中Ri，j(t) 为t时刻路由节点i与节点j的距离，m表示发送时延，由于路由节点接收到数据需要进行解码转发，所以需要一定的时间进行转码，方便起见我们假设每个节点解码能力相同，可以将m设为固定值。

本文的奖励函数由路由节点到目的节点的距离、星间链路传输时延、路由跳数构成，单步即时奖励函数具体设定如下:

其中，α、ρ、μ三个权重参数的和为1，Tij(t)，Lj(t) 需进行归一化处理，rt取值范围是-1 到0。

如果下一跳的节点是目的节点，奖励值应最大，此时奖励设为0，其他情况奖励值均小于0。

如果下一跳的节点是不是目的节点，奖励函数需要考虑路由节点i向路由节点j的传输时延Ti，j(t)，智能体选择下一跳节点的时延越小奖励越大；
若只考虑时延特性，路由的传输可能会偏离最终的目的节点，所以奖励函数还应考虑下一跳节点离目的节点的距离，智能体选择下一跳的节点距离目的节点越近，奖励越大；
本文还考虑跳数的因素，假设路由最大跳数为M，当前实际跳数为n， 则可设置与跳数相关的奖励为Hn= 1/1+e-(n-M)，当n在M之内时，与跳数相关的奖励值趋近于0，若实际跳数n远超过M，则与跳数相关的奖励值趋向于-μ。

本文采用DQN 算法对模型进行训练，具体算法流程如下所示:

输入:状态空间S，动作空间A，折扣率γ，学习率β，目标网络参数更新频率F；
1. 初始化经验回放库D，容量为N；
2. 随机初始化实际Q 网络的参数ϑ；
3. 随机初始化目标Q 网络的参数ϑ＾ = ϑ；
4. repeat 5. 选择起始路由节点i，起始路由节点的状态为si；
6. repeat

7. 在状态si 的情况下选择动作a = πε(si)；
8. 执行动作a，智能体与环境交互，得到单步即时奖励r 和新的状态s′；
9. 将si，a，r，s′放入经验回放库D 中；
10. 从D 中采样新的ss，aa，rr，ss′进行训练；
11. 以[(r + γ max a′ Qϑ(s′，a′)) - Qϑ(s，a)]2 为损失函数训练Q 网络；
12. 状态更新:s ←s′；
13. 每隔F 步对目标Q 网络参数进行更新:ϑ＾←ϑ；
14. until 状态s 为目的节点；
15. until 对于任意的s，a，Qϑ(s，a) 收敛；
输出:Q 网络的Qϑ(s，a) 值，选取最优动作a = argmaxaQϑ(s，a)

本文使用Keras 作为深度学习平台来训练神经网络，神经网络采用6 层的ResNet 网络，程序仿真的相关参数如表1 所示。

不失一般性，设定卫星数量为48 颗，并且均匀地分布于8 条地球近地轨道，其中每条轨道上有6 颗间距相等的低轨卫星，与此同时，为了方便和直观地验证本文所提算法的性能，论文将低轨卫星轨道面展开视作矩形，并设定相邻轨道的间距相等。

在仿真中以快照的形式训练或者测试所提算法，在每个快照中，随机设定一个卫星节点作为目的节点，并假定快照中所有卫星的包含可用带宽、空间位置等状态保持不变，在余下的47 颗卫星中随机地产生一个数据源卫星，定义从源卫星起始并最终选路至目的卫星节点时算作一轮。

本文分别产生了10 个和5 个快照作为训练集和测试集，对于训练集来说，探索指数ε初始值设置为0.9，并随着当前轮中选路的进行每步衰减至上一步0.995 倍，直至本快照训练结束，而快照间的探索指数ε按照上一快照初始值的三分之二进行衰减，对于测试集来说，为了充分利用所训练得到的算法模型，我们将探索指数ε始终设置为0.005。

权重α、ρ和μ被分别设置为0.5、0.3与0.2，本文从两个层面考虑，最终设置了该权重比例，一方面是理论上三者对路由时延影响的程度，另一方面则是在仿真中进行参数的优化，当前的权重参数性能较优。

表1 所提算法仿真参数

所提算法针对训练集的时延和奖励的收敛过程如图4 所示，可以明显的看到，对于十个快照的每一个来说，算法的奖励和传输的时延都在早期经历了一定的震荡后(一般10 几轮到20 几轮之间)，逐步收敛到稳定值，这与算法探索指数的逐步减少以及深度强化学习模型逐步掌握当前快照的路由策略相对应。

另外值的说明的是，对于每个快照在收敛后仍然可以看到较小的毛刺(参见图3 时延线)，这是因为此时的探索指数仍然较大，卫星节点在选路的过程中依然有一定的几率选中非优的下一卫星节点，且由于该几率较小，所以在未来的选路中又回归到了较优的节点上，使得引起的震荡较小。

图5 展示了所提算法依靠训练数据得到的模型针对测试数据的收敛过程，结合图4 可以得出结论，算法模型能够以明显更快的速度适应快照的卫星节点状态，其一般仅需要2-4 轮即可以完成收敛，与此同时，由于模型的探索指数很小，可以看到对于测试数据收敛后基本上不会发生毛刺现象。

此外，还可以看到，图5 中模型的震荡频率和震荡程度均明显的低于图4，这说明了依靠旧快照训练得到的模型能够很快的适应新的快照，且在模型适应后者的过程中所产生的不匹配程度较低。

值得补充说明的是，结合仿真结果不难判断出，本文所提智能路由方法能够避免出现“路由回路”问题，因为方法以最低路由时延为优化目标，智能体依靠大量的“尝试-犯错-再尝试”模式的训练过程，对包含“路由回路”在内的多种耗费时间的错误决策进行了学习认知。

图4 所提算法针对训练数据的收敛过程

图5 所提算法针对测试数据的收敛过程

最后，我们对所提算法相比于其他常用算法的优势性进行仿真验证，考虑到本文场景中待传数据的卫星节点获取周边卫星信息的局限性，论文选取了贪婪周边无状态路由(GPSR)算法[10]作为对比方法，该算法仅以下一节点距离目的节点的距离作为参考因素进行选路，此外，我们还选定贪婪固定权重路由(GFWR)作为对比方法，该方法可以认为是文献[8-10]所提算法的当前场景改进版，方法依靠对基于可用带宽、信噪比和待传数据量计算得到的时延以及下一节点与目的节点的距离两个因素设置固定权重加和进行路径选择。

待收敛后，我们在测试集中随机选用几个处于不同起始卫星的快照，并在图6 中展示了所提方法与对比方法在时延方面的性能，其中GFWR(1-9)代表时延和间距的权重比例关系为1 ∶9，以此类推。

鉴于GFWR 算法在某些权重设定下容易出现路由迂回的现象，本文将发生路由迂回时的时延统一设定为8。

从图中可以看到，GFWR 算法受具体的权重参数设定影响很大，且不可避免的会出现路由迂回现象，相比而言，GPSR 算法则更加稳定些，虽然其延迟在某些情况下要大于GFWR 算法，本文所提算法在时延性能方面明显的优于两种对比方法，且在所有的测试轮中具备不高于对比方法的时延。

以上测试验证了本文所提方法的合理性、针对场景的适应性以及相比常用路由算法的优势性。

图6 路由算法时延性能对比

针对低轨卫星网络高速移动、拓扑变化频繁所导致的路由规划难题，本文提出了一种适用于分布式场景的智能路由算法，算法基于深度强化学习理论，仅依靠待发送数据卫星节点对周边有限几个卫星节点包含可用频谱、间距、信噪比等信息的搜集掌握，迅速自动的选择下一跳卫星节点。

仿真实验证明，所提方法能够较快的实现收敛，且与常用的分布式路由方法相比，具备明显更优的时延性能，作为卫星智能化路由的研究初探，所提方法适用于本文所关注的低轨卫星网络局部自适应路由决策场景。

考虑方法在实际场景中的应用部署，可将低轨卫星网络中的每个节点视作一个智能体，每个智能体在部署之前，可以初始化的设置仿真训练好的决策模型，该模型在卫星节点实际运营过程中，可以依靠节点的交互情况，进行各自的模型更新，由于初始部署的模型已经具备较优的性能，其再次训练的过程能够较快的收敛。