基于相遇概率与社会分析的容忍延迟网络路由实现方法

摘要

本发明公开了一种基于相遇概率与社会分析的容忍延迟网络路由实现方法，DTN网络中当一对节点相遇时，进行所述相遇节点对于同一社区节点的相遇的衰减概率以及对于社外部区节点的相遇的衰减概率更新；接下来，利用更新后的衰减概率进行其他节点或其他社区对于所述相遇节点或者相遇社区的相遇概率更新；以及进行所述相遇节点与其它社区或者其它节点的传递概率更新；当DTN网中有消息产生时，源节点产生消息，消息在网络中扩散，实现了消息从源节点到达目的节点。本发明用给定的社区结构与分布式的概率计算，确定了出色的DTN社会网络路由，为DTN路由的发展，为建立“实用”的DTN通信网路路由做出了贡献；同时保证了消息投递成功率，传递时延，节点内存的平衡。

说明书

技术领域

本发明涉及无线自组织网络通信领域，特别是涉及一种依靠相遇机会实现通信的自 组织网络的容忍延迟网络路由实现方法。

背景技术

DTN(DelayTolerantNetworks)通信作为一类特殊的网络通信，即源节点和目的节点 之间不存在完整的、确定的、规划好的链路；而是面向消息的，利用节点移动带来相遇 机会实现通信的自组织网络；其在特殊环境(如动物迁徙，战区敌情探测等)中已经显 现巨大的实用性以及可靠性，得到了广泛关注与应用。

鉴于DTN网络中消息的投递成功率、消息的延时率和节点内存大小的问题越来越 突出；因此，DTN路由如果只单纯依靠节点随机移动带来的相遇机会实现和不同节点 之间传递消息，这种简单方式已经无法满足DTN应用的要求。特别是针对依赖于节点 社会特性的DTN路由。社会性DTN路由需要在不同的社会网络中传递消息，并且尽可 能的传递到目的节点所属的社会网络内。在DTN网络中，消息传输的高成功率、低延 时率和有限的节点内存这三者之间的关系，都对消息的路由策略提出了很高的要求。那 么如何在高成功率、低延迟率和有限的节点内存之间找到一种平衡的技术方案就显得十 分重要。

相比较于其他的社会性DTN路由策略，“基于相遇概率与社会分析的路由策略” 有着其特殊的优势，其中相遇概率是利用节点的相遇历史信息，通过比较彼此的概率进 行路由的选择；而“社区结构”是目前社会性DTN路由的主要路由策略之一，这种路 由策略的前提是对网络中节点的社区划分，以上两种策略的结合，可以实现更好性能的 DTN路由。

相比较于标签(label)等社会性路由算法，“基于相遇概率与社会分析的容忍延迟 网络路由策略”可以实现更高的消息传递成功率、更低的时延率、而且对节点内存的要 求也有较好的控制，基本上能应用在任何社会性DTN路由中；而对于Bubble路由策略， 当消息在目的社区以外传递时，由于只考虑了节点的流行度，因而不如“基于相遇概率 与社会分析的容忍延迟网络路由策略”更有针对性，实现的效果也一般不会比后者更好。

发明内容

基于上述现有技术存在的问题，本发明提出了一种基于相遇概率与社会分析的容忍 延迟网络路由实现方法，结合社区结构技术，该路由能够取得较好的消息投递成功率， 较低的传递时延，并且对节点内存的使用也有较好的控制。该路由实现了在社会性DTN 应用中，消息及时可靠的传递，具有很好的理论和实用价值。

本发明公开了一种基于相遇概率与社会分析的容忍延迟网络路由实现方法，该方 法包括以下步骤：

DTN网络包括多个社区，各个社区包括多个节点，当一对节点相遇时，进行所述 相遇节点分别对于同一社区内节点的衰减概率以及对于外部社区的衰减概率更新；接下 来，利用更新后的衰减概率进行其他节点或其他社区对于所述相遇节点或者相遇社区的 相遇概率更新；以及进行所述相遇节点与其它社区或者其它节点的传递概率更新；

当DTN网络中有消息产生时，进行网络中节点的初始化：将产生消息m的目的节 点所在社区定义为目的社区，将在目的社区外部的节点的消息的生存时间设定为T₁；将 在目的社区内部的节点的消息的生存时间设定为T₂；源节点产生消息，消息在网络中扩 散，该扩散包括消息在目的社区外部传递、消息在目的社区内传递以及消息在目的社区 外部和目的社区内部之间传递三个过程；其中：消息在目的社区外部的传递过程是：通 过计算并且比较不同节点的对于目的社区的相遇概率，由相遇概率小的节点传递到相遇 概率大的节点；而消息在目的社区内部的传递过程是：通过计算并且比较目的社区内节 点对于目的节点的相遇概率，再由相遇概率小的节点传递到概率大的节点；实现了消息 从源节点到达目的节点；消息在目的社区外部和目的社区内部之间传递过程是：携带消 息的目的社区外部节点与目的社区内部节点相遇，那么该消息会从目的社区外部传递到 目的社区内部；如果是携带消息的目的社区内部节点与目的社区外部节点相遇，那么消 息将肯定不会发生传递。

所述消息在网络中扩散的步骤，具体包括以下处理：

如果产生消息的源节点在目的社区外部，那么它最多可以向其它节点扩散n份消息 的拷贝；如果源节点扩散的消息数量达到n份，那么删除源节点的消息；如果源节点中 的消息的生存时间超过T₁，那么即使源节点扩散的消息数量没有达到n份，同样删除源 节点的消息；如果源节点在目的社区内部，那么对源节点扩散消息的份数没有要求；不 过，若是源节点中的消息生存时间超过T₂时，即删除源节点的消息。

所述衰减概率更新，具体包括以下处理：

在时间维度上，将时间划分为等间隔的时隙τ，节点将根据两次相遇之间所经历的 时隙τ的片数，更新自己的衰减概率。

当网络中有节点x,y相遇时，以节点x为例，相遇节点一方面需要更新与外部社区 的衰减概率，如公式(1)所示：

P_{相遇(x,L)old}为社区L外部节点x,y相遇之前，节点x与社区L的相遇概率；P_衰减(x,L)为节点x,y相遇之后，得到的节点x与社区L相遇的衰减概率；P_{相遇(y,L)old}为社区L外 部节点x,y相遇之前，节点y与社区L的相遇概率；P_衰减(y,L)为节点x,y相遇之后，得到 的节点y与社区L相遇的衰减概率；γ为衰减因子；k为节点x或y上一次在网络中与 其它节点相遇后到现在经历的时隙片数；

另一方面需要更新和同一社区内其它节点相遇的衰减概率，如公式(2)所示：

P_{相遇(x,i)old}为节点x,i相遇之前，节点x对同一社区内节点i的相遇概率；P_衰减(x,i)为 节点x,y相遇之后，节点x与节点相遇的衰减概率；P_{相遇(y,i)old}为节点x,i相遇之前，节 点y对同一社区内节点i的相遇概率；P_衰减(y,i)为节点x,y相遇之后，节点y与节点相遇 的衰减概率；γ为衰减因子；k为节点x或一节点y上一次在网络中与其它节点相遇后到 现在经历的时隙片数；节点i为同一社区的其他节点，包括相遇节点y,x或节点x,y。

同一社区内部的概率更新，节点x,y之间为相遇概率更新；节点x,y与社区内其它 节点z为传递概率更新；具体包括以下处理：

如果相遇的一对节点x,y属于同一个社区L，那么节点x,y将按照如下方式更新与 社区内其它节点的相遇概率：

节点x/节点y首先按照公式(2)更新与社区内其它节点的衰减概率；接下来更新 节点x/节点y和相遇节点y/节点x的相遇概率，如公式(4)所示：

其中P_{init_d}是社区内部节点的初始化相遇概率，P_衰减(x,i)为节点x,y相遇之后，节点x 与社区L中节点i，即节点y的衰减概率；P_{相遇(x,i)new}是节点相遇之后，得到的节点x对 节点y的相遇概率；P_衰减(y,i)为节点x,y相遇之后，节点y与社区L中节点i，即节点x 的衰减概率；P_{相遇(y,i)new}是节点相遇之后，得到的节点y对节点x的相遇概率；

然后，计算节点x需要更新对于社区L内其它节点的传递概率；在节点x/节点y 更新了与节点z相遇的衰减概率之后，如果P_衰减(x,z)＝P_衰减(y,z)，那么此次的节点的概率更 新完成。如果P_衰减(x,z)≠P_衰减(y,z)，假设P_衰减(x,z)>P_衰减(y,z)，这时节点x不再进行对于节点z 的传递概率更新，而节点y按照公式(5)再次进行对于节点z的传递概率更新：

P_{传递(y,z)new}＝P_衰减(y,z)+(1-P_衰减(y,z))*β(5)

其中β为传递因子；P_{传递(y,z)new}是节点y再次进行概率更新之后，与社区L中任意节点z 的传递概率；P_衰减(y,z)为节点x,y相遇之后，得到的节点y与社区L中任意节点z相遇的 衰减概率。

相遇社区的概率更新，具体包括以下处理：

如果相遇的一对节点x,y属于不同的社区，那么节点x,y将按照如下方式更新与彼 此社区的相遇概率；

节点x(节点y)按照公式(1)对节点y(节点x)所属社区进行衰减概率更新， 然后，节点x(节点y)按照公式(6)更新其与节点y(节点x)所属社区L的相遇概 率：

P_{相遇(x,L)new}＝P_衰减(x,L)+(1-P_衰减(x,L))*P_{init_L}(6)

P_{相遇(y,L)new}＝P_衰减(y,L)+(1-P_衰减(y,L))*P_{init_L}

其中：P_{相遇(x,L)new}是节点x,y相遇之后，节点x与社区L的相遇概率；P_衰减(x,L)是节 点x,y相遇之后，节点x对社区L相遇的衰减概率；：P_{相遇(y,L)new}是节点x,y相遇之后， 节点y与社区L的相遇概率；P_衰减(y,,L)是节点x,y相遇之后，节点y对社区L相遇的衰 减概率；Pinit_L是社区外部节点对于该社区的初始化相遇概率。

社区外部的传递概率更新，具体包括以下处理：

所述传递概率更新步骤具体包括以下处理：如果相遇节点x,y均在某一个社区L外 部，在节点x,y更新了各自与社区L的衰减概率之后，如果P_衰减(x,L)＝P_衰减(y,L)，那么 此次的节点的传递概率更新完成；如果P_衰减(x,L)≠P_衰减(y,L)，假设P_衰减(x,L)>P_衰减(y,L)，那 么，这时节点x不再进行传递概率更新，而节点y按照公式(3-1)、(3-2)再次进 行对社区L的传递概率更新：

P_{传递(y,L)new}＝P_衰减(y,L)+(1-P_衰减(y,L))*P_衰减(x,L)*β(3-1)

其中β是传递因子，P_{传递(y,L)new}是节点y再次进行传递概率更新之后，与社区L的 传递概率；P_{衰减(y,L)为}节点x,y相遇之后，节点y与社区L相遇的衰减概率；P_衰减(x,L)为节 点x,y相遇之后，得到的节点x与社区L相遇的衰减概率；

另外：如果P_衰减(x,L)≠P_衰减(y,L)，假设P_衰减(x,L)<P_衰减(y,L)，那么，这时节点y不再进 行传递概率更新，而节点x按照公式(3)再次进行对社区L的传递概率更新：

P_{传递(x,L)new}＝P_衰减(x,L)+(1-P_衰减(x,L))*P_衰减(y,L)*β(3-2)

其中β是传递因子，P_{传递(x,L)new}是节点x再次进行传递概率更新之后，与社区L的 传递概率；P_衰减(y,L)为节点x,y相遇之后，得到的节点y与社区L相遇的衰减概率；P_衰减(x,L)为节点x,y相遇之后，得到的节点x与社区L相遇的衰减概率；

同样的，节点x,y需要更新除了自身所属社区以外的对其它所有外部社区的传递概 率。

本发明将DTN网络的社区结构，概率传输以及消息扩散的特点相结合，确定了 一种基于相遇概率的，延迟可容忍的社会网络路由。本设计针对DTN网络节点的社 会特性以及节点相遇的历史信息，为DTN社会网络路由的发展提供了一种新的技术 上的支持，同时也较为广泛的拓展了DTN社会网络的使用范围。同时该设计方案的 思路也可以应用于其他的DTN网络路由。本设计用给定的社区结构与分布式的概率 计算，确定了出色的DTN社会网络路由，为DTN路由的发展，从消息的洪泛传输 到社会性传输提供了有力的支撑，同时保证了消息投递成功率，传递时延，节点内 存的平衡，为建立“实用”的DTN通信网路路由做出了贡献。

附图说明

图1为基于相遇信息的延迟可容忍社会网络路由模型；

图2为初始化并更新相遇节点的概率的流程图；

图3为判断节点是否可以进行消息的传递的流程图；

图4为源节点的消息扩散方式的流程图；

图5为判断节点中存在的消息是否超过生存时间的流程图；

图6为消息的路由传递方式的流程图；

图7为基于相遇概率与社会分析的容忍延迟网络路由的最佳实施方式示意图。

具体实施方式

下面将结合附图对本发明的具体实施方式进行详细描述，这些实施方式若存在 示例性的内容，不应解释成对本发明的限制。

同时，“基于相遇概率与社会分析的容忍延迟网络路由策略”为了进一步提高消息 传递成功率、降低时延，在消息扩散阶段采用了限制副本数量的多副本路由策略；虽然 对节点内存的大小也提出了较高的要求，不过能够实现基于相遇概率与社会分析的容忍 延迟网络路由的更加可靠传输。

为了能够对使用社区结构的路由策略进行评估，采用消息投递成功率、消息传递时 延，节点内存使用百分比以及消息总跳数四种评价标准，来比较它们的优劣性。

如图1所示的基于相遇概率与社会分析的容忍延迟网络路由模型，可以分成两个方 面：

当一对节点相遇(这里的一对节点包括三种情况，即同属于某一社区外部的一对节 点、属于不同社区的一对节点和属于同一社区的一对节点)时，相遇的节点需要更新对 于其它社区以及其它节点的相遇的概率，包括：更新对于同一社区节点的相遇的衰减概 率以及对于外部社区节点的相遇的衰减概率；更新与相遇节点或者相遇社区的相遇概 率；更新与其它社区或者其它节点的传递概率；

当网络中有消息产生时，源节点产生消息，消息在网络中扩散，该扩散包括消息在 目的社区外传递、消息在目的社区内传递以及消息在目的社区外部和目的社区内部之间 的传递三个主要过程。其中：消息在目的社区外部的传递过程是：通过计算并且比较不 同节点的对于目的社区的相遇概率，由概率小的节点传递到概率大的节点；而消息在目 的社区内部的传递过程是：通过计算并且比较目的社区内节点对于目的节点的相遇概 率，再由概率小的节点传递到概率大的节点；实现了消息从源节点到达目的节点。此部 分具体处理流程包括以下步骤：

步骤1、网络中节点的初始化：当网络中产生消息m时，将产生消息m的目的节 点所在社区定义为目的社区；将在目的社区外部的节点产生的消息m的生存时间设定 为；将在目的社区内部的节点产生的消息m的生存时间设定为；

步骤2、源节点s的消息扩散方式：如果产生消息m的源节点s在目的社区L外部， 那么它最多可以向其它节点扩散n份消息的拷贝；如果源节点s扩散的消息数量达到n 份，那么删除源节点的消息m；如果源节点中的消息m的生存时间超过，那么即使 源节点扩散的消息数量没有达到n份，同样删除源节点的消息m；

如果源节点s在目的社区L内部，那么对源节点扩散消息m的份数没有要求；不 过，若是源节点s中的消息m生存时间超过时，即删除源节点的消息m；

步骤3、目的社区外部节点携带消息m，与另一外部节点y相遇：

相遇的节点先进行相遇概率更新，随后再判断是否进行消息的传递；当产生消息m 的相遇节点更新概率之后，首先节点x会判断其中的消息m是否超过生存时间，如 果超过，则节点之间不会进行任何消息的交换，并且节点x删除消息m；

如果节点x中的消息m没有超过生存时间，则需要判断节点y是否标记接收过 消息m。如果节点y标记接收过消息m，那么这次相遇的节点之间不会进行任何信息的 交换；并且，需要判断消息m是否还存储在节点y中，如果消息m仍然存储在节点y 中，那么判断消息m是否超过了生存时间，超过则删除y中的消息m；

如果节点y没有标记过消息m，那么节点x,y比较与目的社区L的相遇概率，如果 P_相遇(x,L)<P_相遇(y,L)，则节点x将消息m发送到节点y，并且节点x删除消息m。

步骤4、目的社区外部节点x携带消息m，与目的社区内部节点y相遇：

首先节点x会判断其中的消息m是否超过生存时间，如果超过，则节点x删 除消息m；并且不会进行消息的传递；

如果节点x中的消息m没有超过生存时间，则需要判断节点y是否标记接收过 消息m。如果节点y标记接收过消息m，那么首先这次相遇的节点之间不会进行任何信 息的传递；其次，判断消息m是否还存储在节点y中。如果消息m仍然存储在节点y 中，那么判断消息m是否超过了生存时间，超过了则删除节点y中的消息m；反 之，节点y中继续保留消息m；

如果节点y没有标记过消息m，则节点x将消息m发送到节点y；然后，节点x删 除消息m。

步骤5、携带消息m的目的社区内部节点x，与目的社区内部的任一节点y相遇：

首先节点x会判断存储的消息m是否超过生存时间，如果超过，则节点x删 除消息m；并且不会进行消息的传递。

如果节点x中的消息m没有超过生存时间，则需要判断节点y是否标记接收过 消息m。如果节点y标记接收过消息m，那么这次相遇不会进行任何信息的传递；其次， 判断消息m是否还存储在节点y中。如果消息m仍然存储在节点y中，那么判断消息 m是否超过了生存时间，超过则删除y中的消息m。

如果节点y没有标记过消息m，那么节点x,y比较与目的节点d的相遇概率，如果 P_相遇(x,d)<P_相遇(y,d)，则节点x将消息m发送到节点y。

所述衰减概率更新步骤具体包括以下处理：在时间维度上，将时间划分为等间隔的 时隙，节点将根据两次相遇之间所经历的时隙的片数，更新自己的衰减概率。例如： 当网络中有节点x,y相遇时，以节点x为例，相遇节点一方面需要更新与外部社区的衰 减概率，如公式(1)所示：

P_衰减(x,L)＝P_{相遇(x,L)old}*γ^k(1)

P_{相遇(x,L)old}为社区L外部节点x,y相遇之前，节点x与社区L的相遇概率；P_{衰减(x,L)为}节点x,y相遇之后，得到的节点x与社区L相遇的衰减概率；γ为衰减因子；k为节点 x上一次在网络中与其它节点相遇后到现在经历的时隙片数；

另一方面需要更新和同一社区内其它节点相遇的衰减概率，如公式(2)所示：

P_衰减(x,i)＝P_{相遇(x,i)old}*γ^k(2)

P_{相遇(x,i)old}为节点x,i相遇之前，节点x对同一社区内节点i的相遇概率；P_衰减(x,i)为 节点x,y相遇之后，节点x与节点相遇的衰减概率；γ为衰减因子；k为节点x上一次在 网络中与其它节点相遇后到现在经历的时隙片数；节点i为同一社区的其他节点，包 括相遇节点y。

所述传递概率更新步骤具体包括以下处理：如果相遇节点x,y均在某一个社区L 外部，在节点x,y更新了各自与社区L的衰减概率之后，如果P_衰减(x,L)＝P_衰减(y,L)，那 么此次的节点的传递概率更新完成；如果P_衰减(x,L)≠P_衰减(y,L)，假设P_衰减(x,L)>P_衰减(y,L)， 那么，这时节点x不再进行传递概率更新，而节点y按照公式(3)再次进行对社区 L的传递概率更新：

P_{传递(y,L)new}＝P_衰减(y,L)+(1-P_衰减(y,L))*P_衰减(x,L)*β(3-1)

其中β是传递因子，P_{传递(y,L)new}是节点y再次进行传递概率更新之后，与社区L的 传递概率；P_{衰减(y,L)为}节点x,y相遇之后，节点y与社区L相遇的衰减概率；P_{衰减(x,L)为}节 点x,y相遇之后，得到的节点x与社区L相遇的衰减概率；

另外：如果P_衰减(x,L)≠P_衰减(y,L)，假设P_衰减(x,L)<P_衰减(y,L)，那么，这时节点y不再进 行传递概率更新，而节点x按照公式(3)再次进行对社区L的传递概率更新：

P_{传递(x,L)new}＝P_衰减(x,L)+(1-P_衰减(x,L))*P_衰减(y,L)*β(3-2)

其中β是传递因子，P_{传递(x,L)new}是节点x再次进行传递概率更新之后，与社区L的 传递概率；P_{衰减(y,L)为}节点x,y相遇之后，得到的节点y与社区L相遇的衰减概率；P_{衰减(x,L)为}节点x,y相遇之后，得到的节点x与社区L相遇的衰减概率；

同样的，节点x,y需要更新除了自身所属社区以外的对其它所有外部社区的传递概 率，即针对所有的外部社区，考虑是否进行传递概率的更新。

所述相遇概率更新步骤具体包括以下处理：

(1)如果相遇的一对节点x,y属于同一个社区L，那么节点x,y将按照如下方式更 新与社区内其它节点的相遇概率：

节点x首先按照公式(2)更新与社区内其它节点的衰减概率；接下来更新节点x 和相遇节点y的相遇概率，如公式(4)所示：

P_{相遇(x,i)new}＝P_衰减(x,i)+(1-P_衰减(x,i))*P_{init_d}(4)

其中是社区内部节点的初始化相遇概率，P_衰减(x,i)为节点x,y相遇之后，节点y 与社区L中节点i相遇的衰减概率；P_衰减(x,i)为节点x,y相遇之后，节点x与社区L中节 点i相遇的衰减概率。

然后，计算节点x需要更新对于社区L内其它节点的传递概率。这里以同一社区L 内的任意节点z为例说明。

在节点x,y更新了与节点z相遇的衰减概率之后，如果P_衰减(x,z)＝P_衰减(y,z)，那么此次 的节点的概率更新完成。如果P_衰减(x,z)≠P_衰减(y,z)，假设P_衰减(x,z)>P_衰减(y,z)，这时 节点x不再进行对于节点z的传递概率更新，而节点y按照公式(5)再次进行对于节 点z的传递概率更新：

P_{传递(y,z)new}＝P_衰减(y,z)+(1-P_衰减(y,z))*β(5)

其中β为传递因子，为传递因子(0,1)之间。根据仿真实验最佳取值为0.5；P_{传递(y,z)new}是节点y再次进行传递概率更新之后，与社区L中任意节点z的传递概率；P_衰减(y,z)为 节点x,y相遇之后，得到的节点y与社区L中任意节点z相遇的衰减概率；

(2)如果相遇的一对节点x,y属于不同的社区，那么节点x,y将按照如下方式更新 与彼此社区的相遇概率。

这里仍只是以节点x为例。节点x首先按照公式(1)对节点y所属社区进行衰减 概率更新。然后，节点x按照公式(6)更新其与节点y所属社区L的相遇概率：

P_{相遇(x,L)new}＝P_衰减(x,L)+(1-P_衰减(x,L))*P_{init_L}(6)

其中：P_{相遇(x,L)new}是节点x,y相遇之后，节点x与社区L的相遇概率；P_衰减(x,L)是节 点x,y相遇之前，节点x对社区L相遇的衰减概率；P_{init_L}是社区外部节点对于该社区 的初始化相遇概率。

如图7所示，本发明的基于相遇概率与社会分析的容忍延迟网络路由的最佳实施 例：

(1)首先网络中相遇的节点之间彼此更新自己的相遇概率；

(2)源节点产生消息m，在网络中进行消息的扩散；

(3)消息m在网络中进行传递，消息在目的社区外部节点x，x遇到没有标记过 消息m，同时与目的社区相遇概更大的节点y，则将消息传递给节点y；删除节点x中 的消息m；

(4)节点y遇到没有标记过消息m的社区内部节点z，则节点y将消息传递给节 点z；同时删除节点y中的消息m；

(5)节点z遇到没有标记过消息m的目的社区节点p，而且节点p与目的节点有 更大的相遇概率，则节点z将消息传递给节点p；

(6)节点p遇到目的节点d，则将消息m传递给目的节点；同时删除网络中，除 目的节点以外，所有的消息m。