The Research Of Some Relay Nodes Placement In Wireless Sensor Networks

Energy saving is the key problem in wireless sensor networks. Since sensor nodes are powered by batteries and are randomly deployed in harsh environment, it is impossible to replace a battery. But long distance commuciation is very costly, because energy consumption is proportional to exponential time of transmitting distance, one important approach to reduce energy depletion is to place some more powerful relay nodes. In this dissertation, we focus on deploying a minimum number of relay nodes in different types of wireless sensor networks to achieve certain coverage and connectivity requirements.First, we start with the basic theoretical knowledge of graph, network and combinatorial optimization as the preliminary of the dissertation.In chapter 2, we present the background and a survey of wireless sensor networks, introduce common mathematical models and typical methods and algorithms. Further more, we compare and analyze their advantages and disadvantages.The main contents of this dissertation are from chapter 3 to 5. Due to the problems are NP-hard, so we design approximation algorithm for every considered problem.In chapter 3, we first dissuss relay nodes placement in single-tiered wireless sensor networks with basestations, according to the different case between sensor and relay nodes transmission radius, we present two polynomial time approximation algorithms with performance ratio 3 and 7, for the later algorithm, we give the lower bound of the performance ratio. Further more, we introduce basestations in two-tiered wireless sensor networks, and design approximation algorithm with performance ratio5 +ε.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 networks. In chapter 4, we study the fault-tolerant in single and two tiered wireless sensor networks with basestations. For the single-tiered situation, k-connectivity is the issue. For the two-tierd wireless sensor networks, we first design approximation algorithm for 2-coverage 2-connectivity problem, then extend to k-coverage 2-connectivity, we give its algorithm and performance ratio.With the coming of the advanced positioning system, the study of wireless sensor networks in three dimensional space is important. In chapter 5, we first research the relay nodes placement in three dimensional wireless sensor networks, according to the different value of algorithm factor, mainly for the single-coverage single-connectivity and fault-tolerant in two-tierd wireless sensor networks, we design the corresponding algorithm, give constant performance ratio. Finally, in chapter 6, we summarize the research, and look forward to the future in wireless sensor networks, show some open problems in the relay nodes placement problems.