摘 要： 針對當(dāng)前網(wǎng)格資源管理中任務(wù)與資源匹配的缺陷，基于信任效益函數(shù)和最小完成時間，提出了基于信任的Trust Mintime Min-Min算法。分析了傳統(tǒng)的Min-Min算法，考慮Min-Min算法負(fù)載不平衡，對其在調(diào)度策略方面進行了改進。仿真實驗表明，該算法不但可以有效地平衡負(fù)載，而且可以提高任務(wù)的完成率，兼顧計算的有效性和可靠性。
關(guān)鍵詞： 網(wǎng)格計算；信任模型；資源調(diào)度；信任關(guān)系
當(dāng)前計算網(wǎng)格中存在調(diào)度機制與信任機制分離。將信任機制與資源調(diào)度機制有效融合，可以為網(wǎng)格資源安全管理提供保障，使得資源調(diào)度更好地在動態(tài)、異構(gòu)、開放的真實網(wǎng)格環(huán)境中有效運行。
目前相關(guān)的研究中對信任的定義還沒有形成一致的見解，在信任的計算方法中不同的作者有不同的思路。其中具有代表性的研究包括：AZZEDIN與MAHESWARAN[1]等人首次將“信任”融入網(wǎng)格資源管理，提出考慮信任因素的作業(yè)調(diào)度會引入額外負(fù)載并設(shè)計了負(fù)載最小化算法。HUMPHREY[2]等人對具有安全意識的網(wǎng)格計算模型進行了深入研究。ABAWAJY[3]等人提出的DFTS 分布式失效容忍調(diào)度策略，通過復(fù)制作業(yè)的多個副本到不同站點保證作業(yè)在網(wǎng)格環(huán)境下可靠進行。DOGAN[4]和SONG Shan Shan[5]提出了最小化失效率的網(wǎng)格信任調(diào)度框架和調(diào)度算法。唐小勇[6]等人在Buyya設(shè)計的GRACE網(wǎng)格資源管理框架下，提出反映信任值動態(tài)變化規(guī)律的信任函數(shù)，建立基于行為的網(wǎng)格信任機制，并將其應(yīng)用到網(wǎng)格經(jīng)濟模型中的DBC調(diào)度算法中。
本文采用參考文獻[7]中給出的信任定義，將信任效益值和最小完成時間作為調(diào)度目標(biāo)函數(shù)，對資源進行分配，提出了基于信任的網(wǎng)格資源調(diào)度算法Trust Mintime Min-Min算法。
1 概念與問題描述
1.1 信任模型
本文采用的信任定義為：
定義1 信任：由信任值表征的客觀實體的身份和行為的可信度評估，信任值取決于實體可靠性、誠信和性能等。計算網(wǎng)格信任模型主要由資源信任屬性、任務(wù)信任屬性及其相互間信任關(guān)系構(gòu)成。資源信任屬性包含兩方面：
（1）安全性。衡量網(wǎng)格資源對任務(wù)和數(shù)據(jù)的真實性、保密性和完整性的保障程度。采用資源安全級別量化資源安全屬性。
（2）可靠性。長時間執(zhí)行的任務(wù)有可能因為某個資源失效導(dǎo)致運行失敗甚至重啟，造成系統(tǒng)資源浪費和系統(tǒng)性能低下。本文量化資源可靠性為單位時間內(nèi)失效概率。
任務(wù)信任屬性指網(wǎng)格用戶提交任務(wù)請求時，對任務(wù)運行的安全性和可靠性要求。分別采用任務(wù)安全級別與可靠性級別量化任務(wù)信任屬性。
定義3 信任關(guān)系：根據(jù)調(diào)度過程中任務(wù)對資源信任值的要求，二者之間的信任關(guān)系可以分為強信任關(guān)系、弱信任關(guān)系和無信任關(guān)系。
（1）強信任關(guān)系指調(diào)度時任務(wù)的安全性和可靠性需求級別必須高于所分配資源的固有屬性值。如果不存在滿足條件的資源，則此任務(wù)將被放棄。其最終效益值或者為最大，或者為零。
（2）弱信任關(guān)系指調(diào)度算法盡量保證任務(wù)信任屬性值高于資源的信任屬性值，此時可獲得最大效益；否則，可以降低任務(wù)的信任需求，但是其信任效益值隨之下降。
（3）無信任關(guān)系指在調(diào)度過程中不考慮任務(wù)和資源間的信任關(guān)系，僅以完成時間最小為目標(biāo)。
定義4 資源調(diào)度的最小完成時間計算：在網(wǎng)格環(huán)境中，考慮任務(wù)之間沒有通信和數(shù)據(jù)依賴的集合，即元任務(wù)。那么要將m個資源M={m1，m2，…，mm}以合理的方式調(diào)度到n個元任務(wù)T={t1，t2，…，tn}的過程中，目的是得到盡可能小的總執(zhí)行時間(makespan)。n個元任務(wù)在m個資源的預(yù)測執(zhí)行時間ETC(Expected Time to Compute)是一個m×n的矩陣，矩陣中的每一行代表某一個任務(wù)在m個資源上的不同時間，每一列代表某一資源上的m個任務(wù)的不同執(zhí)行時間。
第i個任務(wù)在第j個資源上的預(yù)測最小完成時間(Minimum Completion Time)記為MCT(i，j)，則n個元任務(wù)在m個資源上的預(yù)測最小完成時間也是一個 m×n的矩陣，筆者僅考慮以下決定因素：
(1)ETC(i，j)：任務(wù)i在資源j上的預(yù)測執(zhí)行時間。
(2)CSTART(j)：資源j最早可用時間。
以上這些數(shù)據(jù)可以通過網(wǎng)格中NWS(Network Weather Service)和MDS(Monitoring and Discovery Service)組件來獲取。
定義MCT(i，j)的計算公式為:
MCT(i，j)=ETC(i，j)+CSTART(j) (9)
2 算法
首先將具有強信任關(guān)系和弱信任關(guān)系的任務(wù)各分為一類，把無信任關(guān)系的任務(wù)歸為第三類；然后，先對有信任關(guān)系的任務(wù)進行調(diào)度，計算有信任關(guān)系的每個任務(wù)在各網(wǎng)格計算資源上的最大信任效益函數(shù)值，選擇信任效益最大的任務(wù)—資源對進行映射；再計算無信任關(guān)系的任務(wù)在各網(wǎng)格計算資源上的最小完成時間，選擇完成時間最小的任務(wù)―資源對進行映射。算法描述為：
Trust Mintime Min-Min()
輸入：任務(wù)和資源信任信息，ETC矩陣
輸出：任務(wù)映射方案map
初始化：令T為所有任務(wù)的集合，M為所有資源的集合，集合TR=?覫保存任務(wù)―資源對，變量k用于計數(shù)。
根據(jù)信任關(guān)系（strong、weak 、no）將任務(wù)集合T分為三個不相交的子集合class1，class2，classno
令k=1;
Repeat
if(classk不為空)
TR置為空；
for classk中每一個任務(wù)ti
for M中每一個資源mj
if資源mj能滿足任務(wù)ti的信任需求
計算ti在mj上的信任效益
TrustUtil(i，j)；
endif
endfor
if所有資源均無法滿足任務(wù)ti的信任需求
將ti從T中刪除；
else 找出使任務(wù)的信任效益值最大的資源，
將此任務(wù)—資源對保存到TR中
endfor
從TR中找出信任值最大任務(wù)資源對(ti，mj)；
將ti分配到mj任務(wù)隊列末尾，從classk中刪除ti;
endif
if(classk為空)
K=k+1;
endif
until (k>2)
if (classno不為空)
for classno中的每個任務(wù)ti
for資源M中的每一個資源mj
計算MCT(i，j)
endfor
找到使任務(wù)的最小完成時間MCT最小的資
源，將此任務(wù)—資源對保存到TR中;
endfor
從TR中找出MCT最小的任務(wù)資源對(ti,mj);
將ti分配到mj任務(wù)隊列末尾，從classno中刪
除ti;
endif
until(classno為空)
3 仿真實驗
3.1 實驗內(nèi)容與設(shè)置
仿真試驗考察了20~50個計算資源組成的網(wǎng)格系統(tǒng)對1~200個獨立任務(wù)構(gòu)成集合調(diào)度的情況。
資源安全級別JR和任務(wù)安全級別JS在這4個級別{poor，low，medium，high}內(nèi)隨機產(chǎn)生。資源的單位時間失效率FR在區(qū)間[0.000 1，0.001 5]上隨機生成。任務(wù)需求級別JR在強、弱信任關(guān)系的情況下根據(jù)公式JR=(0.9+0.1×rand)×exp(10-4×任務(wù)數(shù)/主機數(shù))生成。根據(jù)參考文獻[8]中方案取μtask=μmach=100，Vtask=Vmach=0.6。設(shè)置變量1≤Vq≤4控制任務(wù)與資源間的信任關(guān)系，生成一個[0，1]間隨機數(shù)，如果該數(shù)小于0.25 Vq，則稱兩者具有強信任關(guān)系；該數(shù)小于0.5 Vq為弱信任關(guān)系；否則為無信任關(guān)系。信任效益函數(shù)式(7)中w1和w2均取值為0.5。
3.2 實驗結(jié)果和性能分析
設(shè)置200個獨立任務(wù)在50個異構(gòu)資源進行調(diào)度。如圖1所示，顯示了30個資源負(fù)載情況，可以看出本文提出的Trust Mintime Min-Min算法負(fù)載平衡性明顯優(yōu)于傳統(tǒng)的Min-Min算法。
由于考慮了信任關(guān)系，將任務(wù)提交到信任度較高的資源上執(zhí)行，如圖2所示，Trust Mintime Min-Min算法大大提高了任務(wù)提交的成功率，資源也得到有效的利用。
圖3和圖4分別給出了在網(wǎng)格環(huán)境中正常運行和有10%的任務(wù)存在惡意請求的情況下的兩種算法的Makespan。從圖中可以明顯看出，隨著任務(wù)數(shù)目的增加，本文提出的Trust Mintime Min-Min算法在任務(wù)總的執(zhí)行時間越來越少于Min-Min算法，特別是在網(wǎng)格環(huán)境中存在惡意行為的情況下更為明顯。
仿真結(jié)果證明Trust Mintime Min-Min算法在資源負(fù)載、任務(wù)總的執(zhí)行時間等方面較經(jīng)典的Min-Min算法有所提高。考慮到信任關(guān)系，在一定程度上提高了網(wǎng)格系統(tǒng)的安全性和可靠性，保證了網(wǎng)格系統(tǒng)的正常運行。
參考文獻
[1] AZZEDIN F，MAHESWARAN M.Integrating trust into gridresource management systems[C].2002 International Conference on Parallel Processing(ICPP 2002).Canada：IEEE Press 2002：47-54.
[2] HUMPHREY M，THOMPSON M R.Security implication of typical grid computing usage scenario[C].IEEE Proc HPDC. USA：IEEE Press，2001：95-103.
[3] ABAWAJY J H.Fault-tolerant scheduling policy for grid computing systems[C].Proc IPDPS 2004.USA：IEEE Press，2004：50-58.
[4] DOGAN A，OZGUNER F.Matching and scheduling algorithms for minimizing execution time and failure probalitity of applications in heterogeneous computing[J]. IEEE Trans on Parallel and Distributed Systems，2002，13(3)：308-323.
[5] SONG S，KWOK Y K，HWANG K.Trusted job scheduling in open computional grids：Security-driven heuristics and a fast genetic algorithm[C].proceedings of the 19th IEEE International parallel & Distributed Proceessing Symposium (IPDPS-2005).Denver，CO，USA：IEEE Press，2005：33-40.
[6] 唐小勇，李肯立.網(wǎng)格經(jīng)濟模型中基于信任機制的調(diào)度算法[J].計算機應(yīng)用研究，2008，25(8)：2357-2361.
[7] 張偉哲，劉欣然，云小春，等.信任驅(qū)動的網(wǎng)格作業(yè)調(diào)度算法[J].通信學(xué)報，2006，27(2)：73-79.
[8] SHOUKAT A，HOWARD J S，MUTHUCUMARU M，et al. Task execution time modeling for heterogeneous computing systems[C].IPDPS Workshop on Heterogeneous Computing. Cancun，Mexic：IEEE Press，2000：185-199.