摘 要： 介紹了一種基于多Agent的網(wǎng)格資源調度方法，并提出了一種負載均衡算法設計思想，以改善網(wǎng)格環(huán)境中資源分配不均的問題。
關鍵詞: 網(wǎng)格；Agent；資源調度；負載均衡
?
網(wǎng)格是把分布在不同地理位置上的計算資源(包括高端服務器、集群系統(tǒng)、MPP系統(tǒng)大型存儲設備、數(shù)據(jù)庫等)通過因特網(wǎng)整合成一臺巨大的超級計算機，實現(xiàn)各種資源的全面共享。網(wǎng)格節(jié)點是這些網(wǎng)格計算資源的提供者。網(wǎng)格的根本特征不是它的規(guī)模，而是資源共享，消除資源孤島。因此網(wǎng)格的關鍵技術是資源調度，如何有效地調度網(wǎng)格資源將成為網(wǎng)格系統(tǒng)是否可用的關鍵問題。
資源調度和負載均衡是分布式系統(tǒng)設計中的關鍵問題。傳統(tǒng)的主從節(jié)構無法避免單點故障、性能瓶頸等問題，而對等網(wǎng)絡[1]P2P是一種完全分布式的計算模型，不存在這些問題。如果一個系統(tǒng)能保持良好的負載均衡狀態(tài)，那么該系統(tǒng)可以獲得較高的吞吐量。本文首先介紹了一種基于多Agent的網(wǎng)格資源調度方法，并在此方法的基礎上提出了一種負載均衡算法的設計思想。
1 基于多Agent的網(wǎng)格資源調度模型
在網(wǎng)格應用開發(fā)過程中，采用多Agent技術能夠提高網(wǎng)格系統(tǒng)的智能性、靈活性和健壯性。Agent具有自主性，無需進行集中的控制就可以自主決定自己的行為，也具有交互性，相互間可以進行協(xié)作，協(xié)同完成任務。此外，可以將較復雜的任務封裝在Agent中，由多個Agent相互協(xié)作，可以完成單個Agent或其他軟件不能完成的任務。鑒于網(wǎng)格的動態(tài)性，需要動態(tài)、有自適應能力的調度算法來對網(wǎng)格資源進行有效調度。
1.1? 基于多Agent的網(wǎng)格系統(tǒng)節(jié)構圖
基于多Agent的網(wǎng)格系統(tǒng)在邏輯上可以分為4個層次，如圖1所示。系統(tǒng)中，客戶端的任務主要是確定用戶的操作請求，資源端負責處理用戶請求，網(wǎng)格中間件致力于整合各種網(wǎng)格資源。網(wǎng)格資源請求Agent作為用戶代理，負責協(xié)調用戶與網(wǎng)格資源Agent間的交互。其目的是使用戶無需與網(wǎng)格資源直接聯(lián)系，即可更加方便地使用所需的資源。
?
用戶通過客戶端的應用程序提出服務請求，激活網(wǎng)格資源請求Agent。網(wǎng)格資源請求Agent依據(jù)用戶提出的要求，在眾多的資源提供者中進行篩選。滿足用戶要求的資源可能會有多個，網(wǎng)格資源請求Agent可以代替用戶做出最終決策，確定一個最佳資源提供者。滿足要求的資源也可能不存在，此時，網(wǎng)格資源請求Agent可以把若干個資源進行組合，以此得到滿足用戶要求的資源。任務完成后，再由網(wǎng)格資源請求Agent將最終節(jié)果傳給客戶端。
1.2? 基于多Agent的網(wǎng)格資源調度節(jié)構圖
網(wǎng)格的實現(xiàn)可以依賴不同的拓撲節(jié)構，將Agent引入網(wǎng)格，并采用樹型節(jié)構作為網(wǎng)格模型[2-6]。其優(yōu)點是跨域搜索資源時，可以在多項式時間內(nèi)完成匹配。其中，底層Agent直接管理其轄區(qū)內(nèi)的資源節(jié)點，記錄資源信息，采用一定的資源策略來實現(xiàn)任務和資源的匹配。上層Agent主要負載任務的跨域調度。它可以將其子Agent轄區(qū)內(nèi)沒有得到匹配的任務，提交到另一個子Agent進行匹配。
基于Agent網(wǎng)格模型中，Agent節(jié)點包括5個功能模塊和2種數(shù)據(jù)節(jié)構。每個節(jié)點都有任務請求客戶端和任務應答客戶端,圖2是基于Agent網(wǎng)格模型下的資源調度模型，它描述了底層Agent節(jié)點和資源節(jié)點的各個模塊和模塊的工作流程。
?
在Agent接受任務到建立任務連接過程中，如果任務池中為非空，第一步從任務池中提取第i項任務；第二步分析第i項任務的資源需求；第三步由動態(tài)平衡負載模塊(全局資源剩余率，全局任務空閑率，全局負載變化率)生成網(wǎng)格資源調度的上限；第四步調用此模塊返回匹配節(jié)果；第五步如果有匹配節(jié)果，就創(chuàng)建資源節(jié)點和任務請求節(jié)點間的工作流，成功通訊后斷開本連接；最后在第十步檢測到第i項任務完成后，在Agent中清楚所有任務。
任務處理模塊將收到的任務放入任務等待隊列，如果任務等待隊列為非空，在第八步任務管理器從任務隊列中選取第i項任務運行并更新任務狀態(tài)表匯總的狀態(tài)，第九步中若任務完成，調用任務釋放模塊與任務請求節(jié)點通訊，第十一步中若任務已經(jīng)成功歸還任務請求節(jié)點，則更新任務狀態(tài)，收回所占資源。
1.3?基于多Agent的網(wǎng)格資源管理模型下的的緊鄰算法
代理對計算資源和Web用戶是透明的，它只與自己相連的節(jié)點(代理)打交道，接受這些代理或者計算資源的注冊和撤銷[7]。如圖3所示，計算資源可以選擇某個代理進行注冊，每個代理最終管理一組資源，響應用戶的任務請求。由于可用帶寬以及主機性能等原因，各個代理的資源利用率、負載等不盡相同，可能會出現(xiàn)某些代理服務器負載過重、有些代理服務器處于輕負載運行狀態(tài)的情況。一個代理接收到一個新的計算任務以后，如果自身負載過重，或者自身的可用資源難以滿足新的計算任務的要求，就會根據(jù)負載平衡算法，通過ACP(Agent Communication Protocol)把計算任務交給其他代理完成。
?
?
假定并行處理系統(tǒng)是由多個節(jié)點按照一定的節(jié)構相互連接構成的并行處理網(wǎng)絡，每個節(jié)點只能與其直接連接的節(jié)點通信，計算負載也只能通過這些連接移動。在負載平衡過程中，每個節(jié)點只能與其周圍的節(jié)點進行負載交換，通過多次循環(huán)迭代實現(xiàn)系統(tǒng)的負載平衡。?
2 基于多Agent的網(wǎng)格資源調度層次模型的負載均衡算法
2.1?負載平衡算法的思想
本文設計的負載平衡算法屬于動態(tài)平衡算法，決策取決于系統(tǒng)當前的狀態(tài)。也就是說，系統(tǒng)可以根據(jù)當前的負載分布情況，對各個節(jié)點上的負載進行動態(tài)調整，使已經(jīng)分配給重載節(jié)點上的任務，通過通信設備，遷移到輕載的節(jié)點上去，從而提高系統(tǒng)的資源利用率，減小任務的平均響應時間。
算法思想是緊鄰上限機制(Neareast Neighbor-Upper Bound)，它假定并行處理系統(tǒng)是由多個節(jié)點按照一定的節(jié)構相互連接構成的并行處理網(wǎng)絡，每個節(jié)點只能與其直接連接的節(jié)點通信，計算負載也只能通過這些連接移動。每個節(jié)點對于任務提交的資源要求進行分析，得出其任務可以完成的底限；再在底限的基礎上適當上浮一定比例，得到一個資源要求的上限；這樣，就有一個資源要求區(qū)間，用這個區(qū)間值在資源中進行匹配，在所得的資源節(jié)點中，使用一定的資源搜索算法，進行具體的資源定位。在負載平衡過程中，通過節(jié)點上限機制和緊鄰的節(jié)點多次循環(huán)迭代實現(xiàn)系統(tǒng)的負載平衡。
2.2?負載平衡算法的設計
當接受某項任務后，網(wǎng)格的負載和吞吐量必然發(fā)生變化；不同任務引起的變化不同，對上限的影響也是不同的。任務對整個網(wǎng)格負載影響，是以接受節(jié)點資源能力的變化表現(xiàn)出來的。先給出2個公式：
其中，節(jié)點負載率(NLR)描述節(jié)點的當前已耗費的資源能力；節(jié)點剩余資源率(NRRR)描述節(jié)點的未來資源能力。為了定義上面2個概念，再引入2個概念：單節(jié)點已使用資源(NUR)和單節(jié)點全部資源(NAR)。NLR與單節(jié)點的上限(SUB)成正向關系。
單個任務對網(wǎng)格吞吐量的影響很小，可近似看作不變。此時，網(wǎng)格中部分資源的負載增大，剩余資源減少。為使負載不繼續(xù)變大，這部分資源通過緊鄰算法將更多能力較類似的節(jié)點(能力較強的)考慮進來確保上限度量UB<1。
相同負載的強節(jié)點和弱節(jié)點的剩余資源能力是不一樣的，剩余資源能力高的節(jié)點對SUB調高的愿望較低；剩余資源能力低的節(jié)點則相反。所以，NRRR與SUB成逆向關系。于是，有下面的表達式：
其中，SUB由節(jié)點的資源能力在整個網(wǎng)格中的地位決定。因此，它不僅與節(jié)點自己的能力有關，還與網(wǎng)格資源的節(jié)構有關。
其中,SUBS=
Ci即網(wǎng)格所有節(jié)點的上限之和，被稱為網(wǎng)格動態(tài)節(jié)點。它應當只與整個網(wǎng)表初始權值設置格的資源能力節(jié)構有關。而網(wǎng)格的資源能力節(jié)構是動態(tài)變化的，它取決于很多因素:全局任務空閑率(TTFR)反映了網(wǎng)格當前的吞吐量，全局負載變化率(TLCR)反映了全局任務資源要求的波動速率，全局剩余資源率(TRRR) 反映了網(wǎng)格今后的能力。
綜上所述，節(jié)點動態(tài)上限機制最終可以下面的形式來描述：C={f(TTFR,TLCR,TRRR,UC)}，UC為其他因素。其中TTFR，GSRR與UB成正向關系，TLCR與UB成加速關系.則有：
其中k為調整常數(shù)，將求和項調整為網(wǎng)格可以感知的程度，并確保UB<1。
網(wǎng)格環(huán)境中存在著多個Agent，如圖4所示。
?
??? 每個Agent周圍都分布了多個節(jié)點。在單個Agent周圍的節(jié)點和節(jié)點之間通過緊鄰算法，實現(xiàn)系統(tǒng)的協(xié)調，解決節(jié)點和節(jié)點之間的負載平衡問題。在Agent和Agent之間也通過緊鄰算法和ACP，達到網(wǎng)格資源調度的協(xié)調。在多Agent網(wǎng)格資源環(huán)境中，利用緊鄰算法實現(xiàn)了節(jié)點與節(jié)點的協(xié)調、單個Agent與單個Agent的協(xié)調，使整個網(wǎng)格環(huán)境實現(xiàn)分布式的協(xié)同。再利用上限度量的設定，最終實現(xiàn)系統(tǒng)的網(wǎng)絡負載平衡。
3?基于多Agent的負載均衡算法的優(yōu)點
本負載均衡算法最大的特點在于：根據(jù)網(wǎng)格實時負載和吞吐量等信息進行動態(tài)調度，節(jié)點與節(jié)點之間運用緊鄰算法，設定上限量度，恰如其分地選擇資源；能很好地解決小任務堆積強節(jié)點的問題；能夠實現(xiàn)資源預留功能；可擴展性強，它利用了1種兩級調度：一級調度采用動態(tài)上限機制，二級調度可以根據(jù)不同的網(wǎng)格系統(tǒng)來靈活、透明、有效率地選擇。
本文將Agent技術引入網(wǎng)格資源管理調度，提出了1個網(wǎng)格環(huán)境下基于Agent的上限機制負載均衡的設計思想，充分發(fā)揮了Agent的智能性、自主性，并提高了網(wǎng)格資源的利用效率。本算法較大地發(fā)揮了系統(tǒng)的負載平衡能力，提高了網(wǎng)格計算能力和資源利用率。
參考文獻
[1]?STOICA I, MORRIS R, KARGER D, et al. A scalable peer-to-peer lookup service for internet applications[A].Processing of ACM SIGCOMM[C]. New York: ACM Press, 2001．149-160．
[2] ?LI Chun Lin，LI La Yuan．Agent framework to support computational grid[J]．The Journal of Systems and Software，2004，70(1／2)：177-187．
[3] ?LI Chun Lin，LI La Yuan．Apply agent to build grid service management[J]．Computer Applications 2003(26)：323-240．
[4] ?CAO Jun Wei，SPOONER D P．Grid load balancing using intelligent agents[J]．Future Generation Compute Systems，2005(21)：135-149．
[5] ?FREY J，TANNENHAUM T，F(xiàn)OSTER I，et a1．A computation management agent for multi—institution all grids[J]．Cluster Computer，2002，5(3)：237-246．
[6]? CAO JunWei，JARVIS S A，SAINI S，et a1．An agent—based resource management system for grid computing[J]．Scientific Programming(Special Issue on Grid Computing)，2002，10(2)：135-148．
[7]? 趙姍,胡根,周興社.基于多Agent網(wǎng)格資源管理模型的負載均衡研究[J] .微電子學與計算機, 2005，22(10)：51-53.
[8] ?邸爍,鄭緯民，王鼎興，等．并行WWW服務器集群請求分配算法的研究[J]．軟件學報,1999,10(7):713-718．