0 引言

　　云計(jì)算是在分布式計(jì)算、網(wǎng)格計(jì)算、對(duì)等計(jì)算之后產(chǎn)生的一種新型計(jì)算模型[1]，它真正體現(xiàn)了按需服務(wù)的理念。云計(jì)算通過(guò)整合分布式資源，構(gòu)建應(yīng)對(duì)多種服務(wù)要求的計(jì)算平臺(tái)。而云中具有的資源和待處理的任務(wù)都是海量的，如何利用云中資源進(jìn)行高效的任務(wù)調(diào)度也就成為云計(jì)算系統(tǒng)可靠運(yùn)行的關(guān)鍵問(wèn)題。近年來(lái)已有學(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)化問(wèn)題上得到了很好的應(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ì)上述問(wèn)題，本文基于AC算法在優(yōu)化求解問(wèn)題中的優(yōu)勢(shì)，提出一種改進(jìn)AC算法的云計(jì)算任務(wù)調(diào)度方法。為防止優(yōu)化算法過(guò)快收斂，改進(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)用過(guò)程和數(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)化問(wèn)題[4]。

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

　　2.1 蟻群算法

　　AC算法是由意大利學(xué)者提出的仿生算法，是根據(jù)真實(shí)世界中螞蟻尋找食物的行為演變而來(lái)。生物學(xué)家經(jīng)過(guò)大量研究發(fā)現(xiàn)螞蟻會(huì)在經(jīng)過(guò)的道路上釋放一種特殊物質(zhì)，即信息素。信息素可以使在一定范圍內(nèi)的螞蟻感受到其存在和強(qiáng)度，進(jìn)而構(gòu)建它們的行為。蟻群傾向于選擇信息素強(qiáng)度大的路徑，越多的螞蟻選擇相同的路徑，該路徑的信息素強(qiáng)度會(huì)越大。通過(guò)信息素交換信息，蟻群就可以完成積極地信息反饋并找到去往食物的最后路徑。一般地，AC算法是一個(gè)隨機(jī)搜索過(guò)程，由自適應(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ī)則來(lái)實(shí)現(xiàn)尋優(yōu)策略，具體如下：

　　其中，p0為一個(gè)常值且0≤p0≤1，p為從[0，1]的均勻分布中產(chǎn)生的隨機(jī)值，Ni代表節(jié)點(diǎn)i中的螞蟻在下一個(gè)時(shí)刻所能訪問(wèn)的節(jié)點(diǎn)的集合，同時(shí)Ni中的節(jié)點(diǎn)之前沒(méi)被訪問(wèn)過(guò)且訪問(wè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)鍵問(wèn)題。本文采用的信息素更新策略分為局部更新和全局更新兩方面。在局部更新過(guò)程中，如果一只螞蟻選擇了線路ij，其信息素強(qiáng)度可以根據(jù)下式進(jìn)行局部更新：

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

　　另一方面，采用ASRank進(jìn)行信息素的全局更新。在一次迭代過(guò)程中，所有路徑按照長(zhǎng)度進(jìn)行升序排列，即length1≤length2≤…≤lengthM，其中M為螞蟻的數(shù)量。然后根據(jù)路徑的長(zhǎng)度計(jì)算排序路徑的權(quán)重，長(zhǎng)度越短，權(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)路徑的長(zhǎng)度。同時(shí)采用MMAS中的信息素更新策略來(lái)避免搜索過(guò)程中的停滯現(xiàn)象，每個(gè)信息素的取值范圍為[min，max]。

　　在基本的AC算法中，只允許全局最優(yōu)路徑進(jìn)行信息素的更新。而在ASRank中，不同的路徑會(huì)根據(jù)距離被賦予不同的權(quán)重，這也就意味著，距離越短，權(quán)重越大，在下一次的迭代過(guò)程中被選擇的概率就越大。然而過(guò)多的使用局部最優(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所示，其過(guò)程可概括如下：

　　(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ì)算各螞蟻的路徑長(zhǎng)度，并記錄當(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ù)且沒(méi)有退化，轉(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硬盤(pán)，Windows XP版本，采用Java語(yǔ)言編程。

　　任務(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ù)長(zhǎng)度。為了保證仿真的有效性，進(jìn)行100次試驗(yàn)，取平均值。

　　為全面驗(yàn)證算法在云計(jì)算任務(wù)調(diào)度上的優(yōu)勢(shì)，分兩個(gè)方面進(jìn)行仿真實(shí)驗(yàn)：一是保持虛擬終端數(shù)量不變的情況下選擇不同任務(wù)數(shù)量，以檢測(cè)虛擬終端不變下，隨著任務(wù)數(shù)量的增加，改進(jìn)AC算法性能的好壞；二是任務(wù)數(shù)量不變情況下選擇不同數(shù)量的虛擬終端，以檢測(cè)任務(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取值，步長(zhǎng)為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)度上的有效性，說(shuō)明了本文改進(jìn)AC算法是一種良好的調(diào)度方法。

4 結(jié)束語(yǔ)

　　本文針對(duì)云計(jì)算任務(wù)調(diào)度問(wèn)題，提出一種基于改進(jìn)蟻群算法的任務(wù)調(diào)度方法。改進(jìn)AC算法采用AS中的偽隨機(jī)比例規(guī)則設(shè)計(jì)尋優(yōu)策略，結(jié)合MMAC和ASRank設(shè)計(jì)信息素更新策略，有效提高了算法的尋優(yōu)能力，在不同仿真場(chǎng)景下的實(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].無(wú)限互聯(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] 郭浩，邱滌珊，伍國(guó)華，等.基于改進(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.