【优质信源】计划01--一种无线通信中的高能效和低延时调度方法介绍 - 知乎每日精选

Reviewed by: @甜草莓 @Skyfall;前置知识：通信原理、马氏决策过程，马氏链稳态概率，长时平均分析

众所周知，由于移动设备（主要是手机）电池电量的受限，因此如何提升通信的能量效率（利用尽量少的能量发送给定数据）一直是通信中的研究热点。另一方面，随着通信业务量激增，从节能减排的角度，倡导绿色通信也是一个发展趋势。

• 以运营商2015年的总和能耗为例，中国的三大运营商在一年的总和能耗大概能达到671万吨标准煤，这相当于整个社会综合能耗的千分之二。
• 中移动相关负责人就指出：“我们看未来五到十年，我们需求的流量可望增长一千倍。能耗问题是必须要解决的。”

通信中还有一个很重要的研究目标就是低延时。随着各种通信场景的涌现，实时传输业务，比如即时信息，流媒体，监控以及跟踪业务，这些无线通信场景得到越来越广泛的应用。因此，对通信传输的延时控制和优化成为了一个重要研究课题，如Ephremides，Gallager, EI Gamal, Ata, Modiano, Shroff等知名学者都对这个问题很感兴趣，在不同的场景下使用不同的建模方式和解决方案对该问题进行研究。

在实际场景中，无线信道会因为传输环境中的散射、反射等因素导致的多径效应，产生时变的信道状态，也就是信道质量的好坏程度会随着时间变化，而信道质量会影响通信的能量效率。

如下图所示，在信道条件好的时候（绿色），移动设备可以用相对低的传输功耗发送数据；但是在信道条件不好的时候（红色），为了克服坏信道的影响，移动设备需要使用更高的传输功耗发送数据。假设需要发送4次数据，不考虑信道好坏则最快可以在4个时隙内完成传输（1次低能耗+3次高功耗）；如果想最小化移动设备的功耗，那么需要只在好信道条件下传输，算上等待信道变好的时间，一共需要7个时隙。

那么很好理解，如果随机产生的数据包到达后，移动设备不考虑信道状态就直接进行传输，由于无需等待所以延时可以很低，然而当遭遇恶劣信道时，能量效率也会很低。如果数据包到达后可以缓存在移动设备中，然后等待信道条件好的时候再进行机会传输，那么虽然可以降低能耗，但延时也会增大。

因此，该场景下的功耗和延时之间存在天然的折中关系，总结如下图所示：

很多通信的理论研究中会考虑离散的时间模型，即将连续的时间划分为若干离散的时隙。我们用符号 来表示时隙的编号。

接下来为了刻画前文所述的通信调度过程，需要选择合适的时变信道模型、数据包到达模型，以及传输功耗模型。

块衰落信道是一种应用广泛的用于刻画信道衰落的数学模型，在每个时隙内的信道状态保持不变，而在不同时隙间的信道状态相互独立。为了方便读者理解，我们考虑二元信道，也就是信道状态只分为好和坏的状态，分别用0和1表示，其分布概率为：

另一方面，考虑数据包的到达也是随机的。同样为了方便理解，我们考虑0-1到达，也就是每个时隙内最多有1个数据包到达移动设备。第 个时隙初的任务包到达数 的分布概率为:

考虑移动设备在每个时隙内移动设备最多发送1个数据包，用符号 表示第 个时隙内的发送数量：

• 当 ，也就是不发送时，认为传输功耗为0；
• 当 时，信道条件好和坏情况下所需要的传输功耗 分别为 和 ，满足

通过以上信息，可以得到移动设备的缓存状态满足如下更新方式：

其中， 为第 个时隙结束时移动设备缓存中的数据包个数， 为移动设备缓存的大小（最多能存放多少数据包）。

可以把缓存状态看作一个队列，然后通过排队论中的经典结论Little定理[1]（队列中数据包的平均排队延时等于平均对长除以数据包到达率）可以将平均排队延时表示为：

根据此可以发现一个很直观的结论，即移动设备缓存中数据包个数越多，则会产生更高的排队延时。另一方面，根据之前队列更新公式，可以发现让 保持为1，也就是发送数据包可以降低 的值。

本工作的目标就是通过在每个时隙动态地调整 或者 ，在给定平均延时约束下 ，最小化移动设备的能量消耗：

上述优化问题可以表示为：

可能部分读者看到这里已经会觉得有点乱，但这已经是最最简单的情况了。更简单地来说，我们需要做的是，根据系统状态（包括缓存状态 ，任务包到达 和信道状态 ）来决定当前时隙是否需要发送，即 或者 。

接下来我们将介绍如何求解这个优化问题，并给出了一个违反直觉且有趣的结论。

我想用尽量简单的方式来解释我们的求解方法。通过观察队列更新方式，发现缓存状态 具有明显的马尔可夫性质，也就是其状态只跟上一时隙的状态 有关，而与更早时隙的状态无关。因此，一个很直观的思路是用马尔可夫链来描述缓存状态 ，而数据包到达 的分布和调度策略 的选择，则决定了马氏链的状态转移及其概率。

马氏链如下图所示，由于数据包的到达和发送都是0或1，因此每个状态只能在相邻状态间转移，而这个转移方式取决于 的分布参数 ，以及调度策略 ，逻辑为：

这里有一个有趣的结论，也就是 的对应关系。一般来说，我们会觉得每一组给定的状态 应该要对应一个最佳的 。换句话说，根据每一种系统状态，都会有对应的确定的 。

实则不然，这里用概率调度方法来描述调度策略，为：

也就是，每一种系统状态，都不会是一个确定的 ，而是按照概率 来随机选择 的取值。例如 代表各以50%的概率选择 和 。

虽然可能看起来有点奇怪，但在数学上是很好理解的，因为概率调度的决策空间更大。换句话说，确定性调度的可行解也是概率调度的可行解，所以换成概率性调度相当于拓展了优化问题的可行解域，因此概率调度下最优解的性能一定优于（最差也是等于）确定性调度。例如 代表以100%（确定性的）概率选择 。

以上是一个带约束的马尔可夫决策过程，根据状态（state），依据策略（policy）去决定动作（action）。因此策略就可以决定状态的转移概率，进而得到马氏链的稳态分布

数据包的平均延时和移动设备的平均功耗均可以由马氏链 的稳态分布 和概率调度策略 表示，为：

而马氏链的稳态分布 则完全取决于概率调度策略 ，那么用 就可以描述完整的原优化问题，具体为：

后两行为马氏链的平衡方程，其中 为状态转移矩阵，其中元素均为策略 ，任务包到达分布 （给定的参数）和信道参数 （给定的参数）的线性组合。

这个问题无法直接求解，但通过挖掘其内在的线性特征，可以将其转化为能在多项式时间内求解的线性规划（Linear Programming）问题。

方法非常简单，定义新的优化变量 ，满足归一化条件(线性约束) 。然后，原问题改为：

其中矩阵 是新的状态平衡方程，由 导出，元素为 与任务包到达分布 （给定的参数）和信道参数 （给定的参数）的线性组合，详细过程在此省略。有兴趣可以直接看论文。

如图所示，仿真结果揭示了该场景下的平均延时和传输功耗之间的最优折中关系。

• 通过容忍更好的平均延时，可以节省更多传输功耗；
• 通过付出更多传输功耗，可以降低数据包的平均延时；

• 这篇论文探究了点对点通信场景中，平均延时和功耗的折中关系，并提出了一种基于带约束的马氏决策过程（CMDP）的概率调度策略，可以实现最优的延时-功耗折中关系。
• 相比确定性调度，即给定任意状态下的确定性 ，概率调度方式可以实现更优的折中关系。
• 后续考虑了多发送情况，也就是 。如下图所示，根据香农容量公式，更高的发送速率会使得传输功耗指数增加。得到结论，更高的发送速率可以降低延时，但也会降低能量效率，从另一个角度反映了延时-功耗间的折中关系。

• 后续工作[3]揭示了多发送和多信道状态状态下的最优解具有门限结构，也就是当信道条件不好的时候（好的时候队列非空则一定发送）队列长度高于某门限，则一定发送；低于某门限，则一定不发送；当处于两个门限之间时，为概率性发送。门限结构存在性的理论证明工作是这一工作的主要贡献。

本文章由 flowerss 抓取自RSS，版权归源站点所有。

查看原文：【优质信源】计划01--一种无线通信中的高能效和低延时调度方法介绍 - 知乎每日精选