基于费马点的网络连通性修复策略

doi:10.11959/j.issn.2096-109x.2019048

Abstract

Abstract:

The connectivity restoration ensures the availability and reliability of a network.Both of geometrical features and topological structures should be taken into consideration at the same time,without which previous works can hardly restore the connectivity with the least number of relay nodes.The Fermat point,the triangulation and the minimum spanning tree are integrated with the design of an efficient restoration strategy.The theoretical analysis indicate that the approximation ratio of the proposed strategy is $\frac{3 \sqrt{3}}{4 - \sqrt{3}}$ and the complexity of which is O(n log n).Simulation results show that the proposed strategy outperforms other strategies in the number of relay nodes required.

Key words: network availability, connectivity restoration, triangulation, fermat point

CLC Number:

TP393

Zhaobin ZHOU, Hongyan ZHANG, Xiaoding WANG. Fermat point based connectivity restoration strategy in networks[J]. Chinese Journal of Network and Information Security, 2019, 5(5): 32-38.

Figures/Tables 4

算法	近似比	复杂度
Misra等^[5]	12.4	$O (n^{2 k - 2} + n^{2 k + 1} \log n)$
Lloyd等^[9]	7	O(nlogn)
Yang 等^[6]	6.43	$O (n^{2 k - 2} + n^{2 k + 1} \log n)$
Misra等^[7]	6.2	$O (n^{2 k - 2} + n^{2 k + 1} \log n)$
Tang等^[10]	4.5	无
Efrat等^[3]	3.11	$O (n^{2 k - 2} + n^{2 k + 1} \log n)$
Cheng等^[8]	3	O( ⁴n )
Chen 等^[11]	3	O( ³n )
Wang等^[4]	3	O( ³n )
Wang等^[1]	$\frac{3 \sqrt{3}}{2}$	O(n ³)
Lalouani等^[2]		O(n ⁴)
Cheng等^[8]	2.5	O( ³n )
RSFP (本文)	$\frac{3 \sqrt{3}}{4 - \sqrt{3}}$	O(nlogn)

References 16

[1]	XIAODING W , LI X , ZHOU S M . A straight skeleton based connectivity restoration strategy in the presence of obstacles for WSN[J]. Sensors, 2017,17(10):2299.
[2]	LALOUANI W , YOUNIS M , BADACHE N . Optimized repair of a partitioned network topology[J]. Computer Networks, 2017,128: 63-77.
[3]	EFRAT A , FEKETE S P , MITCHELL J S B ,et al. Improved approximation algorithms for relay placement[J]. ACM Transactions on Algorithms (TALG), 2016,12(2):20.
[4]	WANG X D , LI X , ZHOU S M . Restoration strategy based on optimal relay node placement in wireless sensor networks[J]. International Journal of Distributed Sensor Networks, 2015,11(7):409085.
[5]	MISRA S , MAJD N E , HUANG H . Approximation algorithms for constrained relay node placement in energy harvesting wireless sensor networks[J]. IEEE Transactions on Computers, 2014,63(12): 2933-2947.
[6]	YANG D , MISRA S , FANG X ,et al. Two-tiered constrained relay node placement in wireless sensor networks:computational complexity and efficient approximations[J]. IEEE Transactions on Mobile Computing, 2012,11(8): 1399-1411.
[7]	MISRA S , HONG S D , XUE G ,et al. Constrained relay node placement in wireless sensor networks:formulation and approximations[J]. IEEE/ACM Transactions on Networking (TON), 2010,18(2): 434-447.
[8]	CHENG X , DU D Z , WANG L ,et al. Relay sensor placement in wireless sensor networks[J]. Wireless Networks, 2008,14(3): 347-355.
[9]	LLOYD E L , XUE G . Relay node placement in wireless sensor networks[J]. IEEE Transactions on Computers, 2007,56(1): 134-138.
[10]	TANG J , HAO B , SEN A . Relay node placement in large scale wireless sensor networks[J]. Computer Communications, 2006,29(4): 490-501.
[11]	CHEN D , DU D Z , HU X D ,et al. Approximations for steiner trees with minimum number of Steiner points[J]. Journal of Global Optimization, 2000,18(1): 17-33.
[12]	JOSHI Y K , YOUNIS M . Exploiting skeletonization to restore connectivity in a wireless sensor network[J]. Computer Communications, 2016,75: 97-107.
[13]	RANGA V , DAVE M , VERMA A K . Relay node placement to heal partitioned wireless sensor networks[J]. Computers ＆ Electrical Engineering, 2015,48: 371-388.
[14]	陈洪生, 石柯 . 基于四边形斯坦纳树的无线传感器网络连通恢复[J]. 计算机学报, 2014,37(2): 457-469.
	CHEN H S , SHI K . Quadrilateral steiner tree based connectivity restoration for wireless sensor networks[J]. Chinese Journal of Computers, 2014,37(2): 457-469.
[15]	SENEL F , YOUNIS M . Novel relay node placement algorithms for establishing connected topologies[J]. Journal of Network and Computer Applications, 2016,(70): 114-130.
[16]	ROBINS G , ZELIKOVSKY A . Tighter bounds for graph Steiner tree approximation[J]. SIAM Journal on Discrete Mathematics, 2005,19(1): 122-134.

Metrics

Recommended 0

No Suggested Reading articles found!

Fermat point based connectivity restoration strategy in networks

RichHTML

PDF下载

Knowledge

Abstract

Cite this article

share this article

Figures/Tables 4

References 16

Related Articles 15

Metrics

Recommended 0

[1]	Xianyi CHEN, Jun GU, Kai YAN, Dong JIANG, Linfeng XU, Zhangjie FU. Double adversarial attack against license plate recognition system [J]. Chinese Journal of Network and Information Security, 2023, 9(3): 16-27.
[2]	Tianpeng YE, Xiang LIN, Jianhua LI, Xuankai ZHANG, Liwen XU. Personalized lightweight distributed network intrusion detection system in fog computing [J]. Chinese Journal of Network and Information Security, 2023, 9(3): 28-37.
[3]	Lijun ZU, Yalin CAO, Xiaohua MEN, Zhihui LYU, Jiawei YE, Hongyi LI, Liang ZHANG. Adaptive selection method of desensitization algorithm based on privacy risk assessment [J]. Chinese Journal of Network and Information Security, 2023, 9(3): 49-59.
[4]	Ruiqi XIA, Manman LI, Shaozhen CHEN. Identification on the structures of block ciphers using machine learning [J]. Chinese Journal of Network and Information Security, 2023, 9(3): 79-89.
[5]	Jingyi YUAN, Zichuan LI, Guojun PENG. EN-Bypass: a security assessment method on e-mail user interface notification [J]. Chinese Journal of Network and Information Security, 2023, 9(3): 90-101.
[6]	Feng YU, Qingxin LIN, Hui LIN, Xiaoding WANG. Privacy-enhanced federated learning scheme based on generative adversarial networks [J]. Chinese Journal of Network and Information Security, 2023, 9(3): 113-122.
[7]	Chuntao ZHU, Chengxi YIN, Bolin ZHANG, Qilin YIN, Wei LU. Forgery face detection method based on multi-domain temporal features mining [J]. Chinese Journal of Network and Information Security, 2023, 9(3): 123-134.
[8]	Xiaomeng LI, Daidou GUO, Xunfang ZHUO, Heng YAO, Chuan QIN. Carrier-independent screen-shooting resistant watermarking based on information overlay superimposition [J]. Chinese Journal of Network and Information Security, 2023, 9(3): 135-149.
[9]	Zhao CAI, Tao JING, Shuang REN. Survey on Ethereum phishing detection technology [J]. Chinese Journal of Network and Information Security, 2023, 9(2): 21-32.
[10]	Yan PAN, Wei LIN, Yuefei ZHU. Progressive active inference method of protocol state machine [J]. Chinese Journal of Network and Information Security, 2023, 9(2): 81-93.
[11]	Pan YANG, Fei KANG, Hui SHU, Yuyao HUANG, Xiaoshao LYU. Binary program taint analysis optimization method based on function summary [J]. Chinese Journal of Network and Information Security, 2023, 9(2): 115-131.
[12]	Tian XIAO, Zhihao JIANG, Peng TANG, Zheng HUANG, Jie GUO, Weidong QIU. High-performance directional fuzzing scheme based on deep reinforcement learning [J]. Chinese Journal of Network and Information Security, 2023, 9(2): 132-142.
[13]	Chenghao YUAN, Yong LI, Shuang REN. Dynamic multi-keyword searchable encryption scheme [J]. Chinese Journal of Network and Information Security, 2023, 9(2): 143-153.
[14]	Zezhou HOU, Jiongjiong REN, Shaozhen CHEN. Security evaluation for parameters of SIMON-like cipher based on neural network distinguisher [J]. Chinese Journal of Network and Information Security, 2023, 9(2): 154-163.
[15]	Xuejing GUO, Yixiang FANG, Yi ZHAO, Tianzhu ZHANG, Wenchao ZENG, Junxiang WANG. Traditional guidance mechanism based deep robust watermarking [J]. Chinese Journal of Network and Information Security, 2023, 9(2): 175-183.