劉期烈，熊曉玲

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

0 引言

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

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

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

1 系統(tǒng)模型

1.1 模型描述

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

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

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

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

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

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

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

1.2 時變的服務器可靠性

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

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

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

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

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

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

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

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

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

1.3 最優(yōu)化目標

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

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

2 最佳調度算法

2.1 算法設計

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

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

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

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

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

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

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

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

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

2.2 調度算法

通過上面的研究，給出本文的調度算法如下:

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

步驟:

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

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

將服務器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，重復步驟2)。

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

3 算法性能分析

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

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

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

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

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

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

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

對(27)式兩邊當在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:假設所有的隊列在初始情況下都為空，令μi*(t)為最佳的服務率，且假設E{μi*(t)}=E{Ai(t)}=y*，則在本文提出的調度算法下有

證明:由(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)絡效用無限接近于最佳值，但是由定理1可以看出增大V值可以增大隊列積壓值，從而增大延遲，所以在延遲和吞吐量之間形成一個O(1/V，V)的均衡。因此本文提出的調度算法選擇合適的系統(tǒng)參數(shù)V至關重要。

4 仿真分析

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

首先將吞吐量和延遲視作V的函數(shù)，觀察吞吐量和延遲與V的關系，V值的變化范圍為0到500。每個用戶的平均數(shù)據(jù)包到達率為ˉλ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來做實驗，仿真結果如圖2和圖3所示。

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

圖3 平均延遲隨V值的變化關系Fig.3 Average delay versus V

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

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

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

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

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

5 結束語

本文對LTE無線網(wǎng)絡下行鏈路的調度問題進行了研究，針對Non-GBR業(yè)務傳輸提出了一種可以在吞吐量和延遲之間提供一個折衷的調度算法，該算法是運用李雅普諾夫最優(yōu)化的理論設計的，能夠根據(jù)當前的信道狀態(tài)和當前的隊列積壓來做實時地調度決定。理論分析和仿真結果均表明，所提出的調度算法能使網(wǎng)絡吞吐量達到最優(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］.重慶郵電大學學報:自然科學版，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無線鏈路關鍵技術［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.