Novel relay node placement algorithms for establishing connected topologies

This paper addresses the problem of placing the least number of fixed-range relay nodes (RNs) in order to establish multi-hop paths between every pair of terminals. We derive an optimal solution for the case of three terminals and for the cases of more than 3 terminals, we present three novel heuristics, namely, Optimized Triangle Selection based on Minimum Spanning Tree Triangulation (OTS-MST), Incremental Optimization based on Delaunay Triangulation (IO-DT) and hybrid approach. These heuristics take advantage of the optimal three-terminal based solution by forming connected sub-graphs for steinerized sets of three terminals and then connecting these sub-graphs via steinerized edges. OTS-MST considers triangles that have two mst edges and picks the subset of these triangles which provides the highest reduction in the total number of required RNs as compared to a solution that is based on steinerized mst edges. IO-DT calculates the Delaunay triangulation 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 reduces the RN count. Finally we consider a hybrid approach, which combines the strengths of OTS-MST and IO-DT. The performance of the proposed algorithms is validated through simulation.