一种基于改进布谷鸟搜索算法的微云部署方法.pdf

(19)中华人民共和国国家知识产权局(12)发明专利申请(10)申请公布号CN111885493A(43)申请公布日2020.11.03(21)申请号202010773132.3(22)申请日2020.08.04(71)申请人西安邮电大学地址710000陕西省西安市长安区西长安街618号(72)发明人金小敏高枫王忠民陈彦萍(74)专利代理机构西安鼎迈知识产权代理事务所(普通合伙)61263代理人李振瑞(51)Int.Cl.H04W4/02(2018.01)H04W4/70(2018.01)H04W16/18(2009.01)H04W72/04(2009.01)权利要求书4页说明书9页附图3页(54)发明名称一种基于改进布谷鸟搜索算法的微云部署方法(57)摘要本发明提出了一种基于改进布谷鸟搜索算法的微云部署方法。本发明将离散布谷鸟搜索算法和离散差分进化算法结合在一起，第一阶段通过离散化莱维飞行机制，更新布谷鸟种群的位置，将每一代种群中适应度最大的个体直接保留到下一代，避免它被交叉和变异操作破坏；第二阶段对布谷鸟算法的丢巢操作通过离散差分进化算法进行改进，对第一阶段的少部分劣质基因个体通过变异算子与优秀的父基因进行进化，在保留种群的优秀基因和增加种群的多样性的同时，加快算法的收敛速度。本发明算法求解速度快，能在大规模的物联网网络中使用较短时间求解出微云的永久部署位置，大幅度提高微云在网络中的使用效率和生存寿命。CN111885493ACN111885493A权利要求书1/4页1.一种基于改进布谷鸟搜索算法的微云部署方法，其特征在于，包括，建立物联网网络拓扑图；建立任务在物联网网络中的卸载模型和微云内计算资源的分配方案，确定全局优化目标函数，并设计全局优化目标的约束条件，构建部署微云的P-中值模型；采用二进制编码描述部署微云位置的解；采用二进制差分进化算法改进布谷鸟搜索算法的丢巢操作，通过改进的布谷鸟搜索算法求解微云部署位置的最优解。2.根据权利要求1所述的基于改进布谷鸟搜索算法的微云部署方法，其特征在于，所述物联网网络拓扑图的表达式为：其中，G表示物联网网络，包含多个无线接入点和一组潜在的微云位置；V表示无线接入点位置集合；S表示部署微云的潜在位置集合；E表示两个无线接入点之间，或无线接入点与微云之间的链路集合；v表示无线接入点；c表示微云；vid表示无线接入点的id；vLocation表示无线接入点的位置；DeployCost表示在该无线接入点的位置部署微云需要耗费的成本；cid表示微云的id；cLocation表示微云部署的位置；Capacity表示微云内的计算资源。3.根据权利要求1所述的基于改进布谷鸟搜索算法的微云部署方法，其特征在于，所述构建部署微云P-中值模型的方法为：将微云的部署成本定义为仅与地理位置相关的固定成本，表示为其中，fj表示一个微云部署在无线接入点vj的固定成本；移动设备的任务分发至物联网网络中的微云上，一个微云cj上的总任务量表示为其中，δi,j表示无线接入点vi收集到的任务是否被交付给微云cj，Ri表示移动设备到达附近无线接入点vi的任务到达率；经过微云cj进行处理的总的时延表示为其中，DFDT表示无线接入点对每个任务的平均转发时延，qi,j表示任务在无线接入点vi和无线接入点vj之间路由经过的无线接入点数量，μ为单位时间内微云处理任务的速率；所述全局优化目标函数的表达式为：其中，γ1表示成本系数，2CN111885493A权利要求书2/4页maxmax其中，d+DFDTq表示物联网网络中的无线接入点到达距离最远的微云产生的最大的传输时延和转发时延的总和；表示微云上对所有任务进行处理产生的最大处理时延；η∈(0,1)表示折中系数；所述全局优化目标的约束条件为：确保K个微云中的任何一个只能位于集合S中的一个位置；确保集合V中的每一个无线接入点位置最多只部署一个微云；P表示物联网网络中可以部署的微云的最大数量；确保在物联网网络中每个无线接入点上收到的任务会被全部分配到微云上；确保每个无线接入点上所有的任务在物联网网络中产生的总时延不能超过阈值DRD；xi,j∈{0,1}，xi,j表示一个二元变量，若xi,j＝1，则表示一个微云cj部署在无线接入点vi上，否则不部署。4.根据权利要求1所述的基于改进布谷鸟搜索算法的微云部署方法，其特征在于，所述采用二进制编码描述部署微云位置的解的方法：在初始编码时，给定编码长度，在给定的编码长度内随机生成0或1，1表示在无线接入点位置部署微云，0表示在无线接入点位置不部署微云。5.根据权利要求1所述的基于改进布谷鸟搜索算法的微云部署方法，其特征在于，所述改进的布谷鸟搜索算法的方法为：1)初始化改进布谷鸟算法参数；2)通过Floyd算法计算物联网网络中每个无线接入点到达其他接