刘波涛    湖南文理学院计算机科学与技术学院  常德 邮编：415000

　　基金项目：湖南省教育厅项目（No. 12C0822）

　　地址 湖南省常德市湖南文理学院计算机科学与技术学院  刘波涛 13973605173

　　摘要：出于对异构网格环境中任务调度问题对所面临的安全性研究欠缺的考虑，同时考虑到保密性、完整性和真实性等安全性因素，将相应的安全效益函数构造出来；以网格节点的历史行为特点为依据，将节点的信誉度动态评估策略提了出来，在行为特点的基础上将一种离散粒子群算法提了出来，在此基础上将任务安全级调度新模型建立起来。

　　关键词：网格计算；任务调度；离散粒子群算法

　　任务调度系统是网格环境中的重要组成部分，因为网格资源节点存在开放性、异构性的特征。所以，在执行任务的时候，不但要确保结果的正确性而且要保证执行或传输过程中敏感数据不会被篡改、冒名顶替或泄密等。本文与任务安全调度的具体特点相结合，以实际问题的离散空间特征为基础对粒子的位置表示方法进行了定义，同时重新定义了粒子的速度及其运算规则，进而将新的离散粒子群算法提了出来，并且分析了算法的收敛性和复杂度。接下来进行具体的阐述。

　　1 任务安全调度模型

　　网格节点原本存在的安全性，决定因素就在于资源节点采用的算法或方法。例如，保密性的实现通常借助的是不同加密算法；完整性的实现是借助不同的Hash 函数；真实性主要是借助不同的数字签名技术来鉴别通讯实体身份的真实性，从而确保处理任务的提交者是合法的用户。接下来以保密性为例，对网格资源节点的保密性安全水平值的合理设计进行说明。假设网格环境下全部资源节点一共采用了八个加密算法[1]。IDEA 加密算法性，所以对对应的保密性，假设其安全水平值是1 ，那么其他不论是哪一个网格资源的节点 Pj 上，都可以计算出关于加密算法的一个安全水平值，主要是根据它的性能，计算公式为S e j =13.5/ μej（k）， 1 ≤k ≤8 （1）

　　如此便依据加密算法性能的差异性，设定其安全值范围是0.08-1 。同意的道理，网格资源节点Pj 根据其上运用的 Hash 函数，还运用了一项技术类型，即数字签名，将完整和真实的实际水平提了出来，分别是Sgj 和 S aj。

　　2 离散粒子群算法

　　在对任务安全调度（组合优化）问题进行求解的时候，因为难以采用定量方式表示目前粒子和粒子的最佳位置，造成粒子速度以及位置无法以规范的粒子群的演进方程为参照进行更新，这时候PSO 是基本上失效的。

　　2 .1  粒子进化方程的重新定义

　　定义1  用 n 维向量X定义粒子位置，其中X =（x1, …， xi , …， xn）。这指代的是任务分配调度方案。向量中 1 ≤xi ≤m指代的是在节点 xi 上的第i个任务分配，任务不同的情况下，在同一节点上进行分配，那么其调度次序采用的调度准则是：短任务以及具有较高安全级别的任务都处于优先选择的地位。

　　定义2   将两个位置相减，最终得出结果是速度 V , 使用符号 “-”指代新的减法运算。个体极值 Pibest 和全局极值 Gbest，速度指代的是影响现在粒子位置程度， 其定义为

　　（2）

　　式中：c1 、c2 为影响因 子（也称 学习因子）；函数 h（X i , P i best）为 X i 对P i best 的学习操作 ,其 Xi 向 Pibest 第 j 维进行分量学习，其具体过程表示是

　　（3）

　　式中 :p1 为个体极值 Pi best影响现在粒子的程度的概率；rand[0，1]为[0，1]间的一种随机数字。Xi 对全局极值Gbest存在比较接近的学习操作模式。

　　定义3 位置和速度进行的加法运算促使粒子位置移动得以实现，促使粒子达到了一个不一样的新位置，用符号对新加法运算进行表示，其定义是

　　（4）

　　对于计算新位置的任一维 x′ij ，可这样计算其值

　　（5）

　　因为离散量运算存在特殊性，惯性以致使扰动产生为主要功能，主要是为了促进粒子种群更加趋于多样化，以免算法出现早熟或者是局部收敛的情况。本文将一个可实现均匀扰动的速度引进来，也就是依次以等概率从[ 1 , m] 中随机产生一个，这样连续执行n 次，就会获取一个新速度 Veven =（v′1 , … , v′i , …， v′n）作为扰动速度。这一扰动速度对保持种群的多样性是非常有帮助的，可以使算法陷入局部最优的情况得到有效防止，而且这一扰动速度的特点就在于简单、易执行。

　　2 .2 离散粒子群算法设计

　　以前文对粒子进化方程的定义为基础，就网格任务安全调度问题来看，其离散粒子群算法DPSO 流程是这样的：

　　步骤 1 对粒子群的种群规模进行定义，即 pop ，对其最大进化代数 进行定义，即maxgen。对于粒子群中粒子的位置、速度则随机进行初始化。

　　步骤 2 将粒子的Pi best设置为现在的具体位置， Gbest设置成最佳粒子初始群体中的位置。

　　步骤 3 对离散粒子群中的所有粒子执行如下操作： （1）产生一个均匀扰动速度 Veven , 将其作用于当前粒子；（2）计算粒子群中所有粒子的适应度值，运用式（2）更新粒子速度和位置。

　　步骤 4 对不同粒子的个体极值Pi best进行更新，同时以各粒子的个体极值为依据来对全局极值 Gbest进行更新。

　　步骤 5 对算法终止条件进行判断，确定其满足与否，若是条件满足，那就直接转向步骤6，要不然就进入步骤3。

　　步骤 6 输出全局极值 Gbest。

　　3 仿真实验对本文提出的DPSO 算法高效性进行验证，分别进行了仿真实验，包括任务调度的性能指标（调度长度和安全性）和算法执行效率（收敛性）方面。而且对于同类问题求解，对比分析了基于连续空间的 PSO 和基于进化思想的GA。

　　图 1　本文算法与 GA 的收敛性比较

　　实验 1 为了对算法的收敛特性进行对比，将本文算法、PSO及GA 在500次迭代过程中的调度长度变化曲线给出（见图1）。相比GA，本文算法和 PSO的收敛性更佳，而且本文的收敛性比PSO更佳。

　　（a）任务调度长度比较                          （b）任务安全值比较

　　图 2　节点数固定任务数变化时算法的性能指标比较

　　实验 2 性能指标对比。

　　（1）对 m =20 个网格节点，在任务数 n 变化（为100-500个子任务）时，本文算法、PSO及GA各运行20次的平均性能指标见图 2。保持网格环境不变，从图2a可以看出，不断增加的任务数，会相应的增加任务调度长度，其中本文算法和PSO 要比GA明显好很多。尤其是伴随问题规模的扩大，就更加突出其优势。从图2b可以看出，伴随任务数的提高，任务对在网格节点上获得较优安全值会存在更为激烈的竞争，这就导致任务平均安全值的整体下降，面对同等的条件，本文算法存在显著的优势。

　　（a）任务调度长度比较                            （b）任务安全值比较

　　图 3　任务数固定网格节点数变化时算法的性能指标比较

　　（2）固定任务数n =200 ，在网格环境节点数发生变化的时候，图3可见性能指标存在差异情况下的对比结果。从图 3a 我们可以看出，节点数越来越扩充，任务调度长度也就越来越小，主要原因就在于任务在调度时选择的执行网格节点可以是性能更好的，这就使得任务调度长度减小了。从由图3b可以看出，网格节点数扩充时任务获得了更高的安全值，其中相同的条件下本文算法会获得最大值。

　　4 结 论

　　总而言之，本文在综合分析异构网格任务调度问题的基础上，将一个网格任务安全级调度新模型建立起来，同时提出了一种新的离散粒子群算法来就模型进行求解，今后将着重研究和探讨网格任务调度和动态多目标的网格任务调度问题。

　　参考文献：

　　[1] BRAUN T D, SLEGEL H J, BECJ N .A compariso n of eleven static heuristics for mapping a class o f independent ta sks o nto he te rog eneo us distributed computing sy stems [ J] .IEEE Tr ans on Pa rallel and Distributed Computing , 2001, 61（6）：810-837.

　　[ 2] 薛正华， 刘伟哲， 董小社， 等。基于思维进化的集群作 业调度方法研究 [J] .西安交通大学学报， 2008 , 42 （6）：651-654 .

　　[3] 孟宪福， 张晓燕。对等网络环境下多目标约束的并行 任务调度策略研究[J] .计算机集成制造系 , 2008 , 14 （4）：761-766.