1.一种移动边缘计算中基于混合遗传算法的计算卸载方法,其特征在于,包括步骤:S1.建立系统模型,得到子任务集在各处理器的计算时延以及各处理器之间的传输时延,并根据子任务集的约束关系确定子任务集中各任务层值;其中,系统模型由一个用户、一个移动云服务器和多个边缘服务器组成,由移动云服务器进行集中式决策调度方案;一个服务器只能同时处理一个任务,当用户端子任务集过多时,用户所属BS可以与资源池中其他BS通信,进行协同计算卸载,以满足用户需求;
S2.根据确定的任务层值和随机策略初始化种群,得到子任务集的初始种群个体,并根据初始种群个体中任务与处理器的映射关系,进行符号编码,得到任务调度序列,并对初始种群中的个体进行优化;
S3.构建适应度评价函数,根据适应度评价函数对优化后的初始种群中的个体进行选择操作,得到新的种群;
S4.构建交叉机制,使用基于禁忌表搜索算法的交叉操作对新的种群中的个体进行交叉;
S5.使用基于模拟退火算法的变异操作对新的种群中的个体进行变异操作;
S6.判断是否达到迭代步长,若否,则重复步骤S3-S5;若是,则输出全局最优解。
2.根据权利要求1所述的一种移动边缘计算中基于混合遗传算法的计算卸载方法,其特征在于,所述步骤S1中根据子任务集的约束关系确定子任务集中各任务层值,具体为:子任务集的约束关系使用有向无环图模型表示,表示为:G=
其中,V表示子任务集合,V={vi|1≤i≤N};E为子任务之间有向边集合,表示子任务之间优先约束关系;vi表示每个子任务,vi={di,gi};di表示完成任务所需cpu周期;gi表示任务输入数据大小;
子任务集中各任务层值,表示为:
其中,pre(vi)表示每个子任务vi的前继节点集合。
3.根据权利要求2所述的一种移动边缘计算中基于混合遗传算法的计算卸载方法,其特征在于,所述步骤S1中得到子任务集在各处理器的计算时延,具体为:第i个子任务在本地服务器上的计算时延可以表示为:第i个子任务在MEC服务器上的计算时延可以表示为:第i个子任务在MCC服务器上的计算时延可以表示为:其中,di表示任务大小;fL、fE、fC分别表示用户本地服务器、MEC服务器、MCC服务器的计算能力,即每秒钟所能提供的cpu周期数;
第i个子任务在服务器上的计算时延,表示为:
其中,α、β、γ表示0-1变量且α+β+γ=1。
4.根据权利要求3所述的一种移动边缘计算中基于混合遗传算法的计算卸载方法,其特征在于,所述步骤S1中得到各处理器之间的传输时延,具体为:用户向所属BS卸载任务的上传速率,表示为:
其中,P0表示用户端的固定发射功率;h0表示用户与BS之间的信道增益;σ2表示加性高斯白噪声的功率;w表示信道带宽;
所属BS向用户端的下行传速率,表示为:
其中,PE表示BS的固定发射功率;
各处理器之间的传输时延,表示为:
其中,cji表示各处理器之间的传输时延,即前继任务vj到后继任务vi的传输时延。
5.根据权利要求1所述的一种移动边缘计算中基于混合遗传算法的计算卸载方法,其特征在于,所述步骤S2中进行符号编码具体为:A1.基因值初始化,每个基因值代表该任务所分配到的处理器序号:ui=pi+i×M (9)其中,pi表示任务i初始分配的处理器序号;i表示任务编号;M表示处理器总数;
A2.基因值随机交换,对于分配到相同处理器任务的基因值,随机选取其中的两个基因值进行交换,进行 次交换,其中k为分配到该处理器上的任务总数。
A3.根据任务所处层值,由小到大进行排序;相同层值的任务,根据个体基因值,由大到小进行排序;得到子任务集整体调度列;
A4.由个体基因值,确定每个任务所分配的处理器:b=mod(ui/M) (10)其中,b表示任务vi所分配到的处理器序号;
A5.根据步骤A3中得到的子任务集调度序列和A2中得到的子任务与处理器之间的映射关系,得到各处理器上的调度序列。
6.根据权利要求5所述的一种移动边缘计算中基于混合遗传算法的计算卸载方法,其特征在于,所述步骤S2中对初始种群中的个体进行优化,具体为:B1.计算各处理器上的完工时延,得到时延最长处理器pl和时延最短处理器ps;
B2.在处理器pl上查找,是否存在某一任务与处理器上其他任务没有优先级制约关系,若是,则将该任务分配到处理器ps上;若否,则在pl上随机选择一个任务转发至ps;
B3.比较修改前后个体的总时延,若时延变短,则保留该分配方案;否则维持原有分配方案;
B4.重复执行步骤B2-B3,直至输出优化后的个体;
7.根据权利要求1所述的一种移动边缘计算中基于混合遗传算法的计算卸载方法,其特征在于,所述步骤S3中构建适应度评价函数,表示为:其中,Ttotal表示子任务集的总时延,表示为:Ttotal=max{si+ti} (12)其中,ti表示任务i的执行时延;si表示任务vi的开始执行时间,表示为:其中, 表示资源约束条件下的开始执行时间; 表示依赖约束条件下的开始执行时间;
资源约束条件下的开始执行时间,表示为:
依赖约束条件下的开始执行时间,表示为:
其中,任务k为任务vi在所分配处理器调度序列中的前继任务。
8.根据权利要求7所述的一种移动边缘计算中基于混合遗传算法的计算卸载方法,其特征在于,所述步骤S3中根据适应度评价函数对优化后的初始种群中的个体进行选择操作,具体为:C1.计算种群中每个个体的累积概率:
其中,P(Uj)表示个体Uj被选择的概率,表示为:其中,SN表示种群中个体总数;
C2.在[0,1]内产生随机数r;
C3.若r≤q(1),则个体U1被选中;
C4.若q(k-1)≤r≤q(k),2≤k≤SN则个体Uk被选中;
C5.重复步骤C2—C4,直至新的种群生成。
9.根据权利要求1所述的一种移动边缘计算中基于混合遗传算法的计算卸载方法,其特征在于,所述步骤S4具体为:S41.初始化,设定当前种群中个体最大适应度函数值为渴望水平,设定禁忌表元素长度、交叉率、阈值,将禁忌表设为空;
S42.根据交叉率,从种群中选取相邻的两个个体,进行随机编号交叉得到两个子代个体;
S43.比较两个子代个体的适应度值是否大于渴望水平,若是,则子代进入下一代,更新渴望水平为当前个体的适应度值,并执行步骤S45;若否,则执行步骤S44;
S44.查找禁忌表中是否存在某个元素,使得适应度值与元素值的差值小于阈值,若否,则子代进入下一代,并执行步骤S45;若是,则舍弃交叉后子代,父代进入下一代,并执行步骤S46;
S45.更新禁忌表中元素,当表中元素超过表长时,舍弃最初进入表中元素;
S46.返回步骤S42,直至种群中个体交叉完成。
10.根据权利要求1所述的一种移动边缘计算中基于混合遗传算法的计算卸载方法,其特征在于,所述步骤S5具体为:S51.初始化,设定初始温度T0、终止温度Tf、降温值ΔT、内循环次数L;将种群中选取的个体Uj的适应度值设为初始解,初始最优解为Ubest=Uj,初始迭代温度为Tk=T0;
S52.对个体Uj进行变异操作,变异后个体为U'j,计算总时延增量Δf,表示为:Δf=Ttotal(U'j)-Ttotal(Uj) (18)S53.判断U'j的总时延是否小于Ubest的总时延,若是,则Ubest=U'j;
S54.判断总时延增量Δf是否小于0,若是,则Uj=U'j;若否,则判断 是否大于τ,若是,则Uj=U'j;若否,则Uj=Uj;
S55.循环执行步骤S52-S54,并判断是否达到内循环次数,若是,则执行步骤S56;若否,则执行步骤S52;
S56.计算迭代温度Tk=Tk-ΔT,当Tk<Tf时输出Ubest,否则执行步骤S52。