基于K?means和蝙蝠算法的云計(jì)算虛擬機(jī)智能調(diào)度
2016-04-12 00:00:00王焱
現(xiàn)代電子技術(shù) 2016年21期
摘 要： 針對云計(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)前蝙蝠的位置。
