一種多小區OFDMA系統中有效公平的資源分配方法

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

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

全頻率復用——同時利用每個小區的所有的子載波——已成為4G網絡規劃部署的主要目標［1］。而全頻率復用必定會帶來小區間干擾，這正是限制無線通信系統吞吐量的主要原因［2］。在多小區系統場景中，一個主要的研究熱點就是考慮通過怎樣控制來自鄰小區的同道干擾來優化系統性能［3］。如今，分布式資源分配技術已越來越契合現代通信網絡的需求，許多研究人員已經開始借助博弈論來尋求資源分配和干擾協調問題中令人滿意的解［3，5－7］，這是因為源于經濟領域的博弈論天然地適用于無線通信系統的分析與建模。現存的許多文獻研究的都是下行鏈路，在文獻［4］中，作者提出了一種多天線OFDMA系統優先級排序和貪婪理論結合動態分配資源的方法。在文獻［7］中，作者利用非合作博弈理論提出了一種發射功率自適應的方法來減小OFDM系統中的小區間干擾。通過用博弈論的方法找到每個通道用戶的最優發射功率，系統的吞吐量得到了提升，但這篇文獻并沒有考慮這種場景下的子載波分配問題。

目前有關博弈論的工作主要注重功率控制，功控問題利用連續博弈方法能夠很容易地解決。而利用博弈論進行子載波的分配，或多或少被簡化甚至被忽視，并且用來解決子載波的分配問題要更加困難。因此本文利用聯盟形成和納什討價還價解研究了上行OFDMA系統中多小區分布式子載波分配的博弈問題。

1 系統建模

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

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

2 納什討價還價解(NBS)

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

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

定義1:若效用集U?RN是RN的閉凸子集，那么納什討價還價解可以通過以下優化問題來獲得［9］

在本文中，效用函數U定義為每個用戶所能獲得的信道容量，即Ui=Ri=∑kRik，目標就是在最大化用戶容量的同時保證對所有用戶的公平。

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

3.1 算法描述

顯然，式(1)描述的問題是一個NP－hard問題。許多文獻是用集中式方法來解決這種問題，而當用戶和子載波數目大的時候，集中式算法的計算復雜度非常高。這一節提出了一種能獲得NBS的分布式子載波分配算法。與文獻［10］類似，算法先解決兩用戶情形，然后再推廣到多用戶系統。在多用戶系統中，用戶先兩兩結成聯盟，然后對每個聯盟使用先前的兩用戶的算法，來進行子載波的交換。最后，用戶將一次次地重組聯盟并重新合作協商，直至性能不再提升。

3．1．1 聯盟形成

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

3．1．2 對子載波進行討價還價

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

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

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

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

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

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

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

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

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

(2)聯盟形成:每個小區里隨機地形成兩人聯盟。

(3)在每個聯盟中進行討價還價(此步驟進行算法1)。

(4)重復:重復第(2)步和第(3)步，直到沒有性能的提升。

定理1:對于多用戶的情形，如果效用集(U1，U2，…，UN)對任意兩個用戶是帕累托最優，那么這個效用集對小區內所有用戶都是帕累托最優的。

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

因為不同小區里的用戶是不能交換其子載波的，只有屬于相同小區的用戶可以形成聯盟并相互討價還價。應此在多用戶系統中，同一個小區里的一個效用點對任意兩用戶都是帕累托最優的話，這個效用點對這個小區的所有用戶都是帕累托最優的。

3.2 收斂性分析

在每一次迭代過程中，優化函數R的值是不會下降的。而每個用戶的先用函數值Ri有上界。所以，本文提出的算法必定收斂。

3.3 復雜度分析

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

4 仿真結果與分析

本節對改進的子載波分配算法進行了仿真。考慮3小區的OFDMA系統。與文獻［6］中類似，每個蜂窩小區半徑100 m，且各個小區都有12個用戶隨機地均勻分布。基站位于小區中心，相互之間間隔 1 00m。兩用戶之間的路徑損耗表示為hij=0.097/，其中 υ =4是發射用戶i到接收用戶j之間的距離。對于用戶i，j和子載波k，信道增益為gkij=hij，其中 βk～CN(0，1)服從瑞利衰落。為了簡便，令Γ=1，并在仿真中利用==lb(1+)做容量的比較。高斯噪聲方差σ2為10－10W。用戶的最大功率限制設為0．2 W。

先對各用戶進行隨機的子載波分配初始化，然后各用戶通過相互間的合作協商尋求各自性能的提升。圖1展示了改進的子載波分配算法導致的用戶容量的提升與迭代次數的關系，并且分別考慮了存在8個、32個和64個子載波時的12個用戶的OFDMA系統。從圖中可見容量值隨迭代次數的增加不斷提升，最后穩定于某一速率值。另外從圖中得知，隨著子載波數目的增加，由于頻率分集的提升，系統容量也會隨之上升。

圖1 系統容量與迭代次數的關系

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

圖2 系統容量與用戶數量的關系

圖3 不同用戶的容量比較

5 結論

本文研究了多小區OFDMA系統因同道干擾導致的系統容量受限問題，提出了一種底復雜度且有效的子載波分配算法。本文的研究目標是在控制同道干擾的同時最大化系統性能。本文所提算法基于合作博弈概念，即用戶先結成聯盟再對子載波進行討價還價。這種算法的全分布式特性非常適用于多小區干擾協調場景。仿真結果表明本文所提算法具有快收斂、明顯的容量提升以及良好的公平性3種優點。下一步工作，將關注與同時優化功率和子載波分配，從而期望能達到更高的系統吞吐量。

:

［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系統的動態子載波與功率分配方法［J］．電視技術，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．