基于布谷鳥搜索算法的云計算資源負載分配研究

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

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

中圖分類號： TP311 ? ? ?文獻標(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)爆炸性增長，當(dāng)前已經(jīng)進入了“大數(shù)據(jù)時代”，傳統(tǒng)計算機系統(tǒng)無法滿足大數(shù)據(jù)處理的要求，“云計算技術(shù)”應(yīng)運而生。云計算技術(shù)包含許多技術(shù)，如：網(wǎng)格計算、虛擬化計算、分布式計算等，將不同地理位置的資源連接成一個虛擬化資源池，用戶可以根據(jù)自己的需求花費得到相應(yīng)的服務(wù)[1]。在云計算技術(shù)的實際應(yīng)用中，一些問題不斷出現(xiàn)，如云計算龐大的資源規(guī)模，而用戶需求各異，如何提高云計算資源率，更好為客戶服務(wù)是云計算資源負載分配必須面對的問題，因此設(shè)計性能更好的云計算資源負載分配算法是人們一直努力的方向[2，3]。

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

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

1 布谷鳥搜索算法

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

（1） 布谷鳥1次只能生1個蛋，隨機選擇其它鳥類的鳥巢進行孵化;

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

3.2 云計算資源負載分配的模型

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

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

第j個云計算資源完成第i個負載的所花費的總時間為式（6）。Tsum（i，j）=Texe（i，j）+Tdur（i，j）

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

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

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

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

3.3 基于布谷鳥搜索算法的云計算負載分配步驟

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

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

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

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

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

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

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

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

4 仿真模擬測試

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

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

選擇文獻[11]的云計算資源負載分配算法進行對比實驗。

4.2 結(jié)果與分析

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

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

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

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

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

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

4 總結(jié)

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

參考文獻

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

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

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

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

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

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

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

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

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

[11] 馮小靖，潘郁. 云計算環(huán)境下的DPSO資源負載均衡算法[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）

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