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

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

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

    由于考慮了信任關系，將任務提交到信任度較高的資源上執行，如圖2所示，Trust Mintime Min-Min算法大大提高了任務提交的成功率，資源也得到有效的利用。

    圖3和圖4分別給出了在網格環境中正常運行和有10%的任務存在惡意請求的情況下的兩種算法的Makespan。從圖中可以明顯看出，隨著任務數目的增加，本文提出的Trust Mintime Min-Min算法在任務總的執行時間越來越少于Min-Min算法，特別是在網格環境中存在惡意行為的情況下更為明顯。

    仿真結果證明Trust Mintime Min-Min算法在資源負載、任務總的執行時間等方面較經典的Min-Min算法有所提高。考慮到信任關系，在一定程度上提高了網格系統的安全性和可靠性，保證了網格系統的正常運行。
參考文獻
[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] 唐小勇，李肯立.網格經濟模型中基于信任機制的調度算法[J].計算機應用研究，2008，25(8)：2357-2361.
[7] 張偉哲，劉欣然，云小春，等.信任驅動的網格作業調度算法[J].通信學報，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.