潘科，左勇，劉學(xué)勇，陳杰

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

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

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

本文針對(duì)OFDM系統(tǒng)用戶(hù)上行GM問(wèn)題的特點(diǎn)，提出了一種新的用戶(hù)上行資源分配策略，通過(guò)分步求解數(shù)據(jù)包長(zhǎng)度和數(shù)據(jù)占用的子載波數(shù)的聯(lián)合優(yōu)化問(wèn)題，并提出了一種用戶(hù)上行有效吞吐量最大化算法，取得了較傳統(tǒng)算法更高的有效吞吐量.

1 OFDM系統(tǒng)上行鏈路模型

采用時(shí)分雙工的多用戶(hù)OFDM系統(tǒng)中，多個(gè)連續(xù)的OFDM符號(hào)組成一幀，一幀分為上行子幀和下行子幀，在一幀內(nèi)信道狀態(tài)假定是不變的.資源分配每一幀做一次，分為上行資源分配和下行資源分配.

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

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

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

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

圖1 OFDM系統(tǒng)上行鏈路模型Fig.1 The uplink model of the OFDM system

圖2 OFDM系統(tǒng)用戶(hù)上行時(shí)頻資源平面Fig.2 The user-uplink time-frequency resource plate of the OFDM system

2 用戶(hù)上行資源分配策略分析

OFDM系統(tǒng)的UUGM問(wèn)題有2個(gè)特點(diǎn):1)若給定用戶(hù)的發(fā)射功率，則每個(gè)子載波上的接收信噪比與用戶(hù)數(shù)據(jù)占用的子載波數(shù)成反比;2)數(shù)據(jù)包長(zhǎng)度，即數(shù)據(jù)包占用的資源數(shù)，與數(shù)據(jù)包占用的OFDM符號(hào)數(shù)成正比.

傳統(tǒng)包長(zhǎng)優(yōu)化算法［8-10］中有效吞吐量表達(dá)式為

式中:z為數(shù)據(jù)包的長(zhǎng)度，ps為數(shù)據(jù)包成功傳輸?shù)母怕?，r是在給定的某調(diào)制方式下每個(gè)子載波上承載的比特?cái)?shù)，h為數(shù)據(jù)包的信令消耗.由于式(1)中只有一個(gè)變量，沒(méi)有體現(xiàn)OFDM系統(tǒng)中UUGM問(wèn)題的特點(diǎn)，所以傳統(tǒng)包長(zhǎng)優(yōu)化算法不能很好地適用于該問(wèn)題.

Devillers等［5］給出的有效吞吐量表式為波數(shù)集合為V={ni|i=1，2，…，NP}，成功傳輸?shù)母怕始蠟閃={Pri|i=1，2，…，NP}，則 OFDM 系統(tǒng)的用戶(hù)上行有效吞吐量可表示為

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

本文針對(duì)OFDM系統(tǒng)UUGM問(wèn)題的特點(diǎn)，提出了一種新的用戶(hù)上行資源分配策略.該策略通過(guò)優(yōu)化配置數(shù)據(jù)包占用的子載波數(shù)、OFDM符號(hào)數(shù)和子載波分段數(shù)，可使得有效吞吐量最大化.

假設(shè)數(shù)據(jù)包在用戶(hù)時(shí)頻資源平面上占用的資源塊為矩形;ni、mi分別為數(shù)據(jù)包i占用的子載波數(shù)和OFDM符號(hào)數(shù);Pri為數(shù)據(jù)包i成功傳輸?shù)母怕?，它受?shù)據(jù)包i的長(zhǎng)度和每個(gè)子載波上的接收信噪比影響;NP為數(shù)據(jù)包總數(shù).設(shè)各數(shù)據(jù)包占用的OFDM符號(hào)數(shù)集合為U={mi|i=1，2，…，NP}，占用的子載

由文獻(xiàn)［5］可知，使同一數(shù)據(jù)包各子載波上的誤碼率相等是一種接近最優(yōu)的功率分配方式，因此本文的功率分配采用該方式.又因?yàn)榧俣ㄓ脩?hù)帶寬小于信道相干帶寬，用戶(hù)每個(gè)子載波上的信道增益近似相等，所以同一數(shù)據(jù)包每個(gè)子載波上的發(fā)射功率近似相等，數(shù)據(jù)包i的誤碼率BERi可表示為［12］

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

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

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

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

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

3 用戶(hù)上行有效吞吐量最大化算法

3.1 UUGM問(wèn)題及其分解

3.1.1 原始問(wèn)題

由表示有效吞吐量的式(6)可知，數(shù)據(jù)包占用的子載波數(shù)n越大，傳輸?shù)臄?shù)據(jù)量越大，但每個(gè)子載波上的信噪比越低;數(shù)據(jù)包的OFDM符號(hào)數(shù)m越大，信令消耗占數(shù)據(jù)總量的比例越小，但數(shù)據(jù)包成功傳輸?shù)母怕试降?子載波分段數(shù)t越多，傳輸?shù)臄?shù)據(jù)包越多，但數(shù)據(jù)包成功傳輸?shù)母怕试降?因此，要使得有效吞吐量最大，就必須優(yōu)化配置m、n、t.

新策略下的UUGM問(wèn)題可表示為

該問(wèn)題屬于非線(xiàn)性整數(shù)混合規(guī)劃問(wèn)題，枚舉法可求得最優(yōu)解，它的復(fù)雜度為

3.1.2 原始問(wèn)題的分解

為得到一種低復(fù)雜度的算法，將復(fù)雜的原始問(wèn)題分解成2個(gè)較簡(jiǎn)單的子問(wèn)題，即用戶(hù)有效資源分配問(wèn)題和數(shù)據(jù)包參數(shù)設(shè)置問(wèn)題.

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

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

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

3.2 用戶(hù)有效資源分配問(wèn)題分析

單調(diào)性特征描述了函數(shù)在定義域不同區(qū)間上的單調(diào)性，它包括單調(diào)遞增、單調(diào)遞減、單峰、單谷和先峰后谷.單峰是指函數(shù)有且只有一個(gè)極大值點(diǎn);單谷是指函數(shù)有且只有一個(gè)極小值點(diǎn);先峰后谷是指函數(shù)有且只有2個(gè)極值點(diǎn)，其中一個(gè)為極大值點(diǎn)，另一個(gè)為極小值，而且極大值點(diǎn)的x軸坐標(biāo)小于極小值點(diǎn)的x軸坐標(biāo).

3.2.1 目標(biāo)函數(shù)單調(diào)性特征分析

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

當(dāng)x給定時(shí)，要使得f2(x，l)最大，l的最優(yōu)解可以表示為［8］

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

證明 設(shè)l1(x)=Mx，其定義域?yàn)?h/(rM)，+∞)，l1(x)在定義域上單調(diào)遞增，可得

設(shè)l2(x)=L(x)，當(dāng)x∈(h/(rM)，+∞)時(shí)l2(x)單調(diào)遞減，可得

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

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

式中:

引理1 當(dāng)x∈(h/(rM)，+∞)時(shí)，g1(x)是x的單峰函數(shù).

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

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

由于y'(x)連續(xù)，所以存在h/(rM)＜＜+∞，使得y')=0.對(duì)y(x)求二階導(dǎo)可知y″(x)＜0，即y'(x)單調(diào)下降.所以，當(dāng)h/(rM)＜x＜+∞時(shí)，y'(x)有且只有一個(gè)零點(diǎn)，y(x)有且只有一個(gè)駐點(diǎn)，等價(jià)于g1(x)有且只有一個(gè)駐點(diǎn).又因?yàn)間1(x)連續(xù)，有

所以，當(dāng)x∈(h/(rM)，+∞)時(shí)，g1(x)有且只有一個(gè)最大點(diǎn)，是x的單峰函數(shù)，命題得證.

引理2g2(x)和'(x)的單調(diào)性特征與λ無(wú)關(guān).

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

因?yàn)閷?duì)于任意x1必然存在x2=x1/α，使得

所以g2(x，λ =λ1)與g2(x，λ =λ2)一一對(duì)應(yīng)，極值點(diǎn)個(gè)數(shù)相同.因?yàn)棣粒?，所以g2(x，λ=λ1)與g2(x，λ=λ2)的單調(diào)性特征相同.又因?yàn)?λ1和 λ2是任意取值，所以g2(x)的單調(diào)性特征與λ無(wú)關(guān)，λ的變化只是對(duì)g2(x)函數(shù)曲線(xiàn)的壓縮或拉伸.

引理3 當(dāng)h=1，2，…，2 048且x∈(0，+∞)時(shí)，g2(x)有且只有一個(gè)極大值點(diǎn)和一個(gè)極小值點(diǎn).如果令極大值點(diǎn)和極小值點(diǎn)的x軸坐標(biāo)分別為x1和x2，那么x1＜x2.

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

引理3中h是每個(gè)數(shù)據(jù)包的信令消耗量，實(shí)際系統(tǒng)中該消耗量為常數(shù)，這里假設(shè)該常數(shù)的取值范圍為從1到2 048的整數(shù).

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

定理2 當(dāng)h=1，2，…，2 048且x∈(h/(rM)，+∞)時(shí)，g(x)是先峰后谷函數(shù)或者單峰函數(shù)或者單調(diào)增函數(shù).

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

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

表1中有2種情況并未討論.因?yàn)長(zhǎng)(x)為l(x)的最佳取值，所以當(dāng)x∈(h/(rM)，+∞)時(shí)，g2(x)≥g1(x).假設(shè)g1(x)＞g1(x*);假設(shè)時(shí)，，得到矛盾，因此，的情況不會(huì)出現(xiàn).同理可證，的情況也不會(huì)出現(xiàn).

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

3.2.2 L 搜索算法

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

單調(diào)函數(shù)和單谷函數(shù)的最大值一定都在定義域區(qū)間的端點(diǎn)處，只需比較端點(diǎn)處的函數(shù)值即可.因?yàn)閤∈Z+，所以運(yùn)用二分法就可以準(zhǔn)確搜索得到單峰函數(shù)的極大值點(diǎn)坐標(biāo).然而，由于先峰后谷函數(shù)的定義域中存在兩段單調(diào)上升的區(qū)間，通過(guò)斜率值的符號(hào)無(wú)法判斷二分點(diǎn)的x軸坐標(biāo)是否大于極大值點(diǎn)的x軸坐標(biāo)，所以先峰后谷函數(shù)的極大值點(diǎn)坐標(biāo)無(wú)法直接運(yùn)用經(jīng)典的二分法得到.

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

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

3.3 數(shù)據(jù)包參數(shù)設(shè)置問(wèn)題分析

由式(11)可知，數(shù)據(jù)包參數(shù)設(shè)置問(wèn)題為整數(shù)非線(xiàn)性混合規(guī)劃問(wèn)題，如果用枚舉法逐一搜索3個(gè)變量，其復(fù)雜度為O(MN·lnN).為了降低復(fù)雜度，提出了一種次優(yōu)的M搜索算法，該算法只搜索每包OFDM符號(hào)數(shù)這一個(gè)變量，其復(fù)雜度為O(M).

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

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

表2 數(shù)據(jù)包類(lèi)型參數(shù)Table 2 Parameters of data packet

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

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

3.4 UUGM算法及其復(fù)雜度分析

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

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

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

表3 算法復(fù)雜度比較Table 3 Computational complexity of algorithms

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

4 仿真結(jié)果分析

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

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

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

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

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

5 結(jié)束語(yǔ)

提出的用戶(hù)上行有效性吞吐量最大化算法UUGM，以少量提升計(jì)算復(fù)雜度為代價(jià)，較傳統(tǒng)算法明顯地提高了有效吞吐量.本文對(duì)信道近似平坦的假設(shè)是基于單個(gè)用戶(hù)的上行帶寬較窄情況，而頻率選擇性信道下的有效吞吐量?jī)?yōu)化問(wèn)題將有待進(jìn)一步研究.

［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.