在多用戶多輸入多輸出的無線區域網路環境下，達成比例公平分配條件的無線網路基地台連接配對問題

AP Association for Proportional Fairness in MU-MIMO Multi-rate WLANs

陳鈺書(Chen, Yu Shu)

指導教授 ： 蔡明哲

國立清華大學/電機資訊學院/資訊工程學系/碩士(2015年)

摘要

在無線區域網路裡無線網路基地台連接配對問題的演算法設計已經受到許多人的關注，這是因為分配給使用者的頻寬會隨著演算法的不同而有差異。為了要讓每個使用者所被分配到的頻寬能夠符合他的最低需求，在無線網路基地台連接配對問題需要去考慮公平性。已經存在的演算法只有考慮在每個無線網路基地台在某個時間點只能跟一個使用者溝通的環境下，去達到頻寬分配公平性最佳化的狀態。然後現在藉著使用波束成型技術可以讓有多根天線的無線網路基地台能夠同時跟多位使用者傳遞資料。
在這篇論文中，我們探討在多用戶多輸入多輸出的無線區域網路環境下，達成比例公平分配條件的無線網路基地台連接配對問題來使得分配給使用者頻寬的效用函數的和最大化。就我們所知，我們是第一個來探討這個問題的。在這篇論文中，我們會證明這是一個NP-hard 的問題並且提出一個近似演算法使得它的答案會不小於OPT-|U| log(|A|)，在這裡U 是使用者的集合，A 是無線網路基地台的集合。
從模擬的結果可以看出我們所提出的演算法對於分配給使用者頻寬的效用函數的和有良好的表現。

關鍵字

比例公平

並列摘要

Design of AP association algorithms has received considerable attentions in wireless local area networks (WLANs) because the bandwidth allocated to users is decided by the AP association algorithms designed. In order to make the allocated bandwidth of each user satisfy the lower bound of the requirement of each user, AP association needs to be considered about fairness. The existing algorithms concerning the total bandwidth optimization problem under fairness constraints only allow each AP to be able to communicate with at most one user in a time slot. However, today, by the beamforming technique makes it possible that each AP with multiple antennas can
transmit data to multiple users simultaneously.
In this thesis, we study the AP association for proportional fairness, termed AAPFM, to maximize the sum of the utility function of the bandwidth allocated to each user in MU-MIMO WLANs. To the best of our knowledge, we are first to study the AP association problem for proportional fairness in MU-MIMO WLANs. In this thesis, we show the AAPFM problem is NP-hard and propose an approximation algorithm that the solution is greater than OP T − |U | log |A| where U is the set of users and A is the set of APs.
Simulations for evaluations show that the proposed AP association algorithm has good performance in terms of the sum of the utility function of the bandwidth allocated to each user.

參考文獻

[2] Akash Baid, Michael Schapira, Ivan Seskar, Jennifer Rexford, and Dipankar Raychaudhuri. Network cooperation for client-ap association optimization. In Modeling and Optimization in Mobile, Ad Hoc and Wireless Networks (WiOpt), 2012 10th International Symposium on, pages 431{436. IEEE, 2012.

[3] Stephen Boyd and Lieven Vandenberghe. Convex optimization. Cambridge university press, 2004.

[4] Dawei Gong and Yuanyuan Yang. Ap association in 802.11 n wlans with heterogeneous clients. In INFOCOM, 2012 Proceedings IEEE, pages 1440-1448. IEEE, 2012.

[5] Ouldooz Baghban Karimi, Jiangchuan Liu, and Jennifer Rexford. Optimal collaborative access point association in wireless networks. In INFOCOM, 2014 Proceedings IEEE, pages 1141-1149. IEEE, 2014.

[6] Frank Kelly. Charging and rate control for elastic trac. European transactions on Telecommunications, 8(1):33-37, 1997.