The Research Of Wireless Sensor Network Minimum Relay Node Placement Problem

With the rapid development of wireless communication technology, information processing technology, embedded computing technology and sensor technology, some relatively mature wireless network technology is more and more deeply into all aspects of social life. Wireless sensor network has increasingly aroused people’s great attention and becomes a hot spot of current research content.In wireless sensor network, only by guaranteeing the connectivity of network, the information monitored by sensors can be transmitted to the control center. Because of some fault node or limited deployment area conditions, the network could be disconnected. In order to guarantee the connectivity of network, a certain number of prices cheaper relay nodes need to be deployed. Considering from cost savings,the number of relay nodes should be deployed as less as possible, while keeping the network connectivity.In single-tired wireless sensor network, this paper puts forward new algorithms based on Steiner tree. Based on the triangular Steiner tree, if the full Steiner topology graph exists in local area, the minimum full Steiner topology graph can be obtained by solving the minimizing a sum of Euclidean norms problem. And then by using the minimum Steiner full topology as initial value,the number of relay nodes can be reduced by adopting the method of Steiner points position adjustment according to the communication features of sensor nodes and relay nodes.In two-tired wireless sensor network, this paper puts forward a new greedy algorithm called CGCP which is based on the GCP algorithm of the DCover methods. In GCP algorithm, one relay node would be deployed at each step. In the strategy by adding a new relay node, first choosing a key node from the uncovered sensor node, and then placing relay node in order according to the distance between the sensor node and the relay node. At each step, by limiting the scope of key node and modifying the deployment strategy of relay nodes, the GCP algorithm is put forward.A lot of simulation experiments have been made to appraise the performance of algorithms. Through experimental analysis, in single-tired network, this paper proposes the STIO algorithm and the STIO1 algorithm based on different sensor node selection strategy. The STIO algorithm is compared with MST-1tRNP algorithm, the number of relay nodes reduced by almost 15% when the distribution density of sensors is 0.25 or 0.5. On average, the performance of the STIO algorithm is better than the STIO1 algorithm. But in some cases, the performance of the STIO1 algorithm is better than the STIO algorithm. In the fixed area, the STIO algorithm needs the minimum number of relay nodes while the number of sensors is different. In two-tired network, the CGCP algorithm based on the GCP algorithm is proposed to guarantee the network connectivity. The performance of the CGCP algorithm is obtained by compared with the GCP algorithm, the GSC algorithm and the SCP algorithm. And the experiment shows that the CGCP algorithm needs the minimum number of relay nodes when R=r in different number of sensors.