空间信息网络技术和方法作为空天地一体化研究的基础工作之一^[1]，研究空间段网络的组网技术对空间信息的快速分发具有重大意义，为地理监测等实际遥测应用提供了技术支撑^[2]。DTNRG组织提出了延迟可容忍性网络(delay-tolerant network，DTN)^[3]，以解决空间网络这类挑战网络的组网问题，并将此类延迟较大、网络拓扑经常变化的网络统称为DTN网络。

与地面DTN网络相比，空间DTN网络拥有以下显著特征^[4]：① 太空环境中存在宇宙空间背景噪声，卫星链路中存在着高误码率和时延过大；② 卫星的能量供给和处理能力、存储能力受限；③ 卫星拓扑结构频繁变化，但具有周期性的特性。这些特征为空间网络的路由带来了巨大的挑战。

目前，空间DTN网络路由根据实现机制分为动态路由协议、空间虚拟化路由、时间虚拟化路由^[5]。大量路由协议相继提出，如文献[6]提出了泛洪的Epidemic路由算法；文献[7]提出了一种基于概率的路由算法；文献[8]在IRTF草案中提出了CGR(contact graph routing)路由协议，目的在于通过引入可预测性与周期性，以解决空间DTN网络路由的问题；文献[9]提出了一种提高改进的CGR路由协议算法。

本文介绍了DTN网络中基于泛洪的Epidemic、基于估测的Prophet与基于接触信息的CGR的动态路由协议，分析了各路由协议的资源开销，并通过空间DTN网络路由仿真实验对上述路由协议进行了评估。仿真结果表明，CGR路由能精确地利用接触信息，在消息交付率、抵达延时和网络开销指标上表现优秀。

Epidemic路由^[6]是一种基于复制的路由算法。其基本思想是：源节点将消息的副本转发到每个相遇节点，收到消息副本的节点也同样将副本转发到它们的相遇节点，如此进行下去，消息最终被转发到目标节点。

Prophet算法^[7]基于“节点频繁访问一个地方，那么在未来一段时间很可能再次访问这个地方”这一观察，利用历史接触信息估计节点到其他节点的抵达预测值。抵达预测值表示将消息转发到目标节点的概率。当节点遇到其他节点，交换彼此携带的抵达预测值，只有在对方节点到目标节点的传输预测值大于自身到目标节点的传输预测值时，才向对方节点复制消息。

节点在本地预测表中存储自身与其他节点的抵达预测值，当节点 a和b相遇时，更新抵达预测值：

在两点没有相遇的时间里，抵达预测值随着时间的增长而衰减。衰减公式为：

Prophet路由根据上述规则更新计算抵达预测值，以在消息转发决策时使用。

CGR路由算法^[8]完全依赖于通信节点间链路的预先规划，而且假定每个节点都认知整体网络的规划详情。当节点执行消息发送时，本地节点根据预先规划的链路信息搜索消息转发路径。单条链路信息包括的元素见图 1。

图 1 链接信息包含的元素 Fig. 1 Elements in the Contact Information

图选项

从图 1可以看出，链接信息的元素除了常规的两端节点之外，还包括开始时间、结束时间和链路速率。在路径搜索时,利用这些元素判断路径的可行性。

与一般路由不同的是，CGR路由会递归计算出所有符合条件的备选路径，此做法的目的在于支持CGR草案中引入的重要消息(critical bundle)概念，重要消息会被本地节点转发在所有备选路径上；相反，普通消息则只转发到代价最低的路径上。

文献[10]将DTN网络的路由算法分为三类：零知识路由、部分知识路由和完整知识路由。Epidemic和Prophet属于零知识路由，CGR属于包含接触信息的部分知识路由。文献[10]指出，路由算法利用知识能更有效地执行消息转发。

在资源受限的卫星或在轨器上必须考虑运行协议所占用的资源开销，主要包括计算开销和存储开销。计算开销由路由的时间和空间复杂度决定，存储开销由消息占用的缓存决定。下文假定在消息有效期内，与消息相关的节点集合为E，链接集合为V。

Epidemic路由在做消息转发时，采用的策略是将节点自身携带的消息传递给邻居节点，无任何路径搜索或决策计算，可视作无计算开销。此路由算法会使得网络中引入多份网络副本，消息副本会转发给所有的相遇节点，存储开销为E。

Prophet路由中引入了抵达预测值，计算开销由预测值的更新计算构成。在Prophet的实现中，式(1)和式(3)的计算仅发生在节点相遇时刻，式(2)则在节点相遇和消息转发时均会执行计算。假定一定时间内消息转发数量为 N，平均单个消息的时间复杂度为O(V/N+E)。一般地，网络消息数量N远大于V，因此时间复杂度可简化为O(E)。在空间复杂度方面，抵达预测值的计算需维护预测值表，无多重迭代和循环，空间复杂度为O(E)。在存储开销方面，Prophet路由属多副本路由，将节点间的转发行为发生概率考虑为β(0 < β < 1)，存储开销为βE+1。

CGR路由转发消息时递归计算所有可能的路径，验证所有链接信息排列组合，计算复杂度为O(V!)。CGR路由需使用节点和链接信息，因此空间复杂度为O(V+E)。CGR中普通消息副本数为1，存储开销为1；重要消息副本数与计算所得路径数量相关，视作βE+1(0 < β < 1)。

CGR的原作者在文献[9]中提出引入Dijkstra算法以减少时间复杂度。此方法使用多次Dijkstra算法搜索路径至邻居节点，本地节点再从这些邻居节点中进行筛选。文献[11]给出应用Dijkstra算法的CGR路由时间复杂度为O(VE+V²logV)。空间复杂度方面，单次Dijkstra算法需保存节点信息和链接信息，其空间复杂度为O(V+E)，而再次执行Dijkstra算法时并不需再次申请空间，因此空间复杂度为O(V+E)。

所有路由算法的资源开销见表 1，表中CGR的开销值为转发普通消息时的情形。

根据上述分析，Epidemic和Prophet路由无需计算路径，网络规模的增长对计算复杂度的影响较小，但存储资源消耗较高。CGR算法由于需计算完整路径，在计算消耗上较大，通过改进的路径计算方法，能将时间复杂度降低至可接受的范围内。另一方面，单副本特性使得CGR路由拥有较低的存储开销和通信开销。

本文选用了SAVI (http://savi.sourceforge.net/)+ ONE^[12]软件进行空间DTN网络路由仿真。SAVI软件用于构架卫星网络拓扑，并产生卫星网络中的节点间链接信息，然后导入到ONE软件中进行路由算法仿真。

网络拓扑包括一个地面站、一颗同步轨道卫星(geosynchronous orbit,GEO)和两颗低轨卫星(low earth orbiter,LEO)，拓扑中三颗卫星的轨道参数见表 2，地面站选择北京。ONE软件的运行过程见图 2。

图 2 ONE仿真环境 Fig. 2 ONE Simulator

图选项

在此网络场景下进行路由仿真，对Epidemic、Prophet和CGR三种路由在消息抵达率、平均时延和网络开销比方面进行了对比。在仿真中，所有消息均为普通消息，CGR仅作单副本转发。

消息抵达率是指在消息生存期内，网络中成功传输到目标节点的消息数量与所有产生消息的总数比值。

图 3反映了Epidemic、Prophet和CGR中节点不同的缓冲区大小对消息传输抵达率的影响。由图 3可以看出：①随着节点缓冲区大小的增加，各路由的抵达率上升；②在缓冲区有限时，CGR路由的抵达率明显高于其他两种路由，说明CGR路由在节点缓存资源的利用上优于Epidemic和Prophet路由。

图 3 各种路由算法的平均投递率 Fig. 3 Average Delivery Ratio of Different Routing Algorithms

图选项

消息抵达平均延时定义为所有成功抵达的消息从源节点产生到抵达目的节点所经历的平均时间。图 4反映了Epidemic、Prophet和CGR在节点不同缓冲区大小条件下平均端到端延时的变化情况。由图 4可以看出：①随着节点缓冲区大小的增加，端到端的平均延时上升。这是因为随着缓冲区增大，消息抵达率上升，多跳传输成功的消息比重增加，拉大了延时平均值；② Prophet路由的平均延时较大，CGR路由的延时表现与Epidemic相近，表明了盲目投递的Epidemic和精确搜索路径的CGR均能迅捷地利用链路进行消息转发，而Prophet路由的抵达率的预测机制效果较差。

图 4 各种路由协议平均延时 Fig. 4 Average Delay of Different Routing Algorithms

图选项

网络开销比定义为消息中继次数与成功递交次数的比值，能够大致地反映出路由的网络开销(包括节点消息缓冲区、网络带宽等)。网络开销比越小，路由所消耗的通信资源和缓存资源越少。

图 5反映了Epidemic、Prophet和CGR在节点不同缓冲区大小条件下网络开销的变化情况。由图 5可以看出：①随着节点缓冲区大小的增加，路由开销不断增大，但当缓冲区为无穷大时，Epidemic和Prophet的开销比急剧减少。这是因为当节点缓存较小时，新入队的消息将旧消息排挤出缓存，使得消息转发陷入接收→丢弃→再次接收→再次丢弃的循环，产生了大量的无效中继。然而当缓存无限大时，节点缓存一直保留消息，避免了消息的多次重复接收，无效中继次数大大降低。② CGR路由开销几乎没有变化，一直保持约0.6，Epidemic和Prophet则远大于CGR,表明了单副本策略的CGR路由算法的网络开销比明显低于其他两种路由。

图 5 各种路由协议开销比 Fig. 5 Average Overhead Ratio of Different Routing Algorithms

图选项

本文在ONE平台对Epidemic、Prophet和CGR进行了路由仿真实验。实验结果表明，由于CGR路由表现更为优秀，消息抵达率较高，对节点缓存消耗较小，消息抵达的平均延时较低。在缓存与链路容量有限的情况下，CGR路由协议在消息抵达率方面表现出极大的优势。总的来说，CGR路由适合在链路可预测的空间DTN网络中进行部署。