基于云計算的ACO-K中心點資源優(yōu)化算法

孟 穎，羅 可，劉建華，姚麗娟

長沙理工大學 計算機與通信工程學院，長沙 410114

基于云計算的ACO-K中心點資源優(yōu)化算法

孟 穎，羅 可，劉建華，姚麗娟

長沙理工大學 計算機與通信工程學院，長沙 410114

1 引言

云計算[1]作為當前的一個研究熱點，主流的信息技術公司，如Amazon，IBM，Google，都對此先后提出各自的云計算基礎架構。云計算（cloud computing）是指通過互聯網連接的超級計算模式，包含分布式處理（distributed computing）、并行處理（parallel computing）和網格計算（grid computing）的相關技術。云計算是一種新興的計算模型，是集分布式操作系統、分布式數據庫、網格計算等技術于一體的計算機網絡模型，它可以充分地利用硬件資源和軟件資源。

云計算代表IT領域向集約化、規(guī)模化與專業(yè)化道路發(fā)展的趨勢，是IT領域正在發(fā)生的深刻變革[2]。當前，云計算發(fā)展還面臨著許多問題。隨著云計算的不斷普及，計算資源問題的重要性逐步上升，已成為制約其發(fā)展的重要因素。然而，存儲資源如何快速地路由，減少路由間的動態(tài)負荷，兼顧全局負載平衡，得到一組最優(yōu)的計算資源，是人們有待解決的難題。

ACO（Ant Colony algorithm）是一種仿生優(yōu)化算法，它模擬螞蟻的覓食行為來解決復雜的組合優(yōu)化問題，具有智能搜索、全局優(yōu)化、魯棒性、分布式計算和容易與其他算法相結合等優(yōu)點。ACO的應用范圍幾乎已經涉及到各個優(yōu)化領域。K中心點（K-medoids）算法屬于劃分方法的一種，在處理異常數據和噪聲數據方面更為魯棒，不易受極端數據的影響，在聚類算法中應用很廣泛。

ACO-K中心點算法是一種新的聚類算法，它結合這兩種算法的優(yōu)點，全局搜索能力強，處理異常數據優(yōu)越，數據之間的差異性更小。根據云計算環(huán)境的特點，本文提出一種基于云計算環(huán)境下的ACO-K中心點資源分配優(yōu)化算法。該算法能夠在云計算中快速、合理地路由，減少動態(tài)負荷，兼顧全局負載平衡，得到最優(yōu)的計算資源，提高云計算的效率。

2 預備知識

2.1 云計算簡介

IBM公司在技術白皮書“Cloud Computing”中對云計算的定義[3]：云計算一詞用來同時描述一個系統平臺或者一種類型的應用程序。一個云計算的平臺按需進行動態(tài)地部署（provision）、配置（configuration）、重新配置（reconfigure）以及取消服務（deprivation）等。高級的云計算通常包含一些其他的計算資源，例如存儲區(qū)域網絡（SANs）、網絡設備、防火墻以及其他安全設備等。云計算描述了一種可以通過互聯網Internet進行訪問的可擴展應用程序，使用大規(guī)模的數據中心以及功能強勁的服務器來運行網絡應用程序與網絡服務。

根據云計算環(huán)境的特點[4]，提供設備的規(guī)模會根據用戶對資源的需求量來動態(tài)地增大或者縮小。比如用戶需要用N個進程，云計算環(huán)境就分配給該用戶R的計算資源；如果用戶將進程數增加到2N，則用戶的計算資源占有量將動態(tài)地擴展到2R。云計算體現了“網絡就是計算機”的思想。將大量計算資源、存儲資源與軟件資源鏈接在一起，形成巨大規(guī)模的共享虛擬IT資源[5]。在云計算環(huán)境中，帶寬需要被充分地利用，一個行之有效的方法便是盡量為存儲節(jié)點的數據資源分配本地的計算資源。所以，云計算對計算資源分配算法有著苛刻的要求。

本文綜合考慮云計算的特點，提出ACO-K中心點資源分配優(yōu)化算法。通過對存儲節(jié)點分配最合適的計算資源，來最大程度地提高云計算的效率。盡量為存有用戶鏡像的存儲節(jié)點，分配本地或鄰近帶寬需求少的計算節(jié)點。

2.2 ACO算法簡介

蟻群算法是一種受自然界生物的行為啟發(fā)而產生的“自然”算法[6]，它模擬螞蟻的覓食行為來解決復雜的組合優(yōu)化問題。蟻群算法具有智能搜索、全局優(yōu)化、魯棒性、分布式計算和容易與其他算法相結合等優(yōu)點，基本原理如圖1。其中，A為蟻穴，B為食源。

圖1 蟻群聚類示意圖

螞蟻在覓食過程中能在所經過的路徑上留下一種稱為信息素的物質，而螞蟻能夠感知這種物質及其強度，并以此指導自己的運動方向，它們會朝著該物質強度高的方向移動[7]。因此，由大量螞蟻組成的集體覓食行為表現出：某一路徑越短，該路徑上走過的螞蟻就越多，則留下的信息素強度就越大，后來的螞蟻選擇該路徑的概率就越大。螞蟻個體之間就是通過這種信息交流來選擇最短路徑并達到搜索食物的目的。

2.3 K中心點算法簡介

K-中心點聚類算法的核心是中心點的選擇[8]。假設聚類C原先的中心點是Oc_old，現擬改為Oc_new，根據數據對象屬于和其距離最近的聚類原則，可能引起各數據對象所屬聚類的情況發(fā)生調整。對于原先聚類C中的數據對象p可能有如下情況：

（1）p與Oc_new的距離仍然小于其他聚類的中心點的距離，因此p仍屬于聚類C如圖2（a），用Oc_new代替Oc_old，數據對象p的代價為：d(p，Oc_new)-d(p，Oc_old)，d表示兩點之間的距離。

（2）p與其他某一聚類r的中心點的距離最短，則p將改屬于聚類r如圖2（b），用Oc_new代替Oc_old，數據對象p的代價為：d(p，Or)-d(p，Oc_old)，其中Or為聚類r的中心點，此時代價為正值。

類似地，原先聚類C外的任意數據對象 p也可能有兩種情況：

（1）p仍然與它原先所屬的聚類的中心點距離最短，則p仍將屬于原先的聚類如圖2（c），用Oc_new代替Oc_old，數據對象p的代價不變。

（2）在所有聚類的中心點中，p與Oc_new的距離最短，則p將改屬于聚類Oc_new如圖2（d），用Oc_new代替Oc_old，數據對象p的代價為：d(p，Oc_new)-d(p，Or)，其中Or為聚類r的中心點，此時代價為負值。

圖2 K中心優(yōu)化示意圖

2.4 ACO-K中心點算法簡介

ACO-K中心點算法基本原理是從蟻群中隨機選取m個對象，計算任意兩個對象之間的距離，確定蟻群間的距離和最初的聚類中心，并將此中心作為蟻群的歷史最優(yōu)位置，使用K中心點法對歷史最優(yōu)位置進行聚類分析，找到新的聚類中心，來代替蟻群聚類中心。

ACO-K中心點聚類算法：

步驟1對蟻群進行初始化操作，選擇螞蟻數目為m，NC-max為最大迭代次數，m個螞蟻作為初始中心點，設初始中心點為(M1，M2，…，Mm)。

步驟3根據K-medoids法對蟻群的歷史最優(yōu)位置進行新的聚類分析，確定每只螞蟻所在的聚類以及類與類之間的中心點。

步驟4對形成的新蟻群按照步驟2的方法，計算每只螞蟻代表的最優(yōu)解，更新蟻群的歷史最優(yōu)位置和全局最優(yōu)解。

步驟5重新計算任意螞蟻之間的歐氏距離，確定新的聚類中心Oj，找到最優(yōu)路徑。

步驟6如果達到結束條件（取得最終的最優(yōu)聚類中心或者最優(yōu)路徑），則結束，否則轉向步驟3。

3 算法描述

3.1 資源分配策略

云計算的框架是每個單元由一個單獨的主作業(yè)調度節(jié)點和該單元所轄各個節(jié)點集群中的一個從任務分配節(jié)點共同組成[9]。主節(jié)點負責調度構成一個作業(yè)的所有任務，這些任務的數據資源分布在不同從節(jié)點的存儲資源上的用戶鏡像分片中，主節(jié)點監(jiān)控它們的執(zhí)行。從節(jié)點負責執(zhí)行由主節(jié)點指派的任務。在接到主節(jié)點的指派之后，從節(jié)點開始為其下屬的存儲節(jié)點尋找合適的計算節(jié)點。首先，從節(jié)點開始檢測自身的計算資源余量，如果其剩余計算資源足以滿足用戶提交作業(yè)的用量，則優(yōu)先分配自身的計算資源；如果資源已經耗盡或者已不足以滿足給用戶的最小計算資源量，則從節(jié)點報請主節(jié)點搜尋云環(huán)境中其他合適的計算資源。

本文將ACO-K中心點資源分配優(yōu)化算法應用到這一環(huán)節(jié)中。為了減少網絡開銷，在一定范圍內進行搜索。如果云環(huán)境中仍然沒有合適資源，則主節(jié)點移走該節(jié)點集群中的用戶數據鏡像分片。

3.2 資源優(yōu)劣度分析

將節(jié)點域（Slave）看作是一個無向圖G(V，E)[10]，其中，V是區(qū)域Area中所有Slave節(jié)點的集合，E是連接各Slave節(jié)點的網絡集合。尋找合適的計算節(jié)點，即在E中尋找一條最優(yōu)的路徑e∈Area。從以下幾個方面分析資源優(yōu)劣度。

執(zhí)行時間：time_cost(e)，指路徑e盡頭的計算資源處理該作業(yè)預計的耗費時間。

網絡帶寬：bandwidth(e)，指路徑e所提供的網絡最大帶寬。

網絡延遲：delay(e)，指路徑e產生的最大網絡延遲。選擇資源和路徑的過程就是尋找滿足限制條件的盡量小的路徑和資源。資源選擇的約束函數為：

其中，A，B，C為三個約束條件的權重；TL，EL和DL為其邊界限制條件。

當各個計算資源完成本次作業(yè)執(zhí)行速度，對其速度進行預測時，由于每個計算節(jié)點當前的負載程度已知，并且上一次完成作業(yè)時的平均負載程度也能夠查閱。設定執(zhí)行速度為：

其中，RVakm(k)為第m號計算資源的第k次預測執(zhí)行速度，ak為第k次預測時的系統負載程度，RVakm(k)為第m號計算資源的第k次實際的執(zhí)行速度，θ為調節(jié)參數，用來調節(jié)在不同云環(huán)境中經驗值和預測值的比重，使預測達到最優(yōu)。

3.3 ACO-K中心點算法找最優(yōu)計算資源

3.3.1 算法思想

由于在云計算環(huán)境中，資源的具體情況不可知，利用ACO-K中心點算法，能夠在未知的網絡拓撲中查找出計算資源，并選擇最合適的一個或者幾個分配給用戶作業(yè)，直到滿足用戶需求。當查找開始時，由所有的Slave節(jié)點發(fā)出查詢消息，這些消息扮演著蟻群算法中螞蟻的角色，所有的螞蟻都遵從信息素多的節(jié)點概率大，信息素少的節(jié)點概率小的原則選擇下一跳的節(jié)點，并在經過的路徑節(jié)點上留下信息素。

假設t時刻，在i節(jié)點的螞蟻k遵循公式（3），計算下一跳各個節(jié)點n的可能性：

其中，τij(t)為t時刻螞蟻在i節(jié)點上觀察到 j節(jié)點的信息素強度，在分布式環(huán)境下充分利用蟻群算法的分布式特性及本質并行性進行操作和實現；pkij為螞蟻k在i節(jié)點選擇j節(jié)點的概率；avid(k)為螞蟻k的回避列表，avid(k)以單項列表的形式給出，大小為蟻群的最大規(guī)模，Lqij為從i節(jié)點到 j節(jié)點的線路質量，α、β、γ分別為信息素、線路質量和計算能力預測值相對權重；q在0至1之間隨機選取，q0為初始化時所給的閾值。

3.3.2 信息素更新

隨著時間的推移，以前留下的信息素逐漸消失，為了及時反映信息素的變化，用局部更新策略來改變節(jié)點上的信息素強度。

本次覓食相遇并完成用戶連接，將本次覓食最短通道上的信息素按下式調整，更新全局信息素。

其中，ρ為局部信息素揮發(fā)系數，ε為全局信息素揮發(fā)系數，α為信息素的相對權重。

3.4 算法步驟與流程圖

算法步驟：

步驟1對蟻群進行初始化操作。設置蟻群最大規(guī)模，選擇螞蟻Ai數目，初始中心點為(M1，M2，…，Mm)。

步驟2在存儲資源所在從節(jié)點中選擇帶信息素的螞蟻，并判斷信息素強度。

步驟3該蟻群通過公式（3）、（4）、（5）來選擇下一跳的節(jié)點。

步驟4當螞蟻Ai進入一個Slave節(jié)點Vj時，Vj將 Ai設置到回避列表avid(k)中，回避列表大小由螞蟻的數量決定，并通過限制條件公式（1），判斷Vj是否為有效節(jié)點。如果Vj滿足限制條件，則標記為有效節(jié)點，并用公式（6）、（7）更新信息素。如果Vj不是有效節(jié)點，則轉向步驟3。

步驟5將步驟4得到的有效節(jié)點進行資源分配，分配給用戶作業(yè)調度，為防止算法過快收斂，用公式（2）對其速度進行預測。

步驟6當Ai全在回避列表或者Slave節(jié)點未與第二個節(jié)點相連，螞蟻Ai無法繼續(xù)前進，該螞蟻自動消亡。若Ai滿足終止條件，算法結束，否則轉向步驟2；若Ai不全在回避列表，則轉向步驟3。

步驟7如果達到終止條件（找到的計算資源不滿足用戶要求或者螞蟻全部消亡），則算法結束，否則轉向步驟2。

算法結束時，所有計算資源不足以滿足協議（SLA）中的用戶要求，則考慮轉移該存儲節(jié)點的用戶鏡像分片至其他存儲節(jié)點。按有效資源集將作業(yè)分配到相關計算資源節(jié)點，并盡量為高有效度的節(jié)點分配多的作業(yè)，以減低網絡的負載。算法流程圖如圖3。

圖3 算法流程圖

3.5 算法復雜度分析

3.5.1 算法的空間復雜度

算法的空間復雜度：蟻群最大規(guī)模Max_m，中心點個數m，節(jié)點數Num_Slave，聚類個數n。由于蟻群最大規(guī)模Max_m比聚類個數n要大得多，所以，算法總體的空間復雜度T=O(Max_m×Num_Slave×m)。

3.5.2 算法的時間復雜度

初始化種群時間復雜度為T=O(n×Max_m)，執(zhí)行速度時間復雜度為T=O(V2×n)，選擇下一跳節(jié)點時間復雜度為T=O(k×p)，信息素更新時間復雜度為：T=O(τ2×ρ+ τ×ρ)，所以本文算法的總體時間復雜度可寫為：To=O(n3)。

4 仿真實驗

4.1 實驗環(huán)境

實驗環(huán)境為Inter?CoreTM2 Duo 2.93 GHz，RAM3 GB，硬盤320 GB，100 MB網絡帶寬，操作系統Windows XP。用Gridsim來模擬一個云計算的局部域，以檢查ACO-K中心點算法在這種特殊的網格環(huán)境中的運行情況。

通過Gridsim中的GridResource類和一系列的輔助類，模擬云計算的網絡資源，構建較擬真的云環(huán)境。通過設定Grid Information Services類來管理資源。

4.2 實驗結果

下面分別用退火算法（SA）、遺傳算法（GA）、蟻群算法（ACO）[11]與本文的ACO-K中心點算法進行對比分析，每種算法運行20次取其平均值，來比較實驗結果的優(yōu)越性。

[12]對螞蟻數據結構進行設置如表1。對上述四種算法主要參數的設置如表2，考慮到開銷問題本文選取50只螞蟻。每種算法搜尋20%可用節(jié)點的仿真結果如圖4，搜尋5%可用節(jié)點的仿真結果如圖5，四種算法的模擬結果連續(xù)曲線圖如圖6。

表1 螞蟻數據結構表

表2 算法主要參數取值表

圖4 搜尋20%可用節(jié)點仿真圖

在1 000個節(jié)點中模擬在一定比例的有效節(jié)點中搜尋50%節(jié)點分配給用戶作業(yè)。比如有效節(jié)點比例為20%，其數量為200個。只要搜尋到100個有效節(jié)點即認為分配成功。

圖5 搜尋5%可用節(jié)點仿真圖

圖6 仿真結果曲線圖

從圖6中可以看出，橫坐標為有效節(jié)點的比率，縱坐標為有效節(jié)點成功分配作業(yè)的耗時，ACO-K中心點算法在節(jié)點較多，有效資源較少的情況下，鼓勵螞蟻選擇負載小的鏈路，以達到網絡負載平衡，工作效率明顯比另外幾種算法效率高。所以本文ACO-K中心點算法在云計算環(huán)境中更具有優(yōu)勢，大大提高了云計算的效率。

5 結束語

本文提出了基于云計算環(huán)境下的ACO-K中心點資源分配優(yōu)化算法，該算法能夠針對云環(huán)境的大規(guī)模性、共享性和動態(tài)性等特點，在云計算中快速、合理地路由，為用戶分配最優(yōu)資源，通過螞蟻選擇負載小的鏈路，克服云計算不能兼顧全局負載平衡的問題。最后，通過仿真實驗，分析帶寬占用、線路質量和響應時間等因素對資源分配的影響，并將SA、GA、ACO與ACO-K中心點算法進行對比分析，驗證了ACO-K中心點資源分配優(yōu)化算法能夠在云計算環(huán)境中動態(tài)地為用戶的作業(yè)分片搜尋并分配計算資源，有效地完成計算資源搜索與分配的工作，從而提高云計算的效率。但是，如何減少蟻群搜索時間，降低搜索成本和時間復雜度，將是下一步研究的重點。

參考文獻：

[1]Tian Guanhua，Meng Dan，Zhan Jianfeng.Reliable resource provision policy for cloud computing[J].Chinese Journal of Computers，2010，33（10）：1859-1872.

[2]Chen Kang，Zheng Weimin.Cloud computing：system instances and current research[J].Journal of Software，2009，20（5）：1337-1348.

[3]Boss G，Malladi P，Quan D，et al.Cloud computing[Z].[S.l.]：IBM，2007：4-6.

[4]Ian F，Yong Z，Ioan R，et a1.Cloud computing and grid computing 360-degree compared[C]//Grid Computing Environments Workshop.[S.l.]：IEEE Press，2008：1-10.

[5]Feng D G，Zhang M，Zhang Y，et al.Study on cloud computing security[J].Journal of Software，2011，22（1）：71-83.

[6]徐曉華，陳凌.一種自適應的螞蟻聚類算法[J].軟件學報，2006，17（9）：1884-1889.

[7]劉波，潘久輝.基于蟻群優(yōu)化的分類算法的研究[J].計算機應用與軟件，2007（24）：50-53.

[8]孫勝，王元珍.基于核的自適應K-Medoids聚類[J].計算機工程與設計，2009，30（3）：674-688.

[9]鄭湃，崔立真，王海洋，等.云計算環(huán)境下面向數據密集型應用的數據布局策略與方法[J].計算機學報，2010，33（8）：1472-1480.

[10]史恒亮，白光一，唐振民，等.基于蟻群優(yōu)化算法的云數據庫動態(tài)路徑規(guī)劃[J].計算機科學，2010，37（5）：143-145.

[11]華夏渝，鄭駿，胡文心.基于云計算環(huán)境的蟻群優(yōu)化計算資源分配算法[J].華東師范大學學報，2010（1）：127-134.

[12]Pan Daru，Yuan Yanbo.ImprovedQoS routing algorithm based on the AntNet[J].Mini-Micro Systems，2006，27（7）：1169-1174.

MENG Ying,LUO Ke,LIU Jianhua,YAO Lijuan

Institute of Computer and Communication Engineering,Changsha University of Sciences and Technology,Changsha 410114,China

Cloud computing has

increasingly attention from network computing model research,which can realize several kinds of resource sharing and dynamic resource allocation.However,how to effectively route storage resource in cloud,reduce dynamic load and take into account global load balancing are important problems to be solved.ACO is a bionics optimization algorithm with advantages of strong robustness,intelligent search,global optimization,easy to combine with other algorithms. K-medoids is an improved algorithm of k-means,of strong robustness and less susceptible to the impact of extreme data.Combined with priorities of these two algorithms,this paper proposes a kind of ACO-K-medoids resource allocation and optimization algorithm based on cloud computing.The algorithm can get the optimal computing resources and improve efficiency of cloud computing.Simulation experiments in the end of paper verify the efficiency of this algorithm.

cloud computing;resource allocation;K-medoids algorithm;ant colony algorithm;dynamic load

云計算是計算網絡模型研究的熱點領域，能實現幾種資源共享和資源動態(tài)配置。然而，云計算中存儲資源如何快速路由，減少動態(tài)負荷，兼顧全局負載平衡是有待解決的問題。ACO是一種仿生優(yōu)化算法，具有健壯性強、智能搜索、全局優(yōu)化、易與其他算法結合等優(yōu)點。K中心點算法是K均值的改進算法，魯棒性強，不易受極端數據的影響。結合這兩種算法的優(yōu)點，提出一種基于云計算環(huán)境下的ACO-K中心點資源分配優(yōu)化算法，得到最優(yōu)的計算資源，提高云計算的效率。通過仿真驗證了該算法的有效性。

云計算；資源分配；K中心點算法；蟻群算法（ACO）；動態(tài)負荷

A

TP391

10.3778/j.issn.1002-8331.1108-0378

MENG Ying,LUO Ke,LIU Jianhua,et al.ACO-K medoids resource optimization algorithm based on cloud computing. Computer Engineering and Applications,2013,49（5）：103-107.

國家自然科學基金（No.11171095，No.10871031）；湖南省自然科學衡陽聯合基金（No.10JJ8008）；湖南省科技計劃項目（No.2011FJ3051）；湖南省教育廳重點項目（No.10A015）。

孟穎（1984—），女，碩士，主要研究方向為數據挖掘、計算機網絡等；羅可（1961—），男，博士，教授，研究方向為數據挖掘、計算機應用等；劉建華（1985—），男，碩士，研究方向為電力系統運行與控制；姚麗娟（1985—），女，碩士，研究方向為數據挖掘。E-mail：kfmengying@126.com

2011-08-26

2011-10-14

1002-8331（2013）05-0103-05