基于预期延迟值的扩散转发路由算法

doi:10.11959/j.issn.1000-0801.2016294

摘要/Abstract

摘要：

针对现有延迟容忍网络路由算法在消息传递过程中分发不灵活的问题，提出基于节点通话历史记录计算预期通断时长以及消息传递延迟值，并根据结果选择节点、分配副本数进行消息转发的路由算法（MDESF）。在算法不同阶段，根据节点的活跃度选择中继节点，再分配传递消息的副本数目，加快分发，降低延迟。同时为保证消息及时传递，在单副本阶段选择最优节点转发。本算法同时提出内存管理策略，提高消息转发成功率。仿真实验表明，该算法相对其他同类算法在投递率、交付时延和网络拥塞比率方面综合表现更优。

关键词: 延迟容忍网络, 扩散等待路由, 内存管理策略

Abstract:

The existing DTN routing algorithms tend to make data transition inflexible and have a long delay in contact.To solve those problems,an algorithm was proposed which called meeting delay expect value in spray and forward routing algorithm for DTN（MDESF）.This algorithm will use mobile node's contact history to conduct the expected average contact/disconnect time and message expected wait value（EWV）.With those attributes the MDESF will proportionally distribute replicas of a message between two nodes in multiple replicas phase.A buffer management strategy was proposed in order to improve the success rate of imformation fornarded.The simulation results illustrate that the proposed MDESF protocol outperform other existing ones.

Key words: delay tolerant network, spray and wait routing, buffer management strategy

刘鑫,金光,江先亮,钮俊. 基于预期延迟值的扩散转发路由算法[J]. 电信科学, 2016, 32(11): 56-63.

Xin LIU,Guang JIN,Xianliang JIANG,Jun NIU. Meeting delay expect value in spray and forward routing algorithm[J]. Telecommunications Science, 2016, 32(11): 56-63.

图/表 9

图1

表1

图2

图3

图4

图5

表2

图6

图7

参考文献 17

[1]	KEVIN . A delay-tolerant network architecture for challenged internets[J]. ACM Sigcomm Computer Communication Review, 2003,33(4): 27-34.
[2]	BURLEIGH S , HOOKE A , TORGERSON L , et al. Delay-tolerant networking:an approach to interplanetary Internet [J]. IEEE Communications Magazine, 2003,41(6): 128-136.
[3]	熊永平，孙利民，牛建伟，等. 机会网络[J]. 软件学报， 2009,20(1):124-137. XIONG Y P , SUN L M , NIU J W , et al. Opportunistic networks[J]. Journal of Software, 2009,20(1):124-137.
[4]	CAO Y , SUN Z . Routing in delay/disruption tolerant networks:ataxonomy,survey and challenges [J]. IEEE Communications Surveys＆Tutorials, 2011,41(2): 297-327.
[5]	VAHDAT A , BECKER D . Epidemic routing for partially-connected Ad Hoc networks[J]. Master Thesis, 2000.
[6]	SPYROPOULOS , THRASYVOULOS , PSOUNIS , et al. Spray and wait:an efficient routing scheme for intermittently connected mobile networks[J]. ACM WDTN, 2015: 252-259.
[7]	蒋庆丰，门朝光，贾美娟，等. 基于双向拍卖的 DTN拥塞感知激励策略[J]. 电信科学， 2015,31(1):15-22. JIANG Q F , MEN C G , JIA M J , et al. Congestion-aware incentive scheme based on double auction for DTN [J]. Telecommunications Science, 2015,31(1):15-22.
[8]	刘耀，王建新，等. 一种基于节点运动范围自感知的路由算法[J]. 华南理工大学学报， 2009,37(10):79-83. LIU Y , WANG J X . A routing scheme based on awareness of node motion scope [J]. Journal of South China University of Technology（Natural Science Edition）, 2009,37(10):79-83.
[9]	王恩，杨永健，李莅 . DTN中基于生命游戏的拥塞控制策略[J]. 计算机研究与发展， 2014,51(11):2393-2470. WANG E , YANG Y J , LI L . Game of life based congestion control strategy in delay tolerant networks [J]. Journal of Computer Research and Development, 2014,51(11):2393-2470.
[10]	ZHENG H , WANG Y , WU J , et al. Optimizing multi-copy two-hop routing in mobile social networks [C]// 11th IEEE International Conference on Sensing,Communication,and Networking, June 9-12,2014, Singapore. New Jersey: IEEE Press, 2014: 573-581.
[11]	GAO W , LI Q , CAO G . Forwarding redundancy in opportunistic mobile networks:Investigation and elimination [C]// IEEE Conference on Computer Communications, July 11-13,2014, New York,USA. New Jersey: IEEE Press, 2014: 2301-2309.
[12]	JONES E P C , LI L , WARD P A S . Practical routing in delay-tolerant networks [C]// ACM SIGCOMM Workshop on Delay-Tolerant Networking ACM, October 3-5,2005, Philadelphia,USA. New Jersey: IEEE Press, 2005: 237-243.
[13]	WANG E , YANG Y , WU J . A knapsack-based message scheduling and drop strategy for delay-tolerant networks [J]. Wireless Sensor Networks, 2015: 120-134.
[14]	王联，王新华，穗敬麒 . 机会网络模拟器ONE及其扩展研究[J]. 计算机应用研究， 2012,29(1):272-277. WANG L , WANG X H , SUI J L . Extending research for ONE simulator of opportunistic network [J]. Application Research of Computers, 2012,29(1):272-277.
[15]	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.
[16]	PAPANIKOS N . Coordinating replication decisions in multi-copy routing for opportunistic networks [C]// 10th IEEE wiMob. April 23-29,2014, Bowcelona,Spain. New Jersey: IEEE Press, 2014.
[17]	BURGESS J , GALLAGHER B , JENSEN D , et al. MaxProp:routing for vehicle-based disruption-tolerant networks[C]// 25th IEEE International Conference on Computer Communications, April 23-29,2006, Barcelona,Spain. New Jersey: IEEE Press, 2006: 1-11.

符号	说明
N	网络中节点数
TTL_i	消息i的生存周期
L_k	消息副本数
C_ij	节点平均连接时间
D_ij	节点平均断开时间
E_ij	预期延迟值
M_i	消息大小
W_ij	节点i、j的连接带宽
ε_i	消息i成功分发率
U_i	消息i效用值
EWV（v_i,v_d）	v_i到达v_d预期等待时间

参数名称	取值范围
节点数目/个	120～300
消息初始副本数	10
消息大小/MB	0.5～2
信息大小/MB	0.5～1
信息生存时间/s	5 000
消息产生时间/s	150～240
节点缓存队列大小/MB	20
节点传输距离/m	10
节点移动模型	地图最短路径