基于競爭粒子群算法的云計算資源調(diào)度策略

王鎮(zhèn)道 張一鳴 石雪倩

摘? ? 要：針對大規(guī)模云計算環(huán)境下的資源調(diào)度問題，提出了改進的競爭粒子群優(yōu)化算法，以提高云計算資源調(diào)度效率. 基于多目標(biāo)綜合評價模型，首先建立包含任務(wù)完成時間、功耗以及負載均衡度的適應(yīng)度函數(shù)，再利用混沌優(yōu)化方法產(chǎn)生分布更加均勻的初始化粒子，引入自適應(yīng)概率的高斯變異對勝利粒子位置進行更新，以提高種群多樣性并增強全局搜索能力. 仿真試驗表明，在相同的條件下，本文算法能夠?qū)さ阶罴训恼{(diào)度方案，適用于大規(guī)模資源調(diào)度，且結(jié)果優(yōu)于對比模型.

關(guān)鍵詞：云計算;資源調(diào)度;負載均衡;競爭粒子群;混沌初始化;高斯變異;資源分配;算法

中圖分類號：TP301? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? 文獻標(biāo)志碼：A

Cloud Computing Resource Scheduling Strategy Based

on Competitive Particle Swarm Algorithm

WANG Zhendao1，ZHANG Yiming1?，SHI Xueqian2

（1. School of Physice and Electronics，Hunan University，Changsha 410082，China;

2. Nova Energie Co，Ltd，Changsha 410205，China）

Abstract：To solve the resource scheduling problem in the large-scale cloud computing environment， this paper proposes an improved competitive particle swarm optimization algorithm （ICSO） to improve the efficiency of resource scheduling in cloud computing. Based on the multi-objective comprehensive evaluation model， firstly， the fitness function including task completion time， power consumption and load balance are established. Then， the more evenly distributed initialization particles are generated by the chaos optimization method， and the Gaussian mutation of adaptive probability is introduced to update the position of the victory particles， so as to improve the population diversity and enhance the global search ability. Simulation results show that under the same conditions， the algorithm can find the best scheduling scheme， which is suitable for large-scale resource scheduling， and the results are better than the comparison model.

Key words：cloud computing;resource scheduling;load balancing;Competitive Particle Swarm Optimization algorithm（CSO）;chaos initialization;Gaussian variation;resource allocation;algorithms

云計算（Cloud Computing）是繼分布式計算（Distributed Computing）、并行處理（Parallel Computing）、網(wǎng)格計算（Grid Computing）等之后計算模式的最新發(fā)展[1]. 云計算通過將各種互聯(lián)的計算、存儲、數(shù)據(jù)、應(yīng)用等資源進行有效整合來實現(xiàn)多層次的虛擬化與抽象，用戶只需要連接上網(wǎng)絡(luò)即可方便使用云計算強大的計算和存儲能力. 虛擬化技術(shù)是云計算中的關(guān)鍵技術(shù)之一[2]. 通過虛擬化技術(shù)，單個服務(wù)器可以支持多個虛擬機運行多個操作系統(tǒng)和應(yīng)用，從而大大提高服務(wù)器的利用率，通過虛擬化為應(yīng)用提供了靈活多變、可擴展的平臺服務(wù)，用戶租賃滿足其需求的資源，并動態(tài)運行廣泛的應(yīng)用程序，由此可以看出云計算的核心問題是資源管理[3]. 考慮到云計算環(huán)境的動態(tài)性、海量數(shù)據(jù)、異構(gòu)性、任務(wù)規(guī)模大等問題，云計算分布式系統(tǒng)上的資源調(diào)度是 NP-hard 問題. 對于求解計算時間長、復(fù)雜度高的問題，求解的算法主要有群智能優(yōu)化算法. 例如模擬退火算法、遺傳算法、粒子群優(yōu)化算法、蛙跳算法等[4-7]運用在資源調(diào)度問題中取得了較好的效果，由于群智能算法在解決調(diào)度問題上的優(yōu)異表現(xiàn)，因此被日益重視，但這些算法普遍存在對參數(shù)依賴度高、尋優(yōu)效果不理想或者穩(wěn)定性差等問題，且當(dāng)優(yōu)化問題存在大量局部最優(yōu)解或為高維時，容易出現(xiàn)過早收斂. 這就導(dǎo)致隨著云計算調(diào)度任務(wù)規(guī)模的越來越大，這些算法在大規(guī)模任務(wù)調(diào)度問題上整體性能下降，極易陷入“維數(shù)災(zāi)難”.

競爭粒子群算法（Competitive Particle Swarm Optimization，CSO）[8]通過引入成對的競爭機制實現(xiàn)粒子更新，不僅實現(xiàn)簡單，而其在解決高維問題方面性能優(yōu)越，已經(jīng)被應(yīng)用于解決大規(guī)模優(yōu)化問題. 文獻[9]提出利用競爭粒子群算法進行電網(wǎng)調(diào)度，表現(xiàn)出了優(yōu)于同類算法的性能;文獻[10]提出將二進制編碼與競爭粒子群算法結(jié)合來解決電動車充電樁的需求管理問題，改進后的算法展現(xiàn)了在解決大規(guī)模、負載電力系統(tǒng)調(diào)度問題方面的優(yōu)越性能;文獻[11]通過對競爭粒子群優(yōu)化算法的學(xué)習(xí)過程進行簡化，然后將其應(yīng)用于解決燃料電池模型的參數(shù)辨識問題，結(jié)果證明該算法在精度、魯棒性、收斂性方面有很強競爭力.

本文在云計算資源調(diào)度中采用改進的競爭粒子群算法（Improved Competitive Particle Swarm Optimization，ICSO）對資源進行有效分配. 首先通過對任務(wù)完成時間、系統(tǒng)負載均衡度、任務(wù)完成功耗建立約束函數(shù)以兼顧三個目標(biāo)的優(yōu)化. 其次，在初始化操作中引入混沌映射，以改進收斂速度和尋優(yōu)效率;引入自適應(yīng)高斯變異操作對勝利粒子位置進行更新以提高算法搜索精度. 仿真結(jié)果表明，本文算法在任務(wù)完成時間、任務(wù)執(zhí)行功耗以及系統(tǒng)的負載均衡之間取得較好的平衡，提高了在大規(guī)模任務(wù)下的云計算資源的利用率.

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

當(dāng)前云計算系統(tǒng)主要采用Map/Reduce架構(gòu)模式，通過對用戶任務(wù)進行分配來完成任務(wù)調(diào)度. 具體來說，任務(wù)調(diào)度是指在云計算環(huán)境中根據(jù)任務(wù)和資源的實際情況，將任務(wù)分配或遷移到相應(yīng)資源上執(zhí)行的過程[12]，圖1為云計算平臺中任務(wù)調(diào)度的一般過程.? 任務(wù)調(diào)度涉及了優(yōu)先權(quán)、執(zhí)行時間、完成時間、資源利用率、成本、能耗、網(wǎng)絡(luò)吞吐率以及公平性等優(yōu)化參數(shù)和測評指標(biāo)[13]. 任務(wù)調(diào)度策略不僅直接對任務(wù)執(zhí)行時間和成本產(chǎn)生作用，還會影響到整個云計算平臺的性能.

1.1? ?云計算任務(wù)調(diào)度數(shù)學(xué)模型

在云計算資源環(huán)境中，設(shè)資源節(jié)點共有n個，用集合v = {v1，v2，v3，v4，…，vn} 表示，其中vj（1 ≤ j ≤ n）表示第j個虛擬資源節(jié)點，將任務(wù)劃分成m個子任務(wù)，子任務(wù)表示為T = {t1，t2，t3，t4，…，tm}，其中第i個任務(wù)表示為ti（1 ≤ i ≤ m）. 每個子任務(wù)分配到一個虛擬資源節(jié)點運行，子任務(wù)分配到虛擬資源節(jié)點的情況可以用矩陣P表示為：

P = p11? ? p12? ? …? ? p1m

p21? ? p22? ? …? ? p2m

[…]? ? […]? ? ? ? ? ? […]

pn1? ? pn2? ? …? ? pnm? ? ? ?（1）

式中：元素pji代表一個子任務(wù)ti和虛擬資源節(jié)點vj的對應(yīng)關(guān)系. 當(dāng)子任務(wù)ti分配到vj時，pji = 1，反之為0，即pji∈{0，1}. 每個任務(wù)只能分配到某一個虛擬資源節(jié)點上執(zhí)行，所以有：

pji = 1，1 ≤ i ≤ m? ? ? ? ?（2）

考慮到云計算平臺資源的異構(gòu)性，即不同的虛擬節(jié)點所具有的能力側(cè)重點不同，有些節(jié)點資源的運算能力較強而帶寬較小，而有些節(jié)點資源的內(nèi)存較大而計算能力較弱等. 基于以上特性，可以用（VC，VM，VB）表示虛擬機節(jié)點的資源能力，其中 VC 表示 CPU 的運算能力（每秒處理百萬級指令的能力），VM 表示內(nèi)存的大小，VB表示帶寬大小，而子任務(wù)對處理節(jié)點的需求采用P（Ci，Mi，Bi）描述，表示執(zhí)行任務(wù)Pi需要的CPU 處理能力、內(nèi)存及網(wǎng)絡(luò)帶寬.

1.2? ?服務(wù)質(zhì)量模型

服務(wù)質(zhì)量是用來衡量云計算資源調(diào)度中任務(wù)的完成程度的指標(biāo). 由于云計算的任務(wù)調(diào)度是一個多目標(biāo)優(yōu)化問題，綜合評價云計算任務(wù)調(diào)度的優(yōu)良需要從多方面進行考慮，根據(jù)前面對任務(wù)調(diào)度性能指標(biāo)的描述. 首先給出3個優(yōu)化目標(biāo)：任務(wù)完成總用時Tmax、任務(wù)完成功耗E、負載均衡度Bdegree.

對于虛擬機節(jié)點在處理任務(wù)時，它的單個任務(wù)耗時可以表示為：

Tji =? ? ? ? ? ? ?（3）

式中：Li表示完成第i個任務(wù)的長度;VC j為第j個虛擬節(jié)點的CPU處理能力. 第j個虛擬節(jié)點處理任務(wù)總耗時為：

Tj = Tji? ? ? ? ? ? （4）

則任務(wù)總用時Tmax為各虛擬機節(jié)點完成時間中的最大值，即

Tmax = max（pji Tji），1 ≤ j ≤ n? ? ? ? ?（5）

按照目前的研究表明，單位時間能耗和CPU利用率是線性關(guān)系的[13]，結(jié)合能耗的計算公式E = P × T，任務(wù)從t0時刻到t1時刻所產(chǎn)生能耗可以表示為：

E（M） = Pdt? ? ? ? ?（6）

系統(tǒng)完成任務(wù)的總功耗為各節(jié)點功耗總和：

E = E（M）i = kVOC j tji? ? ? ? ?（7）

式中：VOC j為虛擬機節(jié)點j的CPU利用率;tji為虛擬機節(jié)點j執(zhí)行任務(wù)耗時;k為乘法算子. CPU利用率計算方法為：

VOC j =? × 100%? ? ? ? ?（8）

式中：ci、vci分別表示任務(wù)對CPU處理能力的需求以及虛擬機節(jié)點所能提供的CPU運算能力. 同理虛擬機資源j中內(nèi)存的利用率和帶寬利用率可以分別表示為：

VOM j =? × 100%? ? ? ? ?（9）

VOB j =? × 100%? ? ? ? ?（10）

在云計算執(zhí)行任務(wù)過程中，虛擬機的負載主要是由其執(zhí)行的任務(wù)量的大小和自身的計算能力所決定，虛擬機Vj負載情況表示為Vj = {Mj，Cj，Bj}，其中Mj、Cj、Bj分別表示虛擬機Vj上的內(nèi)存利用率、CPU利用率和帶寬利用率. 則虛擬機資源j的利用率為：

VO j = k1

+k2

+k3

×100%

（11）

k1 + k2 + k3 = 1? ? ? ? ? （12）

式中：k1、k2、k3分別為CPU、內(nèi)存、帶寬的權(quán)值. 整個系統(tǒng)的虛擬機資源平均利用率為：

Vavg =? × 100%? ? ? ? ?（13）

以各個虛擬機節(jié)點利用率之間的標(biāo)準(zhǔn)差系數(shù)作為表示集合v = {v1，v2，v3，v4，…，vn}中虛擬機負載情況，則系統(tǒng)的負載均衡度Bdegree可以表示為：

Bdegree =? ? ? ? ? （14）

2? ?任務(wù)調(diào)度策略

2.1? ?競爭粒子群算法

粒子群優(yōu)化算法（Particle Swarm Optimization，PSO）作為最經(jīng)典的群智能算法之一，由于其簡單的實現(xiàn)和快速的收斂性，被廣泛應(yīng)用于求解單目標(biāo)優(yōu)化問題（Single-Objective Optimization Problem，SOP）. 然而，當(dāng)優(yōu)化問題存在大量的局部最優(yōu)解或為高維時，PSO算法性能較差. 競爭群優(yōu)化算法是粒子群優(yōu)化算法的一個變體，Cheng和Jin[8]提出的 CSO算法模擬了生物學(xué)中的優(yōu)勝劣汰的個體競爭機制. 采用競爭機制的優(yōu)化算法比原粒子群優(yōu)化算法能夠更好地平衡收斂性和多樣性. 而且在大規(guī)模優(yōu)化問題上，該算法表現(xiàn)出良好的性能和可拓展性. 該算法假設(shè)種群大小為 M，在解空間內(nèi)隨機地初始化種群. 在每一次迭代過程中首先將種群隨機均分為2組，兩組粒子兩兩進行競爭比較，根據(jù)適應(yīng)值的大小分別為勝利者（Winner）與失敗者（Loser），勝利者將直接進入下一代，失敗者根據(jù)式 （15）和式 （16） 向勝利者學(xué)習(xí)并更新自身位置和速度.

vL（t + 1） = r1（t） × vL + r2（xw（t） - xL（t）） +

φr3（x（t） -? xL（t））? ? ? ? ? ? ? （15）

xL（t + 1） = xL（t） + vL（t + 1）? ? ? ? ? （16）

式中：xw（t）、xL（t）分別表示勝利者和失敗者的位置向量;vL（t + 1）表示失敗者的速度向量;t為迭代次數(shù);r1（t）、r2（t）、r3（t）∈[0，1]D是3個服從均勻分布的隨機向量，與解向量有相同的維數(shù);φ是一個參數(shù)，用于控制x（t）對失敗者位置更新的影響;x（t）有兩種含義，一種表示所有粒子的平均位置，具有全局性;另外一種表示領(lǐng)域內(nèi)粒子的局部平均位置，具有局部性. 在本文中x（t）使用全局平均位置.

2.2? ?改進的競爭粒子群算法

標(biāo)準(zhǔn)的CSO算法具有操作簡單，所需參數(shù)較少，易于實現(xiàn)等優(yōu)點，但由于CSO算法在每次迭代過程中只更新失敗粒子的位置和速度信息，這使得種群多樣性不足，最終導(dǎo)致算法陷入局部最優(yōu)解及“早熟”現(xiàn)象. 因此，為了增強種群的多樣性，平衡種群的探索與開發(fā)，本文借鑒遺傳算法中的變異思想，在CSO算法中引入自適應(yīng)高斯變異，用來對勝利粒子的位置進行更新，同時引入混沌初始化策略對初始種群進行初始化.

2.2.1? ?混沌初始化策略

在標(biāo)準(zhǔn)CSO算法中，種群的初始化是隨機產(chǎn)生的，初始位置的散布程度及其在搜索空間中的位置是否均勻，將直接影響整個搜索過程的收斂速度和算法的尋優(yōu)效率[14-15]. 混沌是一種無規(guī)則的運動狀態(tài)，具有非常強烈的非線性特點，它有規(guī)律性、隨機性和遍歷性等特點，其基本思想是根據(jù)一定規(guī)則把變量從混沌空間映射到求解空間. 本文利用混沌優(yōu)化策略對粒子群進行初始化，Logistic映射具有較均勻的遍歷性分布區(qū)間，能產(chǎn)生分布均勻的混沌序列，有效地保證了種群在解空間中的均勻分布，從而提高算法的搜索效率. 本文選取Logistic映射的方法產(chǎn)生初始混沌序列. 該映射的表達式為：

xn+1 = μxn（1 - xn）? ? ? ? ? ? ? （17）

式中：xn為混沌變量;參數(shù)μ∈（0，4];n為混沌變量序號，n=1，2，3，…，m. 映射圖像如圖2所示，當(dāng)3.569 9 < μ≤4時，系統(tǒng)處于混沌狀態(tài)，在本文中μ取值為4.

本文利用混沌迭代生成初始化粒子群位置，具體步驟如下：

1）對于D維空間中的n個初始粒子位置，首先隨機產(chǎn)生一個D維向量作為第一個混沌向量，即r1∈[0，1]D;

2）將r1的每一維利用式（17）進行n-1次迭代，生成n-1個混沌向量，r2、r3、…、rn;

3）將產(chǎn)生的n個混沌向量按照式（18）映射到解的搜索空間.

xi = xmin + （1 + ri）? ? ? ? ? ? （18）

式中：xmin、xmax分別為搜索空間的上下限;xi即為第i個混沌初始化粒子位置信息.

2.2.2? ?自適應(yīng)高斯變異

由于變異算子在提升算法收斂性能和種群多樣性方面有著顯著表現(xiàn)，文獻[16]將高斯變異引入到PSO算法中以改善粒子在求解過程中的多樣性，提出一種基于高斯變異的多目標(biāo)粒子群優(yōu)化算法. 本文將高斯變異引入CSO算法中對勝利粒子的位置進行更新，變異操作如下：

xt+1 = xt + c × γ，rand（0，1） ≤ Pm

xt+1 = xt，rand（0，1） > Pm? ? ? （19）

式中：c為變異步長;γ為服從高斯分布Gauss（0，1） 的隨機變量;Pm為變異概率. 同時考慮到迭代初期主要發(fā)揮競爭群算法自身的特點，采用較小的變異率，隨著迭代進行，種群多樣性逐漸降低，相應(yīng)地增加了種群的變異概率，因此將變異概率設(shè)定為隨迭代次數(shù)線性遞增，使變異概率自適應(yīng)變化. Pm的計算公式為：

Pm = Pm，min +? ? ? （20）

式中：Pm，min為最小變異率;Pm，max為最大變異率;k為當(dāng)前迭代次數(shù);N為最大迭代次數(shù). 從更新公式可見，隨著迭代次數(shù)的增加，變異概率線性遞增. 因此，引入自適應(yīng)高斯變異后勝利者的更新如式（21）所示.

xw（t + 1） = xw（t） + δ × Gauss（0，1） ×

xw（t） - [x]（t），rand（0，1） ≤ Pm

xw（t + 1） = xw（t），rand（0，1） > Pm? ? （21）

式中：δ為乘法算子;[x]（t）為所有粒子的平均位置，以勝利粒子的當(dāng)前位置和全局粒子的平均位置的差值作為變異步長;rand（0，1） 為服從[0，1]均勻分布的隨機數(shù).

3? ?基于ICSO的云資源調(diào)度算法設(shè)計

3.1? ?粒子編碼與適應(yīng)度函數(shù)設(shè)計

設(shè)任務(wù)數(shù)m，虛擬資源節(jié)點數(shù) n，本研究中每一個粒子代表一種任務(wù)分配方案，假設(shè)粒子所表示的解向量P = { p1，p2，…，pn}，N 表示向量 P 的維數(shù)，Ni 表示向量 P 第 j 維的值，則 Nj = i 表示任務(wù) j 分配到虛擬機 i.

由于本文涉及到多個目標(biāo)的優(yōu)化過程，適應(yīng)度函數(shù)與任務(wù)完成總用時Tmax、任務(wù)完成功耗E、負載均衡度Bdegree 3個目標(biāo)相關(guān)聯(lián)，所以首先需要將多目標(biāo)問題轉(zhuǎn)化為單目標(biāo)問題. 首先將各個優(yōu)化目標(biāo)參數(shù)歸一化，如式（22）所示：

F =? ? ? ? ?（22）

式中：F代表歸一化后的值;f（x）表示當(dāng)前系統(tǒng)中某一個優(yōu)化目標(biāo)參數(shù)大小;f（x）max、 f（x）min分別表示該目標(biāo)參數(shù)的最大值和最小值. 通過對單個優(yōu)化目標(biāo)適應(yīng)度值加權(quán)，將多目標(biāo)優(yōu)化問題轉(zhuǎn)化為單目標(biāo)優(yōu)化問題. 適應(yīng)度函數(shù)可以表示為：

fi = w1FT + w2FE + w3FB? ? ? ? （23）

式中：fi表示第i個粒子的適應(yīng)度值;w1、w2、w3分別表示任務(wù)完成總用時Tmax、任務(wù)完成功耗E、負載均衡度Bdegree 3個目標(biāo)對應(yīng)的權(quán)值，且 w1+w2+w3=1.

3.2? ?改進競爭粒子群算法的任務(wù)調(diào)度

將本文提出的ICSO算法應(yīng)用于云計算資源調(diào)度問題中，調(diào)度算法的具體實現(xiàn)步驟為：

步驟1? ?將云計算任務(wù)調(diào)度方案與ICSO算法中的粒子位置進行一一對應(yīng)，粒子的最佳位置即為最佳任務(wù)調(diào)度方案;

步驟2? ?初始化參數(shù). 給出任務(wù)集數(shù)據(jù)、虛擬機參數(shù)，算法的最大迭代次數(shù)Maxcycle、種群規(guī)模m、變異步長;

步驟3? ?按照公式（17）（18）對粒子群初始位置進行混沌初始化;

步驟4? ?根據(jù)式（23）計算每個粒子的適應(yīng)度值;

步驟5? ?將種群隨機進行兩兩競爭比較，根據(jù)適應(yīng)度值的大小分為勝利者Winner和失敗者Loser;

步驟6? ?根據(jù)式 （15）（16），更新失敗粒子速度以及位置，根據(jù)式 （19）更新勝利粒子的位置和速度. 計算更新粒子的適應(yīng)度值并更新全局最優(yōu)值和最優(yōu)解;

步驟7? ?達到最大迭代次數(shù)的時候，算法結(jié)束，轉(zhuǎn)到步驟8，否則繼續(xù)步驟5;

步驟8? ?得到最優(yōu)粒子位置，即得到最優(yōu)的任務(wù)調(diào)度方案.

4? ?試驗測試和結(jié)果分析

本文采用CloudSim模擬云計算平臺的仿真環(huán)境對算法進行驗證[17-18]，具體的試驗環(huán)境為：Window10操作系統(tǒng)，IntelCoreTM i5-8250U，1.60 GHz CPU，16.00 GB內(nèi)存，CloudSim 4.0. 將本文提出的改進的競爭群算法ICSO與文獻[13]中的競爭群算法以及基本PSO算法和GA算法進行了比較. 各算法試驗參數(shù)設(shè)置如表1所示.

試驗中考慮了資源的處理速度和待處理任務(wù)的長度，設(shè)定兩個任務(wù)集T1、T2，分別設(shè)置任務(wù)數(shù)量為10～100和1 000～5 000，代表小規(guī)模和大規(guī)模兩種任務(wù)規(guī)模情況. 計算節(jié)點數(shù)為10，隨機設(shè)置虛擬節(jié)點的性能，設(shè)置虛擬節(jié)點能力為 [1 000，2 000] mi/s，內(nèi)存為 [512，2 048] MB，帶寬為[5 000，10 000] bit/s，在[500，9 000]間隨機設(shè)置任務(wù)長度，最大迭代次數(shù)為200次，為排除偶然性，每種方法進行10次獨立重復(fù)試驗，并取平均值作為最終的試驗結(jié)果.

為了驗證本文所提調(diào)度模型和算法的有效性，通過改變迭代次數(shù)、任務(wù)數(shù)來比較改進算法和對比算法在各個維度的差別. 首先，分別在大規(guī)模和小規(guī)模兩個任務(wù)集中保證迭代次數(shù)相同的條件下 ，在任務(wù)完成時間、功耗、負載均衡度3方面做出對比. 試驗結(jié)果如圖3～圖8所示.

1）圖3和圖4分別為ICSO算法、CSO算法、GA算法和PSO算法在小規(guī)模和大規(guī)模任務(wù)數(shù)量下的任務(wù)完成時間結(jié)果對比圖. 可以看出，當(dāng)任務(wù)數(shù)量較少時，ICSO算法與試驗對比算法任務(wù)完成時間相差不大. 隨著任務(wù)數(shù)量的增多，CSO和ICSO算法在大規(guī)模任務(wù)下具有明顯的優(yōu)勢，ICSO和CSO算法的任務(wù)完成時間明顯優(yōu)于PSO和GA算法，ICSO算法的任務(wù)完成時間又優(yōu)于基本的CSO算法，說明本文改進的ICSO算法在減少任務(wù)完成時間方面有所提升.

2）圖5和圖6分別為2種任務(wù)集下4種算法的負載均衡度對比圖. 隨著任務(wù)數(shù)量的增多，4種算法的任務(wù)調(diào)度策略的負載均衡度都在上升，但ICSO和CSO算法任務(wù)調(diào)度策略下負載均衡度上升速率明顯小于PSO調(diào)度策略和GA調(diào)度策略;在整個過程中，ICSO調(diào)度算法下的負載均衡度始終低于另外2種算法. 這主要是因為ICSO算法中引入的變異算子提升了種群的多樣性，很好地避免了局部最優(yōu)，使得最后的結(jié)果更好.

3）圖7和圖8為2種任務(wù)集下的4種調(diào)度策略的任務(wù)完成功耗對比圖. 從圖中可以看出，在任務(wù)數(shù)量較少時，ICSO、CSO算法和PSO算法以及GA算法完成的云計算資源調(diào)度在任務(wù)完成功耗上差別不大，但隨著任務(wù)數(shù)量的增多，CSO和ICSO算法在大規(guī)模任務(wù)下的優(yōu)越性得到了體現(xiàn)，PSO算法下的調(diào)度策略功耗明顯高于CSO和ICSO算法下的調(diào)度策略，而ICSO算法的功耗又略低于CSO算法的功耗，這說明改進的算法在降低任務(wù)完成功耗方面也有所提升.

從迭代次數(shù)的角度進行對比，將任務(wù)數(shù)設(shè)置為3 000，比較迭代次數(shù)對最優(yōu)適應(yīng)度值的影響. 結(jié)果如圖9所示.

由圖9可知，在初始階段CSO算法和改進的ICSO算法收斂速度要高于PSO算法和GA算法，在迭代40次前，各算法所得適應(yīng)度值差別并不明顯，這時CSO算法略優(yōu)于其他3種對比算法;隨著迭代次數(shù)增至60以上，CSO算法和ICSO算法所求結(jié)果明顯好于PSO算法和GA算法，且兩種算法在80次開始逐漸趨于穩(wěn)定，而PSO算法在120次以后才開始趨于穩(wěn)定. 在收斂速度方面，CSO算法略微好于ICSO算法，這主要是由于引入的變異操作在一定程度上降低了算法的收斂速度;從求解精度上可以看到，ICSO算法能夠跳出局部最優(yōu)解，實現(xiàn)更好的求解精度，算法結(jié)果表現(xiàn)更加優(yōu)秀.

5? ?結(jié)? ?論

針對大規(guī)模云計算資源調(diào)度中算法求解精度不高，易陷入局部最優(yōu)等問題，本文提出改進的競爭粒子群優(yōu)化算法來求解云計算資源調(diào)度問題. 相較于標(biāo)準(zhǔn)的競爭粒子群算法，該算法利用混沌理論產(chǎn)生初始化種群，使得初始化粒子在解空間中均勻分布;在粒子搜索過程中引入自適應(yīng)變異概率的高斯變異來進行勝利粒子的更新，提升了種群多樣性和算法的全局搜索能力. 在CloudSim仿真環(huán)境下，分別從不同任務(wù)規(guī)模下的求解精度與相同任務(wù)規(guī)模下的收斂速度兩方面進行試驗. 仿真結(jié)果表明，本文提出的多目標(biāo)綜合評價模型兼顧了云計算任務(wù)的完成時間、功耗以及負載均衡度，能搜索到最佳調(diào)度方案，可很好地應(yīng)用于大規(guī)模云計算環(huán)境下的資源調(diào)度問題.

參考文獻

[1]? ? THAIN D，TANNENBAUM T，LIVNY M. Distributed computing in practice：the Condor experience[J]. Concurrency and Computation：Practice and Experience，2005，17（2/3/4）：323—356.

[2]? ? MISHRA B，PANDEY D R. Different approaches of virtualization in cloud computing[J]. International Journal of Scientific Research，2017，5（11）：221—227.

[3]? ? TOPCUOGLU H，HARIRI S，WU M Y. Performance-effective and low-complexity task scheduling for heterogeneous computing[J]. IEEE Transactions on Parallel and Distributed Systems，2002，13（3）：260—274.

[4]? ? ABDULLAH M，OTHMAN M. Simulated annealing approach to cost-based multi-QoS job scheduling in cloud computing enviroment[J]. American Journal of Applied Sciences，2014，11（6）：872—877.

[5]? ? SAFWAT A，F(xiàn)ATMA A. Genetic-based task scheduling algorithm in cloud computing environment[J]. International Journal of Advanced Computer Science and Applications，2016，7（4）：550—556.

[6]? ? 胡志剛，常健，周舟. 面向云環(huán)境中任務(wù)負載的粒子群優(yōu)化調(diào)度策略[J]. 湖南大學(xué)學(xué)報（自然科學(xué)版），2019，46（8）：117—123.

HU Z G，CHANG J，ZHOU Z. PSO scheduling strategy for task load in cloud computing[J]. Journal of Hunan University（Natural Sciences），2019，46（8）：117—123. （In Chinese）

[7]? ? DENG Y，CHENG X H. A heterogeneous multiprocessor task scheduling algorithm based on SFLA[C]//World Automation Congress. Guilin：IEEE，2016：1—5.

[8]? ? CHENG R，JIN Y C. A competitive swarm optimizer for large scale optimization[J]. IEEE Transactions on Cybernetics，2015，45（2）：191—204.

[9]? ? WANG Y，YANG Z L，GUO Y J，et al. A novel binary competitive swarm optimizer for power system unit commitment[J]. Applied Sciences，2019，9（9）：1776.

[10]? WANG Y，YANG Z L，MOURSHED M，et al. Demand side management of plug-in electric vehicles and coordinated unit commitment：a novel parallel competitive swarm optimization method[J]. Energy Conversion and Management，2019，196：935—949.

[11]? XIONG G J，ZHANG J，SHI D Y，et al. A simplified competitive swarm optimizer for parameter identification of solid oxide fuel cells[J]. Energy Conversion and Management，2020，203：112—114.

[12]? 馬小晉，饒國賓，許華虎. 云計算中任務(wù)調(diào)度研究的調(diào)查[J]. 計算機科學(xué)，2019，46（3）：1—8.

MA X J，RAO G B，XU H H. Research on task scheduling in cloud computing[J]. Computer Science，2019，46（3）：1—8. （In Chinese）

[13]? AKHTER N，OTHMAN M. Energy aware resource allocation of cloud data center：review and open issues[J]. Cluster Computing，2016，19（3）：1163—1182.

[14]? 程澤，董夢男，楊添剴，等. 基于自適應(yīng)混沌粒子群算法的光伏電池模型參數(shù)辨識[J]. 電工技術(shù)學(xué)報，2014，29（9）：245—252.

CHENG Z，DONG M N，YANG T K，et al. Extraction of solar cell model parameters based on self-adaptive chaos particle swarm optimization algorithm[J]. Transactions of China Electrotechnical Society，2014，29（9）：245—252. （In Chinese）

[15]? TAN W A，ZHAO Y. Web service composition based on chaos genetic algorithm[J]. Computer Integrated Manufacturing Systems，2018，24（7）：1822—1829.

[16]? HU M，WU T，WEIR J D. An adaptive particle swarm optimization with multiple adaptive methods[J]. IEEE Transactions on Evolutionary Computation，2013，17 （5）：705—720.

[17]? 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 and Experience，2011，41（1）：23—50.

[18]? XU B，PENG Z P，XIAO F X，et al. Dynamic deployment of virtual machines in cloud computing using multi-objective optimization[J]. Soft Computing，2015，19（8）：2265—2273.