基于IPSO_CS的云資源調度算法仿真研究

李新飛, 謝曉蘭,b

(桂林理工大學 a.信息科學與工程學院; b.廣西嵌入式技術與智能系統重點實驗室， 廣西 桂林 541006)

0 引 言

云計算是大規模分布式計算和并行處理的一個新的視角，它以按使用付費的方式提供服務[1]，是一種從任務集中的云計算模式[2]發展，可以提供大規模分布式資源并進行協同計算的超級計算服務。網絡“云”將分解后的小塊計算機程序數據使用在多部服務器組上，在處理和分析后服務于用戶，而任務調度的效率成了云計算中最迫切需要解決的問題。

隨著應用程序計算需求以及用戶需求的快速增長，計算資源不斷增多，任務調度作為組合優化問題在考慮如何及時、高效地進行任務分配以及合理利用資源、提高資源利用率方面起著十分關鍵的作用。任務調度就是綜合考慮任務完成時間、負載均衡和服務質量等因素，將用戶任務匹配給合適的虛擬計算資源，所選用的任務調度優化算法直接影響著任務分配的效率，算法的優劣程度影響著減少總任務執行時間。智能優化算法在解決任務調度問題方面非常有效，可以顯著降低搜索復雜度，增大搜索空間，在模擬自然過程中解決全局最優解問題。粒子群算法以及其各種優化算法作為智能優化算法的典型，雖然應用領域紛雜、起源很久但由于其簡單容易實現且沒有許多參數而被廣泛使用。

在考慮到粒子群及其優化算法的優勢和云計算環境下巨大的資源數量，以及種群初始化和萊維飛行搜索的隨機性造成不穩定性而產生的結果隨機性，對任務的執行時間進行算法穩定性分析判斷，從執行時間和成本出發提出了一種改進的粒子群布谷鳥算法(Improved particle swarm cuckoo algorithm，IPSO_CS)，采用非線性自適應慣性權重代替提高種群多樣性；引入布谷鳥搜索(cuckoo search)中模擬捕食者狩獵的萊維飛行機制增加粒子位置變化的活力，調整搜索范圍的步長因子，增大靠近精英解的概率，以及tent混沌擾動打破局部最優的狀態。仿真結果表明，其可以很好的解決算法的早熟收斂、搜索效率低、結果隨機等問題，相較與其他 PSO 具有更優的性能。

1 研究背景

云計算環境下的任務調度作為數學七大難題之一的NP完全問題[3]，最優解的獲取適合如灰狼算法、粒子群算法、禁忌搜索[4]、煙花算法等相關智能改進算法來逼近最優解。文獻[5]中在編碼方式采用間接編碼進行改進，優化相關參數設置且在任務調度的效率方面有所進步。文獻[6]中為加快搜索速度以及減少云計算任務執行時間引入局部及全局信息深度更新的方法來改進蟻群算法。文獻[7]中的雙適應度遺傳算法 (Double fitness genetic algorithm，DFGA) 考慮任務完成時間和任務平均完成時間雙適應度。文獻[8]中提出一種優化的多目標粒子群算法(Optimize multi-objective task scheduling particle swarm algorithm，MOTS-PSO) ，分別給予任務總執行時間、總傳輸時間和單節點執行代價不同的權重建立多目標優化模型，解決傳統粒子群算法收斂速度慢和精度低等問題，實驗證明算法效果更優。文獻[9]中在多目標方面提出一種遺傳與粒子群算法融合多目標任務調度算法，將粒子群和遺傳算法的優勢結合起來，針對調度策略不能滿足用戶需求的問題進行多目標優化。文獻[10]中在tent映射的自適應混沌粒子群的任務調度問題研究中引入混沌優化策略，以其混沌運動的隨機遍歷優勢解決粒子群(PSO)算法迭代后期易陷入局部最優的缺陷。文獻[11]中將蟻群算法優勢、多維服務質量約束、遺傳算法優勢相結合提出了一種云計算多QoS約束云計算任務調度算法(Multi-QoS with genetic and ant colony optimization algorithm，MQoS-GAAC)，將用戶的服務質量作為適應度函數，采用動態融合策略確定蟻群算法和遺傳算法的最佳融合時間，不僅提高了用戶服務質量，而且保持了資源負載均衡。文獻[12]中研究證明粒子群算法與遺傳算法相比在云計算環境中調度效果更好。以上工作考慮到的目標單一、早熟收斂或多目標優化等問題，可以看出PSO 更適合云計算中的資源調度。本文在考慮到以上工作各方的優勢后提出一種結合粒子群算法和布谷鳥搜索的(IPSO_CS)改進粒子群算法進行任務調度，經仿真結果證明比其他PSO算法調度效果更優。

2 云資源調度問題

云任務調度采用映射/規約模式將任務分配到資源節點上，達到任務完成總時間短、服務質量好等需求。云任務被分解為若干個相互獨立的子任務[13]后，各子任務隨機分配給并行的資源計算節點上執行、整合、輸出，適合于大規模數據的處理，工作效率高。

調度模型及適應度函數

作為云計算環境下的任務集合T={t1，t2，…，tm}，表示在當前時刻共有m個執行過程中不可阻斷的相互獨立任務。VM虛擬機資源集合VM={vmm1，vmm2，…，vmmn} ，n為虛擬機資源數量。在資源節點上預期完成時間的完成情況：

(1)

式中,etcij為相應虛擬機處理速度下任務長度的完成時間。本文云計算任務調度目標旨在盡可能使任務完成時間time最短，任務分配到虛擬機上的總完成時間模型

(2)

任務在虛擬機上占用各種資源的執行成本模型如下：

(3)

式中：Time(i,j)為虛擬機i上任務j的執行時間;k為任務個數;Ci為單位時間虛擬資源的費用。這里的費用包括3個方面：帶寬、內存、CPU，單位為MB。

本模型為使任務完成時間Time和執行成本C最小，采用線性加權計算的適應度函數，分配不同指標不同權重：

Fitness=f1Time+f2C,f1+f2=1

(4)

Fitness作為本文優化目標也作為適應度函數，其值越小，算法性能越好，在實際應用中，任務調度作為實際問題，還需要考慮負載均衡、能耗等因素。

由于種群初始化和萊維飛行搜索的隨機性會造成結果的不穩定性，對任務的執行時間進行算法穩定性的分析判斷。方差D(n)作為樣本偏離程度即數據波動程度可以判斷結果的穩定性：

(5)

從執行時間、執行成本、穩定性進行多方面分析作為本文任務調度模型的判別標準。

3 IPSO_CS算法

3.1 基本粒子群算法

標準粒子群算法[14]是在動物集群活動行為的基礎上，通過最佳個體體驗(pbest)和群體中最佳群體體驗(gbest)在問題求解空間中進行演化，使得種群逐步趨于最優。基本粒子群算法由于其簡單，易實現等優點被廣泛應用。在n維搜索空間算法模仿m個粒子的群體以基于自己和其他粒子最優位置的基礎上進行搜索飛行和位置更新，Xi=(xi1，xi2，…，xin)為第i個粒子的位置，速度Vi=(vi1，vi2，…，vin)。制定相應適應度函數后計算群體內各粒子的適應度值，以最佳個體體驗(pbest)和群體中最佳群體體驗(gbest)對群體內每顆粒子的速度和位置進行更新:

vi,j(t+1)=Wvi,j(t)+c1rand1[pi,j(t)-xi,j(t)]+

c2rand2[pg,j(t)-xi,j(t)]

(6)

xi,j(t+1)=xi,j(t)+vi,j(t+1),

(7)

j=1,2,…,n

式中：W為慣性權重，用于提高算法的收斂性;c1、c2為加速度常數控制個體和全局最佳粒子效果的特定參數；rand1、rand2為隨機數函數，用于在粒子運動時提供在[0，1]范圍內的隨機量[15]，以控制粒子在搜索空間中的運動。

3.2 粒子編碼

在云環境中應用粒子群算法時，待分配子任務作為離散值需要對粒子進行編碼，通過編碼結合任務調度與粒子位置和速度，對粒子個體采用自然數編碼。設有m個任務，分配給n臺虛擬機，粒子種群規模為NP，每個粒子的位置由向量Z表示，則第i個粒子可編碼為m維向量Zi=[zi1，zi2，…，zim]，zij的取值在0～n+1之間的隨機整數，每一維分量表示分配給此任務的虛擬機，比如最優解若為(2,5,3,…)，則表示虛擬機2接受任務1，虛擬機5接受任務2，虛擬機3接受任務3等。粒子速度則由向量v表示，第i個粒子的速度表示為vi=[vi1，vi2，…，vim]，vij為-n到n之間的隨機數。

3.3 算法改進策略

(1) 非線性自適應慣性權重。粒子群算法的慣性權重W作為重要的進化參數是由Shi等提出，也叫慣性因子，決定了先前狀態粒子對當前狀態的影響。通常采用的典型線性遞減[16]策略。在迭代前期由于需要較大的全局搜索能力，需要賦予較大的慣性因子，用以豐富種群多樣性和搜索的隨機性，而后期需要較小的慣性因子聚焦局部搜索能力。在平衡優化粒子搜索能力時，本文采用隨迭代次數自適應的非線性慣性權重策略，對比實驗結果表明，改進后的自適應非線性慣性權重效果更好，且隨著算法不斷迭代，慣性權重值動態改變：

(8)

式中：W為慣性因子,其最大最小值分別為0.9、0.4；d作為迭代次數，最大值為dmax。改進后的自適應慣性權重從最大的慣性因子隨迭代次數自適應降到最小慣性因子，不僅解決了后期收斂速度慢的問題，前期更是擴大了搜索的隨機性。

(2) 布谷鳥搜索。Yang等提出的布谷鳥搜索算法是一種受布谷鳥繁殖行為和levy飛行策略啟發的元啟發式全局優化方法，是一種模擬自然界布谷鳥提高生存機率的繁育行為和萊維飛行特性形成的有效搜索策略。萊維飛行機制是通過隨機游動和偏好隨機游動的短步長與長步長相間行走用以達到平衡整體和局部尋優有效性的方式，在平衡尋優方面，Long等在萊維飛行中加入了動態自適應步長因子[17]。改進后算法全局搜索位置和路徑的更新

(9)

式中：Xt，Xt+1為t時刻和下一時刻粒子i位置；“⊕”為點對點乘法；ɑ為改進步長因子。改進的隨粒子變化自適應調整搜索范圍的步長因子，引導粒子靠近種群最優解即精英解：

(10)

服從λ的萊維分布的隨機搜索路徑：

Levy～u=t-λ

(11)

Mantegna算法模擬隨機步長十分復雜且難實現的萊維飛行，其數學表達如下：

(12)

式中：s為步長;u、v為服從正態分布的兩個隨機數;β通常取1.5。

(13)

Г(x)定義如下：

(14)

服從萊維飛行的粒子運動軌跡模仿動物的捕獵行為，這種行為為其隨機廣泛的搜索能力奠定了基礎。

(3) tent混沌改進。為避免早熟收斂且高效優化此改進算法，引入tent混沌擾動，這種自然界看似很普遍的非線性混沌現象，以其隨機性特點不重復遍歷所有狀態達到解決收斂速度慢、尋優精度差等問題，在保證多樣的種群的條件下，增強了其跳出局部最優的情況，平衡了全局和局部的搜索能力。單梁等[18]研究表明，Tent 映射的遍歷均勻性和收斂速度均優于 Logistic 映射，引入tent混沌擾動粒子，當粒子全局最優收斂到某個值持續不變超過設置的監測值limit時，對粒子的速度進行擾動，改變其搜索方向和距離，引入混沌跳出局部最優解[19]，避免陷入早熟的僵局。本文采用以下tent混沌公式：

(15)

將產生的混沌擾動量載入到粒子速度的更新中。

(16)

式中：Vi+1為擾動后的新的個體速度;rand為服從正態分布的隨機數；Si+1為產生的混沌擾動量；S為隨機產生的(0,1)內的初值。設定粒子最大飛行速度Vmax代替超出上限的速度值。利用混沌函數將產生的新的擾動變量附加到迭代到監測值limit時的粒子速度上，改變粒子的運動方向，得到新的擾動后的粒子狀態。

(4) IPSO_CS算法描述。IPSO_CS算法步驟如下

步驟1初始化種群大小及各項參數等。

步驟2依據改進式(8)改進迭代的自適應權重參數w。

步驟3計算可行粒子執行時間適應度值，確定最佳個體體驗pbest和群體最佳群體體驗gbest。

步驟4將當前適應度值進行比較更新pbest、gbest。

步驟5粒子迭代過程開始，依據式(7)、(9)進化粒子群位置。

步驟6全局最優收斂值迭代次數超過監測值limit，依據式(16)改進粒子速度。

步驟7判斷是否滿足終止條件，否則轉步驟3。

4 仿真實驗分析

4.1 仿真實驗過程

本文采用云仿真軟件cloudsim工具包對該調度策略進行仿真，任務數設置為[50，100，200]，迭代次數[200，500]，將改進后的(IPSO_CS)算法與(PSO)算法、(SAPSO)算法仿真比較。表1、2分別為本文硬件實驗環境配置參數和調度算法參數配置。

表1 硬件實驗環境配置

表2 調度算法參數配置

4.2 仿真結果及分析

將3個算法從任務調度策略和最終結果進行仿真對比分析。

(1) 任務調度策略分析。為確保數據的可靠性，對每組任務進行仿真后取平均值得到最終的結果。不同任務數下任務完成時間隨迭代次數的變化如圖1(a)～(c)所示。

由仿真結果可見，IPSO_CS在3種不同的任務數量下收斂能力和調度尋優能力都比PSO和SAPSO更好。SAPSO算法完成任務總時間比IPSO_CS和PSO相差較多，圖1(a)所示在任務數量較少迭代次數200內，SAPSO沒有趨于穩定，算法收斂和尋優效果差，PSO和IPSO_CS總體的任務完成時間非常貼近，迭代初期100次左右IPSO_CS趨于平緩，PSO在迭代140時趨于平緩。在結合了CS搜索后粒子位置活力更活躍，加快了尋優的能力。圖1(b)為改進算法在后期較好的尋優能力，在迭代次數250之前與PSO算法接近，但SAPSO算法效果整體較差。圖1(c)展示了在較大規模下，3種算法的收斂和尋優能力，在迭代300次左右，3種算法都趨于平穩，在粒子搜索增加CS的動物捕獵行為的模仿后IPSO_CS除了在較早的迭代初期調度效果不佳之外，總體優勢在迭代50次后體現出來。

(a) 任務數50完成時間

不同任務數量下任務完成成本對比如圖2所示。

執行成本的相差不是太大，尤其是IPSO_CS與PSO，但是IPSO_CS在總的費用上要優于PSO和SAPSO，也就可以看出其分配方案更合理，效果更好。

(2)仿真結果穩定性分析。除任務完成時間和費用對比，對50個任務和200個任務的完成時間選取8組值繪出圖3、4所示的穩定性對比[20]，觀察得出IPSO_CS曲線波動較小且總體值小于PSO和SAPSO，說明種群初始化和萊維飛行搜索的隨機性對IPSO_CS的影響較小，本文方案在執行時間上相對穩定。

圖3 任務數50執行時間穩定性對比

圖4 任務數200執行時間穩定性對比

綜上，通過不同規模條件下的仿真，本文的優化IPSO_CS調度算法相比于PSO和SAPSO縮短了系統任務調度完成總時間和費用，在算法收斂、搜索能力、穩定性、調度效果方面都取得了較好效果，總體上保證了樣本多樣性，在資源調度方面尋優更好。

5 結 語

傳統PSO在進行云資源調度時容易出現早熟收斂、搜索效率低、結果隨機等問題。本文提出的一種基于標準粒子群算法改進的資源調度算法(IPSO_CS)，在增加粒子位置變化活力搜索精英解以及打破局部最優的狀態，縮短任務執行時間和成本上，比標準 PSO 算法和SAPSO算法更好，調度策略上更優。仿真結果表明，其可以很好地解決算法的早熟收斂、搜索效率低、結果隨機等問題，相較與其他 PSO 具有更優的性能。本文所提出的調度策略能夠較好的解決云計算中資源調度分配問題。