李 萌 ，劉 鑫

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

1 引言

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

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

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

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

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

(1)

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

3 目標(biāo)約束分析

3.1 任務(wù)時(shí)間約束

假定任務(wù)ri分配給虛擬機(jī)vj處理，則ri的完成時(shí)間可以描述如下

(2)

(3)

(4)

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

(5)

(6)

于是，可以將時(shí)間約束定義如下

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

(7)

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

3.2 任務(wù)成本約束

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

(8)

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

Cmin=Tmin×min(costj)

(9)

Cmax=Tmax×max(costj)

(10)

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

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

(11)

3.3 負(fù)載及綜合約束

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

Lj=a1Wj+a2Cj+a3Mj+a4Fj

(12)

a1～a4代表對(duì)應(yīng)參數(shù)的權(quán)重，且a1+a2+a3+a4=1。

將任務(wù)時(shí)間與任務(wù)成本采取加權(quán)合并，結(jié)合資源負(fù)載情況得到綜合目標(biāo)如下

(13)

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

4 改進(jìn)PSO算法

經(jīng)過云資源調(diào)度模型和目標(biāo)約束分析，采用一種改進(jìn)PSO算法來解決此資源調(diào)度NP問題。根據(jù)PSO算法需要先確定粒子及相應(yīng)參數(shù)，這里選擇將每個(gè)子任務(wù)看做一個(gè)粒子。由于子任務(wù)是非連續(xù)的[9]，所以對(duì)粒子采取自然數(shù)編碼為Q={q1，q2，…，qm}。對(duì)于任意粒子，可能對(duì)應(yīng)的虛擬機(jī)有n種選擇，于是其維度為n。其中qij即代表任務(wù)映射到資源上。將粒子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í)，粒子位置參數(shù)更新過程表示如下

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

(16)

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

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

(19)

因?yàn)榱Ｗ泳哂汹呄蛐裕沟肞SO在多樣性方面存在缺陷。為此，在每一輪的迭代更新時(shí)，粒子都在當(dāng)前位置上通過隨機(jī)方式移動(dòng)一步，比較移動(dòng)前后的適應(yīng)性。若移動(dòng)后的適應(yīng)性變好，則以移動(dòng)后的位置作為最新位置，繼續(xù)更新；若移動(dòng)后的適應(yīng)性變差，則退回移動(dòng)前的位置，繼續(xù)更新。更新過程中的適應(yīng)性計(jì)算公式如下

(20)

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

5 仿真與結(jié)果分析

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

表1 實(shí)驗(yàn)參數(shù)給定

圖1 任務(wù)延時(shí)曲線

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

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

圖2 任務(wù)成本消耗比較

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

圖3 負(fù)載率結(jié)果比較

6 結(jié)束語

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