基于OFDMA系統的改進型功率分配貪婪算法研究

張天瑜

(無錫市廣播電視大學 機電工程系，江蘇 無錫 214011)

作為對抗寬帶無線通信傳輸過程中頻率選擇性衰落的有效手段，正交頻分復用OFDM(Orthogonal Frequency Division Multiplexing)正受到越來越多的關注。對于多用戶的OFDM系統，由于傳輸路徑各不同，并且各用戶的信道衰落是相互獨立的，因此，這就使得對于某一用戶發生衰落嚴重的子載波對于其他用戶也發生嚴重衰落的可能性極小。利用這個特性，正交頻分多址OFDMA(Orthogonal Frequency Division Multiple Access)依據各個用戶的信道條件和相應的優化準則，將OFDM符號的子載波動態地分配給不同的用戶，相對于頻分多址FDMA(FrequencyDivisionMultipleAccess)、時分多址 TDMA(Time Division Multiple Access)，OFDMA可以實現通信系統總體的頻譜效率和功率資源的優化。OFDMA系統利用子載波的正交特性來實現用戶的多址接入，系統中的資源調度模塊可以利用多用戶分集和信道衰落特性，根據信道增益自適應地進行資源分配，能夠明顯地提高OFDMA系統的吞吐量。

目前，常見的兩種最優化自適應資源分配算法分別是邊緣自適應MA(Margin Adaptive)算法和速率自適應RA(Rate Adaptive)算法。MA算法的目標是在滿足各個用戶傳輸速率的前提下，根據各個用戶的瞬時信道狀況，動態地為用戶分配子載波，并確定在各個子載波上傳輸的比特和功率，使總的發射功率達到最小值。而RA算法的目標是在總的發射功率和每一個用戶的最小速率的限制下，動態分配系統資源，使得OFDMA系統的吞吐量達到最大值。

功率分配是一個經典的研究問題，迭代注水功率分配算法是其理論上界[1]，但是需經多次的迭代運算才能求出吞吐量達到最大值時的最優解。參考文獻[2]詳細地討論了在線性條件下功率分配的方案。參考文獻[3]研究了在功率約束下，OFDMA系統的吞吐量達到最大值時的功率分配問題，給出了在用戶間速率成比例和高信噪比限定條件下的線性功率分配算法。這種算法簡化了運算，不需進行迭代運算，但該算法只關注吞吐量達到最大值，忽視了功率分配時用戶間的公平性能。此外，通過研究發現，系統的吞吐量與用戶間的公平性能是相互矛盾的[4-8]。本文在研究上述各種功率分配算法基礎上，在公平約束條件下，提出一種改進型功率分配貪婪算法。該算法根據用戶請求進行子載波的預分配，不僅可以有效地實現每個用戶具體的比特分配和功率分配，而且可以在OFDMA系統的吞吐量與用戶間的公平性能之間尋求到一個理想的平衡點。

1 OFDMA系統模型

在OFDMA系統資源的分配中，用戶間公平性能和用戶服務質量QoS(Quality of Service)性能的保證主要是在分配子載波和功率給用戶時考慮的問題。如果用戶間的公平性能達不到合理的要求，就會導致某些用戶的數據傳輸速率太低，甚至會讓用戶放棄服務。

假設OFDMA系統的用戶數為K，系統的子載波個數為N，并且一個子載波在同一時刻只能夠被1個用戶所占用，系統的可用帶寬為B，用戶k在子載波j上的信道增益為 gk，j；加性高斯白噪聲 AWGN(Additive White Gaussian Noise)的方差為 σ2=N0B/N。 其中，N0為加性高斯白噪聲的單邊功率譜密度；相應的信道噪聲功率比為Hk，j=g2k，j/σ2；第 k 個用戶在第 j個子載波上分得的功率為 pk，j，若第 j個子載波分配給了第 k個用戶，則 pk，j=1，否則，pk，j=0。

基于以上的假設，在RA算法中，最優化自適應資源分配的數學模型可以構建為：

式中，C為系統的吞吐量；ρk，j為子載波占用概率。

并且滿足以下條件：

式(4)表示一個子載波在同一時刻僅可以分配給一個用戶所使用。

式中，PT表示所有子載波的功率和，PC為系統可用的總功率。

上述的最優化自適應資源分配的數學模型是一個非確定多項式NP(Nondeterministic Polynomial)問題，簡化上述NP問題的一個辦法就是把上述的聯合子載波－功率分配方案分成兩步來完成：(1)分配子載波；(2)確定各子載波的功率、調制方式和加載比特數[9-12]。通常由于OFDMA系統已經按照子載波的調度算法對子載波完成了分配，因此只需討論子載波的功率分配問題。

2 迭代注水功率分配算法

迭代注水功率分配算法是以OFDMA系統的吞吐量達到最大值為目標的。對于這個優化問題，根據式(1)，利用Lagrange算法，構造Lagrange函數：

為了求出 pk，j，使得式(1)達到最大值，對式(6)求偏導數，并令其偏導數為0，可得：

令 β=λln2，通過式(7)可以計算出：

式中，[1/β-1/Hk，j]+表示當 1/β-1/Hk，j＞0 時，pk，j=1/β-1/Hk，j；當 1/β-1/Hk，j＜0 時，pk，j=0。

最后，利用迭代算法計算出一個適當的功率注水門限β，由此就可以確定出最優的功率分配。因此，這種功率分配算法被稱為迭代注水功率分配算法。

利用迭代算法計算β的過程為：

(1)設定 β的初始值

(2)修正β的迭代方法

式中，μ為調整步長，0＜μ＜1；NON為本次實際分配功率的子載波總數。

3 改進型功率分配貪婪算法

由于迭代注水功率分配算法只關注吞吐量達到最大值，而忽視了功率分配時用戶間的公平性能，即子載波信道狀態好的功率分配較多，而子載波信道狀態差的功率分配較少甚至是不分配。為此，需要對迭代注水功率分配算法進行改進。針對OFDMA-TDD系統下行鏈路的功率分配，在公平約束條件下，提出一種改進型功率分配貪婪算法。該算法考慮在保證用戶公平性能的條件下，通過迭代分配比特和相應的功率，每次選擇吞吐量增量與功率增量比值最大的子載波來分配功率，使每功率單位所帶來的吞吐量達到最大值。

公平約束條件設置為：

式中，x%為時分雙工 TDD(Time Division Duplex)的下行比例因子;rk為用戶k的下行數據傳輸速率;Rk為用戶k的下行流量;ravg為所有用戶的平均下行數據傳輸速率；δ為公平因子；x%rk＞Rk表示用戶 k的下行流量能被系統全部傳輸；rk＞δravg表示用戶k的下行數據傳輸率高于一定的公平限定值。

在OFDMA系統中，各子載波分配到的比特數目決定了該子載波所采用的調制方式。假設第i個子載波在某一符號期間分配到bj個比特數據，則該子載波應該采用多電平正交幅度調制MQAM(Multilevel Quadrature Amplitude Modulation)，其中 M=2bj。在調制時，不同的調制方式對發射功率的要求是不相同的。對于QAM調制方式，由于矩形QAM星座包括4QAM、16QAM和64QAM等，因此在星座圖中的每個星座點所對應的調制比特數量bj分別為 2、4、6 等。

假設子載波的傳輸功率增量為Δpk，用戶分配到的功率為pa，用戶的功率增量為Δp，則改進型功率分配貪婪算法的流程為:

當 pa+Δp＜pC時，存在功率余量，做以下的循環：

(1)對所有子載波j，計算其功率增量：式中，Δbj為子載波的相鄰調制比特數與當前調制比特數的差值，P(j，bj)為子載波 j每傳輸 bj比特時所需分配的功率。

式中，Hk，j為子載波 j的信道噪聲功率比，Γ為與物理層編碼調制關聯的冗余量。考慮傳輸的誤碼率為BER和物理層編碼調制方式為MQAM與格雷編碼聯合時，Γ=-ln(5BER)/1.5。

(2)如果 pa+Δpj＞pC，則令 pj=+∞。 這樣第 j個子載波就不會在下面的步驟(5)中被選擇。

(3)計算功率每增加Δpj所產生的吞吐量增量：

式中Bs為子載波的帶寬。

(4)令min為用戶k下行數據傳輸率的最小值，即保證公平性能的最小吞吐量。

(5)對于所有的子載波，在公平約束條件下，計算最優的子載波j*：

式中arg為輻角計算。

其公平約束條件設置為：

(6)將功率分配給選定的子載波 j*：Δp=Δpj*。

(7)如果 pa+Δp＜pC，則表明還有功率余量，更新以下參數：

(8)返回到開始進行條件判斷及下一次分配，直至確定每個子載波上的調制方式和分配到的功率。

4 仿真實驗與結果分析

改進型功率分配貪婪算法是在確定子載波后執行的，因此可以利用多用戶情況下功率分配后的吞吐量變化來分析該算法的性能。在仿真實驗中，假設接收端的同步和信道估計良好，考慮單小區OFDMA系統的下行鏈路數據傳輸，系統帶寬為1 MHz，劃分為 64個子載波。子載波上可分配的最大比特數為6，不采用信道編碼。無線信道模型是COST207中的高密度建筑城區，即BadUrban模型，時延擴展為 2.5 μs。信道狀態信息抽樣間隔為0.5 ms，系統可用的總功率pC=1 W，誤碼率BER=10-4，TDD的下行比例因子 x%=70%，公平因子 δ=80%，用戶k下行數據傳輸率的最小值min歸一化為50 Kb/s，其他用戶的信噪比差額 SNRG(Signal to Noise Ratio Gap)為 5 dB。

這里用來對比的迭代注水功率分配算法是一種不考慮用戶速率請求及信噪比SNR需求的理想算法，該算法要求把功率盡量分配給信道條件較好的子載波，這樣才能充分利用有限的功率資源，提高OFDMA系統的吞吐量。

在用戶數K=20的情況下，改變平均SNR，然后分別使用改進型功率分配貪婪算法和迭代注水功率分配算法，通過Matlab軟件仿真得到OFDMA系統的吞吐量隨平均SNR變化的曲線如圖1所示。從圖1可以看出，隨著平均SNR的提高，基于改進型功率分配貪婪算法所得到的系統吞吐量逼近于迭代注水功率分配算法所得到的系統吞吐量，但是在平均SNR較低時，由于公平約束條件的限制，基于改進型功率分配貪婪算法所得到的系統吞吐量低于迭代注水功率分配算法所得到的系統吞吐量。

在平均SNR為30 dB情況下，改變用戶數 K，依次從4～20，然后分別使用改進型功率分配貪婪算法和迭代注水功率分配算法，通過Matlab軟件仿真得到OFDMA系統的吞吐量隨用戶數變化的曲線如圖2所示。從圖2可以看出，在K＜12時，基于改進型功率分配貪婪算法所得到的系統吞吐量逼近于迭代注水功率分配算法所得到的系統吞吐量，但是隨著用戶數的增加，由于公平約束條件的限制，基于改進型功率分配貪婪算法所得到的系統吞吐量低于迭代注水功率分配算法所得到的系統吞吐量。

在用戶數K=20的情況下，改變平均SNR，然后分別使用改進型功率分配貪婪算法和迭代注水功率分配算法，通過Matlab軟件仿真得到OFDMA系統公平性能的比較曲線如圖3所示。從圖3可以看出，改進型功率分配貪婪算法能夠使OFDMA系統得到100%的公平性能，比迭代注水功率分配算法的公平性能提高了大約50%。

從上述3次的仿真結果可以看出，改進型功率分配貪婪算法考慮了用戶的速率請求和誤比特率的需求，可以在OFDMA系統的吞吐量與用戶間的公平性能之間尋求到一個理想的平衡點，其公平性能的提高是以犧牲一定的系統吞吐量作為代價的。

針對OFDMA-TDD系統下行鏈路的功率分配，在公平約束條件下，提出一種改進型功率分配貪婪算法，該算法根據用戶請求進行子載波的預分配，不僅可以有效地實現每個用戶具體的比特分配和功率分配，而且可以在OFDMA系統的吞吐量與用戶間的公平性能之間尋求到一個理想的平衡點。這對于無線數據通信系統具有一定的實用價值。

[1]KNOPP R，HUMBLET P A.Information capacity and power control in single-cell multiuser communications[C].IEEE International Conference on Communications， Seattle， WA，USA，1995:331-335.

[2]WONG I C，SHEN Z K，EVANS B L，et al.A low complexity algorithm forproportionalresource allocation in OFDMA systems[C].IEEE Workshop on Signal Processing Systems， Austin， Texas， USA， 2004:1-6.

[3]SHEN Z K，ANDREWS J G，Evans B L.Optimal power allocation in multiuser OFDM systems[C].IEEE Global Telecommunications Conference， San Francisco， CA， USA，2003:337-341.

[4]RONG B， QIAN Y， LU K.Revenue and fairness guaranteed downlink adaptive power allocation in WiMAX access networks[C].Mobile and Wireless Communications Summit，Budapest，2007:1-5.

[5]PENG Y， DOUFEXI A， AMOUR S， et al.An investigation of adaptive sub-carrier allocation in OFDMA systems[C].Vehicular Technology Conference， Stockholm， Sweden，2005:1808-1811.

[6]ERMOLOVA N Y， MAKAREVITCH B.Low complexity adaptive power and subcarrier allocation for OFDMA[J].IEEE Transactions on Wireless Communications， 2007，6(2):433-437.

[7]CHEN Y F,CHEN J W.A fast subcarrier， bit， and power allocation algorithm for multiuser OFDM-based systems[J].IEEE Transactions on Vehicular Technology， 2008，57(2):873-881.

[8]MOHANRAM C，BHASHYAM S.Joint subcarrier and power allocation in channel-aware queue-aware scheduling for multiuser OFDM[J].IEEE Transactions on Wireless Communications， 2007，6(9):3208-3213.

[9]NG C Y，SUNG C W.Low complexity subcarrier and power allocation for utility maximization in uplink OFDMA systems[J].IEEE Transactions on Wireless Communications，2008，7(5):1667-1675.

[10]SEO H，LEE B G.Proportional-fair power allocation with CDF-based scheduling forfairand efficientmultiuser OFDM systems[J].IEEE Transactions on Wireless Communications， 2006，5(5):978-983.

[11]FEITEN A，MATHAR R，REYER M.Rate and power allocation for multiuser OFDM:an effective heuristic verified by branch-and-bound[J].IEEE Transactions on Wireless Communications， 2008，7(1):60-64.

[12]YAO Y，GIANNAKISG B.Rate-maximizingpower allocation in OFDM based on partial channel knowledge[J]. IEEE Transactions on Wireless Communications，2005，4(3):1073-1083.