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

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

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

0 引 言

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

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

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

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

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

1 模型分析

1.1 系統(tǒng)模型

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

(1)

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

(2)

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

1.2 問題建模

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

(3)

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

rk,n=wlog2(1+η)

(4)

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

(5)

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

(6)

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

(7)

(8)

(9)

(10)

(11)

(12)

(13)

(14)

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

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

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

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

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

(15)

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

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

(1) 初始化參數(shù)?；就ㄟ^用戶反饋的信道狀態(tài)信息獲得k個用戶的信噪比η，這些信噪比η組成的樣本數(shù)據(jù)集為M={x1,x2,…,xk}。

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

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

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

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

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

2.2 人工魚群算法求解子載波分配問題

(16)

(17)

(18)

(19)

(20)

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

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

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

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

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

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

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

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

4) 人工魚的行為定義：

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

Xj=Xi+v·rand()

(21)

(22)

Xnext=Xi+st·rand()

(23)

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

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

(24)

(25)

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

(26)

5) 對人工魚個體Xi分別進行覓食、聚群、追尾和隨機行為，通過行為評價，選擇執(zhí)行食物濃度較大的行為。

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

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

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

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

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

3.1 仿真參數(shù)

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

表1 仿真參數(shù)

3.2 性能分析

圖3顯示了基于最大最小距離K-means算法的分組結(jié)果?？梢钥闯?，根據(jù)信噪比值的不同，小區(qū)內(nèi)隨機分布的20個用戶被自動劃分為三組。

圖3 分組結(jié)果

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

圖4 組播組個數(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)吞吐量對比圖?？梢钥闯?，對于不同的N值，AFSA的性能優(yōu)于GA和CMS，原因是在傳統(tǒng)組播中子載波的數(shù)量越大，用戶遇到不可用的子信道的概率就越高，從而限制了系統(tǒng)吞吐量。相反，本文通過在聚類分組策略下，進行子載波分配，可以將信道條件較差的用戶分隔到某些子組，提高系統(tǒng)吞吐量。仿真結(jié)果表明，AFSA相比較GA和CMS系統(tǒng)吞吐量提升了5.3%和16%。因此，證明了本文方法的有效性。

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

4 結(jié) 語

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