基于改進(jìn)蟻群算法的網(wǎng)格資源調(diào)度研究

陳雨時(shí)，曲海成，2+，龔小川

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

0 引言

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

1 網(wǎng)格調(diào)度算法分析

網(wǎng)格調(diào)度技術(shù)主要涉及任務(wù)負(fù)載均衡算法的性能及優(yōu)化，主要分為兩大類:靜態(tài)調(diào)度算法和動(dòng)態(tài)調(diào)度算法。在靜態(tài)調(diào)度算法中，所有任務(wù)的信息、資源的信息及網(wǎng)絡(luò)帶寬等信息都是預(yù)先知道的，任務(wù)必須分配到適合的網(wǎng)格資源執(zhí)行。靜態(tài)負(fù)載均衡算法主要的缺點(diǎn)是:在任務(wù)的執(zhí)行過程中，所有任務(wù)和資源的信息都是固定不變的。相反，動(dòng)態(tài)調(diào)度算法是通過獲得任務(wù)和資源的實(shí)時(shí)狀態(tài)信息進(jìn)行任務(wù)的調(diào)度，這樣就能更準(zhǔn)確地進(jìn)行任務(wù)的分發(fā)。經(jīng)過對比實(shí)驗(yàn)可以看出，靜態(tài)負(fù)載均衡算法更易實(shí)施，但是動(dòng)態(tài)負(fù)載均衡算法有更好的效果。

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

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

MET(minimum execution time)是不考慮網(wǎng)格資源當(dāng)前的負(fù)載情況，把任務(wù)分發(fā)給執(zhí)行該任務(wù)最快的網(wǎng)格節(jié)點(diǎn)。MET算法企圖找到好的任務(wù)-網(wǎng)格資源匹配，但是由于它沒有考慮網(wǎng)格資源目前的任務(wù)量，這樣會(huì)導(dǎo)致各個(gè)網(wǎng)格資源節(jié)點(diǎn)負(fù)載的不平衡性，處理能力強(qiáng)的資源節(jié)點(diǎn)總是有很多任務(wù)，處理能力差的資源節(jié)點(diǎn)可能總是處于空閑狀態(tài)。

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

Min-Min算法是首先獲得最短執(zhí)行時(shí)間的任務(wù)j，以及得到完成任務(wù)j的MCT最少的網(wǎng)格資源節(jié)點(diǎn)m，然后把任務(wù)j分發(fā)給網(wǎng)格資源節(jié)點(diǎn)m執(zhí)行。Min-Min與MCT都利用了任務(wù)完成時(shí)間，但是由于Min-Min算法在每次選擇任務(wù)的時(shí)候選擇的是所有任務(wù)中最小完成時(shí)間的任務(wù)，這樣將會(huì)減少完成所有任務(wù)所需的時(shí)間。Min-Min算法在網(wǎng)格資源節(jié)點(diǎn)負(fù)載均衡方面要優(yōu)于MCT算法。

Max-Min算法與Min-Min算法很類似。同樣是選擇任務(wù)j完成時(shí)間最短的網(wǎng)格資源節(jié)點(diǎn)，但是與Min-Min算法不同之處是任務(wù)j選擇的是完成所需時(shí)間最大的任務(wù)。Max-Min算法更適用于復(fù)雜任務(wù)的調(diào)度問題。但是實(shí)驗(yàn)結(jié)果表明Max-Min算法不是在所有問題上都優(yōu)于Min-Min。

MaxStd(maximum standard deviation)在 MaxStd算法中，任務(wù)的期望執(zhí)行時(shí)間擁有最高的標(biāo)準(zhǔn)差優(yōu)先執(zhí)行。執(zhí)行的標(biāo)準(zhǔn)差低，在不同的資源節(jié)點(diǎn)上任務(wù)執(zhí)行時(shí)間變化很小的任務(wù)推后執(zhí)行。

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

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

2 改進(jìn)ACO算法設(shè)計(jì)

ACO算法的主要特點(diǎn)有以下幾個(gè)方面［9-10］:

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

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

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

(4)ACO算法反映的是群體智慧，不是個(gè)體智慧，所以算法自身具有很強(qiáng)的魯棒性，對系統(tǒng)初始化條件的要求不是太高，這使得ACO算法可以適用于復(fù)雜的網(wǎng)格計(jì)算環(huán)境。

通過對ACO算法以上幾個(gè)特點(diǎn)和網(wǎng)格任務(wù)調(diào)度本身特性的綜合分析可以得出，ACO算法適合于求解網(wǎng)格任務(wù)調(diào)度問題。

本文提出的改進(jìn)ACO算法主要是在算法中引進(jìn)了一個(gè)向量F=free(j)，1≤j≤m，其中m為網(wǎng)格資源數(shù)，free(j)表示資源j處于空閑狀態(tài)所需的時(shí)間。向量F引進(jìn)以后，根據(jù)F可以更好地了解資源的運(yùn)行情況，更容易掌握其任務(wù)負(fù)載量，這樣為選擇最適當(dāng)?shù)木W(wǎng)格資源提供了關(guān)鍵信息，網(wǎng)格任務(wù)的調(diào)度的效果更佳。

在改進(jìn)ACO算法中，網(wǎng)格計(jì)算系統(tǒng)把每個(gè)任務(wù)看出一只螞蟻。圖1為改進(jìn)ACO算法的流程圖。

圖1 改進(jìn)ACO算法的流程

改進(jìn)ACO的算法主要步驟［11-12］為:

(1)獲得網(wǎng)格資源的狀態(tài)信息及任務(wù)的相關(guān)信息，對F進(jìn)行初始化，網(wǎng)格資源信息素τj(t)與啟發(fā)式信息ηj(t)初始化，螞蟻的數(shù)目為任務(wù)數(shù)n。

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

(3)把任務(wù)j分配給資源k執(zhí)行，更新網(wǎng)格資源節(jié)點(diǎn)的信息素?；氐讲襟E (2)繼續(xù)執(zhí)行，直到所有的任務(wù)都執(zhí)行完成。

改進(jìn)ACO算法包含3個(gè)關(guān)鍵部分有:網(wǎng)格計(jì)算資源信息初始化、網(wǎng)格資源的選擇機(jī)制以及信息素的更新。

(1)網(wǎng)格計(jì)算資源信息初始化

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

啟發(fā)式信息定義為

(2)網(wǎng)格資源的選擇機(jī)制

改進(jìn)ACO算法的網(wǎng)格資源選擇機(jī)制采用傳統(tǒng)ACO算法的計(jì)算轉(zhuǎn)移概率機(jī)制。該機(jī)制對第j個(gè)任務(wù)，即第j只螞蟻，分別計(jì)算在所有網(wǎng)格資源的轉(zhuǎn)移概率表示在t時(shí)刻第j個(gè)任務(wù)選擇資源k的概率的定義為

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

(3)信息素的更新

每當(dāng)完成一個(gè)網(wǎng)格任務(wù)j，各網(wǎng)格資源信息素便會(huì)進(jìn)行更新，其中更新準(zhǔn)則為

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

3 實(shí)驗(yàn)結(jié)果分析

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

實(shí)驗(yàn)一為固定網(wǎng)格資源節(jié)點(diǎn)數(shù)為40，任務(wù)數(shù)目分別為:1000，1500，2000，2500，3000，3500，4000。實(shí)驗(yàn)結(jié)果如圖2所示，從圖2中可以看出，隨著任務(wù)數(shù)的增多，完成任務(wù)數(shù)的時(shí)間增大;當(dāng)任務(wù)數(shù)一定時(shí)，改進(jìn)Ant算法所花的時(shí)間比Ant及其他三種算法所花的時(shí)間少很多。

圖2 網(wǎng)格節(jié)點(diǎn)數(shù)為40的實(shí)驗(yàn)結(jié)果

實(shí)驗(yàn)二的條件是任務(wù)數(shù)為2000，網(wǎng)格節(jié)點(diǎn)數(shù)分別為10，20，30，40。實(shí)驗(yàn)結(jié)果如圖3所示，圖中可以看出，任務(wù)數(shù)為2000，當(dāng)網(wǎng)格資源節(jié)點(diǎn)數(shù)目增多，完成任務(wù)所需的時(shí)間越來越少;當(dāng)網(wǎng)格資源節(jié)點(diǎn)數(shù)目一定時(shí)，在任務(wù)完成時(shí)間上改進(jìn)蟻群算法明顯優(yōu)于其他算法。

圖3 任務(wù)數(shù)為2000的實(shí)驗(yàn)結(jié)果

實(shí)驗(yàn)三的實(shí)驗(yàn)條件是網(wǎng)格任務(wù)數(shù)為2000，網(wǎng)格資源節(jié)點(diǎn)數(shù)為10。實(shí)驗(yàn)主要研究算法的網(wǎng)格資源利用率，其中資源率的定義為

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

表1 網(wǎng)格資源的利用率

圖4 網(wǎng)格資源的利用率柱狀

4 結(jié)束語

網(wǎng)格資源的調(diào)度技術(shù)是分布式計(jì)算中的關(guān)鍵技術(shù)，好的資源調(diào)度算法對提高整個(gè)網(wǎng)格系統(tǒng)的性能起關(guān)鍵作用。本文提出了一種改進(jìn)ACO網(wǎng)格資源調(diào)度算法，更好地解決網(wǎng)格資源的分布性、動(dòng)態(tài)性、可擴(kuò)展性等問題，尤其對網(wǎng)格任務(wù)計(jì)算時(shí)間不確定的任務(wù)，調(diào)度效果更加明顯。改進(jìn)ACO算法使網(wǎng)格負(fù)載均衡率更高，可以更優(yōu)地利用網(wǎng)格資源。在接下來的研究中，可以把網(wǎng)格資源的經(jīng)濟(jì)效益、社會(huì)效益等因素考慮進(jìn)去，這樣可以加快網(wǎng)格資源的商業(yè)化的步伐。

［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).［張軍，胡曉敏，羅旭耀.蟻群優(yōu)化［M］.北京:清華大學(xué)出版社，2007:98-109.］

［5］WANGXianglin，ZHANGShanqing.The grid:Core techno-logies［M］.Beijing:Tsinghua University Press，2006:168-172(in Chinese).［王相林，張善卿.網(wǎng)格計(jì)算核心技術(shù)［M］.清華大學(xué)出版社，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).［陳瑞卿，周健，虞烈.一種判斷點(diǎn)與多邊形關(guān)系的快速算法［J］.西安交通大學(xué)學(xué)報(bào)，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.