2015, Vol. 26
IEEE 802.11n中速率、模式及信道的联合自适应算法
引用本文
陈剑, 李贺武, 张晓岩, 周俊. IEEE 802.11n中速率、模式及信道的联合自适应算法[J].软件学报,2015, 26(1): 98-108.http://www.jos.org.cn/1000-9825/4583.html 
CHEN Jian, LI He-Wu, ZHANG Xiao-Yan, ZHOU Jun. Joint Adaptation Algorithm of Rate, Mode and Channel for IEEE 802.11n[J]. Ruan Jian Xue Bao/ Journal of Software, 2015, 26(1): 98-108.http://www.jos.org.cn/1000-9825/4583.html
IEEE 802.11n中速率、模式及信道的联合自适应算法
1 解放军理工大学 指挥信息系统学院, 江苏 南京 210007;
2 清华大学 信息网络工程研究中心, 北京 100084;
3 Faculty of Electrical Engineering, Mathematics and Computer Science, University of Twente, Enschede 7500, Netherland;
4 南京师范大学 数学科学学院 数学研究所, 江苏 南京 200023
2 清华大学 信息网络工程研究中心, 北京 100084;
3 Faculty of Electrical Engineering, Mathematics and Computer Science, University of Twente, Enschede 7500, Netherland;
4 南京师范大学 数学科学学院 数学研究所, 江苏 南京 200023
摘要：针对IEEE 802.11n无线网络中的速率、MIMO模式与信道宽度的联合自适应问题,提出了一种基于非静态Multi-Armed Bandit学习方法的联合自适应算法,并设计了一种新颖的报酬函数.为解决该算法收敛时间较慢的问题,基于分类回归树设计了MCS、MIMO模式以及信道宽度预测算法,其能够有效利用无线网卡驱动程序采集的相关统计数据预测不同MCS、MIMO模式以及信道宽度组合的报酬函数,大幅度缩小联合自适应算法的搜索空间.该算法具有易实现、近似最优及计算复杂度低的特点.真实实验结果表明:在无干扰和不同干扰环境下,联合自适应算法都能够有效地提高UDP吞吐量.
关键词：
速率
模式
信道宽度
联合自适应
预测算法
Joint Adaptation Algorithm of Rate, Mode and Channel for IEEE 802.11n
1 College of Command Information Systems, PLA University of Science and Technology, Nanjing 210007, China;
2 Information Networks Engineering Research Center, Tsinghua University, Beijing 100084, China;
3 Faculty of Electrical Engineering, Mathematics and Computer Science, University of Twente, Enschede 7500, Netherland;
4 Research Institute of Mathematics, School of Mathematical Science, Nanjing Normal University, Nanjing 210023, China
2 Information Networks Engineering Research Center, Tsinghua University, Beijing 100084, China;
3 Faculty of Electrical Engineering, Mathematics and Computer Science, University of Twente, Enschede 7500, Netherland;
4 Research Institute of Mathematics, School of Mathematical Science, Nanjing Normal University, Nanjing 210023, China
Abstract: To address the issue of joint adaptation of rate, MIMO (multiple input multiple output) mode and channel width in IEEE 802.11n wireless networks, a joint adaptation algorithm based on non-stationary multi-armed bandit learning approach is proposed, and a novel reward function is also presented. To reduce the convergence time of the algorithm mentioned above, the prediction algorithms of MCS (modulation and coding scheme), MIMO mode and channel width based on classification and regression trees are developd to effectively utilize the statistical data collected by the wireless network interface driver to predict the reward values of different combination of MCS, MIMO mode and channel width, and shrink the search space of the joint adaptation algorithm. The proposed algorithm is easy to implement, approximately optimal, and has low computation complexity. The real experiment results show that the UDP throughput is improved significantly by the proposed algorithm under the interference-free environment and the environment with different interference conditions.
Key words:
rate
mode
channel width
joint adaptation
prediction algorithm
IEEE 802.11n[1]是2009年9月颁布的一项新的无线局域网标准,其对物理层和介质访问控制层都作了大的改进和扩展.在介质访问控制层,增加了帧聚合、块确认等机制,有效地提高了传输效率;在物理层,引入了多入多出(multiple input multiple output,简称MIMO)、信道绑定(两个20MHz的信道绑定成一个40MHz的信道)等技术,大幅提升了物理层发送速率.MIMO是IEEE 802.11n在物理层引入的核心关键技术,它利用多根收发天线进行无线传输,在充分散射的传输环境中允许在不增加功率和频谱带宽的条件下,既可通过空分多集(spatial diversity,简称SD)提高给定数据速率下的传输可靠性,又可通过空分复用(spatial multiplexing,简称SM)提高传输速率.
多模式是MIMO技术的内在特征,通常可以分为两类:SD模式和SM模式.SD模式利用多对收发天线之间传输信道衰落不相关的特性,通过分集接收合并改善信道衰落,进而提高链路的传输可靠性.SM模式通过空分复用技术将信号在不同收发天线间并行传输,从而有效地提高传输速率.不同模式在不同环境下获得的性能增益不同,SM模式在信道空分结构较好的条件下取得更优的性能增益,SD模式则在信噪比(signal noise ratio,简称SNR)较低的条件下,可通过分集接收合并提高性能增益.Demmel条件数[2]能够很好地反映出当前工作信道的空分结构状态,然而由于受到硬件和计算复杂度的限制,目前商用无线网卡都不能支持Demmel条件数的获取.因此,如何优化MIMO模式的自适应选择,成为了充分利用MIMO技术优势的关键,同时也是研究的难点所在.
速率自适应是IEEE 802.11a/b/g无线网络中链路层的重要传输优化机制,其根据时变的信道状态为每个待发送报文选择最优的物理层发送速率,即,调制与编码方案(modulation and coding scheme,简称MCS),进而优化传输性能.目前,速率自适应机制主要可分为两类:闭环和开环.在闭环速率自适应机制中,接收方将其接收信道质量或最佳接收速率显式地反馈给发送方,发送方根据接收到的反馈动态调整发送速率;在开环速率自适应机制中,发送方根据探测的信道质量或历史统计信息估计当前的最佳发送速率.闭环速率自适应机制需要收发双方紧密协作,但IEEE 802.11协议族并未对速率自适应做出明确规定,不同生产厂商的无线网络设备之间彼此很难兼容.因此在实际使用中,广泛采用的都是开环速率自适应机制.
在IEEE 802.11a/b/g无线网络中,MCS决定了物理层发送速率,而IEEE 802.11n无线网络中物理层发送速率则由MCS、MIMO模式以及传输信道宽度等因素共同决定.因此,IEEE 802.11n无线网络的速率自适应从一维的最佳MCS搜索问题扩展到三维(MCS、MIMO模式、信道宽度)的组合优化问题.到目前为止,该问题还未得到深入而系统的研究.MCS、MIMO模式和信道宽度的组合优化问题本质上是探索与利用(exploration vs. exploitation)的优化问题,即,如何动态探索和利用三者的最优组合配置.针对该问题,本文首先利用非静态Multi- Armed Bandit学习方法设计MCS、MIMO模式和传输信道宽度的开环联合自适应算法,并提出一种新的报酬函数;其次,为解决上述算法存在收敛速度慢的问题,基于分类回归树设计MCS、MIMO模式以及信道宽度预测算法,大幅减少随机探测次数,进而有效地提高收敛速度.真实实验结果表明:与现有的其他优化算法相比,本文所提出的联合自适应算法能够更加有效地提高UDP吞吐量.
本文第1节简要介绍相关工作.第2节详细描述本文需要解决的问题.第3节给出算法的细节描述,并对算法的实现、计算复杂度和性能进行简要讨论和分析.第4节针对实验结果进行分析和比较.
1 相关工作速率自适应的目标是为无线数据传输找到最优的物理层发送速率,亦即在发送速率和丢包率之间找到最佳平衡点,进而最大化传输吞吐量.速率自适应是IEEE 802.11无线网络中链路层优化的关键机制,得到了广泛关注.在传统的IEEE 802.11a/b/g无线网络中,速率自适应的目标是根据无线信道状态自适应地选择最优MCS. IEEE 802.11n在物理层增加了MIMO和信道绑定两种技术.MIMO技术带来了两种不同MIMO模式,不同MIMO模式决定了不同物理层传输速率.信道绑定允许将相邻的两个20MHz的信道绑定成一个40MHz的信道使用,在相同MCS下,可使物理层传输速率提高一倍[3].由于上述两种技术的引入,因此,适用于IEEE 802.11a/b/g的速率自适应算法[4, 5, 6, 7]在IEEE 802.11n中并不能取得最优的传输吞吐量,甚至会降低无线传输性能[8].
自IEEE 802.11n成为正式标准以来,针对IEEE 802.11n的速率自适应算法成为了一个热点研究问题[8, 9, 10, 11, 12]. MiRA[9]将基于窗口的MCS随机探测法与Zigzag式的MIMO模式选择机制进行了有机结合.MiRA在同一MIMO模式下持续增加物理层发送速率直至吞吐量不再提升,随后改变MIMO模式,并在此模式下探测新的物理层发送速率.Zigzag式的MIMO模式选择的优点是易于实现,但其缺点是收敛于最优MIMO模式的速度较慢.陈剑等人[8]提出了一种简单、有效的MIMO模式选择算法,该算法在速率自适应的加速阶段采用交叉MIMO模式探测法,在找到最优MIMO模式后再进入MCS优化选择过程;进入平稳状态后,采用随机MIMO模式探测法选择最优MIMO模式.实验结果表明,该算法具有很好的最优MIMO模式收敛速度.文献[10]提出了一种速率自适应算法RAMAS,其将MCS和MIMO模式分成两个彼此独立的部分进行并发选择,并通过丢包来推断当前最佳的MIMO模式.文献[11]提出了一种闭环的速率与信道的联合自适应算法,利用不同接收天线的SNR区别来选择接收端的最佳MIMO模式,并通过802.11n标准中的HTC(high throughput control)字段将MIMO模式、信道宽度和SNR反馈回发送方.
与上述研究工作不同,本文将MCS、MIMO模式和信道宽度作为整体进行考虑,首先利用非静态的Multi- Armed Bandit学习方法设计一种开环的联合自适应算法;其次,利用分类回归树分别设计MCS、MIMO模式以及信道宽度预测算法,通过预测法大幅减少三维探索与利用优化算法中随机探测次数,有效地提升了联合优化算法的收敛速度.
2 问题描述本文工作主要针对无线局域网,其包含两类元素:访问点(access point,简称AP)和用户.AP位置相对固定,用户采用游牧的方式(这与大多数无线局域网使用场景相符)进行移动,彼此之间都采用速率自适应算法进行传输优化.对于IEEE 802.11a/b/g标准而言,速率自适应算法RRAA[4],SampleRate[5],RBRA[6],CHARM[7]能够有效工作的基石之一是给定无线信道状态,吞吐量在所有速率点上只存在唯一极大点,亦即最优物理层发送速率.但是在IEEE 802.11n无线网络中,由于MIMO多模式和信道绑定的引入,吞吐量在所有速率点上则存在多个极大点,因此针对IEEE 802.11a/b/g标准的速率自适应算法是无法适用于IEEE 802.11n标准的.存在上述问题的主要原因在于:在某一MIMO模式下,发送速率无法再度提高时,通过切换MIMO模式,发送速率还能够进一步提高.为了更清楚地说明问题,我们通过图 1进行更细致的分析和说明.
 | Fig. 1 Impact of MIMO mode on MCS Selection图 1 MIMO模式对MCS选择的影响 |
图 1将不同模式下的MCS索引分成左右两列,MCS索引号和发送速率都是IEEE 802.11n标准所规定的.发送方首先在SD模式下进行最优发送速率探索,当MCS=3时,最佳发送速率为26Mb/s.但切换MIMO模式之后,最佳发送速率还可以继续提高至104Mb/s(MCS=13).从上述图列分析中可以看出,MIMO模式对MCS选择具有较深影响.因此,针对IEEE 802.11n无线网络的传输优化,必须对MCS和MIMO模式进行联合自适应.
正交频分复用(orthogonal frequency division multiplexing,简称OFDM)是IEEE 802.11n标准采用的物理层通信技术,其将一个信道分解成多个互不干扰的多个子信道,并将数据分解到不同子信道上进行并发传输.信道绑定允许将两个20MHz的信道捆绑成一个40MHz的信道,因此子信道数将增加1倍.在发送功率固定的情况下,每个子信道的发送功率将减少一半,接收端的SNR也会降低最少3dB.此外,报文成功接收率主要受最差子信道的SNR影响,因此传输信道越宽,越容易受到频率选择性衰弱的影响.实验结果表明[13]:增加信道频谱宽度并不一定能够提高传输吞吐量,在某些情况下甚至会严重降低吞吐量.同样,为了更清楚地说明问题,我们通过图 2更细致地分析和说明信道宽度对MCS选择的影响.
 | Fig. 2 Impact of channel width on MCS selection图 2 信道宽度对MCS选择的影响 |
图 2显示:当信道宽度为20MHz时,最佳发送速率为39Mb/s(MCS=4).进行信道绑定之后,发送速率变为90Mb/s,接收端的SNR下降了3dB.为保持接收方的报文成功接收率,发送方降低发送速率至60Mb/s(MCS=3),但此时最佳发送速率仍然大于信道绑定之前的39Mb/s.从图列分析中可以看出,信道绑定对于MCS的优化选择同样具有重要影响.
上述分析结果表明,MIMO模式与信道宽度对MCS的优化选择都具有重要影响.因此,如何设计一种联合自适应算法,是充分利用MIMO技术和信道绑定技术优势的关键所在,也是优化IEEE 802.11n无线网络性能的重要途径.
3 速率、模式与信道的联合自适应算法针对上节提出的速率、MIMO模式与信道的联合自适应问题,本节首先利用非静态Multi-Armed Bandit学习方法设计速率、MIMO模式和信道宽度的三维的探索与利用优化算法,并提出了一种新的报酬函数;其次,为了解决上述算法收敛时间较慢的问题,基于分类回归树分别设计了MCS、MIMO模式以及信道宽度预测算法,该算法能够有效利用无线网卡驱动程序采集的相关统计数据预测不同MCS、MIMO模式以及信道宽度组合的报酬函数,大幅度缩小联合自适应算法的搜索空间,提高收敛速度;最后,本节对算法的实现、计算复杂度及性能进行了详细的分析和讨论.
3.1 基于Multi-Armed Bandit模型的联合自适应算法随机探测法和基于历史统计的预测法是目前开环速率自适应机制主要采用的两类方法.
在IEEE 802.11a/b/g标准中,MCS数量比较小(例如,802.11g的MCS数量为8),因此基于随机和预测方法的一维搜索算法通常能够取得较好的效果.然而IEEE 802.11n标准中增加了MIMO模式和信道绑定技术,传统的一维搜索算法并不能直接得到有效应用.
第2节的分析表明,速率、MIMO模式与信道的联合自适应问题是一个典型的探索与利用问题.无线信道具有高度的时变特性,在通常情况下不具有稳定的概率统计特征,因此不适用于经典的Multi-Armed Bandit学习方法.针对该问题,本文基于文献[14]中所提方法设计速率、MIMO模式与信道的三维非静态Multi-Armed Bandit探索与利用优化算法.
3.1.1 符号定义报文的物理层发送速率r主要由MCS、MIMO模式和信道宽度决定,本文用M表示整个可用MCS集合{M|m1<…<ml},MCS编号越大,发送速率越高.此外,用S表示MIMO模式集合{SD,SM},用W表示信道宽度集合{20,40}.为了便于非静态Multi-Armed Bandit探索与利用优化算法的性能分析,本文假定收发双方之间的数据传输以帧为单位,用F表示,帧传输时采用相同的物理层发送速率,并且每帧所需的传输时间为固定值T.IEEE 802.11n标准支持报文聚合功能,它能够将多个报文聚合成一帧.同时,根据发送速率动态调整帧中报文的数量,以实现每帧传输时间基本相似.因此,本文的假定是合理的.fm,s,w表示在MCS m、MIMO模式s和信道宽度w条件下,总共已发送帧的数量,Nm,s,w则表示在时间T内该帧所能发送的报文数量.此外,由于时间T固定,使用不同发送速率r的帧,具有如下相互关系:{Nm¢,s¢,w¢/r¢=Nm,s,w/r|s,s¢ÎS;m,m¢ÎM;w,w¢ÎW}.rm,s,w表示帧中报文成功发送的概率.由于无线信道具有时变特性,因此,rm,s,w也是时变的,不具备稳态的统计特征.令qm,s,w表示在MCS m、MIMO模式s和信道宽度w条件下总共成功接收的报文数,可得rm,s,w=qm,s,w/(fm,s,wxNm,s,w).
3.1.2 探索与利用优化模型探索与利用优化解决的核心问题是在探索新的最优解与利用已知最优解之间找到平衡,在静态系统中(系统各种状态具有稳定的统计分布特征),经典的Multi-Armed Bandit算法在经过多次探索与利用的迭代循环后,能够收敛到最优解.
本文基于文献[14]中所提方法,针对非静态Multi-Armed Bandit探索与利用模型,设计了一种新颖的MCS、MIMO模式和信道宽度的联合自适应算法.该算法为每一个三元组ám,s,wñ分配一个报酬,并根据公式(1)进行动态更新.在传输数据帧时,联合自适应算法选择报酬最高的三元组,其表示目前已知的最佳MCS、MIMO模式和信道宽度组合.
公式(1)所表示的报酬函数由探索因子和利用因子两部分组成.qm,s,w/fm,s,w表示到目前为止,在MCS m、MIMO模式s和信道宽度w条件下,获得的平均吞吐量.该部分反映出当前三元组的利用因子,数值越大,吞吐量
越高,发送方越倾向于选择该三元组.
反映的是当前发送方的
探索因子,当发送方没有对某一三元组ám,s,wñ进行探测时,fm,s,wxNm,s,w会逐渐变小,探测因子则会逐渐变大.B为发送方处于最高发送速率(三元组为ámr,SM,40ñ)下的报酬,亦即报酬上界.a为探索与利用的平衡因子,a值越大,发送方越倾向于探索新的三元组.
上述探索与利用优化算法面临一个较大的问题:即搜索空间大、算法收敛时间长.联合自适应算法是基于帧的,因此,收敛时间过长将造成联合自适应算法难以快速跟踪无线网络环境和状态从而为每帧的传输选择最优三元组,不能取得预期的传输优化效果,甚至严重影响性能.针对该问题,本文基于分类回归树设计三元组的报酬预测算法.
3.2 基于分类回归树的预测算法 3.2.1 MIMO模式与信道宽度的预测MIMO模式和信道宽度的集合大小均为2,搜索空间较小,因此,本文首先完成对MIMO模式和信道宽度的预测.本节采用文献[15]中所提出的经典CART方法构建MIMO模式与信道宽度的分类回归树,其属性为ám,w,s,qm,s,w,rm,s,wñ.该预测法根据不同MIMO模式和信道宽度的平均qs,w和rs,w,预测下一帧传输时采用的MIMO模式和信道宽度.当对第i帧的MIMO模式和信道宽度预测时,首先需要计算qs,w和rs,w,方法如下:
上式中,R为总的MCS数量.将qs,w和rs,w在构建的MIMO模式与信道宽度的分类回归树上进行分类和识别,得出预测的最佳MIMO模式s*和w*.由于联合自适应算法并不真正探测s*和w*,因此分别对在s*和w*下发送的帧数和成功发送报文数进行调整,即:
本节同样采用CART方法构建MCS分类回归树,其属性为ám,qm,s,w,rm,s,wñ.在MIMO模式为s*、信道宽度为w*的条件下,当对第i帧的MCS预测时,首先需要计算预测的
和
,即,发送完第i帧后总的成功接收报文数和成功接收概率.本文采用滑动平均方法对上述两个变量进行计算,方法如下:
上式中:win为滑动平均窗口大小;s为平滑因子,s值越大,近期所得到的q和r在预测MCS时影响越大.将qm,s,w(i)和rm,s,w(i)在构建的MCS分类回归树上进行分类和识别,得出预测的最佳MCS m.联合自适应算法并不真正探测m*,因此只需对m*下发送的帧数进行调整,即:
本算法每隔时间T,根据驱动程序采集的相关统计数据:首先,对MIMO模式和信道宽度进行预测;然后,在此基础上再对MCS进行预测;最后,综合得出预测的最佳三元组ám*,s,wñ.下面给出三元组ám*,s,wñ的
更新函数:
其中,
为第i帧传输采用三元组ám*,s,wñ的预测报文成功发送概率.为适应非静态Multi-Armed Bandit问题的求解,根据文献[14]中所提优化模型,本文同样设定一个折扣因子g(g<1).最后,将
和
代入公式(1)更新预测最佳三元组的报酬函数.
经过多次帧传输后,本预测算法能够根据相关统计数据,计算出不同预测最佳三元组的报酬函数,进而减少联合自适应算法在不同三元组上的随机探测次数.此外,通过基于分类回归树的预测算法,可以提高联合自适应算法在三元组选择上的倾向性,即:增加对最优三元组的利用率,减少探索与利用过程中带来的报酬损失.
3.3 联合自适应算法伪码描述Algorithm 1.
1. Initialization: mm,s,w=0,fm,s,w=0,qm,s,w=0,rm,s,w=0,for all m,s,w;
2. At each time frame i=0,1,2,…;
3. Select MCS m,MIMO mode s,channel width w (breaking ties arbitrarily) such that:
ám,s,wñ=argmaxmm,s,w(i) //for the whole frame,the packets are sent on ám,s,wñ;
4. Observe the outcomes qm,s,w and rm,s,w,and calculate fm,s,w;
5. Use the CART method to predict the best ám*,s,wñ;
6. Update 
and 
of the predicted ám*,s,wñ,according to the Equ. (2),Equ. (3) and Equ. (4);
7. Update the reward value 
of ám*,s,wñ,according to the Eq.(1);
8. Goto Step 3;
3.4 算法实现讨论本节主要对算法的可实现性进行讨论.基于分类回归树的MCS、MIMO模式和信道宽度预测算法利用经典的CART方法进行设计和实现,本文所提出的预测方法是完全可行的.基于非静态Multi-Armed Bandit的联合自适应算法本质上是对三维的报酬数组进行最优查找,因此,利用已有的快速排序方法可以简单有效地实现该算法,本文所提出的联合自适应算法也是完全可行的.此外,算法实现还需要重点考虑的是如何固定帧传输时间.IEEE 802.11n标准中增加了报文聚合功能,能够将多个报文聚合成一帧.利用报文聚合,本算法可以根据选择的三元组ám,s,wñ,动态调整每帧所传输的报文数,进而保证每帧具有相似的传输时间.目前,IEEE 802.11n无线网卡广泛采用的驱动程序ATH9K[16],能够详细记录每帧传输的细节信息,包括不同MCS、MIMO模式和信道宽度下已发送的帧和报文总数、成功发送的报文总数、丢弃报文数、报文错误率以及确认报文的SNR等信息,这都为分类回归树的构建和报酬函数更新的实现提供了基础.最后,收发双方的信道切换同步问题也是一个实现难点,在本文中,我们采用如下实现方法:如果当前待发送帧需要进行信道切换时,则采用新的MCS和MIMO模式先发送一个信道切换协商报文;接收方收到协商报文后,返回确认报文,进行信道切换,并等待接收新报文;发送方收到确认后,切换信道,按照新的三元组ám,s,wñ发送数据帧.
3.5 算法计算复杂性分析基于非静态Multi-Armed Bandit学习方法的联合自适应算法为每个待发送数据帧从MCS、MIMO模式和信道宽度构成的三维数组中选择报酬函数最大的三元组,因此,利用已有的快速排序方法可以实现O(nlogn)的计算复杂度,其中,n为整个三维数组空间大小.
MCS、MIMO模式和信道宽度预测算法的计算复杂度关键在于CART算法,其基本原理是:通过对由测试变量和目标变量构成的训练数据集的循环分析,形成二叉树形式的分类回归树结构.CART算法的计算分为两部分:训练和识别.识别的计算复杂度与树的高度相同,即O(logk),其中,k为训练样本空间大小.在构建分类回归树时,在根节点(第0层),首先需要将全部数据进行排序,因此对于任意一维特征,需要进行O(klogk)次计算.分析平均的情况,即各有一半训练样本在二叉树节点上向两边分支.第1层有两个子节点,每个子节点的计算复杂度为O((k/2)log(k/2)),所以总计算量为O(klog(k/2)).同理,第2层的总计算量为O(klog(k/4)).依次类推.由于树的高度为O(logk),对全部层的计算复杂度求和得到构建分类回归树的总计算复杂度为O(dk(logk)2),其中,d为训练样本数据的维度.在本文中,MCS预测算法的数据维度为3,MIMO模式与信道宽度预测算法的数据维度为5.
3.6 算法性能分析本节对所提联合自适应算法的性能进行理论分析.假定有一种理想算法,其为第i帧的传输选择最优的三元组为ám*(i),s(i),w(i)ñ,本算法为第i帧所选择的三元组记为ám(i),s(i),w(i)ñ.用函数diff(i)表示传输第i帧时两个三元组取得的吞吐量之差,具体形式如下:
根据上式,到第I帧为止,本文所提联合自适应算法与理想算法之间的平均吞吐量之差可表示为
设定理想算法的最优三元组ám*(i),s(i),w(i)ñ的变化速率最高上界为U(U>0),B为报酬上界.
定理1. 本文所提联合自适应算法与理想算法之间的平均吞吐量之差,满足如下约束条件:
证明:本文所提联合自适应算法是基于D-UCB[14]算法设计的,采用基于分类回归树预测法计算的伪三元组报酬并不影响算法的近似最优属性,因此,本算法依然是近似最优的,详细证明可参考文献[14].
尽管本文所提算法具有D-UCB算法相似的近似最优属性,但通常来说,本文所提算法在实际使用过程中具有更好的性能,尤其是三元组ám,s,wñ数量较大的情况下.原因在于:本文通过预测算法计算伪三元组报酬函数,大幅减少了算法的探测次数,可以充分而有效地利用已知最佳三元组.
此外,从定理1中可以得知:当最优三元组的变化速率U趋近于0时,diff(I)也趋近于0,因此,我们可以得到如下推论:
推论1. 当平均报文成功发送率为常数时(亦即所有信道的状态变化具有独立同分布特性),则本文所提联合自适应算法与理想算法之间的平均吞吐量之差为0.
推论1给出了一个很直观的结果,即,本算法能够很好地适用于最优三元组变化较慢的网络环境.
4 实验性能评价本节通过真实实验对上述设计的联合自适应算法进行实验性能评价.我们在ATH9K[16]无线网卡驱动的速率自适应模块Minstrel[17]上对联合自适应算法、MISS[8]算法以及文献[9]中提出的Zigzag算法了进行了实现,并对联合自适应算法、MISS算法、Zigzag算法以及Minstrel(没有MIMO天线模式选择机制,只作原始的速率自适应)在不同实验环境下进行了详细的实验评价分析.
4.1 实验环境我们采用IBM T410笔记本电脑、Ubuntu11.10操作系统、基于Atheros 922X MIMO芯片的无线网卡、ATH9K无线网卡驱动及HostAP开源软件[18]搭建了一个原型系统用于实验评价.922X MIMO芯片最高支持2x3的天线配置模式,在20MHz和40MHz的信道上分别支持最高130Mbps和300Mbps的传输速率.
本文研究所涉及到的实验环境如图 3所示,图中标注的4个点(A,B,C,D)为实验数据采集点.由于某些特殊原因,该实验楼未安装任何无线局域网AP,因此实验环境几乎没有任何Wi-Fi干扰信号.我们采用Agilent N9010A信号分析仪对实验所采用的无线信道进行全面监测,以确保实验环境的准确、可靠.
 | Fig. 3 Experiment environment图 3 实验环境 |
本实验采用的是商用无线网卡,其信道的切换时延为2~3(ms).为了弱化信道切换时延对算法性能的影响,本文将帧长时间设定为30ms.设定探索与利用的平衡因子a=0.2,平滑因子s=0.3,报酬函数折扣因子g=0.25.
4.2 结果分析我们设计和完成了多组实验,这些实验可以归纳为两类不同的实验环境:干扰环境和无干扰环境.本节选择图 3中的3条无线链路(A-B,A-C,A-D)进行性能评价和分析,发送方采用Iperf[19]向每条链路发送UDP流量,每组实验重复进行3次,并对相关的实验结果进行统计平均、分析和比较.本文主要从UDP吞吐量方面对算法进行评价,通过链路和干扰因素的变化来衡量不同算法在UDP吞吐量上取得的性能指标.
4.2.1 无干扰环境下的性能分析图 4显示了4种算法在无干扰环境下的不同无线链路上的UDP吞吐量变化曲线.从图中可以看出,本文所提联合自适应算法能够在不同的无线链路上大幅度提升UDP吞吐量.与MISS和Zigzag相比,本文所提算法不仅能够优化速率与MIMO模式组合的选择,还能够根据无线信道状态,自适应地选择最优的传输信道宽度,从而进一步地提升发送速率.与标准的速率自适应算法Minstrel相比,本算法的平均UDP吞吐量优化率达到了120%.与MISS算法相比,平均UDP吞吐量优化率为30%,最高可达40%.
 | Fig. 4 Algorithm performance in an interference-free environment图 4 无干扰环境下的算法性能 |
本文主要考虑以下4种干扰环境:相邻40MHz干扰信道、重叠40MHz干扰信道、相邻20MHz干扰信道和重叠20MHz干扰信道.本实验将A-B作为性能测试链路,C-D作为干扰链路.在相邻40MHz干扰信道环境下,链路C-D采用的信道频谱带宽为40MHz,并与链路A-B采用的信道相邻.在实验中,设定链路A-B的信道为Channel 1(IEEE 802.11 标准定义了11个信道,每个信道宽度为20MHz,相邻信道的中心频点间隔为5MHz),链路C-D的信道中心频点与Channel 6相同,信道宽度为40MHz.在重叠40MHz干扰信道环境下,设链路A-B和链路C-D采用相同的40MHz信道.在相邻20MHz干扰信道环境下,设定链路A-B的信道为Channel 1,链路C-D的信道为Channel 6.在重叠20MHz干扰信道环境下,设定链路A-B和链路C-D的信道均为Channel 6.
4种算法在相邻信道干扰环境下的UDP吞吐量变化曲线如图 5所示.
 | Fig. 5 Algorithm performance under adjacent channel interference图 5 在相邻信道干扰环境下的算法性能 |
在相邻40MHz干扰信道环境下,由于干扰信道宽度为40MHz,因此链路A-B的信道宽度为20MHz和40MHz时都会受到干扰.从图 5(a)可以看出:本文所提算法具有较为明显的优势,原因是其能不断地学习并选择最优的信道宽度.在相邻20MHz干扰信道环境下,当链路A-B的信道宽度为20MHz时,链路A-B和链路C-D之间无干扰;而当链路A-B的信道宽度为40MHz时,彼此间存在相互干扰.从图 5(b)可以看出,本文所提算法与MISS算法在性能上差别不大.其中的主要原因是:本文所提算法经过学习后,采用40MHz信道干扰较大,吞吐量较低,因此后续传输中基本都采用20MHz信道.
图 6显示出在重叠信道干扰环境下的UDP吞吐量变化曲线,实验结果也都表明:本文所提算法能够根据无线信道状态,动态地选择最优的速率、MIMO模式与信道宽度组合,大幅度提高收发双方间的UDP吞吐量.
 | Fig. 6 Algorithm performance under overlap channel interference图 6 在重叠信道干扰环境下的算法性能 |
本文针对IEEE 802.11n无线网络中的速率、MIMO模式与信道宽度的联合自适应问题进行了深入研究,提出了一种基于非静态Multi-Armed Bandit学习方法的联合自适应算法.在该算法的基础之上,基于分类回归树分别设计了MCS、MIMO模式以及信道宽度预测算法,进一步解决了联合自适应算法的解空间较大、收敛速度较慢的问题,并提升了算法的实用性和可行性.本文所提算法不仅实现简单、计算复杂度低,而且理论分析表明,该算法具有近似最优属性.实测结果表明:在无干扰和不同干扰环境下,本文所提算法都能够有效地提高UDP吞吐量.本文设计的是一种开环自适应算法,在较大搜索空间下,很难处理快衰环境下的速率和MIMO模式下的联合自适应问题,不能够取得预期的优化效果.因此,下一步研究工作将考虑如何研究移动场景下的联合自适应问题.
参考文献
| [1] | IEEE 802.11n, Part 11: Wireless LAN medium access control (MAC) and physical layer (PHY) specifications: Enhancements for Higher Throughput. 2009. |
| [2] | Kim W, Khan O, Truong KT, Choi SH, Grant R, Wright HK, Mandke K, Daniels RC, Heath RW, Nettles Jr. SM. An experimental evaluation of rate adaptation for multi-antenna systems. In: Proc. of the 30th IEEE Int’l Conf. on Computer Communication (INFOCOM 2009). IEEE Press, 2009. 2313-2321 . |
| [3] | Yang X. IEEE 802.11n: Enhancements for higher throughput in wireless LANs. IEEE Wireless Communications, 2005,12(6): 82-91 . |
| [4] | Wong SH, Yang H, Lu SW, Bharghvan V. Robust rate adaptation for 802.11 wireless networks. In: Proc. of the 12th ACM Int’l Conf. on Mobile Computing and Networking (MobiCom 2006). ACM Press, 2006. 146-157 . |
| [5] | Bicket J. Bit-Rate selection in wireless networks [MS. Thesis]. Boston: Massachusetts Institute of Technology, 2005. |
| [6] | Holland G, Vaidya N, Bahl V. A rate-adaptive MAC protocol for multi-hop wireless networks. In: Proc. of the 7th ACM Int’l Conf. on Mobile Computing and Networking (MobiCom 2001). ACM Press, 2001. 236-251 . |
| [7] | Judd G, Wang X, Steenkiste P. Efficient channel-aware rate adaptation in dynamic environments. In: Proc. of the 6th ACM Int’l Conf. on Mobile Systems, Applications, and Services (MobiSys 2008). ACM Press, 2008. 118-131 . |
| [8] | Chen J, Li HW, Zhang FX, Wu JP. MIMO mode switching scheme for rate adaptation in 802.11n wireless networks. In: Proc. of the IEEE Global Communications Conf. (Globecom 2011). IEEE Press, 2011. 1-6 . |
| [9] | Pefkianakis I, Hu Y, Wong SHY, Yang H, Long SW. MIMO rate adaptation in 802.11n wireless networks. In: Proc. of the 16th ACM Int’l Conf. on Mobile Computing and Networking (MOBICOM 2010). ACM Press, 2010. 257-268 . |
| [10] | Duy N, Aceves JJ. A practical approach to rate adaptation for multi-antenna systems. In: Proc. of the 19th IEEE Int’l Conf. on Network Protocols (ICNP 2011). IEEE Press, 2011. 331-340 . |
| [11] | Deek L, Garcia-Villegas E, Belding E, Lee SJ, Almeroth K. Joint rate and channel width adaptation for 802.11 MIMO wireless networks. In: Proc. of the IEEE Int’l Conf. on Sensing, Communication, and Networking (SECON 2013). IEEE Press, 2013. 167-175 . |
| [12] | Chan AJ, Henrik L, Theodoros S. Video-Aware rate adaptation for MIMO WLANs. In: Proc. of the 19th IEEE Int’l Conf. on Network Protocols (ICNP 2011). IEEE Press, 2011. 321-330 . |
| [13] | Deek L, Garcia-Villegas E, Belding E, Lee SJ, Almeroth K. The impact of channel bonding on 802.11n network management. In: Proc. of the 7th ACM Conf. on Emerging Networking Experiments and Technologies (CoNEXT 2011). ACM Press, 2011. 11-21 . |
| [14] | Garivier A, Moulines E. On upper-confidence bound policies for non-stationary bandit problems. In: Proc. of the 8th European Workshop on Reinforcement Learning (EWRL 2008). 2008. Arxiv.org/ab/0805.3415 |
| [15] | Breiman L. Classification and Regression Trees. Chapman &Hall/CRC, 1984. |
| [16] | Linux wireless. http://wireless.kernel.org/MadWifi |
| [17] | SIP Solutions. Minstrel. http://wireless.kernel.org/MadWifi |
| [18] | Malinen J. HostAP. http://hostap.epitest.fi |
| [19] | NLANR/DAST. Iperf. https://iperf.fr/ |