节点关系强度感知的延迟容忍网络路由机制

胡 敏，王言通，黄春妮

(重庆邮电大学 通信与信息工程学院，重庆 400065)

0 引 言

目前国内外研究机构在延迟容忍网络(delay tolerant network，DTN)路由机制方面的研究中，研究热点是利用节点关系(如社会关系、相遇概率)确定消息转发节点[1,2]，完成消息传输过程。Pan等[3]提出的Bubble Rap路由，依据节点的移动信息对节点划分社区，同时利用网络拓扑结构和节点属性计算节点活跃度并排序，根据节点排名选择转发消息节点；Abdelkader等[4]利用社会网络中“小世界”特性制定路由策略，依据节点相似性和中心性确定转发节点；吴大鹏等[5]提出根据节点社会属性感知的数据转发策略，利用节点连接持续时间评估节点关系。此外，研究人员发现利用节点的历史信息可以对节点的运动进行预测。王恩等[6]利用节点历史信息预测节点相遇概率并根据预测值确定转发节点；Peng等[7]提出的基于投递概率预测的高效路由(delivery probability prediction based on efficient routing，DPER)，根据节点投递概率预测值选择节点并根据预测值分配消息副本。在上述研究的节点关系评估中，忽略了节点间关系强度受其连接节点的影响，使所得结果与节点在网络中的实际关系强度不相吻合，从而错误评估了节点转发能力，降低网络传输性能。

针对上述问题，本文提出节点关系强度感知的延迟容忍网络路由机制(node relationship magnanimity aesthesis routing，NMAR)，该机制利用相遇节点信息衡量节点关系强度变化，并依据节点连接状态信息估计节点相遇概率，并结合节点关系预测节点转发能力，根据节点关系强度和转发能力值选择转发节点，提高消息转发效率，提高网络性能。

1 节点关系强度感知

节点关系通常考虑节点间的相遇时间或相遇频率[8]，节点关系强度能够反映节点间连接的紧密情况。但节点关系强度并不能仅考虑两节点的连接情况，其它节点也会对两节点关系产生影响。

1.1 节点关系

网络中的节点选择任意方向移动，并依靠与其它节点相遇建立的连接转发消息。节点运动场景如图1所示。

节点运动使节点间关系产生变化，由此节点间关系变化取决于节点运动情况。移动过程中相遇节点信息反映节点运动情况，利用相遇节点数量的变化分析节点运动情况，评估节点间关系的变化。

图1 节点运动场景

相遇节点信息是记录存储该节点移动过程中相遇节点的信息，包括节点ID、相遇次数、开始时间、结束时间等。本文利用相遇节点的数量衡量节点关系强度，利用两节点共同相遇节点(共遇节点)的数量变化描述节点关系强度变化，即共遇节点数目增加，则节点关系强度增加；反之，节点关系强度减弱。节点关系强度变化如图2所示。两节点间关系越强，节点间转发消息的能力越强，消息的传输效率越高。

图2 网络中节点关系变化

1.2 节点关系强度感知

网络G由n个节点构成，N为节点集合。节点a与节点b为网络中任意两个节点，节点a的相遇节点集合记为表示为M(a)={ni|ni∈N},ni为网络中节点。节点a和节点b的共遇节点集合记为

CM(a,b)={ni|ni∈M(a),ni∈M(b),ni∈N}

(1)

定义1 共遇节点变化度

共遇节点变化度指节点a与节点b的相邻两个时间周期内共遇节点数目的变化值与非共遇节点数目的比值，记为

(2)

式中：CM(a,b)i表示节点a与节点b在第i个周期内的共遇节点集，CM(a,b)i-1表示节点a与节点b在第i-1个周期内的共遇节点集。

共遇节点变化度反映节点关系强度变化，当共遇节点变化度大于零，共遇节点数目增多，节点关系强度增加；反之，节点关系强度减弱。同时共遇节点变化度的绝对值表征节点间关系强度的变化程度，绝对值越大，节点关系强度变化越剧烈。

定义2 节点连接度

节点连接度是指节点a与节点b的共遇节点数目与两节点所有相遇节点数目的比值，记

(3)

式中：CM(a,b)i表示节点a与节点b在第i个周期内的共遇节点集，M(a)i,M(b)i表示为节点a与节点b在第i个周期内的相遇节点集。

节点连接度表征节点间关系强度，连接度越大，节点间关系强度越高。

定义3 相遇节点变化度

相遇节点变化度是指节点a在两个相邻的时间周期内相遇节点数目变化值与相遇节点数目的比值，记为

(4)

式中：M(a)i为节点a在第i个时间周期内的相遇节点集合，M(a)i-1为节点a在第i-1个时间周期内的相遇节点集合。

相遇节点变化度反映节点因移动造成相遇节点的变化程度，体现节点移动能力大小，变化度值越大，移动能力越强。

节点a，d的关系强度函数记为

Re(a,d)=μCon(a,d)+εDis(a,d)+Var(a)

(5)

式中：μ、ε和为权重因子，μ+ε+=1，μ=0.5，ε=0.3，=0.2。

1.3 节点的转发能力

节点关系强度反映节点间连接路径的数量。消息转发效率不仅与路径数目多少相关，还与各个路径的节点转发能力有关。节点转发能力包括相遇转发能力和邻接转发能力，相遇转发能力是指与目的节点相遇完成消息转发的能力，邻接转发能力是指由非目的节点完成消息转发的能力。转发能力用相遇概率描述，而相遇概率由节点间连接状态预测得到。

网络中任意两个节点之间的连接状态由连通和断开交替变化，并且两节点a、b在将来tk+1时刻的状态(连通/断开)只与当前时刻tk的状态有关而与过去其它时刻无关，如图3所示。因此，节点连接状态的变化过程可视作连续时间的马尔可夫链。

图3 节点连接状态变化过程

图3中λ、μ分别表示节点间的连接状态由断开转变为连通、由连通转变为断开的概率，设连接的持续时间与连接的间隔时间分别用ct、ict来表示，则λ=∑ct/∑t,μ=∑ict/∑t。

该马尔可夫链是一个齐次马尔可夫过程，其状态转移概率为

(6)

即状态转移矩阵为

(7)

节点a、b间连接状态由断开到断开的转移速率为

(8)

同理，连接状态由连通到连通的转移速率为

(9)

即上述演化过程的Q矩阵为

(10)

由柯尔莫哥洛夫向前方程可以得到

(11)

根据求解方程得到，节点a、b间连接状态由断开到连接的概率为

(12)

则节点a、b相遇概率值为

(13)

式中：ict′为平均间隔时间，td为当前时刻距上一次相遇的间隔时间。

节点a、b间转发能力函数记为for(a,b)

(14)

2 NMAR路由机制

为提高消息的传输效率，降低网络开销，本文提出了一个感知节点间关系强度的路由机制NMAR。该路由机制消息传输流程如图4所示，描述如下：

(1)当两节点进入彼此通信半径内(相遇)，比较相遇节点是否为消息目的节点。若是则直接将消息转发给目的节点，同时删除该消息副本；

(2)若相遇节点不是消息的目的节点且携带消息的副本，则不转发消息；

(3)若相遇节点不是消息的目的节点且没有携带消息的副本，计算节点关系强度函数，并且与当前节点的函数值进行比较，当相遇节点关系强度值大于当前节点时，进入步骤(4)，否则不转发消息。

(4)计算节点转发能力值，并与当前节点能力值进行比较，当相遇节点大于当前节点时，将消息转发给中继节点，否则不转发消息。

图4 算法实现流程

3 仿真与分析

本文采用机会网络环境模拟器ONE(opportunistic network environment)[9]对消息投递率、开销比、平均传输时延等网络性能指标进行仿真分析。

3.1 仿真结果与分析

NMAR路由算法选择运动能力和投递能力更强的节点来转发消息，算法伪代码见表1。

仿真中引入考虑节点投递能力的Prophet路由算法[10]，控制网络开销的SprayandWait路由算法[11](SnW)和考虑节点运动的DPER进行仿真验证。仿真参数设置见表2。

3.2 网络性能与节点缓存大小

设置网络节点的数目为120，节点缓存空间变化范围为5 M至50 M，变化间隔为5 M。仿真结果如图5～图7所示。

由图5可以看出网络中消息投递率随节点缓存的增加而提高，在达到最佳效果后趋于平稳，然后消息投递率不再受缓存增加的影响。相比于Prophet、SprayandWait和DPER路由算法，NMAR的消息投递率分别提升了9.55%、5.72%和3.21%。图6为路由算法的平均传输时延与节点缓存关系的对比图，平均传输时延随着节点缓存的增加呈现出先下降后上升的趋势直至趋于平稳状态，NMAR路由算法的平均传输时延低于Prophet、SprayandWait和DPER路由算法。图7描述了网络的开销比随节点缓存增加的变化趋势。从整体看，4种路由算法的开销比随着节点缓存的增加而减小，逐步趋于平稳，NMAR路由算法的开销比整体较小，优于其它3种路由算法。

表1 NMAR路由算法实现代码

表2 仿真参数设置

图5 投递率随节点缓存大小的变化

图6 平均时延随节点缓存大小的变化

图7 开销比随节点缓存大小的变化

3.3 网络性能与节点数目

结合上一小节的仿真实验结果，将节点缓存空间大小设置为38 M，其它仿真参数保持不变，节点数目变化范围为40到200，增幅间隔为40。仿真结果如图8～图10所示。

图8 消息投递率随节点数量的变化

图9 平均时延随节点数量的变化

图10 开销比随节点数量的变化

从图8可以看出消息投递率随节点数目增加而增加，相比于Prophet、SprayandWait和DPER路由算法，NMAR的消息投递率优于其它3种路由算法，分别提升了15.47%、12.02%和5.68%。由图9可以看出随着网络节点数目的增加，消息平均传输时延不断减小后趋于平稳，NMAR的平均传输时延低于Prophet、SprayandWait和DPER路由算法。图10描述了网络开销比随节点数目增加的变化趋势。从整体看，4种路由算法的开销比均随着节点数目的增加表现出上升趋势。从局部看，NMAR路由算法的开销比整体较小，优于其它3种路由算法。

4 结束语

本文研究了延迟网络节点关系强度，通过节点连通状态的分析给出了节点强度关系的感知和度量方法，进一步给出了基于节点关系强度感知的延迟容忍网络路由机制，该机制利用运动过程中相遇节点数量的增减描述节点间关系强度的变化，同时依据节点之间的连接状态预测节点相遇概率，并结合节点关系评估节点的转发能力，根据节点关系强度和转发能力值选择合适的转发节点，优化消息的传输，提升消息的转发效率。仿真实验验证了该路由机制具有很高的扩展性，提高了消息传输效率，改善了网络性能，提升了资源的利用率。

[1]Khabbaz M J,Assi C M,Fawaz W F.Disruption-tolerant networking:A comprehensive survey on recent developments and persisting challenges[J].Communications Surveys & Tuto-rials,IEEE,2012,14(2):607-640.

[2]Cao Yue,Sun Zhili.Routing in delay/disruption tolerant networks:A taxonomy,survey and challenges[J].IEEE Communications Surveys & Tutorials,2013,15(2):654-677.

[3]Wei Kaimin,Liang Xiao,Xu Ke.A survey of social-aware routing protocols in delay tolerant networks:Applications,taxonomy and design-related issues[J].IEEE Communications Surveys & Tutorials,2014,16(1):556-578.

[4]Abdelkader T,Naik K,Nayak A,et al.SGBR:A routing protocol for delay tolerant networks using social grouping[J].IEEE Transactions on Parallel and Distributed Systems,2013,24(12):2472-2481.

[5]WU Dapeng,KONG Xiaolong,ZHANG Hongpei,et al.Social attributes aware data forwarding strategy in intermittently connected wireless networks[J].Journal on Communications,2015,36(1):42-51(in Chinese).[吴大鹏,孔晓龙,张洪沛,等.社会属性感知的间断连接无线网络数据转发策略[J].通信学报,2015,36(1):42-51.]

[6]Wang En,Yang Yongjian,Li li.A clustering routing method based on semi-Markov process and path-finding strategy in DTN[J].Chinese Journal of Computers,2015,38(3):483-499.

[7]Wang E,Yang Y,Chen X,et al.The improved algorithm of spray and wait routing protocol in delay tolerant network[J].International Journal of Advancements in Computing Technology,2013,5(7):238-245.

[8]Bulut E,Geyik S C,Szymanski B K.Utilizing correlated node mobility for efficient DTN routing[J].Pervasive and Mobile Computing,2014,13(4):150-163.

[9]Ayub Q,Rashid S,Zahid M S M,et al.Contact quality based forwarding strategy for delay tolerant network[J].Journal of Network and Computer Applications,2014,39(1):302-309.

[10]Mota V F S,Cunha F D,Macedo D F,et al.Protocols,mobility models and tools in opportunistic networks:A survey[J].Computer Communications,2014,48(8):5-19.

[11]ZHANG Feng,WANG Xiaoming,ZHANG Shanshan.Buffer aware ProPhet routing algorithm for opportunistic networks[J].Computer Engineering and Design,2015,36(5):1145-1149(in Chinese).[张峰,王小明,张珊珊.机会网络中考虑缓存的ProPhet路由算法[J].计算机工程与设计,2015,36(5):1145-1149.]