卫星网络动态资源图多QoS约束路由算法
2023-01-31梁超杨力潘成胜戚耀文
梁超，杨力，潘成胜，，戚耀文
1．大连大学 通信与网络重点实验室，大连 116622
2．南京理工大学 自动化学院，南京 210094
近年来，全球高中低轨卫星通信，尤其是巨型低轨星座系统进入井喷式发展阶段［1］，卫星的计算能力、存储能力也逐渐变强，同时，基于卫星网络的应用也越来越多并朝着多样化的方向发展。路由技术作为卫星网络中的关键技术仍面临很多问题，例如高动态、高时延、局部拥塞等。因此，设计高效可靠的路由算法至关重要。
文献［2］指出，路由协议有许多是为特定网络设计的，呈现出不同的特性，因此，在研究路由算法时，需要考虑不同网络环境所产生的影响。当前卫星网络路由主要基于2种网络模型，一种是基于离散时间片的虚拟拓扑模型，文献［3］提出基于时间片分割的拓扑生成优化算法得到抗毁性良好的拓扑结构，但当有大量卫星时，这种模式不可扩展；另一种是基于虚拟节点的模型，该机制屏蔽了网络的动态性，同时简化了路由机制。基于虚拟节点的路由策略虽然能够规避卫星网络的高动态性问题，但这种方式忽略了虚拟节点与物理节点切换时所带来的路径失效问题。
路由问题是一个多目标优化问题，在网络性能优化方面，主要是以端到端时延、网络吞吐量和数据包交付成功率等指标为优化目标，研究者针对不同的优化目标提出了大量可行方案。文献［4］提出了一种新颖的时间网络模型来描绘大规模小型卫星网络的时变拓扑并提出了一种高效的基于网格的最短路径路由算法。文献［5］提出了一种基于计划拓扑的延迟约束路由机制算法，该算法基于预测的拓扑建立路由表并以时延为约束条件进行路由计算。文献［6］提出了一种基于服务概率和有限副本的算法，基于转发概率和卫星剩余缓存选择路径。文献［7］提出了一种基于星间链路状态信息的路由算法，卫星根据与相邻卫星的链路状态信息和网络拓扑为每一跳做出路由决策。文献［8］提出了一个联合的时空路由算法框架，设计了一种多路径路由算法。文献［9］提出了一种基于网络编码的多径协作路由协议，该方案采用非停止等待机制完成数据包的分批次传输。能量感知路由算法从能量的角度“验证”和“确认”节点的有效性，并基于此设计了一种解决路由无效问题并绕过敏感节点的路由方案［10-11］。以上方案在缩短网络传输时延，降低网络控制开销，提高网络性能方面发挥了重要作用，但在流量突发情况下，网络会发生拥塞，难以保障通信服务质量（Quality of Service，QoS）。
为了缓解网络拥塞，文献［12］提出了一种队列调度的虚拟拓扑延迟容忍网络路由算法，该算法能够较好地平衡空间通信网络拓扑更新和资源消耗的影响。文献［13］针对低轨卫星网络，提出了基于分段路由的负载均衡路由算法，基于拥塞指数在轻载区和重载区采用不同的方案计算路由。以上方案在负载均衡方面均体现了较好的性能，但当网络负载很高时在时延方面略有劣势。文献［14］提出了一种基于存储时间聚合图的多流最大化路由方案以保证任务的QoS。采用蚁群算法求解路由，并将QoS约束应用于改进启发式算法，能够满足网络业务的QoS需求［15-16］，文献［17］讨论了蚁群算法在路由问题中的应用，并针对应用中的问题提出了3种改进策略。上述算法均在某些方面保证了通信的QoS需求，但忽略了网络动态切换带来的影响。
针对拓扑变化导致的网络更新期间可用路径失效问题，文献［18］提出的适应拓扑变化的拥塞最小化网络更新策略降低了网络拥塞。文献［19］明确指出了低轨卫星的切换问题，分析了卫星运行所引起的链路切换对路由计算的影响，表明接入卫星的频繁切换，必然导致原有转发路径失效，继续在其上传输业务时将产生严重的数据包丢失现象，此时需要重新计算卫星通信网络的拓扑和路由。因此，将路由计算和卫星链路切换结合起来可以降低重路由所带来的开销。
综上所述，虽然研究者为提高卫星网络QoS、缓解网络拥塞做了大量研究，但在路由计算时均未考虑卫星动态切换造成的路径失效问题。因此，本文基于虚拟节点网络拓扑，构建动态资源图，提出了一种虚拟节点动态资源图多QoS约束路由算法（Multi-QoS Constraints Routing Algorithm based on Dynamic Resource Graph of Virtual Nodes，DRGVN-QR），从而达到缓解网络拥塞，提高网络QoS的目的。首先，建立虚拟节点动态资源图和多目标优化模型，该模型同时考虑了节点的切换状态、缓存以及链路的剩余带宽、时延等信息；其次，利用蚁群算法建立多QoS约束计算模型求解目标函数，为每个连接请求找到一段时间内符合QoS约束的多条路径，并讨论了信息素挥发系数的取值问题；最后，设计一种幂数加权公式选出一段时间范围内的最优路径。
1 系统模型
1.1 软件定义卫星网络模型
将软件定义网络（Software Defined Network，SDN）应用于卫星网络可以有效缓解星上资源有限、管理困难的问题。因此，本文将SDN应用于低轨（Low Earth Orbit，LEO）卫星网络，SDN控制器部署在3颗地球静止轨道（Geostationary Earth Orbit，GEO）卫星和对应的地面站，位于GEO的控制器负责收集其覆盖区域的LEO卫星节点的状态信息，3个控制器协同工作获取全局视图，地面控制器与GEO控制器进行信息交互并负责路由计算，图1展示了由卫星和地球站组成系统架构，GEO层和地面站作为控制层，LEO层作为数据转发层。
本文采用类铱星星座［20］作为卫星网络模型，假设星座中共有N个轨道平面，每个轨道M颗卫星，则卫星集群可表示为S=｛1，2…，n，n+1，…，2n，…，（m－1）n+1，…，mn｝，其中n代表轨道编号，m表示卫星在轨道中的编号。星座的网络拓扑由星间链路（Inter-Satellite Link，ISL）构成，除了位于反向缝的卫星外，每颗卫星均有4个ISL，即2个轨内ISL和2个轨间ISL；而位于反向缝的卫星只有1个轨间ISL，因此只有3个ISL。
图1 系统架构Fig. 1 System architecture
轨间ISLs长度的计算公式为
式中：R为卫星的轨道半径。
轨内ISLs长度Lh的计算公式为
式中：lat为指轨内ISLs所在的纬度。
为了适应LEO卫星网络拓扑结构的动态变化，本文采用基于虚拟节点的网络拓扑方式，根据LEO卫星网络的初始状态，将地球表面根据卫星星座进行区域划分，每个区域对应一颗卫星，然后给每个区域分配一个逻辑地址〈o，s〉，o代表卫星轨道编号，s代表轨道上的卫星编号，然后根据逻辑地址生成网络拓扑，路由计算总是基于此拓扑进行。
1.2 虚拟节点动态资源图模型
基于虚拟节点的网络拓扑逻辑地址虽然固定，但物理节点时刻变化，在某一时刻逻辑节点与物理节点的对应关系需要进行切换，这会导致虚拟节点和逻辑链路出现短暂甚至长时间的中断现象，如果在切换时刻进行数据转发请求将无法按规划路径到达，并且切换后的虚拟节点资源情况变化很大，如果仍按原路径进行转发将无法保障QoS需求。虚拟节点与物理节点的切换对转发过程的影响如图2所示，在图2（a）中，t时刻源站向目的站发送业务请求，如果按t时刻计算路由，虚拟节点路径为A→B→C，对应的物理节点为1→2→3，在图2（b）中，t+1时刻业务到达节点B即2号卫星，此时虚拟节点与物理节点发生切换，虚拟节点C对应卫星2，此时如果仍进行B→C的转发，那么将无法到达目的站，而可以由2号卫星直接交付给目的站。
因此，本文利用SDN控制器收集网络的所有状态信息，然后将节点切换时间和动态变化的资源情况刻画在各虚拟节点和逻辑链路上，其中虚拟节点与物理节点的切换时间可预测，同时假设节点和链路的其他资源信息也已经通过预测获得。基于此构建出虚拟节点动态资源图（Dynamic Resource Graph of Virtual Nodes，DRGVN），即
图2 节点切换过程Fig. 2 Node switching process
式中：V表示节点 集合；E表示星 间链路；T表示时间范围；Sv(t)表示虚拟节点v与物理节点的切换状态；Bu，v(t)表示链路(u，v)剩余带宽；Dpu，v(t)表示链路(u，v)的传输时延；Bufv表示节点v的缓存大小；Uv(t)表示节点v在t时刻的缓存占用情况。虚拟节点动态资源图采用表1的形式存储。
表1 动态资源信息Table 1 Dynamic resource information
1.3 路径代价优化模型
本节利用上文中建立的虚拟节点动态资源图约束路径的选取并计算路径代价。路径代价的计算主要考虑3个指标，即跳数、传播时延和总端到端时延［21］。本文考虑卫星网络的高动态性因素和数据包在逐跳转发过程中易发生不可预知的情况，在保证链路代价优的前提下应尽量选择节点数量少的路径，因此路径代价通过端到端时延和跳数共同来计算，即
式中：Ps，d(t)表 示t时 刻 源 节 点s到目的节点d的路径代价；ω1、ω2分别表示链路代价和路径包含节点数的权值；hs，d表示路径所包含的节点跳数；Ii，j(t)表 示 节 点i到 节 点j的 单 链 路 代 价，本 文 仅考 虑 传 输 时 延与 排 队 时 延对 链 路代价的影响，即
式 中：Li，j表 示 路 径 长 度；c表 示 电 磁 波 传 播 速 度；Qi，j表示队列 长度；rout表示 出队速度。
本文用fi，j(t)表示t时刻节点i到节点j的流量，虚拟节点v与物理节点的切换状态Sv(t)=1时表示未切换，Sv(t)=0时表示发生切换。在时延、切换状态、带宽和缓存的约束下，设计了多QoS目标优化模型，该模型的目标是为每个源到目的的连接请求寻找一条路径代价最小的路径。因此，建立优化模型的目标函数为
约束条件
为约束（11）表示t时刻链路的可行流量需小于链路的剩余带宽，约束（12）表示节点实际缓存需小于节点最大缓存；约束（13）表示t时刻节点不应处于切换状态。上述模型是一个多目标优化问题，这通常是一个NP难问题，第2节将对该模型进行求解。
2 算法设计
蚁群优化（Ant Colony Optimization， ACO）被用于为每个连接请求寻找最佳路径，因为ACO不仅具有获得组合优化问题最优解的强大能力，而且已经成功地应用于解决LEO卫星网络中的路由问题。因此，本文使用ACO算法求解1.3节的目标函数，求出一段时间内多个时刻的最优路径集合，最后选出该时段路径质量最高的路径。
2.1 基于动态资源图的节点集优化
根据优化目标模型约束，不符合约束条件的节点和链路不能作为备选节点，因此本文基于DRGVN实现一种缩小蚂蚁下一步节点集allowedk的算法，提前去除负载过重的链路实现负载均衡并提高算法收敛速度。具体实现方法如下：
首先，基于虚拟节点的逻辑拓扑图生成拓扑矩阵G
式中：aij表示节点i和节点j之间的距离，当aij=−1时，表示节点i和节点j之间无法建立直接的ISL；节点逻辑地址
式中：Imax表示单条链路所允许的最大代价。
优化allowedk集合的具体实现如算法1所示。
2.2 动态路径选取
为使算法选取的路径在满足QoS约束的基础上实现路径代价最小的优化目标，基于文献［17］的蚁群算法数学模型，本文将链路的剩余带宽Bi，j(t)和链路代价Ii，j(t)作为计算选择下一步节点概率的2个约束条件，则蚂蚁k由当前节点i转移到下一节点j的概率对应的启发函数为
算法1 优化allowedk集合算法
式中：ηij表示节点i到节点j链路的能见度；λ1、λ2、λ3分别表示剩余带宽、链路代价和节点剩余缓存的重要程度；Tij代表节点i到节点j边上的信息素值；α表示信息素的相对权重；β表示能见度的相对重要性。
当所有蚂蚁都完成了一次迭代，需要更新路径上的信息素值，信息素更新公式为
式中：ρ为 信息素 挥发系数；1−ρ为信 息素持 久程度表示蚂蚁k从节点i到节点j留下的信息素增量；P为一个固定值，表示一只蚂蚁一次寻路的信息素总量；Lk表示蚂蚁k经过的路径长度。
2.3 基于时延系数的信息素挥发速度选取
由式（21）可知，蚂蚁k未经过的路径上的信息素以一定速度ρ减少。ρ的数值如果太大，信息素挥发速度过快，导致算法收敛速度慢，路径选择的时效性较低；ρ的数值如果太小，信息素挥发速度慢，容易过早陷入停滞状态，无法选出最优路径。因此，根据路由的时延QoS需求选择合适的ρ值，有利于提升路径质量。
传统蚁群算法的ρ值是一个固定值，不能根据当前网络状态进行调节，无法保证路径质量。本文基于软件定义卫星网络架构，利用SDN控制器实时动态调整ρ值，使算法选择出的路径时刻处于较优状态。设置Tmax代表路径上信息素的阈值，Dmax代表时延阈值，则ρ的取值为
式中：Tsd代表算法选出的最优路径的信息素值；Dsd代表源节点到目的节点的时延；s1、s2、s3、s4为常数阈值，并满足不等式（25）。当路径上的信息素
2.4 DRGVN-QR算法步骤
为了将卫星网络的动态变化考虑在路径选择过程中，本文综合考虑一段时间范围内的网络状态及所选路径在该时间范围内的代价，从而选出全局最优路径。因此，本文基于DRGVN，采用ACO算法并发在每一个时间间隔内选择出一条路径放入Pareto集合中，然后对Pareto集合中路径的代价在时间T范围内进行幂数加权求和，最终选出该时间范围内质量最优的路径。该方案充分利用网络的状态和资源情况进行路径规划，能够有效缓解局部拥塞，提高网络整体的服务质量。
路径代价的幂数加权求和公式为
DRGVN-QR算法的实现流程如图3所示。具体实现流程为：
输入动态资源图DRGVN={V，E，T，Sv(t)，Bu，v(t)，Dpu，v(t)，Bufv，Uv(t)}，随机生成的源目的节点对，给定的业务请求M。
输出源节点s到目的节点d的路径path（M），满足M的传输需求且具有多QoS保障。
步骤1根据卫星网络虚拟节点生成拓扑矩阵G，初 始 化 参 数：α、β、ω1、ω2、λ1、λ2、μ、Tmax、Dmax、Bmax等。
步骤2将代表不同时刻的蚂蚁kt放到源节点，并将源节点标记为已经访问。
步骤3使用算法1计算优化后的下一步节点集allowedkt。
图3 算法流程图Fig. 3 Algorithm process
步骤4蚂蚁根据式（18）计算出的概率在allowedk中选择下一个节点，并将节点标记为已经访问。
步骤5判断当前节点，如果不是目的节点则继续执行步骤6，如果是目的节点则执行步骤8。
步骤6判断allowedk集合是否为空，如果为空则该蚂蚁寻路失败返回执行步骤2，如果不为空则执行步骤4。
步骤7SDN控制器根据式（24）选取ρ值，然后使用式（21）更新信息素。
步骤8迭代结束后，将路径放入Pareto集合。
步骤9使用式（26）对Pareto集合中路径进行质量计算，输出最优解。
3 仿真实验
3.1 仿真场景及参数设置
本文使用STK进行类铱星星座仿真，星座共有6个轨道平面，每个轨道11颗卫星，共66颗卫星均匀分布，轨道高度780 km，轨道倾角86.4°。使用MATLAB进行算法仿真，算法详细步骤见2.4节。
文献［22］对蚁群的算法重要参数进行了大量实验分析，确定了使算法收敛速度和求解性能均达到最优的参数，本文选取α=1、β=5。蚂蚁数量一般与问题规模一致，一般认为节点数量的2/3是最优蚂蚁数量，因此选取m=40。信息素总量在500以内时，问题规模对于信息素总量的选择影响较小，本文选取信息素总量P=20。以上参数的设置能够保证算法性能最优。
设置单条路径信息素最大值Tmax=200，单条链路最大时延Dmax=1 000 ms，根据本文的优化目标，确定各性能指标的重要程度，选取ω1=0.8，ω2=0.2；λ1=0.2，λ2=0.4，λ3=0.4。仿真过程模拟连续发包1 500次，链路可用带宽Bmax=200 Mbps［23］，每次随机选择源和目的节点对。并 通 过 实 验 对 几 组s1、s2、s3、s4取 值 进 行 验证，其网络平均吞吐量如图4示。
图4 网络平均吞吐量Fig. 4 Average throughout of network
实验结果表明当s1=s2=s3=s4=0.5时，仿真后期网络吞吐量出现大幅度波动，因为ρ值固定，算法初期表现较好，但后期没有及时调整路径信息素浓度，出现了缓存队列排队较长的现象，吞吐量无法提升。当s1=0.1、s2=0.3、s3=0.5、s4=0.7时，网络吞吐量整体上明显提高，且比较稳定，但仍有轻微波动，当s1=0.2、s2=0.4、s3=0.6、s4=0.8时，整个网络的吞吐量达到较优状态，且能够保持稳定。根据上述现象，本文选取s1=0.2、s2=0.4、s3=0.6、s4=0.8。
3.2 仿真结果分析
本文在相同实验环境下，将所提出的算法与经典Dijkstra算法和基于多QoS约束的蚁群优化路由算法（QoS-ACO）［16］，以及基于SDN的最短路径算法（SDN-SPF）［20］进行比较。
算法的平均求解时间如图5所示，该指标体现了算法的收敛性。以Dijkstra算法的表现为基准，纵坐标表示所对比算法的求解时间与Dijkstra算法的求解时间的比值。从图中可以看出，SDN-SPF算法在仿真初期求解时间相对较快，但随着仿真的进行，为了缓解网络拥塞该算法的求解时间逐渐增大。本文DRGVN-QR算法在仿真初期就获得了较好的收敛速度，随着仿真的进行，由于本文算法动态调整信息素挥发系数，求解时间出现波动现象，但整体上优于其他算法。因为加入了优化allowedk的算法，DRGVN-QR算法的收敛速度有所提升。
图5 平均求解时间Fig. 5 Average solving time
算法的平均端到端时延如图6所示。在仿真前半段，时延变化平缓，几种算法的时延差别不明显。但随着数据包的不断发送，本文所提DRGVN-QR算法的平均时延最低，与其他算法相比网络端到端时延最大降低了7.8%，且明显优于其他算法。这是因为本文在ACO的启发函数中引入了时延作为重要参考因素，并且挥发系数ρ的值随着网络的变化而动态改变。在选取路径时，本文考虑了一个时间段内的路径代价从而缓解网络拥塞，因此所选路径具有较好的时延性能和带宽优势。
算法的平均丢包率如图7所示，可以看出，随着请求数量的增加网络负载逐渐变大，时延和丢包率也随之增大，与其他算法相比本文所提DRGVN-QR算法的丢包率最低，最大降低了8.6%，且增长趋势越来越小，最终能够保持一个相对稳定状态。这是因为本文避免了路径切换带来的丢包问题，时延降低的同时也能降低丢包率。
算法的平均时延抖动如图8所示。可以看出，在仿真前期，各算法的时延抖动没有太大差距，但随着请求数量的增加，其他算法的平均时延抖动明显增加，DRGVN-QR算法的平均时延抖动整体低于其他算法，最大降低了9.2%，且这种优势愈加明显，最后逐渐趋于稳定。仿真表明，DRGVN-QR算法在网络平均时延抖动方面表现良好，能够有效地提升了网络数据传输的稳定性。
综合考虑以上因素，本文算法通过与其他算法进行对比，体现了良好的性能。
图6 平均端到端时延Fig. 6 Average end-to-end delay
图7 平均丢包率Fig. 7 Average packet loss rate
图8 平均时延抖动Fig. 8 Average delay jitter
4 结 论
本文针对卫星网络特性，首先，建立一种虚拟节点动态资源图模型刻画节点切换和资源的动态性，基于此建立最小路径代价多目标优化模型，该模型同时考虑了节点的切换状态、缓存以及链路的剩余带宽、时延等信息。其次，利用蚁群算法求解满足多QoS约束的最小代价路径集合，并讨论蚁群算法信息素挥发系数的选取问题。最后，设计一种幂指加权公式选出最优路径，保证数据传输的可靠性。通过仿真验证：
1） 在铱星星座仿真环境中，本文所提DRGVN-QR算 法 与SDN-SPF和QoS-ACO算法相比，网络端到端时延最大降低了7.8%。
2） 同时平均丢包率最大降低了8.6%，提高了交付成功率。
3） 平均时延抖动最大降低了9.2%，网络稳定性得到显著提升。
