崔建明， 王昕， 巢志俊

(1. 復(fù)旦大學(xué) 信息科學(xué)與工程學(xué)院， 上海 200433; 2. 上海華為技術(shù)有限公司， 上海 200135)

一種新穎的LTE-A上行頻域資源調(diào)度算法

崔建明1， 王昕1， 巢志俊2

(1. 復(fù)旦大學(xué) 信息科學(xué)與工程學(xué)院， 上海 200433; 2. 上海華為技術(shù)有限公司， 上海 200135)

LTE-A上行多址接入技術(shù)采用的clustered DFT-s-OFDMA方式允許用戶獲得頻域資源上最多兩段不連續(xù)的資源塊(Resource Block, RB)；該項(xiàng)技術(shù)增加了資源分配的靈活性，同時(shí)也增加了資源分配的難度。特別是，在前述松弛的連續(xù)性限制條件下，上行資源調(diào)度還需要進(jìn)一步考慮LTE-A協(xié)議對(duì)RB分配附加的其它約束，包括離散傅里葉變換(Discrete Fourier Transform, DFT)實(shí)現(xiàn)帶來(lái)的質(zhì)因數(shù)分解限制和下行控制信息(Downlink Control Information, DCI)格式限制帶來(lái)的RBG(RB Group)粒度限制。針對(duì)這些難點(diǎn)，設(shè)計(jì)了一種基于兩輪分配的新穎的LTE-A上行資源調(diào)度算法——選址擴(kuò)張算法。該算法有極低的計(jì)算時(shí)間復(fù)雜度，同時(shí)在性能和最優(yōu)算法給出的上界差距很小，比其他一些現(xiàn)有的典型調(diào)度算法在性能和/或計(jì)算時(shí)間復(fù)雜度上有明顯的優(yōu)勢(shì)，很適用于實(shí)際LTE-A系統(tǒng)。

LTE-A； 上行； 資源分配； NP-hard； 次優(yōu)算法； 低復(fù)雜度

0 引言

隨著移動(dòng)互聯(lián)的發(fā)展，人們對(duì)移動(dòng)數(shù)據(jù)的需求越來(lái)越大。根據(jù)現(xiàn)有的統(tǒng)計(jì)，自2012年以來(lái)，全球的移動(dòng)數(shù)據(jù)流量的年復(fù)合增長(zhǎng)率達(dá)到了66%；而預(yù)計(jì)在2017年，全球每個(gè)月的移動(dòng)數(shù)據(jù)流量將會(huì)超過(guò)10×260字節(jié)[1]。為了滿足用戶對(duì)移動(dòng)數(shù)據(jù)的需求，3GPP也在積極推進(jìn)現(xiàn)有移動(dòng)互聯(lián)網(wǎng)的演進(jìn)。目前，LTE網(wǎng)絡(luò)已經(jīng)全面商用，并且正向LTE-A網(wǎng)絡(luò)演進(jìn)。作為L(zhǎng)TE的演進(jìn)網(wǎng)絡(luò)，LTE-A起到了承前啟后的作為，同時(shí)也在逐步商用，幫助全球度過(guò)LTE到5G的過(guò)渡階段。為了提高網(wǎng)絡(luò)吞吐能力，多點(diǎn)協(xié)作、載波聚合等技術(shù)在LTE-A中被運(yùn)用。在上行多址接入技術(shù)方面，更靈活的clustered DFT-s-OFDMA取代了LTE的集中映射式的DFT-s-OFDMA，打破了用戶只能獲取頻域上一段連續(xù)資源塊(RB)的限制，允許用戶在上行資源分配過(guò)程中可以獲得多段不連續(xù)的RB，增加了調(diào)度靈活性；而好的上行資源調(diào)度算法可以充分發(fā)揮出新的多址接入技術(shù)帶來(lái)的增益。

圖1 Clustered DFT-s-OFMA的RB映射關(guān)系圖

在實(shí)際的LTE-A上行鏈路中，為了減少傳輸控制信息所需的比特?cái)?shù)從而與LTE中的下行控制信息(Downlink Control Information, DCI)格式兼容，協(xié)議規(guī)定在每個(gè)TTI(Transmit Time Interval)內(nèi)，每個(gè)用戶最多可以獲得兩段不連續(xù)的頻域資源，且當(dāng)一個(gè)用戶獲得兩段不連續(xù)的頻域資源時(shí)，每一段頻域資源必須以RBG(RB Group)為粒度[2](RBG由頻域上若干個(gè)RB組成)；而當(dāng)用戶僅獲得一段連續(xù)的頻域資源時(shí)，其分配粒度是RB(按協(xié)議規(guī)定一個(gè)RB包含12個(gè)連續(xù)子載波，持續(xù)時(shí)間長(zhǎng)度為1ms[3]；因?yàn)楸疚木劢乖谧虞d波資源分配，所以忽略RB在時(shí)間上的定義)。同時(shí)考慮到離散傅里葉變換(Discrete Fourier Transform, DFT)應(yīng)用的復(fù)雜度問(wèn)題，DFT變換矩陣大小須以2,3,5作為基數(shù)[4]，所以協(xié)議規(guī)定每個(gè)用戶獲得的RB數(shù)目必須滿足NRB=2a·3b·5c，其中a,b,c為非負(fù)整數(shù)[4]。

作為L(zhǎng)TE-A上行資源調(diào)度的子問(wèn)題，LTE上行資源調(diào)度問(wèn)題被廣泛研究：文獻(xiàn)[5]提出利用分支定界算法獲得LTE上行資源分配問(wèn)題的最優(yōu)解，但是最優(yōu)算法計(jì)算復(fù)雜度極高。文獻(xiàn)[6]-[7]針對(duì)相鄰限制條件約束的LTE上行資源調(diào)度問(wèn)題，提出了3種近似算法。文獻(xiàn)[8]證明了在僅考慮相鄰限制條件下，LTE上行鏈路分配問(wèn)題為NP-hard問(wèn)題，同時(shí)給出了4個(gè)次優(yōu)的貪婪算法。對(duì)于LTE-A上行資源調(diào)度問(wèn)題也有少量研究：文獻(xiàn)[9]中作者根據(jù)文獻(xiàn)[6]的收益倍增思想，提出了適用于LTE-A上行資源調(diào)度問(wèn)題的收益倍增算法。文獻(xiàn)[10]中作者利用拉格朗日對(duì)偶法對(duì)LTE-A上行資源調(diào)度問(wèn)題進(jìn)行求解，然而該算法復(fù)雜度較高，且對(duì)效益函數(shù)的凸性有嚴(yán)格要求。事實(shí)上，上述工作均沒(méi)有考慮協(xié)議對(duì)于上行資源調(diào)度問(wèn)題的具體約束。為此，本文考慮了上述所有限制條件，提出了一種基于兩輪分配的新穎的調(diào)度算法——選址擴(kuò)張算法，通過(guò)先進(jìn)行粗顆粒分配再進(jìn)行細(xì)顆粒分配的方式，為算法提供了對(duì)抗信道突變的魯棒性，同時(shí)保證了調(diào)度的靈活性，保證了良好的仿真性能。此外，本文提出的選址擴(kuò)張算法還具有極低的計(jì)算時(shí)間復(fù)雜度，很適用于實(shí)際系統(tǒng)。

2 系統(tǒng)模型

考慮采用clustered DFT-s-OFMDA的LTE-A非協(xié)作多小區(qū)上行網(wǎng)絡(luò)，假設(shè)每個(gè)小區(qū)內(nèi)共有K個(gè)單天線用戶，標(biāo)識(shí)為集合Ψ={1,…,k,…,K}，傳輸帶寬B被正交地劃分為M個(gè)RB，標(biāo)識(shí)為集合Ω={1,…,m,…,M}。假設(shè)基站端采用MMSE接收機(jī)且配有兩根天線，基站n中用戶k在子載波j上的信干噪比SINR可以表示為式(1)。

(1)

其中R(RB(j))表示子載波j所在RB上的各個(gè)子載波平均干擾協(xié)方差矩陣，hk,j,n表示信道增益，pk,j,n表示用戶k在子載波j上的發(fā)送功率。根據(jù)協(xié)議規(guī)定[11]，用戶采用平均分配策略進(jìn)行功率分配pk,j=pk,i,?i,j，總發(fā)送功率Pk采用開環(huán)控制，由式(2)決定，

Pk=min{Pmax-MPR,P0+αPL+10log10Nk}

(2)

其中Pmax表示最大發(fā)送功率，PL表示傳播路徑損耗，P0表示開環(huán)發(fā)射功率，α表示路徑損耗補(bǔ)償系數(shù)，Nk表示用戶k所獲得的RB數(shù)。MPR (Maximum Power Reduction)表示最大功率回退，其設(shè)計(jì)初衷是為了抑制多個(gè)cluster(不連續(xù)的RB)傳輸產(chǎn)生的交調(diào)乘積(Inter-Modulation Products, IMP)。協(xié)議規(guī)定[11]，對(duì)于多個(gè)cluster在單個(gè)CC (Component Carrier)同時(shí)傳輸?shù)那闆r，最大輸出功率允許的MPR表示如式(3)。

MPR=CEIL{MA,0.5}

(3)

根據(jù)MMSE接收機(jī)的性質(zhì)，用戶k在調(diào)度帶寬上整體的SINR可以表示為式(4)[12]。

(4)

Mk代表用戶k獲得的子載波數(shù)。

3 LTE-A上行資源調(diào)度問(wèn)題

我們假定基站已知本小區(qū)用戶所有信道狀態(tài)信息(Channel State Information, CSI)。定義分配給用戶k的RB集合為ak，則用戶k的容量可以表示為式(5)。

(5)

s.t.

(6)

式(6)中的第一個(gè)限制條件表示排他性限制，即每個(gè)RB最多只能被一個(gè)用戶占用；而A表示所有可行方案ak的集合。針對(duì)LTE-A上行鏈路，考慮LTE-A協(xié)議對(duì)于上行資源調(diào)度的約束，ak需要滿足以下限制條件：

1) 松弛的相鄰性限制：ak最多包含兩段不連續(xù)的RB，每段中的所有RB必須是相鄰的；

2) 質(zhì)因數(shù)分解限制：ak所包含的RB數(shù)的質(zhì)因數(shù)分解必須是{2,3,5}的子集，即Nak=2a·3b·5c，Nak表示ak所含RB數(shù)，a,b,c為非負(fù)整數(shù)；

3) RBG粒度限制：對(duì)于包含兩段不連續(xù)RB的ak，其每段RB必須以RBG為粒度。假設(shè)RBG大小為P，則第i個(gè)RBG所包含的RB編號(hào)為(i-1)P+1～min(iP,M)。

原有LTE上行資源調(diào)度問(wèn)題和式(6)相比，限制條件有所變化：沒(méi)有限制條件3)，同時(shí)限制條件1)變成僅允許包含一段連續(xù)的RB，因此其可看成是式(6)的子問(wèn)題。LTE上行資源調(diào)度問(wèn)題已經(jīng)被證明是NP-hard問(wèn)題[8]，因此式(6)同樣也是NP-hard問(wèn)題，無(wú)法在多項(xiàng)式時(shí)間內(nèi)計(jì)算得到該問(wèn)題的最優(yōu)解。對(duì)此，本文提出了一種新穎的基于兩輪分配的選址擴(kuò)張算法；該算法能以極低的計(jì)算時(shí)間復(fù)雜度獲得近似最優(yōu)的LTE-A上行資源調(diào)度方案。

選址擴(kuò)張算法分為3個(gè)階段：選址、擴(kuò)張和調(diào)整。在選址階段，算法利用粗顆粒的chunk(若干個(gè)連續(xù)RB)作為最小調(diào)度單位，可以充分利用信道的相關(guān)性，提高算法對(duì)抗信道突變的魯棒性，在擴(kuò)張階段，算法在選址階段的基礎(chǔ)上利用小顆粒的RB作為調(diào)度單元，從而保證調(diào)度的靈活性。由于式(6)中的限制條件2)和3)使得該問(wèn)題很難解決，所以在前兩個(gè)階段暫時(shí)不考慮這兩個(gè)限制條件。在完成這兩個(gè)階段后，通過(guò)調(diào)整階段使得最后分配結(jié)果滿足限制條件2)和3)。以下是算法的具體步驟：

步驟1：初始化階段：基站獲得所有用戶最新的信道狀態(tài)和其余小區(qū)4個(gè)TTI前的分配結(jié)果(對(duì)于多小區(qū)的非協(xié)作調(diào)度，基站利用其他小區(qū)4個(gè)TTI前的分配結(jié)果作為干擾進(jìn)行考慮)，同時(shí)調(diào)用前期資源分配得到的用戶平均傳輸速率R={R1,…,Rk,…,RK}用來(lái)后續(xù)計(jì)算加權(quán)速率。

步驟2：選址(Nesting)階段：基站按照RBG大小將所有RB劃分為資源大塊chunk，作為該階段分配的最小單元?；久看螐乃锌尚械腸hunk-用戶對(duì)中選取加權(quán)速率增益最大的chunk-用戶對(duì)進(jìn)行分配，同時(shí)更新該用戶在其余備選chunk的加權(quán)速率增益以及各個(gè)用戶的可行chunk集。重復(fù)分配過(guò)程直至沒(méi)有可行的chunk或最大加權(quán)速率增益小于等于0。具體為：

假設(shè)RBG大小P，第i個(gè)chunk(記為Ci)包含編號(hào)為i到min(i+P,M)的RB。與RBG不同，相鄰若干個(gè)chunk之間會(huì)有重疊。計(jì)算所有用戶在各個(gè)chunk上的加權(quán)速率w，并存儲(chǔ)在O(M)×K矩陣Vc內(nèi)。

更新各個(gè)用戶在各自備選chunk上的加權(quán)速率增益為式(7)。

(7)

對(duì)于非備選chunk上的加權(quán)速率增益，置0，即為式(8)。

(8)

步驟3：擴(kuò)張(Expanding)階段：該階段分配以RB為粒度進(jìn)行?；靖鶕?jù)Ωk更新各個(gè)用戶的備選RB，每次從所有備選的RB-用戶對(duì)中選取加權(quán)速率增益最大的RB-用戶對(duì)進(jìn)行分配，同時(shí)更新該用戶的備選RB集合以及在備選RB上的加權(quán)速率增益。重復(fù)步驟3的分配過(guò)程直至沒(méi)有可行的RB或總加權(quán)速率不再增加。

(9)

在非備選的RB上，用戶加權(quán)速率增益置0：為式(10)。

(10)

步驟4：調(diào)整階段：由于前兩個(gè)階段沒(méi)有考慮質(zhì)因數(shù)分解限制和RBG粒度限制，所以該階段需要對(duì)Ωk, ?k進(jìn)行調(diào)整，以保證所有Ωk均符合限制條件1)～3)以及排他性限制條件?；静捎靡环N貪婪的調(diào)整策略進(jìn)行調(diào)整，調(diào)整策略如下：

基站根據(jù)Ωk為所有用戶進(jìn)行優(yōu)先級(jí)排序，2-cluster(包含兩段不連續(xù)RB)的Ωk優(yōu)先級(jí)高于1-cluster(只包含一段連續(xù)RB)的優(yōu)先級(jí)；而針對(duì)擁有相同cluster數(shù)的Ωk，RB數(shù)量多的優(yōu)先級(jí)高于RB數(shù)量少的優(yōu)先級(jí)。調(diào)整次序按照優(yōu)先級(jí)大小來(lái)進(jìn)行，某個(gè)用戶調(diào)整一旦完成，其分配結(jié)果就被固定，即優(yōu)先級(jí)小的用戶調(diào)整過(guò)程中不能改變優(yōu)先級(jí)高的用戶方案。調(diào)整過(guò)程當(dāng)中，盡可能的保證RB的變動(dòng)最小化，以達(dá)到最小化性能損失的目的。

最小化RB變化數(shù)通過(guò)以下方式實(shí)現(xiàn)，對(duì)于2-cluster的方案，由于RBG的位置是固定的，所以可以通過(guò)方案中每段的最大和最小的RB編號(hào)來(lái)確定應(yīng)該調(diào)整的位置。而對(duì)于1-cluster的方案，可以通過(guò)該方案所包含的RB數(shù)和與該RB數(shù)相差最小可行方案RB數(shù)比較，來(lái)確定可行的調(diào)整方向和策略(向左添加RB或者向右添加RB或者左端刪除RB或者右端刪除RB)。如果存在多種可選的情況，則對(duì)比多種調(diào)整情況帶來(lái)的性能損失，挑選性能損失最小的作為最終調(diào)整方式。例如Ωk有7個(gè)RB，則可以通過(guò)共4種方案將其擴(kuò)成8個(gè)RB或者縮減成6個(gè)RB，以滿足質(zhì)因數(shù)分解限制，最終方案的確定只需要比較這4種方案帶來(lái)的性能損失即可。由于用戶的方案調(diào)整可能會(huì)對(duì)其相鄰用戶方案產(chǎn)生影響，所以每完成一個(gè)用戶方案的調(diào)整，需要更新剩余未調(diào)整用戶的分配結(jié)果。

總體算法如下表所示：

算法：選址擴(kuò)張算法

1: Initialize: 初始化用戶集Ψ{1,…,k,…,K}，RB集Ω{1,…,m,…,M}和RBG 大小P; 獲取各用戶的長(zhǎng)期平均速率R={R1,…,Rk,…,RK}和CSI;初始化各用戶所獲得的RB集Ωk=?,?k;

2: Nesting: 初始化總的chunk集C{Ci|1≤i≤M-P+1}，其中Ci={RBi,…,RBmin{i+P,M}}; 初始化各用戶備選chunk集,?k并計(jì)算chunk-用戶對(duì)加權(quán)速率矩陣Vc;

3: Repeat:

4:ws,k=max{Vc};

5: ifws,k<0

6: break;

7:Ωk=Ωk+Cs;

9: Repeat:

10:Δs,k=max{VRB};

11: ifΔs,k<0

12: break;

13:Ωk=Ωk+RBs;

16: 設(shè)置調(diào)整優(yōu)先級(jí)并調(diào)整Ωk;

17:Output:{Ωk,?k}

算法復(fù)雜度分析：選址擴(kuò)張算法的總體計(jì)算時(shí)間復(fù)雜度為O(M(K+M))。由于算法的復(fù)雜度主要來(lái)源于對(duì)加權(quán)速率的計(jì)算，因此本文利用對(duì)加權(quán)速率計(jì)算的次數(shù)來(lái)衡量計(jì)算時(shí)間復(fù)雜度。選址階段的計(jì)算時(shí)間復(fù)雜度是O(M(K+M))：計(jì)算chunk-用戶對(duì)加權(quán)速率矩陣Vc計(jì)算時(shí)間復(fù)雜度是O(MK)。在分配chunk的過(guò)程中，根據(jù)(7)每次最多需要更新其中一行的加權(quán)速率值，每次更新的復(fù)雜度為O(M)，循環(huán)次數(shù)為O(M)，所以選址階段的計(jì)算時(shí)間復(fù)雜度為O(MK)+O(M2)=O(M(M+K))。擴(kuò)張階段的計(jì)算時(shí)間復(fù)雜度是O(MK)：在最壞情況下(大多數(shù)用戶在第一輪沒(méi)有獲得RB)計(jì)算加權(quán)速率矩陣VRB的計(jì)算時(shí)間復(fù)雜度為O(MK)。而在循環(huán)過(guò)程中，由于該階段只能在相鄰的RB附近進(jìn)行擴(kuò)張，所以每次只需要更新O(1)的加權(quán)速率值，循環(huán)持續(xù)O(K)，所以擴(kuò)張階段計(jì)算時(shí)間復(fù)雜度為O(MK)。調(diào)整階段的計(jì)算時(shí)間復(fù)雜度為O(MK)：對(duì)于未調(diào)整的Ωk，只有存在多個(gè)備選替換方案時(shí)才需要計(jì)算加權(quán)速率。對(duì)于2-cluster的Ωk，由于RBG位置固定的特性，備選方案可以通過(guò)Ωk中的2個(gè)cluster位置唯一確定。對(duì)于1-cluster的Ωk，由于只需要通過(guò)簡(jiǎn)單的調(diào)整使得把Ωk內(nèi)的RB數(shù)往其最相鄰的符合質(zhì)因數(shù)限制的數(shù)字上靠，備選方案不會(huì)超過(guò)O(M)，所以該階段在最壞情況下需要O(MK)的計(jì)算時(shí)間復(fù)雜度。因此算法整體的計(jì)算時(shí)間復(fù)雜度為O(M(K+M))。

4 仿真結(jié)果

仿真環(huán)境描述如下：LTE-A上行帶寬設(shè)置為10 MHz，RB數(shù)目為50個(gè)，載波頻率2 GHz。小區(qū)拓?fù)浒?7個(gè)3扇區(qū)站點(diǎn)，站點(diǎn)間距500米。每個(gè)扇區(qū)活躍用戶數(shù)為6人，用戶均勻分布，且移動(dòng)速度為3 km/h。小區(qū)路徑損耗補(bǔ)償系數(shù)和開環(huán)發(fā)射功率設(shè)置為[α,P0]=[0.8,-95 dBm]，大尺度路徑損耗模型為PL=128.1+37.6×log10(x)，x單位為km；陰影衰落服從對(duì)數(shù)正態(tài)分布，標(biāo)準(zhǔn)差為8 dB；信號(hào)穿透損耗20 dB。同時(shí)，我們假定噪聲功率譜密度為-174 dBm/Hz，仿真采用20徑典型城市信道模型。

本節(jié)從用戶速率的經(jīng)驗(yàn)分布函數(shù)(empirical CDF)、小區(qū)吞吐量和歸一化的CPU時(shí)間等方面，將選址擴(kuò)張算法和LTE-A下的基于分支定界思想的最優(yōu)算法、局部比(Local Ratio)算法、收益倍增(Double Benefit)算法和經(jīng)典的輪叫(Round Robin)算法進(jìn)行比較。值得一提的是，由于算法特性，LTE中的最優(yōu)算法、局部比算法和收益倍增算法可以直接應(yīng)用于在協(xié)議約束下的LTE-A上行資源調(diào)度問(wèn)題，其計(jì)算時(shí)間復(fù)雜度，如表1所示。

表1 算法數(shù)據(jù)比較

從CDF曲線可以看出，如圖2所示。

圖2 用戶速率的經(jīng)驗(yàn)CDF曲線

選址擴(kuò)張算法和最優(yōu)算法相比性能差距很小，從表1可以發(fā)現(xiàn)，二者的小區(qū)平均吞吐量性能僅相差大約8%。而從算法的計(jì)算時(shí)間復(fù)雜度和歸一化CPU時(shí)間來(lái)看，選址擴(kuò)張算法要遠(yuǎn)優(yōu)于最優(yōu)算法(例如，前者所需CPU時(shí)間僅為后者的0.6%)。同時(shí)，和近似比為3的局部比算法相比，選址擴(kuò)張算法的性能略優(yōu)于局部比算法，而CPU時(shí)間和計(jì)算復(fù)雜度上要8倍低于局部比算法。同收益倍增算法相比，本文提出的算法在系統(tǒng)性能和計(jì)算復(fù)雜度上均要優(yōu)于收益倍增算法，性能增益約為20%，且所需CPU時(shí)間節(jié)省約7倍。同輪叫算法相比，雖然所提出的算法計(jì)算時(shí)間復(fù)雜度大于輪叫算法，但是選址擴(kuò)張算法在系統(tǒng)性能上要遠(yuǎn)遠(yuǎn)優(yōu)于輪叫算法，小區(qū)吞吐量增益超過(guò)130%。所以本文提出的選址擴(kuò)張算法在仿真性能和計(jì)算復(fù)雜度上均有很優(yōu)秀的表現(xiàn)，考慮到其僅有平方量級(jí)的計(jì)算復(fù)雜度以及和最優(yōu)算法之間極小的性能差距，選址擴(kuò)張算法很適用于實(shí)際LTE-A系統(tǒng)。

5 總結(jié)

在考慮LTE-A協(xié)議約束的情況下，本文設(shè)計(jì)了一種基于兩輪分配的新穎的LTE-A上行資源調(diào)度算法——選址擴(kuò)張算法。該算法只有平方量級(jí)的計(jì)算時(shí)間復(fù)雜度，遠(yuǎn)小于最優(yōu)算法，同時(shí)在算法性能和最優(yōu)算法給出的上界差距很小，比其他一些現(xiàn)有的典型調(diào)度算法在性能和/或計(jì)算時(shí)間復(fù)雜度上有明顯的優(yōu)勢(shì)，很適用于實(shí)際LTE-A系統(tǒng)。

[1] Index CVN. Cisco visual networking index: global mobile data traffic forecast update, 2014-2019[R]. Tech. Rep., 2015.

[2] 3rd Generation Partnership Project (3GPP) Technical Specification Group Radio Access network; Evolved Universal Terrestrial Radio Access (E-UTRA); Physical layer procedures(Release 11)[S]. 3GPP TS 36.213, V11.11.0, Jun. 2015.

[3] 3rd Generation Partnership Project (3GPP) Technical Specification Group Radio Access network; Evolved Universal Terrestrial Radio Access (E-UTRA); Physical channels and modulation (Release 11)[S]. 3GPP TS 36.211, V11.6.0, Sept. 2014.

[4] Ericsson. DFT size for uplink transmissions[C]. 3GPP TSG RAN WG1 Meeting 46, Seoul, R1-062859, 2006,10.

[5] Wong I C, Oteri O, Mccoy W. Optimal resource allocation in uplink SC-FDMA systems[J]. IEEE Transactions on Wireless Communications, 2009, 8(5):2161-2165.

[6] Ren F, Xu Y, Yang H, et al. Frequency Domain Packet Scheduling with Stability Analysis for 3GPP LTE Uplink[J]. IEEE Transactions on Mobile Computing, 2013, 12(12):2412 - 2426.

[7] Andrews M, Zhang L. Multiserver scheduling with contiguity constraints[C].INFOCOM 2009, IEEE. IEEE, 2009: 1278-1286.

[8] Lee S, Pefkianakis I, Meyerson A, et al. Proportional Fair Frequency-Domain Packet Scheduling for 3GPP LTE Uplink[C].INFOCOM 2009, IEEE. IEEE, 2009:2611-2615.

[9] Prasad N, Zhang H, Jiang M, et al. Resource Allocation in 4G MIMO Cellular Uplink[C].Global Telecommunications Conference (GLOBECOM 2011), 2011 IEEE. IEEE, 2011:1-5.

[10] Balasubramanya N M, Lampe L. Near-optimal resource block and power allocation mechanisms in uplink for LTE and LTE-Advanced[C].GLOBECOM Workshops. IEEE, 2014:1014-1019.

[11] 3rd Generation Partnership Project (3GPP) Technical Specification Group Radio Access network; Evolved Universal Terrestrial Radio Access (E-UTRA); User Equipment (UE) radio transmission and reception (Release 10)[S], 3GPP TS 36.101, V10.21.0., Jan. 2016.

[12] Assaad M, Ben-Ameur W, Hamid F. Resource optimization of non-additive utility functions in localized SC-FDMA systems[J]. IEEE Transactions on Signal Processing, 2014, 62(18): 4896-4910.

A Novel Resource Allocation Algorithm for the LTE-A Uplink

Cui Jianming1, Wang Xin1, Chao Zhijun2

(1. Department of Communication Science and Engineering, Fudan university, Shanghai 200433, China;2. Shanghai Huawei Technology Co., Ltd. Shanghai 200135, China)

In this paper, we address the resource allocation problem for the clustered DFT-s-OFDM A based LTE-A uplink,where each user can be allocated up to two nonconsecutive clusters of resource blocks (RBs). To accommodate the flexibility brought by the clustered DFT-s-OFDM, LTE-A standard imposes additional constraints on the RB allocation, such as the discrete-Fourier-transform implementation constraint, andmultiple granularity constraint. These considerations make the relevant resource allocation problem very difficult to be tackled. To this end, an efficient resource allocation algorithm called “nesting and expanding” is proposed. Simulation results show that the proposed low-complexity algorithm can achieve a near-optimal performance, and significantly outperform the existing alternatives.

LTE-auplink; Resource allocation; NP-hard; Suboptimal algorithm; Low-complexity

崔建明(1991-)，碩士研究生，研究方向：無(wú)線通信。 王 昕(1971-)，教授，研究方向：無(wú)線通信，信號(hào)處理。 巢志俊(1973-)，工程師，研究方向：無(wú)線通信。

1007-757X(2017)08-0057-04

TP311

A

2017.04.12)