李霞，彭浩

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

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

李霞，彭浩

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

0　引言

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

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

學(xué)界已經(jīng)有很多有關(guān)負(fù)載均衡算法的文章。Min-Min［2］調(diào)度算法在最小執(zhí)行時(shí)間（MET）內(nèi)運(yùn)用隨機(jī)命令將任務(wù)分配在能夠最快執(zhí)行的節(jié)點(diǎn)上，算法的核心思想是為每一個(gè)非計(jì)劃任務(wù)估算最小完成時(shí)間，然后這些任務(wù)將被分配到能夠以最短時(shí)間完成的節(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云計(jì)算仿真實(shí)驗(yàn)存在的問題

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

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

CloudSim提供云計(jì)算的特性，支持云計(jì)算資源的管理和調(diào)度模擬。云計(jì)算最大的特點(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)太多的時(shí)間。云仿真工具包的體系架構(gòu)如圖1所示。

圖1　Simulation configuration

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

負(fù)載均衡是依靠將總負(fù)載重新分到集成系統(tǒng)的各個(gè)節(jié)點(diǎn)上來提升資源利用率的過程，也是提高作業(yè)時(shí)間的過程。負(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é)整個(gè)系統(tǒng)的負(fù)載。其他節(jié)點(diǎn)與核心節(jié)點(diǎn)相互作用，相對于分布式的方案，由于系統(tǒng)中總體交互量的大幅度降低，集中式的負(fù)載均衡方案能夠以更少的信息量來傳達(dá)指令。然而存在兩個(gè)缺點(diǎn)：第一，集中式算法在中心節(jié)點(diǎn)會引發(fā)系統(tǒng)瓶頸，第二，一旦中心節(jié)點(diǎn)崩潰，負(fù)載均衡進(jìn)程就會出現(xiàn)不可用狀態(tài)。第一個(gè)缺點(diǎn)的解決方案是將負(fù)載分布地更加有效即在可用服務(wù)器之間分配負(fù)載以獲得最有效的吞吐量的優(yōu)化問題。

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

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

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

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

（3）為下一個(gè)分配生成查詢。

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

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

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

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

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

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

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

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

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

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

3　仿真結(jié)果分析

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

3.1仿真配置

選定來自世界六個(gè)主要大陸用戶群表1，為了簡便起見每個(gè)用戶群都在一個(gè)時(shí)區(qū)內(nèi)并且假設(shè)該用戶群中已注冊的用戶有超過5%的在高峰時(shí)間段同時(shí)在線，只有10%的用戶在非高峰時(shí)間段內(nèi)在線，此外每個(gè)用戶每5分鐘發(fā)送一次請求，每個(gè)仿真數(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)該考慮多個(gè)仿真場景，從單一集中式云開始，數(shù)據(jù)中心是社交網(wǎng)絡(luò)的載體，因此全球范圍內(nèi)的用戶的請求都被這唯一一個(gè)數(shù)據(jù)中心處理。數(shù)據(jù)中心有25、50和70臺虛擬機(jī)分布于各種云配置的應(yīng)用上。這種仿真場景如表2（a）所示。

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

表2

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

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

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

［7］單冬冬，呂強(qiáng).貝葉斯網(wǎng)學(xué)習(xí)中一種有效的爬山算法［J］.沈陽：小微型計(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］陳波.云計(jì)算環(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)樵朴?jì)算、分布式網(wǎng)格計(jì)算

2015-09-19

2015-09-29

以云計(jì)算的方式來執(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)化配置計(jì)算資源的優(yōu)越性。

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

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

彭浩（1988-），男，河南信陽人，碩士研究生，研究方向?yàn)樵朴?jì)算

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.