韋傳講，莊 毅

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

1 引 言

隨著無(wú)線網(wǎng)絡(luò)的快速發(fā)展，促使了諸如手機(jī)、筆記本和平板電腦之類的智能設(shè)備的發(fā)明，這樣的聯(lián)網(wǎng)技術(shù)和設(shè)備使得用戶可以移動(dòng)，并可以隨時(shí)隨地訪問(wèn)資源.因此，移動(dòng)性已成為現(xiàn)代互聯(lián)網(wǎng)世界的主要特征.根據(jù)中國(guó)互聯(lián)網(wǎng)信息中心發(fā)布的報(bào)告，截止2018年底，我國(guó)網(wǎng)民數(shù)量大約為8.29億，其中大概有98.6%的網(wǎng)民是通過(guò)手機(jī)訪問(wèn)互聯(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ù)的種類變得多樣化，使得人們對(duì)移動(dòng)設(shè)備的計(jì)算性能的需求也越來(lái)越高[1].

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

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

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

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

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

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

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

2 相關(guān)研究

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

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

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

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

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

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

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

3.1 相關(guān)定義

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

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

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

(1)

(2)

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

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

(3)

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

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

(4)

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

(5)

3.2 約束條件

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

s.t

(6)

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

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

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

3.3.1 最小能耗

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

(7)

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

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

(8)

(9)

(10)

其中，式(8)將服務(wù)器的能耗與服務(wù)器的負(fù)載相聯(lián)系，考慮了CPU、內(nèi)存、網(wǎng)絡(luò)帶寬和磁盤(pán)4個(gè)維度，而不是僅僅考慮CPU利用率.Pmaxi表示服務(wù)器Pi的多維負(fù)載率達(dá)到最高峰值時(shí)的最大功耗；UMDLi(t) 表示服務(wù)器Pi在t時(shí)刻的多維負(fù)載率.式(9)中Ei表示優(yōu)化周期[t1，t2]內(nèi)服務(wù)器Pi的能耗.式(10)中，E表示移動(dòng)云中心所有服務(wù)器的能耗，單位為瓦特(W)，n表示移動(dòng)云數(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 最大效用

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

(11)

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

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

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

(12)

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

(13)

(14)

(15)

s.t

(16)

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

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

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

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

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

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

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

圖1 編碼方式Fig.1 Encoding scheme

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

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

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

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

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

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

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

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

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

(19)

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

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

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

(20)

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

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

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

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

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

Step2.初始化.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

5 實(shí)驗(yàn)與結(jié)果分析

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

5.1 實(shí)驗(yàn)參數(shù)設(shè)置

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

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

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

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

表5 虛擬機(jī)實(shí)例Table 5 Virtual machine instances

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

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

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

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

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

在本文中，數(shù)據(jù)中心的全局效用定義為所有VM的效用與所有服務(wù)器運(yùn)營(yíng)成本的差值.根據(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)，我們可以計(jì)算在不同VM請(qǐng)求下，各個(gè)VM調(diào)度算法產(chǎn)生的全局效用值，計(jì)算結(jié)果如圖5所示.

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

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

5.4 能耗比較

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

圖6 總能耗對(duì)比圖Fig.6 Total energy consumption comparison chart

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

5.5 VMSA-IPSO算法性能分析

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

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

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

6 結(jié) 論

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