鞠成恩 趙曉俠 王明興 問尤龍

摘 要：在大量用戶請求云計算資源服務(wù)時，如何合理組織資源和任務(wù)調(diào)度是云計算的關(guān)鍵技術(shù)之一。如果分配調(diào)度方法不合理，就可能產(chǎn)生用戶需求得不到滿足和資源使用不均衡等問題。在傳統(tǒng)遺傳算法基礎(chǔ)上，將模擬退火算法與遺傳算法相融合，擴大遺傳算法的搜索領(lǐng)域，解決遺傳算法早熟收斂現(xiàn)象，使云資源分配更加合理，以提高云資源利用率。在CloudSim平臺上進行仿真，結(jié)果表明該方式能較好地對云計算資源進行分配，在能耗、帶寬等約束條件下達(dá)到云資源最優(yōu)調(diào)度的目的。

關(guān)鍵詞：智能算法；云資源；優(yōu)化調(diào)度；CloudSim仿真

DOI：10.11907/rjdk.172641

中圖分類號：TP312

文獻(xiàn)標(biāo)識碼：A 文章編號：1672-7800（2018）004-0045-02

Abstract：With the development of Internet， cloud computing has become a hot research topic in academic and commercial fields. When a large number of users request cloud computing resource services， how to do reasonable resource sister scheduling and task scheduling becomes one of the key technologies of cloud computing. If the allocation method is not reasonable， the user demand can not be met and the use of resources is not balanced. The traditional genetic algorithm combines with simulated annealing algorithm to expand the search field and solve the premature convergence phenomenon and makes the use of cloud resource allocation more reasonable to improve the utilization of cloud resources. Simulation experiments on CloudSim platform show that this method can better allocate the cloud computing resources， and achieve the purpose of optimal scheduling of cloud resources.

Key Words：intelligence algorithm； cloud resource； optimal scheduling； CloudSim simulation

0 引言

云計算[1-2]由網(wǎng)格計算發(fā)展而來，它將計算資源、存儲資源和網(wǎng)絡(luò)資源進行整合，按照用戶需求進行分配資源服務(wù)，是一種新興的網(wǎng)絡(luò)服務(wù)和交互模式。云計算在云端部署計算機集群，運用虛擬化技術(shù)組成一個大型虛擬資源池（Virtualized Resource Pool）[3]，利用各種工具對虛擬資源池進行統(tǒng)一管理；在終端為用戶與運營商提供服務(wù)接口，運營商通過這些接口為用戶提供可擴展、分布式存儲與計算等服務(wù)，用戶在使用時可以對資源自行管理與配置[4]。

大多數(shù)情況下云計算的資源調(diào)度任務(wù)并發(fā)產(chǎn)生，且分布不均勻，當(dāng)用戶群體十分龐大時，虛擬機優(yōu)化調(diào)度會越來越復(fù)雜，需要云計算系統(tǒng)提供靈活的分配機制，這些需求使云計算調(diào)度變得困難。本文以基本遺傳算法[5-6]為基礎(chǔ)，引入模擬退火算法[7-8]與之相融合，以改進遺傳算法的局部搜尋能力，擴大遺傳算法搜索領(lǐng)域，從而有效解決了遺傳算法早熟收斂現(xiàn)象，使資源分配更加合理、高效。

1 基于遺傳算法的資源調(diào)度算法設(shè)計

1.1 編碼表示方法與初始種群產(chǎn)生

遺傳算法產(chǎn)生種群一般采用隨機方式，這種方法產(chǎn)生的種群有很多非連通路徑，這些非連通路徑雖然在以后的迭代運算中可能轉(zhuǎn)化為連通路徑，但轉(zhuǎn)化效果一般，使得過程解在有限的進化代數(shù)內(nèi)可能過早收斂，從而影響最終解的質(zhì)量。所以，在確保初始種群的多樣性前提下，要盡可能保證所產(chǎn)生的路徑是連通的，這對于改善算法的求解速度和全局收斂性幫助很大。

將N個虛擬機放置在M個主機上，得到個體基因編碼{k0，k1，…kn-1}。其中第i個虛擬機ki的取值范圍為[0，m-1]。用一個具體例子說明：當(dāng)虛擬機的數(shù)量為10，主機數(shù)量為5時，編碼將產(chǎn)生一個長度為10的序列，假設(shè)產(chǎn)生的序列為{2，3，1，4，0，0，1，2，2，3}，虛擬機在編號0-9中分別按照序列{2，3，1，4，0，0，1，2，2，3}的順序創(chuàng)建在對應(yīng)主機上。

1.2 適應(yīng)度函數(shù)

云環(huán)境下的能耗模型主要考慮計算能耗和數(shù)據(jù)傳輸能耗。有研究表明，云計算環(huán)境下主機的功耗與其CPU利用率之間存在一種近似線性關(guān)系[9]，所以使用CPU利用率作為主機的能耗，用E表示；而直接影響服務(wù)質(zhì)量和用戶使用感受的另一個主要因素是帶寬[10]，具有較少帶寬負(fù)載和時間花費的個體有更好的適應(yīng)度，用B表示。因此，消耗程度低的認(rèn)為適應(yīng)度較好，其函數(shù)F為：

1.3 選擇與交叉算子

使用更加合理的輪盤賭方式選擇算子。輪盤賭是累積并記錄種群中各基因的適應(yīng)值，然后用一個位于[0，1]區(qū)間的隨機數(shù)D做閾值，當(dāng)D大于某個基因記錄值時某個基因就被選中。例如基因數(shù)量為M種群{K1，K2，…，Km}，對應(yīng)的累積值為{ΔF1，ΔF2，…，ΔFm}，ΔFi由式（2）確定。如果產(chǎn)生的隨機數(shù)D剛好大于ΔFi，則Ki號基因被選中：

這樣連續(xù)進行M次形成新的種群，通過新的種群進行單點交叉算子操作。在每個個體中隨機選擇一個位置作為交叉點，將一個體染色體在交叉點位置分為前后兩部分，與另一個體的部分基因進行交換。

1.4 變異方式

本文采用多點變異方式，在個體染色體內(nèi)隨機選擇多個位置，每個位置進行小范圍變異，設(shè)置變異界值為0.1，若產(chǎn)生的隨機數(shù)小于0.1則發(fā)生變異，否則不發(fā)生變異。

2 融合模擬退火算法

模擬退火算法（Wimulated Annealing， SA）的思想最早由Metropolis[8-9]提出，其原理來源于物理中高溫固體物質(zhì)的物理退火，用于求解組合優(yōu)化問題。云環(huán)境下遺傳算法中融合模擬退火算法具體實現(xiàn)如下：①初始化參數(shù)。設(shè)定足夠大的初始溫度T=T0，溫度衰減參數(shù)α，隨機選擇群體中的基因作為初始解進行適應(yīng)值計算，確定每個溫度T下的迭代次數(shù)L；②通過交差算子和變異等生成新種群，計算新種群每個基因個體的適應(yīng)度值；③分別與父代個體進行比較，按照Metropolis準(zhǔn)則：若新適應(yīng)度值大于原適應(yīng)度值，則接受新個體，并以新個體代替原來種群中對應(yīng)的舊個體；若新適應(yīng)度值小于原適應(yīng)度值，則以概率expfk-newfkT接受新個體代替舊個體；④gen=gen+1，若達(dá)到最大迭代次數(shù)L則向下進行，若沒有則返回到第②步；⑤若達(dá)到終止條件則輸出最優(yōu)解，若沒有達(dá)到則令T=αT，重置迭代數(shù)并返回到第②步。

遺傳算法中融合模擬退火算法流程見圖1。

3 仿真

本文采用 Cloud Sim仿真工具進行仿真試驗。 Cloud Sim 是由澳大利亞墨爾本大學(xué)的網(wǎng)格實驗室推出的一款具有跨平臺特點的云計算仿真軟件[11]，是一個模擬大規(guī)模云計算數(shù)據(jù)中心的開源框架，在云資源調(diào)度研究中使用非常廣泛。

初始化的參數(shù)需要對用戶數(shù)量、日期、追蹤標(biāo)志等進行定義，數(shù)據(jù)中心是 Power 類型，創(chuàng)建數(shù)據(jù)中心代理Broker，這里代理的類型也是 Power 類型；創(chuàng)建虛擬機數(shù)和主機數(shù)，這里設(shè)置虛擬機數(shù)和主機數(shù)量比例為2∶1；設(shè)置調(diào)度策略配置遺傳算法；創(chuàng)建云任務(wù)，實驗采用Cloud Sim 自帶的云工作平臺下的任務(wù)。

設(shè)置遺傳算法所需相關(guān)參數(shù)：初始種群規(guī)模為20，變異率為0.01，起始溫度參數(shù)k為100，溫度下降參數(shù)α為0.8，溫度下降時迭代數(shù)20。傳統(tǒng)遺傳算法及融合退火算法對云資源分配的仿真結(jié)果比較如圖2所示。

4 結(jié)語

通過在Cloud Sim平臺上進行仿真實驗，將融入模擬退火算法改進后的遺傳算法與改進前的遺傳算法進行比較。實驗表明：融入模擬退火算法的遺傳算法比傳統(tǒng)遺傳算法更能體現(xiàn)云計算資源調(diào)度中的優(yōu)勢，特別是當(dāng)虛擬主機數(shù)量增加時這種優(yōu)勢更加明顯，更能適應(yīng)云計算大規(guī)模資源調(diào)度環(huán)境。

參考文獻(xiàn)：

[1] 陳康，鄭緯民.云計算：系統(tǒng)實例與研究現(xiàn)狀[J].軟件學(xué)報，2009，20（5）：1337-1348.

[2] 劉鵬.云計算[M].第2版.北京：電子工業(yè)出版社，2011：1-14.

[3] 鄧維，劉方明，金海，等.云計算數(shù)據(jù)中心的新能源應(yīng)用：研究現(xiàn)狀與趨勢[J].計算機學(xué)報，2013，36（3）：582-598.

[4] FOPING F S， DOKAS I M， FEEHAN J， et al. A new hybrid schema-sharing technique for multitenant applications[C]. Fourth IEEE International Conference on Digital Information Management， ICDIM 2009， November 1-4，2009， University of Michigan， Ann Arbor， Michigan，USA.2009：1-6.

[5] 張軍，詹志輝.計算智能[M].北京：國防工業(yè)出版社，1999：53-71.

[6] 周明，孫樹棟.計算智能[M].北京：清華大學(xué)出版社，2009.

[7] 陳華根，吳健生，王家林，等.模擬退火算法中關(guān)鍵參數(shù)的研究[J].同濟大學(xué)學(xué)報：自然科學(xué)版，2004，32（6）：802-805.

[8] 劉洪，侯向.模擬退火算法中關(guān)鍵參數(shù)的研究[J].計算機工程與科學(xué)，2008，30（10）：55-57.

[9] BELOGLAZOV A， BUYYA R. Optimal online deterministic algorithms and adaptive heuristics for energy and performance efficient dynamic consolidation of virtual machines in Cloud data centers[J]. Concurrency & Computation Practice & Experience，2012，24（13）：1397-1420.

[10] HIRAI T， MASUYAMA H， KASAHARA S， et al. Performance analysis of large-scale parallel-distributed processing with backup tasks for cloud computing[J].Journal of Industrial & Management Optimization，2014，10（1）：113-129.

[11] CALHEIROS R N， RANJAN R， BELOGLAZOV A， et al.Cloud Simulation： a toolkit for modeling and simulation of cloud computing environments and evaluation of resource provisioning algorithms[J].Software Practice & Experience，2011，41（1）：23-50.

（責(zé)任編輯：杜能鋼）