基于混沌粒子群算法的云計算調度研究

戰(zhàn) 非，張少茹

（1.西安航空學院 計算機學院，陜西 西安 710077；2.西安交通大學 醫(yī)學院護理系，陜西 西安 710049）

基于混沌粒子群算法的云計算調度研究

戰(zhàn) 非1，張少茹2

（1.西安航空學院 計算機學院，陜西 西安 710077；2.西安交通大學 醫(yī)學院護理系，陜西 西安 710049）

基于云計算環(huán)境下資源調度算法的優(yōu)化為目的，討論了粒子群算法基本原理和該算法在云計算下應用的缺點。采用引入混沌理論的方法，提出一種適合云計算的混沌粒子群優(yōu)化算法。改進算法通過Logistic映射產生隨機混沌量，通過混沌遍歷性對初始粒子群進行混沌初始化，然后在個體粒子更新過程中加入混沌擾動，有效地提高了算法性能。最后通過CloudSim搭建仿真云環(huán)境進行實驗，通過橫向對比蟻群算法和傳統(tǒng)Dijkstra算法等，得出混沌粒子群算法在執(zhí)行效率和相對標準差等方面優(yōu)于其他算法的結論，更加適合于云計算環(huán)境。

云計算；云仿真；粒子群算法；混沌理論

云計算作為一種新興的計算模式，主要應用于互聯(lián)網中，將基礎資源設施、應用系統(tǒng)、軟件平臺等作為服務提供給用戶[1]。云計算也是一種以虛擬化為基礎的架構方式，能夠將資源虛擬化并構建規(guī)模較大的資源池，對外以服務方式進行管理。

隨著云計算的發(fā)展，海量的用戶數(shù)據和大型數(shù)據被放入云計算系統(tǒng)中。云計算中因其自身的特點，需要對異構基礎資源的支持，以分布式計算為基礎，需要計算處理的數(shù)據也分布于不同的節(jié)點[2]。為了提高云計算的效率，資源調度問題顯得至關重要，一個適合于云計算并且高效的資源調度算法是提高云服務響應時間的核心。

文中從已被廣泛應用于求解最優(yōu)問題和調度問題的粒子群算法出發(fā)，討論了算法在云環(huán)境下應用存在的缺陷，進而通過混沌理論提出了一種混沌粒子群的優(yōu)化算法進行改進。算法通過Logistic映射產生隨機混沌信號對粒子群進行混沌初始化，在個體粒子更新過程中加入混沌擾動，證明混沌粒子群算法能有效地加快收斂速度和跳出局部最優(yōu)解。最后通過CloudSim云仿真軟件進行實驗，證明了混沌粒子群算法更加適合于云計算。

1 粒子群算法分析

1.1 粒子群算法原理

粒子群算法（Particle Swarm Optimization，PSO）的提出源于自然界鳥類群體覓食行為。一群鳥隨機在某個區(qū)域內尋找食物，食物存在于區(qū)域中的某一位置，但是每個個體不知道食物的具體位置，但可以感知出當前位置和目標食物的距離[3-4]。雖然開始鳥群個體較分散，但經過一段時間之后會逐漸匯聚，最終找到食物。

粒子群算法將此現(xiàn)象歸結為數(shù)學問題進行優(yōu)化問題求解。每個鳥類個體我們將其當做一個“粒子”，它擁有位置和速度兩個屬性。每個“粒子”通過自身個體找到距食物最近的解和參考整個群體中找到的最近解改變自己的位置和方向，雖然每個鳥個體僅根據有限的鄰居鳥決定自己的位置和方向，但是宏觀上看整個鳥群仿佛在統(tǒng)一控制下匯聚到離食物最近的區(qū)域。

1.2 數(shù)學模型

粒子群算法初始階段為隨機解，然后通過算法中每一輪迭代追蹤和更新個體極值pbest和全局極值gbest得到最優(yōu)解。個體極值指粒子本身找到的最優(yōu)解，全局極值指整個粒子群當前最優(yōu)解。

當個體粒子找到pbest和gbest時，通過以下公式更新自己的速度和位置：

vk代表粒子速度；xk代表當前粒子位置；pbestk代表個體粒子最優(yōu)解位置；gbestk代表當前粒子群最優(yōu)解位置；c0，c1，c2為隨機數(shù)，代表群體認知系數(shù)，c0∈（0，1），c1∈（0，2），c2∈（0，2）；vk+1為 vk、pbestk-xk和gbestk-xk之矢量和。示意圖如圖1所示。

圖1 可移動3種方向的帶權值組合

1.3 粒子群算法流程

粒子群算法對優(yōu)化問題求解算法流程為：

1）確定粒子群個數(shù)n，初隨機產生n個初始解和n個初始速度；

2）初始化每個粒子的適應值；

3）若迭代次數(shù)小于規(guī)定迭代次數(shù)，則轉至（4），否則轉至（8）；

4）重新計算個體粒子的適應值，若其優(yōu)于原來個體極值pbest，則重置pbest為當前適應值；

5）從每個粒子的個體極值pbest中求出全局極值gbest；

6）設定最大速度vmax（vmax＞0），通過式（1）更新速度vk，若vk＞vmax，則vk=vmax。

7）通過式（2）更新粒子當前位置，轉至3）；

8）結束算法。

1.4 粒子群算法的缺陷

粒子群算法若應用在云計算調度中，存在一定的不足：

1）初始化過程表現(xiàn)為隨機性，隨機過程多數(shù)情況雖能夠保證初始解群均勻分布，但個體的粒子質量不能保證，若解群中有一部分遠離最優(yōu)解，可能造成算法收斂速度較慢。云計算中對服務響應時間要求較高，算法執(zhí)行效率較低會大大降低響應時間。

2）粒子算法在處理搜索問題過程中，易出現(xiàn)過早收斂的現(xiàn)象。算法根據個體信息、個體極值和全局極值決定每一輪迭代位置，當本身信息和個體極值占優(yōu)勢，容易陷入局部最優(yōu)解[5]。

2 混沌粒子群算法研究

混沌是一種典型的非線性現(xiàn)象，能夠按照自己規(guī)律，在一定范圍內無重復遍歷全部狀態(tài)。本文討論的混沌主要指一種對初始條件非常敏感的時間演化行為，通過混沌運動的特性完成搜索的優(yōu)化。混沌通常指由確定性方程得到的隨機運動狀態(tài)，常見的混沌系統(tǒng)有Logistic系統(tǒng)、Chen系統(tǒng)、Lorenz系統(tǒng)等[6-7]。文中的研究和實驗都基于Logistic映射，其迭代公式為：

其中μ為控制參數(shù)，zi+1∈（0，1）。當3.5699456＜μ≤4時，Logistic映射表現(xiàn)出混沌狀態(tài)；當μ=4時，呈現(xiàn)典型混沌特征，具有隨機性、規(guī)律性、遍歷性和對初值敏感性等。文中將取μ=4，以Logistic映射作為混沌信號發(fā)生器。

2.2 混沌理論對粒子群算法的改進

將混沌理論引入粒子群算法可以有效的改進上節(jié)討論的粒子群算法的不足，這里提出一種混沌粒子群算法（CPSO），其改進核心思想為：利用混沌運動的遍歷性進行初始化，選擇出較優(yōu)初始群體，加快算法收斂速度；通過Logistic映射產生混沌量，每一輪迭代個體粒子更新時，對當前粒子加入混沌擾動，避免算法早熟收斂，跳出局部最優(yōu)解。

這里以求解n維優(yōu)化問題minf（x1，x2，…，xn），s.t.ai≤xi≤bi為說明，混沌粒子群優(yōu)化算法流程如下：

1）根據式（2）變化可得 zi+1j=μzij（1-zij），i=1，2…，N-1；j=1，2…，n；0＜μ≤4。由此產生N個n維的向量，n維中每個分量為產生的0-1之間的混沌量。如z1=（z11，z12，…，z1n），產生N個 z1，z2，…，zN；

2）將各分量載波到優(yōu)化變量的取值范圍：xij=aj+（bj-aj）zij（i=1，2，…，N；j=1，2，…，n）。計算目標函數(shù)，從N個初始群體中選擇m個較優(yōu)解，隨機產生m個初始速度，完成混沌初始化；

（2）瀝青拌和的設備必須進行防塵設備的安裝，另外瀝青蒸汽的加溫裝置中，蒸汽管道應該與其進行牢固的連接，由于高溫的因素，在需要人員接觸的部位應該使用高溫材料進行保護。

3）根據當前位置和速度更新粒子個體的位置；

4）產生一個 n維向量 u0=（u01，u02，…，u0n），每個分量為0到1之間的隨機數(shù)；

5）While（迭代次數(shù)K＜規(guī)定迭代次次數(shù)nmax）do

For i=1：m

由式（1）更新粒子速度且小于Vmax；

由式（2）代入 u0，取 μ=4，u1j=4u0j（1-u0j）（j= 1，2，…，n）產生混沌向量 ui=（u11，u12，…，u1n）。 將 u1中每個分量載波至混沌擾動范圍[-β，β]中，擾動量Δx=（Δx1，Δx2，…，Δxn）為，計算這兩個位置適應值f和f′，若f′＜f則；

End For

k=k+1，計算粒子i的適應值fi，若fi優(yōu)于原先個體極值則個體極值

pfbestik=fi，設置當前個體極值位置pxbestik；

從所有粒子的pfbestk（i=1，2，…，m）中得到全局極值gfbestk和gxbestk；

End While

6）算法結束，輸出結果gfbestk和gxbestk。

3 仿真實驗

本次實驗采用云計算仿真軟件CloudSim進行，其基本流程包括：首先模擬云環(huán)境，創(chuàng)建計算節(jié)點和分發(fā)云任務數(shù)及資源；其次設定服務參數(shù)，根據目前常規(guī)硬件配置和網絡帶寬創(chuàng)建虛擬機；再次通過混沌蟻粒子群算法進行資源調度，當算法找到符合服務要求的最優(yōu)路徑，提供資源并進行綁定；最后輸出仿真結果。

3.1 仿真實驗核心過程

CloudSim仿真經過的步驟包括：首先新建數(shù)據中心，然后確定模擬資源參數(shù)，通過DatacenterBroker類的對象建立代理，由此代理負責信息的交互，然后創(chuàng)建虛擬機開始執(zhí)行云任務，最終獲取結果。

以下步驟為仿真過程中核心類的主要方法，調用方法中的一些仿真參數(shù)如帶寬（bw），內存（ram），PE數(shù)（pesNumber）等等的定義語句，由于篇幅限制這里省略不寫，這些參數(shù)的取值根據常規(guī)虛擬機硬件水平設置[8-10]。

1）通過CloudSim.init（）進行初始化，新建數(shù)據中心 Datacenter對象類 dt1及數(shù)據中心代理DatacenterBroker類對象broker，通過broker.get_id（）獲得ID；

2）新建虛擬機列表，根據Vm類和要仿真的虛擬機規(guī)格參數(shù)（id、PE數(shù)量、MIPS速率、內存、帶寬等等 ） 創(chuàng) 建 虛 擬 機 vm 對 象 ， 并 通 過 broker.submitVmList（）提交代理；

3）根據Cloudlet類創(chuàng)建對象，建立云任務列表，根據仿真參數(shù)（ID、PE數(shù)量、文件大小等）新建一個云任務并添加進列表；

4）通過broker.submitCloudletList（）將云任務列表提交給代理broker，用startSimulation（）方法啟動仿真過程，stopSimulation（）方法結束后輸出結果。

3.2 實驗結果

通過在CloudSim中進行實驗，設定執(zhí)行的任務數(shù)為20～100，計算節(jié)點數(shù)為20個。為了更好的說明混沌粒子群算法在云計算中優(yōu)勢，選取了標準粒子群算法、傳統(tǒng)Dijkstra算法及標準蟻群算法，在相同實驗參數(shù)情況下執(zhí)行并進行對比。每種算法執(zhí)行10次取平均值，算法效率對比情況如圖2所示。

通過圖2得出，當模擬任務數(shù)量較少時，4種算法完成任務時間差別不大，但是隨著任務量的增加，混沌粒子群算法的執(zhí)行效率要優(yōu)于其他幾種算法。由于仿真模擬任務數(shù)和計算節(jié)點較少，在實際云環(huán)境應用中，混沌粒子群算法的執(zhí)行效率優(yōu)勢會進一步提高。為了更進一步的展示幾種算法的區(qū)別，對任務分配的結果的相對標準差值進行計算，如圖3所示。

圖2 任務執(zhí)行時間結果圖

圖3 相對標準差結果圖

通過圖3顯示，當任務數(shù)增加，混沌粒子群算法的偏差值越來越小并趨于線性漸進，同樣優(yōu)于其他幾種算法。

通過以上分析，云計算的特點就是并行處理大量任務，通過混沌粒子群算法進行資源調度可以有效的改進粒子群算法的缺陷，更加適應常規(guī)云計算的要求。

4 結束語

云計算作為一種蓬勃發(fā)展商業(yè)計算模式，建立在將大量資源虛擬化的基礎上，可以統(tǒng)一對海量數(shù)據進行管理，根據用戶對作業(yè)量的需求提供服務，云計算中要保證客戶端的響應時間，資源調度問題尤為重要，本文主要對云計算中調度算法進行研究。粒子群算法作為目前被廣泛應用于調度問題和求解最優(yōu)問題的算法，在云計算應用中具有一定的缺陷。本文引入混沌理論，提出一種適合于云計算的混沌粒子群算法進行改進，通過CloudSim云仿真軟件進行實驗，證明了混沌粒子群算法能夠有效改善粒子群算法中的不足，更加適合應用在云計算中。

[1]劉鵬.云計算[M].北京:電子工業(yè)出版社，2010.

[2]陳全，鄧倩妮.云計算及其關鍵技術[J].計算機應用，2009（9）:2563-2564.

[3]李劍鋒，彭艦.云計算環(huán)境下基于改進遺傳算法的任務調度算法[J].計算機應用，2011，31（1）:184-186.

[4]孟湘來.基于云計算的數(shù)據中心構建探析[J].中國企業(yè)教育，2012（22）:240-241.

[5]華夏渝，鄭駿，胡文心.基于云計算環(huán)境的一群優(yōu)化計算資源分配算法[J].華東師范大學學報，2010（1）:127-134.

[6]田文洪，趙勇.云計算—資源調度管理[M].國防工業(yè)出版社，2011:27-29.

[7]魯宇明，陳殊，黎明.自適應調整選擇壓力的災變元胞遺傳算法[J].系統(tǒng)仿真學報，2013，25（3）:436-444.

[8]王意潔，孫偉東，周松，等.云計算環(huán)境下的分布存儲關鍵技術[J].軟件學報，2012，23（4）:962-986.

[9]趙欣.不同一維混沌映射的優(yōu)化性能比較研究[J].計算機應用研究，2012，29（3）:913-915.

[10]Buyya R，Yeo CS，Venugopal S.Cloud computing and emerging IT platforms:Vision，hype and reality for delivering computing as the 5th utility[J].Future Generation Computer Systems，2009（25）:599-616.

[11]Didier L I，López D E，Redundancy.Allocation problemsconsidering systemswith imperfectrepairs using multiobjectivegenetic algorithms and discrete event simulation[J].Simulation Modelling Practice and Theory，2011，19（1）:362-381.

[12]LI Jing-wei，JIA Chun-fu，LI Jin，et al.Outsourcing encryption of attribute-based encryption with Map-Reduce[C]//Information and Communications Security-14th International Conference，ICICS 2012:191-201.

[13]Sudha G，Sadasivam，Baktavachalam G.A novel approach to mutiple sequence alignment using hadoop data grids[C]//Proceedings ofthe 2010 WorkshoponMassiveDataAnalyticson the Cloud，2010:472-483.

A research on cloud computing scheduling based on chaos particle swarm optimization algorithm

ZHAN Fei1，ZHANG Shao-ru2
（1.School of Computer Science，Xi'an Aeronautical Universities，Xi'an 710077，China；2.Health Science Center，Xian Jiaotong University，Xi'an 710049，China）

This paper discusses the basic principle of Particle Swarm Optimization algorithm and the shortcomings of the algorithm in cloud computing，from the point of view of resource scheduling algorithm in Cloud Computing environment.Based on the introduction of chaos theory，a new Chaotic Particle Swarm Optimization algorithm is proposed.the improved algorithm random chaotic volume generated by logistic map，through the chaos ergodicity of the initial particle swarm chaos initialization，then add chaotic disturbance in individual particle update process to improve the performance.Finally build cloud simulation platform through the CloudSim and experiments are conducted.Through the horizontal comparison of Particle Swarm Optimization algorithm and the traditional Dijkstra algorithm，it is proved that Chaotic Particle Swarm Optimization algorithm is better than other algorithms in execution efficiency and the relative standard deviation，and thus more suitable for in the cloud computing environment.

cloud computing；cloud simulation；PSO；chaos theory

TN919

：A

：1674－6236（2017）05-0013-04

2016-05-16稿件編號：201605150

國家自然科學基金項目（71373203）

戰(zhàn) 非（1981—），男，陜西西安人，碩士，講師。研究方向：軟件工程、云計算、通信工程，軟件開發(fā)、移動互聯(lián)網應用。