基于改良麻雀搜索优化的WSN节点部署策略

刘睿; 莫愿斌; 荆彩

doi:10.19304/J.ISSN1000-7180.2021.1015

基于改良麻雀搜索优化的WSN节点部署策略

doi: 10.19304/J.ISSN1000-7180.2021.1015

刘睿¹,
莫愿斌^{2, 3, ,},
荆彩²

基金项目:

国家自然科学基金项目 21466008

广西自然科学基金项目 2019GXNSFAA185017

详细信息

作者简介:
刘睿男，(1996-)，硕士研究生.研究方向为智能信息控制

荆彩女，(2000-)，硕士研究生.研究方向为智能信息控制

通讯作者:
莫愿斌(通讯作者) 男，(1969-)，博士，教授.研究方向为智能计算.E-mail: 674148582@qq.com

中图分类号: TP393
计量
- 文章访问数: 8
- HTML全文浏览量: 4
- PDF下载量: 0
- 被引次数: 0
出版历程
- 收稿日期: 2021-08-12
- 修回日期: 2021-09-07
- 网络出版日期: 2022-05-12

Deployment strategy of wireless sensor network based on reformative sparrow search algorithm

LIU Rui¹,
MO Yuanbin^{2, 3
, ,},
JING Cai²

摘要

摘要:
覆盖问题是无线传感器网络(Wireless Sensor Network, WSN)设计中的首要问题，尽可能优化区域覆盖率是提升网络感知性能的直接手段.鉴于此，提出一种基于改良型麻雀搜索算法(Reformative Sparrow Search Algorithm, RSSA)的节点部署优化方案.首先，在算法搜索阶段，RSSA通过引入正余弦指引机制替换原算法位置更新模式，改善算法的遍历性；其次，利用Lévy随机步长特性为算法加入停滞扰动机制，使RSSA具备更强的抗局部极值能力；同时，采用更为契合实际的概率感知模型检测节点的覆盖状态，在迭代更新过程中对比替换更优节点集，从而获得区域覆盖率的提升.为验证改良算法的寻优效果，使用6组通用的基准函数对RSSA进行性能测试，并与三种不同算法进行对比，结果表明RSSA具有良好的优化性能.最后，将RSSA应用于两组WSN节点部署优化实例.对比不同文献中的覆盖优化算法，使用所提算法RSSA优化节点部署最高可取得99.99%的覆盖率，并且使区域内节点呈现均匀化分布，在保证较高覆盖率要求的同时使用了更少的节点，减少了节点冗余，降低了整体网络系统的部署成本.
- 无线传感器网络 /
- 节点部署 /
- 覆盖率 /
- 麻雀搜索算法 /
- 部署成本
Abstract:
Coverage problem is the most important issue in the design of Wireless Sensor Network (WSN), optimizing regional coverage rate as much as possible is a direct means to improve network sensing performance. In view of this, a node deployment optimization scheme based on Reformative Sparrow Search Algorithm (RSSA) is proposed. Firstly, in the search phase, RSSA improves the ergodicity of the algorithm by introducing the sine cosine guidance mechanism to replace the location update mode of the original algorithm. Secondly, the stagnation disturbance mechanism is added to the algorithm by using the characteristics of Lévy random step size, so that RSSA has stronger ability to resist local extremum. At the same time, a more practical probability perception model is used to detect the coverage state of nodes, and a better node set is compared and replaced in the iterative update process, so as to improve the regional coverage. In order to verify the optimization effect of the reformative algorithm, six groups of general benchmark functions are used to test the performance of RSSA, and compared with three different algorithms. The results show that RSSA has good optimization performance. Finally, RSSA is applied to two groups of WSN node deployment optimization examples, and the coverage optimization algorithms in different literatures are compared. Using the proposed algorithm RSSA to optimize node deployment can achieve a maximum coverage of 99.99%, and make the nodes in the region present a uniform distribution. While ensuring high coverage requirements, fewer nodes are used, which reduces node redundancy and reduces the deployment cost of the overall network system.
- Wireless Sensor Network /
- node deployment /
- coverage rate /
- Sparrow Search Algorithm /
- deployment cost

HTML全文

图 1 改良型麻雀搜索算法流程图

Figure 1. Reformative Sparrow Search Algorithm flow

下载: 全尺寸图片幻灯片

图 2 基准函数

Figure 2. Benchmark functions

下载: 全尺寸图片幻灯片

图 3 四种算法在基准函数上的收敛曲线对比

Figure 3. Comparison of convergence curves of 4 algorithms obtained on the benchmark functions

下载: 全尺寸图片幻灯片

图 4 实例一RSSA优化节点分布

Figure 4. RSSA optimized nodes distribution in Experiment 1

下载: 全尺寸图片幻灯片

图 5 两种节点数量下的覆盖率优化曲线

Figure 5. Coverage rate optimization curve under two node numbers

下载: 全尺寸图片幻灯片

图 6 实例二RSSA优化节点分布

Figure 6. RSSA optimized nodes distribution in Experiment 2

下载: 全尺寸图片幻灯片

图 7 四种节点数量下的覆盖率优化曲线

Figure 7. Coverage rate optimization curve under four node numbers

下载: 全尺寸图片幻灯片

表 1 详细参数设置

Table 1. Detailed parameter settings

Algorithm	Parameter setting
PSO	c₁=c₂=1.49445, ω=0.729
SCASL	α=0.05, β=0.5, a=2
SSA	ST=0.8, PD=0.2, SD=0.1
RSSA	ST=0.8, PD=0.2, SD=0.1

下载: 导出CSV

表 2 基准函数信息

Table 2. Benchmark function information

Benchmark function	Formula	d	Range	Opt
Sphere Model	$ {{f}_{1}}\left( x \right)=\sum\limits_{i=1}^{n}{{}}{{x}_{i}}^{2}$	30	[-100, 100]	0
Schwefel’s problem 2.22	$ {{f}_{2}}\left( x \right)=\sum\limits_{i=1}^{n}{{}}\left\| {{x}_{i}} \right\|+\prod\limits_{i=1}^{n}{{}}\left\| {{x}_{i}} \right\|$	30	[-10, 10]	0
Schwefel’s problem 1.2	$ {{f}_{3}}\left( x \right)=\sum\limits_{i=1}^{n}{{}}{{\left( \sum\limits_{j=1}^{i}{{}}{{x}_{j}} \right)}^{2}}$	30	[-100, 100]	0
Schwefel’s problem 2.21	$ {{f_4}\left( x \right) = {\rm{ma}}{{\rm{x}}_i}\left\{ {\left\| {{x_i}} \right\|, 1 \le i \le n} \right\}}$	30	[-100, 100]	0
Generalized Schwefel’s problem 2.26	$ {f_5}\left( x \right) = \sum\limits_{i = 1}^n {} - {x_i}{\rm{sin}}\sqrt {\left\| {{x_i}} \right\|} $	30	[-500, 500]	-418.982n
Ackley’s Function	$ {f_6}\left( x \right) = - 20{\rm{exp}}\left( { - 0.2\sqrt {\frac{1}{n}\sum\limits_{i = 1}^n {} {x_i}^2} } \right) - {\rm{exp}}\left( {\frac{1}{n}\sum\limits_{i = 1}^n {} {\rm{cos}}\left( {2\pi {x_i}} \right)} \right) + 20 + e$	30	[-32, 32]	0

下载: 导出CSV

表 3 基准函数优化结果

Table 3. Benchmark function optimization results

F	PSO		SCASL		SSA		RSSA
F	Mean	Std	Mean	Std	Mean	Std	Mean	Std
f₁	5.08e-10	1.73e-09	2.97e-149	1.76e-149	6.02e-52	3.56e-52	0	0
f₂	1.51e-01	4.93e-01	2.39e-72	2.95e-72	8.71e-28	1.19e-28	3.96e-143	1.48e-144
f₃	1.72e-01	4.43e-01	9.40e-105	5.57e-105	2.52e-50	1.17e-50	2.77e-247	0
f₄	2.66	2.32e-01	1.32e-61	5.26e-61	2.06e-35	8.63e-35	1.30e-148	1.07e-148
f₅	-7.65e+03	787.51	-3.61e+03	377.69	-6.29e+03	682.61	-1.24e+04	667.28
f₆	2.12	1.46	8.88e-16	0	8.88e-16	0	8.88e-16	0

下载: 导出CSV

表 4 算法运行时间

Table 4. The running time of algorithm

F	最短运行时间/s		最长运行时间/s		平均运行时间/s
F	SSA	RSSA	SSA	RSSA	SSA	RSSA
f₁	0.226 3	0.073 9	0.295 2	0.104 7	0.258 7	0.090 5
f₂	0.243 1	0.089 6	0.304 4	0.120 2	0.267 4	0.096 7
f₃	0.320 2	0.179 4	0.433 1	0.225 2	0.387 3	0.190 2
f₄	0.246 2	0.086 6	0.308 6	0.106 4	0.267 7	0.097 6
f₅	0.252 3	0.100 6	0.316 2	0.152 9	0.287 3	0.112 8
f₆	0.237 3	0.097 7	0.322 8	0.121 4	0.283 9	0.107 6

下载: 导出CSV

表 5 实例一中算法优化覆盖率结果对比

Table 5. Comparison of optimized coverage results of each algorithm in Experiment 1

Algorithm	Coverage rate /%
Algorithm	V=20	V=16
VFPSO	98.01	N/A
ESCA	99.56	98.04
RSSA	99.99	99.07

下载: 导出CSV

表 6 实例二中算法优化覆盖率结果对比

Table 6. Comparison of optimized coverage results of each algorithm in Experiment 2

Algorithm	Coverage rate /%
Algorithm	V=50	V=46	V=40	V=36
EABC	90.86	90.86	N/A	N/A
ESCA	98.58	97.26	91.02	N/A
RSSA	99.26	97.91	96.32	93.73

下载: 导出CSV

参考文献(20)

[1]	张贵相, 钟艺, 张春. 基于视觉的触觉传感器信号处理电路设计[J]. 微电子学与计算机, 2016, 33(2): 18-21. DOI: 10.19304/j.cnki.issn1000-7180.2016.02.004. ZHANG G X, ZHONG Y, ZHANG C. Signal processing circuit for vision-based tactile sensor[J]. Microelectronics & Computer, 2016, 33(2): 18-21. DOI: 10.19304/j.cnki.issn1000-7180.2016.02.004.
[2]	宁宇, 彭佑多, 颜健. 一种大范围光电跟踪传感器的实验研究[J]. 激光与光电子学进展, 2019, 56(1): 012801. DOI: 10.3788/LOP56.012801. NING Y, PENG Y D, YAN J. Experimental study of wide range photoelectric tracking sensors[J]. Laser & Optoelectronics Progress, 2019, 56(1): 012801. DOI: 10.3788/LOP56.012801.
[3]	AGUIRRE E, LOPEZ-ITURRI P, AZPILICUETA L, et al. Design and implementation of context aware applications with wireless sensor network support in urban train transportation environments[J]. IEEE Sensors Journal, 2017, 17(1): 169-178. DOI: 10.1109/JSEN.2016.2624739.
[4]	ALAIAD A, ZHOU L N. Patients' adoption of WSN-based smart home healthcare systems: an integrated model of facilitators and barriers[J]. IEEE Transactions on Professional Communication, 2017, 60(1): 4-23. DOI: 10.1109/TPC.2016.2632822.
[5]	ADAME T, BEL A, CARRERAS A, et al. CUIDATS: An RFID-WSNhybrid monitoring system for smart health care environments[J]. Future Generation Computer Systems, 2018, 78: 602-615. DOI: 10.1016/j.future.2016.12.023.
[6]	JIA J, JIAN C, DENG Y S, et al. Joint power charging and routing in wireless rechargeable sensor networks[J]. Sensors, 2017, 17(10): 2290. DOI: 10.3390/s17102290.
[7]	陈贵宝, 郭仲杰, 李婷, 等. 一种高精度CMOS温度传感器的设计[J]. 微电子学与计算机, 2019, 36(8): 34-38. DOI: 10.19304/j.cnki.issn1000-7180.2019.08.008. CHEN G B, GUO Z J, LI T, et al. Design of a high accuracy CMOS temperature sensor[J]. Microelectronics & Computer, 2019, 36(8): 34-38. DOI: 10.19304/j.cnki.issn1000-7180.2019.08.008.
[8]	黄颖, 费莉, 赖小龙. 带有隐私保护的无线传感网能量有效数据融合机制[J]. 微电子学与计算机, 2019, 36(7): 65-69. DOI: 10.19304/j.cnki.issn1000-7180.2019.07.013. HUANG Y, FEI L, LAI X L. Energy-efficient wireless sensor network data fusion mechanism with privacy protection method[J]. Microelectronics & Computer, 2019, 36(7): 65-69. DOI: 10.19304/j.cnki.issn1000-7180.2019.07.013.
[9]	蒋华, 蔡振海, 王鑫. 基于蚁群的水下无线传感器网络能量路由协议[J]. 微电子学与计算机, 2017, 34(8): 12-16. DOI: 10.19304/j.cnki.issn1000-7180.2017.08.003. JIANG H, CAI Z H, WANG X. Energy routing protocol for underwater wireless sensor networks based on ant colony[J]. Microelectronics & Computer, 2017, 34(8): 12-16. DOI: 10.19304/j.cnki.issn1000-7180.2017.08.003.
[10]	张涛, 周晨蕾, 李海龙, 等. 声表面波煤矿瓦斯传感器声光报警系统的设计与制备[J]. 微电子学与计算机, 2015, 32(12): 122-125. DOI: 10.19304/j.cnki.issn1000-7180.2015.12.026. ZHANG T, ZHOU C L, LI H L, et al. The sound and light alarm circuit design for surface acoustic wave methane sensor[J]. Microelectronics & Computer, 2015, 32(12): 122-125. DOI: 10.19304/j.cnki.issn1000-7180.2015.12.026.
[11]	何庆, 徐钦帅, 魏康园. 基于改进正弦余弦算法的无线传感器节点部署优化[J]. 计算机应用, 2019, 39(7): 2035-2043. DOI: 10.11772/j.issn.1001-9081.2018112282. HE Q, XU Q S, WEI K Y. Enhanced sine cosine algorithm based node deployment optimization of wireless sensor network[J]. Journal of Computer Applications, 2019, 39(7): 2035-2043. DOI: 10.11772/j.issn.1001-9081.2018112282.
[12]	宋明智, 杨乐. 改进VFPSO算法于WSN节点随机部署中的应用[J]. 计算机工程与应用, 2016, 52(2): 141-145. DOI: 10.3778/j.issn.1002-8331.1401-0265. SONG M Z, YANG L. Random deployment of sensor nodes using enhanced VFPSO algorithm[J]. Computer Engineering and Applications, 2016, 52(2): 141-145. DOI: 10.3778/j.issn.1002-8331.1401-0265.
[13]	于文杰, 李迅波, 羊行, 等. 外推人工蜂群算法在WSN部署优化中的应用研究[J]. 仪表技术与传感器, 2017(6): 158-160. DOI: 10.3969/j.issn.1002-1841.2017.06.037. YU W J, LI X B, YANG X, et al. Extrapolation artificial bee colony algorithm research on deployment optimization in wireless sensor network[J]. Instrument Technique and Sensor, 2017(6): 158-160. DOI: 10.3969/j.issn.1002-1841.2017.06.037.
[14]	周海鹏, 高芹, 蒋丰千, 等. 自适应混沌量子粒子群算法及其在WSN覆盖优化中的应用[J]. 计算机应用, 2018, 38(4): 1064-1071. DOI: 10.11772/j.issn.1001-9081.2017092372. ZHOU H P, GAO Q, JIANG F Q, et al. Application of self-adaptive chaotic quantum particle swarm algorithm in coverage optimization of wireless sensor network[J]. Journal of Computer Applications, 2018, 38(4): 1064-1071. DOI: 10.11772/j.issn.1001-9081.2017092372.
[15]	XUE J K, SHEN B. A novel swarm intelligence optimization approach: sparrow search algorithm[J]. Systems Science & Control Engineering, 2020, 8(1): 22-34. DOI: 10.1080/21642583.2019.1708830.
[16]	KHEDR A M, OSAMY W, SALIM A. Distributed coverage hole detection and recovery scheme for heterogeneous wireless sensor networks[J]. Computer Communications, 2018, 124: 61-75.
[17]	刘丽娟, 刘定一, 刘婷婷. 改进的正余弦优化算法在WSN覆盖中的应用[J]. 数学的实践与认识, 2021, 51(11): 129-137. https://www.cnki.com.cn/Article/CJFDTOTAL-SSJS202111013.htm LIU L J, LIU D Y, LIU T T. Application of improved sine-cosine optimization algorithm in WSN coverage[J]. Mathematics in Practice and Theory, 2021, 51(11): 129-137. https://www.cnki.com.cn/Article/CJFDTOTAL-SSJS202111013.htm
[18]	胡小平, 曹敬. 改进灰狼优化算法在WSN节点部署中的应用[J]. 传感技术学报, 2018, 31(5): 753-758. DOI: 10.3969/j.issn.1004-1699.2018.05.017. HU X P, CAO J. Improved grey wolf optimization algorithm for WSN node deployment[J]. ChineseJournal of Sensors and Actuators, 2018, 31(5): 753-758. DOI: 10.3969/j.issn.1004-1699.2018.05.017.
[19]	李银通, 韩统, 赵辉, 等. 自学习策略和Lévy飞行的正弦余弦优化算法[J]. 重庆大学学报, 2019, 42(9): 56-65. DOI: 10.11835/j.issn.1000-582X.2019.09.007. LI Y T, HAN T, ZHAO H, et al. An improved sine cosine optimization algorithm with self-learning strategy and Lévy flight[J]. Journal of Chongqing University, 2019, 42(9): 56-65. DOI: 10.11835/j.issn.1000-582X.2019.09.007.
[20]	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. DOI: 10.1007/s00521-015-1920-1.