Keywords

1 Introduction

In the last years, mobile users are increasingly demanding new multimedia services (i.e. high quality video, online multimedia applications, augmented/virtual reality, etc.) that have high bandwidth demands and strict Quality of Service (QoS) requirements. To cope with this demand, network densification through the deployment of small cells operating cellular technologies (e.g. 4G/5G), complemented with Wi-Fi hotspots, which benefit from the unlicensed use of the spectrum, becomes a relevant solution. Indeed, the popularity of Wi-Fi technology among mobile users makes it a competitive option for serving multimedia demands. The amount of traffic of IEEE 802.11 (i.e. Wi-Fi) has suffered a high increase in the last years. It is expected that by 2021, 63% of the global cellular data traffic will be offloaded to Wi-Fi or small cell networks [1]. Globally, there will be nearly 549 million public Wi-Fi hotspots by 2022, up from 124 million in 2017, a fourfold increase. Such a high increase in the amount of traffic volume and the number of Wi-Fi Access Points (AP)/Small Cells makes much more complex the planning, configuration, optimization and management tasks of these networks. For this reason, the automation of these processes is of paramount importance. Legacy systems such as 2G/3G/4G already started the path towards a higher degree of automation through the introduction of Self-Organizing Network (SON) functionalities [2], namely self-planning, self-optimization and self-healing. However, the lessons learnt from cellular SON cannot be directly applied to Wi-Fi systems. Several works such as [3, 4] identify challenges and use cases to introduce SON paradigms in Wi-Fi networks. Concerning self-planning aspects in Wi-Fi/Small Cells networks, most of the works found in the literature focus on the determination of the most adequate AP location and the frequency channel allocation and AP transmitted power. As an example, [5] presents a framework for automated cell-planning in multi-tenant Small Cells networks that considers actions such as adding/removing channels and Small Cells. Similarly, [6] presents a theoretical model to determine the most adequate AP location by an accurate characterization of impact of the environment (walls, doors, etc.) on the signal propagation. Other works, such as [7], deal with the determination of the most appropriate locations of Wi-Fi extenders.

On the other side, it is envisaged that the efficiency of automated network management processes can be substantially enhanced through the exploitation of powerful data analytics technologies able to process the large amount of data that can be collected from Wi-Fi networks by powerful monitoring systems. In this respect, (big) data monitoring and analytics combined with SON technologies will become fundamental in order to enable full scale automated network deployment and optimization [8]. The monitoring system provides the ability to collect information about the network resources and performance of the services while the analytics system allows extracted knowledge of the collected data in order to support different decision making processes over the network. As an example, [9] presents a framework for data monitoring and analytics for the optimization of Cloud Enabled Small Cells in the context of the 5G ESSENCE project. The data collected by the monitoring system can be valuable for the extraction of knowledge related to user habits, user mobility patterns, spatio/temporal user resource demands, etc. Some examples are presented in [10] that evaluates user mobility models in a University campus, in [11] that makes use of Wi-Fi measurements to analyze mobility patterns in a Hospital or in [12] that assesses the spatio/temporal traffic correlation of Wi-Fi traffic data measurements and presents a supervised learning approach to classify the different campus spaces.

Within this context, this paper presents a new self-planning methodology to determine adequate relocations of APs to improve the provided coverage/quality at those regions of the network with low signal quality and high traffic demands. The methodology makes use of a monitoring system that collects historical network measurements and an analytics system that extracts valuable knowledge from the collected data. This knowledge feeds the AP relocation strategy that is based on a genetic algorithm. The performance of the proposed relocation actions are validated in a real Wi-Fi network. Although the AP relocation methodology considered in this paper focuses on a Wi-Fi network, it could be adapted as well to other contexts, for example exploiting the monitoring and analytics framework for small cell networks defined by the 5G ESSENCE project in [9].

The remaining of the paper is organized as follows. Section 2 presents the different steps of the proposed self-planning methodology, while the details of the AP relocation algorithm are presented in Sect. 3. The performance of the proposed approach is empirically evaluated in Sect. 4, while Sect. 5 summarizes the conclusions.

2 Proposed Self-planning Methodology

The proposed self-planning methodology assumes a Wi-Fi network with monitoring capabilities enabling the collection of a number of measurements reported by the users when connected to the different APs. The collected data is processed by a data analytics module to generate actionable insights to be used by the self-planning process. As a result, the self-planning process will be able to detect those situations in which the network performance is not satisfactory thus requiring relocation of one or several APs to other positions. The network is represented as a group of K Access Points located at specific geographical locations (xAP,k, yAP,k). The complete scenario is represented with a set of pixels R, each one associated to a geographical location. According to Fig. 1, the Network Monitoring module collects and stores user measurements during a large period of time Tmeas (i.e. weeks or even months). Each measurement is associated to a particular location s (with s = 1,…,S) with coordinates (xs, ys), i.e. one of the pixels of the scenario, so that S ⊆ R is the set of locations in the scenario with associated measurements. The location information can be obtained by means of different positioning methodologies which are out of the scope of this work, such as Time of Arrival [13] or fingerprint-based approaches [14]. With these inputs, the Data Analytics module generates the following metrics for each location:

Fig. 1.
figure 1

Self-optimisation methodology.

Full size image
  1. 1.

    List of APs where the user was connected to as best server at the s-th location.

  2. 2.

    Average Received Signal Strength Indicator (RSSIs) from the best AP at the s-th location.

  3. 3.

    Average Signal to Noise Ratio (SNRs) at the s-th location.

  4. 4.

    Normalized traffic volume (Vs) defined as the percentage of traffic trans-mitted/received at the s-th location with respect to the total amount of traffic volume transmitted/received in all the scenario in the period Tmeas.

  5. 5.

    The activity factor (Ts) defined as the amount of time in which a user at the s-th location is connected to the network with respect to the measurement period Tmeas.

These historical measurements are very valuable for the self-planning process in order to decide adequate actions of AP relocation. For example, AP relocations may decide to enhance the performance in certain regions with high traffic demands that experience poor SNR or bit rate by moving APs from regions with lower traffic demands (e.g. stairs and corridors of the building where users do not stay connected too much time and do not transmit large traffic volumes).

The Data Analytics module also identifies the regions with relatively high traffic demands by selecting the set U ⊆ S where the normalized traffic volume Vs and activity factor Ts are higher than some specific thresholds Th_v and Th_t, respectively. Then, with the set of samples U, a filtering process is carried out to determine the set of samples W ⊆ U in which the provided coverage and quality are below some specific thresholds Th_RSSI and Th_SNR, respectively. Therefore, the set W represents the most relevant locations of the network where users transmit a high amount of traffic and the network coverage/quality requirements are not guaranteed. The set W is used to trigger the AP relocation process. Specifically, if the set W is not empty (i.e. there are some relevant locations with poor coverage/quality), the AP relocation algorithm described in Sect. 3 is triggered. Otherwise, if the set W is empty, (i.e. there are no samples with poor coverage/quality) no AP relocation is done and a new period of time Tmeas starts.

An adequate setting of thresholds Th_v and Th_t is prime important in order to adequately determine the relevant sample locations considered for optimization. A too low value for these thresholds Th_v and Th_t may cause the appearance of false alarms (i.e. wrong activations of the AP relocation algorithm) since the existence of non-relevant locations (i.e. low traffic volume and low activity) with bad RSSI and SNR will unnecessarily activate the AP Relocation algorithm. On the contrary, a too high value in these thresholds Th_v and Th_t may cause that the AP Relocation algorithm may not be activated when needed. Note also that, in case of activation of the AP Relocation algorithm, high values of Th_v and Th_t may cause the methodology to miss relevant sample locations (with relatively high traffic volume and activity), which will lead to a sub-optimal AP relocation. As for the thresholds Th_RSSI and Th_SNR, they must be selected in accordance with the RSSI and SNR values that ensure a certain user performance (e.g. a minimum required user bit rate).

By observing the set of measurements W, the AP Relocation algorithm will determine a group of M Access Points (M ≤ K) considered as candidates to be relocated. These M APs are selected as the best serving APs for the samples of the set W. Then, the objective of the AP Relocation algorithm is to move one or several of these APs closer to the locations with high traffic demands (i.e. set of samples U) but, at the same time, maintaining enough coverage at all the R pixels of the scenario. Since the APs are usually connected to the wired network and hanged on the walls, the selection of potential AP locations depends on how easily they can be placed. In this respect, an adequate filtering of unfeasible locations will determine the subset RC ⊆ R that includes only the feasible locations where the APs can be placed. This filtering will reduce the computational complexity of the solution search, which consists in running a metaheuristic algorithm that iteratively proposes and evaluates different candidate solutions until a termination condition is fulfilled.

Different metaheuristic algorithms can be considered (e.g. genetic algorithm [15], simulated annealing [16], etc.). This paper makes use of a genetic algorithm approach which is described in Sect. 3. If the AP Relocation algorithm provides a feasible solution, then, the corresponding AP(s) are relocated to the identified position(s).

3 AP Relocation Algorithm

The AP Relocation Algorithm makes use of a genetic algorithm optimization that consists on iteratively proposing possible candidate solutions (individuals), each one consisting in a combination of AP locations, and evaluate the performance of each individual according to a cost function. The best individuals in an iteration (generation) are combined to obtain new individuals that are again evaluated in the subsequent iteration. This process is repeated during multiple generations G. Each individual is represented by a combination of the geographical coordinates of all the K APs in the network. During the execution of the genetic algorithm, only the M APs (M ≤ K) that are the best serving APs for the samples of the set W are candidates to be relocated, while the rest of APs will remain at the same position. To following steps summarize the operation of the genetic algorithm for relocating the M APs:

  1. (1)

    Generate a population of N individuals: Each n-th individual (n = 1,…,N) is represented by a vector vn with the geographical coordinates of the K APs vn = {xAP,1, yAP,1,…, xAP,k, yAP,k ,…, xAP,K, yAP,K}. Each element of the vector vn is called a gene. For each individual, the coordinates of the M candidate APs to be relocated are determined randomly with uniform distribution among the subset of feasible locations RC, while the coordinates of the rest (K-M) APs are fixed at their current locations in the real network.

  2. (2)

    Execute the following sub-steps for each n-th individual:

    1. 2.1.

      Determine the path loss Lu between each sample u ∈ U and its best AP, i.e. the AP with the lowest path loss between the position of sample u and the positions of the APs in the n-th individual according to a predefined propagation model.

    2. 2.2.

      The cost of the n-th individual Cn is calculated as the weighted average of the propagation loss Lu from each u-th sample to its best AP as follows:

      $$ C_{n} = \frac{1}{U}\mathop \sum \nolimits_{u = 1}^{U} w_{u} \cdot L_{u} $$
      (1)

      where the weights wu are defined to give more relevance to the regions with high traffic volume and low SNR. For this reason, the weights wu are defined as:

      $$ w_{u} = \frac{{\alpha_{u} \cdot\beta_{u} }}{{\mathop \sum \nolimits_{{u^{\prime} = 1}}^{U} (\alpha_{{u^{\prime}}} \cdot\beta_{{u^{\prime}}} )}} $$
      (2)

      where:

      $$ \alpha_{u} = \frac{{V_{u} }}{{\mathop \sum \nolimits_{{u^{\prime} = 1}}^{U} V_{{u^{\prime}}} }} $$
      (3)
      $$ \beta_{u} = \frac{{{1 \mathord{\left/ {\vphantom {1 {SNR_{u} }}} \right. \kern-0pt} {SNR_{u} }}}}{{\mathop \sum \nolimits_{{u^{\prime} = 1}}^{U} {1 \mathord{\left/ {\vphantom {1 {SNR_{{u^{\prime}}} }}} \right. \kern-0pt} {SNR_{{u^{\prime}}} }}}} $$
      (4)

      Vu denotes the normalized traffic volume demanded at the u-th sample and SNRu is the Signal to Noise Ratio of sample u-th. αu and βu are normalized parameters so that 0 ≤ wu ≤ 1 as shown in (3) and (4).

      According to Eq. (1), an individual with a lower cost Cn corresponds to a better network layout since it relocates the different APs so that lower values of path loss are observed, especially for samples with high traffic volume or low SNR.

    3. 2.3.

      Two feasibility conditions are checked. The first condition checks whether the individual guarantees the overall network coverage or not. Then, an individual is not feasible if there is any geographical location in the scenario (i.e. a pixel of the set R) with RSSI lower than RSSIcov. The second feasibility condition checks that the proposed individual guarantees that the interference generated from an AP to a neighbor AP that is using the same channel is lower than a threshold Th_RSSIneigh.

  3. (3)

    Selection: This step determines which feasible individuals are selected for the generation of new individuals to be evaluated in the subsequent generation. The cost of each individual Cn is used for the selection process by considering a roulette wheel [16] so that the probability of selecting the n-th individual for recombination is:

    $$ Prob_{n} = \frac{{\frac{1}{{C_{n} }}}}{{\mathop \sum \nolimits_{i = 1}^{N} \frac{1}{{C_{i} }}}} $$
    (5)

    According to this, individuals with lower cost have higher probability to be selected for recombination. Individuals that are not feasible according to the feasibility conditions in step 2.3, are not considered in this selection process.

  4. (4)

    Recombination: This process combines the different genes (i.e. elements of the vectors vn) of the two individuals selected in the previous step (called parents) to generate two new individuals (called children). The rationality of this process is to search for new solutions similar to the best individuals of the previous generation by combining their genes. The recombination process considered here is the so-called “1-point crossover” [16]. Considering the genes of the two parents, a crossover point is defined randomly and all the genes beyond this crossover point are swapped between both parents to obtain the children.

  5. (5)

    Mutation: This operator makes small random changes in the genes of the two individuals obtained after recombination. The probability of selecting a gene for mutation is 1/Ngenes where Ngenes = 2M corresponds to the two coordinates of all the M AP that can be relocated in the individual. As a result, very few genes of an individual are usually modified by this process. When a gene is selected for mutation, the new value, which represents a new AP location, is either an increase or decrease (with equal probability) in one pixel, allowing only changes to locations of the set RC.

As a result of the selection, recombination and mutation process, a total of two new individuals will be obtained. This process is repeated N/2 times until getting the N individuals for the new generation. With the newly generated N individuals, the algorithm executes again the evaluation procedure and computes the associated costs. The process is repeated iteratively until reaching a maximum number of generations G. Then, the final solution of the algorithm is the individual with minimum cost that has been found throughout all the generations.

4 Performance Evaluation

The proposed methodology has been evaluated empirically in a scenario consisting of a building of 40 m × 20 m covered by K = 3 APs represented in Fig. 2. A grid with pixel resolution of 1 m is considered. The measurements are made and reported by 241 different users during a period Tmeas of one month. These reported measurements are collected by the Cisco Prime Infrastructure tool [17]. The locations of the set of U = 12 samples in which the demand of traffic is relatively high (i.e. Normalized Traffic Volume higher than Th_v = 1% and Activity Factor higher than Th_t = 1%) are represented in Fig. 2. Table 1 presents the average SNRu, the normalized traffic volume Vu, the normalized parameters αu and βu and the weight wu for the identified U = 12 samples. By filtering the U samples, the set W contains one sample with RSSI and SNR below Th_RSSI = −81 dBm and Th_SNR = 15 dB, respectively. This sample corresponds to u12 located at coordinates [39, 2] as shown in Fig. 2. Although it is just a single sample, it represents a substantial amount of traffic (i.e. 4.83% of normalized traffic volume) and exhibits a very low SNR compared to the rest of samples. At this location, an average bit rate of 14 Mb/s has been observed while the bit rate at other locations inside the building usually varies between 30 and 50 Mb/s. At this location, the users can connect to two different APs, namely AP1 and AP3. Then, the AP relocation algorithm will evaluate the relocation of these M = 2 APs to improve the performance at the U = 12 locations, while maintaining the network coverage (i.e. RSSI of all the R pixels in the scenario is higher than RSSIcov = −75 dBm) and keeping the interference between neighbor APs using the same channel below RSSIneigh = −70 dBm.

Fig. 2.
figure 2

Considered scenario with the set of U = 12 samples.

Full size image
Table 1. Observed metrics and obtained weight for each sample of the set U = 12.
Full size table

The genetic algorithm considers a population of N = 50 individuals, each one represented by the location coordinates of the K = 3 APs. A total of G = 5000 generations have been considered. The propagation model is taken from the ITU-R [18] so that the path loss between the transmitter and the receiver is calculated as:

$$ L\left( {dB} \right) = 20log_{10} \left( f \right) + N_{o} log_{10} \left( d \right) + P_{f} \left( n \right) - 28 + N_{d} L_{o} $$
(6)

where f = 2.4 GHz is the carrier frequency, No = 30 for office areas, Pf(n) is the floor attenuation factor considered here 0 dB since all the APs and the users are located at the same floor, Nd is the number of obstacles (i.e. walls and doors) between the transmitter and the receiver and Lo = 2 dB is the path loss associated to each obstacle. After executing the AP relocation algorithm, the best solution found is illustrated in Fig. 3. It consists in moving AP3 to the location [32, 2] while keeping AP1 in its current location. This solution has a cost of 75.58 which is considerably better than the cost of 93.6 that was obtained before the execution of the AP relocation algorithm.

Fig. 3.
figure 3

Solution proposed by the genetic algorithm.

Full size image

In order to empirically validate the solution proposed by the genetic AP relocation algorithm, several RSSI measurements have been done at 47 different locations of the building before and after the AP relocation (i.e. with AP3 located at coordinates [20, 4] and [32, 2], respectively). For each location, the RSSI averaged in a period of 2 min is obtained. Figures 4 and 5 present the average RSSI measurements obtained before and after the AP relocation, respectively. After the AP3 relocation, an average RSSI = −67 dBm has been measured at u12 (i.e. coordinates [39, 2]) which is considerably better than an average RSSI = −82 dBm at the same location before the AP3 relocation. Moreover, the AP relocation guarantees an RSSI higher than the threshold RSSIcov = −75 dBm for all the locations of the scenario. Some other validations have been done by moving AP3 to different locations and collecting the new values of the average RSSI measurements. For example, moving AP3 closer to the location of sample u12 (e.g. to coordinates [37, 2]) is not a feasible solution since it causes some coverage problems at region around [17, 8]. Similarly, relocating AP3 to coordinates [28, 2] (i.e. not so close to u12) guarantees the coverage RSSI requirements at all the locations of the building but, an average RSSI = −73 dBm is measured at u12, which is not as good as the average RSSI = −67 dBm obtained when implementing the best solution proposed by the genetic AP relocation algorithm.

Fig. 4.
figure 4

RSSI measurements obtained before the AP Relocation i.e. AP3 at [20, 4].

Full size image
Fig. 5.
figure 5

RSSI measurements obtained after the AP Relocation i.e. AP3 at [32, 2].

Full size image

5 Conclusions

This paper has presented a new self-planning methodology to determine adequate relocations of APs in a Wi-Fi network based on information about signal quality and user traffic demands extracted from network measurements collected and processed by a monitoring and analytics system. From these measurements, the proposed methodology identifies regions with poor RSSI/SNR and high traffic demand, determines candidate APs to be relocated and applies a genetic algorithm optimization to recommend new locations for these APs. The paper has presented an empirical validation of the algorithm performance, making use of measurements collected from a real Wi-Fi network and comparing the obtained RSSI at different locations before and after the execution of the AP relocation.