Access point assignment algorithms in WLANs based on throughput objectives

Abstract

In this article we present branch-and-bound algorithms for the access point assignment problem in WLANs, when the objective function is based on the throughput of stations in the network. We consider: a) maximizing the aggregate throughput, b) achieving lexicographically max-min fair throughputs, c) achieving proportionally fair throughputs. The performance of all branch-and-bound algorithms is examined for various degrees of approximation. Thus we show trade-offs between the increased cost of exploration and improvement in the objective value. We further compare their performance to that of greedy algorithms, embedded as a depth-first-search in the branch-and-bound methods. An omnipresent result is the near-optimal performance of the greedy algorithms, which is particularly important when considering their practical application. In all cases, the performance of the algorithms improves as the distribution of wireless stations becomes more concentrated in areas of the network, as in hotspot topologies.