不確定執行時間的云計算資源調度

李成嚴　曹克翰　馮世祥　孫巍

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

關鍵詞：

云計算;資源調度;模糊規劃;混沌擾動

DOI：10.15938/j.jhust.2019.01.014

中圖分類號： TP399

文獻標志碼： A

文章編號： 1007-2683（2019）01-0085-07

Resource Scheduling with Uncertain Execution?Time in Cloud Computing

LI Cheng?yan，CAO Ke?han，FENG 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引言

云計算系統應用虛擬化技術，以較低的成本提供高質量的資源服務，用戶根據自身需求選擇并付費使用相應的服務[1]。云計算資源調度的研究目標是合理的將多個任務分配到虛擬資源節點上執行，并滿足執行時間短、所需成本低、虛擬資源集群負載均衡等條件，文[2]證明了該調度問題是一個NP完全問題。

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

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

本文使用模糊規劃的方法，在云計算資源調度問題中引入不確定的任務執行時間，建立模糊云資源調度問題的期望值模型，并提出一種改進算法對模型進行求解。本文結構如下，第1部分建立了模糊云資源調度問題的期望值模型，并對模型的求解進行了分析，第2部分介紹了算法的設計過程，第3部分通過仿真實驗對模型和算法進行驗證，最后作出結論。

1模糊云資源調度問題

1?1模糊云資源調度模型

云計算中資源調度問題可以描述為將任務集合?T={t?1，t?2，…，t?n}中的n個任務，分配到虛擬機集合VM={vm?1，vm?2，…，vm?m}中的m個虛擬機上執行（m

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

ETC=?11?12?…?1n

21?22?…?2n

m1?m2?…?mn?（2）

其中，rcu?i為vm?i單位時間內執行任務消耗的資源成本。在一個完整的資源調度方案P中，虛擬機vm?i執行任務所需時間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上執行的任務集合。執行調度方案P?i需要的總時間為

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

執行任務的總成本為

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

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

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

成本約束函數為

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

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

在時間-成本選擇約束條件下的云計算資源調度模型為

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

其中，評價函數

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

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

定義虛擬資源的負載均衡函數為

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

式中，?min?1≤i≤m?vmTime?i表示調度方案中虛擬機的最短執行時間，?max?1≤i≤m?vmTime?i為虛擬機最長執行時間，即調度方案總執行時間。由式（11）可知

1）若?max?1≤i≤m?vmTime?i=0，則任務還未被執行;

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

3）若Load=1，則各虛擬機的執行時間相同，此時系統的負載均衡性達到最佳，Load的值越接近1，證明系統對資源的利用越充分。

1?2模型轉換

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

在對模糊云資源調度模型的求解中，涉及到了模糊加法、模糊乘法和模糊取大三種運算。例如將任務分配到一個虛擬機上執行時，會累積該虛擬機的運行時間和成本，此時需要進行模糊加法運算，計算虛擬機的成本消耗時，會進行模糊乘法運算，而在求解任務總執行時間，即計算式（5）時，需要進行模糊取大運算。文[14]定義了這三種運算。

取任意兩個三角模糊數X～、Y～和任意實數λ，對它們執行模糊運算的結果為模糊加法：

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），因模糊運算具有可分解性，所以Z～的3個端點Z?L，Z?M，Z?R只和模糊執行時間e～?ij?的3個端點e～?ij?L，e～?ij?M和e～?ij?R相關，可按照模型依次求解。則式（9）可轉化為

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

云計算資源調度問題是一個在眾多調度方案中選取最優方案的決策問題，本文的調度目標是最小化評價函數期望值。不同于確定模型中可以直接對確定值排序，模糊數之間的排序較為復雜。文[15]提出了一種較好的三角模糊數排序方法，使用式（16）和（17）計算三角模糊數的平均值和標準差，若一個模糊數具有較高的平均值和較低的標準差，則認為該模糊數排序更高。

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）

根據以上方法，可將模糊云資源調度模型轉化為時間-成本約束條件下的單目標規劃模型，調度的目標轉化為最小化評價函數的平均值和標準差，式（9）可進一步轉化為

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

其中：Z?η為模糊數Z～的平均值;Z?μ為標準差;是對不確定度的加權系數。

2算法設計與分析

2?1精英策略

在蟻群算法中引入精英策略，可以提高算法的局部搜索能力和收斂速度，使蟻群可以在較少的迭代后找到更優的解。但如果精英螞蟻過多，解元素的差異就會變小，這會直接影響螞蟻對路徑的選擇，導致算法停滯。對此，本文基于排序機制提出一種改進策略：在當前循環結束后，根據生成方案的總執行時間，對所有螞蟻進行排序，選取一部分執行時間較短的螞蟻作為精英螞蟻，對它們留下的信息素增量進行一次更新。引入精英策略后，蟻群的信息素更新公式如下：

τ?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）

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

2?2自適應混沌擾動

混沌系統是指在一個確定性系統中，存在貌似隨機的不規則運動，其行為表現為不確定、不可重復和不可預測，稱此現象為混沌現象。混沌運動具有隨機性、遍歷性和對初始條件敏感的特性，利用這些特性，可以優化搜索。Lyapunov指數是用于衡量一個映射混沌性的重要參照，在某種意義上，它可以看作是映射平均折疊次數的一種表示。常用的Logistic映射和Tent映射產生的混沌序列雖然具有較好的混沌性，但它們的映射折疊次數都是有限的。本文采用的是由式（22）定義的無限折疊映射：

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

當迭代初值x?0不為0時，系統處于混沌狀態（實際上初值也不可以為不動點，但上式中的不動點皆為超越數，因此不作考慮）。無限折疊映射的?Lyapunov?指數表達式為

λ=?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映射相比，折疊次數為無窮大的無限折疊映射顯然具有更好的混沌性。在混沌搜索過程中，使用無限折疊映射得到的解會更均勻，以此生成的啟發式信息質量更高，將可以更好的指導蟻群的搜索。

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

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

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

式中：ω為混沌擾動系數;c?γ?ij?為蟻群停滯后第γ次迭代的混沌擾動量;x?ij?由混沌映射公式迭代得到。蟻群停滯的時間越長，混沌擾動的強度就越大，如果經過長時間的擾動后，最優解依然沒有變化，則認為已找到最優解，算法結束。

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

3仿真實驗

3?1算法參數設置

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

加權系數是用來調整調度時對模糊評價函數的平均值和不確定度的側重，越大，調度對問題的不確定性越重視。的取值應由具體的應用環境來確定，若在網絡傳輸穩定、虛擬機處理速度較慢這種時間代價較高的環境中，不確定性對調度的影響較小，應取較小的值。而在不確定性大的環境中，應取較大的值。在本文的對比實驗中，的取值為0?5，虛擬機的數量為8個，算法的主要參數設置如表1所示。

3?2確定模型與模糊模型對比

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

3?3算法性能對比

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

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

通過以上實驗可知，本文提出的ECACO收斂速度快、最優解搜索能力強，使用ECACO對模糊云資源調度模型進行求解，可以實現任務完成時間更短、成本消耗更低并且虛擬機負載更加均衡的目標，從而提高云計算系統的綜合效率。

4結論

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

參 考 文 獻：

[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]羅智勇，朱梓豪，尤波，等.基于串歸約的時間約束下工作流精確率優化算法[J].哈爾濱理工大學學報，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]趙輝，呂青，丁樹業.模糊綜合評判在優化電機冷卻系統中的應用[J].哈爾濱理工大學學報，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.