基于Cloudsim平臺上的啟發(fā)式融合資源動態(tài)調(diào)度算法

摘?要：基于Cloudsim云平臺，針對其自帶的資源調(diào)度算法的缺陷和現(xiàn)存已與Cloudsim結(jié)合的智能優(yōu)化算法的不足，本文將根據(jù)食品安全預(yù)警本體模型規(guī)則，結(jié)合乳制品的分類處理，提出一種新型的啟發(fā)式融合資源動態(tài)調(diào)度算法，實現(xiàn)在云平臺的資源動態(tài)調(diào)度，實現(xiàn)優(yōu)化的作業(yè)資源調(diào)度，旨在減少云端任務(wù)所執(zhí)行的時間，提高效率，在保證負(fù)載相對平衡的前提下，提出一種云資源調(diào)度方法，該方法具有較快的調(diào)度速度，實現(xiàn)資源調(diào)度算法的優(yōu)化。

關(guān)鍵詞：云平臺;Cloudsim;資源調(diào)度;啟發(fā)式算法

中圖分類號：F062.5??????文獻(xiàn)標(biāo)識碼：A??????文章編號：1008-4428（2018）07-0139-02

一、 引言

隨著科技的發(fā)展創(chuàng)新和商業(yè)模式的轉(zhuǎn)變，傳統(tǒng)的計算平臺日漸不能滿足人們的要求。于是云計算應(yīng)運(yùn)而生，它是在網(wǎng)格計算基礎(chǔ)上發(fā)展起來的一種新興商業(yè)計算模型，可以為用戶提供計算、存儲資源等各類服務(wù)，是一種新的基于服務(wù)的資源提供模式。近些年隨著社交網(wǎng)絡(luò)和各種智能移動端的飛速普及，人們的日常需求也逐漸由單純的設(shè)備功能性轉(zhuǎn)變?yōu)閷ヂ?lián)網(wǎng)的可接入性、開放性、共享性、易用性和安全性等方面的服務(wù)質(zhì)量追求，來確?？梢噪S時隨地地使用智能移動設(shè)備獲得所需服務(wù)，并能夠在信息未受到威脅和制約的情況下，方便通暢地實現(xiàn)溝通共享。因此，我們稱云計算是在社會新需求的推動下應(yīng)運(yùn)而生，另外它的用時付費商業(yè)模式不僅恰當(dāng)?shù)剡m應(yīng)了這種社會新需求的轉(zhuǎn)變，而且具有良好的經(jīng)濟(jì)效益優(yōu)勢，從而使它成了國內(nèi)外重點研究主題之一。

隨著用戶對互聯(lián)網(wǎng)需求的劇增，云計算的規(guī)模也逐漸擴(kuò)大，達(dá)到海量的用戶群體。在此基礎(chǔ)上，適應(yīng)用戶動態(tài)的需求變化并實現(xiàn)高效率低成本的資源合理分配成為云計算現(xiàn)階段的研究熱點。其中資源分配的關(guān)鍵是選擇合理的資源分配算法，合理的資源分配算法不僅可以提高計算和傳輸速度，而且能夠減輕云計算網(wǎng)絡(luò)的負(fù)荷和能耗，快速平衡網(wǎng)絡(luò)負(fù)載，從而提升系統(tǒng)性能。在云計算中，資源具有動態(tài)性、異構(gòu)性和大規(guī)模性等特點，如何根據(jù)云計算的實際特點制定合適的資源分配策略是亟待解決的難題。云計算目前發(fā)展并不成熟，但很多具有高度并行、自組織、自適應(yīng)等特性的智能優(yōu)化算法已被廣泛用于解決云計算的資源分配問題。云環(huán)境下研究任務(wù)調(diào)度算法學(xué)術(shù)與現(xiàn)實意義并存，不恰當(dāng)?shù)娜蝿?wù)調(diào)度策略一方面浪費云資源，另一方面也無法滿足用戶服務(wù)質(zhì)量需求。于是本文探討云計算下的資源分配問題，對現(xiàn)有的資源分配算法存在的問題進(jìn)行了分析，在此基礎(chǔ)上提出改進(jìn)的資源分配算法，有利于對現(xiàn)有問題的解決，有很大現(xiàn)實意義。

二、 文獻(xiàn)綜述

作為一種新型的計算服務(wù)模式，云計算得到越來越多國內(nèi)外學(xué)者的關(guān)注。云計算資源分配問題是一個NP難問題：在滿足任務(wù)完成的條件前提下，最大化資源利用率，并均衡系統(tǒng)負(fù)載。目前大多從最優(yōu)跨度、負(fù)載均衡、服務(wù)質(zhì)量、經(jīng)濟(jì)原則四個角度去衡量云計算調(diào)度算法。云環(huán)境下資源分配策略存在多種，現(xiàn)階段主要通過智能優(yōu)化算法實現(xiàn)云計算資源合理分配。結(jié)合云計算自身特性，目前只有智能優(yōu)化算法才能很好地適應(yīng)云計算平臺，于是智能優(yōu)化算法被廣泛推廣到云環(huán)境中。

熊聰聰（2012）以遺傳算法為基礎(chǔ)，搭建了新的任務(wù)調(diào)度模型，引入染色體匹配率參數(shù)來避免早熟，引入服務(wù)質(zhì)量標(biāo)準(zhǔn)改進(jìn)適應(yīng)度函數(shù)，但仍然存在搜索全局最優(yōu)解的能力較低、調(diào)度目標(biāo)單一等問題。Zhu

K（2014）結(jié)合多代理的遺傳算法，選擇一種負(fù)載均衡的模型應(yīng)用到遺傳算法，提高了資源執(zhí)行效率，但存在后期易陷入局部最優(yōu)的問題。劉萬軍（2011）改進(jìn)了粒子群算法，引入動態(tài)多群體協(xié)作和變異粒子逆向飛行因素，但并未考慮慣性權(quán)重、學(xué)習(xí)因子對負(fù)載平衡的影響。宣豪駿（2016）創(chuàng)新性地結(jié)合多種優(yōu)化智能算法提出新的融合算法，與模擬退火、蟻群和遺傳算法對比，能實現(xiàn)更優(yōu)的資源分配。王登科（2013）基于粒子群優(yōu)化與蟻群優(yōu)化，提出全新的云計算任務(wù)調(diào)度算法，算法中吸收了粒子群算法的快速收斂和蟻群算法的尋優(yōu)能力，縮短了系統(tǒng)處理調(diào)度的時間和總的任務(wù)執(zhí)行時間，提高了云計算任務(wù)調(diào)度的效率。徐浙君（2017）提出膜計算和改進(jìn)蟻群算法的融合算法在云計算資源調(diào)度中的研究，并提高了算法的整體性能，仿真實驗說明在網(wǎng)絡(luò)、成本、能量消耗上有了明顯的降低，也提高了資源分配效率。

目前，新興的元啟發(fā)式優(yōu)化算法（包括螢火蟲算法、蝙蝠算法、布谷鳥搜索算法等）還未應(yīng)用到云平臺中實現(xiàn)資源調(diào)度?，F(xiàn)階段還處于對新興的優(yōu)化算法改進(jìn)和融合階段，李煜（2012），劉長平（2013），周永權(quán)（2012）分別對布谷鳥搜索算法進(jìn)行實現(xiàn)和測試;結(jié)合蝙蝠算法的缺點提出基于邏輯自映射的變尺度混沌蝙蝠優(yōu)化算法，改善了蝙蝠算法擺脫局部極值點的能力，提高了算法收斂性和尋優(yōu)精度;螢火蟲算法與C2Opt算子相結(jié)合，設(shè)計了求解TSP的一種新的高效人工螢火蟲群優(yōu)化算法，且在求解較大規(guī)模TSP問題時非常奏效，具有收斂速度快、精度高等特點。

基于以上，本文發(fā)現(xiàn)智能優(yōu)化算法良好的靈活性、可移植性和易于實現(xiàn)的特點對于解決大規(guī)模的云計算資源分配問題很有效。目前智能優(yōu)化算法在解決云計算資源分配問題上已取得了一些成果，但在云計算資源分配模型的約束條件、適應(yīng)度函數(shù)等方面還有很大的研究空間，即現(xiàn)階段已實現(xiàn)的智能算法與Cloudsim的結(jié)合并不是最優(yōu)，因此本文將結(jié)合新興的元啟發(fā)式優(yōu)化算法，建立新的云計算資源調(diào)度模型，實現(xiàn)更優(yōu)的資源調(diào)度。

三、 啟發(fā)式融合資源動態(tài)調(diào)度算法

（一）問題描述及現(xiàn)狀分析

目前，對于Cloudsim的資源調(diào)度算法的研究主要是云平臺與元啟發(fā)式智能優(yōu)化算法的結(jié)合，提高資源調(diào)度效率?，F(xiàn)階段的研究，大多基于遺傳算法、模擬退火算法、蟻群算法等的改進(jìn)和融合，但目前的算法都仍有改進(jìn)空間，如遺傳算法雖有快速隨機(jī)全局搜索能力，但參數(shù)較多，編程較復(fù)雜，易陷入局部最優(yōu);粒子群算法初期收斂速度快，后期局部搜索能力不足，收斂速度緩慢，但同遺傳算法相比，粒子群算法收斂速度快，優(yōu)化性能比遺傳算法好，且編程易實現(xiàn)，需調(diào)整的參數(shù)少;而蟻群算法雖有較好的尋優(yōu)能力，但初期信息素匱乏，收斂速度慢。目前的研究中智能算法與Cloudsim的結(jié)合并不是最優(yōu)，仍有改善空間，因此本文提出一種新型的啟發(fā)式融合算法改進(jìn)云平臺的資源調(diào)度問題。

（二）算法說明

本文在食品安全預(yù)警本體模型的支持下，減少云端任務(wù)所執(zhí)行的時間，提高效率，提出一種基于多資源的任務(wù)調(diào)度算法，該方法具有較快的調(diào)度速度，實現(xiàn)資源調(diào)度算法的優(yōu)化，該算法能在多資源下大大縮短所有任務(wù)的平均完成時間，也能一定程度上保證負(fù)載均衡。啟發(fā)式融合資源動態(tài)調(diào)度算法流程如下圖1所示：

結(jié)合本體規(guī)則及乳制品分類處理的特性，具體算法步驟如下：

·對分類算法庫S中隨機(jī)出現(xiàn)的X0進(jìn)行調(diào)度，得到調(diào)度結(jié)果f（X0）;從而計算出作業(yè)的總完成時間和平均完成時間;

·將所找向量X0橫向移動;同樣計算出一個新的調(diào)度結(jié)果f（X1）;

·比較f（X0）與f（X1），差值記做M（x）;

·若M（x）>0，則f（X1）替換f（X0），反之不變;

·重復(fù)迭代，每次得到的最優(yōu)解組成新的解集合f（X′），對通過f（X′）更新公式進(jìn)行訓(xùn)練;

·對訓(xùn)練后的分類方法庫集合再進(jìn)行隨機(jī)游走操作;

·從局部最優(yōu)中多次隨機(jī)游走從而達(dá)到全局最優(yōu)解;

·得到改進(jìn)融合算法的最優(yōu)解，選擇最優(yōu)的分類處理算法。

上述算法的迭代過程主要通過目標(biāo)函數(shù)f（X）=f（X0）×e-βr2實現(xiàn)，其中，f（X0）表示初始選擇分類方法的分類時間，β表示吸收系數(shù)（為固定值），r表示分類算法間的距離。

（三）算法實現(xiàn)

本算法主要涉及在食品安全預(yù)警本體模型支持下的融合算法的實現(xiàn)，算法實現(xiàn)過程：

1.

初始化輸入：分類處理算法庫的規(guī)模為S，分類任務(wù)集合task={task1，task2，…，taskn}，n個任務(wù)，分類算法庫資源的數(shù)量為resource，初始化輸入由向量來定義，記初始化的向量坐標(biāo)為[-（resource-1），resource+1]之間的整數(shù)。

2. 初始迭代過程：初始化分類算法 Xi（i=1，2，…，n）

最優(yōu)目標(biāo)的迭代：Xj=Xi+γ0e-βγ2ij+ζεi。其中，Xi，Xj表示i，j兩種分類方法的狀態(tài)，ξ是一個隨機(jī)參數(shù)，遵循正態(tài)分布。

目標(biāo)函數(shù)：f（X）=f（X0）×e-βr2。f（X0）表示初始選擇分類方法的分類時間，β表示吸收系數(shù)（為固定值），r表示分類算法間的距離。

經(jīng)過多次迭代后得到初始迭代最優(yōu)解集合記為f（X′）。

3. 訓(xùn)練過程：通過更新公式實現(xiàn)對初始迭代最優(yōu)解的解集合實現(xiàn)訓(xùn)練。

更新公式：Xt+1i=Xti+aLevy（λ）。其中Xti和Xt+1i分別表示第i個分類方法在第t次和第t+1次的分類狀態(tài)，a表示步長控制量，為點對點乘法，Levy（λ）為Levy飛行隨機(jī)搜索的跳躍路徑，并且Levy～u=t-λ，（1<λ<3）。

4.隨機(jī)游走迭代：Xnew=X+εAt。其中ε為[-1，1]中的隨機(jī)數(shù)，x為從當(dāng)前訓(xùn)練集中集中隨機(jī)選擇的一個解，At=為全體算法在迭代次數(shù)為t時的平均時間效率。

在上述算法的迭代過程，根據(jù)食品安全預(yù)警本體模型規(guī)則中的閾值，設(shè)置算法的終止條件，記為θ，完成算法迭代之后得到最優(yōu)解X*。

5.啟發(fā)式融合算法偽代碼如下：

目標(biāo)函數(shù)：f（X），X=（X1，X2，…，Xm）Τ。初始化分類方法庫 xi（i=1，2，…，n）。

初始化基本參數(shù)β，γ0，MaxG（迭代次數(shù)），本體規(guī)則閾值θ。

While（t

for?i=1：n

??for?j=1：i

計算分類方法i的調(diào)度時間

if?（Ii

算法i向算法j移動

??end?if

??計算更新的調(diào)度時間

end

end

對所有分類算法的調(diào)度時間進(jìn)行排序，找出當(dāng)前最優(yōu)解

End

為了驗證本發(fā)明提出的在食品安全預(yù)警本體模型的支持下的新型啟發(fā)式融合算法在云資源調(diào)度中的有效性，將模型在Cloudsim云計算模擬器上進(jìn)行了仿真實驗，所有實驗都基于Eclipse環(huán)境中實現(xiàn)的，如圖2所示。

四、 總結(jié)

本文涉及云計算的資源調(diào)度算法，屬于人工智能和云計算領(lǐng)域。在本體規(guī)則庫的基礎(chǔ)上，本發(fā)明涉及布谷鳥搜索算法、蝙蝠算法和螢火蟲算法，以及云計算、Couldsim

云計算模擬器，旨在實現(xiàn)一種新型的啟發(fā)式融合算法，對比分析任務(wù)執(zhí)行所花費的時間，在食品安全預(yù)警本體模型的支持下，得到最優(yōu)化的云計算資源調(diào)度方案。

基于Cloudsim云平臺，針對其自帶的資源調(diào)度算法的缺陷和現(xiàn)存已與Cloudsim結(jié)合的智能優(yōu)化算法的不足，根據(jù)食品安全預(yù)警本體模型規(guī)則，結(jié)合乳制品的分類處理，提出了一種新型的啟發(fā)式融合資源動態(tài)調(diào)度算法，實現(xiàn)在云平臺的資源動態(tài)調(diào)度，實現(xiàn)優(yōu)化的作業(yè)資源調(diào)度。本算法旨在減少云端任務(wù)所執(zhí)行的時間，提高效率，在保證負(fù)載相對平衡的前提下，提出一種云資源調(diào)度方法，該方法具有較快的調(diào)度速度，實現(xiàn)資源調(diào)度算法的優(yōu)化。

參考文獻(xiàn)：

[1]熊聰聰，馮龍，陳麗仙，蘇靜.云計算中基于遺傳算法的任務(wù)調(diào)度算法研究[J].華中科技大學(xué)學(xué)報（自然科學(xué)版），2012（S1）：1-4.

[2]Zhu K， Song H， Liu L， et al. Hybrid Genetic Algorithm for Cloud Computing Applications[C]∥ IEEE Asia-Pacific Services Computing Conference， Apscc 2011， Jeju， Korea.

DBLP，2014：182-187.

[3]劉萬軍，張孟華，郭文越.基于MPSO算法的云計算資源調(diào)度策略[J].計算機(jī)工程，2011（11）：43-44+48.

[4]宣豪駿，姜瑛.Cloudsim中基于智能算法的任務(wù)調(diào)度研究[J].價值工程，2016（10）：162-163.

[5]王登科，李忠.基于粒子群優(yōu)化與蟻群優(yōu)化的云計算任務(wù)調(diào)度算法[J].計算機(jī)應(yīng)用與軟件，2013（1）：290-293.

[6]徐浙君，陳善雄.基于膜計算和蟻群算法的融合算法在云計算資源調(diào)度中的研究[J].計算機(jī)測量與控制，2017（1）：127-130.

[7]李煜，馬良.新型元啟發(fā)式布谷鳥搜索算法[J].系統(tǒng)工程，2012（8）：64-69.

[8]劉長平，葉春明.具有混沌搜索策略的蝙蝠優(yōu)化算法及性能仿真[J].系統(tǒng)仿真學(xué)報，2013（6）：1183-1188+1195.

[9]周永權(quán)，黃正新.求解TSP的人工螢火蟲群優(yōu)化算法[J].控制與決策，2012（12）：1816-1821.

作者簡介：

張慧中，女，安徽池州人，南京財經(jīng)大學(xué)管理科學(xué)與工程專業(yè)在讀研究生，研究方向：質(zhì)量管理、資源匹配。