基于聚類蟻群算法的虛擬機資源分配算法研究

蔣 茜，何 嘉

（成都信息工程學(xué)院 計算機學(xué)院，四川 成都610225）

0 引言

云計算是建設(shè)智慧城市的重要支撐技術(shù)，它以互聯(lián)網(wǎng)為媒介，博取分布式結(jié)構(gòu)、網(wǎng)格技術(shù)和并行計算概念的長處，與以往的服務(wù)模式相比，更具有商業(yè)價值.[1-2]云計算的關(guān)鍵技術(shù)有實現(xiàn)硬件資源抽象的虛擬化技術(shù)、海量數(shù)據(jù)的存儲管理技術(shù)、SOA框架與新型Web服務(wù)模式、MapReduce等并行編程模型.[3]

云計算環(huán)境下的虛擬機資源分配技術(shù)是云計算得以大規(guī)模應(yīng)用和提供系統(tǒng)性能、兼顧節(jié)能減排的關(guān)鍵技術(shù).[4-5]通過深入系統(tǒng)學(xué)習(xí)和研究而提出的先進的資源調(diào)度技術(shù)，對于提高學(xué)校、政府、研究機構(gòu)和企業(yè)硬件資源的有效利用率、節(jié)約水電等能源、擴大資源共享范圍和降低運營成本都具有重要意義.

1 云環(huán)境下的虛擬機資源管理

1960年前后，IBM大型計算機系統(tǒng)引入虛擬化概念.[6]隨著虛擬化的發(fā)展，在云計算環(huán)境中，虛擬化的產(chǎn)物除了虛擬機、虛擬網(wǎng)絡(luò)等概念，還可以代表云計算環(huán)境中各種硬件資源的抽象.

虛擬化技術(shù)可以將底層的CPU、內(nèi)存、網(wǎng)絡(luò)帶寬等硬件資源進行抽象，使得云服務(wù)使用者無須顧及底層的差異性和兼容性，可以統(tǒng)一管理利舊或其他方式得到的各種不同的底層硬件資源.[7]在虛擬化技術(shù)的幫助下，云計算環(huán)境中的用戶可以通過網(wǎng)絡(luò)使用任意終端獲取來自于“云”中的各種云服務(wù)，不需要了解應(yīng)用運行的具體位置，云服務(wù)就像供應(yīng)日常生活中水電的服務(wù)一樣.[8]

本文使用的虛擬機資源分配的調(diào)度參考結(jié)構(gòu)如圖1所示.[9-10]

（1）用戶任務(wù)請求：以Internet（比如客戶端程序、云服務(wù)商的主頁）為入口，用戶提交作業(yè)，發(fā)起任務(wù)請求；

（2）總調(diào)度管理：調(diào)度中心Controller依據(jù)用戶的身份特征（比如地理位置等）和請求的業(yè)務(wù)特征（數(shù)量和質(zhì)量要求），將請求提交給合適的服務(wù)器域的任務(wù)管理程序Master節(jié)點；

（3）各區(qū)Master節(jié)點調(diào)度資源：Master節(jié)點執(zhí)行某種調(diào)度算法將可用的實際資源信息反饋，對該資源請求分配；

（4）分配資源：Master節(jié)點執(zhí)行調(diào)度，用戶任務(wù)開始使用虛擬機資源；

圖1 云環(huán)境下的資源調(diào)度體系

（5）后臺優(yōu)化：調(diào)度中心在后臺同時執(zhí)行優(yōu)化操作，將不同數(shù)據(jù)中心的資源按照優(yōu)化目標(biāo)函數(shù)和空閑及配置等信息排序優(yōu)化，以備后來者使用.

2 云環(huán)境下虛擬機資源分配策略

2.1 問題建模

用戶提交任務(wù)，任務(wù)被放置在虛擬機上，虛擬機共享物理機資源，由此可將虛擬化資源調(diào)度分為兩個階段：① 微觀上的調(diào)度重點在于物理機的CPU、內(nèi)存和帶寬資源在虛擬機之間使用共享；②宏觀上的調(diào)度為虛擬機和物理機之間的合理映射，涉及負(fù)載均衡等原則.本文將虛擬機資源分配的過程抽象為如圖2所示.

圖2 虛擬機調(diào)度的抽象模型

可將調(diào)度函數(shù)描述為如下的四元表：大的調(diào)度長度

其中：Pi（i＝1，2，…，m）為處理單元；tj（j＝1，2，…，n）為分配到Pi上的任務(wù)；ST（tj，Pi）為tj在Pi上的開始時間；FT（tj，Pi）為tj在Pi上的結(jié)束時間.最小化最是任務(wù)調(diào)度的目標(biāo).

用矢量裝箱問題（vector bin-packing problem）來求解虛擬機的分配調(diào)度，則將虛擬機當(dāng)做物品，裝入物理服務(wù)器（箱子）.[11-13]

用遺傳算法模型來描述該問題：把解看成個體，個體的染色體N為虛擬機的個數(shù)，物理服務(wù)器的個數(shù)為M，將第i個元素的值取為h，解釋為“物理服務(wù)器h上運行著第i個虛擬機”.[14]通過改變兩個染色體的基因片段進行組合雜交，變異則是虛擬機從當(dāng)前物理機隨機放置到另一臺物理機上的過程.[15-16]

基因算法和簡單裝箱算法各有優(yōu)劣，而蟻群算法[17-19]有魯棒性、分布式并行計算等更合適于搜尋虛擬機節(jié)點的優(yōu)點.

2.2 算法描述

基于聚類和蟻群算法的虛擬機資源分配算法，主要包括4個關(guān)鍵步驟.

2.2.1 物理服務(wù)器分組

將服務(wù)器按地理位置分組，每一組設(shè)置一個Master節(jié)點.從用戶任務(wù)提交的總調(diào)度中心Controller節(jié)點出發(fā)，遍歷每個Master節(jié)點，按照其距離對每個區(qū)域進行編號，用 D＝D1，D2，…，Ds｛｝表示s個地區(qū)的集合2.2.2 用戶任務(wù)聚類

假設(shè)用戶任務(wù)之間相互獨立，用T＝T1，T2，…，Tn｛｝表示n個任務(wù)的集合，用一維向量 Ti＝ tif，tir，tih，tik，tit

｛｝來表示任務(wù)Ti，分別表示完成任務(wù)所需要CPU計算能力、內(nèi)存容量、硬盤大小、帶寬容量和預(yù)計完成所需時間.

在對用戶任務(wù)計算任務(wù)相似度時，選用歐式距離計算，只考慮用戶預(yù)計完成所需時間屬性tit，故任務(wù)Ti和Tj的相似度公式為：

利用K-means聚類算法，將分組后的任務(wù)提交給Controller節(jié)點，由Controller根據(jù)任務(wù)所在的物理位置，分發(fā)給對應(yīng)服務(wù)器域的Master節(jié)點.

2.2.3 利用蟻群算法進行虛擬機分配

（1）信息素定義

我們用虛擬機的硬件資源來衡量一個節(jié)點的信息素，包括CPU個數(shù)m及處理能力ρ（MPIS）

，內(nèi)存容量r，硬盤大小h，帶寬b.并按以下公式為每個參數(shù)設(shè)置一個閾值，并初始化各種信息素.

CPU計算能力的信息素：

內(nèi)存的信息素：

硬盤的信息素：

帶寬的信息素：

各個信息素的帶權(quán)和就是節(jié)點i上的信息素值，公式如下所示.

（2）信息素修改

將螞蟻發(fā)現(xiàn)的可用的虛擬機節(jié)點稱為有效節(jié)點.當(dāng)有新任務(wù)分配到有效節(jié)點上時，CPU利用率會增大，信息素值反而變小.本文便要增加完成任務(wù)的節(jié)點的信息素濃度，減少任務(wù)失敗的節(jié)點的信息素.

τit（）為節(jié)點i在時刻t的信息素濃度，t1為新任務(wù)到達時間，t2為任務(wù)運行成功或失敗的時刻.

（3）虛擬機完成任務(wù)所需時間的估計

云環(huán)境下，Master趨于將任務(wù)分配給效率最高的節(jié)點，而確定其是否為有效節(jié)點，則需要給新任務(wù)的預(yù)計執(zhí)行時間設(shè)置一個閾值，當(dāng)其預(yù)計執(zhí)行時間小于或等于這個閾值，這個節(jié)點才是.用以下時間模型來預(yù)測新任務(wù)在節(jié)點上的所需執(zhí)行時間.

（4）螞蟻選擇下一個虛擬機節(jié)點的概率

按照公式，螞蟻選擇概率最大的下一個虛擬機節(jié)點：

其中：Aj＝ETjnpredict（Jpredict（t））；Ns為螞蟻路徑節(jié)點集；k為i的相鄰節(jié)點；α，β表示τj和Aj的重要性.

2.2.4 相鄰服務(wù)器域間任務(wù)調(diào)度

在服務(wù)器域 Dp內(nèi)，即 CPU、內(nèi)存、硬盤、帶寬任意一項使用完后，就表示物理服務(wù)器資源不足.Dp域內(nèi)Master節(jié)點即與相鄰距離最近的Dq域內(nèi)Master節(jié)點通信，將剩余任務(wù)交由區(qū)域Dq的Master節(jié)點進行分配.當(dāng)mmax＝∑i?Nsmi，就從該區(qū)域Dp出發(fā)，尋找相鄰距離最近的Dq，將剩余任務(wù)交由區(qū)域Dq的Master節(jié)點進行分配.

3 算法實施及評價

設(shè)用戶提交的主要是計算任務(wù)，算法中的a，b，c，d分別表示了虛擬機的CPU，內(nèi)存、外存及帶寬的重要性，將a，b，c，d的值分別設(shè)為0.4，0.3，0.2，0.1.α，β為調(diào)節(jié)因子，分別代表了信息素和任務(wù)預(yù)計執(zhí)行時間的重要性.m是一個參數(shù)，其決定了產(chǎn)生螞蟻的數(shù)量.我們將通過實驗來獲得α，β，m的最優(yōu)組合.μ，μ1，μ2為調(diào)節(jié)信息素改變的因子，設(shè)置為0.2，μ2在任務(wù)執(zhí)行失敗時為-0.2.ρ為時間估計的調(diào)節(jié)因子，設(shè)為0.4.

隨機生成100-400個用戶任務(wù)預(yù)計完成所需時間屬性值在區(qū)間[1000，11000]（單位：毫秒）內(nèi)的計算任務(wù)，虛擬機節(jié)點設(shè)置為100個，處理能力為200MIPS-400MIPS，處理器為單／雙核，內(nèi)存為100M-200M，帶寬為1M／s-2M／s，外存為1G-2G.物理機的聚類算法設(shè)其初始分組為2，實驗中暫不涉及跨區(qū)域的調(diào)度.

通過多次實驗，參數(shù)最終設(shè)置為α＝2，β＝1，m＝1.5，對100個任務(wù)構(gòu)成的作業(yè)，普通蟻群算法、隨機分配算法與基于聚類和蟻群算法的虛擬機資源分配算法（新算法）在任務(wù)分配時間方面的比較如表1.

表1 任務(wù)分配時間變化統(tǒng)計

當(dāng)α＝1，β＝2，m＝2.5時，三種算法在任務(wù)分配時間、任務(wù)執(zhí)行時間跨度方面的比較如圖3、圖4所示.

圖3 資源分配算法的任務(wù)分配時間

由圖3、圖4可以看出在任務(wù)分配時間上，新算法優(yōu)于蟻群算法和隨機算法，但在執(zhí)行時間跨度方面性能卻差不多.

圖4 資源分配算法的任務(wù)執(zhí)行時間跨度

4 小結(jié)

虛擬機的分配要保證虛擬機的性能，也要使運營商利潤最大化.基于聚類蟻群算法的虛擬機資源調(diào)度分配算法可增加可用虛擬機節(jié)點的發(fā)現(xiàn)率，并兼顧算法的收斂性.通過實驗，將新算法與隨機分配算法、普通蟻群分配算法對比，其任務(wù)分配時間較短，任務(wù)執(zhí)行時間跨度體現(xiàn)出降勢，能更好地保證用戶任務(wù)按時完成，滿足服務(wù)等級協(xié)議（SLA）.

[1]Armbrust M.Above the Clouds：ABerkeley View of Cloud Computing[R].2009.

[2]《虛擬化與云計算》小組.虛擬化與云計算[M].北京：電子工業(yè)出版社，2009：135.

[3]張 兵.云計算的起源、應(yīng)用與發(fā)展方向[J].信息與電腦：理論版，2011（9）：37-39.

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

[5]Genaud S，Gossa J.Cost-wait Trade-offs in Clint-side Recource Provisioning with Elastic Clouds[C].New york：IEEE，2011：1-16.

[6]Introduction Cloud Computing architecture White Paper，1st Edition，June 2009.

[7]魯 松.計算機虛擬化技術(shù)及應(yīng)用[M].北京：機械工業(yè)出版社，2008：357.

[8]Garfinkel S.An Evaluation of Amazon’s Grid Computing Services：Ec2，S3 and SQS，Technical Report，TR-08-07.

[9]田文洪，趙 勇.云計算-資源調(diào)度管理[M].北京：國防工業(yè)出版社，2007：195.

[10]Barroso LA，Dean J，Holzle U.Web search for a planet：The Google cluster architecture[J].IEEE Micro，2003（2）：22-28.

[11]Karve A.T，Kimbrel，G.Pacifici，et al.Dynamic placement for clustered web applications[C].Edinburgh：UK，2006（6）：23-26.

[12]Chandra Chekuri，Sanjeev Khanna.On multi-dimensional packing problems[J].SIAM，2004（4）：837-851.

[13]Leinberger，W.G.Karypis，K.Vipin.Multi-Capacity Bin Packing Algorithms with Applications to Job Scheduling under Multiple Constraints[C].New York：IEEE，1999（9）：21-24.

[14]Qi Zhang，Eren Gurses，Raouf Boutaba.Dynamic Resource Allocation for Spot Markets in Clouds[J].IT Convergence Engineering，2010（8）：987-1012.

[15]Mark S.David S，F(xiàn)rederic V，et al.Resource Allocation Algorithmsfor Virtualized Service Hosting Platforms[J].Parallel and Distributed Computing，2010（9）：962-974.

[16]李建鋒，彭 艦.云計算環(huán)境下基于改進遺傳算法的任務(wù)調(diào)度算[J].計算機應(yīng)用，2010（1）：184-186.

[17]Dorigo M，Gambardella L M.Ant colony system：A cooperative learning approach to the travelingsalesman problem[C].New York：IEE，1997（1）：53-66.

[18]Lingyun Yang，Ian Foster，Jennifer M Schopf.Homeostatic andTendency-based CPU Load Predictions[J].Proceedings of IPDPS，2003（12）：1-9.

[19]王 剛，鐘志水，黃永青.基于蟻群遺傳算法的網(wǎng)格資源調(diào)度研究[J].計算機仿真，2009（4）：79-82.