Exact Methods for the Problem of Positioning Access Points in Wi-Fi 6/6E Networks

The Access Point Positioning Problem (APPP) consists of determining the smallest number of access points (APs) and their positions in an indoor environment, in order to satisfy restrictions on signal coverage, traffic capacity, and quality of service. This is an NP-hard problem, traditionally addressed by heuristic and meta-heuristic methods, whose formulations usually abstract operational aspects of current networks and, therefore, have limited applicability to Wi-Fi 6/6E scenarios. This work proposes two models of Mixed Integer Linear Programming for APPP that incorporate characteristics of the Wi-Fi 6/6E standard: the three frequency bands (2.4 GHz, 5 GHz and 6 GHz), the allocation of channels with non-interference restrictions between nearby APs and the redundant connectivity, in which each demand point receives a primary association and at least two backup associations. The first formulation operates with granularity by point: each free point of the discretization grid is simultaneously a candidate to receive an AP and a demand unit to be met, which makes the number of binary variables grow quadratically with the size of the plant. The second formulation adopts an iterative approach based on regions: it starts from a reduced set of representative points, solves the model restricted to this set and verifies the solution obtained against all points in the environment, incorporating into the model the most critical point of each violated region. The process is repeated until there are no violations, which ensures the overall viability of the final solution