Binh Le Huu, T Duong Thuy-Van, M Ngo Vuong
Faculty of Information Technology, University of Sciences, Hue University, Hue City, Vietnam.
Faculty of Information Technology, Ton Duc Thang University, Ho Chi Minh City, Vietnam.
PLoS One. 2025 Jan 28;20(1):e0318247. doi: 10.1371/journal.pone.0318247. eCollection 2025.
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.
最优路由器节点布局（RNP）是提高无线网状网络（WMN）性能的有效方法。然而，在无线网状网络中解决RNP问题很困难，因为它是NP难问题。因此，这个问题只能使用启发式算法和元启发式算法等近似优化算法来解决。在本研究中，我们提出了一种解决RNP问题的新的有效方法。该方法背后的思路是分两个阶段使用一个变量比原始RNP问题更少的最优算法来解决RNP问题。在第一阶段，我们使用15%到20%的路由器数量构建一个RNP子问题，目标函数是最小化路由器之间的覆盖重叠以形成一个核心网络。第二阶段使用剩余数量的路由器构建另一个RNP子问题，目标函数是最大化网络连通性。每个子问题都使用近似最优算法来解决。实验结果表明，在客户端覆盖和网络连通性方面，我们提出的方法优于广泛使用的解决RNP问题的方法。
