计算机应用 ›› 2015, Vol. 35 ›› Issue (3): 620-623.DOI: 10.11772/j.issn.1001-9081.2015.03.620

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

基于Voronoi图的无线传感器网络覆盖空洞检测算法

戴国勇1,2, 陈麓屹1, 周斌彬1, 徐萍1   

  1. 1. 浙江树人大学 信息科技学院, 杭州 310014;
    2. 浙江工业大学 计算机科学与技术学院, 杭州 310023
  • 收稿日期:2014-10-20 修回日期:2014-11-24 出版日期:2015-03-10 发布日期:2015-03-13
  • 通讯作者: 戴国勇
  • 作者简介:戴国勇(1983-),男,浙江杭州人,讲师,博士研究生,主要研究方向:无线传感器网络、信息安全;陈麓屹(1982-),女,浙江江山人,助教,硕士,主要研究方向:物联网、数据挖掘;周斌彬(1987-),女,浙江温州人,讲师,硕士,主要研究方向:无线传感器网络;徐萍(1977-),女,浙江台州人,讲师,博士,主要研究方向:人工智能、物联网
  • 基金资助:

    浙江省教育厅科研项目(Y201432448);国家自然科学基金面上项目(61379023)

Coverage hole detection agorithm based on Voronoi diagram in wireless sensor network

DAI Guoyong1,2, CHEN Luyi1, ZHOU Binbin1, XU Ping1   

  1. 1. College of Information Science and Technology, Zhejiang Shuren University, Hangzhou Zhejiang 310014, China;
    2. College of Computer Science and Technology, Zhejiang University of Technology, Hangzhou Zhejiang 310023, China
  • Received:2014-10-20 Revised:2014-11-24 Online:2015-03-10 Published:2015-03-13

摘要:

针对无线传感器网络(WSN)中节点随机部署或部分节点能量耗尽带来的覆盖空洞(CH)问题,提出了一种基于Voronoi图的覆盖空洞检测算法。该算法利用节点的位置信息在覆盖区域范围内构建Voronoi图,通过计算每个Voronoi区域内的节点到该区域的顶点和边的距离来判断是否存在覆盖空洞,标识覆盖空洞的边界节点。仿真实验评估了不同节点分布密度、不同感知半径对空洞平均检测时间、平均能耗的影响,并与路径密度(PD)算法进行比较。实验结果表明所提算法在空洞平均检测时间和节点平均能耗两个方面均有10%左右的提升,对进一步延长网络生存期具有重要价值。

关键词: 无线传感器网络, 覆盖空洞, Voronoi图, 能耗, 半分布式算法

Abstract:

To address the Coverage Hole (CH) problem in Wireless Sensor Network (WSN) caused by nodes' random deployment or running out of energy, a novel coverage hole detecting algorithm was proposed for wireless sensor networks in this paper. The location information of sensor nodes was used to build the Voronoi diagram for the monitored area. Then the distances between a sensor node and the vertex or edges of the corresponding Voronoi cell were calculated to decide the existence of coverage holes and identify the border nodes. Simulations were conducted to evaluate the performance of the proposed algorithm within different sensing ranges and nodes density. The performance comparison with the Path Density (PD) algorithm shows that the proposed algorithm has about 10% promotion both in average detection time and average energy consumption, which is important for prolonging the network lifetime.

Key words: Wireless Sensor Network (WSN), Coverage Hole (CH), Voronoi diagram, energy consumption, semi-distributed algorithm

中图分类号: