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

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

网络与信息安全学报 ›› 2019, Vol. 5 ›› Issue (5): 32-38.doi: 10.11959/j.issn.2096-109x.2019048

• 专栏：复杂网络环境下的路由技术 • 上一篇下一篇

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

周赵斌^1,², 章红艳³, 汪晓丁^1,²()

¹ 福建师范大学数学与信息学院，福建福州350117
² 福建省网络安全与密码技术重点实验室，福建福州350117
³ 福建师范大学协和学院，福建福州 350117

修回日期:2019-06-06 出版日期:2019-10-15 发布日期:2019-11-02
作者简介:周赵斌（1989- ），男，江西南昌人，福建师范大学实验师，主要研究方向为网络与信息安全和网络编码。|章红艳（1982- ），女，江苏南通人，福建师范大学讲师，网络安全与计算。|汪晓丁（1982- ），男，福建安溪人，博士，福建师范大学副教授，主要研究方向为网络与信息安全、无线通信网络、云计算与物联网。
基金资助:
国家自然科学基金资助项目(61702103);福建省自然科学基金资助项目(2016J01289);福建省教育厅基金资助项目(JAT160123)

Fermat point based connectivity restoration strategy in networks

Zhaobin ZHOU^1,², Hongyan ZHANG³, Xiaoding WANG^1,²()

¹ College of Mathematics and Informatics,Fujian Normal University,Fuzhou 350117,China
² Fujian Provincial Key Lab of Network Security ＆Cryptology,Fuzhou 350117,China
³ Concord University College,Fujian Normal University,Fuzhou 350117,China

Revised:2019-06-06 Online:2019-10-15 Published:2019-11-02
Supported by:
The National Natural Science Foundation of China(61702103);The Natural Science Foundation of Fujian Province(2016J01289);Fujian Provincial Education Department Project(JAT160123)

摘要/Abstract

摘要：

连通性修复是保证网络有效性、可靠性的重要手段，而目前关于1-连通性修复的策略没有将图形的几何性质与网络的拓扑结构很好地结合，因此难以用最少的中继节点完成修复。将费马点、三角剖分与最小生成树有效结合，设计了一种基于费马点的网络连通性修复策略，并且从理论上证明了该策略的近似比和复杂度分别为 $\frac{3 \sqrt{3}}{4 - \sqrt{3}}$ 与O(n log n)，而仿真实验表明该策略在中继节点消耗上明显少于其他同类型策略。

关键词: 网络有效性, 连通性修复, 三角剖分, 费马点

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

中图分类号:

TP393

周赵斌, 章红艳, 汪晓丁. 基于费马点的网络连通性修复策略[J]. 网络与信息安全学报, 2019, 5(5): 32-38.

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.

图/表 4

表1

各算法在近似比和复杂度方面的对比"

算法	近似比	复杂度
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)

表1

图1

图2

图3

参考文献 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.

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

Fermat point based connectivity restoration strategy in networks

在线阅读

pdf下载

可视化

摘要/Abstract

引用本文

使用本文

图/表 4

参考文献 16

相关文章 15

Metrics

推荐阅读 0

[1]	陈先意, 顾军, 颜凯, 江栋, 许林峰, 付章杰. 针对车牌识别系统的双重对抗攻击[J]. 网络与信息安全学报, 2023, 9(3): 16-27.
[2]	叶天鹏, 林祥, 李建华, 张轩凯, 许力文. 面向雾计算的个性化轻量级分布式网络入侵检测系统[J]. 网络与信息安全学报, 2023, 9(3): 28-37.
[3]	祖立军, 曹雅琳, 门小骅, 吕智慧, 叶家炜, 李泓一, 张亮. 基于隐私风险评估的脱敏算法自适应方法[J]. 网络与信息安全学报, 2023, 9(3): 49-59.
[4]	夏锐琪, 李曼曼, 陈少真. 基于机器学习的分组密码结构识别[J]. 网络与信息安全学报, 2023, 9(3): 79-89.
[5]	袁静怡, 李子川, 彭国军. EN-Bypass：针对邮件代发提醒机制的安全评估方法[J]. 网络与信息安全学报, 2023, 9(3): 90-101.
[6]	余锋, 林庆新, 林晖, 汪晓丁. 基于生成对抗网络的隐私增强联邦学习方案[J]. 网络与信息安全学报, 2023, 9(3): 113-122.
[7]	朱春陶, 尹承禧, 张博林, 殷琪林, 卢伟. 基于多域时序特征挖掘的伪造人脸检测方法[J]. 网络与信息安全学报, 2023, 9(3): 123-134.
[8]	李晓萌, 郭玳豆, 卓训方, 姚恒, 秦川. 载体独立的抗屏摄信息膜叠加水印算法[J]. 网络与信息安全学报, 2023, 9(3): 135-149.
[9]	蔡召, 荆涛, 任爽. 以太坊钓鱼诈骗检测技术综述[J]. 网络与信息安全学报, 2023, 9(2): 21-32.
[10]	潘雁, 林伟, 祝跃飞. 渐进式的协议状态机主动推断方法[J]. 网络与信息安全学报, 2023, 9(2): 81-93.
[11]	杨盼, 康绯, 舒辉, 黄宇垚, 吕小少. 基于函数摘要的二进制程序污点分析优化方法[J]. 网络与信息安全学报, 2023, 9(2): 115-131.
[12]	肖天, 江智昊, 唐鹏, 黄征, 郭捷, 邱卫东. 基于深度强化学习的高性能导向性模糊测试方案[J]. 网络与信息安全学报, 2023, 9(2): 132-142.
[13]	袁承昊, 李勇, 任爽. 多关键词动态可搜索加密方案[J]. 网络与信息安全学报, 2023, 9(2): 143-153.
[14]	侯泽洲, 任炯炯, 陈少真. 基于神经网络区分器的SIMON-like算法参数安全性评估[J]. 网络与信息安全学报, 2023, 9(2): 154-163.
[15]	郭学镜, 方毅翔, 赵怡, 张天助, 曾文超, 王俊祥. 基于传统引导机制的深度鲁棒水印算法[J]. 网络与信息安全学报, 2023, 9(2): 175-183.