1 Introduction

The demand for wireless access has increased over the last decade. Features such as mobility, scalability, and low deployment cost seem to justify the increased interest in wireless local area networks (WLANs). Extended Service Set (ESS) WLANsFootnote 1 have special importance as they allow the roaming of users among access points (APs) [37] and ensure their mobility over large areas without noticeable connection drops. These networks are commonly deployed in sizable facilities such as airports, universities, and shopping malls.

Many WLAN design approaches are planned based only on network coverage, where the designer aims to minimize the wireless dead zones areas (i.e., non-signal areas). Other important aspects such as interference, user demands, and AP load balance are frequently neglected. However, these aspects should not be ignored, given of their key roles in ensuring network service quality. For example, several real-time applications such as video conferencing, voice over Internet Protocol (VoIP), and cross-platform instant messaging demand stable Internet access and low latency. Currently, the above-mentioned requirements have become even more relevant with the BYOD (bring your own device) trend, in which users expect to be on-line all the time using their mobile devices [38].

The over-provisioning of APs can cause additional costs, as well as the reduction of wireless network performance because the number of non-interfering channels is limited to three. Consequently, the occurrence of AP interference is inevitable, mainly in large-scale WLANs [22, 26]. Therefore, such AP devices should be best installed to cover a pre-set area, attend client demands, and insure efficiency and low interference.

In practice, the majority of WLANs are overcrowded in specific areas because of common interests of clients (e.g., restaurants, coffee shops, food courts, living areas). The combination of this behavior and the demand for different services generates an unbalanced load for networks, which can affect service quality and throughput [7, 29, 57]. Thus, load balancing should be addressed during the network design for operational and functional use. Hence, efficient load-balancing strategies should associate clients with access points, considering AP loads with available received signal strength (RSS).

Challenges related to WLAN planning (i.e., AP placement and channel assignment) have been proven to be NP-hard problems for most available formulations [8, 19, 21, 23, 27]. This complexity precludes the use of exact methods for solving moderate-to-large instances. In this context, metaheuristics can be suitable methods to achieve near-optimal solutions within reasonable processing times. Further, they can be implemented to improve scalability over deterministic methods. These features justify the rising employment of metaheuristics for WLAN design, as illustrated in [4, 6, 33, 34, 37].

This work proposes a hybrid algorithm approach for WLAN planning, in which network structure, load balancing, and channel assignment problems are explicitly addressed. The objective of this approach is the maximization of both network balance index and signal-to-interference-plus-noise ratio (SINR). Three sets of constraints are also modeled: minimum area and demand coverage, AP bandwidth capacity, and channel availability. The proposed algorithm employs evolutionary operators developed specifically to improve its convergence on the WLAN planning problem. This strategy was previously considered in other contexts such as power system design [12, 51], achieving successful results. The developed approach provides efficient WLAN projects within an acceptable runtime.

This manuscript is structured as follows. Section 2 presents a brief review of state-of-the-art WLAN planning works. Section 3 addresses the problem characteristics. Section 4 presents the mathematical model. Section 5 describes the proposed approach. Section 6 approaches the considered scenarios, and finally, Section 7 presents an analysis of the results.

2 Brief review of state-of-the-art WLAN planning-related works

A wide range of WLAN planning-related works have addressed the problem from the exclusive perspective of Wi-Fi coverage, ignoring key factors of network deployment, such as load balance, client demand, and channel assignment. Frühwirth and Brisset [22] employed a Branch and Bound algorithm to minimize the quantity of APs in an 802.11 network, measuring its coverage based on a set of points in a specific grid. Mateus et al. [42] proposed a model to optimize network coverage considering a limited number of APs on two floors of a university building. The authors used Integer Linear Programming (ILP) to maximize the signal strength at the client and minimize interference among the APs. In [31], the authors employed a constructive heuristic, in which new APs are placed, one by one, until the coverage constraints are met. A new global optimization algorithm was used in their work to define AP transmit power. The effects of client agglomeration and interference among APs were not properly considered.

Bejerano and Han [9] proposed a method to perform load balancing by reducing AP coverage in overcrowded areas considering user concentration and AP loads. This approach is similar to the cell-breathing procedure, commonly employed in cellular networks. Cell breathing was also used by [44], in which Moreno et al. developed a Binary Particle Swarm Optimization algorithm to maximize Wi-Fi network coverage while minimizing the number of APs. The authors modeled each AP transmit power as a variable to reduce network interference, but they ignored client demands. In addition, the problem of AP location is only considered in [44] and it is restricted to a small number of candidate points.

Deus et al. [18] proposed a WLAN design approach modeled as a Constraint Satisfaction Problem. In the case of a project requirement violation, a heuristic based on Tabu Search was employed to reduce it by varying AP positions and power levels. If a feasible solution was not found, a new AP would be added to restart the design process. Cell breathing was employed for load balancing. Further, a survival mechanism was enabled to address node failures. The major limitations of the above-mentioned study are: (i) it is based on constraint satisfaction (i.e. not ensuring optimality of common objective functions); (ii) if a feasible solution is not found, new solutions with more APs will be tested, thus improving SINR; (iii) it is not scalable (i.e., it cannot deal with large instances within a reasonable time); and (iv) it is not flexible enough to accommodate variations in the number of clients and their demands.

Regarding evolutionary algorithms, Lima et al. [37] divided the WLAN design into two stages: the first one solves the problem of AP location with a multiobjective Genetic Algorithm (GA) aiming at minimizing the number of APs and maximizing load balance; the second one performs channel allocation using a simple heuristic method, which was built considering outdoor WLANs. Walls and obstacles in the environment were not modeled. Furthermore, that work considered the optimization of continuous variables, expanding the search space and complicating the treatment of constraints related to AP candidate positions. Scully and Brown [50] presented a single-objective GA for network load balancing in crowded areas. The algorithm was presented with other load-balancing techniques used in WLANs and they reported a major improvement in network throughput. However, essential factors were not considered, such as quantity, location, and operating channels of the access points. Goudos et al. [27] used a multiobjective Biogeography-Based Optimization algorithm to design a hybrid wireless network combining APs of a WLAN and Long Term Evolution (LTE) femtocells. The considered objectives were the maximization of both network coverage and RSS, and the minimization of AP transmit power. Their approach was compared to two multiobjective evolutionary algorithms (i.e., NSGA-II and GDE3), disregarding client concentration and environment obstacles.

In [56], the authors used a Variable Neighborhood Search algorithm to solve the WLAN planning problem. Their method intended to minimize the positioning error and maximize SINR; however these objectives were reduced to one via a weighted sum. A set of discrete candidate positions were previously built to reduce design options. Farsi et al. [21] handled WLAN design using a three-step approach. First, the authors solved the WLAN coverage problem using Markov clustering and ILP methods. Then, they used three heuristics to handle the frequency-planning problem. Finally, the third stage applied an algorithm called VFPA to the current incumbent solution to solve both problems together. The objectives were to maximize SINR and minimize the amount of APs. Customer agglomerations or barriers (i.e., walls) were not considered in the formulation. Additionally, the approach was only feasible for a small amount of APs.

There are other WLAN planning-related works based on multiobjective optimization. Zhang et al. [54] proposed a GA-based method to perform AP placement and channel assignment. It attempted to maximize coverage while minimizing interference and the quantity of APs. Practical aspects such as obstacles and user agglomeration were ignored. In [39], the authors implemented a hybrid algorithm (GA + Quasi-Particle Swarm Optimization) applied to maximize the weighted sum of three objectives: maximization of coverage, minimization of number of APs, and minimization of human exposure to AP electric fields. The algorithm was compared to an indoor wireless propagation prediction tool and an adaptive Differential Evolution (DE) variant in two scenarios. Nevertheless, obstacles were not considered, leading to the overestimation of coverage and electric fields experienced by the users. Gamal et al. [23] applied an adaptive variant of Multiobjective Evolutionary Algorithm based on Decomposition (MOEAD/D-DE-ATP) to transmitter placement in heterogeneous networks. The algorithm aimed to maximize the quality of user connections and minimize the network unbalance and interference in overlapping AP areas. Channel assignment was ignored, rendering inaccuracy of signal interference estimations. Further, the approach considered the application of a small quantity of APs in the environment (i.e., maximum of six), raising doubts regarding its scalability to medium and large-scale networks.

Several researchers have studied channel assignment methods in 802.11 networks. Leung and Kim [34] developed a heuristic to reuse channels based on AP loads. Mishra et al. [43] were among the pioneers considering the use of partially overlapping channels (POC) in 2.4 GHz WLANs. In this work, a channel overlap index was defined based on experiments. Similarly, Zhao et al. [55] also addressed POC considering overcrowded WLANs. Their POC assignment algorithm indicates the number of APs to be used and their channels as an additional parameter for WLAN planning. This strategy was based on the SINR model targeting to maximize the overall WLAN capacity. Balbi et al. [8] proposed a centralized channel allocation method based on the Degree of Saturation Algorithm (DSATUR). Their method adjusts its settings automatically according to environment conditions and interference from other unmanaged networks. Mahonen et al. [41] proposed a greedy algorithm based on vertex-coloring techniques to find a channel assignment that maximizes the amount of neighbor APs using different channels. Eisenblätter et al. [19] proposed an algorithm to define a suitable channel mapping to multi-floor WLANs, intending to reduce co-channel interference and increase the average network speed.

Despite the substantial contributions of the referred works, most of them have considered the design problems involved in WLAN deployment (e.g., AP positioning, channel allocation, and load balancing) separately. Moreover, many of the cited works are limited to non-obstacle environments or the use of a poor representation of client profiles in real situations. Table 1 presents a comparison of these works regarding different aspects of WLAN design.

Table 1 Comparison of related works
Full size table

The proposed approach differs from the others mentioned because it gathers several essential aspects of WLAN planning in the same study. It is capable of: (i) addressing AP placement, load balancing, and channel assignment together; (ii) considering obstacles and barriers in the environment; (iii) evaluating different client profiles and; (iv) assessing robustness regarding failures. Finally, a proper multiobjective approach based on metaheuristic methods is employed to solve the WLAN problem without losing scalability.

3 Problem features

Medium and large-scale ESS WLANs must be properly designed to reduce installation costs and improve quality of service. WLAN planning is a complex task because it depends on the solution of a highly constrained nonlinear optimization problem with mixed continuous and discrete variables. Further, several factors must be considered in the WLAN design, such as covered area, user demand, client concentration, access point roaming, and AP interference. These issues are addressed in the next subsections.

3.1 Location and coverage of APs

The classical WLAN coverage problem is to find the smallest set of APs to cover a given demand point set. A demand point (i.e., user) can be covered by an AP if its RSS is higher than the minimum reception threshold [22, 25, 48]. The quantity of APs and their locations are key aspects of network planning because they affect cost, performance, service quality, and the range of the Wi-Fi network.

In most cases, AP allocation is performed ad hoc based on the network designer experience [4]. It is worth emphasizing that the manual design of large-scale WLANs is difficult when considering all relevant aspects. In these cases, it is necessary to: (i) find the set of AP locations to achieve minimum installation cost; (ii) cover the service area of the WLAN properly; (iii) attend to different client demands without exceeding the bandwidth of any AP; and (iv) use non-interfering channels for the lowest network interference.

In addition, other aspects of the WLAN cannot be ignored, such as the characteristics of the area where the network is planned (e.g., obstacles, interference between floors), 802.11 standard (B/G/N/AC), model and characteristics of the equipment, and the maximum supported number of clients. This complexity typically justifies the use of optimization algorithms to deal with AP locations and coverage.

3.2 Load balance

Regarding the 802.11 standard [1], clients can roam quickly among the APs of an ESS WLAN. However, Wi-Fi adapters frequently prioritize the AP with maximum RSS, i.e., they do not employ a mechanism for WLAN load balance. This strategy can result in a low-quality network when a large number of clients are connected to the same AP [9, 33, 50]. Studies have indicated that most WLAN clients have low overall mobility and stay connected to the Wi-Fi network from limited areas [7, 29, 57]. This behavior tends to concentrate clients into a minor set of APs reducing network throughput significantly.

It is essential to consider different user bandwidth requirements during the design process because WLAN use is not limited to basic website access. It is also important to ensure realistic data rates for the latest apps to reduce the probability of AP overloading. WLAN load balancing has a key role to ensure high-quality networks and can be performed automatically when the client connects to any available AP. It was initially proposed by the scientific community [45]; recently, equipment manufacturers have developed proprietary solutions to establish efficient association criteria.

3.3 Channel assignment

WLAN transmitters share a unique broadcast medium. This means that only one user can send packages at any given time and location, otherwise, there may be packet collision resulting in network throughput degradation [24, 34, 41]. Data transmission in different channels is a simple alternative to avoid collisions. However, this option is limited on 2.4 GHz Wi-Fi networks because there are only three available non-interfering channels (i.e., 1, 6, and 11) [24, 52]. This restricted set of channels is justified because these networks operate in a free, unlicensed frequency known as ISM (Industry, Scientific, and Medical) band. The ISM band restricts the number of WLANs operating properly in the same area owing to interference. Thus, reusing the channels is inevitable in environments with many APs, making unfeasible the use of network full capacity [8, 42, 52].

An efficient channel allocation scheme must reduce packet loss caused by interference. Graph coloring is the most employed approach for WLAN channel assignment, however it is typically restricted to small networks due to the observed efficiency reduction when the number of APs increases. Therefore, the use of metaheuristics (e.g., Differential Evolution and Genetic Algorithms) is an alternative for channel assignment in medium and large-scale networks [13, 30, 38, 47].

3.4 Signal-to-interference-plus-noise ratio

In wireless communications, one requirement for a consistent bit rate is high SINR because it allows data reception and decoding by the radio [21, 26, 53]. This parameter becomes more critical with added distance and obstacles because they decrease the signal strength. There are two methods to overcome this limitation: increasing the transmission power or limiting the bit rates. However, the first one can cause other problems in large-scale ESS WLANs, especially regarding interference. The second one is not desirable by users searching for high-speed connections.

The interference generated by other APs operating in the same or adjacent channels also reduces the SINR of the AP because of higher accumulated interference in the environment. Hence, using the SINR model, it is possible to identify a direct relationship between maximizing throughput and minimizing total interference. This is the approach followed in this proposed work, as indicated in the mathematical model provided in the next section.

4 Problem statement

4.1 Mathematical model

The goal of the proposed problem formulation is to find the best AP locations and channels, and ensure compliance with coverage and demand requirements. Two conflicting objectives are considered: maximization of load balance index and average SINR for the users. We expect to obtain a set of Pareto-optimal solutions since this is a Multiobjective Optimization Problem (MOP). The following mathematical model was proposed in [36] and is given in the (1) to (10).

$$ \mathcal{X}^{*}, \mathcal{K}^{*} = \max_{X,Y,C,K} \left\{ \begin{array}{l} \displaystyle {I\beta(V,C)} \\ \displaystyle {SINR_{avg}}\\ \end{array} \right. $$
(1)

subject to:

$$ x_{min} \leq x_{i} \leq x_{max} \quad \forall i \in \{1,\ldots,N\} $$
(2)
$$ y_{min} \leq y_{i} \leq y_{max} \quad \forall i \in \{1,\ldots,N\} $$
(3)
$$ v_{i} \in \{0,1\} \quad \forall i \in \{1,\ldots,N\} $$
(4)
$$ c_{i,j} \in \{0,1\} \quad \forall i \in \{1,\ldots,N\} \ , \ \forall j \in \mathcal{C} $$
(5)
$$ c_{i,j} = 0 \ \text{ if } RSS_{i,j} < RSS_{min} \vee \displaystyle v_{i} = 0 $$
(6)
$$ \sum\limits_{i = 1}^{N} c_{i,j} \leq 1 \quad \forall j \in \mathcal{C} $$
(7)
$$ B_{i} \leq BW_{AP} \quad \forall i \in \{1,\ldots,N\} $$
(8)
$$ N_{clAP,i} \leq MAX_{clAP} \quad \forall i \in \{1,\ldots,N\} $$
(9)
$$ \frac{1}{|\mathcal{C}|} \cdot N_{C} \geq f_{cov} $$
(10)
$$ k_{i} \in \{1,2,3\} \quad \forall i \in \{1,\ldots,n\} $$
(11)

in which:

$$ N_{C} = \sum\limits_{i = 1}^{N} \sum\limits_{j = 1}^{|\mathcal{C}|} c_{i,j} $$
(12)
$$ N_{AP}(V) = \sum\limits_{i = 1}^{N} v_{i} $$
(13)
$$ I\beta(V,C) = \frac{\displaystyle \left( \sum\limits_{i = 1}^{N} B_{i}\right)^{2}}{\displaystyle \left[N_{AP}(V)\cdot \sum\limits_{i = 1}^{N}{B_{i}^{2}} \right]} $$
(14)
$$ B_{i} = v_{i} \cdot \sum\limits_{j = 1}^{|\mathcal{C}|} c_{i,j} \cdot d_{j} $$
(15)
$$ SINR_{avg} = \frac{\displaystyle \sum\limits_{j = 1}^{C} SINR_{i,j} \cdot c_{i,j}}{\displaystyle N_{C}} $$
(16)
$$ SINR_{i,j} = \frac{\displaystyle RSS_{i,j} \cdot t_{i,j}}{\displaystyle \sum\limits_{j = 1}^{C}RSS_{i,j} \cdot t_{i,j} \cdot r_{i,j} + Noise} $$
(17)
$$ RSS_{i,j} = Pt + Gt + Gr - PL(d_{i,j}) - \beta $$
(18)
$$ PL(d_{i,j}) = PL(d_{0}) + 10 \cdot n \cdot \log\left( \frac{d_{i,j}}{d_{0}}\right) + \sum PAF $$
(19)
$$ t_{i,j} = \left\{ \begin{array}{ll} 1, & \text{ if } RSS\geq RSS_{min} \text{ and } k_{p(C_{i})}=k_{j};\\ 0, & \text{otherwise.} \\ \end{array} \right. $$
(20)
$$ r_{i,j} = \left\{ \begin{array}{ll} 1, & \text{ if } i \neq j\\ 0, & \text{otherwise.} \\ \end{array} \right. $$
(21)

In the above equations:

  • \(\mathcal {X}^{*}\) is the set of efficient solutions. Each \(X^{*}_{i} \in \mathcal {X}^{*}\) is a solution with a set of n active APs, the x and y coordinates of such active APs and a list containing the association of client-AP.

  • \(\mathcal {K}^{*}\) is the set of channels. The decision vector, \(K^{*}_{i}, \in \mathcal {K}^{*}\) defines the mapping of the assigned channels to n active APs.

  • X and Y are vectors with the x and y coordinates of the APs.

  • C is a matrix that associates each client with an AP.

  • RSSi,j is the signal strength received from the APj on client Ci, in dB.

  • RSSmin is the minimum sensitivity threshold for the reception of the signal.

  • Bi is the bandwidth consumption of the AP i.

  • BWAP is the maximum bandwidth of an AP.

  • NclAP,i is the amount of users connected to the AP i.

  • MAXclAP is the maximum number of clients able to connect to a single AP.

  • \(|\mathcal {C}|\) is the total number of users in the scenario.

  • NC is the number of clients covered by at least one AP.

  • fcov is the coverage ratio.

  • NAP is the number of active APs, vi.

  • di,j is the Euclidean distance between client i and AP j.

  • SINRavg is the average SINR of the clients.

  • SINRi,j is the RSSi,j divided by the sum of the interference power from all interfering signals and the background noise power.

  • Pt is the transmitter power, in dBm.

  • Gt and Gr are gains of the transmitter and receiver antennas, respectively, in dBi.

  • PL(di,j) is the path loss between transmitter and receiver, in dB.

  • β represents other losses, in dB.

  • PL(d0) is the propagation loss, in dB, at a reference distance d0 from the transmitted signal.

  • PAF is the partial attenuation factor caused by obstacles.

  • APi is the access point that provides connection to the client Ci.

In this model, a given solution is said to be efficient if and only if there is no other one which is better with regard to one of the objectives, without it being worse with respect to the other objective. The Pareto front is the set of all efficient solutions.

Jain’s Fairness Index Iβ (14), as proposed in [14], is used to estimate load balance. This index is one if all active APs present the same load; it is near 1/n if the APs are significantly unbalanced.

Constraints (2) and (3) refer to space limits where the network is planned. Constraints (4) and (5) ensure that the variables vi and ci,j are binary. Constraint (6) states that an AP can cover a client if it is active and the RSSi,j is higher than the receiver sensitivity threshold RSSmin. Constraint (7) ensures that a client is not covered by more than one AP at the same time. Constraints (8) and (9) guarantee that the maximum capacities of the access points are not exceeded. Constraint (10) states that at least fcov% clients are properly covered. Finally, constraint (11) states the set of available non-overlapping channels. The values 1, 2, and 3 refer to channels 1, 6, and 11 for 2.4 GHz WLANs, respectively.

In the following equations, (18) and (19), PL(d0) are set to 47.6 dB for d0 = 1m and β to 2 dB. These values are chosen based on typical devices employed in 2.4 GHz wireless LANs. In indoor environments, signal loss is estimated based on the log-normal shadowing model [48] considering attenuations caused by obstacles. This model presents a suitable compromise between accuracy and computational cost, and is widely used in studies of WLAN networks [4, 22, 38, 46].

5 Proposed WLAN planning approach

This section proposes a new approach to WLAN design that receives as inputs: properly mapped indoor and/or outdoor area (e.g., walls, obstacles, bounds), expected consumption profiles, and equipment specifications (e.g., protocol, antenna gain). The proposed approach works in five steps:

  1. Step 1:

    Generate ten different sets of clients according to the provided consumption profile. Client positions are based on the occupation of the service area.

  2. Step 2:

    Generate a set of demand points, arranged on a regular grid in the coverage area with 0 kbps demand. These are not real clients; rather they are used to ensure coverage and user mobility around the network.

  3. Step 3:

    Apply multiobjective GA, “WLAN NSGA-II”, N1 times to identify efficient network topologies, each one composed of the AP set, their x and y coordinates, and their respective channels.

  4. Step 4:

    Apply single-objective GA, “Channel Assignment GA”, N2 times to improve the channel mapping achieved in Step 3.

  5. Step 5:

    Evaluate the final set of solutions achieved in Step 4 regarding possible changes of the clients. During this step, positions and demands are varied to generate multiple scenarios, in which the robustness of each solution is evaluated. Further, the WLAN projects are tested against failures in the APs.

Steps 3, 4, and 5 constitute the main contributions of this work; they are fully described in the next subsections.

5.1 WLAN NSGA-II

Based on the importance of all the aspects discussed in Sections 3 and 4, the WLAN optimization algorithm is designed to perform AP location and channel assignment together. This choice is reasonable because the quantity and location of APs are directly related to the interference caused in the environment. In other words, these factors are correlated and determine the quality of service offered to the WLAN clients.

The proposed algorithm, called WLAN NSGA-II, is based on the Non-dominated Sorting Genetic Algorithm II (NSGA-II) [17]; its specific adaptations and features are presented below.

5.1.1 Solution encoding and initial population

In WLAN NSGA-II, each individual is composed of 2N real values representing the x and y coordinates of N APs that could be installed. The parameter N, chosen by the designer, must be higher than the minimum quantity of APs required to ensure coverage requirement, mAP. If N > mAP, the algorithm has more access points to consider in the project; it could lead to improved solutions. However, greater N values can hinder algorithm convergence because the search space grows exponentially with the number of AP candidate positions. Therefore, the designer should consider the balance between flexibility and convergence to better choose N.

Consequently, it is key to estimate mAP to ensure that the solutions remain feasible. Hence, we propose a simple procedure to estimate this parameter at very low computational cost as follows:

  1. 1.

    Set mAP ← 0;

  2. 2.

    While required coverage level is not met, repeat:

    1. (a)

      Set mAP ← mAP + 1;

    2. (b)

      Solve K-means clustering algorithm for mAP clusters, considering RSS instead of Euclidean distance (see Section 7.1);

    3. (c)

      Evaluate solutions in step 2b regarding coverage.

The mAP returned by this procedure should be the lower bound for N. It is important to note that N = mAP will allow very low flexibility to the algorithm, which can result in low-quality solutions. Therefore, we recommend the adoption of a higher value for this parameter.

The initial population is built after the definition of the “N” parameter, in which, 1/3 of the individuals are created by a heuristic procedure that divides the service area into cells of equivalent size and randomly distributes N APs into them. Another 1/3 are created by the K-means clustering algorithm, varying the number of clusters from N/2 to N. For further details, refer to Section 7.1. The remaining individuals are generated randomly. The idea behind this mixed procedure is to increase the space coverage of the initial population and maintain individual variability.

5.1.2 Solution decoding

The candidate region for the APs is discretized into a finite set of points. This design choice is driven by three main reasons: (i) all functional terms can be preprocessed, enhancing algorithm speed; (ii) common design restrictions can be easily modeled, e.g., gutters, where the AP should necessarily be installed, or elevators, where the installation of APs is unfeasible; (iii) this choice does not affect the quality of solutions once the distance among candidate points is not long. This strategy makes the developed WLAN planning approach more suitable for application in real-world situations.

Space discretization is accomplished by simple rounding of the AP position to the nearest candidate point. This process is performed to generate the initial population and after each algorithm operation (e.g., crossover, mutation, and local search). Several tests were performed to define the most suitable distance (1, 2, 5, or 10 meters) among the AP installation candidate points. The 2-meter radius was adopted because it presented the best compromise between algorithm performance and solution accuracy.

We are likely to identify solutions to address the coverage requirements with less than N APs because the quantity of the concentrator devices represented in the solution is typically set greater than the minimum required number of APs. In this manner, a redundancy-control technique is adopted to handle the WLAN design. The installation/non-installation of APs is defined by a binary activation vector associated to each individual. Initially, all APs are activated and the activation vector is sorted such that the access points with the best coverage are in its last positions. Thus, the decoding operator attempts to disable each of the sorted APs by scanning the activation vector. Then, the solution is evaluated regarding the required coverage. The AP remains inactive if the constraint is fulfilled; otherwise, it is reactivated. This process continues until the test of the last AP.

After determining the APs to be activated, the association client-AP is performed to ensure service coverage and load balance. First, users are connected to the APs that provide them the highest signal strength. Nevertheless, as mentioned above, this association pattern can lead to unbalanced WLANs. A heuristic method is proposed to redistribute users among the APs to manage this drawback. This method identifies every client able to connect to an access point and tests all active APs with less than 90% of its capacity. The objective is to identify an optimal trade-off between RSS and network load balance, indicated in (22).

$$ AP_{j}^{*} = \min_{i} \left[\alpha \cdot \frac{RSS_{max}-RSS}{RSS_{max}-RSS_{min}} + (1-\alpha) \cdot\frac{load_{AP}}{BW_{AP}}\right] $$
(22)

In this expression, α = 0.7 is the weight assigned to signal strength term; RSSmin and RSSmax are the minimum and maximum thresholds for the RSS, respectively; BWAP is the AP bandwidth.

This strategy is applied on each access point whose load is greater than 1/3 of its maximum capability.

5.1.3 Solution evaluation

Since WLAN clients are not static, their modeling, as a single specific demand, can result in an unsuitable network project owing to eventual changes in access profile and user location. A feasible method to overcome this problem is to consider multiple client scenarios during the design. This feature is employed in the proposed approach, with each solution evaluated in ten different scenarios, all generated from the same profile. The solution performance assessment is performed based on the following rules:

  • solution fitness is set as the average of the ten client scenarios;

  • values assigned to constraints are the worst one observed among the ten scenarios.

The genetic operators (i.e., crossover and mutation) in WLAN NSGA-II can generate solutions that violate constraints such as maximum AP bandwidth or preset minimum coverage. Three penalties, (23), (24), and (25) are adjusted to address these infeasible solutions and are incorporated into the fitness calculation, as (26).

$$ P1 = \sum\limits_{i = 1}^{n} \max \left\{ \left[ 1 \ ; \ \epsilon^{0.05 \cdot \left( B_{i} - BW_{AP}\right)} \right] \right\} $$
(23)
$$ P2 = \sum\limits_{i = 1}^{n} \max \left\{ \left[ 1 \ ; \ \epsilon^{0.01 \cdot \left( N_{clAP,i} - MAX_{cl\_AP}\right)} \right] \right\} $$
(24)
$$ P3 = \max \left\{ \left[ 1 \ ; \ \epsilon^{5 \cdot \left( f_{cov} - cov \right)} \right] \right\} $$
(25)
$$ f_{v}^{\prime} = f_{v} \cdot P1 \cdot P2 \cdot P3 $$
(26)

in which cov is the coverage level observed for the evaluated individual and NclAP,i is the number of clients connected to AP i.

Note that feasible solutions are not penalized, as in these cases all constraint functions assume the value “1”.

5.1.4 Crossover and mutation

An enhanced crossover operator is proposed to generate the offspring solutions in WLAN NSGA-II, in which different rules are used to generate the two offspring solutions (O1 and O2) from the selected parents (P1 and P2), as follows:

  1. 1.

    O1 is generated by simply performing uniform crossover [16] from P1 and P2.

  2. 2.

    O2 is generated via a more complex process:

    1. (a)

      at first, the APs of P2 are evaluated randomly; each one is moved to the position with maximum similarity to P1. The similarity is measured based on the RSS among the APs;

    2. (b)

      second, uniform crossover is applied.

This process re-sorts P2 to increase its similarity to P1, improving locality and attenuating the effects of representation neutrality. Simultaneously, the random evaluation of the APs avoids excessively biased operations and poor performance on the crossover of the last positions of the individuals.

Finally, the mutation is performed using the classical polynomial mutation operator [16].

5.1.5 Local search

The WLAN NSGA-II algorithm embeds a local search operator to reinforce its exploitation capacity, leading candidate solutions to the nearest local optimum. The operator works as follows:

  • Select up to 25 non-dominated individuals with higher crowding-distance values from the current population.

  • Perform orthogonal variations in coordinates x and y of each AP (i.e., gene), in every selected solution.

  • Compare new and original solutions regarding dominance for each variation, selecting the non-dominated one. If both are non-dominated solutions, then select the new one.

  • The local search ends when all individual active positions are tested.

This process repeats every ten generations of WLAN NSGA-II. The step size starts at 6 m, decreases to 4 m after 1/3 of the generations, and to 2 meters after 2/3 of the generations. The intent of this strategy is to apply a broader search at the beginning of the optimization process and reinforce local search in the last part of the iterative cycle.

5.1.6 Channel assignment in WLAN NSGA-II

Channel Assignment is necessary to estimate interference and SINR in each population individual. Whereas this operation is performed thousands of times during the execution of the algorithm, it is important that its implementation is as efficient as possible.

The DSATUR algorithm [11] was adopted in other works to assign the AP channels [24, 37, 41]. A weighted variant of this algorithm was employed in [37] for the same purpose. In this work, AP loads are used as the criterion to decide between two vertices with the same degree of saturation. When channel reusing is inevitable, (16) is evaluated to find the channel that provides the lower interference. Such a variation provides an acceptable approximation of the optimal solution with the advantage of requiring low processing time. This weighted version is employed inside WLAN NSGA-II.

5.1.7 Aggregation of efficient sets

At the end of N1 runs of WLAN NSGA-II, N1 Pareto-front approximations become available. These fronts are aggregated into a single set, filtered by Pareto dominance to remove the dominated solutions. Finally, the Ncand solutions with the highest crowding distance are chosen for analysis in the next step; the remaining ones are discarded.

The purpose behind the multiple runs is to attenuate the influence of the random behavior of evolutionary algorithms in the final set from Step 3. Further, the shrinkage of the final set to Ncand solutions is intended to reduce the number of available choices to simplify the decision making.

5.2 Channel assignment GA

The heuristics employed for channel assignment inside WLAN NSGA-II are intended to find reasonable solutions with lower processing times. In general, solutions from this method can be improved if a more efficient optimization algorithm is employed. A single-objective GA was proposed in [38] to minimize the interference on WLANs. Given a network topology with known AP coordinates, client-AP associations, and a candidate set of channels for the APs, the algorithm searches for a more efficient AP channel distribution regarding interference without affecting load balance.

The Channel Assignment GA is adopted in this work; it has demonstrated considerably better results compared to those achieved by traditional methods including the weighted DSATUR heuristic. It is a GA with integer representation, uniform crossover, and flip mutation. The selection is performed using a traditional binary tournament, in which two individuals are selected at random (with replacements) and the best one is chosen. Elitism is also employed; it ensures that the best individual is always in the current population. The stop criterion is the number of generations. For additional information regarding this algorithm, please refer to the original reference.

The Ncand solutions achieved by WLAN NSGA-II are used as inputs for the Channel Assignment GA. At the end of the process, there can be non-efficient solutions after SINR improvement. These solutions are ignored in the next step of the proposed approach.

5.3 Sensitivity analysis

The solutions obtained by the genetic algorithms are submitted to two sensitivity analysis procedures to evaluate their robustness regarding client profile variation and AP losses.

5.3.1 Sensitivity analysis – client positions and demands

It is well known that user mobility among APs (i.e., handoff) and changes in network bandwidth consumption must be considered during WLAN planning. Once the APs are fixed, it is desirable to adopt a layout that can manage changes of user profiles without significant impact on the solution quality. The use of ten different scenarios in WLAN design is performed to simulate this variability. The quantity of scenarios is chosen to control computational complexity of the method; however, it is not typically sufficient for properly modeling client variability. Therefore, the sensitivity analysis step of the proposed approach is based on robustness evaluation of the solutions returned by the Channel Assignment GA regarding a large number of random disturbances in the location and the demand of the network users. Three quality criteria are observed for a set of Nscen candidate scenarios: coverage, balance index, and average SINR. The results obtained in this phase help the decision maker to choose among the design options provided by the genetic algorithms.

5.3.2 Sensitivity analysis – AP failures

As discussed in Section 3, WLANs are susceptible to several problems, including equipment or communication failures, which can disable part of the network APs and disconnect users. In an ESS WLAN, a simple solution to handle this problem is the use of adjacent APs to cover the regions experiencing failures. However, these devices must have available resources (e.g., bandwidth) to serve the uncovered clients.

Therefore, it is important to analyze the robustness of WLAN projects regarding AP losses. A set of Nscen scenarios is tested to assess solution robustness considering simultaneous failures of up to three APs. In this test, only coverage is considered as the fault robustness criterion. We can see that during network failure, the crucial issue is the maintenance of user connections. Obviously, the remaining problem constraints (e.g., bandwidth and the maximum number of clients per AP) are evaluated to estimate coverage. As in the other sensitivity analysis step, network survival performance can provide decision-making support.

6 Scenarios and parameters

A survey of network requirements is a crucial phase to achieve an efficient WLAN design. Aspects such as the total number of Wi-Fi users, their expected positions, and load consumption cannot be ignored. Further, user mobility and their eventual agglomeration should be considered in the WLAN planning process.

The goal of our experiments is the emulation of real scenarios with high data demand and a realistic distribution of users. The floor plan of a shopping mall from Google maps was used as a model. Each floor is 10,000 m2 and the only obstacles are walls. The food court floor was selected because it presented the highest concentration of users during the day. A total of 512 clients were placed in the area; the scenario situations varied on how they were positioned:

  • The first scenario simulated a situation where most users were crowded in specific areas. Three clusters with different centroids were placed following Gaussian distributions. The first simulated 140 users in the food court and two other clusters, each of 70 clients, concentrated in other regions with high customer flow. The remaining 232 clients were distributed randomly, following a uniform distribution.

  • The second scenario had the following configuration: 100 customers arranged in a cluster at the food court; 270 clients distributed among the mall shops; and the other 142 randomly arranged based on a uniform distribution.

These characteristics complicated the solution because it was necessary to ensure network coverage and performance. See details in Table 2.

Table 2 Scenario parameters
Full size table

The load consumption of users was randomly defined within the [20 Kbps, 2 Mbps] interval. These values were chosen to reproduce a diversity of apps ranging from simple email checking to high quality video playback on a gadget. On average, the total demand of the clients was approximately 1 Mbps. The proposed WLAN planning approach was entirely implemented in Matlab. WLAN NSGA-II and Channel Assignment GA were set with the parameters shown in Tables 3 and 4, respectively. Finally, N1, N2, Ncand, and Nscen were set as 33, 33, 15, and 1,000, respectively. The choice of these parameters was made based on a combinatorial experiment, in which the algorithms were executed considering the following parameter values: 50 and 100 individuals in the population; 100, 500, and 1,000 generations; and 5, 10, and 20% of mutation rate. After combining all possibilities, a visual inspection of the final approximation sets was performed to verify which configuration delivered the most consistent solutions. The smallest quantity of APs required to comply with the minimum coverage level (mAP) was estimated using the procedure described in Section 5.1.1. This indicated that at least 12 APs were required to ensure 99% coverage, as displayed in Fig. 1. There were preliminary tests performed to set the value of N, considering, N = k ⋅ mAP, with k ∈ {1, 2, 3, 4}. From them, the most suitable choice for N was 24 APs (k = 2). For k > 2, we observed almost identical final solutions achieved at considerably higher processing times.

Table 3 WLAN NSGA-II parameters
Full size table
Table 4 Channel assignment GA parameters
Full size table
Fig. 1
figure 1

Estimation of mAP. Values greater than 12 are evaluated to illustrate the effect of increasing the number of clusters in network coverage

Full size image

6.1 Performance comparability

In recent years, the community has attempted to introduce tools to assess WLAN performance. Simulation tools, such as NS3 [49], were developed to estimate performance of specific WLAN configurations. There are also some testbeds for simulating the 802.11 interface via network adapters or Software Defined Radio, such as w-iLab.t [10], Orbit [40], Emulab [40], BOWL [5], and EXTREME [5].

Although these tools are useful for some applications, they are not suitable to evaluate configurations in the WLAN planning problem. The simulation tools do not model all the important aspects of designing WLANs, such as high-density client environments, user demands, and their mobility. Besides, they do not deal with large-scale WLANs. So, such tools do not allow comparison of two different WLAN planning methods under identical scenarios. Finally, the above-cited testbeds are restricted to the calibration of path-loss models or development and validation of new medium access control (MAC) protocols in 802.11 networks.

Regarding Wi-Fi planning, we could not identify any works in the literature able to provide all the required data for result replication. Moreover, these works do not provide source code for their methods. These factors make a fair comparison of WLAN design approaches difficult. Hence, to address this lack of reproducibility, all datasets used in this work are available through the GitHubFootnote 2 repository. Thus, for future comparisons, we have provided the data related to the propagation model and its calibration, the RSS-matrix (i.e., signals from candidate points to user demand), client bandwidth consumption, AP positions, scenarios, and all other necessary information.

7 Computational results

This section presents the results corresponding to Steps 3, 4, and 5 of the proposed approach for two WLAN design situations. Output of steps 1 and 2 are not explicitly presented because they are obtained in a straightforward fashion. Moreover, they are contained in the results of the last three steps.

7.1 Step 3 – WLAN NSGA-II

Four different approaches for network planning were used as benchmarks to validate the solutions generated by the WLAN NSGA-II, as follows:

K-means Algorithm::

In [37], the K-means clustering algorithm was used to define reasonable positioning to set APs. It is a feasible approach in open areas because K-means identifies centroids that better group the demand points (i.e., minimizing distance among the points in the group and the respective centroid). However, this approach is not feasible for indoor networks because the Euclidean distance is an inefficient cluster quality indicator in WLANs with obstacles. Hence, the original K-means was slightly modified to consider this limitation. In this version, the Euclidean distance is replaced by RSS, which is estimated considering distance and barriers between the present centroid and each demand point (i.e., user). In each new iteration, the centroid is reset to the average position of this group. The number of centroids (i.e., AP positions) was defined according to each integer value between the minimum and maximum number of APs considered in WLAN NSGA-II. Load-balancing and channel assignment techniques employed in WLAN NSGA-II were also used in K-means for a fair comparison. The idea behind this method is to represent an experienced WLAN designer.

Commercial tool for network planning::

The software used in this test was Ekahau Site Survey version 8.6 [20], one of the most efficient commercial tools for WLAN planning and site surveying according to the specialized Wi-Fi planning communities [2, 3, 15, 28]. It receives as inputs: a map file, service area definition (e.g., walls, obstacles, and coverage zone), an expected consumption profile, as well as equipment specifications (e.g., type, protocol, and antenna gain). As outputs, it provides the quantity and positioning of APs and the assigned channels. Additionally, a heat map and report are generated. This commercial tool was used with an evaluation license kindly provided by the software representative.

MOEA/D-DE::

Multiobjective Evolutionary Algorithm based on Decomposition with Differential Evolution operator (MOEA/D-DE) [35] was also considered. This algorithm decomposes a MOP into a set of scalar optimization subproblems with neighborhood relations and optimizes them simultaneously. The best candidate solutions found for each subproblem are maintained in the population during the evolution process. MOEA/D-DE uses polynomial mutation and DE operators to create new solutions.

GDE3::

The last benchmark approach considered in this work was the third Evolution Step of Generalized Differential Evolution (GDE3) algorithm [32]. It can address MOPs and performs differential mutation and recombination using DE/rand/1/bin configuration. GDE3 is an elitist algorithm that retains feasible and non-dominated solutions in the population during its selection mechanism. The population size is controlled using Pareto dominance and crowding-distance concepts.

The aggregated result of 33 runs of the WLAN NSGA-II algorithm and those from the other approaches are presented in Fig. 2a and b, for Scenarios 1 and 2, respectively. The same load-balancing and channel allocation schemes were used in all approaches to ensure a fair comparison.

Fig. 2
figure 2

Comparative test - GDE3 x MOEA/D-DE x WLAN NSGA-II x K-means x Ekahau software

Full size image

The different solutions associated with K-means represent distinct WLAN projects with different numbers of APs. Seven solutions achieved by K-means for the first scenario varied from 12 to 18 APs. Nine solutions (from ten to 18 APs) were attained in the second scenario. Notably, the three MOEAs strongly outperformed the solutions achieved by K-means: differences in the objective space among the nearest points of K-means and MOEAs were frequently large. Note that the average difference of 3 dB observed between the two methods is extremely significant in terms of network signal quality. Further, some K-means solutions were penalized because they violated the constraints such as coverage or AP capacity.

The Ekahau Site Survey generated different WLAN design solutions employing from 12 to 17 APs. However, they were also outperformed by the three MOEAs because the software could model user concentration during its planning. This resulted in an unacceptable network balance index and infeasible solutions, which were also penalized.

Regarding the three evolutionary algorithms, MOEA-D/DE clearly provided the worst results in both scenarios, whereas the outcome of WLAN NSGA-II and GDE3 algorithms were very similar. Visually, WLAN NSGA-II obtained wider approximation sets along the objective space. Moreover, a direct comparison of hypervolumes was also performed because the visual inspection was not sufficient for final conclusions. In this comparison, WLAN NSGA-II achieved a final hypervolume 1.5% higher than that achieved by GDE3 in the first scenario, and 3.5% in the second scenario.

7.2 Step 4 – channel assignment GA

In this step, Channel Assignment GA was employed to improve channel allocation achieved with the weighted variant of DSATUR. It was executed 33 times for all non-dominated solutions obtained by WLAN NSGA-II at the end of Step 3. Consequently, some dominated solutions could arise. Hence, they were combined into a single set and filtered with regard to dominance. This action led to 12 solutions for Scenario 1 and 13 for Scenario 2. The outcomes for Channel Assignment GA are displayed in Fig. 3a and b, jointly with the percentage of clients who are experiencing interference (dashed green line).

Fig. 3
figure 3

Comparative test - Channel GA x DSATUR

Full size image

Channel Assignment GA improved DSATUR solutions for congested scenarios considerably, indicating that it has a positive effect on the final solutions provided by WLAN NSGA-II. The outcomes are similar in low-congestion scenarios because DSATUR is also efficient for such easier situations.

7.3 Step 5 - decision support based on sensitivity analysis

In both design situations, the solutions achieved at the end of Step 4 were evaluated in 1,000 scenarios for load profile variation and random AP failures. Considering only load profile changes, the 95% confidence intervals of three criteria for Scenarios 1 and 2 are listed in Tables 5 and 6, respectively.

Table 5 Sensitivity analysis 1 – Load profile variation – scenario 1 – WLAN NSGA-II
Full size table
Table 6 Sensitivity analysis 1 – load profile variation – scenario 2
Full size table

Concerning failure analysis, the 95% confidence intervals for area coverage are verified in Tables 7 and 8. The solutions were sorted by their coverage values, considering 1, 2, or 3 AP faults in random areas. Although SINR and load balance are also affected by failures, only coverage is considered in this analysis; it is expected to be a critical temporary condition. These tables provide additional information to support the choice of the most suitable WLAN design. For instance, in the first scenario, Solutions 3, 5, 6, and 8 have low probability to meet coverage requirement in cases of failure of one or more APs. In our opinion, Solution 12, employing 15 APs, is a reasonable choice to be adopted because it represents an acceptable balance between the objectives and reasonable coverage (more than 97%) even for three AP failures.

Table 7 AP failures – Scenario 1 – NSGA-II
Full size table
Table 8 AP failures – scenario 2 – WLAN NSGA-II
Full size table

In the second scenario, Solution 7 appears to be a suitable choice because of its satisfactory compromise among the three criteria. Additionally, the 12-AP solution presents coverage results comparable to the others that employ more access points.

Finally, the GDE3 algorithm was used as a benchmark for robustness evaluation because it obtained superior Pareto-front approximations compared to MOEA/D-DE. The coverage results achieved by this algorithm for one to three AP failures are provided in the Tables 9 and 10, for Scenarios 1 and 2, respectively. Note that WLAN NSGA-II delivered considerably more robust solutions than the ones achieved by GDE3, which reinforces the inferred superiority of the proposed algorithm.

Table 9 AP failures – scenario 1 – GDE3
Full size table
Table 10 AP failures – Scenario 2 – GDE3
Full size table

These solutions and their sensitivity analyzes are the final outcome of the proposed WLAN planning approach. The decision maker is the responsible for the final decision; however the results of the sensitivity analysis can provide valuable insight for the final WLAN design selection.

7.4 Suggested solutions

The suggested solution for Scenario 1 (Solution 12 in Table 5) is shown in Fig. 4. The colors red, green, and blue correspond to channels 1, 6, and 11, respectively. The algorithm distributed the APs among three clusters without overloading any device. This solution employed more APs in the central area (e.g., food court), which led to improved network balance. In the worst case, the coverage of this solution was greater than 99.5%.

Fig. 4
figure 4

Scenario 1 – Solution 9

Full size image

In the second scenario, the suggested solution (displayed in Fig. 5) also met all client demands with acceptable coverage levels. It employed a small number of APs and offered a reasonable balance index, which is remarkable.

Fig. 5
figure 5

Scenario 2 – Solution 1

Full size image

8 Conclusion

Wireless networks have gained relevance in many applications. Thus, WLAN planning for sizable facilities is an attractive topic for research and presents significant scientific challenges. This manuscript proposed a new method to plan 802.11 networks. The scheme is based on a multiobjective genetic algorithm to obtain AP placement and an initial channel mapping, and also a single-objective GA to improve channel allocation. During the WLAN planning process, AP placement and channel assignment are addressed together to estimate interference caused by a given network layout. Finally, heuristic procedures, embedded inside the algorithm, provide knowledge regarding the problem, improving the algorithm efficiency.

The results achieved from two plausible scenarios of a real floor plan confirmed the effectiveness of the proposed WLAN planning approach. They led to a set of solutions with valuable trade-off among network cost, Wi-Fi interference, load balance, and signal strength. The comparisons of four different approaches, including a well-known commercial tool, indicated that our proposal is a suitable WLAN design tool.

The last module of the design method is a sensitivity analysis procedure to evaluate the solution robustness in several different random scenarios, regarding mobility, demand variation, and AP failures. This module was useful to support the choice of a decision maker for the best network layout for each situation. Finally, this work encourages future comparisons among WLAN planning approaches; all datasets and instances used in this research are available in a public repository.