混合无线传感器网络覆盖优化算法

时间:2018-12-06 作者:博学论文网
  摘要:在无线传感器网络中, 带有移动节点的混合网络引起学者的兴趣。为了解决混合无线传感器网络中的网络有效覆盖问题和移动节点的优化部署问题, 提出一种新的混合无线传感器网络覆盖优化算法 (IVABC) .算法基本思想是对固定节点进行Voronoi多边形划分;利用划分结果分析固定节点的覆盖盲区;利用基于反向学习策略的蜂群算法优化部署移动节点;在网络覆盖率最优化的同时, 有效减少网络迭代次数。
  
  关键词:混合无线传感器网络; 网络覆盖优化; Voronoi多边形; 人工蜂群算法; 反向学习策略;
  
  0 引言
  
  混合无线网络可以有效利用移动节点的动态部署弥补固定节点所形成的信号覆盖盲区, 从而与仅有固定节点组成的传感器网络[1]相比能更好地解决网络资源浪费、易出现覆盖盲区等问题。文献[2]将遗传算法引入混合无线传感器网络中。文献[3]应用改进的蜂群算法对无线传感器网络进行部署优化, 将传感器感知节点部署问题转化为组合优化问题。但2种方法收敛效果不是很明显。文献[4]提出了将反向学习策略方法加入基本的人工蜂群 (artificial bee colony, ABC) 算法中, 其改进的ABC (improved ABC, IABC) 算法收敛效果非常好, 但网络覆盖效果不是很满意。文献[5]提出一种基于Voronoi多边形和ABC算法相结合的新型混合优化算法 (Voronoi-ABC, VABC) , 应用VABC来部署节点, 收敛速度很好, 目标区域覆盖率效果明显, 但跟随蜂产生新食物源的时, 依赖本代的最坏食物源的可能性比较大, 不利于获得最优的结果。
  
  本文利用Voronoi多边形来确定固定节点的覆盖盲区作为指引移动节点的移动参数。利用蜂群算法对移动节点进行分析, 确定最佳移动节点及移动位置。应用反向学习策略加快算法的收敛速度的同时避免算法陷入局部最优。确定移动节点的最终位置, 达到覆盖率最优。
  
  1 基于IVABC的覆盖优化策略
  
  针对传统的蜂群算法中的轮盘赌方式会使种群多样性被降低, 从而引发收敛速度慢、易陷入局部最优解的缺点[6], 本文提出了将Voronoi多边形和反向学习算法结合到人工蜂群算法里来解决覆盖优化问题。
  
  1.1 引领蜂的产生
  
  在ABC中, 食物源的产生是随机的, 同时引领蜂的搜索过程也是随机的。将Voronoi多边形引入ABC算法中, 应用Voronoi多边形顶点找出固定节点的覆盖盲区位置, 并且将覆盖盲区作为产生新蜜源的移动位置。与此同时, 指导引领蜂的搜索位置, 快速锁定蜜源在整个目标区域的大致位置, 并且计算食物源的适应度值。同时引领蜂更新食物源位置。
  
  1.2 跟随蜂选择策略
  
  通过Voronoi多边形加入蜂群算法中, 跟随蜂通过距离评价覆盖盲区的大小来选取引领蜂进行跟随。评价覆盖盲区大小策略如下:
  
  1) 如果顶点VA, VB完全被节点s的覆盖圆所覆盖, 则不存在覆盖盲区;
  
  2) 如果顶点VA, VB中的两个点有一个落在节点s的覆盖圆内, 另一个落在覆盖圆外, 假设顶点VA落在覆盖圆内, 而顶点VB落在覆盖圆外, 必然出现覆盖盲区。利用Voronoi多边形将顶点VB做出标记, 此时顶点VB为覆盖盲区, 顶点VA不进行标记。
  
  1.3 最差蜜源替换
  
  在算法迭代的过程中, 引领蜂和跟随蜂产生新食物源时, 由于过分依靠本代的最坏食物源, 不利于全局寻优, 同时影响算法的收敛速度, 所以把最坏蜜源用反向学习策略新生成的蜜源取代, 即新构造一个蜜源取代最差食物源, 这种方法的过程为引领蜂每次循环完成后, 需要记录最差食物源的位置为xi, 并用xi1表示新生成的食物源位置, xi的第j个分量用xij表示, 所以新的食物源的第j个分量x1ij为
  
  式中xij U为xi的第j个分量的上界, xij L为x的第j个分量的下界。本文更新最差食物源都采用式 (1) 得到新食物源, 如果新食物源效果更好, 则代替旧食物源。
  
  1.4 IVABC的算法过程
  
  1) 目标区域内随机部署无线传感器网络的固定节点, 对固定节点进行Voronoi划分;根据无线传感器固定节点的覆盖圆到Voronoi顶点之间的相对位置找到覆盖盲区, 并计算初始覆盖率。
  
  2) 对蜜蜂种群规模、最大迭代次数等进行初始化处理。
  
  3) 将步骤 (1) 中覆盖盲区作为无线传感器移动节点的移动位置, 分配对应引领蜂进行搜索目标区域, 引领蜂搜索出解集vij, 在解集vij中找出最差解xi, 对每个分量j, 按照式 (1) 进行更新, 从而得到新解xi1, 同时计算适应度值。假如xi1的适应度值高于xi, 则用xi1代替xi;否则, 保留xi.如果结束一次迭代, 则记录迭代过程得到的最好解;并计算当前网络覆盖率。
  
  4) 计算网络覆盖率, 同时应用贪婪算法寻找相对较好的解来更新当前移动节点位置。
  
  5) 有限次循环步骤 (3) 后, 假如有移动节点位置不能提高网络覆盖率, 则由对应的引领蜂转变为侦查蜂进行搜索, 应用反向学习策略产生新移动节点位置取代原来的节点位置。
  
  6) 对最大循环次数进行判断, 假如达到最大执行次数, 循环停止;否则, 根据网络覆盖率重新对蜂群进行搜索。
  
  7) 检验循环结束的条件是否得到满足:若是, 就输出记录最优的移动节点位置作为寻优结果, 最终生成的无线传感器网络覆盖图。
  
  2 实验与结果分析
  
  使用MATLAB 2014软件进行仿真, 仿真目标区域为100 m×100 m, 混合无线传感器总节点数为50个, 其中固定节点30个, 移动节点20个, 通信距离20 m, 感知半径10 m.在ABC和IVABC中, 参数分别为:种群规模50, 引领蜂数20, 蜜源数20, 最大迭代次数1 000次。实验中传感器部署选定监测区域为二维网络空间, 所有传感器节点处于同一平面内, 同构, 具有相同的传感半径R.传感器节点感知模型为概率感知模型, 每个传感器节点覆盖圆范围为πR2.
  
  应用本文提出的IVABC算法的实验仿真结果中节点随机部署情况如图1、图2所示, 图2中深色区域表示移动节点覆盖区域, 浅色区域表示固定节点覆盖区域。由结果可知, 初始网络覆盖率为67.81%.图2算法优化后的, 最终目标区域覆盖率为97.13%, 从而使覆盖率达到最大化。
  
  图1 节点初始随机部署

  
  图2 优化完成后节点最终部署

  
  表1为10次仿真实验的覆盖率数据统计表。从表1中可以看出应用本文提出的IVABC算法后, 混合无线网覆盖率每次均有很大的提升。图3为4种算法的平均覆盖率的寻优曲线。
  
  表1 10次覆盖率仿真实验结果

  
 
  图3 4种算法平均覆盖率对比

  
  可见本文提出的IVABC算法收敛速度快, 且收敛效果好。由表1中仿真10次的网络平均覆盖率数据比较, 看出IVABC算法覆盖效果更好, 平均最大覆盖率最后达到96.39%.IVABC在迭代95次后, 达到最大覆盖率的95%, 由此可见, 收敛速度加快的同时, 覆盖效果明显。
  
  3 结束语
  
  针对混合无线网覆盖优化问题和无线传感器节点的部署问题, 本文提出一种IVABC算法, 并通过与ABC, IABC, VABC算法在混合无线网络中的最终覆盖率、平均覆盖率和迭代次数等方面的对比, 说明了IVABC算法能较好避免基本ABC易陷入局部最优解的同时减少了迭代次数。
  
  参考文献
  
  [1]李济泽, 李科杰。混合无线传感器网络移动节点部署优化[J].集美大学学报:自然科学版, 2010, 15 (5) :394-400.  
  [2]祁育仙, 李国勇。混合WSNs中基于多目标优化的覆盖控制算法[J].传感器与微系统, 2016, 35 (2) :136-139.  
  [3]袁浩。基于改进蜂群算法无线传感器感知节点部署优化[J].重庆邮电大学, 2010, 27 (7) :2-3.  
  [4]宋苏鸣。基于改进人工蜂群算法的无线传感器网络覆盖优化策略[J].西安电子科技大学, 2014 (3) :9-20.  
  [5]穆天圆, 乔学工, 张敏。基于Voronoi图的蜂群优化算法在WSNs覆盖中的应用[J].传感技术学报, 2015, 28 (10) :1-5.
  [6]穆天圆。混合无线传感器网络覆盖优化算法的研究[D].太原:太原理工大学, 2016:12-24.
猜你喜欢
博学论文网(www.hndance.cn)版权所有
专业的代写英语论文,代写英文论文、assignment、各专业毕业论文网站,本站部分论文收集于网络,如有不慎侵犯您的权益,请联系客服,24小时内处理