基于蟻群優化算法的云任務分配策略研究

姜力爭 裴云曼 趙建濤

(華北電力大學控制與計算機工程學院 北京 102206)

0 引 言

云計算[1-2]是一種新型的計算模型，它通過虛擬化技術，將分布于不同網絡節點的資源聯系起來形成資源池，為用戶所需資源進行統一管理和統一分配。而云計算中的任務分配算法的優劣對用戶的滿意程度與平臺的質量效率產生了直接的影響，因此任務分配算法一直是云計算領域的重點研究方向。近年來，許多專家學者對云計算中的任務分配問題進行了深入研究。任務分配算法大致可以分為三類[3]。第一類為基于經典策略的任務分配算法，如輪詢算法、Min-Min算法和Max-Min算法等。第二類為基于單一群智能優化算法的任務分配算法，如蟻群算法、遺傳算法、蛙跳算法等。第三類為基于混合群智能優化算法的任務分配算法，如遺傳-蟻群算法[4]、蛙跳-蟻群算法[5]等。

蟻群算法[6](Ant colony optimization,ACO)是一種仿生優化算法，其靈感是Marco Dorigo發現螞蟻在覓食過程中群體所表現出來的超高的團隊合作能力，能夠很好地應用于任務-資源分配的N-P問題。文獻[6]提出劣化因子蟻群算法，劣化因子的合理選擇不僅可以平衡負載還能提高資源的利用率。文獻[7]提出的改進信息素揮發程度的蟻群優化算法，提高局部和全局的搜索性能。文獻[2]提出的基于資源狀態的蟻群算法，在資源消耗和任務等待時間上有較大優勢。上述研究從不同角度上都改進了云計算任務分配問題。但是云計算的任務分配問題是一個需要以多指標最優為最終目標，既要考慮云服務的穩定性和用戶的滿意程度，又要考慮資源的使用效率和運營成本。現有的研究多以單一指標為最終的研究目標，缺乏對任務分配問題的全面考慮。

針對上述的問題，本文通過對任務分配模型的分析，提出服務穩定性好、資源利用率高、任務完成時間短的任務分配模型。基于該模型，改變資源執行任務的可見度，自適應方式調節信息量，根據虛擬機狀態更新信息素的蟻群優化算法。與輪詢算法、Min-Min算法、標準蟻群算法以及文獻[11]提出的優化蟻群算法(OACO)進行仿真實驗，實驗結果表明該蟻群優化算法在任務完成時間、資源利用率以及服務穩定性上具有顯著優勢。

1 任務分配模型分析

云環境下的任務分配模型[1]可以分為三層：應用層、調度層和物理層。在云環境中，應用層存在多個用戶，每個用戶都可以發送請求來運行多個應用，每個應用又對應著多個任務。調度層會根據不同的任務分配不同的虛擬機。任務分配的過程實質上是將任務按照某一分配原則分配到虛擬機節點上執行的過程。任務分配過程，如圖1所示。

圖1 任務分配過程

由此，可將任務在虛擬機上的執行時間定義為Max(costi)，總資源消耗定義為∑exeij。

2 基本蟻群算法

蟻群算法具有并行、自組織、魯棒性強、正反饋的特點[8]。其智能性主要體現在以下三個方面：

(1) 螞蟻之間可以利用信息素進行“交流”。

(2) 螞蟻在搜索路徑的過程中，已經被螞蟻搜索過的路徑將不會再被選擇。

(3) 螞蟻之間有很強的團隊合作能力，單憑一只螞蟻，很難找到食物。

2.1 定義變量

為了方便描述，定義以下變量：

antNum為螞蟻數量；

taskNum為任務數量；

vmNum為虛擬機數量；

iterationTimes為迭代次數；

optimalPath為最優路徑；

pheromone[taskNum][vmNum]為信息素矩陣；

α為信息素因子；

β為可見度因子；

ρ為信息素揮發因子。

2.2 算法步驟描述

Step1初始化信息素矩陣、最佳長度以及antNum只螞蟻。

pheromone[i][j]=0.1f,ifi

optimalPath=MAX_VALUE

Ants[i].init(exe,α,β), ifi

Step2如果循環次數小于迭代次數iterationTimes，則執行第三步到第五步，否則輸出結果，算法結束。

(1)

Step4更新禁忌表和可搜索列表。

Step5更新信息素濃度。

(2)

(3)

基本蟻群算法的任務分配流程如圖2所示。

圖2 基本蟻群算法的任務分配流程

3 蟻群優化算法

基本蟻群算法[8]在處理較小規模的任務分配問題時能夠快速找到最優解，但隨著大數據時代的帶來，數據呈現出井噴式爆發增長的趨勢，數據的高性能計算是云計算任務分配的核心問題。基本蟻群算法隨著數據規模的擴大計算性能嚴重下降，為此，本文針對基本蟻群算法的缺點進行了優化改進。

相較于基本蟻群算法，優化算法主要體現在以下幾個方面。

(1) 根據虛擬機狀態對任務ti選擇虛擬機rj執行的啟發式因子ηij(t)進行優化。將虛擬機的消耗考慮其中，減少任務的等待時間。

(4)

式中：costj(t)表示t時刻虛擬機vmj的狀態情況。

(2) 在任務選擇虛擬機vj執行后，更新虛擬機的消耗狀態costj。

costj=costj+exeij

(5)

(3) 更新信息素濃度時，采用自適應信息量的更新策略改變τij(new)的值，動態調整信息量強度，提高全局的搜索能力，避免陷入局部最優解。

(6)

(7)

式中：Q為常量，代表每只螞蟻釋放信息素的強弱程度。

4 實驗設計與分析

本實驗采用CloudSim-3.0.3作為實驗環境，步驟主要包括：產生實驗數據，為保證實驗的準確性，每種條件的數據為10組，取平均值作為最終結果。將不同條件的數據由不同的算法執行求取最優解，使用CloudSim進行仿真實驗，得出的實驗結果做可視化圖形處理。

由文獻[9]可知，任務執行時間可以認為只與任務的指令長度(MI)和虛擬機的執行速度(MIPS)有關，一個任務所需的執行時間等于任務指令長度除以運行該任務的虛擬機的執行速度。創建指定任務數量以及任務長度等信息的云任務，提交給任務代理。創建指定CPU數量以及執行速度等信息的虛擬機提交給任務代理。任務代理根據QoS要求提供任務與資源的分配策略。模擬為虛擬機分配處理核所用的策略為空間共享。

以隨機數的方式設置任務的MI范圍為500 000到3 000 000。以隨機數的方式設置虛擬機的MIPS范圍為500到2 000。設置任務數分別為20、40、60、80、100。設置虛擬機數為5。設置螞蟻數為100，迭代次數為50。

根據文獻[10]研究，將蟻群算法的參數設置為α=1.0，β=5.0，ρ=0.5，Q=5.0。

綜上所述，云計算任務分配仿真實驗參數設置表見表1。

表1 云計算任務分配仿真實驗參數設置表

如圖3所示，所提出的基于資源狀態的自適應蟻群優化算法(MACO)調度任務完成時間最短，相比于輪詢算法(RR)與基本蟻群算法(BACO)具有顯著優勢，并且隨著任務數量的增加，優勢會愈加明顯。Min-Min算法是將最小的任務映射到執行最快的虛擬機上，結果顯示Min-Min算法的效果較好，僅稍次于MACO算法。本文提出的MACO算法相比于RR算法提高了35.55%±8.13%，相比于BACO算法提高了20.5%±7.13%，相比于Min-Min算法提高了8.21%±5.07%。

圖3 任務完成時間對比圖

文獻[11]提出的優化蟻群算法(OACO)，其實驗參數與實驗結果與本文較為相似，因此采用文獻[11]中的實驗結果數據進行對比實驗。為與文獻[11]中的數據保持一致性，另外生成一組任務數為25、50、75、100的實驗數據。為排除因實驗數據不同而造成的差異，均以相對RR算法的比值進行比較。如圖4所示，OACO算法相對RR算法的時間比例隨任務數的變化起伏較大，算法的穩定性比本文提出MACO差。在任務數為25時，OACO算法的完成時間優于本文的MACO算法，但隨著任務數的增加，本文提出的算法MACO提高比例逐漸降低并顯著優于OACO算法。無疑在大數據的時代，本文提出的MACO算法穩定性更高。OACO算法相比于RR算法提高了43.88%±6.85%，而本文提出的MACO算法相比于RR算法提高了44.29%±3.62%，以標準差來衡量算法的穩定性，則本文算法的算法穩定性是OACO算法的1.89倍。

圖4 相對RR算法完成時間對比圖

平臺的占用時間，是一批任務全部完成時占用虛擬機的全部時間和，可以反映任務對資源的消耗情況。如圖5所示，完成同一批任務，本文提出的MACO算法占用平臺時間最少，平臺資源的利用率最高。本文提出的MACO算法相比于RR算法提高了9.11%±2.78%，相比于Min-Min算法提高了1.81%±1.59%。

圖5 平臺占用時間對比圖

5 結 語

本文提出了一種基于資源狀態的自適應蟻群優化算法，該算法利用虛擬機的狀態來修正啟發式因子和釋放信息素濃度，并以自適應的方式進行信息量的更新，避免早熟和局部收斂，提高全局搜索能力。實驗結果表明，該算法在任務完成時間、資源利用率和服務穩定性方面均有良好表現。