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

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

2、： 云計算；蟻群算法；服務模式；調度中圖分類號：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引言由于信息化技術的迅速發(fā)展，網絡上數據逐漸復雜龐大，傳統的并行技術等已不能為

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

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

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

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

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

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

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

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

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

15、的 利用蟻群算法，能夠在未知的網絡拓撲中查找出計算資源，并選擇最合適的一個或者幾 個分配給用戶作業(yè)，直到滿足用戶需求當查找開始時，由 slave 節(jié)點發(fā)出查詢消息，這些消 息扮演著蟻群算法中螞蟻的角色，所有的螞蟻都遵從信息素多的節(jié)點概率大，信息素少的節(jié)點概率少的原則選擇下一跳的節(jié)點，并在經過的路徑節(jié)點上留下信息素設資源選擇的約束函數為ô (t )áninj =(E á (t)ã â, q < q0（1）td in (t) 由公式(2)計算, 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 時刻，前向螞蟻在 i 節(jié)點上觀察到 j 節(jié)點的信息索強度，P 為 k 號螞Cdelay(eij )蟻在 i 點選擇 j 點的概率, avid (k ) 為螞蟻是的回避列表， td ij =為從節(jié)點

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

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

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