基于IEEE802.16m的一种改进比例公平调度算法

刘海林，张新有，邢焕来

(西南交通大学信息科学与技术学院，四川成都 610031)

基于IEEE802.16m的一种改进比例公平调度算法

刘海林，张新有，邢焕来

(西南交通大学信息科学与技术学院，四川成都 610031)

比例公平调度算法在系统吞吐量和公平性之间能取得较好的权衡，它在无线网络资源分配中已经成为一个突出的候选方案。但比例公平调度算法本身存在一些缺陷，如无法反映用户的信道状态，没有考虑不同业务的服务质量等。考虑用户的信道状态，针对比例调度算法在分配资源时会抑制不良信道用户的吞吐量，进而影响整个系统的吞吐量的问题，提出了一种改进的比例公平调度算法，以提高IEEE802.16m下行OFDMA系统的吞吐量。该算法根据用户的信道速率将用户分成多个组。先计算每组的调度优先级，然后选择调度优先级最高的组进行调度，最后在选择的组中根据轮询调度算法对用户进行资源分配。仿真结果表明，改进的比例公平调度算法在吞吐量、公平性、时延、丢包率等方面优于传统的比例调度算法。

IEEE802.16m;OFDMA;资源分配;比例公平调度算法

1 概述

全球微波互联接入是互联网市场的一种性能优异的带宽无线接入技术。IEEE802.16m是IEEE802.16e的增强标准［1］。由于正交频分多址(Orthogonal Frequency Division Multiple Access，OFDMA)在宽带无线系统中具有抗多径衰落的能力、灵活的资源分配方式、易与多天线结合、易于扩展带宽等优点，被IEEE802. 16m标准采用作为多址接入方式［2］。

日益增长的带宽需求迫切需要有效地利用IEEE802.16m OFDMA系统中的资源单元(Resource Unit，RU)。在IEEE802.16m下行 OFDMA系统中，RU是基站(Base Station，BS)传输数据到用户的基本单元。在多信道多速率的无线网络中存在各种各样的多载波调度算法，如果总是分配RU给最佳信道的用户以使系统吞吐量最大化，则会导致不良信道的用户饥饿。如果802.16的介质访问控制层协议提供同等的接入概率给所有用户，会导致不良信道的用户占据大部分的通话时间，这样为达到用户吞吐量公平，反而严重降低了系统吞吐量。而比例公平(Proportional Fair，PF)调度算法［3］在公平性和系统吞吐量之间能取得相对比较好的折中，且比较适用于实际系统。但PF调度算法本身存在一些缺陷:如用户的优先级只是根据用户实际需要传输的数据大小来决定，没有考虑用户的信道状态;不同的用户经历的信道状态不同时，用户能获得的数据传输速率也会显示出不公平性，信道状态经历最高变化的用户会得到更高的调度机会。此外，PF调度算法也没有考虑服务时延等。因此，出现了大量基于PF的改进方案，定义了各种基于PF的改进函数。

文献［4-5］在系统可以接受的最低吞吐量的情况下采用比例公平的思想来消除饥饿，该方案实现了用户吞吐量之间的公平性。文献［6-7］结合PF调度算法和储备最小带宽的思想来调度多种业务，取得了更高的吞吐量公平。文献［8］在分配资源时先储备每个业务流的最小带宽请求，然后针对实时业务的服务质量(Quality of Service，QoS)定义了延迟约束和损失概率，提出了比例损失调度算法，最大限度地提高了系统的吞吐量。文献［9］考虑用户的数据包延迟信息，分配最好的资源块给最高分组延迟的用户。该算法只考虑了分组延迟信息这一准则，因此资源块的分配会倾向于不良信道的用户，从而会降低整个系统的吞吐量。文献［10］基于用户的瞬时信道状态和队列长度，针对多载波系统提出了一种跨层的QoS感知的PF调度算法。该算法在系统吞吐量、丢包率和时延方面取得了较好的性能。

这些方案在某些方面都比原来的PF算法有更好的性能，但它们都没有考虑在长时间内提升不良信道用户的吞吐量。在无线网络的某些情况下，如用户从一个良好信道的位置移动到一个不良信道的位置也需要保证其QoS要求。从理论上讲，为了满足不同的QoS要求，基站必须考虑整个系统的状态，然后做出接纳控制决定。PF调度算法在长时间内可以认为分配了相等的通话时间给每个用户。因此，通过PF调度算法来调度会抑制不良信道用户的吞吐量，进而限制整个系统的吞吐量。

针对不良信道的用户会限制整个系统的吞吐量，考虑长时间内用户的信道状态，文中提出一种改进的比例公平(Improved Proportional Fairness，IPF)调度算法，提高IEEE802.16m下行OFDMA系统的吞吐量，同时仍然保持其公平性。

2 OFDMA系统模型

IEEE802.16m支持TDD和FDD两种双工方式。文中采用TDD方式，并以10 M带宽作为研究对象。对类型1子帧来说，其相应的资源单元在频率上有18个连续的子载波，在时域上有6个正交频分复用(Orthogonal Frequency Division Multiplexing，OFDM)符号［11］。RU又分为物理资源单元(Physical Resource U-nit，PRU)和逻辑资源单元(Logical Resource Unit，LRU)。PRU和LRU大小相等，在频域上都是18个子载波，在时域上是6个符号长度。IEEE802.16m将资源在时域和频域上同时进行划分，并以LRU作为最小分配单元。在带宽资源分配中，系统根据相关信息以LRU为单元进行分配，在完成数据分配后需要将LRU映射到PRU中，然后才能发送出去。

下面考虑单蜂窝场景中的 IEEE802.16m下行OFDMA系统，假设所有用户都和一个BS通信。用户估计其瞬时信道状态，并且向BS发送其信道质量指示符［12］。通过信道状态信息，信噪比和误码率，自适应调制编码动态地确定每个用户的瞬时数据传输速率。其中用户的信道状况是随时间变化的。

BS包含一个集中分组调度器，它负责小区内所有用户的带宽资源分配［13］。BS分配无线资源是基于一个基本的时频资源单元(称为RU)。每个RU的确定都可能受到信道状况的影响，但整个RU的发送持续时间保持不变。在每个传输时间间隔(Transmission Time Interval，TTI)，BS调度RU给所有用户。

3 算法描述

3.1 经典比例公平调度算法

IEEE802.16m EMD(Evaluation Methodology Document)文档［14］建议的调度算法就是PF调度算法，因为其综合考虑了优先级、公平性，是调度算法的衡量标准［15］。PF调度算法在分配资源之前先计算各个用户的优先级，在每个传输时刻最先调度优先级最高的用户。假设系统中有M个用户，用户的优先级计算如式(1)所示。

其中，Rk(t)为在t时刻用户k的请求数据传输速率;(t)为在 t时刻截至之前用户 k的平均传输速率。

在t时刻，PF调度算法根据式(2)最先调度优先级最高的用户。

每一次调度完成后，用户k的平均传输速率按式(3)更新，即每个TTI更新一次。

其中，Rck(t)是在t时刻用户k的实际数据传输速率;参数T是滑动时间窗长度，其大小根据调度过程中每个用户闲置的最大时间确定。

PF调度算法流程如图1所示。其中在分配RU的过程中，优先级高的用户优先选择对其具有最大数据传输速率的RU。

每个用户的数据传输速率和其他用户使用的数据传输速率是独立的。由分析可知，PF调度算法是根据当前时刻归一化了的瞬时数据传输速率来选择用户，用户的瞬时数据传输速率在滑动窗口时间T内通过平均传输速率归一化了，所以从长远看每个用户都获得了相等的通话时间。这表明，通过PF调度算法来分配资源，会抑制不良信道用户的吞吐量。因此，不良信道的用户通过PF调度算法来分配资源无疑会限制整个系统的吞吐量。

3.2 改进的比例公平调度算法

为了解决PF调度算法中不良信道用户的吞吐量问题，首先BS根据用户相应的信道瞬时数据传输速率把用户分成不同的组，简化多信道的调度算法，然后导出改进的基于PF调度算法的IPF函数。

首先BS根据用户信道的数据传输速率分成相应的k个区间。在每个TTI，根据用户的信道瞬时数据传输速率把用户分成k个组，把第k组中第一个到达的用户的瞬时数据传输速率作为该组的瞬时数据传输速率Rk(t)。组的数量等于OFDMA系统中可能的数据传输速率集。G={1，2，…，k}表示组集，k表示组号，每个组在t时刻都有一个对应的瞬时数据传输速率Rk(t)。Grk(t)是在t时刻k组的队列长度，即每组的用户数。根据式(4)计算G中各组的优先级。

其中，Rck(t)是在t时刻第k组所有用户的实际数据传输速率之和，没有接受服务的用户，其实际数据传输速率等于0。

αk(t)表示t时刻第k组用户数占总用户数的比例，其计算如式(6)所示。

RUk(t)表示在t时刻截至之前第k组的RU平均使用速率，根据式(7)更新。

在资源分配过程中，一个用户可能被分配多个RU，且分配的RU可能不连续，先选择对该用户具有最大数据传输速率的RU。xk(t，m)表示RU的使用状态，如果RUm被第k组中的用户使用，其值则为1，反之为0。假设每帧中有M个RU，所以xk(t，m)表示t时刻第k组使用的RU数目。

在每个TTI，IPF调度算法根据式(8)选择函数值最大的第k组。

然后从选择的第k组中按照轮询(Round-Robin，RR)调度算法依次分配RU给第k组中的用户，直到所有的RU被分配或者所有的用户都调度完了，最后更新平均速率(t)和RU平均使用速率RUk(t)。

假设所有的用户与BS通信，IPF调度算法流程如图2所示。BS分配RU给每个用户，其中在分配RU的过程中，先调度的用户从未使用的RU中选择对该用户具有最大数据传输速率的RU。

为了提高不良信道用户的吞吐量，IPF调度算法考虑了队列的长度比和RU平均使用速率。此外，在二级调度中使用RR调度算法来提高用户之间的公平性。由分析可知不良信道的用户在队列中需要更多的缓冲区，从而会增加其队列长度比，增加IPF函数的值，增加调度机会，同时IPF调度算法是先以组为单位进行调度，相对剩余的RU也较多，有更多的机会选择较高数据传输速率的RU，所以能提高整个系统的吞吐量。另一方面，当RU平均使用速率较大时，IPF的值会降低，减少了不良信道的用户在下次调度中的机会，以免降低系统的吞吐量。

4 仿真分析

4.1 仿真环境

以IEEE802.16m EMD文档建议的系统参数为仿真参数，在Matlab中进行仿真。假设所有的用户与BS通信，IEEE802.16m OFDMA系统中的无线信道模型服从瑞利分布，文中只考虑下行链路和实时业务。仿真的有关参数设置见表1。

4.2 实验结果分析

文中从公平性、吞吐量、平均时延、丢包率等方面分析改进算法的性能，并且和原算法进行对比。

图3使用Jain Fairness指数比较了IPF调度算法和PF调度算法的公平性。仿真中设置的用户数是50。由Jain Fairness公式可知，公平指数越高，系统的公平性越好。仿真结果显示，公平指数在帧数较多的情况下更接近1。表明在调度开始时，只有部分用户得到了资源调度，还有部分用户没有分配到资源，所以用户公平性较差;在帧数较多的情况下，即随着时间的增加，所有的用户都得到了资源调度，所以用户的公平性趋于稳定。此外，从图3中还可以看出，IPF调度算法公平指数大于PF调度算法。这是因为IPF调度算法在二级调度中使用了RR。RR有较高的公平性，由此取得了更好的公平性。

图3 公平性指数比较

图4显示了系统的吞吐量和帧数的性能。仿真中设置的用户数也是50。如图4所示，IPF调度算法比PF调度算法有更高的系统吞吐量。同时在调度开始时，只有部分用户得到了资源调度，系统吞吐量还不稳定，随着时间的增加，所有的用户都得到了资源调度，系统的吞吐量趋于稳定。主要是因为IPF考虑了队列的长度比以提高不良信道用户的吞吐量，同时IPF调度是先以组为单位进行，剩余的RU相对较多，有更多的机会选择较高数据传输速率的RU。另一方面考虑了RU的平均使用速率，以避免不良信道的用户降低系统的吞吐量。

图5比较了两种调度算法的平均时延。

如图5所示，IPF调度算法和PF调度算法的平均时延分别在用户数为60和30处突然增加。PF调度算法的平均时延快速增加，主要是由于没有考虑不良信道用户的影响。此外也表明IPF调度算法可以容纳比PF调度算法更多的实时业务。

图6比较了两种调度算法的丢包率。

图6 丢包率比较

如图6所示，IPF调度算法的丢包率小于PF调度算法。这是因为IPF调度算法比PF调度算法能容纳更多的实时业务。IPF调度算法和PF调度算法的丢包率在用户数较少时都较低，随着用户数的增加丢包率也增加。这是因为当用户数较少时，系统中有足够的RU来满足用户，用户在较短时间内能够得到调度;随着用户数的增加，系统容量也增加，当系统容量达到最大时，数据包得不到及时传输而被丢弃，从而导致丢包率增大。

5 结束语

为了提高IEEE802.16m下行OFDMA系统中不良信道用户的吞吐量，文中提出一种IPF调度算法。算法根据用户相应的信道数据传输速率把用户分成若干个组，以简化多信道OFDMA系统的调度。此外，算法还综合考虑了瞬时数据传输速率、平均数据传输速率、队列长度比和RU平均使用速率等因素，以提高不良信道用户的吞吐量，从而最大限度地提高系统的吞吐量。仿真结果表明，IPF调度算法在公平性、平均时延、丢包率方面也优于PF调度算法。

［1］ 焦慧颖，董晓鲁.IEEE802.16m标准的最新进展［J］.世界电信，2007，20(11):52-55.

［2］ 杜 滢，方惠英，刘 扬，等.IEEE802.16m宽带无线技术与系统设计［M］.北京:人民邮电出版社，2010.

［3］ 蔡灵灵，赵建立，宋荣方.提供QoS保证的比例公平调度改进算法及其应用［J］.中国电子科学研究院学报，2009，4 (1):67-71.

［4］ Kaneko M，Popovski P，Dahl J.Proportional fairness in multicarrier system with multi-slot frames:upper bound and user multiplexing algorithms［J］.IEEE Transactions on Wireless Communications，2008，7(1):22-26.

［5］ Ruangchaijatupon N，Ji Y.Simple proportional fairness scheduling for OFDMA frame-based wireless systems［C］//Proc of conference on wireless communications and networking.［s. l.］:［s.n.］，2008:1593-1597.

［6］ Ruangchaijatupon N，Yusheng J I.OFDMA resource allocation based on traffic class-oriented optimization［J］.IEICE Transactions on Communications，2009，92(1):93-101.

［7］ Ruangchaijatupon N，Ji Y.Integrated approach to proportionalfair resource allocation for multiclass services in an OFDMA system［C］//Proc of conference on global telecommunications.［s.l.］:［s.n.］，2009:1-6.

［8］ Lee T H，Huang Y W.Resource allocation achieving high system throughput with QoS support in OFDMA-based system ［J］.IEEE Transactions on Communications，2012，60(3):851 -861.

［9］ Sandrasegaran K，Ramli H A M，Basukala R.Delay-prioritized scheduling(DPS)for real time traffic in 3GPP LTE system［C］//Proc of conference on wireless communications and networking.［s.l.］:［s.n.］，2010:1-6.

［10］Kong Z，Kwok Y K，Wang J.A low-complexity QoS-aware proportional fair multicarrier scheduling algorithm for OFDM systems［J］.IEEE Transactions on Vehicular Technology，2009，58(5):2225-2235.

［11］黄志科.IEEE802.16m控制信道的研究［D］.杭州:浙江大学，2012.

［12］王忠侠.基于OFDM的认知无线电资源分配算法研究［D］.长春:吉林大学，2015.

［13］黄高勇.无线多跳中继网络资源分配与调度策略研究［D］.成都:西南交通大学，2014.

［14］ IEEE802.16m Evaluation Methodology Document(EMD) ［EB/OL］.［2009-01-15］.http://grouper.ieee.org/groups/ 802/16/tgm/docs/80216m-08_004r5.zip.

［15］王 瑞.IEEE 802.16m中的协作中继技术研究［D］.北京:北京邮电大学，2009.

An Improved Proportional Fair Scheduling Algorithm Based on IEEE802.16m

LIU Hai-lin，ZHANG Xin-you，XING Huan-lai
(School of Information Science＆Technology，Southwest Jiaotong University，Chengdu 610031，China)

Proportional fair scheduling algorithm can obtain a good tradeoff between system throughput and fairness.It has become an outstanding candidate scheme in wireless networks resource allocation.However，there are some defects in proportional fair scheduling algorithm.For example，it doesn’t reflect the users’channel state and consider the quality of different service.When it comes to the users’channel state，since the proportional scheduling algorithm will inhibit the throughput of the poor channel users，and then affect the overall system throughput.In view of this problem，an improved proportional fairness scheduling algorithm is proposed，which will improve the throughput of IEEE802.16m downlink OFDMA system.According to the users’channel rate，the scheduling algorithm classifies users into several groups.Firstly，the scheduling priority of each group will be calculated.And then the group with the highest scheduling priority will be scheduled.Finally，according to the round-robin scheduling algorithm，resources will be allocated to users in the selected group.The simulation shows that the improved proportional fairness scheduling algorithm is better than the original in terms of throughput，fairness，delay and packet loss rate.

IEEE802.16m;OFDMA;resource allocation;proportional fair scheduling algorithm

TP393.2

:A

1673-629X(2016)09-0158-05

10.3969/j.issn.1673-629X.2016.09.035

2015-12-14

2016-04-07< class="emphasis_bold">网络出版时间:

时间:2016-08-23

国家自然科学基金资助项目(61401374)

刘海林(1989-)，男，硕士，研究方向为无线网络;张新有，副教授，研究方向为网络体系结构、无线网络、嵌入式系统等;邢焕来，副教授，研究方向为SDN、无线网络。

http://www.cnki.net/kcms/detail/61.1450.TP.20160823.1359.058.html