一种适合数字电视上行信道的资源分配方法

李 青，何大治，管云峰，殷惠清

(1.上海交通大学，上海 200140；2.数字电视国家工程研究中心，上海 200125)

一种适合数字电视上行信道的资源分配方法

李 青1，何大治1，管云峰1，殷惠清2

(1.上海交通大学，上海 200140；2.数字电视国家工程研究中心，上海 200125)

上行回传技术是下一代数字电视广播系统需要考虑的关键技术点之一，如何合理分配使用白频谱资源是研究重点。为了解决大量用户同时接入时资源需要被快速分配的问题，在研究分析已有工作的前提下，提出一种基于内容的资源分配方案。这种方案的特点在于兼顾公平与效率，且可以快速完成资源分配，在很短的时延内完成使大量用户接入系统。同时，分析了用户行为、广播内容与接入用户数三者的关系，通过分析三者之间的联系与制衡因素，动态修改资源分配参数。通过与其他算法对比，所提出的资源分配方法在公平性、有效性和基于内容的灵活性方面，更加适合大量用户同时接入的场景。

数字电视；上行；白频谱；资源分配

随着互联网技术的蓬勃发展，人们对于交互式服务的需求越来越多，新兴视频网站的弹幕功能、点赞功能给用户带来了全新体验。传统的广播电视属于典型的单向传输业务，并不支持用户上传数据信息。为了使广播系统满足用户对交互性的需求，许多国际标准组织(如DVB，ATSC)考虑在已有的设施基础之上设计一个低成本的可行回传信道。另一方面，日益紧张的频谱资源不允许为每个上行用户分配一个上行回传信道。文献[1]调研了美国的频谱使用情况，指出虽然频谱资源紧缺，但是仍有很多白频谱资源没有被利用起来。中国的频谱利用情况与美国类似，尤其近几年，可用频谱资源的竞争日渐激烈，而关于白频谱的研究却几近空白。在此基础上，笔者希望寻找一种可行的方案，利用相对比较充分的白频谱资源进行数字电视的上行回传。用户进行上行回传的场景与蜂窝网的上行信道存在差异，差异的主要原因在于广播大塔的覆盖半径在100 km左右，上行用户相比于蜂窝网非常之多。这意味着需要提出一种可行的方案，支持上千个用户的同时接入，满足用户对热点内容的点评或回复需求[2]。

基于这样的假设，笔者提出一种可能的上行回传结构，并结合集中式网络资源分配算法给出一种资源分配方案。同时，笔者希望建立用户接入与广播内容之间的数学模型，使得资源分配算法具有基于内容的可预知性。并通过对内容的分析修改资源分配算法中的控制因子，动态调整资源分配方案。

1 数学模型

为了满足用户的接入需求，上行帧可能需要包含3个部分，如图1所示，上行接入需要有随机接入信道(Random Access Channel，RACH)，用户数据信道(User Data Channel，UDCH)和未来扩展信道(Extended Channel，EXCH)。图中的参数是笔者建议的时频划分参考取值。

用户进行上行回传的过程如图2所示，首先用户设备进行频谱检测，发现临时可用的空白频段资源，然后通过该频段的RACH信道进行接入。在中心基站，天线收到若干用户的接入请求，访问数据库判断用户发现的频点是否当前确实可用，如果可用，则对用户进行功率控制以避免用户之间的干扰，并分配该频段一定的资源给用户，响应用户的接入请求；如果不可用，则下发接入失败的信息，用户等待若干时间再次发起接入请求。

图1 上行帧的可能结构

图2 用户接入流程

在中心基站进行资源分配时，将权衡多个用户的业务进行优化分配，假设资源分配的资源块如图3所示，用户在每个资源块上的信噪比等参数已知或可以通过以往记录的数据获得，那么资源分配的问题可以用一个最优化问题描述。

图3 资源块示意图

(1)

根据式(1)解得

(2)

式中：Γ≜-ln(5BER)/1.6表示SNR间隔；Hk,n≜hk,n/Γ表示资源块的有效SNR，于是，资源分配问题可以优化为

(3)

s.t.1:ck,n∈{0,1}∀k,n

s.t.2:pk，n≥0∀k,n

s.t.5:Ri:Rj=φi:φj∀i,j∈{1,2，3，…,K},i≠j

其中，ck,n=1表示资源块n被分配给了用户k，约束条件s.t.1和s.t.3表示一个资源块能且仅能分配给一个用户。约束条件s.t.2和s.t.4的实际物理意义是发射功率有限且非负。约束条件s.t.5中表示用户总的数据速率符合归一化比例。即

(4)

(5)

上述问题属于一个NP-hard的优化问题，无法在数学上找到显式的表达式来求出最优解。针对这个问题，文献[3]介绍了OFDMA蜂窝系统资源分配需要考虑的问题，提出仿射变换将优化问题转化到凸集上进行最优解搜索；文献[4-5]分别考虑了单天线和多天线情况下的OFDM系统资源分配问题；文献[6]和文献[7]研究了含有中继的网络结构下的资源分配问题，提出可以利用中继的地理位置，在远离中继的地方复用频率给码率较低的用户，来保证公平性和服务质量；文献[8]提出了利用匈牙利算法统一地分配小区边缘的资源；文献[9]提出了一种基于公平性的算法，并建立数学模型用矩阵的方式求得次优解。文献[10]和[11]则研究了无线频谱的分配问题。

2 资源分配快速算法

上述参考文献进行了不同的尝试，提出可行的获得次优解的算法。但是由于计算量较大或不够灵活，使得这些方案并不能够直接用于广播电视用户上行接入的场景。为了解决这个问题，笔者对式(3)进行分析，注意到，如果将约束条件s.t.3改为

(6)

约束条件s.t.5改为

s.t.5:Ri:Rj≈φi:φj∀i,j∈{1,2，3，…,K},i≠j

(7)

即对效率性的要求略微降低。同时，考虑到匈牙利算法作为较为成熟的任务指派问题解法，能够在多项式时间内解决二分图最大匹配问题，可以应用于资源块数目等于用户数情况下的联合最优解寻找。这样一来，笔者提出了一种新的快速资源分配算法，该算法的时间复杂度较低且消耗时间可控，在一定的时间内总能够得到一个最优解或次优解，适用于广播电视同时接入用户数很多的场景。

算法主要分为以下4个步骤：

步骤1，基站估计K个用户在N个资源块上各自可达的数据率rk,n，如果用户k可在资源块n上获得最高的数据率且其他用户在资源块n上不能获得最高的数据率，则将资源块n分配给用户k；如果2个或以上的用户都在资源块n上达到了最高速率，则保留该资源块n和用户，进入步骤2。

步骤2，用Kremain和Nremain分别表示步骤1中没有被分配资源的用户集合和剩余的资源块集合。把这个问题看作一个任务指派问题，如果剩余的用户数K′多于剩余的资源数N′，则随机抽取N′个用户利用匈牙利算法进行任务分配问题的求解，获得一个资源分配的次优解，同时基站需要给另外K′-N′个没有分配到资源的用户下发接入请求失败的信息；如果剩余资源数N′多于剩余用户数K′，则从N′个资源块中随机选取K′个资源块，利用匈牙利算法进行资源分配。步骤2结束之后，每个用户都将被分配一个资源块。判断是否有剩余资源，若有剩余资源，则更新Kremain和Nremain，进入步骤3，若资源都已分配完毕，则进入步骤4。

步骤3，系统预设一个循环门限Nloop，令循环变量loop=1。求所有用户的平均码率，选择m个用户，并从剩余资源块中随机的选择m个资源块，利用匈牙利算法进行分配，loop=loop+1。更新Nremain并判断Nremain是否为空，若为空集，则进入步骤4，否则判断loop是否小于Nloop，若小于Nloop，则重复步骤3否则进入步骤4。

步骤4，计算总的数据率，并将分配结果通过控制信道下行传递给用户。

步骤1和步骤2的目的在于保证每个用户都能至少分配到一个，同时给出用户是否接入成功的信息。步骤3的目的在于提高系统效率，让一些用户可以获得更高的数据率。步骤3中用户的选择有多种方式，可以完全随机选择用户，也可以选择码率低于平均数据率的用户，或码率高于平均数据率的用户，以及根据用户上行的业务不同来选择，优先将资源分配给需要上传大量数据的用户。Nloop的目的是保证算法的时间效率，即步骤3重复到一定的次数一定会结束。在用户较多的情况下，Nloop的值可以较小，以减小接入响应时延，在用户较少的情况下，Nloop可以选择一个较大的值，以满足用户对高速传输的要求。关于Nloop的选择与用户接入概率之间的关系将在下一章详细讨论。

3 资源分配参数设置

在笔者提出的资源分配方法中，Nloop是控制循环次数的因子，Nloop的大小影响了资源分配的速度和最终系统可以达到的性能。在接入用户较多的时候，希望Nloop的值较小，这样可以为很多用户快速地分配一个资源块；可以认为大量用户接入时，所需要的业务一般为投票或者点赞，此时较少的资源块就可以满足用户的需求，而在接入用户较少的时候，希望Nloop的值适当变大，这样可以为每个用户分配更多的资源，提高系统效率；可以认为算法中的Nloop值与接入用户数有关，而接入用户数与用户的接入概率有关。

传统概率模型认为一段时间内的接入用户数符合泊松分布，即接入用户数K=k的概率为

(8)

当系统中同时需要接入的用户较多时，根据中心极限定理，可以近似认为用户的接入概率服从正态分布。

而事实上，一旦广播系统具有了交互性，用户之间的行为将不再是独立事件。文献[12]研究了非独立的投资行为，文献[13]则介绍了复杂网络中的调度问题。受这两篇文章启发，可以假定用户发起上行接入请求并不是独立事件，而是与内容和其他用户反应相关的非线性函数。文献[14]以一家视频网站为例研究了弹幕文化带来的影响，一旦一种内容成为风尚，用户之中会产生粘滞效应，形成文化上的粘滞群，个体之间的互动将刺激上传数据量和发起上传次数的增加。因此，可以推测用户个体是否发起接入请求与其他用户之前的反馈信息之间存在着联系，用户看到的反馈信息越多，发起接入请求的概率越大。另一方面，用户是否发起上行接入请求，与广播内容存在着明显的联系。对于热度比较高的内容(如重要比赛、流行节目、国家大事的追踪报道等)，用户会有较强的愿望参与其中，而参与的方式主要以小数据量的投票、点赞为主。对于这类业务的接入，希望能够同时接入较多的用户，而不需要有很高的码率，因为用户在接入后可以很快地将上行信息发送完毕然后退出系统，Nloop可以选较小的值；而对于另一类热度相对不高的内容(如外语节目)，用户有可能只是选择性地上传字幕等资源，此时接入用户数较少，系统可以设置较大的Nloop值来分配给用户更多的资源。

基于上述分析，笔者希望可以找到一个数学模型，将Nloop取值与用户的接入概率联系起来。用K表示一段时间内已经接入的用户，Buser表示一段时间内用户上传的数据比特总和，α表示广播内容热度参数(α=1表示热度非常高，属于主流人群关注的内容，α=2表示短期内的流行内容，α=3表示普通内容，α=4表示受关注程度较低的内容)，用户k发起接入的概率为Pk，则可以用式(9)表示用户接入概率Pk与α，K，Buser之间的关系

Pk=e-α+Δ(K,Buser)

(9)

其中，Δ(K,Buser)为与K和Buser有关的修正因子，为了保证式(9)有意义，希望Δ(K,Buser)最大值小于α，即用户的接入概率始终小于1。而Δ(K,Buser)关于变量K和Buser的关系曲线，则需要通过统计大量的用户行为获得，使得估计的结果更为准确。Nloop与Pk有关，Pk越大，表示接入的用户越多，Nloop越小；Pk越小，每个时隙内接入的用户越少，Nloop可以预设的值越大。可以用式(10)近似表示Nloop与用户接入概率Pk之间的关系

(10)

式中：[]表示取整运算；Nmin为一个正的常数；Λ(K,Buser)为与K和Buser有关的修正因子，Λ(K,Buser)关于K和Buser的曲线需要通过大量实际统计用户行为获得，同时要保证Nloop最大值不超过N，当Nloop=0时表示不进行算法中的步骤3，此时为最快的接入，每个用户只能分配一个资源块；当Nloop=N时，是资源分配算法时延最大的情况，表示所有的资源都被分配给一个用户(在实际广播系统中，这种情况出现的概率非常低)。

通过上述分析，获得了用户接入概率与业务类型之间的数学模型，根据这个模型，系统可以基于广播内容，提前预设资源分配方案中的Nloop参数，也可以根据一段时间内接入的用户数动态调整Nloop值。该方法适合于广播电视上行接入用户多，覆盖范围广的场景，且相比于其他算法，具有基于内容的可预知特性。

4 仿真结果

为了验证算法的可行性和性能，笔者进行了如下仿真。信道增益根据奥村模型进行估算，并随机的产生用户k在资源块n上的信噪比，并根据信噪比计算出用户在该资源块上可以达到的速率。在仿真时假设可用资源块数N=63，图4对比了16个用户时本文提出的方法与文献[9]中方法分配给用户资源块数目的分配比例；图5对比了上述两种方法每个用户可达最高数据率的分配比例。

图4 两种方法分配给用户资源块数对比图

图5 两种方法用户码率对比图

从两图的结果中可以看出，在快速算法循环的时候，总是选择给数据速率低于平均值的用户分配更多的资源，即公平性优先。对比两种方法可以发现快速算法与文献[9]中的线性算法都保证了相对的比例公平，但是快速算法对用户来说更为公平，16个用户的码率较为接近，尽管频谱效率有所下降，但是通过多次循环分配可以获得较高的系统吞吐量。

图6 不同Nloop值对系统总码率的影响

5 结论与展望

本文在集中式网络资源分配的算法基础上，提出了一种适合于大量用户接入场景下的快速资源分配算法，并且该算法同样可以支持较少用户的高速数据传输。为了研究算法的参数设置，笔者提出了用户接入概率与广播内容之间的数学模型，将分配算法与广播内容联系起来，这样一来，基于内容的接入与资源分配算法可以提前预设恰当的参数，同时可以动态地修改算法参数，在时间性能和频谱效率方面达到最优的选择。

未来的工作将主要集中于Δ(K,Buser)和Λ(K,Buser)的研究分析，笔者希望能够通过对用户的行为分析获得精确的数学模型，为系统提供更精确可靠的参数设置。

[1] Federal communications commission.Spectrum policy task force report，ET Docket No.02-135[S].2002.

[2] 包俊，范金慧，孙鸣，等. 新媒体时代的电视发展分析[J]. 广播与电视技术， 2007， 34(7)： 16-16.

[3] ABRARDO A， ALESSIO A， DETTI P， et al. Centralized radio resource allocation for OFDMA cellular systems[C]//Proc. IEEE International Conference onCommunications， ICC’07.[S.l.]：IEEE Press， 2007： 5738-5743.

[4] LETAIEF K B，ZHANG Y J.Dynamic multiuser resource allocation and adaptation for wireless systems[J]. IEEE Wireless Communications，2006，13(4)：38-47.

[5] HUANG W， LETAIEF K B. A cross-layer resource allocation and scheduling for multiuser space-time block coded MIMO/OFDM systems[C]//Proc.2005 IEEE International Conference onCommunications. [S.l.]：IEEE Press，2005，4：2655-2659.

[6] LI G， LIU H. Resource allocation for OFDMA relay networks with fairness constraints[J].IEEE Journal on Selected Areas in communications，2006，24(11)：2061-2069.

[7] 熊军洲，漆颖，李效坡. LTE—Advanced 系统基于 Relay 的下行集中式资源分配算法研究[J]. 广东通信技术，2012，32(4)：57-61.

[8] 刘辉，刘波. 多小区边缘用户集中式资源分配策略[J].数字通信， 2014(3)：3.

[9] WONG I C， SHEN Z， EVANS B L， et al. A low complexity algorithm for proportional resource allocation in OFDMA systems[C]//Proc. IEEE Workshop onSignal Processing Systems.[S.l.]：IEEE Press，2004：1-6.

[10] 曾令康.基于博弈论的无线资源分配研究[D].北京：北京邮电大学，2010.

[11] 吴非.认知无线电多小区间频谱分配算法研究[D].成都：电子科技大学，2008.

[12] 廖佳.非独立策略投资者行为与股市异象研究[D].上海：复旦大学，2011.

[13] 宣琦. 基于复杂网络理论的复杂调度问题求解方法研究[D].杭州：浙江大学，2008.

[14] 陈席元. 弹幕话语建构的青年亚文化网络社群研究——以哔哩哔哩网对Keyki事件反应为例[J]. 电脑知识与技术， 2014(20)：18.

责任编辑：闫雯雯

Novel Resource Allocation Strategy for TV Broadcast Uplink System

LI Qing1，HE Dazhi1，GUAN Yunfeng1，YIN Huiqing2

(1.ShanghaiJiaoTongUniversity，Shanghai200140，China；2.NationalEngineeringResearchCenterofDigitalTV，Shanghai200125，China)

Interactive technology is one of the key technologies in next-generation digital television broadcast system. A well designed uplink channel needs to be considered.The focus of research is how to use white space in a broadcast system and allocate the time and frequency resources in a proper way. To find an efficient resource allocation algorithm， the existence work is analyzed and a newly resource allocation method based on the broadcasting content is proposed. The feature of proposed resource allocation method is that， it makes a compromise between fairness and efficiency. Besides， this method can be done very quickly thus a quantity of users can access the system with little time delay. Another feature is the parameter of resource allocation method can be adjusted based on the broadcasting content. Users’ behavior and reaction are other users’ responses. A model is established and the users’ access probabilityis described. Using this probability model， the parameter dynamically can be changed. Compared with other resource allocation methods， the proposed method is more suitable for the situation when a large number of users in terms of fairness， efficiency and flexibility based on content.

digital TV； uplink channel； white space；resource allocation

【本文献信息】李青，何大治，管云峰,等.一种适合数字电视上行信道的资源分配方法[J].电视技术,2015，39(11).

国家自然科学基金项目(61420106008)；“111”引智计划项目(B07022)；国家“863”计划项目(2012AA011701；2013AA013503)；上海交通大学科技创新基金项目(AF0300021)

TN941

A

10.16280/j.videoe.2015.11.022

2014-12-25