于淑香,周洪斌
(沙洲職業(yè)工學(xué)院 電子信息工程系,江蘇 張家港 215600)
云計算是網(wǎng)格計算、并行計算和分布式計算等多種技術(shù)的融合[1],其本質(zhì)是把各地的計算機(jī)資源及相關(guān)的終端設(shè)備等組織在網(wǎng)絡(luò)“云”中,為廣大用戶提供軟件、存儲、計算和大數(shù)據(jù)的訪問使用等服務(wù)。云計算系統(tǒng)是采用多種技術(shù)把“云”中各種資源進(jìn)行重組形成一個巨大的資源庫,方便隨用隨取,解決了當(dāng)前大數(shù)據(jù)時代,激增的數(shù)據(jù)量和計算機(jī)有限的硬件水平及處理能力的矛盾。云計算的使用類似居民用水電一樣“按需使用,按量付費(fèi)”,具有較高靈活性和可靠性。高效的任務(wù)調(diào)度和合理資源分配是提高云計算系統(tǒng)性能的重點(diǎn)和難點(diǎn),這些技術(shù)的提高能使云計算系統(tǒng)更好地滿足客戶需求,降低能源消耗,提高企業(yè)效益。
資源調(diào)度模型的發(fā)展過程分為兩個階段,啟發(fā)式算法和傳統(tǒng)的資源調(diào)度算法。啟發(fā)式算法主要根據(jù)非線性理論和人工智能理論,模擬生物的自然行為尋找一些資源調(diào)度問題的最優(yōu)解[2]。而傳統(tǒng)的資源調(diào)度算法有先來先服務(wù),貪心法、輪轉(zhuǎn)調(diào)度,最大最小等算法。很多專家和學(xué)者研究實(shí)驗(yàn)表明,在云計算任務(wù)調(diào)度中,使用啟發(fā)式算法明顯優(yōu)于傳統(tǒng)的資源調(diào)度算法,具有不可比擬的優(yōu)越性。
云計算系統(tǒng)包含很多復(fù)雜和結(jié)構(gòu)迥異的資源,最優(yōu)的任務(wù)調(diào)度方案能保證快速完成用戶任務(wù)并且提高系統(tǒng)的效率和利用率。當(dāng)前的云計算系統(tǒng)大部分選用Map/Reduce思想的編程模型[3],該模型特別適合應(yīng)用于云計算系統(tǒng)中大規(guī)模數(shù)據(jù)集的產(chǎn)生和處理。任務(wù)調(diào)度模型如圖1所示。
圖1任務(wù)調(diào)度模型
云計算系統(tǒng)中有巨大的用戶量和任務(wù)量,在用戶提交任務(wù)后,任務(wù)調(diào)度系統(tǒng)首先要進(jìn)行任務(wù)分布式化,即切分任務(wù),把用戶提交的任務(wù)集切分成多個子任務(wù);子任務(wù)提交給調(diào)度中心后,根據(jù)映射法則的算法,把每個子任務(wù)調(diào)度分配給虛擬資源節(jié)點(diǎn)。
按照相關(guān)的算法將N個用戶任務(wù)分配到M個虛擬資源節(jié)點(diǎn)上(M<N),云計算環(huán)境下任務(wù)的數(shù)學(xué)模型表示如下:
⑴T={T1,T2,……Tn}表示N個待執(zhí)行獨(dú)立任務(wù)的集合。
⑵V={V1,V2,……Vm}表示M個虛擬機(jī)資源節(jié)點(diǎn)。
⑶MIPS={MIPSl,MIPS2,……,MIPSm}表示M個虛擬機(jī)的計算能力,即計算速度,MIPSi表示虛擬機(jī)Vi單位時間內(nèi)處理的指令數(shù),以百萬/秒計。
⑷任務(wù)和虛擬機(jī)節(jié)點(diǎn)之間的映射關(guān)系如矩陣M表示,若任務(wù)Ti被分配到虛擬機(jī)Vj上執(zhí)行調(diào)度,則矩陣中的元素Mij=1,否則Mij=0。
⑸任務(wù)的期望執(zhí)行時間,即第j個子任務(wù)在第i個虛擬機(jī)上執(zhí)行時間。
由上述矩陣,可以計算出每個虛擬機(jī)Vi執(zhí)行子任務(wù)的時間,如公式(1)所示。
公式中n表示虛擬機(jī)Vi執(zhí)行的子任務(wù)數(shù)量,Time(i,j)表示虛擬機(jī)Vi上的第j個子任務(wù)執(zhí)行時間。
蟻群算法是學(xué)者M(jìn)r.Dorigo等提出的,該算法受自然界中螞蟻的覓食行為過程啟發(fā)而提出。該算法具有啟發(fā)式、正反饋和分布式的搜索特點(diǎn),在許多NP類問題的優(yōu)化求解過程中被普遍應(yīng)用,如模式識別、旅行商問題、車輛調(diào)度、多重背包等。隨著算法應(yīng)用演變發(fā)展,出現(xiàn)了更接近現(xiàn)實(shí)的模擬螞蟻覓食過程的算法,即蟻群優(yōu)化算法。
設(shè)螞蟻數(shù)量是n,在尋找食物經(jīng)過的路徑上,螞蟻會留下信息素,而后來的螞蟻會依據(jù)在此路徑上走過的螞蟻留下信息素濃度去選擇合適的路徑,即每只螞蟻會根據(jù)一定的概率轉(zhuǎn)移到下一個虛擬機(jī)資源節(jié)點(diǎn),在t時刻,第k只螞蟻從虛擬機(jī)Vi訪問虛擬機(jī)Vj的概率計算如公式(2)所示。
其中:τij表示路徑(i,j)上的信息素濃度,α表示螞蟻對信息素的敏感度;β表示蟻群對信息素的敏感度,ηij表示節(jié)點(diǎn)j對節(jié)點(diǎn)i上螞蟻的吸引水平,即啟發(fā)因子,allowedk表示還沒有訪問的節(jié)點(diǎn)。
在不斷尋找食物的過程中,螞蟻在路徑上留下的初始信息素會陸續(xù)散發(fā)掉,同時又會在路徑上繼續(xù)釋放出新的信息素,所以為了有利于發(fā)現(xiàn)最優(yōu)的解,在蟻群優(yōu)化算法中,要更新路徑上的信息素,全局和局部的信息素更新如公式(3)所示。
其中:ρ ∈(0,1]表示信息素?fù)]發(fā)系數(shù),Δτij(t)表示所有m只螞蟻釋放在路徑上的信息素總量(t)表示在路徑(i,j)上第k只螞蟻釋放信息素的增量,計算信息素增量如公式(4)所示。
其中,Q表示一次搜索結(jié)束后路徑上存留信息素的總量;Lk表示螞蟻k走過路徑總長度。
2.2.1 信息素初始化
在初始時刻,利用蟻群優(yōu)化算法原理將螞蟻(任務(wù))隨機(jī)的放到云計算系統(tǒng)中的任意一個虛擬機(jī)上。此虛擬機(jī)處理器的數(shù)量為v_num。各處理器的處理能力v_pc,通信帶寬能力v_bw等參數(shù)。利用這些參數(shù)指標(biāo),云計算系統(tǒng)可以初始化每個虛擬機(jī)的信息素值,計算如公式(5)所示。
其中虛擬機(jī)i的指標(biāo)如下:τi()0是信息素初始值,v_numi是處理器的數(shù)量,v_pci是處理器的處理能力(即MIPS),v_bwi是通信帶寬[4]。
2.2.2 選擇虛擬機(jī)概率
在改進(jìn)算法中,螞蟻(任務(wù))從虛擬機(jī)Vi訪問虛擬機(jī)Vj的概率計算如公式(6)所示。
式中,q0∈(0,1)是給定的參數(shù),q為(0,1)范圍內(nèi)的隨機(jī)數(shù)。當(dāng) q<q0時,j取 MAX{allowedk}中的k,能夠得到使邊(i,k)距離i最短、信息素最高的節(jié)點(diǎn)作為下一節(jié)點(diǎn)[5]。
當(dāng)q>q0時,啟發(fā)信息函數(shù)ηij表示任務(wù)i選擇虛擬機(jī)j的期望值。在此取ηij=propertyj*LLj,其中propertyj是固定值等于τi()0的值,其計算如公式(5)所示,LLj是虛擬機(jī)負(fù)載能力的衡量值,其值高低代表虛擬機(jī)當(dāng)前狀態(tài)下處理能力的高低,當(dāng)該值比較高時,被選擇的概率就更大。LLj的計算如公式(7)所示。
其中AVTime表示截止到前一次迭代結(jié)束時,在最優(yōu)路徑中的每個虛擬機(jī)Vi的平均執(zhí)行時間。
2.2.3 信息素更新
在螞蟻選中路徑(i,j)后,立即按公式(8)局部更新路徑(i,j)上的信息素。
式中,ρ是信息素的揮發(fā)因子,且ρ∈(0,1],信息素的殘留濃度用1-ρ表示,ρ值越大,散發(fā)越快,則殘余濃度越低,所以曾探尋過的路徑對選擇當(dāng)前路徑的影響相對較小。信息素的增量用Δτij()t表示,第k只螞蟻在本次迭代中經(jīng)過路徑的長度用Lk表示[6]。
在螞蟻確定選擇某一路徑后應(yīng)減少該條路徑上的信息素,同時增加其余路徑邊被選擇的概率,當(dāng)所有螞蟻都走完一次循環(huán)之后,根據(jù)式(9)全局更新信息素,進(jìn)而使最佳路徑的搜索概率更大[5]。
公式中,Lgbest是此刻得到的最優(yōu)路徑。
⑴算法參數(shù)初始化,包括云計算虛擬機(jī)節(jié)點(diǎn)數(shù),任務(wù)數(shù),信息素和迭代次數(shù)等各參數(shù)。
⑵將X只螞蟻隨機(jī)放置在虛擬機(jī)節(jié)點(diǎn)上。
⑶計算出螞蟻個體轉(zhuǎn)移到下一虛擬機(jī)節(jié)點(diǎn)的概率,并根據(jù)計算結(jié)果進(jìn)行移動。
⑷局部更新螞蟻?zhàn)哌^路徑上的信息素值,并修改相應(yīng)的禁忌表。
⑸重復(fù)步驟2)~4),直到蟻群中的每個螞蟻個體找到一條可行的路徑截止。
⑹全局更新所有路徑的信息素。
⑺增加迭代次數(shù),如其值已達(dá)預(yù)設(shè)的最大迭代次數(shù),則停止搜索,獲得云計算任務(wù)調(diào)度的最優(yōu)解。
為了驗(yàn)證改進(jìn)蟻群算法在云計算系統(tǒng)中任務(wù)調(diào)度分配優(yōu)化效果,本文選用澳大利亞墨爾本大學(xué)和Gridbus項目共同提出的云仿真軟件CloudSim平臺進(jìn)行測試實(shí)驗(yàn)[7],實(shí)驗(yàn)的硬件環(huán)境為2.66GHz的CPU,8G的內(nèi)存,500G硬盤作為硬件環(huán)境,Windows10操作系統(tǒng)和JDK8.0的基礎(chǔ)環(huán)境及Antl.9.7的編譯工具。在CloudSim平臺中對比測試本文改進(jìn)蟻群優(yōu)化任務(wù)調(diào)度算法、標(biāo)準(zhǔn)蟻群算法和MAX-MIN算法在任務(wù)調(diào)度分配執(zhí)行方面的效率。通過初始化CloudSim,創(chuàng)建數(shù)據(jù)中心及DataCenterBroker,創(chuàng)建虛擬機(jī)、云任務(wù)集等一系列的操作后開始仿真實(shí)驗(yàn)。
仿真實(shí)驗(yàn)主要測試在任務(wù)數(shù)量增加的情況下,本文算法的任務(wù)平均完成時間,并與其他比較算法進(jìn)行對比,公平起見所有測試的算法都進(jìn)行10次實(shí)驗(yàn),統(tǒng)計平均,橫坐標(biāo)為申請任務(wù)數(shù)量,縱坐標(biāo)為各算法分別完成任務(wù)處理所需時間。在實(shí)驗(yàn)軟硬件環(huán)境相同,資源節(jié)點(diǎn)相同的情況下,幾種算法的任務(wù)完成時間對比如圖2所示。
圖2各算法任務(wù)執(zhí)行時間對比
在文件任務(wù)量不大情況下,各算法完成任務(wù)分配執(zhí)行所用時間差別不大,但從整體上來看,任務(wù)量相同時本文改進(jìn)蟻群優(yōu)化算法執(zhí)行任務(wù)用時比較短。而隨著任務(wù)數(shù)量的增加,本文算法完成任務(wù)時間增幅度不大,相反另外兩種比較算法的執(zhí)行時間增加幅度非常大。同時在實(shí)驗(yàn)中發(fā)現(xiàn)本文算法的迭代次數(shù)少于其他比較算法,這是因?yàn)楸疚乃惴ǔ晒Φ乇苊饬藗鹘y(tǒng)蟻群優(yōu)化算法容易陷入局部最優(yōu)解的缺點(diǎn),這樣可以使用戶提交的任務(wù)在相應(yīng)的資源節(jié)點(diǎn)最快分配執(zhí)行完成,提高云計算系統(tǒng)的工作效率,取得了比較理想的資源任務(wù)調(diào)度效果。
本文提出了基于改進(jìn)蟻群優(yōu)化算法的云計算任務(wù)調(diào)度算法。首先介紹了云計算系統(tǒng)的編程模型和任務(wù)調(diào)度相關(guān)定義,然后針對傳統(tǒng)蟻群優(yōu)化算法進(jìn)行改進(jìn),并在CloudSim平臺測試該算法在云計算系統(tǒng)任務(wù)調(diào)度中的性能。仿真實(shí)驗(yàn)結(jié)果表明,該算法在云計算系統(tǒng)任務(wù)調(diào)度方面有較好的性能,提高了資源的利用率。