發布時間：所屬分類：工程師職稱論文瀏覽：1次
摘 要： 網格計算即分布式計算，是一門計算機科學。它研究如何把一個需要非常巨大的計算能力才能解決的問題分成許多小的部分，然后把這些部分分配給許多計算機進行處理，最后把這些計算結果綜合起來得到最終結果。本文是一篇統計與信息論壇投稿的論文范文，主要論述
網格計算即分布式計算，是一門計算機科學。它研究如何把一個需要非常巨大的計算能力才能解決的問題分成許多小的部分，然后把這些部分分配給許多計算機進行處理，最后把這些計算結果綜合起來得到最終結果。本文是一篇統計與信息論壇投稿的論文范文，主要論述了基于博弈策略的應急資源網格化調度研究。
摘 要：文章建立基于博弈策略的網格化應急資源調度模型，三個目標函數分別為：(1)完成任務花費的時間最小;(2)整個任務花費的費用最低;(3)任務的生存性。在建立模型之后，結合傳統的網格化調度算法，運用基于靜態貝葉斯博弈的多目標進化算法(SBG-MOEA)求解模型，得出Pareto最優解集，并針對模型結果將SBG-MOEA算法和經典的NSGA-∏算法進行了比較測試，發現算法SBG-MOEA在收斂性Pareto非支配解的分布性上都表現優異。決策者可以根據實際情況從最優解中選取最符合條件的解。
關鍵詞：突發事件,網格化調度,多目標優化,SBG-MOEA
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 引 言
作為網格計算中的一個關鍵性問題，網格任務調度受到了眾多研究學者的關注。網格利用互聯網或專用網絡邏輯上分離的各種資源(包括計算機資源、存儲資源等)連接起來，采用一定的網格調度算法，將這些任務合理分配到網絡節點上運行，達到充分利用資源的效用[1]。網格為用戶提供高性能的計算服務，然而對于用戶來說，網格確實透明的。為了提高資源利用率和縮短完成任務的時間，就要優化調度方法。因此，網格任務調度實質上是一類優化問題。已經被證實是一類NP完全問題[2]。
當前的網格任務調度算法并不能很好地解決其中存在的問題。我們利用基于博弈策略的多目標進化算法對網格任務調度進行求解，該方法主要考慮了任務完成時間、完成費用和任務的生存性三個方面的指標[3]。
1 網格任務調度概述
1.1 網格任務調度特點及目標
1.1.1 網格任務調度的特點
網格環境下，資源數量多，任務數目大，而且兩者的匹配關系復雜。這些使得網格任務調度具有以下幾個特點[4]：
(1)任務調度面向異構平臺;
(2)采用分布式并行的調度方法;
(3)調度與網絡節點內部策略無關;
(4)必須滿足擴展性要求。
1.1.2 網格任務調度的主要目標
網絡是一個分布性的異構系統。網絡上的一個程序可以看作一個任務集。調度問題就是要滿足性能要求和約束關系的前提，將眾多任務按照一種分配和執行順序將其分配到各網絡節點上。但網絡系統是復雜、異構和動態的，而且應用程序對各網絡節點的資源要求不同，另外對任務的調度順序也有要求等，這些問題的存在導致網格任務調度變得非常復雜。不好的調度算法會造成資源調度不合理，任務執行時間延長等問題。因此，網格任務調度算法的主要目的就是要優化調度，提高網格系統的計算性能。主要的性能指標如：負載均衡(Load Blancing)、最優跨度(Optimal Makespan)、服務質量QoS(Quality of Service)和經濟原則(Economic Principles)等[5]。
負載均衡，主要保證各個資源節點的負載達到均衡，不會出現某些節點任務分配過多，而其它一些節點“空閑”的現象;最優跨度是關于調度的長度的一個指標，長度越短越好。調度的長度是從第一個任務開始運行到最后一個任務運行完畢經歷的時間;服務質量，主要保障用戶的任務計算和資源需求等內容。它是對性能、可靠性和可用性等參數的一種表示、協商和管理機制;經濟原則，網格環境中的各個資源由于地理位置、機制和政策等因素的不同，其使用費用也不同，經濟原則的目標是盡量減少網格調度的費用。 1.2 網格調度算法現狀
在現有的研究中，網格調度算法已有大量成果，其中比較經典的有[6-8]：UDA(User Direetly Assigning)算法即用戶直接指派。這類算法主要是用戶直接將自己的任務指派給某個網格資源去執行。用戶往往不知道網格資源的狀態如何。而網格調度器僅僅按照用戶的指派，將相應任務發送給某個網格資源處理，其他的不多過問。OLB(Opportunistie Load Balaneing)即隨機負載均衡算法，其算法思想是：隨機的將某個任務分派給某個網格資源。這種方法通過隨機分配任務盡量使所有資源都處于工作狀態，對網格系統的負載均衡起到一定作用。MCT(Minimum Completion Time)即最小完成時間算法，其算法過程是：按照某一順序調度所有任務，對每個任務簡單的將其分配到最短完成預期的機器上。對于單個任務，該算法可以保證最短時間完成。MIN-MIN算法，其過程是將所有的待調度任務組成一個集合，從集合中找出預期完成時間最短的任務分配給相應的機器執行，從集合中刪除任務，繼續迭代，直到集合為空停止。MAX-MIN算法是選取最長執行時間作業進行執行，作業執行完畢后從集合中刪除，再執行新的調度。
以上傳統的調度算法更多的考慮對任務完成時間的優化。根據第一節網格調度問題的特點，網格調度除了最小化任務完成時間以外，還要考慮最小化資金花費、任務存在性等指標。該問題基于以下假設：每個網格資源單位占用時間花費的資金是不同的，顯然，運算速度快的機器其單位時間花費要小。因此以此任務調度需要同時優化三個目標：時間最短、花費最小、任務存在性，因此這是一個典型的多目標優化問題，兩個目標是一對相互矛盾的優化方向。顯然，通過傳統的網格調度算法很難解決該問題。
基于此本章提出了基于SBG-MOEA的網格調度算法。該算法首先對網格調度解空間進行遺傳編碼，通過基于靜態貝葉斯博弈模型的多目標遺傳算法找出符合網格調度的Pareto[9]解。因為基于博弈模型的多目標遺傳算法存在非支配排序和博弈張力兩方面的力量共同推動種群向Pareto前沿移動，因此該算法具有很強的全局尋優能力和快速收斂能力，適合于求解在線實時調度問題。
2 算法設計
2.1 問題描述及模型
設：有n個獨立任務T=T■，T■，…，T■，其中T■為第i個任務;m個計算機資源R=R■，R■，…，R■表示，其中R■為第j個計算機節點;X■=1表示把任務T■分配到計算資源R■上執行，否則為0;ET是一個n*m矩陣，為任務T■在計算節點上R■的預期執行時間，任務調度時b■表示資源R■的最早可用時間;CT■表示任務T■在計算機節點R■上的預期完成時間，CT■=b■+ET■;m個計算機單位時間價格為D=D■，D■，…，D■;m個計算機的單位時間執行的任務數為S=S■，S■，…，S■。
根據以上定義，考慮到目前網格任務調度主要考慮的是：(1)完成任務t時間最小化。(2)完成整個任務的費用最低。(3)現實計算節點可能會因為硬件錯誤或軟件錯誤不能保證任務的正常完成，因此還需要考慮任務的存在性即網格計算環境中任務在計算節點上能夠正常執行完成的概率[10]，因此待優化目標可以描述為：
f■T，R，X=maxX■×b■×ET■ (1)
CT，R，X=■■λ■×X■×ET■ (2)
DT，R，X=■■D■×X■×ET■ (3)
其中：λ表示計算節點的失效率，CT，R，X代表了網格任務調度所發生的無效情況的累積，它間接地反映了網格任務調度的存在性，其值越小，網格任務的存在性越大。
2.2 算法描述
2.2.1 編碼設計
多目標網格調度任務的解是x=x■，x■，…，x■，…，x■形式，其中n為任務數，x■∈R，它表示將任務T■分配給第x■個計算資源，因此本算法采用如下改進的比特編碼設計：
n
L L L
0010…101 0100…001 … 1010…011
如果計算資源總數為m個，那么每一個T■需要染色體的長度L=「log■M?�V，編碼的長度為n*「log■M?�V。
2.2.2 適應度函數
本文采用任務與資源相配對的關系構成了染色體基因，因為計算資源都是整數。因此，本算法中的變量值即每一段染色體的值也為整數，多目標網格調度優化問題可數學描述為如下的多目標優化問題：
MinF=f■，f■，f■
其中■，即目標函數f■T，R，X，CT，R，X和■■D■×X■×ET■的計算需要網格調度的參數信息，它由具體的問題來決定。這三個目標的求解都是最小化問題。
2.2.3 進化操作
針對具體的網格任務調度問題，在根據問題環境確定了染色體的編碼方式和適應度函數計算方法之后，接下來就是要利用我們提出的算法進行優化。主要包括初始化種群、博弈過程和更新歸檔集等。其中博弈模型描述如下：
博弈參與者，本文設計的多目標網格任務調度主要有完成時間和費用以及生存性三個目標，因為博弈參與人有三個，表示為P=P■，P■，P■;他們會根據收益情況―一定概率選擇合作或者懲罰策略，來取得最大的效用值。
種群在進化過程中對應這一個適應值矩陣，通過適應值矩陣我們可以求出收益矩陣，它表示其中一個參與者做出行動都會對另外一個參與者產生一定的收益，用U=■表示。那么他們的支付函數：每個博弈者的最終目標是最大化■u■，即各個博弈者通過博弈追求各個目標上的最優值。
戰略空間定義為：S=s■，s■，這里s■代表合作戰略，s■代表懲罰策略。
戰略概率矩陣定義為：PS=■，它是指一個參與者對另一個參與者選擇某種戰略的概率。 博弈的整個過程描述為：兩個目標對應的博弈參與者根據概率選取策略并采取行動，為了追求自身利益的最大化它們在每次行動后根據損益情況更新混合概率，以實現自己的目標。策略的選擇主要依據概率矩陣PS，矩陣的更新根據收益矩陣U。參與者對各個目標有個偏好程度，通過采取的策略來更新各個目標偏好。參與者對各個目標的偏好可以轉換為權值向量w
=w■，w■，…，w■，當參與者i選定了一個戰略后，將得到一個權值向量，根據這個權值向量計算種群個體的映射適應值，構造子種群，完成一次博弈過程。
2.2.4 算法流程
根據前面定義，整體算法流程如下：
Step1：初始化種群P0、概率矩陣PS，并初始化一個外部歸檔集，令迭代次數t=0;
Step2：每個博弈參與者給出自己的戰略，并采取相應行動;
Step3：產生一個新的種群，令t=t+1;
Step4：計算種群的適應值矩陣FIT，找出其中的非支配個體;
Step5：更新歸檔集，按照每個博弈參與者的收益情況更新概率矩陣等;
Step6：判斷是否滿足終止條件，如果滿足則輸出最終解，算法結束，否則轉到Step2。
3 實驗仿真分析
3.1 實驗參數設置
模擬的網格任務調度情況如下：
網格擁有計算資源數m，任務數n，則有的網格調度方式為m■個，這是一個NP問題：
(1)計算機上有被占用時間B=b■，b■，…，b■滿足5，15上隨機分布;
(2)任務的網格節點上執行時間滿足10，100上的隨機分布;
(3)每個節點的失效率λ■滿足10-4，10-3上均勻分布;
(4)單位時間執行指令數S=S■，S■，…，S■在1，5上隨機分布;
(5)計算機單位時間價格D與S滿足函數關系D=gS=0.5*S■+1.5。
3.2 實驗結果及分析
3.2.1 仿真實驗一
(1)測試問題
本實驗的主要目的是對比在不同數量的任務和資源情況下，多目標網格任務調度的優化效果，以及任務完成時間、完成費用和生存性兩個指標之間的關系。
(2)參數設置
實驗對比了在計算資源數為12 的情況下，任務數分別為300，400，600是求出的最優解的情況;還對比了任務數為400的情況下，計算資源數目分別為9和15的最優解情況。主要參數設置為：種群規模設為100，循環迭代為5 000，歸檔集大小100，交叉概率為0.6，變異概率為1/N。
(3)實驗結果與分析
實驗結果分別如圖1～圖5所示：
圖1～圖3主要對比了不同任務數下網格化調度結果，圖4和圖5對比了不同資源數量下的網格化調度結果。通過對上圖結果進行比較分析，可以得出如下結論：
(1)多目標網格任務調度問題屬于離散型的優化問題，其最優解是不連續的，形狀是不規則的，當資源數和任務數不斷增加時，圖5將分離的Pareto解連接起來更好地刻畫了網格調度問題的Pareto解的形狀;
(2)網格化調度的完成時間和任務的生存性以及完成任務費用三個指標是相互沖突的，不可能同時獲得三者的最優值，即不存在一種調度方式使三個目標同時處于最優的狀態;
(3)在計算資源一定的情況下，隨著調度任務數量的增加，網格化調度時間不斷增加，網格任務調度的失效性不斷增加，完成任務費用不斷降低。
3.2.2 仿真實驗二
(1)測試問題
本實驗的主要目的是對比本文算法和NSGA-∏算法在求解多目標網格任務調度問題上的效果。
(2)參數設定
網格調度的任務數為400，計算資源為12，其余參數如上節，主要參數兩種算法取相同的參數：種群規模設為100，循環迭代5 000次，歸檔集100，交叉概率0.6，變異概率0.002。
(3)實驗結果與分析
實驗進行50組，表1為兩種算法的收斂性和分布性指標在50組實驗求解結果的平均值。
從表1中我們可以看到，在解得分布性方面SBG-MOEA算法比NSGA∏差，但在解的收斂性分布方面明顯優于NSGA∏。網格化調度問題是離散型多目標優化問題，真正的Pareto前沿形狀也未必是均勻的，所以評價優化算法好壞主要看覆蓋性指標。從表1得出在求解網格化調度問題上優于NSGA∏算法。
4 小 結
本文首先介紹了網格任務調度的基本知識，包括網格任務調度的主要特點，主要目標以及網格任務調度的經典算法。然后針對基于完成時間和完成價格以及生存性的多目標網格化調度問題，提出了基于博弈策略的SBG-MOEA的網格化調度算法。通過實驗仿真和結果分析，表明該算法在解決多目標網格任務調度問題上具有較好的收斂性。
參考文獻：
[1] 杜曉麗，蔣昌俊，徐國榮，等. 一種基于模糊聚類的網格DAG任務圖調度算法[J]. 軟件學報，2010，17(11)：2277-2285.
[2] 徐志偉，馮百明，李偉. 網絡計算技術[M]. 北京：電子工業出版社，2004：93-124.
[3] 王樹鵬，云曉春，余翔湛. 基于生存性和MakesPan的多目標網格任務調度算法研究[J]. 通信學報，2011，27(2)：42-49.
[4] 魏東. 基于混合蟻群算法的網格任務調度研究[D]. 哈爾濱：哈爾濱工程大學(碩士學位論文)，2012：31-32.
[5] 張青. 網格環境下任務調度算法的應用研究[D]. 大連：大連海事大學(碩士學位論文)，2013：13-14.
[6] 薛桂香. 基于智能優化算法的網格任務調度策略研究[D]. 天津：天津大學(博士學位論文)，2010：7-8.
[7] 張維迎. 博弈論與經濟信息學[M]. 上海：上海人民出版社，2008：106-135.
相關期刊簡介：《統計與信息》堅持為社會主義服務的方向，堅持以馬克思列寧主義、毛澤東思想和鄧小平理論為指導，貫徹“百花齊放、百家爭鳴”和“古為今用、洋為中用”的方針，堅持實事求是、理論與實際相結合的嚴謹學風，傳播先進的科學文化知識，弘揚民族優秀科學文化，促進國際科學文化交流，探索防災科技教育、教學及管理諸方面的規律，活躍教學與科研的學術風氣，為教學與科研服務。
