带有相遇预测的自适应路由机制

吴大鹏，杨正川，刘乔寿，王汝言

(重庆邮电大学宽带泛在接入技术研究所，重庆400065)

0 引言

机会网络［1］的拓扑结构具有极强的动态性，源节点和目的节点间不存在完整的端到端路径，链路频繁中断特性，因此，消息传输过程的延时较高。为了充分利用节点运动过程与其他节点相遇的机会，机会网络以“存储、携带、转发”的方式来进行消息的传递。

可见，路由机制是机会网络的关键技术之一。针对机会网络的特性，研究人员提出了相应的路由机制。按照是否对消息进行复制，可以把现有的路由算法分为单副本路由和多副本路由。单副本路由协议中，节点将消息副本转发给另一个节点后，本身将不再保存该消息，即每个消息在网络中始终都只有一个副本。单副本路由机制能够有效地降低消息传输过程所产生的开销，但通常投递率都不高，延时也比较大。相比之下，通过多个副本在网络中的泛洪，多副本路由协议有效地提高了网络中消息投递成功的概率。

Epidemic［2］是一种消息副本数不受限制的多副本路由协议。节点将自身所携带的消息复制并传递给与之相遇的所有节点，通过无限制的泛洪以达到最大化投递成功率和最小化投递延时的目的，但网络中存在大量的冗余副本，造成严重的网络拥塞和资源竞争。Prophet［3］是一种受限的泛洪路由算法。节点首先估计到达目的节点的传递概率，并利用概率传递性来为消息选择相应的中继节点。

喷洒等待(spray and wait，SnW)路由机制［4］预先计算并限定了网络中消息副本的数量，只进行固定数量的副本传输，有效地减少了因消息过度复制所造成的资源浪费和竞争，该算法分为喷洒阶段和等待阶段。在喷洒阶段，源节点产生L个消息副本，当拥有n(n＞1)个消息副本的节点A与节点B相遇时，会将一个(source spray and wait)或者一半(binary spray and wait)消息副本传递给节点B。当n=1时，进入等待阶段，该阶段节点会一直携带该消息副本直到遇到目标节点。

显然，最佳中继节点的选择是设计高效机会网络路由协议的关键问题。喷洒等待路由在选择中继节点时，并未考虑相遇节点之间的差异，具有一定的盲目性。针对这个方面的问题，本文提出了一种带有相遇预测的自适应路由机制(adaptive routing mechanism with encounter prediction，EP－ARM)，通过动态地感知网络中其他节点的状态信息，节点实现自适应的消息转发决策，以达到合理的选择中继节点并提高网络资源利用率的目的。

1 带有相遇预测的自适应路由机制

1.1 转发策略分析

研究表明，消息的副本数越多，其被成功投递的概率就越大［5］。多副本路由机制的本质是对消息进行多次复制，以使得多个副本能够通过不同路径进行转发，从而提高消息的投递成功率。当消息的副本数有限时，路由协议的性能取决于消息副本的转发策略的合理性。

SnW中提出的源端喷洒(source spray)和二元喷洒(binary spray)两种喷洒方案都没有考虑到不同节点间相遇概率的差别，因此在消息转发决策的时候有盲目性。QoN－BSW［6］根据相遇节点的个数来计算节点质量(quality of node，QoN)，并根据QoN的差异进行转发决策;DHN－SaW［7］根据相遇节点的历史状态来决定转发的副本数。QoN－BSW和DHNSaW虽然考虑了本地节点的转发能力，却没有将相遇节点进行区分。DPER［8］将网络简化为只有两跳的虚拟网络，根据与目标节点的相遇概率的差异以选择中继节点，但与目标节点的相遇概率并不能准确地反映节点的转发能力。

在拓扑结构多变的机会网络中，如果不能充分利用节点的特性，其转发决策可能并不合理。为了准确地量化节点的转发能力，EP－ARM综合考虑了节点与目标节点的相遇概率以及与历史相遇节点的相遇概率，通过动态地感知网络中节点的信息，自适应地选择转发能力高的节点作为中继节点。

EP－ARM主要包含两个过程:网络状态感知和消息转发决策。与多数路由协议类似，本文所提出的路由策略中，当两个节点相遇之后，需要交换消息概要向量以及本地所收集的相关信息。然后，节点通过交换所得的信息进行消息转发决策。

1.2 网络状态感知

机会网络中的节点按照一定的规律进行运动，节点运动过程中将记录与其他节点的相遇信息，进而根据历史数据预测节点间的相遇概率;同时，相应的预测结果需要随着节点间的每一次相遇进行更新。显然，若两个节点相遇频繁，则表明它们的相遇概率就高。当任意节点A与节点B相遇后，相应的相遇概率按照(1)式进行更新。

(1)式中:P(a，b)表示节点A与节点B的相遇概率;P(a，b)old表示更新之前节点A与节点B的相遇概率;Pinit表示初始概率。

相遇概率会随着时间的变化而更新，若节点A和节点B在较长时间内没有再次相遇，则表明两者之间的相遇概率在随时间衰减，其更新过程如(2)式所示。

(2)式中:γ∈(0，1)是衰减系数;k表示自从上一次相遇到现在所经历的时间单位。

如果节点与其他节点的相遇越频繁，则该节点转发消息的机会就越多，也就是该节点的转发能力越强。为了量化节点的转发能力，本文定义并记录节点活跃度E(a，b)，其计算方式如(3)式所示。

(3)式中，E(a，b)表示任意节点A中所记录的节点B的活跃度，其值越大，则节点B就越活跃，与其他节点的相遇概率就越高。在记录节点活跃度E(a，b)的同时，需同时标记它的记录时间t(a，b)，并与其他节点进行比较，以更新节点活跃度和记录时间。

机会网络的拓扑结构具有较强的时变性，节点中所保存的信息不可能实时地反映当前网络状态。按照机会网络中消息转发过程基本原理，节点相遇之后需要交换各自的本地信息，以动态地感知网络中其他节点的信息。当节点A和节点B进入通信范围后，节点A首先根据(1)式和(2)式更新本地保存的相遇概率信息，并根据(3)式更新节点活跃度E(a，b)。然后，节点A与节点B比较节点性能的记录时间，若 t(a，i)＜ t(b，i)，则 E(a，i)=E(b，i)。

1.3 消息转发决策

在消息转发决策阶段，节点根据网络状态感知阶段所得到的信息，利用相遇概率和节点活跃度的差异进行消息的转发决策。本文所提出的机制中，为了减少消息低效率洪泛，节点有限制性地将消息转发给活跃度高于自身的节点。

对于任意节点A，定义Qa为节点A的转发能力。该参数综合考虑了节点与目标节点的相遇概率，以及历史相遇节点的相遇概率和节点活跃度，其计算如(4)式所示。

(4)式中:C为所有节点的集合;α为权重系数。

对于节点A中目标节点为iD的消息，若当前副本数为La，则转发给任意相遇节点B的副本数Lb如(5)式所示。

转发能力强的节点将被分配更多的消息副本，以获得更多的转发机会。

带有相遇预测的自适应路由机制的伪代码如下所示。

当任意节点A和节点B建立连接后，首先根据(1)式和(2)式更新相遇概率，并根据(3)式更新节点活跃度;然后，相互交换并更新消息概要向量以及本地所感知的相关网络状态信息;最后，若节点A中的消息副本数La＞1，则根据(4)式和(5)式计算得到的副本数进行转发决策，确定是否将消息转发给节点B以及转发的副本数;若La=1，则进入等待阶段，直至与目的节点相遇。

2 性能分析

本文利用机会网络环境(opportunistic network environment，ONE)［9］对所提出的机制进行验证。为了充分体现所提出机制具有较强的实际应用价值，本文选取Infocom06数据集中的实测数据作为节点运动轨迹。

2.1 数据模型及参数

相关参数设置如表1所示。

表1 仿真参数表Tab.1 Parameter settings

仿真中关于路由决策计算的相关参数分别设置为 Pinit=0.75;β =0.25;γ =0.98;α =0.85。

2.2 结果分析

为了全面验证EP－ARM算法的性能，本文使用了3个性能评估参数:投递延时、投递率和投递开销。投递延时表示从消息产生到最终被投递到目标节点所需的平均时间;投递率表示最终投递成功的消息占产生消息总数的比例;投递开销则定义为未成功投递的消息副本总数和成功投递的消息数量的比值。对于消息副本数不同的情况下，本文对提出的路由协议上述3个方面的性能进行了比较和分析，结果分别如图1－图3所示。

图1 投递延时Fig.1 Delivery latency

图2 投递率Fig.2 Delivery probability

图3 投递开销Fig.3 Delivery overhead

由图1可以看出，本文所提出的路由投递延时明显低于SnW路由。由于EP－ARM在中继节点的选择上更加合理，这样可以使消息迅速地被转发到目标节点。相比于SnW路由的盲目洪泛，选择合适的中继节点可以有效地减少消息的低收益洪泛。仿真结果表明，与SnW相比较，所提出的路由策略平均延迟降低了20%左右。

图2比较了所提出的路由协议与SnW路由协议的消息投递率。由图2可知，EP－ARM的投递率要高于SnW。因为前者综合考虑了节点的性能，使消息的洪泛更具目的性，而后者则因为洪泛的盲目性，使得网络资源的利用率降低，这一点在副本数较少时更为明显。

由图3可知，EP－ARM与SnW相比投递开销几乎没有变化。这是因为EP－ARM并没有增加消息副本的总数量，二者在网络中洪泛的副本数相同，所以在投递开销上几乎一致。

3 总结

针对SnW选择中继节点时的盲目性，本文利用相节点性能的差异，自适应地选择合理的中继节点，提高了网络资源的利用率。仿真结果表明，在不明显改变投递开销的情况下，本文提出的路由投递延时更低，投递率更高。

［1］ELIZABETH M，MADS H.The challenges of disconnected delay－tolerant MANETs ［J］.Ad Hoc Networks，2010，8(2):241－250.

［2］AMIN V，DAVID B.Epidemic Routing for Partially Connected Ad Hoc Networks［R］.Durham NC，USA:Duke University，2000.

［3］LINDGREN A，DORIA A，SCHELEN O.Probabilistic routing in intermittently connected networks［J］.ACM SIGMOBILE Mobile Computing and Communications Review，2003，7(3):19－20.

［4］SPYROPOULOS T，PSOUNIS K，RAGHAVENDRA C.Spray and wait:Efficient routing in intermittently connected mobile networks［C］//Kevin.Proceedings of the 2005 ACM SIGCOMM workshop on Delay－tolerant networking.New York:ACM，2005:252－259.

［5］ZHANG Z S.Routing in intermittently connected mobile ad hoc networks and delay tolerant networks Overview and challenges ［J］.IEEE Communications Surveys Tutorials，2006，8(1):24－37.

［6］WANG G，WANG B，GAO Y.Dynamic Spray and Wait Routing algorithm with Quality of Node in Delay Tolerant Network［C］//International Conference on Communications and Mobile Computing.China:CMC，2010:452－456.

［7］PRUEKSASRIV， INTANAGONWIWATC， ROJVIBOONCHAI K.DNH－SaW:The Different Neighbor－History Spray and Wait Routing Scheme for Delay Tolerant Networks［C］//International Symposium on Intelligent Signal Processing and Communications Systems.Thailand:ISPACS，2011:1－5.

［8］彭敏，洪佩琳，薛开平，等.基于投递概率预测的DTN高效路由［J］. 计算机学报，2011，34(1):174－181.PENG M，HONG Peilin，XUE Kaiping，et al.Delivery probability prediction based efficient routing in DTN［J］.Chinese Journal of Computers，2011，34(1):174－181.

［9］KERÄNEN A，OTT J，KÄRKKÄINEN T.The ONE simulator for DTN protocol evaluation［C］//ICST.The 2nd International Conference on Simulation Tools and Techniques.Italy:ACM，2009:1－10.