Date Added: Nov 2012
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 the authors 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).