具有抢占意识的在线AoI调度算法在两状态马尔可夫信道上的应用

《Computer Networks》：Preemption-Aware Online AoI Scheduling over Two-State Markov Channels

实时无线系统中信息时效性优化研究，提出两态马尔可夫信道下预emption调度框架，结合鲁宾逊-蒙罗阈值学习算法与斜率驱动自预emption机制，理论证明收敛性并实现平均信息时效性降低22%-33.34%。

　　

张凌鸿|邱新涛|黄亮

浙江工业大学计算机科学与技术学院，中国杭州，310013

摘要

在车辆安全、云游戏和工业物联网等应用中，提供及时的信息至关重要，因为过时的更新与延迟更新一样有害。信息年龄（Age of Information, AoI）指标通过测量接收到的更新的新鲜度来满足这一需求。一个关键挑战是决定何时生成新的更新，以及在动态信道条件下是否中断正在进行的传输。虽然基于等待的AoI调度已经得到了广泛研究，并且被证明可以产生阈值结构，但抢占（preemption）机制仍然没有得到充分探索，尤其是在马尔可夫（Markovian）无线信道中，数据包可能会在不良状态下滞留。本文为两状态马尔可夫信道开发了一个具有抢占意识的调度框架。我们设计了一种基于斜率的自我抢占机制来丢弃陈旧的数据包，并将其与Robbins-Monro阈值学习相结合，以在线优化等待决策。我们从理论上证明了在马尔可夫信道中通过抢占实现AoI最小化的收敛性。在多种延迟分布和真实物联网数据集上的仿真结果表明，我们的方法始终能够比基线策略实现更低的AoI，特别是在重尾或变化较大的条件下。特别是在重尾延迟分布下，平均AoI降低了多达22%，在真实数据集上实现了33.34%的AoI降低。这些结果确立了抢占作为实时无线系统中AoI控制的一个原则性和可分析的组成部分。

引言

新兴的无线应用不仅要求高吞吐量，还要求严格的时效性保证。例如，在车辆网络中，每辆连接的自动驾驶车辆必须不断向周围车辆广播其位置和运动状态，以确保道路安全和避免碰撞[1]、[2]、[3]。这样的系统通常涉及数百个节点同时交换更新，从而创建了一个高度动态的通信环境。同样，在移动云游戏和增强现实领域，终端设备必须从边缘服务器接收实时视频或感官流，即使是很小的延迟也会严重降低用户体验[4]。在工业物联网和智慧城市监控中也有类似的要求，传感器必须迅速报告状态变化以实现可靠的控制。这些场景有一个共同的需求：信息的新鲜度与可靠性或吞吐量同样重要，而传统的指标（如平均延迟或吞吐量）不足以捕捉这一点。

为了解决这一限制，引入了信息年龄（Age of Information, AoI）指标[5]。AoI定义为自最近接收到的更新生成以来的时间，直接量化了目的地信息的新鲜度。与吞吐量或延迟不同，AoI强调更新是何时生成的，使其成为实时监控和控制的自然性能指标[6]、[7]。因此，AoI迅速成为无线网络的基石，最近的研究将其应用范围扩展到连接的自动驾驶车辆[8]、不可靠网络中的吞吐量-AoI权衡[9]，以及考虑时效性方差的第二阶优化框架[10]。这些例子证实了AoI作为理论构建和实际设计目标的双重作用。

AoI控制中的一个核心挑战是如何决定何时生成和传输新的更新。如果更新发送得太频繁，它们会争夺信道资源并增加拥塞；如果更新延迟太久，目的地接收到的信息就会过时。这自然导致了等待策略的设计：在完成一次传输后，源必须决定是否以及等待多长时间后再采样和传输下一次更新。大量的研究表明，等待策略的最佳结构通常可以简化为阈值规则，而在线随机逼近方法（如Robbins–Monro）可以在不知道信道统计信息的情况下学习这个阈值[11]、[12]、[13]。这些工作构成了在线AoI调度的当前技术水平。

同时，另一个基本决策却受到的关注较少：当有更新更新鲜或信道条件改善时，是否抢占正在进行的传输。抢占会在传输过程中丢弃数据包并重新开始传输新的数据包，以短期成本换取长期的信息新鲜度。一些研究在多源系统[14]、排队模型[15]和概率调度[16]中探索了这一想法，表明抢占可以显著降低AoI。然而，与等待策略相比，抢占机制仍然没有得到充分探索，通常被经验性地处理。在具有马尔可夫衰落信道的无线网络中，抢占尤其关键，因为数据包可能会在不良状态下滞留并严重过时。尽管如此，关于如何在这种环境中设计抢占机制知之甚少，也没有针对在线抢占学习的理论保证。这一差距限制了AoI优化在最需要的场景（如车辆安全和工业物联网监控）中的适用性。

本文通过为两状态马尔可夫信道开发一个具有抢占意识的AoI调度框架来解决这些差距。我们专注于在一般的两状态马尔可夫信道中通过自我抢占来最小化信息年龄，这对应于网络状态良好和不良的情况。我们研究了两个关键决策：（i）在生成下一次更新之前是否以及等待多长时间，以及（ii）是否抢占正在进行的传输。本文的主要贡献总结如下：•

我们为两状态马尔可夫信道提出了一种新的AoI策略，该策略结合了基于阈值的等待和基于斜率的自我抢占机制。这种设计能够在信道条件改善时实时中断陈旧的数据包传输，并且始终优于Lowait算法等经典方案。

•

我们基于Robbins-Monro迭代提出了一个在线随机逼近框架，用于在自我抢占存在的情况下学习等待时间阈值。我们建立了有限时间性能界限，表明AoI偏差允许一个亚线性学习项

$O(1/\sqrt{K})$，再加上一个与抢占概率成比例的显式残差项，从而量化了马尔可夫信道中自我抢占引入的基本权衡。

•

我们在多种传输延迟分布（指数分布、对数正态分布、均匀分布和帕累托分布）和真实的物联网传感器数据集下评估了所提出的方法。特别是在重尾延迟分布下，平均AoI降低了多达22%，在真实数据集上实现了33.34%的AoI降低。在重尾延迟下，这种改进最为显著（对数正态和帕累托分布）。

本文的其余部分组织如下。第2节回顾了与AoI、基于阈值的学习和抢占机制相关的工作。第3节描述了系统模型并制定了问题。第4节提出了具有抢占意识的调度策略，第5节开发了在线学习和控制实现，并在第5.2节给出了理论保证。第6节使用仿真和真实世界数据集报告了性能评估结果。最后，第7节总结了本文。

小节片段

无线网络中的AoI

早期关于无线网络中信息年龄（AoI）的研究主要集中在排队理论模型上。例如，黄等人[17]分析了多类M/G/1排队系统中的信息时效性，通过凸优化推导出峰值AoI（PAoI）的表达式，并强调了更新频率和排队延迟之间的权衡。后续的研究[18]、[19]、[20]、[21]将AoI分析扩展到更复杂的排队结构和多跳设置。

随着

系统概述

我们考虑一个由源节点和目的节点组成的点对点无线通信系统，如图1(a)所示。在无排队缓冲区的按需生成模型下，源可以随时生成更新数据包并通过时变无线信道将其传输给目的地。在成功接收到更新后，目的地会发送一个即时且无误的确认（ACK）[29]，之后源决定是否等待

具有抢占意识的调度策略设计

本节提出了一种两阶段调度策略，旨在最小化时变无线信道上的长期平均AoI。在每个帧中，该策略做出两个连续决策：启动更新之前的等待时间，以及响应信道改善而抢占正在进行的传输的可能性。这些决策在帧的不同阶段进行，但共同设计用于自适应地调节信息新鲜度。等待时间控制是

在线学习和控制实现

第4节开发的具有抢占意识的调度策略假设知道最优AoI斜率γ^?和未来帧的持续时间，这些在实践中通常是未知的。本节提出了一个完全在线的框架，无需事先了解信道统计信息或传输延迟分布即可实现实时决策。

我们从第4.1节开始，介绍了一种Robbins-Monro随机逼近方法，该方法迭代地从

性能评估

在本节中，我们通过数值示例展示了所提出的PAOS算法在时间平均AoI方面的性能。

结论

本文通过共同解决两个耦合的控制决策来研究两状态马尔可夫信道上的AoI最小化：（i）生成下一次更新之前的服务后等待时间，以及（ii）当信道条件改善时是否抢占正在进行的传输。我们提出了PAOS，这是一个具有抢占意识的调度框架，它结合了基于斜率的自我抢占规则和Robbins-Monro阈值学习。在理论方面，我们建立了有限时间性能

CRediT作者贡献声明

张凌鸿：撰写——原始草稿、可视化、软件、方法论、形式分析、数据整理。邱新涛：撰写——审阅与编辑、可视化、验证、软件、数据整理。黄亮：撰写——审阅与编辑、监督、项目管理、资金获取、概念化。

利益冲突声明

黄亮报告称，他的工作得到了浙江省省级大学基本研究基金的财政支持。如果有其他作者，他们声明没有已知的竞争性财务利益或个人关系可能影响本文报告的工作。