基于布谷鳥搜索算法的云計(jì)算資源負(fù)載分配研究

摘 要： 資源負(fù)載分配是云計(jì)算領(lǐng)域的重要研究方向，當(dāng)前云計(jì)算資源負(fù)載分配算法難以得到最合理的分配方案，導(dǎo)致部分云計(jì)算資源上存在負(fù)載過(guò)重或者空負(fù)載現(xiàn)象，云計(jì)算資源利用率低。為了解決當(dāng)前云計(jì)算資源負(fù)載分配算法存在的局限性，提出基于布谷鳥搜索算法的云計(jì)算資源負(fù)載分配算法。首先分析當(dāng)前云計(jì)算資源負(fù)載分配算法的研究進(jìn)展，建立云計(jì)算資源負(fù)載分配模型，然后利用具有模擬鳥群群集行為和特征的布谷鳥搜索算法對(duì)其進(jìn)行求解，根據(jù)最優(yōu)鳥巢位置得到云計(jì)算資源負(fù)載分配方案，最后采用CloudSim軟件實(shí)現(xiàn)了云計(jì)算資源負(fù)載分配仿真測(cè)試實(shí)驗(yàn)。結(jié)果表明，相當(dāng)于當(dāng)前其它云計(jì)算資源負(fù)載分配算法，布谷鳥搜索算法的求解效率得到了明顯提升，求解精度也得到了相應(yīng)的改善，可以保證云計(jì)算資源上分配的負(fù)載十分均衡，提高了云計(jì)算資源負(fù)載利用率，降低了云計(jì)算系統(tǒng)的運(yùn)行成本。

關(guān)鍵詞： 云計(jì)算資源; 負(fù)載分配; 鳥群群集行為; 求解效率; 最合理分配方案

中圖分類號(hào)： TP311 ? ? ?文獻(xiàn)標(biāo)志碼： A

Research on Cloud Computing Resource Load Allocation

Based on Cuckoo Search Algorithms

LI Bo

（Institute of Intelligent Manufacturing， Guangdong Nanfang Institute of Technology， Jiangmen 529000）

Abstract： Resource load allocation is an important research direction in the field of cloud computing. Current cloud computing resource load allocation algorithms are difficult to obtain the most reasonable allocation scheme， which results in overload or empty load on some cloud computing resources and low utilization rate of cloud computing resources. In order to solve the limitations of current cloud computing resource load allocation algorithm， a cloud computing resource load allocation algorithm based on Cuckoo search algorithm is proposed. Firstly， the current research progress of cloud computing resource load allocation algorithms is analyzed， and model of cloud computing resource load allocation is established. Then， the Cuckoo search algorithm with simulated bird swarm behavior and characteristics is used to solve the problem. According to the optimal nest location， the cloud computing resource load allocation scheme is obtained. Finally， CloudSim software is used to realize simulation test of cloud computing resource load allocation. The results show that the efficiency and accuracy of Cuckoo search algorithm have been improved significantly， which can ensure that the load allocated on cloud computing resources is very balanced. It improves the load utilization of cloud computing resources and reduces the cloud computing system operation cost compared with other cloud computing resource load allocation algorithms.

Key words： Cloud computing resources; Load allocation; Bird clustering behavior; Solution efficiency; Optimal allocation scheme

0 引言

隨著互聯(lián)網(wǎng)技術(shù)的發(fā)展，網(wǎng)絡(luò)用戶數(shù)量急劇增多，數(shù)據(jù)呈現(xiàn)爆炸性增長(zhǎng)，當(dāng)前已經(jīng)進(jìn)入了“大數(shù)據(jù)時(shí)代”，傳統(tǒng)計(jì)算機(jī)系統(tǒng)無(wú)法滿足大數(shù)據(jù)處理的要求，“云計(jì)算技術(shù)”應(yīng)運(yùn)而生。云計(jì)算技術(shù)包含許多技術(shù)，如：網(wǎng)格計(jì)算、虛擬化計(jì)算、分布式計(jì)算等，將不同地理位置的資源連接成一個(gè)虛擬化資源池，用戶可以根據(jù)自己的需求花費(fèi)得到相應(yīng)的服務(wù)[1]。在云計(jì)算技術(shù)的實(shí)際應(yīng)用中，一些問(wèn)題不斷出現(xiàn)，如云計(jì)算龐大的資源規(guī)模，而用戶需求各異，如何提高云計(jì)算資源率，更好為客戶服務(wù)是云計(jì)算資源負(fù)載分配必須面對(duì)的問(wèn)題，因此設(shè)計(jì)性能更好的云計(jì)算資源負(fù)載分配算法是人們一直努力的方向[2，3]。

最初，云計(jì)算資源負(fù)載分配算法沿用網(wǎng)絡(luò)計(jì)算資源分配算法，如Min-min算法，以服務(wù)費(fèi)用最小為目標(biāo)，將負(fù)載分配到一些性能較高的云計(jì)算資源上，由于網(wǎng)絡(luò)計(jì)算資源和云計(jì)算資源存在一定的差別，如：約束條件多、優(yōu)化目標(biāo)多樣性，因此Min-min算法得到的云計(jì)算資源負(fù)載分配方案并非最優(yōu)，從而造成用戶需求得不到滿足，云計(jì)算資源負(fù)載不均衡等問(wèn)題[4]。隨后，許多學(xué)者投身于云計(jì)算資源負(fù)載分配問(wèn)題的研究中，涌現(xiàn)出了許多云計(jì)算資源負(fù)載分配算法。當(dāng)前云計(jì)算資源負(fù)載分配算法可以劃為2類：靜態(tài)算法和動(dòng)態(tài)算法，靜態(tài)算法主要有：輪詢法、加權(quán)輪轉(zhuǎn)調(diào)度算法，它們以云計(jì)算資源負(fù)載均衡為目標(biāo)，采用先來(lái)先服務(wù)的規(guī)則，將負(fù)載分配到不同的云計(jì)算資源上，該類算法的工作過(guò)程十分簡(jiǎn)單，但是它們假設(shè)云計(jì)算資源上負(fù)載呈現(xiàn)一種靜態(tài)變化特點(diǎn)，這與實(shí)際情況不相符合，因此局限性十分明顯[5-7]。動(dòng)態(tài)算法可以適應(yīng)云計(jì)算資源上負(fù)載變化的特點(diǎn)，成為當(dāng)前一個(gè)主要的研究方向，其將云計(jì)算資源負(fù)載分配問(wèn)題看作為一個(gè)含有復(fù)雜約束條件的組合優(yōu)化問(wèn)題，然后通過(guò)啟發(fā)式算法來(lái)解決該問(wèn)題，如：基于粒子群優(yōu)化算法的云計(jì)算資源負(fù)載分配算法、基于各種改進(jìn)粒子群優(yōu)化算法的云計(jì)算資源負(fù)載分配算法，這些動(dòng)態(tài)算法可以得到較好的云計(jì)算資源負(fù)載分配方案[8-10]。在實(shí)際應(yīng)用中，由于云計(jì)算資源負(fù)載分配問(wèn)題是一個(gè)典型NP-hard問(wèn)題，粒子群優(yōu)化算法存在易出現(xiàn)早熟現(xiàn)象、時(shí)間復(fù)雜度過(guò)髙，獲得局部最優(yōu)的云計(jì)算資源負(fù)載分配方案概率高等缺陷[11]。

針對(duì)當(dāng)前云計(jì)算資源負(fù)載分配過(guò)程中存在的負(fù)載嚴(yán)重不均衡、云計(jì)算資源利用率低等難題，提出基于布谷鳥搜索算法的云計(jì)算資源負(fù)載分配算法，并采用具體云計(jì)算資源負(fù)載分配仿真測(cè)試實(shí)驗(yàn)分析了其性能。結(jié)果表明，布谷鳥搜索算法的求解效率高，可以快速得到云計(jì)算資源負(fù)載分配最優(yōu)方案，使云計(jì)算資源上分配負(fù)載均衡，而且性能要明顯優(yōu)于其它云計(jì)算資源負(fù)載分配算法，具有更好的實(shí)際應(yīng)用價(jià)值。

1 布谷鳥搜索算法

布谷鳥將自己蛋放入其它鳥類的巢中，讓它們幫助其哺育幼鳥，是一種典型寄生育雛行為。布谷鳥首先會(huì)觀察其它鳥類的鳥巢，通過(guò)Lévy flights選擇一個(gè)鳥巢，然后將自己蛋放在該鳥巢中，因此根據(jù)布谷鳥的寄生育雛行為提出了布谷鳥搜索算法[12]。為了模擬布谷鳥的寄生育雛行為，布谷鳥搜索算法設(shè)定了3個(gè)理想狀態(tài)，具體如下：

（1） 布谷鳥1次只能生1個(gè)蛋，隨機(jī)選擇其它鳥類的鳥巢進(jìn)行孵化;

（2） 最好的鳥巢會(huì)被保存到下一代;

（3） 鳥巢數(shù)量固定不變，鳥巢主發(fā)現(xiàn)布谷鳥鳥蛋概率為pa固定不變。

對(duì)于一個(gè)待解決的問(wèn)題，鳥巢位置為一個(gè)d 維向量X=（x1，x2，…，xd），其代表問(wèn)題的一個(gè)可行解，鳥巢位置的好壞由適應(yīng)度來(lái)評(píng)價(jià)，布谷鳥尋找適合自己的鳥巢方式為式（1）。Xt+1i=Xti+α⊕Levy（λ） i=1，2，…，n

（1）式中，t表示迭代次數(shù)，⊕表示點(diǎn)積運(yùn)算;α表示布谷鳥搜索步長(zhǎng)，Levy（λ）表示Lévy 分布，其滿足條件為式（2）。Levy（λ）～t-λ， 1<λ<3

（2）式中，λ表示Lévy分布的步長(zhǎng)參數(shù)。

谷鳥搜索步長(zhǎng)的變化方式為式（3）。a=a0（xti-xbest）

（3）式中，xbest表示當(dāng)前最優(yōu)解，即最優(yōu)的布谷鳥巢位置。

測(cè)評(píng)通過(guò)Lévy flights方式更新鳥巢位置后，根據(jù)Pa丟棄一些新鳥巢位置，并采用如下方式對(duì)鳥巢位置進(jìn)行更新為式（4）。Xt+1i=Xti+rand·（Xtk-Xtj） i=1，2，…，n

（4）式中，Xtk和Xtj表示兩個(gè)鳥巢，rand表示縮放因子，是一個(gè)（0 1）區(qū)間的隨機(jī)數(shù)。

布谷鳥搜索算法的工作流程如圖1所示。

3 基于布谷鳥搜索算法的云計(jì)算資源負(fù)載分配設(shè)計(jì)3.1 云計(jì)算的體系結(jié)構(gòu)

云計(jì)算的系統(tǒng)結(jié)構(gòu)如圖2所示。

從圖2可以看出，云計(jì)算的系統(tǒng)結(jié)構(gòu)包括：云應(yīng)用、用戶層中間件、核心中間件、系統(tǒng)級(jí)，具體描述如下：

（1） 云應(yīng)用，該層由云提供商提供，包括了直接對(duì)終端用戶可用的應(yīng)用。

（2） 用戶層中間件，該層包括軟件結(jié)構(gòu)，是用戶接口。

（3） 核心中間件，該層用于支持管理用戶級(jí)應(yīng)用服務(wù)的工作環(huán)境。

（4） 系統(tǒng)級(jí)，該層包括大量的物理資源，用于支持?jǐn)?shù)據(jù)中心。

3.2 云計(jì)算資源負(fù)載分配的模型

云計(jì)算資源負(fù)載分配是指在滿足一定的約束條件下，將待處理的一些負(fù)載分配到多個(gè)云計(jì)算資源上，并在云計(jì)算資源上執(zhí)行負(fù)載。最優(yōu)的云計(jì)算資源負(fù)載分配方案應(yīng)該滿足：（1） 滿足用戶對(duì)負(fù)載完成的時(shí)間;（2） 根據(jù)負(fù)載和云計(jì)算資源特點(diǎn)，將負(fù)載分配到最合理的云計(jì)算資源上執(zhí)行，這兩點(diǎn)相互制約，因?yàn)橥瓿韶?fù)載的時(shí)間越短，需要的云計(jì)算資源會(huì)越多，整個(gè)云計(jì)算系統(tǒng)的功耗相應(yīng)增加。設(shè)負(fù)載和云計(jì)算資源的集合分別為：X={x1，x2，…，tn}和Y={y1，y2，…，ym}，第i個(gè)負(fù)載在第j個(gè)云計(jì)算資源上的預(yù)期執(zhí)行時(shí)間為Texe（i，j），則有式（5）。Texe（i，j）=xlon（i）/Ycal（j）

（5）式中，xlon（i）表示i個(gè)負(fù)載的大小，Ycal（j）表示第j個(gè)云計(jì)算資源的執(zhí)行速度。

第j個(gè)云計(jì)算資源完成第i個(gè)負(fù)載的所花費(fèi)的總時(shí)間為式（6）。Tsum（i，j）=Texe（i，j）+Tdur（i，j）

（6）式中，Tdur（i，j）表示第i個(gè)負(fù)載傳輸?shù)降趈個(gè)云計(jì)算資源需要的時(shí)間。

云計(jì)算資源能夠采用并行運(yùn)行模式，云計(jì)算系統(tǒng)處理所有負(fù)載的時(shí)間為式（7）。Tcos=max∑nj=1∑mi=1Tsum（i，j）

（7） ?執(zhí)行完負(fù)載的功耗計(jì)算公式為式（8）。Ccos=∑nj=1 ∑mi=1Texe（i，j）×Cexe+Tdur（i，j）×Cdur

（8）式中，Cexe和Cdur分別表示云計(jì)算資源執(zhí)行和和傳輸?shù)墓摹?/p>

3.3 基于布谷鳥搜索算法的云計(jì)算負(fù)載分配步驟

（1） 根據(jù)云計(jì)算系統(tǒng)的資源和負(fù)載建立云計(jì)算資源負(fù)載分配的模型。

（2） 初始化布谷鳥搜索算法的鳥巢位置，每一個(gè)布谷鳥的鳥巢位置表示一種云計(jì)算資源負(fù)載分配可行分配方案。

（3） 計(jì)算每一個(gè)鳥巢位置的適應(yīng)度值，本文選擇執(zhí)行完負(fù)載的功耗和，云計(jì)算系統(tǒng)處理所有負(fù)載的時(shí)間作為適應(yīng)度函數(shù)，并保留最優(yōu)鳥巢位置。

（4） 迭代次數(shù)增加。

（5） 隨機(jī)產(chǎn)生1個(gè)數(shù)，并與巢主發(fā)現(xiàn)布谷鳥鳥蛋概率進(jìn)行比較，如該數(shù)大于巢主發(fā)現(xiàn)布谷鳥鳥蛋概率，那么對(duì)鳥巢位置進(jìn)行更新操作，不然，鳥巢位置不變，從而產(chǎn)生新的一組鳥巢位置。

（6） 計(jì)算新的一組鳥巢位置的適應(yīng)度值，保留適應(yīng)度較優(yōu)的鳥巢位置。

（7） 如果迭代次數(shù)達(dá)到最大迭代次數(shù)，就執(zhí)行步驟（8），不然返回步驟（4）。

（8） 根據(jù)最優(yōu)鳥巢位置得到云計(jì)算資源負(fù)載分配方案。

4 仿真模擬測(cè)試

4.1 云計(jì)算系統(tǒng)的相關(guān)設(shè)置

Cloudsim是通過(guò)java語(yǔ)言編寫的云計(jì)算環(huán)境的工具庫(kù)，采用作為云計(jì)算資源負(fù)載分配的仿真軟件，云計(jì)算資源負(fù)載分配程序通過(guò)java語(yǔ)言編程實(shí)現(xiàn)。負(fù)載數(shù)量為30～350，云計(jì)算資源數(shù)量為：40個(gè)，布谷鳥搜索算法參數(shù)設(shè)置如表1所示。

選擇文獻(xiàn)[11]的云計(jì)算資源負(fù)載分配算法進(jìn)行對(duì)比實(shí)驗(yàn)。

4.2 結(jié)果與分析

不同負(fù)載數(shù)量的條件下，兩種云計(jì)算資源負(fù)載分配算法找到最優(yōu)方案的迭代次數(shù)變化曲線如圖3所示。

從圖3可以看出，隨著負(fù)載數(shù)量的增加，迭代次數(shù)不斷的增加，當(dāng)負(fù)載數(shù)量較小時(shí)，兩種算法的迭代次數(shù)相差不大，但當(dāng)負(fù)載數(shù)量比較大時(shí)，布谷鳥搜索算法的迭代次數(shù)少于文獻(xiàn)[11]算法，從而加快了找到云計(jì)算資源負(fù)載分配最優(yōu)方案的速度，驗(yàn)證了布谷鳥搜索算法的有效性。

不同負(fù)載數(shù)量條件下，兩種云計(jì)算資源負(fù)載分配算法的功耗變化曲線如圖4所示。

從圖4可以看出，隨著負(fù)載數(shù)量增加，布谷鳥搜索算法的功耗增長(zhǎng)幅度小，而文獻(xiàn)[11]算法的功耗增長(zhǎng)幅度較大，說(shuō)明布谷鳥搜索算法找到更優(yōu)的云計(jì)算資源負(fù)載分配方案的運(yùn)行成本更低，驗(yàn)證了布谷鳥搜索算法的優(yōu)越性。

不同負(fù)載數(shù)量的條件下，兩種云計(jì)算資源負(fù)載分配算法的資源負(fù)載率最大值變化曲線如圖5所示。

從圖5可以看出，隨著負(fù)載數(shù)量增加，兩種算法的資源負(fù)載率最大值上升，但是在相同的負(fù)載數(shù)量條件下，布谷鳥搜索算法的資源負(fù)載率最大值始終小于文獻(xiàn)[11]算法，沒(méi)有出現(xiàn)負(fù)載過(guò)高的云計(jì)算資源，便資源上的負(fù)載分配更加合理，提高了云計(jì)算資源利用率。

4 總結(jié)

資源負(fù)載分配是云計(jì)算領(lǐng)域的重要研究方向，為了解決當(dāng)前云計(jì)算資源負(fù)載分配算法存在的局限性，提出基于布谷鳥搜索算法的云計(jì)算資源負(fù)載分配算法。首先建立云計(jì)算資源負(fù)載分配的模型，然后利用布鳥搜索算法對(duì)其進(jìn)行求解，得到云計(jì)算資源負(fù)載分配方案，仿真測(cè)試實(shí)驗(yàn)結(jié)果表明，布谷鳥搜索算法可以快速找到云計(jì)算資源負(fù)載最優(yōu)分配方案，確保整個(gè)云計(jì)算系統(tǒng)具有較好的負(fù)載均衡狀態(tài)。

參考文獻(xiàn)

[1] Buyya R， Yeo C S， Venugopal S， et al. Cloud computing and emerging IT platforms： Vision， hype， and reality for delivering computing as the 5th utility[J]. Future Generation Computer Systems， 2009， 25（6）： 599-661.

[2] 姜棟瀚，林海濤. 云計(jì)算環(huán)境下的資源分配關(guān)鍵技術(shù)研究綜述[J]. 中國(guó)電子科學(xué)研究院學(xué)報(bào)， 2018，13（3）：308-314.

[3] 周墨頌，董小社，陳衡，等. 基于計(jì)算資源運(yùn)行時(shí)剩余能力評(píng)估優(yōu)化云平臺(tái)[J]. 計(jì)算機(jī)研究與發(fā)展，2017，54（11）：2516-2533.

[4] 劉小銘，李宗輝，王俊杰，等. 云計(jì)算中時(shí)間感知應(yīng)用的資源分配與調(diào)度算法[J].西南師范大學(xué)學(xué)報(bào)（自然科學(xué)版）， 2017， 42（7）： 46-53.

[5] 朱新峰，張智浩，王彥凌. 移動(dòng)邊緣計(jì)算環(huán)境下的動(dòng)態(tài)資源分配策略[J]. 計(jì)算機(jī)工程與科學(xué)， 2019， 41（7）：1184-1190.

[6] 李杰，張靜，李偉東，等. 一種基于共享公平和時(shí)變資源需求的公平分配策略[J]. 計(jì)算機(jī)研究與發(fā)展，2019，56（7）：1534-1544.

[7] 陳欽榮，劉順來(lái)，林錫彬. 一種混合優(yōu)化的云計(jì)算資源調(diào)度算法[J]. 韓山師范學(xué)院學(xué)報(bào)， 2016，37（6）：15-23.

[8] 趙宏偉. 基于改進(jìn)粒子群算法的云計(jì)算資源調(diào)度模型的研究[J]. 沈陽(yáng)大學(xué)學(xué)報(bào)（自然科學(xué)版）， 2015，27（6）：507-511.

[9] 謝輔雯，張敏. 基于改進(jìn)型離散粒子群優(yōu)化的云計(jì)算資源分配方案[J]. 湘潭大學(xué)自然科學(xué)學(xué)報(bào)，2017，39（3）：89-93.

[10] 周麗娟，王春影. 基于粒子群優(yōu)化算法的云計(jì)算資源調(diào)度策略研究[J]. 計(jì)算機(jī)科學(xué)， 2015， 42（6） ：279-281.

[11] 馮小靖，潘郁. 云計(jì)算環(huán)境下的DPSO資源負(fù)載均衡算法[J].計(jì)算機(jī)工程與應(yīng)用， 2013， 49（6）：105-108.

[12] Yang X S， Deb S. Multi-objective Cuckoo search for design optimization [J]. Computers & Operations Research， 2013， 40（6）： 1616-1624.

（收稿日期： 2019.07.01）

作者簡(jiǎn)介：李波（1983-），男，漢，廣東吳川人，碩士，計(jì)師，研究方向：電子與通信技術(shù)。文章編號(hào)：1007-757X（2020）02-0141-04