李 澎，赵 祥，胡剑平，魏乐乐，张 冰

（1 北京遥测技术研究所 北京 100076 2 西安电子科技大学综合业务网理论及关键技术国家重点实验室 西安 710071）

引言

随着天地一体化网络技术和多媒体业务的发展，低轨道LEO（Low Earth Orbit）卫星网络因其业务传播时延短、建设成本低，成为研究的重点[1]。许多LEO 卫星系统在地面上不同区域建有信关站，用于业务就近下地，从而达到提升网络容量的目的。但是，由于全球用户流量分布不均，卫星业务就近下地的方式将在信关站处形成漏斗形流量，引发链路拥塞问题，影响用户的服务质量QoS（Quality of Service）。加之，卫星网络需要支持多种业务类型，传统路由的单约束条件也不再能够满足多种用户QoS 需求。因此，设计满足用户多种不同业务需求的卫星QoS 路由算法至关重要。

针对LEO 卫星网络QoS 路由问题，国内外许多学者进行了较为深入的研究。例如，Mohorcic M 等提出业务流分类算法TCD（Traffic Class Dependent）[2]。Karapantazis S 等人在LAOR 算法的基础上提出多业务按需路由算法MOR（Multiservice On-demand Routing）[3]。龙飞等提出了一种以端到端时延、时延抖动、链路利用率和带宽为QoS 指标的路由算法[4]。饶元等提出一种多路径路由算法MPIR（Multipath Inter-satellite Link (ISL) Routing）[5]。但这些算法均未考虑信关站漏斗型流量的问题，同时无法兼顾提高业务QoS 保障、缓解网络拥塞以及减少计算复杂度的三方面需求。

本文针对以上问题和特定的LEO 卫星网络模型，提出一种基于区域划分的多业务QoS 路由算法MSR-RP（Multi-Service QoS Routing Algorithm based on Region Partition）。该算法考虑了信关站有限分布造成的漏斗流量问题，一方面通过划分动态区域，减少区域节点数量，降低了算法整体计算复杂度；另一方面，在轻负载区域采用最短路径算法计算路由，重负载区域采用多目标遗传算法计算路由，保障不同业务QoS 并实现负载均衡。最后，对MSR-RP 路由算法进行建模与仿真实现，设计不同的仿真场景，测试路由算法的性能指标并与TCD 算法进行对比分析。仿真结果表明，MSR-RP 算法在为各类业务提供不同的QoS 保障的同时，具有星上应用简单、负载均衡性能良好的特点，并提高了网络吞吐量。随着全局业务量的增大，其网络平均时延、丢包率低于TCD 算法。

1 MSR-RP 算法

1.1 算法总体设计框架

针对LEO 卫星网络业务数据通过信关站下地形成的漏斗形流量造成的网络拥塞问题，本文将LEO 卫星网络动态划分为轻负载区域和重负载区域，并采用集中式路由算法，根据虚拟拓扑策略划分时间片，控制中心根据时间片分别为轻负载区域和重负载区域卫星节点计算路由，并上注至各个卫星，如图1 所示。控制中心在计算轻负载区域卫星路由时使用最短路径算法；控制中心在计算重负载区域路由时，以最大化网络吞吐量和最大化负载均衡指数为目标，将不同业务的QoS 指标作为约束条件，使用遗传算法计算各类业务路由，实现负载均衡的同时为多种业务提供QoS 保障；最后，通过采用PQ 多队列调度机制对业务进行分类调度，保证高优先级业务优先转发，更好地保证了高优先级业务的服务质量。

在该算法中，卫星节点只需要根据控制中心上注的路由表进行数据分组的构造与转发，无需计算路由，减轻星上计算复杂度。算法设计主要涵盖以下四个方面：动态区域划分、轻负载区域路由计算、重负载区域路由计算和多队列调度机制，在第2 节会分别对其进行详细介绍。

1.2 算法整体流程

①将LEO 卫星网络运行周期划分为不同时间片，计算各个时间片对应的卫星网络虚拟拓扑；

② 根据各个时间片中信关站区域的位置关系将LEO 卫星网络划分为重负载区域和轻负载区域，重负载区域的节点包含卫星节点和信关站节点，轻负载区域节点只有卫星节点；

③控制中心按照2.3 节计算方式计算各个时间片轻负载区域卫星节点路由；按照2.4 节计算方式计算重负载区域卫星节点各业务路由；

④ 控制中心以时间片为单位，提前将路由上注至各个卫星节点；

⑤ 各个卫星节点按照时间片切换路由表；

⑥ 卫星将数据分组发往各个发送队列缓存，等待队列调度发送。

2 算法实现机制

2.1 业务分类

随着多媒体业务的发展，网络中传输的业务类型也复杂多样，不同类型的业务具有不同的QoS 需求，针对网络中可能存在的业务类型，本文将网络常见流量分为表1 中的三类。

表1 业务流量分类Table 1 Traffic classification

根据思科2016～2021 年网络流量预测报告[6]，目前网络中Class A 类流量大约占总流量的19%，Class B 类流量大约占72%，Class C 类流量大约占7%。本文设定网络中三种流量比例wA:wB:wC=2:7:1。

本文将Class A 和Class B 类业务的QoS 指标分别定义为以下约束：

①端到端时延约束Dmax：

上式中，Dp(s,d)表示从源节点s到目的节点d可用路径的端到端传播时延。

② 最小传输带宽约束Bmin：

上式中，Bp(s,d)表示从源节点s到目的节点d的路径的最大传输带宽。B(e)表示链路e的剩余带宽。

2.2 动态区域划分

针对卫星业务通过境内信关站下地的情况，文献[7]提出将卫星网络划分为轻负载区域和重负载区域，并使用Dijkstra 算法分别计算路由以实现更好的负载均衡。本文采用类似的思想，重负载区域指覆盖信关站区域上空的若干卫星节点构成的空间区域，其他卫星节点构成的区域为轻负载区域。

如图2 所示，黑色虚线框表示信关站上空区域，红色框为重负载流量区域，红色框以外区域为轻负载区域，绿色三角形为可能的信关站分布情况。当卫星网络流量需要经过信关站下地时，轻负载区域的流量会在重负载区域汇聚，然后经过信关站头顶星下地。

2.3 轻负载区域路由计算

轻负载区域业务流量汇聚效应小，不易发生拥塞，因此无论何种业务类型均使用相同的路径转发至重负载区域边沿节点卫星，后由重负载区域进行区分业务的路由。

轻负载区域路由计算根据星间链路长度为代价，采用最短路径算法获得源端到目的端的最短路由。当路径计算完成后，需要对每颗卫星的路由进行裁剪处理，只需要保存从源卫星出发到重负载区域边沿卫星节点的部分路径作为相应卫星的路由即可。数据分组转发至重负载区域边沿卫星节点后会按照业务类型重新选择传输路径。

2.4 重负载区域路由计算

重负载区域需要承载自身覆盖区域以及轻负载区域的流量。重负载区域路由计算为多目标优化问题，使用遗传算法，以最大化网络吞吐量和最大化负载均衡指数为目标设计适应度函数，将不同业务的QoS 指标作为约束条件，统一计算重负载区域每颗卫星不同类型业务的路由。

算法优化的目标为最大化网络吞吐量和最大化网络负载均衡因子，分别见式（3）和式（4）。遗传算法的适应度评价函数见式（5）。

式（3）表明，网络中的吞吐量为三类业务的轻负载和重负载区域的加和，wA、wB、wC分别为三类业务的权重，分别为三类业务的接收率，为源卫星H的总业务流量，H为重负载区域卫星集合；式（4）中Bi,j为星际链路li,j的实际剩余带宽，LFL为星地链路集合，M为信关站集合；式（5）中α，β为权重系数，且满足α+β=1。

上述数学模型为多目标优化模型，本文采用遗传算法求其全局最优解，使网络具有最大吞吐量和较好负载均衡的同时，可以满足各种业务的QoS 需求。为了更好地描述算法，首先对以下关键概念进行定义：

①个体编码：本文遗传算法的输出为重负载区域每颗卫星传输A、B 和C 三类业务的路由路径，因此，以每类业务到达信关站的路径作为基因，每个个体染色体由重负载区域所有卫星传输Class A、Class B 和Class C 类业务的路由路径三部分组成，染色体长度len=X×Y×3，其中X、Y分别为重负载区域包含的轨道数和同轨卫星数。编码方式如图3 所示。

② 交叉操作：交叉是以交叉概率pc把两个亲代个体的部分结构替换重组生成新的两个新个体的操作。本文采用奇数代单点交叉和偶数代多点交叉的混合交叉方式，提高算法的搜索能力。

③变异规则：以变异概率pm对部分个体进行变异操作，可以为种群引入新的个体，扩展新的算法搜索空间，保持种群多样性，避免陷入局部最优。由于本文个体基因为数据传输路径，因此需要保证经过变异操作后的路径仍为完整通路。

④ 选择操作：选择操作的目的是将优化的个体直接遗传到子代种群。本文采用精英保留和锦标赛选择相结合的选择策略，联合亲代种群和中间种群进行筛选得到子代种群。

重负载区域卫星路由计算采用遗传算法，具体流程如图4 所示。

①根据SPF 算法获得每颗卫星到达各个信关站的最短路径和与最短路径不相交的次短路径，作为基因候选集；

② 构造初始种群。根据①中获得的基因候选集，每个个体随机为每颗重负载区域卫星的每类业务选择一条到达信关站的路径，按照个体编码规则组成个体，不同的J个个体组成初始种群；

③根据式（5）计算个体适应度。判断当前种群是否满足终止条件（当连续Q 代的最优个体没有改变时，结束算法），若满足，结束算法，否则执行④；

④ 若达到最大迭代次数，输出最优个体，结束算法，否则执行⑤；

⑤ 使用选择规则选择保留的个体，生成下一代种群；

⑥ 使用交叉规则对当前种群中的个体进行交叉操作；

⑦ 使用变异规则对当前种群中的个体进行变异操作；

⑧ 为了保证满足Class A 类业务时延约束，在计算个体适应度之前将当前种群中不满足Class A 类业务时延约束的个体淘汰，以保证Class A 类业务的QoS 需求；

⑨ 执行③。

2.5 多队列调度机制

多队列调度机制指使用优先级调度多队列调度机制，确保高优先级业务优先发送，更好地保障高优先级业务QoS 需求。本文使用PQ（Priority Queuing）多队列调度机制，设计队列模型由三部分构成：分类器、FIFO 缓冲队列和调度器。

分类器通过提取数据分组中的标记字段获得数据分组的类型，放入不同的FIFO 缓冲队列等待调度器调度，若FIFO 缓冲队列已满，则丢弃数据分组；FIFO 缓冲队列主要是临时存储各类业务数据分组供调度器调度，本文针对Class A、Class B 和Class C 类业务设置三个FIFO 缓冲队列；调度器负责对缓冲队列中的数据分组进行严格优先级调度。

3 算法仿真与实现

目前主流的网络仿真软件有NS2、QualNet 和OPNET 等。本文研究采用STK[8]和OPNET[9]联合仿真的方式进行卫星网络的建模和对MSR-RP 算法的仿真实现。

3.1 网络层

本文中所研究的网络层模型，包括1 个控制节点controller、4 个地面信关站节点（S1、S2、S3 和S4）和72 个LEO 卫星节点，如图5（a）所示。

3.2 节点层

由图5（a）的网络层模型可知，网络中共有三种不同类型的网络节点，其对应三种不同的节点模型。下面就三种不同的节点模型分别进行介绍。

①卫星节点模型

卫星节点模型用于模拟卫星网络中卫星的运动以及产生、发送和接收数据分组等功能。本文研究中卫星节点的节点层模型如图5（b）所示，包括source、routing、5 对无线收发机和5 个发送队列模块构成。

② 信关站节点模型

信关站节点用于接收卫星网络中的下地数据，由sink、queue_gw 和一对收发机构成，如图5（c）所示。

③控制节点模型

控制节点controller的作用是模拟控制中心的路由上注功能，由control 模块构成，如图5（d）所示。

4 算法性能分析

通过设计仿真场景，对TCD 算法和MSR-RP 算法在平均时延、丢包率、吞吐量和星地链路负载均衡指数方面进行对比，评价MSR-RP 整体路由性能，进一步验证MSR-RP 算法的有效性和正确性。

4.1 平均时延

网络平均时延指对网络数据分组从源节点到目的节点的时延平均值，计算方法如式（6）所示。

其中，Davg为网络平均时延，Num为网络中传输成功的数据分组总数，Di为网络中传输的第i个数据分组从源节点到信关站节点传输的总时延，该时延包括数据分组的排队时延和传播时延。

图6 为TCD 算法和MSR-RP 算法三类业务平均时延随着全局业务量的变化情况。由图可知，各类业务的平均时延随着全局业务量的增加而增加，这主要是由于排队时延的增加导致的。同时，Class A 类业务为时延敏感型业务，执行PQ 队列调度的时候优先级最高，两种算法均能为其始终保持着较低的平均时延，满足其QoS 需求。但是MSR-RP 算法Class A 类业务的平均时延略大于TCD 算法，这是由于重负载区域在计算Class A 类业务路径时，以不增加其原有路径跳数为变异原则，尽可能为Class A 类业务选择最短传输路径，因此MSR-RP 算法中部分卫星节点的Class A 类业务不是以最短路径进行传输，所以其平均时延略高于使用最短路径传输Class A 类业务的TCD 算法。对于Class B 类业务，虽然TCD 算法使用最大剩余带宽的路径传输该类业务，但是该策略会导致输出路径跳数远大于最短路径的跳数，同时由于使用分布式计算，各节点计算时采用相同的带宽拓扑，输出路径仍会造成大量节点的Class B 类业务流量汇聚到相同的传输路径上，造成部分链路拥塞，增加时延。而MSR-RP 算法在轻负载区域使用最短路径算法，重负载区域使用遗传算法计算重负载区域全局最优解，合理分配流量，提高了链路利用率，减少了网络拥塞，因此对Class B 类业务的传输时延也具有一定的保证。Class C 类业务具有最低的优先级，因此其平均时延大于高优先级业务。

4.2 丢包率

丢包率指网络在传输过程中数据分组丢失的个数占传输数据分组总数的比值，丢包率的计算如式（7）所示。

其中，LR为丢包率，Nsend为网络中总的数据分组发送数量，Nrecv为网络中节点实际收到的数据分组数量。

图7 为TCD 算法和MSR-RP 算法三类业务丢包率随着全局业务量的变化情况。由图可知，TCD 算法和MSR-RP 算法的Class A 类业务的丢包率一直维持较低的水平，这是由于两者均采用PQ 多队列调度，Class A类业务具有最高的优先级，会被优先发送，更好地保障了其QoS 需求。随着全局业务量的增加，Class B 和Class C 类业务的丢包率也随之增加，但是由于MSR-RP 算法具有更好的负载均衡能力，因此其Class B 类业务的丢包率始终小于TCD 算法。Class C 类业务由于其没有QoS需求，因此其丢包率远远大于Class A和Class B类业务。

4.3 吞吐量

吞吐量指网络在没有丢包的情况下能够传输的最大业务速率，以比特每秒为单位，吞吐量的计算如式（8）所示。

其中，C为吞吐量，Nrecv为时间T内网络中成功接收的数据分组数量，Lpkt为传输数据分组的长度，T为仿真时间。

图8 为TCD 算法和MSR-RP 算法三类业务吞吐量随全局业务量变化情况，由图可知，Class A 和Class B 类业务的吞吐量随全局业务量的增长而增加。由于本文中三类业务的权重比例为2:7:1，因此在全局业务量比较小的时候，两种算法三类业务的吞吐量比例均接近2:7:1。但是随着全局业务量的增加，MSR-RP 算法为了更好地满足Class B 类业务的QoS 需求，重负载区域路由在计算时将更多的带宽资源分配给了Class B 类业务，从而Class C 类业务的吞吐量随着全局业务量的增加而有所降低。与TCD 算法相比，MSR-RP 算法更好地保障了Class B 类业务的服务质量。

对比TCD 算法，对MSR-RP 算法的有效性和正确性进行了验证。仿真结果表明，MSR-RP 算法与TCD算法相比，在保证各类业务QoS的同时，具有良好的负载均衡能力，网络的吞吐量有较大提升。仿真结果表明了MSR-RP 算法的正确性和有效性。

5 结束语

本文对LEO 卫星星座QoS 路由问题进行研究，针对LEO 卫星网络通过信关站就近下地的漏斗形流量产生的网络拥塞问题，提出了一种基于区域划分的多业务QoS路由算法MSR-RP，并使用STK 和OPNET 仿真软件对该算法进行仿真实现。设计仿真场景，通过MSR-RP算法与TCD 算法进行平均时延、丢包率和吞吐量方面的对比，分析和评估了MSR-RP 算法的性能。结果表明，MSR-RP 算法在实现良好的网络负载均衡，提升网络吞吐量的同时，可以为Class A 类业务保持较低的传输时延，为Class B 类业务提供尽可能大的服务带宽，保障了不同业务的QoS 需求。

MSR-RP 算法能够有效地运行在本文特定的LEO 卫星星座网络上，对于其他极轨或近极轨LEO 星座网络，该算法的设计思想也具有一定的适应性。