作者投稿和查稿 主编审稿 专家审稿 编委审稿 远程编辑

计算机工程 ›› 2020, Vol. 46 ›› Issue (2): 221-229. doi: 10.19678/j.issn.1000-3428.0053812

• 移动互联与通信技术 • 上一篇    下一篇

一种基于改进蚁群算法的三维K-栅栏覆盖算法

党小超1,2, 李月霞1, 郝占军1,2, 张彤1   

  1. 1. 西北师范大学 计算机科学与工程学院, 兰州 730070;
    2. 甘肃省物联网工程研究中心, 兰州 730070
  • 收稿日期:2019-01-25 修回日期:2019-03-27 发布日期:2020-02-12
  • 作者简介:党小超(1963-),男,教授,主研方向为物联网、传感器网络;李月霞,硕士;郝占军(通信作者),副教授;张彤,硕士。
  • 基金资助:
    国家自然科学基金(61662070,61762079);甘肃省科技重点研发项目(1604FKCA097,17YF1GA015);甘肃省科技创新项目(17CX2JA037,17CX2JA039)。

A 3D K-Barrier Coverage Algorithm Based on Improved Ant Colony Algorithm

DANG Xiaochao1,2, LI Yuexia1, HAO Zhanjun1,2, ZHANG Tong1   

  1. 1. College of Computer Science and Engineering, Northwest Normal University, Lanzhou 730070, China;
    2. Gansu Province Internet of Things Engineering Research Center, Lanzhou 730070, China
  • Received:2019-01-25 Revised:2019-03-27 Published:2020-02-12

摘要: 为解决三维环境下无线传感器网络的K-栅栏覆盖问题,提出一种改进的蚁群优化算法3D-ACO。将三维表面映射到二维平面进行网格划分,通过计算网格梯度并引入空间权重及部署方向角来改进蚁群算法寻找最短路径构建栅栏,采用移动节点填补栅栏间隙以确保构建强栅栏。实验结果表明,与strong optimal和strong greedy算法相比,该算法能够在有效提高节点利用率的同时降低节点能耗,并且在三维环境下所构建的栅栏覆盖具有较强的自适应性。

关键词: 无线传感器网络, 栅栏覆盖, 蚁群算法, 网格划分, 空间权重, 部署方向角

Abstract: To address the K-barrier coverage problem of Wireless Sensor Network (WSN) in 3D environment,this paper proposes the 3D-ACO,an improved ant colony optimization algorithm.The 3D surface is mapped to a 2D plane for meshing generation.The spatial weight and deployment direction angle are introduced by mesh gradient to improve the ant colony algorithm,thus finding the shortest path to construct the barrier.The mobile nodes are used to fill the gaps between the barriers,so as to ensure the constructed barriers are strong barriers.Experimental results show that compared with the strong optimal and strong greedy algorithms,the proposed algorithm can effectively improve the utilization of nodes while reducing the energy consumption of nodes.Besides,the barrier coverage constructed in 3D environment has strong adaptability.

Key words: Wireless Sensor Network(WSN), barrier coverage, ant colony algorithm, meshing generation, spatial weight, deployment direction angle

中图分类号: