On the Complexity of System Throughput Derivation for Static 802.11 Networks

Gene Cheunga
cheung@nii.ac.jp
Jeongkeun Leeb
jklee@hp.com
Sung-Ju Leeb
sjlee@hp.com
Puneet Sharmab
puneet@hpl.hp.com

aNational Institute of Informatics, Tokyo, Japan
bMobile & Media Systems Lab, Hewlett Packard Laboratories, Palo Alto, CA

Abstract

The exploding popularity of 802.11 Wireless Local Area Networks (WLAN) has drawn intense research interest in the optimization of WLAN performance through channel assignment to access points (AP), AP-client association control, and transmission we refer to any combination of the three approaches as WLAN management. No matter what degrees of freedom are enabled in WLAN management for performance optimization in a particular WLAN setting, a fundamental question is the corresponding maximum achievable system throughput. We show that for a particular network setting, the derivation of the system throughput (where system throughput is aggregate throughput of all clients or maxmin throughput), for any combination of channel assignment, association control and transmission scheduling, is NP-hard and inapproximable to a constant factor in polynomial time.

PDF (80 KB)