陳真

（韓山師范學(xué)院潮州師范分院，廣東潮州521021）

改進蟻群算法在云環(huán)境下路徑優(yōu)化設(shè)計

陳真

（韓山師范學(xué)院潮州師范分院，廣東潮州521021）

文中針對云計算環(huán)境中的資源分配問題，提出一種改進蟻群優(yōu)化的云計算資源分配算法，通過分析諸如帶寬占用、網(wǎng)絡(luò)負載和響應(yīng)時間等因素對云端資源分配的影響，并結(jié)合云計算平臺的特點，優(yōu)化云環(huán)境下路徑的選擇.仿真實驗結(jié)果表明，改進后的蟻群算法能夠在云中快速、合理地找到云端所需訪問的數(shù)據(jù)庫，并能夠優(yōu)化相應(yīng)的搜索性能，減少搜索時間，降低云數(shù)據(jù)庫整體網(wǎng)絡(luò)負載，獲得比其他一些針對云計算的分配算法具有更優(yōu)的效率.

云計算；網(wǎng)絡(luò)負載；蟻群算法

0 引言

隨著云計算的應(yīng)用及推廣，云計算的規(guī)模將呈現(xiàn)爆發(fā)式增長，如何提高用戶對云資源的訪問，確保對云上的延遲敏感的作業(yè)在也能夠得以很好地運行是個關(guān)鍵問題.

蟻群算法是一種模擬螞蟻行為特征的仿生優(yōu)化算法[1-2].它通過螞蟻在覓食路徑上留下的信息素的積累來尋找復(fù)雜的最優(yōu)途徑問題，目前已被廣泛應(yīng)用于旅行商問題(TSP)、網(wǎng)絡(luò)路由、二次分配、屬性約簡[3]等問題的求解，具有正反饋、魯棒性、并行計算及易移植等優(yōu)點.然而，該算法也存在一些不足，如在處理規(guī)模較大的系統(tǒng)時，往往無法實現(xiàn)對全局空間的充分搜索，容易陷入局部最優(yōu)解，且初期搜索時間偏長等.同樣，對于云計算網(wǎng)絡(luò)服務(wù)中，通過某一條服務(wù)器路徑購買計算資源的人越多，將造成局部網(wǎng)絡(luò)負載越重，網(wǎng)絡(luò)中路徑搜索陷入局部最優(yōu)解，無法找到全局最優(yōu)解，最優(yōu)路徑上用戶數(shù)量巨大，負載過重，可能導(dǎo)致局部網(wǎng)絡(luò)擁塞，甚至整個網(wǎng)絡(luò)癱瘓，使廠商損失慘重，獲得的利潤劇減甚至出現(xiàn)虧損情況等.

因此，若能根據(jù)用戶作業(yè)需求，將任務(wù)資源實時動態(tài)的分配到相關(guān)計算資源節(jié)點將會大大地提高云計算環(huán)境中的網(wǎng)絡(luò)整體性能.文中提出改進蟻群算法在云環(huán)境下路徑優(yōu)化設(shè)計，該算法利用螞蟻覓食時具有找到最短路徑的特性，將它應(yīng)用于網(wǎng)絡(luò)負載平衡數(shù)學(xué)模型加以模擬，能夠在云中快速、合理地找到所需訪問的數(shù)據(jù)庫，避免網(wǎng)絡(luò)路徑搜索陷入局部最優(yōu)解，無法找到全局最優(yōu)解，導(dǎo)致?lián)砣?，甚至整個網(wǎng)絡(luò)癱瘓等負面影響，該方法減少云數(shù)據(jù)庫數(shù)路由的動態(tài)負荷，在一定程度上提高云計算的效率.

1 基本蟻群算法及定義

定義1anti={1，2，…，k,…,m}表示一個蟻群的集合，其中k表示第k只螞蟻，Pk表示第k只螞蟻路徑，當(dāng)m只螞蟻遍歷完所有路徑，求出解集中最示第k只螞蟻路徑距離，記min(k，Pk，Lk)為此解集中的最優(yōu)解，則Lk-min為螞蟻k已走過的最短路徑.

推論1螞蟻家族中m只螞蟻從起點出發(fā)，遍歷完所有節(jié)點回到原點，將其中遍歷最短路徑的那只螞蟻作為繁殖螞蟻；根據(jù)定義1，當(dāng)繁殖螞蟻完成一輪迭代更新后，所有弧上的信息素都要揮發(fā)，但有下限值，記為τmin（k，Pk，Lk）.

2 云計算基礎(chǔ)設(shè)施服務(wù)的資源分配

由于在整個云環(huán)境資源和結(jié)構(gòu)分布及其實際情況比較復(fù)雜，任意線路在任意時刻的網(wǎng)絡(luò)負載存在眾多不可預(yù)期的大幅度變化，也可能資源需求估計過低，使當(dāng)前資源的規(guī)模無法滿足其用戶作業(yè)需求；也可能對資源需求估計過高，使所租用的資源處于閑置狀態(tài)，使得資源利用率大大降低.這種物理節(jié)點和物理鏈路的負載極度不平衡，不但造成資源浪費，而且增加了許多成本，同時降低了服務(wù)的滿意度.因此，要使云計算環(huán)境中的資源的利用率提高，需要對可行路徑上的節(jié)點進行資源分配預(yù)估.

在云平臺中的每個單元分別由一個主作業(yè)調(diào)度節(jié)點及該單元所轄范圍內(nèi)節(jié)點集群中的一個從任務(wù)分配節(jié)點（slave）共同組成[4].將云計算環(huán)境下slave節(jié)點域表示為一個完全圖G=(V，E)，其中V、E分別表示所有網(wǎng)絡(luò)節(jié)點和所有鏈路的集合，鏈路E={(s，m，Qsm)s，m∈N}表示相鄰節(jié)點s，m間的最優(yōu)路徑.Qsm而為s，m間線路屬性集，如：平均帶寬、節(jié)點費用等.

假設(shè)s∈V為源點，M∈｛V-(s)｝終點.對于任一鏈路e∈E，定義3種屬性：時延函數(shù)net_delay（e），費用函數(shù)net_cost（e），帶寬函數(shù)net_bandwidth（e）和能量消耗函數(shù)E（e）.對于相應(yīng)的任一網(wǎng)絡(luò)節(jié)點k∈V，也分別為net_delay（k），net_cost（k）及net_E（k）定義3種屬性.同時假設(shè)esm為網(wǎng)絡(luò)節(jié)點s，m之間的距離，則存在下列關(guān)系：

即：Net_bandwidth（Tsm）=net_bandwidthmax-net_bandwidth0

其中，net_bandwidthmax表示全部可用帶寬；net_bandwidth0表示服務(wù)優(yōu)先級更高的服務(wù)所占用或同時請求的帶寬.

根據(jù)以上定義：網(wǎng)絡(luò)問題就是在網(wǎng)絡(luò)N（V，E）定源點S，終點M，尋找一條路由esm滿足：

（1）時延約束：net_delay（Tsm）≤D；

（2）帶寬約束：net_bandwidth（Tsm）≥Bmin；

（3）費用約束：net_cost（Tsm）≤Cmin；

其中，Bmin、D、Cmin分別代表業(yè)務(wù)對網(wǎng)絡(luò)帶寬、時延、費用的約束限制；

在滿足前面3個約束的條件下，τ（Tsm）值越小，資源的利用率越高，設(shè)資源選擇的約束函數(shù)為：

3 基于云計算環(huán)境下的蟻群優(yōu)化算法

文中提出在云計算環(huán)境的基礎(chǔ)上對蟻群算法進行改進，使其能夠快速、合理地適應(yīng)云端最優(yōu)路徑問題的求解.

3.1 算法的改進策略

由于外激素的揮發(fā)和聚集是時間的函數(shù)，就這就意味著螞蟻在覓食時所經(jīng)過的路徑隨著食物位置的變化過程等效于網(wǎng)絡(luò)的邏輯拓撲的一個漸變過程，它并不會隨著業(yè)務(wù)的變化而在很短時間內(nèi)產(chǎn)生大的變化，即保證了拓撲結(jié)構(gòu)在短時間的相似性，從而使網(wǎng)絡(luò)的邏輯拓撲重配置對網(wǎng)內(nèi)即將接受或正在進行的服務(wù)受損程度得到有效降低.針對上述特征分析，改進后的算法能夠解決動態(tài)選路和全局性導(dǎo)向問題.

在t時刻探測螞蟻k從節(jié)點s轉(zhuǎn)移到節(jié)點m的轉(zhuǎn)移概率函數(shù)如下：

其中，Po是ANT轉(zhuǎn)移概率門檻值；tabuk（k=1，2，…，m)用于記錄螞蟻k所經(jīng)過的節(jié)點集合，將獲取的節(jié)點m加入tabuk中，將m點作為下一個要訪問的起點直至構(gòu)建成一條Hamilton完整的回路；ταsm（t）表示在t時刻螞蟻在s節(jié)點上觀察到m節(jié)點的信息素濃度；參數(shù)μsm用于反映ANT在選擇路徑上殘留信息素濃度的重要程度；α為控制信息素的濃度程度，β是路徑長度的重要程度；

ηsm（t）因子的計算公式如下：

當(dāng)螞蟻構(gòu)建完成一條Hamilton完整的回路之后，必須對途徑線路上累計的信息素濃度進行更新，同時削弱舊的信息素，即將釋放相應(yīng)訪問路徑上舊的信息素.

3.2 信息素更新規(guī)則

為了誘導(dǎo)所有螞蟻向滿足質(zhì)量較優(yōu)的路徑靠攏，當(dāng)螞蟻完成任意一條路徑的(即一個循環(huán)結(jié)束)搜尋后，要對該路徑上的局部信息素和全局信息素進行更新.

3.2.1 節(jié)點信息素的定義與更新

在云平臺上不同的用戶對資源的獲取各不相同，而如何高效地獲取自身所需類別的資源，將是搜索算法高效與否的關(guān)鍵.以節(jié)點作為資源的載體，如果螞蟻在搜索過程中能夠有效地反映其存儲的某類資源的信息，無疑會有效提高搜索的效率.因此，利用節(jié)點的某類資源的訪問成功率作為衡量螞蟻在該節(jié)點的信息素濃度值，能夠更精確的反映節(jié)點包含某種資源的情況，從而為搜索提供依據(jù).

其中：ζ為信息素的調(diào)節(jié)因子[8]；n0（key）、Ntotal分別為螞蟻搜索關(guān)鍵字key成功的次數(shù)和同類資源的總檢索次數(shù).

3.2.2 路徑上信息素的定義與更新

根據(jù)文獻[9-10]，節(jié)點間擁有的資源越多，則相應(yīng)的通信次數(shù)越高，也越利于資源的搜索.文中根據(jù)節(jié)點間路徑上的信息素濃度及相應(yīng)的節(jié)點間通信次數(shù)，為螞蟻搜索提供依據(jù).螞蟻通過節(jié)點路徑上的信息素第（t+1）次時計算公式：

式中，Q2為常數(shù)[11]；表α示瓶頸帶寬對全局信息素的影響強度；Lk-min（s，m）為本次ANT搜索的最佳路徑；Φ表示螞蟻k所走的邊s，m屬于最佳；

若沒有被后續(xù)螞蟻選擇的鏈路上的信息素則更新為：

表示經(jīng)過一輪迭代更新后，所有弧上的信息素都要揮發(fā)，但有下限值τmin.式中，Q1為常數(shù)；Lk是螞蟻k已遍歷過的路徑的長度.

由式（3）可知，鏈路上的信息素會隨著時間的消逝而減少，為了避免螞蟻在路徑選擇時陷入局部最優(yōu)解，通過采用式（4）和式（6）來更新鏈路上的信息素強度，從式（4）可看出，當(dāng)鏈路剩余帶寬越大，信息素濃度就越強.

3.2.3 最優(yōu)路徑選取

在保證用戶請求所選路徑穩(wěn)定的前提下，利用螞蟻在該路徑上的信息素濃度值、所選路徑距離以及該路徑被選取的比重與備選路徑進一步優(yōu)化判斷選擇.計算公式為：

式中：%Ak為螞蟻k與其他螞蟻所選路徑為同一路徑在全部螞蟻中占的比例，τk為選擇路徑Sk的螞蟻在該路徑上留下的信息素濃度均值，L（Sk）為路徑Sk的長度.

3.3 算法實現(xiàn)過程

基于改進蟻群算法的云環(huán)境下路徑搜索步驟如下：

步驟1當(dāng)用戶通過關(guān)鍵字key請求節(jié)點point進行資源搜索時，首先檢測該節(jié)點所包含的資源列表，若存在所需資源，則直接獲取資源，搜索結(jié)束.否則，進入下一步.

步驟2節(jié)點P通過釋放搜索螞蟻擇優(yōu)選取下一節(jié)點發(fā)出資源請求，并將該節(jié)點添加到相應(yīng)的禁忌表tabuk中.避免重復(fù)訪問，并根據(jù)實際情況做出相應(yīng)判斷，其過程為：

（1）當(dāng)ANT進入路徑搜索，每到達一個節(jié)點并收集節(jié)點沿途中信息，即終止搜索，并按照式（2）進行一次局部信息素更新.根據(jù)定義1，當(dāng)螞蟻到達目的后沿原路返回，同時利用式（6）和（7）刷新路徑上的信息素濃度.反之，ANT返回上一節(jié)點繼續(xù)搜索，直到直到所有節(jié)點訪問結(jié)束為止.

（2）若下一節(jié)點亦不能滿足所需資源，則搜索螞蟻K將從節(jié)點信息素表中選取數(shù)值最大的節(jié)點作為下一節(jié)點進行訪問，直到找到所需資源或直到本次搜索周期T結(jié)束，搜索自動結(jié)束.

步驟3當(dāng)所有螞蟻搜索請求完畢返回節(jié)點后，請求節(jié)點利用式（8）對獲取的路徑方案進行優(yōu)化篩選，以獲取最優(yōu)滿足相關(guān)資源的路徑.

為了避免螞蟻在云數(shù)據(jù)庫中無限制的搜尋，造成不必要的網(wǎng)絡(luò)資源浪費，這里我們對螞蟻在搜尋過程中設(shè)定一個生存值Nodes，當(dāng)螞蟻在搜尋過程超出生存值，則螞蟻不能繼續(xù)前行，即算法停止，螞蟻自動消亡，從而實現(xiàn)對資源的有效利用.

螞蟻在云數(shù)據(jù)庫中生存的Nodes值設(shè)定算法：

初始化i=1，Int_Nodes=k；

If(Nodes＜=Int_Nodes)do{

螞蟻繼續(xù)向前搜尋；

Nodes++

}while(anti==ture)；

Else if{

算法停止，螞蟻自動消亡；

}

End

4 仿真實驗分析

由于在云計算環(huán)境中，網(wǎng)絡(luò)資源是個沒有任何固定的拓撲結(jié)構(gòu)，且網(wǎng)絡(luò)存在眾多具體情況是不可預(yù)測的，所以選擇一個真實反映云環(huán)境的結(jié)構(gòu)、資源的分配情況及其實現(xiàn)的測試環(huán)境是相當(dāng)困難的，這里主要驗證該算法能否高效地在云平臺下實現(xiàn)的計算資源的搜索及分配工作，并能夠優(yōu)化搜索性能，減少搜索時間，降低網(wǎng)絡(luò)負載；因此實驗是一個模擬云計算的局部域：

配置環(huán)境：六臺2G以上臺式機組成，其中一臺設(shè)定為服務(wù)器;

其他配置：64位Ubuntu操作系統(tǒng)[12]；Hadoop版本為0.20.2[13]；虛擬化平臺為Xen，虛擬機管理器為OpenNeBula2.3.0版本.

對比算法：路由算法OSPF、SPF(Shortest Path First)、原ACO以及該蟻群優(yōu)化算法RACO

使用其中一臺PC作為主服務(wù)器，用于控制數(shù)據(jù)庫系統(tǒng)數(shù)據(jù)分布情況.另外使用5臺PC作為數(shù)據(jù)存儲節(jié)點，安裝PostGre_SQL.實驗數(shù)據(jù)為實驗室的模擬數(shù)據(jù)，開始時集中存儲在主服務(wù)器上，統(tǒng)計將從學(xué)院的實驗室數(shù)據(jù)作為測試數(shù)據(jù).為了更好證明RACO具有更好的效果，這里同時引入原ACO算法做比較，隨著不同數(shù)據(jù)量的逐漸遞增，各算法的延遲性及查詢響應(yīng)時間，如圖4，圖5.

從圖4中可以看到，該算法（RACO）在平均吞吐量明顯優(yōu)于其它3個算法，在參數(shù)從0到2逐漸遞增的情況下，效果更為明顯，經(jīng)過改進的蟻群算法充分考慮了帶寬、傳輸能量消耗及傳輸時延等因素，有效的動態(tài)調(diào)整路徑選擇，從而保證算法在云環(huán)境下的效率.

從圖5中可以看出，改進后的RACO算法最優(yōu)路徑的搜尋效率是最高的，且所花費的時間是最短的，相比于其他3個算法，該算法（RACO）在時間延遲性能在具有明顯的優(yōu)勢，能夠迅速、準(zhǔn)確地從云端找到所需訪問的數(shù)據(jù)庫，有效的避免陷入局部最優(yōu)解及收斂速度不穩(wěn)定等問題.

5 結(jié)束語

云計算由大量計算資源組成的IT資源池動態(tài)地通過網(wǎng)絡(luò)以按需、租用的形式提供給各用戶，相對網(wǎng)格計算、并行計算等將提出更高基礎(chǔ)設(shè)施的要求，因此一個好的資源調(diào)度算法至關(guān)重要.文中將改進蟻群算法（RACO）和云計算技術(shù)結(jié)合起來，針對云環(huán)境的集群性、共享性、動態(tài)性及高可用性等特點，將費用、帶寬、傳輸能量消耗及傳輸時延等作為衡量蟻群資源分配算法性能指標(biāo)參數(shù)，實時根據(jù)用戶作業(yè)的需求搜尋最佳路徑.通過仿真模擬實驗結(jié)果可以得出，該算法相比其他算法能夠更好的在云平臺中完成對計算資源搜索及分配工作，并能夠優(yōu)化搜索性能，減少搜索時間，降低網(wǎng)絡(luò)負載，具有很好的全局收斂能力.

[1]Dorigo M，Stutzle T.Ant Colony Optimization[M].UK：The MIT Press，2009．

[2]史恒亮，唐振民，劉傳領(lǐng)，等.基于蟻群優(yōu)化算法的云數(shù)據(jù)庫動態(tài)路徑規(guī)劃[J].計算機科學(xué)，2010，37(5)：143-147.

[3]XiongPC，F(xiàn)an Y S，Zhou M C.QoS-aware web service configuration[J].IEEE Transactions on Systems，Man and Cybernetics，2008，38(4)：888-895．

[4]趙肄江，胡蓉.基于虛擬化的綠色云計算[J].湖南科技大學(xué)學(xué)報：自然科學(xué)版，2010，24(3)：41-46.

[5]史恒亮，任崇廣，白光一，等.普杰信自適應(yīng)蟻群優(yōu)化的云數(shù)據(jù)庫動態(tài)路徑查詢[J].計算機工程與應(yīng)用，2010，46(9)：10-13.

[6]何雪海，胡小兵，趙吉東，等.基于自適應(yīng)轉(zhuǎn)移概率的蟻群優(yōu)化算法[J].計算機工程，2010，36(23)：165-168.

[7]文明波，丁治明.適用于云計算的面向查詢數(shù)據(jù)庫數(shù)據(jù)分布策略[J].計算機科學(xué)，2010，37(9)：168-172.

[8]溫如春，許櫻，王祖麟.改進蟻群算法在迷宮路徑規(guī)劃問題中的研究和應(yīng)用[J].江西理工大學(xué)學(xué)報，2010，31(2)：26-28.

[9]王愛靜，郝志峰，黃翰，等.雙向反饋蟻群算法在網(wǎng)絡(luò)負載均衡問題的研究[J].計算機工程與應(yīng)用，2011，47(36)：112-116.

[10]梁爽.基于SOA的云計算框架模型的研究與實現(xiàn)[J].計算機工程與應(yīng)用，2011，47(35)：92-94.

[11]劉萬軍，張孟華，郭文越.基于MPSO算法的云計算資源調(diào)度策略[J].計算機工程，2011，37(11)：43-46.

[12]Assuncao M，Costanzo A，Buyya R.Evaluating the cost benefit of using cloud computing to extend the capacity of clusters［C］//Proc of the 18th ACM international symposium on High performance distributed computing．New York：ACM，2009：141-150．

[13]郭濤，溫少君，陳俊杰.基于個性化的云平臺虛擬機部署機制的研究[J].太原理工大學(xué)學(xué)報，2012(2)：125-129.

The path optimization design of improved ant colony algorithm in cloud environment

CHEN Zhen

(Chaozhou Teachers'College,Hanshan Normal University,Chaozhou 521012,China)

Aiming at the resource allocation problems in cloud computing environmen,the article puts forward an improved ant colony optimization cloud computing resources allocation algorithm through the analyses on bandwidth,the network load and response time factors on the influence of the distribution clouds resources，and combining with the characteristics of cloud computing platform,the choice of the path under the optimization of the cloud environment.Simulation research results show that the improved algorithm can find the required access database in the cloud quickly,optimize search performance,reduce search time and drop the whole network load of cloud database,get better efficiency than some other distribution algorithms of cloud computing.

cloud computing;the network load;ant colony algorithm

TP301.6

A

2012-05-14

陳真（1985-），男，碩士，助教，主要從事云計算機技術(shù)、智能網(wǎng)絡(luò)技術(shù)等方面的研究，E-mail：baile035@126.com.

2095-3046（2012）03-0066-05