0 引言

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

　　蟻群（Ant Colony，AC）算法是對自然界螞蟻尋徑方式的模擬而得出的一種仿生算法，其中最早的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)用，同時在任務(wù)調(diào)度方面也得到了較多的研究。文獻(xiàn)[11-13]分別對蟻群算法進(jìn)行了改進(jìn)，并將其應(yīng)用到敏捷衛(wèi)星的任務(wù)調(diào)度上，各有自己的優(yōu)點與缺點。

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

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

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

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

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

　　2.1 蟻群算法

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

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

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

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

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

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

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

　　信息素是螞蟻進(jìn)行通信的媒介，也是其他螞蟻進(jìn)行路徑選擇的重要依據(jù)，因此信息素的更新是AC算法關(guān)鍵問題。本文采用的信息素更新策略分為局部更新和全局更新兩方面。在局部更新過程中，如果一只螞蟻選擇了線路ij，其信息素強度可以根據(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ù)路徑的長度計算排序路徑的權(quán)重，長度越短，權(quán)重越大。以代表全局最優(yōu)路徑的權(quán)重，則第r短路徑的權(quán)重為max{0，-r}。當(dāng)完成一次迭代時，這些路徑的信息素值可以根據(jù)以下的全局更新規(guī)則進(jìn)行更新：

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

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

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

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

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

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

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

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

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

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

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

3 仿真實驗

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

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

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

　　在對比算法上選取標(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個，任務(wù)規(guī)模從0～100取值，步長為10。仿真結(jié)果如圖2所示。

　　從圖2可以看出，在虛擬終端數(shù)量不變的情況下，隨著任務(wù)數(shù)量的增加，各個算法的最優(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ù)量的增加，各個算法的最優(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算法和信息素更新該機的AC算法性能相當(dāng)，且都優(yōu)于標(biāo)準(zhǔn)AC算法。

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

4 結(jié)束語

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

　　參考文獻(xiàn)

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

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

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

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

　　[5] 董麗麗，黃賁，介軍.云計算中基于差分進(jìn)化算法的任務(wù)調(diào)度研究[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)工程理論與實踐，2012，32(11)：2533-2539.

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

　　[13] 嚴(yán)珍珍，陳英武，邢立寧.基于改進(jìn)蟻群算法設(shè)計的敏捷衛(wèi)星調(diào)度方法[J].系統(tǒng)工程理論與實踐，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.