基于信任驅動的網格任務調度新算法

摘要：利用信任機制的概念，對傳統網格調度算法進行改進，提出了信任驅動的動態調度算法TD_OLB、TD_MCT和靜態調度算法TD_max－min；同時，在相同的假定條件設置下對這些新算法進行了仿真分析和比較研究。仿真結果表明，基于信任機制的調度算法不僅優于傳統的基于makespan的調度算法，而且當要求強信任關系任務的數量大于弱信任關系及無信任關系的任務數量時，信任驅動的TD_max－min調度算法優于信任驅動的TD_min－min算法。

關鍵詞：網格計算； 網格安全； 信任模型； 信任驅動； 任務調度

中圖分類號：TP301．6文獻標志碼：A

文章編號：1001-3695(2007)11-0026-04

0引言

網格把整個因特網整合成一個巨大的超級計算機，實現計算資源、存儲資源、資料資源、信息資源、知識資源、專家資源的全面共享。經常有一些大型的、強資源要求的科學計算問題所需要的計算能力及資源已遠遠超出單臺計算機所能提供的計算能力。網格技術為解決此類問題應運而生[1]。

網格由多個功能模塊組成。其中的任務調度系統，特別是任務調度算法是計算網格運行管理的關鍵技術之一。國內外許多學者對網格任務的調度算法做了大量研究工作，較為經典的有OLB、MET、MCT、min－min、max－min、GA、A*算法等[2]。這些調度算法大多均以makespan作為調度目標函數。隨著網格技術的發展，人們對網格的服務質量和安全等提出了更高的要求，并將QoS需求加入到調度算法中，提出基于QoS的網格任務調度算法[3，4]。

近年來，人們又提出了信任驅動的網格任務調度問題。將信任機制有效地融入到任務調度機制中[4]，使任務調度系統更好地在開放、異構和動態的真實網格環境中有效運行。因此研究融入信任機制的網格資源管理策略，形成信任驅動的網格任務調度算法具有重要的理論價值與現實意義。但是在現階段，人們對信任的含義還沒有取得完全一致的理解，對信任的定義尤其是在信任的計算方法上，不同的作者提出了不同的方法。文獻 [5~7]對信任的定義是“對某實體本身行為的期望，它包括在某些指定內容方面對該實體過去行為的觀察以及其他對該實體的推薦信息”。文獻[8]對信任的定義是“由信任值表征的客觀實體的身份和行為的可信度評估，信任值取決于實體可靠性、誠信和性能等”。文獻[9]用集合的形式來表示信任的定義。雖然文獻[5，6，9]計算信任度的公式不完全一樣，但均涉及到直接信任和間接信任值的計算。此外，不同文獻對信任對象(實體)的研究也有不同。文獻[6，7，9，10]研究的是以域為單位的域間信任關系和域內信任關系；文獻[5，8]研究的則是計算資源與計算任務之間的信任關系。

在信任驅動的網格任務調度問題上，本文采用文獻[8]的信任機制定義，將信任效益函數作為任務調度的目標函數，對傳統OLB、MCT、max－min調度算法進行改進和擴展，提出了基于信任機制的網格任務動態調度算法TD_OLB、TD_MCT和靜態調度算法TD_max－min。同時，在相同的實驗樣本和假定條件下，對這些改進后的算法進行了深入的仿真分析和比較研究。

1信任調度模型

1．1信任的概念

信任是一個非常復雜的主觀概念，目前沒有一致的定義。本文采用文獻[8]中的定義。

定義1信任。由信任值表征的客觀實體的身份和行為的可信度評估;信任值取決于實體可靠性、誠信和性能等。計算網格信任模型主要由資源信任屬性、任務信任屬性及其相互間信任關系構成。

資源信任屬性包含如下兩個方面：a)安全性。衡量網格資源對任務和數據的真實性、保密性和完整性的保障程度。本文采用資源安全級別(resource security value)量化資源安全屬性。b)可靠性。長時間執行的任務有可能因為某個資源失效導致運行失敗甚至重啟，造成系統資源浪費和系統性能低下。本文量化資源可靠性(resource reliability value)為單位時間內的失效概率。

任務信任屬性指網格用戶提交任務請求時，對任務運行的安全性和可靠性要求。本文分別采用任務安全級別與可靠性級別量化任務信任屬性。

1．2信任效益函數

4結束語

將信任機制與任務調度機制有效融合是真實網格環境中大規模分布式資源管理的難題之一。本文提出了基于信任機制的網格任務調度新算法；同時，在一致的ETC矩陣的條件下，通過調節機器異構和任務異構性，變動強、弱信任關系的任務數目，對所有基于信任機制的算法進行仿真分析和比較研究。結果表明，基于信任機制的調度算法不僅優于傳統基于時間的調度算法，而且在傳統基于makespan的目標調度問題中，min－min的性能總是優于max－min的結論不同，當強信任關系任務的數量大于弱信任關系及無信任關系的任務數時，TD_max－min算法明顯優于TD_min－min算法。這個發現進一步說明研究基于信任機制的網格調度算法的理論和實際意義。

參考文獻：

［1］BUYYA R， ABRAMSON D， VENUGOPAL S. The grid economy[J]. Proceedings of the IEEE， 2005，93(3):698-714.

［2］BRAUN R D，SIEGEL H J， BECK N， et al. A comparison study of static mapping heuristics for a class of meta－tasks on heterogeneous computing systems[C]//Proc of the 8th HCW. San Juan: IEEE Computer Society Press，1999:15-29.

［3］HE Xiao－shan，SUN Xian－he， LASZEWSKI G von. QoS guided min－min heuristic for grid task scheduling[J]. Journal of Computer Science and Technology，2003，18(4): 442-451.

［4］DOAN A， ZGNER F. Scheduling of a meta－task with QoS requirements in heterogeneous computing systems[J]. Journal of Pa￣rallel and Distributed Computing， 2006，66(2):181－196.

［5］AZZEDIN F， MAHESWARAN M. Integrating trust into grid resource management systems[C]//Proc of International Conference on Parallel Processing. Vancouver: IEEE Computer Society Press， 2002:47-54.

［6］王東安，徐浩，南凱，等. 基于推薦的網格計算的信任模型[J]. 計算機應用研究，2006，23(2):96-98.

［7］郭學理，楊慧，何鵬. 一種基于信任度的網格計算資源分配模型[J]. 計算機應用研究，2005，22(2):93-95.

［8］張偉哲，劉欣然，云曉春，等.信任驅動的網格任務調度算法[J]. 通信學報，2006，27(2):73-79.

［9］潘海軍，陸魁軍，吳朝暉. 基于網格系統的信任量化研究[J].計算機應用研究， 2005，22(10):49-51.

［10］黃寶邊，曾文華.網格計算中基于信任機制的動態任務調度[J]. 計算機應用，2006，26(1):65-69.

［11］ALI S， SIEGEL H J， MAHESWARAN M， et al. Representing task and machine heterogeneities for heterogeneous computing systems[J]. Tamkang Journal of Science and Engr， 2000，3(3):195-207.

“本文中所涉及到的圖表、注解、公式等內容請以PDF格式閱讀原文”