機載網(wǎng)絡(luò)時間觸發(fā)通信調(diào)度設(shè)計優(yōu)化與評價方法

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

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

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

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

目前，通信調(diào)度設(shè)計多基于有約束引導(dǎo)的啟發(fā)式方法或者求解方法進行，通過設(shè)置網(wǎng)絡(luò)拓撲和流量關(guān)系等約束，生成滿足約束的TT調(diào)度表，典型包括可滿足性模理論[5-8](Satisfiability Modulo Theories，SMT)、混合整數(shù)規(guī)劃[9-12](Mixed Integer Programming，MIP)以及啟發(fā)式算法[13-16]，這些方法在求解過程中具有不同的解算速度和優(yōu)化能力，但一般都比較耗時。采用強化學(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)性選擇與進一步發(fā)展，應(yīng)結(jié)合調(diào)度求解能力與性能保障兩個角度，從求解時間、可求解規(guī)模以及實時通信影響等多個維度開展對比分析研究。

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

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

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

時間觸發(fā)通信著重滿足安全關(guān)鍵任務(wù)中消息傳輸?shù)膶崟r性要求，并致力于保證數(shù)據(jù)傳輸?shù)拇_定性與可靠性，在機載網(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ā)通信進行調(diào)度設(shè)計，各個節(jié)點設(shè)備根據(jù)固定時刻驅(qū)動網(wǎng)絡(luò)上的所有活動，可以有效保證航電系統(tǒng)對信息交互的實時性和確定性要求。TTE、TSN等新一代交換式互連技術(shù)更是憑借著高帶寬利用率、可擴展組網(wǎng)規(guī)模等優(yōu)勢，能夠很好地滿足機載系統(tǒng)發(fā)展需求。

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

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

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

考慮時間觸發(fā)通信的具體過程，當多條流量在交換網(wǎng)絡(luò)中傳輸綜合時，TT流量在全局時鐘同步機制基礎(chǔ)上，通過靜態(tài)規(guī)劃傳輸時間窗口并離線生成時間調(diào)度表，可以實現(xiàn)無沖突傳輸，從而有效改善時間確定性和傳輸可靠性。RC流量遵循事件觸發(fā)通信機制，缺乏事先規(guī)劃好的傳輸時間窗口，勢必會與其它事件觸發(fā)消息競爭端口輸出，導(dǎo)致傳輸過程存在很大的不確定性；而且其與更高優(yōu)先級的TT流量在傳輸過程中相遇時，采取避讓(集成)策略，將進一步增加傳輸不確定性。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消息在傳輸過程中受到嚴格時間約束，可以根據(jù)網(wǎng)絡(luò)拓撲及配置參數(shù)表示約束條件，將其轉(zhuǎn)換成SMT一階邏輯形式，并利用SMT求解器求解，從而實現(xiàn)TT通信調(diào)度設(shè)計。文獻[5]首先提出這種基于SMT的調(diào)度設(shè)計方法，其針對多跳網(wǎng)絡(luò)給出了背靠背傳輸模式下的調(diào)度約束條件，并通過增量化的方式提高了求解速度；進一步，為了兼顧RC消息傳輸實時性，將TT消息間隔視作孔隙，提出了多孔傳輸模式下的調(diào)度求解方法。文獻[6]改進了傳統(tǒng)基于靜態(tài)SMT的TT調(diào)度方法，以獲得最佳離散間隔來減小RC的端到端延遲。

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

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

基于MIP方法進行調(diào)度設(shè)計也應(yīng)滿足與SMT方法相似的約束條件。但應(yīng)注意兩種方法所針對的求解域不同，MIP方法無法實現(xiàn)SMT方法中無沖突約束的Either-Or語句，所以需對式(1)進行轉(zhuǎn)換表述，針對端口τr處的任意2條TT消息fi、fk引入二進制決策變量β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)化目標是最小化消息平均端到端傳輸延遲，即

(3)

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

2.3 啟發(fā)式方法

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

基于啟發(fā)式方法進行調(diào)度設(shè)計同樣也應(yīng)滿足與前文一致的約束條件，其公式化描述可以直接借鑒前文經(jīng)驗。值得注意的是SMT或MIP方法可直接應(yīng)用相應(yīng)的求解器，在設(shè)定求解變量、輸入約束條件后進行黑盒運算，便能獲得滿足約束的調(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)重。當不可調(diào)度時，ωTT/RC取較大數(shù)值以保證搜索快速向可行區(qū)域推進；當可調(diào)度時，ωTT=0以保證搜索向RC延遲更小的性能優(yōu)化方向推進。

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

基于約束引導(dǎo)的調(diào)度設(shè)計應(yīng)用于工業(yè)規(guī)模機載網(wǎng)絡(luò)往往存在耗時較長的缺陷，為實現(xiàn)工業(yè)規(guī)模下機載網(wǎng)絡(luò)的快速調(diào)度設(shè)計，可采用基于強化學(xué)習(xí)的設(shè)計方法。強化學(xué)習(xí)通過與動態(tài)環(huán)境的即時交互獲取狀態(tài)信息，并反饋強化信號對所采取的行動進行評價，經(jīng)過不斷學(xué)習(xí)和選擇實現(xiàn)最優(yōu)策略。將其應(yīng)用于時間觸發(fā)通信調(diào)度設(shè)計，需要首先進行適應(yīng)性定義，例如文獻[17]將狀態(tài)state定義為輸出端口當前的消息排布方式，將動作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)先進行初始搜索，并剪掉明顯不能找到結(jié)果的分支加快搜索。

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

(10)

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

(11)

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

(12)

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

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

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

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

4.1 求解能力

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

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

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

(13)

4.2 傳輸延遲

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

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

(14)

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

(15)

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

(16)

(17)

通過對比RC消息最壞延遲與截止期限的相對大小關(guā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)度模式的評價指標可統(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)度窗口孔隙間隔的標準差

(21)

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

(22)

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

(23)

當

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

(24)

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

(25)

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

(26)

5 實驗分析

5.1 案例設(shè)計

考慮一個典型工業(yè)規(guī)模下的組網(wǎng)案例[12]，拓撲結(jié)構(gòu)如圖4所示，由10個端系統(tǒng)和7個交換機構(gòu)成。設(shè)計8種不同規(guī)模流量配置的實驗案例，其TT/RC消息條數(shù)NTT/RC、骨干網(wǎng)絡(luò)負載率STT/RC以及網(wǎng)絡(luò)總負載S如表2所示。其中，消息參數(shù)配置采用隨機方法生成，源節(jié)點和目的節(jié)點從拓撲結(jié)構(gòu)端系統(tǒng)列表中隨機選取，消息幀長在[127,1 538]bytes內(nèi)隨機選擇，且TT周期和RC帶寬分配間隔在[2,128]ms內(nèi)按照2的冪次率隨機生成；消息傳輸路徑結(jié)合最短路徑算法和流量均衡策略進行自動分配，以避免因為某條鏈路或某個區(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)用各種方法針對上述各實驗案例進行調(diào)度設(shè)計與結(jié)果統(tǒng)計對比。

5.2 求解能力對比

調(diào)度方法基本求解能力體現(xiàn)于求解時間和可求解規(guī)模。由于案例設(shè)計中已給出流量規(guī)模，且不同調(diào)度方法能否求解可通過求解時間是否達到允許上界進行統(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的強運算能力，具有優(yōu)于SMT的可求解規(guī)模，但其求解時間隨消息條數(shù)增多而急劇增加，在時間上限內(nèi)最多可調(diào)度300條TT消息;GA和RL的求解能力逐漸凸顯，尤其RL可以實現(xiàn)更快速的調(diào)度設(shè)計。當TT消息條數(shù)達到400時，僅有GA和RL方法可以進行調(diào)度設(shè)計，其求解時間分別為4.5 h和30 min。

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

5.3 傳輸延遲對比

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

針對TT延遲，不同調(diào)度方法對比如圖6(a)所示。SMT方法僅給出可行調(diào)度方案，而沒有優(yōu)化策略，故其TT延遲遠高于其他調(diào)度方法，在規(guī)模較小的配置情況下也達到毫秒級別。MIP以TT延遲最優(yōu)為目標進行優(yōu)化調(diào)度設(shè)計，故其TT延遲明顯優(yōu)于其他調(diào)度方法；并且隨網(wǎng)絡(luò)規(guī)模擴大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ī)模擴大而增加但仍可保證亞毫秒級別；在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ī)模擴大而增加的整體趨勢。SMT和MIP 兩種算法下RC最壞端到端延遲分布基本相同，這是由于2種算法均采用背靠背調(diào)度策略，可用于RC傳輸?shù)腡T調(diào)度窗口間隔相似。GA和RL方法在調(diào)度過程中考慮以RC延遲為優(yōu)化目標調(diào)整調(diào)度策略，較SMT方法和MIP方法具有明顯的RC傳輸優(yōu)勢，平均優(yōu)化程度分別可達到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ǔ)上，為進一步直觀展示ζTT對流量傳輸延遲的影響，利用表3數(shù)據(jù)繪制4種調(diào)度方法下的TT窗口均勻程度與傳輸延遲關(guān)系圖，如圖7所示。藍色折線對應(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ù)憑借其良好的實時性能保障機制得到廣泛關(guān)注，但同時也帶來了調(diào)度設(shè)計的復(fù)雜性。本文從此角度出發(fā)，分析基于約束引導(dǎo)與基于強化學(xué)習(xí)的不同調(diào)度方法的求解能力與性能保障，主要工作和結(jié)論如下。

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

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

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

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

1)進行增量式調(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è)計。