Journal of Jilin University(Engineering and Technology Edition) ›› 2024, Vol. 54 ›› Issue (3): 761-770.doi: 10.13229/j.cnki.jdxbgxb.20220566

Previous Articles    

Improved sparrow search algorithm optimizes coverage in wireless sensor networks

Jin DUAN(),An-ni YAO,Zhen WANG,Lin-tao YU   

  1. School of Electronic Information Engineering，Changchun University of Science and Technology，Changchun 130012，China
  • Received:2022-07-15 Online:2024-03-01 Published:2024-04-18

RICH HTML

 11   

PDF (PC)

363

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

CLC Number: 

  • TP301.6

Table 1

Standard test functions"

函 数维度区间最小值
F1(x)=∑i=1nxi230［-100，100］0
F2(x)=∑i=1nxi+∏i=1nxi30［-10，10］0
F3(x)=∑i=1n∑j=1jxj230［-100，100］0
F4(x)=maxi{xi,1≤i≤n}30［-100，100］0
F5(x)=∑i=1n-xisin(xi)30［-500，500］-418.982 9n
F6(x)=∑i=1n[xi2-10cos(2πxi+10)]30［-5.12，5.12］0
F7(x)=-20exp-0.21n∑i=1nxi2-exp1ncos(2πxi)+20+e30［-32，32］0
F8(x)=14000xi2-∏i=1ncosxii+130［-600，600］0
F9(x)=1500+∑j=1251j+∑i=12(xi-aij)6-12［-65，65］1
F10(x)=∑i=111ai-x1(bi2+b1x2)bi2+b1x3+x424［-5，5］0.000 30
F11(x)=-∑i=14ciexp-∑j=13aij(xj-pij)23［0，1］-3.86
F12(x)=-ciexp-∑j=16aij(xj-pij)26［0，1］-3.32

Table 2

Comparison of the running results of each algorithm"

函数指标SSAPSOHPSOBOACSSAGGSC-SSALOSSAMSSA
F1(x)最优值3.1280×10-281.0318×10-182.5812×10-1521.1676×10-1365.5906×10-486.1795×10-2060
均值2.5686×10-271.0884×10-153.7236×10-1525.2212×10-241.9126×10-247.6514×10-1710
标准差3.8704×10-276.9952×10-107.6134×10-1532.3350×10-232.4460×10-116.4150×10-1270
F2(x)最优值3.3588×10-173.5539×10-91.1843×10-657.7504×10-177.8221×10-4600
均值7.9059×10-172.4834×10-82.0909×10-601.1937×10-112.0384×10-395.5227×10-1590
标准差5.4325×10-176.9702×10-94.9121×10-609.5953×10-93.2288×10-392.8718×10-1250
F3(x)最优值8.5183×10-145.1376×10-114.8897×10-421.3048×10-231.4358×10-421.2112×10-1530
均值3.6673×10-106.2950×10-112.3992×10-404.7707×10-217.7168×10-419.6838×10-1530
标准差8.1535×10-107.1649×10-123.0600×10-406.0171×10-211.1485×10-409.6854×10-1530
F4(x)最优值1.0952×10-242.4150×10-86.7690×10-777.5195×10-18704.0623×10-830
均值4.6230×10-243.4641×10-87.7480×10-773.7362×10-724.5282×10-633.8551×10-736.9195×10-95
标准差2.9201×10-244.5498×10-94.4423×10-781.7870×10-282.0251×10-621.6371×10-723.3246×10-94
F5(x)最优值-9.0084×103-1.1283×104-8.6938×103-1.2567×104-5.8572×103-6.1375×103-5.8370×103
均值-7.7866×103-9.5521×103-7.8359×103-9.9582×103-5.7150×103-5.2542×103-5.7102×103
标准差6.2266×1026.1018×1024.6312×1021.8645×1035.9340×1014.8384×1025.0417×101
F6(x)最优值8.9966×10-79.5861×10-78.8818×10-161.9619×10-173.3527×10-107.5495×10-140
均值2.0152×10-61.0313×10-54.7962×10-151.2669×10-163.0957×10-61.0427×10-138.7599×10-97
标准差3.2430×10-67.5707×10-61.9629×10-151.0643×10-166.1536×10-62.3982×10-144.7981×10-96
F7(x)最优值7.8676×10-32.0130×10-76.9557×10-771.2952×10-635.6843×10-1400
均值1.8783×10-19.1611×10-77.9884×10-772.1381×10-23.9688×1003.2376×10-1240
标准差1.2376×10-11.2528×10-65.7556×10-781.8596×10-24.5810×1001.4479×10-1230
F8(x)最优值1.3511×10-81.9957×1017.9048×10-147.9471×10-164.7788×10-91.0207×10-1540
均值2.6980×10-81.9960×1011.0321×10-135.3496×10-141.3191×10-51.0583×10-1525.3828×10-160
标准差6.7152×10-91.3281×10-31.3373×10-143.3632×10-123.6012×10-51.7850×10-1523.1932×10-29
F9(x)最优值7.2461×1005.8648×1002.7211×1004.5229×1006.6186×1004.9848×1001.0766×100
均值2.8344×1018.4747×1003.1967×1007.6200×1002.8141×1015.5731×1001.3383×100
标准差2.3867×1011.3962×1018.2469×1009.3611×1003.6313×1014.3085×1001.3731×100
F10(x)最优值1.2387×10-32.8781×10-26.6897×10-47.8048×10-44.0457×10-43.4319×10-43.0749×10-4
均值1.3042×10-31.7124×1012.2611×10-31.8059×10-39.7553×10-41.3896×10-23.0753×10-4
标准差4.6760×10-53.1307×1012.1081×10-38.7924×10-45.9784×10-42.5733×10-21.2408×10-7
F11(x)最优值5.4531×1005.0159×10-18.2930×10-11.3786×1013.3281×10-1-1.1432×100-3.8850×100
均值1.1156×1015.4681×1012.9638×1001.8963×1015.5429×10-14.7936×10-1-2.8346×100
标准差2.3658×1011.9526×1024.3358×1015.9687×1008.2673×1001.5948×1014.5165×10-1
F12(x)最优值-1.4302×100-1.0316×100-2.2453×100-2.7949×100-2.8326×100-3.2815×100-3.3220×100
均值-1.2440×100-1.0313×100-2.5724×100-2.5596×100-2.6211×100-3.0063×100-3.2269×100
标准差2.8702×10-13.2148×10-54.5623×1001.6497×10-14.3392×10-12.3553×10-15.3171×10-2

Fig.1

Convergence curves of each algorithm （partial）"

Fig.2

MSSA algorithms optimize coverage of sensor networks"

Fig.3

LOSSA algorithms optimize coverage of sensor networks"

Fig.4

CSSA algorithms optimize coverage of sensor networks"

Fig.5

GGSC-SSA algorithms optimize coverage of sensor networks"

Fig.6

SSA algorithms optimize coverage of sensor networks"

Table 4

Comparison of coverage results between the original algorithm and the improved algorithm"

算法资源充裕资源有限
SSA79.8565.84
MSSA93.4886.97
GGSC-SSA82.4971.32
CSSA83.6675.17
LOSSA86.5576.58
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.
[1] Yu-ting SU,Ji WANG,Wei ZHAO,Pei-guang JING. Dynamic graph convolutional neural network for image sentiment distribution prediction [J]. Journal of Jilin University(Engineering and Technology Edition), 2023, 53(9): 2601-2610.
[2] Mian-shu CHEN,Lu-lu YU,Xiao-ni LI,Hong-yu ZHENG. Loop detection based on uniform ORB [J]. Journal of Jilin University(Engineering and Technology Edition), 2023, 53(9): 2666-2675.
[3] Qiang GUO,Guo-hui ZHU,Wan-chen LI. TDOA/FDOA localization based on chaotic sparrow search algorithm [J]. Journal of Jilin University(Engineering and Technology Edition), 2023, 53(2): 593-600.
[4] Sheng-sheng WANG,Chen-xu LI,Xiang-yu WANG,Zhi-lin YAO,Yi-shen LIU,Jia-qian WU,Qing-ran YANG. Brain tumor image classification based on improved residual capsule network and sparrow search [J]. Journal of Jilin University(Engineering and Technology Edition), 2022, 52(11): 2653-2661.
[5] Hua-wei JIANG,Zhen YANG,Xin ZHANG,Qian-lin DONG. Research progress of image dehazing algorithms [J]. Journal of Jilin University(Engineering and Technology Edition), 2021, 51(4): 1169-1181.
[6] Hou⁃jie LI,Fa⁃sheng WANG,Jian⁃jun HE,Yu ZHOU,Wei LI,Yu⁃xuan DOU. Pseudo sample regularization Faster R⁃CNN for traffic sign detection [J]. Journal of Jilin University(Engineering and Technology Edition), 2021, 51(4): 1251-1260.
[7] De-xing WANG,Ruo-you WU,Hong-chun YUAN,Peng GONG,Yue WANG. Underwater image restoration based on multi-scale attention fusion and convolutional neural network [J]. Journal of Jilin University(Engineering and Technology Edition), 2021, 51(4): 1396-1404.
[8] Jing JIN,Jian-wu DANG,Yang-ping WANG,Dong SHEN. Multi⁃cue particle filter tracking based on fuzzy statistical texture features [J]. Journal of Jilin University(Engineering and Technology Edition), 2021, 51(3): 1111-1120.
[9] Zai-feng SHI,Jin-zhuo LI,Qing-jie CAO,Hui-long LI,Qi-xing HU. Low⁃dose spectral computer⁃tomography imaging denoising method via a generative adversarial network [J]. Journal of Jilin University(Engineering and Technology Edition), 2020, 50(5): 1755-1764.
[10] Guo-hua LIU,Wen-bin ZHOU. Pulse wave signal classification algorithm based on time⁃frequency domain feature aliasing using convolutional neural network [J]. Journal of Jilin University(Engineering and Technology Edition), 2020, 50(5): 1818-1825.
[11] Ke-yan WANG,Di WANG,Xi ZHAO,Jing-yi CHEN,Yun-song LI. Image dehazing based on joint estimation via convolutional neural network [J]. Journal of Jilin University(Engineering and Technology Edition), 2020, 50(5): 1771-1777.
[12] Hua CHEN,Wei GUO,Jing-wen YAN,Wen-hao ZHUO,Liang-bin WU. A new deep learning method for roads recognition from SAR images [J]. Journal of Jilin University(Engineering and Technology Edition), 2020, 50(5): 1778-1787.
[13] Yan-fen CHENG,Li-juan YAO,Qiao YUAN,Xian-qiao CHEN. Clearing strategy of underwater video image [J]. Journal of Jilin University(Engineering and Technology Edition), 2020, 50(2): 668-677.
[14] Wei ZHANG,Yong HAN,Ming JIN,Xiao-lin QIAO. Toeplitz matrices reconstruction based DOA estimation for coherent signals [J]. Journal of Jilin University(Engineering and Technology Edition), 2020, 50(2): 703-710.
[15] Fu LIU, Mei-jing QUAN, Ke WANG, Yun LIU, Bing KANG, Zhi-wu HAN, Tao HOU. Indoor positioning method based on location fingerprinting of imitating mechanism of scorpion vibration source [J]. Journal of Jilin University(Engineering and Technology Edition), 2019, 49(6): 2076-2082.
Viewed
Full text


Abstract

Cited
  Shared   
  Discussed   
No Suggested Reading articles found!
Copyright © Journal of Jilin University(Engineering and Technology Edition), All Rights Reserved.
Tel: +86-431-85095297　Fax: +86-431-85094074　E-mail: xbgxb@jlu.edu.cn
Powered by Beijing Magtech Co. Ltd