空间延迟/中断容忍网络路由算法性能评估

燕洪成，郭坚，张红军

中国空间技术研究院总体部，北京 100094



空间延迟/中断容忍网络路由算法性能评估

燕洪成*，郭坚，张红军

中国空间技术研究院总体部，北京 100094

文章主要针对空间延迟/中断容忍网络(Delay/disruption Tolerant Networks，DTN)路由算法的性能进行分析评估，为未来空间DTN路由技术的设计提供参考和建议。首先，从利用网络知识多少的角度，对目前提出的适用于空间DTN的路由算法进行了分析和比较；然后，在一个典型空间DTN场景下，通过设定不同的接触计划，从微观和宏观两个方面，对最早投递(Earliest Delivery，ED)、基于本地队列的最早投递(Earliest Delivery with Local Queue，EDLQ)、接触图路由(Contact Graph Routing，CGR)和基于最早传输机会的接触图路由(Contact Graph Routing Earliest Transmission Opportunity，CGR-ETO)几种典型空间DTN路由算法的性能进行了仿真评估；最后，对仿真评估结果进行了分析和总结，并对未来空间DTN路由算法的研究提出了建议。仿真结果表明，对于端到端延时和束投递完成率两项性能指标，ED性能最差，CGR次之，EDLQ和CGR-ETO的性能相当。

空间DTN；路由算法；最早投递；基于本地队列的最早投递；接触图路由；基于最早传

随着太空中航天器数量的增多，传统点到点通信方式的缺点越来越明显，只有将不同航天器与不同地面支持设施互联互通为一个天地一体的信息化网络，才能满足未来航天任务的数据传输需求[1-3]。

由于空间网络所处的太空环境比较恶劣，因此，空间网络具有不同于地面网络的特点，比如，空间网络中的链路通常具有延时大、带宽不对称、通信误码率高等特点，且由于天体遮挡等原因，链路并不是持续可用的；空间网络中网络节点的存储和通信等资源一般非常有限；空间网络一般不能保证时刻存在端到端路径。

空间网络具有的以上特点，对网络协议的设计带来了巨大的挑战。由于地面因特网一般假定源节点和目的节点之间存在端到端路径，节点之间延时不会太长，而且网络丢包率较小，因此地面因特网的网络协议并不适用于空间网络。

延迟/中断容忍网络(Delay/disruption Tolerant Networks，DTN)最初起源于NASA喷气推进实验室对行星际互联网的研究[4]，其通过采用一种新的端到端的覆盖层网络(Overlay Network)体系结构[5]，能够适应网络的大延时和链路间断特点，可以运行于不存在端到端路径的网络中。

由于DTN潜在的应用前景，美国、欧洲、日本相继开展了大量关于DTN的研究工作和演示试验[6]，应用范围涵盖深空任务[6]、激光通信[7]、国际空间站[6]、遥感科学任务[6,8]和中继通信[9]等领域。

空间数据系统咨询委员会(CCSDS)最早针对空间网络定义了一套空间通信协议规范(Space Communications Protocol Specification，SCPS)，然而，随着越来越多的新方法得以提出，CCSDS不再赞成使用SCPS，而是倾向于太阳系互联网(Solar System Internetwork，SSI)协议族[10]。SCPS中的网络协议、安全协议和文件协议都被CCSDS降级为历史文档状态，只有传输协议由于仍在商业应用中被采用才被CCSDS作为活动建议书维护。对于新的空间任务和研发，CCSDS强烈建议不要使用SCPS，而是应该参考SSI协议族(DTN和相关建议)[11]。目前，CCSDS专门成立了空间互联业务——DTN工作组，以推动DTN技术的标准化[10,12]。

中国早在2000年左右就提出了研究和建设天基综合信息网的设想[13]，并通过专项研究取得了显著成果。

未来的空间信息网络将包括遥感、导航、通信、深空探测、载人飞船，以及高空平台等各种系统，具有时空跨度大和网络节点分布稀疏等特点，网络拓扑一般非全连通，网络不能够保证节点间时刻存在端到端路径，从而形成一个典型的空间DTN(空间DTN在概念上侧重地球轨道空间网络，而行星际互联网则侧重深空网络)。DTN最初起源于对行星际互联网的研究，并繁荣于地面DTN的广泛应用[14]，DTN不仅适用于深空网络，同样适用于地球轨道空间网络[15-16]，对我国天地一体化信息网络的建设具有重要的启示作用[6-17]。

DTN为空间信息网络提供了一种端到端的网络传输服务，而这种端到端的网络传输服务需要依赖于路由技术来提供最优的传输路径，因此，路由技术是空间DTN数据传输功能的重要基础。目前，针对空间DTN路由算法性能评估的研究还较少，因此，文章主要针对空间DTN路由算法的性能进行分析比较和仿真评估，为未来空间DTN路由技术的设计提供参考。

1　空间DTN路由算法

路由算法是空间DTN数据传输功能的基础，由于空间DTN的链路断续可用，且不能保证时刻存在端到端路径，因此，传统网络的路由算法并不能适用于空间DTN，需要研究新的DTN路由算法。

由于空间DTN节点的运行轨迹是可预测的，因此，空间DTN的链路调度一般可以提前获得，即空间DTN的路由问题可以看作是确定链路调度的DTN路由问题。目前，研究人员针对移动通信卫星网络的路由问题进行了大量研究[18]，但这些路由算法均假定网络在任意时刻都存在端到端路径，因此，并不适用于空间DTN。针对DTN路由的研究主要集中在机会网络，确定链路调度的DTN路由算法相对较少[19]。

文献[20]针对确定的动态网络提出了演化图模型，并提出了不同优化目标的路径计算算法，王彦等[21]将演化图应用于采用指向性天线的导航星座星间网络的路由计算。文献[22]针对节点运动可预测网络提出一种空时路由框架，采用一种层次化的空时图模型和动态规划来计算消息的最短路径。文献[23]针对DTN、机会移动网络和社交网络等不同的动态网络，提出了一种统一的时变图模型，但仍然采用演化图的方法计算路径。文献[24]利用空间网络星座拓扑的规律性和可预见性，针对空间DTN提出了一种时间图路由。

以上路由算法均只考虑链路调度信息，未考虑网络的排队延时，因此其性能有限。在DTN中，消息传输的端到端延时主要包括等待链路可用延时、排队延时、发送延时和传播延时。排队延时虽然可能只占路径延时的小部分，但由于空间DTN链路通信机会有限，较大的排队延时可能会使消息错过当前可用连接机会，而只能等待下次连接机会，从而增大端到端延时。因此，在空间DTN的路由计算中应考虑消息的排队延时。

文献[25]在2004年美国计算机协会数据通信专业组国际会议(ACM SIGCOMM)上第一次提出了DTN的路由问题，并设计了一种改进的Dijkstra算法，并根据利用知识库的多少提出了不同的路由算法(见图1)，如首次接触(First Contact，FC)、最小预计延时(Minimum Estimated Delay，MED)、最早投递(Earliest Delivery，ED)、基于本地队列的最早投递(Earliest Delivery with Local Queue，EDLQ)、基于全网队列的最早投递(Earliest Delivery with All Queues，EDAQ)、线性规划(Linear Programming，LP)，这些算法利用的网络信息越来越多，性能也越来越好。LP虽能得到最优路径，但需要知道未来的流量需求，现实中较难实现。EDAQ需要利用全网队列信息，但由于DTN时延较大，获取的队列信息时效性较差；同时，向全网泛洪队列信息会带来大量的协议开销。

图1　利用不同网络知识路由算法的性能情况[25]Fig.1　Performance of routing algorithms using different amount of knowledge[25]

在2008年的太空运管(SpaceOps)会议上,文献[26]针对行星际互联网提出了接触图路由(Contact Graph Routing，CGR)。CGR利用已知的接触计划(Contact Plan)计算消息的转发路径，并通过消息的预计容量消耗(Estimated Capacity Consumption，ECC)和接触的残余容量(Residual Capacity，RC)考虑接触的容量限制，因此，其性能会比ED好，但它没有考虑网络的排队延时[27]。

文献[28]在2013年美国计算机学会挑战网络研讨会上针对CGR提出一种考虑全网队列的基于最早传输机会的接触图路由(Contact Graph Routing Earliest Transmission Opportunity，CGR-ETO)，并通过接触计划更新协议更新全网的队列信息。由于CGR假定消息可以在接触的开始时刻发送，而没有考虑排队延时，因此，CGR-ETO通过为每个接触增加一个优先级相关的ETO变量来考虑排队延时[29]。

目前，针对确定DTN提出的有代表性的路由算法利用网络知识的情况如表1所示，选取典型的ED、CGR、EDLQ和CGR-ETO四种路由算法，在一个典型空间DTN场景中对路由算法的性能进行评估。

表1　确定DTN路由算法利用网络知识情况比较

演化图路由、空时路由、ED路由均未考虑网络的排队延时，因此，路由计算结果一致，我们选取ED路由算法作比较。CGR通过消息的预计容量消耗和接触的残余容量考虑接触的容量限制，因此，其性能会比ED好，但其仍然没有考虑网络的排队延时。CGR-ETO考虑了全网的排队延时，但为了简化仿真，设定CGR-ETO仅考虑本地节点的排队延时，并使其与EDLQ进行比较。EDAQ与LP由于实现复杂度较高，因此不在本文的比较范围之内。

2　性能评估

选取图2所示的典型空间DTN场景对4种路由算法进行性能评估，其中，节点1表示航天器，为信源，节点2表示地面站1或中继卫星1，节点3表示地面站2或中继卫星2(由于中继卫星是透明转发，因此可以看作航天器直接与中继卫星的地面站相连)，节点4表示任务运行中心，为信宿[29]。节点1与节点2和节点3之间的通信链路用虚线表示表明这些链路是断续可用的，节点4与节点2和节点3之间的通信链路始终连通。图2所示的拓扑虽然简单，但代表了一个典型的地球轨道任务场景。

图2　典型空间DTN场景Fig.2　A typical space DTN scenario

在OPNET网络仿真软件中对图2所示的空间DTN场景进行了建模，并实现了ED、CGR、EDLQ和CGR-ETO四种路由算法。由于链路传播延时和通信误码率对路由算法的影响较小，而路由算法主要受链路断续连接的影响，因此，为降低仿真复杂度，假定所有通信链路的传播延时和通信误码率可以忽略不计，而主要评估路由算法在链路断续连接情况下的性能。

设定节点1产生数据，数据的优先级相同。路由算法的任务即在链路断续可用的情况下找出到达节点4的延时最优路径。路由算法在消息产生时或收到消息时做出路由转发决策，并将消息添加到邻节点对应的待发送队列中，例如节点1会为节点2和节点3维护两个待发送队列。若待发送队列对应的链路当前可用，即马上发送，若链路当前不可用，那么等待链路可用时发送。待发送队列采用先入先出机制。

假设束(束为DTN传输单位)的载荷大小为100 kbyte，且束的预计容量消耗(为实际占用的通信容量)为107.235 kbyte(由于束在下层协议会被分段，并增加其他协议头部，因此束的预计容量消耗会大于束的载荷大小)[29]。

接触计划的设定按照从简单到复杂的原则，从而逐渐显示出低级路由算法存在的问题和高级路由算法的优势。首先，在一个没有重叠的接触计划下评估四种路由算法的性能，在这个接触计划下，可以看出CGR的预计容量消耗和残余容量消耗所起的作用；然后，在一个较复杂的有重叠的接触计划下评估4种路由算法的性能，在这个接触计划下，可以看出考虑排队延时与不考虑排队延时的区别。路由性能的分析采用微观(Microscopic)和宏观(Macroscopic)相结合的方式，微观分析针对每个束进行，宏观分析主要分析路由算法的平均端到端延时和束投递完成率性能。

2.1无重叠的接触计划

表2为无重叠的接触计划及其链路特性，其中链路1-3有两次接触，接触容量同时也以能够发送的束的数量表示。

表2　无重叠的接触计划及链路特性

图3为接触计划无重叠时ED的性能。节点1一共产生了15个束，在图3的左侧用实心菱形表示。生成的束在什么时刻经由哪个中间节点(节点2还是节点3)最终投递到节点4用矩形表示，实心矩形表示经由节点2投递，虚心矩形表示经由节点3投递。链路1-2和链路1-3的接触在图3的底部表示。

由于ED路由算法没有考虑接触的容量限制，也没有考虑排队延时，因此，ED将产生的所有的束都通过链路1-3经由节点3发送到节点4。ED选择节点3的原因是因为仅考虑当前消息的话，通过链路1-3的接触1会最早投递当前消息。可以看出在经过链路1-3的两个接触后，ED仍然没有将产生的15个束投递完毕，而仅投递了7个束。尽管空间DTN的链路调度一般具有周期性，未投递的束可以继续等待链路1-3的下一次接触机会，但这大大增加了数据投递的延时，同时，对于通信带宽更大的链路1-2却没有利用。

接触计划无重叠时，CGR、EDLQ和CGR-ETO三种路由算法的性能相同，如图4所示。由于EDLQ和CGR-ETO均考虑了排队延时，因此其路由性能是最好的。CGR考虑了接触的容量限制，在接触计划没有重叠时，其性能与EDLQ和CGR-ETO相当。对于CGR，在为序号3的束计算路径时，由于链路1-3的接触1的残余容量已经不足以完成束的发送，CGR在进行路由计算时，将不再考虑链路1-3的接触1，因此，CGR会选择链路1-2来转发束3。在为束14计算路径时，由于链路1-2的接触的容量已经耗尽，CGR会选择链路1-3来转发束。

图3　接触计划无重叠时ED的性能Fig.3　Performance of ED under non-overlapping contact plan

图4　接触计划无重叠时CGR、EDLQ和CGR-ETO的性能Fig.4　Performance of CGR, EDLQ and CGR-ETO under non-overlapping contact plan

图5为接触计划无重叠时，不同路由算法的平均端到端延时性能。由于ED没有考虑排队延时，所以其平均端到端延时最大，CGR通过考虑接触容量限制，获得了与EDLQ和CGR-ETO相同的平均端到端延时性能。

图6为接触计划无重叠时，不同路由算法的束投递完成率性能随时间的变化情况。某时刻的束投递完成率为当前投递成功的束的数量与待投递的束的总数量之比。由于ED没有考虑排队延时，不能充分利用可用通信链路，因此，其束投递完成率最低，而其他三种路由算法的束投递完成率相同，且优于ED,在109 s时，将所有的束都投递成功。

图5　接触计划无重叠时路由算法的平均端到端延时Fig.5　Average end-to-end delay of routing algorithms under non-overlapping contact plan

图6　接触计划无重叠时路由算法的束投递完成率Fig.6　Bundle delivery completion ratio of routing algorithms under non-overlapping contact plan

2.2有重叠的接触计划

为了更进一步地评估不同路由算法的性能，选用表3所示有重叠的接触计划。

图7为ED在接触计划有重叠时的性能。由于较接触计划没有重叠时，链路1-3所有接触的容量总和增大，因此，ED一共投递了12个束，但仍然没有将产生的所有15个束投递成功。由于ED没有考虑接触的容量限制和排队延时，其始终选择通过链路1-3转发所有产生的束，而对于通信带宽更大的链路1-2，ED仍然没有利用。

表3　有重叠的接触计划及链路特性

图7　接触计划有重叠时ED的性能Fig.7　Performance of ED under overlapping contact

由于考虑了接触的容量限制，在接触计划有重叠时，CGR的路由性能较ED有一定提高，如图8所示。在链路1-3的接触1的容量耗尽后，CGR通过选择链路1-2的接触来完成束的转发，并在140 s内将产生的所有15个束投递成功。CGR将束1～8均通过链路1-3的接触1转发，这是因为CGR未考虑网络的排队延时，选择通过链路1-3转发仅仅是因为链路1-3接触1的开始时间早于链路1-2接触的开始时间。虽然CGR成功投递了产生的所有15个束，但束的投递顺序被打乱了，束1～4首先被投递，束5～7与束9～15同时被投递，束8最后被投递。实际上，束8可以通过链路1-2的接触被更早地投递。

图8　接触计划有重叠时CGR的性能Fig.8　Performance of CGR under overlapping contact plan

由于考虑了排队延时，EDLQ和CGR-ETO的路由性能最好，如图9所示。EDLQ在每次计算束的转发路径时，会考虑当前待发送队列中的数据，将发送完当前队列中数据所花费的时间考虑进束的最早投递时间。CGR-ETO每次决定一个束的转发路径并将其添加进对应待发送队列后，会为对应的接触更新ETO变量，从而考虑排队延时。从图9可以看出，EDLQ和CGR-ETO的投递顺序没有被打乱，且整体的投递时间更早。

图9　接触计划有重叠时EDLQ、CGR-ETO的性能Fig.9　Performance of EDLQ and CGR-ETO under overlapping contact plan

图10为接触计划有重叠时，不同路由算法的平均端到端延时性能。由于ED没有考虑排队延时，所以其平均端到端延时最大。CGR虽然考虑了接触容量限制，但仍然没有考虑排队延时，其平均端到端延时性能略差于EDLQ和CGR-ETO。

图11为接触计划有重叠时，不同路由算法的束投递完成率性能随时间的变化情况。由于ED没有考虑排队延时，不能充分利用可用通信链路，因此，其束投递完成率最低。CGR虽然考虑了接触容量限制，但仍然没有考虑排队延时，也不能充分利用通信链路，因此，其束投递完成率略差于EDLQ和CGR-ETO的束投递完成率。CGR在84 s时，将所有的束都投递成功，而EDLQ和CGR-ETO在76 s时即将所有束投递成功。

图10　接触计划有重叠时路由算法的平均端到端延时Fig.10　Average end-to-end delay of routing algorithms under overlapping contact plan

图11　接触计划有重叠时路由算法的束投递完成率Fig.11　Bundle delivery completion ratio of routing algorithms under overlapping contact plan

2.3讨论

从以上的仿真评估中可以看出，ED由于没有考虑排队延时和接触的容量限制，路由性能最差，具体体现在ED的平均端到端延时较大，以及束投递完成率较低。CGR由于考虑了接触的容量限制，在接触计划无重叠时的路由性能与EDLQ和CGR-ETO相当；但当接触计划有重叠时，由于没有考虑排队延时，CGR的路由性能不如EDLQ和CGR-ETO。从目前的仿真实例来看，EDLQ与CGR-ETO的路由性能相当，具体表现在它们的平均端到端延时较低，且束投递完成率较高。平均端到端延时较低可以使消息传输具有较高的实时性，而束投递完成率较高可以使消息传输的吞吐量较高。

对于图2所示的地球轨道网络，当节点1的航天器为一颗遥感卫星时，较高的路由性能可以带来如下好处：第一，较高的实时性可以使地面更早地获得遥感图像信息，这可以使地面决策人员更早地做出决策，争取宝贵的时间；第二，较高的吞吐量可以使地面获得更多的遥感图像信息，这可以使地面决策人员基于更多的信息做出更优的决策。

文献[25]根据利用网络知识的多少为DTN提出的不同路由算法对空间DTN路由算法的理论研究具有重要意义。由于实际实现路由算法时面临种种制约，因此，现实中的路由算法应该基于部分网络知识做出尽量优化的决策。CGR作为DTN软件实现——行星际覆盖网络(Interplanetary Overlay Network，ION)[30]采用的路由算法，是专门为实际实现而设计的，且已经在大量的在轨试验中验证了其有效性[6,31]。CGR-ETO作为ION目前最先进的路由算法，对于实际实现空间DTN具有重要的参考意义。

目前，针对空间DTN路由算法进行评估的网络场景均较简单，未来应该在较复杂的空间DTN场景中对路由算法进行更详尽的评估。同时，空间DTN的存储和通信资源较有限，网络拥塞不可避免，未来还应在空间DTN拥塞控制问题上进行进一步地研究。

3　结束语

未来的空间信息网络具有时空跨度大和网络节点分布稀疏等特点，从而形成一个典型的空间DTN，路由技术是空间DTN数据传输功能的重要基础，本文主要针对空间DTN路由算法的性能进行了分析评估。从仿真评估的结果可以看出，ED的路由性能最差，CGR的路由性能次之，EDLQ和CGR-ETO的路由性能相当。未来针对空间DTN路由算法的研究应该在更复杂的网络场景中进行，同时，需要关注空间DTN的拥塞控制问题。

References)

[1]沈荣骏. 中国天地一体化航天互联网构想[J]. 中国工程科学，2006，8(10)：19-30.

SHEN R J.Some thoughts of Chinese integrated spaceground network system[J]. Engineering Science，2006，8(10)：19-30 (in Chinese).

[2]闵士权. 中国天基综合信息网构想[J]. 航天器工程，2013，22(5)：1-14.

MIN S Q.An idea of China′s space-based integrated information network[J]. Spacecraft Engineering, 2013, 22(5): 1-14 (in Chinese).

[3]BURLEIGH S，CERF V G，CROWCROFT J，et al. Space for internet and internet for space[J]. Ad. Hoc. Networks，2014，23：80-86.

[4]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.

[5]CERF V，BURLEIGH S，HOOKE A，et al. Delay-tolerant networking architecture，RFC 4838[EB/OL]. (2007-04)[2015-09-16]. http:∥tools.ietf.org/html/rfc4838.

[6]燕洪成, 张庆君, 孙勇, 等. 延迟/中断容忍网络技术及其在行星际因特网中的应用[J]. 航天器工程, 2014, 23(2): 114-123.

YAN H C，ZHANG Q J，SUN Y，et al. Delay/disruption tolerant network and its application to interplanetary internet[J]. Spacecraft Engineering，2014，23(2)：114-123 (in Chinese).

[7]ISRAEL D，CORNWELL D. Disruption tolerant networking demonstrations over LLCD′s optical links[EB/OL].(2014-02)[2015-09-16]. http:∥www.ipnsig.org/wp-content/uploads/2014/02/LLCD-DTN-Demonstration-IPNSIG-Final.pdf.

[8]Space-Data Routers[EB/OL]. 2010[2015-09-16]. http:∥www.spacedatarouters.eu.

[9]SUZUKI K，INAGAWA S，LIPPINCOTT J，et al. JAXA-NASA interoperability demonstration for application of DTN under simulated rain attenuation[C]∥The 13th International Conference on Space Operations (SpaceOps 2014)，Pasadena，USA，May 5-9，2014：1-13.

[10]Consultative Committee for Space Data Systems (CCSDS). Solar system internetwork (SSI) architecture，CCSDS 730.1-G-1[R]. Washington：CCSDS，2014.

[11]Consultative Committee for Space Data Systems (CCSDS). [EB/OL][2015-09-16]. http:∥public.ccsds.org/publications/scps.html.

[12]Consultative Committee for Space Data Systems (CCSDS). Rationale，scenarios，and requirements for DTN in space，CCSDS 734.0-G-1[R]. Washington：CCSDS，2010.

[13]袁孝康. 天基综合信息网络构想[J]. 上海航天, 2001(1): 12-15.

YUAN X K.Architecture of space base synthetic information networks[J]. Aerospace Shanghai，2001(1)：12-15 (in Chinese).

[14]FALL K. A delay-tolerant network architecture for challenged internets[C]∥ACM SIGCOMM 2003，Karlsruhe，Germany，August 25-29，2003：27-34.

[15]CAINI C, CRUICKSHANK H, FARRELL S, et al. Delay and disruption-tolerant networking (DTN)：an alternative solution for future satellite networking applications[J]. Proceedings of the IEEE，2011，99(11)：1980-1997.

[16]APOLLONIO P，CAINI C. DTN LEO satellite communications through ground stations and GEO relays[C]∥The 5th International ICST Conference (PSATS 2013)，Toulouse，France，June 27-28，2013：1-12.

[17]林闯，董扬威，单志广. 基于DTN的空间网络互联服务研究综述[J]. 计算机研究与发展，2014，51(5)：931-943.

LIN C，DONG Y W，SHAN Z G. Research on space internetworking service based on DTN[J]. Research and Development，2014，51(5)：931-943 (in Chinese).

[18]卢勇，赵有健，孙富春，等. 卫星网络路由技术[J]. 软件学报，2014，25(5)：1085-1100.

LU Y, ZHAO Y J, SUN F C, et al. Routing techniques on satellite networks[J]. Journal of Software，2014，25(5)：1085-1100 (in Chinese).

[19]苏金树，胡乔林，赵宝康，等. 容延容断网络路由技术[J]. 软件学报，2010，21(1)：119-132.

SU J S，HU Q L，ZHAO B K，et al. Routing techniques on delay/disruption tolerant networks[J]. Journal of Software，2010，21(1)：119-132(in Chinese).

[20]FERREIRA A. Building a reference combinatorial model for MANETs[J]. IEEE Network，2004，18(5)：24-29.

[21]王彦，刘波，虞万荣，等. 基于演化图的导航星座星间路由算法[J]. 中国空间科学技术，2012，32(5)：76-83.

WANG Y，LIU B，YU W R，et al. Routing algorithm for navigation constellation based on evolving graph model[J]. Chinese Space Science and Technology，2012，32(5)：76-83 (in Chinese).

[22]MERUGU S，AMMAR M，ZEGURA E. Routing in space and time in networks with predictable mobility，GIT-CC-04-07[R]. Atlanta，USA：Georgia Institute of Technology，2004.

[23]CASTEIGTS A，FLOCCHINI P，QUATTROCIOCCHI W，et al. Time-varying graphs and dynamic networks[J]. International Journal of Parallel，Emergent and Distributed Systems，2012，27(5)：387-408.

[24]王占伟，王海涛，邹光南. 面向空间容迟容断网络的路由算法研究[J]. 航天器工程，2013，22(3)：62-66.

WANG Z W，WANG H T，ZOU G N. Analysis of routing algorithm for space delay/disruption tolerant network[J]. Spacecraft Engineering，2013，22(3)：62-66 (in Chinese).

[25]JAIN S，FALL K，PATRA R. Routing in a delay tolerant network[C]∥ACM SIGCOMM 2004, Portland, USA, August 30-September 3，2004：145-158.

[26]BURLEIGH S C. Dynamic routing for delay-tolerant networking in space flight operations[C]∥The 10th International Conference on Space Opereations (SpaceOps 2008)，Heidelberg，Germany，May 12，2008：1-9.

[27]BURLEIGH S. Contact graph routing, IRTF Internet-Draft, draft-burleigh-dtnrg-cgr-01[EB/OL].[2015-09-16].http:∥tools.ietf.org/html/draft-burleigh-dtnrg-cgr-01.

[28]BEZIRGIANNIDIS N，TSAPELI F. Towards flexibility and accuracy in space DTN communications[C]∥The 8th ACM MobiCom workshop on Challenged Networks (CHANTS′13)，Miami，USA，September 30，2013：43-48.

[29]BEZIRGIANNIDIS N，CAINI C，MONTENERO D D P，et al. Contact graph routing enhancements for delay tolerant space communications[C]∥7th Advanced Satellite Multimedia Systems Conference and the 13th Signal Processing for Space Communications Workshop (ASMS/SPSC)，Livorno，Italy，September 8-10，2014：17-23.

[30]Interplanetary Overlay Network (ION)[EB/OL]. (2015-5)[2015-09-16]. http:∥sourceforge.net/projects/ion-dtn.

[31]ARANITI G，BEZIRGIANNIDIS N，BIRRANE E，et al. Contact graph routing in DTN space networks: overview，enhancements and performance[J]. IEEE Communications Magazine，2015，35(3)：38-46.

(编辑：车晓玲、范真真)

Performanceevaluation of routing algorithms on space delay/disruption tolerant networks

YAN Hongcheng*，GUO Jian，ZHANG Hongjun

Institute of Spacecraft System Engineering, China Academy of Space Technology, Beijing 100094, China

Performance of routing algorithms on space delay/disruption tolerant networks (DTN) was evaluated to provide design reference and advices for future design of routing techniques on space DTN. Firstly, routing algorithms applicable to space DTN were analyzed and compared in aspect of utilization amount of network knowledege. Then, from microscopic and macroscopic aspects, four typical space DTN routing algorithms, which are earliest delivery(ED), earliest delivery with local queue(EDLQ), contact graph routing(CGR)and contact graph routing earliest transmission opportunity(CGR-ETO), were evaluated by simulations in a typical space DTN scenario with different contact plan configurations. Finally, evaluation results were analyzed and summarized, and future research issues about routing algorithms on space DTN were also discussed. Simulation results indicate that from aspects of end-to-end delay and bundle delivery completion ratio, the performance of CGR is better than ED while the performance of EDLQ and CGR-ETO are the same best.

space delay/disruption tolerant networks；routing algorithms；ED；EDLQ；CGR；CGR-ETO；performance evaluation

10.16708/j.cnki.1000-758X.2016.0038

2015-10-08；

2015-11-11；录用日期：2016-05-11；

时间：2016-07-1213:26:55

http:∥www.cnki.net/kcms/detail/11.1859.V.20160712.1326.007.html

国家自然科学基金(91438102)

燕洪成(1985-)，男，工程师，yanhc519@163.com，主要研究方向为航天器信息系统、空间信息网络

V44；TP393

A

http:∥zgkj.cast.cn

引用格式：燕洪成，郭坚，张红军. 空间延迟/中断容忍网络路由算法性能评估[J].中国空间科学技术, 2016,36(4)：38-46.

YANHC,GUOJ，ZHANGHJ.Performanceevaluationofroutingalgorithmsonspacedelay/disruptiontolerantnetworks[J].ChineseSpaceScienceandTechnology, 2016,36(4)：38-46(inChinese).

输机会的接触图路由；性能评估