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

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

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

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

中圖分類號(hào)：TP301? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? 文獻(xiàn)標(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

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

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

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

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

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

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

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

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

p21? ? p22? ? …? ? p2m

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

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

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

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

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

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

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

對(duì)于虛擬機(jī)節(jié)點(diǎn)在處理任務(wù)時(shí)，它的單個(gè)任務(wù)耗時(shí)可以表示為：

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

VO j = k1

+k2

+k3

×100%

（11）

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

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

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

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

Bdegree =? ? ? ? ? （14）

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

2.1? ?競爭粒子群算法

粒子群優(yōu)化算法（Particle Swarm Optimization，PSO）作為最經(jīng)典的群智能算法之一，由于其簡單的實(shí)現(xiàn)和快速的收斂性，被廣泛應(yīng)用于求解單目標(biāo)優(yōu)化問題（Single-Objective Optimization Problem，SOP）. 然而，當(dāng)優(yōu)化問題存在大量的局部最優(yōu)解或?yàn)楦呔S時(shí)，PSO算法性能較差. 競爭群優(yōu)化算法是粒子群優(yōu)化算法的一個(gè)變體，Cheng和Jin[8]提出的 CSO算法模擬了生物學(xué)中的優(yōu)勝劣汰的個(gè)體競爭機(jī)制. 采用競爭機(jī)制的優(yōu)化算法比原粒子群優(yōu)化算法能夠更好地平衡收斂性和多樣性. 而且在大規(guī)模優(yōu)化問題上，該算法表現(xiàn)出良好的性能和可拓展性. 該算法假設(shè)種群大小為 M，在解空間內(nèi)隨機(jī)地初始化種群. 在每一次迭代過程中首先將種群隨機(jī)均分為2組，兩組粒子兩兩進(jìn)行競爭比較，根據(jù)適應(yīng)值的大小分別為勝利者（Winner）與失敗者（Loser），勝利者將直接進(jìn)入下一代，失敗者根據(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個(gè)服從均勻分布的隨機(jī)向量，與解向量有相同的維數(shù);φ是一個(gè)參數(shù)，用于控制x（t）對(duì)失敗者位置更新的影響;x（t）有兩種含義，一種表示所有粒子的平均位置，具有全局性;另外一種表示領(lǐng)域內(nèi)粒子的局部平均位置，具有局部性. 在本文中x（t）使用全局平均位置.

2.2? ?改進(jìn)的競爭粒子群算法

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

2.2.1? ?混沌初始化策略

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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]均勻分布的隨機(jī)數(shù).

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

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

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

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

F =? ? ? ? ?（22）

式中：F代表歸一化后的值;f（x）表示當(dāng)前系統(tǒng)中某一個(gè)優(yōu)化目標(biāo)參數(shù)大小;f（x）max、 f（x）min分別表示該目標(biāo)參數(shù)的最大值和最小值. 通過對(duì)單個(gè)優(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個(gè)粒子的適應(yīng)度值;w1、w2、w3分別表示任務(wù)完成總用時(shí)Tmax、任務(wù)完成功耗E、負(fù)載均衡度Bdegree 3個(gè)目標(biāo)對(duì)應(yīng)的權(quán)值，且 w1+w2+w3=1.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

5? ?結(jié)? ?論

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

參考文獻(xiàn)

[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ù)負(fù)載的粒子群優(yōu)化調(diào)度策略[J]. 湖南大學(xué)學(xué)報(bào)（自然科學(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]? 馬小晉，饒國賓，許華虎. 云計(jì)算中任務(wù)調(diào)度研究的調(diào)查[J]. 計(jì)算機(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]? 程澤，董夢(mèng)男，楊添剴，等. 基于自適應(yīng)混沌粒子群算法的光伏電池模型參數(shù)辨識(shí)[J]. 電工技術(shù)學(xué)報(bào)，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.