一种适用于空间容延迟网络的路由算法

于相声，孙晨华

(中国电子科技集团公司第五十四研究所，河北石家庄050081)

0 引言

2003年K.Fall［1］等科学家在ICIR上提出了延迟容忍网络(Delay Tolerant Network，DTN)的概念。这种网络主要泛指那些由于节点移动、能量受限等原因而频繁出现链路中断、甚至长时间处于分离状态的一类无线网络。卫星网络具有远距离无线通信的高时延、卫星间链路间歇性连通和信道传输数据率的不对称等特点，因此，卫星网络可被看作一种典型的 DTN 网络［2］。

本文针对卫星网络高延迟、高误码率和终端移动性的特点，提出了一种解决终端移动问题的路由算法SRM，该算法利用卫星节点的运动规律和终端节点的相遇概率，通过构造链接时序表和概率信息表，有效解决卫星网络的路由问题。

1 DTN路由研究现状

由于DTN网络的特点，路由问题一直是研究热点，从路由策略［3，4］方面来看，DTN 路由算法可以分为确定性路由［5，6］和随机性路由［7］两大类。

1．1 确定性路由

确定性路由假定节点将来的移动和连接是可预测的，也就是整个网络的拓扑结构是可以提前预知的。主要算法包括链接图路由［8－10］和时空路由。这类路由需要太多的网络知识(包括节点的移动规律、链接时序和网络拓扑等)。

1．1．1 链接图路由

链接图路由完全依赖于通信结点间链路的预先规划，而且每个结点都知道规划的详情。节点能够通过这些信息构造出一个链接信息图，节点通过链接信息图实现动态的路由查找。

1．1．2 时空路由

时空路由通过构建时空路由表，在当前和将来预期的邻居节点中选择下一跳节点，不同于传统的路由表，时空路由表使用目的节点位置和消息到达的时间来确定其下一跳节点。

1．2 随机性路由

随机性路由方案假定网络是动态的、不确定的，这类路由不需要太多的网络知识就能进行路由，但是它在网络中产生了太多的复制，容易占用网络资源。其中，传染式路由是具有代表性的多副本路由算法。

1．2．1 传染式路由

传染式路由［11，12］模仿生物环境中传染性病毒扩散传播方式，即每个被病毒传染的个体将把病毒传给与其接触的其他个体。传染性路由采用洪泛机制，每个节点存储所要转发的消息，直到网络中所有节点都收到此消息为止。

1．2．2 随机转发路由

在随机转发路由中，节点将数据包随机地发送给邻居节点，邻居节点再将数据包随机地发送给它的邻居节点，直到找到目的节点为止。这种算法最好的结果是数据包只经过一跳就到达了目的节点，最差的情况是数据包历经了网络中所有的节点后才到达目的节点。

本文的空间DTN拓扑是由1颗同步卫星、4颗低轨卫星、1颗空间飞行器、1个地面中心站、1个机载站以及1个船载站组成，在轨卫星可与空间飞行器、地面节点进行通信，近地轨道卫星链路会因为节点的运动而断开，网络切换频繁，同步卫星位于地球静止轨道，通信延时相对较大。空间飞行器与低轨有相似的轨道，既可以作为传输节点，又可以作为终端节点。机载站和船载站随机移动，没有固定的轨迹。网络拓扑如图1所示。

图1 空间DTN拓扑

上述路由算法中，确定性路由算法没有考虑到网络节点的随意移动性，随机性路由算法消耗大量的网络资源，不适应空间DTN的应用。

2 SRM算法设计

首先，计算卫星节点与随机节点间的报文递交概率，构建节点相遇概率信息表，查找出与随机节点相遇概率最大的卫星节点;然后由地面站周期性计算并分发全网卫星及固定节点连接时序图，网络节点利用该连接图构建网络拓扑路由表，并充分考虑网络中业务的实时性要求，采用时延作为链路权值。

2．1 节点相遇概率信息表

节点相遇概率主要指的是无规则移动节点和卫星节点间的相遇概率。显然，当节点相遇频繁时，相遇概率会随着时间不断地增大，反之会不断地减少，这能很好地体现节点之间的联系程度。通过此相遇概率可以大体估算出节点未来的相遇情况，从而为消息的转发提供依据。

当卫星节点与随机移动节点相遇时，首先对几个通信节点的节点相遇概率进行计算:

式中，r为中继节点;d为目标节点;β为一个常量。

如果在时间T内，某个节点没有与其他任何节点相遇并发生连接，那么报文递交概率进行衰减:

式中，γ 为衰老因子，γ∈(0，1)。

网络中每个卫星节点都有一份与随机节点的报文递交概率的表格，具体格式如表1所示。

表1 报文递交概率信息表

当与同步卫星接触时，卫星节点将报文递交概率的表格发送给同步卫星，同时同步卫星将搜集到的最新的各个传输节点到达随机移动节点的递交概率信息发送给各个卫星节点。

2．2 构建网络拓扑路由表

每个卫星结点内都存储了在整个时间轴上所有卫星结点及固定节点之间的链接信息。在搜索路径时，节点并不会搜索整个时间轴上的链接，为节省搜索算法的时间，结点动态地维护链接信息图，将搜索的链接对象尽量控制在消息生存期范围内。每个链接信息图包含如下信息:发送节点、接收节点、开始时间、结束时间和传输速率。

当大小为size的消息m抵达通信节点A后，查询其到达的目的节点D，并按顺序提出目的节点D的链接信息，具体搜索过程如图2所示。

图2 搜索过程示意

①如果C．st-size/rate大于当前时间，则跳过C，选择下一条链接信息。否则进行下一操作。

②如果C的传输节点E等于当前节点A:如果剩余链路容量小于size，则选择下一条链接信息;否则节点D就是信息m的下一跳节点，将A加入到可连接列表中，记录其当前的跳数及传输时间。

③如果C的传输节点E不等于当前节点A，将E加入排除列表中，并按顺序提出节点E的链接信息，重复进行①。

当搜寻到所有的可到达的链路后，从中选择延迟最小的链路进行传输，若延迟相同则选择跳数最小的链路。

3 路由算法仿真及性能分析

为了评价算法的性能，将SRM算法与现有的DTN算法进行了比较，比较对象选择了比较典型的Epidemic算法。为了比较路由策略，必须定义评价其性能参数。性能的评价要考虑很多因素，在此只讨论报文到达率和网络开销2个方面。

3．1 报文到达率

从丢包率可以反映出算法的报文到达率，在Epidemic算法中由于转发数据量过于庞大，而卫星的存储空间有限，导致很多数据被丢弃，因而造成了丢包。在SRM算法中丢包的原因主要是因为引进了概率性，数据包一直在网络中传递，直到生存周期结束。由于在仿真中将卫星的内存空间设置为无限大，因此Epidemic算法的到达率要略好于SRM算法，如图3所示。

图3 Epidemic与SRM算法的到达率对比

3．2 网络开销

网络开销可通过源端发送报文的数量和接收到的重复报文的数量以及报文被转发的次数进行比较，Epidemic算法基本上每个通信节点都进行了数据转发，在路由扩散过程中，引起的资源、缓存、带宽和能量消耗都比较大;而SRM算法在整个网络中只存在一个报文，网络开销要比Epidemic小得多。网络中信令的开销远远小于重复报文数量的开销，因此将信令开销忽略不计。SRM算法的网络开销近似一个常数，而Epidemic算法由于要在每个节点都要复制一次信息，因此最多的重复信息量可以达到原始数量的5倍左右，如图4所示。因此，SRM的网络开销要远远小于Epidemic。

图4 Epidemic与SRM算法的网络开销对比

4 结束语

本文提出了一种适应于空间DTN的路由算法，该算法通过计算概率信息和链路信息确定路由的下一跳节点，实现简单。通过理论分析和仿真测试表明，与Epidemic算法相比，SRM算法在报文到达率略小的情况下，有着更小的网络开销，能够更好地支持终端节点的移动性。

［1］ FALL Kevin Fall，FARRELL Steven．DTN:An Architectural Retrospective［J］．IEEE Journal on Selected Areas in Communications，2008，25(5):828 －836．

［2］ FALL Kevin．A Delay Tolerant Network Architecture for Challenged Internets［C］∥Proceedings of the 2003 Conference on Applications Technologies Architectures and Protocols for Computer Communications，ACM Press，2003:27－34．

［3］ 林 闯，董杨威，单志广．基于DTN的空间网络互联服务研究综述［J］．计算机研究与发展，2014，51(5):931－943．

［4］ 郭金鹏．运动网络使用DTN技术的分析与研究［J］．无线电通信技术，2012，38(6):77 －80．

［5］ 李 涛．容迟网络中的路由算法的研究及比较［J］．计算机与网络，2009(17):69－72．

［6］ JAIN S，FALL K，PATRA R．Routing in a Delay Tolerant Network［J］．Proc of the ACM SIGCOMM 2009．Communications Rev，2009，12(7):44 －52．

［7］ 祁 彦．容迟网络中的随机路由算法研究［J］．数据通信，2008(5):28－30．

［8］ SEGUI J，JENNINGS E，BURLEIGH S．Enhancing Contact Graph Routing for Delay Tolerant Space Networking［C］∥Global Telecommunications Conference(GLOBECOM 2011)，IEEE，2011:1 －6．

［9］ FARRELL S．Endpoint Discovery and Contact Graph Routing in Space and Terrestrial DTNs［C］∥Advanced Satellite Multimedia Systems Conference(asma)and the 11th signal processing for space communications workshop(spsc)，2010:89 －93．

［10］ CAINI C，FIRRINCIELI R．Application of Contact Graph Routing to LEO satellite DTN Communications［C］∥Communications(ICC)．2012 IEEE International Conference on．IEEE，2012:3 301 －3 305．

［11］ NAIN D，PETIGARA N，BALAKRISHNAN H．Integrated Routing and Storage for Messaging Applications in Mobile Ad Hoc Networks［J］．Mobile Networks and Applications，2004，9(6):595 －604．

［12］ BALASUBRAMANIAN A，LEVINE B N，VENKATARAMANI A．DTN Routing as a Resource Allocation Problem［J］．Computer Networks，2009，21(4):65－70．