基于注水方法與粒子群的多用戶OFDM資源分配

孫 明，吳仁超，徐耀群

(1.齊齊哈爾大學計算機與控制工程學院，黑龍江齊齊哈爾161006;2.哈爾濱商業大學系統工程研究所，哈爾濱150028)

OFDM是下一代無線通信標準的物理層核心接入方案[1].OFDM資源分配算法的選擇會對系統性能有很大的影響.近年來，設計高效的OFDM資源分配算法已成為了無線通信領域的一個研究熱點.為了滿足各個用戶的QoS需求，需要考慮到各個用戶的信道狀況和總功率預算，并以最佳用戶體驗作為目標.文獻[2]中證明將每個子載波分配給信道狀況最佳的用戶，同時采用注水方法對功率進行分配，可得到最大的系統速率和.Wong在文獻[3]中提出將功率平分到每個子載波上的低復雜度次優解方案.對于較大小區的OFDM資源分配問題，Bohge推薦使用動態分配算法[4].Kelly在文獻[5]中提出基于對數的效用函數，并且證明了使用對數函數能夠達到比例公平.Wang在文獻[6]中研究了在各態歷經信道中下行OFDM系統的資源分配，提出了隨機對偶梯度算法.在每個用戶速率閾值的要求下，為了實現用戶速率加權和的最大化，Wang采用傳統的注水算法，在功率乘子與子載波分配之間進行大量的相互迭代，并同時對用戶速率閾值乘子進行調整[6].由于在功率乘子與子載波分配大量的相互迭代中，功率乘子與子載波分配都不是最優的，因此會影響用戶速率閾值乘子調整的準確性.另外，Wang的算法對于用戶速率閾值乘子的調整也只限于增加不滿足用戶的乘子的數值，從而沒有嚴格滿足KKT最優性條件.

在各態歷經信道下，本文首先提出一種快速準確地同時定位最優功率乘子與最優子載波分配的新的注水方法，避免了功率乘子與子載波分配的相互迭代對用戶速率閾值乘子調整的影響.為了在滿足用戶的速率閾值的要求下實現用戶速率加權和的最大化，本文采用粒子群算法[7]調整速率閾值乘子，嚴格依照KKT最優性條件精準地定位最優解.對5用戶32子載波的各態歷經信道的多用戶OFDM下行傳輸進行了仿真，實驗結果證明，本文算法所求的用戶速率加權和高于Wang的隨機對偶梯度算法.

1 問題模型及分析

考慮非實時業務中各態歷經信道的OFDM下行傳輸，j={1，…，J)為用戶集合，k={1，…，K}為子載波集合，子載波k的傳輸功率為pk，子載波的總傳輸功率為pT.在一個完整的OFDM周期內，每個用戶可以使用一個或以上的子載波進行傳輸，但一個子載波只可以分配給一個用戶.pj，k表示子載波k分配給用戶j時的功率.假定用戶j在子載波k上的信道增益與噪聲功率的比值γj，k可以被基站完全接收，用戶j在子載波k上的傳輸速率為cj，k(p)=log2(1+pj，kγj，k).考慮各態歷經信道，用戶 j的平均最大可達速率為，平均總傳輸功率為.在每個用戶有不同速率閾值要求的非實時業務中，多用戶OFDM資源分配問題可描述為:在滿足以下兩個條件下，最大化用戶速率加權和.

1)平均總傳輸功率之和等于總傳輸功率要求pT;

該多用戶OFDM資源分配問題的數學模型可描述為[6]:

其中:wj表示非實時業務中用戶j的速率權重.對式(1)構建Lagrange函數:

當前子載波分配{j*1(λ)，…，j*K(λ)}下的最優功率乘子λ*滿足注水函數最優性條件(λ*)]=pT.

從鏈路質量指標函數(3)中可以看出由當前功率乘子根據鏈路質量函數指標最優性條件可以直接計算得到當前子載波分配.但在注水函數(4)中無法根據注水函數最優性條件直接計算得到當前子載波分配下的最優功率乘子.為了確定最優子載波分配和對應的最優功率乘子，Wang采用傳統的注水算法，對功率乘子進行數值搜索并在功率乘子與子載波分配之間進行大量的相互迭代，直到發現滿足鏈路質量指標最優性條件和注水函數最優性條件的最優子載波分配以及與之對應的最優功率乘子.由于子載波分配和功率乘子的相互迭代影響用戶速率乘子的調整，所以會間接影響用戶速率乘子的KKT最優性條件的滿足.

本文提出的新的注水方法，在面對任何子載波分配時，都可以直接計算得到當前子載波分配下的滿足注水函數最優性條件的最優功率乘子，使得傳統注水算法中子載波分配與功率乘子之間的大量相互迭代變成有限的精確的相互迭代.另外，由于子載波分配和與之對應的最優功率乘子之間相互迭代有著明確目標，所以可以在發現最優子載波分配和對應的最優功率乘子后展開對用戶速率乘子調整.采用新的注水方法取代傳統的注水算法，不僅可以降低子載波分配與功率乘子之間的相互迭代的計算量，還可避免由于非最優子載波和非最優功率乘子對用戶速率乘子的調整而影響KKT最優性條件的滿足.

2 新注水方法

新注水方法在面對不同的子載波分配方案時都可以快速地滿足注水函數的功率完全分配.新注水方法不僅對瞬時的信道質量有效，同樣適用于各態歷經信道.在子載波分配完畢之后由小到大排序到注水門檻集合中.令1/λln2不斷增大，使其在兩個相鄰的注水門檻組成注水門檻區間依次取值.具體如下:

對于瞬時的信道，在0到K之間確定I*使得pT(λ)的取值范圍包含 pT.根據式(8)，由 I=I*，pT(λ)=pT，可以得出最優功率乘子.對于各態歷經信道，將不同信道的所有注水門檻統一到一個總注水門檻集合里，這個集合中注水門檻有NK個.在0～NK之間確定I*使得 Eγ[pT(λ)]的取值范圍包含 pT.根據式(6)，由 I=I*，Eγ[pT(λ)]=pT可以得出最優功率乘子

無論對于瞬時的信道還是各態歷經信道，新的注水方法都保證所有子載波都具有相同的功率乘子，并且能對總功率在子載波中進行完全分配，即最優功率分配.

3 KKT最優性條件的分析

KKT最優性條件能夠保證拉格朗日的最優性[7].對于速率閾值限制的Lagrange乘子u=0的情況，采用新注水方法可以得到在沒有速率閾值限制下最大化用戶速率加權和的用戶速率c*=(c1*，…).令表示速率閾值限制.基于c*與的廣義關系，在具有速率閾值限制的最大化速率加權和問題中，對速率閾值限制乘子和用戶速率滿足KKT最優性條件的分析如下:

3)若c*與之間沒有廣義不等的關系，就必須通過調整速率閾值乘子可以使用戶速率與速率閾值乘子滿足KKT最優性條件:若＞0則uj1＞0;若~cj2＞則 uj2=0，其中={c1，…，cJ}為滿足KKT最優性條件的用戶速率，j1稱為不滿足用戶，j2稱為滿足用戶，(j1，j2∈J).

從KKT最優性條件中可以看出，調節所有不滿足用戶的速率閾值乘子使它們的速率達到閾值并且在正向趨向閾值，并且將滿足用戶的速率閾值乘子保持為零.

從c*與的比較中挑選出所有不滿足用戶作為初始不滿足用戶集合，調整初始不滿足用戶集合中所有用戶的速率閾值限制乘子，使得初始不滿足用戶集合中所有用戶的速率達到閾值并且在正向趨向閾值.初始調整完畢后，由于對用戶速率閾值乘子的調整會影響到其他用戶的速率，所以一些原來滿足用戶有可能會變成不滿足用戶，這些用戶是隱藏不滿足用戶，必須將新出現的隱藏不滿足用戶加入到不滿足用戶集合.對新的不滿足用戶集合中的所有用戶再次進行上述的速率閾值限制乘子調整，直到不再出現隱藏不滿足用戶.對于一直滿足要求的用戶，速率閾值限制乘子始終保持為零.

4 粒子群搜索Lagrange乘子算法

在c*與之間沒有廣義不等的關系的情況下，本文通過粒子群搜索所有用戶的速率閾值限制乘子以不斷修正不滿足用戶集合，發現最優速率閾值限制乘子，使得用戶速率與速率閾值限制乘子都滿足KKT最優性條件.

粒子群算法是近年來被廣泛關注的一種全局智能優化算法[8－9].在使用粒子群搜索用戶的速率閾值限制乘子時，粒子群中的每個粒子的位置都是用戶的速率閾值限制乘子決策空間s中的一個解，每個粒子都會根據自己和同伴的經驗來調整自己的位置.

以用戶的速率閾值限制乘子x為目標向量，在決策空間s中隨機生成初始種群，種群規模為I.根據已知的不滿足用戶集合，規定決策空間s中所有不滿足用戶的速率閾值限制乘子的統一下限為零，統一上限為U，所有滿足要求的用戶的閾值乘子始終保持為零.

在t時刻，第i(i=1，…，I)個粒子的位置為xi(t)，飛行速度為vi(t)，它在飛行過程中本身到達過的最好位置為pbi(t)，所有粒子在飛行過程中到達的最好位置為gb(t).第t+1時刻，第i個粒子根據式(8)、(9)更新自己的速度與位置:

其中:ω為慣性權重，控制當前速度對下一刻速度的影響;c1和c2為學習因子;r1和r2是(0，1)上的隨機數.

由于速率閾值乘子的可行解是非負數，所以粒子位置存在正向邊界.粒子的最佳位置由適應度函數決定.第i個粒子在t時刻的適應度函數fi(t)如下:

其中:D為不滿足用戶的個數，對于不滿足用戶集合中的所有用戶，ci，d(t)為第d個不滿足用戶的t時刻的速率，d為第d個不滿足用戶的速率閾值，wd為第d個不滿足用戶的速率權重.適應度函數的目的是滿足所有不滿足用戶的速率超過速率閾值下使所有不滿足用戶的速率在正向趨向各自的閾值.所以粒子適應度函數值越小，代表著由這個粒子的位置對應的用戶速率對KKT最優性條件的滿足程度越高，粒子的位置越優.

在t時刻，第i個粒子的最好位置pbi(t)，所有粒子最好位置gb(t)，可由式(12)、(13)計算得到.

粒子群搜索Lagrange乘子的算法流程可描述為:

Step1求解無速率閾值的最優方案，發現初始不滿足用戶集合.令速率閾值限制的乘子集合u=0，根據新的注水方法得到在沒有速率閾值限制下最大化用戶速率加權和的用戶速率c*=(c1*，…，若c*與之間沒有廣義不等的關系，則將無速率閾值限制的最大化速率加權和的最優解中的所有不滿足用戶作為初始不滿足用戶集合.

Step2利用粒子群算法搜索用戶的速率閾值限制乘子.由不滿足用戶集合確定決策空間s，生成用戶的速率閾值限制乘子的初始種群.根據新的注水方法得到該種群中每個粒子對應的用戶速率，并計算出粒子的適應度函數，根據適應度函數，粒子更新自己的速度與位置，展開了在決策空間s中對最優位置的搜索.搜索完畢后，生成新的用戶速率.

Step3發現完整的不滿足用戶集合，得到滿足速率閾值的最優解.不斷對比新生成的用戶速率和速率閾值限制，完整不滿足用戶集合，保證所有用戶的速率都超過速率閾值.根據完整的不滿足用戶集合，得到滿足速率閾值限制下最大的用戶速率加權和.

5 KKT最優性分析與比較

Wang的隨機對偶梯度算法[6]原理上是次梯度算法，它同時對功率乘子與速率閾值乘子以及子載波分配進行迭代調整.該算法使速率閾值乘子和子載波分配按照鏈路質量指標函數最優性條件和注水函數最優性條件緩慢逼近于最優子載波分配和最優功率乘子;在此同時，增加不滿足用戶的速率閾值乘子，使其速率增長逼近各自對應的速率閾值，并且保持當前滿足用戶的功率閾值乘子不變.由于隨機對偶梯度算法不能快速求解最優功率乘子，并且只能緩慢逼近最優功率乘子和最優子載波分配，因此會影響用戶速率乘子對KKT最優性條件的滿足.另外，隨機對偶梯度算法只是使每個用戶的速率達到閾值，缺乏使其在正向趨向閾值的整體調節措施.由上述可知，隨機對偶梯度算法在真正意義上不滿足KKT最優性條件.

根據本文提出的新注水方法可以直接計算得到當前子載波分配下的最優功率乘子，確定了子載波分配與功率乘子之間的相互迭代的目標，從而避免了非最優功率乘子和非最優子載波分配對用戶速率閾值乘子搜索的影響.另外，粒子群搜索Lagrange乘子算法可以使不滿足用戶速率閾值乘子的調整具有了整體性，更加符合KKT最優性條件.

6 仿真實驗

假設一個5用戶OFDM下行傳輸系統的頻選無線各態歷經信道，總帶寬為1MHz，有32個子載波，噪聲能量密度為10－8，包括了2個獨立生成的信道，用戶的信道增益服從Rayleigh分布，信道增益期望為Eγ=(0.3，0.7).在該5用戶OFDM下行傳輸，用戶數J=5，子載波數N=32，各態歷經信中總注水門檻數NK=64.在每個OFDM周期中的傳輸速率權重 w=(25，25，20，15，15)，速率閾值為=(40，40，25，10，10)，總功率限制為 1Wett.

首先利用新注水方法結合粒子群搜索Lagrange乘子算法對用戶速率加權和進行最大化.取粒子群參數ω=1，r1=r2=1.8，，決策空間 s中不滿足用戶的速率閾值限制乘子的統一上限U=采用新注水方法結合粒子群搜索 Lagrange乘子算法求得的結果，如表1所示.

表1 新注水方法結合粒子群搜索Lagrange乘子算法的求解結果

然后，采用文獻[6]的隨機對偶梯度算法對用戶速率加權和進行最大化，得到的滿足速率閾值限制下的最大用戶速率加權和，如表2所示.

表2 隨機對偶梯度算法求解結果

在表1、2中，c*是在沒有速率閾值限制下最大化用戶速率加權和的用戶速率，~c則是由基于粒子群搜索速率閾值Lagrange乘子得出的是滿足速率閾值限制下最大的用戶速率加權和的用戶速率.wc*是在沒有速率閾值限制下最大化用戶速率加權和，~wc則是滿足速率閾值限制下最大的用戶速率加權和.在仿真過程中，用戶4和用戶5是初始階段的不滿足用戶，用戶3則是隱藏不滿足用戶，用戶3、用戶4和用戶5組成了完整不滿足用戶.

在表1中，新注水方法結合粒子群搜索Lagrange乘子算法將用戶3、用戶4和用戶5組成了完整不滿足用戶集合，并保持用戶1和用戶2等滿足用戶的速率閾值乘子始終為零，通過粒子群算法使完整不滿足用戶集合的用戶速率達到并且從正向逼近其速率閾值，最終得到5個用戶的速率加權和總和為5.503 9×103.在表2中，隨機對偶梯度算法使用戶3、用戶4以及用戶5的速率達到其閾值但沒有從正向逼近其速率閾值，最終得到5個用戶的速率加權和總和為5.499 5×103.通過以上分析比較不難看出，新注水方法結合粒子群搜索Lagrange乘子算法得到的速率加權總和高于隨機對偶梯度算法.

7 結語

在各態歷經信道下，本文提出了一種快速準確地定位最優子載波分配與最優功率乘子的新注水方法，并使用新注水方法結合粒子群算法搜索Lagrange乘子并最大化用戶速率加權和.與隨機對偶梯度算法相比，本算法能更好地滿足KKT最優性條件.仿真結果證明了本算法能夠在滿足速率閾值的限制下得到更大的用戶速率加權和.

[1]3rd Generation Partnership Project，Technical Specification Group Radio Access Network;Physical layer aspects for evolved Universal Terrestrial Radio Access(UTRA)，3GPP Std[S].TR 25.814 v.7.0.0，2006.

[2]YIN H，LIU H.An efficient multiuser loading algorithm for OFDM－based broadband wireless systems[C]//San Francisco:Global Telecommunications Conference，2000.103 － 107.

[3]WONG I C，SHEN Z，B L EVANS，et al.A low complexity algorithm for proportional resource allocation in OFDMA systems[C]//Proc IEEE Workshop on Signal Processing Systems，2004.1－6.

[4]BOHGE M，GROSS J，WOLISZ A.The potential of dynamic power and sub－carrier assignments in multi－user OFDM－FDMA cells[C]//Proc.Global Telecommunications Conference，St.Louis，MO，2005(5):2932 －2936.

[5]KELLY F P.Charging and rate control for elastic traffic [J].Europe Trans.on Telecommun，1997(8):33 －37.

[6]WANG X，GIANNAKIS G B.Resource allocation for wireless multiuser OFDM networks[J].IEEE Trans.on Information Theory，2011，57(7):4359－4372.

[7]任 新.基于進化算法和 KKT條件的正交頻多用技術(OFDM)資源優化分配方案設計[J].科學技術與工程，2013，36(13):10828－10833.

[8]高春濤.粒子群優化算法及其應用[J].哈爾濱商業大學學報:自然科學版，2010，26(4):442－445.

[9]徐耀群，王長舉.一種萬有引力優化算法及其收斂性分析[J].哈爾濱商業大學學報:自然科學版，2013，29(1):63－67.