李成嚴(yán)　曹克翰　馮世祥　孫巍

摘要：針對(duì)執(zhí)行時(shí)間不確定情況下的云計(jì)算資源調(diào)度問題，基于模糊規(guī)劃理論建立了時(shí)間-成本約束條件下的模糊云資源調(diào)度模型，使用三角模糊數(shù)表示不確定的任務(wù)執(zhí)行時(shí)間，以最小化評(píng)價(jià)函數(shù)的平均值和不確定度作為調(diào)度目標(biāo)。提出一種改進(jìn)的混沌蟻群算法對(duì)模型進(jìn)行求解，算法引入精英策略優(yōu)化了信息素的更新，采用折疊次數(shù)無窮大的混沌映射進(jìn)行混沌搜索，并設(shè)計(jì)了自適應(yīng)混沌擾動(dòng)機(jī)制以增強(qiáng)算法的全局搜索能力。在Cloudsim平臺(tái)上用仿真數(shù)值實(shí)例對(duì)模型和算法進(jìn)行驗(yàn)證，證明了模型的可靠性，實(shí)驗(yàn)結(jié)果表明改進(jìn)算法在收斂速度、求解能力和負(fù)載均衡上均有較好的性能。

關(guān)鍵詞：

云計(jì)算;資源調(diào)度;模糊規(guī)劃;混沌擾動(dòng)

DOI：10.15938/j.jhust.2019.01.014

中圖分類號(hào)： TP399

文獻(xiàn)標(biāo)志碼： A

文章編號(hào)： 1007-2683（2019）01-0085-07

Resource Scheduling with Uncertain Execution?Time in Cloud Computing

LI Cheng?yan，CAO Ke?han，F(xiàn)ENG Shi?xiang，SUN Wei

（School of Computer Science and Technology， Harbin University of Science and Technology， Harbin 150080， China）

Abstract：For the problem of cloud computing resource scheduling， based on the fuzzy programming theory， a fuzzy cloud resource scheduling model under time?cost constraint was set up， the uncertain execution time of tasks is represented by the triangular fuzzy number， and the target is to minimize the average value and standard deviation of the evaluation function?An improved chaotic ant colony algorithm was proposed to solve the model， the elitist strategy is introduced to optimize the pheromone updating， a chaotic mapping with infinite folding times is used for chaotic search， and the adaptive chaotic disturbance mechanism is designed to enhance the global searching ability?The model and algorithm were tested on the Cloudsim platform， the reliability of the model was proved， and the experimental results showed that the proposed algorithm had better performance in convergence speed， solution ability and load balance

Keywords：cloud computing; resource scheduling; fuzzy programming; chaotic disturbance

0引言

云計(jì)算系統(tǒng)應(yīng)用虛擬化技術(shù)，以較低的成本提供高質(zhì)量的資源服務(wù)，用戶根據(jù)自身需求選擇并付費(fèi)使用相應(yīng)的服務(wù)[1]。云計(jì)算資源調(diào)度的研究目標(biāo)是合理的將多個(gè)任務(wù)分配到虛擬資源節(jié)點(diǎn)上執(zhí)行，并滿足執(zhí)行時(shí)間短、所需成本低、虛擬資源集群負(fù)載均衡等條件，文[2]證明了該調(diào)度問題是一個(gè)NP完全問題。

當(dāng)前云計(jì)算資源調(diào)度問題的研究主要集中于確定環(huán)境下，文[3]提出了云計(jì)算任務(wù)調(diào)度中一種基于權(quán)重的混合啟發(fā)式方法。文[4]以最小化完工時(shí)間為目標(biāo)，建立了云計(jì)算任務(wù)調(diào)度模型。文[5]建立了云計(jì)算環(huán)境下的多目標(biāo)工作流調(diào)度模型，在降低完工時(shí)間和成本的同時(shí)，減少能耗。在以上這些研究中，均假設(shè)任務(wù)在虛擬機(jī)上的執(zhí)行時(shí)間是已知的確定值，然而在實(shí)際系統(tǒng)中，任務(wù)在完成之前其執(zhí)行時(shí)間是不確定的，稱為不確定性或異步性，這是由當(dāng)前的計(jì)算機(jī)任務(wù)執(zhí)行特性所決定的。因此造成云資源調(diào)度的初始條件是不確定的，所以在研究資源調(diào)度問題時(shí)必須予以考慮。在引入不確定性后，對(duì)云計(jì)算資源調(diào)度問題的求解變得更加復(fù)雜，對(duì)不確定量的描述有隨機(jī)變量、模糊變量、灰色變量等，模糊變量是在當(dāng)概念的外延不清晰時(shí)使用的一種方法。在資源調(diào)度問題中，任務(wù)的執(zhí)行時(shí)間存在不清晰的特征，因此模糊變量和模糊優(yōu)化技術(shù)是一種有效的手段。文[6]研究了云計(jì)算中基于模糊的資源重調(diào)度問題，文[7]建立了以最小化作業(yè)完成時(shí)間為目標(biāo)的模糊調(diào)度模型。本文使用三角模糊數(shù)表示不確定的任務(wù)執(zhí)行時(shí)間，建立了模糊云資源調(diào)度問題的期望值模型。

為求解云計(jì)算資源調(diào)度問題，智能優(yōu)化算法得到了較多的應(yīng)用，如遺傳算法[8]（GA）、粒子群算法[9]（PSO）和蟻群算法[10]（ACO），但以上算法皆有不足，因此國內(nèi)外學(xué)者對(duì)它們進(jìn)行了改進(jìn)。文[11]在PSO中引入了貪心算法，通過貪心算法快速求解PSO的初始粒子值。文[12]將混沌系統(tǒng)和蟻群算法結(jié)合起來，提出了一種混沌蟻群算法（Chaotic Ant Colony Optimization Algorithm，CACO），通過混沌擾動(dòng)使算法跳出局部極值區(qū)間。文[13]在蟻群系統(tǒng)中使用了精英策略，加快了算法收斂速度的同時(shí)提高了解的質(zhì)量。為進(jìn)一步優(yōu)化算法的性能，本文在CACO的基礎(chǔ)上，引入精英策略，并設(shè)計(jì)了自適應(yīng)混沌擾動(dòng)機(jī)制，提出了一種基于精英策略的改進(jìn)算法（chaotic ant colony optimization algorithm based on elitist strategy，ECACO）。

本文使用模糊規(guī)劃的方法，在云計(jì)算資源調(diào)度問題中引入不確定的任務(wù)執(zhí)行時(shí)間，建立模糊云資源調(diào)度問題的期望值模型，并提出一種改進(jìn)算法對(duì)模型進(jìn)行求解。本文結(jié)構(gòu)如下，第1部分建立了模糊云資源調(diào)度問題的期望值模型，并對(duì)模型的求解進(jìn)行了分析，第2部分介紹了算法的設(shè)計(jì)過程，第3部分通過仿真實(shí)驗(yàn)對(duì)模型和算法進(jìn)行驗(yàn)證，最后作出結(jié)論。

1模糊云資源調(diào)度問題

1?1模糊云資源調(diào)度模型

云計(jì)算中資源調(diào)度問題可以描述為將任務(wù)集合?T={t?1，t?2，…，t?n}中的n個(gè)任務(wù)，分配到虛擬機(jī)集合VM={vm?1，vm?2，…，vm?m}中的m個(gè)虛擬機(jī)上執(zhí)行（m

RCU={rcu?1，rcu?2，…，rcu?m}（1）

ETC=?11?12?…?1n

21?22?…?2n

m1?m2?…?mn?（2）

其中，rcu?i為vm?i單位時(shí)間內(nèi)執(zhí)行任務(wù)消耗的資源成本。在一個(gè)完整的資源調(diào)度方案P中，虛擬機(jī)vm?i執(zhí)行任務(wù)所需時(shí)間vmTime?i和成本vmCost?i分別為

vmTime?i=∑nj=1d?j?×?ij?，d?j?∈vmTask?i（3）

vmCost?i=vmTime?i×rcu?i（4）

其中，vmTask?i為分配在vm?i上執(zhí)行的任務(wù)集合。執(zhí)行調(diào)度方案P?i需要的總時(shí)間為

Time（P?i）=?max?{vmTime?1，vmTime?2，…，vmTime?m}（5）

執(zhí)行任務(wù)的總成本為

Cost（P?i）=∑mi=1vmCost?i（6）

在云環(huán)境中，資源的調(diào)度需要考慮多方面的因素，任務(wù)完成時(shí)間決定了客戶的滿意度，而資源提供商希望盡可能的降低成本，因此提出一個(gè)時(shí)間-成本約束條件，將兩者同時(shí)納入考慮范圍。其中，時(shí)間約束函數(shù)為

rTime（P?i）=Time（P?i）-Time?MIN?Time?MAX?-Time?MIN?（7）

成本約束函數(shù)為

rCost（P?i）=Cost（P?i）-Cost?MIN?Cost?MAX?-Cost?MIN?（8）

其中，Time?MAX?、Time?MIN?為任務(wù)在性能最差、最好的機(jī)器上運(yùn)行所需要的時(shí)間，Cost?MAX?、Cost?MIN?為任務(wù)在執(zhí)行時(shí)所需的最高、最低成本。rTime（P?i）和rCost（P?i）的值越小，執(zhí)行任務(wù)所需的時(shí)間和成本就越少。

在時(shí)間-成本選擇約束條件下的云計(jì)算資源調(diào)度模型為

min?{res（P?i）}（9）

其中，評(píng)價(jià)函數(shù)

res（P?i）=trTime（P?i）+crCost（P?i）（10）

由于任務(wù)在虛擬機(jī)上的執(zhí)行時(shí)間是模糊數(shù)，所以評(píng)價(jià)函數(shù)值也是模糊數(shù)。目標(biāo)函數(shù)是使基于時(shí)間-成本約束條件的評(píng)價(jià)函數(shù)的期望值最小。其中：?t是?時(shí)間因子，c是成本因子， 且t+c=1?？梢酝ㄟ^調(diào)節(jié)t和c的取值來影響資源選擇時(shí)的傾向，當(dāng)t=1，c=0時(shí)，調(diào)度的目標(biāo)為最小化任務(wù)完成時(shí)間;當(dāng)t=0，c=1時(shí)，調(diào)度的目標(biāo)為最小化成本;當(dāng)t=0?5，c=0?5時(shí)，調(diào)度的目標(biāo)為使任務(wù)完成時(shí)間較短的同時(shí)，令成本也較低。

定義虛擬資源的負(fù)載均衡函數(shù)為

Load=?min?1≤i≤m?vmTime?i?max?1≤i≤m?vmTime?i（11）

式中，?min?1≤i≤m?vmTime?i表示調(diào)度方案中虛擬機(jī)的最短執(zhí)行時(shí)間，?max?1≤i≤m?vmTime?i為虛擬機(jī)最長(zhǎng)執(zhí)行時(shí)間，即調(diào)度方案總執(zhí)行時(shí)間。由式（11）可知

1）若?max?1≤i≤m?vmTime?i=0，則任務(wù)還未被執(zhí)行;

2）若Load=0且?max?1≤i≤m?vmTime?i！=0，此時(shí)有空閑虛擬機(jī);

3）若Load=1，則各虛擬機(jī)的執(zhí)行時(shí)間相同，此時(shí)系統(tǒng)的負(fù)載均衡性達(dá)到最佳，Load的值越接近1，證明系統(tǒng)對(duì)資源的利用越充分。

1?2模型轉(zhuǎn)換

本文使用三角模糊數(shù)來表示任務(wù)在虛擬機(jī)上不確定的執(zhí)行時(shí)間e～?ij?，三角模糊數(shù)R～=（r?L，r?M，r?R）的隸屬度函數(shù)圖如圖1所示，其中r?L、r?M、r?R代表了3個(gè)端點(diǎn)值。應(yīng)用三角模糊數(shù)建立模糊模型后，在求解模型時(shí)需要使用模糊運(yùn)算。

在對(duì)模糊云資源調(diào)度模型的求解中，涉及到了模糊加法、模糊乘法和模糊取大三種運(yùn)算。例如將任務(wù)分配到一個(gè)虛擬機(jī)上執(zhí)行時(shí)，會(huì)累積該虛擬機(jī)的運(yùn)行時(shí)間和成本，此時(shí)需要進(jìn)行模糊加法運(yùn)算，計(jì)算虛擬機(jī)的成本消耗時(shí)，會(huì)進(jìn)行模糊乘法運(yùn)算，而在求解任務(wù)總執(zhí)行時(shí)間，即計(jì)算式（5）時(shí)，需要進(jìn)行模糊取大運(yùn)算。文[14]定義了這三種運(yùn)算。

取任意兩個(gè)三角模糊數(shù)X～、Y～和任意實(shí)數(shù)λ，對(duì)它們執(zhí)行模糊運(yùn)算的結(jié)果為模糊加法：

X～+Y～=（x?L+y?L，x?M+y?M，x?R+y?R）（12）

模糊乘法：

λ?X～?=（λx?L，λx?M，λx?R），λ≥0

（λx?R，λx?M，λx?L），λ<0（13）

模糊取大：

X～∨Y～=（x?L∨y?L，x?M∨y?M，x?R∨y?R）（14）

記Z～=res（P?i），因模糊運(yùn)算具有可分解性，所以Z～的3個(gè)端點(diǎn)Z?L，Z?M，Z?R只和模糊執(zhí)行時(shí)間e～?ij?的3個(gè)端點(diǎn)e～?ij?L，e～?ij?M和e～?ij?R相關(guān)，可按照模型依次求解。則式（9）可轉(zhuǎn)化為

min?{res（P?i）}=?min?{Z～}=?min?{Z?L，Z?M，Z?R}（15）

云計(jì)算資源調(diào)度問題是一個(gè)在眾多調(diào)度方案中選取最優(yōu)方案的決策問題，本文的調(diào)度目標(biāo)是最小化評(píng)價(jià)函數(shù)期望值。不同于確定模型中可以直接對(duì)確定值排序，模糊數(shù)之間的排序較為復(fù)雜。文[15]提出了一種較好的三角模糊數(shù)排序方法，使用式（16）和（17）計(jì)算三角模糊數(shù)的平均值和標(biāo)準(zhǔn)差，若一個(gè)模糊數(shù)具有較高的平均值和較低的標(biāo)準(zhǔn)差，則認(rèn)為該模糊數(shù)排序更高。

p（X～）=14（X?L+2X?M+X?R）（16）

σ?p（X～）=180[3（X?L）?2+4（X?M）?2+3（X?R）?2-4X?LX?M-2X?LX?R-4X?MX?R]12?（17）

根據(jù)以上方法，可將模糊云資源調(diào)度模型轉(zhuǎn)化為時(shí)間-成本約束條件下的單目標(biāo)規(guī)劃模型，調(diào)度的目標(biāo)轉(zhuǎn)化為最小化評(píng)價(jià)函數(shù)的平均值和標(biāo)準(zhǔn)差，式（9）可進(jìn)一步轉(zhuǎn)化為

min?{res（P?i）}=?min?{Z～}=?min?{Z?L，Z?M，Z?R}=?min?{Z?η+Z?μ}，∈[0，1]（18）

其中：Z?η為模糊數(shù)Z～的平均值;Z?μ為標(biāo)準(zhǔn)差;是對(duì)不確定度的加權(quán)系數(shù)。

2算法設(shè)計(jì)與分析

2?1精英策略

在蟻群算法中引入精英策略，可以提高算法的局部搜索能力和收斂速度，使蟻群可以在較少的迭代后找到更優(yōu)的解。但如果精英螞蟻過多，解元素的差異就會(huì)變小，這會(huì)直接影響螞蟻對(duì)路徑的選擇，導(dǎo)致算法停滯。對(duì)此，本文基于排序機(jī)制提出一種改進(jìn)策略：在當(dāng)前循環(huán)結(jié)束后，根據(jù)生成方案的總執(zhí)行時(shí)間，對(duì)所有螞蟻進(jìn)行排序，選取一部分執(zhí)行時(shí)間較短的螞蟻?zhàn)鳛榫⑽浵仯瑢?duì)它們留下的信息素增量進(jìn)行一次更新。引入精英策略后，蟻群的信息素更新公式如下：

τ?ij?（t+1）=（1-ρ）τ?ij?（t）+?Δ?τ?ij?（19）

Δ?τ?ij?=∑mk=1[?Δ?τ?k?ij?·（1-ρ）+?Δ?τ??ij?]，?case?1

∑mk=1?Δ?τ?k?ij?，case2

0，?otherwise?（20）

case?1：k是精英螞蟻且將t?j分配給vm?i

case?2：k不是精英螞蟻且將t?j分配給vm?i

Δ?τ??ij?=Time（P?ave?）-Time（P?k）Time（P?ave?）-Time（P?）·QTime（P?k）（21）

其中：ρ為信息素?fù)]發(fā)系數(shù);τ?ij?（t）表示在t時(shí)刻路徑（vm?i，t?j）上的信息素濃度;?Δ?τ?k?ij?表示第k只螞蟻在本次迭代中留在路徑（vm?i，t?j）上的信息素增量;?Δ?τ??ij?為精英螞蟻的信息素增量;Time（P?ave?）為當(dāng)前循環(huán)中所有螞蟻生成方案的平均執(zhí)行時(shí)間。

2?2自適應(yīng)混沌擾動(dòng)

混沌系統(tǒng)是指在一個(gè)確定性系統(tǒng)中，存在貌似隨機(jī)的不規(guī)則運(yùn)動(dòng)，其行為表現(xiàn)為不確定、不可重復(fù)和不可預(yù)測(cè)，稱此現(xiàn)象為混沌現(xiàn)象?；煦邕\(yùn)動(dòng)具有隨機(jī)性、遍歷性和對(duì)初始條件敏感的特性，利用這些特性，可以優(yōu)化搜索。Lyapunov指數(shù)是用于衡量一個(gè)映射混沌性的重要參照，在某種意義上，它可以看作是映射平均折疊次數(shù)的一種表示。常用的Logistic映射和Tent映射產(chǎn)生的混沌序列雖然具有較好的混沌性，但它們的映射折疊次數(shù)都是有限的。本文采用的是由式（22）定義的無限折疊映射：

x?n+1?=?sin?2x?n，n=0，1，2，…，x?0∈[-1，1]（22）

當(dāng)?shù)踔祒?0不為0時(shí)，系統(tǒng)處于混沌狀態(tài)（實(shí)際上初值也不可以為不動(dòng)點(diǎn)，但上式中的不動(dòng)點(diǎn)皆為超越數(shù)，因此不作考慮）。無限折疊映射的?Lyapunov?指數(shù)表達(dá)式為

λ=?lim??n→∞?1n∑?n-1?i=0?ln?|f?′（x?i）|

=?lim??n→∞?1n∑?n-1?i=0?ln?2x?2?i?cos?2x?i（23）

與Logistic映射和Tent映射相比，折疊次數(shù)為無窮大的無限折疊映射顯然具有更好的混沌性。在混沌搜索過程中，使用無限折疊映射得到的解會(huì)更均勻，以此生成的啟發(fā)式信息質(zhì)量更高，將可以更好的指導(dǎo)蟻群的搜索。

蟻群算法容易陷入局部最優(yōu)解，而精英策略的引入一定程度上放大了這個(gè)缺點(diǎn)，因此引入混沌搜索和混沌擾動(dòng)對(duì)其進(jìn)行優(yōu)化。在算法初始化過程中，使用混沌搜索來達(dá)到全局搜索的目的，然后選擇較優(yōu)路徑生成啟發(fā)性信息，以此初始化蟻群信息素矩陣，指引后續(xù)搜索。當(dāng)蟻群經(jīng)過一定次數(shù)的迭代后，搜索到的最優(yōu)解變化量不大于一個(gè)判定量時(shí)，認(rèn)為算法陷入停滯狀態(tài)，對(duì)當(dāng)前最優(yōu)解路徑上的信息素量進(jìn)行混沌擾動(dòng)。設(shè)判定蟻群停滯的迭代次數(shù)和判定量分別為?γ和δ（δ為一極小常數(shù)），當(dāng)滿足|f?t-f?t+γ?|≤δ（f?t和f?t+γ?為第t次迭代和第t+γ次迭代的最優(yōu)解）時(shí)，蟻群的信息素更新公式調(diào)整為

τ?ij?（t+1）=（1-ρ）τ?ij?（t）+?Δ?τ?ij?+ωc?γ+1?ij?（24）

c?γ+1?ij?=（1-ω）c?γ?ij?+x?ij?（25）

式中：ω為混沌擾動(dòng)系數(shù);c?γ?ij?為蟻群停滯后第γ次迭代的混沌擾動(dòng)量;x?ij?由混沌映射公式迭代得到。蟻群停滯的時(shí)間越長(zhǎng)，混沌擾動(dòng)的強(qiáng)度就越大，如果經(jīng)過長(zhǎng)時(shí)間的擾動(dòng)后，最優(yōu)解依然沒有變化，則認(rèn)為已找到最優(yōu)解，算法結(jié)束。

ECACO算法的流程圖如圖2所示。

3仿真實(shí)驗(yàn)

3?1算法參數(shù)設(shè)置

為驗(yàn)證本文提出的模型和算法，在云仿真平臺(tái)Cloudsim上進(jìn)行仿真實(shí)驗(yàn)。因目前沒有適合云計(jì)算資源調(diào)度問題的標(biāo)準(zhǔn)數(shù)據(jù)集，本文采用文[16]的方法，在區(qū)間[50000，150000]和區(qū)間[500，1500]內(nèi)隨機(jī)生成任務(wù)的大小和虛擬機(jī)處理速度，以此作為仿真實(shí)驗(yàn)的數(shù)據(jù)。在實(shí)驗(yàn)中，要將每一個(gè)確定的執(zhí)行時(shí)間?e?ij?轉(zhuǎn)化為三角模糊數(shù)，其左端點(diǎn)在區(qū)間[ξ?1e?ij?，e?ij?]內(nèi)隨機(jī)生成（0<ξ?1<1），右端點(diǎn)在區(qū)間[e?ij?，ξ?2e?ij?]內(nèi)隨機(jī)生成（ξ?2>1），在以下實(shí)驗(yàn)中令ξ?1=0?9，ξ?2=1?2。?經(jīng)過多次重復(fù)實(shí)驗(yàn)得知，ACO、CACO和ECACO都將在300次迭代中收斂，因此設(shè)置算法最大迭代次數(shù)為300次。對(duì)于ECACO，在蟻群陷入停滯狀態(tài)后，若進(jìn)行50次混沌擾動(dòng)后最優(yōu)解依然不變，則直到算法迭代結(jié)束，當(dāng)前最優(yōu)解都將保持不變。即可將混沌擾動(dòng)50次后依然不變的解視為最終解，因此設(shè)置最大混沌擾動(dòng)次數(shù)為50次。

加權(quán)系數(shù)是用來調(diào)整調(diào)度時(shí)對(duì)模糊評(píng)價(jià)函數(shù)的平均值和不確定度的側(cè)重，越大，調(diào)度對(duì)問題的不確定性越重視。的取值應(yīng)由具體的應(yīng)用環(huán)境來確定，若在網(wǎng)絡(luò)傳輸穩(wěn)定、虛擬機(jī)處理速度較慢這種時(shí)間代價(jià)較高的環(huán)境中，不確定性對(duì)調(diào)度的影響較小，應(yīng)取較小的值。而在不確定性大的環(huán)境中，應(yīng)取較大的值。在本文的對(duì)比實(shí)驗(yàn)中，的取值為0?5，虛擬機(jī)的數(shù)量為8個(gè)，算法的主要參數(shù)設(shè)置如表1所示。

3?2確定模型與模糊模型對(duì)比

為了對(duì)任務(wù)執(zhí)行時(shí)間確定和不確定兩種情況下的模型進(jìn)行比較，在不同任務(wù)規(guī)模下，使用ECACO算法對(duì)兩種模型進(jìn)行求解。在模型側(cè)重方向的選擇中，令評(píng)價(jià)函數(shù)中時(shí)間的權(quán)重和成本的權(quán)重相同，以便同時(shí)比較時(shí)間和成本的變化，因此設(shè)置時(shí)間因子?t?=0?5，成本因子?c?=0?5。確定云資源調(diào)度模型和模糊云資源調(diào)度模型之間的對(duì)比結(jié)果如圖3所示?？梢钥闯?，不確定因素的存在提高了評(píng)價(jià)函數(shù)的值，這意味著任務(wù)的執(zhí)行時(shí)間和所需成本會(huì)增加，因此必須在調(diào)度時(shí)考慮不確定性因素的影響，否則會(huì)導(dǎo)致理論與實(shí)際的偏差過大而降低系統(tǒng)的效率。

3?3算法性能對(duì)比

在相同參數(shù)下，對(duì)ACO、CACO和ECACO進(jìn)行實(shí)驗(yàn)，圖4、5、6分別為在任務(wù)數(shù)量為100的情況下，當(dāng)?t=0?5，c=0?5時(shí)，t=1，c=0時(shí)，以及t=0，c=1?時(shí)算法的迭代過程。可以看出，不管時(shí)間因子和成本因子如何取值，當(dāng)使用ECACO求解模型時(shí)，得到的調(diào)度方案都能夠在時(shí)間和成本的最小化上獲得更好的結(jié)果。圖7是任務(wù)數(shù)量為400，?t=0?5，c=0?5?時(shí)算法的迭代過程，可以看出，在大規(guī)模的任務(wù)調(diào)度上，ECACO依然表現(xiàn)出了良好的性能。觀察3種算法的迭代曲線，可知當(dāng)蟻群陷入停滯狀態(tài)后，ECACO的擾動(dòng)機(jī)制可以使蟻群更快的跳出局部極值區(qū)間，找到更優(yōu)解。相比較于CACO，本文提出的ECACO具有更快的收斂速度和更好的全局搜索能力。除此之外，ECACO能夠判斷出蟻群是否獲得穩(wěn)定最優(yōu)解，并且在獲得穩(wěn)定解后提前停止迭代，因此在一定程度上減少了算法迭代的時(shí)間，提高了系統(tǒng)的整體效率。

當(dāng)?t=0?5，c=0?5?時(shí)，使用3種算法對(duì)不同任務(wù)規(guī)模下的模型進(jìn)行多次求解，對(duì)得到的解取平均值，結(jié)果如表2所示，相對(duì)差值列為CACO的評(píng)價(jià)函數(shù)值大于ECACO評(píng)價(jià)函數(shù)值的相對(duì)平均值。表2表明，無論是小規(guī)模的資源調(diào)度還是大規(guī)模的資源調(diào)度，使用ECACO都能夠獲得更好的解。圖8為?t=0?5，c=0?5?時(shí)，不同任務(wù)規(guī)模下3種算法的負(fù)載均衡程度對(duì)比?？梢钥闯?，ECACO的負(fù)載均衡程度明顯高于ACO和CACO，這證明ECACO對(duì)于資源的利用率更高，可以有效避免虛擬機(jī)上的工作負(fù)載過重。

通過以上實(shí)驗(yàn)可知，本文提出的ECACO收斂速度快、最優(yōu)解搜索能力強(qiáng)，使用ECACO對(duì)模糊云資源調(diào)度模型進(jìn)行求解，可以實(shí)現(xiàn)任務(wù)完成時(shí)間更短、成本消耗更低并且虛擬機(jī)負(fù)載更加均衡的目標(biāo)，從而提高云計(jì)算系統(tǒng)的綜合效率。

4結(jié)論

本文使用模糊變量表示不確定的任務(wù)執(zhí)行時(shí)間，建立了云計(jì)算資源調(diào)度問題的模糊規(guī)劃模型，并提出一種改進(jìn)算法進(jìn)行求解。ECACO引入了精英策略增強(qiáng)蟻群的局部搜索能力，然后通過無限折疊映射生成啟發(fā)式信息和混沌擾動(dòng)量，并優(yōu)化了混沌擾動(dòng)機(jī)制，讓蟻群在停滯后能更快的跳出局部極值區(qū)間。實(shí)驗(yàn)證明ECACO具有更好的性能，能夠進(jìn)一步提高云計(jì)算系統(tǒng)的效率。不確定因素的存在會(huì)使任務(wù)的執(zhí)行時(shí)間和成本增加，因此在調(diào)度時(shí)必須考慮。相對(duì)于以往研究，本文提出的模型將不確定因素納入了研究范圍，更符合實(shí)際環(huán)境中的應(yīng)用。

參 考 文 獻(xiàn)：

[1]JULA A， SUNDARARAJAN E， OTHMAN Z. Cloud Computing Service Composition： A Systematic Literature Review[J]. Expert Systems with Applications， 2014， 41（8）： 3809.

[2]RIMAL B P， JUKAN A， KATSAROS D， et al. Architectural Requirements for Cloud Computing Systems： An Enterprise Cloud Approach[J]. Journal of Grid Computing， 2011， 9（1）： 3.

[3]ABDULLAHI M， NGADI M A， ABDULHAMID S M. Symbiotic Organism Search Optimization Based Task Scheduling in Cloud Computing Environment[J]. Future Generation Computer Systems?The International Journal of Escience， 2016， 56： 640.

[4]YAO G S， DING Y S， JIN Y C， et al. Endocrine?based Coevolutionary Multi?swarm for Multi?objective Workflow Scheduling in a Cloud System[J]. Soft Computing， 2017， 21（15）： 4309.

[5]KAMALINIA A， GHAFFARI A. Hybrid Task Scheduling Method for Cloud Computing by Genetic and DE Algorithms[J]. Wireless Personal Communications， 2017， 97（4）： 6301.

[6]KIM J， KIM T， PARK M， et al. Fuzzy?Based Resource Reallocation Scheduling Model in Cloud Computing[J]. Lecture Notes in Electrical Engineering， 2014， 301： 43.

[7]SHOJAFAR M， JAVANMARDI S， ABOLFAZLI S. FUGE： A Joint Meta?heuristic Approach to Cloud Job Scheduling Algorithm Using Fuzzy Theory and a Genetic Method[J]. Cluster Computing?The Journal of Networks Software Tools and Applications， 2015， 18（2）： 829.

[8]HASSAN M A， KACEM I， MARTIN S， et al. Genetic Algorithms for Job Scheduling in Cloud Computing[J]. Studies in Informatics & Control， 2015， 24（4）： 387.

[9]SADHASIVAM N， THANGARAJ P. Design of an Improved PSO Algorithm for Workflow Scheduling in Cloud Computing Environment[J]. Intelligent Automation & Soft Computing， 2016，31（8）： 493.

[10]HU X X， ZHOU X W. Improved Ant Colony Algorithm on Scheduling Optimization of Cloud Computing Resources[J]. Applied Mechanics & Materials， 2014， 678： 75.

[11]ZHONG Z F， CHEN K， ZHAI X J， et al. Virtual Machine?Based Task Scheduling Algorithm in a Cloud Computing Environment[J]. Tsinghua Science and Technology， 2016， 21（6）： 660.

[12]MA Y， WANG Y. Grid Task Scheduling Based on Chaotic Ant Colony Optimization Algorithm[C]// International Conference on Computer Science and Network Technology. IEEE， 2013： 469.

[13]YOUSEFIKHOSHBAKHT M， DIDEHVAR F， RAHMATI F. An Efficient Solution for the VRP by Using a Hybrid Elite Ant System[J]. International Journal of Computers Communications & Control， 2014， 9（3）： 340.

[14]BENTRCIA T， MOUSS L H， MOUSS N K， et al. Evaluation of Optimality in the Fuzzy Single Machine Scheduling Problem Including Discounted Costs[J]. International Journal of Advanced Manufacturing Technology， 2015， 80（5-8）： 1369.

[15]BALIN S. Non?identical Parallel Machine Scheduling with Fuzzy Processing Times Using Genetic Algorithm and Simulation[J]. International Journal of Advanced Manufacturing Technology， 2012， 61（9-12）：?1115.

[16]CALHEIROS R N， RANJAN R， BELOGLAZOV A， et al. CloudSim： A Toolkit for Modeling and Simulation of Cloud Computing Environments and Evaluation of Resource Provisioning Algorithms[J]. Software Practice & Experience， 2010， 41（1）： 23.

[17]PRIYA V， BABU C N K. Moving Average Fuzzy Resource Scheduling for Virtualized Cloud Data Services[J]. Computer Standards & Interfaces， 2016， 50： 251.

[18]羅智勇，朱梓豪，尤波，等.基于串歸約的時(shí)間約束下工作流精確率優(yōu)化算法[J].哈爾濱理工大學(xué)學(xué)報(bào)，2018，23（5）：68.

[19]LU D， MA J， SUN C， et al. Credit?based Scheme for Security?aware and Fairness?aware Resource Allocation in Cloud Computing[J]. Science China?Information Sciences， 2017， 60（5）： 052103.

[20]趙輝，呂青，丁樹業(yè).模糊綜合評(píng)判在優(yōu)化電機(jī)冷卻系統(tǒng)中的應(yīng)用[J].哈爾濱理工大學(xué)學(xué)報(bào)，2016，21（6）：106.

[21]ZHANG Y， SUN J. Novel Efficient Particle Swarm Optimization Algorithms for Solving QoS?demanded Bag?of?tasks Scheduling Problems with Profit Maximization on Hybrid Clouds[J]. Concurrency and Computation?Practice & Experience， 2017， 29（21）： 4249.