摘要: 1．本文的创新点
延迟容忍网络泛指那些泛指由于节点移动等原因而没有稳定的端到端传输路径、甚至大部分时间处于中断状态的一类网络。与传统网络相比，延迟容忍网络拓扑动态变化，节点间没有稳定的端到端传输路径，路由问题是当前研究的热点问题之一。本文则研究了概率联系的延迟容忍网络单播路由问题。我们首先假设网络中的节点以一定的概率相遇，然后以期望传输延迟最小为优化目标，研究单副本报文传输的最优路由策略,并提出了一个最优机会路由算法——蛙跳（Leapfrog）路由算法。主要贡献及创新点如下：
? 首先，本文通过一个例子介绍了延迟容忍网络机会路由的概念，并通过形式化和理论分析证明了“在概率联系的延迟容忍网络中，最优机会路由是所有可能的路由策略中最优的”。
? 其次，本文揭示了最优机会路由的本质规律：在最优机会路由策略下，节点总是选择那些距离目标节点的最小期望传输延迟比自身到目标节点的最小期望传输延迟还要小的节点作为中继节点来转发报文，即报文总是由高延迟的节点向低延迟节点以一种蛙跳的方式进行传输。通过严格地理论分析和证明，我们还导出了计算每个节点到目标节点最小期望传输延迟的递推公式。在此基础上，我们基于反向Dijkstra算法的思想提出了Leapfrog算法，能够高效地计算每个节点的最小期望传输延迟。
? 最后，本文还在公开的延迟容忍网络数据集的基础上进行了仿真实验，实验结果证实：蛙跳路由算法的性能明显优于已有的算法。

2．实现方法
本文提出了概率联系的延迟容忍网络最优机会路由算法——蛙跳（Leapfrog）路由算法，并证明了其最优性。该算法包括预处理阶段和路由阶段。在预处理阶段，各个节点首先通过基于洪泛策略的传染病（Epidemic）路由算法发布自身与其它各节点的相遇概率，从而获知了整个网络中任意一对节点的相遇概率；然后，各个节点根据我们所提的Leapfrog算法计算自身到目标节点的最小期望传输延迟；在路由阶段，每个节点按照蛙跳路由策略转发报文，即只有在遇到最小期望传输延迟比自身还小的节点时转发报文，否则不转发该报文。本文的重点则是通过严格的理论分析，证明了蛙跳（Leapfrog）路由算法的最优性，即能够取得最小的期望传输延迟。具体方法主要分为两步：
? 第一步，我们首先将任意的路由策略形式化为一组路由选择函数，每个节点对应一个路由选择函数，函数的参数为实时的网络连接状态，即节点在路由选择时与其它节点的联系状态，函数的输出值为一个中继节点，表示给定一个网络连接状态，节点会选择该中继节点转发报文。寻找最优路由策略就变为了确定这样的一组最优的路由选择函数。然后，我们进一步地将路由选择函数的值域定义为候选中继节点集，并简单证明了“给定一个最优路由选择函数，则唯一确定一个候选中继节点集；给定一个候选中继节点集，也唯一确定了一个最优路由选择函数”，从而将寻找最优路由选择函数的问题转化为了确定最优候选中继节点集的问题。
? 第二步，我们首先分析求解了给定节点的最优候选中继节点集，并证明了一个重要的性质“一个节点属于另一个节点的最优候选中继节点集当且仅当该节点的最小期望传输延迟小于另一个节点的最小期望传输延迟”。这一重要性质不断给出了最优候选中继节点集的组成，还揭示了最优机会路由具有“蛙跳传输特性”的本质规律。然后，我们根据这一性质推导出了计算每个节点最小期望传输延迟的递推公式，并运用反向Dijkstra算法的思想设计了Leapfrog算法来实现这一计算。一旦每个节点的最小期望传输延迟计算出来了，节点的最优候选中继节点集和也就确定下来了，相应的最优路由选择函数也就确定下来了。

3．结论及未来待解决的问题
本文分别通过理论和实验证明了“在概率联系的延迟容忍网络中，最优机会路由是所有可能的路由策略中最优的”，并揭示了最优机会路由的本质规律，给出了一个最优机会路由算法——蛙跳（Leapfrog）路由算法。
本文仅仅解决了概率联系的延迟容忍网络中的单副本报文传输的问题，未来将解决多副本传输的问题。
4．实用价值或应用前景
延迟容忍网络涵盖了因特网以外的许多通讯网络，如星际网络、乡村网络、战争网络、野生动物监控与追踪网络、移动Ad Hoc网络和无线传感器网络、PSN(Pocket Switched Networks)网络等等。本文则揭示了在这些网络中实施最优机会路由的本质规律，能够为这些网络设计高效路由算法提供理论支持，具有重要的实用价值。