李霞，彭浩

（鄭州輕工業(yè)學(xué)院計算機(jī)與通信工程學(xué)院，鄭州　450001）

基于局部擇優(yōu)隨機(jī)爬坡算法的云計算負(fù)載策略研究

李霞，彭浩

（鄭州輕工業(yè)學(xué)院計算機(jī)與通信工程學(xué)院，鄭州450001）

0　引言

隨著互聯(lián)網(wǎng)技術(shù)快速發(fā)展且和廣泛應(yīng)用，云計算作為一種新興的計算體系正逐漸成為工業(yè)界和學(xué)術(shù)界的熱門話題，云計算旨在提供一種能夠滿足普通社會團(tuán)體日常需要的計算功能。在全世界范圍內(nèi)云計算的的基礎(chǔ)設(shè)施被商業(yè)與個人用戶用來獲取應(yīng)用服務(wù)，因此云計算代表動態(tài)提供計算服務(wù)的新范式。通常來說云計算服務(wù)是由大量網(wǎng)絡(luò)虛擬機(jī)組成的頂級數(shù)據(jù)中心來提供支持，云計算是一個分布式的計算機(jī)制，這種機(jī)制利用高速網(wǎng)絡(luò)將作業(yè)由個人PC端轉(zhuǎn)移至遠(yuǎn)端計算機(jī)集群來進(jìn)行數(shù)據(jù)處理。

雖然云計算的前景很樂觀，但許多關(guān)鍵性問題仍需要解決來使云計算變?yōu)楝F(xiàn)實(shí)。負(fù)載均衡問題是其中之一，負(fù)載均衡為整個云分配任務(wù)量，在實(shí)現(xiàn)云計算的過程中他扮演一個非常重要的角色已經(jīng)成為不可或缺的部分。云服務(wù)提供商的負(fù)載均衡機(jī)制是能夠達(dá)到為消費(fèi)者構(gòu)建一個低成本且無限制的資源池并且具備組織計算資源的能力，這種能力表現(xiàn)在部署于數(shù)據(jù)中心的應(yīng)用上以及響應(yīng)用戶分配應(yīng)用請求上。

學(xué)界已經(jīng)有很多有關(guān)負(fù)載均衡算法的文章。Min-Min［2］調(diào)度算法在最小執(zhí)行時間（MET）內(nèi)運(yùn)用隨機(jī)命令將任務(wù)分配在能夠最快執(zhí)行的節(jié)點(diǎn)上，算法的核心思想是為每一個非計劃任務(wù)估算最小完成時間，然后這些任務(wù)將被分配到能夠以最短時間完成的節(jié)點(diǎn)上。輪詢調(diào)度算法（RR）［3］簡單分配所有位于數(shù)據(jù)中心和處理單元的進(jìn)程。文章為負(fù)載均衡提出的局部擇優(yōu)隨機(jī)爬坡算法能夠使可用資源最大限度最優(yōu)化的使用。運(yùn)用云分析軟件CloudSim［4-5］對上述算法進(jìn)行模擬和分析，從與輪訓(xùn)調(diào)度算法和先來先服務(wù)算法的對比研究結(jié)果中證明局部擇優(yōu)隨機(jī)爬坡算法的優(yōu)勢。

1　云仿真軟件CloudSim簡介

1.1云計算仿真實(shí)驗(yàn)存在的問題

云計算要求將大規(guī)模的應(yīng)用部署變得更簡潔便宜，這就為研究者制造了很多新問題。測試新問題需要一些測試平臺。并且云基礎(chǔ)設(shè)施是分布式的，應(yīng)用程序也部署在不同的地理位置。對系統(tǒng)規(guī)模、資源調(diào)度分配策略和性能等指標(biāo)進(jìn)行重復(fù)可伸縮的試驗(yàn)來對不同應(yīng)用模式進(jìn)行量化、評價是非常困難的［4］。為此，需要一個云計算環(huán)境的分布式系統(tǒng)模擬器來實(shí)現(xiàn)云計算試驗(yàn)的模擬，降低研究測試門檻和成本。

1.2CloudSim的優(yōu)勢及其基礎(chǔ)架構(gòu)

CloudSim提供云計算的特性，支持云計算資源的管理和調(diào)度模擬。云計算最大的特點(diǎn)是：采用成熟的虛擬化技術(shù)，將數(shù)據(jù)中心的資源虛擬化為資源池，打包對外象用戶提供服務(wù)。CloudSim恰好體現(xiàn)此特點(diǎn)，擴(kuò)展部分實(shí)現(xiàn)一系列接口，提供基于數(shù)據(jù)中心的虛擬化技術(shù)、虛擬化云的建模和仿真功能。此外CloudSim將仿真實(shí)驗(yàn)練習(xí)和編程實(shí)現(xiàn)分離，因此研究人員可以更多的關(guān)注仿真的復(fù)雜性而不需要在編程技巧上花費(fèi)太多的時間。云仿真工具包的體系架構(gòu)如圖1所示。

圖1　Simulation configuration

2　基于局部擇優(yōu)隨機(jī)爬坡算法的負(fù)載均衡

負(fù)載均衡是依靠將總負(fù)載重新分到集成系統(tǒng)的各個節(jié)點(diǎn)上來提升資源利用率的過程，也是提高作業(yè)時間的過程。負(fù)載均衡開發(fā)策略的要點(diǎn)是對負(fù)載的預(yù)測、負(fù)載的對比比較以及不同系統(tǒng)的穩(wěn)定性、系統(tǒng)性能、節(jié)點(diǎn)間的交互、作業(yè)屬性的轉(zhuǎn)換、節(jié)點(diǎn)的選擇等方面的優(yōu)化。這種負(fù)載被認(rèn)為是CPU負(fù)荷、內(nèi)存使用量、延遲和網(wǎng)絡(luò)負(fù)載。

負(fù)載均衡算法可以是分布式的也可以是集中的。我們的算法采用集中方式：算法依靠系統(tǒng)中的核心節(jié)點(diǎn)來執(zhí)行［6］。該節(jié)點(diǎn)獨(dú)立負(fù)責(zé)整個系統(tǒng)的負(fù)載。其他節(jié)點(diǎn)與核心節(jié)點(diǎn)相互作用，相對于分布式的方案，由于系統(tǒng)中總體交互量的大幅度降低，集中式的負(fù)載均衡方案能夠以更少的信息量來傳達(dá)指令。然而存在兩個缺點(diǎn)：第一，集中式算法在中心節(jié)點(diǎn)會引發(fā)系統(tǒng)瓶頸，第二，一旦中心節(jié)點(diǎn)崩潰，負(fù)載均衡進(jìn)程就會出現(xiàn)不可用狀態(tài)。第一個缺點(diǎn)的解決方案是將負(fù)載分布地更加有效即在可用服務(wù)器之間分配負(fù)載以獲得最有效的吞吐量的優(yōu)化問題。

解決優(yōu)化問題較為完整的算法必須具備這樣的特征：能夠保證找到一個可用的賦值給變量或者能夠證明沒有這樣的賦值存在；性能高效穩(wěn)定并且能夠?yàn)樗杏脩舻妮斎胩峁┮粋€準(zhǔn)確的和最優(yōu)的的答案。但是缺點(diǎn)在于，當(dāng)工作環(huán)境比較惡劣的情況下這些算法的執(zhí)行時間呈指數(shù)級的增長，在云計算領(lǐng)域這是不能夠被接受的。其他的不完整的算法不能夠保證為所有用戶輸入提供正確答案，但這些方法能夠以較高概率針對可解問題找到滿足條件的賦值。近年來這些算法應(yīng)用很普及源于他們簡潔、快速以及在解決特定問題時所表現(xiàn)出的客觀效能。爬坡算法的變體局部擇優(yōu)隨機(jī)爬坡算法是解決此類優(yōu)化問題的一種不完全的算法。隨機(jī)局部優(yōu)化算法是一個值持續(xù)不斷增加的向上的環(huán)［7］。當(dāng)值達(dá)到頂峰時周圍沒有更高值出現(xiàn)時停止。在爬坡運(yùn)動和選擇概率的隨機(jī)性上，多樣化選擇會隨著爬坡運(yùn)動的梯度變化而變化。因此局部擇優(yōu)隨機(jī)爬坡算法通過對原始任務(wù)進(jìn)行細(xì)微的改變來將任務(wù)分配到一組作業(yè)中去，這組作業(yè)中的每個元素根據(jù)既定的條件來進(jìn)行評測并向有效進(jìn)程靠近以提高此種狀態(tài)下的評測值，該組作業(yè)中最優(yōu)的元素被定為下一個要執(zhí)行的任務(wù)，以上過程被重復(fù)執(zhí)行直到找到解決方案或者達(dá)到停止條件［8］。因此局部擇優(yōu)隨機(jī)爬坡算法包含兩個組件，一個是備選生成器能夠?qū)溥x解決方案匹配給一組可能的繼任者，另一個是評測條件生成器能夠?qū)⒚總€有效的解決方案劃分等級，如此，這種評測機(jī)制能夠找到更好的解決方案。

上述算法的描述過程如下：

（1）維護(hù)虛擬機(jī)的索引表和虛擬機(jī)的工作狀態(tài)（忙碌/可用），開始時所有虛擬機(jī)都是可用狀態(tài)。

（2）新任務(wù)進(jìn)入云任務(wù)池［9］。

（3）為下一個分配生成查詢。

（4）隨機(jī)產(chǎn)生一個虛擬機(jī)ID。

（5）如果虛擬機(jī)已經(jīng)被分配，就分析配置表來獲取特定虛擬機(jī)的狀態(tài)。

①返回虛擬機(jī)ID。

②發(fā)送請求給由ID標(biāo)識的虛擬機(jī)。

③如果虛擬機(jī)已經(jīng)被分配則根據(jù)分配情況來更新配置表。

④運(yùn)用隨機(jī)函數(shù)來生成一個隨機(jī)虛擬機(jī)。

⑤依據(jù)概率因子為任務(wù)分配虛擬機(jī)，如此能夠更有效的處理任務(wù)。

⑥如果已分配虛擬機(jī)的性能不如預(yù)期則記錄下來，在下一次迭代中降低分配該虛擬機(jī)的概率。

⑦當(dāng)虛擬機(jī)完成請求處理并且微云接收到處理結(jié)果時生成已撤銷虛擬機(jī)分配的通知。

⑧從第二步開始重復(fù)執(zhí)行為下一次分配準(zhǔn)備。

3　仿真結(jié)果分析

云仿真軟件用于算法測試，考慮到位于云端的應(yīng)用將運(yùn)行在電子競拍和社交網(wǎng)站如Facebook、google+等大型網(wǎng)站上，設(shè)計相應(yīng)的仿真配置。

3.1仿真配置

選定來自世界六個主要大陸用戶群表1，為了簡便起見每個用戶群都在一個時區(qū)內(nèi)并且假設(shè)該用戶群中已注冊的用戶有超過5%的在高峰時間段同時在線，只有10%的用戶在非高峰時間段內(nèi)在線，此外每個用戶每5分鐘發(fā)送一次請求，每個仿真數(shù)據(jù)中心都寄宿于特定數(shù)量的虛擬機(jī)上，這些虛擬機(jī)為應(yīng)用程序服務(wù)。虛擬機(jī)的配置：4GB RAM、100GB Storage、4CPUs。實(shí)驗(yàn)用戶群的規(guī)格描述如表1。

表1

3.2仿真場景

為了達(dá)到仿真目標(biāo)，應(yīng)該考慮多個仿真場景，從單一集中式云開始，數(shù)據(jù)中心是社交網(wǎng)絡(luò)的載體，因此全球范圍內(nèi)的用戶的請求都被這唯一一個數(shù)據(jù)中心處理。數(shù)據(jù)中心有25、50和70臺虛擬機(jī)分布于各種云配置的應(yīng)用上。這種仿真場景如表2（a）所示。

在第二種場景中，我們考慮兩個數(shù)據(jù)中心，期初每個數(shù)據(jù)中心在三種云配置下分別為應(yīng)用部署25、50、75臺虛擬機(jī)。然后每個數(shù)據(jù)中心在三種云配置下分別為應(yīng)用部署25和50臺虛擬機(jī)；25臺和75虛擬機(jī)；50和75臺虛擬機(jī)如表表2（b）所示。在考慮三個數(shù)據(jù)中心的情況下，期初每個數(shù)據(jù)中心在三種云配置下分別部署25、50、75臺虛擬機(jī)。此外分別為每個數(shù)據(jù)中心混合部署25、50和75臺虛擬機(jī)。如表3（a）。

表2

第四種情況與第三種情況相似，只是在六個數(shù)據(jù)中心的情況下進(jìn)行。如表3（b），表4（a）和表4（b）中顯示。

表3

表4

3.3結(jié)果

在前面所描述的方案和配置下，隨機(jī)爬坡算法、輪訓(xùn)調(diào)度算法、先進(jìn)先服務(wù)算法的總體平均響應(yīng)時間的結(jié)果在表2（a），2（b），3（a），3（b），4（a），4（b）中顯示。表2（a），2（b），3（a），3（b），4（a），4（b）以圖形綜述的形式描繪了隨機(jī)爬坡算法與輪訓(xùn)調(diào)度算法的性能對比。在大部分的實(shí)例中隨機(jī)爬坡算法的性能表現(xiàn)都優(yōu)異于另外兩種算法。

4　結(jié)語

本文研究了將爬坡算法的改進(jìn)算法局部擇優(yōu)隨機(jī)爬坡算法應(yīng)用于云計算負(fù)載均衡策略中，在四種不同虛擬機(jī)部署場景中將此改進(jìn)算法與傳統(tǒng)調(diào)度算法輪詢調(diào)度（RR）與先到先服務(wù)算法（FCFS）橫向?qū)Ρ葘?shí)驗(yàn)得出三種算法下虛擬機(jī)響應(yīng)時間數(shù)據(jù)如圖2，通過數(shù)據(jù)可以證明局部擇優(yōu)隨機(jī)爬坡算法在一個數(shù)據(jù)中心的情況下響應(yīng)時間優(yōu)勢不明顯，但隨著數(shù)據(jù)中心的增加響應(yīng)時間相較另外兩種算法優(yōu)勢顯著，響應(yīng)時間大幅度降低，效能提升可觀。

圖2

［1］楊靖琦.云化業(yè)務(wù)平臺可伸縮性研究［D］.北京.北京郵電大學(xué)，2014.

［2］張瀾.網(wǎng)格環(huán)境下Min-Min調(diào)度算法改進(jìn)與實(shí)現(xiàn)［D］.鄭州.信息工程學(xué)院，2008.

［3］Karapici，Alban，F(xiàn)eka.The simulation of round robin and priority scheduling algorithm［C］.In Proceeding of the 12th International Conference on Information Technology-New Generations（ITNG），2015.

［4］王霞俊.基于CLOUDSIM平臺的云任務(wù)分配策略研究［J］.上海：微型電腦應(yīng)用，2013：59-60.

［5］查英華，楊靜麗.云計算仿真平臺CloudSim在資源分配研究中的應(yīng)用［J］.武漢：軟件導(dǎo)刊，2012：58-59.

［6］楊際祥，譚國真.一種大規(guī)模分布式計算負(fù)載均衡策略［J］.北京：電子學(xué)報，2012：2226-2227.

［7］單冬冬，呂強(qiáng).貝葉斯網(wǎng)學(xué)習(xí)中一種有效的爬山算法［J］.沈陽：小微型計算機(jī)系統(tǒng)，2009：2458-2459.

［8］Shams，B.，Khansari，M.Immunization of complex networks using stochastic hill-climbing algorithm［C］.In Proceeding of the 3th Computer and Knowledge Engineering（ICCKE），2013.

［9］陳波.云計算環(huán)境下負(fù)載均衡技術(shù)的研究［D］.無錫：江南大學(xué)，2014.

Cloud Computing;Loding Balance;Soft Computing;Stochastic Hill Climbing;CloudAnalyst

Load Balancing in Cloud Computing Using Stochastic Hill Climbing-A Approach
LI Xia，PENG Hao

（College of Computer and Communication Engineering，Zhengzhou University of Light Industry，Zhengzhou 450001）

1007-1423（2015）28-0003-06

10.3969/j.issn.1007-1423.2015.28.001

李霞（1962-），女，教授，研究方向?yàn)樵朴嬎?、分布式網(wǎng)格計算

2015-09-19

2015-09-29

以云計算的方式來執(zhí)行任務(wù)的過程中負(fù)載節(jié)點(diǎn)的選擇是非常關(guān)鍵的環(huán)節(jié)，從挖掘資源有效性的角度出發(fā)，負(fù)載節(jié)點(diǎn)必須根據(jù)任務(wù)屬性來合理選擇，提出一種負(fù)載均衡算法——局部擇優(yōu)的隨機(jī)爬坡算法，該算法用來為虛擬機(jī)或服務(wù)器分配即將運(yùn)行的調(diào)度作業(yè)，用云分析軟件對算法的性能進(jìn)行定量和定性的分析。將局部擇優(yōu)隨機(jī)爬坡算法與輪訓(xùn)調(diào)度算法和先進(jìn)先服務(wù)算法進(jìn)行對比分析來反映局部擇優(yōu)隨機(jī)爬坡算法在選擇負(fù)載節(jié)點(diǎn)優(yōu)化配置計算資源的優(yōu)越性。

云計算；負(fù)載均衡；軟計算；隨機(jī)爬坡算法；云分析

河南省科技攻關(guān)項目“智慧校園建設(shè)”（豫財政【2014】124號）

彭浩（1988-），男，河南信陽人，碩士研究生，研究方向?yàn)樵朴嬎?/p>

Utilizes the computing resources on the network to facilitate the execution of complicated tasks that requires large-scale computation.Se-lects nodes（load balancing）is crucial for executing a task in the cloud computing，and to exploit the effectiveness of the resources，they have to be properly selected according to the properties of the task.Proposes a soft computing based load balancing approach，uses a lo-cal optimization approach Stochastic Hill climbing for allocation of incoming jobs to the servers or virtual machines（VMs）.Analyzes per-formance of the algorithm both qualitatively and quantitatively using CloudAnalyst.Makes a comparison with Round Robin and First Come First Serve（FCFS）algorithms.The comparison reflect the advantage of local optimization approach Stochastic Hill climbing in se-lecting load balance node.