摘  要： 針對當(dāng)前網(wǎng)格資源管理中任務(wù)與資源匹配的缺陷,，基于信任效益函數(shù)和最小完成時(shí)間,，提出了基于信任的Trust Mintime Min-Min算法。分析了傳統(tǒng)的Min-Min算法,，考慮Min-Min算法負(fù)載不平衡,，對其在調(diào)度策略方面進(jìn)行了改進(jìn)。仿真實(shí)驗(yàn)表明,，該算法不但可以有效地平衡負(fù)載,，而且可以提高任務(wù)的完成率，兼顧計(jì)算的有效性和可靠性,。
關(guān)鍵詞： 網(wǎng)格計(jì)算,；信任模型,；資源調(diào)度；信任關(guān)系

    當(dāng)前計(jì)算網(wǎng)格中存在調(diào)度機(jī)制與信任機(jī)制分離,。將信任機(jī)制與資源調(diào)度機(jī)制有效融合,，可以為網(wǎng)格資源安全管理提供保障，使得資源調(diào)度更好地在動(dòng)態(tài),、異構(gòu),、開放的真實(shí)網(wǎng)格環(huán)境中有效運(yùn)行。
    目前相關(guān)的研究中對信任的定義還沒有形成一致的見解,，在信任的計(jì)算方法中不同的作者有不同的思路,。其中具有代表性的研究包括：AZZEDIN與MAHESWARAN[1]等人首次將“信任”融入網(wǎng)格資源管理，提出考慮信任因素的作業(yè)調(diào)度會(huì)引入額外負(fù)載并設(shè)計(jì)了負(fù)載最小化算法,。HUMPHREY[2]等人對具有安全意識的網(wǎng)格計(jì)算模型進(jìn)行了深入研究,。ABAWAJY[3]等人提出的DFTS 分布式失效容忍調(diào)度策略，通過復(fù)制作業(yè)的多個(gè)副本到不同站點(diǎn)保證作業(yè)在網(wǎng)格環(huán)境下可靠進(jìn)行,。DOGAN[4]和SONG Shan Shan[5]提出了最小化失效率的網(wǎng)格信任調(diào)度框架和調(diào)度算法,。唐小勇[6]等人在Buyya設(shè)計(jì)的GRACE網(wǎng)格資源管理框架下，提出反映信任值動(dòng)態(tài)變化規(guī)律的信任函數(shù),，建立基于行為的網(wǎng)格信任機(jī)制,，并將其應(yīng)用到網(wǎng)格經(jīng)濟(jì)模型中的DBC調(diào)度算法中。
    本文采用參考文獻(xiàn)[7]中給出的信任定義,，將信任效益值和最小完成時(shí)間作為調(diào)度目標(biāo)函數(shù),，對資源進(jìn)行分配，提出了基于信任的網(wǎng)格資源調(diào)度算法Trust Mintime Min-Min算法,。
1 概念與問題描述
1.1 信任模型
    本文采用的信任定義為：
    定義1 信任：由信任值表征的客觀實(shí)體的身份和行為的可信度評估,，信任值取決于實(shí)體可靠性、誠信和性能等,。計(jì)算網(wǎng)格信任模型主要由資源信任屬性,、任務(wù)信任屬性及其相互間信任關(guān)系構(gòu)成。資源信任屬性包含兩方面：
    （1）安全性,。衡量網(wǎng)格資源對任務(wù)和數(shù)據(jù)的真實(shí)性,、保密性和完整性的保障程度。采用資源安全級別量化資源安全屬性,。
    （2）可靠性,。長時(shí)間執(zhí)行的任務(wù)有可能因?yàn)槟硞€(gè)資源失效導(dǎo)致運(yùn)行失敗甚至重啟，造成系統(tǒng)資源浪費(fèi)和系統(tǒng)性能低下,。本文量化資源可靠性為單位時(shí)間內(nèi)失效概率,。
    任務(wù)信任屬性指網(wǎng)格用戶提交任務(wù)請求時(shí)，對任務(wù)運(yùn)行的安全性和可靠性要求。分別采用任務(wù)安全級別與可靠性級別量化任務(wù)信任屬性,。

    定義3 信任關(guān)系：根據(jù)調(diào)度過程中任務(wù)對資源信任值的要求,，二者之間的信任關(guān)系可以分為強(qiáng)信任關(guān)系、弱信任關(guān)系和無信任關(guān)系,。
    （1）強(qiáng)信任關(guān)系指調(diào)度時(shí)任務(wù)的安全性和可靠性需求級別必須高于所分配資源的固有屬性值,。如果不存在滿足條件的資源，則此任務(wù)將被放棄,。其最終效益值或者為最大,，或者為零。
    （2）弱信任關(guān)系指調(diào)度算法盡量保證任務(wù)信任屬性值高于資源的信任屬性值,，此時(shí)可獲得最大效益,；否則，可以降低任務(wù)的信任需求,，但是其信任效益值隨之下降,。
    （3）無信任關(guān)系指在調(diào)度過程中不考慮任務(wù)和資源間的信任關(guān)系，僅以完成時(shí)間最小為目標(biāo),。
    定義4 資源調(diào)度的最小完成時(shí)間計(jì)算：在網(wǎng)格環(huán)境中，考慮任務(wù)之間沒有通信和數(shù)據(jù)依賴的集合,，即元任務(wù),。那么要將m個(gè)資源M={m1，m2,，…,，mm}以合理的方式調(diào)度到n個(gè)元任務(wù)T={t1，t2,，…,，tn}的過程中，目的是得到盡可能小的總執(zhí)行時(shí)間(makespan),。n個(gè)元任務(wù)在m個(gè)資源的預(yù)測執(zhí)行時(shí)間ETC(Expected Time to Compute)是一個(gè)m×n的矩陣,，矩陣中的每一行代表某一個(gè)任務(wù)在m個(gè)資源上的不同時(shí)間，每一列代表某一資源上的m個(gè)任務(wù)的不同執(zhí)行時(shí)間,。
    第i個(gè)任務(wù)在第j個(gè)資源上的預(yù)測最小完成時(shí)間(Minimum Completion Time)記為MCT(i,，j)，則n個(gè)元任務(wù)在m個(gè)資源上的預(yù)測最小完成時(shí)間也是一個(gè) m×n的矩陣,，筆者僅考慮以下決定因素：
    (1)ETC(i,，j)：任務(wù)i在資源j上的預(yù)測執(zhí)行時(shí)間。
    (2)CSTART(j)：資源j最早可用時(shí)間,。
    以上這些數(shù)據(jù)可以通過網(wǎng)格中NWS(Network Weather Service)和MDS(Monitoring and Discovery Service)組件來獲取,。
    定義MCT(i，j)的計(jì)算公式為:
    MCT(i，j)=ETC(i,，j)+CSTART(j)          (9)
2 算法
    首先將具有強(qiáng)信任關(guān)系和弱信任關(guān)系的任務(wù)各分為一類,，把無信任關(guān)系的任務(wù)歸為第三類；然后,，先對有信任關(guān)系的任務(wù)進(jìn)行調(diào)度,，計(jì)算有信任關(guān)系的每個(gè)任務(wù)在各網(wǎng)格計(jì)算資源上的最大信任效益函數(shù)值，選擇信任效益最大的任務(wù)—資源對進(jìn)行映射,；再計(jì)算無信任關(guān)系的任務(wù)在各網(wǎng)格計(jì)算資源上的最小完成時(shí)間,，選擇完成時(shí)間最小的任務(wù)―資源對進(jìn)行映射。算法描述為：
    Trust Mintime Min-Min()
    輸入：任務(wù)和資源信任信息,，ETC矩陣
    輸出：任務(wù)映射方案map
    初始化：令T為所有任務(wù)的集合,，M為所有資源的集合，集合TR=?覫保存任務(wù)―資源對,，變量k用于計(jì)數(shù),。
    根據(jù)信任關(guān)系（strong、weak ,、no）將任務(wù)集合T分為三個(gè)不相交的子集合class1,，class2，classno
    令k=1;
    Repeat
        if(classk不為空)
           TR置為空,；
           for classk中每一個(gè)任務(wù)ti
            for  M中每一個(gè)資源mj
               if資源mj能滿足任務(wù)ti的信任需求
                計(jì)算ti在mj上的信任效益
                    TrustUtil(i,，j)；
               endif
             endfor
           if所有資源均無法滿足任務(wù)ti的信任需求
            將ti從T中刪除,；
           else  找出使任務(wù)的信任效益值最大的資源,，
                將此任務(wù)—資源對保存到TR中
           endfor
       從TR中找出信任值最大任務(wù)資源對(ti，mj),；
       將ti分配到mj任務(wù)隊(duì)列末尾,，從classk中刪除ti;
       endif
    if(classk為空)
        K=k+1;
    endif
       until (k>2)
       if  (classno不為空)
        for  classno中的每個(gè)任務(wù)ti
           for資源M中的每一個(gè)資源mj
             計(jì)算MCT(i，j)
           endfor
           找到使任務(wù)的最小完成時(shí)間MCT最小的資
            源,，將此任務(wù)—資源對保存到TR中;
        endfor
        從TR中找出MCT最小的任務(wù)資源對(ti,mj);
        將ti分配到mj任務(wù)隊(duì)列末尾,，從classno中刪
            除ti;
       endif
    until(classno為空)
3 仿真實(shí)驗(yàn)
3.1 實(shí)驗(yàn)內(nèi)容與設(shè)置
    仿真試驗(yàn)考察了20~50個(gè)計(jì)算資源組成的網(wǎng)格系統(tǒng)對1~200個(gè)獨(dú)立任務(wù)構(gòu)成集合調(diào)度的情況。
    資源安全級別JR和任務(wù)安全級別JS在這4個(gè)級別{poor,，low,，medium，high}內(nèi)隨機(jī)產(chǎn)生,。資源的單位時(shí)間失效率FR在區(qū)間[0.000 1,，0.001 5]上隨機(jī)生成。任務(wù)需求級別JR在強(qiáng),、弱信任關(guān)系的情況下根據(jù)公式JR=(0.9+0.1×rand)×exp(10-4×任務(wù)數(shù)/主機(jī)數(shù))生成,。根據(jù)參考文獻(xiàn)[8]中方案取μtask=μmach=100,，Vtask=Vmach=0.6。設(shè)置變量1≤Vq≤4控制任務(wù)與資源間的信任關(guān)系,，生成一個(gè)[0,，1]間隨機(jī)數(shù)，如果該數(shù)小于0.25 Vq,，則稱兩者具有強(qiáng)信任關(guān)系,；該數(shù)小于0.5 Vq為弱信任關(guān)系；否則為無信任關(guān)系,。信任效益函數(shù)式(7)中w1和w2均取值為0.5,。
3.2 實(shí)驗(yàn)結(jié)果和性能分析
    設(shè)置200個(gè)獨(dú)立任務(wù)在50個(gè)異構(gòu)資源進(jìn)行調(diào)度。如圖1所示,，顯示了30個(gè)資源負(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)境中正常運(yùn)行和有10%的任務(wù)存在惡意請求的情況下的兩種算法的Makespan。從圖中可以明顯看出,，隨著任務(wù)數(shù)目的增加,，本文提出的Trust Mintime Min-Min算法在任務(wù)總的執(zhí)行時(shí)間越來越少于Min-Min算法，特別是在網(wǎng)格環(huán)境中存在惡意行為的情況下更為明顯,。

    仿真結(jié)果證明Trust Mintime Min-Min算法在資源負(fù)載、任務(wù)總的執(zhí)行時(shí)間等方面較經(jīng)典的Min-Min算法有所提高,?？紤]到信任關(guān)系，在一定程度上提高了網(wǎng)格系統(tǒng)的安全性和可靠性,，保證了網(wǎng)格系統(tǒng)的正常運(yùn)行,。
參考文獻(xiàn)
[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)濟(jì)模型中基于信任機(jī)制的調(diào)度算法[J].計(jì)算機(jī)應(yīng)用研究，2008,，25(8)：2357-2361.
[7] 張偉哲,，劉欣然，云小春,，等.信任驅(qū)動(dòng)的網(wǎng)格作業(yè)調(diào)度算法[J].通信學(xué)報(bào),，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.