(中國衛(wèi)星海上測控部，江蘇 江陰 214431)

0 引言

虛擬信道調度算法在國內外被廣泛研究。文獻[1]將數據幀生成模塊與虛擬信道復用模塊作為一個整體考慮，提出了自適應幀生成算法與虛擬信道調度算法相結合的多路復用方法，在任一時刻均計算信道傳輸緊迫度，其異步信道采用搶占式調度策略；文獻[2]提出了一種基于虛擬信道/幀分離估算緊迫度的動態(tài)調度算法,將信源數據分成同步數據和異步數據，在異步數據的調度中，構造虛擬信道傳輸緊迫度函數分配傳輸時隙，其同步信道和異步信道的時隙不可互轉；文獻[3]設計了一種邊界可移動的VIP/同步/異步混合復用方式，其同步信道采用獨占式調度策略，異步信道采用搶占式調度策略，在同步信道時隙數據無效時，將調度異步信道。

目前針對虛擬信道調度一個或幾個特性而設計的調度算法[4-7]，局限于某些應用場合，或者著眼于提高整體調度性能[8-10]，無法得到普遍應用；信道時隙計算、信道優(yōu)先級調整內嵌到算法中，限制了調度算法在更大范圍內通用。本文著眼于設計廣泛通用的虛擬信道調度算法，把信道時隙計算和信道優(yōu)先級調整從算法中剝離，信道時隙和信道優(yōu)先級以參數形式傳入算法中；對全同步調度算法、全異步調度算法和同步/異步混合調度算法進行了研究，設計了獨占式輪轉和順序式輪轉兩種全同步調度算法，搶占式優(yōu)先和非搶占式優(yōu)先兩種全異步調度算法，以及獨占式混合和順序式混合兩種同步/異步混合調度算法，在此基礎上考慮應急信道數據發(fā)送要求，實現(xiàn)了基于動態(tài)窗口的虛擬信道通用調度算法。

1 全同步調度算法

設虛擬信道VS1～VSn為同步信道，占用時隙分別為Ts1～Tsn，遙測幀周期為T，顯然Tsi應當為T的整數倍，同步信道總時隙Ts為Ts1～Tsn之和。采用時間輪轉調度算法實現(xiàn)虛擬信道同步調度，時間片長度為T。按照調度策略，分為獨占式輪轉調度算法和順序式輪轉調度算法，算法描述如下：

1)根據虛擬信道占用時隙和遙測幀周期，計算信道輪轉次數Ni(1≤i≤n)：Ni=Tsi/T。

2)系統(tǒng)維護一張?zhí)摂M信道調度表，如表1所示，“序號”為調度順序，“發(fā)送計數”Ci為本輪周期內剩余調度次數，初始化為Ni，Ri為信道數據是否有效。

表1 時間輪轉調度算法中的虛擬信道調度表

3)獨占式輪轉調度：當前信道調度完畢后，再調度下一個信道。即當遙測幀中斷到來時，系統(tǒng)按照如下步驟搜索虛擬信道調度表：

①系統(tǒng)從前往后搜索。如果Ri為真且Ci大于0，則調度信道i，對應的“發(fā)送計數”Ci減1；接下來Ni-1周期內，均調度信道i，直至Ci計數值為0時調度信道i+1；如果Ci為0，該信道不參與調度；

②當最后一個信道n調度完畢后，所有信道Ci恢復初始值Ni，此時可以重新獲取信道時隙，然后重復步驟①，直至系統(tǒng)退出。

4)順序式輪轉調度算法與獨占式輪轉調度算法略有不同，當前信道不是一次性調度完畢，而是僅調度1次，下次調度下一個信道。即當遙測幀中斷到來時，系統(tǒng)按照如下步驟搜索虛擬信道調度表：

①系統(tǒng)依次從前往后搜索。如果Ci大于0，則調度信道i，Ci減1，下一次調度信道i+1；如果Ci為0，則該信道不參與調度，直接調度信道i+1；

②當最后一個信道n被調度后，返回調度表起始處，重復步驟①，直至所有信道均被調度完畢，即Ci均為0，則所有虛擬信道的Ci恢復為初始值Ni，此時可以重新獲取信道時隙，重復步驟①，直至系統(tǒng)退出。

設計了獲取同步信道調度函數int GetSyncVC(int *Ci, int *Ri,int n,int &nNextVC,BOOL bSeq)實現(xiàn)該算法，函數流程如圖1所示。其中n為同步信道個數，nNextVC為下一次可能被調度的虛擬信道(初始化為0)，bSeq為TRUE表示順序式輪轉調度，bSeq為FALSE表示獨占式輪轉調度，返回值表示當前被調度的虛擬信道(-1表示本輪信道調度完畢)。

①在調度某信道時，如果發(fā)現(xiàn)該信道數據無效，則自動調度下一信道，以避免發(fā)送填充數據;

②在順序式調度模式下，當搜索到最后一個信道且未發(fā)現(xiàn)有需要調度數據時，需返回調度表頭部重新進行搜索，以調度其他信道尚未調度完畢的數據;

③在順序式調度模式下，下一次調度下一個信道；而在獨占式調度模式下，當本信道調度完畢后，下一次才調度下一個信道。

圖1 同步信道調度函數流程圖

同步信道占用時隙隨衛(wèi)星運行狀態(tài)變化，全同步調度算法提供了時隙調整接口，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次有效時的調度順序。當某信道數據無效時，該算法可調度后續(xù)數據有效的信道；當信道數據恢復時，可確保該信道數據得到調度。而順序式同步調度相比獨占式同步調度，能夠提高信道調度及時性。

2 全異步調度算法

設虛擬信道VA1～VAn為異步信道，占用時隙分別為Ta1～Tan，優(yōu)先級依次為P1～Pn，按照優(yōu)先級排序，即P1≥P2≥……≥Pn。遙測幀周期為T，顯然Tai應當為T的整數倍，異步信道總時隙Ta為Ta1～Tan之和，該時間稱為異步信道調度周期。

按照調度策略不同，分為非搶占式優(yōu)先級調度算法和搶占式優(yōu)先級調度算法，算法描述如下：

1)根據虛擬信道占用時隙和遙測幀周期，計算信道發(fā)送次數Si(1≤i≤n)：Si=Tai/T。

2)系統(tǒng)維護一張信道調度表，按照優(yōu)先級從高到低排列，如表2所示，“發(fā)送計數”Ci為本輪周期內剩余調度次

表2 順序式同步調度和獨占式同步調度順序

數，初始化為Si，Ri為信道數據是否有效，初始化時信道調度表如表3所示。

表3 優(yōu)先級調度算法中的虛擬信道調度表

3)非搶占式優(yōu)先級調度算法中，系統(tǒng)按照如下步驟搜索虛擬信道調度表：

①當遙測幀周期到來時，如果VA1信道Ri為真，在接下來S1個周期內，均發(fā)送VA1數據，發(fā)送完畢后，Ri設置為假，令i=2；如果VA1信道Ri為假，令i=2；

②當遙測幀周期到來時，如果VAi信道Ri為真，在接下來的Si個周期內，均發(fā)送VAi的數據，發(fā)送完畢后，Ri設置為假。如果VCi信道Ri為假，令i++，如果i≤n，重復步驟②，否則轉③；

③此時最后一個信道n調度完畢，所有信道Ci恢復初始值Si，在此可以調整信道優(yōu)先級，然后重復步驟①，直至系統(tǒng)退出。

4)搶占式優(yōu)先級調度算法與非搶占式優(yōu)先級調度算法略有不同，即低優(yōu)先級信道占用時間片時，高優(yōu)先級信道可搶占其時間片，概述如下：

①與非搶占式優(yōu)先級調度算法步驟①相同；

②當遙測幀周期到來時，如果VAi信道Ri為真，發(fā)送一幀VAi信道數據，并令Ci減1(如果Ci等于0，設置VAi的Ri為否)，并轉步驟①；如果VAi信道Ri為假，令i++，如果i≤n，重復步驟②，否則轉③；

③與非搶占式優(yōu)先級調度算法步驟③相同。

設計了獲取異步信道調度函數int GetAsynVC(int *Ci,int *Ri,int n,int &nNextVC,BOOL bPreemp)實現(xiàn)該算法，流程圖如圖2所示。bPreemp為TRUE表示搶占式優(yōu)先級調度，bPreemp為FALSE表示非搶占式優(yōu)先級調度，返回值表示當前被調度的虛擬信道(-1表示本輪信道調度完畢)。

①在搶占式優(yōu)先級調度模式下，高優(yōu)先級信道優(yōu)先調度，即使當前信道數據未調度完畢，也從第一個信道開始調度；②當信道調度完畢后，數據準備就緒標志置為假。此時如果是非搶占式優(yōu)先級調度，還需返回調度表頭重新進行調度。圖2 異步信道調度函數流程圖

異步信道占用時隙及其優(yōu)先級可隨衛(wèi)星運行狀態(tài)變化，全異步調度算法提供了信道時隙調整接口以及優(yōu)先級調整接口，在一輪調度完成，即函數GetAsynVC()返回-1時調整，此時按照優(yōu)先級重新排序生成VA1～VAn，重新計算初始值Si，Ci計數恢復為初始值Si，此后系統(tǒng)將按新的時隙和優(yōu)先級進行調度。此外，系統(tǒng)在每次調用函數GetAsynVC()前，均可調整優(yōu)先級。

假設有4個異步信道VA1、VA2、VA3、VA4，占用時隙分別為8 s、4 s、2 s、1 s，幀周期為1 s，發(fā)送次數分別為8、4、2、1，優(yōu)先級設置為4、3、2、1，各信道數據均準備完畢。搶占式優(yōu)先級調度和非搶占式優(yōu)先級調度過程中，搜索的信道如表4所示。

表4 搶占式和非搶占式優(yōu)先級調度中搜索的信道

表4顯示搶占式和非搶占式最終調度信道相同，但實際搜索信道不同。表5第2列和第3列顯示了VA1信道在第5次調度時數據無效、在第7次調度時恢復、在第9次調度時數據無效、在第11次調度時恢復的調度順序，調度開始時所有數據均有效；表5第3列和第4列顯示了所有數據均有效時，在第5次調度時，VA3優(yōu)先級提高為5時的調度順序，搶占式調度第5次開始調度VA3，而非搶占式調度第9次才開始調度VA3。

表5 數據無效對信道調度的影響

3 同步/異步混合調度算法

設虛擬信道VS1～VSm為同步信道(統(tǒng)稱為VS，即同步窗口)，VA1～VAn為異步信道(統(tǒng)稱為VA，即異步窗口)，同步信道占用時隙為Ts，異步信道占用時隙為Ta。設計了固定比率同步/異步混合調度算法，按照調度策略分為獨占式混合算法和順序式混合算法。算法描述如下：

1)根據窗口占用時隙和遙測幀周期，計算窗口打開次數Wi(1≤i≤2)：W1=Ts/T，W2=Ta/T。

2)系統(tǒng)維護一張窗口調度表，如表6所示，“序號”表示調度順序，“發(fā)送計數”Ci表示本輪周期內該窗口還剩余的調度次數，且Ci被初始化為Wi，“數據有效標志”Vi表示該窗口數據是否有效，V1初始化為同步信道Ri值之和，V2初始化為異步信道Ri值之和，初始化時窗口調度表如表6所示。

表6 同步/異步混合窗口調度表

3)獨占式混合算法中，首先調度VS窗口，即采用全同步調度算法調度VS1～VSm，調度W1個周期后，在接下來W2個周期內，調度VA窗口，即采用全異步調度算法調度VA1～VAm。共調度(W1+W2)個周期后，一次混合調度完畢后，重復步驟3)，直至系統(tǒng)退出。

4)順序式混合算法中，依次調度VS窗口、VA窗口、VS窗口、VA窗口。即采用全同步調度算法調度VS1～VSm，調度1個周期以后，在接下來的1個周期內，采用全異步調度算法調度VA1～VAm，然后調度VS1～VSm、VA1～VAm。共調度(W1+W2)個周期以后，一次混合調度完畢，重復步驟4)，直至系統(tǒng)退出。

混合信道調度算法流程圖如圖3所示。其中窗口調度采用GetSyncVC函數實現(xiàn)，即設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計數恢復為初始值，此后系統(tǒng)按新的時隙進行調度。

圖3 混合信道調度算法流程圖

注：①擬調度窗口發(fā)送計數有效而數據無效時，GetSyncVC函數將跳過該窗口調度下一個窗口，之前需計算窗口數據有效標志；

②在一輪混合調度完畢后，調整窗口打開次數；

③在一輪異步信道調度完畢后，調整信道發(fā)送次數及優(yōu)先級；

④在一輪同步信道調度完畢后，調整信道輪轉次數。

同步/異步混合調度算法采用兩級調度機制，第一級在同步窗口和異步窗口之間調度，第二級采用全同步或全異步調度。顯然，混合調度算法根據調度方式可分為8種調度模式，如表7所示。

表7 混合調度算法的多種調度模式

4 基于動態(tài)窗口的通用調度算法

該算法建立在全同步調度算法、全異步調度算法以及同步/異步混合調度算法之上，既能滿足同步數據固定時隙要求，又能適應異步數據動態(tài)調整要求，還能滿足應急數據及時發(fā)送要求，并減少信道資源浪費。算法描述如下：

1)設計了如表8所示的混合調度表，相比同步/異步混合調度表，增加了應急窗口VE，初始化時，同步窗口、異步窗口比率為W1:W2，應急窗口發(fā)送次數默認為0，當需要發(fā)送應急信道數據時才計算其值。

表8 基于動態(tài)窗口的混合調度表

2)設計了動態(tài)窗口調度函數int GetDynamicW(intCi[3],int &nNextVC,BOOL bSeq)實現(xiàn)窗口調度，算法流程如圖4所示。其中：Ci[]為窗口剩余調度次數(初始化為Wi)；nNextVC為下次可能被調度窗口(初始化為0)；bSeq為TRUE表示順序式輪轉調度，bSeq為FALSE表示獨占式輪轉調度；返回值-1表示本次調度輪空，0表示應急窗口有效，1表示同步窗口有效，2表示異步窗口有效。

圖4 動態(tài)窗口調度函數流程圖

3)在動態(tài)窗口調度函數GetDynamicW()、同步信道調度函數GetSyncVC()、異步信道調度函數GetAsynVC()基礎上，實現(xiàn)基于動態(tài)窗口的混合調度算法，流程圖與圖3類似，不同之處在于窗口調度采用GetDynamicW()函數，其返回值為0時調度應急窗口，1時調度同步窗口、2時調度異步窗口。

基于動態(tài)窗口的通用調度算法中，當W0=0時，即實現(xiàn)了第3節(jié)的同步/異步混合調度算法；當W0=W1=0時，即實現(xiàn)了第2節(jié)的全異步調度算法；當W0=W2=0時，即實現(xiàn)了第1節(jié)的全同步調度算法。

5 實驗結果與分析

采用Visual C++6.0實現(xiàn)了基于動態(tài)窗口的通用調度算法，程序界面圖5所示。用戶通過設置窗口調度方式、同步信道調度方式、異步調度方式定制信道調度方式，通過設置窗口調度比率控制同步調度、異步調度以及應急調度的所占用時隙。

第一個列表框顯示程序中使用的同步信道和異步信道中各虛擬信道的初始次數和優(yōu)先級，其中同步信道共4個，即VS1～VS4，初始次數分別為8、4、2、1，異步信道共4個，即VA1～VA4，初始次數分別為8、4、2、1，優(yōu)先級分別為4、3、2、1。

第二個列表框顯示全同步調度順序式和獨占式的調度結果，全同步調度通過控制窗口調度比率實現(xiàn)，即同步窗口調度次數為15，異步窗口調度次數為0，應急窗口調度次數為0；第三個列表框顯示全異步調度搶占式和非搶占式的調度結果，窗口調度比率設置為同步窗口調度次數為0，異步窗口調度次數為15，應急窗口調度次數為0，列表框最后一列中，顯示了異步信道調度時信道搜索情況；第四個列表框顯示混合式調度順序式的調度結果，窗口調度比率設置為同步窗口調度次數為15，異步窗口調度次數為15，應急窗口調度次數為0。

第五個列表框顯示動態(tài)調度結果，初始時窗口調度比率設置為同步窗口調度次數為15，異步窗口調度次數為15，應急窗口調度次數為0；為模擬應急窗口調度，首先設置應急窗口調度次數為正值，然后點擊“應急調度”按鈕，模擬程序運行過程中實時接收應急數據的情況。列表框中顯示，同步調度和異步調度交叉進行，因為窗口調度方式選擇了“順序式”；同步信道中VS1～VS4為獨占運行，異步信道中VA1～VA4為非搶占式運行；當用戶點擊應急調度后，列表框中顯示應急調度被及時插入到調度隊列中，調度2次后又恢復正常調度。

上述信道占用時隙、信道優(yōu)先級、信道調度模式等信息可通過參數傳入調度程序，這些參數既可由嵌入衛(wèi)星的調度程序實時計算生成，也可由地面運控軟件發(fā)送遙控數據注入的方式生成；前一種方式與時隙計算、優(yōu)先級計算內嵌到算法中的執(zhí)行效率一致，后一種方式雖然降低了系統(tǒng)執(zhí)行效率，但增加了地面人工控制接口，有利于應急情況處置。實際應用中，兩種方式可結合使用。

6 結論

在全同步調度算法、全異步調度算法、同步/異步混合調度算法基礎上，實現(xiàn)的基于動態(tài)窗口的虛擬信道通用調度算法具有如下幾個特點：

1)算法通用性強。通過參數配置，可實現(xiàn)全同步調度算法、全異步調度算法、同步/異步混合調度算法以及兼顧應急信道的混合調度算法，并具有8種可選的調度策略；

2)算法窗口利用率和信道利用率高。在同步調度和異步調度中，當擬調度信道發(fā)送計數有效而數據無效時，算法將跳過該信道調度下一個信道，實現(xiàn)了信道時隙自動接續(xù)；在同步/異步混合調度以及兼顧應急信道的混合調度中，當擬調度窗口發(fā)送計數有效而數據無效時，算法將跳過該窗口調度下一個窗口，實現(xiàn)了窗口時隙自動接續(xù)；

3)算法動態(tài)特性強。初始化時、每一輪調度完畢后，算法獲取窗口占用時隙、信道占用時隙以及信道優(yōu)先級，每次異步信道調度時也獲取信道優(yōu)先級，調度策略的參數化也提高了算法的動態(tài)調整性能。

本文提出的算法，拋開了傳統(tǒng)算法把時隙計算、優(yōu)先級計算和調度策略內嵌到算法中的設計思路，信道占用時隙、信道優(yōu)先級、信道調度模式、調度策略等均以參數形式傳入，提高了算法通用性和適用性。