航天器分布式智能計算體系的數學建模與調度算法研究

李金哲，王 磊

0 引 言

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

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

本文首先對航天器分布式智能計算體系進行數學建模，給出了任務調度問題的多目標優化模型；然后結合了粒子群算法全局搜集能力強、收斂速度快和蟻群算法尋優能力強的優勢，同時又對二者分別設計了進一步的優化算法，將粒子群算法生成的調度結果對蟻群算法進行初始化，利用蟻群算法生成了最終的調度結果，實現了任務調度算法性能的提升，使計算體系適應時域上不斷變化的用戶需求和系統狀態，處于健康、高效地運轉狀態.

1 智能計算體系模型

1.1 智能計算體系的組成

本文所描述的分布式智能計算體系在物理上由三部分組成：若干個專用或通用的計算節點、高速總線網絡以及用于公共存儲的固態大容量存儲器.

其中，各個節點通過高速總線網絡進行連接，相互通訊.而大容量存儲器存儲有智能應用的程序，還有存儲智能應用程序的位置描述文件，各個節點可根據位置描述文件通過高速總線網絡從存儲器相應位置下載所需的應用程序；節點獲取任務后，會在大容量存儲器中寫入運行描述文件，運行描述文件中包含任務執行節點的信息和任務執行程度的信息，當該節點出現故障無法繼續執行任務時，其余節點可以根據任務執行程度繼續執行該任務，提高計算體系的運轉效率[7].大容量存儲器還存儲不斷增加的實時大數據，用于在線的智能學習和訓練.

1.2 智能計算體系的節點模型

設初始計算體系中含有m個節點，則計算體系可以表示為一個集合S={s1,s2…sm},為了對節點的狀態進行描述，需要建立節點的數學模型，使用以下幾個指標來表征當前節點的狀態：

1) 計算裕度

計算節點的主頻決定了它的峰值計算能力，這是一個固定的量.用占空比μi(0≤μi≤1)可以描述當前時刻節點的計算裕度.

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

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

2) 剩余存儲能力

剩余存儲能力是指節點本地空閑動態存儲器的大小，單位為兆字節(Mbytes).節點在執行任務時需要從大容量存儲器中讀取該智能應用程序及其運行描述，并將之復制到本節點的動態存儲器的空閑分區，因此足夠的剩余存儲能力是節點執行任務的必要條件，不滿足任務剩余存儲能力要求的節點無法參與該任務的競標.

3) 實時能耗

節點在工作過程中將產生能耗，其能耗與當前負載有關，當前節點占空比越高，能耗越高.

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

Pcpu=mPmax+μ(1-m)Pmax

(1)

1.3 智能計算體系的任務模型

智能計算體系中用戶的需求本質上是一種應用，它是一段可安裝的程序，已經裝載于大容量存儲器之中.包括代碼、任務需求、運行描述和任務表四個部分：其中代碼是可執行、可復制的，包括BSS、data和代碼段；任務需求是關于對存儲量、運算量的描述，為一個數組；運行描述是該程序已經被執行程度的表述，是由一組動態數據表達；任務表用于發布該應用，是一個數組.

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

2 任務調度問題的優化模型

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

(2)

2.1 優化目標

1) 執行任務時間最短

對用戶來說，期望計算體系可以盡快的完成計算任務，設ETij為子任務task0j在節點si的期望運行時間，與映射關系X類似，可得運行時間矩陣ET如下.

(3)

(4)

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

CTij=bj+ETij

(5)

CXmax=max{CTij}

(6)

當CXmax最小時，系統可以以最快的速度執行計算任務.

2) 能耗最低

智能計算體系的正常運轉需要充足的能源供應，期望智能計算體系在達到服務質量要求并滿足用戶的計算需求的情況下，盡可能減少能源消耗.

CPU是計算密集型任務中最主要的能耗部件，因此主要以CPU能耗為建模依據，其占空比與能耗存在一種線性相關的能耗模型如式(1)，第i個節點在時間t內的能耗可表示為式(7)

(7)

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

(8)

當WXsys最小時，計算體系的能耗最低.

3) 負載均衡

計算體系中的計算節點處于同等的地位，在運行過程中，期望它們處于一種負載均衡的狀態，即沒有長期高負荷或負載過低的節點.

(9)

(10)

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

(11)

LBX最小時，整個計算體系的負載最為均衡.

2.2 任務調度的代價函數

基于2.1節所述的優化目標，任務調度問題的代價函數為

minCXmax

(12)

minWXsys

(13)

minLBX

(14)

約束條件為

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

(15)

(16)

0≤μi(t)≤1

(17)

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

2.3 多目標優化的帕累托最優模型

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

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

(18)

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

在帕累托最優前沿中選擇最優解的方法是根據具體需求而變化的，本文選取距離評價指標法[10]選擇最優解，以能耗、完成時間、負載均衡度為坐標構建一個空間直角坐標系，則帕累托最優解集中的各解在此直角系中的坐標即可確定，則解集中存在至多三個解，分別使能耗最低、完成時間最短、負載最為均衡，選取這幾個解對應的單項最優值為三個坐標，即產生了一個虛擬的最理想解，然后計算各解與虛擬最理想解的距離，距離最短者就是我們選擇的解.

3 任務調度算法設計

期望任務調度算法能兼具快速全局搜索能力和良好的局部尋優能力，遺傳算法和粒子群算法均可快速全局搜索且局部尋優能力均較弱，但粒子群算法收斂更快，且參數較少易于實現，而蟻群算法的局部尋優能力較強.故先將粒子群算法和蟻群算法進行改良，再將它們結合起來，利用粒子群算法的快速全局搜索能力生成一個初始調度方案，用該初始調度方案初始化蟻群算法，利用蟻群算法良好的局部尋優能力，得到最終的任務調度方案.

3.1 改進的粒子群算法

基本的粒子群算法適用于連續域中的極值搜索，而計算體系中的執行任務節點選擇問題是離散問題，因此需要對調度方案進一步的合理處理，方可進行粒子群算法的迭代.

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

(19)

(20)

為提高任務調度算法粒子群部分的性能，對慣性權重ω進行動態調整，初期選取較大的慣性權重，擴大算法的全局搜索能力，隨著迭代次數的增加線性遞減，實現對迭代后期的局部搜索精度的提高，設預定最大迭代次數為tmax，ω∈[ωmin,ωmax]，則第t次迭代的慣性權重ωt為

(21)

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

(22)

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

xij(t+1)=

(23)

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

3.2 改進的蟻群算法

用粒子群算法得到的調度結果對蟻群算法進行初始化，將粒子群算法中的向量形式轉化為式(2)所示的矩陣形式，生成一組節點集，通過蟻群算法從節點集中生成一組節點，達到調度目的.

迭代過程中，第k只螞蟻在結點i處選擇結點j作為下一個結點的概率為

(24)

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

(25)

(26)

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

(27)

(28)

式中，Q為常數；W為一權重系數，Le為精英螞蟻e所完成的迄今最優游歷Te的長度.

任務調度算法的蟻群部分按照式(27)更新信息素，并按照式(24)進行位置轉移，當迭代次數達到預先設定值時，算法停止運行.

3.3 算法流程

Step1 定義任務調度問題的3個目標函數.

Step2 設定該選擇算法的相關參數.

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

Step4 計算每個粒子的目標函數值，找出粒子個體局部帕累托最優解集和全局帕累托最優解集.

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

Step6 對粒子速度和位置進行更新.

Step7 如果達到設定的迭代次數，輸出任務分配的初始選擇結果，否則，跳轉至Step4.

Step8 根據粒子群算法得出的初始調度結果初始化蟻群算法的信息素.

Step9 螞蟻進行路徑搜索.

Step10 每只螞蟻按照迭代關系選擇選擇下一節點，更新信息素時將三個目標函數的值先各自乘以一個比例系數再相加作為路徑長度，按照帕累托最優選擇精英螞蟻并加強它的信息素，并把所選節點加入到調度列表.

Step11 蟻群算法達到最大迭代次數，保留全局螞蟻最后一代的值作為全局最優解集合，算法結束，輸出調度結果.否則，跳轉至Step9.

4 仿真驗證與結果分析

為了對本文提出的DPSO-EACO算法進行評估，使用了澳大利亞墨爾本大學開發的分布式計算仿真平臺CloudSim[12]，對其中的DatacenterBroker類進行擴展添加自定義的任務調度算法即可對調度算法進行仿真模擬.

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

首先仿真了以執行時間最短為單一目標的情況下，3種算法的性能對比，分別將3種算法各運行20次，得到兩種調度規模的結果如圖1和圖2所示.

圖1 總任務完成時間曲線(5個節點，50個任務)Fig.1 Completion time curves of total tasks(5 nodes,50 tasks)

圖2 總任務完成時間曲線(5個節點，500個任務)Fig.2 Completion time curves of total tasks(5 nodes,500 tasks)

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

通過兩種調度規模下的仿真實驗，結果表明本文提出的DPSO-EACO算法在單一目標下的時間性能和優化性能上都取得了比較好的提升.

然后演示了完成求解綜合能耗、完成時間、負載均衡度的多目標調度帕累托最優問題時3種算法的性能對比.設定Pmax=30 W,m=0.6.分別將3種算法各運行20次，得到兩種調度規模的結果如以下各圖所示.

圖3 DPSO算法的帕累托最優解集(5個節點，50個任務)Fig.3 Pareto optimal solution set of DPSO algrithm(5 nodes,50 tasks)

圖4 EACO算法的帕累托最優解集(5個節點，50個任務)Fig.4 Pareto optimal solution set of EACO algrithm(5 nodes,50 tasks)

圖5 DPSO-EACO算法帕累托最優解集(5個節點，50個任務)Fig.5 Pareto optimal solution set of DPSO-EACE algrithm(5 nodes,50 tasks)

圖6 DPSO算法的帕累托最優解集(5個節點，500個任務)Fig.6 Pareto optimal solution set of DPSO algrithm(5 nodes,500 tasks)

圖7 EACO算法的帕累托最優解集(5個節點，500個任務)Fig.7 Pareto optimal solution set of EACO algrithm(5 nodes,500 tasks)

圖8 DPSO-EACO算法帕累托最優解集(5個節點，500個任務)Fig.8 Pareto optimal solution set of DPSO-EACO algrithm(5 nodes,500 tasks)

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

5 結 論

本文給出了航天器分布式智能計算體系的數學模型和任務調度問題的多目標帕累托最優優化模型.對離散粒子群算法中使用了動態權重，在蟻群算法中使用了精英螞蟻，將優化后的算法結合起來，利用粒子群算法生成初始調度方案，再用該初始調度方案初始化蟻群算法，使用蟻群算法生成最終的調度結果.綜合利用了粒子群算法的快速收斂速度和蟻群算法較強的局部尋優能力，不僅在針對任務完成時間最短這一單一目標優化時取得了更好優化性能；在尋找能耗最低、任務完成時間最短、負載均衡的帕累托最優狀態時，也發揮了更優的優化性能.