面向移動云計算的自適應(yīng)虛擬機調(diào)度算法

韋傳講，莊 毅

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

1 引 言

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

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

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

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

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

1)從CPU、內(nèi)存、網(wǎng)絡(luò)帶寬和磁盤4個維度，將最小化數(shù)據(jù)中心能耗、最大化數(shù)據(jù)中心效用以及最小化服務(wù)器數(shù)量作為目標(biāo)，建立了基于多目標(biāo)優(yōu)化的VM調(diào)度模型VMSM-EUN.該模型具有能耗低、效用高和調(diào)度結(jié)果優(yōu)等特點.

2)根據(jù)粒子群進化的不同階段，分別設(shè)計了適用于加速因子與慣性因子的動態(tài)自適應(yīng)調(diào)整策略，可加速粒子群的求解過程并獲得更優(yōu)解.

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

2 相關(guān)研究

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

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

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

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

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

3 虛擬機調(diào)度模型

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

3.1 相關(guān)定義

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

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

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

(1)

(2)

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

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

(3)

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

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

(4)

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

(5)

3.2 約束條件

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

s.t

(6)

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

3.3 目標(biāo)函數(shù)

為實現(xiàn)移動云數(shù)據(jù)中心效益最大化和降低運行成本的目標(biāo)，本小節(jié)根據(jù)上述定義與調(diào)度約束條件，設(shè)計了3個VM調(diào)度的目標(biāo)函數(shù)，具體如下.

3.3.1 最小能耗

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

(7)

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

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

(8)

(9)

(10)

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

3.3.2 最大效用

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

(11)

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

3.3.3 最小服務(wù)器數(shù)

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

(12)

綜上所述，VM調(diào)度模型VMSM-EUN可以描述為：

(13)

(14)

(15)

s.t

(16)

4 基于改進粒子群的虛擬機調(diào)度算法

4.1 改進的粒子群優(yōu)化算法

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

在PSO中，每一個粒子被認為是潛在的解決方案，每個粒子都與兩個向量相關(guān)聯(lián)，它們分別是速度向量v(t)=[v1，v2，…，vD] 和位置向量x(t)=[x1，x2，…，xD]，其中D為解空間的維度.在進化過程中改進的PSO算法的更新方程如式(17)、式(18)[20]所示，在PSO中所有粒子是根據(jù)當(dāng)前局部最優(yōu)解pbest和當(dāng)前全局最優(yōu)解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)上一致分布的隨機數(shù).每一維上的粒子速度被限制在vmax(vmax>0) 內(nèi)，如果某一維更新后的速度大于用戶給定的vmax，那么就設(shè)為vmax，即v(t+1)>vmax時，v(t+1)=vmax.如果某一維更新后的速度小于等于用戶給定的-vmax，那么就設(shè)為-vmax，即v(t+1)≤-vmax時，v(t+1)=-vmax.目前已有的研究對PSO進行了改進，典型工作有主要3個方面：YH Shi等人將慣性因子引入PSO，并證明了當(dāng)慣性因子值較大時，全局尋優(yōu)能力強，局部尋優(yōu)能力弱；值較小反之[21].除慣性因子外，加速因子c1和c2也是PSO中的重要參數(shù).權(quán)重因子包括慣性因子ω和加速因子c1、c2，使粒子保持著原有的運動狀態(tài)，并具有探索和開發(fā)的能力.在Kennedy的兩個極端情況下，實驗表明“僅社交”模型和“僅認知”模型中，兩種加速因子對于PSO的成功至關(guān)重要[22].Kennedy和Eberhart建議c1、c2固定值為2.0，這種配置已被許多研究人員采用[23].Suganthan證明了對于不同的問題，使用c1、c2的“ad hoc”值而不是固定值可以產(chǎn)生更好的性能[24].Ratnaweera等人提出了一種具有線性時變加速度系數(shù)(HPSO-TVAC)的PSO算法，在開始時設(shè)置較大的c1和較小的c2，并且在搜索期間逐漸反轉(zhuǎn).在對比實驗中，HPSO-TVAC顯示出最佳的整體性能.這是由于時變c1和c2可以平衡全局搜索能力和局部搜索能力[25].由上所述可見，在粒子群尋優(yōu)的過程中采用適合的慣性因子ω、加速因子c1和c2，將有助于提高PSO性能.因此我們在4.3小節(jié)中，將在粒子群求解過程中確定每一次迭代后粒子群所處的狀態(tài)，動態(tài)自適應(yīng)的改變慣性因子ω和加速因子c1、c2的取值.

4.2 映射關(guān)系與編碼方式

為了將PSO算法用于求解VM調(diào)度問題，我們需要將粒子的編碼與現(xiàn)實問題對應(yīng)，本文中粒子的位置、速度與現(xiàn)實中VM調(diào)度問題的映射關(guān)系如下所述.

圖1 編碼方式Fig.1 Encoding scheme

4.3 自適應(yīng)參數(shù)調(diào)整

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

4.3.1 加速因子c1和c2的調(diào)整

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

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

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

表1 去模糊規(guī)則表Table 1 Fuzzy control rules

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

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

(19)

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

4.3.2 慣性因子ω的調(diào)整

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

(20)

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

圖2 自適應(yīng)參數(shù)調(diào)整流程圖Fig.2 Self-adaptive parameter adjustment flow chart

4.4 虛擬機調(diào)度算法

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

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

Step2.初始化.

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

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

Step3.計算每個粒子到其他粒子的平均距離和進化因子f根據(jù)進化因子f的大小對粒子群的狀態(tài)進行評估，自適應(yīng)的調(diào)整參數(shù)c1、c2和ω.

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

Step5.對于每個粒子更新其當(dāng)前最好位置pbest.

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

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

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

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

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

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

Step9.根據(jù)更新后的粒子群，更新局部最優(yōu)粒子和全局最優(yōu)粒子的位置信息.

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

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

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

5 實驗與結(jié)果分析

本文基于多目標(biāo)優(yōu)化算法建立了VM調(diào)度模型VMSM-EUN，將最小化數(shù)據(jù)中心能耗、最大化數(shù)據(jù)中心效用以及最小化服務(wù)器數(shù)作為目標(biāo)，設(shè)計并實現(xiàn)了基于改進粒子群的VM調(diào)度算法VMSA-IPSO來求解該模型.

5.1 實驗參數(shù)設(shè)置

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

表2 服務(wù)器參數(shù)特征Table 2 Server configuration

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

表4 實驗參數(shù)配置Table 4 Experimental parameter configuration

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

5.2 活動服務(wù)器數(shù)量比較

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

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

圖4 激活服務(wù)器總數(shù)Fig.4 Total number of active servers

5.3 數(shù)據(jù)中心效用比較

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

(21)

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

圖5 數(shù)據(jù)中心效用值比較Fig.5 Data center utility values comparison

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

5.4 能耗比較

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

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

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

5.5 VMSA-IPSO算法性能分析

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

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

綜上所述，本文方法引入關(guān)鍵參數(shù)自適應(yīng)調(diào)整策略，增強了VMSA-IPSO調(diào)度算法的收斂性，加快了算法的求解速度，使其能夠更快找到更好的VM調(diào)度方案，提高調(diào)度方案的質(zhì)量.

6 結(jié) 論

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