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

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

CLC Number:

TP393

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.

Figures/Tables 13

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

Minimum cost of node deployment strategy for heterogeneous sensor networks

RichHTML

PDF (PC)

Like

Knowledge

Abstract

Cite this article

share this article

Figures/Tables 13

References 25

Related Articles 15

Metrics

Comments

Recommended 10

[1]	LU Jixiang,FANG Boya. Research and experiment on multi-user computational offloading based on mobile edge computing [J]. Journal of Xidian University, 2020, 47(4): 78-85.
[2]	ZHOU Ji,XU Mengying,WANG Jiaojiao,LU Yi. Improved scheme for spectrum allocation in cognitive wireless sensor networks [J]. Journal of Xidian University, 2020, 47(3): 80-85.
[3]	WANG Ren,WANG Yi,HU Yanjun,JIANG Fang,XU Yaohua. Collaborative offloading of overloaded MEC servers in ultra-dense heterogeneous networks [J]. Journal of Xidian University, 2020, 47(2): 126-134.
[4]	YANG Jie,JIANG Junzheng. Method for data recovery in the sensor network based on the joint graph model [J]. Journal of Xidian University, 2020, 47(1): 44-51.
[5]	TIAN Qiang,FENG Dazheng,LI Jin,HU Haoshuang. New two-step semidefinite relaxation method for acoustic energy-based localization [J]. Journal of Xidian University, 2019, 46(4): 16-21.
[6]	ZHEN Yan,ZHAO Hu. Resource scheduling strategy in hierarchical software defined wireless sensor networks [J]. Journal of Xidian University, 2019, 46(4): 87-98.
[7]	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.
[8]	FANG Deliang;RAN Xiaomin;LI Ou. Energy efficient distributed sensor management algorithm [J]. Journal of Xidian University, 2017, 44(2): 171-177.
[9]	QIAO Junfeng;LIU Sanyang;QI Xiaogang. Power control in wireless sensor networks based on robust optimization [J]. Journal of Xidian University, 2016, 43(5): 81-87.
[10]	WANG Aimin;LIU Yongqiang;ZHANG Jing;LIU Yanheng. Coverage algorithm for finding the minimum working sets in WSNs [J]. Journal of Xidian University, 2016, 43(4): 141-146.
[11]	WANG Jing;ZHANG Shuai;GAO Dan;WANG Yingguan. Distributed synchronization protocol for wireless sensor networks [J]. Journal of Xidian University, 2016, 43(4): 105-110+134.
[12]	WEI Shengyun;ZHANG Jing;GUO Hong;LI Ou. Sensor selection algorithm based on modified binary particle swarm optimization [J]. Journal of Xidian University, 2016, 43(2): 150-156.
[13]	DU Bai;LI Hongyan. Network selection algorithm in heterogeneous wireless networks based on residual service time [J]. J4, 2016, 43(1): 7-11.
[14]	LIU Kui;LIU Sanyang. Novel sensor node importance evaluation method based on the agglomeration contraction principle [J]. J4, 2015, 42(3): 90-96.
[15]	WANG Jing;ZHANG Shuai;GAO Dan;WANG Yingguan . Expansive time synchronization protocol for wireless sensor networks [J]. J4, 2015, 42(2): 133-139.

类型	成本/￥	感知半径/m	通信半径/m
1	2	30	60
2	3	40	80
3	5	60	120