一種面向成本驅(qū)動的云資源調(diào)度策略研究?

聶清彬蔡婷張莉萍曹耀欽

(1.重慶郵電大學(xué)移通學(xué)院，重慶401520；2.四川大學(xué)錦江學(xué)院，四川錦江620860;3.重慶郵電大學(xué)軟件工程學(xué)院，重慶400065)

0 引言

云計(jì)算是通過整合、管理、調(diào)配分布在網(wǎng)絡(luò)各處的計(jì)算資源，并以統(tǒng)一的界面同時向大量用戶提供服務(wù)的新型計(jì)算模式．云計(jì)算是把具有可伸縮的、動態(tài)的、分散的資源進(jìn)行虛擬化以后以付費(fèi)的方式提供給用戶，用戶只需要提交任務(wù)給云計(jì)算中心，云計(jì)算機(jī)中心就會分配相應(yīng)的資源來完成這些任務(wù)[1]．由于云計(jì)算中的任務(wù)量巨大，每時每刻都有海量的任務(wù)提交給云計(jì)算中心，因此對于云計(jì)算系統(tǒng)而言，如何采用有效的資源調(diào)度算法來合理地分配資源，讓整個云計(jì)算資源得到充分利用、降低任務(wù)執(zhí)行成本，提高執(zhí)行效率是研究的重點(diǎn)．

很多學(xué)者提出了用改進(jìn)的蟻群算法來更好的解決云環(huán)境下的任務(wù)調(diào)度，如張秋明[2]提出采用螞蟻系統(tǒng)的偽隨即比例規(guī)則進(jìn)行尋優(yōu)，防止算法過快收斂到局部最優(yōu)解，同時結(jié)合最大最小蟻群的設(shè)計(jì)思想完成信息素的更新，有效地解決優(yōu)化問題，提高了云資源的利用率；魏赟，陳元元[3]提出了一種能改善任務(wù)并行性和兼顧任務(wù)串行關(guān)系的改進(jìn)蟻群算法DSFACO，把提交的任務(wù)細(xì)分成能互相制約關(guān)系的子任務(wù)，根據(jù)執(zhí)行先后次序放到不同優(yōu)先級的調(diào)度隊(duì)列中，縮短了任務(wù)的延遲時間，實(shí)現(xiàn)了云環(huán)境下任務(wù)的最優(yōu)分配；張煥青，張學(xué)平[4]提出了基于虛擬機(jī)負(fù)載均衡的蟻群優(yōu)化算法LBACO，通過調(diào)整信息素因子，改進(jìn)信息素更新規(guī)則，實(shí)現(xiàn)任務(wù)調(diào)度的負(fù)載均衡；華夏渝，鄭駿，胡文心[5]提出了一種基于改進(jìn)蟻群算法的計(jì)算資源分配算法，在資源調(diào)度之前，首先對可用節(jié)點(diǎn)的計(jì)算能力進(jìn)行預(yù)測，分析線路質(zhì)量、帶寬的使用情況以及響應(yīng)時間等因素對資源調(diào)度的影響，通過蟻群算法計(jì)算出最優(yōu)的資源，該算法在符合云計(jì)算環(huán)境配置的前提下，對比以往的網(wǎng)格分配算法，具有更優(yōu)的調(diào)度效果和更短的響應(yīng)時間．這些算法都不同程度地優(yōu)化了云計(jì)算中資源調(diào)度的過程，但是都鮮有考慮到成本因素，就和日常購物一樣，消費(fèi)者購買同樣的商品都需要對比不同的價格，往往在同等條件下選擇價格更低的商品．云計(jì)算任務(wù)分配也一樣，用戶都要考慮任務(wù)的執(zhí)行成本以及負(fù)載．因此為了降低任務(wù)執(zhí)行成本，同時使云計(jì)算中心負(fù)載更加均衡，本文在已有的蟻群算法基礎(chǔ)之上提出基于負(fù)載均衡的改進(jìn)蟻群算法(Cost and Load balance Ant Colony Optimization(CLBACO)來實(shí)現(xiàn)對子任務(wù)的分配．

1 云計(jì)算中任務(wù)調(diào)度問題的描述

目前，云計(jì)算環(huán)境下任務(wù)調(diào)度很多都采用Google提出的Map/Reduce的分布式編程模式[6]，分成Map(映射)和Reduce(化簡)兩個階段：在Map階段，將用戶提交的任務(wù)劃分成一些小的子任務(wù)，然后分配到若干個虛擬機(jī)節(jié)點(diǎn)上并發(fā)地執(zhí)行，執(zhí)行結(jié)束并輸出結(jié)果；在Reduce階段，將Map階段輸出的結(jié)果進(jìn)行匯總處理，并把最終的處理結(jié)果交付給用戶．在Map/Reduce計(jì)算編程模式下，如何對分割的子任務(wù)進(jìn)行高效低成本的調(diào)度是算法的關(guān)鍵．

在云環(huán)境中，將n個分別獨(dú)立的子任務(wù)分配到m個虛擬機(jī)上并行執(zhí)行(m

虛擬機(jī)vmj上執(zhí)行的任務(wù)成本之和

執(zhí)行完所有任務(wù)云計(jì)算中心所需的總成本為

云計(jì)算中心的平均成本為

2 基于成本改進(jìn)的蟻群調(diào)度算法

蟻群算法是由M.Dorigo等人在20世紀(jì)90年代提出的一種啟發(fā)式仿生算法[7]，它模擬螞蟻群體覓食過程．在螞蟻尋找食物過程中，在其經(jīng)過的每一條路經(jīng)上遺留下一種信息，叫信息素(pheromone)．這些路徑上已經(jīng)留下的信息素的濃度大小對后續(xù)螞蟻選擇自己下一步的走哪條路徑具有很大的影響．一般情況下，螞蟻都會選擇信息素濃度更高的路徑．如果有更多的螞蟻傾向選擇某一條路徑，則在該路徑上留下的信息素濃度也就越高，這樣后續(xù)的螞蟻選擇該路徑的概率也就越大．大量螞蟻選擇信息濃度高的路徑的行為就體現(xiàn)出蟻群的整體運(yùn)動機(jī)制．最終搜索到一條較短的覓食路徑，該算法具有正反饋魯棒性、并行性、可擴(kuò)展性以及高求解精度，并且易與其他方法結(jié)合的優(yōu)點(diǎn)．能在海量的解空間中最大限度地尋找全局最優(yōu)解，特別是在解決組合優(yōu)化問題方面，根據(jù)狀態(tài)轉(zhuǎn)移概率來搜索解的空間，結(jié)合信息素的更新，找到最優(yōu)解．本文提出基于執(zhí)行成本的改進(jìn)蟻群算法，在標(biāo)準(zhǔn)蟻群算法的基礎(chǔ)上為降低任務(wù)執(zhí)行成本對云計(jì)算任務(wù)分配算法進(jìn)行改進(jìn)，提出信息素改進(jìn)因子PIF,改進(jìn)信息素的更新規(guī)則，使得在執(zhí)行同等任務(wù)的情況下，任務(wù)的執(zhí)行成本最低，虛擬機(jī)的利用率最高．

2.1 虛擬機(jī)的選擇

結(jié)合蟻群算法公式(5)計(jì)算出任務(wù)ti被分配到虛擬機(jī)vmj的概率值

其中τij(t)表示在t時刻路徑(i,j)上的信息素濃度；ηij(t)表示在t時刻路徑(i,j)上的啟發(fā)信息；α為期望啟發(fā)因子，表示螞蟻在任務(wù)調(diào)度過程中的啟發(fā)信息對任務(wù)選擇的相對重要程度；β為信息素啟發(fā)因子，表示路徑上的殘留信息素濃度對任務(wù)選擇的影響程度；tabuk(k=1,2···n)，記錄螞蟻已經(jīng)走過的城市，被訪問過的城市會加入禁忌表；allowedk表示第k只螞蟻允許訪問的下一個城市的節(jié)點(diǎn)，是禁忌表之外螞蟻還沒走過的城市．設(shè)置螞蟻的迭代次數(shù)為nc，最大迭代次數(shù)為ncmax．

2.2 初始化信息素和啟發(fā)信息

在蟻群算法中，信息素τij(t)和啟發(fā)函數(shù)ηij(t)是最重要的參數(shù)．由于云計(jì)算的動態(tài)性和異構(gòu)性，本文通過虛擬機(jī)的計(jì)算能力、網(wǎng)絡(luò)帶寬和執(zhí)行成本對啟發(fā)函數(shù)和信息素進(jìn)行初始化，

其中表示虛擬機(jī)vmj的處理器數(shù)量，表示虛擬機(jī)vmj處理器運(yùn)算速度，表示虛擬機(jī)vmj網(wǎng)絡(luò)帶寬,表示虛擬機(jī)內(nèi)存．

在進(jìn)行任務(wù)分配選擇虛擬機(jī)過程中，可以通過輪盤賭算法來決定某一個任務(wù)分配到哪個虛擬機(jī)上去執(zhí)行．首先通過概率轉(zhuǎn)移公式(5)計(jì)算出任務(wù)ti分配到虛擬機(jī)vmj的概率，這就相當(dāng)于構(gòu)造出賭盤上的一個扇區(qū)，賭盤上的扇區(qū)分區(qū)面積越大，指針指向該分區(qū)的概率也就越大．任務(wù)分配到該虛擬機(jī)的概率值對應(yīng)每個分區(qū)的大小，則任務(wù)分配到該虛擬機(jī)的轉(zhuǎn)移概率值越大，更有可能被選中來執(zhí)行下一個任務(wù)．

2.3 信息素的更新

當(dāng)螞蟻將任務(wù)分配到虛擬機(jī)上以后，隨著迭代次數(shù)的增加，原有的信息素就會隨之增加．如果不對路徑上殘留的信息素進(jìn)行更新，算法將會陷入局部收斂的狀態(tài)，因此在每只螞蟻完成任務(wù)分配時，就利用公式(8)進(jìn)行信息素更新

其中：ρ是信息揮發(fā)因子，表示信息素在單位時間內(nèi)的揮發(fā)程度；1?ρ表示信息素濃度殘留程度，ρ∈(0,1]，如果ρ越大，說明信息素?fù)]發(fā)越快，則過去搜素過的路徑對現(xiàn)在的選擇影響也就越??；?τij表示信息素濃度的增量，用執(zhí)行成本costij對信息素增量?τij進(jìn)行改進(jìn)，改進(jìn)的信息素更新分為局部更新和全局更新．

(1)當(dāng)一只螞蟻通過路徑搜素，也就是任務(wù)被分配到某一個虛擬機(jī)上,找到了相應(yīng)的分配方案以后，路徑上所有的虛擬機(jī)都將進(jìn)行一次局部信息素更新，此時?τij定義如下:

其中D1表示常量，costij表示第i只螞蟻在vmj上的執(zhí)行成本．

(2)當(dāng)所有螞蟻完成路徑搜素后，找到本次迭代中最優(yōu)的路徑，然后對路徑上的所有虛擬機(jī)進(jìn)行全局信息素更新，此時?τij定義如下：

其中costtotal?best表示在第本次最優(yōu)分配方案中為任務(wù)搜素到的最低執(zhí)行成本，D2為常量．

2.4 負(fù)載不均衡度的定義

在虛擬機(jī)vmj負(fù)載不均衡度定義Lj如下：

costj表示虛擬機(jī)vmj上的執(zhí)行所有任務(wù)所需成本，costavg表示所有虛擬機(jī)執(zhí)行任務(wù)的平均成本．

2.5 信息素改進(jìn)因子的建立

在實(shí)際云環(huán)境中，由于云計(jì)算資源存在動態(tài)性和異構(gòu)性，每個虛擬機(jī)的網(wǎng)絡(luò)帶寬、計(jì)算能力、內(nèi)存大小等差異較大，單位時間內(nèi)執(zhí)行任務(wù)的成本有較大差別；有的虛擬機(jī)性能較差，有的虛擬機(jī)性能明顯較好，這樣就容易造成大量任務(wù)聚集到一部分性能高的虛擬機(jī)上執(zhí)行，而且容易造成等待的任務(wù)增多，同時另外性能較差的虛擬機(jī)資源卻處于閑置的狀態(tài)，使得整個云計(jì)算中的資源利用率很低[8]．為了解決這個問題，本文提出改變信息素更新規(guī)則，信息素中一方面要考慮虛擬機(jī)執(zhí)行任務(wù)成本，另一方面可以通過成本改變虛擬機(jī)的負(fù)載不均衡度，通過改進(jìn)信息素更新規(guī)則可以讓閑置的虛擬機(jī)分配更多的任務(wù)，為分配過多任務(wù)的虛擬機(jī)減輕負(fù)載，改進(jìn)信息素因子PIF定義為：

如果虛擬機(jī)vmj在之前迭代過程中負(fù)載過重，執(zhí)行同樣的任務(wù)，執(zhí)行時間會更長．根據(jù)公式(1)計(jì)算，執(zhí)行任務(wù)的成本就會比其他虛擬機(jī)完成該任務(wù)的成本更大，則虛擬機(jī)vmj的信息素調(diào)整因子PIF和其他虛擬機(jī)因子相比，PIF更大，則τij(t+1)變小，根據(jù)公式(5)進(jìn)行任務(wù)分配時，虛擬機(jī)vmj被分配到任務(wù)的概率變小，經(jīng)過算法多次迭代以后，改進(jìn)后的算法最終能實(shí)現(xiàn)云計(jì)算中心虛擬機(jī)的負(fù)載平衡．

3 算法流程

第1步：初始化云計(jì)算機(jī)中所有虛擬機(jī)的信息素的值，信息素啟發(fā)因子α和揮發(fā)因子ρ，期望啟發(fā)因子β,螞蟻個數(shù)m,設(shè)置迭代次數(shù)nc=0以及最大迭代次數(shù)ncmax；

第2步：將螞蟻隨機(jī)地選擇任務(wù)；

第3步：根據(jù)公式(5)計(jì)算每個虛擬機(jī)被選中的概率，通過輪盤賭算法確定最終執(zhí)行任務(wù)的虛擬機(jī)；

第4步：如果完成本次任務(wù)分配，根據(jù)公式(9)進(jìn)行局部信息素的更新，否則跳轉(zhuǎn)到步驟2；

第5步：如果所有螞蟻完成了本次任務(wù)的分配，根據(jù)分配情況找出本次任務(wù)分配中最優(yōu)的分配方案，根據(jù)公式(10),通過本次的最優(yōu)解進(jìn)行全局信息素更新；

第6步：判定當(dāng)前迭代次數(shù)是否達(dá)到最大迭代次數(shù)，如果是，結(jié)束算法流程；如果沒有，跳轉(zhuǎn)到步驟2繼續(xù)執(zhí)行．

4 仿真實(shí)驗(yàn)結(jié)果與分析

為驗(yàn)證算法的有效性和可行性，選擇云計(jì)算仿真平臺CloudSim3.0進(jìn)行仿真實(shí)驗(yàn)，利用CloudSim里面的Cloudlet，DataCenter，VM以及一些輔助類來模擬云計(jì)算環(huán)境及網(wǎng)絡(luò)資源，創(chuàng)建任務(wù)和虛擬機(jī)，并重寫DataCenterBroker,Cloudlet類來構(gòu)造CLBACO算法；模擬云計(jì)算的真實(shí)環(huán)境，并在基于同樣配置和參數(shù)設(shè)置的條件下與標(biāo)準(zhǔn)的蟻群算法以及文獻(xiàn)[3]中的云計(jì)算中改進(jìn)任務(wù)調(diào)度算法DSFACO進(jìn)行對比．

在實(shí)驗(yàn)中，對CloudSim模擬器參數(shù)進(jìn)行設(shè)置,設(shè)置數(shù)據(jù)中心為20個，每個數(shù)據(jù)中心設(shè)置10個虛擬機(jī)．虛擬機(jī)性能參數(shù)設(shè)置為500～2000MIPS，內(nèi)存為512-2048MB,帶寬為5000～10000b/s,任務(wù)指令長度為300～3600 MI(Million Instruction)，任務(wù)數(shù)量為200～1000個任務(wù)，虛擬機(jī)單位時間運(yùn)行所消耗成本rcu(vmj)值為20$，最大迭代次數(shù)ncmax為50次，在資源中心執(zhí)行時間共享和空間共享的策略，調(diào)度算法中的參數(shù)設(shè)置為:α=1,β=3,ρ=0.02，CloudSim仿真步驟如下：

步驟一：初始化CloudSim包；步驟二：創(chuàng)建數(shù)據(jù)中心；步驟三：創(chuàng)建數(shù)據(jù)代理中心；步驟四：創(chuàng)建虛擬機(jī)；步驟五：創(chuàng)建云任務(wù)；步驟六：調(diào)用任務(wù)調(diào)度策略，分配任務(wù)到虛擬機(jī)；步驟七：啟動仿真；步驟八：仿真結(jié)束后分析結(jié)果．

試驗(yàn)中在同等條件下將標(biāo)準(zhǔn)的蟻群算法ACO，文獻(xiàn)[2]中的DSFACO算法和本文的CLBACO算法進(jìn)行試驗(yàn)仿真，對比任務(wù)的執(zhí)行成本以及虛擬機(jī)的負(fù)載率狀況，具體實(shí)驗(yàn)數(shù)據(jù)如圖1所示，圖中任務(wù)執(zhí)行成本單位為美元($)，執(zhí)行時間單位為s(second)．

圖1 任務(wù)執(zhí)行成本比較

圖2 負(fù)載均衡率比較

從圖1可以看出，當(dāng)任務(wù)量較少時，CLBACO和DSFACO算法執(zhí)行成本差別不大；隨著任務(wù)數(shù)量的增加，執(zhí)行同樣多數(shù)量的任務(wù)，CLBACO算法的執(zhí)行成本明顯降低．說明通過本算法改進(jìn)信息素的局部更新和全局更新，可以達(dá)到讓任務(wù)執(zhí)行成本降低的目的．

圖2反映了虛擬機(jī)的負(fù)載不均衡度對比．從圖中可以看出：標(biāo)準(zhǔn)的蟻群算法ACO負(fù)載不均衡度是最高的，說明負(fù)載不平衡；DSFACO算法負(fù)載有所改進(jìn)，但是算法改進(jìn)不夠明顯；CLBACO算法相比前面兩種算法將負(fù)載不均衡度降低了0.5-1.2左右，在有效降低成本的同時，也很好的實(shí)現(xiàn)了負(fù)載均衡．

5 結(jié)束語

本文提出了基于成本約束函數(shù)、負(fù)載均衡的改進(jìn)蟻群優(yōu)化算法CLBACO,用來改進(jìn)云計(jì)算中的資源調(diào)度．實(shí)驗(yàn)結(jié)果表明，CLBACO算法性能明顯優(yōu)于DSFACO算法，有效優(yōu)化了資源的調(diào)度，降低了任務(wù)執(zhí)行成本,提高了系統(tǒng)執(zhí)行任務(wù)效率，讓云計(jì)算系統(tǒng)始終保持在一個負(fù)載均衡的狀態(tài)．

參考文獻(xiàn)：

[1]李依桐，林燕.基于混合粒子群算法的云計(jì)算任務(wù)調(diào)度研究[J].計(jì)算技術(shù)與自動化，2014,33(1):73-77.

[2]張秋明.基于改進(jìn)蟻群算法的云計(jì)算任務(wù)調(diào)度[J].電子技術(shù)應(yīng)用，2015.41(2):120-126.

[3]魏赟,陳元元.基于改進(jìn)蟻群算法的云計(jì)算任務(wù)調(diào)度模型[J].計(jì)算機(jī)工程,2015,41(1):12-16.

[4]張煥青，張學(xué)平,等.基于負(fù)載均衡蟻群優(yōu)化算法的云計(jì)算任務(wù)調(diào)度[J].微電子學(xué)與計(jì)算機(jī),2015,5(5):31-40.

[5]華夏渝,鄭駿,胡文心.基于云計(jì)算環(huán)境的蟻群優(yōu)化計(jì)算資源分配算法[J].華東師范大學(xué)學(xué)報(bào),2010,2(1):127-134.

[6]查英華，楊靜麗.改進(jìn)蟻群算法在云計(jì)算任務(wù)調(diào)度中的應(yīng)用[J].計(jì)算機(jī)工程與設(shè)計(jì),2013,34(5):1716-1816.

[7]董云紅，高志棟,等.基于蟻群算法的云計(jì)算資源調(diào)度研究[J].中國西部科技，2013,12(4):29-31.

[8]董麗麗，黃賁，介軍.云計(jì)算中基于差分進(jìn)化算法的任務(wù)調(diào)度研究[J].計(jì)算機(jī)工程與應(yīng)用，2014,50(5):90-95.