OFDM系統用戶上行有效吞吐量最大化算法

潘科，左勇，劉學勇，陳杰

(中國科學院微電子研究所通信與多媒體SoC研究室，北京100029)

近年來，為了提高頻譜利用效率，正交頻分(orthogonal frequency division multiple，OFDM)通信系統中的子載波和功率自適應分配問題得到了廣泛研究.根據優化目標的不同，該研究方向主要包括兩類問題:裕量自適應(margin adaptation，MA)問題和速率自適應(rate adaptation，RA)問題.MA問題主要是研究在用戶固定傳輸速率和誤碼率約束條件下，最小化發射總功率;RA問題主要是研究在系統發射總功率約束條件下，最大化系統吞吐量.除了發射總功率的約束，RA問題又按照其余不同的約束條件，主要分為3類:1)在誤碼率約束下，速率最大化(rate maximization，RM)［1-2］;2)在速率約束下，誤碼率最小化(BER minimization，BM)［3-4］;3)有效吞吐量最大化(goodput maximization，GM)，有效吞吐量是指接收端在單位時間內正確接收到的數據量.其中前兩類問題，主要是針對語音和視頻傳輸等實時性業務，有固定的誤碼率要求或速率要求.第3類問題與前兩者不同，它主要針對文件傳輸和網頁瀏覽等非實時性業務.這類業務往往既沒有固定的誤碼率要求，又沒有固定的速率要求，但要求接收的數據完全正確.在發送端，上層的數據被打包傳輸;接收端對數據包進行循環冗余校驗(cyclical redundance checking，CRC)，只要數據包中有錯誤比特，整個數據包就被丟棄，因此有效吞吐量是此類業務最重要的性能參數.

以往對資源分配的研究集中于MA、RM和BM問題，對于GM問題的研究多限于解決一個OFDM符號上的子載波分配問題，而對時間和頻率資源，即OFDM符號和子載波，同時進行分配的研究很少.Devillers等［5］研究了基于GM的功率和子載波分配問題，得出子載波等誤碼率的功率分配方式是一種接近最優的功率分配方式的結論，但所提出的算法只適用于一個OFDM符號上的子載波分配.Stupia等［6-7］雖然把GM問題的研究擴展到了多輸入多輸出(multiple input multiple output，MIMO)系統，但提出的算法仍然沒有考慮二維的時頻資源.另一方面，文獻［8-10］雖然研究了基于GM的包長優化問題，但沒有結合OFDM系統用戶上行GM的特點.

本文針對OFDM系統用戶上行GM問題的特點，提出了一種新的用戶上行資源分配策略，通過分步求解數據包長度和數據占用的子載波數的聯合優化問題，并提出了一種用戶上行有效吞吐量最大化算法，取得了較傳統算法更高的有效吞吐量.

1 OFDM系統上行鏈路模型

采用時分雙工的多用戶OFDM系統中，多個連續的OFDM符號組成一幀，一幀分為上行子幀和下行子幀，在一幀內信道狀態假定是不變的.資源分配每一幀做一次，分為上行資源分配和下行資源分配.

上行鏈路的資源分配過程分為兩個方面.以802.16d系統［11］為例，一方面，基站端在下行子幀開始之前，以用戶為單位進行多用戶間的系統資源分配，用戶資源分配信息在下行子幀中傳輸給用戶端.另一方面，單個用戶端在收到資源分配信息后，得知基站為其分配的上行資源，在上行子幀開始之前為其各種業務進行資源分配，本文將此種資源分配稱為用戶上行資源分配(user-uplink resource allocation，UURA).

本文不考慮基站端多用戶間的系統資源分配問題，只研究單個用戶端的UURA問題，問題的目標是使用戶上行有效吞吐量最大化(user-uplink GM，UUGM).

假設用戶分得的子載波數為N，帶寬小于信道相干帶寬，該用戶各子載波的信道增益近似相等;分得的OFDM符號數為M;在用戶端，精確的信道狀態信息已知.OFDM系統的上行鏈路模型如圖1所示，其中用戶端的選擇性自動重傳(selective repeat-ARQ，SR-ARQ)模塊處理基站端校驗數據包后反饋的確認(ACK)或重傳(NACK)請求，實現數據包的重傳.系統子載波總數為Nsys.系統可使用 QPSK、16QAM和64QAM這3種調制方式.

OFDM系統中用戶上行時頻資源平面如圖2所示.用戶可用的資源包括N個子載波和M個OFDM符號，資源的基本單位為資源槽(slot，它由一個子載波和一個OFDM符號組成.若一個數據包占用n個子載波和m個OFDM符號，則占用mn個slot.

圖1 OFDM系統上行鏈路模型Fig.1 The uplink model of the OFDM system

圖2 OFDM系統用戶上行時頻資源平面Fig.2 The user-uplink time-frequency resource plate of the OFDM system

2 用戶上行資源分配策略分析

OFDM系統的UUGM問題有2個特點:1)若給定用戶的發射功率，則每個子載波上的接收信噪比與用戶數據占用的子載波數成反比;2)數據包長度，即數據包占用的資源數，與數據包占用的OFDM符號數成正比.

傳統包長優化算法［8-10］中有效吞吐量表達式為

式中:z為數據包的長度，ps為數據包成功傳輸的概率，r是在給定的某調制方式下每個子載波上承載的比特數，h為數據包的信令消耗.由于式(1)中只有一個變量，沒有體現OFDM系統中UUGM問題的特點，所以傳統包長優化算法不能很好地適用于該問題.

Devillers等［5］給出的有效吞吐量表式為波數集合為V={ni|i=1，2，…，NP}，成功傳輸的概率集合為W={Pri|i=1，2，…，NP}，則 OFDM 系統的用戶上行有效吞吐量可表示為

式中:bk表示子載波k上的比特數，B={bk|k=1，2，…，N}，P為各子載波上的功率組成的集合.式(2)雖然通過控制子載波上的比特數和功率可以控制用戶數據占用的子載波數，但子載波分段數和OFDM符號數都被限定為1，從而限制了有效吞吐量的最大化.

本文針對OFDM系統UUGM問題的特點，提出了一種新的用戶上行資源分配策略.該策略通過優化配置數據包占用的子載波數、OFDM符號數和子載波分段數，可使得有效吞吐量最大化.

假設數據包在用戶時頻資源平面上占用的資源塊為矩形;ni、mi分別為數據包i占用的子載波數和OFDM符號數;Pri為數據包i成功傳輸的概率，它受數據包i的長度和每個子載波上的接收信噪比影響;NP為數據包總數.設各數據包占用的OFDM符號數集合為U={mi|i=1，2，…，NP}，占用的子載

由文獻［5］可知，使同一數據包各子載波上的誤碼率相等是一種接近最優的功率分配方式，因此本文的功率分配采用該方式.又因為假定用戶帶寬小于信道相干帶寬，用戶每個子載波上的信道增益近似相等，所以同一數據包每個子載波上的發射功率近似相等，數據包i的誤碼率BERi可表示為［12］

式中:B為系統帶寬，N0為零均值高斯白噪聲的單邊功率譜密度，g為每個子載波的信道增益，pi和SNRi分別為數據包i的發射功率和接收信噪比，c1=0.5，c2=1.5，Pri表示為

為便于分析，假設所有數據包占用的子載波數相同，OFDM符號數相同，即mi=mj=m，ni=nj=n，i=j，m和n分別為數據包OFDM符號數和子載波數;所有數據包的發射功率相同，即Pi=P/t，P為用戶的發射總功率，在上行鏈路方向，用戶的發射功率是資源分配的一個關鍵約束條件，t為子載波分段數.如果用戶時頻資源平面的頻率軸方向上排列著t個數據包，那么子載波分段數為t.

將m、n、t以及式(4)、(5)代入式(3)得到新策略下有效吞吐量的表達式為

式中:M/m表示OFDM符號分段數w，說明用戶時頻資源平面的時間軸方向上排列著w個數據包.可知，用戶分得的M個OFDM符號在新策略中將全部被用于數據傳輸.

將式(6)與式(1)、(2)比較可知，新策略全面地考慮了OFDM系統UUGM問題的2個特點，每個子載波上的接收信噪比與用戶數據占用的子載波數nt成反比，而數據包的包長是m與n的乘積，它不但與n有關，還與m有關.

3 用戶上行有效吞吐量最大化算法

3.1 UUGM問題及其分解

3.1.1 原始問題

由表示有效吞吐量的式(6)可知，數據包占用的子載波數n越大，傳輸的數據量越大，但每個子載波上的信噪比越低;數據包的OFDM符號數m越大，信令消耗占數據總量的比例越小，但數據包成功傳輸的概率越低;子載波分段數t越多，傳輸的數據包越多，但數據包成功傳輸的概率越低.因此，要使得有效吞吐量最大，就必須優化配置m、n、t.

新策略下的UUGM問題可表示為

該問題屬于非線性整數混合規劃問題，枚舉法可求得最優解，它的復雜度為

3.1.2 原始問題的分解

為得到一種低復雜度的算法，將復雜的原始問題分解成2個較簡單的子問題，即用戶有效資源分配問題和數據包參數設置問題.

用戶有效資源分配問題，主要研究如何合理設置用戶有效資源參數，使得用戶上行有效吞吐量最大化.由式(7)和(8)可知，n和t相互獨立，要求nt≤N，所以用戶分得的N個子載波可能只有部分被用于數據傳輸，即用戶分得的資源并不都是有效的，只有用于傳輸用戶數據的部分才是有效的，剩余的部分是無效的.用戶有效資源的參數包括數據包的包長l和用戶數據占用的子載波數x，其中l=mn，x=nt.將l和x代入式(7)，變量的個數將從3個減少到2個，得到用戶有效資源分配問題的表達式:

式(10)說明用戶數據占用的子載波數必須小于用戶可用的子載波數，要使得有效吞吐量為正值，包長必須大于信令消耗占用的資源量，而且必須不大于用戶數據占用的總資源量.

數據包參數設置問題，主要研究如何合理設置數據包的參數，使得實際的有效吞吐量盡量接近用戶有效吞吐量最大值.如果得到了x和l的最優解，那么只要找到m，n，t∈Z+使得l=mn，x=nt成立，則m、n和t就是原始問題的最優解.但是，這樣的m、n和t很難找到，所以g(x，l)的最大值是g(m，n，t)最大值的上界，這里希望后者能盡量接近前者.又因為g(x，l)是x和l的連續函數，所以這里希望mn與l的差距和nt與x的差距都盡量小，從而使得g(m，n，t)與g(x，l)的差距盡量小.于是，數據包參數設置問題的表達式:

3.2 用戶有效資源分配問題分析

單調性特征描述了函數在定義域不同區間上的單調性，它包括單調遞增、單調遞減、單峰、單谷和先峰后谷.單峰是指函數有且只有一個極大值點;單谷是指函數有且只有一個極小值點;先峰后谷是指函數有且只有2個極值點，其中一個為極大值點，另一個為極小值，而且極大值點的x軸坐標小于極小值點的x軸坐標.

3.2.1 目標函數單調性特征分析

為便于分析，這里放寬x、l為整數的約束條件，令x，l∈R+，并把g(x，l)分為兩部分:

當x給定時，要使得f2(x，l)最大，l的最優解可以表示為［8］

定理1 存在唯一的x*∈(h/(rM)，+∞)，使得下式成立:

證明 設l1(x)=Mx，其定義域為(h/(rM)，+∞)，l1(x)在定義域上單調遞增，可得

設l2(x)=L(x)，當x∈(h/(rM)，+∞)時l2(x)單調遞減，可得

所以l1(h/(rM))-l2(h/(rM))＜0，l1(+∞)-l2(+∞)＞0，且l1(x)和l2(x)都為連續函數，故必然存在的x*∈(h/(rM)，+∞)使得l1(x*)=l2(x*).由l1(x)和l2(x)單調性可知x*唯一，而且由約束式(12)可知，當x＜x*時，l2(x)＞l1(x)，l(x)=l1(x);當x＜x*時，l1(x)＞l2(x)，l(x)=l2(x).因此命題得證.

由定理1可知，l(x)是(h/(rM)，+∞)上的分段函數，因而f2(x，l)和g(x，l)也是x的分段函數.把式(15)代入g(x，l)得

式中:

引理1 當x∈(h/(rM)，+∞)時，g1(x)是x的單峰函數.

證明 將式(12)和(17)代入式(16)可得

由于g1(x)＞0，所以g1(x)和lng1(x)的單調性相同.令y(x)=lng1(x)，對y(x)求導可知:

由于y'(x)連續，所以存在h/(rM)＜＜+∞，使得y')=0.對y(x)求二階導可知y″(x)＜0，即y'(x)單調下降.所以，當h/(rM)＜x＜+∞時，y'(x)有且只有一個零點，y(x)有且只有一個駐點，等價于g1(x)有且只有一個駐點.又因為g1(x)連續，有

所以，當x∈(h/(rM)，+∞)時，g1(x)有且只有一個最大點，是x的單峰函數，命題得證.

引理2g2(x)和'(x)的單調性特征與λ無關.

證明 令 λ 分別等于 λ1和 λ2，其中 λ1=αλ2，且 α∈R+，α ≠1，令

因為對于任意x1必然存在x2=x1/α，使得

所以g2(x，λ =λ1)與g2(x，λ =λ2)一一對應，極值點個數相同.因為α＞0，所以g2(x，λ=λ1)與g2(x，λ=λ2)的單調性特征相同.又因為 λ1和 λ2是任意取值，所以g2(x)的單調性特征與λ無關，λ的變化只是對g2(x)函數曲線的壓縮或拉伸.

引理3 當h=1，2，…，2 048且x∈(0，+∞)時，g2(x)有且只有一個極大值點和一個極小值點.如果令極大值點和極小值點的x軸坐標分別為x1和x2，那么x1＜x2.

證明 根據式(16)可知，g2(x)的單調性特征只與參數λ和h有關，而引理2已證明g2(x)的單調性特征與λ無關.所以當h=1，2，…，2 048，即為有限的離散值時，假定λ為常數，將h逐一代入g2(x)檢驗命題的真假.因為g2'(+∞)=d，d是大于0的常數，所以在x較大時g2(x)單調遞增，在檢驗時x不必取到無窮.所有檢驗結果均表明了g2(x)在(0，+∞)上有且只有一個極大值點和一個極小值點，且x1＜x2.因此，命題得證，g2(x)是先峰后谷函數.

引理3中h是每個數據包的信令消耗量，實際系統中該消耗量為常數，這里假設該常數的取值范圍為從1到2 048的整數.

g(x)是由g1(x)和g2(x)組成的兩段函數，它的單調性特征由下面的定理2可知.

定理2 當h=1，2，…，2 048且x∈(h/(rM)，+∞)時，g(x)是先峰后谷函數或者單峰函數或者單調增函數.

證明 設g1(x)的極大值點、g2(x)的極大值點和極小值點以及g(x)的分段點的x軸坐標分別為、x1、x2、x*.由定理1可知x*＞h/(rM)，由引理1可知＞h/(rM).因為g(x)是由g1(x)和g2(x)所組成的分段函數，g1(x)和g2(x)的單調性特征已知，所以g(x)的單調特征容易得到.g(x)的單調性特征如表1所示，表中a和b分別代表當x＜x*和x＞x*時g(x)的單調性特征.

表1 g(x)的分段單調性特征Table 1 The sectional monotonicity of function g(x)

表1中有2種情況并未討論.因為L(x)為l(x)的最佳取值，所以當x∈(h/(rM)，+∞)時，g2(x)≥g1(x).假設g1(x)＞g1(x*);假設時，，得到矛盾，因此，的情況不會出現.同理可證，的情況也不會出現.

由表 1易得:當h=1，2，…，2 048且當x∈(h/(rM)，+∞)時，g(x)只能是先峰后谷函數或者單峰函數或者單調增函數.因此，命題得證.

3.2.2 L 搜索算法

定理2中，x定義域為(h/(rM)，+∞)，而考慮式(10)，則x的 定 義 域 為 ［max(1，ceil(h/(rM)))，N］，ceil(x)表示不小于x的最小整數.因而，式(9)中g(x)的單調性特征是定理2中g(x)部分定義域區間上的單調性特征.因此g(x)在式(9)定義域上的單調性特征有以下5種可能:單調遞增、單調遞減、單峰、單谷和先峰后谷.

單調函數和單谷函數的最大值一定都在定義域區間的端點處，只需比較端點處的函數值即可.因為x∈Z+，所以運用二分法就可以準確搜索得到單峰函數的極大值點坐標.然而，由于先峰后谷函數的定義域中存在兩段單調上升的區間，通過斜率值的符號無法判斷二分點的x軸坐標是否大于極大值點的x軸坐標，所以先峰后谷函數的極大值點坐標無法直接運用經典的二分法得到.

定理3 當h=40，41，…，2 048時，設x1和x2分別為g2(x)的極大值點和極小值點的x軸坐標，那么'(x)是單谷函數，且存在唯一的極小值點，其x軸坐標為，使得

圖3 L搜索算法流程Fig.3 The flow chart of L search algorithm

3.3 數據包參數設置問題分析

由式(11)可知，數據包參數設置問題為整數非線性混合規劃問題，如果用枚舉法逐一搜索3個變量，其復雜度為O(MN·lnN).為了降低復雜度，提出了一種次優的M搜索算法，該算法只搜索每包OFDM符號數這一個變量，其復雜度為O(M).

一方面，為了使(x-nt)2最小，本文放寬了對t為整數的約束，使t取實數.其中對于任意整數x和n，t=x/n;當t為非整數時，t=ti+tf，ti為t的整數部分，tf為t的分數部分.x個子載波被相應地分為兩部分:1)nti個子載波，2)剩下的(x-nti)個子載波，打包時兩部分將分別處理.

另一方面，由于t=x/n，式(11)等價于min|lmn|.為了使|l-mn|最小，逐一搜索m，對應的n由l/m四舍五入得到.因為l/m=n≤max(n)=x，所以m的搜索范圍是l/x≤m≤M.如果m是M的因子，在同等條件下將被優先選擇.當w=M/m非整數時，w=wi+wf，wi為w的整數部分，wf為w的分數部分.M個OFDM符號被相應地分為兩部分:1)mwi個OFDM符號，2)剩下的(M-mwi)個OFDM符號，打包時兩部分將分別處理.因為子載波與OFDM符號都分別被分為了兩部分，所以組合起來有4種類型的數據包，如表2所示.如果出現包長小于h/r的情況，則不給該類型的包填充數據.

表2 數據包類型參數Table 2 Parameters of data packet

M算法的流程如圖4所示.其中，m|M表示m整除M，rd(x)表示對x四舍五入，mopt、nopt、topt分別是算法得到的數據包的OFDM符號數、子載波數及子載波分段數.

圖4 M搜索算法流程Fig.4 The flow chart of the M search algorithm

3.4 UUGM算法及其復雜度分析

結合L和M搜索算法，本節提出了一種用戶上行有效吞吐量最大化算法UUGM.該算法的流程如圖5所示，其中，J表示調制方式的種類數，j表示第j種調制方式，gmax表示最大有效吞吐量.由3.2節可知，L搜索算法的復雜度與二分法的復雜度相同，為O(lnN)，由3.3節可知M搜索算法的復雜度為O(M).UUGM算法先調用L搜索算法，再調用M搜索算法，所以它的復雜度為O(lnN+M).

圖5UUGM算法流程Fig.5 The flow chart of the UUGM algorithm

已有算法(如傳統策略下的包長優化算法(GB_CLASSIC)［8］、M_OFDM_TDMA 算法［5-7］和 OFDMTDMA非優化算法)的復雜度如表3所示.其中，GB_CLASSIC算法的每個數據包占用的子載波數固定為N，OFDM符號數可由解析表達式求得，復雜度為O(1).M_OFDM_TDMA算法是文獻［5-7］的算法在用戶帶寬小于相干情況下的等效算法，每個數據包占用的OFDM符號數固定為1，子載波數為自適應控制變量，復雜度為O(lnN).OFDM-TDMA非優化算法中，每個數據包占用的子載波數為N，符號數為1.

表3 算法復雜度比較Table 3 Computational complexity of algorithms

從表3可見，GB_CLASSIC和OFDM_TDMA算法復雜度最低，但從后面的仿真結果得到，它們的有效吞吐量也是最低的.而UUGM算法的復雜度雖然略高于M_OFDM_TDMA算法(M通常遠小于N)，但遠低于枚舉法.

4 仿真結果分析

通過仿真將UUGM算法的性能與枚舉法和已有的基于GM的算法進行了比較.仿真系統參數為Nsys=1 024，N=128，M=20，h=64，用戶帶寬小于相干帶寬，信道增益服從瑞利分布.用戶的有效吞吐量值為傳輸1 000幀后得到的平均值.

UUGM算法與枚舉法的有效吞吐量如圖6所示.可見，UUGM算法的有效吞吐量接近于枚舉法(EX).圖7為UUGM算法與已有算法的有效吞吐量比較.

圖6 UUGM算法和枚舉法的有效吞吐量Fig.6 The goodput of the UUGM algorithm and the enumeration method

圖7 4種算法下的用戶有效吞吐量Fig.7 The user goodput of 4 algorithms

由圖7可見，4種算法當中，OFDM-TDMA算法由于未進行任何優化，有效吞吐量最低.GB_CLASSIC算法雖然復雜度較低，但有效吞吐量較低.M_OFDM_TDMA算法與UUGM算法復雜度相當，有效吞吐量相對較低.相比之下，新策略下UUGM算法的有效吞吐量明顯高于其他3種算法.例如當平均信噪比為0 dB時，UUGM算法的有效吞吐量為278.1 bit/幀，而其余3種算法中最大的有效吞吐量為97.19 bit/幀，前者比后者高出了186%;當平均信噪比15 dB時，UUGM算法的有效吞吐量比其余3種算法中的最大有效吞吐量高出了5%.

5 結束語

提出的用戶上行有效性吞吐量最大化算法UUGM，以少量提升計算復雜度為代價，較傳統算法明顯地提高了有效吞吐量.本文對信道近似平坦的假設是基于單個用戶的上行帶寬較窄情況，而頻率選擇性信道下的有效吞吐量優化問題將有待進一步研究.

［1］BASHAR S，DING Z.Admission control and resource allocation in a heterogeneous OFDMA wireless network［J］.IEEE Trans on Wireless Communications，2009，8(8):4200-4210.

［2］KO H，OH S，KIM B，et al.Simple bit allocation algorithms with BER-constraint for OFDM-based systems［C］//WCNC09.Budapest，Hungary，2009:1-5.

［3］ERMOLOVA N Y，MAKAREVITCH B.Low complexity adaptive power and subcarrier allocation for OFDMA［J］.IEEE Trans on Wireless Communications，2007，6(2):433-437.

［4］ERMOLOVA N Y，MAKAREVITCH B.Performance of practical subcarrier allocation schemes for OFDMA［C］//PIMRC07.Hilten Athens，Greece，2007:1-4.

［5］DEVILLERS B，LOUVEAUX J，VANDENDORPE L.Bit and power allocation for goodput optimization in coded parallel subchannels with ARQ［J］.IEEE Trans on Signal Processing，2008，56(8):3652-3661.

［6］STUPIA I，VANDENDORPE L，LOUVEAUX J，et al.Power allocation for goodput optimization in BICM-OFDM systems［C］//ICC08.Beijing ，China，2008:3604-3608.

［7］STUPIA I，GIANNETTI F，LOTTICI V，et al.BICMBOFDM link resource adaptation［C］//ICC09.Dresden，Germany，2009:1-5.

［8］MODIANO E.An adaptive algorithm for optimizing the packet size used in wireless ARQ protocols［J］.Wireless Networks，1999(5):279-286.

［9］CICCARESE G，BLASI M D，MARRA P，et al.A packet size control algorithm for IEEE 802.16e［C］//WCNC08.Las Vegas，USA，2008:1420-1425.

［10］ZHANG Y，SHU F.Packet size optimization for goodput and energy efficiency enhancement in slotted IEEE 802.15.4 networks［C］//WCNC09.Budapest，Hungary，2009:1-6.

［11］IEEE.IEEE Std 802.16d，IEEE standard for local and metropolitan area networks—part 16:air interface for fixed broadband wireless access systems［S］.Hoboken:IEEE，2004.

［12］GOLDSMITH A J，CHUA S.Variable-rate variable-power MQAM for fading channels［J］.IEEE Trans on Communications，1997，45(10):1218-1230.