戰(zhàn) 非，張少茹

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

基于混沌粒子群算法的云計(jì)算調(diào)度研究

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

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

基于云計(jì)算環(huán)境下資源調(diào)度算法的優(yōu)化為目的，討論了粒子群算法基本原理和該算法在云計(jì)算下應(yīng)用的缺點(diǎn)。采用引入混沌理論的方法，提出一種適合云計(jì)算的混沌粒子群優(yōu)化算法。改進(jìn)算法通過Logistic映射產(chǎn)生隨機(jī)混沌量，通過混沌遍歷性對(duì)初始粒子群進(jìn)行混沌初始化，然后在個(gè)體粒子更新過程中加入混沌擾動(dòng)，有效地提高了算法性能。最后通過CloudSim搭建仿真云環(huán)境進(jìn)行實(shí)驗(yàn)，通過橫向?qū)Ρ认伻核惴ê蛡鹘y(tǒng)Dijkstra算法等，得出混沌粒子群算法在執(zhí)行效率和相對(duì)標(biāo)準(zhǔn)差等方面優(yōu)于其他算法的結(jié)論，更加適合于云計(jì)算環(huán)境。

云計(jì)算；云仿真；粒子群算法；混沌理論

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

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

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

1 粒子群算法分析

1.1 粒子群算法原理

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

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

1.2 數(shù)學(xué)模型

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

當(dāng)個(gè)體粒子找到pbest和gbest時(shí)，通過以下公式更新自己的速度和位置：

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

圖1 可移動(dòng)3種方向的帶權(quán)值組合

1.3 粒子群算法流程

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

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

2）初始化每個(gè)粒子的適應(yīng)值；

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

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

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

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

7）通過式（2）更新粒子當(dāng)前位置，轉(zhuǎn)至3）；

8）結(jié)束算法。

1.4 粒子群算法的缺陷

粒子群算法若應(yīng)用在云計(jì)算調(diào)度中，存在一定的不足：

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

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

2 混沌粒子群算法研究

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

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

2.2 混沌理論對(duì)粒子群算法的改進(jìn)

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

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

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

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

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

3）根據(jù)當(dāng)前位置和速度更新粒子個(gè)體的位置；

4）產(chǎn)生一個(gè) n維向量 u0=（u01，u02，…，u0n），每個(gè)分量為0到1之間的隨機(jī)數(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）產(chǎn)生混沌向量 ui=（u11，u12，…，u1n）。 將 u1中每個(gè)分量載波至混沌擾動(dòng)范圍[-β，β]中，擾動(dòng)量Δx=（Δx1，Δx2，…，Δxn）為，計(jì)算這兩個(gè)位置適應(yīng)值f和f′，若f′＜f則；

End For

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

pfbestik=fi，設(shè)置當(dāng)前個(gè)體極值位置pxbestik；

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

End While

6）算法結(jié)束，輸出結(jié)果gfbestk和gxbestk。

3 仿真實(shí)驗(yàn)

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

3.1 仿真實(shí)驗(yàn)核心過程

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

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

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

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

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

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

3.2 實(shí)驗(yàn)結(jié)果

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

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

圖2 任務(wù)執(zhí)行時(shí)間結(jié)果圖

圖3 相對(duì)標(biāo)準(zhǔn)差結(jié)果圖

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

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

4 結(jié)束語

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

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

[2]陳全，鄧倩妮.云計(jì)算及其關(guān)鍵技術(shù)[J].計(jì)算機(jī)應(yīng)用，2009（9）:2563-2564.

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

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

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

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

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

[8]王意潔，孫偉東，周松，等.云計(jì)算環(huán)境下的分布存儲(chǔ)關(guān)鍵技術(shù)[J].軟件學(xué)報(bào)，2012，23（4）:962-986.

[9]趙欣.不同一維混沌映射的優(yōu)化性能比較研究[J].計(jì)算機(jī)應(yīng)用研究，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稿件編號(hào)：201605150

國家自然科學(xué)基金項(xiàng)目（71373203）

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