基于时间聚合图的DTN网络最短时延路由算法

doi:10.11959/j.issn.1000-436x.2017228

通信学报 ›› 2017, Vol. 38 ›› Issue (Z1): 1-8.doi: 10.11959/j.issn.1000-436x.2017228

• 学术论文 • 下一篇

基于时间聚合图的DTN网络最短时延路由算法

王鹏,李红艳,张焘,李朋云

西安电子科技大学综合业务网理论及关键技术国家重点实验室，陕西西安 710071

出版日期:2017-10-01 发布日期:2018-06-07
作者简介:王鹏（1995-），男，河南济源人，西安电子科技大学硕士生，主要研究方向为空间信息网络。|李红艳（1966-），女，陕西西安人，博士，西安电子科技大学教授、博士生导师，主要研究方向为空间信息网络、无线网络、移动自组织网络。|张焘（1992-），男，福建三明人，西安电子科技大学博士生，主要研究方向为空间信息网络。|李朋云（1995-），女，河北保定人，西安电子科技大学硕士生，主要研究方向为空间信息网络。
基金资助:
国家重点研究发展计划基金资助项目(2016YFB0501004);国家自然科学基金资助项目(91638202);国家自然科学基金资助项目(91338115);国家自然科学基金资助项目(61231008);国家自然科学基金资助项目(61401326);国家自然科学基金资助项目(61571351);国家科技重大专项基金资助项目(2015ZX03002006);中央高校基础研究经费基金资助项目(WRYB142208);中央高校基础研究经费基金资助项目(JB140117);111计划基金资助项目(B08038);陕西省自然科学基础研究计划基金资助项目(2016JQ6054)

Minimum delay algorithm based on time aggregated graph in DTN network

Peng WANG,Hong-yan LI,Tao ZHANG,Peng-yun LI

State Key Laboratory of Integrated Service Networks,Xidian University,Xi’an 710071,China

Online:2017-10-01 Published:2018-06-07
Supported by:
The National Key Research and Development Program of China(2016YFB0501004);The National Natural Science Foundation of China(91638202);The National Natural Science Foundation of China(91338115);The National Natural Science Foundation of China(61231008);The National Natural Science Foundation of China(61401326);The National Natural Science Foundation of China(61571351);National S＆T Major Project(2015ZX03002006);The Fundamental Research Funds for the Central Universities(WRYB142208);The Fundamental Research Funds for the Central Universities(JB140117);111 Project(B08038);Natural Science Basic Research Plan in Shaanxi Province(2016JQ6054)

摘要/Abstract

摘要：

DTN(delay tolerant network)网络时变特征导致静态网络的路由算法无法求解该网络中给定业务的快速传输问题。时变路由算法CGR (contact graph routing)利用链路最早连通时段获得最短路径，由于连通时段先后顺序影响导致其算法链路利用率低下。针对该问题，对端到端最短路径的路由方法进行了研究，在时间聚合图中增加节点缓存时间序列表征同一链路不同时间段之间的联系，采用深度优先搜索从目的点向源节点反向找路，求解出已知业务需求端到端最短时延算法。用样例证明了算法的可行性。

关键词: DTN网络, 时间聚合图, 最短路径, CGR算法

Abstract:

The DTN network has the characteristics of dynamic topology change,thus the routing algorithm of static network can not solve the routing problem of time-varying network,and can not support fast transmission of given tasks.The existing time-variant routing algorithm CGR (contact graph routing) uses the earliest contact to obtain the shortest path,but because of the influence of the order of the connectivity period,the CGR algorithm has low link utilization.To solve this problem,the method of finding the shortest path was proposed.Besides,in order to characterize the relation between the different connect periods of the same link,the time series of node cache was added to the time aggregated graph.Based on this,the end-to-end multi-path shortest delay routing algorithm for the known task requirements was proposed.Finally,the feasibility of the algorithm was proved by an example.

Key words: DTN network, time aggregated graph, optimal path, CGR algorithm

中图分类号:

TN915.03

王鹏,李红艳,张焘,李朋云. 基于时间聚合图的DTN网络最短时延路由算法[J]. 通信学报, 2017, 38(Z1): 1-8.

Peng WANG,Hong-yan LI,Tao ZHANG,Peng-yun LI. Minimum delay algorithm based on time aggregated graph in DTN network[J]. Journal on Communications, 2017, 38(Z1): 1-8.

图/表 5

参考文献 9

[1]	FALL K , . A delay-tolerant network architecture for challenged internets[C]// 2003 Conference on Applications,Technologies,Architectures,and Protocols for Computer Communications. ACM, 2003: 27-34.
[2]	CHEN H , LOU W . On protecting end-to-end location privacy against local eavesdropper in wireless sensor networks[J]. Pervasive and Mobile Computing, 2015,16: 36-50.
[3]	SHAH S F A , ZAFAR M H , ANFONOVIC I ,et al. Hybrid routing scheme for vehicular delay tolerant networks[C]// Computer Science and Electronic Engineering (CEEC),IEEE, 2016: 158-163.
[4]	CAINI C , FIRRINCIELI R . DTN for LEO satellite communications[C]// International Conference on Personal Satellite Services. Springer Berlin Heidelberg, 2011: 186-198.
[5]	JAIN S , FALL K , PATRA R . Routing in a delay tolerant network[M]. ACM, 2004.
[6]	WERNER M . A dynamic routing concept for ATM-based satellite personal communication networks[J]. IEEE Journal on Selected Areas in Communications, 1997,15(8): 1636-1648.
[7]	GEORGE B , SANGHO K . Spatio-temporal networks:modeling and algorithms[M]. Springer Science ＆ Business Media, 2012.
[8]	SMITH D K . Network flows:theory,algorithms,and applications[J]. Journal of the Operational Research Society, 1994,45(11): 1340.
[9]	ARANITI G , BEZIRGIANNIDIS N , BIRRANE E ,et al. Contact graph routing in DTN space networks:overview,enhancements and performance[J]. IEEE Communications Magazine, 2015,53(3): 38-46.

基于时间聚合图的DTN网络最短时延路由算法

Minimum delay algorithm based on time aggregated graph in DTN network

在线阅读

PDF下载

可视化

被引次数

摘要/Abstract

引用本文

使用本文

图/表 5

参考文献 9

相关文章 8

Metrics

推荐阅读 0

[1]	兰巨龙,金子晋,孙鹏浩,江逸茗,王月. 基于可靠性的服务功能链构建算法[J]. 通信学报, 2019, 40(1): 64-70.
[2]	胡欣,宋航宇,刘帅军,李秀华,王卫东,汪春霆. 基于时间演进图的LEO星间切换实时预测及更新方法[J]. 通信学报, 2018, 39(10): 43-51.
[3]	马宪民,刘妮. 自适应视野的人工鱼群算法求解最短路径问题[J]. 通信学报, 2014, 35(1): 1-6.
[4]	陈业斌,李颖,郑啸,陈涛. 关于有向环网平均直径的研究[J]. 通信学报, 2013, 34(2): 138-146.
[5]	唐伟,郭伟. 无线传感器网络中能量高效的基站位置优选算法[J]. 通信学报, 2010, 31(9): 1-7.
[6]	聂仁灿,周冬明,赵东风,谭颖芳. 竞争型脉冲耦合神经网络及用于多约束QoS路由求解[J]. 通信学报, 2010, 31(1): 65-72.
[7]	饶育萍,林竞羽,侯德亭. 基于最短路径数的网络抗毁评价方法[J]. 通信学报, 2009, 30(4): 113-117.
[8]	李蔚,黄德修,刘德明,何军. 光网络中一种快速动态负荷均衡的波长路由算法[J]. 通信学报, 2005, 26(9): 60-67.