Wireless Network Fault Tolerant Topology Control Algorithm Research

A wireless ad hoc network is a multi-hop, temporary, self-organized system which consists of a group of wireless communication transceiver devices. It can be quickly developed at any time and any place which does not need any infrastructure. The mobile nodes in the network have the function of routing and packet forwarding. The network topology can be formed via wireless links. A wireless sensor network is a fully-distributed system which doesn’t have the center node. The networks are formed in a self-organized and multi-hop way. Quantities of static and mobile sensor nodes are densely and randomly deployed in the monitor area. There is good cooperation ability between each node. They finish the global task by the local data exchange. Wireless networks including wireless ad hoc networks and wireless sensor networks attract more and more attention recently. They have important value and wide application prospect in the fields of emergency rescue, environmental monitoring and medical health.Recently, fault-tolerant communication and energy efficiency are the research focus and hot spots in wireless networks. Topology control is one of the most effective methods to ensure network connectivity and enhance the reliability, fault-tolerance and energy saving. The main goal of fault-tolerant topology control in wireless networks is to minimize energy consumption while maintaining desired properties of the network topology such as connectivity by power assignment and the construction of virtual backbone network. This paper makes a survey on the existing fault-tolerant topology control algorithms. The existing algorithms are analyzed regarding the fault-tolerance, energy-efficiency, algorithm complexity and stabilization. In this paper, we classify and review the state-of-the-art algorithms which have been proposed. Based on the graph theory, linear programming and cybernetics, we provide new fault-tolerant algorithms about broadcast, multicast and convergecast. Theoretical analysis indicates the correctness and efficiency of the algorithm. Moreover, simulation experiments show the total energy is smaller and the algorithm can prolong the network lifetime.This thesis includes five chapters. The first chapter introduces the concept of wireless ad hoc networks and wireless sensor networks. Based on the current study situation, we develop the study problem and research significance. The second chapter has a simple overview of the basic theory of fault-tolerant algorithms such as network models, energy models, other definitions about fault-tolerance, and categories some of the existing classical clustering algorithms. In the third chapter, an energy-efficient broadcast tree algorithm CBEEB is proposed. This algorithm consists of a clustering algorithm and an IBIP algorithm. First, each node in the network needs to compute the priority and then elects the clusterheads and cluster members of the network. The cluster members can be seen as the leaf nodes of the broadcast tree. As the energy cost of the leaf nodes is zero. Then, the IB IP algorithm is running on the set of the clusterheads to get the whole broadcast tree. In the fourth chapter, we study the construction of k-broadcast, k-multicast and k-convergecast topology control problems in wireless ad hoc networks. Our goal of these problems is to achieve the k-fault-tolerance with a minimal overall power assignment. For three different topology control problems, a new framework of approximation algorithm is proposed to maintain the k-fault-tolerant topology. In contrast to existing results, the algorithm has a smaller approximation ratio. Moreover, simulation experiments show that the total energy consumption is smaller. Finally, the fifth chapter summarizes this paper, and presents the future work.