刘永毓，刘婷婷

（1.中国移动通信集团广东有限公司，广州 510630；2.爱立信移动数据应用研究开发（广州 限公司，广州 510630）

LTE无线网络下行链路动态资源分配算法研究

刘永毓1，刘婷婷2

（1.中国移动通信集团广东有限公司，广州 510630；2.爱立信移动数据应用研究开发（广州 限公司，广州 510630）

本文采用李雅普诺夫最优化的方法设计了一种资源分配算法，理论分析和仿真结果表明，该方法不但提高了系统的吞吐量，同时还在在吞吐量和延迟之间实现了较好的均衡。

下行链路；动态资源分配算法

1 引言

无线资源是有限的，而用户的需求是无限的。由于无线信道的时变性，因此高效的调度算法对于提高系统的吞吐量和用户的稳定性具有重要的作用。从网络的角度来说，这种系统可以转换为一个多用户多服务器系统，每个服务器代表一个子信道。由于在每个时隙一个给定的服务器只能为一个用户服务，因此本文要解决的就是多个用户竞争一个给定的服务器的问题。系统模式如图1所示。

图1 用户间单个服务器竞争示意图

图1中，基站将要传输给每个用户的数据包都先存储在一个相应的缓存区队列中，图中Qi表示要发送给第i个用户的数据包存储队列，Ai(t)表示在时刻t到达队列i的数据包的个数，S表示给定的单个服务器。由于信道的衰落，每个队列和服务器之间的连接是随着时间而变化的，连接状态用一个二进制连接变量Ci(t)表示。最终要解决的问题就是当与服务器S处于连接状态的多个队列竞争服务器S时，到底要将服务器S分配给哪一个队列[2]。最终目标就是设计一个高效的资源分配算法不但要提高网络吞吐量，而且还要保证用户的服务质量。

在此队列模型中服务器的分配是可以控制的，网络控制者在做分配决定前知道队列的长度。在每个时隙可能根据对队列历史状态的观察和之前的分配情况来决定现在的分配，分配政策首先要使系统稳定，其次要最大限度的提高网络吞吐量，降低延迟，保证用户的服务质量。本文是用李雅普诺夫最优化的理论设计一种基于队列积压和延迟的动态资源分配算法，这种方法既维持了网络的稳定性，将队列积压降低到一个最小的阻塞状态，降低了延迟，又提高了吞吐量，而且在吞吐量和延迟之间设置了一个很好的均衡。

2 系统模型分析

2.1 系统模型描述

系统模型如图1所示，用Q(t)=(Q1(t),...,Qn(t))表示每个队列在时隙t的队列积压（数据包的个数），假设每个队每个队列的数据包的个数。假设A(t)独立同分布，且E{A(t)}=@(λ1, ..., λn)。用C(t)=(C1(t), C2(t),...C3(t))表示服务器S与队列连接的状态矩阵。在时隙t，若Ci(t)=1则表示队列Qi与服务器S处于连接状态（信道状态处于ON状态），若Ci(t)=0，则表示队列Qi与服务器S处于断开的状态（信道状态处于OFF状态）。用µi(t)表示在时隙t为用户i成功服务的数据包的个数，则队列的动态更新方程如下[3]：

要使整个系统稳定，则所有队列在时间平均的意义上必须满足以下条件：

2.2 时变的链路可靠性

假设服务器在每个时隙至多可以传输一个数据包，则µi(t)∈{0,1}。用x(t)=(x1(t),x2(t),..., x3(t))表示传输矩阵，xi(t)∈{0,1}，若xi(t)=1则表示服务器S在时隙t要对队列Qi进行传输，假设x(t)来自所有可允许的传输集合X，x(t)∈X。传输矩阵x(t)和服务器的状态矩阵C(t)联合决定每个时隙服务器成功分配的概率，用以下所示的可靠性函数表示：

可靠性函数Ψi(x(t)，C(t))∈[0,1]，表示在给定x(t)和C(t)时服务器S成功分配给队列Qi的概率。

在实际中，C(t)表示每个时隙信道估计的结果，这个估计可能不准确，因此用可靠性函数Ψi(x(t)，C(t))表示实际网络中信道可以为用户队列传输的概率。假设ACK/NACK信息在每个时隙末会反馈给每个用户队列，已告知传输是否成功，没有传输成功的数据包继续存储在缓存队列中。

则服务变量表示如下：

假设给定当前的预传输矩阵x(t)和服务器状态矩阵C(t)时，在当前时隙t成功传输与否与过去的状态无关。

2.3 最优化的目标函数

设计资源分配政策的最终目的就是使目标函数最优化，本文的目标函数如下所示：

式中，yi(t)为时隙t中用户i成功服务的数据包的个数。

定义为无线网络下行链路的网络容量区，定义为所有可获得吞吐量矩阵@(1,..., n)的闭集合。

3 最佳资源分配政策

李雅普诺夫最优化理论是随机网络最优化的一种数学方法，此优化方法可以防止对信道状况预测不准确而带来的限制，它只需观察每个时隙开始时刻的信道状况，不像传统的基于预测的算法需要对信道状况做长期的预测。这种方法充分考虑了队列模型的动态效果，充分利用了队列的积压信息来做各种调度控制决定。

3.1 算法设计思想

用Hi(t)表示在时隙t数据包到达队列Qi前端的等待时间，如果Qi在t时没有数据包，则定义Hi(t)=0。如果在t时一个数据包到达一个空的队列，规定在t+1时将其放置在队列前端。定义示性变量αi(t)，如果Qi(t)＞0，则αi(t)=1，反之为0。则数据包到达队列前端的等待时间Hi(t)的更新方程如下[4]：

式中，βi(t)=1-αi(t)；Ti(t)为队列前端的数据包和后继到达的数据包之间的时间间隔。可以这样理解：如果αi(t)=0，则βi(t)=1，则队列Qi此时为空，此时仅且当仅有一个数据包到达时Hi(t)=1。相反，如果αi(t)=1，

则βi(t)=0。由于队列前端数据包和后继到达数据包之间的间隔Ti(t)可能大于或等于Hi(t)+1，在这种情况下，定义t+1时刻队列为空，则此时Hi(t+1)=0。

定义(t)[Q(t); H(t)]，Q(t)和H(t)分别为方程（1）的值和方程（9）的值的矩阵，构建如下所示的李雅普诺夫函数：

将每个时隙所有队列的平方和定义为李雅普诺夫函数L(t)，如果L(t)很小，则所有的队列都很小，如果L(t)很大，则至少有一个队列很大。因此李雅普诺夫函数是用其来衡量网络阻塞的标量。

定义((t))为李雅普诺夫一步漂移，其表达式如下：

如果在每个时隙做控制决定，贪婪的最小化Δ(t)，这样可以将队列积压降低到一个最小的阻塞状态，直观的维持了网络的稳定性。

V是一个非负的系统控制参数，用于调节延迟和基于吞吐量的网络效用之间均衡。在每个时隙做控制决定贪婪的最小化漂移-效用函数的值，这样既维持了网络的稳定性，又提高了网络效用。

3.2 最佳资源分配算法

每个时隙t，观察Q(t)，H(t)和C(t)，按照下面的步骤做服务器的分配决定：

（1）选择一个传输矩阵x(t)解决以下最大化问题：

（2）队列更新：根据方程（1）和方程（12）更新队列。

4 算法性能分析

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

如果ε≥0，则所有的队列Θi(t)的均值稳定。如果ε＞0，则所有的队列都稳定。

对上式两边当t→∞取极限得（b）证毕。由式（12）得

由于|Θi(t)|≥0，则E{Θi(t)2}≥E{|Θi(t)|}2，则式两边同时除以t，并在t→∞取极限得。

定理2：假设所有的队列起初为空，令y*表示最佳的吞吐量的时间平均矩阵，则g(y*)=g*为最佳的网络效用，μ*(t)为最佳服务率，假设E{μ*(t)}=E{Ai(t)}=y*，系统控制参数V＞0。

由定理2可以看出，增大系统控制参数V可以使基于吞吐量的网络效用无限接近于最佳值，但是由定理1可以看出增大V值可以增大队列积压值，从而增大延迟，所以在延迟和吞吐量之间形成一个O(1/V,V)的均衡，因此本文提出的分配算法选择合适的系统参数V至关重要。

5 仿真分析

为验证本文所提算法的优越性能，我们使用吞吐量、延迟来评估系统系能，仿真工具为Matlab。仿真场景为50个用户的无线网络下行链路，调度间隔（slot）为1ms，在每个调度间隔数据包的平均到达率为0.5，信道处于on状态的概率为0.5。

我们首先将吞吐量和延迟视作V的函数，观察吞吐量和延迟与V的关系，V值变化范围为0到1000，仿真时间为1500ms。由图2可以看出随着V值的增大系统的平均吞吐量也不断增大并趋于饱和，同时系统的平均延迟，随着V值得增大线性增长，因此必须选择一个最佳的V值既使系统的吞吐量比较理想，同时又不会导致太大的延迟。由图2可知，选择V=120时，平均吞吐量等于0.397，平均延迟为105个slot，是一个很好的折中点。

图2 平均吞吐量及延迟与V的关系

其次，我们固定V值时，比较本文所提出的算法和随即分配算法吞吐量和延迟的性能，仿真时间为1000ms。随即分配算法就是将服务器随即分配给不为空的用户队列。图3将两种算法的吞吐量进行延迟，在仿真算法内本文提出的算法吞吐量比随机分配的算法高。图3给出两种算法的延迟的经验分布，可以看出本文算法和随机分派算法相比改善了延迟性能。

6 结束语

本文针对LTE无线网络下行链路系统用户间对一个服务器竞争的问题，根据李雅普诺夫最优化理论，设计了一种动态资源分配方法——基于队列积压和延迟。本文提出的算法不但能优化吞吐量，还能减少用户延迟，实现两者均衡。■

图3 吞吐量图

[1] 徐景，胡宏林，周婷．3GPPLTE标准化进展．中兴通信技术，2007, 13(2): 9-12

[2] 谭伟，张文新，马雨出．LTE的无线资源管理．邮电设计技术，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 文献标示码：A

1672-7274（2016）08-0023-04