高 强,郭 成,2,张胜利,蒲卫华,吴荣东

(1.深圳大学 电子与信息工程学院,广东 深圳 518000;2.鹏城实验室,广东 深圳 518038;3.深圳航天东方红卫星有限公司,广东 深圳 518000)

0 引 言

卫星通信中卫星轨道类型对每个任务要求都有相当大的影响(轨道的高低决定着飞行周期),也影响着实际通信系统的设计,根据服务的预期和通信类型,卫星星座部署需求有所不同[1]。

近些年,有关小卫星网络的路由算法和应用的策略相继提出,前期的路由方案主要分为两种:虚拟拓扑和虚拟节点。前者就是将拓扑结构时间虚拟化,将时间离散化为一系列的时间片,每个时间片被称为快照[2]。快照中,由于时隙跨度较短卫星网络的拓扑被认为是稳定的或准静态的,其变化只发生在快照的交接点。虚拟节点又可分为星座虚拟化和区域虚拟化:星座虚拟化就是将小卫星星座化为有固定地理位置的虚拟节点;区域虚拟化就是将地球表面进行网格划分并分配固定的逻辑地址,充分考虑地理与人口的因素。基于虚拟节点的算法[3-9]隐藏卫星节点的移动性,采用局部优化的方法,缺乏全局的把握,所以所得的路径不一定能够最优。

为了满足日益增多的业务需求,对资源进行有效利用,保证网络服务质量(Quality of Service,QoS),一些基于QoS多层卫星网络路由算法[10-14]也陆续被提出。但现有的调度大都是集中式调度,缺乏灵活性,而且与遗传算法等启发式算法相结合,降低了时间效率。所以,提出性能优良的卫星间调度仍是亟需研究解决的问题。

面对地面两地的远距离通信,本文从多方面考虑优化路由路径。首先针对卫星组网结构的复杂和链路的频繁转换,选用根据节点的实时运动确定全局网络模型链路的连接方法,并且充分考虑高纬度区域和接缝区域链路的状态。面对星上资源有限造成多业务的拥塞情况,又将业务分类为实时和非实时两种,对非实时业务进行加权轮询调度保证其公平性,又可以对数据进行分流,保证链路的利用率和数据的有效转发。

1 路由过程

上述路由机制均简化了拓扑的结构,也就是提前规定好拓扑结构,相当于在离线状态下进行路由,伴随而来的是对链路拥塞或损坏、流量变化等实时情况的应对能力较差。一个好的路由机制对数据的吞吐量、丢包率以及链路的拥塞情况和抗毁性等都有较高的要求。本文所提出的路由机制,首先寻找卫星的接入(源卫星和目的卫星),根据本文建立的评估函数建立星上路由表,将星上的数据调度形成一个完整的调度队列,按次序根据最优评估函数一步一步地寻找最优解,直到达到目的卫星。具体模型如图1所示。

图1 路由算法模型

1.1 星座设计

本文建立的星座模型如图2所示。不同于星链计划中庞大的卫星数和“之”字形的运行路线,本文中采用极地轨道(图2轨道面与赤道面近似垂直)的设计,在这种轨道上飞行的卫星都可以经过南北两极。规律的运行轨迹可以更好地实现位置和传输数据的快速定位,虽然有时受地球自转的影响。另外,相比于其他小卫星轨道轨迹,采用极地轨道不需要大量的小卫星便能覆盖全球,大大降低了成本。本文采用的卫星数为M×N,M代表轨道数,N代表每个轨道的卫星数,每个卫星的运行周期为T。不同运行方向的卫星轨道之间称为接缝,在接缝区域之间的轨间链路存在时间较短,故在本文中假设在此区域不存在卫星链路。

图2 星座模型

另外,在高纬度区域时,卫星上的天线指向会发生变化,故定义维度阈值latmax,超出该阈值时不存在轨间链路。整个卫星网络可以简化为

G=(V,E) 。

(1)

式中:V表示卫星节点;E表示链路。采用类似于“铱”星星座结构,极地轨道模型,故每个卫星最多拥有4个链路(2个轨内链路和2个轨间链路)。考虑高纬度区域和轨道接缝的限制,生成链路矩阵E(算法1)具体描述如下:

输入:维度阈值latmax,此刻某卫星C的维latc

输出:网络链路矩阵E

1 if latc

2 ifC不在接缝区域内 then

3C相邻的4个卫星链路都接通

4 else ifC在接缝区域内 then

5C仅与同轨道的两颗相邻卫星建

立链路

6 end if

7 else if latc>latmaxthen

8C仅与同轨道的两颗相邻卫星建立

链路

9 end if

10 更新链路矩阵E

1.2 接入控制

关于卫星与地面站的接入情况,Wang等人[15]提供了基本的思路,但并没有考虑实际卫星的结构状况(卫星上通信天线的方位指向是固定的,两颗正在通信的卫星绕过极点时相对运动方向发生改变,天线连接断开,通信结束)。本文基于此进行优化。考虑物理可见的情况,如果地球阻止卫星之间的连接,无论是激光还是微波,都不能形成通信链路,即不能进行通信。设置以下的几个参数:Re为地球的半径;D为卫星之间或卫星与地面站之间的距离;H为地球中心点到卫星连线的垂直距离;α为卫星之间的连线与卫星地球中心之间连线的夹角。

图3所示的情况可判决卫星间是否可见,但还要考虑地面站与卫星的可见情况。当卫星与地面站链路与地球相切时可达到距离的临界值,然后选用最接近源和目的地面站的卫星作为接入。

图3 卫星的接入

例如卫星S1与卫星S2的距离为D1,H1为卫星S1和S2连线的中心点到地心的距离,如果

H1≥Re,

(2)

则卫星在物理上是可见的,可以形成卫星间通信链路。

卫星S2与S4的距离为D2,H2为S2与S4连接线的中心点到地心的直线距离,如果满足

H2≤Re,

(3)

则卫星在物理上是不可见的,它不能建立卫星间的链路。

对于卫星和地面站的连接,地面站刚进入辐射半角为α1的卫星辐射范围内时,卫星与地面站的距离最大即达到临界值。此时距离的值达到最大值Dmax,即卫星与地面建立通信联系的条件是

D≤Dmax。

(4)

卫星地面站的接入(算法2)具体描述如下:

输入:源地面站G,地球半径Re,卫星距地心的距离Hl,卫星的辐射半角α1,与源地面站建立链路的卫星数量n,卫星序号Li

输出: 输出源接入卫星s

1余弦定理计算其临界条件Dmax

2Dsg=Dmax

3 fori=1 tonthen

4 ifDig≤Dmax&&Dig≤Dsg

5s=Li

6Dsg=Dig

7 end if

8 end for

9 输出源接入卫星s

10 同理可得目的接入卫星d

由上可知,节点间的物理可视性是设计卫星间链路和星地链路时最基本也是最重要的参考因素。在物理可见度的基础上,卫星与地面目标的距离越近,卫星-地面进入的延迟就越短。 它可以保证此时建立的卫星通信链路可以持续一段时间,不会瞬间断开,导致通信链路无效。 因此,当两个地面目标请求卫星通信时,使用此时最接近两个目标的低轨道卫星作为通信接入卫星。具体的实现方法如算法2所示。

1.3 调度

调度问题是路由选择过程中不可忽视的一点。考虑到业务高速化,多样化的背景下必须保证不同业务的服务质量。所以根据网络业务的复杂性,将不同的业务进行等级划分: A类实时性业务和B类非实时性业务。实时性业务的优先级最高,各种非实时性业务的优先级相同,本文简单将其划分为A类、B类和C类3类。

不同业务有着不同的QoS需求:实时性业务要求低时延、低丢包率等与时间有关的要求;非实时性业务仅以完整到达率作为要求。调度的目的就是给各种数据包排序,确保转发的优先级,尽可能多地满足各种业务需求。根据优先级来说,实时性数据包必须比非实时性数据包先执行转发操作,而对于非实时性数据包,考虑公平的因素可以进行适当的插入,即采用轮询调度进行数据包的排序(算法3),最终得到的即为卫星节点缓存之中的调度队列,即数据包的转发次序。

算法3具体描述如下:

输入:当前卫星节点的所有数据包,A类实时性业务,B类非实时性业务(B0,B1,B2)

输出: 数据包调度队列 arr

1 for 所有数据包 do

2 if 数据包 ∈ A类 then

3 高优先级队列 ← 数据包

4 else if 数据包 ∈ B类 then

5 if 数据包 ∈ B0类 then

6 B0缓存队列 ← 数据包

7 else if 数据包 ∈ B1类 then

8 B1缓存队列 ←数据包

9 else if 数据包 ∈ B2类 then

10 B2缓存队列 ←数据包

11 end if

12 end if

13 end for

14 低优先级队列 = 加权轮询(B0,B1,B2缓存队列)

15 总调度队列 arr =[高优先级队列,低优先级队列]

1.4 路由选择

本文参考Guo等人[16]的思路建立一个评估函数来进行路由的选择。评估函数主要包括延迟因子和损耗因子。

1.4.1 损耗因子

基本思想是卫星网络中的所有节点周期性地产生携带路由信息的路由学习包,然后广播给其所有相邻的卫星节点。邻居节点对其在特定时间内收到的路由学习包数量进行统计,计算链路的传输权重,选择最优下一跳。具体是每个卫星节点为其邻居增加一个滑动窗口机制来实时统计路由学习包的数量,而路由学习包中有唯一固定不变的序列号SQ,随学习包产生的先后顺序而增大;滑动窗口记录了一段时间内的序列号,如图4所示,最后时刻SQ=30,滑动窗口收到后在相应位置1,此时滑动窗口的尺寸即为30,链路的传输权重即为窗口中0的个数与总尺寸的比值。此时损耗因子表示为

图4 滑动窗口

lθ=e(i,j) ×tij。

(5)

式中:e(i,j)代表链路的连通性,e(i,j)=1代表链路接通,e(i,j)=0表示未接通链路。

1.4.2 延时因子

由上面的定义可知,Dij代表卫星i与卫星j之间的距离。在小卫星组网的条件下,定义初始状态下卫星之间的最大距离为Dmax,则延时因子可定义为

dϑ=e(i,j) ×(Dij/Dmax)。

(6)

当前节点的路由表项(算法4)具体描述如下:

输入:链路矩阵E,当前节点i与临近的节点j,卫星距离的临界值Dmax

输出: 节点路由表

1 for 对i的所有相邻节点jdo

2 计算损耗因子lθ=e(i,j)×(ti,j

3 计算卫星节点i,j之间的距离Dij

4 计算延时因子dθ=e(i,j)×((Dij/Dmax)

5 评估函数φ=ω1lθ+ω2dθ

6 将函数值记录在当前节点的路由表中

7 end for

8 在当前卫星中存储路由表值

这样就算出此节点到所有相邻节点的传输权重,定义为损耗因子,再与延时因子构成评估函数:

φ=ω1lθ+ω2dθ。

(7)

由此形成的路由表项存储在此节点中,即可得出最优下一跳节点。

1.5 路由调度算法

整个路由调度算法表示为转发就按照调度队列进行,实时性数据包只考虑最优的下一跳节点,非实时性数据包可以根据情况转发。设置拥塞度δ等于当前的数据包数据除以节点所能容忍的数据包最大长度,定义阈值a为拥塞状态,禁止非实时性数据包的进入,只允许实时性数据包的转发。到达拥塞状态时非实时性数据包可以选择次优节点进行转发,一步一步地到达最终的目的节点。

路由调度算法(算法5)具体描述如下:

输入:源节点s,目的节点d,中继节点r,节点路由表,调度队列err

输出: 最优下一跳

1 for 调度列表are do

2 查找路由表寻找最小评估函数φ

3 if 最优下一跳节点空闲 then

4 将数据包发送至下一跳节点

5 else if 拥塞度δ≥athen

6 if 数据包 ∈ B类 then

7 查找路由表寻找次优评估函数φ

8 将数据包发送给次优节点

9 else

10 将数据包发送至最优下一跳节点

11 end if

12 end if

13 end for

14 return 最优下一跳节点r

所以最终的路由算法(算法6)如下:

输入:源节点s,目的节点d,中继节点R

输出:整个最优路径

1 fors≠ddo

2R=算法5输出r

3s=R

4 path.append(R)

5 end for

6 return path

另外,考虑到万一有数据包传输中链路突然断裂的情况,即卫星节点运行到纬度的阈值70°,卫星间的轨间链路断裂。所以考虑完整传输数据包问题,可以规定卫星节点到达纬度65°时不再进行轨间链路的数据传输。卫星与地面站之间也存在链路,假设Tld为节点间数据传输的最大延时,Tlm为数据包的最晚传输时间,

Tlm=接触截止时间-Tld,

(8)

数据包必须在最晚传输时间内进行传输才能完整到达卫星节点。

备选卫星(算法7)具体描述如下:

输入:星地链路的最晚传输时间Tlm

输出:最新的源卫星s′和目的卫星d′

1 fori=0 toTlmdo

2s′,d′ = 算法2

3r′ = 算法5

4 path′ = 算法6

5 end for

6 return path′

如果源接入卫星和目的接入卫星发生变化,则重新执行接入算法,然后按照路由表项选择最优路径。

2 仿真与分析

通过卫星仿真软件STK(Satellite Tool Kit)搭建本文所需要的仿真环境。采用极地轨道,偏心率为0,轨道倾角为87°,系统运行周期为7 200 s,仿真总时长为两个系统周期。

通过Matlab与STK互联,生成所需要的小卫星系统星座模型。对于所有的轨内链路和轨间链路,带宽都设置为32 MHz,队列长度设置为100个数据分组的大小,每个分组的平均大小为1 000 b。本文选取了不同数量的卫星节点进行相应的测量,主要为端到端时延和数据传输速率。

图5显示了不同的卫星节点下,ARA(Adaptive Routing Algorithm)算法[15]与本实验算法下不同业务数据包的端到端时延情况。从图5可以看出,随着卫星节点数量的增多,ARA算法与本实验的B类数据包算法端到端时延都逐渐增大。这是因为在选择下一跳节点时要考虑节点的状态,卫星数量增多导致对链路的考虑时间相应增大,但相比之下还是本文的算法时延更小。与实时性相关的A类算法优先级最高,链路总是优先选择,随着节点的增多时延变化不大,但都远远小于其他算法,所以本文算法在端到端时延方面有着更好的性能。

图5 端到端平均时延

图6给出了各算法在不同卫星节点中吞吐量的变化关系,可以看出随着卫星节点的增多,本算法在A类数据包传输过程中保持着稳定的吞吐量。这是由于在相同源地点和目的地点的传输路径下,虽然中间传输的卫星在改变,但路径方位基本保持不变。另外,对非实时的数据,考虑负载的变化和流量的拥塞,卫星数增多会导致吞吐量的减弱,但B类数据包算法的平均吞吐量比ARA算法的吞吐量还略高,所以本文算法有着较好的性能。仿真结果证明了本文算法的正确性和有效性。

图6 平均吞吐量

3 结束语

在卫星网络中,一个良好的网络模型才是算法优化过程的基础,故本文首先综合小卫星的优势建立起整个的小卫星星座结构网络,然后提出了基于调度的小卫星路由优化算法,充分考虑业务量巨大的因素,保证业务的利用率。通过评估链路权重进行选路,实时路由获取最优路径,有效解决了全局网络中节点改变的难题。本文方法在时延方面有着良好表现,为实际场景中路由的优化方面提供了重要的参考。

下一步工作将从多方面考虑时间的变化和业务的需求,研究更加强大的优化算法。