高级搜索

一种改进的虚拟力重定位覆盖增强算法

周非 郭浩田 杨伊

引用本文: 周非, 郭浩田, 杨伊. 一种改进的虚拟力重定位覆盖增强算法[J]. 电子与信息学报, doi: 10.11999/JEIT190662 shu
Citation:  Fei ZHOU, Haotian GUO, Yi YANG. An Improved Virtual Force Relocation Coverage Enhancement Algorithm[J]. Journal of Electronics and Information Technology, doi: 10.11999/JEIT190662 shu

一种改进的虚拟力重定位覆盖增强算法

    作者简介: 周非: 男,1977年生,博士,教授,研究方向为无线定位、信号处理、图像处理等;
    郭浩田: 男,1994年生,硕士,研究方向为无线传感网络;
    杨伊: 女,1992年生,硕士,研究方向为无线传感网络
    通讯作者: 郭浩田,17784456880@163.com
  • 基金项目: 国家自然科学基金(61471077)

摘要: 在移动无线传感网络(MWSN)的部署问题中最关键的是如何提供最大的区域覆盖范围。针对现有的覆盖控制算法存在覆盖率不理想、部署效率低、能耗过高的问题,该文提出了一种高效部署策略。第1阶段利用voronoi图获得整个网络的覆盖孔,检测voronoi多边形内的未覆盖区域,并提供虚拟力驱动传感器移动,同时采用动态调整策略改变移动步长,从而减少能量损耗;第2阶段提出一种检测机制,利用delaunay三角网检测传感器之间的局部覆盖孔并进行修复。仿真结果表明,该算法在提高网络覆盖率的同时加快了收敛速度,为部署移动无线传感网络提供了新的解决思路。

English

    1. [1]

      YUE Yinggao and HE Ping. A comprehensive survey on the reliability of mobile wireless sensor networks: Taxonomy, challenges, and future directions[J]. Information Fusion, 2018, 44: 188–204. doi: 10.1016/j.inffus.2018.03.005

    2. [2]

      ETANCELIN J M, FABBRI A, GUINAND F, et al. DACYCLEM: A decentralized algorithm for maximizing coverage and lifetime in a mobile wireless sensor network[J]. Ad Hoc Networks, 2019, 87: 174–187. doi: 10.1016/j.adhoc.2018.12.008

    3. [3]

      HACIOGLU G, KAND V F A, and SESLI E. Multi objective clustering for wireless sensor networks[J]. Expert Systems with Applications, 2016, 59: 86–100. doi: 10.1016/j.eswa.2016.04.016

    4. [4]

      ALIA O M and Al-AJOURI A. Maximizing wireless sensor network coverage with minimum cost using harmony search algorithm[J]. IEEE Sensors Journal, 2017, 17(3): 882–896. doi: 10.1109/jsen.2016.2633409

    5. [5]

      ABO-ZAHHAD M, SABOR N, SASAKI S, et al. A centralized immune-Voronoi deployment algorithm for coverage maximization and energy conservation in mobile wireless sensor networks[J]. Information Fusion, 2016, 30: 36–51. doi: 10.1016/j.inffus.2015.11.005

    6. [6]

      XU Ying, DING Ou, QU Rong, et al. Hybrid multi-objective evolutionary algorithms based on decomposition for wireless sensor network coverage optimization[J]. Applied Soft Computing, 2018, 68: 268–282. doi: 10.1016/j.asoc.2018.03.053

    7. [7]

      ROUT M and ROY R. Dynamic deployment of randomly deployed mobile sensor nodes in the presence of obstacles[J]. Ad Hoc Networks, 2016, 46: 12–22. doi: 10.1016/j.adhoc.2016.03.004

    8. [8]

      MAHBOUBI H and AGHDAM A G. Distributed deployment algorithms for coverage improvement in a network of wireless mobile sensors: Relocation by virtual force[J]. IEEE Transactions on Control of Network Systems, 2017, 4(4): 736–748. doi: 10.1109/TCNS.2016.2547579

    9. [9]

      HABIBI J, MAHBOUBI H, and AGHDAM A G. A gradient-based coverage optimization strategy for mobile sensor networks[J]. IEEE Transactions on Control of Network Systems, 2017, 4(3): 477–488. doi: 10.1109/TCNS.2016.2515370

    10. [10]

      LEE H J, KIM Y H, HAN Y H, et al. Centroid-Based movement assisted sensor deployment schemes in wireless sensor networks[C]. The 70th Vehicular Technology Conference Fall, Anchorage, USA, 2009. doi: 10.1109/VETECF.2009.5379087.

    11. [11]

      FANG Wei, SONG Xinhong, WU Xiaojun, et al. Novel efficient deployment schemes for sensor coverage in mobile wireless sensor networks[J]. Information Fusion, 2018, 41: 25–36. doi: 10.1016/j.inffus.2017.08.001

    12. [12]

      BARTOLINI N, BONGIOVANNI G, PORTA T L, et al. Voronoi-based deployment of mobile sensors in the face of adversaries[C]. 2014 IEEE International Conference on Communications, Sydney, Australia, 2014: 532–537. doi: 10.1109/ICC.2014.6883373.

    13. [13]

      QIU Chenxi and SHEN Haiying. A delaunay-based coordinate-free mechanism for full coverage in wireless sensor networks[J]. IEEE Transactions on Parallel and Distributed Systems, 2014, 25(4): 828–839. doi: 10.1109/TPDS.2013.134

    14. [14]

      LI Wei and ZHANG Wei. Coverage hole and boundary nodes detection in wireless sensor networks[J]. Journal of Network and Computer Applications, 2015, 48: 35–43. doi: 10.1016/j.jnca.2014.10.011

    15. [15]

      JOSHITHA K L and JAYASHRI S. A novel redundant hole identification and healing algorithm for a homogeneous distributed Wireless Sensor Network[J]. Wireless Personal Communications, 2019, 104(4): 1261–1282. doi: 10.1007/s11277-018-6079-5

    16. [16]

      SO-IN C, NGUYEN T G, and NGUYEN N G. An efficient coverage hole-healing algorithm for area-coverage improvements in mobile sensor networks[J]. Peer-to-Peer Networking and Applications, 2019, 12(3): 541–552. doi: 10.1007/s12083-018-0675-8

  • 图 1  局部覆盖孔

    图 2  基于形心传感器移动示意图

    图 3  基于虚拟力传感器移动示意图

    图 4  基于检测机制漏洞修复示意图

    图 5  传感器运动过程图

    图 6  覆盖率变化图

    图 7  单次蒙特卡洛仿真覆盖率变化曲线

    图 8  不同节点个数,4种算法性能对比图

    表 1  基于voronoi图的虚拟力重定位算法

     Randomly deploy N sensors in the monitoring area;
     Repeat
     Construct voronoi polygons based on the position of the
     sensors;
      For each $i{\rm{ (} }1 \le i \le N)$
       For each $j{\rm{ } }(1 \le j \le {\rm{vertex(} }i\rm{)})$// vertex: the number of
       voronoi polygon vertices;
        If ${{\rm dist(} }i,j{) < }{R_s}$ //case 1: voronoi polygon vertices are
        all covered;
         Calculate the force of the centroid on the sensor and
         the position of the sensor;
        Else //case 2: voronoi polygon vertices are not all
        covered;
         Calculate ${F_{\rm{uncov}}}$ and the position of the sensor at the
         next moment;// ${F_{\rm{uncov}}}$:the force of the uncovered grid
         point on the sensor;
         End for
        End for
       Sensor location update;
      End for
     Until termination criterion is met
    下载: 导出CSV

    表 2  基于delaunay三角的局部覆盖空洞修复算法

     Construct a delaunay triangulation based on the position of the
     sensors;
     For each $j{\rm{ } }(1 \le j \le {\rm{TRI} }\left( i \right))$// TRI: the number of delaunay
     triangles
       Calculate empty circle center coordinates and radius;
       If there is a gap between the sensors:
        Calculate the force of the centroid of the empty circle on
        the sensor and the position of the sensor circle on the
        sensor;
        If ${\rm{fitness} }(x(t)) \ge {\rm{fitness} }(x(t - {\rm{1} }))$
         Sensor location update;
         Break;
       Else
         Sensor position unchanged;
       End if
      End if
     End for
    下载: 导出CSV
  • 加载中
图(8)表(2)
计量
  • PDF下载量:  8
  • 文章访问数:  900
  • HTML全文浏览量:  103
文章相关
  • 通讯作者:  郭浩田, 17784456880@163.com
  • 收稿日期:  2019-08-30
  • 录用日期:  2020-02-27
  • 网络出版日期:  2020-04-15
通讯作者: 陈斌, bchen63@163.com
  • 1. 

    沈阳化工大学材料科学与工程学院 沈阳 110142

  1. 本站搜索
  2. 百度学术搜索
  3. 万方数据库搜索
  4. CNKI搜索

/

返回文章