基于改進蟻群優化算法的云計算任務調度研究

于淑香，周洪斌

（沙洲職業工學院 電子信息工程系，江蘇 張家港 215600）

引言

云計算是網格計算、并行計算和分布式計算等多種技術的融合[1]，其本質是把各地的計算機資源及相關的終端設備等組織在網絡“云”中，為廣大用戶提供軟件、存儲、計算和大數據的訪問使用等服務。云計算系統是采用多種技術把“云”中各種資源進行重組形成一個巨大的資源庫，方便隨用隨取，解決了當前大數據時代，激增的數據量和計算機有限的硬件水平及處理能力的矛盾。云計算的使用類似居民用水電一樣“按需使用，按量付費”，具有較高靈活性和可靠性。高效的任務調度和合理資源分配是提高云計算系統性能的重點和難點，這些技術的提高能使云計算系統更好地滿足客戶需求，降低能源消耗，提高企業效益。

資源調度模型的發展過程分為兩個階段，啟發式算法和傳統的資源調度算法。啟發式算法主要根據非線性理論和人工智能理論，模擬生物的自然行為尋找一些資源調度問題的最優解[2]。而傳統的資源調度算法有先來先服務，貪心法、輪轉調度，最大最小等算法。很多專家和學者研究實驗表明，在云計算任務調度中，使用啟發式算法明顯優于傳統的資源調度算法，具有不可比擬的優越性。

1 云計算任務調度模型

1.1 云計算的編程模型

云計算系統包含很多復雜和結構迥異的資源，最優的任務調度方案能保證快速完成用戶任務并且提高系統的效率和利用率。當前的云計算系統大部分選用Map/Reduce思想的編程模型[3]，該模型特別適合應用于云計算系統中大規模數據集的產生和處理。任務調度模型如圖1所示。

圖1任務調度模型

云計算系統中有巨大的用戶量和任務量，在用戶提交任務后，任務調度系統首先要進行任務分布式化，即切分任務，把用戶提交的任務集切分成多個子任務；子任務提交給調度中心后，根據映射法則的算法，把每個子任務調度分配給虛擬資源節點。

1.2 任務調度的相關定義

按照相關的算法將N個用戶任務分配到M個虛擬資源節點上（M＜N），云計算環境下任務的數學模型表示如下：

⑴T={T1，T2，……Tn}表示N個待執行獨立任務的集合。

⑵V={V1，V2，……Vm}表示M個虛擬機資源節點。

⑶MIPS={MIPSl，MIPS2，……，MIPSm}表示M個虛擬機的計算能力，即計算速度，MIPSi表示虛擬機Vi單位時間內處理的指令數，以百萬/秒計。

⑷任務和虛擬機節點之間的映射關系如矩陣M表示，若任務Ti被分配到虛擬機Vj上執行調度，則矩陣中的元素Mij=1，否則Mij=0。

⑸任務的期望執行時間，即第j個子任務在第i個虛擬機上執行時間。

由上述矩陣，可以計算出每個虛擬機Vi執行子任務的時間，如公式（1）所示。

公式中n表示虛擬機Vi執行的子任務數量，Time(i,j)表示虛擬機Vi上的第j個子任務執行時間。

2 改進蟻群優化算法

蟻群算法是學者Mr.Dorigo等提出的，該算法受自然界中螞蟻的覓食行為過程啟發而提出。該算法具有啟發式、正反饋和分布式的搜索特點，在許多NP類問題的優化求解過程中被普遍應用，如模式識別、旅行商問題、車輛調度、多重背包等。隨著算法應用演變發展，出現了更接近現實的模擬螞蟻覓食過程的算法，即蟻群優化算法。

2.1 蟻群優化算法原理

設螞蟻數量是n，在尋找食物經過的路徑上，螞蟻會留下信息素，而后來的螞蟻會依據在此路徑上走過的螞蟻留下信息素濃度去選擇合適的路徑，即每只螞蟻會根據一定的概率轉移到下一個虛擬機資源節點，在t時刻，第k只螞蟻從虛擬機Vi訪問虛擬機Vj的概率計算如公式（2）所示。

其中:τij表示路徑(i,j)上的信息素濃度，α表示螞蟻對信息素的敏感度；β表示蟻群對信息素的敏感度，ηij表示節點j對節點i上螞蟻的吸引水平，即啟發因子，allowedk表示還沒有訪問的節點。

在不斷尋找食物的過程中,螞蟻在路徑上留下的初始信息素會陸續散發掉,同時又會在路徑上繼續釋放出新的信息素，所以為了有利于發現最優的解，在蟻群優化算法中，要更新路徑上的信息素，全局和局部的信息素更新如公式（3）所示。

其中:ρ ∈(0,1]表示信息素揮發系數，Δτij(t)表示所有m只螞蟻釋放在路徑上的信息素總量(t)表示在路徑(i,j)上第k只螞蟻釋放信息素的增量，計算信息素增量如公式（4）所示。

其中，Q表示一次搜索結束后路徑上存留信息素的總量；Lk表示螞蟻k走過路徑總長度。

2.2 蟻群優化算法的改進

2.2.1 信息素初始化

在初始時刻，利用蟻群優化算法原理將螞蟻（任務）隨機的放到云計算系統中的任意一個虛擬機上。此虛擬機處理器的數量為v_num。各處理器的處理能力v_pc，通信帶寬能力v_bw等參數。利用這些參數指標，云計算系統可以初始化每個虛擬機的信息素值，計算如公式(5)所示。

其中虛擬機i的指標如下：τi()0是信息素初始值，v_numi是處理器的數量，v_pci是處理器的處理能力（即MIPS），v_bwi是通信帶寬[4]。

2.2.2 選擇虛擬機概率

在改進算法中，螞蟻（任務）從虛擬機Vi訪問虛擬機Vj的概率計算如公式（6）所示。

式中，q0∈(0，1)是給定的參數，q為(0，1)范圍內的隨機數。當 q＜q0時，j取 MAX{allowedk}中的k，能夠得到使邊(i,k)距離i最短、信息素最高的節點作為下一節點[5]。

當q＞q0時，啟發信息函數ηij表示任務i選擇虛擬機j的期望值。在此取ηij=propertyj*LLj,其中propertyj是固定值等于τi()0的值,其計算如公式（5）所示，LLj是虛擬機負載能力的衡量值，其值高低代表虛擬機當前狀態下處理能力的高低，當該值比較高時，被選擇的概率就更大。LLj的計算如公式（7）所示。

其中AVTime表示截止到前一次迭代結束時，在最優路徑中的每個虛擬機Vi的平均執行時間。

2.2.3 信息素更新

在螞蟻選中路徑(i,j)后，立即按公式（8）局部更新路徑(i,j)上的信息素。

式中，ρ是信息素的揮發因子，且ρ∈(0，1]，信息素的殘留濃度用1-ρ表示，ρ值越大，散發越快，則殘余濃度越低，所以曾探尋過的路徑對選擇當前路徑的影響相對較小。信息素的增量用Δτij()t表示，第k只螞蟻在本次迭代中經過路徑的長度用Lk表示[6]。

在螞蟻確定選擇某一路徑后應減少該條路徑上的信息素，同時增加其余路徑邊被選擇的概率，當所有螞蟻都走完一次循環之后，根據式（9）全局更新信息素，進而使最佳路徑的搜索概率更大[5]。

公式中，Lgbest是此刻得到的最優路徑。

2.3 算法描述

⑴算法參數初始化，包括云計算虛擬機節點數，任務數，信息素和迭代次數等各參數。

⑵將X只螞蟻隨機放置在虛擬機節點上。

⑶計算出螞蟻個體轉移到下一虛擬機節點的概率，并根據計算結果進行移動。

⑷局部更新螞蟻走過路徑上的信息素值，并修改相應的禁忌表。

⑸重復步驟2)～4)，直到蟻群中的每個螞蟻個體找到一條可行的路徑截止。

⑹全局更新所有路徑的信息素。

⑺增加迭代次數，如其值已達預設的最大迭代次數，則停止搜索，獲得云計算任務調度的最優解。

3 仿真實驗及結果分析

3.1 實驗環境

為了驗證改進蟻群算法在云計算系統中任務調度分配優化效果，本文選用澳大利亞墨爾本大學和Gridbus項目共同提出的云仿真軟件CloudSim平臺進行測試實驗[7]，實驗的硬件環境為2.66GHz的CPU，8G的內存，500G硬盤作為硬件環境，Windows10操作系統和JDK8.0的基礎環境及Antl.9.7的編譯工具。在CloudSim平臺中對比測試本文改進蟻群優化任務調度算法、標準蟻群算法和MAX-MIN算法在任務調度分配執行方面的效率。通過初始化CloudSim，創建數據中心及DataCenterBroker,創建虛擬機、云任務集等一系列的操作后開始仿真實驗。

3.2 結果分析

仿真實驗主要測試在任務數量增加的情況下，本文算法的任務平均完成時間，并與其他比較算法進行對比，公平起見所有測試的算法都進行10次實驗，統計平均，橫坐標為申請任務數量，縱坐標為各算法分別完成任務處理所需時間。在實驗軟硬件環境相同，資源節點相同的情況下，幾種算法的任務完成時間對比如圖2所示。

圖2各算法任務執行時間對比

在文件任務量不大情況下，各算法完成任務分配執行所用時間差別不大，但從整體上來看，任務量相同時本文改進蟻群優化算法執行任務用時比較短。而隨著任務數量的增加，本文算法完成任務時間增幅度不大，相反另外兩種比較算法的執行時間增加幅度非常大。同時在實驗中發現本文算法的迭代次數少于其他比較算法，這是因為本文算法成功地避免了傳統蟻群優化算法容易陷入局部最優解的缺點，這樣可以使用戶提交的任務在相應的資源節點最快分配執行完成，提高云計算系統的工作效率，取得了比較理想的資源任務調度效果。

4 結語

本文提出了基于改進蟻群優化算法的云計算任務調度算法。首先介紹了云計算系統的編程模型和任務調度相關定義，然后針對傳統蟻群優化算法進行改進，并在CloudSim平臺測試該算法在云計算系統任務調度中的性能。仿真實驗結果表明，該算法在云計算系統任務調度方面有較好的性能，提高了資源的利用率。