Keywords

1 Introduction

Since a decade, there is an emphasis on deploying wireless networks in a mesh topology to form a Wireless Mesh Network (WMN) [1]. This has been shown as a cost-effective approach to extend the coverage of the wireless technology. Despite their cost-effectiveness and their capacity to bridge the digital divide observed between rural and urban regions, WMNs are still lowly deployed in rural regions. In the few deployments, WMNs in rural regions consist usually of one gateway which connects the network to Internet, and a set of mesh routers (MRs). The number and the location of these routers have a direct incidence on the cost and the performance of the network.

As said in [2] the network planning in rural region is coverage-driven rather than capacity-driven. That means we are more concerned by the space to cover than the capacity to provide. In other terms, in the case of WMN planning, the number of routers is determined by their coverage. In rural regions, the main concern when planning a WMN is the cost of the architecture. This cost depends on the number of mesh routers and it should be minimized while providing some coverage percentage of a given area.

In this paper, we consider the network model found in [3], wherein a given area to cover is decomposed into elementary areas which can be required or optional in terms of coverage and where a node can be placed or not. This model is extended to consider the presence of obstacles which can hinder the connectivity. The aim is therefore to determine the location of mesh routers which: minimizes the number of MRs; maximizes the coverage of area of interest; and ensures the connectivity of the network.

To achieve this goal, a network model is defined and the placement problem is formulated. Then, a placement approach based on simulated annealing algorithm is proposed. It is evaluated on different regions instances using Scilab 5.4.0.

The rest of the paper is organized as follows: Sect. 2 briefly presents previous work in WMN planning. Section 3 provides the network model and formulates the placement problem. Section 4 explains the simulated annealing approach. Section 5 presents the experimental setup and discusses the results. Conclusion and future work end this paper.

2 Related Work

A good survey on the planning of WMN is found in [4]. This work classifies the planning problem according to the flexibility of the network topology: unfixed (not-predefined) and fixed (predefined). In unfixed topology, we should set the location of at least some nodes in the network: the gateway(s) or the routers. This problem is usually assimilated to the one of facilities and locations with mesh routers representing facilities and the users to serve representing locations.

Different formulations of the placement approach have been proposed in the literature. They depend on the type of node considered in the planning problem: gateway(s) [5], mesh routers [6], or both [7].

To solve this problem, different approaches have been proposed among which: Graph-theoretic-based approaches [8]; Meta-heuristic based approaches [9], and linear programming based approaches [10].

An approach also based on simulated annealing to solve the mesh nodes placement problem is provided in [9]. It aims to find optimal locations of routers that maximize the network connectivity and client coverage, given a two-dimensional area with a number of fixed client nodes.

The placement problem of mesh routers in rural a region has been introduced in [11] and later extended in [3]. They considered the region as decomposed into a set of elementary areas which may require the coverage or where a node may be placed. A placement approach based on metropolis algorithm has been therefore used. We extend this model by considering the existence of obstacles that can prevent the connectivity of the network.

3 Placement Problem Formulation

In the present placement problem, a given region is composed of areas of interest that should be covered as it is in [3]. When an area is not of interest, the coverage of this region is considered as optional. A given region comprised also prohibited areas where a node cannot be placed (lake, river, road…), and a set of obstacles that could hinder the connectivity.

The area to cover is modelled as a two-dimensional irregular form in a two-dimension coordinate plane. We consider the smallest rectangle that can contain the irregular form. Therefore, we assume that this rectangle is decomposed into small square forms. Each discrete point is called elementary area (EA). Each EA can be of one or more types: Elementary Area of Interest (EAI); Non-line-of-sight Elementary Area (NEA); or Prohibitive Elementary Area (PEA).

When an EA is not an EAI, it is automatically an optional EA (OEA). A set of two-dimensional matrices is defined to characterise each EA: Cover indicating whether an EA requires coverage; Place indicating whether we can place a node in an EA; CoverDepth indicating the number of routers covering an EA; and Pathloss indicating whether an EA contains an obstacle. Therefore, an EA at position (x,y) can be characterised by (1–4).

$$ {\text{Cover}}\left( {{\text{x}},{\text{y}}} \right) = \left\{ \begin{aligned} & 0 \to coverage \,\,not \,\,required \\ & 1 \to coverage\,\, required \\ \end{aligned} \right. $$
(1)
$$ {\text{Place}}\left( {{\text{x}},{\text{y}}} \right) = \left\{ \begin{aligned} & 0 \to cannot\,\, place \,\,a\,\, node \\ & 1 \to can\,\, place \,\,a \,\,node \\ \end{aligned} \right. $$
(2)
$$ {\text{CoverDepth}}\left( {{\text{x}},{\text{y}}} \right) = \left\{ \begin{aligned} & 0 \to no \,\,coverage \\ & n \to covered \,\,by \,\,n \,\,routers \\ \end{aligned} \right. $$
(3)
$$ {\text{Pathloss}}\left( {{\text{x}},{\text{y}}} \right) = \left\{ \begin{aligned} & 0 \to no\,\, obstruction \\ & p \to attenuation\,\, factor\,\, = \,\,p \\ \end{aligned} \right. $$
(4)

We assume, to alleviate the complexity of the problem, that the attenuation factor of any obstacle in the line of sight between two routers is high enough to prevent any wireless link between those routers. We also assume that all routers are equipped with an omnidirectional antenna all having the same coverage radius (r). The radius is expressed as the number of EAs (r = 6 means that the radius stretches over 6 EAs).

Let l be an EA at position (x,y). If a mesh router is located in l, then the set of EAs covered by this mesh router is given by (5).

$$ \forall \left( {{\text{a}},{\text{b}}} \right), \left( {{\text{x}} - {\text{a}}} \right)^{2} + \left( {{\text{y}} - {\text{b}}} \right)^{2} < {\text{r}}^{2} $$
(5)

We assume the number of routers to be placed to be unknown at the beginning.

The mesh router placement problem in rural regions can be described as the determination of a minimum set of positions, which maximizes the coverage of areas of interest, minimizes the coverage of optional areas while maximizing the use of cost effective locations and ensuring the connectivity.

4 Simulated Annealing Approach

4.1 Basic Algorithm

The SA algorithm proceeds as follow: First, an initial solution is generated; several iterations are performed from this solution. A new random solution is generated at each iteration. If the solution improves the value of the objective function, it is directly accepted. Otherwise, this non-improving solution is accepted with a probability depending on the current temperature and the difference E between the value of its objective function and the one of the previous solution. Since the temperature decreases progressively, the probability of accepting non-improving solutions also decreases. Usually, the probability in the SA algorithm follows the Boltzmann distribution \( e^{{ - \frac{\Delta E}{T}}} \) [12].

4.2 Particularization

We use a multi-start SA algorithm in the proposed scheme. It consists of running the SA algorithm many times to keep the best result at the end. The basic SA is adapted according to the flowchart given in Fig. 1.

Fig. 1.
figure 1

Flowchart of the modified SA algorithm

Full size image

Initialization.

The initial number of routers for a given region is calculated by dividing the total required area by the area covered by a router. Let r be the radius of a router, the minimum number of routers is given by (6).

$$ {\text{nr}}_{ \hbox{min} } = \mathop \sum \nolimits {\text{Cover}}\left( {{\text{x}}, {\text{y}}} \right) /({\text{r}}^{2} *3.14) $$
(6)

Since routers should overlap to ensure the connectivity, and because the form of the region is irregular, we use a greater number so that the coverage and the connectivity can be ensured. This number is reduced later while trying to keep the same coverage. However, a too great number at the beginning is not efficient. We choose an initial number of routers between 1.4*nr min and 2*nr min .

Best keep the best solution for each number of routers. nRun is the number of times the SA algorithm will be executed. Routers are placed randomly in the region during the initialization phase of the SA algorithm, but only in areas of interest. We randomly select an EA for each router. We check if Cover(EA) = 1, and Place(EA) = 1, and, if a router is not already set at this location then the current router can be placed there. Otherwise, we continue by selecting another EA. The initialization ends when all routers are placed.

Cooling Schedule.

The initial temperature T = 10 has been determined empirically. We select a geometric update scheme with α = 0.5. When the temperature is less than T min  = 0.001, the cooling process stops.

Move.

We define a set of movements with moving only one router at the same time. We select randomly a distance and a direction; the movement from the current EAa to the new EAb is simulated if and only if Cover(EAb) = 1 and Place(EAb) = 1. Initially great moves are selected to allow a rapid convergence. The size of moves decreases with the temperature; when the temperature is close to T min , the size of moves is one EA.

Fitness Function.

We count the number of EAIs that are covered to evaluate the fitness function. This is done by (7) after the initialisation.

$$ {\text{f}} = \mathop \sum \nolimits {\text{sign}}\left( {{\text{CoverDepth }}. * {\text{Cover}}} \right) $$
(7)

Since we move only one router at the same time, we consider also only the EAs which are concerned by the movement.

Acceptance Criterion.

When \( C_{b} \ge C_{a} \), the coverage change is directly accepted. But when the coverage change is negative, the change is accepted with a certain probability following the Boltzmann distribution and influenced by the temperature \( T \) to avoid local optimum.

Equilibrium State and Stopping Condition.

The equilibrium state is supposed to be reached if after a number (stop) of moves no solution has been accepted. The stopping condition depends on \( Imp \) and on T min . At each temperature \( T_{i} \), \( Imp \) indicates whether the solution has improved. When the equilibrium state at a temperature \( T_{i} \) is reached, before decreasing the temperature we check whether the solution has improved. In case of an improvement, we decrease the temperature and move to the next iteration. But if there is no improvement or the temperature is less than T min , we stop the search process and suppose having reached an optimum.

At the beginning nr min routers are used. The SA algorithm is running nRun times at each stage. If the required coverage is satisfied, we remove one router and restart until the coverage can no longer be satisfied.

Nodes Connectivity.

The network is connected if for two pair of routers there exists a non-empty set of links that allows a communication between those two routers. At this step we check if each router is connected to at least one router while verifying that there exists no sub-network. This task is more complicated with the presence of obstructions in the model. We must not only check that the router radiuses are overlapping, but also the existence of the line of sight between the routers.

Reducing the Number of Routers.

After nRun for a given number of routers nr, we select the run, which provides the best coverage of the area of interest and we remove one router. To remove a router, three strategies can be used: Remove the router with the minimum single-coverage; Remove the router with the minimum coverage of EAI; Remove the router with the maximum over-coverage. The first appears to be the best among these three strategies.

Local Compensation.

When removing one router - if its single coverage is not null - we try to compensate it locally. The idea is to check if by moving its neighbours the compensation can be achieved. So, when removing the router, we keep its coordinates. Then we determine its neighbours and we simulate small moves. We accept a move only if it improves the coverage.

5 Experimental Results

To evaluate our proposed algorithm, we consider a grid of 100 × 100 with the radius of a router r = 6. The unit is the size of an EA. If size (EA) = 20 m, the grid will be 2 km × 2 km = 4 km2 and the radius r = 120 m. This is realistic since 802.11a routers have a theoretical outdoor transmission range of 120 m, 802.11b 150 m and 802.11n routers 250 m. The other global parameters for the experimentation phase are: nRun = 3, Stop = 500, NumberOfObstruction = 50, nrinit = 1.5nrmin, r = 6, Tinit = 10, and Tmin = 0.001.

We generate two regions with different areas of interest, obstructions and prohibited areas as in Fig. 2. Blue regions represent the area of interest that should be covered and black regions represent optional areas in this figure. Prohibited areas are not directly seen, because some areas of interest and optional areas can also be prohibited areas. Obstructions are placed randomly on regions.

Fig. 2.
figure 2

Region instances: (a) instance 1; (b) instances 2.

Full size image

6 Results

In instance 1, all the three runs provide a coverage percentage of the area of interest close to 100 % with nr init  = 65. All routers are connected and the coverage of the optional area is around 20 %. We observe that with nr = 63 or nr = 62, no run provided a connected network. But with nr between 61 and 58, we get at least one connected network from each run. This is due to the presence of obstructions between routers. That means, in presence of obstructions, augmenting the number of routers is not an efficient strategy to ensure the connectivity of the network. We also observe that with nr = 59 (1.34*nr min ), we obtain a coverage percentage of the area of interest greater than 99 %, with all the routers connected. This number could be considered as the optimal number to achieve a coverage percentage of the area of interest close to 100 %. This number of routers starts a horizontal asymptote. Augmenting the number of routers will not improve the coverage, since it is close to 100 %.

In instance 2, the initial number of routers nr init  = 68 provides a coverage percentage of the area of interest close to 100 %; with all routers connected. As in the first instance, the locations of obstructions in the region influence the connectivity of the network. With nr = 63 or 64, no run provided a connected network. A good trade-off between the number of routers and the coverage percentage of the area of interest is found with nr = 61 (1.32*nr min ) with a coverage of 98 %.

Figure 3 compares the best and the worst coverage percentage of the area of interest for instance 1, 2 respectively. The almost monotonically increasing curve of the best coverage percentage (maximal) is obtained by keeping the best previous configuration after removing one router and making the local compensation. Apart from some low peaks with a decrease of 5 % from the best, other numbers of routers provide a variation less than 4 % between the best and the worse percentage coverage of the area of interest in Fig. 3. That means, even though the approach is probabilistic, the results are similar.

Fig. 3.
figure 3

Coverage percentage of area of interest

Full size image

Figures 4 and 5 show router locations (a), links and obstructions (b), respectively in instance 1, and 2. In Figure (a), blue, red, and white colours represent areas covered respectively by one, two, and three routers. In Figure (b), lines represent links between routers that are represented as white squares. Obstructions are represented as green squares.

Fig. 4.
figure 4

Router locations and links

Full size image
Fig. 5.
figure 5

Router locations and links

Full size image

59 routers are used in Fig. 4; that corresponds to 1.34*nr min . 61 routers are used in Fig. 5 (1.32*nr min ). In Figs. 4a and 5a, we can observe some very small dead spots represented by black space between routers. The fact that they are insignificant also witnesses the suitability of the placement approach.

7 Conclusion

From the two dissimilar instances and different runs of the algorithm, we can generalise some results. The first result is the efficiency of the approach to solve this problem of mesh router nodes placement in regions with different forms. In fact, in the two instances the average coverage is close to 100 % with nrinit = 1.5*nrmin. Secondly, we observe that an optimal number is around 1.3* nrmin, with a coverage percentage of the areas of interest of at least 98 %. This approach improves the coverage percentage provided by using the simple metropolis approach provided in [3], with the same number of routers. However, it always considers the case where the area of interest is continuous. A new approach should therefore be provided to deal with the case of disjoint areas of interest.