基于貪婪策略的低復(fù)雜度功率分配算法

袁偉娜， 王艷龍， 劉偉婷， 郭逸飛， 王碩恒

（華東理工大學(xué)信息科學(xué)與工程學(xué)院，上海 200237）

移動(dòng)用戶數(shù)的爆炸式增長(zhǎng)使得5G將會(huì)面臨海量用戶的接入[1-2]，而傳統(tǒng)的多址接入技術(shù)已無法滿足更高的容量要求，因此急需改進(jìn)現(xiàn)有的多址接入技術(shù)，由此，日本DoCoMo公司提出了功率域非正交多址接入 (Non-Orthogonal Multiple Access，NOMA)[3]技術(shù)。

NOMA的基本思想是在發(fā)送端發(fā)送疊加信號(hào)主動(dòng)引入干擾信息，然后在接收端根據(jù)串行干擾消除技術(shù)進(jìn)行解調(diào)[4-6]。因而如何在發(fā)送端進(jìn)行功率分配，對(duì)提高系統(tǒng)的吞吐量和降低用戶間多址干擾有很大的影響[7]。

根據(jù)文獻(xiàn)[8]的總結(jié)，目前對(duì)NOMA系統(tǒng)性能的關(guān)注主要集中在能量效率(EE)、用戶公平性(MMF)、系統(tǒng)吞吐量(SF)這3個(gè)方面。文獻(xiàn)[9]提出了提高NOMA系統(tǒng)能量效率的功率分配算法；文獻(xiàn)[10-11]詳細(xì)研究了最大化用戶間公平性的功率分配算法；文獻(xiàn)[12]提出的全空間搜索的功率分配（Full Search Power Allocation，F(xiàn)SPA）算法采用枚舉法計(jì)算出各種功率分配情況下的吞吐量，可使總吞吐量達(dá)到理論上的最優(yōu)值，但由于較高的計(jì)算復(fù)雜度，實(shí)用性較差。文獻(xiàn)[13]提出了具有較低復(fù)雜度的固定功率分配 (Fixed Power Allocation，F(xiàn)PA) 算法及分?jǐn)?shù)階功率分配 (Fractional Transmit Power Allocation, FTPA) 算法，但FPA沒有考慮實(shí)際的信道質(zhì)量，吞吐量性能較差；FTPA考慮了信道質(zhì)量及路徑損耗等問題，但由于功率分配方式簡(jiǎn)單，算法的性能仍有待提高。目前的研究工作主要集中在保證服務(wù)質(zhì)量（QoS）以及給不同用戶分配不同權(quán)值這兩種方向。文獻(xiàn)[14]基于這樣的思路，提出了一種吞吐量接近理論最優(yōu)值、且具有較低復(fù)雜度的功率分配算法。

本文根據(jù)SIC接收機(jī)的特點(diǎn)及用戶間的功率關(guān)系，提出了一種新的基于貪婪策略的功率分配算法。首先對(duì)用戶進(jìn)行排序及動(dòng)態(tài)分組，然后進(jìn)行局部吞吐量最優(yōu)判斷，并留下每組中的最優(yōu)情況，其余的進(jìn)行刪除處理。該算法成功地將FSPA算法的復(fù)雜度從隨用戶數(shù)指數(shù)級(jí)的增長(zhǎng)降低到線性級(jí)的增長(zhǎng)，并且保證了吞吐量性能基本相同。最后通過仿真對(duì)比分析了上述幾種主要算法的吞吐量性能，從而驗(yàn)證了本文算法的優(yōu)勢(shì)所在。

1 NOMA系統(tǒng)

本文中子信道之間仍采用正交頻分多址(Orthogonal Frequency Division Multiple Access,OFDMA）技術(shù)[15-16]，而一個(gè)子信道由多個(gè)用戶共享。圖1示出了NOMA系統(tǒng)頻帶資源分布，其中N為單個(gè)子信道上同時(shí)復(fù)用的用戶數(shù)，βmn為用戶的功率分配系數(shù)。設(shè)各子信道分配的總功率相等，則單個(gè)子信道的總功率pk=pBS/m，其中pBS為基站發(fā)射總功率，m為子信道數(shù)。由于經(jīng)OFDMA技術(shù)可濾除其他子信道干擾，所以本文主要研究單個(gè)子信道內(nèi)下行鏈路的功率分配問題。

圖1 NOMA系統(tǒng)頻帶資源分布Fig. 1 Frequency band of NOMA

圖2示出了一個(gè)基站兩用戶下行鏈路NOMA系統(tǒng)模型。系統(tǒng)為單發(fā)射、單接收天線，兩用戶需要發(fā)射的信號(hào)分別為x1,x2, 發(fā)射功率為pi，則疊加信號(hào)為

圖2 兩用戶下行鏈路NOMA系統(tǒng)模型Fig. 2 Downlink NOMA system model for two users

根據(jù)香農(nóng)定理，可得兩用戶的吞吐量分別為

實(shí)際系統(tǒng)中，一個(gè)子信道上肯定不止兩用戶在復(fù)用，為不失一般性，假設(shè)用戶數(shù)為N，根據(jù)信噪比(SINR)大小降序排列后的用戶數(shù)組可表示為{UE1,UE2,···,UEN}，則用戶n的接收信號(hào)為

式中：hn為用戶n的信道增益；xk為用戶k的傳輸信號(hào)；pk為其分配的功率；In為小區(qū)間干擾；nn為高斯白噪聲?？紤]到小區(qū)遠(yuǎn)近效應(yīng)的影響，小區(qū)邊緣用戶由于信噪比較低會(huì)被分配更大的功率，所以式(5)改寫為

經(jīng)過SIC接收機(jī)處理后，用戶n的信噪比可表示為

根據(jù)香農(nóng)定理可以得出吞吐量：

2 基于貪婪策略的功率分配算法

2.1 功率分配算法原理

由式（8）可知，對(duì)于用戶n，無論前面的n?1個(gè)用戶的分配情況怎么變化，只要當(dāng)前狀態(tài)確定，局部的吞吐量就確定，且更下層用戶的分配情況也不會(huì)影響當(dāng)前的吞吐量性能，即本文的貪婪策略滿足無后效性，最終解是全局最優(yōu)的。具體的處理過程可以用一種數(shù)據(jù)結(jié)構(gòu)中典型的樹結(jié)構(gòu)來體現(xiàn)，如圖3所示。式中：?為最小間隔。

圖3 本文算法樹狀結(jié)構(gòu)圖Fig. 3 Tree structure of this paper

算法步驟如下：

（3）局部最優(yōu)判斷，刪除多余分支。首先對(duì)與用戶n相連的下一層的Snk計(jì)算其功率分配系數(shù)和:?n=?n?1+βn,其中 ?n?1為上一層和節(jié)點(diǎn)的功率分配系數(shù)之和。接下來把 ?n相同的路徑分配到同一組，如結(jié)構(gòu)圖中所示匯集到同一個(gè)Sn點(diǎn)。然后根據(jù)計(jì)算式Tn=Tn?1+Rn對(duì)每組中所有的功率分配組合進(jìn)行吞吐量計(jì)算，其中Tn?1為上層連至根節(jié)點(diǎn)的所有用戶吞吐量之和，Rn根據(jù)式（8）進(jìn)行計(jì)算。同一組的分支中，最終只留下可使吞吐量達(dá)到最大的一個(gè)分支，其余分支做刪除處理。這樣使得每層的和節(jié)點(diǎn)都與其上一層的某個(gè)和節(jié)點(diǎn)有且僅有一條幸存支路相連，保證了樹結(jié)構(gòu)的正確性。

（4）最后一層處理及輸出最優(yōu)路徑。最后一層只有一個(gè)分組即 ?N=1 ，且每個(gè)節(jié)點(diǎn)下只有一個(gè)分支 βN=1??N?1, 經(jīng)判斷，留下使最終的吞吐量TN達(dá)到最大的分支。根據(jù)這個(gè)唯一的分支，自下向上遍歷至根節(jié)點(diǎn)，輸出使總吞吐量達(dá)到最大的全局最優(yōu)的功率分配組合 { β1,β2,···,βN} 。

2.2 復(fù)雜度計(jì)算及分析

本文算法的時(shí)間頻度T(n) 為需要搜索的功率分配組合的數(shù)量，即整個(gè)樹狀結(jié)構(gòu)所需處理的總分支數(shù)，求解過程如下：

3 仿真分析

3.1 仿真參數(shù)選取

將本文算法與文獻(xiàn)[14]算法進(jìn)行了仿真分析比較。為使仿真結(jié)果更接近實(shí)際情況，仿真參數(shù)主要選自LTE規(guī)范[18-20]，見表1。

圖4 4個(gè)用戶的樹結(jié)構(gòu)圖Fig. 4 Tree structure of 4 users

表1 主要的仿真參數(shù)Table 1 Simulation parameters

3.2 仿真結(jié)果及分析

圖6示出了FSPA算法與本文算法的吞吐量對(duì)比結(jié)果。用3種散點(diǎn)值分別代表FSPA算法的3種吞吐量，用3種線型來代表本文算法的3種吞吐量。從仿真結(jié)果不難發(fā)現(xiàn)，點(diǎn)線之間接近擬合，說明本文算法在3種吞吐量性能評(píng)估上都非常接近于FSPA算法，也間接地驗(yàn)證了被舍棄刪除的支路的確是局部吞吐量性能更差的組合。本文算法的小區(qū)邊緣用戶的吞吐量更大，是因?yàn)榭紤]了用戶間的公平性，保證了小區(qū)邊緣用戶在同時(shí)復(fù)用的所有用戶中有著最大的功率分配因子。

圖5 3種算法復(fù)雜度對(duì)比Fig. 5 Complexity comparison of three algorithms

圖6 FSPA與本文算法的吞吐量對(duì)比Fig. 6 Throughout comparison between FSPA and this paper

3.2.2 系統(tǒng)吞吐量的對(duì)比仿真 圖7、圖8、圖9分別示出了文獻(xiàn)[14]算法、本文算法、FTPA算法、FPA算法在系統(tǒng)總吞吐量、幾何平均吞吐量、小區(qū)邊緣用戶吞吐量上的對(duì)比結(jié)果。其中FTPA算法和FPA算法的固定系數(shù)分別取使其能達(dá)到最優(yōu)解的0.7和0.1[13]。

圖7 4種算法總吞吐量對(duì)比Fig. 7 Overall cell throughout of four algorithms

圖8 4種算法幾何平均吞吐量對(duì)比Fig. 8 Geometric cell throughout of four algorithms

圖9 4種算法小區(qū)邊緣用戶吞吐量對(duì)比Fig. 9 Cell-edge user throughout of four algorithms

可以看出，在3種吞吐量的性能對(duì)比上，F(xiàn)PA算法與其他3種算法的差距較大，這與其自身較簡(jiǎn)單的功率分配策略有關(guān)。本文算法和文獻(xiàn)[14]算法的各種吞吐量性能基本一致，非常接近理論最優(yōu)值且都明顯優(yōu)于FTPA算法。與文獻(xiàn)[14]算法平方級(jí)的復(fù)雜度相比，本文算法的線性級(jí)復(fù)雜度明顯具有更大的優(yōu)勢(shì)。

從圖8、圖9中可以看出，無論是采用哪種功率分配算法，幾何平均吞吐量及小區(qū)邊緣用戶吞吐量隨著同時(shí)復(fù)用的用戶數(shù)的增加，都會(huì)不可避免地逐漸減小，最終趨于平穩(wěn)。這主要是因?yàn)橄到y(tǒng)本身的時(shí)頻資源有限，且根據(jù)式（8）可知用戶間的干擾也會(huì)逐漸增加，導(dǎo)致信噪比隨之下降，以致每個(gè)用戶的吞吐量最終都會(huì)下降。

4 結(jié) 論

本文根據(jù)SIC的檢測(cè)原理及貪心算法中局部最優(yōu)判別的思想，提出了一種新的低復(fù)雜度功率分配算法，并用樹的結(jié)構(gòu)呈現(xiàn)出了這種思想。仿真分析發(fā)現(xiàn)，在和全空間搜索功率分配算法的總吞吐量非常接近的情況下，本文算法成功地把指數(shù)級(jí)增長(zhǎng)的復(fù)雜度降低成了線性級(jí)的增長(zhǎng)。而與其他的算法相比，本文算法也均具有不同程度的優(yōu)勢(shì)。