摘 要： 介紹了一種基于多Agent的網格資源調度方法，并提出了一種負載均衡算法設計思想，以改善網格環境中資源分配不均的問題。
關鍵詞: 網格；Agent；資源調度；負載均衡
?
網格是把分布在不同地理位置上的計算資源(包括高端服務器、集群系統、MPP系統大型存儲設備、數據庫等)通過因特網整合成一臺巨大的超級計算機，實現各種資源的全面共享。網格節點是這些網格計算資源的提供者。網格的根本特征不是它的規模，而是資源共享，消除資源孤島。因此網格的關鍵技術是資源調度，如何有效地調度網格資源將成為網格系統是否可用的關鍵問題。
資源調度和負載均衡是分布式系統設計中的關鍵問題。傳統的主從節構無法避免單點故障、性能瓶頸等問題，而對等網絡[1]P2P是一種完全分布式的計算模型，不存在這些問題。如果一個系統能保持良好的負載均衡狀態，那么該系統可以獲得較高的吞吐量。本文首先介紹了一種基于多Agent的網格資源調度方法，并在此方法的基礎上提出了一種負載均衡算法的設計思想。
1 基于多Agent的網格資源調度模型
在網格應用開發過程中，采用多Agent技術能夠提高網格系統的智能性、靈活性和健壯性。Agent具有自主性，無需進行集中的控制就可以自主決定自己的行為，也具有交互性，相互間可以進行協作，協同完成任務。此外，可以將較復雜的任務封裝在Agent中，由多個Agent相互協作，可以完成單個Agent或其他軟件不能完成的任務。鑒于網格的動態性，需要動態、有自適應能力的調度算法來對網格資源進行有效調度。
1.1? 基于多Agent的網格系統節構圖
基于多Agent的網格系統在邏輯上可以分為4個層次，如圖1所示。系統中，客戶端的任務主要是確定用戶的操作請求，資源端負責處理用戶請求，網格中間件致力于整合各種網格資源。網格資源請求Agent作為用戶代理，負責協調用戶與網格資源Agent間的交互。其目的是使用戶無需與網格資源直接聯系，即可更加方便地使用所需的資源。
?
用戶通過客戶端的應用程序提出服務請求，激活網格資源請求Agent。網格資源請求Agent依據用戶提出的要求，在眾多的資源提供者中進行篩選。滿足用戶要求的資源可能會有多個，網格資源請求Agent可以代替用戶做出最終決策，確定一個最佳資源提供者。滿足要求的資源也可能不存在，此時，網格資源請求Agent可以把若干個資源進行組合，以此得到滿足用戶要求的資源。任務完成后，再由網格資源請求Agent將最終節果傳給客戶端。
1.2? 基于多Agent的網格資源調度節構圖
網格的實現可以依賴不同的拓撲節構，將Agent引入網格，并采用樹型節構作為網格模型[2-6]。其優點是跨域搜索資源時，可以在多項式時間內完成匹配。其中，底層Agent直接管理其轄區內的資源節點，記錄資源信息，采用一定的資源策略來實現任務和資源的匹配。上層Agent主要負載任務的跨域調度。它可以將其子Agent轄區內沒有得到匹配的任務，提交到另一個子Agent進行匹配。
基于Agent網格模型中，Agent節點包括5個功能模塊和2種數據節構。每個節點都有任務請求客戶端和任務應答客戶端,圖2是基于Agent網格模型下的資源調度模型，它描述了底層Agent節點和資源節點的各個模塊和模塊的工作流程。
?
在Agent接受任務到建立任務連接過程中，如果任務池中為非空，第一步從任務池中提取第i項任務；第二步分析第i項任務的資源需求；第三步由動態平衡負載模塊(全局資源剩余率，全局任務空閑率，全局負載變化率)生成網格資源調度的上限；第四步調用此模塊返回匹配節果；第五步如果有匹配節果，就創建資源節點和任務請求節點間的工作流，成功通訊后斷開本連接；最后在第十步檢測到第i項任務完成后，在Agent中清楚所有任務。
任務處理模塊將收到的任務放入任務等待隊列，如果任務等待隊列為非空，在第八步任務管理器從任務隊列中選取第i項任務運行并更新任務狀態表匯總的狀態，第九步中若任務完成，調用任務釋放模塊與任務請求節點通訊，第十一步中若任務已經成功歸還任務請求節點，則更新任務狀態，收回所占資源。
1.3?基于多Agent的網格資源管理模型下的的緊鄰算法
代理對計算資源和Web用戶是透明的，它只與自己相連的節點(代理)打交道，接受這些代理或者計算資源的注冊和撤銷[7]。如圖3所示，計算資源可以選擇某個代理進行注冊，每個代理最終管理一組資源，響應用戶的任務請求。由于可用帶寬以及主機性能等原因，各個代理的資源利用率、負載等不盡相同，可能會出現某些代理服務器負載過重、有些代理服務器處于輕負載運行狀態的情況。一個代理接收到一個新的計算任務以后，如果自身負載過重，或者自身的可用資源難以滿足新的計算任務的要求，就會根據負載平衡算法，通過ACP(Agent Communication Protocol)把計算任務交給其他代理完成。
?
?
假定并行處理系統是由多個節點按照一定的節構相互連接構成的并行處理網絡，每個節點只能與其直接連接的節點通信，計算負載也只能通過這些連接移動。在負載平衡過程中，每個節點只能與其周圍的節點進行負載交換，通過多次循環迭代實現系統的負載平衡。?
2 基于多Agent的網格資源調度層次模型的負載均衡算法
2.1?負載平衡算法的思想
本文設計的負載平衡算法屬于動態平衡算法，決策取決于系統當前的狀態。也就是說，系統可以根據當前的負載分布情況，對各個節點上的負載進行動態調整，使已經分配給重載節點上的任務，通過通信設備，遷移到輕載的節點上去，從而提高系統的資源利用率，減小任務的平均響應時間。
算法思想是緊鄰上限機制(Neareast Neighbor-Upper Bound)，它假定并行處理系統是由多個節點按照一定的節構相互連接構成的并行處理網絡，每個節點只能與其直接連接的節點通信，計算負載也只能通過這些連接移動。每個節點對于任務提交的資源要求進行分析，得出其任務可以完成的底限；再在底限的基礎上適當上浮一定比例，得到一個資源要求的上限；這樣，就有一個資源要求區間，用這個區間值在資源中進行匹配，在所得的資源節點中，使用一定的資源搜索算法，進行具體的資源定位。在負載平衡過程中，通過節點上限機制和緊鄰的節點多次循環迭代實現系統的負載平衡。
2.2?負載平衡算法的設計
當接受某項任務后，網格的負載和吞吐量必然發生變化；不同任務引起的變化不同，對上限的影響也是不同的。任務對整個網格負載影響，是以接受節點資源能力的變化表現出來的。先給出2個公式：
其中，節點負載率(NLR)描述節點的當前已耗費的資源能力；節點剩余資源率(NRRR)描述節點的未來資源能力。為了定義上面2個概念，再引入2個概念：單節點已使用資源(NUR)和單節點全部資源(NAR)。NLR與單節點的上限(SUB)成正向關系。
單個任務對網格吞吐量的影響很小，可近似看作不變。此時，網格中部分資源的負載增大，剩余資源減少。為使負載不繼續變大，這部分資源通過緊鄰算法將更多能力較類似的節點(能力較強的)考慮進來確保上限度量UB<1。
相同負載的強節點和弱節點的剩余資源能力是不一樣的，剩余資源能力高的節點對SUB調高的愿望較低；剩余資源能力低的節點則相反。所以，NRRR與SUB成逆向關系。于是，有下面的表達式：
其中，SUB由節點的資源能力在整個網格中的地位決定。因此，它不僅與節點自己的能力有關，還與網格資源的節構有關。
其中,SUBS=
Ci即網格所有節點的上限之和，被稱為網格動態節點。它應當只與整個網表初始權值設置格的資源能力節構有關。而網格的資源能力節構是動態變化的，它取決于很多因素:全局任務空閑率(TTFR)反映了網格當前的吞吐量，全局負載變化率(TLCR)反映了全局任務資源要求的波動速率，全局剩余資源率(TRRR) 反映了網格今后的能力。
綜上所述，節點動態上限機制最終可以下面的形式來描述：C={f(TTFR,TLCR,TRRR,UC)}，UC為其他因素。其中TTFR，GSRR與UB成正向關系，TLCR與UB成加速關系.則有：
其中k為調整常數，將求和項調整為網格可以感知的程度，并確保UB<1。
網格環境中存在著多個Agent，如圖4所示。
?
??? 每個Agent周圍都分布了多個節點。在單個Agent周圍的節點和節點之間通過緊鄰算法，實現系統的協調，解決節點和節點之間的負載平衡問題。在Agent和Agent之間也通過緊鄰算法和ACP，達到網格資源調度的協調。在多Agent網格資源環境中，利用緊鄰算法實現了節點與節點的協調、單個Agent與單個Agent的協調，使整個網格環境實現分布式的協同。再利用上限度量的設定，最終實現系統的網絡負載平衡。
3?基于多Agent的負載均衡算法的優點
本負載均衡算法最大的特點在于：根據網格實時負載和吞吐量等信息進行動態調度，節點與節點之間運用緊鄰算法，設定上限量度，恰如其分地選擇資源；能很好地解決小任務堆積強節點的問題；能夠實現資源預留功能；可擴展性強，它利用了1種兩級調度：一級調度采用動態上限機制，二級調度可以根據不同的網格系統來靈活、透明、有效率地選擇。
本文將Agent技術引入網格資源管理調度，提出了1個網格環境下基于Agent的上限機制負載均衡的設計思想，充分發揮了Agent的智能性、自主性，并提高了網格資源的利用效率。本算法較大地發揮了系統的負載平衡能力，提高了網格計算能力和資源利用率。
參考文獻
[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，FOSTER 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網格資源管理模型的負載均衡研究[J] .微電子學與計算機, 2005，22(10)：51-53.
[8] ?邸爍,鄭緯民，王鼎興，等．并行WWW服務器集群請求分配算法的研究[J]．軟件學報,1999,10(7):713-718．