0 引言

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

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

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

1 云計算任務調度

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

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

2 改進的蟻群算法

　　2.1 蟻群算法

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

　　2.2 蟻群算法的改進

　　2.2.1 偽隨機比例規則尋優

　　參考螞蟻系統設計思想，采用偽隨機比例規則來實現尋優策略，具體如下：

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

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

　　2.2.2 信息素更新改進

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

　　其中，t∈(0，1)為調整參數，代表著信息素揮發系數；Tnn是由最近探索法生成的初始可行方法所產生的訪問路徑的和。

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

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

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

　　2.2.3 改進蟻群算法流程

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

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

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

　　(3)計算各螞蟻的路徑長度，并記錄當前最優解；

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

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

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

　　(7)輸出最優解。

3 仿真實驗

　　為了檢驗本文改進AC算法在云計算任務調度中的效果，采用仿真實驗對其進行驗證。采用的仿真環境為2.80 GHz CPU，4 GB內存，500 GB硬盤，Windows XP版本，采用Java語言編程。

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

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

　　在對比算法上選取標準的AC算法，只進行尋優改進的AC算法，只進行信息素更新改進的AC算法和本文的改進AC算法。

　　3.1 任務數量變化的仿真

　　假設虛擬終端數量為固定數目8個，任務規模從0～100取值，步長為10。仿真結果如圖2所示。

　　從圖2可以看出，在虛擬終端數量不變的情況下，隨著任務數量的增加，各個算法的最優解值增大。而在不同任務規模下，本文改進AC算法的最優解都要小于標準AC算法、尋優改進的AC算法、信息素更新改進的AC算法。其中尋優改進的AC算法和信息素更新改進的AC算法性能相當，且都優于標準AC算法。

　　3.2 虛擬終端變化的仿真

　　假設任務規模固定為50，虛擬終端數量從1～10取值。仿真結果如圖3所示。

　　從圖3可以看出，在任務數量不變的情況下，隨著虛擬終端數量的增加，各個算法的最優解值減小。而在不同虛擬終端下，本文改進AC算法的最優解都要小于標準AC算法、尋優改進的AC算法、信息素更新改進的AC算法。其中尋優改進的AC算法和信息素更新該機的AC算法性能相當，且都優于標準AC算法。

　　本節從兩個不同方面的仿真實驗驗證了本文改進算法在云計算任務調度上的有效性，說明了本文改進AC算法是一種良好的調度方法。

4 結束語

　　本文針對云計算任務調度問題，提出一種基于改進蟻群算法的任務調度方法。改進AC算法采用AS中的偽隨機比例規則設計尋優策略，結合MMAC和ASRank設計信息素更新策略，有效提高了算法的尋優能力，在不同仿真場景下的實驗結果驗證了算法的有效性。

　　參考文獻

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

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

　　[3] 陳春玲，張瑞霞，曹萌萌.云計算任務調度算法的改進[J].無限互聯技術，2014(1)：9-10，20.

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

　　[5] 董麗麗，黃賁，介軍.云計算中基于差分進化算法的任務調度研究[J].計算機工程與應用，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].系統工程理論與實踐，2012，32(11)：2533-2539.

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

　　[13] 嚴珍珍，陳英武，邢立寧.基于改進蟻群算法設計的敏捷衛星調度方法[J].系統工程理論與實踐，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.