一種適合數字電視上行信道的資源分配方法

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

(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越?。籔k越小，每個時隙內接入的用戶越少，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