the 基于agent 的網(wǎng)格資源共享聯(lián)盟guide download

1、1引言構建計算網(wǎng)格的主要目的之一就是資源共享,使自利Agent 能夠通過合作完成計算任務。計算網(wǎng)格中的Agent在不同的時間段有不同的負載量,如果某個Agent在某時刻達到自己的負載峰值,該Agent可以利用空閑的Agent資源來執(zhí)行任務。這些自利Agent之間有一個動態(tài)的負載均衡。Agent通過共享使用其他伙伴的資源來完成計算任務。因此,建立Agent之間合作關系顯得至關重要。在網(wǎng)格系統(tǒng)中,資源分布于不同地理位置,隸屬于不同的Agent管理者,Agent所固有的自利性也使得對設計計算網(wǎng)格的資源分配機制的設計面臨挑戰(zhàn)。此外,由于資源提供者在資源能力、資源可用性、資源使用代價與安全策略上存在差異

2、,要想將資源分配給合適的任務以使資源的利用率和相應的收益最大同樣也十分困難。近年來,在多Agent系統(tǒng)中,聯(lián)盟問題的研究十分活躍,聯(lián)盟機制是多Agent系統(tǒng)合作求解的關鍵,聯(lián)盟的形成是多A-gent系統(tǒng)合作求解的重要方式,通過聯(lián)盟可以提高合作求解問題的能力。針對網(wǎng)格資源分布性、異構性和動態(tài)性的特點,把Agent合作機制引入網(wǎng)格資源管理是一個值得研究的問題。由每一個Agent管理若干個資源,可以把網(wǎng)格資源分配問題轉(zhuǎn)化為Agent合作求解問題,進而可以把Agent聯(lián)盟機制引入到網(wǎng)格資源分配中,以提高資源分配的效率和適用性。本文提出了一種新穎的基于Agent的網(wǎng)格資源共享聯(lián)盟的資源分配方法。2網(wǎng)格資

3、源與Agent聯(lián)盟在多Agent系統(tǒng)中,Agent聯(lián)盟已經(jīng)是非常活躍的研究領域。聯(lián)盟形成主要包括以下三個方面8,(1聯(lián)盟結構的產(chǎn)生,也就是說,把一系列的Agent劃分為互不相交的聯(lián)盟集合。在計算網(wǎng)格環(huán)境中,體現(xiàn)在網(wǎng)格中的Agent如何尋找伙伴以及達成資源共享協(xié)議。(2解決聯(lián)盟最優(yōu)問題。對于計算網(wǎng)格來說就是如何把計算任務分配給聯(lián)盟中的Agent才能使得每個Agent 的效用都能達到最優(yōu)。(3利益分配的問題。對于計算網(wǎng)格來說就是如何把利益分配給參加聯(lián)盟的Agent。一個Agent是否加入一個聯(lián)盟主要是根據(jù)參加潛在的聯(lián)盟獲得利益來決策。由于網(wǎng)格中的Agent在不同的時間段有不同的負載量,如果某時刻達

4、到自己的負載峰值或者該Agent不能夠滿足任務所需,此時該Agent可以利用其他Agent的資源來為自己服務。由于Agent本身的自利性,Agent在利用其他Agent的資源時,也可以貢獻出自身所擁有的空閑資源。Agent如何貢獻自身資源,如何共享其他Agent資源以及該Agent貢獻的資源量和共享的資源量都是需要研究的問題。考慮到資源的異構性以及基于Agent的網(wǎng)格資源共享聯(lián)盟李洪濤,焦玉璽,張偉LI Hong-tao,JIAO Yu-xi,ZHANG Wei煙臺大學計算機學院智能信息處理實驗室,山東煙臺264005Laboratory of Information Processing,S

5、chool of Computer,Yantai University,Yantai,Shandong264005,ChinaLI Hong-tao,JIAO Yu-xi,ZHANG Wei.Agent based resource-sharing coalitions in grid.Computer Engineering and Applications,2009,45(9:110-113.Abstract:Grid resource allocation is one of the key problems to grid computing.More and more grid re

6、searchers are paying at-tention to the problem of grid resource allocation.In this paper,a novel mechanism of grid resource allocation is given.The mecha-nism is composed of agent strategies for searching out the best coalitions to join and an multi-party negotiation.Grid resource al-location is rea

7、lized through forming resource-sharing coalitions.The simulation results show that self-interest agents in computa-tional grids have considerable impact on the decisions of each agent about how to allocate their resource to appropriate tasks. Key words:grid;resource-sharing coalitions;Agent摘要:網(wǎng)格資源分配

8、是網(wǎng)格計算中的關鍵問題之一,并引起網(wǎng)格研究者越來越多的關注。提出了一種新穎的網(wǎng)格資源分配機制,該機制主要由基于Agent技術的搜索最佳聯(lián)盟策略和多黨協(xié)商機制組成,通過形成資源共享聯(lián)盟來實現(xiàn)網(wǎng)格資源的分配。模擬結果顯示計算網(wǎng)格中的自利Agent對網(wǎng)格資源的分配具有很大的影響。關鍵詞:網(wǎng)格;資源共享聯(lián)盟;Agent基金項目:國家自然科學基金(the National Natural Science Foundation of China under Grant No.60496323。作者簡介:李洪濤(1982-,男,碩士研究生,研究方向為分布式人工智能與網(wǎng)格計算;焦玉璽(1980-,男,碩士研究

9、生,研究方向為分布式人工智能與多Agent技術;張偉(1961-,男,博士,碩士生導師,教授,研究方向為分布式人工智能與計算。收稿日期:2008-01-31修回日期:2008-04-24ÁÁÁÁW(t C(R t t 1t2圖1分配負載函數(shù)ÁÁÁÁÁÁÁÁÁÁÁÁt 1t2tg(t 圖2空閑CPU 的分配函數(shù)每一類資源的性能差異,為了更好刻畫資源性能,引入了標準衡量指標,例如:對于CPU ,用標準速度C (P s 來刻畫其性能。定義1給

10、定一組資源R =R 1,R 2,R m ,并且R 中的R i 具有不同的性能,設該類資源的標準性能為C (R s ,R i 的性能為C (R i =n i ×C (R s ,其中n i 是R i 的性能相當于標準性能C (R s 的個數(shù),這一組資源在時間段t 1,t 2的總性能C(R 為:C (R =N ×C (R s ×|t 1-t 2|其中N =mi =1n i(1定義2時刻t ,一個Agent 需要M 個標準性能的資源R 來運行它的任務,那么該Agent 在該時刻的資源R 的負載量為M ×C (R s 。定義3Agent 運行它的任務所需資源R 的

11、負載函數(shù)為一個時間函數(shù)w (t :T R ,表示在時刻t 的Agent 負載量。某時刻Agent 的負載量可能大于它的整個性能,此時可以通過獲得聯(lián)盟中其他Agent 提供的空閑資源R 繼續(xù)執(zhí)行,如圖1所示。為了實現(xiàn)Agent 之間的合作,還需要定義Agent 空閑資源R 的可分配函數(shù)。定義4對于某類資源R ,在時刻t 1,t 2內(nèi)的負載函數(shù)為w (t ,全部性能函數(shù)為C (R ,則該類空閑資源的可分配函數(shù)為g(t :g (t =C (R -w (t ,t t 1,t 2(2如圖2所示:當g (t >0,則Agent 存在該類空閑資源;當g (t <0,則此時的Agent 已經(jīng)滿額運

12、載,而且要使用其他Agent 的該類空閑資源來繼續(xù)執(zhí)行任務。定義5對于某類資源R ,在時刻t 1,t 2內(nèi),空閑資源R 的可分配函數(shù)g(t ,某個Agent a 為了繼續(xù)執(zhí)行所要執(zhí)行的任務需要額外的其他Agent 的空閑資源R 的性能為C R (a ,g (t :C R (a ,g (t =t 1t 2乙g -(t d t(3其中當g (t >0時,g -(t =0,當g (t <0時,g -(t =g (t 。并且為了完成Agent a 的任務,使用聯(lián)盟中其他Agent 的空閑資源R 的所要付出的代價為V R (a ,g (t :V R (a ,g (t =C R (a ,g (

13、t S s×V s (4其中,S s 為標準使用單元,V s 為使用標準單元的代價。定義6對于某類資源R ,在時刻t 1,t 2內(nèi),空閑資源R 的分配函數(shù)g (t ,某個Agent a 所能提供給聯(lián)盟的的空閑資源R 的性能為C I (a ,g (t :C I (a ,g (t =t 1t 2乙g +(t d t(5其中當g (t <0時,g +(t =0,當g (t >0時,g +(t =g(t 。同樣使用Agent A 空閑資源R 所付出的代價為V I (a ,g (t :V I (a ,g (t =C I (a ,g (t S s×V s (6在網(wǎng)格系統(tǒng)中,

14、每一個Agent 都能夠通過貢獻自身的空閑資源來獲得聯(lián)盟中其他Agent 的空閑資源,以便完成各自所要完成的任務。對于A 中每個Agent 來講,最理想的結果就是通過貢獻盡可能少的自身空閑資源,而獲得盡可能多的其他A -gent 的空閑資源來完成自身所要完成的任務。定義7假定一個Agent a i 從它參加的聯(lián)盟CL j 中獲得的空閑資源R 的能力為C gain (a i ,CL j ,而它貢獻出的自身的空閑資源R 的能力為C give (a i ,CL j ,Agent a i 借助于參加聯(lián)盟獲得資源使得自身能夠在規(guī)定的時間約束內(nèi)完成任務集合中K i 的任務。因而Agent a i 效用函數(shù)

15、定義為U (a i ,CL jU (a i ,CL j =(C gain (a i ,CL j -C give (a i ,CL j ×V s S s+V (K i (7對于A 中的所有Agent 來說,其中V (K i 為Agent a i 為了完成任務集合K i 中的任務所要獲得的報酬。它們將使用這個效用函數(shù)來決策是否參加某個聯(lián)盟和參加哪個聯(lián)盟,同時必須遵循以下規(guī)則:(1某個Agent 是否參加某個聯(lián)盟主要由哪個聯(lián)盟能夠使它的效用函數(shù)值最大所決定。(2Agent 在決策參加某個聯(lián)盟之前,必須知道A 中其他Agent 資源的使用情況。這些信息可以通過網(wǎng)格系統(tǒng)中網(wǎng)格信息服務模塊獲得。

16、(3每個Agent 至多參加一個聯(lián)盟。(4參加某個聯(lián)盟后,不能中途退出,只有等到聯(lián)盟中的任務執(zhí)行完畢后,方可解散聯(lián)盟。(5計算網(wǎng)格中的Agent 必須使用統(tǒng)一的時間。3基于Agent 的網(wǎng)格資源共享聯(lián)盟的分配機制基于Agent 的網(wǎng)格資源共享聯(lián)盟的分配機制,主要由A -gent 搜索最優(yōu)聯(lián)盟策略和多黨協(xié)商機制組成。3.1尋找最優(yōu)的資源共享聯(lián)盟的策略假設所有的Agent 都是通過基于Agent 的網(wǎng)格資源共享聯(lián)盟的分配機制來尋找合適聯(lián)盟。在計算網(wǎng)格中,每個Agent都是貪婪地尋找最優(yōu)聯(lián)盟,所謂最優(yōu)聯(lián)盟就是這個聯(lián)盟能夠使它的效用最大而且聯(lián)盟的大小盡可能小。每個Agent 在開始與其他的Agent

17、協(xié)商之前,需要首先評估系統(tǒng)中潛在的聯(lián)盟,這主要是根據(jù)可以獲得的其他Agent 的空閑分配函數(shù)來確定潛在的聯(lián)盟。在實際過程中,如果某個任務從一個Agent 遷移到另一個Agent 中去執(zhí)行,會增加額外的通信花費。因此,Agent 都是試圖找到一個聯(lián)盟,這樣的聯(lián)盟盡可能少的遷移任務,并且使得效用最大。同時,每個Agent 都更傾向于參加規(guī)模比較小的聯(lián)盟。即使假設Agent 能夠知道其他Agent 的空閑資源的分配函數(shù),它也不能夠使用本地的調(diào)度策略進行分配。Agent 必須通過協(xié)商形成資源共享聯(lián)盟來對資源進行分配。3.2形成資源共享聯(lián)盟的多黨協(xié)商機制聯(lián)盟的可能空間:一個Agent 都是僅僅考慮包括自

18、身的可能聯(lián)盟,對于每一個Agent 來說,可能的聯(lián)盟空間都是2R -1。協(xié)商過程:Agent 主要是通過發(fā)送信息進行協(xié)商,對于每一個Agent 來說,協(xié)商過程主要是處理來自外部Agent 的信息,在協(xié)商過程中的任何決策都必須由Agent 的協(xié)商策略決定。協(xié)商策略:基于Agent 的網(wǎng)格資源共享聯(lián)盟的分配機制中,所有的Agent 都必須使用統(tǒng)一的協(xié)商策略來形成資源共享聯(lián)盟。(1每個Agent 可以向多個聯(lián)盟發(fā)送請求加入信息,而無需等待聯(lián)盟的證實信息。每個Agent 希望參加的聯(lián)盟Agent 0Agent 1Agent 2Agent 3Agent 4Agent 5Agent 6Agent 7Age

19、nt 8Agent 950,30,11,22,04,160,2,51,52,13,04,25,370,1,21,5,62,0,33,44,55,4,66,2,480,2,3,71,4,62,73,2,64,0,25,3,76,0,17,090,41,4,62,0,63,1,84,85,6,86,17,08,4,5100,11,42,0,5,83,0,5,84,5,95,7,86,0,4,77,0,18,1,99,5,8實際聯(lián)盟結構01,523402,413,50,3245,60123564,701,52,84,7602,73,516,89Agent 個數(shù)表1每個聯(lián)盟希望參加的聯(lián)盟與實際的聯(lián)盟結

20、構計算所有可能聯(lián)盟空間開始發(fā)現(xiàn)最優(yōu)聯(lián)盟返回等待接受或者拒絕信息收到其他Agent 的信息沒有發(fā)送消息給其他Agent 或以前發(fā)送的信息被拒存在可能的聯(lián)盟發(fā)送給其他Agent 信息聯(lián)盟是其自身是否是否否是否是圖3Agent 共享聯(lián)盟形成機制流程圖(2每個Agent 都是參加最早證實的聯(lián)盟。(3每個Agent 都是貪婪地接受最優(yōu)的聯(lián)盟。(4每個Agent 即使收到了多個聯(lián)盟的請求加入的信息,它也必須僅僅接受其中的一個。(5當聯(lián)盟形成、失敗、或者超時時,Agent 都會終止它的協(xié)商過程。如果Agent 離開聯(lián)盟,則不能得到任何的報酬,因為這些Agent 都是使用貪婪的搜索策略尋找最優(yōu)聯(lián)盟。并且它們認

21、為首先發(fā)現(xiàn)的聯(lián)盟就是最優(yōu)的聯(lián)盟。3.3基于Agent 的網(wǎng)格資源共享聯(lián)盟的分配流程基于Agent 的網(wǎng)格資源共享聯(lián)盟的分配流程如圖3所示,具體過程如下:步驟1查看可能的聯(lián)盟空間是否為空,如果為空,則計算所有可能的聯(lián)盟空間。步驟2首先判斷該Agent 是否已經(jīng)找到最優(yōu)聯(lián)盟,如果找到了最優(yōu)聯(lián)盟,返回終止,否則,檢查是否收到其他Agent 發(fā)來的信息,如果收到來自其他Agent 的信息,則該Agent 決策是否參加該聯(lián)盟,如果參加該聯(lián)盟,則找到了最優(yōu)聯(lián)盟,終止返回。如果沒有收到來自其他Agent 的信息,轉(zhuǎn)步驟3。步驟3判斷是否發(fā)送給其他Agent 信息,如果發(fā)送過信息,判斷發(fā)送的信息是否被拒,沒有

22、遭受拒絕轉(zhuǎn)步驟4。否則判斷是否存在可能的聯(lián)盟,如果存在可能的聯(lián)盟,等待接受信息或者拒絕信息,轉(zhuǎn)步驟2。如果不存在可能的聯(lián)盟,則該聯(lián)盟由自身組成。步驟4該Agent 沒有發(fā)送給其他Agent 信息,檢查是否存在可能的聯(lián)盟,如果存在可能的聯(lián)盟,則發(fā)送給其他Agent 信息,轉(zhuǎn)步驟3。否則,最優(yōu)聯(lián)盟是其自身。4實驗結果利用網(wǎng)格的模擬環(huán)境來模擬提出的網(wǎng)格資源分配方法,模擬環(huán)境是Gridsim 和JADE (Java Agent Development Frame -work。GridSim 是一個在Windows 和Linux 的平臺上都可以運行的網(wǎng)格模擬器,該模擬器是用Java 編寫的,所以具有跨平

23、臺特性。GridSim 可以進行網(wǎng)格調(diào)度算法的模擬,可以通過提供的method 來編寫模擬文件,從而完成模擬的過程。JADE 是符合FIPA 規(guī)范的多Agent 系統(tǒng)軟件開發(fā)框架,用來開發(fā)滿足FIPA 標準的智能Agent 和多Agent 的應用程序,同時它也提供豐富的移動Agent 開發(fā)工具,包含兩個主要產(chǎn)品:滿足FIPA 規(guī)范的Agent 運行平臺和Agent 開發(fā)包。實驗環(huán)境用JADE 來構建A -gent 并實現(xiàn)Agent 間的交互,利用Gridsim 實現(xiàn)網(wǎng)格資源的分配過程的模擬。在實驗中,分別構建了5到10個Agent ,每個Agent 有若干資源,實驗主要說明以下幾個問題:(1A

24、gent 希望參加的聯(lián)盟與實際參加的聯(lián)盟的區(qū)別?(2Agent 間交互信息與Agent 個數(shù)之間的關系如何?(3自利Agent 與合作Agent 對于網(wǎng)格資源分配效用的區(qū)別?表1顯示了Agent 希望參加的聯(lián)盟結構與實際參加的聯(lián)盟結構之間的區(qū)別。由于每個Agent 都希望參加盡可能小的聯(lián)盟,所以在實驗環(huán)境中,假設每個聯(lián)盟大小不會大于2。表中的數(shù)字代表Agent 的編號,例如:0,3表示是由Agent 0和Agent 3構成的聯(lián)盟。隨著Agent 數(shù)量的增加,可能聯(lián)盟的空間指數(shù)增加,因而這些Agent 之間的交互信息量也是指數(shù)增加。圖4顯示了隨著Agent 數(shù)量的增加,每個Agent 接收到平均

25、信息量、可能聯(lián)盟空間的大小以及總的信息量之間的關系。圖5顯示了自利Agent 與合作Agent 對于網(wǎng)格中資源的效用是有很大的區(qū)別,一般而言,由合作Agent 組成網(wǎng)格中的資源效用比由自利Agent 組成網(wǎng)格中的資源效用大。這主要是參考文獻:1張穎峰,李毓麟.基于進化算法的網(wǎng)格計算資源管理調(diào)度系統(tǒng)J.計算機工程,2003,29(15:110-111.2Xu Zhihong ,Sun Ji -zhou.An ant algorithm based grid computingand task schedulingJ.Journal of Tianjin University ,2004,37(5

26、.3Li Xing ,Xu Zhi-hong ,Shen Xue-qin.The improvements of ant al -gorithm-based task scheduling in gridJ.Journal of Hebei Univer -sity of Technology ,2004,33(1.4Abraham A ,Liu Hongbo ,Zhang Weishi.Jobs scheduling on compu -tational grids using fuzzy particle swarm algorithmJ.Knowledge-Based Intellige

27、nt Information and Engineering Systems ,2006,4252.5梁正友,支成秀.基于離散粒子群優(yōu)化算法的網(wǎng)格資源分配研究J.計算機工程與科學,2007,29(10:77-78.6Maniezzo V ,Colorni A.Ant system applied to the quadratic assign -ment problemJ.IEEE Trans Knowl Data Eng ,1999,11(5:769-778.7Kennedy J ,Eberhart R C .Particle swarm optimization ProcC/IEEEInt

28、ernational Conference on Neural Networks ,Part IV.Piscataway NJ :IEEE Service Center ,1995:1942-1948.8Liao Ching-Jong ,Tseng Chao-Tang ,Luarn Pin.A discrete version of particle swarm optimization for flowshop scheduling problems J.Computers &Operations Research ,2007,34(10:3099-3111.9Eberhart R

29、C ,Kennedy J.Swarm intelligenceM.S.l.:Morgan Kauf -manns ,2001.10支成秀,梁正友.融合粒子群優(yōu)化算法與蟻群算法的隨機搜索算法J.廣西科學院學報,2006,22(4:231-233.11Buyya R ,Murshed M.GridSim :A toolkit for the modeling andsimulation of distributed resource management and scheduling for grid computingJ.J.Concurrency and Computation :Practi

30、c-Experi -ence (CCPE ,2002,14(13-15:1175-1220.(上接104頁ÁÂÁÃÁÁÃÂÁÄÁÁÄÂÁÅÁÁÅÂÁÁÂÃÄÅÆÇÈÉ ÆÂ Æ Ä ÁÂÃÄÅÆ

31、99;ÈÉ ÆÂ Æ Â Å Æ ÂÄÅ Ã Â !" Ä ÆÇÈÉ ÆÂ Æ Ä Æ ÂÉÆ# Æ! Ã5ags 6ags 7ags 8ags 9ags 10ags350300250200150100500Total Number of Messages Total Number of Possible C

32、oalitions Average Number of Messages from One Agent 圖4可能聯(lián)盟空間、每個Agent 平均接收到的信息量和總信息交互量之間的關系ÁÂÃÃÃÁÄÃÃÃÁÅÃÃÃÁÆÃÃÃÁÇÃÃÃÃÇÃÃÃÆÃÃÃÅ

33、ÃÃÃÄÃÃÃÂÃÃÃIdl Int Idl Ag Ov Ag Ov Ag 500040003000200010000-1000-2000-3000-4000-50005a gs6ag s7ag s8ag s9ag s10a gsIdleCapacity for Self-Interested Agents Idle Capacity for Cooperative Agents Overload for Self-Interested Agents Overload forCoope

34、rative Agents圖5可能聯(lián)盟空間、每個Agent 平均接收到的信息量和總信息交互量之間的關系因為由合作Agent 組成的網(wǎng)格中的資源是所有合作Agent 提供的資源,他們不考慮自己的效用。通過實驗結果表明自利Agent 對網(wǎng)格資源分配具有很大的影響,自利Agent 間的交互信息量比合作Agent 的大,而且自利Agent 的負載量也比合作Agent 的負載量大,從圖5可以清楚地看到。因此,設計網(wǎng)格資源分配機制的時候必須考慮Agent 的自利性。5結語對資源分配的研究,是網(wǎng)格計算系統(tǒng)資源管理的一個重要問題。聯(lián)盟機制作為一種有效的合作方法,已經(jīng)變成一個研究熱點。本文提出了一種通過Agen

35、t 聯(lián)盟進行資源分配的方法,該方法主要有Agent 搜索最佳聯(lián)盟策略和多黨協(xié)商機制組成。本文把計算網(wǎng)格系統(tǒng)中自利Agent 之間的資源共享問題轉(zhuǎn)化為一個形成資源共享聯(lián)盟的問題。提出了一種分布式的聯(lián)盟形成機制,該機制主要通過多黨協(xié)商來實現(xiàn)。在這個分布式的聯(lián)盟形成機制中,每個Agent 都使用自身的搜索策略來尋找最優(yōu)聯(lián)盟,并且每個Agent 都根據(jù)自身的協(xié)商策略來決策參加哪個聯(lián)盟。實驗結果表明自利Agent 對網(wǎng)格資源的分配具有很大的影響,因此,設計網(wǎng)格資源分配機制的時候必須考慮Agent 的自利性。在網(wǎng)格計算系統(tǒng)中,為了使資源共享聯(lián)盟更加適用,下一步工作主要從以下幾個方面考慮:Agent 局部分

36、配機制對資源共享機制有什么影響?在形成資源共享聯(lián)盟的過程中考慮信任因素。參考文獻:1Caillou P ,Aknine S ,Pinson S.A multi -agent method for formingand dynamic restructuring of pareto optimal coalitionsC/Proceed -ings of the First International Joint Conference on Autonomous A -gents and Multi-agent Systems ,2002.2Foster I ,Kesselman C.The grid :blueprint for a new computing in -frastructureM.S.l.:Morgan Kaufmann ,1998.3He L ,Ioerger T R.A quantitative model of capabilities in multi-a -gent systemsC/Proceedings of the International Conference on Ar -tifi