基于粒子群離散優化的網格資源分配方法*

孔軼艷, 宋偉奇

(1.柳州職業技術學院，廣西 柳州　545006; 2.柳州城市職業學院，廣西 柳州　545006)

?

基于粒子群離散優化的網格資源分配方法*

孔軼艷1, 宋偉奇2

(1.柳州職業技術學院，廣西 柳州545006; 2.柳州城市職業學院，廣西 柳州545006)

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

粒子群優化；網格計算；資源分配；離散序列

0　引言

隨著物聯網技術的快速發展，面向大數據處理分析的計算機網格技術成為計算機通信網絡領域的熱點研究問題之一[1-2].該技術主要針對高速網絡數據，采用并行分布式計算的方法實現信息快速有效的交互，其中網格資源的合理分配與調度是該方法的重要基礎[3].

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

1　網格資源模型

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

Cmax=max{Ci}

(1)

優化的目的就是在給定業務和節點集合的基礎上，實現式(1)中的Cmax最小化.

2　粒子群離散優化分析

2.1基本粒子群算法介紹

(2)

(3)

(4)

(5)

2.2離散優化分析及實現

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

2.2.1離散位置和速度

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

(6)

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

(7)

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

(8)

粒子速度滿足

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

(9)

2.2.2離散優化的實現步驟

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

1)速度限定：

(10)

(10)式中，速度的范圍預先表示為[-vmax,vmax]，根據文獻[10]的研究，為了確保式(10)表示的函數信息更加擬合實際網格調度概率，取值vmax=4.

2)速度歸一化.

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

(11)

3)優化實現.

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

(12)

(13)

(14)

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

3　計算機仿真分析

為分析本文方法的可行性和優越性，基于DridSIM平臺搭建了10個網格節點分配模型，通過隨機生成不同的任務信息，并把隨機生成的業務依次送入網格系統調度分配.為直觀地說明本文方法的有效性，仿真中將本文方法同目前常用的min-min優化方法和同樣采用了POS優化處理的文獻進行了對比分析，實驗中網絡節點的具體參數設置參考文獻[10]，設置如表1所示.

表1　網絡節點資源分布情況

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

圖1　 網格時間利用效率對比分析

圖2針對單個網絡節點完成不同業務需求的時間消耗進行了仿真分析，可以看出，隨著業務需求數量的增加，單個節點的時間消耗也在增加.在業務需求量較小的情況下，本文方法和傳統的三類方法都保持了基本相當的處理速度.當業務量大于800以后，本文方法的處理速度明顯優于其他方法，且隨著業務量的增加，這種運算速度的優勢越明顯.

圖2　單個網格節點的處理性能仿真

圖3顯示了本次仿真分析中各個資源節點所承載的業務優化信息大小，可以看出，本文方法在各個節點承載的業務優化量基本保持在15000的均衡水平，相對于其他三種方法，具有較好的資源調度能力，均勻單個節點的承載能力有所改善.

圖3　節點業務量承載分布圖

4　結語

針對傳統基于POS方法的網格資源分配存在收斂較慢、后期易陷入局部極值點的缺陷，筆者提出了一種改進的離散優化的粒子群網格資源分配方法.該方法在標準POS的基礎上針對網格分布特性，進行離散改寫，并基于獲取的網格資源特性給出了優化集合粒子位置、速度等相關參量的定義.參照標準POS方法推導分析了相應的優化矩陣和實現步驟，并通過粒子速度的歸一化處理，有效緩解POS后期粒子的局部早熟問題.最后，通過構建的仿真平臺對該方法進行了性能仿真分析，單個節點的處理速度明顯得到提升，且總體業務的時間利用率改善了5%.

[1] 都志輝，陳渝，劉鵬. 網格計算[M]. 北京：清華大學出版社，2002：9-11.

[2] 曹鴻強，肖儂，盧錫城，等. 一種基于市場機制的計算網格資源分配方法[J].計算機研究與發展，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] 李明楚，許雷，孫偉峰，等. 基于非完全信息博弈的網格資源分配模型[J].軟件學報，2012,23(2)：428-438.

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

[6] 李志浩. 網格資源分配博弈的隨機動態分析[J].計算機應用研究, 2009, 26(3):852-854.

[7] 張忠平，溫麗娟. OPT-Min-Min：基于 Min-Min 網格資源調度算法的優化[J].小型微型計算機系統，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].北京郵電大學學報，2009,39(S)：111-114.

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

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

[12] 胡毅，龔斌，劉運臣. 基于蟻群算法的多QoS約束海量數據網格任務調度[J]. 華中科技大學學報：自然科學版, 2007,35(Ⅱ):90-93.

[責任編輯黃祖賓]

[責任校對蘇琴]

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.

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

孔軼艷(1981-)，女，廣西柳州人，柳州職業技術學院講師，研究方向：計算機網絡通信；宋偉奇(1976-)，男，廣西柳州人，碩士，柳州城市職業學院副教授，研究方向：網絡安全.

TP393

A

1673-8462(2016)02-0081-04