基于改進蟻群算法的網格資源調度研究

陳雨時，曲海成，2+，龔小川

(1.哈爾濱工業大學電子與信息工程學院，黑龍江哈爾濱150001;2.遼寧工程技術大學軟件學院，遼寧葫蘆島125105)

0 引言

目前集群計算和網格技術被廣泛應用到遙感影像處理系統中。在集群計算環境中，PC機或工作站通過局域網連接，為用戶提供高性能計算。由于集群計算處于一個局域網內，所以它的應用具有局限性，通常計算能力也有限。而網格計算是把不同地理位置的網格資源結合起來構成一個虛擬的超級計算機［1］，網格計算對資源的類型及地理位置沒有限制，可以為系統提供很強的計算能力［2］。但是網格計算是通過網絡把不同地域的計算資源結合起來構成一個整體，這就使它不同于傳統的集群計算。網格調度問題與傳統集群計算的調度問題相比更加難以解決，主要原因有:網格系統任務的屬性更加復雜，如:任務量變大、任務具有優先級、任務對資源的需求限制等;網格資源的屬性具有實時多變性、網格資源的多樣性、類型的復雜性等特點。因此，網格系統中資源的管理和調度是網格系統中的關鍵部分，其中任務分配和負載均衡問題是重點需要解決的難題。在網格計算環境中，負載均衡算法的目標是使計算資源上的網格任務盡量達到平衡，所有任務的執行時間最短和每個資源的利用率達到最高［5］。文中提出了一種改進的ACO調度算法，可以使任務在更短的時間內完成，網格資源的利用率顯著提高。網格任務為遙感資源的空間檢索任務，即:將用戶請求的多邊形區域 (可能是凸多邊形、凹多邊形或是帶有孔的多邊形等)，通過射線法［6］與數據庫中記錄的多邊形區域進行匹配，找出滿足用戶需求的記錄。多邊形形狀越復雜，任務計算量越大，資源的空閑時間越難掌握，而改進ACO算法適合解決這類問題。

1 網格調度算法分析

網格調度技術主要涉及任務負載均衡算法的性能及優化，主要分為兩大類:靜態調度算法和動態調度算法。在靜態調度算法中，所有任務的信息、資源的信息及網絡帶寬等信息都是預先知道的，任務必須分配到適合的網格資源執行。靜態負載均衡算法主要的缺點是:在任務的執行過程中，所有任務和資源的信息都是固定不變的。相反，動態調度算法是通過獲得任務和資源的實時狀態信息進行任務的調度，這樣就能更準確地進行任務的分發。經過對比實驗可以看出，靜態負載均衡算法更易實施，但是動態負載均衡算法有更好的效果。

網格資源調度是一個NP完全問題。許多算法已經被應用于解決此問題。常用的算法包括:OLB、MET、MCT、SWA、KPB、Min-Min、Max-Min、Dupplex、MaxStd 和 GA等［3-5］，下面對其進行具體的對比分析。

OLB(opportunistic load balancing)是在不考慮任務執行時間的情況下，按最短的分配表以任意的順序把每個任務分配給網格資源。OLB算法的目的是為了平衡各網格資源的負載，但由于它沒有考慮任務執行時間，所以很難達到網格負載均衡的目的。

MET(minimum execution time)是不考慮網格資源當前的負載情況，把任務分發給執行該任務最快的網格節點。MET算法企圖找到好的任務-網格資源匹配，但是由于它沒有考慮網格資源目前的任務量，這樣會導致各個網格資源節點負載的不平衡性，處理能力強的資源節點總是有很多任務，處理能力差的資源節點可能總是處于空閑狀態。

MCT(minimum completion time)算法的思想是把任務分發給最早完成該任務的網格資源節點。其中任務j在資源節點m完成時間定義為任務j在節點m上的執行時間與目前節點m上任務執行所需的時間之和。這是一種同時考慮了任務執行時間和網格資源節點負載情況的啟發式算法。

Min-Min算法是首先獲得最短執行時間的任務j，以及得到完成任務j的MCT最少的網格資源節點m，然后把任務j分發給網格資源節點m執行。Min-Min與MCT都利用了任務完成時間，但是由于Min-Min算法在每次選擇任務的時候選擇的是所有任務中最小完成時間的任務，這樣將會減少完成所有任務所需的時間。Min-Min算法在網格資源節點負載均衡方面要優于MCT算法。

Max-Min算法與Min-Min算法很類似。同樣是選擇任務j完成時間最短的網格資源節點，但是與Min-Min算法不同之處是任務j選擇的是完成所需時間最大的任務。Max-Min算法更適用于復雜任務的調度問題。但是實驗結果表明Max-Min算法不是在所有問題上都優于Min-Min。

MaxStd(maximum standard deviation)在 MaxStd算法中，任務的期望執行時間擁有最高的標準差優先執行。執行的標準差低，在不同的資源節點上任務執行時間變化很小的任務推后執行。

GA(genetic algorithm)是Holland發現的，該算法是模擬自然生物的進化過程，基于達爾文的自然選擇準則。GA通過控制大量染色體來實現進化，其中這些染色體是根據問題進行描述的，每個染色體代表解空間的一個潛在解。在每代循環過程中，對染色體的操作主要包含3個:復制、交叉和變異。通過這3個過程，不但可以保留較好的解，還可以產生更好的解。因為GA以上的優點，它現在已經廣泛應用于啟發式問題的求解問題。同時，很多研究者也把GA應用到了網格任務調度的問題中，并且研究發現GA可以給該問題帶來較好的解。

ACO(ant colony optimization)也是一種分布式、啟發式算法，ACO的靈感來源于螞蟻群體尋找食物的行為，算法針對的是離散的優化問題［8］。它的研究模型來源于對真實螞蟻行為的觀測，通過開發真實螞蟻高度協作行為的自組織原型來 (self-organizing principle)來調動一群人工agent協作解決一些計算問題。螞蟻都是通過一種“媒介質”來協調他們之間的行動，所謂的“媒介質”指的是一種以環境的變化為媒介的間接通信形式，例如，螞蟻正在尋找食物時，會在其經過的路上釋放一種化學物質 (信息素)，隨著路徑上的化學物質的增加，也會增大其他螞蟻走同一條路的概率。ACO通過釋放信息素來實現螞蟻之間的間接通信，從而達到協調工作的目的。ACO算法利用人工螞蟻agent之間的協作來找到最優或次優解。這種算法也被廣泛的應用到許多NP問題中，并且取得的很好的效果。

2 改進ACO算法設計

ACO算法的主要特點有以下幾個方面［9-10］:

(1)網格任務調度是一種NP完全問題，由于ACO算法具有很強的自適應性，且具有正反饋的特點，這樣加快了網格任務調度的求解過程。

(2)ACO算法是以信息素為介質進行間接通信，通過蟻群釋放的信息素可以逐漸地發現最優解。前面也提到了，ACO算法給解決TPS、JSP、GCP等問題組合優化問題提供了很好的求解方式。網格任務調度問題正是一種組合優化問題，它是尋找一種任務與資源的最優組合方式，所以ACO算法同樣適用于網格任務調度問題。

(3)ACO算法是螞蟻之間通過利用釋放的信息素協同工作尋找最優解的問題，充分體現了ACO算法中螞蟻個體之間的協作性與該算法很強的并行性。而網格計算本身是分布式計算中的一種，這樣ACO算法就可以利用算法本身的并行性和協作性為網格任務的分配提供方便。

(4)ACO算法反映的是群體智慧，不是個體智慧，所以算法自身具有很強的魯棒性，對系統初始化條件的要求不是太高，這使得ACO算法可以適用于復雜的網格計算環境。

通過對ACO算法以上幾個特點和網格任務調度本身特性的綜合分析可以得出，ACO算法適合于求解網格任務調度問題。

本文提出的改進ACO算法主要是在算法中引進了一個向量F=free(j)，1≤j≤m，其中m為網格資源數，free(j)表示資源j處于空閑狀態所需的時間。向量F引進以后，根據F可以更好地了解資源的運行情況，更容易掌握其任務負載量，這樣為選擇最適當的網格資源提供了關鍵信息，網格任務的調度的效果更佳。

在改進ACO算法中，網格計算系統把每個任務看出一只螞蟻。圖1為改進ACO算法的流程圖。

圖1 改進ACO算法的流程

改進ACO的算法主要步驟［11-12］為:

(1)獲得網格資源的狀態信息及任務的相關信息，對F進行初始化，網格資源信息素τj(t)與啟發式信息ηj(t)初始化，螞蟻的數目為任務數n。

(2)選擇任務j，獲得資源列表信息，計算任務j分配給所有資源的轉移概率選擇值最大的網格資源作為與任務j匹配的資源。

(3)把任務j分配給資源k執行，更新網格資源節點的信息素。回到步驟 (2)繼續執行，直到所有的任務都執行完成。

改進ACO算法包含3個關鍵部分有:網格計算資源信息初始化、網格資源的選擇機制以及信息素的更新。

(1)網格計算資源信息初始化

在改進 ACO算法中，初始化向量 Free(0...m－1)=a，其中a是0＜a＜1，m網格資源的數目，網格計算資源的信息素定義為

啟發式信息定義為

(2)網格資源的選擇機制

改進ACO算法的網格資源選擇機制采用傳統ACO算法的計算轉移概率機制。該機制對第j個任務，即第j只螞蟻，分別計算在所有網格資源的轉移概率表示在t時刻第j個任務選擇資源k的概率的定義為

式中:τj(t)——t時刻網格資源 j的信息素濃度;ηj——網格資源j的啟發因子，即ηj=τj(0);α——信息素的重要程度;β——網格資源啟發因子的重要程度。由于網格資源的分布性與動態性，大量實驗表明 α和 β值都取0.5較合適。

(3)信息素的更新

每當完成一個網格任務j，各網格資源信息素便會進行更新，其中更新準則為

式中:Tij——第 i個任務在資源 j上完成所需的時間，ρ——信息素的持久性 (0＜ρ＜1)，1－ρ表示信息素的揮發系數。

3 實驗結果分析

該部分研究使用的是Gridsim仿真平臺，Gridsim工具包的主要目的是基于網格計算的大規模分布式資源下的任務分配和資源調度技術。通過Gridsim我們可以仿真擁有數萬個資源和上千用戶的大規模網格計算環境的研究系統。在Gridsim平臺上分別對Random、Min-min、Max-min、ACO算法以及改進ACO算法及進行的相關實驗，其中，α和β值都取0.5，ρ取0.8。Free(0...m －1)=1，m 網格資源節點數目。本文針對以上算法做了三組實驗，其中前兩組實驗是分析任務完成時間，第三組實驗室分析網格資源的利用率，也叫負載均衡率。在以下實驗中，前提條件是所有任務都相互獨立以及任務都具有同等優先級。

實驗一為固定網格資源節點數為40，任務數目分別為:1000，1500，2000，2500，3000，3500，4000。實驗結果如圖2所示，從圖2中可以看出，隨著任務數的增多，完成任務數的時間增大;當任務數一定時，改進Ant算法所花的時間比Ant及其他三種算法所花的時間少很多。

圖2 網格節點數為40的實驗結果

實驗二的條件是任務數為2000，網格節點數分別為10，20，30，40。實驗結果如圖3所示，圖中可以看出，任務數為2000，當網格資源節點數目增多，完成任務所需的時間越來越少;當網格資源節點數目一定時，在任務完成時間上改進蟻群算法明顯優于其他算法。

圖3 任務數為2000的實驗結果

實驗三的實驗條件是網格任務數為2000，網格資源節點數為10。實驗主要研究算法的網格資源利用率，其中資源率的定義為

式中:T1，T2...Tm——m 個網格資源節點各自處理任務所花的時間，max(T1，T2...Tm)——所有網格資源中執行任務時間最長的節點。表1給出了5種算法的資源利用率的一個實驗結果。圖4為表1的柱狀圖，從實驗結果也可以看出，改進ACO明顯優于其他算法，與一般ACO算法相比，網格資源利用率大約提高了15%。綜上所述，在網格計算環境下，改進ACO算法 明顯優于Random、Min-min、Max-min及ACO網格調度算法，改進ACO算法使網格資源完成任務所花的時間減少以及網格計算資源的利用率有所提高。

表1 網格資源的利用率

圖4 網格資源的利用率柱狀

4 結束語

網格資源的調度技術是分布式計算中的關鍵技術，好的資源調度算法對提高整個網格系統的性能起關鍵作用。本文提出了一種改進ACO網格資源調度算法，更好地解決網格資源的分布性、動態性、可擴展性等問題，尤其對網格任務計算時間不確定的任務，調度效果更加明顯。改進ACO算法使網格負載均衡率更高，可以更優地利用網格資源。在接下來的研究中，可以把網格資源的經濟效益、社會效益等因素考慮進去，這樣可以加快網格資源的商業化的步伐。

［1］Dorigo M，Blum C.Ant colony optimization theory:A survey［J］.Theory Compute Sci，2005，344(2/3):243-278.

［2］Stefka Fidanova，Mariya Durchova.Ant algorithm for grid scheduling problem ［G］.LNCS 3743:Proceedings of the 5th International Conference on Large-Scale Scientific Computing，2006:405-412.

［3］Kousalya K，Balasubramanie P.An enhanced ant algorithm for grid scheduling problem ［J］.International Journal of Computer Sci-ence and Network Security，2008，8(4):269-270.

［4］ZHANG Jun，HU Xiaomin，LUO Xuyao.Ant colony optimization［M］.Beijing:Tsinghua University Press，2007:98-109(in Chinese).［張軍，胡曉敏，羅旭耀.蟻群優化［M］.北京:清華大學出版社，2007:98-109.］

［5］WANGXianglin，ZHANGShanqing.The grid:Core techno-logies［M］.Beijing:Tsinghua University Press，2006:168-172(in Chinese).［王相林，張善卿.網格計算核心技術［M］.清華大學出版社，2006:168-172.］

［6］CHEN Ruiqing，ZHOU Jian，YU Lie.Fast method to determine spatial relationship between point and polygon ［J］.Journal of Xi’an Jiaotong University，2007，41(1):59-63(in Chinese).［陳瑞卿，周健，虞烈.一種判斷點與多邊形關系的快速算法［J］.西安交通大學學報，2007，41(1):59-63.］

［7］Lorpunmanee S，Sap M，Abdullah A，et al.An ant colony optimization for dynamic job scheduling in grid environment［J］.International Journal of Computer and Information Science and Engineering，2007，1(4):207-214.

［8］Huang Han，Wu Chun-Guo，Hao Zhi-Feng.A pheromone-ratebased analysis on the convergence time of ACO algorithm ［J］.IEEE Transactions on Systems，Man，and Cybernetics-PART B:CYBERNETICS，2009，39(4):910-923.

［9］Yan H，Shen X，Li X，et al.An improved ant algorithm for job scheduling in grid computing［C］//Presented at Proceedings of the Fourth International Conference on Machine Learning and Cybernetics，2005:2957-2961.

［10］Li Y.A bio-inspired adaptive job scheduling mechanism on a computational grid［J］.International Journal of Computer Science and Network Security，2006，6(3):1-7.

［11］Faisal Nadeem M，Arash Ostadzadeh S，Stephan Wong，et al.Task scheduling strategies for dynamic reconfigurable processors in distributed systems［C］//Istanbul，Turkey:High Performance Computing and Simulation，2011:90-97.

［12］Pavani G，Waldman H.Grid resource management by means of ant colony optimization ［C］//San Jose，CA:3rd International Conference on Broadband Communications，Networks and Systems，2006:1-9.