航天器分布式智能計(jì)算體系的數(shù)學(xué)建模與調(diào)度算法研究

李金哲，王 磊

0 引 言

目前國(guó)內(nèi)外航天器計(jì)算體系結(jié)構(gòu)主要包括三種方式：基于串口的計(jì)算體系結(jié)構(gòu)、基于內(nèi)部總線的計(jì)算體系結(jié)構(gòu)以及基于串口和內(nèi)部總線混合的計(jì)算體系結(jié)構(gòu).但是這些計(jì)算體系結(jié)構(gòu)從本質(zhì)上來說都是以計(jì)算機(jī)為中心的主從式星型拓?fù)浣Y(jié)構(gòu).在節(jié)點(diǎn)通訊時(shí)，一般僅能與計(jì)算機(jī)進(jìn)行點(diǎn)對(duì)點(diǎn)通訊，無法實(shí)現(xiàn)任意節(jié)點(diǎn)之間的高速實(shí)時(shí)互聯(lián).舊有體系的局限性也對(duì)航天器的性能產(chǎn)生了限制：大量物理系統(tǒng)的參數(shù)不能通過計(jì)算體系傳遞到信息系統(tǒng)的各個(gè)節(jié)點(diǎn)，導(dǎo)致航天器自主管理與生存能力不足；同時(shí)為了可靠性，各節(jié)點(diǎn)設(shè)計(jì)了大量冗余模塊，資源消耗過多；目前航天器的計(jì)算節(jié)點(diǎn)大多是預(yù)先設(shè)定好功能的專用節(jié)點(diǎn)，若其發(fā)生故障將導(dǎo)致航天器部分功能的缺失，嚴(yán)重情況下甚至將威脅整星的安全.要解決這些問題，不僅要建立具有自組織能力的智能計(jì)算體系，將節(jié)點(diǎn)通用化并利用高速總線網(wǎng)絡(luò)互相連接，利用整體的計(jì)算能力為單個(gè)節(jié)點(diǎn)提供冗余與備份；還要在該體系中高效的進(jìn)行任務(wù)調(diào)度，其本質(zhì)就是尋找一種分配策略[1].基于該策略，可以將任務(wù)分配給不同的節(jié)點(diǎn)，以實(shí)現(xiàn)任務(wù)在可用資源之間的合理分配與高效執(zhí)行[2].不合適的任務(wù)調(diào)度策略不僅可能造成計(jì)算資源的嚴(yán)重浪費(fèi)，降低系統(tǒng)的運(yùn)行效率，還容易造成系統(tǒng)中節(jié)點(diǎn)負(fù)載不均衡，長(zhǎng)期負(fù)載過重的節(jié)點(diǎn)的壽命將受到影響，嚴(yán)重時(shí)將威脅系統(tǒng)的安全.

分布式計(jì)算體系的任務(wù)調(diào)度問題是一個(gè)NP完全問題[3]，難以使用窮舉法對(duì)其求解，而近年來，智能優(yōu)化算法在分布式計(jì)算體系的任務(wù)調(diào)度問題中的應(yīng)用研究越來越廣泛，文獻(xiàn)[4]使用了遺傳算法以最快完成任務(wù)為目標(biāo)求解了任務(wù)調(diào)度問題；文獻(xiàn)[5]使用了粒子群算法以能耗最低為目標(biāo)實(shí)現(xiàn)了任務(wù)調(diào)度；文獻(xiàn)[6]使用了蟻群算法以負(fù)載均衡為目標(biāo)實(shí)現(xiàn)了任務(wù)調(diào)度.各種算法都存在著其優(yōu)勢(shì)與不足，遺傳算法可以進(jìn)行快速全局搜索，但其參數(shù)較多，實(shí)現(xiàn)較為復(fù)雜且容易陷入局部最優(yōu)；粒子群算法較遺傳算法擁有更快的收斂速度，且參數(shù)較少，實(shí)現(xiàn)起來較為容易，但其局部搜索能力也有所欠缺；蟻群算法擁有良好的尋優(yōu)能力，但由于算法初期的信息素匱乏，導(dǎo)致收斂緩慢.且目前研究分布式計(jì)算體系任務(wù)調(diào)度算法時(shí)，多數(shù)是進(jìn)行單目標(biāo)優(yōu)化，對(duì)多目標(biāo)優(yōu)化的任務(wù)調(diào)度問題研究較少，由于多個(gè)優(yōu)化目標(biāo)互相之間往往存在沖突，無法同時(shí)達(dá)到最優(yōu)，因此尋找多目標(biāo)的相對(duì)最優(yōu)解成為相關(guān)研究的重點(diǎn)與難點(diǎn).

本文首先對(duì)航天器分布式智能計(jì)算體系進(jìn)行數(shù)學(xué)建模，給出了任務(wù)調(diào)度問題的多目標(biāo)優(yōu)化模型；然后結(jié)合了粒子群算法全局搜集能力強(qiáng)、收斂速度快和蟻群算法尋優(yōu)能力強(qiáng)的優(yōu)勢(shì)，同時(shí)又對(duì)二者分別設(shè)計(jì)了進(jìn)一步的優(yōu)化算法，將粒子群算法生成的調(diào)度結(jié)果對(duì)蟻群算法進(jìn)行初始化，利用蟻群算法生成了最終的調(diào)度結(jié)果，實(shí)現(xiàn)了任務(wù)調(diào)度算法性能的提升，使計(jì)算體系適應(yīng)時(shí)域上不斷變化的用戶需求和系統(tǒng)狀態(tài)，處于健康、高效地運(yùn)轉(zhuǎn)狀態(tài).

1 智能計(jì)算體系模型

1.1 智能計(jì)算體系的組成

本文所描述的分布式智能計(jì)算體系在物理上由三部分組成：若干個(gè)專用或通用的計(jì)算節(jié)點(diǎn)、高速總線網(wǎng)絡(luò)以及用于公共存儲(chǔ)的固態(tài)大容量存儲(chǔ)器.

其中，各個(gè)節(jié)點(diǎn)通過高速總線網(wǎng)絡(luò)進(jìn)行連接，相互通訊.而大容量存儲(chǔ)器存儲(chǔ)有智能應(yīng)用的程序，還有存儲(chǔ)智能應(yīng)用程序的位置描述文件，各個(gè)節(jié)點(diǎn)可根據(jù)位置描述文件通過高速總線網(wǎng)絡(luò)從存儲(chǔ)器相應(yīng)位置下載所需的應(yīng)用程序；節(jié)點(diǎn)獲取任務(wù)后，會(huì)在大容量存儲(chǔ)器中寫入運(yùn)行描述文件，運(yùn)行描述文件中包含任務(wù)執(zhí)行節(jié)點(diǎn)的信息和任務(wù)執(zhí)行程度的信息，當(dāng)該節(jié)點(diǎn)出現(xiàn)故障無法繼續(xù)執(zhí)行任務(wù)時(shí)，其余節(jié)點(diǎn)可以根據(jù)任務(wù)執(zhí)行程度繼續(xù)執(zhí)行該任務(wù)，提高計(jì)算體系的運(yùn)轉(zhuǎn)效率[7].大容量存儲(chǔ)器還存儲(chǔ)不斷增加的實(shí)時(shí)大數(shù)據(jù)，用于在線的智能學(xué)習(xí)和訓(xùn)練.

1.2 智能計(jì)算體系的節(jié)點(diǎn)模型

設(shè)初始計(jì)算體系中含有m個(gè)節(jié)點(diǎn)，則計(jì)算體系可以表示為一個(gè)集合S={s1,s2…sm},為了對(duì)節(jié)點(diǎn)的狀態(tài)進(jìn)行描述，需要建立節(jié)點(diǎn)的數(shù)學(xué)模型，使用以下幾個(gè)指標(biāo)來表征當(dāng)前節(jié)點(diǎn)的狀態(tài)：

1) 計(jì)算裕度

計(jì)算節(jié)點(diǎn)的主頻決定了它的峰值計(jì)算能力，這是一個(gè)固定的量.用占空比μi(0≤μi≤1)可以描述當(dāng)前時(shí)刻節(jié)點(diǎn)的計(jì)算裕度.

占空比μi是單位時(shí)間內(nèi)CPU進(jìn)行任務(wù)計(jì)算的時(shí)間所占的比例，它直接描述的是CPU當(dāng)前的負(fù)載情況，μi與時(shí)間和任務(wù)分配方式有關(guān)，即μi=f(Δ,t),Δ為當(dāng)前任務(wù)分配方式，t為時(shí)間，當(dāng)任務(wù)被分配到節(jié)點(diǎn)后，由于其預(yù)期完成時(shí)間是給定的，所以也就確定了計(jì)算節(jié)點(diǎn)在每個(gè)脈沖周期需要進(jìn)行的運(yùn)算次數(shù)，從而確定單位時(shí)間內(nèi)CPU的有效工作時(shí)間，即為當(dāng)前CPU的負(fù)載情況.

當(dāng)任務(wù)發(fā)布表更新時(shí)，各節(jié)點(diǎn)通過檢查自身占空比得到負(fù)載情況，用峰值計(jì)算能力減去當(dāng)前負(fù)載即為此時(shí)節(jié)點(diǎn)的計(jì)算裕度.實(shí)際中為了延長(zhǎng)節(jié)點(diǎn)的壽命，提高節(jié)點(diǎn)的可靠度，往往不希望節(jié)點(diǎn)長(zhǎng)期處于滿負(fù)荷運(yùn)行的狀態(tài)，可以人工設(shè)置一個(gè)占空比的上限μmaxi(0≤μi≤μmaxi<1)，用該上限減去當(dāng)前負(fù)載即為節(jié)點(diǎn)此時(shí)的計(jì)算裕度.

2) 剩余存儲(chǔ)能力

剩余存儲(chǔ)能力是指節(jié)點(diǎn)本地空閑動(dòng)態(tài)存儲(chǔ)器的大小，單位為兆字節(jié)(Mbytes).節(jié)點(diǎn)在執(zhí)行任務(wù)時(shí)需要從大容量存儲(chǔ)器中讀取該智能應(yīng)用程序及其運(yùn)行描述，并將之復(fù)制到本節(jié)點(diǎn)的動(dòng)態(tài)存儲(chǔ)器的空閑分區(qū)，因此足夠的剩余存儲(chǔ)能力是節(jié)點(diǎn)執(zhí)行任務(wù)的必要條件，不滿足任務(wù)剩余存儲(chǔ)能力要求的節(jié)點(diǎn)無法參與該任務(wù)的競(jìng)標(biāo).

3) 實(shí)時(shí)能耗

節(jié)點(diǎn)在工作過程中將產(chǎn)生能耗，其能耗與當(dāng)前負(fù)載有關(guān)，當(dāng)前節(jié)點(diǎn)占空比越高，能耗越高.

CPU的能耗與負(fù)載是正相關(guān)的，CPU的負(fù)載情況可以由CPU占空比μ來表示，這是一個(gè)在實(shí)際應(yīng)用中很容易獲取的參數(shù).首先建立計(jì)算體系的能耗模型，將CPU占空比映射到系統(tǒng)能耗上,即pcpu=f(μ).根據(jù)相關(guān)研究，CPU利用率與能耗存在線性相關(guān)的關(guān)系[8]，如式(1)所示：

Pcpu=mPmax+μ(1-m)Pmax

(1)

1.3 智能計(jì)算體系的任務(wù)模型

智能計(jì)算體系中用戶的需求本質(zhì)上是一種應(yīng)用，它是一段可安裝的程序，已經(jīng)裝載于大容量存儲(chǔ)器之中.包括代碼、任務(wù)需求、運(yùn)行描述和任務(wù)表四個(gè)部分：其中代碼是可執(zhí)行、可復(fù)制的，包括BSS、data和代碼段；任務(wù)需求是關(guān)于對(duì)存儲(chǔ)量、運(yùn)算量的描述，為一個(gè)數(shù)組；運(yùn)行描述是該程序已經(jīng)被執(zhí)行程度的表述，是由一組動(dòng)態(tài)數(shù)據(jù)表達(dá)；任務(wù)表用于發(fā)布該應(yīng)用，是一個(gè)數(shù)組.

本文將任務(wù)模型中不可再分解的程序記為task0，一個(gè)任務(wù)由一個(gè)或多個(gè)task0構(gòu)成，且task0之間相互獨(dú)立，各個(gè)task0的任務(wù)長(zhǎng)度和占用存儲(chǔ)已知.若任務(wù)可以分解為多個(gè)task0，那么執(zhí)行該任務(wù)的過程中，可將其分解并將多個(gè)task0交由計(jì)算體系中不同的計(jì)算節(jié)點(diǎn)來完成.可以用一個(gè)計(jì)算任務(wù)包含task0的個(gè)數(shù)、任務(wù)長(zhǎng)度和所占存儲(chǔ)空間來描述該任務(wù)，記第i個(gè)計(jì)算任務(wù)為taski，則taski={λtask0i,task_lengthi,task_memoryi},其中λtask0i為包含task0的個(gè)數(shù)；task_lengthi為任務(wù)長(zhǎng)度，單位為百萬條指令(MI,million instructions)；task_memoryi為所占存儲(chǔ)空間，單位為兆字節(jié).

2 任務(wù)調(diào)度問題的優(yōu)化模型

設(shè)當(dāng)前需要系統(tǒng)執(zhí)行的計(jì)算任務(wù)taski由n個(gè)task0組成，則計(jì)算體系中的任務(wù)調(diào)度問題可以描述為：在計(jì)算體系中，有n個(gè)相互獨(dú)立的task0分配給計(jì)算體系中m個(gè)計(jì)算節(jié)點(diǎn)來執(zhí)行(n>m).其中任務(wù)集表示為T={task01,task02…task0n}，計(jì)算節(jié)點(diǎn)集表示為S={s1,s2…sm}，task0j表示第j個(gè)子任務(wù)，j∈{1,2,…n}；si表示第i個(gè)節(jié)點(diǎn)，i∈{1,2,…m}.每個(gè)子任務(wù)僅由一個(gè)節(jié)點(diǎn)執(zhí)行.任務(wù)集T={task01,task02…task0n}與計(jì)算節(jié)點(diǎn)集S={s1,s2…sm}的分配關(guān)系可以用矩陣X表示為：

(2)

2.1 優(yōu)化目標(biāo)

1) 執(zhí)行任務(wù)時(shí)間最短

對(duì)用戶來說，期望計(jì)算體系可以盡快的完成計(jì)算任務(wù)，設(shè)ETij為子任務(wù)task0j在節(jié)點(diǎn)si的期望運(yùn)行時(shí)間，與映射關(guān)系X類似，可得運(yùn)行時(shí)間矩陣ET如下.

(3)

(4)

式中，length_task0j為task0j的長(zhǎng)度，單位為百萬條指令MI，million instructions，process_si為節(jié)點(diǎn)si的執(zhí)行速度，單位是MIPS，即每秒處理百萬條的指令數(shù).設(shè)bi為第j個(gè)子任務(wù)開始執(zhí)行的時(shí)間，CTij(i∈{1,2,…m}，j∈{1,2,…n})為子任務(wù)task0j在節(jié)點(diǎn)si的期望完成時(shí)間，max{CTij}為計(jì)算體系完成整個(gè)計(jì)算任務(wù)的時(shí)間,則有

CTij=bj+ETij

(5)

CXmax=max{CTij}

(6)

當(dāng)CXmax最小時(shí)，系統(tǒng)可以以最快的速度執(zhí)行計(jì)算任務(wù).

2) 能耗最低

智能計(jì)算體系的正常運(yùn)轉(zhuǎn)需要充足的能源供應(yīng)，期望智能計(jì)算體系在達(dá)到服務(wù)質(zhì)量要求并滿足用戶的計(jì)算需求的情況下，盡可能減少能源消耗.

CPU是計(jì)算密集型任務(wù)中最主要的能耗部件，因此主要以CPU能耗為建模依據(jù)，其占空比與能耗存在一種線性相關(guān)的能耗模型如式(1)，第i個(gè)節(jié)點(diǎn)在時(shí)間t內(nèi)的能耗可表示為式(7)

(7)

其中i∈{1,2,…m}，系統(tǒng)的總能耗表示為式(8)

(8)

當(dāng)WXsys最小時(shí)，計(jì)算體系的能耗最低.

3) 負(fù)載均衡

計(jì)算體系中的計(jì)算節(jié)點(diǎn)處于同等的地位，在運(yùn)行過程中，期望它們處于一種負(fù)載均衡的狀態(tài)，即沒有長(zhǎng)期高負(fù)荷或負(fù)載過低的節(jié)點(diǎn).

(9)

(10)

此種分配方案下計(jì)算體系的負(fù)載均衡度LBX定義如式(11)

(11)

LBX最小時(shí)，整個(gè)計(jì)算體系的負(fù)載最為均衡.

2.2 任務(wù)調(diào)度的代價(jià)函數(shù)

基于2.1節(jié)所述的優(yōu)化目標(biāo)，任務(wù)調(diào)度問題的代價(jià)函數(shù)為

minCXmax

(12)

minWXsys

(13)

minLBX

(14)

約束條件為

xij∈{0,1},i∈{1,2,…m},j∈{1,2,…n}

(15)

(16)

0≤μi(t)≤1

(17)

代價(jià)函數(shù)(12)代表了系統(tǒng)執(zhí)行任務(wù)的時(shí)間最短；代價(jià)函數(shù)(13)代表了系統(tǒng)的能耗最低；代價(jià)函數(shù)(14)代表了系統(tǒng)負(fù)載最為均衡.約束條件(15)中，xij=1代表任務(wù)j由節(jié)點(diǎn)i執(zhí)行；約束(16)表示每個(gè)任務(wù)僅能由一個(gè)計(jì)算節(jié)點(diǎn)執(zhí)行；約束(17)代表每個(gè)節(jié)點(diǎn)的占空比不能超過1，即節(jié)點(diǎn)均不能超負(fù)荷運(yùn)行.問題的解為任務(wù)集T={task01,task02…task0n}與計(jì)算節(jié)點(diǎn)集S={s1,s2...sm}的分配關(guān)系矩陣X.

2.3 多目標(biāo)優(yōu)化的帕累托最優(yōu)模型

在實(shí)際工程中，代價(jià)函數(shù)(12)～(14)之間是不可能同時(shí)滿足的，使三者同時(shí)達(dá)到最小的唯一解不存在.這是一個(gè)典型的適用于帕累托最優(yōu)[9]的問題，帕累托最優(yōu)是指無法在不使群體中任何個(gè)體狀況受損的情況下，提升群體中任何個(gè)體狀況的情況.對(duì)于任務(wù)調(diào)度問題的優(yōu)化，同樣期望能在不影響其他代價(jià)函數(shù)的情況下，對(duì)某個(gè)代價(jià)函數(shù)進(jìn)行優(yōu)化，最終實(shí)現(xiàn)帕累托最優(yōu)狀態(tài).

對(duì)于代價(jià)函數(shù)(12)～(14)來說，任意兩個(gè)解之間可能存在兩種關(guān)系：(1)一個(gè)解優(yōu)于另一個(gè)解；(2)兩個(gè)解之間沒有解優(yōu)于對(duì)方.本文利用帕累托占優(yōu)條件來判斷兩個(gè)解之間的關(guān)系，設(shè)f1和f2是代價(jià)函數(shù)(12)～(14)的兩個(gè)解，若f1的一個(gè)代價(jià)函數(shù)嚴(yán)格優(yōu)于f2，且f1另兩個(gè)代價(jià)函數(shù)均不嚴(yán)格劣于f2，則稱f1對(duì)f2帕累托占優(yōu)，如式(18)所示

(18)

式中，gi(i∈{1,2,3}),gj(j∈{1,2,3})分別代表代價(jià)函數(shù)(12)～(14).最終將形成一個(gè)解集，這個(gè)解集中的所有解均不比其余解更優(yōu)，這個(gè)解集即為帕累托最優(yōu)前沿，其中所有的解均為帕累托最優(yōu)解.

在帕累托最優(yōu)前沿中選擇最優(yōu)解的方法是根據(jù)具體需求而變化的，本文選取距離評(píng)價(jià)指標(biāo)法[10]選擇最優(yōu)解，以能耗、完成時(shí)間、負(fù)載均衡度為坐標(biāo)構(gòu)建一個(gè)空間直角坐標(biāo)系，則帕累托最優(yōu)解集中的各解在此直角系中的坐標(biāo)即可確定，則解集中存在至多三個(gè)解，分別使能耗最低、完成時(shí)間最短、負(fù)載最為均衡，選取這幾個(gè)解對(duì)應(yīng)的單項(xiàng)最優(yōu)值為三個(gè)坐標(biāo)，即產(chǎn)生了一個(gè)虛擬的最理想解，然后計(jì)算各解與虛擬最理想解的距離，距離最短者就是我們選擇的解.

3 任務(wù)調(diào)度算法設(shè)計(jì)

期望任務(wù)調(diào)度算法能兼具快速全局搜索能力和良好的局部尋優(yōu)能力，遺傳算法和粒子群算法均可快速全局搜索且局部尋優(yōu)能力均較弱，但粒子群算法收斂更快，且參數(shù)較少易于實(shí)現(xiàn)，而蟻群算法的局部尋優(yōu)能力較強(qiáng).故先將粒子群算法和蟻群算法進(jìn)行改良，再將它們結(jié)合起來，利用粒子群算法的快速全局搜索能力生成一個(gè)初始調(diào)度方案，用該初始調(diào)度方案初始化蟻群算法，利用蟻群算法良好的局部尋優(yōu)能力，得到最終的任務(wù)調(diào)度方案.

3.1 改進(jìn)的粒子群算法

基本的粒子群算法適用于連續(xù)域中的極值搜索，而計(jì)算體系中的執(zhí)行任務(wù)節(jié)點(diǎn)選擇問題是離散問題，因此需要對(duì)調(diào)度方案進(jìn)一步的合理處理，方可進(jìn)行粒子群算法的迭代.

基本粒子群的速度和位置公式如下

(19)

(20)

為提高任務(wù)調(diào)度算法粒子群部分的性能，對(duì)慣性權(quán)重ω進(jìn)行動(dòng)態(tài)調(diào)整，初期選取較大的慣性權(quán)重，擴(kuò)大算法的全局搜索能力，隨著迭代次數(shù)的增加線性遞減，實(shí)現(xiàn)對(duì)迭代后期的局部搜索精度的提高，設(shè)預(yù)定最大迭代次數(shù)為tmax，ω∈[ωmin,ωmax]，則第t次迭代的慣性權(quán)重ωt為

(21)

此時(shí)，粒子群算法的速度更新公式如式(22)

(22)

在運(yùn)行任務(wù)調(diào)度算法的粒子群算法部分時(shí)，速度直接按照式(22)更新，而位置向量按式(20)更新后將違背定義時(shí)每一位上均為整數(shù)的設(shè)定，所以要對(duì)位置的更新做進(jìn)一步的處理[11]，方法如式(23)

xij(t+1)=

(23)

式中，|xij(t+1)|表示對(duì)xij(t+1)先取絕對(duì)值，然后向上取整, mod(|xij(t+1)|,m)表示xij(t+1)的絕對(duì)值對(duì)m進(jìn)行取模運(yùn)算，通過這種進(jìn)一步的處理方式，將位置向量的各位合理均勻地映射到預(yù)設(shè)的取值范圍，完成對(duì)位置向量的更新.

3.2 改進(jìn)的蟻群算法

用粒子群算法得到的調(diào)度結(jié)果對(duì)蟻群算法進(jìn)行初始化，將粒子群算法中的向量形式轉(zhuǎn)化為式(2)所示的矩陣形式，生成一組節(jié)點(diǎn)集，通過蟻群算法從節(jié)點(diǎn)集中生成一組節(jié)點(diǎn)，達(dá)到調(diào)度目的.

迭代過程中，第k只螞蟻在結(jié)點(diǎn)i處選擇結(jié)點(diǎn)j作為下一個(gè)結(jié)點(diǎn)的概率為

(24)

當(dāng)m只螞蟻均完成一次游歷后，各路徑上的信息素將按照式(25)進(jìn)行更新

(25)

(26)

為提高算法的性能并提高算法的運(yùn)行速度，在蟻群算法中加入精英策略，引入精英螞蟻e，即具有迄今最優(yōu)游歷Te的人工螞蟻，在信息素更新時(shí)對(duì)精英螞蟻穿越過的所有邊再額外增加信息素，對(duì)Te進(jìn)行加強(qiáng)，實(shí)現(xiàn)對(duì)優(yōu)秀個(gè)體的保護(hù)，降低最優(yōu)解丟失的可能性.信息素更新公式如式(27)

(27)

(28)

式中，Q為常數(shù)；W為一權(quán)重系數(shù)，Le為精英螞蟻e所完成的迄今最優(yōu)游歷Te的長(zhǎng)度.

任務(wù)調(diào)度算法的蟻群部分按照式(27)更新信息素，并按照式(24)進(jìn)行位置轉(zhuǎn)移，當(dāng)?shù)螖?shù)達(dá)到預(yù)先設(shè)定值時(shí)，算法停止運(yùn)行.

3.3 算法流程

Step1 定義任務(wù)調(diào)度問題的3個(gè)目標(biāo)函數(shù).

Step2 設(shè)定該選擇算法的相關(guān)參數(shù).

Step3 初始化粒子群的位置和速度.

Step4 計(jì)算每個(gè)粒子的目標(biāo)函數(shù)值，找出粒子個(gè)體局部帕累托最優(yōu)解集和全局帕累托最優(yōu)解集.

Step5 確定每個(gè)粒子的個(gè)體極值pbest和全局極值gbest.

Step6 對(duì)粒子速度和位置進(jìn)行更新.

Step7 如果達(dá)到設(shè)定的迭代次數(shù)，輸出任務(wù)分配的初始選擇結(jié)果，否則，跳轉(zhuǎn)至Step4.

Step8 根據(jù)粒子群算法得出的初始調(diào)度結(jié)果初始化蟻群算法的信息素.

Step9 螞蟻進(jìn)行路徑搜索.

Step10 每只螞蟻按照迭代關(guān)系選擇選擇下一節(jié)點(diǎn)，更新信息素時(shí)將三個(gè)目標(biāo)函數(shù)的值先各自乘以一個(gè)比例系數(shù)再相加作為路徑長(zhǎng)度，按照帕累托最優(yōu)選擇精英螞蟻并加強(qiáng)它的信息素，并把所選節(jié)點(diǎn)加入到調(diào)度列表.

Step11 蟻群算法達(dá)到最大迭代次數(shù)，保留全局螞蟻?zhàn)詈笠淮闹底鳛槿肿顑?yōu)解集合，算法結(jié)束，輸出調(diào)度結(jié)果.否則，跳轉(zhuǎn)至Step9.

4 仿真驗(yàn)證與結(jié)果分析

為了對(duì)本文提出的DPSO-EACO算法進(jìn)行評(píng)估，使用了澳大利亞墨爾本大學(xué)開發(fā)的分布式計(jì)算仿真平臺(tái)CloudSim[12]，對(duì)其中的DatacenterBroker類進(jìn)行擴(kuò)展添加自定義的任務(wù)調(diào)度算法即可對(duì)調(diào)度算法進(jìn)行仿真模擬.

選取了5個(gè)計(jì)算節(jié)點(diǎn)，運(yùn)算能力分別為{400MIPS,600MIPS,800MIPS,1000MIPS,1200MIPS}，分別在50個(gè)長(zhǎng)度在[5000MI,10000MI]之間的任務(wù)調(diào)度規(guī)模和500個(gè)長(zhǎng)度在[5000MI,10000MI]之間的任務(wù)調(diào)度規(guī)模下，使用離散粒子群算法(DPSO)和精英螞蟻算法(EACO)和本文的DPSO-EACO算法進(jìn)行了對(duì)比.離散粒子群部分，ωmax=0.9，ωmin=0.4,c1=c2=1.5,群體規(guī)模為20，迭代次數(shù)為40代；精英蟻群部分，群體規(guī)模為20，α=1,β=1,ρ=0.1,Q=10,迭代次數(shù)為160代.作為對(duì)比的DPSO算法的參數(shù)設(shè)置與離散粒子群部分參數(shù)相同，EACO算法的參數(shù)與精英蟻群部分相同，二者迭代次數(shù)均為200代.

首先仿真了以執(zhí)行時(shí)間最短為單一目標(biāo)的情況下，3種算法的性能對(duì)比，分別將3種算法各運(yùn)行20次，得到兩種調(diào)度規(guī)模的結(jié)果如圖1和圖2所示.

圖1 總?cè)蝿?wù)完成時(shí)間曲線(5個(gè)節(jié)點(diǎn)，50個(gè)任務(wù))Fig.1 Completion time curves of total tasks(5 nodes,50 tasks)

圖2 總?cè)蝿?wù)完成時(shí)間曲線(5個(gè)節(jié)點(diǎn)，500個(gè)任務(wù))Fig.2 Completion time curves of total tasks(5 nodes,500 tasks)

從上面的實(shí)驗(yàn)結(jié)果可以看出，設(shè)置50個(gè)子任務(wù)時(shí)，DPSO算法收斂速度較快，在迭代約20次后即收斂到約116.4 s完成任務(wù)，EACO算法在150代左右才完成收斂，但是優(yōu)化效果較好，約118.9 s完成任務(wù)，DPSO-EACO算法在120代左右完成收斂，優(yōu)化效果最好，約109.6 s完成任務(wù)，可見DPSO-EACO算法雖然比DPSO算法收斂的慢，但是優(yōu)化效果提高了約6.8 s；DPSO-EACO算法比EACO算法約早30代收斂，優(yōu)化效果也提高了約2.2 s.設(shè)置500個(gè)子任務(wù)時(shí)，DPSO算法約30代收斂到1 178 s,EACO算法約10代收斂到1 123 s，DPSO-EACO算法約43代收斂到1 116 s，可見隨著任務(wù)數(shù)的增多， DPSO-EACO算法與EACO算法和DPSO算法相比依然具有更優(yōu)的優(yōu)化效果.

通過兩種調(diào)度規(guī)模下的仿真實(shí)驗(yàn)，結(jié)果表明本文提出的DPSO-EACO算法在單一目標(biāo)下的時(shí)間性能和優(yōu)化性能上都取得了比較好的提升.

然后演示了完成求解綜合能耗、完成時(shí)間、負(fù)載均衡度的多目標(biāo)調(diào)度帕累托最優(yōu)問題時(shí)3種算法的性能對(duì)比.設(shè)定Pmax=30 W,m=0.6.分別將3種算法各運(yùn)行20次，得到兩種調(diào)度規(guī)模的結(jié)果如以下各圖所示.

圖3 DPSO算法的帕累托最優(yōu)解集(5個(gè)節(jié)點(diǎn)，50個(gè)任務(wù))Fig.3 Pareto optimal solution set of DPSO algrithm(5 nodes,50 tasks)

圖4 EACO算法的帕累托最優(yōu)解集(5個(gè)節(jié)點(diǎn)，50個(gè)任務(wù))Fig.4 Pareto optimal solution set of EACO algrithm(5 nodes,50 tasks)

圖5 DPSO-EACO算法帕累托最優(yōu)解集(5個(gè)節(jié)點(diǎn)，50個(gè)任務(wù))Fig.5 Pareto optimal solution set of DPSO-EACE algrithm(5 nodes,50 tasks)

圖6 DPSO算法的帕累托最優(yōu)解集(5個(gè)節(jié)點(diǎn)，500個(gè)任務(wù))Fig.6 Pareto optimal solution set of DPSO algrithm(5 nodes,500 tasks)

圖7 EACO算法的帕累托最優(yōu)解集(5個(gè)節(jié)點(diǎn)，500個(gè)任務(wù))Fig.7 Pareto optimal solution set of EACO algrithm(5 nodes,500 tasks)

圖8 DPSO-EACO算法帕累托最優(yōu)解集(5個(gè)節(jié)點(diǎn)，500個(gè)任務(wù))Fig.8 Pareto optimal solution set of DPSO-EACO algrithm(5 nodes,500 tasks)

從上面的實(shí)驗(yàn)結(jié)果可以看出，當(dāng)調(diào)度規(guī)模為50個(gè)任務(wù)時(shí)，DPSO的優(yōu)化結(jié)果為時(shí)間Tmax1=125.78 s；能耗W1=2.99×104J；負(fù)載均衡度LB1=11.5，EACO的優(yōu)化結(jié)果為時(shí)間Tmax1=116.58 s，能耗W1=2.86×104J,負(fù)載均衡度LB1=3.5；DPSO-EACO算法的優(yōu)化結(jié)果為時(shí)間Tmax1=115.6 s；能耗W1=2.85×104J;負(fù)載均衡度LB1=3.1.當(dāng)調(diào)度規(guī)模為500個(gè)任務(wù)時(shí)，DPSO的優(yōu)化結(jié)果為時(shí)間Tmax2=1 128.5 s,能耗W2=2.75×105J,負(fù)載均衡度LB2=62；EACO的優(yōu)化結(jié)果為時(shí)間Tmax2=1 092.6 s；能耗W2=2.71×105J；負(fù)載均衡度LB2=18，DPSO-EACO的優(yōu)化結(jié)果為時(shí)間Tmax2=1 080 s；能耗W2=2.683×105J;負(fù)載均衡度LB2=12.與DPSO算法對(duì)比，DPSO-EACO算法的優(yōu)化性能獲得了大幅度提升，避免了DPSO算法過早收斂至局部極值的問題；與EACO算法對(duì)比，50個(gè)子任務(wù)時(shí)收斂相對(duì)較快，500個(gè)子任務(wù)時(shí)收斂略慢，但可以取得更好的優(yōu)化效果.以上仿真結(jié)果表明，在不同的調(diào)度規(guī)模下，DPSO-EACO算法均可以實(shí)現(xiàn)對(duì)較快速全局搜索與良好局部尋優(yōu)的兼顧.

5 結(jié) 論

本文給出了航天器分布式智能計(jì)算體系的數(shù)學(xué)模型和任務(wù)調(diào)度問題的多目標(biāo)帕累托最優(yōu)優(yōu)化模型.對(duì)離散粒子群算法中使用了動(dòng)態(tài)權(quán)重，在蟻群算法中使用了精英螞蟻，將優(yōu)化后的算法結(jié)合起來，利用粒子群算法生成初始調(diào)度方案，再用該初始調(diào)度方案初始化蟻群算法，使用蟻群算法生成最終的調(diào)度結(jié)果.綜合利用了粒子群算法的快速收斂速度和蟻群算法較強(qiáng)的局部尋優(yōu)能力，不僅在針對(duì)任務(wù)完成時(shí)間最短這一單一目標(biāo)優(yōu)化時(shí)取得了更好優(yōu)化性能；在尋找能耗最低、任務(wù)完成時(shí)間最短、負(fù)載均衡的帕累托最優(yōu)狀態(tài)時(shí)，也發(fā)揮了更優(yōu)的優(yōu)化性能.