面向移動云計算的自適應虛擬機調度算法

韋傳講，莊 毅

(南京航空航天大學 計算機科學與技術學院， 南京 211106)

1 引 言

隨著無線網絡的快速發展，促使了諸如手機、筆記本和平板電腦之類的智能設備的發明，這樣的聯網技術和設備使得用戶可以移動，并可以隨時隨地訪問資源.因此，移動性已成為現代互聯網世界的主要特征.根據中國互聯網信息中心發布的報告，截止2018年底，我國網民數量大約為8.29億，其中大概有98.6%的網民是通過手機訪問互聯網(1)http://www.cnnic.net.cn/hlwfzyj/hlwxzbg/hlwtjbg/201902/t20190228_70645.htm..隨著互聯網技術的不斷發展，應用服務的種類變得多樣化，使得人們對移動設備的計算性能的需求也越來越高[1].

移動設備功能和性能需求的上升需要不斷突破本身的資源瓶頸，才能滿足人們的需求.然而，硬件的提升需要新材料新技術的突破.目前移動設備存在的難以解決的問題，包括移動設備的存儲有限，電池續航能力有限，設備的處理能力有限等，都需要新材料技術的突破，才能夠使移動設備的性能達到質的飛躍，而這些突破無法在短期實現[2].而云計算技術的出現，使得移動設備固有的缺點得以彌補.云平臺上有近乎無限的計算資源和存儲資源，能夠滿足移動終端的各種高性能計算，并提供給移動終端最優的云服務.

移動云計算技術結合了移動互聯網技術與傳統云計算技術，改善了移動設備固有的缺點.云平臺上的計算資源和存儲資源被認為幾乎是無限的，可以滿足移動設備的多種計算需求，使得移動設備獲得更好的云服務[3].移動云計算能夠支持多種移動設備執行豐富的移動應用，可以為用戶帶來豐富的產品體驗.同時，移動云計算也為移動網絡運營商和云服務提供商帶來了商業機會[4].移動云計算相較于傳統云計算而言，它是一種先進的移動計算技術，其利用各種云和網絡技術的統一彈性資源獲得不受限的功能、存儲和移動性，它弱化了移動終端硬件設備的限制，通過以太網或互聯網渠道隨時隨地地為大量的移動終端提供各種定制的云服務，而不用管其基于的終端平臺[5].此外，移動云計算還繼承了傳統云計算的一些優勢，如可伸縮性、支持多用戶以及安全服務[6].

移動云計算的日益普及和云中心數量與規模的不斷擴大，使得能源消耗成為云中心的最大的運營成本.關于能耗的數字統計隨處可見，根據《中國數據中心白皮書(2018年)》2顯示，截止2017年底全球數據中心共計44.4萬個，大約安裝了493.3萬架機架，部署至少5500萬臺服務器，預計2020年會部署安裝更多的機架和服務器，這些服務器消耗著越來越多的能源.因此世界上很多國家或組織已經在關注云數據中心高能耗的問題，并付諸行動.移動云計算在滿足云用戶不斷增長應用需求的同時，需要對工作負載和資源配置進行快速智能化和動態管理，從而實現能耗最小和效益最大化的運行模式.因此，很有必要研究相關算法以支持對移動云中心的資源管理，降低開銷，提高效率和可靠性.

本文針對移動云中心高能耗問題，從移動云中心資源調度的角度展開研究，設計目標函數，并建立虛擬機(Virtual Machine，VM)調度模型，最后提出VM調度算法以對模型進行求解.本文的主要研究工作及貢獻如下：

1)從CPU、內存、網絡帶寬和磁盤4個維度，將最小化數據中心能耗、最大化數據中心效用以及最小化服務器數量作為目標，建立了基于多目標優化的VM調度模型VMSM-EUN.該模型具有能耗低、效用高和調度結果優等特點.

2)根據粒子群進化的不同階段，分別設計了適用于加速因子與慣性因子的動態自適應調整策略，可加速粒子群的求解過程并獲得更優解.

3)為驗證VM調度模型VMSM-EUN的有效性，設計了基于改進粒子群的自適應參數調整的VM調度算法VMSA-IPSO來求解該模型.并通過仿真實驗驗證了本文算法與模型的有效性，并通過對比實驗驗證了算法的優越性.

2 相關研究

在移動云計算的眾多研究中，通過對虛擬資源的合理調度來降低數據中心的能耗一直是一個研究熱點.國內外研究學者從多個方向提出了提高云數據中心的資源利用率和能源效率的方案，包括新穎的資源調度方案、數據中心服務器散熱和控溫方案、服務器調壓變頻方案以及高效負載均衡器等.其中資源調度方案對數據中心的能耗影響尤為突出，但設計更快速、更節能的資源調度算法被認為是一個挑戰.

目前，許多解決方案采用的分配方法是通過在任意給定時間將單個VM分配給主機的方式，來解決VM分配問題.這種方法獨立地規定了VM的資源需求，以確保每個主機具有足夠的容量來執行工作負載.但是，這種方法會降低資源利用效率.此外，許多已有的VM部署方案還采用了一種根據當前的CPU資源需求優化資源使用的部署策略.但應用程序的工作負載總是會隨著時間的推移而波動，這對VM的動態調度是一個重大的挑戰.最近的一些研究表明，通過分析、預測CPU資源和云網絡流量也能為云中心有效管理資源提供幫助，確保資源高效合理的分配.為了解決VM調度問題，已有許多專家學者展開了研究，主要包括以降低能耗為目標和以收益最大化為目標.

以降低能耗為目標，對移動云數據中心的資源進行管理和調度，提高云中心資源的利用率和能源效率.Li xiang等人將數據中心的能耗分為計算能耗和冷卻能耗，他們精心設計了熱能耗模型來分析數據中心的氣流和服務器CPU的溫度分布，提出了一種能夠最大限度地降低云數據中心總能耗的整體VM調度算法[7].文獻[8]提出了一種通過對服務器的狀態進行管理來減少能耗的方法.將空閑服務器節電狀態與輸入作業負載進行映射，考慮了資源動態變化情況、工作服務器不同負載時的功耗和空閑服務器休眠狀態及轉換時的功耗等情況，設計了啟發式調度器來對VM進行調度，以使得VM映射中功耗增量最小.文獻[9]提出一種能量感知VM調度方法，該方法考慮了數據中心的物理主機的異構帶寬，由功率感知算法和帶寬供應算法組成.Yibin Li等人在DVS技術的基礎上，提出了一種新的能量感知移動云動態資源調度算法[10]，在滿足嚴格的時間約束和應用的概率約束的前提下，可減少移動設備的總能耗.文獻[11]提出了一個混合云框架H(2)http://www.caict.ac.cn/kxyj/qwfb/bps/201810/t20181016_186900.htm.和集成資源管理器，該框架和管理器能夠管理具有多種沙箱化和虛擬化技術的云基礎設施，可有效地平衡工作負載的能源、性能和成本效益.Jang等人提出了一種新的虛擬CPU調度方案，以提高云應用的I/O性能并減少能耗.該方案設計了一個評估函數，該評估函數通過觀察每個虛擬CPU 的的資源消耗量來評估VM的任務特性.基于評價函數，該調度方案自適應地控制VM在處理I/O請求時的優先級，以實現公平分配.實驗結果表明，該方案提高了VM的響應速度和I/O帶寬，并降低能耗[12].Ting Yang等人提出了一種新穎的工作感知VM布局[13]，以減少數據中心的能耗，并盡可能多地滿足網絡QoS要求.并通過實驗驗證了其方案可在節省能源消耗的同時減小通信延遲.文獻[14]提出了一種VM整合的自適應節能調度算法，該算法的主要思想是最大限度的利用服務器，將數據中心的VM部署在盡可能少的服務器上，以最小化能耗.該算法通過自組織和概率論方法來阻止過載服務器接受VM請求，以確保良好的QoS，并使用在線遷移來確保遷移過程的順利進行.實驗結果表明，該算法能降低數據中心能耗實現節能目標[14].

以收益最大化為目標，主要有基于機器學習算法、基于拍賣機制和博弈論的方法.文獻[15]提出了一種考慮云用戶和云服務提供商的雙激勵VM調度模型，該模型通過最大化VM請求的成功率和最小化組合成本實現對云用戶的激勵，并通過最小化利潤的公平性偏差實現對云服務提供商的激勵.上述的策略能使獲得更高的用戶滿意度，但是容易造成資源的浪費.Sharrukh Zaman等人針對現有云資源分配策略無法保證有效的分配和云提供商收入最大化的問題，設計了一種基于拍賣的動態VM分配機制，該機制在進行VM配置決策時考慮了用戶對VM的需求.實驗表明所提出的機制可以提高資源利用率和分配效率，并為云提供商帶來更高收益[16].Liu Xing等人提出了一種基于Stackellberg博弈模型的VM定價和分配方案，該方案考慮服務阻塞對用戶效用的影響，通過模型分析推導出最優定價的閉式表達式，并通過粒子群算法對VM靜態和動態調度進行最優定價搜索.實驗結果證明了該方案可以通過定價策略控制網絡阻塞，有效提高移動用戶和云提供商的實用性[17].文獻[18]對移動云環境下應用任務需求進行分析，設計了基于Stackelberg博弈的動態計算資源調度算法和博弈模型，仿真實驗表明該算法和模型能保證移動終端的體驗質量并最大化終端效用[18].

綜上所述，目前已有的云中心的VM調度方法雖然在一定程度上減少了云中心的能耗，但是仍然存在不足，一方面，當VM調度的數量很大時，現有的算法不能滿足調度的性能需求.另一方面，上述的VM調度算法在設計時考慮問題不夠全面，如僅考慮CPU能耗而不考慮其他部件的能耗問題.因此，本文在充分考慮了CPU、內存、網絡帶寬和磁盤4個維度，提出了面向能耗和效用的VM調度模型VMSM-EUN，并設計了VM調度算法VMSA-IPSO來求解該模型.

3 虛擬機調度模型

本節考慮服務器上的各種硬件資源，將VM調度模型看作“Packing Problem”.在VM調度問題中，需要把服務器看作背包，VM看作物品，在將物品放入背包時需要考慮物品的大小和背包的大小.“Packing Problem”需要一個多目標優化算法來進行求解.本文考慮VM調度的3個目標，設計了相應的函數，從而將背包問題轉換為帶約束的多目標優化問題.因此，我們需要設計目標函數，明確約束條件，建立VM調度模型.

3.1 相關定義

定義1.云中心描述.移動云中心所有的服務器用向量P={P1，…，Pi，…，Pn}表示；移動云中心所有的VM用向量V={V1，…，Vj，…，Vm}表示，其中n為移動云中心服務器數量，m為移動云中心VM數量.Pi={Pcpui，Prami，Phddi，Pneti，Pcosti}分別表示服務器Pi的CPU計算能力Pcpui、內存空間Prami、硬盤空間Phddi、網絡帶寬Pneti以及成本Pcosti；Vj={Vcpuj，Vramj，Vhddj，Vnetj，Rj}分別表示VM所需的CPU資源Vcpuj、內存空間Vramj、硬盤空間Vhddj、網絡帶寬Vnetj；VM效用Rj={Rj1，…，Rji，…，Rjn}，Rji表示VMVj分配到服務器Pi產生的效用值.

定義2.服務器的多維度負載度計算.采用加權和法，將服務器中各部件的能耗占比定義為能耗權重，再通過計算加權和得到服務器的多維度負載度.定義服務器Pi的多維度負載度FMDLi為式(1)：

FMDLi=ω1×Ucpui+ω2×Urami+ω3×Uhddi+ω4×Uneti

(1)

(2)

其中：Ucpui，Urami，Uhddi，Uneti分別代表服務器Pi的CPU、內存、硬盤和網絡帶寬利用率.ω1，ω2，ω3，ω4分別為CPU 能耗占比，內存部件能耗占比，硬盤部件能耗占比，網絡部件能耗占比.Pji∈{0，1}，Pji=1表示VMVj被部署到服務器Pi上運行，Pji=0表示VMVj未被部署到服務器Pi上運行.

定義3.虛擬機效用函數.VM的效用函數是一個線性函數，如式(3)所示.

(3)

式(3)中的αi、βi、γi和φi分別表示VM每個單位CPU、內存、網絡帶寬資源和硬盤資源的價格.Cj、Mj、Bj和Hj表示VMVj的CPU、內存、網絡帶寬和硬盤的資源配置大小.

定義4.服務器效用函數.一臺服務器的效用值為該服務器上所有VM產生的效用與該服務器的成本的差值，因此服務器的效用函數如式(4)所示.

(4)

云中心的效用為所有物理機的效用值之和，因此云中心的效用函數如式(5)所示.

(5)

3.2 約束條件

為找到VM和服務器之間的最佳映射方案，實現云中心的效益最大化和低能耗的目標，在進行VM調度時需要明確約束條件.下面給出VM調度模型需滿足的約束條件：

s.t

(6)

式(6)中第一個式子表示對于移動云數據中心中的任意一臺VM，在任意時刻它只能運行在某一臺服務器上運行；式(6)中其余的不等式表示一臺服務器所承載VM占用的資源總和小于等于其所擁有的資源.

3.3 目標函數

為實現移動云數據中心效益最大化和降低運行成本的目標，本小節根據上述定義與調度約束條件，設計了3個VM調度的目標函數，具體如下.

3.3.1 最小能耗

文獻[19]提出了一個新的服務器的能耗模型，并證明了服務器的能量消耗與CPU利用率呈線性關系.本文在該文獻提出的服務器能耗模型的基礎上進行優化，不是僅僅考慮CPU利用率而是將服務器的能耗與服務器的負載相聯系，考慮了CPU、內存、網絡帶寬和磁盤4個維度，提出了改進的服務器能耗模型.首先將服務器Pi的多維度負載度FMDLi進行歸一化處理，得到服務器的多維度負載率UMDLi，歸一化處理方法如式(7)所示.其中FminMDLi，FmaxMDLi表示優化周期[t1，t2]內服務器Pi的多維負載度的最小值和最大值.

(7)

改進的云服務器能耗模型，如式(8)-式(10)所示.

P(UMDLi(t))=c×Pmaxi+(1-c)×Pmaxi×UMDLi(t)

(8)

(9)

(10)

其中，式(8)將服務器的能耗與服務器的負載相聯系，考慮了CPU、內存、網絡帶寬和磁盤4個維度，而不是僅僅考慮CPU利用率.Pmaxi表示服務器Pi的多維負載率達到最高峰值時的最大功耗；UMDLi(t) 表示服務器Pi在t時刻的多維負載率.式(9)中Ei表示優化周期[t1，t2]內服務器Pi的能耗.式(10)中，E表示移動云中心所有服務器的能耗，單位為瓦特(W)，n表示移動云數據中心的服務器數量；Yi∈{0，1}表示服務器Pi是否處于激活狀態.Yi=1，表示服務器Pi處于激活狀態.Yi=0，表示服務器Pi處于關閉狀態.

3.3.2 最大效用

移動云計算中心的效用為全部VM效用和所有服務器成本的差，計算方法如式(11)所示.

(11)

式(11)中R表示移動云中心的總效用值；n表示移動云中心服務器總數；m表示云中心承載的VM總數；Rji表示在服務器Pi上運行VMVj產生的VM效用；Pcosti表示服務器Pi的使用成本.

3.3.3 最小服務器數

通常在虛擬資源調度的優化階段，為了進一步降低能耗，需要將資源利用率較低的服務器上的VM遷移到其它服務器上，并將該服務器設為休眠狀態，使得云中心可以運行較少的服務器來承載相同的負載，以進一步減少數據中心的能量消耗.服務器數計算方法如式(12)所示.

(12)

綜上所述，VM調度模型VMSM-EUN可以描述為：

(13)

(14)

(15)

s.t

(16)

4 基于改進粒子群的虛擬機調度算法

4.1 改進的粒子群優化算法

粒子群優化(Particle Swarm Optimization，PSO)算法是模擬鳥群尋找食物的集體行為而提出的一種基于群體智能的全局優化技術.PSO中成員粒子以一定的速度和加速度向更好的位置移動，每個粒子表示問題空間的解[8].

在PSO中，每一個粒子被認為是潛在的解決方案，每個粒子都與兩個向量相關聯，它們分別是速度向量v(t)=[v1，v2，…，vD] 和位置向量x(t)=[x1，x2，…，xD]，其中D為解空間的維度.在進化過程中改進的PSO算法的更新方程如式(17)、式(18)[20]所示，在PSO中所有粒子是根據當前局部最優解pbest和當前全局最優解gbest來更新自己的信息.

v(t+1)=ωv(t)+c1r1(pbest-x(t))+c2r2(gbest-x(t))

(17)

x(t+1)=x(t)+v(t+1)

(18)

其中，v為粒子速度，ω為慣性因子，c1、c2為加速因子，r1、r2為(0，1)上一致分布的隨機數.每一維上的粒子速度被限制在vmax(vmax>0) 內，如果某一維更新后的速度大于用戶給定的vmax，那么就設為vmax，即v(t+1)>vmax時，v(t+1)=vmax.如果某一維更新后的速度小于等于用戶給定的-vmax，那么就設為-vmax，即v(t+1)≤-vmax時，v(t+1)=-vmax.目前已有的研究對PSO進行了改進，典型工作有主要3個方面：YH Shi等人將慣性因子引入PSO，并證明了當慣性因子值較大時，全局尋優能力強，局部尋優能力弱；值較小反之[21].除慣性因子外，加速因子c1和c2也是PSO中的重要參數.權重因子包括慣性因子ω和加速因子c1、c2，使粒子保持著原有的運動狀態，并具有探索和開發的能力.在Kennedy的兩個極端情況下，實驗表明“僅社交”模型和“僅認知”模型中，兩種加速因子對于PSO的成功至關重要[22].Kennedy和Eberhart建議c1、c2固定值為2.0，這種配置已被許多研究人員采用[23].Suganthan證明了對于不同的問題，使用c1、c2的“ad hoc”值而不是固定值可以產生更好的性能[24].Ratnaweera等人提出了一種具有線性時變加速度系數(HPSO-TVAC)的PSO算法，在開始時設置較大的c1和較小的c2，并且在搜索期間逐漸反轉.在對比實驗中，HPSO-TVAC顯示出最佳的整體性能.這是由于時變c1和c2可以平衡全局搜索能力和局部搜索能力[25].由上所述可見，在粒子群尋優的過程中采用適合的慣性因子ω、加速因子c1和c2，將有助于提高PSO性能.因此我們在4.3小節中，將在粒子群求解過程中確定每一次迭代后粒子群所處的狀態，動態自適應的改變慣性因子ω和加速因子c1、c2的取值.

4.2 映射關系與編碼方式

為了將PSO算法用于求解VM調度問題，我們需要將粒子的編碼與現實問題對應，本文中粒子的位置、速度與現實中VM調度問題的映射關系如下所述.

圖1 編碼方式Fig.1 Encoding scheme

4.3 自適應參數調整

考慮PSO的特性，我們將粒子群求解過程中狀態變化與加速因子c1和c2的取值聯系在一起，自適應的調整c1和c2.并且將粒子群的進化因子f與慣性因子ω建立映射關系，使得ω的取值跟隨進化狀態的變化而變化.具體的自適應參數調整方法如下所述.

4.3.1 加速因子c1和c2的調整

參考文獻[26]： 設f為進化因子.將粒子群的狀態分類為：探索、開發、收斂和跳出4種狀態.在粒子群求解過程中通過計算進化因子f的數值大小來確定每一次迭代后粒子群所處的狀態，最后得出進化因子f與粒子群所處的狀態的模糊隸屬函數.模糊隸屬函數有交叉的區域，即存在一個f對應兩個函數值.我們稱這個區域為過渡期.在過渡期，粒子群可能處于兩種狀態中的任意一種.對于最終分類，可以使用“單例法”或“質心法”[27]兩種常用的去模糊技術中的任一種.本文使用單例法，因為它比質心法更有效，并且與去模糊規則表一起實現起來比較簡單.與大多數模糊邏輯方案類似，我們設計的去模糊規則表也涉及狀態和“狀態變化”變量.探索、開發、收斂和跳出4種狀態分別用S1、S2、S3和S4表示.根據參考文獻[26]，PSO序列S1?S2?S3?S4?S1?…反映了PSO過程中狀態的變化.模糊隸屬函數圖像的交叉區域分別為：S1與S2交叉區域、S2與S3交叉區域、S1與S4交叉區域.為了分類的穩定性即不過度的切換狀態指示符，設計了如表1所示的去模糊化規則表.表1中，F(f)表示模糊隸屬度，St-1表示前一個狀態，St表示當前狀態的選取結果.

在粒子群優化的狀態模糊分類后，我們將根據每一次迭代后粒子群所處的狀態，動態的改變加速因子c1和c2的取值.綜上所述，我們得到以下調整系數c1和c2的策略：

1)在探索狀態下增大c1和減小c2：在探索狀態下探索盡可能多的最佳值非常重要，增大c1和減小c2可以幫助粒子單獨探索并達到它們自己的歷史最佳位置，而不是圍繞當前可能與局部最優相關的最佳粒子.

表1 去模糊規則表Table 1 Fuzzy control rules

2)在開發狀態下略微增大c1并略微減小c2：在這種狀態下，粒子利用局部信息并聚集到每個粒子的歷史最佳位置所指示的可能的局部最佳位置.因此，緩慢增加c1并保持相對較大的值可以增強圍繞局部最好pbest的搜索和利用.與此同時，全局最佳粒子并不總是在此階段定位全局最優區域.因此，緩慢減少c2并保持較小值可以避免陷入局部最優.此外，在探索狀態之后和收斂狀態之前更可能發生開發狀態.因此，改變c1和c2的時間應該是從探索狀態略微改變到收斂狀態.

3)在收斂狀態下略微增大c1并略微增大c2：在收斂狀態下，群體似乎找到全局最優區域，因此，應增強c2的影響以將其他粒子引導到可能的全局最優區域.因此，應增大c2的值.另一方面，應減小c1的值以使群快速收斂，但是這種策略會過早地將這兩個參數飽和到它們的下限和上限.結果是群體將被當前最佳區域強烈吸引，導致過早收斂，如果當前最佳區域是局部最優，則是有害的.為避免這種情況，c1和c2都略有增加.略微增大兩個加速因子最終將具有與減小c1和增大c2相同的預期效果，因為它們的值將被限制到大約2.0，因為c1和c2之和的上限為4.0[23].當c1和c2的和大于4.0時，需要對c1和c2進行歸一化，歸一化處理方法如式(19)所示.

(19)

4)在跳出狀態下減小c1和增大c2：當全局最佳粒子跳出局部最佳位置并朝向更好的最佳狀態時，它可能遠離擁擠群集.一旦這個新區域被一個粒子找到，這顆粒子就會成為(可能是新的)領導者，其他粒子應該跟隨它并盡可能快地趨近這個新區域.較大的c2和相對較小的c1有助于實現這一目的.

4.3.2 慣性因子ω的調整

PSO中的慣性因子ω用于平衡全局和本地搜索功能.許多研究人員主張ω的值在探索狀態下應該很大而在開發狀態下應該很小.然而，純粹隨著時間減少ω并不一定正確.進化因子f與慣性權重ω具有一些特征，其中f在探索狀態期間也相對較大并且在收斂狀態下變得相對較小.因此，ω的取值應跟隨進化狀態的變化而變化，即令ω與f存在這樣的映射ω(f)：R+→R+.

(20)

在本文中，ω初始化為0.9.由于ω不一定隨時間單調變化，而是隨f單調變化，因此ω將適應以f為特征的搜索環境.在跳出或探索狀態下，較大f和ω將有利于全局搜索.相反，當f很小時，檢測到開發或收斂狀態，ω減小以有利于局部搜索.設計的自適應參數調整流程圖如圖2所示.

圖2 自適應參數調整流程圖Fig.2 Self-adaptive parameter adjustment flow chart

4.4 虛擬機調度算法

基于改進粒子群，我們設計了VM調度算法VMSA-IPSO，算法具體步驟如下：

Step1.定期收集連續到達的VM請求作為算法的輸入；

Step2.初始化.

Step2-1.根據VMSM-EUN模型中決策變量的個數，設置種群大小為N，最大迭代次數為Gen.

Step2-2.生成初始粒子群.根據VM請求以及服務器的各種資源約束，隨機生成N個可行VM部署方案，每一個解都是一個粒子，每個粒子都是由二維編碼方案編碼的，這些粒子構成了初始種群.粒子的初始位置由初始種群決定，粒子的初始速度由粒子的第一維狀態信息決定.

Step3.計算每個粒子到其他粒子的平均距離和進化因子f根據進化因子f的大小對粒子群的狀態進行評估，自適應的調整參數c1、c2和ω.

Step4.粒子群中為一個粒子，根據式(10)、式(11)和式(12)計算其目標函數的值.

Step5.對于每個粒子更新其當前最好位置pbest.

Step6.比較所有粒子的當前最好位置pbest，選出適應值最高的與當前全局最好位置gbest作比較，得出種群的全局最佳位置gbest.

Step7.根據式(17)更新種群中所有粒子的速度.

Step8.更新種群中所有粒子的位置.

Step8-1.根據式(18)更新粒子位置，此位置更新操作可能會丟失VM，將在后續步驟中重新部署丟失的VM.

Step8-2.刪除VM.上述位置更新操作可能導致VM部署在兩臺服務器上.因此，必須刪除重復的VM以確保部署方案的可行性.刪除方法是將二維編碼的本地位置設置為0，并將這些重復的VM一起刪除.同樣，這些被刪除的VM將在下一步重新部署.

Step8-3.重新部署被刪除的VM.要獲得更新后的可行解決方案，就必須將丟失或意外刪除的VM重新部署到服務器上.首先將當前處于激活狀態的服務器作為主機服務器，當所有處于激活狀態的服務器都無法放置VM時才會啟用新服務器.

Step9.根據更新后的粒子群，更新局部最優粒子和全局最優粒子的位置信息.

Step10.判斷是否達到最大迭代次數，若達到則輸出VM調度方案，否則重復步驟Step 3～Step 9.

圖3 基于改進粒子群的虛擬機調度算法偽代碼Fig.3 Pseudo code of the VM scheduling algorithm

基于改進粒子群的VM調度算法VMSA-IPSO的偽代碼，如圖3所示.

5 實驗與結果分析

本文基于多目標優化算法建立了VM調度模型VMSM-EUN，將最小化數據中心能耗、最大化數據中心效用以及最小化服務器數作為目標，設計并實現了基于改進粒子群的VM調度算法VMSA-IPSO來求解該模型.

5.1 實驗參數設置

為了驗證VMSM-EUN模型和VMSA-IPSO算法的有效性，本文使用云計算仿真工具CloudSim進行仿真實驗.為驗證本文提出的VM資源調度算法的性能，在相同環境和條件下將本文提出的VM調度算法VMSA-IPSO與文獻[29]提出的MBFD( Modified Best Fit Decreasing algorithm)算法以及“Packing Problem”問題近似算法FF(First-Fit algorithm)、 BF(Best-Fit algorithm)進行比較.從活動服務器數量、服務器效用和能耗3個方面進行了對比分析.實驗模擬包含400個異構服務器的異構虛擬化數據中心，為了反映虛擬化數據中心的異構性，我們根據參考文獻[30]，選取了兩種類型的服務器，它們具有不同的配置和能耗特征，服務器的參數特征如表2所示.所選服務器在不同負載級別的功耗(瓦特)如表3[31]所示.對比仿真實驗的參數設置如表4所示.根據文獻[32]，在基于Xeon處理器的服務器中，CPU是能耗最大的部件，其能耗占比高達74%，內存能耗占比為19%，硬盤能耗占比為5%，網絡部件能耗占比2%.在表4中ω1，ω2，ω3，ω4分別為CPU 能耗權重，內存能耗權重，硬盤能耗權重，網絡帶寬能耗權重.表5給出了本次實驗的VM實例.

表2 服務器參數特征Table 2 Server configuration

表3 服務器在不同負載級別的功耗(瓦特)Table 3 Power consumption of servers at various load levels(W)

表4 實驗參數配置Table 4 Experimental parameter configuration

表5 虛擬機實例Table 5 Virtual machine instances

5.2 活動服務器數量比較

在本文中，活動服務器的數量是處于活動狀態的服務器總數，這些服務器運行承載云服務的VM.在此實驗中，VM請求的數量為100到1000，我們將激活HP ProLiant G4服務器或HP ProLiant G5服務器來響應其請求.圖4給出了與其他方法的對比實驗結果.

由圖4可見，隨著VM請求數量的增加，本文提出的算法總是能激活最小數量的服務器，而FF算法始終激活最大數量的服務器.MBFD算法激活的服務器總數小于BF算法和FF算法，但激活的服務器總數多于本文提出的算法VMSA-IPSO.因此，VMSA-IPSO算法能夠使移動云數據中心開啟更少的服務器，提高了資源的利用率.

圖4 激活服務器總數Fig.4 Total number of active servers

5.3 數據中心效用比較

在本文中，數據中心的全局效用定義為所有VM的效用與所有服務器運營成本的差值.根據式(4)、式(5)可得：

(21)

式(21)中，Rtotal、Rvm和Pcost分別為數據中心的全局效用、所有VM的效用和所有服務器的成本.Yi∈{0，1}表示服務器Pi是否處于激活狀態.Yi=1，表示服務器Pi處于激活狀態.Yi=0，表示服務器Pi處于關閉狀態.根據式(21)，我們可以計算在不同VM請求下，各個VM調度算法產生的全局效用值，計算結果如圖5所示.

圖5 數據中心效用值比較Fig.5 Data center utility values comparison

如圖5所示，與其他算法相比，我們的算法獲得了更高的效用值.隨著VM請求數量的增長，云中心在這4種算法下的效用值各不相同，但是本文提出方法的效用值總是高于FF、BF和MBFD.對于同一組VM請求，如果虛擬化數據中心中服務器的利用率較高，可激活較少的服務器來承載云服務工作負載，此時虛擬化數據中心的能源消耗將減少，數據中心的效用會大幅度增加.

5.4 能耗比較

在本文中，能耗是指所有處于激活狀態的服務器的總能耗，計算方法如式(8)-式(10)所示.在滿足不同數量的VM請求下，對比的各個算法的總能耗如圖6所示.

圖6 總能耗對比圖Fig.6 Total energy consumption comparison chart

通過圖6我們可以得出，無論VM請求的規模如何，本文提出的方法均可使數據中心運營商能夠節省更多能量.與其他3種方法相比，我們的方法可以節省較多能源費用.這是因為FF，BF和MBFD在解決問題的過程中，缺乏虛擬化數據中心中異構服務器的能耗特征等反映全局狀態的信息.那些算法只考慮了多維資源約束，且未考慮不同服務器的能量差異.

5.5 VMSA-IPSO算法性能分析

為比較VMSA-IPSO算法的收斂時間，本文將未引入參數自適應調整策略的調度算法與VMSA-IPSO算法進行比較.在對比實驗中，粒子群大小為30，迭代次數為100.圖7中，VM請求數量為300.圖8中，VM請求數量為800.從圖7和圖8可以看出，VMSA-IPSO開始進化并快速收斂，然后趨向平穩，能達到很好的收斂效果，收斂時間大約為50～60次迭代的時間.而未引入參數自適應調整策略的算法的收斂時間大約為75-85次迭代的時間.

圖7 收斂時間對比1(虛擬機請求數量：300)Fig.7 Convergence time comparison 1 (Number of virtual machine requests：300)

綜上所述，本文方法引入關鍵參數自適應調整策略，增強了VMSA-IPSO調度算法的收斂性，加快了算法的求解速度，使其能夠更快找到更好的VM調度方案，提高調度方案的質量.

6 結 論

本文以最小化能耗、最大化效用以及最小化服務器數為目標，建立了VM調度模型VMSM-EUN，設計了基于改進粒子群的VM調度算法VMSA-IPSO來求解該模型.本文在綜合考慮了云中心效用和能耗的前提下，提出的調度算法能更好的解決移動云計算環境下的VM調度問題.通過與現有算法的對比實驗，驗證了本文提出的基于改進粒子群的VM調度算法具有使云中心能耗更低，效用更大的優點，能進行更優的VM調度.