《1 前言》

1 前言 　 　

IEEE 802.16e 是移动宽带无线接入标准，该标准后向兼容 IEEE 802.16d [1 , 2] 。它在 2 ~ 6 GHz 的频段内支持低速的移动终端，填补了高速率的无线局域网和高移动性的无线蜂窝通信系统之间的空白。 IEEE 802.16e 支持多种类型的数据业务：UGS ，ERT- VR ，RT-VR ，NRT-VR 和 BE 业务，同时还必须保证用户的服务质量。目前主要通过接纳控制、流量调节、调度以及拥塞控制等方法来保证用户业务的服务质量。其中调度是其核心环节，它可根据不同业务的需要来分配相应的带宽，并可保障业务的时延要求。通常在无线网络中所使用的调度算法都是首先在有线网络中提出来，经过改进后应用到无线网络中的。但无线网络同有线网络相比具有很大的特殊性，例如带宽有限、信道的位置依赖性以及突发的信道误码等。

无线通信中，考虑到对带宽的充分利用，在某一时刻某一业务流所处的信道条件较差，不适合数据传输时，系统应该将该业务流所占用的带宽分配给信道条件好的业务流。为了保证公平性，当该业务流的信道条件变好后，系统应该对该业务流作出补偿。这就是无线调度中的补偿模式。补偿模式是区分各个无线公平调度算法的关键。

近年来出现了一些对无线公平分组调度算法的研究，但大都针对单业务类型和业务流没有最小预约速率的情况[3 , 4] 。在 IEEE 802.16e 中，每个移动端（MS）可同时支持多种业务流，并且在业务流建立时确定业务流传输的最小/最大速率：Vmin / Vmax ，业务流建立后必须保证 Vmin ，ΔV ＝ Vmax－Vmin 为传输速率的可调范围。同时这些算法大多采用 Gilbert- Elliot 模型作为信道模型，即认为信道处于两种状态：可用状态和不可用状态，当调度器分配一个用户使用信道，而该用户的信道处于不可用状态时，它将信道让给其他可传输的用户使用，并且在以后的某个时刻对用户补偿。在这类方法中，因为调制方式固定，所以分配相同的信道时隙就意味着用户得到相同的传输容量。但是在 IEEE 802.16e 中采用的自适应调制方式中，信道传输容量因采用的调制方式的不同而不同，这就是带宽随时隙不均匀分布（ BUDTS ， bandwidth uneven distribution with time slot） [5] 特性。若要实现自适应调制系统下的用户公平性和高的系统吞吐量，需要引入新的无线分组调度算法。

笔者提出了适用于 IEEE 802.16e 的基于最小速率保证的公平调度（MTRFS ， minimum reserved traffic rate based fair scheduling）算法。 MTRFS 算法区分不同的业务类型并可保障业务流的最小预约速率。考虑到无线信道的特殊性，算法中引入了补偿模式，以保障处在较恶劣信道条件下的业务流的最小速率。在满足了业务流的最小速率要求的前提下，算法将剩余的带宽分配给信道条件最好的业务流，以达到整个系统吞吐量的最大化。 IEEE 802.16e 系统中，上行链路的资源管理是其 QoS 问题的核心，故研究上行链路的调度算法。

《2 系统和信道模型 》

2 系统和信道模型 　 　

研究802.16e通信系统的上行链路，它由一个基站和 n 个用户组成，系统带宽为 B 。信道分成长度为 T 的物理帧，上下行各占50 % 。假设基站通过信道状态预测器（CSP ，channel state predictor）预测各用户在下一帧的信道状态，调度器确定下一帧的调制方式以及使用的 MS ，并且通过专门的控制信息（UL- MAP 消息）通知 MS ，MS 收到带宽答复后，基于不同业务流有不同的 QoS 要求，在 MS 侧进行带宽的二次分配。

《2.1 系统模型》

2.1 系统模型

根据 IEEE 802.16e 协议的特点，提出了上行链路调度系统模型，如图 1 所示。 BS 侧收到 MS 发送的 PDU（protocol data unit）后，进行解析，数据送到高层；带宽请求消息送到 BS 调度器，BS 调度器根据带宽申请情况以及信道预测器的预测值，进行带宽的分配（GPSS 方式），进而形成 UL-MAP 消息，在下行链路广播给各个 MS 。 MS 收到 BS 广播的 UL-MAP 消息后，解析出该 MS 的带宽答复值，再由 MS 调度器进行带宽的第二次分配。该 MS 的各业务流根据带宽分配结果进行数据的发送，同时根据各业务流缓存队列里的待发送数据长度向 BS 发送下一帧的带宽申请（带宽的申请基于业务流）。

《图 1》

图 1 系统模型图

Fig.1 System model figure

《2.2 信道模型》

2.2 信道模型

传统的无线分组调度算法一般使用 Gilbert- Elliot 模型来模拟信道状态，参见图 2 。但在自适应调制系统中，由于表征信道质量的参数如 SINR 已经被量化成若干阶，分别对应不同的信道速率，因此采用两态 Gilbert-Elliot 模型已经无法反映移动台信道状态的转移。在自适应调制系统中，某一时刻某一用户所采用的信道模式是根据 SINR 的预测值来确定的。在提出的系统模型中，该过程由信道状态预测器 CSP 来完成。 CSP 根据导频预测用户所占用的信道在第 n 帧的 SINR 值：SINR（n），进而确定第 n 帧使用的调制方式。设｛SINRi ｝M 为系统所使用的 M 种调制方式在一定误比特率约束下的信噪比切换门限，那么当 SINR（n）落在［SINRi， SINRi＋1 ］（1 i M ，SINRM ＋1 ＝∞）时，使用第 i 种调制方式；而当 SINR（n）＜ SINR1 时，不使用信道。设当使用第 i （1 i M）种调制方式时信道处于 i 状态，当不使用信道时信道处于 0 状态，那么信道可以利用有限状态 Markov 过程进行建模[6] 。如图 3 所示，其中 Pi , j 为从 i 到 j 的状态转移概率 0 。

《图 2》

图 2 两态 Gilbert-Elliot 无线信道模型

Fig.2 Two-state Gilbert-Elliot wireless channel model

《图 3》

图 3 多状态 Markov 链模型

Fig.3 Multiple-state Markov chain model

《2.3 公平性与满意度》

2.3 公平性与满意度

公平性是 QoS 性能的一项重要指标。传统的公平性指数[7] 定义为

其中 Vi（t）表示第 i 个 MS 的传输速率，n 为 MS 的个数。但是，在 IEEE 802.16e 中，传统的公平性指数无法描述具有不同吞吐量要求的 MS 间的公平性 [8] 。为此，将公平性指数改为

其中 Vi,min 表示第 i 个 MS 的最小保留速率。显然，0 fairness（t） 1 ，当 fairness（t）＝ 1 时，系统最公平，fairness（t）＝ 0 时，系统最不公平。需要指出的是：所谓公平性，应该是同时处于活动状态的流。因为只有同时处于活动状态的流，才会竞争资源。

为了衡量不同信道条件下的 MS 得到的服务与其期望值之间的关系，定义每个 MS 实际接收到的与其期望得到的吞吐量之比为满意度，即

《3 算法的基本原理 》

3 算法的基本原理 　 　

为了给用户提供公平服务，同时保证业务流的 QoS 性能和系统的吞吐量，应该做到以下几点：

1）对于无信道故障的流保证短期吞吐量公平，对于碰到有限信道故障的流保证长期吞吐量公平。这一点可由调度算法结合接纳控制算法和流量整形来完成，其中调度算法保障有限信道故障流的长期吞吐量公平。

2）支持对时延敏感的流和对差错敏感的流，最好能做到区别调度不同的流。在 IEEE 802.16e 中，实时业务 UGS ，ERT-VR ，RT-VR 对时延敏感，MS 端进行二次分配时，在保障业务流最小预约速率的前提下，对实时业务流应该分配尽可能多的资源。而对于差错敏感的非实时流，采用更可靠的调制和编码方式以降低其差错率。

3） BS 端及时准确地预测出上行链路的信道状态，并根据不同的信道条件区别对待不同的 MS 。在保证其最小预约速率的前提下，让信道条件好的 MS 得到更多的带宽分配。

为了描述的方便，对所用的符号作如下说明： Bmin（i ，j）， Bcom（i ，j）， Bshare（i ，j）分别表示第 i 个MS 的第 j 个业务流分配到的最小带宽、补偿带宽、共享带宽，某个 MS 分配到的带宽为上述三者之和。δ 为带宽分配的最小单位。为第 i 个 MS 的信道利用率。 Vmin（i ，j）为业务流的最小预约速率。 FN 为已经传输的帧数（frame number）。 Bremain 为尚未分配的带宽。 T（i ，j）为 BS 端已经接收到的业务量。为业务流的权重。

BS 端调度器收到各个业务流的带宽申请后分配带宽。为达到上述要求，分为以下 3 部分：

1）对信道处于可用状态的业务流分配该业务流的最小预约速率所需带宽，该值由接入网络时规定的业务流最小预约速率和业务流所处的信道状态决定，即

信道处于不可用状态的业务流暂时不分配带宽，其带宽分配给信道条件好的业务流。

2）如果某些业务流从信道不可用状态中恢复过来并且处于滞后状态，对其进行带宽补偿，带宽补偿值为

若剩余的带宽不足以满足全部滞后业务流的补偿，则优先满足实时性要求高和信道条件好的业务流。补偿的过程是在第一步分配之后进行的，避免了对某些业务流的补偿导致其他正常业务流得不到传输机会，保证了业务流之间的独立性。

3）在完成前两步后，将系统剩余的带宽分配给信道条件最好的业务流，以提高整个系统的吞吐量，即

若带宽资源不够，优先考虑高级别业务。 i′ 表示信道条件最好的 MS 。为此时业务流实际需要的带宽。

BS 调度器完成业务流带宽分配后，将同一个 MS 的业务流的带宽答复相加，得到分配给该 MS 的带宽，通过 UL － MAP 消息传给 MS ，由 MS 进行带宽的二次分配。由于 BS 决策的原因，MS 端接收到的带宽答复可能会小于申请的带宽。基于不同业务不同的 QoS 要求，MS 对带宽重新分配。 MS 端带宽的分配类似于 BS 端的带宽分配，分为 3 部分：

1）分配各个业务流的最小带宽。由于 BS 分配给该 MS 总的带宽可能小于该 MS 各个业务流的最小带宽之和，所以分配最小带宽时优先满足高优先级的业务流。

2）完成第一步后，若还有剩余带宽，对最小传输速率没有得到满足的业务流进行补偿。若剩余的带宽不足以满足全部业务流的补偿，则优先满足实时性要求高和信道条件好的业务流。

3）最后，将剩余的带宽按照各个业务流的权重在业务流之间进行分配。

《4 仿真结果》

4 仿真结果 　 　

仿真参数设置如下：帧长 1 ms ，上下行各占 50 % 。带宽 10 MHz（考虑到系统开销，实际利用带宽为 8 MHz）。信道分 5 个状态，对应的调制方式为不可用、BPSK ，QPSK ，16QAM ，64QAM 。各 MS 的最小预约速率和实际业务流速率以及信道状态见表 1 。业务流 UGS ，ERT-VR ，RT-VR ，NRT-VR 和 BE 的权重分别为 0.5 ，0.5 ，0.4 ，0.2 ，0.1 。仿真时间 10 s ，仿真软件使用 OPNET10.0 。

《表 1》

表 1 MS 参数

Table 1 The MS’s parameters

图 4 是 MTRFS 算法与 Max C/ I 算法和 PF （proportional fair）算法的吞吐量对比。 Max C/ I 算法将带宽分配给信道条件最好的 MS ，是系统吞吐量性能的上限，但是其公平性最差。 PF 算法在业务流之间按照比例分配带宽，具有很好的公平性。由于 MTRFS 算法在满足最小预约速率后会将剩余的带宽分配给信道条件最好的 MS ，比 PF 算法按照比例分配会带来一定的吞吐量增加。因此，由仿真结果可知：MTRFS 算法的吞吐量（平均值）略高于 PF 算法，但都低于 Max C/ I 算法。

《图 4》

图 4 不同算法下的吞吐量性能

Fig.4 Throughput performance in different algorithms

图 5 是信道条件较差的 MS2 在 MTRFS 算法和 PF 算法下的吞吐量对比，该 MS 的最小预约速率为 1.5 Mb/s 。由于 MTRFS 算法提供了补偿模式，在信道变好后对滞后流提供了补偿。其吞吐量曲线在 1.5 Mb/s 上下波动，10 s 仿真时间内吞吐量平均值为 1.503 Mb/s ，其吞吐量的长期公平性得到了保证，而 PF 算法没有进行补偿，吞吐量平均值为 1.097Mb/s ，最小预约速率没有满足，不符合协议的要求。

《图 5》

图 5 不同算法下 MS2 的吞吐量

Fig.5 Throughput of MS2 in different algorithms

图６是 PF 算法与 MTRFS 算法的公平性对比。由于对滞后流引入了补偿模式，MTRFS 算法的公平性能略高于 PF 算法。

《图 6》

图 6 不同算法下的公平性能

Fig.6 Fairness performance in different algorithms

图 7 为 MTRFS 算法对不同信道条件下的 MS 提供的服务与其期望得到的服务之比（定义该比值为满意度）。可以看出，MTRFS 算法区别对待处于不同信道条件下的 MS ，MS 所处的信道条件越好，其得到的服务满意度越高。

《图 7》

图 7 不同信道条件下 MS 接受服务的满意度

Fig.7 Service satisfaction of MS in different channel condition

图８、图９分别表示 MTRFS 算法对实时业务和非实时业务的时延性能。

《图 8》

图 8 实时业务流的时延性能

Fig.8 Latency performance of real-time service flows

《图 9》

图 9 非实时业务流的时延性能

Fig.9 Latency performance of non-real-time service flows

由于实时业务的时延性要求较高，而非实时业务对时延没有明确的要求。因此 MTRFS 算法（主要在 MS 端实现）在确保各个业务流的最小预约速率的前提下，优先发送实时业务。非实时业务的时延较大，主要是因为其实际业务流速率大于最小预约速率（BE 业务没有最小预约速率）。由于其最小速率已经得到满足，并且其典型应用为 FTP ，HTTP ，所以是可以接受的。

《5 结语》

5 结语 　 　

调度是无线通信系统中一个重要的问题。无线信道的突发性错误、自适应调制系统中出现的带宽随时隙不均匀分布特性以及系统对多业务的支持和业务流具有最小预约速率，这些特点使得 IEEE 802.16e 中的调度问题比较困难。 MTRFS 算法充分考虑到这些困难，算法中引入了补偿模式，以保障业务流的最小速率，并且对业务流的补偿不影响正常业务流的数据传输。同时算法区别对待不同的业务类型以实现其 QoS 性能。 MTRFS 算法与 IEEE802.16e 协议很好的结合，具有很强的实用性。