Polynomial time algorithm for solving k-coverage problem in wireless sensor networks

Qi WANG; Zheng’an XIAO; Huaixing WANG

doi:10.11959/j.issn.1000-0801.2017287

您当前的位置：

首页 >

文章列表页 >

Polynomial time algorithm for solving k-coverage problem in wireless sensor networks

research and development | 更新时间：2024-06-05

- Polynomial time algorithm for solving k-coverage problem in wireless sensor networks
- Telecommunications Science Vol. 33, Issue 12, Pages: 91-98(2017)
- 作者机构：
- 作者简介：
- 基金信息：
- DOI：10.11959/j.issn.1000-0801.2017287
  CLC： TN918.91
- Published Online：2017-12，
  
  Published：20 December 2017
- 稿件说明：
移动端阅览
Qi WANG, Zheng’an XIAO, Huaixing WANG. Polynomial time algorithm for solving k-coverage problem in wireless sensor networks[J]. Telecommunications science, 2017, 33(12): 91-98.
DOI：

Qi WANG, Zheng’an XIAO, Huaixing WANG. Polynomial time algorithm for solving k-coverage problem in wireless sensor networks[J]. Telecommunications science, 2017, 33(12): 91-98. DOI： 10.11959/j.issn.1000-0801.2017287.

摘要

针对无线传感器网络的最差覆盖和最佳覆盖，探寻如何解决二维目标区域内的“k-覆盖问题”，提出了一种解决此问题的多项式时间算法。该算法基于扩展圆盘的几何图形提出了一系列的定义和定理，将“k-覆盖问题”转化成了寻找相邻分界线的问题。仿真结果表明，算法可在多项式时间内计算出最优k-违反路径和最优k-支持路径，从而合理规避或选取网络覆盖点。

Abstract

How to solve the k-coverage problem

which was divided into worst-case and best-case

inside the two-dimensional target area in wireless sensor networks was explored

and a polynomial time algorithm for solving this problem was put forward.In this algorithm

a series of definitions and theorems were proposed based on the geometric graph of growing disks

and the k-coverage problem was transformed into one of finding a series of adjacent borders.The simulation results show that the algorithm could compute the optimal k-breach path and k-support path in polynomial time

so as to avoid or select the network coverage reasonably.

关键词

Keywords

references

MEGERIAN S , KOUSHANFAR F , POTKONJAK M , et al . Worst and best-case coverage in sensor networks [J ] . IEEE Transaction on Mobile Computing , 2005 , 4 ( 1 ): 84 - 92 .

杨海雳 , 赵静 . 基于 Voronoi 图的无线传感器网络覆盖算法研究 [J ] . 信息通信 , 2015 ( 7 ): 28 - 31 .

YANG H L , ZHAO J . Research of coverage algorithm with Voronoi diagram for wireless sensor network [J ] . Information ＆Communications , 2015 ( 7 ): 28 - 31 .

王成 , 樊建席 , 王仁喜 , 等 . 基于Voronoi图的无线传感器网络K覆盖算法 [J ] . 计算机工程 , 2012 , 38 ( 4 ): 84 - 87 .

WANG C , FAN J X , WANG R X , et al . K coverage algorithm in wireless sensor network based on Voronoi diagram [J ] . Computer Engineering , 2012 , 38 ( 4 ): 84 - 87 .

丁旭 , 吴晓蓓 , 黄成 . 基于改进粒子群算法和特征点集的无线传感器网络覆盖问题研究 [J ] . 电子学报 , 2016 , 44 ( 4 ): 967 - 973 .

DING X , WU X P , HUANG C . Area coverage problem based on improved PSO algorithm and feature point set in wireless sensor networks [J ] . Acta Electronica Sinica , 2016 , 44 ( 4 ): 967 - 973 .

孙泽宇 , 伍卫国 , 王换招 , 等 . 无线传感器网络基于参数可调增强型覆盖控制算法 [J ] . 电子学报 , 2015 , 43 ( 3 ): 466 - 474 .

SUN Z Y , WU W G , WANG H Z , et al . An enhanced coverage control algorithm for wireless sensor networks based on adjustable parameters [J ] . Acta Electronica Sinica , 2015 , 43 ( 3 ): 466 - 474 .

刘志强 , 沈廼桐 , 毛强 , 等 . 无线传感器网络动态覆盖的CVT算法 [J ] . 传感器与微系统 , 2015 ( 6 ): 115 - 118 .

LIU Z Q , SHEN N T , MAO Q , et al . A dynamic coverage algorithm for wireless sensor networks based on CVT [J ] . Transducer and Microsystem Technologies , 2015 ( 6 ): 115 - 118 .

高洁 , 吴延红 , 白建侠 , 等 . 无线传感器网络最小覆盖能量优化算法 [J ] . 传感技术学报 , 2016 , 29 ( 9 ): 1435 - 1440 .

GAO J , WU Y H , BAI J X , et al . The minimum coverage energy optimization algorithms in wireless sensor network [J ] . Chinese Journal of Sensors And Actuators , 2016 , 29 ( 9 ): 1435 - 1440 .

LIU X Y , WU K L , ZHU Y , et al . Mobility increases the surface coverage of distributed sensor networks [J ] . Computer Networks the International Journal of Computer ＆ Telecommunications Networking , 2013 , 57 ( 11 ): 2348 - 2363 .

TAN L , CHENG Y C , YANG M H , et al . Priority coverage algorithm and performance simulation for node deployment in directional sensor networks [J ] . Sensor Letters , 2014 , 12 ( 2 ): 275 - 280 .

鲁晓波 , 阮福 , 王立中 . 无线传感器网络覆盖优化策略 [J ] . 内蒙古师大学报(自然汉文版) , 2016 , 45 ( 4 ): 480 - 483 .

LU X B , RUAN F , WANG L Z . Coverage optimization strategy of wireless sensor networks based on improved artificial fish swarm algorithm [J ] . Journal of Inner Mongolia Normal University (Natural Science Edition) , 2016 , 45 ( 4 ): 480 - 483 .

王兴伟 , 蔡凌 , 黄敏 , 等 . 基于空间镶嵌的三维无线传感器网络 K 覆盖机制 [J ] . 小型微型计算机系统 , 2014 , 35 ( 3 ): 433 - 436 .

WANG X W , CAI L , HUANG M , et al . Spatial tessellation based K coverage scheme for 3D wireless sensor network [J ] . Journal of Chinese Computer Systems , 2014 , 35 ( 3 ): 433 - 436 .

MINI S , UDGATA S K , SABAT S L . Sensor deployment and scheduling for target coverage problem in wireless sensor networks [J ] . IEEE Sensors Journal , 2014 , 14 ( 3 ): 636 - 644 .

MAHBOUBI H , MOEZZI K , AGHDAM A G , et al . Distributed deployment algorithms for improved coverage in a network of wireless mobile sensors [J ] . IEEE Transactions on Industrial Informatics , 2013 , 10 ( 1 ): 163 - 174 .

ZHANG Y , SUN X , WANG B . Efficient algorithm for K-barrier coverage based on integer linear programming [J ] . China Communications , 2016 , 13 ( 7 ): 16 - 23 .

BAN D S , WEN J , JIANG J , et al . Constructing K-barrier coverage in mobile wireless sensor networks [J ] . Journal of Software , 2011 , 22 ( 9 ): 2089 - 2103 .

Views

600

下载量

CSCD

Alert me when the article has been cited

提交

Tools

Publicity Resources

Quality of service based hierarchical resource allocation algorithm

Wireless sensor node localization based on IPSO-MC

Communication performance analysis of wireless sensor network for railway environmental monitoring

Energy-efficient data gathering scheme based on Kalman prediction and compressed sensing

Game theory-based malware propagation model for wireless sensor network

Related Author

Yi WANG

Xiaodong CAO

Jinrong CHEN

Cheng DING

Jianping WU

Yongyan LI

Hao HU

Ruifeng CHEN

Related Institution

Zhejiang University

University of Shaoxing at Shang Yu

Institute of Computing Technology, China Academy of Railway Sciences Co., Ltd.

China Railway Harbin Group Co.,Ltd.

College of Mathematics Physics and Information Engineering, Jiaxing University

⁰