Genetic algorithms and greedy-randomized adaptive search procedure for router placement problem in wireless networks

Abstract

Wireless networks are present in all the large buildings or sites, and they are expected to provide high speed Internet for the connected users. This can be achieved by connecting wireless routers to the Internet backbone through fast connection cables (e.g. fiber optics), as well finding optimal distribution of the routers along the building, so that the targeted area is covered with Internet access as much as possible, provided that the cost constraints of routers and the cost of their mutual interconnection are satisfied. Therefore, in this paper, we present two approaches for solving the problem of router placement in a two-dimensional area, where the goal is to provide optimal Internet coverage by meeting the cost constraints. Our first approach is based on Genetic Algorithms, and the second one employs the Greedy-Randomized Adaptive Search Procedure. Both approaches utilize a neighborhood exploration mechanism that consists of operators which are dealing with adding, removing, jumping and shifting routers in the target area. Furthermore, an advanced operator for intelligent shifting of routers inside a predefined neighborhood is implemented. The computational experiments, performed over a data set of four large instances, indicate that both proposed approaches can obtain competitive results to the ones that are presently available in the literature. Consequently, the results indicate that both approaches can be easily adapted for application in practice for designing the topography of wireless networks, in terms of router placement and distribution.

Keywords

Router placement wireless networks genetic algorithms greedy randomized adaptive search procedure

1. Introduction

In today’s life, wireless Internet connection is required in buildings, either for entertainment or business, be it at home, at a restaurant, at the office or in any other place. These buildings can be small or large, such as shopping malls, railway stations or airport terminals. In most cases, such buildings must be provided with indoor Internet access in areas (rooms, corridors, toilets, etc.), as well as in some parts of the outer area (balconies, gardens, yards, etc.). While, for some small buildings, a router or few of them can be sufficient to cover the area with Internet access, for large buildings sometimes dozens or hundreds of them might be needed, which is also in the reliance to the coverage of the router, in terms of its signal transmission power and its antenna gain [14]. Further, when placing the routers around a building, the cables that connect them to the Internet backbone (which might be a fiber optic cable for fast Internet connection) need to be spread around the building. Therefore, for large buildings, solving this problem manually is a quite difficult and time consuming task [12], as the solver has to decide on questions such as how many routers have to be utilized, where should they be placed and how should they get connected to the Internet backbone by cable. As a result, to obtain a cost-effective and computationally efficient solution, an algorithmic approach is required.

In this paper, we consider a specific version of it, tagged as Router Placement Problem (RPP), which was defined as part of Google Hash Code competition. This competition is organized in annual basis by Google and it is composed of two rounds: qualification round and final round. In the qualification round, groups of maximum four members compete by solving a problem within limited period (usually five hours). In the final round only, the best qualifiers from the first round are invited to take part in a single day competition by solving a new complex engineering problem. The RPP problem solved in this paper belongs to the final round of 2017 competition that was organized in Paris, France [1]. The precise task in the RPP is that, given a building plan, decide where to place wireless routers within the building and how to connect them to the fiber backbone so that the wireless Internet access coverage is maximized, while the combined cost of routers and backbone connection is minimized.

The main contribution of this paper is twofold: (1) design and implementation of two metaheuristics, namely genetic algorithms and greedy-randomized adaptive search procedure, for solving the problem under discussion, and (2) presentation of an empirical study that encompasses computational experiments with the two developed algorithms, where their results are compared against the best results known in the literature.

2. Literature review

The problem of node distribution over a certain area, and under certain constraints, is widely used for modelling various problems. In the literature, there is a plethora of related models and solutions that are associated to the RPP problem considered in this paper. One such an example is the problem of Router Placement in a Wireless Mesh Network (RPWMN) [1]. The objective of this optimization problem is finding the adequate position of the routers in a network to maximize the connectivity and coverage of the clients. In [26], the RPWMN problem is tackled by a Simulated Annealing approach, where the problem is optimized based on two objectives, the first being the size of the giant component in the network, whereas the second is the user coverage.

Further, the problem of Wireless Mesh Network (WMN) has been investigated by the authors in [27]. In their perspective, the topology of the network is that each node is connected to one or more other nodes, offering the possibility of data transmission over multiple paths [3]. The main property of this topology is the non-necessity of maintaining a central node. Xhafa et al. [27] present a genetic algorithm approach to solve the WMN model, where the aim is to maximize the coverage of clients, while increasing the level of connectivity between routers. Such a solution would be able to support multimedia intelligent telecommunication services to clients.

Another related model is the problem of the Dynamic Router Node Placement in Wireless Mesh Network (DRNPWMN) [16], where, both, the clients and the routers are movable, whilst the clients can also disconnect from the network at any time. In addition, in this model, clients are associated with specific weight coefficients that are proportionate to the specific service priorities of individual clients. This optimization problem is solved by a bat-inspired algorithm, where a local minimum search approach is used to find and improve the solution by moving the routers within a circle until an appropriate position is found [16].

Furthermore, in [24], the authors present a model that is tagged as Wireless Sensor Network (WSN) problem. Differently from WMN, the WSN problem is not only focussed on node placement, but also in energy saving of the sensor nodes, due to the limited life time of the corresponding batteries. Tsai et al. [24] present a survey of the various methods that are available in the literature in regards to investigating and solving the WSN problem, where the aim is to find the appropriate location of the sensors so that the targeted area is covered as much as possible, while minimizing the overall energy consumption. One of the first proposed methods is a tabu search algorithm, which tries to avoid the local optimum by saving search information about the earlier explored solutions. In addition, WSN problem is also solved using genetic algorithm and simulated annealing [24].

In Table 1, we present a summary of some of the basic features that differentiate the specific problems discussed in this section. From the details given in the table, one can notice that different models concentrate on covering specific features, such as: static node positioning (RPWMN, WSN and RPP), coverage of clients with priority (DRNPWMN), end user performance (RPWMN and DRNPWMN), sensitivity of node power source (WSN) and cost of connection to the backbone (RPP). Consequently, the RPP problem, which is tackled in this project, is more like RPWMN and WSN, by differing only for one feature, whereas it differs in more features when compared to DRNPWMN problem. Nevertheless, the RPP problem is the only model which considers the cost of connection to the Internet backbone.

Table 1
Comparison to the related problems

Problem abbreviation Static node positioning Coverage of clients with priority End user performance Sensitivity of node power source Cost of connection to the backbone

RPWMN Yes No Yes No No

DRNPWMN No Yes Yes No No

WSN Yes No No Yes No

RPP Yes No No No Yes

Problem abbreviation	Static node positioning	Coverage of clients with priority	End user performance	Sensitivity of node power source	Cost of connection to the backbone
RPWMN	Yes	No	Yes	No	No
DRNPWMN	No	Yes	Yes	No	No
WSN	Yes	No	No	Yes	No
RPP	Yes	No	No	No	Yes

To the best of authors’ knowledge, besides the results that are published in the web page of Google Hash Code [13], there is no any paper in the literature that presents or makes a formal description of any solution to the RPP problem.

3. System and mathematical modelling

For a didactic explanation of the problem at hand, let us suppose a simple scenario of a four-room building that needs to be provided with Internet access. The area of the building is divided into cells, which are represented in a coordinate system with 14 rows and 26 columns (see Fig. 1). Considering a router with omni-directional antenna, the radius of router range is 3 cells (i.e. it can cover three neighbouring cells from the cell where it is placed), whereas the cost of one wireless router is 5 currency units. The cost of connecting one cell to the backbone is 1 currency unit, while the maximum budget is 64 currency units. Let us suppose that the initial cell that is already connected to the backbone is denoted with coordinates 5 and 2. Given these input details, the actual task is to find the places (i.e. cells) where the routers should be placed and how should they get connected to the initial cell that is already connected to the backbone, so that the area is covered with the Internet as much as possible, while the cost is minimized.

Fig. 1.

A sample building plan to be provided with wireless Internet access.

The formal description of the router placement problem represents an Integer Linear Programming (ILP) model, which is formulated based on the original specification in the Google Hash Code competition [13]. $\begin{matrix} (1) & max (1000 * T + (B - (N * P_{b} + M * P_{r}))) \end{matrix}$ Subject to: $\begin{array}{l} (2) & \sum_{j = 1}^{H} \sum_{k = 1}^{W} a_{i j k} b_{j k} = 1, \forall i = 1, \dots, M \\ (3) & \sum_{j = 1}^{H} \sum_{k = 1}^{W} a_{i j k} c_{j k} = 0, \forall i = 1, \dots, M \\ (4) & N * P_{b} + M * P_{r} ⩽ B \\ (5) & \begin{matrix} | x_{r} - x_{c} | ⩽ R \land | y_{r} - y_{c} | ⩽ R \\ \land \neg [min (x_{r}, x_{c}) ⩽ x_{q} ⩽ max (x_{r}, x_{c}) \land min (y_{r}, y_{c}) ⩽ y_{q} ⩽ max (y_{r}, y_{c})], \\ \forall r = 1, \dots, M, \forall c = 1, \dots, T_{c}, \forall q = 1, \dots, Q \end{matrix} \end{array}$

This model includes parameters that specify the specific input problem details, the decision variables that need to be set when obtaining a solution, the objective function used for evaluation of the solution, and the constraints that must be met to gain a feasible solution. In the following, the specific description of the individual elements of the model is given.

Parameters:

Number of rows of the grid

Number of columns of the grid

Radius of the range of a router

Price of connecting one cell to the backbone

Price of one wireless router

Maximum budget

Number of target cells

Number of wall cells in the grid

Coordinates of backbone cell

Coordinates of target cells in the grid

Coordinates of wall cells in the grid

Decision variables:

Number of cells where routers are placed

Number of cells connected to the backbone

Number of target cells covered

Coordinates of cells in the grid where routers are placed

Coordinates of cells in the grid, which are covered at least by the signal of one router

equals 1, if router i is placed in cell with coordinates $(j, k)$ , otherwise it is 0, $\forall i = 1, \dots, M$ , $\forall j = 1, \dots, H$ , $\forall k = 1, \dots, W$ ,

equals 1, if cell with coordinates $(j, k)$ is connected to backbone, otherwise it is 0, $\forall j = 1, \dots, H$ , $\forall k = 1, \dots, W$ ,

equals 1, if cell with coordinates $(j, k)$ is a wall cell, otherwise it is 0, $\forall j = 1, \dots, H$ , $\forall k = 1, \dots, W$

In Eq. (1), the maximizing objective function, is taken from the original Google Hash Code definition [13], where a solution is evaluated based on two components. The first component earns 1000 points for each cell covered with Internet access, whereas the second component gets 1 point for each unused unit of the total allocated budget B.

In terms of constraints, (2) ensures that all routers are placed in cells that are connected to the backbone point, whereas (3) makes sure that no routers are placed in wall cells. Further, (4) guarantees that the total allocated budget is not surpassed. Finally, (5) enforces the constraint that no wall cell exists between a router cell and a cell that is covered by that router signal.

4. Solution approaches

This section presents in depth details of the approach adopted to solve the router placement problem, while at the end, we present the results of the execution of the algorithms against the running scenario of the four-room building.

4.1. Background

The router placement problem is a complex combinatorial problem that belongs to the class of node placement problems, which have shown to be computationally expensive to solve them to optimality [2]. Hence, heuristic optimisation strategies [9,19,23] and advanced machine learning techniques [6,7] are mainly used in the literature to solve such critical problems for practical purposes. In this paper, the solution for the router placement problem is based on two different approaches, where one belongs to the group of population-based approaches (i.e. Genetic Algorithms – GA), while the other one fits in the group of single state methods (i.e. Greedy Randomized Adaptive Search Procedure – GRASP). The genetic algorithms have been successful applied to solve various optimisation problems in diverse application domains [22], including optimization of the problem for node placement [25,27] which is a problem closely related to the RPP problem. On the other hand, a simple, yet quite effective, single state method is the Greedy-Randomized Adaptive Search Procedure (GRASP), which has had a successful application in different domains, such as graph and map drawing, routing, telecommunications, etc. [20]. In the following, we describe the particularities about solution encoding and the respective operators that are used for generation of neighbour solutions of a given current solution. Further, we present specific details about both proposed techniques.

4.2. Data structures for solution encoding

A given solution for the router placement problem is encoded (represented) with a data structure of two lists, where one represents the cells where the routers will be placed, and the other list represents the cells that need to be connected to the Internet backbone. In both lists, any member contains two values, which denote the coordinates of the cells (i.e. locations), where the router is placed or the cells that need to be connected to the backbone, respectively. In the following, we show a sample representation of the solution for the running scenario of the four-room building. $\begin{matrix} S = [R, C], where R = [(3, 6), (3, 9)] and C = [(3, 6), (3, 8), (3, 9)] \end{matrix}$

In this case, the solution consists of 2 routers that are dispatched in two different cells (R list) within the building area and three cells that need to be connected in the Internet backbone (C list). This kind of encoding makes it trivial to evaluate the fitness of the solution, when it has slightly changed from its previous version (which is the most frequent case in the search process), as the delta function can be applied without difficulty, to find the difference in quality between the changed parts in the solution. Further, although this representation is a simple one, it still allows flexibility in applying various operators, either by changing the values of the coordinates or by removing or adding new members (i.e. routers) in the list.

In form of complementary data structures, with the aim of speeding up the search process, for each individual solution, three hash lists are maintained, such as:

List of covered cells that stores information about which cells are already covered with Internet, where the key represents the cell location, whereas the value is equal to the number of routers covering that cell. When a given element has its value set to zero (which means that no routers cover that cell), then, that element is removed from the list. This hash list is very useful in the process of solution evaluation, where, instead of traversing each cell in the building to check whether it is covered with Internet access by any of the routers, simply, the length of this hash list denotes the number of covered cells.

List of non-covered cells that is similar to the list of covered cells, but it is used to find better neighbour solutions when various operators are applied, as described in the next section.

List of movable routers that keeps track of certain routers that have been impacted by other routers, in terms of cell coverage, when different operators are applied. A given router X is added into this list; in case another router Y has changed the coverage state of the cells covered by router X. The change of coverage state can be when router Y, from now on, also covers some cells covered by router X or when some cells covered by both routers are not covered anymore by router Y. On the other hand, a given router X is removed from this list when, although its position has changed (by means of some operator), it has not contributed in increasing the solution fitness.

4.3. Nature of neighborhood operators

The mechanism for generation of neighbour solutions, for both approaches, consists of operators that enable the addition or removal of routers, as well as random movement of existing routers around the cells of the building area. The exact operators utilized within this implementation are described in the following.

Add or remove – These two operators, randomly, add a router or remove an existing router within the solution. When adding a router, cells that are not presently covered with Internet are considered first, and, if no such cells are found, then, the router is placed in a random cell, but a feasible one (i.e. not a wall cell or a cell where there is already a router). In case of removal, simply, a given router, placed at a cell, is selected at random and then removed from the solution.

Jump – This operator randomly selects an existing router from the current solution and changes its location to a new random cell. This new cell can be selected based on two forms, which is either by considering only the group of non-covered cells (i.e. cells without Internet coverage) or by considering all feasible cells (i.e. only the wall cells are excluded).

Shift – This operator shifts a randomly selected router from its current cell to one of the cells in its neighbourhood. The size of the neighbourhood could be small, where only the immediate neighbours, in all directions (i.e. vertically, horizontally and diagonally), of the current cell are considered, or it could be larger, by containing all the cells that are currently covered by the neighbourhood radius, which is a parameter supplied to the algorithm.

Smart shift – This operator randomly shifts, within its neighbourhood, a given random router from the list of moveable routers. As described in Algorithm 1, the operator at hand, exhaustively, tries out shifting the selected router in one of its neighbouring cells (as defined by parameter nsr). When a new cell is found for the router, which produces a better-quality solution, this operator quits and returns that solution. Otherwise, the operator returns a modified solution, where the router is shifted in one of the cells in its neighbourhood, which yields to the same quality solution as the input one. In case the selected router, from the list of moveable routers (i.e. lmr list), when tried out in each of its neighbouring cells, does not produce a better or an equal quality solution, then the input solution remains unchanged.

Algorithm 1

Smart shift operator procedure

4.4. Connection and disconnection of routers to the backbone cell

Since the routers are spread all-over the area of the building they need to get connected by cable to the cell that is supplied with backbone. This problem, from the literature point of view, is equivalent to the problem of finding Minimum Spanning Tree (MST) in a given graph, where the routers are represented by nodes while the connections between them are represented by edges.

The most usual methods (used in the literature) for finding the MST in a graph are Kruskal’s and Dijkstra-Prim’s algorithms [15]. Nevertheless, these algorithms are optimal only for fixed graphs, where no new nodes can be added. As presented in Fig. 2, for the router placement problem, there are occasions that it might be more convenient to add extra nodes in the graph so that cost of connection between all nodes decreases. The idea of finding the MST by introducing new nodes in the graph was proposed by Steiner [5], which is a problem known to belong to the category of NP hard problems. In this implementation, the Steiner algorithm is applied in that way that new nodes are generated within the internal area, bounded by the existing nodes (cells where routers are placed), and then the Kruskal algorithm is applied to evaluate whether the generation of each of these new nodes yields to a better connection of the routers. This process is repeated for several times and the best case of new node insertion is adapted as solution for router connection.

Fig. 2.

Illustration of the two modalities for router connection.

Furthermore, when a new router is added to a solution, that router needs to get connected to the existing backbone connection tree (i.e. cells already connected to the backbone cell) of that solution. Naively, this process would require checking the distance of the new router cell against each of n cells already connected to the backbone, which would require $O (n)$ comparisons. In our case, we apply a more advanced approach, which is the $kd$ -tree algorithm [18] that explores only the neighbour cells of a given cell, while having a complexity of logarithmic order. In our case, the dimension d is set to 2, since the area where routers are dispatched is two dimensional. Algorithm 2 uses the $kd$ -tree algorithm to find the path of the connection of a new router to the existing backbone connection tree. This procedure is applied whenever a new router is added into an existing solution.

Algorithm 2

Router connection procedure

When a router is removed (e.g. removal of $r 1$ in Fig. 3), the list of cells connected to the backbone (lcb) needs to be updated so that the remaining routers are connected the backbone with as few as possible cells. The update process is done in two steps, where, the first step consists of removing unusable cells from lcb, whereas the second step is about adding new cells to lcb that are required for better (direct) connection of routers, which have become unconnected during the removal step (e.g. router $r 4$ after removing router $r 1$ in Fig. 3). The update procedure is done by applying Algorithm 3 recursively, where, at the initiation, the cell where the removed router was placed (e.g. the cell of router $r 1$ in Fig. 3) is removed from lcb. Afterwards, the recursive removal process continues until a cell that contains a router is found (e.g. cell with router r4 in Fig. 3) or until an intersecting cell, which intersects paths to other routers (e.g. cell with coordinates 2 and 5 in Fig. 3), is found. This process is completed in lines from 3 to 16 in Algorithm 3, where, in case no more cells need to be removed, the cell that needs to be reconnected to the backbone (i.e. to be inserted into lcb list) is returned (marked). Lines from 17 until 26 in Algorithm 3 update the list of cells that need to be checked for removal (lcr) by considering each neighbour cell ( $nc$ ) of the currently removed cell c. Further, the ulcb list is updated, in case the current solution s has a router in any of the neighbour cells ( $nc$ ) or the backbone cell b lies within that area (i.e. lines 22 and 23). Contrarily, the temporary list of selected cells for removal (ctr) is updated, in cases where a cell from nc is not yet checked for removal, does not contain a router and it is not a backbone cell. Finally, each cell that is selected for removal (ctr) is removed from lcb and, subsequently Algorithm 3 is applied in a recursive manner to repeat the process accordingly. When this process is finished, the list of cells connected to the backbone will be up-to-date such that all routers in solution s are connected to the Internet backbone.

Fig. 3.

Illustration of the procedure for cell reconnection after a router is removed.

Algorithm 3

The procedure for updating the list of cells that need to be connected to the backbone after removal of a router

4.5. Genetic algorithms

The GA approach explores the search space based on three main steps: (1) selection of individuals from the population to act as parents that will breed the next generation, (2) varying the parents to produce new individuals (aka. children) and (3) updating the population so that the search process carries on exploring promising areas of search space [17]. The GA approach implemented in this paper is a two-phase procedure, wherein the first phase, an elitism based genetic algorithm [4] is enforced, whereas in the second phase a hill climbing algorithm is applied to further improve the solution. In the following, we show details about GA specific procedures such as initialization, selection, mutation, recombination, population update, and the actual pseudocode.

4.5.1. Initialization

The process of the initialization of the population (see Algorithm 4) starts by calculating the enr factor, which represents an estimated figure on how many routers at most could be used to cover the given building area, which depends on the available budget, on one side, and on the router and backbone connection cost, on the other side. At the start of a given iteration for producing a solution, two lists are initialized, namely lus (for keeping track of cells already covered by a given router) and lrl (that records cells where routers could be placed). The first while loop fills the lrl list with random candidate cells to be used as router locations, where only cells that are not covered by a given router (placed in any of the cells in lrl) are considered, which is a process ensured by utilizing lus list. This part of the procedure ensures that routers are dispatched as much as possible in the building area, so that there is a good Internet access coverage (i.e. solution) from the start of the search process. After no more router cells can be added into the lrl list, its members are sorted based on the distance from the backbone in ascending order, so that the members closer to the backbone connected cell are considered first for insertion. The second while loop, at each iteration, selects a location (i.e. router cell) from the lrl list and adds it to the current solution (i.e. population member) I, provided that the cost of the addition (i.e. router price and backbone connection cost) does not cause to surpass the total budget in disposition. Furthermore, to ensure better dispatching of routers all around the building, so that the initial solution has a be better quality, the members of the lrl list are not selected consecutively, but in a stepwise order wherein each second member of the lrl list is picked up (as expressed by variable j). When this selection process reaches the end of the list, it restarts from the beginning by selecting the remaining members (i.e. router locations).

Algorithm 4

Initial solution procedure

4.5.2. Selection

The selection phase (as depicted in Algorithm 5) has the function of selecting a member of the population to take part in producing the next generation. This procedure is based on the tournament selection method, which returns the best member found after evaluating $ts$ number of random (but distinct) individuals from the population. The $ts$ parameter is an input figure that determines how many members of the population will be evaluated. This selection schema is known for its simplicity in implementation and computation, while permitting adjustment of selection pressure (via $ts$ parameter) and supporting scaling features for genetic algorithms [11].

Algorithm 5

Selection procedure

4.5.3. Mutation and recombination

The mutation mechanism is implemented by using the group of four neighbourhood operators described above, where, at each generation of the algorithm, one of them is selected at random to mutate a given child. The probability of operator selection is proportionate based, which is set based on some preliminary experimentation, and reads as in the following: smart shift (45%), jump (35%), add (10%) and remove (10%). In case the smart shit operator is selected and none of the routers are moveable, then the jump operator is applied instead.

On the other hand, the recombination mechanism is implemented by using the so-called rectangle crossover, where two parents (individuals), as selected by the tournament selection procedure (described above), are recombined. The combination is made by interchanging parts, surrounded by a rectangle, between the two parents (see Fig. 4). The practical effect of this crossover operator is that the routers located within the area of the rectangle of the first parent are transferred within the same area of the second parent and vice versa. The routers located outside of the rectangle box remain unchanged for both parents. Both dimensions of the rectangle are chosen at random, between 2.5% and 20% of the respective dimension (height or width) of the building area. Further, the center of the rectangle is selected at random amongst the target cells (i.e. cells requiring Internet access), which is the same for both parents. This way, the variability of the dimensions of the rectangle enables flexibility in generating children, where at times they might be very similar to their parents (when the rectangle dimensions are small), and vice versa.

Fig. 4.

A sample application of rectangle crossover for the scenario of the four-room building.

In addition, whenever a given mutation or crossover operator is applied, the procedure for the reconnection of the routers (i.e. Algorithm 3) is enforced, so that it is ensured that a feasible solution is devised, in relation to the cost of connection of the routers to the backbone.

4.5.4. Population update strategy

The population is updated based on $l + m$ schema, where l represents the size of the population (i.e. in our case the $ps$ parameter) and m represents the number of new generated individuals (i.e. children). The pollution of the next generation is composed of the best l members that are selected from the group of $l + m$ individuals. To ensure diversity within the members of the population, a special procedure compares every child against the current population, and, in case the child is similar to any of the existing members, that child replaces that member of the population. For this purpose, the similarity measure between two members is computed based on two factors: (1) the difference in quality between the members is less than 10, and (2) the similarity in terms having the same number of routers in same places is greater than 95%. In case the first factor is not met, then the second factor is not evaluated at all.

Algorithm 6

Genetic algorithm procedure

4.5.5. GA pseudocode

The particularities of the specific method applied here are presented in Algorithm 6, where two main phases can be outlined, namely GA phase and Hill Climbing (HC) phase. The GA phase runs about 80% of the total allocated time, whereas the HC phase uses the remaining 20% of the time. After generation of the initial population (by using Algorithm 4) of size $ps$ , the algorithm enters its GA phase, where, at each generation, the following procedures are applied:

Selection of two distinct members of the existing population by using Algorithm 5,

Application of the rectangle crossover to create two new children,

Probable mutation of the generated children in one of the defined operators,

Improving the generated children by applying a hill climbing algorithm inside the GA phase, and

Updating the population by utilizing the above-mentioned strategy.

When the GA phase is completed, the algorithm proceeds with a pure HC phase, where, the best member returned by the GA phase undergoes several mutations (i.e. 20% of the total time) by applying one of the mutation operators described above. After this phase, the best mutated individual is returned as the output of the algorithm.

4.6. Greedy-randomized adaptive search procedure

In the literature, in addition to the population-based methods, where genetic algorithms are part of, there is a plethora of single state methods that are used for solving various complex (i.e. NP hard) problems [17]. As stated earlier, in this paper, we use the GRASP approach, which solves a given optimisation problem based on two main steps: (1) construction of a feasible solution by making sure that both greediness and randomness aspects are considered within the search process and (2) application of local search in the vicinity of the constructed solution, with the intention of exploitation of the search spaces to a maximum extent possible [8]. In the following, we present in-depth details about component definition, as well as the description of the construction and local search phase.

4.6.1. Definition of components

In a GRASP implementation, definition of components is a basic and yet a fundamental process, since it might have an immense impact in the procedure of the construction phase [21]. For the envisioned router placement problem, where routers are to be placed in different cells, with the aim of covering as much as possible the targeted area of the building, it is viable to define a component as “a router placed in a given target cell”. This would enable to evaluate the quality of a component based on the number of target cells its respective router covers, when it gets placed into a certain cell. Subsequently, this method of component definition, would allow to have a total number of components that are equal to the total number of targeted cells. In Fig. 5, we present a sample component, where a router (with a radius of three cells) is placed in the cell with coordinates $(4, 4)$ , which are zero based. The number of covered cells (i.e. the quality of the component) by this router is 35.

Fig. 5.

Illustration of a sample component.

The procedure for setting up the components is part of the pre-processing phase, where, before the start of the GRASP algorithm, all possible components are generated and evaluated, while they are stored into a hash table for fast retrieval.

4.6.2. Construction phase

During the construction phase of the GRASP method (Algorithm 7), a feasible solution for the router placement problem will be constructed. Besides the input problem details, this procedure is guided by three different parameters, as explained in the following:

Components (C) – as defined in the previous section,

Percentage of components (p) – the amount of highest value components that will make up the restricted candidate list, and

Maximum iterations ( $mi$ ) – determines the longest possible duration of the construction phase.

The construction phase starts by initializing a solution s to an empty state, while all components C are made available for insertion. Then, this phase enters an iterative cycle, which runs for a certain number of iterations (as defined by mi parameter). Within a single iteration, a feasible solution will be created by inserting components one after the other. The selection of a component c for insertion is done at random from a restricted candidate list (rcl), which represents the highest value components based on the limit set by parameter p (Lines 12 and 13). In order to maintain solution feasibility, priory to inserting a component, it is checked whether the cost of that component, in terms of router price and connection of the router to the Internet backbone, would cause the overall budget b to be surpassed (Line 14). In case a given component gets inserted into s (Line 15), then the list of available components $AC$ is updated by removing all components whose target cells are already covered by the inserted component (Lines 16 and 17), whereas, on the opposite case, if a given component cannot be inserted into s due to the limited remaining budget, then that component is removed from the list of available components $AC$ (Line 21). The process of insertion of components (i.e. construction of currents solutions s) stops when one of the following conditions is met:

There are no more components left that can be feasibly inserted into solution s (i.e. list of available components $AC$ is empty). In this case, if the solution s is feasible then it is returned as the constructed solution, otherwise the solution s is reset to an empty state, while all the components are made available for insertion and the construction process starts over (Lines 5 to 10).

The insertion of the latest component has brought to a situation that all target cells are covered with Internet (Lines 18 and 19).

Algorithm 7

Construction phase procedure

When a certain component fails to be inserted into solution s due to the limited budget, then, it is checked whether there is enough budget left to insert a new router and connect it (from the cell where it is placed) to the closest cell currently being connected to the Internet backbone. If this is not the case, then the current solution is returned as the output solution (Lines 22 to 23).

In addition, with the aim of having an explorative topography when searching the search space, the “Pop in construction” mechanism is utilized. The idea behind this mechanism is to apply a local search mechanism inside the construction phase, after several components would have already been inserted. In various cases in the literature [10], the “Pop in construction” mechanism has been applied twice during the construction phase, where the first and second application is done after inserting 40% and 80% of the maximum number of components into the solution, respectively. The same strategy is also implemented within the GRASP approach described in this paper (Line 24). The exact “Pop in construction” mechanism that is implemented (Algorithm 8), tries to improve a given solution s by removing (popping) and adding (pushing) components into it, which is a process that runs for a couple of iterations (i.e. $nc / 2$ times). In the course of a single iteration, at first, one of the components of the current solution $s_{c}$ is removed, and then, with an equal probability, either one of the neighboring components (i.e. components that are within the radius of the removed components) is added to $s_{c}$ , or one of the components, whose cells are not covered with Internet, is selected at random for insertion into the current solution $s_{c}$ . This mechanism has a greedy nature, meaning that a given current solution $s_{c}$ is adapted for the next iteration only if it is better than the previous solution s.

4.6.3. Improvement phase

The improvement phase consists of a hill climbing strategy (Algorithm 9), which runs for a certain amount of time t, by applying the neighborhood generation operators that were described in Section 4.2. In the course a single iteration, the existing solution $s_{c}$ is modified by selecting of the possible operators (i.e. add, remove, jump, shift or smart shift). The process of selection of operators is made by relying on the respective probabilities, which are set based on empirical experimentation with the algorithm. The shift operators (smart and simple shift) and jump operator, which have shown to perform better, have higher probabilities of selection, precisely 45% and 35%, respectively, whereas remove and add operators have not shown to make substantial improvements, hence are awarded with smaller probabilities of selection, that is 15% and 5%, respectively (Lines 6 to 16). Further, the modified solution $s_{c}$ is evaluated, and, based on its quality, it is either accepted as a new current solution, when it is not worse than the existing current solution, or it is disregarded, on the opposite case (Lines 17 to 19). The improvement phase quits either when it reaches a certain number of iterations without improvement (as denoted by mui parameter) or when the total allocated time t expires.

Algorithm 8

Mechanism “pop in construction”

Algorithm 9

Improvement phase procedure

4.6.4. GRASP pseudocode

The approach (see Algorithm 10) applied in this implementation undergoes two main steps: (1) a GRASP approach consisting of the construction and local search phases (Lines 3 to 17), and (2) Hill Climbing phase that tries to further improve the solution (Lines 18 to 34). The GRASP and Hill Climbing steps run about 80% and 20% of the total allocated time, respectively.

Algorithm 10

GRASP procedure

As discussed in Section 4.3, the process of the connection of routers is an NP hard problem. Therefore, with the aim of reducing the computation time, during the first step, the solution is constructed only by considering the distribution of the routers in the building by trying to cover as many target cells as possible, while the process of the inter-connection of the routers is omitted. In order to have an approximate numeral on how much would it cost to connect all the routers with Internet backbone, before employing the GRASP algorithm, the solution s is constructed (Line 5) and improved (Line 6) by also connecting the routers (Line 7), so that the connection cost could be calculated (Line 8) and used as an estimated router budget that would be spared (from the overall budget B) when constructing the solution in the upcoming iterations, where the procedure for connection of routers is omitted. In the latter stages of the algorithm, the estimated router budget ( $rb$ ) will be utilized to reconstruct a final feasible solution for the router placement problem, which includes also the connection of routers to the backbone. Further, the router budget $rb$ is also used to determine what is the maximum number of components $mc$ that could possibly be added into a given solution s when considering the overall budget B and the cost of a single router $rc$ (Line 9). The $mc$ value is used in the construction phase of the GRASP algorithm, when we need to know the degree of completeness of a given solution s with components. Next, during the cyclic phase of the GRASP algorithm (Lines 11 to 17), the construction and solution improvement is done without employing the router connection procedure (i.e. Algorithm 3), and, whenever a new better solution is found, it is saved as the best-found solution.

After the end of the GRASP step (Line 17), the solution needs to be regulated by incorporating the part of the connection of the routers to the Internet backbone. To do this, initially the list of cells that need to be connected to the backbone is created (by using Algorithm 3), and then, the overall cost of router placement is calculated by considering both, the number of routers used and the cost of their connection to the Internet backbone (Lines 19 to 21). In case the overall cost happens to be larger than the total budget B, then, the algorithm enters an iterative phase (Lines 22 to 28), where the components (i.e. routers) with the least coverage are removed one after the other, until the overall cost becomes equal or less than the total budget. Within this phase, after a component gets removed, the remaining routers are reconnected (when required) by employing Algorithm 3.

Next, in the Hill Climbing step, the algorithm tries to further improve the solution by engaging only the improvement phase of the GRASP approach (i.e. Algorithm 9) for 20% of the allocated time of execution. At this final stage, the algorithm operates by considering also the router connection part.

4.7. Description of the solution for the running scenario

In order to didactically describe the output of the proposed approaches, we have executed both algorithms against the simple scenario of the four-room building that was described in the introductory section. As it can be observed in Fig. 6, both algorithms yield the same solution, which can be expressed in four different aspects: (1) number of routers used (7 routers), (2) area covered with Internet access (200 cells), (3) area without Internet coverage (14 cells) and (3) number of cells connected to the Internet backbone (29 cells). Therefore, by using Eq. (1) from Section 3 and details (i.e. cost of connecting one cell to the backbone and the cost of one router) of the running scenario in Section 1, the total cost (for both solutions) is $(1000 * 200) + (64 - (29 * 1 + 7 * 5)) = 200000 + 0 = 200000$ . A difference though can be noticed between the solutions produced by the GA and GRASP approaches, is the structure of the cells connected to the backbone, which slightly differs in all rooms, except for the room located on the right of the building. Further, the two routers that are used on the left room are placed one more cell to the left by GRASP approach than by GA approach.

Fig. 6.

Coverage with Internet access of the building represented in the simple scenario.

5. Computational experiments

This section presents the details of the individual test instances, as well as experiments for fine-tuning the values of the parameters of the both proposed approaches. Further, we present the computation results that compare our proposed approaches against the best results that are obtained during the competition of Google Hash Code [13]. Both proposed approaches are developed by using Python programming language under the developing environment of PyCharm 2017. All experiments are done by using a machine with an Intel Xeon with two CPUs having a clock speed of 2 GHz and a RAM memory of 16 GB, while running under an x64 Windows Server 2012 operating system. The source code and detailed results of both approaches are published in GitHub.1

¹
https://github.com/admirkadriu/router_placment_ga

https://github.com/endritilazi/router_placement_grasp

5.1. Test set

The test set for Router Placement Problem, as defined by the authors of Google Hash Code competition [13], consists of four test instances, whose details are summarized in Table 2. The largest instance is “lets go higher” with a total of 850,200 cells, where 33.89% and 4.57% are target and wall cells, respectively. In the aspect of constraints, the “opera” instance has the largest area with walls, while the “rue de londres” instance is the most constraint in terms of budget limit, where its ratio over the number of target cells is only 0.34. Further, seeing that the router price is the same in all instances, one can notice that the utility of routers (when considering the router radius range) is the least in the “lets go higher” instance. The price of connecting a single cell to the backbone is the same for all instances, except for the “lets go higher” instance, where the price is 5 times higher in comparison to the other instances.

The best-known results, for the four described instances, are achieved by AIM Tech team, which did win the first place in the Google Hash Code [13] competition held in Paris in 2017. The sum of the score for the four instances is 548,065,447, whereas the results for the individual instances are as in the following: $rue de londres = 59, 530, 002$ , $opera = 176, 320, 008$ , $charleston road = 21, 963, 069$ and $lets go higher = 290, 252, 302$ .

Table 2
Test set details

Instance feature Instance name

Rue de londres Opera Charleston road Lets go higher

Dimensions ( $No. of cells = row \times columns$ ) $225, 836 = 559 \times 404$ $360, 180 = 667 \times 540$ $43, 200 = 240 \times 180$ $850, 200 = 872 \times 975$

Percentage of target cells 28.53 54.67 50.79 33.89

Percentage of wall cells 6.08 10.49 6.34 4.57

Budget limit 21,634 94,860 29,907 265,4677

Budget / No. of target cells 0.34 0.48 1.36 9.21

Price of one wireless router 100 100 100 100

Radius of a router range 10 7 10 5

Price of connecting a single cell to the backbone 1 1 1 5

Instance feature	Instance name
Dimensions ( $No. of cells = row \times columns$ )	$225, 836 = 559 \times 404$	$360, 180 = 667 \times 540$	$43, 200 = 240 \times 180$	$850, 200 = 872 \times 975$
Percentage of target cells	28.53	54.67	50.79	33.89
Percentage of wall cells	6.08	10.49	6.34	4.57
Budget limit	21,634	94,860	29,907	265,4677
Budget / No. of target cells	0.34	0.48	1.36	9.21
Price of one wireless router	100	100	100	100
Radius of a router range	10	7	10	5
Price of connecting a single cell to the backbone	1	1	1	5

5.2. Parameter tuning

In this section, we present the computational experiments for fine-tuning the values of the parameters for both the proposed approaches. Based on a preliminary experimentation, for each parameter, three best- performing values are selected. Then, the systematic experiments are conducted by executing each approach five times for each selected value of each single parameter and for each instance of the test set. The output results are averaged over the five runs of a given approach for a single parameter value and a given instance. The results of our approaches, for specific instances, are compared against the best-known results, by outlining the mutual percentage gap. In terms of the computation, both approaches are executed in the same amount of time for individual instances, as expressed, in the unit of minutes, in the following: $rue de londres = 40$ , $opera = 140$ , $charleston road = 30$ and $lets go higher = 140$ .

5.3. GA approach

The GA approach has been tested by experimenting with six specific parameters, namely, population size/ tournament size combination, crossover probability, mutation probability, hill climbing iterations, application or not of smart shift operator and radius of smart shift operator (aka. neighbourhood shift radius). In the following, we present and discuss the results for individual parameters.

Figure 7 presents the computational experiments for the three different combinations of values for pop size ( $ps$ ) and tournament size ( $ts$ ) parameters. From the figure, it is evident that the combination of $ps = 40$ and $ts = 20$ dominates the other two tested combinations for all instances, except in the instance of rue de londres, where the combination of $ps = 100$ and $ts = 20$ yields better results for 0.22%. Based on parameter values, in overall, it can be observed that there is no need to increase the population size beyond 40, as that would contribute to longer computation times. Instead, it is suggested to have a larger horizon of tournament size (half of the value of $ps$ parameter) when selecting parents for breading the next population.

Fig. 7.

Pop size (ps) and tournament size (ts).

Fig. 8.

Crossover probability.

Fig. 9.

Mutation probability.

Figures 8 and 9 depict the results regarding the individual probabilities used for applying crossover and mutation operators. The empirical experiments show that the application of the crossover and mutation operator with a probability 50% is the preferred scenario over the complete test set, except for the instance of rue de londres, where it is suggested to have a larger probability of application of the mutation operator (i.e. 90%). Nevertheless, since for the probability value of 90%, the GA approaches does not perform better for the instance of lets go higher, which is more complex than the instance of rue de londres, we assume the value of 50% as the tuned value for the mutation probability parameter.

In Fig. 10, we show the results of the experiments for three different modalities of applying the hill climbing algorithm during a generation (i.e. iteration). From the figure, it is evident that the application of the hill climbing algorithm has a noticeable effect on the quality of solutions for all instances, especially for the instance of opera, where the difference from the case when the hill climbing is not applied, is around 18%. Further, out of the two evaluated modes of the application (i.e. 150 or 300 iterations) of the hill climbing algorithm, the results suggest that its intensity of use should be around 150 iterations per a single generation of GA approach.

Fig. 10.

Hill climbing iterations.

Figure 11 shows the differences in the results of the GA approach when applying (or not) the smart shift operator. It is obvious that the employment of the smart shift operator, as part of the mutation strategy, does help in producing better results for all instances, which, for the instance of opera goes beyond 3%. In addition, in Fig. 12, we present the results of the experiments with different radiuses (i.e. horizons) of the smart shift operator. Based on the results for the three different values of the smart shift radius (i.e. 3, 5 and 10), it is suggested that the value of 5 outperforms all the other options for the complete test set, although this difference does not go beyond 0.35% in any of the instances.

Fig. 11.

Application of smart shift operator in GA.

Fig. 12.

Neighbourhood shift radius in GA.

5.4. GRASP approach

In a similar way as GA approach, the GRASP approach has been tested by experimenting with six different fine-tuning parameters. Besides tests with application or not of the smart shift operator, and its parameter about neighbourhood shift radius, the GRAP approach has been evaluated by experimenting with four other parameters, namely, percentage of components, maximum iterations for construction, maximum iterations with no improvement and frequency of application of “Pop in construction” mechanism.

Figure 13 presents the results about the percentage of components that will be selected to make up the restricted candidate list, which is utilized within the construction phase. The results indicate that the best scenario over all instances is the case when the percentage of components is 10. However, the diagram shows that for the charleston road and lets go higher instances, the GRASP approach is not sensitive to the value of this parameter, since the results are (in average) the same for all three values that are considered for experimentation. In Fig. 14, we depict the results that show the effect of the number of iterations of the construction phase within the GRASP approach. From the figure, it can be noticed that for rue de londres and opera instances, the best performing variant is when GRAP runs for 10 iterations during the construction phase, while for the other two instances, this parameter has no effect (charleston road) or little importance (lets go higher).

Fig. 13.

Percentage of components.

Fig. 14.

Maximum iterations for construction.

The diagram in Fig. 15 shows the results about the parameter for the number of iterations of execution of the algorithm without improvements. As with two previous parameters, the largest impact of this parameter can be noticed for the instances of rue de londres and opera, where, for the earlier, the difference is smaller (0.08%), whereas for the latter, the difference goes up to 0.88%. The best variant over all instances is when this parameter has the value of 2500. Any further increase of the values of this parameter only worsens the quality of the solution, whilst it also contributes to longer computation times.

Fig. 15.

Maximum iterations with no improvement.

Figures 16 and 17 presents the experiments of the GRASP approach in relation to the application of the smart shift operator. The results indicate that the application of the smart shift operator does help in improving the quality of solutions for all instances, and especially in the instance of opera, where the improvement is substantial (3.74%), but also for the instance of rue de londres, where the improvement is 1.14%. Furthermore, in Fig. 17, by analysing all the instances of the test set, one can notice that the best value for the parameter of neighbourhood shift radius is 5. In this case, the improvement, in comparison to the other value options, which are 3 and 8, stands at 0.64% and 0.96%, respectively.

Fig. 16.

Application of smart shift operator in GRASP.

Fig. 17.

Neighborhood shift radius in GRASP.

Fig. 18.

Frequency of application of “pop in construction” mechanism.

In Fig. 18, we present the results about the parameter that determines the frequency of application of the mechanism “Pop in construction”. This diagram shows that the “Pop in construction mechanism” produces the maximal effect when it is applied twice during the construction phase, which is a fact also noted down in Section 4.5.2, when describing the construction phase of the GRASP approach. As seen in the figure, applying it more often does not yield to better results, in terms of quality of solutions, while it would also increase the computation time, due to its effect of partial deconstruction of the running solution.

5.5. Comparison of the best results

After tuning the values of all parameters, both approaches have been executed five more times with best parameter settings over the complete test set. The duration of the computation time, for a single execution of a given approach against the individual instances, has remained the same as in the case when the parameter values are tuned (refer to Section 5.2).

In Table 3, we present the best results achieved by both (GA and GRASP) approaches, which are detailed for individual instances. These results are compared (by means of percentage gap) against the best-known results achieved by AIM Tech (AT) team during the Google Hash Code competition [13], as well as between the two approaches themselves.

Table 3
Comparison of best results of GA and GRASP

Instance AT GA vs AT (%) GRASP vs AT (%) GA vs GRASP (%)

Rue de Londres 59,530,002 0.710 0.540 0.239

Opera 176,320,008 1.700 2.200 −0.294

Charleston road 21,963,069 −0.0015 −0.0015 0.000

Let’s go higher 290,252,302 0.043 0.053 −0.233

Average: 0.613 0.698 −0.0718

Instance	AT	GA vs AT (%)	GRASP vs AT (%)	GA vs GRASP (%)
Rue de Londres	59,530,002	0.710	0.540	0.239
Opera	176,320,008	1.700	2.200	−0.294
Charleston road	21,963,069	−0.0015	−0.0015	0.000
Let’s go higher	290,252,302	0.043	0.053	−0.233
Average:	0.613	0.698	−0.0718

In overall, the results indicate that both, GA and GRASP approach, are competitive to the approach of AIM Tech team, where the gap, when averaged over all test instances, is only 0.613% and 0.698%, respectively. In relation to the specific instances, the opera instance remains the most challenging for both presented approaches, with the gap of 1.7% and 2.2 % for GA and GRASP, respectively. In the other hand, as shown in Table 3, both approaches slightly outperform the AIM Tech team results when it comes to the instance of charleston road, where the results are better for 0.0015%, which means that new best solutions are found in this instance. The new best-found value in the instance of charleston road is 21,963,274.

In terms of mutual comparison between the GA and GRASP approaches, when the results are averaged over the complete test set, the GA approach produces somewhat better results than the GRASP approach, where the margin is less than 0.1%. However, the GRASP approach outperforms the GA approach when it comes to solving the instance of rue de londres for margin of little bit more than 0.2%.

6. Conclusion

In this paper, we presented two meta-heuristic based methods for solving the problem of router placement in a two-dimensional area, which might be applicable in the domain of wireless network design. The first method is based on Genetic Algorithms, whereas the second one is based on the Greedy-Randomized Adaptive Search Procedure. While, both approaches are known for their abilities to diversify and intensify the search process when needed, in this implementation, they are both further empowered with intensification features by embedding a Hill Climbing (HC) algorithm in two different phases: (1) employing HC within their standard phases and (2) executing HC as a post processing phase.

The experimental results show that both, GA and GRASP approach can obtain comparable results to the ones known in the literature. In three, out of four instances, the averaged results show a gap of no more than 1.7% and 2.2% of the GA and GRASP approach respectively. Even more, for one of the instances (charleston road), both approaches slightly outperform the current results in the literature, meaning that the presented approaches have the capabilities of obtaining new best results. Further, when comparing the GA and GRASP approaches between themselves, the earlier, slightly perform better than the latter for three of the considered instances.

In the future, the work in this paper could be further improved in several different directions, where two of them could be the following: (1) algorithm improvement and (2) extension of the problem with various features. With respect to algorithm improvement, it would be interesting to investigate other modalities in improving Steiner Tree algorithm about the calculation of the cost of optimal router connection or exploring other alternative methods for such calculations. On the other hand, in the aspect of problem extension, one possibility could be allowing routers with different coverage (radius) ranges, as well as assigning weights to various cells, so that some parts of the area (to be covered with Internet access) are prioritized in comparison to the others.

Footnotes

Acknowledgements

We thank Prof. Hamed Ahmadi from the School of Computer Science and Electronic Engineering at University of Essex for reading this paper and helping us to improve it with his valuable comments.

Conflict of interest

None to report.

References

I.F.

Akyildiz,

Wang and

Wang, Wireless mesh networks: A survey, Computer networks 47(4) (2005), 445–487. doi:10.1016/j.comnet.2004.12.001.

Amaldi,

Capone,

Cesana,

Filippini and

Malucelli, Optimization models and methods for planning wireless mesh networks, Computer Networks 52(11) (2008), 2159–2171. doi:10.1016/j.comnet.2008.02.020.

Benyamina,

Hafid and

Gendreau, Wireless mesh networks design – a survey, IEEE Communications surveys & tutorials 14(2) (2012), 299–310. doi:10.1109/SURV.2011.042711.00007.

Bhandari,

C.A.

Murthy and

Pal, Genetic algorithm with elitist model and its convergence, International Journal of Pattern Recognition and Artificial Intelligence 10(6) (1996), 731–747. doi:10.1142/S0218001496000438.

Brazil,

Graham,

Thomas and

Zachariasen, On the history of the Euclidean Steiner tree problem, Archive for history of exact sciences 68(3) (2014), 327–354. doi:10.1007/s00407-013-0127-z.

D’Angelo,

Rampone and

Palmieri, An artificial intelligence-based trust model for pervasive computing, in: 2015 10th International Conference on P2p, Parallel, Grid, Cloud and Internet Computing (3pgcic), 2015.

G.L.M.

D’Angelo and

Rampone, Automated eddy current non-destructive testing through low definition lissajous figures, in: 2016 IEEE Metrology for Aerospace (MetroAeroSpace), 2016.

T.A.

Feo and

M.G.C.

Resende, A probabilistic heuristic for a computationally difficult set covering problem, Operations research letters 8(2) (1989), 67–71. doi:10.1016/0167-6377(89)90002-3.

A.A.

Franklin and

C.S.

Ram Murthy, Node placement algorithm for deployment of two-tier wireless mesh networks, in: IEEE GLOBECOM 2007-IEEE Global Telecommunications Conference, 2007.

10.

F.W.

Glover and

G.A.

Kochenberger (eds), Handbook of Metaheuristics, Vol. 57, Springer Science & Business Media, 2006.

11.

Goldberg and

Deb, A comparative analysis of selection schemes used in genetic algorithms, Foundations of genetic algorithms 1 (1991), 69–93.

12.

D.J.

Goodman, The wireless Internet: Promises and challenges, Computer 33(7) (2000), 36–41. doi:10.1109/2.869368.

13.

Google HashCode, “Google #hash code,” 24 10 2017. [Online]. Available: https://hashcode.withgoogle.com/past_editions.html.

14.

Kotz and

Essien, Analysis of a campus-wide wireless network, Wireless Networks 11(1–2) (2005), 115–133. doi:10.1007/s11276-004-4750-0.

15.

Levitin and

Mukherjee, Introduction to the Design & Analysis of Algorithms, Vol. 3, Pearson Education, 2011.

16.

C.-C.

Lin,

Y.-S.

Li and

D.-J.

Deng, A bat-inspired algorithm for router node placement with weighted clients in wireless mesh networks, in: Communications and Networking in China (CHINACOM), 2014 9th International Conference on, 2014.

17.

Luke, Essentials of Metaheuristics, Lulu, 2013.

18.

Maneewongvatana and

Mount, It’s okay to be skinny, if your friends are fat, in: Center for Geometric Computing 4th Annual Workshop on Computational Geometry, Vol. 2, 1999.

19.

S.N.

Muthaiah and

Rosenberg, Single gateway placement in wireless mesh networks, in: Proc. ISCN 8, 2008.

20.

Resende and

Ribeiro, Greedy randomized adaptive search procedures: Advances and extensions, 2017.

21.

M.G.

Resende and

C.C.

Ribeiro, Greedy randomized adaptive search procedures: Advances, hybridizations, and applications, in: Handbook of Metaheuristics, Springer, Boston, MA, 2010.

22.

Sgurev,

Yager,

Kacprzyk and

Atanassov, Recent Contributions in Intelligent Systems, Springer International Publishing, 2017.

23.

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

24.

C.-W.

Tsai,

P.-W.

Tsai,

J.-S.

Pan and

H.-C.

Chao, Metaheuristics for the deployment problem of WSN: A review, Microprocessors and Microsystems 39(8) (2015), 1305–1317. doi:10.1016/j.micpro.2015.07.003.

25.

Vanhatupa,

Hannikainen and

Hamalainen, Genetic algorithm to optimize node placement and configuration for WLAN planning, in: ISWCS 2007. 4th International Symposium on Wireless Communication Systems, 2007.

26.

Xhafa,

Barolli,

Sánchez and

Barolli, A simulated annealing algorithm for router nodes placement problem in wireless mesh networks, Simulation Modelling Practice and Theory 19(10) (2011), 2276–2284. doi:10.1016/j.simpat.2010.08.014.

27.