基于社会环境的一种优化Prophet延迟容忍网络路由算法

万 冰

（摩托罗拉系统（中国）有限公司 成都分公司，四川 成都 611731）

基于社会环境的一种优化Prophet延迟容忍网络路由算法

万 冰

（摩托罗拉系统（中国）有限公司 成都分公司，四川 成都 611731）

在移动智能终端普及的今天，延迟容忍网络作为数据的补充传输方案具有重要的意义。在社会环境中，节点移动规律具有明显周期性，Prophet路由算法在该类场景中效果较好。因此文章提出了一种基于加强传统概率的路由算法，其在工作日模型下对E Prophet算法进行了仿真实验。实验结果表明，所提出的E Prophet算法在该场景下优于传统的Prophet算法。

延迟容忍网络；社会环境；移动规律；路由算法

延迟容忍网络（（Delay Tolerant Network，DTN））又称为容断或容迟网络，由多个移动对象携带具备无线通信能力的传感器组成[1]。在延迟容忍网络中数据利用节点之间相遇的机会进行转发，因此这种“存储—携带—转发”的传输方式可以较少地依赖于基础设施，网络中的链接频繁中断[2]。因此从延迟容忍网络出现就广泛围绕挑战性环境中的应用讨论，如战场环境[3]、车辆交通环境[4]、水下场景[5]等。随着智能移动终端的普及，在城市区域中利用移动智能终端所构建的延迟容忍网络具有传输成本低、移动性支持好、对通信基础设施需求较低等优势。不同场景中节点的移动规律不一致，导致现有的延迟容忍网络路由算法不能在城市场景中发挥网络应有的性能[6]。

前期研究表面，社会环境中节点具有一定的周期移动规律性，所以基于概率预测的Prophet在社会环境中具有较好的表现[7]。

为了提升延迟容忍网络在城市环境中的性能表现，本文提出一种适用于社会环境的优化Prophet路由算法（Enhanced Prophet，E Prophet），E Prophet算法中的衰老因子符合城市环境中节点的相遇规律。本文利用工作日模型（Working Day Mode，WDM），建立了趋于真实社会环境节点的移动状态，并在多次实验的基础上，观察了随时间变化下两种算法在社会环境中的网络关键性能指标，并对结果进行了相关的分析。

1 Prophet路由算法简介

Prophet算法由A·Lindgren等[8]提出，其基本思想是在节点中加入冗余知识，以便记录节点之间的相遇概率。在Prophet算法中，每个节点都存在一个概率据测矩阵，依据所设计的策略进行概率预测值的更新。如节点a与节点b的相遇概率定义如式1所示。

其中P(a,b)old表示上一个状态的相遇概率，Pinit表示初始化概率。在算法中状态值P(a,b)s1与P(a,b)s2分别表示两个时间状态下节点之间概率预测值。状态S1，S2两个状态之间预测值变化函数，它基于算法中所设计的衰老因子γ的设计。当节点a与节点b分开后，由于衰老因子的存在，导致两个节点之间的概率预测值持续减少。其衰减计算函数如式2所示。

式中γk因子是一个幂指数函数，其中0＜γ＜1，k为与时间相关整数。由于幂指数的存在，随着时间的增加节点之间概率预测值会持续降低。通过这样的设计，相互接触较为频繁的节点，其概率预测值会维持一个较为高的预测值。在社会环境中，由于节点之间的存在的社会属性，因此可以用社交图（Social Graph）（见图1）表现节点之间的接触或社交情况[9]。

图1 社会环境中节点社交

基于图1社会环境中的社交图可以发现，在网络中节点之间的接触规律受制于节点的社交圈。而在社会网络中社交圈的存在，也表明了节点与节点之间的接触概率并不服从均匀分布。由此，Prophet算法中的概率预测方式，在社会环境的延迟容忍网络中符合节点的相遇规则，因此也可以得到较好的表现。

2 Prophet算法在社会环境下延迟容忍网络中的问题

基于概率预测的Prophet算法从提出到现在并没有针对的场景，但是其概率预测的方式，较为适应一些具有相遇规律的场景，因此在基于社会网络的延迟容忍网络中，得到了众多学者的关注[10]。在社会环境中，具有通信能力的移动节点往往由移动智能终端与携带智能终端的车辆等组成，因此移动节点同样具有社会属性。在社会环境中，白天人们活动，具有一定的目的性与规律性，如上班、逛街等。晚上人们在家休息活动范围局限在一个较小的范围当中，甚至不移动。这也就构成了社会环境中节点移动的基本规律。通过Infocom数据集（41节点）在72小时采集的相遇数据如图2所示。

图2 Infocom数据集在72小时的相遇规律

基于图1可以看到，节点在不同的时间段中相遇次数具有较大的差别。节点相遇具有一定的周期性。在一个周期中，节点具有高相遇次数期间与低相遇次数期间。低相遇次数期间，网络中节点总体的相遇次数趋近于零，这也是人们晚上休息所导致的。在高相遇次数期间，节点相遇次数出现了较大的波动，可以理解为在社会环境中人们的早高峰与晚高峰。从周期上面看，其总体的相遇规律可以由式3所示。

fn(t)=f(t+NT) （3）

其中，fn(t)表示在当前时间网络中节点相遇次数，N为整数，T为12小时常量。可以看到，在低相遇期间，时间持续较长为12小时，因此在Prophet路由算法中，由于如式2中衰老因此的存在，预测矩阵中节点之间的预测概率值，会在这个低相遇次数周期中由于节点间相遇次数的减少而持续降低。当节点相遇次数再次进入到高相遇周期时，节点之间的预测概率值都处于一个较低的水平，节点之间的预测概率需要一个重新收敛的过程。因此，Prophet算法在社会场景中，无法较好地适应这种节点的相遇周期，影响了算法的性能发挥。

3 一种优化的E Prophet路由算法

基于Prophet在社会环境中无法较好适应低相遇次数周期与高次数相遇周期的问题，文章提出了一种优化的Prophet路由算法。重新设计了衰老因子的策略方式。同样路由算法基于节点之间相遇的情况，其算法的描述如下。

步骤1：网络中全体节点建立相遇概率矩阵E，以存储全体网络节点的预测概率值。

步骤2：基于式1进行相遇概率连续状态的更新。

步骤3：基于式4进行相遇概率衰减。

式中，T1表示在低相遇次数周期中时间，反之T2表示在高相遇周期中时间。衰老方式计算在不同节点所处时间段中存在区别。其中K1与K2如式5—6所示。

式中tnow表示网络运行的当前时间，tT为上一更新时间，β为常量。

其中定义时间周期判断(tnow/Thour)/δ为真时，为T2时间区间，反之亦然。

4 仿真环境与实验结果

由于真实数据集的节点过少，或部分真实数据集节点移动范围过小，因此这里选择由F.EKman等提出的工作日模型（Working Day Movement Model，WDM）[11]。

其仿真场景中节点分组如表1所示。

表1 节点分组类型

仿真场景中选择了其关键仿真参数如表2所示。

表2 关键仿真参数

设置与社交环境较为近似的仿真场景后，对延迟容忍网络中关键指标如网络投递成功率、平均投递延迟与网络负载比3个关键指标与传统Prophet指标进行对比分析如图3—5所示，以观察优化的Prophet算法与Prophet算法性能。

图3 两种算法的网络投递成功率

图4 两种算法的平均投递延迟

图5 两种算法的网络负载比

通过两种算法在3种延迟容忍网络的关键指标中对比发现，所提出的E Prophet路由算法在社会环境中明显优于原始的Prophet算法。由于WDM模型中节点相遇分布在时间维度的剧烈波动，也导致了3种指标随着时间出现了较为剧烈的波动。

5 结语

随着智慧城市的发展，社会环境中对数据的需求具有多种多样的解决方案，而延迟容忍网络作为数据传输的一种解决方案具有移动性支持强、成本低、系统抗灾性强的特点。文章提出的E Prophet算法一定程度上提升了Prophet算法在社会环境中延迟容忍网络的系统性能，有利于提高基于延迟容忍网络的应用系统的性能。

[1]GAO L, YU S, LUAN T H, et al. Routing Protocols in Delay Tolerant Networks[M].German：Springer International Publishing, 2015.

[2]MAYER C P, WALDHORST O P. Offloading Infrastructure Using Delay Tolerant Networks and Assurance of Delivery[J]. Jochen Furthmüller, 2011（1）：1-7.

[3]DINI G, DUCA A L. Towards a reputation-based routing protocol to contrast blackholes in a delay tolerant network[J]. Ad Hoc Networks, 2012（7）：1167-1178.

[4]UCHIDA N, ITO K, HIRAKAWA G, et al. Vehicle-to-Vehicle Delay Tolerant Networks with Area of Interest for Road Surveillance System[C]. Poland：International Conference on Broadband and Wireless Computing, Communication and Applications[A] .Computer Society, 2015：466-471.

[5]刘灿.容延容断网络中基于负载均衡的路由算法的研究[D].长沙：国防科学技术大学，2011.

[6]李文藻，林锋.节点缓冲区大小对城市部署的DTN网络的影响分析[J].无线互联科技，2014（10）：117-119.

[7]MOREIRA W，FERREIRA R，CIRQUEIRA D，et al. SocialDTN：a DTN implementation for digital and social inclusion[C].ACM MOBICOM Workshop on Lowest Cost Denominator NETWORKING for Universal Access. ACM，2013：25-28.

[8]LINDGREN A, DORIA A, SCHELÉN O. Probabilistic Routing in Intermittently Connected Networks[J]. Acm Sigmobile Mobile Computing & Communications Review, 2004（3）：19-20.

[9]BONNEAU J, ANDERSON J, ANDERSON R, et al. Eight friends are enough：social graph approximation via public listings[J]. ACM EUROSYS Workshop on Social Network Systems, 2009（3）：13-18.

[10]SCHURGOT M R, COMANICIU C, JAFFRES R K. Beyond traditional DTN routing: social networks for opportunisticcommunication[J]. Communications Magazine, 2012（7）：155- 162.

[11]EMAN F, KER, NEN A, et al.Working day movement model[C].ACM Wi-Fi Multimedia, 2008：33-40.

An optimized Prophet delay tolerant network routing algorithm based on social environment

Wan Bing
（Chengdu Branch of Motorola Systems（China）Co., Ltd., Chengdu 611731, China）

With the popularity of the mobile terminal today, as a supplement to the data transmission project, delay tolerant network is of great significance. In the social environment, node movement law has obvious periodic node movement, prophet routing algorithm has better effect in the scene. Therefore, this paper proposes a kind of routing algorithm based on .strengthening traditional probability. The E Prophet algorithm is simulated under the mode during the working day.The simulation results show that the proposed E Prophet algorithm is superior to the traditional Prophet algorithm in this scenario.

delay tolerant network; social environment; movement law; routing algorithm

四川省科技厅软科学项目；项目编号：2014ZR0146。四川省教育厅重点项目；项目编号：16ZA0218。

万冰（1978— ），女，四川成都，硕士；研究方向：计算机通信与网络研究设计。