A Study On Topology Control And Energy Efficient In Wireless Sensor Networks

A wireless sensor network (WSN) is a wireless network consisting of spatially distributed autonomous devices using sensors to cooperatively monitor physical or environmental conditions, such as temperature, sound, vibration, pressure, motion or pollutants, at different locations.In sensor network, some sensor nodes may fail or be blocked due to lack of power, physical damage or environmental interference. Sensor nodes are prone to failure and movement, the topology of a sensor network changes very frequent after deployment. Therefore topology issues are receiving more and more attentions in sensor networks. While WSN applications are normally optimized by the given underlying network topology, another trend is to optimize WSN by means of topology control.The sensor node, being a microelectronic device, can only be equipped with a limited power source. The lifetime of network depends on the lifetime of the power resources of nodes, so minimizing energy consumption to prolong the network lifetime is a major design objective for sensor networks. In this dissertation, we mainly study the problem of topology control and energy efficient in wireless sensor networks. The whole dissertation is organized as following:Chapter1 outlines the background of our subject. Give some introduction for basic concepts in graph theory, combinatorial optimization, algorithms and complexity.Chapter2 introduces the notions and the methods of topology control at first. In the following, we make a survey previous on topology control problem.Chapter3 presents the design and analysis of our approximation algorithms for the fault tolerant connected sensor cover problem with variable sensing and transmission Radii. The algorithm runs in polynomial time and the performance ratio isO( r log khn ).Chapter4 formulates the problem of maximizing the lifetime of sensor network, i.e. maximizing the total lifetime of connected coverage set. 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-K?nemann. Chapter5 considers the energy efficient in sensor networks. Firstly, we review the related works on energy efficient. Secondly, we present algorithm for the problem of assigning sensor nodes to clusters in two-tiered network, where the relay nodes are used cluster head, so that the lifetime of the network is maximized and the total energy consumption is minimize. The problem is modeled as a min-cost flow problem which can be solved by some efficient algorithm.Chapter6 summarizes the paper and propose the prospects.