基于人工蜂群的云計算負載均衡算法

賈 嘉,慕德俊

(1.西北工業(yè)大學自動化學院，西安 710072;2.西北工業(yè)大學網(wǎng)絡空間安全學院，西安 710072)

云計算將所有的計算資源及計算任務都托管在云上，通過互聯(lián)網(wǎng)向用戶提供計算服務。云計算環(huán)境中的處理單元被稱為虛擬機(virtual machine,VM),調度器負責檢查虛擬機是否計算負載過高或過低,或者是否有任務閑置[1]，并通過任務的遷移使得各個虛擬機上的計算負載盡可能平均。負載均衡是云計算的主要問題之一，目前已有大量用于尋求負載均衡的算法。云計算負載平衡算法可分為三大類別：通用負載均衡算法、基于體系結構的負載均衡算法、基于人工智能的負載均衡算法。

通用負載均衡算法在不考慮具體的云計算體系結構的前提下，提出適用面較廣的算法。此類算法類似計算機操作系統(tǒng)中的資源分配與調度方法，例如：輪詢、先到先服務、最短服務時間方法等。文獻[2]提出了加權的輪詢算法(weighted round-bin)、最短期望延遲算法(shortest expected delay) 等經(jīng)典的通用算法，并對比了其性能。Gupta等[3]根據(jù)虛擬機每秒鐘執(zhí)行的機器指令數(shù)(machine instruction per second,MIPS)和故障率兩個指標設計了負載均衡算法。文獻[4]將云系統(tǒng)中的處理器核作為計算資源調度的基本單位來實現(xiàn)負載平衡。Wang等[5]為三層結構的云計算系統(tǒng)提出了一種兩階段的負載調度與均衡算法。

基于體系結構的負載均衡算法關注某種具體云系統(tǒng)架構下的負載均衡問題。此類算法往往不是顯式實現(xiàn)負載均衡的，而是通過設計云系統(tǒng)的各模塊及其相互關系來隱式達成負載均衡。文獻[6]構建了一種云系統(tǒng)架構，此架構包含兩種最主要的模塊：資源管理模塊和消息管理模塊。資源管理模塊定期收集處于活躍狀態(tài)的計算資源的負載情況以及用戶對計算資源的請求情況。而在響應用戶請求的過程中，消息管理器直接與客戶發(fā)生交互、并發(fā)揮核心作用。Xu等[7]將一個公共云系統(tǒng)劃分成若干個分片，云系統(tǒng)整體上設置一個總控制器，各分片分別設置一個調度器。總控制器通過與各調度器的實時信息交換來刷新各調度器所掌握的負載信息，各調度器根據(jù)上述信息展開調度、實現(xiàn)負載均衡。

將人工智能算法應用于云系統(tǒng)負載平衡是學術界近年來的研究趨勢[8]。其中，軟計算方法模擬自然界的生物行為設計算法，解決科學與工程優(yōu)化問題，已成為目前的研究熱點[9]。與前述兩種類型的負載均衡算法相比，基于軟計算的負載均衡算法能夠更加高效地處理不精確性、不確定性和不完整性[10]。與現(xiàn)有的典型軟計算方法，如遺傳算法(genetic algorithm,GA)差分演化算法(differential evolution,DE)和粒子群優(yōu)化算法(particle swarm optimization,PSO)等相比，人工蜂群算法具有以下優(yōu)勢：①算法易于實現(xiàn)；②適用范圍廣：不要求優(yōu)化目標函數(shù)解析式已知，也不要求優(yōu)化目標函數(shù)連續(xù)或可微；即便優(yōu)化目標函數(shù)十分復雜，算法仍可以高效執(zhí)行，且在離散或連續(xù)情況下均適用；③算法性能不依賴于算法初始化技巧；④適合在分布式/并行計算平臺上實現(xiàn)；⑤算法不宜過早收斂，且易于收斂到全局最優(yōu)點。

1 云計算負載均衡與人工蜂群算法

1.1 云計算負載均衡概述

云計算根據(jù)用戶或系統(tǒng)的不同需求提供虛擬機的動態(tài)資源池。如何接受和響應各種服務請求，取決于云計算系統(tǒng)的管理策略，而此策略是基于各服務器的負載情況的。在云計算系統(tǒng)中，負載均衡技術用于增強資源利用的并行性，通過恰當?shù)貫橛嬎闳蝿者x擇虛擬機來縮短響應時間。

諸如PSO等負載均衡算法，其主要目標是從邏輯上將全體虛擬機節(jié)點的計算資源作為一個整體，為計算任務分配虛擬機節(jié)點，并允許計算任務在虛擬機節(jié)點間遷移，最大限度地縮短完成時間并減少故障次數(shù)[11]。

1.2 人工蜂群算法

Karaboga等[12]提出了人工蜂群算法，用于解決工程優(yōu)化問題。在該算法中，每個蜜蜂都是一個代理，也是優(yōu)化問題的一個可能的解，它通過交換信息以協(xié)作解決復雜的組合優(yōu)化問題。

該算法主要步驟可以描述如下：

(1)在覓食過程的第一步，派出若干只蜜蜂作為偵察峰開始隨機探索環(huán)境以尋找花蜜來源。

(2)在第二階段，找到食物來源后，偵察蜂成為引領蜂，并從已發(fā)現(xiàn)的花蜜來源獲取花蜜。引領蜂回到蜂巢并且卸下花蜜后，可以直接返回到它發(fā)現(xiàn)花蜜的地點，或者通過搖擺舞姿來分享花蜜來源信息。

(3)在第三階段，旁觀者蜜蜂在蜂巢內觀看搖擺舞姿，搖擺舞持續(xù)時間越長則表明花蜜來源質量越高。旁觀者蜜蜂根據(jù)質量選擇一個花蜜來源并前往獲取花蜜，這種蜜蜂角色稱為跟隨蜂。

(4)如果一個引領蜂的花蜜來源枯竭，它會重新成為一只偵察峰，并開始隨機搜索新的花蜜來源。

2 基于人工蜂群的負載均衡算法

將計算任務視為“蜜蜂”、虛擬機作為“花蜜源”，人工蜂群算法的基本思想可用于解決云計算負載均衡問題。

2.1 基本思想

在云系統(tǒng)中，全體虛擬機被依照其負載高低做降序排列。如果某個虛擬機負載過重，那么需要將若干個計算任務從該虛擬機上移除。當移除的任務被遷移至負載較低的虛擬機時，它們會記錄當前所在虛擬機的負載情況及該虛擬機上各任務的優(yōu)先級等信息，并將這些信息廣播至等待隊列中的全體計算任務。等待隊列中的計算任務根據(jù)所接收到的信息來選擇虛擬機。

每當有高優(yōu)先級任務將要被遷移時，算法應從全體低負載虛擬機中選擇包含高優(yōu)先級任務最少的虛擬機作為遷移目的地，以便保證被遷移的任務能盡早得到執(zhí)行。

實質上，計算任務扮演了蜜蜂角色，虛擬機是花蜜來源。為計算任務選擇恰當?shù)奶摂M機來執(zhí)行，類似于蜜蜂搜尋花蜜來源。虛擬機過載，象征某個花蜜來源枯竭；選擇負載較低的虛擬機作為計算任務的遷移目的地，類似于蜜蜂尋找新的花蜜來源。被遷移的任務向等待隊列中的任務廣播虛擬機的狀態(tài)信息，類似于偵察蜂通過搖擺舞姿將花蜜來源信息告知旁觀者蜜蜂。根據(jù)虛擬機的狀態(tài)信息來確定等待隊列中的哪個任務應該分配給哪個虛擬機，類似于旁觀者蜜蜂根據(jù)搖擺舞姿選擇花蜜來源。

基于上述基本思想，針對云計算負載均衡問題建立數(shù)學模型，并將負載均衡算法設計為以下三個主要步驟：負載均衡決策、虛擬機分組、計算任務調度。

2.2 數(shù)學模型

令VM={VM1,VM2,…,VMm}為云系統(tǒng)上全體虛擬機的集合，C={C1,C2,…,Cn}為需要執(zhí)行的全體計算任務的集合。全部n個任務都將以非搶占方式執(zhí)行，即任務一旦開始執(zhí)行不能被停止(但允許一個任務在完成部分計算量后，被遷移至其他虛擬機)，直至執(zhí)行完畢，且暫不考慮任務執(zhí)行因故障而中斷的情況。

2.2.1 最大完工時間

以最大完工時間表示全體任務執(zhí)行完畢所用的時間開銷，記為Makespan。以第一個任務開始執(zhí)行作為計時起點，令TEij代表任務i在虛擬機j上執(zhí)行完成的時刻，那么有：

Makespan=max{TEij|i=1,2,…,n;j=1,

2,…,m}

(1)

負載均衡算法的目標為：令Makespan的值盡可能小。

2.2.2 虛擬機容量

定義虛擬機j的容量：

Capj=p_numj×p_powerj+bandwidthj

(2)

式(2)中：p_numj是虛擬機j具有的處理器個數(shù)；p_power是單個處理器的處理能力(以單位時間內執(zhí)行的指令數(shù)衡量)；bandwidthj是虛擬機j具有的網(wǎng)絡通信帶寬。

定義整個云系統(tǒng)的容量：

(3)

2.2.3 虛擬機的負載

計算任務完成時長虛擬機j在t時刻的負載：

(4)

式(4)中：task_numberj,t是t時刻虛擬機j等待隊列中的任務總數(shù)；service_ratej,t是t時刻虛擬機j的服務率(單位時間內能完成的計算任務個數(shù))。

虛擬機j完成等待隊列中的任務需要的時長(按t時刻的狀態(tài)計算)：

(5)

整個云系統(tǒng)的負載：

(6)

整個云系統(tǒng)完成等待隊列中的任務需要的時長：

(7)

2.2.4 任務完成時長標準差

任務完成時長的標準差定義為

(8)

標準差越大則說明負載在各虛擬機上的分布越不均衡。

2.3 算法流程

下面給出本文算法詳細流程。

1 計算負載情況：

根據(jù)式(2)～式(4)、式(6)計算各虛擬機負載即系統(tǒng)整體負載。根據(jù)式(5)、式(7)、式(8)計算負載方差δ；如果δ

2 負載平衡決策：

當前時刻，若Loadt>Cap[式(3)、式(6)]，那么系統(tǒng)整體過載，算法退出；否則自動進行負載平衡。

3 虛擬機分組：

將所有虛擬機分為高負載、負載已平衡、低負載三個分組，依次記為Grouph、Groupb、Groupl。將Grouph中的虛擬機按負載高低做降序排列，Groupl中的虛擬機按負載高低做升序排列

4 虛擬機調度：

while Grouph≠φ且Groupl≠φ

for VMs∈Grouph

按優(yōu)先級對VMs等待隊列中的任務做降序排列；

依照式(9)～式(11)依次為VMs中的任務選擇目的地虛擬機VMd并遷移；

每當一個任務遷移完成后重新計算VMs和VMd的負載；

如果需要，調整VMs和VMd所屬分組。

end

將Grouph中的虛擬機按負載高低重新做降序排列；

Groupl中的虛擬機按負載高低重新做升序排列。

end

2.4 負載均衡決策

在基于數(shù)學模型計算得到工作負載和標準差后，云系統(tǒng)應該決定是否進行負載平衡。具體地，應考慮兩方面因素：判斷云系統(tǒng)整體上是否過載(即整個系統(tǒng)的計算負載已飽和)；判斷云系統(tǒng)整體上否負載均衡。只有在系統(tǒng)未飽和的狀態(tài)下，負載均衡才是有意義的。

當云系統(tǒng)的計算負載[式(6)]超過該系統(tǒng)的最大容量[式(3)]時，系統(tǒng)整體過載。如果云平臺的負載標準偏差[式(8)]低于或等于設定的閾值threshold，那么系統(tǒng)是平衡的[13]；否則系統(tǒng)處于不平衡狀態(tài)。但僅憑標準差的值無法判斷整個系統(tǒng)處在超載或負載不足狀態(tài)。

2.5 虛擬機分組

根據(jù)負載情況對虛擬機分組，包括三種類型的分組：過載的虛擬機分組、低負載虛擬機分組、負載平衡的虛擬分組。當需要從屬于過載組的虛擬機上向外遷移任務時，必須根據(jù)低負載虛擬機分組的負載情況，決定把哪個低負載虛擬機作為遷移目的地。

在本文算法中，需遷移的任務扮演了偵察蜂角色，低負荷的虛擬機則是尚未枯竭的花蜜源。被遷移的任務向等待隊列中的任務廣播的信息包括：任務原來所在虛擬機的負載、其他所有虛擬機的負載、各虛擬機上任務的優(yōu)先級、各虛擬機等待隊列中任務數(shù)量、每個虛擬機分組中的虛擬機數(shù)量。負載平衡的虛擬機不會被用作任務遷移的起點或目的地。一旦任務遷移結束，那么新進入負載平衡狀態(tài)的虛擬機將被歸入負載平衡虛擬機分組。當全體虛擬機都被歸入負載平衡分組時，系統(tǒng)整體負載平衡。

2.6 計算任務調度

如果決定要平衡負載，那么尋找低負載的虛擬機作為任務遷移的目的地。選擇目的地的重要影響因素是任務的優(yōu)先級。目的地虛擬機選擇規(guī)則如下。

以UnderLoad代表低負載的虛擬機集合，high(VMj)、middle(VMj)、low(VMj)分別代表虛擬機j等待隊列中高優(yōu)先級任務、中優(yōu)先級任務、低優(yōu)先級任務的數(shù)量。

如果被遷移的是高優(yōu)先級任務，那么目的地虛擬機應為

VMh,destination=VMd|VMd∈UnderLoad,

(9)

如果被遷移的是中優(yōu)先級任務，那么目的地虛擬機應為

VMm,destination=VMd|VMd∈UnderLoad,

middle(VMk)]

(10)

如果被遷移的是低優(yōu)先級任務，那么目的地虛擬機應為

VMl,destination=VMd|VMd∈UnderLoad,

middle(VMk)+low(VMk)]

(11)

3 實驗分析

采用CloudSim[14]作為仿真環(huán)境，驗證了所設計算法的性能。虛擬機個數(shù)為6，除特別說明外，仿真環(huán)境參數(shù)設置均取默認值。程序運行于一臺個人計算機，內存1.75 GB，CPU為3.0 GHz。

圖1對比了不采用負載均衡(計算任務先到先服務策略，且從集合VM中輪流選擇虛擬機提供服務)、和采用人工蜂群算法做負載平衡兩種策略的最大完工時間。橫軸代表系統(tǒng)中任務總數(shù)，縱軸代表最大完工時間(Makespan)。由圖1可見，當計算任務總數(shù)較少時，兩種情況下，系統(tǒng)完工時間的差異也并非十分顯著。其原因在于此時系統(tǒng)整體上處于低負載狀態(tài)，即使不進行負載均衡也不易出現(xiàn)某個虛擬機負載過重的情況，各虛擬機的完工時間的標準差[式(8)]較小。然而，在不采用負載均衡的策略下，計算任務一旦被分配至虛擬機就無法遷移，隨著任務數(shù)增多，易進入負載不均衡狀態(tài)，導致高負載虛擬機完工時間變長而低負載虛擬機的部分計算資源被閑置，最終使得系統(tǒng)最大完工時間變長。而人工蜂群均衡算法通過“偵察蜂廣播機制”，實時探查各虛擬機的負載情況，并在系統(tǒng)出現(xiàn)負載失衡時將高負載虛擬機的部分任務遷移至低負載虛擬機，這使得系統(tǒng)最大完工時間關于任務總數(shù)的增長率顯著降低。

圖1 三種算法最大完工時間對比Fig.1 Comparison of Makespan of three algorithms

如表1所示對比了粒子群算法和人工蜂群算法的最大完工時間隨Cloudlet總數(shù)的變化趨勢。Cloudlet是一種為處于云上移動設備的計算任務增速的模式。Cloudlet將移動設備上的計算任務遷移到同一個局域網(wǎng)下的服務器上執(zhí)行。一個Cloudlet可以被視作為移動端計算任務實時定制的虛擬服務器。Cloudlet總數(shù)增多意味著從移動端遷移到虛擬服務器的計算任務增多。顯然，人工蜂群算法具備更有的最大完工時間。

圖2給出了智能蜂群負載均衡算法和粒子群負載均衡算法[15]在反應時間上的對比。很顯然，前者具有更短的反應時間。

表1 最大完工時間關于Cloudlet總數(shù)的變化趨勢對比：粒子群算法與人工蜂群算法Table 1 Comparison of the change trend of the maximum completion time with respect to the total number of Cloudlets

圖2 粒子群算法與人工蜂群算法系統(tǒng)反應時間對比Fig.2 System response time comparison:between particle swarm optimization algorithm and artificial bee colony algorithm

圖1也顯示了粒子群算法和人工蜂群算法的Makespan比較，可以清楚地看出，與粒子群算法相比，人工蜂群算法更有效。

比較了兩種算法的負載不平衡度。負載不平衡度由式(12)給出：

(12)

不平衡度越大則說明負載在各虛擬機之間的分布越不平衡。圖3對比了不采用負載均衡策略和采用人工蜂群負載均衡算法兩種情況下的不平衡度。在不采用負載均衡策略的情況下，M個虛擬機依次接收計算任務，且不能動態(tài)遷移計算任務，負載不平衡度較高且出現(xiàn)明顯的波動。采用人工蜂群算法做負載平衡后，可以實時地更新各虛擬機的負載狀態(tài)并將計算任務分配到負載較低的虛擬機上執(zhí)行，這顯著降低了不平衡度，也顯著減緩了不平衡度隨計算任務增加而出現(xiàn)的波動。此外，圖3也顯示了人工蜂群算法的不平衡度明顯低于粒子群算法的不平衡度。

盡管任務遷移有助于系統(tǒng)整體的負載平衡，但是任務遷移會帶來計算環(huán)境切換、網(wǎng)絡通信等時間開銷。如果遷移次數(shù)過多，也會影響系統(tǒng)的性能。負載均衡算法必須從全局角度考慮任務調度，盡可能減少任務遷移。本文算法優(yōu)先選擇低優(yōu)先級的任務進行遷移，從而盡可能避免任務遷導致移高優(yōu)先級任務被拖延。圖4對比了粒子群算法與人工蜂群算法的任務遷移次數(shù)。顯然，本文方法有助于減少不必要的任務遷移。

圖3 三種算法的不平衡度對比Fig.3 Imbalance comparison three algorithms

圖4 粒子群算法與人工蜂群算法的任務遷移次數(shù)對比Fig.4 Comparison of task migration times between particle swarm optimization algorithm and artificial bee colony algorithm

4 結論

源自自然現(xiàn)象的算法往往能為動態(tài)優(yōu)化問題提供高效的解決方案。將人工蜂群算法用于云計算系統(tǒng)負載均衡。此算法利用群體智能來從過載的虛擬機中移除任務，并將這些移除的任務提交給最適合的低負載虛擬機。算法不僅平衡了負載，而且在遷移任務的過程中考慮了等待隊列中任務的優(yōu)先級。選擇具有最低優(yōu)先級的任務進行遷移以減少不平衡。實驗結果表明，該算法在最大完工時間、反應時間、不平衡度、任務遷移次數(shù)等指標上均具有較優(yōu)的性能。

未來進一步的工作將關注如何將蟻群優(yōu)化(ACO)、粒子群優(yōu)化(PSO)等算法的優(yōu)勢融入人工蜂群算法，以進一步提高算法效率。