原文信息

Sharma, Nikhilesh, Nicholas Mastronarde, and Jacob Chakareski. "Delay-sensitive energy-harvesting wireless sensors: Optimal scheduling, structural properties, and approximation analysis." IEEE Transactions on Communications 68.4 (2019): 2509-2524.

关键字：马尔可夫决策过程、能量收集、延迟敏感无线传感、近似动态规划、结构特性

1 问题背景

能量受限 (energy-constrained) 的无线传感器通常运行在动态信道 (dynamic channel) 和对数据传输延迟非常敏感的环境中。这种传感器具备能量收集能力，能利用环境中的能量（例如环境光或射频能量）维持自身能量所需。这种新兴应用的成功关键在于及时传输采集的数据，而成功部署此类系统的关键是理解此类系统在不同运行条件下的基本性能极限，以及有效计算达到该极限的最佳策略。

文章考虑一个在衰落信道上传输延迟敏感数据的能量收集传感器 (energy-harvesting sensor, EHS)，并将其构建为延迟敏感能量收集调度 (delay-sensitive energy harvesting scheduling, DSEHS) 问题。尽管EHSs可以在不更换电池的情况下自主运行，但能量收集源中的流量负载、能量收集和信道变化随机性对传感器功率管理、传输功率分配和传输调度提出了新的挑战。截止原文发表，许多研究确定了多种计算最优策略的方法，但它们并没有提供对其结构性质的一般性见解。本文作者在文章中将 DSEHS 问题构建为一个马尔可夫决策过程 (Markov Decision Process, MDP)，并分析了其性质，在此基础上量化了在给定能量收集的情况下最小化队列延迟的最优调度策略的长期性能，并提出一种低复杂度的近似值迭代算法来计算近似最优策略，其在近似精度、计算复杂度和内存之间提供了一种可控的权衡。具体而言，文章探讨了以下问题：

1. 如何建模时延敏感的能量收集调度问题 (DSEHS) ？
2. 最优价值函数关于状态是否有良好的结构性质？（最优价值函数即最优策略下使得目标函数能取得的最小值）
3. 如何设计近似值迭代算法？
4. 近似值迭代算法的有效性如何？

2 无线传感器模型

3 延迟敏感能量收集调度问题

如果数据包到达、能量收集和信道动态是已知且固定的，则可以离线进行 PDS 值迭代。如果动态是非平稳的，那么该算法可以周期在线执行，以随着动态的变化更新PDS值函数。但是如果缓冲区和电池容量足够大，那么任何需要计算和存储每个单一状态的值函数的表格方法由于维度指数增大变得难以处理。此外，如果缓冲区和电池大小是无限的，这种表格式方法就不适用。

离线 (offline) 是指已知数据包到达、能量收集和信道动态下，可以直接计算最优的价值函数，并获得最优策略，从而可以部署执行。在线(online) 是指上述过程未知，在实际部署中需要不断更新和估计，从而不断接近最优策略。

决策后状态价值函数性质

4 近似算法

上述最优策略可以通过如PDS价值迭代或策略迭代算法获得最优策略。尽管如此，由于维度影响，尤其是状态变量需要遍历电池队列、数据队列、信道三个维度，因此文章利用上一节提出最优策略的性质，文章设计了一个 AVI 近似算法，从而降低算法复杂度。

分段平面近似误差有界

为了在缓冲-电池平面上进行空间自适应近似，文章使用四叉树数据结构，其叶节点顶点定义网格，且四叉树的每个叶子被分成两个三角形。所有叶节点的平面共同组成了图2所示的分段平面近似如下。

近似 PDS 值迭代 (AVI) 算法

算法2给出了AVI (approximate value iteration)算法。

5 数值结果

最优PDS值函数的结构性质

图4a、图4g和图4b、图4h分别给出了最优PDS值函数和策略。最优PDS值函数(i)在队列积压(命题1和3)中不减小且差异越来越大，(ii)在电池状态(命题2和4)中不增大且差异越来越大。在较好的信道状态下(-4.68 dB)，最优值函数的幅度较小，因为该状态的长期预期成本较低。

图4c和图4d分别为贪心值函数和策略。我们观察到最优策略比贪婪策略更保守，因为它在低电池状态下不传输数据包。这是因为在给定数据到达、能量到达和通道动态的情况下，最优策略权衡其当前调度操作对其未来性能的影响。

图4e、4i、图4f和图4j分别显示了使用动态改进的四叉树生成的近似PDS值函数和策略(在更高的缓冲状态下得到20个更精细的平面)。近似PDS值函数保留了最优PDS值函数的结构。此外，由近似PDS值函数派生的策略(即AVI策略)具有与最优策略相似的结构，并且比最优策略更冒险，但比贪婪策略更谨慎。

近似解与最优调度策略和贪婪策略的性能

贪婪策略在给定可用能量的情况下传输尽可能多的积压数据包，即

综上所述，这些结果表明，所提出的解决方案不仅比贪婪策略提供更多的传感器数据（因为当有更少的溢出时，更少的传感器数据丢失），而且在使用更少的能量的同时具有更低的延迟。文章认为同时改进这些指标是问题的内在特征，当优化延迟指标（排队延迟和溢出）时，改进电池指标对于有效地服务传入流量是必要的。

参考文献

[1] N. Mastronarde and M. van der Schaar, “Fast reinforcement learning for energy-efficient wireless communication,” IEEE Trans. Signal Process., vol. 59, no. 12, pp. 6262–6266, 2011.

[2] N. Mastronarde and M. van der Schaar, “Joint physical-layer and system- level power management for delay-sensitive wireless communications,” IEEE Trans. Mobile Comput., vol. 12, no. 4, pp. 694–709, 2013

[3] N. Salodkar, A. Bhorkar, A. Karandikar, and V. Borkar, “An on-line learning algorithm for energy efficient delay constrained scheduling over a fading channel,” IEEE J. Sel. Areas Commun., 2008.

[4] L. Kaelbling, M. Littman, and A. Moore, “Reinforcement learning: A survey,” J. Artif. Intell. Res., pp. 237–285, 1996.