基于拍賣算法的TD－LTE系統(tǒng)上行資源分配算法

劉 凱，丁 璐，趙建業(yè)，劉志敏

（北京大學(xué)信息科學(xué)技術(shù)學(xué)院，北京100871）

基于拍賣算法的TD－LTE系統(tǒng)上行資源分配算法

劉 凱，丁 璐，趙建業(yè)，劉志敏

（北京大學(xué)信息科學(xué)技術(shù)學(xué)院，北京100871）

在LTE上行系統(tǒng)中，用戶設(shè)備必須在連續(xù)的子載波上發(fā)送數(shù)據(jù)，而且易受到鄰扇區(qū)同頻干擾，有效的資源分配是提高系統(tǒng)性能的關(guān)鍵。對上行資源分配相關(guān)文獻進行分析綜述，提出一種基于拍賣的TD－LTE上行系統(tǒng)單扇區(qū)及多扇區(qū)資源分配算法，并進行了TD－LTE系統(tǒng)級平臺仿真驗證。仿真結(jié)果表明，與傳統(tǒng)方法相比，提出的方法可以更為有效地提高系統(tǒng)頻譜效率和邊緣用戶頻譜效率，提升了用戶QoS。

資源分配；長期演進無線通信系統(tǒng)；上行；拍賣算法；頻譜效率

0 引言

3GPP移動通信長期演進（LTE）項目是面向第四代移動通信的技術(shù)標準，其演進版本為LTEAdvanced，以正交頻分多址（OFDM）和多輸入多輸出（MIMO）為技術(shù)基礎(chǔ)，在網(wǎng)絡(luò)結(jié)構(gòu)、空中接口協(xié)議和傳輸技術(shù)上較第三代移動通信系統(tǒng)（3G）有較高的性能提升［1］。資源分配是LTE的關(guān)鍵技術(shù)之一，可以有效地提高多用戶系統(tǒng)性能［2］，TD－LTE是LTE的時分雙工制式。

對于多載波系統(tǒng)的資源分配，文獻［3，4］給出了基于拉格朗日松弛的優(yōu)化算法，可以在多用戶頻率選擇性信道中提高系統(tǒng)吞吐率。然而，LTE上行采用單載波頻分多址（SC－FDMA），用戶設(shè)備（UE）必須使用連續(xù)的子載波［5］。文獻［6］考慮了多用戶資源塊（RB）的連續(xù)分配問題，并提出了兩種啟發(fā)式算法。文獻［7］根據(jù)UE在載波上的平均增益，提出了一種平均值增強的貪婪算法。而上述文獻主要針對單扇區(qū)缺少多扇區(qū)上行系統(tǒng)干擾模型。文獻［8］提出了在多用戶MIMO條件下的調(diào)度方法，主要考察了多用戶在MIMO上的分配協(xié)調(diào)。文獻［9］在宏基站和家庭式基站組成的異構(gòu)網(wǎng)絡(luò)中，提出了跨層干擾控制與資源分配結(jié)合的策略，需要依賴對信道質(zhì)量的準確估計，在TDD系統(tǒng)中延遲問題會大大影響該方法的效果。文獻［10］將LTE上行資源分配問題建模成一個集合劃分問題，但該文是在扇區(qū)間進行干擾消除的基礎(chǔ)上進行資源分配的，也沒有考慮其他扇區(qū)對本扇區(qū)帶來的干擾。

1 系統(tǒng)和信號模型

1.1 系統(tǒng)模型

考慮一個包含7個六邊形小區(qū)的LTE上行系統(tǒng)。每個小區(qū)分為3個扇區(qū)，位于小區(qū)中心的eNodeB采用方向性天線對小區(qū)各個扇區(qū)進行覆蓋；每個扇區(qū)都占用整個系統(tǒng)帶寬B，含有N個均勻分布的UE，如圖1所示。

圖1 扇區(qū)和UE模型

系統(tǒng)中，總帶寬B共包含K個子載波，其中每12個子載波組成一個資源塊（RB）。如上所述，LTE上行系統(tǒng)規(guī)定每個UE必須使用連續(xù)的RB，因此，為了使資源分配建模更為簡潔明了，將若干個連續(xù)RB組成一個RB簇，做為資源分配單元［11］。系統(tǒng)中的所有RB會被分成相等大小的若干個RB簇，RB簇的數(shù)目與UE數(shù)目相同，每個RB簇所包含的RB數(shù)目為系統(tǒng)總RB數(shù)目除以UE數(shù)目得到的商，每個UE可以并且僅可以分配到其中的一個RB簇。這種方法充分利用了UE在相鄰RB之間信道狀況變化較小的特點，保證了UE分配到RB的連續(xù)性，并且具有實現(xiàn)簡單的特點。

1.2 信號模型

根據(jù)香農(nóng)公式，可以將LTE上行第i個扇區(qū)的吞吐量Ri表示為：

式中，Bkij為扇區(qū)i的第j個UE在RB簇k上的帶寬；ηkij是一個取值為0或1的指示變量：如果扇區(qū)i的第j個UE占用RB簇k，ηkij就為1，否則為0；SNRiejfkf為扇區(qū)i的第j個UE在RB簇k上的等效信噪比（SNR），可以由RB簇內(nèi)包含的所有子載波的信干噪比（SINR）經(jīng)過指數(shù)有效SIR映射（EESM）算法計算得到［10］：

式中，γkijl為扇區(qū)i的第j個UE在RB簇k的第l個子載波kl上的信干噪比SINR，Nk為RB簇k含有的子載波數(shù)目，β值與MCS等級相關(guān)。γkijl的計算方法為：

2 單扇區(qū)資源分配

2.1 數(shù)學(xué)問題描述

首先僅針對目標扇區(qū)進行分析，即在式（4）中，認為扇區(qū)干擾的構(gòu)成量和均為本扇區(qū)eNodeB已知的量。因此，扇區(qū)中的每個UE在不同RB簇上的對于eNodeB都是已知量。文中資源分配的目標是提高扇區(qū)吞吐量，即扇區(qū)內(nèi)所有用戶可以傳輸?shù)目偙忍財?shù)。因此，第i個扇區(qū)的資源分配問題可以表示為：

2.2 基于拍賣的單扇區(qū)資源分配算法

拍賣算法最早由D.P.Bertsekas提出，通過模仿現(xiàn)實中的拍賣過程，可以有效地解決一對一分配問題［14］。假設(shè)有N個人和N個物品，并且第j個人得到第k個物品可以獲得的增益為vkj，一對一分配問題的目標就是把人和物品匹配起來，從而使所有人獲得的總增益最大。拍賣算法可以用低復(fù)雜度的方法來解決這一問題。它模擬了一個競爭投標的過程，在這個過程中，沒有得到分配的人會不斷提高他們的叫價，為這些物品競標，物品會分配給叫價最高的人。在這里假設(shè)一個正值ε（稱為補松弛）和物品的價格向量{pk，k=1，…N}，對第j個人而言，如果分配到物kj后可以獲得的利潤（好處減去出價）與所有分配方案中能得到的最優(yōu)利潤之差的絕對值不大于ε，即滿足補松弛條件，那么這個人就是滿意的。拍賣算法通過迭代的方法，不斷地將物品分配給人，直到每個人都滿意。

根據(jù)一對一分配問題的建模方法，可以將上行資源分配問題抽象為：系統(tǒng)中有N個UE和N個RB簇，并且第j個UE在第k個RB簇上可以獲得的增益為vkj，資源分配的目標就是把UE和RB簇匹配起來，使所有UE獲得的總增益最大。其中增益參數(shù)vkj設(shè)為：該UE在該RB簇上的SNRjekff對應(yīng)的MCS等級下可傳輸?shù)谋忍財?shù)，即對應(yīng)式（5）中的f（SNRiejfk

f）。還需要注意的是，LTE上行系統(tǒng)采用非自適應(yīng)重傳［13］，即傳輸失敗的用戶使用與前一次傳輸相同的資源和MCS等級進行重傳。因此在LTE系統(tǒng)中實現(xiàn)拍賣算法時，需要首先剔除這部分已經(jīng)得到分配的重傳UE和對應(yīng)的RB簇，再在剩余的沒有分配的新傳UE和RB簇中通過拍賣算法得到最優(yōu)解。應(yīng)用考慮重傳的拍賣算法解決單扇區(qū)資源分配問題的具體過程描述如下：

第1步：初始化。

①選定一個ε＞0；

②認為所有N個UE都不滿意；

③設(shè)pk=0，k=1，…N。

第2步：針對非自適應(yīng)重傳UE的處理。

對于每個重傳UE jre，把該UE在用于其上次傳輸?shù)腞B簇kjre上對應(yīng)的增益參數(shù)vjrekjre設(shè)為一個極大值，并把該UE在其他RB簇k≠kjre上的增益參數(shù)vjrek設(shè)為0，使重傳用戶jre在拍賣算法的迭代中會一直選擇kjre為最優(yōu)的傳輸RB簇。

迭代過程：

①選擇一個不滿意的UE j，計算他可以獲得的最大利潤γjkj和得到最大利潤時分配到的RB簇kj：

以及他的第二大的利潤δjk^j和得到第二大利潤時分配到的RB簇^kj：

②把第kj個RB簇分給第j個UE。如果這個RB簇在之前已經(jīng)被分配給另一個UE j－，則取消之前給第j－個UE的分配；如果第j個UE在分配到第kj個RB簇之前已經(jīng)被分配了第k－j個RB簇，則把第k－

j個RB簇分配給第j－個UE。

③更新第kj個RB簇的pkj：

④把第j個UE設(shè)為滿意。通過判斷是否滿足補松弛條件，決定第j－個UE是否滿意。

第3步：迭代終止條件：所有UE都滿意。

這一方法充分地利用了UE在系統(tǒng)帶寬上的頻率選擇性。UE的MCS等級由UE在這個RB簇上的信道狀況決定，信道越好，可用的MCS等級越高，同時UE可以選擇系統(tǒng)帶寬上的任意一個RB簇使用，而由于信道的頻率選擇性。拍賣算法充分利用了UE在不同RB簇上MCS等級差別，為每個UE選擇合適的RB簇，從而使系統(tǒng)總體可以傳輸?shù)谋忍財?shù)最高，也因此使每個UE偏向于使用頻帶上MCS等級高的RB簇。

3 多扇區(qū)資源分配

3.1 問題模型

在實際的LTE上行系統(tǒng)中，多個扇區(qū)同時進行相互獨立的資源調(diào)度，可以直接對每個扇區(qū)獨立應(yīng)用2.2節(jié)中提出的單扇區(qū)資源分配算法得到單扇區(qū)的最優(yōu)解，再將各扇區(qū)的優(yōu)化結(jié)果聯(lián)合起來得到多扇區(qū)的資源分配方案。而對某個扇區(qū)而言，其他扇區(qū)干擾無法預(yù)知，即式（4）中的和不確定。同時每個扇區(qū)并不知道相鄰扇區(qū)的資源分配結(jié)果。時變性導(dǎo)致測量的信道狀況（即等效SNR）在實際發(fā)送時發(fā)生很大變化。表1為在城市宏蜂窩（UMa）場景下不同MCS等級下RB的平均傳輸成功率。可以看出，在扇區(qū)間同頻干擾存在時，RB的傳輸成功率會隨MCS等級的增加而不斷減小，頻譜效率無法得到有效提高。

表1 不同MCS等級下RB塊的平均傳輸成功率

3.2 多扇區(qū)資源分配算法

針對多扇區(qū)系統(tǒng)直接應(yīng)用第2.2節(jié)算法存在的問題，提出了一種適用于多扇區(qū)干擾不確定情況下的改進算法，通過在每個扇區(qū)的eNodeB端對每次的傳輸結(jié)果進行統(tǒng)計分析，以優(yōu)化拍賣算法參數(shù)的方法實現(xiàn)性能的提升。

在之前的討論中，任意一個扇區(qū)的第j個UE在第k個RB簇上拍賣算法的增益參數(shù)vkj設(shè)定為由信道狀況決定的MCS等級對應(yīng)的可傳輸?shù)谋忍財?shù)?？紤]到多扇區(qū)資源分配時扇區(qū)間干擾不確定的情況會導(dǎo)致不同MCS等級下RB傳輸成功率的不同，本文將增益參數(shù)修正為可以正確傳輸?shù)谋忍財?shù)的期望，表示為：

式中，rp為該UE在該RB簇上使用的MCS等級p對應(yīng)的RB傳輸成功率，它可以通過“學(xué)習(xí)”的方法得到：eNodeB會為每一個UE記錄其在不同MCS等級下的傳輸情況，初始化認為在每個MCS等級下傳輸成功率都為1，然后eNodeB根據(jù)每次接收UE數(shù)據(jù)是否成功和UE傳輸使用的MCS等級情況，逐步得到系統(tǒng)在不同MCS等級下的RB傳輸成功率統(tǒng)計。這種方法可以使用于傳輸情況未知的系統(tǒng)，移植性好。

本文的多扇區(qū)資源分配算法中，每個扇區(qū)的eNodeB資源分配的具體步驟如下：

第1步：eNodeB根據(jù)本扇區(qū)各UE在整個帶寬的RB簇上周期性發(fā)送的SRS信號進行上行信道估計的SNR大小決定UE在這些RB簇上的MCS等級，并根據(jù)MCS等級和RB簇的大小計算UE可以傳輸?shù)谋忍財?shù)，記為vjk。

第2步：eNodeB根據(jù)本扇區(qū)各UE最近一次上行傳輸?shù)那闆r，記錄其MCS等級和傳輸成功情況，更新不同MCS等級的傳輸成功率。設(shè)UE最近一次MCS等級為p，在此次傳輸前eNodeB記錄已經(jīng)使用MCS等級p進行過Ntotal次傳輸，其中Nsuccess次傳輸成功。如果此次傳輸成功，更新Ntotal=Ntotal+1，Nsuccess=Nsuccess+1；否則，僅更新Ntotal=Ntotal+1。同時，MCS等級p的RB傳輸成功率更新為：

第3步：eNodeB根據(jù)式（9），計算出本扇區(qū)中的各個UE在不同RB簇上期望成功傳輸?shù)谋忍財?shù)。

第4步：根據(jù)3.2節(jié)中給出的考慮重傳的拍賣算法的步驟，以第3步得到的值為增益參數(shù)進行迭代，得到本扇區(qū)進行資源分配的最優(yōu)解。

以上為各個扇區(qū)eNodeB的資源分配過程，將系統(tǒng)中所有扇區(qū)的eNodeB的分配過程聯(lián)合起來，就得到了多扇區(qū)系統(tǒng)的分配結(jié)果。

4 仿真及結(jié)果分析

4.1 仿真條件

建立了TD－LTE系統(tǒng)級仿真平臺以驗證文中設(shè)計的算法性能。UE使用full buffer業(yè)務(wù)模型，每次傳輸?shù)拇笮。ū忍財?shù)）由RB簇中包含的RB數(shù)目和MCS等級通過查表［13］決定。

表2為系統(tǒng)仿真參數(shù)。其中，單扇區(qū)資源分配和多扇區(qū)同時進行資源分配的不同在于：在單扇區(qū)資源分配方案中，目標扇區(qū)在每個調(diào)度子幀都進行資源分配，其他扇區(qū)的資源分配方案已知。而在多扇區(qū)資源分配方案中，扇區(qū)都同時進行獨立資源分配，其他扇區(qū)的資源分配方案未知。仿真中比較本文算法與將每個RB輪流分配給每個用戶的輪循算法的扇區(qū)頻譜效率和UE歸一化UE吞吐量（即UE頻譜效率）這兩個指標。

表2 TD－LTE上行仿真參數(shù)

4.2單扇區(qū)資源分配仿真結(jié)果

表1給出了單扇區(qū)情況下基于輪偱和拍賣的資源分配算法的頻譜效率。較輪循算法，使用拍賣算法可以使目標扇區(qū)的頻譜效率提高25％；歸一化UE吞吐量累積概率密度（CDF）分布圖2表明拍賣算法使UE最大頻譜效率和扇區(qū)邊緣頻譜效率（CDF圖中5％位置對應(yīng)的歸一化UE吞吐量大?。┓謩e提高20％和25％。單扇區(qū)仿真MCS等級數(shù)目比例圖3反映出拍賣算法較少使用較低的MCS等級（1～5），而是更多地使用較高的MCS等級（11～15），從而充分利用信道的頻率選擇性來提高系統(tǒng)的頻譜效率。

表1 單扇區(qū)資源分配的扇區(qū)頻譜效率

圖2 單扇區(qū)資源分配的歸一歸一化UE吞吐量CDF

圖3 單扇區(qū)所有RB的MCS等級數(shù)目比例

4.3 多扇區(qū)資源分配仿真結(jié)果

表2給出了在多扇區(qū)中使用輪循算法、直接應(yīng)用單扇區(qū)拍賣算法和使用多扇區(qū)拍賣算法得到的扇區(qū)頻譜效率，圖4給出了這幾種算法下的歸一化UE吞吐量CDF分布圖。使用多扇區(qū)拍賣算法相比輪循算法，可以使扇區(qū)頻譜效率提高30.8％，使UE最大頻譜效率和扇區(qū)邊緣頻譜效率分別提高了34.0％ 和33.9％，與直接應(yīng)用單扇區(qū)拍賣算法相比性能得到了很大的提升。圖5反映了多扇區(qū)拍賣算法一方面繼承了拍賣算法對信道頻率選擇性的充分利用，偏向于選擇中等及較高的MCS等級，另一方面考慮到由于干擾的不確定性使等級更高的MCS較難傳輸成功，在中等及較高的MCS等級中偏向于選擇使傳輸更容易成功的中等的MCS等級，在一定程度上保證了每次傳輸成功的比特數(shù)目，從而在整體上提高了頻譜效率。

表2 多扇區(qū)系統(tǒng)資源分配的扇區(qū)頻譜效率

圖4 多扇區(qū)系統(tǒng)資源分配歸一化UE吞吐量CDF

圖5 多扇區(qū)所有RB的MCS等級數(shù)目比例

5 結(jié)束語

上行資源分配是LTE系統(tǒng)中的一個重要問題，本文分析了單扇區(qū)的資源分配問題，在上行鏈路非自適應(yīng)重傳的前提下，提出了一種基于拍賣的單扇區(qū)資源分配算法。進一步，將這種算法應(yīng)用于多扇區(qū)系統(tǒng)分布式資源分配的環(huán)境中，針對因扇區(qū)間干擾造成的高等級MCS傳輸性能下降的問題，提出了一種多扇區(qū)資源分配算法。通過系統(tǒng)級仿真驗證了算法的性能。結(jié)果表明，與傳統(tǒng)的輪偱算法相比，本文算法可以提升系統(tǒng)頻譜效率與邊緣用戶頻譜效率，這是對QoS的直接改善，同時有效地改善了實際系統(tǒng)存在的丟包率隨MCS等級升高而上升的問題。算法具有復(fù)雜度較低、不改變現(xiàn)有LTE系統(tǒng)設(shè)計的特點。

［1］Astely D，Dahlman E，F(xiàn)uruskar A，et al.LTE：the Evolution of Mobile Broadband［J］.IEEE Communications Magazine，2009，47（4）：44－51.

［2］Fan JC，Yin Q Y，Li G Y，et al.Adaptive Block－level Resource Allocation in OFDMA Networks［J］.IEEE Transactions on Wireless Communications，2011，10（11）：3966－3972.

［3］陳瑾平，李春國，楊綠溪.比例速率約束下OFDMA系統(tǒng)近似最優(yōu)的資源分配算法［J］.電子與信息學(xué)報，2011，33（5）：1147－1153.

［4］Rawi A FAL，Sharif B S，Tsimenidis CC.User Priority A－ware Scheduling and Dynamic Resource Allocation in Orthogonal Frequency Division Multiple Access［J］.IET Communications，2011，5（7）：1006－1019.

［5］Myung H G，Lim J，Goodman D J.Single Carrier FDMA for uplink Wireless Transmission［J］.IEEE Vehicular Technology Magazine，2006，1（3）：30－38.

［6］Chang CH，Chao H L，Liu C L.Sum Throughput－improved Resource Allocation for LTE Uplink Transmission［C］∥IEEE Vehicular Technology Conference（VTC Fall），San Francisco，Sep.2011：1－5.

［7］Nwamadi O，Zhu X，Nandi A K.Enhanced Greedy Algorithm Based Dynamic Subcarrier Allocation for Single Carrier FDMA Systems［C］∥IEEEWireless Communications and Networking Conference（WCNC），Budapest，Hungary，Apr.，2009：1－6.

［8］Prasad N，ZHANG Honghai，ZHU HAO，et al.Multi－User MIMO Scheduling in the Fourth Generation Cellular Uplink［J］.Wireless Communications，IEEE Transactions on，2013，12（9）：4272－4285.

［9］王廣德，常永宇，蔣文婷，等.LTE－A異構(gòu)網(wǎng)絡(luò)下的高效資源分配算法［J］.無線電通信技術(shù)，2013，39（1）：1003－3114.

［10］Wong IC，OteriO，Mccoy W.Optimal Resource Allocation in uplink SC－FDMA System［J］.IEEE Transactions on Wireless Communications，2009，8（5）：2161－2165.

［11］Lim J，Myung H G，Oh K，etal.Channel－dependent Scheduling of Uplink Single Carrier FDMA Systems［C］∥IEEE Vehicular Technology Conference（VTC Fall），Montréal，Canada，Sept.，2006：1－5.

［12］Donthi SN，Mehta N B.An Accurate Model for EESM and its Application to Analysis of CQIFeedback Schemes and Scheduling in LTE［J］.IEEE Transactions on Wireless Communications，2011，10（10）：3436－3448.

［13］3GPP TS 36.213 V9.3.0－2010.Evolved Universal Terrestrial Radio Access（E－UTRA）Physical layer procedures ［S］，2010.

［14］Bertsekas D P.Auction Algorithms for Network Flow Problems：A Tutorial Introduction［J］.Computational Optimization and Applications，1992，1：7－66.

Resource Allocation Algorithm for Up link TD-LTE Based on Auction Algorithm

LIU Kai，DING Lu，ZHAO Jian－ye，LIU Zhi－min
（School of Electronics Engineering and Computer Science，Peking University，Beijing 100871，China）

In LTE uplink systems，the user equipment occupies continuous subcarriers，and one transmission is interfered by inter－sector interference.The efficient resource allocation is important to improve the system performance.Based on analysis and summary for related literature，a resource allocation algorithm for single－sector and multiple－sector systems based on auction algorithm is proposed，which is verified with system－level TD－LTE simulations.The results show that the proposed algorithm outperforms the conventionalmethod，and improves system spectrum efficiency（SE）and SE of cell－edge users，and the QoS for users is improved.

resource allocation；Long Term Evolution（LTE）；uplink；auction algorithm；spectrum efficiency

TN911

A

1003－3114（2015）04－47－5

10.3969/j.issn.1003－3114.2015.04.12

劉 凱，丁 璐，趙建業(yè)，等.基于拍賣算法的TD－LTE系統(tǒng)上行資源分配算法［J］.無線電通信技術(shù)，2015，41（4）：47－51，73.

2014－12－29

國家高技術(shù)研究發(fā)展計劃（863計劃）（2012AA011401）

劉凱（1990―），男，碩士研究生，主要研究方向：無線通信系統(tǒng)、綠色無線通信節(jié)能技術(shù)。趙建業(yè)（1972―），男，教授，博士生導(dǎo)師，主要研究方向：電路與系統(tǒng)、通信技術(shù)。