基于K?means和蝙蝠算法的云計(jì)算虛擬機(jī)智能調(diào)度

摘 要： 針對云計(jì)算虛擬機(jī)調(diào)度中存在的資源分配不均衡問題，提出了一種基于K?means和蝙蝠算法的云計(jì)算虛擬機(jī)智能調(diào)度方法。該方法充分考慮物理節(jié)點(diǎn)空閑資源和虛擬機(jī)所需資源的互補(bǔ)性，以物理節(jié)點(diǎn)作為初始聚類中心，使用資源的相關(guān)性定義二者的距離，利用蝙蝠算法的全局尋優(yōu)能力迭代尋優(yōu)，達(dá)到合理調(diào)度虛擬機(jī)的目的。模擬實(shí)驗(yàn)仿真的結(jié)果表明，該方法在降低物理節(jié)點(diǎn)數(shù)量和提高資源利用率方面具有一定的優(yōu)勢，是一種可行的方法。

關(guān)鍵詞： K?means； 蝙蝠算法； 云計(jì)算； 虛擬機(jī)； 調(diào)度

中圖分類號(hào)： TN911?34； TP391 文獻(xiàn)標(biāo)識(shí)碼： A 文章編號(hào)： 1004?373X（2016）21?0021?03

Cloud computing virtual machine intelligent scheduling

based on K?means and bat algorithm

WANG Yan

（Department of Education， Hanjiang Normal University， Shiyan 442000， China）

Abstract： To solve the resource allocation imbalance problem existing in cloud computing virtual machine scheduling， a cloud computing virtual machine intelligent scheduling method based on K?means and bat algorithm is proposed. The method fully considers the complementarity of the physical node idle resource and the resource needed by virtual machine， selects the physical node as the initial clustering center， and uses the resource correlation to define the distance between them. The global searching ability of bat algorithm is used for iterative optimization to achieve the goal of reasonable virtual machine scheduling. The scheduling method was simulated. The experiment results show that the method has certain advantages in reducing the quantity of physical nodes and improving the resource utilization， and is an effective method.

Keywords： K?means； bat algorithm； cloud computing； virtual machine； scheduling

0 引 言

云計(jì)算是一種新型的商業(yè)計(jì)算模式，是分布式處理、并行處理和網(wǎng)絡(luò)計(jì)算的拓展和延伸，已成為工業(yè)界和學(xué)術(shù)界的研究熱點(diǎn)。云計(jì)算的本質(zhì)是以虛擬化技術(shù)為基礎(chǔ)，實(shí)現(xiàn)數(shù)據(jù)共享和服務(wù)共享。云平臺(tái)通過虛擬機(jī)的方式，通過高速的互聯(lián)網(wǎng)互連，形成虛擬資源池。虛擬機(jī)調(diào)度問題是云計(jì)算的關(guān)鍵技術(shù)之一，主要實(shí)現(xiàn)將虛擬機(jī)有效映射到相應(yīng)的物理機(jī)上，達(dá)到物理機(jī)的負(fù)載均衡，有效利用現(xiàn)有資源。由于虛擬機(jī)需求量與物理集群的異構(gòu)，可行部署空間增大，使云計(jì)算虛擬機(jī)調(diào)度成為一個(gè)NP?hard問題。本文主要基于K?means和蝙蝠混合算法研究了云計(jì)算虛擬機(jī)調(diào)度問題，實(shí)現(xiàn)了資源的高效平衡分配。

1 相關(guān)研究

云計(jì)算中虛擬機(jī)調(diào)度策略對云系統(tǒng)的性能具有很大的影響，能夠提高資源的利用率，最大化滿足用戶的需求。目前已有不少學(xué)者對云計(jì)算的虛擬機(jī)調(diào)度機(jī)制進(jìn)行了研究。文獻(xiàn)[1]提出了一種基于多屬性層次分析的虛擬機(jī)部署與調(diào)度策略，該算法將虛擬機(jī)按資源特點(diǎn)進(jìn)行分類量化，根據(jù)量化后的權(quán)向量和服務(wù)器資源的使用記錄，實(shí)現(xiàn)虛擬機(jī)的調(diào)度。文獻(xiàn)[2]在分組遺傳算法的基礎(chǔ)上，提出了基于多維資源協(xié)同聚合的虛擬機(jī)調(diào)度策略，對均衡資源分配具有一定的優(yōu)勢。文獻(xiàn)[3]提出了云計(jì)算的改進(jìn)的credit調(diào)度算法，根據(jù)空閑率、緩存等因素選擇與其相關(guān)的任務(wù)，能提高緩存效率和增加延遲敏感型任務(wù)的響應(yīng)速度。文獻(xiàn)[4]提出基于能耗比例模型的虛擬機(jī)調(diào)度算法，并采用“最近最小能耗比例優(yōu)先”的策略進(jìn)行調(diào)度，提高了云系統(tǒng)的能效。文獻(xiàn)[5]提出了基于改進(jìn)NSGA Ⅱ的虛擬機(jī)調(diào)度算法，將該模型的求解轉(zhuǎn)化為一個(gè)多目標(biāo)優(yōu)化問題，在任務(wù)執(zhí)行時(shí)間、負(fù)載均衡和能量消耗方面具有一定的進(jìn)步。本文在以上研究的基礎(chǔ)上提出基于K?means和蝙蝠混合算法的云計(jì)算虛擬機(jī)調(diào)度方法，將虛擬機(jī)分配到與其資源互補(bǔ)的物理機(jī)上，充分利用物理機(jī)上的資源，達(dá)到最優(yōu)化目標(biāo)。

2 蝙蝠算法和K均值算法

2.1 蝙蝠算法

蝙蝠算法是劍橋大學(xué)學(xué)者Xin?She Yang于2010年提出的一種新型優(yōu)化算法，主要是受自然界中的蝙蝠搜尋、捕食行為啟發(fā)形成的新型優(yōu)化算法，每個(gè)優(yōu)化問題的解是搜索可行空間的一個(gè)蝙蝠[6?8]。

（1） 蝙蝠的運(yùn)動(dòng)

蝙蝠算法在[d]維空間中定義了蝙蝠的位置和速度的變化情況，蝙蝠[i]在[t]時(shí)刻的位置和速度的變化通過下列公式描述：

[fi=fmin+（fmax-fmin）β] （1）

[Vti=Vt-1i+（Xti-X*）fi] （2）

[Xti=Xt-1i+Vti] （3）

式中：[β]表示在[0，1]之間的隨機(jī)變量；[x*]表示當(dāng)前全局最優(yōu)位置；[fi]為頻率大小，根據(jù)要搜索的范圍大小確定其最大值和最小值。局部搜索時(shí)，蝙蝠位置的更新公式為：

[Xnew=XOLD+εAt] （4）

式中：[ε∈[-1，1]]是隨機(jī)數(shù)；[At]是所有蝙蝠在同一時(shí)間段的平均音量。

（2） 音量和脈沖發(fā)生率

當(dāng)蝙蝠[i]找到目標(biāo)時(shí)，音量[Ai]就會(huì)降低，同時(shí)脈沖發(fā)生率[ri]就會(huì)增加，其更新公式如下：

[At+1i=αAti] （5）

[rti=r0i[1-exp（-γt）]] （6）

式中：[α]和[γ]為常量，為簡化變化過程通常取[α=γ=0.9。]

2.2 K?means算法

K?means算法以[K]為參數(shù)，把[n]個(gè)對象分為[K]個(gè)類，通過距離大小衡量聚類結(jié)果的優(yōu)劣，聚類的距離越近，說明其相似度就越大，聚類效果越好[9?10]。聚類結(jié)果中在同一類中的對象相似度較高，而不同聚類中的對象相似度較小，其基本思想是在數(shù)據(jù)空間中任意選擇[K]個(gè)數(shù)據(jù)對象作為初始聚類中心，根據(jù)其余數(shù)據(jù)與對應(yīng)聚類中心的相似度進(jìn)行聚類劃分，然后再計(jì)算新的聚類中心，不斷重復(fù)執(zhí)行這一聚類過程，即可得到最終類別劃分結(jié)果。聚類結(jié)果實(shí)際上是尋找數(shù)據(jù)集的劃分過程，各聚類本身盡可能的緊湊，而各聚類之間盡可能的分開。

3 云計(jì)算虛擬機(jī)智能調(diào)度模型

云計(jì)算數(shù)據(jù)中心有[m]個(gè)物理節(jié)點(diǎn)，有[n]個(gè)虛擬機(jī)發(fā)送調(diào)度請求，每個(gè)物理節(jié)點(diǎn)的資源向量分為已使用的資源向量和空閑的資源向量，物量節(jié)點(diǎn)上的資源是多維的，包括CPU、內(nèi)存、帶寬和I/O等，每個(gè)物理節(jié)點(diǎn)已使用的資源等于分配到該節(jié)點(diǎn)的虛擬機(jī)資源之和[11?12]。設(shè)虛擬機(jī)集合為[V=VMi1≤i≤n，]物理節(jié)點(diǎn)集合為[M=PMj1≤j≤m}，]虛擬機(jī)調(diào)度的目的是利用最少的物理節(jié)點(diǎn)獲得最大的資源利用率，并且保證物理節(jié)點(diǎn)分配的資源利用率不超過其資源的最大容量，其可以建立如下的目標(biāo)和約束條件：

（1） 目標(biāo)函數(shù)：

[mini=1muiui=1，PMj是活躍節(jié)點(diǎn)0，PMj是非活躍節(jié)點(diǎn)] （7）

[max1ki=1kui，j] （8）

約束條件：[ikqi，k≤jcj；1≤i≤n；1≤j≤m]

式中：[ui]表示第[i]個(gè)物理節(jié)點(diǎn)是否使用；[ui， j]表示物理節(jié)點(diǎn)在第[j]維度的利用率；[qi，k]表示虛擬機(jī)對資源[k]的需求量。

4 基于K?means和蝙蝠算法的虛擬機(jī)調(diào)度方法

4.1 調(diào)度思想

本文提出的虛擬機(jī)調(diào)度方法的基本思想是將每個(gè)虛擬機(jī)分配到距離最近的物理節(jié)點(diǎn)上，通過多次迭代，每個(gè)虛擬機(jī)都與所在的物理節(jié)點(diǎn)最近。在本文中虛擬機(jī)與物理節(jié)點(diǎn)的距離用資源相關(guān)系數(shù)表示，相關(guān)系數(shù)越小，說明虛擬機(jī)所需資源與物理節(jié)點(diǎn)擁有的資源之間具有更多的互補(bǔ)，在空閑資源滿足條件的情況下，將其分配到相關(guān)系數(shù)小的物理節(jié)點(diǎn)，有利于更充分地利用資源。虛擬資源與物理節(jié)點(diǎn)之間的相關(guān)性采用皮爾遜相關(guān)系數(shù)表示，取值范圍為[-1，1]：

[ρV，P=i=1t（Vi-V）（Pi-P）i=1t（Vi-V）2i=1t（Pi-P）2] （9）

將虛擬機(jī)與物理節(jié)點(diǎn)的距離定義為：

[dV，P=1+ρV，P2] （10）

則虛擬機(jī)與物理節(jié)點(diǎn)的距離取值范圍為[0，1]。本文將虛擬機(jī)到不活躍物理節(jié)點(diǎn)的距離定義為最大，將其取為1，表示只有當(dāng)虛擬機(jī)無法放置時(shí)才分配到新物理節(jié)點(diǎn)。

4.2 蝙蝠編碼規(guī)則

蝙蝠算法采用實(shí)數(shù)據(jù)編碼，一個(gè)編碼對應(yīng)一個(gè)可行解。本文采用[m]個(gè)物理節(jié)點(diǎn)為初始聚類中心，這樣聚類對應(yīng)的物理節(jié)點(diǎn)限定了聚類的大小，簡化了對資源的考慮，并且確定的聚類減少了遷移的次數(shù)，使資源的分配更加穩(wěn)定。

每個(gè)蝙蝠由[m]個(gè)聚類中心構(gòu)成。設(shè)當(dāng)前虛擬機(jī)分為[m]類，每個(gè)數(shù)據(jù)為[d]維特征，用于實(shí)數(shù)進(jìn)行編碼，以K均值聚類中心作為尋優(yōu)變量，每個(gè)可行解是由[m]個(gè)聚類中心構(gòu)成，由于解的維數(shù)是[d]維，這里可行解的位置是[m×d]維向量，可行解的編碼示例，其結(jié)構(gòu)如下：

[[Z11][Z12]…[Z1d]………[Zk1][Zk2] …[Zkd]]

其中[Zm1，Zm2，…，Zmd]代表第[m]類的[d]維聚類中心。

4.3 虛擬機(jī)調(diào)度步驟

（1） 蝙蝠初始化：給定含有[n]個(gè)虛擬機(jī)對象的數(shù)據(jù)集[T]和物理節(jié)點(diǎn)數(shù)[m，]基于蝙蝠算法的K?means聚類方法，將每類的聚類中心作為蝙蝠的位置編碼，反復(fù)進(jìn)行多次，生成[N]個(gè)初始蝙蝠。以上聚類中心方法執(zhí)行多次，生成含有[n]個(gè)蝙蝠的初始化種群[XI（I=1，2，…，n），]其目標(biāo)函數(shù)為[f（X），][X=（x1，x2，…，xd）T]。

（2） 初始化蝙蝠種群的速度、脈沖頻率、脈沖響度和脈沖發(fā)射速率。

（3） 根據(jù)適應(yīng)度公式計(jì)算每個(gè)蝙蝠的適應(yīng)度值，保留最優(yōu)解，并利用速度和位置公式對其他蝙蝠進(jìn)行更新。

（4） 產(chǎn)生一個(gè)隨機(jī)數(shù)rand1，if （rand1>[ri]），則對當(dāng)前群體中最佳蝙蝠位置進(jìn)行隨機(jī)擾動(dòng)得到替換當(dāng)前蝙蝠的位置。

（5） 通過隨意飛行產(chǎn)生新解，產(chǎn)生隨機(jī)數(shù)rand2，if （rand2[

（6） 利用K?means方法對蝙蝠位置進(jìn)行優(yōu)化，按照最近鄰近法原則確定對應(yīng)的聚類劃分，并重新計(jì)算聚類中心，更新蝙蝠的適應(yīng)度，根據(jù)適應(yīng)度函數(shù)排列蝙蝠，找到當(dāng)前最佳位置，如果達(dá)到結(jié)束條件（滿足條件的位置或最大迭代次數(shù)）則聚類完成，轉(zhuǎn)到步驟（7），否則轉(zhuǎn)到步驟（3）。

（7） 輸出最優(yōu)的蝙蝠位置對應(yīng)的數(shù)據(jù)聚類結(jié)果。

5 仿真實(shí)驗(yàn)

采用CloudSim 3.0云平臺(tái)軟件對本文提出的調(diào)度方法進(jìn)行模擬仿真，CloudSim是澳大利亞墨爾本大學(xué)的網(wǎng)格實(shí)驗(yàn)室和Gridbus項(xiàng)目宣布推出的云計(jì)算仿真軟件。本仿真實(shí)驗(yàn)將虛擬機(jī)分別設(shè)置為100，200，300，400，500，每個(gè)實(shí)例取10次運(yùn)算的平均值，將所需物理節(jié)點(diǎn)數(shù)量和系統(tǒng)資源綜合利用率兩方面與K?means調(diào)度方法進(jìn)行比較。

（1） 物理節(jié)點(diǎn)數(shù)據(jù)對比

物理節(jié)點(diǎn)使用數(shù)量的對比情況見圖1，可以看出，本文調(diào)度方法的物量節(jié)點(diǎn)的數(shù)量比K?means調(diào)度方法平均降低12%左右，有效地減少了資金投入，物理機(jī)節(jié)點(diǎn)的能耗也降低，使數(shù)據(jù)中心具有高密度、低成本的優(yōu)點(diǎn)。主要原因是本文調(diào)度方法通過聚類方法將虛擬機(jī)分配到服務(wù)器中，并且將虛擬機(jī)到不活躍物理節(jié)點(diǎn)的距離設(shè)置為最大，表示只有當(dāng)虛擬機(jī)無法放置時(shí)才分配到新的物理節(jié)點(diǎn)，這樣有效地提高了數(shù)據(jù)中心物理節(jié)點(diǎn)的分配密度，降低了物理節(jié)點(diǎn)的節(jié)點(diǎn)數(shù)量。

（2） 系統(tǒng)資源綜合利用率比較

系統(tǒng)資源綜合利用率對比見圖2，可以看出本文調(diào)度方法系統(tǒng)資源綜合利用率比K?means調(diào)度方法平均提高了11%左右，有效地提高了資源的綜合利用率。主要是因?yàn)楸疚恼{(diào)度方法在調(diào)度時(shí)考慮了虛擬機(jī)與服務(wù)器資源的互補(bǔ)性，有效地防止了一種資源過于飽和導(dǎo)致其他資源不能使用的情況，通過資源互補(bǔ)分配虛擬機(jī)有效地提高了資源的綜合利用率。

6 結(jié) 語

在開放的云計(jì)算環(huán)境下，合理的虛擬機(jī)調(diào)度策略有利于提高資源的綜合利用率，并有效地降低能耗。本文提出了一種云計(jì)算環(huán)境中使用的虛擬機(jī)智能調(diào)度方法，考慮了虛擬機(jī)與服務(wù)器資源的互補(bǔ)性，降低了云服務(wù)提供者的運(yùn)營成本，仿真實(shí)驗(yàn)表明該方法在節(jié)省物理節(jié)點(diǎn)和提高綜合資源利用率方面都取得了較好的效果，是一種可行的方法。

參考文獻(xiàn)

[1] 莊威，桂小林，林建材，等.云環(huán)境下基于多屬性層次分析的虛擬機(jī)部署與調(diào)度策略[J].西安交通大學(xué)學(xué)報(bào)，2013，47（2）：28?32.

[2] 袁愛平，萬燦軍.云環(huán)境下基于改進(jìn)遺傳算法的虛擬機(jī)調(diào)度策略[J].計(jì)算機(jī)應(yīng)用，2014，34（2）：357?359.

[3] 暴錫文.一種云計(jì)算環(huán)境下基于Xen的虛擬機(jī)調(diào)度機(jī)制[J].計(jì)算機(jī)測量與控制，2014，22（10）：3381?3384.

[4] 肖鵬，劉洞波，屈喜龍.云計(jì)算中基于能耗比例模型的虛擬機(jī)調(diào)度算法[J].電子學(xué)報(bào)，2015，43（2）：305?310.

[5] 殷小龍，李君，萬明祥.云環(huán)境下基于改進(jìn)NSGAII的虛擬機(jī)調(diào)度算法[J].計(jì)算機(jī)技術(shù)與發(fā)展，2014，24（8）：71?75.

[6] 李煜，馬良.新型全局優(yōu)化蝙蝠算法[J].計(jì)算機(jī)科學(xué)，2013，40（9）：225?228.

[7] 金偉健，王春枝.基于蝙蝠算法的云計(jì)算資源分配研究[J].計(jì)算機(jī)應(yīng)用研究，2015，32（4）：1184?1187.

[8] 全雪姣，孟凡榮，王志曉.對K?mean初始聚類中心的優(yōu)化[J].計(jì)算機(jī)工程與設(shè)計(jì)，2011（8）：165?167.

[9] 吳夙慧，成穎，鄭彥寧，等.K?means算法研究綜述[J].現(xiàn)代圖書情報(bào)技術(shù)，2011，31（5）：30?35.

[10] 宋旭東，朱文輝，邱占芝.大數(shù)據(jù)K?Means聚類挖掘優(yōu)化算法[J].大連交通大學(xué)學(xué)報(bào)，2015，36（3）：91?94.

[11] 李喬，鄭嘯.云計(jì)算研究現(xiàn)狀綜述[J].計(jì)算機(jī)科學(xué)，2011，38（4）：32?37.

[12] 徐文忠，彭志平，左敬龍.基于遺傳算法的云計(jì)算資源調(diào)度策略研究[J].計(jì)算機(jī)測量與控制，2015，23（5）：1653?1656.