Performance evaluation of six mesh router replacement methods for wireless mesh networks: A comparison study for small and middle scale networks considering two islands distribution of mesh clients

Abstract

In this paper, we present a hybrid intelligent simulation system for optimization of mesh routers in Wireless Mesh Networks (WMNs) called WMN-PSOHCDGA. We implemented six mesh router replacement methods: CM, RIWM, LDIWM, LDVM, RDVM and FC-RDVM and consider Two Islands distribution of mesh clients. We carry out a comparison study of these router replacement methods for small and middle scale WMNs. We assessed the performance by computer simulations. The simulation results show that six methods have a good performance for connectivity and coverage metrics, for both small and middle scale WMNs. However, they have different behavior for load balancing. For small scale WMNs, the load balancing of LDIWM, RIWM and FC-RDVM is better than CM, LDVM and RDVM. While, comparing LDIWM, RIWM and FC-RDVM, the LDIWM has better load balancing. We found that the load balancing for small scale WMNs is not good, because there is a concentration of mesh routers in some areas. For middle scale WMNs, the CM, LDIWM, LDVM and RDVM have not a good load balancing. While, the RIWM and FC-RDVM have better performance. Comparing RIWM and FC-RDVM, we found that the load balancing of FC-RDVM is better than RIWM.

Keywords

Wireless mesh networks mesh router replacement methods two islands distribution intelligent algorithms hybrid intelligent simulation system

1. Introduction

Networks of today are going through rapid evolution and there are appearing different kinds of wireless networks, which have different kind of applications. One of them are Wireless Mesh Networks (WMNs), which can be used for last-mile networks and edge computing. They are cost-effective and have good scalability, fault-tolerance, and load distribution capabilities. WMNs are well-suited for linking edge devices and can provide enhanced analytics capabilities, improved response times, better performance, and increased security and privacy.

For design and optimization process of WMNs are needed different parameters including mesh router connectivity, mesh client coverage, Quality of Service (QoS), and network cost, which make the problem NP-Hard. Therefore, it is needed a trade-off among these parameters and this can be done by intelligent and heuristic approaches.

For mesh router node placement problem, the objective is to assign the mesh router nodes in the grid area in order to achieve optimal network connectivity and client coverage while also balancing the load of mesh routers. In order to measure these metrics, we consider three parameters: Size of Giant Component (SGC), Number of Covered Mesh Clients (NCMC), Number of Covered Mesh Clients per Router (NCMCpR).

Node placement problems are known to be computationally hard to solve [2,4–6,13]. In some previous works, there are some intelligent algorithms, which have been investigated for the node placement problem [1,3,7,9].

In our previous work [10,11], we implemented some intelligent simulation systems for solving the node placement problem in WMNs by considering single intelligent algorithms such as Particle Swarm Optimization (PSO), Hill Climbing (HC), Genetic Algorithms (GAs), Simulated Annealing (SA) and so on. Then, we designed and implemented a hybrid simulation system based on PSO and Distributed GA (DGA) called WMN-PSODGA.

In this paper, we present a new hybrid intelligent system for Wireless Mesh Networks (WMNs) called WMN-PSOHCDGA by integrating three intelligent algorithms: PSO, HC and Distributed Genetic Algorithm (DGA). We implemented in WMN-PSOHCDGA system six mesh router replacement methods: Constriction Method (CM), Random Inertia Weight Method (RIWM), Linearly Decreasing Inertia Weight Method (LDIWM), Linearly Decreasing Vmax Method (LDVM), Rational Decrement of Vmax Method (RDVM) and Fast Convergence Rational Decrement of Vmax Method (FC-RDVM).

We compare the results of these six methods considering Two Islands distribution of mesh clients and different instances (different scales of WMNs). The simulation results show that for small scale WMNs, the load balancing of LDIWM, RIWM and FC-RDVM is better than CM, LDVM and RDVM. While, comparing LDIWM, RIWM and FC-RDVM, the LDIWM has better load balancing. We found that the load balancing for small scale WMNs is not good, because there is a concentration of mesh routers in some areas. For middle scale WMNs, the CM, LDIWM, LDVM and RDVM have not a good load balancing. While, the RIWM and FC-RDVM have better performance. Comparing RIWM and FC-RDVM, we found that the load balancing of FC-RDVM is better than RIWM.

The contributions of this research work are as follows.

Design and implementation of WMN-PSOHCDGA hybrid simulation system by integrating three intelligent algorithms: PSO, HC and DGA. The implemented system can be used for different scenarios during engineering and deployment phase of WMNs.

Implementation in WMN-PSOHCDGA system of six mesh router replacement methods, which make the proposed system applicable in different environments.

Consideration of two instances, which make the proposed system applicable in small and middle scale WMNs.

The proposed WMN-PSOHCDGA system assessment is verified by extensive simulation results.

The rest of the paper is organized as follows. In Section 2 are introduced PSO, HC and DGA algorithms. Section 3 presents WMN-PSOHCDGA simulation system. The simulation results are given in Section 4. Finally, we give conclusions and future work in Section 5.

2. PSO, HC and DGA intelligent algorithms

In this section, we introduce three algorithms, which are combined to implement the proposed hybrid intelligent system.

2.1. Particle swarm optimization

In PSO, a group of particles are used to find solutions in the search space of a given problem. The movement of these particles is inspired by the collective behaviour of different species. They collaborate together to find food or migrate to a better environment. The optimal solution is achieved by the interaction of particles in the flock or group.

Each particle determines the movement towards the optimal solution by using the best-known location, the best location achieved by other flock members (best fitness), and random perturbations. The particle communicate with each other particles and are influenced by the best point found by any member of the group. Thus, all members of the group converge to the optimal solution.

2.2. Hill climbing algorithm

The HC is a local search and heuristic algorithm used for optimization problems. The HC tries to find a sufficiently good solution to the problem, but this may not be the global optimal solution.

In HC, the local search algorithm continuously moves in the direction of finding the peak of the mountain or the best solution to the problem. The algorithm terminates when it reaches a peak value where no neighbor has a higher value.

The HC has many applications. Especially is used for optimizing the mathematical problems. One of the widely considered examples is traveling-salesman problem, which try to minimize the distance traveled by the salesman. The HC is also called greedy local search because considers only its good immediate neighbor state not beyond that. In HC algorithm, it is not needed to maintain and handle the search tree or graph because the algorithm only keeps a single current state.

2.3. Distributed genetic algorithm

Genetic Algorithms (GA) is a robust search technique and has the ability to avoid falling prematurely into local optimas. GA is used and applied to various optimization problems in different domains. However, GAs are computationally expensive and time-consuming.

In our hybrid intelligent system, we use Distributed GA (DGA), which has a mechanism to escape from local optima by considering multiple islands. In DGA, each island computes its own solution and then migrate them as shown in Fig. 1. The GA has many operators, but the main operators are Selection, Crossover and Mutation. We have implemented different operators in our simulations system.

Fig. 1.

Model of migration in DGA.

3. Structure of WMN-PSOHCDGA simulation system

In this section, we present the proposed WMN-PSOHCDGA simulation system. We combine three intelligent algorithms (PSO, HC and DGA) by considering their advantages and implement an hybrid intelligent system.

Fig. 2.

Flowchart of WMN-PSOHCDGA system.

We show the flowchart of the proposed system in Fig. 2. The proposed system starts by generating the initial solution randomly by ad hoc methods [14]. Then, it optimizes each island by using DGA and PSO algorithms. Finally, the HC algorithm is used to improve the convergence of PSO algorithm. The most crucial aspect of HC is defining the neighbour solution, which directly impacts the performance of the HC algorithm. In our WMN-PSOHCDGA system, we use the next locations of particle-pattern as the neighbour solutions.

The system includes these components: initialization, particle-pattern, fitness function, distribution of mesh clients and replacement methods.

The velocity of particles is determined by a random process, which considers the area size. For example, when the area size is $W \times H$ , the velocity is randomly chosen between $- \sqrt{W^{2} + H^{2}}$ and $\sqrt{W^{2} + H^{2}}$ .

We consider a particle as a mesh router. The fitness value of a particle-pattern is computed by combination of mesh routers and mesh clients positions. Each particle-pattern is a solution as shown is Fig. 3. We represent a WMN by a gene and each individual in the population is a combination of mesh routers.

Fig. 3.

Relationship among global solution, particle-patterns, and mesh routers in PSO part.

The fitness function of WMN-PSOHCDGA considers three metrics (SGC, NCMC and NCMCpR) together with their weight coefficients (α, β, and γ), where $α + β + γ = 1$ . $\begin{array}{r} Fitness = α \times SGC (x_{i j}, y_{i j}) + β \times NCMC (x_{i j}, y_{i j}) + γ \times NCMCpR (x_{i j}, y_{i j}) . \end{array}$

In this work, we consider Two Islands distribution of mesh clients, which considers users located as shown in Fig. 4.

Fig. 4.

Two islands distribution of mesh clients.

There are many mesh router replacing methods for WMNs. In this paper, we consider six of them: CM, RIWM, LDIWM, LDVM, RDVM and FC-RDVM

In CM, PSO parameters are set to a week stable region ( $ω = 0.729$ , $C_{1} = C 2 = 1.4955$ ).

In RIWM, the ω parameter is changed in random way from 0.5 to 1.0. The $C_{1}$ and $C_{2}$ are kept 2.0, while ω is estimated by the weak stable region and its average value is 0.75.

In LDIWM, $C_{1}$ and $C_{2}$ are constant parameters and are set to 2.0. While, ω parameter is changed linearly from unstable region ( $ω = 0.9$ ) to stable region ( $ω = 0.4$ ).

In LDVM, PSO parameters are set to unstable region ( $ω = 0.9$ , $C_{1} = C_{2} = 2.0$ ). A value of $V_{max}$ which is maximum velocity of particles is considered. With increasing of iteration of computations, the $V_{max}$ is kept decreasing linearly [12]. The $V_{max}$ is defined as shown in Eq. (1). $\begin{matrix} (1) & V_{max} (k) = \sqrt{W^{2} + H^{2}} \times \frac{T - k}{T} \end{matrix}$ Where W and H are the width and the height of the considered area, respectively. While, T and k are the total number of iterations and a current number of iteration, respectively. The k is a variable varying from 1 to T, which is increased by increasing the iterations.

In RDVM, PSO parameters are set to unstable region ( $ω = 0.9$ , $C_{1} = C_{2} = 2.0$ ) and the $V_{max}$ is decreasing with the increase of iterations as shown in Eq. (2). $\begin{matrix} (2) & V_{max} (x) = \sqrt{W^{2} + H^{2}} \times \frac{T - x}{x} . \end{matrix}$ Where, W and H are the width and the height of the considered area, while T and x are the total number of iterations and a current number of iteration, respectively.

In FC-RDVM [8], we consider $V_{max}$ , which is maximum velocity of particles, which decreases with the increasing of iterations as shown in Eq. (3). $\begin{matrix} (3) & V_{max} (k) = \sqrt{W^{2} + H^{2}} \times \frac{T - k}{T + δ k} \end{matrix}$ In Eq. (3), W and H are width and height of the considered area. While, T and k are the total number of iterations and the current number of iteration. Variable k is varying from 1 to T, which is increased by increasing the number of iterations. While, δ is a curvature parameter.

4. Simulation results

In order to assess the performance of considered router replacement methods by computer simulations. For simulations, we set the coefficients of the fitness function as $α = 0.8$ , $β = 0.1$ , and $γ = 0.1$ . All other parameter settings are shown in Table 1.

Table 1
Simulation parameters

Parameters Values

Small scale WMN Middle scale WMN

$α : β : γ$ 8 : 1 : 1

Number of GA islands 16

Evolution steps 9

Number of migrations 300

Number of mesh routers 16 32

Number of mesh clients 48 96

Mesh client distribution Two islands distribution

Selection method Rulette selection method

Corssover method UNDX

Mutation method Boundary mutation

Parameters	Values
$α : β : γ$	8 : 1 : 1
Number of GA islands	16
Evolution steps	9
Number of migrations	300
Number of mesh routers	16	32
Number of mesh clients	48	96
Mesh client distribution	Two islands distribution
Selection method	Rulette selection method
Corssover method	UNDX
Mutation method	Boundary mutation

We show the visualization results for small scale WMNs in Fig. 5. The simulation results show that six methods have a good performance for connectivity and coverage metrics. So, all mesh routers are connected and all mesh clients are covered.

We show the indicator of load balancing for small scale WMNs in Fig. 6. The parameter r is the correlation coefficient. When the standard deviation is decreased with the increase of the number of updates, the load balancing among mesh routers is better. We can see that the router replacement methods show different performance on load balancing. Considering six router replacement methods, The load balancing of LDIWM, RIWM and FC-RDVM is better than CM, LDVM and RDVM. While, comparing LDIWM, RIWM and FC-RDVM, the LDIWM has better load balancing. We found that the load balancing for small scale WMNs is not good, because there is a concentration of mesh routers in some areas.

We show the visualization results for middle scale WMNs in Fig. 7. For middle scale WMNs, also all router replacements methods show a good performance for SCC and NCMC. However, compared with Fig. 5, the mesh routers have better distribution.

We show the indicator of load balancing for middle scale networks in Fig. 8. For middle scale WMNs, in the case of CM, LDIWM, LDVM and RDVM, the standard deviation is an increasing line. While for RIWM and FC-RDVM, it is a decreasing line. Comparing RIWM and FC-RDVM, we see that the load balancing of FC-RDVM is better than RIWM.

5. Conclusions

In this work, we assessed the performance of six mesh router replacement methods (CM, RIWM, LDIWM, LDVM, RDVM and FC-RDVM) for WMNs using a hybrid intelligent simulation system by integrating PSO, HC and DGA algorithms called WMN-PSOHCDGA. We considered Two Islands distribution of mesh clients and carried out a comparison study of six router replacement methods for small and middle scale WMNs.

The simulation results have shown that six methods have a good performance for connectivity and coverage metrics, for both small and middle scale networks. However, they have different behavior for load balancing.

For small scale WMNs, the load balancing of LDIWM, RIWM and FC-RDVM is better than CM, LDVM and RDVM. While, comparing LDIWM, RIWM and FC-RDVM, the LDIWM has better load balancing. We found that the load balancing for small scale WMNs is not good, because there is a concentration of mesh routers in some areas.

For middle scale WMNs, the CM, LDIWM, LDVM and RDVM did not have a good load balancing. While, the RIWM and FC-RDVM have better performance. Comparing RIWM and FC-RDVM, the load balancing of FC-RDVM was better than RIWM.

In future work, we will consider the implementation of different crossover, mutation and other router replacement methods. We also will consider less number of mesh routers and carry out simulations for small scale WMNs. Furthermore, we plan to implement a testbed and compare the simulation results with experimental results.

Fig. 5.

Visualization results after optimization (small scale WMN).

Fig. 6.

Standard deviation, regression line and correlation coefficient (small scale WMN).

Fig. 7.

Visualization results after optimization (middle scale WMN).

Fig. 8.

Standard deviation, regression line and correlation coefficient (middle scale WMN).

Conflict of interest

The author has no conflict of interest to report.

References

Barolli,

Sakamoto,

Ozera,

Barolli,

Kulla and

Takizawa, Design and implementation of a hybrid intelligent system based on particle swarm optimization and distributed genetic algorithm, in: International Conference on Emerging Internetworking, Data & Web Technologies, Springer, 2018, pp. 79–93.

A.A.

Franklin and

C.S.R.

Murthy, Node placement algorithm for deployment of two-tier wireless mesh networks, in: Proc. of Global Telecommunications Conference, IEEE, 2007, pp. 4823–4827.

M.R.

Girgis,

T.M.

Mahmoud,

B.A.

Abdullatif and

A.M.

Rabie, Solving the wireless mesh network design problem using genetic algorithm and simulated annealing optimization methods, International Journal of Computer Applications 96(11) (2014), 1–10. doi:10.5120/16835-6680.

Lim,

Rodrigues,

Wang and

Xu, k-center problems with minimum coverage, Theoretical Computer Science 332(1–3) (2005), 1–17.

Maolin

et al., Gateways placement in backbone wireless mesh networks, International Journal of Communications, Network and System Sciences 2(1) (2009), 44–50. doi:10.4236/ijcns.2009.21005.

S.N.

Muthaiah and

C.P.

Rosenberg, Single gateway placement in wireless mesh networks, in: Proc. of 8th International IEEE Symposium on Computer Networks, 2008, pp. 4754–4759.

Naka,

Genji,

Yura and

Fukuyama, A hybrid particle swarm optimization for distribution state estimation, IEEE Transactions on Power systems 18(1) (2003), 60–68. doi:10.1109/TPWRS.2002.807051.

Sakamoto,

Barolli,

Liu,

Kulla,

Barolli and

Takizawa, A fast convergence RDVM for router placement in WMNs: Performance comparison of FC-RDVM with RDVM by WMN-PSOHC hybrid intelligent system, in: International Conference on Computational Intelligence in Security for Information Systems Conference, Springer, 2022, pp. 17–25.

Sakamoto,

Kulla,

Oda,

Ikeda,

Barolli and

Xhafa, A comparison study of simulated annealing and genetic algorithm for node placement problem in wireless mesh networks, Journal of Mobile Multimedia 9(1–2) (2013), 101–110.

10.

Sakamoto,

Kulla,

Oda,

Ikeda,

Barolli and

Xhafa, A comparison study of hill climbing, simulated annealing and genetic algorithm for node placement problem in WMNs, Journal of High Speed Networks 20(1) (2014), 55–66. doi:10.3233/JHS-140487.

11.

Sakamoto,

Oda,

Ikeda,

Barolli and

Xhafa, Implementation and evaluation of a simulation system based on particle swarm optimisation for node placement problem in wireless mesh networks, International Journal of Communication Networks and Distributed Systems 17(1) (2016), 1–13. doi:10.1504/IJCNDS.2016.077935.

12.

J.F.

Schutte and

A.A.

Groenwold, A study of global optimization using particle swarms, Journal of Global Optimization 31(1) (2005), 93–108. doi:10.1007/s10898-003-6454-x.

13.

Wang,

Xie,

Cai and

D.P.

Agrawal, Efficient mesh router placement in wireless mesh networks, in: Proc. of IEEE Internatonal Conference on Mobile Adhoc and Sensor Systems (MASS-2007), IEEE, 2007, pp. 1–9.

14.

Xhafa,

Sanchez and

Barolli, Ad hoc and neighborhood search methods for placement of mesh routers in wireless mesh networks, in: Proc. of 29th IEEE International Conference on Distributed Computing Systems Workshops (ICDCS-2009), IEEE, 2009, pp. 400–405.

Parameters	Values

	Small scale WMN	Middle scale WMN
$α : β : γ$	8 : 1 : 1
Number of GA islands	16
Evolution steps	9
Number of migrations	300
Number of mesh routers	16	32
Number of mesh clients	48	96
Mesh client distribution	Two islands distribution
Selection method	Rulette selection method
Corssover method	UNDX
Mutation method	Boundary mutation