802.11网络中基于邻近点算法的比例公平优化

徐学斌，呼翔宇，王新宇，黄 蕾，李 玄

（1.中国科学院 上海微系统与信息技术研究所，上海　200050；2.国网天津静海供电有限公司 天津　301600；3.上海无线通信研究中心 上海　201210；4.上海大学 上海　200072）

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　性能异常与解决方案

什么是性能异常现象呢？如图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资源管理。