改进的麻雀搜索算法优化无线传感器网络覆盖

doi:10.13229/j.cnki.jdxbgxb.20220566

摘要/Abstract

摘要：

针对麻雀搜索算法在高维复杂问题上由于随机性大而容易陷入局部最优的问题，提出了一种融合多策略改进的麻雀搜索算法。在初始化阶段，引入佳点集策略以确保种群具备多样性和遍历性。在发现者位置更新中，采用动态学习机制平衡全局寻优和局部探索；在跟随者位置更新中，引入莱维飞行扰动机制以增强局部逃逸能力。最后，将本文算法应用于解决无线传感器网络覆盖问题，从最大化覆盖率、最小化冗余和最大化能耗均衡3个角度对多目标覆盖优化问题进行抽象。仿真结果表明：3项改进措施显著提高了算法性能，增强了网络节点覆盖质量，使网络整体性能得到了有效提升，证明本文算法具备实际应用的良好性能。

关键词: 信息处理技术, 麻雀搜索算法, 无线传感器网络覆盖, 佳点集初始化, 动态学习机制, 莱维飞行策略

Abstract:

In response to the challenges of significant randomness and susceptibility to local optima in the sparrow search algorithm， an enhanced approach was proposed integrating multiple strategies. During the initialization phase， a good point set strategy was introduced to ensure population diversity and thorough exploration. The discoverer's position update incorporates a dynamic learning mechanism， effectively balancing global optimization and local exploration capabilities. Simultaneously， the follower's position update integrates a Lévy flight disturbance mechanism， reinforcing local escape capabilities. Finally, the proposed method was applied to solve the coverage problem of wireless sensor networks. Through a multi-objective coverage optimization function， considering coverage rate maximizing， redundancy minimization， and energy consumption equilibrium maximizing. The simulation results show that the three improvement measures significantly improve the algorithm performance, enhance the coverage quality of network nodes, and effectively improve the overall performance of the network, proving that the proposed method has good performance in practical applications.

Key words: information processing technology, sparrow search algorithm, wireless sensor network coverage, good point set initialization, dynamic learning mechanism, Lévy flight strategy

中图分类号:

TP301.6

段锦,姚安妮,王震,于林韬. 改进的麻雀搜索算法优化无线传感器网络覆盖[J]. 吉林大学学报(工学版), 2024, 54(3): 761-770.

Jin DUAN,An-ni YAO,Zhen WANG,Lin-tao YU. Improved sparrow search algorithm optimizes coverage in wireless sensor networks[J]. Journal of Jilin University(Engineering and Technology Edition), 2024, 54(3): 761-770.

图/表 9

表1

标准测试函数"

函数	维度	区间	最小值
$F 1 (x) = ∑ i = 1 n x i 2$	30	［-100，100］	0
$F 2 (x) = ∑ i = 1 n x i + ∏ i = 1 n x i$	30	［-10，10］	0
$F 3 (x) = ∑ i = 1 n ∑ j = 1 j x j 2$	30	［-100，100］	0
$F 4 (x) = m a x i {x i, 1 ≤ i ≤ n}$	30	［-100，100］	0
$F 5 (x) = ∑ i = 1 n - x i s i n (x i)$	30	［-500，500］	-418.982 9n
$F 6 (x) = ∑ i = 1 n [x i 2 - 10 c o s (2 π x i + 10)]$	30	［-5.12，5.12］	0
$F 7 (x) = - 20 e x p - 0.2 1 n ∑ i = 1 n x i 2 - e x p 1 n c o s (2 π x i) + 20 + e$	30	［-32，32］	0
$F 8 (x) = 14000 x i 2 - ∏ i = 1 n c o s x i i + 1$	30	［-600，600］	0
$F 9 (x) = 1500 + ∑ j = 1 25 1 j + ∑ i = 1 2 (x i - a i j) 6 - 1$	2	［-65，65］	1
$F 10 (x) = ∑ i = 1 11 a i - x 1 (b i 2 + b 1 x 2) b i 2 + b 1 x 3 + x 4 2$	4	［-5，5］	0.000 30
$F 11 (x) = - ∑ i = 1 4 c i e x p - ∑ j = 1 3 a i j (x j - p i j) 2$	3	［0，1］	-3.86
$F 12 (x) = - c i e x p - ∑ j = 1 6 a i j (x j - p i j) 2$	6	［0，1］	-3.32

表1

表2

各算法运行结果对比"

函数	指标	SSA	PSO	HPSOBOA	CSSA	GGSC-SSA	LOSSA	MSSA
$F 1 (x)$	最优值	3.1280×10^-28	1.0318×10^-18	2.5812×10^-152	1.1676×10^-136	5.5906×10^-48	6.1795×10^-206	0
	均值	2.5686×10^-27	1.0884×10^-15	3.7236×10^-152	5.2212×10^-24	1.9126×10^-24	7.6514×10^-171	0
	标准差	3.8704×10^-27	6.9952×10^-10	7.6134×10^-153	2.3350×10^-23	2.4460×10^-11	6.4150×10^-127	0
$F 2 (x)$	最优值	3.3588×10^-17	3.5539×10^-9	1.1843×10^-65	7.7504×10^-17	7.8221×10^-46	0	0
	均值	7.9059×10^-17	2.4834×10^-8	2.0909×10^-60	1.1937×10^-11	2.0384×10^-39	5.5227×10^-159	0
	标准差	5.4325×10^-17	6.9702×10^-9	4.9121×10^-60	9.5953×10^-9	3.2288×10^-39	2.8718×10^-125	0
$F 3 (x)$	最优值	8.5183×10^-14	5.1376×10^-11	4.8897×10^-42	1.3048×10^-23	1.4358×10^-42	1.2112×10^-153	0
	均值	3.6673×10^-10	6.2950×10^-11	2.3992×10^-40	4.7707×10^-21	7.7168×10^-41	9.6838×10^-153	0
	标准差	8.1535×10^-10	7.1649×10^-12	3.0600×10^-40	6.0171×10^-21	1.1485×10^-40	9.6854×10^-153	0
$F 4 (x)$	最优值	1.0952×10^-24	2.4150×10^-8	6.7690×10^-77	7.5195×10^-187	0	4.0623×10^-83	0
	均值	4.6230×10^-24	3.4641×10^-8	7.7480×10^-77	3.7362×10^-72	4.5282×10^-63	3.8551×10^-73	6.9195×10^-95
	标准差	2.9201×10^-24	4.5498×10^-9	4.4423×10^-78	1.7870×10^-28	2.0251×10^-62	1.6371×10^-72	3.3246×10^-94
$F 5 (x)$	最优值	-9.0084×10³	-1.1283×10⁴	-8.6938×10³	-1.2567×10⁴	-5.8572×10³	-6.1375×10³	-5.8370×10³
	均值	-7.7866×10³	-9.5521×10³	-7.8359×10³	-9.9582×10³	-5.7150×10³	-5.2542×10³	-5.7102×10³
	标准差	6.2266×10²	6.1018×10²	4.6312×10²	1.8645×10³	5.9340×10¹	4.8384×10²	5.0417×10¹
$F 6 (x)$	最优值	8.9966×10^-7	9.5861×10^-7	8.8818×10^-16	1.9619×10^-17	3.3527×10^-10	7.5495×10^-14	0
	均值	2.0152×10^-6	1.0313×10^-5	4.7962×10^-15	1.2669×10^-16	3.0957×10^-6	1.0427×10^-13	8.7599×10^-97
	标准差	3.2430×10^-6	7.5707×10^-6	1.9629×10^-15	1.0643×10^-16	6.1536×10^-6	2.3982×10^-14	4.7981×10^-96
$F 7 (x)$	最优值	7.8676×10^-3	2.0130×10^-7	6.9557×10^-77	1.2952×10^-63	5.6843×10^-14	0	0
	均值	1.8783×10^-1	9.1611×10^-7	7.9884×10^-77	2.1381×10^-2	3.9688×10⁰	3.2376×10^-124	0
	标准差	1.2376×10^-1	1.2528×10^-6	5.7556×10^-78	1.8596×10^-2	4.5810×10⁰	1.4479×10^-123	0
$F 8 (x)$	最优值	1.3511×10^-8	1.9957×10¹	7.9048×10^-14	7.9471×10^-16	4.7788×10^-9	1.0207×10^-154	0
	均值	2.6980×10^-8	1.9960×10¹	1.0321×10^-13	5.3496×10^-14	1.3191×10^-5	1.0583×10^-152	5.3828×10^-160
	标准差	6.7152×10^-9	1.3281×10^-3	1.3373×10^-14	3.3632×10^-12	3.6012×10^-5	1.7850×10^-152	3.1932×10^-29
$F 9 (x)$	最优值	7.2461×10⁰	5.8648×10⁰	2.7211×10⁰	4.5229×10⁰	6.6186×10⁰	4.9848×10⁰	1.0766×10⁰
	均值	2.8344×10¹	8.4747×10⁰	3.1967×10⁰	7.6200×10⁰	2.8141×10¹	5.5731×10⁰	1.3383×10⁰
	标准差	2.3867×10¹	1.3962×10¹	8.2469×10⁰	9.3611×10⁰	3.6313×10¹	4.3085×10⁰	1.3731×10⁰
$F 10 (x)$	最优值	1.2387×10^-3	2.8781×10^-2	6.6897×10^-4	7.8048×10-4	4.0457×10^-4	3.4319×10-4	3.0749×10^-4
	均值	1.3042×10^-3	1.7124×10¹	2.2611×10^-3	1.8059×10-3	9.7553×10^-4	1.3896×10-2	3.0753×10^-4
	标准差	4.6760×10^-5	3.1307×10¹	2.1081×10^-3	8.7924×10-4	5.9784×10^-4	2.5733×10-2	1.2408×10^-7
$F 11 (x)$	最优值	5.4531×10⁰	5.0159×10^-1	8.2930×10^-1	1.3786×10¹	3.3281×10^-1	-1.1432×10⁰	-3.8850×10⁰
	均值	1.1156×10¹	5.4681×10¹	2.9638×10⁰	1.8963×10¹	5.5429×10^-1	4.7936×10^-1	-2.8346×10⁰
	标准差	2.3658×10¹	1.9526×10²	4.3358×10¹	5.9687×10⁰	8.2673×10⁰	1.5948×10¹	4.5165×10^-1
$F 12 (x)$	最优值	-1.4302×10⁰	-1.0316×10⁰	-2.2453×10⁰	-2.7949×10⁰	-2.8326×10⁰	-3.2815×10⁰	-3.3220×10⁰
	均值	-1.2440×10⁰	-1.0313×10⁰	-2.5724×10⁰	-2.5596×10⁰	-2.6211×10⁰	-3.0063×10⁰	-3.2269×10⁰
	标准差	2.8702×10^-1	3.2148×10^-5	4.5623×10⁰	1.6497×10^-1	4.3392×10^-1	2.3553×10^-1	5.3171×10^-2

表2

图1

图2

图3

图4

图5

图6

表4

参考文献 26

1	Malik M, Joshi A, Sakya G. Network lifetime improvement for WSN using machine learning[C]∥2021 7th International Conference on Signal Processing and Communication (ICSC), Noida, India, 2021: 80-84.
2	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: 268-282.
3	Wu C, Fu X, Pei J, et al. A novel sparrow search algorithm for the traveling salesman problem[J]. IEEE Access, 2021, 9: 153456-153471.
4	Dorigo M, Maniezzo V, Colorni A. Ant system: optimization by a colony of cooperating agents[J]. IEEE Transactions on Systems, Man, and Cybernetics, 1996, 26(1): 29-41.
5	Eberhart, Shi Yu-hui.Particle swarm optimization: developments, applications and resources[C]∥Proceedings of the 2001 Congress on Evolutionary Computation, Seoul, Korea, 2001: 81-86.
6	Holland J H. Genetic algorithms[J]. Scientific American, 1992, 267(1): 66-73.
7	薛建凯. 一种新型的群智能优化技术的研究与应用:麻雀搜索算法[D]. 上海: 东华大学信息科学与技术学院, 2019.
	Xue Jian-kai. Research and application of a novel swarm intelligence optimization technique: sparrow search algorithm[D]. Shanghai: School of Information Science and Technology, Donghua University, 2019.
8	Xue J, Shen B. A novel swarm intelligence optimization approach:sparrow search algorithm[J]. Systems Science and Control Engineering, 2020, 8(1): 22-34.
9	Yang Y, Liu J, Wang Q, et al. Dynamic path planning for AGV based on Tent chaotic sparrow search algorithm[C]∥2021 International Conference on Information Control, Electrical Engineering and Rail Transit (ICEERT), Lanzhou, China, 2021: 100-104.
10	Zhang S, Zhang J, Wang Z, et al. Regression prediction of material grinding particle size based on improved sparrow search algorithm to optimize BP neural network[C]∥2021 2nd International Symposium on Computer Engineering and Intelligent Communications (ISCEIC), Nanjing, China, 2021: 216-219.
11	Chen H, Ma X, Huang S. A feature selection method for intrusion detection based on parallel sparrow search algorithm[C]∥2021 16th International Conference on Computer Science & Education (ICCSE), Lancaster, United Kingdom, 2021: 685-690.
12	Xu L, Wang H, Liu Y, et al. PID control for aeroengine based on sparrow search algorithm[C]∥2021 China Automation Congress (CAC), Beijing, China, 2021: 8327-8330
13	国强, 朱国会, 李万臣. 基于混沌麻雀搜索算法的TDOA/FDOA定位[J]. 吉林大学学报: 工学版, 2023, 53(2): 593-600.
	Guo Qiang, Zhu Guo-hui, Li Wan-chen. TDOA/FDOA localization based on chaotic sparrow search algorithm[J]. Journal of Jilin University (Engineering and Technology Edition), 2023, 53(2): 593-600.
14	Zhang C, Ding S. A stochastic configuration network based on chaotic sparrow search algorithm[J]. Knowledge-Based Systems, 2021, 220: No. 106924.
15	Yuan J, Zhao Z, Liu Y, et al. DMPPT control of photovoltaic Microgrid based on improved sparrow search algorithm[J]. IEEE Access, 2021, 9: 16623-16629.
16	Mirjalili S. Dragonfly algorithm: a new meta-heuristic optimization technique for solving single-objective, discrete, and multi-objective problems[J]. Neural Computing and Applications, 2016, 27(4): 1053-1073.
17	华罗庚, 王元. 数论在近代分析中的应用[M]. 北京:科学出版社, 1978: 1-99.
18	Kiefer J. On large deviations of the empiric D. F. of vector chance variables and a law of the iterated logarithm[J]. Pacific Journal of Mathematics, 1961, 11(2): 649-660.
19	Edwards A M, Phillips R A, Watkins N W, et al. Revisiting Lévy flight search patterns of wandering albatrosses, bumblebees and deer[J]. Nature, 2007, 449(7165): 1044-1048.
20	Wang X, Wang S, Ma J. An improved co-evolutionary particle swarm optimization for wireless sensor networks with dynamic deployment[J]. Sensors, 2007, 7(1): 354-370.
21	Ouyang C, Zhu D, Qiu Y.Lens learning sparrow search algorithm[J].Mathematical Problems in Engineering, 2021, 2021(2): 1-17.
22	Xia J. Coverage optimization strategy of wireless sensor network based on swarm intelligence algorithm[C]∥2016 International Conference on Smart City and Systems Engineering (ICSCSE), Hunan, China, 2016: 179-182.
23	贾润亮, 张海玉. 改进群体智能算法的无线传感器网络覆盖优化[J]. 西南大学学报: 自然科学版, 2024, 46(1): 155-166.
	Jia Run-liang, Zhang Hai-yu. Improved population intelligence algorithm for wireless sensor network coverage optimization[J]. Journal of Southwest University: Natural Science Edition, 2024, 46(1): 155-166.
24	王毅, 神显豪, 唐超尘, 等. 基于水波优化算法的无线传感器网络覆盖研究[J]. 南京理工大学学报, 2021, 45(6): 680-686.
	Wang Yi, Shen Xian-hao, Tang Chao-chen, et al. Research on wireless sensor network coverage based on water wave optimization algorithm[J]. Journal of Nanjing University of Science and Technology, 2021, 45(6): 680-686.
25	王振东, 汪嘉宝, 李大海. 一种增强型麻雀搜索算法的无线传感器网络覆盖优化研究[J]. 传感技术学报, 2021, 34(6): 818-828.
	Wang Zhen-dong, Wang Jia-bao, Li Da-hai. An enhanced sparrow search algorithm for coverage optimization of wireless sensor networks[J]. Journal of Sensing Technology, 2021, 34(6): 818-828.
26	Wang L, Wu W, Qi J, et al. Wireless sensor network coverage optimization based on whale group algorithm[J]. Computer Science and Information Systems, 2018, 15: No. 23.

Metrics

Viewed

Full text

Abstract

Cited

Shared

Discussed

算法	资源充裕	资源有限
SSA	79.85	65.84
MSSA	93.48	86.97
GGSC-SSA	82.49	71.32
CSSA	83.66	75.17
LOSSA	86.55	76.58

[1]	苏育挺,王骥,赵玮,井佩光. 基于动态图卷积的图像情感分布预测[J]. 吉林大学学报(工学版), 2023, 53(9): 2601-2610.
[2]	陈绵书,于录录,李晓妮,郑宏宇. 基于均匀ORB特征的回环检测算法[J]. 吉林大学学报(工学版), 2023, 53(9): 2666-2675.
[3]	国强,朱国会,李万臣. 基于混沌麻雀搜索算法的TDOA/FDOA定位[J]. 吉林大学学报(工学版), 2023, 53(2): 593-600.
[4]	王生生,李晨旭,王翔宇,姚志林,刘一申,吴佳倩,杨晴然. 基于改进残差胶囊网络和麻雀搜索的脑瘤图像分类[J]. 吉林大学学报(工学版), 2022, 52(11): 2653-2661.
[5]	蒋华伟,杨震,张鑫,董前林. 图像去雾算法研究进展[J]. 吉林大学学报(工学版), 2021, 51(4): 1169-1181.
[6]	李厚杰,王法胜,贺建军,周瑜,李威,窦宇轩. 基于伪样本正则化Faster R⁃CNN的交通标志检测[J]. 吉林大学学报(工学版), 2021, 51(4): 1251-1260.
[7]	王德兴,吴若有,袁红春,宫鹏,王越. 基于多尺度注意力融合和卷积神经网络的水下图像恢复[J]. 吉林大学学报(工学版), 2021, 51(4): 1396-1404.
[8]	金静,党建武,王阳萍,申东. 融合模糊统计纹理特征的多线索粒子滤波跟踪[J]. 吉林大学学报(工学版), 2021, 51(3): 1111-1120.
[9]	郭继昌,乔珊珊. 基于深度图的水下图像复原[J]. 吉林大学学报(工学版), 2021, 51(2): 677-684.
[10]	史再峰,李金卓,曹清洁,李慧龙,胡起星. 基于生成对抗网络的低剂量能谱层析成像去噪算法[J]. 吉林大学学报(工学版), 2020, 50(5): 1755-1764.
[11]	刘国华,周文斌. 基于卷积神经网络的脉搏波时频域特征混叠分类[J]. 吉林大学学报(工学版), 2020, 50(5): 1818-1825.
[12]	王柯俨,王迪,赵熹,陈静怡,李云松. 基于卷积神经网络的联合估计图像去雾算法[J]. 吉林大学学报(工学版), 2020, 50(5): 1771-1777.
[13]	谌华,郭伟,闫敬文,卓文浩,吴良斌. 基于深度学习的SAR图像道路识别新方法[J]. 吉林大学学报(工学版), 2020, 50(5): 1778-1787.
[14]	程艳芬,姚丽娟,袁巧,陈先桥. 水下视频图像清晰化方法[J]. 吉林大学学报(工学版), 2020, 50(2): 668-677.
[15]	张薇,韩勇,金铭,乔晓林. 基于托普利兹矩阵集重构的相干信源波达方向估计[J]. 吉林大学学报(工学版), 2020, 50(2): 703-710.