基于拍卖算法的TD－LTE系统上行资源分配算法

刘 凯，丁 璐，赵建业，刘志敏

（北京大学信息科学技术学院，北京100871）

基于拍卖算法的TD－LTE系统上行资源分配算法

刘 凯，丁 璐，赵建业，刘志敏

（北京大学信息科学技术学院，北京100871）

在LTE上行系统中，用户设备必须在连续的子载波上发送数据，而且易受到邻扇区同频干扰，有效的资源分配是提高系统性能的关键。对上行资源分配相关文献进行分析综述，提出一种基于拍卖的TD－LTE上行系统单扇区及多扇区资源分配算法，并进行了TD－LTE系统级平台仿真验证。仿真结果表明，与传统方法相比，提出的方法可以更为有效地提高系统频谱效率和边缘用户频谱效率，提升了用户QoS。

资源分配；长期演进无线通信系统；上行；拍卖算法；频谱效率

0 引言

3GPP移动通信长期演进（LTE）项目是面向第四代移动通信的技术标准，其演进版本为LTEAdvanced，以正交频分多址（OFDM）和多输入多输出（MIMO）为技术基础，在网络结构、空中接口协议和传输技术上较第三代移动通信系统（3G）有较高的性能提升［1］。资源分配是LTE的关键技术之一，可以有效地提高多用户系统性能［2］，TD－LTE是LTE的时分双工制式。

对于多载波系统的资源分配，文献［3，4］给出了基于拉格朗日松弛的优化算法，可以在多用户频率选择性信道中提高系统吞吐率。然而，LTE上行采用单载波频分多址（SC－FDMA），用户设备（UE）必须使用连续的子载波［5］。文献［6］考虑了多用户资源块（RB）的连续分配问题，并提出了两种启发式算法。文献［7］根据UE在载波上的平均增益，提出了一种平均值增强的贪婪算法。而上述文献主要针对单扇区缺少多扇区上行系统干扰模型。文献［8］提出了在多用户MIMO条件下的调度方法，主要考察了多用户在MIMO上的分配协调。文献［9］在宏基站和家庭式基站组成的异构网络中，提出了跨层干扰控制与资源分配结合的策略，需要依赖对信道质量的准确估计，在TDD系统中延迟问题会大大影响该方法的效果。文献［10］将LTE上行资源分配问题建模成一个集合划分问题，但该文是在扇区间进行干扰消除的基础上进行资源分配的，也没有考虑其他扇区对本扇区带来的干扰。

1 系统和信号模型

1.1 系统模型

考虑一个包含7个六边形小区的LTE上行系统。每个小区分为3个扇区，位于小区中心的eNodeB采用方向性天线对小区各个扇区进行覆盖；每个扇区都占用整个系统带宽B，含有N个均匀分布的UE，如图1所示。

图1 扇区和UE模型

系统中，总带宽B共包含K个子载波，其中每12个子载波组成一个资源块（RB）。如上所述，LTE上行系统规定每个UE必须使用连续的RB，因此，为了使资源分配建模更为简洁明了，将若干个连续RB组成一个RB簇，做为资源分配单元［11］。系统中的所有RB会被分成相等大小的若干个RB簇，RB簇的数目与UE数目相同，每个RB簇所包含的RB数目为系统总RB数目除以UE数目得到的商，每个UE可以并且仅可以分配到其中的一个RB簇。这种方法充分利用了UE在相邻RB之间信道状况变化较小的特点，保证了UE分配到RB的连续性，并且具有实现简单的特点。

1.2 信号模型

根据香农公式，可以将LTE上行第i个扇区的吞吐量Ri表示为：

式中，Bkij为扇区i的第j个UE在RB簇k上的带宽；ηkij是一个取值为0或1的指示变量：如果扇区i的第j个UE占用RB簇k，ηkij就为1，否则为0；SNRiejfkf为扇区i的第j个UE在RB簇k上的等效信噪比（SNR），可以由RB簇内包含的所有子载波的信干噪比（SINR）经过指数有效SIR映射（EESM）算法计算得到［10］：

式中，γkijl为扇区i的第j个UE在RB簇k的第l个子载波kl上的信干噪比SINR，Nk为RB簇k含有的子载波数目，β值与MCS等级相关。γkijl的计算方法为：

2 单扇区资源分配

2.1 数学问题描述

首先仅针对目标扇区进行分析，即在式（4）中，认为扇区干扰的构成量和均为本扇区eNodeB已知的量。因此，扇区中的每个UE在不同RB簇上的对于eNodeB都是已知量。文中资源分配的目标是提高扇区吞吐量，即扇区内所有用户可以传输的总比特数。因此，第i个扇区的资源分配问题可以表示为：

2.2 基于拍卖的单扇区资源分配算法

拍卖算法最早由D.P.Bertsekas提出，通过模仿现实中的拍卖过程，可以有效地解决一对一分配问题［14］。假设有N个人和N个物品，并且第j个人得到第k个物品可以获得的增益为vkj，一对一分配问题的目标就是把人和物品匹配起来，从而使所有人获得的总增益最大。拍卖算法可以用低复杂度的方法来解决这一问题。它模拟了一个竞争投标的过程，在这个过程中，没有得到分配的人会不断提高他们的叫价，为这些物品竞标，物品会分配给叫价最高的人。在这里假设一个正值ε（称为补松弛）和物品的价格向量{pk，k=1，…N}，对第j个人而言，如果分配到物kj后可以获得的利润（好处减去出价）与所有分配方案中能得到的最优利润之差的绝对值不大于ε，即满足补松弛条件，那么这个人就是满意的。拍卖算法通过迭代的方法，不断地将物品分配给人，直到每个人都满意。

根据一对一分配问题的建模方法，可以将上行资源分配问题抽象为：系统中有N个UE和N个RB簇，并且第j个UE在第k个RB簇上可以获得的增益为vkj，资源分配的目标就是把UE和RB簇匹配起来，使所有UE获得的总增益最大。其中增益参数vkj设为：该UE在该RB簇上的SNRjekff对应的MCS等级下可传输的比特数，即对应式（5）中的f（SNRiejfk

f）。还需要注意的是，LTE上行系统采用非自适应重传［13］，即传输失败的用户使用与前一次传输相同的资源和MCS等级进行重传。因此在LTE系统中实现拍卖算法时，需要首先剔除这部分已经得到分配的重传UE和对应的RB簇，再在剩余的没有分配的新传UE和RB簇中通过拍卖算法得到最优解。应用考虑重传的拍卖算法解决单扇区资源分配问题的具体过程描述如下：

第1步：初始化。

①选定一个ε＞0；

②认为所有N个UE都不满意；

③设pk=0，k=1，…N。

第2步：针对非自适应重传UE的处理。

对于每个重传UE jre，把该UE在用于其上次传输的RB簇kjre上对应的增益参数vjrekjre设为一个极大值，并把该UE在其他RB簇k≠kjre上的增益参数vjrek设为0，使重传用户jre在拍卖算法的迭代中会一直选择kjre为最优的传输RB簇。

迭代过程：

①选择一个不满意的UE j，计算他可以获得的最大利润γjkj和得到最大利润时分配到的RB簇kj：

以及他的第二大的利润δjk^j和得到第二大利润时分配到的RB簇^kj：

②把第kj个RB簇分给第j个UE。如果这个RB簇在之前已经被分配给另一个UE j－，则取消之前给第j－个UE的分配；如果第j个UE在分配到第kj个RB簇之前已经被分配了第k－j个RB簇，则把第k－

j个RB簇分配给第j－个UE。

③更新第kj个RB簇的pkj：

④把第j个UE设为满意。通过判断是否满足补松弛条件，决定第j－个UE是否满意。

第3步：迭代终止条件：所有UE都满意。

这一方法充分地利用了UE在系统带宽上的频率选择性。UE的MCS等级由UE在这个RB簇上的信道状况决定，信道越好，可用的MCS等级越高，同时UE可以选择系统带宽上的任意一个RB簇使用，而由于信道的频率选择性。拍卖算法充分利用了UE在不同RB簇上MCS等级差别，为每个UE选择合适的RB簇，从而使系统总体可以传输的比特数最高，也因此使每个UE偏向于使用频带上MCS等级高的RB簇。

3 多扇区资源分配

3.1 问题模型

在实际的LTE上行系统中，多个扇区同时进行相互独立的资源调度，可以直接对每个扇区独立应用2.2节中提出的单扇区资源分配算法得到单扇区的最优解，再将各扇区的优化结果联合起来得到多扇区的资源分配方案。而对某个扇区而言，其他扇区干扰无法预知，即式（4）中的和不确定。同时每个扇区并不知道相邻扇区的资源分配结果。时变性导致测量的信道状况（即等效SNR）在实际发送时发生很大变化。表1为在城市宏蜂窝（UMa）场景下不同MCS等级下RB的平均传输成功率。可以看出，在扇区间同频干扰存在时，RB的传输成功率会随MCS等级的增加而不断减小，频谱效率无法得到有效提高。

表1 不同MCS等级下RB块的平均传输成功率

3.2 多扇区资源分配算法

针对多扇区系统直接应用第2.2节算法存在的问题，提出了一种适用于多扇区干扰不确定情况下的改进算法，通过在每个扇区的eNodeB端对每次的传输结果进行统计分析，以优化拍卖算法参数的方法实现性能的提升。

在之前的讨论中，任意一个扇区的第j个UE在第k个RB簇上拍卖算法的增益参数vkj设定为由信道状况决定的MCS等级对应的可传输的比特数。考虑到多扇区资源分配时扇区间干扰不确定的情况会导致不同MCS等级下RB传输成功率的不同，本文将增益参数修正为可以正确传输的比特数的期望，表示为：

式中，rp为该UE在该RB簇上使用的MCS等级p对应的RB传输成功率，它可以通过“学习”的方法得到：eNodeB会为每一个UE记录其在不同MCS等级下的传输情况，初始化认为在每个MCS等级下传输成功率都为1，然后eNodeB根据每次接收UE数据是否成功和UE传输使用的MCS等级情况，逐步得到系统在不同MCS等级下的RB传输成功率统计。这种方法可以使用于传输情况未知的系统，移植性好。

本文的多扇区资源分配算法中，每个扇区的eNodeB资源分配的具体步骤如下：

第1步：eNodeB根据本扇区各UE在整个带宽的RB簇上周期性发送的SRS信号进行上行信道估计的SNR大小决定UE在这些RB簇上的MCS等级，并根据MCS等级和RB簇的大小计算UE可以传输的比特数，记为vjk。

第2步：eNodeB根据本扇区各UE最近一次上行传输的情况，记录其MCS等级和传输成功情况，更新不同MCS等级的传输成功率。设UE最近一次MCS等级为p，在此次传输前eNodeB记录已经使用MCS等级p进行过Ntotal次传输，其中Nsuccess次传输成功。如果此次传输成功，更新Ntotal=Ntotal+1，Nsuccess=Nsuccess+1；否则，仅更新Ntotal=Ntotal+1。同时，MCS等级p的RB传输成功率更新为：

第3步：eNodeB根据式（9），计算出本扇区中的各个UE在不同RB簇上期望成功传输的比特数。

第4步：根据3.2节中给出的考虑重传的拍卖算法的步骤，以第3步得到的值为增益参数进行迭代，得到本扇区进行资源分配的最优解。

以上为各个扇区eNodeB的资源分配过程，将系统中所有扇区的eNodeB的分配过程联合起来，就得到了多扇区系统的分配结果。

4 仿真及结果分析

4.1 仿真条件

建立了TD－LTE系统级仿真平台以验证文中设计的算法性能。UE使用full buffer业务模型，每次传输的大小（比特数）由RB簇中包含的RB数目和MCS等级通过查表［13］决定。

表2为系统仿真参数。其中，单扇区资源分配和多扇区同时进行资源分配的不同在于：在单扇区资源分配方案中，目标扇区在每个调度子帧都进行资源分配，其他扇区的资源分配方案已知。而在多扇区资源分配方案中，扇区都同时进行独立资源分配，其他扇区的资源分配方案未知。仿真中比较本文算法与将每个RB轮流分配给每个用户的轮循算法的扇区频谱效率和UE归一化UE吞吐量（即UE频谱效率）这两个指标。

表2 TD－LTE上行仿真参数

4.2单扇区资源分配仿真结果

表1给出了单扇区情况下基于轮偱和拍卖的资源分配算法的频谱效率。较轮循算法，使用拍卖算法可以使目标扇区的频谱效率提高25％；归一化UE吞吐量累积概率密度（CDF）分布图2表明拍卖算法使UE最大频谱效率和扇区边缘频谱效率（CDF图中5％位置对应的归一化UE吞吐量大小）分别提高20％和25％。单扇区仿真MCS等级数目比例图3反映出拍卖算法较少使用较低的MCS等级（1～5），而是更多地使用较高的MCS等级（11～15），从而充分利用信道的频率选择性来提高系统的频谱效率。

表1 单扇区资源分配的扇区频谱效率

图2 单扇区资源分配的归一归一化UE吞吐量CDF

图3 单扇区所有RB的MCS等级数目比例

4.3 多扇区资源分配仿真结果

表2给出了在多扇区中使用轮循算法、直接应用单扇区拍卖算法和使用多扇区拍卖算法得到的扇区频谱效率，图4给出了这几种算法下的归一化UE吞吐量CDF分布图。使用多扇区拍卖算法相比轮循算法，可以使扇区频谱效率提高30.8％，使UE最大频谱效率和扇区边缘频谱效率分别提高了34.0％ 和33.9％，与直接应用单扇区拍卖算法相比性能得到了很大的提升。图5反映了多扇区拍卖算法一方面继承了拍卖算法对信道频率选择性的充分利用，偏向于选择中等及较高的MCS等级，另一方面考虑到由于干扰的不确定性使等级更高的MCS较难传输成功，在中等及较高的MCS等级中偏向于选择使传输更容易成功的中等的MCS等级，在一定程度上保证了每次传输成功的比特数目，从而在整体上提高了频谱效率。

表2 多扇区系统资源分配的扇区频谱效率

图4 多扇区系统资源分配归一化UE吞吐量CDF

图5 多扇区所有RB的MCS等级数目比例

5 结束语

上行资源分配是LTE系统中的一个重要问题，本文分析了单扇区的资源分配问题，在上行链路非自适应重传的前提下，提出了一种基于拍卖的单扇区资源分配算法。进一步，将这种算法应用于多扇区系统分布式资源分配的环境中，针对因扇区间干扰造成的高等级MCS传输性能下降的问题，提出了一种多扇区资源分配算法。通过系统级仿真验证了算法的性能。结果表明，与传统的轮偱算法相比，本文算法可以提升系统频谱效率与边缘用户频谱效率，这是对QoS的直接改善，同时有效地改善了实际系统存在的丢包率随MCS等级升高而上升的问题。算法具有复杂度较低、不改变现有LTE系统设计的特点。

［1］Astely D，Dahlman E，Furuskar A，et al.LTE：the Evolution of Mobile Broadband［J］.IEEE Communications Magazine，2009，47（4）：44－51.

［2］Fan JC，Yin Q Y，Li G Y，et al.Adaptive Block－level Resource Allocation in OFDMA Networks［J］.IEEE Transactions on Wireless Communications，2011，10（11）：3966－3972.

［3］陈瑾平，李春国，杨绿溪.比例速率约束下OFDMA系统近似最优的资源分配算法［J］.电子与信息学报，2011，33（5）：1147－1153.

［4］Rawi A FAL，Sharif B S，Tsimenidis CC.User Priority A－ware Scheduling and Dynamic Resource Allocation in Orthogonal Frequency Division Multiple Access［J］.IET Communications，2011，5（7）：1006－1019.

［5］Myung H G，Lim J，Goodman D J.Single Carrier FDMA for uplink Wireless Transmission［J］.IEEE Vehicular Technology Magazine，2006，1（3）：30－38.

［6］Chang CH，Chao H L，Liu C L.Sum Throughput－improved Resource Allocation for LTE Uplink Transmission［C］∥IEEE Vehicular Technology Conference（VTC Fall），San Francisco，Sep.2011：1－5.

［7］Nwamadi O，Zhu X，Nandi A K.Enhanced Greedy Algorithm Based Dynamic Subcarrier Allocation for Single Carrier FDMA Systems［C］∥IEEEWireless Communications and Networking Conference（WCNC），Budapest，Hungary，Apr.，2009：1－6.

［8］Prasad N，ZHANG Honghai，ZHU HAO，et al.Multi－User MIMO Scheduling in the Fourth Generation Cellular Uplink［J］.Wireless Communications，IEEE Transactions on，2013，12（9）：4272－4285.

［9］王广德，常永宇，蒋文婷，等.LTE－A异构网络下的高效资源分配算法［J］.无线电通信技术，2013，39（1）：1003－3114.

［10］Wong IC，OteriO，Mccoy W.Optimal Resource Allocation in uplink SC－FDMA System［J］.IEEE Transactions on Wireless Communications，2009，8（5）：2161－2165.

［11］Lim J，Myung H G，Oh K，etal.Channel－dependent Scheduling of Uplink Single Carrier FDMA Systems［C］∥IEEE Vehicular Technology Conference（VTC Fall），Montréal，Canada，Sept.，2006：1－5.

［12］Donthi SN，Mehta N B.An Accurate Model for EESM and its Application to Analysis of CQIFeedback Schemes and Scheduling in LTE［J］.IEEE Transactions on Wireless Communications，2011，10（10）：3436－3448.

［13］3GPP TS 36.213 V9.3.0－2010.Evolved Universal Terrestrial Radio Access（E－UTRA）Physical layer procedures ［S］，2010.

［14］Bertsekas D P.Auction Algorithms for Network Flow Problems：A Tutorial Introduction［J］.Computational Optimization and Applications，1992，1：7－66.

Resource Allocation Algorithm for Up link TD-LTE Based on Auction Algorithm

LIU Kai，DING Lu，ZHAO Jian－ye，LIU Zhi－min
（School of Electronics Engineering and Computer Science，Peking University，Beijing 100871，China）

In LTE uplink systems，the user equipment occupies continuous subcarriers，and one transmission is interfered by inter－sector interference.The efficient resource allocation is important to improve the system performance.Based on analysis and summary for related literature，a resource allocation algorithm for single－sector and multiple－sector systems based on auction algorithm is proposed，which is verified with system－level TD－LTE simulations.The results show that the proposed algorithm outperforms the conventionalmethod，and improves system spectrum efficiency（SE）and SE of cell－edge users，and the QoS for users is improved.

resource allocation；Long Term Evolution（LTE）；uplink；auction algorithm；spectrum efficiency

TN911

A

1003－3114（2015）04－47－5

10.3969/j.issn.1003－3114.2015.04.12

刘 凯，丁 璐，赵建业，等.基于拍卖算法的TD－LTE系统上行资源分配算法［J］.无线电通信技术，2015，41（4）：47－51，73.

2014－12－29

国家高技术研究发展计划（863计划）（2012AA011401）

刘凯（1990―），男，硕士研究生，主要研究方向：无线通信系统、绿色无线通信节能技术。赵建业（1972―），男，教授，博士生导师，主要研究方向：电路与系统、通信技术。