李 青,何大治,管云峰,殷惠清
(1.上海交通大學(xué),上海 200140;2.數(shù)字電視國家工程研究中心,上海 200125)
一種適合數(shù)字電視上行信道的資源分配方法
李 青1,何大治1,管云峰1,殷惠清2
(1.上海交通大學(xué),上海 200140;2.數(shù)字電視國家工程研究中心,上海 200125)
上行回傳技術(shù)是下一代數(shù)字電視廣播系統(tǒng)需要考慮的關(guān)鍵技術(shù)點(diǎn)之一,如何合理分配使用白頻譜資源是研究重點(diǎn)。為了解決大量用戶同時(shí)接入時(shí)資源需要被快速分配的問題,在研究分析已有工作的前提下,提出一種基于內(nèi)容的資源分配方案。這種方案的特點(diǎn)在于兼顧公平與效率,且可以快速完成資源分配,在很短的時(shí)延內(nèi)完成使大量用戶接入系統(tǒng)。同時(shí),分析了用戶行為、廣播內(nèi)容與接入用戶數(shù)三者的關(guān)系,通過分析三者之間的聯(lián)系與制衡因素,動態(tài)修改資源分配參數(shù)。通過與其他算法對比,所提出的資源分配方法在公平性、有效性和基于內(nèi)容的靈活性方面,更加適合大量用戶同時(shí)接入的場景。
數(shù)字電視;上行;白頻譜;資源分配
隨著互聯(lián)網(wǎng)技術(shù)的蓬勃發(fā)展,人們對于交互式服務(wù)的需求越來越多,新興視頻網(wǎng)站的彈幕功能、點(diǎn)贊功能給用戶帶來了全新體驗(yàn)。傳統(tǒng)的廣播電視屬于典型的單向傳輸業(yè)務(wù),并不支持用戶上傳數(shù)據(jù)信息。為了使廣播系統(tǒng)滿足用戶對交互性的需求,許多國際標(biāo)準(zhǔn)組織(如DVB,ATSC)考慮在已有的設(shè)施基礎(chǔ)之上設(shè)計(jì)一個(gè)低成本的可行回傳信道。另一方面,日益緊張的頻譜資源不允許為每個(gè)上行用戶分配一個(gè)上行回傳信道。文獻(xiàn)[1]調(diào)研了美國的頻譜使用情況,指出雖然頻譜資源緊缺,但是仍有很多白頻譜資源沒有被利用起來。中國的頻譜利用情況與美國類似,尤其近幾年,可用頻譜資源的競爭日漸激烈,而關(guān)于白頻譜的研究卻幾近空白。在此基礎(chǔ)上,筆者希望尋找一種可行的方案,利用相對比較充分的白頻譜資源進(jìn)行數(shù)字電視的上行回傳。用戶進(jìn)行上行回傳的場景與蜂窩網(wǎng)的上行信道存在差異,差異的主要原因在于廣播大塔的覆蓋半徑在100 km左右,上行用戶相比于蜂窩網(wǎng)非常之多。這意味著需要提出一種可行的方案,支持上千個(gè)用戶的同時(shí)接入,滿足用戶對熱點(diǎn)內(nèi)容的點(diǎn)評或回復(fù)需求[2]。
基于這樣的假設(shè),筆者提出一種可能的上行回傳結(jié)構(gòu),并結(jié)合集中式網(wǎng)絡(luò)資源分配算法給出一種資源分配方案。同時(shí),筆者希望建立用戶接入與廣播內(nèi)容之間的數(shù)學(xué)模型,使得資源分配算法具有基于內(nèi)容的可預(yù)知性。并通過對內(nèi)容的分析修改資源分配算法中的控制因子,動態(tài)調(diào)整資源分配方案。
為了滿足用戶的接入需求,上行幀可能需要包含3個(gè)部分,如圖1所示,上行接入需要有隨機(jī)接入信道(Random Access Channel,RACH),用戶數(shù)據(jù)信道(User Data Channel,UDCH)和未來擴(kuò)展信道(Extended Channel,EXCH)。圖中的參數(shù)是筆者建議的時(shí)頻劃分參考取值。
用戶進(jìn)行上行回傳的過程如圖2所示,首先用戶設(shè)備進(jìn)行頻譜檢測,發(fā)現(xiàn)臨時(shí)可用的空白頻段資源,然后通過該頻段的RACH信道進(jìn)行接入。在中心基站,天線收到若干用戶的接入請求,訪問數(shù)據(jù)庫判斷用戶發(fā)現(xiàn)的頻點(diǎn)是否當(dāng)前確實(shí)可用,如果可用,則對用戶進(jìn)行功率控制以避免用戶之間的干擾,并分配該頻段一定的資源給用戶,響應(yīng)用戶的接入請求;如果不可用,則下發(fā)接入失敗的信息,用戶等待若干時(shí)間再次發(fā)起接入請求。
圖1 上行幀的可能結(jié)構(gòu)
圖2 用戶接入流程
在中心基站進(jìn)行資源分配時(shí),將權(quán)衡多個(gè)用戶的業(yè)務(wù)進(jìn)行優(yōu)化分配,假設(shè)資源分配的資源塊如圖3所示,用戶在每個(gè)資源塊上的信噪比等參數(shù)已知或可以通過以往記錄的數(shù)據(jù)獲得,那么資源分配的問題可以用一個(gè)最優(yōu)化問題描述。
圖3 資源塊示意圖
(1)
根據(jù)式(1)解得
(2)
式中:Γ?-ln(5BER)/1.6表示SNR間隔;Hk,n?hk,n/Γ表示資源塊的有效SNR,于是,資源分配問題可以優(yōu)化為
(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表示一個(gè)資源塊能且僅能分配給一個(gè)用戶。約束條件s.t.2和s.t.4的實(shí)際物理意義是發(fā)射功率有限且非負(fù)。約束條件s.t.5中表示用戶總的數(shù)據(jù)速率符合歸一化比例。即
(4)
(5)
上述問題屬于一個(gè)NP-hard的優(yōu)化問題,無法在數(shù)學(xué)上找到顯式的表達(dá)式來求出最優(yōu)解。針對這個(gè)問題,文獻(xiàn)[3]介紹了OFDMA蜂窩系統(tǒng)資源分配需要考慮的問題,提出仿射變換將優(yōu)化問題轉(zhuǎn)化到凸集上進(jìn)行最優(yōu)解搜索;文獻(xiàn)[4-5]分別考慮了單天線和多天線情況下的OFDM系統(tǒng)資源分配問題;文獻(xiàn)[6]和文獻(xiàn)[7]研究了含有中繼的網(wǎng)絡(luò)結(jié)構(gòu)下的資源分配問題,提出可以利用中繼的地理位置,在遠(yuǎn)離中繼的地方復(fù)用頻率給碼率較低的用戶,來保證公平性和服務(wù)質(zhì)量;文獻(xiàn)[8]提出了利用匈牙利算法統(tǒng)一地分配小區(qū)邊緣的資源;文獻(xiàn)[9]提出了一種基于公平性的算法,并建立數(shù)學(xué)模型用矩陣的方式求得次優(yōu)解。文獻(xiàn)[10]和[11]則研究了無線頻譜的分配問題。
上述參考文獻(xiàn)進(jìn)行了不同的嘗試,提出可行的獲得次優(yōu)解的算法。但是由于計(jì)算量較大或不夠靈活,使得這些方案并不能夠直接用于廣播電視用戶上行接入的場景。為了解決這個(gè)問題,筆者對式(3)進(jìn)行分析,注意到,如果將約束條件s.t.3改為
(6)
約束條件s.t.5改為
s.t.5:Ri:Rj≈φi:φj?i,j∈{1,2,3,…,K},i≠j
(7)
即對效率性的要求略微降低。同時(shí),考慮到匈牙利算法作為較為成熟的任務(wù)指派問題解法,能夠在多項(xiàng)式時(shí)間內(nèi)解決二分圖最大匹配問題,可以應(yīng)用于資源塊數(shù)目等于用戶數(shù)情況下的聯(lián)合最優(yōu)解尋找。這樣一來,筆者提出了一種新的快速資源分配算法,該算法的時(shí)間復(fù)雜度較低且消耗時(shí)間可控,在一定的時(shí)間內(nèi)總能夠得到一個(gè)最優(yōu)解或次優(yōu)解,適用于廣播電視同時(shí)接入用戶數(shù)很多的場景。
算法主要分為以下4個(gè)步驟:
步驟1,基站估計(jì)K個(gè)用戶在N個(gè)資源塊上各自可達(dá)的數(shù)據(jù)率rk,n,如果用戶k可在資源塊n上獲得最高的數(shù)據(jù)率且其他用戶在資源塊n上不能獲得最高的數(shù)據(jù)率,則將資源塊n分配給用戶k;如果2個(gè)或以上的用戶都在資源塊n上達(dá)到了最高速率,則保留該資源塊n和用戶,進(jìn)入步驟2。
步驟2,用Kremain和Nremain分別表示步驟1中沒有被分配資源的用戶集合和剩余的資源塊集合。把這個(gè)問題看作一個(gè)任務(wù)指派問題,如果剩余的用戶數(shù)K′多于剩余的資源數(shù)N′,則隨機(jī)抽取N′個(gè)用戶利用匈牙利算法進(jìn)行任務(wù)分配問題的求解,獲得一個(gè)資源分配的次優(yōu)解,同時(shí)基站需要給另外K′-N′個(gè)沒有分配到資源的用戶下發(fā)接入請求失敗的信息;如果剩余資源數(shù)N′多于剩余用戶數(shù)K′,則從N′個(gè)資源塊中隨機(jī)選取K′個(gè)資源塊,利用匈牙利算法進(jìn)行資源分配。步驟2結(jié)束之后,每個(gè)用戶都將被分配一個(gè)資源塊。判斷是否有剩余資源,若有剩余資源,則更新Kremain和Nremain,進(jìn)入步驟3,若資源都已分配完畢,則進(jìn)入步驟4。
步驟3,系統(tǒng)預(yù)設(shè)一個(gè)循環(huán)門限Nloop,令循環(huán)變量loop=1。求所有用戶的平均碼率,選擇m個(gè)用戶,并從剩余資源塊中隨機(jī)的選擇m個(gè)資源塊,利用匈牙利算法進(jìn)行分配,loop=loop+1。更新Nremain并判斷Nremain是否為空,若為空集,則進(jìn)入步驟4,否則判斷l(xiāng)oop是否小于Nloop,若小于Nloop,則重復(fù)步驟3否則進(jìn)入步驟4。
步驟4,計(jì)算總的數(shù)據(jù)率,并將分配結(jié)果通過控制信道下行傳遞給用戶。
步驟1和步驟2的目的在于保證每個(gè)用戶都能至少分配到一個(gè),同時(shí)給出用戶是否接入成功的信息。步驟3的目的在于提高系統(tǒng)效率,讓一些用戶可以獲得更高的數(shù)據(jù)率。步驟3中用戶的選擇有多種方式,可以完全隨機(jī)選擇用戶,也可以選擇碼率低于平均數(shù)據(jù)率的用戶,或碼率高于平均數(shù)據(jù)率的用戶,以及根據(jù)用戶上行的業(yè)務(wù)不同來選擇,優(yōu)先將資源分配給需要上傳大量數(shù)據(jù)的用戶。Nloop的目的是保證算法的時(shí)間效率,即步驟3重復(fù)到一定的次數(shù)一定會結(jié)束。在用戶較多的情況下,Nloop的值可以較小,以減小接入響應(yīng)時(shí)延,在用戶較少的情況下,Nloop可以選擇一個(gè)較大的值,以滿足用戶對高速傳輸?shù)囊蟆jP(guān)于Nloop的選擇與用戶接入概率之間的關(guān)系將在下一章詳細(xì)討論。
在筆者提出的資源分配方法中,Nloop是控制循環(huán)次數(shù)的因子,Nloop的大小影響了資源分配的速度和最終系統(tǒng)可以達(dá)到的性能。在接入用戶較多的時(shí)候,希望Nloop的值較小,這樣可以為很多用戶快速地分配一個(gè)資源塊;可以認(rèn)為大量用戶接入時(shí),所需要的業(yè)務(wù)一般為投票或者點(diǎn)贊,此時(shí)較少的資源塊就可以滿足用戶的需求,而在接入用戶較少的時(shí)候,希望Nloop的值適當(dāng)變大,這樣可以為每個(gè)用戶分配更多的資源,提高系統(tǒng)效率;可以認(rèn)為算法中的Nloop值與接入用戶數(shù)有關(guān),而接入用戶數(shù)與用戶的接入概率有關(guān)。
傳統(tǒng)概率模型認(rèn)為一段時(shí)間內(nèi)的接入用戶數(shù)符合泊松分布,即接入用戶數(shù)K=k的概率為
(8)
當(dāng)系統(tǒng)中同時(shí)需要接入的用戶較多時(shí),根據(jù)中心極限定理,可以近似認(rèn)為用戶的接入概率服從正態(tài)分布。
而事實(shí)上,一旦廣播系統(tǒng)具有了交互性,用戶之間的行為將不再是獨(dú)立事件。文獻(xiàn)[12]研究了非獨(dú)立的投資行為,文獻(xiàn)[13]則介紹了復(fù)雜網(wǎng)絡(luò)中的調(diào)度問題。受這兩篇文章啟發(fā),可以假定用戶發(fā)起上行接入請求并不是獨(dú)立事件,而是與內(nèi)容和其他用戶反應(yīng)相關(guān)的非線性函數(shù)。文獻(xiàn)[14]以一家視頻網(wǎng)站為例研究了彈幕文化帶來的影響,一旦一種內(nèi)容成為風(fēng)尚,用戶之中會產(chǎn)生粘滯效應(yīng),形成文化上的粘滯群,個(gè)體之間的互動將刺激上傳數(shù)據(jù)量和發(fā)起上傳次數(shù)的增加。因此,可以推測用戶個(gè)體是否發(fā)起接入請求與其他用戶之前的反饋信息之間存在著聯(lián)系,用戶看到的反饋信息越多,發(fā)起接入請求的概率越大。另一方面,用戶是否發(fā)起上行接入請求,與廣播內(nèi)容存在著明顯的聯(lián)系。對于熱度比較高的內(nèi)容(如重要比賽、流行節(jié)目、國家大事的追蹤報(bào)道等),用戶會有較強(qiáng)的愿望參與其中,而參與的方式主要以小數(shù)據(jù)量的投票、點(diǎn)贊為主。對于這類業(yè)務(wù)的接入,希望能夠同時(shí)接入較多的用戶,而不需要有很高的碼率,因?yàn)橛脩粼诮尤牒罂梢院芸斓貙⑸闲行畔l(fā)送完畢然后退出系統(tǒng),Nloop可以選較小的值;而對于另一類熱度相對不高的內(nèi)容(如外語節(jié)目),用戶有可能只是選擇性地上傳字幕等資源,此時(shí)接入用戶數(shù)較少,系統(tǒng)可以設(shè)置較大的Nloop值來分配給用戶更多的資源。
基于上述分析,筆者希望可以找到一個(gè)數(shù)學(xué)模型,將Nloop取值與用戶的接入概率聯(lián)系起來。用K表示一段時(shí)間內(nèi)已經(jīng)接入的用戶,Buser表示一段時(shí)間內(nèi)用戶上傳的數(shù)據(jù)比特總和,α表示廣播內(nèi)容熱度參數(shù)(α=1表示熱度非常高,屬于主流人群關(guān)注的內(nèi)容,α=2表示短期內(nèi)的流行內(nèi)容,α=3表示普通內(nèi)容,α=4表示受關(guān)注程度較低的內(nèi)容),用戶k發(fā)起接入的概率為Pk,則可以用式(9)表示用戶接入概率Pk與α,K,Buser之間的關(guān)系
Pk=e-α+Δ(K,Buser)
(9)
其中,Δ(K,Buser)為與K和Buser有關(guān)的修正因子,為了保證式(9)有意義,希望Δ(K,Buser)最大值小于α,即用戶的接入概率始終小于1。而Δ(K,Buser)關(guān)于變量K和Buser的關(guān)系曲線,則需要通過統(tǒng)計(jì)大量的用戶行為獲得,使得估計(jì)的結(jié)果更為準(zhǔn)確。Nloop與Pk有關(guān),Pk越大,表示接入的用戶越多,Nloop越小;Pk越小,每個(gè)時(shí)隙內(nèi)接入的用戶越少,Nloop可以預(yù)設(shè)的值越大。可以用式(10)近似表示Nloop與用戶接入概率Pk之間的關(guān)系
(10)
式中:[]表示取整運(yùn)算;Nmin為一個(gè)正的常數(shù);Λ(K,Buser)為與K和Buser有關(guān)的修正因子,Λ(K,Buser)關(guān)于K和Buser的曲線需要通過大量實(shí)際統(tǒng)計(jì)用戶行為獲得,同時(shí)要保證Nloop最大值不超過N,當(dāng)Nloop=0時(shí)表示不進(jìn)行算法中的步驟3,此時(shí)為最快的接入,每個(gè)用戶只能分配一個(gè)資源塊;當(dāng)Nloop=N時(shí),是資源分配算法時(shí)延最大的情況,表示所有的資源都被分配給一個(gè)用戶(在實(shí)際廣播系統(tǒng)中,這種情況出現(xiàn)的概率非常低)。
通過上述分析,獲得了用戶接入概率與業(yè)務(wù)類型之間的數(shù)學(xué)模型,根據(jù)這個(gè)模型,系統(tǒng)可以基于廣播內(nèi)容,提前預(yù)設(shè)資源分配方案中的Nloop參數(shù),也可以根據(jù)一段時(shí)間內(nèi)接入的用戶數(shù)動態(tài)調(diào)整Nloop值。該方法適合于廣播電視上行接入用戶多,覆蓋范圍廣的場景,且相比于其他算法,具有基于內(nèi)容的可預(yù)知特性。
為了驗(yàn)證算法的可行性和性能,筆者進(jìn)行了如下仿真。信道增益根據(jù)奧村模型進(jìn)行估算,并隨機(jī)的產(chǎn)生用戶k在資源塊n上的信噪比,并根據(jù)信噪比計(jì)算出用戶在該資源塊上可以達(dá)到的速率。在仿真時(shí)假設(shè)可用資源塊數(shù)N=63,圖4對比了16個(gè)用戶時(shí)本文提出的方法與文獻(xiàn)[9]中方法分配給用戶資源塊數(shù)目的分配比例;圖5對比了上述兩種方法每個(gè)用戶可達(dá)最高數(shù)據(jù)率的分配比例。
圖4 兩種方法分配給用戶資源塊數(shù)對比圖
圖5 兩種方法用戶碼率對比圖
從兩圖的結(jié)果中可以看出,在快速算法循環(huán)的時(shí)候,總是選擇給數(shù)據(jù)速率低于平均值的用戶分配更多的資源,即公平性優(yōu)先。對比兩種方法可以發(fā)現(xiàn)快速算法與文獻(xiàn)[9]中的線性算法都保證了相對的比例公平,但是快速算法對用戶來說更為公平,16個(gè)用戶的碼率較為接近,盡管頻譜效率有所下降,但是通過多次循環(huán)分配可以獲得較高的系統(tǒng)吞吐量。
圖6 不同Nloop值對系統(tǒng)總碼率的影響
本文在集中式網(wǎng)絡(luò)資源分配的算法基礎(chǔ)上,提出了一種適合于大量用戶接入場景下的快速資源分配算法,并且該算法同樣可以支持較少用戶的高速數(shù)據(jù)傳輸。為了研究算法的參數(shù)設(shè)置,筆者提出了用戶接入概率與廣播內(nèi)容之間的數(shù)學(xué)模型,將分配算法與廣播內(nèi)容聯(lián)系起來,這樣一來,基于內(nèi)容的接入與資源分配算法可以提前預(yù)設(shè)恰當(dāng)?shù)膮?shù),同時(shí)可以動態(tài)地修改算法參數(shù),在時(shí)間性能和頻譜效率方面達(dá)到最優(yōu)的選擇。
未來的工作將主要集中于Δ(K,Buser)和Λ(K,Buser)的研究分析,筆者希望能夠通過對用戶的行為分析獲得精確的數(shù)學(xué)模型,為系統(tǒng)提供更精確可靠的參數(shù)設(shè)置。
[1] Federal communications commission.Spectrum policy task force report,ET Docket No.02-135[S].2002.
[2] 包俊,范金慧,孫鳴,等. 新媒體時(shí)代的電視發(fā)展分析[J]. 廣播與電視技術(shù), 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 系統(tǒng)基于 Relay 的下行集中式資源分配算法研究[J]. 廣東通信技術(shù),2012,32(4):57-61.
[8] 劉輝,劉波. 多小區(qū)邊緣用戶集中式資源分配策略[J].數(shù)字通信, 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].北京:北京郵電大學(xué),2010.
[11] 吳非.認(rèn)知無線電多小區(qū)間頻譜分配算法研究[D].成都:電子科技大學(xué),2008.
[12] 廖佳.非獨(dú)立策略投資者行為與股市異象研究[D].上海:復(fù)旦大學(xué),2011.
[13] 宣琦. 基于復(fù)雜網(wǎng)絡(luò)理論的復(fù)雜調(diào)度問題求解方法研究[D].杭州:浙江大學(xué),2008.
[14] 陳席元. 彈幕話語建構(gòu)的青年亞文化網(wǎng)絡(luò)社群研究——以嗶哩嗶哩網(wǎng)對Keyki事件反應(yīng)為例[J]. 電腦知識與技術(shù), 2014(20):18.
責(zé)任編輯:閆雯雯
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
【本文獻(xiàn)信息】李青,何大治,管云峰,等.一種適合數(shù)字電視上行信道的資源分配方法[J].電視技術(shù),2015,39(11).
國家自然科學(xué)基金項(xiàng)目(61420106008);“111”引智計(jì)劃項(xiàng)目(B07022);國家“863”計(jì)劃項(xiàng)目(2012AA011701;2013AA013503);上海交通大學(xué)科技創(chuàng)新基金項(xiàng)目(AF0300021)
TN941
A
10.16280/j.videoe.2015.11.022
2014-12-25