云環(huán)境下應(yīng)用粒子群算法分配排隊(duì)系統(tǒng)任務(wù)調(diào)度策略

甘娜

（廣東工程職業(yè)技術(shù)學(xué)院信息工程學(xué)院，廣州 510520)

云環(huán)境下應(yīng)用粒子群算法分配排隊(duì)系統(tǒng)任務(wù)調(diào)度策略

甘娜

（廣東工程職業(yè)技術(shù)學(xué)院信息工程學(xué)院，廣州 510520)

云環(huán)境下任務(wù)調(diào)度的核心模塊是任務(wù)排隊(duì)等待調(diào)度執(zhí)行，任務(wù)等待的時(shí)間與任務(wù)執(zhí)行成本關(guān)系到系統(tǒng)的應(yīng)用性能。提出一種基于基本粒子群算法的任務(wù)排隊(duì)方案，改善排隊(duì)系統(tǒng)性能。此方案首先詳細(xì)分析云任務(wù)排隊(duì)模型特點(diǎn)，建立基于基本粒子群算法的排隊(duì)模型；其次，分析粒子群算法的云任務(wù)排隊(duì)系統(tǒng)調(diào)度流程；最后，建立一個(gè)云任務(wù)調(diào)度仿真排隊(duì)模型。估計(jì)系統(tǒng)總費(fèi)用，確定最優(yōu)服務(wù)率，驗(yàn)證粒子群算法在云任務(wù)排隊(duì)系統(tǒng)中提高全局尋優(yōu)能力的有效性。

任務(wù)調(diào)度；排隊(duì)；粒子群算法；系統(tǒng)總費(fèi)用

0 引言

云環(huán)境中任務(wù)調(diào)度指的是用戶提交的任務(wù)被分割成n個(gè)子任務(wù)，形成n個(gè)子任務(wù)和m個(gè)虛擬機(jī)的映射關(guān)系，有多種可能的匹配方式。如何提高虛擬機(jī)服務(wù)臺的服務(wù)質(zhì)量和效率，對于云任務(wù)調(diào)度排隊(duì)系統(tǒng)的優(yōu)化具有實(shí)際意義。既能提高排隊(duì)系統(tǒng)的服務(wù)性能，又能降低服務(wù)成本。因此，本文在加快服務(wù)速度、減少服務(wù)等待時(shí)間、提高服務(wù)臺利用率方面對排隊(duì)系統(tǒng)性能進(jìn)行優(yōu)化。本文對基于粒子群算法的排隊(duì)系統(tǒng)服務(wù)過程進(jìn)行仿真，仿真結(jié)果驗(yàn)證了粒子群算法在分析排隊(duì)系統(tǒng)性能中的合理性及有效性，提高了服務(wù)臺利用率，減少了服務(wù)等待時(shí)間。

1 問題描述與建模

一個(gè)云任務(wù)調(diào)度排隊(duì)系統(tǒng)由輸入過程、排隊(duì)規(guī)則和服務(wù)規(guī)則三個(gè)基本部分組成。排隊(duì)模型見圖1：

圖1 排隊(duì)模型

排隊(duì)模型需要三個(gè)參數(shù)：到達(dá)率λ，服務(wù)率 μ，虛擬機(jī)服務(wù)臺數(shù)目C。主要從兩個(gè)方面進(jìn)行描述：

（1）到達(dá)為固定速率λ的Poisson分布；

（2）服務(wù)服從服務(wù)率μ的指數(shù)分布。

對應(yīng)的排隊(duì)模型為M/M/C/∞。系統(tǒng)的負(fù)載為α=λ/μ，如果α≥C，則系統(tǒng)超過系統(tǒng)的處理能力，出現(xiàn)無窮排隊(duì)，任務(wù)的等待時(shí)間趨向于無窮大。一般主要分析在α＜C的狀態(tài)下，排隊(duì)等待時(shí)間的分布情況。

2 粒子群算法設(shè)計(jì)

標(biāo)準(zhǔn)粒子群算法（PSO算法）是一種受鳥群覓食行為的啟發(fā)而提出的優(yōu)化算法，主要實(shí)現(xiàn)優(yōu)化問題的求解。通過粒子個(gè)體間的信息共享和社會交互，使群體中的粒子個(gè)體朝同一方向迭代，逐漸向最優(yōu)解靠近。在云任務(wù)調(diào)度過程中，任務(wù)可看作粒子，任務(wù)分配到的虛擬機(jī)即為最優(yōu)解。

算法的基本步驟如下：

Step1：在 t(t =0)時(shí)刻，確定群體規(guī)模n，隨機(jī)初始化所有粒子的位置Xid(t)與速度Vid(t)；

Step2：通過目標(biāo)函數(shù) f(Xid(t) )，評價(jià)每個(gè)粒子i的適應(yīng)度值，初始化每個(gè)粒子i的Pid(t)為粒子的當(dāng)前位置，Pid(t)的適應(yīng)度值即為當(dāng)前粒子位置的適應(yīng)度值，初始化Pgd(t)為群體中的最佳位置，Pgd(t)的適應(yīng)度值即為所有粒子的最佳適應(yīng)度值；

Step3：更新每個(gè)粒子的速度Vid(t)、更新每個(gè)粒子的位置Xid(t)；

Step4：通過目標(biāo)函數(shù) f(Pid(t))，重新確定每個(gè)粒子i的適應(yīng)度值；

Step5：如果當(dāng)前Pid(t)的適應(yīng)度值好于Pid(t)，則當(dāng)前位置代替Pid(t)，更新其局部最優(yōu)解；如果當(dāng)前Pgd(t)的適應(yīng)度值好于Pgd(t)，則當(dāng)前位置代替Pgd(t)，更新其全局最優(yōu)解；

Step6：判斷是否最大迭代次數(shù)？是，輸出Pid(t)，輸出最優(yōu)解，否則轉(zhuǎn)Step3。

云環(huán)境中的虛擬機(jī)資源性能差異較大，是一個(gè)存在較多局部極值的環(huán)境，將PSO算法應(yīng)用于云任務(wù)調(diào)度中求解效率高、全局搜索能力強(qiáng)，適應(yīng)于云任務(wù)調(diào)度問題。

3 粒子群算法的云任務(wù)排隊(duì)系統(tǒng)調(diào)度流程

Step1：編碼。優(yōu)化數(shù)值，產(chǎn)生一群更適應(yīng)問題環(huán)境的種群；

實(shí)數(shù)編碼方式如下：

其中ρ為編碼實(shí)數(shù)，n為二進(jìn)制編碼位數(shù)，bi為第i位的二進(jìn)制值；

Step 2：產(chǎn)生初始種群。設(shè)置變量的取值范圍、搜索空間維度d，小生境粒子的數(shù)量為k，種群粒子個(gè)數(shù)，最大迭代次數(shù)；每個(gè)種群在范圍內(nèi)隨機(jī)初始化粒子的速度和初始位置，其中第i個(gè)粒子位置χ，第i個(gè)粒子的飛行速度υ，獲取學(xué)習(xí)因子C1，C2和慣性權(quán)重ω；

Step 3：每個(gè)線程更新各粒子的速度與位置，計(jì)算粒子適應(yīng)度值。對每個(gè)線程中的子種群加入收縮因子參數(shù)，關(guān)聯(lián)參數(shù)，確保算法收斂速度和精度。目標(biāo)函數(shù)作為適應(yīng)度函數(shù)，計(jì)算粒子的適應(yīng)度值；

Step 4：更新子種群的最優(yōu)解和種群的最優(yōu)解；

Step 5：判斷是否最大迭代次數(shù)？條件為真，則輸出最優(yōu)解，算法結(jié)束。條件為假，則轉(zhuǎn)到Step 3，進(jìn)行下一次迭代。

4 數(shù)值仿真與性能分析

4.1 系統(tǒng)總費(fèi)用估計(jì)

任務(wù)排隊(duì)穩(wěn)態(tài)系統(tǒng)單位時(shí)間的平均總費(fèi)用由服務(wù)費(fèi)用和等待費(fèi)用構(gòu)成，優(yōu)化目標(biāo)是最小化兩者費(fèi)用之和，并確定達(dá)到最優(yōu)目標(biāo)值的最優(yōu)服務(wù)水平。

多服務(wù)臺排隊(duì)系統(tǒng)模型，已知在平穩(wěn)狀態(tài)下單位時(shí)間內(nèi)總費(fèi)用（服務(wù)費(fèi)用與等待費(fèi)用之和）的期望值為

其中，C是服務(wù)臺數(shù)，C's是每個(gè)服務(wù)臺單位時(shí)間內(nèi)的總費(fèi)用，Cw為每個(gè)任務(wù)在系統(tǒng)停留單位時(shí)間的費(fèi)用，L是系統(tǒng)中的任務(wù)平均數(shù)（也可把L換成是系統(tǒng)中等待的任務(wù)平均數(shù)Lq）。

顯然，它們都隨C值的不同而不同。因?yàn)镃's和Cw都是給定的，唯一可能變動的是服務(wù)臺數(shù)C，所以，Z是C的函數(shù)Z(C ) ，現(xiàn)在是求最優(yōu)解C*使Z(C*)為最小。

4.2 最優(yōu)服務(wù)率確定

假定任務(wù)到達(dá)服從參數(shù)為λ的一般分布，服務(wù)設(shè)施的平均服務(wù)率為μ，服從幾何分布。又設(shè)：

若用Z(μ)表示給定 μ值時(shí)任務(wù)等待和服務(wù)設(shè)施的費(fèi)用之和，則有：

對多服務(wù)臺排隊(duì)系統(tǒng)，（式3）可表示為（式4）：

由（式 4）可求得（式5）：

即當(dāng)C's和Cw給定時(shí)，系統(tǒng)的最優(yōu)服務(wù)率只同任務(wù)的到達(dá)率λ有關(guān)。

下面根據(jù)系統(tǒng)總費(fèi)用估計(jì)和最優(yōu)服務(wù)率確定的方法，引入一些基本參數(shù)，服務(wù)水平為3.8元（即每執(zhí)行一個(gè)任務(wù)需要花費(fèi)成本）。通過計(jì)算機(jī)輔助計(jì)算出系統(tǒng)總費(fèi)用和最優(yōu)服務(wù)率。具體數(shù)據(jù)見表1：

表1 單位時(shí)間內(nèi)系統(tǒng)總費(fèi)用和最優(yōu)服務(wù)率

5 結(jié)語

本文通過MATLAB平臺對基于粒子群算法的云任務(wù)排隊(duì)系統(tǒng)建模，分析得出適合任務(wù)量波動變化并且滿足服務(wù)指標(biāo)要求的服務(wù)臺代表數(shù)量、最優(yōu)服務(wù)率、最優(yōu)服務(wù)設(shè)施數(shù)等系統(tǒng)參數(shù)。通過仿真模型估計(jì)任務(wù)等待成本和服務(wù)臺服務(wù)成本，仿真結(jié)果表明，粒子群算法克服了陷入局部最優(yōu)解的缺點(diǎn)，粒子群優(yōu)化算法在求解排隊(duì)系統(tǒng)問題中能實(shí)現(xiàn)有效的任務(wù)調(diào)度，減少了任務(wù)等待時(shí)間，合理規(guī)劃了服務(wù)臺資源。

[1]潘峰，周倩，李位星，高琪.標(biāo)準(zhǔn)粒子群優(yōu)化算法的馬爾科夫鏈分析[J].自動化學(xué)報(bào),2013.

[2]周俊，陳璟華，劉國祥等.粒子群優(yōu)化算法中慣性權(quán)重綜述[J].廣東電力，2013.

[3]周焱霞.云數(shù)據(jù)中心虛擬機(jī)放置問題研究[D].中國科學(xué)技術(shù)大學(xué),2015.

[4]孫曉川.未來網(wǎng)絡(luò)虛擬化資源管理機(jī)制研究[D].北京郵電大學(xué),2013.

[5]李進(jìn)超，梁謹(jǐn).虛擬機(jī)動態(tài)資源分配及放置算法研究[D].上海：復(fù)旦大學(xué),2014.

[6]紀(jì)震,廖惠聯(lián),吳清華.粒子群算法及其應(yīng)用[M].科學(xué)出版社,2009.

Application of Particle Swarm Optimization to Task Scheduling in Cloud Environment

GAN Na
（Department of Information Engineering,Guangdong Engineering Polytechnic，Guangzhou 510520）

In the cloud environment,the core module of task scheduling is task queuing,waiting for scheduling execution,the time of task waiting and the cost of task execution are related to the application performance of the system.Proposes a task queuing scheme based on the basic particle swarm optimization(PSO)algorithm to improve the performance of the queuing system.Firstly,analyzes the cloud task queuing model,sets up a queue model based on particle swarm optimization algorithm.Secondly,analyzes the particle swarm optimization algorithm for cloud task scheduling process of queuing system.Finally,establishes a cloud task scheduling simulation queuing model.Estimates the total cost of the system,and determines the optimal service rate is,verifies the effectiveness of PSO in improving the global searching ability in the cloud task queuing system.

Task Scheduling;Queue;Particle Swarm Optimization Algorithm;Total System Cost

1007-1423（2017）32-0038-03

10.3969/j.issn.1007-1423.2017.32.009

甘娜（1980-），女，江西萍鄉(xiāng)人，碩士，研究方向?yàn)橹悄軆?yōu)化、云計(jì)算

2017-08-15

2017-11-01