何鋒，李二帥，周璇，李浩若，龔子杰

北京航空航天大學(xué) 電子信息工程學(xué)院，北京 100191

航空電子系統(tǒng)(以下簡稱航電系統(tǒng))涵蓋飛機(jī)通信、導(dǎo)航、探測、管理、控制等所有電子系統(tǒng)以及支撐各系統(tǒng)間信息交換和資源共享的網(wǎng)絡(luò)系統(tǒng)，是具有苛刻空間限制和功能/性能約束條件的信息密集型系統(tǒng)[1]。機(jī)載網(wǎng)絡(luò)是航電系統(tǒng)的重要組成部分，其連接飛機(jī)物理結(jié)構(gòu)空間中的相關(guān)電子設(shè)備，支持電子系統(tǒng)間的信息綜合與功能綜合，從而使航電系統(tǒng)成為有機(jī)整體，并標(biāo)志著航電系統(tǒng)架構(gòu)代際演化[2]。

隨著計算機(jī)、通信等技術(shù)的飛速發(fā)展，航電系統(tǒng)對機(jī)載網(wǎng)絡(luò)提出了更高的性能要求。采用時間觸發(fā)(Time-Triggered，TT)通信機(jī)制可以避免傳統(tǒng)事件觸發(fā)(Event-Triggered，ET)通信機(jī)制下的資源競爭與共享沖突問題，從而提高信息傳輸?shù)膶崟r性，并保證信息交互的確定性。目前，以時間觸發(fā)以太網(wǎng)[3](Time-Triggered Ethernet, TTE)等為代表的時間觸發(fā)通信技術(shù)方案已得到廣泛關(guān)注，但將其應(yīng)用于機(jī)載環(huán)境中需首要保證合理的時間觸發(fā)通信調(diào)度。這種通信調(diào)度設(shè)計協(xié)調(diào)TT消息，規(guī)劃時間偏置，以避免TT消息爭用物理鏈路影響其確定性傳輸，具有NP求解復(fù)雜度[4]，難以在多項式時間內(nèi)完成，因此需要探尋求解優(yōu)化技術(shù)。此外，從航電系統(tǒng)功能實現(xiàn)的角度出發(fā)，機(jī)載網(wǎng)絡(luò)支持混合關(guān)鍵性流量以匹配不同優(yōu)先級別任務(wù)，通信調(diào)度設(shè)計應(yīng)關(guān)注消息延遲影響，保證消息盡快在規(guī)定時間內(nèi)完成傳輸；并進(jìn)一步支持應(yīng)用層面任務(wù)執(zhí)行，以拓展應(yīng)用-網(wǎng)絡(luò)聯(lián)動調(diào)度，由此也對調(diào)度設(shè)計提出了進(jìn)一步優(yōu)化訴求。

目前，通信調(diào)度設(shè)計多基于有約束引導(dǎo)的啟發(fā)式方法或者求解方法進(jìn)行，通過設(shè)置網(wǎng)絡(luò)拓?fù)浜土髁筷P(guān)系等約束，生成滿足約束的TT調(diào)度表，典型包括可滿足性模理論[5-8](Satisfiability Modulo Theories，SMT)、混合整數(shù)規(guī)劃[9-12](Mixed Integer Programming，MIP)以及啟發(fā)式算法[13-16]，這些方法在求解過程中具有不同的解算速度和優(yōu)化能力，但一般都比較耗時。采用強(qiáng)化學(xué)習(xí)[17](Reinforcement Learning，RL)方法在多領(lǐng)域算法優(yōu)化方面具備了一些成功案例，可以考慮利用馬爾可夫過程描述增量化調(diào)度任務(wù)，通過設(shè)置調(diào)度狀態(tài)、動作和獎勵，以實現(xiàn)快速優(yōu)化設(shè)計。不同的調(diào)度設(shè)計方法遵循不同的數(shù)學(xué)模型，采用不同的求解方式，同時也具有不同的運算特征和評價性能。為指導(dǎo)工程實際應(yīng)用中調(diào)度方法的適應(yīng)性選擇與進(jìn)一步發(fā)展，應(yīng)結(jié)合調(diào)度求解能力與性能保障兩個角度，從求解時間、可求解規(guī)模以及實時通信影響等多個維度開展對比分析研究。

為此，本文首先概要介紹時間觸發(fā)通信的過程與特征；在其基礎(chǔ)上給出不同約束引導(dǎo)下的調(diào)度模型，并發(fā)展出基于強(qiáng)化學(xué)習(xí)的調(diào)度方法；然后從求解能力和性能保障角度出發(fā)，建立具有普適性的調(diào)度設(shè)計評價指標(biāo)；最后以典型網(wǎng)絡(luò)拓?fù)錇閼?yīng)用背景，針對不同調(diào)度設(shè)計方法開展對比研究，分析并歸納實際應(yīng)用特征，以期探尋機(jī)載網(wǎng)絡(luò)時間觸發(fā)調(diào)度模式，并給出調(diào)度算法選擇參考建議。

本文的創(chuàng)新點在于：形成了對時間觸發(fā)通信調(diào)度設(shè)計方法的一致符號與模型描述，提出了時間觸發(fā)通信調(diào)度設(shè)計評價指標(biāo)體系與計算公式，針對不同調(diào)度設(shè)計方法應(yīng)用特征并結(jié)合典型案例進(jìn)行了性能對比和建議。

1 時間觸發(fā)通信機(jī)制

時間觸發(fā)通信著重滿足安全關(guān)鍵任務(wù)中消息傳輸?shù)膶崟r性要求，并致力于保證數(shù)據(jù)傳輸?shù)拇_定性與可靠性，在機(jī)載網(wǎng)絡(luò)升級換代中扮演關(guān)鍵角色。典型時間觸發(fā)通信組網(wǎng)方案包括MIL-STD-1553B[18-19]、時間觸發(fā)協(xié)議[20](Time-Triggered Protocol，TTP)、時間觸發(fā)控制器局域網(wǎng)[21](Time-Triggered-Controller Area Network，TTCAN)[22]、TTE以及時間敏感網(wǎng)絡(luò)[23](Time-Sensitive Network，TSN)，其主要技術(shù)匯總?cè)绫?所示。這些組網(wǎng)方案基于時間觸發(fā)通信進(jìn)行調(diào)度設(shè)計，各個節(jié)點設(shè)備根據(jù)固定時刻驅(qū)動網(wǎng)絡(luò)上的所有活動，可以有效保證航電系統(tǒng)對信息交互的實時性和確定性要求。TTE、TSN等新一代交換式互連技術(shù)更是憑借著高帶寬利用率、可擴(kuò)展組網(wǎng)規(guī)模等優(yōu)勢，能夠很好地滿足機(jī)載系統(tǒng)發(fā)展需求。

表1 典型時間觸發(fā)通信組網(wǎng)方案技術(shù)匯總

本文以典型TTE網(wǎng)絡(luò)為應(yīng)用背景進(jìn)行時間觸發(fā)通信調(diào)度設(shè)計與評價研究，其可支持TT流量、速率約束(Rate Constrained，RC)流量和盡力傳輸(Best Effort，BE)流量混合關(guān)鍵性傳輸[24]。圖1給出包含三個端系統(tǒng)與一個交換機(jī)的TTE網(wǎng)絡(luò)示例，其中發(fā)送端1發(fā)送一條周期為3 ms的TT流量以及BE流量，發(fā)送端2發(fā)送一條周期為2 ms的TT流量以及BE、RC流量，交換機(jī)對來自于2個發(fā)送端的流量進(jìn)行綜合，向接收端發(fā)送集成流量。

圖1 TTE網(wǎng)絡(luò)中流量的傳輸過程

考慮時間觸發(fā)通信的具體過程，當(dāng)多條流量在交換網(wǎng)絡(luò)中傳輸綜合時，TT流量在全局時鐘同步機(jī)制基礎(chǔ)上，通過靜態(tài)規(guī)劃傳輸時間窗口并離線生成時間調(diào)度表，可以實現(xiàn)無沖突傳輸，從而有效改善時間確定性和傳輸可靠性。RC流量遵循事件觸發(fā)通信機(jī)制，缺乏事先規(guī)劃好的傳輸時間窗口，勢必會與其它事件觸發(fā)消息競爭端口輸出，導(dǎo)致傳輸過程存在很大的不確定性；而且其與更高優(yōu)先級的TT流量在傳輸過程中相遇時，采取避讓(集成)策略，將進(jìn)一步增加傳輸不確定性。BE流量為傳統(tǒng)以太網(wǎng)通信方式，具有最低優(yōu)先級且無需服務(wù)質(zhì)量(Quality of Service,QoS)保證。

2 基于約束引導(dǎo)的調(diào)度設(shè)計

2.1 SMT方法

SMT問題是布爾可滿足問題的拓展，用于求解SMT問題的自動化工具被稱為SMT求解器，常用的有Yices、Z3等。由于TT消息在傳輸過程中受到嚴(yán)格時間約束，可以根據(jù)網(wǎng)絡(luò)拓?fù)浼芭渲脜?shù)表示約束條件，將其轉(zhuǎn)換成SMT一階邏輯形式，并利用SMT求解器求解，從而實現(xiàn)TT通信調(diào)度設(shè)計。文獻(xiàn)[5]首先提出這種基于SMT的調(diào)度設(shè)計方法，其針對多跳網(wǎng)絡(luò)給出了背靠背傳輸模式下的調(diào)度約束條件，并通過增量化的方式提高了求解速度；進(jìn)一步，為了兼顧RC消息傳輸實時性，將TT消息間隔視作孔隙，提出了多孔傳輸模式下的調(diào)度求解方法。文獻(xiàn)[6]改進(jìn)了傳統(tǒng)基于靜態(tài)SMT的TT調(diào)度方法，以獲得最佳離散間隔來減小RC的端到端延遲。

1)基本周期約束：任意消息fi在其傳輸路徑pi,j上的任意輸出端口τr處的發(fā)送時刻非負(fù)，且能保證fi在其傳輸周期內(nèi)發(fā)送完成。

2)路徑依賴約束：任意消息fi在其傳輸路徑pi,j上兩個相鄰的輸出端口τr、τs的調(diào)度時刻受到交換機(jī)緩沖區(qū)深度、存儲空間大小以及技術(shù)延遲等限制。

3)端到端傳輸約束：任意消息fi的端到端傳輸延遲fi,j,r·etedelay不超過其截止期限。

4)同步轉(zhuǎn)發(fā)約束：考慮多播消息fi在輸出端口τr首次出現(xiàn)傳輸路徑分離，其在τr及前序端口處的調(diào)度時刻均應(yīng)相同[25]。

5)傳輸開銷約束：任意輸出端口τr處TT時間片數(shù)量最小，也即TT消息背靠背傳輸[6]。

6)無沖突約束：任意兩條消息fi、fk，若其傳輸路徑pi,j、pk,l均經(jīng)過輸出端口τr，則fi、fk的發(fā)送時刻應(yīng)保證兩消息在τr處不發(fā)生競爭沖突，可表示為

?τr∈pi,j∩pk,l,

{fi,j,r·offset+a×fi·period≥fk,l,r·

offset+b×fk·period+fk·length}∨

{fk,l,r·offset+b×fk·period≥

fi,j,r·offset+a×fi·period+fi·length}

(1)

式中：HPr表示流經(jīng)τr的所有消息的超周期。

2.2 MIP方法

MIP方法是一種線性規(guī)劃方法，其在給定線性約束條件下，研究線性目標(biāo)函數(shù)的極值問題，目前有Gurobi、CPLEX等多種求解器，可實現(xiàn)大規(guī)模約束變量和約束條件下的MIP問題快速規(guī)劃。由于其天然支持帶目標(biāo)條件的性能優(yōu)化求解，已被許多學(xué)者用來實施通信調(diào)度設(shè)計研究。例如，文獻(xiàn)[9]引入幀間間隔和同步誤差等時間參數(shù)，并考慮與應(yīng)用層匹配，實現(xiàn)了應(yīng)用響應(yīng)時間和端到端延遲的多目標(biāo)優(yōu)化；文獻(xiàn)[10]進(jìn)一步強(qiáng)調(diào)消息對任務(wù)的依賴關(guān)系，通過預(yù)先處理減少約束變量，可在合理時間內(nèi)完成工業(yè)規(guī)模的消息調(diào)度設(shè)計；文獻(xiàn)[11]分析TT消息發(fā)送、傳輸和接收的完整過程，以消息流累積端到端延遲為目標(biāo)進(jìn)行優(yōu)化設(shè)計；在此基礎(chǔ)上，文獻(xiàn)[12]將網(wǎng)絡(luò)與分區(qū)聯(lián)合考慮，給出了保證分區(qū)層端到端延遲最小時的通信調(diào)度結(jié)果。

基于MIP方法進(jìn)行調(diào)度設(shè)計也應(yīng)滿足與SMT方法相似的約束條件。但應(yīng)注意兩種方法所針對的求解域不同，MIP方法無法實現(xiàn)SMT方法中無沖突約束的Either-Or語句，所以需對式(1)進(jìn)行轉(zhuǎn)換表述，針對端口τr處的任意2條TT消息fi、fk引入二進(jìn)制決策變量βi,k,r有

?τr∈pi,j∩pk,l,

{fi,j,r·offset+a×fi·period+βi,k,r×φ≥

fk,l,r·offset+b×fk·period+fk·

length}∧{fk,l,r·offset+b×fk·

period+(1-βi,k,r)×φ≥fi,j,r·offset+

a×fi·period+fi·length}

(2)

式中：φ取值足夠大以保證βi,k,r=1時第1個不等式恒成立，而βi,k,r=0時第2個不等式恒成立。此外，MIP方法支持優(yōu)化設(shè)計，常用優(yōu)化目標(biāo)是最小化消息平均端到端傳輸延遲，即

(3)

因為該優(yōu)化目標(biāo)的引入，應(yīng)用MIP進(jìn)行調(diào)度設(shè)計的過程中通?？梢允÷远说蕉藗鬏敿s束。

2.3 啟發(fā)式方法

啟發(fā)式算法也是解優(yōu)化問題的一種常用方法，其根據(jù)某種啟發(fā)式信息對已知的可行解進(jìn)行改進(jìn)，通過若干次迭代在相對短的時間內(nèi)獲得滿意解，典型包括遺傳算法(Genetic Algorithm，GA)等。通常啟發(fā)式算法獲得的解極有可能是近似解，而不一定是最優(yōu)解，但由于啟發(fā)式算法實現(xiàn)簡單，且支持大規(guī)模快速運算，所以目前也已被廣泛應(yīng)用于時間觸發(fā)通信調(diào)度研究中。例如，文獻(xiàn)[13]綜合考慮TT與RC消息的可調(diào)度性，以RC端到端延遲最小為優(yōu)化目標(biāo)，進(jìn)行TT消息調(diào)度設(shè)計；文獻(xiàn)[14]在此基礎(chǔ)上，結(jié)合消息分包、VL分配與路由等因素影響，通過設(shè)置消息候選列表，進(jìn)一步提高了消息可調(diào)度性及傳輸緊性；文獻(xiàn)[15]針對系統(tǒng)應(yīng)用、分區(qū)或計算模塊增加導(dǎo)致通信流量增加的情況，完成了通信消息的增量式調(diào)度設(shè)計；文獻(xiàn)[16]在分區(qū)模型基礎(chǔ)上，設(shè)計TT消息的非多孔性調(diào)度表，可以大幅減少RC消息的端到端傳輸延遲。

基于啟發(fā)式方法進(jìn)行調(diào)度設(shè)計同樣也應(yīng)滿足與前文一致的約束條件，其公式化描述可以直接借鑒前文經(jīng)驗。值得注意的是SMT或MIP方法可直接應(yīng)用相應(yīng)的求解器，在設(shè)定求解變量、輸入約束條件后進(jìn)行黑盒運算，便能獲得滿足約束的調(diào)度方案；而啟發(fā)式算法還應(yīng)設(shè)計迭代搜索策略以保證優(yōu)化設(shè)計的運行速度和近似程度。一種通用方法是首先比較消息fi的端到端延遲與其截止期限，以判定是否存在可行調(diào)度解。令

(4)

顯然，若cTT/RC>0，則存在fi使得

fi,j·etedelay>fi,j·deadline

(5)

即不可調(diào)度；若cTT/RC=0，則恒有

fi,j·etedelay≤fi,j·deadline

(6)

即可調(diào)度。在此基礎(chǔ)上，定義

(7)

以表征不同可行調(diào)度解之間的性能差距，并設(shè)置代價函數(shù)

Cost=ωTT×δTT+ωRC×δRC

(8)

式中：δTT/RC為調(diào)度可行度，有

(9)

其中:ωTT/RC為TT或RC幀的懲罰權(quán)重。當(dāng)不可調(diào)度時，ωTT/RC取較大數(shù)值以保證搜索快速向可行區(qū)域推進(jìn)；當(dāng)可調(diào)度時，ωTT=0以保證搜索向RC延遲更小的性能優(yōu)化方向推進(jìn)。

3 基于強(qiáng)化學(xué)習(xí)的調(diào)度設(shè)計

基于約束引導(dǎo)的調(diào)度設(shè)計應(yīng)用于工業(yè)規(guī)模機(jī)載網(wǎng)絡(luò)往往存在耗時較長的缺陷，為實現(xiàn)工業(yè)規(guī)模下機(jī)載網(wǎng)絡(luò)的快速調(diào)度設(shè)計，可采用基于強(qiáng)化學(xué)習(xí)的設(shè)計方法。強(qiáng)化學(xué)習(xí)通過與動態(tài)環(huán)境的即時交互獲取狀態(tài)信息，并反饋強(qiáng)化信號對所采取的行動進(jìn)行評價，經(jīng)過不斷學(xué)習(xí)和選擇實現(xiàn)最優(yōu)策略。將其應(yīng)用于時間觸發(fā)通信調(diào)度設(shè)計，需要首先進(jìn)行適應(yīng)性定義，例如文獻(xiàn)[17]將狀態(tài)state定義為輸出端口當(dāng)前的消息排布方式，將動作action定義為TT消息在端口的調(diào)度發(fā)送時刻，即若干fi,j,r·offset，將獎勵reward定義為調(diào)度成功與否以及端到端傳輸延遲。

在訓(xùn)練初期，為了能夠盡快找到端到端延遲較小的調(diào)度表作為訓(xùn)練樣本，使用樹搜索方法結(jié)合深度優(yōu)先與最優(yōu)優(yōu)先進(jìn)行初始搜索，并剪掉明顯不能找到結(jié)果的分支加快搜索。

在訓(xùn)練階段，首先用初始搜索所得樣本對神經(jīng)網(wǎng)絡(luò)進(jìn)行預(yù)訓(xùn)練，以改進(jìn)均方差為目標(biāo)函數(shù)

(10)

獲得一條完整的訓(xùn)練軌跡，即可保證在每個狀態(tài)state(t)，神經(jīng)網(wǎng)絡(luò)的輸出out(t)逼近action(t)。為便于進(jìn)一步探索和適應(yīng)，需要對輸出out提供一定噪聲，可以out為中心，取寬度有限區(qū)間均勻采樣作為fi,j,r·offset。然后改進(jìn)貪婪策略進(jìn)行軌跡收集，在每個狀態(tài)處選擇盡量減小端到端延遲的動作action，將策略參數(shù)化并尋找最優(yōu)參數(shù)保證所有消息的端到端延遲最小。由于此時搜索空間較訓(xùn)練初期較小，應(yīng)使用較小的學(xué)習(xí)率，可設(shè)置目標(biāo)函數(shù)為軌跡總獎勵值，有

(11)

式中：P(t,θ)為t時刻策略選擇已執(zhí)行動作action的概率;reward(t)為t時刻執(zhí)行action的獎勵值。在此基礎(chǔ)上，對目標(biāo)函數(shù)求梯度以構(gòu)造損失函數(shù)，從而保證目標(biāo)函數(shù)以最快的速度向端到端延遲最小的方向收斂?？紤]到fi,j,r·offset可選擇范圍極大，直接計算梯度會導(dǎo)致梯度過大而無法優(yōu)化，故對其進(jìn)行對數(shù)化處理，有

(12)

為了獲得更多樣化的樣本，可以采用n步展開方法進(jìn)行搜索，即每到一個狀態(tài)時，模擬之后n步搜索。如果在n步之后可以滿足預(yù)先設(shè)定的最低端到端延遲要求，則繼續(xù)采用這一條軌跡；如果沒有滿足要求或者消息無法調(diào)度，則選擇其他軌跡。注意模擬最大深度n根據(jù)消息總數(shù)等特征確定，以避免n較小時過早收斂到初始軌跡而陷入局部最優(yōu)解，而n過大時導(dǎo)致計算開銷龐大；預(yù)先設(shè)定的閾值通過動態(tài)方法確定，可以根據(jù)搜索的深度進(jìn)行自適應(yīng)調(diào)整。

此外，這種基于強(qiáng)化學(xué)習(xí)的調(diào)度方法具備一定的泛化能力，在訓(xùn)練完成后可以直接應(yīng)用于消息分布相近的調(diào)度求解問題中。

4 調(diào)度設(shè)計評價

航電系統(tǒng)綜合化程度的不斷提高導(dǎo)致機(jī)載網(wǎng)絡(luò)在組網(wǎng)拓?fù)?、消息通信?guī)模、消息傳輸干擾等方面的復(fù)雜性日益增加，為時間觸發(fā)通信調(diào)度的設(shè)計及優(yōu)化也帶來了巨大的挑戰(zhàn)。應(yīng)回歸時間觸發(fā)通信調(diào)度設(shè)計的求解能力與性能保障兩個角度，建立合理的評價指標(biāo)體系以開展不同調(diào)度設(shè)計方法的有效性評估。

4.1 求解能力

調(diào)度設(shè)計的求解優(yōu)化重點關(guān)注調(diào)度方法的求解時間T和可求解規(guī)模S，是判定調(diào)度方法是否適用的最根本指標(biāo)。

求解時間是調(diào)度方法開始運行到結(jié)束運行的時間跨度，可表征調(diào)度方法的執(zhí)行效率。受限于求解器自身運算速度或者迭代搜索策略設(shè)置等因素影響，可能存在調(diào)度算法長時間運算而無法獲得封閉解的情況，考慮到這無法滿足工業(yè)實際應(yīng)用需求，對求解時間加上限約束T≤Th，典型可取Th=10 h等[11]。求解時間達(dá)到該上限而仍未獲得封閉解則可等價認(rèn)為此時無法調(diào)度，所以應(yīng)注意結(jié)束運行時并不一定能夠獲得可行調(diào)度解。

可求解規(guī)模具體通過網(wǎng)絡(luò)負(fù)載體現(xiàn)，強(qiáng)調(diào)在相同網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)的基礎(chǔ)上，增加消息條數(shù)以提高網(wǎng)絡(luò)負(fù)載，判斷調(diào)度方法在求解時間上限范圍內(nèi)能否獲得封閉解，或者統(tǒng)計能得到封閉解時所對應(yīng)的最大平均負(fù)載[11]。假設(shè)網(wǎng)絡(luò)輸出端口總數(shù)為Nport，且有Nr條消息流經(jīng)端口τr，記作{f1,f2,…,fNr}，則網(wǎng)絡(luò)平均負(fù)載

(13)

4.2 傳輸延遲

調(diào)度設(shè)計的性能優(yōu)化重點關(guān)注調(diào)度結(jié)果對系統(tǒng)實時性的影響[26]。消息在網(wǎng)絡(luò)傳輸過程中的端到端延遲是一項重要衡量依據(jù)，顯然消息在規(guī)定的截止期限內(nèi)越快到達(dá)目的節(jié)點，則網(wǎng)絡(luò)系統(tǒng)的實時性保障潛力越強(qiáng)。

fi,j,lasti,j·offset-fi,j,firsti,j·offset

(14)

式中：firsti,j,lasti,j分別表示fi在傳輸路徑pi,j上的第一個輸出端口和最后一個輸出端口。

(15)

RC的服務(wù)曲線受到TT強(qiáng)制搶占的影響，有

(16)

(17)

通過對比RC消息最壞延遲與截止期限的相對大小關(guān)系，即可進(jìn)行消息是否滿足實時要求的基本判斷，并可在實時要求保障條件下進(jìn)一步計算消息傳輸時間裕量開展評價分析[1]。

在此基礎(chǔ)上，可以分別計算TT消息和RC消息的端到端最壞延遲DTT和DRC的平均值以反映調(diào)度設(shè)計對延遲影響的統(tǒng)計特征。

4.3 調(diào)度模式

背靠背[7]和多孔[29]兩種調(diào)度模式的不同也會極大影響系統(tǒng)的實時性能。圖3以不同直線表示不同端口，不同色塊表示不同TT消息調(diào)度窗口，給出了兩種調(diào)度模式的對比。背靠背模式下TT消息在周期內(nèi)緊密排列，RC消息有較長的完整傳輸時間窗口；多孔模式下TT消息在周期內(nèi)分散排列，RC消息可利用TT間隔迅速響應(yīng)。

圖3 時間觸發(fā)通信調(diào)度模式

對于調(diào)度模式的評價指標(biāo)可統(tǒng)一表征為TT窗口的均勻程度ζTT?？紤]HPr內(nèi)流經(jīng)τr的TT幀個數(shù)

(18)

這些幀按時間順序排列從而構(gòu)成有序集合{f1,f2,…,fNfr}，將幀fi與下一幀的孔隙間隔記為θi，則有

θi=fi+1·offset-fi·offset-fi·length

(19)

特殊地

θNfr=HPr+f1·offset-fNfr·offset-

fNfr·length

(20)

此時，TT調(diào)度窗口孔隙間隔的標(biāo)準(zhǔn)差

(21)

由于所有幀間隔之和為定值

(22)

可推導(dǎo)得到λr取值范圍

(23)

當(dāng)

{θi}={0,0,…,φr}

(24)

時，λr取最大值，對應(yīng)于完全緊密調(diào)度。當(dāng)

(25)

時，λr取最小值，對應(yīng)于均勻多孔調(diào)度。為便于TT窗口均勻程度概念直觀理解，即ζTT越大，程度越高，考慮λr為成本型指標(biāo)，對其進(jìn)行歸一化處理，并綜合全網(wǎng)端口有

(26)

5 實驗分析

5.1 案例設(shè)計

考慮一個典型工業(yè)規(guī)模下的組網(wǎng)案例[12]，拓?fù)浣Y(jié)構(gòu)如圖4所示，由10個端系統(tǒng)和7個交換機(jī)構(gòu)成。設(shè)計8種不同規(guī)模流量配置的實驗案例，其TT/RC消息條數(shù)NTT/RC、骨干網(wǎng)絡(luò)負(fù)載率STT/RC以及網(wǎng)絡(luò)總負(fù)載S如表2所示。其中，消息參數(shù)配置采用隨機(jī)方法生成，源節(jié)點和目的節(jié)點從拓?fù)浣Y(jié)構(gòu)端系統(tǒng)列表中隨機(jī)選取，消息幀長在[127,1 538]bytes內(nèi)隨機(jī)選擇，且TT周期和RC帶寬分配間隔在[2,128]ms內(nèi)按照2的冪次率隨機(jī)生成；消息傳輸路徑結(jié)合最短路徑算法和流量均衡策略進(jìn)行自動分配，以避免因為某條鏈路或某個區(qū)域過于擁堵，而出現(xiàn)系統(tǒng)無法調(diào)度求解或調(diào)度性能極差等極端情況；各案例采用相同RC配置信息，以充分體現(xiàn)TT調(diào)度設(shè)計對RC通信延遲影響。

表2 實驗案例配置

圖4 工業(yè)規(guī)模組網(wǎng)案例

為有效評價調(diào)度方法性能，在Eclipse環(huán)境下集成SMT求解器Z3和MIP求解器Gurobi，搭建綜合調(diào)度設(shè)計平臺，開發(fā)實現(xiàn)基于SMT、MIP、GA以及RL的設(shè)計方法，并分別應(yīng)用各種方法針對上述各實驗案例進(jìn)行調(diào)度設(shè)計與結(jié)果統(tǒng)計對比。

5.2 求解能力對比

調(diào)度方法基本求解能力體現(xiàn)于求解時間和可求解規(guī)模。由于案例設(shè)計中已給出流量規(guī)模，且不同調(diào)度方法能否求解可通過求解時間是否達(dá)到允許上界進(jìn)行統(tǒng)一表征，故此處僅給出不同案例配置下的求解時間對比，如圖5所示。

圖5 不同調(diào)度方法求解時間對比

對于規(guī)模較小的配置情況，SMT和MIP方法應(yīng)用成熟求解器可以在1 min內(nèi)快速完成調(diào)度設(shè)計，GA和RL方法相對時間較長，但仍可在20 min 內(nèi)完成調(diào)度求解。隨著消息條數(shù)增加，SMT方法最先無法完成調(diào)度，在本實驗研究過程中最多可調(diào)度180條TT消息；MIP方法借助于Gurobi的強(qiáng)運算能力，具有優(yōu)于SMT的可求解規(guī)模，但其求解時間隨消息條數(shù)增多而急劇增加，在時間上限內(nèi)最多可調(diào)度300條TT消息;GA和RL的求解能力逐漸凸顯，尤其RL可以實現(xiàn)更快速的調(diào)度設(shè)計。當(dāng)TT消息條數(shù)達(dá)到400時，僅有GA和RL方法可以進(jìn)行調(diào)度設(shè)計，其求解時間分別為4.5 h和30 min。

此外，應(yīng)注意SMT和MIP方法可得到穩(wěn)定的調(diào)度設(shè)計，即相同配置情況下多次運行結(jié)果高度一致。而GA和RL方法需要搜索迭代，具有一定的隨機(jī)性，故相同配置情況下多次運行結(jié)果存在明顯差異，且求解時間與設(shè)置的迭代次數(shù)正相關(guān)。

5.3 傳輸延遲對比

為全面對比不同調(diào)度算法對消息網(wǎng)絡(luò)傳輸延遲的影響，對各算法下TT端到端延遲和RC最壞端到端延遲進(jìn)行統(tǒng)計，如圖6所示。其中SMT方法和MIP無法支持所有案例配置，僅給出其所支持配置情況統(tǒng)計結(jié)果。

針對TT延遲，不同調(diào)度方法對比如圖6(a)所示。SMT方法僅給出可行調(diào)度方案，而沒有優(yōu)化策略，故其TT延遲遠(yuǎn)高于其他調(diào)度方法，在規(guī)模較小的配置情況下也達(dá)到毫秒級別。MIP以TT延遲最優(yōu)為目標(biāo)進(jìn)行優(yōu)化調(diào)度設(shè)計，故其TT延遲明顯優(yōu)于其他調(diào)度方法；并且隨網(wǎng)絡(luò)規(guī)模擴(kuò)大TT延遲保持在200 μs附近小幅波動而未體現(xiàn)明顯增加趨勢，這是由于實驗配置中TT帶寬占比在20%以下，MIP調(diào)度方法可在各端口處找到合適的時間窗口，保證TT及時轉(zhuǎn)發(fā)傳輸。GA和RL方法的統(tǒng)計曲線重合度很高，在TT條數(shù)不超過200條的較小規(guī)模配置情況下，其延遲明顯低于SMT方法且略高于MIP方法；在中等規(guī)模配置情況下，會隨網(wǎng)絡(luò)規(guī)模擴(kuò)大而增加但仍可保證亞毫秒級別；在TT條數(shù)超過300條的大規(guī)模配置情況下也可保證延遲不超過1.5 ms。

圖6 不同調(diào)度方法傳輸延遲對比

針對RC延遲，不同調(diào)度方法對比如圖6(b)所示。由于RC延遲受到高優(yōu)先級TT流量影響，故不同調(diào)度方法下的RC統(tǒng)計曲線均體現(xiàn)出隨TT規(guī)模擴(kuò)大而增加的整體趨勢。SMT和MIP 兩種算法下RC最壞端到端延遲分布基本相同，這是由于2種算法均采用背靠背調(diào)度策略，可用于RC傳輸?shù)腡T調(diào)度窗口間隔相似。GA和RL方法在調(diào)度過程中考慮以RC延遲為優(yōu)化目標(biāo)調(diào)整調(diào)度策略，較SMT方法和MIP方法具有明顯的RC傳輸優(yōu)勢，平均優(yōu)化程度分別可達(dá)到7.97%和12.35%。

5.4 調(diào)度模式對比

調(diào)度模式通過TT窗口均勻程度ζTT反映，不同實驗案例配置下各種調(diào)度方法的ζTT以及TT和RC平均端到端延遲DTT/RC(ms)如表2所示，其中“—”對應(yīng)表示該案例配置下該調(diào)度算法無法求解?？梢园l(fā)現(xiàn)SMT和MIP方法的ζTT較GA和RL方法更小，這表明前兩者更傾向于背靠背調(diào)度模式而后兩者更傾向于多孔調(diào)度模式。注意即使背靠背調(diào)度模式下，TT窗口間也會天然存在圖1所示消息幀周期傳輸所帶來的孔隙，所以SMT和MIP 兩種算法的ζTT并不是一味偏向于較小的數(shù)值，此處僅以相對大小給出調(diào)度模式的傾向性。

在此基礎(chǔ)上，為進(jìn)一步直觀展示ζTT對流量傳輸延遲的影響，利用表3數(shù)據(jù)繪制4種調(diào)度方法下的TT窗口均勻程度與傳輸延遲關(guān)系圖，如圖7所示。藍(lán)色折線對應(yīng)于TT流量，可以發(fā)現(xiàn)ζTT與DTT無明顯相關(guān)性，這是由于ζTT以端口為對象，分析特定端口處所有TT幀的窗口排布，而DTT以消息為對象，分析特定消息在其傳輸路徑上的調(diào)度時刻。紅色折線對應(yīng)于RC流量，從圖7(a)至圖7(f)中均可觀察到DRC隨ζTT增加呈先減小后增加的趨勢，且存在明顯轉(zhuǎn)折點保證DRC更小，這說明較背靠背調(diào)度或均勻調(diào)度而言，TT窗口孔隙適度的調(diào)度更利于RC流量在網(wǎng)絡(luò)中的傳輸；圖7(g)～圖7(h)的折線雖然僅有增加的趨勢，但也符合上述結(jié)論。

表3 不同調(diào)度方法調(diào)度模式對比

圖7 TT窗口均勻程度與傳輸延遲

6 結(jié) 論

近年來，航電系統(tǒng)對數(shù)據(jù)的實時通信要求逐漸提高，時間觸發(fā)通信技術(shù)憑借其良好的實時性能保障機(jī)制得到廣泛關(guān)注，但同時也帶來了調(diào)度設(shè)計的復(fù)雜性。本文從此角度出發(fā)，分析基于約束引導(dǎo)與基于強(qiáng)化學(xué)習(xí)的不同調(diào)度方法的求解能力與性能保障，主要工作和結(jié)論如下。

1)總結(jié)了時間觸發(fā)通信模型，并針對TTE網(wǎng)絡(luò)分別基于SMT、MIP、GA和RL等方法設(shè)計了時間觸發(fā)通信調(diào)度模型。

2)建立了合理的評價指標(biāo)體系以開展時間觸發(fā)調(diào)度設(shè)計評估，典型包括求解時間、可求解規(guī)模、TT和RC流量端到端延遲以及TT窗口均勻程度，并給出了應(yīng)用網(wǎng)絡(luò)演算進(jìn)行最壞傳輸延遲計算的方法。

3)通過工業(yè)組網(wǎng)案例對上述通信調(diào)度模型進(jìn)行對比評價分析，SMT方法僅可對小規(guī)模案例提供可行調(diào)度方案，不具備優(yōu)化設(shè)計能力；MIP方法優(yōu)先確保TT傳輸，可適用于中小規(guī)模案例；GA和RL方法具有明顯RC延遲優(yōu)勢，并能完成大規(guī)模案例調(diào)度設(shè)計。

未來機(jī)載網(wǎng)絡(luò)時間觸發(fā)通信調(diào)度優(yōu)化設(shè)計的研究重點與發(fā)展趨勢可能包括以下幾個方面：

1)進(jìn)行增量式調(diào)度設(shè)計，以提高調(diào)度求解速度和可求解規(guī)模，并適應(yīng)系統(tǒng)增量升級發(fā)展需要。

2)探尋TT窗口均勻程度與RC延遲的復(fù)雜關(guān)系，以有效引導(dǎo)調(diào)度優(yōu)化方向。

3)聯(lián)合系統(tǒng)應(yīng)用層的時間觸發(fā)通信調(diào)度優(yōu)化設(shè)計。