Abstract
Wireless Sensor Network (WSN) is a network consisting of a number of sensor nodes (SN). Due to the restraint of power consumption and communication range, sensor nodes communicate with each other using the multi-hop method. When the distance between some SNs is larger than their communication range, the WSN cannot be connected. One approach to resolve this problem is to place relay nodes (RN) which have better transmission power, but more expensive, than general SNs. This thesis focuses on the minimization of the relay node placement problem. This problem is called STP-MSP (the Steinerized Tree Problem with Minimum number of Steiner Points), which is defined as follows. Given a set of SNs, X={p1,p2,…,pn}, in the Euclidean plane R2, and a positive constant R, representing SNs’ communication range, STP-MSP asks for a Steiner tree T that connects all nodes in X such that each edge in T has length less than or equal to R, and the number of Steiner points is minimized. In [1], it is shown showed that the STP-MSP problem is NP-hard. In [2][3], authors presented an approximate algorithm with approximation ratio 3. In this paper, we proved some analyses and improvements on the 3-approximation algorithm. First, we analyzed the worst cases of the algorithm, which could lead a tighter bound of the approximation ratio. Second, we used the Delaunay triangulation to improve the performance of the algorithm, by which the time complexity is reduced from O(n3) to O(n log n).