基于改進蟻群優(yōu)化算法的云計算任務調度研究

于淑香，周洪斌

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

引言

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

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

1 云計算任務調度模型

1.1 云計算的編程模型

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

圖1任務調度模型

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

1.2 任務調度的相關定義

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

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

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

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

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

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

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

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

2 改進蟻群優(yōu)化算法

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

2.1 蟻群優(yōu)化算法原理

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

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

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

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

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

2.2 蟻群優(yōu)化算法的改進

2.2.1 信息素初始化

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

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

2.2.2 選擇虛擬機概率

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

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

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

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

2.2.3 信息素更新

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

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

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

公式中，Lgbest是此刻得到的最優(yōu)路徑。

2.3 算法描述

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

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

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

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

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

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

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

3 仿真實驗及結果分析

3.1 實驗環(huán)境

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

3.2 結果分析

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

圖2各算法任務執(zhí)行時間對比

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

4 結語

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