高级在轨系统中的虚拟信道混合调度算法研究

别玉霞 张秀奇* 王宇鹏 胡 智

①(沈阳航空航天大学电子信息工程学院 沈阳 110136)

②(沈阳师范大学软件学院 沈阳 110134)

1 引言

随着航空航天技术的发展，空间任务呈现复杂化、多样化、高速率、强突发等特点，对大容量和高实时传输及处理提出了要求。世界空间组织创立的空间数据系统咨询委员会负责开发各种适应航天器复杂化及有效利用有限空间资源的通信协议[1]。其初级阶段为以分包遥测、遥控为核心的常规在轨系统，高级阶段为能够实现空间链路层数据传输的高级在轨系统(Advanced Orbiting Systems,AOS)[2]。AOS通过划分虚拟信道(Virtual Channel,VC)[3]，可以在每条虚拟信道上传输来自星上不同服务需求的数据，汇成一条数据流后通过物理信道传输。AOS采用动态的虚拟信道调度技术，可以灵活处理多信源、多用户、多目标的高速率数据业务，实现多用户高效共享同一条物理信道，从而满足不同航天器和不同类型用户的传输需求[4]。

虚拟信道调度是按照一定的调度顺序，以时分复用的方式对信道中的帧进行传输。AOS传输的业务类型呈现多样化，包括工程遥测数据、生理遥测数据、工程遥控数据、科学观测数据、科学实验数据、延时回放数据、音频数据、视频数据等。目前的AOS虚拟信道调度算法主要包括经典调度算法、动态优先级调度算法和群智能调度算法等。经典调度算法只是考虑单一参数来决定虚拟信道的调度顺序[5]，当传输不同服务需求的数据时，因考虑不全面会导致时延及帧剩余量等方面的问题。动态优先级调度算法[6–8]考虑传输紧迫度基数和传输紧迫度加权系数两个因素，并没有具体考虑到各虚拟信道的帧剩余量和时延，有一定的片面性。本文将虚拟信道的帧剩余量和时延两因素考虑在算法中，优化了数据的时效性和系统缓存性能。典型的群智能算法包括遗传算法[9]、蚁群算法[10]、粒子群算法[11–13]等。群智能算法在各种调度问题上广泛应用，其中粒子群算法因简单、易实现、收敛速度快等优点在调度问题上得到了较多的应用。

综上，本文首先将AOS多种类型的业务分为异步数据和同步数据。异步数据使用异步虚拟信道调度，基于粒子群算法的框架，结合遗传算法的交叉与变异算子，提出了基于遗传-粒子群排序的异步虚拟信道调度算法。同步数据使用同步虚拟信道调度，在轮询调度算法的基础上，引入动态加权因子，设计了基于动态加权轮询的同步虚拟信道调度算法。异步与同步虚拟信道的混合调度算法能够减小平均调度时延和帧剩余量，提高处理效率。

2 AOS虚拟信道混合调度模型

2.1 虚拟信道调度方式

航天器数据类型多样化，数据量大小不一，传输实时性要求也各不相同。在AOS传输的业务中，工程遥测、生理遥测、工程遥控、科学观测、科学实验和延时回放数据的突发性强，需优先处理，属于异步数据，在异步虚拟信道中传输；音频数据和视频数据的等时性高，属于同步数据，在同步虚拟信道中传输；此外，本文增加一条VIP虚拟信道，专门负责传输某些重要性和紧迫性极强的紧急数据，称为VIP数据。

为高效共享同一条物理信道，AOS将这些数据以时分复用的方式在不同的虚拟信道中传输。由于每种数据业务的传输要求不同，本文为每种数据业务分别分配一条虚拟信道，每条虚拟信道分配一个优先级。

虚拟信道调度方式有全同步、全异步和同步/异步混合调度。全同步调度方式中，每个虚拟信道的调度顺序是固定的，仅适用于同步数据的传输，不能灵活处理突发的异步数据。全异步调度方式可根据每个虚拟信道的优先级灵活地传输，但对于那些优先级较低的同步数据，有可能产生较长的排队延时。同步/异步混合调度方式是将虚拟信道划分为同步虚拟信道和异步虚拟信道两部分，分别传输同步数据和异步数据，可同时解决对异步数据的灵活处理和同步数据的等时传输问题，适用于传输要求不同的多类型数据的传输，相比前两种调度方式，系统效率更高，虽增加了调度的复杂度，但能较好地避免前两种方法的缺陷。

图1 虚拟信道调度系统结构

2.2 虚拟信道混合调度过程

本文将一个调度周期分为异步时隙和同步时隙，且两类时隙轮流出现。异步时隙时只调度异步虚拟信道，同步时隙时只调度同步虚拟信道。若完成一轮异步或同步调度后出现VIP数据，则其他虚拟信道停止传输，允许VIP数据立即占用当前时隙。没有数据等待传送时，传输填充帧。

虚拟信道混合调度过程中有调度同步虚拟信道、调度异步虚拟信道、传送VIP虚拟信道和传送填充帧4种状态。虚拟信道混合调度的状态图如图2所示。其中，X代表下一时隙为异步时隙，Y代表下一时隙为同步时隙，V代表有VIP数据，NV代表无VIP数据，A代表有异步数据，NA代表无异步数据，S代表有同步数据，NS代表无同步数据。

图2 虚拟信道混合调度状态图

单一的粒子群算法和遗传算法在多目标调度问题中容易陷入局部最优解，将两种算法结合可以有效解决此问题。因此，对异步虚拟信道，本文采用基于遗传-粒子群排序的调度算法，群体内的粒子根据遗传算法进化算子进行自身位置更新，从而找到最优的异步虚拟信道调度顺序。动态加权轮询调度算法根据虚拟信道的数据量制定动态加权系数，轮流传输，适用于传输同步数据。因此对同步虚拟信道，本文采用动态加权轮询的调度算法，即调度时间内，各同步虚拟信道按照加权因子和分配的时隙数，轮流占用物理信道。

3 基于遗传-粒子群排序的异步虚拟信道调度算法

3.1 遗传-粒子群适应度函数模型

AOS虚拟信道调度问题为一种组合优化问题，即在有限个可行调度顺序集合中找出最优调度顺序，通过约束得出影响异步虚拟信道调度顺序的适应度函数。该调度问题中主要有以下约束：

(1) 业务优先级约束。随着AOS传输的数据业务种类不断增多，不同业务的实时性和吞吐率要求不同。在AOS虚拟信道复用中，表现为业务优先级的不同。高优先级业务的实时性和吞吐率要求高，即要求延时小、帧剩余量低。相反低优先级业务对时延和帧剩余量的要求低。因此，业务优先级约束对不同虚拟信道的调度时延、帧剩余量提出了不同的要求，AOS虚拟信道调度系统应考虑不同业务的优先级约束。

(2) 调度时延紧迫度约束。调度时延紧迫度约束取决于当前虚拟信道的实际调度时延和最大调度时延。其中最大调度时延与业务的时效性要求和优先级有关。基于业务时效性要求，每种业务的数据要在其最大调度时延内得到传输，使用户在该时间内得到最有价值的信息，超过最大调度时延的信息将不再具有价值。此外，为保证重要信息的及时传达，应尽快传输高优先级虚拟信道的数据，因此最大调度时延的设置应取决于虚拟信道的优先级。

(4) 适应度函数。综合考虑AOS虚拟信道调度问题的3种约束，建立的混合粒子群适应度函数为

但从研究现状来看，国内学术界对海外中国政治研究的回应，无论是与海外新汉学研究成果的丰富相比较，还是与中国政治实践的波澜壮阔相比较，都显得过于单薄。就研究主体而言，尽管近年来介入海外中国研究的作者与机构开始增多，但他们的研究基本上处于一种分散化的状态，合作研究甚少，更没有建立起跨区域、跨学科的协同研究机制与平台。与之相对应，相关研究得不到有力的平台支撑，目前还没有普惠性的供专门跟踪海外中国研究成果的信息平台，已有的数据库服务的对象面相对较窄；除《国外社会科学》《国外理论动态》外，相关研究的成果发表渠道更是稀缺。

3.2 遗传-粒子群调度算法设计

(c) 选择算子。为提高收敛速度，并避免陷入局部极值，本文采用父子竞争与随机产生竞争相结合的选择机制。首先，采用父子竞争机制，分别计算粒子原本位置向量x和经过交叉变异后的位置向量x′′的适应度函数值，选择其中适应度函数值小的一个，其位置向量记为x′′′，父子竞争可以保护优良的位置向量，提高收敛速度。

其次，为了增加粒子多样性，避免陷入局部极值，采用随机产生竞争机制。随机产生一个位置向量x′′′′，比较x′′′与x′′′′的适应度函数值，选择其中适应度函数值小的一个，作为粒子位置更新后的最终位置向量x′′′′′，随机产生竞争机制可使算法跳出局部极值，扩大搜索范围。

3.3 基于遗传-粒子群排序的异步虚拟信道调度流程

粒子群随机初始化后，首先根据式(7)计算每个粒子适应度函数值f(i)，记为粒子个体最优值，粒子群最优值g取最小的f(i)值。然后使用遗传-粒子群进化算子更新粒子位置，根据新位置向量计算粒子适应度函数值，并与初始粒子个体最优值比较，将较小值作为新的粒子个体最优值；再将新的粒子个体最优值与全局极值比较，将较小值作为新的全局极值。按上述过程，N个粒子经过D次位置更新后得出粒子群最优值对应的位置向量，即群最优位置gBest， gBest就是当前最优调度顺序。遗传-粒子群排序过程如表1所示。

表1 算法1：遗传-粒子群排序过程

图3 交叉过程示意图

图4 变异过程示意图

确定当前时隙是异步时隙时，首先判断异步虚拟信道中是否有数据(帧剩余量≥1)。若有数据，根据式(7)计算适应度函数值，根据算法1求出当前最优调度顺序，并按照此顺序依次传输有数据的异步虚拟信道。若异步虚拟信道中没有数据，则传输填充数据。异步虚拟信道调度过程如表2所示。

表2 算法2：异步虚拟信道调度过程

4 基于动态加权轮询的同步虚拟信道调度算法

在同步调度周期内，由于每个同步虚拟信道的包到达率不同，为提高同步虚拟信道的传输效率，本文在周期轮询调度算法的基础上，引入动态加权因子，设计了基于动态加权周期轮询的同步虚拟信道调度算法，优化系统的调度性能。算法首先对各同步虚拟信道分配加权因子，加权因子与相应同步虚拟信道的包到达率成正比。在一个同步调度周期内，各同步虚拟信道占用的时隙数正比于其加权因子。设同步虚拟信道数量为n，第i条同步虚拟信道的包到达率为Qi(i＝1,2,···,n)，则第i条同步虚拟信道的加权因子Ai为

设一个同步调度周期内同步虚拟信道的总时隙数为Ts，则第i条同步虚拟信道可分配到的时隙数Fi为

确定前时隙为同步时隙时，按照以上过程计算每条同步虚拟信道加权因子Ai的值和可分配到的时隙数Fi，加权因子Ai由大到小的排列顺序即为同步虚拟信道的调度顺序，以相应的时隙数为间隔依次轮流调度，并计算出各同步虚拟信道的平均调度时延和帧剩余量。在下一个同步调度周期内，同步虚拟信道的包到达率发生变化，所以加权因子和可分配到的时隙数也随其动态变化。

同步虚拟信道采用动态加权轮询调度算法，既能满足同步虚拟信道的延时要求，又能提高同步类型数据在传输过程中的公平性，减少数据的剩余量，提高处理效率。

5 仿真与分析

按图1所示的系统模型进行仿真，并与轮询调度算法、动态优先级调度算法、遗传调度算法进行对比。

5.1 参数设置

仿真参数设置如下：

(1) 仿真时间T＝0.1 s；

(2) 处理速度为1×105～1.7×105帧/s；

(3) 虚拟信道总数为9个。其中，VC1～VC6为异步虚拟信道，VC7～VC8为同步虚拟信道，VC9为VIP虚拟信道。同步虚拟信道和异步虚拟信道的包到达服从泊松过程。VIP虚拟信道的帧到达率λ(t)服从正弦分布，表达式为

其中，λmax＝5×103帧/s为最大帧到达率，TVIP＝0.25T为帧到达率变化周期。具体参数设置如表3所示。

表3 虚拟信道参数

(4) 粒子群初始化：粒子个数N＝10，空间维度n＝6，位置更新次数D＝30。

5.2 平均调度时延仿真

对比图5可以看出，除轮询调度算法VC2在处理速度小于1.2×105帧/s时存在平均调度时延外，VC1～VC6以及VC9的平均调度时延基本为0，4种算法的主要区别在于VC7和VC8的平均调度时延。由于VC8的平均帧到达率较高，在动态优先级调度算法中，其平均调度时延较大，此外，动态优先级调度算法中VC7的平均调度时延大于0。在遗传调度算法中，VC8的平均调度时延高于轮询调度算法和动态优先级调度算法，较动态优先级调度算法多7.41%，较轮询调度算法多31.84%; VC7的平均调度时延略低于动态优先级调度算法，约为动态优先级调度算法的35.09%。在本文算法中，VC8的平均调度时延均小于动态优先级调度算法和遗传调度算法，约为动态优先级调度算法的91.55%，约为遗传调度算法的85.24%；VC7的平均调度时延几乎为0。可见，本文的混合调度算法在调度时延性能上有明显的提升。

图5 平均调度时延

5.3 帧剩余量仿真

对比图6可以看出，除轮询调度算法VC2在处理速度小于1.2×105帧/s时存在帧剩余量外，VC1～VC6以及VC9的帧剩余量基本为0，4种算法的区别主要在于VC7和VC8的帧剩余量。由于VC8的平均帧到达率较高，在轮询调度算法中帧剩余量最大。VC8的帧剩余量在动态优先级调度算法中也较大，此外，VC7也有一定的帧剩余量。在遗传调度算法中，当处理速度小于1.65×105帧/s时，VC8的帧剩余量少于动态优先级调度算法，VC7的帧剩余量几乎为0；处理速度大于1.65×105帧/s时，各虚拟信道的帧剩余量为0。在本文算法中，当处理速度小于1.34×105帧/s时，VC8的帧剩余量均明显少于其他3种调度算法，VC7的帧剩余量几乎为0；处理速度大于1.34×105帧/s时，各虚拟信道的帧剩余量为0。可见，本文的混合调度算法能有效降低虚拟信道的帧剩余量，从而可提高数据帧的实时传输性能，并降低丢帧率。

图6 虚拟信道帧剩余量

5.4 算法满意度分析

为了衡量算法的总体调度性能，本文参考文献[14,15]设计了算法满意度，仿真部分主要对比了轮询调度算法、动态优先级调度算法、遗传调度算法、遗传-粒子群排序调度算法中帧剩余量和平均调度时延的差异，所以满意度公式中除了优先级外还考虑了帧剩余量和平均调度时延。算法满意度B用式(12)表示

其中，Pi为第i条虚拟信道的优先级，RESi为第i条虚拟信道的帧剩余量，tavg_delay_i为第i条虚拟信道的平均调度时延。设各算法满意度的最大值为Bmax，则算法的归一化满意度可表示为

图7为4种算法的归一化满意度随处理速度变化的曲线。可以看出，本文算法的满意度更好。

图7 算法的归一化满意度

综上，通过对算法的仿真与分析得出，本文提出的虚拟信道混合调度算法，在满足各虚拟信道数据源特性的基础上，有更小的平均调度时延和更少的帧剩余量。不能实时处理时，在一定程度上牺牲帧到达率较大的同步数据，提高整体的调度性能，算法整体满意度较高。同时，通过同步异步混合调度的方式，满足了不同类型异步数据的传输要求，保证了VIP数据的实时传输，同时兼顾了同步数据的等时性。

卫星系统与AOS高级在轨系统相似，都需要在有限资源的情况下合理地分配业务量大、种类多的任务，因此卫星系统调度问题也属于组合优化问题。本文将遗传算法和粒子群算法结合，解决了传统算法收敛速度慢的问题，且遗传-粒子群算法简单易实现有较强的搜索和寻优能力，能够合理且快速地调度资源，实现卫星资源使用效能最大化，所以本文算法的计算复杂度同样适用于卫星系统。

6 结束语

本文基于AOS虚拟信道复用技术，针对空间数据业务类型的多样化，建立了AOS虚拟信道混合调度模型，提出基于遗传-粒子群排序的异步虚拟信道调度算法、基于动态加权轮询的同步虚拟信道调度算法。仿真表明，本文所提虚拟信道混合调度算法兼顾了异步数据的优先性、同步数据的等时性和VIP数据的紧迫性，在平均调度时延、帧剩余量和算法满意度上，均有更好的效果，更适合空间多类型业务的有效传输。