在机会主义车辆路由方案中，通过扩展的Q学习算法自适应调整候选转发集的大小

《Computer Networks》：Adaptively tuning candidates forwarding set sizes via extended Q-learning in opportunistic vehicular routing schemes

本文提出基于动态Q学习的自适应候选转发集（CFS）大小调整方案，结合延迟敏感和延迟容忍型应用需求，优化车辆网络中的机会路由性能，在高速公路和城市场景中验证其显著降低端到端延迟（平均31.1%-41.2%）、减少路由开销（33.3%-53.79%）并提升广播增益（23.14%-57.44%），同时保持与现有方案相当的可靠传输率。

　　

穆罕默德·纳德里（Mohammad Naderi）| 穆罕默德·甘巴里（Mohammad Ghanbari）| 阿巴斯·阿尔加瓦尼（Abbas Arghavani）

伊朗德黑兰伊斯兰阿扎德大学计算机工程系，科学与研究分部

摘要

机会主义路由通过在候选转发集合中转发数据包来实现车辆网络中的可靠通信。确定候选转发集合大小的主要方案是基于过滤和固定大小的策略。这些传统方法经常导致有限的共享带宽使用效率低下。这种缺陷会进一步对服务质量参数（如传输延迟）产生不利影响。我们的目标是在利用机会主义路由固有的超高可靠性的同时解决这些问题。为此，我们提出了一种创新的、自适应的候选转发集合大小调整策略，该策略由动态Q学习算法驱动。Q学习参数根据多种服务质量指标进行校准，包括数据延迟、传输比率和数据生成率，以及实时车辆条件（如信号强度和移动特性）。结果表明，在高速公路场景下，与PRO、DSTOR、FROB和ACRS方案相比，我们的方案平均可将端到端延迟分别降低31.1%、40.46%、36.42%和14.39%；将路由开销分别降低33.3%、46.29%、52.49%和50.18%；并将广播增益分别提高23.14%、56.15%、39.9%和9.44%。此外，与这些基准方案相比，我们的方案在城市环境中的改进还包括端到端延迟平均降低26.76%、41.2%、33.26%和9.4%；路由开销平均降低33.9%、47.49%、53.79%和50.38%；广播增益平均提高12.58%、57.44%、35.05%和6.52%。同时，在两种场景下，平均传输比率和丢失率的变化都基本保持在1%左右，表明改进幅度较小。

引言

车辆网络（VNs）作为无线通信领域中快速发展的一个分支，已成为智能交通系统（ITS）的基本组成部分[1]。利用先进的无线通信技术，车辆网络致力于提高驾驶员的意识、确保交通安全并增加乘客的便利性[[2], [3], [4]]。这些网络支持多种通信模式，包括车对车（V2V）、车对基础设施（V2I）和车对一切（V2X），以支持各种应用，这些应用可以分为对延迟敏感和对延迟容忍的[5]。对延迟敏感的服务（如交通违规警报、碰撞前警告和车道变换辅助）对于道路安全至关重要，需要极低的延迟[6]。相反，对延迟容忍的应用（包括多媒体流媒体、天气更新和在线游戏）则需要较大的数据吞吐量，同时对延迟的敏感性较低[7]。尽管车辆网络具有巨大潜力，但仍有许多挑战阻碍了所需服务质量（QoS）的实现。这些挑战包括车辆的高移动性、动态的交通模式、有损的无线信道和有限的带宽[8,9]。在人口密集的城市地区，建筑物、交叉路口和道路布局等障碍物会干扰信号传播[10]，因此选择高效的路由策略对于确保可靠通信、维持有效的数据传输和优化资源利用至关重要[11]。传统的路由协议（如单播、多播和广播）通常分为基于拓扑的或基于位置的[9,12]。然而，这些传统方法在网络拥塞、端到端延迟增加和较高开销成本的情况下常常遇到困难[13]。为了解决上述问题，机会主义路由（OR）范式最近因能够利用多个传输机会并动态适应不断变化的网络条件而受到越来越多的研究关注[[14], [15], [16], [17], [18]]。OR方案通过利用节点的移动性，通过多跳通信机会主义地将消息传递到目的地[18]。一般来说，OR可以分为基于发送者和基于接收者的方法¹[19]。在基于发送者的OR中，源节点根据预定义的指标优先选择其一对一跳邻居，形成一个候选转发集合（CFS），该集合参与数据包的传输[[19], [20], [21]]。此类系统的性能在很大程度上取决于CFS大小的有效调整，这直接影响吞吐量、延迟和资源效率。为基于发送者的OR开发一个稳健的CFS选择策略是一个重要挑战，这也是本研究的主要焦点。

尽管基于发送者的OR可以实现超高可靠的通信，但其效率受到多种限制：

1)

数据包冗余：同一CFS成员中的隐藏终端和重叠的重传计时器会导致重复传输，加剧广播风暴问题，并在密集场景中降低传输比率。

2)

传输延迟：除了消息传输比率外，传输延迟也是评估消息传输性能的重要指标[22]。然而，在机会主义路由范式中，数据包在CFS队列中经常需要等待很长时间，从而导致显著的端到端延迟。

确定能够作为候选转发集合转发数据包的邻居节点数量对于缓解前述破坏性影响至关重要。然而，在确定最佳CFS大小方面存在显著的研究空白，特别是在以下方面：1）同时考虑车辆拓扑条件（如高车辆速度）和应用需求，以及衰落因素；2）避免为了实现超高可靠性而牺牲某些QoS方面，并防止不必要的网络资源消耗；3）交互式应对动态车辆环境带来的挑战，以管理间歇性的拓扑变化。认识到这些研究空白，我们使用交互式Q学习算法来解决它们，如下一小节所述。

当前的CFS大小调整策略主要依赖于固定大小或基于过滤的方法。这些方法优先考虑可靠性，但经常忽视延迟约束，部分原因是难以将延迟直接嵌入优化模型[23]。此外，由于选择最佳CFS大小是一个NP难问题，仅靠数学模型不足以满足车辆应用的多样化和有时相互冲突的需求。基于学习的方法可以通过与环境持续交互、结合实时反馈并相应地调整决策来克服这些挑战。Q学习特别适合这一点，因为它可以在不需要事先了解环境的情况下通过探索学习最佳策略[24]。它已经被应用于车辆网络的路由[25]、卫星-地面集成网络（STINs）[14]、月球表面自组织网络[15]、水下物联网（IoUT）[16]、纳米传感器网络[17]、无人机（UAVs）[26]、软件定义车辆网络（SDVN）中的区域选择[27]、SDVN中模糊成员函数的调整[28]等。受此启发，我们采用了一个扩展的Q学习框架，根据应用需求和网络条件动态调整CFS大小。

指定候选转发集合大小最常用的策略是基于固定值和基于过滤的方案。表1总结了每个类别中的关键先进方案。在基于固定大小的类别中，选择一个预先确定的固定值（例如，前12个优先级高的邻居节点）来形成候选转发集合[[29], [30], [31], [32], [33], [34], [35], [36], [37]]。更准确地说，在[[29], [30], [31], [32], [33], [34], [35], [36], [37]]中，每个数据广播包在其所有过程中都使用相同的预定义固定值，无论应用类型和车辆网络条件如何。这些方法采用各种标准和策略来优先选择邻居节点，然后选择固定数量的邻居节点。相反，基于过滤的候选转发集合优化概念是通过从邻居节点中移除一些节点来形成候选转发集合[21]。基于阈值的方法[[38], [39]]、比较邻居与转发节点的标准[[39]]、基于冗余概率的方法[19]和基于自适应的方法[41]是最常用的CFS过滤技术。无线网络中也存在其他方法，但由于它们与车辆网络的不同特性，本文尚未对其进行审查。有兴趣的人可以参考[21]进行进一步研究。虽然固定大小方案在稀疏网络中可能有效且易于实现，但在密集环境中会导致过多的冗余和广播风暴。尽管基于过滤的方法具有更好的适应性，但它们通常无法保证低延迟。较新的自适应策略[[19], [20], [41]提供了进一步的改进，但通常会导致较高的时间复杂度。重要的是，现有的研究工作没有充分解决在不同应用需求下可靠性和延迟之间的权衡，本文旨在填补这一空白。

• 我们提出了一种自适应调整候选转发集合大小（ATFS）方案，用于机会主义车辆路由，该方案同时考虑了数据包传输比率和延迟。
• 2)
  我们扩展了Q学习算法，加入了环境感知的奖励函数、学习率、折扣因子和探索策略，以适应不断变化的车辆拓扑和多样化的应用需求（即对延迟敏感和对延迟容忍的应用）。
• 3)
  我们证明了所提出的ATFS方案在各种交通流中，无论是在城市还是高速公路场景下，都能显著提高端到端路由延迟、路由开销和广播增益，同时保持与基于过滤和固定大小的CFS大小方案相当的可靠性。

本文的其余部分组织如下。第2节描述了我们的系统模型、邻居发现机制和问题陈述。第3节详细介绍了所提出的方案。第4节阐述了分析结果和我们的方法与现有最佳方案的性能评估。最后，第5节提出了一些结论性和未来的工作方向。

假设

假设

所提出方案中的车辆网络被表示为一个无向图 $V(t$ 表示时间 $E(t$ 表示时间 $t$ 表示车辆之间的无向链接。只有当两个车辆节点具有双向通信链接时，它们才能直接通信。所提出的方案假设每个车辆节点都有一个唯一的标识符（ID）。此外，假设每个车辆节点都配备了GPS（全球定位系统）。

ATFS：自适应调整候选转发集合大小

所提出的扩展Q学习框架如图3所示。根据图3中的框架，奖励函数计算考虑了传输比率、传输延迟、接收到的ACK消息以及从同一CFS成员广播的重复数据消息之间的平衡。它还利用了邻居节点的链接过期时间和接收到的数据包信号强度，以及各种数据生成率来调整学习率。

性能评估

本节通过仿真全面评估了我们方案的性能，并与现有的最佳CFS大小调整方案进行了比较。仿真设置的详细信息如下所述。

结论

我们提出了一种在机会主义路由范式中的转发集合大小调整方案。为此，我们引入了一个多维Q学习算法，考虑了不同的数据包大小。所提出的方案将来自各种应用的数据包及其CFS列表视为状态，并将各种CFS大小视为动作。所提出的Q学习的即时奖励、学习率、折扣因子和探索策略都根据不同的QoS进行了自适应调整。

CRediT作者贡献声明

穆罕默德·纳德里（Mohammad Naderi）：撰写 – 审稿与编辑、撰写 – 原稿、可视化、验证、软件、方法论、调查、形式分析、数据整理、概念化。穆罕默德·甘巴里（Mohammad Ghanbari）：撰写 – 审稿与编辑、监督、项目管理、形式分析、数据整理、概念化。阿巴斯·阿尔加瓦尼（Abbas Arghavani）：撰写 – 审稿与编辑、撰写 – 原稿、监督、项目管理。