Approximate Optimization for Proportional Fair AP Association in Multi-rate WLANs

摘要

In this study, we investigate the problem of achieving proportional fairness via Access Point (AP) association in multi-rate WLANs. This problem is formulated as a non-linear program with an objective function of maximizing the total user bandwidth utilities in the whole network. It is NP-hard, and therefore effort in this paper is made to seek approximate solutions. We propose a centralized algorithm to derive the user-AP association via relaxation. Such a relaxation may cause a large integrality gap. Therefore a compensation function is introduced to guarantee that our algorithm can achieve at least half of the optimal solution in the worst-case scenario theoretically. Extensive simulation study has been reported to validate and compare the performances of our algorithms with those of the state-of-the-art.