云計算中基于NSGA II的虛擬資源調度算法

方錦明

（義烏工商職業技術學院 機電信息分院，浙江 義烏322000）

0 引 言

Luis M.Vaquero學者在研究了20種云計算的定義后，給出了一個云計算的定義：云計算是一種大規模的易用的可訪問的虛擬資源 （如硬件、平臺和／或服務）池［1－4］。由此可知，虛擬性［5］在云計算中扮演了一個核心角色。然而，在云計算環境中，虛擬資源的調度問題也凸顯出來。虛擬資源的調度是指，按照一定的規則合理地將用戶申請的虛擬資源映射到相應的物理資源。一個好的調度器應該能夠均勻地將虛擬資源映射到物理資源上，然而，由于請求的虛擬資源的差異性和物理資源的異構性，該問題是一個難解問題。

在現在的已經實現的云計算調度系統上，一般都是采用簡單的策略實現。如EC2［6］使用按購買分配，VMware［7］按照CPU和內存的使用動態分配，NimBus［8］和 Eucalyptus［9］采用靜態貪婪策略和隨機選擇，oVirt［10］采用手工分配模式，OpenNebula［11］采用需要／排序動態分配的策略。簡單的調度策略來進行調度已經很難滿足日益增長的云計算的規模，因此不少學者開始研究這個問題。如Ravi Iyer［12］研究了虛擬資源間對物理資源的競爭所導致的性能下降，并提出了一種有效的模型來預測這種下降并在此基礎上提出了一種虛擬機管理模型；墨爾本大學的學者［13］提出了一個InterGrid系統來管理不同云系統間虛擬資源的遷移問題；國內學者田冠華等［14］提出了一種基于失效規則的資源動態提供策略，能有效提高動態提供節點資源的可靠性。

本文通過對虛擬資源調度過程的分析，將虛擬資源的調度過程抽象為具有CPU，內存，和帶寬等屬性的節點的匹配過程，分析了該問題的難解性，將其轉換為具有負載均衡的多目標優化問題，采用多目標優化算法來對虛擬資源進行調度。與具體的虛擬資源調度的實現相比，該調度模型更能反映云計算中虛擬資源調度的復雜性，同時不同于簡單的調度策略，采用多目標優化算法進行調度，能使得云計算中虛擬資源的調度更加合理。通過實驗驗證了本文提出的模型的合理性并驗證了使用多目標優化算法求解該問題的合理性。

1 虛擬資源調度的建模

不同于網格計算等其他分布式計算平臺，云計算中一個核心就是虛擬化。圖1是云計算與其他分布式計算平臺的差異。簡單地講，虛擬資源就是通過虛擬化技術將物理資源抽象為同一的虛擬資源。使用虛擬資源的優點有：

圖1 云計算與其他分布式平臺的差異

（1）可用性：在共享的分布式環境中，每個用戶的需求是不一樣的，在沒有對資源虛擬的情況下，當一個用戶占用了一個物理資源時，其他的用戶只有等待，而該用戶使用結束時，其他用戶又不得不重新配置自己的環境。當資源被虛擬化后，不僅不同的用戶可以同時使用相同的資源，而且每個用戶只需配置自己的環境一次。

（2）安全性：在虛擬環境中，每個用戶的程序相互隔離，當一個用戶程序出現崩潰以后，不會影響到其他用戶程序的運行；同時，每個用戶在虛擬環境中，其權限受到限制，對用戶的數據更加安全。在虛擬環境中，用戶可以隨時暫停，保存，恢復程序的運行。當由于配置錯誤等其他原因導致環境崩潰后，可以通過回滾的方式將環境恢復到正確的狀態。

（3）遷移性：當由于設備更新換代或者其他原因需要將程序遷移到新的環境中時，虛擬資源的配置可以很容易遷移到其他平臺上。

虛擬資源的優點導致了虛擬化技術的蓬勃發展，然而，將虛擬資源均衡地調度到物理資源上成為一個難點。因為每個用戶對虛擬資源的需求不同，而且物理資源也具有差異性。本文首先對虛擬資源的調度進行建模并證明其難解性。

虛擬資源的調度是將虛擬資源合理地映射到物理資源上。在云計算的實際環境中，一個虛擬資源可以抽象為一個具有一定屬性的節點。如一個具有cpu屬性，內存屬性和帶寬屬性的虛擬資源可以抽象為v（c，m，b），其中，c為cpu屬性，m為內存屬性，b為帶寬屬性。同理一個物理資源也可以抽象為p（c，m，b）。如表1所示。

表1 抽象后的虛擬資源及物理資源

在此基礎上，本文提出如下定義：

定義1 虛擬資源的調度是將將虛擬資源映射到物理資源上的一個方案，對應于虛擬資源vi（cvi，mvi，bvi），vi＝1，2，… ，m，和物理資源pi（cpi，mpi，bpi），pi＝ 1，2，… ，n，一個調度可以由m個物理資源組成的排列L（pi1，pi2，…，pim）來表示，此時，虛擬資源cv1被調度到物理資源pi1，虛擬資源cv2被調度到物理資源pi2等。

定理1 采用窮舉算法進行求解，虛擬資源的調度是難解問題。

證明：采用窮舉算法對云計算環境中的虛擬問題進行求解，則，對于v1有n個選擇，v2有n個選擇，…，vm有n個選擇，因此對于排列L有nm種，因此該算法的時間復雜度是O（nm），由NP問題的定義知，該問題是難解問題。

2 基于NSGA II的虛擬資源調度算法

在前面討論的基礎上，本文針對虛擬資源的調度問題，提出采用多目標優化算法進行求解，下面分別介紹多目標優化算法的主要組成部分：編碼、優化函數和搜索算法。

2.1 編 碼

由定義1知道，虛擬資源的調度是尋找一個調度序列，設虛擬資源的編號為vi＝1，2，…，m，物理資源的編號為pi＝1，2，…，n。本文采用序列編號作為編碼方式，因此對需要調度的虛擬資源進行排序設為 （v1，v2，…，vm），然后按照排序對虛擬資源進行調度，設調度序列為 （va1，va2，…，vam），其中，vai∈｛pi｝，則調度方法為，對應于vi，i＝1，2，…，m，其映射的物理資源為vai。算法中的編碼方式為（va1，va2，…，vam）。

2.2 優化函數

評價一個調度算法的好壞，主要是看該算法給出的調度方法是否符合負載均衡的要求，因此本文借鑒數學上方差的思想，對資源分布的均勻性進行量化，提出了針對不同屬性的均勻分布策略。

對于一個給定的編碼 （va1，va2，…，vam）有：（1）cpu屬性的均衡度

因此，cpu的均衡度為

同理，可得：

（2）內存屬性的均衡度

（3）帶寬屬性的均勻性

2.3 搜索算法

本文使用NSGA II［15］對問題求解。NSGA II是多目標優化算法中的經典算法，其思想與遺傳算法類似，不同的是在個體選擇過程中首先按照Pareto支配的概念進行排序同時計算個體的擁擠度，然后按照非支配優先，擁擠度較小的原則選擇個體。Pareto支配是指：設求解目標函數的最小值，則對于兩個個體，若所有的目標有：A （B）＜＝B（A）且A不等于B，則稱A （B）支配B （A），反之，則稱A、B互不支配。NSGA II能一次求解多個目標，但是，非支配排序是一個非常耗時的過程，為改善算法的求解性能，受文獻［16］的啟發，本文提出了如下基于樹的非支配求解算法來加快算法的求解速度。

首先對種群按照第一個目標進行排序，然后對每一個個體賦一個唯一的編號，設1，2，…，n。因此編號小的個體一定不會被編號大的個體所支配。然后采用二叉樹構造法構建一棵非支配樹。最后采用算法1獲取非支配解集。

算法1：獲取非支配解集

遍歷樹Tree獲得非支配解集F

逐個將Tree及其左子樹壓入第一層非支配解集F1；

將F1壓入F；

循環如果F中的個體數＜小于樹節點個體的一半

對于Fi－1中的每一個個體p

對于pi＝p.right；pi！＝null；pi＝pi.left

若pi不被Fi中的個體所支配

將pi添加到Fi；

否則

將pi添加到集合Left；

對于每個pi屬于Left

若pi不被Fi中的個體所支配

將pi添加到Fi；

若pi支配Fi中的某個個體qi

將qi添加到Left；

程序結束

算法的整體流程圖如圖2所示。首先隨機生成包含n個基因的種群P1，同時選擇交叉，變異生成下一代種群Q1；然后，將一棵空樹和節點集PiUQi作為參數輸入到算法1，返回一棵樹，對該樹按算法2進行遍歷得到排序后的集合，同時對最后一個集合進行擁擠度的計算；最后按照非支配優先，擁擠度較小的原則選擇個體，即：若A支配B，則選擇A，若A，B互不支配，則選擇擁擠度較小的那個個體。

圖2中，選擇交叉采用錦標賽選擇，兩點交叉，即，隨機選擇兩個個體，并選擇其中較優的個體作為父個體p1，同樣的方法選擇父個體p2，然后隨機生成兩個交叉點c1，c2，將p1從c1到c2的基因片段與p2從c1到c2的基因片段交換，生成子個體u1，u2。變異是對每個個體每一位按照變異因子Pc進行變異，即：若隨機數小于變異因子，則隨機生成一個基因位替換原來的基因。算法中采用基于樹的非支配排序算法進行排序，然后參照文獻 ［15］計算擁擠度，即：對于每一個目標，非支配個體按照該目標排序，對于第一個和最后一個個體擁擠度為最小，其他個體則是相鄰兩個個體的距離倒數。

圖2 算法的整體流程

3 實驗及結果分析

實驗的主要目的有：①驗證NSGA II算法的可行性；②在不同資源數和不同資源比例下對比NSGA II與隨機調度算法，靜態調度算法及排序匹配算法。

3.1 實驗設置及對比算法的描述

本文實驗Java語言編程實現。算法的具體參數設置如下：種群個數：48，最大迭代次數：1000，交叉因子：0.9，變異因子：1／l，其中l為基因長度。本文對比了3種簡單的調度算法：隨機調度算法，靜態調度算法和排序匹配算法。對于虛擬資源集V，物理資源集P，3種算法簡述如下：

（1）隨機調度算法：隨機給出一個調度方案L（a1，…，am）；

（2）靜態調度算法：調度方案為L （a1，… ，am），其中，ai＝i%n；

（3）排序匹配算法：該算法的主要思想是：對于一個要分配的資源，尋找與其最接近的物理資源作為分配策略。即：對于某個虛擬資源vi（cvi，mvi，bvi）和物理資源pi（cpi，mpi，bpi），pi＝1，2，… ，n，其計算公式如下：ai＝min｛pi｝，pi＝1，2，… ，n。此時有：min｛｜cpi－cvi｜＋｜mpi－mvi｜＋｜bpi－bvi｜｝。

3.2 對本文示例的求解

對第二節的實例進行求解，以驗證本文模型的正確性和NSGA II求解該問題的可行性以及對比其他算法的優勢。限于篇幅，表2給出了使用NSGA II算法對第二節實例求解的前8個非支配解的求解情況。從表中可以看出NSGA II可以通過一次求解獲取多個不同的解。因此，本文采用3種策略來選擇最終解：cpu策略、內存策略、帶寬策略、均衡策略，實際使用中可以根據不同的需要進行選擇。cpu策略是指：在所有解中選擇cpu最均衡的解。內存和帶寬策略亦類似。均衡策略是指：對于一組非支配解，選擇目標函數之和最小的解。

表2 使用NSGA II求解的非支配解集分布情況

表3給出不同策略下的求解結果，注意，隨機算法、靜態算法和排序算法不能按照相應的策略給出不同的解。

表3 NSGA II算法對本文實例求解結果及與其他算法的對比

從表3中可以看出幾種屬性間相互影響，對于一個給定的問題，幾乎不存在唯一最優解。同時，NSGA II給出了多個解，用戶可以按照自己的要求選擇不同的解，而簡單的求解算法則無法達到這樣的要求。簡單地可以看到，NSGAII給出的解幾乎全面優于其他算法。

3.3 不同資源比下的比較

為了更詳細地比較NSGA II與其他算法的求解結果，了解在不同資源映射情況下NSGA II的解的情況，本文對多個資源分配進行求解。在云計算環境中，虛擬資源個數與物理資源個數比代表了資源的緊張程度。如：虛擬資源個數與物理資源個數的比例0.2，那么，此時有大量的物理資源被閑置，此種情況下，調度的均衡性變的不是非常重要；反正，若比例為1.2，則表明物理資源非常緊張，調度的好壞，直接影響著系統的均衡性和吞吐量。為全面了解算法的求解情況，本文對比例為 ［0.2－1.2］的虛擬資源調度進行求解。

實驗中，隨機生成個數為 ［100－1000］的物理資源，然后按照不同的比值生成虛擬資源。物理資源和虛擬資源的各個屬性隨機生成。CPU取值為 ［100～2000］，內存的取值為 ［10～4000］，帶寬的取值為 ［1～100］。這樣的資源取值可以充分代表異構的物理資源的復雜性及虛擬任務的多樣性。

圖3－圖5顯示了在均衡策略下算法運行100次后的平均結果。3張圖分別表示cpu，內存和帶寬的均衡性。從圖中可以看出，NSGA II算法要全面優于其他算法。而隨機算法和固定算法的均衡度接近，排序算法的均衡度最差。這是因為，排序算法是按照匹配度進行的，這樣會導致某個匹配的機器負載較重，資源分配失去平衡性。

為從直觀的數值上比較各個算法的均衡度，表4給出了各個算法在不同資源比下的各個均衡度的平均值及NSGA II相比其他算法的均衡度提高的倍數。從表中可以看出，在均衡策略下，NSGA II各個數值都要優于其他算法的結果。

表4 各個算法的平均值及NSGA II相對于其他算法提高的倍數

4 結束語

本文對云計算環境下的虛擬資源調度問題進行了建模，提出將虛擬資源和物理資源抽象為具有一定屬性的節點的匹配過程。采用NSGA II算法對該問題進行求解，同時改進了NSGA II的非支配排序過程。最后通過實驗對比了NSGA II算法和其他3種基于簡單策略的調度算法。實驗表明，NSGA II可以用來求解云計算環境下的虛擬資源調度問題，一次求解給出多個候選解，為用戶采用不同的調度策略進行調度提供了可能性。同時，實驗中給出了在均衡策略下與其他3種簡單的調度算法的對比，結果表明，本文提出的基于NSGA II的調度算法能進行更好地調度。

［1］Armbrust Michael，Fox Armando，Griffith Rean，et al.A view of cloud computing ［J］.Communications of the ACM，2010，53 （4）：50－58.

［2］WANG Jiajun，LU Zhihui，WU Jie，et al.Cloud computing technology development analysis and applications discussion［J］.Computer Engineering and Design，2010，31 （20）：4405－4409（in Chinese）.［王佳雋，呂智慧，吳杰，等.云計算計算發展分析及其應用探討 ［J］.計算機工程與設計，2010，31 （20）：4405－4409.］

［3］Amazon.Amazon EC2 ［EB／OL］.http：／／www.amazon.com／ec2，2011.

［4］Luis M Vaquero，Luis Rodero Merino，Juan Caceres，et al.A break in the clouds：Towards a cloud definition ［J］.ACM Sigcomm，2009，39 （1）：50－55.

［5］Mendel Rosenblum，Tal Carfinkel.Virtual machine monitors：Current technology and future trends computer ［J］.Computer，2005，38 （5）：39－47.

［6］Ostermann Simon，Iosup Alexandria，Yigitbasi Nezih，et al.A performance analysis of EC2cloud computing services for scientific computing ［J］.Cloud Computing，2010，34 （4）：115－131.

［7］VMware Inc.VMware VCloud initiative ［EB／OL］.http：／／www.vmware.com／technology／cloud－computing.html，2011.

［8］WANG Lizhe，Laszewski Von Gregor.Scientific cloud computing：Early definition and experience［C］.Dalian：10th IEEE International Conference on High Performance Computing and Communications，2008：825－830.

［9］Nurmi Daniel，Wolski Rich，Grzegorczyk Chris.The eucalyptus open－source cloud－computing system ［C］. Washington：IEEE Computer Society，2009：1－8.

［10］Redhet Inc.oVirt.［EB／OL］.http：／／ovirt.org，2011.

［11］Borja Sotomayor，Rubén S Montero，Ignacio M Llorente，et al.Virtual infrastructure management in private and hybrid clouds［J］.Internet Computing IEEE，2009，13 （5）：14－22.

［12］Ravi Iyer，Ramesh Illikkal，Omesh Tickoo，et al.VM3：Measuring modeling and managing VM shared resources ［J］.Computer Networks，2009，53 （17）：2873－2887.

［13］Alexandre Di Costanzo，Marcos Dias De Assuncao，Rajkumar Buyya.Harnessing cloud technologies for a virtualized ［J］.Distributed Computing Infrastructure，2009，13 （5）：24－33.

［14］TIAN Guanhua，MENG Dan，ZHAN Jianfeng.Reliable resource provision policy for cloud computing ［J］.Chinese Journal of Computer，2010，33 （10）：1859－1872 （in Chinese）［田冠華，孟丹，詹劍鋒.云計算環境下基于失效規則的資源動態提供策略 ［J］.計算機學報，2010，33 （10）：1859－1872.］

［15］LI Hui，ZHANG Qingfu.Multiobjective optimization problems with complicated pareto sets MOEA／D and NSGA－II［J］.IEEE Transactions on Evolutionary Computation，2009，13（2）：284－302.

［16］SHI Chuan，YAN Zhenyu，SHI Zhongzhi，et al.A fast multi－objective evolutionary algorithm based on a tree structure［J］.Applied Soft Computing，2010，10 （2）：468－480.