基于QoS云計(jì)算任務(wù)調(diào)度優(yōu)化

聶清彬，陳飛旭，秦美峰，曹耀欽

(1.西南交通大學(xué)希望學(xué)院,成都 610400;2.成都文理學(xué)院,成都 610400;3重慶工程學(xué)院,重慶 400065)

近年來,云計(jì)算憑借其低成本、配置靈活和資源利用效率高的優(yōu)勢(shì),正在以極快的速度興起。在云計(jì)算[1-2]中,其資源的分配一直是研究的重點(diǎn),云計(jì)算的用戶可以根據(jù)自己的需求來付費(fèi)和購(gòu)買適合的資源，從而最大程度節(jié)省了成本，給用戶帶來了更好體驗(yàn)。因此，就如何規(guī)劃、利用龐大的云計(jì)算資源問題,國(guó)內(nèi)外學(xué)者從自己的研究中提出了相應(yīng)的觀點(diǎn)。方秋義等[3]采用一種滿足一定條件下的低成本和低負(fù)載的資源分配策略，以此實(shí)現(xiàn)系統(tǒng)的負(fù)載均衡；李志敏等[4]通過在云計(jì)算資源算法中引入人工蜂群算法，算法收斂精度提高，使云計(jì)算資源分配的效率提升；魏杰等[5]將針對(duì)數(shù)據(jù)密集型應(yīng)用的虛擬資源分配,提出云環(huán)境下時(shí)延敏感的虛擬機(jī)放置方法,該方法可以有效地降低總數(shù)據(jù)傳輸時(shí)延和最大數(shù)據(jù)傳輸時(shí)延，獲得較優(yōu)的云計(jì)算資源，從而節(jié)省運(yùn)營(yíng)成本；蔡曉麗等[6]設(shè)計(jì)了一種改進(jìn)的粒子群算法，通過改進(jìn)粒子迭代過程中社會(huì)項(xiàng)系數(shù)和認(rèn)知項(xiàng)系數(shù)的權(quán)重變化,使算法更符合最優(yōu)解的求解規(guī)律,避免陷入局部最優(yōu)解，以此提高資源分配的準(zhǔn)確性；王英等[7]提出了一種基于生產(chǎn)函數(shù)的云服務(wù)提供商收益最大化同時(shí)兼顧用戶滿意度的資源調(diào)度算法，合理規(guī)劃云服務(wù)器所有資源,最大程度優(yōu)化配置資源;然后結(jié)合用戶請(qǐng)求，解決了云數(shù)據(jù)中心資源利用率低、云服務(wù)提供商收益低的問題。

這些算法雖然能夠成功地完成云計(jì)算的資源分配,但由于云計(jì)算技術(shù)的飛速發(fā)展，用戶對(duì)其使用的需求日益提高，用戶在關(guān)注任務(wù)是否能完成的同時(shí)，更加注重于完成調(diào)度的成本和時(shí)間等。在現(xiàn)有研究基礎(chǔ)之上，將傳統(tǒng)蟻群算法進(jìn)行改良得到改進(jìn)的蟻群優(yōu)化算法(improved ant colony optimization algorithm),使算法的效率明顯提高。在處理云計(jì)算資源分配方面的問題時(shí)有了明顯的提升，在減少成本的同時(shí)節(jié)省了任務(wù)所需要的時(shí)間，仿真模擬實(shí)驗(yàn)說明算法在處理云計(jì)算資源分配方面問題時(shí)擁有較好的優(yōu)越度[8]。

1 調(diào)度算法描述

調(diào)度算法是云計(jì)算資源調(diào)度的核心技術(shù)，優(yōu)秀的調(diào)度算法可以保證云計(jì)算資源調(diào)度的高效性和合理性，因此引入傳統(tǒng)的蟻群算法，并對(duì)其進(jìn)行優(yōu)化和改進(jìn)，實(shí)現(xiàn)高效資源調(diào)度[9-13]。

蟻群算法(AG)[14-20]是一種模擬螞蟻覓食行為的模擬優(yōu)化算法，它是由意大利學(xué)者Dorigo M等于1991年首先提出，并首先使用在解決TSP(旅行商問題)上。自然界中的螞蟻從巢穴出發(fā)覓食，通常會(huì)在通過的路徑上留下大量的信息素來引導(dǎo)后面的螞蟻，路徑上信息素積累的越多，其使之后的螞蟻選擇該路徑的概率也就越大，傳統(tǒng)的蟻群算法到最后往往會(huì)出現(xiàn)幾條路徑的信息素高于其他路徑的情況，如果每只螞蟻都將任務(wù)分配給信息素濃度最高的節(jié)點(diǎn)處理，那么就會(huì)出現(xiàn)搜索停滯現(xiàn)象。也就是算法收斂速度過快導(dǎo)致的局部最優(yōu)解，從而無法得到全局最優(yōu)解。因此需要對(duì)傳統(tǒng)的蟻群算法進(jìn)行改進(jìn)和優(yōu)化，以發(fā)現(xiàn)全局最優(yōu)解。在傳統(tǒng)的蟻群算法運(yùn)算的前期階段中各路徑的信息素含量差距不明顯，則螞蟻就更傾向于選擇路程較短的路徑，這就讓距離較短的路徑更容易被后來的螞蟻選擇,導(dǎo)致盲目而局部的搜索，因此為了避免這種情況的出現(xiàn)，為此，在傳統(tǒng)的蟻群算法基礎(chǔ)之上加入隨機(jī)選擇機(jī)制,擴(kuò)大全局尋優(yōu)能力，增加解的多樣性,設(shè)置由參數(shù)q0控制偽隨機(jī)比率，表示如下

(1)

(2)

(3)

2 云計(jì)算任務(wù)分配問題

云計(jì)算任務(wù)分配問題是將n個(gè)任務(wù)通過采用的調(diào)度算法合理地分配到m個(gè)可利用的虛擬節(jié)點(diǎn)資源上，并使得任務(wù)執(zhí)行時(shí)間最短，所消耗成本最低，同時(shí)滿足用戶Qos需求的過程[21-25]。

2.1 云計(jì)算任務(wù)模型

常見的云計(jì)算任務(wù)調(diào)度算法是將一個(gè)任務(wù)劃分成幾個(gè)相對(duì)獨(dú)立的子任務(wù)，再將每個(gè)子任務(wù)分配到相應(yīng)的虛擬資源同時(shí)進(jìn)行計(jì)算，最后再將每個(gè)計(jì)算的結(jié)果進(jìn)行匯總處理，得到最終結(jié)果，研究只對(duì)上述情況中相對(duì)獨(dú)立的子任務(wù)并行計(jì)算的情況做出分析,任務(wù)T是包含n個(gè)元素的任務(wù)集，表示為：T={Task1,Task2…Taski},Taski代表用戶需要處理的任務(wù)。

2.2 云計(jì)算資源模型

2.3 Qos模型

在文獻(xiàn)[11]中提到，云計(jì)算的服務(wù)質(zhì)量(Qos)是衡量用戶對(duì)云計(jì)算滿意程度的一種標(biāo)準(zhǔn)。研究將用戶的開銷需求、任務(wù)完成時(shí)間需求和任務(wù)結(jié)果是否有效可用這3個(gè)方面的Qos需求納入考慮范圍內(nèi)，分別建立開支需求適應(yīng)度因子(payment)、任務(wù)完成時(shí)間適應(yīng)度因子(time)和任務(wù)結(jié)果有效可用性適應(yīng)度因子(usable)。

2.3.1 用戶開支需求適應(yīng)度因子

在分配云計(jì)算資源時(shí)，假設(shè)調(diào)度任務(wù)到被分配的虛擬節(jié)點(diǎn)上，則虛擬節(jié)點(diǎn)集合vm={vm1,vm2…,vmj}，其中任務(wù)Taski對(duì)應(yīng)vmj，且調(diào)度任務(wù)所需要的費(fèi)用不得超過用戶規(guī)定的開支，故資源的分配需要滿足以下約束條件

(4)

式中：GP表示執(zhí)行任務(wù)所需的費(fèi)用，LP表示用戶設(shè)置的開支約束,vmij·p表示任務(wù)Taski在被分配的虛擬節(jié)點(diǎn)上vmj的執(zhí)行費(fèi)用。

(5)

2.3.2 任務(wù)完成時(shí)間需求適應(yīng)度因子

在分配云計(jì)算資源時(shí)，假設(shè)調(diào)度任務(wù)到被分配的虛擬節(jié)點(diǎn)上，則虛擬節(jié)點(diǎn)集合vm={vm1,vm2，…,vmj}，其中任務(wù)Taski對(duì)應(yīng)vmj，且調(diào)度任務(wù)完成時(shí)間不得超過用戶設(shè)置的完成時(shí)間需求，故資源的分配需要滿足以下約束條件

(6)

式中：GT表示任務(wù)實(shí)際完成時(shí)間；LT表示用戶設(shè)置的時(shí)間長(zhǎng)度約束；vmij·t表示任務(wù)Taski在被分配的虛擬節(jié)點(diǎn)上vmj的完成時(shí)間。

(7)

2.3.3 任務(wù)結(jié)果有效可用性適應(yīng)度因子

在分配云計(jì)算資源時(shí)，假設(shè)調(diào)度任務(wù)到被分配的虛擬節(jié)點(diǎn)上，則虛擬節(jié)點(diǎn)集合vm={vm1,vm2…,vmj}，其中任務(wù)Taski對(duì)應(yīng)虛擬機(jī)vmj，且最終虛擬節(jié)點(diǎn)得出的任務(wù)結(jié)果的有效性和可用程度不得低于用戶提出的有效可用性需求，故任務(wù)集所用的虛擬節(jié)點(diǎn)資源的執(zhí)行任務(wù)的有效可用性必須滿足

(8)

其中：GU表示任務(wù)集所選的虛擬節(jié)點(diǎn)資源運(yùn)算結(jié)果的有效可用性；LU表示用戶提出的有效可用性約束；vmij·u表示任務(wù)Taski被分配的虛擬節(jié)點(diǎn)上vmj計(jì)算得到結(jié)果的有效可用性。在資源分配過程中，用戶會(huì)優(yōu)先選擇任務(wù)結(jié)果有效可用性高的虛擬節(jié)點(diǎn)進(jìn)行資源調(diào)度，故任務(wù)Taski在經(jīng)虛擬節(jié)點(diǎn)資源vmj運(yùn)行得出結(jié)果的有效可用性適應(yīng)度因子為

(9)

(10)

(11)

2.4 云計(jì)算資源調(diào)度的綜合適應(yīng)度函數(shù)模型

綜上對(duì)用戶的QoS需求的分析，根據(jù)所得的用戶開支需求適應(yīng)度因子、任務(wù)完成時(shí)間需求適應(yīng)度因子和任務(wù)結(jié)果有效可用性適應(yīng)度因子，可以得到執(zhí)行任務(wù)、分配虛擬節(jié)點(diǎn)資源的綜合適應(yīng)度函數(shù)模型如下

(12)

至此，以資源調(diào)度的適應(yīng)度因子作為引導(dǎo)因子來改進(jìn)傳統(tǒng)的蟻群算法，得到改進(jìn)的蟻群算法公式如下

(13)

式中：tabuk表示已經(jīng)通過的路徑。

3 算法流程

1)初始化：根據(jù)虛擬節(jié)點(diǎn)的計(jì)算能力、帶寬、內(nèi)存等基礎(chǔ)參數(shù)對(duì)蟻群優(yōu)化算法的各項(xiàng)參數(shù)進(jìn)行初始化，其中包括信息素的初始化、虛擬節(jié)點(diǎn)初始價(jià)格的初始化、迭代次數(shù)的初始化、信息素濃度的初始化和任務(wù)執(zhí)行時(shí)間的初始化。創(chuàng)建禁忌列表tabuk用于記錄螞蟻已經(jīng)走過的路徑。

3)根據(jù)改進(jìn)公式(13)計(jì)算每一只螞蟻選擇下一個(gè)相鄰節(jié)點(diǎn)的轉(zhuǎn)移概率，根據(jù)計(jì)算結(jié)果將任務(wù)分配到相應(yīng)的虛擬資源節(jié)點(diǎn)上。

4)當(dāng)任務(wù)被分配到虛擬資源節(jié)點(diǎn)上以后，更新在本次迭代過程中螞蟻通過路徑上的信息素，并將已通過的路徑添加進(jìn)禁忌表tabuk中。

5)重復(fù)執(zhí)行步驟2)～4)，使整個(gè)蟻群任務(wù)集都找到最優(yōu)的路徑為止。

7)對(duì)所有路徑上的信息素進(jìn)行全局更新。

8)迭代次數(shù)累加，判斷是否達(dá)到最大迭代次數(shù)，若未達(dá)到，則繼續(xù)執(zhí)行步驟2),若已達(dá)到最大迭代次數(shù)，則停止搜索，得到的結(jié)果即是云計(jì)算資源分配的最優(yōu)解。

4 實(shí)驗(yàn)測(cè)試與結(jié)果分析

CloudSim 3.0是墨爾本大學(xué)的網(wǎng)絡(luò)實(shí)驗(yàn)室和Gridbus項(xiàng)目推出云計(jì)算仿真軟件。為了驗(yàn)證本文設(shè)計(jì)的改進(jìn)蟻群優(yōu)化算法在處理云計(jì)算資源調(diào)度問題時(shí)的有效性和可行性，使用CloudSim 3.0平臺(tái)，在相同的條件和環(huán)境下進(jìn)行實(shí)驗(yàn)，并與傳統(tǒng)的蟻群算法以及CloudSim 3.0自帶的Min-Min調(diào)度算法的任務(wù)分配結(jié)果進(jìn)行對(duì)比。

實(shí)驗(yàn)中，對(duì)CloudSim 3.0 模擬器進(jìn)行參數(shù)設(shè)置，設(shè)置20個(gè)任務(wù)中心，每個(gè)任務(wù)中心部署10個(gè)虛擬節(jié)點(diǎn)資源，隨機(jī)設(shè)置虛擬節(jié)點(diǎn)的性能，設(shè)置虛擬節(jié)點(diǎn)能力為[1000,2000]MIP,內(nèi)存為[512,2048]MB,帶寬為[5000,10000]b/s,用戶任務(wù)數(shù)量為200～1000個(gè)，在[500,3800]間隨機(jī)設(shè)置任務(wù)長(zhǎng)度，最大迭代次數(shù)為60次。

圖1 算法運(yùn)行的成本比較

從圖1中可以看出當(dāng)任務(wù)數(shù)量較少時(shí)，傳統(tǒng)的蟻群算法、Min-Min調(diào)度算法和改進(jìn)的蟻群優(yōu)化算法在完成云計(jì)算資源調(diào)度方面所消耗的成本大致差別不大，但隨著任務(wù)數(shù)量的增多，傳統(tǒng)的蟻群算法在云計(jì)算資源調(diào)度方面所消耗的成本快速上升，而改進(jìn)的蟻群算法在此方面仍維持較低的成本支出且始終低于Min-Min算法的消耗，這說明提出的改進(jìn)蟻群優(yōu)化算法有效地降低了成本消耗。

從圖2中可以看出，雖然Min-Min調(diào)度算法在任務(wù)和改進(jìn)的蟻群優(yōu)化算法在任務(wù)數(shù)量較少時(shí)完成調(diào)度的時(shí)間相差不大，且都低于傳統(tǒng)的蟻群算法所需要的時(shí)間，但在任務(wù)數(shù)量增加后，改進(jìn)的蟻群優(yōu)化算法在消耗時(shí)間方面的漲幅相對(duì)更小，上升曲線也更平穩(wěn)，故說明提出的改進(jìn)蟻群優(yōu)化算法在任務(wù)完成時(shí)間方面有較好優(yōu)勢(shì)。

圖2 算法運(yùn)行時(shí)間的比較

圖3 算法得出結(jié)果的有效可靠性比較

從圖3中可以看出，在任務(wù)數(shù)量較少時(shí)提出的蟻群優(yōu)化算法得出結(jié)果的有效性低于傳統(tǒng)的蟻群算法和Min-Min調(diào)度算法得出結(jié)果的有效性，但隨著任務(wù)數(shù)量的增加，改進(jìn)的蟻群優(yōu)化算法得出結(jié)果的有效性成正比例上升，并且高于其余2個(gè)算法得出結(jié)果的有效性，而其他2個(gè)算法雖然在任務(wù)數(shù)量較低時(shí)有更高的任務(wù)結(jié)果有效性，但增長(zhǎng)曲線更波折、不穩(wěn)定，故說明提出的改進(jìn)的蟻群優(yōu)化算法在得出的任務(wù)結(jié)果的有效性方面也具有明顯優(yōu)勢(shì)。

5 結(jié) 語

針對(duì)一般云計(jì)算資源調(diào)度問題沒有全面的考慮用戶QoS需求的情況，引入引導(dǎo)因子對(duì)傳統(tǒng)的蟻群算法進(jìn)行優(yōu)化和改良，得到一種改進(jìn)的蟻群優(yōu)化算法，該算法充分的考慮了任務(wù)完成時(shí)間、任務(wù)所需成本和任務(wù)結(jié)果的有效性，以此來綜合得出用戶對(duì)服務(wù)的滿意程度。并對(duì)改進(jìn)算法進(jìn)行模擬仿真實(shí)驗(yàn)，實(shí)驗(yàn)表明，該算法在任務(wù)完成時(shí)間、任務(wù)所需成本和任務(wù)結(jié)果的有效可用性3個(gè)方面均具有明顯的優(yōu)勢(shì)，但在滿足基于用戶QoS需求這3個(gè)方面的同時(shí)，要求能高效地進(jìn)行任務(wù)調(diào)度方面還略有不足，應(yīng)該考慮負(fù)載均衡的問題。