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

doi:10.11959/j.issn.1000-0801.2017287

Abstract

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

CLC Number:

TN918.91

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.

Figures/Tables 6

References 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.

Metrics

Recommended 0

No Suggested Reading articles found!

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

RichHTML

PDF下载

Knowledge

Abstract

Cite this article

share this article

Figures/Tables 6

References 15

Related Articles 15

Metrics

Recommended 0

[1]	Cheng DING, Jinrong CHEN, Xiaodong CAO, Yi WANG. Quality of service based hierarchical resource allocation algorithm [J]. Telecommunications Science, 2022, 38(1): 102-111.
[2]	Yongyan LI,Jianping WU. Wireless sensor node localization based on IPSO-MC [J]. Telecommunications Science, 2020, 36(3): 11-18.
[3]	Haoran LIU,Xingqi WANG,Yujing DENG,Yuhua QIN. Evaluation model of node importance in directed scale-free network based on cascade failure [J]. Telecommunications Science, 2020, 36(2): 43-51.
[4]	Ruifeng CHEN,Ming NI,Chunjie XU,Hao HU. Communication performance analysis of wireless sensor network for railway environmental monitoring [J]. Telecommunications Science, 2019, 35(5): 70-77.
[5]	Ying ZHOU,Lihua YANG,Longxiang YANG,Meng NI. Energy-efficient data gathering scheme based on Kalman prediction and compressed sensing [J]. Telecommunications Science, 2019, 35(1): 74-80.
[6]	Shigen SHEN,Sheng FENG,Haiping ZHOU,Longjun HUANG,Keli HU,Qiying CAO. Optimal approach of suppressing WSN malware propagation based on cloud computing and dynamic Bayesian game [J]. Telecommunications Science, 2018, 34(9): 78-86.
[7]	Haibo YANG,Yourong CHEN,Banteng LIU,Yunkai ZHU,Ziyi SU. Coverage scheduling algorithm of mobile sensor nodes for optimizing network lifetime [J]. Telecommunications Science, 2018, 34(5): 39-49.
[8]	Shihua CAO,Keyong HU,Lidong WANG,Qihui WANG. Distributed hue recognition based k connectivity path detection in WSN [J]. Telecommunications Science, 2018, 34(2): 65-73.
[9]	Lijun LI,Fuquan ZHANG,Hongfei LIU. Data transmission algorithm for mobile wireless sensor network based on power loss equalization control mechanism [J]. Telecommunications Science, 2018, 34(11): 1-9.
[10]	Kai ZHOU. Nodes deployment strategy for underwater wireless sensors networks based on grids [J]. Telecommunications Science, 2018, 34(11): 48-58.
[11]	Haiping ZHOU,Shigen SHEN,Longjun HUANG,Sheng FENG. Game theory-based malware propagation model for wireless sensor network [J]. Telecommunications Science, 2018, 34(11): 67-76.
[12]	Deyue MENG,Errong PEI,Youlin HUANG. Design of MAC protocol and performance analysis for heterogeneous nodes separating CRSN [J]. Telecommunications Science, 2017, 33(8): 107-119.
[13]	Jianhua LIU,Minglu LI,Dazhi LI,Luqun LI. Adaptation trust evolution scheme for mobile robot in industrial wireless sensor-cloud [J]. Telecommunications Science, 2017, 33(6): 86-96.
[14]	Guoyong DAI,Weiyuan SHI,Kezhen YING,Qingzhang CHEN,Keji MAO. Novel barrier-reinforcing method based on mobile nodes re-deployment in WSN [J]. Telecommunications Science, 2017, 33(6): 97-104.
[15]	Yanzhi ZHANG,Xiaoqin YE. Detection of sybil attacks based on periodic ultra wide band distance information in WSN [J]. Telecommunications Science, 2016, 32(8): 110-117.