WiFi自适应速率算法与无线网络瓶颈探测
本篇文章主要综述了超过40篇WiFi自适应速率算法的核心机制和无线网络(LTE和WiFi)下瓶颈的探测。
WiFi Rate Adaptive Algorithm and Wireless Bottleneck Detection
1 基于历史信息的发端决定的自适应速率算法
1.1 基于ACK的统计信息
容易实现，无需修改MAC帧格式，但是对信道状况的变化调整和反应往往不够及时
未进行丢包区分：这些算法都是通过发送节点统计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主要是在信道快变的情况下，尽量采用低速率从而保证可靠传输。
- RAMAS8：这是一个基于信用的算法，将传输速率调控分为两个组，一个是调制组(modulation)，另一个是增强组(enhancement)，前者有不同的MCS值，后者由空间串流(spatial stream）、保护间隔GI、信道宽度等组成，根据包传输的成功率和失败率统计信息，由两个组分别进行独立调控，然后将结果结合起来。根据9评测，这个算法可能对于多流情况的适应比较保守，而对于使用MCS的情况过于激进，导致在某些情况下表现差。
- STRALE10：联合调整PHY速率和A-MPDU(Aggregate MAC Protocol Data Unit)长度。在收到一个BlockACK之后，对于上一个A-MPDU传输计算能使其获得最高吞吐的最优A-MPDU长度。下一个A-MPDU长度将由EWMA决定出。两者之间的差将与一个阈值相比较，如果超过阈值，那么会检查是否使用更低一级的MCS将能够取得更高的吞吐。这个方法无法区分出干扰，在802.11n上进行了实现。
- Minstrel-HT11：依靠信道宽度，保护间隔(Guard Interval)和流的数量来创建速率组。每一组包含8个不同的数据传输速率（对应不同的MCS）。过程分为2部分：(1)采样部分，它会从速率组中随机选择一个可用速率，如果获得了更高的吞吐，则使用这个速率来传输下一个MPDU，否则仍使用之前的速率。此处的吞吐是根据采用了EWMA的FLR(Frame Loss Rate)。在进入非采样部分前，会统计出3个数据速率选择，最佳吞吐、次佳吞吐、最大可能(Most probablity)。(2)非采样部分，MPDU会先用最佳吞吐速率发送直到超过了最大重传次数，然后用次佳传输速率，同样会有可能使用最大可能速率。不过12表明在某些情况下，特别是在一个不衰减(non-fading)信道上，信道质量从坏变好的时候，它并不一定能够提升带宽。
- Damysus13：这个方法是用于802.11ax上的，利用了Basic Service Set(BSS) Color Scheme。它使用自适应的OBSS/PD(Overlapping Basic Service Set/Preamble-Detection）阈值并联合调整发送功率。每100ms的间隔就会完成一次统计报告，每1s一个循环会记录包的成功和失败率，并与阈值做比较。然后会据此决定是否增减传输速率、OBSS/PD阈值、传输功率。根据14分析，该方法依赖于丢包率阈值，而没有一个单一的最佳的丢包率PLR阈值能够帮助实现最大吞吐。
进行丢包区分：仍然是通过发送节点的ACK统计信息，但是增加了丢包区分的功能，丢包区分可以是来自接收方的反馈信息，也可以由发送方主动探测
基于接收方信息反馈：
- LD-ARF(loss differentiating-ARF)15：基于ARF，仍由成功失败次数调速，但增加了丢包区分。若发送节点收到了CTS而无ACK则认为信道丢包，降速；如果没有收到CTS则认为碰撞丢包，不降速。主要是认为控制帧以低的基本速率发送，不易丢包。
- 文献16利用接收信号强度、位错误率和symbol-level错误机制等信息，提出了一种COLLIE机制，区分两种丢包，通过AP将接收到的错误信号反馈回发送节点，由发送节点计算各种错误衡量参数，根据具体情况分别调整退避时间和传输速率。这种情况需要将错误帧信号反馈，开销大。
- EasiRA17：通过两种方式测量链路质量，首先计算丢帧率FLR并将其与移动性或其他传感器信息结合；其次它会取得ESS(Environmental Signal Strength)信息来帮助区分是什么原因导致了丢包。当一个包因为比特错误导致没法接收时，收端会回送一个NAK来告知发端碰撞丢包。如果发端没有收到ACK和NAK则减速。这个方法结合了随机和决定性的速率自适应机制，利用了外部信息。但是外部信息不一定所有设备都可用。
基于发送方探测：
- CARA(Collision-Aware Rate Adaptation)18：初速设为最小，依据成功失败次数调速，利用RTS/CTS探测区分两种丢包。当数据发送失败达到设定门槛值时，CARA协议启动RTS探测，以确定是否需要降低数据传输速率。例如启动probing之后，收到CTS回应，说明信道已经预留，但再次传输失败，则认为是信道质量问题。这个方法固然可以一定程度上区分丢包，但是若有隐藏终端时将导致RTS频繁开关，发送节点可能出现大量碰撞丢包。
- RRAA(Robust Rate Adaptation Algorithm)19：初速设为最大，依据丢包率调速，提出改进的探测方法A-RTS，通过控制RTS窗口值和RTS计数值，改善因为隐藏终端导致的碰撞丢包。
- PBRA20：在以上的基础上，增加了估算碰撞的概率决定是否使用RTS/CTS探测。
- OTLR21 22：在利用速率$r$发生丢包后，将数据帧分为长短帧，利用短帧试探速率$r$和基本速率$r_b$，如果出现以下情况则判断为碰撞丢包：$r$传送短帧成功，$r_b$传输短帧失败；$r_b$传输短帧成功，但ACK反馈的SNR有能力支持更高的速率。
- MiRA23：这是一个用于MIMO信道的方法。它在inner-mode和intra-mode之间使用zigzag速率自适应来应对MPDU loss的问题。它会先在intra-mode进行速率探测，直到goodput不再升高时，会zigzag到inter-mode，只有在当前速率的滑动平均goodput明显变化的时候才会开启探测。探测间隔同样是自适应的，使得goodput较低的时候探测次数会少一点。在探测最佳速率的时候同样会考量到帧聚合和BlockAck。它同样有碰撞检测机制——如果聚合帧发生了至少一次的重传但是子帧的丢失率小于10%则认为碰撞。如果发生碰撞，就会触发一个自适应的RTS/CTS机制，这也是这一方法的主要缺陷，引入了该机制成为额外开销。
基于发送方的RSS检测
1.2 基于接收节点处的SNR预测反馈
RSSLA(Link Adaptation via Received Signal Strength Measurement)25：根据重传次数调整速率。在带AP的WLAN中，假定AP的发送速率固定时，则各节点通过检测来自AP的信号强度RSS，在固定背景噪声N的情况下，可以认为SNR=RSS/N。各节点一方面通过接收到的任何从AP发送给自己的信号更新其RSS-avg，另一方面存储并不断更新12个门槛值，表示对应4个数据速率，3中数据包长度区间所要求的最小RSS值。这里直接用平均方法进行RSS预测，实际误差大。
SGRA26：这个工作发现尽管信噪比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$；干扰时通过采样测试干扰强度的变化修正丢包率以选择合适速率。
CHARM(channel-aware rate adaptation algorithm)27: 根据重传次数调整速率。基于路径损耗和噪声功率预测发送速率的调整机制。每个ACK，数据包和控制包中都包含当前的发送功率P，噪声功率N。任何节点接收包时，根据自身目前的RSS计算节点对之间的路径损耗$PL=P-RSS$。由此计算接收节点信噪比。
RSSLA和SGRA都认为RSS和SNR存在线性关系，对于固定背景噪声的带基站形式的WLAN比较适用（AP）。而CHARM则对于任意无线网络都相对适用。基于SNR预测的机制，会由于节点运动引起信道相干时间变化，导致SNR和BER的关系也随环境而变化，因此在移动环境下适应性差而且需要针对不同硬件平台校准。
1.3 基于物理层信息反馈机制预测BER
- softRate28确定不同调制方法和编码率下的BER映射关系，计算每个速率对应的最佳BER阈值范围$[\alpha, \beta]$，具体的阈值计算与错误恢复机制有关，接收方利用softPHY hint信号区分干扰和信道错误引起的丢包，计算无干扰下的帧的平均BER，反馈回发送端，发送端根据与阈值关系调速
2 基于信息反馈的收端决定的自适应速率算法
由接收节点直接根据信噪比决定传输速率，并将速率信息反馈回发送节点，需要RTS/CTS支持，需要改MAC帧格式，增加一些新字段；或者需要修改ACK用以反馈
2.1 使用RTS/CTS进行反馈
- RBAR(Receiver Based Auto Rate)29：接收节点收到发送节点发出的RTS后分析其信噪比，以此确定传输速率，用CTS通知发送节点，由此对于信道状况的变化反应更快，适应能力更强。
- OAR(Opportunistic Auto Rate)30：针对RBAR每次只发送一个数据包而没有充分利用信道条件的问题，这一方法提出了在信道条件良好的情况下，连续发送多个数据帧，发送数量为传输速率与基本速率的比值，不过因为其采用同样的速率连续传帧，对于此期间信道突变的适应性不好。AAR(Adaptive Auto Rate)31在此基础上继续加以改进，以自适应的速率传输每个数据分段，分段速率由接收节点估计并通过ACK返回。该方法能够适应信道突变，并灵活调整分段数据大小，但对于信道条件较差的环境，节点可能长时间没法接入信道，导致公平性较差。
- FAR(Full Auto Rate)32：结合了基于发送节点和接收节点的速率调整方法，对所有的帧都进行速率控制。RTS/CTS帧由发送节点控制，而数据和ACK帧由接收节点控制。该方法对控制帧也进行了速率自适应，提高性能，但没有考虑公平性的问题，同时控制帧冲突或碰撞时，没有有效的解决方法。
2.2 使用ACK进行反馈
- MutFed(Multual Feedback)33：收端测量SINR，每10帧根据SINR阈值到速率的映射表做一次速率选择，通过ACK发送回发端。发端一旦出现两帧传输失败，就自动降低MCS。该方法没法区分丢包。
- OFRA(On Demand Feedback Rate Adaptation)34：在收端根据SINR估计信道质量，然后根据事先预设好的lookup table选择一个最优的bit rate，然后按需（只在换速时）使用ACK反馈回发送端。如果是一个少ACK类型的网络，会使用一个特别设计的反馈帧。它的问题在于需要修改ACK帧格式，特别的反馈帧会引入额外开销（反馈帧会以最低速率发送）
- SIRA(SINR-aware Intra-frame Rate Adaptation)35：为单个Aggregate MAC Protocol Data Unit(A-MPDU)传输选择两个速率之一。当测得的SINR小于阈值（阈值是对于速率的理论BER小于1e-4时最小的SINR），将设置符号"I"，该symbol将会被通过BlockAck的形式feedback回发送端。该方法的问题主要在于只会为一个aggregated frame决定两个速率，这对于fast-fading的信道来说可能不够。
- Ideal方法（NS-3中有实现）：初始建立一个SINR和MCS的映射表对，表中的SINR阈值保证选择一个MCS会使得BER低于一个值（默认为1e-5)。带外反馈。
3 基于速率和其他参数的综合调整的速率控制算法
文献36 37 38建模：802.11a在高斯白噪声和Nakagami-m衰减信道模型(fast-fading)下吞吐量与信道状况、数据帧长和传输速率。
文献39结合载波侦听功率门槛值和数据传输速率的综合调整算法DSB(Dyamin Spatial Backoff)
文献40提出基于发送功率和速率的综合调整机制PRC(Power an dRate Control)，即通过噪声估算确定数据速率，并尽量降低发射功率，减小对其他并发传输的干扰。
4 无线网络瓶颈探测
- LTE： BurstTracker41：核心思想是知悉基站队列：如果基站队列为空，则认为瓶颈是在到基站之前；如果基站队列不为空，则认为瓶颈在基站。但本工作无需直接获取基站信息，而是利用用户端的信息来获取这一点。通过观察resource scheduling information（即RB的分配）来推断何时具有瓶颈。
- WiFi: Wily42：这个工作主要面向三个目标：WiFi hop latency的特征是怎么样的；哪个因素对WiFi hop latency影响最大；如何优化WiFi hop latency。提出了一个叫WiLy(WiFi hop Latency)的方法，能够有效地将RTNL(Round Trip Network Latency, RTT 减去 server processing time)拆分为UL(uplink wireless latency)， WL(wired network latency)， DL(downlink wireless latency)。它能够准确测量所有包的DL，然后使用三次握手中精确测量的UL和WL来近似估计其他包的UL和WL。它不需要客户设备的支持，可以在OpenWrt上部署，不需要芯片厂商的支持。测量了WiFi hop latency和WiFi factors(RSSI, retry ratio, airtime utilization, etc.)，利用这些Wifi factors，训练了一个决策树模型来指导优化。论文中举例比如在airtime utilization 大于55%的情况下，有超过67%的概率会有不良延时问题。他们发现导致AP长延迟的主要因素是高的airtime utilization和RSSI。
5 参考文献
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.
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.
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.
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.
Madwifi[EB/OL]. http://sourceforge.net/projects/madwifi
Bicket J C. Bit-rate selection in wireless networks[D]. Massachusetts Institute of Technology, 2005.
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.
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.
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.
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.
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.
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.
Wu S. ERA: An Efficient Rate Adaption Algorithm with Fragmentation[J]. 2007.
Biaz S, Wu S. OTLR: Opportunistic transmission with loss recovery for WLANs[C]//2008 IEEE Wireless Communications and Networking Conference. IEEE, 2008: 1541-1546.
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.
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.
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.
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.
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.
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.
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.
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.
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.
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.
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.
Yang X, Vaidya N. Spatial backoff contention resolution for wireless networks[C]//2006 2nd IEEE Workshop on Wireless Mesh Networks. IEEE, 2006: 13-22.
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.
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.
Lee O, Kim J, Lim J, et al. SIRA: SNR-Aware intra-frame rate adaptation[J]. IEEE Communications Letters, 2014, 19(1): 90-93.
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.
Fietkau F, Smithies D. minstrel ht: New rate control module for 802.11 n[J]. http:,//lwn. net/Articles/376765, 2010.
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).
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.
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.
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.
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.
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.
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.
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.
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.
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.
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.