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

Fermat point based connectivity restoration strategy in networks

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

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 3√3/(4-√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.