LTE 系統上行鏈路調度算法研究*

王曉明，王 晨，王志強，緱鵬超

（國網陜西省電力公司信息通信公司，陜西 西安 710004）

0 引言

近幾年，移動通信取得了飛速進展。移動用戶對高數據速率的需求，進一步推動了移動網絡的出現。第三代合作計劃（3rd Generation Partnership Project，3GPP）的長期演進（Long Term Evolution，LTE）技術是新移動技術之一。早在2004 年底，3GPP 就啟動了LTE 技術的標準化工作，并在2009年3 月發布了R8 版本的FDD-LTE 和TDD-LTE 標準，標志著LTE 標準草案研究完成，LTE 進入實質研發階段。R9 版本中進一步提出了LTE-Advanced（Long Term Evolution-Advanced，LTE-A）的概念。LTE-A 于2010 年6 月通過ITU 的評估，于2010 年10 月正式成為IMT-A 的主要技術之一，是在R8 版本基礎上的演進和增強。R10 版本對其加以完善，是LTE-A 的關鍵版本。LTE-A 的目的是滿足無線通信市場的需求，滿足和超過IMT-Advanced 的需求，同時保持對LTE 較好的后向兼容性。LTE-A主要采用載波聚合、多點協作傳輸、中繼等關鍵技術。這些技術增強了LTE-A 小區的系統容量與信息的傳輸速率，同時極大地改善了小區邊緣用戶的性能。LTE 可以提供每秒兆比特級的數據速率[1]，具有高頻譜效率、高峰值速率、高移動性和網絡架構扁平化等多種優勢。LTE 可以提供語音、視頻和數據的無縫融合，與LTE-Advanced 已成為最有前景的無線接入技術。

LTE 本質上與之前的移動無線接入技術不同。LTE 系統在其下行鏈路中使用正交頻分多址（Orthogonal Frequency Division Multiple Access，OFDMA）技術，在其上行鏈路中使用單載波頻分多址（Single Carrier Frequency Division Multiple Access，SC-FDMA）技 術。OFDMA 技 術 和SC-FDMA 技術通過提供更好的干擾控制來提高數據速率[1]。OFDMA 技術和SC-FDMA 技術都是將信道分成多個子載波，然而將子載波調度給不同的用戶，以使系統利用率最大，并不是一件簡單的事情。目前，下行鏈路調度已經被大多數研究人員關注，而上行鏈路調度仍是研究相對較少的領域[2-6]。

在LTE 系統中，基站（Evolved Node B，eNodeB）執行分組調度任務。分組調度指的是為傳輸分組分配某組子載波。子載波分配在12 個15 kHz 的子載波組中進行，在時域上持續時間為1 ms。1 ms 的持續時間為傳輸時間間隔（Transit Time Interval，TTI），用于執行分配任務的單元稱為物理資源塊（Physical Resource Block，PRB），預計每個用戶在不同的PRB 中經歷頻率選擇性衰落。此外，由于不同的空間位置，不同的用戶在某個PRB 上經歷互不相同的信道條件，而信道條件會影響調制和編碼方案（Modulation and Coding Scheme，MCS）。因此，eNodeB 必須將多個PRB 分配給多個用戶，以最大化每個TTI 中比特傳輸的可能性。在TEL 系統中，調度在下行鏈路和上行鏈路完成。其中，下行鏈路允許進行PRB 的分布式分配[7]。而在上行鏈路中，由于SC-FDMA 技術的限制，PRB 的連續分配更為恰當，而PRB 的連續分配會使分配問題成為NP-Hard 問題[8]。

此外，當調度具有服務質量（Quality of Service，QoS）約束的實時業務分組時，調度方案需要考慮延遲期限和分組丟棄約束。為了滿足延遲期限要求，文獻[9-10]提出了包含兩個階段的調度方案：第一個階段為時域分組調度（Time-Domain Packet Scheduling，TDPS），第二個階段為頻域調度（Frequency Domain Scheduling，FDPS）。TDPS基于頭（head of the line，HoL）分組延遲將用戶列入名單，再將PRB 分配給名單中的用戶[9]，用于在比特傳輸方面最大化系統吞吐量，但是考慮最終分配的用戶子集會導致次優解決方案。為了計算最優解，研究應該遍歷所有可能的選項，同時保持一定的計算復雜度。

文獻[8-9，11-14]提出的用于下行鏈路和上行鏈路的調度算法僅進行了信道感知調度，認為分組始終在用戶設備（User Equipment，UE）緩沖區中傳輸。這些算法會將PRB 分配給具有信道增益高的UE，即使該UE 在其緩沖區中沒有足夠的數據來使用分配的PRB。由于沒有考慮緩沖區狀態，MAC層吞吐量（即實際發送的比特數）較低[15]。

本文研究了LTE 系統上行鏈路調度優化算法，eNodeB 通過考慮實時業務的延遲約束條件來保證分組能在延遲期限內傳輸。調度時eNodeB 考慮UE面臨丟棄風險的分組數，能最小化由調度引起的丟棄分組數，確保具有緊急要求的UE 總能被優先調度，提高公平性。

1 上行鏈路調度

基于延遲感知實時業務，對文獻[15]中的改進動態匈牙利算法（Dynamic Hungarian Algorithm with modification，DHAM）進行優化。表1 示出了本文所使用的多個符號及其含義。

表1 符號及其含義

對于盡力服務型（best-effort traffic）業務，DHAM可以以最優方式工作。然而，當具有延遲約束的業務即實時業務時，DHAM 可能會降低QoS。典型的實時業務包括語音和視頻。由于DHAM 是CA 與緩沖器共同感知的，因此可能以更好的信道質量調度UE，即使信道質量差的用戶緩沖區被建立，它們也可能無法獲得傳輸機會。此外，對于實時業務，如果分組沒有在其期限內傳輸，則該分組被丟棄，最終導致QoS 進一步惡化。基于此，本文對DHMA進行優化，以確保其適用于實時業務。

使用和DHMA 相同的流量矩陣W進行計算。W由wi，j組成，wi，j為第i個UE 通過第j個資源塊（Resource Chunk，RC）發送數據時產生的流量。首先建立目標整數線性規劃模型，該目標整數線性規劃模型包括目標函數、實時業務的延遲約束條件、第一約束條件和第二約束條件。

目標函數為：

式中，αi，j為二進制變量。當第i個UE 被分配第j個RC 時，αi，j為1；當第i個UE 沒有被分配第j個RC 時，αi，j為0。

實時業務的延遲約束條件為：

式中，δi為第i個UE 的HoL 分組的延遲。當第i個UE 在當前TTI 被調度時，；當第i個UE 在當前TTI 未被調度時，。此外，Dth為實時業務的延遲期限，其中t為當前TTI 的長度。

實時業務的延遲約束條件用于表示當第i個UE 的HoL 分組超過延遲期限時，eNodeB 強制對第i個UE 進行調度。

第一約束條件為：第一約束條件用于表示如果將某個RC 分配給所有UE，則只能將該RC 分配給至多一個UE。第二約束條件為：

第二約束條件用于表示如果給某個UE 分配RC，則只能給該UE 分配至多一個RC。

實時業務的延遲約束條件、第一約束條件和第二約束條件為不等式，以便適用于不同數量的RC和UE。

消除可能的不可行性為ND＞M；當ND＜M，即延遲違規用戶數量小于RC 數量時，可以采用式（1）～式（4）；當ND＞M時，只能列出延遲違規用戶集合Ω中的用戶，然后對其執行DHAM，不涉及延遲約束。但是，若在當前TTI 中未調度w∈Ω，僅在Ω執行DHAM，將得不到丟棄的分組數。如表2 所示，UE2 具有相對較好的信道條件，但較少的分組面臨丟棄風險；而UE1 具有相對較差的信道條件，但在其緩沖區中將丟棄大量的分組。因此，為了實現公平性，應該優先調度UE1。然而，采用DHAM 時得到的結果相反。

表2 調度實例一

此外，還需要最小化由此調度引起的分組丟棄數量。表3 的例子中，可以得到調度UE 導致丟棄的字節數大于調度UE2 導致丟棄的字節數。顯然，調度UE2 時公平性較差，但系統會更完善。因為調度UE2 能減少未來分組丟棄，從而間接控制長期系統吞吐量。

表3 調度實例二

為了確保公平性并最小化分組丟棄，本文建立如下目標函數：

式中，ki為如果第i個UE 未在當前TTI 中調度，將被丟棄的字節數；dij為如果第i個UE 分配到第j個RC 時，第i個UE 將丟棄的字節數。

關于式（5）的約束條件為：

2 仿真和結果

為了驗證本文算法的有效性，在OMNeT++網絡模擬器中開發的系統級模擬器上進行仿真。仿真所用的實施環境如圖1 所示，一個小區被6 個一級小區所包圍，中心小區為服務小區，一級小區提供干擾信號功率。本文以中心小區為研究對象，所有仿真結果均被記錄在中心小區。

圖1 仿真模型

本文將UE 按照泊松分布方式部署在小區中，UE 是靜止的（雖然仿真中UE 靜止，但對于移動用戶，該算法也是有效的），并假設所有UE 都與其服務eNodeB 直連，且上行鏈路傳輸功率控制和MCS 參考文獻[16]。參考文獻[17-18]使用塊衰落信道模型（若基站和用戶設備之間幾乎沒有相對移動，則認為一定時間內信道基本保持不變，在這段時間內的連續符號遭受的衰落是相同的，即為塊衰落模型），信道條件在一個TTI 上保持不變。此外，本文還假設eNodeB 在獲取調度決策時知道所有UE的CQI、緩沖長度和關鍵分組。

本文將提出的上行鏈路調度算法和DHAM 的性能進行對比，對比參數包括公平性、MAC 層吞吐量、最差信道條件的用戶傳送的分組量以及延遲等參數。公平性結果對比如圖2 所示。使用本文提出的調度算法時，公平性得到改善，因為不管在什么時候，當用戶在相當長時間內遭受不良信道條件時，本文調度算法能為其提供占用信道的機會，而DHAM 僅提高MAC 層吞吐量，所以常常會選擇具有更高信道質量的用戶。但是，采用本文調度算法減少了因延遲而產生的分組丟棄，所以在改善公平性的同時并沒有犧牲MAC 層吞吐量，如圖3 所示。

圖2 公平性對比

圖3 MAC 層吞吐量對比

采用本文提出的調度算法，能優先處理分組，即將違反延遲約束的用戶。如果所有用戶的輸入速率相似，那么信道質量差的用戶通常會受到最嚴重的打擊。采用本文調度算法能增強最差信道條件的用戶分組傳送效果。圖4 示出了在本文調度算法的延遲感知調度下，具有最差信道條件的用戶的分組傳送的增強效果。

如圖5 所示，為了優先選擇具有更多延遲分組的用戶，采用本文提出的調度算法會推遲具有更高信道質量的用戶分組的傳輸，因此增加了平均延遲，但其能保證實際延遲在業務分組延遲限制內。

圖4 最差用戶分組傳送效果

圖5 語音業務平均延遲影響

3 結語

針對實時業務，本文提出了一種新的上行鏈路調度算法，考慮了實時業務的延遲約束，能夠保證實時業務分組在延遲期限內傳輸，適用于實時業務。在調度時，eNodeB 能考慮UE 面臨丟棄風險的分組數，能最小化由調度引起的丟棄分組數，確保具有緊急要求的UE 總能被優先調度，改善公平性。仿真結果表明，在LTE eNodeB 上采用該調度算法，能顯著改善LTE 上行鏈路性能。