摘 要： 针对IEEE 802.11DCF机制的QoS问题，提出一种新的分布式优先级调度机制。该机制对实时业务使用了不同于普通DCF的后退方法，以较高的概率保证了实时业务访问信道的优先级，同时在实时业务内部采用了一种近似FCFS的调度方式以限制实时业务的最大延迟。
关键词： 服务质量（QoS） IEEE 802.11 DCF 分布式优先级调度
1 设计与实现
IEEE 802.11标准规定的通道访问方式——分布式协调功能(DCF)是一种基于竞争的分布式控制方式。该方式对于所有的业务类型都不区分优先级别，无法控制数据时延，因而不能支持实时业务。现有的基于IEEE802.11DCF的QoS机制中，有一些是通过设定不同的系统参数，采取一定的区分服务机制，来为不同级别的业务提供不同质量的支持。它们主要侧重于在吞吐率和平均延迟方面为实时业务提供优先服务，而对于实时业务的最大延迟限度要求考虑得不够。
本文则是在DCF基础上提出一种分布式优先级调度（Distributed Priority Scheduling，DPS）机制。采用一种新的后退（Backoff）方法来实现区分服务，为实时业务提供吞吐率和平均延迟上的优先级保证。在实时业务内部，DPS机制采用了近似FCFS的调度方式，来解决最大延迟限制问题。DPS机制对实时业务和非实时业务这2个优先级采用了基于竞争的区分方式。而在实时业务和非实时业务内部，DPS机制又分别采用了不同的调度方式。
本文提出的DPS机制在实时业务内部采用了局部的FCFS方式，即在每个数据帧传输期间的局部时间内，保证先到达的数据帧先得到服务。这样做有助于保证每个实时业务流的数据都在最大延迟限度内传送完毕。它不需要在节点间传送附加信息，每个节点只需根据自己的数据帧到达情况决定是否发送数据帧。这样的算法虽然不是严格的FCFS，但能在一定程度上近似达到FCFS在延迟方面较好的效果。与绝对FCFS相比，由于无需在控制帧中携带数据包的优先级信息，因此本文提出的DPS机制在算法上相对简单。此外，DPS机制不需要无线网络各节点统一时钟，实现较简单。与原来的DCF机制相比，该机制并未增加额外的开销，在各种QoS机制中算是一种比较好的选择。
对于非实时业务流，DPS机制采用的调度方式与IEEE 802.11DCF机制基本相同，只是为了进一步保证实时业务流的优先级，而对MAC层进行了改进，并在MAC层上一层的接口队列（Interface Queue，IFQ）也做了一些改动。
2 实时业务流的调度
2.1 局部FCFS调度方式
实时业务流的近似FCFS调度方式建立在IEEE 802.11的CSMA/CA机制基础上。DPS的近似FCFS调度方式如图1所示。节点在发送数据帧之前，首先要侦听信道是否空闲。若信道闲，则该节点在侦听到信道连续空闲DIFS时间后可以发送；若信道忙，则等待到当前的数据帧传输结束后，产生一段后退时间作为后退定时器的初值。之后随着信道的连续空闲，后退定时器的值逐渐减少。如果期间有节点发送数据帧，则其余节点的定时器被冻结，当信道重新空闲DIFS时，后退定时器解冻，后退时间继续减少，直到定时器的值为0，该节点就开始发送数据帧。
要实现近似FCFS的调度顺序，实时业务流后退时间的计算如图2所示。假设tcurr表示无线信道由闲变忙的时刻，即信道上某一数据帧开始传输的时刻，在该数据帧的传输期间，有数据帧A在时刻ta到达某个节点，则数据帧A的后退时间按下式计算：
其中，ρ称为加速因子。若在数据帧A之后又有一个数据帧B在时刻tb到达网络中的某个节点，由于tb>ta，而tcurr和ρ对于数据帧A和数据帧B取值都相同，根据公式（1），有Bb>Ba，即后到达的数据帧B的后退时间会大于先到达的数据帧A的后退时间。从而保证在一个数据帧传输过程中，先到达的数据帧先得到服务。由于数据帧的后退时间仅和它的到达时刻以及它到达时正在传送的数据帧有关，因而算法比较简单，不需要各个无线节点统一时钟，因此适于在无线Ad Hoc网络中应用。
2.2 实时流后退时间的选取
有学者给出了一种迭代算法来估计DCF机制中竞争窗口的平均值。其算法是通过监测一个始终有数据要发送的无线节点，并计算它的平均竞争窗口值来估计整个网络中竞争窗口的平均值。他们还用仿真实验验证了迭代算法的有效性，迭代算法与仿真结果基本相符。本文就是用这种迭代算法来计算平均窗口值。限于篇幅，此处不再赘述。
DPS机制通过后退时间区分方法为实时业务提供吞吐率和平均延迟上的优先级保证，因此需要为实时业务选取较小的后退时间。通过调节公式（1）中的?籽值，把实时流的后退时间调节到大致相当于[0，16]这一后退窗口的范围内。因此，如果网络中有10个非实时业务流，这个后退时间范围就占到了平均竞争窗口的前31％左右，则实时业务优先发送的概率约为70％；如果网络中有50个非实时流，该后退时间范围就占平均竞争窗口的前15％左右，则实时业务优先发送的概率约为85％。
2.3 实时流的碰撞解决
通过仿真实验得到，实时流数据之间的碰撞情况很少，出现的碰撞大部分都发生在实时数据与非实时数据之间以及非实时数据间。于是，在碰撞后要充分考虑实时业务和非实时业务的不同特点，采取有利于提高实时业务竞争力的碰撞机制。
非实时业务(特别是Best-Effort型业务)的传输质量主要为吞吐率，而对延迟的要求不高。然而，对于实时业务来讲，延迟要求相对较严格，超出最大延迟限界的数据无法使用。因此，在DPS机制中，对非实时数据的碰撞仍然采用DCF机制的解决方法，发生碰撞时将竞争窗口翻倍，从而暂时减小它对无线信道的竞争力；而对于实时数据的碰撞提出了新的解决机制，使得实时数据在碰撞后能很快恢复信道的使用权。
在DPS机制中，将碰撞时刻作为该数据的到达时刻，重新按照公式（1）计算后退时间。为避免碰撞双方因后退时间取值相同而再次发生碰撞，用随机函数对后退时间做了随机化处理。
3 非实时业务流的调度
非实时业务流的调度与DCF机制基本相同。但为了进一步保证实时业务的优先级，除了对MAC层进行了上述改进以外，还在MAC层上一层的IFQ做了一点改动。即在每个节点的接口队列处，将实时业务流的数据帧插入到非实时业务流的数据帧之前。这样可以保证每个节点上实时数据优先于非实时数据，从而避免了本地大量的非实时业务的阻塞对实时业务访问信道造成影响。但是，应该注意到，这样做并不能保证某一节点的实时数据优先于其他节点的非实时数据。实时节点间的优先级还是要依靠后退时间区分方法来实现。
4 DPS的性能评价
为验证上述算法的有效性，作者在ns-2上实现了DPS机制并对其性能进行了仿真评价。
4.1 实验环境
所有无线节点都在彼此的传输范围内，组成一个Ad Hoc无线局域网，无线链路速率为2Mbps。用CBR业务代表实时业务，其速率为67.2Kbps，用建立在TCP协议基础上的FTP业务来表示非实时业务，TCP包长为2KB。
仿真实验分别在轻载和重载2种网络环境下进行，以3个FTP背景数据业务表示轻载，12个背景数据业务表示重载。在每种负载情况下，分别做具有0，2，4，……18个实时流的仿真实验，每次仿真运行时间为300秒。
4.2 DPS机制的性能评价
下面从对实时业务的支持和总体QoS性能2个方面来评价DPS机制的性能。
4.2.1 对实时业务的支持
评价DPS机制是否能够为实时业务提供有效的支持，可以从实时业务的端到端平均延迟和延迟分布二方面来考察。
(1)实时业务的端到端平均延迟
端到端平均延迟指的是数据帧从发送方的应用层出发，经过网络传输，最后到达接收方的应用层所经历的平均延迟。在延迟抖动不大的情况下，实时业务的端到端平均延迟能够体现出实时业务的优先级。较小的平均延迟说明实时业务在众多业务流竞争信道的过程中具有优先发送的能力。
观察DPS机制对实时流的端到端平均延迟的改善情况，轻载和重载时端到端平均延迟分别如图3和图4所示。很明显，DPS机制大大降低了实时流的平均延迟，并且数据表明，流平均延迟都不超过400ms。
进一步观察，对比轻载和重载的不同网络环境下的实时流平均延迟。对于DCF机制，平均延迟能够在轻载时随着实时节点数目的增加而增大，而重载时平均延迟基本保持不变。这说明实时流的延迟在很大程度上决定于非实时业务流。也就是说，DCF机制不具备优先发送实时业务的能力。对于DPS机制，轻载和重载下的延迟表现基本一致，这也说明实时流没有受到非实时流的影响，实时流具有较高的优先级。
(2)实时业务的延迟分布
对于有较严格延迟要求的实时业务，超过了最大延迟限度的数据无法再继续使用。因此，DPS机制在后退时间区分机制的基础上，结合了近似FCFS的调度方式，在延迟限度方面给予了更多的考虑。
在仿真实验中，分别在轻载和重载时选取了具有6个实时流的场景，统计出DPS机制中实时数据帧的延迟在各个时间段上的百分比。轻载下86％的实时流延迟小于200ms，重载下88％的实时流延迟小于200ms，即实时流的延迟绝大部分都小于400ms。而实验表明，DCF机制下延迟低于400ms的数据在轻、重载时均超不过总数据量的5％，绝大多数的数据在没有到达接收端时已经失效了。由此说明DPS机制在延迟和延迟限度方面都能够达到很理想的效果。
4.2.2 总体QoS性能
好的调度机制既能够提供实时业务的优先级服务，保证实时业务流之间的公平性，同时也能适当兼顾网络总体的QoS性能，使资源尽可能被充分利用。DCF与DPS机制下的轻载和重载时的信道利用率分别如图5和图6所示。可见，当实时流数目小于10时，DPS机制的信道利用率并没有明显下降。
5 结 论
本文提出了一种新的分布式优先级调度机制，采用新的后退方法来实现区分服务。在实时业务内部，DPS机制采用了近似FCFS的调度方式，来解决最大延迟限制问题和改善公平性。通过仿真实验，可以得出如下结论：DPS机制不但能够为实时业务提供吞吐率和平均延迟上的优先级，还能够保证绝大部分实时数据在最大延迟限度内得到传送，并且在全局QoS和公平性方面也都有出色的表现。
参考文献
1 Barrack C，Siu K Y.A Distributed Scheduling Algorithm for Quality of Service Support in Multiaccess Networks.In：Proceedings of IEEE ICNP′99，1999
2 Kanodia V，Li C，Sabharwal A et al.Ordered Packet Scheduling in Wireless Ad Hoc Networks：Mechanisms and Performance Analysis.In：Proceedings of ACM MOBIHOC，Lausanne，Switzerland，2002
3 Cali F，Conti M，Gregori E.Dynamic Tuning of the IEEE 802.11 Protocol to Achieve a Theoretical Throughput Limit. IEEE/ACM Trans on Networking，2000；8(6)