多速率WLAN网络的时间公平调度算法

潘志鹏,吴 斌,叶甜春

(中国科学院微电子研究所,北京 100029)

多速率WLAN网络的时间公平调度算法

潘志鹏,吴 斌,叶甜春

(中国科学院微电子研究所,北京 100029)

IEEE 802.11协议的分布式协调功能使得各站点以相同的概率接入信道,会导致多速率无线局域网的性能异常.该文通过对吞吐率公平与时间公平进行详细的理论分析与比较,提出了一种线性可调节时间公平的循环轮询队列调度算法.该算法实时地统计各站点准确的信道占用时间,并采用循环轮询方式保证各站点之间的时间公平性,提升系统的吞吐率性能.为保障业务流的服务质量,采用动态调节方式更新轮询单位服务时间,实现了传输效率与延时性能的折中.经过NS-3仿真与硬件系统实测验证表明,该算法在严格保证时间公平的同时,有效提升了系统上/下行吞吐率性能.

无线局域网;吞吐率公平;时间公平;队列调度;NS-3仿真

现有无线局域网(Wireless Local Area Network,WLAN)支持802.11a/b/g/n/ac协议,存在1 Mbit/s至1 Gbit/ss多种发送速率.而多速率WLAN将导致高速率站点所获得的吞吐率性能与低速率站点保持一致,引起性能异常现象[1-2].这是由于802.11协议所采用的带冲突避免的载波侦听多路访问(Carrier Sense Multiple Access with Collision Avoidance,CSMA/CA)机制,本质上提供各个站点以同等概率接入信道,并不区分各站点的传输速率,而低速率站点将占用更多的信道时间资源来传输相同大小的数据帧,降低了系统资源使用效率的同时,也导致了高速率站点的不公平性.针对多速率WLAN的性能异常问题,大量文献基于时间公平性提出了不同的系统优化算法.根据优化对象可将其细分成两大类:上行优化算法[3-8]和下行优化算法[9-11].

上行优化算法是一种分布式协调方法,通常采用修改各站点媒体接入控制层(Media Access Control, MAC)的参数,实现上行链路资源的最优化分配.可修改的MAC接入参数包括竞争窗口[6-7]、最小竞争窗口[4-5]、仲裁帧间间隔[5]、数据帧大小[8]、多分布式协调功能(Distributed Coordination Function,DCF)实例[3]等.而下行优化算法则是一种集中式调节算法,利用接入点对各个站点的高效调度机制,可以保证各个站点获得同等的信道时间资源,进而实现下行链路的最优化分配.

目前,接入点的队列调度机制一般采用先到先服务(First-Come First-Served,FCFS)或循环轮询(Round Robin,RR)算法,保证了各个站点的吞吐率公平,尤其是单速率WLAN网络.而下行优化算法采用基于时间公平的队列调度机制,如基于时间的调节器(Time-Based Regulator,TBR)算法[9]与差额传输时间(Deficit Transmission Time,DTT)算法[10]等,一定程度上提升了下行链路的系统吞吐率性能.

笔者以不修改MAC层接入参数为前提,提出了一种线性可调节时间公平的循环轮询队列调度算法(Time-based Fairness Round Robin,TFRR),在保证下行用户数据报协议(User Datagram Protocol,UDP)与传输控制协议(Transmission Control Protocol,TCP)传输链路以及上行TCP传输链路的时间公平性的同时,又能有效地提升系统的吞吐率性能.

1　系统模型与理论分析

一个典型的基础型WLAN网络,由1个接入点(Access Point,AP)负责管理N个站点(Station,STA)的无线接入,而处于不同信道环境的STA会通过速率自适应选择最佳的发送速率,最终导致同一个网络存在多种传输速率.不同的公平机制严重影响了多速率WLAN的系统性能.以下针对吞吐率公平与时间公平进行详细的理论分析与性能比较.

假设站点i的发送速率为ri,则传输长度为L的数据帧所需时间可表示为

其中,tov为固定冗余开销,包括物理层前导码传输时间、反馈帧信道占用时间、短帧间间隔、分布式协调功能帧间间隔以及平均退避时间.若各站点均严格遵循CSMA/CA的竞争接入机制,则可保证接入信道的概率完全一致,最终实现各站点之间的吞吐率公平.定义饱和状态下,各个站点均接入一次信道,其时间总和为)

在该时间段T内,吞吐率公平条件下总共传输了N个数据帧,则系统饱和吞吐率为

若采用时间公平机制,各个站点接入信道的时间保持一致,则每个站点所分配的信道时间为T/N,可得到时间段T内系统饱和吞吐率为

比较时间公平与吞吐率公平两种公平机制下,系统饱和吞吐率的比值可表示为

当且仅当t1=t2=…=tN时等式成立,此时也意味着r1=r2=…=rN.由此可知,对于多速率WLAN,时间公平条件下的系统吞吐率性能(S2)将大于吞吐率公平下的系统性能(S1).因此,文中重点研究时间公平性机制,并提出相应的优化算法.

2　基于时间公平的TFRR算法

TFRR算法实现了基于线性可调节时间公平的队列调度机制,集成于MAC软件驱动层,其体系架构如图1所示,主要由4个功能模块组成:队列调度、有效剩余时间更新、延时评估以及线性可调节公平.

图1　TFRR算法体系架构

算法的核心思想是,AP实时统计各目的站点的上/下行数据帧传输的信道占用时间,进而更新其有效剩余时间,并以此作为队列调度的依据,同时结合循环轮询方式,最终可实现站点之间的时间公平性.另外,为保障特定数据流的服务质量(Quality of Service,QoS)性能,增加了延时评估模块,采用动态调节方式更新每次轮询各个目的站点可使用的信道时间资源.而考虑到不同场景的应用需求,增加了线性可调节公平模块,通过配置不同的权衡因子可实现吞吐率公平与时间公平的折中.

该算法以每个独立站点个体为调节粒度,可有效保证站点之间无线信道占用时间的公平性.其中,针对下行UDP/TCP流,AP端会根据各站点的有效信道利用时间,实现对不同目的站点的数据帧缓存队列的主动调度,进而达到下行接入的时间公平性;而针对上行TCP流,AP端通过控制不同站点的TCP反馈帧的调度顺序,间接实现了对不同发送速率站点的TCP流量控制,同样可保证上行接入的时间公平性.

2.1队列调度

TFRR算法实时统计并判断各队列的有效剩余时间,并结合循环轮询机制,实现了高效的队列调度.详细的队列调度流程如图2所示.当各站点队列均处于流量饱和条件下时,TFRR算法使得高速率站点相比于低速率站点可传输更多的数据帧,既保证了站点之间的时间公平性,又提升了系统的吞吐率性能.而在流量非饱和条件下,TFRR算法会将多余的传输机会分配给有需求的站点,以充分利用无线信道资源.

图2　队列调度流程

2.2有效剩余时间更新

有效剩余时间更新涉及3个过程:队列初始化、轮询周期内及轮询周期结束.当站点i通过AP的认证与关联操作后,AP会为该目的站点初始化一个缓存队列,并将其有效剩余时间设置为

其中,Tu为每次轮询各站点的单位服务时间.

在轮询周期k内,AP会实时地统计各个站点所占用的无线信道时间,包含上/下行流量,对应AP端的接收/发送事件,每个数据帧占用的信道时间采用式(1)的计算方式.进而更新接收/发送数据帧所对应站点队列的有效剩余时间,更新过程可表示为

其中,TRX和TTX分别为接收和发送数据帧的信道占用时间.

而轮询周期k结束(RndComplete有效)时,AP会再一次更新所有站点队列的有效剩余时间,即

其中,α为历史残留系数,通常设置α≤1/2,可保证有效剩余时间只受短期内的传输效果影响,且随时间呈指数递减关系;n表示站点i连续队列为空的轮询次数.这就意味着,如果一个站点长时间与AP无任何的数据通信,其有效剩余时间将趋于稳定值Tu.而在流量饱和条件下各站点每轮循环内所获得的调度服务时间将保持一致,实现各站点之间的时间公平.

2.3延时评估

一个数据帧的传输延时主要由两部分组成:排队延时和媒体接入延时.其中,排队延时除了受数据帧到达速率和无线传输速率影响外,不同的队列调度机制也将导致差异化的延时性能.而媒体接入延时是数据帧被成功调度并启动发送开始,直到目的端正确接收为止,该延时主要受网络中的站点数和各站点的传输速率影响.

由此可知,众多影响因素中,队列调度是惟一可供调节且影响着系统的延时性能.因此,TFRR算法增加了延时评估功能模块.该模块根据当前活跃站点数(NSTA)以及各站点的延时限制,选择合适的单位服务时间.在流量饱和条件下,一个完整的轮询周期Tpoll可表示为

一方面,单位服务时间越大,则轮询周期越长,会导致服务间隔增大,影响了特定流量的延时性能;另一方面,单位服务时间越小,则站点每次服务所分配的传输时间越短,降低了MAC层传输效率,尤其是支持11n/ac协议帧聚合功能的站点.综上所述,在保证所有业务流的QoS前提下,理应选择最大的单位服务时间以提高数据帧传输效率.因此,可采用的更新方式为

其中,dmin为所有业务流之中最小的传输延时限制值.

2.4线性可调节公平

时间公平算法通过限制各站点接入信道时间的一致性,避免了多速率网络的性能异常现象,可提高整个系统的吞吐率性能.但这是以减小低速率站点的吞吐率为代价的,在流量饱和情况下会导致低速率站点与高速率站点之间吞吐率性能的极度不公平性.某些应用场景,如机场、咖啡厅等公共场所,将会受益于时间公平算法所带来的性能提升;而有些应用场景,比如应急通信场所,则更倾向于吞吐率公平所能维持的性能稳定性.因此,为适应不同的场景需求,文中采用了线性可调节公平机制.具体调节效果可归纳为

其中,βTFRR为权衡因子,满足0≤βTFRR≤1,表示时间公平与吞吐率公平之间的折中效果,即βTFRR越大,时间公平效果越明显;反之,则吞吐率公平效果就越显著.特别地,当βTFRR=1时,系统将采用TFRR队列调度算法实现完全的时间公平;而当βTFRR=0时,系统则采用基本的RR队列调度算法实现完全的吞吐率公平.

3　NS-3　仿真

3.1仿真系统构建

利用NS-3软件[12]构建了由1个AP和N个STA组成的基础型WLAN网络.每个节点包含了对上层应用、传输控制/网络通信协定(Transmission Control Protocol/Internet Protocol,TCP/IP)协议栈、WLAN网络设备和无线信道等各个层次的精确模拟.为仿真真实场景的上、下行流量特性,采用开/关或泊松分布两种方式产生特定模式的传输控制/用户数据报协议(Transmission Control Protocol/User Datagram Protocol,TCP/UDP)数据流.WLAN网络设备采用802.11a协议,其中间层包含了基本DCF竞争接入机制、队列调度算法和速率自适应等模块.仿真实验中,添加了对FCFS、RR、DTT和TFRR这4种队列调度算法的模型构建及性能仿真.

3.2吞吐率性能与公平性比较

将仿真系统设置为1个AP和10个STA,其中,STA-1～STA-3、STA-4～STA-5、STA-6～STA-7和STA-8～STA-10与AP的距离分别为10 m、40 m、70 m和100 m,对应的稳定传输速率等效于54 Mbit/s、36 Mbit/s、18 Mbit/s和6 Mbit/s.上层UDP协议流量采用泊松分布方式产生,而TCP协议采用了Westwood无线拥塞控制协议.所有的数据帧大小均设置为1 500 B.针对FCFS、RR、DTT和TFRR这4种算法,分别仿真了下行UDP、下行TCP以及上行TCP这3种流量场景.

图3表明了TFRR算法的系统吞吐率性能在3种不同的流量场景下,相比于FCFS算法与RR算法提升了50%～75%;而在上行TCP场景下,相比于DTT算法提升了47%.进一步分析可知,TFRR算法是惟一一个能在3种流量场景下均保持严格时间公平的算法,而FCFS算法与RR算法维持了系统吞吐率公平,DTT算法则仅仅保证了下行流量的时间公平.

图3　上/下行吞吐率性能比较

3.3延时性能分析

为了分析TFRR算法的单位服务时间对各个站点延时性能的影响,基于下行UDP仿真场景,设置STA-1～STA-5速率为54 Mbit/s,STA-6～STA-10速率为6 Mbit/s,并为各站点添加了1.5 Mbit/s的下行UDP流量,此时高速率站点将处于流量非饱和状态,而低速率站点则是流量饱和状态.将参数Tu分别固定为1 ms、3 ms和5 ms,仿真了各站点的吞吐率性能与数据帧传输延时分布情况.结果表明,各站点的吞吐率性能并不受Tu大小的影响,而高速率站点的传输延时会随着Tu的增大而呈线性增加,其传输延时的累积分布函数(Cumulative Distribution Function,CDF)如图4所示.这是由于饱和流量站点的服务周期增加了非饱和流量站点的排队等待延时.因此,实际应用场景下有必要根据式(10)对Tu参数进行约束,既可保证所有站点的延时性能,又尽可能地提高数据传输效率.

图4　TFRR算法的延时分布特性

图5　TFRR算法的线性可调节公平

3.4可调节公平性

针对下行TCP仿真场景,线性地调整权衡因子βTFRR的大小,并依次统计系统的吞吐率性能(S)与公平性系数(Fairness Index,FI)大小,采用Jain公平因子[13]评估系统的公平系数,结果如图5所示.从图5可明显地发现,随着权衡因子的逐渐递增,系统的吞吐率性能呈现线性递增趋势.这是由于权衡因子越大,系统的时间公平性比重越高,有利于提升多速率网络的系统吞吐率性能,而公平性系数与权衡因子也同样近似于线性关系.

3.5移动场景

为模拟真实环境,设置了如图6所示的节点分布及其位置移动场景.其中, STA-1～STA-3和STA-6～STA-8为静止节点,与AP的距离分别为10 m和100 m;STA-4和STA-5为移动节点,以2 m/s的固定速率移动.为比较RR算法、DTT算法和TFRR算法的队列调度性能,系统添加了混合的上、下行TCP流量,仿真效果如图7所示.需要指出的是,在RR算法下各站点的性能变化情况类似于DTT算法的,因此,仅给出了DTT算法与TFRR算法的实时仿真效果.

图6　移动场景的网络拓扑

从图7(a)可知,在混合流量条件下,RR算法或DTT算法并不能很好地保证系统中各站点之间的吞吐率公平或时间公平,而是随着移动场景的改变而起伏变化.而图7(b)则表明,TFRR算法在严格保证各站点接入信道时间一致性的同时,使得各站点的吞吐率性能具备了一定的比例公平性.其中,STA-4随着距离的不断增加导致其吞吐率性能的逐级递减,直至与AP解关联;STA-5在前半段时间内逐渐靠近AP,而在后半段时间内逐渐远离AP,反映在吞吐率性能上则是先逐级递增,然后再逐级递减;STA-2和STA-7的吞吐率性能并不受移动节点的影响,反而会由于STA-4退出网络,活跃站点数的减小,最终使得后半段时间内的吞吐率性能略有提升.

图7(c)则表明了,AP采用TFRR队列调度算法所获得的系统吞吐率性能将远大于RR算法和DTT算法的,这也体现了TFRR算法在真实的混合流量环境下所具有的性能优越性.

4　实测验证

为了验证TFRR算法的可行性,搭建了一个硬件系统测试平台,包含1个AP和2个STA.所有节点均采用集成Atheros的AR5212A无线模块的便携式电脑,移植开源驱动软件Madwifi之后,可支持IEEE 802.11a/b/g协议.速率自适应选择AMRR算法,两个STA的最佳传输速率分别为54 Mbit/s与6 Mbit/s.在AP端实现了RR和TFRR两种队列调度算法,并置于硬件系统中进行实测分析.采用Iperf软件分别测试了RR算法与TFRR算法的饱和UDP与TCP吞吐率性能,实测结果如图8所示.无论是UDP流量,还是TCP流量,RR算法保证了各站点的吞吐率公平,而TFRR算法在时间公平的基础上则是保证了各站点吞吐率性能的比例公平性.这也直接导致了TFRR算法的系统UDP与TCP吞吐率性能相比于RR算法分别提升了107%与96.5%.

5　结束语

针对多速率WLAN网络分析了时间公平条件下的性能优越性,笔者提出了线性可调节时间公平的循环轮询队列调度算法.该算法不仅利用不同速率站点之间的时间公平提升系统的吞吐率性能,又兼顾了数据帧的传输延时限制.同时,针对不同的应用场景需求,还支持线性可调节公平机制,实现了吞吐率公平与时间公平的折中.最后,通过NS-3仿真与硬件系统测试验证了该算法的有效性与可行性.

[1]HEUSSE M,ROUSSEAU F,BERGER S G,et al.Performance Anomaly of 802.11b[C]//Proceedings of IEEE INFOCOM.Piscataway:IEEE,2003:836-843.

[2]GORBENKO A,TARASYUK O,KHARCHENKO V,et al.Estimating Throughput Unfairness in a Mixed Data Rate Wi-Fi Environment[C]//2013 International Conference on Digital Technologies.Piscataway:IEEE,2013:181-184.

[3]YAZICI M A,AKAR N.Running Multiple Instances of the Distributed Coordination Function for Air-time Fairness in Multi-rate WLANs[J].IEEE Transactions on Communications,2013,61(12):5067-5076.

[4]JOSHI T,MUKHERJEE A,YOO Y,et al.Airtime Fairness for IEEE 802.11 Multirate Networks[J].IEEETransactions on Mobile Computing,2008,7(4):513-527.

[5]LIN P,CHOU W,LIN T.Achieving Airtime Fairness of Delaysensitive Applications in Multirate IEEE 802.11 Wireless LANs[J].IEEE Communications Magazine,2011,49(9):169-175.

[6]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.

[7]TARASYUK O,GORBENKO A,KHARCHENKO V,et al.Contention Window Adaptation to Ensure Airtime Consumption Fairness in Multirate Wi-Fi Networks[C]//2014 10th International Conference on Digital Technologies. Piscataway:IEEE,2014:344-349.

[8]HU S P,LI J D,PAN G F.Performance and Fairness Enhancement in IEEE 802.11 WLAN Networks[J].AEUInternational Journal of Electronics and Communications,2014,68(7):667-675.

[9]TAN G,GUTTAG J.Time-based Fairness Improves Performance in Multi-rate WLANs[C]//Proceedings of the Annual Conference on USENIX Annual Technical Conference.Berkeley:USENIX Assoc,2004:269-282.

[10]GARROPPO R G,GIORDANO S,LUCETTI S,et al.Providing Air-time Usage Fairness in IEEE 802.11 Networks with the Deficit Transmission Time(DTT)Scheduler[J].ACM Wireless Networks,2007,13(4):481-495.

[11]SHAPIRA N,HENCINSKI O,SHIRI M,et al.Airtime-aware Scheduling for Wireless Local-area Network:US 0269635[P].2014-09-18.

[12]NS-3 PROJECT.NS-3 Manual[EB/OL].[2015-03-12].http://www.nsnam.org/docs/release/3.19/manual/ns-3-manual.pdf.

[13]JAIN R,DURRESI A,BABIC G.Throughput Fairness Index:an Explanation:ATM Forum/99-0045[R].Columbus: ATM,1999.

(编辑:齐淑娟)

Airtime fairness scheduling algorithm for multi-rate WLANs

PAN Zhipeng,WU Bin,YE Tianchun
(Institute of Microelectronics,Chinese Academy of Sciences,Beijing 100029,China)

The DCF(Distributed Coordination Function)used in the IEEE 802.11 protocol provides equal transmission opportunities to each station,which will lead to the performance anomaly in the multi-rate wireless local area network(WLAN).In this paper,we propose a round-robin queue scheduler based on linear scaling of airtime fairness after a detailed theoretical analysis of throughput fairness and airtime fairness.It counts the accurate channel occupancy time of each station,then adopts round-robin to ensure the airtime fairness,and finally improves the system throughput.According to the quality of service(QoS) of data flows,the proposed algorithm can achieve a compromise between transmission efficiency and delay performance by dynamically updating the polling cycle.Simulation by NS-3 and verification by the hardware system show that the proposed algorithm can effectively improve the system uplink and downlink throughput performance while ensuring per-station airtime fairness.

WLAN;throughput fairness;airtime fairness;queue scheduler;NS-3 simulation

TN925+.93

A

1001-2400(2016)04-0128-07

10.3969/j.issn.1001-2400.2016.04.023

2015-03-31 网络出版时间：2015-10-21

国家科技重大专项资助项目(2013ZX03004007);北京市科技新星计划资助项目(2010B060)

潘志鹏(1988-),男,中国科学院博士研究生,E-mail:panzhipeng@ime.ac.cn.

网络出版地址：http://www.cnki.net/kcms/detail/61.1076.TN.20151021.1046.046.html