Keywords

1 Introduction

Wireless Mesh Networks (WMNs) [1–3] are important network infrastructure for providing cost-efficient broadband wireless connectivity. They are showing their applicability in deployment of medical, transport and surveillance applications in urban areas, metropolitan, neighboring communities and municipal area networks. At the heart of WMNs are the issues of achieving network connectivity and stability as well as QoS in terms of user coverage. These issues are very closely related to the family of node placement problems in WMNs, such as mesh router nodes placement.

Node placement problems have been long investigated in the optimization field due to numerous applications in location science (facility location, logistics, services, etc.) and classification (clustering).

Facility location problems are thus showing their usefulness to communication networks, and more especially from WMNs field. WMNs are currently attracting a lot of attention from wireless research and technology community for providing cost-efficient broadband wireless connectivity.

WMNs are based on mesh topology, in which every node (representing a server) is connected to one or more nodes, enabling thus the information transmission in more than one path. The path redundancy is a robust feature of this kind of topology. Compared to other topologies, mesh topology needs not a central node, allowing networks based on such topology to be self-healing. These characteristics of networks with mesh topology make them very reliable and robust networks to potential server node failures. In WMNs mesh routers provide network connectivity services to mesh client nodes. The good performance and operability of WMNs largely depends on placement of mesh routers nodes in the geographical deployment area to achieve network connectivity, stability and user coverage. The objective is to find an optimal and robust topology of the mesh router nodes to support connectivity services to clients.

For most formulations, node placement problems are shown to be computationally hard to solve to optimality [4–7], and therefore heuristic and metaheuristic approaches are useful approaches to solve the problem for practical purposes. Several heuristic approaches are found in the literature for node placement problems in WMNs [8–12].

In this work, we use our proposed and implemented WMN-SA system that is based on SA to deal with the node placement problem in WMNs. For simulations, we consider normal distribution of 48 mesh clients in a 32 × 32 sized grid. Then we deploy 16 mesh routers and apply SA, to calculate the optimum solution for the maximum size of GC, and then maximize the number of covered users.

The rest of the paper is organized as follows. The definition of node placement problem is shown in Sect. 2. The proposed and implemented WMN-SA system is presented in Sect. 3. The simulation results are given in Sect. 4. We give some concluding remarks and future work in Sect. 5.

2 Node Placement Problem in WMNs

In this problem, we are given a grid area arranged in cells where to distribute 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 and client coverage. Network connectivity is measured by the size of the GC 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.

An instance of the problem consists as follows.

  • N mesh router nodes, each having its own radio coverage, defining thus a vector of routers.

  • An area W × H where to distribute N mesh routers. Positions of mesh routers are not pre-determined, and are to be computed.

  • M client mesh nodes located in arbitrary points of the considered area, defining a matrix of clients.

It should be noted that network connectivity and user coverage are among most important metrics in WMNs and directly affect the network performance.

In this work, we have considered a bi-objective optimization in which we first maximize the network connectivity of the WMN (through the maximization of the size of the GC) and then, the maximization of the number of covered users.

3 Proposed and Implemented WMN-SA System

In this section, we present WMN-SA system. Our system can generate instances of the problem using different distributions of client and mesh routers.

The GUI interface of WMN-SA is shown in Fig. 1. We set the network configuration parameters as distribution, number of clients, number of mesh routers, grid size, radius of transmission distance and the size of subgrid.

Fig. 1
figure 1figure 1

GUI tool for WMN-SA system

Full size image

3.1 Simulated Annealing

3.1.1 Description of Simulated Annealing

SA algorithm [13] is a generalization of the metropolis heuristic. Indeed, SA consists of a sequence of executions of metropolis with a progressive decrement of the temperature starting from a rather high temperature, where almost any move is accepted, to a low temperature, where the search resembles Hill Climbing. In fact, it can be seen as a hill-climber with an internal mechanism to escape local optima (see pseudo-code in Algorithm 1). In SA, the solution s′ is accepted as the new current solution if δ ≦0 holds, where δ = f(s′) – f(s). To allow escaping from a local optimum, the movements that increase the energy function are accepted with a decreasing probability exp (−δ/T) if δ > 0, where T is a parameter called the “temperature”. The decreasing values of T are controlled by a cooling schedule, which specifies the temperature values at each stage of the algorithm, what represents an important decision for its application (a typical option is to use a proportional method, like Tk = α Tk-11). SA usually gives better results in practice, but uses to be very slow. The most striking difficulty in applying SA is to choose and tune its parameters such as initial and final temperature, decrement of the temperature (cooling schedule), equilibrium detection, etc.

For further details on initial solution, fitness evaluation and movement types, refer to [14].Footnote 1 However, the acceptability criteria of neighboring solutions is now different, as explained next.

3.1.2 Acceptability Criteria

The acceptability criteria for newly generated solution is based on the definition of a threshold value (accepting threshold) as follows. We consider a succession tk such that tk > tk + 1, tk > 0 and tk tends to 0 as k tends to infinity. Then, for any two solutions si and sj, if fitness(sj)-fitness(si) < tk, then accept solution sj.

For the SA, tk values are taken as accepting threshold but the criterion for acceptance is probabilistic:

  • If fitness(sj) - fitness(si) _ 0 then sj is accepted.

  • If fitness(sj)-fitness(si) > 0 then sj is accepted with probability exp[(fitness(sj)-fitness(si))/tk] (at iteration k the algorithm generates a random number R \( \in \) (0,1) and sj is accepted if R < exp[(fitness(sj)-fitness(si))/tk]).

In this case, each neighbor of a solution has a positive probability of replacing the current solution. The tk values are chosen in way that solutions with large increase in the cost of the solutions are less likely to be accepted (but there is still a positive probability of accepting them).

4 Simulation Results

We carried out many simulations to evaluate the performance of WMNs using WMN-SA simulation system. In these simulation scenarios, we consider a grid with 32 × 32 size. The number of mesh routers is considered 16 and the number of mesh clients 48. For evaluation, we considered normal distribution of mesh clients. We set the value of SA temperature to 1 and conduct simulations for different number of iterations for each phase.

In Figs. 2 and 3, we show results of size of GC and number of covered users, respectively. For each phase of calculations, SA runs a number of 64, 128, 256 and 512 iterations. Because of the presence of random processes in our simulation system, we conduct the simulations 10 times, in order to create a general view of results. The maximum size of GC is 16, as we have 16 routers in our scenario. In Fig. 2a, b, the performance of the system for optimizing the size of GC, is almost the same. After 25 iterations the router backbone is completed with all 16 routers. While in the cases of 256 and 512 iterations (Fig. 2c, d), the performance increases, as the max size of GC is reached for less generations (10 and 8, respectively). We show the results for 50 generations as the size of GC is always maximum for more generations.

Fig. 2
figure 2figure 2

Size of GC for different numbers of iterations

Full size image
Fig. 3
figure 3figure 3

Number of covered users for different numbers of iterations

Full size image

In Fig. 3 is shown the covered users for each iterations. First, we conducted simulations with 50 generations. In that case, not all users were covered. Then, we increased the number of generations per simulation to 200. The algorithm runs in similar ways for all cases when number of iterations is different. The maximum number of covered users goes up to 46. The performance becomes a little better when we move from 64 iterations up to 512 (see Fig. 3a–d), in terms of faster optimization. In the cases of 256 and 512 iterations per phase, in Fig. 3c, d, in around 10 phases there are more than 40 users covered. For less iterations per phase the performance is worse.

5 Conclusions

We conducted simulations with our WMN-SA system, in a grid with size 32 × 32, where we deployed 48 mesh clients and 16 mesh routers. Using SA, we optimized the size of GC and then the number of covered users for different number of iterations per phase.

From the simulation results, we conclude that, SA is a good algorithm for optimizing the size of GC, while in terms of number of covered users, it does not cover all the users. The performance of of WMN-SA system increases when we use more iterations per phase. In the case of the size of GC, all the routers were connected for less than 10 phases, when the number of iterations were 512.

In our future work, we would like to make a quantitative evaluation of the calculation time for all cases and compare the performance with other approaches. Moreover, we would like to implement other search optimization algorithms in our simulation system.