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

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

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

中圖分類號： TP311 ? ? ?文獻標志碼： 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 引言

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

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

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

1 布谷鳥搜索算法

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

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

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

（3） 鳥巢數量固定不變，鳥巢主發現布谷鳥鳥蛋概率為pa固定不變。

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

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

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

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

（3）式中，xbest表示當前最優解，即最優的布谷鳥巢位置。

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

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

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

3 基于布谷鳥搜索算法的云計算資源負載分配設計3.1 云計算的體系結構

云計算的系統結構如圖2所示。

從圖2可以看出，云計算的系統結構包括：云應用、用戶層中間件、核心中間件、系統級，具體描述如下：

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

（2） 用戶層中間件，該層包括軟件結構，是用戶接口。

（3） 核心中間件，該層用于支持管理用戶級應用服務的工作環境。

（4） 系統級，該層包括大量的物理資源，用于支持數據中心。

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

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

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

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

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

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

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

（8）式中，Cexe和Cdur分別表示云計算資源執行和和傳輸的功耗。

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

（1） 根據云計算系統的資源和負載建立云計算資源負載分配的模型。

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

（3） 計算每一個鳥巢位置的適應度值，本文選擇執行完負載的功耗和，云計算系統處理所有負載的時間作為適應度函數，并保留最優鳥巢位置。

（4） 迭代次數增加。

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

（6） 計算新的一組鳥巢位置的適應度值，保留適應度較優的鳥巢位置。

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

（8） 根據最優鳥巢位置得到云計算資源負載分配方案。

4 仿真模擬測試

4.1 云計算系統的相關設置

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

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

4.2 結果與分析

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

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

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

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

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

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

4 總結

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

參考文獻

[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]. 中國電子科學研究院學報， 2018，13（3）：308-314.

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

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

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

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

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

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

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

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

[11] 馮小靖，潘郁. 云計算環境下的DPSO資源負載均衡算法[J].計算機工程與應用， 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-），男，漢，廣東吳川人，碩士，計師，研究方向：電子與通信技術。文章編號：1007-757X（2020）02-0141-04