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

周赵斌; 章红艳; 汪晓丁

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

您当前的位置：

首页 >

文章列表页 >

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

专栏：复杂网络环境下的路由技术 | 更新时间：2024-06-03

- 基于费马点的网络连通性修复策略
- Fermat point based connectivity restoration strategy in networks
- 网络与信息安全学报 2019年5卷第5期页码：32-38
- 作者机构：
  
  1. 福建师范大学数学与信息学院，福建福州350117
  2. 福建省网络安全与密码技术重点实验室，福建福州350117
  3. 福建师范大学协和学院，福建福州 350117
- 作者简介：
  
  [ "周赵斌（1989- ），男，江西南昌人，福建师范大学实验师，主要研究方向为网络与信息安全和网络编码。" ]
  [ "章红艳（1982- ），女，江苏南通人，福建师范大学讲师，网络安全与计算。" ]
  [ "汪晓丁（1982- ），男，福建安溪人，博士，福建师范大学副教授，主要研究方向为网络与信息安全、无线通信网络、云计算与物联网。" ]
- 基金信息：
  
  国家自然科学基金资助项目;The National Natural Science Foundation of China(61702103);福建省自然科学基金资助项目;The Natural Science Foundation of Fujian Province(2016J01289);福建省教育厅基金资助项目;Fujian Provincial Education Department Project(JAT160123)
- DOI：10.11959/j.issn.2096-109x.2019048
  中图分类号： TP393
- 网络首发：2019-10，
  
  纸质出版：2019-10-15
- 稿件说明：
移动端阅览
周赵斌, 章红艳, 汪晓丁. 基于费马点的网络连通性修复策略[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.
周赵斌, 章红艳, 汪晓丁. 基于费马点的网络连通性修复策略[J]. 网络与信息安全学报, 2019,5(5):32-38. DOI： 10.11959/j.issn.2096-109x.2019048.

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. DOI： 10.11959/j.issn.2096-109x.2019048.

摘要

连通性修复是保证网络有效性、可靠性的重要手段，而目前关于1-连通性修复的策略没有将图形的几何性质与网络的拓扑结构很好地结合，因此难以用最少的中继节点完成修复。将费马点、三角剖分与最小生成树有效结合，设计了一种基于费马点的网络连通性修复策略，并且从理论上证明了该策略的近似比和复杂度分别为

与O(n log n)，而仿真实验表明该策略在中继节点消耗上明显少于其他同类型策略。

Abstract

The connectivity restoration ensures the availability and reliability of a network.Both of geometrical feature

s 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

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.

关键词

Keywords

references

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.

LALOUANI W , YOUNIS M , BADACHE N . Optimized repair of a partitioned network topology [J ] . Computer Networks , 2017 , 128 : 63 - 77 .

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.

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.

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 .

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 .

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 .

CHENG X , DU D Z , WANG L , et al . Relay sensor placement in wireless sensor networks [J ] . Wireless Networks , 2008 , 14 ( 3 ): 347 - 355 .

LLOYD E L , XUE G . Relay node placement in wireless sensor networks [J ] . IEEE Transactions on Computers , 2007 , 56 ( 1 ): 134 - 138 .

TANG J , HAO B , SEN A . Relay node placement in large scale wireless sensor networks [J ] . Computer Communications , 2006 , 29 ( 4 ): 490 - 501 .

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 .

JOSHI Y K , YOUNIS M . Exploiting skeletonization to restore connectivity in a wireless sensor network [J ] . Computer Communications , 2016 , 75 : 97 - 107 .

RANGA V , DAVE M , VERMA A K . Relay node placement to heal partitioned wireless sensor networks [J ] . Computers ＆ Electrical Engineering , 2015 , 48 : 371 - 388 .

陈洪生 , 石柯 . 基于四边形斯坦纳树的无线传感器网络连通恢复 [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 .

SENEL F , YOUNIS M . Novel relay node placement algorithms for establishing connected topologies [J ] . Journal of Network and Computer Applications , 2016 ,( 70 ): 114 - 130 .

ROBINS G , ZELIKOVSKY A . Tighter bounds for graph Steiner tree approximation [J ] . SIAM Journal on Discrete Mathematics , 2005 , 19 ( 1 ): 122 - 134 .

浏览量

229

下载量

CSCD

文章被引用时，请邮件提醒。

提交

工具集

关联资源

暂无数据