SpaceFibre网络服务质量时隙资源分配算法*

郑静雅，安军社

(1. 中国科学院国家空间科学中心 复杂航天系统电子信息技术重点实验室， 北京 100190;2. 中国科学院大学， 北京 100049)

随着空间探测任务复杂度不断提升，卫星有效载荷通信网络的数据量迅猛增长、数据传输速率不断提高，现有SpaceWire[1]等星载数据网络已不能满足超高速率航天应用场景。因此欧洲航天局提出了新一代超高速星载数据链路SpaceFibre技术[2]，该技术具有高传输率、高带宽、低误码率等特点[3-5]。SpaceFibre物理链路包含多条虚拟通道(Virtual Channel，VC)，每条VC可发送不同类型数据流。当数据流过载导致多条VC同时请求链路带宽资源时，SpaceFibre网络采用服务质量(Quality of Service，QoS)机制对各虚拟通道进行仲裁，该机制由优先级优先权、预留带宽和调度三种子机制组成[6]。

SpaceFibre协议对优先级优先权子机制和预留带宽子机制进行了详细描述，但没有说明调度子机制中时隙资源分配方法。时隙资源分配控制网络带宽分配，直接影响系统时延性能。由于星载数据网络具有规模小、实时性和可靠性要求高等特点，不宜直接套用其他网络调度算法[7-8]。目前对SpaceFibre时隙资源分配问题的研究尚少，文献[9]提出一种简单二进制序列均匀调度表生成方法，仅占用较少硬件资源即可保证数据传输的确定性，但该方法在网络兼容性、算法鲁棒性和时延性能等方面还有待优化；文献[10]使用基本遗传算法生成调度表，然而该方法存在操作复杂和收敛速度慢等问题。

本文给出无调度、无冲突和冲突调度矩阵定义，建立网络QoS排队模型分析时隙资源数量、位置和周期对网络时延性能的影响。基于排队模型给出包含改进二进制序列调度子算法和改进混合单亲遗传调度子算法的时隙资源分配算法，两个子算法相辅相成、互为补充。前者通过改进时隙数目使算法向后兼容SpaceWire网络；为提高算法鲁棒性，增加时隙长度和链路带宽约束，并改进初始时隙位置生成方式；通过改进时隙补偿方法减少了时隙冲突。后者将前者生成的调度矩阵作为初始个体，在基因移动算子基础上增加交叉算子，并使用基因移动算子对交叉子代进行二次遗传操作。在Opnet平台下自行搭建网络QoS仿真模型，对算法有效性进行仿真分析。结果表明，该算法可根据不同数据流的特点生成具有航天工程实用价值的低延时SpaceFibre星载数据网络时隙资源分配方案。

1 SpaceFibre网络QoS性能分析模型

1.1 网络服务质量机制分析

优先级优先权、预留带宽和调度三种QoS子机制均集成于SpaceFibre介质访问控制器(Medium Access Controller，MAC)中。

优先级优先权计算如式(1)所示[2]。

PriPrei=2B(Q-1-Ei)+B

(1)

其中：B表示带宽信用限制；Q为优先级数；Ei表示编号为i的VC优先级值，Ei越小优先级越高。

预留带宽是一种依据虚拟通道预留带宽和VC带宽使用率计算带宽信用的QoS机制。带宽信用BWCredit计算如式(2)所示[2]，n为虚拟通道发送数据字的数目，可用带宽AvailBW指自上次带宽信用更新起网络节点所有虚拟通道发送字数总和。已用带宽UsedBW指自上次带宽信用更新后VCi发送数据字的数目。标准化期望带宽Fi指VCi分配带宽占链路总带宽的比例。

(2)

优先权为PriPre与BWCredit之和。通常优先级越高，优先权越大。当高优先级虚拟通道带宽信用达到B时，低优先级VC优先权才可能较大。

调度QoS子机制为链路的确定性传输提供保障。SpaceFibre网络中时间轴被划分为若干固定长度的时帧，作为基本周期性时间单元。每个时帧又包含若干时隙，时隙是网络最小时间单位。

各虚拟通道均具有时帧调度向量，该向量记录本VC在一个时帧的各时隙中是否被允许参与调度。所有VC的时帧调度向量构成网络节点二进制调度矩阵，该矩阵行数目为VC数，列数目为时帧内总时隙数。调度矩阵中1表示有效时隙，即指定时隙允许该VC参与调度；0表示空闲时隙，即在指定时隙不允许该VC发送任何数据。当同一时隙中允许多条虚拟通道参与调度时，MAC选择优先权较大的虚拟通道进行数据传输。典型的SpaceFibre服务质量机制混合使用实例如表1[11]所示，该表可抽象为二进制8×8调度矩阵。

表1 SpaceFibre网络QoS机制混合使用实例Tab.1 SpaceFibre QoS mechanism mixed instance

VC0和VC1优先级最高，其他VC具有较低且相同的优先级。在时隙1，除VC1外其他虚拟通道均可参与调度。优先级最高的VC0拥有最高优先权，所以在时隙1优先选择VC0发送数据。当VC0无发送数据请求时，MAC在VC2～VC7中选择具有待发送数据且BWCredit最高的虚拟通道发送数据。每进行一次数据发送操作，各VC均需更新带宽信用和优先权。优先级不变时，被调度VC的带宽信用降低，该虚拟通道优先权也降低，有效避免了单一VC持续抢占带宽资源的问题。三种QoS子机制的混合使用保证了关键卫星数据的优先传输，为网络的可靠传输提供了保障。

在星载数据网络中，主要从数据传输延时、带宽和可靠性三方面对网络数据流的服务质量进行评估[12]。不同空间任务流量对网络QoS的要求不同。例如控制类流量典型特征是数据包生成具有随机性、数据包较小和实时性要求较高，实时视频显示业务同时具有较高实时性需求和带宽需求。因此，需采取有效算法合理分配SpaceFibre网络时隙资源，以满足各有效载荷数据流的带宽需求，从而减少数据传输延时并保障数据可靠传输。

1.2 网络服务质量数学模型

1.2.1 网络条件约束及参数定义

以SpaceFibre网络QoS机制分析为基础，建立网络排队模型定量分析时隙分配对网络时延性能的影响。网络模型相应约束如下：网络运行期间链路无故障；网络运行时虚拟通道的数目保持不变；网络运行期间虚拟通道优先级值不变。为便于形式化描述，网络参数说明如表2所示。

表2 模型参数表Tab.2 Parameter list of model

根据SpaceFibre网络约束条件及参数定义引入调度矩阵相关定义。

定义1给定网络节点调度矩阵SN×L，对任意i∈[0,N-1]，j∈[1,L]均有si,j=1，则称SN×L为无调度矩阵。

根据网络服务质量分析和参数定义得到如图1所示的SpaceFibre网络时帧结构。

图1 SpaceFibre时帧结构Fig.1 Time frame structure of SpaceFibre

1.2.2 网络排队模型

SpaceFibre星载数据网络服务质量可以抽象为单服务台、多虚拟通道队列的排队问题，排队模型如图2所示。每个队列代表一条虚拟通道，介质访问控制器MAC被抽象为服务台。虚拟通道数目N∈[1,32]，VCi(i∈[0,N-1])数据流符合到达速率为λi的泊松分布。VC0至VCN-1优先级依次降低。为排除缓存容量[13]对网络时延性能的影响，排队系统最大队列长度为无穷大。

图2 SpaceFibre网络QoS排队模型Fig.2 Queuing model for SpaceFibre QoS

网络服务质量排队模型服务速率为：

μ=Vlink/Lframe

(3)

VCi平均端到端延时为：

(4)

若SN×L为无调度矩阵，MAC不使用调度子机制，网络QoS机制可进一步抽象为带有非抢占优先级的M/G/1排队模型，平均等待时间为[14]：

(5)

无调度矩阵队列平均延时与时隙分配无关，仅与排队系统参数有关。在高优先级队列长期占用链路带宽的极端情况下，低优先级队列平均延时可能会超出可接受范围。当高优先级带宽需求较大时，应采用调度子机制保障数据的确定性传输。

若SN×L为无冲突调度矩阵，虽使用调度子机制，但不考虑高优先级抢占时隙的情况。平均等待时间如式(6)所示，ρiWi为VCi数据包传输时间。

(6)

VCi数据包到达时有服务台正在服务VCi和排队模型处于VCi空闲时隙两种可能，相应Ri为：

(7)

VCi有效时隙间隔为Di，第k个数据包到达时刻为εk，N(Di)为Di时间内达到的数据包总数，则数据包有效时隙等待时间为过滤泊松过程：

(8)

过滤泊松过程的特征函数为[15]：

(9)

(10)

设随机变量X(t)=Y2(t)，类似可得：

(11)

当时隙位置均匀分布时，有效时隙间隔为：

Di=TF/Hi

(12)

且时帧长度TF满足：

TF=Lτ

(13)

所以SN×L为无冲突调度矩阵时，SpaceFibre服务质量排队模型中VCi平均等待时间为：

(14)

若SN×L为冲突调度矩阵，平均延时需考虑优先级占用。 VCi最大平均等待时间为：

(15)

(16)

经整理得：

(17)

若SN×L为冲突调度矩阵且排队模型参数，同时隙队列数目一定时，Di越小平均延时越低，因此应尽量减少有效时隙间隔。此外，同时隙VC数不宜过多，否则会因增加平均等待时间而增加Ti。

2 SpaceFibre网络QoS时隙分配算法设计

根据网络QoS性能分析模型，提出SpaceFibre网络服务质量时隙资源分配算法。该算法包含两个子算法：改进的二进制序列调度(Improved Binary Sequence Scheduling，IBSS)子算法和改进的混合单亲遗传调度(Improved Hybrid Partheno-Genetic Scheduling，IHPGS)子算法。IBSS子算法是IHPGS子算法的初始种群之一， IHPGS进一步降低了IBSS的网络延时。若IBSS生成的调度矩阵满足可接受延时要求，可不进行IHPGS操作，但两子算法相互配合可获得网络时延性能更优的时隙资源分配方案。

2.1 改进的二进制序列调度IBSS

IBSS在简单二进制序列算法[9](Simple Binary Sequence Algorithm，SBSA)基础上根据实际工程应用场景进行修正。

为向后兼容SpaceWire时间码，IBSS改进了时隙数目。SpaceWire网络是先于SpaceFibre网络的上一代星载数据网络，该网络设置6 bit时间码以实现时间同步。为组建SpaceWire高速-SpaceFibre超高速星载数据网络，时帧TF内的时隙数目L固定为64。这一修正可能会使时帧长度增加而导致平均延时增加，但由式(13)知，可通过调整时隙长度τ以保证TF不变。

IBSS增加了时隙长度约束以降低误码率。若完整数据帧传输时间大于τ，则在单个有效时隙内MAC无法发送完整数据段，导致节点组帧失败，进而，引起数据传输错误。因此，τ应大于最长TF数据帧传输时间以保障所有VC数据正确传输，设nlane为SpaceFibre网络节点物理通道数，Lfmax为网络最大数据帧长度，则τ应满足：

(18)

IBSS考虑了广播通道占用带宽对时隙资源分配的影响。除进行数据包传输外，SpaceFibre网络还需分配部分带宽给广播通道以用于整个网络的监管。设广播消息预留带宽占链路总带宽比例为pb，则每条虚拟通道期望带宽Fi修正为：

(19)

其中，Pi/Qi为期望带宽Fi的最简分式表达式。当Qi大于L时，要对Fi进行修正，具体修正方式为Pi逐1增加，Qi保持不变，直至新的最简分式满足：

(20)

VCi时帧调度向量为：

si=(si,1,si,2,…，si,L)

(21)

Btotal为链路在时帧TF内的总带宽，VCi在TF内分配带宽为Bi，则分配给VCi的带宽比Ri为：

(22)

令F′i=Ri[9]，得VCi有效时隙数为：

(23)

(24)

IBSS子算法对低优先级补偿和控制流量补偿操作进行改进。极端情况下，简单二进制序列算法的补偿操作可能会因时隙冲突而无法完成。为满足各流量带宽需求、减少时隙冲突，IBSS在进行时隙补偿时，选择最接近待补偿位置且冲突最少的空闲时隙位置进行置1处理。

IBSS子算法具有硬件资源占用较少、延时较低、鲁棒性和兼容性较好等特点，为SpaceFibre网络时隙资源的合理分配提供了基本保障。IBSS描述示意如图3所示，具体算法流程见算法1。

图3 IBSS描述示意Fig.3 Description of IBSS

算法1 改进二进制序列调度IBSSAlg.1 Improved binary sequence scheduling

2.2 改进的混合单亲遗传调度IHPGS

单亲遗传算法是一种取消了交叉操作并使用变异操作替代的特殊遗传算法。改进单亲遗传算法[16](Improved Partheno-Genetic Algorithm，IPGA)消除了变异概率，修改了选择和变异操作使算法更加高效稳定，但该算法的遗传操作均在单条染色体上进行，易陷入“进化瓶颈”。

面向SpaceFibre星载数据网络应用的改进混合单亲遗传调度IHPGS子算法在IPGA遗传算子的基础上增加最优个体与次优个体交叉算子并使用基因倒位、基因换位、基因右移和基因左移等基因移动算子对交叉后的染色体进行二次遗传操作，增加了个体间的基因交互、有效克服了个体早熟的问题。IHPGS子算法运行时只需设置初始种群规模和迭代终止条件，无须设置其他参数，具有遗传操作简单、运算速度快的特点。

IHPGS子算法将IBSS生成的调度矩阵作为初始个体。整个初始种群包含IBSS生成的优良个体和按带宽需求生成的普通个体，进化过程中两者相互竞争并进行基因交换。一定进化程度的初始种群提高了IHPGS收敛速度，降低了算法对种群多样性的依赖。IHPGS子算法描述如图4所示。

图4 IHPGS描述示意Fig.4 Description of IHPGS

VCi优先级值为Ei，平均延时为Ti，则IHPGS子算法适应度函数Cfit为最小化调度矩阵个体中各虚拟通道平均延时加权和：

(25)

十种遗传算子详细描述如下。基因移动算子在每次操作前需随机获取基因段首尾位置I、J(1≤I

遗传算子1：组内最优个体保持不变。

遗传算子2：对组内最优调度矩阵个体每行执行基因倒位。基因倒位：将I到J段的基因序列倒序，并将倒序后的选定基因段插入位置P。

遗传算子3：对组内最优调度矩阵个体每行执行基因换位操作。基因换位：仅交换位置I和J的基因，将交换后的选定基因段插入位置P。

遗传算子4：对组内最优个体每行执行基因左移操作。基因左移：位置I+1到J的基因段向左移一个基因位，位置I基因放至J原位置，将移位后基因段插入位置P，具体操作见图5(b)。

遗传算子5：对组内最优个体每行执行基因右移操作。基因右移：位置I到J-1的基因段右移一个基因位，位置J基因放至I原位置，将移位后基因段插入位置P，具体操作见图5(c)。

(a) 初始基因序列(a) Initial gene sequence

(b) 基因左移结果(b) Result of left-shift operator

(c) 基因右移结果(c) Result of right-shift operator图5 基因移位算子示意Fig.5 Description of shift operators

遗传算子7：对交叉子代每行执行基因倒位。

遗传算子8：对交叉子代每行执行基因换位。

遗传算子9：对交叉子代每行执行基因左移。

遗传算子10：对交叉子代执行基因右移。

迭代终止条件可以是最优调度矩阵个体各虚拟通道平均延时均在可接受范围内，也可以是迭代次数限制，还可以是适应度函数开始保持不变。具体终止条件需结合实际工程应用按需选择。

3 仿真与分析

3.1 仿真与验证

为深入探讨算法有效性，使用Opnet软件搭建网络仿真模型，对比不同算法生成调度矩阵的时延性能。Opnet平台没有适用于SpaceFibre标准的仿真模块，在Opnet Modeler 14.5平台下自行搭建如图6所示网络QoS仿真模块，该模块包含数据包源、虚拟通道缓冲区、MAC和发射机四部分。src0～src5数据包源生成指定速率的数据包并存储在相应VC缓冲区queue0～queue5中。MAC根据调度矩阵给定的传输方案进行仲裁，数据最终通过发射机传输到SpaceFibre网络。

图6 SpaceFibre网络QoS仿真模型Fig.6 Simulation model of SpaceFibre QoS

仿真过程中各VC采用如表3[9]所示的流量特征。不同流量类型依次对应SpaceFibre网络节点不同虚拟通道VC0～VC5。网络节点广播通道预留带宽为10%，SpaceFibre网络链路速率为2.5 Gbit/s。

表3 网络流量特征Tab.3 The characteristics of each traffic in the network

简单二进制算法时隙数L1为50而IBSS子算法时隙数L2=64，由网络QoS排队模型知，需在相同时帧下对比两算法时延性能。分别设置时帧TF为25 μs、50 μs、100 μs、200 μs、400 μs、800 μs和1600 μs并编号为0～6组。计算不同L下7组TF对应的时隙长度，计算结果如表4所示。

表4 时隙长度Tab.4 Time-slot length

为验证IHPGS子算法时延性能，将IHPGS子算法与IBSS子算法、基本遗传算法(Classic Genetic Algorithm，CGA)[10]、IPGA算法、二进制粒子群优化(Binary Particle Swarm Optimization，BPSO)[17]算法和二进制入侵杂草优化(Binary Invasive Weed Optimization，BIWO)[18]算法进行对比分析。为比较各算法收敛速度，设置CGA、IPGA、BPSO、BIWO和IHPGS迭代终止条件均为循环数目达迭代次数限制值30。各算法其他参数见表5。

表5 不同算法参数Tab.5 Parameters of different algorithms

SpaceFibre网络单通道节点的最大数据帧长度为256 B，由式(18)可得，时隙长度需满足τ≥0.819 2 μs。根据网络QoS排队模型可知，τ越大平均延时越大，因此选择τ=2 μs进行不同算法调度矩阵的仿真验证。

3.2 结果与分析

图7为SpaceFibre网络时隙资源分配IBSS子算法与简单二进制算法在7组时帧长度TF下各虚拟通道平均延时对比图。实线为简单二进制序列算法仿真结果，虚线表示IBSS子算法仿真结果。由分析结果可知，二者均实现了确定性延时。各VC平均延时随TF的增加而增大，与网络排队模型分析结果一致。两种算法中控制流量队列VC0的延时均维持在较低值。对比分析两种调度机制下VC1～VC5平均延时曲线可知，IBSS子算法对应虚拟通道平均延时曲线均低于简单二进制序列算法，且随TF的增大IBSS子算法的优势越明显。

图7 SBSA与IBSS平均延时Fig.7 Average delay under SBSA and IBSS

τ=2 μs时，IHPGS子算法与IBSS子算法、CGA、IPGA、BPSO和BIWO算法在Opnet网络仿真模型中的运行结果如图8所示。由图8可知，各调度机制下对时延性能要求较高的控制流量曲线都保持在较低位置。相比其他算法，IBSS子算法和IHPGS子算法在30 h仿真时间内各VC延时均趋于平稳。因此，在收敛速度方面IHPGS要优于CGA、 IPGA、BPSO和BIWO算法。IHPGS子算法最高延时曲线VC4要明显低于CGA、 IPGA、BPSO和BIWO最高延时曲线。所以无论是收敛速度还是时延性能，IHPGS均优于CGA、 IPGA、BPSO和BIWO。对比IBSS子算法和IHPGS子算法， 后者相比前者其延时曲线更加集中，这意味着各虚拟通道平均延时更加均衡。当高优先级VC平均延时在可接受范围内时，低优先级虚拟通道数据传输机会增多。

(a) CGA各虚拟通道延时(a) Delay of virtual channels under CGA

(b) BPSO各虚拟通道延时(b) Delay of virtual channels under BPSO

(c) IPGA各虚拟通道延时(c) Delay of virtual channels under IPGA

(d) BIWO各虚拟通道延时(d) Delay of virtual channels under BIWO

(e) IBSS各虚拟通道延时(e) Delay of virtual channels under IBSS

(f) IHPGS各虚拟通道延时(f) Delay of virtual channels under IHPGS

计算图8不同算法各VC平均延时及平均延时加权和，如表6所示。各虚拟通道平均延时加权和计算方法与式(25)相同，式中VCi优先级越高，相应优先级值Ei越小，则VCi权重αi越大。分析可知，CGA、BPSO、IPGA、BIWO算法、IBSS子算法和IHPGS子算法虚拟通道平均延时加权和依次降低。相比CGA、BPSO和 IPGA算法，IHPGS子算法中VC0平均延时略有增加但小于1.1 μs。对比CGA、BPSO、IPGA和BIWO算法，IHPGS子算法中VC1～VC5平均延时明显降低。相比CGA，IHPGS各虚拟通道平均延时分别下降53.51%、78.81%、99.75%、83.92%和58.41%。IHPGS各VC平均延时与BPSO相比分别下降35.14%、60.76%、99.63%、96.86%和78.24%。相比IPGA，IHPGS子算法虚拟通道平均延时分别下降67.58%、91.68%、54.80%、58.21%和91.94%。IHPGS子算法中VC1～VC5平均延时对比BIWO分别下降61.11%、38.71%、72.22%、55.62%和46.50%。比较IBSS子算法和IHPGS子算法， VC0～VC2平均延时基本相同，IHPGS子算法VC4和VC5平均延时降低是以VC3略微增加为代价的。若各VC可接受延时为15 μs，这种均衡可使所有VC平均延时均在可接受范围内。

表6 不同算法时延性能对比Tab.6 Delay performance under different algorithms

4 结论

对SpaceFibre网络服务质量机制进行分析并建立SpaceFibre网络QoS排队模型，定量分析时隙资源分配对虚拟通道平均延时的影响。基于时延性能分析模型，提出包含IBSS和IHPGS两子算法的SpaceFibre网络时隙资源分配算法。利用Opnet平台搭建网络服务质量仿真模型，对IBSS子算法、IHPGS子算法、CGA、BPSO、IPGA和BIWO生成的调度矩阵进行仿真验证并对比分析仿真结果。结果表明，该算法可明显降低网络平均延时，有效改善网络时延性能，为今后SpaceFibre星载数据网络设计实现中的时隙资源分配提供理论依据。该算法基于静态参数，在今后的研究中将分析VC数据流和物理传输参数的时变特征。