云計算環(huán)境下基于非均勻窗口蟻群行為的負(fù)載平衡算法

張少輝，崔仲遠(yuǎn)，韓秋英

(周口師范學(xué)院 計算機科學(xué)與技術(shù)學(xué)院，河南 周口，466001)

?

云計算環(huán)境下基于非均勻窗口蟻群行為的負(fù)載平衡算法

張少輝，崔仲遠(yuǎn)，韓秋英

(周口師范學(xué)院 計算機科學(xué)與技術(shù)學(xué)院，河南 周口，466001)

摘要：針對云計算環(huán)境下可能面臨請求過載和較長響應(yīng)時間的問題，在非均勻窗口蟻群行為思想的啟發(fā)下，提出一種負(fù)載平衡算法。假設(shè)云環(huán)境下任何時候虛擬機都處于過載狀態(tài)，即服務(wù)提供者不得不分配資源。根據(jù)該假設(shè)，對可利用的資源合理優(yōu)化，優(yōu)化過程中動態(tài)代理和靜態(tài)代理同時進行，其中蟻群行為被用于負(fù)載平衡，通過加載資源到所有的虛擬機上來實現(xiàn)系統(tǒng)平衡。利用CloudSim仿真器模擬云計算環(huán)境進行實驗分析，實驗結(jié)果表明，與容錯分簇的負(fù)載均衡感知(tolerant cluster-aware，TCLB)、基于博弈論的負(fù)載均衡算法(scheduling strategy on load balancing，SSLB)和基于蜜蜂行為的負(fù)載均衡算法(honey bee behavior inspired load balancing，HBB-LB)相比，提出的算法分別節(jié)省了37%，8%和4%的響應(yīng)時間，最大完成時間也大幅度降低，整體性能有所提高。

關(guān)鍵詞：云計算；負(fù)載平衡；代理；蟻群行為；響應(yīng)時間；最大完成時間

0引言

在高度可靠的大型網(wǎng)絡(luò)中，云計算[1]是一種基于分布式互聯(lián)網(wǎng)用于遠(yuǎn)程分享、使用不同資源與服務(wù)的設(shè)計模式，如存儲、計算能力和應(yīng)用程序等。然而，由于動態(tài)傳入的請求，在此過程中需要進行動態(tài)資源分配，云計算領(lǐng)域固有的動態(tài)性需要高效的負(fù)載平衡機制，即資源分布在不同用戶或者統(tǒng)一的請求方式中，沒有節(jié)點是處于過載狀態(tài)或處于閑置狀態(tài)[2-3]。負(fù)載平衡是云計算的一個重要方面，在沒有提供負(fù)載平衡的情況下，一些過載節(jié)點的效率就可能大幅下降，最終導(dǎo)致違反服務(wù)等級協(xié)議[4](service level agreement，SLA)。

傳統(tǒng)的分布式計算、 并行計算和網(wǎng)格計算環(huán)境下負(fù)載平衡算法分為靜態(tài)、動態(tài)或混合調(diào)度算法[5]，云計算環(huán)境下的算法是動態(tài)負(fù)載平衡算法，即重點是減少通信延遲和執(zhí)行時間，滿足用戶的動態(tài)服務(wù)，同時優(yōu)化負(fù)載平衡。

1相關(guān)工作

負(fù)載平衡是各種計算機網(wǎng)絡(luò)中最重要的問題之一。為了解決這個問題，已有很多學(xué)者對其進行研究。

文獻[6]提出在公共負(fù)載平衡中引入一種博弈論的模型。該算法根據(jù)負(fù)載程度把云劃分為3類，分別是空閑云、正常云、過載云。零負(fù)載的云代表空閑云，如果處于零和最高值之間就是正常云，否則就是過載云。但這種負(fù)荷度范圍的選擇問題一直都沒有得到解決。

文獻[7]提出了一種利用虛擬調(diào)度機制的遺傳算法來達到虛擬服務(wù)器之間的負(fù)載平衡。以種群粒子優(yōu)劣為依據(jù)自適應(yīng)調(diào)整慣性權(quán)重，這種機制選擇負(fù)載最小的虛擬機(virtual machine，VM)來提供負(fù)載傳輸和優(yōu)化高昂的遷移成本。然而由于數(shù)據(jù)中心大量的虛擬機和頻繁的服務(wù)請求，可能導(dǎo)致服務(wù)調(diào)度效率低下。

文獻[8]提出了2種云環(huán)境下的動態(tài)算法。第1種是針對機會主義負(fù)載平衡，即由節(jié)點傳入任務(wù)時具有最小執(zhí)行時間；第2種是維持最小負(fù)載平衡以提高資源利用率。然而這2種算法均不適合抄送環(huán)境。抄送環(huán)境需要提前將所需虛擬資源部署在系統(tǒng)中，選擇一個影響最小的解決方案，達到最佳負(fù)載平衡，同時減少或避免動態(tài)遷移，而文獻[8]的2種算法均無法提前部署資源。

文獻[9]提出了一種利用分形方法觸發(fā)的策略和多準(zhǔn)則決策的方法。分形方法避免了瞬時峰值的遷移問題，多準(zhǔn)則決策的方法是為了解決對不同物理資源分配的決策問題，雖然在資源選擇方面更加均衡，但該模型在提交任務(wù)過程中需要較多的響應(yīng)時間。

文獻[10]將遺傳算法思想加入到分布式負(fù)載均衡算法中，獲取對不同目標(biāo)的權(quán)重運算，提出了一種面向云計算的負(fù)載均衡算法，為大型云系統(tǒng)的負(fù)載均衡問題提供了潛在的可行方案，減少了物理節(jié)點的使用數(shù)量和遷移次數(shù)，然而，該算法的資源利用率不高。為了提高資源利用率，文獻[11]研究了蜜蜂覓食方案并檢測了分布式隨機抽樣方法，該方法通過加載近乎全局的均值測量來維護各個節(jié)點。

文獻[12]提出了一種工作在2個相位的機制，在第1相位可以確定CPU的利用率和每個實例所開銷的內(nèi)存，同時，也能知道每個虛擬機的內(nèi)存可供開銷的量；在第2相位，比較可用資源和所需資源，如果所需資源可以獲取，則進一步確定是否丟棄請求，但這種機制的缺點在于缺乏可擴展性。

從上述方法可以看出，人工智能機制如遺傳算法、蜜蜂算法、博弈論和智能代理等都能應(yīng)用于云計算中的負(fù)載平衡，但諸如此類負(fù)載平衡算法的動態(tài)特性缺乏可擴展性和可靠性。因此，需要一種具有良好可擴展性和可靠性的算法，即盡可能地提供動態(tài)資源調(diào)度、最大化資源優(yōu)化配置、最大化吞吐能力、最小化響應(yīng)時間。

2平衡算法組件

負(fù)載平衡算法具有5個主要原則[5]及功能，如表1所示。算法提供效率的依據(jù)有5點[5]。

1)可靠性。算法必須是可靠的，因為將工作從一個位置轉(zhuǎn)移到其他位置時，進程失敗可能增加等待時間、導(dǎo)致客戶不滿意。

2)適應(yīng)性。算法必須能夠適應(yīng)動態(tài)變化的用戶請求并在最短的時間內(nèi)提供任務(wù)分配。

3)容錯。算法必須確保容錯能力，從而在系統(tǒng)總負(fù)荷出現(xiàn)問題的情況下維持平衡機制不間斷工作。

4)吞吐量。算法必須確保以最小代價增加吞吐量，若負(fù)載平衡算法沒有增加系統(tǒng)的吞吐量，則表明沒有達到目的。

5)輪候時間。算法應(yīng)盡量減少某項任務(wù)分配資源等待時間。

表1　負(fù)載平衡各個原則及功能

3本文的負(fù)載平衡算法

本文提出的自主代理是基于負(fù)載平衡算法解決最大化的資源優(yōu)化配置、最大化的吞吐能力、最少的響應(yīng)時間、動態(tài)資源調(diào)度。若滿足任何時候虛擬機處于過載狀態(tài)，則服務(wù)提供者不得不分配資源，服務(wù)提供者將對可用的資源合理優(yōu)化，由所有虛擬機共同承擔(dān)負(fù)載，從而保持平衡，否則服務(wù)提供者分配資源將不確定，因此，本文假設(shè)虛擬機都處于過載狀態(tài)。

3.1非均勻窗口蟻群算法

蟻群算法[13]有3個最重要的準(zhǔn)則，即轉(zhuǎn)移概率準(zhǔn)則、局部調(diào)整準(zhǔn)則、全局信息素調(diào)整規(guī)則。

采用非均勻窗口蟻群是為了克服一般蟻群算法的搜索時間長、容易陷入局部最優(yōu)的缺點[14-15]，主要策略是在算法初期給出一個可以接受的群體最小進化率Gmin，設(shè)置較小螞蟻窗口值win，最大限度地縮小螞蟻移動范圍以減少搜索時間，群體的進化率定義為

(1)

(2)

(2)式中，k表示螞蟻下一步所能到達的節(jié)點數(shù)。

從(2)式可以看出，蟻群窗口進行調(diào)整時，群體進化率越小，win越大，其搜索空間進行了拓展，有利于更快地找到最優(yōu)解。同時無需根據(jù)優(yōu)化的具體問題反復(fù)確定窗口的大小，提高了通用性。

3.2應(yīng)用于負(fù)載平衡

眾所周知，蟻群算法是一種生物啟發(fā)算法，利用路徑遺留的信息素、信息素濃度和擴散機制來吸引螞蟻選擇覓食路徑，由于非均勻窗口蟻群算法能快速選擇最短或最佳路徑，因此，本文將其應(yīng)用于解決負(fù)載問題。非均勻窗口蟻群算法最吸引人的地方，除了能最快選擇最佳路徑外，非常適用于負(fù)載平衡，即螞蟻從出發(fā)到目的地執(zhí)行任務(wù)無需再回到出發(fā)地，而是在抵達目的地后自己毀滅掉，從而在網(wǎng)絡(luò)中減少不合適的路線。既然負(fù)載平衡在抄送中需要搜索底層的負(fù)載服務(wù)器和資源，蟻群算法完全能滿足這種目的，且不會增加網(wǎng)絡(luò)的額外負(fù)載。

負(fù)載平衡由3部分代理組成：負(fù)載代理、信道代理和遷移代理。負(fù)載和信道代理都是靜態(tài)代理，遷移代理是動態(tài)代理[16]。

負(fù)載代理控制著信息原則以及維持?jǐn)?shù)據(jù)中心的所有細(xì)節(jié)。其主要工作是在數(shù)據(jù)中心分配新任務(wù)后計算每個可利用的虛擬機上的負(fù)荷，所支持的表稱為虛擬機負(fù)載適合度表。虛擬機負(fù)載適合度表主要用于維持記錄數(shù)據(jù)中心所有虛擬機中特定部分的記錄。它包含了虛擬機ID、內(nèi)存消耗狀態(tài)、CPU的效率、適合度值、所有虛擬機的負(fù)載狀態(tài)。它的結(jié)構(gòu)如表2所示。表2中，μ表示內(nèi)存使用百分比，λ是CPU使用效率百分比，v是虛擬機適合度值。

表2　虛擬機負(fù)載適合度表

信道代理控制著傳輸原則、選擇原則和定位原則，接收到來自負(fù)載代理的請求后，信道代理將會啟動一些遷移代理到其他的數(shù)據(jù)中心，在相同配置的虛擬機上進行搜索。它也會按順序持續(xù)保存來自響應(yīng)表中這些代理的所有信息記錄，其響應(yīng)表如表3所示，其中，*A表示適用，即發(fā)現(xiàn)相似的配置，**NA表示不適用，即未發(fā)現(xiàn)相似的配置。

表3　響應(yīng)表

遷移代理由信道代理發(fā)動，它將會移動到其他的數(shù)據(jù)中心，并會和那個數(shù)據(jù)中心負(fù)載代理進行信息交流來查詢虛擬機當(dāng)前的狀態(tài)，找到理想的配置。接收到請求信息后，利用同樣的方式與父級信道代理溝通。然而，它將會停留在目的地的位置，靜候來自于父級信道代理的自毀信息。這個遷移代理的狀態(tài)基于其適用性可能會存活，也有可能被摧毀。

負(fù)載平衡是利用虛擬機的負(fù)載狀態(tài)，依據(jù)可使用內(nèi)存、可利用的CPU使用率以及期待的響應(yīng)時間，周期性地決定虛擬機的工作負(fù)載，計算出每臺虛擬機的適合度，具體由(3)—(4)式給出。

(3)

(4)

適合度百分?jǐn)?shù)將給出虛擬機的狀態(tài)

(5)

無論何時的請求到達數(shù)據(jù)中心，在完成資源分配后，負(fù)載代理都會對反映當(dāng)前所有虛擬機狀態(tài)的虛擬機適合度表進行升級。這些因子影響傳入請求的進程后，負(fù)載代理就會計算出μ和λ百分?jǐn)?shù)。再基于μ可利用的值，就能得到每個節(jié)點的適合度v。只要每個節(jié)點的v值大于25%的閾值，在此情形下，虛擬機的狀態(tài)就是正常的。當(dāng)虛擬機的適合度小于或等于閾值時，則需執(zhí)行負(fù)載平衡。

類似于蟻群算法，到達目的地數(shù)據(jù)中心后，遷移代理首先將告知信息發(fā)送給父級信道代理；然后，它將核實那個數(shù)據(jù)中心的負(fù)載代理是否存在所需相似配置的虛擬機可供使用。若沒有可用虛擬機，遷移代理就會發(fā)送一條不適用的指令信息返回到父級信道代理，同時等待來自父級信道代理的自毀指令；若有一個或者多個可用虛擬機，遷移代理將會進一步核實他們的μ和ν，并將他們發(fā)送到信道代理。接收到來自各種遷移代理的響應(yīng)后，信道代理將其記錄在響應(yīng)分析表中，具體如表4所示。

表4　虛擬機負(fù)載適合度表

數(shù)據(jù)中心接收新的請求后，負(fù)載代理就會映射可使用的虛擬機參數(shù)規(guī)格。若虛擬機的適合度值正常，負(fù)載代理繼續(xù)進行未來的分配；否則，負(fù)載代理將會請求信道代理透視數(shù)據(jù)中心是否有相似配置的虛擬服務(wù)器進行負(fù)載平衡。此時，信道代理掃描響應(yīng)分析表，并找出來匹配請求。若找到一個以上合適的記錄，將挑選具有最大v值的記錄。信道代理與響應(yīng)的遷移代理通信以核實當(dāng)前的v和VM。接收到來自遷移代理的響應(yīng)后，信道代理會再次分析所有合適的虛擬機。這里類似于非均勻窗口的窗口和進化率問題，尋找更快的解決方式。圖1是負(fù)載平衡算法的框架圖，可以看出，與蟻群算法流程非常相似，負(fù)載適合度表升級類似于信息素的更新管理，尋找最佳資源分配過程與尋找路徑過程對應(yīng)，移動代理響應(yīng)使尋找最優(yōu)資源配置的時間和解空間不斷減少和優(yōu)化，這與非均勻窗口的功能類似。算法1-算法3給出了本文算法的偽代碼過程。

圖1　負(fù)載平衡算法框架圖Fig.1　Frames of algorithm of load balancing

算法1遷移代理()。

Input：來自信道代理(VMinitialization)的VMconfigure；

Output：尋找來自另外的數(shù)據(jù)中心相似的VM

{接收來自信道代理(VMinitialization)的VMconfigure；

尋找 一個數(shù)據(jù)中心；

核實 VM負(fù)載表；

If(確定能找到)

Return(A)

Else

Return(NA)；

正在等待接收(自毀指令)；

結(jié)束進程 (MAi)；}

算法2負(fù)載代理()。

Input: 接收用戶請求；

Output:利用A2LB分配資源；

CaseI：{

If(虛擬機負(fù)載表==空)

那么分配請求資源；維持虛擬機負(fù)載表；

μavailable=μtotal-μused

If(v>25)then

{ 分配狀態(tài):=正常；}

Else

{分配狀態(tài)：=臨界；

初始化 信道代理(VMinitialization)；}

CaseII：

If(虛擬機負(fù)載表≠空)

掃描虛擬機負(fù)載表；

If(負(fù)載狀態(tài)(VMi)==臨界)

{請求信道代理(VMload-balance)；

接收；

請求傳輸?shù)?DCid；}

Else

請求分配到 VMid；

升級 虛擬機負(fù)載表；}

算法3信道代理(VMinitialization)。

Input：接收來自于負(fù)載代理的VMi配置信息；

Output：響應(yīng)分析列表，虛擬機ID；

接收來自負(fù)載代理的VMi；

初始化遷移代理；

接收來自于遷移代理的通知；

維持響應(yīng)表；

If(響應(yīng)==NA)

{ 發(fā)出指令自毀(MAi)；}

Else

{ 接收v(MAi)； 維持響應(yīng)分析表；

周期性更新響應(yīng)分析表；}

信道代理(VMload-balance)：

正傳入請求：

{ 掃描響應(yīng)分析表；

準(zhǔn)備匹配的VMi列表；

L1：fori=1ton

Large=0；

If(v(VMi>Large))

Large=v(VMi)；

vold=vi；

更新MAi信息；

If(vold==vi)

Return()to負(fù)載代理；

Else轉(zhuǎn)到L1；}

4實驗與分析

實驗在英特爾酷睿II雙核處理器，2.45GHzCPU，4.0GByteRAM和微軟WindowsVista平臺上實現(xiàn)，編程工具為Java。根據(jù)CloudSim上的仿真結(jié)果分析了本文算法的性能，將CloudSim模擬器[17]的級別進行擴展，將本文提出的非均勻窗口蟻群負(fù)載均衡算法(loadbalancebasedonnon-uniformwindowantcolonybehavior，NWACB-LB)與文獻[6]提出的基于博弈論的負(fù)載均衡算法(schedulingstrategyonloadbalancing，SSLB)、文獻[7]提出的容錯分簇的負(fù)載均衡感知算法(tolerantcluster-aware，TCLB)、文獻[11]提出的基于蜜蜂行為的負(fù)載均衡算法(honeybeebehaviorinspiredloadbalancing，HBB-LB)進行比較。

4.1最大完成時間和響應(yīng)時間比較

表5為本文算法負(fù)載前后完成時間對比，可以看出，隨著任務(wù)數(shù)增加，最大完成時間明顯增加，動態(tài)負(fù)載均衡后最大完成時間明顯減少。

表5　負(fù)載均衡前后的最大完成時間

圖2為分別采用HBB-LB，SSLB，TCLB和NWACB-LB算法在短時間內(nèi)信道代理VM的響應(yīng)時間圖。實驗結(jié)果表明，相比TCLB，SSLB和HBB-LB算法，本文算法的平均響應(yīng)時間至少分別節(jié)省了37%，8%，4%，表明本文算法更加有效。

圖2　短時間內(nèi)VM對各個算法的響應(yīng)時間Fig.2　Response time of VM for each algorithm in short time

圖3為分別采用HBB-LB，SSLB，TCLB和NWACB-LB算法的最大完成時間圖。從圖3可以看出，相比HBB-LB，SSLB和TCLB算法，本文算法明顯減少了最大完成時間，因為當(dāng)適合度值低于一定閾值時，信道代理就會被激活，并開始搜尋有相同配置的虛擬機，完成時間明顯縮短。

4.2不平衡的負(fù)載級別比較

使用大約500個任務(wù)進行實驗，對所有4種算法中VM間負(fù)載的不平衡級別進行比較。其中，VM間負(fù)載的不平衡級別定義為

(10)

(10)式中：Tmax和Tmin分別表示所有VM中最大Ti和最小Ti，其中，Ti表示負(fù)載均衡后第i個任務(wù)完成時間；Tavg為VM中所有Ti的平均值。

圖3　各個算法的最大完成時間Fig.3　Maximum completion time of four algorithms

NWACB-LB在負(fù)載均衡前后VM間的不平衡級別如圖4所示。從圖4可以看出，NWACB-LB負(fù)載均衡后，明顯降低了不平衡級別。所有4種算法不平衡級別的對比結(jié)果如圖5所示，NWACB-LB與其他3種算法相比，更加有效地降低了不平衡的級別，很大程度上歸功于負(fù)載適合度表在移動代理響應(yīng)中的作用。

圖4　本文算法在負(fù)載均衡前后VM間不平衡級別Fig.4　Imbalanced levels between VM before and after load balancing in the proposed algorithm

對VM間遷移任務(wù)的平衡進行比較，遷移任務(wù)是指VM間被重新分配的任務(wù)數(shù)量，4種算法在3—5種VM間進行變化時，相應(yīng)的遷移任務(wù)的走勢如圖6—圖8所示。從圖6—圖8可以看出，在不考慮VM數(shù)量的情況下，本文算法中的遷移任務(wù)數(shù)量均小于其他3種算法，可見本文算法在容錯和適應(yīng)性方面更加有效。

圖5　各個算法的不平衡等級與任務(wù)數(shù)量關(guān)系Fig.5　Relationship between imbalanced levels and the number of tasks in four algorithms

圖6　3種VM情況下，各算法遷移任務(wù)數(shù)比較Fig.6　Comparison of numbers of migrations for four algorithms in the case of three VM

圖7　4種VM情況下，各算法遷移任務(wù)數(shù)比較Fig.7　Comparison of numbers of migrations for four algorithms in the case of four VM

圖8　5種VM情況下，各算法遷移任務(wù)數(shù)比較Fig.8　Comparison of numbers of migrations for four algorithms in the case of five VM

5結(jié)論

在非均勻窗口的蟻群算法基礎(chǔ)上，本文提出了一種云計算環(huán)境下的負(fù)載平衡算法，為云環(huán)境提供了動態(tài)的負(fù)載平衡。該算法的主要貢獻在于負(fù)載代理可以從其他目的地數(shù)據(jù)中心啟動類似于蟻群算法的搜索虛擬機，具有比一般蟻群算法更快的搜索速度，實驗結(jié)果表明了本文算法的整體性能有所提高。

參考文獻：

[1]鄧茹月, 覃川, 謝顯中. 移動云計算的應(yīng)用現(xiàn)狀及存在問題分析[J]. 重慶郵電大學(xué)學(xué)報：自然科學(xué)版, 2012, 24(6): 716-723

DENG Ruyue, TAN Chuan, XIE Xianzhong.Application Status and Problem Analysis of Mobile Cloud Computing [J]. Journal of Chongqing University of Posts and Telecommunications ：Natural Science Edition, 2012, 24(6): 716-723.

[2]王鵬, 黃焱, 李坤,等. 云計算集群相空間負(fù)載均衡度優(yōu)先調(diào)度算法研究[J]. 計算機研究與發(fā)展, 2014, 51(5):1095-1107.

WANG Peng, HUANG Yan, LI Kun, et al. Load Balancing Degree First Algorithm on Phase Space for Cloud Computing Cluster[J]. Journal of Computer Research and Development, 2014, 51(5): 1095-1107.

[3]蔡嵩. 云環(huán)境中基于樸素貝葉斯負(fù)載均衡技術(shù)的研究與實現(xiàn)[D]. 鎮(zhèn)江：江蘇大學(xué), 2014.

CAI Song.Research and Implementation of the Load Balancing Technology Based on Native Bayes Algorithm in Cloud Computing Environment [D].Zhenjiang：Jiangsu University, 2014.

[4]DHORE S R, SINHA P K. Multi-agent Optimized Load Balancing Using Spanning Tree for Mobile Services[J]. International Journal of Computer Applications, 2010, (6):33-40.

[5]BHASKAR. R, DEEPU S R, SHYLAJA B S. Dynamic Allocation Method For Efficient Load Balancing In Virtual Machines For Cloud Computing Environment[J].Advanced Computing：An International Journal,2012,3(5):53-61.

[6]HU J, GU J, SUN G, et al. A scheduling strategy on load balancing of virtual machine resources in cloud computing environment[C]//IEEE.Parallel Architectures, Algorithms and Programming (PAAP), 2010 Third International Symposium on. New York：IEEE, 2010: 89-96.

[7]蘇金樹, 郭文忠, 余朝龍, 等. 負(fù)載均衡感知的無線傳感器網(wǎng)絡(luò)容錯分簇算法[J]. 計算機學(xué)報, 2014, 37(2): 445-456.

SU Jinlong, GUO Wenzhong, YU Chaolong,et al. Fault-Tolerance Clustering Algorithm with Load-Balance Aware in Wireless Sensor Network [J]. Chinese Journal of Computers, 2014, 37(2): 445-456.

[8]AMAR M, ANURAG K, RAKESH K, et al. SLA Driven Load Balancing For Web Applications in Cloud Computing Environment[J].Information and Knowledge Management. 2011, 1(1): 10-17.

[9]施楊斌. 云計算環(huán)境下一種基于虛擬機動態(tài)遷移的負(fù)載均衡算法[D]. 上海：復(fù)旦大學(xué), 2011.

SHI Yangbin. Load Balancing Algorithm Based on Virtual Machine Dynamic Migration in Cloud Computing Environment[D]. Shanghai：Fudan University, 2011.

[10] 李強, 郝沁汾, 肖利民,等. 云計算中虛擬機放置的自適應(yīng)管理與多目標(biāo)優(yōu)化[J]. 計算機學(xué)報, 2011, 34(12): 2253-2264.

LI Qiang, HAO Mifen, XIAO Limin,et al. Adaptive Management and Multi-Objective Optimization for Virtual Machine Placement in Cloud Computing [J]. Chinese Journal of Computers, 2011, 34(12): 2253-2264.

[11] KRISHNA P V. Honey bee behavior inspired load balancing of tasks in cloud computing environments[J]. Applied Soft Computing, 2013, 13(5): 2292-2303.

[12] ALAM M G R, BISWAS C, NOWER N. A Semi-Distributed and Mobile Agent based architecture for load balancing of heterogeneous wireless networks[C]//IEEE. Computer and Information Technology (ICCIT), 2011 14th International Conference on. New York：IEEE, 2011, 4(1): 139-144.

[13] LI S H, HWANG J I G. Bidirectional Ant Colony Optimization Algorithm for Cloud Load Balancing[C]//IEEE. Proceedings of the 2nd International Conference on Intelligent Technologies and Engineering Systems (ICITES2013).Kaohsiung,Taiwan,China:Springer International Publishing, 2014: 907-913.

[14] 梁旭，黃明 .現(xiàn)代智能優(yōu)化混合算法及其應(yīng)用[M]. 北京:電子工業(yè)出版社，2011.

LIANG Xu, HUANG Ming. Modern Hybrid Intelligent Optimization Algorithm and Its Application[M].Beijing: Electronic Industry Press , 2011.

[15] 殷洪海. 云環(huán)境下基于改進蟻群算法的資源調(diào)度策略[D].成都：電子科技大學(xué), 2014.

YIN Honghai. Resource Scheduling Policy Based on Improved Ant Colony Algorithm in A Cloud Environment [D].Chengdu：University of Electronic Science and Technology of China, 2014.

[16] 唐道紅. 云環(huán)境下基于虛擬機動態(tài)遷移的資源調(diào)度策略研究[D]. 重慶：重慶郵電大學(xué), 2012.

TANG Daohong. Research on Resources Scheduling Strategy Based on Dynamic Migration of Virtual Machine in Cloud Computing[D].Chongqing：Chongqing University of Posts and Telecommunications, 2012.

[17] ALAM M G R, BISWAS C, NOWER N. A Semi-Distributed and Mobile Agent based architecture for load balancing of heterogeneous wireless networks[C]//IEEE. Computer and Information Technology (ICCIT), 2011 14th International Conference on. New York：IEEE, 2011: 139-144.

DOI：10.3979/j.issn.1673-825X.2016.04.019

收稿日期：2015-06-19

修訂日期：2016-04-07通訊作者：張少輝zhangsh_email@126.com

基金項目：河南省科技廳軟科學(xué)研究計劃項目(142400411213)；河南省高等學(xué)校重點科研項目(15A520118)

Foundation Items：The Soft Science Research Project from Science and Technology Department of Henan Province (142400411213); The High School Key Research Projects of Henan Province (15A520118)

中圖分類號：TP391

文獻標(biāo)志碼：A

文章編號：1673-825X(2016)04-0567-08

作者簡介：

張少輝(1982-)，男，河南鄭州人，講師，碩士，研究領(lǐng)域為云計算、智能算法等。E-mail：zhangsh_email@126.com。

崔仲遠(yuǎn)(1982-)，男，河南濮陽人，講師，碩士，研究領(lǐng)域為云計算、智能算法。

韓秋英(1981-)，女，河南沈丘人，講師，碩士，研究領(lǐng)域為云計算、計算機應(yīng)用等。

(編輯：王敏琦)

Load balancing algorithm based on non-uniform window ant colony behavior in cloud computing environment

ZHANG Shaohui, CUI Zhongyuan, HAN Qiuying

(College of Computer Science and Technology, Zhoukou Normal University, Zhoukou 466001, P.R.China)

Abstract:In view of request overloading and high response time in cloud computing environments, inspired by the idea of the non-uniform window ant colony behavior, a new load balancing algorithm is proposed. We introduce a working hypothesis that any virtual machine is under the condition of overloading, that is, the service provider has to allocate resources. According to the assumption, the available resources are optimized, where the dynamic and static agents are processed at the same time, and the ant colony behavior is used for load balance. System balance is achieved by means of loading resources into all virtual machines. The CloudSim simulation is used to emulator cloud environment for experiment analysis. Experimental results show that compared with load balancing of fault-tolerant cluster-aware(TCLB), scheduling strategy on load balancing(SSLB) and honey bee behavior inspired load balancing(HBB-LB)，the responsible time of the proposed algorithm is less than that of TCLB, SSLB and HBB-LB by 37%, 8% and 4% respectively. And the maximum completion time is also reduced significantly with overall improved performance.

Keywords：cloud computing; load balancing; agents; ant colony behavior; responsible time; maximum completion time