异构传感网成本优化的节点部署策略

doi:10.19665/j.issn1001-2400.2021.04.002

摘要/Abstract

摘要：

针对异构无线传感器网络中节点部署密度大、目标覆盖和网络连通容错性能差以及部署代价高的问题,提出了一种基于改进珊瑚礁算法的成本优化的节点异构传感网络容错部署策略。该策略综合考虑了部署位置和节点类型不同造成的部署代价不同,在保证监测目标被传感器节点多重覆盖和传感器节点之间多重连通的条件下,以节点部署成本最优化为求解目标。在改进的珊瑚礁算法中一方面借鉴和声搜索算法的思想增强算法的优化能力,另一方面通过对算法求解过程中优秀解的再利用,增强算法的优化效率。仿真结果表明,较之其他比较算法,提出的改进珊瑚礁算法能有效地在保证目标多重覆盖和节点之间多重连通的条件下降低网络部署成本。

关键词: 无线传感器网络, 异构网络, 连通覆盖, 珊瑚礁算法, 和声搜索算法

Abstract:

A minimum-cost-deployment strategy based on objective optimization is proposed to address the problems existing in heterogeneous sensor networks such as high density of the nodes,bad target coverage and connectivity performances,and high deployment spending.The problem we aim to solve is characterized by different parameters in terms of the deployment cost of positions and the cost of the sensors.The enhanced version of coral reef optimization (CRO for short) algorithm is utilized to solve the problem of how to select the proper positions and sensors to achieve the minimum deployment cost of heterogeneous sensor networks which can fulfill both k-coverage and m-connectivity requirements.The enhanced version of the CRO is named ECRO.In the ECRO two methods are employed to improve the optimization efficiency of the CRO.One method is that inspired by the process of the harmony search algorithm the operators such as HMCR and PAR of the harmony search algorithm blend with the CRO.The other one is that the excellent solutions are reused to exploit the knowledge and experience accumulated in the process of running the CRO.For comparison purposes,a greedy algorithm is also proposed.Simulation experiments show that compared with some related existing algorithms,the proposed algorithm reduces the deployment cost of sensor nodes while fulfilling the requirements of k-coverage and m-connectivity requirements.

Key words: wireless sensor networks, heterogeneous networks, connected coverage, coral reef optimization algorithm, harmony search algorithm

中图分类号:

TP393

李明,胡江平,曹晓莉. 异构传感网成本优化的节点部署策略[J]. 西安电子科技大学学报, 2021, 48(4): 11-19.

LI Ming,HU Jiangping,CAO Xiaoli. Minimum cost of node deployment strategy for heterogeneous sensor networks[J]. Journal of Xidian University, 2021, 48(4): 11-19.

图/表 13

图1

图2

表1

表2

表3

图3

图4

图5

图6

图7

图8

图9

图10

参考文献 25

[1]	RAHMAN A U, ALHARBY A, HASBULLAH H, et al. Corona Based Deployment Strategies in Wireless Sensor Network:A Survey[J]. Journal of Network and Computer Applications, 2016, 64:176-193. doi: 10.1016/j.jnca.2016.02.003
[2]	BRZOZOWSKI M, FROHBERG M, LANGENDOERFER P. Real-World Deployments of Sensor Networks:Practical Lessons for Researchers[J]. Computer Communications, 2019, 145:326-334. doi: 10.1016/j.comcom.2019.07.008
[3]	CHEN D, CHEN L C, CHEN M Y. A Coverage-Aware and Energy-Efficient Protocol for The Distributed Wireless Sensor Networks[J]. Computer Communications, 2019, 137:15-31. doi: 10.1016/j.comcom.2019.01.008
[4]	薛亮, 陈晰, 赵继军, 等. 无线传感器网络中基于Voronoi 覆盖Delaunay三角剖分图的最小刚性拓扑控制算法[J]. 自动化学报, 2016, 42(10):1570-1584.
	XUE Liang, CHEN Xi, ZHAO Jijun, et al. A Minimal Rigid Topology Control Algorithm Based on Voronoi Coverage and Delaunay Triangulation in Wireless Sensor Networks[J]. Journal of Automatica Sinica, 2016, 42(10):1570-1584.
[5]	卢毅, 周杰, 万连城. 一种无线传感器网络二维目标覆盖的改进方法[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.
[6]	范兴刚, 王超, 杨静静, 等. 一种基于选择框的有向K-栅栏构建算法[J]. 计算机学报, 2016, 39(5):946-960.
	FAN Xinggang, WANG Chao, YANG Jingjing, et al. A Strong K-Barrier Construction Scheme Based on Selecting Box for Directional Sensor Networks[J]. Chinese Journal of Computer, 2016, 39(5):946-960.
[7]	FANG W, SONG X H, WU X J, et al. Novel Efficient Deployment Schemes for Sensor Coverage in Mobile Wireless Sensor Networks[J]. Information Fusion, 2018, 41:25-36. doi: 10.1016/j.inffus.2017.08.001
[8]	HANH N T, NGUYEN T, HOAIETAL N X, et al. An Efficient Genetic Algorithm for Maximizing Area Coverage in Wireless Sensor Networks[J]. Information Sciences, 2019, 488:58-75. doi: 10.1016/j.ins.2019.02.059
[9]	李明, 胡江平. 基于和声搜索算法的无线传感器网络容错部署方法[J]. 传感器与微系统, 2019, 38(11):50-53.
	LI Ming, HU Jiangping. A Fault Tolerant Deployment Method Based on Harmony Search Algorithm for Wireless Sensor Networks[J]. Transducer and Microsystem Technologies, 2019, 38(11):50-53.
[10]	李明, 石为人. 基于二进制粒子群算法的异构传感器网络成本最优节点部署机制[J]. 计算机科学, 2010, 37(12):63-66.
	LI Ming, SHI Weiren. Optimal Sensor Deployment Scheme in Heterogeneous Sensor Networks Based on Binary Particle Swarm Algorithm[J]. Computer Science, 2010, 37(12):63-66.
[11]	KATTI A. Target Coverage in Random Wireless Sensor Networks using Cover Sets[J]. Journal of King Saud University-Computer and Information Sciences, 2019, 5:1-13.
[12]	NGUYEN P L, HANH N T, KHUONG N T, et al. Node Placement for Connected Target Coverage in Wireless Sensor Networks with Dynamic Sinks[J]. Pervasive and Mobile Computing, 2019, 59:101070. doi: 10.1016/j.pmcj.2019.101070
[13]	刘洲洲, 李士宁. WSNs中基于期望网络覆盖和分簇压缩感知的数据收集方案[J]. 控制与决策, 2018, 33(3):422-430.
	LIU Zhouzhou, LI Shining. DataCollection Scheme Based on Expected Network Coverage and Cluster Compressive Sensing for Wsns[J]. Control and Decision, 2018, 33(3):422-430.
[14]	ZISHAN A, KARIM I, SHUBHA S, et al. Maximizing Heterogeneous Coverage in Over and Under Provisioned Visual Sensor Networks[J]. Journal of Network and Computer Applications, 2018, 124:44-62. doi: 10.1016/j.jnca.2018.09.009
[15]	KE W C, LIU B H, TSAI M J. Constructing A Wireless Sensor Network to Fully Cover Critical Grids by Deploying Minimum Sensors on Grid Points is NP-Complete[J]. IEEE Transactions on Computers, 2007, 56(5):710-715. doi: 10.1109/TC.2007.1019
[16]	LIU L, HU B, LI L. Energy Conservation Algorithms for Maintaining Coverage and Connectivity in Wireless Sensor Networks[J]. IET Communications, 2010, 4(7):786-800. doi: 10.1049/iet-com.2009.0129
[17]	SALCEDO S, GALLO M D, PASTOR S A, et al. Offshore Wind Farm Design with the Coral Reefs Optimization Algorithm[J]. Renewable Energy, 2014, 63(2):109-115. doi: 10.1016/j.renene.2013.09.004
[18]	LI M, MIAO C Y, LEUNG C. A Coral Reef Algorithm Based on Learning Automata for The Coverage Control Problem of Heterogeneous Directional Sensor Networks[J]. Sensors, 2015, 15(12):30617-30635. doi: 10.3390/s151229820
[19]	SANZ S, DÍAZ P G, SER J D, et al. A Novel Grouping Coral Reefs Optimization Algorithm for Optimal Mobile Network Deployment Problems under Electromagnetic Pollution and Capacity Control Criteria[J]. Expert Systems with Applications, 2016, 55:388-402. doi: 10.1016/j.eswa.2016.02.032
[20]	GEEM Z W, KIM J H, LOGANATHAN G V. A New Heuristic Optimization Algorithm:Harmony Search[J]. Simulation, 2001, 76(2):60-68. doi: 10.1177/003754970107600201
[21]	李明, 曹晓莉, 胡卫军. 基于多目标和声搜索的无线传感器网络分簇路由算法[J]. 仪器仪表学报, 2014, 35(1):162-168.
	LI Ming, CAO Xiaoli, HU Weijun. Optimal Multi-Objective Clustering Routing Protocol Based on Harmony Search Algorithm for Wireless Sensor Networks[J]. Chinese Journal of Scientific Instrument, 2014, 35(1):162-168.
[22]	HARIZAN S, KUILA P. Coverage and Connectivity Aware Energy Efficient Scheduling in Target Based Wireless Sensor Networks:An Improved Genetic Algorithm Based Approach[J]. Wireless Networks, 2019, 25(4):1995-2011. doi: 10.1007/s11276-018-1792-2
[23]	SHALABI M A, ANBAR M, WAN T C, et al. Energy Efficient Multi-Hop Path in Wireless Sensor Networks Using An Enhanced Genetic Algorithm[J]. Information Sciences, 2019, 500:259-273. doi: 10.1016/j.ins.2019.05.094
[24]	REBAIN M, LEBERRE M.SNOUSSI H, et al. Sensor Deployment Optimization Methods to Achieve both Coverage and Connectivity in Wireless Sensor Networks[J]. Computers and Operations Research, 2015, 59:11-21. doi: 10.1016/j.cor.2014.11.002
[25]	李明, 胡江平. 异构传感器网络中基于差分进化的调度算法[J]. 计算机工程, 2019, 45(9):70-75.
	LI Ming, HU Jiangping. Scheduling Algorithm Based on Differential Evolution in Heterogeneous Sensor Network[J]. Computer Engineering, 2019, 45(9):70-75.

(α₁,α₂,α₃)	ECRO (F₁,F₂,F₃)	CRO(F₁,F₂,F₃)
(0.1,0.55,0.35)	(0.59,0.96,0.98)	(0.58,0.93,0.94)
(0.2,0.45,0.35)	(0.63,0.99,0.89)	(0.57,0.95,0.87)
(0.3,0.35,0.35)	(0.67,0.99,0.98)	(0.65,0.95,0.94)
(0.7,0.2,0.1)	(0.47,0.98,0.74)	(0.43,0.93,0.69)
(0.8,0.1,0.1)	(0.65,0.76,0.71)	(0.64,0.76,0.65)

(α₁,α₂,α₃)	ECRO(F₁,F₂,F₃)	CRO(F₁,F₂,F₃)
(0.1,0.55,0.35)	(0.67,0.97,0.91)	(0.81,0.95,0.85)
(0.2,0.45,0.35)	(0.72,1,0.9)	(0.68,0.94,0.86)
(0.3,0.35,0.35)	(0.73,1,0.91)	(0.70,0.96,0.87)
(0.7,0.2,0.1)	(0.59,0.98,0.87)	(0.53,0.96,0.82)
(0.8,0.1,0.1)	(0.73,0.88,0.82)	(0.72,0.84,0.76)