在具有不可靠链接的网络中，基于信息效用路由的时代

《Computer Networks》：Age of information utility-based routing in networks with unreliable links

多跳无线网络中Age-of-Information敏感的净效用模型与最优路由算法研究。提出融合信息时效性惩罚、链路可靠性影响和动态转发成本的效用模型，推导链路重传的期望效用衰减闭式表达式，将问题转化为带解析权重边的新最短路径问题，设计在线路由决策机制并验证其有效性。

　　

阿卜杜拉齐兹·萨万（Abdalaziz Sawwan）| 肖明军（Mingjun Xiao）| 吴杰（Jie Wu）

美国宾夕法尼亚州费城天普大学计算机与信息科学系

摘要

在具有不可靠链接和异构转发成本的多跳无线网络中，研究消息的新鲜度对于实时监控和控制应用至关重要。现有的不可靠网络路由协议通常优化跳数、预期传输次数或简化的基于时间的效用模型，这些模型可能忽略了信息价值随时间推移在目的地处如何衰减的问题。在这项工作中，我们引入了一种对信息年龄（AoI）敏感的“网络效用”（net-utility）公式，该公式明确地将更新的传递收益与信息年龄的新鲜度惩罚以及在不可靠链接上重传的累积转发成本联系起来。我们考虑了随机周期性的消息更新生成，其中更新之间的时间是随机的，平均时间为T，每次更新都携带一个内在收益b，同时会产生节点依赖的转发成本和由于链接故障导致的随机额外延迟。我们提出了一种最优路由算法，通过实时动态选择路由并丢弃那些预期效用贡献不足以抵消其剩余预期成本的更新来最大化长期预期效用。通过推导出在多次尝试不可靠链接直到首次成功时的预期效用衰减的封闭形式表达式，我们将路由决策简化为具有解析计算出的边权重的最短路径计算和在线转发/丢弃规则。当链接尝试失败（在随机故障检测时间后检测到）时，发送方将承担额外的转发成本和与等待时间成比例的额外新鲜度损失。在我们的基线分析和算法中，我们采用了标准的链路层自动重传请求（ARQ）规则，该规则会立即重试“相同”的下一个跳，直到首次成功。我们还讨论了如何通过仅替换每个链接的条件均值项，将相同的最短路径简化方法扩展到非指数型的经验故障时间分布。

引言

在许多多跳无线系统中，及时传递信息是一级要求，包括网络物理监控和控制、车辆和空中传感、紧急和灾难响应以及工业物联网。在这些环境中，路由决策不仅受到路径长度或能量消耗的限制，还受到（i）链接不可靠性的限制，这会导致重传和随机额外延迟，以及（ii）由于能量、拥塞或运营激励而在中间节点产生的异构转发成本的影响。因此，对一个更新“良好”的路由策略可能对下一个更新来说并不是最优的，因为“传递更新的价值”取决于目的地当前的陈旧程度以及预期新更新到达的速度。

“信息年龄”（Age of Information，AoI）已成为量化目的地端新鲜度的原则性指标；它衡量了自最近接收到的更新生成以来的时间长度[1]，[2]。大量关于AoI的研究集中在调度、采样和传输策略上，这些策略旨在在排队和干扰约束下“最小化”平均/峰值AoI [3]。补充的多跳研究探讨了路由和链接激活如何影响AoI和吞吐量的权衡[4]。然而，在许多运营网络中，目标并不是单纯的最小化AoI：运营商通常关心新鲜度与传递更新所支付的成本（能量、费用或资源消耗）之间的明确权衡，如果即将有更新到来，他们可能会理性地选择“丢弃”过于延迟的更新。

受到这一差距的启发，我们研究了在“不可靠”多跳网络中基于效用的路由，用于随机生成的状态更新。我们的关键建模选择是优化一个“网络效用”，该效用明确地结合了（a）消息传递时的内在收益，（b）随着传递时目的地当前AoI增加的新鲜度惩罚，以及（c）沿路由产生的累积转发成本，包括在链接故障下的重传成本和延迟。关键在于，更新的效用是在“更新流”的背景下评估的：它取决于“之前成功接收到的”更新的时间以及“下一个”更新到达的预期时间尺度（通过随机更新周期）。这与独立处理数据包的标准路由公式以及不附加每个更新的具体收益/成本的AoI最小化公式不同。

从算法角度来看，我们在完全了解链接可靠性和延迟的情况下，证明了这种对AoI敏感的网络效用最大化存在一个“高效”的最优解。我们推导出了在捕获故障在随机等待时间后检测到的经验现象的故障时间模型下，尝试不可靠链接直到首次成功时的预期效用衰减的封闭形式表达式。这将随机路由问题转化为一个具有解析计算出的边权重的图上的最短路径问题，从而可以使用经典的多项式时间最短路径算法。重要的是，由此产生的路由规则是“在线”的：中间节点可以在当前更新的剩余预期净贡献变为负值时决定继续转发或丢弃该更新。

在真实网络中的可行性由一个轻量级反馈机制支持：接收方在接收到更新后广播一个简短的确认信息，其中仅包含更新序列ID，使中间节点能够在不维护大量状态的情况下跟踪最新传递的更新。由于这种反馈信息量小且可以优先处理，因此在低频率的状态更新情况下，可以合理假设其传播速度快于更新生成周期。在这种标准的“单次更新飞行”机制下，每个更新都可以根据目的地最新接收到的序列进行路由。图1展示了该问题的示意图。

这项工作的新颖之处不仅在于使用AoI作为性能指标，还在于将AoI“嵌入到成本-收益效用中”，并据此为不可靠的多跳网络推导出一个“最优”的路由规则。具体来说，我们做出了以下贡献：

•

针对不可靠多跳路由的AoI敏感网络效用模型。我们制定了一个效用模型，该模型在奖励传递收益的同时，对（i）通过目的地AoI造成的新鲜度损失和（ii）包括链接故障下重传引起的累积转发成本进行惩罚。该模型针对随机周期性更新生成进行了定制，并明确考虑了更新流上下文（之前传递的更新和下一个更新的预期时间尺度）。

•

通过预期效用衰减将其简化为最短路径问题。我们推导出了在尝试不可靠链接直到首次成功时的封闭形式预期效用衰减表达式，从而得到了可以解析计算的边权重。这将随机效用最大化问题转化为具有多项式复杂度的动态最短路径计算。

•

基于在线的最优路由规则。在最优路径结构的基础上，我们提供了一个在线转发规则，当当前更新的剩余预期净贡献变为负值时可以丢弃该更新。这直接解决了在预期即将有更新到来时，传递过于陈旧的更新不值得的情况。

•

在代表性拓扑上进行评估。我们通过在稀疏、密集和类似ARPANET的图上进行模拟来验证所提出方案的有效性，展示了不可靠性、成本和AoI敏感性参数如何共同影响路由决策和实现的效用。

本文的其余部分组织如下。第2节回顾了相关工作。第3节提出了问题的一般模型。第4节提出了不可靠网络的一般情况的最优解。第5节展示了模拟结果，以验证算法的效率。最后，第6节给出了结论。

相关工作

我们将本文与三个主要研究方向进行对比：（i）多跳无线和传感器网络的可靠性和成本意识路由指标，（ii）具有时间敏感目标的基于效用的路由，以及（iii）AoI理论和以AoI为中心的优化（包括多跳设置）。我们的贡献位于这些方向的交叉点：我们将AoI嵌入到不可靠多跳路由中的每个更新的成本-收益效用中，并推导出一个（期望意义上的）最优最短路径结构

提出的模型

在本节中，我们展示了归因于随机周期性消息更新的基于AoI的效用模型。此外，我们还讨论了用于将消息从源节点s传递到目的节点d的不可靠网络模型。

问题的最优解

在本节中，我们提供了不可靠问题的一般最优解，并证明了我们提出解决方案的最优性。我们假设信息始终是完整的。

实验设置

我们在三种代表性拓扑上评估了算法2的多个参数设置。这些拓扑分别显示在图5和图7中：图5(a)代表稀疏拓扑（结果显示在图6的左列中），图5(b)代表密集拓扑（结果显示在图6的右列中），图7代表骨干ARPANET拓扑（结果显示在图9中）。

我们研究了两个代表性的AoI权重值：$\delta =1$

结论

在这项工作中，我们提出了一个对不可靠多跳网络敏感的信息年龄（AoI）效用模型，在该模型中，每个随机生成的更新都具有随AoI衰减的时间敏感效用。该模型捕捉了在基于AoI的效用下转发成本和延迟引起的新鲜度损失之间的明确权衡。在这个模型下，我们提出了一种最优路由算法，用于最大化传递更新的预期效用。该算法利用了最优路径

CRediT作者贡献声明

阿卜杜拉齐兹·萨万（Abdalaziz Sawwan）：撰写 – 审稿与编辑、撰写 – 原始草稿、可视化、验证、软件、方法论、调查、形式分析、数据整理、概念化。肖明军（Mingjun Xiao）：撰写 – 审稿与编辑、验证。吴杰（Jie Wu）：撰写 – 审稿与编辑、验证、监督、资源管理、项目管理、方法论、调查、资金获取、概念化。

利益冲突声明

作者声明他们没有已知的可能会影响本文报告工作的竞争性财务利益或个人关系。