高級在軌系統中的虛擬信道混合調度算法研究

別玉霞 張秀奇* 王宇鵬 胡 智

①(沈陽航空航天大學電子信息工程學院 沈陽 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數據的緊迫性，在平均調度時延、幀剩余量和算法滿意度上，均有更好的效果，更適合空間多類型業務的有效傳輸。