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

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

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

0 引 言

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

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

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

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

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

1 模型分析

1.1 系統模型

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

(1)

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

(2)

圖1 組播系統模型

1.2 問題建模

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

(3)

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

rk,n=wlog2(1+η)

(4)

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

(5)

根據組播系統吞吐量的定義[14]，組播系統總吞吐量可表示為：

(6)

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

(7)

(8)

(9)

(10)

(11)

(12)

(13)

(14)

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

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

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

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

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

(15)

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

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

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

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

(3) 計算剩余樣本數據到現有初始聚類中心的距離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)表示系統所消耗的子載波數不超過總載波數。式(20)表示基站向每個組播子組傳輸數據速率須大于等于子組的最小數據速率，其最小數據速率Rmin為1 Mbit/s[8]，保證組內用戶正確解碼。

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

圖2 人工魚的編解碼結構

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

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

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

2) 依據人工魚的編碼結構，產生可用子載波分配矩陣L1來確定優化維數D，然后隨機產生人工魚向量Xi=(xi1,xi2,…,xiD)，i=1,2,…,P。

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

4) 人工魚的行為定義：

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

Xj=Xi+v·rand()

(21)

(22)

Xnext=Xi+st·rand()

(23)

式中：rand()表示產生隨機數的函數。

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

(24)

(25)

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

(26)

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

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

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

2.3 算法復雜度分析

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

3 仿真結果與分析

3.1 仿真參數

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

表1 仿真參數

3.2 性能分析

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

圖3 分組結果

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

圖4 組播組個數與系統吞吐量關系

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

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

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

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

4 結 語

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