徐學(xué)斌，呼翔宇，王新宇，黃 蕾，李 玄

（1.中國科學(xué)院 上海微系統(tǒng)與信息技術(shù)研究所，上海　200050；2.國網(wǎng)天津靜海供電有限公司 天津　301600；3.上海無線通信研究中心 上?！?01210；4.上海大學(xué) 上海　200072）

802.11網(wǎng)絡(luò)中基于鄰近點算法的比例公平優(yōu)化

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

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

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

通信與信息系統(tǒng)；性能優(yōu)化；鄰近點算法；比例公平

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

1　性能異常與解決方案

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

為了解決這一問題，目前已有相關(guān)文獻(xiàn)提出了各種各樣的辦法，文獻(xiàn)［4］提出了基于時間的比例公平方式來在多速率的無線網(wǎng)絡(luò)中提高網(wǎng)絡(luò)性能，文獻(xiàn)［5］設(shè)計了一個新的MAC協(xié)議，其中以高速率傳輸?shù)挠脩敉ㄟ^轉(zhuǎn)發(fā)低速率的用戶的流量來幫助他們進(jìn)行傳輸從而提高整體網(wǎng)絡(luò)的性能。文獻(xiàn)［6-7］通過將比例公平效用函數(shù)運用在確定性與時變信道上，從而提高整個網(wǎng)絡(luò)信道利用率。

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

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

圖1　Wi-Fi網(wǎng)絡(luò)性能異常

2　系統(tǒng)模型與問題描述

2.1系統(tǒng)模型

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

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

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

圖2　四種不同的STA-AP的關(guān)聯(lián)圖

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

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

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

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

2.2問題描述

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

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

3　優(yōu)化接入概率：PPA

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

可以發(fā)現(xiàn)，公式（9）可以分解成對每個AP進(jìn)行優(yōu)化。對于每個AP n，考慮以下的凸規(guī)劃。

為了在AP和它所關(guān)聯(lián)STA之間進(jìn)行一個Map-Reduce運算，我們將（11）改為一個具有相同限制條件同樣的函數(shù)：

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

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

執(zhí)行：For k=0，1…，AP與其所關(guān)聯(lián)的STA重復(fù)以下步驟。

STA側(cè)：每一個STA u∈un（f）根據(jù)以下公式保持和更新

之后，AP n把更新后的xk+1n的值通報給它關(guān)聯(lián)下的STA。

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

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

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

4　仿真結(jié)果

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

表1　參數(shù)配置

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

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

圖3　AP側(cè)PPA算法收斂圖

圖4　STA側(cè)PPA算法收斂圖

圖5　用戶的吞吐量

5　結(jié)束語

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

［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

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

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