基于改進PSO的云計算資源調(diào)度路徑優(yōu)化研究

李 萌 ，劉 鑫

(1.陜西科技大學鎬京學院，陜西 西安 712046;2.中南大學商學院，湖南 長沙 410083)

1 引言

為了實現(xiàn)大規(guī)模數(shù)據(jù)的存儲管理，云計算作為新型計算框架被廣泛應用于各類互聯(lián)網(wǎng)業(yè)務場景中。它能夠根據(jù)使用者的意圖及時可靠的提供按需分配的服務與資源[1]。隨著使用者與業(yè)務的增加，云計算框架需要管理大量的軟硬件資源。目前主要通過虛擬化技術，結合調(diào)度策略調(diào)整任務與資源的對應分配[2]。但是由于系統(tǒng)的動態(tài)特性顯著，影響調(diào)度性能的因素具有非線性，設計一種高效可靠的資源調(diào)度路徑優(yōu)化算法成為該領域的難點[3]。如今很多學者致力于云計算資源調(diào)度的研究，也提出了一些較好的調(diào)度算法。

文獻[4]設計了AC-SFL調(diào)度算法，采用回饋系數(shù)改善蟻群的收斂性能，同時優(yōu)化蛙跳改善最優(yōu)解搜索性能。該算法具有較好的網(wǎng)絡吞吐量和成本利用率，但是過于關注算法的收斂和尋優(yōu)效果，沒有過多考慮資源調(diào)度模型本身的優(yōu)化。文獻[5]設計了BA-LBRSA調(diào)度算法，在負載模型的基礎上采用蟻群進行任務分配。該算法具有較好的負載利用率，但是模型構造過程中沒有充分考慮效率問題。文獻[6]設計了一種ACO優(yōu)化算法，調(diào)度效率較好，但是在負載率和大規(guī)模任務處理方面還存在欠缺。文獻[7]設計了ACO-GA調(diào)度算法，通過混合算法增強最優(yōu)策略的搜索。文獻[8]設計了IACO調(diào)度算法，分析了基于最大完成時間的調(diào)度模型，并考慮了收斂過程中的負載均衡性。這些算法在某些性能方面取得了不錯的效果，但是整體的動態(tài)適應性有待提高。

本文首先構造資源調(diào)度模型，并分析影響調(diào)度模型的目標約束，具體包括任務時間、成本和負載率，從而確保調(diào)度模型求解的綜合性能。然后將改進PSO算法引入調(diào)度模型計算，并針對PSO的初始化和參數(shù)更新等操作進行優(yōu)化設計。最后通過CloudSim平臺對調(diào)度算法的任務延時、任務成本，以及資源負載率進行仿真實驗，驗證了本文所提算法的有效性。

2 資源調(diào)度模型

云計算需要處理大量動態(tài)任務，且很多任務必須滿足時效性。為符合應用需求，調(diào)度管理中心應該提高資源調(diào)度的規(guī)模和使用率，這需要依賴資源調(diào)度模型來實現(xiàn)。假定系統(tǒng)中部署的虛擬機數(shù)量是n，則對應集合可以描述為V={v1，v2，…，vn}。系統(tǒng)中到達的任務經(jīng)過劃分后形成的子任務數(shù)量是m，對應集合可以描述為R={r1，r2，…，rm}。處理任務時調(diào)度中心會把所有的子任務分配到當前可用的虛擬機。由于虛擬機在任意時刻僅可以處理一個任務，所以可以將虛擬機與任務存在的關系描述成如下矩陣

(1)

元素gij描述的是任務ri和虛擬機vj的映射。任務映射分配的有效性決定了資源調(diào)度的合理性，因此在映射過程中，應該最大限度保證任務處理的時間、成本，以及網(wǎng)絡均衡性。

3 目標約束分析

3.1 任務時間約束

假定任務ri分配給虛擬機vj處理，則ri的完成時間可以描述如下

(2)

(3)

(4)

其中，k表示分配給vj的任務數(shù)量。根據(jù)Wj、Cj、Mj、Fj參量得到虛擬機的任務處理性能，將最高和最低的分別標記為max(vj)和min(vj)。將任務最優(yōu)和最差的處理時間描述如下

(5)

(6)

于是，可以將時間約束定義如下

Tc=(ttotal-Tmin)/(Tmax-Tmin)

(7)

系統(tǒng)任務完成的越快，Tc結果越小，意味資源調(diào)度對時間越有利。

3.2 任務成本約束

雖然有效的資源調(diào)度會降低任務時間，但是，單獨的時間最優(yōu)不代表資源調(diào)度整體性能的合理，于是，這里進一步考慮任務成本問題。設定vj執(zhí)行任務時單位時間所需成本是costj。則系統(tǒng)任務全部處理完的累計成本可以描述如下

(8)

虛擬機處理任務的最優(yōu)與最差成本分別記為min(costj)、max(costj)，結合Tmin與Tmax可得全部任務處理完成所需的最優(yōu)和最差成本消耗如下

Cmin=Tmin×min(costj)

(9)

Cmax=Tmax×max(costj)

(10)

于是，可以將任務成本約束定義如下

CC=(Ctotak-Cmin)/(Cmax-Cmin)

(11)

3.3 負載及綜合約束

資源與任務的調(diào)度管理都是動態(tài)的，任意資源上的負載情況都在不斷變化，從而形成不同資源上的負載均衡問題。在分析任務時間時，考慮了虛擬機的Wj、Cj、Mj、Fj四個參數(shù)，如果通過計算發(fā)現(xiàn)某些虛擬機的參數(shù)較好，便會有大量的任務被分配過來，導致網(wǎng)絡資源產(chǎn)生空洞或者熱點。因此，即便是虛擬機性能參與了時間約束計算，仍然不能有效保證負載的均衡分配。于是根據(jù)參數(shù)Wj、Cj、Mj、Fj，將負載公式描述如下

Lj=a1Wj+a2Cj+a3Mj+a4Fj

(12)

a1～a4代表對應參數(shù)的權重，且a1+a2+a3+a4=1。

將任務時間與任務成本采取加權合并，結合資源負載情況得到綜合目標如下

(13)

λ1與λ2代表權重系數(shù)，且λ1+λ2=1；Lc代表負載約束，其值越小，意味著該虛擬機性能越差，被選擇的可能性越小。

4 改進PSO算法

經(jīng)過云資源調(diào)度模型和目標約束分析，采用一種改進PSO算法來解決此資源調(diào)度NP問題。根據(jù)PSO算法需要先確定粒子及相應參數(shù)，這里選擇將每個子任務看做一個粒子。由于子任務是非連續(xù)的[9]，所以對粒子采取自然數(shù)編碼為Q={q1，q2，…，qm}。對于任意粒子，可能對應的虛擬機有n種選擇，于是其維度為n。其中qij即代表任務映射到資源上。將粒子i的位置參數(shù)描述為向量Qi=(qi1，qi2，…，qiu)T，速度參數(shù)描述為Si=(si1，si2，…，siu)T。假定粒子所在空間表示為R=(xmax-xmin，ymax-ymin，zmax-zmin)，粒子起始位置為Ps(xstart，ystart，zstart)，最終位置為Pt(xtarg et，ytarg et，ztarg et)，則粒子的位置參數(shù)初始化為

(14)

(15)

在根據(jù)位置和速度的更新迭代搜索得到最優(yōu)粒子時，粒子位置參數(shù)更新過程表示如下

qi(k+1)=qi(k)+(1-ηi(k))si(k+1)

(16)

qi(k+1)為第k+1次迭代后得到的最新位置；ηi(k)為調(diào)整因子，其計算方式表示為

(17)

粒子的速度更新公式表示如下

si(k+1)=ε(k)si(k)+a1b1(q′i(k)-qi(k))+

a2b2(q′(k)-qi(k))

(18)

式中a1和a2均表示(0，1)范圍內(nèi)隨機數(shù)，用于提高粒子群多樣性；b1和b2是加速系數(shù)，用于控制粒子的訓練性。ε(k)表示慣性系數(shù)，它會直接影響尋優(yōu)效果，應該在迭代過程中實時進行調(diào)整，使其保持最優(yōu)。在參數(shù)更新過程中，PSO存在前期搜索過快，容易出現(xiàn)可行解被略過的現(xiàn)象。為避免該缺陷對算法收斂的影響，在迭代前期，應該使用較大的ε(k)值，控制PSO收斂速度。隨著迭代次數(shù)的增加，逐漸逼近最優(yōu)解，降低ε(k)值以提高收斂速度。這樣做的同時，也可以有效防止PSO早熟?；谝陨纤枷?，ε(k)的調(diào)整公式描述為

(19)

因為粒子具有趨向性，使得PSO在多樣性方面存在缺陷。為此，在每一輪的迭代更新時，粒子都在當前位置上通過隨機方式移動一步，比較移動前后的適應性。若移動后的適應性變好，則以移動后的位置作為最新位置，繼續(xù)更新；若移動后的適應性變差，則退回移動前的位置，繼續(xù)更新。更新過程中的適應性計算公式如下

(20)

式中μ和ω表示(0，1)范圍內(nèi)的衡量系數(shù)；適應性與負載約束成正比，與時間成本約束成反比。

5 仿真與結果分析

基于CloudSim仿真環(huán)境，將本文提出的資源調(diào)度算法添加至Datacenter Broker類中。同時將改進蟻群實現(xiàn)的資源調(diào)度算法(LACO)[8]也添加至Datacenter Broker類中，與改進PSO調(diào)度算法進行對比。算法中給定參數(shù)costj∈[1，10]，b1=b2=1，εmax=0.9，εmin=0.3，移動步長為0.05R。仿真實驗參數(shù)給定如表1所示。

表1 實驗參數(shù)給定

圖1 任務延時曲線

在任務規(guī)模為100、300和500三種情況下，得到兩種算法的任務延時，結果如圖1所示。從任務延時曲線比較可知，改進PSO調(diào)度算法在迭代初期為避免最優(yōu)解被忽略，對粒子速度采取抑制，雖然初期收斂速度沒有改進蟻群算法快，但是到了中后期，由于更新方式和慣性系數(shù)等優(yōu)化，收斂性能顯著優(yōu)于LACO算法。任務規(guī)模為100時，完成最優(yōu)解搜索時比LACO迭代少了25次，任務延時少了10ms；任務規(guī)模為300時，完成最優(yōu)解搜索時比LACO迭代了45次，任務延時少了23ms；任務規(guī)模為500時，完成最優(yōu)解搜索時比LACO迭代了82次，任務延時少了53ms。另外可以看出，任務數(shù)量的增加對本文算法的影響較LACO算法小，表明本文算法的尋優(yōu)和收斂效果更好，對于大規(guī)模任務具有更好的處理能力。

任務規(guī)模從100增加至500時，仿真得到兩種算法的任務成本消耗，結果如圖2所示。比較發(fā)現(xiàn)，任務規(guī)模為100時，兩種算法的成本消耗相差無幾。但是隨著任務規(guī)模的增加，成本消耗相差越來越大。當任務規(guī)模為500時，本文算法的成本消耗較LACO算法節(jié)省了13.81%。本文算法在資源調(diào)度過程中考慮了成本約束，任務規(guī)模越大，成本節(jié)約越顯著。

圖2 任務成本消耗比較

仿真得到兩種算法的負載情況，結果如圖3所示。根據(jù)對比發(fā)現(xiàn)，在任務規(guī)模為100時，兩種算法的負載率差別不大，隨著任務規(guī)模增加，兩種算法都表現(xiàn)出較好的負載率，整個過程負載率均保持在50%以下，但是本文算法的負載率較LACO算法更好。這是由于本文算法考慮了負載約束，同時在時間約束過程中也考慮了負載因素影響。

圖3 負載率結果比較

6 結束語

為了有效實現(xiàn)云計算資源調(diào)度路徑優(yōu)化，本文提出了基于改進PSO調(diào)度算法。首先分析了資源與任務的映射模型，然后對映射過程中的各類條件約束進行具體分析。最后引入PSO算法，并對PSO粒子初始化、更新，以及適應性做了相應優(yōu)化。通過仿真實驗結果，證明本文算法能夠明顯降低云計算任務完成時間，有效節(jié)約任務成本，并且具有良好的資源負載率。