Title :
On the Complexity of System Throughput Derivation for Static 802.11 Networks
Author :
Cheung, Gene ; Lee, Jeongkeun ; Lee, Sung-Ju ; Sharma, Puneet
Author_Institution :
Nat. Inst. of Inf., Tokyo, Japan
fDate :
10/1/2010 12:00:00 AM
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 scheduling-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 max-min throughput), for any combination of channel assignment, association control and transmission scheduling, is NP-hard and hard to approximate in polynomial time.
Keywords :
channel allocation; computational complexity; optimisation; scheduling; wireless LAN; AP-client association control; WLAN management; access points; channel assignment; polynomial time; static 802.11 networks; system throughput derivation; transmission scheduling; wireless local area networks; Aggregates; IEEE 802.11 Standards; Interference; Optimization; Schedules; Throughput; Wireless LAN; NP-hardness; WLAN; optimization;
Journal_Title :
Communications Letters, IEEE
DOI :
10.1109/LCOMM.2010.081910.100835