分布式綜合化航空電子網絡拓撲優化技術

邱 征，魏雪菲，王世奎

（中航工業西安航空計算技術研究所，西安 710065）

0 引言

IMA（Integrated Modular Avionics）是一種先進綜合航空電子技術。IMA 技術采用統一的通信網絡進行互聯，采用標準、通用的設備和網絡減少航空電子系統開銷和重量［1］。IMA 綜合化架構帶來功能綜合、資源集中與系統耦合的問題，目前僅能通過手動方式優化IMA 架構設計與業務分配。國外提出一系列優化算法針對功能分布、互聯拓撲和資源分配進行優化［2-4］，能夠較好地優化航電架構，但尚需考慮航電網絡本身通信延遲、交換容量、線纜重量等開銷和性能。這些指標在分布式綜合化架構（DIMA）下更加重要。AFDX 網絡［5］是一種主流的航電交換網絡，采用星型拓撲。AFDX 網絡端系統通過交換機互聯通信，交換機可以轉發端系統、級聯交換機的消息。AFDX 網絡適合混合安全關鍵系統，它采用消息靜態路由、流量控制、鏈路劃分、帶寬分配等手段來保證通信確定性，同時還通過物理連通與邏輯同傳的雙冗余機制來保證信息的可靠性。

AFDX 網絡架構設計核心在于受限條件下路由規劃和確定性調度機制［7］：物理鏈路余度、端到端延遲、帶寬預算分配、混合關鍵業務并發、信息可靠性等限制。Charara 提出一種半自動端到端延遲證明與計算方法［8］。Zhang 提出一種自動最小化平均網絡負載的VL 路由方法［9］。Al Sheik［10］提出通過優化消息載荷和速率降低網絡負載。Carta 在連接和節點數一定的情況下，考慮帶寬隔離約束，提出一種自動生成VL 路由方法［11］。

目前所有網絡優化方法均基于網絡拓撲。針對規模、延遲、開銷等目標，本文提出一種基于多目標優化的最優網絡拓撲的計算模型與方法。網絡拓撲優化的目標是計算獲取一個優化的拓撲，包含交換機數量、交換機位置和物理連接，包括：

1）功能業務特性的大量端系統部署信息；2）功能交互所需的一系列信號，需要帶寬、延遲、隔離約束；3）終端物理安裝位置和線纜路徑的物理長度；4）鏈路和交換機的屬性，包含重量、開銷、可靠性和端口數。

本文針對AFDX 網絡協議特性作了兩處簡化假設。首先，路由是作為端到端通信計算，沒有采用多播VL。其次，雙冗余的AFDX 網絡中僅考慮單鏈路通信，假設兩條鏈路上的通信能力一致。

1 網絡拓撲模型與多目標優化算法

1.1 拓撲結構模型

AFDX 拓撲采用設備D 和連接L 描述。設備由一組端系統DE和一組交換機DS組成。兩個設備之間的連接是點對點通信。網絡拓撲可以通過無向圖G=（V，E）進行建模，節點V={DE，DS}，邊E={E1，…，En}，其中Ei=（Vp，Vq）。AFDX 拓撲圖受更多限制：1）端系統節點通常只有一個邊；2）交換機節點有多個邊，但是節點邊的最大數量=交換機端口數目pmax；3）兩個端系統之間不能有邊。

AFDX 網絡拓撲圖可以涵蓋業務拓撲、物理拓撲，網絡拓撲設計目標包括駐留在端系統DE上的任務T。所有任務T 的信號集S 特定，它是兩個任務之間的直接通信，例如Sk=（Ti，Tj）。信號不是一個單獨的數據，而是兩個任務之間通信預定義藍圖，藍圖需要優化設計。對于每一個信號Sk，它的路由必須能夠從源任務駐留設備DE（Ti）到目的任務駐留設備DE（Tj）。一個完整的路由（在圖論中為路徑P）可以采用設備、鏈接、交換機列表進行定義，例如Pk=（D1E，L2，D2S，L3，…，D7E）。路由必須由源設備開始，到目的設備終止，并且拓撲中間都是正確完整連接，且沒有物理斷開。

在網絡拓撲中，每個交換機或連接上的信號數量、容量有限，可以通過一個簡單的資源模型表達。信號資源需求如式（1）：

索引1 到n 表示網絡拓撲中使用不同資源類型，最主要的資源類型為帶寬。另外，像CPU 負載、緩沖負載或者信號數等也可以考慮。

交換機和連接提供的每個資源類型ri∈R+，其資源都是一個正數。只有交換機、物理連接（虛擬連接）能滿足信號所需最小資源時，信號才能分配到該交換機或連接上。一旦分配完成，需要的資源數量就被消耗，其他信號就不能再使用該資源。交換機和鏈接上分配的信號所需要資源之和，必須小于等于其對應的每個資源類型所擁有的可用資源。

此外，任務應該考慮隔離約束δ，隔離約束定義：兩個任務不能在一樣的設備、設備類型、位置或者這三者的組合上。隔離任務的信號，除了有相同的源或目的，在它們的路徑中不能再有任何相同的節點或者邊。如果需要不同的安裝位置，鏈接必須采用單獨的物理線纜。

網絡拓撲受限于航電物理構型剖面。剖面可以通過網絡安裝位置I，線纜路由C 和連接點J 建模。每個端系統的位置已知，交換機位置也是從可供安裝的位置中選擇。交換機的布局同信號一樣，受相似的資源模型限制。安裝布局位置為每一個不同類型i 提供基礎資源ρi∈R+，ρi為交換機所需要消耗的資源。從而限制每個安裝位置的交換機數量。線纜路由是位置之間可能的物理鏈接，它的屬性通過長度進行刻畫。線纜路由通過連接點進行分割和連接。位置、線纜路由和連接點形成了剖面圖GA=（VA，EA），其中VA={I，J}，EA=C。

1.2 拓撲優化方法

通用的優化方法是生成一個過設計的拓撲，再基于目標函數和約束條件縮小該拓撲。首先需要建立一個能滿足需求的初始拓撲，再迭代優化該拓撲。假定采用的輸入如下：

1）所有已經分配任務的端系統集合、信號列表、資源需求和隔離約束；2）網絡平臺：包含由信號、基礎資源和端口數量刻畫屬性的交換機和同樣由可用資源進行刻畫的鏈接；3）由位置、基礎資源及線纜路由組成的構型剖面。

圖1 拓撲優化的一般方法

過設計的拓撲命名為最大化網絡，可通過圖1進行描述。該最大化網絡在每個位置按照基礎資源限制，擺放盡可能多的交換機。它為每個端系統和每個交換機引入一個鏈接，不考慮每個端系統只能有一個鏈接的限制。此外，為每一對交換機之間引入一個鏈接。按照此規則建立的最大網絡，擁有|DE|個端系統，可以布局|DS|個交換機，|DS|2+1/2|DE|+|DE||DE|條鏈接。在第2 階段，所有的信號在最大網絡中進行路由，因此，最大網絡所有用到的要素形成優化拓撲，如優化目標可以為交換機和鏈接的最小數目。優化后的拓撲必須滿足交換機和端系統的最大端口數目要求。

最大網絡的創建是一個預處理步驟。以優化拓撲為目標的信號路由是一個組合優化問題。它可以通過一個二進制程式（binary program，BP）進行公式化。通常BP 是找到一個的二進制向量x，將其最小化。

其中，x 是求解向量，f 是開銷向量，A 和Aeq包含一個任意數量的線性等式和不等式。

拓撲優化問題解決向量編碼如式（4）：

對每一個交換節點Vj，其資源類型k 的可用資源會限制該交換機上信號的最大數量。同理，表示每個鏈接Ej存在不等式：

|DS|+|E|資源不等式組成了Ar。

信號Si和Sj之間的隔離可用以下不等式表示：

上述不等式表示對于每對隔離的信號其每個交換機使用。所有的隔離不等式組成矩陣Aδ。

對于每個交換機|Vj|和鏈接|Ej|需要兩個不等式，將xP和xV、xE關聯起來。不等式如式（10）：

確保如果至少一個信號用到它，則使用變量為1，另外：

如果沒有信號分配給它們，則強制使用變量為0。使用約束由AE和AV組成。

最后，每個交換機和端系統最大鏈接數由以下不等式限定：

對于端系統b 為1，對于交換機b 為pmax。這個|DS|+|DS|的不等式組成了矩陣Aport。

BP 計算最大網絡中每個信號的正確信號路徑，該路徑包括上述所有等式和不等式：

并且

1.3 優化加速方法

BP 問題屬于一類NP 難題。路徑編碼部分（xP）的x 占變量大部分，它表示每個可能的路徑。為了減少變量數目，xP可以通過向量xR簡化。xR為每個信號i 編碼一個預計算路徑集合Ri1，…，Rim。所有信號路徑就從該預計算路徑集合中選擇。xR中變量個數受限于m|S|，用戶可以定義m。在Yen 的算法中建議最大網絡選擇從源到目的設備的m 最短路徑［12］。通過使用候選路由，路徑約束等式就可以簡化。BP中所有其他的等式和不等式，也需要相應修改來適應路由替換。例如，一個路由替換原路徑所消耗資源。使用預計算路可能不會達到全局最優。上述問題可以通過混合整數線性規劃（MILP）或者布爾可滿足性（SAT）解決。通過問題模型化可以計算全局最優解。開銷向量f 增加的開銷可以分解到所有的交換機、鏈路或者路徑部分。因為航空電子系統的設計（包括網絡）遵從多個目標，因此提出一種多目標的擴展。替換掉一個開銷變量f，可以假定以下公式已經最小化。

通常這些開銷存在部分沖突，不存在一個通用的最優解。因此，在多目標優化中提出了計算Pareto最優解。Pareto 最優解是一個折中最優解的集合。拓撲優化中全局的Pareto 最優解通過Pareto 前沿采樣（Pareto-Front-Sampling，PFS）計算。PFS 是由Ozlen［13］提出的一種迭代外部算法。它解決了一系列單目標BP，通過變動約束使得每次迭代都能找到一個有效解。每次迭代使用一個標準的BP 解決器。參見文獻［3］中使用的PFS 算法細節。

2 機載網絡拓撲與業務

機載網絡拓撲規模包含交換機、鏈接線纜規模。交換機的規模固定，采用mS進行定義。對于線纜鏈接，需要每種長度的規模，再通過單獨線纜長度相乘，得到總長度規模。鏈接的長度通過剖面模型的最短路徑獲取。對于每一個鏈接，其規模為miE。開銷向量為：

僅針對交換機計算操作中斷開銷（Operational Interruption Cost，OIC）。OIC 是因網絡失效導致的通信中斷延遲開銷，依賴于平均失效間隔時間MTBF給定的交換機可靠性。

2.1 A320 場景

通過類320 場景驗證網絡拓撲優化。希望得到一個涵蓋4 個航空子系統，包含信號、任務和端系統的網絡優化拓撲。參照A320-200，定義通風控制系統（VCS），放氣系統（BAS），充氣系統（PS）和過熱檢測系統（OHDS）。圖2 描述了系統的任務和信號。信號由源端到目的端函數的所有參數組成；可以包含幾個獨立的消息。每個系統有兩個獨立的線纜，因此，它們的信號必須隔離?？偣残枰峙?2 個信號。每個系統有兩個控制器。此外，在PS 和OHDS之間還有一個通用的外置交換機通信。

圖2 任務信號及隔離

端系統和交換機有7 個可安裝位置，包含鼻翼、中部和尾部。鼻翼位置可以駐留1 個交換機，中部和尾部分別駐留2 個交換機，航空電子中間位置最多可擺放4 個交換機。鼻翼位置到中間位置的訪問時間假定為5 min，中間位置到尾部的訪問時間假定為45 min。另外，給出可能的線纜拓撲連接。每個線纜路由根據飛機外部尺寸分配一個固定長度。

圖3 任務與端系統的映射

圖3 展示了IMA 模塊的系統功能分配。有4 個擁有控制器功能的核心計算模塊（CPM）和10 個連接外圍功能的遠程數據接口單元（RDC）。

網絡由5 個端口，重0.4 kg 的交換機組成，MTBF 設置為100 000 飛行小時，連接線纜指定為0.1 kg/m。交換機沒有帶寬限制，可以假定這52 條消息在一個單獨的交換機或者鏈路上都可行。優化設計任務是找到具有最低規模和OIC 的網絡拓撲結構。初始拓撲和路由可以是手工定義，實現兩種自動優化：首先，算法的信號路由優化，基于初始手動拓撲驗證改進后的信號路由。其次，拓撲規模和OIC的優化，計算Pareto 優化拓撲。最后，在簡化預計算路徑的下重復拓撲優化。同時評估所有研究的目標值、拓撲和運行時間。

2.2 類A380 場景

通過類A380 場景來驗證大規模的拓撲優化，并得到一個新規模的優化拓撲。目前A380 AFDX網絡交換機屬性在文獻［6］中描述，系統位置信息來源于文獻［14］。網絡擁有104 個端系統，9 個AFDX 交換機，網絡支持100 Mb/s 通信帶寬，模擬機載系統業務消息與控制耦合，例如，每個系統域到座艙的高帶寬消息。主要的消息接收端有飛行管理（FM）、飛行告警（FW）、飛行控制與數據計算（FCDC）和座艙信息與數據系統（CIDS），可以確定有327 條速率為0.5 到4 Mb/s 的點到點連接。對于冗余系統線纜，存在45 條隔離約束。通過提出的方法和初始的拓撲可以得到一個正確的優化路由。假定交換機重2 kg，線纜重0.037 kg/m，安裝機柜規模為25.1 kg（包含9 個交換機和113 條鏈接）。

3 優化算例

3.1 類A320 場景結果

手動設計優化拓撲如圖4 所示，它擁有8 個交換機，4 個位于系統前后緣，在系統中間位置上下分別布局2 個。對稱的設計在飛機兩邊形成兩個并行路由，它們分別承載隔離的信號?？偣灿?4 條鏈路，所有的交換機危險程度都是NOGO。

圖4 手動設計拓撲結構

解2 采用PS 系統和OHDS 系統之間的通信路由，替換掉中間位置之間的線纜。減少了兩條鏈接。此外，兩個交換機危險程度降低為GOIF。規模和OIC 分別降低為20.1 kg 和746$/a。

解3 中規模達到最優解，如圖5 所示。優化后的拓撲與手工設計相似，但是在中間每個位置只有一個交換機，增加了一個長鏈接。拓撲只有6 個交換機和10 個鏈接，減少了重量和OIC，所有交換機又都達到NOGO 危險程度。

圖5 解3-規模優化拓撲

解4 給出OIC 最優集，如圖6 所示。它同樣擁有6 個交換機，但是在飛機中間位置引入長卷纜柱（cabling）。這使得只有4 個交換機變為NOGO，2 個變為GO。它的規模為26.2 kg，在這些拓撲中最大。

圖6 解4-中斷開銷優化拓撲

通過預計算路徑方法，針對拓撲規模和OIC 分別再次計算拓撲優化。通過選擇路徑長度最短來創建路徑候選，得到最大網絡中的最少路徑。在本解中，得到的m=21，但這并不是拓撲規模全局最小解，它需要8 個交換機。最終得到的全局最優解m≥30。一個合理預計算路徑數目，并沒達到OIC 的全局最優解。

通過下頁表1 對比可知，預計算路徑在運行時間、變量數目和約束給定的情況下，能明顯節省時間。計算拓撲優化的Pareto 最優解花費4 h，運行時間最長。每個全局最優拓撲平均花費1 h。使用預計算路徑簡化后，每個解為3 min，速度提升一個量級。

3.2 類A380 場景結果

類A380 網絡優化拓撲，擁有7 個交換機和111條鏈接，重量約22 kg，比初始減少了12%。減少了座艙域中的兩個交換機，中間交換機獲得了一個多域的角色，并且移動了位置，因此，位于圖的中心。每個交換機平均鏈接數目從15 條增加到19 條。這種方式打破了系統區域，但是網絡負載沒有變化。類A380 優化問題有139 071 個變量，相當于類A320 優化規模的15 倍（如表1 所示）。

表1 求解規模與運行時間

3.3 優化結果分析

類A320 場景的優化實驗表明提出的方法可以針對不同維度找到優化解。相對手動設計，信號路由改進效果較明顯。規模和OIC 都可以通過選擇非傳統路由方法改進，但通過手動設計方法無法預測。通過拓撲優化的Pareto 最優解能夠發現非傳統路由的全部潛在可行解。通過改進拓撲，規?？山档?%，OIC 可降低30%，達到規模最優。然而，由于OIC 目標本身的復雜性，手動優化幾乎不可能實現。不經過優化（通過手動），即使能夠得到一部分最優解，也不能確定該解是否為全局最優解。本文提出的方法可以通過部分的自動設計和設計調整，能夠達到全局最優解。此外，通過折中解能顯示解的最優特性和目標之間的關系，而手動設計則很難達到這種精度。BP 問題的大小和結果運行時間難以考慮。計算4 個小時獲得Pareto 最優解也可以接受，但是本文所研究的只是一個小規模的算例，隨著變量數量、交換機數目增長，計算復雜度呈指數值增長。類A380 拓撲優化表明：當目標受限，將消息分組到更少的信號上時，在整個飛機級采用該方法是適用的。同時，可以采用預計算路徑方法限制運行時間。但是，預計更多的候選路徑，并不能達到全局最優的OIC。如果后續選擇候選路徑時能夠考慮OIC 的話，這一情況可能會得到進一步改進。使用預計算路徑不能保證達到全局最優。因此，拓撲優化不能替代網絡設計人員，而是一個有效的輔助分析手段。

4 結論

目前分布式綜合化航電架構依賴高帶寬航電網絡，網絡規模和開銷對航電系統效能影響很大。本文提出一種基于業務拓撲、網絡拓撲以及延遲、距離約束下的多目標網絡拓撲優化算法，通過最大網絡的迭代優化得到最優網絡拓撲。優化的輸入參數包括功能、信號和資源需求模型、拓撲安裝位置、線纜路徑的模型。優化模型的計算是一個BP 問題，最優解是面向網絡規模和OIC 的線性開銷函數的優化拓撲。另外，通過Pareto 采樣，能夠得出多目標約束下的最佳折中拓撲結構集。類A320 場景架構優化能夠提升30%。類A380 架構優化能夠提升12%，表明大規模網絡優化的可行性。