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

Abstract

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.

Introduction

Wireless mesh networks (WMN) are currently the main technology solution in wireless local area networks (WLAN) of agencies, businesses, and schools. WMN is being prioritized by network administrators because it has many advantages compared to wireless networks using traditional access points, typically reducing congestion due to the ability to balance load, and convenience in deploying infrastructure because there is no need to connect wired links to all wireless routers. Fig 1 shows an example of a WMN consisting of two gateway mesh router (GMR) (w₁ and w₂), eight mesh wireless routers (r₁ to r₈), and twenty-one clients. Two GWRs, w₁ and w₂, are connected directly to the Internet service provider (ISP) via an optical fiber or a twisted pair cable. In a WMN, the number of GMRs is usually determined based on the average traffic load in the network and the capacity of the connection channels from the GMRs to the ISP, as shown in Fig 1, which are channels from w₁ and w₂. The remaining wireless routers (r₁ to r₈) connect to each other through wireless links, forming a mesh topology. Each client connects to a wireless router to access Internet. If a client is covered by multiple routers, it connects to the router with the strongest signal strength.

[Figure omitted. See PDF.]

Designing and deploying a WMN network with the best performance is essential to satisfy the current demand for wireless network services. This has motivated many research groups to focus on WMN recently. Network topology control [1–4], router node placement (RNP) [5–20], routing protocols [21–24], and access point allocation [25–28] are some of the most common topics that have been deployed, in which the RNP problem is the most interesting topic. As this problem is NP-hard [10], conventional algorithms cannot solve it. The use of approximate optimization algorithms, such as heuristics and meta-heuristics is one possible solution to this problem. Several approximation algorithms have been successfully applied to solve the RNP problem, such as the Multi-Verse Optimizer algorithm (MVO) [8], particle swarm optimizer algorithm (PSO) [6], accelerated particle swarm optimizer algorithm (APSO) [6], linearly decreasing weight particle swarm optimizer (LDWPSO) [29], the coyote optimization algorithm (COA) [5], Chemical Reaction Optimization algorithm (CRO) [7]. These studies have solved the RNP problem, and the results obtained can be applied to install WMN in practice. However, in the case of WMN with a large area, many mesh routers, and dense client density, solving the RNP problem using approximate algorithms is often difficult because of the increase in the number of variables and search space, leading to increased computational complexity. Therefore, it is necessary to investigate how to effectively apply approximation optimization algorithms to the RNP problem in these cases. This motivated us to conduct this study. The main contributions of this study are summarized as follows.

1. (i) We propose a new objective function for the RNP problem that contains two metrics, NC and COR.

2. (ii) We propose a new and effective method to solve the RNP problem. Our idea is to solve the RNP problem in two stages using 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 COR 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 NC. Each sub-problem is solved using an approximate optimal algorithm.

The remainder of this paper is organized as follows. The next section presents the RNP problem. The following sections describes the proposed method to solve the RNP problem and experimental results. The final section is conclusions and suggestions for further research.

Related works

Recently, a lot of researchers have been interested in finding a solution to the RNP problem in WMN. Numerous methods have been put up to address this issue, most commonly including the use of reinforcement learning and approximate optimization algorithms. Using reinforcement learning, the authors of [15] proposed a highly effective method to solve the RNP problem. The authors modeled the RNP problem as a reinforcement learning process. The features for reinforcement learning are {environment, agent, action, and reward}, which correspond to {network system, mesh routers, coordinate adjustment of mesh routers, and network connectivity} of the RNP problem. Simulation results indicate that as compared to current methods, the suggested method has greatly enhanced network connection. Approximate optimization algorithms are another method that researchers have recently employed to solve the RNP problem. A recent study by Sylia M. T. et al. used the COA to address the RNP problem [5]. In this study, an objective function made up of two performance metrics, network connectivity and user convergence, is developed. The RNP problem is then reformulated as a nonlinear programming problem with the purpose of maximizing the two specified metrics. The outcomes of the simulation show that, in comparison to alternative optimization methods, COA is more beneficial and successful at determining the best coordinates for mesh routers. Another study recommended using the MVO algorithm to solve the RNP problem [8]. The authors of this study suggested a new objective function for the RNP issue that takes into account the connected client ratio and connected router ratio metrics, two crucial performance indicators. Next, in order to maximize the two suggested metrics, the mesh routers are placed using a coordinate set that is determined by the MVO method. The findings of the experiment indicate that, in comparison to the other optimization algorithm, the MVO algorithm improves the connected client ratio and decreases the path loss of the wireless links when it is used to the RNP problem. In [30], the authors suggested an improved Moth Flame Optimization (MFO) algorithm for solving the RNP issue. This technique is known as Enhanced Chaotic Lévy Opposition-based MFO (ECLO-MFO). Taking into account network connectivity and client coverage metrics, the suggested ECLO-MFO’s efficacy is evaluated in a variety of scenarios and configurations. In comparison with the original MFO and 10 other optimization algorithms, the simulation results show the accuracy and superiority of ECLO-MFO in selecting the ideal placements of mesh routers. Also with the method of applying approximate optimization algorithm to RNP problem, an intelligent simulation system based on the Cuckoo Search (CS) algorithm, WMN-CS, was proposed and put into use by the authors of [31]. By adjusting the scale parameter (γ) and host bird discovery rate (p_a), this study assessed WMN-CS performance for different combinations of hyperparameters. The simulation findings indicate that when the host bird recognition rate (p_a) is between 0.900 and 0.925 and the scale parameter (γ) is between 0.07 and 0.09, greater performance is obtained.

The findings of the aforementioned studies suggest that using approximate optimization methods to address the RNP problem is a feasible and highly successful strategy. However, in the case of WMN with a vast area, multiple mesh routers, and dense client density, solving the RNP problem with approximate methods is frequently challenging due to a rise in the number of variables and search space, resulting in increased computing complexity. As a result, It is essential to look into the best ways to solve the RNP problem using approximation optimization algorithms in these instances. This problem is addressed in this study by a novel approach to solving the RNP problem which is implemented in two stages. The following sections present the proposed solution in detail.

RNP problem

Graph theoretical model for WMN

Consider a WMN consisting of m mesh routers, n clients, and k gateway routers located in an area of H × W m. We used an undirected graph G(V, E) to represent this WMN, where V and E denote the vertex and edge sets, respectively. V = R ∪ W ∪ C, where R = {r_i|i = 1..m} is the set of mesh routers, W = {w_i|i = 1..k} is the set of gateway routers and C = {c_i|i = 1..n} denotes the set of clients. E = L_r,r ∪ L_r,w ∪ L_r,c, where L_r,r is the set of wireless links between mesh routers, L_r,w is the set of wireless links between mesh routers and gateway routers, and L_r,c is the set of wireless links between mesh routers and clients.

For the RNP problem, the network connectivity metric is often used to evaluate network performance [5, 6, 8]. This metric was also used in this study. In addition, we used an additional metric of overage overlap between routers for the core network design stage.

Network connectivity

In a WMN, network connectivity is defined as the ratio of the number of connected clients to the number of clients in the network. Let NC be the network connectivity; then, NC is determined by(1)where C_c denotes the set of clients connected to at least one gateway router. Returning to the example of WMN in Fig 1, sets C and C_c are determined as follows(2)(3)because c₅, c₉ and c₂₅ are not connected to any gateway router. According to (1) we have:(4)

CoOverage overlap radius between mesh routers

In a WMN, the coverage overlap radius (COR) between routers significantly affects the coverage area of the entire network. Fig 2 illustrates the COR between the two mesh routers r_i and r_j, calculated as(5)where d_cr is the coverage radius of each mesh router, and d_i,j is the distance between mesh routers r_i and r_j. determined by(6)where and are the coordinates of the mesh routers r_i and r_j, respectively.

[Figure omitted. See PDF.]

Formulation of the RNP problem

In this section, we formulate the RNP as a nonlinear programming problem. Consider the WMN described in the perivous section. Given and are the sets of coordinates of n clients and k gateway routers. The RNP problem is stated as finding a set which is a set of coordinates for placing m mesh routers to achieve the specific objectives. In our context, the objectives of the RNP problem are to maximize NC and minimize COR. Consequently, The RNP problem is formulated as a nonlinear programming problem as follows:(7)subject to(8)(9)where lb_x, lb_y and ub_x, ub_y are the lower and upper bounds of search space and .

Most previous studies have chosen at search space for the entire network area. This option is reasonable for determining the coordinate solution for mesh routers. However, this is not optimal because in some cases, the router positions are close to the boundaries. In this case, approximately half of the mesh routers’ coverage area extends beyond the network area. This squanders the network resources. In this study, the search space is shrunk enough to cover clients that are close to the boundaries. This reduces the computational complexity and optimizes network resource usage. To determine the optimal lower and upper bounds for the search space, we consider the case in which the client is farthest from the center, that is, at the origin of the network space, as shown in Fig 3. In this case, the router position shown in Fig 3 is sufficient to cover the client, whereas coverage beyond the network area is minimal. The lower and upper bounds of the search space and are determined as follows: (10)(11)(12)where d_cr is the coverage radius of the routers and W and H are the width and height of the network area, respectively.

[Figure omitted. See PDF.]

Proposed method

In this section, we present a new method to solve the RNP problem. Our idea was to solve the RNP problem in two stages using an approximate optimization algorithm with fewer variables than the original RNP problem. The first stage places 15% to 20% of the mesh routers in the network area to form a core network with the widest coverage area. Therefore, the objective function of this stage focuses on minimizing COR. Mesh routers that have been successfully placed at this stage act as gateways for the remaining routers that are placed at the next stage. The objective function focuses on maximizing the NC used for the second stage to place all remaining routers in the network area.

Objective function

As discussed in Section 1, the objective of the NRP problem in our context is to optimize two metrics: NC and COR. Because most approximate optimization algorithms are designed to solve single-objective minimization problems, the objective function is constructed as follows:(13)where λ is a coefficient in the range [0, 1], that is used to control the optimal degree of the metrics.

Algorithm 1 Solving RNP problem by Combining Approximate Algorithms and Network Classification

Input:

 • Set of clients: C = {c_i|i = 1..n} and their coordinates: ;

 • Set of gateway routers: W = {w_i|i = 1..k} and their coordinates: ;

• Set of mesh routers: R = {r_i|i = 1..m};

• Size of network area: W × H;

Output: The best coordinates to place m mesh routers: ;

Method:

// Stage 1

1: Select mesh routers for set from set R;

2: λ ← 0.1;

3: ;

4: Use an approximate optimization algorithm to solve the RNP problem with input: C, , , d_cr, W, H. Output: ;

// Stage 2

5: for (each mesh router ) do

6:  if (r_i is not connected to any gateway router) then

7:   ;

8:   ;

9:  end if

10: end for

11: λ ← 0.9;

12: ;

13: Determine which clients are already covered by routers in set , denoted by set C_covered;

14: C ← C∖{C_covered};

15: Use an approximate optimization algorithm to solve the RNP problem with input: C, , , d_cr, W, H. Output: ;

16: ;

Proposed algorithm

Algorithm 1 is the pseudo-code of the algorithm used to solve the RNP problem by combining approximate optimization algorithms and network classification. In the first stage, λ coefficient in objective function (13) is set to 0.1 to focus on minimizing COR metric. The goal of this stage is to find coordinates to place mesh routers to form a core network with the largest coverage area. The mesh routers placed in this stage act as gateways for the mesh routers placed in the second stage. In the second stage, λ coefficient in the objective function (13) is set to 0.9 to focus on optimizing the NC metric. This allows finding coordinates to place all remaining mesh routers so that the number of clients covered is maximized.

Performance evaluation

Simulation scenarios

We implemented a simulation using Python programming language to evaluate the performance of the proposed method. All experiments were carried out on a 3.3 GHz Core i7 CPU machine. Our method is compared with the well-known RNP problem-solving method that employs approximate optimization algorithms, WOA [32] and MVO [33]. All methods are implemented in Python. The simulation assumptions are presented in Table 1. Simulation scenarios are performed in a network area from 2000 × 2000 [m²] to 2500 × 2500 [m²]. The number of mesh routers varies from 20 to 45 with a step of 2, and the number of mesh clients varies from 100 to 400 with a step of 25 The parameters of the approximate optimization algorithms are presented in Table 2. These parameters are set as in [8] to provide a basis for comparing simulation results. Because of the randomness of the approximate optimization algorithms, to ensure the accuracy of the simulation results, we execute each scenario 50 times. The results presented in this section are averages of 50 runs.

[Figure omitted. See PDF.]

[Figure omitted. See PDF.]

Simulation results

First, we compare the network topologies obtained using the proposed method versus the traditional method. The results shown in Figs 4 and 5, are performed for the simulation scenario where the number of mesh routers is 25, covering 200 clients in an network area of 2000 × 2000 m². We easily observe that the proposed method yields a more optimal topology than the traditional method for both cases where the MVO and WOA algorithms are used. Specifically, considering the case of the MVO algorithm (Fig 4), when using the traditional method, the topology obtained in Fig 4(a), 164 clients are covered, corresponding to a rate of 84%. If the proposed method is used, the number of clients covered is 177, corresponding to a rate of 89.78% (Fig 4(b)). The results are also completely similar for the case of using the WOA algorithm, as shown in Fig 5. The proportion of clients covered is 73.33% and 80.00% for the traditional method and the proposed method, respectively.

[Figure omitted. See PDF.]

(a) traditional method (one-stage) and (b) proposed method (two-stages).

[Figure omitted. See PDF.]

(a) traditional method (one-stage) and (b) proposed method (two-stages).

Next, we analyze an important metric that is often used to evaluate the effectiveness of the RNP problem solving method, NC, defined as (4). Fig 6 shows the variation of NC versus the number of mesh routers in the case where the number of clients is 150 and the MVO algorithm is used. In this figure, the legends labeled one-stage and two-stages represent the traditional and proposed methods, respectively. We can observe that with both methods, NC increases proportionally to the number of mesh routers, where the proposed method, two-stages, always yields a higher NC than that of the traditional method, one-stage. Considering of 20 mesh routers, the average NC values of the one-stage and two-stages methods are 75.84% and 79.81%, respectively. Thus, the two-stage method improved the NC by 3.97% compared to the one-stage method. When the number of mesh routers increase from 20 to 40, NC of both methods increases, in which the NC of the two-stages method is higher than that of the one-stage method with an average value of 3% to 5%. The specific values are shown in Table 3, where we summarize the statistical data of all 50 replicate runs for each simulation scenario. The increase of NC using the proposed method is a very significant result in improving the WMN performance.

[Figure omitted. See PDF.]

[Figure omitted. See PDF.]

In the case of using the WOA algorithm, the results are found as shown in Fig 7. Although NC is not achieved as in the case of the MOV algorithm, if comparing between two methods, the two-stages method always yields higher NC than the one-phase method when the number of mesh routers increases from 20 to 40. The specific data are shown in Table 4, where we compare both the mean, maximum, minimum and standard deviation of 50 replicate runs for each simulation scenario. For the average NC, the proposed method, two-stages, increases NC by 3.1% to 5.1%. compared to the traditional method, one-stage. The simulation scenario with 20 routers had the highest NC increase, at 12%. In this instance, the NCs of the traditional and new methods are 64.82% and 69.91%, respectively. For the remaining simulation scenarios, the average NC also increased significantly.

[Figure omitted. See PDF.]

[Figure omitted. See PDF.]

Another parameter that affects NC is the number of clients. We carefully investigated these scenarios with the number of clients varies from 100 to 400. As analyzed in Figs 4 and 5 about the obtained topologies, the two-stages method gives topologies with a wider coverage area than the 1-stage method. Therefore, the probability of the client being covered is higher, leading to increased NC. This is clearer from the results in Figs 8 and 9, where we plot NC as a function of the number of clients. Considering the case of using the MVO algorithm, the results are found as shown in Fig 8. We can easily observe that NC is inversely proportional to the number of clients for both methods. However, the two-stages method always outperforms the one-stage method in terms of NC. The average NC value increased by 4.03%. The results are also completely similar for the case of using the WOA algorithm, as shown in Fig 9, the average NC increases by an average of 3.98% if the two-stage method is used. The detailed data on the NC of the conventional method and the proposed method are clearly presented in Table 5, where we also summarize the simulation scenarios to determine the impact of the number of clients. It is evident that the suggested approach consistently yields a higher NC than the conventional method across all network instances with varying client counts.

[Figure omitted. See PDF.]

[Figure omitted. See PDF.]

[Figure omitted. See PDF.]

In the case of a larger network area, the proposed method also provides higher efficiency than the traditional method. This is verified by the results shown in Figs 10 and 11, where we analyze the data of all 50 runs. We can observe that the larger the network area, the larger the difference in NC between the two methods. This implies that the proposed method provides higher efficiency in case of larger network area. Considering the case of using 36 routers, the box charts in Fig 10 show that when the network area is 2000 × 2000 [m²], the median values of the one-stage and two-stage methods are 94.89% and 96.77%, respectively, a difference of 1.88%. These values are 74.48% and 80.42%, a difference of 5.94% for the case of a network area of 2500 × 2500 [m²].

[Figure omitted. See PDF.]

[Figure omitted. See PDF.]

Through the results analyzed above, we conclude that the proposed method, two-stages, is highly effective in terms of research compared to the traditional method, one-stage. This is a very meaningful result, contributing to improving the performance of WMN.

Conclusion

One of the methods to improve the WMN performance is to find the best solution to the RNP problem, that is, finding the best set of coordinates to place all mesh routers to achieve the given objectives. 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. This study proposed 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 built 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 of these sub-problems was solved using an approximate optimal algorithm. The experimental results demonstrate that our proposed method outperforms widely used NRP problem-solving methods in terms of network connectivity.

In future studies, we will further refine this approach by accounting for the additional quality of transmission limits and the mesh router load-balancing issue to enhance network performance.

Supporting information

S1 Dataset.

https://doi.org/10.1371/journal.pone.0318247.s001

(ZIP)

References

1. 1. Pragasen Mudali MOA. Context-Based Topology Control for Wireless Mesh Networks. Mobile Information Systems;2016:16 pages. https://doi.org/10.1155/2016/9696348

2. 2. Aron FO, Olwal TO, Kurien A, Odhiambo MO. Energy Efficient Topology Control Algorithm for Wireless Mesh Networks. In: 2008 International Wireless Communications and Mobile Computing Conference; 2008. p. 135–140.

3. 3. Vázquez-Rodas A, de la Cruz Llopis LJ. A centrality-based topology control protocol for wireless mesh networks. Ad Hoc Networks. 2015;24:34–54.

* View Article

* Google Scholar

4. 4. Binh L, Duong Thi Thuy V, Ngo V. TFACR: A Novel Topology Control Algorithm for Improving 5G-based MANET Performance by Flexibly Adjusting the Coverage Radius. IEEE Access. 2023;11:105734–105748.

* View Article

* Google Scholar

5. 5. Taleb SM, Meraihi Y, Gabis AB, Mirjalili S, Zaguia A, Ramdane-Cherif A. Solving the mesh router nodes placement in wireless mesh networks using coyote optimization algorithm. IEEE Access. 2022; p. 1–1.

* View Article

* Google Scholar

6. 6. Nouri N, Aliouat Z, Naouri A, Hassak S. Accelerated PSO algorithm applied to clients coverage and routers connectivity in wireless mesh networks. Journal of Ambient Intelligence and Humanized Computing. 2021.

* View Article

* Google Scholar

7. 7. Sayad L, Bouallouche-Medjkoune L, Aissani D. A Chemical Reaction Algorithm to Solve the Router Node Placement in Wireless Mesh Networks. Mob Netw Appl. 2020;25(5):1915–1928.

* View Article

* Google Scholar

8. 8. Binh LH, Truong TK. An Efficient Method for Solving Router Placement Problem in Wireless Mesh Networks Using Multi-Verse Optimizer Algorithm. Sensors. 2022;22(15). pmid:35897998

* View Article

* PubMed/NCBI

* Google Scholar

9. 9. Mekhmoukh Taleb S, Meraihi Y, Benmessaoud Gabis A, Mirjalili S, Ramdane-Cherif A. Nodes placement in wireless mesh networks using optimization approaches: a survey. Neural Computing and Applications. 2022;34.

* View Article

* Google Scholar

10. 10. Amaldi E, Capone A, Cesana M, Filippini I, Malucelli F. Optimization Models and Methods for Planning Wireless Mesh Networks. Computer Networks. 2008;52:2159–2171.

* View Article

* Google Scholar

11. 11. Xhafa F, Sánchez C, Barolli A, Takizawa M. Solving mesh router nodes placement problem in Wireless Mesh Networks by Tabu Search algorithm. Journal of Computer and System Sciences. 2015;81:1417–1428.

* View Article

* Google Scholar

12. 12. Bello OM, Taiwe KD. Mesh Node Placement in Wireless Mesh Network Based on Multiobjective Evolutionary Metaheuristic. In: Proceedings of the International Conference on Internet of Things and Cloud Computing. ICC’16. New York, NY, USA: Association for Computing Machinery; 2016.Available from: https://doi.org/10.1145/2896387.2896444.

13. 13. Sayad L, Bouallouche-Medjkoune L, Aissani D. A Simulated Annealing Algorithm for the placement of Dynamic Mesh Routers in a Wireless Mesh Network with Mobile Clients. Internet Technology Letters. 2018;1:e35.

* View Article

* Google Scholar

14. 14. Xhafa F, Barolli A, Sánchez C, Barolli L. A simulated annealing algorithm for router nodes placement problem in Wireless Mesh Networks. Simulation Modelling Practice and Theory. 2011;19(10):2276–2284.

* View Article

* Google Scholar

15. 15. Binh LH, Duong TVT. A Novel and Effective Method for Solving the Router Nodes Placement in Wireless Mesh Networks using Reinforcement Learning. PLOS ONE. 2024;19(4, e0301073). pmid:38598499

* View Article

* PubMed/NCBI

* Google Scholar

16. 16. Lin CC. Dynamic router node placement in wireless mesh networks: A PSO approach with constriction coefficient and its convergence analysis. Information Sciences. 2013;232:294–308.

* View Article

* Google Scholar

17. 17. Sayad L. Optimal placement of mesh routers in a wireless mesh network with mobile mesh clients using simulated annealing. In: 2017 5th International Symposium on Computational and Business Intelligence (ISCBI); 2017. p. 45–49.

18. 18. Seetha S, Anand John Francis S, Grace Mary Kanaga E. Optimal Placement Techniques of Mesh Router Nodes in Wireless Mesh Networks. In: Haldorai A, Ramu A, Mohanram S, Chen MY, editors. 2nd EAI International Conference on Big Data Innovation for Sustainable Cognitive Computing. Cham: Springer International Publishing; 2021. p. 217–226.

19. 19. Lin CC, Chen TH, Jhong SY. Wireless mesh router placement with constraints of gateway positions and QoS. In: 2015 11th International Conference on Heterogeneous Networking for Quality, Reliability, Security and Robustness (QSHINE); 2015. p. 72–74.

20. 20. Lin CC, Tseng PT, Wu TY, Deng DJ. Social-aware dynamic router node placement in wireless mesh networks. Wireless Networks. 2015;22.

* View Article

* Google Scholar

21. 21. Binh LH, Duong TVT. Load balancing routing under constraints of quality of transmission in mesh wireless network based on software defined networking. Journal of Communications and Networks. 2021;23(1):12–22.

* View Article

* Google Scholar

22. 22. Lahsen-Cherif I, Zitoune L, Veque V. Energy Efficient Routing for Wireless Mesh Networks with Directional Antennas: When Q-learning meets Ant systems. Ad Hoc Networks. 2021;121:102589.

* View Article

* Google Scholar

23. 23. Dai L, Xue Y, Chang B, Cao Y, Cui Y. Optimal Routing for Wireless Mesh Networks With Dynamic Traffic Demand. Mobile Networks and Applications. 2008;13:97–116.

* View Article

* Google Scholar

24. 24. Duong TVT, Binh LH, Ngo VM. Reinforcement learning for QoS-guaranteed intelligent routing in Wireless Mesh Networks with heavy traffic load. ICT Express. 2022;8(1):18–24.

* View Article

* Google Scholar

25. 25. Ding R, Xu Y, Gao F, Shen X, Wu W. Deep Reinforcement Learning for Router Selection in Network With Heavy Traffic. IEEE Access. 2019;7:37109–37120.

* View Article

* Google Scholar

26. 26. Raschellà A, Bouhafs F, Mackay M, Shi Q, Ortin J, Gallego JR, et al. A Dynamic Access Point Allocation Algorithm for Dense Wireless LANs Using Potential Game. Computer Networks. 2019;167:106991.

* View Article

* Google Scholar

27. 27. Kumar G, Chigarapalle S. A Study on Access Point Selection Algorithms in Wireless Mesh Networks. International Journal of Advanced Networking and Applications. 2014;6:2158–2167.

* View Article

* Google Scholar

28. 28. Kim MS, Kim Y, Lee SS, Lee S, Golmie N. A user application-based access point selection algorithm for dense WLANs. PLoS ONE. 2019;14. pmid:30650150

* View Article

* PubMed/NCBI

* Google Scholar

29. 29. Eberhart RC, Shi Y. Comparing inertia weights and constriction factors in particle swarm optimization. In: Proceedings of the 2000 Congress on Evolutionary Computation. CEC00 (Cat. No.00TH8512). vol. 1; 2000. p. 84–88 vol.1.

30. 30. Taleb MYMSea S M. Mesh Router Nodes Placement for Wireless Mesh Networks Based on an Enhanced Moth–Flame Optimization Algorithm. Mobile Networks and Applications. 2023;28:518–541.

* View Article

* Google Scholar

31. 31. Sakamoto S. Implementation of a cuckoo search intelligent simulation system for node placement problem in wireless mesh networks: Performance evaluation for tuning hyperparameters Pa and γ. Internet of Things. 2024; p. 101288.

* View Article

* Google Scholar

32. 32. Mirjalili S, Lewis A. The whale optimization algorithm. Advances in engineering software. 2016;95:51–67.

* View Article

* Google Scholar

33. 33. Mirjalili S, Mirjalili SM, Hatamlou A. Multi-verse optimizer: a nature-inspired algorithm for global optimization. Neural Computing and Applications. 2016;27(2):495–513.

* View Article

* Google Scholar

Citation: Binh LH, T. Duong T-V, M. Ngo V (2025) A novel approach for the router nodes placement in wireless mesh networks using phasing with approximation optimization algorithms. PLoS ONE 20(1): e0318247. https://doi.org/10.1371/journal.pone.0318247

About the Authors:

Le Huu Binh

Contributed equally to this work with: Le Huu Binh, Thuy-Van T. Duong

Roles: Conceptualization, Investigation, Methodology, Software, Writing – original draft, Writing – review & editing

Affiliation: Faculty of Information Technology, University of Sciences, Hue University, Hue City, Vietnam

ORICD: https://orcid.org/0000-0002-0951-4046

Thuy-Van T. Duong

Contributed equally to this work with: Le Huu Binh, Thuy-Van T. Duong

Roles: Conceptualization, Methodology, Writing – original draft, Writing – review & editing

E-mail: [email protected]

Affiliation: Faculty of Information Technology, Ton Duc Thang University, Ho Chi Minh City, Vietnam

ORICD: https://orcid.org/0000-0002-4619-5371

Vuong M. Ngo

Roles: Methodology, Software, Writing – original draft

Affiliation: Ho Chi Minh City Open University, Ho Chi Minh City, Vietnam

[/RAW_REF_TEXT]

[/RAW_REF_TEXT]

[/RAW_REF_TEXT]

[/RAW_REF_TEXT]

[/RAW_REF_TEXT]

[/RAW_REF_TEXT]

[/RAW_REF_TEXT]

References

1. Pragasen Mudali MOA. Context-Based Topology Control for Wireless Mesh Networks. Mobile Information Systems;2016:16 pages. https://doi.org/10.1155/2016/9696348

2. Aron FO, Olwal TO, Kurien A, Odhiambo MO. Energy Efficient Topology Control Algorithm for Wireless Mesh Networks. In: 2008 International Wireless Communications and Mobile Computing Conference; 2008. p. 135–140.

3. Vázquez-Rodas A, de la Cruz Llopis LJ. A centrality-based topology control protocol for wireless mesh networks. Ad Hoc Networks. 2015;24:34–54.

4. Binh L, Duong Thi Thuy V, Ngo V. TFACR: A Novel Topology Control Algorithm for Improving 5G-based MANET Performance by Flexibly Adjusting the Coverage Radius. IEEE Access. 2023;11:105734–105748.

5. Taleb SM, Meraihi Y, Gabis AB, Mirjalili S, Zaguia A, Ramdane-Cherif A. Solving the mesh router nodes placement in wireless mesh networks using coyote optimization algorithm. IEEE Access. 2022; p. 1–1.

6. Nouri N, Aliouat Z, Naouri A, Hassak S. Accelerated PSO algorithm applied to clients coverage and routers connectivity in wireless mesh networks. Journal of Ambient Intelligence and Humanized Computing. 2021.

7. Sayad L, Bouallouche-Medjkoune L, Aissani D. A Chemical Reaction Algorithm to Solve the Router Node Placement in Wireless Mesh Networks. Mob Netw Appl. 2020;25(5):1915–1928.

8. Binh LH, Truong TK. An Efficient Method for Solving Router Placement Problem in Wireless Mesh Networks Using Multi-Verse Optimizer Algorithm. Sensors. 2022;22(15). pmid:35897998

9. Mekhmoukh Taleb S, Meraihi Y, Benmessaoud Gabis A, Mirjalili S, Ramdane-Cherif A. Nodes placement in wireless mesh networks using optimization approaches: a survey. Neural Computing and Applications. 2022;34.

10. Amaldi E, Capone A, Cesana M, Filippini I, Malucelli F. Optimization Models and Methods for Planning Wireless Mesh Networks. Computer Networks. 2008;52:2159–2171.

11. Xhafa F, Sánchez C, Barolli A, Takizawa M. Solving mesh router nodes placement problem in Wireless Mesh Networks by Tabu Search algorithm. Journal of Computer and System Sciences. 2015;81:1417–1428.

12. Bello OM, Taiwe KD. Mesh Node Placement in Wireless Mesh Network Based on Multiobjective Evolutionary Metaheuristic. In: Proceedings of the International Conference on Internet of Things and Cloud Computing. ICC’16. New York, NY, USA: Association for Computing Machinery; 2016.Available from: https://doi.org/10.1145/2896387.2896444.

13. Sayad L, Bouallouche-Medjkoune L, Aissani D. A Simulated Annealing Algorithm for the placement of Dynamic Mesh Routers in a Wireless Mesh Network with Mobile Clients. Internet Technology Letters. 2018;1:e35.

14. Xhafa F, Barolli A, Sánchez C, Barolli L. A simulated annealing algorithm for router nodes placement problem in Wireless Mesh Networks. Simulation Modelling Practice and Theory. 2011;19(10):2276–2284.

15. Binh LH, Duong TVT. A Novel and Effective Method for Solving the Router Nodes Placement in Wireless Mesh Networks using Reinforcement Learning. PLOS ONE. 2024;19(4, e0301073). pmid:38598499

16. Lin CC. Dynamic router node placement in wireless mesh networks: A PSO approach with constriction coefficient and its convergence analysis. Information Sciences. 2013;232:294–308.

17. Sayad L. Optimal placement of mesh routers in a wireless mesh network with mobile mesh clients using simulated annealing. In: 2017 5th International Symposium on Computational and Business Intelligence (ISCBI); 2017. p. 45–49.

18. Seetha S, Anand John Francis S, Grace Mary Kanaga E. Optimal Placement Techniques of Mesh Router Nodes in Wireless Mesh Networks. In: Haldorai A, Ramu A, Mohanram S, Chen MY, editors. 2nd EAI International Conference on Big Data Innovation for Sustainable Cognitive Computing. Cham: Springer International Publishing; 2021. p. 217–226.

19. Lin CC, Chen TH, Jhong SY. Wireless mesh router placement with constraints of gateway positions and QoS. In: 2015 11th International Conference on Heterogeneous Networking for Quality, Reliability, Security and Robustness (QSHINE); 2015. p. 72–74.

20. Lin CC, Tseng PT, Wu TY, Deng DJ. Social-aware dynamic router node placement in wireless mesh networks. Wireless Networks. 2015;22.

21. Binh LH, Duong TVT. Load balancing routing under constraints of quality of transmission in mesh wireless network based on software defined networking. Journal of Communications and Networks. 2021;23(1):12–22.

22. Lahsen-Cherif I, Zitoune L, Veque V. Energy Efficient Routing for Wireless Mesh Networks with Directional Antennas: When Q-learning meets Ant systems. Ad Hoc Networks. 2021;121:102589.

23. Dai L, Xue Y, Chang B, Cao Y, Cui Y. Optimal Routing for Wireless Mesh Networks With Dynamic Traffic Demand. Mobile Networks and Applications. 2008;13:97–116.

24. Duong TVT, Binh LH, Ngo VM. Reinforcement learning for QoS-guaranteed intelligent routing in Wireless Mesh Networks with heavy traffic load. ICT Express. 2022;8(1):18–24.

25. Ding R, Xu Y, Gao F, Shen X, Wu W. Deep Reinforcement Learning for Router Selection in Network With Heavy Traffic. IEEE Access. 2019;7:37109–37120.

26. Raschellà A, Bouhafs F, Mackay M, Shi Q, Ortin J, Gallego JR, et al. A Dynamic Access Point Allocation Algorithm for Dense Wireless LANs Using Potential Game. Computer Networks. 2019;167:106991.

27. Kumar G, Chigarapalle S. A Study on Access Point Selection Algorithms in Wireless Mesh Networks. International Journal of Advanced Networking and Applications. 2014;6:2158–2167.

28. Kim MS, Kim Y, Lee SS, Lee S, Golmie N. A user application-based access point selection algorithm for dense WLANs. PLoS ONE. 2019;14. pmid:30650150

29. Eberhart RC, Shi Y. Comparing inertia weights and constriction factors in particle swarm optimization. In: Proceedings of the 2000 Congress on Evolutionary Computation. CEC00 (Cat. No.00TH8512). vol. 1; 2000. p. 84–88 vol.1.

30. Taleb MYMSea S M. Mesh Router Nodes Placement for Wireless Mesh Networks Based on an Enhanced Moth–Flame Optimization Algorithm. Mobile Networks and Applications. 2023;28:518–541.

31. Sakamoto S. Implementation of a cuckoo search intelligent simulation system for node placement problem in wireless mesh networks: Performance evaluation for tuning hyperparameters Pa and γ. Internet of Things. 2024; p. 101288.

32. Mirjalili S, Lewis A. The whale optimization algorithm. Advances in engineering software. 2016;95:51–67.

33. Mirjalili S, Mirjalili SM, Hatamlou A. Multi-verse optimizer: a nature-inspired algorithm for global optimization. Neural Computing and Applications. 2016;27(2):495–513.