基于蟻群優(yōu)化算法的云任務(wù)分配策略研究

姜力爭 裴云曼 趙建濤

(華北電力大學(xué)控制與計(jì)算機(jī)工程學(xué)院 北京 102206)

0 引 言

云計(jì)算[1-2]是一種新型的計(jì)算模型，它通過虛擬化技術(shù)，將分布于不同網(wǎng)絡(luò)節(jié)點(diǎn)的資源聯(lián)系起來形成資源池，為用戶所需資源進(jìn)行統(tǒng)一管理和統(tǒng)一分配。而云計(jì)算中的任務(wù)分配算法的優(yōu)劣對用戶的滿意程度與平臺(tái)的質(zhì)量效率產(chǎn)生了直接的影響，因此任務(wù)分配算法一直是云計(jì)算領(lǐng)域的重點(diǎn)研究方向。近年來，許多專家學(xué)者對云計(jì)算中的任務(wù)分配問題進(jìn)行了深入研究。任務(wù)分配算法大致可以分為三類[3]。第一類為基于經(jīng)典策略的任務(wù)分配算法，如輪詢算法、Min-Min算法和Max-Min算法等。第二類為基于單一群智能優(yōu)化算法的任務(wù)分配算法，如蟻群算法、遺傳算法、蛙跳算法等。第三類為基于混合群智能優(yōu)化算法的任務(wù)分配算法，如遺傳-蟻群算法[4]、蛙跳-蟻群算法[5]等。

蟻群算法[6](Ant colony optimization,ACO)是一種仿生優(yōu)化算法，其靈感是Marco Dorigo發(fā)現(xiàn)螞蟻在覓食過程中群體所表現(xiàn)出來的超高的團(tuán)隊(duì)合作能力，能夠很好地應(yīng)用于任務(wù)-資源分配的N-P問題。文獻(xiàn)[6]提出劣化因子蟻群算法，劣化因子的合理選擇不僅可以平衡負(fù)載還能提高資源的利用率。文獻(xiàn)[7]提出的改進(jìn)信息素?fù)]發(fā)程度的蟻群優(yōu)化算法，提高局部和全局的搜索性能。文獻(xiàn)[2]提出的基于資源狀態(tài)的蟻群算法，在資源消耗和任務(wù)等待時(shí)間上有較大優(yōu)勢。上述研究從不同角度上都改進(jìn)了云計(jì)算任務(wù)分配問題。但是云計(jì)算的任務(wù)分配問題是一個(gè)需要以多指標(biāo)最優(yōu)為最終目標(biāo)，既要考慮云服務(wù)的穩(wěn)定性和用戶的滿意程度，又要考慮資源的使用效率和運(yùn)營成本。現(xiàn)有的研究多以單一指標(biāo)為最終的研究目標(biāo)，缺乏對任務(wù)分配問題的全面考慮。

針對上述的問題，本文通過對任務(wù)分配模型的分析，提出服務(wù)穩(wěn)定性好、資源利用率高、任務(wù)完成時(shí)間短的任務(wù)分配模型。基于該模型，改變資源執(zhí)行任務(wù)的可見度，自適應(yīng)方式調(diào)節(jié)信息量，根據(jù)虛擬機(jī)狀態(tài)更新信息素的蟻群優(yōu)化算法。與輪詢算法、Min-Min算法、標(biāo)準(zhǔn)蟻群算法以及文獻(xiàn)[11]提出的優(yōu)化蟻群算法(OACO)進(jìn)行仿真實(shí)驗(yàn)，實(shí)驗(yàn)結(jié)果表明該蟻群優(yōu)化算法在任務(wù)完成時(shí)間、資源利用率以及服務(wù)穩(wěn)定性上具有顯著優(yōu)勢。

1 任務(wù)分配模型分析

云環(huán)境下的任務(wù)分配模型[1]可以分為三層：應(yīng)用層、調(diào)度層和物理層。在云環(huán)境中，應(yīng)用層存在多個(gè)用戶，每個(gè)用戶都可以發(fā)送請求來運(yùn)行多個(gè)應(yīng)用，每個(gè)應(yīng)用又對應(yīng)著多個(gè)任務(wù)。調(diào)度層會(huì)根據(jù)不同的任務(wù)分配不同的虛擬機(jī)。任務(wù)分配的過程實(shí)質(zhì)上是將任務(wù)按照某一分配原則分配到虛擬機(jī)節(jié)點(diǎn)上執(zhí)行的過程。任務(wù)分配過程，如圖1所示。

圖1 任務(wù)分配過程

由此，可將任務(wù)在虛擬機(jī)上的執(zhí)行時(shí)間定義為Max(costi)，總資源消耗定義為∑exeij。

2 基本蟻群算法

蟻群算法具有并行、自組織、魯棒性強(qiáng)、正反饋的特點(diǎn)[8]。其智能性主要體現(xiàn)在以下三個(gè)方面：

(1) 螞蟻之間可以利用信息素進(jìn)行“交流”。

(2) 螞蟻在搜索路徑的過程中，已經(jīng)被螞蟻搜索過的路徑將不會(huì)再被選擇。

(3) 螞蟻之間有很強(qiáng)的團(tuán)隊(duì)合作能力，單憑一只螞蟻，很難找到食物。

2.1 定義變量

為了方便描述，定義以下變量：

antNum為螞蟻數(shù)量；

taskNum為任務(wù)數(shù)量；

vmNum為虛擬機(jī)數(shù)量；

iterationTimes為迭代次數(shù)；

optimalPath為最優(yōu)路徑；

pheromone[taskNum][vmNum]為信息素矩陣；

α為信息素因子；

β為可見度因子；

ρ為信息素?fù)]發(fā)因子。

2.2 算法步驟描述

Step1初始化信息素矩陣、最佳長度以及antNum只螞蟻。

pheromone[i][j]=0.1f,ifi

optimalPath=MAX_VALUE

Ants[i].init(exe,α,β), ifi

Step2如果循環(huán)次數(shù)小于迭代次數(shù)iterationTimes，則執(zhí)行第三步到第五步，否則輸出結(jié)果，算法結(jié)束。

(1)

Step4更新禁忌表和可搜索列表。

Step5更新信息素濃度。

(2)

(3)

基本蟻群算法的任務(wù)分配流程如圖2所示。

圖2 基本蟻群算法的任務(wù)分配流程

3 蟻群優(yōu)化算法

基本蟻群算法[8]在處理較小規(guī)模的任務(wù)分配問題時(shí)能夠快速找到最優(yōu)解，但隨著大數(shù)據(jù)時(shí)代的帶來，數(shù)據(jù)呈現(xiàn)出井噴式爆發(fā)增長的趨勢，數(shù)據(jù)的高性能計(jì)算是云計(jì)算任務(wù)分配的核心問題。基本蟻群算法隨著數(shù)據(jù)規(guī)模的擴(kuò)大計(jì)算性能嚴(yán)重下降，為此，本文針對基本蟻群算法的缺點(diǎn)進(jìn)行了優(yōu)化改進(jìn)。

相較于基本蟻群算法，優(yōu)化算法主要體現(xiàn)在以下幾個(gè)方面。

(1) 根據(jù)虛擬機(jī)狀態(tài)對任務(wù)ti選擇虛擬機(jī)rj執(zhí)行的啟發(fā)式因子ηij(t)進(jìn)行優(yōu)化。將虛擬機(jī)的消耗考慮其中，減少任務(wù)的等待時(shí)間。

(4)

式中：costj(t)表示t時(shí)刻虛擬機(jī)vmj的狀態(tài)情況。

(2) 在任務(wù)選擇虛擬機(jī)vj執(zhí)行后，更新虛擬機(jī)的消耗狀態(tài)costj。

costj=costj+exeij

(5)

(3) 更新信息素濃度時(shí)，采用自適應(yīng)信息量的更新策略改變?chǔ)觟j(new)的值，動(dòng)態(tài)調(diào)整信息量強(qiáng)度，提高全局的搜索能力，避免陷入局部最優(yōu)解。

(6)

(7)

式中：Q為常量，代表每只螞蟻釋放信息素的強(qiáng)弱程度。

4 實(shí)驗(yàn)設(shè)計(jì)與分析

本實(shí)驗(yàn)采用CloudSim-3.0.3作為實(shí)驗(yàn)環(huán)境，步驟主要包括：產(chǎn)生實(shí)驗(yàn)數(shù)據(jù)，為保證實(shí)驗(yàn)的準(zhǔn)確性，每種條件的數(shù)據(jù)為10組，取平均值作為最終結(jié)果。將不同條件的數(shù)據(jù)由不同的算法執(zhí)行求取最優(yōu)解，使用CloudSim進(jìn)行仿真實(shí)驗(yàn)，得出的實(shí)驗(yàn)結(jié)果做可視化圖形處理。

由文獻(xiàn)[9]可知，任務(wù)執(zhí)行時(shí)間可以認(rèn)為只與任務(wù)的指令長度(MI)和虛擬機(jī)的執(zhí)行速度(MIPS)有關(guān)，一個(gè)任務(wù)所需的執(zhí)行時(shí)間等于任務(wù)指令長度除以運(yùn)行該任務(wù)的虛擬機(jī)的執(zhí)行速度。創(chuàng)建指定任務(wù)數(shù)量以及任務(wù)長度等信息的云任務(wù)，提交給任務(wù)代理。創(chuàng)建指定CPU數(shù)量以及執(zhí)行速度等信息的虛擬機(jī)提交給任務(wù)代理。任務(wù)代理根據(jù)QoS要求提供任務(wù)與資源的分配策略。模擬為虛擬機(jī)分配處理核所用的策略為空間共享。

以隨機(jī)數(shù)的方式設(shè)置任務(wù)的MI范圍為500 000到3 000 000。以隨機(jī)數(shù)的方式設(shè)置虛擬機(jī)的MIPS范圍為500到2 000。設(shè)置任務(wù)數(shù)分別為20、40、60、80、100。設(shè)置虛擬機(jī)數(shù)為5。設(shè)置螞蟻數(shù)為100，迭代次數(shù)為50。

根據(jù)文獻(xiàn)[10]研究，將蟻群算法的參數(shù)設(shè)置為α=1.0，β=5.0，ρ=0.5，Q=5.0。

綜上所述，云計(jì)算任務(wù)分配仿真實(shí)驗(yàn)參數(shù)設(shè)置表見表1。

表1 云計(jì)算任務(wù)分配仿真實(shí)驗(yàn)參數(shù)設(shè)置表

如圖3所示，所提出的基于資源狀態(tài)的自適應(yīng)蟻群優(yōu)化算法(MACO)調(diào)度任務(wù)完成時(shí)間最短，相比于輪詢算法(RR)與基本蟻群算法(BACO)具有顯著優(yōu)勢，并且隨著任務(wù)數(shù)量的增加，優(yōu)勢會(huì)愈加明顯。Min-Min算法是將最小的任務(wù)映射到執(zhí)行最快的虛擬機(jī)上，結(jié)果顯示Min-Min算法的效果較好，僅稍次于MACO算法。本文提出的MACO算法相比于RR算法提高了35.55%±8.13%，相比于BACO算法提高了20.5%±7.13%，相比于Min-Min算法提高了8.21%±5.07%。

圖3 任務(wù)完成時(shí)間對比圖

文獻(xiàn)[11]提出的優(yōu)化蟻群算法(OACO)，其實(shí)驗(yàn)參數(shù)與實(shí)驗(yàn)結(jié)果與本文較為相似，因此采用文獻(xiàn)[11]中的實(shí)驗(yàn)結(jié)果數(shù)據(jù)進(jìn)行對比實(shí)驗(yàn)。為與文獻(xiàn)[11]中的數(shù)據(jù)保持一致性，另外生成一組任務(wù)數(shù)為25、50、75、100的實(shí)驗(yàn)數(shù)據(jù)。為排除因?qū)嶒?yàn)數(shù)據(jù)不同而造成的差異，均以相對RR算法的比值進(jìn)行比較。如圖4所示，OACO算法相對RR算法的時(shí)間比例隨任務(wù)數(shù)的變化起伏較大，算法的穩(wěn)定性比本文提出MACO差。在任務(wù)數(shù)為25時(shí)，OACO算法的完成時(shí)間優(yōu)于本文的MACO算法，但隨著任務(wù)數(shù)的增加，本文提出的算法MACO提高比例逐漸降低并顯著優(yōu)于OACO算法。無疑在大數(shù)據(jù)的時(shí)代，本文提出的MACO算法穩(wěn)定性更高。OACO算法相比于RR算法提高了43.88%±6.85%，而本文提出的MACO算法相比于RR算法提高了44.29%±3.62%，以標(biāo)準(zhǔn)差來衡量算法的穩(wěn)定性，則本文算法的算法穩(wěn)定性是OACO算法的1.89倍。

圖4 相對RR算法完成時(shí)間對比圖

平臺(tái)的占用時(shí)間，是一批任務(wù)全部完成時(shí)占用虛擬機(jī)的全部時(shí)間和，可以反映任務(wù)對資源的消耗情況。如圖5所示，完成同一批任務(wù)，本文提出的MACO算法占用平臺(tái)時(shí)間最少，平臺(tái)資源的利用率最高。本文提出的MACO算法相比于RR算法提高了9.11%±2.78%，相比于Min-Min算法提高了1.81%±1.59%。

圖5 平臺(tái)占用時(shí)間對比圖

5 結(jié) 語

本文提出了一種基于資源狀態(tài)的自適應(yīng)蟻群優(yōu)化算法，該算法利用虛擬機(jī)的狀態(tài)來修正啟發(fā)式因子和釋放信息素濃度，并以自適應(yīng)的方式進(jìn)行信息量的更新，避免早熟和局部收斂，提高全局搜索能力。實(shí)驗(yàn)結(jié)果表明，該算法在任務(wù)完成時(shí)間、資源利用率和服務(wù)穩(wěn)定性方面均有良好表現(xiàn)。