基于动静结合方法的卫星网络路由方法研究*

邢 川，陈二虎，韩笑冬

0 引 言

近年来，低轨(LEO，low earth orbit)移动卫星星座组网成为卫星领域的热点，卫星网络的路由方法问题实现卫星组网的重要技术问题[1].相比于中高轨卫星，LEO卫星能够为用户提供更低时延的高速网络连接，然而低轨卫星星座的拓扑结构变化也更为频繁，使得其网络路由方法也相应较为复杂.受限于星间链路、星地链路有限的带宽、卫星有限的计算能力和数据存储能力的制约，卫星网络的特点区别于传统地面固定网络和无线通信网络，因此必须针对卫星网络的特点研究并设计新的路由方法[2].

对于LEO卫星星座来说，轨道和卫星排布是确定的，每颗卫星的环绕周期通常是固定的，因而其星座的拓扑结构随时间的变化是可预测的[3].因此传统的星间路由方法主要是根据卫星网络周期性的拓扑变化预先将路由信息包括路由表和转发表注入到卫星上，卫星节点按照时间进行相应的路由和转发，此类路由方法为静态配置类路由方法(简称静态方法)[4].当前地面网络常用的路由方法主要包括OSPF、AODV、ATM等方法[5]，这类型方法通常需要动态的进行信令的分发传递，获取实时的链路状态和节点状态，然后及时更新计算路由路径，此类方法为动态探测类路由方法(简称动态方法)[6].

在卫星网络中应用静态方法的弊端是无法适应突发的链路故障及网络结构变化.当某个卫星节点或某条卫星链路发生故障或通信流量变化造成链路拥塞时，继续根据原始拓扑结构规划路径可能会导致丢包或拥塞加重.动态方法的弊端则是消耗占用卫星网络大量的带宽，同时受收敛速度影响必然会造成一定程度的丢包[7].

本文将静态方法与动态方法进行了有效的结合，采用自协调的方法同时运行动态方法与静态方法.当星座实际拓扑符合预测时主要使用静态方法，同时对网络状态进行实时的探测，减少实时不断更新的计算工作.当探测到部分节点或链路发生的故障时，自动切换为动态方法，尽可能降低故障的影响.在故障消失或恢复后，动态方法可自动切换至静态方法，此方法可极大的加强传统卫星网络路由方法的可靠性，提高卫星的自主生存能力.

1 星座拓扑结构

在典型的极地轨道低轨星座网络模型中，星座内部卫星间的网络为点对点网络[8]，每个卫星有4个端口，分别与其他4～6个相邻卫星的卫星相邻，每个端口与唯一的邻居卫星建立双向连接通信[9].作为一个典型的网格状无向网络，网络部分拓扑可以抽象为如图1所示的结构.

图1 网络部分拓扑结构图Fig.1 Network topology frame

该类型网络对路由方法的基本要求是在运行正常时不因为路由算法丢包，在出现故障时能够自动进行规避.

2 静态路由方法

自协调路由方法中以基于快照的静态路由作为静态方法，当网络结构与快照相符时，静态方法快照按时序切换，在某幅快照时间内，路由表根据该快照所反映的网络拓扑计算得到.为了防止快照切换过于频繁及切换过程导致的丢包，本文提出一种快照序列构造及分割策略.

2.1 快照建立与切换

当星座内卫星的连接关系与当前时刻拓扑快照相同时，认为没有星间链路的故障，这时星座内采用静态路由方法.虽然网络随着卫星的运动而时刻发生变化，但一段时间内网络拓扑结构保持不变，且在网络不同周期内其拓扑结构是周期性的.静态路由方法利用星座结构的周期性变化特征，通过对卫星运行状态的仿真将单个系统周期进行“分片”，生成离散的有限可数的拓扑快照.将卫星构型发生变化的时刻定义为集合T=(t0,t1,…,tN)，其中每个时间代表一个拓扑变化的时刻，划分时间间隔[ti,tt+1]的依据是任意一条星间链路发生变化的时刻(连接或断开).在时间间隔内网络拓扑不发生变化，定义此时快照为Si，时间间隔[ti,ti+1]定义为有效时间间隔.在全周期内，网络的拓扑结构可以总结为一个快照序列S=(S0,S1,S2,…,SN).

图2 离散拓扑示意图Fig.2 Discrete-time topology sketch map

由于某些时段多个链路发生切换的时间间隔很小，例如在高纬地区异轨相邻卫星相对速度较大，往往规定纬度高于60°时异轨星间链路不连接，故当几个异轨卫星到达指定纬度时几乎同时发生链路断开.若仍以单条链路的变化划分快照可能会造成快照在短时间内发生多次快速切换，为了避免这种状况，应对有效时间间隔较小的几个快照进行合并.

以图3为例，Tk表示快照生存时间.当在T0到Tk中，相邻单幅快照之间只有一条链路发生变化，若不存在反复变化的链路(即各条链路最多只变化一次)，可以将这段时间的快照进行合并，保留T0时刻和时刻两幅快照作为快照N和N+2，到为过渡状态.过渡状态以第N和N+2幅快照作为依据，两幅之间有通断变化的链路在过渡状态快照中均强制设置为断，T0到T8之间始终不变的链路即保持其状态，从而保证不会因为快照合并和切换而发生丢包.以S[N]表示第N幅快照内所有连接链路，则上述规则可以表示为，

S[N+1]=S[N]∩S[N+2]

(1)

图3 快照合并示例Fig.3 Snapshot combination demonstration

此外，为了保证切换过程的可靠性，需要将切换时间特殊处理.以图3(b)为例，S[N]与S[N+1]快照在tp时刻发生切换，若某数据包在tp-Δt时刻发出(其中Δt≪t0)，tp时刻前未到达目的端.如果数据包恰好经过在tp时刻断开的链路，就会发生丢包.

过渡快照N+1的开始时间前移δa时间，同时结束时间后移δb时间.δa和δb的值可以根据数据包在网络中传输的最大时延确定.对于有M×N颗卫星(N个轨道面，每个轨道面上有M颗卫星)的星座来说，其网络半径R为信息在网络中传输的最大距离(跳数).

(4)

对应的端到端时延可以表示为，

DTmax=∑i,jDISLIJ+r·ts≈R·(DISL_average+TS)

(5)

其中，DISLIJ表示数据包在卫星i到卫星j间的传播时延，可以用其平均值DISL_average近似估算；TS为数据包在路由节点内的传输时延.不妨取δa=δb=DTmax，尽可能减少拓扑切换过程导致的丢包.

拓扑快照可以预置在星上非易失存储器中，也可以由地面站上注到卫星内存中，以节约星上存储资源.快照对应的路由表也可以采用事先预置的方式，或通过快照切换前在星上提前进行计算的方式节约存储空间.

2.2 静态路由计算

当系统内未出现链路故障时，快照只在ti(i∈T)时刻发生切换，并将在时间间隔内维持不变，在此时间间隔内的选路都遵循该拓扑快照及其对应的路由表.在快照有效时间内，路由问题可以看作是静态拓扑路由，从而有效简化路由问题.路由表使用最短路径算法Dijkstra计算得到，在时间段内的数据包都将根据这一时段事先计算的路由表进行转发.

3 动态路由方法

动态路由方法主用于解决星间链路出现异常故障的问题，此时链路实际连接状态与拓扑结构不符，继续使用静态路由方法会造成丢包.根据卫星的计算能力和传输能力，采用裁剪的OSPF协议实现动态路由方法.

动态路由方法依赖HELLO协议及LSA协议进行链路状态的探知和通知.在当前时刻已经确认正确的链路状态基础上进行链路状态的更新，依靠实时的HELLO探测及(相较于静态路由)更频繁的LSA洪泛在全网各卫星间同步当前网络拓扑状态.

3.1 链路探测机制

卫星之间需要短间隔周期性发送探测数据包(HELLO)，通过交换HELLO包确定可达的邻居路由器.当卫星某个端口收到来自其他卫星的HELLO时，该卫星将根据当前快照中对应的拓扑结构判断该HELLO包是否来自其相邻卫星，若是正常邻居卫星，且在对方应答的邻居表中填写自身ID，建立双向的连接关系，否则将丢弃该HELLO包.此外，HELLO协议还负责连接关系的维持.对于已经建立连接的卫星，当上次接收到邻居卫星的HELLO包超过一定时间间隔后，判定链路超时.HELLO包协议作为链路探测的基础协议，应当始终以较高的频次运行.

3.2 连接状态洪泛机制

为了保证星座中每个卫星都维护相同的连接状态，需在卫星间进行连接状态洪泛.卫星网络运行时，当某个卫星的链路发生变化或链路状态到达刷新时间，卫星向外发送一个反映当前自身连接链路状态的LSA(link state advertisement)数据包，用洪泛的方法向全网进行链路状态更新，最终保证整个卫星网络中所有卫星都能够得到该消息的一个副本.其他卫星收到最新的LSA时，若其中表示的连接信息与其自身所维护的连接状态数据库不同，就对数据库进行更新，从而保证每颗卫星都能同步维护相同的星座连接状态.

3.3 动态路由计算

每颗卫星再根据其连接状态数据库进行路由表的计算，以自身卫星为根节点，计算到网络内除自身以外的其他卫星所需要经过的最优路径，并将其存在路由表中.卫星利用Dijkstra最短路径算法自主进行路由表的动态计算，依照此时计算得到的路由表进行查表转发

4 动静结合方法

在静态路由阶段可以设置较低频次的LSA刷新策略，或仅当HELLO协议探测到链路状态变化时再进行LSA的洪泛，以减少静态路由阶段的网络开销.当系统进入动态路由时期后，需要各卫星节点以较高的频次进行LSA洪泛，以保证链路的变化能够在全网各个节点快速悉知.

4.1 动静切换逻辑

路由协议切换状态机示意如图4所示.

图4 系统状态转换图Fig.4 System state-transition graph

图中包含状态：

S0:路由停止状态

S1:静态路由状态1(使用原始快照进行路由计算)

S2:动态路由状态

S3:静态路由状态2(存在永久故障链路，根据修改后的快照进行路由表计算)

事件：

e01:系统开始运行时网络拓扑结构与快照相符

e03:系统开始运行时网络拓扑结构与快照不符

e13:连接状态与快照不符(至少一条链路故障)

e21:永久故障链路恢复，连接状态与快照相符?e31:链路故障恢复(故障计时器未超时)，连接状态与快照相符

e32:故障链路计时器超时，认为出现永久故障链路，连接状态与快照不符?

e_stop:系统停止运行

动作：

a13:开启链路故障计时器

a21:取消快照中永久故障标识，恢复原始快照

a31:关闭链路故障计时器

a32:在快照中给相应链路置永久故障标识

4.2 动静切换方法

系统在每次链路状态发生变化时，将其与当前时刻快照进行对比.当对比结果相同时，说明星座中没有故障链路或故障链路在当前时刻快照中应该是断开的链路，网络实际的拓扑与快照相符，这时系统采用静态路由策略.当通过HELLO协议探测到大于等于一条的链路发生故障时，连接状态与拓扑快照不符，该卫星由静态路由协议切换到动态路由协议，并将该连接状态变化的信息通过LSA泛洪到全网，全网所有卫星都将在其当前连接状态中记录链路临时故障，并切换到动态路由协议.当HELLO协议探测到故障链路恢复，由LSA广播至全网，且连接状态恢复到与当前时刻原定快照相同时，系统切换回静态路由协议.

4.3 异常状态处理

动态路由协议仍然基于当前(有故障标识的)连接状态计算路由表，每当连接状态发生变化时，需要重新计算路由表，以供当前时段的查表转发.当网络中存在故障链路时，由于存在拓扑变化导致的链路周期性断开/连接，一直使用动态路由会产生较大星上计算资源及信令开销，可能造成网络的拥塞和丢包.为了防止某条链路的长久故障造成系统一直处于动态路由的状态，当某些星间链路出现长期故障(HELLO协议无法探测到对方的时间超过规定时长)时，将在全周期所有快照中标记该链路为永久故障，并重新计算全周期各个快照对应的路由表，在永久故障恢复之前，全网使用基于新路由表的静态路由.待故障恢复后重新恢复无故障链路的原始静态路由，基于原始路由表进行状态转发.

5 仿真验证

本文采用EXata网络仿真软件对路由协议进行仿真验证.设置EXata使用的卫星模型为第1章所述模型如图5所示.

图5 卫星模型仿真场景Fig.5 Satellite model simulation scene

在模型上添加业务流测试路由方法运行的正确性，得出以下仿真结果：

路由方法运行状态业务丢包率卫星连接情况方法收敛时间无故障情况静态 0%全部正常连接0s链路故障情况动态2%～5%(在拓扑结构发生变化时丢包)除故障链路外正常连接1～5s

6 结 论

本文通过对的静态路由方法和动态路由方法的有机协调，从仿真结果看，在故障和正常情况下均能够正常的实现卫星网络的路由计算，有效提高了路由方法的鲁棒性和可靠性.

该路由方法可在各类通信、导航、遥感卫星需要使用路由算法时进行应用.