采用传递概率与社会网络分析的延迟容忍网络路由
2016-12-22杨沫由磊李冰赵建军
杨沫,由磊,李冰,赵建军
(天津大学电子信息工程学院,300072,天津)
采用传递概率与社会网络分析的延迟容忍网络路由
杨沫,由磊,李冰,赵建军
(天津大学电子信息工程学院,300072,天津)
结合了传递概率与社会网络分析的路由设计,可以充分利用网络中节点的运动特性增强端到端的消息传输质量。通过对节点进行相遇历史信息分析和社会关系分析,提出了基于传递概率与社会网络分析的延迟容忍网络路由(RPRSA)。相遇历史信息分析是通过节点在相遇时进行独立概率计算和彼此概率信息交换,使得节点可以预测它在短期内的移动特性;社会关系分析是通过节点在长期内的移动所形成的关系亲疏程度,使得节点可以预测它的长期运动规律。仿真结果表明,该路由算法能够很好地利用节点的运动特性,保证弱社会关系节点和孤立节点有更好的消息传输质量,更好地提高节点端到端的消息传输质量。
延迟容忍网络;社会网络分析;传递概率;路由设计
延迟容忍网络[1-2](delay tolerant network,DTN)是一类缺乏稳定、持续端到端连接的网络组织结构,这类网络的路由被称之为DTN路由,如果在DTN路由中采取了社会网络的分析方法,即为社会性DTN路由,其中典型的路由有标签路由(Lable)、升序路由(Rank)、冒泡路由(Bubble Rap,下文简化为Bubble)[3-4]等。Label直接利用社区传递的方式提高传输质量;Rank通过高流行度节点扩散消息的方式提高传输质量;Bubble通过利用高流行度节点向社区扩散消息的方式提高传输质量。可是现有的路由无法保证孤立节点和弱社会关系节点的通信传输质量,这正是现有社会性DTN路由面临的主要挑战之一。为此,本文设计了基于传递概率的社会性路由,既可以很好地预测节点短期移动特性,也可以很好地预测节点的长期运动规律,这样能够很好地解决现有社会性DTN路由所存在的这一问题,通过仿真验证了该路由与已有的路由相比有更好的通信传输质量。
1 RPRSA中的基本模型与方法
1.1 网络模型和假设
1.2 社会网络分析模型
本文采用文献[8-9]中的k-clique算法进行社会网络分析。k-clique算法具有如下特点:在数学形式上将这些完整的社区称之为k-clique,通过k-clique社会分析算法得到的社区要求社区内的节点必须与社区内其他节点都有联系,k为社区内的节点数,在k-clique算法中,允许不同的社区中有重复的节点,而且允许有不属于任何社区的孤立节点[10-11]。社会网络分析的方式如下,通过设定阈值θ,可以将归一化矩阵G进行二值化得到矩阵M,再设定社区内的节点数常值k′,通过已知的M与k′,就可以用k-clique算法得到网络中的社区结构,记作集合L,元素用l表示。特别指出的是,本文虽然采用了k-clique算法,但是可以容易地扩展到其他的社会网络分析算法(例如Laplace图特征值谱二分法、GN算法等),网络中节点间的社会关系并不是固定的,而是随着时间动态变化。由于集中式的社会网络分析方法无法动态反映节点之间的社会关系,本文采取了分布式的社会网络分析方法,可以更好地反映节点间的社会关系。
1.3 传递概率模型
在社会性DTN中,有一类情况可能会发生,网络中存在部分节点具有弱社会关系甚至是孤立的。为了保证这些节点在社会性DTN中的通信传输质量,本文采取了基于传递概率的路由策略[12]。通过传递概率的更新,节点可以更好地预测自己在未来一段时间内的运动特性。如果一对节点进行了直接端到端通信,那么在之后的一段时间内很可能再次进行直接端到端通信,这就可以提高弱社会关系甚至孤立节点的通信传输质量。本文的传递概率更新包括节点间传递概率更新和节点社区间传递概率更新。
节点间传递概率更新是在同一个社区的节点之间进行的。其中,直接节点间传递概率更新是节点对直接相遇后,直接更新彼此的传递概率;间接节点间传递概率更新是节点通过直接相遇节点更新与其他节点的传递概率。节点社区间传递概率是在不同社区的节点之间进行的。其中:直接社区传递概率更新是节点与不同社区的节点直接相遇后,直接更新节点与对方社区的传递概率;间接社区传递概率更新是节点通过直接相遇节点所在的社区更新与其他社区的传递概率。每一个节点都记录一个传递概率表单,表单采用矩阵P表示,元素用p表示,其中节点间的初始传递概率为pn,节点社区间的初始传递概率为pd。传递概率更新的计算则要根据节点间的相遇历史信息计算得到。
1.4 路由模型
为了保证DTN网络的消息传输成功率,降低网络中通信失败的源节点数,本文采取了源节点多拷贝路由机制:消息的源节点s最多可以在DTN网络中产生c份相同消息的拷贝;消息m到达目的节点d所在社区l后的多复制路由机制,即如果m传递到下一跳节点后,上一跳节点将不删除m,这可以加快网络中消息到达目的节点的速度。
同时,为了防止采取的路由机制对网络造成负担,本文首先限制了源节点拷贝数,其次消息在未到达l时采取零复制路由机制,即m传递到下一跳节点后,上一跳节点将删除m,并且消息在到达l后,l以外的所有节点都要删除消息m,最后限制m的生存时间,如果在规定时间内没有到达目的节点,那么删除m。
2 传递概率更新算法
传递概率更新分为传递概率衰减部分更新和传递概率上升部分更新两个步骤。传递概率衰减部分更新是节点间相遇时,在进行端到端通信之前,相遇节点依照相邻两次相遇的时间间隔进行衰减部分的更新;传递概率上升部分更新是相遇节点间互相参照对方的传递概率表单,更新自身表单中对应传递概率相对较小的部分。
直接节点间传递概率更新如下式
(1)
间接节点间传递概率更新,如果p(y,z)=p(x,z),则传递概率上升部分无需更新,只需要更新传递概率衰减部分;在p(y,z) (2) 直接社区传递概率更新如下式 (3) 间接社区传递概率更新,如果p(y,l)=p(x,l),则传递概率上升部分不需要更新,只需要更新传递概率衰减部分;在p(y,l) (4) 在基于传递概率与社会网络分析的延迟容忍网络路由算法(delay-tolerant network routing based on probability of relay and social analysis, RPRSA)中,如果有需要传递消息的节点相遇,则根据节点间彼此的传递概率表单以及社会关系属性判断消息是否进行传递。RPRSA路由算法流程如下。 设置实验仿真时间T;设置仿真实验的节点组;设置节点的消息产生周期r;设置消息最大副本数c;设置消息生存时间F;初始化节点的传递概率表单P。 在节点x、y相遇时,节点x的路由过程如下。 步骤1 判断节点x中消息的生存时间是否超过F,对于超过F的消息,在节点x中删除; 步骤2 判断节点x是否有需要传递的消息,如果有进行步骤3,否则节点x结束消息传递; 步骤3 判断节点y是否接收过节点x即将传递的消息,如果接收过,则拒绝再次接收这个消息,否则节点x、y进行步骤4; 步骤4 如果节点x有节点y没有接收过的消息m,且该消息的目的节点是d,则目的节点d所在的目的社区是l。 步骤5 如果节点y是消息m的目的节点,则执行步骤6,否则节点x直接将消息m传递给y,并且删除网络中所有的消息m; 步骤6 如果节点x、y不都在目的社区l外部,则执行步骤7,否则比较节点x、y与目的社区l的传递概率,当p(x,l) 步骤7 如果节点x、y不都在目的社区l内部,则执行步骤8,否则比较节点x、y与目的节点d的传递概率,当p(x,d) 步骤8 节点x在目的社区l外部,节点y在目的社区l内部,则节点x将消息m发送到节点y,并且节点x删除消息m。 步骤9 循环执行步骤1～8,直到仿真时间结束。 RPRSA路由充分利用了节点的短期移动特性和长期运动规律,使得弱社会关系节点和孤立节点可以更好地传输消息,保证更多的节点之间能够建立端到端的有效连接。 4.1 仿真场景与参数 本文采用了数据集Reality Mining[13-14],该数据集开始于2004年,采集了96个节点,其中75个节点来自麻省理工大学媒体实验室,另外21个节点来自临近的斯隆商学院。 本文采集时间为16 981 816 s,采集了205 187组数据,每一组数据包括以下4方面内容:组序号,即代表数据集中的第几组数据;连接状态,即连接或者断开;时间,即得到此连接状态的时间;节点序号,即处于此连接状态下的一对节点各自的序号。 仿真实验选取了数据集中的3个数据段,表1列出了所选取的数据量以及仿真的起止时间。 表1 仿真实验中选取的3个数据段 实验仿真时间为T,即仿真时间的起始值和终止值的差值。仿真时选取了3个不同的节点组,每组节点的数据集中有96个节点作为源节点,每个源节点随机选取一个节点作为自己的目的节点,目的节点的产生是随机的,没有关联;消息产生周期r为50 000 s;衰减因子γ=0.98;传递因子β=0.25;节点间的初始传递概率pn=0.75,节点社区间的初始传递概率pd=0.75。 初步的仿真表明,这些参数值的选取是合理的。尽管参数的取值并不是唯一的,但是取值符合概率模型的实际情况。当参数值发生变化后,会对网络中的节点间传递概率产生影响,但对最后的仿真结果几乎无影响,因为消息动态地在网络中寻找合适的节点进行路由转发。 本文中将RPRSA路由分别与Rank、Label、Bubble[7]路由进行了对比,分析了消息生存时间F和源节点消息拷贝数c对RPRSA路由的影响,并从两个方面衡量算法的性能:源节点平均传输成功率,即目的节点收到的消息数占源节点发送消息总数的百分比;通信失败的源节点数,即在仿真时间内未能与目的节点成功通信至少一次的源节点数。 4.2 仿真结果 首先分析RPRSA路由,在给定的3个节点组中,每组节点分别在已选取的3个数据段上进行仿真,消息生存时间F=T/3,源节点消息拷贝数c=1。对Rank、Label、Bubble路由进行同样的仿真,这样每种算法都会得到9组仿真数据。 4.2.1 源节点平均传输成功率 由于篇幅限制,对每种算法得到的9组数据中的平均传输成功率再次取平均值,然后再与其他算法进行比较。 图1 RPRSA和Label路由平均传输成功率差值 图2 RPRSA和Rank路由平均传输成功率差值 图3 RPRSA和Bubble路由平均传输成功率差值 图1～3是RPRSA路由分别与Label、Rank、Bubble路由的源节点平均传输成功率R进行差值(RRPRSA,Label;RRPRSA,Rank;RRPRSA,Bubble)运算得到的结果。在图1中差值大于0的数目要明显多于小于0的数目;在图2中差值大于0的数目要略微多于小于0的数目;在图3中差值大于0的数目要略微少于小于0的数目。因此,可以得到RPRSA路由的源节点传输成功率优于Label和Rank路由,而相比Bubble路由会有些劣势。 4.2.2 通信失败的源节点数 表2列出了网络中通信失败的源节点数对比情况。由于篇幅限制,本文没有列出第3组节点在3个数据段上的通信失败的源节点数。 可以看到,与Label、Rank、Bubble路由相比,在相同条件下RPRSA路由中通信失败的源节点数都要少很多。因此,RPRSA路由可以更好地保证弱社会关系节点和孤立节点的通信传输质量,更好地实现端到端之间的通信,尤其对于那些端端之间有更高可靠性要求的网络,RPRSA路由是更好的选择。 表2 网络中通信失败的源节点数对比情况 4.2.3 生存时间F对RPRSA路由的影响 选取第1组节点和第3个数据段,在其他条件相同时,分别取值为T/3、T/2和T。图4中是TTL取值T/2和T/3时所得到的平均传输成功率的差值;图5中是TTL取值T和T/2时所得到的平均传输成功率的差值。 图4 TTL取值T/3与T/2时性能对比 图5 TTL取值T/2与T时性能对比 表3比较了第3个数据段,对于不同的F取值时,网络中通信失败的源节点数。 适当的增加F,可以提高网络的平均传输成功率,但几乎不会降低通信失败的源节点数;而且F增加也会对网络造成负担。 4.2.4 源节点拷贝数c对RPRSA路由的影响 表3 在第3个数据段F对通信失败的源节点数的影响 选取第1组节点和第3个数据段,在其他条件相同时,c分别取值1和5。图6是c=5和c=1时所得到的平均传输成功率的差值。 图6 源节点拷贝数取值5与1时性能对比 表4统计了c取值1和5时,网络中通信失败的源节点数。 表4 源节点拷贝数对通信失败的源节点数影响 适当地提高c值,虽然可以提高平均传输成功率,但几乎不会降低通信失败的源节点数,而且c的取值增加也会对网络造成负担。 与Label、Rank、Bubble路由相比,本文所提的RPRSA路由在保证平均传输成功率的同时减小了通信失败的源节点数,尤其是对于需要在某些节点间完成重要消息传递的应用,RPRSA路由更具有可靠性。 本文没有考虑消息的传输时延,与Bubble路由相比,平均传输成功率仍然有进一步提高的空间。今后将进一步研究改善RPRSA路由的性能。 [1] 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: 27-34. [2] DALY E M, HAAHR M. Social network analysis for routing in disconnected delay-tolerant MANETs [C]∥Proceedings of the 8th ACM International Symposium on Mobile Ad Hoc Networking and Computing. New York, USA: ACM, 2007: 32-40. [3] BETTSTETTER C. Mobility modeling in wireless networks: categorization, smooth movement, and border effects [J]. ACM Sigmobile Mobile Computing and Communications Review, 2001, 5(3): 55-66. [4] 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. [5] JONES E P C, LI L, SCHMIDTKE J K, et al. Practical routing in delay-tolerant networks [J]. IEEE Transactions on Mobile Computing, 2007, 6(8): 943-959. [6] EVERETT M, BORGATTI S P. Ego network betweenness [J]. Social Networks, 2005, 27(1): 31-38. [7] FREEMAN L C. A set of measures of centrality based on betweenness [J]. Sociometry, 1977, 40(1): 35-41. [8] 白如江, 冷伏海.k-clique 社区知识创新演化方法研究 [J]. 图书情报工作, 2013, 57(17): 86-94. BAI Rujiang, LENG Fuhai. Knowledge innovational evolution analysis based onk-clique community network [J]. Library and Information Service, 2013, 57(17): 86-94. [9] HUI P, YONEKI E, CHAN S Y, et al. Distributed community detection in delay tolerant networks [C]∥Proceedings of the Second ACM/IEEE International Workshop on Mobility in the Evolving Internet Architecture. New York, USA: ACM, 2007: 7. [10]EVERETT M G, BORGATTI S P. Analyzing clique overlap [J]. Connections, 1998, 21(1): 49-61. [11]HUI P, CROWCROFT J. How small labels create big improvements [C]∥Proceedings of the 2007 IEEE International Conference on Pervasive Computing and Communications Workshop. Piscataway, NJ, USA: IEEE, 2007: 65-70. [12]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. [13]POTTENGER W M, YANG T. Detecting emerging concepts in textual data mining [C]∥Proceedings of the 2002 Society for Industrial and Applied Mathematics. New York, USA: ACM, 2002: 89-105. [14]EAGLE N, PENTLAND A. Reality mining: sensing complex social systems [J]. Personal and Ubiquitous Computing, 2006, 10(4): 255-268. [本刊相关文献链接] 赵皓,高智勇,高建民,等.一种采用相空间重构的多源数据融合方法.2016,50(8):84-89.[doi:10.7652/xjtuxb201608 014] 赵博选,高建民,陈琨.求解多目标柔性作业车间调度问题的两阶段混合Pareto蚁群算法.2016,50(7):145-151.[doi:10.7652/xjtuxb201607022] 刘岳镭,冯祖仁,任晓栋.具有恶化效应的双代理单机最优调度算法.2016,50(6):9-14.[doi:10.7652/xjtuxb201606002] 刘强,董小社,朱正东,等.一种短作业环境下的延迟调度算法.2015,49(2):1-5.[doi:10.7652/xjtuxb201502001] 崔颖安,李雪,夏辉,等.面向社交媒体嵌入关系数据感知方法的研究.2015,49(2):31-36.[doi:10.7652/xjtuxb201502 006] 陈家旭,唐亚哲,胡成臣,等.延迟容忍网络中基于地点偏好的社会感知多播路由协议设计.2014,48(6):13-18.[doi:10.7652/xjtuxb201406003] 赵晓明,周颢,何军,等.视频点播系统中视频分片协同存储方案研究.2014,48(4):26-30.[doi:10.7652/xjtuxb201404 005] (编辑 武红江) A Delay-Tolerant Network Routing Based on Probability of Relay and Social Network Analysis YANG Mo,YOU Lei,LI Bing,ZHAO Jianjun (School of Electronic Information Engineering, Tianjin University, Tianjin 300072, China) Routing designs that combine with relay probability and social network analysis can fully utilize movement characteristic of nodes and enhance quality of message transmission from end to end. A delay-tolerant network routing based on probability of relay and social network analysis (RPRSA) is proposed based on the analyses of historical information of nodes encounters and social relationship. The analysis of historical information is to forecast short-run movement characteristic by independent probability computation and probability information exchange with each other when nodes encounter, and the analysis of social relation is to forecast long-run movement law by the degree of intimacy among nodes formed in long-run movements. Simulation results show that the proposed routing makes full use of movement features among nodes, guarantees the quality of messages transmission among the nodes with weak social relation and the isolate nodes, and enhances the quality of messages transmission from end to end. delay-tolerant network; social network analysis; relay probability; routing design 2016-08-01。 作者简介:杨沫(1990—),男,硕士生;由磊(通信作者),男,讲师。 基金项目:国家自然科学基金资助项目(61202380);天津市自然科学基金资助项目(12JCQNJC00300)。 时间:2016-10-19 10.7652/xjtuxb201612021 TP393 A 0253-987X(2016)12-0136-06 网络出版地址:http: ∥www.cnki.net/kcms/detail/61.1069.T.20161019.1112.004.html3 路由算法
4 仿真结果与分析
5 结 语
