英语原文共 4 页，剩余内容已隐藏，支付完成后下载完整资料
延时容忍网络路由协议的改进——PRoPHETV2
萨摩格·克拉西克 吕勒奥理工大学 [samo.grasic@ltu.se]
埃尔温·戴维斯 傻瓜咨询顾问公司 [elwynd@folly.org.uk]
安德斯·林格伦 瑞典计算机科学学院 [andersl@sics.se]
阿薇瑞·多利亚 独立咨询顾问公司 [avri@acm.org]
摘要
对于延迟和中断容忍网络得研究已经发展成为一个成熟的研究领域。PRoPHET是在对延时容忍网络的早期研究中发展形成的一种用于延时容忍网络的路由协议，并且很多人都研究过这一协议。在本篇论文中，我们调查研究了给路由协议是如何演变以迎接网络中的新挑战，这些新的挑战都是通过研究和实践经验所确定了的。
我们建议对PRoPHET中的路由度量计算方式作一些小的修改，这些小的修改有能够减轻该协议中的一些问题并改进该协议的性能。在做出这些修改之后，我们定义了该协议的更新版本，即PRoPHETV2。我们运用仿真模拟的方式来验证改进后的协议，并将其性能与原始版本的协议的性能以及其他一些路由协议的性能进行了比较。评估是通过现有的网络部署的痕迹和综合移动模型来做的。因为该路由协议的基本原理保持不变，所以将现有的协议实现方式通过有限的努力迁移到新的路由协议中是可以做到的。
分类和主题描述
C.2.2 网络协议[路由协议]
概述
算法，设计
关键词
延时容忍网络、路由
介绍
在过去的十年中，对延时容忍网络的研究已经从一个小生境的研究领域逐渐发展成为网络中的主流研究课题。这一领域相比它早起时已经变得更加成熟，这些年我们在这一领域已经进步了很多。为了利用时间可调度的机会主义无线自组织网络在其部署区域的连通性，我们需要一种有效的路由方案。学界对于延时容忍网络的研究大多集中在路由协议上，并且已经在研究论文中提出了了许多的协议。PRoPHET是在对延时容忍网络的早期研究中所定义的路由协议之一。该协议也是唯一在互联网研究专门工作组的一个互联网草案的协议细节中具有明确的技术规范的延时容忍网络路由协议。因此，它经常被用作标准检测程序，并与其他延时容忍网络路由协议相比较以评估其他延时容忍网络路由协议的性能，以及用于一些真实世界的测试和部署。PRoPHET使用与其他节点先前相遇的历史以及网络传递属性来修剪洪泛分布树从而优化网络中包的转发。
根据对PRoPHET的评估以及我们自己对协议的部署与模拟的经验，我们认识到该协议需要发展以迎接新的挑战并提高其自身性能。在这篇论文中，我们审视了以前的研究，这些研究还有提高的空间；并且我们讨论了一些由于糟糕的实验设置而导致的不足，同时我们发现对PRoPHET做出一些小的修改可以解决这些不足并提高该路由协议的性能。然后我们描述了对PRoPHET的建议改进方式，并将改进后的算法称为PRoPHETV2，并且通过仿真评估了改进后的协议的性能，而且将改进后的协议的性能与原始版本的协议的性能以及其他一些路由协议的性能进行了比较。
背景
PRoPHET使用与其他节点先前相遇的历史以及人类交往中的固有传递属性来估算传递的可预测性（在论文的后面部分简称为DP）P（A,B）。在任意节点A中，对节点A的所有已知目的地节点B保存一个DP表。当节点相遇时，相遇的节点彼此交换DP表，并且根据其他节点的标识信息以及下面的公式计算所得的接收表更新它们自身的DP表。对于A遇到的节点B。节点A使用公式（1）来更新它的DP表。是一个可以配置的常数。使用公式1可以使频繁相遇的节点获得一个较高的DP值（的建议值为0.75）。
1
节点A通过与其相遇的每个节点B间接相连的全部目的地i的DP值也会根据节点B发送到节点A的表中的值更新，这是因为DP具有传递性（如果节点A与节点B频繁地相遇，并且节点B与节点i频繁地相遇，那么尽管节点A不与节点i直接相遇，节点A对于目的地是节点i的消息是一个很好的载体，因为节点A可以把消息通过节点B传递给节点i）。这种传递更新使用公式2来计算节点A和节点i之间的传递概率，其中beta;是一格可配置的常数（beta;的建议值为0.25，该文被收录入2011年4月的互联网草案：draft-lindgren-dtnrg-prophet-09.txt中）。
2
为了消除来自网络的陈旧信息，节点A的DP表对于所有的目的节点i根据公式（3）周期性地减小，式中gamma;是一个常数（gamma;的建议值为0.998），是T自上次老化过程运行到本次更新所用的时间。
3
在本节的剩余部分，我们将分析一些已经发现的可以提高PRoPHET性能的情况，利用这些情况可以为观察到的行为找到原因并且考虑如何改进当前状态。
N4C部署的经验
N4C项目在瑞典山脉的偏远地区部署了真正的延时容忍网络。在一年一的度夏季部署期间对N4C系统的一个组成部分的测试实现了PRoPHET。在2009年的夏季测试后的第一个星期，有人注意到一部分数据骡（数据骡是一种媒介，它物理地支撑存储计算机以在远程位置之间创建一个数据通信链路）拒绝将捆绑在因特网网关上的捆绑包送到直升机基地的固定节点。调查表明，尽管数据骡从来没有直接与网关相接触，网关节点的数据骡的DP实际上比直升机基地上的节点的DP高。在检查其他节点的DP的过程中，我们发现这些节点的DP都非常高，而且他们与实际网络拓扑不相符。根据PRoPHET的传递更新方程（2）可以找到这个不可预知的协议行为的原因。当遭遇频率不均匀地分布在网络上并且节点间的相遇很频繁时，老化机制不能将DP值快速地降低足够的的大小，那么上述问题就有可能会出现。在我们的例子中，把节点分成了两个部分，一部分节点（在村庄中的）的相遇频率是比较高的，另一部分节点的相遇频率比较低（数据骡、边界节点和网关）。
停车场问题
在它（即停车场问题）的最初形式中，有一些实例：如果一些节点聚集到一起并且频繁地交换它们的DP设置，那么这些节点根据PRoPHET将会是它们的DP值产生不合理的变化。停车场问题的命名就是出自上述情况，对这种情况的讨论与把许多使用延时容忍网络设备的用户聚集到超市停车场的情况相关。在对N4C部署的数据的分析中，我们更清楚地认识到即使没有集群的设备，我们也能看到许多相遇只相隔很短的时间，但是人类希望的是一个有着几个小时或几天时间间隔的模式。实际上，这些相遇中有许多是由于片状无线宽带条件所导致的重新连接，将每次这种重新连接都算作节点之间的相遇实际上把节点真正的相遇次数高估了。如果PRoPHET把这些重新连接都算作节点之间新的相遇的话，那么相遇的节点的DP值将会增加的太多并且移动模式模型将被扭曲。这与理论上假设的停车场问题非常相似。
2.3链式拓扑的例子
为了展示在某些设置中节点的DP在演化过程中随着时间的推移所产生的一个问题，我们在ONE仿真平台上做了一些仿真。我们用下图1所示的拓扑结构来分析以及说明了关于PRoPHET中传递更新方程式的一个观察结果。这个简单的网络由4个节点A、B、C、D组成，这4个节点构成了一个链式拓扑。节点之间的联系只持续很短的时间，并且在任意时刻在网络中只有一个连接。
节点A、B代表 节点B、C、D代表高
低相遇频率的区域 相遇频率的区域
图1 链式拓扑
节点A和B只会在仿真开始时连接一次，代表低相遇频率的网络区域。在这之后B—C、C—D将会定期地连接与断开连接，代表高相遇频率的区域。使用这种简单的方案，我们调查研究节点A和B的初始连接的信息怎样在网络中传递以及如何进入高相遇频率的区域。为了做好研究，我们只关注节点B、C、D到A的DP值。
如图2所示，在节点A和B初始相遇后的一小会后，即使这两个节点只有一次相遇，P（B，A）仍然持续增长。经过22次迭代后,尽管节点C与节点A没有相遇，但P（C，A）甚至比P（B，A）还要大。因此，根据PRoPHET的转交策略，节点A的任何数据流都不会从节点C传递到B。上述情况是由于PRoPHET中的传递公式2的可加性以及只用一个数字来表示DP的现实所导致的，这就使得节点不可能确定某一信息是从哪个节点接收到的（这是一个为了减少复杂性和存储的状态量的有意的设计选择）。因此，当节点B和节点C相遇时节点C之前通过节点B得到的信息将再次传递给B，反之亦然，所以即使没有额外的相遇发生它们对节点A的DP值仍然被进一步增大。
当关于节点A和B初始相遇的信息到达高相遇频率的区域，它被不适当地放大。当遇到频率更加均匀的网络时这个问题就不那么严重了，并且可以通过一个更积极的老龄化策略部分解决。
迭代次数
图2 使用PRoPHET的DP随时间的变化
2.4文献中的PRoPHET的评估
在本节中，我们会评判一些PRoPHET的性能表现不佳的论文并且尝试去理解这些结果。在赫尔辛基理工大学PRoPHET被用来与各种合成移动性方案相比较。凯德农等人发现PRoPHET对于随机路点（RWP）的情况是次优的，部分是因为
RWP不提供可预测的流动模式，这种流动模式是PRoPHET可利用的。当使用更现实的移动性时，PRoPHET的性能是优于Epidemic路由的。值得注意的是在更现实的场景中PRoPHET和Spray-and-Wait路由协议的交付率接近单跳直接交付法。这表明移动性是这样的：大多数节点最终将遇到一个特定的目的地，因此不适合展示多跳协议的优点。在本文和2008年9月的CHSNTS杂志上刊登的凯威奥和奥特的论文《时间尺度和延时容忍路由协议》中都有一个有趣的观察结果，即当beta;被设置为0时，PRoPHET有最好的性能。我们将在后面的论文中考虑这种情况。
在评估快速路由协议时，我们发现PRoPHET的性能比其他被评估路由协议的性能差一些。由于评估使用得失真实世界的痕迹，而不是随机运动，所以我们想进一步审查PRoPHET在这种情况下的表现。《延时容忍网络路由作为一个资源分配问题》一文的作者慨地分享了他们的踪迹和源代码促进了这一进程。在仿真平台实现PRoPHET是发现了几个错误（在传递更新方程中使用的是gamma;而不是beta;，路由信息交换方式的问题）。此外，所有路由信息和被聚合在一起的通信量在每个模拟日结束的时候都被从网络中清除出去了。这对于像PRoPHET这样的路由协议是不合适的，因为这些协议是根据长期的相遇历史做出判断。因此，PRoPHET的DP值不能收敛，并且整个学习阶段都保持着该协议。
2.5 传递的必要性
如上所述，若干报告声称当beta;被设定为零从而有效地禁用传递性质时PRoPHET有最好的结果。因此，有人可能会认为包含路由度量计算中的传递属性不是有益的，因此不应该被使用。那么，新版本的PRoPHET是否应该无视传递性？我们相信这一问题的答案是“否”。首先，许多表明传递性有负面影响的结果可能是由前几节所讨论的问题所导致的，这些问题将会下一节的提案中解决。此外，我们相信此传递属性在某些设置中对于协议的良好运行至关重要，在这些设置中网络可能已被分区从而使某些节点无法通信。当网络由多个几乎不相交的多个社区组成，只有少数节点在社区边缘移动时，这种情况就会发生。一个典型的例子是前面讨论过的如图1所示的网络。如果直接接触被用于在这样一个网络中建立路由度量的标准，那么节点C就不会传播关于A的任何知识，因此节点D将永远无法知道有一个经过C通往A的潜在路径。一个功能正确的传递协议将通过网络向目的地创建一个阶梯。
提出的改进
根据前一节的讨论，我们现在将描述一些对PRoPHET机制的改进措施，最后提出了一种新的协议版本，PRoPHETV2。
明白了停车场问题后，如果协议认为相遇的发生是由于间歇性的无线连接频繁断开与连接所造成的，则可以用新开发出的增加了相遇的节点的DP的演变公式来解决这一问题。该公式如下式4所示。此公式中使用的机制解决了这个问题，并且避免了每个节点在不存储大量额外信息的情况下的失真。这样做是考虑到前一次与这个节点进行信息交换的时间，并且减少了最近遇到的节点中要增加DP值得节点数。
4
在公式4由下式计算：
在上式中是一个设置应用程序中与网络部署相关的场景中的连接之间的预期典型时间间隔的参数。是与B节点上次相遇到此次相遇的时间间隔。
在最初的传递更新公式2中有一个问题，即只要beta;0，每一个已知节点k的DP值都会增大不管网络中的任何节点最近是否于节点k相遇。虽然这些传递增量通常都很小，但是它们在高相遇频率（对节点k意外的节点）的情况下会使DP值不合理地增大。当这种虚假信息的通过网络的高接触频率的一部分传播时，就会发生2009年夏季的N4C测试中出现的问题。
为了解决上述问题，我们提出了一个新的传递更新公式5，它不具有原始方程的加性属性。相反，我们比较旧的DP值与（我们建议取beta;值为0.9）的结果，然后选择二者中的较大者作为新的DP值。
5
通过使用上述最大化函数，我们使DP值的变化不用在没有新信息的情况下进行夸张的增长。
3.1PRoPHETV2
使用上面概述的改进的DP演化机制，我们定义了新版本的PRoPHET：PRoPHETV2。新版本的路
全文共7643字，剩余内容已隐藏，支付完成后下载完整资料
资料编号：[10793]，资料为PDF文档或Word文档，PDF文档可免费转换为Word
以上是毕业论文外文翻译，课题毕业论文、任务书、文献综述、开题报告、程序设计、图纸设计等资料可联系客服协助查找。
