一种容迟网中基于经验拟合的路由协议消息转发方法

摘要

本发明涉及一种容迟网中基于经验拟合的路由协议消息转发方法，克服了现有技术的不足，依据经验拟合方法，能够解决二阶段容迟网喷射等待路由协议里副本分配算法复杂度较高的问题，并且可以大幅度减少计算步骤，从而降低算法的复杂度，提高实验的效率，并且基于该经验公式的两阶段喷射等待路由协议接近理论最优，能使消息的传递开销显著减少，同时能保持较高的投递率。

说明书

技术领域

本发明涉及一种容迟网中基于经验拟合的路由协议消息转发方法，属于移动对等网中路由技术领域。

背景技术

移动延迟容忍网络(MDTN)由一组移动设备组成，例如手机或传感器单元，它们可以可以通过无线协议在小范围内进行通信(例如蓝牙)。随着各种便携式设备的迅速普及，市场上的平板电脑、智能手机、车载感知设备等终端集成了多种类型的传感器，感知、计算和通信的能力越来越强。利用这些便携式设备组成的移动感知网络，可以随时随地对人类经常活动的热点区域进行机会感知。这种以人为中心的感知方式，对有意识主动部署传感网进行数据收集方式构成了重要的互补。与此同时,网络拓扑时变性节点资源受限性等特点,也使得传统的无线传感网络或移动自组织网络通信模式难以有效运行。在移动机会网络中，网络拓扑有可能被分割成几个不连通的子区域，发送端和接收端有可能位于不同的子区域而导致常规的CTP等路由算法无法正常工作。实际上，节点对之间不存在端到端连通的路径并不意味着不能实现通信，由于节点的移动，两个节点可以在进入相互的通信范围后完成数据交换。因此机会路由的模式由传统路由的存储-转发(store and forward)模式扩展为存储-携带-转发(store-carry-forward)。

喷射等待协议(Spray and Wait,S&W)，是由T.Spyropoulos,K.Psounis和C.S.Raghavendra等人在2005年提出，是一种基于泛洪路由(Epidemic)的改进路由。其内容为：源节点预先拷贝成M份数据，当与其他未携带消息副本的节点相遇时按一定消息副本分配比例来分配这M份数据。直到节点只有1份消息时执行直接交付(即携带报文的节点只有遇到目的节点时才进行转发)。例如，二分喷射等待协议(Binary S&W)是一个节点将自己所携带副本数的一半分配给相遇到的节点。但是其实这样的协议协议从消息复制的角度来看是不灵活的。研究者Thompson等人提出针对DTN网络中拥塞控制的一种机制，该机制可以通过网络中消息副本的数量和每个节点的缓存能力来调整每个节点的消息拷贝速率。

多阶段喷射等待协议(Multiperiod spraying)是研究者Zijian Wang和BoleslawKarol Szymanski在2010年提出的，这是一种在Spray and Wait协议基础上基于消息剩余生命周期大小做出副本拷贝决策的的路由算法。该算法的思想是：整体还是使用Spray AndWait算法，但是一开始投放比达到额定投递率所需的副本数少的副本数，经过一段时间观察后，给仍未进行投递的消息增加副本数以此来增加投递率。所以这个算法会将消息的整个生命周期分割成几段可变的时间段。经过实验仿真表明整个算法在能够和Spray AndWait算法达到相同的投递率情况下，整体开销能够减少。所以多阶段喷射等待协议不仅能够达到较高的投递率，还能减少消息在网络内的传递开销。但是该协议里消息副本数的确定方法的算法复杂度较高，影响实验的运行效率。

发明内容

本发明所要解决的技术问题是提供一种容迟网中基于经验拟合的路由协议消息转发方法，能够解决二阶段容迟网喷射等待路由协议里副本分配算法复杂度较高的问题，并且可以大幅度减少计算步骤，从而降低算法的复杂度，提高实验的效率，同时能够减少消息副本的传递开销。

本发明为了解决上述技术问题采用以下技术方案：本发明设计了一种容迟网中基于经验拟合的路由协议消息转发方法，用于实现容迟网中路由协议消息的转发，包括如下步骤：

步骤001.源节点根据目标消息的生存周期T，获得目标消息对应第一发送阶段的最大副本数L₁，并进一步获得目标消息对应的第一发送阶段时长T_d，然后开始计时，并进入步骤002；

步骤002.源节点生成并转发目标消息副本，同时，判断源节点是否接收到来自目的节点所转发确认接收到目标消息副本的反馈消息，是则目标消息转发成功结束；否则进入步骤003；

步骤003.判断计时是否达到第一发送阶段时长T_d，是则进入步骤005；否则进入步骤004；

步骤004.判断源节点已经生成并转发的目标消息副本数是否等于L₁，是则待计时达到第一发送阶段时长T_d时，进入步骤005；否则返回步骤002；

步骤005.源节点根据目标消息对应第一发送阶段的最大副本数L₁，获得目标消息对应其剩余时长(T-T_d)的增量副本数ΔL，并进入步骤006；

步骤006.源节点生成并转发目标消息副本，同时，判断源节点是否接收到来自目的节点所转发确认接收到目标消息副本的反馈消息，是则目标消息转发成功结束；否则进入步骤007；

步骤007.判断计时是否达到目标消息的生存周期T，是则目标消息转发失败结束；否则进入步骤008；

步骤008.判断源节点已经生成并转发的目标消息副本数是否等于(L₁+ΔL)，是则返回步骤007；否则返回步骤006。

作为本发明的一种优选技术方案，所述步骤001中，源节点根据目标消息的生存周期T，按如下公式：

获得目标消息对应第一发送阶段的最大副本数L₁，其中，P表示用户期望的目标消息转发投递率，λ表示容迟网中节点与节点之间的平均接触率。

作为本发明的一种优选技术方案，所述步骤001中，源节点根据目标消息的生存周期T和目标消息对应第一发送阶段的最大副本数L₁，按如下公式：

获得目标消息对应的第一发送阶段时长T_d，其中，P表示用户期望的目标消息转发投递率，λ表示容迟网中节点与节点之间的平均接触率。

作为本发明的一种优选技术方案，所述步骤005中，源节点根据目标消息对应第一发送阶段的最大副本数L₁，按如下公式：

ΔL＝L₂-L₁

获得目标消息对应其剩余时长(T-T_d)的增量副本数ΔL。

作为本发明的一种优选技术方案，所述用户期望的目标消息转发投递率P大于90％。

作为本发明的一种优选技术方案，所述步骤002中和所述步骤006中，源节点分别按照按喷射等待协议，生成并转发目标消息副本，以及完成后续操作。

作为本发明的一种优选技术方案，所述步骤002中和所述步骤006中，源节点分别按二分喷射等待协议，生成并转发目标消息副本，以及完成后续操作。

作为本发明的一种优选技术方案，所述步骤002和所述步骤006中，所述目的节点采用泛洪路由协议转发确认接收到目标消息副本的反馈消息。

本发明所述一种容迟网中基于经验拟合的路由协议消息转发方法采用以上技术方案与现有技术相比，具有以下技术效果：本发明设计的容迟网中基于经验拟合的路由协议消息转发方法，克服了现有技术的不足，依据经验拟合方法，能够解决二阶段容迟网喷射等待路由协议里副本分配算法复杂度较高的问题，并且可以大幅度减少计算步骤，从而降低算法的复杂度，提高实验的效率，并且基于该经验公式的两阶段喷射等待路由协议接近理论最优，能使消息的传递开销显著减少，同时能保持较高的投递率。

附图说明

图1是本发明所设计容迟网中基于经验拟合的路由协议消息转发方法的流程示意图。

具体实施方式

下面结合说明书附图对本发明的具体实施方式作进一步详细的说明。

如图1所示，本发明设计了一种容迟网中基于经验拟合的路由协议消息转发方法，用于实现容迟网中路由协议消息的转发，在实际应用过程当中，具体包括如下步骤：

步骤001.源节点根据目标消息的生存周期T，按如下公式：

获得目标消息对应第一发送阶段的最大副本数L₁，其中，P表示用户期望的目标消息转发投递率，实际应用中，用户期望的目标消息转发投递率P大于90％，λ表示容迟网中节点与节点之间的平均接触率，并且源节点根据目标消息的生存周期T和目标消息对应第一发送阶段的最大副本数L₁，按如下公式：

获得目标消息对应的第一发送阶段时长T_d，其中，然后开始计时，并进入步骤002。

步骤002.源节点生成并转发目标消息副本，同时，判断源节点是否接收到来自目的节点所转发确认接收到目标消息副本的反馈消息，是则目标消息转发成功结束；否则进入步骤003。

步骤003.判断计时是否达到第一发送阶段时长T_d，是则进入步骤005；否则进入步骤004。

步骤004.判断源节点已经生成并转发的目标消息副本数是否等于L₁，是则待计时达到第一发送阶段时长T_d时，进入步骤005；否则返回步骤002。

步骤005.源节点根据目标消息对应第一发送阶段的最大副本数L₁，按如下公式：

ΔL＝L₂-L₁

获得目标消息对应其剩余时长(T-T_d)的增量副本数ΔL，并进入步骤006。

步骤006.源节点生成并转发目标消息副本，同时，判断源节点是否接收到来自目的节点所转发确认接收到目标消息副本的反馈消息，是则目标消息转发成功结束；否则进入步骤007。

步骤007.判断计时是否达到目标消息的生存周期T，是则目标消息转发失败结束；否则进入步骤008。

步骤008.判断源节点已经生成并转发的目标消息副本数是否等于(L₁+ΔL)，是则返回步骤007；否则返回步骤006。

对于上述所设计容迟网中基于经验拟合的路由协议消息转发方法技术方案中，我们进一步设计步骤002中和步骤006中，源节点分别按照按喷射等待协议或二分喷射等待协议，生成并转发目标消息副本，以及完成后续操作；并且所述目的节点采用泛洪路由协议转发确认接收到目标消息副本的反馈消息。

如此，本发明所设计容迟网中基于经验拟合的路由协议消息转发方法，在实际应用过程当中，当携带消息副本节点会按照二分喷射等待协议进行消息转发，当任何携带该消息的节点达到目的节点，目的节点都会产生一个该消息的反馈消息，并且这个反馈消息会按照泛洪路由协议进行消息转发。只有当源节点收到该消息的反馈消息，消息转发才结束。源节点如果在T_d时间没有收到这个反馈确认消息，则会在现有副本数的基础上增加ΔL个，然后继续进行消息转发，直到源节点收到该消息的反馈确认消息才结束消息的转发。这种根据经验公式快速计算关键变量值L₁、ΔL的方法，不仅能够减少副本的传递开销，而且算法的复杂度也降低，效率提高。

进一步地，在被分配了消息副本的节点按已有的喷射等待协议进行消息转发时，优选按照二分喷射等待协议进行消息转发，即被分配了消息副本的节点与其他未携带消息副本的节点相遇时，将其所携带消息副本数的一半分配给未携带消息副本的节点，也可以按照源节点喷射等待协议进行消息转发，除此之外，本发明设计方案中对于消息的转发，不限于该两种转发方式。

为了验证本发明所设计容迟网中基于经验拟合的路由协议消息转发方法能够有效实现减少副本开销，特列举一实施例进行说明。

本实施例中，假设网络中有10个节点，节点编号为n₁到n₁₀。容迟网中节点与节点之间的平均接触率λ＝1×10^-4，设节点n₁为源节点、节点n₁₀为目的节点，用户期望的目标消息转发投递率P＝95％，目标消息的生存周期T＝6000s。则投递率达到95％时，第一阶段分配给该消息的副本数L₁：

第一阶段的时长T_d：

其中，

然后，节点n₁按已有的二分喷射等待协议将所携带消息4个副本进行消息转发，当时间为1000s时，节点n₁与任意未携带消息副本的节点n₂相遇时，由于n₂节点不是目的节点，则节点n₁可以按照所携带消息副本数的一半分配给未n₂，此时n₁节点剩余消息副本数为2，节点n₂将携带2个消息副本。节点n₁和n₂都按已有的二分喷射等待协议继续消息转发。

当时间为2000s时，节点n₂与节点n₁₀相遇，由于n₁₀是目的节点，则节点直接将消息副本传递到n₁₀。n₁₀接收该消息同时产生一个该消息的反馈确认消息，并且该反馈确认消息按照泛洪路由协议进行消息转发。

当时间为3000s时，由于反馈确认消息还未投递到源节点n₁，节点n₁计算第二阶段增加的副本数ΔL：

ΔL＝L₂-L₁＝6-4＝2

同时源节点n₁消息副本数增加2个，此时节点n₁含有的副本数为3。节点n₁会继续按已有的二分喷射等待协议将所携带消息3个副本进行消息转发。

当时间为4000s时，，携带反馈确认消息的节点与节点n₁相遇，消息转发结束。

如上述，可以证明本发明所设计容迟网中基于经验拟合的路由协议消息转发方法，基于经验拟合的两阶段喷射等待路由协议消息转发的改进方法，通过加入经验公式快速的计算出算法里每个阶段所要分配的副本数，使得算法的复杂度降低一个数量级，提高了实验的运行效率。该方法算出的副本数值运用在两阶段喷射等待路由协议里，与理论最优非常接近，不仅减少了副本的传递开销，还可以获得较高的投递率。

综上所述，本发明所设计容迟网中基于经验拟合的路由协议消息转发方法，克服了现有技术的不足，依据经验拟合方法，能够解决二阶段容迟网喷射等待路由协议里副本分配算法复杂度较高的问题，并且可以大幅度减少计算步骤，从而降低算法的复杂度，提高实验的效率，并且基于该经验公式的两阶段喷射等待路由协议接近理论最优，能使消息的传递开销显著减少，同时能保持较高的投递率。

上面结合附图对本发明的实施方式作了详细说明，但是本发明并不限于上述实施方式，在本领域普通技术人员所具备的知识范围内，还可以在不脱离本发明宗旨的前提下做出各种变化。