基于貝葉斯決策的網格計算資源分配算法

李 昊，謝中江，侯哲生

(1.吉林師范大學計算機學院，吉林四平136000;2.吉林凱賽生物技術有限公司，吉林吉林132021;3.吉林化工學院機電工程學院，吉林吉林132022)

網格計算不同于常規分布式計算，網格環境的異構性和復雜性使得資源分配面臨很多不確定因素的影響，為了進行最優的資源分配，Martino等人提出了一些基于最優化理論的任務調度算法，比如依據遺傳算法［1-3］、蟻群算法［4-6］、函數構造法［7-9］等，這些算法從不同角度對任務調度最優解進行求解，均取得較好效果.在對任務進行資源分配的過程中，資源的狀態并非一成不變的，一個有效的任務調度算法，應該有效利用資源預報系統，對分配決策進行及時調整.網格計算中可以應用 NWS［10］、RPS［11］等基于時間序列的資源預報系統進行資源狀態的實時預報及分析.基于貝葉斯決策的網格計算資源分配算法正是應用了資源的預報和分析，將完全不確定型決策引入到任務調度算法中，更好的實現負載平衡和用戶QoS要求.

1 基于貝葉斯決策的決策模型

對用戶任務分配網格資源，可以看成是完全不確定型決策問題，網格計算的主要特點是網格結構的異構性、網格服務質量的不確定性，當用戶提交任務，任務運行情況取決于資源分配算法的優劣，當用戶任務有明確的完成時間要求時，資源分配不當會帶來一定的風險.在分配決策過程中可能會出現多種無法預料的狀態，這些事件出現的概率估計的正確程度直接影響到決策中收益期望值.為了更好的進行決策，在條件許可的情況下，可以進一步補充一些新的信息.補充信息可以通過計算機網絡以及網格應用程序執行性能監控和預報系統獲得.獲得新信息后，可以根據這些補充信息修正原來狀態時間出現的概率，并利用修正的概率分布重新進行決策.由于這種概率修正主要根據貝葉斯(Bayes)定理進行，故稱這種決策為貝葉斯決策.

1.1 分配算法的步驟

基于貝葉斯決策的網格計算資源分配算法通常分為3步進行.

1.1.1 根據先驗概率進行決策

網格資源分配算法首先根據以往情況及經驗對這些事件出現的概率進行估計，即得出先驗概率，然后依據先驗概率分布及期望值準則做出決策，選擇出最優方案，并得出相應最優期望值，記為EMV*(先).這也是多種任務調度優化算法的調度依據部分，由此得到的調度決策是本次用戶任務調度的基礎.

1.1.2 預驗分析

用戶任務開始調度，分配資源進行計算，資源的性能狀態和負載開始變化，依據之前信息的調度算法將無法適應新的變化，此時需要及時補充新的信息，在NWS等系統中，分布在資源上的sensor將周期返回狀態信息，并進行資源預報.在補充新信息之前，對補充新信息是否合算做出分析，從而決定是否補充新信息.

1.1.3 后驗分析

根據獲得的新信息，對先驗概率分布進行修正，得到后驗概率分布，在此基礎上做出決策，并計算出補充信息的價值.

1.2 分配算法的收益分析

因為性能監控和預報系統的預報準確程度以及本身就消耗掉的資源都是我們要考慮的因素.在Nimord/G［12］等基于經濟學資源分配和任務調度系統中，補充新信息意味著額外的費用開銷，采用了新信息則要求有明顯的收益.下面給出收益分析的具體方法.

1.2.1 確定已有的資源狀態θi，給出資源系統對應狀態出現的概率值.根據當前狀態進行最優調度算法的計算，確定調度方案dj在每種資源狀態θi的效益值uij，根據期望值準則，計算各方案效益期望值:

相應最優方案及期望值

1.2.2 接下來的預驗分析中，要估算出完全信息的價值(任何信息的價值均不會超過完全信息的價值)，并以它作為標準.當完全信息預報出現θk狀態時，問題變成確定性決策問題.最優方案顯然應由下式確定:

在完全信息下，決策所能獲得的最大收益期望值:

EPPI和EMV*(先)的差額即由于理想化的預報資源狀態，而即使調整調度策略而帶來的收益值，定義為完全信息的價值，記為EVPI:

1.2.3 很顯然，準確的預知資源接下來的狀態是不可能的，調度算法只能根據預報系統返回的狀態信息或者預報信息對之前的信息進行修正.通常，補充的新信息是通過對x1、x2、……、xs共s個狀態進行調查、實驗，預報其中哪種情況將出現，同時通過資料獲取條件概率P(xi|θj)，即實際出現狀態θj而預報xj的概率.

在已知先驗概率 p(θi)(i=1，2，…，m)及條件概率 P(xi| θj)(i=1，2，…，s;j=1，2，…，m)的基礎上，利用貝葉斯公式可計算出修正概率，即后驗概率:

根據計算的后驗概率，可預先做出決策的框架.假設補充信息預報將出現xk狀態，則用后驗修正概率分布 P(θi|xk)(j=1，2，…，m)，計算各方案的期望收益值，并依據期望值準則進行決策，得

一旦得到補充信息預報，即可按上述方式進行決策.需要注意的是，補充信息通常具有不確定性，因而，這樣的信息是不完全的，或說不是絕對準確的，因此，與完全信息相比，補充信息的價值不會大于完全信息的價值.

2 算法實現與分析

在文獻［13］中，已經實現了結合網絡資源預報的網絡資源分配算法，采用NWS進行網絡資源預報.在仿真試驗中，假設用戶任務deadline為3個時間單位，網格計算資源的可用性將決定用戶任務的完成情況，如果任務順利完成，產生效益5萬元，不能完成將損失1萬元，延遲運行，每時間單位損失0.2萬元.根據以往經驗，資源可用概率為30%.在該算法中，采用資源可用性預報，對資源可用的預報準確率為80%，對資源不可用的預報準確率為90%，預報需要支出0.08萬元.

這里對100個用戶任務進行隨機模擬，得出未采用貝葉斯決策和采用貝葉斯決策平均效益值，算法運行結果如圖1所示.

可以看出，采用基于經驗期望值的網格任務調度算法，平均效益值(F1)要低于采用了貝葉斯決策的平均效益值(F2).而兩者的差值大于預報支出費用，表明可以采用資源預報系統，提高決策的準確性.

圖1 平均效益值計算結果

3 結 論

網格計算中任務分配，根據貝葉斯決策可以提高調度算法的平均效益值.在資源調度的過程中，如何增強資源狀態預報的準確性，降低資源預報的費用，是提高該算法優越性需要下一步進行的工作.

［1］MARTINO D V.Sub optimal scheduling in a GRID using genetic algorithms［A］.Parallel and Distributed Processing Symposium［C］.2003，22-26.

［2］SONG S，HWANG K，KWOK Y K.Risk-resilient heuristics and genetic algorithms for security-assured grid job scheduling［A］.Com-puters，IEEE Trcmsactions［C］.2006，703-719.

［3］林劍檸，吳慧中.基于遺傳算法的網格資源調度算法［J］.計算機研究與發展，2004，14(12):2195-2199.

［4］XU Z H，HOU X D，SUN J Z.Ant algorithm-based task scheduling in grid computing［A］.Electrical and Computer Engineering，2003.IEEE CCECE 2003［C］.2003，1107-1110.

［5］YAN H，SHEN X Q，LI X，et al.An improved ant algorithm for job scheduling in grid computing［A］.Machine Learning and Cybernet-ics［C］.2005，2957-2961.

［6］許智宏，孫濟洲.用螞蟻算法進行網格任務調度的研究［J］.計算機應用，2005，25(10):2236-2237.

［7］WANG T，ZHOU X S，LIU Q R，et al.OD:a general resource sched-uling algorithm for computational grid ［A］.Computer and Computa-tional Sciences，IMSCCS ＇06［C］.2006，644-647.

［8］王樹鵬，云曉春，余翔湛.基于生存性和 Makespan的多目標任務調度算法研究［J］.通信學報，2006，27(2):42-49.

［9］季一木，王汝傳.基于粒子群的網格任務調度算法研究［J］.通信學報，2007，28(10):60-66.

［10］Wolski R，Spring N，Hayes J.The Network Weather Service:A Distributed Resource Performance Forecasting Service for Metacom-puting［J］.Journal of Future Generation Computing Systems，1999，15(5/6):757-768.

［11］Peter A.Dinda Hallaron D R O.Host Load Prediction Using Linear Models［J］.Cluster Computing，2000，3(4):265-280.

［12］Buyya R.Nimrod/G Problem Solving Environment and Computational Economics.Grid Computing Environments Community Practice(CP)Document［M］.Global Grid Forum(GGF)/First GGF Workshop，Amsterdam，the Netherlands，2001.

［13］武秀川，李昊，鞠九濱.基于計算經濟模型改善網格資源分發和發現的性能［J］.計算機工程與應用，2005，41(10):64-66.