面向風(fēng)險均衡的AFDX虛擬鏈路路徑尋優(yōu)算法

趙長嘯，何鋒，閻芳，王鵬,*,熊華鋼

1.中國民航大學(xué) 天津市民用航空器適航與維修重點(diǎn)實驗室， 天津 300300 2.北京航空航天大學(xué) 電子信息工程學(xué)院, 北京 100083

綜合化是機(jī)載航電系統(tǒng)發(fā)展的趨勢，綜合模塊化航電系統(tǒng)(Integrated Modular Avionics，IMA)已成為新一代飛機(jī)航電系統(tǒng)的主流應(yīng)用架構(gòu)[1]，在空客A380、A350，波音B777、B787，中國的C919及處在論證階段的寬體客機(jī)，航電系統(tǒng)都采用了IMA架構(gòu)。IMA采用綜合核心處理系統(tǒng)(Integrated Core Processor，ICP)加載功能軟件的方式實現(xiàn)航電功能，并通過航空電子全雙工交換式以太網(wǎng)(AFDX)網(wǎng)絡(luò)實現(xiàn)各系統(tǒng)間信息共享[2]。IMA平臺的分區(qū)技術(shù)[3]和AFDX的虛擬鏈路(Virtual Link，VL)技術(shù)[4]具有系統(tǒng)隔離能力，可以保證駐留于同一平臺的航電功能獨(dú)立的實現(xiàn)其功能。但是目前系統(tǒng)設(shè)計中ICP和AFDX網(wǎng)絡(luò)設(shè)計是相互獨(dú)立的，當(dāng)將二者進(jìn)行集成時，ICP中的分區(qū)隔離特性有可能被AFDX中VL的不合理規(guī)劃破壞，產(chǎn)生風(fēng)險。如一架采用了IMA航電架構(gòu)的波音787飛機(jī)在某次試飛驗證實驗中，機(jī)載總線輸出的反推力虛假信號導(dǎo)致了飛機(jī)襟翼縮回而飛機(jī)被迫緊急終止飛行，此次事故征候的原因是AFDX交換式網(wǎng)絡(luò)引入了非設(shè)計性的系統(tǒng)交互，產(chǎn)生了數(shù)據(jù)的非預(yù)期傳輸路徑，破壞了系統(tǒng)層面的隔離特性，而在系統(tǒng)設(shè)計中二者是應(yīng)該充分隔離的[5-6]。因此在AFDX路徑規(guī)劃中應(yīng)考慮數(shù)據(jù)的安全關(guān)鍵特性，保證系統(tǒng)層面的隔離完整性。

目前，對AFDX路徑規(guī)劃問題主要集中在實時性、任務(wù)可靠性等方面。文獻(xiàn)[7-8]分別采用確定性網(wǎng)絡(luò)驗算和隨機(jī)網(wǎng)絡(luò)驗算對AFDX網(wǎng)絡(luò)進(jìn)行實時性優(yōu)化；文獻(xiàn)[9]提出了一種基于遺傳算法的AFDX路徑優(yōu)化方法；文獻(xiàn)[10-11]利用軌跡法進(jìn)行AFDX路徑配置，以保證VL的端到端延遲滿足系統(tǒng)要求。文獻(xiàn)[12-13]則從任務(wù)可靠性方面對AFDX網(wǎng)絡(luò)進(jìn)行了分析。這些研究分析僅針對AFDX網(wǎng)絡(luò)本身，未能考慮IMA平臺隔離有效性在網(wǎng)絡(luò)方面的延伸，網(wǎng)絡(luò)路徑規(guī)劃時未考慮各VL的安全關(guān)鍵程度，有可能造成風(fēng)險集中，影響整機(jī)的安全性。針對AFDX網(wǎng)絡(luò)的安全性問題，美國聯(lián)邦航空局發(fā)布了專門的咨詢通告AC 20-156[14]以指導(dǎo)對AFDX等機(jī)載高速互連網(wǎng)絡(luò)的適航工作。

基于此背景，本文提出了一種面向風(fēng)險均衡的路徑規(guī)劃(RBPP)算法，給出了民機(jī)航電系統(tǒng)功能的風(fēng)險量化模型；以均衡各物理鏈路風(fēng)險和滿足系統(tǒng)級隔離需求為目標(biāo)，并利用仿真實驗進(jìn)行分析對比驗證了算法的合理和優(yōu)越性。

1 IMA平臺與AFDX網(wǎng)絡(luò)集成風(fēng)險分析

IMA采用的分區(qū)技術(shù)從時間、空間兩方面對共享的平臺資源進(jìn)行了限制，但主要集中于IMA平臺，當(dāng)向網(wǎng)絡(luò)域延伸時，存在著隔離失效的風(fēng)險。AFDX網(wǎng)絡(luò)是IMA采用的網(wǎng)絡(luò)互連協(xié)議，AFDX引入VL對數(shù)據(jù)流量進(jìn)行邏輯上的隔離，在每個端系統(tǒng)的輸出端，與一條特定的VL相關(guān)聯(lián)的流量用帶寬分配間隔(Bandwidth Allocation Gap，BAG)來描述，BAG反映了在同一個VL中兩個相鄰幀的起始二進(jìn)制位之間的最小時間間隔[15]。AFDX網(wǎng)絡(luò)中通信通過VL來實現(xiàn)，但是由于網(wǎng)絡(luò)中的物理鏈路可以承載一條或多條VL，這就可能帶來不同航電系統(tǒng)間的非預(yù)期交互或非設(shè)計性交互，即在網(wǎng)絡(luò)邏輯拓?fù)渲邢嗷ジ綦x的不同VL在物理拓?fù)渲写嬖诨ハ嘤绊懙目赡堋?/p>

本文以一個示例網(wǎng)絡(luò)對AFDX網(wǎng)絡(luò)存在的有效隔離不足的風(fēng)險進(jìn)行分析?？紤]一個由4個交換機(jī)(sw1～sw4)，9個端系統(tǒng)(es1～es9)的AFDX網(wǎng)絡(luò)物理拓?fù)?，如圖1(a)所示。假設(shè)端系統(tǒng)es2和es4可分別實現(xiàn)IMA系統(tǒng)中的不同航電功能，按照安全性評估結(jié)果，兩端系統(tǒng)間需完全隔離，在IMA高速處理平臺端，系統(tǒng)的“健壯分區(qū)”特性使得兩個端系統(tǒng)滿足隔離要求；在網(wǎng)絡(luò)域，由于AFDX路徑規(guī)劃中未考慮VL承載的信息的安全特性，由端系統(tǒng)es2發(fā)出的vl4和由es4發(fā)出的vl8,從邏輯拓?fù)淙鐖D1(b)所示，兩條VL承載的數(shù)據(jù)是相互隔離的，但是由于其在實際物理拓?fù)渲泄灿靡粭l物理鏈路，因此在端系統(tǒng)es2和es4之間存在著耦合影響關(guān)系，破環(huán)了全系統(tǒng)的隔離特性。當(dāng)端系統(tǒng)es2和es4代表影響飛機(jī)安全的關(guān)鍵系統(tǒng)時，此問題變得更加嚴(yán)重。如在某型民機(jī)航電系統(tǒng)中，完全喪失通信系統(tǒng)或完全喪失導(dǎo)航系統(tǒng)均屬Ⅲ類(Major Failure)失效狀態(tài)，但是同時喪失通信系統(tǒng)和導(dǎo)航系統(tǒng)屬于Ⅰ類(Catastrophic Failure)失效狀態(tài)。因此對于這些關(guān)系到飛機(jī)飛行安全的系統(tǒng)，系統(tǒng)獨(dú)立性是安全性分析中需重點(diǎn)關(guān)注的問題。

在中國的國產(chǎn)大飛機(jī)C919中[16]，“航電系統(tǒng)主干網(wǎng)絡(luò)數(shù)據(jù)傳輸采用了ARINC664網(wǎng)絡(luò)總線，該總線與其他飛機(jī)系統(tǒng)的交聯(lián)非常復(fù)雜，與主飛控系統(tǒng)、動力系統(tǒng)、電源系統(tǒng)的部分信號、航電系統(tǒng)部分信號通過ARINC664總線直接交聯(lián)”?？梢姡珹FDX網(wǎng)絡(luò)連接了飛控、航電、動力等眾多的安全關(guān)鍵系統(tǒng)，不同端系統(tǒng)間的隔離有效性變得尤為重要，因此在對AFDX網(wǎng)絡(luò)進(jìn)行VL路徑規(guī)劃時應(yīng)對風(fēng)險進(jìn)行分析考慮。

圖1 IMA系統(tǒng)風(fēng)險示例
Fig.1 Example of IMA system risk

2 系統(tǒng)分析建模

2.1 網(wǎng)絡(luò)模型

2.2 風(fēng)險模型

在民機(jī)安全性分析中，依據(jù)航電系統(tǒng)功能失效對飛機(jī)、飛行機(jī)組、乘客的影響將失效狀態(tài)(Failure Condition)劃分為5個等級[17]。失效狀態(tài)等級的確定一般依據(jù)已有的相似機(jī)型的運(yùn)行數(shù)據(jù)、分析數(shù)據(jù)以及專家經(jīng)驗等信息確定，對于無法通過分析達(dá)成共識的失效狀態(tài)需通過飛行試驗確定。同一個航電系統(tǒng)可能有多個失效狀態(tài)，而不同的失效狀態(tài)其類別可能不同，一個航電系統(tǒng)的安全關(guān)鍵程度包括兩個指標(biāo)：最高的失效狀態(tài)類別，高等級失效狀態(tài)的數(shù)量。如某型客機(jī)的航電核心處理系統(tǒng)有21個Ⅰ類失效狀態(tài)，5個Ⅱ類失效狀，8個Ⅲ類失效狀態(tài)；飛機(jī)客艙照明系統(tǒng)有2個Ⅲ類失效狀態(tài)，3個Ⅳ類失效狀態(tài)，4個Ⅴ類失效狀態(tài)?？梢姾诫姾诵南到y(tǒng)的安全性關(guān)鍵特性要遠(yuǎn)高于客艙照明系統(tǒng)。

2.2.1 航電功能失效風(fēng)險模型

(1)

1) 災(zāi)難級失效不可容忍策略，即對Ⅰ類失效狀態(tài)賦值量級遠(yuǎn)超其他失效狀態(tài)類別：如取w1=100 000，w2=10，w3=1。對運(yùn)輸類飛機(jī)可采用此策略。

2) 不同級別失效風(fēng)險度差異賦值方式，即賦值體現(xiàn)不同類別風(fēng)險差異，同時各類別失效狀態(tài)風(fēng)險差異是可比擬的，如w1=100，w2=10，w3=1,對通用飛機(jī)可采用此策略。

2.2.2 IMA分區(qū)失效風(fēng)險模型

IMA通過分區(qū)技術(shù)，實現(xiàn)不同航電功能間的邏輯隔離，單一航電功能可以駐留于IMA系統(tǒng)中的一個分區(qū)或多個分區(qū)，同一分區(qū)中不可駐留不同航電功能，因此分區(qū)的失效風(fēng)險與其駐留的航電功能相關(guān)，定義分區(qū)partitionj的失效風(fēng)險為駐留于該分區(qū)的航電功能的失效風(fēng)險：

(2)

即當(dāng)同一航電功能駐留于多個分區(qū)時，各分區(qū)具有相同的失效風(fēng)險。

2.2.3 端系統(tǒng)失效風(fēng)險模型

在AFDX網(wǎng)絡(luò)中，分區(qū)通過端系統(tǒng)進(jìn)行數(shù)據(jù)的收發(fā)，單一端系統(tǒng)可支持一個或多個分區(qū)的通信需求，ARINC 664-P7中給出了端系統(tǒng)和分區(qū)的接口[18]，如圖2所示。VL實現(xiàn)分區(qū)到分區(qū)的確定性通信，多個分區(qū)進(jìn)行端系統(tǒng)共享時，各分區(qū)收發(fā)的VL仍能保證確定的獨(dú)立性，因此端系統(tǒng)esj的失效風(fēng)險由其支持的分區(qū)的失效風(fēng)險確定，其風(fēng)險定義為

圖2 分區(qū)與端系統(tǒng)接口
Fig.2 Interface between partitions and end systems

(3)

在民機(jī)中，Ⅰ類失效狀態(tài)(災(zāi)難的)和Ⅱ類失效狀態(tài)(危險的)的影響范圍和后果都是難以接受的，民機(jī)系統(tǒng)設(shè)計中，失效狀態(tài)類別每提高一個等級，其相應(yīng)的可靠性要求提高2個數(shù)量級。因此失效風(fēng)險模型為了體現(xiàn)高安全關(guān)鍵分區(qū)對系統(tǒng)安全的影響，定義了RⅠ為當(dāng)端系統(tǒng)所服務(wù)的分區(qū)駐留功能包含Ⅰ類失效時的最低風(fēng)險度；RⅡ為當(dāng)端系統(tǒng)所服務(wù)的分區(qū)駐留功能最高為Ⅱ類失效時的最高風(fēng)險度；RⅢ為當(dāng)端系統(tǒng)所服務(wù)的分區(qū)不包含Ⅰ、Ⅱ類失效時的最高失效風(fēng)險度，且RⅠ>RⅡ>RⅢ。

2.2.4 虛擬鏈路失效風(fēng)險模型

在AFDX網(wǎng)絡(luò)中，端系統(tǒng)之間通過VL進(jìn)行以太網(wǎng)幀的交換，在計算各VL的風(fēng)險度由其連接的源和目的端系統(tǒng)確定。

(4)

2.3 VL路徑優(yōu)化模型

對AFDX網(wǎng)絡(luò)中的VL進(jìn)行路徑規(guī)劃，是一個帶約束的分配問題：

A:VL→PL

(5)

本文提出的RBPP問題以均衡各物理鏈路所負(fù)擔(dān)的風(fēng)險，避免風(fēng)險匯集為目標(biāo)，同時還需滿足系統(tǒng)隔離需求、網(wǎng)絡(luò)實時性需求以及鏈路負(fù)載等要求。

優(yōu)化目標(biāo)為使各物理鏈路間的風(fēng)險差異最小，即

(6)

在AFDX網(wǎng)絡(luò)VL路徑規(guī)劃過程中還有如下約束：

1) 鏈路負(fù)載限制。物理鏈路承載的所有VL帶寬需求之和不應(yīng)超過物理鏈路的最大帶寬Cj：

(7)

2) 實時性要求。采用文獻(xiàn)[19]提出的網(wǎng)絡(luò)演算方法計算最壞情況下的VL延遲，滿足任意VL的最壞情況時延不超過其規(guī)定的最大允許時延要求：

(8)

3) 隔離要求。對于具有隔離要求的端系統(tǒng)，優(yōu)化后的物理路徑需滿足不同的隔離等級要求：

(9)

(10)

3 基于群粒子算法的RBPP問題求解

RBPP以最短VL路徑為基礎(chǔ)，以均衡各物理鏈路間的風(fēng)險位目標(biāo)進(jìn)行優(yōu)化，同時考慮端系統(tǒng)間的隔離需求及網(wǎng)絡(luò)中消息的傳輸實時性要求。AFDX網(wǎng)絡(luò)VL路徑規(guī)劃為NP問題，采用啟發(fā)式算法進(jìn)行問題求解，本文采用粒子群優(yōu)化(Particle Swarm Optimization, PSO)算法進(jìn)行求解。

3.1 問題描述

群粒子算法是由Kennedy和Eberhart提出的一種基于population的遺傳算法[20]，其改進(jìn)了的局部搜索能力較差的缺點(diǎn)。該算法最初由飛鳥集群活動的規(guī)律性啟發(fā)，利用群體智能建立了一個簡化模型。粒子群優(yōu)化算法中每個優(yōu)化問題的解都是搜索空間中的一只鳥，稱之為“粒子”[21]。所有的粒子都有一個由被優(yōu)化的函數(shù)決定的適應(yīng)值，每個粒子還有一個速度決定他們飛翔的方向和距離，然后粒子們就追隨當(dāng)前的最優(yōu)粒子在解空間中搜索[22]。

利用群粒子算法求解，首先需定義群粒子及求解空間。在本問題中，將粒子定義為需進(jìn)行路徑規(guī)劃的VL集合，粒子的位置表示VL的路徑規(guī)劃結(jié)果，假設(shè)待規(guī)劃的網(wǎng)絡(luò)中有VLNUM條VL，則其解空間為VLNUM×PATHNUM維空間，其中PATHNUM為初始化的有效VL路徑數(shù)量，解為VLNUM個變長數(shù)組集合。

優(yōu)化問題的適應(yīng)函數(shù)由優(yōu)化目標(biāo)和懲罰函數(shù)組成，第2.3節(jié)式(6)已給出了系統(tǒng)優(yōu)化目標(biāo)函數(shù)，其懲罰函數(shù)由分配約束定義，由式(7)和式(8)可得

(11)

適應(yīng)函數(shù)為

Fit(A)=Q(A)+γPE(A)

(12)

式中：Fit(A)為適應(yīng)函數(shù);Q(A)為由優(yōu)化目標(biāo)函數(shù)，由算法的優(yōu)化目標(biāo)轉(zhuǎn)化得到;PE(A)為懲罰函數(shù)，由約束條件轉(zhuǎn)化得到;γ為懲罰函數(shù)的權(quán)重值。適應(yīng)函數(shù)值越小，則此解的性能越好。

粒子的速度集合為V={v1,v2,…,vVLnum},vi取值范圍為在 (-PATHnum+1,PATHnum-1) 的整數(shù)，其代表粒子可以移動的距當(dāng)前位置的最遠(yuǎn)距離。算法會生成ρ個粒子，隨機(jī)的初始化各粒子的初始位置和初始速度，算法通過迭代在解空間中尋找最優(yōu)解。

在搜尋最優(yōu)解的過程中，粒子記錄兩個最優(yōu)值，Pbest為粒子在搜尋過程中記錄的最優(yōu)值，Gbest為整個粒子群所經(jīng)歷的最優(yōu)解。粒子位置和速度的更新公式為

Vt+1=ωVt+c1r1(Pbest-Xt)+c2r2(Gbest-Xt)

(13)

Xt+1=Xt+Vt

(14)

式中：X為粒子的位置;V為粒子的速度；ω為慣性權(quán)重，表示粒子對前速度繼承情況；c1、c2為粒子的認(rèn)知參數(shù)和社會參數(shù)，代表了粒子向自身最優(yōu)Pbest和全局最優(yōu)Gbest推進(jìn)的加速權(quán)值；r1、r2表示在0～1之間的隨機(jī)數(shù)。

3.2 算法步驟

采用PSO算法求解RBPP問題的具體步驟如下：

步驟1依據(jù)各端系統(tǒng)失效狀態(tài)清單計算端系統(tǒng)風(fēng)險值、VL風(fēng)險值及VL的隔離需求等級，計算方法見式(1)～式(4)。

步驟2求解各VL的可行路徑集合，構(gòu)建RBPP問題的解空間。

步驟3對待求解的VL進(jìn)行粒子編碼。

步驟4設(shè)置粒子群規(guī)模及迭代次數(shù)，初始化粒子位置及初始速度。

步驟5依據(jù)式(13)～式(14)更新粒子位置及速度，計算適應(yīng)度函數(shù)，并記錄局部最優(yōu)解及全局最優(yōu)解。

步驟6完成預(yù)設(shè)更新次數(shù)或滿足終止條件，對全局最優(yōu)解進(jìn)行式(9)的符合性檢查，若滿足條件，輸出結(jié)果；否則返回步驟4重新計算。

3.2.1 構(gòu)建解空間

對于AFDX虛擬鏈路的路徑優(yōu)化問題，PSO中每一個粒子代表了所有需要優(yōu)化的VL集合，粒子的位置代表了所有VL從源端系統(tǒng)經(jīng)過交換機(jī)到目的端系統(tǒng)的路徑。直接求解所有VL的路徑，尤其對于含有多播VL的AFDX網(wǎng)絡(luò)，算法實現(xiàn)十分困難，因此本算法中首先對各VL求解其可能的路徑集合，在此基礎(chǔ)上然后構(gòu)建PSO問題的解空間，求解RBPP下的最優(yōu)解。

1) 單播VL：對于單播VL，采用Dijkstra最短路徑算法[23]，針對每條VL進(jìn)行路徑規(guī)劃，選取較短的前PATHnum條路徑構(gòu)建最終算法的可行解。

2) 多播VL：對于多播VL，采用一般的最小Steiner樹算法[24]求解多播VL的最短路徑算法，選取樹的權(quán)值較小的前PATHnum顆樹構(gòu)建最終算法的可行解空間。

PATHnum的數(shù)值可依據(jù)不同的網(wǎng)絡(luò)進(jìn)行確定，對于一個具有VLnum條VL的AFDX網(wǎng)絡(luò)，RBPP問題的解空間為VLnum×PATHnum維空間。

3.2.2 解空間編碼

由于每條VL所經(jīng)過的交換機(jī)數(shù)目不定，因此各vl的路徑采用變長編碼方式。

以樹形結(jié)構(gòu)進(jìn)行存儲和操作。

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

在文獻(xiàn)[25] 中的PSO推薦參數(shù)值為ω=0.9,c1=c2=2。群粒子規(guī)模設(shè)置為20，迭代最大次數(shù)為2 000，各粒子位置及初始速度隨機(jī)設(shè)置。

3.2.4 隔離有效性檢驗

對求得的最優(yōu)解依據(jù)式(9)進(jìn)行隔離有效性的檢驗，所有VL的隔離有效性滿足，則結(jié)果為當(dāng)前AFDX網(wǎng)絡(luò)的VL路徑規(guī)劃結(jié)果。否則將當(dāng)前位置以(Path,k)的格式記錄于invalid集合，其中Path為當(dāng)前粒子位置，即VL路徑規(guī)劃結(jié)果，k為不滿足的隔離條件數(shù)量。返回步驟4重新開始計算。

3.2.5 粒子更新及終止條件

粒子位置、速度依據(jù)式(13)和式(14)更新，對更新后的粒子位置，進(jìn)行有效性檢查，若當(dāng)前位置屬于invalid集合，則跳過適應(yīng)度函數(shù)計算，并更新粒子位置及速度。

若當(dāng)粒子位置更新10次，全局最優(yōu)解Gbest不再變化或粒子位置更新達(dá)到2 000次時，則終止更新，當(dāng)前的全局最優(yōu)位置，即為問題的解。

當(dāng)invalid集合中元素個數(shù)達(dá)到20時，即表示PSO算法整體執(zhí)行了20次，找到了20個符合風(fēng)險均衡但不滿足隔離需求的路徑規(guī)劃方案。此時表示，網(wǎng)絡(luò)可能不存在滿足所有隔離需求的配置方案，此時從這20個方案找出與隔離方案要求最接近的方案作為次優(yōu)解，并給出不滿足的隔離需求供系統(tǒng)設(shè)計者進(jìn)行VL的重新優(yōu)化。

4 實例分析

利用C++構(gòu)建AFDX網(wǎng)絡(luò)模型[26]，實現(xiàn)AFDX網(wǎng)絡(luò)協(xié)議仿真在此基礎(chǔ)上對VL路徑規(guī)劃問題進(jìn)行分析，實現(xiàn)RBPP算法。仿真運(yùn)行的硬件系統(tǒng)配置為：Intel i7-2600處理器(主頻3.40 GH)，內(nèi)存8 G(1 333 MHz)，操作系統(tǒng) Windows 10(版本號10586)。實驗采用的AFDX網(wǎng)絡(luò)拓?fù)錇槲墨I(xiàn)[27]提出的經(jīng)典結(jié)構(gòu)如圖3所示，以及空客A380采用的AFDX網(wǎng)絡(luò)結(jié)構(gòu)[28]如圖4所示。

圖3 典型的工業(yè)AFDX網(wǎng)絡(luò)
Fig.3 Typical industry AFDX network

圖4 A380中AFDX網(wǎng)絡(luò)
Fig.4 AFDX network of A380

4.1 AFDX模型有效性分析

本文采用文獻(xiàn)[26]中提出的AFDX仿真平臺基礎(chǔ)，在文獻(xiàn)[9]改進(jìn)的AFDX仿真平臺上進(jìn)行試驗，此仿真平臺的仿真模型的精確度在文獻(xiàn)[9]中給出了說明。

4.2 實驗1

在實際的AFDX網(wǎng)絡(luò)研發(fā)過程中，某些研發(fā)單位會將多播VL簡化為多條單播VL進(jìn)行優(yōu)化配置，以簡化優(yōu)化過程，如在文獻(xiàn)[9]中的VL路徑規(guī)劃中將多播VL處理為多條單播VL并以sub-vl進(jìn)行標(biāo)記。此處理在多播VL數(shù)據(jù)流量不大的情況下進(jìn)行流量均衡算法，對路徑規(guī)劃的結(jié)果影響不大，但是對于針對網(wǎng)絡(luò)風(fēng)險進(jìn)行路徑規(guī)劃時，會產(chǎn)生“虛”風(fēng)險問題，本節(jié)以圖1、圖3、圖4所示的交換機(jī)網(wǎng)絡(luò)為例進(jìn)行分析。假設(shè)各網(wǎng)絡(luò)中每個交換機(jī)連接一個端系統(tǒng)，端系統(tǒng)esi分別與交換機(jī)swi相連接，假設(shè)端系統(tǒng)的風(fēng)險度均為1，各端系統(tǒng)間無隔離需求，端系統(tǒng)es1～es4均發(fā)送1條廣播VL，各VL的參數(shù)配置相同，為

為簡化分析過程，假設(shè)VL連接的所有端系統(tǒng)的風(fēng)險貢獻(xiàn)度相同，風(fēng)險貢獻(xiàn)度取值為

依據(jù)式(4)，則所有VL的風(fēng)險度為1。

本實驗選用的VL路徑規(guī)劃算法包括：

1) 文獻(xiàn)[9]提出的基于遺傳算法的路徑優(yōu)化算法(POGA)，此算法直接將多播VL進(jìn)行了多條單播VL簡化處理。

2) 本文提出的RBPP算法，對單播VL和多播VL分別采用不同的路徑規(guī)劃算法。

3) RBPP-simple算法，對待規(guī)劃的VL集合進(jìn)行處理，將多播VL簡化多條單播VL，在路徑規(guī)劃算法上采用RBPP算法。

比較不同網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)下，3種算法規(guī)劃后的網(wǎng)絡(luò)所有交換機(jī)間鏈路的平均風(fēng)險仿真結(jié)果,如圖5所示。

圖5 交換機(jī)間鏈路平均風(fēng)險
Fig.5 Average risk among links between switches

由圖5的仿真結(jié)果可知，對于相同的網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)，對多播VL進(jìn)行簡化處理的POGA和RBPP-simple算法，與RBPP算法相比，網(wǎng)絡(luò)中物理鏈路的平均風(fēng)險增加了50%和65%。盡管RBPP-simple算法考慮了風(fēng)險均衡，但由于將多播VL的簡化處理造成了優(yōu)化VL集合的“虛”中風(fēng)險增多。如對于圖1所示的4交換機(jī)網(wǎng)絡(luò)，不同端系統(tǒng)間的可行鏈路僅有1條，對于RBPP算法，待優(yōu)化的VL集合為4條廣播消息，而進(jìn)行簡化處理后，待優(yōu)化的VL集合為16條單播VL，將多播VL的風(fēng)險進(jìn)行了“倍增”，因此物理鏈路承載了“虛”風(fēng)險。綜上對涉及安全關(guān)鍵系統(tǒng)的AFDX網(wǎng)絡(luò)，不能將多播VL簡單的拆分為單播VL進(jìn)行路徑規(guī)劃。

4.3 實驗2

本實驗詳細(xì)描述RBPP算法各步驟的實現(xiàn)情況，以圖3所示的典型AFDX網(wǎng)絡(luò)拓?fù)溥M(jìn)行風(fēng)險均衡實驗，對比RBPP與負(fù)載均衡(LB)、最短路徑(SP)算法。假設(shè)：

1) 端系統(tǒng)es1～es8分別與交換機(jī)sw1～sw8相連接。

2) 各端系統(tǒng)僅與1個分區(qū)相連，且各分區(qū)駐留1個航電系統(tǒng)功能，各航電系統(tǒng)功能的各級失效狀態(tài)數(shù)量如表1所示，其中端系統(tǒng)es3和es7需完全隔離，即

表1 端系統(tǒng)失效狀態(tài)清單Table 1 List of failure conditions of end system

航電功能與分區(qū)及端系統(tǒng)的對應(yīng)支持關(guān)系如表2所示。

航電系統(tǒng)功能風(fēng)險度計算采用不同級別失效風(fēng)險度差異賦值方式，w1=100,w2=10,w3=1。取RⅠ=180,RⅡ=40,RⅢ=8,對端系統(tǒng)esk=1/p取εk=1/p,p為共享端系統(tǒng)esk的分區(qū)數(shù)量。依據(jù)式(1)～式(3)計算可得各航電系統(tǒng)功能、分區(qū)及端系統(tǒng)的風(fēng)險度如表3，其中es1所服務(wù)的分區(qū)中航電功能失效狀態(tài)最高為Ⅱ類，因此其風(fēng)險度不應(yīng)超過RⅡ,es1所服務(wù)的分區(qū)中航電功能失效狀態(tài)最高為 Ⅰ 類，因此其風(fēng)險度不小于RⅠ。

在網(wǎng)絡(luò)中配置7條VL，源節(jié)點(diǎn)分別為es1、es2、es3、es4、es5、es7和es8目的節(jié)點(diǎn)均為es6,所有VL的最大包長Lmax=500 byte，TBAG=4 ms，消息傳輸允許延遲1 ms，優(yōu)先級均為1，由端系統(tǒng)計算得到的VL風(fēng)險度如表4。

表2 駐留應(yīng)用與端系統(tǒng)分區(qū)關(guān)系

表3 端系統(tǒng)風(fēng)險度Table 3 Risk of end system

分別采用SP算法、LB算法和本文提出的RBPP算法進(jìn)行路徑規(guī)劃，本實驗中，通信流量較少，3種算法均無超時消息。3種算法得到的路徑規(guī)劃如表5。

分析各算法路徑規(guī)劃后，全網(wǎng)物理鏈路的風(fēng)險方差為

σSP=142.3,σLB=111.6,σRBPP=107.1

可知，σSP>σLB>σRBPP,即RBPP算法的風(fēng)險均衡能力最好，最短路徑算法能力最差。分析原因為，最短路徑算法以最小跳為優(yōu)化目標(biāo)，未考慮VL信息的特性；LB算法以在各物理鏈路中均衡流量負(fù)載為目標(biāo)，在分散流量的同時具有一定的風(fēng)險均衡能力；RBPP算法以物理鏈路間的風(fēng)險均衡為目標(biāo)，因此其風(fēng)險均衡能力最強(qiáng)。

對于端系統(tǒng)的隔離能力，端系統(tǒng)es3和es7需完全隔離，因此所有的物理路徑不應(yīng)同時承載vl3和vl7,由表5可知，SP和LB算法規(guī)劃后，鏈路sw6-sw7承載了vl3和vl7,違反了端系統(tǒng)隔離需求，RBPP算法在執(zhí)行優(yōu)化算法時，進(jìn)行了路徑的隔離性檢查，可滿足要求。

表4 VL風(fēng)險度Table 4 Risk of VL

表5 不同算法路徑規(guī)劃結(jié)果Table 5 Results of path planning for different algorithms

4.4 實驗3

本實驗在圖3、圖4所示的網(wǎng)絡(luò)中配置中等規(guī)模的流量，對比RBPP、LB、SP 3種AFDX路徑規(guī)劃算法的性能。對兩種不同的網(wǎng)絡(luò)架構(gòu)各配置1 000條單播VL，配置信息如表6。

圖3和圖4中具有相同標(biāo)識的端系統(tǒng)具有相同風(fēng)險度，采用表3的風(fēng)險度取值，補(bǔ)充端系統(tǒng)es9的風(fēng)險度為70。端系統(tǒng)間的隔離需求矩陣如表7，即端系統(tǒng)es3和es5需完全隔離，es2和es3,es1和es7,es4和es6間有限的隔離，其他節(jié)點(diǎn)間無隔離需求。

采用RBPP、LB、SP 3種算法進(jìn)行虛擬鏈路規(guī)劃，計算不同算法下全網(wǎng)物理鏈路的風(fēng)險方差σ，仿真結(jié)果如表8所示，3種算法在兩種網(wǎng)絡(luò)拓?fù)錀l件下均無超時消息。

表6 VL配置信息Table 6 Information of VL

表7 端系統(tǒng)隔離需求Table 7 Isolation requirement of end system

表8 仿真結(jié)果Table 8 Simulation results

由仿真結(jié)果可知，在中等規(guī)模流量條件下，兩種網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)下，RBPP算法的風(fēng)險均衡能力比LB算法分別提高了10.7%和23.4%，比SP算法分別提高了35.4%和47.9%。

對于端系統(tǒng)的間隔離需求，SP算法僅考慮了網(wǎng)絡(luò)中各節(jié)點(diǎn)的連通性，未考慮傳輸消息包含的信息，路徑規(guī)劃僅關(guān)注VL傳輸路徑跳數(shù)，因此在兩種拓?fù)渚W(wǎng)絡(luò)中對端系統(tǒng)間隔離需求均未能滿足；LB算法考慮了傳輸消息的流量信息，具有一定的路徑均衡能力，但主要考慮的是傳輸流量，因此在兩種拓?fù)渚W(wǎng)絡(luò)中種僅在典型AFDX網(wǎng)絡(luò)結(jié)構(gòu)中滿足了es2和es3相關(guān)的VL共享物理路徑不超過40條的隔離需求；RBPP算法以滿足端系統(tǒng)隔離需求，同時均衡各物理鏈路風(fēng)險為目標(biāo)，因此，在兩種網(wǎng)絡(luò)中都能滿足端系統(tǒng)隔離需求。但是由于要滿足端系統(tǒng)隔離需求，在進(jìn)行風(fēng)險均衡時的部分VL的可用路徑變少，使得各鏈路間的風(fēng)險偏差提高，如在網(wǎng)絡(luò)鏈路相對較少的A380AFDX網(wǎng)絡(luò)拓?fù)渲?，RBPP算法優(yōu)化后的網(wǎng)絡(luò)鏈路間風(fēng)險偏差與LB相近。

對于算法效率，由于RBPP算法首先對各VL進(jìn)行最短路徑求解，然后對VL集合進(jìn)行粒子群優(yōu)化，其算法執(zhí)行時間遠(yuǎn)高于LB和SP。另外對于網(wǎng)絡(luò)中可用鏈路相對較少的網(wǎng)絡(luò)，單次PSO優(yōu)化得到的結(jié)果可能不滿足隔離需求，因此需要多次執(zhí)行優(yōu)化算法，算法執(zhí)行時間有可能會高于網(wǎng)絡(luò)拓?fù)鋸?fù)雜的網(wǎng)絡(luò)。如在本實驗中，雖然A380AFDX網(wǎng)絡(luò)與典型AFDX網(wǎng)絡(luò)相比網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)相對簡單，但是RBPP算法執(zhí)行時間更長。

5 結(jié) 論

1) 為保證IMA的系統(tǒng)級隔離要求，提出了一種面向風(fēng)險均衡的AFDX網(wǎng)絡(luò)VL路徑規(guī)劃算法RBPP，以均衡各物理鏈路間的風(fēng)險為優(yōu)化目標(biāo)，提高系統(tǒng)安全性。

2) 給出了端系統(tǒng)、VL和物理鏈路的風(fēng)險度計算方法，引入PSO算法進(jìn)行VL路徑規(guī)劃，與最短路徑算法和流量均衡算法相比，可有效分散風(fēng)險；同時端系統(tǒng)隔離性檢查可有效滿足系統(tǒng)級隔離需求。

3) 目前采用的RBPP求解算法，在路徑規(guī)劃后進(jìn)行隔離性檢查，對不滿足的路徑集合進(jìn)行重規(guī)劃，效率較低，下一步研究計劃將隔離性檢查在路徑規(guī)劃過程工實現(xiàn)，以提高計算效率。

[1] 熊華鋼, 王中華. 先進(jìn)航空電子綜合技術(shù)[M]. 北京: 國防工業(yè)出版社, 2009: 10-12.

XIONG H G, WANG Z H. Advanced integrated avionics technology[M]. Beijing: National Defence Industry Press, 2009: 10-12 (in Chinese).

[2] SUCCA M, BOSCOLO I, DROCCO A, et al. IXV avionics architecture: Design, qualification and mission results[J]. Acta Astronautica, 2016, 124: 67-78.

[3] 王國慶, 谷青范, 王淼, 等. 新一代綜合化航空電子系統(tǒng)構(gòu)架技術(shù)研究[J]. 航空學(xué)報, 2014, 35(6): 1473-1486

WANG G Q, GU Q F, WANG M, et al. Research on the architecture technology for new generation integrated avionics system[J]. Acta Aeronautica et Astronautica Sinica, 2014, 35(6): 1473-1486 (in Chinese).

[4] CHA Y J, LIM J H, LEE S Y, et al. New feasible grouping algorithms for virtual link in AFDX networks[C]∥International Conference on Informatics, Electronics and Vision, 2015: 1-4.

[5] BAKER K. Filling the FAA guidance and policy gap for systems integration and safety assurance[C]∥IEEE Digital Avionics Systems Conference.Piscataway,NJ: IEEE Press, 2011: 1B4-1-1B4-4.

[6] SPITZER C R. The avionics handbook[M]. Boca Raton, FL： CRC Press, 2001: 155-158.

[7] BAUER H, SCHARBARG J L, FRABOUL C. Improving the worst-case delay analysis of an AFDX network using an optimized trajectory approach[J]. IEEE Transactions on Industrial Informatics, 2010, 6(4): 521-533.

[8] 趙露茜, 李峭, 林晚晴, 等. 基于隨機(jī)網(wǎng)絡(luò)演算的TTE網(wǎng)絡(luò)時延分析[J]. 航空學(xué)報, 2016, 37(6): 1953-1961.

ZHAO L X, LI Q, LIN W Q, et al. Stochastic network calculus for analysis of latency on TTEthernet network[J]. Acta Aeronautica et Astronautica Sinica, 2016, 37(6): 1953-1961 (in Chinese).

[9] 代真, 何鋒, 張宇靜, 等. AFDX虛擬鏈路路徑實時尋優(yōu)算法[J]. 航空學(xué)報, 2015, 36(6): 1924-1932.

DAI Z, HE F, ZHANG Y J, et al. Real-time path optimization algorithm of AFDX virtual link[J]. Acta Aeronautica et Astronautica Sinica, 2015, 36(6): 1924-1932 (in Chinese).

[10] FRANCES F, FRABOUL C, GRIEU J. Using network calculus to optimize the AFDX network[J]. IEEE Transactions on Medical Imaging, 2006, 25(10): 1319-1328.

[11] 劉成, 李航, 何鋒, 等. 基于軌跡方法的AFDX網(wǎng)絡(luò)路由配置算法[J]. 北京航空航天大學(xué)學(xué)報, 2012, 38(12): 1587-1590, 1595.

LIU C, LI H, HE F, et al. Routing algorithm of AFDX network based on trajectory approach[J]. Journal of Beijing University of Aeronautics and Astronautics, 2012, 38(12): 1587-1590, 1595 (in Chinese).

[12] WU Z, HUNG N, LI R, et al. A delay reliability estimation method for avionics full duplex switched Ethernet based on stochastic network calculus[J]. Eksploatacja i Niezawodnosc-Maintenance and Reliability, 2015, 17(2):288-296.

[13] ZHANG Y T, HUANG Z, XIONG H G. Study on network reliability in avionics based on performance degradation constraints[J]. Acta Aeronautica et Astronautica Sinica, 2011, 32(8): 1461-1468.

[14] Federal Aviation Administration. Advisory Circulars: AC 20-156 aviation databus assurance[S]. Washington, D.C.： Federal Aviation Administration, 2006.

[15] AN D, KIM K H, KIM K I. Optimal configuration of virtual links for avionics network systems[J]. International Journal of Aerospace Engineering, 2015, 11(8): 1-9.

[16] 馮曉林, 戴衛(wèi)兵, 彭國金. C919飛機(jī)航空總線采集和實時分析技術(shù)[J]. 飛行力學(xué), 2016, 34(5): 73-76.

FENG X L, DAI W B, PENG G J, Avionic bus collection and real-time analysis techniques of C919[J]. Flight Dynamics, 2016, 34(5): 73-76 (in Chinese).

[17] Society of Automotive Engineers. Guidelines and methods for conducting the safety assessment process on civil airborne systems and equipment: ARP4761[S]. Troy Michigan: Society of Automotive Engineers,1996.

[18] Aeronautical Radio Inc.. Aircraft data network part 7 avionics full-duplex switched Ethernet network: ARINC664-P7[S]. Annapolis: Aeronautical Radio Inc., 2009.

[19] LIU C, WANG T, ZHAO C X, et al. Worst-case flow model of VL for worst-case delay analysis of AFDX[J]. Electronics Letters, 2012, 48(6): 327-328.

[20] EBERHART R C, KENNEDY J. A new optimizer using particle swarm theory[C]∥Proceedings of The Sixth International Symposium on Micro Machine and Human Science. Piscataway, NJ: IEEE Press, 2002: 39-43.

[21] XU F, CHEN H, GONG X, et al. Fast nonlinear model predictive control on FPGA using particle swarm optimization[J]. IEEE Transactions on Industrial Electronics, 2016, 63(1): 310-321.

[22] LIANG J J, QIN A K, SUGANTHAN P N, et al. Comprehensive learning particle swarm optimizer for global optimization of multimodal functions[J]. IEEE Transactions on Evolutionary Computation, 2006, 10(3): 281-295.

[23] CRAUSER A, MEHLHORN K, MEYER U, et al. A parallelization of Dijkstra’s shortest path algorithm[M]. Berlin: Springer, 1998: 722-731.

[24] FURER M, RAGHAVACHARI B. Approximating the minimum-degree steiner tree to within one of optimal[J]. Journal of Algorithms, 1994, 17(3): 409-423.

[25] SHI Y, EBERHART R C. Parameter selection in particle swarm optimization[C]∥Proceedings of the 7th International Conference on Evolutionary Programming Ⅶ, 1998: 591-600.

[26] 黃臻, 張勇濤, 熊華鋼. 基于離散事件方法的AFDX建模與仿真[J]. 北京航空航天大學(xué)學(xué)報, 2011, 37(10): 1326-1332.

HUNG Z, ZHANG Y T, XIONG H G.AFDX modeling and simulation based on discrete event method[J]. Journal of Beijing University of Aeronautics and Astronautics, 2011, 37(10): 1326-1332 (in Chinese).

[27] CHARARA H, SCHARBARG J L, ERMONT J, et al. Methods for bounding end-to-end delays on an AFDX network[C]∥2006 Euromicro Conference on Real-Time Systems. Piscataway, NJ: IEEE Press, 2006.

[28] ITIER J B. A380 integrated modular avionics[C]∥Proceedings of the ARTIST2 Meeting on Integrated Modular avionics, 2007.