无线传感器网络中基于“k-覆盖问题”的多项式时间算法

王骐; 肖正安; 王怀兴

doi:10.11959/j.issn.1000-0801.2017287

您当前的位置：

首页 >

文章列表页 >

无线传感器网络中基于“k-覆盖问题”的多项式时间算法

研究与开发 | 更新时间：2024-06-05

- 无线传感器网络中基于“k-覆盖问题”的多项式时间算法
- Polynomial time algorithm for solving k-coverage problem in wireless sensor networks
- 电信科学 2017年33卷第12期页码：91-98
- 作者机构：
- 作者简介：
  
  [ "王骐（1970-），男，博士，湖北第二师范学院物理与机电工程学院副教授，主要研究方向为无线传感器网络安全、嵌入式系统应用。" ]
  [ "肖正安（1974-），男，湖北第二师范学院物理与机电工程学院讲师，主要研究方向为图像数字信号处理。" ]
  [ "王怀兴（1977-），男，湖北第二师范学院物理与机电工程学院副教授，主要研究方向为嵌入系统应用。" ]
- 基金信息：
  
  湖北省高等学校优秀中青年科技创新团队计划项目;Hubei Provincial Department of Education Research Program(T201417)
- DOI：10.11959/j.issn.1000-0801.2017287
  中图分类号： TN918.91
- 网络出版日期：2017-12，
  
  纸质出版日期：2017-12-20
- 稿件说明：
移动端阅览
王骐, 肖正安, 王怀兴. 无线传感器网络中基于“k-覆盖问题”的多项式时间算法[J]. 电信科学, 2017,33(12):91-98.

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.
王骐, 肖正安, 王怀兴. 无线传感器网络中基于“k-覆盖问题”的多项式时间算法[J]. 电信科学, 2017,33(12):91-98. DOI： 10.11959/j.issn.1000-0801.2017287.

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 .

浏览量

600

下载量

CSCD

文章被引用时，请邮件提醒。

提交

工具集

关联资源

基于服务质量的层次化结构资源分配算法

基于IPSO-MC融合算法的无线传感器节点定位

面向铁路环境监测的无线传感器网络通信性能分析

基于卡尔曼预测与压缩感知的WSN中高能效数据收集方法

基于博弈论的无线传感器网络恶意程序传播模型