Fermat point based connectivity restoration strategy in networks - Zhaobin ZHOU; Hongyan ZHANG; Xiaoding WANG (网络与信息安全学报)
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<msqrt> 3 </msqrt> 4−<msqrt> 3 </msqrt> 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.