应用于MIMO-OFDMA下行链路的分组调度算法

《应用于MIMO-OFDMA下行链路的分组调度算法》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

2014年10月北京航空航天大学学报October2014第40卷第10期JournalofBeijingUniversityofAeronauticsandAstronauticsV01．40No．10应用于MIMO．OFDMA下行链路的分组调度算法刘壮李曦纪红(北京邮电大学泛网无线通信教育部重点实验室，北京100876)摘要：提出了一种基于效用函数的应用于多输入多输出正交频分复用接入(MIMO—OFDMA，MuhipleInputMultipleOutput-OrthogonalFrequencyDivisionMultiplexingAccess)系统下行链路的分组调度算法．该算法在调度时不仅考虑物理层的信道状况，还利用基站发送缓冲区的状态信息和用户反馈回来的ARQ(AutomaticRepeat-request)信息来帮助基站做出调度决策．针对系统中多种业务的不同服务质量(QoS，QualityofService)要求，分别设计了其效用函数，并将调度决策问题转化成一个系统总效用函数值最大化问题．同时考虑到实际的长期演进计划(LTE，LongTermEvolution)系统中对子载波共享的限制条件，提出了一种可以降低实际复杂度的启发式算法用于求解该最优化问题．仿真结果表明，该算法不但在保证实时业务用户QoS要求方面要好于传统的调度算法，还能获得较好的系统总容量和丢包率性能．关键词：多输入多输出；正交频分多址；分组调度；反馈时延；效用函数中图分类号：TN91文献标识码：A文章编号：1001-5965(2014)10-1451-06Packetschedulingalgorithmformulti-serviceMIMO-OFDMAdownlinksystemsLiuZhuangLiXiJiHong(KeyLaboratoryofUniversalWirelessCommunications，MinistryofEducation，BeijingUniversityofPostsandTelecommunications，Beijing100876，China)Abstract：Autility．basedpacketschedulingalgorithmwasproposedfordownlinkmultiusermultipleinputmultipleoutput．orthogonalfrequencydivisionmultiplexingaccess(MIMO-OFDMA)systems．Theproposedal-gorithmnotonlyconsideredthechannelconditionofphysicallayer，butalsoutilizedthetransmittingbufferstatusinformationandtheautomaticrepeat-request(ARQ)feedbackinformationtohelpimprovethesystemperformance．Inordertosatisfythedifferentqualitiesofservice(QoS)ofmulti-service，differentutilityfune—tionsweredesignedfordifferenttrafficsandthentheschedulingproblemwasformulatedintoaproblemofoverallsvstemutilitymaximization．Moreover，consideredthelimitsofpracticallongtermevolution(LTE)，aheuristicalgorithmwithlowcomputationalcomplexitywasproposed．ThesimulationresultsshowthattheproposedalgorithmoutperformstheexistingalgorithmsintermsofthesystemthroughputandthepacketlossrateandcanalsoguaranteetheQoSdemandofreal-timetraffic．Keywords：multipleinputmultipleoutput(MIMO)；orthogonalfrequencydivisionmultiplexing(OFDM)；packetscheduling；feedbackdelay；utilityfunction近年来，多输入多输出正交频分复用接入(MIMO．OFDMA，MultipleInputMultipleOutput-OrthogonalFrequencyDivisionMultiplexingAccess)技术作为下一代无线通信系统最重要的候选技术收稿日期：2013—10．30；网络出版时间：2014-05-0616：48；DOI：10．13700／j．bh．1001-5965．2013．0616网络出版地址：WWW．cnki．net／kcms／doi／lO．13700／j．bh．1001-5965．2013．0616．html基金项目：北京高等学校青年英才计划资助项目(YETP0432)；国家863计划资助项目(2012AA01A508)；国家青年科学基金资助项目(61302080)作者简介：刘tt(1989一)，男，陕西榆林人，硕士生，liuzhuan90823@163．com． 1452北京航空航天大学学报已经得到了广泛的研究．MIMO结合OFDMA技术可以获得很高的系统容量并且可以有效地对抗信道的多径效应和频率选择性衰落，但是也引入了一个新的难题，即如何将子载波在频率和空间上高效地分配给移动用户．由于自适应分组调度方案的实现复杂度过高，寻找在MIMO．OFDMA系统中高效的分组调度算法成为了目前研究的热点．MIMO．OFDMA系统中的分组调度算法主要可以分为两种策略：不支持子载波共享和支持子载波共享．第1种策略可以消除子载波中的共信道干扰，这样调度算法的实现也会比较简单¨。1．在第2种策略中，因为被服务用户数量的增加，调度算法的系统容量会明显优于第1种策略∞。4。．在支持子载波共享的策略中，用户间的共信道干扰是其面临的一个主要问题，可采用波束成形技术来解决．迫零波束成形技术(ZFBF，Zero．ForcingBeamforming)是其中最简单的情形∞1．在设计分组调度算法时，一个需要注意的问题是要满足不同类型业务的不同服务质量(QoS，QualityofService)需求．通常来说，实时业务更加注重时延、丢包率等QoS因素，而非实时业务更加注重系统吞吐量等性能的影响．在文献[6]中提出了一种在MIMO．OFDMA下行系统中考虑混合业务的调度算法，它为不同类型的业务分配了固定的优先权值．在文献[7]中提出了一种基于动态优先权的调度方案，它根据业务等待消耗的时间动态地调整用户的优先权．另外，之前讨论都假设基站可得到精确的信道状态，但是当系统处于快时变衰落时，反馈时延可能会导致过时的信道估计信息．文献[8]分析了反馈时延在多用户分集中的影响，文献[9]提出了一种考虑反馈时延影响的自适应调度算法，但不能直接适用于MIMO．OFDMA系统．本文提出了一种基于优先权函数的考虑业务优先级和反馈时延影响的分组调度算法．该算法针对反馈时延引起的信道信息估计失准的情况，引入了用户的自动重传请求(ARQ，AutomaticRepeate-request)反馈信息来帮助基站做出调度判决．另外该算法为不同类型业务设置了相应的优先等级，这可以保证实时业务的QoS需求并且降低系统的丢包率．此外，该算法在设计时考虑到了长期演进计划(LTE，LongTermEvolution)系统中对于子载波共享做出的限制条件，这确保了该算法可以适用于实际的LTE系统．仿真结果表明，提出的调度算法与传统的调度算法相比在系统容量方面可以获得更好的性能，并且可以有效地保证实时业务的QoS需求1系统模型如图1所示，本文考虑一个下行多用户的MIMO．0FDMA系统，该系统包含一个基站和K个活跃的移动用户，基站配有M．根发射天线以及J7、r个子载波，而每个移动用户配有M，根接收天线．在该模型中，总共的活跃用户数目要大于发射天线的数目(K>M．)，因此系统需要在每个子载波上从K个用户中选择l≤肘．个用户来发送数据．在LTE标准中规定，每个子载波最多可以发送4层数据，并且在多用户MIMO发送过程中每个用户在每个子载波上最大支持2层数据发送¨0|．本文假设该系统处于一个快速时变的频率选择性衰落信道的环境下，因此基站会从移动用户端接收到过时的信道质量信息(CQI，ChannelQualityIndicator)估计反馈，这也是本文决定将ARQ反馈信息引人调度决策过程的原因．用户1MTMn．1‘一Io—lMTMn．1刳画墨lMIMO]l画酷F—I衰落信道1用户”一l及别而ll便仪衙l子载波于载波分配CQI及ARQ反馈信息选择l子载波分配l调度判决信息-l子载波分配l发送缓冲区基站发射器状态信息终端接收器图1MIMO．OFDMA下行链路系统Fig．1MIMO·0FDMAdownlinksystem1．1采用ZFBF技术的多用户调度模型在多用户MIMO-OFDMA系统中，每个子载波的信道状况可以使用一个二维矩阵日来表征：日1=[日。，⋯，日^，⋯，日K](1)式中，日1为矩阵日的转置矩阵；日。为用户k的信道响应，日。=[日∽]村．xM，≤≤，日。为用户在发射天线肘。和接收天r线1肘，k间的K脉冲响应．k本文采用多用户天线选择(MAS，MultiuserAntennaSelection)方案来获得MIMO信道上已选择用户的正交性⋯。．这样基站和被选择用户间的虚拟MIMO信道矩阵可以被表示为日1=[日。，⋯，日¨⋯，日肼．]肼．。村．(2)式中日。，是一个M。×1的向量，表示用户k’的被选择天线与基站的发射天线间的脉冲响应．为消除子载波上的用户间干扰，本文决定采用ZFBF技术．子载波上的ZFBF权重矩阵W可 第10期刘壮等：应用于MIMO．OFDMA下行链路的分组调度算法1453以由信道状态矩阵日的广义逆矩阵来表示：W=H“(日日”)。1D(3)式中，D=diag(dl'．一，d。，⋯，d。)为在波束成形下保证发射功率不变的对角矩阵；而日“为矩阵日的共轭转置．对角矩阵的元素d。可以表示为d。=1／√[(日日“)。1]¨(4)文献[12]中已经证明在子载波上对每个已选择用户进行等功率分配可以得到与注水算法相同的性能．因此，在子载波n中用户k在接收天线r上的信噪比可以表示为q—P。。ld：⋯‰^’NM，盯：V7式中，P。。。为系统总的发射功率；而or。为系统的噪声功率．由于发送天线上的信噪比Sn,k,t近似等于s“．，，因此对应数据传输速率可表示为7¨，。=lb(1+p¨，。JsⅢ．。)(6)式中，p础．。代表了在子载波n中为用户k在发射天线t上分配的发送功率．因此可以得到系统总容量的数学表示：KNrc=：∑∑∑_p。，。，。lb(1+p。，。．。S。，。，。)(7)k=】4=1l=1式中P“．。=1代表在子载波n中基站在发射天线t上向用户k分配了信道资源，否则p“．。=0．1．2采用ZFBF技术的多用户调度模型本文中考虑系统为用户提供3种优先等级的业务支持，分别为实时业务(RT，RealTime)、非实时业务(NRT，Non．RealTime)和尽力而为业务(BE，BestEffort)．实时业务具有最高的优先级，其次才是发送非实时业务．不同优先级的业务对于系统性能的要求也各不相同．实时业务对系统时延的要求比较高，数据率要求低，且能容忍一定的误码率．非实时业务由于其具有较高的传输速率要求，并且对系统时延不敏感，所以传输优先级低于实时业务．与之相比，尽力而为业务被服务的优先级最低，并且对系统时延和传输数据速率都没有比较严格的要求．2基于优先权函数的调度算法2．1混合业务调度算法与传统的单一业务MIMO-OFDMA系统不同，支持混合业务的MIMO-OFDMA系统需要同时支持用户不同等级的业务需求，包括具有QoS要求的实时业务、更多注重数据吞吐量的非实时业务以及优先级最低的尽力而为业务．因此，本文调度算法按照不同业务的优先级顺序将每一个调度时间间隔的调度过程分为以下3个步骤．1)实时业务资源调度：系统构造一个基于排队时延的效用函数，然后选择最优用户向其分配资源，直到所有的实时话音业务都被分配到资源．2)非实时业务资源调度：通过构造包含比例公平模块和反馈评估模块的优先权函数，并每次选择最优用户向其分配资源，可以保证公平性的前提下最大化系统的吞吐量．3)尽力而为业务的资源调度：当这时还有资源剩余时，将这些资源分配给信道条件最好的用户的BE业务，以尽可能地提高系统总容量．2．2优先权函数的构造2．2．1实时业务的优先权函数本文假设为每个用户都分配了一个实时业务发送缓存队列．缓存队首包时延与用户最大容忍时延的比值更大的用户会有更高的优先级被选中分配到子载波资源．另外，每个用户的发送缓存队列都有最大长度的限制．因此，队列等待长度与队列最大长度的比值越大的用户将会有越高的调度优先级．综合以上分析情况，本文构造了一个用于满足实时业务QoS需求的优先权函数：‰㈤牡掣(8)工，㈣Lmax阢(t)=t—t。。，(k)(9)式中，耽(t)为用户k在当前调度时刻t的队首包时延；tenter为用户k队首业务数据进入缓存队列的时间戳；￡；(t)为用户k的发送缓存区的队列等待长度；D。。。和Lm．x分别为用户k的实时业务最大容忍时延和发送缓存队列的最大长度．2．2．2非实时业务的优先权函数本文假设系统处于快时变衰落的信道环境下，因此基站由于反馈时延的原因可能会收到过时的信道估计信息．错误的信道估计会使基站收到该用户的否定应答(NACK，NegativeAcknowledgement)反馈急剧上升，因此可以利用基站收到的确认字符(ACK，Acknowledgement)反馈信息来帮助调度器进行调度决策．本文使用t。来表示用户k发送的信道估计信息是否可信，当t。为0时代表该用户的信道估计反馈肯定是过时的，为1时则刚好相反．实际上一个用户很少会处于这两种极端情况，通常来说t。是位于0和1之间的一个数，当基站收到该用户的NACK反馈越多，它的t。值就会越低． 1454北京航空航天大学学报在MIMO．OFDMA系统中，利用空间分集基站在一个子载波上可能会向某个用户同时进行多个发送过程．对于每一个发送过程i，基站会记录它的ARQ反馈信息O。．当基站收到NACK反馈时，Oi被设为0，当收到ACK反馈时Oi被设为1．很明显可以看出，发送过程i是一个伯努利实验z，它的概率分布函数可以表示为工(X=o；)=(P。·t。)q·(1一P。·t。)1。0‘(10)式中P。是每次数据传输预计成功的概率，基站会记录．，个连续时间间隔内接收到的ACK反馈信息，并利用该信息来更新每个用户信道估计信息的可信度．利用最大似然估计(MLE，MaximumLikehoodEstimation)的方法¨引，可以将通过ARQ反馈信息来更新用户k的CQI可信度t；的问题转化为一个最优化问题：1JxMmlax南；Ib(工(叫tt))(11)tI∈[t㈤。，1](12)式中，t。是根据ARQ反馈信息得到的用户k的可信度估计；t枷。是用户k的可信度估计的下限值．在给定Oi的情况下，用户k的可信度t。不会低于在oi中进行成功传输的比例．因此tkmin可以表示为，JxM、／f(∑0i)／(‘，×M)⋯≠⑦‰2{二(13)【(n(1_ps))／2⋯=⑦解决了对应的MLE问题后，基站就可以得到每个用户对应的CQI反馈可信度t。．之后就可以利用该参数去构造非实时业务的优先权函数．2．2．3启发式求解算法最优化的解决方案可以通过穷举搜索的方法来找到，但是这样会导致系统的计算复杂度过高，从而不能应用于实际的系统当中．因此，本文提出了一种启发式算法用于以实际系统可以接受的复杂度来寻找调度问题的次优解．本节给出了本文算法的伪代码描述．在提出的算法中，厂和Sh。分别代表系统中活跃用户和可用子载波的集合，M代表用户k在该调度时刻需要传输的业务数据包的数量．算法的伪代码描述如下．1)设置Jrl=A={1，2，⋯，K}，Sfre。={1，2，⋯，Ⅳ}，吼={1，2，⋯，R，}foreachn．2)寻找(k+，n+，r+)=argmax(U(k，n，kE^，n∈5hc，rE甲“r))．更新信息6(k’，n+，r+)=1，以．=蛾．／{r’}，力=[h∽。。]．3)利用SVD方法计算出矩阵力的lf21：力=UDV*圳Dlo]㈣力1=Null(n)=Vo4)选择k=a。《m．axIh¨。力12．#En寻找r’=argmax(U(k，r，n))，更新信息：6(k’，n+，r’)=1吼。=F*n=啦】5)如果∑8(k’，n+，r)≥2，则设置A=以／{k’}；如果∑∑8(k’，n,r)≥N∽则设置A=以／{k’}，F=F／{k’}．6)如果∑∑8(k，n’，r)≥4，设置s嘛=Sfree／{n+}，A={1，2，⋯，K}，然后返回到步骤2)；否则返回到步骤3)．7)只要满足{Jsh。}≠0和{，}≠0，就重复步骤2)一步骤6)的过程．通过利用多用户天线选择算法和贪婪算法的思想¨引，本文提出的启发式算法的时间复杂度降低到了0(KNR)的程度，这远小于应用穷举式搜索算法所需要的时间复杂度D(∥8)．因此，满足多项式时间复杂度的启发式算法可以满足实际系统的需要．3仿真结果与分析本文使用Matlab软件对MIMO-OFDMA系统进行仿真，仿真采用的系统架构如图1所示，主要仿真参数设置如下：系统中发射天线和接收天线的数目都为4，信道状态使用一个六径的瑞利衰落信道进行建模⋯1．这里假设所有信道都受到快衰落和大尺度衰落的影响，信道的最大时延扩展假设为5斗s，最大多普勒频移为30Hz．在系统中基站总共可用的发射功率为1W，总共可用带宽为1MHz．另外，信道的噪声功率谱密度为一80dB·W／Hz．在仿真中设置基站拥有256个子载波用于调度，系统内等待调度的活跃用户的数目设置为从2个增长到20个． 第10期刘壮等：应用于MIMO．OFDMA下行链路的分组调度算法1455为简单起见，这里假设所有发送缓存区最多可以容纳50个业务数据包．发送缓存区中数据包的到来采用泊松分布来仿真，A指数设为每一时间间隔20个数据包，用户可以容忍的最大数据时延设为30个调度时间间隔．将本文提出的算法与文献[2]中提出的TF算法以及文献[4]中提出的U．TMCR算法应用于仿真系统中进行性能对比．图2为不同调度算法的系统容量仿真结果，可以看出，本文提出的算法与U-TMCR算法的系统容量性能要明显优于文献[2]中提出的TF算法，这是因为本文算法和U．TMCR算法都采用了支持子载波共享的方式．采用子载波共享的方式可以有效地利用MIMO技术空间分集的增益，从而增加了系统中被服务用户的数量，因此可以大幅度地提高系统总容量．从图2中还可以看出，本文算法相比文献[4]提出的U．TMCR算法也有一定程度的提高，这是因为本文算法可以有效地利用用户返回的ARQ信息来帮助基站区分用户反馈的CQI信息是否过时．当用户处于快衰落的信道环境时，基站将会降低为它分配子载波的优先级．当该用户恢复到一个正常的信道状态时，由于采用了比例公平算法的思想，基站会提高为它分配子载波的优先级．这样系统就可以避免因为用户处于快衰落状态而产生过多的无效传输引起的性能恶化．=斧2删饰蹈螺垛用户数目图2系统总容量对比图Fig．2Totalsystemthroughput图3为3种算法的系统丢包率的比较．本文提出的调度算法表现出了较好的丢包率性能，这是因为所提算法同时考虑了物理层信道状况和MAC层中发送缓存区的排队时延．当用户的实时业务数据包的等待时延接近系统的最大容忍时延时，急剧增加的效用优先权值会有利于该用户优先得到调度，从而尽量避免产生丢包．从图3中可以看出，算法的丢包率要明显优于TF算法和U．TMCR算法．另外需要注意的一点是，系统丢包率的降低同样有助于系统获得较高的系统容量，这是因为被丢弃的数据包是无益于系统容量的．褂脚悄霜降用尸数目图3系统平均丢包率对比图Fig．3Systemaveragepacketlossrate图4显示了应用3种不同的调度算法后系统中用户实时业务数据的平均时延性能．从图4中可以明显看出，应用本文算法后的实时业务数据的平均时延性能都要好于另外两种算法，这是因为该算法将业务优先级的区别纳入了算法的调度决策准则之中．考虑到实时业务用户对时延的要求更为苛刻，所以本文算法通过牺牲了一部分非实时业务用户的性能，从而优先保障了实时业务的性能要求，这样可以有效地降低实时业务数据的丢包率和平均时延．{制鲁露斗撩爿翟林用尸数日图4实时业务平均时延对比图Fig．4Averagedelayofreahimetraffic4结论1)本文基于MIMO．OFDMA系统下行链路传输的单小区模型，考虑了信道状态报告的反馈时延效应，该模型与MIMO-OFDMA系统的实际传输模型更加接近．2)本文利用了基站中用户发送缓冲区的状态信息和用户终端反馈回的ARQ信息来帮助系统做出调度决策，并根据实时业务、非实时业务和尽力而为业务不同的QoS需求，分别为其设计了效用函数．仿真结果表明，本文提出的调度算法可以有效提高系统的吞吐量性能并降低实时业务数O 1456北京航空航天大学学报2014年据的丢包率和平均时延．[7]TsaiCF，ChangCJ，RenFC，eta1．Adaptiveradioresourcea1．3)本文提出了该调度算法的一种启发式求1“‘i。“ho。”“1i“。o”DMA75DMAsYs‘emswithmul‘ime。ia解方案，可以使得调度算法的求解降低到多项式蒹热篙三?””Wi”k”C0一”沁砒i0“，时间复杂度的程度，这可以有效地满足实际系统[8]G。h。二y‘s：M。ht。NB．Joi。t。，。luati。。。f。d。。。dfe。db。。k的要求．scheme，scheduli峨andrateadaptationinOFDMAsvstemswithfeedbackdelays[C]／／GlobalCommunicationsConference参考文献(References)(GLOBECOM)．NewYork：IEEE,2012：4566—457l[1]MawMS，SasaseI．ResourceallocationschemeinM1MO．OFD一[9]PelechrinisK，KrishnamurthyP。GkantsidisC．Towardsatrust—MAsystemforuser’sdifferentdatathroughputrequirementsworthyPFschedulerforcellulardatanetworks[C]／／Global[C]／／IEEE2007WirelessCommunicationsandNetworkingCommunicationsConference(GLOBECOM)．NewYork：IEEE，Conference．NewYork：IEEE，2007：1708—17122012：1010—1016[2]DaB，KoCC．ResourceallocationindownlinkM1MO．OFDMA[10]YueGS，PrasadN，RangarajanS．DownlinkmuhiuserMIMOwithproportionalfairness[J]．JournalofCommunications．2009．schedulinginLTEadvancedsystems[C]／／InternationalConfer．4(1)：8—13enceonCommunications．Piscataway，NJ：IEEE．2012：4484一[3]PetermannM，BockelmannC．KammeyerKD．Ona110cation4488strategiesfordynamicMIMO—OFDMAwithmulti．userbeamfoHn．[11]ZhangJH，LiuGY，WangWD．Muhiuserantennaselectioning[C]／／Proceedingsof12thInternationalOFDM．Workshop．In．forzero-forcingbeamformingbasedMIMOOFDMA[C]／／Asia．OWo’07，2007PacificConferenceonCommunications．Piscataway，NJ：IEEE．[4]YenCM，ChangCJ．WangLC．Autility．basedTMCRschedu一2007：107—110lingschemefordownlinkmuhiuserMIMO．OFDMAsystems『J]．[12]LiGQ，LiuH．OntheoptimalityofdownlinkOFDMAMIMOIEEETransactionsonVehicularTechnology，2010，59(8)：4105一systems[C]／／ConferenceRecordoftheThirty-EighthAsilomar4l15ConferenceonSignals，SystemsandComputers．Piscataway．NJ：[5]KimJ，ParkS，LeeJH．eta1．AschedulingalgorithmcombinedIEEE，2004：324—328withzero—forcingbeamformingforamuhiuserMIMOwirelesssys．[13]KaySM．Fundamentalsofstatisticalsignalprocessing：estima．tem[C]／／IEEEVehicularTechnologyConference(2005’Fall)．tiontheory[M]．EnglewoodCliffs，NewJersey：Prentice．Hall．2005：211—2151993：93—95[6]YuJ，caiYM，MaYH，eta1．Across-layerdesignofpacket[14]MurtyKG．Operationsresearch[M]．EnglewoodCliffs，NewschedulingandresourceallocationformuhiuserMIMO．OFDMJersey：Prentice—Hall，1995：113—118systems[C]／／6thInternationalConferenceonInformation．Com．[15]NguyenTD，HanY．AproportionalfairnessalgorithmwithQoSmunicationsandSignalProcessing．Piscataway，NJ：IEEE，2007：provisionindownlinkOFDMAsystems[J]．IEEECommunica．1—5tionsLetters，2006，10(11)：760—762