Fermat point based connectivity restoration strategy in networks

Zhaobin ZHOU; Hongyan ZHANG; Xiaoding WANG

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

您当前的位置：

首页 >

文章列表页 >

Fermat point based connectivity restoration strategy in networks

Special Column: Routing Technology in Complex Network Environment | 更新时间：2024-06-03

- Fermat point based connectivity restoration strategy in networks
- Chinese Journal of Network and Information Security Vol. 5, Issue 5, Pages: 32-38(2019)
- 作者机构：
  
  1. 福建师范大学数学与信息学院，福建福州350117
  2. 福建省网络安全与密码技术重点实验室，福建福州350117
  3. 福建师范大学协和学院，福建福州 350117
- 作者简介：
- 基金信息：
- DOI：10.11959/j.issn.2096-109x.2019048
  CLC： TP393
- Online First：2019-10，
  
  Published：15 October 2019
- 稿件说明：
移动端阅览
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：

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 .

Views

229

下载量

CSCD

Alert me when the article has been cited

提交

Tools

Publicity Resources

No data

Related Author

No data

Related Institution

No data

⁰