基于聚類和改進共生演算法的云任務(wù)調(diào)度策略

李昆侖，關(guān)立偉，郭昌隆

(河北大學 電子信息工程學院，河北 保定 071000)

0 引言

云計算是近幾年發(fā)展起來的一種按需共享信息服務(wù)模式，是未來網(wǎng)絡(luò)服務(wù)的重要形式[1]。云計算系統(tǒng)將不同物理位置上的資源整合為一個邏輯整體，為用戶提供一體化應用服務(wù)，因此，云環(huán)境中的任務(wù)調(diào)度與資源分配關(guān)系著整個云平臺的使用效率，其模型的優(yōu)劣直接關(guān)系到云計算系統(tǒng)是否能夠提供有效的、可靠的服務(wù)，任務(wù)調(diào)度是云計算的關(guān)鍵技術(shù)之一[2-4]。

在云環(huán)境中，以遺傳算法(Genetic Algorithm, GA)和粒子群優(yōu)化(Particle Swarm Optimization, PSO)算法等為代表的群體優(yōu)化算法被廣泛地應用于解決調(diào)度問題并取得了可觀的效果[5-8]。這些算法往往單一考慮調(diào)度代價，云計算的目標是按需提供服務(wù)，單純的計算時間、通信消耗或負載均衡無法滿足現(xiàn)實需求。因此，基于服務(wù)質(zhì)量(Quality of Service, QoS)的調(diào)度算法被相繼提出，主要分為基于成本的QoS和基于用戶滿意度的QoS?；诔杀镜腝oS綜合考慮執(zhí)行時間、負載均衡、資源利用率等，如文獻[9]提出一種基于成本的QoS驅(qū)動算法，算法不僅考慮了最大完工時間和負載均衡，還考慮了對任務(wù)進行分配時的時間和通信損耗，減小了調(diào)度代價。文獻[10]提出一種多QoS約束的調(diào)度算法，以執(zhí)行時間和資源利用率作為約束條件，并在動態(tài)環(huán)境中依據(jù)用戶預算和截止期限來完成對任務(wù)的調(diào)度，保證了較高的資源利用率和較少的調(diào)度時間?；谟脩魸M意度的QoS指在用戶能在期望時間內(nèi)完成任務(wù)的前提下，使用戶的綜合滿意值最高。王娟等[11]為了滿足不同用戶的QoS偏好，提出了一種具有偏好感知的粒子群算法，該算法為防止占有率較高的任務(wù)偏好掩蓋占有率低的任務(wù)，采用了按優(yōu)先級分別調(diào)度任務(wù)，提升了用戶的QoS。而文獻[12]同樣將用戶按QoS進行分類并對類別按優(yōu)先級來進行調(diào)度，與文獻[11]不同的是該算法設(shè)定了類間與類內(nèi)的雙優(yōu)先級，進一步提升了用戶的滿意度。

以上基于QoS的算法滿足了不同場景的調(diào)度需求，但進行調(diào)度的任務(wù)面向全體服務(wù)資源，存在選擇開銷和計算量較大的問題。現(xiàn)有研究表明，對資源進行聚類預處理是解決該問題的有效方式，如杜曉麗等[13]提出的有向無環(huán)圖(Direct Acyclic Graph, DAG)任務(wù)調(diào)度算法，陳志剛等[14]提出的資源多維性能聚類任務(wù)調(diào)度算法，以及李文娟等[15]和郭鳳羽等[16]采用的基于模糊聚類的云任務(wù)調(diào)度算法等。這些算法證明引入聚類操作可降低任務(wù)調(diào)度開銷，為本文提供了有益參考。因此，本文算法旨在解決以下問題：1)傳統(tǒng)調(diào)度算法未綜合考慮用戶滿意度與調(diào)度成本，沒有完全體現(xiàn)云計算廉價按需服務(wù)的宗旨；2)智能算法對資源的選擇開銷大，收斂速度慢?；诰垲惖乃惴▓?zhí)行代價小，但尋求最優(yōu)分配能力往往低于智能算法。故當處理的任務(wù)量增加，傳統(tǒng)算法不能平衡執(zhí)行代價與尋優(yōu)能力間關(guān)系。

針對上述問題，提出一種基于聚類和改進共生演(Symbiotic Organisms Search, SOS)算法的云任務(wù)調(diào)度策略。以提升云系統(tǒng)性能和云用戶滿意度為目標構(gòu)造評價函數(shù)，進一步體現(xiàn)云計算廉價按需服務(wù)的宗旨。將任務(wù)與資源進行聚類處理，減小對資源的選擇開銷、提高收斂速度；依據(jù)改進的共生演算法進行細節(jié)處理，加強算法尋優(yōu)能力。對比實驗表明，綜合聚類操作和共生演算法優(yōu)點的調(diào)度策略擁有較快的收斂速度和較強的尋優(yōu)能力，驗證了本文算法在基于批量模式的云任務(wù)調(diào)度問題上的有效性。

1 云計算任務(wù)調(diào)度模型

目前，Google提出的MapReduce編程模式[17]是目前云環(huán)境中應用最廣的編程模型，其基本執(zhí)行過程如圖1所示。

圖1 Map/Reduce 云任務(wù)調(diào)度模型 Fig. 1 Map/Reduce cloud task scheduling model

Mapreduce共有6個過程，分為兩個階段：Map階段和Reduce階段。Map階段將一個較大任務(wù)通過Map/Reduce函數(shù)分成N個較小任務(wù)并分配給多個Worker并行執(zhí)行，然后輸出中間文件保存在本地。Reduce階段將Map階段處理的結(jié)果進行分析和匯總并輸出最終結(jié)果。

依據(jù)上述模型，任務(wù)與資源可描述如下：

T={t1,t2,…,tn}表示待處理的任務(wù)集合，n=|T|代表子任務(wù)數(shù)，第i個任務(wù)刻畫為ti={tlength,tsource,tstorage}，其中tlength表示任務(wù)長度，tsource表示傳輸數(shù)據(jù)量，tstorage表示所需存儲空間。

R={r1,r2,…,rm}為云環(huán)境中的可用資源，m=|R|代表有效資源數(shù)。第j個資源rj(j∈[1,m])可以進一步刻畫為rj={rcomput,rbandwidth,rstorage}。其中：rcomput為資源的計算能力，rbandwidth為資源的傳輸能力，rstorage表示資源的存儲能力。

2 基于聚類和改進共生演的云任務(wù)調(diào)度策略

2014年，Cheng等[18]通過模仿自然界中不同生物間關(guān)系，提出一種新型優(yōu)化算法——共生演(Symbiotic Organisms Search, SOS)算法。SOS算法最初用來解決復雜函數(shù)的優(yōu)化問題，其易于實現(xiàn)且魯棒性強，已被相繼用來解決旅行商問題(Travelling Salesman Problem, TSP)、結(jié)構(gòu)優(yōu)化問題和控制問題等[19-22]。

2.1 標準共生演算法

SOS算法包含共生、共棲和寄生3個過程，描述如下。

共生過程：

Xinew=Xi+rand(0,1)*(Xbest-Mutual_Vector*BF1)

(1)

Xjnew=Xj+rand(0,1)*(Xbest-Mutual_Vector*BF2)

(2)

Mutual_Vector=(Xi+Xj)/2

(3)

其中：Xi為第i個個體，Xj是隨機與Xi相作用的個體。rand(0,1)是[0,1]間的隨機數(shù)，BF1和BF2取值為1或2。

共棲過程：

Xinew=Xi+rand(-1,1)*(Xbest-Xj)

(4)

其中：rand(-1,1)為[-1,1]隨機數(shù)，(Xbest-Xj)反映一種受益關(guān)系，由Xj提供信息提升Xi的存活率。

寄生過程：

Xinew=Xp

(5)

Xp為系統(tǒng)中個體通過隨機修改不同維數(shù)中的數(shù)值產(chǎn)生，能夠增加種群多樣性，防止陷入局部最優(yōu)。

2.2 共生演算法的改進

文獻[23]采用式(6)對SOS算法進行離散化，并證明在解決云任務(wù)調(diào)度問題時，離散共生演算法(Discrete Symbiotic Organisms Search, DSOS)相比PSO等智能算法能夠得到更好的調(diào)度結(jié)果。本文以DSOS作為基本算法并對其進行以下改進，可進一步提高收斂速度和減小算法陷入局部最優(yōu)的概率。

(6)

Xinew為更新個體，「?為ceil函數(shù)，mod為求余函數(shù)。

2.2.1 考慮潛在解的離散共生演算法

DSOS是一個更新與淘汰的過程，直接淘汰適應度低個體可能會損失潛在優(yōu)秀解。如圖2，黑色標記代表已找到最優(yōu)分配位置，灰色代表未找到最優(yōu)分配，其中A1代表當前最優(yōu)，A2、A3為相比較的個體。很明顯A2適應度大于A3，但若要實現(xiàn)全部最優(yōu)分配，A2需要改變兩部分片段，A3只需改變一部分片段，所以在尋優(yōu)速度上，A3很可能會大于A2。

圖2 三種個體基因比較 Fig. 2 Comparison of three individual genes

為克服上述缺陷，本文提出一種交叉方式，盡量減小優(yōu)秀潛在解的損失，見式(7)：

(7)

其中:J(x)為判斷函數(shù)，接受更優(yōu)個體，G(x1,x2)為在x1,x2間進行交叉變異的函數(shù)，隨機選取交叉點，為防止交叉后個體與當前最優(yōu)相同，變異位在最優(yōu)片段范圍選取，Xi為第i代適應度更高個體，Xzi為第i代暫時淘汰個體，Xbesti為第i代最優(yōu)個體。

2.2.2 旋轉(zhuǎn)學習尋優(yōu)操作

2.2.1節(jié)在一定程度上加強了算法的性能，但算法依然可能陷入局部最優(yōu)。因此，為增強算法的勘探能力，補充種群多樣性，本文用旋轉(zhuǎn)學習機制(Rotation-Based Learning, RBL)更新個體。

旋轉(zhuǎn)角度決定RBL性能，角度固定，則學習范圍固定。DSOS前期探索能力強，后期弱，固定旋轉(zhuǎn)不適用SOS算法高效更新，因此，本文采用自適應角度旋轉(zhuǎn)：β=d·2*π/Iter，d取值1或-1，決定旋轉(zhuǎn)方向，Iter為迭代次數(shù)。該角度設(shè)定滿足算法前期大范圍搜索和后期小范圍搜索的情況。

如圖3所示，b和a對應搜索空間的上下限，C為[a,b]中點，以C為圓心，(a+b)/2為半徑作圓，設(shè)Z為N點坐標。

圖3 二維空間中的旋轉(zhuǎn)學習機制 Fig. 3 Rotational learning mechanism in two-dimensional space

將旋轉(zhuǎn)學習機制嵌入到算法的操作為：

1)選取個體Xi對其每一維度都進行旋轉(zhuǎn)學習，如下：

(8)

2)對M以旋轉(zhuǎn)角度β進行旋轉(zhuǎn)至P，點P在x軸上的投影Q為對應旋轉(zhuǎn)學習的結(jié)果，則：

(9)

推廣至高維情形，對應的旋轉(zhuǎn)數(shù)可表示為：

z*=(ai+bi)/2-(μj×cosβ-νj×sinβ)

(10)

3)采用式(11)對學習點進行離散化，選取優(yōu)秀個體進入下代種群:

(11)

式(11)的離散方式更適合本文對β角的規(guī)定，實驗表明該離散方式比直接采用ceil、floor或mod函數(shù)更有效。

2.3 資源與任務(wù)的模糊聚類

2.3.1 經(jīng)典模糊C均值算法

模糊C均值(Fuzzy C-Means, FCM)是Bezdek于1981年提出[24]，是基于目標函數(shù)聚類算法中較完善、應用較廣的一種算法。任務(wù)或資源間沒有確定的分界線，具有模糊特性，因此本文采用FCM對任務(wù)和資源進行模糊分類。FCM目標函數(shù)為：

(12)

其中：μij表示隸屬度，ci是模糊組i的聚類中心，dij=‖ci-xj‖為第i個中心與第j個數(shù)據(jù)間的歐氏距離，m是一個加權(quán)指數(shù)。

2.3.2 資源的重排序放置與任務(wù)的模糊聚類

任務(wù)調(diào)度結(jié)果主要受資源計算能力、通信帶寬和存儲能力的影響，因此許多學者主要從處理能力、通信能力和存儲能力三方面考慮資源的性能。本文參考文獻[14-15]，將資源模糊分為計算型資源、帶寬型資源和存儲型資源三類，并對其進行重排序放置，如圖4所示。

圖4 資源的聚類重排序 Fig. 4 Clustering and reordering for resources

操作過程如下。

1)用式(13)對任務(wù)與資源進行模糊量化：

(13)

2)設(shè)置閾值t、迭代次數(shù)k和隸屬度矩陣U，將資源分為R1、R2、R33類，將任務(wù)分為T1、T2、T3類。

3)依據(jù)類別相似度對資源集合按性能由高到低進行排序，并再次設(shè)定閾值t′，使?jié)M足‖tmi-tmc‖≤t′的任務(wù)i歸入到第m(m=1,2,3)類,剩余任務(wù)納入第4類，tmc為第m類聚類中心。

4)利用如下公式計算任務(wù)集需求度和資源綜合能力：

(14)

(15)

5)按式(16)對任務(wù)進行指導分配；

da=‖tcd-rp‖

(16)

2.3.3 聚類的效用分析

受積木原理的啟發(fā)，稱聚類效用為積木效用，即在有限空間內(nèi)放置積木塊使積木高度最低。表1為初始化后相應資源擬分配到的任務(wù)，依據(jù)分配結(jié)果可將相對應任務(wù)量和資源的計算能力抽象為兩組積木塊組合，如圖5將任務(wù)抽象為計算量積木，積木的長度代表對資源計算能力的需求。將資源抽象為性能積木，積木長度為處理單位任務(wù)量的時間消耗。

表1 資源所分配到的任務(wù)Tab. 1 Tasks assigned to resources

圖5 任務(wù)與資源的積木抽象 Fig. 5 Task and resource abstract model

理想的調(diào)度結(jié)果是使完工時間最短且負載均衡，即任務(wù)積木與資源積木的最優(yōu)壘積，如圖6。

圖6 理想分配效果 Fig. 6 Ideal assignment results

未經(jīng)任何處理的資源初始化后任務(wù)分配沒有任何規(guī)律，可看出得到由圖5到圖6的結(jié)果需要多次搜索且不一定能得到最優(yōu)分配。針對該問題，本文采用聚類操作可在一定程度上改善算法性能。首先對資源進行聚類后按類間相似度和相鄰資源差異度重新排序放置，使得資源在虛擬空間中按標號有規(guī)律地放置，如圖7所示。

圖7 資源聚類后重排序放置 Fig. 7 Reordered placement after resource clustering

對任務(wù)進行聚類后，同一類別任務(wù)對資源需求具有相似性，進行調(diào)度時必然偏向選取排序后資源的相似位置，使任務(wù)進行分配具有一定的目的性。經(jīng)過指導迭代后便可得到如圖8所示供需吻合的粗略結(jié)果。指導迭代是指通過計算任務(wù)集合對資源集合的需求來指導該類別任務(wù)在編碼中的位置，以吻合相對應資源類別的迭代。

與傳統(tǒng)算法不同，本文設(shè)定任務(wù)聚類集合為動態(tài)類集合，操作過程中同一類別任務(wù)依然可以選擇非與該類最相似的資源集合，即某類任務(wù)較多時，可將部分任務(wù)調(diào)度到其他類資源進行處理，可保證系統(tǒng)的負載均衡。聚類后開始執(zhí)行調(diào)度算法，每次調(diào)度針對同一類別任務(wù)進行(其他類別任務(wù)作為約束信息)，因此稱本步操作為細節(jié)搜索階段。實驗證明本文方法更易得到與資源吻合的理想結(jié)果，如圖9所示。

圖8 聚類及指導迭代后任務(wù)聚集形式 Fig. 8 Task aggregation form after clustering and guided iteration

圖9 最終理想分配結(jié)果 Fig. 9 Final ideal assignment results

聚類后不易進入局部最優(yōu)的原因：本文改進的共生演算法主體用式(1)～(5)進行種群更新并利用式(6)進行離散化。由于算法的貪婪選擇特性，算法后期種群中的個體具有極強的相似性，在空間隨機選取的進行共生的兩個個體可表示為Xi=Xs,Xj=Xs且Xbest=Xs,因此式(1)可描述如下：

Xinew=Xi+rand(0,1)*(Xbest-BF*(Xi+Xj)/2)=

Xs+rand(0,1)*(Xs-BF*(Xs+Xs)/2)=

Xs+rand(0,1)*(Xs-BF*Xs)

Xs-BF*Xs的取值為0或Xs，因此Xinew的取值范圍為：

max(Xinew)=Xs+0*(Xs-BF*Xs)或

max(Xinew)=Xs+rand(0,1)*0=Xs

同理得到：

min(Xnew)=Xs+1*(Xs-2*Xs)=Xs-Xs=0

Xinew=Xi+rand(-1,1)*(Xbest-Xj)=

Xs+rand(-1,1)*(Xs-Xs)=Xs=Xi

上式表明共棲過程后期可能起不到更新種群的作用，前兩步搜索不到的位置只能依靠寄生操作實現(xiàn)，但寄生操作不一定能夠得到有效更新，算法在后期搜索效率低下。

對資源和任務(wù)進行聚類后上述問題得到改善，算法后期任務(wù)雖只能搜索到小于當前標號的資源，但是聚類后的資源聚集在相似位置，相似任務(wù)目的性地搜索資源，使算法后期依然以更大概率搜索到全局最優(yōu)。本文又將資源按照處理能力由高到低的順序排列如圖7，使得處理能力強的資源能夠被搜索到的概率更大，避免了處理能力強資源閑置的現(xiàn)象。因此，本文采取的聚類操可加強算法尋優(yōu)能力。

2.4 編碼策略

傳統(tǒng)編碼形式多為資源-任務(wù)間接編碼形式，X={x1,x2,…,xN},其中N代表任務(wù)總數(shù)，xi代表第i個任務(wù)所分配的處理機標號。

本文采取聚類操作和指導迭代，每次進化操作均對同一類別個體進行，傳統(tǒng)編碼形式并不適應此操作，因此，本文提出一種可變資源-任務(wù)間接編碼形式，X={xi1,xi2,…,xin}∪ {xj1,xj2,…,xjm}∪{xz1,xz2,…,xzp},其中i、j、z代表類別標號，n、m、p為每個類別的任務(wù)數(shù)，n+m+p=N，N為總?cè)蝿?wù)數(shù)。

∪位置為可交換節(jié)點，片段染色體位置可更改，片段染色體針對相應類別個體進行編碼產(chǎn)生。因此，依據(jù)指導迭代更新片段染色體位置，減小了對資源的選取范圍，對片段內(nèi)個體進行更新，可加強算法的細節(jié)搜索能力。

2.5 評價模型

為體現(xiàn)云計算廉價按需提供服務(wù)的宗旨，本文提出一種綜合調(diào)度成本和用戶滿意度的驅(qū)動模型。

將同一物理平臺或應用服務(wù)于盡可能多的用戶，必須減小資源的空閑率，提高資源的整體使用率，從而使得成本降低，提升經(jīng)濟效益，故本文將任務(wù)的處理時間和資源利用率作為成本約束條件。其中時間指標函數(shù)為：

(17)

其中：m為資源數(shù)，k為第j個處理器上要處理任務(wù)的數(shù)量，w(i,j)表示第i個任務(wù)在第j個處理器上的時間損耗。資源利用率指標函數(shù)為：

(18)

其中：NV為資源總數(shù)；uv表示第v個資源的綜合利用率；實驗發(fā)現(xiàn)資源利用率與時間消耗不處于同一數(shù)量級，因此采用加入權(quán)重c(本文取值15)的方式，使得二者數(shù)量級相同，因此調(diào)度代價適應度函數(shù)定義為：

Fd=min(α*ft+β*fu)

(19)

其中：α、β∈rand(0,1),α+β=1且α·β≠0。

為提升用戶滿意度，本文提出一種基于偏好的滿意度模型。將任務(wù)按屬性分為四類：計算型任務(wù)、帶寬型任務(wù)、存儲型任務(wù)和普通任務(wù)。計算型任務(wù)的評價準則為：

(20)

(21)

存儲型任務(wù)的評價準則：

(22)

普通任務(wù)評價準則：

(23)

綜合評價準則定義為：

Ftotal=max(Δ-(Ft+Fr+Fc+Fp)/N)

(24)

N1、N2、N3、N4為各類任務(wù)的數(shù)量，且N1+N2+N3+N4=N,Δ為滿意度最優(yōu)值，一般Δ=10。故本文的驅(qū)動模型為：

Fz=γ1*Ftotal-γ2*ε*Fd

(25)

其中：γ1、γ2為權(quán)重系數(shù)，ε為數(shù)量級調(diào)整系數(shù)。

2.6 算法流程

考慮任務(wù)數(shù)量大小對聚類效果的影響，算法設(shè)定任務(wù)數(shù)小于設(shè)定值NT(NT值取60～150時效果最佳)時直接采用改進的SOS算法，當任務(wù)數(shù)大于設(shè)定值NT時采用基于聚類的改進共生演算法——基于模糊C均值和改進共生演算法的云任務(wù)調(diào)度算法(Fuzzy c-means based and Improved Discrete Symbiotic Organisms Search algorithm, FIDSOS)，具體過程描述如下。

1)參數(shù)初始化：設(shè)置種群大小Scale、迭代次數(shù)K、終止條件及各項參數(shù)。

2)算法選擇與種群初始化：判斷任務(wù)數(shù)目是否大于設(shè)定閾值NT，大于則進入步驟3)，否則依據(jù)資源-任務(wù)整體編碼方式生成初始種群并進入步驟4)。

3)對任務(wù)和資源進行模糊聚類并對資源進行重排序，依據(jù)任務(wù)的聚類結(jié)構(gòu)按照可變資源-任務(wù)間接編碼方生成初始種群，進行指導迭代后進入步驟4)。

4)依據(jù)改進DSOS算法對種群進行更新得到進化種群：

①按SOS算法過程對種群進行進化更新；

②對暫淘汰個體按式(7)進行更新操作；

③對當前優(yōu)秀個體進行旋轉(zhuǎn)尋優(yōu)操作。

5)判斷種群是否達到終止條件，達到則進入步驟6)；否則返回步驟4)。

6)得到調(diào)度結(jié)果，計算滿意度和調(diào)度代價。

3 實驗與分析

3.1 實驗環(huán)境及實驗參數(shù)

參考文獻[11-12]及[25-26]模擬搭建的云任務(wù)調(diào)度仿真系統(tǒng)及作者在文獻[27]所做的前期工作，利用Matlab實現(xiàn)一個云任務(wù)調(diào)度仿真系統(tǒng)。仿真系統(tǒng)主要由任務(wù)產(chǎn)生器、資源產(chǎn)生器、故障干擾產(chǎn)生器、調(diào)度器和評價器5部分組成。任務(wù)產(chǎn)生器產(chǎn)生任務(wù)向量，任務(wù)屬性包括任務(wù)大小等QoS因素，本文研究的是批任務(wù)。資源產(chǎn)生器可依據(jù)要求產(chǎn)生資源，資源屬性包括：CPU頻率(計算能力)、能提供的存儲空間、帶寬等。故障干擾產(chǎn)生器主要模擬網(wǎng)絡(luò)中可能出現(xiàn)的故障，作用于資源，可影響資源屬性。調(diào)度器接收到調(diào)度請求后對任務(wù)和可用資源進行標號并依據(jù)調(diào)度算法得到的結(jié)果將任務(wù)分配到資源上，然后更新節(jié)點值。評價器判斷調(diào)度結(jié)果是否滿足系統(tǒng)和用戶需求。

仿真系統(tǒng)模擬10～1 000個任務(wù)在處理器上的執(zhí)行情況。通過控制任務(wù)產(chǎn)生器將任務(wù)長度控制在[500,1 500]范圍內(nèi)，帶寬需求控制在[100,500]內(nèi)，存儲需求控制在[200，1 000]內(nèi)；同理，通過控制資源產(chǎn)生器，將資源的計算能力控制在[2 000,10 000]內(nèi)，傳輸能力控制在[500,5 000]內(nèi)，存儲能力控制在[500,5 000]內(nèi)。各項指標均按一定規(guī)則在上述范圍內(nèi)用模擬器隨機生成。

將本文算法與改進遺傳算法(Global Genetic Algorithm, GGA)、混合粒子群遺傳算法(Hybrid Particle Swarm Optimization and Genetic Algorithm, PSO-GA)和基本DSOS算法進行對比分析。優(yōu)化目標為最小代價和用戶滿意度。實驗統(tǒng)一設(shè)置終止條件為最大迭代次數(shù)為400次或連續(xù)50次迭代差值小于0.001。算法具體參數(shù)參照表2。

表2 算法參數(shù)Tab. 2 Algorithm parameters

表3 不同任務(wù)數(shù)算法性能對比Tab. 3 Performance comparison with different number of tasks

圖10 任務(wù)數(shù)不同時適應度和迭代次數(shù)對比 Fig. 10 Fitness and iteration comparison with different number of tasks

其中改進GA中:

(26)

(27)

其中：fmax為最大的適應度值，favg為平均適應度值，f′為要交叉的兩個個體中較大的適應度值，f為要變異個體的適應度值；PSO-GA算法中rand(0,1)代表在0～1隨機取值；本文算法中fb=2*π/k，k為當前迭代次數(shù)。

3.2 實驗結(jié)果分析

為防止特殊情況對實驗結(jié)果的影響，所有實驗各運行10次，記錄調(diào)度成本值和用戶滿意度并取10次的平均值作為最終結(jié)果。

系統(tǒng)生成8個虛擬機資源和10、20、60、100、150、200、550、1 000個數(shù)目的子任務(wù)集合進行實驗。

表3展示了任務(wù)數(shù)量為60和550時的算法性能，可知四種算法中GGA算法穩(wěn)定性較差，其次為PSO-GA算法。DSOS算法和本文算法擁有較好的穩(wěn)定性，且在任務(wù)數(shù)增加時本文穩(wěn)定性所受影響較小。算法迭代次數(shù)和尋優(yōu)能力對比如圖10所示，為方便說明任務(wù)數(shù)大小對算法的影響，選取對比任務(wù)數(shù)為60、200、550和1 000 四個數(shù)目?？煽闯霎斎蝿?wù)數(shù)較少時四種算法的尋優(yōu)能力相差不大，隨著任務(wù)數(shù)的增加本文算法尋優(yōu)能力優(yōu)勢越發(fā)明顯。當任務(wù)數(shù)超過200后其他算法性能極度下降，性能下降最快的是遺傳算法，而本文算法依然保持著較好魯棒性和較強的尋優(yōu)能力。遺傳算法更新個體上依靠交叉和變異，交叉點和變異點數(shù)目的選取影響著算法速度，隨著任務(wù)數(shù)目的增加若交叉點和變異點一成不變必然會導致算法尋優(yōu)能力變差。而PSO算法和SOS算法依據(jù)各自的進化公式在相應的解空間上不斷搜索最優(yōu)解，尋優(yōu)所受影響勢必小于遺傳算法，但由于搜索的無目的性和評價函數(shù)的影響，在任務(wù)數(shù)增加時依然會使得尋優(yōu)能力變差。本文算法對資源和任務(wù)進行模糊聚類后，能在解空間上具有目的性的搜索，使得算法尋優(yōu)速度快且不會因為由于任務(wù)數(shù)的增加而使得算法性能加速下降。

尋優(yōu)速度不能完全說明算法優(yōu)劣，本文旨在最小化調(diào)度代價的同時最大化用戶滿意度。由圖11和圖12知，任務(wù)較少時本文算法與其他三種算法在調(diào)度代價和用戶滿意度上相差甚微，只有當任務(wù)數(shù)增加到60時差別才開始顯現(xiàn)，效果最差的為GGA算法，PSO-GA與DSOS算法效果相當，本文算法在調(diào)度代價和用戶滿意度上都有著較好結(jié)果。

隨著任務(wù)規(guī)模逐漸增加，算法差異開始變得明顯。由圖13可看出在調(diào)度代價上DSOS算法與PSO-GA算法尋優(yōu)能力相當，GGA算法表現(xiàn)最差，本文算法保持最優(yōu)；但在用戶滿意度上(如圖14所示)，DSOS算法與GGA算法相當，均劣于PSO-GA算法，本文算法保持最優(yōu)且優(yōu)勢愈發(fā)明顯。

傳統(tǒng)改進算法單一考慮系統(tǒng)性能或用戶滿意度，在以調(diào)度成本約束用戶滿意度的情況下可能產(chǎn)生不一樣的優(yōu)化結(jié)果，算法性能無法保證。本文采用基于聚類和改進共生演的算法能夠在保持最小化調(diào)度代價的同時在解空間進行有目的性的搜索，可收斂到更優(yōu)解，進而提高了用戶的滿意度。由此可見，F(xiàn)IDSOS算法具有更好的性能。

圖11 任務(wù)較少時算法調(diào)度代價對比 Fig. 11 Cost comparison with less tasks

圖12 任務(wù)較少時用戶滿意度對比 Fig. 12 Satisfaction comparison with less tasks

圖13 任務(wù)較多時算法調(diào)度代價對比 Fig. 13 Cost comparison with more tasks

圖14 任務(wù)較多時用戶滿意度對比 Fig. 14 Satisfaction comparison with more tasks

4 結(jié)語

針對現(xiàn)有一些調(diào)度算法未將調(diào)度代價和用戶滿意度綜合考慮且容易陷入局部最優(yōu)解、收斂慢的問題，提出一種在云環(huán)境下使用的任務(wù)調(diào)度算法。為提升算法精度，設(shè)置閾值NT，任務(wù)數(shù)量小于NT時直接采用改進共生演算法，任務(wù)數(shù)大于NT時采用基于聚類和改進的共生演算法。通過對任務(wù)和資源進行聚類，算法能對解空間進行目的性的搜索，進而提高算法的尋優(yōu)速度。改進共生演算法考慮潛在優(yōu)秀解可防止優(yōu)秀解的丟失，最后對整個種群進行的旋轉(zhuǎn)尋優(yōu)操作，減小了算法陷入局部最優(yōu)的概率，加強了算法的尋優(yōu)能力。實驗結(jié)果表明，相比改進的遺傳算法GGA、PSO-GA算法和DSOS算法，本文算法在保持高收斂性能的前提上能夠搜索到更為優(yōu)秀的解，能夠?qū)崿F(xiàn)較小調(diào)度成本且能夠提高用戶的滿意度。

參考文獻(References)

[1] FOSTER I, ZHAO Y,RAICU I, et al. Cloud computing and grid computing 360-degree compared [C]// GCE’08: Proceedings of the 2008 Grid Computing Environments. Washington,DC: IEEE Computer Society, 2008: 1-10.

[2] BOCHENINA K. A comparative study of scheduling algorithms for the multiple deadline-constrained workflows in heterogeneous computing systems with time windows [EB/OL]. [2017- 04- 12]. http://pdfs.semanticscholar.org/c88f/93f927d69432276665f53a5203c6987e8594.pdf.

[3] DURAO F,FONSEKA A,GARCIA V C, et al. A systematic review on cloud computing [J]. Journal of Supercomputing, 2014, 68(3): 1321-1346.

[4] AVRAM M G. Advantages and challenges of adopting cloud computing from an enterprise perspective [EB/OL]. [2017- 04- 12].https://core.ac.uk/download/pdf/82662807.pdf.

[5] AHMAD S G, LIEW C S, MUNIR E U, et al. A hybrid genetic algorithm for optimization of scheduling workflow applications in heterogeneous computing systems [J]. Journal of Parallel and Distributed Computing, 2016, 87(C): 80-90.

[7] BRATTON D, KENNEDY J. Defining a standard for particle swarm optimization [C]// Proceedings of the 2007 IEEE Swarm Intelligence Symposium. Washington, DC: IEEE Computer Society, 2007: 120-127.

[8] XUE S-J, WU W. Scheduling workflow in cloud computing based on hybrid partial swarm algorithm [J]. TELKOMNIKA : Indonesian Journal of Electrical Engineering, 2012,10(7): 1560-1566.

[9] BANSAL N, MAURYA A, KUMAR T, et al. Cost performance of QoS driven task scheduling in cloud computing [EB/OL]. [2017- 04- 15]. http://core.ac.uk/download/pdf/82232227.pdf.

[10] ARABNEJAD H, BARBOSA J G. Multi-QoS constrained and profit-aware scheduling approach for concurrent workflows on heterogeneous systems [J]. Future Generation Computer Systems, 2017,68: 211-221.

[11] 王娟,李飛,張路橋.PSO應用于QoS偏好感知的云存儲任務(wù)調(diào)度[J].通信學報,2014,35(3):231-238.(WANG J, LI F, ZHANG L Q. Apply PSO into cloud task scheduling with QoS preference awareness [J]. Journal on Communications, 2014, 35(3): 231-238.)

[12] GAMAL EL DIN HASSAN ALI H, SAROIT I A, KOTB A M. Grouped tasks scheduling algorithm based on QoS in cloud computing network [J]. Egyptian Informatics Journal, 2017, 18(1): 11-19.

[13] 杜曉麗,蔣昌俊,徐國榮,等.一種基于模糊聚類的DAG任務(wù)圖調(diào)度算法[J].軟件學報,2006,17(11):2277-2288.(DU X L, JIANG C J, XU G R, et al. A grid DAG scheduling algorithm based on fuzzy clustering [J]. Journal of Software, 2006, 17(11): 2277-2288.)

[14] 陳志剛,楊博.網(wǎng)絡(luò)服務(wù)資源多維性能聚類任務(wù)調(diào)度[J].軟件學報,2009,20(10):2766-2774.(CHEN Z G,YANG B. Task scheduling based on multidimensional performance clustering of grid service resources [J]. Journal of Software,2009, 20(10): 2766-2774.)

[15] 李文娟,張啟飛,平玲娣,等.基于模糊聚類的云任務(wù)調(diào)度算法[J].通信學報,2012,33(3):146-153.(LI W J, ZHANG Q F, PING L D, et al. Cloud scheduling algorithm based on fuzzy clustering [J]. Journal on Communications, 2012, 33(3): 146-153.)

[16] 郭鳳羽,禹龍,田生偉,等.云計算環(huán)境下對資源聚類的工作流任務(wù)調(diào)度算法[J].計算機應用,2013,33(8):2154-2157.(GUO F Y, YU L, TIAN S W, et al. Workflow task scheduling algorithm based on resource clustering in cloud computing environment [J]. Journal of Computer Applications, 2013, 33(8): 2154-2157.)

[17] DEAN J, GHEMAWAT S. MapReduce: simplified data processing on large clusters [C]// OSDI ’04: Proceedings of the 6th Conference on Symposium on Operating Systems Design and Implementation. Berkeley, CA: USENIX Association, 2004: 10.

[18] CHENG M Y, PRAYOGO D. Symbiotic organisms search: a new metaheuristic optimization algorithm [J]. Computer and Structures, 2014,139: 98-112.

[19] EZUGWU E S, ADEWUMI A O, FRINCU M E. Simulated annealing based symbiotic organisms search optimization algorithm for traveling salesman problem [J]. Expert Systems with Applications, 2017,77: 189-210.

[20] YU V F, REDI A A N P, YANG C L, et al. Symbiotic organisms search and two solution representations for solving the capacitated vehicle routing problem [J]. Applied Soft Computing, 2017, 52(C): 657-672.

[21] TEJANI G G, SAVSANI V J, PATEL V K. Adaptive Symbiotic Organisms Search (SOS) algorithm for structural design optimization [J]. Journal of Computational Design and Engineering, 2016, 3(3): 226-249.

[22] GUHA D, ROY P, BANERJEE S. Quasi-oppositional symbiotic organism search algorithm applied to load frequency control [J]. Swarm and Evolutionary Computation, 2016,33: 46-67.

[23] ABDULLAHI M, NGADI M A, ABDULHAMID S M. Symbiotic organism search optimization based task scheduling in cloud computing environment [J]. Future Generation Computer Systems, 2016,56: 640-650.

[24] BEZDEK J C. Pattern Recognition with Fuzzy Objective Function Algorithms [M]. Norwell, MA: Kluwer Academic Publishers, 1981:10-18.

[25] 王娟,李飛,劉兵,等.融合層次分析法的PSO云存儲任務(wù)調(diào)度算法[J].計算機應用研究,2014,31(7):2013-2016.(WANG J, LI F, LIU B, et al. AHP integrated PSO task scheduling algorithm in cloud storage system[J]. Application Research of Computers, 2014, 31(7): 2013-2016.)

[26] LI K. Scheduling parallel tasks with energy and time constraints on multiple manycore processors in a cloud computing environment [EB/OL]. [2017- 03- 01]. http://www.cs.newpaltz.edu/～lik/publications/Keqin-Li-FGCS-2017.pdf.

[27] 李昆侖,王珺,宋健,等.基于改進GEP和資源改變量的局部云任務(wù)調(diào)度算法[J].軟件學報,2015,26(S2):78-89.(LI K L, WANG J, SONG J, et al. Local cloud task scheduling algorithm based on improved GEP and change of resources [J]. Journal of Software, 2015, 26(S2): 78-89.)

This work is partially supported by the National Natural Science Foundation of China (61672205).

LIKunlun, born in 1962, Ph. D., professor. His research interests include pattern recognition, image processing, computer network, intelligent information processing.

GUANLiwei, born in 1990, M.S. candidate. His research interests include cloud computing task scheduling, virtualization.

GUOChanglong, born in 1991, M. S. candidate. His research interests include data mining, recommendation algorithm.