一种无线传感器网络二维目标覆盖的改进方法

doi:10.19665/j.issn1001-2400.2019.02.017

摘要/Abstract

摘要：

针对二维目标覆盖问题,提出了一种新的量子退火算法,设计了相应的系统模型,并给出了覆盖优化的目标函数。因为以往的启发式算法存在运行停滞等问题,所以为量子退火算法设计了全新的解集生成方式、量子旋转门、量子位测量方法和量子位状态更新方法,加快了算法的收敛速度。将基于量子退火算法的方法与粒子群算法、蚁群算法进行了仿真比较。仿真结果显示,相比粒子群算法与蚁群算法,该量子退火算法能够有效地提升解的质量,检出的目标数有较大幅度的提高。

关键词: 无线传感器网络, 量子退火算法, 目标覆盖, 粒子群算法, 蚁群算法

Abstract:

Two-dimensional target coverage is a key issue in wireless sensor networks. A good coverage algorithm can effectively improve the monitoring effect of wireless sensor networks. Aiming at the two-dimensional target coverage problem, a new quantum annealing algorithm is proposed, and the corresponding system model is designed. The objective function of coverage optimization is also given. Aiming at the problem of running stagnation in the past heuristic algorithms, a new solution set generation method, quantum revolving gate, qubit measurement method and qubit state update method are designed for the quantum annealing algorithm, which accelerates the convergence speed of the algorithm. The method based on the quantum annealing algorithm is compared with particle swarm optimization and ant colony optimization. Simulation results show that compared with the particle swarm optimization algorithm and the ant colony optimization, the proposed algorithm can effectively improve the quality of the solution, with the number of detected targets greatly improved.

Key words: wireless sensor networks, quantum simulated annealing algorithm, target coverage, particle swarm optimization, ant colony optimization

中图分类号:

TP393

卢毅,周杰,万连城. 一种无线传感器网络二维目标覆盖的改进方法[J]. 西安电子科技大学学报, 2019, 46(2): 101-106.

LU Yi,ZHOU Jie,WAN Liancheng. Improved method for 2D target coverage in wireless sensor networks[J]. Journal of Xidian University, 2019, 46(2): 101-106.

图/表 3

表1

量子旋转门中旋转角查询表"

$z k angle$	Δθ	α_kβ_k>0	α_kβ_k<0	α_k=0	β_k=0
0	φt	-1	1	±1	0
	φt	1	-1	0	±1

表1

图1

图2

参考文献 17

[1]	CHENG C F, WANG C W . The Barrier-Breach Problem of Barrier Coverage in Wireless Sensor Networks[J]. IEEE Wireless Communications Letters, 2017,21(10):2262-2265. doi: 10.1109/LCOMM.2017.2694432
[2]	ZHANG X M, YAN F, LI C , et al. Coverage Efficiency-based Broadcast Protocol for Asynchronous Wireless Sensor Networks[J]. IEEE Wireless Communications Letters, 2016,5(1):76-79. doi: 10.1109/LWC.2015.2498173
[3]	YU J G, WAN S L, CHENG X Z , et al. Coverage Contribution Area Based k -coverage for Wireless Sensor Networks[J]. IEEE Transactions on Vehicular Technology, 2017,66(9):8510-8523. doi: 10.1109/TVT.2017.2681692
[4]	CHENG C F, WANG C W . The Target-barrier Coverage Problem in Wireless Sensor Networks[J]. IEEE Transactions on Mobile Computing, 2018,17(5):1216-1232. doi: 10.1109/TMC.2017.2751040
[5]	WU H Y, SHAHIDEHPOUR M . Applications of Wireless Sensor Networks for Area Coverage in Microgrids[J]. IEEE Transactions on Smart Grid, 2018,9(3):1590-1598. doi: 10.1109/TSG.2016.2594203
[6]	DENG X J, TANG Z J, YANG L T , et al. Confident Information Coverage Hole Healing in Hybrid Industrial Wireless Sensor Networks[J]. IEEE Transactions on Industrial Informatics, 2018,14(5):2220-2229. doi: 10.1109/TII.2017.2764038
[7]	YANG C L, CHIN K W, LIU Y , et al. Complete Targets Coverage in Wireless Sensor Networks with Energy Transfer[J]. IEEE Communications Letters, 2018,22(2):396-399. doi: 10.1109/LCOMM.2017.2773464
[8]	YANG C L, CHIN K W . On Nodes Placement in Energy Harvesting Wireless Sensor Networks for Coverage and Connectivity[J]. IEEE Transactions on Industrial Informatics, 2017,13(1):27-36. doi: 10.1109/TII.2016.2603845
[9]	HAN G J, LIU L, JIANG J F , et al. Analysis of Energy-efficient Connected Target Coverage Algorithms for Industrial Wireless Sensor Networks[J]. IEEE Transactions on Industrial Informatics, 2017,13(1):135-143. doi: 10.1109/TII.2015.2513767
[10]	ZHU J J, WANG B . The Optimal Placement Pattern for Confident Information Coverage in Wireless Sensor Networks[J]. IEEE Transactions on Mobile Computing, 2016,15(4):1022-1032. doi: 10.1109/TMC.2015.2444397
[11]	ZHANG Z, WILLSON J, LU Z X , et al. Approximating Maximum Lifetime k -coverage Through Minimizing Weighted k -cover in Homogeneous Wireless Sensor Networks[J]. IEEE/ACM Transactions on Networking, 2016,24(6):3620-3633. doi: 10.1109/TNET.2016.2531688
[12]	GUO P, LIU X F, TANG S J , et al. Enabling Coverage-preserving Scheduling in Wireless Sensor Networks for Structural Health Monitoring[J]. IEEE Transactions on Computers, 2016,65(8):2456-2469. doi: 10.1109/TC.2015.2485204
[13]	王爱民, 刘永强, 张婧 , 等. WSNs中一种寻找最小工作节点集的覆盖算法[J]. 西安电子科技大学学报, 2016,43(4):141-146. doi: 10.3969/j.issn.1001-2400.2016.04.025
	WANG Aimin, LIU Yongqiang, ZHANG Jing , et al. Coverage Algorithm for Finding the Minimum Working Sets in WSNs[J]. Journal of Xidian University, 2016,43(4):141-146. doi: 10.3969/j.issn.1001-2400.2016.04.025
[14]	魏声云, 张静, 郭虹 , 等. 改进二进制粒子群优化的节点选择算法[J]. 西安电子科技大学学报, 2016,43(2):150-156. doi: 10.3969/j.issn.1001-2400.2016.02.026
	WEI Shengyun, ZHANG Jing, GUO Hong , et al. Sensor Selection Algorithm Based on Modified Binary Particle Swarm Optimization[J]. Journal of Xidian University, 2016,43(2):150-156. doi: 10.3969/j.issn.1001-2400.2016.02.026
[15]	LI Y Y, GAO W, WU C M , et al. Deployment of Sensors in WSN: An Efficient Approach Based on Dynamic Programming[J]. Chinese Journal of Electronics, 2015,24(1):33-36. doi: 10.1049/cje.2015.01.006
[16]	YE M, WANG Y P, DAI C , et al. A Hybrid Genetic Algorithm for the Minimum Exposure Path Problem of Wireless Sensor Networks Based on a Numerical Functional Extreme Model[J]. IEEE Transactions on Vehicular Technology, 2016,65(10):8644-8657. doi: 10.1109/TVT.2015.2508504
[17]	QASIM T, ZIA M, MINHAS Q A , et al. An Ant Colony Optimization Based Approach for Minimum Cost Coverage on 3-D Grid in Wireless Sensor Networks[J]. IEEE Communications Letters, 2018,22(6):1140-1143. doi: 10.1109/LCOMM.2018.2819643