天基信息网络低轨非对称路由协议研究

李伟明 张素娟 申景诗

（山东航天电子技术研究所，山东烟台 264670）

天基信息网络低轨非对称路由协议研究

李伟明 张素娟 申景诗

（山东航天电子技术研究所，山东烟台 264670）

天基信息网络中的低轨道（LEO）卫星因拓扑变化快、轨道周期短，存在较多的信息网络相关节点间的非对称链路。文章从路由表优化和特殊链路处理方案等方面进行研究，提出了一种基于分时的低轨卫星网络路由算法。以星间链路传输时延作为计算代价度量来判断路由选择的优劣，从链路检测、路由计算和数据转发等三部分对路由协议进行描述，并制定了低轨链路处理方案，可以有效地发现网络中的非对称链路，及时进行相应处理。最后，仿真对比分析结果表明，文章所提出的协议方案在非对称链路存在的情况下性能更为优越。

天基信息网络；分时路由；最短路径；路由协议

1 引言

随着载人航天器、人造卫星和空间探测器的快速发展，如何保证空间信息高效可靠的传输，是当前天基信息网络的重点。天基信息网络由多层卫星组成，其中，低轨道（LEO）卫星拓扑变化快、轨道周期短，存在较多的层内及层间非对称链路，而空间路由协议则是以上链路实现有效通信的基础，其优劣程度直接影响到路由算法和通信质量的性能。现有的卫星网络路由协议大都假定所有的星间链路为双向对称链路，但随着卫星网应用的不断更新和拓展，这种假设的合理性和可行性就明显出现问题。因此，研究非对称链路的路由协议，对实现低轨道卫星稳定通信具有实际工程意义。

目前，可根据对拓扑变化处理策略的不同将空间路由协议归纳为：拓扑结构固定化路由协议［1－3］、基于时空位置信息的路由协议［4－5］和基于切换技术的路由协议［6－8］。这些协议在对拓扑高速动态变化问题的解决策略、链路度量值、路径计算以及卫星失效处理等方面各有特点，其中，基于时空位置信息的路由协议相比于其余两类，可根据当前网络中承载业务的统计特性动态调整路由方案，实现全网资源的最佳分配，避免出现某些链路严重超载。而该类中的DTRA（Discrete Time based Routing Algorithm）协议［7］是可适用于多层IP卫星网络，在充分利用卫星网络运行的规律性、周期性和可预测性等固有特征的基础上，采用计算最短时延路径的方式，不仅能够保证单个时间段内的星上分组无环转发，而且可做到切实保证路由表切换时不产生路由环路。

为此，针对天基信息网络低轨道卫星所存在的非对称链路问题，本文提出了一种基于分时的网络非对称路由算法（A－DTRA），从链路检测、路由计算及数据转发等三部分对路由协议进行描述，并制定了非对称链路处理方案，可以有效地发现网络中的非对称链路，及时进行相应处理。最后，仿真对比分析结果表明，该协议方案在非对称链路存在的情况下性能更为优越，可为建设空间信息网络提供工程参考。

2 相关定义

在具体阐述DTRA协议前，先对协议内各参数进行如下定义：

使用ISLa→b表示卫星节点a和卫星节点b之间的星间链路（ISL），使用D（ISLa→b）来表示卫星节点a到卫星节点b之间的传输时延。卫星节点a与卫星节点b之间的多跳路径可表示为

式中：Qi表示数据分组在中间卫星节点i上的排队时延；Pi表示数据分组在该卫星节点上的处理时延。由于算法仅以ISL传输时延作为计算代价度量，因此可将Qi和Pi取为固定值D0，路径Ra→b上的总传输时延还可表示为

故在卫星节点a到卫星节点b的路径集合S（Ra→b）中，最短时延路径可定义为

针对卫星网络具有周期性及可预测性的特点，将卫星网络的运转周期预先分割成为若干等长的小的时间片，在每一个时间片内，分别对卫星网络链路状态进行检测。经过链路检测这一步骤后，相当于对网络的拓扑结构进行了离散化，拓扑结构成为一个静态的加权有向链路图Gk（权值设置为星间链路传输时延）。将Gk定义为卫星网络在时间片［tk，tk＋1］的有向虚拟拓扑图，并用以下的链表格式表示：＜a，b，D（ISLa→b），flag＞，其中a和b为直接相邻卫星，flag表示为卫星节点a到卫星节点b的链路状态标志，用以表明在路由通路上是否含有非对称链路。flag的默认值是0，表示链路是对称的。

定义起始路由表为等间隔的时间片内对应的有向虚拟拓扑图开展路由计算时产生的路由表［9］。该表是一个临时的数据结构，只在离线状态下进行路由计算时使用。卫星节点a的起始路由表由时间标签和各表项结构组成。时间标签表示以该时间点作为起始时间点的时间片对应的路由表。起始路由表的表项格式表示为

式中：卫星b在此作为目的端节点，t表示以t为起始时刻对应的路由表，为卫星节点a到卫星节点b的首选下一跳，D（Ra→b）表示卫星节点a到卫星节点b的最短传输时延，为卫星节点a到卫星节点b的次优路径下一跳。flag1代表首选下一跳的链路状态标志，flag2代表次优路径下一跳的链路状态标志。

简化星上路由表定义为卫星节点加载经过时间片合并处理后的路由表。使用简化星上路由表的目的是为了减小星上开销，其表项格式表示为

式中：flagt1，1，flagt1，2为卫星节点a到目的端卫星节点b在t1时间段的首选下一跳及次优路径下一跳的链路状态标志；flagt2，1，flagt2，2为卫星节点a到目的端卫星节点b在t2时间段的首选下一跳及次优路径下一跳的链路状态标志。tk表示在一个系统周期的时间内从tk到tk＋1的时间段中，当前的卫星节点a将首选下一跳Ntk，1a，b及次优路径下一跳Ntk，2a，b当作目的端卫星节点b的路由选择［10－11］。

切换路由表，定义为记录卫星节点a的起始路由表的切换时间，该表的表项结构表示为

式中：ttime代表路由表的切换时刻，表示卫星节点将当前路由表切换为以时间ttime为起始时间的时间片对应的路由表；nnumber代表切换后时间片的原始路由表编号，与时间片序号相对应。切换路由表是临时的数据结构，在计算星上路由表时使用［12］。

3 基于非对称链路的优化路由协议设计

路由计算分为起始路由表计算及星上路由表计算两部分。在执行起始路由表计算之前，可依据对ISL动态特性的分析，将星座周期提前划分，计算出每段时间片所对应的有向虚拟拓扑图，路由算法的计算代价以ISL传输时延作为度量标准。按照卫星网络的运行参数以及最终链路状态的检测结果，起始路由表算法可在每个有向虚拟拓扑图上，为所有卫星节点计算出该时间片内的起始路由表。之后由星上路由表算法遵循避免策略对起始路由表进行合并，生成简化的星上路由表［13－14］。其路由表计算步骤如下：

（1）采用Dijkstra算法计算路由路径的首选下一跳，之后计算出符合无环多路径约束条件下的下一跳集合，并且从集合中选择路径时延最短的卫星节点作为次优路径下一跳。若同时存在多个路径时延最短者，则优先选择逻辑编号较小的卫星节点。若次优路径下一跳的集合为空，则将次优路径下一跳设置为空。

（2）根据链路状态检测结果，若首选下一跳卫星节点为失效卫星，或是其链路状态标志flag1的值为－1，则将次优路径下一跳作为首选下一跳，并从次优路径下一跳的集合中重新选择次优路径下一跳，直至满足首选及次优路径下一跳的链路状态标志flag为0或1为止。

（3）完成起始路由表计算后，比较相邻时间片内路由表的内容以生成切换路由表。

（4）按照卫星网络拓扑结构变化的规律性，若在若干相邻时间片内卫星节点间的连接关系不变，而仅是星间链路的长度改变，则起始路由表的内容可能完全相同。故为降低星上存储开销，星上路由表计算算法首先对相邻卫星节点切换前后的起始路由表的内容进行比较，如连续若干时间片的起始路由表内容都相同，则将其合并成为同一时间段的简化星上路由表，而时间段的长度就等于这些相邻时间片长度之和。

（5）源端卫星节点仅须要按照当前的运行时间进行查找相应时间段对应的路由表，然后采用简化的星上路由表信息进行数据转发即可。

4 协议性能仿真分析

采用具有12颗卫星节点的网络作为低轨卫星网络仿真模型，分别分布在3个轨道平面上。卫星轨道高度设为780km，轨道面倾角为86.4°，网络运行周期为101min，偏心率为0。卫星网络域模型的链路连接关系如图1所示。

图1 卫星网络域模型的链路连接关系与路由开销（单位s）Fig.1 Link and routing overhead of satellite network zone model

将卫星网络的运行时间设置为7200s。卫星节点（0，1）与卫星节点（3，2）之间的平均路由跳数的仿真结果如图2所示，平均端到端时延仿真结果如图3所示。由图2可知，路由算法A－DTRA所建立的路由，其路由跳数的平均值为4跳。图3中的平均端到端时延稳定维持在100ms左右，与理论分析相同。

不同于现有的基于虚拟拓扑、覆盖区域划分或虚拟节点的路由算法，该算法利用最小路径计算原理，把动态网络拓扑结构划分成按时间段分割的一系列连续的静态拓扑结构，可利用局部状态信息，仅须要在时间的分割点更新路由表即可，在星上可进行实时计算，可较好地解决拥塞问题。

图2 平均路由跳数曲线Fig.2 Average number of hops curve

图3 平均端到端时延曲线Fig.3 Average end－to－end delay curve

5 结束语

本文以天基信息网络低轨道卫星内存在的非对称链路问题为背景，研究了一种基于分时的低轨卫星网络非对称路由算法。从链路检测、路由计算及数据转发等三部分对路由协议进行描述并制定了非对称链路情况处理方案，可有效地发现网络中的非对称链路并及时进行相应处理。仿真算例表明：在非对称链路情况下，本协议方案性能更为优越，可较好地避免拥塞问题。这种设计思想可以做进一步改进后推广到低中高跨层网络的非对称链路路由中。

（References）

［1］Chang H S，Kim B W，Lee C G，et al.FSA－based link assignment and routing in low－earth orbit satellite networks［J］.IEEE Transactions on Vehicular Technology，1998，47（3）：1037－1048

［2］Gounder V V，Prakash R，Abu Amara H.Routing in LEO－based Satellite Networks［C］／／IEEE Emerging Technologies Symposium on Wireless Communications and Systems.New York：IEEE，2000：221－226

［3］Werner M.A dynamic routing concept for ATM－based satellite personal communication networks［J］.IEEE Journal on Selected Areas in Communications，1997，15（8）：1636－1648

［4］Hashimoto Y，Sarikaya B.Design of IP－based routing in a LEO satellite network［C］／／Proceedings of Third International Workshop on Satellite－Based Information Services.California：WOSBIS，1998

［5］周云晖，孙富春，张钹.一种基于时隙划分的三层卫星网络QoS路由协议［J］.计算机学报，2006，29（10）：1813－1822.Zhou Yunhui，Sun Fuchun，Zhang Bo.A time－division QoS routing protocol for three－layered satellite networks［J］.Chinese Journal of Computers，2006，29（10）：1813－1822（in Chinese）

［6］Akyildiz I F，Ekici E，Bender M D.MLSR：a novel routing algorithm for multilayered satellite IP networks［J］.Networking，IEEE／ACM Transactions on，2002，10（3）：411－424

［7］Mao T Y.A multicast routing algorithm for LEO satellite networks［C］／／2009ETP International Conference on Future Computer and Communication.Wuhan：ETP，2009：94－96

［8］S Scott K，Burleigh S.Bundle protocol specification，IETF RFC5050［S］.Pasadena：NASA Jet Propulsion Laboratory，2007

［9］Lee J，Kang S.Satellite over Satellite（SOS）network：a novel architecture for satellite network［C］／／Proceedings of Nineteenth Annual Joint Conference of the IEEE Computer and Communications Societies.New York：IEEE，2000：315－321

［10］Liu C，Wu J.Destination－region－based local minimum aware geometric routing［C］／／IEEE Internatonal Conference on Digital Object Identifier.New York：IEEE，2007：127－131

［11］Henderson T R.Networking over next－generation satellite systems［D］.Berkeley：University of California，1999

［12］Vutukury S，Garcia J J.A simple approximation to minimum delay routing［J］.ACM SIFCOMM Computer Communication Review，1999，29（4）：227－238

［13］Sam J.Semantically routing queries in peer－to－peer networks［C］／／Proceedings of the International Workshop on Peer－to－Peer Computing.Berkeley：IPTPS，2002：152－160

［14］Bai J J，Lu X C，Lu Z X.Compact explicit multi－path routing for LEO satellite networks［C］／／Porceedings of IEEE Workshop on High Performance Switching and Routing.New York：IEEE，2005：296－301

（编辑：张小琳）

Research on Asymmetric Routing Protocol for LEO Satellite of Space－based Information Network

LI Weiming ZHANG Sujuan SHEN Jingshi
（Shandong Aerospace Electr－technology Institute，Yantai，Shandong 264670，China）

LEO satellites of space－based information network have the characteristics of rapid topology transforming，short orbital period，and more asymmetric links inside layers.This paper studies routing table optimization，special link solutions etc，and proposes a LEO satellite network routing algorithm based on time division.It determines the routing selection result according to inter－satellite link transmission delay，describes routing protocol in three aspects of link detection，routing calculation and data relay，and formulates the dealing scheme for LEO link，which can find out and deal with the asymmetry of the network effectively.Finally，the simulation result shows that the protocol scheme proposed by this paper is more effective in the condition of asymmetric link.

spatial information network；discrete time routing；shortest path；routing protocol

TN915

：ADOI：10.3969／j.issn.1673－8748.2016.01.011

2015－11－17；

：2016－01－11

国家高新技术研究发展计划（863计划）（2015AA7015087）

李伟明，男，博士，工程师，从事卫星编队控制及组网协议、通信与导航技术研究工作。Email：liweiming513＠163.com。