曹杰　王少鵬

摘 要：文章建立基于博弈策略的網(wǎng)格化應(yīng)急資源調(diào)度模型，三個目標函數(shù)分別為：（1）完成任務(wù)花費的時間最??；（2）整個任務(wù)花費的費用最低；（3）任務(wù)的生存性。在建立模型之后，結(jié)合傳統(tǒng)的網(wǎng)格化調(diào)度算法，運用基于靜態(tài)貝葉斯博弈的多目標進化算法（SBG-MOEA）求解模型，得出Pareto最優(yōu)解集，并針對模型結(jié)果將SBG-MOEA算法和經(jīng)典的NSGA-∏算法進行了比較測試，發(fā)現(xiàn)算法SBG-MOEA在收斂性Pareto非支配解的分布性上都表現(xiàn)優(yōu)異。決策者可以根據(jù)實際情況從最優(yōu)解中選取最符合條件的解。

關(guān)鍵詞：突發(fā)事件；網(wǎng)格化調(diào)度；多目標優(yōu)化；SBG-MOEA

中圖分類號：F253 文獻標識碼：A

Abstract： The essay establishes meshing model of emergency resource schedule on the basis of game strategies， and the three objective functions are respectively： （1）It takes minimum time to finish the task； （2）It takes the minimum cost for the whole task； （3）Survivability of the task. After establishing the model， combine with traditional meshing schedule algorithm to solve the model with multi-objective evolutionary algorithm（SBG-MOEA）which is based on static bayesian game， then the optimal solution set of Pareto has been concluded. Based on the model result， the comparison test is done between algorithm SBG-MOEA and classical algorithm NSGA-∏. Then it has been found that algorithm SBG-MOEA shows excellent distinction in distributivity of non-dominated solution for convergence Pareto. The decision maker can select the solution which most matches condition from the optimal solution set according to reality.

Key words： emergency； meshing schedule； multi-objective optimization； SBG-MOEA

0 引 言

作為網(wǎng)格計算中的一個關(guān)鍵性問題，網(wǎng)格任務(wù)調(diào)度受到了眾多研究學者的關(guān)注。網(wǎng)格利用互聯(lián)網(wǎng)或?qū)Ｓ镁W(wǎng)絡(luò)邏輯上分離的各種資源（包括計算機資源、存儲資源等）連接起來，采用一定的網(wǎng)格調(diào)度算法，將這些任務(wù)合理分配到網(wǎng)絡(luò)節(jié)點上運行，達到充分利用資源的效用[1]。網(wǎng)格為用戶提供高性能的計算服務(wù)，然而對于用戶來說，網(wǎng)格確實透明的。為了提高資源利用率和縮短完成任務(wù)的時間，就要優(yōu)化調(diào)度方法。因此，網(wǎng)格任務(wù)調(diào)度實質(zhì)上是一類優(yōu)化問題。已經(jīng)被證實是一類NP完全問題[2]。

當前的網(wǎng)格任務(wù)調(diào)度算法并不能很好地解決其中存在的問題。我們利用基于博弈策略的多目標進化算法對網(wǎng)格任務(wù)調(diào)度進行求解，該方法主要考慮了任務(wù)完成時間、完成費用和任務(wù)的生存性三個方面的指標[3]。

1 網(wǎng)格任務(wù)調(diào)度概述

1.1 網(wǎng)格任務(wù)調(diào)度特點及目標

1.1.1 網(wǎng)格任務(wù)調(diào)度的特點

網(wǎng)格環(huán)境下，資源數(shù)量多，任務(wù)數(shù)目大，而且兩者的匹配關(guān)系復雜。這些使得網(wǎng)格任務(wù)調(diào)度具有以下幾個特點[4]：

（1）任務(wù)調(diào)度面向異構(gòu)平臺；

（2）采用分布式并行的調(diào)度方法；

（3）調(diào)度與網(wǎng)絡(luò)節(jié)點內(nèi)部策略無關(guān)；

（4）必須滿足擴展性要求。

1.1.2 網(wǎng)格任務(wù)調(diào)度的主要目標

網(wǎng)絡(luò)是一個分布性的異構(gòu)系統(tǒng)。網(wǎng)絡(luò)上的一個程序可以看作一個任務(wù)集。調(diào)度問題就是要滿足性能要求和約束關(guān)系的前提，將眾多任務(wù)按照一種分配和執(zhí)行順序?qū)⑵浞峙涞礁骶W(wǎng)絡(luò)節(jié)點上。但網(wǎng)絡(luò)系統(tǒng)是復雜、異構(gòu)和動態(tài)的，而且應(yīng)用程序?qū)Ω骶W(wǎng)絡(luò)節(jié)點的資源要求不同，另外對任務(wù)的調(diào)度順序也有要求等，這些問題的存在導致網(wǎng)格任務(wù)調(diào)度變得非常復雜。不好的調(diào)度算法會造成資源調(diào)度不合理，任務(wù)執(zhí)行時間延長等問題。因此，網(wǎng)格任務(wù)調(diào)度算法的主要目的就是要優(yōu)化調(diào)度，提高網(wǎng)格系統(tǒng)的計算性能。主要的性能指標如：負載均衡（Load Blancing）、最優(yōu)跨度（Optimal Makespan）、服務(wù)質(zhì)量QoS（Quality of Service）和經(jīng)濟原則（Economic Principles）等[5]。

負載均衡，主要保證各個資源節(jié)點的負載達到均衡，不會出現(xiàn)某些節(jié)點任務(wù)分配過多，而其它一些節(jié)點“空閑”的現(xiàn)象；最優(yōu)跨度是關(guān)于調(diào)度的長度的一個指標，長度越短越好。調(diào)度的長度是從第一個任務(wù)開始運行到最后一個任務(wù)運行完畢經(jīng)歷的時間；服務(wù)質(zhì)量，主要保障用戶的任務(wù)計算和資源需求等內(nèi)容。它是對性能、可靠性和可用性等參數(shù)的一種表示、協(xié)商和管理機制；經(jīng)濟原則，網(wǎng)格環(huán)境中的各個資源由于地理位置、機制和政策等因素的不同，其使用費用也不同，經(jīng)濟原則的目標是盡量減少網(wǎng)格調(diào)度的費用。endprint

1.2 網(wǎng)格調(diào)度算法現(xiàn)狀

在現(xiàn)有的研究中，網(wǎng)格調(diào)度算法已有大量成果，其中比較經(jīng)典的有[6-8]：UDA（User Direetly Assigning）算法即用戶直接指派。這類算法主要是用戶直接將自己的任務(wù)指派給某個網(wǎng)格資源去執(zhí)行。用戶往往不知道網(wǎng)格資源的狀態(tài)如何。而網(wǎng)格調(diào)度器僅僅按照用戶的指派，將相應(yīng)任務(wù)發(fā)送給某個網(wǎng)格資源處理，其他的不多過問。OLB（Opportunistie Load Balaneing）即隨機負載均衡算法，其算法思想是：隨機的將某個任務(wù)分派給某個網(wǎng)格資源。這種方法通過隨機分配任務(wù)盡量使所有資源都處于工作狀態(tài)，對網(wǎng)格系統(tǒng)的負載均衡起到一定作用。MCT（Minimum Completion Time）即最小完成時間算法，其算法過程是：按照某一順序調(diào)度所有任務(wù)，對每個任務(wù)簡單的將其分配到最短完成預期的機器上。對于單個任務(wù)，該算法可以保證最短時間完成。MIN-MIN算法，其過程是將所有的待調(diào)度任務(wù)組成一個集合，從集合中找出預期完成時間最短的任務(wù)分配給相應(yīng)的機器執(zhí)行，從集合中刪除任務(wù)，繼續(xù)迭代，直到集合為空停止。MAX-MIN算法是選取最長執(zhí)行時間作業(yè)進行執(zhí)行，作業(yè)執(zhí)行完畢后從集合中刪除，再執(zhí)行新的調(diào)度。

以上傳統(tǒng)的調(diào)度算法更多的考慮對任務(wù)完成時間的優(yōu)化。根據(jù)第一節(jié)網(wǎng)格調(diào)度問題的特點，網(wǎng)格調(diào)度除了最小化任務(wù)完成時間以外，還要考慮最小化資金花費、任務(wù)存在性等指標。該問題基于以下假設(shè)：每個網(wǎng)格資源單位占用時間花費的資金是不同的，顯然，運算速度快的機器其單位時間花費要小。因此以此任務(wù)調(diào)度需要同時優(yōu)化三個目標：時間最短、花費最小、任務(wù)存在性，因此這是一個典型的多目標優(yōu)化問題，兩個目標是一對相互矛盾的優(yōu)化方向。顯然，通過傳統(tǒng)的網(wǎng)格調(diào)度算法很難解決該問題。

基于此本章提出了基于SBG-MOEA的網(wǎng)格調(diào)度算法。該算法首先對網(wǎng)格調(diào)度解空間進行遺傳編碼，通過基于靜態(tài)貝葉斯博弈模型的多目標遺傳算法找出符合網(wǎng)格調(diào)度的Pareto[9]解。因為基于博弈模型的多目標遺傳算法存在非支配排序和博弈張力兩方面的力量共同推動種群向Pareto前沿移動，因此該算法具有很強的全局尋優(yōu)能力和快速收斂能力，適合于求解在線實時調(diào)度問題。

2 算法設(shè)計

2.1 問題描述及模型

設(shè)：有n個獨立任務(wù)T=T■，T■，…，T■，其中T■為第i個任務(wù)；m個計算機資源R=R■，R■，…，R■表示，其中R■為第j個計算機節(jié)點；X■=1表示把任務(wù)T■分配到計算資源R■上執(zhí)行，否則為0；ET是一個n*m矩陣，為任務(wù)T■在計算節(jié)點上R■的預期執(zhí)行時間，任務(wù)調(diào)度時b■表示資源R■的最早可用時間；CT■表示任務(wù)T■在計算機節(jié)點R■上的預期完成時間，CT■=b■+ET■；m個計算機單位時間價格為D=D■，D■，…，D■；m個計算機的單位時間執(zhí)行的任務(wù)數(shù)為S=S■，S■，…，S■。

根據(jù)以上定義，考慮到目前網(wǎng)格任務(wù)調(diào)度主要考慮的是：（1）完成任務(wù)t時間最小化。（2）完成整個任務(wù)的費用最低。（3）現(xiàn)實計算節(jié)點可能會因為硬件錯誤或軟件錯誤不能保證任務(wù)的正常完成，因此還需要考慮任務(wù)的存在性即網(wǎng)格計算環(huán)境中任務(wù)在計算節(jié)點上能夠正常執(zhí)行完成的概率[10]，因此待優(yōu)化目標可以描述為：

f■T，R，X=maxX■×b■×ET■ （1）

CT，R，X=■■λ■×X■×ET■ （2）

DT，R，X=■■D■×X■×ET■ （3）

其中：λ表示計算節(jié)點的失效率，CT，R，X代表了網(wǎng)格任務(wù)調(diào)度所發(fā)生的無效情況的累積，它間接地反映了網(wǎng)格任務(wù)調(diào)度的存在性，其值越小，網(wǎng)格任務(wù)的存在性越大。

2.2 算法描述

2.2.1 編碼設(shè)計

多目標網(wǎng)格調(diào)度任務(wù)的解是x=x■，x■，…，x■，…，x■形式，其中n為任務(wù)數(shù)，x■∈R，它表示將任務(wù)T■分配給第x■個計算資源，因此本算法采用如下改進的比特編碼設(shè)計：

n

L L L

0010…101 0100…001 … 1010…011

如果計算資源總數(shù)為m個，那么每一個T■需要染色體的長度L=「log■M？骎，編碼的長度為n*「log■M？骎。

2.2.2 適應(yīng)度函數(shù)

本文采用任務(wù)與資源相配對的關(guān)系構(gòu)成了染色體基因，因為計算資源都是整數(shù)。因此，本算法中的變量值即每一段染色體的值也為整數(shù)，多目標網(wǎng)格調(diào)度優(yōu)化問題可數(shù)學描述為如下的多目標優(yōu)化問題：

MinF=f■，f■，f■

其中■，即目標函數(shù)f■T，R，X，CT，R，X和■■D■×X■×ET■的計算需要網(wǎng)格調(diào)度的參數(shù)信息，它由具體的問題來決定。這三個目標的求解都是最小化問題。

2.2.3 進化操作

針對具體的網(wǎng)格任務(wù)調(diào)度問題，在根據(jù)問題環(huán)境確定了染色體的編碼方式和適應(yīng)度函數(shù)計算方法之后，接下來就是要利用我們提出的算法進行優(yōu)化。主要包括初始化種群、博弈過程和更新歸檔集等。其中博弈模型描述如下：

博弈參與者，本文設(shè)計的多目標網(wǎng)格任務(wù)調(diào)度主要有完成時間和費用以及生存性三個目標，因為博弈參與人有三個，表示為P=P■，P■，P■；他們會根據(jù)收益情況—一定概率選擇合作或者懲罰策略，來取得最大的效用值。

種群在進化過程中對應(yīng)這一個適應(yīng)值矩陣，通過適應(yīng)值矩陣我們可以求出收益矩陣，它表示其中一個參與者做出行動都會對另外一個參與者產(chǎn)生一定的收益，用U=■表示。那么他們的支付函數(shù)：每個博弈者的最終目標是最大化■u■，即各個博弈者通過博弈追求各個目標上的最優(yōu)值。

戰(zhàn)略空間定義為：S=s■，s■，這里s■代表合作戰(zhàn)略，s■代表懲罰策略。

戰(zhàn)略概率矩陣定義為：PS=■，它是指一個參與者對另一個參與者選擇某種戰(zhàn)略的概率。endprint

博弈的整個過程描述為：兩個目標對應(yīng)的博弈參與者根據(jù)概率選取策略并采取行動，為了追求自身利益的最大化它們在每次行動后根據(jù)損益情況更新混合概率，以實現(xiàn)自己的目標。策略的選擇主要依據(jù)概率矩陣PS，矩陣的更新根據(jù)收益矩陣U。參與者對各個目標有個偏好程度，通過采取的策略來更新各個目標偏好。參與者對各個目標的偏好可以轉(zhuǎn)換為權(quán)值向量w

=w■，w■，…，w■，當參與者i選定了一個戰(zhàn)略后，將得到一個權(quán)值向量，根據(jù)這個權(quán)值向量計算種群個體的映射適應(yīng)值，構(gòu)造子種群，完成一次博弈過程。

2.2.4 算法流程

根據(jù)前面定義，整體算法流程如下：

Step1：初始化種群P0、概率矩陣PS，并初始化一個外部歸檔集，令迭代次數(shù)t=0；

Step2：每個博弈參與者給出自己的戰(zhàn)略，并采取相應(yīng)行動；

Step3：產(chǎn)生一個新的種群，令t=t+1；

Step4：計算種群的適應(yīng)值矩陣FIT，找出其中的非支配個體；

Step5：更新歸檔集，按照每個博弈參與者的收益情況更新概率矩陣等；

Step6：判斷是否滿足終止條件，如果滿足則輸出最終解，算法結(jié)束，否則轉(zhuǎn)到Step2。

3 實驗仿真分析

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

模擬的網(wǎng)格任務(wù)調(diào)度情況如下：

網(wǎng)格擁有計算資源數(shù)m，任務(wù)數(shù)n，則有的網(wǎng)格調(diào)度方式為m■個，這是一個NP問題：

（1）計算機上有被占用時間B=b■，b■，…，b■滿足5，15上隨機分布；

（2）任務(wù)的網(wǎng)格節(jié)點上執(zhí)行時間滿足10，100上的隨機分布；

（3）每個節(jié)點的失效率λ■滿足10-4，10-3上均勻分布；

（4）單位時間執(zhí)行指令數(shù)S=S■，S■，…，S■在1，5上隨機分布；

（5）計算機單位時間價格D與S滿足函數(shù)關(guān)系D=gS=0.5*S■+1.5。

3.2 實驗結(jié)果及分析

3.2.1 仿真實驗一

（1）測試問題

本實驗的主要目的是對比在不同數(shù)量的任務(wù)和資源情況下，多目標網(wǎng)格任務(wù)調(diào)度的優(yōu)化效果，以及任務(wù)完成時間、完成費用和生存性兩個指標之間的關(guān)系。

（2）參數(shù)設(shè)置

實驗對比了在計算資源數(shù)為12 的情況下，任務(wù)數(shù)分別為300，400，600是求出的最優(yōu)解的情況；還對比了任務(wù)數(shù)為400的情況下，計算資源數(shù)目分別為9和15的最優(yōu)解情況。主要參數(shù)設(shè)置為：種群規(guī)模設(shè)為100，循環(huán)迭代為5 000，歸檔集大小100，交叉概率為0.6，變異概率為1/N。

（3）實驗結(jié)果與分析

實驗結(jié)果分別如圖1～圖5所示：

圖1～圖3主要對比了不同任務(wù)數(shù)下網(wǎng)格化調(diào)度結(jié)果，圖4和圖5對比了不同資源數(shù)量下的網(wǎng)格化調(diào)度結(jié)果。通過對上圖結(jié)果進行比較分析，可以得出如下結(jié)論：

（1）多目標網(wǎng)格任務(wù)調(diào)度問題屬于離散型的優(yōu)化問題，其最優(yōu)解是不連續(xù)的，形狀是不規(guī)則的，當資源數(shù)和任務(wù)數(shù)不斷增加時，圖5將分離的Pareto解連接起來更好地刻畫了網(wǎng)格調(diào)度問題的Pareto解的形狀；

（2）網(wǎng)格化調(diào)度的完成時間和任務(wù)的生存性以及完成任務(wù)費用三個指標是相互沖突的，不可能同時獲得三者的最優(yōu)值，即不存在一種調(diào)度方式使三個目標同時處于最優(yōu)的狀態(tài)；

（3）在計算資源一定的情況下，隨著調(diào)度任務(wù)數(shù)量的增加，網(wǎng)格化調(diào)度時間不斷增加，網(wǎng)格任務(wù)調(diào)度的失效性不斷增加，完成任務(wù)費用不斷降低。

3.2.2 仿真實驗二

（1）測試問題

本實驗的主要目的是對比本文算法和NSGA-∏算法在求解多目標網(wǎng)格任務(wù)調(diào)度問題上的效果。

（2）參數(shù)設(shè)定

網(wǎng)格調(diào)度的任務(wù)數(shù)為400，計算資源為12，其余參數(shù)如上節(jié)，主要參數(shù)兩種算法取相同的參數(shù)：種群規(guī)模設(shè)為100，循環(huán)迭代5 000次，歸檔集100，交叉概率0.6，變異概率0.002。

（3）實驗結(jié)果與分析

實驗進行50組，表1為兩種算法的收斂性和分布性指標在50組實驗求解結(jié)果的平均值。

從表1中我們可以看到，在解得分布性方面SBG-MOEA算法比NSGA∏差，但在解的收斂性分布方面明顯優(yōu)于NSGA∏。網(wǎng)格化調(diào)度問題是離散型多目標優(yōu)化問題，真正的Pareto前沿形狀也未必是均勻的，所以評價優(yōu)化算法好壞主要看覆蓋性指標。從表1得出在求解網(wǎng)格化調(diào)度問題上優(yōu)于NSGA∏算法。

4 小 結(jié)

本文首先介紹了網(wǎng)格任務(wù)調(diào)度的基本知識，包括網(wǎng)格任務(wù)調(diào)度的主要特點，主要目標以及網(wǎng)格任務(wù)調(diào)度的經(jīng)典算法。然后針對基于完成時間和完成價格以及生存性的多目標網(wǎng)格化調(diào)度問題，提出了基于博弈策略的SBG-MOEA的網(wǎng)格化調(diào)度算法。通過實驗仿真和結(jié)果分析，表明該算法在解決多目標網(wǎng)格任務(wù)調(diào)度問題上具有較好的收斂性。

參考文獻：

[1] 杜曉麗，蔣昌俊，徐國榮，等. 一種基于模糊聚類的網(wǎng)格DAG任務(wù)圖調(diào)度算法[J]. 軟件學報，2010，17（11）：2277-2285.

[2] 徐志偉，馮百明，李偉. 網(wǎng)絡(luò)計算技術(shù)[M]. 北京：電子工業(yè)出版社，2004：93-124.

[3] 王樹鵬，云曉春，余翔湛. 基于生存性和MakesPan的多目標網(wǎng)格任務(wù)調(diào)度算法研究[J]. 通信學報，2011，27（2）：42-49.

[4] 魏東. 基于混合蟻群算法的網(wǎng)格任務(wù)調(diào)度研究[D]. 哈爾濱：哈爾濱工程大學（碩士學位論文），2012：31-32.

[5] 張青. 網(wǎng)格環(huán)境下任務(wù)調(diào)度算法的應(yīng)用研究[D]. 大連：大連海事大學（碩士學位論文），2013：13-14.

[6] 薛桂香. 基于智能優(yōu)化算法的網(wǎng)格任務(wù)調(diào)度策略研究[D]. 天津：天津大學（博士學位論文），2010：7-8.

[7] 張維迎. 博弈論與經(jīng)濟信息學[M]. 上海：上海人民出版社，2008：106-135.

[8] 何建敏，劉春林，曹杰，等. 應(yīng)急管理與應(yīng)急系統(tǒng)——選址、調(diào)度與算法[M]. 北京：科技出版社，2007.

[9] Pareto V. Cours D' Economie politique， volume I and II[M]. Lausanne： F. Rouge， 1896.

[10] 王樹鵬，云曉春，魚翔湛. 基于生存性和 Makespan 的多目標網(wǎng)格任務(wù)調(diào)度算法研究[J]. 通信學報，2010，27（2）：42-49.endprint