祝楊坤,達(dá)新宇,張亞普

（空軍工程大學(xué)信息與導(dǎo)航學(xué)院 西安 710077）

1 引言

正交頻分復(fù)用（orthogonal frequency division multiplexing,OFDM）是一種能夠有效減緩寬帶無線系統(tǒng)頻率選擇性影響的先進(jìn)高速率傳輸技術(shù)，它將整個頻率選擇性衰落信道轉(zhuǎn)換成為多個并行的窄帶平坦衰落子信道，將自適應(yīng)技術(shù)用在轉(zhuǎn)換后的并行子信道中，可以根據(jù)子信道的瞬時特性動態(tài)地進(jìn)行系統(tǒng)資源優(yōu)化分配，能夠有效地提高通信系統(tǒng)的抗噪聲性能和頻譜效率。

多用戶OFDM自適應(yīng)動態(tài)資源分配主要有兩類優(yōu)化技術(shù)：功率自適應(yīng)（power adaption,MA）[1]和速率自適應(yīng)（rate adaptive，RA）[2，3]。RA技術(shù)的分配算法主要有兩種：系統(tǒng)傳輸速率最大化算法和保證用戶公平性的算法。目前有很多文獻(xiàn)對多用戶OFDM資源分配進(jìn)行研究，試圖解決RA問題，然而大多不能在用戶公平性和整個系統(tǒng)傳輸速率最大化之間取得很好的折中。參考文獻(xiàn)[3]將子載波與功率分配分為兩步一次執(zhí)行，較好地解決了用戶的公平性問題，但總的傳輸速率有所下降；參考文獻(xiàn)[4]提出一種非迭代算法放松了用戶速率公平性的約束限制，以犧牲速率公平性獲取了系統(tǒng)復(fù)雜度的降低；參考文獻(xiàn)[5]采用約束條件松弛技術(shù),將動態(tài)資源分配問題轉(zhuǎn)化為凸優(yōu)化問題求解，通過追求最大的系統(tǒng)效應(yīng)來實現(xiàn)系統(tǒng)傳輸速率的最大化；參考文獻(xiàn)[6]提出一種采用多用戶分集增益，通過合理選擇用戶的接入時刻，從而達(dá)到在保證用戶公平性的同時提高了系統(tǒng)容量的資源分配算法；參考文獻(xiàn)[7]利用對偶分解方法將多業(yè)務(wù)資源分配問題分解為若干獨立子問題，分別得到了最優(yōu)資源塊與最優(yōu)功率分配規(guī)則；參考文獻(xiàn)[8]將認(rèn)知OFDM中下行鏈路的功率分配問題，建模為一個約束優(yōu)化問題，提出一種基于免疫克隆的求解方法；參考文獻(xiàn)[9]研究了基于魚群算法的OFDMA自適應(yīng)資源分配，采用一種新的子載波分配方式，并根據(jù)改進(jìn)的自適應(yīng)魚群算法進(jìn)行功率分配，在實現(xiàn)總的傳輸速率最大化的同時較好地保證用戶公平性，但魚群算法在每次尋優(yōu)過程中都需要執(zhí)行幾種行為，因此算法復(fù)雜度較高。

本文研究采用差分進(jìn)化（differential evolution,DE）算法[10]解決多用戶OFDM自適應(yīng)資源分配中的速率自適應(yīng)問題，并將資源分配問題分為子載波分配和功率分配問題來解決，最終在保證用戶公平性的同時實現(xiàn)系統(tǒng)總的傳輸速率最大化。

2 系統(tǒng)模型

在多用戶OFDM自適應(yīng)資源分配系統(tǒng)中，考慮系統(tǒng)收發(fā)端已知信道狀態(tài)信息，假設(shè)系統(tǒng)中共有M個用戶共享N個子載波，自適應(yīng)分配算法的目標(biāo)是在功率Ptotal的約束下，在保證用戶公平性的同時，優(yōu)化子載波和功率分配方案，實現(xiàn)系統(tǒng)總傳輸速率的最大化。

根據(jù)參考文獻(xiàn)[3]，可以將子載波和功率分配優(yōu)化問題數(shù)學(xué)模型表示如下：

其中，N0是加性高斯白噪聲（AWGN）的功率譜密度，第m個用戶在第n個子載波的功率與信道增益分別為pm,n、hm,n，B為總信道帶寬，ρm,n用來判斷子載波n是否分配給用戶m，若是，則為1，否則為0，該參數(shù)限制了每個子載波只能供一個用戶使用。 是為確保用戶公平性而預(yù)先設(shè)定的一組比例公平系數(shù)值，定義公平性參數(shù)F[11]為：

可以看出，F(xiàn)≤1，且F越接近1，系統(tǒng)公平性越好。

3 自適應(yīng)資源分配算法

理論上，期望對多用戶子載波和功率進(jìn)行聯(lián)合分配獲得最優(yōu)解，但由于多種約束條件的限制導(dǎo)致聯(lián)合分配方案復(fù)雜度極高，因此考慮將子載波與功率分開進(jìn)行優(yōu)化分配，先進(jìn)行子載波分配，然后根據(jù)分配好的子載波進(jìn)行功率分配以獲得最優(yōu)結(jié)果。

3.1 子載波分配算法

本節(jié)進(jìn)行的子載波分配基于參考文獻(xiàn)[2]的次優(yōu)子載波分配算法，C為矩陣M×N，矩陣中元素為ρm,n，表示子載波的分配情況，算法流程如下。

（1）初始化

用戶速率Rm=0,各用戶等功率分配，功率pm=Ptotal/M，C為全0矩陣，為M×N矩陣，用戶的子載波分配集合Ω=，子載波集合A={1,2,…,N}，K為1×M的全0矩陣，表示各用戶分配的子載波數(shù)目。

（2）每個用戶分配信道增益最好的子載波

For m=1 to M

Cm,n=1，=0，Ωm=Ωm∪{n}，A=A-{n}，K(m)=K(m)+1，更新Rm。

（3）根據(jù)比例公平系數(shù)分配剩余子載波

While A=

尋找m滿足min(Rm/γm)；

Cm,n=1，||=0，Ωm=Ωm∪{n}，A=A-{n}，K(m)=K(m)+1更新Rm。

（4）記錄分配結(jié)果

子載波分配結(jié)果為C，用戶的子載波分配集合為Ω={Ω1,Ω2,…,ΩM}，用戶分配的子載波數(shù)目為K。

以上次優(yōu)子載波分配算法的分配原理是讓每個用戶盡可能地使用具有最好信道增益的子載波，每次迭代時，由具有最低比例速率的用戶優(yōu)先選擇子載波，這種分配方式在子載波分配過程中盡可能地保證了用戶間的公平性。在功率分配過程中為降低系統(tǒng)復(fù)雜度，初始化時先進(jìn)行等功率分配，獲得粗略的分配結(jié)果，然后在下一步的功率分配中采用相應(yīng)算法，在維持比例公平性的前提下盡可能地獲得最大的傳輸速率。

3.2 基于差分進(jìn)化算法的功率自適應(yīng)分配

近年來，優(yōu)化算法用于求解各種工程的最優(yōu)化問題，受到人們的廣泛重視，并在諸多工程領(lǐng)域得到迅速推廣和應(yīng)用。智能優(yōu)化算法作為一種具有很強(qiáng)自適應(yīng)性和自組織性的啟發(fā)式搜索算法，不需要提供額外的初始點及優(yōu)化目標(biāo)函數(shù)的梯度信息，降低了初始條件的硬性要求，為研究無線通信中資源分配問題提供了新的契機(jī)。差分進(jìn)化算法是一種基于群體差異的高效并行搜索的新興進(jìn)化算法，它采用概率轉(zhuǎn)移規(guī)則，不需要確定性的規(guī)則。因此，相比于遺傳算法、粒子群算法，其具有良好的求取全局極值能力,并具有結(jié)構(gòu)簡單、易實現(xiàn)、可調(diào)參數(shù)少、頑健性強(qiáng)等優(yōu)點。本節(jié)將基于差分進(jìn)化算法進(jìn)行功率自適應(yīng)分配，目的是使整個系統(tǒng)在滿足用戶公平性的同時達(dá)到傳輸速率最大化。

如式（1）所示，功率分配優(yōu)化問題為非線性約束優(yōu)化問題，在采用DE算法尋優(yōu)時，必須考慮到優(yōu)化問題的非線性約束條件，因此，需要對原始的DE算法進(jìn)行相應(yīng)的改進(jìn)，以滿足式（1）中的條件。其中約束條件（c）、（d）已通過子載波分配算法滿足，條件（e）可以通過式（1）、式（2）聯(lián)合滿足，而條件（a）、（b）在尋優(yōu)算法中需要單獨設(shè)置改進(jìn)措施來滿足。

算法基本流程如下。

（1）個體編碼

根據(jù)先前每個用戶分配的子載波情況，對每個用戶所分配的子載波進(jìn)行功率初始化，每個用戶為一個長度為K（m）的一維數(shù)組pm,i，K（m）為該用戶分配的子載波數(shù)，每個用戶的功率分配情況pm=(pm,1,pm,2,…,pm,K(m))，初始元素可以用如下隨機(jī)方法產(chǎn)生：

圖1 編碼方案

對于產(chǎn)生的個體，需要滿足約束條件（a）、（b），由式（3）可知，約束條件（b）自然滿足。因此，為滿足條件（a），設(shè)置約束條件檢測改進(jìn)步驟，即在個體生成后，將每個用戶分配的功率記入1×M的矩陣中，分配后總功率為PT，若PT>Ptotal，即分配結(jié)果不滿足約束條件（a），則尋找m滿足max(P(m))，令P(m)=P(m)-(PT-Ptotal)，再將P(m)等功率分配到第m個用戶的相應(yīng)子載波上。

（2）產(chǎn)生群體

重復(fù)Np次步驟（1），即可得到隨機(jī)生成的Np個個體，獲得初始群體。

（3）變異

DE算法和其他進(jìn)化算法的主要區(qū)別是變異操作，也是產(chǎn)生新個體的主要步驟，該操作的基本原理是將一個差分向量加到一個基向量上去，變異操作后得到中間個體記為Vi,G+1，即：

其中，r1,r2,r3∈{1,2,…,Np}且r1≠r2≠r3≠i，F(xiàn)∈[0,1]為一常數(shù)，稱為變異因子，它控制著差分向量的幅度，F(xiàn)值越大算法的收斂速度越慢。

由于變異操作會導(dǎo)致個體中分配功率的變化，因此每個個體的變異操作結(jié)束后都需要執(zhí)行一次約束條件檢測改進(jìn)步驟，以滿足功率分配的約束條件。

（4）交叉

其中，i=1,…,Np，m=1,…,M，rnbr(m)是[1,M]范圍的一個隨機(jī)整數(shù)，用來保證候選個體至少從中取到某一用戶的功率分配矩陣，rand∈[0,1]是一個均勻分布的隨機(jī)數(shù)，交叉因子CR∈[0,1]決定了中間個體分量值代替目標(biāo)個體分量值概率。

交叉操作通過雜交個體間的某功率分配矩陣，來增加種群的多樣性，這種操作會造成個體總功率的改變，因此同樣需要執(zhí)行約束條件檢測改進(jìn)步驟，以滿足功率分配的約束條件。

（5）選擇

其中：

根據(jù)式（6）決定是否在下一代中用候選個體替換當(dāng)前目標(biāo)個體。

（6）記錄最優(yōu)值

在算法執(zhí)行中引入公告板，將每一代選擇操作后得到的最優(yōu)狀態(tài)及最優(yōu)結(jié)果記錄在公告板中，當(dāng)G次迭代結(jié)束后，根據(jù)公告板中記錄內(nèi)容，選擇最優(yōu)狀態(tài)與最優(yōu)結(jié)果作為尋優(yōu)的最終結(jié)果。

4 仿真結(jié)果

4.1 仿真參數(shù)設(shè)置

在仿真中，采用6徑衰落信道進(jìn)行信道建模。總的可用帶寬B=1 MHz，分為N=64個子載波。總的發(fā)射功率Ptotal=1 W，AWGN的功率譜密度為-80 dB·W·Hz-1。仿真中假設(shè)用戶的傳輸速率要求相同，即R1∶R2∶…∶Rm=1∶1∶…∶1。本文采用DE算法解決自適應(yīng)資源問題，設(shè)置DE算法參數(shù)為：變異因子F=0.5，交叉因子CR=0.5，種群個數(shù)Np=50，最大迭代次數(shù)Gmax=100，蒙特卡洛仿真次數(shù)為100次。

4.2 性能分析

圖2對比了用戶數(shù)K在2～12變化時本文算法與Shen算法、Wong算法以及參考文獻(xiàn)[8]基于AFSA的資源分配算法的系統(tǒng)容量。由圖中可明顯看出，隨著用戶數(shù)目的增加，本文提出的分配算法可獲得比Shen算法、Wong算法更高的系統(tǒng)容量，容量提升約0.1 bit/s/Hz，但略低于采用AFSA進(jìn)行資源分配的系統(tǒng)容量，約為0.04 bit/s/Hz。

圖2 系統(tǒng)容量隨用戶數(shù)變化曲線

圖3 為用戶數(shù)M=8，各用戶的速率比例系數(shù)為1∶1∶1∶1∶1∶1∶1∶1時，本文算法與Shen算法、Wong算法及基于AFSA的資源分配算法的各用戶系統(tǒng)容量比較。從圖中可清晰地看出，Wong算法的用戶公平性沒有得到應(yīng)有的保證，且用戶系統(tǒng)容量較低；Shen算法雖然基本上保證了用戶速率的公平性，但各用戶系統(tǒng)容量較低；本文算法和基于AFSA資源分配算法都可以較好地保證用戶速率的公平性，各用戶系統(tǒng)容量得到一定提升，并且較為相近。

圖3 用戶數(shù)為8時各用戶的系統(tǒng)容量

圖4顯示了4種算法在各用戶的速率比例系數(shù)為1∶1∶1∶1∶1∶1∶1∶1時的比例公平性。由圖中可以看出，Shen算法的比例公平性最好，參數(shù)值接近于1；Wong算法雖然提升了系統(tǒng)容量，但其比例公平性最差；當(dāng)用戶數(shù)目較大時，AFSA算法的比例公平性與Shen算法有明顯差距；由前文分析可知，本文算法雖然系統(tǒng)容量略低于AFSA算法，但比例公平性接近于Shen算法，與Shen算法相比，比例公平性參數(shù)值僅差0.003左右。

圖4 各算法的比例公平性

綜合以上可知，Shen算法通過采用迭代搜索方法較好地實現(xiàn)了用戶公平性，但系統(tǒng)復(fù)雜度較高且容量較低；Wong算法采用非迭代算法放松了用戶公平性的約束限制，以犧牲公平性獲取復(fù)雜度的降低和較高的系統(tǒng)容量；AFSA算法在子載波分配過程中松弛了約束條件，降低了用戶間的公平性，在功率分配過程中將用戶公平性與系統(tǒng)容量綜合考慮作為優(yōu)化目標(biāo)函數(shù)來彌補(bǔ)降低的公平性，并最大化系統(tǒng)容量，從圖2～圖4的對比結(jié)果可以看出，AFSA算法雖獲得高于其余算法的系統(tǒng)容量，但松弛條件降低了用戶公平性，并且魚群算法尋優(yōu)過程的多種行為帶來了較高的系統(tǒng)復(fù)雜復(fù)雜度；本文算法由于全面考慮分配過程中的約束條件，并且采用復(fù)雜度較低的DE算法，在獲得較優(yōu)公平性的同時，獲得較高的系統(tǒng)容量，體現(xiàn)了本文算法的優(yōu)越性。

4.3 算法復(fù)雜度

由上節(jié)可知，本文算法與參考文獻(xiàn)[8]的算法均可以在保證用戶速率公平性的前提下，獲得系統(tǒng)容量較大的提升，本部分將對采用的DE算法與采用AFSA算法的計算時間復(fù)雜度進(jìn)行分析比較。

兩種算法在資源優(yōu)化分配中都采用了將子載波與功率分步進(jìn)行的分配策略，因此在分析復(fù)雜度時，也應(yīng)當(dāng)將子載波分配與功率分配分開計算復(fù)雜度。首先，對兩種算法的子載波分配進(jìn)行復(fù)雜度分析，已知用戶數(shù)為M，種群個體數(shù)為N，由分配方案可知，兩種算法的子載波分配方案復(fù)雜度均為O(MNlbN)；其次，對兩種算法的功率分配方案進(jìn)行分析，根據(jù)對兩種群智能算法的描述可知，假設(shè)最大迭代次數(shù)為G，每個個體迭代一次需要的運行時間為TT，則可以得出群智能優(yōu)化算法進(jìn)行優(yōu)化結(jié)束后所需要的總運行時間為N×G×TT。

對于AFSA算法，一個人工魚個體的更新需要并行執(zhí)行4種行為，分別為覓食行為、追尾行為、聚群行為和隨機(jī)行為，覓食行為、追尾行為、聚群行為所需要的運算為：4次乘法運算，4次加法運算；隨機(jī)行為所需要的運算為：1次乘法運算，1次加法運算。假設(shè)乘法與加法運算時間分別為Tm與Ta，由于覓食行為執(zhí)行時還存在try_number次的嘗試迭代，因此AFSA算法完成優(yōu)化所需的平均時間為：

對于本文采用的DE算法，一個個體的更新執(zhí)行變異、交叉操作以及為滿足功率約束條件所設(shè)置的改進(jìn)步驟，變異操作所需要的運算為1次乘法運算和4次加法運算；交叉操作所需要的運算為2次加法運算，因此本文算法完成優(yōu)化所需的平均時間為：

對兩種算法設(shè)置的參數(shù)如下：最大迭代次數(shù)G=100，種群N=50，AFSA算法中嘗試次數(shù)try_number=20，對兩種算法的性能進(jìn)行簡要對比記錄，見表1。

表1展示了兩種資源分配算法的各種性能對比情況，可以看出，兩種算法的子載波分配算法復(fù)雜度相同，當(dāng)用戶數(shù)為8時，在保證用戶比例公平性的同時，本文算法的系統(tǒng)容量比基于AFSA的資源分配算法的系統(tǒng)容量低約0.01 bit/s/Hz，但其功率分配運算的復(fù)雜度僅為AFSA分配算法的4%，證明了本算法的高效性。

表1 兩種算法性能對比概況

5 結(jié)束語

本文提出一種采用改進(jìn)的差分進(jìn)化算法解決多用戶比例公平性約束條件下的速率自適應(yīng)資源分配問題，將資源分配問題分為兩步執(zhí)行，先進(jìn)行有效的子載波分配，然后根據(jù)已分配子載波情況采用改進(jìn)的差分進(jìn)化算法，兼顧系統(tǒng)容量最大化與用戶公平性進(jìn)行功率分配。仿真結(jié)果表明，本文算法很好地解決了速率自適應(yīng)資源分配問題，在實現(xiàn)低復(fù)雜度下系統(tǒng)容量最大化的同時保證了用戶間的公平性，是一種有效的兼顧系統(tǒng)容量和用戶公平性的自適應(yīng)資源分配算法。

1 Wong I C,Evans B L.Optimal downlink OFDMA resource allocation with linear complexity to maximize ergodic rates.IEEE Trans on Wireless Communications,2008,7(3):962～971

2 Mohanram C,Bhashyam S.A sub-optimal joint subcarrier and power allocation algorithm for multiuser OFDM.IEEE Communications Letters,2005,9(8):685～687

3 Shen Z K,Andrews J G,Evans B L.Adaptive resource allocation in multiuser OFDM systems with proportional rate constraints.IEEE Transactions on Wireless Communications,2005,4(6):2726～2737

4 Wong I C,Shen Z K,Evans B L,et al.A low complexity algorithm for proportional resource allocation in OFDMA systems.Proceedings of IEEE Signal Processing Systems,USA,2004

5 Huang J W,Subramanian V G,Agrawal R,et al.Downlink scheduling and resource allocation for OFDM systems.IEEE Transactions on Wireless Communications,2009,8(1):288～296

6 薛曉潔,趙林靖,劉鵬等.一種新型的多用戶OFDM系統(tǒng)資源分配策.電子學(xué)報,2007,35(6A):64～68 Xue X J,Zhao L J,Liu P,et al.A novel resource allocation algorithm in multiuser OFDM system.Chinese Journal of Electronics,2007,35(6A):64～68

7 左勇,劉學(xué)勇,劉海洋等.基于對偶分解的OFDMA系統(tǒng)資源分配算法.電子與信息學(xué)報,2012,34(12):2843～2849 Zuo Y,Liu X Y,Liu H Y,et al.A dual-decompostition-based resource allocation algorithm for OFDMA systems.Journal of Electronics & Information Technology,2012,34(12):2843～2849

8 柴爭義,陳亮,朱思峰等.認(rèn)知無線網(wǎng)絡(luò)中基于免疫克隆優(yōu)化的功率分配.電子科技大學(xué)學(xué)報,2013,42(1):36～40 Chai Z Y,Chen L,Zhu S F,et al.Power allocation of cognitive wireless network based on immune clonal optimization.Journal of University of Electronic Science and Technology of China,2013,42(1):36～40

9 汪照,李有明,陳斌等.基于魚群算法的OFDMA自適應(yīng)資源分配.物理學(xué)報,2013(12)Wang Z,Li Y M,Chen B,et al.OFDMA adaptiue resource allocation based on fish swarm algorithm.Acta Physica Sinica,2013(12)

10 Das S,Suganthan P N.Differential evolution:a survey of the state-of-the-art.IEEE Transactions on Evolutionary Computation,2011,15(1):4～31.

11 Schwarz S,Mehlfuhrer C,Rupp M,et al.Throughput maximizing multiuser scheduling with adjustable fairness.Proceedings of IEEE InternationalConference on Communications,Kyoto,Japan,2011