王恩重 陶傳奇

（1.南京理工大學計算機科學與工程學院 南京 210094）（2.南京航空航天大學計算機科學與技術(shù)學院 南京 210016）（3.計算機軟件新技術(shù)國家重點實驗室（南京大學） 南京 210023）

1 引言

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

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

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

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

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

2 云計算任務調(diào)度

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

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

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

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

3 算法描述

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

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

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

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

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

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

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

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

3.2.1 信息素更新方式的改進

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

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

3.2.2 信息素揮發(fā)系數(shù)的改進

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

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

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

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

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

1）對算法進行初始化；

2）將x只螞蟻隨機分配到相應的虛擬機上；

3）對每只螞蟻移動到下一個節(jié)點的概率Pikj進行計算，然后將螞蟻移動到計算結(jié)果指示的節(jié)點上；

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

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

6）對比所有可行路徑，通過式（4）對當前最優(yōu)路徑進行“獎勵”，對最差路徑進行“嚴懲”，對比上一個路徑長的路徑進行“輕罰”；

7）對所有路徑上的信息素進行全局更新；

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

算法的偽代碼如下：

Begin

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

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

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

For each螞蟻do

While（當前螞蟻找到可行路徑）do

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

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

當螞蟻找到可行路徑，記錄路徑總長度。

End while

對比可行路徑，記錄最優(yōu)和最差路徑，通過式（4）對當前最優(yōu)路徑進行“獎勵”，對最差路徑進行“嚴懲”，對比上一個路徑長的路徑進行“輕罰”；

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

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

重新隨機選擇螞蟻的位置；

End while

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

End

5 實驗驗證與分析

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

1）對CloudSim進行初始化；

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

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

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

5）將虛擬機添加到虛擬機列表中，同時將虛擬機列表提交到DatacenterBroker；

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

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

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

5.1 實驗參數(shù)設(shè)置

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

5.2 實驗結(jié)果及分析

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

圖3 MACO，ACO算法任務執(zhí)行時間對比

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

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

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

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

圖5 算法負載均衡度比較

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

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

6 結(jié)語

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