802.11網絡中基于鄰近點算法的比例公平優化

徐學斌，呼翔宇，王新宇，黃 蕾，李 玄

（1.中國科學院 上海微系統與信息技術研究所，上?！?00050；2.國網天津靜海供電有限公司 天津　301600；3.上海無線通信研究中心 上?！?01210；4.上海大學 上?！?00072）

802.11網絡中基于鄰近點算法的比例公平優化

徐學斌1，呼翔宇2，王新宇3，黃 蕾3，李 玄4

（1.中國科學院 上海微系統與信息技術研究所，上海200050；2.國網天津靜海供電有限公司 天津301600；3.上海無線通信研究中心 上海201210；4.上海大學 上海200072）

802.11Wi-Fi網絡中，接入點（AP）的介質接入控制（MAC）協議分配給它的競爭用戶（STA）相等的傳輸機會而不考慮的用戶的鏈路質量的差異，這就會導致有著不同鏈路質量的競爭節點獲得相等的吞吐量（基于吞吐量的公平性），從而降低網絡整體的性能。為了克服這一性能異常問題，基于比例公平的優化由于其吞吐量增強能力已經引起廣大的關注。在本文中，提出了一種基于鄰近點算法的比例公平優化方法，每個競爭節點根據其鏈路質量的差異使用不同的接入概率來訪問接入點。數值結果驗證了我們的理論分析，Wi-Fi網絡的吞吐量可以通過接入概率的優化得到顯著改善。

通信與信息系統；性能優化；鄰近點算法；比例公平

在用戶數據流量的急劇增長的驅動下，為了滿足用戶各種應用和服務需求的爆炸式增長，到2020年，全球范圍內的Wi-Fi接入點（AP）的部署將增加1330萬［1］。盡管Wi-Fi網絡可通過提供無縫覆蓋與近距離可靠的數據服務來使用戶獲得良好的體驗，但是Wi-Fi網絡本身存在的性能異常［2］現象依然對用戶體驗和對進一步提升網絡整體吞吐量有很大的影響。

1　性能異常與解決方案

什么是性能異?，F象呢？如圖1所示，假設802.11ac的無線網絡中，存在兩個用戶A和B，兩者都以65 Mb/s的速率給遠端的AP傳送數據。隨著時間的推移，用戶 A逐漸往外移動，此時為了保證信號質量，傳輸速率用戶A的傳輸速率從65 Mb/s降為13 Mb/s。此時，用戶A和AP之間的吞吐量將大大下降，這是很正常的現象，但我們同時發現用戶B和AP之間的吞吐量也因為受到用戶A的影響而產生同樣程度的下降，這種現象稱為性能異常。究其原因，就是在IEEE 802.11規范中，AP的介質接入控制（MAC）協議分配給它自己的競爭者相等的傳輸機會而不考慮的用戶的鏈路質量的差異［3］，從而導致系統的整體性能的降低。

為了解決這一問題，目前已有相關文獻提出了各種各樣的辦法，文獻［4］提出了基于時間的比例公平方式來在多速率的無線網絡中提高網絡性能，文獻［5］設計了一個新的MAC協議，其中以高速率傳輸的用戶通過轉發低速率的用戶的流量來幫助他們進行傳輸從而提高整體網絡的性能。文獻［6-7］通過將比例公平效用函數運用在確定性與時變信道上，從而提高整個網絡信道利用率。

比例公平優化由于其吞吐量增強能力一直被廣泛關注，因此，一個有效的比例公平吞吐量的分配方式可以極大地提高無線網絡的性能［8］。802.11 Wi-Fi網絡中的比例公平分配問題已經在最近的文獻［8-11］中得到了很廣泛的研究與分析。這些工作的關鍵貢獻是，他們提出了一個可行的，精確的802.11協議的建模。特別是Patras和Garcia-Saavedra引進了一個802.11用戶吞吐量的嚴格分析模型，這個模型可以構建一個封閉的凸問題。

在本文中，我們首先在Patras和Garcia-Saavedra研究的基礎上對802.11協議進行了精確建模，然后提出了一種新的分布式算法來優化用戶競爭AP的接入概率，從而來解決性能異常問題，提高系統的整體性能。具體地講，通過對模型執行相關的對數轉變，這樣基于吞吐量的比例公平分配方式可以轉化為一個對數-求和-指數問題，同時這也是一個連續的凸問題。然后，我們使用“Map-Reduce”［12］的方法解決這個具有挑戰性的比例公平的凸問題。通過采用鄰近點算法（PPA）［13］，接入點（AP）和用戶（STA）通過交換信息獲得最佳接入概率。

圖1　Wi-Fi網絡性能異常

2　系統模型與問題描述

2.1系統模型

根據IEEE 802.11的規定，假設有一個地理區域，N個AP隨機部署在這片區域中，這樣就形成了一個AP集合N= ｛1，2，..，NA｝。同樣在區域中有U個STA，STA的集合可以記為U=｛1，2，..，UA｝。每一個STAu∈U一次只能接入一個AP，所有可行的STA-AP關聯被記為F，每種f∈F代表一種特定的STA-AP的關聯，如圖2所示。在配置f下，AP n下的STA的集合可以記為Un（f），它的對應基數是

根據J.Leith’s最新的理論分析［9，14］，在一個隨機選中的時隙中，STA u∈Un（f）競爭到AP n媒介的概率為τu，n。傳統上來講，我們可以通過調整競爭窗Wu［9］的大小來得到接入概率τu，n的值，也就是

其中Wu=CWmin，u=CWmax，u，qu，n是當 STA u競爭到了信道之后包的傳輸概率，這樣我們就可以得到STA u的吞吐量：

圖2　四種不同的STA-AP的關聯圖

ps，u，n是STA u成功傳輸的概率，Lu，n是相關的數據包負載，Pe，n表示AP n在一個時隙為空的概率，Ps，n表示AP n一次成功傳輸的概率，Pl，n則表示AP n失敗傳輸的概率。最后，上述變量可以明確表示如下：

值得注意的是，pf，u，n是由于噪聲，隱藏終端等誤差造成的傳輸失敗的概率，該概率可以通過包的配對技術［15］進行預估。此外，Te，n是一個物理層常數（例如在802.11a/g系統中為9 μs）。平均成功傳輸周期Ts，n與失敗傳輸周期Tl，n明確表示如下：

相關的pl，u，n，Ts，u，n，Tf，u，n也可以從下面的公式得到：

可以發現pl，u，n是在AP n的區域范圍內，有著最大索引值u的STA傳輸失敗的概率。TPLCP，H和TACK分別表示物理層會聚協議的前導序列和標頭，MAC的開銷，以及確認幀（ACK）的周期時間。短幀間間隔 （SIFS）和DCF幀間間隔（DIFS）是物理層常數 （例如，802.11a/g系統中分別為16 μs 和34 μs）。

2.2問題描述

在固定配置f下，我們在Wi-Fi網絡中對公式（6）考慮以下的比例公平效用原則：

這樣公式（9）便變換成一個凸函數，如何優化接入概率xn提高系統的性能便成為了一個“凸”問題，在下一部分，我們運用凸優化的手段，使用PPA技術去解決這個問題。

3　優化接入概率：PPA

在這一部分，我們使用PPA算法并行計算調整每一個AP n的xn，值得注意的是，PPA算法是一個加速的ADMM（交替方向乘子法），通過在每次更新過程中使用額外的預測步驟，他能夠達到O（1/k）（k是迭代次數）的收斂速率。

可以發現，公式（9）可以分解成對每個AP進行優化。對于每個AP n，考慮以下的凸規劃。

為了在AP和它所關聯STA之間進行一個Map-Reduce運算，我們將（11）改為一個具有相同限制條件同樣的函數：

xnu為AP n下所有STA u關于xn的副本。然后，我們引入與公平性相關的拉格朗日乘子，對公式（11）運用PPA算法。

初始化：每個AP設置相同的初始值ρ＞0，γ∈（0，2）。AP n初始化它自身的

執行：For k=0，1…，AP與其所關聯的STA重復以下步驟。

STA側：每一個STA u∈un（f）根據以下公式保持和更新

之后，AP n把更新后的xk+1n的值通報給它關聯下的STA。

停止條件：在執行下一次迭代之前，AP n將檢查其關聯下STA是否滿足以下不等式

如果條件成立，AP n終止執行算法，或者更新新的值繼續執行算法。

從以上算法描述中可以看出，計算任務被分配給各個STA，同時每個AP起到收集和傳播信息的作用。

4　仿真結果

這一部分，我們評估所提出PPA算法的性能。具體來說，在一個局部區域，我們假設考慮一個由3個AP構成802.11 Wi-Fi網絡，其中15個STA通過選擇最佳的物理層鏈路速率來訪問他們的AP，即根據文獻［3］，S的每個元素是隨機從矢量［6.5，13，19.5，26，39，52，58.5，85］Mb/s中選擇的，相關系統參數列在表1中，我們假設所有站點總是有數據包在等待傳輸，然后我們展示在固定配置下的PPA算法的性能。

表1　參數配置

1）PPA收斂。如圖3，4所描述，在固定的配置f下，這個快速的“一致”過程在迭代35次左右時完成。圖3中，每個AP能夠獲得最優的比例公平（9），同時關聯下的STA也得到了它們自身優化的接入概率，如圖4（以AP1的STA作為范例）。

2）吞吐量對比。如圖5所示，大多數用戶的吞吐量都有著不同程度的提高。在執行完PPA算法之后，Wi-Fi網絡的吞吐量能達到52.82 Mb/s。相比于初始時的46.92 Mb/s，網絡吞吐量提高了12.57%。具體而言，大多數用戶的吞吐量提高了，一些用戶的吞吐量增加的并不明顯甚至可能下降，但是網絡總體的吞吐量得到了很好的提升。

圖3　AP側PPA算法收斂圖

圖4　STA側PPA算法收斂圖

圖5　用戶的吞吐量

5　結束語

在本文中，我們對802.11 Wi-Fi網絡的比例公平性問題進行了研究。通過采用PPA技術，我們有效地解決了這個“凸”的問題，提高了網絡的性能。此外，我們給出的仿真結果表明我們的算法，在改善吞吐量方面有著顯著效果。今后，我們將評估該算法在多種802.11網絡條件下的實際部署情況。

［1］ABI Research.Global public Wi-Fi hotspots will reach 7.8 million in 2015 and continue to grow at a CAGR of 11.2% through 2020［EB/OL］（2015-03）.https://www.abiresearch. com/press/global-public-wi-fihotspots-will-reach-78-million/.

［2］Heusse M.Rousseau F.Berger-Sabbatel G.et al.Performance anomaly of 802.11b［C］//in Proc.of IEEE INFOCOM，（San Francisco，USA），March-April 2003.

［3］IEEE 802.11Wireless lan medium access control（MAC）and physical layer（PHY）specifications［z］.Revision of IEEE Std 802.11-1999，2007.

［4］Tan G.Guttag J.Time-based fairness improves performance in multi-rate WLANs［C］//Proceedings of the annual conference on USENIX Annual Technical Conference，June 27-July 02，2004，Boston，MA.

［5］Liu P.Tao Z，Panwar S.A cooperative MAC protocol for wireless local area networks［C］//in Proceedings of IEEE International Conference on Communication（ICC），June 2005.

［6］Liew S C，Zhang Y J.Proportional fairness in multi-channel multi-rate wireless networks-Part I:The case of deterministic channels with application to AP association problem in largescale WLAN［J］.IEEE Trans.Wireless Commun.，2008，7 （9）:3446-3456.

［7］Zhang Y J，Liew S C.Proportional fairness in multi-channel multirate wireless networks-Part II:The case of time-varying channels with application to OFDM systems［J］.IEEE Trans. Wireless Commun.，2008，7（9）:3457-3467.

［8］Subramanian V，Leith D.On the rate region of CSMA/CA wlans［J］.IEEE Transactions on Information Theory，2013，59 （6）:3932-3938.

［9］Patras P，Garcia-Saavedra A，Malone D，et al.Rigorous and practical proportional-fair allocation for multi-rate Wi-Fi，［EB10L］（2015-03）http://arxiv.org/abs/1411.6685.

［10］Leith D，Subramanian V，Duffy K，Log-convexity of rate region in 802.11e wlans［J］.IEEE Communications Letters，2010，14 （1）:57-59.

［11］Le Y，Ma L，Cheng W，et al.A Time Fairness Based MAC Algorithm for Throughput Maximization in 802.11 Networks［J］. IEEE Transactions on Computers，2015，64（1）:19-31.

［12］Dean J，Ghemawat S.Map Reduce:simplified data processing on large clusters［J］.Communications of the ACM，2008，51 （1）:107-113.

［13］Cai X，Gu G，He B，et al.A relaxed customized proximal point algorithm for separable convex programming［EB/OL］. （2013-10-07）http://www.optimization-online.org/DB HTML/2011/08/3141.html.

［14］Partov B，Leith D.Utility fair rate allocation in LTE/802.11 networks［EB/OL］.（2015-01）http://arxiv.org/abs/1506.01058.

［15］Giustiniano D，Malone D，Leith D.et al.Papagiannaki，Experimental assessment of 802.11 MAC layer channel estimators［J］.IEEE Communications Letters，2007，11（12）：961-963.

Proportional fairness optimization based on proximal point algorithm in 802.11 network

XU Xue-bin1，HU Xiang-yu2，WANG Xin-yu3，HUANG Lei3，LI Xuan4
（1.Shanghai Institute of Microsystem and Information Technology，Chinese Academy of Sciences，Shanghai 200050，China；2.Jinghai Power Supply Company Limited，State Grid Tianjin Electric Power Company，Tianjin 301600，China；3.Shanghai Research Center For Wireless Communications，Shanghai 201210，China；4.Shanghai University，Shanghai 200072，China）

In the 802.11 Wi-Fi networks，an access point（AP）adopting a medium access control（MAC）protocol assigns equal transmission opportunities to its own contenders without taking differences of users’link qualities，in this way，this leads to equal achieved throughputs（throughput based fairness）among contending nodes with different link qualities，which degrades networks severely.In order to conquer the performance anomaly problem，proportion fairness optimization has drawn great attention for its high throughput enhancement.In this paper，we propose a proportional fairness optimization based on proximal point algorithm，in which each competing nodes use different access probability to access APs by taking differences of users’link qualities.Numerical results verify our theoretical analysis and the Wi-Fi network throughput can be dramatically improved with the optimization among APs.

communication and information system；performance optimization；proximal point algorithm；proportional fairness

TN92

A

1674-6236（2016）14-0001-04

2016-01-12稿件編號：201601078

國家自然科學基金資助項目（61231009）；國家科技重大項目（2014ZX03001024）；上海市科教委項目（15511102602）

徐學斌（1991—），男，江蘇南京人，碩士研究生。研究方向：Wi-Fi資源管理。