基于离散粒子群优化算法的网格任务调度方法

《基于离散粒子群优化算法的网格任务调度方法》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。

1、基于离散粒子群优化算法的网格任务调度方法基于离散粒子群优化算法的X格任务调度方法刘波涛    湖南文理学院计算机科学与技术学院  常德 邮编：415000  基金项目：湖南省教育厅项目（No. 12C0822）  地址湖南省常德市湖南文理学院计算机科学与技术学院 刘波涛13973605173  :出于对异构X格环境中任务调度问题对所面临的安全性研究欠缺的考虑，同时考虑到保密性、完整性和真实性等安全性因素，将相应的安全效益函数构造出来；以X格节点的历史行为特点为依据，将节点的信誉度动态评估策略提了出来，在行为特点的基础上将一种离散粒子群算法提了出来，在此基础上将任务安全级调度新模型建立起来。关键

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

3、不同的Hash函数；真实性主要是借助不同的数字签名技术来鉴别通讯实体身份的真实性，从而确保处理任务的提交者是合法的用户。接下来以保密性为例，对X格资源节点的保密性安全水平值的合理设计进行说明。假设X格环境下全部资源节点一共采用了八个加密算法[1]。IDEA加密算法性，所以对对应的保密性，假设其安全水平值是1，那么其他不论是哪一个X格资源的节点Pj上，都可以计算出关于加密算法的一个安全水平值，主要是根据它的性能，计算公式为Sej=13.5/μej(k),1≤k≤8(1)如此便依据加密算法性能的差异性，设定其安全值范围是0.08-1。同意的道理，X格资源节点Pj根据其上运用的Hash函数，还运用了

4、一项技术类型，即数字签名，将完整和真实的实际水平提了出来，分别是Sgj和Saj。 2离散粒子群算法在对任务安全调度(组合优化)问题进行求解的时候，因为难以采用定量方式表示目前粒子和粒子的最佳位置，造成粒子速度以及位置无法以规范的粒子群的演进方程为参照进行更新，这时候PSO是基本上失效的。2.1 粒子进化方程的重新定义 定义1 用n维向量X定义粒子位置，其中X=(x1,…,xi,…,xn)。这指代的是任务分配调度方案。向量中1≤xi≤m指代的是在节点xi上的第i个任务分配，任务不同的情况下，在同一节点上进行分配，那么其调度次序采用的调度准则是：短任务以及具有较高安全级别的任务都处于优先选择的地位

5、。定义2  将两个位置相减，最终得出结果是速度V,使用符号“-”指代新的减法运算。个体极值Pibest和全局极值Gbest，速度指代的是影响现在粒子位置程度，其定义为（2）式中:c1、c2为影响因子(也称学习因子);函数h(Xi,Pibest)为Xi对Pibest的学习操作,其Xi向Pibest第j维进行分量学习，其具体过程表示是 （3）式中:p1为个体极值Pibest影响现在粒子的程度的概率；rand[0，1]为[0，1]间的一种随机数字。Xi对全局极值Gbest存在比较接近的学习操作模式。定义3位置和速度进行的加法运算促使粒子位置移动得以实现，促使粒子达到了一个不一样的新位置，用符号对新加

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

7、问题来看，其离散粒子群算法DPSO流程是这样的：步骤1对粒子群的种群规模进行定义，即pop，对其最大进化代数进行定义，即maxgen。对于粒子群中粒子的位置、速度则随机进行初始化。步骤2将粒子的Pibest设置为现在的具体位置，Gbest设置成最佳粒子初始群体中的位置。步骤3对离散粒子群中的所有粒子执行如下操作:(1)产生一个均匀扰动速度Veven,将其作用于当前粒子；(2)计算粒子群中所有粒子的