基于用戶(hù)QoS預(yù)測(cè)的任務(wù)流調(diào)度算法

楊麗蘊(yùn)，張紹林，韓　宏，秦　科

(1.中國(guó)電子技術(shù)標(biāo)準(zhǔn)化研究院，北京 100007；2.電子科技大學(xué) 計(jì)算機(jī)科學(xué)與工程學(xué)院，四川 成都 611731)

基于用戶(hù)QoS預(yù)測(cè)的任務(wù)流調(diào)度算法

楊麗蘊(yùn)1，張紹林2，韓宏2，秦科2

(1.中國(guó)電子技術(shù)標(biāo)準(zhǔn)化研究院，北京 100007；2.電子科技大學(xué) 計(jì)算機(jī)科學(xué)與工程學(xué)院，四川 成都 611731)

摘要:提出在云計(jì)算數(shù)據(jù)中心環(huán)境下，節(jié)省開(kāi)銷(xiāo)并保障用戶(hù)QoS的調(diào)度算法，用預(yù)測(cè)的方式來(lái)判斷QoS走勢(shì)，用任務(wù)流調(diào)度開(kāi)規(guī)避不利的QoS情況。通過(guò)ARIMA預(yù)測(cè)模型對(duì)任務(wù)的QoS進(jìn)行預(yù)測(cè)，根據(jù)預(yù)測(cè)結(jié)果得到有潛在QoS危險(xiǎn)的任務(wù)預(yù)警，并利用一個(gè)粒子群(PSO)和引力搜索(GSA)的混合算法求得最終的調(diào)度策略，最后通過(guò)任務(wù)調(diào)度保障用戶(hù)的QoS，同時(shí)在調(diào)度算法中根據(jù)網(wǎng)絡(luò)擁塞控制的思想添加了一個(gè)保留虛擬機(jī)的方案。實(shí)驗(yàn)表明該算法能有效保障用戶(hù)QoS，比原混合算法減少時(shí)間開(kāi)銷(xiāo)9.26%。

關(guān)鍵詞:云計(jì)算數(shù)據(jù)中心；服務(wù)質(zhì)量；任務(wù)流調(diào)度；ARIMA預(yù)測(cè)模型；粒子群優(yōu)化算法；引力搜索算法

云計(jì)算[1-2]打破了傳統(tǒng)的計(jì)算機(jī)和網(wǎng)絡(luò)資源分配方式，把計(jì)算機(jī)相關(guān)的基礎(chǔ)設(shè)施服務(wù)平臺(tái)以及軟件作為一種服務(wù)提供給用戶(hù)。用戶(hù)根據(jù)自己的需求向提供商購(gòu)買(mǎi)需要的服務(wù)，這種基于訂閱的即付模式[3]受到廣大消費(fèi)者的青睞。由于云計(jì)算低成本的基礎(chǔ)投入以及高效率的應(yīng)用，云計(jì)算的各種應(yīng)用服務(wù)在當(dāng)前的智慧城市和大數(shù)據(jù)中心建設(shè)、運(yùn)營(yíng)及能效管理[4]中起著越來(lái)越重要的作用，成為未來(lái)主流的應(yīng)用模式[5]。

云計(jì)算的管理是虛擬基礎(chǔ)設(shè)施管理的一部分，包括對(duì)虛擬機(jī)管理和對(duì)虛擬機(jī)測(cè)試的管理[6]，它通過(guò)軟件的形式(比如Open Nebula，OpenStack，Eucalyptus，ECP，Overt等)來(lái)實(shí)現(xiàn)云計(jì)算的資源管理[7-8]。面向企業(yè)級(jí)設(shè)計(jì)的傳統(tǒng)資源管理解決方案無(wú)法滿(mǎn)足云計(jì)算對(duì)于管理的要求，由于云計(jì)算環(huán)境下的多租戶(hù)、大規(guī)模，云計(jì)算的動(dòng)態(tài)性以及其他相關(guān)因素，使得云計(jì)算的資源管理成為一個(gè)十分困難的問(wèn)題，而資源調(diào)度則是資源管理中最重要、最困難的一環(huán)。

云計(jì)算的調(diào)度按照用戶(hù)需求給用戶(hù)合理分配資源，實(shí)現(xiàn)云系統(tǒng)的負(fù)載均衡，正確的調(diào)度能夠很大程度上提高云系統(tǒng)的資源利用率，提高系統(tǒng)的容錯(cuò)率，保障系統(tǒng)的穩(wěn)健性。資源調(diào)度問(wèn)題是一個(gè)多目標(biāo)優(yōu)化的NP難問(wèn)題[9]，研究主要集中在對(duì)多目標(biāo)約束情況下的基于全局搜索的啟發(fā)式算法[10-11]。任務(wù)調(diào)度的早期的工作主要關(guān)注于性能和服務(wù)質(zhì)量，目前的調(diào)度研究主要轉(zhuǎn)向以經(jīng)濟(jì)原則為目標(biāo)的調(diào)度。文獻(xiàn)[12-13]把虛擬機(jī)動(dòng)態(tài)遷移作為優(yōu)化目標(biāo)，以此減少能量消耗。文獻(xiàn)[14]掛起優(yōu)先級(jí)相對(duì)較低的任務(wù)，通過(guò)這種方式減少能耗。文獻(xiàn)[15]使用了雙適應(yīng)度的粒子群優(yōu)化算法優(yōu)化任務(wù)的完成時(shí)間和成本。文獻(xiàn)[16]根據(jù)服務(wù)器負(fù)載均衡關(guān)閉不需要的虛擬機(jī)來(lái)達(dá)到節(jié)能目的。文獻(xiàn)[17]把任務(wù)分割成子任務(wù)，放入不同優(yōu)先級(jí)的隊(duì)列中，然后使用改進(jìn)蟻群算法進(jìn)行調(diào)度，使得任務(wù)延遲時(shí)間、調(diào)度公平性及效率方面性能更好。澳大利亞的Rajkumar Buyya等人提出了面向經(jīng)濟(jì)模型的資源調(diào)度方式[18]，他們提出通過(guò)SLA資源分配器來(lái)協(xié)商用戶(hù)和提供商之間的利益，目前這方面的問(wèn)題還在繼續(xù)研究之中。

1預(yù)測(cè)模型和調(diào)度算法

用戶(hù)購(gòu)買(mǎi)云服務(wù)的時(shí)候會(huì)和服務(wù)提供商簽訂SLA[19]，如果服務(wù)提供商違背SLA將會(huì)造成不良影響且支付違約金，因此，服務(wù)提供商在設(shè)計(jì)云系統(tǒng)的時(shí)候需要用各種手段保障用戶(hù)的QoS能夠按照協(xié)議準(zhǔn)時(shí)完成。由于系統(tǒng)中的用戶(hù)任務(wù)繁多，在分配任務(wù)的時(shí)候需要選擇合適的虛擬機(jī)，因此系統(tǒng)將面臨任務(wù)流調(diào)度問(wèn)題。

1.1ARIMA預(yù)測(cè)模型

本文提出一種基于用戶(hù)QoS預(yù)測(cè)的用戶(hù)任務(wù)流調(diào)度，以達(dá)到滿(mǎn)足用戶(hù)QoS的目的。預(yù)測(cè)模型選擇ARIMA(Autoregressive Integrated Moving Average Model)模型[20]，根據(jù)預(yù)測(cè)結(jié)果進(jìn)行合適的任務(wù)調(diào)度，規(guī)避不利的預(yù)測(cè)狀態(tài)。

在ARIMA(p，d，q)模型里，AR表示自回歸，MA表示移動(dòng)平均，I是差分過(guò)程，p代表自回歸項(xiàng)，q代表了移動(dòng)平均項(xiàng)，d對(duì)象序列的平穩(wěn)時(shí)期差分次數(shù)。

式(1)給出了下一時(shí)間點(diǎn)的預(yù)測(cè)值計(jì)算

(1)

式中：c是常數(shù)；φ是自回歸參數(shù)；et是白噪聲；θ是移動(dòng)平均成分。如果在ARIMA(p，d，q)模型中，p，d，q的值能夠被確定，那么可以通過(guò)式以及監(jiān)控?cái)?shù)據(jù)很容易計(jì)算出未來(lái)的預(yù)測(cè)值。

1.2粒子群優(yōu)化算法和引力搜索算法

本文參考了粒子群和引力搜索混合算法(Sahar Mirzayi & Vahid Rafe)[21]，該算法以粒子群算法為基礎(chǔ)，在每次迭代粒子群移動(dòng)的時(shí)候加入了粒子之間的引力作用，使得粒子的搜索范圍更大，搜索精度更高。

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

算法中的位置向量xi=(xi1,xi2,…,xiD)和速度向量vi=(vi1,vi2,…,viD)，D是空間維度。

(2)

(3)

2)引力搜索算法

引力搜索算法把問(wèn)題建模成多個(gè)粒子，每個(gè)粒子受其他粒子的引力作用，引力提供粒子加速度，使得粒子能夠在解空間里移動(dòng)。

粒子群使用Xi來(lái)表示

(4)

(5)

(6)

(7)

(8)

式中：k-best表示在某個(gè)時(shí)間點(diǎn)選取一定數(shù)量處于最優(yōu)位置的粒子，這些粒子將會(huì)對(duì)其他隨機(jī)粒子產(chǎn)生引力，導(dǎo)致新一輪的位置變化。新的粒子速度由當(dāng)前速度加上加速度，加速度由引力計(jì)算得出

(9)

(10)

best(t)=minfitj(t)，j∈1,…,N

(11)

worst(t)=maxfitj(t)，j∈1,…,N

(12)

式中：fitj(t)由式計(jì)算得出。在某個(gè)時(shí)刻t，粒子xi的質(zhì)量用Mi(t)來(lái)表示。粒子的質(zhì)量越大，表示粒子的局部?jī)?yōu)化越好，越接近最優(yōu)解，所以對(duì)其他粒子的引力越大。質(zhì)量Mi(t)根據(jù)下式計(jì)算得出

(13)

(14)

引力算法在迭代過(guò)程中是慢慢區(qū)域穩(wěn)定，因此引力常數(shù)G(t)是逐漸變小的。式(15)給出了引力常數(shù)G(t)的求解

G(t)=Goe-a(1/T)

(15)

式中：初始值Go設(shè)置為100；初始值a設(shè)置為20；參數(shù)T是算法總迭代次數(shù)

引力算法的優(yōu)勢(shì)是有部分粒子的位置是非常優(yōu)化的。為了改進(jìn)提高算法的收斂速度，在每一輪中選取部分優(yōu)化很好的粒子，這部分粒子將對(duì)其他粒子產(chǎn)生引力，選取的數(shù)量直接影響著算法性能，由式(16)給出

(16)

式中：p是粒子總的數(shù)量；i是當(dāng)前迭代次數(shù)。

2基于用戶(hù)QoS預(yù)測(cè)的任務(wù)流調(diào)度算法

文獻(xiàn)[21]介紹的混合算法中沒(méi)有制定在每次調(diào)度前對(duì)的虛擬機(jī)保留方案。由于過(guò)多的保留虛擬機(jī)會(huì)造成資源浪費(fèi)，而過(guò)少的保留虛擬機(jī)會(huì)因?yàn)樘摂M機(jī)的連續(xù)刪除和創(chuàng)建帶來(lái)很大的系統(tǒng)開(kāi)銷(xiāo)和能源浪費(fèi)。因此本文在原混合算法的基礎(chǔ)上提出了虛擬機(jī)的保留方案，虛擬機(jī)保留的數(shù)量參考了網(wǎng)絡(luò)擁塞控制算法的思路，而具體保留哪些虛擬機(jī)則根據(jù)虛擬機(jī)的資源利用率來(lái)判斷。同時(shí)為了確保用戶(hù)的QoS，本文提出一種基于QoS預(yù)測(cè)的調(diào)度模型，通過(guò)任務(wù)流的調(diào)度來(lái)滿(mǎn)足模型中的指標(biāo)。

2.1用戶(hù)QoS預(yù)測(cè)模型

根據(jù)QoS的可浮動(dòng)范圍，將當(dāng)前用戶(hù)QoS狀態(tài)分為了4類(lèi)，如圖1所示：

1)QoS正常區(qū)域：用戶(hù)的任務(wù)能夠非常及時(shí)地得到服務(wù)器的響應(yīng)，用戶(hù)對(duì)當(dāng)前的服務(wù)處于滿(mǎn)意狀態(tài)。

2)QoS預(yù)警區(qū)域：用戶(hù)的任務(wù)能夠得到服務(wù)器的及時(shí)響應(yīng)，但是任務(wù)的QoS響應(yīng)時(shí)間相對(duì)于正常區(qū)域的QoS略高，表明用戶(hù)的QoS處于相對(duì)危險(xiǎn)的區(qū)域。這時(shí)候需要預(yù)測(cè)模塊的預(yù)測(cè)數(shù)據(jù)來(lái)判斷用戶(hù)QoS的走向，如果QoS走向有著嚴(yán)重的下降趨勢(shì)，那么就需要調(diào)度中心對(duì)用戶(hù)的任務(wù)進(jìn)行調(diào)度，確保用戶(hù)的QoS是處于理想?yún)^(qū)域或者向著理想?yún)^(qū)域發(fā)展。

3)QoS危險(xiǎn)區(qū)域：用戶(hù)的任務(wù)的響應(yīng)時(shí)間已經(jīng)快要接近用戶(hù)制定的底線(xiàn)，這時(shí)候如果預(yù)測(cè)模塊的預(yù)測(cè)數(shù)據(jù)表明QoS沒(méi)有處于上升趨勢(shì)，那么就需要調(diào)度中心對(duì)用戶(hù)的任務(wù)進(jìn)行調(diào)度，優(yōu)先給任務(wù)分配資源。

4)QoS失敗區(qū)域：用戶(hù)的任務(wù)沒(méi)能夠得到服務(wù)的及時(shí)響應(yīng)，用戶(hù)任務(wù)將無(wú)法按期完成，這時(shí)候應(yīng)該按照合同計(jì)算對(duì)用戶(hù)產(chǎn)生的損失并且進(jìn)行賠償，因此必須確保用戶(hù)QoS不能到達(dá)失敗區(qū)域。

圖1　用戶(hù)QoS狀態(tài)圖

根據(jù)用戶(hù)QoS的預(yù)測(cè)結(jié)果以及當(dāng)前的監(jiān)控值可以計(jì)算出用戶(hù)的QoS變化趨勢(shì)，通過(guò)變化趨勢(shì)的取值范圍把QoS變化趨勢(shì)分為4個(gè)狀態(tài)：

1)QoS上升：QoS狀態(tài)向著好的方向變化；

2)QoS緩慢降級(jí)：QoS狀態(tài)惡化，速度低速；

3)QoS中速降級(jí)：QoS狀態(tài)惡化，速度中速；

4)QoS高速降級(jí)：QoS狀態(tài)惡化，速度高速。

然后通過(guò)整合QoS狀態(tài)以及QoS的趨勢(shì)，可以得到如表1的QoS預(yù)警決策。相應(yīng)決策那里的預(yù)警策略可以根據(jù)需求進(jìn)行調(diào)整。

表1QoS預(yù)警決策

QoS狀態(tài)QoS趨勢(shì)相應(yīng)決策正常區(qū)域QoS上升正常運(yùn)行正常區(qū)域QoS緩慢降級(jí)正常運(yùn)行正常區(qū)域QoS中速降級(jí)正常運(yùn)行正常區(qū)域QoS高速降級(jí)預(yù)警預(yù)警區(qū)域QoS上升正常運(yùn)行預(yù)警區(qū)域QoS緩慢降級(jí)正常運(yùn)行預(yù)警區(qū)域QoS中速降級(jí)預(yù)警預(yù)警區(qū)域QoS高速降級(jí)預(yù)警危險(xiǎn)區(qū)域QoS上升正常運(yùn)行危險(xiǎn)區(qū)域QoS緩慢降級(jí)預(yù)警危險(xiǎn)區(qū)域QoS中速降級(jí)預(yù)警危險(xiǎn)區(qū)域QoS高速降級(jí)預(yù)警失敗區(qū)域所有告警

2.2混合粒子群調(diào)度算法

2.2.1算法的優(yōu)化目標(biāo)

(17)

2.2.2基于PSO和GSA融合算法的改進(jìn)

文獻(xiàn)[21]融合了PSO算法和GSA算法，該融合算法在之前并沒(méi)有被研究過(guò)，算法使用PSO算法完成粒子的全局搜索，然后使用GSA算法完成粒子的局部搜索任務(wù)，這兩個(gè)算法分工明確，能夠很好解決全局搜索和局部搜索不能兼顧的問(wèn)題，并且通過(guò)實(shí)驗(yàn)表明該融合算法收斂速度快，能夠避免局部最優(yōu)解。但是原文中沒(méi)有提供調(diào)度時(shí)段的虛擬機(jī)保留方案，下面是本文提出的方案。

在任務(wù)流開(kāi)始任務(wù)調(diào)度的時(shí)候首先有2個(gè)表，一個(gè)是虛擬機(jī)表，一個(gè)是待分配任務(wù)表，首先需要根據(jù)云計(jì)算的歷史數(shù)據(jù)從虛擬機(jī)表中選擇下次調(diào)度任務(wù)需要保留的虛擬機(jī)，這是因?yàn)楸Ａ籼摂M機(jī)比刪除然后再新建虛擬機(jī)節(jié)省資源和時(shí)間，但是保留過(guò)多的虛擬機(jī)有可能造成虛擬機(jī)資源浪費(fèi)，并且保留的虛擬機(jī)型號(hào)也不一定和下一次的任務(wù)調(diào)度完全匹配，那么勢(shì)必會(huì)造成大量的資源碎片，降低資源利用率，形成浪費(fèi)。因此需要一個(gè)算法策略來(lái)決定保留虛擬機(jī)的數(shù)量以及保留哪些虛擬機(jī)。

首先是保留虛擬機(jī)的數(shù)量，數(shù)量不宜過(guò)多，也不宜過(guò)少。場(chǎng)景需要在一個(gè)動(dòng)態(tài)模型中找到一個(gè)動(dòng)態(tài)變化的最大值。保留虛擬機(jī)數(shù)量的算法策略有3種：

1)數(shù)量恢復(fù)階段，保留虛擬機(jī)的數(shù)量以乘積方式遞增；

2)數(shù)量保持階段，保留虛擬機(jī)的數(shù)量以小步長(zhǎng)加法的方式增加；

3)數(shù)量回落階段，保留虛擬機(jī)的數(shù)量以倍減的方式遞減。

根據(jù)虛擬機(jī)的歷史數(shù)據(jù)計(jì)算出每個(gè)調(diào)度輪回中，虛擬機(jī)能夠保持良好運(yùn)行狀態(tài)的虛擬機(jī)數(shù)量百分比per_vmn，以及最優(yōu)百分比值opt_vmn，然后根據(jù)現(xiàn)階段虛擬機(jī)的數(shù)量計(jì)算出平均值以及最優(yōu)值，初始數(shù)量設(shè)置為平均值數(shù)量。為了更好理解，現(xiàn)假設(shè)計(jì)算出的平均值為200，最優(yōu)值為733，恢復(fù)階段乘法參數(shù)設(shè)置為2，回落階段乘法參數(shù)同樣為2，保持階段加法步長(zhǎng)為66。虛擬機(jī)數(shù)量保留策略如圖 2所示。確定了保留虛擬機(jī)的數(shù)量以后需要確定具體保留哪些虛擬機(jī)。本文采取的是根據(jù)虛擬機(jī)負(fù)荷來(lái)判斷，保留負(fù)荷高的虛擬機(jī)。

圖2　虛擬機(jī)數(shù)量保留策略示意圖

2.2.3算法流程

在云計(jì)算系統(tǒng)運(yùn)行過(guò)程中，提供商以按需模式向云用戶(hù)提供服務(wù)，并且為了收集分析數(shù)據(jù)，需要對(duì)整個(gè)系統(tǒng)進(jìn)行監(jiān)控，適時(shí)增加虛擬機(jī)數(shù)量以滿(mǎn)足用戶(hù)請(qǐng)求。調(diào)度過(guò)程中調(diào)度中心會(huì)根據(jù)歷史數(shù)據(jù)來(lái)對(duì)任務(wù)進(jìn)行估計(jì)，如果現(xiàn)有虛擬機(jī)無(wú)法滿(mǎn)足用戶(hù)QoS，那么用戶(hù)任務(wù)將被分配到性能更強(qiáng)大的虛擬機(jī)上。調(diào)度中心根據(jù)用戶(hù)待分配任務(wù)列表以及手中的云資源來(lái)對(duì)任務(wù)進(jìn)行調(diào)度。下面是調(diào)度的具體流程：

1)根據(jù)虛擬機(jī)保留方案保留虛擬機(jī)；

2)根據(jù)任務(wù)數(shù)量初始化粒子數(shù)量；

3)在式(3)中設(shè)定粒子群算法初始速度；

4)通過(guò)式(3)計(jì)算粒子的速度；

5)通過(guò)式(2)計(jì)算粒子的位置；

6)通過(guò)式(13)和(14)計(jì)算粒子的質(zhì)量；

7)通過(guò)式(11)找到k_best粒子；

8)通過(guò)式(12)選取位置較差的粒子準(zhǔn)備下一步；

9)通過(guò)式(8)計(jì)算粒子的所受引力；

10)通過(guò)式(9)更新粒子加速度；

11)通過(guò)式(10)更新粒子位置；

12)通過(guò)式(15)更新萬(wàn)有引力參數(shù)G(t)；

13)通過(guò)式(17)找出預(yù)測(cè)值最優(yōu)的粒子解集；

14)檢測(cè)迭代次數(shù)是否達(dá)到最大，不是則返回第4)步；

15)算法結(jié)束。

每一輪迭代都是先通過(guò)PSO算法對(duì)粒子進(jìn)行移動(dòng)，然后再通過(guò)GSA對(duì)部分粒子進(jìn)行局部搜索，這樣2個(gè)算法互相彌補(bǔ)，擴(kuò)大搜索空間以及提高了搜索精度。

3基于CloudSim的模擬仿真實(shí)驗(yàn)分析

本文仿真實(shí)驗(yàn)使用CloudSim(Buyya，Ranjan，& Calheiros)[23]。試驗(yàn)中虛擬機(jī)的定價(jià)方式以及虛擬機(jī)的配置參數(shù)參照Amazon EC2的標(biāo)準(zhǔn)。輸入的任務(wù)是一個(gè)任務(wù)流DAG，每個(gè)任務(wù)的屬性都是一樣的，在CloudSim中文件輸入大小以及輸出大小都設(shè)置為1 Gbyte。

針對(duì)PSO算法的參數(shù)，參考Pandey 在實(shí)驗(yàn)中的設(shè)置[24]，粒子的數(shù)量設(shè)置為任務(wù)數(shù)量的2倍，PSO中粒子初始速度為隨機(jī)數(shù)，最大迭代次數(shù)設(shè)置為400，粒子的慣性值為0.9。GSA算法中的粒子初始速度設(shè)置為0。每次調(diào)度時(shí)間不能大于100 ms，每個(gè)實(shí)驗(yàn)運(yùn)行20次，最終數(shù)據(jù)取平均值。試驗(yàn)中的一個(gè)重要指標(biāo)參照公式，其中ω1和ω2取值都為0.5。

本文主要是根據(jù)歷史數(shù)據(jù)以及系統(tǒng)的監(jiān)控信息來(lái)對(duì)用戶(hù)未來(lái)的QoS情況進(jìn)行預(yù)測(cè)，然后通過(guò)一個(gè)啟發(fā)式的任務(wù)流調(diào)度算法來(lái)對(duì)任務(wù)進(jìn)行調(diào)度，找出最適合用戶(hù)QoS的解，并且這個(gè)解也要盡量減少系統(tǒng)的成本消耗。首先是測(cè)試任務(wù)在虛擬機(jī)上運(yùn)行時(shí)的消耗，消耗分別是任務(wù)的運(yùn)行消耗，其次是任務(wù)的數(shù)據(jù)傳輸消耗。本文選擇以下對(duì)比算法：貪心算法、PSO算法[24]、GSA算法、PSO-GSA融合算法，以及本文的HPSO算法。算法性能指標(biāo)參照式，主要包括任務(wù)的運(yùn)行成本和數(shù)據(jù)傳輸成本。算法的目的是讓這個(gè)成本越低越好。

從圖3可以看出任務(wù)的主要消耗是任務(wù)的運(yùn)行消耗，主要是任務(wù)占用處理器核心進(jìn)行計(jì)算，運(yùn)行消耗占用總消耗的80%以上。在調(diào)度的時(shí)候需要根據(jù)任務(wù)的消耗對(duì)任務(wù)進(jìn)行合理的分配。因?yàn)樘摂M機(jī)的規(guī)格不一，消耗較多的任務(wù)傾向于分配到較大的虛擬機(jī)。

圖3　執(zhí)行任務(wù)的代價(jià)圖

從圖4可以看出，貪心算法在任務(wù)數(shù)量增多以后任務(wù)的執(zhí)行成本有明顯增加。引力搜索算法(GSA)的情況比貪心算法是有明顯改善。這是由于引力搜索算法的全局搜索能力比較差的緣故。粒子群算法(PSO)雖然全局搜索能力依然有限，但是可以給粒子賦予較高的初始速度來(lái)優(yōu)化全局搜索能力，因此PSO的表現(xiàn)要略?xún)?yōu)于GSA。P-G融合改進(jìn)算法因?yàn)槭褂昧Ｗ尤核惴ǖ娜炙阉髂芰?，再利用GSA進(jìn)行每次迭代中的粒子微調(diào)，提高具備搜索能力。本文提出的改進(jìn)算法HPSO因?yàn)樵黾恿颂摂M機(jī)保留方案，在每一輪任務(wù)調(diào)度的時(shí)候?qū)μ摂M機(jī)的保留數(shù)量以及質(zhì)量進(jìn)行算法決策，因此能有效減少資源浪費(fèi)，增加資源利用率。相對(duì)于原算法在任務(wù)數(shù)量較低的時(shí)候沒(méi)有太大變化，當(dāng)任務(wù)達(dá)到1 000的時(shí)候執(zhí)行代價(jià)降低了9.26%。

圖4　執(zhí)行代價(jià)對(duì)比圖

4結(jié)束語(yǔ)

本文研究了如何利用歷史數(shù)據(jù)以及監(jiān)控?cái)?shù)據(jù)來(lái)預(yù)測(cè)用戶(hù)的QoS，然后從用戶(hù)的任務(wù)調(diào)度入手來(lái)確保用戶(hù)的QoS，同時(shí)也降低了系統(tǒng)的資源浪費(fèi)。本文首先研究了一個(gè)用戶(hù)QoS的預(yù)測(cè)模型ARIMA，通過(guò)該模型對(duì)用戶(hù)QoS的狀態(tài)進(jìn)行預(yù)測(cè)，然后根據(jù)預(yù)測(cè)結(jié)果以及當(dāng)前狀態(tài)的監(jiān)控?cái)?shù)據(jù)對(duì)結(jié)果進(jìn)行分類(lèi)，當(dāng)用戶(hù)的QoS狀態(tài)處于預(yù)警狀態(tài)或者危險(xiǎn)狀態(tài)時(shí)通過(guò)云計(jì)算資源管理中心對(duì)用戶(hù)任務(wù)進(jìn)行調(diào)度，分配更合適的資源。其中使用的調(diào)度算法是一個(gè)改進(jìn)的PSO和GSA混合算法，本文彌補(bǔ)了原混合算法在保留虛擬機(jī)方案方面的空缺，通過(guò)實(shí)驗(yàn)證明方案非常成功。

ARIMA模型作為預(yù)測(cè)模型是可行的，但是在預(yù)測(cè)模型中并沒(méi)有考慮云計(jì)算數(shù)據(jù)中心用戶(hù)任務(wù)數(shù)據(jù)的周期性，以及用戶(hù)的QoS偏好屬性，因此在預(yù)測(cè)的準(zhǔn)確性方面還有不小的提升空間。本文對(duì)PSO和GSA融合算法的改進(jìn)缺少大量實(shí)際任務(wù)流數(shù)據(jù)的支撐，因此在虛擬機(jī)保留方案中并沒(méi)能很好地考慮任務(wù)流調(diào)度中的數(shù)據(jù)特性而采取響應(yīng)的策略，添加的虛擬機(jī)保留方案只是不斷地試探虛擬機(jī)的最佳保留數(shù)量，并在該數(shù)量附近區(qū)間內(nèi)不斷循環(huán)，沒(méi)能維持在最佳數(shù)量。

參考文獻(xiàn)：

[1]BUYYA K，YEO C S，VENUGOPAL S， et al. Cloud computing and e merging IT platforms： vision， hype， and reality for delivering computing as the 5th utility[J]. Future veneration computer systems，2009，25(6)：599-616.

[2]ARMBRUST M， FOX A， GRIFFITH R， et al. Above the clouds： a berkeley view of cloud computing[R].Berkeley：UCB/EECS，2009.

[3]LOMBARDI F，DI PIETRO R. Secure virtualization for cloud computing[J]. Journal of network and computer applications，2011，34(4)：1113-1122.

[4]李海波，王潔萍，王衛(wèi)國(guó)，等.數(shù)據(jù)中心能效分析及標(biāo)準(zhǔn)化建議[J].信息技術(shù)與標(biāo)準(zhǔn)化，2012(5)：32-35.

[5]LIN W W，QI D Y. Research on resource self-oranizing model for cloud computing[C]//2010 International Conference on Internet Technology and Applications.[S.l.]：IEEE， 2010：1-5.

[6]余鳳，徐曉鐘，李建軍.基于云計(jì)算IaaS產(chǎn)品測(cè)試技術(shù)的研究[J].電視技術(shù)，2014，38(15)：272-276.

[7]CERBELAUD D， GARG S， HUYLEBROECK J. Opening the clouds： qualitative overview of the state-of-the-art open source VM-based cloud management platforms[C]// Acm/ifip/usenix International Conference on MIDDLEWARE. New York：Springer-Verlag，2009：1821-1829.

[8]WEN X， GU G， LI Q， et al. Comparison of open-source cloud management platforms： OpenStack and OpenNebula[C]//2012 9th International Conference on Fuzzy Systems and Knowledge Discovery (FSKD).[S.l.]：IEEE，2012：2457-2461.

[9]ZHU X， YOUNG D， WATSON B J， et al. 1000 islands： an integrated approach to resource management for virtualized data centers[J]. Cluster computing， 2009， 12(1)：45-57.

[10]LI B， LI J， HUAI J， et al. EnaCloud： an energy-saving application live placement approach for cloud computing environments[C]//Proc. 2009 IEEE International Conference on Cloud Computing. [S.l.]：IEEE， 2009：17-24.

[11]張雨， 李芳， 周濤. 云計(jì)算環(huán)境下基于遺傳蟻群算法的任務(wù)調(diào)度研究[J]. 計(jì)算機(jī)工程與應(yīng)用， 2014， 50(6)：51-55.

[12]WANG X R， WANG Y F. Coordanating power control and performance management for virtualized server clusters[J]. IEEE transactions on parallel and distributed systems， 2011， 22(2)： 245-259.

[13]JUNG G， HILTUNEN M A， JOSHI K R， et al. Mistral： dynamically managing power， performance， and adaptation cost in cloud infrastructures[C]//Proc. 2010 IEEE 30th International Conference on Distributed Computing Systems. [S.l.]：IEEE， 2010：62-73.

[14]SOTOMAYOR B， KEAHEY K， FOSTER I， et al. Enabling cost-effective resource leases with virtual machines[C]//Hot Topics Session in ACM/IEEE International Symposium on High Performance Distributed Computing. [S.l.]：IEEE， 2007：237-240.

[15]封良良， 張?zhí)眨?賈振紅，等. 云計(jì)算環(huán)境下基于改進(jìn)粒子群的任務(wù)調(diào)度算法[J]. 計(jì)算機(jī)工程， 2013， 39(5)：183-186.

[16]CHEN Y， DAS A， QIN W， et al. Managing server energy and operational costs in hosting centers[C]//ACM SIGMETRICS Performance Evaluation Review. [S.l.]：ACM， 2005： 303-314.

[17]魏赟， 陳元元. 基于改進(jìn)蟻群算法的云計(jì)算任務(wù)調(diào)度模型[J]. 計(jì)算機(jī)工程， 2015，41(2)：12-16.

[18]BUYYA R， YEO C S， VENUGOPAL S. Market-oriented cloud computing： vision， hype， and reality for delivering it services as computing utilities[C]//Proc. 10th IEEE International Conference on High Performance Computing and Communications. Dalian：IEEE，2008：26-32.

[19]王潔萍，李海波，高林.云計(jì)算模式下服務(wù)水平協(xié)議標(biāo)準(zhǔn)化研究[J].信息技術(shù)與標(biāo)準(zhǔn)化，2012(10)：22-24.

[20]REHMAN Z U， HUSSAIN O K， HUSSAIN F K， et al. User-side QoS forecasting and management of cloud services[J]. World wide web-internet & web information systems， 2015， 18(6)：1677-1716.

[21]MIRZAYI S， RAFE V. A hybrid heuristic workflow scheduling algorithm for cloud computing environments[J]. Journal of experimental & theoretical artificial intelligence， 2015， 27(6)：721-735.

[22]RASHEDI E， HOSSEIN N，SARYAZDI S. GSA： a gravitational search algorithm[C]// 2012 2nd International Conference on Computer and Knowledge Engineering (ICCKE). [S.l.]：IEEE，2012：2232-2248.

[23]BUYYA R， RANJAN R， CALHEIROS R N. Modeling and simulation of scalable cloud computing environments and the CloudSim toolkit： challenges and opportunities[C]//International Conference on High PERFORMANCE Computing & Simulation. [S.l.]：IEEE， 2009：1-11.

[24]PANDEY S， WU L， GURU S M， et al. A particle swarm optimization-based heuristic for scheduling workflow applications in cloud computing environments[C]//2010 24th IEEE International Conference on Advanced Information Networking and Applications. [S.l.]：IEEE， 2010：400-407.

楊麗蘊(yùn)(1981— )，女，學(xué)士，主要研究方向?yàn)樵朴?jì)算；

張紹林(1985— )，碩士生，主要研究方向?yàn)樵朴?jì)算、大數(shù)據(jù)；

韓宏(1972— )，副教授、博士，主要研究方向?yàn)樵朴?jì)算、信息安全；

秦科(1980— )，副教授、博士，主要研究方向?yàn)樵朴?jì)算、大數(shù)據(jù)。

責(zé)任編輯：時(shí)雯

Workflow scheduling algorithm based on forecast of users’ QoS

YANG Liyun1，ZHANG Shaolin2，HAN Hong2，QIN Ke2

(1.SoftwareEngineeringandEvaluationCenter，ChinaElectronicsStandardizationInstitute，Beijing100007，China；(2.SchoolofComputerScience&Engineering，UniversityofElectronicsScience&TechnologyofChina，Chengdu611731，China)

Abstract:Presenting a model to save the consumption and assure the users QoS in the data center environment of cloud computing. It analyzes the current state of the running tasks according to the results of the QoS prediction assigned by the ARIMA forecasting model. The scheduling policy with the algorithm combined particle swarm optimization(PSO) and gravitational search algorithm(GSA) is calculated according to the analyses of QoS status. A retaining virtual machine algorithm on the basis of the original algorithm is proposed. The retaining algorithm takes the reference to the network congestion control algorithm. Experiment shows that the algorithm could reduce the energy consumption of 9.26% than the original hybrid algorithm.

Key words:data center of cloud computing；QoS；workflow scheduling；ARIMA；PSO；GSA

中圖分類(lèi)號(hào)：TP312

文獻(xiàn)標(biāo)志碼：A

DOI：10.16280/j.videoe.2016.06.017

基金項(xiàng)目：工信部智能制造專(zhuān)項(xiàng)(工業(yè)云服務(wù)模型標(biāo)準(zhǔn)化與試驗(yàn)驗(yàn)證系統(tǒng))

作者簡(jiǎn)介：

收稿日期：2016-05-19

文獻(xiàn)引用格式：楊麗蘊(yùn)，張紹林，韓宏，等.基于用戶(hù)QoS預(yù)測(cè)的任務(wù)流調(diào)度算法[J].電視技術(shù)，2016，40(6)：91-97.

YANG L Y，ZHANG S L，HAN H，et al. Workflow scheduling algorithm based on forecast of users’QoS [J].Video engineering，2016，40(6)：91-97.