Exploiting Mobility in Proportional Fair Cellular Scheduling Measurements and Algorithms

摘要

比例公平（PF）调度算法是蜂窝网络中的事实标准。它们利用用户的信道状态多样性（由快速衰减引起），对于平稳的信道状态分布和无限的时间视野是最优的。然而，移动用户的信道是非平稳的，这是由于慢衰减（秒级）造成的，并且与基站在短时间内相关联。因此，我们开发了利用移动性的预测有限视界PF调度($(PF{)}^{2}S$)框架。我们提供了来自3G网络的广泛信道测量结果，并表征了由移动性引起的信道状态趋势。我们发现用户的信道状态具有高度可重复性，并利用这一点开发了数据速率预测机制。然后，我们提出了一些利用预测机制的信道分配估计算法。我们的基于跟踪的模拟考虑了由预测和信道分配估计算法组合而成的$(PF{)}^{2}S$框架实例。它们表明该框架可以将吞吐量提高15%到55%，与传统的PF调度器相比，同时提高了公平性。

1. 引言

3G和4G（LTE）蜂窝网络集成了机会调度器[11]。这些调度器利用快速衰落导致的信道状态变化以及多用户分集，为具有良好信道条件的用户分配资源。比例公平（PF）调度算法是蜂窝网络中机会调度器的实际标准[16]。它们旨在提供高吞吐量，同时保持用户之间的公平性。过去已经对PF调度算法进行了广泛的研究（例如[6]、[10]、[18]）。这些算法在以下假设下是最佳的：无线信道状态是一个平稳过程（即它只受到快速衰落的影响），并且用户的关联时间很长（例如静态用户或行人）[20]、[28]。然而，当这些假设不成立时（对于移动用户来说就是这种情况），这些算法的性能就不再是最优的[5]。

图1说明了一辆汽车在一条5公里路上的轨迹以及与3个不同扇区之间的信号质量$(E_c/I_o)$，（我们是在这条路上3次驾驶过程中收集的$E_c/I_o$值）。可以看出，信道具有一个占主导地位的慢衰落分量，其上叠加了一个快速衰落分量。由于$E_c/I_o$在几秒钟内具有明显的趋势，因此信道状态分布是非平稳的。另外，沿着路径的运动会导致扇区之间的切换，因此关联周期很短。

图1. 移动用户沿3个蜂窝扇区道路的轨迹：（a）地图轮廓和与蜂窝网络的交互以及（b）在3次不同驾驶期间测量的信道质量（$E_c/I_o$）值。

例如，图1说明了汽车沿5km路径的轨迹和3个不同扇区(在路径上的3次驾驶期间收集了$E_c/I_o$值)的信号质量($E_c/I_o$)。可以看出，信道具有占主导地位的慢衰落分量，其上叠加了快速衰落分量。由于$E_c/I_o$在几秒钟内具有明显的趋势，因此信道状态分布是非平稳的。此外，沿着路径的运动会引发扇区之间的切换，因此关联期很短。

由于PF调度器并未针对移动性进行优化，我们设计了预测有限视距PF调度$（PF{）}^{2}S$框架，该框架是针对移动节点定制的，同时利用慢衰落和快衰落。它包括三个组件：（i）数据速率预测，（ii）未来信道分配的估计，（iii）慢衰落感知调度。

为了描述慢衰落现象，为速率预测机制的设计提供输入，并获取用于评估框架和算法的跟踪信息，我们进行了广泛的测量活动。特别是，我们讨论了从3G网络收集的细粒度（即毫秒级分辨率）测量数据。具体来说，我们在长达810公里的行驶过程中以及在超过1300分钟的测量期间内，测量了无线信道属性。与之前的一些研究（例如[27]）不同，它们测量的是接收信号强度指示器（RSSI），即频率带内接收的总功率，我们测量的是每个扇区的信号质量（$E_c/I_o$）。这使我们能够获得重要的见解，因为$E_c/I_o$是用户数据速率的最为相关的预测因素

我们分析了这些轨迹并发现移动用户的体验明显变差。然而，这种变差的趋势不能简单地归因于视距指标，因此，开发简单的信道状态预测是不可行的。但是，对于相同路径上的多个驱动器，$E_c/I_o$的慢衰减分量具有很好的可重复性（例如，图1(b)），这使得数据驱动的预测方法变得可行。

基于以上观察结果，我们开发了一个两阶段的速率预测机制（称为覆盖图预测机制CMPM）。在离线阶段，处理测量轨迹以构建信道质量图。在线阶段由扇区执行，包括确定用户的位置和速度，从而预测数据速率。定位可以通过查询用户的GPS简单完成。然而，由于这会给用户带来能量和计算负担，我们还设计了通道历史定位方案CHLS，该方案需要一些关于用户轨迹的知识。CHLS使用变体的动态时间规整（DTW）算法（最初是为语音识别开发的[24]）。

$(PF{)}^{2}S$框架还需要能够基于速率预测结果估计未来信道分配的算法。我们提出了三种启发式算法，它们对预测误差的鲁棒性和对相对准确预测的性能水平各有不同。使用从收集的跟踪数据生成的测试用例，我们对$(PF{)}^{2}S$框架进行了广泛的模拟评估。我们考虑了9个框架实例，它们代表了速率预测机制和信道分配估计算法的不同组合。我们发现各种框架实例始终优于PF调度程序。具体来说，在现实移动场景中，吞吐量提高范围为15%到55%（同时保持或提高了公平性水平）。最后，我们研究了框架和算法对各种网络参数和假设（包括用户数量和延迟约束）的敏感度。

本文的主要贡献有三点：一是通过广泛的测量活动证明，移动用户经历了可重复但非平稳的慢衰落信道；二是提供了一个针对移动用户的蜂窝调度框架（和相应的算法）；三是通过基于跟踪的模拟表明，该框架可以显著提高性能。

本文的结构如下：第二节讨论相关工作，第三节回顾信道状态指标并阐明问题。 第四节介绍调度框架。 第五节讨论慢衰落的测量和特征。 第六节介绍速率预测机制，第七节介绍估计未来信道分配的算法。 第八节对框架和算法进行了评估。 第九节我们得出结论并讨论未来的工作。

2. 相关工作

机会调度：如前所述，机会和PF调度已经得到了广泛的研究(例如，[6]，[11]，[18]，[20]，[28])。使用快速衰落信道状态预测的PF调度算法出现在[7]，[14]中。在[3]，[10]，[27]中考虑了移动用户的调度，其中[3]，[10]中的基本假设是用户的移动模式导致一个平稳(和已知)的慢衰落信道。 [27]中的算法使用基于RSSI的预测方法在几分钟的时间尺度上调度单个用户。另一方面，我们使用基于Ec/Io的预测机制在更精细的时间尺度(几十秒)上解决多用户调度问题。

信道测量与预测：几十年来，无线信道测量研究一直在进行中[4]，[15]。最近，[21]研究了应用程序与1x-EVDO网络物理层属性之间的相互作用（使用的是我们测量工具的前身）。在受控环境中，对慢衰落进行了研究[29]。非平稳无线信道状态的短期（数毫秒）预测方法出现在[22]中。在[30]，[31]中的测量主要关注3G网络中实现带宽的可重复性。与之前的工作不同，我们对3G网络中的无线信道质量进行了测量，以表征和预测数秒内的慢衰落模式。

定位和移动预测：蜂窝网络中的定位包括利用时间到达、时间差到达、到达角度、小区ID和接收信号强度等方法（参见[17]及其参考文献）。利用模式跟踪和学习算法的移动预测方案在[19]中进行了综述。 [12]中的方法使用DTW算法，尽管是用于速度估计。最相关的作品是[17]，[27]，它们利用GSM网络中的RSSI通过指纹识别定位用户。另一方面，我们的方案使用多个信道属性（即，$E_c/I_o$和RSSI）以及最近的历史记录，并通过基于跟踪的模拟进行评估。

3. 模型和问题公式

在本节中，我们将回顾3G网络中的信道状态估计过程，并阐述调度问题。

A. 3G网络中的信道状态

在3G网络中，每个基站覆盖一个小区，该小区被分成（通常是3个）扇区。如图1(a)所示，出于数据调度和切换的目的，用户估计每个附近扇区的无线信道质量。它是估计一个扇区特定导频信号的功率与带内总功率（包括干扰和噪声）的比率，并由$E_c/I_o$表示。在第五部分中，我们将在我们的测量研究中考虑这些值。

用户与最强邻近扇区（称为服务扇区）进行关联（连接），并在该扇区分配专用缓冲区。当服务扇区的$E_c/I_o$值低于阈值（例如，由于移动性）时，用户将进行切换操作，与该服务扇区断关联，并与具有更高$E_c/I_o$值的新扇区建立连接。

扇区到用户的下行信道是时分的。我们将用$E_c/I_o[j]$表示第j时隙的值。用户定期向扇区报告其信噪比($E_c/I_o$)。然后，选择适当的通道化码并将其映射到可行的数据速率。第j时隙中第i个用户的可行数据速率记为$r_{ij}$。扇区中实现的机会调度器利用多用户数据速率的多样性来为用户分配下行时隙（参见图1(a)）。

B. 调度问题定义

常见的3G调度器解决了比例公平（PF）调度问题[16]，[18]，旨在实现高整体吞吐量的同时保持用户之间的公平性。关于恒定信道和长关联时间的常见假设在移动场景中并不成立（将在第五部分中说明）。因此，我们将下行链路调度问题表述为PF调度问题的变体，同时利用类似于[5]的公式（研究对抗信道）。与以前的工作不同（例如[10]，[20]，[28]），我们没有对信道状态分布做出假设，而是在有限的时间跨度内进行优化。

我们假设一个扇区有K个相关用户，且下行缓冲队列有未处理的数据。用${\alpha }_{ij}$表示调度器分配（如果用户i被分配到第j个时隙，则${\alpha }_{ij}$=1，否则${\alpha }_{ij}$=0）。我们用 R = { r i j } K × T R = \{r_{ij}\}_{K×T} R={rij​}K×T​和 α = { α i j } K × T α = \{α_{ij}\}_{K×T} α={αij​}K×T​分别表示可行的数据速率和调度器分配矩阵。相关术语可以在表1中找到。我们假设一个有限的时间跨度T时隙，对应于用户的关联时间。在第T个时隙结束时，用户i获得累计服务${\sum }_{j=1}^T{\alpha }_{ij}{r}_{i,j}$。因此，我们制定了以下问题，其目标是最大化比例公平成本函数。

有限视野比例公平调度:

即使知道R的全部信息，此问题也是NP难问题(证明见附录B)。在实践中，此问题必须以在线方式解决。用户是根据历史知识按插槽逐个安排的，而无需完全了解R。虽然FPF调度问题的目标是最大化比例公平度量(1)，但在评估框架(第VIII节)时，我们还考虑以下度量。

定义1（吞吐量）：所有用户分配的平均数据速率，记作${\sum }_{i=1}^K{\sum }_{j=1}^T{\alpha }_{ij}{r}_{i,j}/T$，称为吞吐量。

定义2（延迟）：用户i在连续的时间插槽中没有接收分配的数量称为延迟，用$d_i$表示。如果$d_i\ge D_{starved}$，则用户i被视为饥饿，其中$D_{starved}$是延迟阈值。

我们注意到，在第八章节中，时间范围有时以秒为单位进行考虑，并用 $\tilde{T}$ 表示。

4. 预测FPF调度$（PF{）}^{2}S$框架

在本节中，我们将回顾广泛部署的PF调度算法，并介绍一种在线调度框架，用于解决FPF调度问题，该问题由两个组件组成：(i)数据速率预测和(ii)未来信道分配的估计。这些组件的设计将分别在第6节和第7节中介绍。我们首先描述了在3G网络中部署的PF调度程序，该程序将在后面的章节中用作基准。

定义3（PF-EXP）：将满足${\alpha }_{i\ast j}=1$，其中$i\ast =argma{x}_{i\in K}{r}_{ij}/R_i[j]$，且$R_i[j]=(1-ϵ)R_i[j-1]+ϵ{\alpha }_{ij}{r}_{ij}$的调度器称为PF-EXP。

在PF-EXP调度器的定义中，$ϵ$决定吞吐量和延迟之间的折衷。具有较大的$ϵ$（≈1）值，调度器更重视用户当前可行的速率，从而提高吞吐量，但会牺牲延迟性能。具有较小的$ϵ$（≈0）值时，用户的分配历史具有更大的权重，因此，延迟性能得到改善，但会牺牲吞吐量。当无线信道状态是一个平稳过程并且用户具有较长的关联时间（即T→∞）时，PF-EXP调度器接近于最优比例公平性[20]、[28]。

我们的预测FPF调度$(PF{)}^{2}S$框架采用了类似于PF-EXP调度器的分时分配方法，它利用梯度上升法[9]来最大化目标函数(1)。在每个时间槽中，信道将分配给对应于目标函数最大增加量的用户。暂时放宽(3)中的整数约束，用户i在时间槽j的梯度为：

计算上述梯度需要知道整个数据速率矩阵R，对于只了解过去的在线算法来说是不可行的。因此，式(4)的分母被分成三个部分(从左到右):过去、现在和未来。从在线调度器的角度来看，前两个组件在任何时间槽中都是已知的。为了实现逐时隙调度，式(4)的未来部分作为$(PF{)}^{2}S$框架的一部分进行计算，这在上面的伪代码中进行了描述。

未来信道分配$（{\alpha }_{ij}）$ 由 ${\hat{r}}_{ij}$和${\hat{\alpha }}_{ij}$表示， 分别用$\hat{R}$和$\hat{\alpha }$表示矩阵表示。 在0时刻,$\hat{R}和\hat{\alpha }$ 的预测值是对整个视界（下一个T槽）预先计算的。这些矩阵可以生成 使用第六节和第七节中描述的方法，但 框架可以支持其他方法。对于每个用户i，在每个 计算与（4）对应的排名$M_{ij}$，即槽j 使用$\hat{R}$和$\hat{\alpha }$。选择排名最高的用户。

对于恒定信道，未来信道统计信息包含在分母的过去分量中（4）。因此，仅依赖过去信息的算法（即PF-EXP）是最优的。然而，对于非恒定信道分布，情况并非如此。因此，与PF-EXP不同，该框架中的第4步考虑了未来信道分量。通过纳入预测的未来，(PF)2S框架可以利用慢衰落趋势。此外，通过逐时隙决策，该框架还可以利用快衰落成分，类似于PF-EXP。

由于$(PF{)}^{2}S$框架旨在安排在慢衰落峰期(可能每几秒钟发生一次)期间的用户，因此必须确保这不会导致长时间的延迟。因此，在每个时隙中，该框架首先考虑等待时间超过Dstarved(在定义2中定义)的饥饿用户集，并选择一个。如果没有用户饥饿，它会在所有用户中选择。这样，该框架可以处理延迟约束。请注意，可以通过设置Dstarved = ∞来忽略延迟考虑。

5. 慢衰减测量

我们现在描述从3G网络收集的测量值。我们的分析表明，移动用户经历了明显和可重复的慢衰减。关于可重复性的观察为数据速率预测（R^）机制的设计提供了见解（第6节）。

图2.测量装置和测量收集的路线（参见表II）。

A. 测量设置与测试驱动

测量活动使用三星Galaxy S II (GSII) Skyrocket手机[26]进行，采用图2所示的设置。手机通过USB连接到运行高通可扩展诊断监视器(QXDM)软件的笔记本电脑。QXDM实时查询手机，并捕获各种物理层属性（下面描述）以及GPS位置和速度报告。QXDM每20毫秒记录一次这些测量，捕获快速衰减和慢衰减组件。

对于移动测量，设备被放置在汽车中，汽车行驶了4条不同的路线（参见表II），这些路线既包括高速公路，也包括郊区道路。每条路线都遵循给定的路线的全程，并且进行了多次驾驶。为了进行对照，我们也进行了静态（非移动）设备的测量。在测量期间，持续下载以确保网络连接的持续性。总之，我们在810公里的行程中测量了无线信道属性，测量时间超过1300分钟。

B. 通道状态指标与动态

QXDM存储三个物理层属性：带内总功率（包括干扰和噪声），称为RSSI，接收导频功率（RSCP）以及导频功率与总干扰之比（$E_c/I_o$）。11 这些关键属性表征信道质量，并由用户定期报告给服务部门[16]。后两者是每个相邻扇区导频信道的特定值，而前一个（RSSI）则不是。此外，虽然RSSI通常记录在以前的工作中并被使用（例如[27]），但从调度角度来看，$E_c/I_o$是用户信道质量最相关的指标[16]。

我们通过一个例子来说明慢衰落现象。图3(a)显示了所有路线上27个驱动器用户关联时间的直方图，表明关联时间大约为几十秒。作为一个具体的例子，图3(b)显示了沿着R4路线的单个驱动器部分测量到的RSSI和服务的扇区$E_c/I_o$的轨迹。显然，RSSI并不总是反映与$E_c/I_o$相同的趋势。此外，$E_c/I_o$经历了数秒的慢衰落。由于在大多数情况下，用户的关联时间是几十秒，因此慢衰落的峰值和谷值都发生在每个扇区。因此，接下来的两个子部分主要关注被$(PF{)}^{2}S$框架所利用的$E_c/I_o$慢衰落趋势。

图3.（a）沿路线R1-R4的27个驱动器的扇区关联时间分布（b）路线R4部分驱动器的RSSI和扇区服务$E_c/I_o$的测量值（垂直柱表示切换）。

图4. $E_c/I_o$（测量值）、$E_c/I_o^{\ast }$（标准化值）和$\widetilde{E_c/I_o^{\ast }}$（平滑值）的比较：（a）来自R4路线的移动轨迹和（b）静态轨迹。

C. 慢衰落与移动性

我们首先证明慢衰落现象与用户移动性密切相关。然后，我们描述了慢衰落和移动性指标之间的相关性，并表明（与过去工作的假设相反，例如[3]）慢衰落趋势不能与简单的视线指标联系起来。

为了量化用户在T时隙的$E_c/I_o$轨迹中的慢衰减，我们定义了如下慢衰减度量。首先，减去均值并对轨迹进行归一化处理以获得：

该操作不会影响$E_c/I_o$的趋势，但会去除可因扇区而变的幅值，从而能够比较不同扇区的$E_c/I_o$轨迹。然后，通过使用小波变换对$E_c/I_o^{\ast }$进行平滑处理，以去除快速衰减的成分（频率大于 1Hz）。$E_c/I_o^{\ast }$的平滑版本记作$\widetilde{E_c/I_o^{\ast }}$ （有关平滑操作的更多细节请参阅附录 C）。图 4 为移动用户和静态用户的$E_c/I_o^{\ast }$示例。使用 $\widetilde{E_c/I_o^{\ast }}$ 和$E_c/I_o$可以清楚地说明观察期间$E_c/I_o$值的趋势（存在或不存在）。

我们计算了从每个服务扇区收集的每个$E_c/I_o$轨迹的S值（参见表II）。图5（a）显示了静态轨迹和R1-R4路由的慢衰减度量值的累积分布函数（CDF）。移动路由的慢衰减度量值要大得多，经验上证实了S能够准确地将具有慢衰减的移动轨迹与不移动的轨迹区分开。

早期的研究假设慢衰落与视距参数（即距离或速度）之间存在很强的相关性[3]，[11]，从而支持对信道质量的函数预测。然而，我们的分析表明慢衰落(S)与视距指标之间的相关性较弱。例如，图5(b)和图5( c)分别显示了S与用户平均速度或行驶距离的散点图。S与速度或距离的相关系数分别为0.18和0.25。相反，慢衰落受到诸如切换、景观和运动引起的阴影等因素的控制，即使在受控场景中，这些因素也很难进行建模[29]。

图5.慢衰减的特征：(a)移动和静态轨迹的慢衰减度量(S)的CDF；(b)-( c)所有移动轨迹的平均速度或连接扇区时的行驶距离与S的散点图。

D. 慢衰减可重复性

如上所述，慢衰落趋势与视距因素没有直接关系，因此简单的功能预测是不可行的。然而，$E_c/I_o$的慢衰落分量具有非常高的可重复性，使得数据驱动的预测方法成为可能。具体来说，我们观察到来自多次测量(来自不同的驱动器)的$E_c/I_o$是可以预测的，误差为1-3dB(类似的结果出现在[27]中，对于RSSI)。为了说明可重复性，我们将路线R4的一部分分成25m的段，并在图1(b)中显示了穿过3个扇区的一部分段观察到的3个驱动器的$E_c/I_o$。曲线的重叠表明所有驱动器之间的相似性。

我们通过计算每个路线的所有驱动器的$E_c/I_o$交叉相关来加强这一观察结果，如下所示。每个路线被分成25米的段，然后该路线上的每个驱动器都由$E_c/I_o$值的向量表示，每个向量对应一个段（例如，如果路线包括n个段，则每个驱动器由长度为n的向量表示，同一段中的多个观察值由它们的平均值表示）。然后我们计算所有向量（驱动器）的相关系数。图6（b）（c）（d）显示了路线 R1、R3 和 R4 上所有驱动器之间的相关性。相关系数在0.9-0.98之间，表明相关性非常高。所有重复驱动器之间的高相关性意味着带有位置标签的历史$E_c/I_o$测量值可用于准确预测未来的慢衰落。

图6.测量得出的$E_c/I_o$值的可重复性：（a）通过R1线路上一个扇区的7个驱动器的测量值（以25m为间隔进行对齐）；（b）(d)R1、R3和R4线路上所有具有足够数据的驱动器之间的$E_c/I_o$相关系数。

6. 可行数据率预测（$\hat{R}$）

$(PF{)}^{2}S$框架需要一种机制来预测用户在T个时隙中的可行数据速率（$\hat{R}$）。我们基于对$E_c/I_o$的慢衰减分量的高度可重复性的观察，设计了一种机制，并将其称为覆盖图预测机制（CMPM）。在离线阶段，处理测量跟踪以构建地理覆盖图。在线阶段由扇区执行，并由两个步骤组成。首先，确定用户的位置和速度。然后，将此信息与覆盖图结合使用来预测用户i的可行速率${\hat{r}}_{ij}，\forall 1\le j\le T$。

第一步可以通过查询用户的GPS来实现。然而，由于这会给用户带来能量和计算负担，我们还开发了通道历史本地化方案(CHLS)。该方案假设已知用户整体轨迹。在第八部分中，我们使用两种替代方案对框架进行了评估。

A. 覆盖图构建

覆盖图是通过离线方式（针对每条路线一次）构建的，将格子放置在地理平面上，并将其划分为正方形部分（参见图7）。在所有格子中，用户所在格子表示为b，被一组扇区覆盖，居住在该部分的用户可以与之关联，表示为$U_b$。蜂窝运营商通常测量主要路线的信道质量。这些测量可以用于计算每个部分b的平均RSSI值以及每个相邻扇区$u\in U_b$的平均$E_c/I_o$和RSCP值。这些分别表示为$\overline{RSSI<b>}$，$\overline{E_c/I_{o_u}<b>}$，$\overline{RSC{P}_u<b>}$。为了计算这些值进行评估，每个样本测量都带有GPS位置标记，并绑定到适当的部分。

图7 CHLS的示意图：覆盖图段从1开始标记（在时隙1，用户位于段1）。在当前的时隙（$T_p$），用户位于Bcell和Bmax之间的一个段中，这些段落在服务扇区的覆盖区域内。

B. 通道历史定位方案（CHLS）

CMPM在线阶段的第一个步骤是将用户定位到覆盖图上。为了在没有GPS的情况下实现这一点，我们设计了CHLS。它基于信道度量值之间的差异，将用户的历史信道质量与用户轨迹上的覆盖图段进行匹配。然后，将用户的位置估计为其当前信道质量值所配对的段。将信道质量历史（即时间序列）与段（即位置）进行匹配取决于用户的速度，而这是可以改变的。因此，我们利用动态时间扭曲（DTW）算法13来“解开”用户的历史信道质量，以最好地适应覆盖图。

CHLS需要用户轨迹和用户在最近历史时间槽中的位置知识。用户的历时信道测量是可用的，无需额外费用，因为它们会定期报告给网络以进行调度和切换。

下文描述该方案的符号定义如下（参见图7）。该扇区保存用户过去$T_p$个时隙的$E_c/I_{o_u}[j]$，$RSC{P}_u[j]$和$RSSI[j]$的历史记录，这些时隙按顺序从1到$T_p$编号（当前时隙）。覆盖图段按顺序编号，从用户在时隙1的估计位置所在的段开始。这些段的编号不超过$Bmax$，即在该扇区覆盖范围内用户可能居住的最远部分。服务扇区覆盖了一系列范围为 B = { b ： B c e l l ≤ b ≤ B m a x } B=\{b：B_{cell}≤b≤B_{max} \} B={b：Bcell​≤b≤Bmax​}的段。

DTW算法应用于确定选择B中每个b作为用户位置估计的成本。它构建了一个大小为$B_{max}\times T_p$的矩阵H。条目$h_{b,j}$的值表示将1到j的时间槽与1到b的段配对的最低成本。约束条件是段1与槽1配对，段b与槽j（例如，端点配对）配对。第一行和第一列中的条目是$h_{1,j}和h_{b,1}=\infty ，\forall b,j$，而其余矩阵使用公式$h_{b,j}=c(b,j)+min(h_{b-1,j},h_{b,j-1},h_{b-1,j-1})$计算，其中将段b与时间槽j匹配的成本为

如果对于$u\in U_b$，在时隙 j 中不存在信道质量历史，则 $c(b,j)=\infty$。请注意，CHLS 使用所有三个信道质量属性来提高准确性。此外，对于每个时隙，它利用几个扇区对应的信道质量属性。该方案得出结论，估计用户位于$b^{\ast }=argmin{}_{b\in B}{h}_b,T_p$。要完成第一步，估计用户的速度，使用训练数据来计算估计位置附近过去速度的平均值。

我们通过模拟评估了CHLS。我们将$T_p$设置为3000个插槽（对应于60秒的时间范围），将段大小设置为25m×25m，并假设服务扇区覆盖半径为1000m。我们使用表II中报告的一半轨迹创建了覆盖图。从剩余的轨迹中，我们选择了500个60秒长度的随机实例。定位误差的分布如图8(a)所示。该方案的中位数误差为23m，平均误差为123m。作为比较，我们对的RSSI本地化方案[27]的评估如图8(b)所示，中位数误差超过300m。

图8.覆盖图预测机制(CMPM)的评价：(a)500次测试的CHLS误差分布与(b) [27]提供的定位方案的500次测试的误差分布比较；©使用GPS或CHLS确定位置和速度时的CMPM数据速率预测示例。

C. 可行数据速率预测

回想一下，FPF调度问题公式是基于可行的数据速率。因此，我们现在转向使用数据速率。附录A中提供的$E_c/I_o$和数据速率之间的关系是单调的，因此，第五章中的可复制性结论也适用于数据速率。

一个简单的在线算法，可在该领域内通过覆盖图以及用户当前位置和速度的估计值（来自GPS或CHLS）来估算用户的未来数据速率。首先，假设在未来的时间段内速度保持不变，则预测未来的位置。然后将每个位置映射到覆盖图中的段，从而产生数据速率。

图8( c )显示了CMPM使用两种变体的数据速率预测示例，我们将其称为CMPM-GPS和CMPM-CHLS。在第八部分中，我们证明了当CMPM-CHLS被集成到(PF)2S框架中时，可以捕捉到足够多的慢衰落效应，从而改善调度性能。

7. 分配估算（$\hat{\alpha }$）

$（PF{）}^{2}S$框架（将在第IV部分中描述）需要基于数据速率预测的信道分配（$\hat{\alpha }$）估计算法。这可以视为通过使用预测数据速率矩阵$\hat{R}$获得FPF调度问题的解决方案。由于该框架以在线方式运行，因此主要的设计考虑因素是简单性和对预测错误的鲁棒性。现在，我们将介绍三种算法，它们在鲁棒性方面可以交换公平性和吞吐量性能。这些算法将在第VIII部分与该框架的其余部分一起评估。
轮询估计(RRE)：这种简单的启发式假设未来的时间槽以轮询方式分配，每个用户接收相同数量的槽，导致估计的分配${\hat{\alpha }}_{ij}=1/K\forall i,j。$

盲目梯度估计(BGE)：这种启发式算法(4)利用在每个时间片中选择一个用户，但不包括未来组件（因为它是未知的）。具体来说，从j = 1开始，它将${\hat{\alpha }}_{i\ast j}$设置为1，其中$i\ast =argma{x}_{i\in K}({\hat{r}}_{ij})/{\sum }_{t=1}^j{\hat{\alpha }}_{it}{\hat{r}}_{it}$。表达式仅包含小于等于j的时间片索引，与PF-EXP类似。BGE需要O(KT)次运算。

局部搜索估计（LSE）：下面的贪婪算法以基于由随机值组成的$\hat{\alpha }$的目标函数值C为起点。它逐个插槽地迭代，贪婪地分配插槽j给具有最大梯度值的用户，假设所有其他时隙都是固定的。该算法循环进行（在T之后返回到插槽1），直到达到局部最大值（即在T次迭代中没有变化）。由于目标值是有上界的，因此保证了终止。LSE的每个循环需要O（KT）次计算。实际上，它通常在几个循环后终止。

图9(a)给出了各个算法的$\hat{\alpha }$值的示例。LSE的估计值在预测的慢衰落峰值附近紧密聚集。BGE的估计值较为分散，RRE的估计值较为均匀。因此，如果速率预测是准确的，使用LSE的框架提供了最佳性能，因为它正确地分配了靠近峰值速率的时隙。使用BGE的框架在峰值速率周围分配时隙，从而取得了较好的性能。使用RRE的框架均匀地分配时隙，偶尔也会用在在峰值期间。另一方面，如果预测有误，LSE将会受到影响，因为它推动框架按预测的慢衰落峰值安排用户的时隙。BGE对预测误差具有一定的鲁棒性，而RRE是最具鲁棒性的。

图9. (a)对于一个T˜=15s的用户，预测数据速率的示例以及LSE，BGE和RRE算法计算出的相应αˆ估计。(b)测试用例K=7和T˜=15s的数据速率(rij )。

8. 性能评估

现在我们使用基于轨迹的模拟来评估在第四节中描述的$(PF{)}^{2}S$框架的性能。框架实例使用 CMPM 实现和信道分配估计算法的组合。测试用例使用测量轨迹生成，性能指标是比例公平 (1) 和吞吐量 (Defn. 1)。我们表明，各种 $(PF{)}^{2}S$框架实例一致优于所部署的调度程序 (PF-EXP)，在现实场景中的吞吐量改善范围为 15% 至 55%，同时保持类似的延迟性能。然后我们研究了框架对时间范围、用户数量、移动性、$\hat{R}$准确性、延迟阈值和覆盖图分辨率的敏感性。

A. 生成覆盖图和测试用例

从第V节给出的数据集中，每条路线的半数驱动被用作覆盖图构建的训练测量值（使用25m×25m段大小）。 剩余的测量值用于生成测试用例。对于每个具有足够测量数据的扇区，生成一个单独的测试用例。每个测试用例由K个用户和T个时隙组成，模拟用户从扇区覆盖区域内的不同位置出发，并沿着路线以不同的速度在两个方向上行驶。

对于每个用户i，数据速率$r_{ij}，1\le j\le T$是通过从用户所在的trace部分选择T个随机连续时隙段来生成的。在一半的情况下，向量是时间反转的，模拟相反方向的移动。图9（b）显示了具有K = 7和$\tilde{T}=30s$ 的示例测试用例的数据速率（$r_{ij}$）（前几节介绍过$\tilde{T}$是以秒为单位的时间跨度）。

最后，对于每个生成的比率矩阵R，我们考虑了3种方法来获得预测的比率矩阵$\hat{R}$：具有洞察力的（也称为完全知识，$\hat{R}=R$）、CMPM（使用GPS信息进行位置估计，称为CMPM-GPS）和使用CHLS的CMPM（称为CMPM-CHLS）。使用这些方法能够评估具有不同$\hat{R}$预测质量的框架。

B. 基准比较和上界

我们将$(PF{)}^{2}S$ Framework与已部署的调度器PF-EXP（参见定义3）进行了比较，通过将吞吐量和公平性值归一化到PF-EXP获得的相关值来实现。因此，大于1的度量值表示相对于PF-EXP有所改进。作为上限，FPF问题的最优解（称为OPT）是使用CVX（一种MATLAB求解器[1]）获得的。请注意，OPT是在忽略整数约束（3）的情况下，使用R且没有延迟约束的情况下获得的。

如第四部分所述，参数ϵ隐式地控制了PF-EXP调度器的吞吐量-延迟权衡。$(PF{)}^{2}S$框架使用参数$D_{starved}$明确地控制吞吐量-延迟权衡。 除非另有规定，否则我们将Dstarved固定为0.5秒。 为了确保与我们的框架进行公平比较，我们选择一个使PF-EXP算法具有类似延迟性能的ϵ值。 相应地，基于图10中显示的PF-EXP最大延迟的箱线图15，我们选择ϵ=0.01。 我们在第八部分D中讨论这些参数的灵敏度。

图10.PF-EXP算法最大延迟的统计特征(K=5，T˜=30s，可变ε)对于30个测试用例。

C. 吞吐量和公平收益
我们评估了各种PF2S框架实例的吞吐量和公平性性能，并实验性地确认了$\hat{\alpha }$估计算法对速率预测误差具有不同程度的鲁棒性。

图11(a)和图11(b)展示了该框架的公平性和吞吐量性能增益的箱形图，共22个随机生成测试用例，K=7，T〜=30秒（增益大于1表示优于PF-EXP）。由于目标函数是对数的，因此公平性增益仅为几个百分点。该框架所有实例的吞吐量增益均显著（高达70%）。显然，框架实例的性能取决于速率预测准确度（$\tilde{R}$）和信道分配估计（$\tilde{\alpha }$）算法。因此，我们将框架实例按R〜进行分类，

Clairvoyant：吞吐量增益巨大（$\tilde{R}$预测机制：20%至70%）。根据框架实例的性能，预计估计算法按性能排名为LSE>BGE>RRE。通常情况下，具有完整知识的LSE性能接近最优。

CMPM-GPS的$\tilde{R}$：图11(a)和11(b)表明，对于$\tilde{\alpha }$估计算法，排名依次为BGE>RRE>LSE。正如第VII节所述，BGE对预测误差具有相对鲁棒性，因此与LSE相比，它通常能通过CMPM-GPS实现20%至55%的吞吐量提升。

CMPM-CHLS中的$\tilde{R}$：与使用完整知识相比，使用LSE和BGE的实例性能下降最大。然而，与PF-EXP相比，它们仍然可以带来收益。总体而言，我们发现RRE对误差的恢复能力最强，可带来15%到50%的显著吞吐量收益。

为了确认$（PF{）}^{2}S$框架相对于PF-EXP算法的增益不会以降低用户延迟性能为代价，图11（c）和11（d）展示了用户经历的延迟。回想一下，延迟（参见定义2）指的是用户在一段时间内没有收到分配。图11（c）显示了使用BGE以及PF-EXP调度程序时$（PF{）}^{2}S$框架的用户延迟经验的累积分布函数（CDF）。显然，该框架的延迟性能与PF-EXP调度程序的延迟性能相当，尽管如图11（d）所示，该框架导致用户的延迟略有更高的变化。这些结果证实，$（PF{）}^{2}S$框架提供了与PF-EXP调度程序类似的延迟性能。

图11.不同框架实例的性能比较(PF)2S Framework (组合$\hat{R}和\hat{\alpha }$预测算法):对22个测试用例进行统计评估，其中K=7和T~=30s，以及由此产生的(a)相对于PF-EXP的公平性增益，(b)相对于PF-EXP的吞吐量增益，©BGE算法的用户延迟的累积分布函数，以及(d)用户延迟的标准偏差。

总之，基于实际测量的评估表明，实际（PF）2S框架实例在延迟性能方面与PF-EXP调度程序相匹配，但通常会一致地提供更高的性能，吞吐量增益通常在15%到55%之间。尽管公平性增益是成对数增长的，但它们的数量级只有几个百分点。

D. 敏感性分析
以下是使用RRE和CMPM-CHLS的框架的结果（其他框架实例的结果类似，因此提供了等效的结论，因此省略）。

时间视野（T˜）：图12（a）显示了具有不同时间视野T˜的测试用例的公平性和吞吐量增益。直观地说，较大的T˜为框架提供了更多机会，使其比不包括未来数据速率的PF-EXP受益更多。对于T˜的小到中等值（5秒，15秒），框架显示出10％-30％的吞吐量改进。当T˜ = 60秒时，性能增益增加到20％-60％。最终，随着T˜的增长，框架受到预测精度的限制，而预测精度随着时间的推移而降低。

用户数量（K）：图12（b）显示了公平性和吞吐量增益的20个测试用例，其中T〜= 30s，并且用户数量可变。随着移动用户的增加，每个用户都会体验到自己的慢衰落信道，多用户分集增加并且性能得到改善。吞吐量增益从3个用户的25％增加到10个用户的45％。

图12.使用RRE与CMPM-CHLS时$(PF{)}^{2}S$框架的性能增益：(a)具有K=10的10个测试用例，时间范围（$\tilde{T}$）变化；(b)$\tilde{T}$=30s的20个测试用例，用户数量（K）变化。

流动性影响：为了确定静态用户的影响，我们从移动和静态（静止）测量中评估了测试用例。 静态测量的结果显示在图13（a）中，无线信道状态分布是固定的。 图13（b）考虑了在具有K = 5和$\tilde{T}$= 30s的测试用例中所有算法的框架性能（具有完整知识，因为在此情况下预测是不相关的）。 框架性能与PF-EXP非常相似（吞吐量增益在6%以内），并且非常接近OPT。 图14显示了具有10个移动用户和可变数量的静态用户的10个$\tilde{T}$= 30s测试用例的增益。 随着静态用户的增加，PF-EXP性能得到改善（接近最优），因此增益减少。 但是，由于10个移动用户，增益仍然相当显著，在某些情况下吞吐量增益超过30%。

慢衰落峰预测：如前所述，$\hat{R}$预测的准确性会影响框架性能。通过仔细检查，我们发现预测精度的关键因素是慢衰落峰的位置。因此，我们现在考虑模拟$\hat{R}$对框架性能的影响。

图13.使用静态（非移动）测量生成的测试用例的（PF）2S框架评估，其中$\tilde{T}$=30s和K=5：（a）数据速率$r_{ij}$和相应的（b）使用BGE算法的公平性和吞吐量增益与PF-EXP相比。

图14.使用RRE与CMPM-CHLS结合的$(PF{)}^{2}S$框架性能增益：对10个测试用例进行统计评估，$\tilde{T}$=30s，10个移动用户，以及不同数量的静态用户。

具体而言，预测的速率向量对于一个子集的用户 被移动了一定的数量，例如，${\hat{r}}_{ij}$ = $r_{i(j-offset)}$。图15 显示了使用具有偏移量子集的速率预测的RRE框架的公平性和吞吐量增益。 正如预期的那样，随着偏移量的增加（无论是领先还是滞后），性能都会下降。 但是，它们仍然相当显著（≈ 20%的吞吐量增益）。 这个实验表明，在几秒钟内预测慢衰落峰值与实际峰值的结果将带来显著的性能改善。 其他测试证实，这在更普遍的情况下也是成立的。

图15.具有K=5个用户和$\tilde{T}$=30s的示例测试用例的$(PF{)}^{2}S$框架评估：(a)公平性；(b)吞吐量增益超过PF-EXP，使用BGE算法模拟数据速率预测偏移量。

延迟参数（$D_{starved}，ϵ$）：如第IV部分所述，该框架使用延迟阈值Dstarved来优先处理“饥饿”用户。PF-EXP调度程序使用$ϵ$来隐式控制延迟。现在，我们探讨了PF-EXP调度程序（$ϵ$）和$（PF{）}^{2}S$框架（$D_{starved}$）上放宽延迟参数所获得性能提升。在图16（a）中，我们根据图10进行了匹配，这些参数在延迟容忍度（0.25-2s）的范围内具有可比的延迟参数。该图显示，（PF）2S框架继续优于PF-EXP调度程序，并且收益只有轻微的变化。

图16.使用RRE与CMPM-CHLS时$(PF{)}^{2}S$ Framework的性能增益：(a)为$(PF{)}^{2}S$ Framework（$D_{starved}$）和PF-EXP调度程序（$ϵ$）的延迟参数变化提供图9（b）中的测试用例，(b)对15个测试用例进行统计评估，其中K=10和$\tilde{T}$=30s，以获得不同的覆盖图分辨率值。

覆盖地图分辨率：在上述结果中，覆盖地图段大小为25m×25m。图16（b）显示了15个测试用例的框架增益，其中K=10和$\tilde{T}=30s$作为功能与地图段大小。随着段大小变得合理大，性能不会显着下降，因为较大的段会导致对更大区域的信道质量属性的平均。这表明粗信道测量对框架是有用的。

9. 结论和未来工作

我们描述了一项广泛的无线测量研究，以及$(PF{)}^{2}S$框架的设计和基于跟踪的性能评估。我们表明，通过利用慢衰落，该框架(由各种算法组成)可以提供显着的吞吐量增益，同时改进或保持公平水平。最后，我们对不同参数和假设的敏感性进行了研究。

个人疑点及解答

1. 什么是慢衰减、什么是快速衰减

   在信道中，慢衰落是指信号幅度的长期变化，是传播环境在较长时间、较大范围内发生变化的结果，又被称为长期衰落、大尺度衰落；快衰落则描述了信号幅度的瞬时变化，与多径传播有关，又被称为短期衰落、小尺度衰落。

   多径传播使信号包络产生的起伏虽然比信号的周期缓慢，但是仍然可能是在秒或秒以下的数量级，衰落的周期常能和数字信号的一个码元周期相比较，故通常将由多径效应引起的衰落称为快衰落。即使没有多径效应，仅有一条无线电路径传播时，由于路径上季节、日夜、天气等的变化，也会使信号产生衰落现象。这种衰落的起伏周期可能较长，甚至以若干天或若干小时计，称这种衰落为慢衰落。

   我的理解是：如果是慢衰落的话，人可以明显感知到信号变差的过程，快衰落应该是人没反应过来就恢复了

2. 为什么说无线信道状态是一个平稳过程
   无线信道状态只受到快速衰落的影响，变化是瞬时的，很快就能恢复，无线信道状态大体是一个平稳过程，它不会随着时间的推移而发生显著的变化。

3. $E_c/I_o$和RSSI是什么意思
   RSSI，即频率带内接收的总功率，表示信号强度指标
   $E_c/I_o$表示特定导频信号的功率与带内总功率（包括干扰和噪声）的比率，表示信号质量

4. 文中说的向扇区报告其信噪比($E_c/I_o$)，选择适当的通道化码并将其映射到可行的数据速率是什么意思？

   通道化码是一种将多个通道的信息编码为单个通道传输的方法，可以提高传输效率、减少干扰和噪声的影响、提供更好的灵活性和可扩展性。

5. RSCP值是什么
   RSCP（Received Signal Strength and Channel Power）值是一种指示接收信号强度的参数。它通常用于无线网络中，表示接收到的信号强度和信道功率。

   在无线网络中，RSCP值可以提供关于信号质量和连接稳定性的信息。通常情况下，RSCP值越高，表示接收到的信号强度越大，连接质量越好。相反，RSCP值越低，表示接收到的信号强度越小，连接质量越差。

6. 这逼文章在到底在讲什么？
   文章提出了一种场景：一辆车行驶了较长的距离，较快经过了三个扇区，过程中明显能感觉到网络质量变差到恢复的过程（慢衰落），指出PF调度算法在类似场景下将失效，提出了有限视距的PF算法（FPF）。
   用户分配到的时间乘上数据速率就是用户得到的总服务，目标是让扇区内所有用户的总服务最大化，得到公式1
   
   限制条件s.t.是指分给某个用户i后，其余的就只能是0了，所以所有用户求和是1。
   用梯度上升法求解，对某个${\alpha }_{i,j}$求导，log求导是倒数乘以某个常数（不用管），log里面照抄，${\alpha }_{i,j}{r}_{i,j}$求导剩个$r_{i,j}$在分母。
   
   那这玩意的分母准确的说有三部分，过去、现在和未来三部分组成
   
   那么问题来了，未来这部分怎么求，所以文章分别建立了R和α的预测算法。
   文章做了个覆盖图预测算法，先算出车在哪个位置，用这个位置的信号质量当成车的信号质量，信号质量查表看数据速率。
   然后用了三个算法来算α怎么分配，然后做了一些实验。