正交频分多址系统中一种面向多业务应用的自适应资源分配算法

朱晓荣罗小琴朱洪波

①(南京邮电大学通信与信息工程学院 南京 210003)

②(东南大学移动通信国家重点实验室 南京 210003)

正交频分多址系统中一种面向多业务应用的自适应资源分配算法

朱晓荣*①②罗小琴①朱洪波①

①(南京邮电大学通信与信息工程学院 南京 210003)

②(东南大学移动通信国家重点实验室 南京 210003)

针对正交频分多址(OFDMA)系统下行链路多业务自适应调度的问题，该文首先以最大化系统吞吐量为优化目标、每种业务的服务质量(QoS)保证为约束条件，建立了一种通用的多业务自适应资源分配模型。为解决此优化问题，提出了一种具体的自适应资源调度算法。该算法对实时业务按照“用户选择最好的信道”的原则分配尽可能少的资源以保证其QoS，对非实时业务把尽可能多的剩余资源按照“信道选择最好的用户”的原则进行分配，充分利用信道资源，提升系统容量。仿真结果表明，该算法保证了下行OFDMA系统吞吐量的同时，在实时业务的延时和丢包率等方面有一定的优越性。

无线通信；资源分配；调度；有效容量；正交频分多址

1 引言

下一代无线通信系统的目标是提供无处不在的无线通信和高质量的无线服务。随着用户对服务的多样性需求，人们往往更关注服务质量(Quality of Service, QoS)保证，而功率、频谱等无线资源以及自适应编码等相关技术的有效利用无疑是提升系统性能的关键。因此，需要联合物理层和链路层等，考虑跨层资源的利用[1]，使用户效用最大化。

正交频分多址(Orthogonal Frequency-Division Multiple Access, OFDMA)技术广泛应用于解决频率选择性衰落，可提供更高、更可靠的数据传输速率，在4G等移动通信系统中有广泛的应用前景。文献[2]针对下行链路多用户OFDMA系统，提出一种基于效用的跨层多业务流(Utility-based Cross-layer Multiple Traffic, UCMT)调度算法，该算法以系统效用函数为跨层最优化问题，然后利用启发式双约束粒子群优化算法找到最佳的资源分配。文献[3]在个人用户速率约束的条件下，基于凸优化理论提出了一种方法使多天线正交频分复用(Multiple InputMultiple Output-Orthogonal Frequency Division Multiplexing, MIMO-OFDM)通信的总发送功率最小化，此方案适用于上行链路和下行链路，但是没有考虑不同服务的QoS要求。文献[4]针对不同业务的QoS要求采用不同的资源分配方法，建立基于社会福利最大化的柔性业务资源分配算法。文献[5]针对正交频分多址/空分多址(OFDMA/SDMA)系统下行链路提出了一种动态优先级自适应的无线资源分配(Adaptive Radio Resource Allocation, ARRA)方案，紧急用户给予较高的优先级，用户的优先级可以逐帧地动态调整。然而，ARRA仅依赖违反QoS要求的剩余时间来调节优先级而没有对实时(Real-Time, RT)服务和非实时(NonReal-Time, NRT)服务给予明确区分。因此，可能导致在高业务流下非实时业务被服务，而实时业务没被服务的概率很高。文献[6]针对下行链路多用户MIMO-OFDM系统提出了一个基于效用吞吐量最大化和复杂度降低(Utility-based Throughput Maximization and Complexity Reduction, U_TMCR)的调度方案，该算法虽然实现灵活，但资源利用率不高，实时业务QoS要求的满足在很大程度上影响了系统性能。而文献[7]研究了OFDMA系统下行链路采用自适应设置用户的优先权门限以调节系统吞吐量的提升和QoS保证要求的折中，实现了负载平衡的资源调度，但是在每调度帧中采用模糊推断算法为每个用户设置调度的优先权，复杂度较高。文献[8]在比例速率约束和最小速率约束条件下，研究了OFDMA系统下行和上行链路的和速率最大算法，提出了一种低复杂度的用户选择子信道的基于信噪比权重的排列方案，并结合注水算法进行功率分配。

本文针对上述问题，以最大化系统吞吐量为优化目标、每种业务的QoS保证为约束条件，首先形成了OFDMA系统一种通用的多业务自适应资源分配的最优化问题。为解决此优化问题，提出了一种具体的自适应资源调度算法。由于衰落、干扰、用户位置等因素的影响，对同一信道，不同的用户有不同的信道增益；而对同一用户，不同的信道其增益也不同。本文定义“最好的信道”为某一用户从众多子信道中选择信道增益最大的那个信道，定义“最好的用户”为某一信道从排队用户中选择信道增益最大的那个用户。该算法的核心思想是：首先对每个用户的业务按照紧急程度值由大到小进行排序，然后对实时业务按照“用户选择最好的信道”的原则分配尽可能少的资源以保证其QoS，对非实时业务把尽可能多的剩余资源按照“信道选择最好的用户”的原则进行分配，充分利用信道资源，提升系统容量。

2 多业务自适应资源分配模型

本文主要考虑OFDMA 系统下行链路，将信道划分为N 个子信道，帧划分为J 个时隙。多业务是指QoS 业务和尽力而为业务(FTP业务)，其中QoS业务包括实时业务(语音业务和视频业务)和非实时业务(HTTP业务)。表1 给出了4 种业务的具体指标要求[9]。来自不同用户的数据形成数据流，不同业务的数据被存储在独立的缓冲区等待资源分配和调度。

表1 4种业务指标要求

本文提出的多业务自适应资源分配模型是设计最优的资源分配方案使得系统的吞吐量最大同时满足每个用户的QoS要求。考虑具有稳定各态历经、时变增益为gk,i的瑞利子信道，参数i(i=1,2,…,N)和k(k=1,2,…,K)分别表示子信道和用户个数，N0是加性高斯白噪声密度。帧长用Tf表示，由J个时隙组成，时隙索引为j。B表示子信道的带宽，表示一帧中的第j个时隙内子信道i上的用户k分配的发送功率。接收的信噪比(SNR)可表示为

注意到式(3)代表了所需要的SNR的近似值，而分配的功率应使得式(1)中的SNR满足式(3)中的最小SNR要求，因此令式(1)中的和式(3)中的相等，可以得

本文定义用户k的吞吐量为该帧中为用户k分配传输的比特数，用Rk表示，即

条件约束：

其中Pmax是每帧分配的最大总功率表示当前帧需要传输的比特数否则用户的QoS要求不能满足，QoS要求对实时业务来说即需要满足最大的包时延容忍度，而对非实时业务来说，需要满足最小的传输速率要求。因此，在每调度帧开始进行设置，其值与用户的QoS要求和排队状态有关。式(7)是基站的功率约束条件，式(8)是QoS要求满足条件。

平时室内要保持空气新鲜流通，相对湿度60%左右；保持宝宝的呼吸道畅通，根据病情给予化痰，及时清除分泌物，必要时给予支气管解痉治疗和氧疗。

由以上的最优化问题可以看出，本文提出的资源分配模型就是设法找到最佳的分配方案{, i=1,2,…,N, k=1,2,…,K, j=1,2,…,J }，使得在式(7)和式(8)两个约束条件下，使式(6)中的系统吞吐量达到最大。该优化问题是典型的非确定性多项式困难问题(NP-Hard)，其最优化解很难得到，因此，本文在第3节中提出了一种启发式调度算法来求解此问题。

3 面向多业务应用的资源调度算法

以最大化系统的吞吐量为优化目标，并保证每种业务的QoS，为了减少复杂度，本文提出了一种面向多业务应用的资源调度(Aimed at the multiservice Application Resource Scheduling, A_ ARS)算法来解决式(6)～式(8)中的最优化问题。该算法的核心思想是：(1)每调度帧中按照“用户选择最好的信道”的原则分配尽可能少的资源以保证时延敏感业务的QoS；(2)把尽可能多的剩余资源按照“信道选择最好的用户”的原则分配给时延非敏感业务，实现信道增益，提升系统容量。本文提出的A_ARS算法包括如下两个步骤。

3.1 基于有效容量的时隙分配

假设用户的业务可以分为3类：RT业务，NRT业务和尽力而为(Best Effort, BE)业务。与NRT和BE业务相比，RT业务具有更高的优先级。RT业务如语音和视频，NRT业务如超文本传输协议HTTP, BE业务如FTP(File Transfer Protocal)。

为了满足RT业务的QoS要求，本文定义用户k的紧急程度值ζk为[11]

其中，wk表示在当前帧的用户k的队头数据包在违反QoS要求前的剩余时间，ck表示用户的优先级系数。由于NRT业务或BE业务不考虑延时要求，因此采用传统的先输入先输出规则。

本文采用基于有效容量[11]的方法推导出每帧中满足实时业务统计性QoS保证的最小时隙数，即保证用户k的QoS分配信道i的最小时隙数{Jk,i}可以通过求解如式(10)所示的最优化问题得到[11]：

3.2 多业务资源调度算法

每帧的多业务调度算法如下：首先，所有的RT业务按照式(9)得到的紧急程度值有序地进行排队，对每个用户按照紧急程度值由大到小进行排序，索引号为k(1,2,…,K), k值越小表示优先级越高。按照优先级为对每个排队的用户k从所有信道中选择“最好的信道”，即最大信道增益的信道i*。然后给用户k分配信道i*上的wk,i*时隙满足QoS要求。在每调度帧中多个用户可以共享信道i*，只要。信道i*中每个帧中的剩余时隙，即将被分配给所有NRT或BE用户中具有最高信道增益的用户。因此，本文提出的多业务自适应资源分配的问题就变成如何找到每帧的时隙数量的集合{wk,i}满足QoS约束下最小化RT业务的信道占用量的问题，即{Jk,i}可以由式(10)得到，式(12)表示QoS约束，式(13)表示分配的时隙数不能超过一帧中的总的时隙数。表示剩余信道资源，可以被NRT或BE业务使用。很明显越小，NRT或BE业务可使用的空闲信道资源越多，因此，最小化也即最大化NRT或 BE业务的可用容量，按照“信道选择最好的用户”的原则从所有的NRT或BE用户中选择具有最高信道增益的用户。然后，基站的最大发送功率减去RT用户分配的总功率所得的剩余功率将被平均分配给NRT或BE用户。

可以看出，式(11)的最小化问题是一个线性规划问题，可以利用单纯形法(simplex)容易地求出解。一旦确定了分配模式{wk,i}，根据文献[11]中的表2，自适应传输模式和相应的传输功率也可确定。

4 性能评估

本文通过仿真实验来评估本文所提出的A_ ARS算法的性能。在仿真中，根据IEEE 802.16B标准[12]，下行链路多用户OFDMA系统中的参数如表2所示。路径损耗模型建模为128.1+37.6 log2(R) dB，其中R为用户到基站的距离(km)。假定阴影衰落的平均值为0，标准差为8 dB。本文假设有4种业务类型：语音，视频，HTTP和FTP。

本文所提出的A_ARS算法将和文献[5]中的ARRA方案和文献[6]中的U_TMCR方案进行比较。在本仿真中，用户数从80变化到480，假定每个用户只有一种业务，每种业务类型用户的数量相等。该系统的业务强度定义为用户总的平均数据速率与最大系统传输速率的比[7,8]。语音、视频、HTTP和FTP到达用户的平均数据速率分别设置为4.8 kbps, 64.0 kbps, 14.5 kbps和88.9 kbps，并且随着用户数量从80变化到480，业务负载则从0.15变化到0.90。

表2 OFDMA系统仿真参数

图1显示了系统吞吐量随业务密度的变化。可以看出，A_ARS方案所获得的吞吐量最大，在业务密度为0.75时，A_ARS的系统吞吐量比ARRA和U_TMCR方案分别提高8.02%和2.34%。这是因为A_ARS方案在实现RT业务QoS要求(基于优先级的资源分配算法)和提高NRT/BE业务的系统吞吐量(基于信道状态的算法)之间取得了平衡。ARRA方案的吞吐量随着业务强度的增加，其增长速度逐渐降低。这是因为在高优先级用户和高信干比用户中，ARRA方案将为高优先级用户分配更多的资源。U_TMCR方案通过最大化总的效用值来调度用户，但是U_TMCR方案为了使RT用户保持完美的丢包率，将比A_ARS方案占用更多的资源，从而也导致了吞吐量增长速度下降。当业务密度较高时，A_ARS方案为满足QoS要求，将给实时业务分配更多的资源，只有很少的资源可以分配给非实时用户，因此导致非实时业务吞吐量下降，所以图1中会出现业务密度为0.75的拐点。此拐点表明，业务强度超过0.75时，必须将更多的资源分配给优先级高的实时用户，以保持其QoS要求。

图2显示了FTP业务的吞吐量随业务强度的关系。从图中可以看出在业务负载小于0.6时，A_ARS方案对FTP吞吐量方面的性能优于其他两种方案，但当业务强度超过0.6时，A_ARS方案的FTP吞吐量将降低。这是因为A_ARS方案使用基于有效容量的时隙分配可以最小化分配给高优先级用户的资源量，从而分配更多的资源给FTP用户。相比之下，其他方案将通过牺牲FTP用户的吞吐量以便分配更多的资源给语音和视频用户，从而保持QoS要求。但在高业务负载时，必须将更多的资源分配给紧急实时用户，以保持其QoS要求。因此，只有很少的资源可以分配给FTP用户。同时也可以看出U_TMCR方案在业务密度为0.6之前一直增长，然后开始下降。这是因为当业务密度较高时，U_TMCR方案为满足QoS要求，将给RT业务分配更多的资源。但是，A_ARS方案的吞吐量下降率要低于U_TMCR方案，这是因为A_ARS方案仅分配最小的资源以保住RT服务的QoS要求，从而把更多的可利用资源分配给FTP用户。因此，可以从图中看到，当业务强度为0.75时，A_ARS和U_TMCR两种方案的吞吐量曲线有一个交点。

图1 系统吞吐量随业务密度的变化关系

图2 FTP用户的平均传输速率与业务强度的关系

图3(a)和图3(b)分别表示语音和视频的丢包率，丢包率要求ε(1%)如图中虚线所示。从图中可以看出，A_ARS算法的语音和视频数据包的丢包率在业务密度小于0.45之前几乎为0，而其他两个方案在业务密度约为0.3时就开始增加了。也可以看出A_ARS方案的语音和视频丢包率在业务密度接近1.0之前都低于1%违反概率要求的丢包率。但是，U_TMCR(ARRA)方案的语音丢包率在业务密度为0.9(0.8)之前都低于违反概率要求的丢包率。而对于视频而言，ARRA方案在业务密度为0.8时丢包率就违反要求，U_TMCR方案在接近1.0时才违反1%的概率要求。这是因为A_ARS方案根据RT业务的紧急程度值来分配资源决定服务的顺序。而ARRA方案的丢包率随着业务密度的增加而增加，这是因为ARRA方案仅根据违反QoS之前的剩余时间来调节用户的优先级，因此，实时用户的优先级可能低于非实时用户的，究其原因是NRT业务通常比RT业务的数据包大。

图4(a)及图4(b)分别显示了语音和视频用户的平均数据包延迟，图中用虚线标出了最大数据包延时Dmax，对于所有的算法，平均数据包延迟都低于延迟要求。同时也可以看出，在大多数情况下，A_ARS算法的时延也低于其他两种算法。这是因为A_ARS算法能够实现最大的系统吞吐量，并且赋予RT用户的优先级高于其他用户的优先级。但是，当用户数量很大时，如业务密度为0.9, A_ARS方案将推迟传输视频数据包而更多的资源为语音数据包传输。因此，A_ARS方案视频业务的延迟大于U_TMCR方案的延时。从图中也可以看出，当业务密度超过0.6时，U_TMCR方案的语音和视频数据包延时低于ARRA方案的延时。这是因为U_TMCR方案中紧急的RT用户有较高的被服务概率，但是ARRA方案中RT用户的紧急数据包的优先级可能小于NRT数据包的优先级。因此，通过图3和图4可以看出，在业务强度小于0.9时，A_ ARS算法对于RT业务在丢包率和延时方面优于其他两个方案。

最后，对A_ARS, U_TMCR和ARRA 3种方案的计算复杂度进行比较。图5表示3个调度方案的计算时间，图中虚线表示帧周期(5 ms)。可以看出3个方案的计算时间都小于帧周期，其中，A_ARS方案的计算时间递增，而U_TMCR和ARRA方案的计算时间在业务密度为0.45之前递增，然后开始下降。当业务密度小于0.65时，A_ARS方案的计算时间小于U_TMCR和ARRA方案的计算时间。这是因为随着业务密度的增加，A_ARS方案搜索更多的可能组合，因此需要更多的计算时间。然而，当业务密度较低时，U_TMCR方案中的CSA和ARRA中的通用函数的优点不明显，需要更多的迭代次数来分配一帧的L个符号。当业务密度较高时，这两种算法能够连续地分配OFDMA符号，因此计算时间降低。

图3 语音用户和视频用户的丢包率与业务强度的关系

图4 语音数据包和视频数据包平均时延

图5 平均计算时间与业务强度的关系

5 结束语

本文针对OFDMA系统下行链路提出了一种多业务自适应资源调度算法，该算法包括两个阶段。第1阶段中，基于有效容量推导出最小的时隙数保证实时业务的QoS，在第2阶段通过多用户分集和频率分集来设计一个简单而有效的调度算法，在保证实时业务QoS的前提下最大化系统的吞吐量。

仿真结果表明，本文所提算法与ARRA和U_TMCR算法相比，在QoS要求保证下，业务密度为0.75时，系统的吞吐量分别提高了8.02%和2.34%。本文所提算法的整体满意度要高于ARRA和U_TMCR算法，这是因为本文所提算法仅分配最少的资源以保证RT业务的QoS，并因此可以为NRT/FTP业务分配更多的可利用资源。此外，在业务强度小于0.65时，本文所提算法的计算时间也低于U_TMCR和ARRA。

[1] Hatoum A, Langar R, Aitsaadi N, et al.. Cluster-based resource management in OFDMA femtocell networks with QoS guarantees[J]. IEEE Transactions on Vehicular Technology, 2014, 63(5): 2378-2391.

[2] Winston W L Ho and Liang Ying-chang. Optimal resource allocation for multiuser MIMO-OFDM systems with user rate constraints[J]. IEEE Transactions on Vehicular Technology, 2009, 58(3): 1190-1203.

[3] Ma Wen-ming, Zhang Hai-jun, Wen Xiang-ming, et al.. Utility-based cross-layer multiple traffic scheduling for MUOFDMA[J]. Advances in Information Sciences and Service Sciences (AISS), 2011, 3(8): 122-131.

[4] 严伟, 朱晓荣, 陈守宁, 等. 基于社会福利最大化的柔性业务资源分配研究[J]. 通信学报, 2013, 34(6): 165-173.

Yan Wei, Zhu Xiao-rong, Chen Shou-ning, et al.. Flexible business resource allocation based on the social welfare maximization[J]. Journal of Communications, 2013, 34(6): 165-173.

[5] Tsai C F, Chang C J, Ren F C, et al.. Adaptive radio resource allocation for downlink OFDMA/SDMA systems with multimedia traffic[J]. IEEE Transactions on Wireless Communications, 2008, 7(5): 1734-1743.

[6] Yen C M, Chang C J, and Wang L C. A Utility-based TMCR scheduling scheme for downlink multiuser MIMO-OFDMA systems[J]. IEEE Transactions on Vehicular Technology, 2010, 59(8): 4105-4114.

[7] Chung Yao-hsing and Chang Chung-ju. A balanced resource scheduling scheme with adaptive priority thresholds for OFDMA downlink systems[J]. IEEE Transactions on Vehicular Technology, 2012, 61(3): 1276-1286.

[8] Chung Wen-ching, Chang Chung-ju, and Wang Li-chun . An intelligent priority resource allocation scheme for LTE-A downlink systems[J]. IEEE Wireless Communications Letters, 2012, 1(3): 241-244.

[9] Marco M and Perez-Neira A I. Efficient margin adaptive scheduling for MIMO-OFDMA systems[J]. IEEE Transactions on Wireless Communications, 2013, 12(1): 278-287.

[10] WiMAX forum. Wimax system evaluation methodology V.1.0[S]. 2007.

[11] 严伟, 朱晓荣, 邵世祥. 下行多业务OFDMA 系统中基于有效容量的资源分配算法研究[J]. 电子与信息学报, 2012, 34(9): 2236-2240.

Yan Wei, Zhu Xiao-rong, and Shao Shi-xiang. In the downlink OFDMA system more business resource allocation algorithm based on the effective capacity study[J]. Journal of Electronics & Information Technology, 2012, 34(9): 2236-2240.

[12] IEEE Standard Std. 802.16-2004. Local and metropolitan area networks-part 16: air interface for fixed broadband wireless access systems[S]. 2004.

朱晓荣： 女，1977年生，博士，副教授，研究方向为泛在无线网络、异构网络、无线传感器网络.

罗小琴： 女，1989年生，硕士生，研究方向为移动互联网.

朱洪波： 男，1956年生，博士，教授，研究方向为移动通信和宽带无线技术.

Adaptive Resource Allocation Scheduling Algorithm for Multi-service Application in OFDMA System

Zhu Xiao-rong①②Luo Xiao-qin①Zhu Hong-bo①

①(College of Telecommunications & Information Engineering, Nanjing University of Posts and Telecommunications, Nanjing 210003, China)

②(National Mobile Communications Research Laboratory, Southeast University, Nanjing 210003, China)

Aimed at the problem of downlink multiservice adaptive scheduling in Orthogonal Frequency-Division Multiple Access (OFDMA) system, a universal model for multiservice adaptive resource allocation is built, which is to maximize system throughput, under the constraints of Quality of Service (QoS) guarantees. In order to resolve this optimization problem, a multiservice adaptive resource scheduling algorithm is proposed. In this algorithm, the real-time service is allocated as little resource as possible to guarantee its QoS by “the user choosing the best channel” whereas the non-real time service is allocated the residual resource by “the channel choosing the best user” to increase the system capacity. The simulation results show that the proposed algorithm can guarantee the throughputs of the downlink OFDMA systems and meanwhile have some advantages in aspects of delay and packet dropping rate of real-time services.

Wireless communication; Resource allocation; Scheduling; Effective capacity; OFDMA

TN92

： A

：1009-5896(2015)06-1298-06

10.11999/JEIT141158

2014-09-04收到，2014-11-18改回

国家自然科学基金(61372125)，国家973计划项目(2013CB329104)和东南大学移动通信国家重点实验室开放研究基金(2013D01)资助课题

*通信作者：朱晓荣 xrzhu @njupt.edu.cn