A novel approach for the router nodes placement in wireless mesh networks using phasing with approximation optimization algorithms

Optimal router node placement (RNP) is an effective method for improving the performance of wireless mesh networks (WMN). However, solving the RNP problem in WMN is difficult because it is NP-hard. As a result, this problem can only be solved using approximate optimization algorithms such as heuristics and meta-heuristics. In this study, we propose a new and effective method for solving the RNP problem. The idea behind this method is to solve the RNP problem in two stages using an optimal algorithm with fewer variables than the original RNP problem. In stage 1, we build an RNP sub problem using 15% to 20% of the number of routers, with the objective function of minimizing coverage overlap between routers to form a core network. Stage 2 is built into another RNP sub problem with the remaining number of routers, and the objective function is to maximize the network connectivity. Each sub problem was solved using an approximate optimal algorithm. The experimental results demonstrate that, in terms of client coverage and network connectivity, our proposed method outperforms widely used RNP problem-solving methods.