李為，熊春林，王德剛，張曉瀛，魏急波

（國防科學技術大學 電子科學與工程學院，湖南 長沙 410073）

1 引言

OFDMA（orthogonal frequency division multiple access）技術具有較高的頻譜利用效率和對抗多徑衰落的優(yōu)良特性，被普遍認為是當前和未來移動通信網的關鍵傳輸技術之一。協同中繼技術能顯著增加通信網絡的覆蓋范圍和鏈路的可靠性，具有廣泛應用前景?；谥欣^協同的OFDMA系統可充分結合2種技術的優(yōu)點，已經引起了國內外學者們和業(yè)界的研究興趣，并被IEEE 802.16j和3GPP-LTE 等多個標準組織采納。

資源分配能顯著提高協同OFDMA系統的頻譜效率和多用戶分集增益。協同OFDMA系統的資源分配主要包括中繼選擇、子載波分配和功率分配。目前，已有的工作大部分目標為保證一定公平性的約束條件下最大化系統的吞吐量[1,2]。此類方法傾向于將更多資源分配給信道條件較好的用戶，而位于較差信道條件下的用戶往往得不到足夠的資源。文獻[3, 4]針對公平性問題，采用比例速率約束和最大最小公平性準則來改善公平性，但是又引入了新的問題，信道環(huán)境很差的用戶會占用大量的系統資源，導致整個系統的吞吐量降低。

為了實現公平性和吞吐量的更優(yōu)折中，人們引入效用（utility）理論來衡量網絡中用戶的滿意程度[5～7]。效用的高低取決于用戶的應用層需求。文獻[6]研究了協同OFDMA系統中基于效用最大化的資源分配問題，但是只考慮基站和協同節(jié)點總功率約束（TPC,total power constraint）的條件。實際場景往往需要考慮基站和中繼單獨功率約束(PPC, per-relay power constraint)的情況，該約束條件下的資源分配問題更為復雜。

本文以所有用戶的總效用最大為優(yōu)化目標，研究PPC 約束條件下的協同OFDMA跨層資源分配問題。和以往的研究不同的是，本文考慮多服務的協同OFDMA系統，且每個用戶根據應用層的需求具有自己獨立的效用函數，這更符合實際情況。這樣，資源分配成為一個離散和連續(xù)變量混合的多維優(yōu)化問題，這是一個NP 問題。文獻[1]研究了TPC條件下加權速率最大化資源分配問題，采用的方法是將離散變量松弛為連續(xù)變量，將問題轉化為凸優(yōu)化問題用對偶法來求解。但是，多服務情況下，用戶的效用函數存在多樣性，甚至可能是不連續(xù)函數，很難將資源分配問題轉化為凸優(yōu)化問題來求解。

在解析類方法遇到困難時，啟發(fā)式智能算法提供了一條有效解決問題的思路，如粒子群優(yōu)化（PSO,particle swarm optimization）算法。PSO算法是一種基于群體智能的統計最優(yōu)化算法，由Eberhart和Kennedy受到鳥群捕食的啟發(fā)在1995年提出[8,9]，能夠高效求解高度非線性的混合優(yōu)化問題，因此在工程中得到廣泛應用[10～12]。PSO算法最初用來求解連續(xù)變量的優(yōu)化問題，現在已有文獻針對離散粒子群算法進行了研究，并將其應用到了離散優(yōu)化問題中[13～15]。然而，這些方法僅僅將連續(xù)空間上的運算法則簡單搬移到離散空間中，沒有考慮離散空間的特點。為了更好地提高離散空間的搜索效率，需要根據離散空間的特點建立起特殊的運算法則。

為解決多服務協同OFDMA系統的資源優(yōu)化問題，本文提出了一種多值離散粒子群優(yōu)化（MDPSO,multi-values discrete particle swarm optimization）算法。所提算法根據多維離散空間的特點，構建了新的基于概率特性的運算法則，由此建立了粒子速度和位置的更新策略。所提MDPSO算法可以廣泛用于求解各類高維組合優(yōu)化問題。仿真結果顯示本方法很好的解決了資源優(yōu)化問題，效用和公平性2個指標相對于目前已有算法均取得了較大的性能提升。

2 系統模型和問題闡述

2.1 協同OFDMA系統模型

如圖1所示，所考慮的協同OFDMA系統具有1個基站(BS, base station)，K個中繼站(RS, relay station)，和M個移動站（MS, mobile station）。系統可供使用的子載波數目為N，總帶寬為W，每個子載波的帶寬為W/N。BS和 MS m、BS和RS k、RS k 和 MS在子載波n上的信道系數分別表示為每個子載波上的噪聲為0均值循環(huán)對稱復高斯變量，方差為N0W/N。

圖1 協同OFDMA系統模型

考慮2種類型的中繼策略：放大轉發(fā)（AF,amplify-and-forward）和譯碼轉發(fā)（DF, decode-andforward）。設定每個子載波在同一時刻最多分配給一個用戶和一個中繼（沒有子載波復用）。中繼的處理過程如下：首先，基站（BS）在子載波n上以功率發(fā)送信號給中繼節(jié)點（RS）和移動站（MS），然后，RS k接收到信號后在相同的子載波上以功率譯碼轉發(fā)或者放大轉發(fā)給MS m。由文獻[16]得到中繼用戶對(RS k, MS m)在子載波n上的信道容量為

其中，

為了表示方便，將中繼選擇方法和子載波分配方案用2進制變量表示。表示子載波n和中繼K分配給用戶m，否則，

這樣用戶m 的容量可以表示為

圖2 BE服務效用函數(C=90 kbit/s)

2.2 效用函數

用戶滿意的程度可以用效用來表示，效用是用戶速率的函數。采用效用函數進行跨層優(yōu)化設計可以很好地獲得效用和公平性的平衡。針對不同的服務和不同的用戶，會有不同的效用函數[17]。本文考慮了2種服務類型：最大努力服務（BE）和速率約束服務（RC）。

最大努力服務（BE）的效用函數可以表示為[18]

速率約束服務（RC）的效用函數可以表示為

其中，minR表示用戶最低的速率需求。

針對不同的MS 參數ma或minR可能具有不同的取值。根據用戶的不同需求還可以設置其他效用函數。

2.3 問題闡述

本文資源優(yōu)化的目標是最大化用戶的效用總和。優(yōu)化問題表示為如下。

Problem: P1

其中，kP表示基站(k=0)或者中繼站(k=1, 2,…, K)的最大發(fā)送功率；式(7)為基站和中繼站的功率約束；式(8)和式(9)保證了每個子載波最多分配給一個用戶和中繼站；式(11)保證RC 用戶的需求，RCS表示RC用戶的集合。明顯問題P1為帶有非線性約束條件的連續(xù)和離散變量混合優(yōu)化問題，為NP-hard問題。在下一節(jié)中將采用MDPSO算法來求解。

3 資源分配算法

前一節(jié)定義的資源優(yōu)化問題，為離散和連續(xù)混合變量優(yōu)化問題。采取分而治之的辦法，將問題P1分為2個子問題：子載波中繼分配和功率分配。首先采用均勻功率分配方案，在此前提下進行子載波和中繼分配。最后再進行功率分配獲得性能進一步的提升。本節(jié)首先介紹PSO算法，然后采用MDPSO算法來進行子載波和中繼分配，最后用迭代注水方法進行功率分配。

3.1 粒子群優(yōu)化（PSO）

粒子群優(yōu)化算法是一種基于群體智能隨機搜索的全局優(yōu)化算法。搜索過程從問題解的一個初始集合開始，系統由一群粒子(particle)組成。在搜索過程中采取最優(yōu)解信息共享機制，即粒子飛行的策略只是追隨自己當前的最好位置和整個群體當前的最好位置，整個群體就實現了對解空間中最好解的搜索。所以粒子群優(yōu)化算法與其他的群體智能算法不同，在粒子群優(yōu)化算法中，每個粒子是有記憶的，各自分別保留自己在搜索過程中找到的最好的問題解信息，而群體則保留當前的群體最好解信息。

粒子群算法中的每一個粒子包含著如下信息：

1) 粒子位置Xi，表示需要優(yōu)化的變量；

2) 粒子速度Vi，表示在下一次迭代中粒子位置的變化；

3) 個體最優(yōu)值pbesti，表示單個粒子所經歷的最優(yōu)值；

4) 群體最優(yōu)值gbesti，表示所有粒子所經歷的最優(yōu)值。

在每次迭代中，每個粒子在空間中各自搜索，它的移動策略將根據自己的經驗以及群體最優(yōu)值共同決定。其速度和位置更新公式為[19]

其中，n為粒子個數，i表示粒子編號ω為慣性質量表示粒子保持之前速度的程度，1r和2r為2個均勻分布在[0,1]區(qū)間內的隨機變量，1c和2c為學習因子分別表示粒子靠近自身最優(yōu)值和群體最優(yōu)值的權重。從社會心理學的角度來看，式(12)中的第2項為認知項表示個體采用自身成功經驗的部分，而第3項為社會項表示其借鑒其他人成功經驗的部分。

假設優(yōu)化問題為最大化問題，則每個粒子在每次迭代中根據下面公式來更新其個體最優(yōu)值

其中，()f·為需要優(yōu)化的函數，這里用來評估粒子的適應度。

而群體最優(yōu)值為

3.2 基于MDPSO的資源優(yōu)化算法

傳統的粒子群優(yōu)化算法僅用來求解連續(xù)問題。而本文中的資源優(yōu)化問題是個多維離散空間的優(yōu)化問題。針對離散問題，粒子位置更新、速度更新等操作需要重新定義。本節(jié)將基于概率操作建立MDPSO算法，并用于求解資源優(yōu)化問題。

首先，將子載波中繼分配方案編碼為離散空間的向量，也對應著粒子的位置。第i個粒子的位置可以表示為

進一步定義離散空間向量的運算如下。

定義1 粒子位置的減法(得到速度)。

給定粒子的2個位置

它們的距離定義為

其中，

Vij中的(asn,bsn)表示將其第n項變?yōu)?asn,bsn)，而-1表示沒有變化。

定義2 粒子位置和速度的加法(得到新的位置)。

給定位置Xi={(ai1,bi1),(ai2,bi2),…,(aiN,biN)}和速度Vs={(as1,bs1),(as2,bs2),…,(asN,bsN)}，定義它們的加法操作為

其中，

加法操作是減法操作的逆運算，然而此處是不需要滿足交換律的。在MDPSO算法中，此操作用來更新粒子的位置。

定義3 多個速度的加權相加(得到新的速度)。

給定3個粒子速度變量：Vi={(ai1,bi1),(ai2,bi2),…,(aiN,biN)},Vj={(aj1,bj1),(aj2,bj2),…, (ajN,bjN)}和Vs={(as1,bs1),(as2,bs2),…,(asN,bsN)}以及3個比例因子c1,c2,c3≥0，它們的加權相加定義為V0=c1Vi+c2Vj+c3Vs={(a01,b01),(a02,b02),…,(a0N,b0N)}。

V0按照如下方式得到。

1)d1=round(N×c1/(c1+c2+c3)),d2=round(N ×c2/(c1+c2+c3))round (·) 表示取最近的整數。

2) 隨機地從集合D= {1, 2, …, N}中選取d1個數，構成D1；然后從集合D-D1中選取d2個數構成集合D2，剩余的數構成D3=D-D1-D2。

3) 對V0中的每一個元素賦值，

此操作用來完成MDPSO算法中的速度更新。它決定了粒子搜索的方向。其物理意義是在3個速度中求得加權合速度。由于離散空間內，同一直線上任何兩不同點的距離相等，連續(xù)域的加權求和在離散空間中沒有意義，這里采用了隨機策略，使其反映了多維離散空間的特點。

定義4 粒子位置的變異操作(得到新的粒子位置)。

如果是適應度函數具有局部最優(yōu)值，則粒子在迭代多次后很可能陷入局部最優(yōu)。為了避免這種現象發(fā)生，引入了變異操作。

給定粒子的位置：Xi={(ai1,bi1),(ai2,bi2),…,(aiN,biN)}和變異因子λ∈[0,1]。

設變異后的位置為Mutate(Xi,λ)={(at1,bt1),(at2,bt2),…,(atN,btN)}，其取值由以下操作得到。

1) 在Mutate(Xi,λ)中隨機選取λN個元素(atn,btn)。

2) 對步驟1)中所選的λN個元素進行賦值

其中，rand表示在[0,1]中選取的均勻分布的偽隨機標量。

3) Mutation(Xi,λ)中其余的元素和Xi中對應元素相同。

變異操作在位置更新中引入了隨機因素，從社會心理學的角度上可以理解為個體的情緒。由此粒子的運動由以下3個因素影響：個體經驗（pbest）、社會效應（gbest）、個體情緒（mutation）。

基于以上定義最終得到MDPSO算法如下所示。其中，最大迭代次數取值為50～100。變異因子λ取值為2/N。學習因子c1、c2和慣性質量ω均取為1。粒子群大小可以根據具體問題來確定，這里取值為50。

MDPSO算法

3.3 迭代注水法進行功率分配

上一節(jié)采用MDPSO算法完成了子載波中繼分配問題，采用的是均勻功率分配方案。當功率資源足夠豐富時此方法已經接近最優(yōu)性能。當功率不充足時，可以采用功率分配技術來進一步提高性能。此時P1轉化連續(xù)變量的優(yōu)化問題。假定第一階段基站到中繼站之間的信道很好，這是符合實際場景的，因為可以基站和中繼節(jié)點可以架設較高位置的天線，達到視距傳輸，同時在基站和中繼站采用較高增益的天線來改進SNR。

首先，由式(6)得到拉格朗日函數為

其中，uk為拉格朗日因子。對Lag求的微分得到：

應用Karush-Kuhn-Tucker (KKT)條件[20]，由式(18)和式(19)得到最優(yōu)功率分配為

迭代注水算法：迭代注水功率分配

1) 對每個RS 和BS將功率均勻分配在每個子載波上

2) 賦值迭代次數Max_iterations

3) t=1

4) While t≤Max_iterations do

6) 更新mR

7) End while

4 仿真結果和分析

仿真參數的設置參考了IEEE 802.16j OFDMA下行鏈路系統?？紤]低速移動下的OFDMA小區(qū)網絡，小區(qū)半徑為1 km。中繼站（RS）布置在距離基站（BS）2/3 km的位置。移動站（MS）的位置隨機均勻分布在整個小區(qū)內。詳細參數如表1所示。設定有14個BE用戶，其效用函數分別為

2個RC用戶其速率約束為Rmin=1× 106bit/s 。為了對比，考察了5種不同算法組合的性能曲線，分別是：1）DPSO和注水功率分配聯合算法（迭代次數t為80）；2）文獻[4]中的最大加權和速率迭代注水算法；3）隨機子載波分配和注水功率分配；4）DPSO和均勻功率分配；5）DPSO 和注水功率分配聯合算法（迭代次數t為20 000）。

表1 仿真參數

圖3顯示了不同RS數目時，DPSO算法的迭代收斂性?？梢钥吹?，總效用隨著迭代次數增加而增加，但達到較高迭代次數時，逐漸飽和。說明粒子在最初迭代時迅速移動尋找最優(yōu)值，而在多次迭代之后逐漸收斂到接近最優(yōu)值。圖中還顯示隨著RS數目的增加，效用也增加；但RS數目達到5時，性能也已經飽和，此時再繼續(xù)增加RS數目對性能提升不大。此現象說明，當小區(qū)中RS數目達到一定程度后小區(qū)容量也將達到飽和。

圖3 DPSO算法的迭代收斂性

圖4對比了在不同RS數目下，幾種算法的效用函數。為了比較，同時仿真了迭代次數為80和20 000次的DPSO算法性能?？梢钥闯觯酓PSO算法性能最優(yōu)，在迭代次數為80次時已經取得明顯優(yōu)于文獻[4]中算法的性能。從圖中還可觀察到即使是采用等功率分配的DPSO算法，其性能也可以達到較好值。這是因為子載波分配和中繼分配保證了每個信道盡可能獲得較高的SNR，而低SNR的信道被丟棄。在高SNR的情況下，等功率分配是近似最優(yōu)分配方案。所以可以得知，在資源分配中，子載波分配和中繼選擇占據了更為重要的地位。

圖4 不同RS數目下各種算法效用函數對比

圖5對比了在不同RS數目下幾種算法的吞吐量?？梢钥吹剿酓PSO算法的性能最優(yōu)，在迭代次數為20 000次時，相比文獻[4]中的算法性能提升了接近一倍；在迭代次數為80次時，有約50%的性能提升。只利用DPSO進行子載波和中繼分配，而采用等功率分配時，性能相比文獻[4]中的算法也有約20%的提升。由此看來，所提DPSO智能算法在離散和連續(xù)變量優(yōu)化問題上性能比傳統算法有明顯優(yōu)勢。

圖5 不同RS數目下各種算法吞吐量對比

圖6 各種算法公平性指數對比

表2 各算法耗費時間對比（CPU AMD Athlon 64×2雙核處理器3 800+ 2.0 GHz, 2 GB RAM）

表2進一步對各種算法的復雜度進行了比較，顯示了各種算法在計算機上的運行時間。其中，RS數目為6?？梢钥吹剑崴惴ㄟ\算時間約為文獻[4]算法的3倍。注意到此結果由CPU上通過串行方式運行得到。實際中可以采用并行方式在FPGA（field programmable gate array）硬件上實現，而所提粒子群算法中各個粒子獨自分別尋優(yōu)，具有天然并行特性。理論上通過并行設計可將運行時間減少到約1/N（N=50為粒子群中粒子數量）。 所以本算法將來在工程應用中運算時間上也具備一定優(yōu)勢。

5 結束語

本文研究了協同OFDMA系統的跨層資源分配問題。考慮了多用戶多服務的場景，即不同用戶具有不同的效用函數。將此問題建模為離散連續(xù)變量的聯合優(yōu)化問題。根據多維離散空間的特點構建了新的MDPSO算法。此算法適合求解高維度離散空間優(yōu)化問題，可以被廣泛應用于解決各類大規(guī)模組合優(yōu)化問題。利用所提MDPSO算法來進行子載波分配和中繼選擇，并用迭代注水法進行功率分配。仿真結果顯示所提算法在效用函數和公平性2個指標上均明顯優(yōu)于已有算法。

[1] WANG T, VANDENDORPE L. WSR maximized resource allocation in multiple DF relays aided OFDMA downlink transmission[J]. IEEE Trans Signal Process, 2011, 59(8):3964-3976.

[2] LI H X. Dynamic resource allocation in OFDMA-Based DF cooperative relay networks[J]. Wireless Personal Communications, 2012,62(3):655-670.

[3] TASSIULAS L, SARKAR S. Maxmin fair scheduling in wireless networks[A]. IEEE infocom'02[C]. New York, 2002.763-772.

[4] PAN Y W, NIX A, BEACH M. Distributed resource allocation for OFDMA-based relay networks[J]. IEEE Trans Veh Technol, 2011,60(3): 919-931.

[5] KATOOZIAN M, NAVAIE K, YANIKOMEROGLU H. Utility-based adaptive radio resource allocation in OFDM wireless networks with traffic prioritization[J]. IEEE Trans Wireless Commun, 2009, 8:66-71.

[6] LIU C, ZHANG S, QIN X. Utility-based resource allocation in OFDMA relay networks with service differentiation[A]. IEEE WCNC[C].Cancun, Quintana Roo, 2011.72-77.

[7] FATHI M, TAHERI H. Utility-based resource allocation in orthogonal frequency division multiple access networks[J]. Iet Communications,2010, 4(12): 1463-1470.

[8] EBERHART R C, KENNEDY J. A new optimizer using particle swarm theory[A]. Proceedings of the Sixth International Symposium on Micromachine Human Science[C]. Nagoya, Japan, 1995.39-43.

[9] KENNEDY J, EBERHART R C. Particle swarm optimization[A].Proceedings of IEEE International Conference on Neural Networks[C].Piscataway, NL, 1995.39-43.

[10] MAHDAD B, BOUKTIR T, SRAIRI K. Strategy based PSO for dynamic control of UPFC to enhance power system security[J]. Journal of Electrical Engineering & Technology, 2009, 4(3):315-322.

[11] RAGLEND I J, RAGHUVEER C, AVINASH G R, etal. Solution to profit based unit commitment problem using particle swarm optimization[J]. Applied Soft Computing, 2010, 10(4): 1247-1256.

[12] FU X, LI A Q, WANG L P, etal. Short-term scheduling of cascade reservoirs using an immune algorithm-based particle swarm optimization[J]. Computers & Mathematics with Applications, 2011, 62(6):2463-2471.

[13] SHARMA N, TARCAR A K, ANTONY V, etal. On the use of particle swarm optimization for adaptive resource allocation in orthogonal frequency division multiple access systems with proportional rate constraints[J]. Information Sciences, 2012, 182(1):115-124.

[14] YUSOFF M, ARIFFIN J, MOHAMED A. An improved discrete particle swarm optimization in evacuation planning[A]. IEEE International Conference of Soft Computing and Pattern Recognition[C]. Malacca,2009. 49-53.

[15] PAREEK U, LEE D C. Resource allocation in bidirectional cooperative cognitive radio networks using swarm intelligence[A]. IEEE Symp. Swarm Intelligence[C]. Paris, 2011.1-7.

[16] LANEMAN J, TSE D, WORNELL G. Cooperative diversity in wireless networks: efficient protocols and outage behavior[J]. IEEE Trans Inf Theory, 2004, 50(12):3062-3080.

[17] SONG G, LI Y G. Cross-layer optimization for OFDM wireless networks－part I: theoretical framework[J]. IEEE Trans Wireless Commu,2005, 4:614-624.

[18] WEN-HSING K L, WAN J L. Utility-based resource allocation in wireless networks[J]. IEEE Trans Wireless Commun, 2007, 6:3600-3606.

[19] HU X, SHI Y, EBERHART R. Recent advances in particle swarm[A].IEEE International Congress on Evolutionary Computation[C]. 2004.90-97.

[20] BOYD S, VANDENBERGHE L. Convex Optimization[M]. Cambridge: Cambridge Univ Press, 2004.

[21] YU W, RHEE W, BOYD S, etal. Iterative waterfilling for Gaussian vector multiple access channels[J]. IEEE Trans Inf Theory, 2004,50(1):145-151.