基于K?means和蝙蝠算法的云計算虛擬機智能調(diào)度
2016-04-12 00:00:00王焱
現(xiàn)代電子技術 2016年21期
摘 要： 針對云計算虛擬機調(diào)度中存在的資源分配不均衡問題，提出了一種基于K?means和蝙蝠算法的云計算虛擬機智能調(diào)度方法。該方法充分考慮物理節(jié)點空閑資源和虛擬機所需資源的互補性，以物理節(jié)點作為初始聚類中心，使用資源的相關性定義二者的距離，利用蝙蝠算法的全局尋優(yōu)能力迭代尋優(yōu)，達到合理調(diào)度虛擬機的目的。模擬實驗仿真的結果表明，該方法在降低物理節(jié)點數(shù)量和提高資源利用率方面具有一定的優(yōu)勢，是一種可行的方法。
關鍵詞： K?means； 蝙蝠算法； 云計算； 虛擬機； 調(diào)度
中圖分類號： TN911?34； TP391 文獻標識碼： A 文章編號： 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 引 言
云計算是一種新型的商業(yè)計算模式，是分布式處理、并行處理和網(wǎng)絡計算的拓展和延伸，已成為工業(yè)界和學術界的研究熱點。云計算的本質(zhì)是以虛擬化技術為基礎，實現(xiàn)數(shù)據(jù)共享和服務共享。云平臺通過虛擬機的方式，通過高速的互聯(lián)網(wǎng)互連，形成虛擬資源池。虛擬機調(diào)度問題是云計算的關鍵技術之一，主要實現(xiàn)將虛擬機有效映射到相應的物理機上，達到物理機的負載均衡，有效利用現(xiàn)有資源。由于虛擬機需求量與物理集群的異構，可行部署空間增大，使云計算虛擬機調(diào)度成為一個NP?hard問題。本文主要基于K?means和蝙蝠混合算法研究了云計算虛擬機調(diào)度問題，實現(xiàn)了資源的高效平衡分配。
1 相關研究
云計算中虛擬機調(diào)度策略對云系統(tǒng)的性能具有很大的影響，能夠提高資源的利用率，最大化滿足用戶的需求。目前已有不少學者對云計算的虛擬機調(diào)度機制進行了研究。文獻[1]提出了一種基于多屬性層次分析的虛擬機部署與調(diào)度策略，該算法將虛擬機按資源特點進行分類量化，根據(jù)量化后的權向量和服務器資源的使用記錄，實現(xiàn)虛擬機的調(diào)度。文獻[2]在分組遺傳算法的基礎上，提出了基于多維資源協(xié)同聚合的虛擬機調(diào)度策略，對均衡資源分配具有一定的優(yōu)勢。文獻[3]提出了云計算的改進的credit調(diào)度算法，根據(jù)空閑率、緩存等因素選擇與其相關的任務，能提高緩存效率和增加延遲敏感型任務的響應速度。文獻[4]提出基于能耗比例模型的虛擬機調(diào)度算法，并采用“最近最小能耗比例優(yōu)先”的策略進行調(diào)度，提高了云系統(tǒng)的能效。文獻[5]提出了基于改進NSGA Ⅱ的虛擬機調(diào)度算法，將該模型的求解轉化為一個多目標優(yōu)化問題，在任務執(zhí)行時間、負載均衡和能量消耗方面具有一定的進步。本文在以上研究的基礎上提出基于K?means和蝙蝠混合算法的云計算虛擬機調(diào)度方法，將虛擬機分配到與其資源互補的物理機上，充分利用物理機上的資源，達到最優(yōu)化目標。
2 蝙蝠算法和K均值算法
2.1 蝙蝠算法
蝙蝠算法是劍橋大學學者Xin?She Yang于2010年提出的一種新型優(yōu)化算法，主要是受自然界中的蝙蝠搜尋、捕食行為啟發(fā)形成的新型優(yōu)化算法，每個優(yōu)化問題的解是搜索可行空間的一個蝙蝠[6?8]。
（1） 蝙蝠的運動
蝙蝠算法在[d]維空間中定義了蝙蝠的位置和速度的變化情況，蝙蝠[i]在[t]時刻的位置和速度的變化通過下列公式描述：
[fi=fmin+（fmax-fmin）β] （1）
[Vti=Vt-1i+（Xti-X*）fi] （2）
[Xti=Xt-1i+Vti] （3）
式中：[β]表示在[0，1]之間的隨機變量；[x*]表示當前全局最優(yōu)位置；[fi]為頻率大小，根據(jù)要搜索的范圍大小確定其最大值和最小值。局部搜索時，蝙蝠位置的更新公式為：
[Xnew=XOLD+εAt] （4）
式中：[ε∈[-1，1]]是隨機數(shù)；[At]是所有蝙蝠在同一時間段的平均音量。
（2） 音量和脈沖發(fā)生率
當蝙蝠[i]找到目標時，音量[Ai]就會降低，同時脈沖發(fā)生率[ri]就會增加，其更新公式如下：
[At+1i=αAti] （5）
[rti=r0i[1-exp（-γt）]] （6）
式中：[α]和[γ]為常量，為簡化變化過程通常取[α=γ=0.9。]
2.2 K?means算法
K?means算法以[K]為參數(shù)，把[n]個對象分為[K]個類，通過距離大小衡量聚類結果的優(yōu)劣，聚類的距離越近，說明其相似度就越大，聚類效果越好[9?10]。聚類結果中在同一類中的對象相似度較高，而不同聚類中的對象相似度較小，其基本思想是在數(shù)據(jù)空間中任意選擇[K]個數(shù)據(jù)對象作為初始聚類中心，根據(jù)其余數(shù)據(jù)與對應聚類中心的相似度進行聚類劃分，然后再計算新的聚類中心，不斷重復執(zhí)行這一聚類過程，即可得到最終類別劃分結果。聚類結果實際上是尋找數(shù)據(jù)集的劃分過程，各聚類本身盡可能的緊湊，而各聚類之間盡可能的分開。
3 云計算虛擬機智能調(diào)度模型
云計算數(shù)據(jù)中心有[m]個物理節(jié)點，有[n]個虛擬機發(fā)送調(diào)度請求，每個物理節(jié)點的資源向量分為已使用的資源向量和空閑的資源向量，物量節(jié)點上的資源是多維的，包括CPU、內(nèi)存、帶寬和I/O等，每個物理節(jié)點已使用的資源等于分配到該節(jié)點的虛擬機資源之和[11?12]。設虛擬機集合為[V=VMi1≤i≤n，]物理節(jié)點集合為[M=PMj1≤j≤m}，]虛擬機調(diào)度的目的是利用最少的物理節(jié)點獲得最大的資源利用率，并且保證物理節(jié)點分配的資源利用率不超過其資源的最大容量，其可以建立如下的目標和約束條件：
（1） 目標函數(shù)：
[mini=1muiui=1，PMj是活躍節(jié)點0，PMj是非活躍節(jié)點] （7）
[max1ki=1kui，j] （8）
約束條件：[ikqi，k≤jcj；1≤i≤n；1≤j≤m]
式中：[ui]表示第[i]個物理節(jié)點是否使用；[ui， j]表示物理節(jié)點在第[j]維度的利用率；[qi，k]表示虛擬機對資源[k]的需求量。
4 基于K?means和蝙蝠算法的虛擬機調(diào)度方法
4.1 調(diào)度思想
本文提出的虛擬機調(diào)度方法的基本思想是將每個虛擬機分配到距離最近的物理節(jié)點上，通過多次迭代，每個虛擬機都與所在的物理節(jié)點最近。在本文中虛擬機與物理節(jié)點的距離用資源相關系數(shù)表示，相關系數(shù)越小，說明虛擬機所需資源與物理節(jié)點擁有的資源之間具有更多的互補，在空閑資源滿足條件的情況下，將其分配到相關系數(shù)小的物理節(jié)點，有利于更充分地利用資源。虛擬資源與物理節(jié)點之間的相關性采用皮爾遜相關系數(shù)表示，取值范圍為[-1，1]：
[ρV，P=i=1t（Vi-V）（Pi-P）i=1t（Vi-V）2i=1t（Pi-P）2] （9）
將虛擬機與物理節(jié)點的距離定義為：
[dV，P=1+ρV，P2] （10）
則虛擬機與物理節(jié)點的距離取值范圍為[0，1]。本文將虛擬機到不活躍物理節(jié)點的距離定義為最大，將其取為1，表示只有當虛擬機無法放置時才分配到新物理節(jié)點。
4.2 蝙蝠編碼規(guī)則
蝙蝠算法采用實數(shù)據(jù)編碼，一個編碼對應一個可行解。本文采用[m]個物理節(jié)點為初始聚類中心，這樣聚類對應的物理節(jié)點限定了聚類的大小，簡化了對資源的考慮，并且確定的聚類減少了遷移的次數(shù)，使資源的分配更加穩(wěn)定。
每個蝙蝠由[m]個聚類中心構成。設當前虛擬機分為[m]類，每個數(shù)據(jù)為[d]維特征，用于實數(shù)進行編碼，以K均值聚類中心作為尋優(yōu)變量，每個可行解是由[m]個聚類中心構成，由于解的維數(shù)是[d]維，這里可行解的位置是[m×d]維向量，可行解的編碼示例，其結構如下：
[[Z11][Z12]…[Z1d]………[Zk1][Zk2] …[Zkd]]
其中[Zm1，Zm2，…，Zmd]代表第[m]類的[d]維聚類中心。
4.3 虛擬機調(diào)度步驟
（1） 蝙蝠初始化：給定含有[n]個虛擬機對象的數(shù)據(jù)集[T]和物理節(jié)點數(shù)[m，]基于蝙蝠算法的K?means聚類方法，將每類的聚類中心作為蝙蝠的位置編碼，反復進行多次，生成[N]個初始蝙蝠。以上聚類中心方法執(zhí)行多次，生成含有[n]個蝙蝠的初始化種群[XI（I=1，2，…，n），]其目標函數(shù)為[f（X），][X=（x1，x2，…，xd）T]。
（2） 初始化蝙蝠種群的速度、脈沖頻率、脈沖響度和脈沖發(fā)射速率。
（3） 根據(jù)適應度公式計算每個蝙蝠的適應度值，保留最優(yōu)解，并利用速度和位置公式對其他蝙蝠進行更新。
（4） 產(chǎn)生一個隨機數(shù)rand1，if （rand1>[ri]），則對當前群體中最佳蝙蝠位置進行隨機擾動得到替換當前蝙蝠的位置。
