基于粒子群离散优化的网格资源分配方法*

孔轶艳, 宋伟奇

(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