网站建设公司antnw,福州网红餐厅,嘉祥住房和城乡建设局网站,登录网站后没有转页面#xff08;一支笔一包烟#xff0c;一节论文看一天 #xff09;#xff08;一张纸一瓶酒#xff0c;一道公式推一宿#xff09; 摘要1. 引言2. 相关工作3. 模型和问题公式4. 预测FPF调度 #xff08; P F #xff09; 2 S #xff08;PF#xff09;^2S #xff08;… 一支笔一包烟一节论文看一天 一张纸一瓶酒一道公式推一宿 摘要1. 引言2. 相关工作3. 模型和问题公式4. 预测FPF调度 P F 2 S PF^2S PF2S框架5. 慢衰减测量6. 可行数据率预测 R ^ \hat R R^7. 分配估算 α ^ \hat α α^8. 性能评估9. 结论和未来工作个人疑点及解答 Exploiting Mobility in Proportional Fair Cellular Scheduling Measurements and Algorithms 摘要
比例公平PF调度算法是蜂窝网络中的事实标准。它们利用用户的信道状态多样性由快速衰减引起对于平稳的信道状态分布和无限的时间视野是最优的。然而移动用户的信道是非平稳的这是由于慢衰减秒级造成的并且与基站在短时间内相关联。因此我们开发了利用移动性的预测有限视界PF调度( ( P F ) 2 S (PF)^2S (PF)2S)框架。我们提供了来自3G网络的广泛信道测量结果并表征了由移动性引起的信道状态趋势。我们发现用户的信道状态具有高度可重复性并利用这一点开发了数据速率预测机制。然后我们提出了一些利用预测机制的信道分配估计算法。我们的基于跟踪的模拟考虑了由预测和信道分配估计算法组合而成的 ( P F ) 2 S (PF)^2S (PF)2S框架实例。它们表明该框架可以将吞吐量提高15%到55%与传统的PF调度器相比同时提高了公平性。
1. 引言
3G和4GLTE蜂窝网络集成了机会调度器[11]。这些调度器利用快速衰落导致的信道状态变化以及多用户分集为具有良好信道条件的用户分配资源。比例公平PF调度算法是蜂窝网络中机会调度器的实际标准[16]。它们旨在提供高吞吐量同时保持用户之间的公平性。过去已经对PF调度算法进行了广泛的研究例如[6]、[10]、[18]。这些算法在以下假设下是最佳的无线信道状态是一个平稳过程即它只受到快速衰落的影响并且用户的关联时间很长例如静态用户或行人[20]、[28]。然而当这些假设不成立时对于移动用户来说就是这种情况这些算法的性能就不再是最优的[5]。
图1说明了一辆汽车在一条5公里路上的轨迹以及与3个不同扇区之间的信号质量 ( E c / I o ) (E_c/I_o) (Ec/Io)我们是在这条路上3次驾驶过程中收集的 E c / I o E_c/I_o Ec/Io值。可以看出信道具有一个占主导地位的慢衰落分量其上叠加了一个快速衰落分量。由于 E c / I o E_c/I_o Ec/Io在几秒钟内具有明显的趋势因此信道状态分布是非平稳的。另外沿着路径的运动会导致扇区之间的切换因此关联周期很短。 图1. 移动用户沿3个蜂窝扇区道路的轨迹a地图轮廓和与蜂窝网络的交互以及b在3次不同驾驶期间测量的信道质量 E c / I o E_c/I_o Ec/Io值。
例如图1说明了汽车沿5km路径的轨迹和3个不同扇区(在路径上的3次驾驶期间收集了 E c / I o E_c/I_o Ec/Io值)的信号质量( E c / I o E_c/I_o Ec/Io)。可以看出信道具有占主导地位的慢衰落分量其上叠加了快速衰落分量。由于 E c / I o E_c/I_o Ec/Io在几秒钟内具有明显的趋势因此信道状态分布是非平稳的。此外沿着路径的运动会引发扇区之间的切换因此关联期很短。
由于PF调度器并未针对移动性进行优化我们设计了预测有限视距PF调度 P F 2 S PF^2S PF2S框架该框架是针对移动节点定制的同时利用慢衰落和快衰落。它包括三个组件i数据速率预测ii未来信道分配的估计iii慢衰落感知调度。
为了描述慢衰落现象为速率预测机制的设计提供输入并获取用于评估框架和算法的跟踪信息我们进行了广泛的测量活动。特别是我们讨论了从3G网络收集的细粒度即毫秒级分辨率测量数据。具体来说我们在长达810公里的行驶过程中以及在超过1300分钟的测量期间内测量了无线信道属性。与之前的一些研究例如[27]不同它们测量的是接收信号强度指示器RSSI即频率带内接收的总功率我们测量的是每个扇区的信号质量 E c / I o E_c/I_o Ec/Io。这使我们能够获得重要的见解因为 E c / I o E_c/I_o Ec/Io是用户数据速率的最为相关的预测因素
我们分析了这些轨迹并发现移动用户的体验明显变差。然而这种变差的趋势不能简单地归因于视距指标因此开发简单的信道状态预测是不可行的。但是对于相同路径上的多个驱动器 E c / I o E_c/I_o Ec/Io的慢衰减分量具有很好的可重复性例如图1(b)这使得数据驱动的预测方法变得可行。
基于以上观察结果我们开发了一个两阶段的速率预测机制称为覆盖图预测机制CMPM。在离线阶段处理测量轨迹以构建信道质量图。在线阶段由扇区执行包括确定用户的位置和速度从而预测数据速率。定位可以通过查询用户的GPS简单完成。然而由于这会给用户带来能量和计算负担我们还设计了通道历史定位方案CHLS该方案需要一些关于用户轨迹的知识。CHLS使用变体的动态时间规整DTW算法最初是为语音识别开发的[24]。 ( P F ) 2 S (PF)^2S (PF)2S框架还需要能够基于速率预测结果估计未来信道分配的算法。我们提出了三种启发式算法它们对预测误差的鲁棒性和对相对准确预测的性能水平各有不同。使用从收集的跟踪数据生成的测试用例我们对 ( P F ) 2 S (PF)^2S (PF)2S框架进行了广泛的模拟评估。我们考虑了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 E_c/I_o Ec/Io和RSSI以及最近的历史记录并通过基于跟踪的模拟进行评估。
3. 模型和问题公式
在本节中我们将回顾3G网络中的信道状态估计过程并阐述调度问题。
A. 3G网络中的信道状态
在3G网络中每个基站覆盖一个小区该小区被分成通常是3个扇区。如图1(a)所示出于数据调度和切换的目的用户估计每个附近扇区的无线信道质量。它是估计一个扇区特定导频信号的功率与带内总功率包括干扰和噪声的比率并由 E c / I o E_c/I_o Ec/Io表示。在第五部分中我们将在我们的测量研究中考虑这些值。
用户与最强邻近扇区称为服务扇区进行关联连接并在该扇区分配专用缓冲区。当服务扇区的 E c / I o E_c/I_o Ec/Io值低于阈值例如由于移动性时用户将进行切换操作与该服务扇区断关联并与具有更高 E c / I o E_c/I_o Ec/Io值的新扇区建立连接。
扇区到用户的下行信道是时分的。我们将用 E c / I o [ j ] E_c/I_o[j] Ec/Io[j]表示第j时隙的值。用户定期向扇区报告其信噪比( E c / I o E_c/I_o Ec/Io)。然后选择适当的通道化码并将其映射到可行的数据速率。第j时隙中第i个用户的可行数据速率记为 r i j r_{ij} rij。扇区中实现的机会调度器利用多用户数据速率的多样性来为用户分配下行时隙参见图1(a)。
B. 调度问题定义
常见的3G调度器解决了比例公平PF调度问题[16][18]旨在实现高整体吞吐量的同时保持用户之间的公平性。关于恒定信道和长关联时间的常见假设在移动场景中并不成立将在第五部分中说明。因此我们将下行链路调度问题表述为PF调度问题的变体同时利用类似于[5]的公式研究对抗信道。与以前的工作不同例如[10][20][28]我们没有对信道状态分布做出假设而是在有限的时间跨度内进行优化。
我们假设一个扇区有K个相关用户且下行缓冲队列有未处理的数据。用 α i j α_{ij} αij表示调度器分配如果用户i被分配到第j个时隙则 α i j α_{ij} αij1否则 α i j α_{ij} αij0。我们用 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获得累计服务 ∑ j 1 T α i j r i , j \sum^T_{j1}α_{ij}r_{i,j} ∑j1Tαijri,j。因此我们制定了以下问题其目标是最大化比例公平成本函数。
有限视野比例公平调度: 即使知道R的全部信息此问题也是NP难问题(证明见附录B)。在实践中此问题必须以在线方式解决。用户是根据历史知识按插槽逐个安排的而无需完全了解R。虽然FPF调度问题的目标是最大化比例公平度量(1)但在评估框架(第VIII节)时我们还考虑以下度量。
定义1吞吐量所有用户分配的平均数据速率记作 ∑ i 1 K ∑ j 1 T α i j r i , j / T \sum^K_{i1} \sum^T_{j1}α_{ij}r_{i,j}/T ∑i1K∑j1Tαijri,j/T称为吞吐量。
定义2延迟用户i在连续的时间插槽中没有接收分配的数量称为延迟用 d i d_i di表示。如果 d i ≥ D s t a r v e d d_i≥D_{starved} di≥Dstarved则用户i被视为饥饿其中 D s t a r v e d D_{starved} Dstarved是延迟阈值。
我们注意到在第八章节中时间范围有时以秒为单位进行考虑并用 T ~ \tilde{T} T~ 表示。
4. 预测FPF调度 P F 2 S PF^2S PF2S框架
在本节中我们将回顾广泛部署的PF调度算法并介绍一种在线调度框架用于解决FPF调度问题该问题由两个组件组成(i)数据速率预测和(ii)未来信道分配的估计。这些组件的设计将分别在第6节和第7节中介绍。我们首先描述了在3G网络中部署的PF调度程序该程序将在后面的章节中用作基准。
定义3PF-EXP将满足 α i ∗ j 1 α_{i∗j} 1 αi∗j1其中 i ∗ a r g m a x i ∈ K r i j / R i [ j ] i∗ arg \ max_{i \in K} r_{ij}/R_i[j] i∗arg maxi∈Krij/Ri[j]且 R i [ j ] ( 1 − ϵ ) R i [ j − 1 ] ϵ α i j r i j R_i[j] (1 − \epsilon)R_i[j − 1] \epsilon α_{ij} r_{ij} Ri[j](1−ϵ)Ri[j−1]ϵαijrij的调度器称为PF-EXP。
在PF-EXP调度器的定义中 ϵ \epsilon ϵ决定吞吐量和延迟之间的折衷。具有较大的 ϵ \epsilon ϵ≈1值调度器更重视用户当前可行的速率从而提高吞吐量但会牺牲延迟性能。具有较小的 ϵ \epsilon ϵ≈0值时用户的分配历史具有更大的权重因此延迟性能得到改善但会牺牲吞吐量。当无线信道状态是一个平稳过程并且用户具有较长的关联时间即T→∞时PF-EXP调度器接近于最优比例公平性[20]、[28]。
我们的预测FPF调度 ( P F ) 2 S (PF)^ 2S (PF)2S框架采用了类似于PF-EXP调度器的分时分配方法它利用梯度上升法[9]来最大化目标函数(1)。在每个时间槽中信道将分配给对应于目标函数最大增加量的用户。暂时放宽(3)中的整数约束用户i在时间槽j的梯度为 计算上述梯度需要知道整个数据速率矩阵R对于只了解过去的在线算法来说是不可行的。因此式(4)的分母被分成三个部分(从左到右):过去、现在和未来。从在线调度器的角度来看前两个组件在任何时间槽中都是已知的。为了实现逐时隙调度式(4)的未来部分作为 ( P F ) 2 S (PF)^2S (PF)2S框架的一部分进行计算这在上面的伪代码中进行了描述。 未来信道分配 α i j α_{ij} αij 由 r ^ i j \hat {r}_{ij} r^ij和 α ^ i j \hat {α}_{ij} α^ij表示 分别用 R ^ \hat{R} R^和 α ^ \hat α α^表示矩阵表示。 在0时刻, R ^ 和 α ^ \hat R 和 \hat α R^和α^ 的预测值是对整个视界下一个T槽预先计算的。这些矩阵可以生成 使用第六节和第七节中描述的方法但 框架可以支持其他方法。对于每个用户i在每个 计算与4对应的排名 M i j M_{ij} Mij即槽j 使用 R ^ \hat R R^和 α ^ \hat α α^。选择排名最高的用户。
对于恒定信道未来信道统计信息包含在分母的过去分量中4。因此仅依赖过去信息的算法即PF-EXP是最优的。然而对于非恒定信道分布情况并非如此。因此与PF-EXP不同该框架中的第4步考虑了未来信道分量。通过纳入预测的未来(PF)2S框架可以利用慢衰落趋势。此外通过逐时隙决策该框架还可以利用快衰落成分类似于PF-EXP。
由于 ( P F ) 2 S (PF)^2S (PF)2S框架旨在安排在慢衰落峰期(可能每几秒钟发生一次)期间的用户因此必须确保这不会导致长时间的延迟。因此在每个时隙中该框架首先考虑等待时间超过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 E_c/I_o Ec/Io。11 这些关键属性表征信道质量并由用户定期报告给服务部门[16]。后两者是每个相邻扇区导频信道的特定值而前一个RSSI则不是。此外虽然RSSI通常记录在以前的工作中并被使用例如[27]但从调度角度来看 E c / I o E_c/I_o Ec/Io是用户信道质量最相关的指标[16]。
我们通过一个例子来说明慢衰落现象。图3(a)显示了所有路线上27个驱动器用户关联时间的直方图表明关联时间大约为几十秒。作为一个具体的例子图3(b)显示了沿着R4路线的单个驱动器部分测量到的RSSI和服务的扇区 E c / I o E_c/I_o Ec/Io的轨迹。显然RSSI并不总是反映与 E c / I o E_c/I_o Ec/Io相同的趋势。此外 E c / I o E_c/I_o Ec/Io经历了数秒的慢衰落。由于在大多数情况下用户的关联时间是几十秒因此慢衰落的峰值和谷值都发生在每个扇区。因此接下来的两个子部分主要关注被 ( P F ) 2 S (PF)^2S (PF)2S框架所利用的 E c / I o E_c/I_o Ec/Io慢衰落趋势。 图3.a沿路线R1-R4的27个驱动器的扇区关联时间分布b路线R4部分驱动器的RSSI和扇区服务 E c / I o E_c/I_o Ec/Io的测量值垂直柱表示切换。
图4. E c / I o E_c/I_o Ec/Io测量值、 E c / I o ∗ E_c/I_o^∗ Ec/Io∗标准化值和 E c / I o ∗ ~ \widetilde{E_c/I_o^∗} Ec/Io∗ 平滑值的比较a来自R4路线的移动轨迹和b静态轨迹。
C. 慢衰落与移动性
我们首先证明慢衰落现象与用户移动性密切相关。然后我们描述了慢衰落和移动性指标之间的相关性并表明与过去工作的假设相反例如[3]慢衰落趋势不能与简单的视线指标联系起来。
为了量化用户在T时隙的 E c / I o E_c/I_o Ec/Io轨迹中的慢衰减我们定义了如下慢衰减度量。首先减去均值并对轨迹进行归一化处理以获得 该操作不会影响 E c / I o E_c/I_o Ec/Io的趋势但会去除可因扇区而变的幅值从而能够比较不同扇区的 E c / I o E_c/I_o Ec/Io轨迹。然后通过使用小波变换对 E c / I o ∗ E_c/I_o^∗ Ec/Io∗进行平滑处理以去除快速衰减的成分频率大于 1Hz。 E c / I o ∗ E_c/I_o^∗ Ec/Io∗的平滑版本记作 E c / I o ∗ ~ \widetilde{E_c/I_o^∗} Ec/Io∗ 有关平滑操作的更多细节请参阅附录 C。图 4 为移动用户和静态用户的 E c / I o ∗ E_c/I_o^∗ Ec/Io∗示例。使用 E c / I o ∗ ~ \widetilde{E_c/I_o^∗} Ec/Io∗ 和 E c / I o E_c/I_o Ec/Io可以清楚地说明观察期间 E c / I o E_c/I_o Ec/Io值的趋势存在或不存在。
我们计算了从每个服务扇区收集的每个 E c / I o E_c/I_o Ec/Io轨迹的S值参见表II。图5a显示了静态轨迹和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 Ec/Io的慢衰落分量具有非常高的可重复性使得数据驱动的预测方法成为可能。具体来说我们观察到来自多次测量(来自不同的驱动器)的 E c / I o E_c/I_o Ec/Io是可以预测的误差为1-3dB(类似的结果出现在[27]中对于RSSI)。为了说明可重复性我们将路线R4的一部分分成25m的段并在图1(b)中显示了穿过3个扇区的一部分段观察到的3个驱动器的 E c / I o E_c/I_o Ec/Io。曲线的重叠表明所有驱动器之间的相似性。
我们通过计算每个路线的所有驱动器的 E c / I o E_c/I_o Ec/Io交叉相关来加强这一观察结果如下所示。每个路线被分成25米的段然后该路线上的每个驱动器都由 E c / I o E_c/I_o Ec/Io值的向量表示每个向量对应一个段例如如果路线包括n个段则每个驱动器由长度为n的向量表示同一段中的多个观察值由它们的平均值表示。然后我们计算所有向量驱动器的相关系数。图6bcd显示了路线 R1、R3 和 R4 上所有驱动器之间的相关性。相关系数在0.9-0.98之间表明相关性非常高。所有重复驱动器之间的高相关性意味着带有位置标签的历史 E c / I o E_c/I_o Ec/Io测量值可用于准确预测未来的慢衰落。 图6.测量得出的 E c / I o E_c/I_o Ec/Io值的可重复性a通过R1线路上一个扇区的7个驱动器的测量值以25m为间隔进行对齐b(d)R1、R3和R4线路上所有具有足够数据的驱动器之间的 E c / I o E_c/I_o Ec/Io相关系数。
6. 可行数据率预测 R ^ \hat R R^ ( P F ) 2 S (PF)^2S (PF)2S框架需要一种机制来预测用户在T个时隙中的可行数据速率 R ^ \hat R R^。我们基于对 E c / I o E_c/I_o Ec/Io的慢衰减分量的高度可重复性的观察设计了一种机制并将其称为覆盖图预测机制CMPM。在离线阶段处理测量跟踪以构建地理覆盖图。在线阶段由扇区执行并由两个步骤组成。首先确定用户的位置和速度。然后将此信息与覆盖图结合使用来预测用户i的可行速率 r ^ i j ∀ 1 ≤ j ≤ T \hat r_{ij}∀1 ≤ j ≤ T r^ij∀1≤j≤T。
第一步可以通过查询用户的GPS来实现。然而由于这会给用户带来能量和计算负担我们还开发了通道历史本地化方案(CHLS)。该方案假设已知用户整体轨迹。在第八部分中我们使用两种替代方案对框架进行了评估。
A. 覆盖图构建
覆盖图是通过离线方式针对每条路线一次构建的将格子放置在地理平面上并将其划分为正方形部分参见图7。在所有格子中用户所在格子表示为b被一组扇区覆盖居住在该部分的用户可以与之关联表示为 U b U_b Ub。蜂窝运营商通常测量主要路线的信道质量。这些测量可以用于计算每个部分b的平均RSSI值以及每个相邻扇区 u ∈ U b u \in U_b u∈Ub的平均 E c / I o E_c/I_o Ec/Io和RSCP值。这些分别表示为 R S S I b ‾ \overline{RSSIb} RSSIb E c / I o u b ‾ \overline{E_c/I_{o_u}b} Ec/Ioub R S C P u b ‾ \overline{RSCP_ub} RSCPub。为了计算这些值进行评估每个样本测量都带有GPS位置标记并绑定到适当的部分。
图7 CHLS的示意图覆盖图段从1开始标记在时隙1用户位于段1。在当前的时隙 T p T_p Tp用户位于Bcell和Bmax之间的一个段中这些段落在服务扇区的覆盖区域内。
B. 通道历史定位方案CHLS
CMPM在线阶段的第一个步骤是将用户定位到覆盖图上。为了在没有GPS的情况下实现这一点我们设计了CHLS。它基于信道度量值之间的差异将用户的历史信道质量与用户轨迹上的覆盖图段进行匹配。然后将用户的位置估计为其当前信道质量值所配对的段。将信道质量历史即时间序列与段即位置进行匹配取决于用户的速度而这是可以改变的。因此我们利用动态时间扭曲DTW算法13来“解开”用户的历史信道质量以最好地适应覆盖图。
CHLS需要用户轨迹和用户在最近历史时间槽中的位置知识。用户的历时信道测量是可用的无需额外费用因为它们会定期报告给网络以进行调度和切换。
下文描述该方案的符号定义如下参见图7。该扇区保存用户过去 T p T_p Tp个时隙的 E c / I o u [ j ] E_c/I_{o_u}[j] Ec/Iou[j] R S C P u [ j ] RSCP_u[j] RSCPu[j]和 R S S I [ j ] RSSI[j] RSSI[j]的历史记录这些时隙按顺序从1到 T p T_p Tp编号当前时隙。覆盖图段按顺序编号从用户在时隙1的估计位置所在的段开始。这些段的编号不超过 B m a x Bmax Bmax即在该扇区覆盖范围内用户可能居住的最远部分。服务扇区覆盖了一系列范围为 B { b B c e l l ≤ b ≤ B m a x } B\{bB_{cell}≤b≤B_{max} \} B{bBcell≤b≤Bmax}的段。
DTW算法应用于确定选择B中每个b作为用户位置估计的成本。它构建了一个大小为 B m a x × T p B_{max} \times T_p Bmax×Tp的矩阵H。条目 h b , j h_{b,j} hb,j的值表示将1到j的时间槽与1到b的段配对的最低成本。约束条件是段1与槽1配对段b与槽j例如端点配对配对。第一行和第一列中的条目是 h 1 , j 和 h b , 1 ∞ ∀ b , j h_{1,j}和h_{b,1} ∞∀ b, j h1,j和hb,1∞∀b,j而其余矩阵使用公式 h b , j c ( b , j ) m i n ( h b − 1 , j , h b , j − 1 , h b − 1 , j − 1 ) h_{b,j} c(b, j) min(h_{b-1,j} , h_{b,j-1}, h_{b-1,j-1}) hb,jc(b,j)min(hb−1,j,hb,j−1,hb−1,j−1)计算其中将段b与时间槽j匹配的成本为 如果对于 u ∈ U b u \in U_b u∈Ub在时隙 j 中不存在信道质量历史则 c ( b , j ) ∞ c(b, j) ∞ c(b,j)∞。请注意CHLS 使用所有三个信道质量属性来提高准确性。此外对于每个时隙它利用几个扇区对应的信道质量属性。该方案得出结论估计用户位于 b ∗ a r g m i n b ∈ B h b , T p b^∗ arg \ min \ _{b∈B} \ h_b,T_p b∗arg min b∈B hb,Tp。要完成第一步估计用户的速度使用训练数据来计算估计位置附近过去速度的平均值。
我们通过模拟评估了CHLS。我们将 T p T_p Tp设置为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 E_c/I_o Ec/Io和数据速率之间的关系是单调的因此第五章中的可复制性结论也适用于数据速率。
一个简单的在线算法可在该领域内通过覆盖图以及用户当前位置和速度的估计值来自GPS或CHLS来估算用户的未来数据速率。首先假设在未来的时间段内速度保持不变则预测未来的位置。然后将每个位置映射到覆盖图中的段从而产生数据速率。
图8( c )显示了CMPM使用两种变体的数据速率预测示例我们将其称为CMPM-GPS和CMPM-CHLS。在第八部分中我们证明了当CMPM-CHLS被集成到(PF)2S框架中时可以捕捉到足够多的慢衰落效应从而改善调度性能。
7. 分配估算 α ^ \hat α α^ P F 2 S PF^2S PF2S框架将在第IV部分中描述需要基于数据速率预测的信道分配 α ^ \hat α α^估计算法。这可以视为通过使用预测数据速率矩阵 R ^ \hat R R^获得FPF调度问题的解决方案。由于该框架以在线方式运行因此主要的设计考虑因素是简单性和对预测错误的鲁棒性。现在我们将介绍三种算法它们在鲁棒性方面可以交换公平性和吞吐量性能。这些算法将在第VIII部分与该框架的其余部分一起评估。 轮询估计(RRE)这种简单的启发式假设未来的时间槽以轮询方式分配每个用户接收相同数量的槽导致估计的分配 α ^ i j 1 / K ∀ i , j 。 \hat α_{ij} 1/K \ \ ∀ i, j。 α^ij1/K ∀i,j。
盲目梯度估计(BGE)这种启发式算法(4)利用在每个时间片中选择一个用户但不包括未来组件因为它是未知的。具体来说从j 1开始它将 α ^ i ∗ j \hat α_{i∗j} α^i∗j设置为1其中 i ∗ a r g m a x i ∈ K ( r ^ i j ) / ∑ t 1 j α ^ i t r ^ i t i∗ argmax_{i \in K}(\hat r_{ij} ) / \sum _{t1}^j \hat α_{it} \hat r_{it} i∗argmaxi∈K(r^ij)/∑t1jα^itr^it。表达式仅包含小于等于j的时间片索引与PF-EXP类似。BGE需要O(KT)次运算。
局部搜索估计LSE下面的贪婪算法以基于由随机值组成的 α ^ \hat α α^的目标函数值C为起点。它逐个插槽地迭代贪婪地分配插槽j给具有最大梯度值的用户假设所有其他时隙都是固定的。该算法循环进行在T之后返回到插槽1直到达到局部最大值即在T次迭代中没有变化。由于目标值是有上界的因此保证了终止。LSE的每个循环需要OKT次计算。实际上它通常在几个循环后终止。
图9(a)给出了各个算法的 α ^ \hat α α^值的示例。LSE的估计值在预测的慢衰落峰值附近紧密聚集。BGE的估计值较为分散RRE的估计值较为均匀。因此如果速率预测是准确的使用LSE的框架提供了最佳性能因为它正确地分配了靠近峰值速率的时隙。使用BGE的框架在峰值速率周围分配时隙从而取得了较好的性能。使用RRE的框架均匀地分配时隙偶尔也会用在在峰值期间。另一方面如果预测有误LSE将会受到影响因为它推动框架按预测的慢衰落峰值安排用户的时隙。BGE对预测误差具有一定的鲁棒性而RRE是最具鲁棒性的。 图9. (a)对于一个T˜15s的用户预测数据速率的示例以及LSEBGE和RRE算法计算出的相应αˆ估计。(b)测试用例K7和T˜15s的数据速率(rij )。
8. 性能评估
现在我们使用基于轨迹的模拟来评估在第四节中描述的 ( P F ) 2 S (PF)^2S (PF)2S框架的性能。框架实例使用 CMPM 实现和信道分配估计算法的组合。测试用例使用测量轨迹生成性能指标是比例公平 (1) 和吞吐量 (Defn. 1)。我们表明各种 ( P F ) 2 S (PF)^2S (PF)2S框架实例一致优于所部署的调度程序 (PF-EXP)在现实场景中的吞吐量改善范围为 15% 至 55%同时保持类似的延迟性能。然后我们研究了框架对时间范围、用户数量、移动性、 R ^ \hat R R^准确性、延迟阈值和覆盖图分辨率的敏感性。
A. 生成覆盖图和测试用例
从第V节给出的数据集中每条路线的半数驱动被用作覆盖图构建的训练测量值使用25m×25m段大小。 剩余的测量值用于生成测试用例。对于每个具有足够测量数据的扇区生成一个单独的测试用例。每个测试用例由K个用户和T个时隙组成模拟用户从扇区覆盖区域内的不同位置出发并沿着路线以不同的速度在两个方向上行驶。
对于每个用户i数据速率 r i j 1 ≤ j ≤ T r_{ij}1 ≤ j ≤ T rij1≤j≤T是通过从用户所在的trace部分选择T个随机连续时隙段来生成的。在一半的情况下向量是时间反转的模拟相反方向的移动。图9b显示了具有K 7和 T ~ 30 s \widetilde T 30s T 30s 的示例测试用例的数据速率 r i j r_{ij} rij前几节介绍过 T ~ \widetilde T T 是以秒为单位的时间跨度。
最后对于每个生成的比率矩阵R我们考虑了3种方法来获得预测的比率矩阵 R ^ \hat R R^具有洞察力的也称为完全知识 R ^ R \hat R R R^R、CMPM使用GPS信息进行位置估计称为CMPM-GPS和使用CHLS的CMPM称为CMPM-CHLS。使用这些方法能够评估具有不同 R ^ \hat R R^预测质量的框架。
B. 基准比较和上界
我们将 ( P F ) 2 S (PF)^2S (PF)2S Framework与已部署的调度器PF-EXP参见定义3进行了比较通过将吞吐量和公平性值归一化到PF-EXP获得的相关值来实现。因此大于1的度量值表示相对于PF-EXP有所改进。作为上限FPF问题的最优解称为OPT是使用CVX一种MATLAB求解器[1]获得的。请注意OPT是在忽略整数约束3的情况下使用R且没有延迟约束的情况下获得的。
如第四部分所述参数ϵ隐式地控制了PF-EXP调度器的吞吐量-延迟权衡。 ( P F ) 2 S (PF)^2S (PF)2S框架使用参数 D s t a r v e d D_{starved} Dstarved明确地控制吞吐量-延迟权衡。 除非另有规定否则我们将Dstarved固定为0.5秒。 为了确保与我们的框架进行公平比较我们选择一个使PF-EXP算法具有类似延迟性能的ϵ值。 相应地基于图10中显示的PF-EXP最大延迟的箱线图15我们选择ϵ0.01。 我们在第八部分D中讨论这些参数的灵敏度。 图10.PF-EXP算法最大延迟的统计特征(K5T˜30s可变ε)对于30个测试用例。
C. 吞吐量和公平收益 我们评估了各种PF2S框架实例的吞吐量和公平性性能并实验性地确认了 α ^ \hat α α^估计算法对速率预测误差具有不同程度的鲁棒性。
图11(a)和图11(b)展示了该框架的公平性和吞吐量性能增益的箱形图共22个随机生成测试用例K7T〜30秒增益大于1表示优于PF-EXP。由于目标函数是对数的因此公平性增益仅为几个百分点。该框架所有实例的吞吐量增益均显著高达70%。显然框架实例的性能取决于速率预测准确度 R ~ \widetilde R R 和信道分配估计 α ~ \widetilde α α 算法。因此我们将框架实例按R〜进行分类
Clairvoyant吞吐量增益巨大 R ~ \widetilde R R 预测机制20%至70%。根据框架实例的性能预计估计算法按性能排名为LSEBGERRE。通常情况下具有完整知识的LSE性能接近最优。
CMPM-GPS的 R ~ \widetilde R R 图11(a)和11(b)表明对于 α ~ \widetilde α α 估计算法排名依次为BGERRELSE。正如第VII节所述BGE对预测误差具有相对鲁棒性因此与LSE相比它通常能通过CMPM-GPS实现20%至55%的吞吐量提升。
CMPM-CHLS中的 R ~ \widetilde R R 与使用完整知识相比使用LSE和BGE的实例性能下降最大。然而与PF-EXP相比它们仍然可以带来收益。总体而言我们发现RRE对误差的恢复能力最强可带来15%到50%的显著吞吐量收益。
为了确认 P F 2 S PF^2S PF2S框架相对于PF-EXP算法的增益不会以降低用户延迟性能为代价图11c和11d展示了用户经历的延迟。回想一下延迟参见定义2指的是用户在一段时间内没有收到分配。图11c显示了使用BGE以及PF-EXP调度程序时 P F 2 S PF^2S PF2S框架的用户延迟经验的累积分布函数CDF。显然该框架的延迟性能与PF-EXP调度程序的延迟性能相当尽管如图11d所示该框架导致用户的延迟略有更高的变化。这些结果证实 P F 2 S PF^2S PF2S框架提供了与PF-EXP调度程序类似的延迟性能。
图11.不同框架实例的性能比较(PF)2S Framework (组合 R ^ 和 α ^ \hat R和\hat α R^和α^预测算法):对22个测试用例进行统计评估其中K7和T~30s以及由此产生的(a)相对于PF-EXP的公平性增益(b)相对于PF-EXP的吞吐量增益©BGE算法的用户延迟的累积分布函数以及(d)用户延迟的标准偏差。
总之基于实际测量的评估表明实际PF2S框架实例在延迟性能方面与PF-EXP调度程序相匹配但通常会一致地提供更高的性能吞吐量增益通常在15%到55%之间。尽管公平性增益是成对数增长的但它们的数量级只有几个百分点。
D. 敏感性分析 以下是使用RRE和CMPM-CHLS的框架的结果其他框架实例的结果类似因此提供了等效的结论因此省略。
时间视野T˜图12a显示了具有不同时间视野T˜的测试用例的公平性和吞吐量增益。直观地说较大的T˜为框架提供了更多机会使其比不包括未来数据速率的PF-EXP受益更多。对于T˜的小到中等值5秒15秒框架显示出10-30的吞吐量改进。当T˜ 60秒时性能增益增加到20-60。最终随着T˜的增长框架受到预测精度的限制而预测精度随着时间的推移而降低。
用户数量K图12b显示了公平性和吞吐量增益的20个测试用例其中T〜 30s并且用户数量可变。随着移动用户的增加每个用户都会体验到自己的慢衰落信道多用户分集增加并且性能得到改善。吞吐量增益从3个用户的25增加到10个用户的45。 图12.使用RRE与CMPM-CHLS时 ( P F ) 2 S (PF)^2S (PF)2S框架的性能增益(a)具有K10的10个测试用例时间范围 T ~ \widetilde T T 变化(b) T ~ \widetilde T T 30s的20个测试用例用户数量K变化。
流动性影响为了确定静态用户的影响我们从移动和静态静止测量中评估了测试用例。 静态测量的结果显示在图13a中无线信道状态分布是固定的。 图13b考虑了在具有K 5和 T ~ \widetilde T T 30s的测试用例中所有算法的框架性能具有完整知识因为在此情况下预测是不相关的。 框架性能与PF-EXP非常相似吞吐量增益在6%以内并且非常接近OPT。 图14显示了具有10个移动用户和可变数量的静态用户的10个 T ~ \widetilde T T 30s测试用例的增益。 随着静态用户的增加PF-EXP性能得到改善接近最优因此增益减少。 但是由于10个移动用户增益仍然相当显著在某些情况下吞吐量增益超过30%。
慢衰落峰预测如前所述 R ^ \hat R R^预测的准确性会影响框架性能。通过仔细检查我们发现预测精度的关键因素是慢衰落峰的位置。因此我们现在考虑模拟 R ^ \hat R R^对框架性能的影响。 图13.使用静态非移动测量生成的测试用例的PF2S框架评估其中 T ~ \widetilde T T 30s和K5a数据速率 r i j r_{ij} rij和相应的b使用BGE算法的公平性和吞吐量增益与PF-EXP相比。
图14.使用RRE与CMPM-CHLS结合的 ( P F ) 2 S (PF)^2S (PF)2S框架性能增益对10个测试用例进行统计评估 T ~ \widetilde T T 30s10个移动用户以及不同数量的静态用户。
具体而言预测的速率向量对于一个子集的用户 被移动了一定的数量例如 r ^ i j \hat r_{ij} r^ij r i ( j − o f f s e t ) r_{i(j−offset)} ri(j−offset)。图15 显示了使用具有偏移量子集的速率预测的RRE框架的公平性和吞吐量增益。 正如预期的那样随着偏移量的增加无论是领先还是滞后性能都会下降。 但是它们仍然相当显著≈ 20%的吞吐量增益。 这个实验表明在几秒钟内预测慢衰落峰值与实际峰值的结果将带来显著的性能改善。 其他测试证实这在更普遍的情况下也是成立的。 图15.具有K5个用户和 T ~ \widetilde T T 30s的示例测试用例的 ( P F ) 2 S (PF)^2S (PF)2S框架评估(a)公平性(b)吞吐量增益超过PF-EXP使用BGE算法模拟数据速率预测偏移量。
延迟参数 D s t a r v e d ϵ D_{starved}\epsilon Dstarvedϵ如第IV部分所述该框架使用延迟阈值Dstarved来优先处理“饥饿”用户。PF-EXP调度程序使用 ϵ \epsilon ϵ来隐式控制延迟。现在我们探讨了PF-EXP调度程序 ϵ \epsilon ϵ和 P F 2 S PF^2S PF2S框架 D s t a r v e d D_{starved} Dstarved上放宽延迟参数所获得性能提升。在图16a中我们根据图10进行了匹配这些参数在延迟容忍度0.25-2s的范围内具有可比的延迟参数。该图显示PF2S框架继续优于PF-EXP调度程序并且收益只有轻微的变化。 图16.使用RRE与CMPM-CHLS时 ( P F ) 2 S (PF)^2S (PF)2S Framework的性能增益(a)为 ( P F ) 2 S (PF)^2S (PF)2S Framework D s t a r v e d D_{starved} Dstarved和PF-EXP调度程序 ϵ \epsilon ϵ的延迟参数变化提供图9b中的测试用例(b)对15个测试用例进行统计评估其中K10和 T ~ \widetilde T T 30s以获得不同的覆盖图分辨率值。
覆盖地图分辨率在上述结果中覆盖地图段大小为25m×25m。图16b显示了15个测试用例的框架增益其中K10和 T ~ 30 s \widetilde T30s T 30s作为功能与地图段大小。随着段大小变得合理大性能不会显着下降因为较大的段会导致对更大区域的信道质量属性的平均。这表明粗信道测量对框架是有用的。
9. 结论和未来工作
我们描述了一项广泛的无线测量研究以及 ( P F ) 2 S (PF)^2S (PF)2S框架的设计和基于跟踪的性能评估。我们表明通过利用慢衰落该框架(由各种算法组成)可以提供显着的吞吐量增益同时改进或保持公平水平。最后我们对不同参数和假设的敏感性进行了研究。
个人疑点及解答 什么是慢衰减、什么是快速衰减 在信道中慢衰落是指信号幅度的长期变化是传播环境在较长时间、较大范围内发生变化的结果又被称为长期衰落、大尺度衰落快衰落则描述了信号幅度的瞬时变化与多径传播有关又被称为短期衰落、小尺度衰落。 多径传播使信号包络产生的起伏虽然比信号的周期缓慢但是仍然可能是在秒或秒以下的数量级衰落的周期常能和数字信号的一个码元周期相比较故通常将由多径效应引起的衰落称为快衰落。即使没有多径效应仅有一条无线电路径传播时由于路径上季节、日夜、天气等的变化也会使信号产生衰落现象。这种衰落的起伏周期可能较长甚至以若干天或若干小时计称这种衰落为慢衰落。 我的理解是如果是慢衰落的话人可以明显感知到信号变差的过程快衰落应该是人没反应过来就恢复了 为什么说无线信道状态是一个平稳过程 无线信道状态只受到快速衰落的影响变化是瞬时的很快就能恢复无线信道状态大体是一个平稳过程它不会随着时间的推移而发生显著的变化。 E c / I o E_c/I_o Ec/Io和RSSI是什么意思 RSSI即频率带内接收的总功率表示信号强度指标 E c / I o E_c/I_o Ec/Io表示特定导频信号的功率与带内总功率包括干扰和噪声的比率表示信号质量 文中说的向扇区报告其信噪比( E c / I o E_c/I_o Ec/Io)选择适当的通道化码并将其映射到可行的数据速率是什么意思 通道化码是一种将多个通道的信息编码为单个通道传输的方法可以提高传输效率、减少干扰和噪声的影响、提供更好的灵活性和可扩展性。 RSCP值是什么 RSCPReceived Signal Strength and Channel Power值是一种指示接收信号强度的参数。它通常用于无线网络中表示接收到的信号强度和信道功率。 在无线网络中RSCP值可以提供关于信号质量和连接稳定性的信息。通常情况下RSCP值越高表示接收到的信号强度越大连接质量越好。相反RSCP值越低表示接收到的信号强度越小连接质量越差。 这逼文章在到底在讲什么 文章提出了一种场景一辆车行驶了较长的距离较快经过了三个扇区过程中明显能感觉到网络质量变差到恢复的过程慢衰落指出PF调度算法在类似场景下将失效提出了有限视距的PF算法FPF。 用户分配到的时间乘上数据速率就是用户得到的总服务目标是让扇区内所有用户的总服务最大化得到公式1 限制条件s.t.是指分给某个用户i后其余的就只能是0了所以所有用户求和是1。 用梯度上升法求解对某个 α i , j α_{i,j} αi,j求导log求导是倒数乘以某个常数不用管log里面照抄 α i , j r i , j α_{i,j}r_{i,j} αi,jri,j求导剩个 r i , j r_{i,j} ri,j在分母。 那这玩意的分母准确的说有三部分过去、现在和未来三部分组成 那么问题来了未来这部分怎么求所以文章分别建立了R和α的预测算法。 文章做了个覆盖图预测算法先算出车在哪个位置用这个位置的信号质量当成车的信号质量信号质量查表看数据速率。 然后用了三个算法来算α怎么分配然后做了一些实验。
