空间DTN网络CGR路由算法综述

张博文 ，姚秀娟

（1.中国科学院国家空间科学中心北京100190；2.中国科学院大学北京100049）

伴随着通信技术的发展，通信场景愈发丰富，出现了许多新兴网络，包括空间通信网络、传感器网络、移动车载网、战术通信网、乡村通信网络等。与传统网络环境相比，这些场景的网络环境有着时延大、传输误码率高、端到端连接状态不稳定等特点。2003年，IRTF（Internet Research Task Force）的下属组 织 DTNRG（Delay Tolerant Networking Research Group）提出了 DTN（Delay Tolerant Network）网络协议以解决此类问题[1]。DTN网络协议在传输层与应用层之间添加了捆绑层（Bundle Layer），并采用存储-转发的路由机制，通过将数据存储在当前节点等待的方式来应对网络中断问题[2-3]。

2008年，美国航空航天局NASA基于DTN网络提 出 了 CGR（Contact Graph Routing）路 由 算 法[4]。CGR路由算法利用空间网络节点的周期性，通过各传输节点已知的接触计划（Contact Plan）生成接触图（Contact Graph），再根据生成的接触图决定数据的传输路径。CGR路由算法因其占用存储资源和计算资源较少的优势，成为了空间网络通信领域的研究热点[5-7]。然而CGR路由算法在路径选择、计算传输时间等方面还存在着一些待改进的问题，仍有进一步优化的空间[8-11]。

文中将简要介绍CGR路由算法的实现原理以及CGR路由算法的优缺点。针对该算法存在的问题介绍和分析3种基于CGR路由算法做出的改进算法：ECGR路由算法、CGR-ETO路由算法以及CGREB路由算法。通过分析比较这3种改进算法的优缺点以及应用场景对这3种算法做出评估。最后对CGR路由算法的发展做出展望。

1 CGR路由算法

CGR路由算法是由美国航空航天局NASA喷气推进实验室针对空间通信网络具有周期性和确定性的特点所提出。该算法通过通信节点间链路的预先规划以及周期性，根据网络中各节点之间的接触计划生成接触图。当通信节点有消息发送时，CGR算法将分析这个接触图并计算出生成下一跳节点的集合，然后在集合中选择传输路径。当数据到达下一跳节点时，CGR算法将在下一跳节点继续运行这个流程[12-15]。与其他路由算法相比，CGR路由算法可以有效利用空间通信网络节点间的通信机会。

CGR路由算法的整体流程如图1所示。CGR算法首先通过接触计划生成接触图。接触计划信息分为两个部分，接触信息（Contact Message）与距离信息（Range Message）。接触信息用来描述给定时间间隔内两个节点间的数据传输速率。每个接触信息包含以下内容：开始UTC时间、终止UTC时间、发送节点、接收节点以及发送节点到接收节点的计划传输速率。距离信息用来描述给定时间间隔内两个节点间的距离。每个距离信息包含以下内容：开始UTC时间、终止UTC时间、发送节点、接收节点以及发送节点到接收节点的预期距离。

图1 CGR路由算法流程图

每个节点根据完整的接触计划建立自己的接触图数据结构，接触图在每个节点本地建立，并对每个其它节点建立两个链表xmit列表以及origin列表：xmit列表，每个列表包括接触开始时间，接触停止时间，发送节点号和数据传输速率，列表数据通过所有接收节点为节点的接触信息得到。xmit列表通过接触开始时间进行排序。origin列表，每个列表包括发送节点号与该节点到节点的当前距离，列表数据通过距离信息得到[16-17]。

一旦生成了接触图，CGR路由算法会分为两部分流程，分别为接触检查过程（CGR-CRP）和消息转发过程（CGR-FBP）。表1展示了这两个流程中所使用的变量。CRP的流程通过检查节点D的xmit列表中每一个接触信息m对接触信息m的开始时间、预计消耗容量等参数进行判定，如果参数符合要求则可将节点D加入到可转发节点列表中。表2列出了CGR-CRP流程的伪代码。

表1 CGR路由算法变量定义

可以看到，CGR-CRP流程的作用是得到能够转发数据包的邻居节点的集合，然后通过CGR最佳路径选择标准来选择路径并进行转发。如果是在地球轨道卫星通信环境，最佳路径选择标准应为数据包传输延迟最小路径。如果是在深空通信环境，通信机会远比几分钟或是几小时的传输延迟要重要得多，数据包要在自身生存时间内到达目的地，最佳路径应将最早失效时间作为路径选择标准，将接触效用最大化。

在结束CRP流程后，消息传输进入FBP流程。此时，可转发节点列表ProxNodes中的每个节点都是可以转发数据包的相邻节点，可通过其中一个节点将数据包向目的节点转发。表3列出了CGR-FBP流程的伪代码。完成了CRP和FBP流程后数据包将转发到下一节点，CGR路由算法将在下一跳节点继续运行整个流程。

表2 CGR-CRP伪代码

表3 CGR-FBP伪代码

通过上述的CGR路由算法流程可以看到，CGR路由算法是一种基于先验知识的DTN网络路由算法。这种路由算法在周期性应用场景中比其他类型的路由算法要更少地占用存储资源以及计算资源。但是，CGR路由算法仍有一些问题亟待解决，例如：在路径选择算法中并未考虑路由环路的情况；计算传输时间时未计入数据包的排队延迟；传输路径选择算法计算量较大。为此，出现了许多基于CGR路由算法的改进算法致力于对CGR路由算法做出进一步的优化。

2 CGR路由算法改进

2.1 ECGR路由算法

为了提升CGR路由算法的安全性，避免路由环路及路由震荡现象的发生，文献[18]在CGR路由算法的基础上提出了ECGR（Enhanced Contact Graph Routing）路由算法[18]。ECGR路由算法与CGR路由算法相比，主要作出了以下两点的改进：1）在深空通信场景下，将最佳路径选择标准由最早失效时间改为最早到达时间（Earliest Arrival Time）；2）在路径选择中使用Dijkstra最短路径算法。

CGR路由算法中并没有考虑到路由算法的安全性问题，由于CGR路由算法采用的路径选择标准是传输数据包的最早失效时间，而数据包的最早失效时间并不是单调递增或单调递减的度量单位，所以CGR路由算法可能会产生路由环路以及路由震荡的情况。在ECGR路由算法中用最早到达时间代替最早失效时间作为最佳路径选择标准正是因为最早到达时间为单调递减度量单位，能够保证不会产生路由环路以及路由震荡。此外，选择最早到达时间作为路径选择标准可以在路径选择过程中使用Dijkstra最短路径算法。使用Dijkstra最短路径算法可以有效地减少时间复杂度。根据文献，CGR路由算法的时间复杂度为O（V!），而ECGR路由算法的时间复杂度为O（VE+V2logV）。

ECGR路由算法解决了CGR路由算法中存在的路由算法安全性问题，有效阻止了路由环路以及路由震荡现象的发生。当前ECGR路由算法已经加入到CGR路由算法的最新方案中。

2.2 CGR-EB路由算法

文献[19]基于减少节点计算量的考虑提出了CGR-EB路由算法。CGR-EB路由算法在CGR路由算法的基础上增加了扩展块编排到数据包里[19-20]。

CGR-EB路由算法中将网络的路径信息作为扩展块编排到数据包里，在数据包的传输过程中节点根据扩展块信息对本地节点信息进行验证。如果信息没有发生变化，则不需要重新对消息转发路径进行计算，扩展块会被省略，节点处理数据包的方式与CGR路由算法中相同。只有当发现接触发生变化时节点才会重新计算路径。CGR-EB算法有效地在资源受限的环境中减少了路由路径选择计算的复杂度，从而减少了节点的计算量。

CGR-EB路由算法可以分为两个阶段，构造扩展块以及路径评估。构造扩展块阶段中，CGR-EB收集接触图中的数据包转发路径的数据，并将数据编码成为扩展块。表4列出了CGR-EB路由算法使用路由消息编码的扩展块信息。虽然接触的距离信息也是CGR路由算法中一个重要的考虑因素，但它不作为扩展块的一部分在网络中转发。路径评估阶段中，当一个节点接收到一个包含扩展块的转发消息时，它必须评估扩展块内容的有效性，然后决定是否承认该路径，以利于自己的路由计算。评估方法是通过比较增量误差与每个节点所配置的阈值。如果误差超过阈值，则节点上的接触与正在评估的特定属性的扩展块中编码的接触不匹配。

CGR-EB路由算法扩展块的信息验证流程总结如下：1）根据当前节点的接触计划检查下一节点的接触是否可靠。如果不可靠，则执行CGR路由算法中的路径选择流程生成新的路径，CGR扩展块更改为新的路径信息。2）如果接触可靠，则对传输速率、预计容量消耗等信息进行验证。同样，如果信息存在太大差异，则执行CGR路由算法中的路径选择流程生成新的路径，CGR扩展块更改为新的路径信息。将扩展块编排到数据包里的改进使CGR-EB路由算法可以很大限度的减少计算的复杂度，更好地应对通信网络环境中出现的异常状况。

表4 CGR-EB扩展块内容

2.3 CGR-ETO路由算法

文献[21]针对CGR路由算法提出了一种基于最早传输机会的接触图路由算法（Contact Graph RoutingEarliestTransmission Opportunity，CGRETO）[21]。在CGR路由算法中假设数据包在接触开始时立即发送，并没有将数据包传送的排队延迟计算在内，而是假定消息可以在接触的开始时刻立即发送。在CGR-ETO路由算法中，通过队列信息，为每次接触增加一个与优先级相关的ETO（Earliest Transmission Opportunity）参数从而更准确地计算数据包的传输时间。

ETO参数定义为按一定优先级转发数据包的最早可行时间，ETO参数与数据包的优先级相关，不同优先级的数据包对应不同的ETO参数。ETO参数的取值范围为开始接触时间到结束接触时间，不同优先级ETO参数的初始值都是开始接触时间。在接触图的遍历过程中，不同于CGR路由算法，CGR-ETO算法用ETO参数替代最早失效时间去计算最早到达时间。

当数据包在传输队列中等待时，CGR-ETO算法会计算数据包的预计容量消耗，通过预计容量消耗除以传输速率计算得到数据包的预计传输时间。然后将该数据包的预计传输时间作为排队延迟加到之前预计的ETO信息或当前时间上（以较晚者为准），所有等于或低于该数据包优先级的数据包ETO信息都会被更新。之后CGR-ETO路由算法会遍历接触计划使用ETO信息来决定最优的消息传输路径。

假如CGR-ETO算法在每次数据包转发时都修改接触计划中的排队延迟，将会对通信系统造成很大的计算成本。为了减少这种计算成本，CGR-ETO算法设置了接触计划更新阈值，阈值的表示方式为接触持续时间的百分比。例如，如果接触持续时间为1000 s，接触计划更新阈值设置为10%，则直到自上次计算以来ETO增加超过100秒本地节点才会重新计算最佳路线。

因为空间网络环境中数据的传输时间和传输速率有限，所以CGR路由算法在每次节点间接触所能传输的容量有限，存在接触超额预定的问题。文献[22]提出了基于CGR-ETO路由算法的超额预订管理（Overbooking Management）去解决CGR路由算法中接触超额预订的问题[22]。CGR路由算法在每次接触前会检查是否有足够的剩余容量，当转发较高优先级的数据包时，因为数据包优先级的关系，会故意忽略优先级较低的捆绑包。如果接触已经被低优先级数据包预订，这就会导致接触的超额预订。

CGR-ETO改进算法中有别于CGR路由算法计算剩余容量时仅考虑具有相同或更高级的数据包，而是不考虑数据包的优先级计算接触的总剩余容量，根据总剩余量大小，做出不同的数据包转发决策。如果接触的总剩余量为正数但小于预计容量消耗，属于部分超额预订。超额预订处理机制为从最低优先级队列中的最后一个数据包开始重新转发。如果接触的总剩余容量是负值，为全部超额预订。超额预订处理机制为从为接触计划的最后一个数据包开始重新转发。

2.4 改进算法应用场景比较与评估

通过上述3种改进算法的介绍，可以看到每种改进算法的侧重点有所不同。CGR-EB路由算法与ECGR路由算法相比，在传输的数据包中加入了扩展块，扩展块只有在每次消息转发路径需要更改时才会被调用用来帮助通信系统选择消息包转发的最优路径。通过引入扩展块，CGR-EB路由算法处理每个数据包所调用路径计算过程的次数降低，从而有效减少了每个通信节点对于转发路径选择的计算量。此外，在端到端延迟以及投递完成率这两个指标上，增加扩展块并不会带来什么明显的影响，CGREB路由算法与ECGR路由算法并没有较大差别。

在传输数据量较少的场景下CGR-ETO路由算法无法体现其优势。因为在数据量较少的情况下接触计划很少发生传输时间重叠的情况，从而很少出现排队延迟的情况。但随着通信网络中传输数据量的增大，接触计划产生重叠的频率也随之增加，此时CGR-ETO路由算法的端到端延迟情况会明显优于ECGR路由算法。此外，因为ECGR路由算法没有考虑数据传输的排队延迟无法充分利用通信链路，所以在通信网络中传输数据量较大的情况下，ECGR的投递完成率也不及CGR-ETO路由算法。然而CGR-ETO路由算法需要在每次转发过程中重新计算接触计划中的排队延迟，所以与ECGR路由算法相比CGR-ETO路由算法会给通信系统增加一定的计算量，具体增加的计算成本取决于不同场景下CGR-ETO路由算法设置的ETO参数更新阈值。

可以看到，CGR-ETO路由算法与CGR-EB路由算法较ECGR路由算法都有着更明确的应用方向。在通信网络节点计算能力有限的条件下，与另外两种路由算法相比CGR-EB路由算法将更加适合。当通信网络节点计算能力强的情况下，使用CGR-ETO路由算法的消息传输表现将会优于其他两种路由算法。

3 发展方向

CGR路由算法作为DTN网络路由算法的研究热点之一，在近些年也得到了长足的发展与进步。以上几种改进算法使CGR路由算法在安全性、计算量和时间预估等方面都有所改善。但目前CGR路由算法在拥塞控制以及算法的实际应用场景这两个方面还存在不足。下面将结合CGR路由算法的的特点，分析CGR路由算法在拥塞控制领域和应用场景仿真领域的发展。

1）路由算法中的拥塞控制方法

当前CGR路由算法还缺少对通信网络的拥塞控制。与其他通信网络环境相比，DTN网络环境节点存储空间以及计算能力有限，容易导致节点的剩余容量不足，从而影响到消息在网络中的路径选择以及通信效率。因此，在CGR路由算法中加入节点拥塞控制机制，例如为节点预留缓存空间、当节点资源将要用尽时优先传输优先级较高的数据包、将节点信息转发到资源较为充裕的其他节点上，从而避免通信网络发生拥塞。

2）真实应用场景仿真

当前的CGR路由算法研究大多建立于虚拟的太空通信场景中，研究的CGR路由算法改进算法缺少对现实应用场景的仿真。随着CGR路由算法研究的进一步深入，尝试对当前太空中真实的网络通信环境进行仿真，验证CGR路由算法在真实DTN通信网络中的效果以及可实施性，应当作为之后的研究重点之一。

4 结论

文中对CGR路由算法以及当前CGR路由算法的改进算法进行了分析和介绍，其中包括对路径选择做出改进使用最早到达时间替代最早失效时间的ECGR路由算法、考虑数据包排队延迟并且提出超额预订管理的CGR-ETO路由算法以及对路径消息进行编码生成扩展块的CGR-EB路由算法。在通信网络节点计算能力有限的条件下，CGR-EB路由算法优势较为明显。当通信网络节点计算能力强的情况下，GR-ETO路由算法的消息传输表现最佳。本文在对CGR路由算法发展现状做出总结的同时，也对该领域的未来发展方向进行了展望，指出CGR路由算法的拥塞控制以及在实际场景中的应用将会是未来的研究趋势。