应用分层编码保障组播系统QoS的高效资源分配

引用本文

陈雷, 王洪玉. 应用分层编码保障组播系统QoS的高效资源分配[J]. 北京邮电大学学报, 2014, 37(4): 64-68. 复制到剪切板

CHEN Lei, WANG Hong-yu. Efficient Resource Allocation Based on Layered Coding in Multicast Systems with QoS Guarantee[J]. JOURNAL OF BEIJING UNIVERSITY OF POSTS AND TELECOMMUNICATIONS, 2014, 37(4): 64-68. 复制到剪切板

Permissions

《北京邮电大学学报》编辑部所有

应用分层编码保障组播系统QoS的高效资源分配

陈雷^1,2, 王洪玉²

1. 中国刑事警察学院公安情报学系, 沈阳 110035;
2. 大连理工大学信息与通信工程学院, 辽宁大连 116024

作者简介: 陈雷(1981-), 男, 讲师, 博士, E-mail：chenleikb@gmail.com.

收稿日期: 2013-11-13

基金项目: 国家自然科学基金项目(61172058)；高等学校博士学科点专项科研基金项目(20120041110011)

摘要

在传统的组播策略中, 系统总的吞吐量受限于组播组中最差用户的信道增益.为了克服组播系统吞吐量受限的问题, 采用基于分层编码的组播策略.在保障组内每个用户的服务质量(QoS)的同时, 提出了一个新颖的子载波和比特分配算法, 来最大化整个组播组的吞吐量.在下行的正交频分多址无线组播系统中, 提出了最优资源分配算法.为了减少最优化算法的计算复杂度, 提出了一个2阶段次优化算法.仿真结果显示, 次优化算法的系统功效十分接近最优化算法.次优化算法要远远优于传统的组播策略, 而且还要优于Tian等所提出的算法.

关键词: 组播分层编码资源分配服务质量

中图分类号:TN929.53 文献标志码:A DOI:10.13190/j.jbupt.2014.04.014

Efficient Resource Allocation Based on Layered Coding in Multicast Systems with QoS Guarantee

CHEN Lei^1,2, WANG Hong-yu²

1. Department of Public Security Intelligence, China Criminal Police College, Shenyang 110035, China;
2. Department of Information and Communication Engineering, Dalian University of Technology, Liaoning Dalian 116024, China

Abstract

In conventional multicast scheme (CMS), the total throughput of multicast group is constrained by the user with the worst channel quality. In order to overcome the limited throughput problem, a multicast scheduling was considered based on layered coding. A new subcarrier and bit allocation algorithm is exploited for targeting the maximum throughput of a whole multicast group while at the same time guaranteeing the quality of services (QoS) requirements of all users. The article proposed an optimal resource allocation algorithm in the downlink of OFDMA-based wireless multicast group. A two-phase suboptimal algorithm was proposed as well to reduce the computational complexity. Simulations show that the performance gap between the optimal algorithm and the proposed suboptimal algorithm is quite small. The proposed algorithm significantly outperforms CMS. Moreover, it obtains more throughput than Tian's algorithm.

Key words: multicast layered coding resource allocation quality of service

3GPP在其R6版本中首先提出了多媒体广播和组播服务标准，随后其成为了有代表性的组播广播技术^[1].该标准在传统的组播策略(CMS，conventional multicast scheme)中，为了保证组播组中所有用户能同时正确接收到相同的信息，因此需要基站以信道质量最差的用户所能接收的速率发送信息^[2]，从而导致了系统整体吞吐量的受限.为了解决这个问题，基于分层编码的组播策略被应用到组播传输中.在分层编码传输策略中，原始的组播数据首先被编码成一个基本层和多个增强层.当前，对组播资源分配的研究，多都集中在多个组播组间的动态资源分配问题上.Liu Juan等^[3]讨论了一种资源分配策略，该策略用来最大化所有组播组的整体吞吐量.但是该策略没有考虑组播组间公平的问题.Ngo等^[4]考虑了最大化系统吞吐量与组间公平的问题.Hyungsuk等^[5]考虑了组间公平与用户间公平的2种组播动态资源分配策略.只有少数文献研究了单个组播组内的动态资源分配问题.Tian等^[6]在保证每个用户QoS需求的同时，提出了一个最优的子载波分配算法来最大化系统吞吐量.该算法中每个子载波所能达到的速率是被限制在有限的几个常数值上，而且只采用等功率的分配.

为了克服文献[6]所提出算法的不足，笔者研究了在单组组播系统中，采用基于分层编码的动态子载波和比特分配算法，来保证组播组中每个用户的不同QoS需求.

1 系统模型

考虑下行单组OFDMA组播系统.基站发送组播数据给1个组播组内的每个用户，每个用户的QoS需求不同，如图 1所示.系统总带宽被分为N个子载波，在组播组中有K个用户.假设每个用户反馈瞬时信道信息和QoS需求，通过无差错的反馈信道给基站.用户k在子载波n上的瞬时信道增益可以表示为|h_{k, n}|².基站总功率为P_T，每个子载波n分配的功率为p_n和加载c_nbit.定义R_{k, n}和R_k^req分别表示用户k在子载波n上实际的速率和满足用户k的QoS需求时所需要的速率.定义f(c_n)表示一个用户能够正确接收c_nbit数据时，所需要的接收功率.

图 1 采用分层编码的单组无线组播系统框图

采用精细可伸缩视频编码(FGS)分层编码，在发送端，首先将原始组播数据编码成1个基本层和多个增强层数据.R_base表示基本层速率.定义每个用户QoS的速率R_k^req都大于R_base.最优化问题可以表示为

(1)

满足

(2)

(3)

(4)

(5)

w_{k, n}是0或1，表示用户k是否占用子载波n.如果占用，则w_{k, n}为1，否则为0.式(2) 表示系统总功率受限.式(3) 表示要求满足每个用户的QoS需求.式(4) 表示子载波分配给哪些用户.例如，在MQAM调制时，f(c_n)和R_{k, n}可以表示为

(6)

(7)

其中：p_e为要求的误码率(BER)，N₀/2为加性高斯白噪声的方差，

2 基于FGS分层编码的资源分配2.1 最优化算法

为了将最优化问题中的非线性目标函数转化为线性整数规划问题，并进行遍历求解.假设c_n只能取整数值{0, 1, 2, …, M}，表示单个子载波上所能加载的比特数.f(c_n)={0, f(1), f(2), …, f(M)}，f(0)=0.{f(c_n)}是从式(6) 计算得到的所需接收功率的集合.为了使得f(c_n)为整数变量，定义新的标志γ_{k, n, c}表示第k个用户在第n个子载波上加载的比特数.

(8)

通过使用新的标志将最优化问题转变为整数规划问题

(9)

满足

(10)

(11)

整数规划问题是一种NP-hard问题不易求解并且计算量大.因此，笔者提出了次优化算法.

2.2 次优化的比例公平子载波分配

考虑了一种次优化的算法，该算法分为子载波分配阶段和功率与比特加载阶段.在子载波分配阶段，假设每个子载波被分配有相等的功率p_n=p_T/N.因此最优化问题的式(1)~式(5) 被重新写为

(12)

满足

(13)

(14)

(15)

(16)

首先，通过子载波分配使得所有用户都将获得基本层的数据.其次，将剩余的子载波按每个用户的不同QoS需求分配子载波.最后，对剩余的子载波采用最大化系统吞吐量的方法分配.

1) 基本层算法

① 初始化可以设置B={1, 2, …, K}和A={1, 2, …, N}.，n∈A.如果则转到步骤②，否则，声称要求不能被满足.

② 当A≠∅时找子载波满足

③ 更新R_base=R_base-B_n^*，A=A-{n^*}；如果R_base≤0，则剩余子载波的集合为A^*={1, 2, …}；否则，返回到②.

2) QoS保障算法

子载波的分配需根据用户反馈的信道质量和QoS分配，直到每个用户都满足.因此，提出了一个比例公平的分配公式

(17)

其中：R_k表示用户k实际拥有的速率, 定义PF_k=R_k/R_k^req.

① 初始化可以设置为R₁=R₂=…=R_k=R_base，更新R_k^req=R_k^req－R_base，k∈B.

② 找一个用户满足

③ R_{k^*, 1}, R_{k^*, 2}, …, R_{k^*, n}，n∈A^*将按递减方式排列，例如R_{k^*, l₁}≥R_{k^*, l₂}≥…≥R_{k^*, l_n}；分配子载波l₁给用户k^*，如果l₁没有被使用，则设置c_l₁=R_{k^*, l₁}，并更新R_k^*=R_k^*+c_l₁.否则，如果c_l₁≤R_{k^*, l₁}，则更新R_k^*=R_k^*+c_l₁，A^*=A^*-{l₁}，否则，如果c_l₁＞R_{k^*, l₁}，则将该子载波排除后，返回到③，重新寻找.

④ 如果R_k≥R_k^req，k∈B，则将计算剩余子载波集合为A^**={1, 2, …}.否则，声称要求不能被满足.

3) 增强层算法

增强层算法利用前两步剩余的子载波.该算法用来实现最大化系统吞吐量.定义k_n表示能接收子载波n的用户当中，最差信道增益的用户.T_{k_n, n}是子载波n的吞吐量.

① 初始化可以设置为R_{k, 1}, R_{k, 2}, …, R_{k, n}，k∈B，n∈A^**将按递减次序进行排列，例如R_{1, n}≥ R_{2, n}≥…≥R_{K, n}.

② A^**≠∅时，计算(R_{K, n}≥R_{k_n, n})；并且找到一个用户满足.其中，1(A)表示当A条件满足时，1(A)值为1，否则为0.

③ 设置

2.3 次优化的比特加载和功率分配

子载波分配完，进入比特加载和功率分配.最优化问题的式(1)~式(5) 重新表示为

(18)

满足

(19)

(20)

(21)

(22)

其中u_n是使用子载波n的总用户数.p_n和c_n将通过功率和比特分配算法进行分配.定义Δp_n(c)为在子载波n上增加1 bit数据时所增加的功率.

(23)

(24)

定义k_n是第k个使用子载波n的用户.该用户是使用子载波n的用户中，信道增益最小的.D_n={k|w_{k, n}=1}是使用子载波n的用户集合.算法如下：

① 初始化可以设置为c_n=0，并且为每个子载波计算Δp_n(0)；设置当前总功率为P_T^*=0；

② 找到子载波；

③ 更新；如果P_T^*≥P_T^*，则算法终止；否则更新c_n^*=c_n^*+1；

④ 计算Δp_n^*(c_n^*)，返回②.

3 仿真结果与分析

笔者仿真了提出的最优化算法、次优子载波分配与功率分配算法，并将提出的算法与Tian Lin等^[6]提出的算法和CMS进行了比较.在Tian Lin等^[6]提出的算法中，给每个子载波分配的速率只能从有限的几个常数值中选取，即d_m(m=1, 2, …, M).仿真的场景如图 2所示.仿真的参数设定如下：系统总的带宽为10 MHz；要求的误码率BER为p_e=10^-4；所有用户都均匀分布于半径为1 km的小区中；路损常数为3；基站与用户间的信道是瑞利衰落信道；加性高斯白噪声的方差N₀是10^－9 W/Hz；总的子载波数N=64；系统总的用户数K=30；子载波速率取值的常数范围M=6；所有试验结果都是经历1万次的独立实验.

图 2 平均接收信噪比与系统总吞吐量的关系，N=6，K=6

从图 2中可以看到，在较大的SNR的情况下，最优化算法与次优子载波与功率分配算法仅有5%的差距.Tian Lin等^[6]提出的算法的系统功效低于次优子载波与功率分配算法和次优化子载波分配算法的系统功效.这是因为在Tian Lin等^[6]提出的算法中每个子载波所能得到的速率被限制在几个整数范围内.因此限制了子载波实际所能达到的速率.同时还可以看到，提出的算法的功效都超过了CMS的系统功效.这是因为基于分层编码的机会组播技术利用了多用户分集增益.每个子载波能分配给有较好的瞬时信道增益的用户.然而，CMS只利用了组播增益，而没有利用多用户分集增益.

从图 3中可以看到，当用户数目从2增加到12时，采用CMS的系统吞吐量将达到饱和.而其他算法的吞吐量将不断增加，这是因为最优化算法、次优子载波分配与功率分配算法和次优子载波分配算法都采用分层编码策略，因此可以给信道条件好的用户分配更多的子载波，而不会受限于最差用户的信道条件.还能看到，笔者提出的算法功效都优于Tian Lin等^[6]提出的算法，这是因为笔者提出的算法没有限定子载波取值的范围，因此可以根据子载波实际获得的速率进行分配.

图 3 用户数与系统总吞吐量的关系，N=9，P_T=50 dBm

在图 4中，假设用户1、用户2和用户3有不同的信道增益.用户1、用户2和用户3的QoS需求R₁^req、R₂^req和R₃^req分别是0.32 Mbit/s、0.26 Mbit/s和0.18 Mbit/s.而其他用户有相同的R_k^req=0.18 Mbit/s.基本层的速率是0.09 Mbit/s.当用户数目增多时，这3个用户的速率依次降低到其QoS需求的速率.当用户数继续增加时，所有用户的速率降低到基本层速率.这是由于用户数目增多时，差用户出现的概率增加，系统要分配较多的子载波来传输基本层数据，因此减少了传输增强层数据的子载波数，影响了每个用户的速率.

图 4 用户数与用户速率的关系，N=64，K=6，P_T=50 dBm

4 结束语

研究了在满足单个组播组内所有用户QoS需求的情况下，基于精细可伸缩视频编码分层编码的最大化系统吞吐量的资源分配算法.提出了一个新颖的2阶段次优化算法，子载波分配阶段由3步组成，比特加载阶段，通过功率和比特加载算法来进一步提高系统功效.从仿真结果看，提出的次优化算法的系统功效接近最优化算法，并且很大程度地超出了传统组播策略，而且也优于Tian Lin等^[6]提出的算法.

参考文献

[1]	Introduction to Multimedia Broadcast and Multicast Services (MBMS) in Radio Access Network, 3GPP TS 25.346, Rev v7.4.0, 2007.
[2]	Afolabi R O, Dadlani A, Kiseon K. Multicast scheduling and resource allocation algorithms for OFDMA-based systems: a survey[J].IEEE Communications Surveys and Tutorials, 2013, 15(1): 240–254. doi: 10.1109/SURV.2012.013012.00074
[3]	Liu Juan, Chen Wei, Cao Zhigang, et al. Dynamic power and sub-carrier allocation for OFDMA-based wireless multicast systems[C]//ICC 2008. Beijing: IEEE Press, 2008: 2607-2611.
[4]	Ngo D T, Tellambura C, Nguyen H H. Efficient resource allocation for OFDMA multicast systems with fairness consideration[C]//RWS 2009. Baltimore: IEEE Press, 2009: 392-395.
[5]	Hyungsuk W, Han C, Do Y E. Multicast scheduling in cellular data networks[J].IEEE Transactions on Wireless Communications, 2009, 8(6): 4540–4549.
[6]	Tian Lin, Pang Di, Yang Yubo, et al. Subcarrier allocation for multicast services in multicarrier wireless systems with QoS guarantees[C]//WCNC 2010. Sydney: IEEE Press, 2010: 1-6.