基于負載均衡的大規(guī)模TTE消息調(diào)度表生成方法

葉 帆，陳銀超，王 濤，季袁冬，羅懋康,3，江秀強

(1.四川大學(xué)空天科學(xué)與工程學(xué)院, 成都 610207；2.航空工業(yè)成都飛機設(shè)計研究所，成都 610073；3.四川大學(xué)數(shù)學(xué)學(xué)院，成都 610064)

1 引 言

分布式航電系統(tǒng)在航空航天領(lǐng)域具有廣闊的應(yīng)用前景[1,2].此類系統(tǒng)要求機載網(wǎng)絡(luò)必須具備高實時性、高容錯性、高確定性及高帶寬等特性.時間觸發(fā)以太網(wǎng)(Time-Triggered Ethernet, TTE)被認為是未來機載網(wǎng)絡(luò)的理想解決方案[2,3].時間觸發(fā)以太網(wǎng)基于全局同步的時鐘協(xié)議實現(xiàn)高確定性、高實時性的時間觸發(fā)通信，并根據(jù)離線確定的靜態(tài)通信調(diào)度表來傳輸時間觸發(fā)消息.當(dāng)前，針對TTE調(diào)度表生成方法雖然已有較多的研究，但尚未形成統(tǒng)一標(biāo)準，仍需深入研究[4,5].

針對機載網(wǎng)絡(luò)的大規(guī)模數(shù)據(jù)調(diào)度需求，本文研究TTE消息的路徑規(guī)劃和調(diào)度方法.文獻[6-9]設(shè)計了基于不同規(guī)則的靜態(tài)優(yōu)先級調(diào)度方法.這些方法大多采用TTE現(xiàn)有的AS6802標(biāo)準[2]給出的星型、雪花型拓撲，消息路徑唯一，且使用最短路徑策略生成消息路徑，規(guī)則確定、復(fù)雜度低，對大規(guī)模消息調(diào)度問題可行性好、計算時間也少，但是，這些方法沒有考慮到多徑及端系統(tǒng)規(guī)模超過50個[8]的復(fù)雜拓撲等情形，在實際應(yīng)用中容易出現(xiàn)因最短路徑上的負載過大而造成消息阻塞的問題，無法進行后續(xù)的時序調(diào)度.

負載均衡在路徑規(guī)劃和時序規(guī)劃問題中的應(yīng)用越來越多[10-13].文獻[10]構(gòu)建了一個考慮負載的路徑代價函數(shù)，利用深度優(yōu)先搜索算法尋找最小代價值的路由.文獻[11]基于K最短路徑(K shortest paths, KSP)算法計算各業(yè)務(wù)的備選路徑，在保證待選路徑的較優(yōu)性的前提下利用遺傳算法優(yōu)選出盡可能使全網(wǎng)負載均衡的業(yè)務(wù)路徑組合.文獻[12]則研究了時間觸發(fā)(Time-Triggered, TT)流量路徑規(guī)劃和時序規(guī)劃對速率受限(Rate Constrained, RC)流量實時性的影響，并根據(jù)KSP算法和鏈路最大負載最小的原則進行路徑規(guī)劃.但是，就我們所知，能夠服務(wù)于大規(guī)模數(shù)據(jù)傳輸需求和負載均衡要求的機載網(wǎng)絡(luò)的高效數(shù)據(jù)調(diào)度方法還未出現(xiàn)，有待進一步研究.

針對復(fù)雜拓撲條件下機載網(wǎng)絡(luò)的大規(guī)模數(shù)據(jù)高效傳輸問題，本文提出了一種基于負載均衡思想的TTE消息調(diào)度表生成方法.該方法主要有以下幾個特點：

(i)考慮了復(fù)雜網(wǎng)絡(luò)拓撲.與星型網(wǎng)絡(luò)及雪花型網(wǎng)絡(luò)等相比，本方法中的消息路徑并不唯一；

(ii)考慮了消息長度的影響.相比單個時隙傳輸，本方法具有更好的實時性；

(iii)設(shè)計了基于負載均衡和靜態(tài)優(yōu)先級的調(diào)度分配方法.

此外，本方法具有較低的算法復(fù)雜度，適用于對大規(guī)模消息數(shù)據(jù)進行高效地時序規(guī)劃.

2.1 TTE消息傳輸

TTE支持三種類型的流量在網(wǎng)絡(luò)中傳輸，即TT流量, RC流量和盡力而為(Best-Effort, BE)流量[2-6].針對機載網(wǎng)絡(luò)的實際需求，本文僅考慮TT流量的傳輸.TT流量根據(jù)各網(wǎng)絡(luò)節(jié)點所加載的靜態(tài)調(diào)度表中預(yù)定義的時間進行傳輸，由全局同步時間觸發(fā)，具有確定的延遲和抖動.該流量常被用于具有嚴格確定性和實時性要求的情形，能夠滿足未來機載網(wǎng)絡(luò)對大規(guī)模數(shù)據(jù)傳輸確定性和時效性的需求.

時間觸發(fā)以太網(wǎng)在空間和時間維度上調(diào)度網(wǎng)絡(luò)流量，使得網(wǎng)絡(luò)具有確定性，即確定數(shù)據(jù)包何時在何鏈路上傳輸，以及何時最終到達其目的端口.這種調(diào)度在空間維度上體現(xiàn)為路徑規(guī)劃，需要為每個數(shù)據(jù)包找到一條合適的路由，即由鏈路和交換機組成的網(wǎng)絡(luò)路徑；在時間維度上是時序規(guī)劃，需要沿著每個數(shù)據(jù)包路由的鏈路分配時隙(slot)，每個時隙僅保留用于所配置幀的傳輸.具體的傳輸過程如圖1所示.

路徑規(guī)劃需要確定消息傳輸所經(jīng)過的網(wǎng)絡(luò)節(jié)點.在圖1中，Sender為發(fā)送端，Switch為交換機，Receiver為接收端.此外，還有兩條消息，其中淺灰色的TT消息周期為2ms, 從Sender1傳輸?shù)絉eceiver，傳輸路徑為

Sender1→Switch1→Switch3→Receiver，

深灰色的TT消息周期為3ms，從Sender2傳輸?shù)絉eceiver，傳輸路徑為

Sender2→Switch2→Switch3→Receiver.

消息在數(shù)據(jù)流鏈路上傳輸過程中的時序規(guī)劃就是確定消息間的先后順序.在圖1中，兩個TT消息(深灰色和淺灰色所示)同時在Switch3到Receiver的鏈路上傳輸，消息間的先后關(guān)系以它們的集群周期為基準.因為淺灰色TT消息和深灰色TT消息的周期分別為3 ms和2 ms，其集群周期，即消息周期的最小公倍數(shù)(least common multiple, LCM)為6 ms.因此，可以根據(jù)消息傳輸?shù)拈_始時刻與集群周期的開始時刻間的時間間隔的長短來衡量消息的先后.

圖1 TT消息傳輸示意圖

2.2 TTE消息調(diào)度模型

與傳統(tǒng)的星型及雪花型網(wǎng)絡(luò)拓撲不同，實際的機載網(wǎng)絡(luò)規(guī)模大、拓撲結(jié)構(gòu)復(fù)雜.為了驗證大規(guī)模、非單一路徑網(wǎng)絡(luò)拓撲下的算法性能，本文以TTE多跳網(wǎng)絡(luò)拓撲[13]為基礎(chǔ)，將三組多跳網(wǎng)絡(luò)拓撲互聯(lián)組合形成如圖2所示的TTE多跳互聯(lián)網(wǎng)絡(luò).該網(wǎng)絡(luò)中有終端系統(tǒng)(End System, ES)及網(wǎng)絡(luò)交換機(Network Switch, NS)這兩種節(jié)點角色，各節(jié)點之間通過全雙工鏈路進行連接.在圖2中，ES與NS之間的雙向箭頭代表矩形中各ES與NS之間均存在全雙工鏈路，只不過為了表示清晰在此簡化為一條雙向箭頭.在各個節(jié)點中，算法將加載離線生成調(diào)度表.根據(jù)調(diào)度表中的派發(fā)時刻和接收時刻, 算法對TT消息進行傳輸，轉(zhuǎn)發(fā)行為只允許發(fā)生在網(wǎng)絡(luò)交換機中，全雙工鏈路允許雙向通信.

圖2 TTE多跳互聯(lián)網(wǎng)絡(luò)拓撲

將網(wǎng)絡(luò)模型建模為有向圖G=[V,L]，其中V為網(wǎng)絡(luò)節(jié)點集合，V=ES∪NS，L為網(wǎng)絡(luò)中數(shù)據(jù)流鏈路的集合.數(shù)據(jù)流鏈路是兩個節(jié)點間的定向通信連接，lpk=[vp,vk]∈L，vp,vk∈V.

定義網(wǎng)絡(luò)拓撲矩陣G，

(1)

其中，存在vi,vj∈V，使得當(dāng)數(shù)據(jù)流鏈路lij存在時網(wǎng)絡(luò)拓撲矩陣元素Gij值為1，當(dāng)數(shù)據(jù)流鏈路lij不存在時網(wǎng)絡(luò)拓撲矩陣元素Gij值為0.

定義集群周期為消息周期的最小公倍數(shù).由于TT消息均為周期性消息，調(diào)度過程隨LCM呈現(xiàn)周期性重復(fù).因此，本文所討論的調(diào)度表生成問題只考慮一個LCM內(nèi)的消息調(diào)度即可.

TT消息幀格式符合ARINC 664p7規(guī)范，消息通過幀的有效載荷進行傳輸.本文假設(shè)所有TT消息為周期性消息，且不考慮打包和分段.將TT消息建模為如下的6元組形式，通過該6元組能夠完整描述TT消息的傳輸行為：

mi={mi.period,mi.length,mi.source,mi.dest,

mi.path,mi.offset}

(2)

其中mi.period表示消息周期對應(yīng)的時間長度，mi.length表示消息長度引發(fā)的傳輸時間對應(yīng)的時間長度，mi.source表示消息傳輸源節(jié)點，mi.dest表示消息傳輸目的節(jié)點，mi.path表示消息傳輸路徑，為數(shù)據(jù)流鏈路的有序序列，mi.offset表示消息相對集群周期起始時間的偏移量.為了將時序規(guī)劃問題簡化為整數(shù)規(guī)劃問題，我們使用時隙[5]作為調(diào)度表的時間單位對消息的周期和消息傳輸時間進行整數(shù)化處理，使得mi.period為消息周期對應(yīng)的時隙數(shù)，mi.length為消息長度引發(fā)的傳輸時間對應(yīng)的時隙數(shù).

本文主要考慮如何以確定性的優(yōu)化規(guī)則分配大規(guī)模消息數(shù)據(jù)的傳輸路徑和傳輸時隙.為了研究方便，并結(jié)合實際應(yīng)用[2-6]，我們作如下的假設(shè)：

(i)網(wǎng)絡(luò)中所有消息都為周期性的TT消息；

(ii)網(wǎng)絡(luò)中所有鏈路資源都可用，交換機采用存儲轉(zhuǎn)發(fā)方式；

(iii)只考慮TT消息單播的情形；

(iv)調(diào)度表設(shè)計時以時隙為單位對消息周期、消息傳輸時間進行化整；

(v)假設(shè)網(wǎng)絡(luò)中每次發(fā)送的TT消息都能封裝在一個幀里，且一個幀只傳輸一條消息，不考慮幀的打包和分段.

3 基于負載均衡的調(diào)度表生成方法

網(wǎng)絡(luò)消息的路徑規(guī)劃過程根據(jù)消息的源節(jié)點mi.source，目的節(jié)點mi.dest和網(wǎng)絡(luò)拓撲G確定各個消息的傳輸路徑mi.path.該路徑為數(shù)據(jù)流鏈路的有序序列{l1,l2,…,ln}，具體實現(xiàn)過程如圖3所示.首先，我們使用Yen’s KSP算法[14]生成各個消息的待選路徑集合，然后根據(jù)規(guī)則對消息進行排序，最后按照排序順序依次為消息從待選路徑集合中選擇網(wǎng)絡(luò)鏈路最小負載最小的路徑，加入規(guī)劃路徑集合.

圖3 路徑規(guī)劃流程圖

3.1.1 負載計算公式 定義數(shù)據(jù)流鏈路lkp上的負載B的計算公式為

(3)

其中，mi.path為消息傳輸路徑，mi.period為消息周期對應(yīng)的時隙個數(shù)，mi.length為消息長度引發(fā)的傳輸時間對應(yīng)的時隙個數(shù).網(wǎng)絡(luò)最小鏈路利用率Bmin為

(4)

其中k,p為網(wǎng)絡(luò)節(jié)點vk,vp.

3.1.2 排序規(guī)則 生成待選路徑后，為了選出負載均衡的路徑結(jié)果，我們首先需要根據(jù)規(guī)則對消息進行排序.本文考慮消息長度帶來的影響，定義規(guī)則為消息長度越長，排序越靠前，優(yōu)先進行路徑選擇；消息長度越短越靠后，在已選路徑的負載基礎(chǔ)上進行路徑選擇，相同長度的消息按照原本順序進行排序.

3.1.3 選擇過程 為了達到負載均衡的目的，本文選擇使得消息路徑中鏈路最小負載最小的路徑作為路徑規(guī)劃的結(jié)果.由于某些消息的傳輸任務(wù)路徑唯一，導(dǎo)致一些主干鏈路的負載很高且難以緩解，因而設(shè)計鏈路最小負載作為路徑選擇的條件能夠關(guān)注到較小負載的均衡狀況，以達到負載均衡的目的.

3.2 時序規(guī)劃方法

針對大規(guī)模消息的調(diào)度問題，本文設(shè)計了一種靜態(tài)優(yōu)先級調(diào)度方法.與智能優(yōu)化算法相比，該方法的計算時間更少、效率更高.此外，該方法基于規(guī)則，因而具有確定性.對于已知傳輸路徑的消息時序規(guī)劃問題，調(diào)度過程需要確定各個消息在其路徑的各個數(shù)據(jù)流鏈路中的首個數(shù)據(jù)幀的偏移量offsetij(第i個消息在路徑第j個數(shù)據(jù)流鏈路上傳輸時首個消息幀偏移量)，同時還要確定該消息幀傳輸?shù)慕Y(jié)束時刻endij，具體過程為：首先根據(jù)優(yōu)先級評估計算公式計算消息優(yōu)先級，然后按照從小到大的順序?qū)ο⑦M行優(yōu)先級排序，評估值越小時排序越靠前、優(yōu)先級越高，最后根據(jù)優(yōu)先級排序依次按照規(guī)則對消息進行調(diào)度分配.

(i)優(yōu)先級評估值計算.由于優(yōu)先級較高的消息將先進行時序規(guī)劃，較低優(yōu)先級消息的排序會受到已規(guī)劃消息的影響，因而應(yīng)使得較難調(diào)度的消息先進行時序規(guī)劃，較易調(diào)度的消息靠后.鑒于單調(diào)速率算法[15]已證明，根據(jù)消息周期進行優(yōu)先級排序具有最優(yōu)性，消息周期越短，本文綜合考慮消息周期與消息長度對優(yōu)先級排序的影響，消息周期越短，優(yōu)先級越高，消息長度越長，優(yōu)先級越高；反之，消息周期越長，消息長度越長，優(yōu)先級越低.優(yōu)先級評估值pi的計算公式為

(5)

這樣，優(yōu)先級評估值pi越小，消息周期越短、長度越長，優(yōu)先級越高.當(dāng)消息優(yōu)先級評估值相同時，按消息原始順序進行排序.

(ii)調(diào)度規(guī)則.優(yōu)先級排序后，我們將按照優(yōu)先級順序?qū)ο⑦M行調(diào)度.若該消息為鏈路中首個被調(diào)度的消息，則令其集群周期偏移為0，該鏈路中后續(xù)消息將與前一個消息“背靠背”排布進行調(diào)度.若產(chǎn)生沖突，則令該消息后移一個slot，直到無沖突.若無法消除該沖突，則無法生成調(diào)度表.具體規(guī)則如(6)～(8)式所示.

endi,j=offseti,j+mi,length

(6)

(7)

(8)

其中offseti,j表示消息i在其路徑中第j個數(shù)據(jù)流鏈路上的傳輸時刻距離集群周期LCM起始的偏移量，cont(mi.pathj)表示數(shù)據(jù)流鏈路mi.pathj上已規(guī)劃的消息偏移個數(shù)，endi,j表示消息i在其路徑中第j個數(shù)據(jù)流鏈路上傳輸完畢時刻距離集群周期LCM起始的偏移量，delayi,j表示消息i在其路徑中第j個數(shù)據(jù)流鏈路上傳輸?shù)挠布舆t和排隊抖動，該數(shù)據(jù)依據(jù)實際的網(wǎng)絡(luò)物理性能而離線設(shè)定.

4 仿真與分析

4.1 仿真設(shè)置

路徑和時序規(guī)劃仿真實驗的硬件配置CPU為Intel(R)Core(TM)i7-10510U、內(nèi)存16GB，采用MATLAB R2016a進行編程計算，并利用PyCharm Community Edition 2021.1.1 x64開發(fā)平臺進行SMT對比仿真.

仿真采用的網(wǎng)絡(luò)拓撲如圖2所示，包含55個端系統(tǒng)和6個交換機，共61個網(wǎng)絡(luò)節(jié)點，且轉(zhuǎn)發(fā)行為只發(fā)生在交換機上.在仿真程序中，該網(wǎng)絡(luò)拓撲表示為矩陣G61×61的形式，如式(1)所示，矩陣元素Gij為1時節(jié)點i到節(jié)點j間存在數(shù)據(jù)流鏈路lij，矩陣元素為0則表示不存在數(shù)據(jù)流鏈路.

由文獻[11]，我們設(shè)置網(wǎng)絡(luò)鏈路的傳輸速率為100 MB/s，并根據(jù)TTE幀格式(符合ARINC 664p7)設(shè)置幀長為64～1518 B.由文獻[2]，我們設(shè)置消息周期為15、25、30、50、75、150 ms，時隙長度為0.5 ms，并據(jù)此對消息周期和幀長進行取整計算，可得幀長傳輸時隙為1～3 slot，消息周期時隙為30、50、60、100、150、300 slot.在可達的前提下，令消息端口均勻分布，消息傳輸需求示例如表1所示.

表1 消息傳輸需求

為了驗證本文所提方法的有效性和在時間復(fù)雜度方面的性能提升，我們采用傳統(tǒng)的迪杰斯特拉(Dijkstra，DIJ)路徑規(guī)劃算法[6,16]和經(jīng)典的基于滿足性模理論(Satisfiability Modulo Theory, SMT)的時序規(guī)劃方法[5]，并與本文所設(shè)計的基于K短路徑的負載均衡路徑規(guī)劃方法及基于規(guī)則的靜態(tài)優(yōu)先級調(diào)度(Static Priority Scheduling, SPS)方法綜合，得到四種方法組合，并在不同消息規(guī)模下進行對比仿真實驗.這四種方法分別為：DIJ最短路徑算法+SMT時序規(guī)劃方法(DIJ+SMT)，基于K短路徑的負載均衡路徑規(guī)劃方法+SMT時序規(guī)劃方法(KSP+SMT)，DIJ最短路徑算法+基于規(guī)則的靜態(tài)優(yōu)先級調(diào)度方法(DIJ+SPS)，以及基于K短路徑的負載均衡路徑規(guī)劃方法+基于規(guī)則的靜態(tài)優(yōu)先級調(diào)度方法(KSP+SPS).對四個方法組合在不同消息規(guī)模下進行仿真實驗時的具體消息設(shè)置參見表2.

表2 仿真實驗消息設(shè)置

4.2 仿真結(jié)果與分析

4.2.1 仿真結(jié)果 我們以表2中第二組消息為例展示本文方法仿真結(jié)果，DIJ算法與KSP方法的路徑規(guī)劃結(jié)果分別如圖4a和4b所示，兩種方法的時序規(guī)劃結(jié)果如圖5，6所示.圖4展示了部分路徑結(jié)果矩陣Path100×5，其中矩陣行元素為調(diào)度消息序號，列元素為路徑結(jié)果中數(shù)據(jù)流鏈路排列序號，矩陣中的元素代表了傳輸路徑中數(shù)據(jù)流鏈路的序號，0代表無鏈路即無路徑.

圖4 路徑規(guī)劃結(jié)果:(a)DIJ算法路徑矩陣;(b)KSP方法路徑矩陣

可以看出，當(dāng)消息為1～10時，兩種路徑方法結(jié)果相同.這驗證了KSP方法的有效性和正確性.當(dāng)消息為90～100時，KSP方法的數(shù)據(jù)流鏈路路徑與DIJ算法不同.我們以第90個消息為例進行分析.DIJ算法的路徑結(jié)果為數(shù)據(jù)流鏈路1傳輸至數(shù)據(jù)流鏈路97，KSP算法的路徑結(jié)果為數(shù)據(jù)流鏈路53傳輸至數(shù)據(jù)流鏈路149.由于兩個算法第1個消息的路徑結(jié)果均為數(shù)據(jù)流鏈路1傳輸至數(shù)據(jù)流鏈路98，因而對于第90條消息而言，KSP算法緩解了數(shù)據(jù)流鏈路1上的負載.由此，我們可以推斷其他消息的鏈路負載情況，尤其當(dāng)網(wǎng)絡(luò)中鏈路負載不均勻時，DIJ算法中最短路徑的負載難以緩解，更容易出現(xiàn)路徑阻塞的現(xiàn)象.

圖5和6展示了TT消息調(diào)度表，表的橫坐標(biāo)以時隙為單位，表示一個LCM內(nèi)的消息幀排布情況，縱坐標(biāo)表示網(wǎng)絡(luò)中的數(shù)據(jù)流鏈路序號，圖中的黑色小矩形代表各消息已被分配的時隙，通過調(diào)度表能夠確定消息在網(wǎng)絡(luò)中傳輸?shù)穆窂胶蜁r間順序.

圖5 KSP+SMT時序規(guī)劃結(jié)果

圖6 KSP+SPS時序規(guī)劃結(jié)果

由于消息路徑中數(shù)據(jù)流鏈路上的時隙偏移offset決定了調(diào)度表中消息被分配的時隙的位置，因而通過圖7和8中的時隙偏移offset分布直方圖和分布曲線圖可以看出，本文設(shè)計的SPS方法因采用了“背靠背”的排布規(guī)則，比SMT方法時隙偏移offset分布更加集中，更靠近LCM前端，體現(xiàn)在調(diào)度表中消息排列更為緊湊，更好地保證了TT消息傳輸?shù)拇_定性和實時性.

圖7 時隙偏移分布直方圖

4.2.2 評估指標(biāo)與分析 調(diào)度方法的關(guān)鍵評估指標(biāo)包括：計算時間指標(biāo)、延時指標(biāo)和負載指標(biāo).

圖8 時隙偏移分布曲線

上述四種方法在不同規(guī)模的消息數(shù)據(jù)下的計算時間的比較結(jié)果如表3所示，其中每個單元格里的上下兩個數(shù)據(jù)分別是路徑規(guī)劃時間和時序規(guī)劃時間.通過比較可知，路徑規(guī)劃方法的計算時間都是多項式級別的，而SMT方法的計算時間呈現(xiàn)指數(shù)型增長.當(dāng)消息規(guī)模為496時，SMT方法很難得出結(jié)果.SPS方法的計算時間大多較短，且在消息規(guī)模為496時計算時間仍遠小于1 s.因此，相比于DIJ+SMT和KSP+SMT方法，KSP+SPS方法能夠有效減少大規(guī)模消息的計算時間.雖然DIJ算法耗時比KSP方法少，但當(dāng)方法流量不均勻時，DIJ算法更容易出現(xiàn)路徑阻塞的現(xiàn)象，導(dǎo)致調(diào)度表生成失敗.因此，為了保證調(diào)度表生成方法的適應(yīng)性，KSP+SPS方法比DIJ+SPS方法更適用于復(fù)雜拓撲下大規(guī)模消息數(shù)據(jù)傳輸?shù)膱鼍?

表3 計算時間的對比(單位：s)

延時指標(biāo)包括平均延時Da和平均延時百分比Dap.假設(shè)各個消息的傳輸截止時間為其周期.則該指標(biāo)可通過下面兩式進行計算：

(9)

(10)

其中，消息個數(shù)為N，offseti,last為消息傳輸最后一條路徑上的偏移時隙.四種方法在不同規(guī)模消息數(shù)據(jù)下的延時指標(biāo)比較結(jié)果參見表4，可以看到，四種方法的延時百分比相差不大，KSP+SPS方法的表現(xiàn)好于兩種SMT方法，與DIJ+SPS方法基本持平.因此，KSP+SPS方法能夠較好地滿足消息的確定性和實時性需求.

表4 延時指標(biāo)對比

消息負載指標(biāo)包括網(wǎng)絡(luò)鏈路最大負載BDmax、平均負載BDavg、負載標(biāo)準差BDsigm和網(wǎng)絡(luò)鏈路負載分布直方圖，由于網(wǎng)絡(luò)負載之和不變，若鏈路數(shù)量相同則平均負載結(jié)果相同，為了對比方法效果平均負載和負載標(biāo)準差的計算剔除了負載為0的鏈路.兩種路徑規(guī)劃方法在不同消息規(guī)模下的網(wǎng)絡(luò)鏈路最大負載、平均負載和負載標(biāo)準差如表5所示，在消息規(guī)模248和496下的鏈路負載分布直方圖對比結(jié)果如圖9和圖10所示.

表5 網(wǎng)絡(luò)鏈路負載指標(biāo)對比

由表5中的BDmax數(shù)據(jù)可知，對于本文研究的拓撲而言，最短路徑方法和負載均衡方法對于網(wǎng)絡(luò)鏈路最大負載的影響都很小.這是由于某些消息調(diào)度任務(wù)的路徑唯一導(dǎo)致一些主干鏈路上的負載難以緩解.但是，通過負載均衡方法能夠緩解路徑不唯一的消息調(diào)度任務(wù)帶來的負載影響.由表5中的BDavg，BDsigm可以看出，KSP方法的負載平均值和負載標(biāo)準差均小于DIJ算法.這表明KSP方法平均負載更小且負載分布更為均衡.進一步，由圖9和圖10可以看出，綠色的KSP方法較小負載的頻率分布高于紅色的DIJ算法，紅色的DIJ算法較大負載的頻率分布高于或持平綠色的KSP方法，且DIJ算法中負載為0的鏈路也多于KSP方法.可見, 本文所設(shè)計的基于負載均衡的路徑規(guī)劃方法均衡負載的效果較為顯著，能夠較好滿足機載網(wǎng)絡(luò)中非TT消息傳輸?shù)呢撦d需求.

圖9 鏈路負載頻率分布直方圖(消息數(shù)量=496)

圖10 鏈路負載頻率分布直方圖(消息數(shù)量=248)

5 結(jié) 論

未來的機載網(wǎng)絡(luò)拓撲趨于更加復(fù)雜、數(shù)據(jù)量更大，對調(diào)度表生成速度及負載可靠性要求更高.本文提出了一種基于負載均衡的TTE消息調(diào)度表生成方法，該方法結(jié)合消息長度和負載的影響選取負載均衡的路徑規(guī)劃結(jié)果，根據(jù)優(yōu)先級評估值以“背靠背”原則為基礎(chǔ)計算消息的時間偏移，實現(xiàn)了對負載均衡的路徑規(guī)劃與時序規(guī)劃問題的聯(lián)合求解.在平均負載、負載標(biāo)準差方面比傳統(tǒng)的DIJ算法提升了10%以上，改善了鏈路的負載均衡狀況.同時，計算效率比SMT方法提升2到3個數(shù)量級，而延時指標(biāo)與傳統(tǒng)方法則在同一個量級，能保證消息傳輸?shù)膶崟r性.

綜上，該方法在改善鏈路負載的同時提高了調(diào)度表生成的效率，能夠滿足更高的TT消息實時性和確定性需求，為機載TTE網(wǎng)絡(luò)負載均衡和調(diào)度表生成提供了一種可行的解決方案.