WiFi自适应速率算法与无线网络瓶颈探测

Written By BobAnkh, 2021-08-06(Fri), in Category Paper

network, research, wifi, wireless

摘要

本篇文章主要综述了超过40篇WiFi自适应速率算法的核心机制和无线网络(LTE和WiFi)下瓶颈的探测

WiFi Rate Adaptive Algorithm and Wireless Bottleneck Detection

1 基于历史信息的发端决定的自适应速率算法

1.1 基于ACK的统计信息

容易实现,无需修改MAC帧格式,但是对信道状况的变化调整和反应往往不够及时

  1. 未进行丢包区分:这些算法都是通过发送节点统计ACK信息,而且不区分碰撞丢包和信道丢包。但是这里有一个问题,将信道丢包处理为碰撞丢包会调整退避时间导致增加竞争等待时间;将碰撞丢包处理为信道丢包会降低信道速率导致更长的传输时间,使得竞争状况恶化

    • ARF(Auto Rate Fallback)1初速设最低,根据成功失败次数进行速率调控。在连续收到若干ACK信号后,超过设定门限\(N_c\),则尝试用更高速率发送;一旦失败超过门限次数\(N_f\)后,降低速率。这基本上是最早最初的实现,这个方法不能够对信道状况的变化做出及时的反应和调整,对于稳定信道仍会不断探新。
    • AARF2:ARF的升级版,连续成功的门槛改成了\(2N_c\),减少了探索频度,无本质改进。文献3用启发式长短间隔探索来跟踪信道的快慢变化,文献4以延时因子为目标,以较小\(N_c\)​迅速响应信道变化。
    • ONOE5:是一种基于信用度的速率调整算法,初速的设置802.11a/g为24M,802.11b为11M,它依靠丢包率进行调速,对单包丢失与否不敏感,试图找到丢帧率小于50%的最高速率。通过统计每个目的连接的帧传输次数、成功传输次数、重传次数和信用度进行调整。
    • SampleRate6基于最短传输时间调速,初始设为最高速率,连续丢包4次则降低速率,发送过程10包一组,第10个包探测非重传传输时间小于当前平均传输时间的新速率,并在下组中选择传输时间较短的速率。
    • HRC(Hybrid Rate Control)7:通过ACK包的接收信号强度SSI预测信道变化的程度,每个rate对应3个动态调整的SSI阈值:两个对应信道稳定情况下的高端和低端阈值,另一个为信道波动情况下的低端阈值。HRC主要是在信道快变的情况下,尽量采用低速率从而保证可靠传输。
    • RAMAS34:这是一个基于信用的算法,将传输速率调控分为两个组,一个是调制组(modulation),另一个是增强组(enhancement),前者有不同的MCS值,后者由空间串流(spatial stream)、保护间隔GI、信道宽度等组成,根据包传输的成功率和失败率统计信息,由两个组分别进行独立调控,然后将结果结合起来。根据35评测,这个算法可能对于多流情况的适应比较保守,而对于使用MCS的情况过于激进,导致在某些情况下表现差。
    • STRALE30:联合调整PHY速率A-MPDU(Aggregate MAC Protocol Data Unit)长度。在收到一个BlockACk之后,对于上一个A-MPDU传输计算能使其获得最高吞吐的最优A-MPDU长度。下一个A-MPDU长度将由EWMA决定出。两者之间的差将与一个阈值相比较,如果超过阈值,那么会检查是否使用更低一级的MCS将能够取得更高的吞吐。这个方法无法区分出干扰,在802.11n上进行了实现。
    • Minstrel-HT31:依靠信道宽度,保护间隔(Guard Interval)和流的数量来创建速率组。每一组包含8个不同的数据传输速率(对应不同的MCS)。过程分为2部分:(1)采样部分,它会从速率组中随机选择一个可用速率,如果获得了更高的吞吐,则使用这个速率来传输下一个MPDU,否则仍使用之前的速率。此处的吞吐是根据采用了EWMA的FLR(Frame Loss Rate)。在进入非采样部分前,会统计出3个数据速率选择,最佳吞吐、次佳吞吐、最大可能(Most probablity)。(2)非采样部分,MPDU会先用最佳吞吐速率发送直到超过了最大重传次数,然后用次佳传输速率,同样会有可能使用最大可能速率。不过32表明在某些情况下,特别是在一个不衰减(non-fading)信道上,信道质量从坏变好的时候,它并不一定能够提升带宽。
    • Damysus36:这个方法是用于802.11ax上的,利用了Basic Service Set(BSS) Color Scheme。它使用自适应的OBSS/PD(Overlapping Basic Service Set/Preamble-Detection)阈值并联合调整发送功率。每100ms的间隔就会完成一次统计报告,每1s一个循环会记录包的成功和失败率,并与阈值做比较。然后会据此决定是否增减传输速率、OBSS/PD阈值、传输功率。根据37分析,该方法依赖于丢包率阈值,而没有一个单一的最佳的丢包率PLR阈值能够帮助实现最大吞吐。
  2. 进行丢包区分:仍然是通过发送节点的ACK统计信息,但是增加了丢包区分的功能,丢包区分可以是来自接收方的反馈信息,也可以由发送方主动探测

    1. 基于接收方信息反馈:

      • LD-ARF(loss differentiating-ARF)8基于ARF,仍由成功失败次数调速,但增加了丢包区分。若发送节点收到了CTS而无ACK则认为信道丢包,降速;如果没有收到CTS则认为碰撞丢包,不降速。主要是认为控制帧以低的基本速率发送,不易丢包。
      • 文献9利用接收信号强度、位错误率和symbol-level错误机制等信息,提出了一种COLLIE机制,区分两种丢包,通过AP将接收到的错误信号反馈回发送节点,由发送节点计算各种错误衡量参数,根据具体情况分别调整退避时间和传输速率。这种情况需要将错误帧信号反馈,开销大。
      • EasiRA40:通过两种方式测量链路质量,首先计算丢帧率FLR并将其与移动性或其他传感器信息结合;其次它会取得ESS(Environmental Signal Strength)信息来帮助区分是什么原因导致了丢包。当一个包因为比特错误导致没法接收时,首段会回送一个NAK来告知发端碰撞丢包。如果发端没有收到ACK和NAK则减速。这个方法结合了随机和决定性的速率自适应机制,利用了外部信息。但是外部信息不一定所有设备都可用。
    2. 基于发送方探测:

      • CARA(Collision-Aware Rate Adaptation)10初速设为最小,依据成功失败次数调速,利用RTS/CTS探测区分两种丢包。当数据发送失败达到设定门槛值时,CARA协议启动RTS探测,以确定是否需要降低数据传输速率。例如启动probing之后,收到CTS回应,说明信道已经预留,但再次传输失败,则认为是信道质量问题。这个方法固然可以一定程度上区分丢包,但是若有隐藏终端时将导致RTS频繁开关,发送节点可能出现大量碰撞丢包。
      • RRAA(Robust Rate Adaptation Algorithm)11初速设为最大,依据丢包率调速,提出改进的探测方法A-RTS,通过控制RTS窗口值和RTS计数值,改善因为隐藏终端导致的碰撞丢包。
      • PBRA12:在以上的基础上,增加了估算碰撞的概率决定是否使用RTS/CTS探测。
      • OTLR13 14:在利用速率\(r\)发生丢包后,将数据帧分为长短帧,利用短帧试探速率\(r\)和基本速率\(r_b\),如果出现以下情况则判断为碰撞丢包:\(r\)传送短帧成功,\(r_b\)传输短帧失败;\(r_b\)传输短帧成功,但ACK反馈的SNR有能力支持更高的速率。
      • MiRA33:这是一个用于MIMO信道的方法。它在inner-mode和intra-mode之间使用zigzag速率自适应来应对MPDU loss的问题。它会先在intra-mode进行速率探测,直到goodput不再升高时,会zigzag到inter-mode,只有在当前速率的滑动平均goodput明显变化的时候才会开启探测。探测间隔同样是自适应的,使得goodput较低的时候探测次数会少一点。在探测最佳速率的时候同样会考量到帧聚合和BlockAck。它同样有碰撞检测机制——如果聚合帧发生了至少一次的重传但是子帧的丢失率小于10%则认为碰撞。如果发生碰撞,就会触发一个自适应的RTS/CTS机制,这也是这一方法的主要缺陷,引入了该机制成为额外开销。
    3. 基于发送方的RSS检测

      • 文献11根据RSS进行区分。发送节点在发送完数据的SIFS(短帧空间)时隙中检测信道,如果RSS超过门槛且没有收到ACK则认为碰撞,这种方法对传输时间较短的干扰信号无效,且RSS门槛值不好找(需要考虑接收处的SNR和灵敏度)。
      • WOOF15,对Sample算法的修正,初速设为最大,根据丢包率调速,但是会结合信道的拥塞程度修正丢包率,用CBTF(Channel Busy Time Fraction)衡量网络的拥塞程度,定义为一定时间间隔内信道忙时隙所占的比例。信道忙时隙通过检测RSS是否超过了设定阈值进行判断。

1.2 基于接收节点处的SNR预测反馈:

  1. RSSLA(Link Adaptation via Received Signal Strength Measurement)16:根据重传次数调整速率。在带AP的WLAN中,假定AP的发送速率固定时,则各节点通过检测来自AP的信号强度RSS,在固定背景噪声N的情况下,可以认为SNR=RSS/N。各节点一方面通过接收到的任何从AP发送给自己的信号更新其RSS-avg,另一方面存储并不断更新12个门槛值,表示对应4个数据速率,3中数据包长度区间所要求的最小RSS值。这里直接用平均方法进行RSS预测,实际误差大。

  2. SGRA17:这个工作发现尽管信噪比SNR能够较好地预测信道状况,但帧传输率FDR从0到1,SNR对应5~7dB的渐变带宽,以SNR阈值作为速率的突变调整不够准确。它利用接收到的ACK包的Signal Strength来估算SNR,具体的调节策略包括在线校准机制和速率适应机制。利用\(SNR_{low}\)对应的10%的FDR和\(SNR_{high}\)对应的90%的FDR建立了SNR-FDR的在线校准曲线,将信道分为干扰和无干扰,由SNR预测各种速率R对应的\(FDR[R]\),选取\(argmax_R FDR[R]*R\);干扰时通过采样测试干扰强度的变化修正丢包率以选择合适速率。

  3. CHARM(channel-aware rate adaptation algorithm)18: 根据重传次数调整速率。基于路径损耗和噪声功率预测发送速率的调整机制。每个ACK,数据包和控制包中都包含当前的发送功率P,噪声功率N。任何节点接收包时,根据自身目前的RSS计算节点对之间的路径损耗\(PL=P-RSS\)。由此计算接收节点信噪比。

RSSLA和SGRA都认为RSS和SNR存在线性关系,对于固定背景噪声的带基站形式的WLAN比较适用(AP)。而CHARM则对于任意无线网络都相对适用。基于SNR预测的机制,会由于节点运动引起信道相干时间变化,导致SNR和BER的关系也随环境而变化,因此在移动环境下适应性差而且需要针对不同硬件平台校准。

1.3 基于物理层信息反馈机制预测BER

2 基于信息反馈的收端决定的自适应速率算法

由接收节点直接根据信噪比决定传输速率,并将速率信息反馈会发送节点,需要RTS/CTS支持,需要改MAC帧格式,增加一些新字段;或者需要修改ACK用以反馈

2.1 使用RTS/CTS进行反馈

2.2 使用ACK进行反馈

3 基于速率和其他参数的综合调整的速率控制算法

4 无线网络瓶颈探测

img

img

5 参考文献


  1. Kamerman A, Monteban L. WaveLAN®‐II: a high‐performance wireless LAN for the unlicensed band[J]. Bell Labs technical journal, 1997, 2(3): 118-133. 

  2. Lacage M, Manshaei M H, Turletti T. IEEE 802.11 rate adaptation: a practical approach[C]//Proceedings of the 7th ACM international symposium on Modeling, analysis and simulation of wireless and mobile systems. 2004: 126-134. 

  3. Chevillat P, Jelitto J, Barreto A N, et al. A dynamic link adaptation algorithm for IEEE 802.11 a wireless LANs[C]//IEEE International Conference on Communications, 2003. ICC'03. IEEE, 2003, 2: 1141-1145. 

  4. Qiao D, Choi S. Fast-responsive link adaptation for IEEE 802.11 WLANs[C]//IEEE International Conference on Communications, 2005. ICC 2005. 2005. IEEE, 2005, 5: 3583-3588. 

  5. Madwifi[EB/OL]. http://sourceforge.net/projects/madwifi 

  6. Bicket J C. Bit-rate selection in wireless networks[D]. Massachusetts Institute of Technology, 2005. 

  7. Haratcherev I, Langendoen K, Lagendijk R, et al. Hybrid rate control for IEEE 802.11[C]//Proceedings of the second international workshop on Mobility management & wireless access protocols. 2004: 10-18. 

  8. Pang Q, Leung V C M, Liew S C. A rate adaptation algorithm for IEEE 802.11 WLANs based on MAC-layer loss differentiation[C]//2nd International Conference on Broadband Networks, 2005. IEEE, 2005: 659-667. 

  9. Rayanchu S, Mishra A, Agrawal D, et al. Diagnosing wireless packet losses in 802.11: Separating collision from weak signal[C]//IEEE INFOCOM 2008-The 27th Conference on Computer Communications. IEEE, 2008: 735-743. 

  10. Kim J S, Kim S K, Choi S H. CARA: Collision-aware rate adaptation for IEEE 802.11 WLANs[J]. The Journal of Korean Institute of Communications and Information Sciences, 2006, 31(2A): 154-167. 

  11. Wong S H Y, Yang H, Lu S, et al. Robust rate adaptation for 802.11 wireless networks[C]//Proceedings of the 12th annual international conference on Mobile computing and networking. 2006: 146-157. 

  12. Chen X, Qiao D, Yu J, et al. Probabilistic-based rate adaptation for IEEE 802.11 WLANs[C]//IEEE GLOBECOM 2007-IEEE Global Telecommunications Conference. IEEE, 2007: 4904-4908. 

  13. Wu S. ERA: An Efficient Rate Adaption Algorithm with Fragmentation[J]. 2007. 

  14. Biaz S, Wu S. OTLR: Opportunistic transmission with loss recovery for WLANs[C]//2008 IEEE Wireless Communications and Networking Conference. IEEE, 2008: 1541-1546. 

  15. Camp J, Knightly E. Modulation rate adaptation in urban and vehicular environments: Cross-layer implementation and experimental evaluation[J]. IEEE/ACM Transactions on Networking, 2010, 18(6): 1949-1962. 

  16. Pavon J P, Choi S. Link adaptation strategy for IEEE 802.11 WLAN via received signal strength measurement[C]//IEEE International Conference on Communications, 2003. ICC'03. IEEE, 2003, 2: 1108-1113. 

  17. Zhang J, Tan K, Zhao J, et al. A practical SNR-guided rate adaptation[C]//IEEE INFOCOM 2008-The 27th Conference on Computer Communications. IEEE, 2008: 2083-2091. 

  18. Judd G, Wang X, Steenkiste P. Efficient channel-aware rate adaptation in dynamic environments[C]//Proceedings of the 6th international conference on Mobile systems, applications, and services. 2008: 118-131. 

  19. Vutukuru M, Balakrishnan H, Jamieson K. Cross-layer wireless bit rate adaptation[C]//Proceedings of the ACM SIGCOMM 2009 conference on Data communication. 2009: 3-14. 

  20. Holland G, Vaidya N, Bahl P. A rate-adaptive MAC protocol for multi-hop wireless networks[C]//Proceedings of the 7th annual international conference on Mobile computing and networking. 2001: 236-251. 

  21. Sadeghi B, Kanodia V, Sabharwal A, et al. Opportunistic media access for multirate ad hoc networks[C]//Proceedings of the 8th annual international conference on Mobile computing and networking. 2002: 24-35. 

  22. Li Z, Das A, Gupta A K, et al. Full auto rate MAC protocol for wireless ad hoc networks[J]. IEE proceedings-communications, 2005, 152(3): 311-319. 

  23. Qiao D, Choi S. Goodput enhancement of IEEE 802.11 a wireless LAN via link adaptation[C]//ICC 2001. IEEE International Conference on Communications. Conference Record (Cat. No. 01CH37240). IEEE, 2001, 7: 1995-2000. 

  24. Qiao D, Choi S, Shin K G. Goodput analysis and link adaptation for IEEE 802.11 a wireless LANs[J]. IEEE transactions on Mobile Computing, 2002, 1(4): 278-292. 

  25. Choudhury S, Gibson J D. Payload length and rate adaptation for multimedia communications in wireless LANs[J]. IEEE Journal on Selected Areas in Communications, 2007, 25(4): 796-807. 

  26. Yang X, Vaidya N. Spatial backoff contention resolution for wireless networks[C]//2006 2nd IEEE Workshop on Wireless Mesh Networks. IEEE, 2006: 13-22. 

  27. Kim T S, Lim H, Hou J C. Improving spatial reuse through tuning transmit power, carrier sense threshold, and data rate in multihop wireless networks[C]//Proceedings of the 12th annual international conference on Mobile computing and networking. 2006: 366-377. 

  28. Schmidt F, Hithnawi A, Punal O, et al. A receiver-based 802.11 rate adaptation scheme with on-demand feedback[C]//2012 IEEE 23rd International Symposium on Personal, Indoor and Mobile Radio Communications-(PIMRC). IEEE, 2012: 399-405. 

  29. Lee O, Kim J, Lim J, et al. SIRA: SNR-Aware intra-frame rate adaptation[J]. IEEE Communications Letters, 2014, 19(1): 90-93. 

  30. Byeon S, Yoon K, Yang C, et al. STRALE: Mobility-aware PHY rate and frame aggregation length adaptation in WLANs[C]//IEEE INFOCOM 2017-IEEE Conference on Computer Communications. IEEE, 2017: 1-9. 

  31. Fietkau F, Smithies D. minstrel ht: New rate control module for 802.11 n[J]. http:,//lwn. net/Articles/376765, 2010. 

  32. Arif T Y, Munadi R. Evaluation of the Minstrel-HT Rate Adaptation Algorithm in IEEE 802.11 n WLANs[J]. International Journal of Simulation--Systems, Science & Technology, 2017, 18(1). 

  33. Pefkianakis I, Lee S B, Lu S. Towards MIMO-aware 802.11 n rate adaptation[J]. IEEE/acm Transactions on Networking, 2012, 21(3): 692-705. 

  34. Nguyen D, Garcia-Luna-Aceves J J. A practical approach to rate adaptation for multi-antenna systems[C]//2011 19th IEEE International Conference on Network Protocols. IEEE, 2011: 331-340. 

  35. Kriara L, Marina M K. SampleLite: A hybrid approach to 802.11 n link adaptation[J]. ACM SIGCOMM Computer Communication Review, 2015, 45(2): 4-13. 

  36. Selinis I, Katsaros K, Vahid S, et al. Damysus: A practical IEEE 802.11 ax BSS color aware rate control algorithm[J]. International Journal of Wireless Information Networks, 2019, 26(4): 285-307. 

  37. Yin W, Hu P, Indulska J, et al. Performance of mac80211 rate control mechanisms[C]//Proceedings of the 14th ACM international conference on Modeling, analysis and simulation of wireless and mobile systems. 2011: 427-436. 

  38. Lin C R, Chang Y H J. AAR: An adaptive rate control protocol for mobile ad hoc networks[C]//The 11th IEEE International Conference on Networks, 2003. ICON2003. IEEE, 2003: 585-590. 

  39. Khan S, Mahmud S A, Noureddine H, et al. Rate-adaptation for multi-rate IEEE 802.11 WLANs using mutual feedback between transmitter and receiver[C]//21st Annual IEEE International Symposium on Personal, Indoor and Mobile Radio Communications. IEEE, 2010: 1372-1377. 

  40. Huang T, Chen H, Zhang Z, et al. EasiRA: A hybrid rate adaptation scheme for 802.11 mobile wireless access networks[C]//2012 IEEE Wireless Communications and Networking Conference (WCNC). IEEE, 2012: 1520-1525. 

  41. Balasingam A, Bansal M, Misra R, et al. Detecting if LTE is the Bottleneck with BurstTracker[C]//The 25th Annual International Conference on Mobile Computing and Networking. 2019: 1-15. 

  42. Pei C, Zhao Y, Chen G, et al. WiFi can be the weakest link of round trip network latency in the wild[C]//IEEE INFOCOM 2016-The 35th Annual IEEE International Conference on Computer Communications. IEEE, 2016: 1-9. 

Other Articles

Previous Article: 利用docker-compose快速部署——以Cloudreve为例