Research on WSN Topological Invulnerability Based on Adaptive Simulated Annealing Particle Swarm Optimization Algorithm

doi:10.3969/j.issn.1671-1122.2021.06.011

Abstract

Abstract:

According to the characteristics of WSN nodes vulnerable to failure and damage, the invulnerability of WSN network was studied from the perspective of topology structure. Taking the natural connectivity of the network as the optimization objective, and considering the constraints of the total connectivity of the network nodes, the number of nodes and links, the communication radius of the nodes and the load of the nodes, a network topology invulnerability optimization model was established. Model was NP-hard problem, this paper proposed a new heuristic algorithm-adaptive simulated annealing particle swarm optimization algorithm, which applied the simulated annealing method before updating the particle population, to replace the part of fitness poor particles, overcome the traditional particle swarm optimization algorithm easy to fall into local optimum, and the inertia weight adaptation method was used to guarantee the convergence speed. Experimental results show that this method is effective to solve the network topology invulnerability optimization model. By using different strategies to attack the network nodes, the network topology optimized by the proposed algorithm is proved to be highly invulnerability.

Key words: particle swarm optimization, simulated annealing, network topology, invulnerability

CLC Number:

TP309

SONG Yulong, WANG Lei, WU Xinrong, ZENG Weijun. Research on WSN Topological Invulnerability Based on Adaptive Simulated Annealing Particle Swarm Optimization Algorithm[J]. Netinfo Security, 2021, 21(6): 89-96.

Figures/Tables 6

References 21

[1]	TAN Yuejin, WU Jun, DENG Hongzhong. Progress in Invulnerability of Complex Networks[J]. Journal of University of Shanghai for Science and Technology, 2011,33(6):653-668.
	谭跃进, 吴俊, 邓宏钟. 复杂网络抗毁性研究进展[J]. 上海理工大学学报, 2011,33(6):653-668.
[2]	HU Xingyu, ZHANG Xueyi, WU Jun, et al. Research for Invulnerability of Ad hoc Network Topologies[J]. Computer Technology and Development, 2010,20(1):185-188.
	胡兴雨, 张学义, 吴俊, 等. Ad hoc网络结构抗毁性研究[J]. 计算机技术与发展, 2010,20(1):185-188.
[3]	DENG Hongzhong, WU Jun, LI Yong, et al. Influence of Complex Network Topologic Structure on System Invulnerability[J]. Systems Engineering and Electronics, 2008,30(12):2425-2428.
	邓宏钟, 吴俊, 李勇, 等. 复杂网络拓扑结构对系统抗毁性影响研究[J]. 系统工程与电子技术, 2008,30(12):2425-2428.
[4]	ALBERT R, JEONG H, BARABASI A L. Error and Attack Tolerance of Complex Networks[J]. Nature, 2000,406(7):378-382. doi: 10.1038/35019019 URL
[5]	NIE Yuanyuan, FANG Zhigeng, GAO Su, et al. Survivability Analysis of LEO Satellite Networks Based on Network Utility[J]. IEEE Access, 2019,7(1):123182-123194. doi: 10.1109/Access.6287639 URL
[6]	WU Dapeng, LIU Zhenli, YANG Zhigang, et al. Survivability-enhanced Virtual Network Embedding Strategy in Virtualized Wireless Sensor Networks[J]. Sensors, 2020,21(1):218-237. doi: 10.3390/s21010218 URL
[7]	FU Xiuwen, YANG Yongsheng, POSTOLACHE O. Invulnerability of Clustering Wireless Sensor Networks Against Cascading Failures[J]. IEEE Systems Journal, 2019,13(2):1431-1442. doi: 10.1109/JSYST.2018.2849779
[8]	HUANG Ru, MA Lei, ZHAI Guangtao, et al. Resilient Routing Mechanism for Wireless Sensor Networks With Deep Learning Link Reliability Prediction[J]. IEEE Access, 2020,8(1):64857-64872. doi: 10.1109/Access.6287639 URL
[9]	LI Jianping, WANG Xiaokai. WSN Reliability Evaluation Based on Fuzzy Neural Network[J]. Journal of Computer Applications, 2016,36(S2):69-72, 76.
	李建平, 王晓凯. 基于模糊神经网络的无线传感器网络可靠性评估[J]. 计算机应用, 2016,36(S2):69-72, 76.
[10]	YU Zeng. Evaluation of Node Importance and Invulnerability Simulation Analysis in Complex Load-network[J]. Neurocomputing, 2020,416(11):158-164. doi: 10.1016/j.neucom.2019.05.092 URL
[11]	FU Xiuwen, YAO Haiqing, YANG Yongsheng. Exploring the Invulnerability of Wireless Sensor Networks against Cascading Failures[J]. Information Sciences, 2019,491(4):289-305. doi: 10.1016/j.ins.2019.04.004 URL
[12]	ZHANG Li, ZHAO Lihong, JIANG Yong, et al. Reliability Evaluation of Spatial Information Network Based on Petri Net Jump-plane Nodes[J]. Control Engineering of China, 2016,23(S1):66-72.
	张莉, 赵丽红, 蒋勇, 等. 基于Petri网跳面节点的空间信息网可靠性评估[J]. 控制工程, 2016,23(S1):66-72.
[13]	WANG Xin, LI Bin. Invulnerability of Wireless Sensor Networks Evaluation Based on the Number of Shortest Way[J]. Electronic Science and Technology, 2012,25(11):88-90.
	王鑫, 李彬. 基于最短路径数的WSN抗毁性评价方法[J]. 电子科技, 2012,25(11):88-90.
[14]	ZHAO Jingxian. Evaluation Method of Network Invulnerability Based on Nonoverlapping Paths Entropy[J]. Application Research of Computers, 2015,32(3):825-826.
	赵静娴. 基于不重叠路径熵的网络抗毁性评估方法[J]. 计算机应用研究, 2015,32(3):825-826.
[15]	SUN Chengyu, SHEN Maoxing, SHI Xiangfeng. Study of Computing Method to Node Tenacity Index for Network Invulnerability[J]. Application Research of Computers, 2017,34(7):1997-2000.
	孙成雨, 申卯兴, 史向峰. 网络抗毁性的点韧性度指标计算方法研究[J]. 计算机应用研究, 2017,34(7):1997-2000.
[16]	DONG Feihong, LYU Jing, GONG Xiangwu, et al. Optimization Design of Structure Invulnerability in Space Information Network[J]. Journal of Communications, 2014,35(10):50-58.
	董飞鸿, 吕晶, 巩向武, 等. 空间信息网络结构抗毁性优化设计[J]. 通信学报, 2014,35(10):50-58.
[17]	SUN Chengyu, SHEN Maoxing, SHENG Hao, et al. Optimization Design of Structure Invulnerability for Air Defense Multiple Sensor Network[J]. Journal of Communications, 2017,38(6):118-126.
	孙成雨, 申卯兴, 盛浩, 等. 防空多传感器网络结构抗毁性优化设计[J]. 通信学报, 2017,38(6):118-126.
[18]	XU Ying, ZOU Baihan. Survivability Analysis and Optimization of Dependent Networks Based on Natural Connectivity [C]//IEEE. 2020 IEEE International Conference on Artificial Intelligence and Computer Applications (ICAICA), June 27-29, 2020, Dalian, China. New York: IEEE, 2020: 1156-1160.
[19]	CVETKOVIĆ, DRAGOŠ M, DOOB M, et al. Spectra of Graphs: theory and Application[M]. Berlin: Deutscher Verlag der Wissenschaften, 1980.
[20]	ZHANG Ying, YANG Guangyuan, ZHANG Bin. FW-PSO Algorithm to Enhance the Invulnerability of Industrial Wireless Sensor Networks Topology[J]. Sensors, 2020,20(4):1114-1135. doi: 10.3390/s20041114 URL
[21]	YAN Chun, OU Zhaochuang, LIU Wei, et al. Research on UBI Auto Insurance Pricing Model Based on Adaptive SAPSO to Optimize the Fuzzy Controller[J]. International Journal of Fuzzy Systems, 2020,22(3):491-503. doi: 10.1007/s40815-019-00789-6 URL

参数	符号	取值
网络节点数	N	110
网络总边数	M	260
节点通信半径	R	50
节点最大度值	L	50
种群编码长度	K	N(N-1)/2
种群规模	N₀	600
初始温度	T₀	1000
降温速率	q	0.6
粒子转换概率	p	0.01
速度更新上限	${{V}_{\max }}$	1
速度更新下限	${{V}_{\min }}$	-1
认知参数	${{c}_{1}}$	1.5
社会参数	${{c}_{2}}$	1.5
最大惯性权重	${{\omega }_{\max }}$	1.2
最小惯性权重	${{\omega }_{\min }}$	0.9
算法最大迭代次数	gen	600

算法	最优值	运行时间/s
模拟退火算法	11.459	1292
粒子群算法	10.900	1071
基于模拟退火自适应粒子群算法	12.775	1574