劉永毓，劉婷婷

（1.中國(guó)移動(dòng)通信集團(tuán)廣東有限公司，廣州 510630；2.愛(ài)立信移動(dòng)數(shù)據(jù)應(yīng)用研究開(kāi)發(fā)（廣州 限公司，廣州 510630）

LTE無(wú)線網(wǎng)絡(luò)下行鏈路動(dòng)態(tài)資源分配算法研究

劉永毓1，劉婷婷2

（1.中國(guó)移動(dòng)通信集團(tuán)廣東有限公司，廣州 510630；2.愛(ài)立信移動(dòng)數(shù)據(jù)應(yīng)用研究開(kāi)發(fā)（廣州 限公司，廣州 510630）

本文采用李雅普諾夫最優(yōu)化的方法設(shè)計(jì)了一種資源分配算法，理論分析和仿真結(jié)果表明，該方法不但提高了系統(tǒng)的吞吐量，同時(shí)還在在吞吐量和延遲之間實(shí)現(xiàn)了較好的均衡。

下行鏈路；動(dòng)態(tài)資源分配算法

1 引言

無(wú)線資源是有限的，而用戶的需求是無(wú)限的。由于無(wú)線信道的時(shí)變性，因此高效的調(diào)度算法對(duì)于提高系統(tǒng)的吞吐量和用戶的穩(wěn)定性具有重要的作用。從網(wǎng)絡(luò)的角度來(lái)說(shuō)，這種系統(tǒng)可以轉(zhuǎn)換為一個(gè)多用戶多服務(wù)器系統(tǒng)，每個(gè)服務(wù)器代表一個(gè)子信道。由于在每個(gè)時(shí)隙一個(gè)給定的服務(wù)器只能為一個(gè)用戶服務(wù)，因此本文要解決的就是多個(gè)用戶競(jìng)爭(zhēng)一個(gè)給定的服務(wù)器的問(wèn)題。系統(tǒng)模式如圖1所示。

圖1 用戶間單個(gè)服務(wù)器競(jìng)爭(zhēng)示意圖

圖1中，基站將要傳輸給每個(gè)用戶的數(shù)據(jù)包都先存儲(chǔ)在一個(gè)相應(yīng)的緩存區(qū)隊(duì)列中，圖中Qi表示要發(fā)送給第i個(gè)用戶的數(shù)據(jù)包存儲(chǔ)隊(duì)列，Ai(t)表示在時(shí)刻t到達(dá)隊(duì)列i的數(shù)據(jù)包的個(gè)數(shù)，S表示給定的單個(gè)服務(wù)器。由于信道的衰落，每個(gè)隊(duì)列和服務(wù)器之間的連接是隨著時(shí)間而變化的，連接狀態(tài)用一個(gè)二進(jìn)制連接變量Ci(t)表示。最終要解決的問(wèn)題就是當(dāng)與服務(wù)器S處于連接狀態(tài)的多個(gè)隊(duì)列競(jìng)爭(zhēng)服務(wù)器S時(shí)，到底要將服務(wù)器S分配給哪一個(gè)隊(duì)列[2]。最終目標(biāo)就是設(shè)計(jì)一個(gè)高效的資源分配算法不但要提高網(wǎng)絡(luò)吞吐量，而且還要保證用戶的服務(wù)質(zhì)量。

在此隊(duì)列模型中服務(wù)器的分配是可以控制的，網(wǎng)絡(luò)控制者在做分配決定前知道隊(duì)列的長(zhǎng)度。在每個(gè)時(shí)隙可能根據(jù)對(duì)隊(duì)列歷史狀態(tài)的觀察和之前的分配情況來(lái)決定現(xiàn)在的分配，分配政策首先要使系統(tǒng)穩(wěn)定，其次要最大限度的提高網(wǎng)絡(luò)吞吐量，降低延遲，保證用戶的服務(wù)質(zhì)量。本文是用李雅普諾夫最優(yōu)化的理論設(shè)計(jì)一種基于隊(duì)列積壓和延遲的動(dòng)態(tài)資源分配算法，這種方法既維持了網(wǎng)絡(luò)的穩(wěn)定性，將隊(duì)列積壓降低到一個(gè)最小的阻塞狀態(tài)，降低了延遲，又提高了吞吐量，而且在吞吐量和延遲之間設(shè)置了一個(gè)很好的均衡。

2 系統(tǒng)模型分析

2.1 系統(tǒng)模型描述

系統(tǒng)模型如圖1所示，用Q(t)=(Q1(t),...,Qn(t))表示每個(gè)隊(duì)列在時(shí)隙t的隊(duì)列積壓（數(shù)據(jù)包的個(gè)數(shù)），假設(shè)每個(gè)隊(duì)每個(gè)隊(duì)列的數(shù)據(jù)包的個(gè)數(shù)。假設(shè)A(t)獨(dú)立同分布，且E{A(t)}=@(λ1, ..., λn)。用C(t)=(C1(t), C2(t),...C3(t))表示服務(wù)器S與隊(duì)列連接的狀態(tài)矩陣。在時(shí)隙t，若Ci(t)=1則表示隊(duì)列Qi與服務(wù)器S處于連接狀態(tài)（信道狀態(tài)處于ON狀態(tài)），若Ci(t)=0，則表示隊(duì)列Qi與服務(wù)器S處于斷開(kāi)的狀態(tài)（信道狀態(tài)處于OFF狀態(tài)）。用μi(t)表示在時(shí)隙t為用戶i成功服務(wù)的數(shù)據(jù)包的個(gè)數(shù)，則隊(duì)列的動(dòng)態(tài)更新方程如下[3]：

要使整個(gè)系統(tǒng)穩(wěn)定，則所有隊(duì)列在時(shí)間平均的意義上必須滿足以下條件：

2.2 時(shí)變的鏈路可靠性

假設(shè)服務(wù)器在每個(gè)時(shí)隙至多可以傳輸一個(gè)數(shù)據(jù)包，則μi(t)∈{0,1}。用x(t)=(x1(t),x2(t),..., x3(t))表示傳輸矩陣，xi(t)∈{0,1}，若xi(t)=1則表示服務(wù)器S在時(shí)隙t要對(duì)隊(duì)列Qi進(jìn)行傳輸，假設(shè)x(t)來(lái)自所有可允許的傳輸集合X，x(t)∈X。傳輸矩陣x(t)和服務(wù)器的狀態(tài)矩陣C(t)聯(lián)合決定每個(gè)時(shí)隙服務(wù)器成功分配的概率，用以下所示的可靠性函數(shù)表示：

可靠性函數(shù)Ψi(x(t)，C(t))∈[0,1]，表示在給定x(t)和C(t)時(shí)服務(wù)器S成功分配給隊(duì)列Qi的概率。

在實(shí)際中，C(t)表示每個(gè)時(shí)隙信道估計(jì)的結(jié)果，這個(gè)估計(jì)可能不準(zhǔn)確，因此用可靠性函數(shù)Ψi(x(t)，C(t))表示實(shí)際網(wǎng)絡(luò)中信道可以為用戶隊(duì)列傳輸?shù)母怕?。假設(shè)ACK/NACK信息在每個(gè)時(shí)隙末會(huì)反饋給每個(gè)用戶隊(duì)列，已告知傳輸是否成功，沒(méi)有傳輸成功的數(shù)據(jù)包繼續(xù)存儲(chǔ)在緩存隊(duì)列中。

則服務(wù)變量表示如下：

假設(shè)給定當(dāng)前的預(yù)傳輸矩陣x(t)和服務(wù)器狀態(tài)矩陣C(t)時(shí)，在當(dāng)前時(shí)隙t成功傳輸與否與過(guò)去的狀態(tài)無(wú)關(guān)。

2.3 最優(yōu)化的目標(biāo)函數(shù)

設(shè)計(jì)資源分配政策的最終目的就是使目標(biāo)函數(shù)最優(yōu)化，本文的目標(biāo)函數(shù)如下所示：

式中，yi(t)為時(shí)隙t中用戶i成功服務(wù)的數(shù)據(jù)包的個(gè)數(shù)。

定義為無(wú)線網(wǎng)絡(luò)下行鏈路的網(wǎng)絡(luò)容量區(qū)，定義為所有可獲得吞吐量矩陣@(1,..., n)的閉集合。

3 最佳資源分配政策

李雅普諾夫最優(yōu)化理論是隨機(jī)網(wǎng)絡(luò)最優(yōu)化的一種數(shù)學(xué)方法，此優(yōu)化方法可以防止對(duì)信道狀況預(yù)測(cè)不準(zhǔn)確而帶來(lái)的限制，它只需觀察每個(gè)時(shí)隙開(kāi)始時(shí)刻的信道狀況，不像傳統(tǒng)的基于預(yù)測(cè)的算法需要對(duì)信道狀況做長(zhǎng)期的預(yù)測(cè)。這種方法充分考慮了隊(duì)列模型的動(dòng)態(tài)效果，充分利用了隊(duì)列的積壓信息來(lái)做各種調(diào)度控制決定。

3.1 算法設(shè)計(jì)思想

用Hi(t)表示在時(shí)隙t數(shù)據(jù)包到達(dá)隊(duì)列Qi前端的等待時(shí)間，如果Qi在t時(shí)沒(méi)有數(shù)據(jù)包，則定義Hi(t)=0。如果在t時(shí)一個(gè)數(shù)據(jù)包到達(dá)一個(gè)空的隊(duì)列，規(guī)定在t+1時(shí)將其放置在隊(duì)列前端。定義示性變量αi(t)，如果Qi(t)＞0，則αi(t)=1，反之為0。則數(shù)據(jù)包到達(dá)隊(duì)列前端的等待時(shí)間Hi(t)的更新方程如下[4]：

式中，βi(t)=1-αi(t)；Ti(t)為隊(duì)列前端的數(shù)據(jù)包和后繼到達(dá)的數(shù)據(jù)包之間的時(shí)間間隔?？梢赃@樣理解：如果αi(t)=0，則βi(t)=1，則隊(duì)列Qi此時(shí)為空，此時(shí)僅且當(dāng)僅有一個(gè)數(shù)據(jù)包到達(dá)時(shí)Hi(t)=1。相反，如果αi(t)=1，

則βi(t)=0。由于隊(duì)列前端數(shù)據(jù)包和后繼到達(dá)數(shù)據(jù)包之間的間隔Ti(t)可能大于或等于Hi(t)+1，在這種情況下，定義t+1時(shí)刻隊(duì)列為空，則此時(shí)Hi(t+1)=0。

定義(t)[Q(t); H(t)]，Q(t)和H(t)分別為方程（1）的值和方程（9）的值的矩陣，構(gòu)建如下所示的李雅普諾夫函數(shù)：

將每個(gè)時(shí)隙所有隊(duì)列的平方和定義為李雅普諾夫函數(shù)L(t)，如果L(t)很小，則所有的隊(duì)列都很小，如果L(t)很大，則至少有一個(gè)隊(duì)列很大。因此李雅普諾夫函數(shù)是用其來(lái)衡量網(wǎng)絡(luò)阻塞的標(biāo)量。

定義((t))為李雅普諾夫一步漂移，其表達(dá)式如下：

如果在每個(gè)時(shí)隙做控制決定，貪婪的最小化Δ(t)，這樣可以將隊(duì)列積壓降低到一個(gè)最小的阻塞狀態(tài)，直觀的維持了網(wǎng)絡(luò)的穩(wěn)定性。

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

3.2 最佳資源分配算法

每個(gè)時(shí)隙t，觀察Q(t)，H(t)和C(t)，按照下面的步驟做服務(wù)器的分配決定：

（1）選擇一個(gè)傳輸矩陣x(t)解決以下最大化問(wèn)題：

（2）隊(duì)列更新：根據(jù)方程（1）和方程（12）更新隊(duì)列。

4 算法性能分析

定理1：假設(shè)存在ε≥0使λ+2ε1∈Λ，令Θ(t)=(Θ1(t),..., Θn(t))，假設(shè)E{L((0))}＜∞，則在本文提出的分配算法下有：

如果ε≥0，則所有的隊(duì)列Θi(t)的均值穩(wěn)定。如果ε＞0，則所有的隊(duì)列都穩(wěn)定。

對(duì)上式兩邊當(dāng)t→∞取極限得（b）證畢。由式（12）得

由于|Θi(t)|≥0，則E{Θi(t)2}≥E{|Θi(t)|}2，則式兩邊同時(shí)除以t，并在t→∞取極限得。

定理2：假設(shè)所有的隊(duì)列起初為空，令y*表示最佳的吞吐量的時(shí)間平均矩陣，則g(y*)=g*為最佳的網(wǎng)絡(luò)效用，μ*(t)為最佳服務(wù)率，假設(shè)E{μ*(t)}=E{Ai(t)}=y*，系統(tǒng)控制參數(shù)V＞0。

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

5 仿真分析

為驗(yàn)證本文所提算法的優(yōu)越性能，我們使用吞吐量、延遲來(lái)評(píng)估系統(tǒng)系能，仿真工具為Matlab。仿真場(chǎng)景為50個(gè)用戶的無(wú)線網(wǎng)絡(luò)下行鏈路，調(diào)度間隔（slot）為1ms，在每個(gè)調(diào)度間隔數(shù)據(jù)包的平均到達(dá)率為0.5，信道處于on狀態(tài)的概率為0.5。

我們首先將吞吐量和延遲視作V的函數(shù)，觀察吞吐量和延遲與V的關(guān)系，V值變化范圍為0到1000，仿真時(shí)間為1500ms。由圖2可以看出隨著V值的增大系統(tǒng)的平均吞吐量也不斷增大并趨于飽和，同時(shí)系統(tǒng)的平均延遲，隨著V值得增大線性增長(zhǎng)，因此必須選擇一個(gè)最佳的V值既使系統(tǒng)的吞吐量比較理想，同時(shí)又不會(huì)導(dǎo)致太大的延遲。由圖2可知，選擇V=120時(shí)，平均吞吐量等于0.397，平均延遲為105個(gè)slot，是一個(gè)很好的折中點(diǎn)。

圖2 平均吞吐量及延遲與V的關(guān)系

其次，我們固定V值時(shí)，比較本文所提出的算法和隨即分配算法吞吐量和延遲的性能，仿真時(shí)間為1000ms。隨即分配算法就是將服務(wù)器隨即分配給不為空的用戶隊(duì)列。圖3將兩種算法的吞吐量進(jìn)行延遲，在仿真算法內(nèi)本文提出的算法吞吐量比隨機(jī)分配的算法高。圖3給出兩種算法的延遲的經(jīng)驗(yàn)分布，可以看出本文算法和隨機(jī)分派算法相比改善了延遲性能。

6 結(jié)束語(yǔ)

本文針對(duì)LTE無(wú)線網(wǎng)絡(luò)下行鏈路系統(tǒng)用戶間對(duì)一個(gè)服務(wù)器競(jìng)爭(zhēng)的問(wèn)題，根據(jù)李雅普諾夫最優(yōu)化理論，設(shè)計(jì)了一種動(dòng)態(tài)資源分配方法——基于隊(duì)列積壓和延遲。本文提出的算法不但能優(yōu)化吞吐量，還能減少用戶延遲，實(shí)現(xiàn)兩者均衡?！?/p>

圖3 吞吐量圖

[1] 徐景，胡宏林，周婷．3GPPLTE標(biāo)準(zhǔn)化進(jìn)展．中興通信技術(shù)，2007, 13(2): 9-12

[2] 譚偉，張文新，馬雨出．LTE的無(wú)線資源管理．郵電設(shè)計(jì)技術(shù)，2007(3): 62-64

[3] 3GPP, R1-060297. Uplink power control, Nokia TSGR,144.

LTE Wireless Network Downward Link Dynamic Resource Allocation Algorithm Research

Liu Yongyu1; Liu Tingting2
(1.The China Mobile Croup Guangdong Co.,Ltd., Guangzhou, 510630; 2.Ericsson Mobile Data Applications Research And Development (Guangzhou) Co., Ltd., Guangzhou, 510630)

This article adopts the best method of lyapunov optimization to design a kind of resource allocation algorithm, theoretical analysis and simulation results show that this method is not only to increase the throughput of the system, but also achieved a good balance between throughput and latency.

down link; Dynamic resource allocation algorithm

10.3969/J.ISSN.1672-7274.2016.08.006

TN929.53 文獻(xiàn)標(biāo)示碼：A

1672-7274（2016）08-0023-04