摘 要：云計(jì)算服務(wù)的商用對(duì)用戶來(lái)說(shuō)最關(guān)鍵的是成本問(wèn)題。文章提出了基于粒子群算法的云計(jì)算任務(wù)調(diào)度策略。采用了間接編碼的方式，設(shè)置參數(shù)，考慮經(jīng)濟(jì)成本和時(shí)間成本因素，選取了適應(yīng)度函數(shù)，實(shí)驗(yàn)結(jié)果表明，文章算法具有較強(qiáng)的尋優(yōu)能力，可以解決云計(jì)算任務(wù)調(diào)度問(wèn)題。

關(guān)鍵詞：云計(jì)算；任務(wù)調(diào)度；成本粒子群算法

引言

在這大數(shù)據(jù)的時(shí)代，云計(jì)算已是學(xué)術(shù)界、商界的新貴。雖然云計(jì)算技術(shù)在商業(yè)中應(yīng)用的比較廣泛，但是就云計(jì)算技術(shù)，還有許多需要完善和改進(jìn)的。云計(jì)算是一種商業(yè)計(jì)算模型，它將計(jì)算任務(wù)分布在大量計(jì)算機(jī)構(gòu)成的資源池上，是各種應(yīng)用系統(tǒng)能夠根據(jù)需要獲取計(jì)算力、存儲(chǔ)空間和信息服務(wù)。

1 任務(wù)調(diào)度問(wèn)題描述

在云計(jì)算環(huán)境下，一個(gè)大規(guī)模的任務(wù)計(jì)算必須在邏輯上劃分成許多個(gè)子任務(wù)進(jìn)行，然后通過(guò)處理子任務(wù)來(lái)完成主任務(wù)。任務(wù)調(diào)度是將云計(jì)算中用戶提交的任務(wù)請(qǐng)求分配到多個(gè)資源的過(guò)程。在云計(jì)算的應(yīng)用中，大多數(shù)是商業(yè)的應(yīng)用，因此在云計(jì)算的任務(wù)調(diào)度更多的考慮成本指標(biāo)，同時(shí)滿足用戶的需求。成本由時(shí)間成本和經(jīng)濟(jì)成本等組成。

2 基于本文算法的云計(jì)算任務(wù)調(diào)度

粒 子 群 優(yōu) 化 算 法（Particle Swarm Optimization，簡(jiǎn)稱PSO）是由美國(guó)的J.Kennedy 博士和 R.C.Eberhart受鳥群覓食行為的啟發(fā)提出的一種基于群體智能的優(yōu)化算法。因算法程序結(jié)構(gòu)簡(jiǎn)單、需要調(diào)節(jié)的參數(shù)較少、高效等特點(diǎn)，被廣泛應(yīng)于到科學(xué)研究。

2.1 粒子編碼方式

本文采用間接編碼方式，采用離散數(shù)值編碼，編碼長(zhǎng)度等于子任務(wù)數(shù)量。設(shè)有M個(gè)任務(wù)，N個(gè)資源，每個(gè)任務(wù)又劃分為多個(gè)子任務(wù)。

子任務(wù)的總數(shù)量：

其中，TNum（t）為第 t 個(gè)任務(wù)劃分子任務(wù)的個(gè)數(shù)。

對(duì)每個(gè)子任務(wù)的編碼方式為：

采用自然數(shù)編碼，即按任務(wù)自然數(shù)順序進(jìn)行編碼。第i個(gè)任務(wù)中的第 j 個(gè)子任務(wù)的序號(hào)是 R[i，j]。

文中使用ETC 矩陣[1]表示任務(wù)的運(yùn)行時(shí)間，ETC（i，j）表示子任務(wù)i在第j個(gè)資源上執(zhí)行的時(shí)間。其中，ETC（i，j）表示子任務(wù)i在云資源j上執(zhí)行的時(shí)間，ETC（i，j）=0表示子任務(wù)i不在資源j上執(zhí)行。用RUC數(shù)組表示計(jì)算資源單位時(shí)間內(nèi)任務(wù)執(zhí)行的成本[3]，根據(jù)粒子解碼結(jié)果和ETC矩陣[2]，可看出資源j運(yùn)行完被分配到本資源的全部子任務(wù)的時(shí)間Time（j）：

所有資源上的子任務(wù)全部執(zhí)行完后，表示全部任務(wù)運(yùn)行完畢，則任務(wù)的總完成時(shí)間FTime：

第r個(gè)資源運(yùn)行本資源上的全部子任務(wù)所花費(fèi)的總時(shí)間為：

完成全部任務(wù)的總花費(fèi)成本為：

2.2 粒子速度和位置的更新

標(biāo)準(zhǔn)粒子群算法的速度和位置更新公式為：

其中[2]，ω代表慣性權(quán)重，v表示第i個(gè)粒子在第k+1次迭代時(shí)在j維的速度，c1、c2表示粒子個(gè)體的學(xué)習(xí)因子和粒子群體的學(xué)習(xí)因子，r1，r2為0到1之間均勻分布的隨機(jī)數(shù)，x表示第i個(gè)粒子在第k+1次迭代時(shí)在j維的位置，pbest表示第i個(gè)粒子在第k次迭代時(shí)個(gè)體歷史最優(yōu)位置，gbest表示第k次迭代時(shí)的全局最優(yōu)位置。其次為了防止粒子飛出最大解空間，通常限制vij∈（-vmax，vmax）。

為了增加搜索過(guò)程中的種群的多樣性，優(yōu)化最優(yōu)解的搜索能力，本文提出自適應(yīng)的慣性權(quán)重，如下的更新公式

其中rand為0，1之間的隨機(jī)數(shù)

3 實(shí)驗(yàn)仿真與結(jié)果

本文實(shí)驗(yàn)使用Matlab生成ETC矩陣和RCU數(shù)組。運(yùn)用CloudSim-3.0對(duì)傳統(tǒng)粒子群算法和本文算法進(jìn)行云環(huán)境下的仿真實(shí)驗(yàn)，實(shí)驗(yàn)在任務(wù)數(shù)相同、任務(wù)大小相同、計(jì)算資源的計(jì)算能力相同的情況下進(jìn)行。實(shí)驗(yàn)測(cè)試執(zhí)行200次，采用200次實(shí)驗(yàn)的實(shí)驗(yàn)結(jié)果的平均值作為作圖的數(shù)據(jù)。實(shí)驗(yàn)參數(shù)設(shè)置：種群規(guī)模P為50個(gè)，計(jì)算資源數(shù)N為10個(gè)，任務(wù)數(shù)M為20個(gè)，慣性權(quán)重ωstart、ωend為0.95、0.4，學(xué)習(xí)因子c1、c2為2、2，最大迭代次數(shù)為1000次。

實(shí)驗(yàn)結(jié)果如下圖：

由以上實(shí)驗(yàn)結(jié)果可以看出，與傳統(tǒng)的PSO算法相比，本文算法尋優(yōu)能力更強(qiáng)，收斂速度較快。

4 結(jié)束語(yǔ)

本文研究了云計(jì)算任務(wù)調(diào)度模型，改進(jìn)了粒子群算法，并應(yīng)用到云計(jì)算任務(wù)調(diào)度上，主要考慮了時(shí)間成本和經(jīng)濟(jì)成本。仿真結(jié)果顯示本文算法具有較強(qiáng)的尋優(yōu)能力。

參考文獻(xiàn)

[1]封良良，張?zhí)?，賈振紅，等.云計(jì)算環(huán)境下基于改進(jìn)粒子群的任務(wù)調(diào)度算法[J].計(jì)算機(jī)工程，2013，39（5）：183-186.

[2]婁建峰，高岳林，李飛，等.基于改進(jìn)粒子群算法的云計(jì)算任務(wù)調(diào)度算法[J].微電子學(xué)與計(jì)算機(jī)，2016，33（8）：112-116.

[3]封良良，夏曉燕，賈振紅，等.實(shí)驗(yàn)基于資源預(yù)先分類的云計(jì)算任務(wù)調(diào)度算法[J].計(jì)算機(jī)仿真，2013，30（10）：363-367.

作者簡(jiǎn)介：常賀（1993-），男，碩士研究生，研究方向：計(jì)算機(jī)網(wǎng)絡(luò)與控制工程。