基于粒子群離散優(yōu)化的網(wǎng)格資源分配方法*

孔軼艷, 宋偉奇

(1.柳州職業(yè)技術(shù)學(xué)院，廣西 柳州　545006; 2.柳州城市職業(yè)學(xué)院，廣西 柳州　545006)

?

基于粒子群離散優(yōu)化的網(wǎng)格資源分配方法*

孔軼艷1, 宋偉奇2

(1.柳州職業(yè)技術(shù)學(xué)院，廣西 柳州545006; 2.柳州城市職業(yè)學(xué)院，廣西 柳州545006)

為提升網(wǎng)格計(jì)算的資源分配效率和調(diào)度精確性，提出了一種粒子群離散優(yōu)化的網(wǎng)格資源分配方法.該方法首先基于網(wǎng)格的離散特性給出了粒子位置和速度的定義；接著，基于網(wǎng)格參量推導(dǎo)了粒子優(yōu)化矩陣，分析了離散優(yōu)化的實(shí)現(xiàn)步驟，并通過粒子速度的歸一化處理，有效緩解POS后期粒子的局部早熟問題.最后，通過DridSim平臺(tái)構(gòu)建的10個(gè)資源節(jié)點(diǎn)分別針對(duì)利用效率、時(shí)間消耗進(jìn)行了仿真分析，結(jié)果表明本文方法的時(shí)間利用效率提升了近5%.

粒子群優(yōu)化；網(wǎng)格計(jì)算；資源分配；離散序列

0　引言

隨著物聯(lián)網(wǎng)技術(shù)的快速發(fā)展，面向大數(shù)據(jù)處理分析的計(jì)算機(jī)網(wǎng)格技術(shù)成為計(jì)算機(jī)通信網(wǎng)絡(luò)領(lǐng)域的熱點(diǎn)研究問題之一[1-2].該技術(shù)主要針對(duì)高速網(wǎng)絡(luò)數(shù)據(jù)，采用并行分布式計(jì)算的方法實(shí)現(xiàn)信息快速有效的交互，其中網(wǎng)格資源的合理分配與調(diào)度是該方法的重要基礎(chǔ)[3].

隨著智能尋優(yōu)技術(shù)的發(fā)展，研究人員將該技術(shù)應(yīng)用于網(wǎng)格資源的調(diào)度分配優(yōu)化問題，取得了很好的應(yīng)用成果[4-8].文獻(xiàn)[9]基于蟻群算法(ACS)對(duì)網(wǎng)格調(diào)度生成均衡性導(dǎo)航優(yōu)化，由于初值信息的缺乏，限制了收斂速度和優(yōu)化精度；文獻(xiàn)[10]采用粒子群優(yōu)化算法(POS)對(duì)初始信息進(jìn)行起點(diǎn)優(yōu)化分析，雖然提升了前期網(wǎng)格數(shù)據(jù)的優(yōu)化精度，但是在后期的尋優(yōu)過程中，POS方法容易陷入局部最優(yōu)值，搜索精度降低.文獻(xiàn)[11]針對(duì)兩者的不足進(jìn)行了融合性的分析處理，但是在融合過程中沒有考慮網(wǎng)格離散化過程中位置與速度歸一化對(duì)收斂性能的影響，一定程度上降低了處理效率.針對(duì)這種問題，筆者提出了一種改進(jìn)粒子群優(yōu)化網(wǎng)格資源分配方法.首先，在標(biāo)準(zhǔn)POS的基礎(chǔ)上針對(duì)網(wǎng)格分布特性，進(jìn)行離散改寫，并基于獲取的網(wǎng)格資源特性給出優(yōu)化集合粒子位置、速度等相關(guān)參量的定義.接著，參照標(biāo)準(zhǔn)POS方法推導(dǎo)分析了相應(yīng)的優(yōu)化矩陣和實(shí)現(xiàn)步驟，并通過粒子速度的歸一化處理，有效緩解POS后期粒子的局部早熟問題.最后，通過DridSim平臺(tái)構(gòu)建的10個(gè)資源節(jié)點(diǎn)分別針對(duì)利用效率、時(shí)間消耗以及節(jié)點(diǎn)可信度進(jìn)行了仿真分析.

1　網(wǎng)格資源模型

給定集合T={t1,t2,…,tn}表示不同的業(yè)務(wù)需求組成的調(diào)度指令集合，為實(shí)現(xiàn)有效的多任務(wù)通信，該集合需要通過網(wǎng)格資源集合G={g1,g2,…,gm}進(jìn)行調(diào)度和分配.分析中，將一次業(yè)務(wù)需求任務(wù)表示為tj(j∈[1,n])，單個(gè)對(duì)應(yīng)網(wǎng)格節(jié)點(diǎn)表示為gi(i∈[1,m]).為有效度量網(wǎng)格節(jié)點(diǎn)的計(jì)算效率，采用單位時(shí)間內(nèi)節(jié)點(diǎn)自動(dòng)完成任務(wù)調(diào)度需求的次數(shù)表示網(wǎng)格節(jié)點(diǎn)的計(jì)算速度.同時(shí)，將不同任務(wù)在不同節(jié)點(diǎn)上的執(zhí)行時(shí)間表示為Ci,j(i∈[1,m],j∈[1,n])，可以描述為子任務(wù)tj在節(jié)點(diǎn)gi上的時(shí)間消耗.單個(gè)節(jié)點(diǎn)gi處理承載全部任務(wù)的時(shí)間總消耗表示為Ci，當(dāng)前基于POS的優(yōu)化調(diào)度計(jì)算中采用優(yōu)化單次業(yè)務(wù)分配過程中粒子的適應(yīng)值為目標(biāo)函數(shù)，具體計(jì)算表示為：

Cmax=max{Ci}

(1)

優(yōu)化的目的就是在給定業(yè)務(wù)和節(jié)點(diǎn)集合的基礎(chǔ)上，實(shí)現(xiàn)式(1)中的Cmax最小化.

2　粒子群離散優(yōu)化分析

2.1基本粒子群算法介紹

(2)

(3)

(4)

(5)

2.2離散優(yōu)化分析及實(shí)現(xiàn)

由于基本POS算法主要是針對(duì)時(shí)間連續(xù)問題提出，而網(wǎng)格資源的任務(wù)調(diào)度及優(yōu)化問題均屬于離散狀態(tài)，如果采用連續(xù)處理手段，既降低了精度，也影響了實(shí)時(shí)性，因此，需要對(duì)連續(xù)POS進(jìn)行離散化分析實(shí)現(xiàn)，針對(duì)網(wǎng)格資源調(diào)度的固有特性，該部分主要針對(duì)粒子離散位置及速度信息進(jìn)行重新定義，并給出了具體的實(shí)現(xiàn)方法.

2.2.1離散位置和速度

粒子i的位置向量為Xi={x1,x2,…,xj,…,xn}，其中，xj為節(jié)點(diǎn)xj執(zhí)行任務(wù)tj的位置信息，滿足l≤xj≤m，針對(duì)節(jié)點(diǎn)是否承接任務(wù)傳輸需求，可以將位置信息表示為(0,1)組成的二值矩陣形式，即

(6)

位置矩陣中如果取值為sij=1,i∈{1,2,…,m}，j∈{1,2,…,n}，則表示子業(yè)務(wù)tj在網(wǎng)格節(jié)點(diǎn)gj中完成任務(wù)調(diào)度；如果sij=0，則表示該節(jié)點(diǎn)處于空閑狀態(tài).由于任務(wù)的離散獨(dú)立性，單個(gè)節(jié)點(diǎn)一次只能完成一次任務(wù)調(diào)度，即位置取值滿足(7)式的特性.

(7)

粒子速度主要貢獻(xiàn)是計(jì)算位置變化的概率信息，基于式(6)可以將離散的粒子速度表示為

(8)

粒子速度滿足

vij∈[-vmax,vmax],i∈{1,2,…,m},j∈{1,2,…,n}

(9)

2.2.2離散優(yōu)化的實(shí)現(xiàn)步驟

通過2.2.1中的分析可以看出，粒子速度主要度量了位置的變化概率，其范圍滿足[0,1]的約束要求.因此，為了將式(8)表示的速度參量限制在該范圍內(nèi)，需要進(jìn)行歸一化計(jì)算，具體的實(shí)現(xiàn)步驟為：

1)速度限定：

(10)

(10)式中，速度的范圍預(yù)先表示為[-vmax,vmax]，根據(jù)文獻(xiàn)[10]的研究，為了確保式(10)表示的函數(shù)信息更加擬合實(shí)際網(wǎng)格調(diào)度概率，取值vmax=4.

2)速度歸一化.

考慮到Sigmoid函數(shù)在處理單點(diǎn)信息峰值中具有較好的分辨能力，因此基于Sigmoid函數(shù)進(jìn)行速度的歸一化分析，具體的計(jì)算公式可以表示為

(11)

3)優(yōu)化實(shí)現(xiàn).

根據(jù)式(10)和(11)定義的歸一化速度，可以將離散優(yōu)化后的粒子信息更新過程表示為

(12)

(13)

(14)

式(14)中的R(0，1)同隨機(jī)數(shù)r1,r2一樣，取值范圍限制在[0,1]的范圍內(nèi).

3　計(jì)算機(jī)仿真分析

為分析本文方法的可行性和優(yōu)越性，基于DridSIM平臺(tái)搭建了10個(gè)網(wǎng)格節(jié)點(diǎn)分配模型，通過隨機(jī)生成不同的任務(wù)信息，并把隨機(jī)生成的業(yè)務(wù)依次送入網(wǎng)格系統(tǒng)調(diào)度分配.為直觀地說明本文方法的有效性，仿真中將本文方法同目前常用的min-min優(yōu)化方法和同樣采用了POS優(yōu)化處理的文獻(xiàn)進(jìn)行了對(duì)比分析，實(shí)驗(yàn)中網(wǎng)絡(luò)節(jié)點(diǎn)的具體參數(shù)設(shè)置參考文獻(xiàn)[10]，設(shè)置如表1所示.

表1　網(wǎng)絡(luò)節(jié)點(diǎn)資源分布情況

圖1針對(duì)不同任務(wù)總量的時(shí)間利用效率進(jìn)行了仿真分析，可以看出，文獻(xiàn)[9]和[10]采用的蟻群算法由于受到初值模糊的影響，收斂速度較差，時(shí)間利用效率最低，min-min優(yōu)化方法的時(shí)間利用效率適中，保持在70%左右，而本文方法通過離散優(yōu)化處理以后，整個(gè)系統(tǒng)的利用效率始終維持在75%左右，有了明顯的提升.

圖1　 網(wǎng)格時(shí)間利用效率對(duì)比分析

圖2針對(duì)單個(gè)網(wǎng)絡(luò)節(jié)點(diǎn)完成不同業(yè)務(wù)需求的時(shí)間消耗進(jìn)行了仿真分析，可以看出，隨著業(yè)務(wù)需求數(shù)量的增加，單個(gè)節(jié)點(diǎn)的時(shí)間消耗也在增加.在業(yè)務(wù)需求量較小的情況下，本文方法和傳統(tǒng)的三類方法都保持了基本相當(dāng)?shù)奶幚硭俣?當(dāng)業(yè)務(wù)量大于800以后，本文方法的處理速度明顯優(yōu)于其他方法，且隨著業(yè)務(wù)量的增加，這種運(yùn)算速度的優(yōu)勢(shì)越明顯.

圖2　單個(gè)網(wǎng)格節(jié)點(diǎn)的處理性能仿真

圖3顯示了本次仿真分析中各個(gè)資源節(jié)點(diǎn)所承載的業(yè)務(wù)優(yōu)化信息大小，可以看出，本文方法在各個(gè)節(jié)點(diǎn)承載的業(yè)務(wù)優(yōu)化量基本保持在15000的均衡水平，相對(duì)于其他三種方法，具有較好的資源調(diào)度能力，均勻單個(gè)節(jié)點(diǎn)的承載能力有所改善.

圖3　節(jié)點(diǎn)業(yè)務(wù)量承載分布圖

4　結(jié)語

針對(duì)傳統(tǒng)基于POS方法的網(wǎng)格資源分配存在收斂較慢、后期易陷入局部極值點(diǎn)的缺陷，筆者提出了一種改進(jìn)的離散優(yōu)化的粒子群網(wǎng)格資源分配方法.該方法在標(biāo)準(zhǔn)POS的基礎(chǔ)上針對(duì)網(wǎng)格分布特性，進(jìn)行離散改寫，并基于獲取的網(wǎng)格資源特性給出了優(yōu)化集合粒子位置、速度等相關(guān)參量的定義.參照標(biāo)準(zhǔn)POS方法推導(dǎo)分析了相應(yīng)的優(yōu)化矩陣和實(shí)現(xiàn)步驟，并通過粒子速度的歸一化處理，有效緩解POS后期粒子的局部早熟問題.最后，通過構(gòu)建的仿真平臺(tái)對(duì)該方法進(jìn)行了性能仿真分析，單個(gè)節(jié)點(diǎn)的處理速度明顯得到提升，且總體業(yè)務(wù)的時(shí)間利用率改善了5%.

[1] 都志輝，陳渝，劉鵬. 網(wǎng)格計(jì)算[M]. 北京：清華大學(xué)出版社，2002：9-11.

[2] 曹鴻強(qiáng)，肖儂，盧錫城，等. 一種基于市場(chǎng)機(jī)制的計(jì)算網(wǎng)格資源分配方法[J].計(jì)算機(jī)研究與發(fā)展，2002,39(8)：913-916.

[3] FOSTER I, KESEELMAN C, TUECKE S. The anatomy of the grid: enabling scalable virtual organizations[J]. Internation Journal of Supercomputer Applications, 2001,15(3):200-222.

[4] 李明楚，許雷，孫偉峰，等. 基于非完全信息博弈的網(wǎng)格資源分配模型[J].軟件學(xué)報(bào)，2012,23(2)：428-438.

[5] 胡毅，龔斌，王風(fēng)宇. 網(wǎng)格資源調(diào)度中基于云模型的蟻群算法[J].華中科技大學(xué)學(xué)報(bào)：自然科學(xué)版, 2010,38(I):64-67.

[6] 李志浩. 網(wǎng)格資源分配博弈的隨機(jī)動(dòng)態(tài)分析[J].計(jì)算機(jī)應(yīng)用研究, 2009, 26(3):852-854.

[7] 張忠平，溫麗娟. OPT-Min-Min：基于 Min-Min 網(wǎng)格資源調(diào)度算法的優(yōu)化[J].小型微型計(jì)算機(jī)系統(tǒng)，2014，35(7) : 1573-1577.

[8] KRAUTER K, BUYYA R, MAHESWARAN M. A taxonomy and survey of grid resource management systems for distributed computing[J]. Software: Practice and Experience, 2002,32(2):135-164.

[9] 黃文明，蘭靜，張陽. 基于改進(jìn)蟻群算法的網(wǎng)格資源調(diào)度[J].北京郵電大學(xué)學(xué)報(bào)，2009,39(S)：111-114.

[10] 李志浩，劉向東，段曉東. 改進(jìn)粒子群算法在網(wǎng)格資源分配中的優(yōu)化[J]. 計(jì)算機(jī)研集成制造系統(tǒng)，2009,15(12)：2375-2382.

[11] 梁正友，支成秀. 融合POS與ACS的網(wǎng)格資源分配研究[J].計(jì)算機(jī)工程與應(yīng)用，2009,45(9)：102-104.

[12] 胡毅，龔斌，劉運(yùn)臣. 基于蟻群算法的多QoS約束海量數(shù)據(jù)網(wǎng)格任務(wù)調(diào)度[J]. 華中科技大學(xué)學(xué)報(bào)：自然科學(xué)版, 2007,35(Ⅱ):90-93.

[責(zé)任編輯黃祖賓]

[責(zé)任校對(duì)蘇琴]

Grid Resource Allocation Method based on Discrete Particle Swarm Optimization

KONG Yi-yan1,SONG Wei-qi2

(1.LiuzhouVocational&TechnicalCollege，Liuzhou545006,China;2.LiuzhouCityVocationalCollege,Liuzhou545016,China)

In order to promote the efficiency of resource allocation and scheduling of grid computing accuracy, this paper proposes a grid resource allocation method based on discrete particle swarm optimization This method firstly gives the definition of discrete particle position and velocity; Second, the particles optimization matrix is deduced based on grid parameters. The paper analyzes the implementation steps of discrete optimization. The particle's local early-maturing problem in the late of POS is effectively relieved based on the particle velocity normalized processing. Finally, through the DridSim platform built 10 nodes, respectively. The utilization efficiency of resources and time consumption is carried on the simulation. And the results show that the method of time use efficiency increased by almost 5%.

particle swarm optimization; grid computing; resources allocation. discrete sequence

2016-03-20.

廣西教育廳項(xiàng)目(KY2015YB478)；廣西教育廳項(xiàng)目(KY2015LX745).

孔軼艷(1981-)，女，廣西柳州人，柳州職業(yè)技術(shù)學(xué)院講師，研究方向：計(jì)算機(jī)網(wǎng)絡(luò)通信；宋偉奇(1976-)，男，廣西柳州人，碩士，柳州城市職業(yè)學(xué)院副教授，研究方向：網(wǎng)絡(luò)安全.

TP393

A

1673-8462(2016)02-0081-04