卫星中断容忍网络路由算法研究*

杨　力，李富利，张　栋

（大连大学信息工程学院辽宁省通信与网络重点实验室，辽宁　大连　116622）



卫星中断容忍网络路由算法研究*

杨力，李富利，张栋

（大连大学信息工程学院辽宁省通信与网络重点实验室，辽宁大连116622）

摘要：针对卫星网络易中断、长时延等问题，提出一种适合卫星DTN网络的路由算法——SDTNR算法。该算法在节点缓存中设置了3个存放不同服务等级报文的队列，队列根据报文响应比排序，响应比小的报文优先发送。SDTNR算法根据卫星运行规律，建立节点选择表并实时更新该表，根据表中信息选择满足条件的节点作为下一跳节点，以此保证通信的可靠性。仿真结果表明，SDTNR与EPR、PR、FC 3种算法相比，SDTNR更好地提高了报文的投递率、降低了网络开销和平均时延。

关键词：中断容忍，长时延，路由算法，卫星网络

0　引言

DTN［1-2］是针对特定网络通信链路时断时续、网络拓扑动态变化、链路通信时延大等特性提出的，这些特性容易导致传统的路由协议难以应用。卫星网络具有长时延、易中断、链路不对称等特性，卫星网络属于一种特殊的DTN网络，即卫星中断容忍网络［3］，将DTN网络部分关键技术，特别是路由技术应用到卫星网络中将有利于解决卫星网络易中断等特性产生的问题。

目前主流DTN路由算法有以下几种：①感染路由（Epidemic Routing）算法［4］，其思想是节点间通过随机交换形式交换对方缓存中没有的报文，致使节点中含有其他节点缓存报文的副本，实现简单，但产生大量副本，造成网络资源消耗过快，使网络开销增大，且忽略了数据重要性；②基于概率的路由（Prophet Routing）算法［5］，该算法由Lindgren等人提出，思想是节点使用传输预测值作为传输概率，当节点之间再次相遇时更新概率值，并根据概率值判断是否转发报文，优点避免了报文的盲目传递，缺点使用预测值存在很大风险；③散发等待（Spray-and-Wait）路由算法［6］，该算法由Spyropoulos等人提出，该算法也是对感染路由算法的一种改进，该算法首次就使源节点携带报文的L个副本，并转发L/M个副本给相遇的节点，直到源节点只有一个副本，此时源节点要等待遇到目的节点时转发报文。优点降低了网络开销，缺点L、M值难以确定；④首次联系（First Contact）算法［7］，其思想是持有报文的节点将报文传输给最先遇到的节点，实现单拷贝，优点易实现，缺点是会造成时延增大。

上述算法优缺点鲜明，但是如果考虑直接应用到卫星中断容忍网络，由于它们没有结合卫星网络拓扑规律性等特性，将很难获得较好的性能，例如：报文投递率、网络开销比等。

针对上述问题，本文从缓存管理和节点选择环节入手，提出一种适合卫星DTN网络的路由算法—SDTNR算法，一方面，该算法在节点缓存中设置了3个存放不同服务等级报文的队列，每个队列根据报文响应比排序，响应比小的报文优先发送，这样能够降低网络中报文的平均时延并对报文进行有目的的转发，同时考虑到了卫星网络中数据的重要性；另一方面，SDTNR算法根据卫星运行轨迹的可预测性和连接的可见性，建立节点选择表并实时更新该表，根据表中信息选择满足条件的节点作为下一跳节点，以此限制了数据转发的盲目性、限制了报文副本数并保证了通信的可靠性。

1 SDTNR路由算法的设计

SDTNR算法主要包含缓存管理和节点选择两个方面，在缓存管理方面，该算法设置了3个低优先级到高优先级的缓存队列，分别存放3种不同服务等级报文，在不同的缓存队列中，根据报文响应比大小对报文排序，该响应比的计算充分考虑了报文的传输时延、发送时延、排序时延等因素。优先发送在网络中滞留时间长的报文，即响应比小的报文。同时为了体现传输数据的公平性，本算法采用了时间片轮转方法发送不同队列中的数据。在节点选择方面，本算法根据卫星网络中卫星运行轨迹可预测和连接可见性等特性，使每个节点维护一张选择表，该表包括下一跳节点、连接的开始时间、结束时间、持续时间和节点的空闲比，下一跳的节点必须是在通信范围内的节点，该表实时更新，根据该表的信息选择符合条件的节点，作为下一跳节点。

1.1缓存管理

SDTNR算法为每个节点缓存设置了3个就绪队列，分别放置高、中、低优先级的bundle（bundle是DTN网络中的数据单元，类似于网络中的报文）。高优先级对应服务等级为expedited的bundle，中优先级对应服务等级为normal的bundle，低优先级对应服务等级为bulk的bundle。这3个服务等级是由应用程序为每个待发送的bundle指定的［8］，为了在每个就绪队列中对相同服务等级的bundle进行排序，本算法设计了一种重新计算相同服务等级bundle的响应比。

1.1.1卫星之间距离的计算

在卫星网络中，卫星信道由星间链路组成，链路长度为通信链路距离之和。星间距离关系如图1所示。通过卫星间的瞬时地心角与轨道高度计算星间距离。瞬时地心角计算公式如下所示［9］：

（α1，β1）、（α2，β2）为两个卫星星下点的经纬度。

星间距离计算公式如下：

R为地球半径，H1是卫星A的高度，H2是卫星B的高度。将瞬时地心角代入星间距离计算公式，就可以算出两颗卫星间通信距离。

对于星地距离，SDTNR算法把H2设置为0，得出星地距离。

图1　卫星间距离示意图

链路长度之和的计算公式如下：

L1、L2…Ln分别表示报文经过各个链路的长度，其中n为正整数。

传输时延公式如下：

C表示光速。

Sttl表示报文生存时间，Rttl表示报文剩余时间，Qdelay表示报文滞留时延，该时延是排队时延、处理时延、发送时延之和。

1.1.2响应比计算

SDTNR算法中把传输时延和滞留时延之和称为报文的响应时间。该响应比计算公式如下：

Rp表示报文的响应比，响应比越小报文的权值越大。对于来自同一个源节点的报文，由于传输时延相同，则报文在网络中滞留时延越大，响应比越小，即报文的优先权越大，应及时转发出去，以减小时延；对于来自不同源节点的报文，则需要同时考虑传输时延和滞留时延。

而DTN网络在早期的设计中，受到了邮政服务的影响，按照报文的重要性分成了加急（expedited）、普通（normal）、大宗（bulk）3种优先级类型，加急类型的报文得到最高级的服务，普通类型的报文得到较可靠的服务，而大宗类型的报文得到尽力的服务，但是，这种服务类型的定义，只是针对同一源节点发送的报文设定的，这就意味着一个报文的服务优先级只能和同一源节点发送的报文相比较，即一个源节点发送的高服务优先级的报文可能并不比其他源节点发送的中优先级报文更快地发送出去。为了体现这一特性，SDTNR算法并不是优先发送加急队列中的报文，同时为了公平性，该算法给3个队列设置了不同的执行时间片，在优先级越高的队列中，规定执行时间片大一点，这主要考虑卫星网络中数据传输的主要性。本算法通过实验得出，最佳的执行时间片分别为90 s，60 s，30 s。

1.2节点选择

选择出响应比小的报文后，需要为该报文选择下一跳节点，SDTNR算法根据每个节点所建的节点选择表选择下一跳节点，该表包含的元素见表1。

表1　节点选择表的元素

节点选择表中下一跳节点必须是此刻进行通信的节点。开始时间、结束时间和持续时间是STK［10］软件中导出的数据。在卫星网络中，由于卫星的运行轨迹可以预测以及拓扑变化的规律性，因此，可以通过STK软件获得合适周期T内所有节点的可见时间。从STK中导出的某颗节点到其中一个节点的可见时间表见表2，仿真周期是24 h。

由表2可知，在整个仿真过程中，这两个节点的可见时间段有六次，每次持续时间都不同。SDTN算法通过可见时间表对路由表进行实时更新。每当两个节点进入彼此通信范围时，节点就会自动扫描所导出的可见时间表，添加下一个节点和它们连接的开始时间、结束时间以及持续时间。

表2　节点到某个节点的可见时间表

针对选择表中的空闲比，SDTNR算法借鉴了王占伟等人提出的一种空闲比计算方法［11］。空闲比是为了防止节点缓存已满，这时再向该节点发送bundle，节点会无法接受该bundle造成bundle的丢失，而提出的一种预防方法。空闲比的定义如下：

U表示已占用队列的长度，L表示总队列的长度。

本算法设置了空闲比的门限值β（β=0.25），若空闲比大于门限值，节点就接受报文；若空闲比小于门限值，节点就拒绝接受报文。

由选择表信息可知，在某一时刻可能存在源节点与目的节点不能通信的情况，可以通过其他节点作为中转站，由中转站节点把报文发送给目的节点，因此，需要选择较优的节点完成数据的发送。通信路径如图2所示。

图2　节点之间通信的路径

对于在通信范围内的节点，若此刻通信剩余时间大于滞留平均时延以及空闲比小于门限值，SDTNR算法选择满足该条件的节点作为下一跳节点。

2仿真与性能评价

2.1仿真平台与仿真环境

本文采用是ONE1.5仿真软件，这是一款专门为DTN网络所设计的软件。由于本软件不支持卫星网络，为了更好模拟卫星的运行，该文首先通过STK软件导出卫星的运行轨迹，再把运行轨迹的经纬度转化为平面地图中x，y轴上的数据，其次，在Open-JUMP中编辑和定义，最后，真实地显示出卫星在二维图中的运行轨迹。

本文设计了一个三层卫星模型，仿真模拟场景如图3所示，该场景包括一个高轨卫星（GEO）、两颗中轨卫星（MEO1、MEO2）、3颗低轨卫星（LEO1、LEO2、LEO3）、3个位于喀什、北京、拉萨的地面站。为了体现目的性，卫星是发送数据的源节点，地面站是接收数据的目的节点。卫星的运动模型是MapRoutMovement，地面站的运动模型设为StationaryMovement，卫星与卫星、卫星与地面站通过SimpleBrodcastInterface类型的HighSpeedInterface接口进行通信，而地面站之间通过btInterface接口进行通信。

图3　仿真模拟场景图

为了仿真网络场景，本文在ONE中设置了六类节点组，每层卫星是一个节点组，把3个地面站设置成一类节点组，每一组卫星参数设置相同，部分仿真参数见表3所示。

表3　部分仿真参数配置表

在相同卫星网络场景下，该文分别对感染路由算法（EPR）、基于概率的路由算法（PR）、首次联系路由算法（FC）和面向卫星DTN（SDDTR）路由算法进行仿真并对其性能作了对比分析。

2.1.1报文投递率分析

报文投递率指的是报文成功到达目的节点的数量与报文的总数量之比。定义如下：

报文投递率是衡量数据传输可靠性和算法性能最有效的评价指标。仿真结果如图4所示。

图4　不同算法报文投递率比较图

由图4可知，FC的报文投递率最低，因为FC中只有一个拷贝，在卫星DTN网络中，卫星的移动变化大，通信距离长，链路时断时续会易造成报文丢失，因此，一个拷贝的FC算法容易丢失报文，造成报文投递率过低。EPR算法和PR算法的报文投递率比FC算法的报文投递率要高，因为这两者的产生的报文拷贝较多。而EPR比PR的报文投递率高，因为在ERP算法中使用了全交换策略，提高了报文投递率。而本文提出的卫星DNT路由算法（SDTNR）则大大提高了报文的投递率，因为该算法增加了节点缓存管理功能，优先转发响应比小的报文，且概算法在下一跳节点选择方面，并不是仅仅选择一个节点，而是选择满足条件的多个节点，因此，提高了报文转发的成功率。

2.1.2平均时延的分析

在卫星DTN网络中，由于有大量的报文产生，因此，计算每个报文的时延没有意义，因此，在本仿真中，比较的是平均时延。图5是4种算法平均时延的比较图。

图5　不同算法平均时延比较图

由图可知，FC算法的平均时延最大，这是因为单拷贝降低了报文转发到目的节点的概率，增大了报文在网络中滞留时间。EPR算法的平均时延比PR算法的平均时延大，ERP产生大量副本，易阻塞网络引起链路中断，增到了报文的排队时延和传输时延。可以看出，SDTNR算法的平均时延小于其他3种算法，该算法优先转发响应比小的报文，降低了报文在网络中滞留的时间，因此，降低整个网络的时延。

2.1.3网络开销比

网络开销比是指在整个仿真过程中完成的总转发数减去成功到达目的节点的数据量之差与成功到达目的节点的数据量之比。定义如下：

ratio=（relayed-delivered）/delivered（9）relayed表示网络中中转的报文的次数。

网络开销比用来评价所设计的路由算法的总体传输性能。图6是不同路由算法的网络开销比较图。

图6　不同算网络开销比较图

由图可知，本文提出的SDTNR算法的网络开销比明显低于EPR算法和PR算法。首先，该算法通过选择满足条件的下一跳节点策略缓解了网络中冗余信息的转发次数；其次，在节点选择表考虑了节点空闲比缓解了网络拥塞，从而使用网络的开销比降低。

3　结论

本文针对现有路由算法直接应用于卫星网络存在的网络开销大、平均时延长等问题，提出一种适合卫星DTN网络的路由算法（SDTNR）。该算法与EPR、PR、FC算法相比提高了报文投递率、减小了平均时延、节约了网络开销比。因此，该路由算法应用到卫星中断容忍网络中会有很大的扩展性。

参考文献：

［1］FARRELL S，CAHILL V.Delay and disruption-tolerant networking［J］.Artech House，2006.

［2］CERF V，HOOKE A，TORGERSON L，et al.Delay-tolerant networking architecture［J］.IETF RFC，2007（4838）：89-95.

［3］王鹏宇.容迟网络（DTN）在天地一体化网络中的应用介绍［J］.电光系统，2012，12（4）：35-38.

［4］VAHDAT A，BECKER D.Epidemic routing for partially-connected ad hoc networks［R］.Technical Report Cs-2000-06，2006.

［5］LINDGREN A，DORIA A，SCHELEN O.Probabilistic routing in intermittently connected networks［C］//ACM SIGMOBILE Mobile Computing and Communication Review，2003.

［6］SPYROPOULOS，RAGHAVENDRA C S.Spray and wait:an efficient routing scheme for intermittently connected mobile networks［C］//Proc of the ACM SIGCOMM Workshop on Delay-Tolerant Networking，2009.

［7］SUSHANT J，KEVIN F，RABIN P.Routing in a delay tolerant Net Work［C］//ACM SIGCOMM，2004.

［8］SCOTT K，BURLEIGH S.RFC5050:Bundle protocol specification［R］.NASA Jet Propulsion Laboratory，2007.

［9］潘成胜，宣景鹏，魏德宾.卫星网络中基于BaseRTT计算的TCPVegas算法改进［J］.系统仿真学报，2012，24（5）：1254-1258.

［10］杨颖，王琦.STK在计算机仿真中的应用［M］.北京：国防工业出版社，2005.

［11］王占伟，王海涛，邹光南.面向空间容迟容断网络的路由算法研究［J］.航天器工程，2013（22）：62-66.

Research on Routing Algorithm of Satellite Delay-Tolerant Network

YANG Li，LI Fu-li，ZHANG Dong
（School of Information Engineering，Dalian University Key Laboratory of Communications Network and Information Processing，Dalian 116622，China）

Abstract：For the problems of interrupt、long delay in Satellite network，which proposes a routing algorithm which is suitable for Satellite DTN network--SDTNR algorithm is proposed.This algorithm set up three queues，each queue stores the packet of different service levels and sorts according to the ration of packet’s response，and meanwhile，this algorithm sends the packet whose ration of response is small preferentially.SDTNR algorithm based on the predictability of satellite set up node selection table and updated the table in real time，according to the information in the table to select several nodes which meet the conditions as the next hop node，in order to ensure the reliability of communication.The simulation results show that，SDTNR compared with EPR，PR，FC，which can greatly improve the packet delivery ratio，and reduces the network overhead and average delay.

Key words：disruption tolerant，long delay，routing algorithm，satellite network

作者简介：杨力（1982-），女，黑龙江佳木斯人，博士，教授。研究方向：空间信息网络传输技术、无线通信网络协议理论与方法。

*基金项目：国家“863”计划基金资助项目（2013AAXX04）

收稿日期：2015-03-15修回日期：2015-05-10

文章编号：1002-0640（2016）03-0057-05

中图分类号：TN915

文献标识码：A