云計算資源分配中的蟻群算法研究.doc

蟻群算法在云計算資源分配中的應(yīng)用研究張春艷（中國礦業(yè)大學(xué)計算機(jī)科學(xué)與技術(shù)學(xué)院, 徐州221116）摘要：針對目前已提出的云計算資源調(diào)度模型，提出一種基于蟻群算法的資源分配策略。分配云計算資源時，首先在云計算網(wǎng)絡(luò)中發(fā)現(xiàn)社團(tuán)，探測可用節(jié)點的計算能力，然后根據(jù)云計 算服務(wù)模式特點，通過分析諸如網(wǎng)絡(luò)帶寬占用、線路質(zhì)量、響應(yīng)時間、任務(wù)費用、可靠性等 因素對資源分配的影響，利用蟻群算法得到一組最優(yōu)的計算資源。通過在 CloudSim 環(huán)境下 的仿真進(jìn)行分析和比較，這種算法能在滿足云計算服務(wù)模式的情況下，獲得比其他一些針對 網(wǎng)絡(luò)的的分配算法更短的響應(yīng)時間和更強(qiáng)的工作質(zhì)量，從而更加適合在云環(huán)境中使用。 關(guān)鍵詞： 云計算；蟻群算法；服務(wù)模式；調(dià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 ant 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, response 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 service 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ù)等已不能為滿 足人類日益增長的辦公和科研發(fā)展的需要。一些網(wǎng)絡(luò)模式應(yīng)運而生，云計算作為一種新型的 并行計算技術(shù)也出現(xiàn)在網(wǎng)絡(luò)上。云計算作為一種基于互聯(lián)網(wǎng)的新計算模式，是分布式計算(Distributed Computing)、并行 計算(Parallel Computing)和網(wǎng)格計算(Grid Computing)的進(jìn)一步發(fā)展， 也是這些計算機(jī)科學(xué) 概念的商業(yè)實現(xiàn)。它將計算任務(wù)分布在大量計算機(jī)構(gòu)成的資源池上，使各種應(yīng)用系統(tǒng)能夠根 據(jù)需要獲取計算力、存儲空間和各種軟件服務(wù)。云計算的資源是動態(tài)易擴(kuò)展而且虛擬化的， 通過互聯(lián)網(wǎng)提供云計算是基于互聯(lián)網(wǎng)的超級計算模式，通過架構(gòu)一個分布的、可全球訪問的 資源結(jié)構(gòu)，使數(shù)據(jù)中心在類似互聯(lián)網(wǎng)的環(huán)境下運行計算，即把存儲于個人電腦、移動電話和 其他設(shè)備上的大量信息和處理器資源集中在一起，協(xié)同工作。主要包括三種層次的服務(wù)：基礎(chǔ)設(shè)施即服務(wù)（IaaS）、平臺即服務(wù)（PaaS）和軟件即服務(wù)（SaaS）1。作者簡介：張春艷（1985-），女，工科碩士，主要研究方向：云計算和蟻群算法. E-mail: 近年來，虛擬化作為云計算的基石，也一直是一個炙手可熱的研究領(lǐng)域。虛擬化的浪潮席卷服務(wù)器、存儲、網(wǎng)絡(luò)、PC 機(jī)等各個領(lǐng)域。虛擬化最突出的優(yōu)勢就是節(jié)省資金、整合服 務(wù)器、最大化資源利用率。本文提出的蟻群算法分配策略，綜合考慮了云計算分布的一系列特點，以期實現(xiàn)在這種 環(huán)境中能夠滿足用戶作業(yè)分配合適資源的需求。1云計算服務(wù)模式在云計算服務(wù)模式中，用戶交互接口以 Web Service 方式為各種用戶提供訪問接口，以 獲取用戶需求；配置工具用以在分配的節(jié)點上準(zhǔn)備任務(wù)運行環(huán)境；系統(tǒng)管理模塊負(fù)責(zé)管理和 分配所有可用的資源，其核心是保證負(fù)載均衡；服務(wù)目錄是用戶可以訪問的服務(wù)清單；監(jiān)視 統(tǒng)計模塊負(fù)責(zé)監(jiān)視節(jié)點的運行狀態(tài)，并完成用戶使用節(jié)點情況的統(tǒng)計。用戶交互接口允許用 戶從目錄中選擇并調(diào)用一個服務(wù)，將請求傳遞給系統(tǒng)管理模塊后，它將為用戶分配合適的資 源, 然后調(diào)用配置工具為用戶準(zhǔn)備運行環(huán)境。在云服務(wù)器端, 所有的計算及存儲資源分布在 不同的節(jié)點上，系統(tǒng)管理員主要是使用一些配置工具和系統(tǒng)管理軟件，一方面可以方便快捷 地為用戶提供計算和存儲資源，另一方面可以對這些計算存儲資源進(jìn)行高效管理，提高資源 利用率。對于云計算服務(wù)提供商來說, 其核心技術(shù)是如何對用戶申請的計算資源進(jìn)行分配和管 理，其效率直接影響整個云計算環(huán)境的工作性能。由于云計算中資源具有自治性、虛擬化等 獨特的特點，使得原有的針對單純分布式、網(wǎng)格計算資源分配和調(diào)度算法已無法在該環(huán)境中 有效工作。在云計算中，資源分配的效率非常重要，對云計算平臺的系統(tǒng)綜合性能影響很大。2算法描述基于上述云環(huán)境的特點及服務(wù)模式，我們提出以下資源分配算法。2.1資源分配流程參考 Map/Reduce 計算系統(tǒng)2，云環(huán)境中的每個單元可以分為兩大角色：Master 和 Slave， 前者主要配置 NameNode 和 JobTracker 節(jié)點，后者配置 DataNode 和 TaskTracker 節(jié)點。在 資源分配時由該單元的主作業(yè)調(diào)度節(jié)點（master JobTracker）和該單位所轄各個節(jié)點集群中 的從任務(wù)分配節(jié)點（slave TaskTracker）共同完成。因此我們可以將云環(huán)境的所有單元中的 節(jié)點分為兩大社團(tuán)結(jié)構(gòu)3，所有的主節(jié)點 master JobTracker 和從節(jié)點 slave TaskTracker 分別 作為一類社團(tuán)結(jié)構(gòu)。主節(jié)點負(fù)責(zé)調(diào)度構(gòu)成一個作業(yè)的所有任務(wù)，這些任務(wù)的數(shù)據(jù)資源分布在 不同的用戶鏡像分片中，而用戶鏡像分片處在從節(jié)點存儲資源上，主節(jié)點監(jiān)控任務(wù)執(zhí)行，重 新執(zhí)行失敗的任務(wù)或做錯誤處理。從節(jié)點負(fù)責(zé)執(zhí)行由主節(jié)點分派的任務(wù)。從節(jié)點在接到主節(jié) 點的分派后，從節(jié)點開始尋找合適的計算節(jié)點為其下屬的存儲節(jié)點準(zhǔn)備。首先，該從節(jié)點開 始檢測自己的計算資源用量，如果其剩下的計算資源能夠滿足用戶提交作業(yè)使用量，則分配 自身的計算資源，如果剩余的資源不足以滿足需要給用戶的最小計算資源量，則開始搜索云 計算環(huán)境中其他合適的計算資源。下面介紹的蟻群分配算法將在這一環(huán)節(jié)中實現(xiàn)。搜索工作 在一定范圍內(nèi)進(jìn)行，目的是為了防止增加所帶來的網(wǎng)絡(luò)開銷。若仍舊找不到合適資源，則從 節(jié)點向主作業(yè)調(diào)度節(jié)點提出請求移走該節(jié)點集群中的用戶數(shù)據(jù)鏡像分片。2.2模型及其考慮參數(shù)將 slave 節(jié)點域作為一個無向圖 G（V, E），其中 V 是區(qū)域 Area 中所有 slave 節(jié)點的集合，E 是連接各 slave 節(jié)點的網(wǎng)絡(luò)集合。在云計算網(wǎng)絡(luò)中均勻地劃分成若干個子區(qū)域，然后給每個區(qū)域分配相同個數(shù)的螞蟻，每個組的螞蟻只在各自的區(qū)域進(jìn)行搜索。其度量標(biāo)準(zhǔn)要考 慮的有如下參數(shù)：預(yù)計執(zhí)行時間：time_cost(e)，指路徑 e 盡頭的的計算資源處理這樣作業(yè)要消耗的時間。 網(wǎng)絡(luò)延遲，delay(e)，指路徑 e 產(chǎn)生的最大網(wǎng)絡(luò)延遲。網(wǎng)絡(luò)帶寬：bandwidth(e)，指路徑 e 所提供的網(wǎng)絡(luò)最大帶寬。 用戶對云計算資源需求的多樣性與偏好性，如何作 Qos 保證。 將預(yù)計執(zhí)行時間和網(wǎng)絡(luò)延時綜合后用變量 td in (t, e) 表示在 t 時間段內(nèi)該 e 盡頭為 i 計算資源的所用量。假設(shè)某虛擬機(jī)資源VM i 的特征集合：Ri = ri1 , ri 2 , ri 3 , ri 4 , rim , m 1,5其中，rim 表示一個 K 維對角矩陣，分別表示 CPU、內(nèi)存的個數(shù)，帶寬、費用及故障率的倒數(shù)。資源VM i 的性能描述矩陣向量是：VM i = Ei1 , Ei 2 , Ei 3 , Ei 4 , Eim , m 1,5其中 Eim 表示 rim 對應(yīng)的特征值。任務(wù)的 QoS 描述通常可以采用任務(wù)完成時間、網(wǎng)絡(luò)帶寬、費用、可靠性等參數(shù)指標(biāo)來 量化 QoS，如任務(wù)完成時間的 QoS 描述包括開始時間、全部完成時間、結(jié)束時間等，使用 時可選取任務(wù)全部完成時間作為評判指標(biāo)。通常第 i 類任務(wù)的一般期待向量可以描述為：Ei = ei1 , ei 2 , ei 3 , ei 4 , eim , m 1,5m其中 eim 分別表示 CPU、內(nèi)存、帶寬等的一般期待，且滿足：2.3蟻群算法尋找最優(yōu)計算資源描述 eij = 1j =1由于在云計算環(huán)境中，資源的具體情況不可知，且網(wǎng)絡(luò)沒有一個固定的拓?fù)浣Y(jié)構(gòu)，所以 整個云環(huán)境的結(jié)構(gòu)和資源分布及其實際情況不可預(yù)知在這種情況下，計算資源的位置和質(zhì) 量對數(shù)據(jù)節(jié)點來說是不可知的 利用蟻群算法，能夠在未知的網(wǎng)絡(luò)拓?fù)渲胁檎页鲇嬎阗Y源，并選擇最合適的一個或者幾 個分配給用戶作業(yè)，直到滿足用戶需求當(dāng)查找開始時，由 slave 節(jié)點發(fā)出查詢消息，這些消 息扮演著蟻群算法中螞蟻的角色，所有的螞蟻都遵從信息素多的節(jié)點概率大，信息素少的節(jié)點概率少的原則選擇下一跳的節(jié)點，并在經(jīng)過的路徑節(jié)點上留下信息素設(shè)資源選擇的約束函數(shù)為 (t )ninj =(E (t) , q q0（1）td in (t) 由公式(2)計算, q q0jij(t ) (E (t )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 ) EL.bandwidth（3）其中，delay(e) DL ij (t ) 為 t 時刻，前向螞蟻在 i 節(jié)點上觀察到 j 節(jié)點的信息索強(qiáng)度，P 為 k 號螞Cdelay(eij )蟻在 i 點選擇 j 點的概率, avid (k ) 為螞蟻是的回避列表， td ij =為從節(jié)點Bbandwidth(eij )0i 到節(jié)點 j 的線路質(zhì)量， , 和 為信息素、線路質(zhì)量和計算能力預(yù)測值的相對權(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 值。這兩個值和公式(1)用來控制螞蟻直接選擇信息素一線路質(zhì)量比最大相鄰節(jié)點的概率3算法調(diào)度工作流程首先，對用戶的任務(wù)按優(yōu)先級進(jìn)行排序，然后進(jìn)行分類，分類體現(xiàn)了用戶任務(wù)對不 同 QoS 的要求和偏好，并依據(jù) QoS 分類利用蟻群算法實施資源分配與調(diào)度，并將任務(wù)與資 源綁定，運行任務(wù)。 其流程如下圖所示：圖 1 算法調(diào)度工作流程Fig. 1 Algorithm scheduling workflow4實驗仿真用云計算仿真模擬工具 CloudSim 來模擬一個云計算的局部域4，以檢查本算法在這種 特殊的網(wǎng)格環(huán)境中的運行情況。該軟件支持模擬新興的云計算基礎(chǔ)設(shè)施和管理服務(wù)：1)支持建模和安裝大規(guī)模云計算基礎(chǔ)設(shè)施，包括在單一物理計算節(jié)點和 java 虛擬機(jī)上 的數(shù)據(jù)中心。2)可對數(shù)據(jù)中心，服務(wù)代理，調(diào)度和分配策略進(jìn)行建模。3)提供虛擬引擎，有助于在一個數(shù)據(jù)中心節(jié)點上創(chuàng)建和管理多個，獨立和協(xié)同的虛擬服 務(wù)。4)可以靈活地在共享空間和共享時間分配的處理核心之間切換。 在體系結(jié)構(gòu)上，CloudSim 仿真器采用分層的結(jié)構(gòu)，自底向上由 SimJava，GridSim，CloudSim，用戶代碼四個層次組成。 下圖分別為使用該算法和最優(yōu)算法任務(wù)完成時間、計算能力偏好類任務(wù)及帶寬偏好類任務(wù)比較圖。完成時間/s60004000200006000 10000 12000 作業(yè)任務(wù)數(shù)/個最優(yōu)時間算法 本文算法圖 2 任務(wù)完成時間比較圖Fig.2 Task completion time comparison chart6CPU個數(shù)/顆543210ID0ID1ID2ID3 子任務(wù)標(biāo)識號/個最優(yōu)時間算法 本文算法圖 3 計算能力偏好類任務(wù)比較圖Fig.3 Computing power preference class task comparison chart4000帶寬/Mb/s3000200010000ID4 ID5 ID6ID7 子任務(wù)標(biāo)識號/個最優(yōu)時間算法 本文算法圖 4 帶寬偏好類任務(wù)比較圖Fig.4 Bandw