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