段博文，蔡躍明，魏 毅，杜家華

(1．解放軍理工大學(xué) 通信工程學(xué)院，江蘇 南京210007;2．71960部隊(duì)司令部，河南信陽(yáng)464000)

全頻率復(fù)用——同時(shí)利用每個(gè)小區(qū)的所有的子載波——已成為4G網(wǎng)絡(luò)規(guī)劃部署的主要目標(biāo)［1］。而全頻率復(fù)用必定會(huì)帶來(lái)小區(qū)間干擾，這正是限制無(wú)線通信系統(tǒng)吞吐量的主要原因［2］。在多小區(qū)系統(tǒng)場(chǎng)景中，一個(gè)主要的研究熱點(diǎn)就是考慮通過(guò)怎樣控制來(lái)自鄰小區(qū)的同道干擾來(lái)優(yōu)化系統(tǒng)性能［3］。如今，分布式資源分配技術(shù)已越來(lái)越契合現(xiàn)代通信網(wǎng)絡(luò)的需求，許多研究人員已經(jīng)開(kāi)始借助博弈論來(lái)尋求資源分配和干擾協(xié)調(diào)問(wèn)題中令人滿意的解［3，5－7］，這是因?yàn)樵从诮?jīng)濟(jì)領(lǐng)域的博弈論天然地適用于無(wú)線通信系統(tǒng)的分析與建?！，F(xiàn)存的許多文獻(xiàn)研究的都是下行鏈路，在文獻(xiàn)［4］中，作者提出了一種多天線OFDMA系統(tǒng)優(yōu)先級(jí)排序和貪婪理論結(jié)合動(dòng)態(tài)分配資源的方法。在文獻(xiàn)［7］中，作者利用非合作博弈理論提出了一種發(fā)射功率自適應(yīng)的方法來(lái)減小OFDM系統(tǒng)中的小區(qū)間干擾。通過(guò)用博弈論的方法找到每個(gè)通道用戶的最優(yōu)發(fā)射功率，系統(tǒng)的吞吐量得到了提升，但這篇文獻(xiàn)并沒(méi)有考慮這種場(chǎng)景下的子載波分配問(wèn)題。

目前有關(guān)博弈論的工作主要注重功率控制，功控問(wèn)題利用連續(xù)博弈方法能夠很容易地解決。而利用博弈論進(jìn)行子載波的分配，或多或少被簡(jiǎn)化甚至被忽視，并且用來(lái)解決子載波的分配問(wèn)題要更加困難。因此本文利用聯(lián)盟形成和納什討價(jià)還價(jià)解研究了上行OFDMA系統(tǒng)中多小區(qū)分布式子載波分配的博弈問(wèn)題。

1 系統(tǒng)建模

考慮一個(gè)有M個(gè)基站的上行OFDMA系統(tǒng)，記為M={1，2，…，l，…，M}?？捎玫念l譜資源劃分為K個(gè)子載波。用戶集合和子載波集合分別記為N={1，2，…，n，…，N }和K={1，2…，k，…，K}。N=，指集合N的元素個(gè)數(shù)，K=，指集合K的元素個(gè)數(shù)。每一個(gè)基站m∈M都有一個(gè)用戶子集Nm?N，其中∪mNm=N，以及子載波集合Km，其中Km=K，?m∈M。

定義信道增益矩陣H=RN×N×K，其中hkij是指使用子載波k時(shí)發(fā)射用戶i和接受用戶j之間的信道增益。規(guī)定hkij≠hkji。hkii指使用子載波k時(shí)發(fā)射用戶i到基站的信道增益。類似地定義發(fā)射功率矩陣為P=RN×K，其中元素pik指第i個(gè)發(fā)射用戶在第k個(gè)子載波上的功率，而且必須滿足非負(fù)的限制。另外，用戶i總的發(fā)射功率不能超過(guò)。定義子載波分配矩陣為A∈{0，1}N×K，其元素aik=1為用戶i用子載波k來(lái)傳輸信息，否則aik=0。用戶和基站都分別配備一根發(fā)射天線和接收天線。第m個(gè)小區(qū)用戶i在子載波k上的容量為，其中是信干噪比，Γ=－ln(5BER)/1.5是誤比特率間隔。

2 納什討價(jià)還價(jià)解(NBS)

限于篇幅，本文略去對(duì) NBS基本概念［8－10］的闡述。本文直接闡明如何將這種方法應(yīng)用于OFDMA系統(tǒng)中的子載波分配。

在一個(gè)優(yōu)化問(wèn)題中，帕累托最優(yōu)點(diǎn)可能有多個(gè)，那么一個(gè)不能回避的問(wèn)題是:應(yīng)該尋找并采用哪個(gè)帕累托最優(yōu)點(diǎn)。在本文中，主要是以資源共享的公平性來(lái)選擇帕累托最優(yōu)點(diǎn)。在所有用戶的最小需求滿足之后，余下的資源根據(jù)各個(gè)用戶的信道條件將其成比例地分給每個(gè)用戶。而這正是納什討價(jià)還價(jià)(NBS)解的優(yōu)點(diǎn)，它在一定條件下能得到一個(gè)唯一又公平的帕累托最優(yōu)點(diǎn)。下面簡(jiǎn)要介紹NBS的相關(guān)概念:

定義1:若效用集U?RN是RN的閉凸子集，那么納什討價(jià)還價(jià)解可以通過(guò)以下優(yōu)化問(wèn)題來(lái)獲得［9］

在本文中，效用函數(shù)U定義為每個(gè)用戶所能獲得的信道容量，即Ui=Ri=∑kRik，目標(biāo)就是在最大化用戶容量的同時(shí)保證對(duì)所有用戶的公平。

3 基于納什討價(jià)還價(jià)解的分布式子載波分配算法

3.1 算法描述

顯然，式(1)描述的問(wèn)題是一個(gè)NP－h(huán)ard問(wèn)題。許多文獻(xiàn)是用集中式方法來(lái)解決這種問(wèn)題，而當(dāng)用戶和子載波數(shù)目大的時(shí)候，集中式算法的計(jì)算復(fù)雜度非常高。這一節(jié)提出了一種能獲得NBS的分布式子載波分配算法。與文獻(xiàn)［10］類似，算法先解決兩用戶情形，然后再推廣到多用戶系統(tǒng)。在多用戶系統(tǒng)中，用戶先兩兩結(jié)成聯(lián)盟，然后對(duì)每個(gè)聯(lián)盟使用先前的兩用戶的算法，來(lái)進(jìn)行子載波的交換。最后，用戶將一次次地重組聯(lián)盟并重新合作協(xié)商，直至性能不再提升。

3．1．1 聯(lián)盟形成

為了避免計(jì)算復(fù)雜度太高，本文采用文獻(xiàn)［10］中的思想。如果用戶的總數(shù)是偶數(shù)，則用戶兩兩結(jié)成聯(lián)盟。否則，假設(shè)額外存在一個(gè)“啞”用戶來(lái)確保用戶總數(shù)是偶數(shù)，任何用戶都不能與這“啞”用戶交換資源。另外，算法中的兩人聯(lián)盟是在各個(gè)小區(qū)中隨機(jī)形成的，因此只要是能使性能提升的兩人組合都將會(huì)考慮進(jìn)來(lái)。

3．1．2 對(duì)子載波進(jìn)行討價(jià)還價(jià)

一旦兩人聯(lián)盟形成，討價(jià)還價(jià)就開(kāi)始了。就像在集市討價(jià)還價(jià)一樣，兩個(gè)用戶可以協(xié)商并互換自己的資源——子載波——來(lái)使自己獲益。所有構(gòu)成聯(lián)盟的子載波——用戶的排列組合都應(yīng)進(jìn)行比較，從而得出哪一個(gè)匹配能產(chǎn)生最高的用戶速率。顯然，每個(gè)聯(lián)盟中的計(jì)算不需要聯(lián)盟與聯(lián)盟之間交互信息，因此這個(gè)算法是分布式的。然而，由于這種操作的復(fù)雜度比較高，用窮舉法搜尋最優(yōu)用戶，子載波匹配是不可行的。因此本文設(shè)計(jì)了一種有效的算法來(lái)交換用戶的子載波，這實(shí)質(zhì)上解決的是一個(gè)復(fù)雜的整數(shù)規(guī)劃問(wèn)題。即先將子載波進(jìn)行排序，然后用“兩段分”的方法為兩個(gè)用戶分配子載波。

1)算法1:兩用戶的子載波分配

(1)初始化。以最小速率需求來(lái)初始化子載波分配，初始化λ1=1和λ2=1。

(2)對(duì)子載波進(jìn)行排序，根據(jù)的值從大到小對(duì)子載波進(jìn)行排序。

(3)用戶1使用第1至j個(gè)子載波，用戶2使用第j+1至N個(gè)子載波。為了簡(jiǎn)便，假設(shè)功率是平均分配在用戶使用的子載波上的，計(jì)算U=(Ri－)。

(4)觀察每一個(gè)j對(duì)應(yīng)的分配方案能產(chǎn)生的效用，選擇能產(chǎn)生最大效用U的“兩段分”子載波分配方案，并計(jì)算對(duì)應(yīng)的R1和R2。

(5)更新信道分配。更新 λ=，λ=12。繼續(xù)第(2)步，直至效用U不再提升。)

2)算法2:多用戶的子載波分配

(1)初始化:所有子載波隨機(jī)分給用戶。

(2)聯(lián)盟形成:每個(gè)小區(qū)里隨機(jī)地形成兩人聯(lián)盟。

(3)在每個(gè)聯(lián)盟中進(jìn)行討價(jià)還價(jià)(此步驟進(jìn)行算法1)。

(4)重復(fù):重復(fù)第(2)步和第(3)步，直到?jīng)]有性能的提升。

定理1:對(duì)于多用戶的情形，如果效用集(U1，U2，…，UN)對(duì)任意兩個(gè)用戶是帕累托最優(yōu)，那么這個(gè)效用集對(duì)小區(qū)內(nèi)所有用戶都是帕累托最優(yōu)的。

證明:假設(shè)(U1，U2，…，UN)對(duì)所有的用戶來(lái)說(shuō)不是帕累托最優(yōu)，那么必定存在另外一個(gè)點(diǎn)(U'1，U'2，…，U'N)使得U'i≥Ui，?i和U'i＞Ui，?i(假設(shè)是用戶k，U'k＞Uk)。因此，對(duì)于兩個(gè)用戶k和j(j≠k)，效用點(diǎn)(U1，U2，…，UN)就不是帕累托最優(yōu)，這與先前的假設(shè)相矛盾。證畢。

因?yàn)椴煌^(qū)里的用戶是不能交換其子載波的，只有屬于相同小區(qū)的用戶可以形成聯(lián)盟并相互討價(jià)還價(jià)。應(yīng)此在多用戶系統(tǒng)中，同一個(gè)小區(qū)里的一個(gè)效用點(diǎn)對(duì)任意兩用戶都是帕累托最優(yōu)的話，這個(gè)效用點(diǎn)對(duì)這個(gè)小區(qū)的所有用戶都是帕累托最優(yōu)的。

3.2 收斂性分析

在每一次迭代過(guò)程中，優(yōu)化函數(shù)R的值是不會(huì)下降的。而每個(gè)用戶的先用函數(shù)值Ri有上界。所以，本文提出的算法必定收斂。

3.3 復(fù)雜度分析

在每一次迭代中，算法的復(fù)雜度為O(N2)，本文可以利用文獻(xiàn)［10］中所用的二進(jìn)制搜索算法進(jìn)一步將其降至O(NlogN)。

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

本節(jié)對(duì)改進(jìn)的子載波分配算法進(jìn)行了仿真?？紤]3小區(qū)的OFDMA系統(tǒng)。與文獻(xiàn)［6］中類似，每個(gè)蜂窩小區(qū)半徑100 m，且各個(gè)小區(qū)都有12個(gè)用戶隨機(jī)地均勻分布?；疚挥谛^(qū)中心，相互之間間隔 1 00m。兩用戶之間的路徑損耗表示為hij=0.097/，其中 υ =4是發(fā)射用戶i到接收用戶j之間的距離。對(duì)于用戶i，j和子載波k，信道增益為gkij=hij，其中 βk～CN(0，1)服從瑞利衰落。為了簡(jiǎn)便，令Γ=1，并在仿真中利用==lb(1+)做容量的比較。高斯噪聲方差σ2為10－10W。用戶的最大功率限制設(shè)為0．2 W。

先對(duì)各用戶進(jìn)行隨機(jī)的子載波分配初始化，然后各用戶通過(guò)相互間的合作協(xié)商尋求各自性能的提升。圖1展示了改進(jìn)的子載波分配算法導(dǎo)致的用戶容量的提升與迭代次數(shù)的關(guān)系，并且分別考慮了存在8個(gè)、32個(gè)和64個(gè)子載波時(shí)的12個(gè)用戶的OFDMA系統(tǒng)。從圖中可見(jiàn)容量值隨迭代次數(shù)的增加不斷提升，最后穩(wěn)定于某一速率值。另外從圖中得知，隨著子載波數(shù)目的增加，由于頻率分集的提升，系統(tǒng)容量也會(huì)隨之上升。

圖1 系統(tǒng)容量與迭代次數(shù)的關(guān)系

在圖2中，將本文的算法(Algorithm 1)和另外兩種算法(Algorithm 2，Algorithm 3)進(jìn)行了對(duì)比。算法2是指每個(gè)子載波根據(jù)其用戶的信道條件進(jìn)行分配，算法3是指每個(gè)用戶分有相同數(shù)目的子載波。另外，本文對(duì)3種算法都進(jìn)行等功率分配，并固定子載波數(shù)目為64個(gè)。圖2展示了系統(tǒng)容量與用戶數(shù)目變化之間的關(guān)系，表明了本文所提算法的性能比較優(yōu)越。

圖2 系統(tǒng)容量與用戶數(shù)量的關(guān)系

圖3 不同用戶的容量比較

5 結(jié)論

本文研究了多小區(qū)OFDMA系統(tǒng)因同道干擾導(dǎo)致的系統(tǒng)容量受限問(wèn)題，提出了一種底復(fù)雜度且有效的子載波分配算法。本文的研究目標(biāo)是在控制同道干擾的同時(shí)最大化系統(tǒng)性能。本文所提算法基于合作博弈概念，即用戶先結(jié)成聯(lián)盟再對(duì)子載波進(jìn)行討價(jià)還價(jià)。這種算法的全分布式特性非常適用于多小區(qū)干擾協(xié)調(diào)場(chǎng)景。仿真結(jié)果表明本文所提算法具有快收斂、明顯的容量提升以及良好的公平性3種優(yōu)點(diǎn)。下一步工作，將關(guān)注與同時(shí)優(yōu)化功率和子載波分配，從而期望能達(dá)到更高的系統(tǒng)吞吐量。

:

［1］ CHENG Shinming，LIEN Shouyu．On exploiting cognitive radio to mitigate interference in macro/femto heterogeneous networks［J］．IEEE Wireless Communications，2011，1(3):40－46．

［2］ YANG Kai，PRASAD Narayan，WANG Xiaodong．An auction approach to resource allocation in uplink OFDMA systems［J］．IEEE Trans．Signal Processing，2009，57(11):4482－4496．

［3］ KWON Hojoong，LEE Byeonggi．Distributed resource allocation through noncooperative game approach in multi－cell OFDMA systems［C］//Proc．IEEE ICC．Istanbul:IEEE Press，2006:4345－4350 ．

［4］司釗，張靜，董建萍，等．多天線OFDMA系統(tǒng)的動(dòng)態(tài)子載波與功率分配方法［J］．電視技術(shù)，2009，33(S2):179－182．

［5］ HAN Zhu，JI Zhu，LIU K J R．Non－cooperative resource competition game by virtual referee in multi－cell OFDMA networks［J］．IEEE Journal on Selected Areas in Communications，2007，25(6):1079－1090．

［6］ AL－ZAHRANI A Y，YU F R．A game theory approach for inter－cell interference management in OFDM networks［C］//Proc．IEEE ICC．Kyoto:IEEE Press，2011:1－5．

［7］ TAN C K，SIM M L，CHUAH T C．Blotto game－based low－complexity fair multiuser subcarrier allocation for uplink OFDMA networks［EB/OL］．［2014－02－10］．http://jwcn．eurasipjournals．com/content/2011/1/53．

［8］ ZHOU L．The Nash bargaining theory with non－convex problems［J］．Econometrica，1997，65(5):681－685．

［9］ ZHU HAN，ZHU JI，LIU K J R．Fair multiuser channel allocation for OFDMA networks using Nash bargaining solutions and coalitions［J］．IEEE Trans．Communications，2005，53(8):1366－1376．

［10］ VATSIKAS S，ARMOUR S，VOS M D，et al．A distributed algorithm for wireless resource allocation using coalitions and the Nash bargaining solution［C］//Proc．IEEE VTC．［S．l．］:IEEE Press，2011:1－5．