在指数接触模型和帕累托接触模型下的概率性DTN（动态网络）路由

《Ad Hoc Networks》：Probabilistic DTN routing under exponential and Pareto contact models

延迟容忍网络中，现有路由协议多孤立考虑接触间隔时间（ICT）或接触持续时间（CD），本文提出MDPR协议首次统一建模ICT与CD的协同影响，基于指数分布适配车联网场景，采用帕累托分布优化人本网络，并设计低内存EWMA参数估计方法，实验表明其相比SOTA协议提升37%投递率，降低40%平均延迟和44%平均开销。

　　

李先生

美国加州大学洛杉矶分校计算机科学系，洛杉矶，美国

摘要

在延迟容忍网络（DTNs）中，路由面临的主要挑战是间歇性的连接性，这使得准确预测消息传递变得困难。尽管许多协议使用了启发式方法或部分数学模型，但在对整个接触过程进行建模方面仍存在显著差距。现有的方法通常只考虑节点接触之间的时间（接触间隔时间）或接触期间的时间（接触持续时间），而很少同时考虑两者。这种遗漏是关键性的，因为成功的传递不仅需要节点相遇，还需要有足够的接触时间来完成数据传输。

本文通过提出一种新颖的、轻量级的模型驱动概率路由（MDPR）协议来填补这一空白。我们开发了一个统一的分析模型，用于计算端到端的传递概率，该模型明确考虑了接触间隔时间和接触持续时间之间的相互作用，解决了以往工作中的关键问题。我们基于两种经过实证验证的分布来构建这个模型：车辆网络的指数分布和以人为中心的网络的帕累托分布。为了确保在资源受限的节点上能够实际应用该协议，我们还提出并评估了一种高效、低内存的基于指数加权移动平均（EWMA）的在线参数估计方案。

我们通过对旧金山出租车、MIT Reality和GeoLife数据集进行广泛的基于轨迹的模拟来验证MDPR的有效性。结果证实了我们模型驱动方法的优越性。MDPR在传递率上比现有协议高出最多37个百分点，在平均延迟上减少了40%，在平均开销成本上减少了44%。这些发现表明，我们全面的概率模型提供了一个更准确的效用指标，为现实世界的DTN场景提供了一种稳健、高效且实用的路由解决方案。

引言

延迟容忍网络（DTNs）是一类具有间歇性连接、长时间或可变延迟以及缺乏同时端到端路径的特征的网络[1]。这些条件在车辆网络[2]、野生动物追踪[3]和深空通信[4]中很常见，导致传统的路由协议（如TCP/IP）无效。因此，DTNs依赖于存储-携带-转发范式，即节点机会性地将数据包（消息）传输给遇到的其他节点，希望消息最终能够到达目的地。

这一范式中的主要挑战之一是路由决策：一个有效的协议必须智能地决定何时以及向谁转发消息，以最大化传递概率同时最小化资源消耗。已经提出了多种路由策略，从简单的泛洪协议到更复杂的启发式和社会感知方法。例如，开创性的PRoPHET协议[5]引入了一个随着接触次数增加而增加的传递预测性指标。虽然这些方法通常有效，但许多方法依赖于临时制定的指标和固定系数，可能无法准确捕捉节点移动性和接触机会的真实随机性。

一种更严格的方法是对接触过程进行正式的数学建模。然而，正如我们在相关工作综述中指出的，文献中仍然存在显著差距。一些协议建模了节点接触之间的时间（接触间隔时间，ICT）[6]，而其他协议则建模了接触期间的时间（接触持续时间，CD）[7]，但很少有协议同时建模两者。这种遗漏是关键性的：成功的传递不仅取决于节点的相遇，还取决于相遇时间足够长以完成数据传输。

本文通过提出一种新颖的、轻量级的模型驱动概率路由（MDPR）协议来填补这一空白。通过建立一个严格的概率框架，MDPR同时考虑了节点相遇频率和传输窗口限制，解决了以往工作中持续时间建模的缺失问题。

我们的建模方法优先考虑移动性的随机性而非系统级约束。虽然带宽波动、缓冲区容量有限和能量限制等因素确实会影响传递成功率，但它们通常可以通过标准的排队或资源策略来管理。相比之下，接触间隔时间（ICT）和接触持续时间（CD）代表了环境的不可控随机性。因此，我们的模型将带宽和缓冲区大小视为输入参数，使我们能够独立解决接触机会本身的复杂概率问题。

我们的核心贡献如下：

• •
  我们开发了一个统一的分析模型，用于计算DTN中的端到端传递概率。与以往孤立考虑接触频率和持续时间的工作不同，我们的模型基于接触间隔时间（机会的到来）和接触持续时间（机会的效用）之间的相互作用来明确推导成功概率。
• •
  我们基于两种经过实证验证的分布来构建这个模型，以覆盖不同的移动性范式：（1）车辆网络的指数分布和（2）以人为中心的网络的帕累托分布，后者能够捕捉到人类移动性的重尾特性。
• •
  我们提出了两种实用的参数估计方案，一种是基于最大似然估计（MLE）的标准滑动窗口方法，另一种是基于指数加权移动平均（EWMA）的高效、低内存在线方法，确保协议在资源受限的节点上也能运行。
• •
  我们使用旧金山出租车、MIT Reality和GeoLife数据集进行了广泛的基于轨迹的性能评估。我们的结果验证了我们模型驱动方法的准确性，证明MDPR在传递率上比现有协议高出最多37个百分点，在平均延迟上减少了40%，在平均开销成本上减少了44%。这些发现表明，我们全面的概率模型提供了一个更准确的效用指标，为现实世界的DTN场景提供了稳健、高效且实用的路由解决方案。

介绍

延迟容忍网络（DTNs）是一类具有间歇性连接、长时间或可变延迟以及缺乏同时端到端路径的特征的网络[1]。这些条件在车辆网络[2]、野生动物追踪[3]和深空通信[4]中很常见，使得传统的路由协议（如TCP/IP）无效。因此，DTNs依赖于存储-携带-转发范式，即节点机会性地将数据包（消息）传输给遇到的其他节点，希望消息最终能够到达目的地。

这一范式中的主要挑战之一是路由决策：一个有效的协议必须智能地决定何时以及向谁转发消息，以最大化传递概率同时最小化资源消耗。已经提出了多种路由策略，从简单的泛洪协议到更复杂的启发式和社会感知方法。例如，开创性的PRoPHET协议[5]引入了一个随着接触次数增加而增加的传递预测性指标。尽管这些方法通常有效，但许多方法依赖于临时制定的指标和固定系数，可能无法准确捕捉节点移动性和接触机会的真实随机性。

一种更严格的方法是对接触过程进行正式的数学建模。然而，正如我们在相关工作综述中指出的，文献中仍然存在显著差距。虽然一些协议建模了节点接触之间的时间（接触间隔时间，ICT）[6]，其他协议则建模了接触期间的时间（接触持续时间，CD）[7]，但很少有协议同时建模两者。这种遗漏是关键性的：成功的传递不仅取决于遇到合适的节点，还取决于相遇时间足够长以完成数据传输。

本文通过提出一种新颖的、轻量级的模型驱动概率路由（MDPR）协议来填补这一空白。MDPR通过建立一个严格的概率框架，同时考虑了节点相遇频率和传输窗口限制，解决了以往工作中持续时间建模的缺失问题。

我们的建模方法优先考虑移动性的随机性而非系统级约束。虽然带宽波动、缓冲区容量有限和能量限制等因素确实会影响传递成功率，但它们通常可以通过标准的排队或资源策略来管理。相比之下，接触间隔时间（ICT）和接触持续时间（CD）代表了环境的不可控随机性。因此，我们的模型将带宽和缓冲区大小视为输入参数，使我们能够独立解决接触机会本身的复杂概率问题。

我们的核心贡献如下：

• •
  我们开发了一个统一的分析模型，用于计算DTN中的端到端传递概率。与以往孤立考虑接触频率和持续时间的工作不同，我们的模型基于接触间隔时间（机会的到来）和接触持续时间（机会的效用）之间的相互作用来明确推导成功概率。
• •
  我们基于两种经过实证验证的分布来构建这个模型，以覆盖不同的移动性范式：（1）车辆网络的指数分布和（2）以人为中心的网络的帕累托分布，后者能够捕捉到人类移动性的重尾特性。
• •
  我们提出了两种实用的参数估计方案，一种是基于最大似然估计（MLE）的标准滑动窗口方法，另一种是基于指数加权移动平均（EWMA）的高效、低内存在线方法，确保协议在资源受限的节点上也能运行。
• •
  我们使用旧金山出租车、MIT Reality和GeoLife数据集进行了广泛的基于轨迹的性能评估。我们的结果验证了我们模型的准确性，证明MDPR在传递率上比现有协议高出最多37个百分点，在平均延迟上减少了40%，在平均开销成本上减少了44%。这些发现表明，我们全面的概率模型提供了一个更准确的效用指标，为现实世界的DTN场景提供了稳健、高效且实用的路由解决方案。

本文的其余部分安排如下。第2节回顾相关工作。第3节详细介绍我们的数学模型。第4节介绍参数估计技术。第5节描述路由策略。第6节提供全面的性能评估，第7节总结本文并概述未来工作的方向。

相关工作

延迟容忍网络（DTNs）的路由技术已经从简单的泛洪机制发展到复杂的、上下文感知的策略。在本节中，我们通过将现有协议与我们提出的模型驱动概率路由（MDPR）进行比较，来回顾最先进的技术。

数学模型

本节开发了我们提出的路由协议的核心数学框架。目标是推导出一个精确的分析表达式，用于计算在未来相遇时成功将消息传递到目的地的概率。这个概率将作为我们转发决策的主要效用指标。为了说明这一概率过程的关键组成部分，图1展示了一个典型的DTN场景，突出了接触间隔时间之间的相互作用

参数估计

第3节中提出的概率模型依赖于从接触间隔时间和接触持续时间的基础分布中得出的参数。为了使模型在现实世界的应用中有效，每个节点必须从其与其他节点的接触历史中动态且高效地估计这些参数。本节详细介绍了两种实现这一任务的方法：一种使用最近观察结果的滑动窗口的基线方法，以及一种基于

路由策略

路由策略被设计为一个基于效用的概率转发协议。核心原则是只有当某个节点提供更高的最终传递概率时，才将消息复制到该节点。这种方法通常被称为机会主义转发，旨在通过避免冗余或低价值的传输来逐步增加消息在网络中的传递可能性，从而节省资源。

性能评估

在本节中，我们对提出的模型驱动概率路由（MDPR）协议进行了全面的性能评估。我们首先验证了内部参数估计的稳健性，并分析了协议的理论资源复杂性。然后，我们使用三个真实世界的移动性轨迹——旧金山出租车轨迹、MIT Reality轨迹和GeoLife数据集，将MDPR与几个已建立的基准进行了比较。

结论与未来工作

在本文中，我们解决了现有DTN路由协议的一个根本性限制：在评估传递概率时忽略了同时建模接触间隔时间和接触持续时间的问题。我们提出了一种新颖的、轻量级的模型驱动概率路由（MDPR）协议，该协议基于一个统一的分析模型，明确考虑了这种相互作用。通过将我们的模型基于经过实证验证的指数分布和帕累托分布，我们为这两种情况量身定制了该协议

利益冲突声明

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