改进NSGA-II算法及监测天线部署优化研究

doi:10.19665/j.issn1001-2400.2021.05.027

摘要/Abstract

摘要：

为求解地面电磁辐射源监测天线的最佳部署位置,以达到准确监测、高效部署的目的,构建了以最大化覆盖率、最小化冗余率和未被覆盖障碍物数量为目标,以天线间保持连通性为约束条件的多目标优化模型。通过判断每两个障碍物之间的距离与天线工作覆盖范围最大半径的大小关系预设参考点作为若干天线部署位置;通过仿真比较了不同障碍物数量和参考点数量对覆盖率、冗余率等部署效率的影响,验证了障碍物数量对冗余率的影响更大,以增加冗余率为代价可减少天线覆盖区域内的障碍物数量。利用内存存储前几代非支配解的方法改进NSGA-II算法,在改变环境后可以更快地求得新的最优解,提高收敛速度。对模型和改进后的算法进行了仿真分析,结果表明迭代速度平均提高了30%以上,平均迭代一次的时间减少了25%以上,验证了改进算法响应动态变化的有效性;通过算法评价指标mIGDB验证了改进算法的收敛性和多样性。

关键词: 多目标优化, 天线部署, 改进NSGA-II算法, 预设参考点, 电磁辐射源监测

Abstract:

In order to solve the optimum deployment location of the ground radiation monitoring antenna to achieve accurate monitoring and efficient deployment,a multi-objective optimization model is constructed to maximize the coverage rate,minimize the redundancy rate and the number of uncovered obstacles.And the model is constrained by communication between antennas.By comparing the relationship between the distance between two obstacles and the maximum radius of the antenna's working coverge range,the reference points are preset as the antenna deployment location.The effects of the number of obstacles and the number of reference points on the deployment efficiency such as coverage rate and redundancy rate are compared by simulation.It is verified that the number of obstacles has a greater effect on the redundancy rate,and that the number of obstacles in the antenna coverage area is reduced at the expense of the increased redundancy rate.The second generation of the non-dominant sorting genetic (NSGA-II) algorithm is improved by using the memory to store the previous generations of non-dominant solutions.After changing the environment,the new optimal solution can be obtained faster and the convergence speed can be improved.The simulation results of the model and the improved algorithm show that the iteration speed is increased by more than 30% on average,and that the average iteration time is reduced by more than 25%,which verifies the effectiveness of the improved algorithm in response to dynamic changes.The convergence and diversity of the improved algorithm are verified by the algorithm evaluation index mIGDB.

Key words: multi-objective optimization, sensors deployment, improved NSGA-II algorithm, preset reference point, electromagnetic radiation source monitoring

中图分类号:

TN92

杜文占,余志勇,杨剑,姜海滨. 改进NSGA-II算法及监测天线部署优化研究[J]. 西安电子科技大学学报, 2021, 48(5): 239-248.

DU Wenzhan,YU Zhiyong,YANG Jian,JIANG Haibin. Improved NSGA-II algorithm and research on monitoring antenna optimization deployment[J]. Journal of Xidian University, 2021, 48(5): 239-248.

图/表 13

图1

图2

图3

图4

图5

图6

表1

图7

表2

部署结果数据"

障碍物数量	K=6		K=7
障碍物数量	C=4	C=2	C=4
O/%	93.89	97.33	91.06
ρ/%	18.10	15.82	27.94
部署效率/(m²·个^-1)	21 339	22 120	20 695
$l -$ /m	165.15	164.81	131.91
未被覆盖障碍物/个	5	3	4
平均时间/s	1 197.4	1 416.9	892.9

表2

图8

图9

图10

表3

参考文献 16

[1]	MALON K, SKOKOWSKI P, LOPATKA J. Optimization of Wireless Sensor Network Deployment for Electromagnetic Situation Monitoring[J]. International Journal of Microwave and Wireless Technologies, 2018, 10(7):746-753. doi: 10.1017/S1759078718000211
[2]	CAO B, ZHAO J W, YANG P, et al. 3-D Deployment Optimization for Heterogeneous Wireless Directional Sensor Networks on Smart City[J]. IEEE Transactions on Industrial Informatics, 2019, 15(3):1798-1808. doi: 10.1109/TII.2018.2884951
[3]	徐英, 周尚武. 电磁环境监测传感器部署效率评估方法[J]. 装备环境工程, 2018, 15(4):51-55.
	XU Ying, ZHOU Shangwu. Evaluation Method for Deployment Efficiency of Electromagnetic Environmental Monitoring Sensor[J]. Equipment Environmental Engineering, 2018, 15(4):51-55.
[4]	陈涛, 何聪. 基于GIS的网格化监测定位传感器节点优化部署策略研究[J]. 通信技术, 2019, 52(12):2950-2955.
	CHEN Tao, HE Cong. The Optimal Deployment Strategy of Grid Monitoring and Positioning Sensor Nodes Based on GIS[J]. Communications Technology, 2019, 52(12):2950-2955.
[5]	葛云露, 董俊, 姬生云, 等. 电磁频谱监测设备部署优化算法[J]. 电波科学学报, 2014, 29(2):353-357.
	GE Yunlu, DONG Jun, JI Shengyun, et al. Deployment Optimization Algorithm for Electromagnetic Spectrum Monitoring Equipment[J]. Chinese Journal of Radio Science, 2014, 29(2):353-357.
[6]	任淑婷, 刘海波, 张竞文. 基于改进遗传算法的频谱监测系统规划研究[J]. 通信技术, 2018, 51(12):2897-2904.
	REN Shuting, LIU Haibo, ZHANG Jingwen. Spectrum Monitoring System Planning Based on Improved Genetic Algorithm[J]. Communications Technology, 2018, 51(12):2897-2904.
[7]	陈立鹏. 基于NSGA-III改进的动态多目标优化算法及其应用[D]. 沈阳:东北大学, 2015.
[8]	HE D, LIANG G, PORTILLA J, et al. A Novel Method for Radio Propagation Simulation Based on Automatic 3D Environment Reconstruction[C]// Proceedings of the 2012 6th European Conference on Antennas and Propagation (EUCAP).Piscataway:IEEE, 2012:1445-1449.
[9]	RAJKUMARI R, MARCHANG N. Binary Decision-Based Collaborative Spectrum Sensing in Infrastructure-Less Cognitive Radio Network[J]. Annals of Telecommunications -Annales des Télécommunications, 2018, 73(11-12):677-688.
[10]	DEB K, PRATAP A, AGARWAL S, et al. A Fast and Elitist Multiobjective Genetic Algorithm:NSGA-II[J]. IEEE Transactions on Evolutionary Computation, 2002, 6(2):182-197. doi: 10.1109/4235.996017
[11]	DEB K, JAIN H. An Evolutionary Many-Objective Optimization Algorithm Using Reference-Point-Based Nondominated Sorting Approach,Part I:Solving Problems With Box Constraints[J]. IEEE Transactions on Evolutionary Computation, 2014, 18(4):577-601. doi: 10.1109/TEVC.2013.2281535
[12]	庞善天, 陈基漓, 谢晓兰. 基于参考点拥挤度改进的NSGAIII算法[J]. 计算机工程与设计, 2019, 40(6):1626-1633.
	PANG Shantian, CHEN Jili, XIE Xiaolan. Improved NSGAIII Algorithm based on Congestion of Reference Points[J]. Computer Engineering and Design, 2019, 40(6):1626-1633.
[13]	石露露. 动态多目标优化进化算法研究[D]. 西安:西安电子科技大学, 2019.
[14]	LIU Q X, DU S Z, WYK B J V, et al. Niching Particle Swarm Optimization based on Euclidean Distance and Hierarchical Clustering for Multimodal Optimization[J]. Nonlinear Dynamics, 2020, 99(3):2459-2477. doi: 10.1007/s11071-019-05414-7
[15]	SAHMOUD S, TOPCUOGLU H R. A Memory-Based NSGA-II Algorithm for Dynamic Multi-Objective Optimization Problems[C]// Proceedings of the 19th European Conference on the Applications of Evolutionary Computation.Heidelberg:Springer, 2016:296-310.
[16]	TIAN Y, CHENG R, ZHANG X Y, et al. PlatEMO:A MATLAB Platform for Evolutionary Multi-Objective Optimization[J]. IEEE Computational Intelligence Magazine, 2017, 12(4):73-87.

输入参数	数值
ROI/m²	500×500
M/个	11
R/m	100
l_max/m	200
K	6
种群大小	100
迭代次数	100
x	5

算法	K=6,C=4	K=6,C=2	K=7,C=4	K=6,C=4
算法	MB-NSGA-II	MB-NSGA-II	MB-NSGA-II	NSGA-II
X	67	74	43	95
t/s	1 197.4	1 416.9	892.9	1 779.6