NOMA下行信道總速率最大化算法研究

鄒金妤 張足生 高佳曼 吳超超

(東莞理工學(xué)院 網(wǎng)絡(luò)空間安全學(xué)院，廣東東莞 523808)

在過去的二十多年中，隨著移動通信技術(shù)標(biāo)準(zhǔn)的不斷發(fā)展，基于正交頻分多址接入(Orthogonal Frequency Division Multiple Access，OFDMA)技術(shù)的第四代移動通信技術(shù)(4G)，已達(dá)到每秒數(shù)十兆比特的數(shù)據(jù)傳輸率，這適應(yīng)了當(dāng)時移動通信的發(fā)展需求。然而，隨著智能終端設(shè)備的廣泛使用，移動通訊的需求持續(xù)增長[1]，4G的傳輸速率已不能滿足當(dāng)下移動通信的發(fā)展需求，對無線傳輸速率提出了更高的要求。

按照IMT-2020(5G)推進(jìn)組發(fā)布的《5G愿景與需求白皮書》，第五代移動通信技術(shù)(5G)定位于頻譜效率更高、速率更快、容量更大的無線網(wǎng)絡(luò)，其頻譜效率與4G相比可以提高5～15倍[2]。NOMA已被納入5G標(biāo)準(zhǔn)，能夠帶來高速的數(shù)據(jù)傳輸和較低的系統(tǒng)延遲，并實現(xiàn)相對較高的頻譜利用率。

NOMA技術(shù)可以同時為多個用戶提供服務(wù)，通過疊加編碼(Superposition Coding，SC)技術(shù)，在發(fā)送端將多個用戶的疊加信號分配到同一時頻資源上；然后，利用串行干擾消除(Successive Interference Cancellation，SIC)技術(shù)，在接收端對用戶間存在的干擾進(jìn)行消減，從而完成基站到用戶的下行NOMA通信系統(tǒng)的數(shù)據(jù)傳輸[3]。因此，NOMA技術(shù)能夠為未來的無線通信系統(tǒng)獲得更高的吞吐量[4]。

通過NOMA技術(shù)，基站能同時與多個用戶進(jìn)行通信，也就是在下行信道上同時向多個用戶傳輸不同的數(shù)據(jù)流，但是如果將所有的用戶都疊加到同一信道上，這既不符合實際系統(tǒng)約束，還會造成數(shù)據(jù)的錯誤傳輸以及系統(tǒng)的解碼時延。在這種情況下，以最大化系統(tǒng)總速率為目標(biāo)，基站應(yīng)該如何選擇一個用戶子集來進(jìn)行數(shù)據(jù)傳輸，這還有待研究。

為此，本文研究NOMA下行信道的用戶選擇問題，以基站的發(fā)射功率和單個信道疊加的用戶數(shù)為約束條件來優(yōu)化系統(tǒng)的總速率。

1 相關(guān)研究

NOMA技術(shù)允許多個用戶共享同一時頻域資源，由此引入的用戶間干擾將會降低系統(tǒng)的性能，而通過合理的用戶選擇和功率分配可以減小這種干擾，所以關(guān)于這兩個問題的討論成了NOMA研究中的熱點。

1.1 NOMA用戶選擇算法

在NOMA系統(tǒng)中，同一信道上所疊加的用戶數(shù)量受實際系統(tǒng)的約束，為了減少用戶間的干擾，降低解碼時延，規(guī)避嚴(yán)重的錯誤傳播[5]，已有學(xué)者對于用戶選擇問題進(jìn)行了研究，以提高系統(tǒng)總的吞吐量。用戶選擇算法主要有隨機選擇、基于信道差異選擇和基于遍歷搜索的用戶選擇。

隨機用戶選擇算法[6]不依賴其他的限制條件，在用戶集合中，隨機地選擇疊加用戶。雖然復(fù)雜度很低，但是由于疊加用戶之間是隨機匹配的，沒有考慮用戶之間的疊加干擾，因此，不能保證用戶接入的公平性。

基于用戶信道差異的用戶選擇算法[7]，根據(jù)用戶疊加原理，當(dāng)疊加用戶之間的信道差異較大時，在功率分配過程中可以獲得較大的功率差異，便于接收端分離用戶的信息。由于考慮了疊加用戶之間的信道狀況，性能相對于隨機選擇有了很大提高，但當(dāng)信道差異較小時將會影響疊加組合的傳輸性能。

遍歷搜索的用戶選擇算法[8]基于比例公平調(diào)度(Proportional Fairness Scheduling，PF)準(zhǔn)則，通過對隨機的用戶組合進(jìn)行PF準(zhǔn)則值的計算和比較，找到在用戶容量與系統(tǒng)容量之間達(dá)到良好折中的疊加用戶組合。雖然性能優(yōu)勢明顯，但該算法的用戶迭代的復(fù)雜度較高。

1.2 NOMA功率分配算法

在NOMA系統(tǒng)中，基站會為服務(wù)的用戶分配功率，其中，用戶所分配功率的大小不僅決定著自身吞吐量的性能，還影響著疊加信號中的其他用戶的性能，進(jìn)而影響系統(tǒng)的總吞吐量。此外，由于在接收端需要根據(jù)用戶的發(fā)射功率進(jìn)行串行干擾消除，功率分配算法還會直接影響到后續(xù)的用戶信號檢測。因此，在NOMA系統(tǒng)中，為使基站可以更好地權(quán)衡用戶速率與系統(tǒng)整體容量性能之間的關(guān)系，給用戶合理地分配功率相當(dāng)關(guān)鍵。

文獻(xiàn)[9]提出了全空間搜索功率分配(Full Search Power Allocation，F(xiàn)SPA)算法，通過遍歷各種可能的用戶配對組合和功率分配方式，以獲得最佳的系統(tǒng)性能。但是，隨著用戶規(guī)模的增加，對于實際系統(tǒng)來說，功率搜索在計算上變得過于復(fù)雜。文獻(xiàn)[10]以最大化系統(tǒng)的幾何平均吞吐量為目標(biāo)，通過遺傳算法聯(lián)合優(yōu)化用戶分組和功率分配問題，雖然相較FSPA復(fù)雜度有所降低，但對兩個問題進(jìn)行聯(lián)合優(yōu)化本身就有著極高的計算難度和挑戰(zhàn)。文獻(xiàn)[11]使用Karush-Kuhn-Tucker(KKT)條件解決了在最大功率約束下最大化加權(quán)和速率的優(yōu)化問題。

從最大化多用戶比例公平的角度，文獻(xiàn)[12]提出一種基于瞬時用戶吞吐量加權(quán)和最大化的功率分配方案，其目標(biāo)函數(shù)在理論上是最佳的，因此NOMA系統(tǒng)能夠達(dá)到理論上的最佳性能。但是，該方法不易擴展到采用調(diào)制和編碼的實際系統(tǒng)中。為此，有學(xué)者提出了兩種簡化的次優(yōu)方案，分別為固定功率分配算法 (Fixed Power Allocation，F(xiàn)PA)[13]和分?jǐn)?shù)階功率分配算法(Fractional Transmit Power Allocation，F(xiàn)TPA)[14]。盡管這兩種簡化的方法具有非常低的計算復(fù)雜度，并且可以應(yīng)用于實際系統(tǒng)，但是它們的性能受到相對簡單的功率分配標(biāo)準(zhǔn)的限制，本文認(rèn)為可以通過增加功率約束加以改進(jìn)。

綜上所述，在具有大量用戶的NOMA下行系統(tǒng)中，用戶選擇算法研究已取得了一些成果。但是本文所關(guān)注的以基站發(fā)射功率為約束條件，選擇一個用戶子集，使得系統(tǒng)總速率最大是尚待研究的關(guān)鍵問題。

2 系統(tǒng)概述及問題建模

2.1 系統(tǒng)概述

1)疊加編碼技術(shù)。在NOMA系統(tǒng)中，發(fā)送端利用疊加編碼技術(shù)[15]將多個用戶的信號疊加在同一時頻域上，使得一個子信道可以同時接入多個用戶。假設(shè)系統(tǒng)中有兩個用戶和一個包含兩個點對點編碼器的發(fā)射機，用戶的輸入信息被兩個編碼器分別映射成兩個復(fù)信號，通過疊加編碼技術(shù)將這兩個復(fù)信號進(jìn)行疊加，圖1給出了兩個用戶信號在星座圖上的疊加過程，由圖可以看出，基站端發(fā)送的疊加信號是通過把具有較大功率的用戶1的正交相移鍵控(Quadrature Phase Shift Keying，QPSK)星座圖和具有小功率的用戶2的QPSK星座圖疊加起來得到的。

圖1 采用QPSK調(diào)制的用戶1和用戶2的疊加編碼

2)功率復(fù)用技術(shù)。在NOMA系統(tǒng)中，由于接收端以用戶間所分配的總功率為標(biāo)準(zhǔn)來劃分不同用戶，為此在發(fā)送端，移動通信基站必須對同一時頻資源塊上的各個疊加用戶進(jìn)行功率分配，以確保用戶間的功率各不相同。圖2將OFDMA系統(tǒng)和NOMA系統(tǒng)中的功率分配進(jìn)行對比，功率復(fù)用技術(shù)[16]使得基站覆蓋范圍內(nèi)的用戶獲得更大的可接入帶寬，從而極大地提高了NOMA網(wǎng)絡(luò)的吞吐量，增加了接入無線通信系統(tǒng)內(nèi)的用戶的公平性。

圖2 OFDMA系統(tǒng)和NOMA系統(tǒng)功率分配對比

通過疊加編碼和功率復(fù)用技術(shù)可以得到基站所發(fā)送的疊加信號，具體流程如圖3所示，利用正交相移鍵控、正交振幅調(diào)制等單載波調(diào)制技術(shù)，對每個用戶的比特流進(jìn)行調(diào)制，將每個調(diào)制信號的波形相加后得到基站發(fā)送的疊加信號x(t)：

圖3 疊加信號的形成過程

(1)

其中，M表示疊加用戶的數(shù)量，i表示任一疊加用戶，wi(i=1,2,…,M)表示用戶i的功率分配因子，P表示基站的發(fā)射功率，xi(t)表示用戶i的信號。

3)下行NOMA系統(tǒng)模型。圖4為NOMA系統(tǒng)下行信道發(fā)送和接收信號的處理流程，基站作為發(fā)射端，在同一時頻域上疊加用戶U1,U2,…,UM；U1,U2,…,UM作為接收端進(jìn)行解碼、重構(gòu)以及串行干擾消除。

圖4 下行NOMA系統(tǒng)模型

對于發(fā)射端，假設(shè)基站所服務(wù)的用戶數(shù)量為N，通過疊加編碼技術(shù)可以使多個用戶疊加在同一信道上，但是為了減少解碼時延與錯誤傳播，每個信道會設(shè)定最多可疊加的用戶數(shù)量閾值，假設(shè)為M。本文的目標(biāo)即為在基站發(fā)射功率的約束下，在N個用戶中最多選擇M個用戶，使得下行NOMA系統(tǒng)的總速率最大。

對于接收端，假設(shè)U1的信道狀態(tài)比U2差，U2的信道狀態(tài)比U3差，以此類推，UM的信道狀態(tài)最好。其中，信道狀態(tài)越好的用戶所分配的功率越小[3]，所以UM具有最小的發(fā)射功率。對于接收機來說，最先識別到強用戶的信號，若想正確解調(diào)出UM的信號，終端要先逐次對U1,U2,…,UM-1的信號解碼、重構(gòu)以及串行干擾消除，最后才能解碼出UM的信號。

2.2 問題建模

本節(jié)問題建模參考了Wan P J等人的研究成果。在下行NOMA系統(tǒng)中，假設(shè)基站的發(fā)射功率為P，基站所服務(wù)的用戶集合為U，其中編號依次為1，2，…，N，共包含N個用戶；用戶的有效噪聲為a，系統(tǒng)容量域包含的速率分配為x，則P滿足下式：

(2)

其中，P>0，i表示用戶集合U中的任一用戶，ai表示第i個用戶的有效噪聲，ai-1表示第i-1個用戶的有效噪聲，aN表示第N個用戶的有效噪聲，并且用戶的有效噪聲滿足a0=0，a1≤a2≤…≤aN。

對于一個非空的用戶子集S，集合中所有用戶的功率需求為p(S)，其表達(dá)式如下：

(3)

其中，i表示用戶子集S中的任一用戶，ri表示用戶i的速率需求且ri>0，r(S>i)表示子集S中在用戶i后面的所有用戶的總速率需求。當(dāng)子集S不為空時，集合中所有用戶的速率需求為r(S)，其表達(dá)式如下：

r(S)=∑i∈Sri.

(4)

在下行NOMA系統(tǒng)中，假設(shè)單個信道最多可疊加的用戶數(shù)量為M。在不失一般性的前提下，假設(shè)每個用戶的功率需求最多為P，本文以基站的發(fā)射功率和單個信道疊加的用戶數(shù)量為約束條件來優(yōu)化系統(tǒng)總速率，具體定義如下。

定義1：當(dāng)|S|≤M且p(S)≤P時，在用戶集合U中選擇子集S，使其總速率需求r(S)最大。其中，|S|表示集合S中的用戶數(shù)量，p(S)表示集合S中所有用戶的功率需求。

3 用戶選擇算法

針對NOMA下行信道上的用戶選擇問題，利用枚舉法可以獲得系統(tǒng)的最優(yōu)解，但該算法具有指數(shù)級的時間復(fù)雜度，隨著用戶數(shù)量的提高將難以計算，對此，Wan P J等人提出了松弛貪婪算法，可以在降低時間復(fù)雜度的前提下獲得系統(tǒng)近似最優(yōu)解，本文將該算法與本文所提算法進(jìn)行對比分析。首先，提出一種基于貪婪策略的用戶選擇算法，能夠在多項式時間內(nèi)獲得近似最優(yōu)系統(tǒng)總速率;之后，為了進(jìn)一步得到最優(yōu)系統(tǒng)總速率，在此基礎(chǔ)上又提出基于分支限界的用戶選擇算法，從而實現(xiàn)了用戶選擇優(yōu)化和算法時間復(fù)雜度之間的平衡。

3.1 松弛貪婪算法

松弛貪婪算法是一種多項式時間的用戶選擇近似算法，基于松弛策略，通過數(shù)學(xué)建模將用戶選擇問題轉(zhuǎn)化為優(yōu)化問題，以最大化系統(tǒng)總速率為目標(biāo)建立目標(biāo)函數(shù)，在所選用戶集滿足功率約束的前提下，使得目標(biāo)函數(shù)值達(dá)到最大。而松弛策略的主要目的是放松可行解的約束條件，擴大可行域的范圍，使得松弛后的優(yōu)化問題可以在多項式時間內(nèi)求得，并通過修正的方式將松弛后優(yōu)化問題的解轉(zhuǎn)化為原問題用戶選擇的解，從而解決用戶選擇問題。

3.2 基于貪婪策略的用戶選擇算法 (GR)

在進(jìn)行用戶選擇時，將用戶按速率降序排列，通過貪婪策略，總是把當(dāng)前步驟中滿足功率約束的最好的選擇作為目標(biāo)用戶子集，具體算法如表1所示。

表1 基于貪婪策略的用戶選擇算法

3.3 基于分支限界的用戶選擇算法(BR)

分支限界是以廣度為優(yōu)先的方式對解空間樹進(jìn)行搜索，以便得到最佳解的算法。關(guān)于最大化問題，在查找過程中，可以利用限界函數(shù)估計所有子結(jié)點目標(biāo)函數(shù)的可能取值，從中選取使目標(biāo)函數(shù)取最大值的子結(jié)點為擴展結(jié)點，然后展開下一個查找，并通過不斷調(diào)整查找方向來迅速地找出所求問題的最佳解。具體算法如表2所示。

表2 基于分支限界的用戶選擇算法

其中，目標(biāo)函數(shù)為：arg maxr(S)=∑i∈Sri，下面對于算法中的三個關(guān)鍵問題進(jìn)行分析：

1)解空間的構(gòu)造方法。將用戶集合U中的速率降序排列，以此作為分支限界解空間結(jié)點的生成順序；

2)約束規(guī)則的確定。以p(S)≤P為約束條件，判斷結(jié)點是否進(jìn)行分支；

3)目標(biāo)函數(shù)的邊界評估方法。目標(biāo)函數(shù)的下界down：如表1所示，通過貪婪法求解用戶集合D，將集合D中的用戶總速率r(D)作為目標(biāo)函數(shù)的下界。

目標(biāo)函數(shù)的上界up：在部分解r(G)的基礎(chǔ)上，從用戶集合U中選擇不屬于集合G的至多(M-|G|)個用戶添加到集合G中，判斷每個用戶在添加到集合G后是否滿足功率約束，篩選滿足條件的用戶加入集合G，將此時的r(G)作為目標(biāo)函數(shù)的上界。即：限界函數(shù)

(5)

其中，r(G)表示集合G中用戶的總速率，|G|表示集合G中用戶的數(shù)量，UG表示屬于集合U但不屬于集合G的用戶。

4 實驗

4.1 復(fù)雜度分析

對于NOMA下行信道上的用戶選擇問題，GR算法和松弛貪婪算法取得相對較優(yōu)系統(tǒng)總速率，而枚舉算法[17]和BR算法可得到最大系統(tǒng)總速率。假設(shè)基站中的用戶數(shù)量為N，單個信道可疊加的用戶數(shù)量為M，為了得到相對較優(yōu)總速率，GR算法以及松弛貪婪算法的時間復(fù)雜度為O(NlogN)；為了得到最大總速率，枚舉算法的復(fù)雜度為O(NM)，BR算法為O(2N)。

枚舉算法是在功率約束下解決用戶選擇問題的最優(yōu)算法，通過理論分析可以看出，隨著用戶數(shù)量的增加，枚舉算法具有很高的時間復(fù)雜度，可行性較差。本文提出的BR算法也可以得到用戶選擇問題的最優(yōu)解，并且在得到最大總速率的前提下，通過有效選擇目標(biāo)函數(shù)的上界在一定程度上降低了枚舉算法的時間復(fù)雜度。而GR算法和松弛貪婪算法是解決用戶選擇問題的近似算法，本文提出的BR算法與其相比結(jié)果更優(yōu)。

4.2 仿真分析

為了評估GR算法、松弛貪婪算法以及BR算法解決用戶選擇問題的性能，本節(jié)對NOMA下行信道系統(tǒng)進(jìn)行仿真，并通過Matlab平臺對算法的性能進(jìn)行驗證。仿真過程中用到的參數(shù)如表3所示。

表3 仿真參數(shù)

當(dāng)疊加用戶數(shù)M分別為2、4、6時，隨著用戶數(shù)量的增加，GR算法、松弛貪婪算法以及BR算法的性能對比如圖5、圖6、圖7所示。從圖中可以看出，GR算法的總速率略高于松弛貪婪算法，性能提升了2.6%左右。這是因為松弛貪婪算法采用松弛策略擴大了可行域的范圍，在此基礎(chǔ)上得到一個用戶集合，通過去除集合內(nèi)不滿足功率約束的用戶得到目標(biāo)用戶子集，由于還要進(jìn)一步去除最后一個滿足功率約束的用戶，造成一定的誤差，導(dǎo)致系統(tǒng)性能降低。因此，GR算法與其相比具有更優(yōu)的性能。而本文的BR算法選取了較好的目標(biāo)函數(shù)的上界，有效地對解空間樹進(jìn)行剪枝，從而在一定程度上降低了算法時間復(fù)雜度，并且達(dá)到最大系統(tǒng)總速率，實現(xiàn)了用戶選擇優(yōu)化和算法時間復(fù)雜度之間的平衡。所以，本文的BR算法與松弛貪婪算法相比，性能提升了6.1%左右，具有較優(yōu)的總速率。

圖5 不同用戶選擇算法下的性能對比(M=2)

圖6 不同用戶選擇算法下的性能對比(M=4)

圖7 不同用戶選擇算法下的性能對比(M=6)

當(dāng)用戶數(shù)分N別為10、20、30時，隨著疊加用戶數(shù)量的增加，GR算法、松弛貪婪算法以及BR算法的性能對比如圖8、圖9、圖10所示。從圖中可以看出，在用戶數(shù)量不同時，隨著疊加用戶數(shù)量的增加，三個算法的性能相對平穩(wěn)。其中，本文BR算法與GR算法以及松弛貪婪算法相比，其性能最優(yōu)，提升了約3.1%、5.9%。BR算法可以得到系統(tǒng)最大總速率，并通過有效平衡最大總速率與算法時間復(fù)雜度，使得算法的可行性較強。

圖8 不同用戶選擇算法下的性能對比(N=10)

圖9 不同用戶選擇算法下的性能對比(N=20)

圖10 不同用戶選擇算法下的性能對比(N=30)

5 結(jié)語

在下行NOMA系統(tǒng)中，以最大化總速率為目標(biāo)研究了下行信道的用戶選擇問題。給定N個下行用戶，單個信道最多可以疊加M個用戶，在基站發(fā)射功率的約束下，提出了基于分支限界的用戶選擇算法對接入同一子信道的多個用戶進(jìn)行選擇，使得系統(tǒng)內(nèi)的總速率最大。仿真結(jié)果表明，本文提出的基于分支限界的用戶選擇算法與傳統(tǒng)算法相比，可以得到下行NOMA系統(tǒng)最優(yōu)總速率，也極大地降低了算法的時間復(fù)雜度。