Relay Node Placement And Algorithms In Wireless Sensor Network

A wireless sensor network (WSN) consists of many low-cost, low-power sensor nodes. The most key task for a sensor node is to monitor a certain area and to collect data from the area and transfer the data into a base station. In the real life there are some locations in which the relay nodes can not be placed, because these locations may be interfered by a variety of signals, or some locations may not be considered in certain circumstances, or the relay nodes can not be placed for other reasons. Therefore, we may consider giving a lot of locations alternated placing the relay nodes, then picking up minimum number of locations placing relay nodes to have the network work. WSN collecting how much data is dominated by the lifetime of network. Placing relay nodes into the wireless sensor network can make the network connectivity and also can prolong its lifetime. The relay node is not in order to monitor the environment or collect data but for keeping contacting with sensor nodes, so that the data of the sensor nodes reach a base station via some relay nodes. As the cost of a relay node is expensive, we expect to place minimum number of relay nodes to make the network lifetime as T.This paper discusses constrained relay node placement problem for cover and connectivity and relay node placement for maximizing network lifetime in the two-tiered WSN. These problems had been proved to be NP-hard. For the first problem we present an approximation algorithm and obtain a performance ratio; for the second problem we deploy a heuristic algorithm. This dissertation is structured as follows:In the chapter1, we introduce some basic conceptions on graph theory and combinatorial optimization, which we need in the later chapters.In the chapter 2, we take an overview of relay node placement problems in WSN. We survey their algorithm in some important works and compare with each other.In the chapter 3, we design an approximation algorithm for constrained relay node placement problem in the two-tiered WSN and obtain a performance ratio. In this algorithm, we first search for minimum number of alternative locations placing relay nodes to cover all the sensor nodes, and then look for minimum number of alternative positions placing relay nodes so that the relay nodes which cover these sensor nodes contacting with base stations. In the chapter we prove that the performance ratio of the algorithm is 9 +log 2d , d is the maximum of sensor nodes which can be covered by one relay node.In the chapter 4, using the idea of greedy algorithm, we design a heuristic algorithm for relay node placement for maximizing network lifetime. Furthermore, we give an experiment example to compare the solution of our algorithm and the optimal one. In the algorithm, we first place relay nodes as few as possible to make WSN connected, and then add a quantity of relay nodes to ensure the network lifetime as T.In the chapter 5, we summarize the paper and make a prospect to the future work.