面向負(fù)載-時(shí)間窗口的基于PSO-GA的云軟件服務(wù)自適應(yīng)資源分配方法

楊立堅(jiān)，陳 星，黃引豪

(福州大學(xué) 數(shù)學(xué)與計(jì)算機(jī)科學(xué)學(xué)院，福州 350108)

(福建省網(wǎng)絡(luò)計(jì)算與智能信息處理重點(diǎn)實(shí)驗(yàn)室，福州 350108)

1 引 言

云計(jì)算是將某一個(gè)或某幾個(gè)數(shù)據(jù)中心的計(jì)算資源虛擬化之后，向用戶提供以租用計(jì)算資源的服務(wù)，其為海量數(shù)據(jù)和計(jì)算資源提供基礎(chǔ)性的接入，并且這些資源可以按需進(jìn)行動(dòng)態(tài)接入和釋放.在云計(jì)算環(huán)境中，云軟件服務(wù)面臨著動(dòng)態(tài)變化的工作負(fù)載，然而，這種動(dòng)態(tài)和不可預(yù)測的工作負(fù)載可能導(dǎo)致軟件服務(wù)質(zhì)量的下降，特別是當(dāng)對資源的需求增加時(shí).為了在不斷變化的工作負(fù)載下提供資源的可伸縮性和彈性，云提供商通常需要在共享基礎(chǔ)設(shè)施中提供軟件和硬件資源的按需配置.如今，基于云的軟件服務(wù)的大量使用證明了云軟件工程正在獲得發(fā)展勢頭[1].如何為這些云軟件服務(wù)合理分配資源是一項(xiàng)具有挑戰(zhàn)性的任務(wù).近年來，隨著云軟件資源自適應(yīng)技術(shù)[2-5]的不斷發(fā)展，云應(yīng)用分配資源的有效性有所提高，用戶追求的高軟件服務(wù)質(zhì)量與云廠商追求的低云資源開銷之間的矛盾關(guān)系也有所平衡.與此同時(shí)，如何更好地提高資源分配的有效性成為了自適應(yīng)技術(shù)發(fā)展新的挑戰(zhàn).

現(xiàn)有的自適應(yīng)技術(shù)中，大都是針對云環(huán)境中當(dāng)前負(fù)載的狀況做出響應(yīng)，并進(jìn)行資源自適應(yīng)分配.AlQayedi等人[6]提出一種基于排隊(duì)理論的方案，根據(jù)當(dāng)前的工作負(fù)載來估計(jì)滿足響應(yīng)時(shí)間所需的VM實(shí)例的數(shù)量，該方案還采用響應(yīng)式資源調(diào)配技術(shù)，以CPU利用率為閾值，定期(每1或2分鐘)檢查工作負(fù)載狀況，重新計(jì)算所需的VM實(shí)例，以調(diào)整(添加或刪除)所分配的VM數(shù)量，但當(dāng)未來工作負(fù)載波動(dòng)比較嚴(yán)重時(shí)，該方案未能得出較好的虛擬機(jī)資源分配方案.Maurer等人[2]設(shè)計(jì)了一種新的自適應(yīng)和資源高效的決策方法，并根據(jù)工作負(fù)載的波動(dòng)性，提出了基于規(guī)則的自適應(yīng)知識(shí)管理方法來實(shí)現(xiàn)虛擬機(jī)的自主重構(gòu)，但其未考慮資源成本最小化目標(biāo).Xie等人[7]提出了一種基于粒子群算法的資源配置和價(jià)格調(diào)整策略，根據(jù)工作負(fù)載的特點(diǎn)，設(shè)計(jì)了一個(gè)效用函數(shù)來評價(jià)服務(wù)質(zhì)量.根據(jù)所有工作負(fù)載對資源的需求，由相應(yīng)的資源代理動(dòng)態(tài)調(diào)整資源價(jià)格，以獲得每個(gè)工作負(fù)載的最大利潤，但粒子群算法存在局部收斂問題，在計(jì)算資源配置與價(jià)格調(diào)整時(shí)，得到的方案無法代表整體最優(yōu)解.Dhrub等人[8]了一種考慮QoS指標(biāo)的動(dòng)態(tài)調(diào)整資源分配的自伸縮模型，它在虛擬機(jī)級別執(zhí)行資源更正，同時(shí)考慮使用不足和使用過度的情況，雖然該方法能夠根據(jù)不斷改變的負(fù)載對分配給應(yīng)用程序的資源進(jìn)行按需調(diào)整，但未綜合考慮QoS與虛擬機(jī)租賃成本之間的關(guān)系，且未將未來復(fù)雜波動(dòng)的負(fù)載變化情況考慮到方法中.Chen等人[9]提出了一種適用于云計(jì)算環(huán)境下軟件服務(wù)的自適應(yīng)資源管理框架，該框架由3部分構(gòu)成，首先通過歷史數(shù)據(jù)訓(xùn)練QoS預(yù)測模型，其次采用基于PSO的運(yùn)行時(shí)決策算法結(jié)合QoS預(yù)測值來確定未來的資源分配操作，再通過引入反饋控制使資源分配達(dá)到預(yù)期效果，但其在計(jì)算QoS預(yù)測值時(shí)，未考慮未來負(fù)載的影響.

對基于云資源的系統(tǒng)應(yīng)用來說，應(yīng)用的負(fù)載情況是影響資源分配的主要因素之一.在云環(huán)境中，預(yù)測工作負(fù)載對于更有效地分配資源是可行的.僅通過當(dāng)前負(fù)載來進(jìn)行資源分配，其有效性受到未來負(fù)載波動(dòng)的影響，而通過預(yù)測工作負(fù)載[10-12]來提高資源分配有效性則受到工作負(fù)載預(yù)測模型精度的影響.針對以上問題，受Wang等人[13]的啟發(fā)，本文提出一種面向負(fù)載時(shí)間窗口的云軟件服務(wù)資源自適應(yīng)分配策略，并在此基礎(chǔ)上建立優(yōu)化虛擬機(jī)資源分配方案計(jì)算模型，在進(jìn)行資源分配時(shí)，將當(dāng)前的負(fù)載以及窗口內(nèi)未來的負(fù)載加入模型計(jì)算過程中，使用基于PSO-GA的運(yùn)行時(shí)決策算法搜索合適的資源分配方案.該模型旨在提高云軟件服務(wù)的自適應(yīng)資源分配的有效性.由于工作負(fù)載的變化是給定的，因此本文的模型是正交于工作負(fù)載預(yù)測的，可以與現(xiàn)有的負(fù)載預(yù)測模型相關(guān)聯(lián).

本文的主要貢獻(xiàn)如下：

?對面向負(fù)載時(shí)間窗口的資源分配進(jìn)行形式化定義.

?使用基于PSO-GA的運(yùn)行時(shí)決策算法，結(jié)合QoS預(yù)測模型，根據(jù)面向負(fù)載的時(shí)間窗口，搜索目標(biāo)資源分配方案，并對當(dāng)前分配方案作出調(diào)整.

?我們在RUBiS基準(zhǔn)上評估我們的方法.實(shí)驗(yàn)結(jié)果表明，該方法能夠提高資源分配的有效性.

本文剩余的部分由以下內(nèi)容構(gòu)成，第2部分進(jìn)行問題的形式化定義.第3部分整體概述了方法的實(shí)現(xiàn)框架，并詳細(xì)介紹PSO-GA算法，其中包括算法中變量的定義以及具體實(shí)現(xiàn)，然后介紹如何根據(jù)算法結(jié)果調(diào)整資源分配方案.第4部分實(shí)例研究，報(bào)告了我們的方法與其他方法在RUBiS基準(zhǔn)上不同指標(biāo)進(jìn)行對比的實(shí)驗(yàn)結(jié)果.第5部分對本文進(jìn)行總結(jié).

2 問題定義

在這部分，我們對問題進(jìn)行形式化定義.

當(dāng)運(yùn)行的環(huán)境變化的時(shí)候，云中軟件服務(wù)就會(huì)有不同的服務(wù)質(zhì)量(Quality of Service，QoS).而運(yùn)行環(huán)境變化在本文中主要分為外部環(huán)境變化與內(nèi)部環(huán)境變化.外部環(huán)境變化是由外部因素造成的，內(nèi)部環(huán)境變化主要是受管理系統(tǒng)影響.在本節(jié)的問題定義中，有兩個(gè)主要的因素，如表1所示.

表1 問題定義中的主要元素

外部因素主要指系統(tǒng)工作負(fù)載.假設(shè)負(fù)載是一個(gè)分段函數(shù)，每個(gè)時(shí)間段的負(fù)載不變，如式(1)所示：

(1)

我們假設(shè)每段負(fù)載持續(xù)的時(shí)間是相等的，并由二元組表示：wi=.ni表示ti時(shí)刻的請求數(shù)量，ri表示ti時(shí)刻的請求讀寫率.另外，在t≥ti+1的負(fù)載是我們不能觀測到的.

內(nèi)在因素指的是由不同類型與數(shù)量的虛擬機(jī)組成的分配方案.由于虛擬機(jī)在租賃的時(shí)候是按小時(shí)來收費(fèi)，所以我們假設(shè)虛擬機(jī)每次租賃一小時(shí)，且一小時(shí)后自動(dòng)關(guān)閉.則我們在調(diào)整虛擬機(jī)分配方案時(shí)刻，只需考慮增加的虛擬機(jī)方案.對應(yīng)于每個(gè)時(shí)段的負(fù)載，虛擬機(jī)增加方案可以表示為：

(2)

假設(shè)每個(gè)調(diào)整方案中有m種可增加的虛擬機(jī)類型Type=<1，2，3，…，m>，則ti時(shí)刻增加虛擬機(jī)配置方案addi可以表示為：

(3)

對應(yīng)于增加虛擬機(jī)分配方案的是每個(gè)時(shí)刻調(diào)整后的虛擬機(jī)分配方案：

(4)

其中q=1h/Δt，表示最大的未過期增加虛擬機(jī)分配方案的數(shù)量.Δt=ti+1-ti，表示每種負(fù)載持續(xù)的時(shí)間段.由公式(4)可知，每個(gè)時(shí)段的虛擬機(jī)分配方案是由對應(yīng)時(shí)段未到期的所有增加虛擬機(jī)方案相加得到.

當(dāng)為云系統(tǒng)應(yīng)用分配資源時(shí)，云工程師或者自適應(yīng)系統(tǒng)的目標(biāo)是需要權(quán)衡分配方案對應(yīng)的服務(wù)質(zhì)量QoS與資源耗費(fèi)Cost之間的關(guān)系.我們通過目標(biāo)函數(shù)來表示它們之間的關(guān)系.

目標(biāo)函數(shù)的其中一個(gè)參數(shù)為QoSi，它表示ti時(shí)刻的QoS值，通常使用服務(wù)等級協(xié)議(Service-Level Agreement，SLA)來指定，包括響應(yīng)時(shí)間(Response Time，RT)，數(shù)據(jù)吞吐量(Data Throughput，DT)等等.響應(yīng)時(shí)間表示用戶請求服務(wù)的時(shí)候，等待服務(wù)響應(yīng)所需時(shí)間.而數(shù)據(jù)吞吐量表示在一個(gè)給定時(shí)間系統(tǒng)能夠處理的信息量.但是這些指標(biāo)無法用來預(yù)測系統(tǒng)的QoS值，因?yàn)橹挥蟹峙渫晏摂M機(jī)資源后，這些指標(biāo)才能被監(jiān)控到.于是就需要一個(gè)QoS預(yù)測模型[13，14]，如公式(5)所示，該模型的輸入包括請求數(shù)量與類型(w)，虛擬機(jī)數(shù)量與類型(vm)，輸出為QoS預(yù)測值.

QoSpredicted=QoS(w，vm)

(5)

通過該QoS預(yù)測模型，給定一個(gè)負(fù)載w與資源配置方案vm，模型就能夠預(yù)測出對應(yīng)的QoS值.

函數(shù)的另一個(gè)參數(shù)為Costi它表示ti時(shí)刻負(fù)載區(qū)間對應(yīng)的增加虛擬機(jī)addi的成本.假設(shè)每種類型虛擬機(jī)租賃消費(fèi)P=，則Costi可表示為

(6)

那么目標(biāo)函數(shù)可以通過QoSi與Costi表示為：

(7)

公式中r1與r2代表權(quán)重，是由工程師根據(jù)經(jīng)驗(yàn)進(jìn)行選定.

然而，在實(shí)際環(huán)境中，僅通過當(dāng)前的負(fù)載計(jì)算出的對應(yīng)資源分配方案有效性無法得到保障，于是，我們需要使用面向負(fù)載的時(shí)間窗口，根據(jù)窗口內(nèi)的負(fù)載給出對應(yīng)的增加虛擬機(jī)分配方案，進(jìn)而求出對應(yīng)時(shí)刻的虛擬機(jī)分配方案.

面向負(fù)載時(shí)間窗口，在進(jìn)行資源分配的時(shí)刻，時(shí)間窗口能夠觀察相對于當(dāng)前時(shí)刻之后的一段負(fù)載，進(jìn)而對資源進(jìn)行相應(yīng)調(diào)整.

假設(shè)窗口i能夠預(yù)測到長度為l(包含的區(qū)間數(shù)量)的工作負(fù)載區(qū)域，結(jié)合公式(1)，該區(qū)域內(nèi)的負(fù)載Wi可表示為：

(8)

與負(fù)載窗口Wi對應(yīng)的是窗口內(nèi)增加虛擬機(jī)分配方案ADDi，它表示為：

(9)

那么根據(jù)公式(9)，窗口內(nèi)虛擬機(jī)分配方案VMi可表示為：

(10)

于是，問題就轉(zhuǎn)化為搜索窗口內(nèi)一個(gè)最優(yōu)的增加虛擬機(jī)資源分配方案.由于該問題是一個(gè)經(jīng)典的組合優(yōu)化問題，在理論上屬于np難題，所以，我們可以使用啟發(fā)式算法基于適應(yīng)度函數(shù)來搜索一個(gè)合適的資源分配方案.

3 方 法

本節(jié)介紹方法的實(shí)現(xiàn)，整體架構(gòu)如圖1所示.

圖1 方法概覽圖

3.1 方法概覽

本文介紹了面向負(fù)載的時(shí)間窗口，并通過負(fù)載窗口計(jì)算虛擬機(jī)資源分配方案，如圖1所示，可以分為以下幾個(gè)部分：

首先，初始化時(shí)間窗口參數(shù)，其中包括時(shí)間窗口對應(yīng)的負(fù)載、負(fù)載對應(yīng)的增加虛擬機(jī)分配方案以及虛擬機(jī)分配方案.其次，我們使用PSO-GA算法，在QoS預(yù)測模型的支持下，搜索窗口內(nèi)的目標(biāo)資源分配方案.最后，根據(jù)目標(biāo)資源分配方案，對當(dāng)前的虛擬機(jī)分配方案作出相應(yīng)調(diào)整.

3.2 PSO-GA搜索目標(biāo)資源分配方案

3.2.1 粒子群優(yōu)化算法(PSO)

PSO算法[15，16]屬于進(jìn)化算法的一種，通過模擬自然界鳥群遷徙的活動(dòng)，讓粒子不斷地迭 代從而尋找最優(yōu)解.粒子在PSO算法中是非常重要的概念，每一個(gè)粒子代表優(yōu)化問題的一個(gè)候選解，粒子通過自身歷史最優(yōu)值與族群歷史最優(yōu)值不斷在解空間中迭代更新.式(11)是粒子的速度公式，式(12)是粒子的位置公式.

(11)

(12)

3.2.2 遺傳算法(GA)

GA算法[16]是通過模擬生物界中生物進(jìn)化過程的計(jì)算模型.遺傳算法同樣從隨機(jī)解出發(fā)，按照自然界優(yōu)勝劣汰的原則，通過上一代優(yōu)秀個(gè)體的組合交叉和變異過程，逐代演化生成越來越好的下一代個(gè)體，從而找到更優(yōu)的近似解.

3.2.3 基于PSO-GA的目標(biāo)虛擬機(jī)資源分配方案搜索策略

本章提出一種改進(jìn)的粒子群算法PSO-GA，PSO-GA算法通過引入PSO算法對粒子個(gè)體的優(yōu)化過程，使GA算法中的粒子個(gè)體得到優(yōu)化，從而解決了GA算法搜索后期效率低下的問題.PSO-GA算法先通過粒子的適應(yīng)度評價(jià)函數(shù)對粒子進(jìn)行排序，保留其中優(yōu)秀的個(gè)體用于下一次PSO算法迭代，而淘汰表現(xiàn)較差的個(gè)體.通過對優(yōu)秀個(gè)體的交叉與變異操作得到剩下的粒子，進(jìn)入下一代.在本章中，一個(gè)粒子只是代表一個(gè)時(shí)間窗口內(nèi)的解，每經(jīng)過一個(gè)固定的時(shí)間間隔，通過PSO-GA求出一個(gè)最佳的粒子當(dāng)做該時(shí)刻的目標(biāo)虛擬機(jī)資源分配方案.下面對改進(jìn)粒子群算法中的粒子編碼、適應(yīng)度函數(shù)、以及更新策略進(jìn)行設(shè)計(jì).

3.2.4 粒子編碼

對于云軟件服務(wù)資源分配問題的編碼，本章采用離散編碼方式對PSO的粒子進(jìn)行編碼[17].對于時(shí)間窗口k，窗口內(nèi)的增加虛擬機(jī)資源分配方案可以表示為：

(13)

其中l(wèi)為時(shí)間窗口k的長度，它表示窗口內(nèi)增加虛擬機(jī)資源分配方案的數(shù)量.

將窗口k內(nèi)增加虛擬機(jī)分配方案ADDk作為粒子X，一個(gè)粒子代表窗口k對應(yīng)的增加虛擬機(jī)資源分配方案.假設(shè)窗口中虛擬機(jī)類型有m種，窗口長度為l，則第i個(gè)粒子的第t次迭代可表示為：

(14)

圖2展示了長度為3，虛擬機(jī)種類為3的時(shí)間窗口內(nèi)的一個(gè)粒子編碼.它表示窗口中第1個(gè)增加虛擬機(jī)分配方案為[011]，第2個(gè)增加虛擬機(jī)分配方案為[014]，第3個(gè)增加虛擬機(jī)分配方案為[001].

圖2 增加虛擬機(jī)資源分配方案粒子編碼

3.2.5 適應(yīng)度函數(shù)建立

在引入時(shí)間窗口之后，適應(yīng)度函數(shù)需要通過窗口內(nèi)的負(fù)載以及虛擬機(jī)資源分配方案來計(jì)算.假設(shè)時(shí)間窗口的長度為l，則窗口i內(nèi)的負(fù)載Wi可表示為：

(15)

由公式可以看出，窗口i內(nèi)的負(fù)載是分段函數(shù).

時(shí)間窗口i內(nèi)的虛擬機(jī)資源分配方案VMi需要通過窗口i內(nèi)增加的虛擬機(jī)資源分配方案ADDi計(jì)算得到，ADDi如公式(16)所示：

(16)

則VMi可表示為：

(17)

由于我們已經(jīng)對窗口i內(nèi)增加的虛擬機(jī)資源分配方案ADDi進(jìn)行粒子編碼，所以VMi可以通過粒子編碼計(jì)算得到.

窗口內(nèi)增加虛擬機(jī)資源分配方案通過fitness函數(shù)進(jìn)行評估.fitness函數(shù)在QoS值與資源成本Cost之間進(jìn)行權(quán)衡，能夠指導(dǎo)粒子群優(yōu)化算法搜尋求解的方向.由于引入了時(shí)間窗口，則由上述公式，fitness函數(shù)可表示為：

(18)

fitness函數(shù)中的QoS值為窗口i內(nèi)總的QoS值，如公式(18)前半部分所示，其中wk∈Wi，表示窗口i內(nèi)l個(gè)時(shí)段中某個(gè)時(shí)段的負(fù)載.而vmk∈VMi，表示窗口i內(nèi)l個(gè)時(shí)段中某個(gè)時(shí)段的虛擬機(jī)資源分配方案

于是，根據(jù)時(shí)間窗口i內(nèi)的負(fù)載Wi以及虛擬機(jī)分配方案VMi中每個(gè)時(shí)段對應(yīng)的wk與vmk，通過QoS預(yù)測模型(式(5))，分別計(jì)算出QoS，然后再對這l個(gè)QoS求和，就能得到窗口i內(nèi)總的QoS值.

另外，它們的權(quán)重r1與r2是專家通過對不同系統(tǒng)的需求而定的.且從公式中可以明顯看出，窗口內(nèi)越好的增加虛擬機(jī)資源分配方案，所對應(yīng)的評估值也越小.因此，在給定窗口i內(nèi)的負(fù)載Wi以及ADDi對應(yīng)的粒子編碼后，我們就可以通過fitness函數(shù)計(jì)算出對應(yīng)的評估值.

3.2.6 粒子更新策略

我們通過遺傳算法的交叉變異過程來更新整個(gè)粒子群的狀態(tài).

變異操作隨機(jī)選取粒子中的一個(gè)基因段，不規(guī)律改變其基因值，且新值必須都在對應(yīng)的閾值內(nèi)[18].圖3為對圖2粒子編碼的變異操作，隨機(jī)選擇粒子的一個(gè)基因段mg1，mg1位置上的值由(0，1，4)變異為(0，2，3)，該變異符合虛擬機(jī)分配準(zhǔn)則.

圖3 粒子編碼慣性部分變異

圖4為局部(或全局)最優(yōu)粒子部分的交叉操作[19]，隨機(jī)產(chǎn)生兩個(gè)交叉的基因段位置cg1與cg2，將這兩個(gè)基因段內(nèi)的值替換為pBest(或gBest)對應(yīng)基因段的值.在更新過程對于局部(或全局)最優(yōu)粒子的交叉概率都為50%.

圖4 粒子編碼局部(或全局)最優(yōu)粒子部分的交叉操作

3.2.7 算法流程

如PSO-GA算法所示，搜索目標(biāo)虛擬機(jī)配置方案的流程如下：

Step 1.隨機(jī)初始化粒子種群，其中包括種群規(guī)模大小N、最大迭代次數(shù)以及種群本染色體addi，并初始化每個(gè)種群的局部最優(yōu)解pBesti以及全局最優(yōu)解gBest，如算法2-6行.

Step 2.在滿足算法執(zhí)行條件下，通過粒子的交叉變異操作對粒子群進(jìn)行更新操作，通過公式(13)計(jì)算每個(gè)種群染色體addi的評估值，并更新全局最優(yōu)與局部最優(yōu)染色體，如算法7-16行所示.

Step 3.輸出最終的全局最優(yōu)解gBest.

算法.PSO-GA

輸入：種群規(guī)模N

輸出：滿足執(zhí)行條件下的一個(gè)全局最優(yōu)解gBest

1.procedure PSO-GA

2.foreach particlei

3. Initialize velocityaddifor particlei

4. Evaluate particleiand setpBesti=addi

5.endfor

6.gBest=min{pBesti}

7.whilenot stop

8.fori=1toN

9. update particleibymutateandcrossover

10. Evaluate particlei

11.ifFitnessi(addi)

12.pBesti=addi

13.ifFitnessi(pBesti)

14.gBest=pBesti

15.endfor

16.endwhile

17.printgBest

18.end procedure

3.3 調(diào)整虛擬機(jī)資源分配方案

于是，在每個(gè)資源調(diào)整的時(shí)刻，通過PSO-GA算法在窗口內(nèi)搜索目標(biāo)增加虛擬機(jī)資源方案，該方案是在滿足算法執(zhí)行條件下搜索到的適應(yīng)度函數(shù)值最小的方案，可以表示為：

(19)

4 實(shí)例研究

我們在RUBiS[20]基準(zhǔn)上評估我們的方法.評估的目標(biāo)是：基于面向負(fù)載的時(shí)間窗口，通過比較PSO-GA算法與其他兩種方法計(jì)算出來的目標(biāo)虛擬機(jī)分配方案的各項(xiàng)指標(biāo)，評估PSO-GA算法的性能.

4.1 實(shí)驗(yàn)環(huán)境

RUBiS是一個(gè)模仿eBay.com的拍賣網(wǎng)站原型，通常用于評估應(yīng)用服務(wù)器的性能可伸縮性[20].它提供了一個(gè)客戶端，可以為各種工作負(fù)載模式模擬用戶行為.我們假設(shè)工作負(fù)載量在[2000，7000]范圍內(nèi)，并且工作負(fù)載中有兩種類型的任務(wù)(讀與寫).實(shí)驗(yàn)中使用到的虛擬機(jī)分為小中大3種類型，每種配置方案都是由虛擬機(jī)數(shù)量與類型構(gòu)成的，具體的虛擬機(jī)信息如表2所示.

表2 虛擬機(jī)類型及價(jià)格

在實(shí)驗(yàn)中，我們通過一個(gè)Sigmoid函數(shù)將響應(yīng)時(shí)間(RT)的值映射到[0，1]的時(shí)間間隔，其值實(shí)際上是QoS值，根據(jù)經(jīng)驗(yàn)數(shù)據(jù)，映射的QoS值(代表客戶對服務(wù)質(zhì)量的滿意度)與響應(yīng)時(shí)間的函數(shù)如圖5所示.

圖5 QoS映射圖

本實(shí)驗(yàn)在已知一段時(shí)間內(nèi)連續(xù)的負(fù)載前提下進(jìn)行的.這里，我們定義Wi={wi，wi+1，wi+2}，時(shí)間窗口長度為90分鐘(窗口內(nèi)包含3段負(fù)載)，每30分鐘預(yù)測一次.并設(shè)置了實(shí)驗(yàn)場景驗(yàn)證方法的性能.

圖6是負(fù)載情況圖，我們一共預(yù)測了540分鐘的時(shí)間，為了使預(yù)測趨于穩(wěn)定，假設(shè)540分鐘后的負(fù)載是無法觀測到的.對于每個(gè)時(shí)間段的負(fù)載，在其下方都有對應(yīng)的讀寫比率.

圖6 工作負(fù)載情況圖

如公式(18)所示，適應(yīng)度函數(shù)表示云工程師給出的資源分配目標(biāo).較好的資源配置方案應(yīng)獲得較小的適應(yīng)度函數(shù)值.云工程師預(yù)先定義的權(quán)重(r1和r2)反映了他們對服務(wù)質(zhì)量和資源成本的不同偏好.在實(shí)際應(yīng)用中，最常見的適應(yīng)度函數(shù)是平衡服務(wù)質(zhì)量和資源成本，由于云服務(wù)的服務(wù)質(zhì)量和資源之間的復(fù)雜關(guān)系，這一點(diǎn)也很難實(shí)現(xiàn).因此，在實(shí)驗(yàn)中，我們根據(jù)我們的經(jīng)驗(yàn)設(shè)置r1=900和r2=1/6，以平衡QoS和資源成本，如公式(20)所示：

(20)

4.2 實(shí)驗(yàn)總體介紹

我們在面向負(fù)載時(shí)間窗口計(jì)算目標(biāo)虛擬機(jī)資源分配方案的過程中，使用3種方法進(jìn)行實(shí)驗(yàn)：

a)貪心算法.貪心法不考慮時(shí)間窗口中負(fù)載的變化，在每次計(jì)算虛擬機(jī)資源分配方案的時(shí)候，都是以上一時(shí)刻的最優(yōu)配置計(jì)算當(dāng)前時(shí)刻的負(fù)載對應(yīng)的最優(yōu)虛擬機(jī)配置.

b)單點(diǎn)最優(yōu)局部隨機(jī)法.分成兩個(gè)階段來進(jìn)行.首先，一個(gè)時(shí)間窗口內(nèi)的負(fù)載區(qū)間Wi中包含3個(gè)負(fù)載，對于每個(gè)負(fù)載，我們依據(jù)Fitness函數(shù)，遍歷所有虛擬機(jī)配置方案，找到對應(yīng)的一個(gè)評估值最小的方案，我們稱之為單點(diǎn)最優(yōu)配置方案.其次，根據(jù)單點(diǎn)最優(yōu)配置方案，在其附近隨機(jī)增減2臺(tái)虛擬機(jī)來進(jìn)行實(shí)驗(yàn).在設(shè)定的運(yùn)行時(shí)間內(nèi)，得到窗口i內(nèi)最優(yōu)的一個(gè)虛擬機(jī)資源分配方案.

c)PSO-GA算法.初始化時(shí)間窗口對應(yīng)的增加虛擬機(jī)ADDi的染色體，設(shè)定種群規(guī)模為50，迭代次數(shù)為100，每次迭代通過公式(18)計(jì)算每個(gè)粒子染色體的評估值，并選出全局最優(yōu)粒子與局部最優(yōu)粒子，再通過概率都為50%的變異交叉對粒子的染色體進(jìn)行更新操作.在滿足算法執(zhí)行條件的前提下，繼續(xù)進(jìn)行更新后的粒子評估值計(jì)算，以及迭代更新.

我們設(shè)置單點(diǎn)最優(yōu)局部隨機(jī)法與PSO-GA算法執(zhí)行的時(shí)間都為2分鐘，進(jìn)而比較上述3種實(shí)驗(yàn)方法的性能.

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

我們分別對單點(diǎn)最優(yōu)局部隨機(jī)法、貪心法以及PSO-GA在給定的負(fù)載場景下進(jìn)行實(shí)驗(yàn).對應(yīng)的虛擬機(jī)分配結(jié)果如圖7至圖9所示，其中位于圖上方的表格表示每個(gè)時(shí)刻對應(yīng)的增加虛擬機(jī)分配方案，條形圖表示每個(gè)負(fù)載根據(jù)增加虛擬機(jī)分配方案調(diào)整過后對應(yīng)的虛擬機(jī)分配方案，它們由小中大三種虛擬機(jī)組成.

圖7 貪心算法實(shí)驗(yàn)虛擬機(jī)資源分配結(jié)果

圖8 單點(diǎn)最優(yōu)局部隨機(jī)法實(shí)驗(yàn)虛擬機(jī)資源分配結(jié)果

圖9 PSO-GA實(shí)驗(yàn)虛擬機(jī)資源分配結(jié)果

為了更好的評估我們的方法的性能，我們將QoS值、成本以及公式(20)所獲取到的評估值一起作為資源分配有效性的評估指標(biāo)，這可以證明我們的方法總體上提供了最合理的資源分配計(jì)劃.

圖10表示系統(tǒng)的總體Fitness值，它是由0-360分鐘內(nèi)各個(gè)時(shí)段的評估值相加而來.從這個(gè)圖中可以看出，我們的方法比貪心算法跟單點(diǎn)最優(yōu)局部隨機(jī)法的性能分別高出5.74%和4.15%.這些性能增益主要是由于PSO-GA算法既注重了種群每一代之間的進(jìn)化過程，又注重了優(yōu)秀個(gè)體的保留與再成熟，提高了種群多樣性，計(jì)算出來的虛擬機(jī)資源配置更接近最優(yōu)資源分配方案.而單點(diǎn)最優(yōu)局部隨機(jī)法，雖然是基于單點(diǎn)最優(yōu)進(jìn)行隨機(jī)實(shí)驗(yàn)，但搜索沒有目的，具有隨機(jī)性，無法更好地向最優(yōu)的資源配置方案靠近，貪心算法由于每次只考慮當(dāng)前負(fù)載的最優(yōu)資源分配方案，所以，其計(jì)算出來的方案會(huì)隨負(fù)載的波動(dòng)而波動(dòng).

圖10 總體Fitness值比較

另外，從圖11可以看出，就QoS而言，PSO-GA計(jì)算出來的配置方案的平均QoS值為0.96，比其他兩種方法的平均QoS值好，且在0～360分鐘內(nèi)，QoS值維持在0.91～0.99之間，特別是在60～150分鐘負(fù)載快速上升階段，我們可以看到基于PSO-GA算法的虛擬機(jī)資源分配方案能夠?qū)oS值維持在一個(gè)合理的水平，且比較穩(wěn)定.再觀察貪心算法的QoS曲線，可以看出，它的QoS值波動(dòng)比較嚴(yán)重，(在240分鐘的時(shí)候達(dá)到0.95，而到120分鐘時(shí)，降到0.77)而單點(diǎn)最優(yōu)局部隨機(jī)法的QoS值在0.80～0.94之間，平均QoS值介于兩者之間，為0.89.其次，我們比較了PSO-GA算法與其他兩種對比方法的資源成本，如圖4～圖7中的條形圖所示，貪心算法在0～360分鐘內(nèi)的每個(gè)時(shí)段的平均成本為89.24 RMB，單點(diǎn)最優(yōu)局部隨機(jī)法為91.94 RMB，而我們的PSO-GA的平均成本最高，為102.65 RMB.可以發(fā)現(xiàn)，在保證服務(wù)質(zhì)量的前提下，PSO-GA算法的資源成本是我們能夠接受的.

圖11 QoS與Cost比較

最后，我們比較3種實(shí)驗(yàn)方法的執(zhí)行時(shí)間，可以明顯地看出，在同樣執(zhí)行2分鐘時(shí)間的前提下，PSO-GA算法在計(jì)算虛擬機(jī)資源分配方案的性能上比單點(diǎn)最優(yōu)局部隨機(jī)法要好.雖然貪心算法計(jì)算虛擬機(jī)資源分配方案的速度是3種方法中最快的，但是，其虛擬機(jī)資源分配方案的各項(xiàng)指標(biāo)比較差.

5 總 結(jié)

在進(jìn)行資源分配的時(shí)候，通過每個(gè)時(shí)刻負(fù)載來計(jì)算資源分配方案無法滿足負(fù)載波動(dòng)較大的云環(huán)境，且有效性無法得到保證.而使用面向負(fù)載的時(shí)間窗口，將當(dāng)前的負(fù)載以及窗口內(nèi)未來的負(fù)載加入計(jì)算，可以提高自適應(yīng)資源分配的有效性.在本文中，我們提出面向負(fù)載時(shí)間窗口的云軟件服務(wù)自適應(yīng)資源分配策略，并使用PSO-GA運(yùn)行時(shí)決策算法來搜索合適的虛擬機(jī)資源分配方案.然后，通過將PSO-GA算法與另外兩種方法進(jìn)行比較，驗(yàn)證算法的性能.實(shí)驗(yàn)結(jié)果表明，PSO-GA算法所表現(xiàn)出來的性能比其他兩種方法更好.

盡管本文的方法計(jì)算出的資源分配方案有效性有所提高，但是文中使用的負(fù)載是通過離散分段函數(shù)來定義的，在實(shí)際環(huán)境中，負(fù)載更多時(shí)候是連續(xù)的，此時(shí)，通過時(shí)間窗口觀察到的負(fù)載數(shù)量就比分段函數(shù)多，如何將窗口內(nèi)的連續(xù)負(fù)載加入計(jì)算成為新的挑戰(zhàn).未來的研究方向主要有兩點(diǎn)：一是結(jié)合實(shí)驗(yàn)中3種算法的優(yōu)缺點(diǎn)，繼續(xù)研究和改進(jìn)算法，提高算法性能.二是引入連續(xù)負(fù)載函數(shù)，研究如何在連續(xù)負(fù)載環(huán)境中進(jìn)行自適應(yīng)資源分配.