Optimized relay node placement for establishing connectivity in sensor networks

Relay node placement in wireless sensor networks has gained importance due to its potential use in prolonging network life time, reducing data latency, and establishing connected topologies. In this paper we studied the relay node placement problem to establish multi-hop communication paths between every pair terminals (i.e., sensors) where each hop in the path is less than a common communication range. Such a problem is defined as Steiner Tree problem with minimum Steiner points and Bounded Edge-Length problem which is known to be NP-Hard. This paper presents a novel relay node placement heuristics called Incremental Optimization based on Delaunay Triangulation (IO-DT). The algorithm takes advantage of feasibility of finding optimal solution for the case of three terminals. IO-DT calculates the Delaunay triangulation (DT) of terminals and iterates over the formed triangles. In each iteration the algorithm steinerizes a triangle as part of the final topology if selecting such a triangle provides a reduction in total number of relay node required as compared to the minimum spanning tree (mst) based approach. The time complexity of IO-DT is quadratic in the number of terminals, which is superior to competing schemes. The performance of the algorithm is validated through simulation.