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

孫 明，吳仁超，徐耀群

(1.齊齊哈爾大學(xué)計(jì)算機(jī)與控制工程學(xué)院，黑龍江齊齊哈爾161006;2.哈爾濱商業(yè)大學(xué)系統(tǒng)工程研究所，哈爾濱150028)

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

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

1 問題模型及分析

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

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

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

其中:wj表示非實(shí)時(shí)業(yè)務(wù)中用戶j的速率權(quán)重.對(duì)式(1)構(gòu)建Lagrange函數(shù):

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

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

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

2 新注水方法

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

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

無論對(duì)于瞬時(shí)的信道還是各態(tài)歷經(jīng)信道，新的注水方法都保證所有子載波都具有相同的功率乘子，并且能對(duì)總功率在子載波中進(jìn)行完全分配，即最優(yōu)功率分配.

3 KKT最優(yōu)性條件的分析

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

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

從KKT最優(yōu)性條件中可以看出，調(diào)節(jié)所有不滿足用戶的速率閾值乘子使它們的速率達(dá)到閾值并且在正向趨向閾值，并且將滿足用戶的速率閾值乘子保持為零.

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

4 粒子群搜索Lagrange乘子算法

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

粒子群算法是近年來被廣泛關(guān)注的一種全局智能優(yōu)化算法[8－9].在使用粒子群搜索用戶的速率閾值限制乘子時(shí)，粒子群中的每個(gè)粒子的位置都是用戶的速率閾值限制乘子決策空間s中的一個(gè)解，每個(gè)粒子都會(huì)根據(jù)自己和同伴的經(jīng)驗(yàn)來調(diào)整自己的位置.

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

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

其中:ω為慣性權(quán)重，控制當(dāng)前速度對(duì)下一刻速度的影響;c1和c2為學(xué)習(xí)因子;r1和r2是(0，1)上的隨機(jī)數(shù).

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

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

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

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

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

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

Step3發(fā)現(xiàn)完整的不滿足用戶集合，得到滿足速率閾值的最優(yōu)解.不斷對(duì)比新生成的用戶速率和速率閾值限制，完整不滿足用戶集合，保證所有用戶的速率都超過速率閾值.根據(jù)完整的不滿足用戶集合，得到滿足速率閾值限制下最大的用戶速率加權(quán)和.

5 KKT最優(yōu)性分析與比較

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

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

6 仿真實(shí)驗(yàn)

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

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

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

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

表2 隨機(jī)對(duì)偶梯度算法求解結(jié)果

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

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

7 結(jié)語

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

[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]任 新.基于進(jìn)化算法和 KKT條件的正交頻多用技術(shù)(OFDM)資源優(yōu)化分配方案設(shè)計(jì)[J].科學(xué)技術(shù)與工程，2013，36(13):10828－10833.

[8]高春濤.粒子群優(yōu)化算法及其應(yīng)用[J].哈爾濱商業(yè)大學(xué)學(xué)報(bào):自然科學(xué)版，2010，26(4):442－445.

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