基于吞吐量和延遲折衷的LTE 下行調(diào)度算法研究

劉期烈，熊曉玲

(重慶郵電大學(xué)移動通信技術(shù)重點實驗室，重慶400065)

0 引言

基于OFDM(orthogonal frequency division multiplexing)的4G 無線通信系統(tǒng) LTE［1］(long term evolution)的出現(xiàn)引起了無線網(wǎng)絡(luò)下行鏈路調(diào)度算法［2］設(shè)計的研究熱潮。此系統(tǒng)中的調(diào)度是多用戶多業(yè)務(wù)調(diào)度，數(shù)據(jù)全部以IP數(shù)據(jù)包的形式傳輸，調(diào)度的功能就是在每個調(diào)度時刻決定將哪些無線資源分配給哪些用戶以完成通信，調(diào)度的目標(biāo)就是使系統(tǒng)吞吐量最大化，但是要以多用戶之間的公平性以及業(yè)務(wù)的服務(wù)質(zhì)量為前提［3］。

在此系統(tǒng)中，業(yè)務(wù)類型可分為2大類:GBR(guranteed bit rate)業(yè)務(wù)和Non-GBR(non-guranteed bit rate)業(yè)務(wù)。GBR業(yè)務(wù)對時延要求較為嚴(yán)格，可以通過接入控制、預(yù)留資源及事先保證等措施來保證其傳輸要求［4］，實時調(diào)度算法對其影響有限。Non-GBR業(yè)務(wù)沒有嚴(yán)格的時延要求，但是高延遲也是無法忍受的，可通過實時的調(diào)度優(yōu)化系統(tǒng)吞吐量和延遲。因此，對于傳輸Non-GBR業(yè)務(wù)，如何設(shè)計合理的調(diào)度算法來優(yōu)化系統(tǒng)的吞吐量和延遲是值得研究的問題。

目前，已有多個文獻(xiàn)對Non-GBR業(yè)務(wù)的調(diào)度算法進(jìn)行了研究。文獻(xiàn)［5］提出輪詢(round robin，RR)算法，保證了用戶之間很好的公平性，但是系統(tǒng)的吞吐量很低，因為當(dāng)某些用戶的信道條件很差時也會得到等概率的服務(wù)。文獻(xiàn)［6-7］中提出最大權(quán)重(maxweight)算法可以使系統(tǒng)的吞吐量最佳化，但是無論從平均延遲還是單個用戶的延遲來說此算法的延遲性能［8-10］都很差，為了解決這個問題，本文運用李雅普諾夫最優(yōu)化的理論［11-13］提出一種吞吐量效用最大化的調(diào)度算法，在延遲和吞吐量之間找到了一個很好的均衡。

1 系統(tǒng)模型

1.1 模型描述

從網(wǎng)絡(luò)的角度來說，這種系統(tǒng)可以轉(zhuǎn)化為一個多用戶多信道的離散時間槽系統(tǒng)，模型如圖1所示。

圖1中有n個用戶的緩存隊列和m個服務(wù)器(信道)，在每個時隙，一個給定的服務(wù)器只能分配給一個用戶，但是一個用戶可以接受來自多個服務(wù)器的服務(wù)。信道模型采用開關(guān)(ON/OFF)模型，由于信道的衰落，每個用戶和服務(wù)器之間的連接是時變的，如果一個用戶和一個服務(wù)器之間在時隙t是連接的，則表示這個服務(wù)器所代表的信道在時隙t處于ON狀態(tài)。

圖1 系統(tǒng)模型Fig.1 System model

假設(shè)基站將要傳輸給每個用戶的數(shù)據(jù)包都先存儲在一個相應(yīng)的緩存區(qū)隊列中，圖中Qi表示要發(fā)送給第 i個用戶的數(shù)據(jù)包存儲隊列，用 Q(t)=(Q1(t)，…，Qn(t))表示每個隊列在時隙t的隊列積壓矩陣，Sj表示第j個服務(wù)器，Ai(t)表示在時隙t到達(dá)隊列i的數(shù)據(jù)包的個數(shù)，用A(t)=(A1(t)，…，An(t))表示到達(dá)矩陣。為簡單起見，我們假設(shè)所有的數(shù)據(jù)包都有固定的大小，數(shù)據(jù)包的到達(dá)服從伯努利隨機(jī)過程，因此Ai(t)∈{0，1}，并假設(shè)A(t)獨立同分布，E{A(t)}= λ?(λ1，…，λn)。用μi(t)表示在時隙t為隊列Qi成功服務(wù)的數(shù)據(jù)包的個數(shù)，則隊列更新方程為

從方程(1)可以看出隊列緩存區(qū)可以存儲無限多個數(shù)據(jù)包，沒有數(shù)據(jù)包的丟棄。

我們定義系統(tǒng)的穩(wěn)定性［14］如下

即如果在時間平均的意義上所有隊列長度和是有限的，則網(wǎng)絡(luò)是穩(wěn)定的。

1.2 時變的服務(wù)器可靠性

用一個二進(jìn)制變量cij(t)表示服務(wù)器Sj和隊列Qi在時隙t的連接狀態(tài)，如果cij(t)=1則表示服務(wù)器Sj在時隙t對隊列Qi處于ONN狀態(tài)(即二者處于連接狀態(tài))，反之則表示兩者處于斷開狀態(tài)。用xj(t)=(x1j(t)，x2j(t)，…，xnj(t))表示服務(wù)器 Sj在時隙t的預(yù)傳輸矩陣，其中 xij(t)∈ {0，1}，如果xij(t)=1則表示cij(t)=1且服務(wù)器Sj在時隙t要為隊列Qi傳輸，假設(shè)xj(t)來自所有可允許的傳輸集合。預(yù)傳輸矩陣xj(t)和連接變量cij(t)聯(lián)合決定每個時隙t服務(wù)器Sj為隊列Qi成功服務(wù)的概率，用以下可靠性函數(shù)表示為

Pr［Sj成功服務(wù) Qi|xij(t)，cij(t)］ =

定義可靠性函數(shù)Ψij(xij(t)，cij(t))有如下特性

在實際中，cij(t)表示在每個時隙t的信道估計結(jié)果，由于這個估計可能不準(zhǔn)確，因此用可靠性函數(shù)Ψij(xij(t)，cij(t))表示實際網(wǎng)絡(luò)中信道可以支持隊列i傳輸?shù)母怕?。假設(shè)ACK/NACK(acknowledgement/nacknowledg-ement)信息在每個時隙末的時候會反饋給網(wǎng)絡(luò)調(diào)度者來告知每個隊列是否服務(wù)成功，服務(wù)不成功的數(shù)據(jù)包不離開緩存隊列。

用一個伯努利隨機(jī)變量Mij(t)表示在時隙t服務(wù)器Sj為隊列Qi成功服務(wù)的數(shù)據(jù)包的個數(shù)，具體定義為

定義隨機(jī)變量Yij(t)表示服務(wù)器Sj在時隙t是否分配給隊列Qi，具體定義如下

由于在實際系統(tǒng)中，在每個時隙一個給定的服務(wù)器只能為一個用戶服務(wù)，因此:

則服務(wù)變量μi(t)表示為

則用戶隊列更新方程可化簡為

1.3 最優(yōu)化目標(biāo)

我們的目標(biāo)就是設(shè)計一個高效的調(diào)度政策使以下基于吞吐量的效用函數(shù)［8］最大化

yi(t)為在時隙t為用戶i服務(wù)的數(shù)據(jù)包的個數(shù)。約束條件(10)式中的Λ為無線下行鏈路的網(wǎng)絡(luò)容量區(qū)，定義為所有可獲得吞吐量矩陣的閉集合。

2 最佳調(diào)度算法

2.1 算法設(shè)計

本文運用李雅普諾夫最優(yōu)化理論來設(shè)計調(diào)度算法。首先構(gòu)建李雅普諾夫函數(shù)L(t)，它是用來衡量系統(tǒng)的隊列積壓的一個標(biāo)量，具體定義為

可以看出L(t)≥0，如果L(t)的值很小，則意味著所有的隊列積壓都很小，如果L(t)的值很大，則至少有一個隊列積壓很大。為了保持系統(tǒng)穩(wěn)定，在每個時隙應(yīng)該盡最大可能減小L(t)的值。因此，我們定義李雅普諾夫漂移為

李雅普諾夫漂移Δ(t)表示李雅普諾夫函數(shù)L(t)從一個時隙到下一個時隙的變化，如果在每個時隙做控制決定貪婪的最小化Δ(t)，則可以使隊列減小到最低的阻塞狀態(tài)，這樣不但直觀的維持了網(wǎng)絡(luò)的穩(wěn)定性，而且降低了延遲。在每個時隙既要使吞吐量最優(yōu)化，還要降低延遲且保持系統(tǒng)穩(wěn)定，根據(jù)李雅普諾夫最優(yōu)化理論，我們的政策就是在每個時隙做控制決定最小化漂移－效用函數(shù):

(15)式中，V是一個非負(fù)的系統(tǒng)控制參數(shù)，用于調(diào)節(jié)延遲和基于吞吐量的網(wǎng)絡(luò)效用之間的均衡。在每個時隙做控制決定貪婪的最小化漂移－效用函數(shù)的值，這樣既維持了網(wǎng)絡(luò)的穩(wěn)定性，降低了延遲，又提高了網(wǎng)絡(luò)效用，有以下2個推理。

推理1:在每個時隙t，李雅普諾夫漂移Δ(t)滿足

(16)式中B是一個有限的常數(shù)，將方程(1)兩邊平方，并將(3)式及(4)式代入，利用μi(t)≤m，Ai(t)≤1進(jìn)行不等式的放大縮小便得到(16)式，具體證明省略。

推理2:在每個時隙t，漂移－效用函數(shù)滿足

(17)式中，常數(shù)B和(16)式的一樣，將(7)式、(9)式和(10)式代入(16)式便可得，具體證明省略。本文提出的資源分配算法設(shè)計理念就是在每個時隙做控制決定貪婪的最小化(17)式的右邊。由于傳輸決定不會影響Ai(t)，則只需使(18)式最大化

由于在每個時隙一個給定的服務(wù)器只能分配給一個用戶服務(wù)，因此

2.2 調(diào)度算法

通過上面的研究，給出本文的調(diào)度算法如下:

輸入:時隙t的所有隊列長度Qi(t)(1≤i≤n)及數(shù)據(jù)包到達(dá)個數(shù)Ai(t)，所有服務(wù)器Sj(1≤j≤m)和所有隊列的連接狀態(tài)cij(t)和Sj的預(yù)傳輸矩陣xij(t)。

步驟:

1)初始化k=1，Yij(t)=0，Q(0)i(t)=Qi(t)，1≤i≤n，1≤j≤m。

2)在第k輪服務(wù)器的分配中，找出隊列下標(biāo)滿足以下條件的

將服務(wù)器Sk分配給隊列 Qω，即 Yωk(t)=1，Yik(t)=0(i≠ ω )，并按(21)(22)式更新隊列Qω的長度。

其他的隊列長度保持不變，即

3)如果k=m，則停止，計算下一個時隙開始時刻的隊列長度，Qi(t+1)=Q(m)i(t)+Ai(t);否則k+1，重復(fù)步驟2)。

輸出:服務(wù)器的分配Yij(t)(1≤i≤n，1≤j≤m)，和下一個時隙 t開始時刻的隊列長度Qi(t+1)(1≤ i≤n)。

3 算法性能分析

定理1:假設(shè)存在ε≥0滿足λ+2ε1∈Λ，令Q(t)=(Q1(t)，…，Qn(t))，y*為最佳的吞吐量，g(y*)=g*為最佳吞吐量的效用，則在本文提出的調(diào)度算法下有

1)如果 ε≥0，則所有的隊列 Qi(t)(i∈ {1，…，n})在時間平均的意義上來說是穩(wěn)定的;

2)如果ε＞0，則所有隊列Qi(t)是強(qiáng)穩(wěn)定的，且有

證明:方程(16)可以寫為

對(24)式兩邊求期望得:

對(25)式兩邊從τ∈{0，1，…，t－1}求和得

假設(shè)ε＞0，對(26)式兩邊同時除以 tε，利用E{L(t)}≥0，E{g(y(t))}≥0變形得

對(27)式兩邊當(dāng)在t→∞ 求極限得(23)式。

由(26)式得

將(13)式代入(28)式得

則對所有的i∈{1，…，n}有

因為E{Qi(t)2}≥E{|Qi(t)|}2，則對所有的時隙t＞0有

對(31)式兩邊同時除以t，并在t→∞ 求極限得:

(32)式表明所有的隊列在時間平均的意義上來說是穩(wěn)定的。

定理2:假設(shè)所有的隊列在初始情況下都為空，令μi*(t)為最佳的服務(wù)率，且假設(shè)E{μi*(t)}=E{Ai(t)}=y*，則在本文提出的調(diào)度算法下有

證明:由(17)式得

運用g(y*)=g*及E{μi*(t)}=E{Ai(t)}=y*得

對(35)式兩邊求期望得

對上不等式兩邊從τ∈{0，1，…，t－1}求和，并除以t得:

由于L(·)≥0，將(37)式變形得

對(38)式中的凸函數(shù) g(·)使用詹森不等式［16］有

對(39)式在t→∞ 求極限得(33)式。

由定理2可以看出，增大系統(tǒng)控制參數(shù)V可以使基于吞吐量的網(wǎng)絡(luò)效用無限接近于最佳值，但是由定理1可以看出增大V值可以增大隊列積壓值，從而增大延遲，所以在延遲和吞吐量之間形成一個O(1/V，V)的均衡。因此本文提出的調(diào)度算法選擇合適的系統(tǒng)參數(shù)V至關(guān)重要。

4 仿真分析

為驗證本文所提算法的有效性，我們使用吞吐量、延遲來評估系統(tǒng)性能，仿真工具為Matlab(matrix laboratory)。以下數(shù)據(jù)仿真中我們都假設(shè)n=m，即假設(shè)在系統(tǒng)資源比較缺乏的情況下對算法性能做一個保守的估計。

首先將吞吐量和延遲視作V的函數(shù)，觀察吞吐量和延遲與V的關(guān)系，V值的變化范圍為0到500。每個用戶的平均數(shù)據(jù)包到達(dá)率為ˉλi=0.5，i∈{1，2，…，n}，信道狀態(tài)概率為 Pr［Sj(t)=ON］=0.5 ，j∈{1，2，…，m}，分別以不同的n=m=30 ，n=m=50來做實驗，仿真結(jié)果如圖2和圖3所示。

圖2 平均吞吐量隨V值的變化關(guān)系Fig.2 Average throughput versus V

圖3 平均延遲隨V值的變化關(guān)系Fig.3 Average delay versus V

圖2表示當(dāng)n=m=30，n=m=50時平均獲得的吞吐量隨V值的變化關(guān)系?？梢钥闯鲭S著V值的增大，平均獲得的吞吐量不斷增大并趨于飽和。圖3表示平均延遲隨V值的變化關(guān)系，可以看出隨著V值的增大，延遲也不斷增大。因此V控制吞吐量和延遲之間的均衡，必須選擇一個最佳的V值既使系統(tǒng)的吞吐量比較理想，同時又不會導(dǎo)致太大的延遲。結(jié)合圖2和圖3，我們可以看出當(dāng)n=30，50時我們分別選擇V=50，100時可以在吞吐量和延遲之間有一個很好的折衷。

因此，接下來我們以固定的值做實驗，比較最大權(quán)重算法和本文提出的算法的吞吐量效用和延遲。數(shù)據(jù)包的平均到達(dá)率和信道狀態(tài)參數(shù)設(shè)置和第1組實驗一樣，仿真時間為1 000個時隙，每個時隙設(shè)置為1 ms，仿真結(jié)果如圖4和圖5所示。

圖4顯示了本文所提算法和最大權(quán)重算法的吞吐量效用的比較，可以看出2種算法的吞吐量效用非常接近，因為2種算法都是在信道狀態(tài)比較好的情況下傳輸?shù)摹?/p>

圖4 2種算法吞吐量效用的比較Fig.4 Throughput utility of these two algorithm

圖5顯示了2種算法的延遲的經(jīng)驗分布，可以看出本文所提算法的延遲性能比最大權(quán)重算法要優(yōu)越很多，因為最大權(quán)重算法在每個調(diào)度時隙把所有可用的服務(wù)器全分配給隊列最長的用戶，將比其小的隊列都視為空，因此導(dǎo)致了單個用戶較大的延遲。

5 結(jié)束語

本文對LTE無線網(wǎng)絡(luò)下行鏈路的調(diào)度問題進(jìn)行了研究，針對Non-GBR業(yè)務(wù)傳輸提出了一種可以在吞吐量和延遲之間提供一個折衷的調(diào)度算法，該算法是運用李雅普諾夫最優(yōu)化的理論設(shè)計的，能夠根據(jù)當(dāng)前的信道狀態(tài)和當(dāng)前的隊列積壓來做實時地調(diào)度決定。理論分析和仿真結(jié)果均表明，所提出的調(diào)度算法能使網(wǎng)絡(luò)吞吐量達(dá)到最優(yōu)，同時減小了單個用戶的延遲，在吞吐量和延遲之間有一個很好的折衷。

圖5 2種算法延遲性能的比較Fig.5 Delay performance of these two algorithm

［1］3GPP TR 25.913.Requirements for Evolved UTRA(EUTRA)and Evolved UTRAN(E-UTRAN)(Release7)［EB/OL］.(2006-03-31)［2014-08-10］.http://www.etsi.org/deliver/etsi_tr/125900_125999/125913/07.03.00_60/tr_125913v070300p.pdf.

［2］趙先明，朱伏生，唐宏，等.TD-LTE系統(tǒng)動態(tài)資源分配算法研究［J］.重慶郵電大學(xué)學(xué)報:自然科學(xué)版，2013，25(2):226-230.ZHAO Xianming ，ZHUFusheng，TANG Hong，et al.Dynamic resource allocation algorithm in TD-LTE communication system［J］.Journal of Chongqing University of Posts and Telecommunications:Natural Science edition，2013，25(2):226-230.

［3］胡宏林，徐景.3GPP LTE無線鏈路關(guān)鍵技術(shù)［M］.北京:電子工業(yè)出版社，2008.HU Honglin，XU Jing.3GPP LTE Key Techology of Wireless Link［M］.Beijing:Publish House of Electronic Industry，2008.

［4］RAYMOND K，ROB A，MITSUHIRO K.On Radio Admission Control for LTE Systems［C］//Vehicular Technology Conference Fall(VTC 2010-Fall).［s.l.］.IEEE，2010:1-5.

［5］GUO Chuanxiong.ImprovedSmoothedRoundRobin Schedulers for High-Speed Packet Networks［C］//IEEE the 27th Conference on Computer Communications.［s.1.］:Conference on Publications，2008:906-914.

［6］ALEXANDER L S.Large Deviations of Queues Sharing a Randomly Time-Varying Server［J］.Queueing Systems，2008，59(1):1-35.

［7］YING Lei，SRIKANT R，ERYILMAZ A，et al.A Large Deviations Analysis of Scheduling in Wireless Networks［J］.IEEE Transaction on Information Theory，2006，52(11):5088-5098.

［8］BODAS S，SHAKKOTTAI S，YING Lei，et al.Low-Complexity Scheduling Algorithms for Multichannel Downlink Wireless Networks［J］.IEEE/ACM Transcation on Networking，2012，20(5):1608-1621.

［9］BUI L，SRIKANT R，STOLYAR A.Novel Architectures and Algorithms for Delay Reduction in Back-Pressure Scheduling and Routing ［C］//IEEE Infocom.［s.l.］:IEEE，2009:2936-2940.

［10］YING Lei，SHAKKOTTAI S，REDDY A.On Combining Shortest-Path and Back-Pressure Routing Over Multihop Wireless Networks［C］//IEEE Infocom.［s.L.］:IEEE.2009:1674-1682.

［11］MICHAEL J N.Delay-Based Network Utility Maximization［J］.IEEE/ACM Transcation on Networking，2013，21(1):41-54.

［12］LEONIDAS G，MICHAEL J N，LEANDROST.Resource Allocation and Cross-Layer Control in Wireless Networks［J］.Foundations and Trends in Networking，2006，1(1):1-144.

［13］MICHAEL J N，EYTAN M，CHARLES E R.Dynamic Power Allocation and Routing for Time-Varying Wireless Networks［J］.IEEE Journal on Selected Areas in Communications，2005，23(1):89-103.

［14］YAO Yuan，LONGBO H，ABHIHSHEK S，et al.Data Centers Power Reduction:A two Time Scale Approach for Delay Tolerant Workloads［C］//Proceedings IEEE Infocom.［S.l.］:IEEE，2012:1431-1439.

［15］CHIH-PING L，MICHAEL J N.Network Utility Maximization over Partially Observable Markovian Channels［C］//International Symposium on Modeling and Optimization in Mobile，Ad Hoc and Wireless Networks.［S.l.］:［s.n.］，2011:17-24.

［16］STEPHEN B，LIEVEN V.Convex Optimization［M］.New York:Cambridge University Press，2004:1-730.