李信誠，徐壽偉，王重洋

（山東科技大學(xué)計算機(jī)科學(xué)與工程學(xué)院，山東青島 266590）

0 引言

云計算是分布式計算的一種形式，給不同需求的云用戶提供服務(wù)。通過互聯(lián)網(wǎng)將用戶提交的云任務(wù)發(fā)送給服務(wù)器，并在處理器的調(diào)度處理下將結(jié)果返回給云用戶。隨著云計算的發(fā)展，人們對于其安全性、能耗、資源管理、調(diào)度等問題進(jìn)行了全方位研究。任務(wù)調(diào)度一直是云計算研究的熱點話題，如何提高云環(huán)境下任務(wù)調(diào)度的效率，減小運(yùn)行成本開銷具有重要的研究價值。云計算管理各種虛擬化資源，使得調(diào)度成為一個關(guān)鍵組成部分，任務(wù)調(diào)度背后的基本思想是使任務(wù)最大限度地減少執(zhí)行時間并且提高算法性能。為了在云環(huán)境中有效執(zhí)行各類云任務(wù)，需要適當(dāng)?shù)娜蝿?wù)調(diào)度策略。

隨著用戶數(shù)量的增加，云計算任務(wù)隊列中的任務(wù)數(shù)量加劇，大幅度增加了云計算數(shù)據(jù)中心的能耗和成本；另外，在云任務(wù)提交給云服務(wù)器進(jìn)行處理時，有效的任務(wù)調(diào)度算法決定云服務(wù)器的工作效率、負(fù)載均衡等。因此，為了使云服務(wù)器更好地處理用戶需求、提高調(diào)度能力，在云環(huán)境中提供具有成本效益的執(zhí)行算法，采取適當(dāng)?shù)娜蝿?wù)調(diào)度策略是必要的。在云環(huán)境中如何對任務(wù)進(jìn)行高效合理調(diào)度從實現(xiàn)系統(tǒng)全局最優(yōu)化，是云計算研究的重點和難點。

1 相關(guān)工作

在云計算環(huán)境中，任務(wù)調(diào)度是一個NP難點問題。任務(wù)調(diào)度算法研究較多：文獻(xiàn)［5］提出資源按需供應(yīng)是云計算任務(wù)調(diào)度過程的主要目標(biāo)之一，任務(wù)調(diào)度負(fù)責(zé)提高資源利用率和性能、縮短響應(yīng)時間并保持整個系統(tǒng)平衡的方式，將任務(wù)分配給虛擬機(jī)執(zhí)行。不同的任務(wù)調(diào)度順序?qū)φ{(diào)度性能影響很大，確定最適合任務(wù)的虛擬機(jī)（Virtual Machine，VM）類型集和最佳任務(wù)調(diào)度順序并不容易。Domanal等改進(jìn)PSO和CSO算法，提出一種新的任務(wù)調(diào)度和資源管理混合算法，提高了云資源利用率，降低了平均響應(yīng)時間；Kumar等設(shè)計了一個具有選擇最優(yōu)資源決策能力的任務(wù)處理框架并提出一種粒子群優(yōu)化算法，在用戶定義的期限內(nèi)處理虛擬機(jī)上的應(yīng)用程序，改進(jìn)了任務(wù)調(diào)度的時間、成本及吞吐量；Huang等提出一種任務(wù)調(diào)度器，將具有粒子群優(yōu)化算法的幾個離散變體用于云計算中的任務(wù)調(diào)度，實驗結(jié)果證明了該方法的效率和有效性；蝙蝠算法很少應(yīng)用于資源調(diào)度過程中，Pei等提出了混合蝙蝠和變量鄰域搜索的算法來解決所研究的問題，并在其編碼過程中實現(xiàn)了最優(yōu)調(diào)度規(guī)則；Liu提出一種改進(jìn)的蝙蝠算法，結(jié)合膜計算方式在CloudSim軟件搭建仿真環(huán)境進(jìn)行仿真實驗，得到良好的收斂穩(wěn)定性與精確性。

任務(wù)調(diào)度是一個NP-hard問題，需要使用啟發(fā)式算法如粒子群優(yōu)化（Particle Swarm Optimization，PSO）算法、蝙蝠優(yōu)化算法（Bat Algorithm，BA）等來解決問題，為應(yīng)用程序提供高效的調(diào)度算法非常重要，但以上方法都未在搜索精度和收斂速度等方面進(jìn)行改進(jìn)。本文提出混沌擾動的線性遞減慣性權(quán)重值的混合BA-PSO算法（簡稱為

w

_BAPSO算法），結(jié)合帶有混沌擾動的線性遞減慣性權(quán)重值

w

改進(jìn)了PSO算法容易陷入局部最優(yōu)和BA算法收斂速度較慢的缺點，提高了任務(wù)調(diào)度的資源利用率，減少了成本和時間開銷。

2 w w_BAPSO算法模型

為減少任務(wù)調(diào)度的時間和成本，提高調(diào)度算法的收斂速度和搜索精度，本文提出一種基于混沌擾動的線性遞減慣性權(quán)重參數(shù)。結(jié)合蝙蝠算法和粒子群算法，克服了粒子群算法搜索精度低和蝙蝠算法收斂速度慢的缺點，有效提高了算法的收斂速度和搜索精度。

2.1 任務(wù)調(diào)度模型

云計算中分布有大量的資源和數(shù)據(jù)，具有資源差異性、異構(gòu)性、動態(tài)性等特點，進(jìn)行資源調(diào)度的目標(biāo)是減少運(yùn)行時間和成本，提高資源利用率。本文使用Fard等提出的云計算資源架構(gòu)，底部到頂部為資源層、平臺層和應(yīng)用程序?qū)樱Y源層中分布有虛擬資源和物理資源。任務(wù)調(diào)度模型如圖1所示。

Fig.1 Schematic diagram of task scheduling model圖1 任務(wù)調(diào)度模型

應(yīng)用程序?qū)邮沁B接用戶和云計算平臺的載體，通過互聯(lián)網(wǎng)將用戶與云服務(wù)器進(jìn)行互聯(lián)。云用戶在應(yīng)用程序?qū)赢a(chǎn)生服務(wù)需求，提交云任務(wù)請求后生成云任務(wù)列表。在云任務(wù)列表中，將任務(wù)分為較小的子任務(wù)提交給平臺層。平臺層提供開發(fā)、測試、部署軟件以及管理功能，在平臺層中主要分布有云服務(wù)調(diào)度服務(wù)器、資源管理模塊以及任務(wù)調(diào)度模塊。當(dāng)云任務(wù)列表到達(dá)云服務(wù)調(diào)度服務(wù)器后，通過資源管理模塊分配相應(yīng)的資源用以執(zhí)行，通過任務(wù)調(diào)度模塊執(zhí)行任務(wù)調(diào)度算法。在云計算服務(wù)器的處理下，經(jīng)過合理的調(diào)度算法和調(diào)度策略將云任務(wù)分配到資源層。資源層提供基礎(chǔ)設(shè)施，是平臺層和應(yīng)用層進(jìn)行任務(wù)調(diào)度及資源處理的基礎(chǔ)。資源層包括物理資源和虛擬資源。物理資源就是分布在不同空間的物理機(jī)、服務(wù)器等硬件設(shè)施；虛擬資源由虛擬化技術(shù)形成的資源池組成。在資源層中，分布有大量的物理機(jī)和虛擬機(jī)，云任務(wù)被分配到對應(yīng)的虛擬機(jī)上執(zhí)行，消耗物理資源并將結(jié)果返回給平臺層中的云服務(wù)器，最終將任務(wù)執(zhí)行結(jié)果反饋給應(yīng)用程序?qū)?，用戶得到任?wù)執(zhí)行結(jié)果。

2.2 w_BAPSO算法

在粒子群迭代過程中，使用式（1）、式（2）對速度和位置進(jìn)行更新：

其中，

w

為慣性權(quán)重，表示粒子繼承當(dāng)前速度的程度；

c

、

c

是學(xué)習(xí)因子，

c

表示“自我認(rèn)知”，代表粒子自我學(xué)習(xí)的能力，

c

表示“社會認(rèn)知”，代表粒子向全局最優(yōu)學(xué)習(xí)的能力，

c

、

c

∈[0，2]，通常情況下

c

=

c

=2；

r

和

r

是分布在［0，1］之間的隨機(jī)數(shù)。在

w

_BAPSO算法的迭代過程中，加入帶有l(wèi)ogistics混沌擾動的線性遞減的慣性權(quán)重參數(shù)。在粒子群算法迭代初期，較大的慣性權(quán)重有助于全局搜索，避免陷入局部最優(yōu)。在粒子群算法迭代后期，較小的慣性權(quán)重有助于局部搜索，在局部中搜索出全局最優(yōu)解。為了更好地平衡算法的全局搜索以及局部搜索能力，Shi提出了線性遞減慣性權(quán)重策略：

其中，

w

是第t次迭代中慣性權(quán)重的值，

w

是慣性權(quán)重的最大值，

w

是慣性權(quán)重的最小值，

iter

是當(dāng)前的迭代次數(shù)，

T

是迭代總次數(shù)，慣性權(quán)重隨迭代次數(shù)線性遞減。在非線性遞減的慣性權(quán)重基礎(chǔ)上，添加一個Logistics混沌擾動項

At

∈[0，0.1]，其公式如下：

其中

μ

為控制參量，當(dāng)

μ

=4，0≤

At

≤1時，Logistics處于完全混沌狀態(tài)，可以利用其混沌特性進(jìn)行迭代搜索。

增添擾動項非線性遞減的慣性權(quán)重具有隨機(jī)性，有效改進(jìn)了粒子群的搜索能力和搜索范圍。通過引入Logistics混沌擾動項產(chǎn)生混沌變量，在每一次迭代過程中對當(dāng)前的速度公式進(jìn)行擾動，提高了算法跳出局部最優(yōu)解的處理能力。

蝙蝠算法是一種新型的群體智能優(yōu)化算法，每個蝙蝠個體有相應(yīng)的適應(yīng)度，蝙蝠群通過調(diào)整頻率、脈沖發(fā)射率和響度，在解空間中搜素最優(yōu)蝙蝠個體。蝙蝠脈沖的響度

A

(

i

)和脈沖速率

R

(

i

)隨著迭代過程不斷更新，脈沖響度從最大值不斷減小，同時脈沖速率從初始值開始逐漸增大。

在此基礎(chǔ)上，結(jié)合BA算法對PSO算法進(jìn)行改進(jìn)。

然后判斷脈沖速率

R

(

i

)和隨機(jī)數(shù)

Rand

(0，1)的大小。（1）若

Rand

(0，1)＞

R

，則從當(dāng)前解附近形成一個局部解，使用式（9）生成當(dāng)前位置，產(chǎn)生一個局部新解。此過程可以克服粒子群算法陷入局部最優(yōu)的缺陷，產(chǎn)生隨機(jī)解便于粒子擴(kuò)大搜索范圍，更好地搜索全局最優(yōu)解。

（2）若

Rand

(0，1)＜

R

且此時粒子的適應(yīng)度值小于最佳位置的適應(yīng)度值，則保留當(dāng)前位置，使用式（10）更新粒子的位置，并使用式（6）、式（7）增大

R

，縮小

A

，重新排序，找到最優(yōu)解

gbest。

（3）否則使用式（11）更新其位置：

本文提出的

w

_BAPSO算法流程如圖2所示。

Fig.2 Flow of w_BAPSO algorithm圖2 w_BAPSO算法流程

3 應(yīng)用實驗

采用Cloudsim仿真平臺，將

w

_BAPSO算法在云計算任務(wù)調(diào)度中進(jìn)行仿真實驗驗證，通過設(shè)置不同規(guī)模任務(wù)數(shù)量對實驗結(jié)果進(jìn)行比較。實驗結(jié)果表明本文提出的

w

_BAPSO算法在云計算任務(wù)調(diào)度中有較好性能，提高了收斂速度，減少了任務(wù)調(diào)度過程中的時間和成本。

3.1 w_BAPSO算法的適應(yīng)度函數(shù)

任務(wù)

i

在虛擬機(jī)

j

上的執(zhí)行時間用

ETC

(

i

，

j

)表示，

ETC

(

i

，

j

)的計算公式如式（12）所示，其中

task_length

表示任務(wù)

i

的長度，

vm_cpu

表示虛擬機(jī)

j

的運(yùn)行速度。

任務(wù)調(diào)度過程的總執(zhí)行時間計算如式（13）、式（14）所示：

其中，

x

表示任務(wù)

task

與虛擬機(jī)

vm

的分配關(guān)系。當(dāng)

x

=1時，表示任務(wù)

task

在虛擬機(jī)

vm

上執(zhí)行，否則

x

=0。

Time

（

j

）表示虛擬機(jī)

j

的運(yùn)行時間。最大完成時間

Makespan

計算如下：

使用Cost(

i

，

j

)表示云任務(wù)

i

在虛擬機(jī)

j

上運(yùn)行的成本，Cost(

i

，

j

)的計算公式如下：

其中，

P

、

P

、

P

分別表示虛擬機(jī)內(nèi)存外存、帶寬的運(yùn)行成本。使用

total Cost

表示所有虛擬機(jī)的運(yùn)行總成本：

本文的適應(yīng)度函數(shù)使用多目標(biāo)優(yōu)化方案，使用

total-Time、Makespan、total Cost

設(shè)計目標(biāo)函數(shù)，并對目標(biāo)函數(shù)按照式（18）-（20）進(jìn)行歸一化處理：

3.2 實驗環(huán)境及算法參數(shù)設(shè)置

本文使用計算機(jī)仿真通用平臺CloudSim進(jìn)行實驗驗證。CloudSim是澳大利亞墨爾本大學(xué)和Gridbus項目組共同推出的云計算仿真軟件，本實驗采用CloudSim 3.0版本。計算機(jī)采用Windows10操作系統(tǒng)，8GB內(nèi)存，Core i7處理器。將本文提出的算法分別與標(biāo)準(zhǔn)粒子群優(yōu)化（PSO）算法、改進(jìn)后的粒子群優(yōu)化算法（AIW-PSO）、標(biāo)準(zhǔn)蝙蝠算法（BA）進(jìn)行對比實驗。為進(jìn)一步比較本文提出算法的性能，設(shè)置云任務(wù)數(shù)量分別為50、200，對比指標(biāo)為算法的適應(yīng)度值、收斂情況、最大完成時間Makespan、任務(wù)平均完成時間及任務(wù)平均成本。

CloudSim平臺中虛擬機(jī)、主機(jī)、任務(wù)的參數(shù)設(shè)置如表1所示。

Table1 Parameter settings表1 參數(shù)設(shè)置

3.3 實驗結(jié)果對比

設(shè)置兩組數(shù)據(jù)進(jìn)行對比實驗，當(dāng)云任務(wù)數(shù)量為50和200時，測試

w

_BAPSO算法在云計算資源調(diào)度中的性能，分別比較兩種任務(wù)規(guī)模下4種算法的收斂速度、執(zhí)行云任務(wù)的平均成本、平均時間以及虛擬機(jī)的最大完成時間。任務(wù)調(diào)度在云計算中的收斂情況如圖3所示，不同規(guī)模任務(wù)級條件下算法的收斂情況有所不同。由圖3可知，當(dāng)任務(wù)規(guī)模較小時，本文提出的

w

_BAPSO算法在80次迭代時收斂，產(chǎn)生最小的適應(yīng)度值，約為0.31，而其他幾個算法收斂程度較為緩慢，且具有陷入局部最優(yōu)的過程，一直處于不斷迭代中，其中PSO表現(xiàn)出的性能最差，收斂精度較低。當(dāng)任務(wù)規(guī)模較大時，

w

_BAPSO和AIW_PSO算法都表現(xiàn)出較好的性能，但

w

_BAPSO算法收斂速度更快，尋優(yōu)能力更強(qiáng)；而PSO和BA算法在迭代后期仍未找到全局最優(yōu)解，收斂效果較差。因此，本文提出的

w

_BAPSO算法應(yīng)用于云計算任務(wù)調(diào)度過程中，具有較快的收斂速度和搜索精度。

Fig.3 Convergence of the algorithm under different number of tasks圖3 不同任務(wù)數(shù)量下算法的收斂情況

4種算法在不同任務(wù)規(guī)模下的最大完成時間如圖4所示。當(dāng)任務(wù)規(guī)模較大時，最大完成時間

Makespan

都有不同程度的提高。從圖中可以看出，不論任務(wù)規(guī)模大小，

w

_BAPSO算法的

Makespan

都處于較小值，因此可以得出

w

_BAPSO算法在執(zhí)行任務(wù)調(diào)度過程中最大完成時間較小，有效提高了虛擬機(jī)的利用率和任務(wù)調(diào)度性能。

Fig.4 Makespan of the algorithm under different number of tasks圖4 不同任務(wù)數(shù)量下算法的最大完成時間

4種算法在不同任務(wù)規(guī)模下的平均完成時間如圖5所示。從圖中可以看出，當(dāng)任務(wù)規(guī)模較小時，4種算法的任務(wù)平均完成時間較為一致，但

w

_BAPSO算法的任務(wù)平均完成時間較小，為226ms；當(dāng)任務(wù)規(guī)模較大時，任務(wù)的平均完成時間差異比較明顯，但

w

_BAPSO算法依舊有著最少的時間，為1 026ms。也就是說，在不同規(guī)模的任務(wù)調(diào)度過程中，

w

_BAPSO算法的調(diào)度時間最小，耗時最短，能以較快的速度收斂到全局最優(yōu)值，產(chǎn)生最佳調(diào)度方案。不同任務(wù)規(guī)模下幾種算法進(jìn)行任務(wù)調(diào)度的成本如圖6所示。當(dāng)任務(wù)規(guī)模為50時，4種算法都維持在較小成本；當(dāng)任務(wù)規(guī)模增大時，PSO算法成本較大，

w

_BAPSO算法成本相對較小。因此，本文提出的

w

_BAPSO算法在解決任務(wù)調(diào)度問題中具有較小的成本。

Fig.5 Averagecompletion timeof thealgorithm under different number of tasks圖5 不同任務(wù)數(shù)量下算法的平均完成時間

Fig.6 Averagecost of thealgorithm under different number of tasks圖6 不同任務(wù)數(shù)量下算法的平均花費

4 結(jié)語

為克服粒子群算法和蝙蝠算法缺點，本文提出了混沌擾動

w

_BAPSO算法，將其用于云計算任務(wù)調(diào)度過程，有效避免了粒子群算法陷入局部最優(yōu)和蝙蝠算法收斂速度慢的缺陷。實驗結(jié)果證明，

w

_BAPSO算法具有收斂速度快且搜索精度高的優(yōu)點，調(diào)度成本小，最大完成時間短。后續(xù)研究工作中要進(jìn)一步改善算法的收斂速度和尋優(yōu)精度，更好地適應(yīng)大規(guī)模云計算任務(wù)調(diào)度。