潘云嵩，周崇亮，萬曉冬

(南京航空航天大學(xué) 自動化學(xué)院，江蘇 南京 211106)

0 引言

航空電子系統(tǒng)是飛行器所有電子系統(tǒng)的總和。其系統(tǒng)大致經(jīng)歷了分立式、聯(lián)合式、綜合模塊化(IMA)3個階段[1]。目前，航空電子正從IMA走向分布式綜合模塊化航空電子系統(tǒng)(DIMA)的發(fā)展階段。

DIMA繼承了已應(yīng)用在B787、A380上的IMA的模塊化概念，制定具有標(biāo)準(zhǔn)統(tǒng)一接口的核心處理器模塊，分別為數(shù)據(jù)處理模塊(DPM)、信號處理模塊(SPM)、圖像處理模塊(GPM)、網(wǎng)絡(luò)支持模塊(NPM)、存儲器模塊(MMM)、電源模塊(PCM)。同時克服了IMA存在的集中式大機(jī)柜帶來的可靠性較差、線纜過長、不宜冷卻、故障容易擴(kuò)散等缺點(diǎn)[2]。核心處理模塊根據(jù)需求分布在飛機(jī)的各個位置，各個模塊之間通過實(shí)時高容錯通信網(wǎng)絡(luò)互連。

通過實(shí)時高容錯通信網(wǎng)絡(luò)連接起來的通用核心處理模塊、傳感器和作動器構(gòu)成DIMA的硬件物理層[3]。硬件物理層為系統(tǒng)運(yùn)行提供計算資源、存儲資源、IO資源、能源等。通用核心處理模塊如何分布在飛機(jī)上，稱之為硬件模塊映射問題。在DIMA系統(tǒng)中，飛行任務(wù)被細(xì)分成原子化的子任務(wù)模塊，每個子任務(wù)只能由一個特定的處理器模塊處理。為在完成一個飛行任務(wù)需要多個多種類型的處理器模塊協(xié)同合作，即功能應(yīng)用軟件在多個多種處理器模塊加注和運(yùn)算，并根據(jù)需要驅(qū)動傳感器或是作動器完成子任務(wù)。飛行任務(wù)的子任務(wù)模塊如何加載到分布在物理層上的通用處理模塊，稱之為軟件模塊映射問題。

Hamburg Univetsity of Technology的Bj?rnAnnigh?fer從成本的角度出發(fā)，提出了基于遺傳算法求解Pareto多目標(biāo)優(yōu)化的方案[4-5]。清華大學(xué)Chao Zhang從成本和可靠性的角度出發(fā)，對多個優(yōu)化目標(biāo)賦予不同的權(quán)值轉(zhuǎn)換成基于遺傳算法的單一目標(biāo)優(yōu)化問題[6]。上述文獻(xiàn)均未對處理器模塊做細(xì)分，把六大類處理器模塊當(dāng)作同一實(shí)體討論，且把子任務(wù)模塊和硬件模塊作為一個整體同時進(jìn)行優(yōu)化。在航空電子系統(tǒng)運(yùn)行期間，子任務(wù)模塊是動態(tài)加注到已經(jīng)分布在飛機(jī)物理層上的通用處理器模塊上，因此把硬件模塊映射和軟件模塊映射分成獨(dú)立的兩個階段更適合。本文在采用多種群遺傳算法[7]求解六大類通用處理模塊映射問題的基礎(chǔ)上，采用貪心算法求解軟件映射優(yōu)化問題。

1 DIMA資源映射問題描述

1.1 硬件模塊映射

DIMA采用模塊化的設(shè)計理念。航電功能系統(tǒng)模塊化設(shè)計，分出DPM、SPM、GPM、NPM、MMM、PCM六大模塊，每個模塊完成特定的功能。這六大類型模塊要分別安裝到分布在飛機(jī)不同位置的機(jī)架上，如圖1所示。

1.2 硬件映射數(shù)學(xué)模型

機(jī)架定義為L1,N1,L2,N2,…,Lm,Nm,其中Lm,Nm表示第m個機(jī)架具有Nm個安裝槽位供處理器模塊安裝。處理器模塊統(tǒng)一標(biāo)記為D1,D2,…,DND, 其中ND等于處理器模塊總數(shù)量。處理器模塊安裝在機(jī)架上，則可以表示為x向量：

X=[X1,Xi,…,XND]

(1)

其中，Xi表示為第i個模塊的安裝向量。

Xi=[xi,L1,…,xi,Lm]

(2)

其中，xi,Lm=1則表示第i個模塊安裝在第Lm機(jī)架上。xi,Lm=0，則表示不安裝。

約束條件1：每個模塊只能安裝在一個機(jī)架的一個安裝槽位上，一個機(jī)架可以安裝多個模塊，即：

AXT≤B

(3)

其中，B為長度為m的一維向量B=[1,1,…,1],A=diag(I,I,…,I),I=[1,1,…,1],長度為ND。

約束條件2：一個機(jī)架可以安裝多個模塊，但不能超過機(jī)架的總安裝槽位，即：

(4)

其中，1≤j≤m,，Nj表示第j個機(jī)架的槽位數(shù)量。

硬件映射方案的散熱用向量H表示:

H=[H1,Hi,…,HND]

(5)

其中，Hi表示為第i個模塊的安裝向量。

Hi=[Hi,L1,…,Hi,Lm]

(6)

其中，Hi,Lm≠0則表示第i模塊安裝在第lm機(jī)架上且散熱量為Hi,Lm≠0，Hi,Lm=0，則表示此槽位沒有模塊。

約束條件3：機(jī)架上安裝的處理器模塊總散熱量不能超過機(jī)架的最大冷卻能力，即：

AHT≤C

(7)

其中，C為長度為m的一維向量C=[C1,…Cm]，Cm為機(jī)架的最大冷卻能力，A=diag(I,I,…,I),I=[1,1,…,1],長度為ND。

在航電系統(tǒng)運(yùn)行期間，處理器模塊會與外圍設(shè)備(傳感器或是作動器)產(chǎn)生交互，機(jī)架到外圍設(shè)備的距離用矩陣L表示：

(8)

其中，lqp表示q機(jī)架到第p個外圍設(shè)備的距離，lqp=lpq，則所有安裝在機(jī)架里的處理器到外圍設(shè)備的距離用Dis表示，即：

(9)

(10)

1.3 軟件模塊映射問題

DIMA分成3個層次結(jié)構(gòu)，分別為功能層、任務(wù)層、處理器模塊層。系統(tǒng)功能被分成多個子任務(wù)。這些子任務(wù)是原子化，即一個子任務(wù)只能分配給一個處理器模塊處理。但一個處理器模塊可以處理多個來自不同系統(tǒng)功能的子任務(wù)。軟件模塊映射問題就是系統(tǒng)所有的子任務(wù)如何加注到模塊上，如圖2所示。

圖2 軟件映射示意圖

系統(tǒng)任務(wù)用F表示，原子任務(wù)用T表示，式(11)表示第i個系統(tǒng)功能可分成m個子任務(wù)。式(12)表示整個DIMA共有N個系統(tǒng)功能。

FI=(Ti,1,Ti,2,…,Ti,m)

(11)

F=(F1,F2,…,FN)

(12)

處理器模塊用M表示，MT表示該模塊能處理T類型的任務(wù)。

軟件映射問題就是給出功能Fi，依據(jù)怎樣的規(guī)則在DIMA模塊層中找出能完成該功能所需的處理器模塊集合Mset={MT1,…,MTm}。

2 問題優(yōu)化求解

2.1 硬件映射的優(yōu)化

上文已對硬件映射做了數(shù)學(xué)描述，建立如式(13)所示的數(shù)學(xué)模型，即求Dis最小值：

(13)

St.AXT≤B

AHT≤C

該模型是帶3個約束條件的單一目標(biāo)優(yōu)化問題。優(yōu)化的目標(biāo)為處理器模塊到外圍設(shè)備的距離Dis最短。Dis在DIMA系統(tǒng)中是個很關(guān)鍵的指標(biāo)，直接關(guān)系到通信效率、線纜費(fèi)用等方面。本文采用帶有修復(fù)因子的多種群遺傳算法求解該硬件映射的最優(yōu)解。

染色體采用自然數(shù)編碼形式[8]?？偣灿衜個模塊需要安裝，記為(1，2，3，…，m)。所有的機(jī)架共有n個安裝槽位，編號為(1，2，3，…，n)。染色體編碼形式如圖3所示，其中標(biāo)記為“0”表示此槽位不安裝任何模塊。采用自然數(shù)編碼形式能保證滿足式(3)和式(4)的約束條件。

圖3 染色體編碼形式

隨機(jī)產(chǎn)生染色體交叉位置k，然后交換1～k的染色體體位，并記下兩條1～k染色體體位的對應(yīng)關(guān)系。依照1～k對應(yīng)關(guān)系，交換k～n兩條染色體體位。

隨機(jī)產(chǎn)生2個染色體的突變位置，然后交換這2個位置的編碼，完成染色體的突變。

修復(fù)策略：對生成的每一代染色體，計算其對應(yīng)機(jī)架上所有模塊產(chǎn)生的散熱量，如果超過了機(jī)架的冷卻能力，隨機(jī)把該機(jī)架上的模塊放入具有剩余冷卻能力最大的機(jī)架內(nèi)，直至滿足式(7)對機(jī)架冷卻能力的約束條件。

多種群遺傳算法在常規(guī)的標(biāo)準(zhǔn)遺傳算法(SGA)的基礎(chǔ)上引入多個種群。每個種群配置不同的交叉概率pc和突變概率pm，這樣能擴(kuò)大算法的搜索范圍。每個種群通過移民算法，把最優(yōu)的個體引入其他種群，實(shí)現(xiàn)多個種群的協(xié)同進(jìn)化。其算法框架如圖4所示。

圖4 多種群算法流程圖

對硬件映射問題的求解，需要的數(shù)據(jù)有機(jī)架的數(shù)量、每個機(jī)架的槽位、每個機(jī)架與外圍設(shè)備的距離和處理器模塊的散熱量，限于篇幅就不列出了。如圖5和圖6所示，采用多種群算法求解硬件映射問題約進(jìn)化到80代時收斂。

圖5 每一代種群進(jìn)化結(jié)果

圖6 每一代精英個體適應(yīng)度

對精英個體的染色體通過解碼就得到該問題的最優(yōu)解，如表1所示。表1中表示150個硬件處理模塊在3個機(jī)架上的映射，自然數(shù)是硬件處理模塊的編號，0值表示該機(jī)架該位置不安裝任何處理器模塊。限于篇幅，未能列出全部數(shù)據(jù)。

表1 硬件模塊映射結(jié)果

2.2 軟件模塊映射優(yōu)化

求解軟件映射問題時確定如下3個優(yōu)化目標(biāo)：

1) 要能保證完成系統(tǒng)功能。

2) 子任務(wù)加注到處理器模塊盡可能靠近外圍設(shè)備。處理器靠近外圍設(shè)備就地處理，避免了數(shù)據(jù)在通信網(wǎng)絡(luò)上的遠(yuǎn)程傳輸。

3) 協(xié)同合作完成系統(tǒng)功能的多個多種類型的處理器模塊在空間上盡可能接近。處理器模塊聚集度高，將直接縮短處理器模塊之間數(shù)據(jù)的傳輸距離，這就能提高DIMA通信效率和可靠性。

其中x，y為模塊在飛機(jī)平面上的空間位置坐標(biāo)。

本文采用基于優(yōu)先級的貪心算法[9]解決軟件映射問題。首先依據(jù)任務(wù)緊迫性、運(yùn)算數(shù)據(jù)大小等因素事先排出子任務(wù)的優(yōu)先級，然后采用貪心的策略遍歷所有可行解依次找到滿足上述3個優(yōu)化目標(biāo)的解。其算法過程如下：

a) 遍歷所有的核心處理模塊，沒有剩余運(yùn)算能力的核心處理模塊排除在搜索范圍之外。

b) 依據(jù)子任務(wù)的優(yōu)先級，從高到低逐個選擇處理器模塊，依據(jù)以下2個優(yōu)先級準(zhǔn)則：

1) 若子任務(wù)需要用到某種外圍設(shè)備，則采用遍歷方式尋找離該外圍最近的模塊。

3) 模塊m加入集群，更新集群中心。

c) 如果還有子任務(wù)沒有分配，則繼續(xù)步驟a)和步驟b)，否則結(jié)束遍歷。

在硬件映射完成的基礎(chǔ)上，采用貪心策略依次滿足軟件模塊映射的3個優(yōu)化目標(biāo)，最終必定能找到一個近似最優(yōu)的軟件模塊映射問題解，即求得子任務(wù)加載到通用處理器模塊的方案。限于篇幅，未能列出優(yōu)化軟件模塊映射問題的輸入數(shù)據(jù)，軟件模塊映射優(yōu)化結(jié)果，見表2所示。表2表示4個具有不同優(yōu)先級的子任務(wù)軟件模塊被加注到4個硬件模塊之上。

表2 軟件模塊映射結(jié)果

3 結(jié)語

分布式綜合化模塊化航空電子系統(tǒng)(DIMA)是在聯(lián)合式航空電子系統(tǒng)和綜合化模塊化航空電子系統(tǒng)的基礎(chǔ)上發(fā)展起來面向未來的下一代航空電子系統(tǒng)。從國內(nèi)外公開發(fā)表的文獻(xiàn)來看，DIMA的資料還不是很多，知識點(diǎn)非常零散。本文采用多種群遺傳算法解決DIMA硬件映射問題，實(shí)驗(yàn)結(jié)果顯示是有效果的。對軟件映射問題，本文提出了基于優(yōu)先級貪心算法。其實(shí)質(zhì)是用貪心算法找到合適的映射方案，以期滿足盡可能縮短數(shù)據(jù)在處理器模塊之間、處理器模塊與傳感器作動器之間的傳輸距離3個優(yōu)化目標(biāo)。

[1] 徐科華, 陳謀, 徐揚(yáng),等. 民用飛機(jī)機(jī)載電子系統(tǒng)分布式體系架構(gòu)研究[J]. 工程設(shè)計學(xué)報, 2012, 19(6):494-498.

[2] 朱聞淵, 尹家偉, 蔣祺明. 新型航空電子系統(tǒng)總線互連技術(shù)發(fā)展綜述[J]. 計算機(jī)工程, 2011(s1):398-402.

[3] Wolfig R, Jakovljevic M. Distributed IMA and DO-297: Architectural, communication and certification attributes [C] //Digital Avionics Systems Conference, IEEE/AIAA 27th. IEEE, 2008(1): 4-10.

[4] Annighofer B, Thielecke F. Multi-objective mapping optimization for distributed Integrated Modular Avionics[J]. Digital Avionics Systems Conference, 2012,6B2:1-13.

[5] B. Annigh?fer, Thielecke F. A systems architecting framework for optimal distributed integrated modular avionics architectures[J]. CEAS Aeronautical Journal, 2015, 6(3):1-12.

[6] Zhang C, Xiao J. Modeling and optimization in Distributed Integrated Modular Avionics[J]. Digital Avionics Systems Conference, 2013:1-20.

[7] 劉鵬程, 李新利. 基于多種群遺傳算法的含分布式電源的配電網(wǎng)故障區(qū)段定位算法[J]. 電力系統(tǒng)保護(hù)與控制, 2016, 44(2):36-41.

[8] 鄒琳, 夏巨諶, 胡國安. 基于實(shí)數(shù)編碼的多種群并行遺傳算法研究[J]. 小型微型計算機(jī)系統(tǒng), 2004, 25(6):982-986.

[9] 代文強(qiáng), 李曉榮, 馮毅. 最大和搜索結(jié)果多樣性問題及其貪婪算法分析[J]. 系統(tǒng)工程理論與實(shí)踐, 2016(3):706-711.