On the Complexity of System Throughput Derivation for Static 802.11 Networks

Download Now Date Added: Oct 2010
Format: PDF

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 scheduling - the authors 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. They show that for a particular network setting, the derivation of the system throughput (where system throughput is aggregate throughput of all clients or max-min throughput), for any combination of channel assignment, association control and transmission scheduling, is NP-hard and hard to approximate in polynomial time.