文章快速检索  
  高级检索
社会机会网络中基于节点相遇历史信息的路由算法
刘玉梅 , 任清源
哈尔滨工程大学 信息与通信工程学院, 黑龙江 哈尔滨 150001     
摘要: 针对Bubble Rap路由算法的路由开销不理想的问题,提出一种利用节点相遇历史信息和删除消息副本相结合的低开销路由(LCMT)算法。利用与目的节点相遇次数进行消息转发改变了Bubble Rap单一的消息转发评判标准,使其对不同数据集场景的适应性得到提高,并结合效用函数对消息副本数进行控制,从而减小了路由开销。和Bubble Rap路由算法相比,仿真结果表明在Infocom06和MIT数据集中,该算法可在保证良好消息传输成功率的前提下显著降低路由开销。
关键词: 社会机会网络     路由算法     LCMT     相遇次数     效用函数    
Routing algorithm based on node meeting history information in the social opportunistic network
LIU Yumei , REN Qingyuan
College of Information and Communication Engineering, Harbin Engineering University, Harbin 150001, China
Abstract: For solving the problem that routing overhead is not ideal in the social opportunistic network routing algorithm-Bubble Rap, this paper presented a low delivery cost routing algorithm which combines nodes' historical meeting information and deleting messages' duplicates-LCMT(low delivery cost protocol using the meeting times with destination node). Using meeting times with destination node changes the single evaluation criteria for message forwarding of bubble-rap and improves the adaptability to different data sets occasions. It also reduces the routing delivery cost through combining with the utility function which can control messages' copy number. Compared with bubble rap, the simulation results in Infocom06 and MIT data sets show that the proposed algorithm can moderately increase the success rate of message transmission and effectively reduce the routing overhead.
Key words: social opportunistic network     routing protocol     LCMT     meeting times     utility function    

机会网络[1]的概念来源于容忍延迟网络(DTN)[2-3],是一种无需固定网络设施的无线自组网。近些年来研究人员提出如Epidemic、Spray and Wait、Spray and Focus等基于多副本的路由算法[4],虽然利用多副本可以提高消息传输成功率并减少传输延迟,但缺点是路由开销较大,在网络资源受限时,会降低网络性能。如今手持移动设备的普及使机会网络可以利用节点的社会特性进行消息的转发,由于通信节点从一定程度上代表了人类活动的社会性,因此社会网络分析的方法有助于该类网络路由算法的设计,这类网络也被称之为社会机会网络[5-6]。在社会机会网络中,人们通常由于共同兴趣、职业、活动范围等因素组成社区,社区内的节点容易互相转发消息,所以社会机会网络算法应该将人类社区考虑进来。在文献[7]中,作者提出基于社区的路由算法Bubble Rap,通过提取人类的移动数据进行社区划分并定义社区中的重要节点,这样充分利用人类的社交关系,从而将消息传输给更容易到达目的节点的中继节点。然而Bubble Rap的转发目标不够准确,消息转发方式比较单一,且路由开销仍有改善的空间。故本文提出新的算法对其进行改进。

1 LCMT算法提出的理论基础

社会机会网络主要指移动设备组成的网络-PSN(pocket switch networks)[8],这些移动设备由人携带,因此反映了人们的日常生活活动。在这种环境下,研究人类的移动和社交特点成为提高路由性能的关键。在真实数据集中可以反映出人类从一个地点移动到另外一个地点的频率、某人与他人的相遇次数、相遇后连接持续时间,以及各人所属社区和偏好等信息,这些信息都是有助于提高路由性能的。

尽管Bubble Rap已被证实在PSNs中有很好的性能,但其仍具有局限性。它仅根据节点的中心性这一特性来寻找社区中的中继节点,中心性反映了节点的相遇次数,高中心性节点被定义为相对容易完成消息传输的中继节点,与记录目的节点的相遇次数相比,这样的方法效率低且不具有针对性,因此有时不能及时将消息传送到目的节点。另外在社会机会网络中,消息通常是通过拷贝的方式进行转发的,这样在网络中就会存在大量的消息副本,在保证了消息传输成功率的同时也带来了较高的路由开销。在本文要改进的社区路由算法Bubble Rap中,只是删除了将要进入社区内的消息在社区外的副本,而社区外部的消息在进入社区之前会产生很大的路由开销。对于那些转发消息速度较慢的节点,很容易发生拥塞,不能接收新的消息。在Bubble Rap中,用Infocom06数据集进行仿真发现,虽然传输成功率良好,但是路由开销并不理想。本文在Bubble Rap路由算法的基础上,充分利用与目的节点相遇次数这一指标将消息传输到目的节点或目的节点所在社区,降低了社区外消息传输的盲目性,同时通过效用函数删除网络中多余的消息副本,从而降低了路由开销。

2 改进的低开销路由算法

为了改善Bubble Rap算法的不足,本文提出利用节点相遇历史信息和删除消息副本相结合的低开销路由算法(LCMT):1)利用与目的节点的相遇次数结合Bubble算法作为主要的消息转发方式;2)混合效用机制综合利用消息生存时间、节点相遇次数和社区划分来控制消息副本数;3)设置的TTL阈值有助于提高消息转发效率,下面将具体介绍新的改进算法。

2.1 LCMT算法中的消息转发机制

在文献[9]中,社区的划分和中心节点都是根据与其他节点的相遇次数形成的,可见节点相遇次数是可以作为消息转发依据的。为了使消息的转发具有更强的针对性,提取与目的节点相遇次数作为新的转发标准,将有利于路由性能的提升。

Infocom06和MIT这2个数据集的4号节点与各消息的目的节点相遇次数分别如图 12所示,Infocom06中的平均节点相遇次数为1 740次,而MIT中仅为130次,但2个数据集中都有相遇次数相对较多的节点,而与目的节点相遇频繁的节点显然可以提高消息传送到目的节点的机会,这有助于机会网络的“转发”特性。

图 1 Infocom06数据集4号节点与各消息目的节点相遇次数
图 2 MIT数据集各节点与目的节点相遇次数

为了提高对MIT数据集代表的低节点相遇次数网络场景的适应性,本文中提出的LCMT算法还结合了Bubble Rap进行消息的转发。此外,与目的节点的相遇次数也被用于效用函数的产生机制中。

2.2 LCMT算法中的消息副本控制策略

在利用Bubble Rap算法进行消息传输时,只有在消息从目的节点社区外进入社区内时才会进行消息副本的删除,也就是图 3中节点b要将消息转发给c这种情况。这样导致在目的节点社区内部和外部都会存在大量的消息副本。图 3中的sd节点分别代表消息源节点和目的节点,右侧虚线圆环代表目的节点所在的社区。

图 3 Bubble Rap中基于社区的消息转发原理

基于节点的相遇历史信息和社区信息[9],本文提出一种用于控制网络中消息副本数的效用函数:

式中:ui(M,A)表示目的节点为A的消息M在节点i处的效用值,该值越小,表明其对应的消息副本越容易被删除;当消息的生存时间到期时,CTTL为0,否则为1,使用这个参数是为了删除已过期的消息,当该值为零时效用值为零,便直接删除该消息。当消息将要由社区外部进入社区内部时,将Ccommunity设为0,表明消息进入社区内部后便无需再让社区外节点保留消息副本;TTime(M)代表消息M从产生到现在所用的时间,TTTL(M)代表消息M的生存时间,反映了消息将要到期的程度,该比值越大表明消息越需及时处理,应该得到保留;中的fDest(M)表示当前节点与消息M的目的节点相遇次数,fAll表示当前节点与其他所有节点相遇次数,该比值使得消息转发更具有针对性,其值越大越有利于保留当前节点中的消息副本,从而让更小效用值的消息被删除。

当节点ij相遇时,如果进行了消息的转发,那么删除i中的消息副本需满足:

式中0≤up≤1用于设定社区外删除副本的条件,up参数的变化可以调节社区外消息副本的删除程度。该值越大,表明满足删除条件的节点越多,越不利于社区外多副本的存在。

图 4是在Infocom06数据集下对LCMT算法的性能仿真,可以看到在传输成功率基本恒定的情况下,up值越大其路由开销越小。因此,在下文中基于Infocom06数据集的仿真将该参数设为1。

图 4 参数up对LCMT算法性能的影响
2.3 LCMT算法中设置的TTL阈值

文献[10]指出Bubble-Rap中的节点必须等待社区中高中心性节点才进行消息转发,这样容易超出消息的生存时间,为此在LCMT中设置TTL(time to live)阈值来减少这种消息的损耗,从而保证了消息的成功传输,并在一定程度上减少路由开销。

TTL阈值以所占设定消息生存时间的百分比来表示,本文中称之为Threshold。当消息存活时间大于阈值时,说明利用与目的节点相遇次数进行消息转发效率不高,此时选择用Bubble Rap进行消息转发更好,在这2种转发方式中都伴随着效用函数对消息副本的控制。

表 1中的数据仿真是在TTL值为3 600 min的条件下,利用Infocom06数据集来反映文中提到的TTL阈值(Threshold)变化对消息传输性能的影响。从表 1可以看出当Threshold=0时,代表LCMT算法仅利用与目的节点相遇次数这一指标进行消息转发,此时消息的传输成功率虽然比较理想,但单纯利用相遇次数的机制也带来了一定的路由开销;而当Threshold=1时,只利用带有消息副本控制机制的Bubble Rap算法来转发消息,可以看到传输成功率和路由开销都不太理想。为了能够在保证传输成功率的同时尽量降低路由开销,当 LCMT在Infocom06数据集下进行仿真时,本文将Threshold参数的取值设置为0.4。

表 1 TTL阈值对传输性能的影响
Threshold消息传输成功率路由开销
00.91312.230
0.10.90010.873
0.20.8929.204
0.30.8918.787
0.40.8888.378
0.50.8848.726
0.60.8809.165
0.70.8719.706
0.80.86810.621
0.90.85611.852
1.00.84013.256

2.4 LCMT算法中的消息转发原理

综合以上3种策略,LCMT完成了对Bubble Rap算法的改进,当节点ninj相遇后,其消息转发原理如下所示:

when node ni becomes in contact with node nj

if the connection history of node ni contains the

destination node of the message M

do MyFreWithDest++

if the connection history of node nj contains the

destination node of the message M

do PeerFreWithDest++

if time of the message M used > threshold*TTL

if PeerFreWithDest >MyFreWithDest

do Send message M to node nj

if ui(M,A) < up*uj(M,A)

do Delete message M of node ni

else

Leave this message in the node ni

else

if peerInCommunity & &!meInCommunity

do Send message M to node nj

if ui(M,A) < up*uj(M,A)

do Delete message M of node ni

else

if !peerInCommunity & &meInCommunity

do Leave the message M in node ni

else

if both nodes in the same community

do Send message M base on Centrality

if ui(M,A) < up*uj(M,A)

do Delete message M of node ni

其中PeerFreWithDest表示的是nj与消息M的目的节点的相遇次数,MyFreWithDest表示的是节点ni与目的节点的相遇次数,peerInCommunity表示节点nj所属的社区,meInCommunity表示节点ni所属社区。首先算法对节点相遇历史信息进行统计,然后结合TTL阈值和社区划分策略进行消息的转发,无论在基于相遇次数的传输机制中还是在原有的Bubble Rap算法中都运用了效用函数来判决是否删除消息副本。当参数Threshold=1时,该算法退化为带有副本控制机制的Bubble Rap算法;当Threshold=0时,该算法仅利用与目的节点相遇次数进行消息的转发。

3 LCMT协议仿真与性能分析

本文在ONE仿真平台下对Bubble Rap和LCMT算法进行仿真和性能对比,为了考察节点平均相遇次数对算法性能的影响,分别在Infocom06和MIT数据 集中对这2种算法进行仿真。采用消息传输成功率和路由开销这两个指标来评价路由算法的性能,消息传输成功率衡量了路由算法正确传输消息到目的节点的能力,而路由开销衡量了消息转发的效率,路由开销越大表明转发效率越低,它们分别定义如下:

3.1 Infocom06数据集下的LCMT性能仿真

Infocom06数据集代表了一种平均节点相遇次数较多的网络场景,其具体配置参数如表 2所示,采用随机种子仿真10次取平均值,考察消息生存时间对算法性能的影响。LCMT中的Threshold值设置为0.4,而up的值设为1。

表 2 Infocom06数据集下主要仿真参数
参数名称 参数值
设备iMote
网络类型蓝牙
持续时间/d3
仿真时间/min3 600
实验设备数量98
消息大小/kB1
产生消息个数1 000
平均节点相遇次数1 740

实验表明LCMT算法在平均相遇次数较多的Infocom06数据集下具有很好的性能。在图 5中虽然Bubble Rap算法已经具有很高的消息传输成功率,但LCMT在此基础上仍有所提升。图 6说明,相比于 Bubble Rap算法,LCMT在路由开销方面有着较大的优势,这表明用于控制消息副本数的效用函数达到了有效降低路由开销的目的。

图 5 Infocom06下LCMT的消息传输成功率
图 6 Infocom06下LCMT的路由开销
3.2 MIT数据集下的LCMT性能仿真

MIT数据集代表了一种平均节点相遇次数较少的网络场景,按照表 3的参数指标进行配置,采用随机种子仿真10次取平均值,考察消息生存时间对算法性能的影响。由于该数据集下节点相遇机会较少,为尽量提高消息传输成功率,LCMT的Threshold值设置为0.1,而up的值设为0.7。

表 3 MIT数据集下主要仿真参数
参数名称 参数值
设备手机
网络类型蓝牙
持续时间/d246
仿真时间/min30 240
实验设备数量97
消息大小/kB1
产生消息个数1 000
平均节点相遇次数130

图 2表明MIT数据集中的节点相遇次数普遍偏低,因此仅利用与目的节点相遇次数作为消息转发依据所获得的算法性能不会很理想,但LCMT结合了基于社区划分的Bubble Rap路由算法,使得在MIT这样的网络场景中也能够取得较好的性能提升。从图 78可以看到,在MIT数据集下,LCMT算法的消息传输成功率相比于Bubble Rap有所提升,同时也达到了降低路由开销的目的。但MIT数据集中的节点平均相遇机会较少,导致LCMT算法的消息传输成功率远不如Infocom06数据集的表现。

图 7 MIT数据集下LCMT算法的消息传输成功率
图 8 MIT数据集下LCMT算法的路由开销
4 结论

通过仿真,证实了利用与目的节点相遇次数进行消息转发的可行性,并表现出了良好的性能。

1) LCMT算法对于不同的数据集具有更好的适应性,它不仅继承了Bubble Rap的社区划分性能,而且还利用与目的节点相遇次数这一指标增加了消息传输成功率,提出的删除消息副本的效用函数在很大程度上减小了路由开销。

2) 对于MIT这种平均节点相遇次数较少的数据集,大多数路由算法都很难实现较高的消息传输成功率。即使在Epidemic路由算法中,MIT数据集的消息传输成功率最高也只有66%,但Epidemic是基于洪泛策略的路由算法,它以高路由开销为代价来换取消息传输成功率性能,在实际网络资源有限的情况下很难实现,只具有参考意义。

本文在有效降低路由开销的基础上相比于Bubble Rap算法适度提高了消息传输成功率,今后的工作应该继续提高路由算法在节点相遇机会较少的网络场景中的消息传输成功率,可以尝试从数据集中提取新的节点相遇特征进行消息的转发。

参考文献
[1] 仁智, 黄勇, 陈前斌. 机会网络路由协议[J]. 计算机网络 , 2010, 30 (3) : 723-728
[2] FALL K. A delay-tolerant network architecture for challenged internets[C]//Proceedings of the 2003 Conference on Applications, Technologies, Architectures, and Protocols for Computer Communications. New York, USA: ACM, 2003: 15-28.
[3] IRTF. Delay Tolerant Networking Research Group[EB/OL]. [2015-08-09].http://www.dtnrg.org.
[4] POONGUZHARSELVI B, VETRISELVI V. Survey on routing algorithms in opportunistic networks[C]//Proceedings of 2013 International Conference on Computer Communication and Informatics. Coimbatore, India: IEEE, 2013: 1-5.
[5] SOELISTIJANTO B, HOWARTH M. Traffic distribution and network capacity analysis in social opportunistic networks[C]//Proceedings of the 2012 IEEE 8th International Conference on Wireless and Mobile Computing, Networking and Communications. Washington DC, USA: IEEE, 2012: 823-830.
[6] AYYAT S A, HARRAS K A, ALY S G. Interest aware people rank: towards effective social-based opportunistic advertising[C]//Proceedings of 2013 IEEE Wireless Communications and Networking Conference. Shanghai, China: IEEE, 2013: 4428-4433.
[7] HUI P, CROWCROFT J, YONEKI E. Bubble Rap: social-based forwarding in delay tolerant networks[J]. IEEE transactions on mobile computing , 2011, 10 (11) : 1576-1589 DOI:10.1109/TMC.2010.246
[8] PIETILAINEN A K, DIOT C. Social pocket switched networks[C]//Proceedings of 2009 IEEE INFOCOM Workshops. Rio de Janero, Brazil: IEEE, 2009: 19-25.
[9] LEE J, KIM S K, YOON J H, et al. Snapshot: a forwarding strategy based on analyzing network topology in opportunistic networks[J]. Wireless networks , 2015, 21 (6) : 2055-2068 DOI:10.1007/s11276-015-0900-9
[10] JAIN S, KISHORE N, CHAWLA M, et al. Composite mechanisms for improving Bubble Rap in delay tolerant networks[J]. The journal of engineering , 2014 DOI:10.1049/joe.2013.0117

文章信息

刘玉梅, 任清源
LIU Yumei, REN Qingyuan
社会机会网络中基于节点相遇历史信息的路由算法
Routing algorithm based on node meeting history information in the social opportunistic network
应用科技, 2016, 43(5): 70-74
Applied Science and Technology, 2016, 43(5): 70-74
DOI: 10.11991/yykj.201511024

文章历史

收稿日期: 2015-11-25
网络出版日期: 2016-09-19

相关文章

工作空间