Abstract:To solve the problem of relay node placement in hybrid wireless sensor networks, a minimum number of relay nodes placement algorithm is proposed in this paper to meet certain requirements of connectivity and survivability, where relay nodes can only be placed on a subset of candidate locations. In the connected relay node placement problem, an efficient STP approximation algorithm based on minimum spanning tree is proposed to ensure the connectivity between sensor nodes and base stations. In the survivable relay node placement problem, a polynomial time approximation algorithm based on {0,1,2}SNDP is proposed to ensure the biconnectivity between sensor nodes and base stations. Experimental results show that the proposed singletiered constrained relay node placement algorithm has a smaller running time and can almost achieve the performance comparable to the optimal solution.