无线接入网络自适应公平调度算法

杨璐，吴清亮

(1. 东南大学 计算机科学与工程学院，江苏 南京 210096；

2. 东南大学 计算机网络和信息集成教育部重点实验室，江苏 南京 210096）

1 引言

在“面向服务”的无线/移动通信系统中，评价一个系统性能好坏的标准并不局限于系统的总服务流量，更重要的是提供给用户的服务满意程度，即对服务提供的质量保障。但是无线网络的核心矛盾是无线资源匮乏以及无线网络结构与带宽的动态特性、大时延、高速移动性等因素对应用服务质量的保障。例如无线网络中链路特性及终端的移动性造成网络资源的动态变化，为无线网络资源管理和分配带来了困难，所以如何有效地动态管理和动态自适应分配网络资源以满足用户对移动性、多元化应用和服务质量保障的需求已成为无线网络亟需解决的问题。

在传统的有线网络中，调度是其中很重要的环节，调度也称动态资源分配，它可根据不同服务需求保障服务的带宽分配，并可保障服务的时延要求。调度算法大都以报文或时隙为单位决定流或报文的发送，主要任务包括2方面：一是决定报文的发送时间（即不同用户报文发送次序），称为分组调度；二是决定不同流或用户应得的资源份额，称为流调度。目前有线网络中已有很多成熟的公平调度算法，包括加权轮循（WRR， weighted round robin）等基于报文结构的算法以及与广义处理器共享（GPS， generalized processor sharing）相关的公平调度算法。但是这些调度算法无法直接应用于无线网络，主要是因为无线信道与有线信道相比具有很大的特殊性，主要表现在无线终端的移动性、无线带宽的时变性和有限性以及无线信道的高误码率。因此无线网络分组调度算法需要结合无线网络链路的特点对调度策略进行调整，所以为了有效地分配无线信道资源和提高系统服务质量(QoS)，无线网络分组调度算法需要考虑下列准则：保证用户之间的公平性；动态适应无线链路的变化；满足特定服务的 QoS 要求；提高系统吞吐量和无线信道利用率；服务质量的平滑过渡和降低系统复杂度等。

最近出现了一些对无线网络调度算法的研究，提出了许多调度算法和时延保障与滞后补偿方式以及再分配模型。文献[1～3]讨论了对不同服务类别采用不同的带宽补偿方式。文献[1]中，仅针对同类别的服务进行带宽补偿，没有考虑非同类别的服务补偿；文献[2]提出了一种自适应的分组调度算法，根据超前流与滞后流的队长极限分别调整其补偿权重，具有优化吞吐率和平滑超前流的服务质量的良好效果；而文献[3]的补偿方式仅是简单地对低级别服务进行惩罚。文献[1～3]中也考虑了通过自适应调整服务类别权重来保障服务的QoS需求。文献[4]综述了一些无线调度算法的研究。

本文提出了一种具有服务区分能力和服务质量保障的二级结构自适应公平调度算法，对剩余带宽进行公平分配，并且确保时延，保障分组队列的服务质量平滑降级。考虑到无线信道的特殊性，算法引入了补偿和再分配模式。其中补偿模式又分为流级和分组级。流级补偿针对滞后流按照其预约速率的固定比例进行补偿，分组级的补偿采用对报文队列进行不同权重的补偿。

2 无线网络二级结构自适应公平调度模型

本文把无线接入网络看作是有线网络的扩展[5]，将它分为2个部分：无线接入部分和有线核心网络。网络按区域划分，每个区域有唯一的基站作为无线接入点，各个区域之间由基站相连。基站和移动终端之间的通信分为上行和下行，由基站统一调度。本文假定一个用户到基站之间的通信为一个报文数据流，各用户与基站的通信是独立的，也就是用户到基站的链路是独立的；同时假定网络存在区分服务机制，在有线网络的边界路由器将进入无线链路的单个服务流按QoS要求分类，聚合成不同的流聚集，聚集信息存储于流聚集每个报文的 DS（different service）标记域中，称为 DSCP（differentiated service code point），流聚集通过DSCP标示自己在调度时根据报文头DSCP提供每跳转发（PHB）服务。

无线网络资源调度算法需要结合其链路的特点对调度策略进行调整。当由于误码或其他原因造成某连接暂时中断，为了对带宽进行充分利用，应考虑将这部分闲置的信道分配给其他连接；而当中断连接恢复传输后，应该对其进行补偿，实现公平性。这种补偿模式正是无线资源调度与有线调度算法的最重要区别。它决定了获得额外带宽的流如何对从中断恢复正常的流进行补偿。本文假设整个网络为无任何链路故障的理想状态，对每个连接对应一个变量flag来区分各个报文数据流的排队状态。通过flag的值将报文数据流分为同步流、超前流和滞后流3种状态[6,7]。

图1是本文提出的无线接入网络二级结构自适应公平调度模型。

图1 无线网络二级结构自适应公平调度模型

该模型由流级的具有服务区分的自适应公平调度和分组级具有服务质量保障的与队列平滑服务的分组调度组成。流级和分组级的补偿都是必须的，流级补偿反映为信道变化时要求重新分配权重，分组级补偿反映为不同的发送时间和队列长度权重分配。流级补偿使用比例方式和归一化的权重分配机制，它能有效地进行服务区分和自适应信道变化，保障无线网络用户之间的长期公平性。而分组级补偿采用公平分组调度和队列权重分配机制。该机制的应用能够保障服务的短期公平性和服务质量，并且有利于保障不同队列服务质量的平滑过渡。

3 无线网络二级结构自适应公平调度算法

根据二级结构的无线网络自适应公平调度模型，本文提出一种无线网络自适应公平调度算法(TWFS, two-level wireless fair scheduling)。

3.1 流调度

定义1 （额外带宽）由于链路故障，基站（调度器）将原报文数据流所占有带宽分配给其他的流。这部分带宽被分配给那些有报文等待的、以可变比特率传输的无差错状态连接，称之为额外带宽[6,7]。

定义2 （时变带宽）如果出现带宽的时变性，即动态容量的变化，使得带宽发生变化，使用归一化权重比例分配机制，称为时变带宽。

本算法按照各个连接的权重对额外带宽和时变带宽进行公平分配，每个可变比特率无差错状态连接所获得的额外带宽正比于它的权重。这里以ri、wn、wb、wl分别表示服务 i、滞后流、超前流和同步流的权重。

当系统有f个流连接时，初始化的权重分配根据服务类型进行比例分配，所以权重的分配即表示了带宽的分配关系，亦即可以反应在不同的发送速率选择上。其所有权重分配如式(1)所示：

当有流完成传输任务或有新的流加入时，要进行权重的再分配以保持公平性。每当有连接状态发生变化时（包括监测到故障恢复）或流传输结束后，其权重归还整个系统。

一般一个流地加入其权重的分配，根据其服务类型分配固定比特率连接权重与可变比特率连接权重： rj= rcj+ rvj。

当流k的链路发生故障时，其归还权重 rk，其他的流对其权重进行公平比例分配。

可变比特率连接权重的更新公式为

当流k恢复转输的时候，由超前流的可变比特率连接权重进行补偿，而同步流和滞后流前期获得的额外服务并不回吐，根据式(3)：

补偿直到该流i成为同步流为止。此时其权重根据其服务类型视同如新流加入一样分配。同时超前流m因流k而获得的额外服务完全补偿完成时或由超前流变成同步流时停止流m对此流的补偿，如果超前流m没有因此流而获得额外服务则不在考虑范围内。

同时，为避免过多的权重计算和减少路由器与端节点重新协商发送速率次数，本文使用一个效用参数即链路的使用效率β，即一段时间内当归还权重少于1-β的时候不进行权重的计算。

3.2 分组调度

TWFS算法的分组级队列调度算法基础采用STFQ[8]和WF2Q[9]2种算法相结合的公平调度策略，原理是：当一个报文到达时，更新其时间标志，每个流均由报文序列组成，流中的报文采用FIFO的顺序，流f的第i个报文 pj的到达时间是A（pj），ff该报文将被分配一个起始标识S（pj）和一个结束f标识F （ pj），如式(4)所示：f

lj是流f的第j个报文的长度，ψ 是流f的ff权；v (t)是时刻t的虚拟时间B(t)为在t时刻所有的准备就绪的流的集合，C (t)为t时刻的信道容量，流的标识为该流中的第一个报文的起始标识。

当一个报文被传输完毕后，下一个报文被选择，所使用的策略如下：

1) 在所有的起始标识小于等于 v(t) +l的流中，选择具有最小结束标识的流；

2) 如果没有这样的流，那么选择带有最小起始标识的流来处理。

在STFQ和WF2Q算法中，其权重值为一固定的值，并不针对队列长度、带宽的变化和QoS需求、排队时延等诸多因素考虑，因此不能很好地自适应于无线网络的动态变化性。但是，由于无线信道的变化与各用户服务传输需求的差异性，调度算法还应该顾及各用户等待传输数据量的情况。在传输“流”的形式数据服务时，信道质量好的用户对应的等待数据量可能较少，仅调度该队列的数据服务在高速无线共享信道上传输就无法充分利用信道资源，造成系统的无线信道利用率降低。调度器在使用每个资源单元前可以综合分析信道状态、队列中等待数据量和数据报文传输时延3方面因素对各用户调度优先级的影响来确定资源单元的调度方案。

一种新的同时兼顾数据报文的时延、信道状态变化和各队列中等待数据量对调度方案影响的下行共享信道调度算法。进行流权重的修改，考虑队列长度的影响，平滑降低服务质量。

在文献[4]中不对 3个队列权重更新，其只更新了超前流的权重和滞后流的权重，对同步流保持不变。如果不进行 3个队列权重更新，会出现什么情况呢？3个队列并不进行权重的自适应，会造成其排队队列循环出现大队列的情况，理想的情况是 3个队列比较合理地分配队长，并且逐渐减少滞后流，稳定同步流和超前流队长。

更新3个队列权重值的方法有2种。

方法1 利用3个队列（滞后流、同步流、超前流）的队长比值分配不同的权值。

方法 2 3个队列权重更新可以根据队尾报文的虚时间与QoS时延要求之间的差，这个差与排队时间的比值来决定权值的分配。

本文认为方法1更适合权重值的更新，因为这是一种简单有效的方法，计算量小，更新不会太频繁。为了给滞后流更多的补偿，可以加大超前流的队长极值，尽量使用较小的滞后流的队长阈值。

因此对于分组级队列权重分配如下，设定ψf的时变表达示ψi(t )，根据流i的到达时间判断流所属队列，而后进行权重的分配，其分配公式如下：

至此得到了一种无线网络自适应公平动态资源调度算法，该算法可以对流服务类型进行区分和服务质量保障以及报文队列补偿的平滑流服务质量。

4 仿真实验及结果分析

本文使用的仿真器是ns-2，仿真实验网络的拓扑如图2 所示。节点1至n通过的带宽为10Mbit/s有线链路与节点A相连，而节点B和C则通过带宽为2Mbit/s无线链路连接。

图2 仿真实验网络拓扑结构

通过带宽的时变性与拥塞发生状况下服务质量保障与队列长度变化来考察算法的性能。假设有3服务类 1、2、3，从节点 1、2、3中出来的数据流分别对应3个服务类，也就是说从节点i出来的数据流为服务类i，i=1，2，3。节点A中的缓冲区大小为200kbyte。节点4给出干扰流量。

在实验中，每个服务类包括一个数据流，其分布和分配的带宽如表 1所示。音频（audio）流每20ms发送160byte报文，而视频（video）流每33ms发送8kbyte的报文，其他数据流发送4kbyte报文，而FTP数据流是持续发送的。

表1 实验中的数据流

本文实验中给音频数据流设定的固定比特率权重参数为 0.3，给视频数据流设定固定比特率权重参数0.4，其他数据流的固定比特率权重参数为0.1。

图3显示了各服务类数据流的权重分布。从图3中可以看出，TWFS算法能较好地满足不同服务类型的比例区分。其中权重的随机小幅波动表现了可变比特率权重和队列权重分配以及类型 4的On-off流量影响，当类型4的流进行传输时，发生网络拥塞，TWFS算法能够根据网络拥塞情况实时调节各服务类的比例权重。

图3 权重的变化

同时考察TWFS在带宽的时变性与拥塞发生状况下的比例公平性之外，本实验记录下了这段时间内超前流、同步流、滞后流3个队列长度的变化情况分别如图4和图5所示。

图4 带流队列服务质量平滑的队列长度变化

图5 不带流队列服务质量平滑的队列长度变化

图4 和图5分别显示了带流队列服务质量平滑与不带流队列服务质量平滑的超前流、同步流、滞后流队列长度的变化情况。从图中可以看出，由于TWFS算法采用了流队列服务质量平滑，使得超前流、同步流、滞后流队列长度保持在一个稳定的状态下。而不采用流队列服务质量平滑的队列长度呈现出较大的波动，系统不能有效地平衡网络中的超前流、同步流、滞后流于一个稳定状态。用户的数据流总是在3种状态下来回切换，使得服务质量时好时坏。这种情况下用户服务质量不能得到有效保障，同时也不利于提高网络利用率。

5 结束语

本文首先对无线网络自适应公平调度问题进行了深入分析，在此基础上针对无线网络应用环境提出了一种具有服务区分与服务质量保障的二级结构自适应公平调度模型，然后在该模型的指导下设计出一种无线网络自适应公平动态资源调度算法——TWFS。采用二级结构的自适应补偿调度策略，可以使公平性和自适应性以及QoS确保都得到保障，为无线网络的差异性多服务质量传输提供了可行方案。最后用仿真方法验证了TWFS算法的稳定性、短期公平性和长期公平性。下一步的主要工作是在更复杂的队列模型，如多状态的马尔科夫排队模型中，结合无线网络流量的固有特性如自相似性、短连接性等对调度算法进行研究。

[1] MOORMAN J, LOCKWOOD J, KANG S. Wireless quality of service using multiclass priority fair queuing [EB/OL]. http: //iwander.vlsi.uiuc.edu/wireless/papers/jsac00.ps,2000.

[2] KUOCHEN W, CHIN Y L. A fair scheduling algorithm with adaptive compensation in wireless networks[A]. GLOBECOM’2001[C]. San Antonio, Texas, 2001. 3543-3547.

[3] ECKHARDT D A, STEENKISTE P. Effort-limited fair (ELF) scheduling for wireless networks[A]. INFOCOM’2000[C]. Tel Aviv, Israel,2000. 1097-1106.

[4] CAO Y, LI V. Scheduling algorithms in broad-band wireless networks[J]. Proceedings of the IEEE, 2001, 1: 76-81.

[5] NANDAGOPAL T, LU S, BHARGHAVAN V. A unified architecture for the design and evaluation of wireless fair queueing algorithms[J].Wireless Networks, 2002, 8(2/3): 231-24.

[6] 宋舰, 李乐民. 一种按比例补偿的公平调度算法. 电子与信息学报,2004,26(5):777-782.SONG J, LI L M. Wireless fair scheduling algorithm using proportional compensation mode[J]. Journal of Electronics and Information Technology, 2004,26(5):777-782.

[7] 宋舰, 李乐民. 一种支持服务类别的无线公平调度算法. 电子学报,2004, 32(1): 59-63.SONG J, LI L M. A wireless fair scheduling algorithm supporting CoS[J]. Chinese Journal of Electronics, 2004, 32(1): 59-63.

[8] PAWAN G, HARRICK M V, HAICHEN C. Start-time fair queuing a scheduling algorithm for integrate services packet switching networks[EB/OL]. http://www.acm.org/SIGCOMM, 1996.

[9] JON C R, BENNETT K, HUI Z. WF2Q: Worst - case fair weighted fair queuing [EB/OL]. http:// www1acm1org/ INFOCOM, 1996.