Proportional Fairness in Multi-Rate Wireless LANs

In multi-rate wireless LANs, throughput-based fair
bandwidth allocation can lead to drastically reduced aggregate
throughput. To balance aggregate throughput while serving
users in a fair manner, proportional fair or time-based fair
scheduling has been proposed to apply at each access point (AP).
However, since a realistic deployment of wireless LANs can
consist of a network of APs, this paper considers proportional
fairness in this much wider setting. Our technique is to intelligently
associate users with APs to achieve optimal proportional
fairness in a network of APs. We propose two approximation
algorithms for periodical offline optimization. Our algorithms
are the first approximation algorithms in the literature with
a tight worst-case guarantee for the NP-hard problem. Our
simulation results demonstrate that our algorithms can obtain
an aggregate throughput which can be as much as 2.3 times
more than that of the max-min fair allocation in 802.11b.
While maintaining aggregate throughput, our approximation
algorithms outperform the default user-AP association method
in the 802.11b standard significantly in terms of fairness.