聶清彬,陳飛旭,秦美峰,曹耀欽
(1.西南交通大學希望學院,成都 610400;2.成都文理學院,成都 610400;3重慶工程學院,重慶 400065)
近年來,云計算憑借其低成本、配置靈活和資源利用效率高的優(yōu)勢,正在以極快的速度興起。在云計算[1-2]中,其資源的分配一直是研究的重點,云計算的用戶可以根據(jù)自己的需求來付費和購買適合的資源,從而最大程度節(jié)省了成本,給用戶帶來了更好體驗。因此,就如何規(guī)劃、利用龐大的云計算資源問題,國內(nèi)外學者從自己的研究中提出了相應的觀點。方秋義等[3]采用一種滿足一定條件下的低成本和低負載的資源分配策略,以此實現(xiàn)系統(tǒng)的負載均衡;李志敏等[4]通過在云計算資源算法中引入人工蜂群算法,算法收斂精度提高,使云計算資源分配的效率提升;魏杰等[5]將針對數(shù)據(jù)密集型應用的虛擬資源分配,提出云環(huán)境下時延敏感的虛擬機放置方法,該方法可以有效地降低總數(shù)據(jù)傳輸時延和最大數(shù)據(jù)傳輸時延,獲得較優(yōu)的云計算資源,從而節(jié)省運營成本;蔡曉麗等[6]設計了一種改進的粒子群算法,通過改進粒子迭代過程中社會項系數(shù)和認知項系數(shù)的權重變化,使算法更符合最優(yōu)解的求解規(guī)律,避免陷入局部最優(yōu)解,以此提高資源分配的準確性;王英等[7]提出了一種基于生產(chǎn)函數(shù)的云服務提供商收益最大化同時兼顧用戶滿意度的資源調度算法,合理規(guī)劃云服務器所有資源,最大程度優(yōu)化配置資源;然后結合用戶請求,解決了云數(shù)據(jù)中心資源利用率低、云服務提供商收益低的問題。
這些算法雖然能夠成功地完成云計算的資源分配,但由于云計算技術的飛速發(fā)展,用戶對其使用的需求日益提高,用戶在關注任務是否能完成的同時,更加注重于完成調度的成本和時間等。在現(xiàn)有研究基礎之上,將傳統(tǒng)蟻群算法進行改良得到改進的蟻群優(yōu)化算法(improved ant colony optimization algorithm),使算法的效率明顯提高。在處理云計算資源分配方面的問題時有了明顯的提升,在減少成本的同時節(jié)省了任務所需要的時間,仿真模擬實驗說明算法在處理云計算資源分配方面問題時擁有較好的優(yōu)越度[8]。
調度算法是云計算資源調度的核心技術,優(yōu)秀的調度算法可以保證云計算資源調度的高效性和合理性,因此引入傳統(tǒng)的蟻群算法,并對其進行優(yōu)化和改進,實現(xiàn)高效資源調度[9-13]。
蟻群算法(AG)[14-20]是一種模擬螞蟻覓食行為的模擬優(yōu)化算法,它是由意大利學者Dorigo M等于1991年首先提出,并首先使用在解決TSP(旅行商問題)上。自然界中的螞蟻從巢穴出發(fā)覓食,通常會在通過的路徑上留下大量的信息素來引導后面的螞蟻,路徑上信息素積累的越多,其使之后的螞蟻選擇該路徑的概率也就越大,傳統(tǒng)的蟻群算法到最后往往會出現(xiàn)幾條路徑的信息素高于其他路徑的情況,如果每只螞蟻都將任務分配給信息素濃度最高的節(jié)點處理,那么就會出現(xiàn)搜索停滯現(xiàn)象。也就是算法收斂速度過快導致的局部最優(yōu)解,從而無法得到全局最優(yōu)解。因此需要對傳統(tǒng)的蟻群算法進行改進和優(yōu)化,以發(fā)現(xiàn)全局最優(yōu)解。在傳統(tǒng)的蟻群算法運算的前期階段中各路徑的信息素含量差距不明顯,則螞蟻就更傾向于選擇路程較短的路徑,這就讓距離較短的路徑更容易被后來的螞蟻選擇,導致盲目而局部的搜索,因此為了避免這種情況的出現(xiàn),為此,在傳統(tǒng)的蟻群算法基礎之上加入隨機選擇機制,擴大全局尋優(yōu)能力,增加解的多樣性,設置由參數(shù)q0控制偽隨機比率,表示如下
(1)
(2)
(3)
云計算任務分配問題是將n個任務通過采用的調度算法合理地分配到m個可利用的虛擬節(jié)點資源上,并使得任務執(zhí)行時間最短,所消耗成本最低,同時滿足用戶Qos需求的過程[21-25]。
常見的云計算任務調度算法是將一個任務劃分成幾個相對獨立的子任務,再將每個子任務分配到相應的虛擬資源同時進行計算,最后再將每個計算的結果進行匯總處理,得到最終結果,研究只對上述情況中相對獨立的子任務并行計算的情況做出分析,任務T是包含n個元素的任務集,表示為:T={Task1,Task2…Taski},Taski代表用戶需要處理的任務。
在文獻[11]中提到,云計算的服務質量(Qos)是衡量用戶對云計算滿意程度的一種標準。研究將用戶的開銷需求、任務完成時間需求和任務結果是否有效可用這3個方面的Qos需求納入考慮范圍內(nèi),分別建立開支需求適應度因子(payment)、任務完成時間適應度因子(time)和任務結果有效可用性適應度因子(usable)。
2.3.1 用戶開支需求適應度因子
在分配云計算資源時,假設調度任務到被分配的虛擬節(jié)點上,則虛擬節(jié)點集合vm={vm1,vm2…,vmj},其中任務Taski對應vmj,且調度任務所需要的費用不得超過用戶規(guī)定的開支,故資源的分配需要滿足以下約束條件
(4)
式中:GP表示執(zhí)行任務所需的費用,LP表示用戶設置的開支約束,vmij·p表示任務Taski在被分配的虛擬節(jié)點上vmj的執(zhí)行費用。
(5)
2.3.2 任務完成時間需求適應度因子
在分配云計算資源時,假設調度任務到被分配的虛擬節(jié)點上,則虛擬節(jié)點集合vm={vm1,vm2,…,vmj},其中任務Taski對應vmj,且調度任務完成時間不得超過用戶設置的完成時間需求,故資源的分配需要滿足以下約束條件
(6)
式中:GT表示任務實際完成時間;LT表示用戶設置的時間長度約束;vmij·t表示任務Taski在被分配的虛擬節(jié)點上vmj的完成時間。
(7)
2.3.3 任務結果有效可用性適應度因子
在分配云計算資源時,假設調度任務到被分配的虛擬節(jié)點上,則虛擬節(jié)點集合vm={vm1,vm2…,vmj},其中任務Taski對應虛擬機vmj,且最終虛擬節(jié)點得出的任務結果的有效性和可用程度不得低于用戶提出的有效可用性需求,故任務集所用的虛擬節(jié)點資源的執(zhí)行任務的有效可用性必須滿足
(8)
其中:GU表示任務集所選的虛擬節(jié)點資源運算結果的有效可用性;LU表示用戶提出的有效可用性約束;vmij·u表示任務Taski被分配的虛擬節(jié)點上vmj計算得到結果的有效可用性。在資源分配過程中,用戶會優(yōu)先選擇任務結果有效可用性高的虛擬節(jié)點進行資源調度,故任務Taski在經(jīng)虛擬節(jié)點資源vmj運行得出結果的有效可用性適應度因子為
(9)
(10)
(11)
綜上對用戶的QoS需求的分析,根據(jù)所得的用戶開支需求適應度因子、任務完成時間需求適應度因子和任務結果有效可用性適應度因子,可以得到執(zhí)行任務、分配虛擬節(jié)點資源的綜合適應度函數(shù)模型如下
(12)
至此,以資源調度的適應度因子作為引導因子來改進傳統(tǒng)的蟻群算法,得到改進的蟻群算法公式如下
(13)
式中:tabuk表示已經(jīng)通過的路徑。
1)初始化:根據(jù)虛擬節(jié)點的計算能力、帶寬、內(nèi)存等基礎參數(shù)對蟻群優(yōu)化算法的各項參數(shù)進行初始化,其中包括信息素的初始化、虛擬節(jié)點初始價格的初始化、迭代次數(shù)的初始化、信息素濃度的初始化和任務執(zhí)行時間的初始化。創(chuàng)建禁忌列表tabuk用于記錄螞蟻已經(jīng)走過的路徑。
3)根據(jù)改進公式(13)計算每一只螞蟻選擇下一個相鄰節(jié)點的轉移概率,根據(jù)計算結果將任務分配到相應的虛擬資源節(jié)點上。
4)當任務被分配到虛擬資源節(jié)點上以后,更新在本次迭代過程中螞蟻通過路徑上的信息素,并將已通過的路徑添加進禁忌表tabuk中。
5)重復執(zhí)行步驟2)~4),使整個蟻群任務集都找到最優(yōu)的路徑為止。
7)對所有路徑上的信息素進行全局更新。
8)迭代次數(shù)累加,判斷是否達到最大迭代次數(shù),若未達到,則繼續(xù)執(zhí)行步驟2),若已達到最大迭代次數(shù),則停止搜索,得到的結果即是云計算資源分配的最優(yōu)解。
CloudSim 3.0是墨爾本大學的網(wǎng)絡實驗室和Gridbus項目推出云計算仿真軟件。為了驗證本文設計的改進蟻群優(yōu)化算法在處理云計算資源調度問題時的有效性和可行性,使用CloudSim 3.0平臺,在相同的條件和環(huán)境下進行實驗,并與傳統(tǒng)的蟻群算法以及CloudSim 3.0自帶的Min-Min調度算法的任務分配結果進行對比。
實驗中,對CloudSim 3.0 模擬器進行參數(shù)設置,設置20個任務中心,每個任務中心部署10個虛擬節(jié)點資源,隨機設置虛擬節(jié)點的性能,設置虛擬節(jié)點能力為[1000,2000]MIP,內(nèi)存為[512,2048]MB,帶寬為[5000,10000]b/s,用戶任務數(shù)量為200~1000個,在[500,3800]間隨機設置任務長度,最大迭代次數(shù)為60次。
圖1 算法運行的成本比較
從圖1中可以看出當任務數(shù)量較少時,傳統(tǒng)的蟻群算法、Min-Min調度算法和改進的蟻群優(yōu)化算法在完成云計算資源調度方面所消耗的成本大致差別不大,但隨著任務數(shù)量的增多,傳統(tǒng)的蟻群算法在云計算資源調度方面所消耗的成本快速上升,而改進的蟻群算法在此方面仍維持較低的成本支出且始終低于Min-Min算法的消耗,這說明提出的改進蟻群優(yōu)化算法有效地降低了成本消耗。
從圖2中可以看出,雖然Min-Min調度算法在任務和改進的蟻群優(yōu)化算法在任務數(shù)量較少時完成調度的時間相差不大,且都低于傳統(tǒng)的蟻群算法所需要的時間,但在任務數(shù)量增加后,改進的蟻群優(yōu)化算法在消耗時間方面的漲幅相對更小,上升曲線也更平穩(wěn),故說明提出的改進蟻群優(yōu)化算法在任務完成時間方面有較好優(yōu)勢。
圖2 算法運行時間的比較
圖3 算法得出結果的有效可靠性比較
從圖3中可以看出,在任務數(shù)量較少時提出的蟻群優(yōu)化算法得出結果的有效性低于傳統(tǒng)的蟻群算法和Min-Min調度算法得出結果的有效性,但隨著任務數(shù)量的增加,改進的蟻群優(yōu)化算法得出結果的有效性成正比例上升,并且高于其余2個算法得出結果的有效性,而其他2個算法雖然在任務數(shù)量較低時有更高的任務結果有效性,但增長曲線更波折、不穩(wěn)定,故說明提出的改進的蟻群優(yōu)化算法在得出的任務結果的有效性方面也具有明顯優(yōu)勢。
針對一般云計算資源調度問題沒有全面的考慮用戶QoS需求的情況,引入引導因子對傳統(tǒng)的蟻群算法進行優(yōu)化和改良,得到一種改進的蟻群優(yōu)化算法,該算法充分的考慮了任務完成時間、任務所需成本和任務結果的有效性,以此來綜合得出用戶對服務的滿意程度。并對改進算法進行模擬仿真實驗,實驗表明,該算法在任務完成時間、任務所需成本和任務結果的有效可用性3個方面均具有明顯的優(yōu)勢,但在滿足基于用戶QoS需求這3個方面的同時,要求能高效地進行任務調度方面還略有不足,應該考慮負載均衡的問題。