每周文章分享-184

在基于水下和地面射频(RF)的网络中，如何在用户之间公平地分配网络接入是一个重要的问题，而本文从则规划的角度研究了考虑公平性的多用户无线网络的时空调度问题。论文的工作重点在于水声网络(UAN)，但所提出的策略也适用于地面射频网络，因此使用“非有线”网络的非常规术语来进行概括。在马尔可夫决策过程(MDP)框架下，将该调度问题表述为一个顺序决策问题。然而，由于机动性、时变和公平性等特性，经典的无限视野RL调度不再适用。

当环境探索的代价较为昂贵时，规划比在线学习更有效，但这也导致实现比例公平时当前和未来奖励之间的累加结构不再成立。论文提出了一种近似的加性奖励函数，实现了动态的规划。针对节点移动性引起的模型改变，论文提出了一种新的重规划方案来优化策略更新的时机。另外，论文使用了样本的近似降低了计算复杂度。

本文要解决的是考虑比例公平性，在有限视野MDP背景下的UAN调度问题。方法被总结为基于采样的公平规划与重规划准则(SBFP-RC)方案。该方法的创新和贡献具体如下：

1）将考虑公平性的调度问题表述为MDP，并提出了一个公平加权的奖励函数，保证了当前和未来奖励之间的可加性关系；

2）提出了一种基于采样的线性近似规划方案，并推导了连续两步逼近误差的上界，通过数值验证了该结果，表明逼近误差呈指数衰减；

3）基于两个模型之间效用差异的理论上限，开发了一个重新规划标准来确定策略更新时间。

（1）网络模型

图1  网络模型示意图

论文考虑一个由N个用户（移动设备、传感器、无人航行器等）和一个基站组成的多用户通信系统，如图1所示，(a)是水下场景，(b)是陆上场景。基站(BS)配备了M个等间距阵列元素，元素间间距为d。论文重点关注下行场景，其中BS向用户发送数据。在每个时隙中，根据缓冲区的状态，BS选择要服务的用户子集。为了提高可靠性和减少干扰，BS执行发射波束形成。优化目标是使整个系统的下行容量最大化，同时在一定程度上保证服务的公平性。

（2）问题建模

系统状态由两个部分组成：缓冲区的队列长度和信道状态。用户在时隙t中的底层缓冲状态向量表示为：

（1）

其中，向量中单个元素是用户n的缓冲状态，表示缓冲区中的数据包数量，如图2所示。

图2  缓冲状态向量

为了描述时变信道，论文采用了Gilbert Elliot模型，该模型是一个用来近似基于分组的传输信道特性的马尔可夫过程。经典的Gilbert Elliot模型假设通道条件为两种状态，论文将其扩展到Nc个离散状态，以更好地捕捉通道的时间演化行为。时隙t中的信道状态向量表示为：

（2）

其中，向量中元素是用户n的信道状态，表示等效信道增益系数H的离散值，如图3所示。最后，将系统状态定义为缓冲状态向量与通道状态向量的组合。

图3  信道状态向量

在每个时隙中，浮标选择一个用户子集来服务。时隙t中的决策向量表示为：

（3）

向量中元素是用户n的决策变量，用户n选择是否服务，如图4所示。

图4  决策向量

用中断容量的平方来衡量用户n在时隙t中的瞬时服务质量，该容量考虑了带干扰信噪比的中断概率：

（4）

除了容量之外，公平性是多用户资源分配问题的另一个重要方面。如何在不同用户之间权衡效用改进的问题是困难的，并且取决于效用函数本身。在本文中，考虑比例公平衡量来制定调度问题。形式上，将有限范围内的预期单用户效用表示为un，并将优化问题表述如下：

（5）

（6）

将时隙t中的单用户剩余效用(utility-to-go)函数定义为：

（7）

在经典MDP设置中，可用的剩余效用函数是递归定义的，在动态规划(DP)中可以利用它来降低计算复杂性。然而，在本文场景中，当前和未来奖励之间因为比例公平效用函数的对数函数不再满足线性关系，无法使用递归表达式，这会导致一个指数级大的决策空间，难以计算。

为了重新使用递归的剩余效用函数，论文推导了剩余效用函数的近似表达：

（8）

通过这种方式可以进一步近似出最优效用函数，而它可以递归地计算：

   （9）

（3）基于采样的线性近似规划

上文解决了效用函数无法递归的问题，但由于状态空间的大小随着用户数量呈指数增长，即使对于少量用户，计算量依然非常大。为了解决此问题，作者进一步提出基于采样的公平规划(SBFP)方案。

为了减轻在线计算，首先从动作值函数（Q函数）入手，当给定Q函数，在线决策可以通过在决策空间上最大化Q函数的和来进行。然而，Q函数的精确表示需要一个含有指数N级元素数量的表，随着N的增加，这很快变得不可行。为了解决Q函数表示的困难，采用参数化函数形式作为近似，定义线性近似的Q函数为：

（10）

通过离线计算权矩阵W，并在线最大化近似Q函数得到相应的最优决策。近似的剩余效用函数与Q函数相关：

（11）

参数化函数形式使得能够递归地计算近似的Q函数和剩余效用函数。然而，这种递归逼近结构可能会导致误差的积累，并且在逼近的几个步骤之后，逼近的效用函数可能不够准确而无法使用。因此，作者进一步证明了所提出的近似策略实际上不会受到严重的误差积累的影响。

本文中，作者关注的是线性逼近引起的渐近误差，假设有足够数量的样本，期望估计中的误差可以忽略不计。但由于可以有效地从信道预测器中收集样本，因此渐近结果是有意义的。

确定线性逼近中误差传播特性是确定逼近误差边界的关键。在每个时间步长中，近似由两个阶段组成，这两个阶段都会引入误差。在第一阶段，收集样本，根据前一步近似的效用函数来评估时隙t中的Q函数；在第二阶段，通过优化权重矩阵来计算近似Q函数的最佳线性函数表示。剩余效用函数以及Q函数的误差上界推导结果为：

（12）

（13）

作者证明，当前步骤t的误差上界由两部分组成：前一步的衰减误差和新产生的误差。因此，在t之后步骤中引起的误差会随着优化中后退一步而衰减（即t减少1）。由于误差衰减现象，步骤t中的误差是关于线性逼近步骤数T - t的次线性函数。本文中，根据最坏情况值计算边界，因此实际性能将优于误差分析预测的结果。

（4）在线重规划

接下来，作者将网络中用户的移动性纳入前文提出的规划算法。随着用户的移动，期望信号和干扰信号的强度会发生变化。瞬时中断容量是剩余效用函数和Q函数的关键构建块，同样受用户位置的影响。因此，基于过去用户位置构建的策略最终可能会因为模型转移而变得不准确，应该在策略变为次优之前对其进行更新。但是在水声网络中，计算量大的策略重新规划过程应该尽可能避免。然而重新规划页并不总是必要的，因为用户的移动性是有限的，即时奖励的轻微变化可能不会改变最优策略。为了确定恰当的重新规划时间，需要理解从瞬时容量的改变到策略空间变化的映射关系。

论文求得环境变化引起的效用函数差异的上界为：

（14）

给定计算的边界，只有当效用差异大于阈值时，才进行重规划。论文将提出的与上述重规划准则相关联的SBFP算法记为SBFP-RC。