Topology design for wireless ad-hoc networks with backbone support
Yufeng Xin, Mark A. Shayman · 2005
Abstract — A backbone-based hybrid network architecture has the potential to enhance the connectivity and throughput capacity of wireless ad-hoc networks. A fundamental problem for this hybrid network architecture is designing the optimal network topology under certain topological constraints. In this paper, this problem is formulated as a generalized optimal geometric Steiner network problem with minimum number of Steiner nodes under the various practical constraints. In this new problem formulation, the backbone (Steiner) nodes have two heterogeneous transmission ranges, one for connecting to the terminal nodes and the other for connecting to other backbone nodes. The overall network and the backbone subnetwork are both connected. We also consider the case when the number of hops from a terminal node to its closest backbone node is constrained. As the problem is NP-hard, we propose a multiple-step solution approach, compare several heuristic algorithms by a comprehensive simulation study and identify some critical topological characteristics. The results show that a highly scalable backbone network can be built for a large number of terminal nodes.