基于相遇概率时效性和重复扩散感知的机会网络消息转发算法

葛 宇，梁 静

（1.四川师范大学计算机科学学院，成都610068； 2.成都工业学院计算机工程学院，成都610031）（∗通信作者电子邮箱liangj@189.cn）

0 引言

机会网络在节点移动过程中自我组织而形成，没有固定的拓扑结构，消息转发投递需要借助节点移动相遇形成的通信机会进行传输，即以“存储-携带-转发”的路由模式实现节点间通信［1-2］。在这种模式中，消息在中继节点上缓存；当两个节点相遇时进行消息转发，直到消息到达目的节点。由于不需要固定设备辅助通信，机会网络能很好地适应拓扑变化场景［3-4］，如：移动电子商务、野生数据收集、深海网络等。

机会网络中，如何让消息在节点间被合理转发、快速投递，是当前研究热点之一［5］。针对机会网络中的消息转发问题，目前有学者基于有限消息冗余、节点相遇概率等策略提出了一些解决方案［2，5］，但还面临如下问题：

1）在使用节点相遇概率指导消息选择中继节点时，由于节点无法实时获取完整的全局网络信息，导致节点间接相遇概率分析中存在数据延迟问题。

2）消息在选择不同节点进行扩散的过程中，可能被运动相似的节点同时携带，从而导致重复扩散，不利于消息全局搜寻目标节点，降低了扩散效率。

针对以上分析，本文从节点直接、间接相遇情况以及对应的相遇概率时效性入手，结合对消息重复扩散问题的分析，提出消息转发效用，并设计了相应的消息副本转发算法，用于帮助消息选择合理的中继节点。

1 相关工作

在机会网络中，如何利用消息冗余和节点相遇机会有效转发数据，是现今机会网络研究的一个重要方向［5］，目前具有代表性的研究成果如下：

文献［6］提出Epidemic算法，核心思想是网络中节点相遇时，直接复制转发对方缓存中缺少的消息，其主要优点在于不考虑缓存限制的情况下可以增加数据传递的成功率，降低传输延迟，但是网络中会产生非常多数据副本，占用大量的网络资源，造成不必要的浪费。文献［7］在Epidemic算法基础上进行了改进，利用节点局部位置信息来控制消息的扩散范围，利用多种效用信息筛选出最优的节点进行消息复制转发，一定程度上控制了网络开销。

文献［8］提出了SAW（Spray And Wait）算法，算法分为两个阶段寻找消息目的节点：节点相遇时，在Spray阶段，消息以复制转发的形式在网络中扩散；当消息副本数达到指定阈值后进入Wait阶段，此时消息不再被复制转发，仅等待和目的节点相遇。该算法通过控制消息副本数量，降低了路由开销。文献［9］改进了SAW算法，利用中心节点搜集全局信息，对网络状况进行评估，动态控制消息副本数量阈值，实现了消息副本数随网络状况自适应调整。

文献［10］介绍了基于概率策略的ProPHET算法，该算法利用一个预测值来评估消息被节点成功投递的概率。当两个节点相遇时，节点更新各自的预测值，并根据该值来判断是否进行数据传输，以此来控制消息副本扩散和网络开销。Maxprop路由算法［11］利用了ProPHET算法的思路，通过跳数估算投递开销，并结合投递概率对消息进行排序，从而控制消息转发，提高了投递成功率，但其消息优先级机制会影响消息投递效率，转发策略可能导致消息盲目扩散。文献［12］为了避免消息被盲目转发，将模糊数学原理用于消息转发效用设计中，在ProPHET算法基础上利用模糊模型改进了消息中继节点选择策略。

2 消息转发效用设计

2.1 节点相遇概率及时效性

消息携带节点与消息目的节点的相遇概率对应了该消息的投递概率，目前的研究认为：移动机会网络中节点相遇间隔时间符合指数分布［13-15］。据此，以下分别对节点直接相遇、间接相遇情况进行讨论。

1）节点直接相遇情况下，相遇间隔时间对应的指数分布概率密度函数如式（1）：

2）当两节点间接相遇时（如节点nj依次经历了中继n1，n2，…，nn后与nD相遇），文献［16］指出其相遇间隔时间属于高阶指数分布，对应的密度函数如式（2）：

式（1）、（2）中λ表示两节点的相遇频率。将以上密度函数变换为分布函数即可得出节点之间的直接、间接相遇概率，从而表示出节点nj携带消息mk在生存时间（Time To Live，TTL）内与其目的节点nD的相遇概率（即消息投递概率），如式（3）：

式（3）用节点nj与消息mk目的节点nD的相遇概率来表示nj对mk的投递概率；其中V={njn1，n1n2，…，nnn D}描述了nj与nD间接相遇过程。

在实际应用中，消息大多情况下是被间接投递到目的节点［1］。值得注意的是，文献［16］提出的间接相遇时间间隔密度函数式（2）没有考虑相遇频率参数λ的时效，从而会导致式（3）计算间接投递概率存在时效问题，具体分析如下。

图1中，线段n0、n1、n2、nD分别表示4个节点在某时段内的移动轨迹，n0携带有目的节点为nD的消息mk。在T1时刻n0与n1相遇，为了评估n1作为中继成功投递mk的概率，n1根据式（3）计算出与nD的间接相遇概率如式（4）：

其中：λn2nD表示n2、nD间的相遇频率，结合图1可以看出T1时刻式（4）中λn2nD参数只能从最近一次n2、nD的相遇过程中（T0时刻）获取，因此T0到T1时间段内n2、nD的相遇情况没有反映到λn2nD中，必然对相遇概率的计算结果造成不利影响。不难看出造成上述问题的原因是程序获取了过时的λ参数，据信息管理学中逐渐过时定律［17］可知，λ参数更新时间越久，对应的信息价值越低，从而导致了相遇概率式（3）计算结果的信息价值降低。特别地，若消息间接投递过程中经历的中继节点越多，出现上述问题的可能性越大。

图1 节点相遇情况Fig.1 Node encounter situation

基于以上分析，为评估节点相遇概率的信息价值，以下从λ参数更新延迟角度定义了时效指标R。

定义1 时效指标。令T表示当前时刻，ε代表节点nj到nD间接相遇集合V={njn1，n1n2，…，ni nD}中各项，nD表示消息mk目的节点，tε表示V中各项对应的最近相遇时刻（即最后一次获取相应λ参数的时刻），T表示当前时刻(T＞tε)，nj与消息mk目的节点相遇对应的时效指标R如式（5）：

需要说明的是R(mk，nj)∈(0，1)，其值越小说明延时越高；T-tε表示相应λ参数的延迟，和R值大小成反比；nj和第一转发节点n1是直接相遇，不需要考虑λnjn1延迟问题，故令ε≠njn1。特别地，若nj与n D直接相遇，不存在延时问题，令指标值为1。

2.2 消息重复扩散问题

文献［5］指出，携带有相同消息副本的节点，在移动过程中应尽可能地避免出现在同一区域，这样有利于提高消息的扩散效率和投递成功率。为此，以下对节点运动方向相似可能引起消息被重复扩散的问题进行了讨论，定义了节点移动偏离指标，用于评价消息在节点间被重复扩散的可能性。

在常见的移动模型（如 RandomWaypoint、MapBasedMovement、MapRouteMovement等）中，移动节点可获取当前的位置和运动方向［18］。如图2所示：设t时刻n0与候选集合U={n1，n2，n3，n4}中节点相遇，n0需要从U中选择中继节点帮助扩散自身的缓存消息。箭头方向表示节点的移动方向，r表示节点的通信半径。结合图中节点n0、n1的运动方向和通信半径可知，阴影部分就是两节点移动中通信范围重合的区域，若两节点均携带有相同消息副本，必然会在该区域造成重复扩散，降低了消息副本的使用效率（同理，n3、n4间携带相同消息也会造成重复扩散）。相反，n0、n2节点当前移动方向对应的通信范围几乎不会重叠，相同消息副本若在n0、n2之间复制转发出现重复扩散的可能性较小。

图2 节点运动相似分析Fig.2 Motion similarity analysisof nodes

结合以上分析不难看出：节点间的移动方向偏离程度直接关系到它们是否会造成消息重复扩散。为此，以下基于“夹角余弦法”定义了节点移动偏离指标。

定义2 节点移动偏离指标。当前运动方向分别为ni与nj的两节点对应的移动偏离指标记为K（ni，nj），如式（6）：

式（6）满足以下特性：

1）K（ni，nj）的取值范围是［0，1］，其值越小说明ni、nj间运动方向偏离小、运动相似度高，对应的消息被重复扩散可能性高；反之，消息被重复扩散的可能性越低。

2）节点静止时没有对应的运动方向信息，因此本文在ni、nj任一节点处于静止状态时，为K（ni，nj）随机指定［0，1］范围值。

2.3 消息转发效用

结合前文对节点相遇概率时效性和消息重复扩散问题的分析，以下定义了消息转发效用，用于评价节点成功投递消息的可能性，具体描述如下。

定义3 消息转发效用。设携带有消息mk的节点ni与一组未携带消息mk的节点U=｛nj|j=1，2，3，…｝相遇（U中不含mk的目的节点），U中每个节点nj对应消息mk的转发效用定义如式（7）：

式（7）中各项描述如下：

1）从消息被投递概率角度考虑，根据式（3）引入了概率调节项P（mk，nj），其值与W（mk，nj）成正比。

2）根据2.1节中对间接投递延时问题的分析，为降低延时对消息投递概率（即节点相遇概率）的影响，式（7）使用时效指标R（mk，nj）作为调节项，当延时较大时，R（mk，nj）值变小，从而降低P（mk，nj）的影响力。

3）根据2.2节的分析，从尽可能减小消息被重复扩散的角度出发，应尽量避免ni把消息转发给和自身移动偏离指标小的节点，为此式（7）将节点偏离度K（ni，nj）作为调节项，表示U中节点nj相对ni的运动偏离程度，其值大小与效用W（mk，nj）成正比。另外，还应该避免ni把消息转发给集合U内部偏离度小的节点（即U内部相互之间运动方向相似度高的节点），式（7）用偏离度平均值Q(nj，U)表示节点nj对应的内部偏离度，其值越小说明nj与U中其他节点运动相似度较大，对应式（7）降低调节项K(ni，nj)的影响力。

3 依据效用的消息副本转发算法设计

基于前文对节点相遇概率时效和消息重复扩散可能性的分析，并参考文献［8］SAW算法的副本数量控制机制，本文以消息转发效用式（7）为基础设计了消息副本转发算法。算法中，每个节点中存在以下数据结构：

1）直接相遇节点历史信息如表1（以下简记为DE表）。节点ni对应的DE表记为DE（ni），记录与ni直接相遇过的节点信息。

表1 直接相遇节点历史信息Tab.1 Direct encounter nodehistorical information

2）间接相遇节点历史信息如表2（以下简记为IDE表）。节点ni对应的IDE表记为IDE（ni），id1、id2表示相遇节点双方的id，IDE（ni）表记录除ni外的其他节点相遇信息，用于后续计算间接相遇路径。

表2 间接相遇节点历史信息Tab.2 Indirect encounter nodehistorical information

3）节点携带的消息副本信息如表3（以下简记为M表）。节点ni对应的M表记为M（ni），其中消息内容字段包含了网络数据包的所有内容，候选中继字段记录了当前可以帮助消息转发的中继节点相关信息。

表3 节点携带的消息副本信息Tab.3 Messagecopy information carried by node

假设ni与集合U=｛nj|j=1，2，…｝中节点相遇，ni通过如下步骤对自身携带的消息副本进行处理（其中，消息转发效用的计算和运用主要体现在步骤4）：

步骤1U中每个节点与ni交换并更新相遇信息，具体操作如下：

1.1）nj(nj∈U)去掉DE（nj）和IDE（nj）中过期记录后同自身信息一起发送给ni。

1.2）ni接收后将nj信息更新到DE（ni），同时根据DE（nj）和IDE（nj）更新自身IDE（ni）。

1.3）ni去掉DE(ni)和IDE(ni)中过期记录后同自身信息一起发送给nj。

1.4）nj接收后将ni信息更新到DE(nj)，同时根据DE(ni)和IDE(ni)更新自身IDE(nj)。

1.5）ni根据式（6）计算与nj的移动偏离指标K(ni，nj)。

步骤2ni计算U中各节点的内部偏离度，即U内平均移动偏离指标Q(nj，U)。

步骤3ni清空M（ni）中所有消息的候选中继字段。

步骤4 针对M（ni）中每个消息mk，遍历U中每个节点nj，计算转发效用并选择合理的转发节点，具体如下：

4.1）若消息mk的目的节点等于nj(nj∈U)，投递消息并为其作删除标记。

4.2）针对M（ni）中没有删除标记且不在M（nj）中的消息mk，由式（3）、（5）分别计算P（mk，nj）和R（mk，nj）。

4.3）结合步骤1.5、步骤2和步骤4.2的计算结果，由式（7）计算nj相对消息mk的转发效用W（mk，nj），并记录到M（ni）中对应消息的候选中继字段。

4.4）mk遍历完U中节点后，从候选中继中用选择效用值大于随机值rand∈［min（W（mk，nj）），max（W（mk，nj））］的节点进行副本数减半操作并转发。

步骤5 删除M（ni）中有删除标记的节点。

以上步骤对应的伪代码如下：

从以上消息副本转发算法流程描述可以看出，在ni与集合U中节点相遇后进行消息转发处理的主要过程中较少使用循环嵌套，其中交换更新信息过程对应的时间复杂度为O(|U|)（步骤1）；ni为自身缓存中每个消息选择中继并转发的过程对应时间复杂度为O（|M（ni）|×|U|）（步骤4）。

4 仿真验证及结果分析

为了验证本文算法的性能，实验在ONE模拟器［18］上仿真运行了本文算法和Epidemic、ProPHET、Maxprop、SAW算法，并在不同缓存大小和不同消息TTL的情况下从成功率、平均延时、开销指标对算法进行评价。其中，成功率是整个网络成功传递的消息数和产生的所有消息数之比值，值越高说明在转发消息时选择的中继节点越合理；平均延时是指网络中所有消息从源节点产生到成功投递的延迟时间平均值，值越小表示消息传递的速度越快，说明算法的转发效率越高；开销是指消息被传递总次数与成功传递的消息数之差，再和成功传递的消息数求比值，网络开销比率越小表示网络性能越优。

本文实验利用ONE自带的赫尔辛基城市地图为仿真场景、ShortestPathMapBasedMovement和 MapRouteMovement作为节点的移动模型，在4 500 m×4 300 m的网络区域内布置三类节点（步行、汽车和电车），仿真时间43200 s，具体参数如表4，其余参数采用模拟器默认设置。

表4 网络参数Tab.4 Network parameters

1）节点缓存变化情况下五种算法对比。

图3～5显示了五种算法随节点缓存逐渐增大，TTL固定在120 min时对应的成功率、开销、投递延时结果。

图3 节点在不同缓存下对应的消息投递成功率对比Fig.3 Comparison of messagedelivery success ratebetween nodes in different caches

图4 节点在不同缓存下对应的消息平均投递开销对比Fig.4 Comparison of average messagedelivery cost between nodesin different caches

从图中可以看出：本文算法在3个指标上均优于ProPHET和Epidemic算法；和SAW算法相比，本文算法的投递成功率在缓存大于3～9 MB间提高约7%～18%，9 MB后略有提高，开销指标和延迟指标接近SAW算法；和Maxprop算法相比，本文算法的投递概率缓存在3～9 MB时略高，但对应的开销和延时指标本文算法明显领先。

图5 节点在不同缓存下对应的消息平均投递延时对比Fig.5 Comparison of average message delivery delay between nodes in different caches

2）消息TTL变化情况下五种算法对比。

图6～8显示了五种算法随消息生存时间TTL逐渐增大，缓存固定30 MB时对应的结果。从图中可以看出：随着TTL的增大，本文算法取得了比ProPHET、Epidemic算法更好的结果；相比SAW算法，本文算法在投递成功率上领先了2%～18%，开销指标上和延时指标略有减小；相比Maxprop，本文算法的投递成功率在TTL∈(20，90)时略高，但开销和延时指标本文算法领先。

图6 在不同TTL下对应的消息投递成功率对比Fig.6 Comparison of message delivery success rates under different TTL

图7 在不同TTL下对应的消息平均投递开销对比Fig.7 Comparison of message average delivery cost under different TTL

从以上实验结果可以看出：在节点缓存变化或消息TTL变化的情况下，本文算法因为采用了更合理的中继选择方案（通过转发效用综合考虑了节点相遇概率时效和消息重复扩散可能性），在三个指标上均优于Epidemic和ProPHET算法；与Maxprop相比本文算法成功率指标略高，但是在开销和延时指标上保持领先。另外，与SAW算法相比，在消息TTL大于20 min或节点缓存大于3 MB的情况下本文算法在投递成功率和开销指标上取得了一定优势。这是由于节点缓存或消息TTL设定较小时，消息很可能还没有遇到合适的中继节点就因节点没有存储空间或TTL到期而被删除，导致本文算法的节点转发机制未起作用。随着节点缓存或消息TTL的增加，消息在节点缓存中的停留时间变长，转发机制发挥作用使本文算法在成功率和开销上体现出了一定优势。

图8 在不同TTL下对应的消息平均投递延时对比Fig.8 Comparison of message average delivery delay under different TTL

5 结语

本文针对机会网络中消息中继选择问题，从节点相遇概率计算时效性和消息重复扩散的角度进行分析，根据节点移动偏离标和遇概率时效指标，设计了基于转发效用的消息副本转发算法。仿真实验结果表明：本文提出的消息转发算法通过合理选择中继节点，提高了消息的转发效率，相比Epidemic、ProPHET、Maxprop、SAW算法，综合考虑投递成功率、开销和延时指标，本文算法表现出了更好的性能。