社会属性驱动的容迟网络路由改良算法

摘要

本发明提供的社会属性驱动的容迟网络路由改良算法，针对Bubble Rap将数据快速传递到结点整体中介中心性较高的结点，会导致结点整体中介中心性较低的结点可能不能获得消息，提出了均衡整体中心中介度和局部中心中介的评估中介中心性的方案，并且提出了结点有一定的概率向评估中介中心性低的结点传递数据，Bubble Rap在数据传输过程中采用基于洪泛的机制，为降低网络中副本数量，采用基于改良的二分转发方法进行数据传输和TTW时间，在对传输速度较小的影响下，使结点中数据副本的过期时间变短，大幅降低了网络中的副本数据，降低了网络负载和结点资源，较大程度避免了洪泛机制导致的网络拥塞，提高了网络性能。

说明书

技术领域

本发明涉及一种容迟网络路由改良算法，特别涉及社会属性驱动的容迟网络路由改良算法，属于容迟网络路由算法技术领域。

背景技术

随着互联网技术快速发展，TCP/IP协议簇得到广泛应用，已成为互连网的通信标准，TCP/IP协议实现端到端的通信需具备以下条件：一是存在源结点到目的结点的通信链路，二是端到端的最大通信往返时间不能太长，三是较小的端到端的分组丢失率；但现实中存在一些受限网络,如快速移动网络，稀疏移动无线自组网络等，其网络特点是：源结点到目的结点不存在完整的通信链路，端到端时延和分组丢失率很高，因此传统的TCP/IP通信协议无法适应此类网络。为解决此类网络的通信互联问题，出现了容迟网络，容迟网络具有高时延，高分组丢失率、传输速率低、链路中断频繁、结点移动频繁、通信链路长时间中断、结点能量受限等特点，是一种无线通信自组网络，采用存储-捎带-转发机制实现数据传输，主要用于解决通信链路非常不稳定的通信网络，近年来随着智能终端和移动通信技术的发展，智能手机、PDA和其他便携式通信终端已成为人们生活中的一部分，通过蓝牙、Ad-hoc等无线通信技术实现终端之间的通信互联，而不依赖移动通信商的基站，这种网络中结点是通过结点间相遇实现信息转发，结点随人的移动而移动，人与人之间交往的同时结点也就相遇，因而结点具有了人类社会属性，这种网络中结点具有社会属性的容迟网络为社交时延容忍网络。

社交时延容忍网络作为时延容忍网络中的一种，与时延容忍网络最大的不同是结点具有社会属性，随着智能终端的普及，移动网络迅猛发展，现实中移动网络主要以人为中心，社交时延容忍网络得到了广泛关注，其中路由算法作为延时容忍网络的重中之重，成为首要研究对象，在社交时延容忍网络中，结点间的通信依靠结点相遇来实现，而结点具有社会属性，因此在社交时延容忍网络中利用结点的社会属性设计高效的路由算法具有重要的研究意义和广泛的应用价值。本发明分析Bubble Rap路由算法，针对其存在的不足提出修改方案，提高分组成功投递率，降低网络时延，节约系统资源。

时延容忍网络体系结构主要应用在源结点到目的结点链路频繁中断、结点资源有限和高时延的网络环境中，是实现结点之间信息的异步可靠传输的通信体系结构。容迟网络特性决定了传统的网络路由协议无法应用于容迟网络中，传统网络最重要的特点是端到端存在一条完整通信链路，而容迟网络不具备此特点，容迟网络的网络环境是高延时、没有完整通信链路、结点资源有限等，因此容迟网络需要特定的路由算法，根据是否对消息进行复制，将容迟网络路由分成单副本路由和多副本路由。最简单的单副本路由算法就是直接传输，只有当源结点遇到目的结点才会将数据转发，即源结点和目的间的数据传递只需要一跳即可完成。该种路由机制算法简单，节省网络资源，但是只有当源结点和目的结点相遇时，才能成功，如果源结点与目的结点始终不能相遇，则数据投递失败，直接传输、首次联系和随机路由由于缺乏结点的了解，转发数据具有一定的盲目性；多副本路由通过洪泛的方式进行数据传递，以达到最大化的覆盖网络中的结点，从而实现数据快速有效的到达目的结点的路由算法。该路由算法利用更多的转发次数来换取更高的数据投递的成功率和降低时延，但是此算法使网络中充满大量数据副本，导致网络开销极大，当网络负载极高时，结点缓存空间和通信宽带迅速消耗殆尽，导致数据投递率成功率明显下降。

Bubble Rap路由算法利用社交网络中社区与中介中心性概念，采用K-CLIQUE社区侦测和Newman的加权网络分析算法划分结点移动的社区，通过中介中心性衡量结点的在社区中的重要程度，中介中心性越大表明结点将信息转发到目的结点的概率越大，反之越小；Bubble Rap路由算法策略为：假设每个结点在整个网络中存在社区内部中介中心性和一个整体的中介中心性，传递数据分二个阶段：第一阶段，当源结点需要发送消息到目的结点时，源结点开始移动，当遇到其他结点时，先比较结点的整体中介中心性，若比源结点大，这转发信息给此结点，反之不转发，直到信息传递到目的结点或目的结点所在社区；第二阶段，信息到达目的结点所在社区，查询结点的局部中介中心性，若比结点大，则转发信息给此结点，反之不转发，直到信息投递到目的结点或TTW值变为0；为降低网络负载和缓存，信息转发后可删除结点中该信息的缓存。

Bubble Rap算法基于以下二个假设：假设一，每个结点属于一个或多个社区，单个结点也能成为一个社区，社区内部结点之间相遇的概率大于与其他社区结点相遇的概率；假设二，每个结点拥有一个整体中介中心性和它所在社区的局部中介中心性，中介中心是中心性中的一种度量方法，结点中介中心性越高的结点，则在网络中的重要性越高，即结点在网络中的活跃度越高。

路由工作过程为:首先利用K-CLIQUE和Newman的加权网络分析方法侦测划分社区，然后转发数据，转发数据分为二个阶段，第一个阶段数据传递给整体中介中心性较高的结点，当结点相遇时，结点比较其整体中介中心性，如果大于此结点的整体中介中心性，则转发数据给相遇结点，否则不转发，直到数据传递到目的结点所在社区的结点或目的结点，然后在信息传递到目的社区后进入第二个阶段，用局部中介中心性替代整体中介中心性，直到数据转发到目的结点或信息超时过期被删除。

该路由策略存在以下不足：

一是根据该路由策略，整体中介中心较高的结点，则在网络中活跃度较高，为了将信息快速传递出去，选择整体中介中心较高的结点作为转发结点，若在转发过程中遇到目的结点或目的结点所在的社区，则将信息传递给目的结点所在的社区的结点；如果传递过程中所有的转发结点都不与目的结点所在社区的结点相遇，则信息投递失败；失败原因是信息一直向活跃度较高的结点传递，认为活跃度较高的结点一定可以将信息传递到目的结点，但现实情况是活跃度较高的结点表明其可将信息快速传递出去，但不能保证它与网络中所有结点都有相遇的机会，即整体中介中心最高的结点并不能表明其在所有社区都较活跃，导致信息投递失败；

二是根据中介中心性定义和社区划分方法，处在社区之间上的结点，通常结点的整体中介中心性较高，整体中介中心性高的结点在整体的活跃度很高，路由数据转发策略会导致信息停留在高活跃度的结点上，而无法传递到活跃度稍低的结点；

三是路由在数据转发过程中利用社会的社区与中介中心性属性选择整体活跃度较高和社区内部活跃较高的结点作为转发结点，提高数据转发效率和投递成功率，如果结点在数据传递后删除原数据副本，数据传递就是基于单副本路由，而单副本路由的缺点是副本扩散速度慢且数据向活跃度较高的结点传递过程中可能会错过与目的结点相遇的机会，降低数据投递的成功率和增加数据传输时延；在数据传输后不删除原数据，则数据以洪泛机制传输给比结点整体中介中心性大或局部中介中心性大的结点，洪泛机制加快信息传递的速率，提高信息投递的成功率和降低网络时延，但增加了网络负载，随着网络规模增加，网络性能会下降，即结点在传递信息时采用了洪泛机制的策略，但没有考虑洪泛机制导致的网络负载的增加和网络拥塞。

Bubble Rap容迟网络路由策略根据社会属性中的中介中心作为转发数据的依据，但中介中心性越高，并不能代表结点在所有社区都高，而且信息向整体中介中心较高的结点汇聚，导致信息不能传递到中介中心性较低的目的结点，在转发数据后是否删除原数据，若删除则是单副本，不删除则变成洪泛机制，前者导致信息扩散速度慢，而后者随着网络规模增大，网络会出现拥塞。针对Bubble Rap算法存在的这些不足，本发明在Bubble Rap的基础上，进行修改优化，提出社会属性驱动的容迟网络路由改良算法，较好的解决上述存在的问题，从而进一步提高容迟网络Bubble Rap路由性能。

发明内容

本发明提供的社会属性驱动的容迟网络路由改良算法，分析Bubble Rap算法存在的不足，提出了具体的修改方案，进一步提高数据的投递率、降低网络时延和网络负载；根据Bubble Rap路由算法数据转发依赖于整体中介中心性，而中介中心性高的结点不代表结点在所有社区的活跃度都较高等不足，本发明提出改良方案，在数据传输的过程中，为克服洪泛机制和单副本路由的不足，利用二分法转发方法转发数据，并修改二分法数据转发数据副本数量的计算方式，使得信息有概率的传递到网络中各个层次的社区中，避免因目的结点所在社区活跃度较低而无法获取其他结点发送的信息；为进一步的控制网络中数据副本数量，在数据转发的同时，修改原结点中转发数据副本的TTW值，使结点中数据副本的过期时间变短，减少网络副本的数量，较大程度避免了洪泛机制导致的网络拥塞，提高了网络性能。

为达到以上技术效果，本发明所采用的技术方案如下：

社会属性驱动的容迟网络路由改良算法，基于Bubble Rap算法提出具体的的容迟网络路由改良方法，进一步提高数据的投递率、降低网络时延和网络负载；利用加权和局部中介中心性方差来均衡整体中介中心性和局部中介中心性，提出评估中介中心性，已选择更优的结点作为转发结点，在数据传输的过程中利用二分法转发方法转发数据，并修改二分法数据转发数据副本数量的计算方式，让活跃度较高的结点获得更多的副本，以便数据快速传递出去，以一定的概率向评估中介中心性较小的结点转发数据，倾向于将数据转发给活跃度较高，所属社区较多且局部中介中心性活跃度均衡的结点，使得信息有概率的传递到网络中各个层次的社区中；进一步的控制网络中数据副本数量，在数据转发的同时，修改原结点中转发数据副本的TTW值，使结点中数据副本的过期时间变短，减少网络副本的数量，避免洪泛机制导致的网络拥塞；

算法改良中使用的核心概念为：

概念一，时间TTW，一个信息在创建后，在系统存在的最大时间，即信息过期时间，避免信息长期停留在系统中，占用有限的系统资源；

概念二，副本数量W，信息在创建时，结点可创建的最大的信息备份数量；

概念三，F-Bubble Rap算法是指在Bubble Rap路由算法中转发数据后，不删除原结点中的数据副本；

概念四，G-Bubble Rap算法是指在Bubble Rap路由算法中转发数据后，删除原结点中的数据副本；

本发明提出评估中介中心性来进一步提高选择转发结点的准确性，同时利用改良的二分转发方法对F-Bubble Rap算法和G-Bubble Rap算法中是否删除原副本数据进行折中，在数据转发后减小结点中原副本的TTW值，减小副本在系统中的生存时间，减小网络中副本数量的目的，本发明提出以一定的概率向较低中介中心性结点传递信息，对BubbleRap算法进行修改。

社会属性驱动的容迟网络路由改良算法，进一步的，提出均衡整体中介中心性和局部中介中心性的改良方法，即结点整体中介中心低于捎带数据的结点，若此结点在自己所属社区的局部中介中心性较高，且所属的社区数据较多，则捎带数据结点也可以将信息转发给此结点，本发明提出利用加权的方式均衡整体中介中心性和局部中介中心形成评估中介中心性，同时利用局部中介中心的方差进一步调整局部中介中心在评估中介中心性中的比例；

方差定义为各个数字与平均数之差的平方和的平均数，表示各个数与均值之间的偏离程度，一个结点可属于很多社区，结点可能有很多个局部中介中心性，在结点整体中介中心性一样和局部社区个数一样的情况下，局部中介中心性平均值越高，同时中介中心性的方差越小，表明结点在它所属的社区活跃度均衡，利用局部中介中心性的方差调节局部中介中心性在传递数据中的作用，其计算式为：

H(i)＝R{[x-R(x)]

其中R(x)表示结点x局部中介中心性的均值，方差的范围太大，本发明对方差进行进一步处理，将其归一化，其计算式为：

根据式2得出b的范围为0到1，通过加权将整体中介中心性和局部中介中心性均衡成一个评估中介中心性，其公式为：

其中J

社会属性驱动的容迟网络路由改良算法，进一步的，采用二分法转发方法从源头上控制副本的数量，并且对二分法转发方法进行改良，使其更适应Bubble Rap算法特点，减少因控制副本数量影响信息传递的投递率；

本发明二分法转发方法工作方法：结点i捎带m个数据副本，当结点i遇到结点j时，如果结点j是目的结点，则结点i将数据转发给结点j，结点i删除数据副本，如果结点j不是目的结点且j里面没有该数据副本，当数据副本数量m大于1时，结点i则转发自己的一半的数据副本给结点j，即结点i转发m/2个信息副本给节点j，自己保留剩下的m-m/2个数据副本；当结点只剩下一个数据副本，即m＝1时，则结点不在转发数据，直到遇到目的结点或数据过期而删除；二分法转发方法是一个基于平衡的二叉树的转发，如果网络中的结点数量是M，则二叉树的深度Y为：

Bubble Rap中传递数据利用结点的中介中心性，提高数据的有效传输，本发明将整体中介中心性和局部中介中心性合成评估中介中心性，评估中介中心越高的结点，其将信息传递到目的结点的概率越高，二分法转发方法中当副本数量为1是，则不再转发数据，期望评估中介中心性越高的结点获得越多的副本用来传递，在改良的二分法转发的算法中，本发明利用结点的评估中介中心性，结点转发副本数量不是转发一半的数据，而是根据评估中介中心性确定转发的副本数量，其转发数量的公式为：

其中m为转发数量，n为结点i捎带的副本数量，J

二分法转发方法改良在传递数据的过程中利用洪泛机制，加快结点的信息传播速度，在信息的源头控制副本的数量，降低网络中的副本数量，同时利用评估中介中心性改良二分法转发方法中每次转发数据副本的个数，使活跃结点获得更多的副本数量，进一步提高信息的传播速度；在选择是否转发数据时，比较结点的评估中介中心性，解决Bubble Rap算法中导致信息可能不能传递到具有较低整体中介性的目的结点的问题。

社会属性驱动的容迟网络路由改良算法，进一步的，采用将数据以一定的概率转发到比自己的评估中介中心性小的结点，若结点的评估中介中心性越大，局部中介中心性越均衡，并且所属的社区越多，这种结点越可能将信息传递到目的结点，本发明综合考虑结点的评估中介中心性、结点所属社区的个数和结点局部中介中心性来确定转发概率，其计算式为：

其中b为结点局部中介中心方差的归一化的结果，如果遇到的结点比本结点的评估中介中心性低的话，结点将以概率q转发一个数据副本给此结点，本结点的副本数量不变，根据改良的二分转发方法，较低评估中介中心性获取到一个数据副本后，直到遇到目的结点所在的社区结点才转发信息，其他情况这不转发，以一定的概率向评估中介中心性较低的结点转发数据；

数据传输的过程中采用二分法的转发方法，该算法在洪泛过程中，加快信息扩散速度，降低网络时延，但增加网络的副本数量，而以一定概率向评估中介中心性较低的结点传递数据，增加网络中的副本数量。

社会属性驱动的容迟网络路由改良算法，进一步的，本发明采用控制数据副本过期时间TTW，进一步控制网络中副本数量，改良后的二分转发方法，结点在向比自己评估中介中心性高的结点转发数据副本的数量计算得到，在转发数据后，源结点的TTW值应减小，因为它需要传递的信息，已经有更好的结点帮助它在传递，这也符合Bubble Rap算法的基本思想，选择活跃度更高的结点帮助转发数据，其中G-Bubble Rap算法在转发数据后，直接删除源结点中的数据副本,本发明提出修改TTW值的公式，其公式为式6：

其中TTW(i)表示结点传递数据后剩余的TTW时间，J

社会属性驱动的容迟网络路由改良算法，进一步的，本发明改良的Bubble Rap算法描述：结点计算出自己的评估中介中心性，当结点i遇到结点j时，如果结点j是目的结点或目的结点所在的社区结点，则直接转发数据给结点j，同时删除本结点中关于此数据的信息；如果结点j不是目的结点或目的结点所在社区的结点，比较彼此的评估中介中心性，如果结点j的评估中介中心性小于结点i的评估中介中心性，则获取传递概率q，结点i以q的概率传递数据副本给结点j，传递数据的副本数量为1，原副本数量变；如果结点j的评估中介中心性大于结点i的评估中介中心性，结点i计算出需要传递给结点的j的数据副本数量，同时计算出结点i中副本的剩余的TTW值，如果结点i的数据副本数量为1则不转发,数据传递到目的结点所在社区后，用结点的局部中介中心性替换评估中介中心性。

与现有技术相比，本发明的贡献和创新点在于：

第一，本发明提供的社会属性驱动的容迟网络路由改良算法，针对Bubble Rap将数据快速传递到结点整体中介中心性较高的结点，会导致结点整体中介中心性较低的结点可能不能获得消息，提出了均衡整体中心中介度和局部中心中介的评估中介中心性的方案，并且提出了结点有一定的概率向评估中介中心性低的结点传递数据，Bubble Rap在数据传输过程中采用基于洪泛的机制，为降低网络中副本数量，采用基于改良的二分转发方法进行数据传输和TTW时间，在对传输速度较小的影响下，大幅降低了网络中的副本数据，降低了网络负载和结点资源，提高了网络性能；

第二，本发明提供的社会属性驱动的容迟网络路由改良算法，分析了Bubble Rap算法存在的不足，提出了具体的修改方案，进一步提高数据的投递率、降低网络时延和网络负载；根据Bubble Rap路由算法数据转发依赖于整体中介中心性，而中介中心性高的结点不代表结点在所有社区的活跃度都较高等不足，本发明提出改良方案，利用加权和局部中介中心性方差来均衡整体中介中心性和局部中介中心性，提出评估中介中心性，已选择更优的结点作为转发结点，在数据传输的过程中，为克服洪泛机制和单副本路由的不足，利用二分法转发方法转发数据，并修改二分法数据转发数据副本数量的计算方式，让活跃度较高的结点获得更多的副本，以便数据快速传递出去，以一定的概率向评估中介中心性较小的结点转发数据，倾向于将数据转发给活跃度较高，所属社区较多且局部中介中心性活跃度均衡的结点，使得信息有概率的传递到网络中各个层次的社区中，避免因目的结点所在社区活跃度较低而无法获取其他结点发送的信息；为进一步的控制网络中数据副本数量，在数据转发的同时，修改原结点中转发数据副本的TTW值，使结点中数据副本的过期时间变短，减少网络副本的数量，较大程度避免了洪泛机制导致的网络拥塞；

第三，本发明提供的社会属性驱动的容迟网络路由改良算法，针对Bubble Rap容迟网络路由策略根据社会属性中的中介中心作为转发数据的依据，但中介中心性越高，并不能代表结点在所有社区都高，而且信息向整体中介中心较高的结点汇聚，导致信息不能传递到中介中心性较低的目的结点，在转发数据后是否删除原数据，若删除则是单副本，不删除则变成洪泛机制，前者导致信息扩散速度慢，而后者随着网络规模增大，网络会出现拥塞，针对Bubble Rap算法存在的这些不足，本发明在Bubble Rap的基础上进行修改优化，提出社会属性驱动的容迟网络路由改良算法，较好的解决上述存在的问题，从而进一步提高容迟网络Bubble Rap路由性能，算法实用高效、易于扩展、精准高速，具有交互性能强、智能化程度高、可扩展性高、语言移植能力好等优势，是一种具备显著创新性，且优势突出的容迟网络路由算法，具有巨大的利用价值和市场运用空间。

附图说明

图1是本发明的二分法转发方法改良示意图。

图2是本发明改良后的Bubble Rap算法的流程示意图。

具体实施方式

下面结合附图，对本发明提供的社会属性驱动的容迟网络路由改良算法的技术方案进行进一步的描述，使本领域的技术人员可以更好的理解本发明并能予以实施。

本发明分析了Bubble Rap算法存在的不足，提出了具体的修改方案，进一步提高数据的投递率、降低网络时延和网络负载。根据Bubble Rap路由算法存在信息快速传递到整体最活跃结点，拥有数据的活跃结点可能与目的结点所在的社区没有联系；结点转发数据后，删除原副本数据则转发数据是基于单副本路由的方式传递，不删除原副本数据则转发数据是基于洪泛机制，前者数据扩散速度慢且易错过与目的结点相遇的机会，后者导致网络中副本数据增加，引起网络拥塞；数据转发依赖于整体中介中心性，而中介中心性高的结点不代表结点在所有社区的活跃度都较高等不足，本发明提出改良方案，利用加权和局部中介中心性方差来均衡整体中介中心性和局部中介中心性，提出评估中介中心性，已选择更优的结点作为转发结点，在数据传输的过程中，为克服洪泛机制和单副本路由的不足，利用二分法转发方法转发数据，并修改二分法数据转发数据副本数量的计算方式，让活跃度较高的结点获得更多的副本，以便数据快速传递出去，以一定的概率向评估中介中心性较小的结点转发数据，倾向于将数据转发给活跃度较高，所属社区较多且局部中介中心性活跃度均衡的结点，使得信息有概率的传递到网络中各个层次的社区中，避免因目的结点所在社区活跃度较低而无法获取其他结点发送的信息。为进一步的控制网络中数据副本数量，在数据转发的同时，修改原结点中转发数据副本的TTW值，使结点中数据副本的过期时间变短，减少网络副本的数量，较大程度避免了洪泛机制导致的网络拥塞。

根据本申请对Bubble Rap路由算法不足的分析，本发明提出了基于Bubble Rap算法的容迟网络路由改良方法，算法改良中使用的核心概念为：

概念一，时间TTW，一个信息在创建后，在系统存在的最大时间，即信息过期时间，避免信息长期停留在系统中，占用有限的系统资源；

概念二，副本数量W，信息在创建时，结点可创建的最大的信息备份数量；

概念三，F-Bubble Rap算法是指在Bubble Rap路由算法中转发数据后，不删除原结点中的数据副本；

概念四，G-Bubble Rap算法是指在Bubble Rap路由算法中转发数据后，删除原结点中的数据副本。

一、整体中介中心性与局部中介中心性改良

中介中心性是结点处在其他结点最短路径上的次数，整体中介中心性是结点落在网络中所有结点之间最短路径上的次数，结点整体中介中心性越高，则结点在全网中活跃度越高，这个结点可能频繁的出入各个社区，局部中介中心性是结点落在社区中所有结点之间最短路径上的次数，结点局部中介中性度越高，结点在社区内部活跃度越高。

Bubble Rap根据整体中介中心性和局部中介中心性，先将信息快速传递到整体中介中心性较高的结点，直到信息传递到目的结点所在社区后，采用局部中介中心性替换整体中介中性心，直到信息传递给目的结点，这种数据转发策略可能导致那些社区中所有结点的整体中介中心性都较低的结点无法接收到来至其他社区的信息，Bubble Rap算法存在这个不足的主要原因是整体中介中心性较高并不表结点在所有社区都有较高的活跃度。为解决这个问题，本发明提出均衡整体中介中心性和局部中介中心性的改良方法，即结点整体中介中心低于捎带数据的结点，若此结点在自己所属社区的局部中介中心性较高，且所属的社区数据较多，则捎带数据结点也可以将信息转发给此结点，本发明提出利用加权的方式均衡整体中介中心性和局部中介中心形成评估中介中心性，同时利用局部中介中心的方差进一步调整局部中介中心在评估中介中心性中的比例。

方差定义为各个数字与平均数之差的平方和的平均数，表示各个数与均值之间的偏离程度，一个结点可属于很多社区，结点可能有很多个局部中介中心性，在结点整体中介中心性一样和局部社区个数一样的情况下，局部中介中心性平均值越高，同时中介中心性的方差越小，表明结点在它所属的社区活跃度均衡，利用局部中介中心性的方差调节局部中介中心性在传递数据中的作用，其计算式为：

H(i)＝R{[x-R(x)]

其中R(x)表示结点x局部中介中心性的均值，方差的范围太大，本发明对方差进行进一步处理，将其归一化，其计算式为：

根据式2得出b的范围为0到1，通过加权将整体中介中心性和局部中介中心性均衡成一个评估中介中心性，其公式为：

其中J

二、二分法转发方法改良

Bubble Rap算法传递时删除原副本，则是单副本路由，存在信息扩散速度慢的不足且易错过与目的结点相遇的机会，而传递过程中不删除原副本，则数据是以洪泛机制传递给中介中心性大于本结点的结点，存在网络负载增加的不足。针对Bubble Rap是否删除原副本数据都存在明显不足，本发明在Bubble Rap是否删除原副本数据上采用折中的办法，依然采用洪泛机制进行数据传递，但控制网络中副本的数量，避免洪泛机制导致网络负载增加而影响网络性能，本发明采用二分法转发方法从源头上控制副本的数量，并且对二分法转发方法进行改良，使其更适应Bubble Rap算法特点，减少因控制副本数量影响信息传递的投递率。

本发明二分法转发方法工作方法：结点i捎带m个数据副本，当结点i遇到结点j时，如果结点j是目的结点，则结点i将数据转发给结点j，结点i删除数据副本，如果结点j不是目的结点且j里面没有该数据副本，当数据副本数量m大于1时，结点i则转发自己的一半的数据副本给结点j，即结点i转发m/2个信息副本给节点j，自己保留剩下的m-m/2个数据副本；当结点只剩下一个数据副本，即m＝1时，则结点不在转发数据，直到遇到目的结点或数据过期而删除。其过程可以用图1表示：二分转发法(i,5)表示结点i捎带5个数据副本，图中的过程为：结点i捎带5个数据(i,5)遇到结点j，结点j不是目的结点且j没有该数据副本，由于5＞1,所以结点i转发数据的一半给数据结点j，结点j在转发后变成(j,2)，而结点i变成(i,3)，依次类推，结点i遇到结点y和z，结点i分别转发数据给了y和z，结点j遇到结点n，转发数据给n，直到结点拥有的副本数量只剩下一个；二分法转发方法是一个基于平衡的二叉树的转发，如果网络中的结点数量是M，则二叉树的深度Y为：

Bubble Rap中传递数据利用结点的中介中心性，提高数据的有效传输。本发明将整体中介中心性和局部中介中心性合成评估中介中心性，评估中介中心越高的结点，其将信息传递到目的结点的概率越高，二分法转发方法中当副本数量为1是，则不再转发数据，期望评估中介中心性越高的结点获得越多的副本用来传递，在改良的二分法转发的算法中，本发明利用结点的评估中介中心性，结点转发副本数量不是转发一半的数据，而是根据评估中介中心性确定转发的副本数量，其转发数量的公式为：

其中m为转发数量，n为结点i捎带的副本数量，J

二分法转发方法改良在传递数据的过程中利用了洪泛机制，加快结点的信息传播速度，在信息的源头控制副本的数量，降低网络中的副本数量，同时利用评估中介中心性改良二分法转发方法中每次转发数据副本的个数，使活跃结点获得更多的副本数量，进一步提高信息的传播速度；在选择是否转发数据时，比较结点的评估中介中心性，避免将信息传递给那些拥有很高的整体中介中心性，导致目的结点所在社区的整体中介中心性都很低的结点，无法获取信息。解决了Bubble Rap算法中导致信息可能不能传递到具有较低整体中介性的目的结点的问题。

三、按概率转发信息给较低评估中介中心性结点

Bubble Rap算法导致某些信息不能传递到目的结点的根本原因，是结点在转发数据，只转发给那些中介中心性比本结点中介中心性高的结点，而中介中心高的结点可能与目的结点所在社区的结点无联系，导致拥有数据的结点可能都不会与目的结点所在社区中的结点相遇，数据逐步往上冒，如果遇到目的结点所在社区的结点，则转向目的社区结点所在社区，如果在冒泡的时候，不能遇到目的结点所在的社区结点，则数据转发失败。虽然本发明采用了评估中介中心性来选择传递数据的结点，利用加权的方式均衡了整体中介中心性和局部中介中心性，一定程度上避免了上述情况，但问题解决不彻底，为进一步解决该问题，采用将数据以一定的概率转发到比自己的评估中介中心性小的结点，进一步降低上述情况发生的概率；若结点的评估中介中心性越大，局部中介中心性越均衡，并且所属的社区越多，这种结点越可能将信息传递到目的结点，所以本发明综合考虑结点的评估中介中心性、结点所属社区的个数和结点局部中介中心性来确定转发概率，其计算式为：

其中b为结点局部中介中心方差的归一化的结果，其计算式为式2，如果遇到的结点比本结点的评估中介中心性低的话，结点将以概率q转发一个数据副本给此结点，本结点的副本数量不变，根据改良的二分转发方法，较低评估中介中心性获取到一个数据副本后，直到遇到目的结点所在的社区结点才转发信息，其他情况这不转发，以一定的概率向评估中介中心性较低的结点转发数据，不会大幅增加网络中副本的数量。

数据传输的过程中采用二分法的转发方法，该算法在洪泛过程中，加快信息扩散速度，降低网络时延，但增加网络的副本数量，而以一定概率向评估中介中心性较低的结点传递数据，增加了网络中的副本数量。下面进一步控制网络中数据副本的数量。

四、控制数据副本数量

Bubble Rap数据转发策略中存在结点转发数据后，是否删除源结点的数据信息，如果不删除数据信息，则数据扩散采用洪泛的方式，网络副本数据会增加，如果删除数据信息，则数据传递方式就变成单副本传递，扩散速度较慢，网络时延高，信息的投递率也会降低。在改良的Bubble Rap算法中采用折中的办法，数据传输过程采用改良的二分法转发方法，与直接洪泛机制相比降低了数据副本数量，但随着网络规模的变大，数据副本数量规模还是很大。虽然通过调整源副本数量W的大小，控制网络中副本的数量，但如果W的数量太小，将影响信息的投递率。

所以本发明采用控制数据副本过期时间TTW，进一步的控制网络中副本数量，改良后的二分转发方法，结点在向比自己评估中介中心性高的结点转发数据副本的数量通过式4计算得到，那么在转发数据后，源结点的TTW值应减小，因为它需要传递的信息，已经有更好的结点帮助它在传递，这也符合Bubble Rap算法的基本思想，选择活跃度更高的结点帮助转发数据，其中G-Bubble Rap算法在转发数据后，直接删除源结点中的数据副本,本发明提出修改TTW值的公式，该公式与式4类似，其公式为式6：

其中TTW(i)表示结点传递数据后剩余的TTW时间，J

五、改良后的Bubble Rap算法

本发明提出评估中介中心性来进一步提高选择转发结点的准确性，同时利用改良的二分转发方法对F-Bubble Rap算法和G-Bubble Rap算法中是否删除原副本数据进行折中，为进一步控制网络副本数量，在数据转发后，减小结点中原副本的TTW值，从而减小副本在系统中的生存时间，达到减小网络中副本数量的目的，Bubble Rap的基本思想是信息向具有较高活跃度的结点传递，在传递的过程中遇到目的结点所在社区的结点，则转发信息给此相遇结点，然而现实情况下，存在信息在传递的过程的所有结点与目的结点所在社区的结点都没有联系，则信息传递失败。本发明提出以一定的概率向较低中介中心性结点传递信息，从而较大程度上解决了上述问题，根据以上的修改方案，本发明对Bubble Rap算法进行修改，改良后的Bubble Rap算法的流程如图2所示：

改良的Bubble Rap算法描述：结点通过式3计算出自己的评估中介中心性，当结点i遇到结点j时，如果结点j是目的结点或目的结点所在的社区结点，则直接转发数据给结点j，同时删除本结点中关于此数据的信息；如果结点j不是目的结点或目的结点所在社区的结点，比较彼此的评估中介中心性，如果结点j的评估中介中心性小于结点i的评估中介中心性，则根据式5获取传递概率q，结点i以q的概率传递数据副本给结点j，传递数据的副本数量为1，原副本数量变；如果结点j的评估中介中心性大于结点i的评估中介中心性，结点i根据式4计算出需要传递给结点的j的数据副本数量，同时根据式6计算出结点i中副本的剩余的TTW值，如果结点i的数据副本数量为1则不转发,数据传递到目的结点所在社区后，用结点的局部中介中心性替换评估中介中心性，并不以一定的概率向评估中介中心性较低的结点转发数据。

本发明对基于社会属性的容迟网络的路由算法进行研究和改良，容迟网络是一个较新的领域，也是未来网络的重要组成部分，容迟网络拥有自己的特征，如高延迟、结点间歇链接，结点资源有限、分组丢失率高和结点稀疏布置等特征，特别是结点之间不存在完整的通信链路，传统的网络无法适应容迟网络。基于容迟网络的特点，现有技术提出了一些路由算法，随着智能通讯中断的大量使用，利用这些设备组成通讯网络成为可能，而这种网络完全符合容迟网络的特点，利用社会属性来作为转发数据的结点的选择依据，利用社会属性作为转发数据结点选择依据非常有效，Bubble Rap路由算法通过整体中介中心性将数据快速的传递到整体中介中心性较高的结点里，数据传输的过程采用洪泛机制，在BubbleRap路数算法的基础上，本发明分析了其存在的不足，提出了对应的解决的方案，BubbleRap将数据快速传递到结点整体中介中心性较高的结点，会导致结点整体中介中心性较低的结点可能不能获得消息，提出了均衡整体中心中介度和局部中心中介的评估中介中心性的方案，并且提出了结点有一定的概率向评估中介中心性低的结点传递数据，Bubble Rap在数据传输过程中采用基于洪泛的机制，为降低网络中副本数量，采用基于改良的二分转发方法进行数据传输和TTW时间，在对传输速度较小的影响下，大幅降低了网络中的副本数据，降低了网络负载和结点资源，提高了网络性能。本发明利用ONE模拟器对改良的BubbleRap算法进行了仿真分析，得出改良的Bubble Rap算法在系统开销和平均时延和两个版本Bubble Rap中最优的那个接近的情况下，取得非常好的数据成功投递率和平均跳数，证明了修改的路由算法要大幅好于原始的Bubble Rap路由算法。