1.一种移动云环境下基于任务依赖的计算迁移方法,其特征在于:该方法包括以下步骤:
S1:建立计算任务模型;
用一个带权有向无环图G(V,ξ)来表示产生的一组计算任务,其中V={v1,v2,v3,...,vn}表示这一组计算任务的集合,n表示这一组计算任务的数量,ξ={h(vi,vj)|vi,vj∈V}表示计算任务之间的依赖关系集合,当h(vi,vj)=0时,表示任务vi和任务vj之间没有依赖关系,当h(vi,vj)=1时,表示任务vi和任务vj之间只有时序依赖,当h(vi,vj)=2时,表示任务vi和任务vj之间存在时序和数据双重依赖;
用一个四元组vi=(di,wi,ri,tyi)来表示计算任务,其中di表示vi任务本身的数据量,单位为MB;wi表示处理该任务时所需要的计算量,单位为MB;ri表示任务vi的处理结果的数据量,单位为MB;tyi表示计算任务的类型;计算任务根据各自实现目的分为不同的类型;
S2:建立计算迁移系统中的计算资源模型;
移动云计算环境下的计算资源由移动终端的本地资源和微云资源两部分组成,移动终端的本地资源和微云资源之间通过局域网进行通信;
ty ty
通过一个四元组(flocal ,Plocal,Psend,Prec)来表示移动终端的本地资源,其中,flocal 表示单位时间内处理的数据量,单位为GHz,ty∈TY表示移动终端对不同类型任务的计算能力,Plocal表示本地的计算功率,单位为w;
Psend表示本地发送数据的功率,单位为w;Prec表示本地接收数据的功率,单位为w;k表示ty微云的编号,k=1,2,...,m,fk 表示微云的不同计算能力,单位为GHz,ty∈TY;移动终端和微云之间通过局域网进行通信,该局域网带宽统一通过Bc表示,Bc单位为MB/ms;
S3:在系统模型的基础上给出迁移问题的数学形式描述;
在移动云计算环境下,由移动终端产生的计算任务,有在本地处理和迁移到微云端处理两种选择;用一个一维向量S=(s1,s2,s3,...,sn)来表示迁移方案,其中si∈{0,1,...,k,...,m},m表示微云的个数;
当si=0的时候,表示任务vi在本地进行处理,此时,分别计算其响应时间和终端能耗;
当si=1,...,k,...,m的时候,表示任务vi将要被迁移到微云中进行处理,此时分别计算其响应时间和终端能耗;
当任务vi的前驱任务vj与任务vi之间存在数据依赖并且处理位置不同时,需要考虑任务vj向任务vi之间的数据传递,若任务vi有多个此类前驱,则需要计算多个数据传递;
采用效用函数U来表示最终的优化结果,最终目标是响应时间最小并且终端能耗最低,效应函数U越小即代表迁移方案越接近最优,而此时所对应的迁移方案S即为最终迁移方案;
S4:设计遗传改进算法;
根据S1~S3步骤,结合遗传算法,以期获得响应时间和终端能耗总体较优的迁移方案;
遗传算法模拟生物的遗传规律,从初始个体出发,通过选择、交叉和变异操作来产生新的个体,如此不断进化下去,直到满足停止条件;
S41:首先进行种群初始化操作,即初始化计算任务的处理位置;
对于一个任务vi的处理位置,随机产生si={0,...,m}的随机整数,用相同的方法遍历所有的计算任务,获得作为染色体的初始位置集合S0,种群由矩阵pop表示;
S42:在所述S41步骤的基础上,然后进行适应性值的计算;
每个染色体代表一个解,满足最优适应性值的个体即为最优解,目标函数即为适应度函数,由该函数计算得到的值称为适应性值;
S43:在所述S42步骤的基础上进行选择操作,来选择适应性值较优的部分染色体,采用轮盘赌法来进行选择操作,重复次数为popsize,得到的个体进行下一步操作;
S44:在所述S43步骤的基础上,选择操作之后得到的个体进行交叉操作,首先,根据交叉概率pc选择两个即将进行交叉操作的个体作为父代个体,接着在两个父代个体的同一位置选取一个交叉点,该交叉点之后的第一个基因所对应的计算任务满足如下条件:在交叉点之后交换这两个父代个体的基因,获得
两个新的子代个体;
S45:在所述S44步骤的基础上,交叉操作之后进行变异操作,首先,根据变异概率pm选择一个即将进行变异操作的染色体,然后在该染色体中选择一个基因si,该基因所对应的计算任务满足如下条件: 将该基因进行变异,使新基因si’=sj,之后便可得到一个新的个体;
S46:重复S1~S5步骤,直到满足停止条件;
S5:得到最终迁移方案;
当迭代次数达到设定的值之后就会停止,然后将适应性U最优的个体输出,得到迁移方案S即为最终的迁移方案。
2.根据权利要求1所述的一种移动云环境下基于任务依赖的计算迁移方法,其特征在于:在所述S5步骤中,当迭代次数达到设定的值之后就会停止,每一次迭代都会将当前的最优适应性值以及该值的个体保存下来,迭代停止后,将适应性U最优的个体输出,得到迁移方案S即为最终的迁移方案。