混沌擾動w_BAPSO算法在任務調度中的應用

李信誠，徐壽偉，王重洋

（山東科技大學計算機科學與工程學院，山東青島 266590）

0 引言

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

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

1 相關工作

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

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

w

_BAPSO算法），結合帶有混沌擾動的線性遞減慣性權重值

w

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

2 w w_BAPSO算法模型

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

2.1 任務調度模型

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

Fig.1 Schematic diagram of task scheduling model圖1 任務調度模型

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

2.2 w_BAPSO算法

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

其中，

w

為慣性權重，表示粒子繼承當前速度的程度；

c

、

c

是學習因子，

c

表示“自我認知”，代表粒子自我學習的能力，

c

表示“社會認知”，代表粒子向全局最優(yōu)學習的能力，

c

、

c

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

c

=

c

=2；

r

和

r

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

w

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

其中，

w

是第t次迭代中慣性權重的值，

w

是慣性權重的最大值，

w

是慣性權重的最小值，

iter

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

T

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

At

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

其中

μ

為控制參量，當

μ

=4，0≤

At

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

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

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

A

(

i

)和脈沖速率

R

(

i

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

在此基礎上，結合BA算法對PSO算法進行改進。

然后判斷脈沖速率

R

(

i

)和隨機數(shù)

Rand

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

Rand

(0，1)＞

R

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

（2）若

Rand

(0，1)＜

R

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

R

，縮小

A

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

gbest。

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

本文提出的

w

_BAPSO算法流程如圖2所示。

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

3 應用實驗

采用Cloudsim仿真平臺，將

w

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

w

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

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

任務

i

在虛擬機

j

上的執(zhí)行時間用

ETC

(

i

，

j

)表示，

ETC

(

i

，

j

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

task_length

表示任務

i

的長度，

vm_cpu

表示虛擬機

j

的運行速度。

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

其中，

x

表示任務

task

與虛擬機

vm

的分配關系。當

x

=1時，表示任務

task

在虛擬機

vm

上執(zhí)行，否則

x

=0。

Time

（

j

）表示虛擬機

j

的運行時間。最大完成時間

Makespan

計算如下：

使用Cost(

i

，

j

)表示云任務

i

在虛擬機

j

上運行的成本，Cost(

i

，

j

)的計算公式如下：

其中，

P

、

P

、

P

分別表示虛擬機內存外存、帶寬的運行成本。使用

total Cost

表示所有虛擬機的運行總成本：

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

total-Time、Makespan、total Cost

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

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

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

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

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

3.3 實驗結果對比

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

w

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

w

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

w

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

w

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

w

_BAPSO算法應用于云計算任務調度過程中，具有較快的收斂速度和搜索精度。

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

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

Makespan

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

w

_BAPSO算法的

Makespan

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

w

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

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

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

w

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

w

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

w

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

w

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

w

_BAPSO算法在解決任務調度問題中具有較小的成本。

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

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

4 結語

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

w

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

w

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