5G通信組播傳輸分組策略與資源分配算法研究

張文倩 倪 菊 劉小蘭 毛淑霞 肖海林

1(桂林電子科技大學(xué)信息與通信學(xué)院 廣西 桂林 541004)2(桂林電子科技大學(xué)圖書(shū)館 廣西 桂林 541004)

0 引 言

新興的第五代(5G)無(wú)線通信系統(tǒng)通過(guò)高數(shù)據(jù)速率、低延遲和巨大的網(wǎng)絡(luò)靈活性等特點(diǎn)來(lái)滿足用戶(hù)需求[1]。在5G多媒體數(shù)據(jù)傳輸場(chǎng)景下，為同時(shí)向大量觀眾發(fā)送信息，組播技術(shù)成為5G系統(tǒng)的關(guān)鍵技術(shù)之一，其通過(guò)點(diǎn)對(duì)多點(diǎn)(Point-to-Multipoint，PtM)同時(shí)將數(shù)據(jù)傳輸?shù)揭唤M終端進(jìn)行通信，減少點(diǎn)對(duì)點(diǎn)單播傳輸機(jī)制帶來(lái)的資源消耗，提高蜂窩系統(tǒng)的頻譜效率[2]。

然而，組播傳輸?shù)目蛇_(dá)數(shù)據(jù)速率受信道條件最差用戶(hù)的數(shù)據(jù)速率限制，導(dǎo)致較低的系統(tǒng)吞吐量[3]。近年來(lái)，一些文獻(xiàn)對(duì)組播傳輸速率受限問(wèn)題展開(kāi)研究。文獻(xiàn)[4]提出一種機(jī)會(huì)主義方案，該方案通過(guò)服務(wù)信道質(zhì)量最好的組播用戶(hù)，來(lái)平衡組播增益。文獻(xiàn)[5]對(duì)文獻(xiàn)[4]進(jìn)行改進(jìn)，提出了一種基于自適應(yīng)用戶(hù)選擇的機(jī)會(huì)組播調(diào)度方法，通過(guò)自適應(yīng)地選擇最優(yōu)用戶(hù)比例，提高吞吐量。以上文獻(xiàn)均是采用單速率來(lái)進(jìn)行組播傳輸，雖然保證了一定的公平性，但頻譜效率低。文獻(xiàn)[6]提出了一種多速率方案，將組播用戶(hù)劃分為更小的子組來(lái)提高系統(tǒng)容量。一般的隨機(jī)分組方法將用戶(hù)隨機(jī)劃分為若干組，算法易實(shí)現(xiàn)，但組內(nèi)用戶(hù)接收數(shù)據(jù)的能力差異較大，系統(tǒng)整體性能較低。文獻(xiàn)[7]提出一種低復(fù)雜度的聯(lián)盟博弈理論，通過(guò)用戶(hù)與其他用戶(hù)自主聯(lián)盟來(lái)形成子組。文獻(xiàn)[8]提出一種固定組大小的分組方法，該方法根據(jù)SNR值對(duì)用戶(hù)進(jìn)行分組，但需要人為設(shè)定組播組的個(gè)數(shù)，若組播組個(gè)數(shù)設(shè)定不合理，會(huì)影響組播系統(tǒng)的整體性能。

盡管以上文獻(xiàn)采用分組策略來(lái)提升組播系統(tǒng)吞吐量，但并未考慮資源的充分利用。在這基礎(chǔ)上，正交頻分多址(Orthogonal Frequency Division Multiple Access，OFDMA)被提出并廣泛應(yīng)用于組播系統(tǒng)，以靈活管理頻譜資源[9]。基于OFDMA技術(shù)，文獻(xiàn)[10]提出一種基于低復(fù)雜度子組的資源分配方案，在保證系統(tǒng)容量最大化前提下，通過(guò)調(diào)整系統(tǒng)性能函數(shù)來(lái)選擇不同的調(diào)度策略。文獻(xiàn)[11]提出一種約束團(tuán)隊(duì)進(jìn)化算法實(shí)現(xiàn)每個(gè)組的子載波分配。事實(shí)上，組播組的資源分配問(wèn)題是非確定性多項(xiàng)式約束優(yōu)化問(wèn)題，求解難度為NP-hard，雖然通過(guò)窮舉法可以獲得最優(yōu)解，但其復(fù)雜度隨著問(wèn)題規(guī)模的增大而呈指數(shù)增長(zhǎng)。精確算法在求解該類(lèi)問(wèn)題時(shí)，求解效率低、運(yùn)行速度慢，在實(shí)際中往往不可行。相比之下，智能算法能夠全局尋優(yōu)， 可以在較短時(shí)間內(nèi)求得大規(guī)模問(wèn)題的可行解， 因此成為了非確定性多項(xiàng)式約束優(yōu)化問(wèn)題的主要求解算法[12]。

近年來(lái)，一些智能算法被廣泛地應(yīng)用于子載波分配[13]。文獻(xiàn)[14]利用遺傳算法進(jìn)行子載波分配，將子載波分配變量映射為染色體上的基因，系統(tǒng)吞吐量轉(zhuǎn)化為染色體的適應(yīng)度函數(shù)。該方法較傳統(tǒng)組播機(jī)制提高了系統(tǒng)吞吐量，但算法效率低且易陷入局部最優(yōu)值。文獻(xiàn)[15]采用粒子群算法進(jìn)行子載波分配，該算法所需參數(shù)較少且收斂速度快，過(guò)程較易實(shí)現(xiàn)，但其種群收益所對(duì)應(yīng)的系統(tǒng)吞吐量較低[16]。人工魚(yú)群算法(Artificial Fish Swarm Algorithm，AFSA) 是一種基于動(dòng)物行為的群體智能優(yōu)化算法，用于解決非確定性多項(xiàng)式約束優(yōu)化問(wèn)題，在參數(shù)估計(jì)、神經(jīng)網(wǎng)絡(luò)訓(xùn)練和組合優(yōu)化中得到廣泛的應(yīng)用，具有很強(qiáng)的魯棒性。并且人工魚(yú)群算法對(duì)初始值和參數(shù)的選擇要求不高，簡(jiǎn)單易操作，收斂速度快，能使搜索行為跳出局部最優(yōu)點(diǎn)，獲得全局最優(yōu)解[17-18]。文獻(xiàn)[19]采用人工魚(yú)群算法來(lái)解決非確定性多項(xiàng)式約束的能源優(yōu)化問(wèn)題，利用人工魚(yú)群算法的全局搜索能力，獲得全局最優(yōu)解。

綜合以上考慮，本文提出一種動(dòng)態(tài)聚類(lèi)分組策略與子載波分配方法，該方法將組播用戶(hù)通過(guò)SNR值自動(dòng)分成合適數(shù)量的組。并在該分組策略下，采用改進(jìn)的人工魚(yú)群算法進(jìn)行子載波分配，將子載波分配變量映射為人工魚(yú)的位置，系統(tǒng)吞吐量轉(zhuǎn)化為人工魚(yú)在某一位置的食物濃度進(jìn)行迭代尋優(yōu)，以最大化系統(tǒng)吞吐量。

1 模型分析

1.1 系統(tǒng)模型

信道模型包括大尺度衰落模型和小尺度衰落模型，因此，第k個(gè)用戶(hù)在子載波n上的信道增益可表示為[21]：

(1)

式中：Dk為用戶(hù)k到基站的距離；α為路徑損耗因子；φk,n為用戶(hù)k在子載波n上服從對(duì)數(shù)正態(tài)分布的陰影衰落；φk,n為用戶(hù)k在子載波n上服從瑞利分布的多徑衰落。用戶(hù)k的接收信噪比表示為：

(2)

圖1 組播系統(tǒng)模型

1.2 問(wèn)題建模

為了保證組內(nèi)所有用戶(hù)都能成功解碼接收信號(hào)，基站被限制使用最低的數(shù)據(jù)速率，通常由最低的信道增益來(lái)決定[7]，則組播子組s的信道增益可表示為：

(3)

式中：Hk,n為第k個(gè)用戶(hù)在子載波n上的信道增益。用戶(hù)k在子載波n上的數(shù)據(jù)傳輸速率表示為：

rk,n=wlog2(1+η)

(4)

式中：w為每個(gè)子載波的帶寬。第s個(gè)組播子組在子載波n上的數(shù)據(jù)傳輸速率如下：

(5)

根據(jù)組播系統(tǒng)吞吐量的定義[14]，組播系統(tǒng)總吞吐量可表示為：

(6)

式中：αs,n為二進(jìn)制變量，αs,n=1表示第n個(gè)子載波分配給第s組，否則αs,n=0。因此，本文構(gòu)建的系統(tǒng)優(yōu)化問(wèn)題表示如下：

(7)

(8)

(9)

(10)

(11)

(12)

(13)

(14)

式(8)表示用戶(hù)k是否分配到組播子組s；式(9)表示子組s是否分配了子載波n；式(10)表示每次只能將特定的用戶(hù)分配給一個(gè)子組；式(11)表示每次只能將特定的子載波分配給一個(gè)子組；式(12)表示屬于不同組播子組的兩個(gè)用戶(hù)不能分配到相同的子組中。式(13)表示系統(tǒng)所消耗的子載波數(shù)不超過(guò)系統(tǒng)子載波總數(shù)。式(14)表示基站向每個(gè)組播子組傳輸數(shù)據(jù)速率須大于等于子組的最小數(shù)據(jù)速率，其最小數(shù)據(jù)速率Rmin為1 Mbit/s[8]，保證組內(nèi)用戶(hù)正確解碼。

從式(7)可以看出，這是一個(gè)非線性約束規(guī)劃問(wèn)題，求解復(fù)雜度較高。因此本文將式(7)問(wèn)題轉(zhuǎn)換為組播用戶(hù)分組和子載波分配兩個(gè)子問(wèn)題，從而求得次優(yōu)解。

2 組播分組策略與子載波分配方法

2.1 基于最大最小距離K-means組播分組

本節(jié)采用最大最小距離K-means聚類(lèi)算法[22]對(duì)組播用戶(hù)進(jìn)行分組，分組算法的思想是根據(jù)用戶(hù)反饋給基站的信噪比值將相近或者相同的信噪比盡可能地分在一組，實(shí)現(xiàn)組播用戶(hù)分組。本節(jié)的優(yōu)化目標(biāo)是最大化組播系統(tǒng)的可達(dá)速率，其由組播子組的容量及組播子組的個(gè)數(shù)共同決定，通過(guò)分組策略將其分為合適的組播子組，即該優(yōu)化目標(biāo)等價(jià)于最大化子組內(nèi)用戶(hù)的最小數(shù)據(jù)速率[23]。因此，可建立組播分組子問(wèn)題P1如下：

(15)

s.t. 式(8),式(10),式(12)

基于最大最小距離K-means算法進(jìn)行組播分組的步驟如下：

(1) 初始化參數(shù)。基站通過(guò)用戶(hù)反饋的信道狀態(tài)信息獲得k個(gè)用戶(hù)的信噪比η，這些信噪比η組成的樣本數(shù)據(jù)集為M={x1,x2,…,xk}。

(2) 隨機(jī)選取任意一個(gè)樣本Z1=x1作為第一個(gè)聚類(lèi)中心，并選取距離Z1最遠(yuǎn)的樣本數(shù)據(jù)Z2作為第二個(gè)聚類(lèi)中心。

(3) 計(jì)算剩余樣本數(shù)據(jù)到現(xiàn)有初始聚類(lèi)中心的距離di,1,di,2,…,di,k′，找出其中最小值di。

(4) 從所有最小值中找到最大值Dmax。

(6) 若不滿足步驟(5)，則k=k′。

(7) 計(jì)算剩余樣本與k個(gè)初始聚類(lèi)中心的距離，使每個(gè)樣本分配到距離聚類(lèi)中心最近的組中。

2.2 人工魚(yú)群算法求解子載波分配問(wèn)題

(16)

(17)

(18)

(19)

(20)

式(17)表示子組是否分配了子載波n；式(18)表示只能將特定的子載波分配給一個(gè)子組；式(19)表示系統(tǒng)所消耗的子載波數(shù)不超過(guò)總載波數(shù)。式(20)表示基站向每個(gè)組播子組傳輸數(shù)據(jù)速率須大于等于子組的最小數(shù)據(jù)速率，其最小數(shù)據(jù)速率Rmin為1 Mbit/s[8]，保證組內(nèi)用戶(hù)正確解碼。

子問(wèn)題P2的目標(biāo)是求解子載波分配矩陣A，由于分配矩陣A受到式(17)-式(20)的限制，則產(chǎn)生的分配矩陣必須滿足約束條件。首先若對(duì)整個(gè)A進(jìn)行求解，求解維數(shù)為G×N，求解維數(shù)過(guò)高降低了求解速度。為了降低求解復(fù)雜度，本文采用文獻(xiàn)[24]提出的編碼方式作為人工魚(yú)的位置編碼方式。如圖2所示，構(gòu)造一個(gè)G=5、N=8的子載波分配模型。L中有9個(gè)值為1的元素，檢查L(zhǎng)的第i行n列，以及L的第c行n列是否有多個(gè)1元素。如果是，則隨機(jī)將其中為1的元素置0，僅保留一個(gè)為1元素，形成L1。然后按先行后列的順序抽取對(duì)應(yīng)L1中值為1的元素位置的A中元素進(jìn)行編碼，得到編碼解行向量X(xi∈{0,1})，使用編碼解行向量X進(jìn)行優(yōu)化。之后，再將優(yōu)化后的行向量X按照L1中先行后列的順序還原成分配矩陣A。

圖2 人工魚(yú)的編解碼結(jié)構(gòu)

分配矩陣A所對(duì)應(yīng)的解的優(yōu)化長(zhǎng)度D，由L1中1元素的個(gè)數(shù)決定。假設(shè)人工魚(yú)的數(shù)目為P，則每條人工魚(yú)將分布在一個(gè)D維空間。每條人工魚(yú)代表優(yōu)化問(wèn)題的一個(gè)解，人工魚(yú)的位置對(duì)應(yīng)一種子載波分配方式，以Xi=(xi1,xi2,…,xiD)代表第i條人工魚(yú)的當(dāng)前位置。該人工魚(yú)在某一位置的食物濃度為目標(biāo)函數(shù)，在尋優(yōu)過(guò)程中，搜索到某一位置的人工魚(yú)食物濃度最大，則該位置所對(duì)應(yīng)的解為最優(yōu)的子載波分配方式。

基于人工魚(yú)群算法求解βg,n的步驟如下：

1) 初始化算法各參數(shù)：人工魚(yú)群大小P，可視范圍v，擁擠度因子d，迭代次數(shù)m，移動(dòng)步長(zhǎng)st，人工魚(yú)每次覓食最大試探次數(shù)t。

2) 依據(jù)人工魚(yú)的編碼結(jié)構(gòu)，產(chǎn)生可用子載波分配矩陣L1來(lái)確定優(yōu)化維數(shù)D，然后隨機(jī)產(chǎn)生人工魚(yú)向量Xi=(xi1,xi2,…,xiD)，i=1,2,…,P。

3) 根據(jù)式(16)計(jì)算每條人工魚(yú)的食物濃度Yi，即系統(tǒng)總吞吐量。每次迭代后，選出最大的食物濃度值，其對(duì)應(yīng)的人工魚(yú)位置為當(dāng)前最優(yōu)人工魚(yú)位置，并將最優(yōu)的人工魚(yú)位置BX及其值賦予公告板。

4) 人工魚(yú)的行為定義：

(1) 覓食行為：在人工魚(yú)Xi的可視域內(nèi)隨機(jī)選擇一個(gè)狀態(tài)Xj，其表示如式(21)所示，記錄其食物濃度為Yj。若YiYj，則采用式(23)進(jìn)行隨機(jī)搜索。

Xj=Xi+v·rand()

(21)

(22)

Xnext=Xi+st·rand()

(23)

式中：rand()表示產(chǎn)生隨機(jī)數(shù)的函數(shù)。

(2) 聚群行為：對(duì)人工魚(yú)Xi的有效區(qū)域進(jìn)行搜索，記錄其鄰居的其他人工魚(yú)Xj個(gè)數(shù)nf。若nf>0，計(jì)算有效搜索區(qū)域內(nèi)的中心位置為Xc，其表示如式(24)所示，計(jì)算相應(yīng)食物濃度為Yc。若Yc/nf>dYi，則人工魚(yú)向最大食物濃度的位置移動(dòng)執(zhí)行式(25)；否則執(zhí)行覓食行為。

(24)

(25)

(3) 追尾行為：對(duì)人工魚(yú)Xi的有效區(qū)域進(jìn)行搜索，記錄其鄰居的其他人工魚(yú)Xj個(gè)數(shù)nf。若nf>0，找到其中食物濃度最大的人工魚(yú)Xmax，計(jì)算最大食物濃度Ymax。若Ymax/nf>dYi，則人工魚(yú)向最大食物濃度位置移動(dòng)，執(zhí)行式(26)；否則執(zhí)行覓食行為。

(26)

5) 對(duì)人工魚(yú)個(gè)體Xi分別進(jìn)行覓食、聚群、追尾和隨機(jī)行為，通過(guò)行為評(píng)價(jià)，選擇執(zhí)行食物濃度較大的行為。

6) 通過(guò)擇優(yōu)后得到人工魚(yú)向量Xi，并且將公告牌更新為該個(gè)體BX。

7) 若達(dá)到最大迭代次數(shù)m或公告牌上最優(yōu)解達(dá)到滿意誤差界內(nèi)，算法結(jié)束，由BX逆映射回βg,n；否則轉(zhuǎn)到步驟5)繼續(xù)進(jìn)行。

2.3 算法復(fù)雜度分析

若對(duì)每個(gè)組播組用戶(hù)直接進(jìn)行子載波分配求解目標(biāo)函數(shù)，計(jì)算復(fù)雜度為O(GN)，其需要對(duì)所有種組合情況進(jìn)行分析以找到最優(yōu)解。隨著組播用戶(hù)規(guī)模增大，其復(fù)雜度呈指數(shù)增長(zhǎng)，復(fù)雜度較高。文獻(xiàn)[14]采用遺傳算法求解，計(jì)算復(fù)雜度為O(PGNK)，其復(fù)雜度呈線性增長(zhǎng)。本文采用人工魚(yú)群算法求解目標(biāo)函數(shù)時(shí)，每條人工魚(yú)執(zhí)行一次覓食行為、聚群行為、追尾行為時(shí)最多計(jì)算t次系統(tǒng)吞吐量，所以人工魚(yú)群算法在求解最優(yōu)解時(shí)計(jì)算復(fù)雜度為O(3Pmt)，復(fù)雜度較低。

3 仿真結(jié)果與分析

3.1 仿真參數(shù)

仿真實(shí)驗(yàn)中，考慮基于OFDMA組播無(wú)線系統(tǒng)的單小區(qū)網(wǎng)絡(luò)，本文設(shè)置組播用戶(hù)隨機(jī)分布在500 m×500 m小區(qū)范圍內(nèi)，信道模型的仿真參數(shù)設(shè)置參考文獻(xiàn)[7]，K-means聚類(lèi)分組的比例系數(shù)為0.32。人工魚(yú)群算法的控制參數(shù)設(shè)置為：人工魚(yú)數(shù)目P=50，最大迭代次數(shù)m=100，視野范圍v=7，擁擠度因子d=2，嘗試次數(shù)t=10，移動(dòng)步長(zhǎng)st=a×v，a∈(0,1)為視步系數(shù)[25]，具體仿真參數(shù)如表1所示。

表1 仿真參數(shù)

3.2 性能分析

圖3顯示了基于最大最小距離K-means算法的分組結(jié)果。可以看出，根據(jù)信噪比值的不同，小區(qū)內(nèi)隨機(jī)分布的20個(gè)用戶(hù)被自動(dòng)劃分為三組。

圖3 分組結(jié)果

圖4顯示了不同分組方案下，組播組個(gè)數(shù)與系統(tǒng)吞吐量的關(guān)系。可以看出，三種分組算法的系統(tǒng)吞吐量先隨組播組的個(gè)數(shù)增大而呈上升趨勢(shì)，這是因?yàn)橥ㄟ^(guò)對(duì)組播組分組之后，組播組內(nèi)用戶(hù)間的信道質(zhì)量相近，使組播組內(nèi)信道質(zhì)量最差的用戶(hù)得到改善，從而使系統(tǒng)吞吐量增大；當(dāng)組播組的個(gè)數(shù)大于3時(shí)，系統(tǒng)吞吐量略有下降，這是因?yàn)殡S著組播組個(gè)數(shù)的不斷增加，每個(gè)組所分到的資源減少。當(dāng)G=3時(shí)，本文的分組算法系統(tǒng)吞吐量達(dá)到了最大2.23 Mbit/s。由于所提分組算法得到的組播組個(gè)數(shù)也是3，這驗(yàn)證了該分組方法能夠合理的計(jì)算G值，使系統(tǒng)吞吐量達(dá)到最佳。因此，本文選擇G=3作為該場(chǎng)景的分組數(shù)以實(shí)現(xiàn)系統(tǒng)吞吐量最大化。數(shù)值仿真結(jié)果表明，本文算法相比于文獻(xiàn)[8]固定組大小的分組方案和隨機(jī)分組方案性能提升了2%和4.5%。

圖4 組播組個(gè)數(shù)與系統(tǒng)吞吐量關(guān)系

圖5顯示了AFSA子載波分配方法的收曲線。分別考慮K=20、N=16和K=20、N=32兩種情況下，AFSA子載波分配算法的收斂性。可以看出，隨著子載波數(shù)量N的增大，本文方法在10次迭代內(nèi)可以得到最優(yōu)解，體現(xiàn)出良好的收斂性能。

圖5 AFSA子載波分配方法的收斂曲線

圖6顯示了AFSA、GA和CMS的系統(tǒng)吞吐量對(duì)比圖。可以看出，對(duì)于不同的N值，AFSA的性能優(yōu)于GA和CMS，原因是在傳統(tǒng)組播中子載波的數(shù)量越大，用戶(hù)遇到不可用的子信道的概率就越高，從而限制了系統(tǒng)吞吐量。相反，本文通過(guò)在聚類(lèi)分組策略下，進(jìn)行子載波分配，可以將信道條件較差的用戶(hù)分隔到某些子組，提高系統(tǒng)吞吐量。仿真結(jié)果表明，AFSA相比較GA和CMS系統(tǒng)吞吐量提升了5.3%和16%。因此，證明了本文方法的有效性。

圖6 AFSA、GA和CMS的系統(tǒng)總吞吐量比較圖(G=3)

4 結(jié) 語(yǔ)

針對(duì)傳統(tǒng)組播在5G通信系統(tǒng)中吞吐量較低的問(wèn)題，提出一種最大最小距離K-means組播分組策略與改進(jìn)的人工魚(yú)群算法的子載波分配方法。數(shù)值仿真結(jié)果表明，相對(duì)于傳統(tǒng)組播和遺傳算法，本文算法的系統(tǒng)吞吐量分別提升16%和5.3%。