车联网技术的应用非常广泛，包括交通信息共享与智能驾驶，以及娱乐内容共享等^[1].其中，车载终端的内容下载受到了广泛的关注，如车辆在运行过程中可以向服务器请求路况信息、娱乐信息等^[2].为了提升车载终端的下载速率，可以通过密集部署路侧基础设施(RSU, road side unit)拉近终端和接入点之间的距离^[3].然而，在RSU密集部署的场景中，相邻RSU干扰严重，车载终端运动速度快，传输速率会随着车辆的移动显著变化，因此，需要研究一种适应于该场景的内容下载调度算法.

针对车联网场景中的内容下载问题，彭军等^[4]提出了车辆间协作从RSU下载内容的方案，这种方式适用于RSU稀疏部署，车辆有可能处在覆盖范围之外的情况. Ding等^[5]提出了一种缓存方法，RSU预先缓存一些受欢迎的内容，这样可以减少内容下载时间，提高内容下载效率.

笔者考虑RSU密集部署的车联网场景中，车辆请求时延受限的内容传输方法，即车辆请求下载的内容有一个有效的期限^[6]，服务器需要在有效期内把内容传输给车辆，否则内容失效.最大速率优先算法总是调度当前信道条件最好的车辆^[7]，即优先调度数据速率最高的车辆，这种方法不适用于时延受限内容的下载.最早过期优先(EDD, earliest due date)算法优先调度最先过期的数据包，该机制不能最大化系统的吞吐量，因为有些数据包可能是以非常低的传输速率调度的^[8].综上所述，研究一种高效的时延受限的内容调度方法是非常重要的.

笔者依据李雅普诺夫优化方法，利用分组的等待时延建立李雅普诺夫方程，保证系统稳定，在满足时延限制需求的同时，进一步提升系统的吞吐量.

1 系统模型与问题描述 1.1 系统模型

在M个RSU密集部署的场景下，假设系统中共有V辆车随机请求下载内容，服务器为每辆车维持一个队列Q_v，因此系统中共有V个队列.令向量A(t)=(A₁(t), A₂(t), …, A_V(t))表示请求到达过程，即A_v(t)表示时隙t到达队列Q_v的分组数.假设A(t)是独立同分布的伯努利过程，其期望为E{A(t)}=λ，其中λ$ \buildrel \Delta \over = ({\lambda _1},{\lambda _2}, \cdots ,{\lambda _V})$表示请求到达率.假设分组大小固定且相等，每个时隙至多有一个分组到达，因此A_v(t)∈{0, 1}.令向量Q(t)=(Q₁(t), Q₂(t), …, Q_V(t))表示当前系统中每个队列中的分组数.所有的分组都标记有到达的时刻以便计算时延.队列更新方程为

$ {Q_v}\left( {t + 1} \right) = \max \left[ {{Q_v}\left( t \right) - {\mu _v}\left( t \right) - {D_v}\left( t \right),0} \right] + {A_v}\left( t \right) $

(1)

其中：${\mu _v}(t) = \sum\limits_{j = 1}^M {{\mu _{jv}}} $(t)为服务器在时隙t成功给车辆v传输的分组数，D_v(t)为丢弃的分组数.假设每个时隙，服务器最多丢一个分组，即D_v(t)∈{0, 1}.

令向量S_j(t)=(S_j1(t), S_j2(t), …, S_jV(t))表示t时刻RSU_j到所有车辆的传输速率，即S_jv(t)表示t时刻RSU_j可以成功为车辆v传输的分组数.令向量x_j(t)=(x_j1(t), x_j2(t), …, x_jV(t))表示RSU_j的调度动作向量，其中x_jv(t)∈{0, 1}，x_jv(t)=1表示RSU_j在t时隙给车辆v传输，如果限制每个RSU在同一时隙只能调度一辆车，那么向量x_j(t)中最多只有一个分量为1.令χ表示所有可行的x(t)的集合.因此，μ_v(t)可表示为

$ {\mu _v}\left( t \right) = \sum\limits_{j = 1}^M {{\mu _{jv}}\left( t \right) = \sum\limits_{j = 1}^M {{x_{jv}}\left( t \right){S_{jv}}\left( t \right)} } $

(2)

1.2 问题模型

目标是满足用户时延需求的同时，提升系统的吞吐量性能.定义向量Y(t)=(Y₁(t), Y₂(t), …, Y_V(t))表示系统的吞吐量，即Y_v(t)表示时隙t队列Q_v的吞吐量，定义为

${Y_v}(t) \buildrel \Delta \over = {\lambda _v} - {D_v}(t)$

(3)

定义变量y_v(t)表示Y_v(t)的时间均值，即${\bar y_v}(t) \buildrel \Delta \over = {\lambda _v} - \frac{1}{t}\sum\limits_{\tau = 0}^{t - 1} E \left\{ {D(\tau )} \right\}$，y_v表示y_v(t)在t趋于无穷大的极限值.在随机网络中，为了保证服务器调度的公平性，通常用对数函数表示系统的吞吐量性能^[9]，定义函数$g(Y) = \sum\limits_{v = 1}^V {\lg } (1 + {Y_v})$表示系统的吞吐量性能.在基于反馈的优化框架中，为系统引入一个辅助变量可以将问题转化为一个只和时间相关的问题，而不是和关于时间的函数相关的问题.由于函数g(Y)是一个非线性的连续凹函数，引入辅助向量γ=(γ₁, γ₂, …, γ_V)，其中－1≤γ_v≤1.定义变量γ_v(t)表示γ_v(t)的时间均值，γ_v表示γ_v(t)在t趋于无穷大的极限值.这样，系统吞吐量性能函数可以写成

$ g\left( {\bf{ \pmb{\mathsf{ γ}} }} \right) = \sum\limits_{v = 1}^V {\left( {1{\rm{g}}\left( {1 + \max \left[ {{\gamma _v},0} \right]} \right) + \min \left[ {{\gamma _v},0} \right]} \right)} $

(4)

目标是最大化系统吞吐量，同时要保证用户的时延需求，最优化问题可以表述为

$ \max :g\left( {\mathit{\boldsymbol{\bar \gamma }}} \right) $

(5)

$ {\rm{s}}.{\rm{t}}.{{\bar Q}_v} < \infty ,v \in \left\{ {1,2, \cdots ,V} \right\} $

(6)

$ {{\bar y}_v} \geqslant {{\bar \gamma }_{\rm{v}}},v \in \left\{ {1,2, \cdots ,V} \right\} $

(7)

$ - 1 \leqslant {\gamma _{\rm{v}}}\left( t \right) \leqslant 1,v \in \left\{ {1,2, \cdots ,V} \right\} $

(8)

$ \mathit{\boldsymbol{\bar Q}}和\mathit{\boldsymbol{\bar y}}\mathit{可确定} $

(9)

其中：向量Q={Q₁, Q₂, …, Q_V}表示系统队列平均长度，${\overline Q _v} \buildrel \Delta \over = \lim \;su{p_{t \to \infty }}\frac{1}{t}\sum\limits_{\tau = 0}^{t - 1} E \left\{ {{Q_v}(\tau )} \right\}$，如果随机离散时间系统稳定，则满足Q_v < ∞，即约束条件(6) 保证了系统稳定性，约束条件(8) 限制了γ=(γ₁, γ₂, …, γ_V)的取值，约束条件(9) 保证了系统吞吐量小于到达率.为了保证约束条件(7)，定义一个虚拟队列Z_v(t)^[10]，更新方程为

$ {Z_v}\left( {t + 1} \right) = \max \left[ {{Z_v}\left( t \right) - {\lambda _v} + {D_v}\left( t \right) + {\gamma _v}\left( t \right),0} \right] $

(10)

把Y_v(t)的定义式(3) 代入式(10)，并对τ∈{0, 1, …, t－1}累加求和再除以t可得

$ \frac{{{Z_v}\left( t \right) - {Z_v}\left( 0 \right)}}{t} + \frac{1}{t}\sum\limits_{\tau = 0}^{t - 1} {{Y_v}\left( \tau \right) \geqslant } \frac{1}{t}\sum\limits_{\tau = 0}^{t - 1} {{\gamma _v}\left( \tau \right)} $

(11)

对不等式(11) 两边求期望，且Z_v(0)=0，进一步可得

$ \frac{{E\left\{ {{Z_v}\left( t \right)} \right\}}}{t} + {{\bar y}_v}\left( t \right) \geqslant {{\bar \gamma }_{\rm{v}}}\left( t \right) $

(12)

由式(12) 可知，如果E{Z_v(t)}/t→0，即虚拟队列Z_v(t)稳定，则约束条件(7) 成立.

1.3 分组等待时延的计算

每个时隙，服务器首先决定调度变量，如果服务器决定调度队列Q_v，则Q_v中至少有一个分组被传输，如果队列Q_v没有被调度，再根据时延决定是否要丢包.

令H_v(t)表示时隙t队列Q_v队首分组的等待时延，如果队列Q_v为空，则H_v(t)=0.如果在时隙t，有一个分组到达空队Q_v，则该分组在t+1时隙才会变成队首分组，并设该分组的等待时延H_v(t+1)=1.定义指示变量α_v(t)，如果队列Q_v(t)不为空，则α_v(t)=1；否则α_v(t)=0，则时延H_v(t)可按式(13) 计算.

$ \begin{array}{*{20}{c}} {{H_v}\left( {t + 1} \right) = } \\ {{\alpha _v}\left( t \right)\max \left[ {{H_v}\left( t \right) + 1 - \left( {{\mu _v}\left( t \right) + } \right.} \right.} \\ {\left. {\left. {{D_v}\left( t \right)} \right){T_v}\left( t \right),0} \right] + \left( {1 - {\alpha _v}\left( t \right)} \right){A_v}\left( t \right)} \end{array} $

(13)

其中T_v(t)为连续2个分组到达的时间间隔.由式(13) 可知，当α_v(t)=0时，即队列Q_v为空，如果时隙t有分组到达，则H_v(t+1)=1.如果队首的分组既没有被传输也没有被丢弃，即μ_v(t)+D_v(t)=0，那么时延H_v(t)加1；否则，队首分组成功传输或者被丢弃，则后面的分组变成队首分组，时延为max[H_v(t)+1－(μ_v(t)+D_v(t))T_v(t), 0].

2 提出的调度算法 2.1 李雅普诺夫优化方法

根据李雅普诺夫优化方法可知，可以依据系统队列长度设计调度算法来保证系统的稳定性并最大化系统的吞吐量^[9].由式(13) 可知，对于所有的v∈{1, 2, …, V}，队列长度总是小于等于该队首分组的等待时延，即Q_v(t)≤H_v(t)成立，因此利用H(t)代替Q(t)设计调度方法来保证系统的稳定性，即保证H(t)有界，这样就可以满足时延要求，同时也保证了Q(t)有界，吞吐量最大.另外，为了满足约束条件(7)，需要保证虚拟队列Z(t)稳定.因此，定义Θ(t) [Z(t); H(t)]作为队列Z(t)和H(t)的联合向量，不失一般性，假设λ_v>0，定义李雅普诺夫方程为

$ L\left( {\mathit{\boldsymbol{ \boldsymbol{\varTheta} }}\left( t \right)} \right) = \frac{1}{2}\sum\limits_{v = 1}^V {Z_v^2} \left( t \right) + \frac{1}{2}\sum\limits_{v = 1}^V {{\lambda _v}} H_v^2\left( t \right) $

(14)

相应地，李雅普诺夫方程的偏移量Δ(Θ(t))可以表述为

$\Delta \left( {\mathit{\boldsymbol{ \boldsymbol{\varTheta} }}\left( t \right)} \right) = E\left\{ {L\left( {\mathit{\boldsymbol{ \boldsymbol{\varTheta} }}\left( {t + 1} \right)} \right) - L\left( {\mathit{\boldsymbol{ \boldsymbol{\varTheta} }}\left( t \right)} \right)\left| {\mathit{\boldsymbol{ \boldsymbol{\varTheta} }}\left( t \right)} \right.} \right\}$

(15)

根据李雅普诺夫优化方法中的偏移加罚模型^[10]，每个时隙，算法应最小化边界值：

$ \min \Delta \left( {\mathit{\boldsymbol{ \boldsymbol{\varTheta} }}\left( t \right)} \right) - {D_{\max }}E\left\{ {g\left( {\mathit{\boldsymbol{\gamma }}\left( t \right)} \right)\left| {\mathit{\boldsymbol{ \boldsymbol{\varTheta} }}\left( t \right)} \right.} \right\} $

(16)

其中：Δ(Θ(t))代表队列的稳定情况；g(γ(t))代表优化的目标，也就是系统吞吐量；D_max是一个非负权重，用来影响性能的折中，这里D_max是给定的，表示内容的最大时延要求，如果时延要求较小，则很多包会被丢弃，系统吞吐量下降，因此，该值的大小会影响系统性能.

根据李雅普诺夫方程的定义，可以得到下面2个定理，由于篇幅的限制，证明过程省略.

定理1 每个时隙t，对于任意的Θ(t)，采用任意一种调度算法，李雅普诺夫方程偏移量满足

$ \begin{array}{*{20}{c}} {\mathit{\boldsymbol{ \boldsymbol{\varDelta} }}\left( {\mathit{\boldsymbol{ \boldsymbol{\varTheta} }}\left( t \right)} \right) \leqslant B - \sum\limits_v {{Z_v}} \left( t \right)E\left\{ {{Y_v}\left( t \right) - } \right.} \\ {\left. {{\gamma _v}\left( t \right)\left| {\mathit{\boldsymbol{ \boldsymbol{\varTheta} }}\left( t \right)} \right.} \right\} - \sum\limits_v {{\lambda _v}} {H_v}E\left\{ {\left( {{\mu _v}\left( t \right) + } \right.} \right.} \\ {\left. {\left. {{D_v}\left( t \right)} \right){T_v}\left( t \right) - 1\left| {\mathit{\boldsymbol{ \boldsymbol{\varTheta} }}\left( t \right)} \right.} \right\}} \end{array} $

(17)

其中B为常数.

定理2 每个时隙t，对于任意的Θ(t)，采用任意一种调度算法，T_v(t)与D_v(t)、μ_v(t)和Θ(t)相互独立，可得

$ \begin{array}{*{20}{c}} {\mathit{\boldsymbol{ \boldsymbol{\varDelta} \boldsymbol{\varTheta} }}\left( t \right) - {D_{\max }}E\left\{ {g\left( {\mathit{\boldsymbol{\gamma }}\left( t \right)} \right)\left| {\mathit{\boldsymbol{ \boldsymbol{\varTheta} }}\left( t \right)} \right.} \right\} \leqslant } \\ {B - {D_{\max }}E\left\{ {g\left( {\mathit{\boldsymbol{\gamma }}\left( t \right)} \right)\left| {\mathit{\boldsymbol{ \boldsymbol{\varTheta} }}\left( t \right)} \right.} \right\} - } \\ {\sum\limits_v {{Z_v}\left( t \right)E\left\{ {{\lambda _v} - {D_v}\left( t \right) - {\gamma _v}\left( t \right)\left| {\mathit{\boldsymbol{ \boldsymbol{\varTheta} }}\left( t \right)} \right.} \right\} - } } \\ {\sum\limits_v {{H_v}\left( t \right)E\left\{ {{\mu _v}\left( t \right) + {D_v}\left( t \right) - {\lambda _v}\left| {\mathit{\boldsymbol{ \boldsymbol{\varTheta} }}\left( t \right)} \right.} \right\}} } \end{array} $

(18)

其中B的值与定理1相同.

因为假设请求到达A_v(t)是伯努利过程，所以到达间隔T_v(t)是均值为E{T_v(t)}=1/λ_v的几何过程.

2.2 算法步骤

本节给出算法的具体步骤.根据定理1和定理2，最小化目标变成式(18) 中不等号的右边项.

每个时隙t，服务器根据Z(t)、H(t)和S(t)的值，通过决策控制变量γ(t)、D(t)、x(t)来最小化式(18) 中不等号的右边项，整理式(18) 中包括控制变量的项可得

$ \begin{array}{*{20}{c}} {{D_{\max }}E\left\{ {g\left( {\mathit{\boldsymbol{\gamma }}\left( t \right)} \right)\left| {\mathit{\boldsymbol{ \boldsymbol{\varTheta} }}\left( t \right)} \right.} \right\} - } \\ {\sum\limits_{v = 1}^V {{Z_v}\left( t \right)E\left\{ {{D_v}\left( t \right) + {\gamma _v}\left( t \right)\left| {\mathit{\boldsymbol{ \boldsymbol{\varTheta} }}\left( t \right)} \right.} \right\}} + } \\ {\sum\limits_{v = 1}^V {{H_v}\left( t \right)E\left\{ {\left( {{\mu _v}\left( t \right) + {D_v}\left( t \right)} \right)\left| {\mathit{\boldsymbol{ \boldsymbol{\varTheta} }}\left( t \right)} \right.} \right\}} } \end{array} $

(19)

1) 选择辅助变量：γ(t)={γ₁(t), γ₂(t), …, γ_V(t)}，每个时隙根据Θ(t)的值，通过求解下列问题，可得γ(t).

$ \max :{D_{\max }}g\left( {\gamma \left( t \right)} \right) - \sum\limits_{v = 1}^V {{Z_v}\left( t \right)} {\gamma _v}\left( t \right) $

(20)

$ {\rm{s}}{\rm{.t}}. - 1 \leqslant {\gamma _v}\left( t \right) \leqslant 1,v \in \left\{ {1,2, \cdots ,V} \right\} $

(21)

变量γ(t)的值影响队列Z(t)的更新，从而影响D(t)的值.

2) 选择传输变量：现在考虑服务器如何为RSU_j选择传输动作向量x_j(t)=(x_j1(t), x_j2(t), …, x_jV(t))，其中变量x_jv(t)∈{0, 1}，重新整理式(19) 中的剩余项可得

$ \begin{array}{*{20}{c}} {\sum\limits_{v = 1}^V {{H_v}\left( t \right)E\left\{ {{\mu _v}\left( t \right)\left| {\mathit{\boldsymbol{ \boldsymbol{\varTheta} }}\left( t \right)} \right.} \right\}} + } \\ {\sum\limits_{v = 1}^V {\left( {{H_v}\left( t \right) - {Z_v}\left( t \right)} \right)E\left\{ {{D_v}\left( t \right)\left| {\mathit{\boldsymbol{ \boldsymbol{\varTheta} }}\left( t \right)} \right.} \right\}} } \end{array} $

(22)

定义一个标志变量m_v(t)，当H_v(t)≥Z_v(t)时，m_v(t)=1；否则m_v(t)=0.假设如果服务器调度了队列Q_v，则至少可成功传输一个分组，服务器就不会再丢包，因此，如果服务器没有调度队列Q_v，且m_v(t)=1时，则D_v(t)=1，再由式(2) 可知，${\mu _v}(t) = \sum\limits_{j = 1}^M {{x_{jv}}} (t){S_{jv}}(t)$，因此，式(22) 可以改写成(简便起见，先不写条件期望)

$ \begin{array}{*{20}{c}} {\sum\limits_{v = 1}^V {{H_v}\left( t \right){\mu _v}\left( t \right) + \sum\limits_{v = 1}^V {\left( {{H_v}\left( t \right) - {Z_v}\left( t \right)} \right){D_v}\left( t \right)} } = } \\ {\sum\limits_{v = 1}^V {{H_v}\left( t \right)\sum\limits_{j = 1}^M {{x_{jv}}\left( t \right){S_{jv}}\left( t \right) + \sum\limits_{v = 1}^V {{D_v}\left( t \right)\left( {{H_v}\left( t \right) - } \right.} } } } \\ {\left. {{Z_v}\left( t \right)} \right)\left( {1 - \sum\limits_{j = 1}^M {{x_{jv}}\left( t \right)} } \right){m_v}\left( t \right)} \end{array} $

(23)

整理式(23)，只考虑包含控制变量的项，可得

$ \begin{array}{*{20}{c}} {\max :\sum\limits_{v = 1}^V {{H_v}\left( t \right)\sum\limits_{j = 1}^M {{x_{jv}}} \left( t \right){S_{jv}}\left( t \right)} - }\\ {\sum\limits_{v = 1}^V {{m_v}\left( t \right)\left( {{H_v}\left( t \right) - {Z_v}\left( t \right)} \right)} \sum\limits_{j = 1}^M {{x_{jv}}\left( t \right)} } \end{array} $

(24)

$ {\rm{s}}{\rm{.t}}{\rm{.}}\;\;\;\;\;\;\mathit{\boldsymbol{x}}\left( t \right) \in \mathit{\boldsymbol{\chi }} $

(25)

根据S(t)和Θ(t)的值最大化式(24) 求x(t).

3) 丢包决策：如果队列Q_v的队首分组没有被调度，且满足Z_v(t)≤H_v(t)，则丢掉队首分组，即D_v(t)=1.

求出变量γ(t)后，要最大化表达式：

$ \sum\limits_v {{H_v}\left( t \right){\mu _v}\left( t \right)} + \sum\limits_v {\left( {{H_v}\left( t \right) - {Z_v}\left( t \right)} \right)} {D_v}\left( t \right) $

因此当Z_v(t)≤H_v(t)时，应令D_v(t)=1，即队列Q_v丢包.

4) 队列更新：利用上述过程给出的控制变量γ_v(t)和D_v(t)的值更新虚拟队列Z_v(t).同时，根据队首分组是否传输成功，更新队列Q_v(t)和队首分组的时延H_v(t).

2.3 时延分析

根据算法步骤1) 求解变量γ_v(t)时，如果满足Z_v(t)>D_max，则γ_v(t)=－1，由于D_v(t)≤1，所以此时γ_v(t)+D_v(t)≤0，根据Z_v(t)的更新公式(10)，Z_v(t+1)≤D_max，即该算法可以保证Z_v(t)有上界.

下面分析提出的算法可以满足时延需求.对于任意队列Q_v(t)，首先在t=0时，队列为空，时延H_v(t)=0.然后，假设时隙t，时延满足H_v(t)≤D_max－1，由时延更新公式(13) 可知，从时隙t到t+1最多增加1，所以，H_v(t+1)≤D_max；反之，如果H_v(t)>D_max－1，因为时延H_v(t)是整数，则H_v(t)=D_max，又因为Z_v(t)≤D_max，所以此时H_v(t)≥Z_v(t)成立，如果服务器没有调度队列Q_v(t)，根据算法步骤3) 丢包决策可得D_v(t)=1，此时Q_v(t)的队首分组会被丢弃.因此，该算法可以保证时延的上界是D_max.

3 仿真 3.1 仿真参数设置

在仿真中首先使用VISSIM软件模拟车辆的运行过程^[11]，记录每个时隙车辆的位置信息.考虑直线型的高速场景，公路长度设为1 km.车辆由两端入口进入，到达过程服从泊松分布，达到率θ设为300车/h/入口.另外，车速在90~120 km/h之间变化. RSU密集部署，间距200 m，假设系统中共有3辆车.车辆的请求过程相互独立，服从参数为λ_v的伯努利分布.其他参数如表 1所示.

根据式(3) 给出的吞吐量的定义，在仿真中，通过统计车辆请求的包数和被丢弃的包数可以确定系统的平均吞吐率.

3.2 仿真结果与分析

图 1所示为基于提出的算法和EDD算法下，系统吞吐量和请求到达率的关系.结果表明，当平均到达率小于0.3时，2种算法的吞吐量性能一样，都是最优的；当到达率大于0.3时，提出的算法性能优于EDD算法.

图 2所示为基于提出的算法和EDD算法下平均等待时延和请求到达率的关系，其中D_max是给定的时延要求. 图 2结果表明，采用提出的算法平均等待时延小于采用EDD算法的时延，当到达率较大时，即系统负荷重时，提出的算法仍然可以保证时延满足要求，而EDD算法的时延不满足要求.

图 3所示为基于提出的算法和EDD算法下系统丢包率和时延的关系.当D_max值较小时，采用2种算法系统的丢包率都很高，但是提出的算法明显优于EDD算法；当时延D_max增大时，丢包率明显下降；当时延很大时，丢包率的变化不再明显，因为所有数据包都有足够的时间可以被调度.

4 结束语

提出了在密集部署RSU的车联网场景下，时延受限内容传输调度算法，利用分组的等待时延建立李雅普诺夫方程，保证系统稳定，最大化吞吐量的同时保证分组等待时延有界.仿真结果表明，相比于现有的算法，提出的算法可以保证时延需求，进一步提升了系统吞吐量性能.