云計(jì)算資源分配中的蟻群算法研究

1、蟻群算法在云計(jì)算資源分配中的應(yīng)用研究張春艷（中國(guó)礦業(yè)大學(xué)計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院, 徐州221116）摘要：針對(duì)目前已提出的云計(jì)算資源調(diào)度模型，提出一種基于蟻群算法的資源分配策略。分配云計(jì)算資源時(shí)，首先在云計(jì)算網(wǎng)絡(luò)中發(fā)現(xiàn)社團(tuán)，探測(cè)可用節(jié)點(diǎn)的計(jì)算能力，然后根據(jù)云計(jì) 算服務(wù)模式特點(diǎn)，通過分析諸如網(wǎng)絡(luò)帶寬占用、線路質(zhì)量、響應(yīng)時(shí)間、任務(wù)費(fèi)用、可靠性等 因素對(duì)資源分配的影響，利用蟻群算法得到一組最優(yōu)的計(jì)算資源。通過在 CloudSim 環(huán)境下 的仿真進(jìn)行分析和比較，這種算法能在滿足云計(jì)算服務(wù)模式的情況下，獲得比其他一些針對(duì) 網(wǎng)絡(luò)的的分配算法更短的響應(yīng)時(shí)間和更強(qiáng)的工作質(zhì)量，從而更加適合在云環(huán)境中使用。 關(guān)鍵詞

2、： 云計(jì)算；蟻群算法；服務(wù)模式；調(diào)度中圖分類號(hào)：TPApplied research of ant colony algorithm in computing clouds resources allocationZHANG Chunyan(Computer science and technology School, Cumt,Xuzhou221116)Abstract: In view of the present scheduling model of cloudscomputing resources, a resource allocation strategy based on a

3、nt colony algorithm is proposed. Distributing cloud calculative resources,first find societies in computing clouds network, detect usable node computing power, and then based on the cloud calculative service mode, through the analysis of the characteristic such as networkbandwidth, line quality, res

4、ponse time, task expenses, other factors on the reliability of resource allocation influence, using the ant colony algorithm to get a set of optimal computing resources.Through analysis and comparison in the simulation under CloudSim environment, this algorithm can satisfy the cloud calculative serv

5、ice mode of the circumstances, get shorter response time and strongerwork quality than some other in network of distribution algorithm, and thereby more suitable for use in the cloud environment.Key words: Cloud computing; ant algorithm; service mode; schedule0引言由于信息化技術(shù)的迅速發(fā)展，網(wǎng)絡(luò)上數(shù)據(jù)逐漸復(fù)雜龐大，傳統(tǒng)的并行技術(shù)等已不能為

6、滿 足人類日益增長(zhǎng)的辦公和科研發(fā)展的需要。一些網(wǎng)絡(luò)模式應(yīng)運(yùn)而生，云計(jì)算作為一種新型的 并行計(jì)算技術(shù)也出現(xiàn)在網(wǎng)絡(luò)上。云計(jì)算作為一種基于互聯(lián)網(wǎng)的新計(jì)算模式，是分布式計(jì)算(Distributed Computing)、并行 計(jì)算(Parallel Computing)和網(wǎng)格計(jì)算(Grid Computing)的進(jìn)一步發(fā)展， 也是這些計(jì)算機(jī)科學(xué) 概念的商業(yè)實(shí)現(xiàn)。它將計(jì)算任務(wù)分布在大量計(jì)算機(jī)構(gòu)成的資源池上，使各種應(yīng)用系統(tǒng)能夠根 據(jù)需要獲取計(jì)算力、存儲(chǔ)空間和各種軟件服務(wù)。云計(jì)算的資源是動(dòng)態(tài)易擴(kuò)展而且虛擬化的， 通過互聯(lián)網(wǎng)提供云計(jì)算是基于互聯(lián)網(wǎng)的超級(jí)計(jì)算模式，通過架構(gòu)一個(gè)分布的、可全球訪問的 資源結(jié)構(gòu)，使數(shù)

7、據(jù)中心在類似互聯(lián)網(wǎng)的環(huán)境下運(yùn)行計(jì)算，即把存儲(chǔ)于個(gè)人電腦、移動(dòng)電話和 其他設(shè)備上的大量信息和處理器資源集中在一起，協(xié)同工作。主要包括三種層次的服務(wù)：基礎(chǔ)設(shè)施即服務(wù)（IaaS）、平臺(tái)即服務(wù)（PaaS）和軟件即服務(wù)（SaaS）1。作者簡(jiǎn)介：張春艷（1985-），女，工科碩士，主要研究方向：云計(jì)算和蟻群算法. E-mail: zhangcy8511近年來(lái)，虛擬化作為云計(jì)算的基石，也一直是一個(gè)炙手可熱的研究領(lǐng)域。虛擬化的浪潮席卷服務(wù)器、存儲(chǔ)、網(wǎng)絡(luò)、PC 機(jī)等各個(gè)領(lǐng)域。虛擬化最突出的優(yōu)勢(shì)就是節(jié)省資金、整合服 務(wù)器、最大化資源利用率。本文提出的蟻群算法分配策略，綜合考慮了云計(jì)算分布的一系列特點(diǎn)，以期實(shí)現(xiàn)在這

8、種 環(huán)境中能夠滿足用戶作業(yè)分配合適資源的需求。1云計(jì)算服務(wù)模式在云計(jì)算服務(wù)模式中，用戶交互接口以 Web Service 方式為各種用戶提供訪問接口，以 獲取用戶需求；配置工具用以在分配的節(jié)點(diǎn)上準(zhǔn)備任務(wù)運(yùn)行環(huán)境；系統(tǒng)管理模塊負(fù)責(zé)管理和 分配所有可用的資源，其核心是保證負(fù)載均衡；服務(wù)目錄是用戶可以訪問的服務(wù)清單；監(jiān)視 統(tǒng)計(jì)模塊負(fù)責(zé)監(jiān)視節(jié)點(diǎn)的運(yùn)行狀態(tài)，并完成用戶使用節(jié)點(diǎn)情況的統(tǒng)計(jì)。用戶交互接口允許用 戶從目錄中選擇并調(diào)用一個(gè)服務(wù)，將請(qǐng)求傳遞給系統(tǒng)管理模塊后，它將為用戶分配合適的資 源, 然后調(diào)用配置工具為用戶準(zhǔn)備運(yùn)行環(huán)境。在云服務(wù)器端, 所有的計(jì)算及存儲(chǔ)資源分布在 不同的節(jié)點(diǎn)上，系統(tǒng)管理員主要是使

9、用一些配置工具和系統(tǒng)管理軟件，一方面可以方便快捷 地為用戶提供計(jì)算和存儲(chǔ)資源，另一方面可以對(duì)這些計(jì)算存儲(chǔ)資源進(jìn)行高效管理，提高資源 利用率。對(duì)于云計(jì)算服務(wù)提供商來(lái)說(shuō), 其核心技術(shù)是如何對(duì)用戶申請(qǐng)的計(jì)算資源進(jìn)行分配和管 理，其效率直接影響整個(gè)云計(jì)算環(huán)境的工作性能。由于云計(jì)算中資源具有自治性、虛擬化等 獨(dú)特的特點(diǎn)，使得原有的針對(duì)單純分布式、網(wǎng)格計(jì)算資源分配和調(diào)度算法已無(wú)法在該環(huán)境中 有效工作。在云計(jì)算中，資源分配的效率非常重要，對(duì)云計(jì)算平臺(tái)的系統(tǒng)綜合性能影響很大。2算法描述基于上述云環(huán)境的特點(diǎn)及服務(wù)模式，我們提出以下資源分配算法。2.1資源分配流程參考 Map/Reduce 計(jì)算系統(tǒng)2，云環(huán)境中的

10、每個(gè)單元可以分為兩大角色：Master 和 Slave， 前者主要配置 NameNode 和 JobTracker 節(jié)點(diǎn)，后者配置 DataNode 和 TaskTracker 節(jié)點(diǎn)。在 資源分配時(shí)由該單元的主作業(yè)調(diào)度節(jié)點(diǎn)（master JobTracker）和該單位所轄各個(gè)節(jié)點(diǎn)集群中 的從任務(wù)分配節(jié)點(diǎn)（slave TaskTracker）共同完成。因此我們可以將云環(huán)境的所有單元中的 節(jié)點(diǎn)分為兩大社團(tuán)結(jié)構(gòu)3，所有的主節(jié)點(diǎn) master JobTracker 和從節(jié)點(diǎn) slave TaskTracker 分別 作為一類社團(tuán)結(jié)構(gòu)。主節(jié)點(diǎn)負(fù)責(zé)調(diào)度構(gòu)成一個(gè)作業(yè)的所有任務(wù)，這些任務(wù)的數(shù)據(jù)資源分布在 不同

11、的用戶鏡像分片中，而用戶鏡像分片處在從節(jié)點(diǎn)存儲(chǔ)資源上，主節(jié)點(diǎn)監(jiān)控任務(wù)執(zhí)行，重 新執(zhí)行失敗的任務(wù)或做錯(cuò)誤處理。從節(jié)點(diǎn)負(fù)責(zé)執(zhí)行由主節(jié)點(diǎn)分派的任務(wù)。從節(jié)點(diǎn)在接到主節(jié) 點(diǎn)的分派后，從節(jié)點(diǎn)開始尋找合適的計(jì)算節(jié)點(diǎn)為其下屬的存儲(chǔ)節(jié)點(diǎn)準(zhǔn)備。首先，該從節(jié)點(diǎn)開 始檢測(cè)自己的計(jì)算資源用量，如果其剩下的計(jì)算資源能夠滿足用戶提交作業(yè)使用量，則分配 自身的計(jì)算資源，如果剩余的資源不足以滿足需要給用戶的最小計(jì)算資源量，則開始搜索云 計(jì)算環(huán)境中其他合適的計(jì)算資源。下面介紹的蟻群分配算法將在這一環(huán)節(jié)中實(shí)現(xiàn)。搜索工作 在一定范圍內(nèi)進(jìn)行，目的是為了防止增加所帶來(lái)的網(wǎng)絡(luò)開銷。若仍舊找不到合適資源，則從 節(jié)點(diǎn)向主作業(yè)調(diào)度節(jié)點(diǎn)提出請(qǐng)求移

12、走該節(jié)點(diǎn)集群中的用戶數(shù)據(jù)鏡像分片。2.2模型及其考慮參數(shù)將 slave 節(jié)點(diǎn)域作為一個(gè)無(wú)向圖 G（V, E），其中 V 是區(qū)域 Area 中所有 slave 節(jié)點(diǎn)的集合，E 是連接各 slave 節(jié)點(diǎn)的網(wǎng)絡(luò)集合。在云計(jì)算網(wǎng)絡(luò)中均勻地劃分成若干個(gè)子區(qū)域，然后給每個(gè)區(qū)域分配相同個(gè)數(shù)的螞蟻，每個(gè)組的螞蟻只在各自的區(qū)域進(jìn)行搜索。其度量標(biāo)準(zhǔn)要考 慮的有如下參數(shù)：預(yù)計(jì)執(zhí)行時(shí)間：time_cost(e)，指路徑 e 盡頭的的計(jì)算資源處理這樣作業(yè)要消耗的時(shí)間。 網(wǎng)絡(luò)延遲，delay(e)，指路徑 e 產(chǎn)生的最大網(wǎng)絡(luò)延遲。網(wǎng)絡(luò)帶寬：bandwidth(e)，指路徑 e 所提供的網(wǎng)絡(luò)最大帶寬。 用戶對(duì)云計(jì)算資源需

13、求的多樣性與偏好性，如何作 Qos 保證。 將預(yù)計(jì)執(zhí)行時(shí)間和網(wǎng)絡(luò)延時(shí)綜合后用變量 td in (t, e) 表示在 t 時(shí)間段內(nèi)該 e 盡頭為 i 計(jì)算資源的所用量。假設(shè)某虛擬機(jī)資源VM i 的特征集合：Ri = ri1 , ri 2 , ri 3 , ri 4 , rim , m 1,5其中，rim 表示一個(gè) K 維對(duì)角矩陣，分別表示 CPU、內(nèi)存的個(gè)數(shù)，帶寬、費(fèi)用及故障率的倒數(shù)。資源VM i 的性能描述矩陣向量是：VM i = Ei1 , Ei 2 , Ei 3 , Ei 4 , Eim , m 1,5其中 Eim 表示 rim 對(duì)應(yīng)的特征值。任務(wù)的 QoS 描述通?？梢圆捎萌蝿?wù)完成時(shí)間、

14、網(wǎng)絡(luò)帶寬、費(fèi)用、可靠性等參數(shù)指標(biāo)來(lái) 量化 QoS，如任務(wù)完成時(shí)間的 QoS 描述包括開始時(shí)間、全部完成時(shí)間、結(jié)束時(shí)間等，使用 時(shí)可選取任務(wù)全部完成時(shí)間作為評(píng)判指標(biāo)。通常第 i 類任務(wù)的一般期待向量可以描述為：Ei = ei1 , ei 2 , ei 3 , ei 4 , eim , m 1,5m其中 eim 分別表示 CPU、內(nèi)存、帶寬等的一般期待，且滿足：2.3蟻群算法尋找最優(yōu)計(jì)算資源描述 eij = 1j =1由于在云計(jì)算環(huán)境中，資源的具體情況不可知，且網(wǎng)絡(luò)沒有一個(gè)固定的拓?fù)浣Y(jié)構(gòu)，所以 整個(gè)云環(huán)境的結(jié)構(gòu)和資源分布及其實(shí)際情況不可預(yù)知在這種情況下，計(jì)算資源的位置和質(zhì) 量對(duì)數(shù)據(jù)節(jié)點(diǎn)來(lái)說(shuō)是不可知

15、的 利用蟻群算法，能夠在未知的網(wǎng)絡(luò)拓?fù)渲胁檎页鲇?jì)算資源，并選擇最合適的一個(gè)或者幾 個(gè)分配給用戶作業(yè)，直到滿足用戶需求當(dāng)查找開始時(shí)，由 slave 節(jié)點(diǎn)發(fā)出查詢消息，這些消 息扮演著蟻群算法中螞蟻的角色，所有的螞蟻都遵從信息素多的節(jié)點(diǎn)概率大，信息素少的節(jié)點(diǎn)概率少的原則選擇下一跳的節(jié)點(diǎn)，并在經(jīng)過的路徑節(jié)點(diǎn)上留下信息素設(shè)資源選擇的約束函數(shù)為ô (t )áninj =(E á (t)ã â, q < q0（1）td in (t) 由公式(2)計(jì)算, q q0jijô(t )á (Eá (t )ãâ

16、td ij (t )P=kijô(t )á (Eá (t )ã , j avid (k )（2） in n â navod (k ) td in (t)0, otherwise time _ cos t (t ) < TLt(e) > EL.bandwidth（3）其中，delay(e) < DLô ij (t ) 為 t 時(shí)刻，前向螞蟻在 i 節(jié)點(diǎn)上觀察到 j 節(jié)點(diǎn)的信息索強(qiáng)度，P 為 k 號(hào)螞Cdelay(eij )蟻在 i 點(diǎn)選擇 j 點(diǎn)的概率, avid (k ) 為螞蟻是的回避列表， td ij =為從節(jié)點(diǎn)

17、Bbandwidth(eij )0i 到節(jié)點(diǎn) j 的線路質(zhì)量，á , â和ã 為信息素、線路質(zhì)量和計(jì)算能力預(yù)測(cè)值的相對(duì)權(quán)重為防 止結(jié)果過快地收斂在局部最優(yōu)解上，設(shè)定隨機(jī)系數(shù) q 0,1 ，常數(shù) q 0,1 ， q0 為 QoS 標(biāo)準(zhǔn)，選擇資源和路徑的過程就是在不滿足 QoS 的情況下尋找滿足限定條件（3）的盡量大的 j 值或者在滿足 QoS 的情況下尋找滿足條件（3）的 P 值。這兩個(gè)值和公式(1)用來(lái)控制螞蟻直接選擇信息素一線路質(zhì)量比最大相鄰節(jié)點(diǎn)的概率3算法調(diào)度工作流程首先，對(duì)用戶的任務(wù)按優(yōu)先級(jí)進(jìn)行排序，然后進(jìn)行分類，分類體現(xiàn)了用戶任務(wù)對(duì)不 同 QoS 的要求和

18、偏好，并依據(jù) QoS 分類利用蟻群算法實(shí)施資源分配與調(diào)度，并將任務(wù)與資 源綁定，運(yùn)行任務(wù)。 其流程如下圖所示：圖 1 算法調(diào)度工作流程Fig. 1 Algorithm scheduling workflow4實(shí)驗(yàn)仿真用云計(jì)算仿真模擬工具 CloudSim 來(lái)模擬一個(gè)云計(jì)算的局部域4，以檢查本算法在這種 特殊的網(wǎng)格環(huán)境中的運(yùn)行情況。該軟件支持模擬新興的云計(jì)算基礎(chǔ)設(shè)施和管理服務(wù)：1)支持建模和安裝大規(guī)模云計(jì)算基礎(chǔ)設(shè)施，包括在單一物理計(jì)算節(jié)點(diǎn)和 java 虛擬機(jī)上 的數(shù)據(jù)中心。2)可對(duì)數(shù)據(jù)中心，服務(wù)代理，調(diào)度和分配策略進(jìn)行建模。3)提供虛擬引擎，有助于在一個(gè)數(shù)據(jù)中心節(jié)點(diǎn)上創(chuàng)建和管理多個(gè)，獨(dú)立和協(xié)同的

19、虛擬服 務(wù)。4)可以靈活地在共享空間和共享時(shí)間分配的處理核心之間切換。 在體系結(jié)構(gòu)上，CloudSim 仿真器采用分層的結(jié)構(gòu)，自底向上由 SimJava，GridSim，CloudSim，用戶代碼四個(gè)層次組成。 下圖分別為使用該算法和最優(yōu)算法任務(wù)完成時(shí)間、計(jì)算能力偏好類任務(wù)及帶寬偏好類任務(wù)比較圖。完成時(shí)間/s60004000200006000 10000 12000 作業(yè)任務(wù)數(shù)/個(gè)最優(yōu)時(shí)間算法 本文算法圖 2 任務(wù)完成時(shí)間比較圖Fig.2 Task completion time comparison chart6CPU個(gè)數(shù)/顆543210ID0ID1ID2ID3 子任務(wù)標(biāo)識(shí)號(hào)/個(gè)最優(yōu)時(shí)間算法 本文算法圖 3 計(jì)算能力偏好類任務(wù)比較圖Fig.3 Computing power preference class task comparison chart4000帶寬/Mb/s3000200010000ID4 ID5 ID6ID7 子任務(wù)標(biāo)識(shí)號(hào)/個(gè)最優(yōu)時(shí)間算法 本文算法圖 4 帶寬偏好類任務(wù)