基于改進(jìn)蟻群優(yōu)化算法的云計(jì)算調(diào)度方法?

王恩重 陶傳奇

（1.南京理工大學(xué)計(jì)算機(jī)科學(xué)與工程學(xué)院 南京 210094）（2.南京航空航天大學(xué)計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院 南京 210016）（3.計(jì)算機(jī)軟件新技術(shù)國(guó)家重點(diǎn)實(shí)驗(yàn)室（南京大學(xué)） 南京 210023）

1 引言

隨著IT和互聯(lián)網(wǎng)技術(shù)的飛速發(fā)展，傳統(tǒng)的應(yīng)用也變得越來越復(fù)雜，需要支持更多的用戶、更強(qiáng)的計(jì)算能力，同時(shí)也需要更加的穩(wěn)定安全，而為了支撐這些不斷增長(zhǎng)的需求，企業(yè)不得不去購買和升級(jí)各類硬件設(shè)備和軟件資源，另外還需要一個(gè)完整的運(yùn)維團(tuán)隊(duì)來支持這些設(shè)備或軟件的正常運(yùn)作，包括安裝、配置、測(cè)試、運(yùn)行、升級(jí)以及保證系統(tǒng)的安全等。這會(huì)使得企業(yè)開銷變得非常巨大，并且隨著數(shù)量或規(guī)模的增加費(fèi)用也會(huì)不斷提高。這對(duì)于大型互聯(lián)網(wǎng)企業(yè)會(huì)造成一定壓力，而對(duì)于中小型企業(yè)更是有致命性威脅。大數(shù)據(jù)時(shí)代，數(shù)據(jù)量呈現(xiàn)爆炸式的增長(zhǎng)速度，現(xiàn)有的計(jì)算機(jī)硬件水平和信息處理能力已經(jīng)出現(xiàn)瓶頸，云計(jì)算的誕生是解決這種難題的“良藥”。

自云計(jì)算概念被提出到現(xiàn)在，已有10年時(shí)間，如今云計(jì)算以其可伸縮性、高可靠性、低成本以及按需服務(wù)等諸多特點(diǎn)吸引了無數(shù)研究人員和企業(yè)的關(guān)注，成為了當(dāng)今時(shí)代的熱門話題。云計(jì)算是分布式存儲(chǔ)、虛擬化、并行計(jì)算等技術(shù)的集合體，如同數(shù)據(jù)庫連接池一樣，它將云中所有的可用資源整合成為一個(gè)龐大的資源庫，達(dá)到資源隨用隨取的目的，很好地解決了大數(shù)據(jù)快速計(jì)算和高效存儲(chǔ)的問題，同時(shí)也有效地避免了PC機(jī)和小型數(shù)據(jù)中心的性能瓶頸。目前云計(jì)算已經(jīng)逐步擴(kuò)展并慢慢融入到我們的生活中，國(guó)外的谷歌、亞馬遜［1］、IBM［2］、微軟等公司已經(jīng)率先推廣云計(jì)算業(yè)務(wù)，國(guó)內(nèi)也有阿里巴巴、騰訊、百度等大型互聯(lián)網(wǎng)公司紛紛加入云計(jì)算行列，并有許多中小型企業(yè)也緊隨其后。

云計(jì)算的本質(zhì)是為用戶提供快速可靠的服務(wù)，用戶只需在終端將任務(wù)發(fā)送到云數(shù)據(jù)中心，即可使用云平臺(tái)來完成各種需求，并最終獲取處理結(jié)果。云數(shù)據(jù)中心由大量的服務(wù)器和網(wǎng)絡(luò)設(shè)備構(gòu)成，隨著用戶數(shù)量的逐步增多，將會(huì)有成千上萬的任務(wù)等待云來處理，因此設(shè)計(jì)出高效的云計(jì)算調(diào)度算法是云計(jì)算研究的關(guān)鍵所在。

Agarwal［3］等提出了基于遺傳算法的任務(wù)調(diào)度算法，在縮短任務(wù)完成時(shí)間方面有一定效果。文獻(xiàn)［4］提出基于最短任務(wù)延遲時(shí)間的改進(jìn)蟻群算法，在保證調(diào)度公平性和效率前提下有效縮短了任務(wù)延遲時(shí)間。文獻(xiàn)［5］以煙花算法作為云計(jì)算任務(wù)調(diào)度算法，在任務(wù)執(zhí)行時(shí)間和負(fù)載均衡兩個(gè)方面做優(yōu)化，相對(duì)于粒子群算法和遺傳算法有較好的效果。文獻(xiàn)［6］通過改進(jìn)蟻群算法，考慮虛擬機(jī)計(jì)算能力、網(wǎng)絡(luò)帶寬等因素，在負(fù)載均衡和任務(wù)執(zhí)行時(shí)間上有一定提升。Wang［7］等基于云計(jì)算和自適應(yīng)遺傳算法的特性，提出了基于時(shí)間跨度和負(fù)載均衡的雙適應(yīng)遺傳算法，采用貪心算法對(duì)種群進(jìn)行初始化，引入方差來描述節(jié)點(diǎn)間的負(fù)載密集度和多適應(yīng)函數(shù)的權(quán)重。該算法相比于自適應(yīng)遺傳算法，有更好的負(fù)載均衡度和最大完工時(shí)間。Sheng［8］等針對(duì)任提出了一種基于模板的遺傳算法結(jié)合用戶QoS約束的任務(wù)調(diào)度方法，根據(jù)處理器的CPU、帶寬等因素計(jì)算出應(yīng)該分配給每個(gè)處理器的任務(wù)最大尺寸，以此作為模板，將任務(wù)分割為多個(gè)子集并通過遺傳算法將這些子集合理分配到每個(gè)處理器。該算法可以有效縮短任務(wù)的最大完工時(shí)間。

本文通過對(duì)云計(jì)算任務(wù)調(diào)度中常用的蟻群優(yōu)化算法進(jìn)行分析，總結(jié)算法中的不足，分別在信息素更新和信息素?fù)]發(fā)兩個(gè)方面對(duì)算法進(jìn)行了改進(jìn)，并通過實(shí)驗(yàn)對(duì)算法進(jìn)行了驗(yàn)證。

2 云計(jì)算任務(wù)調(diào)度

云計(jì)算系統(tǒng)中的節(jié)點(diǎn)存在復(fù)雜性和異構(gòu)性等特點(diǎn)，隨著用戶數(shù)量的增加，云計(jì)算任務(wù)隊(duì)列中的用戶任務(wù)急劇增加，如何高效地進(jìn)行任務(wù)調(diào)度，提高任務(wù)執(zhí)行效率和資源利用率是云計(jì)算研究的重中之重。

針對(duì)云計(jì)算中龐大的任務(wù)量，任務(wù)調(diào)度一般會(huì)對(duì)任務(wù)進(jìn)行切分，首先將用戶提交的任務(wù)集合劃分為多個(gè)子任務(wù)，然后根據(jù)每個(gè)子任務(wù)的不同，并考慮虛擬資源節(jié)點(diǎn)的使用情況，合理進(jìn)行任務(wù)和虛擬資源的映射。該問題可以描述為：按照一定的策略將m任務(wù)分配到n異構(gòu)的虛擬資源節(jié)點(diǎn)上（n＜m），用Task={T1，T2，…Tm}表示所有待執(zhí)行子任務(wù)的集合，用VMN={V1，V2，…Vn}表示虛擬資源節(jié)點(diǎn)的集合，限制一個(gè)子任務(wù)只能在一個(gè)虛擬資源節(jié)點(diǎn)上運(yùn)行，則任務(wù)和虛擬資源節(jié)點(diǎn)的映射關(guān)系如式（1）所示：

其中TmVn表示子任務(wù)和虛擬機(jī)的對(duì)應(yīng)關(guān)系。任務(wù)調(diào)度最終將達(dá)到平均執(zhí)行時(shí)間最小、資源利用充分、服務(wù)質(zhì)量良好等目的。云計(jì)算任務(wù)調(diào)度原理圖如圖1所示。

圖1 云計(jì)算任務(wù)調(diào)度原理圖

3 算法描述

傳統(tǒng)的任務(wù)調(diào)度算法包括FCFS（First Come First Served）算法，RR（Round-Robin）算法［9］，SJF（Shortest Job First）算法，Max-min算法［10］，Min-min算法［11］等。云計(jì)算資源調(diào)度問題是一個(gè)NP完全問題，啟發(fā)式任務(wù)調(diào)度算法相比于基本的任務(wù)調(diào)度算法有更大的優(yōu)勢(shì)。常見的啟發(fā)式任務(wù)調(diào)度算法有遺傳算法［12］、模擬退火算法［13］、蟻群算法［14］和粒子群算法［15］等。

蟻群算法是由意大利學(xué)者M(jìn).Dorigo等于20世紀(jì)90年代模擬真實(shí)螞蟻的覓食行為過程而提出的一種啟發(fā)式仿生優(yōu)化算法［16］。目前，它已被廣泛用于解決大多數(shù)NP類問題的優(yōu)化求解，如旅行商問題、圖像著色、車輛調(diào)度、網(wǎng)絡(luò)路由、多重背包等靜態(tài)組合優(yōu)化和動(dòng)態(tài)組合優(yōu)化問題［17］。在后續(xù)的算法演變中，為了更真實(shí)地模擬螞蟻覓食的過程，出現(xiàn)了蟻群優(yōu)化算法。本文的算法改進(jìn)主要針對(duì)蟻群優(yōu)化算法。

3.1 蟻群優(yōu)化算法模型

假設(shè)在云計(jì)算環(huán)境中，現(xiàn)有n個(gè)虛擬機(jī)等待執(zhí)行任務(wù)，有m個(gè)任務(wù)等待處理，有x只螞蟻，螞蟻在覓食的過程中會(huì)在路徑上留下信息素，下一只螞蟻覓食時(shí)會(huì)根據(jù)信息素濃度選擇路徑，路徑選擇的概率公式如下所示：

其中ηij表示子任務(wù)i選擇虛擬機(jī)j時(shí)的啟發(fā)因子，它的值定義為表示第j個(gè)任務(wù)在第i個(gè)虛擬機(jī)上的執(zhí)行時(shí)間和任務(wù)傳輸時(shí)間的和，即，其中TLi表示第i臺(tái)虛擬機(jī)上的總?cè)蝿?wù)量，MIMPSi表示第i臺(tái)虛擬機(jī)對(duì)任務(wù)的處理速度，TSj表示傳遞到第i臺(tái)虛擬機(jī)的任務(wù)j的任務(wù)量，BWi表示第i臺(tái)虛擬機(jī)的帶寬。τij表示任務(wù)j選擇虛擬機(jī)i的信息素，α表示信息素啟發(fā)系數(shù)，代表路徑上信息素的影響程度，α越大，則對(duì)螞蟻選擇路徑的影響越大。β表示期望啟發(fā)系數(shù)，代表期望對(duì)路徑選擇的作用。另外，使用tabu表示禁忌表，螞蟻?zhàn)哌^的路徑將被加入禁忌表，防止路徑重復(fù)。allowedk表示螞蟻可以選擇的下一個(gè)虛擬機(jī)，也即除禁忌表以外的其他路徑。

螞蟻在尋找最優(yōu)路徑時(shí)，伴隨著信息素濃度的改變，公式如下：

其中，Δτij(t)表示所有螞蟻信息素的增量之和，Δτikj(t)表示第k只螞蟻在經(jīng)過路徑（i，j）時(shí)所產(chǎn)生的信息素，Q為算法引入的系數(shù)，Lk表示第k只螞蟻所走過的路程，ρ為信息素?fù)]發(fā)系數(shù)，它的值介于0和1之間，它的作用是為了防止算法陷入局部最優(yōu)解。

3.2 改進(jìn)的蟻群優(yōu)化算法

3.2.1 信息素更新方式的改進(jìn)

蟻群算法在搜索最有路徑時(shí)會(huì)出現(xiàn)收斂速度慢，搜索效率低的問題。本文針對(duì)這個(gè)問題，在蟻群算法的信息素更新公式中引入獎(jiǎng)懲系數(shù)，當(dāng)螞蟻在行進(jìn)的過程中如果發(fā)現(xiàn)了最優(yōu)（即最短）路徑，則立即根據(jù)獎(jiǎng)懲系數(shù)給當(dāng)前路徑予以“獎(jiǎng)勵(lì)”，即對(duì)信息素增加相應(yīng)的值，從而加強(qiáng)該路徑的信息素濃度。如果當(dāng)前路徑比上一次的路徑更長(zhǎng)，則根據(jù)獎(jiǎng)懲系數(shù)對(duì)當(dāng)前路徑進(jìn)行“懲罰”，即將信息素減去相應(yīng)的值來削弱改路徑的信息素濃度。在當(dāng)前螞蟻的整個(gè)搜索過程中，通過對(duì)比，找出長(zhǎng)度最長(zhǎng)的路徑（即最差解），對(duì)之進(jìn)行“嚴(yán)懲”，即根據(jù)獎(jiǎng)懲系數(shù)將最差路徑的信息素減去更大的值，在最大程度上減少其對(duì)螞蟻選擇路徑的干擾。

其中ω為引入的獎(jiǎng)懲系數(shù)，Lcur為當(dāng)前路徑的總長(zhǎng)度，Llast為上一次的路徑的總長(zhǎng)度。當(dāng)出現(xiàn)最優(yōu)路徑時(shí)，對(duì)當(dāng)前信息素濃度增加作為獎(jiǎng)勵(lì)，當(dāng)出現(xiàn)相對(duì)較差路徑時(shí)，則對(duì)當(dāng)前信息素濃度減去作為懲罰，當(dāng)出現(xiàn)最差路徑時(shí)，則對(duì)當(dāng)前信息素濃度減去作為嚴(yán)懲。

3.2.2 信息素?fù)]發(fā)系數(shù)的改進(jìn)

蟻群算法中，信息素?fù)]發(fā)系數(shù)ρ對(duì)算法的搜索性能有較大影響，ρ值越大，全局搜索能力將越差；ρ值越小，則局部搜索能力越差，因此合理的處理ρ值，會(huì)直接影響到搜索的結(jié)果，使用 ρ(t+1)表示更新后的信息素?fù)]發(fā)系數(shù)，本文采用的ρ值更新公式如下：

其中g(shù)en表示算法迭代到第gen代，μ表示比例系數(shù)，為固定常數(shù)，ρmin為 ρ值得最小臨界值。余弦函數(shù)在0～之間的曲線圖如圖2所示。

圖2 余弦函數(shù)在0～之間的曲線圖

算法中通過將算法迭代的代數(shù)（0，gen］按比例映射到（0，］之間，通過上述方式，將 ρ值以余弦函數(shù)遞減方式更新，從而達(dá)到兼顧局部搜索和全局搜索的目的。

4 改進(jìn)蟻群優(yōu)化算法求解步驟

1）對(duì)算法進(jìn)行初始化；

2）將x只螞蟻隨機(jī)分配到相應(yīng)的虛擬機(jī)上；

3）對(duì)每只螞蟻移動(dòng)到下一個(gè)節(jié)點(diǎn)的概率Pikj進(jìn)行計(jì)算，然后將螞蟻移動(dòng)到計(jì)算結(jié)果指示的節(jié)點(diǎn)上；

4）當(dāng)螞蟻移動(dòng)到新的節(jié)點(diǎn)上后，更新其經(jīng)過路徑的信息素，并修改禁忌表；

5）重復(fù)執(zhí)行步驟2），3），4），直到整個(gè)蟻群中的每個(gè)螞蟻都找到一個(gè)可行路徑為止；

6）對(duì)比所有可行路徑，通過式（4）對(duì)當(dāng)前最優(yōu)路徑進(jìn)行“獎(jiǎng)勵(lì)”，對(duì)最差路徑進(jìn)行“嚴(yán)懲”，對(duì)比上一個(gè)路徑長(zhǎng)的路徑進(jìn)行“輕罰”；

7）對(duì)所有路徑上的信息素進(jìn)行全局更新；

8）如果迭代次數(shù)達(dá)到預(yù)設(shè)迭代次數(shù)，則終止搜索，得出最優(yōu)解。

算法的偽代碼如下：

Begin

初始化算法參數(shù)、任務(wù)集合T、虛擬資源節(jié)點(diǎn)集合V、螞蟻數(shù)量X、最大迭代次數(shù)gen；

將X只螞蟻隨機(jī)分布到虛擬資源節(jié)點(diǎn)集合V上，并對(duì)每只螞蟻的禁忌表tabu、各路徑信息素濃度進(jìn)行初始化；

While（達(dá)到迭代次數(shù)）do

For each螞蟻do

While（當(dāng)前螞蟻找到可行路徑）do

根據(jù)式（2）計(jì)算概率來選擇下一個(gè)資源節(jié)點(diǎn)執(zhí)行任務(wù)；

當(dāng)螞蟻移動(dòng)到新的節(jié)點(diǎn)上后，更新其經(jīng)過路徑的信息素，并修改禁忌表；

當(dāng)螞蟻找到可行路徑，記錄路徑總長(zhǎng)度。

End while

對(duì)比可行路徑，記錄最優(yōu)和最差路徑，通過式（4）對(duì)當(dāng)前最優(yōu)路徑進(jìn)行“獎(jiǎng)勵(lì)”，對(duì)最差路徑進(jìn)行“嚴(yán)懲”，對(duì)比上一個(gè)路徑長(zhǎng)的路徑進(jìn)行“輕罰”；

更新最優(yōu)路徑中任務(wù)和虛擬節(jié)點(diǎn)的對(duì)應(yīng)關(guān)系；End for

通過式（3）來更新所有路徑的信息素濃度；

重新隨機(jī)選擇螞蟻的位置；

End while

給出最優(yōu)路徑，并記錄負(fù)載均衡度值；

End

5 實(shí)驗(yàn)驗(yàn)證與分析

本文使用Cloudsim進(jìn)行模擬實(shí)驗(yàn)驗(yàn)證改進(jìn)蟻群算法（MACO）在云移動(dòng)應(yīng)用測(cè)試任務(wù)調(diào)度方面的可行性。實(shí)驗(yàn)中使用的硬件環(huán)境是三星筆記本電腦，具體配置為Intel（R）Core（TM）i5-7300HQ CPU@2.5GHz，8G內(nèi)存，500G硬盤，Windows10操作系統(tǒng)，使用Intellij Idea搭建CloudSim運(yùn)行環(huán)境。CloudSim的執(zhí)行步驟如下：

1）對(duì)CloudSim進(jìn)行初始化；

2）創(chuàng)建數(shù)據(jù)中心；

3）創(chuàng)建DatacenterBroker，用于協(xié)調(diào)和分配資源；

4）創(chuàng)建虛擬機(jī)；

5）將虛擬機(jī)添加到虛擬機(jī)列表中，同時(shí)將虛擬機(jī)列表提交到DatacenterBroker；

6）創(chuàng)建云任務(wù)集合；

7）將云任務(wù)（Cloudlet）添加到云任務(wù)集合中，并提交到DatacenterBroker；

8）開始仿真，仿真結(jié)束后打印結(jié)果。

5.1 實(shí)驗(yàn)參數(shù)設(shè)置

在實(shí)驗(yàn)中設(shè)置虛擬機(jī)的個(gè)數(shù)為20個(gè)，任務(wù)個(gè)數(shù)分別設(shè)置為50，100，150，200，250，300個(gè)，螞蟻數(shù)為20個(gè)，迭代次數(shù)為100次。文中對(duì)蟻群算法的參數(shù)取值如表1所示。

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

根據(jù)表1設(shè)置的算法參數(shù)進(jìn)行實(shí)驗(yàn)，首先將本文的改進(jìn)蟻群算法（MACO）同傳統(tǒng)的蟻群優(yōu)化算法（ACO）進(jìn)行實(shí)驗(yàn)比較，兩個(gè)算法分別執(zhí)行10次，對(duì)所得結(jié)果取平均值，對(duì)比圖如圖2所示。

圖3 MACO，ACO算法任務(wù)執(zhí)行時(shí)間對(duì)比

從圖3中可以看出，當(dāng)任務(wù)量比較小時(shí)改進(jìn)蟻群算法（MACO）和原始蟻群優(yōu)化算法（ACO）的任務(wù)執(zhí)行時(shí)間相差在3s左右，隨著任務(wù)量的逐步增大，改進(jìn)的蟻群算法在任務(wù)執(zhí)行時(shí)間上的優(yōu)勢(shì)更加明顯，當(dāng)任務(wù)量達(dá)到300個(gè)時(shí)，兩種算法的任務(wù)執(zhí)行時(shí)間相差10s多，因此相比之下MACO算法在云測(cè)試調(diào)度中有更高效率。

相同的實(shí)驗(yàn)環(huán)境，將改進(jìn)的蟻群算法同先來先服務(wù)算法（FCFS）和Max-min算法進(jìn)行對(duì)比，同樣每個(gè)算法各執(zhí)行10次，對(duì)得到的結(jié)果取平均值，所得結(jié)果如如圖4所示。

由圖3可得，本文的改進(jìn)蟻群優(yōu)化算法（MA?CO）在任務(wù)執(zhí)行時(shí)間上要優(yōu)于FCFS算法和Max-min算法。由實(shí)驗(yàn)數(shù)據(jù)可得，當(dāng)任務(wù)量為100時(shí)，MACO算法的任務(wù)執(zhí)行時(shí)間相較于FCFS算法和Max-min算法分別少41s和19s，當(dāng)任務(wù)量增大至300個(gè)時(shí)，MACO算法的任務(wù)執(zhí)行時(shí)間相較于FCFS算法和Max-min算法分別少305s和220s，因此MACO算法的性能要遠(yuǎn)優(yōu)于FCFS算法和Max-min算法。

圖4 MACO，F(xiàn)CFS，Max-min算法任務(wù)執(zhí)行時(shí)間對(duì)比

圖5 算法負(fù)載均衡度比較

圖5 顯示了MACO、ACO、FCFS和Max-min算法的負(fù)載均衡度對(duì)比情況，由圖可得，MACO算法相對(duì)于FCFS算法和Max-min算法，在實(shí)現(xiàn)負(fù)載均衡上有較為明顯的優(yōu)勢(shì)，而相對(duì)與ACO算法，在保證負(fù)載均衡度的前提下可以有效降低任務(wù)執(zhí)行時(shí)間，因而MACO算法總體上更具有優(yōu)勢(shì)。

綜合以上實(shí)驗(yàn)可知本文的改進(jìn)蟻群算法在降低總?cè)蝿?wù)執(zhí)行時(shí)間和實(shí)現(xiàn)負(fù)載均衡方面都有較好的效果，因而證明了本文算法的可行性。

6 結(jié)語

本文介紹了云計(jì)算技術(shù)特點(diǎn)和現(xiàn)有工作，并對(duì)云計(jì)算任務(wù)調(diào)度遠(yuǎn)離進(jìn)行了總結(jié)，同時(shí)提出了一種基于改進(jìn)蟻群優(yōu)化算法的云計(jì)算任務(wù)調(diào)度方法。該算法從蟻群算法的信息素更新和信息素?fù)]發(fā)兩個(gè)方面進(jìn)行改進(jìn)，并使用CloudSim進(jìn)行了仿真實(shí)驗(yàn)，分別同F(xiàn)CFS、ACO和Max-min算法進(jìn)行了對(duì)比，最終驗(yàn)證了本文調(diào)度方法的可行性。將來的工作將進(jìn)行算法的進(jìn)一步優(yōu)化和提高資源利用率，同時(shí)也會(huì)在保證QoS和降低云數(shù)據(jù)中心能耗等方面進(jìn)行研究。