The Research Of Relay Node Placement And Algorithm In Wireless Sensor Networks

The wireless sensor networks consist of a lot of cheap sensor nodes which are placed on vile envioronment , The sensor nodes have the function of monitoring , data processing and communication in a short distance. and are also controled by the battery, but the energy is limited and could not be replaced in time, at the same time, transmit information and communication are also needs energy, the energy consumption is in proportion of the index of the distance. So how to reduce the energy consuming will be an important issue in the future.The thesis mainly discusses two different relay node placement problems with different connect requirement。And gives two approximation algorithms and their performance ratio. This thesis is structured as follows:In the chapter1, we introduce some basic conceptions on graph theory and combinatorial optimization, which are needed in the later chapters.In the chapter 2, we take an overview of relay node placement problems in WSN, and the achievement on the issue. We survey their algorithm on some important works and compare with each other.In the chapter 3, We design an approximation algorithm for constrained relay node placement problem which has a different requirement of the connectivity in the one-tiered WSN and obtain a performance ratio. The algorithm first give weight to every edge , and then research for the minimum sum of the weight of the edge. The ratio of the algorthim is 10.In the chapter 4, we mainly discusses the problem when R=r , and givies an algorthim to meet the requirement that there are at least two disjoint paths between all the sensor nodes .We also give the approvement of the performance ratio.In the chapter 5, we summarize the paper and make a prospect to the future work.