考虑相遇强度的约束扩散路由算法*

张毅夫 刘 静 余海健 朱子奇

（1.武汉科技大学计算机科学与技术学院 武汉 430065）

（2.武汉科技大学大数据科学与工程研究院 武汉 430065）

（3.武汉科技大学智能信息处理与实时工业系统湖北省重点实验室 武汉 430065）

1 引言

机会网络［1］同时具备间歇式联通网络［2］和延时容忍网络［3］的特征，采用“存储—携带—转发”的模式进行通信，是一种不需要源节点和目的节点之间存在完成链路，利用节点移动带来的相遇机会实现通信的自组织网络［4］。如图1 所示，消息在源节点1 处产生，同一阴影内的节点表明它们可以建立通信。在t1时刻，消息由源节点1转发给节点3；紧接着，由于节点的移动，在t2 时刻，消息携带节点3 与其节点4成功建立通信，并将消息交付给节点4；最终，在t3时刻，消息被成功的交付给目的节点7。

图1 机会网络示意图

机会网络非常契合拓扑变化的场景，具有极大的实用价值，目前已衍生出许多具体应用，如手持设备组网PSN（Pocket Switched Network）［5］，车载网络CarTel［6］，野生动物追踪机会网络ZebraNet［7］，偏远地区网络传输DakNet［8］等。同时，机会网络受限于不稳定的拓扑链接、能量和储存受限等原因，仍存在消息投递率低、网络负载高和平均时延高这些缺点。提高机会网络的消息转发效率是机会网络中的重点研究问题。

本文基于节点的历史相遇信息提出了EICD算法。主要贡献如下：

1）提出了相遇强度和其计算公式，相遇强度把时间作为计算的重要依据，能够更准确地评估两个节点相遇的可能性。

2）针对多拷贝路由中存在的大量消息副本和已投递消息的冗余副本，利用约束扩散策略和去冗余策略来控制网络中消息副本数量并及时删除网络中存在的冗余副本，降低网络负载。

2 相关工作

机会网络中，根据存在的消息副本数量将路由算法分为两类［9］：单拷贝路由算法和多拷贝路由算法。

最典型的单拷贝路由算法当属Direct Delievery 算法［10］，该算法从消息在源节点生成直到投递到目的节点，不再生成任何消息副本，也不借助任何中继节点转发，源节点在移动过程中只有遇到目的节点时才将消息转发给目的节点。该算法具备与单拷贝路由算法同样的特性，可以大幅度减少网络中的资源浪费和网络开销，但存在消息投递率低、消息转发时延高等缺陷。

在多拷贝算法中，Epidemic算法［11］是其中的典型。该算法的主要思想是当两个节点在移动中相遇并建立通信时，节点会将自身携带且对方不存在的消息复制给对方。该算法会在网络中产生大量的副本，从而造成极大的网络资源浪费。由于节点缓存空间与通信时间有限，大面积的丢包和无用的计算致使该算法存在投递率低、网络负载高等缺点。

Spray And Wait 算法［12］将路由分为“Spray”和“Wait”两个阶段，在“Spray”阶段，先对消息进行一定数量的复制，当两个节点相遇时，节点转发一半数量的消息副本给相遇节点，自身保留另一半，直至节点中仅剩一份消息副本。之后进入“Wait”阶段，即消息携带节点只在遇到目的节点时将消息转发给目的节点。该算法将Direct Delievery 算法和Epidemic算法进行结合，既能保证一定的消息投递率又能适当地降低网络负载和转发时延。

Prophet 算法［13］是一种考虑相遇概率的路由算法。该算法通过节点间的历史相遇信息来预测未来两节点的相遇概率。当两个节点相遇时，比较两个节点与消息目的节点相遇的概率，依此来决定是否复制和转发该消息。

MaxProp 算法［14］充分考虑节点的缓存资源，根据节点相遇概率和消息跳数（消息通过中继节点转发的次数）来决定何时丢弃缓存中的消息。跳数越大，则消息的优先级越低；跳数越小，则消息的优先级越高。

在多拷贝路由算法中，为提高消息投递率，将会生成大量的消息副本。在消息传递过程中，大量的消息副本和已投递消息的冗余副本不仅占用了节点的缓存空间，还浪费了大量的计算时间，这在一定程度上降低了消息投递率、加大了网络负载和转发时延。鉴于此，本文利用约束扩散策略和去冗余策略来控制网络中消息副本数量并及时删除网络中存在的冗余副本，降低网络负载。同时，提出考虑相遇强度的精准传递策略来帮助消息更准确地找到目的节点。

3 EICD算法

EICD 算法通过控制网络中的副本数量和删除网络中冗余的消息副本两种方式来降低网络负载和转发时延，同时充分考虑时间因素来评估节点间下次相遇的可能性。该算法将路由过程分为三个阶段，分别为约束扩散阶段、考虑相遇强度的精准传递阶段和去冗余阶段。

3.1 约束扩散阶段

静态网络常用度中心性、相似中心性和中介中心性［15～16］来衡量节点在网络中的中心度。由于动态网络和静态网络的网络拓扑本质不同，这些指标无法应用于机会网络。本文借鉴静态网络的度中心性等概念，提出节点活跃度Ac和其计算公式。Aci为节点Ni的活跃度，计算如式（1）：其中，a(Ni,Nj)代表节点Ni与节点Nj的连接情况。若建立过连接，则a(Ni,Nj)=1；否则a(Ni,Nj)=0。ω(Ni,Nj) 代表节点Ni与节点Nj建立连接的次数。一般来说，活跃度高的节点能和更多的节点建立通信。

约束扩散阶段如算法1 所示。在约束扩散阶段，利用限制数量的消息复制策略去控制网络中消息的副本数量，进而提高整个网络的转发效率。为避免在扩散阶段浪费大量的网络资源，故限制消息自源节点产生后，只有跳数为0 的消息才被允许去寻找活跃度更高的节点。消息跳数即消息由源节点产生到成功投递到目的节点的过程中，经过中继节点的次数。

算法1 约束扩散策略

输入 源节点Ni，相遇节点Nj，节点活跃度Ac，源节点Ni携带的消息m。

输出 源节点Ni中消息是否转发给相遇节点Nj。

1）对源节点Ni中产生的消息m生民共s个副一

2）FOR源节点Ni的所有相遇节点NjDO

3）FOR源节点Ni中的所有消息m DO

4）IF相遇节点Ni是消息m的目的节点THEN

5）将消息m传递给相遇节点Nj

6）ELSE IF相遇节点Nj不存在消息m

7）&&Acj＞Aci

8）&&消息m的跳数为0 THEN

9）将消息m传递给相遇节点Nj

10）END IF

11）END IF

12）END FOR

13）END FOR

3.2 精准传递阶段

为了记录节点的历史相遇信息，本文针对网络中的节点建立了一张TEt 表，即。TEt 表中，表示节点Ni与节点Nj的第k 次相遇的时间，表示节点Ni与节点Nj第k+1次相遇强度，表示节点Ni与节点Nj第k 次通信持续的时间。相遇强度E是一个评估指标，代表此节点在未来一段时间遇到其它某节点的机会。相遇强度越大则相遇可能性越高，反之亦然。相遇强度是节点选择中继节点的一项重要依据。本文充分考虑时间因素，将相遇强度的计算分为激励和衰退两部分。

用tit表示两节点此次相遇距离上次相遇已经过的时间，计算如式（2）：

用tst表示网络中相遇的平均间隔时间，计算如式（3）：

用max_E表示网络中历史最大相遇强度，计算如式（4）。其中，K 为Ni和Nj的最大相遇次数；N为网络中所有节点的集合。

相遇强度的激励策略部分计算如式（5）。Eold表示更新前的相遇强度；max_E为网络中历史最大相遇强度；e为激励系数，若两节点该时间间隔内相遇，则在Eold的基础上先提高e*Eold，再进行额外的激励增加。

当相遇间隔时间tit∈(0,tst]时，给予相遇强度更大的激励。此时两个节点之间再次建立通信时间距离上次通信结束时间较短，短时间内两个节点多次通信意味着在未来一段时间内，它们很可能再次建立通信。两节点间的每次相遇都会对Eold有激励作用。当tit∈(tst,∞)时，两节点间的相遇间隔时间较长，将给予相遇强度更少的激励。伴随相遇间隔时间tit越来越长，Eenc会越来越趋近于Eold，却不会低于它。鉴于此，本文设立相遇强度衰退机制。即如果在较长时间中两个节点没有相遇，就通过衰退策略不断地降低相遇强度，衰退策略部分计算如式（6）。

其中γ表示衰退系数。当两个节点在衰退期相遇后，会在衰退后的相遇强度基础上再进行激励策略。

算法2 精准传递策略

输入 节点Ni，相遇节点Nj，源节点Ni携带的消息m，消息的目的节点Nd。

输出 节点Ni中消息是否转发给相遇节点Ni。

1）FOR源节点Ni的所有相遇节点NiDO

2）根据公式（5）和（6）更新节点Ni与Nj之间的相遇强度

3）FOR源节点Ni中的所有消息m DO

4）令Ei，d=Ni与Nj在此时刻的相遇强度（不更新TEt 发表）

5）令Ei，d=Nj与Nd在此时刻的相遇强度（不更新TEt 发表）

6）IF Ei，d＜Ei，dTHEN

7）将消息m传递给相遇节点Nj

8）END IF

9）END FOR

10）END FOR

精准传递算法如算法2 所示。当两个节点相遇后，首先根据式（5）和式（6）更新两个节点的TEt表。然后，根据式（6）分别计算此时刻两个节点和目的节点的相遇强度，由于两个节点并未与目的节点相遇，所以此时不需要更新两个节点与目的节点之间的TEt 表。最后，根据此时刻两个节点与目的节点的相遇强度大小来决定是否转发消息。

3.3 去冗余阶段

为了提高投递效率，在消息产生时，往往会对消息m 进行一定数量的复制。在消息m 成功投递到目的节点后，网络中剩余的消息副本仍然存在并占用网络资源，它们不仅会占用缓存空间，而且还会增加计算量，所以需要及时地删除网络中冗余的消息副本。本文设计了一种去冗余策略来删除成功投递的消息在网络中存在的冗余副本。

算法3 去冗余策略

输入 节点Ni，相遇节点Nj，节点活跃度Ac，节点交付记录DR、节点携带消息m、节点活跃度Ac。

输出 去冗余后节点Ni、Nj的状态。

1）当节点Ni和节点Nj建立通信时

2）DRnew=DRi∪DRj

3）根据DRnew删除节点Ni中已交付的消息

4）根据DRnew删除节点Nj中已交付的消息

5）IF Aci＞AcjTHEN

6）DRi=DRnew

7）清空节点Nj的交付记录DRi

8）END IF

9）IF Aci＜AcjTHEN

10）DRj=DRnew

11）清空节点Ni的交付记录DRi

12）END IF

设DR（Delivery Record）为各节点的消息交付记录，用来记录本节点成功交付的消息。当两节点处于通信状态时，交换彼此的DR，得到一个新的DRnew，节点Ni、Nj根据DRnew删除节点中冗余的已交付消息副本；在删除冗余消息副本后，为避免节点的DR 占用过多的节点缓存资源，将会删除活跃度低的节点的DR，把活跃度高的节点的DR 更新为DRnew。去冗余算法如算法3所示。

4 仿真结果与分析

4.1 仿真环境

本文使用The ONE（The Opportunistic Network Environment simulator）仿真平台来进行仿真实验。在分别改变节点缓存空间、消息生存周期以及节点数量对算法进行多次对比仿真实验，实验仿真参数如表1所示。

表1 仿真环境参数设置

4.2 实验结果及分析

为了验证本文所提出的EICD 算法的有效性，将其与四个经典的路由算法Epidemic、Spray And Wait、Prophet 以及MaxProp 进行对比，并选用消息投递率、网络负载、平均转发时延［17～18］三个机会网络中重要的评价指标来评价算法的性能。

4.2.1 节点缓存空间对路由算法的影响

EICD 算法与其它经典算法在不同节点缓存空间下的性能比较如图2～图4 所示。设定网络中消息生存周期为150min，节点数量为240个。

图2 不同缓存空间下的消息投递率

图3 不同缓存空间下的网络负载

图4 不同缓存空间下的平均转发时延

实验结果表明，各算法的投递率和平均转发时延随着节点缓存空间的增加而上升，网络负载随着节点缓存空间的增加而降低。EICD 算法的投递率比MaxProp、Spray And Wait、Epidemic 和Prophet 等算法都有显著提高。在网络负载方面，EICD 算法强于MaxProp、Epidemic 和Prophet 算法，弱于Spray And Wait 算法。这是因为Spray And Wait 算法在“Wait”阶段只进行一次到目的节点的转发，从而节省了大量的网络资源。在平均转发时延上，伴随着缓存空间加大，平均转发时延的增加幅度逐渐减小。

4.2.2 消息生存周期对路由算法的影响

EICD 算法与其它经典算法在不同消息生存周期下的性能比较如图5～图7 所示。设定网络中节点缓存空间为10MB，节点数量为240个。

图5 不同消息生存周期下的消息投递率

图6 不同缓消息生存周期下的网络负载

图7 不同消息生存周期下的平均转发时延

随着节点消息生存周期的提高，算法投递率整体呈上升趋势，但是当消息生存周期过大时，算法的投递率会趋于平稳，甚至略有降低。这是因为消息生存周期过长，挤占了节点的缓存空间，使得节点没有缓存空间接受新消息。在平均转发时延上，消息生存周期过长将不会过早地丢弃该消息，这使得成功投递的消息投递所耗时长有所提升，从而提高了消息平均转发时延。

4.2.3 网络中节点数量对路由算法的影响

EICD 算法与其它经典算法在不同节点数量下的性能比较如图8～图10所示。设定网络中节点缓存空间为10MB，消息生存周期为150min。

图8 不同节点数量下的消息投递率

图9 不同节点数量下的网络负载

图10 不同节点数量下的平均转发时延

随着节点数量的增加，所有网络的整体性能普遍增高。伴随着节点数量的增加，各算法的投递率大体呈上升趋势，EICD 算法投递率高于其它算法。在网络负载上，除Spray And Wait 算法外的其它拳法上升趋势明显。在平均转发时延上，EICD算法明显优于其它算法。

5 结语

本文提出了一种考虑相遇强度的约束扩散路由算法。在消息产生节点对消息复制s 个副本，然后仅进行一次向活跃度高的节点的跳跃；接着当两个节点相遇时，根据提出的充分考虑时间因素的相遇强度计算策略来计算节点与消息目的节点在未来一段时间的相遇强度，并将消息转发给具有更高相遇强度的中继节点；在去冗余阶段，节点会交换彼此的消息交付记录并据此来删除已投递消息的冗余副本，降低网络负载。仿真实验表明，EICD 算法在节点缓存空间不同、消息生存周期不同和节点数量不同等情况下，均能够有效地提高消息投递率、降低网络负载和平均转发时延。