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

doi:10.11959/j.issn.1000-0801.2017287

电信科学 ›› 2017, Vol. 33 ›› Issue (12): 91-98.doi: 10.11959/j.issn.1000-0801.2017287

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

王骐,肖正安,王怀兴

湖北第二师范学院物理与机电工程学院，湖北武汉 430205

修回日期:2017-09-30 出版日期:2017-12-01 发布日期:2018-01-12
作者简介:王骐（1970-），男，博士，湖北第二师范学院物理与机电工程学院副教授，主要研究方向为无线传感器网络安全、嵌入式系统应用。|肖正安（1974-），男，湖北第二师范学院物理与机电工程学院讲师，主要研究方向为图像数字信号处理。|王怀兴（1977-），男，湖北第二师范学院物理与机电工程学院副教授，主要研究方向为嵌入系统应用。
基金资助:
湖北省高等学校优秀中青年科技创新团队计划项目(T201417)

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

Qi WANG,Zheng’an XIAO,Huaixing WANG

School of Physics and Electromechanical Engineering,Hubei University of Education,Wuhan 430205,China

Revised:2017-09-30 Online:2017-12-01 Published:2018-01-12
Supported by:
Hubei Provincial Department of Education Research Program(T201417)

摘要/Abstract

摘要：

针对无线传感器网络的最差覆盖和最佳覆盖，探寻如何解决二维目标区域内的“k-覆盖问题”，提出了一种解决此问题的多项式时间算法。该算法基于扩展圆盘的几何图形提出了一系列的定义和定理，将“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.

Key words: wireless sensor network, k-coverage problem, growing disk, adjacent border, polynomial time algo-rithm

中图分类号:

TN918.91

王骐,肖正安,王怀兴. 无线传感器网络中基于“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.

图/表 6

参考文献 15

[1]	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.
[2]	杨海雳, 赵静 . 基于 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.
[3]	王成, 樊建席, 王仁喜 ,等. 基于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.
[4]	丁旭, 吴晓蓓, 黄成 . 基于改进粒子群算法和特征点集的无线传感器网络覆盖问题研究[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.
[5]	孙泽宇, 伍卫国, 王换招 ,等. 无线传感器网络基于参数可调增强型覆盖控制算法[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.
[6]	刘志强, 沈廼桐, 毛强 ,等. 无线传感器网络动态覆盖的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.
[7]	高洁, 吴延红, 白建侠 ,等. 无线传感器网络最小覆盖能量优化算法[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.
[8]	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.
[9]	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.
[10]	鲁晓波, 阮福, 王立中 . 无线传感器网络覆盖优化策略[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.
[11]	王兴伟, 蔡凌, 黄敏 ,等. 基于空间镶嵌的三维无线传感器网络 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.
[12]	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.
[13]	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.
[14]	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.
[15]	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.

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

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

在线阅读

PDF下载

可视化

摘要/Abstract

引用本文

使用本文

图/表 6

参考文献 15

相关文章 15

Metrics

推荐阅读 0

[1]	丁铖, 陈锦荣, 曹小冬, 王翊. 基于服务质量的层次化结构资源分配算法[J]. 电信科学, 2022, 38(1): 102-111.
[2]	李勇燕,吴坚平. 基于IPSO-MC融合算法的无线传感器节点定位[J]. 电信科学, 2020, 36(3): 11-18.
[3]	张红,沈士根,吴小军,曹奇英. 基于元胞自动机和静态贝叶斯博弈的WSN恶意程序传染模型[J]. 电信科学, 2019, 35(6): 60-69.
[4]	陈瑞凤,倪明,徐春婕,胡昊. 面向铁路环境监测的无线传感器网络通信性能分析[J]. 电信科学, 2019, 35(5): 70-77.
[5]	周颖,杨丽花,杨龙祥,倪梦. 基于卡尔曼预测与压缩感知的WSN中高能效数据收集方法[J]. 电信科学, 2019, 35(1): 74-80.
[6]	曹世华,胡克用,王李冬,王琦晖. 基于分布式色调识别的无线传感器网络k连通性路径检测[J]. 电信科学, 2018, 34(2): 65-73.
[7]	周海平,沈士根,黄龙军,冯晟. 基于博弈论的无线传感器网络恶意程序传播模型[J]. 电信科学, 2018, 34(11): 67-76.
[8]	孟得月,裴二荣,黄佑林. 异质节点分离CRSN中MAC协议设计与性能分析[J]. 电信科学, 2017, 33(8): 107-119.
[9]	刘建华,李明禄,李大志,李鲁群. 工业无线传感云中面向移动机器人的自适应信任演化机制[J]. 电信科学, 2017, 33(6): 86-96.
[10]	戴国勇,施伟元,应可珍,陈庆章,毛科技. 基于移动节点二次部署的WSN栅栏新型强化方法[J]. 电信科学, 2017, 33(6): 97-104.
[11]	孟凯露,岳克强,尚俊娜. 基于元胞蝙蝠算法的无线传感器网络节点定位研究[J]. 电信科学, 2017, 33(11): 56-65.
[12]	刘开南,韩旭. 基于人工蜂群寻优算法的WSN中继节点布局方案[J]. 电信科学, 2016, 32(9): 61-67.
[13]	邹永艳,张衍志. WSN中视觉辅助方案结合TI CC2431 ZPS平台的跟踪定位方法[J]. 电信科学, 2016, 32(9): 68-74.
[14]	张衍志,叶小琴. WSN中基于周期性超宽带距离信息的女巫攻击检测[J]. 电信科学, 2016, 32(8): 110-117.
[15]	刘述木,杨建,黎远松. WSN中基于自适应预测聚类的多组群目标的跟踪方法[J]. 电信科学, 2016, 32(7): 68-75.