本发明公开了一种基于QoS保障的LEO卫星网络可靠性路由方法，通过引导热点区域流量向非热点区域转移，且在选路同时，设计严格的服务质量QoS约束，来完成星间路由路径的搜寻，以保证找到的路径具有最优的服务质量，尽量途经轻量化负载任务的卫星，降低卫星发生拥塞概率，继而减小丢包率，提高路由转发路径的可靠性。
1.基于QoS保障的LEO卫星网络可靠性路由方法，其特征在于，包括以下步骤：S1、构建LEO卫星网络，并对LEO卫星网络中的全网链路状态信息库进行周期性更新；
S2、令LEO卫星网络中的LEO卫星等待触发路由；
S3、判断地面用户是否有新的呼叫或呼叫切换到达，若是则进入步骤S4，否则返回步骤S2；
S5、利用链路最小带宽约束对卫星拓扑进行剪枝预处理，将多约束QoS最优路径路由模型简化为时延约束最小路径代价路由模型；
S6、根据基于合成成本代价的拉格朗日松弛算法对时延约束最小路径代价路由模型进*
S7、判断最优路由路径p是否存在，若是则进入步骤S8，否则进入步骤S9；
S8、通过最优路由路径p完成此次LEO卫星网络的星间可靠路由通信，结束流程；
所述步骤S4中的多约束QoS最优路径路由模型的计算公式为：min Cost(p)
其中p(s,d)表示源卫星节点s和目的卫星节点d之间的一条可用路径p，Cost(p)表示路径p的总代价值，且：
其中Costij表示卫星i与卫星j之间的链路代价函数，且：Costij＝γij×TDij其中TDij表示卫星i与卫星j之间存在链路 上的复合时延代价函数，其计算公式为：
TDij(t)＝PDij(t)+QDij(t)其中TDij(t)表示链路 的总时延，PDij(t)表示链路 的传播时延，QDij(t)表示链路 的输出队列时延，且：
其中 表示卫星i与卫星j之间的物理距离，c为光速，t表示t时刻，Δt表示LEO卫星网络进行全网链路状态信息库更新的时间间隔，q(y)表示在时刻y时输出队列中的传输分组数，Pavg表示输出队列中已有传输分组的平均长度，BW表示星间链路容量；TD(p)表示路径p的累计时延，TDmax表示用户通信业务要求的最大容忍时延；Band(i,j)表示卫星i与卫星j之间的链路可用带宽，其计算公式为：其中 表示卫星i与卫星j之间的链路总带宽， 表示卫星i与卫星j之间的链路已用带宽；Band(p)表示路径p的实际可用带宽，Bandmin表示用户通信业务最小要求可用带宽；γij表示卫星i与卫星j之间的链路代价修正因子，其计算公式为：其中lati表示卫星i的纬度，loni表示卫星i的经度。
2.根据权利要求1所述的LEO卫星网络可靠性路由方法，其特征在于，所述步骤S1包括以下分步骤：
S11、通过M×N颗LEO卫星构建LEO卫星网络，其中M为LEO卫星网络的轨道面数，N为每个轨道面上的卫星数；
S13、通过每个轨道面的轨道发言人卫星收集对应轨道面内所有其他卫星的卫星链路状态报告，并与自身的卫星链路状态报告汇总，形成本轨道面的轨道面链路状态报告；
S14、通过每个轨道面的轨道发言人卫星将本轨道面的轨道面链路状态报告发送至相邻轨道面；
S15、通过每个轨道面的轨道发言人卫星接收来自其他轨道面的轨道面链路状态报告，经过汇总完成全网链路状态信息库的构建；
S16、通过每颗卫星接收来自其所在轨道面的轨道发言人卫星发送的最新全网链路状态信息库，实现全网链路状态信息库的周期性更新。
3.根据权利要求2所述的LEO卫星网络可靠性路由方法，其特征在于，所述步骤S13包括以下分步骤：
S131、在每个轨道面内，通过每颗卫星计算自身的卫星链路状态报告，并将其发送至距离轨道发言人卫星最近的相邻卫星；
S132、相邻卫星接收到卫星链路状态报告后，判断是否曾经接收过该卫星链路状态报告，若是则丢弃该卫星链路状态报告，并继续等待接收其他卫星发送的卫星链路状态报告，否则进入步骤S133；
S133、判断相邻卫星自身的卫星链路状态报告是否已发送，若是则只将相邻卫星接收到的卫星链路状态报告发送至下一颗相邻卫星，进入步骤S134，否则将相邻卫星自身的卫星链路状态报告及其接收到的卫星链路状态报告一起发送至下一颗相邻卫星，进入步骤S134；
S134、重复步骤S131～S133，直到轨道发言人卫星获取到本轨道面内所有其他卫星的卫星链路状态报告，并将其与自身的卫星链路状态报告汇总，形成本轨道面的轨道面链路状态报告。
4.根据权利要求2所述的LEO卫星网络可靠性路由方法，其特征在于，所述步骤S15包括以下分步骤：
S151、在每个轨道面内，通过每颗卫星接收来自其他轨道面的轨道面链路状态报告；
S152、判断是否曾经接收过该轨道面链路状态报告，若是则丢弃该轨道面链路状态报告，并返回步骤S151继续等待接收来自其他轨道面的轨道面链路状态报告，否则进入步骤S153；
S153、判断该接收轨道面链路状态报告的卫星是否为其所在轨道面的轨道发言人卫星，若是则进入步骤S154，否则向其所在轨道面的轨道发言人卫星方向转发该轨道面链路状态报告，并返回步骤S151；
S154、存储该轨道面链路状态报告，并将其转发至下一个相邻轨道面；
S155、重复步骤S151～S154，直到每个轨道面的轨道发言人卫星都接收到来自LEO卫星网络内所有其他轨道面的轨道面链路状态报告，并将轨道面链路状态报告进行汇总，完成全网链路状态信息库的构建。
5.根据权利要求2‑4任一所述的LEO卫星网络可靠性路由方法，其特征在于，所述卫星链路状态报告的计算公式为：
所述轨道面链路状态报告的计算公式为：P_LSA(m)＝{S_LSA(x)|x为轨道面m上的卫星}其中S_LSA(i)表示卫星i的链路状态报告， 表示卫星i的邻居卫星x的当前逻辑地址，0≤mx≤M‑1,0≤nx≤N‑1，TDix表示卫星i与其邻居卫星x之间存在链路ISLi→x上的复合时延代价函数，Band(i,x)表示卫星i与其邻居卫星x之间的链路可用带宽，γix表示卫星i与其邻居卫星x之间的链路代价修正因子，P_LSA(m)表示轨道面m的链路状态报告，S_LSA(x)表示轨道面m上的卫星x的链路状态报告。
6.根据权利要求1所述的LEO卫星网络可靠性路由方法，其特征在于，所述步骤S5包括以下分步骤：
S51、利用用户通信业务最小要求可用带宽Bandmin对源节点卫星当前所具有的全局网络状态拓扑图G(V,E)中不满足链路最小带宽约束的星间链路进行剪枝预处理，得到剪枝预* * * *
处理后的全局网络状态拓扑图G (V ,E)，其中V和V 均表示LEO卫星网络中卫星节点的集*
S52、在剪枝预处理后的全局网络状态拓扑图G (V ,E)上，将多约束QoS最优路径路由模型简化为时延约束最小路径代价路由模型：*
p＝min{Cost(p):p∈p(s,d)&TD(p)≤TDmax}*
7.根据权利要求6所述的LEO卫星网络可靠性路由方法，其特征在于，所述步骤S6包括以下分步骤：
S61、将时延约束最小路径代价路由模型p转化为路由模型L：其中L(θ)表示把时延约束条件吸收到目标函数后形成的新的线性函数，且：L(θ)＝min{Costθ(p)‑θTDmax:p∈p(s,d)} ＝{Costθ(p):p∈p(s,d)}‑θTDmax其中θ表示拉格朗日乘子，Costθ(p)表示路径p所包含的合成链路代价之和，且：其中Costθ＝Costij+θTDij表示合成链路代价函数；
S62、令拉格朗日乘子θ＝0，将链路代价Costij作为Dijkstra算法的输入，计算得到最短路径pcost；
S63、判断最短路径pcost的时延TD(pcost)是否满足TD(pcost)≤TDmax，若是则将最短路径*
pcost作为最优路由路径p，否则进入步骤S64；
S64、将复合时延代价TDij为Dijkstra算法的输入，计算得到最短路径pTD；
S65、判断最短路径pTD的时延TD(pTD)是否满足TD(pTD)≤TDmax，若是则进入步骤S66，否*
S66、通过迭代替换最短路径pcost和最短路径pTD，寻找得到使得最短路径pcost与最短路径pTD的合成链路代价函数Costθ取得最小值，且使得线性函数L(θ)取得最大值的拉格朗日乘子θ：
其中Cost(pcost)表示最短路径pcost的代价值，Cost(pTD)表示最短路径pTD的代价值；
S67、将拉格朗日乘子θ代入合成链路代价函数Costθ，并将合成链路代价函数Costθ作为Dijkstra算法的输入，计算得到最短路径r；
S68、判断最短路径r的合成链路代价之和Costθ(r)是否满足Costθ(r)＝Costθ(pcost)，若*
是则将最短路径pTD作为最优路由路径p，否则进入步骤S69；
S69、判断最短路径r的时延TD(r)是否满足TD(r)≤TDmax，若是则将最短路径r作为pTD的值，否则将最短路径r作为pcost的值，反复迭代步骤S66～S68，直到计算出满足条件的最优*
基于QoS保障的LEO卫星网络可靠性路由方法
技术领域
[0001] 本发明属于LEO卫星通信技术领域，具体涉及一种基于QoS保障的LEO卫星网络可靠性路由方法的设计。
背景技术
[0002] 随着空间信息技术的迅猛发展，低轨(LEO，Low Earth Orbit)卫星通信系统在全球通信、导航定位、气象预测、灾害监测和军事应用等方面发挥着越来越重要的作用，而作
为LEO卫星通信网络关键技术之一的星间路由算法，则是提升整个卫星通信网络性能的核
心因素。但是，由于外太空卫星网络所处的环境是较为恶劣，也是较为复杂的，存在着诸如
网络拓扑频繁动态变化、星上负载不均衡、电磁干扰、卫星节点和链路易发生故障等情况，
所以，为了保证提供给地面用户可靠、有效的通信服务，获得较佳的用户体验感，需要选择
一条最优的路由路径来完成源目卫星之间数据包的高效传输。
发明内容
[0003] 本发明的目的是提出一种基于QoS保障的LEO卫星网络可靠性路由方法，使得LEO卫星网络能够提供给用户一个稳定的、可靠的高质量体验感的通信服务，完成源目卫星之
间数据包的路由转发。
[0004] 本发明的技术方案为：基于QoS保障的LEO卫星网络可靠性路由方法，包括以下步骤：
[0005] S1、构建LEO卫星网络，并对LEO卫星网络中的全网链路状态信息库进行周期性更新。
[0006] S2、令LEO卫星网络中的LEO卫星等待触发路由。
[0007] S3、判断地面用户是否有新的呼叫或呼叫切换到达，若是则进入步骤S4，否则返回步骤S2。
[0008] S4、构建多约束QoS最优路径路由模型。
[0009] S5、利用链路最小带宽约束对卫星拓扑进行剪枝预处理，将多约束QoS最优路径路由模型简化为时延约束最小路径代价路由模型。
[0010] S6、根据基于合成成本代价的拉格朗日松弛算法对时延约束最小路径代价路由模*
型进行求解，得到最优路由路径p。
[0011] S7、判断最优路由路径p*是否存在，若是则进入步骤S8，否则进入步骤S9。
[0012] S8、通过最优路由路径p*完成此次LEO卫星网络的星间可靠路由通信，结束流程。
[0013] S9、拒绝此次路由请求，结束流程。
[0014] 进一步地，步骤S1包括以下分步骤：
[0015] S11、通过M×N颗LEO卫星构建LEO卫星网络，其中M为LEO卫星网络的轨道面数，N为每个轨道面上的卫星数。
[0016] S12、选取每个轨道面的轨道发言人卫星。
[0017] S13、通过每个轨道面的轨道发言人卫星收集对应轨道面内所有其他卫星的卫星链路状态报告，并与自身的卫星链路状态报告汇总，形成本轨道面的轨道面链路状态报告。
[0018] S14、通过每个轨道面的轨道发言人卫星将本轨道面的轨道面链路状态报告发送至相邻轨道面。
[0019] S15、通过每个轨道面的轨道发言人卫星接收来自其他轨道面的轨道面链路状态报告，经过汇总完成全网链路状态信息库的构建。
[0020] S16、通过每颗卫星接收来自其所在轨道面的轨道发言人卫星发送的最新全网链路状态信息库，实现全网链路状态信息库的周期性更新。
[0021] 进一步地，步骤S13包括以下分步骤：
[0022] S131、在每个轨道面内，通过每颗卫星计算自身的卫星链路状态报告，并将其发送至距离轨道发言人卫星最近的相邻卫星。
[0023] S132、相邻卫星接收到卫星链路状态报告后，判断是否曾经接收过该卫星链路状态报告，若是则丢弃该卫星链路状态报告，并继续等待接收其他卫星发送的卫星链路状态
报告，否则进入步骤S133。
[0024] S133、判断相邻卫星自身的卫星链路状态报告是否已发送，若是则只将相邻卫星接收到的卫星链路状态报告发送至下一颗相邻卫星，进入步骤S134，否则将相邻卫星自身
的卫星链路状态报告及其接收到的卫星链路状态报告一起发送至下一颗相邻卫星，进入步
骤S134。
[0025] S134、重复步骤S131～S133，直到轨道发言人卫星获取到本轨道面内所有其他卫星的卫星链路状态报告，并将其与自身的卫星链路状态报告汇总，形成本轨道面的轨道面
链路状态报告。
[0026] 进一步地，步骤S15包括以下分步骤：
[0027] S151、在每个轨道面内，通过每颗卫星接收来自其他轨道面的轨道面链路状态报告。
[0028] S152、判断是否曾经接收过该轨道面链路状态报告，若是则丢弃该轨道面链路状态报告，并返回步骤S151继续等待接收来自其他轨道面的轨道面链路状态报告，否则进入
步骤S153。
[0029] S153、判断该接收轨道面链路状态报告的卫星是否为其所在轨道面的轨道发言人卫星，若是则进入步骤S154，否则向其所在轨道面的轨道发言人卫星方向转发该轨道面链
路状态报告，并返回步骤S151。
[0030] S154、存储该轨道面链路状态报告，并将其转发至下一个相邻轨道面。
[0031] S155、重复步骤S151～S154，直到每个轨道面的轨道发言人卫星都接收到来自LEO卫星网络内所有其他轨道面的轨道面链路状态报告，并将轨道面链路状态报告进行汇总，
完成全网链路状态信息库的构建。
[0032] 进一步地，卫星链路状态报告的计算公式为：
[0033]
[0034] 所述轨道面链路状态报告的计算公式为：
[0035] P_LSA(m)＝{S_LSA(x)|x为轨道面m上的卫星}
[0036] 其中S_LSA(i)表示卫星i的链路状态报告， 表示卫星i的邻居卫星x的当前逻辑地址，0≤mx≤M‑1,0≤nx≤N‑1，TDix表示卫星i与其邻居卫星x之间存在链路ISLi→x上的复
合时延代价函数，Band(i,x)表示卫星i与其邻居卫星x之间的链路可用带宽，γix表示卫星i
与其邻居卫星x之间的链路代价修正因子，P_LSA(m)表示轨道面m的链路状态报告，S_LSA
(x)表示轨道面m上的卫星x的链路状态报告。
[0037] 进一步地，步骤S4中的多约束QoS最优路径路由模型的计算公式为：
[0038] min Cost(p)
[0039]
[0040]
[0041] 其中p(s,d)表示源卫星节点s和目的卫星节点d之间的一条可用路径p，Cost(p)表示路径p的总代价值，且：
[0042]
[0043] 其中Costij表示卫星i与卫星j之间的链路代价函数，且：
[0044] Costij＝γij×TDij
[0045] 其中TDij表示卫星i与卫星j之间存在链路 上的复合时延代价函数，其计算公式为：
[0046] TDij(t)＝PDij(t)+QDij(t)
[0047] 其中TDij(t)表示链路 的总时延，PDij(t)表示链路 的传播时延，QDij(t)表示链路 的输出队列时延，且：
[0048]
[0049]
[0050] 其中 表示卫星i与卫星j之间的物理距离，c为光速，t表示t时刻，Δt表示LEO卫星网络进行全网链路状态信息库更新的时间间隔，q(y)表示在时刻y时输出队列中的
传输分组数，Pavg表示输出队列中已有传输分组的平均长度，BW表示星间链路容量；TD(p)表
示路径p的累计时延，TDmax表示用户通信业务要求的最大容忍时延；Band(i,j)表示卫星i与
卫星j之间的链路可用带宽，其计算公式为：
[0051]
[0052] 其中 表示卫星i与卫星j之间的链路总带宽， 表示卫星i与卫星j之间的链路已用带宽；Band(p)表示路径p的实际可用带宽，Bandmin表示用户通信业务
最小要求可用带宽；γij表示卫星i与卫星j之间的链路代价修正因子，其计算公式为：
[0053]
[0054] 其中lati表示卫星i的纬度，loni表示卫星i的经度。
[0055] 进一步地，步骤S5包括以下分步骤：
[0056] S51、利用用户通信业务最小要求可用带宽Bandmin对源节点卫星当前所具有的全局网络状态拓扑图G(V,E)中不满足链路最小带宽约束的星间链路进行剪枝预处理，得到剪
* * * *
枝预处理后的全局网络状态拓扑图G (V ,E)，其中V和V均表示LEO卫星网络中卫星节点的
*
集合，E和E均表示LEO卫星网络中链路的集合。
[0057] S52、在剪枝预处理后的全局网络状态拓扑图G*(V*,E*)上，将多约束QoS最优路径路由模型简化为时延约束最小路径代价路由模型：
[0058] p*＝min{Cost(p):p∈p(s,d)&TD(p)≤TDmax}
[0059] 其中p*表示最优路由路径。
[0060] 进一步地，步骤S6包括以下分步骤：
[0061] S61、将时延约束最小路径代价路由模型p*转化为路由模型L*：
[0062]
[0063] 其中L(θ)表示把时延约束条件吸收到目标函数后形成的新的线性函数，且：
[0064] L(θ)＝min{Costθ(p)‑θTDmax:p∈p(s,d)}
[0065] ＝{Costθ(p):p∈p(s,d)}‑θTDmax
[0066] 其中θ表示拉格朗日乘子，Costθ(p)表示路径p所包含的合成链路代价之和，且：
[0067]
[0068] 其中Costθ＝Costij+θTDij表示合成链路代价函数。
[0069] S62、令拉格朗日乘子θ＝0，将链路代价Costij作为Dijkstra算法的输入，计算得到最短路径pcost。
[0070] S63、判断最短路径pcost的时延TD(pcost)是否满足TD(pcost)≤TDmax，若是则将最短*
路径pcost作为最优路由路径p，否则进入步骤S64。
[0071] S64、将复合时延代价TDij为Dijkstra算法的输入，计算得到最短路径pTD。
[0072] S65、判断最短路径pTD的时延TD(pTD)是否满足TD(pTD)≤TDmax，若是则进入步骤*
S66，否则最优路由路径p不存在，进入步骤S7。
[0073] S66、通过迭代替换最短路径pcost和最短路径pTD，寻找得到使得最短路径pcost与最短路径pTD的合成链路代价函数Costθ取得最小值，且使得线性函数L(θ)取得最大值的拉格
朗日乘子θ：
[0074]
[0075] 其中Cost(pcost)表示最短路径pcost的代价值，Cost(pTD)表示最短路径pTD的代价值。
[0076] S67、将拉格朗日乘子θ代入合成链路代价函数Costθ，并将合成链路代价函数Costθ作为Dijkstra算法的输入，计算得到最短路径r。
[0077] S68、判断最短路径r的合成链路代价之和Costθ(r)是否满足Costθ(r)＝Costθ*
(pcost)，若是则将最短路径pTD作为最优路由路径p，否则进入步骤S69。
[0078] S69、判断最短路径r的时延TD(r)是否满足TD(r)≤TDmax，若是则将最短路径r作为pTD的值，否则将最短路径r作为pcost的值，反复迭代步骤S66～S68，直到计算出满足条件的
*
最优路由路径p。
[0079] 本发明的有益效果是：
[0080] (1)本发明通过分散式的卫星路由表计算执行者分担路由计算压力，降低了局部范围内卫星路由功能全部失效的风险，使得用户接入卫星(即源卫星)能够独立计算路由转
发表。
[0081] (2)本发明通过引导热点区域流量向非热点区域转移，实现了全球流量均衡分布，能够轻量化全网卫星流量负载压力，减小了卫星发生拥塞概率，降低了丢包率。
[0082] (3)本发明通过设置高服务质量QoS约束，保证了搜寻路径的服务质量，使得路由路径发生拥塞概率极小，提高了路由转发过程中的可靠性。
[0083] 综上，本发明使得LEO卫星网络能够提供给用户一个稳定的、可靠的高质量体验感的通信服务，从而完成源目卫星之间数据包的路由转发。
附图说明
[0084] 图1所示为本发明实施例提供的基于QoS保障的LEO卫星网络可靠性路由方法流程图。
[0085] 图2所示为本发明实施例提供的Walker star星座模型示意图。
[0086] 图3所示为本发明实施例提供的全球热点区域分布图。
[0087] 图4所示为本发明实施例提供的轨道面路由状态信息构建示意图。
具体实施方式
[0088] 现在将参考附图来详细描述本发明的示例性实施方式。应当理解，附图中示出和描述的实施方式仅仅是示例性的，意在阐释本发明的原理和精神，而并非限制本发明的范
围。
[0089] 在描述本发明的具体实施例之前，首先对本发明出现的一些缩略语进行解释，以便更好的理解本发明：
[0090] LEO：Low Earth Orbit，低轨卫星；
[0091] QoS：Quality of Service，服务质量；
[0092] ISL：Inter‑Satellite Link，星间链路；
[0093] S_LSA：Satellite Link State Advertisement，卫星链路状态报告；
[0094] P_LSA：Plane Link State Advertisement，轨道面链路状态报告；
[0095] NSB：Network State Base，全网状态信息库；
[0096] LARAC：Lagrange Relaxation based Aggregated Cost，基于合成成本代价的拉格朗日松弛算法。
[0097] 本发明实施例提供了一种基于QoS保障的LEO卫星网络可靠性路由方法，如图1所示，包括以下步骤S1～S9：
[0098] S1、构建LEO卫星网络，并对LEO卫星网络中的全网链路状态信息库进行周期性更新。
[0099] 步骤S1包括以下分步骤S11～S16：
[0100] S11、通过M×N颗LEO卫星构建LEO卫星网络，其中M为LEO卫星网络的轨道面数，N为每个轨道面上的卫星数。
[0101] 本发明实施例中，采用Walker star星座模型作为实验场景构建LEO卫星网络，如图2所示，设定该卫星网络中共有M×N颗卫星，为了简化由于卫星周期性运动导致拓扑动态
变化带来的路由编址设计难题，因此引入逻辑地址概念来标定每个卫星的路由转发地址，
逻辑地址用Sm,n表示，其中，m表示第m个轨道面，n表示在第m个轨道面上的第n颗卫星，且0≤
m≤M‑1,0≤n≤N‑1，m和n都为正整数。基于逻辑地址的设计理念，在每次卫星网络进行周期
性链路状态信息更新后，可将此时的卫星网络拓扑看成一张由逻辑地址来标定卫星路由地
址的静态逻辑平面，方便后续路由算法的设计。
[0102] 卫星通信网络中的链路ISL包括：轨内星间链路(Intra‑Plane ISL)以及轨间星间链路(Inter‑Plane ISL)，正常情况下，每颗卫星是具有四条星间链路的，即两条轨内ISL以
及两条轨间ISL。但是，也存在两种特殊情况，其一，是位于极地区域(即纬度超过70度的区
域)内，由于卫星的高速运动，天线系统难以实时跟踪卫星位置，而且，极地区域内的用户通
信链接需求也是极少的，因此需要将轨间ISL断开，所以，处于极地地区内的卫星只具有两
条轨内ISL；其二，是位于卫星网络反向缝两侧的卫星，由于反向缝两侧的卫星相对速度是
极大的，因此，缝间两侧的星间链路并不建立，所以此位置的卫星只具有三条星间链路。同
时需要说明的是，轨内星间链路长度是一定的，其连接也是较稳定的，而轨间星间链路的长
度是随纬度的增加而减少变化的。
[0103] S12、选取每个轨道面的轨道发言人卫星(Orbit speaker)。
[0104] 本发明实施例中，对于轨道发言人卫星的实际选取，需要考虑以下几点因素：(1)如图3所示，全球热点区域的分布是不均衡的，北半球分布着较为密集的业务需求，而南半
球的业务需求相对较少，需要使网络中路由状态信息的收集与分发不影响热点区域内的卫
星网络质量；(2)同时，在Walker star星座中，卫星进入极地区域时是会断开轨间星间链路
的；(3)靠近赤道附近的卫星轨道之间的星间链路也是较长的。因此，本发明实施例将轨道
发言人卫星的职务限定在从北向南运行且处于南半球的负载较轻卫星当中。同时，为了避
免由于卫星进入极地区域而转交轨道发言人职务的情况频繁发生，断开链路两端的轨道发
言人卫星将轨道发言人职务转交至由北向南运动且位于南半球纬度最低的卫星。因为卫星
的运动具有周期性和可预测性的特点，因此卫星可以精确获取其他卫星的地理位置，从而
可以得知应将轨道发言人职务应该转交至具体的哪一颗卫星。
[0105] S13、通过每个轨道面的轨道发言人卫星收集对应轨道面内所有其他卫星的卫星链路状态报告，并与自身的卫星链路状态报告汇总，形成本轨道面的轨道面链路状态报告。
[0106] 步骤S13包括以下分步骤S131～S134：
[0107] S131、在每个轨道面内，通过每颗卫星计算自身的卫星链路状态报告，并将其发送至距离轨道发言人卫星最近的相邻卫星。
[0108] S132、相邻卫星接收到卫星链路状态报告后，判断是否曾经接收过该卫星链路状态报告，若是则丢弃该卫星链路状态报告，并继续等待接收其他卫星发送的卫星链路状态
报告，否则进入步骤S133。
[0109] S133、判断相邻卫星自身的卫星链路状态报告是否已发送，若是则只将相邻卫星接收到的卫星链路状态报告发送至下一颗相邻卫星，进入步骤S134，否则将相邻卫星自身
的卫星链路状态报告及其接收到的卫星链路状态报告一起发送至下一颗相邻卫星，进入步
骤S134。
[0110] S134、重复步骤S131～S133，直到轨道发言人卫星获取到本轨道面内所有其他卫星的卫星链路状态报告，并将其与自身的卫星链路状态报告汇总，形成本轨道面的轨道面
链路状态报告。
[0111] 本发明实施例中，对于每个轨道面上路由状态信息的收集而言，是通过每个轨道面轨道发言人卫星收集对应轨道面内所有其他卫星的路由状态信息(卫星链路状态报告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。
[0112] S14、通过每个轨道面的轨道发言人卫星将本轨道面的轨道面链路状态报告发送至相邻轨道面。
[0113] S15、通过每个轨道面的轨道发言人卫星接收来自其他轨道面的轨道面链路状态报告，经过汇总完成全网链路状态信息库的构建。
[0114] 步骤S15包括以下分步骤S151～S155：
[0115] S151、在每个轨道面内，通过每颗卫星接收来自其他轨道面的轨道面链路状态报告。
[0116] S152、判断是否曾经接收过该轨道面链路状态报告，若是则丢弃该轨道面链路状态报告，并返回步骤S151继续等待接收来自其他轨道面的轨道面链路状态报告，否则进入
步骤S153。
[0117] S153、判断该接收轨道面链路状态报告的卫星是否为其所在轨道面的轨道发言人卫星，若是则进入步骤S154，否则向其所在轨道面的轨道发言人卫星方向转发该轨道面链
路状态报告，并返回步骤S151。
[0118] S154、存储该轨道面链路状态报告，并将其转发至下一个相邻轨道面。
[0119] S155、重复步骤S151～S154，直到每个轨道面的轨道发言人卫星都接收到来自LEO卫星网络内所有其他轨道面的轨道面链路状态报告，并将轨道面链路状态报告进行汇总，
完成全网链路状态信息库的构建。
[0120] 本发明实施例中，卫星链路状态报告的计算公式为：
[0121]
[0122] 所述轨道面链路状态报告的计算公式为：
[0123] P_LSA(m)＝{S_LSA(x)|x为轨道面m上的卫星}
[0124] 其中S_LSA(i)表示卫星i的链路状态报告， 表示卫星i的邻居卫星x的当前逻辑地址，0≤mx≤M‑1,0≤nx≤N‑1，TDix表示卫星i与其邻居卫星x之间存在链路ISLi→x上的复
合时延代价函数，Band(i,x)表示卫星i与其邻居卫星x之间的链路可用带宽，γix表示卫星i
与其邻居卫星x之间的链路代价修正因子，P_LSA(m)表示轨道面m的链路状态报告，S_LSA
(x)表示轨道面m上的卫星x的链路状态报告。
[0125] S16、通过每颗卫星接收来自其所在轨道面的轨道发言人卫星发送的最新全网链路状态信息库，实现全网链路状态信息库的周期性更新。
[0126] 本发明实施例中，每颗轨道发言人卫星在完成NSB更新后，都会通过轨内ISL将周期更新后的NSB分发传送至该轨道面的每颗卫星，这样，LEO卫星网络中的每颗卫星都能以
较小开销代价实现实时更新获取NSB，从而为后期具体路由表项的计算做好前期准备。
[0127] S2、令LEO卫星网络中的LEO卫星等待触发路由。
[0128] S3、判断地面用户是否有新的呼叫或呼叫切换到达，若是则进入步骤S4，否则返回步骤S2。
[0129] S4、构建多约束QoS最优路径路由模型。
[0130] 多约束QoS最优路径路由模型的计算公式为：
[0131] min Cost(p)
[0132]
[0133]
[0134] 本发明实施例提出的多约束QoS最优路径路由模型实现了在满足时延、带宽这两个重要QoS参数约束，即保证路由传输路径p服务质量的前提下，尽量引导全球数据流量均
衡分布，降低卫星发生拥塞的概率，减小数据传输的丢包率，提高卫星网络数据传输的可靠
性。其中p(s,d)表示源卫星节点s和目的卫星节点d之间的一条可用路径p，Cost(p)表示路
径p的总代价值，且：
[0135]
[0136] 其中Costij表示卫星i与卫星j之间的链路代价函数，且：
[0137] Costij＝γij×TDij
[0138] 其中TDij表示卫星i与卫星j之间存在链路 上的复合时延代价函数，其计算公式为：
[0139] TDij(t)＝PDij(t)+QDij(t)
[0140] 本发明实施例中，鉴于卫星网络拓扑以及流量负载的持续变化，选择恰当的路径计算代价度量对路由算法性能有很大的影响，因此需要设计合理的星间链路复合时延代价
函数，其中传播时延仅仅反映的是网络拓扑的物理连接变化，而队列时延仅仅反映的是网
络流量变化的情况，因此，本发明实施例选择星间链路ISL传播时延，以及输出缓冲队列时
延作为复合链路时延代价因子，这样的时延代价函数设计保证，既能反映卫星网络拓扑物
理连接变化，亦能反映网络流量负载的变化。其中TDij(t)表示链路 的总时延，PDij(t)
表示链路 的传播时延，QDij(t)表示链路 的输出队列时延，且：
[0141]
[0142]
[0143] 其中 表示卫星i与卫星j之间的物理距离，c为光速表示无线信号或激光信号的传输速率(忽略干扰)，t表示t时刻，Δt表示LEO卫星网络进行全网链路状态信息库更
新的时间间隔，q(y)表示在时刻y时输出队列中的传输分组数，Pavg表示输出队列中已有传
输分组的平均长度，BW表示星间链路容量；TD(p)表示路径p的累计时延，TDmax表示用户通信
业务要求的最大容忍时延；Band(i,j)表示卫星i与卫星j之间的链路可用带宽，其计算公式
为：
[0144]
[0145] 星间链路可用带宽，即链路剩余带宽，为凹性度量参数，且链路剩余带宽越大，其服务性能越好，越不易发生链路堵塞、丢包等情况。其中 表示卫星i与卫星j之
间的链路总带宽， 表示卫星i与卫星j之间的链路已用带宽；Band(p)表示路径p
的实际可用带宽，Bandmin表示用户通信业务最小要求可用带宽；γij表示卫星i与卫星j之间
的链路代价修正因子，其计算公式为：
[0146]
[0147] 其中lati表示卫星i的纬度，loni表示卫星i的经度。
[0148] 全球大多数热点是分布在赤道和50°N之间范围内的，因此，通常覆盖0°N～50°N区域的卫星会变得较为拥挤、繁忙，但是其他区域卫星却未得到充分利用。由于人口分布、经
济与技术发展等因素，覆盖南半球上空的卫星要比覆盖北半球上空的卫星流量负载轻得
多。根据图3全球热点区域估计分布图显示，本发明实施例将南半球地区视为非热点区域，
而将北半球的北美、欧洲、中东和东亚地区视为热点区域，北半球的其他地区则被划分为非
热点区域。
[0149] 针对全球流量分布不均衡的问题，我们考虑将卫星的地理位置因素引入到链路代价计算中去，即引入链路代价修正因子γij，以此来增强穿过热点地区的链路代价与穿过非
热点地区的链路代价之间的差异性，实现将热点区域流量引导至非热点区域传输，实现流
量的均衡分布，减小热点区域上空卫星的压力与发生拥塞的可能性，保障卫星路由转发数
据包时的QoS，也有效提高了非热点区域上空卫星的使用率。
[0150] S5、利用链路最小带宽约束对卫星拓扑进行剪枝预处理，将多约束QoS最优路径路由模型简化为时延约束最小路径代价路由(DCLC，Delay Constrained Least Cost)模型。
[0151] 由于在建立的多约束QoS最优路径路由模型中，存在着链路可用带宽Band(i,j)这个参数，且其为凹性度量参数，为了降低路由模型求解的难度与复杂度，所以每颗接入卫星
在得到地面通信用户路由请求，获得具体QoS要求约束参数后，在执行具体路由计算之前，
需要对卫星拓扑进行剪枝预处理，将多约束QoS最优路径路由模型简化为时延约束最小路
径代价路由模型。
[0152] 步骤S5包括以下分步骤S51～S52：
[0153] S51、利用用户通信业务最小要求可用带宽Bandmin对源节点卫星当前所具有的全局网络状态拓扑图G(V,E)中不满足链路最小带宽约束的星间链路进行剪枝预处理，得到剪
* * * *
枝预处理后的全局网络状态拓扑图G (V ,E)，其中V和V均表示LEO卫星网络中卫星节点的
*
集合，E和E均表示LEO卫星网络中链路的集合。
[0154] 在新的全局卫星网络拓扑图G*(V*,E*)上搜索用户所需路由路径时，将无需再考虑带宽这一约束条件，经过剪枝预处理后，带宽这一约束条件肯定是满足的。
[0155] S52、在剪枝预处理后的全局网络状态拓扑图G*(V*,E*)上，将多约束QoS最优路径路由模型简化为时延约束最小路径代价路由模型：
[0156] p*＝min{Cost(p):p∈p(s,d)&TD(p)≤TDmax}
[0157] 其中p*表示最优路由路径。
[0158] S6、根据基于合成成本代价的拉格朗日松弛算法对时延约束最小路径代价路由模*
型进行求解，得到最优路由路径p。
[0159] 虽然在步骤S5中已经删除了带宽条件这一约束，一定程度上降低了路由模型求解的难度，但是DCLC问题，仍然无法在多项式时间内求出精确解，而且其已经被证明为是一个
NP_hard问题，因此，本发明实施例提出采用启发式的算法来完成求解时延约束最小路径代
价路由模型，计算求得问题的近似解。在实际设计中，本发明实施例最终选择了采用基于拉
格朗日松弛的启发式算法来完成对最优路由路径的计算。
[0160] 拉格朗日松弛算法是一种求解问题下界的方法，它具有较低的时间复杂度和较优的计算性能，其主要思想是把约束条件吸收到目标函数中，通过减少约束条件的方式，以降
低原始问题的计算复杂度，最终使减少约束条件后的问题能够在多项式时间内求得问题的
最优解。
[0161] 步骤S6包括以下分步骤S61～S69：
[0162] S61、将时延约束最小路径代价路由模型转化为路由模型L*：
[0163]
[0164] 其中L(θ)表示把时延约束条件吸收到目标函数后形成的新的线性函数，且：
[0165] L(θ)＝min{Costθ(p)‑θTDmax:p∈p(s,d)}
[0166] ＝{Costθ(p):p∈p(s,d)}‑θTDmax
[0167] 其中θ表示拉格朗日乘子，Costθ(p)表示路径p所包含的合成链路代价之和，且：
[0168]
[0169] 其中Costθ＝Costij+θTDij表示合成链路代价函数。
[0170] 由拉格朗日松弛算法的相关定理证明可知，* * *
也易看出L(θ)为p (即min Cost(p))的下界，为了更加逼近p，需要找到L(θ)的最大值L ，那
* * *
么L即为p的近似解，当求得的拉格朗日乘子θ值，使得函数L(θ)取得最大值时并作为p (即
目标函数Cost(p))的下界时，此时所求得的路径p就是满足时延约束条件下的最小新链路
*
代价开销的路径p。通过求解得到上述函数L(θ)的最大值，就能得到优化问题的下界。
[0171] S62、令拉格朗日乘子θ＝0，将链路代价Costij作为Dijkstra算法的输入，计算得到最短路径pcost。
[0172] S63、判断最短路径pcost的时延TD(pcost)是否满足TD(pcost)≤TDmax，若是则将最短*
路径pcost作为最优路由路径p，否则进入步骤S64。
[0173] S64、将复合时延代价TDij为Dijkstra算法的输入，计算得到最短路径pTD。
[0174] S65、判断最短路径pTD的时延TD(pTD)是否满足TD(pTD)≤TDmax，若是则进入步骤*
S66，否则最优路由路径p不存在，进入步骤S7。
[0175] S66、通过迭代替换最短路径pcost和最短路径pTD，寻找得到使得最短路径pcost与最短路径pTD的合成链路代价函数Costθ取得最小值，且使得线性函数L(θ)取得最大值的拉格
朗日乘子θ：
[0176]
[0177] 其中Cost(pcost)表示最短路径pcost的代价值，Cost(pTD)表示最短路径pTD的代价值。
[0178] S67、将拉格朗日乘子θ代入合成链路代价函数Costθ，并将合成链路代价函数Costθ作为Dijkstra算法的输入，计算得到最短路径r。
[0179] S68、判断最短路径r的合成链路代价之和Costθ(r)是否满足Costθ(r)＝Costθ*
(pcost)，若是则将最短路径pTD作为最优路由路径p，否则进入步骤S69。
[0180] S69、判断最短路径r的时延TD(r)是否满足TD(r)≤TDmax，若是则将最短路径r作为pTD的值，否则将最短路径r作为pcost的值，反复迭代步骤S66～S68，直到计算出满足条件的
*
最优路由路径p。
[0181] 本发明实施例中，对于DCLC问题，通过基于拉格朗日松弛的启发式算法对目标函2
数求解，该问题的时间复杂度为O([E+VlogV])，V表示LEO卫星网络中卫星节点数量，E表示
LEO卫星网络中星间链路数量；通过对拉格朗日乘子θ进行松弛求得目标解的方式，是可以
灵活控制优化目标和算法运行时间的，LARAC算法理论上为原问题的目标函数提供了下界
值，是一种合适的求解卫星网络下实时动态QoS的可靠性路由算法。
[0182] S7、判断最优路由路径p*是否存在，若是则进入步骤S8，否则进入步骤S9。
[0183] S8、通过最优路由路径p*完成此次LEO卫星网络的星间可靠路由通信，结束流程。
[0184] S9、拒绝此次路由请求，结束流程。
[0185] 本发明实施例提供的LEO卫星网络可靠性路由方法的可靠性保证主要体现在三个方面：
[0186] (1)卫星网络中的每颗LEO卫星在得到周期性更新的NSB后，用户所需实际路由表项的计算任务将分散至各个LEO卫星当中去，即当地面用户发起通信业务请求时，使得某颗
LEO卫星成为用户的接入卫星(源节点卫星)时，该卫星将独立独自计算以自己为源节点的
源路由形式路由转发表项。轨道发言人卫星将不再为轨道面内所有其他卫星集中计算它们
的全局路由表项，只负责完成路由状态信息的收集与分发，避免了因将过多的星上计算执
行任务累加于单颗中心控制卫星上，防止控制卫星因计算任务负载过大造成故障拥塞或遭
受网络恶意攻击等时，使得所辖局部范围内的全部成员卫星的路由转发功能失效、瘫痪，就
算采用及时移交计算任务给其他局部中心控制卫星的处理方式，也难免带来较大路由等待
时延，影响用户通信的体验感，所以以这种分散式路由计算执行者的方式提高了路由计算
的可靠性。
[0187] (2)由于全球热点区域的分布是不均衡的，大多数热点是分布在赤道和50°N之间范围内，所以南半球上空卫星的流量负载压力要远小于北半球上空的卫星，因此为了实现
引导全球流量的均衡分布，本发明将卫星所处地理位置这个因素考虑进来，提出了一个链
路代价修正因子γij，但是仅仅有修正因子是不够的，然后本发明将修正因子与复合时延代
价函数进行结合，设计了一种能够引导流量均衡分布的新的链路代价函数Costij，这样的设
计，实现了从卫星地理位置因素考虑引导流量均衡分布，避免了热点区域卫星因流量过于
集中、星上负载过大、星上发生拥堵时，服务质量急剧下降的情况发生，提高了路由转发过
程的可靠性，也提高了非热点区域卫星的使用率。
[0188] (3)QoS通常是对通信网络中数据传输质量的描述，是对数据进行传输中极其重要的量化衡量标准，为了提高用户数据包路由传输过程中的可靠性，本发明设计选择综合服
务性能最好的转发路径来完成数据的传输，因为服务质量高的路径上其发生拥塞、丢包的
概率也是极小的，能给用户带来更佳的服务体验，选择约束的QoS参数越多，其QoS越能得到
更高效、可靠的保障，但是其求解难度也会随之增大，因此本发明仅考虑将实际路由设计问
题中最重要也是最常用的度量参数链路时延、带宽引入进来，来完成多约束条件的建立，以
此来保证算法搜寻综合服务性能最好的路径。
[0189] 本领域的普通技术人员将会意识到，这里所述的实施例是为了帮助读者理解本发明的原理，应被理解为本发明的保护范围并不局限于这样的特别陈述和实施例。本领域的
普通技术人员可以根据本发明公开的这些技术启示做出各种不脱离本发明实质的其它各
种具体变形和组合，这些变形和组合仍然在本发明的保护范围内。
