基于QoS保障的LEO卫星网络可靠性路由方法

摘要

本发明公开了一种基于QoS保障的LEO卫星网络可靠性路由方法，通过引导热点区域流量向非热点区域转移，且在选路同时，设计严格的服务质量QoS约束，来完成星间路由路径的搜寻，以保证找到的路径具有最优的服务质量，尽量途经轻量化负载任务的卫星，降低卫星发生拥塞概率，继而减小丢包率，提高路由转发路径的可靠性。

说明书

技术领域

本发明属于LEO卫星通信技术领域，具体涉及一种基于QoS保障的LEO卫星网络可靠性路由方法的设计。

背景技术

随着空间信息技术的迅猛发展，低轨(LEO，Low Earth Orbit)卫星通信系统在全球通信、导航定位、气象预测、灾害监测和军事应用等方面发挥着越来越重要的作用，而作为LEO卫星通信网络关键技术之一的星间路由算法，则是提升整个卫星通信网络性能的核心因素。但是，由于外太空卫星网络所处的环境是较为恶劣，也是较为复杂的，存在着诸如网络拓扑频繁动态变化、星上负载不均衡、电磁干扰、卫星节点和链路易发生故障等情况，所以，为了保证提供给地面用户可靠、有效的通信服务，获得较佳的用户体验感，需要选择一条最优的路由路径来完成源目卫星之间数据包的高效传输。

发明内容

本发明的目的是提出一种基于QoS保障的LEO卫星网络可靠性路由方法，使得LEO卫星网络能够提供给用户一个稳定的、可靠的高质量体验感的通信服务，完成源目卫星之间数据包的路由转发。

本发明的技术方案为：基于QoS保障的LEO卫星网络可靠性路由方法，包括以下步骤：

S1、构建LEO卫星网络，并对LEO卫星网络中的全网链路状态信息库进行周期性更新。

S2、令LEO卫星网络中的LEO卫星等待触发路由。

S3、判断地面用户是否有新的呼叫或呼叫切换到达，若是则进入步骤S4，否则返回步骤S2。

S4、构建多约束QoS最优路径路由模型。

S5、利用链路最小带宽约束对卫星拓扑进行剪枝预处理，将多约束QoS最优路径路由模型简化为时延约束最小路径代价路由模型。

S6、根据基于合成成本代价的拉格朗日松弛算法对时延约束最小路径代价路由模型进行求解，得到最优路由路径p

S7、判断最优路由路径p

S8、通过最优路由路径p

S9、拒绝此次路由请求，结束流程。

进一步地，步骤S1包括以下分步骤：

S11、通过M×N颗LEO卫星构建LEO卫星网络，其中M为LEO卫星网络的轨道面数，N为每个轨道面上的卫星数。

S12、选取每个轨道面的轨道发言人卫星。

S13、通过每个轨道面的轨道发言人卫星收集对应轨道面内所有其他卫星的卫星链路状态报告，并与自身的卫星链路状态报告汇总，形成本轨道面的轨道面链路状态报告。

S14、通过每个轨道面的轨道发言人卫星将本轨道面的轨道面链路状态报告发送至相邻轨道面。

S15、通过每个轨道面的轨道发言人卫星接收来自其他轨道面的轨道面链路状态报告，经过汇总完成全网链路状态信息库的构建。

S16、通过每颗卫星接收来自其所在轨道面的轨道发言人卫星发送的最新全网链路状态信息库，实现全网链路状态信息库的周期性更新。

进一步地，步骤S13包括以下分步骤：

S131、在每个轨道面内，通过每颗卫星计算自身的卫星链路状态报告，并将其发送至距离轨道发言人卫星最近的相邻卫星。

S132、相邻卫星接收到卫星链路状态报告后，判断是否曾经接收过该卫星链路状态报告，若是则丢弃该卫星链路状态报告，并继续等待接收其他卫星发送的卫星链路状态报告，否则进入步骤S133。

S133、判断相邻卫星自身的卫星链路状态报告是否已发送，若是则只将相邻卫星接收到的卫星链路状态报告发送至下一颗相邻卫星，进入步骤S134，否则将相邻卫星自身的卫星链路状态报告及其接收到的卫星链路状态报告一起发送至下一颗相邻卫星，进入步骤S134。

S134、重复步骤S131～S133，直到轨道发言人卫星获取到本轨道面内所有其他卫星的卫星链路状态报告，并将其与自身的卫星链路状态报告汇总，形成本轨道面的轨道面链路状态报告。

进一步地，步骤S15包括以下分步骤：

S151、在每个轨道面内，通过每颗卫星接收来自其他轨道面的轨道面链路状态报告。

S152、判断是否曾经接收过该轨道面链路状态报告，若是则丢弃该轨道面链路状态报告，并返回步骤S151继续等待接收来自其他轨道面的轨道面链路状态报告，否则进入步骤S153。

S153、判断该接收轨道面链路状态报告的卫星是否为其所在轨道面的轨道发言人卫星，若是则进入步骤S154，否则向其所在轨道面的轨道发言人卫星方向转发该轨道面链路状态报告，并返回步骤S151。

S154、存储该轨道面链路状态报告，并将其转发至下一个相邻轨道面。

S155、重复步骤S151～S154，直到每个轨道面的轨道发言人卫星都接收到来自LEO卫星网络内所有其他轨道面的轨道面链路状态报告，并将轨道面链路状态报告进行汇总，完成全网链路状态信息库的构建。

进一步地，卫星链路状态报告的计算公式为：

所述轨道面链路状态报告的计算公式为：

P_LSA(m)＝{S_LSA(x)|x为轨道面m上的卫星}

其中S_LSA(i)表示卫星i的链路状态报告，

进一步地，步骤S4中的多约束QoS最优路径路由模型的计算公式为：

min Cost(p)

其中p(s,d)表示源卫星节点s和目的卫星节点d之间的一条可用路径p，Cost(p)表示路径p的总代价值，且：

其中Cost

Cost

其中TD

TD

其中TD

其中

其中

其中lat

进一步地，步骤S5包括以下分步骤：

S51、利用用户通信业务最小要求可用带宽Band

S52、在剪枝预处理后的全局网络状态拓扑图G

p

其中p

进一步地，步骤S6包括以下分步骤：

S61、将时延约束最小路径代价路由模型p

其中L(θ)表示把时延约束条件吸收到目标函数后形成的新的线性函数，且：

L(θ)＝min{Cost

＝{Cost

其中θ表示拉格朗日乘子，Cost

其中Cost

S62、令拉格朗日乘子θ＝0，将链路代价Cost

S63、判断最短路径p

S64、将复合时延代价TD

S65、判断最短路径p

S66、通过迭代替换最短路径p

其中Cost(p

S67、将拉格朗日乘子θ代入合成链路代价函数Cost

S68、判断最短路径r的合成链路代价之和Cost

S69、判断最短路径r的时延TD(r)是否满足TD(r)≤TD

本发明的有益效果是：

(1)本发明通过分散式的卫星路由表计算执行者分担路由计算压力，降低了局部范围内卫星路由功能全部失效的风险，使得用户接入卫星(即源卫星)能够独立计算路由转发表。

(2)本发明通过引导热点区域流量向非热点区域转移，实现了全球流量均衡分布，能够轻量化全网卫星流量负载压力，减小了卫星发生拥塞概率，降低了丢包率。

(3)本发明通过设置高服务质量QoS约束，保证了搜寻路径的服务质量，使得路由路径发生拥塞概率极小，提高了路由转发过程中的可靠性。

综上，本发明使得LEO卫星网络能够提供给用户一个稳定的、可靠的高质量体验感的通信服务，从而完成源目卫星之间数据包的路由转发。

附图说明

图1所示为本发明实施例提供的基于QoS保障的LEO卫星网络可靠性路由方法流程图。

图2所示为本发明实施例提供的Walker star星座模型示意图。

图3所示为本发明实施例提供的全球热点区域分布图。

图4所示为本发明实施例提供的轨道面路由状态信息构建示意图。

具体实施方式

现在将参考附图来详细描述本发明的示例性实施方式。应当理解，附图中示出和描述的实施方式仅仅是示例性的，意在阐释本发明的原理和精神，而并非限制本发明的范围。

在描述本发明的具体实施例之前，首先对本发明出现的一些缩略语进行解释，以便更好的理解本发明：

LEO：Low Earth Orbit，低轨卫星；

QoS：Quality of Service，服务质量；

ISL：Inter-Satellite Link，星间链路；

S_LSA：Satellite Link State Advertisement，卫星链路状态报告；

P_LSA：Plane Link State Advertisement，轨道面链路状态报告；

NSB：Network State Base，全网状态信息库；

LARAC：Lagrange Relaxation based Aggregated Cost，基于合成成本代价的拉格朗日松弛算法。

本发明实施例提供了一种基于QoS保障的LEO卫星网络可靠性路由方法，如图1所示，包括以下步骤S1～S9：

S1、构建LEO卫星网络，并对LEO卫星网络中的全网链路状态信息库进行周期性更新。

步骤S1包括以下分步骤S11～S16：

S11、通过M×N颗LEO卫星构建LEO卫星网络，其中M为LEO卫星网络的轨道面数，N为每个轨道面上的卫星数。

本发明实施例中，采用Walker star星座模型作为实验场景构建LEO卫星网络，如图2所示，设定该卫星网络中共有M×N颗卫星，为了简化由于卫星周期性运动导致拓扑动态变化带来的路由编址设计难题，因此引入逻辑地址概念来标定每个卫星的路由转发地址，逻辑地址用S

卫星通信网络中的链路ISL包括：轨内星间链路(Intra-Plane ISL)以及轨间星间链路(Inter-Plane ISL)，正常情况下，每颗卫星是具有四条星间链路的，即两条轨内ISL以及两条轨间ISL。但是，也存在两种特殊情况，其一，是位于极地区域(即纬度超过70度的区域)内，由于卫星的高速运动，天线系统难以实时跟踪卫星位置，而且，极地区域内的用户通信链接需求也是极少的，因此需要将轨间ISL断开，所以，处于极地地区内的卫星只具有两条轨内ISL；其二，是位于卫星网络反向缝两侧的卫星，由于反向缝两侧的卫星相对速度是极大的，因此，缝间两侧的星间链路并不建立，所以此位置的卫星只具有三条星间链路。同时需要说明的是，轨内星间链路长度是一定的，其连接也是较稳定的，而轨间星间链路的长度是随纬度的增加而减少变化的。

S12、选取每个轨道面的轨道发言人卫星(Orbit speaker)。

本发明实施例中，对于轨道发言人卫星的实际选取，需要考虑以下几点因素：(1)如图3所示，全球热点区域的分布是不均衡的，北半球分布着较为密集的业务需求，而南半球的业务需求相对较少，需要使网络中路由状态信息的收集与分发不影响热点区域内的卫星网络质量；(2)同时，在Walker star星座中，卫星进入极地区域时是会断开轨间星间链路的；(3)靠近赤道附近的卫星轨道之间的星间链路也是较长的。因此，本发明实施例将轨道发言人卫星的职务限定在从北向南运行且处于南半球的负载较轻卫星当中。同时，为了避免由于卫星进入极地区域而转交轨道发言人职务的情况频繁发生，断开链路两端的轨道发言人卫星将轨道发言人职务转交至由北向南运动且位于南半球纬度最低的卫星。因为卫星的运动具有周期性和可预测性的特点，因此卫星可以精确获取其他卫星的地理位置，从而可以得知应将轨道发言人职务应该转交至具体的哪一颗卫星。

S13、通过每个轨道面的轨道发言人卫星收集对应轨道面内所有其他卫星的卫星链路状态报告，并与自身的卫星链路状态报告汇总，形成本轨道面的轨道面链路状态报告。

步骤S13包括以下分步骤S131～S134：

S131、在每个轨道面内，通过每颗卫星计算自身的卫星链路状态报告，并将其发送至距离轨道发言人卫星最近的相邻卫星。

S132、相邻卫星接收到卫星链路状态报告后，判断是否曾经接收过该卫星链路状态报告，若是则丢弃该卫星链路状态报告，并继续等待接收其他卫星发送的卫星链路状态报告，否则进入步骤S133。

S133、判断相邻卫星自身的卫星链路状态报告是否已发送，若是则只将相邻卫星接收到的卫星链路状态报告发送至下一颗相邻卫星，进入步骤S134，否则将相邻卫星自身的卫星链路状态报告及其接收到的卫星链路状态报告一起发送至下一颗相邻卫星，进入步骤S134。

S134、重复步骤S131～S133，直到轨道发言人卫星获取到本轨道面内所有其他卫星的卫星链路状态报告，并将其与自身的卫星链路状态报告汇总，形成本轨道面的轨道面链路状态报告。

本发明实施例中，对于每个轨道面上路由状态信息的收集而言，是通过每个轨道面轨道发言人卫星收集对应轨道面内所有其他卫星的路由状态信息(卫星链路状态报告S_LSA)，并与自身的路由状态信息汇总后，从而形成的本轨道面上所有卫星链路状态报告信息集合(轨道面链路状态报告P_LSA)的，同时，每颗卫星也是会以一定的频率发送自身S_LSA给轨道发言人卫星。接下来以图4为例，解释轨道发言人卫星是如何收集轨道面其他卫星的S_LSA，进而生成P_LSA的。卫星U在计算好自身的卫星链路状态报告S_LSA(U)后，可将S_LSA(U)发送至其相邻卫星V或W，具体发送至卫星V还是卫星W则取决于这两颗相邻卫星V和W哪颗距离该轨道面内的轨道发言人卫星最近，如图4所示，卫星V距离轨道发言人卫星最近，那么，卫星U则将S_LSA(U)发送至卫星V。卫星V在收到S_LSA(U)后，首先会检查自己是否曾经收到过该信息，若收到过则将该信息丢弃。如果卫星V并未收到过该信息，且自身的S_LSA(V)也尚未发送，则将自己的卫星链路状态报告连同接收到的卫星U的卫星链路状态报告一起发送至下一颗相邻卫星，否则，只将卫星U的S_LSA(U)发送至下一颗相邻卫星。这样一来，经过有限的时间后，轨道发言人卫星将获取本轨道内所有其他卫星的卫星链路状态报告，同时结合自身的卫星链路状态报告生成本轨道面的轨道面链路状态报告P_LSA。

S14、通过每个轨道面的轨道发言人卫星将本轨道面的轨道面链路状态报告发送至相邻轨道面。

S15、通过每个轨道面的轨道发言人卫星接收来自其他轨道面的轨道面链路状态报告，经过汇总完成全网链路状态信息库的构建。

步骤S15包括以下分步骤S151～S155：

S151、在每个轨道面内，通过每颗卫星接收来自其他轨道面的轨道面链路状态报告。

S152、判断是否曾经接收过该轨道面链路状态报告，若是则丢弃该轨道面链路状态报告，并返回步骤S151继续等待接收来自其他轨道面的轨道面链路状态报告，否则进入步骤S153。

S153、判断该接收轨道面链路状态报告的卫星是否为其所在轨道面的轨道发言人卫星，若是则进入步骤S154，否则向其所在轨道面的轨道发言人卫星方向转发该轨道面链路状态报告，并返回步骤S151。

S154、存储该轨道面链路状态报告，并将其转发至下一个相邻轨道面。

S155、重复步骤S151～S154，直到每个轨道面的轨道发言人卫星都接收到来自LEO卫星网络内所有其他轨道面的轨道面链路状态报告，并将轨道面链路状态报告进行汇总，完成全网链路状态信息库的构建。

本发明实施例中，卫星链路状态报告的计算公式为：

所述轨道面链路状态报告的计算公式为：

P_LSA(m)＝{S_LSA(x)|x为轨道面m上的卫星}

其中S_LSA(i)表示卫星i的链路状态报告，

S16、通过每颗卫星接收来自其所在轨道面的轨道发言人卫星发送的最新全网链路状态信息库，实现全网链路状态信息库的周期性更新。

本发明实施例中，每颗轨道发言人卫星在完成NSB更新后，都会通过轨内ISL将周期更新后的NSB分发传送至该轨道面的每颗卫星，这样，LEO卫星网络中的每颗卫星都能以较小开销代价实现实时更新获取NSB，从而为后期具体路由表项的计算做好前期准备。

S2、令LEO卫星网络中的LEO卫星等待触发路由。

S3、判断地面用户是否有新的呼叫或呼叫切换到达，若是则进入步骤S4，否则返回步骤S2。

S4、构建多约束QoS最优路径路由模型。

多约束QoS最优路径路由模型的计算公式为：

min Cost(p)

本发明实施例提出的多约束QoS最优路径路由模型实现了在满足时延、带宽这两个重要QoS参数约束，即保证路由传输路径p服务质量的前提下，尽量引导全球数据流量均衡分布，降低卫星发生拥塞的概率，减小数据传输的丢包率，提高卫星网络数据传输的可靠性。其中p(s,d)表示源卫星节点s和目的卫星节点d之间的一条可用路径p，Cost(p)表示路径p的总代价值，且：

其中Cost

Cost

其中TD

TD

本发明实施例中，鉴于卫星网络拓扑以及流量负载的持续变化，选择恰当的路径计算代价度量对路由算法性能有很大的影响，因此需要设计合理的星间链路复合时延代价函数，其中传播时延仅仅反映的是网络拓扑的物理连接变化，而队列时延仅仅反映的是网络流量变化的情况，因此，本发明实施例选择星间链路ISL传播时延，以及输出缓冲队列时延作为复合链路时延代价因子，这样的时延代价函数设计保证，既能反映卫星网络拓扑物理连接变化，亦能反映网络流量负载的变化。其中TD

其中

星间链路可用带宽，即链路剩余带宽，为凹性度量参数，且链路剩余带宽越大，其服务性能越好，越不易发生链路堵塞、丢包等情况。其中

其中lat

全球大多数热点是分布在赤道和50°N之间范围内的，因此，通常覆盖0°N～50°N区域的卫星会变得较为拥挤、繁忙，但是其他区域卫星却未得到充分利用。由于人口分布、经济与技术发展等因素，覆盖南半球上空的卫星要比覆盖北半球上空的卫星流量负载轻得多。根据图3全球热点区域估计分布图显示，本发明实施例将南半球地区视为非热点区域，而将北半球的北美、欧洲、中东和东亚地区视为热点区域，北半球的其他地区则被划分为非热点区域。

针对全球流量分布不均衡的问题，我们考虑将卫星的地理位置因素引入到链路代价计算中去，即引入链路代价修正因子γ

S5、利用链路最小带宽约束对卫星拓扑进行剪枝预处理，将多约束QoS最优路径路由模型简化为时延约束最小路径代价路由(DCLC，Delay Constrained Least Cost)模型。

由于在建立的多约束QoS最优路径路由模型中，存在着链路可用带宽Band(i,j)这个参数，且其为凹性度量参数，为了降低路由模型求解的难度与复杂度，所以每颗接入卫星在得到地面通信用户路由请求，获得具体QoS要求约束参数后，在执行具体路由计算之前，需要对卫星拓扑进行剪枝预处理，将多约束QoS最优路径路由模型简化为时延约束最小路径代价路由模型。

步骤S5包括以下分步骤S51～S52：

S51、利用用户通信业务最小要求可用带宽Band

在新的全局卫星网络拓扑图G

S52、在剪枝预处理后的全局网络状态拓扑图G

p

其中p

S6、根据基于合成成本代价的拉格朗日松弛算法对时延约束最小路径代价路由模型进行求解，得到最优路由路径p

虽然在步骤S5中已经删除了带宽条件这一约束，一定程度上降低了路由模型求解的难度，但是DCLC问题，仍然无法在多项式时间内求出精确解，而且其已经被证明为是一个NP_hard问题，因此，本发明实施例提出采用启发式的算法来完成求解时延约束最小路径代价路由模型，计算求得问题的近似解。在实际设计中，本发明实施例最终选择了采用基于拉格朗日松弛的启发式算法来完成对最优路由路径的计算。

拉格朗日松弛算法是一种求解问题下界的方法，它具有较低的时间复杂度和较优的计算性能，其主要思想是把约束条件吸收到目标函数中，通过减少约束条件的方式，以降低原始问题的计算复杂度，最终使减少约束条件后的问题能够在多项式时间内求得问题的最优解。

步骤S6包括以下分步骤S61～S69：

S61、将时延约束最小路径代价路由模型转化为路由模型L

其中L(θ)表示把时延约束条件吸收到目标函数后形成的新的线性函数，且：

L(θ)＝min{Cost

＝{Cost

其中θ表示拉格朗日乘子，Cost

其中Cost

由拉格朗日松弛算法的相关定理证明可知，

S62、令拉格朗日乘子θ＝0，将链路代价Cost

S63、判断最短路径p

S64、将复合时延代价TD

S65、判断最短路径p

S66、通过迭代替换最短路径p

其中Cost(p

S67、将拉格朗日乘子θ代入合成链路代价函数Cost

S68、判断最短路径r的合成链路代价之和Cost

S69、判断最短路径r的时延TD(r)是否满足TD(r)≤TD

本发明实施例中，对于DCLC问题，通过基于拉格朗日松弛的启发式算法对目标函数求解，该问题的时间复杂度为O([E+VlogV]

S7、判断最优路由路径p

S8、通过最优路由路径p

S9、拒绝此次路由请求，结束流程。

本发明实施例提供的LEO卫星网络可靠性路由方法的可靠性保证主要体现在三个方面：

(1)卫星网络中的每颗LEO卫星在得到周期性更新的NSB后，用户所需实际路由表项的计算任务将分散至各个LEO卫星当中去，即当地面用户发起通信业务请求时，使得某颗LEO卫星成为用户的接入卫星(源节点卫星)时，该卫星将独立独自计算以自己为源节点的源路由形式路由转发表项。轨道发言人卫星将不再为轨道面内所有其他卫星集中计算它们的全局路由表项，只负责完成路由状态信息的收集与分发，避免了因将过多的星上计算执行任务累加于单颗中心控制卫星上，防止控制卫星因计算任务负载过大造成故障拥塞或遭受网络恶意攻击等时，使得所辖局部范围内的全部成员卫星的路由转发功能失效、瘫痪，就算采用及时移交计算任务给其他局部中心控制卫星的处理方式，也难免带来较大路由等待时延，影响用户通信的体验感，所以以这种分散式路由计算执行者的方式提高了路由计算的可靠性。

(2)由于全球热点区域的分布是不均衡的，大多数热点是分布在赤道和50°N之间范围内，所以南半球上空卫星的流量负载压力要远小于北半球上空的卫星，因此为了实现引导全球流量的均衡分布，本发明将卫星所处地理位置这个因素考虑进来，提出了一个链路代价修正因子γ

(3)QoS通常是对通信网络中数据传输质量的描述，是对数据进行传输中极其重要的量化衡量标准，为了提高用户数据包路由传输过程中的可靠性，本发明设计选择综合服务性能最好的转发路径来完成数据的传输，因为服务质量高的路径上其发生拥塞、丢包的概率也是极小的，能给用户带来更佳的服务体验，选择约束的QoS参数越多，其QoS越能得到更高效、可靠的保障，但是其求解难度也会随之增大，因此本发明仅考虑将实际路由设计问题中最重要也是最常用的度量参数链路时延、带宽引入进来，来完成多约束条件的建立，以此来保证算法搜寻综合服务性能最好的路径。

本领域的普通技术人员将会意识到，这里所述的实施例是为了帮助读者理解本发明的原理，应被理解为本发明的保护范围并不局限于这样的特别陈述和实施例。本领域的普通技术人员可以根据本发明公开的这些技术启示做出各种不脱离本发明实质的其它各种具体变形和组合，这些变形和组合仍然在本发明的保护范围内。