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

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

長(zhǎng)沙理工大學(xué) 計(jì)算機(jī)與通信工程學(xué)院，長(zhǎng)沙 410114

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

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

長(zhǎng)沙理工大學(xué) 計(jì)算機(jī)與通信工程學(xué)院，長(zhǎng)沙 410114

1 引言

云計(jì)算[1]作為當(dāng)前的一個(gè)研究熱點(diǎn)，主流的信息技術(shù)公司，如Amazon，IBM，Google，都對(duì)此先后提出各自的云計(jì)算基礎(chǔ)架構(gòu)。云計(jì)算（cloud computing）是指通過(guò)互聯(lián)網(wǎng)連接的超級(jí)計(jì)算模式，包含分布式處理（distributed computing）、并行處理（parallel computing）和網(wǎng)格計(jì)算（grid computing）的相關(guān)技術(shù)。云計(jì)算是一種新興的計(jì)算模型，是集分布式操作系統(tǒng)、分布式數(shù)據(jù)庫(kù)、網(wǎng)格計(jì)算等技術(shù)于一體的計(jì)算機(jī)網(wǎng)絡(luò)模型，它可以充分地利用硬件資源和軟件資源。

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

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

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

2 預(yù)備知識(shí)

2.1 云計(jì)算簡(jiǎn)介

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

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

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

2.2 ACO算法簡(jiǎn)介

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

圖1 蟻群聚類(lèi)示意圖

螞蟻在覓食過(guò)程中能在所經(jīng)過(guò)的路徑上留下一種稱(chēng)為信息素的物質(zhì)，而螞蟻能夠感知這種物質(zhì)及其強(qiáng)度，并以此指導(dǎo)自己的運(yùn)動(dòng)方向，它們會(huì)朝著該物質(zhì)強(qiáng)度高的方向移動(dòng)[7]。因此，由大量螞蟻組成的集體覓食行為表現(xiàn)出：某一路徑越短，該路徑上走過(guò)的螞蟻就越多，則留下的信息素強(qiáng)度就越大，后來(lái)的螞蟻選擇該路徑的概率就越大。螞蟻個(gè)體之間就是通過(guò)這種信息交流來(lái)選擇最短路徑并達(dá)到搜索食物的目的。

2.3 K中心點(diǎn)算法簡(jiǎn)介

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

（1）p與Oc_new的距離仍然小于其他聚類(lèi)的中心點(diǎn)的距離，因此p仍屬于聚類(lèi)C如圖2（a），用Oc_new代替Oc_old，數(shù)據(jù)對(duì)象p的代價(jià)為：d(p，Oc_new)-d(p，Oc_old)，d表示兩點(diǎn)之間的距離。

（2）p與其他某一聚類(lèi)r的中心點(diǎn)的距離最短，則p將改屬于聚類(lèi)r如圖2（b），用Oc_new代替Oc_old，數(shù)據(jù)對(duì)象p的代價(jià)為：d(p，Or)-d(p，Oc_old)，其中Or為聚類(lèi)r的中心點(diǎn)，此時(shí)代價(jià)為正值。

類(lèi)似地，原先聚類(lèi)C外的任意數(shù)據(jù)對(duì)象 p也可能有兩種情況：

（1）p仍然與它原先所屬的聚類(lèi)的中心點(diǎn)距離最短，則p仍將屬于原先的聚類(lèi)如圖2（c），用Oc_new代替Oc_old，數(shù)據(jù)對(duì)象p的代價(jià)不變。

（2）在所有聚類(lèi)的中心點(diǎn)中，p與Oc_new的距離最短，則p將改屬于聚類(lèi)Oc_new如圖2（d），用Oc_new代替Oc_old，數(shù)據(jù)對(duì)象p的代價(jià)為：d(p，Oc_new)-d(p，Or)，其中Or為聚類(lèi)r的中心點(diǎn)，此時(shí)代價(jià)為負(fù)值。

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

2.4 ACO-K中心點(diǎn)算法簡(jiǎn)介

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

ACO-K中心點(diǎn)聚類(lèi)算法：

步驟1對(duì)蟻群進(jìn)行初始化操作，選擇螞蟻數(shù)目為m，NC-max為最大迭代次數(shù)，m個(gè)螞蟻?zhàn)鳛槌跏贾行狞c(diǎn)，設(shè)初始中心點(diǎn)為(M1，M2，…，Mm)。

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

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

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

步驟6如果達(dá)到結(jié)束條件（取得最終的最優(yōu)聚類(lèi)中心或者最優(yōu)路徑），則結(jié)束，否則轉(zhuǎn)向步驟3。

3 算法描述

3.1 資源分配策略

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

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

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

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

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

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

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

其中，A，B，C為三個(gè)約束條件的權(quán)重；TL，EL和DL為其邊界限制條件。

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

其中，RVakm(k)為第m號(hào)計(jì)算資源的第k次預(yù)測(cè)執(zhí)行速度，ak為第k次預(yù)測(cè)時(shí)的系統(tǒng)負(fù)載程度，RVakm(k)為第m號(hào)計(jì)算資源的第k次實(shí)際的執(zhí)行速度，θ為調(diào)節(jié)參數(shù)，用來(lái)調(diào)節(jié)在不同云環(huán)境中經(jīng)驗(yàn)值和預(yù)測(cè)值的比重，使預(yù)測(cè)達(dá)到最優(yōu)。

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

3.3.1 算法思想

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

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

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

3.3.2 信息素更新

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

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

其中，ρ為局部信息素?fù)]發(fā)系數(shù)，ε為全局信息素?fù)]發(fā)系數(shù)，α為信息素的相對(duì)權(quán)重。

3.4 算法步驟與流程圖

算法步驟：

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

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

步驟3該蟻群通過(guò)公式（3）、（4）、（5）來(lái)選擇下一跳的節(jié)點(diǎn)。

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

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

步驟6當(dāng)Ai全在回避列表或者Slave節(jié)點(diǎn)未與第二個(gè)節(jié)點(diǎn)相連，螞蟻Ai無(wú)法繼續(xù)前進(jìn)，該螞蟻?zhàn)詣?dòng)消亡。若Ai滿(mǎn)足終止條件，算法結(jié)束，否則轉(zhuǎn)向步驟2；若Ai不全在回避列表，則轉(zhuǎn)向步驟3。

步驟7如果達(dá)到終止條件（找到的計(jì)算資源不滿(mǎn)足用戶(hù)要求或者螞蟻全部消亡），則算法結(jié)束，否則轉(zhuǎn)向步驟2。

算法結(jié)束時(shí)，所有計(jì)算資源不足以滿(mǎn)足協(xié)議（SLA）中的用戶(hù)要求，則考慮轉(zhuǎn)移該存儲(chǔ)節(jié)點(diǎn)的用戶(hù)鏡像分片至其他存儲(chǔ)節(jié)點(diǎn)。按有效資源集將作業(yè)分配到相關(guān)計(jì)算資源節(jié)點(diǎn)，并盡量為高有效度的節(jié)點(diǎn)分配多的作業(yè)，以減低網(wǎng)絡(luò)的負(fù)載。算法流程圖如圖3。

圖3 算法流程圖

3.5 算法復(fù)雜度分析

3.5.1 算法的空間復(fù)雜度

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

3.5.2 算法的時(shí)間復(fù)雜度

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

4 仿真實(shí)驗(yàn)

4.1 實(shí)驗(yàn)環(huán)境

實(shí)驗(yàn)環(huán)境為Inter?CoreTM2 Duo 2.93 GHz，RAM3 GB，硬盤(pán)320 GB，100 MB網(wǎng)絡(luò)帶寬，操作系統(tǒng)Windows XP。用Gridsim來(lái)模擬一個(gè)云計(jì)算的局部域，以檢查ACO-K中心點(diǎn)算法在這種特殊的網(wǎng)格環(huán)境中的運(yùn)行情況。

通過(guò)Gridsim中的GridResource類(lèi)和一系列的輔助類(lèi)，模擬云計(jì)算的網(wǎng)絡(luò)資源，構(gòu)建較擬真的云環(huán)境。通過(guò)設(shè)定Grid Information Services類(lèi)來(lái)管理資源。

4.2 實(shí)驗(yàn)結(jié)果

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

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

表1 螞蟻數(shù)據(jù)結(jié)構(gòu)表

表2 算法主要參數(shù)取值表

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

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

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

圖6 仿真結(jié)果曲線圖

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

5 結(jié)束語(yǔ)

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

參考文獻(xiàn)：

[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]徐曉華，陳凌.一種自適應(yīng)的螞蟻聚類(lèi)算法[J].軟件學(xué)報(bào)，2006，17（9）：1884-1889.

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

[8]孫勝，王元珍.基于核的自適應(yīng)K-Medoids聚類(lèi)[J].計(jì)算機(jī)工程與設(shè)計(jì)，2009，30（3）：674-688.

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

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

[11]華夏渝，鄭駿，胡文心.基于云計(jì)算環(huán)境的蟻群優(yōu)化計(jì)算資源分配算法[J].華東師范大學(xué)學(xué)報(bào)，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

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

云計(jì)算；資源分配；K中心點(diǎn)算法；蟻群算法（ACO）；動(dòng)態(tài)負(fù)荷

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.

國(guó)家自然科學(xué)基金（No.11171095，No.10871031）；湖南省自然科學(xué)衡陽(yáng)聯(lián)合基金（No.10JJ8008）；湖南省科技計(jì)劃項(xiàng)目（No.2011FJ3051）；湖南省教育廳重點(diǎn)項(xiàng)目（No.10A015）。

孟穎（1984—），女，碩士，主要研究方向?yàn)閿?shù)據(jù)挖掘、計(jì)算機(jī)網(wǎng)絡(luò)等；羅可（1961—），男，博士，教授，研究方向?yàn)閿?shù)據(jù)挖掘、計(jì)算機(jī)應(yīng)用等；劉建華（1985—），男，碩士，研究方向?yàn)殡娏ο到y(tǒng)運(yùn)行與控制；姚麗娟（1985—），女，碩士，研究方向?yàn)閿?shù)據(jù)挖掘。E-mail：kfmengying@126.com

2011-08-26

2011-10-14

1002-8331（2013）05-0103-05