基于拍賣算法的TD－LTE系統上行資源分配算法

劉 凱，丁 璐，趙建業，劉志敏

（北京大學信息科學技術學院，北京100871）

基于拍賣算法的TD－LTE系統上行資源分配算法

劉 凱，丁 璐，趙建業，劉志敏

（北京大學信息科學技術學院，北京100871）

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

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

0 引言

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

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

1 系統和信號模型

1.1 系統模型

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

圖1 扇區和UE模型

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

1.2 信號模型

根據香農公式，可以將LTE上行第i個扇區的吞吐量Ri表示為：

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

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

2 單扇區資源分配

2.1 數學問題描述

首先僅針對目標扇區進行分析，即在式（4）中，認為扇區干擾的構成量和均為本扇區eNodeB已知的量。因此，扇區中的每個UE在不同RB簇上的對于eNodeB都是已知量。文中資源分配的目標是提高扇區吞吐量，即扇區內所有用戶可以傳輸的總比特數。因此，第i個扇區的資源分配問題可以表示為：

2.2 基于拍賣的單扇區資源分配算法

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

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

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

第1步：初始化。

①選定一個ε＞0；

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

③設pk=0，k=1，…N。

第2步：針對非自適應重傳UE的處理。

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

迭代過程：

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

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

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

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

③更新第kj個RB簇的pkj：

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

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

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

3 多扇區資源分配

3.1 問題模型

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

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

3.2 多扇區資源分配算法

針對多扇區系統直接應用第2.2節算法存在的問題，提出了一種適用于多扇區干擾不確定情況下的改進算法，通過在每個扇區的eNodeB端對每次的傳輸結果進行統計分析，以優化拍賣算法參數的方法實現性能的提升。

在之前的討論中，任意一個扇區的第j個UE在第k個RB簇上拍賣算法的增益參數vkj設定為由信道狀況決定的MCS等級對應的可傳輸的比特數。考慮到多扇區資源分配時扇區間干擾不確定的情況會導致不同MCS等級下RB傳輸成功率的不同，本文將增益參數修正為可以正確傳輸的比特數的期望，表示為：

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

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

第1步：eNodeB根據本扇區各UE在整個帶寬的RB簇上周期性發送的SRS信號進行上行信道估計的SNR大小決定UE在這些RB簇上的MCS等級，并根據MCS等級和RB簇的大小計算UE可以傳輸的比特數，記為vjk。

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

第3步：eNodeB根據式（9），計算出本扇區中的各個UE在不同RB簇上期望成功傳輸的比特數。

第4步：根據3.2節中給出的考慮重傳的拍賣算法的步驟，以第3步得到的值為增益參數進行迭代，得到本扇區進行資源分配的最優解。

以上為各個扇區eNodeB的資源分配過程，將系統中所有扇區的eNodeB的分配過程聯合起來，就得到了多扇區系統的分配結果。

4 仿真及結果分析

4.1 仿真條件

建立了TD－LTE系統級仿真平臺以驗證文中設計的算法性能。UE使用full buffer業務模型，每次傳輸的大小（比特數）由RB簇中包含的RB數目和MCS等級通過查表［13］決定。

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

表2 TD－LTE上行仿真參數

4.2單扇區資源分配仿真結果

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

表1 單扇區資源分配的扇區頻譜效率

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

圖3 單扇區所有RB的MCS等級數目比例

4.3 多扇區資源分配仿真結果

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

表2 多扇區系統資源分配的扇區頻譜效率

圖4 多扇區系統資源分配歸一化UE吞吐量CDF

圖5 多扇區所有RB的MCS等級數目比例

5 結束語

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

［1］Astely D，Dahlman E，Furuskar 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系統近似最優的資源分配算法［J］.電子與信息學報，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異構網絡下的高效資源分配算法［J］.無線電通信技術，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

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

2014－12－29

國家高技術研究發展計劃（863計劃）（2012AA011401）

劉凱（1990―），男，碩士研究生，主要研究方向：無線通信系統、綠色無線通信節能技術。趙建業（1972―），男，教授，博士生導師，主要研究方向：電路與系統、通信技術。