0 引言

　　云計(jì)算是在分布式計(jì)算、網(wǎng)格計(jì)算,、對(duì)等計(jì)算之后產(chǎn)生的一種新型計(jì)算模型[1],，它真正體現(xiàn)了按需服務(wù)的理念。云計(jì)算通過整合分布式資源,，構(gòu)建應(yīng)對(duì)多種服務(wù)要求的計(jì)算平臺(tái),。而云中具有的資源和待處理的任務(wù)都是海量的，如何利用云中資源進(jìn)行高效的任務(wù)調(diào)度也就成為云計(jì)算系統(tǒng)可靠運(yùn)行的關(guān)鍵問題。近年來已有學(xué)者在云計(jì)算調(diào)度方面做了大量的研究,，如文獻(xiàn)[2-5]，這些算法都提高了云計(jì)算任務(wù)調(diào)度的效率,，取得了一定的研究成果,。

　　蟻群（Ant Colony，AC）算法是對(duì)自然界螞蟻尋徑方式的模擬而得出的一種仿生算法,，其中最早的AC算法是螞蟻系統(tǒng),，在AC算法的基礎(chǔ)上發(fā)展了許多改進(jìn)AC算法，如最大最小螞蟻系統(tǒng)(Max-min Ant System,，MMAS)[6],、排序螞蟻系統(tǒng)(Rank-based Version of Ant System，ASRank)[7],、多群螞蟻算法（Multi Colony Ant Algorithm）[8],、具有變異特征的蟻群算法（Ant Colony Algorithm with Mutation Features）[9]、基于信息素自適應(yīng)調(diào)整的改進(jìn)蟻群算法（Improved Ant Colony Algorithm based on Adaptive Adjusting Pheromone）[10]等,。AC算法以及其改進(jìn)算法在求解優(yōu)化問題上得到了很好的應(yīng)用,，同時(shí)在任務(wù)調(diào)度方面也得到了較多的研究。文獻(xiàn)[11-13]分別對(duì)蟻群算法進(jìn)行了改進(jìn),，并將其應(yīng)用到敏捷衛(wèi)星的任務(wù)調(diào)度上,，各有自己的優(yōu)點(diǎn)與缺點(diǎn)。

　　針對(duì)上述問題,，本文基于AC算法在優(yōu)化求解問題中的優(yōu)勢,，提出一種改進(jìn)AC算法的云計(jì)算任務(wù)調(diào)度方法。為防止優(yōu)化算法過快收斂,，改進(jìn)算法采用ACS的偽隨機(jī)比例規(guī)則進(jìn)行尋優(yōu),，同時(shí)將ASRank和MMAS中信息素更新方法進(jìn)行融合，以完成改進(jìn)AC算法的信息素更新,，有效改善了算法的尋優(yōu)能力,，提高云資源的調(diào)度效率。

1 云計(jì)算任務(wù)調(diào)度

　　與其他已有的網(wǎng)絡(luò)模式不同,，云計(jì)算具有其獨(dú)有的特征,。首先云計(jì)算將計(jì)算和存儲(chǔ)能力與單臺(tái)計(jì)算機(jī)的原始軟件分離，并在用戶終端和網(wǎng)絡(luò)服務(wù)中完成這些功能,，也就是模型將編程,、應(yīng)用過程和數(shù)據(jù)存儲(chǔ)在網(wǎng)絡(luò)中，而用戶終端僅負(fù)責(zé)用戶交流和獲取服務(wù),。文獻(xiàn)[14]總結(jié)云計(jì)算的特點(diǎn)為：(1)提供了安全穩(wěn)定的數(shù)據(jù)存儲(chǔ)中心,，用戶不用擔(dān)心數(shù)據(jù)丟失、軟件更新、病毒攻擊以及其他事項(xiàng),；(2)對(duì)用戶設(shè)備的基本要求低且方便使用,；(3)在不同的地方完成文件的處理，并且能在不同設(shè)備上完成文件的共享和應(yīng)用,。

　　從云計(jì)算的特征可以看出,，云計(jì)算任務(wù)調(diào)度的本質(zhì)是將有限的個(gè)任務(wù)分配給有限的可用資源上，在充分利用云資源基礎(chǔ)上使得總的處理時(shí)間最短,。由于在現(xiàn)實(shí)條件下,，完成一定的任務(wù)需要相應(yīng)的成本，因此云計(jì)算任務(wù)調(diào)度不僅要以處理時(shí)間為衡量標(biāo)準(zhǔn),，還要考慮成本因素,，即云計(jì)算任務(wù)調(diào)度是一個(gè)時(shí)間費(fèi)用優(yōu)化問題[4]。

2 改進(jìn)的蟻群算法

　　2.1 蟻群算法

　　AC算法是由意大利學(xué)者提出的仿生算法,，是根據(jù)真實(shí)世界中螞蟻尋找食物的行為演變而來,。生物學(xué)家經(jīng)過大量研究發(fā)現(xiàn)螞蟻會(huì)在經(jīng)過的道路上釋放一種特殊物質(zhì)，即信息素,。信息素可以使在一定范圍內(nèi)的螞蟻感受到其存在和強(qiáng)度,，進(jìn)而構(gòu)建它們的行為。蟻群傾向于選擇信息素強(qiáng)度大的路徑,，越多的螞蟻選擇相同的路徑,，該路徑的信息素強(qiáng)度會(huì)越大。通過信息素交換信息,，蟻群就可以完成積極地信息反饋并找到去往食物的最后路徑,。一般地，AC算法是一個(gè)隨機(jī)搜索過程,，由自適應(yīng)階段和合作階段組成,。在自適應(yīng)階段，每個(gè)候選方法都要根據(jù)累積信息自我調(diào)整,；在合作階段,，所有的候選方法要彼此交換信息，進(jìn)而尋找出最優(yōu)方法,。

　　2.2 蟻群算法的改進(jìn)

　　2.2.1 偽隨機(jī)比例規(guī)則尋優(yōu)

　　參考螞蟻系統(tǒng)設(shè)計(jì)思想,，采用偽隨機(jī)比例規(guī)則來實(shí)現(xiàn)尋優(yōu)策略，具體如下：

　　其中,，p0為一個(gè)常值且0≤p0≤1,，p為從[0，1]的均勻分布中產(chǎn)生的隨機(jī)值,，Ni代表節(jié)點(diǎn)i中的螞蟻在下一個(gè)時(shí)刻所能訪問的節(jié)點(diǎn)的集合,，同時(shí)Ni中的節(jié)點(diǎn)之前沒被訪問過且訪問之后不會(huì)違反相應(yīng)的約束條件,。在候選節(jié)點(diǎn)選擇之前隨機(jī)產(chǎn)生p的值。如果p≤p0,，就選擇使得取最大值的節(jié)點(diǎn)為下一時(shí)刻的節(jié)點(diǎn),；如果p>p0，螞蟻就會(huì)依概率P(i,，s）隨機(jī)選擇下一時(shí)刻的節(jié)點(diǎn),。其中P(i，s）的計(jì)算形式如下：

　　其中,，?子(i，s)表示第i個(gè)與第s個(gè)任務(wù)之間的信息素強(qiáng)度,，?濁(i,，s)為任務(wù)執(zhí)行間隔的影響，?資(i,，s）為任務(wù)優(yōu)先級(jí)影響,，而?琢、?茁,、?酌則為各個(gè)影響因素相應(yīng)的權(quán)重,。

　　2.2.2 信息素更新改進(jìn)

　　信息素是螞蟻進(jìn)行通信的媒介，也是其他螞蟻進(jìn)行路徑選擇的重要依據(jù),，因此信息素的更新是AC算法關(guān)鍵問題,。本文采用的信息素更新策略分為局部更新和全局更新兩方面。在局部更新過程中,，如果一只螞蟻選擇了線路ij,，其信息素強(qiáng)度可以根據(jù)下式進(jìn)行局部更新：

　　其中，t∈(0,，1)為調(diào)整參數(shù),，代表著信息素?fù)]發(fā)系數(shù)；Tnn是由最近探索法生成的初始可行方法所產(chǎn)生的訪問路徑的和,。

　　另一方面,，采用ASRank進(jìn)行信息素的全局更新。在一次迭代過程中,，所有路徑按照長度進(jìn)行升序排列,，即length1≤length2≤…≤lengthM，其中M為螞蟻的數(shù)量,。然后根據(jù)路徑的長度計(jì)算排序路徑的權(quán)重,，長度越短，權(quán)重越大,。以代表全局最優(yōu)路徑的權(quán)重,，則第r短路徑的權(quán)重為max{0,，-r}。當(dāng)完成一次迭代時(shí),，這些路徑的信息素值可以根據(jù)以下的全局更新規(guī)則進(jìn)行更新：

　　其中,，lengthR和lengthG分別代表第R優(yōu)和全局最優(yōu)路徑的長度。同時(shí)采用MMAS中的信息素更新策略來避免搜索過程中的停滯現(xiàn)象,，每個(gè)信息素的取值范圍為[min,，max]。

　　在基本的AC算法中,，只允許全局最優(yōu)路徑進(jìn)行信息素的更新,。而在ASRank中，不同的路徑會(huì)根據(jù)距離被賦予不同的權(quán)重,，這也就意味著,，距離越短，權(quán)重越大,，在下一次的迭代過程中被選擇的概率就越大,。然而過多的使用局部最優(yōu)解會(huì)導(dǎo)致信息素的停滯現(xiàn)象，在AC算法中,，信息素的值會(huì)伴隨著局部信息素的增多而減少,，進(jìn)而降低了選擇此路徑的可能性。MMAS算法對(duì)信息素的取值進(jìn)行了范圍限制,，保證了每條路徑的信息素值都不低于最小信息素值,，這樣避免了所有螞蟻選擇一條路徑的發(fā)生，也就避免了信息素的停滯現(xiàn)象,。

　　2.2.3 改進(jìn)蟻群算法流程

　　本文改進(jìn)AC算法的流程如圖1所示,，其過程可概括如下：

　　(1)H←0，其中H為迭代步數(shù)或搜素次數(shù),，初始化ij,，并將M個(gè)螞蟻放在N個(gè)頂點(diǎn)上；

　　(2)將螞蟻的出發(fā)點(diǎn)放在當(dāng)前解集中,，按照2.2.1節(jié)中的尋優(yōu)策略將螞蟻移至下一位置,，同時(shí)將下一時(shí)刻位置放入當(dāng)前解集；

　　(3)計(jì)算各螞蟻的路徑長度,，并記錄當(dāng)前最優(yōu)解,；

　　(4)按照2.2.2節(jié)中方法對(duì)各路徑的信息素強(qiáng)度進(jìn)行更新；

　　(5)對(duì)于各邊(i,，j),，置ij←0，H←H+1,；

　　(6)如果H小于預(yù)定的迭代次數(shù)且沒有退化,，轉(zhuǎn)至步驟(2),；

　　(7)輸出最優(yōu)解。

3 仿真實(shí)驗(yàn)

　　為了檢驗(yàn)本文改進(jìn)AC算法在云計(jì)算任務(wù)調(diào)度中的效果,，采用仿真實(shí)驗(yàn)對(duì)其進(jìn)行驗(yàn)證,。采用的仿真環(huán)境為2.80 GHz CPU，4 GB內(nèi)存,，500 GB硬盤,，Windows XP版本，采用Java語言編程,。

　　任務(wù)的處理在虛擬終端上進(jìn)行,，為仿真不同性能的虛擬終端，假設(shè)各個(gè)虛擬終端的計(jì)算能力是隨機(jī)產(chǎn)生的,，取值為[6,，10]，同時(shí)虛擬終端價(jià)格也是隨機(jī)產(chǎn)生且取值范圍為[50,，100]。迭代次數(shù)取為50,，同時(shí)在[100,，200]范圍內(nèi)隨機(jī)產(chǎn)生任務(wù)長度。為了保證仿真的有效性,，進(jìn)行100次試驗(yàn),，取平均值。

　　為全面驗(yàn)證算法在云計(jì)算任務(wù)調(diào)度上的優(yōu)勢,，分兩個(gè)方面進(jìn)行仿真實(shí)驗(yàn)：一是保持虛擬終端數(shù)量不變的情況下選擇不同任務(wù)數(shù)量,，以檢測虛擬終端不變下，隨著任務(wù)數(shù)量的增加,，改進(jìn)AC算法性能的好壞,；二是任務(wù)數(shù)量不變情況下選擇不同數(shù)量的虛擬終端，以檢測任務(wù)數(shù)量不變下,，隨著虛擬終端的增加,，改進(jìn)AC算法性能的好壞。

　　在對(duì)比算法上選取標(biāo)準(zhǔn)的AC算法,，只進(jìn)行尋優(yōu)改進(jìn)的AC算法,，只進(jìn)行信息素更新改進(jìn)的AC算法和本文的改進(jìn)AC算法。

　　3.1 任務(wù)數(shù)量變化的仿真

　　假設(shè)虛擬終端數(shù)量為固定數(shù)目8個(gè),，任務(wù)規(guī)模從0～100取值,，步長為10。仿真結(jié)果如圖2所示,。

　　從圖2可以看出,，在虛擬終端數(shù)量不變的情況下,，隨著任務(wù)數(shù)量的增加，各個(gè)算法的最優(yōu)解值增大,。而在不同任務(wù)規(guī)模下,，本文改進(jìn)AC算法的最優(yōu)解都要小于標(biāo)準(zhǔn)AC算法、尋優(yōu)改進(jìn)的AC算法,、信息素更新改進(jìn)的AC算法,。其中尋優(yōu)改進(jìn)的AC算法和信息素更新改進(jìn)的AC算法性能相當(dāng)，且都優(yōu)于標(biāo)準(zhǔn)AC算法,。

　　3.2 虛擬終端變化的仿真

　　假設(shè)任務(wù)規(guī)模固定為50,，虛擬終端數(shù)量從1～10取值。仿真結(jié)果如圖3所示,。

　　從圖3可以看出,，在任務(wù)數(shù)量不變的情況下，隨著虛擬終端數(shù)量的增加,，各個(gè)算法的最優(yōu)解值減小,。而在不同虛擬終端下，本文改進(jìn)AC算法的最優(yōu)解都要小于標(biāo)準(zhǔn)AC算法,、尋優(yōu)改進(jìn)的AC算法,、信息素更新改進(jìn)的AC算法。其中尋優(yōu)改進(jìn)的AC算法和信息素更新該機(jī)的AC算法性能相當(dāng),，且都優(yōu)于標(biāo)準(zhǔn)AC算法,。

　　本節(jié)從兩個(gè)不同方面的仿真實(shí)驗(yàn)驗(yàn)證了本文改進(jìn)算法在云計(jì)算任務(wù)調(diào)度上的有效性，說明了本文改進(jìn)AC算法是一種良好的調(diào)度方法,。

4 結(jié)束語

　　本文針對(duì)云計(jì)算任務(wù)調(diào)度問題,，提出一種基于改進(jìn)蟻群算法的任務(wù)調(diào)度方法。改進(jìn)AC算法采用AS中的偽隨機(jī)比例規(guī)則設(shè)計(jì)尋優(yōu)策略,，結(jié)合MMAC和ASRank設(shè)計(jì)信息素更新策略,，有效提高了算法的尋優(yōu)能力，在不同仿真場景下的實(shí)驗(yàn)結(jié)果驗(yàn)證了算法的有效性,。

　　參考文獻(xiàn)

　　[1] 林闖,，蘇文博，孟坤,，等.云計(jì)算安全：架構(gòu),、機(jī)制與模型評(píng)價(jià)[J].計(jì)算機(jī)學(xué)報(bào)，2013,，36(9)：1765-1784.

　　[2] 楊鏡,，吳磊，武德安,，等.云平臺(tái)下動(dòng)態(tài)任務(wù)調(diào)度人工免疫算法[J].計(jì)算機(jī)應(yīng)用,，2014,，34(2)：351-356.

　　[3] 陳春玲，張瑞霞,，曹萌萌.云計(jì)算任務(wù)調(diào)度算法的改進(jìn)[J].無限互聯(lián)技術(shù),，2014(1)：9-10，20.

　　[4] 李依桐,，林燕.基于混合粒子群算法的云計(jì)算任務(wù)調(diào)度研究[J].計(jì)算技術(shù)與自動(dòng)化,，2014，33(1)：73-77.

　　[5] 董麗麗,，黃賁,，介軍.云計(jì)算中基于差分進(jìn)化算法的任務(wù)調(diào)度研究[J].計(jì)算機(jī)工程與應(yīng)用，2014,，50(5)：90-95.

　　[6] STUTZLE T,，HOOS H.MAX-MIN ant system[J].Future Generation Computer Systems，2000,，16(8)：889-914.

　　[7] BULLNHEIMER B,，HARTL R F，STRAUSS C.A new rank based version of the ant system: A computational study[J]. Central European Journal for Operation Research and Economics,，1999,，7(1)：25-28.

　　[8] MIDDENDORF M，REISCHLE F,，SCHMECK H.Multi colonyant algorithm[J].Journal of Heuristics，2002,，8(3)：305-320.

　　[9] WU Q H,，ZHANG J H，XU X H.An ant colony algorithm with mutation features[J].Journal of computer research and development,，1999,，36(10)：1240-1245.

　　[10] QIN G L，YANG J B.An improved ant colony algorithm based on adaptively adjusting pheromone[J].Information and Control,，2002,，31(3)：198-201.

　　[11] 郭浩，邱滌珊,，伍國華,，等.基于改進(jìn)蟻群算法的敏捷成像衛(wèi)星任務(wù)調(diào)度方法[J].系統(tǒng)工程理論與實(shí)踐，2012,，32(11)：2533-2539.

　　[12] 邱滌珊,，郭浩，賀川,，等.敏捷成像衛(wèi)星多星密集任務(wù)調(diào)度方法[J].航空學(xué)報(bào),，2013,，34(4)：882-889.

　　[13] 嚴(yán)珍珍，陳英武,，邢立寧.基于改進(jìn)蟻群算法設(shè)計(jì)的敏捷衛(wèi)星調(diào)度方法[J].系統(tǒng)工程理論與實(shí)踐,，2014，34(3)：793-801.

　　[14] LI C L,，DENG ZH H.On the value of cloud computing[J].Library and Information,，2009(4)：42-46.