基于位置感知的大规模LEO星座分布式路由算法

刘高赛, 姜兴龙, 李华旺, 梁 广

(1. 中国科学院微小卫星创新研究院, 上海 201203; 2. 中国科学院大学, 北京 100049;3. 上海微小卫星工程中心, 上海 201203)

0 引 言

低地球轨道(low earth orbit,LEO)卫星网络由于经济高效、传播时延低、路径损耗小等特性,在发展全球信息化建设中受到了较多的关注。近几年LEO卫星互联网的发展突飞猛进,为了满足日益增长的业务对大容量的需求,卫星互联网多采用大规模LEO卫星组网,其中典型的包括美国的Starlink星座、英国的Oneweb星座、加拿大的Telesat系统。Starlink星座预计会有超过12 000颗卫星组成,用于提供宽带接入和高速互联网服务。面向宽带互联网的大容量吞吐需求,Starlink和Telesat星座纷纷采用激光星间链路,由于激光高精度跟瞄和超高速传输等技术复杂、成熟度较低以及日凌影响等问题,因此有较高的中断频率。大规模LEO卫星网络的高动态性、链路中断率高、拓扑变化快等问题,对星座的路由算法带来了新的挑战。

路由算法是卫星组网的关键,影响着卫星业务的吞吐量、鲁棒性、传输时延等服务质量(quality of service, QoS)。卫星节点有着计算能力低、存储空间小、能源受限和无法升级硬件等特点。卫星节点和卫星网络的特点使得地面已有的路由算法不适用于卫星网络。传统的卫星路由策略包括虚拟拓扑和虚拟节点,虚拟拓扑的路由表是由地面站注入,无法根据实时网络状态避免网络拥塞和节点故障。针对以上不足,文献[9-14]采用基于虚拟节点的分布式路由算法。但分布式路由中，当中间节点出现故障,卫星需重新计算路由,将增加数据传输时延。文献[15]提出了一种基于备用节点的分布式路由算法,解决分布式路由算法在节点出现故障导致传输效率下降的问题。针对分布式路由的星座运算量大的问题,文献[16]提出了一种加权半分布式路由算法(weighted semi-distributed routing algorithm,WSDRA),将星座中卫星分为信使卫星和路由卫星,仅路由卫星计算数据包的流向,将星座整体运算量平均减少了一半。

分布式路由算法采用广播方式寻找最佳路径,造成大量的资源浪费,星座的路由收敛速度慢,大规模星座尤为明显。为简化星座管理和减小路由寻径开销,地面网络分域思想被应用于星座分簇,主要算法包括动态划分簇和静态划分簇。簇内卫星路由发现多采用泛洪方式,造成不必要的能源和带宽浪费。也有研究人员将大规模星座划分为一定数量的小立方体,通过小立方体而不是坐标来定位卫星,降低了端到端时延和计算复杂度。但此算法需卫星节点向周围卫星发送维活信令,采用网格方式划分网络,需要卫星存储网格信息,增大了卫星存储负载。同时，随着网格数量增多,也将影响路由效率。为减少HELLO包的发送,文献[23]利用卫星的可预测性,提出GomHop算法,减少了数据跨平面的传输,将数据优先传送到同一平面中,但未考虑算法的鲁棒性,卫星出现故障时需要重新计算路由。

综上,为了降低路由开销、端到端时延，提高星座吞吐量,研究人员对已有的分布式路由算法和分簇路由算法进行了优化。还有研究人员在大规模星座采用分层的路由策略,高轨卫星管理低轨卫星,中继低轨卫星数据。这些策略同样提高了路由的效率,降低了端到端时延。但是路由收敛时未能充分利用卫星运行位置可预测的特性,多层卫星造成了成本增高、链路时延增加等问题。通过上述分析,本文提出了一种基于位置感知的分布式路由算法(distributed routing algorithm based on location awareness, LADRA),该算法为保证不同业务的QoS要求,基于状态矢量函数(state vector function,SVF)和传播矢量函数(propagation vector function,PVF),充分利用了卫星轨道运行的可预测性,对传统先进先出(first in first out,FIFO)排队规则进行优化。通过仿真表明,本算法相比传统分布式路由算法(distributed routing algorithm,DRA)和WSDRA,降低了路由开销,随着链路中断概率的增加,降低了端到端时延,提高了星座吞吐量。本文的主要贡献如下。

(1) 提出大规模LEO星座路由预选算法。根据卫星运行位置可预测性,每颗卫星传输数据包时,预选2～3个发送端口。此过程每颗卫星只需存储周围卫星的轨道参数,存储空间的占用不受星座规模大小的影响。

(2) 提出大规模LEO星座路径收敛机制。根据SVF和PVF对预选路径收敛。采用SVF避免了网络拥塞,降低了排队时延。PVF对路径的收敛过程,在两条完全独立的路径中,根据QoS需求,选择较优的一条作为主路径,另一条作为备用路径,提高了路由的鲁棒性和吞吐量。

(3) 针对SVF收敛过程中可能发生的碰撞问题,本文给出了处理流程,保障了SVF收敛之后有两条无重合的路径。

(4) 优化FIFO排队策略。本文的队列出队规则不仅和入队时间有关,而且与数据包大小有关,提高了单位时间数据包的传输量。

1 系统模型与问题定义

1.1 大规模LEO星座模型

图1 大规模LEO星座拓扑和卫星节点定义Fig.1 Large-scale LEO constellation topology and satellite node definition

1.2 问题定义

传统的FIFO排队模型,按照业务到达的时间先后进行排队,先进的数据包先出,不考虑数据包的大小不同。本文对FIFO排队规则进行改进,出队规则不仅与入队时间有关,而且与数据包的大小和数据包的传输速率有关。出队顺序所参照的表达式为

=+pkg

(1)

式中:为数据包入队时间；为数据包传输速率；pkg为数据包大小。在同一个卫星端口排队的数据包,值小的数据包优先出队。

按照此规则不同数据包排队时延计算表达式为

(2)

式中:<表示卫星中,由式(1)计算出数据包pkg的值,小于数据包pkg的值,Δ表示pkg加入队列时,正在传输的数据包已经传输的时间。例如,图1中的卫星的一个发送端口在排队的数据包有4个,4个数据包的入队时间如图2所示。由式(2)可知,数据数据包pkg排队时延为(pkgpkgpkg)-(-),pkg的排队时延为(pkgpkg)。

图2 数据包到达时间和数据包大小Fig.2 Packet arrival time and packet size

星座的吞吐率是评价路由算法的一个关键指标,本文定义的星座吞吐率表达式为

(3)

式中:Rcv为卫星, 作为目的节点接收到的业务数据量;end为星座中数据包接收结束的时刻;start为星座中存在卫星接收数据的时刻。

对于资源受限的卫星网路,路由开销是评价路由算法的另一个关键指标,本文路由开销定义如下:

(4)

式中:表示星座中路由控制包的数量;表示目的卫星接收到的数据包总数。

2 LADRA路由算法设计

2.1 路径预选机制

(5)

图3 SRC与DST的位置关系图Fig.3 Relative position of SRC and DST

根据在时刻SRC、DST和SRC周围卫星的位置信息,计算出图3中的∠：

(6)

采用同样的方法求得∠、∠、∠的值,SRC根据∠、∠、∠、∠的大小选择下一跳,以90°为选择下一跳的阈值角度。如图3中,∠、∠大于90°,SRC_L和SRC_D不作为SRC的下一跳卫星,∠、∠小于90°,SRC_U、SRC_R可以作为SRC的下一跳卫星。SRC到DST的中间节点,选择下一跳卫星时,同样选择夹角小于90°的卫星作为下一跳。迭代上述过程,将路由请求包(routing request packet,RREQ)传输到DST。路由预选机制中的RREQ,从源卫星到目的卫星的传输过程中,每颗卫星会传输RREQ到一个或两个下一跳卫星,导致较多的RREQ在星座中传输,浪费了链路资源和有限的卫星能源,为此提出了路径收敛机制。

2.2 路径收敛机制

本文选择夹角小于90°的卫星作为下一跳,由图3可知,SRC会有两颗卫星满足此条件。中间卫星的下一跳同样可能有一颗或两颗卫星,如图3中SRC_R周围有两颗卫星满足此条件。如果中间节点较多,每颗中间卫星产生两个分支,由文献[27]可知,路径的建立会消耗较多的卫星能源。为此在路径建立时,对路径进行收敛,减少不必要的RREQ的复制传输。本文采用两个因子收敛路径,第一个因子根据卫星端口的排队长度,简称排队因子,第二个因子根据不同路径卫星节点的能源状况,简称能源因子。

排队因子采用SVF,从SRC到DST的方向收敛路径。能源因子采用PVF,从DST到SRC的方向收敛路径。SVF的表达式为

(7)

PVF的表达式为

(8)

首先通过路径预选,然后通过排队因子和能源因子对路径进行收敛,最终确定数据包传输路径。防止SVF收敛后,SRC卫星到DST卫星只有一条路径,本文的排队因子对路径的收敛作用于中间卫星。中间卫星收到RREQ后,以SRC_R为例,SRC_R经过路径预选后,采用SVF收敛,在预选链路中选择排队时延短的端口发送RREQ。中间节点迭代SRC_R的处理过程,直到RREQ传送到DST。按照上述过程,DST会收到来自两条路径的RREQ,DST采用PVF实现路径最终的收敛。确定一条路径为主路径,另一条路径为备用路径。

在SRC卫星发送的RREQ中,加上SRC的PVF,中间节点收到RREQ后,按照式(8)更新PVF,最终两条路径的PVF传输到DST。DST比较两条路径的大小,选择两条路径中较大的作为主传输路径,另一条路径作为备用路径。当主路径出现拥塞或其他链路问题时,SRC采用备用路径传输业务数据。当路径上中间卫星感知到下一跳的位置变化范围超出路径预选的范围,将向SRC发送路径更新包。SRC将按照上述过程重新构建主路径和备用路径。通过SVF,采用排队因子,降低业务数据的排队时延。通过PVF,采用能源因子,降低由于中继卫星能源不足导致链路中断的概率。主路径和备用路径的迭代建立,保证了主路径中断后,数据包能够快速重传。

采用SVF收敛路径时,存在收敛碰撞的问题,即RREQ传输到目的卫星前,两颗卫星通过SVF收敛,将RREQ传输到了同一颗卫星,导致RREQ到达目的卫星时只有一条路径。为解决收敛碰撞的问题,本文对SVF收敛导致的碰撞问题进行了处理。

2.3 SVF收敛碰撞处理

采用SVF收敛路径,会产生两种收敛结果,第一种是从SRC到DST,两条路径不会收敛到同一颗中间卫星。第二种是SVF收敛的过程中发生收敛碰撞,两条路径到达DST前收敛到了同一颗中间卫星。SVF的第一种收敛结果如图4所示。从源卫星到目的卫星,没有发生SVF收敛碰撞,从SRC到DST产生了两条独立的路径。

图4 SVF收敛无碰撞示意图Fig.4 Diagram of SVF convergence without collision

SVF的第二种收敛结果如图5所示。卫星与卫星在选择下一跳时,均选择了卫星,按照上述提出的SVF收敛机制,卫星到目的卫星只会产生一条路径,导致PVF收敛机制失效。针对SVF的收敛碰撞问题,本文提出了SVF收敛碰撞处理机制。以图5为例说明SVF收敛碰撞处理过程。SVF收敛碰撞发生在图5中卫星和卫星,由于卫星为DST,在DST卫星发生碰撞,采用PVF从碰撞的两条路径,分别选择一条主传输路径和一条备用路径。如果在卫星预选路径之后再使用SVF对路径收敛,会导致只有一条路径到达DST卫星,因此对于在中间节点发生的收敛碰撞,以卫星为例,SVF收敛碰撞的处理流程如图6所示。

图5 SVF收敛碰撞示意图Fig.5 Diagram of SVF convergence collision

图6 卫星v2,2处理SVF收敛碰撞流程Fig.6 SVF convergence collision processing flow of satellite v2,2

假设发生SVF收敛碰撞的卫星,通过PVF收敛后选择作为上一跳。收敛碰撞处理如下:

(1) 中间卫星传递RREQ包时,在RREQ包中加入经过SVF收敛后,没被选择的下一跳位置信息。例如,图5中向发送的RREQ包中包含的位置信息。

(2) 按照假设,经过PVF的收敛,选择为上一跳,将的RREQ包中的位置信息删除,保留的RREQ包中的位置信息,并将该位置信息写入的RREQ包中。

(3) 发生碰撞的卫星,进行路径预选机制后,发送包含位置信息的RREQ包到卫星和,接收到发生收敛碰撞卫星的RREQ包,计算上一跳可能的位置信息,并与的位置信息对比,确认是的上一跳,则在中将上一跳置为。

(4) 卫星接收到发生收敛碰撞卫星的RREQ包,进行与相同的操作,但不是的上一跳,的上一跳确认为。

LADRA首先通过位置感知执行路径预选,然后采用SVF和PVF对路径进行收敛,最后针对SVF收敛过程中的碰撞问题,本文给出了处理流程。LADRA的伪代码如算法1所示。

算法 1 LADRA输入:周围卫星的轨道参数i, Ω, e, ω, a, M0,时间t输出:数据包输出端口P1) 通过式(5)计算周围卫星的位置2) 将周围卫星的位置信息和目的卫星的位置信息,输入到式(6),分别计算周围每颗卫星和目的卫星的夹角,按照周围卫星上下左右4个方位,将夹角分别定义为β、η、γ、α3) for i=[β, η, γ, α]4) if i≤90°then5) 将i存储到待选端口集合P,P=[P, i] 6) end if7) end for8) if 此卫星为SRC卫星 then9) 将RREQ通过预选端口集合P发送出去10) else if 此卫星为DST卫星 then11) 由式(8)的PVF,选择路径中最低剩余能量最高的路径,回复RREP作为主路径,另一条路径,回复RREP作为备用路径12) else13) if 收到两个RREQ(发生碰撞) then14) 由式(8)PVF,选择路径中最低剩余能量较高的路径,回复RREP 15) 执行图6的碰撞处理流程,将RREQ包从预选路径的端口集合P发出16) else (无碰撞发生)17) 由式(7)的SVF,计算待选端口P中排队时间次少的下一跳位置信息写入RREQ包,向排队时间最短的端口发送路由请求RREQ包18) end if 19) end if

其中,标号1)～7)是路径预选,8)～19)是采用排队因子和能源因子对路径进行收敛。本文提出的路径预选和收敛机制,减少了路由开销,每次路由的更新,每颗卫星仅需完成周围卫星的位置计算和路径收敛计算。卫星的路由存储开销主要包括周围卫星的轨道六根数,与星座规模的大小无关。计算开销主要包括周围卫星位置的计算和数值比较。排队因子降低了排队时延,均衡了网络负载；能源因子减少了对能源相对少的卫星进一步消耗,延长了星座运行时间。本文提出的基于SVF和PVF的路径收敛策略,除采用排队因子和能源因子,还可以根据业务QoS需求,选择端到端时延、路由跳数、链路故障率等因子。

3 仿真实验

为了验证LADRA的有效性,本文使用STK开发平台设计了大规模LEO近极轨星座,借鉴STK导出的轨道数据,利用Matlab对LADRA算法进行验证和分析,并将LADRA分别与DRA以及WSDRA进行对比。

3.1 仿真参数

网络架构采用第一代Oneweb近极轨星座,星座共有648颗卫星,分布在18条LEO轨道。星座中除反向缝处不存在星间链路,其余卫星存在4条星间链路。仿真参数设置如表1所示。图7为第一代Oneweb星座结构图。根据STK导出的轨道信息,在Matlab中实现本文算法功能,如图8所示为根据STK轨道信息,在Matlab中计算的实时星下点分布。

表1 仿真参数设置Table 1 Simulation parameters setting

图7 第一代Oneweb星座结构图Fig.7 The first generation Oneweb constellation structure diagram

图8 星下点分布图Fig.8 Distribution map of sub-satellite points

3.2 仿真分析

对于资源受限的卫星网络,路由建立阶段的开销是影响卫星网络运行的一个因素,也是评价路由算法的一个标准，式(3)为路由开销的定义。本文对LADRA、传统的DRA、WSDRA 3种路由建立开销进行了对比。图9是3种算法在不同跳数下,路由建立阶段的开销对比图。从图9中可以看出,随着源卫星与目的卫星的跳数增加,发送相同数量的数据包,路由开销逐渐增大,传统的DRA路由开销随着跳数增加,路由开销呈()增加。本文的LADRA,随着路由跳数增加,开销呈线性增长,且增长速度较慢。路由跳数大于10跳,LADRA路由开销平均为WSDRA的50%。路由建立的开销方面,LADRA更加适合大规模LEO卫星网络。

图9 不同跳数下路由建立阶段的开销Fig.9 Cost of route establishment at different hop counts

图10给出了传统DRA、WSDRA和本文提出的LADRA,在不同的链路中断概率下的端到端时延对比图。仿真结果表明,3种算法在中断概率小于1%时,端到端时延相近,但随着链路的中断频率增加,本文的LADRA端到端时延增加量最小。中断频率大于3%时,LADRA端到端时延平均为WSDRA的一半。因为本文算法在构建端到端传输路径时,不仅构建了一条主传输路径,而且构建了一条备用路径,当链路出现故障时,能够直接切换备用路径传输业务数据。另外,WSDRA的端到端时延低于传统DRA。因为WSDRA在卫星节点出现故障或拥塞时,能够在主方向和次方向选择下一跳,而DRA只在主方向上选择下一跳。

图10 不同链路中断概率下的端到端时延Fig.10 End-to-end delay at different link interruption probabilities

图11给出了传统DRA、WSDRA和本文提出的LADRA,在不同传输中断频率下的星座吞吐量。从图11中可以看出,中断概率小于1%时,3种算法的吞吐量相近。当中断频率大于3%时,本文LADRA吞吐量大约为WSDRA的两倍。这是因为备用路径和对传统FIFO方式进行优化的结果,另外,本文LADRA,在路径建立阶段信令包的开销较少,节约了链路资源。

图11 不同链路中断概率下的吞吐率Fig.11 Throughput rates at different link interruption probabilities

4 结 论

由于大规模LEO星座具有高时延、高动态、激光星间链路中断概率大等特性,采用传统的路由算法,存在着适用性差等问题。因此,本文提出了一种LADRA,为解决大规模星座路由问题提供一种新的思路。首先,通过路径预选和收敛机制,根据业务数据自适应地确定一条主路径和一条备用路径。然后,针对SVF导致的收敛碰撞问题提出了处理方案,避免了SVF收敛到同一颗中间节点。最后，通过理论分析和实验验证了LADRA的路由建立阶段开销较小。随着中断概率的增加,LADRA与传统的DRA、WSDRA相比,降低了端到端时延、提高了星座的吞吐量,更加适合大规模LEO星座。

未来将对此算法进行优化,确保此算法运行在大规模LEO星座中具有更好的抗毁能力、安全性、更高的吞吐量和更低的端到端时延。