基于貝葉斯決策的網(wǎng)格計算資源分配算法

李 昊，謝中江，侯哲生

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

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

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

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

1.1 分配算法的步驟

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

1.1.1 根據(jù)先驗概率進行決策

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

1.1.2 預驗分析

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

1.1.3 后驗分析

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

1.2 分配算法的收益分析

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

1.2.1 確定已有的資源狀態(tài)θi，給出資源系統(tǒng)對應狀態(tài)出現(xiàn)的概率值.根據(jù)當前狀態(tài)進行最優(yōu)調(diào)度算法的計算，確定調(diào)度方案dj在每種資源狀態(tài)θi的效益值uij，根據(jù)期望值準則，計算各方案效益期望值:

相應最優(yōu)方案及期望值

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

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

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

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

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

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

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

2 算法實現(xiàn)與分析

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

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

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

圖1 平均效益值計算結果

3 結 論

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

［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］林劍檸，吳慧中.基于遺傳算法的網(wǎng)格資源調(diào)度算法［J］.計算機研究與發(fā)展，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］許智宏，孫濟洲.用螞蟻算法進行網(wǎng)格任務調(diào)度的研究［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的多目標任務調(diào)度算法研究［J］.通信學報，2006，27(2):42-49.

［9］季一木，王汝傳.基于粒子群的網(wǎng)格任務調(diào)度算法研究［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īng)濟模型改善網(wǎng)格資源分發(fā)和發(fā)現(xiàn)的性能［J］.計算機工程與應用，2005，41(10):64-66.