导航星座抗毁路由方法与技术研究

易先清,罗雪山,李健杰,汤邵勋

(国防科技大学五院信息系统工程重点实验室,湖南长沙410073)

0 引 言

北斗二代导航系统具有分期建设、局部覆盖到全球覆盖、满足不同应用及性能需求等特点,星座组网结构包括同步星座、高轨星座、中轨星座的复合组网。对于由多个星层组成的二代导航卫星网络,其结构相对单层星座复杂,特别是各星层之间的相对移动为星座的设计/建设与运行/管理带来了极大的挑战,其中基于多层星座结构的二代导航系统路由问题是其中亟待解决的关键问题之一。

在北斗二代导航系统中,需要传输的信息包括星座控制信息(包括单星控制信息和星座组网运行控制信息)、星座状态信息(包括单星状态反馈信息和星座组网运行状态反馈信息)、用户应用信息(包括导航定位信息、授时信息、短报文通信相关信息等)、感知报告信息(包括双向授时相关信息、位置报告信息、目标侦测信息)等,为了有效传输这些不同类型的信息,必须设计出合理的二代导航系统路由策略,研究正是从导航系统中各组成星座的组成结构与运行特点,特别是导航系统中卫星节点失效对其信息传输的影响出发,进行北斗二代导航星座抗毁路由研究。

研究包括如下三个部分:1)在基于我国初步设计的北斗二代导航星座系统组网结构[15]的基础上,给出基于此结构的导航星座抗毁路由所需定义,2)分析并给出基于此结构的导航星座抗毁路由算法,3)进行分析与总结。

1 基于GEO/M EO组网的二代导航星座抗毁结构与定义

分析卫星网络的组网结构是研究二代导航系统通信路由的基础,根据我国初步设计的北斗二代导航星座系统组网结构,设计基于此星座组网结构的抗毁路由方法与算法。我国北斗二代导航星座系统由同步静止轨道星座GEO(高轨星座HEO)、中轨星座MEO、倾斜轨星座IGSO、地面监控网节点站组成。IGSO星座的运行方式与MEO星座类似、而且IGSO星座每条轨道上仅有一颗卫星,为简化问题描述、突出研究重点,在接下来的讨论中将IGSO星座与MEO星座划分为一类进行讨论。在同轨星座、邻轨星座以及GEO星座与MEO星座之间、GEO星座和MEO星座与地面监控站节点之间设计通信链路,定义如下:

1)同步静止轨道星座(简称GEO星层)

GEO星层中的GEO卫星均匀分布在赤道上空的地球同步轨道面上,设GEO星层由NG(NG≥5)颗GEO卫星Gi((i=1,2,L,NG)组成。

2)中轨星座(MEO星层)

MEO星层由星座中所有MEO卫星组成,并按Walker星座形式组织,提供包括极地区域的全球性通信覆盖。设MEO星层由 NM×MM颗MEO卫星Mi,j(i=1,…,NM;j=1,………,MM)组成,其中NM是MEO星层轨道面数,MM为均匀分布在一个轨道面上的卫星数。

3)地面监控节点TS

地面监控节点 TS(Terrestrial)由分布在地球表面某固定位置的地面用户接收终端设备组成,提供强大的信息处理与收发能力,被GEO星层或MEO星层所覆盖。设地面监控节点由 TSw座地面监控节点TSi(i=1,2,L,TSw)组成。

基于北斗二代导航星座系统组网结构,进行如下路由描述所需定义,以满足其抗毁路由分析需求:

定义1(分群与群管理者GH(x)):设X为某GEO卫星Gi通信覆盖域AGi下的一个MEO物理分群,AG i下对应的MEO逻辑分群定义为X′,显然有X⊂X′,设 x为群X 中卫星,x′为群X′中卫星。GEO卫星Gi便作为群X 和X′中的群管理者,定义为GH(x)。

定义 2(群首 H(x)):定义 H(x)为 X群群首,根据分群时刻群X中距离GEO卫星Gi由近至远,依次分为首选群首 H0(x),第1备份群首H1(x),第2备份群首 H2(x),…,第S(X)-1备份群首HS(X)-1(x),这里S()是计算物理群X大小的函数,该函数只统计群中MEO类型的成员。

首选群首H0(x)为X群中分群时刻距离Gi最近的MEO卫星,满足

定义3(链路延时函数D(lx′→y))设x′、y分别为二代导航星座系统中各通信节点直接连接的通信链路(只经过一跳)两端的信源节点和信宿节点,定义 lx′→y为两通信节点 x′、y间的直连链路,其延时函数D(lx′→y)定义如下

定义4(链路延时报告LDR)链路延时报告LDR包括MEO星座延时报告MLDR和GEO星座延时报告GLDR。设x′为MEO星座的某MEO卫星,MEO星座延时报告MLDR(x′)定义为一组二元值{y,D(lx′→y)},其中 y是x′与y间通信链路的目的节点,可以是地面监控节点 TG(TG:Terrestrial Gateway)或MEO卫星Mi,j或GEO卫星Gi,关于MEO星座的链路延时报告 MLDR(x′)由下式描述:

设x为GEO星座的某GEO卫星,GEO星座延时报告GLDR(x)定义为一组二元值{y,D(lx→y)},其中y是x与y间通信链路的目的节点,可以是地面监控节点 TG或MEO卫星 Mi,j或GEO卫星 Gi,关于 GEO星座的链路延时报告GLDR(x)由下式描述:

定义5(群链路延时报告 GroupLDR(X′)与网络链路延时报告 NetLDR)在以某GEO卫星xG为群管理者的分群中,其群链路延时报告包括群管理者收集的链路延时报告GLDR(xG)和其覆盖域下MEO星座中的所有MEO成员 xM的链路延时报告MLDR(xM),其中分为逻辑群X′链路延时报告GroupLDR(X′)和物理群X链路延时报告GroupLDR(X),分别定义如下:

定义6(路径Ps→d)定义路径Ps→d为二代导航星座系统中源节点s至目的节点d间的最短延时路径 。设 N 路径 Ps→d上的节点数 ,则路径 Ps→d定义为

定义7(路由表计算者RTC(x))路由表计算的群管理者GH(x)或群首H0(x)或备份群首 Hi(x)统称为针对该逻辑分群 X′的路由表计算者RTC(x)。定义如下

定义8(静态初始路由表SORT)SOR T根据二代导航星座系统中卫星轨道的可预测特性和卫星运行的周期性和当时的网络状态为整个二代导航星座系统各路径Ps→d预先计算所得,以引导数据包按计划路径传输。定义逻辑分群X′路由子表SOR T(X′)和全网路由表SORT如下

定义9(动态真实路由表D TRT)全网各群X′同时以分布式异步生成其动态真实路由表DTRT(X′),各群 DTRT(X′)交换合并形成全网动态真实路由表DTRT。逻辑分群X′路由子表DTRT(X′)和全网路由表DTRT定义如下

2 抗毁路由方法与算法设计

为了有效传输二代导航星座系统中不同类型的各类信息,设计的基于北斗二代导航星座系统组网结构的抗毁路由算法DRRA基于双层星座、分群管理、群首备份、链路冗余、链路修补的组网结构和管理模式,具有数据包路由抗毁、数据包路由拥塞回避、数据包路由最短延时等特点。

基于二代导航星座系统组网结构的抗毁路由算法DRRA实现过程主要通过两大步骤来完成,首先建立静态初始路由表SORT,然后在SORT的基础上增量建立动态真实路由表DTRT。

建立静态初始路由表SORT。为了减少网上冗余信息,路由表计算者RTC(x)首先根据导航星座卫星轨道的可预测特性和卫星运行的周期性,针对每一快照周期 Ts内收集的运行状态信息,在系统T周期开始时为整个二代导航星座系统中各路径Ps→d预先计算针对各快照周期的静态初始路由表SOR T,并按信源节点s归属分别存储在对应群的各路由表计算者RTC(x)中。

建立动态真实路由表DTRT。在二代导航星座系统实际运行的过程中,在每一快照周期Ts开始时或在某事件触发启动路由表更新时,各群的路由表计算者RTC(x)分别从静态初始路由表SORT中抽取、复制对应群成员的路由信息,再根据其收集到的来自全网各通信节点的当前状态信息,利用信息增量修正IIM方法,进行增量修正,建立反映二代导航星座系统实际运行状态的基于逻辑群X′的动态真实路由表DTRT(X′),最后通过交换复合,形成整个二代导航星座系统的动态真实路由表DTRT中。并将DTRT(X′)分发至对应群的各成员中。

在二代导航星座系统抗毁路由算法 DRRA中,链路状态更新主要分成两大类型:周期性更新和事件触发更新。

2.1 信息增量修正IIM方法

根据采用快照周期和事件触发两种方式启动路由表更新,信息增量修正IIM方法也设计了周期性修正与触发性修正两种方法:

一种是在二代导航星座系统组网拓扑结构未发生预料之内的变化时,基于快照周期 Ts的周期性修正:在本系统通信网络两次快照周期Ts之间,若无通信节点或链路失效,各通信节点间的互连关系保持不变(基于“快照”认为不变,实际连续变化),但链路流量负载的变化以及因卫星移动引起的链路长度变化都将导致链路延时的动态变化,此时信息增量修正IIM方法主要是从相应群的SORT(X′)中提取、复制针对该快照周期 Ts的SORT(X′),并对发生链路延时变化的邻接节点根据路由表计算者RTC(x)计算新路由信息进行针对性的修正。

另一种情况是在二代导航星座系统组网拓扑结构发生预料之内的变化时,基于随机事件的触发性修正:在二代导航星座系统运行的过程中,若网络中通信节点或链路失效,其网络拓扑结构将随之发生变化。通过监视检测网络中的这种通信节点或链路失效,以此随即触发二代导航星座系统中的路由表更新。此时信息增量修正IIM方法从相应群的SORT(X′)中提取、复制基于当前快照周期Ts的SORT(X′),对因网络中通信节点或链路失效引起的路由表计算者RTC(x)计算进行引导,通知RTC(x)只对受通信节点或链路失效影响的相关节点进行路由的重计算,并将重计算的路由信息更新到提取的基于当前快照周期 Ts的SOR T(X′)中,生成新的相关群的动态真实路由表DTRT(X′)。这样可以使计算出的路径不再经过失效节点和链路,以便适应新的网络结构。

进行基于信息增量修正IIM方法的路由表更新时,以每个快照周期 Ts内的静态初始路由表SORT为基础,由路由表计算者RTC(x)从SORT中抽取复制建立本快照周期 Ts的属于本群的SORT(X′),然后逐项搜索 SORT(X′)中每一表项,并根据收集/交换得到的(7)式定义的全网状态信息报告NetLDR检查表项中路径Ps→d上的每一链路lx→y状态情况,若发生变化,RTC(x)采用一种称为Bellman的分布式异步最短路由算法,启动针对路径Ps→d源节点s和目的节点d的路由重计算。对于上述第一种情况,将新路径与原路径不同的链路lx→y更新到SROT(X′)中;对于上述第二种情况,则分别将新路径与原路径不同的链路lx→y更新到SORT 和SORT(X′)中。

抗毁路由算法DRRA的实施由延时报告生成、延时报告交换、路由表计算三个过程组成。

2.2 延时报告生成

在二代导航星座系统运行的过程中,路由表计算者RTC(x)再根据系统各通信节点在当前快照周期收集到的状态信息,利用信息增量修正IIM方法,在静态初始路由表SORT路由信息的基础上,抽取、复制、修正,建立反映二代导航星座系统实际运行状态的基于群 X′的动态真实路由表DTRT(X′),最后通过交换复合,形成整个二代导航星座系统的动态真实路由表DTRT中,包括准备、初始化、延时测量、延时报告生成、延时发送等过程。

2.3 延时报告交换

群管理者GH(x)形成所属群X′完整的群链路延时报告GroupLDR(X′)后,便开始在各群 X′间相互交换、复合各自形成的这些群链路延时报告GroupLDR(X′),以获取整个二代导航星座系统拓扑结构的全部状态信息NetLDR。

虽然延时报告的交换主要发生诸群群管理者GH(x)之间,但根据群管理者GH(x)失效与否,延时报告交换包含以下四种情况:

1)当二代导航星座系统中GEO星座无GEO卫星失效时,延时报告交换发生在GEO星座中诸卫星之间。

2)当二代导航星座系统中GEO星座存在失效卫星(设Gi-1)时,延时报告交换发生在GEO星座中诸正常卫星和GEO失效卫星管理群群首卫星H0(xi-1)之间。

在二代导航星座系统运行的过程中,因某种原因致使GEO星座中某GEO卫星Gi-1失效时,或因某种特定需求需要GEO星座中某GEO卫星Gi-1关闭时,延时报告交换发生GEO星座中正常工作的GEO卫星与失效卫星Gi-1原管理群群首H0(xi-1)之间。为了降低延时报告交换过程中失效的GEO卫星Gi-1对MEO星座产生的压力,待失效卫星Gi-1原管理群群首H0(xi-1)在MEO星座中完成收集群链路延时报告后,按最短延时路径通过多跳星间链路 ISLMEO↔MEO转发至Gi和Gi-2所管理群群首H0(xi)和H0(xi-2),再由相应群首通过单跳星际链路IOLMEO↔GEO传递至相邻群群管理者GH0(xi)和GH0(xi-2),如图1所示。待各正常工作的GEO卫星形成完整的整个系统网络的链路延时总报告 NetLDR后,再通过逆向星际链路 IOLGEO↔MEO将该 NetLDR 转发至H0(xi-1),完成整个二代导航星座系统存在GEO卫星失效情况下的链路延时总交换。

图1 GEO同步星座各星间延时报告交换

3)当二代导航星座系统中GEO星座中诸卫星全部失效时,延时报告交换只发生在MEO星座不同群的群首之间。

在二代导航星座系统运行的过程中,因某种原因致使GEO星座中所有GEO卫星失效时,或应某种特定需求需要GEO星座中所有GEO卫星关闭时,MEO星座中各分群群首H(x)并不将形成的链路延时报告MLDR(X′)向原群管理者GH(x)传递,而是向MEO星座中与其左右相邻的逻辑群群首按最短延时路径通过星间链路ISLMEO↔MEO进行多跳转发,即延时报告交换只发生在MEO星座中各群群首H(x)之间。

4)当二代导航星座系统中GEO星座与MEO独立工作时,延时报告交换分别发生在GEO星座中各卫星和MEO星座中不同群群首之间。

在二代导航星座系统分期建设的过程中,或在上述二代导航星座系统运行过程中应某种需求需要GEO星座与MEO星座独立运行时,各星座独立进行延时报告交换,其中GEO星座的延时报告交换按上述1)中描述的步骤进行,MEO星座的延时报告交换按上述3)中描述的步骤进行。

2.4 路由表计算

在二代导航星座系统中,为了降低路由表计算过程中对二代导航星座系统资源的占用率,和提高路由表计算者进行路由决策时的计算效率[11],采用群中集中与群间分布计算相结合的方法进行整个系统通信网络路由表的计算与重计算,具体为:按逻辑分群由群中路由表计算者RTC(x)进行群内各节点成员路由表的统一集中计算,各不同群由各自的路由表计算者R TC(x)采用分布异步的方式分别计算各群(成员)的路由表。当二代导航星座系统各星座协同工作时,网络路由表计算主要由充当群管理者的卫星GH(x)或 H0(x)完成;在GEO星座卫星全部失效或两星座独立运行时,各星座的路由表计算由各星座独立完成,其中MEO星座路由表计算由其中充当群首的MEO卫星H0(x)完成。

计算过程主要包括如下两种情况:

1)当二代导航星座系统中GEO星座与MEO星座协同工作时,由路由表计算者RTC(x)分别为其管理群计算全系统范围内的路由表SORT和DTRT;

2)在GEO星座卫星全部失效或两星座独立运行时,各星座的路由表DTRT计算由各星座独立完成。

针对基于GEO/MEO双层星座联合组网的二代导航星座系统,在建设初期或根据网络运行需求需要两星座独立运行时,或在GEO星座卫星全部失效时,各星座的路由表的重计算由各星座独立完成。其中GEO星座路由表计算简单,各GEO卫星分别收集状态信息并交换后调用Bellman算法进行路由重计算。而MEO星座路由表计算则仍按分群模式管理,由其群首H0(x)充当群管理者完成路由重计算。

3 抗毁路由算法性能分析与总结

下面主要从算法的星上计算开销/存储开销和链路通信资源开销的角度比较分析其实施复杂性。文献[19]详细讨论了算法的星上计算开销/星上存储开销以及链路通信资源开销。

3.1 星上计算开销/星上存储开销

为了简明分析,设m,n分别为二代导航星座系统中GEO和MEO星座中GEO和MEO卫星数。

通过前面对二代导航星座系统抗毁路由算法DRRA的设计描述可知,该算法的复杂性主要体现在全网链路状态NetLDR更新的复杂性和路径Ps→d计算的复杂性上,通过文献[19]分析其复杂性为O(m2+m×n+n),而已有星上路由算法如SGRP、MLSR的计算复杂性为O(m2×n2),星上全分布式路由算法FDIS(Full Distributed)的计算复杂性为O((m+n)2)。与其它星上路由机制相比,由于抗毁路由算法充分利用了分层二代导航星座系统的结构特点,其星上计算开销和星上存储开销主要由指定的具有较强星上处理能力的群管理者GEO卫星和与群管理者最近的群首MEO卫星承担,而普通卫星节点的星上开销非常低,且路由表计算者RTC(x)利用信息增量修正IIM方法只对发生状态变化的节点重计算路由,未发生状态变化的节点路由仅从SORT中抽取复制得到,并将状态变化持久有效(如节点或链路失效)形成的新路由记录至SORT中以备后用,因此单节点路由计算的复杂度较其它相关算法要低,因此该算法能够较好地适用于基于分层的二代导航星座系统环境。

3.2 链路通信资源开销

在基于多个星座的二代导航星座系统结构中,各通信节点间的链路通信资源开销也是衡量其组网结构和路由算法的一项重要指标。二代导航星座系统链路通信资源开销与星座规模、路由更新周期、链路状态更新机制等因素相关。提出的二代导航星座系统抗毁路由算法DRRA中,其链路状态更新机制充分利用了GEO卫星通信覆盖域与MEO星座之间的覆盖关系和各星座的运行特点,通过分群来实现分布与集中相结合的路由更新策略,使服务路由更新的链路状态延时报告首先通过各分布群群中各成员x′收集,然后同期汇集到各群群首H0(x),再通过各分布群的群首H0(x)传送至相应群管理者GH(x),各群管理者GH(x)再全面交换形成路由计算所需的全网链路延时总报告NetLDR,从而降低网络中传送的总链路状态通告数目。

4 结 论

提出了一种适应二代导航星座系统组网结构的抗毁路由算法DRRA,与其它星上路由机制相比,该算法具有计算复杂度相对较低、存储容量相对较小、支持卫星节点失效运行的特点和功能。这主要基于:

1)二代导航星座系统中通信节点间链路冗余设计方案;

2)二代导航星座系统中通信节点失效时间隔失效节点视距范围内次相邻节点链路修补方案;

3)MEO星座分群群首失效时采用群首选择备份机制;

4)二代导航星座系统中分群群管理者失效时采用群首兼容群管理者功能的角色扩充机制。另外较其它相关算法而言,提出的路由算法在计算/存储复杂度以及通信资源占用率和数据包路由最短延时等方面具有优势,这主要基于提出:

1)基于GEO通信覆盖域的MEO星座分群管理机制;

2)通过分群来实现分布与集中相结合的路由更新策略;

3)基于状态更新的信息增量修正路由计算方法;

4)二代导航星座系统中通信节点间链路冗余设计方案。

[1]Werner M,Delucchi C.ATM virtual path routing for LEO/MEO satellite networks with intersatellite links[C]//Satellite Systems for Mobile Communications and Navigation,1996,Fifth International Conference on,London,1996:143-146.

[2]Werner M.A Dynamic Routing Concept for ATMBased Satellite Persona1 Communication Networks[J].IEEE Journa1 on Selected Areas in Communications,1997,15(8):1639-1648.

[3]Chang K L,Chang H,Kim W,et a1.Topological Design and Routing for Low-Earth Orbit Satellite Networks[C]//Proc.of IEEE GLOBECOM,1995:529-535.

[4]Gounder V V,Prakash R,Abu-Anlara H.Routing in LEO-based satellite networks[C]//Proc.of IEEE E-merging Technologies Symp.Wireless Communications and Systems,1999(22):1-22,6.

[5]Chang H S,Kim B W,lee G G,et a1.FSA-based link assignment and routing in low-Earth orbit satellite networks[J].IEEE Transactions on Vehicular Technology,1998,47(3):1037-1048.

[6]Werner W,Berndl G,Edmaier B.Performance of optimized routing in LEO intersatellite link networks[C]//Proc.of IEEE 47th VehicularTechnology Conference,1997(1):246-250.

[7]Ekici E,Akyildiz I F,Bender M D.A distributed routing algorithm for datagram traffic in LEO satellite networks[J].IEEE/ACM Transaction on Networking,2001,9(2):137-147.

[8]Lo M W.Satellite constellation design[J].IEEE Computing in Science and Engineering,1999,1(1):58-67.

[9]Chen C,Ekici E.A routing protocol for hierarchical LEO/MEOsatellite IP networks[J].ACM/Kluwer Wireless Networks(WINET),2005:507-521.

[10]Chen C,Ekici E,Akyildiz I F.Satellite Grouping and Routing Protocol for LEO/MEO Satellite IP Networks[C]//Proc.of the Fifth International ACM Workshop on Wireless M obile Multimedia,2002:109-116.

[11]Akyildiz I F,Ekici E,Bender M D.M LSR:A novel routing algorithm for multi-layered satellite IP networks[J].IEEE/ACM Transaction on Networking,2002,10(3):411-424.

[12]China National Administration of GNSS.COMPASS and Its Applications in Life Relief.[C]//Proc.of theUnited Nations/Azerbaijan/United States of America/European Space Agency Workshop on the Applications of Global Navigation Satellite Systems,Baku,Azerbaijan,2009.

[13]China Satellite Navigation Project Center.COMPASS/BeiDou Navigation Satellite System Development[C]//Proc.of the The 4th Meeting of International Committee on GNSS,Saint Petersburg Russia,2009.

[14]Sun H W,Li Z G,Ping F.Development of Satellite Navigation in China[C]//Proc.of the Frequency Control Symposium,2007 Joint with the 21st European Frequency and Time Forum IEEE International,2007.

[15]China National Administration of GNSS.Applications and Development and Applications of Compass/Beidou Satellite Navigation System[C]//Proc.of the International Committee on GNSS 2009(IGNSS2009),Gold Coast Australia,2009.

[16]Maine K P,Anderson P,Langer J.Crosslinks for the next-generation GPS[C]//the Aerospace Conference,2003.Proceedings of 2003 IEEE,2003(4):1589-1596.

[17]谭述森.北斗卫星导航系统的发展与思考[J].宇航学报,2008,29(2):391-396.

[18]童 铠.卫星导航系统在我国的应用与发展[J].国际太空,2004,(1):4-8.

[19]易先清,冯明月,赵 阳,罗雪山.一种基于GEO/MEO星层组网的卫星网络抗毁路由研究[J].计算机科学,2007,34(8):74-82.