CN114567933B 基于改进遗传算法的异构云雾协同网络中的资源分配方法（南京邮电大学）

(19)国家知识产权局(12)发明专利公司32224HO4W72/044(2023.01)基于改进遗传算法的异构云雾协同网络中本发明公开基于改进遗传算法的异构云雾终端设备将计算任务迁移所需的上行链路的传明在雾端收集终端设备所需完成计算任务的数q2C6:I(aₙ=m)(t+t°+t)≤tm,n∈N,m∈Sn∈N,N={1,2,…,N}表示终端设备的集合，终端设备的任务卸载策略表示为3计算资源；表示完成终端设备的所有计算任务所需的最小计算资源，tm×表示终端设备完成所有计算t表示终端设备n将计算任务迁移至雾端处理所能接受的最在本地完成计算任务所能接受的最大时延，t表示终端设备n将计算任务迁移至云端处理染色体0S(n)表示a,染色体RA(n)表示p,染色体FA(n)表第三步，将交叉算子作用于群体g(t),基于自适应交叉概率Pc交换被选择的成对个体第四步，将变异算子作用于群体g(t),基于自适应变异概率Pm改变被选择的个体的部2.根据权利要求1所述的基于改进遗传算法的异构云雾协同网络中的资源分配方法，e=I(-M≤aₙ≤-1)e”,m+I(aM°=φfnm+pr;",4Pnm=n,Pnm,设备n的总传输功率；移至雾端时的上行链路传输速率；P⁰=ξ(f)²C,P!=βe+αM,M=φfn.m+pr:"",53.根据权利要求2所述的基于改进遗传算法的异构云雾协同网络中的资源分配方法，t=I(-M≤a≤-1)tnm+I(aₙ=-Mt=I(1≤aₙ≤M)t,m+I(aₙ=M+14.根据权利要求3所述的基于改进遗传算法的异构云雾协同网络中的资源分配方法，6OS8+(n)=σn*OS&(n)+(RA8+¹(n)=(1-σn)*RA&(n)+RA8+¹(n)=σn*RAå(n)+(1-σFA8+(n)=(1-σn)*FA&(n)+σFA+(n)=σn*FA(n)+(1-σn)(n);77.根据权利要求6所述的基于改进遗传算法的异构云雾协同网络中的资源分配方法，OS部分采用整数变异；RA和FA部分采用非均匀变异，随机扰动被选择的个体的基因值，获得具有新基因值的被选择的个体；随机生成一个2元变异掩模序列θ,n∈{1,2,...,N},确定被选择的个体的需要产生变异的基因点；若OS(n)的基因点发生变异，则该基因点的基因值将会变成其相反数；若RA(n)或FA(n)的基因点发生变异，则基于变异公式更新该基因点的基因值；变异公式为：x⁸(n)表示发生变异的基因点的基因值，△(t,y)表示[0,y]范围内符合非均匀分布的一个随机数，y代表Um-x⁸(n)或x⁸(n)-Umi,y取值范围为表示变异点x⁸(n)取值范围的最大值，表示变异点x⁸(n)取值范围的最小值；random(0,1)表示随机产生0式中，r为[0,1]范围内符合均匀概率分布的一个随机数；b是设定的系统参数，决定了随机扰动对进化代数t的依赖程度。8.根据权利要求7所述的基于改进遗传算法的异构云雾协同网络中的资源分配方法，将自适应交叉概率Pc和自适应变异概率Pm均分别与当前种群的适应度函数值关联：f₁(g)表示染色体i的适应度函数值，faverage(8)表示当前种数值，fm.n(g)表示当前种群中的染色体适应度函数值中的最小值；依据适应度标准差公式计算当前种群的个体适应度标准差σ,适应度标准差公式为：继续进行有效搜索，若σ≤φ则count的数值增加1,若σ>φ则count=0;8在当前迭代次数达到[T/2]次之前，若count=V,则判定陷入局部最优解，对当前种群进行高斯扰动并增大变异概率Pm使当前变异概率Pm变为2Pm,迫使搜索跳出局部最优解，[T/2]为向下取整。9技术领域[0001]本发明涉及基于改进遗传算法的异构云雾协同网络中的资源分配方法，属于资源分配技术领域。背景技术[0002]物联网概念是在互联网概念的基础上，将其用户端延伸和扩展到任何物品与物品之间，进行信息交换和通信的一种网络概念。物联网是实现智能社会的关键因素，为了避免物联网设备消耗巨大的计算资源，物联网设备可以将其计算任务迁移到云端，这样可以缓解设备的计算压力。然而，云计算可能会产生不可避免的时延和传输能耗。因此，作为云计算的延伸，雾计算的提出引发了广泛的关注。[0003]雾计算并非是性能强大的服务器，而是由性能较弱、更为分散的各种功能计算机组成，雾计算是介于云计算和个人计算之间的，是半虚拟化的服务计算架构模型，强调数量，不管单个计算节点能力多么弱都要发挥作用。与云计算相比，雾计算所采用的架构更呈分布式，更接近网络边缘。雾计算将数据、数据处理和应用程序集中在网络边缘的设备中，而不像云计算那样将它们几乎全部保存在云中，数据的存储及处理更依赖本地设备，而非[0004]雾计算和云计算是高度互补的，两者的资源协同利用是非常重要和必要的。只有将云计算和雾计算两者协同利用，才能有效降低系统的成本。此外，随着无线局域网的广泛部署，设备通常需要连接到网络中的多个不同的无线接入点(WAP)。在异构网络中，设备不仅需要决定任务是否卸载，还需要选择合适的无线接入点以获得较高的数据传输速率。因此，随着考虑的场景更加全面，资源优化问题也更加复杂。在异构环境中，当系统的无线接入网点数量较多时，得到最优卸载策略的计算复杂度会很大，会造成很大的计算时延。因此，降低计算量成为异构环境下云雾协同计算能否实用的关键点。发明内容[0005]本发明所要解决的技术问题是克服现有技术的缺陷，提供基于改进遗传算法的异构云雾协同网络中的资源分配方法，本发明在雾端收集终端设备所需完成计算任务的数量，完成计算任务所需的计算量以及完成任务所能接受的最大时延这三个参数，通过改进遗传算法实现对终端设备的卸载决策、分配到的计算资源和传输功率的联合优化，得到了异构网络中基于云雾协同计算的资源分配方案，解决了异构网络中雾计算和云计算共存协同的资源分配问题，减少了计算量，本发明在雾端收集终端设备所需完成计算任务的数量，完成计算任务所需的计算量以及完成任务所能接受的最大时延这三个参数，通过改进遗传算法实现对终端设备的卸载决策、分配到的计算资源和传输功率的联合优化，得到了异构网络中基于云雾协同计算的资源分配方案，解决了异构网络中雾计算和云计算共存协同的[0006]为达到上述目的，本发明提供基于改进遗传算法的异构云雾协同网络中的资源分{aₙ=ili∈S,n∈N},aₙ=0表示终端设备nm个SBSs将计算任务卸载至云端；aₙ=M+1表示终端设备n选择通过MBS将计算任务卸载至雾aₙ=m为真时等于1,否则等于0;[0025]t表示终端设备n将计算任务迁移至雾端处理所能接受的最大时延，t⁰表示终端设备n在本地完成计算任务所能接受的最大时延，t表示终端设备[0038]n是由第m个基站分配给终端设备n的正交子信道数，K}个子信道，每个子信道最多只能分配给一个终端设备使用；@表示第m个基站的信道带[0039]Pn表示终端设备n通过子信道k向第m个基站传输计算任务的功率，g”表示终端的上行链路传输速率。[0065]第三步，将交叉算子作用于群体g(t),基(t+1)赋值给群体g(t)。[0080]以基因为最小交叉单位，随机获取被选择的染色体对的基因交叉位置点；[0081]根据下式在基因交叉位置点进行交叉操作：[0088]式中，序列σ,n∈{1,2,...,N}表示染色体上的基因交叉位置点，遵循伯努利分[0089]表示当前父辈染色体a的染色体OS(n),RA(n)表示当前父辈染色体a的染色体RA(n),FA(n)表示当前父辈染色体a的染色体FA(n);[0090]OSB(n)表示当前父辈染色体b的染色体OS(n),RA⁸(n)表示当前父辈染色体b的染色体RA(n),FA'(n)表示当前父辈染色体b的染色体FA(n);[0091])表示交叉后新生成的子代染色体a的染色体OS(n),)表示交叉后新生成的子代染色体a的染色体RA(n),)表示交叉后新生成的子代染色体a的染色体[0092]OSS+¹(n)表示交叉后新生成的子代染色体b的染色体OS(n),表示交叉后新生成的子代染色体b的染色体RA(n),FA+¹(n)表示交叉后新生成的子代染色体b的染色体[0094]OS部分采用整数变异；[0095]RA和FA部分采用非均匀变异，随机扰动被选择的个体的基因值，获得具有新基因值的被选择的个体；[0097]随机生成一个2元变异掩模序列θ,n∈{1,2,...,N},确定被选择的个体的需要产生变异的基因点；[0098]若OS(n)的基因点发生变异，则该基因点的基因值将会变成其相反数；[0099]若RA(n)或FA(n)的基因点发生变异，则基于变异公式更新该基因点的基因值；[0100]变异公式为：[0102]x⁸(n)表示发生变异的基因点布的一个随机数，y代表U-x⁸(n)或x⁸(n)-Umi,y取值范围为[Ui,Umax],Un表示变异机产生0或1;[0113]依据适应度标准差公式计算当前种群的个体适应度标准差σ,适应度标准差公式为：种群进行高斯扰动并增大变异概率Pm使当前变异概率Pm变为2Pm,迫使搜索跳出局部最优算量以及完成任务所能接受的最大时延这三个参数，通过改进遗传算法(IGA)实现对终端设备的卸载决策，分配到的计算资源和传输功率的联合优化，得到了异构网络中基于云雾协同计算的资源分配方案，解决了异构网络中雾计算和云计算共存协同的资源分配问题，并在保持性能的基础上减少了计算量；[0120]本发明改进了一般系统中简单的分层计算模型，加入了异构场景。在异构网络中，终端设备不仅需要决定任务是否卸载，还需要选择合适的无线接入点以获得较高的数据传输速率。虽然考虑的场景更加复杂，资源优化问题也更加复杂，但更符合现实中的应用场[0121]本发明用遗传算法求解该系统资源分配问题，针对传统遗传算法无法解决复杂约束函数的问题，引入了罚函数来反映解对于约束条件的偏离程度，从而淘汰不可行解；[0122]本发明提出了一种遗传算法的参数自适应改进方法，提升遗传算法的收敛性能，提出一种依据种群适应度标准差的变异概率扰动方法，使得算法能跳出局部最优的情况继续搜索。附图说明[0123]图1为本发明的异构网络模型图；[0124]图2为本发明中遗传算法的流程示意图；[0125]图3为本发明中染色体的结构图；[0126]图4为本发明中交叉过程结构图；[0127]图5为本发明中变异过程的结构图。具体实施方式[0128]以下实施例仅用于更加清楚地说明本发明的技术方案，而不能以此来限制本发明的保护范围。[0129]图1为本发明建立的一个由云计算、雾计算和物联网组建的三层体系异构网络模型图，物联网设备通过异构网络将计算任务迁移到雾端或云端，具体地包括：[0130]第一方面，根据物联网特性，考虑了一个由云计算、雾计算和物联网组建的三层体系结构。物联网设备通过异构网络将计算任务迁移到雾或云端。在此结构下，建立了基于云雾协同计算的异构网络计算迁移问题模型。在异构网络中，终端设备不仅需要决定任务是否卸载，还需要选择合适的无线接入点以获得较高的数据传输速率。[0131]第二方面，用遗传算法来求解异构环境下的云雾协同资源分配问题，针对传统遗传算法无法解决复杂约束函数的问题，引入了罚函数来反映解对于约束条件的偏离程度，从而淘汰不可行解。[0132]第三方面，针对提高遗传算法收敛速度和遗传算法容易早熟的缺点，对遗传算法[0133]设系统中一共有N个终端设备，表示为终端设备集N={1,2,…,N}。系统中的每个终端设备n都含有一个计算任务W={D,Cn,t"},D表示该计算任务的大小(单位为KB),C表示完成终端设备n完成计算任务所需的计算资源，t"表示终端设备n完成计算任务所能接受的最大时延。[0134]本发明中，异构网络中的基站(BaseStations,BSs)包含一个宏基站MBS和M个小基将SBSs的计算任务传输中继到MBS,终端设备要么直接将计算任务卸载至MBS,或者将计算[0137]将卸载决策表示为S={-M-1,-M,...-1,0,1,...,M,M+1}时延t和能耗P°仅由终端设备自身计算[0142]其中，f°表示终端设备n的计算能力，C表示表示完成终端用户的所有计算任务所终端设备将计算任务迁移时产生的时延和能耗。当终端设备n将自身的计算任务卸载到雾站之间的信道增益，Pn,m表示终端设备n通过子信道k向第m个基站传输计算任务的功率，[0148]t=I(l≤a≤M)t,m+I(aₙ=M+1)t处再迁移至雾端产生的时延，表示终端设备n通过第m个SBSs将计算任务中继至MBS处再迁移至雾端产生的能耗，e,表示扫描可用基站时消耗的能量，P表示终端设备n在空闲状态下的维护功率。Pn,表示终端设备n的总传输功率，任务迁移至云端产生的时延，表示终端设备n直接通[0176]每个染色体包含OS(n),RA(n)和FA(n)三个部分，每个部分分别由N个等位基因组[0178]染色体OS(n)表示a,RA(n)表示p,FA(n)表示f;[0181]第三步，将交叉算子作用于群体g(t),基[0182]第四步，将变异算子作用于群体g(t),基于自适应变异概率Pm改变被选择的个体的部分基因值，得到新的个体；群体g(t)经过选择、交叉和变异运算之后得到下一代群体g(t+1)。计算其适应度值，并根据适应度值进行排序，准备进行下一次遗传操作。[0183]第五步，依据适应度标准差公式计算当前种群g(t+1)的个体适应度标准差σ,对当前迭代次数和标准差进行判定，决定是否进行高斯扰动和增大变异概率操作；[0184]第六步：若当前进化代数t达到了最大迭代次数T,输出最优解，否则转至第二步。[0185]图2为基本遗传算法流程示意图，遗传算法(GA)利用生物遗传学的观点，结合适者生存和随机信息交换的思想，通过选择、交叉和变异等机制，实现种群的进化。在寻优过程中，遗传算法在解空间内随机产生多个起始点并同时开始搜索，由适应度函数来指导搜索方向，通过对当前群体施加选择、交叉和变异等一系列遗传操作，从而产生出新一代的群体，能够在复杂搜索空间快速寻求全局优化解。[0186]如图3所示，一条染色体由多个等位基因组成，每个基因都对应一个变量。本发明中染色体分OS(n),RA(n)和FA(n)三个部分，每个部分分别由N个等位基因组成，分别对应N个终端设备。这三个部分分别用来表示式十一中的变量a,p以及f。[0187]第一部分表示终端设备的任务卸载策略，如当a值为0表示终端设备n选择在本地计算该任务，值为m,m∈M₁时表示终端设备为-m,m∈M₁表示终端设备n选择通过选择通过第m个SBSs将计算任务卸载到云端，值为M+1表示终端设备n选择通过MBS将计算任务卸载到雾端，值为-M-1表示终端设备n选择将计算任务卸载到云端。[0188]第二部分的等位基因值表示每个终端设备的上行链路传输功率；[0189]第三部分的等位基因值表示终端设备所分配到的用于完成计算任务的计算资源。[0190]与遗传学的优胜劣汰法则一样，遗传算法在每次迭代中都会选择部分染色体而淘汰另一部分染色体。而决定染色体被选择还是被淘汰的标准则是每个染色体的适应度值。染色体的适应度值根据适应度函数计算，本发明以式十一中的最小目标函数作为适应度函数，因为该优化问题是最小优化问题，所以对于本发明的染色体来说，其适应度值越小越[0191]为了产生新的解，扩大解空间，遗传算法每次迭代都要采取选择、交叉和变异操作。交叉指两条染色体之间交换部分基因从而形成两条新的染色体，变异是指染色体的部分基因发生改变。本发明引入现有技术中的罚函数，对不可行解进行惩罚，以满足式十一中的约束条件。以优化问题中的约束函数作为罚函数，对不可行解的适应度值放大，这样可保证该不可行解一定会在迭代过程中被淘汰。[0192]基于改进遗传算法，获得最小目标函数中最优的a,p以及f,包括：[0193]染色体OS(n)表示a,染色体RA(n)表示p,染色体FA(n)表示f;[0194]第一步初始化种群g(t),设置最大迭代次数T、种群大小s、自适应交叉概率Pc、自[0195]第二步适应度评估，基于适应度函数计算群体g(t)中每个个体的适应度函数值，根据每个个体的适应度函数值选择优良个体遗传到下一代群体；[0196]初始化后，当前种群中每条染色体的适应度值都根据适应度函数求出。其目的是选择更好的染色体来繁殖下一代作为父母。判断一个染色体的好坏取决于它自身的适应度值。因为公式十一是最小优化问题，所以对于染色体来说，其适合度值越低越好。为了满足公式十一的约束条件，采用现有技术中的罚函数为了满足约束C4,罚函数penaly(n,g)中应该包括{F-∑“f,这一项，其他约束条[0198]第四步，将变异算子作用于群体g(t),基于自适应变异概率Pm改变被选择的个体[0202],式十三[0205]引入现有技术中的罚函数penaly(n,g)来衡量约束并表示公式十一中的不等式约束，罚函数如下：例如，为了满足约束C4,罚函数penaly(n,g)中应该包括[0208],式十四[0214]根据下式在基因交叉位置点进行交叉操作：99[0217]式中，序列σ,n∈{1,2,...,N}表示染色体上的基因交叉位置点，遵循伯努利分[0218]OSå(n)表示当前父辈染色体a的染色体OS(n),RAå(n)表示当前父辈染色体a的染色体RA(n),)表示当前父辈染色体a的染色体FA(n);[0219]表示当前父辈染色体b的染色体OS(n),RA(n)表示当前父辈染色体b的染色体RA(n),FA'(n)表示当前父辈染色体b的染色体FA(n);[0220]()表示交叉后新生成的子代染色体a的染色体OS(n),)表示交叉后新生成的子代染色体a的染色体RA(n),)表示交叉后新生成的子代染色体a的染色体[0221])表示交叉后新生成的子代染色体b的染色体0S(n),)表示交叉后新生成的子代染色体b的染色体RA(n),)表示交叉后新生成的子代染色体b的染色体[0222]例如，当σ₃=1,如图4所示，父辈的交叉将会发生在0S(3),RA(3)和FA(3)之间。而若o₃=0,则父辈之间的交叉不会在上述基因位置发生。[0224]OS部分采用整数变异；[0225]RA和FA部分采用非均匀变异，随机扰动被选择的个体的基因值，获得具有新基因值的被选择的个体；[0227]随机生成一个2元变异掩模序列0。,n∈{1,2,...,N},确定被选择的个体的需要产生变异的基因点；如果突变掩码的元素为1,则该掩码对应位置上的基因会发生突变。而如果突变掩码的元素为0,则该基因不会发生突变。[0228]若OS(n)的基因点发生变异，则该基因点的基因值将会变成其相反数；[0229]若RA(n)或FA(n)的基因点发生变异，则该基因点的基因值在后代中按照变异公式十六被替换；[0230]变异公式为：,式十六[0232]x⁸(n)表示发生变异的基因点的基因值，△(t,y)表示[0,y]范围内符合非均匀分布的一个随机数，y代表Um×-x⁸(n)或x⁸(n)-Um,变异点x⁸(n)的取值范围为[Un,Um×,Um"表示变异点x⁸(n)取值范围的最大值，Un表示变异点x⁸(n)取值范围的