摘  要： 針對(duì)當(dāng)前網(wǎng)格資源管理中任務(wù)與資源匹配的缺陷，基于信任效益函數(shù)和最小完成時(shí)間，提出了基于信任的Trust Mintime Min-Min算法。分析了傳統(tǒng)的Min-Min算法，考慮Min-Min算法負(fù)載不平衡，對(duì)其在調(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)、開(kāi)放的真實(shí)網(wǎng)格環(huán)境中有效運(yùn)行。
    目前相關(guān)的研究中對(duì)信任的定義還沒(méi)有形成一致的見(jiàn)解，在信任的計(jì)算方法中不同的作者有不同的思路。其中具有代表性的研究包括：AZZEDIN與MAHESWARAN[1]等人首次將“信任”融入網(wǎng)格資源管理，提出考慮信任因素的作業(yè)調(diào)度會(huì)引入額外負(fù)載并設(shè)計(jì)了負(fù)載最小化算法。HUMPHREY[2]等人對(duì)具有安全意識(shí)的網(wǎng)格計(jì)算模型進(jìn)行了深入研究。ABAWAJY[3]等人提出的DFTS 分布式失效容忍調(diào)度策略，通過(guò)復(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ù)，對(duì)資源進(jìn)行分配，提出了基于信任的網(wǎng)格資源調(diào)度算法Trust Mintime Min-Min算法。
1 概念與問(wèn)題描述
1.1 信任模型
    本文采用的信任定義為：
    定義1 信任：由信任值表征的客觀實(shí)體的身份和行為的可信度評(píng)估，信任值取決于實(shí)體可靠性、誠(chéng)信和性能等。計(jì)算網(wǎng)格信任模型主要由資源信任屬性、任務(wù)信任屬性及其相互間信任關(guān)系構(gòu)成。資源信任屬性包含兩方面：
    （1）安全性。衡量網(wǎng)格資源對(duì)任務(wù)和數(shù)據(jù)的真實(shí)性、保密性和完整性的保障程度。采用資源安全級(jí)別量化資源安全屬性。
    （2）可靠性。長(zhǎng)時(shí)間執(zhí)行的任務(wù)有可能因?yàn)槟硞€(gè)資源失效導(dǎo)致運(yùn)行失敗甚至重啟，造成系統(tǒng)資源浪費(fèi)和系統(tǒng)性能低下。本文量化資源可靠性為單位時(shí)間內(nèi)失效概率。
    任務(wù)信任屬性指網(wǎng)格用戶提交任務(wù)請(qǐng)求時(shí)，對(duì)任務(wù)運(yùn)行的安全性和可靠性要求。分別采用任務(wù)安全級(jí)別與可靠性級(jí)別量化任務(wù)信任屬性。

    定義3 信任關(guān)系：根據(jù)調(diào)度過(guò)程中任務(wù)對(duì)資源信任值的要求，二者之間的信任關(guān)系可以分為強(qiáng)信任關(guān)系、弱信任關(guān)系和無(wú)信任關(guān)系。
    （1）強(qiáng)信任關(guān)系指調(diào)度時(shí)任務(wù)的安全性和可靠性需求級(jí)別必須高于所分配資源的固有屬性值。如果不存在滿足條件的資源，則此任務(wù)將被放棄。其最終效益值或者為最大，或者為零。
    （2）弱信任關(guān)系指調(diào)度算法盡量保證任務(wù)信任屬性值高于資源的信任屬性值，此時(shí)可獲得最大效益；否則，可以降低任務(wù)的信任需求，但是其信任效益值隨之下降。
    （3）無(wú)信任關(guān)系指在調(diào)度過(guò)程中不考慮任務(wù)和資源間的信任關(guān)系，僅以完成時(shí)間最小為目標(biāo)。
    定義4 資源調(diào)度的最小完成時(shí)間計(jì)算：在網(wǎng)格環(huán)境中，考慮任務(wù)之間沒(méi)有通信和數(shù)據(jù)依賴的集合，即元任務(wù)。那么要將m個(gè)資源M={m1，m2，…，mm}以合理的方式調(diào)度到n個(gè)元任務(wù)T={t1，t2，…，tn}的過(guò)程中，目的是得到盡可能小的總執(zhí)行時(shí)間(makespan)。n個(gè)元任務(wù)在m個(gè)資源的預(yù)測(cè)執(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ù)測(cè)最小完成時(shí)間(Minimum Completion Time)記為MCT(i，j)，則n個(gè)元任務(wù)在m個(gè)資源上的預(yù)測(cè)最小完成時(shí)間也是一個(gè) m×n的矩陣，筆者僅考慮以下決定因素：
    (1)ETC(i，j)：任務(wù)i在資源j上的預(yù)測(cè)執(zhí)行時(shí)間。
    (2)CSTART(j)：資源j最早可用時(shí)間。
    以上這些數(shù)據(jù)可以通過(guò)網(wǎng)格中NWS(Network Weather Service)和MDS(Monitoring and Discovery Service)組件來(lái)獲取。
    定義MCT(i，j)的計(jì)算公式為:
    MCT(i，j)=ETC(i，j)+CSTART(j)          (9)
2 算法
    首先將具有強(qiáng)信任關(guān)系和弱信任關(guān)系的任務(wù)各分為一類，把無(wú)信任關(guān)系的任務(wù)歸為第三類；然后，先對(duì)有信任關(guān)系的任務(wù)進(jìn)行調(diào)度，計(jì)算有信任關(guān)系的每個(gè)任務(wù)在各網(wǎng)格計(jì)算資源上的最大信任效益函數(shù)值，選擇信任效益最大的任務(wù)—資源對(duì)進(jìn)行映射；再計(jì)算無(wú)信任關(guān)系的任務(wù)在各網(wǎng)格計(jì)算資源上的最小完成時(shí)間，選擇完成時(shí)間最小的任務(wù)―資源對(duì)進(jìn)行映射。算法描述為：
    Trust Mintime Min-Min()
    輸入：任務(wù)和資源信任信息，ETC矩陣
    輸出：任務(wù)映射方案map
    初始化：令T為所有任務(wù)的集合，M為所有資源的集合，集合TR=?覫保存任務(wù)―資源對(duì)，變量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ú)法滿足任務(wù)ti的信任需求
            將ti從T中刪除；
           else  找出使任務(wù)的信任效益值最大的資源，
                將此任務(wù)—資源對(duì)保存到TR中
           endfor
       從TR中找出信任值最大任務(wù)資源對(duì)(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ù)—資源對(duì)保存到TR中;
        endfor
        從TR中找出MCT最小的任務(wù)資源對(duì)(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)對(duì)1~200個(gè)獨(dú)立任務(wù)構(gòu)成集合調(diào)度的情況。
    資源安全級(jí)別JR和任務(wù)安全級(jí)別JS在這4個(gè)級(jí)別{poor，low，medium，high}內(nèi)隨機(jī)產(chǎn)生。資源的單位時(shí)間失效率FR在區(qū)間[0.000 1，0.001 5]上隨機(jī)生成。任務(wù)需求級(jí)別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)系；否則為無(wú)信任關(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ù)存在惡意請(qǐng)求的情況下的兩種算法的Makespan。從圖中可以明顯看出，隨著任務(wù)數(shù)目的增加，本文提出的Trust Mintime Min-Min算法在任務(wù)總的執(zhí)行時(shí)間越來(lái)越少于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.