改进多目标蚁狮算法的WSNs节点部署策略

doi:10.19665/j.issn1001-2400.2022.05.006

摘要/Abstract

摘要：

针对无线传感网络节点部署中需要均衡覆盖率、连通度、节点数目等问题,构建了最低覆盖率与节点间连通性为约束条件的多目标节点部署模型,利用Pareto最优解集的思想,提出了一种基于改进多目标蚁狮算法的节点部署策略。首先,使用Fuch混沌映射初始化种群,以增加种群的多样性,同时引入自适应收缩边界因子改善算法易陷入局部最优的缺点;然后,利用时变策略对蚂蚁位置扰动以增强算法的寻优能力;再后,通过测试函数与其他多目标算法进行对比分析,结果表明改进后的算法在不同的测试函数上均能获得最小的世代距离与反向世代距离值,验证了所提策略的有效性;最后,将改进多目标蚁狮算法应用于无线传感器网络多目标节点部署中。仿真结果表明,相对于其他几种多目标算法,改进多目标蚁狮算法能有效解决无线传感器网络节点的多目标优化部署问题,提高了监测区域覆盖率与连通性,并为决策者提供更多可行解。

关键词: 无线传感网络, 节点部署, 多目标优化, 蚁狮算法, Pareto原则

Abstract:

In order to balance the coverage,connectivity and number of nodes in the deployment of wireless sensor networks (WSNs),a multi-objective node deployment model with the minimum coverage and connectivity between nodes as the constraint conditions is constructed,and by using the ideology of the Pareto optimal solution set,a node deployment strategy based on the improved multi-objective ant-lion Algorithm (IMOALO) is proposed.First,the Fuch chaotic map is used to initialize the population and increase the diversity of population.At the same time,the performance of the IMOALO is improved by introducing the adaptive shrinkage boundary factor,which can overcome the shortcoming of being easily plunged into local optimal of the MOALO.Second,the time-varying strategy position disturbance is used to the ant for improving the optimization ability of the algorithm.Third,a comparison of the test function with other multi-objective algorithms shows that the improved algorithm can lead to the minimum GD and IGD values on different test functions,which verifies the effectiveness of the proposed strategy.Finally,the IMOALO is applied to the multi-objective node deployment in WSNs.Simulation results show that compared with other multi-objective algorithms,the IMOALO can effectively solve the multi-objective optimization deployment problem of the nodes in WSNs,improve the coverage and connectivity of the monitoring area,and provide more feasible solutions for decision makers.

Key words: wireless sensor networks, node deployment, multi-objective optimization, ant lion algorithm, Pareto principle

中图分类号:

TP393

张浩, 覃涛, 徐凌桦, 王霄, 杨靖. 改进多目标蚁狮算法的WSNs节点部署策略[J]. 西安电子科技大学学报, 2022, 49(5): 47-59.

ZHANG Hao, QIN Tao, XU Linghua, WANG Xiao, YANG Jing. WSNs node deployment strategy based on the improved multi-objective ant-lion algorithm[J]. Journal of Xidian University, 2022, 49(5): 47-59.

图/表 16

图1

图2

图3

图4

图5

图6

图7

图8

表1

表2

图9

表3

图10

图11

图12

图13

参考文献 28

[1]	XU Y, DING O, QU R, et al. Hybrid Multi-Objective Evolutionary Algorithms Based on Decomposition for Wireless Sensor Network Coverage Optimization[J]. Applied Soft Computing, 2018, 68(3):268-282. doi: 10.1016/j.asoc.2018.03.053
[2]	RANDHAWA S, JAIN S. MLBC:Multi-Objective Load Balancing Clustering Technique in Wireless Sensor Networks[J]. Applied Soft Computing, 2019, 74(1):66-89. doi: 10.1016/j.asoc.2018.10.002
[3]	徐公国, 段修生, 单甘霖, 等. 基于多目标局部变异-自适应量子粒子群优化算法的复杂地形多传感器优化部署[J]. 兵工学报, 2018, 39(11):2192-2201. doi: 10.3969/j.issn.1000-1093.2018.11.013
	XU Gongguo, DUAN Xiusheng, SHAN Ganlin, et al. Optimization Deployment of Multi-Sensors in Complex Terrain Based on Multi-Objective LM-AQPSO Algorithm[J]. ACTA ARMAMENTARII, 2018, 39(11):2192-2201. doi: 10.3969/j.issn.1000-1093.2018.11.013
[4]	HARIZAN S, KUILA P. A Novel NSGA-II for Coverage and Connectivity Aware Sensor Node Scheduling in Industrial Wireless Sensor Networks[J]. Digital Signal Processing, 2020, 10(5):1-14. doi: 10.1006/dspr.1999.0355
[5]	GUPTA S K, KUILA P, JANA P K. Genetic Algorithm Approach for K-Coverage and M-Connected Node Placement in Target Based Wireless Sensor Networks[J]. Computers & Electrical Engineering, 2015, 56(11):544-556.
[6]	OSAMA M A, AL-AJOURI A. Maximizing Wireless Sensor Network Coverage with Minimum Cost Using Harmony Search Algorithm[J]. IEEE Sensors Journal, 2017, 17(3):882-896. doi: 10.1109/JSEN.2016.2633409
[7]	REBAI M, BERRE M L, SNOUSSI H, et al. Sensor Deployment Optimization Methods to Achieve Both Coverage and Connectivity in Wireless Sensor Networks[J]. Computers & Operations Research, 2015, 59(7):11-21. doi: 10.1016/j.cor.2014.11.002
[8]	MIAO Z M, YUAN X F, ZHOU F Y, et al. Grey Wolf Optimizer with an Enhanced Hierarchy and Its Application to the Wireless Sensor Network Coverage Optimization Problem[J]. Applied Soft Computing Journal, 2020, 96(8):1-21.
[9]	GUPTA G P, JHA S. Biogeography-Based Optimization Scheme for Solving the Coverage and Connected Node Placement Problem for Wireless Sensor Networks[J]. Wireless Networks, 2019, 25(6):3167-3177. doi: 10.1007/s11276-018-1709-0
[10]	杜文占, 余志勇, 杨剑, 等. 改进NSGA-II算法及监测天线部署优化研究[J]. 西安电子科技大学学报, 2021, 48(5):239-248.
	DU Wenzhan, YU Zhiyong, YANG Jian, et al. Improved NSGA-Ⅱ Algorithm and Research on Monitoring Antenna Optimization Deployment[J]. Journal of Xidian University, 2021, 48(5):239-248.
[11]	王登峰, 李慎华. 基于Pareto挖掘的白车身侧碰安全件轻量化优化设计[J]. 中国机械工程, 2021, 32(13):1584-1590.
	WANG Denfeng, LI Shenhua. Lightweight Optimization Design of Side Impact Safety Parts of BIW Based on Pareto Mining[J]. China Mechanical Engineering, 2021, 32(13):1584-1590.
[12]	程俊杰, 王海峰, 尚玲玲, 等. 一种高空飞艇螺旋桨结构多目标优化设计方法[J]. 航空动力学报, 2021, 36(3):584-591.
	CHENG Junjie, WANG Haifeng, SHANG Lingling, et al. Multi-Objective Optimization Design Method for Propeller Structure of a High-Altitude Airship[J]. Journal of Aerospace Power, 2021, 36(3):584-591.
[13]	闫群民, 马瑞卿, 马永翔, 等. 一种自适应模拟退火粒子群优化算法[J]. 西安电子科技大学学报, 2021, 48(4):120-127.
	YAN Qunmin, MA Ruiqing, MA Yongxiang, et al. Adaptive Simulated Annealing Particle Swarm Optimization Algorithm[J]. Journal of Xidian University, 2021, 48(4):120-127.
[14]	MIRJALILI S, MIRJALILI S M, LEWIS A. Grey Wolf Optimizer[J]. Advances in Engineering Software, 2014, 69(5):46-61. doi: 10.1016/j.advengsoft.2013.12.007
[15]	MIRJALILI S, LEWIS A. The Whale Optimization Algorithm[J]. Advances in Engineering Software, 2016, 95(5):51-67. doi: 10.1016/j.advengsoft.2016.01.008
[16]	FOULADGAR N, LOTFI S. A Novel Approach for Optimization in Dynamic Environments Based on Modified Cuckoo Search Algorithm[J]. Soft Computing, 2016, 20(7):2889-2903. doi: 10.1007/s00500-015-1951-7
[17]	ZHANG M J, LONG D Y, QIN T, et al. A Chaotic Hybrid Butterfly Optimization Algorithm with Particle Swarm Optimization for High-Dimensional Optimization Problems[J]. Symmetry, 2020, 12(11):1-27. doi: 10.3390/sym12010001
[18]	MIRJALILI S. The Ant Lion Optimizer[J]. Advances in Engineering Software, 2015, 83(1):80-98. doi: 10.1016/j.advengsoft.2015.01.010
[19]	MIRJALILI S, JANGIR P, SAREMI S. Multi-Objective Ant Lion Optimizer:A Multi-objective Optimization Algorithm for Solving Engineering Problems[J]. Applied Intelligence, 2017, 46(1):1-17. doi: 10.1007/s10489-016-0811-1
[20]	王瀛洲, 倪裕隆, 郑宇清, 等. 基于ALO-SVR的锂离子电池剩余使用寿命预测[J]. 中国电机工程学报, 2021, 41(4):1445-1457.
	WANG Yingzhou, NI Yulong, ZHENG Yuqing, et al. Remaining Useful Life Prediction of Lithium-Ion Batteries Based on Support Vector Regression Optimized and Ant Lion Optimizations[J]. Proceedings of the CSEE, 2021, 41(4):1445-1457.
[21]	刘颖明, 王瑛玮, 王晓东, 等. 基于蚁狮算法的风电集群储能容量配置优化方法[J]. 太阳能学报, 2021, 42(1):431-437.
	LIU Yingming, WANG Yingwei, WANG Xiaodong, et al. Optimization of Storage Capacity Allocation in Wind Farm Cluster Based on Ant Lion Optimization Algorithm[J]. Acta Energiae Solaris Sinica, 2021, 42(1):431-437.
[22]	黄长强, 赵克新. 基于改进蚁狮算法的无人机三维航迹规划[J]. 电子与信息学报, 2018, 40(7):1532-1538.
	HUANG Changqiang, ZHAO Kexin. Three Dimensional Path Planning of UAV with Improved Ant Lion Optimizer[J]. Journal of Electronics & Information Technology, 2018, 40(7):1532-1538.
[23]	刘景森, 霍宇, 李煜. 优选策略的自适应蚁狮优化算法[J]. 模式识别与人工智能, 2020, 33(2):121-132. doi: 10.16451/j.cnki.issn1003-6059.202002004
	LIU Jingsen, HUO Yu, LI Yu. Preferred Strategy Based Self-adaptive Ant Lion Optimization Algorithm[J]. Pattern Recognition and Artificial Intelligence, 2020, 33(2):121-132. doi: 10.16451/j.cnki.issn1003-6059.202002004
[24]	王亚东, 石全, 尤志锋, 等. 差分准对立学习多目标蚁狮算法[J]. 计算机工程与应用, 2020, 56(13):156-163. doi: 10.3778/j.issn.1002-8331.1903-0320
	WANG Yadong, SHI Quan, YOU Zhifeng, et al. Differential Evolutionary Quasi-Oppositional Multi-Objective Ant Lion Optimizer[J]. Computer Engineering and Applications, 2020, 56(13):156-163. doi: 10.3778/j.issn.1002-8331.1903-0320
[25]	傅文渊, 凌朝东. 自适应折叠混沌优化方法[J]. 西安交通大学学报, 2013, 47(2):33-38.
	FU Wenyuan, LING Chaodong. An Adaptive Iterative Chaos Optimization Method[J]. Journal of Xi'an Jiaotong University, 2013, 47(02):33-38.
[26]	DEB K, PRATAP A, AGARWAL S, et al. A Fast and Elitist Multiobjective Genetic Algorithm:NSGA-Ⅱ[J]. IEEE Transactions on Evolutionary Computation, 2002, 6(2):182-197. doi: 10.1109/4235.996017
[27]	COELLO C, LECHUGA M S. MOPSO:A Proposal for Multiple Objective Particle Swarm Optimization[C]//Congress on Evolutionary Computation. Piscataway: IEEE, 2002:1051-1056.
[28]	于建芳, 刘升, 韩斐斐, 等. 基于柯西变异的蚁狮优化算法[J]. 微电子学与计算机, 2019, 36(6):45-49.
	YU Jianfang, LIU Sheng, HAN Feifei, et al. Ant Lion Optimization Algorithm Based on Cauchy Variation[J]. Microelectronics & Computer, 2019, 36(6):45-49.

算法	ZDT1		ZDT2		ZDT3		ZDT4		ZDT6
算法	Mean	Std	Mean	Std	Mean	Std	Mean	Std	Mean	Std
NSGA-Ⅱ	0.068 5	0.045 2	0.195 7	0.078 1	0.046 7	0.031 3	0.127 7	0.098 5	0.032 9	0.020 4
MOPSO	0.016 0	0.016 7	0.017 9	0.016 9	0.040 2	0.045 4	0.371 2	0.214 1	0.008 8	0.003 7
MOALO	0.080 3	0.046 7	0.069 7	0.056 4	0.085 2	0.042 0	0.132 5	0.070 5	0.022 4	0.010 1
CMOALO	0.099 2	0.059 4	0.138 3	0.045 2	0.203 6	0.005 3	0.122 7	0.065 3	0.015 2	0.005 1
IMOALO	0.008 0	0.001 3	0.008 0	0.000 8	0.008 2	0.000 4	0.008 1	0.001 0	0.003 1	0.000 6

算法	ZDT1		ZDT2		ZDT3		ZDT4		ZDT6
算法	Mean	Std	Mean	Std	Mean	Std	Mean	Std	Mean	Std
NSGA-Ⅱ	0.002 7	0.001 4	0.000 5	0.000 2	0.001 9	0.002 1	0.006 5	0.005 3	0.004 2	0.002 8
MOPSO	0.000 5	0.000 5	0.002 0	0.002 3	0.000 7	0.000 5	0.003 6	0.003 4	0.010 1	0.006 1
MOALO	0.003 8	0.003 0	0.004 0	0.001 1	0.003 3	0.002 5	0.003 9	0.003 2	0.004 1	0.003 2
CMOALO	0.001 2	0.002 2	0.002 4	0.000 8	0.002 5	0.000 9	0.001 6	0.001 1	0.002 8	0.001 4
IMOALO	0.000 5	0.000 2	0.000 4	0.000 1	0.000 6	0.000 3	0.001 0	0.000 2	0.002 2	0.000 2

方案编号	目标函数1	目标函数2	方案编号	目标函数1	目标函数2	方案编号	目标函数1	目标函数2
1	0.034 8	0.019 2	11	0.327 9	0.010 5	21	0.502 7	0.005 8
2	0.035 9	0.017 9	12	0.330 3	0.010 0	22	0.511 9	0.005 7
3	0.036 9	0.017 5	13	0.332 5	0.009 8	23	0.514 9	0.005 6
4	0.037 3	0.017 2	14	0.370 8	0.009 7	24	0.515 4	0.005 6
5	0.037 9	0.016 9	15	0.372 5	0.009 6	25	0.516 9	0.005 5
6	0.131 8	0.014 3	16	0.375 7	0.009 5	26	0.521 4	0.005 5
7	0.210 4	0.013 0	17	0.441 3	0.007 4	27	0.522 2	0.005 4
8	0.258 9	0.012 2	18	0.471 6	0.006 8	28	0.526 3	0.005 3
9	0.272 7	0.012 0	19	0.480 3	0.006 5	29	0.554 7	0.004 1
10	0.327 4	0.010 6	20	0.497 3	0.006 1	30	0.555 0	0.004 0