基于混沌映射自適應(yīng)NSGA-Ⅱ算法的IMA雙層資源分配方法

樊智勇， 李伯寧， 王 凱， 趙 珍

(中國民航大學(xué)，天津 300000)

0 引言

隨著航空電子系統(tǒng)功能的日益復(fù)雜化，傳統(tǒng)的分立式和聯(lián)合式航電系統(tǒng)已經(jīng)不能滿足現(xiàn)代飛機的需求，為提升現(xiàn)代飛機的性能，綜合模塊化航電(Integrated Modular Avionics,IMA)[1]架構(gòu)被廣泛應(yīng)用于C919，B787和A350等民航客機。采用IMA架構(gòu)的航電系統(tǒng)具有系統(tǒng)綜合化、結(jié)構(gòu)層次化和調(diào)度靈活化等優(yōu)勢[2]。IMA架構(gòu)的設(shè)計理念是基于ARINC組織提出的ARINC653規(guī)范[3]，在該規(guī)范中，實時操作系統(tǒng)將硬件資源劃分為時間和空間相互獨立的資源分區(qū)，保證某個分區(qū)的故障不會擴散到其他分區(qū)，從而提升系統(tǒng)的可靠性和可擴展性[4]。

IMA架構(gòu)中，航電系統(tǒng)功能由駐留在不同模塊、分區(qū)上的應(yīng)用完成，因此，需要為各應(yīng)用配置系統(tǒng)資源，這些系統(tǒng)資源主要分為計算資源、通信資源和存儲資源3類[5]。在以往的資源配置中，工程師主要依靠主觀判斷和經(jīng)驗，難以驗證分配方案是否有效或最優(yōu)[6]。因此，眾多國內(nèi)外專家學(xué)者對IMA架構(gòu)的資源分配方法展開了研究。

文獻[7]將IMA架構(gòu)所需總帶寬和分區(qū)調(diào)度引起的系統(tǒng)開銷作為優(yōu)化目標(biāo)函數(shù)，改進了基于分解的多目標(biāo)優(yōu)化算法(MOEA/D)，能有效降低系統(tǒng)開銷和帶寬需求，但該方法沒有考慮任務(wù)的內(nèi)存開銷；文獻[8]針對IMA架構(gòu)的分區(qū)分配和調(diào)度設(shè)計問題，提出了一種所有約束均為線性不等式的模型，能保證在滿足所有約束條件的情況下實現(xiàn)全局最優(yōu)，但該模型中需要設(shè)置的參數(shù)較多；文獻[9]提出了一種多層資源分配方法，分別在平臺層和節(jié)點層對任務(wù)進行分配并優(yōu)化分區(qū)參數(shù)，試圖找到一個通信代價最小的任務(wù)分配方案，但是該方法沒有考慮資源分配的均衡性。本文針對上述分配方法的不足之處進行了研究。

針對IMA架構(gòu)的資源配置問題，本文根據(jù)IMA架構(gòu)任務(wù)調(diào)度的特點，綜合考慮計算、通信和存儲3類資源以及資源配置均衡性因素，建立了IMA架構(gòu)的雙層資源分配模型，并采用混沌Logistic映射自適應(yīng)改進NSGA-Ⅱ算法對模型進行優(yōu)化求解，得到最優(yōu)的分配結(jié)果。

1 問題描述

IMA架構(gòu)中資源種類繁多，并且具有時間隔離和空間隔離的特性，使得其資源分配相較于傳統(tǒng)架構(gòu)的航電系統(tǒng)更為復(fù)雜多變。飛行過程中，飛機的各種功能應(yīng)用都駐留在IMA架構(gòu)的計算機上[10]，因此，在系統(tǒng)運行之前需要對資源進行合理的靜態(tài)配置。考慮到IMA架構(gòu)是基于ARINC653的雙層調(diào)度機制，分為分區(qū)間調(diào)度和分區(qū)內(nèi)調(diào)度，因此，本文的資源分配也采用雙層分配的形式。

設(shè)IMA架構(gòu)共包含nN個處理節(jié)點，處理節(jié)點為IMA架構(gòu)分區(qū)駐留的計算機，每個處理節(jié)點上駐留nP個分區(qū)，為完成航電系統(tǒng)的功能共需nΓ個任務(wù)。

根據(jù)IMA架構(gòu)的設(shè)計原則，本文提出了一種IMA架構(gòu)的雙層分配思想，任務(wù)集合為IMA架構(gòu)運行過程中駐留的應(yīng)用集合，第1層分配將任務(wù)集合劃分為任務(wù)組，每個任務(wù)組駐留在一個分區(qū)，分區(qū)內(nèi)的任務(wù)應(yīng)滿足可調(diào)度性約束和任務(wù)分配約束，建立分區(qū)分配模型進行求解，得到分區(qū)的CPU利用率、帶寬和內(nèi)存開銷，第2層分配將分區(qū)分配到各個處理節(jié)點，建立節(jié)點分配模型，優(yōu)化求解得到各個處理節(jié)點的CPU利用率、帶寬和內(nèi)存開銷以及最終的分配結(jié)果。

在建立IMA架構(gòu)雙層資源分配模型之前，先進行如下假設(shè)：

1) 任務(wù)之間相互獨立，即任務(wù)之間不存在資源競爭和執(zhí)行順序的依賴關(guān)系；

2) 任務(wù)的周期不大于任務(wù)的相對截止時間，即Ti≤Di；

3) 分區(qū)內(nèi)采用最早截止優(yōu)先(EDF)算法，任務(wù)的相對截止時間越早，優(yōu)先級越高；

5) 忽略任務(wù)間的切換開銷；

6) 任務(wù)間的通信被認(rèn)為是全雙工的。

1.1 分區(qū)分配模型

分區(qū)分配的核心思想是在滿足資源約束的條件下，最小化分區(qū)中的最大任務(wù)數(shù)、通信代價和內(nèi)存占用，將完成某些航電功能的所有任務(wù)分配到各個分區(qū)。

1.1.1 分區(qū)分配符號定義

在藍印中定義的任務(wù)集合可表示為

SΓ={τ1,τ2,…,τnΓ}

(1)

式中：τ為IMA系統(tǒng)中的任務(wù)；nΓ為任務(wù)總數(shù)。

分區(qū)的集合可表示為

SP={P1,P2，…,PnP}

(2)

式中，Pj表示1個分區(qū)，則有

Pj={τa,τb,…,τi}。

(3)

(4)

(5)

此時，任務(wù)τi可表示為τi,j。

1.1.2 分區(qū)分配目標(biāo)

分區(qū)分配將劃分的任務(wù)組分配到各自的分區(qū)，主要包含以下3個分配目標(biāo)。

1) 最小化分區(qū)中的最大任務(wù)數(shù)。

為了使各個分區(qū)的任務(wù)數(shù)量差距較小，從而優(yōu)化第2層分配結(jié)果中處理節(jié)點的負(fù)載標(biāo)準(zhǔn)差，需要最小化每個分區(qū)的最大任務(wù)數(shù)量，即

(6)

2) 最小化分區(qū)的通信代價。

ARINC653 Part4[12]中刪除了分區(qū)內(nèi)通信的開銷，因此，本文不考慮同一分區(qū)任務(wù)相互通信的開銷，通信代價表征為所有任務(wù)之間的通信開銷減去同一分區(qū)內(nèi)任務(wù)之間的通信開銷，即

(7)

3) 最小化分區(qū)的內(nèi)存占用。

分區(qū)的內(nèi)存占用表征為分區(qū)內(nèi)所有任務(wù)運行時占用內(nèi)存之和，則有

(8)

1.1.3 分區(qū)資源約束

分區(qū)內(nèi)的任務(wù)應(yīng)滿足以下約束。

1) 可調(diào)度性約束。

定義1(任務(wù)CPU利用率) 任務(wù)τi的CPU利用率ui為

(9)

定義2(分區(qū)CPU利用率) 分區(qū)Pj的CPU利用率Uj為分區(qū)中所有任務(wù)的CPU利用率之和，即

(10)

(11)

式中，Cj,Uj分別表示分區(qū)中優(yōu)先級高于任務(wù)τi的任務(wù)的WCET和CPU利用率，由此,可得出單一分區(qū)中任務(wù)可調(diào)度的一個充分條件為

(12)

2) 任務(wù)分配約束。

IMA架構(gòu)運行時不允許任務(wù)在分區(qū)間遷移，因此，所有的任務(wù)同一時刻只能被分配到同一分區(qū)，并且所有的任務(wù)都要被分配，即

(13)

1.1.4 基于可行性法則的分區(qū)分配模型

第一層分配模型的構(gòu)建采用可行性法則[14]，根據(jù)1.1.2節(jié)可得出優(yōu)化目標(biāo)為

(14)

式中：β1，β2和β3為歸一化系數(shù)，分別為任務(wù)總數(shù)的倒數(shù)、任務(wù)所需帶寬總量的倒數(shù)和任務(wù)所需內(nèi)存總量的倒數(shù)。由1.1.3節(jié)可得分區(qū)分配劃分的懲罰函數(shù)為

(15)

(16)

1.2 處理節(jié)點分配模型

在IMA架構(gòu)中，各個處理節(jié)點有相應(yīng)的硬件資源約束，運行在處理節(jié)點上的分區(qū)占用的資源不能超過處理節(jié)點所擁有的資源，此外，單一處理節(jié)點的負(fù)載如果過大會影響系統(tǒng)的實時性，因此，在保證資源約束的同時，還要保證處理節(jié)點的負(fù)載均衡。

1.2.1 處理節(jié)點分配符號定義

(17)

(18)

1.2.2 處理節(jié)點分配目標(biāo)

處理節(jié)點分配將分區(qū)分配到各處理節(jié)點，主要包含以下3個分配目標(biāo)。

1) 最小化處理節(jié)點負(fù)載的標(biāo)準(zhǔn)差。

(19)

(20)

式中，γ1，γ2和γ3為負(fù)載權(quán)重，可根據(jù)不同的偏好選擇負(fù)載權(quán)重，本文取γ1=γ2=0.3，γ3=0.4，則有

(21)

2) 最小化處理節(jié)點通信代價。

ARINC653規(guī)范中定義同一處理節(jié)點中的分區(qū)采用內(nèi)存通信，不同處理節(jié)點中的分區(qū)通過機載網(wǎng)絡(luò)總線通信，由于內(nèi)存總線通信相比網(wǎng)絡(luò)總線通信要更加高效、可靠，因此，優(yōu)先將通信量大的分區(qū)分配到同一處理節(jié)點。此外，由于內(nèi)存總線相對于網(wǎng)絡(luò)總線帶寬要大得多，因此本文忽略分區(qū)間通信占用的內(nèi)存總線。基于上述分配原則，通信代價表征為所有分區(qū)的總通信代價減去被分配到同一處理節(jié)點的分區(qū)之間的通信代價，即

(22)

3) 最小化處理節(jié)點內(nèi)存占用。

(23)

1.2.3 處理節(jié)點資源約束

處理節(jié)點中的分區(qū)應(yīng)滿足以下約束。

1) 可調(diào)度性約束。

定義4在IMA架構(gòu)中，總存在一個足夠小的主時間框架TRL和一組最小分區(qū)系數(shù)ηk，且各任務(wù)參數(shù)滿足

(24)

2) 網(wǎng)絡(luò)帶寬約束。

每個處理節(jié)點中運行的分區(qū)占用總帶寬不能超過該節(jié)點的最大帶寬約束，表示為

(25)

3) 內(nèi)存約束。

每個處理節(jié)點運行的分區(qū)占用的總內(nèi)存不能超過該節(jié)點最大的內(nèi)存約束，表示為

(26)

4) 分區(qū)分配約束。

每個分區(qū)都應(yīng)被分配到相應(yīng)的處理節(jié)點，且只能被分配到一個處理節(jié)點，即

(27)

1.2.4 基于可行性法則的節(jié)點分配模型

由1.2.2節(jié)可得到分區(qū)在處理節(jié)點上分配的優(yōu)化目標(biāo)為

(28)

式中：ω1,ω2和ω3為歸一化系數(shù)，分別為處理節(jié)點總數(shù)的倒數(shù)、處理節(jié)點總帶寬的倒數(shù)和處理節(jié)點內(nèi)存總量的倒數(shù)。由1.2.3節(jié)可得到分區(qū)在處理節(jié)點上分配的懲罰函數(shù)為

PP=

(29)

(30)

2 基于改進NSGA-Ⅱ算法的資源分配

文獻[16]提出的NSGA-Ⅱ算法引入了快速非支配排序思想和精英保存策略，使得算法具有更好的收斂性和收斂速度，更適用于多目標(biāo)優(yōu)化問題。

雖然NSGA-Ⅱ算法在針對多目標(biāo)優(yōu)化問題時相比傳統(tǒng)遺傳算法有一定的優(yōu)勢，但仍存在一些缺陷，例如，NSGA-Ⅱ算法在種群初始化時通常采用隨機生成的方式，導(dǎo)致初始種群遍歷性較差，可能使算法陷入局部最優(yōu)；此外，NSGA-Ⅱ算法的遺傳操作通常采用固定參數(shù)的模擬二進制交叉、多項式變異，導(dǎo)致算法在搜索過程中的移動空間較小，容易過早收斂，可能無法得到全局最優(yōu)解。

針對以上NSGA-Ⅱ算法的缺陷，對算法做出以下改進：1) 引入混沌Logistic映射進行種群初始化，提升初始種群的遍歷性；2) 引入自適應(yīng)交叉、變異算子，保證種群多樣性并提升收斂速度。

2.1 混沌Logistic映射實數(shù)編碼

傳統(tǒng)的實數(shù)編碼采用隨機函數(shù)生成初始種群，種群均勻度較差。本文采用混沌Logistic映射實數(shù)編碼，混沌映射生成的序列在解空間內(nèi)分布較為均勻，因此能提高初始種群的遍歷性，從而避免某個分區(qū)中沒有分配任務(wù)的情況，混沌Logistic映射[17]表示為

zi+1=[b×θ×zi×(1-zi)] 0

(31)

式中：θ為控制參數(shù)，當(dāng)θ>3.57且zi≠0.25,0.5,0.75時，系統(tǒng)進入混沌狀態(tài)。本文設(shè)定θ=4，z0=0.298 3；b為染色體基因位的上界，在第一、第二層分配中分別為分區(qū)個數(shù)和處理節(jié)點個數(shù)。第一層分配的染色體編碼可視為一個數(shù)組，其中，數(shù)組各個位置的下標(biāo)表示任務(wù)編號，值表示分區(qū)編號；第二層分配的編碼方式與第一層類似，數(shù)組X各個位置的下標(biāo)表示分區(qū)編號，值表示處理節(jié)點編號。

2.2 自適應(yīng)交叉、變異概率

在遺傳操作中，交叉和變異對算法的收斂性有重要影響。交叉概率太小會導(dǎo)致種群中產(chǎn)生新個體的速度變慢，從而降低算法的搜索速度；而交叉概率過大，則容易導(dǎo)致個體產(chǎn)生速度過快，使算法收斂到局部最優(yōu)解。同理，變異概率過小會導(dǎo)致種群失去多樣性，從而過早收斂；而過大的變異概率則可能破壞種群中的優(yōu)秀個體，對最優(yōu)個體的適應(yīng)度造成影響[18]。傳統(tǒng)NSGA-Ⅱ算法將交叉、變異概率設(shè)置為一個固定值，在進化前期可能導(dǎo)致搜索緩慢，后期導(dǎo)致優(yōu)秀解集丟失。

針對傳統(tǒng)交叉、變異算子的缺點，引入自適應(yīng)交叉、變異算子。由于在進化初期，種群中個體的差異較大，此時應(yīng)設(shè)置較小的交叉概率和較大的變異概率，增加種群產(chǎn)生新個體的速度，加強算法的搜索能力。在進化后期，由于種群經(jīng)過非支配排序和精英策略的篩選，個體之間的差異變小，且適應(yīng)度較好，此時，應(yīng)設(shè)置較大的交叉概率和較小的變異概率，保證算法的收斂性和種群的多樣性。因此，自適應(yīng)交叉、變異算子表征為隨著算法迭代次數(shù)的增加，交叉概率增加，變異概率減小，算式如下

(32)

式中：pc,new,pc,old,pm,new和pm,old分別為當(dāng)前代數(shù)的交叉概率，上一代的交叉概率，當(dāng)前代數(shù)的變異概率和上一代的變異概率；ng為當(dāng)前迭代次數(shù)；G為總迭代次數(shù)。

2.3 算法描述

改進NSGA-Ⅱ算法的主要步驟如下：

2) 生成K個個體作為初始父代種群，輸入初始交叉、變異概率pc，pm；

3) 計算初始種群中個體的適應(yīng)度；

4) 開始迭代，執(zhí)行選擇、自適應(yīng)交叉變異，生成新的X個子代個體；

5) 合并父代和子代種群；

6) 對合并后的種群進行非支配排序和擁擠度距離計算；

7) 根據(jù)非支配排序和擁擠度距離計算結(jié)果，在合并的種群中找出K個較優(yōu)秀的個體進入下一次迭代；

8) 判斷是否達到迭代次數(shù)G，若未達到最大進化代數(shù)則跳轉(zhuǎn)至步驟4)，否則迭代結(jié)束，輸出Pareto最優(yōu)解。

3 算例及仿真驗證

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

在一定范圍內(nèi)隨機生成任務(wù)參數(shù)，表1給出了各個任務(wù)的具體參數(shù)，生成18個任務(wù)分配到8個分區(qū)，再將8個分區(qū)分配到3個處理節(jié)點。

表1 任務(wù)參數(shù)Table 1 Task parameters

設(shè)置改進NSGA-Ⅱ算法初始交叉概率pc=1，初始變異概率pm=1/H，H為染色體基因個數(shù)。任務(wù)被分配到分區(qū)后，根據(jù)EDF調(diào)度策略賦予任務(wù)優(yōu)先級，即截止時間早的任務(wù)優(yōu)先級高。

算法計算后得出Pareto解，在第1層分配的Pareto解中選取適應(yīng)度最小的個體作為第2層分配的輸入，在第2層分配的Pareto解中選取適應(yīng)度最小的個體作為分配方案的最終解。

3.2 實驗結(jié)果分析

1) 分區(qū)分配結(jié)果。

第一步，先將18個任務(wù)分配到8個分區(qū)中，將種群規(guī)模設(shè)置為200，迭代次數(shù)為200，在滿足約束條件的情況下求優(yōu)化目標(biāo)的最小值，采用改進的NSGA-Ⅱ算法，與傳統(tǒng)NSGA-Ⅱ算法相比，隨著迭代次數(shù)的增加，種群中適應(yīng)度最小個體的適應(yīng)度變化如圖1所示。

圖1 分區(qū)分配適應(yīng)度變化(18個任務(wù))Fig.1 Partition allocation adaptability changes(18 missions)

由圖1可知，改進后的NSGA-Ⅱ算法收斂速度相比改進前有明顯提升，改進前收斂至適應(yīng)度最小值需要117次迭代，而改進后僅需21次迭代。

分配結(jié)果如表2所示。

表2 任務(wù)分配結(jié)果Table 2 Task allocation results

2) 節(jié)點分配結(jié)果。

第二步,將8個分區(qū)分配到3個100 Mibit/s帶寬、256 MiB內(nèi)存的同構(gòu)處理節(jié)點中，算法改進前后種群中適應(yīng)度最小個體的適應(yīng)度函數(shù)變化如圖2所示。

圖2 節(jié)點分配適應(yīng)度變化(18個任務(wù))Fig.2 Node allocation adaptability changes (18 missions)

由圖2可知，改進NGSA-Ⅱ算法相對改進之前有更好的收斂速度和更小的適應(yīng)度，同時,由于第一步分配的結(jié)果較好和混沌編碼的遍歷性較好，改進NSGA-Ⅱ算法實驗第二步初始種群的最小適應(yīng)度較小。

分配結(jié)果如表3所示。

表3 分區(qū)分配結(jié)果Table 3 Partition allocation result

由式(24)可得出任務(wù)滿足可調(diào)度性充分條件。各處理節(jié)點負(fù)載如表4所示。

表4 各處理節(jié)點負(fù)載(3個處理節(jié)點)Table 4 Load of each processing node(3 processing nodes)

由表4可知，改進NSGA-Ⅱ算法相比傳統(tǒng)NSGA-Ⅱ算法分配結(jié)果有以下優(yōu)勢：1) 3個處理節(jié)點的帶寬總占用由112 Mibit/s減小到98 Mibit/s;2) NSGA-Ⅱ算法的分配結(jié)果中處理節(jié)點的內(nèi)存占用差距較大，并在N2節(jié)點出現(xiàn)了內(nèi)存滿載的狀況，改進后的分配結(jié)果內(nèi)存占用較為均衡;3) 由式(24)計算可得改進前負(fù)載標(biāo)準(zhǔn)差為0.151 8，改進后為0.144 5，負(fù)載標(biāo)準(zhǔn)差降低了4.55%。

3.3 算法有效性測試

為測試算法的有效性，增大任務(wù)規(guī)模。隨機生成50個任務(wù)，分配到16個分區(qū)中，再將16個分區(qū)分配到6個處理節(jié)點中。由于增大了解空間的范圍，將迭代次數(shù)增加到500，其余參數(shù)不變。

1) 分區(qū)分配結(jié)果。

適應(yīng)度函數(shù)的變化如圖3(a)所示。

圖3 分區(qū)及節(jié)點分配適應(yīng)度變化(50個任務(wù))Fig.3 Partition and node allocation adaptability changes(50 missions)

2) 節(jié)點分配結(jié)果。

同樣選擇100 Mibit/s帶寬，256 MiB內(nèi)存的同構(gòu)處理節(jié)點，將16個分區(qū)分配到6個處理節(jié)點中。

適應(yīng)度函數(shù)的變化如圖3(b)所示，由圖3可知，改進NSGA-Ⅱ算法在處理50個任務(wù)的分配問題時，相比傳統(tǒng)NSGA-Ⅱ算法效果更好，有較快的收斂速度和較小的適應(yīng)度。

各處理節(jié)點負(fù)載如表5所示。

表5 各處理節(jié)點負(fù)載(6個處理節(jié)點)Table 5 Load of each processing node(6 processing nodes)

由式(24)可知，任務(wù)均可調(diào)度，由表5可知，傳統(tǒng)NSGA-Ⅱ算法的分配結(jié)果中出現(xiàn)了N3節(jié)點CPU利用率到達90.32%的情況，而改進NSGA-Ⅱ算法則避免了某一處理節(jié)點CPU利用率過高的情況；由式(24)計算可得改進前負(fù)載標(biāo)準(zhǔn)差為0.210 4，改進后為0.170 8，負(fù)載標(biāo)準(zhǔn)差降低了21.05%，改進NSGA-Ⅱ算法對增大規(guī)模后的分配問題性能提升作用更加明顯。

4 結(jié)束語

為解決IMA系統(tǒng)的資源分配問題，采用改進NSGA-Ⅱ算法對IMA資源模型進行優(yōu)化，并擴大分配規(guī)模驗證算法的可行性，在實驗中得到以下結(jié)論：

1) 在算法性能方面，改進NSGA-Ⅱ算法在IMA資源分配問題上能在更少的迭代次數(shù)中收斂，并具有更好的適應(yīng)度，證明改進后的算法具有一定的優(yōu)越性；

2) 在算法可行性方面，分別對18個任務(wù)和50個任務(wù)的分配問題進行實驗驗證，均能夠在滿足約束條件的情況下完成分配；

3) 在負(fù)載均衡方面，改進NSGA-Ⅱ算法能有效避免某一處理節(jié)點負(fù)載過大的情況，在大規(guī)模分配問題中這種提升更加明顯，將負(fù)載標(biāo)準(zhǔn)差降低21.05%。

實驗結(jié)果表明，本文算法能有效解決IMA架構(gòu)的資源分配問題，能得到更優(yōu)的分配結(jié)果，該算法在IMA架構(gòu)的設(shè)計中具有較高的工程價值。