基于非合作博弈的OFDMA無線多跳中繼網絡上行鏈路資源分配算法

向征，方旭明，徐鵬,3

（1. 西南交通大學 信息編碼與傳輸重點實驗室，四川 成都 610031；2. 中國民航飛行學院 空中交通管理學院，四川 廣漢 618307；3. 西南交通大學 數學學院，四川 成都 610031）

1 引言

近年來，無線多跳中繼技術[1]因其在提升系統吞吐量、減少系統發射功率等方面所表現出來的優勢，越來越受到研究學者的關注。另一方面，正交頻分多址接入技術[2]（OFDMA）與FDMA、TDMA和CDMA等傳統多址技術相比，由于具有占用帶寬小、無碼間干擾以及多用戶分集等優點，已經被LTE-Advanced、IEEE 802.16m等下一代無線寬帶接入網絡標準所采用。因此，將2種技術相結合的OFDMA無線多跳中繼網絡中的各項關鍵技術都非常值得研究，無線資源分配問題即是其中之一。

關于OFDMA網絡無線資源分配的研究成果按場景可以分為單小區和多小區2種。在單小區場景下，其他小區對本小區的干擾被完全忽略，通過利用最優化方法，在一定的限制條件下來最大化系統吞吐量（即余量自適應）或者最小化系統總發射功率（即速率自適應）。余量自適應（MA）的優化目標是在一定的網絡吞吐量和誤碼率限制下最小化網絡總發射功率，即以節省系統能耗為目的，文獻[3]和文獻[4]討論了此種優化目標。而速率自適應（RA）的優化目標是在一定的網絡總發射功率限制下最大化網絡吞吐量，文獻[5]和文獻[6]對該優化目標進行了深入的研究。

實際蜂窩系統一般都是干擾受限的，小區間干擾是影響系統性能的關鍵因素，所以單小區場景不能真實地反映整個網絡的性能。因此，考慮各小區間干擾的多小區場景就成為了更合理的研究場景。然而，在多小區場景下，各小區之間無法共享信道狀態信息，各小區用戶只能以局部方式最大化自身性能，由此將導致系統性能不升反降。另一方面，博弈論作為一種新興的研究手段，已經在無線通信研究的各個領域得到了廣泛應用。而作為其中一個分支的非合作博弈論，也逐漸被應用到了多小區 OFDMA系統資源分配的研究中。文獻[7]應用非合作博弈論研究了OFDMA系統多小區功率協調問題，但未將子載波分配和功率分配聯合進行優化。為了解決此問題，文獻[8]在提出最小干擾準則的用戶調度的基礎上運用非合作博弈論對系統功率進行聯合優化。文獻[9]考慮了包含中繼的多小區 OFDMA系統下行鏈路資源分配問題，但只對第2跳進行了分析。文獻[10]和文獻[11]對多小區 OFDMA無線多跳中繼網絡下行資源分配問題進行了研究，運用非合作博弈論對中繼情況下的2跳鏈路分別進行了建模和分析。文獻[12]則對多小區OFMDA系統單跳上行鏈路資源分配問題進行了一定的研究。雖然以上文獻對多小區OFDMA系統的資源分配進行了深入研究，但都沒有考慮包含中繼上行鏈路資源分配的情況。

基于上述研究背景，本文應用非合作博弈論對多小區場景下OFMDA無線多跳中繼網絡上行鏈路的資源分配問題進行了研究。首先建立了多小區OFMDA無線多跳中繼網絡上行鏈路的資源分配優化模型，然后給出了包含定價機制的非合作功率分配博弈模型，并且證明了在該模型中納什均衡點的存在性和唯一性。最后，提出了求解該非合作博弈模型的分布式算法，并通過仿真分析驗證了該算法的性能。

2 系統模型

考慮一種典型的采用OFDMA多址技術的多跳中繼網絡（如圖 1所示）。各小區中心有一個中心基站（BS），在靠近小區邊緣的位置有多個中繼站（RS）用來提升小區邊緣覆蓋質量。小區中的各移動臺（MS）選擇距離自己最近的BS或者RS來接入網絡，接入BS的MS稱為直傳MS，接入RS的MS稱為中繼MS。由于本文考慮的是上行鏈路的資源分配，因此需要考慮以下2種上行鏈路；第1種是從MS到BS的直傳鏈路，第2種是先由MS發送到RS，再從RS轉發到BS的中繼鏈路。這里將每一個發送時隙（即調度周期）分為2個子時隙，如圖2所示。在第1個子時隙中，各個小區的直傳鏈路，以及中繼鏈路的第1跳進行傳輸，因此發送節點為各小區中的MS；在第2個子時隙中，只有中繼鏈路的第2跳進行傳輸，因此發送節點為各小區中的 RS。另外，在各個小區內部，某一子載波在任何一個子時隙中只能分配給一個發送節點，而其他小區中的發送節點則能夠同時使用該子載波。因此，小區內沒有同頻干擾，而小區之間存在同頻干擾。

圖1 基于OFDMA的多跳中繼網絡拓撲示意

圖2 上行鏈路一個調度周期中的幀結構

設系統中有I個具有同頻干擾的小區，用i（i∈1,2,…,I）表示各小區序號。各小區中MS的數量為K個，RS的數量為6個。系統帶寬為B，子載波數量為N，則每個子載波帶寬為Bn=B/N。在第1個子時隙中，Hi,k,n表示小區i中的第k個MS在第n個子信道上的上行鏈路信道增益，為同頻小區j中在第n個子信道上同時進行發送的MS到小區i的BS或RS的信道增益。因此，在第1個子時隙中，小區i中的第k個MS在第n個子信道上的上行鏈路信干噪比可表示為

其中，pi,k,n為小區i中的第k個MS在第n個子信道上的發送功率，pj,k,n表示同頻小區j中在第n個子信道上同時進行發送 MS的發送功率，σ2為AWGN功率。同理可得，在第2個子時隙中，小區i中的第m個RS在第n個子信道上的上行鏈路信干噪比為

其中，Hi,m,n表示小區i中的第m個RS在第n個子信道上的上行鏈路信道增益，為同頻小區j中在第n個子信道上同時進行發送的RS到小區i的 BS的信道增益。pi,m,n為小區 i中的第 m個RS在第n個子信道上的發送功率，pj,m,n表示同頻小區j中在第n個子信道上同時進行發送RS的發送功率。

對于一定的誤碼率（BER），可以求得在第 1個子時隙中，小區i中的第k個MS在第n個子信道上的上行鏈路信道容量為

其中，Γ為實際系統M-QAM調制信號和信道香農容量的 SNR差值，其與 BER 的關系為Γ=-ln(5BER)/1.5[5]。同理可知，在第2個子時隙中，小區i中的第m個RS在第n個子信道上的上行鏈路信道容量為

其中，Sk為在第1個子時隙中直傳MS所分配到的子信道集合。為小區i中的第k個中繼MS所能達到的上行速率，其中，由第 1跳鏈路速率和第2跳鏈路速率之間的小者決定，即

其中，Xk為在第1個子時隙中中繼MS所分配到的子信道集合，Yk為在第2個子時隙中為該中繼MS進行轉發的RS所分配到的子信道集合。本文的資源分配目標是：在每一個調度周期內，在滿足各RS和MS功率約束限制的前提下，合理地進行子載波分配和功率分配，從而最大化系統上行鏈路吞吐量。該最優化問題可表述為

3 基于非合作博弈的資源分配算法

3.1 非合作博弈模型

由前文可知，系統中直傳MS和中繼MS的速率都等于它們各自所分配到的所有子信道速率之和，因此可以通過最大化各子信道速率來近似地實現系統整體吞吐量的最大化。另一方面，系統中的各MS或RS都只能根據自身獲得的一些相關信息，分布式地在各個子信道上進行功率分配。所以，在各同頻子信道上的功率分配可以用非合作博弈模型來描述。由于每一個調度周期中的2個子時隙的發送節點類型不同，因此需要分別對每一個子時隙進行建模。對于第1個子時隙，該非合作博弈模型可表示為

其中，{i}={1,2,…,I}表示各小區在相同子信道n上具有同頻干擾的 MS集合，為各MS在子信道 n上的發送功率策略集合，是各MS在子信道n上的凈效用函數。相似地，第2個子時隙中的各RS非合作博弈模型可表示為

對于GMS，令向量為博弈后所有MS在子信道n上的發送功率值，向量為除第i個MS發送功率之外的功率向量，因此第i個MS在子信道n上最終獲得的凈效用可表示為。在非合作博弈中，各MS為了最大化各自在其每一個子信道上的速率（即效用），必然使自己的發送功率達到最大值，因此系統最終的平衡點是一組由各個MS的最大發送功率值所組成的向量，然而該組向量中的各個值卻不是帕累托最優解。通過引入定價機制，在每個MS獲得發送功率的同時制定出所需要付出的代價，然后尋找出效用與代價之間的最佳平衡點，即可以使系統達到最優。

由于凈效用函數等于效用函數與定價函數之差，所以第i個MS在子信道n上的凈效用函數[12]可表示為

3.2 納什均衡點的存在性和唯一性

納什均衡是非合作博弈論的一個基本概念。根據定義，納什均衡是任何一個局中人單獨偏離它，其期望收益函數值不會因此變大。因此一旦所有局中人的混合策略組成了納什均衡，任何一個局中人都不會擅自偏離它。它是非合作博弈的“解”的合適定義。對于 GMS，納什均衡點是由同頻子信道 n上各個 MS的發射功率值組成的一個向量。在該點上，任何一個MS都不能在其他同頻子信道MS發射功率保持不變的情況下，通過單方面提升發射功率來增加自身的凈效用。即該向量（即納什均衡點）是功率分配的最終解。下面將證明關于 GMS的納什均衡點的存在性和唯一性。

由納什定理可知，在非合作博弈中，如果每個局中人的策略空間是歐氏空間上的一個非空的、閉的、有界的凸集，并且每個局中人的凈效用函數是連續且擬凹的函數，則該博弈必存在納什均衡。由于每個 MS的策略空間顯然MS的策略空間是歐氏空間RN上的一個非空的、閉的、有界的凸集。另外，凈效用函數對的二階偏導為

要證明GMS納什均衡點的唯一性，關鍵是證明其最優解表達式是標準函數，即滿足正性、單調性和可測量性。由定價因子的取值范圍可以保證功率求解表達式大于0，即滿足正性。關于單調性，由式(12)可知，由于某一 MS自身的發射功率與同一子信道的其他MS的干擾發射功率有關，故可令P=I(P)。設P≥P′，有：

則表達式為單減函數，當 P=P′時取等號。最后，要證明可測量性，即是要證明1θ?＞，θI(P)≥I(θP)。因為

所以表達式滿足可測量性。綜上可得，GMS具有唯一的納什均衡點。GRS納什均衡點的存在性和唯一性與GMS時的情況相似，可同理證明。

3.3 求解算法

對非合作博弈納什均衡點的求解，通常采用基于迭代的求解算法，從非均衡狀態逐步收斂到納什均衡點。對于 GMS，由式(12)可得同頻子信道 n上各MS功率的迭代表達式為

基于以上迭代表達式，本文給出多小區OFDMA中繼網絡上行鏈路中一種基于非合作博弈論的分布式資源分配算法，過程如下：

1) 在第 1個子時隙中，在各小區內，分別為中繼MS和直傳MS分配子信道（如round robin算法）；

5) 在第 2個子時隙中，在各小區內，為中繼MS分配子信道（如round robin算法）；

9) 對于直傳MS，利用第1子時隙的子信道分配結果和功率分配結果可計算出直傳MS最終的吞吐量；對于中繼MS，分別利用第1子時隙和第2子時隙的子信道分配結果和功率分配結果可計算出各子時隙的吞吐量，再取其中小者即為中繼 MS最終的吞吐量。

從以上對求解算法的描述可以看出，該求解算法的復雜度只與系統中的小區個數I、子載波個數N以及每個調度周期的子時隙個數有關，而與每個小區中MS的個數K無關。因此，在系統小區個數I、子載波個數N以及每個調度周期的子時隙個數確定的情況下，各小區中MS的接入和退出并不會影響到該算法的復雜度，因此使得該算法有很廣泛的適用場景。

4 仿真分析

為了對所提出的資源分配算法進行評價，本文用 MATLAB進行了算法實現，相關仿真參數設置如下：系統總帶寬為10MHz，可用子載波數為256個；系統包含19個小區，小區半徑為1 000m，每小區內有6個RS，RS與基站距離為500m，各RS最大可用發射功率為10W；各小區MS數量相同，小區內MS均勻分布，其中，1/4數量的MS為直傳MS,剩下3/4數量的MS為中繼MS，各MS最大可用發射功率為 1W；考慮信號的大尺度衰落和瑞利衰落，路徑損耗指數為 4，不考慮陰影效應；系統誤碼率（BER）為10-4，相應地Γ=5.067 3；AWGN信道噪聲功率密度為-200dBm/Hz；調度周期為1ms，均勻地分為2個子時隙。仿真時長為50 000個調度周期。仿真中采用的子信道分配算法為輪詢（round robin）算法，即在各小區中平均地為每個MS分配所有可用子載波。每小區MS數量為16、32、64。逐漸增大定價因子，觀察每個調度周期內，系統吞吐量和系統總發射功率的變化情況。

首先，從圖3～圖5可以看出，無論在任何場景下，隨著定價因子的增大，系統吞吐量均呈現先快速增長、后緩慢下降的趨勢。圖4～圖8則顯示系統總發射功率隨定價因子的增長而單調下降，下降的速度先急后緩。其原因是：當定價因子較小時，各節點在考慮自身所付出代價的情況下，使用比最大發射功率少一些的功率來進行發射，相應地互相之間的干擾功率也減小，由此使得系統吞吐量得到提升。當定價因子超過最優定價因子之后，定價因子的懲罰性大大加強，各節點的發射功率大大減小，使得吞吐量逐漸下降。

圖3 每小區16個MS時系統吞吐量

圖4 每小區32個MS時系統吞吐量

圖5 每小區64個MS時系統吞吐量

圖6 每小區16個MS時系統總發射功率

圖7 每小區32個MS時系統總發射功率

圖8 每小區64個MS時系統總發射功率

當定價因子為 0時，對應的系統吞吐量為各MS和 RS在各子載波上用最大等功率發射時獲得的系統吞吐量，此時系統總發射功率為最大。可以看出，隨著定價因子的增大，系統吞吐量相對于定價因子為0的情況下，最大可以提升5%左右，而此時系統總發射功率僅為最大等功率發射時的40%～50%左右。隨著定價因子的繼續增大，系統吞吐量將回落到定價因子為0時的水平，此時從圖6～圖8可以看出，系統總發射功率相對于最大等功率發射時減少了90%左右，大大減少了能量消耗，達到了較高的能效比。由于時間和篇幅的限制，仿真中的定價因子在各子時隙和各自信道上都是恒定不變的。如果能根據各子信道增益實際情況來動態地改變各子時隙和各子信道上的定價因子，不僅能使系統吞吐量得到更大的提升，而且也能使系統總發射功率減少的更多，從而達到更高的能效比，當然同時也會帶來更大的系統計算復雜度和控制開銷。

為了進一步說明本文提出的功率分配算法所帶來的系統性能增益，本文將等功率分配算法、經典的注水算法[7]與本文提出的功率分配算法進行了比較。等功率分配算法是不考慮信道增益，簡單地將節點自身功率平均地分配到自身獲得的所有子信道上，其復雜度最低。注水算法是根據自身獲得的子信道的不同增益，在信道增益較好的子信道上分配較多的功率，在信道增益較差的子信道上分配較少的功率，其復雜度稍高。圖9可以看到，盡管注水算法考慮了自身各子信道的信道增益，但是其性能仍然和使用等功率算法時基本相同，而本文提出的算法則較其他兩者能獲得4%左右的吞吐量增益。

圖9 3種功率分配算法的吞吐量比較

從圖 10顯而易見，使用本文提出的算法在較其他兩者在獲得更多系統吞吐量的同時，其系統總發射功率僅為其他兩者的 40%～50%左右，大幅降低了系統總發射功率。這里定義一個能效比因子，它的值等于系統吞吐量與總發射功率之比，單位為比特/焦耳。能效比因子越大，單位能量下產生的比特數就越多，系統則越節能。綜合圖9和圖10可以得出，采用等功率算法、注水算法時的能效比因子基本相同，分別為1.33×106（每小區16個MS）、0.66×106（每小區 32個 MS）和 0.33×106（每小區64個MS），而采用本文提出的算法時的能效比因子分別為3.00×106（每小區16個MS）、1.79×106（每小區 32個 MS）和 0.65×106（每小區 64個MS）。因此，本文提出的功率分配算法具有較高的能效比。

圖10 3種功率分配算法的系統總發射功率比較

5 結束語

博弈論作為一個新興的研究方法，已經日漸深入地應用到通信研究的各個領域之中，而本文即采用了其分支之一的非合作博弈論對 OFDMA無線多跳中繼網絡上行鏈路資源分配問題進行了研究。在建立兩跳系統優化模型的基礎上，通過引入非合作博弈論及定價機制來建立了相應的非合作功率分配博弈模型，同時納什均衡的存在性和唯一性也得到了證明，并且提出了具體的求解算法。仿真結果顯示本文所提出的算法既能有效地提升系統吞吐量，又能大幅降低系統總發射功率，達到了較高的能效比。

[1] PABST R. Relay-based deployment concepts for wireless and mobile broadband radio[J]. IEEE Communication Magazine, 2004, 42(9):80-89.

[2] SALEM. An overview of radio resource management in relay-enhanced OFDMA-based networks[J]. IEEE Communications Surveys & Tutorials, 2010, 12(3): 422-438.

[3] YOON J P, KIM W J , BAEK J Y, et al. Efficient uplink resource allocation for power saving in IEEE 802.16 OFDMA systems[A].2008 IEEE 67th Vehicular Technology Conference, VTC Spring 2008[C]. Singapore, 2008. 2167-2171.

[4] SADR S, ANPALAGAN A, RAAHEMIFAR K. Radio resource allocation algorithms for the downlink of multiuser OFDM communication systems[J]. IEEE Communications Surveys & Tutorials, 2009,11(3): 92-106.

[5] WONG I C, SHEN Z K, EVANS B L, et al. A low complexity algorithm for proportional resource allocation in OFDMA systems[A]. The IEEE 2004 Workshop on Signal Processing Systems, SIPS’04[C].Austin, Texas, USA, 2004. 1-6.

[6] SHEN Z K, ANDREWS J G, EVANS B L. Adaptive resource allocation in multiuser OFDM systems with proportional rate constraints[J]. IEEE Transactions on Wireless Communications, 2005, 4(6): 2726-2737.

[7] 張天魁, 曾志民, 張穎瑩. 基于博弈論的OFDMA系統多小區功率協調分配算法[J]. 通信學報, 2008, 29(1): 22-29.ZHANG T K，ZENG Z M, ZHANG Y Y. Multicell adaptive power allocation scheme based on game theory in OFDMA systems[J]. Journal on Communications, 2008, 29(1): 22-29.

[8] 仲崇顯, 李春國, 楊綠溪. 基于非合作博弈論的多小區OFDMA系統動態資源分配算法研究[J]. 電子與信息學報, 2009, 31(8):1935-1940.ZHONG C X, LI C G, YANG L X. Dynamic resource allocation algorithm for multi-cell OFDMA systems based on noncooperative game theory[J]. Journal of Electronics & Information Technology, 2009,31(8): 1935-1940.

[9] XINMIN Y, TONG W, JING H, et al. A non-cooperative game approach for distributed power allocation in multi-cell OFDMA-relay networks[A]. IEEE Vehicular Technology Conference, VTC Spring 2008[C]. Marina Bay, Singapore, 2008. 1920-1924.

[10] XIAO L, CUTHBERT L. Multi-cell non-cooperative power allocation game in relay based OFDMA systems[A]. IEEE Vehicular Technology Conference, VTC Spring 2009[C]. Barcelona, Spain, 2009. 1-5.

[11] XIAO L, ZHANG T K, CUTHBERT L. User fairness analysis of a game theory based power allocation scheme in OFDMA relay systems[A]. European Wireless Conference 2009, EW2009[C]. Aalborg,Denmark, 2009. 173-177.

[12] ZHANG T K, FENG C Y SU G, et al. Uplink multi-cell non-cooperative power allocation game algorithm for OFDMA cellular networks[A]. 5th International Conference on Wireless Communications, Networking and Mobile Computing, WiCom 2009[C]. Beijing,China, 2009.1-4.