A topology control algorithm based on D-region fault tolerance

• Published in: Science China. Information sciences 2013-07, Vol.56 (7), p.29-37
• Main Authors: Sun, RuoZi, Wang, Yue, Yuan, Jian, Shan, XiuMing, Ren, Yong
• Format: Article
• Language: English
• Subjects: Algorithms; Computer Science; Control algorithms; Control theory; D region; Diameters; Failure; Fault tolerance; Fault tolerant; Information Systems and Communication Service; Military applications; Natural disasters; Network design; Network topologies; Networks; Nodes; Relativity; Research Paper; Topology; Wireless networks; 容错算法; 容错网络; 容错能力; 拓扑; 控制算法; 无线网络; 网络连接; 节点故障
• ISSN: 1674-733X; 1869-1919
• DOI: 10.1007/s11432-012-4652-1

In a wireless network, node failure due to either natural disasters or human intervention can cause network partitioning and other communication problems. For this reason, a wireless network should be fault tolerant. At present, most researchers use k-connectivity to measure fault tolerance, which requires the network to be connected after the failure of any up to k-1 nodes. However~ wireless network node failures are usually spatially related, and particularly in military applications, nodes from the same limited area can fail together. As a metric of fault-tolerance, k-connectivity fails to capture the spatial relativity of faults and hardly satisfies the fault tolerance requirements of a wireless network design. In this paper, a new metric of fault-tolerance, termed D-region fault tolerance, is introduced to measure wireless network fault tolerance. A D-region fault tolerant network means that even after all the nodes have failed in a circular region with diameter D, it still remains connected. Based on D-region fault tolerance, we propose two fault-tolerant topology control algorithms-- the global region fault tolerance algorithm （GRFT） and the localized region fault tolerance algorithm （LRFT）. It is theoretically proven that both algorithms are able to generate a network with D-region fault tolerance. Simulation results indicate that with the same fault tolerance capabilities, networks based on both GRFT and LRFT algorithms have a lower transmission radius and lower logical degree.