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

①(沈陽航空航天大學(xué)電子信息工程學(xué)院 沈陽 110136)

②(沈陽師范大學(xué)軟件學(xué)院 沈陽 110134)

1 引言

隨著航空航天技術(shù)的發(fā)展，空間任務(wù)呈現(xiàn)復(fù)雜化、多樣化、高速率、強(qiáng)突發(fā)等特點(diǎn)，對大容量和高實(shí)時傳輸及處理提出了要求。世界空間組織創(chuàng)立的空間數(shù)據(jù)系統(tǒng)咨詢委員會負(fù)責(zé)開發(fā)各種適應(yīng)航天器復(fù)雜化及有效利用有限空間資源的通信協(xié)議[1]。其初級階段為以分包遙測、遙控為核心的常規(guī)在軌系統(tǒng)，高級階段為能夠?qū)崿F(xiàn)空間鏈路層數(shù)據(jù)傳輸?shù)母呒壴谲壪到y(tǒng)(Advanced Orbiting Systems,AOS)[2]。AOS通過劃分虛擬信道(Virtual Channel,VC)[3]，可以在每條虛擬信道上傳輸來自星上不同服務(wù)需求的數(shù)據(jù)，匯成一條數(shù)據(jù)流后通過物理信道傳輸。AOS采用動態(tài)的虛擬信道調(diào)度技術(shù)，可以靈活處理多信源、多用戶、多目標(biāo)的高速率數(shù)據(jù)業(yè)務(wù)，實(shí)現(xiàn)多用戶高效共享同一條物理信道，從而滿足不同航天器和不同類型用戶的傳輸需求[4]。

虛擬信道調(diào)度是按照一定的調(diào)度順序，以時分復(fù)用的方式對信道中的幀進(jìn)行傳輸。AOS傳輸?shù)臉I(yè)務(wù)類型呈現(xiàn)多樣化，包括工程遙測數(shù)據(jù)、生理遙測數(shù)據(jù)、工程遙控?cái)?shù)據(jù)、科學(xué)觀測數(shù)據(jù)、科學(xué)實(shí)驗(yàn)數(shù)據(jù)、延時回放數(shù)據(jù)、音頻數(shù)據(jù)、視頻數(shù)據(jù)等。目前的AOS虛擬信道調(diào)度算法主要包括經(jīng)典調(diào)度算法、動態(tài)優(yōu)先級調(diào)度算法和群智能調(diào)度算法等。經(jīng)典調(diào)度算法只是考慮單一參數(shù)來決定虛擬信道的調(diào)度順序[5]，當(dāng)傳輸不同服務(wù)需求的數(shù)據(jù)時，因考慮不全面會導(dǎo)致時延及幀剩余量等方面的問題。動態(tài)優(yōu)先級調(diào)度算法[6–8]考慮傳輸緊迫度基數(shù)和傳輸緊迫度加權(quán)系數(shù)兩個因素，并沒有具體考慮到各虛擬信道的幀剩余量和時延，有一定的片面性。本文將虛擬信道的幀剩余量和時延兩因素考慮在算法中，優(yōu)化了數(shù)據(jù)的時效性和系統(tǒng)緩存性能。典型的群智能算法包括遺傳算法[9]、蟻群算法[10]、粒子群算法[11–13]等。群智能算法在各種調(diào)度問題上廣泛應(yīng)用，其中粒子群算法因簡單、易實(shí)現(xiàn)、收斂速度快等優(yōu)點(diǎn)在調(diào)度問題上得到了較多的應(yīng)用。

綜上，本文首先將AOS多種類型的業(yè)務(wù)分為異步數(shù)據(jù)和同步數(shù)據(jù)。異步數(shù)據(jù)使用異步虛擬信道調(diào)度，基于粒子群算法的框架，結(jié)合遺傳算法的交叉與變異算子，提出了基于遺傳-粒子群排序的異步虛擬信道調(diào)度算法。同步數(shù)據(jù)使用同步虛擬信道調(diào)度，在輪詢調(diào)度算法的基礎(chǔ)上，引入動態(tài)加權(quán)因子，設(shè)計(jì)了基于動態(tài)加權(quán)輪詢的同步虛擬信道調(diào)度算法。異步與同步虛擬信道的混合調(diào)度算法能夠減小平均調(diào)度時延和幀剩余量，提高處理效率。

2 AOS虛擬信道混合調(diào)度模型

2.1 虛擬信道調(diào)度方式

航天器數(shù)據(jù)類型多樣化，數(shù)據(jù)量大小不一，傳輸實(shí)時性要求也各不相同。在AOS傳輸?shù)臉I(yè)務(wù)中，工程遙測、生理遙測、工程遙控、科學(xué)觀測、科學(xué)實(shí)驗(yàn)和延時回放數(shù)據(jù)的突發(fā)性強(qiáng)，需優(yōu)先處理，屬于異步數(shù)據(jù)，在異步虛擬信道中傳輸；音頻數(shù)據(jù)和視頻數(shù)據(jù)的等時性高，屬于同步數(shù)據(jù)，在同步虛擬信道中傳輸；此外，本文增加一條VIP虛擬信道，專門負(fù)責(zé)傳輸某些重要性和緊迫性極強(qiáng)的緊急數(shù)據(jù)，稱為VIP數(shù)據(jù)。

為高效共享同一條物理信道，AOS將這些數(shù)據(jù)以時分復(fù)用的方式在不同的虛擬信道中傳輸。由于每種數(shù)據(jù)業(yè)務(wù)的傳輸要求不同，本文為每種數(shù)據(jù)業(yè)務(wù)分別分配一條虛擬信道，每條虛擬信道分配一個優(yōu)先級。

虛擬信道調(diào)度方式有全同步、全異步和同步/異步混合調(diào)度。全同步調(diào)度方式中，每個虛擬信道的調(diào)度順序是固定的，僅適用于同步數(shù)據(jù)的傳輸，不能靈活處理突發(fā)的異步數(shù)據(jù)。全異步調(diào)度方式可根據(jù)每個虛擬信道的優(yōu)先級靈活地傳輸，但對于那些優(yōu)先級較低的同步數(shù)據(jù)，有可能產(chǎn)生較長的排隊(duì)延時。同步/異步混合調(diào)度方式是將虛擬信道劃分為同步虛擬信道和異步虛擬信道兩部分，分別傳輸同步數(shù)據(jù)和異步數(shù)據(jù)，可同時解決對異步數(shù)據(jù)的靈活處理和同步數(shù)據(jù)的等時傳輸問題，適用于傳輸要求不同的多類型數(shù)據(jù)的傳輸，相比前兩種調(diào)度方式，系統(tǒng)效率更高，雖增加了調(diào)度的復(fù)雜度，但能較好地避免前兩種方法的缺陷。

圖1 虛擬信道調(diào)度系統(tǒng)結(jié)構(gòu)

2.2 虛擬信道混合調(diào)度過程

本文將一個調(diào)度周期分為異步時隙和同步時隙，且兩類時隙輪流出現(xiàn)。異步時隙時只調(diào)度異步虛擬信道，同步時隙時只調(diào)度同步虛擬信道。若完成一輪異步或同步調(diào)度后出現(xiàn)VIP數(shù)據(jù)，則其他虛擬信道停止傳輸，允許VIP數(shù)據(jù)立即占用當(dāng)前時隙。沒有數(shù)據(jù)等待傳送時，傳輸填充幀。

虛擬信道混合調(diào)度過程中有調(diào)度同步虛擬信道、調(diào)度異步虛擬信道、傳送VIP虛擬信道和傳送填充幀4種狀態(tài)。虛擬信道混合調(diào)度的狀態(tài)圖如圖2所示。其中，X代表下一時隙為異步時隙，Y代表下一時隙為同步時隙，V代表有VIP數(shù)據(jù)，NV代表無VIP數(shù)據(jù)，A代表有異步數(shù)據(jù)，NA代表無異步數(shù)據(jù)，S代表有同步數(shù)據(jù)，NS代表無同步數(shù)據(jù)。

圖2 虛擬信道混合調(diào)度狀態(tài)圖

單一的粒子群算法和遺傳算法在多目標(biāo)調(diào)度問題中容易陷入局部最優(yōu)解，將兩種算法結(jié)合可以有效解決此問題。因此，對異步虛擬信道，本文采用基于遺傳-粒子群排序的調(diào)度算法，群體內(nèi)的粒子根據(jù)遺傳算法進(jìn)化算子進(jìn)行自身位置更新，從而找到最優(yōu)的異步虛擬信道調(diào)度順序。動態(tài)加權(quán)輪詢調(diào)度算法根據(jù)虛擬信道的數(shù)據(jù)量制定動態(tài)加權(quán)系數(shù)，輪流傳輸，適用于傳輸同步數(shù)據(jù)。因此對同步虛擬信道，本文采用動態(tài)加權(quán)輪詢的調(diào)度算法，即調(diào)度時間內(nèi)，各同步虛擬信道按照加權(quán)因子和分配的時隙數(shù)，輪流占用物理信道。

3 基于遺傳-粒子群排序的異步虛擬信道調(diào)度算法

3.1 遺傳-粒子群適應(yīng)度函數(shù)模型

AOS虛擬信道調(diào)度問題為一種組合優(yōu)化問題，即在有限個可行調(diào)度順序集合中找出最優(yōu)調(diào)度順序，通過約束得出影響異步虛擬信道調(diào)度順序的適應(yīng)度函數(shù)。該調(diào)度問題中主要有以下約束：

(1) 業(yè)務(wù)優(yōu)先級約束。隨著AOS傳輸?shù)臄?shù)據(jù)業(yè)務(wù)種類不斷增多，不同業(yè)務(wù)的實(shí)時性和吞吐率要求不同。在AOS虛擬信道復(fù)用中，表現(xiàn)為業(yè)務(wù)優(yōu)先級的不同。高優(yōu)先級業(yè)務(wù)的實(shí)時性和吞吐率要求高，即要求延時小、幀剩余量低。相反低優(yōu)先級業(yè)務(wù)對時延和幀剩余量的要求低。因此，業(yè)務(wù)優(yōu)先級約束對不同虛擬信道的調(diào)度時延、幀剩余量提出了不同的要求，AOS虛擬信道調(diào)度系統(tǒng)應(yīng)考慮不同業(yè)務(wù)的優(yōu)先級約束。

(2) 調(diào)度時延緊迫度約束。調(diào)度時延緊迫度約束取決于當(dāng)前虛擬信道的實(shí)際調(diào)度時延和最大調(diào)度時延。其中最大調(diào)度時延與業(yè)務(wù)的時效性要求和優(yōu)先級有關(guān)。基于業(yè)務(wù)時效性要求，每種業(yè)務(wù)的數(shù)據(jù)要在其最大調(diào)度時延內(nèi)得到傳輸，使用戶在該時間內(nèi)得到最有價值的信息，超過最大調(diào)度時延的信息將不再具有價值。此外，為保證重要信息的及時傳達(dá)，應(yīng)盡快傳輸高優(yōu)先級虛擬信道的數(shù)據(jù)，因此最大調(diào)度時延的設(shè)置應(yīng)取決于虛擬信道的優(yōu)先級。

(4) 適應(yīng)度函數(shù)。綜合考慮AOS虛擬信道調(diào)度問題的3種約束，建立的混合粒子群適應(yīng)度函數(shù)為

但從研究現(xiàn)狀來看，國內(nèi)學(xué)術(shù)界對海外中國政治研究的回應(yīng)，無論是與海外新漢學(xué)研究成果的豐富相比較，還是與中國政治實(shí)踐的波瀾壯闊相比較，都顯得過于單薄。就研究主體而言，盡管近年來介入海外中國研究的作者與機(jī)構(gòu)開始增多，但他們的研究基本上處于一種分散化的狀態(tài)，合作研究甚少，更沒有建立起跨區(qū)域、跨學(xué)科的協(xié)同研究機(jī)制與平臺。與之相對應(yīng)，相關(guān)研究得不到有力的平臺支撐，目前還沒有普惠性的供專門跟蹤海外中國研究成果的信息平臺，已有的數(shù)據(jù)庫服務(wù)的對象面相對較窄；除《國外社會科學(xué)》《國外理論動態(tài)》外，相關(guān)研究的成果發(fā)表渠道更是稀缺。

3.2 遺傳-粒子群調(diào)度算法設(shè)計(jì)

(c) 選擇算子。為提高收斂速度，并避免陷入局部極值，本文采用父子競爭與隨機(jī)產(chǎn)生競爭相結(jié)合的選擇機(jī)制。首先，采用父子競爭機(jī)制，分別計(jì)算粒子原本位置向量x和經(jīng)過交叉變異后的位置向量x′′的適應(yīng)度函數(shù)值，選擇其中適應(yīng)度函數(shù)值小的一個，其位置向量記為x′′′，父子競爭可以保護(hù)優(yōu)良的位置向量，提高收斂速度。

其次，為了增加粒子多樣性，避免陷入局部極值，采用隨機(jī)產(chǎn)生競爭機(jī)制。隨機(jī)產(chǎn)生一個位置向量x′′′′，比較x′′′與x′′′′的適應(yīng)度函數(shù)值，選擇其中適應(yīng)度函數(shù)值小的一個，作為粒子位置更新后的最終位置向量x′′′′′，隨機(jī)產(chǎn)生競爭機(jī)制可使算法跳出局部極值，擴(kuò)大搜索范圍。

3.3 基于遺傳-粒子群排序的異步虛擬信道調(diào)度流程

粒子群隨機(jī)初始化后，首先根據(jù)式(7)計(jì)算每個粒子適應(yīng)度函數(shù)值f(i)，記為粒子個體最優(yōu)值，粒子群最優(yōu)值g取最小的f(i)值。然后使用遺傳-粒子群進(jìn)化算子更新粒子位置，根據(jù)新位置向量計(jì)算粒子適應(yīng)度函數(shù)值，并與初始粒子個體最優(yōu)值比較，將較小值作為新的粒子個體最優(yōu)值；再將新的粒子個體最優(yōu)值與全局極值比較，將較小值作為新的全局極值。按上述過程，N個粒子經(jīng)過D次位置更新后得出粒子群最優(yōu)值對應(yīng)的位置向量，即群最優(yōu)位置gBest， gBest就是當(dāng)前最優(yōu)調(diào)度順序。遺傳-粒子群排序過程如表1所示。

表1 算法1：遺傳-粒子群排序過程

圖3 交叉過程示意圖

圖4 變異過程示意圖

確定當(dāng)前時隙是異步時隙時，首先判斷異步虛擬信道中是否有數(shù)據(jù)(幀剩余量≥1)。若有數(shù)據(jù)，根據(jù)式(7)計(jì)算適應(yīng)度函數(shù)值，根據(jù)算法1求出當(dāng)前最優(yōu)調(diào)度順序，并按照此順序依次傳輸有數(shù)據(jù)的異步虛擬信道。若異步虛擬信道中沒有數(shù)據(jù)，則傳輸填充數(shù)據(jù)。異步虛擬信道調(diào)度過程如表2所示。

表2 算法2：異步虛擬信道調(diào)度過程

4 基于動態(tài)加權(quán)輪詢的同步虛擬信道調(diào)度算法

在同步調(diào)度周期內(nèi)，由于每個同步虛擬信道的包到達(dá)率不同，為提高同步虛擬信道的傳輸效率，本文在周期輪詢調(diào)度算法的基礎(chǔ)上，引入動態(tài)加權(quán)因子，設(shè)計(jì)了基于動態(tài)加權(quán)周期輪詢的同步虛擬信道調(diào)度算法，優(yōu)化系統(tǒng)的調(diào)度性能。算法首先對各同步虛擬信道分配加權(quán)因子，加權(quán)因子與相應(yīng)同步虛擬信道的包到達(dá)率成正比。在一個同步調(diào)度周期內(nèi)，各同步虛擬信道占用的時隙數(shù)正比于其加權(quán)因子。設(shè)同步虛擬信道數(shù)量為n，第i條同步虛擬信道的包到達(dá)率為Qi(i＝1,2,···,n)，則第i條同步虛擬信道的加權(quán)因子Ai為

設(shè)一個同步調(diào)度周期內(nèi)同步虛擬信道的總時隙數(shù)為Ts，則第i條同步虛擬信道可分配到的時隙數(shù)Fi為

確定前時隙為同步時隙時，按照以上過程計(jì)算每條同步虛擬信道加權(quán)因子Ai的值和可分配到的時隙數(shù)Fi，加權(quán)因子Ai由大到小的排列順序即為同步虛擬信道的調(diào)度順序，以相應(yīng)的時隙數(shù)為間隔依次輪流調(diào)度，并計(jì)算出各同步虛擬信道的平均調(diào)度時延和幀剩余量。在下一個同步調(diào)度周期內(nèi)，同步虛擬信道的包到達(dá)率發(fā)生變化，所以加權(quán)因子和可分配到的時隙數(shù)也隨其動態(tài)變化。

同步虛擬信道采用動態(tài)加權(quán)輪詢調(diào)度算法，既能滿足同步虛擬信道的延時要求，又能提高同步類型數(shù)據(jù)在傳輸過程中的公平性，減少數(shù)據(jù)的剩余量，提高處理效率。

5 仿真與分析

按圖1所示的系統(tǒng)模型進(jìn)行仿真，并與輪詢調(diào)度算法、動態(tài)優(yōu)先級調(diào)度算法、遺傳調(diào)度算法進(jìn)行對比。

5.1 參數(shù)設(shè)置

仿真參數(shù)設(shè)置如下：

(1) 仿真時間T＝0.1 s；

(2) 處理速度為1×105～1.7×105幀/s；

(3) 虛擬信道總數(shù)為9個。其中，VC1～VC6為異步虛擬信道，VC7～VC8為同步虛擬信道，VC9為VIP虛擬信道。同步虛擬信道和異步虛擬信道的包到達(dá)服從泊松過程。VIP虛擬信道的幀到達(dá)率λ(t)服從正弦分布，表達(dá)式為

其中，λmax＝5×103幀/s為最大幀到達(dá)率，TVIP＝0.25T為幀到達(dá)率變化周期。具體參數(shù)設(shè)置如表3所示。

表3 虛擬信道參數(shù)

(4) 粒子群初始化：粒子個數(shù)N＝10，空間維度n＝6，位置更新次數(shù)D＝30。

5.2 平均調(diào)度時延仿真

對比圖5可以看出，除輪詢調(diào)度算法VC2在處理速度小于1.2×105幀/s時存在平均調(diào)度時延外，VC1～VC6以及VC9的平均調(diào)度時延基本為0，4種算法的主要區(qū)別在于VC7和VC8的平均調(diào)度時延。由于VC8的平均幀到達(dá)率較高，在動態(tài)優(yōu)先級調(diào)度算法中，其平均調(diào)度時延較大，此外，動態(tài)優(yōu)先級調(diào)度算法中VC7的平均調(diào)度時延大于0。在遺傳調(diào)度算法中，VC8的平均調(diào)度時延高于輪詢調(diào)度算法和動態(tài)優(yōu)先級調(diào)度算法，較動態(tài)優(yōu)先級調(diào)度算法多7.41%，較輪詢調(diào)度算法多31.84%; VC7的平均調(diào)度時延略低于動態(tài)優(yōu)先級調(diào)度算法，約為動態(tài)優(yōu)先級調(diào)度算法的35.09%。在本文算法中，VC8的平均調(diào)度時延均小于動態(tài)優(yōu)先級調(diào)度算法和遺傳調(diào)度算法，約為動態(tài)優(yōu)先級調(diào)度算法的91.55%，約為遺傳調(diào)度算法的85.24%；VC7的平均調(diào)度時延幾乎為0?？梢姡疚牡幕旌险{(diào)度算法在調(diào)度時延性能上有明顯的提升。

圖5 平均調(diào)度時延

5.3 幀剩余量仿真

對比圖6可以看出，除輪詢調(diào)度算法VC2在處理速度小于1.2×105幀/s時存在幀剩余量外，VC1～VC6以及VC9的幀剩余量基本為0，4種算法的區(qū)別主要在于VC7和VC8的幀剩余量。由于VC8的平均幀到達(dá)率較高，在輪詢調(diào)度算法中幀剩余量最大。VC8的幀剩余量在動態(tài)優(yōu)先級調(diào)度算法中也較大，此外，VC7也有一定的幀剩余量。在遺傳調(diào)度算法中，當(dāng)處理速度小于1.65×105幀/s時，VC8的幀剩余量少于動態(tài)優(yōu)先級調(diào)度算法，VC7的幀剩余量幾乎為0；處理速度大于1.65×105幀/s時，各虛擬信道的幀剩余量為0。在本文算法中，當(dāng)處理速度小于1.34×105幀/s時，VC8的幀剩余量均明顯少于其他3種調(diào)度算法，VC7的幀剩余量幾乎為0；處理速度大于1.34×105幀/s時，各虛擬信道的幀剩余量為0?？梢?，本文的混合調(diào)度算法能有效降低虛擬信道的幀剩余量，從而可提高數(shù)據(jù)幀的實(shí)時傳輸性能，并降低丟幀率。

圖6 虛擬信道幀剩余量

5.4 算法滿意度分析

為了衡量算法的總體調(diào)度性能，本文參考文獻(xiàn)[14,15]設(shè)計(jì)了算法滿意度，仿真部分主要對比了輪詢調(diào)度算法、動態(tài)優(yōu)先級調(diào)度算法、遺傳調(diào)度算法、遺傳-粒子群排序調(diào)度算法中幀剩余量和平均調(diào)度時延的差異，所以滿意度公式中除了優(yōu)先級外還考慮了幀剩余量和平均調(diào)度時延。算法滿意度B用式(12)表示

其中，Pi為第i條虛擬信道的優(yōu)先級，RESi為第i條虛擬信道的幀剩余量，tavg_delay_i為第i條虛擬信道的平均調(diào)度時延。設(shè)各算法滿意度的最大值為Bmax，則算法的歸一化滿意度可表示為

圖7為4種算法的歸一化滿意度隨處理速度變化的曲線?？梢钥闯?，本文算法的滿意度更好。

圖7 算法的歸一化滿意度

綜上，通過對算法的仿真與分析得出，本文提出的虛擬信道混合調(diào)度算法，在滿足各虛擬信道數(shù)據(jù)源特性的基礎(chǔ)上，有更小的平均調(diào)度時延和更少的幀剩余量。不能實(shí)時處理時，在一定程度上犧牲幀到達(dá)率較大的同步數(shù)據(jù)，提高整體的調(diào)度性能，算法整體滿意度較高。同時，通過同步異步混合調(diào)度的方式，滿足了不同類型異步數(shù)據(jù)的傳輸要求，保證了VIP數(shù)據(jù)的實(shí)時傳輸，同時兼顧了同步數(shù)據(jù)的等時性。

衛(wèi)星系統(tǒng)與AOS高級在軌系統(tǒng)相似，都需要在有限資源的情況下合理地分配業(yè)務(wù)量大、種類多的任務(wù)，因此衛(wèi)星系統(tǒng)調(diào)度問題也屬于組合優(yōu)化問題。本文將遺傳算法和粒子群算法結(jié)合，解決了傳統(tǒng)算法收斂速度慢的問題，且遺傳-粒子群算法簡單易實(shí)現(xiàn)有較強(qiáng)的搜索和尋優(yōu)能力，能夠合理且快速地調(diào)度資源，實(shí)現(xiàn)衛(wèi)星資源使用效能最大化，所以本文算法的計(jì)算復(fù)雜度同樣適用于衛(wèi)星系統(tǒng)。

6 結(jié)束語

本文基于AOS虛擬信道復(fù)用技術(shù)，針對空間數(shù)據(jù)業(yè)務(wù)類型的多樣化，建立了AOS虛擬信道混合調(diào)度模型，提出基于遺傳-粒子群排序的異步虛擬信道調(diào)度算法、基于動態(tài)加權(quán)輪詢的同步虛擬信道調(diào)度算法。仿真表明，本文所提虛擬信道混合調(diào)度算法兼顧了異步數(shù)據(jù)的優(yōu)先性、同步數(shù)據(jù)的等時性和VIP數(shù)據(jù)的緊迫性，在平均調(diào)度時延、幀剩余量和算法滿意度上，均有更好的效果，更適合空間多類型業(yè)務(wù)的有效傳輸。