The Research Of Fault Tolerant And Topology In Wireless Sensor Networks

The wireless sensor network(WSN) consists of many sensor nodes,which are randomly deployed in harsh environment. and the sensor nodes are provided by batteries. Long distance commuciation is very costly, so the energy consumption is proportional to exponential time of transmitting distance. Placeing the more powerful relay nodes, improve the fault-tolerant of the networks and the topology control of the sensor network are all important ways to reduce energy depletion and prolong the lifetime of the networks.In this dissertation, we mainly study the problem of fault-tolerant and topology control in wireless sensor networks. The whole dissertation is organized as following:In chapter 1,we gives some introduction of basic concepts in graph theory, network and combinatorial optimization .In chapter 2 ,we present the background and a survey of fault-tolerant and topology control, Further more, we compare and analyze their advantages and disadvantages.Sensor nodes are very vulnerable to failures, they may lose functionalities at any time because of energy depletion, harsh environment factor or malicious attack, so it is important to consider fault-tolerant in wireless sensor network.In chapter 3,we mainly dissusss fault-tolerant in two-tiered wireless sensor networks with basestations, Firstly,we present a polynomial time approximation algorithms with performance ratio(10 +ε) for the 2-coverage 2-connectivity problem, then we design approximation algorithm for 3-coverage 3-connectivity problem, and extend to k-coverage 3-connectivity, and giving its algorithm and performance ratio.In chapter 4,we formulates the problem of maximizing the lifetime of sensor network, i.e. maximizing the total lifetime of connected coverage set with variable sensing and transmission Radii. We give a mathematical model of this problem using a linear programming with exponential number of variables and solve this linear programming using the approximation algorithms of Garg-Konemann, at last we give the performance ratio r (1 +ε)(1 + 2log hn)(ε> 0).where r is the link radius of the sensor network, n is the number of sensor nodes of the network, h is the total number of sensing radius choices available to sensor node.In chapter 5, we address the Adjustable range Set Covers and coverage problem that has as its objective finding a maximum number of sets ,such that each set cover all the targets and the sensors are connected,then design a heuristics algorithm . Finally, in chapter 6, we summarize the research, and look forward to the future in wireless sensor networks.