基于局部擇優隨機爬坡算法的云計算負載策略研究

李霞，彭浩

（鄭州輕工業學院計算機與通信工程學院，鄭州　450001）

基于局部擇優隨機爬坡算法的云計算負載策略研究

李霞，彭浩

（鄭州輕工業學院計算機與通信工程學院，鄭州450001）

0　引言

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

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

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

1　云仿真軟件CloudSim簡介

1.1云計算仿真實驗存在的問題

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

1.2CloudSim的優勢及其基礎架構

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

圖1　Simulation configuration

2　基于局部擇優隨機爬坡算法的負載均衡

負載均衡是依靠將總負載重新分到集成系統的各個節點上來提升資源利用率的過程，也是提高作業時間的過程。負載均衡開發策略的要點是對負載的預測、負載的對比比較以及不同系統的穩定性、系統性能、節點間的交互、作業屬性的轉換、節點的選擇等方面的優化。這種負載被認為是CPU負荷、內存使用量、延遲和網絡負載。

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

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

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

（1）維護虛擬機的索引表和虛擬機的工作狀態（忙碌/可用），開始時所有虛擬機都是可用狀態。

（2）新任務進入云任務池［9］。

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

（4）隨機產生一個虛擬機ID。

（5）如果虛擬機已經被分配，就分析配置表來獲取特定虛擬機的狀態。

①返回虛擬機ID。

②發送請求給由ID標識的虛擬機。

③如果虛擬機已經被分配則根據分配情況來更新配置表。

④運用隨機函數來生成一個隨機虛擬機。

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

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

⑦當虛擬機完成請求處理并且微云接收到處理結果時生成已撤銷虛擬機分配的通知。

⑧從第二步開始重復執行為下一次分配準備。

3　仿真結果分析

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

3.1仿真配置

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

表1

3.2仿真場景

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

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

表2

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

表3

表4

3.3結果

在前面所描述的方案和配置下，隨機爬坡算法、輪訓調度算法、先進先服務算法的總體平均響應時間的結果在表2（a），2（b），3（a），3（b），4（a），4（b）中顯示。表2（a），2（b），3（a），3（b），4（a），4（b）以圖形綜述的形式描繪了隨機爬坡算法與輪訓調度算法的性能對比。在大部分的實例中隨機爬坡算法的性能表現都優異于另外兩種算法。

4　結語

本文研究了將爬坡算法的改進算法局部擇優隨機爬坡算法應用于云計算負載均衡策略中，在四種不同虛擬機部署場景中將此改進算法與傳統調度算法輪詢調度（RR）與先到先服務算法（FCFS）橫向對比實驗得出三種算法下虛擬機響應時間數據如圖2，通過數據可以證明局部擇優隨機爬坡算法在一個數據中心的情況下響應時間優勢不明顯，但隨著數據中心的增加響應時間相較另外兩種算法優勢顯著，響應時間大幅度降低，效能提升可觀。

圖2

［1］楊靖琦.云化業務平臺可伸縮性研究［D］.北京.北京郵電大學，2014.

［2］張瀾.網格環境下Min-Min調度算法改進與實現［D］.鄭州.信息工程學院，2008.

［3］Karapici，Alban，Feka.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平臺的云任務分配策略研究［J］.上海：微型電腦應用，2013：59-60.

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

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

［7］單冬冬，呂強.貝葉斯網學習中一種有效的爬山算法［J］.沈陽：小微型計算機系統，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］陳波.云計算環境下負載均衡技術的研究［D］.無錫：江南大學，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-），女，教授，研究方向為云計算、分布式網格計算

2015-09-19

2015-09-29

以云計算的方式來執行任務的過程中負載節點的選擇是非常關鍵的環節，從挖掘資源有效性的角度出發，負載節點必須根據任務屬性來合理選擇，提出一種負載均衡算法——局部擇優的隨機爬坡算法，該算法用來為虛擬機或服務器分配即將運行的調度作業，用云分析軟件對算法的性能進行定量和定性的分析。將局部擇優隨機爬坡算法與輪訓調度算法和先進先服務算法進行對比分析來反映局部擇優隨機爬坡算法在選擇負載節點優化配置計算資源的優越性。

云計算；負載均衡；軟計算；隨機爬坡算法；云分析

河南省科技攻關項目“智慧校園建設”（豫財政【2014】124號）

彭浩（1988-），男，河南信陽人，碩士研究生，研究方向為云計算

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.