Journal of Computer Applications ›› 2020, Vol. 40 ›› Issue (7): 2033-2037.DOI: 10.11772/j.issn.1001-9081.2019122211

• Network and communications • Previous Articles     Next Articles

Wireless sensor network deployment algorithm based on basic architecture

SHI Jiaqi, TAN Li, TANG Xiaojiang, LIAN Xiaofeng, WANG Haoyu   

  1. School of Computer and Information Engineering, Beijing Technology and Business University, Beijing 100048, China
  • Received:2020-01-02 Revised:2020-02-27 Online:2020-07-10 Published:2020-04-13
  • Supported by:
    This work is partially supported by the Beijing Municipal Natural Science Foundation-Haidian Original Innovation Joint Fund (L182007), the National Natural Science Foundation of China (61702020) and its supporting Project (PXM2018_014213_000033).

基于小结构体的无线传感器网络部署算法

史佳琦, 谭励, 唐小江, 连晓峰, 王浩宇   

  1. 北京工商大学 计算机与信息工程学院, 北京 100048
  • 通讯作者: 谭励
  • 作者简介:史佳琦(1996-),女,河北保定人,硕士研究生,主要研究方向:无线传感器网络;谭励(1980-),女,广西南宁人,教授,博士生导师,博士,主要研究方向:无线传感器网络、智能信息网络、机器学习;唐小江(1994-),男,甘肃庆阳人,博士研究生,主要研究方向:无线传感器网络;连晓峰(1977-),男,山西长治人,副教授,博士,主要研究方向:移动机器人、机器视觉、三维重构;王浩宇(1995-),男,山东烟台人,硕士研究生,主要研究方向:无线传感器网络。
  • 基金资助:
    北京市自然科学基金-海淀原始创新联合基金资助项目(L182007);国家自然科学基金(61702020)及其配套项目(PXM2018_014213_000033)。

Abstract: At present, the deployment of nodes in wireless sensor network mainly adopts the algorithm based on Voronoi diagram. In the process of deployment using Voronoi algorithm, due to the large number of nodes involved in the deployment and the high complexity of the algorithm, the iteration time of the algorithm is long. In order to solve the problem of long iteration time in node deployment, a Deployment Algorithm based on Basic Architecture (DABA) was proposed. Firstly the nodes were combined into basic architectures, then center position coordinates of the basic architecture were calculated, finally the node deployment was performed by using Voronoi diagram. The algorithm was still able to realize the deployment effectively under the condition that there were obstacles in the deployment area. The experimental results show that DABA can reduce the deployment time by two thirds compared with the Voronoi algorithm. The proposed algorithm can significantly reduce the iteration time and the complexity of the algorithm.

Key words: basic architecture, Voronoi diagram, coverage, travel distance, iteration time

摘要: 目前无线传感器网络中节点的部署主要采用基于Voronoi图的算法,在使用Voronoi算法进行部署的过程中由于参与部署的节点数量多,算法的复杂度高,导致算法的迭代时间较长。为解决节点部署中算法迭代时间较长的问题,提出一种基于小结构体的部署算法(DABA)。首先,将节点组合成小结构体;然后,计算小结构体的中心位置坐标;最后,利用Voronoi图进行节点部署。所提算法对于部署区域存在障碍的情况仍然能有效进行部署。实验结果表明,DABA在部署时间方面能够比基于Voronoi图的算法减少三分之二。所提算法可明显减少算法的迭代时间,同时降低算法的复杂性。

关键词: 小结构体, Voronoi图, 覆盖率, 移动距离, 迭代时间

CLC Number: