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

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

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

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

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

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

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

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

(1)

(2)

(3)

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

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

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

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

2.2 云計算資源模型

2.3 Qos模型

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

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

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

(4)

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

(5)

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

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

(6)

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

(7)

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

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

(8)

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

(9)

(10)

(11)

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

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

(12)

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

(13)

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

3 算法流程

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

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

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

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

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

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

4 實驗測試與結(jié)果分析

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

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

圖1 算法運行的成本比較

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

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

圖2 算法運行時間的比較

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

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

5 結(jié) 語

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