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

李信誠，徐壽偉，王重洋

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

0 引言

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

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

1 相關工作

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

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

w

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

w

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

2 w w_BAPSO算法模型

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

2.1 任務調度模型

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

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

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

2.2 w_BAPSO算法

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

其中，

w

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

c

、

c

是學習因子，

c

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

c

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

c

、

c

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

c

=

c

=2；

r

和

r

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

w

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

其中，

w

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

w

是慣性權重的最大值，

w

是慣性權重的最小值，

iter

是當前的迭代次數，

T

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

At

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

其中

μ

為控制參量，當

μ

=4，0≤

At

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

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

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

A

(

i

)和脈沖速率

R

(

i

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

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

然后判斷脈沖速率

R

(

i

)和隨機數

Rand

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

Rand

(0，1)＞

R

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

（2）若

Rand

(0，1)＜

R

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

R

，縮小

A

，重新排序，找到最優解

gbest。

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

本文提出的

w

_BAPSO算法流程如圖2所示。

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

3 應用實驗

采用Cloudsim仿真平臺，將

w

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

w

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

3.1 w_BAPSO算法的適應度函數

任務

i

在虛擬機

j

上的執行時間用

ETC

(

i

，

j

)表示，

ETC

(

i

，

j

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

task_length

表示任務

i

的長度，

vm_cpu

表示虛擬機

j

的運行速度。

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

其中，

x

表示任務

task

與虛擬機

vm

的分配關系。當

x

=1時，表示任務

task

在虛擬機

vm

上執行，否則

x

=0。

Time

（

j

）表示虛擬機

j

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

Makespan

計算如下：

使用Cost(

i

，

j

)表示云任務

i

在虛擬機

j

上運行的成本，Cost(

i

，

j

)的計算公式如下：

其中，

P

、

P

、

P

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

total Cost

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

本文的適應度函數使用多目標優化方案，使用

total-Time、Makespan、total Cost

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

3.2 實驗環境及算法參數設置

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

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

Table1 Parameter settings表1 參數設置

3.3 實驗結果對比

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

w

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

w

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

w

_BAPSO和AIW_PSO算法都表現出較好的性能，但

w

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

w

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

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

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

Makespan

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

w

_BAPSO算法的

Makespan

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

w

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

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

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

w

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

w

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

w

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

w

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

w

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

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

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

4 結語

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

w

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

w

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