基于动态窗口的虚拟信道通用调度算法

2019-06-27

计算机测量与控制 2019年6期

(中国卫星海上测控部，江苏江阴 214431)

0 引言

虚拟信道调度算法在国内外被广泛研究。文献[1]将数据帧生成模块与虚拟信道复用模块作为一个整体考虑，提出了自适应帧生成算法与虚拟信道调度算法相结合的多路复用方法，在任一时刻均计算信道传输紧迫度，其异步信道采用抢占式调度策略；文献[2]提出了一种基于虚拟信道/帧分离估算紧迫度的动态调度算法,将信源数据分成同步数据和异步数据，在异步数据的调度中，构造虚拟信道传输紧迫度函数分配传输时隙，其同步信道和异步信道的时隙不可互转；文献[3]设计了一种边界可移动的VIP/同步/异步混合复用方式，其同步信道采用独占式调度策略，异步信道采用抢占式调度策略，在同步信道时隙数据无效时，将调度异步信道。

目前针对虚拟信道调度一个或几个特性而设计的调度算法[4-7]，局限于某些应用场合，或者着眼于提高整体调度性能[8-10]，无法得到普遍应用；信道时隙计算、信道优先级调整内嵌到算法中，限制了调度算法在更大范围内通用。本文着眼于设计广泛通用的虚拟信道调度算法，把信道时隙计算和信道优先级调整从算法中剥离，信道时隙和信道优先级以参数形式传入算法中；对全同步调度算法、全异步调度算法和同步/异步混合调度算法进行了研究，设计了独占式轮转和顺序式轮转两种全同步调度算法，抢占式优先和非抢占式优先两种全异步调度算法，以及独占式混合和顺序式混合两种同步/异步混合调度算法，在此基础上考虑应急信道数据发送要求，实现了基于动态窗口的虚拟信道通用调度算法。

1 全同步调度算法

设虚拟信道VS1～VSn为同步信道，占用时隙分别为Ts1～Tsn，遥测帧周期为T，显然Tsi应当为T的整数倍，同步信道总时隙Ts为Ts1～Tsn之和。采用时间轮转调度算法实现虚拟信道同步调度，时间片长度为T。按照调度策略，分为独占式轮转调度算法和顺序式轮转调度算法，算法描述如下：

1)根据虚拟信道占用时隙和遥测帧周期，计算信道轮转次数Ni(1≤i≤n)：Ni=Tsi/T。

2)系统维护一张虚拟信道调度表，如表1所示，“序号”为调度顺序，“发送计数”Ci为本轮周期内剩余调度次数，初始化为Ni，Ri为信道数据是否有效。

表1 时间轮转调度算法中的虚拟信道调度表

3)独占式轮转调度：当前信道调度完毕后，再调度下一个信道。即当遥测帧中断到来时，系统按照如下步骤搜索虚拟信道调度表：

①系统从前往后搜索。如果Ri为真且Ci大于0，则调度信道i，对应的“发送计数”Ci减1；接下来Ni-1周期内，均调度信道i，直至Ci计数值为0时调度信道i+1；如果Ci为0，该信道不参与调度；

②当最后一个信道n调度完毕后，所有信道Ci恢复初始值Ni，此时可以重新获取信道时隙，然后重复步骤①，直至系统退出。

4)顺序式轮转调度算法与独占式轮转调度算法略有不同，当前信道不是一次性调度完毕，而是仅调度1次，下次调度下一个信道。即当遥测帧中断到来时，系统按照如下步骤搜索虚拟信道调度表：

①系统依次从前往后搜索。如果Ci大于0，则调度信道i，Ci减1，下一次调度信道i+1；如果Ci为0，则该信道不参与调度，直接调度信道i+1；

②当最后一个信道n被调度后，返回调度表起始处，重复步骤①，直至所有信道均被调度完毕，即Ci均为0，则所有虚拟信道的Ci恢复为初始值Ni，此时可以重新获取信道时隙，重复步骤①，直至系统退出。

设计了获取同步信道调度函数int GetSyncVC(int *Ci, int *Ri,int n,int &nNextVC,BOOL bSeq)实现该算法，函数流程如图1所示。其中n为同步信道个数，nNextVC为下一次可能被调度的虚拟信道(初始化为0)，bSeq为TRUE表示顺序式轮转调度，bSeq为FALSE表示独占式轮转调度，返回值表示当前被调度的虚拟信道(-1表示本轮信道调度完毕)。

①在调度某信道时，如果发现该信道数据无效，则自动调度下一信道，以避免发送填充数据;

②在顺序式调度模式下，当搜索到最后一个信道且未发现有需要调度数据时，需返回调度表头部重新进行搜索，以调度其他信道尚未调度完毕的数据;

③在顺序式调度模式下，下一次调度下一个信道；而在独占式调度模式下，当本信道调度完毕后，下一次才调度下一个信道。

图1 同步信道调度函数流程图

同步信道占用时隙随卫星运行状态变化，全同步调度算法提供了时隙调整接口，GetSyncVC()返回-1时重新计算初始值Ni，Ci恢复为初始值Ni。

假设4个同步信道VS1、VS2、VS3、VS4，占用时隙为8 s、4 s、2 s、1 s，帧周期为1 s，轮转次数为8、4、2、1。总时隙为15 s，一个调度周期需调度15次。信道数据均有效，顺序式同步调度和独占式同步调度的虚拟信道如表2第2列和第5列所示；第3列和第6列表示VS2数据无效时调度顺序，加粗部分为第二轮调度；第4列和第7列表示VS2数据在第10次有效时的调度顺序。当某信道数据无效时，该算法可调度后续数据有效的信道；当信道数据恢复时，可确保该信道数据得到调度。而顺序式同步调度相比独占式同步调度，能够提高信道调度及时性。

2 全异步调度算法

设虚拟信道VA1～VAn为异步信道，占用时隙分别为Ta1～Tan，优先级依次为P1～Pn，按照优先级排序，即P1≥P2≥……≥Pn。遥测帧周期为T，显然Tai应当为T的整数倍，异步信道总时隙Ta为Ta1～Tan之和，该时间称为异步信道调度周期。

按照调度策略不同，分为非抢占式优先级调度算法和抢占式优先级调度算法，算法描述如下：

1)根据虚拟信道占用时隙和遥测帧周期，计算信道发送次数Si(1≤i≤n)：Si=Tai/T。

2)系统维护一张信道调度表，按照优先级从高到低排列，如表2所示，“发送计数”Ci为本轮周期内剩余调度次

表2 顺序式同步调度和独占式同步调度顺序

数，初始化为Si，Ri为信道数据是否有效，初始化时信道调度表如表3所示。

表3 优先级调度算法中的虚拟信道调度表

3)非抢占式优先级调度算法中，系统按照如下步骤搜索虚拟信道调度表：

①当遥测帧周期到来时，如果VA1信道Ri为真，在接下来S1个周期内，均发送VA1数据，发送完毕后，Ri设置为假，令i=2；如果VA1信道Ri为假，令i=2；

②当遥测帧周期到来时，如果VAi信道Ri为真，在接下来的Si个周期内，均发送VAi的数据，发送完毕后，Ri设置为假。如果VCi信道Ri为假，令i++，如果i≤n，重复步骤②，否则转③；

③此时最后一个信道n调度完毕，所有信道Ci恢复初始值Si，在此可以调整信道优先级，然后重复步骤①，直至系统退出。

4)抢占式优先级调度算法与非抢占式优先级调度算法略有不同，即低优先级信道占用时间片时，高优先级信道可抢占其时间片，概述如下：

①与非抢占式优先级调度算法步骤①相同；

②当遥测帧周期到来时，如果VAi信道Ri为真，发送一帧VAi信道数据，并令Ci减1(如果Ci等于0，设置VAi的Ri为否)，并转步骤①；如果VAi信道Ri为假，令i++，如果i≤n，重复步骤②，否则转③；

③与非抢占式优先级调度算法步骤③相同。

设计了获取异步信道调度函数int GetAsynVC(int *Ci,int *Ri,int n,int &nNextVC,BOOL bPreemp)实现该算法，流程图如图2所示。bPreemp为TRUE表示抢占式优先级调度，bPreemp为FALSE表示非抢占式优先级调度，返回值表示当前被调度的虚拟信道(-1表示本轮信道调度完毕)。

①在抢占式优先级调度模式下，高优先级信道优先调度，即使当前信道数据未调度完毕，也从第一个信道开始调度；②当信道调度完毕后，数据准备就绪标志置为假。此时如果是非抢占式优先级调度，还需返回调度表头重新进行调度。图2 异步信道调度函数流程图

异步信道占用时隙及其优先级可随卫星运行状态变化，全异步调度算法提供了信道时隙调整接口以及优先级调整接口，在一轮调度完成，即函数GetAsynVC()返回-1时调整，此时按照优先级重新排序生成VA1～VAn，重新计算初始值Si，Ci计数恢复为初始值Si，此后系统将按新的时隙和优先级进行调度。此外，系统在每次调用函数GetAsynVC()前，均可调整优先级。

假设有4个异步信道VA1、VA2、VA3、VA4，占用时隙分别为8 s、4 s、2 s、1 s，帧周期为1 s，发送次数分别为8、4、2、1，优先级设置为4、3、2、1，各信道数据均准备完毕。抢占式优先级调度和非抢占式优先级调度过程中，搜索的信道如表4所示。

表4 抢占式和非抢占式优先级调度中搜索的信道

表4显示抢占式和非抢占式最终调度信道相同，但实际搜索信道不同。表5第2列和第3列显示了VA1信道在第5次调度时数据无效、在第7次调度时恢复、在第9次调度时数据无效、在第11次调度时恢复的调度顺序，调度开始时所有数据均有效；表5第3列和第4列显示了所有数据均有效时，在第5次调度时，VA3优先级提高为5时的调度顺序，抢占式调度第5次开始调度VA3，而非抢占式调度第9次才开始调度VA3。

表5 数据无效对信道调度的影响

3 同步/异步混合调度算法

设虚拟信道VS1～VSm为同步信道(统称为VS，即同步窗口)，VA1～VAn为异步信道(统称为VA，即异步窗口)，同步信道占用时隙为Ts，异步信道占用时隙为Ta。设计了固定比率同步/异步混合调度算法，按照调度策略分为独占式混合算法和顺序式混合算法。算法描述如下：

1)根据窗口占用时隙和遥测帧周期，计算窗口打开次数Wi(1≤i≤2)：W1=Ts/T，W2=Ta/T。

2)系统维护一张窗口调度表，如表6所示，“序号”表示调度顺序，“发送计数”Ci表示本轮周期内该窗口还剩余的调度次数，且Ci被初始化为Wi，“数据有效标志”Vi表示该窗口数据是否有效，V1初始化为同步信道Ri值之和，V2初始化为异步信道Ri值之和，初始化时窗口调度表如表6所示。

表6 同步/异步混合窗口调度表

3)独占式混合算法中，首先调度VS窗口，即采用全同步调度算法调度VS1～VSm，调度W1个周期后，在接下来W2个周期内，调度VA窗口，即采用全异步调度算法调度VA1～VAm。共调度(W1+W2)个周期后，一次混合调度完毕后，重复步骤3)，直至系统退出。

4)顺序式混合算法中，依次调度VS窗口、VA窗口、VS窗口、VA窗口。即采用全同步调度算法调度VS1～VSm，调度1个周期以后，在接下来的1个周期内，采用全异步调度算法调度VA1～VAm，然后调度VS1～VSm、VA1～VAm。共调度(W1+W2)个周期以后，一次混合调度完毕，重复步骤4)，直至系统退出。

混合信道调度算法流程图如图3所示。其中窗口调度采用GetSyncVC函数实现，即设Ci[]={W1,W2}，n=2，nNextMixVc=0，bMix表示顺序式混合(TRUE)还是独占式混合(FALSE)：

int nW= GetSyncVC(Ci,2, nNextMixVc, bMix);

nW为0，表示调度同步信道；nW为1，表示调度异步信道；nW为-1，表示本轮调度结束，开启新一轮调度，此时重新计算初始值S和A，Ci计数恢复为初始值，此后系统按新的时隙进行调度。

图3 混合信道调度算法流程图

注：①拟调度窗口发送计数有效而数据无效时，GetSyncVC函数将跳过该窗口调度下一个窗口，之前需计算窗口数据有效标志；

②在一轮混合调度完毕后，调整窗口打开次数；

③在一轮异步信道调度完毕后，调整信道发送次数及优先级；

④在一轮同步信道调度完毕后，调整信道轮转次数。

同步/异步混合调度算法采用两级调度机制，第一级在同步窗口和异步窗口之间调度，第二级采用全同步或全异步调度。显然，混合调度算法根据调度方式可分为8种调度模式，如表7所示。

表7 混合调度算法的多种调度模式

4 基于动态窗口的通用调度算法

该算法建立在全同步调度算法、全异步调度算法以及同步/异步混合调度算法之上，既能满足同步数据固定时隙要求，又能适应异步数据动态调整要求，还能满足应急数据及时发送要求，并减少信道资源浪费。算法描述如下：

1)设计了如表8所示的混合调度表，相比同步/异步混合调度表，增加了应急窗口VE，初始化时，同步窗口、异步窗口比率为W1:W2，应急窗口发送次数默认为0，当需要发送应急信道数据时才计算其值。

表8 基于动态窗口的混合调度表

2)设计了动态窗口调度函数int GetDynamicW(intCi[3],int &nNextVC,BOOL bSeq)实现窗口调度，算法流程如图4所示。其中：Ci[]为窗口剩余调度次数(初始化为Wi)；nNextVC为下次可能被调度窗口(初始化为0)；bSeq为TRUE表示顺序式轮转调度，bSeq为FALSE表示独占式轮转调度；返回值-1表示本次调度轮空，0表示应急窗口有效，1表示同步窗口有效，2表示异步窗口有效。

图4 动态窗口调度函数流程图

3)在动态窗口调度函数GetDynamicW()、同步信道调度函数GetSyncVC()、异步信道调度函数GetAsynVC()基础上，实现基于动态窗口的混合调度算法，流程图与图3类似，不同之处在于窗口调度采用GetDynamicW()函数，其返回值为0时调度应急窗口，1时调度同步窗口、2时调度异步窗口。

基于动态窗口的通用调度算法中，当W0=0时，即实现了第3节的同步/异步混合调度算法；当W0=W1=0时，即实现了第2节的全异步调度算法；当W0=W2=0时，即实现了第1节的全同步调度算法。

5 实验结果与分析

采用Visual C++6.0实现了基于动态窗口的通用调度算法，程序界面图5所示。用户通过设置窗口调度方式、同步信道调度方式、异步调度方式定制信道调度方式，通过设置窗口调度比率控制同步调度、异步调度以及应急调度的所占用时隙。

第一个列表框显示程序中使用的同步信道和异步信道中各虚拟信道的初始次数和优先级，其中同步信道共4个，即VS1～VS4，初始次数分别为8、4、2、1，异步信道共4个，即VA1～VA4，初始次数分别为8、4、2、1，优先级分别为4、3、2、1。

第二个列表框显示全同步调度顺序式和独占式的调度结果，全同步调度通过控制窗口调度比率实现，即同步窗口调度次数为15，异步窗口调度次数为0，应急窗口调度次数为0；第三个列表框显示全异步调度抢占式和非抢占式的调度结果，窗口调度比率设置为同步窗口调度次数为0，异步窗口调度次数为15，应急窗口调度次数为0，列表框最后一列中，显示了异步信道调度时信道搜索情况；第四个列表框显示混合式调度顺序式的调度结果，窗口调度比率设置为同步窗口调度次数为15，异步窗口调度次数为15，应急窗口调度次数为0。

第五个列表框显示动态调度结果，初始时窗口调度比率设置为同步窗口调度次数为15，异步窗口调度次数为15，应急窗口调度次数为0；为模拟应急窗口调度，首先设置应急窗口调度次数为正值，然后点击“应急调度”按钮，模拟程序运行过程中实时接收应急数据的情况。列表框中显示，同步调度和异步调度交叉进行，因为窗口调度方式选择了“顺序式”；同步信道中VS1～VS4为独占运行，异步信道中VA1～VA4为非抢占式运行；当用户点击应急调度后，列表框中显示应急调度被及时插入到调度队列中，调度2次后又恢复正常调度。

上述信道占用时隙、信道优先级、信道调度模式等信息可通过参数传入调度程序，这些参数既可由嵌入卫星的调度程序实时计算生成，也可由地面运控软件发送遥控数据注入的方式生成；前一种方式与时隙计算、优先级计算内嵌到算法中的执行效率一致，后一种方式虽然降低了系统执行效率，但增加了地面人工控制接口，有利于应急情况处置。实际应用中，两种方式可结合使用。