賈 嘉,慕德俊

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

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

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

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

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

1 云計(jì)算負(fù)載均衡與人工蜂群算法

1.1 云計(jì)算負(fù)載均衡概述

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

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

1.2 人工蜂群算法

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

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

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

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

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

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

2 基于人工蜂群的負(fù)載均衡算法

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

2.1 基本思想

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

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

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

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

2.2 數(shù)學(xué)模型

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

2.2.1 最大完工時(shí)間

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

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

2,…,m}

(1)

負(fù)載均衡算法的目標(biāo)為：令Makespan的值盡可能小。

2.2.2 虛擬機(jī)容量

定義虛擬機(jī)j的容量：

Capj=p_numj×p_powerj+bandwidthj

(2)

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

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

(3)

2.2.3 虛擬機(jī)的負(fù)載

計(jì)算任務(wù)完成時(shí)長(zhǎng)虛擬機(jī)j在t時(shí)刻的負(fù)載：

(4)

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

虛擬機(jī)j完成等待隊(duì)列中的任務(wù)需要的時(shí)長(zhǎng)(按t時(shí)刻的狀態(tài)計(jì)算)：

(5)

整個(gè)云系統(tǒng)的負(fù)載：

(6)

整個(gè)云系統(tǒng)完成等待隊(duì)列中的任務(wù)需要的時(shí)長(zhǎng)：

(7)

2.2.4 任務(wù)完成時(shí)長(zhǎng)標(biāo)準(zhǔn)差

任務(wù)完成時(shí)長(zhǎng)的標(biāo)準(zhǔn)差定義為

(8)

標(biāo)準(zhǔn)差越大則說明負(fù)載在各虛擬機(jī)上的分布越不均衡。

2.3 算法流程

下面給出本文算法詳細(xì)流程。

1 計(jì)算負(fù)載情況：

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

2 負(fù)載平衡決策：

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

3 虛擬機(jī)分組：

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

4 虛擬機(jī)調(diào)度：

while Grouph≠φ且Groupl≠φ

for VMs∈Grouph

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

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

每當(dāng)一個(gè)任務(wù)遷移完成后重新計(jì)算VMs和VMd的負(fù)載；

如果需要，調(diào)整VMs和VMd所屬分組。

end

將Grouph中的虛擬機(jī)按負(fù)載高低重新做降序排列；

Groupl中的虛擬機(jī)按負(fù)載高低重新做升序排列。

end

2.4 負(fù)載均衡決策

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

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

2.5 虛擬機(jī)分組

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

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

2.6 計(jì)算任務(wù)調(diào)度

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

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

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

VMh,destination=VMd|VMd∈UnderLoad,

(9)

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

VMm,destination=VMd|VMd∈UnderLoad,

middle(VMk)]

(10)

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

VMl,destination=VMd|VMd∈UnderLoad,

middle(VMk)+low(VMk)]

(11)

3 實(shí)驗(yàn)分析

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

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

圖1 三種算法最大完工時(shí)間對(duì)比Fig.1 Comparison of Makespan of three algorithms

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

圖2給出了智能蜂群負(fù)載均衡算法和粒子群負(fù)載均衡算法[15]在反應(yīng)時(shí)間上的對(duì)比。很顯然，前者具有更短的反應(yīng)時(shí)間。

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

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

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

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

(12)

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

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

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

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

4 結(jié)論

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

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