计算机应用 ›› 2016, Vol. 36 ›› Issue (12): 3244-3250.DOI: 10.11772/j.issn.1001-9081.2016.12.3244

• 网络与通信 • 上一篇    下一篇

差分进化融合混合虚拟力的有向传感器网络覆盖算法

关志艳1, 冯秀芳2   

  1. 1. 山西大学商务学院 信息学院, 太原 030031;
    2. 太原理工大学 计算机科学与技术学院, 太原 030024
  • 收稿日期:2016-06-16 修回日期:2016-09-08 出版日期:2016-12-10 发布日期:2016-12-08
  • 通讯作者: 关志艳
  • 作者简介:关志艳(1983-),女,山西临汾人,讲师,硕士,主要研究方向:无线传感器网络、节点覆盖、数据融合;冯秀芳(1966-),女,山西太原人,教授,博士,主要研究方向:无线传感器网络、机器学习、数据挖掘。
  • 基金资助:
    国家自然科学基金资助项目(61472272)。

Coverage algorithm based on differential evolution and mixed virtual force for directional sensor networks

GUAN Zhiyan1, FENG Xiufang2   

  1. 1. Information Institute, Business College of Shanxi University, Taiyuan Shanxi 030031, China;
    2. College of Computer Science and Technology, Taiyuan University of Technology, Taiyuan Shanxi 030024, China
  • Received:2016-06-16 Revised:2016-09-08 Online:2016-12-10 Published:2016-12-08
  • Supported by:
    This work is partially supported by the National Natural Science Foundation of China (61472272).

摘要: 针对感知方向可调的有向传感器网络(DSN),为最大限度减少覆盖空洞和重叠区,从而提高有效覆盖率,提出了差分进化融合混合虚拟力的DSN覆盖算法。首先,建立有向感知模型,分析节点之间、节点与障碍物之间及节点与边界之间的混合虚拟作用力,在此基础上建立节点旋转角度与作用力之间的调整公式;然后,为弱化混合虚拟力造成的局部次优解缺陷,引入差分进化模型,将虚拟力作为进化更新的一个影响因子,节点间经过变异、交叉及选择操作来寻找最佳适度值,提高有效覆盖率。覆盖仿真实验表明,在100 m×100 m监测区域下,求得100次随机部署后经过差分进化融合混合虚拟力算法网络有效覆盖率提高了19.68%,而经过混合虚拟力算法和差分进化算法的覆盖率分别提高了10.32%和11.35%;差分进化融合混合虚拟力算法在迭代80次左右网络趋于稳定,而混合虚拟力算法和差分进化算法分别需要130次和140次左右迭代。相对于混合虚拟力算法和差分进化算法,将两者相结合的差分进化融合混合虚拟力算法的收敛速度更快,有效覆盖率提高更明显。

关键词: 有向传感器网络, 混合虚拟力, 差分进化, 覆盖率, 收敛速度

Abstract: For Directional Sensor Network (DSN) consists of sensors with adjustable directions, in order to reduce coverage holes and overlapping area to the utmost, so as to improve the effective coverage, a differential evolution-mixed virtual force based coverage algorithm was put forward. Firstly, the directional sensing model was established, the mixed virtual forces between nodes, nodes and obstacles, nodes and the boundary were analyzed, and the adjustment formula between node rotation angle and force was established. Secondly, the differential evolution model was used to weaken defects of local suboptimal solutions caused by mixed virtual force. The virtual force was taken as a factor of evolutionary update. The best fitness value was found between nodes to optimize the effective coverage through mutation, crossover and selection operations. The coverage simulation experiments show that, in the detection area of 100 m×100 m, after 100 times of random deployment, the average effective coverage rate of the network is increased by 19.68% by the differential evolution-mixed virtual force algorithm, and the average effective coverage rate of the network is respectively increased by 10.32% and 11.35% by mixed virtual force algorithm and differential evolution algorithm. The network of differential evolution-mixed virtual force algorithm tends to be stable after 80 iterations, while the network of mixed virtual force algorithm and differential evolution algorithm respectively requires 130 iterations and 140 iterations. Compared with mixed virtual force algorithm and differential evolution algorithm, the differential evolution-mixed virtual force based coverage algorithm is faster, and can improve the effective coverage rate more obviously.

Key words: Directional Sensor Network (DSN), mixed virtual force, differential evolution, coverage rate, convergence speed

中图分类号: