A comparison study of chi-square and uniform distributions of mesh clients for different router replacement methods using WMN-PSODGA hybrid intelligent simulation system

1.Introduction

The wireless networks and devices are becoming increasingly popular and they provide users access to information and communication anytime and anywhere [2, 10, 13, 16, 20, 23]. Wireless Mesh Networks (WMNs) are gaining a lot of attention because of their low-cost nature that makes them attractive for providing wireless Internet connectivity. A WMN is dynamically self-organized and self-configured, with the nodes in the network automatically establishing and maintaining mesh connectivity among itself (creating, in effect, an ad hoc network). This feature brings many advantages to WMN such as low up-front cost, easy network maintenance, robustness and reliable service coverage [1]. Moreover, such infrastructure can be used to deploy community networks, metropolitan area networks, municipal and corporative networks, and to support applications for urban areas, medical, transport and surveillance systems.

Mesh node placement in WMNs can be seen as a family of problems, which is shown (through graph theoretic approaches or placement problems, e.g. [8, 14]) to be computationally hard to solve for most of the formulations [27].

We consider the version of the mesh router nodes placement problem in which we are given a grid area where to deploy a number of mesh router nodes and a number of mesh client nodes of fixed positions (of an arbitrary distribution) in the grid area. The objective is to find a location assignment for the mesh routers to the cells of the grid area that maximizes the network connectivity, client coverage and consider load balancing for each router. Network connectivity is measured by Size of Giant Component (SGC) of the resulting WMN graph, while the user coverage is simply the number of mesh client nodes that fall within the radio coverage of at least one mesh router node and is measured by Number of Covered Mesh Clients (NCMC). For load balancing, we added in the fitness function a new parameter called NCMCpR (Number of Covered Mesh Clients per Router).

Node placement problems are known to be computationally hard to solve [11, 12, 28]. Machine learning and evolutionary-based algorithms are some practical approaches capable of solving computationally hard problems. These approaches, which have been applied to fields ranging from networking and telecommunications to automation and power control systems [5, 7], are investigated for node placement problems in several previous works [3, 9, 15, 18].

In [21], we implemented a Particle Swarm Optimization (PSO) based simulation system, called WMN-PSO. Also, we implemented another simulation system based on Genetic Algorithm (GA), called WMN-GA [19], for solving node placement problem in WMNs. Then, we designed and implemented a hybrid simulation system based on PSO and Distributed GA (DGA). We call this system WMN-PSODGA.

Using the WMN-PSODGA, we can explore different router replacement methods and various distributions of mesh clients. This is important because each router replacement method does not achieve the same performance on every distribution of mesh clients. Moreover, every distribution of mesh clients yields different results for different WMN applications since the topology of a WMN can vary widely. In this paper, we compare the simulation results of chi-square and uniform distributions of mesh clients for different router replacement methods.

The rest of the paper is organized as follows. In Section 2, we introduce intelligent algorithms. In Section 3 is presented the implemented hybrid simulation system. The simulation results are given in Section 4. Finally, we give conclusions and future work in Section 5.

2.Intelligent algorithms

2.1.Particle swarm optimization

In PSO a number of simple entities (the particles) are placed in the search space of some problem or function and each evaluates the objective function at its current location. The objective function is often minimized and the exploration of the search space is not through evolution [17].

Each particle then determines its movement through the search space by combining some aspect of the history of its own current and best (best-fitness) locations with those of one or more members of the swarm, with some random perturbations. The next iteration takes place after all particles have been moved. Eventually the swarm as a whole, like a flock of birds collectively foraging for food, is likely to move close to an optimum of the fitness function.

Each individual in the particle swarm is composed of three D-dimensional vectors, where D is the dimensionality of the search space. These are the current position x→i, the previous best position p→i and the velocity v→i.

The particle swarm is more than just a collection of particles. A particle by itself has almost no power to solve any problem; progress occurs only when the particles interact. Problem solving is a population-wide phenomenon, emerging from the individual behaviors of the particles through their interactions. In any case, populations are organized according to some sort of communication structure or topology, often thought of as a social network. The topology typically consists of bidirectional edges connecting pairs of particles, so that if j is in i’s neighborhood, i is also in j’s. Each particle communicates with some other particles and is affected by the best point found by any member of its topological neighborhood. This is just the vector p→i for that best neighbor, which we will denote with p→g. The potential kinds of population “social networks” are hugely varied, but in practice certain types have been used more frequently. We show the pseudo code of PSO in Algorithm 1.

In the PSO process, the velocity of each particle is iteratively adjusted so that the particle stochastically oscillates around p→i and p→g locations.

Algorithm 1

Pseudo code of PSO

2.2.Distributed genetic algorithm

Classic GAs have proved their effectiveness in solving real-world optimization problems. However, in problems with a huge search space and with many local optima, they cannot guarantee success in finding the global optima. To successfully find the global optima, many different approaches can be used in combination with the classic GA. For example, the gradient-descent (GD) technique for local searching and constraints management has demonstrated great feasibility to provide high precision with reduced number of individuals and generations [6]. Distributed Genetic Algorithm (DGA), on the other hand, has shown their usefulness for the resolution of many computationally hard combinatorial optimization problems. We show the pseudo code of DGA in Algorithm 2.

Algorithm 2

Pseudo code of DGA

Population of individuals: Unlike local search techniques that construct a path in the solution space jumping from one solution to another one through local perturbations, DGA use a population of individuals giving thus the search a larger scope and chances to find better solutions. This feature is also known as “exploration” process in difference to “exploitation” process of local search methods.

Fitness: The determination of an appropriate fitness function, together with the chromosome encoding are crucial to the performance of DGA. Ideally we would construct objective functions with “certain regularities”, i.e. objective functions that verify that for any two individuals which are close in the search space, their respective values in the objective functions are similar.

Selection: The selection of individuals to be crossed is another important aspect in DGA as it impacts on the convergence of the algorithm. Several selection schemes have been proposed in the literature for selection operators trying to cope with premature convergence of DGA. There are many selection methods in GA. In our system, we implement 2 selection methods: Random method and Roulette wheel method.

Crossover operators: Use of crossover operators is one of the most important characteristics. Crossover operator is the means of DGA to transmit best genetic features of parents to offsprings during generations of the evolution process. Many methods for crossover operators have been proposed such as Blend Crossover (BLX-α), Unimodal Normal Distribution Crossover (UNDX), Simplex Crossover (SPX).

Mutation operators: These operators intend to improve the individuals of a population by small local perturbations. They aim to provide a component of randomness in the neighborhood of the individuals of the population. In our system, we implemented two mutation methods: uniformly random mutation and boundary mutation.

Escaping from local optima: GA itself has the ability to avoid falling prematurely into local optima and can eventually escape from them during the search process. DGA has one more mechanism to escape from local optima by considering some islands. Each island computes GA for optimizing and they migrate its gene to provide the ability to avoid from local optima (see Fig. 1).

Convergence: The convergence of the algorithm is the mechanism of DGA to reach to good solutions. A premature convergence of the algorithm would cause that all individuals of the population be similar in their genetic features and thus the search would result ineffective and the algorithm getting stuck into local optima. Maintaining the diversity of the population is therefore very important to this family of evolutionary algorithms.

Fig. 1.

Model of migration in DGA.

3.Proposed and implemented WMN-PSODGA hybrid intelligent simulation system

In this section, we present the proposed WMN-PSODGA hybrid intelligent simulation system. In the following, we describe the initialization, particle-pattern, gene coding, fitness function, and replacement methods. The pseudo code of our implemented system is shown in Algorithm 3. Also, our implemented simulation system uses Migration function as shown in Fig. 2. The Migration function swaps solutions among lands included in PSO part.

Algorithm 3

Pseudo code of WMN-PSODGA system

Fig. 2.

Model of WMN-PSODGA migration.

Initialization. We decide the velocity of particles by a random process considering the uniform sampling of the area size. For instance, when the area size is W×H, the velocity is decided randomly from −W2+H2 to W2+H2.

Particle-pattern. A particle is a mesh router. A fitness value of a particle-pattern is computed by combination of mesh routers and mesh clients positions. In other words, each particle-pattern is a solution as shown is Fig. 3.

Fig. 3.

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

Gene coding. A gene (individual) describes a WMN. As shown in Fig. 4, each individual has its own combination of mesh routers, which includes information about their position and communication distance. In other words, each individual has information over the WMN that can calculate the value of its fitness function. Therefore, each combination of these mesh routers is a solution.

Fig. 4.

Graphical representation of gene coding for a problem with N mesh routers using L islands and M individuals (DGA part).

Fitness function. WMN-PSODGA has the fitness function to evaluate the temporary solution of the router’s placements. The fitness function is defined as:

This function uses the following indicators.

WMN-PSODGA aims to maximize the value of the fitness function in order to optimize the placements of the routers using the above three indicators. Weight-coefficients of the fitness function are α, β, and γ for NCMC, SGC, and NCMCpR, respectively. Moreover, the weight-coefficients are implemented as α+β+γ=1.

Router replacement methods. A mesh router has x, y positions, and velocity. Mesh routers are moved based on velocities. There are many router replacement methods as showing in the following.

4.Simulation results

In this section, we compare the simulation results of chi-square and uniform distributions of mesh clients for different router replacement methods. The weight-coefficients of fitness function were adjusted for optimization. In this paper, the weight-coefficients are α=0.6, β=0.3, γ=0.1. The number of mesh routers is considered 16 and the number of mesh clients 48. Table 1 summarizes the common parameters used for simulation. Figure 5 and Fig. 6 show the visualization results after the optimization for chi-square distribution and uniform distribution, respectively. Figure 7 and Fig. 8 show the number of covered mesh clients by each router. Figure 9 and Fig. 10 show the standard deviation where r is the correlation coefficient.

As shown in Fig. 5, when using chi-square distribution, 16 mesh routers can cover all mesh clients for all router replacement methods. On the other hand, in Fig. 6, the simulation results show that for the uniform distribution, 16 mesh routers are not enough to cover all mesh clients regardless of router replacement method used. This can be seen also from Fig. 7 and Fig. 8. In Fig. 9 and Fig. 10, we can see which router replacement methods show better results for load balancing by comparing their standard deviations and their correlation coefficients. When the standard deviation is an increasing line (r>0), the number of mesh clients for each router tends to be different. On the other hand, when the standard deviation is a decreasing line (r<0), the number of mesh clients for each router tends to go close to each other. For chi-square distribution (see Fig. 9), CM, RIWM, LDIWM and LDVM have a positive correlation coefficient r, indicating that each of these router replacement methods does not show good load balancing. For this distribution, the best performance is achieved for RDVM. Figure 10 shows that when using uniform distribution, there are four router replacement methods (CM, RIWM, LDVM and RDVM) that show good load balancing, and only one (LDIWM) has a positive correlation coefficient. Among the four methods that give better results, RIWM is the one outperforming the other methods.

Fig. 5.

Visualization results after the optimization (chi-square distribution).

Fig. 6.

Visualization results after the optimization (uniform distribution).

Fig. 7.

Number of covered clients by each router after the optimization (chi-square distribution).

Fig. 8.

Number of covered clients by each router after the optimization (uniform distribution).

Fig. 9.

Transition of the standard deviations (chi-square distribution).

Fig. 10.

Transition of the standard deviations (uniform distribution).

5.Conclusions

In this work, we evaluated the performance of WMNs using a hybrid intelligent simulation system based on PSO and DGA (called WMN-PSODGA). We compared the simulation results of chi-square and uniform distributions of mesh clients for different router replacement methods: CM, RIWM, LDIWM, LDVM and RDVM.

The simulation results show that the uniform distribution makes a good load balancing for four router replacement methods, but the mesh routers do not cover all mesh clients. On the other hand, in terms of load balancing, the only method that shows poor results for this distribution is LDIWM. All other methods show satisfactory results, with RIWM showing slightly better results than the rest of methods. For chi-square distribution, the mesh routers can cover all mesh clients but this distribution has not good load balancing for four of the replacement methods. Nevertheless, RDVM does show good loading balancing results for this distribution, and this makes it the most adequate method. Thus, the best scenario is chi-square distribution of mesh clients with RDVM as a router replacement method.

In future work, we will consider other distributions of mesh clients such as normal, exponential and weibull distribution.

Conflict of interest

The authors have no conflict of interest to report.