基于改進(jìn)蟻群算法的云計(jì)算資源分配方法

胡睿+劉鋼

摘要：針對(duì)云計(jì)算中的資源分配問題，提出了一種改進(jìn)的蟻群算法。由于傳統(tǒng)的蟻群算法在解決負(fù)載均衡問題上存在不足，改進(jìn)的蟻群算法加入了信息素調(diào)節(jié)因子，來防止數(shù)據(jù)中心的計(jì)算資源過載。在CloudSim仿真平臺(tái)上進(jìn)行實(shí)驗(yàn)，結(jié)果表明改進(jìn)蟻群算法的任務(wù)時(shí)間跨度和負(fù)載均衡度都要優(yōu)于傳統(tǒng)的蟻群算法。

關(guān)鍵詞：云計(jì)算；資源分配；蟻群優(yōu)化；負(fù)載均衡

中圖分類號(hào)：TP18 文獻(xiàn)標(biāo)識(shí)碼：A 文章編號(hào)：1009-3044（2017）29-0179-02

1 概述

隨著互聯(lián)網(wǎng)越來越普及，人們?nèi)粘９ぷ麟x不開對(duì)互聯(lián)網(wǎng)中海量數(shù)據(jù)的接收和處理，可是單個(gè)計(jì)算機(jī)的數(shù)據(jù)處理能力已經(jīng)無法滿足人們工作需求。云計(jì)算技術(shù)的出現(xiàn)，可以有效地解決這類問題。云計(jì)算作為一種創(chuàng)新型的計(jì)算方式，通過互聯(lián)網(wǎng)的高速傳送能力，把對(duì)數(shù)據(jù)的處理操作從單個(gè)計(jì)算機(jī)轉(zhuǎn)移到互聯(lián)網(wǎng)的計(jì)算機(jī)集群中，這樣可以大大縮短數(shù)據(jù)處理的時(shí)間。云計(jì)算采用的是按需付費(fèi)的模式，客戶無需自己動(dòng)手搭建云平臺(tái)，可以直接在云服務(wù)運(yùn)營(yíng)商所提供的云平臺(tái)上部署自己的應(yīng)用程序。這樣減少了很多前期準(zhǔn)備工作，節(jié)省了時(shí)間。同時(shí)打破時(shí)間和地點(diǎn)的限制，客戶可以隨時(shí)隨地在云平臺(tái)上調(diào)試自己的應(yīng)用程序。云計(jì)算作為分布式計(jì)算的一種特殊形式，可以使計(jì)算能力大幅提升。

算法是解決云計(jì)算資源分配問題的一個(gè)重要手段，目前一些學(xué)者已經(jīng)對(duì)云計(jì)算資源分配算法進(jìn)行了研究，并取得了一定的成果。文獻(xiàn)[1]提出了一種基于蟻群優(yōu)化的資源分配方法，考慮云計(jì)算的特點(diǎn)，對(duì)任務(wù)量進(jìn)行預(yù)測(cè)，從而得到最優(yōu)分配方案。文獻(xiàn)[2]針對(duì)傳統(tǒng)遺傳算法收斂慢和早熟的缺點(diǎn)，對(duì)遺傳算法的染色體編碼和適應(yīng)度函數(shù)進(jìn)行了修改，使得改進(jìn)后的遺傳算法能夠更好的解決資源分配問題。文獻(xiàn)[3]為了對(duì)服務(wù)集群的負(fù)載均衡進(jìn)行優(yōu)化，提出了一種改進(jìn)粒子群算法的優(yōu)化策略，將多群體協(xié)作和變異粒子逆向運(yùn)行的思想引入到粒子群算法中，提高了算法的執(zhí)行效率。文獻(xiàn)[4]提出了引入模擬退火算法中的Metropolis接受準(zhǔn)則的蟻群算法，根據(jù)Metropolis接受準(zhǔn)則來接受一部分“劣質(zhì)”新解，來避免算法陷入局部最優(yōu)和資源分配更均衡。本文在傳統(tǒng)蟻群算法的基礎(chǔ)上，對(duì)轉(zhuǎn)移概率公式進(jìn)行了修改，同時(shí)加入了信息素調(diào)節(jié)因子。力求使改進(jìn)后的蟻群算法執(zhí)行效率更好，同時(shí)負(fù)載均衡度更優(yōu)。

2 改進(jìn)蟻群算法的資源分配

2.1 問題描述

資源分配可以具體化為將n個(gè)云任務(wù)有序分配給m個(gè)計(jì)算資源的過程。

（1） 云任務(wù)集合表示為：，表示第i個(gè)云任務(wù)。

（2） 計(jì)算資源的集合為：，表示第j個(gè)計(jì)算資源。

一個(gè)云任務(wù)只能在一個(gè)計(jì)算資源上執(zhí)行，我們用一個(gè)矩陣來表示每個(gè)云任務(wù)與每個(gè)計(jì)算資源之間的映射關(guān)系：

其中，表示將云任務(wù)分配給計(jì)算資源執(zhí)行。

資源分配的宗旨就是確定云任務(wù)與計(jì)算資源之間合理的分配關(guān)系，云任務(wù)完成時(shí)間和計(jì)算資源的負(fù)載均衡度是衡量資源分配是否合理的重要指標(biāo)。

是任務(wù)在計(jì)算資源上的執(zhí)行時(shí)間。

是計(jì)算資源執(zhí)行任務(wù)的時(shí)間跨度。

2.2 改進(jìn)算法描述

（1） 初始化信息素強(qiáng)度和能見度

公式（3）中信息素強(qiáng)度和能見度與節(jié)點(diǎn)的計(jì)算能力成正比，N是常量。

（2） 螞蟻下一跳選擇城市的概率

公式（4）定義了螞蟻k從任務(wù)i出發(fā)，選擇資源節(jié)點(diǎn)j的概率。

這里我們定義一個(gè)，值由公式（4）決定，對(duì)路徑上殘留信息素有重大的影響。根據(jù)我們新定義的，轉(zhuǎn)移概率能夠通過和自適應(yīng)地調(diào)整。是所有邊信息素的平均值，因此可以作為一個(gè)調(diào)節(jié)因子。如果值越小，螞蟻選擇信息素較小路徑通過的可能性越大。的設(shè)定可以使算法隨機(jī)搜索，有效避免算法陷入局部最優(yōu)。

（3） 信息素更新規(guī)則

為了滿足云計(jì)算資源分配的實(shí)際需求，我們對(duì)信息素更新公式進(jìn)行了修改。公式（6）和公式（7）分別是修改以后的局部信息素更新公式和全局信息素更新公式。這里，D是常量，表示計(jì)算資源執(zhí)行任務(wù)的完成時(shí)間，表示計(jì)算資源執(zhí)行任務(wù)的最短完成時(shí)間。

（4） 負(fù)載均衡調(diào)節(jié)機(jī)制

為了避免過多的任務(wù)都分配到一個(gè)計(jì)算資源上，從而造成該計(jì)算資源過載。我們?cè)谶@里定義了一個(gè)信息素調(diào)節(jié)因子FA。假如將任務(wù)i分配給計(jì)算資源j執(zhí)行，計(jì)算資源j的信息素我們通過公式（9）去更新，而未被分配任務(wù)i計(jì)算資源的信息素我們通過公式（10）去更新。如果計(jì)算資源在之前的迭代中超載，計(jì)算資源的將比其他計(jì)算資源的大，這樣一來計(jì)算資源的信息素調(diào)節(jié)因子FA將比其他計(jì)算資源的小。那么，在下次迭代中再把任務(wù)分配給計(jì)算資源可能性就會(huì)降低。這種負(fù)載均衡調(diào)節(jié)機(jī)制保證了在多次迭代中，為計(jì)算資源均勻分配任務(wù)。我們通過公式（11）來評(píng)價(jià)負(fù)載均衡度，表示計(jì)算資源分配到云任務(wù)的數(shù)量，表示計(jì)算資源處理云任務(wù)的能力。

3 仿真實(shí)驗(yàn)及結(jié)果分析

為了證明改進(jìn)后的蟻群算法的有效性，我們對(duì)云仿真軟件CloudSim 3.1進(jìn)行了功能擴(kuò)展，并重寫了Cloudlet等類方法，同時(shí)對(duì)實(shí)驗(yàn)參數(shù)進(jìn)行了設(shè)置。計(jì)算節(jié)點(diǎn)處理能力的取值范圍是300MIPS～600MIPS，云任務(wù)的大小30000MB～80000MB，輸出數(shù)據(jù)量300MB/S。啟發(fā)因子是0.7，期望啟發(fā)因子是0.7，信息素濃度揮發(fā)系數(shù)是0.3，螞蟻的個(gè)數(shù)是60，最大迭代次數(shù)是60。

任務(wù)數(shù)從20增加到100，傳統(tǒng)蟻群算法（ACO）、文獻(xiàn)[7]提出的引入Metropolis接受準(zhǔn)則的蟻群算法（MACO）和本文提出的改進(jìn)后的蟻群算法（LBACO）的任務(wù)時(shí)間跨度如圖1所示。從圖1可以看出，在任務(wù)數(shù)量規(guī)模較小的時(shí)候，三種算法的任務(wù)時(shí)間跨度相差不大。在任務(wù)數(shù)量為30的時(shí)候，三種算法的任務(wù)時(shí)間跨度基本相同。而當(dāng)任務(wù)數(shù)量逐漸增加到80以上的時(shí)候，LBACO算法的任務(wù)時(shí)間跨度明顯要小于ACO算法和MACO算法。

接下來我們看任務(wù)規(guī)模較大的情況，我們將任務(wù)數(shù)從50逐漸增加至350，ACO算法、MACO算法和LBACO算法的負(fù)載均衡度如圖2所示。從圖2可以看出，在任務(wù)數(shù)量較小的時(shí)候，三種算法的負(fù)載均衡度之間相差不多。但在任務(wù)規(guī)模較大的時(shí)候，LBACO算法的負(fù)載均衡度要比ACO算法和MACO算法更好。

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

本文對(duì)傳統(tǒng)蟻群算法進(jìn)行改進(jìn)，來解決云計(jì)算資源分配問題。改進(jìn)后的算法在任務(wù)時(shí)間跨度和負(fù)載均衡度這兩方面，都有較大改善?？墒歉倪M(jìn)后的算法還存在兩點(diǎn)不足：第一，改進(jìn)后的算法仍然存在迭代初期盲目性的問題，這個(gè)需要使用其他算法與蟻群算法融合。第二，改進(jìn)后的算法只是以任務(wù)完成時(shí)間最小為原則，而沒有考慮執(zhí)行開銷等其他因素。

參考文獻(xiàn)：

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

[2] 劉愉，趙志文，李小蘭，等. 云計(jì)算環(huán)境中優(yōu)化遺傳算法的資源調(diào)度策略[J].北京師范大學(xué)學(xué)報(bào)：自然科學(xué)版，2012，48（4）：378-383.

[3] 劉萬(wàn)軍，張孟華. 云中基于MPSO算法的云計(jì)算資源調(diào)度策略[J].計(jì)算機(jī)工程，2011，37（11）：43-45.

[4] 苗培. 蟻群優(yōu)化算法在云計(jì)算資源分配上的應(yīng)用[J].山東師范大學(xué)，2015.endprint