多小區(qū)OFDMA系統(tǒng)基于罰函數(shù)-SA的資源分配算法

(華南理工大學(xué) 電子與信息學(xué)院，廣州 510640)

1 引 言

無線通信技術(shù)的快速發(fā)展極大地改變了人們的生活，在有限的無線頻譜資源條件下，要提供高速數(shù)據(jù)傳輸和服務(wù)更多用戶，對(duì)現(xiàn)有技術(shù)是一項(xiàng)挑戰(zhàn)。正交頻分復(fù)用(Orthogonal Frequency Division Multiplexing,OFDM) 由于其特有的抗頻率選擇性衰落、抗符號(hào)間干擾的能力，能顯著提高頻譜利用率，被廣泛應(yīng)用于最新的通信系統(tǒng)中，如無線局域網(wǎng)(WLAN)、ADSL高速接入等。

在多用戶系統(tǒng)中，多載波技術(shù)需要和其它多址技術(shù)結(jié)合以實(shí)現(xiàn)多用戶復(fù)用。OFDMA系統(tǒng)將不同的子載波集分配給小區(qū)內(nèi)各個(gè)用戶。它不需要在用戶之間設(shè)置保護(hù)頻帶，并且各個(gè)用戶所使用的子載波也并不一定連續(xù)，而是允許以子載波為單位任意分配，因而具有比FDMA更高的靈活性。

目前，對(duì)OFDMA系統(tǒng)資源分配方面的研究大多只考慮單小區(qū)問題模型，A. Abrardo 等[1]雖然基于多小區(qū)進(jìn)行研究，但是其初始分配仍是基于單小區(qū)進(jìn)行。服務(wù)于多個(gè)基站的中央控制器根據(jù)現(xiàn)有反饋情況進(jìn)行集中式資源分配，通過多分配算法將不符合多小區(qū)約束條件的載波從載波集中剔除后進(jìn)行功率調(diào)整以滿足吞吐量要求的方法來進(jìn)行多小區(qū)資源分配。這樣做雖然降低了算法復(fù)雜度，但是載波資源不能充分利用。

Ian C.Wong[2]等利用傳統(tǒng)的兩分法，將分配問題轉(zhuǎn)化為子載波分配和功率分配兩個(gè)子問題分別求解。這樣將一個(gè)復(fù)雜的系統(tǒng)模型分割成兩個(gè)相對(duì)簡(jiǎn)單的模型，這樣的分配實(shí)際上只能得到一個(gè)次優(yōu)的分配結(jié)果。

A. Gjendemsjφ[3-4]等在總功率一定的情況下，使得速率最大化的問題模型中證明采用離散功率的方法能夠在不影響系統(tǒng)性能的前提下，極大地降低搜索復(fù)雜度。

針對(duì)多小區(qū)OFDMA系統(tǒng)資源分配問題，本文采用多小區(qū)多用戶同時(shí)分配子載波和功率資源，在用戶速率一定的情況下，嘗試也將功率離散化，進(jìn)行集中式資源分配以使問題模型達(dá)到最優(yōu)。本文提出的問題模型，將某一約束條件轉(zhuǎn)換為罰函數(shù)后，退化成NP難旅行商問題。因此本文進(jìn)一步給出了改進(jìn)的模擬退火算法進(jìn)行求解，極大地提高了系統(tǒng)性能，簡(jiǎn)化了復(fù)雜度。

2 系統(tǒng)模型

本文所研究的OFDMA系統(tǒng)有一個(gè)中央控制器，對(duì)不同終端和基站之間的增益進(jìn)行分析，統(tǒng)一管理多個(gè)小區(qū)的資源分配?？紤]N個(gè)小區(qū)，小區(qū)集為C={1,2,…,K}，在小區(qū)k中有Uk個(gè)用戶，用戶集為Uk={1,2,…,nk}，載波集M={1,2,…,x}，離散功率集pm∈{q1,q2,…,qm}，因此我們定義一個(gè)新的的變量xi,j,m：

(1)

(2)

式中，pi表示第i個(gè)用戶的傳輸功率值；Gi(j)表示將第j個(gè)載波分配給第i個(gè)用戶后的信道增益，對(duì)于不在同一個(gè)小區(qū)使用分配相同子載波的用戶對(duì)i而言也是屬于干擾噪聲；σ2表示其它所有的干擾和噪聲。

在OFDMA系統(tǒng)中，業(yè)務(wù)的傳輸速率是通過分配一定數(shù)目的子載波和功率來保證的，由于系統(tǒng)的總吞吐量為所有實(shí)時(shí)業(yè)務(wù)的傳輸速率之和，因此針對(duì)實(shí)時(shí)業(yè)務(wù)的優(yōu)化目標(biāo)應(yīng)該是保證傳輸速率要求的前提下最小化系統(tǒng)的發(fā)射功率，其目標(biāo)函數(shù)為

(3)

為了減少小區(qū)內(nèi)干擾，同一個(gè)小區(qū)內(nèi)，每個(gè)載波只能分配給一個(gè)用戶，可用式(4)表示：

(4)

對(duì)于某一給定的信噪比(SIR)，根據(jù)用戶速率要求和信道條件狀況，基站為每個(gè)用戶設(shè)置了一個(gè)目標(biāo)頻譜效率η：

ηi=lb(1+SIRi)

(5)

此時(shí)就可以將每個(gè)用戶分配的最大載波數(shù)ri與用戶速率Ri相關(guān)聯(lián)起來，如式(6)所示。若考慮公平性問題，只需令ri值相等：

ri=Ri/ηi

(6)

(7)

在實(shí)際應(yīng)用中，為了盡量減少各個(gè)小區(qū)之間的干擾，對(duì)每個(gè)小區(qū)內(nèi)所有用戶功率具有一定的最大功率要求，如下所示：

(8)

綜上所述，多小區(qū)OFDMA系統(tǒng)資源分配的優(yōu)化目標(biāo)是在滿足速率約束以及最大功率要求的條件下，使所有用戶的功率總和最小，如下所示：

(9)

(10)

(11)

(12)

(13)

(14)

xi,j,m∈{0,1}，?i∈Uk,j∈M

(15)

式中，式(11)是個(gè)邏輯表達(dá)式，Q表示一個(gè)很大的數(shù)，表示如果載波沒有分配給用戶，它的功率值就一定為0。式(14)表示每個(gè)用戶可以分配ri個(gè)子載波，每個(gè)子載波分配后，其功率也確定，是功率集中的某一值。由式(2)可知，式(12)是多小區(qū)分配必須要滿足的信噪比要求，即分配必須滿足式(16)所定義的信噪比要求：

(16)

式中，pi,m表示第i個(gè)用戶分配了第m個(gè)離散功率，Gi(j)表示將第j個(gè)載波分配給第i個(gè)用戶后的信道增益，不在同一個(gè)小區(qū)但卻分配相同子載波j的用戶對(duì)i而言也會(huì)產(chǎn)生干擾，B為信道帶寬，N0為零均值熱噪聲功率譜密度。

3 罰函數(shù)-模擬退火算法

在式(9)～(15)定義的優(yōu)化問題中，由于約束條件同時(shí)包含了其它小區(qū)的干擾情況，問題模型比一般的旅行商問題還要復(fù)雜許多。觀察多小區(qū)模型可以發(fā)現(xiàn)，其相對(duì)于單小區(qū)而言，相當(dāng)于增加了約束條件(12)。當(dāng)罰函數(shù)充分大時(shí)，原約束非線性規(guī)劃問題的全局極小點(diǎn)集與罰問題的全局極小點(diǎn)集相同[5]，因此我們可以采用將其變?yōu)閱涡^(qū)問題目標(biāo)值的罰函數(shù)來進(jìn)行簡(jiǎn)化。將約束問題放到目標(biāo)函數(shù)之后，就可以使目標(biāo)函數(shù)變?yōu)榱P函數(shù)，此時(shí)目標(biāo)函數(shù)變?yōu)?/p>

p(x,Mk)=f(x)+Mk{[min(0,g(x))]2}

(17)

(18)

式中，Mk是一個(gè)按一定步長(zhǎng)變化的相對(duì)大的數(shù)。由于本文在數(shù)據(jù)很小的時(shí)候，也希望能夠使得目標(biāo)值盡量滿足，所以式(17)的平方值在仿真過程中，依情況可以去掉。簡(jiǎn)化優(yōu)化問題后，就可以采用本文所提出的改進(jìn)的模擬退火算法來求解：

步驟1：初始值的選?。弘S機(jī)選擇滿足條件的一組值。具體方法為，確定不等式約束的下標(biāo)集合，一個(gè)是已經(jīng)滿足的約束條件的集合Tk，另一個(gè)是尚未滿足的約束條件的集合Sk。通過逐漸縮小Sk，增大Tk，最后使Tk包含所有約束條件，此時(shí)停止搜索。

步驟2：定解區(qū)域的確定。本文在仿真的過程中，就設(shè)置定解區(qū)域必須要滿足約束條件，一旦不滿足，就由于罰函數(shù)的存在，而使目標(biāo)值很大，從而達(dá)到結(jié)果被擯棄的效果。

步驟3：內(nèi)循環(huán)準(zhǔn)則，包括新狀態(tài)產(chǎn)生函數(shù)、新狀態(tài)接受函數(shù)和內(nèi)循環(huán)停止準(zhǔn)則。為了確定新數(shù)據(jù)是否能夠被接受，還需要選擇一個(gè)適當(dāng)?shù)慕邮芎瘮?shù)。

為了盡量簡(jiǎn)化算法模型，本文采用最簡(jiǎn)單的漢明距離的方法來產(chǎn)生新狀態(tài)，若上一次產(chǎn)生的目標(biāo)函數(shù)值比此次得出的目標(biāo)函數(shù)值大，則接受新狀態(tài)；新的目標(biāo)函數(shù)值比較大，則根據(jù)Mentropolis法則以概率e(-Δf/tk)決定是否接受新解。一旦在此局部過程中，處于穩(wěn)定狀態(tài)，則跳出此次內(nèi)循環(huán)。

本文中漢明距離并不是固定的，每次狀態(tài)更新時(shí)，都會(huì)通過一個(gè)函數(shù)來判斷采用的漢明距離。這樣，整個(gè)狀態(tài)產(chǎn)生函數(shù)簡(jiǎn)單而又不失一般性。

步驟4：外循環(huán)準(zhǔn)則，包括退溫函數(shù)和整個(gè)算法結(jié)束的準(zhǔn)則。降溫策略主要解決溫度的下降速度問題。溫度下降既不能太快也不能太慢，太快會(huì)導(dǎo)致解的質(zhì)量下降，太慢會(huì)導(dǎo)致太長(zhǎng)的運(yùn)行時(shí)間，尤其對(duì)于問題規(guī)模較大時(shí)。

本文中退溫函數(shù)采用常系數(shù)法，即tk+1=αtk,α∈(0,1)，其中α在0.8～0.99之間。該方法形式簡(jiǎn)單，而且對(duì)只要求尋找近似最優(yōu)解的問題也足夠有效，因而成為目前最常用的一種方法。α越趨近于1，意味著退溫越慢，搜索次數(shù)越多，精確度也越高。一旦全局處于抽樣穩(wěn)定狀態(tài)，結(jié)束整個(gè)算法，搜索到的能量最低態(tài)就是最優(yōu)解。

原始的模擬退火算法流程可用圖1表示，本文改進(jìn)算法中的某些方法，如新狀態(tài)產(chǎn)生的方法和退溫函數(shù)等。在仿真過程中逐步調(diào)整參數(shù)，包括漢明距離、退溫函數(shù)的常系數(shù)等，以達(dá)到最大化系統(tǒng)吞吐量的目的。

圖1 模擬退火流程圖Fig.1 Simulation annealing flow chart

4 仿真結(jié)果與分析

基于文中第2部分提出的系統(tǒng)模型，采用蒙特卡洛仿真方法來計(jì)算系統(tǒng)性能。為了更好地描述通用的蜂窩系統(tǒng)，我們采用文獻(xiàn)[6]中的仿真參數(shù)。系統(tǒng)中總帶寬為5 MHz，小區(qū)數(shù)為7，每個(gè)小區(qū)內(nèi)用戶數(shù)為16個(gè)，子載波總數(shù)為32，零均值熱噪聲功率譜密度N0為10-20。

為保證運(yùn)算的收斂性，本文對(duì)內(nèi)、外循環(huán)的最大搜索次數(shù)做了限定，一旦超過，則退出循環(huán)。內(nèi)循環(huán)最大次數(shù)設(shè)置為500次，外循環(huán)最大次數(shù)設(shè)置為1 000次。

圖2為本文提出的罰函數(shù)-模擬退火算法在各個(gè)不同的頻譜效率下的收斂情況。由于運(yùn)算過程是程序自動(dòng)控制，所以迭代次數(shù)在頻譜效率不同的情況下也會(huì)有所不同。

在搜索最優(yōu)解的過程中，模擬退火除了可以接受優(yōu)化解外，還用了一個(gè)隨機(jī)接受準(zhǔn)則(Metropolis)有限地接受惡化解，并使接受惡化解的概率慢慢趨于零，這使得算法有可能從局部最優(yōu)解中跳出，盡可能找到全局最優(yōu)解，并保證了算法的收斂性。此算法可用Markoff鏈的遍歷理論來給它以數(shù)學(xué)上的描述。理論已證明：只要初始溫度足夠高，退火過程足夠慢，模擬退火以概率1收斂到全局最優(yōu)解。

圖2 不同頻譜效率下的迭代曲線Fig.2 Iteration numbers with different spectral efficiency

圖3和圖4比較了文獻(xiàn)[1]中多分配算法及本文提出的算法兩者的性能。離散功率的取值范圍是本文仿真的關(guān)鍵，在(0，pmaxk)間進(jìn)行等間隔取值和指數(shù)間隔取值，并進(jìn)行對(duì)比。發(fā)現(xiàn)等間隔取值可以獲得更好的吞吐量。本文中的仿真圖都是等間隔功率取值與多分配進(jìn)行對(duì)比的結(jié)果，圖中所采用離散功率個(gè)數(shù)為32個(gè)。

圖3 不同頻譜效率下系統(tǒng)傳輸總功率Fig.3 Total power in different spectral efficiency

圖4 不同頻譜效率下平均用戶吞吐量Fig.4 User throughput in different spectral efficiency

多分配算法是在單小區(qū)的基礎(chǔ)上關(guān)閉某些載波并進(jìn)行功率調(diào)整來達(dá)到滿足公式(16)中所示的信噪比的要求，這必然造成載波資源的浪費(fèi)。從圖3可以看出，本文提出的算法計(jì)算出的系統(tǒng)總功率相比較于多分配算法有所增加，原因在于多分配算法是以犧牲部分資源為代價(jià)的，即被關(guān)閉的載波將不再被分配。本文采用的罰函數(shù)-SA算法充分利用載波資源，從圖4可以看出，本文提出的罰函數(shù)模擬退火算法相對(duì)于多分配算法，吞吐量可以提高大約30%。

仿真參數(shù)調(diào)整過程中，在用戶數(shù)為16的情況下，每小區(qū)內(nèi)最大功率必須大于0.5 W，否則，多分配算法也無法得到分配結(jié)果。本文仿真考慮公平性原則，所以分配給每個(gè)用戶的載波數(shù)是相同的。退溫函數(shù)常系數(shù)α一般情況下取0.9，退溫精度得到保證的同時(shí)也可以減少運(yùn)算次數(shù)。仿真過程偶爾會(huì)出現(xiàn)曲線不太平滑的情況，通過采用多次運(yùn)算取平均值的方法來達(dá)到平滑效果。

5 結(jié) 論

由于載波功率等無線資源是非常寶貴的，所以必須充分利用。歸結(jié)起來，本文的目的就是在速率一定的情況下，對(duì)載波和功率資源進(jìn)行分配，使系統(tǒng)總體功率達(dá)到最小。在對(duì)多個(gè)小區(qū)的功率和載波同時(shí)分配時(shí)，問題模型復(fù)雜性相對(duì)單小區(qū)大大提升。本文采用兩個(gè)創(chuàng)新性的方法來簡(jiǎn)化多小區(qū)資源分配問題，一是通過功率離散化，二是通過引入罰函數(shù)，使得問題模型的求解可以采用改進(jìn)的模擬退火算法。離散化的功率的設(shè)置范圍、方法和個(gè)數(shù)是本仿真的重點(diǎn)。本文提出的罰函數(shù)改進(jìn)模擬退火算法每用戶平均吞吐量相對(duì)多分配提升大約30%的性能，功率離散化的優(yōu)越性得到很大的體現(xiàn)，有很高的研究?jī)r(jià)值。多小區(qū)系統(tǒng)性能是當(dāng)前無線通信研究的重點(diǎn)，所以我們后續(xù)的工作將是針對(duì)用戶數(shù)不斷增加來研究單位功率吞吐量的變化情況。

參考文獻(xiàn)：

[1] Abrardo A,Alessandro A,Detti P,et al.Radio resource allocation problem for OFDMA cellular systems[J].Computer and Operations Research,2009,36 (5) :1572-1581.

[2] Wong C I,Shen Z,Evans L B,et al. A low complexity Algorithm for proportional resource allocation in OFDMA systems[C]//Proceedings of IEEE Workshop on Signal Processing Systems(SIPS04).[S.l.]:IEEE,2004:1-6.

[3] Gjendemsjφ A, Gesbert D,φien G E,et al.Optimal power allocation and scheduling for two cell capacity maximization[C]//Proceedings of 2006 4th International Symposium on Modeling and Optimization in Mobile, Ad Hoc and Wireless Networks.[S.l.]:IEEE,2006:1-6.

[4] Gjendemsjφ A,Gesbert D, φien E G,et al.Binary power control for sum rate maximization over multiple interfering links[J].IEEE Transactions on Wireless Communication, 2008,7(8):3164-3173.

[5] Fiacco V A,McCormick P G.Nonlinear programming:sequential unconstained minimization techniques[M].Mclean,Virginia:Research Analysis Corporation,1990.

[6] 3GPP TR25.814 V7.0.0,Physical layer aspects for evolved Universal Terrestrial Radio Access (UTRA)(Release7)[S].