Novel relay node placement algorithms for establishing connected topologies

作者：Senel Fatih^*; Younis Mohamed

来源：Journal of Network and Computer Applications, 2016, 70: 114-130.

DOI：10.1016/j.jnca.2016.04.025

• Relay Node placement
• Network connectivity
• Topology management
• Interconnecting wireless networks

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 (10-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. 10-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.

• 出版日期2016-7