低轨卫星网络中卫星间最短路径的快速求解方法及系统

1.本发明涉及卫星通信技术领域，特别地，涉及一种低轨卫星网络中卫星间最短路径的快速求解方法及系统、电子设备、计算机可读取的存储介质。


背景技术：

2.最短距离路径(shortest distance path,sdp)在通信网络路由问题中被广泛采用，以实现最小的网络延迟、最优的传输成本和最大的系统效率，而在由星间链路连接的leo卫星网络中，最短路径也被广泛用于解决低时延和高资源利用率的路由问题。现有的dijkstra算法、bellman-ford算法等方法都是求解最短路径的经典算法，这些传统sdp算法大多是基于图的迭代算法，首先需建立网络的图模型，计算图模型中各节点的连接关系和各边距离，通过在图上的迭代来计算sdp。但是，与其他无线网络不同，leo卫星网络具有独特的拓扑特征，其网络拓扑结构是动态的，而卫星在星座中的位置是规则的，它们的运动由确定性轨道动力学控制，星间链路距离随卫星相位变化。在与本发明最相近似的现实方案中，将从源节点到目标节点的最小跳数路径(minimum hop path,mhp)集合形成一个子图，可以看作是有向无环图(dag)，用拓扑排序法代替dijkstra算法来求解dag中的sdp。具体地，首先，按照从源节点到相邻节点，直到目标节点的线性顺序对所有节点进行排序，如果存在从节点u到节点v的路径，则节点u在顶点顺序上排在节点v前面；其次，将源节点到每个节点的距离初始化为无穷大；然后，再按拓扑顺序遍历每个节点时，对源节点到该节点的距离进行更新，直到得到源节点到目标节点的最短距离。但该dag算法依然需要依赖迭代计算，并且需要提前计算获取所涉及到的所有边的链路距离。
3.因此，现有传统sdp算法的求解完全依赖于迭代计算，虽然可以获得最优解，但计算复杂度随着网络规模的增大而迅速增加。而现有基于dag的算法相比于传统sdp算法虽然减少了部分计算量，但仍需要迭代计算，计算复杂度仍然较大，并且需要提前计算好各链路的距离作为输入参数，而且只能得到近似最优解，求解精度有待提高。


技术实现要素：

4.本发明提供了一种低轨卫星网络中卫星间最短路径的快速求解方法及系统、电子设备、计算机可读取的存储介质，以解决现有求解sdp的算法存在的计算复杂度大、求解精度较差的技术问题。
5.根据本发明的一个方面，提供一种低轨卫星网络中卫星间最短路径的快速求解方法，包括以下内容：
6.输入低轨卫星网络的星座参数和始末卫星的位置信息，所述星座参数包括低轨卫星网络的轨道面数量、每个轨道平面内均匀分布的卫星数量、轨道高度、相位因子和轨道倾角；
7.基于输入的星座参数计算得到星座相位参数，所述星座相位参数包括轨道面内卫星间相位差、相邻轨道面之间的升交点赤经差和相邻轨道卫星相位差，并基于始末卫星的
位置信息构建mesh状的最短路径求解区域；
8.基于星座相位参数和始末卫星的位置信息计算得到始末卫星间的相位差；
9.基于相位差判断始末卫星构成的相位情形为单谷情形或者双谷情形，并根据相位情形判断结果，在最短路径求解区域内求解始末卫星间最小跳数路径的最短路径，并输出最短路径的距离值和途经节点。
10.进一步地，基于下式计算得到始末卫星间的相位差：
11.△
u＝u
m,n-u0＝(m-1)
△
φ+(n-1)
△f12.其中，
△
u表示始末卫星间的相位差，(m，n)表示末端卫星在最短路径求解区域中的位置编号，n为轨道面编号，m为轨道面内编号，u
m,n
表示末端卫星的相位，u0表示始端卫星的相位，
△
φ表示轨道面内卫星间相位差，
△
f表示相邻轨道卫星相位差。
13.进一步地，当始末卫星间的相位差时，则判定始末卫星构成的相位情形为单谷情形；当始末卫星间的相位差时，则判定始末卫星构成的相位情形为双谷情形；其中，u0表示始端卫星的相位，
△
f表示相邻轨道卫星相位差，mod()表示求余函数。
14.进一步地，在最短路径求解区域内，任一条最小跳数路径的距离计算公式为：
[0015][0016]
其中，(m，n)表示末端卫星在最短路径求解区域中的位置编号，对应的始端卫星位置编号为(1，1)，其表示同轨星间链路的距离，re为地球半径，hs为卫星的轨道高度，
△
φ表示轨道面内卫星间相位差，表示最小跳数路径上第i个异轨星间链路的距离，θ表示两卫星间连线地心角度，表示相邻轨道面之间的升交点赤经差，α表示卫星的轨道倾角，
△
f表示相邻轨道卫星相位差，u(vi)表示第i次跨轨道面转发处的卫星相位，u(vi)＝u0+(v
i-1)
△
φ+(i-1)
△
f,i＝1,2,...,n-1，vi表示第i次跨轨道面转发处的卫星编号。
[0017]
进一步地，在最短路径求解区域内求解始末卫星间最小跳数路径的最短路径时，将最小跳数路径的最短路径求解转化为所有跨轨道面转发位置的总路径相位偏移量最小求解，其中，总路径相位偏移量表示为：
[0018][0019]
表示第i次跨轨道面转发处的相位偏移量，
u＝us表示异轨星间链路距离函数dh(u)的对称轴。
[0020]
进一步地，在单谷情形下求解始末卫星间最小跳数路径的最短路径的过程为：
[0021]
最短路中所有跨轨道面转发连续进行，先基于下式计算第i次跨轨道面转发处的卫星编号vi：
[0022]
vi＝v1,i＝1,2,...,n-1
[0023][0024][0025]
其中，u0表示始端卫星的相位，表示中间变量，round()表示四舍五入取整函数；
[0026]
然后，基于第i次跨轨道面转发处的卫星编号vi计算得到第i次跨轨道面转发处的卫星相位u(vi)，进而计算得到始末卫星间最小跳数路径的最短路径。
[0027]
进一步地，在双谷情形下求解始末卫星间最小跳数路径的最短路径的过程为：
[0028]
将最短路径简化为包含两段连续跨轨道面转发的双台阶路径，基于下式分别计算得到第一段连续跨轨道面转发的转发次数r、第1次跨轨道面转发处的卫星编号v1和轨道面内连续转发的次数
△
v：
[0029][0030][0031][0032]
其中，rh表示r的取值上限，round()表示四舍五入取整函数，u0表示始端卫星的相位，mod()表示求余函数，表示中间变量，vh表示v1的取值上限；
[0033]
再基于下式计算第i次跨轨道面转发处的卫星编号vi和卫星相位u(vi)：
[0034]
[0035][0036]
然后，基于下式计算第i次跨轨道面转发处的相位偏移量：
[0037][0038]
基于下式计算得到总路径相位偏移量：
[0039][0040]
再令
△
v＝0，v1＝v2＝...＝v
n-1
，随后遍历v1＝1,2，...，n-1，求对应的和并取其中的最小值为
[0041]
比较和的大小，取两者中的较小者所对应的r、v1和
△
v来计算vi和u(vi)，进而计算得到始末卫星间最小跳数路径的最短路径。
[0042]
另外，本发明还提供一种低轨卫星网络中卫星间最短路径的快速求解系统，采用如上所述的快速求解方法，包括：
[0043]
输入模块，用于输入低轨卫星网络的星座参数和始末卫星的位置信息，所述星座参数包括低轨卫星网络的轨道面数量、每个轨道平面内均匀分布的卫星数量、轨道高度、相位因子和轨道倾角；
[0044]
第一计算模块，用于基于输入的星座参数计算得到星座相位参数，所述星座相位参数包括轨道面内卫星间相位差、相邻轨道面之间的升交点赤经差和相邻轨道卫星相位差，并基于始末卫星的位置信息构建mesh状的最短路径求解区域；
[0045]
第二计算模块，用于基于星座相位参数和始末卫星的位置信息计算得到始末卫星间的相位差；
[0046]
输出模块，用于基于相位差判断始末卫星构成的相位情形为单谷情形或者双谷情形，并根据相位情形判断结果，在最短路径求解区域内求解始末卫星间最小跳数路径的最短路径，并输出最短路径的距离值和途经节点。
[0047]
另外，本发明还提供一种电子设备，包括处理器和存储器，所述存储器中存储有计算机程序，所述处理器通过调用所述存储器中存储的所述计算机程序，用于执行如上所述的方法的步骤。
[0048]
另外，本发明还提供一种计算机可读取的存储介质，用于存储对低轨卫星网络中卫星间最短路径进行快速求解的计算机程序，所述计算机程序在计算机上运行时执行如上所述的方法的步骤。
[0049]
本发明具有以下效果：
[0050]
本发明的低轨卫星网络中卫星间最短路径的快速求解方法，只需输入低轨卫星网络的星座参数和始末卫星的位置信息，即可基于星座参数计算得到星座相位参数并基于始末卫星的位置信息构建mesh状的最短路径求解区域，再基于星座相位参数和始末卫星的位置信息计算得到始末卫星间的相位差，最后基于相位差判断始末卫星构成的相位情形，并
根据不同相位情形在最短路径求解区域内求解始末卫星间最小跳数路径的最短路径，并输出最短路径的距离值和途经节点。本实施例的快速求解方法，基于卫星星座拓扑特性和星间链路距离特性提出了低轨卫星网络星间最短路径显式解析的直接求解方法，简称eap算法，与现有的dijkstra算法和dag算法相比，省去了迭代计算过程，并且无需提前计算所有链路长度，计算复杂度低且求解准确度高，而且，计算复杂度不随星座规模增加而增加，并且能保持良好的精确率，可以很好地适用于卫星数目繁多的巨型星座，如星链、kuiper等。
[0051]
另外，本发明的低轨卫星网络中卫星间最短路径的快速求解系统同样具有上述优点。
[0052]
除了上面所描述的目的、特征和优点之外，本发明还有其它的目的、特征和优点。下面将参照图，对本发明作进一步详细的说明。
附图说明
[0053]
构成本技术的一部分的附图用来提供对本发明的进一步理解，本发明的示意性实施例及其说明用于解释本发明，并不构成对本发明的不当限定。在附图中：
[0054]
图1是本发明优选实施例的低轨卫星网络中卫星间最短路径的快速求解方法的流程示意图。
[0055]
图2是本发明优选实施例的低轨卫星网络的拓扑结构和星间链路结构的示意图。
[0056]
图3是本发明优选实施例中构建的m
×
n维最短路径求解区域的示意图。
[0057]
图4是本发明优选实施例中将双谷情形下的最短路径简化为包含两段连续跨轨道面转发的双台阶路径的示意图。
[0058]
图5是本发明优选实施例中采用不同sdp算法在不同星座规模下的时间消耗对比结果的柱状示意图。
[0059]
图6是本发明另一实施例的低轨卫星网络中卫星间最短路径的快速求解系统的模块结构示意图。
具体实施方式
[0060]
以下结合附图对本发明的实施例进行详细说明，但是本发明可以由下述所限定和覆盖的多种不同方式实施。
[0061]
如图1所示，本发明的优选实施例提供一种低轨卫星网络中卫星间最短路径的快速求解方法，包括以下内容：
[0062]
步骤s1：输入低轨卫星网络的星座参数和始末卫星的位置信息，所述星座参数包括低轨卫星网络的轨道面数量、每个轨道平面内均匀分布的卫星数量、轨道高度、相位因子和轨道倾角；
[0063]
步骤s2：基于输入的星座参数计算得到星座相位参数，所述星座相位参数包括轨道面内卫星间相位差、相邻轨道面之间的升交点赤经差和相邻轨道卫星相位差，并基于始末卫星的位置信息构建mesh状的最短路径求解区域；
[0064]
步骤s3：基于星座相位参数和始末卫星的位置信息计算得到始末卫星间的相位差；
[0065]
步骤s4：基于相位差判断始末卫星构成的相位情形为单谷情形或者双谷情形，并
根据相位情形判断结果，在最短路径求解区域内求解始末卫星间最小跳数路径的最短路径，并输出最短路径的距离值和途经节点。
[0066]
可以理解，本实施例的低轨卫星网络中卫星间最短路径的快速求解方法，只需输入低轨卫星网络的星座参数和始末卫星的位置信息，即可基于星座参数计算得到星座相位参数并基于始末卫星的位置信息构建mesh状的最短路径求解区域，再基于星座相位参数和始末卫星的位置信息计算得到始末卫星间的相位差，最后基于相位差判断始末卫星构成的相位情形，并根据不同相位情形在最短路径求解区域内求解始末卫星间最小跳数路径的最短路径，并输出最短路径的距离值和途经节点。本实施例的快速求解方法，基于卫星星座拓扑特性和星间链路距离特性提出了低轨卫星网络星间最短路径显式解析的直接求解方法，简称eap算法，与现有的dijkstra算法和dag算法相比，省去了迭代计算过程，并且无需提前计算所有链路长度，计算复杂度低且求解准确度高，而且，计算复杂度不随星座规模增加而增加，并且能保持良好的精确率，可以很好地适用于卫星数目繁多的巨型星座，如星链、kuiper等。
[0067]
可以理解，如图2所示，本发明针对的是低轨卫星网络，即leo轨道星座网络，大多数leo轨道星座网络系统普遍采用walker星座，即星座内卫星按照圆轨道飞行，所有卫星具备相同的轨道倾角α、高度hs和轨道周期ts。通常，walker星座中有n
p
个轨道面沿赤道均匀分布，每个轨道平面内有m
p
个卫星均匀分布，轨道面内卫星间相位差为：而相邻轨道卫星相位差f表示相位因子。而walker星座具体包含walker-delta与walker-star星座两类，其区别在于前者一般采用倾斜轨道，后者一般采用近极轨道，相邻轨道面之间的升交点赤经差
△
ω分别为和每颗卫星与其前后左右四颗卫星之间各建立一条双向星间链路(isl)，其中同一轨道面内相邻两卫星间的链路为同轨isl，不同轨道面两卫星间的链路为异轨isl。在卫星运动过程中，所有isl始终保持连接，walker星座构型和星间链路使得低轨卫星星座网络拓扑为mesh状，且每个节点度为4。而两卫星间的最短路指总路径长度最短的路径，由于低轨卫星网络的拓扑为mesh状的规则拓扑，且链路距离相差较小，最短路途经的卫星节点和转发跳数也最少。因此，本发明通过在最小跳数路径(mhp)集合内求解最短路，当卫星沿最小跳数路径转发时，卫星在每个途经节点可能的转发方向不大于两个，均为朝向目的节点的方向。
[0068]
可以理解，在所述步骤s1和s2中，输入低轨卫星网络的轨道面数量n
p
、每个轨道平面内均匀分布的卫星数量m
p
、轨道高度hs、相位因子f和轨道倾角α，以及始末卫星在mesh状拓扑网络中的位置信息、始端卫星的相位。然后，即可基于公式：分别计算得到轨道面内卫星间相位差
△
φ和相邻轨道卫星相位差
△
f，当低轨卫星网络采用walker-delta星座构型时，相邻轨道面之间的升交点赤经差
△
ω为而当低轨卫星网络采用walker-star星座构型时，相邻轨
道面之间的升交点赤经差
△
ω为然后，基于始末卫星在mesh状拓扑网络中的位置信息构建m
×
n维的最短路径求解区域，具体如图3所示，其中，始端卫星的节点编号为(1,1)，末端卫星的节点编号为(m，n)，(v，h)则代表第h个轨道面上的第v个卫星。
[0069]
可以理解，在所述步骤s3中，令始端节点的卫星相位为u
1,1
＝u0，u0为始端卫星的相位，通过输入得到，则节点(v，h)的相位为u
v,h
＝u0+(v-1)
△
φ+(h-1)
△
f。因此，基于下式计算得到始末卫星间的相位差：
[0070]
△
u＝u
m,n-u0＝(m-1)
△
φ+(n-1)
△f[0071]
其中，
△
u表示始末卫星间的相位差，(m，n)表示末端卫星在最短路径求解区域中的位置编号，n为轨道面编号，m为轨道面内编号，u
m,n
表示末端卫星的相位，u0表示始端卫星的相位，
△
φ表示轨道面内卫星间相位差，
△
f表示相邻轨道卫星相位差。
[0072]
可以理解，在所述步骤s4中，在构建了m
×
n维的最短路径求解区域后，其同轨星间转发跳数和异轨星间转发跳数分别为m-1和n-1，则任意一条最小跳数路径的距离可表示为：
[0073]
其中，表示最小跳数路径上第i个异轨星间链路的距离，表示第j个同轨星间链路的距离。由于所有同轨星间链路距离相同，故是固定值，统一为dv，而随着卫星相位变化，因此，任意一条最小跳数路径的距离可表示为：而同轨星间链路距离其中，re为地球半径，hs为卫星的轨道高度，
△
φ表示轨道面内卫星间相位差。而异轨星间链路距离随卫星相位u而变化，因此，将跨轨道面转发处的卫星相位来表征异轨星间链路距离，具体地，θ表示两卫星间连线地心角度，表示第i次跨轨道面转发处的卫星相位，vi表示第i次跨轨道面转发处的卫星编号，即在m
×
n维mesh拓扑的节点(vi，i)处进行跨轨道面转发，其中，vi∈{1，2，...，m}，i＝1,2,...,n-1，例如，图3中的v1＝v2＝2,v3＝m，只要集合{vi}确定，则该条最小跳数路径就可以确定。而每次星间链路转发都会产生固定的相位变化，则第i次跨轨道面转发处的卫星相位u(vi)可表示为：u(vi)＝u0+(v
i-1)
△
φ+(i-1)
△
f,i＝1,2,...,n-1。
[0074]
因此，在计算出跨轨道面转发处的卫星相位后，即可计算得到异轨星间转发链路距离，从而可以计算得到任意一条最小跳数路径的距离。
[0075]
可以理解，本发明利用跨轨道面转发处的卫星相位来表征异轨星间链路距离，只需计算得到每次跨轨道面转发处的卫星相位，即可计算得到每次异轨星间转发链路的距
离，而同轨星间转发链路的距离为固定值，从而可以快速计算得到任意一条最小跳数路径的距离，其中的最小者即为最短距离，整个求解过程无需计算所有链路的长度，大大降低了计算复杂度。
[0076]
可以理解，在最短路径求解区域内求解始末卫星间最小跳数路径的最短路径时，根据星间链路距离特性，将最小跳数路径的最短路径求解转化为所有跨轨道面转发位置的总路径相位偏移量最小求解，即将求解问题转化为求解问题其中，dh(u)表示异轨星间链路距离函数。考虑到dh(u)的对称性和单调性，dh(u)在u远离对称轴u＝us时增长，则第i次跨轨道面转发处的相位偏移量表示与最小距离位置的相位偏差，而所有跨轨道面转发位置的总路径相位偏移量可表示为：
[0077][0078]
因此，目标问题可以进一步转化为寻找满足的{vi}问题。可以理解，当计算得到的始末卫星间的相位差时，则判定始末卫星构成的相位情形为单谷情形；而当始末卫星间的相位差时，则判定始末卫星构成的相位情形为双谷情形；其中，u0表示始端卫星的相位，
△
f表示相邻轨道卫星相位差，mod()表示求余函数。
[0079]
其中，在单谷情形下求解始末卫星间最小跳数路径的最短路径的过程具体为：
[0080]
最短路中所有跨轨道面转发连续进行，先基于下式计算第i次跨轨道面转发处的卫星编号vi：
[0081]
vi＝v1,i＝1,2,...,n-1
[0082][0083][0084]
其中，u0表示始端卫星的相位，表示中间变量，round()表示四舍五入取整函数，在单谷情形下连续进行n-1次跨轨道面转发。
[0085]
然后，基于第i次跨轨道面转发处的卫星编号vi计算得到第i次跨轨道面转发处的卫星相位u(vi)，计算公式为：u(vi)＝u0+(v
i-1)
△
φ+(i-1)
△
f,i＝1,2,...,n-1，从而可以
计算得到第i个异轨星间链路的距离进而计算得到始末卫星间最小跳数路径的最短路径
[0086]
另外，在双谷情形下求解始末卫星间最小跳数路径的最短路径的过程具体为：
[0087]
先将双谷情形下的最短路径简化为包含两段连续跨轨道面转发的双台阶路径，如图4所示。而双台阶路径可以通过三个参量来确定，分别为第一段连续跨轨道面转发的转发次数r、第1次跨轨道面转发处的卫星编号v1和轨道面内连续转发的次数
△
v。例如，在图4中，从源节点(1,1)开始，在节点(v1,1)处进行第1次跨轨道面转发，连续进行r次跨轨道面转发后到达节点(v1，r+1)，再经过连续的
△
v次同轨转发，到达节点(v1+
△
v，r+1)，再进行剩余n-1-r次连续跨轨道面转发，最后达到目标节点(m，n)。其中，具体基于下式分别计算得到第一段连续跨轨道面转发的转发次数r、第1次跨轨道面转发处的卫星编号v1和轨道面内连续转发的次数
△
v：
[0088][0089][0090][0091]
其中，rh表示r的取值上限，round()表示四舍五入取整函数，u0表示始端卫星的相位，mod()表示求余函数，表示中间变量，vh表示v1的取值上限。
[0092]
再基于下式计算第i次跨轨道面转发处的卫星编号vi和卫星相位u(vi)：
[0093][0094]
然后，基于下式计算第i次跨轨道面转发处的相位偏移量：
[0095][0096]
再基于下式计算得到总路径相位偏移量：
[0097][0098]
并且，考虑到双谷情形下也有可能最短路径中所有跨轨道面转发连续发生，故令
△
v＝0，v1＝v2＝...＝v
n-1
，即r＝n-1，随后遍历v1＝1,2，...，n-1，计算出对应的和并取其中的最小值为所有异轨星间链路连续转发时的总路径相位偏移量
[0099]
最后，比较和的大小，取两者中的较小者所对应的r、v1和
△
v来计算vi和u(vi)，进而计算得到始末卫星间最小跳数路径的最短路径。
[0100]
可以理解，本发明将最短路距离求解问题转化为跨轨道面转发的总路径相位偏差量最小求解问题，大大降低了计算复杂度，并且可以准确地计算得到最短距离值和最短路径途经节点。
[0101]
可以理解，为了进一步验证本发明的eap算法的优点，本技术发明人还进行了多种leo星座场景下的数值仿真，在单谷情况下，采用蒙特卡洛模拟方法随机生成了100万个星座网络，并在每个星座中计算多组最短路，仿真结果证明所有最短路距离都与dijkstra算法结果的相同。其中，采用不同sdp算法在不同星座规模下的时间消耗对比结果如表1和图5所示。
[0102]
表1、不同sdp算法在不同星座规模下的时间消耗对比结果
[0103][0104]
从表1和图5可以看出，本发明的eap算法能有效减少时间消耗，与dijkstra算法和dag算法相比，节约时间分别超过99.4％和74.0％，而且随着星座规模的增大，节省时间的比率也随之增大，这表明本发明所提出的eap算法在星链等大规模星座中具有更显著的优势，这是因为在大规模星座中，m和n较大，传统的递推算法比本发明的显式解析算法需要消耗更多的时间。
[0105]
同时，还验证了双谷情况下本发明的eap算法的准确性并考察了偏差，进一步分析了星链星座中的sdp特性。为了比较误差，本技术发明人还提出了rand-mhp算法，即在相应的mhp区域(即m
×
n维的最短路径求解区域)中随机生成一条随机路径，本发明的eap算法在双谷情形下的准确性分析结果如表2所示。
[0106]
表2、eap算法在双谷情形下的准确性分析结果
[0107] rand mhpeapeap(overall)mean relative error8.82％0.11％0.09％max relative error151.39％7.18％7.32％
optimal sdp probability9.67％77.75％88.38％
[0108]
从表2可以看出，本发明的eap算法在双谷情形下的平均相对误差仅为0.11％，最大误差低至7.18％，超过77％的路径与最优解具有相同的距离。并且，如果还包含单谷情形，即eap(overall)结果显示所有情况下的eap整体绩效都进一步提升，总体平均相对误差小于0.1％，与rand-mhp算法相比，求解精度更高，本发明所提出的eap算法无论是在单谷情形下还是双谷情形下均适用且有效。
[0109]
另外，如图6所示，本发明的另一实施例还提供一种低轨卫星网络中卫星间最短路径的快速求解系统，优选采用如上所述的快速求解方法，包括：
[0110]
输入模块，用于输入低轨卫星网络的星座参数和始末卫星的位置信息，所述星座参数包括低轨卫星网络的轨道面数量、每个轨道平面内均匀分布的卫星数量、轨道高度、相位因子和轨道倾角；
[0111]
第一计算模块，用于基于输入的星座参数计算得到星座相位参数，所述星座相位参数包括轨道面内卫星间相位差、相邻轨道面之间的升交点赤经差和相邻轨道卫星相位差，并基于始末卫星的位置信息构建mesh状的最短路径求解区域；
[0112]
第二计算模块，用于基于星座相位参数和始末卫星的位置信息计算得到始末卫星间的相位差；
[0113]
输出模块，用于基于相位差判断始末卫星构成的相位情形为单谷情形或者双谷情形，并根据相位情形判断结果，在最短路径求解区域内求解始末卫星间最小跳数路径的最短路径，并输出最短路径的距离值和途经节点。
[0114]
可以理解，本实施例的低轨卫星网络中卫星间最短路径的快速求解系统，只需输入低轨卫星网络的星座参数和始末卫星的位置信息，即可基于星座参数计算得到星座相位参数并基于始末卫星的位置信息构建mesh状的最短路径求解区域，再基于星座相位参数和始末卫星的位置信息计算得到始末卫星间的相位差，最后基于相位差判断始末卫星构成的相位情形，并根据不同相位情形在最短路径求解区域内求解始末卫星间最小跳数路径的最短路径，并输出最短路径的距离值和途经节点。本实施例的快速求解系统，基于卫星星座拓扑特性和星间链路距离特性提出了低轨卫星网络星间最短路径显式解析的直接求解方法，简称eap算法，与现有的dijkstra算法和dag算法相比，省去了迭代计算过程，并且无需提前计算所有链路长度，计算复杂度低且求解准确度高，而且，计算复杂度不随星座规模增加而增加，并且能保持良好的精确率，可以很好地适用于卫星数目繁多的巨型星座，如星链、kuiper等。
[0115]
另外，本发明的另一实施例还提供一种电子设备，包括处理器和存储器，所述存储器中存储有计算机程序，所述处理器通过调用所述存储器中存储的所述计算机程序，用于执行如上所述的方法的步骤。
[0116]
另外，本发明的另一实施例还提供一种计算机可读取的存储介质，用于存储对低轨卫星网络中卫星间最短路径进行快速求解的计算机程序，所述计算机程序在计算机上运行时执行如上所述的方法的步骤。
[0117]
一般计算机可读取存储介质的形式包括：软盘(floppy disk)、可挠性盘片(flexible disk)、硬盘、磁带、任何其与的磁性介质、cd-rom、任何其余的光学介质、打孔卡片(punch cards)、纸带(paper tape)、任何其余的带有洞的图案的物理介质、随机存取存
储器(ram)、可编程只读存储器(prom)、可抹除可编程只读存储器(eprom)、快闪可抹除可编程只读存储器(flash-eprom)、其余任何存储器芯片或卡匣、或任何其余可让计算机读取的介质。指令可进一步被一传输介质所传送或接收。传输介质这一术语可包含任何有形或无形的介质，其可用来存储、编码或承载用来给机器执行的指令，并且包含数字或模拟通信信号或其与促进上述指令的通信的无形介质。传输介质包含同轴电缆、铜线以及光纤，其包含了用来传输一计算机数据信号的总线的导线。
[0118]
以上所述仅为本发明的优选实施例而已，并不用于限制本发明，对于本领域的技术人员来说，本发明可以有各种更改和变化。凡在本发明的精神和原则之内，所作的任何修改、等同替换、改进等，均应包含在本发明的保护范围之内。
[0119]
本领域内的技术人员应明白，本技术的实施例可提供为方法、系统、或计算机程序产品。因此，本技术可采用完全硬件实施例、完全软件实施例、或结合软件和硬件方面的实施例的形式。而且，本技术可采用在一个或多个其中包含有计算机可用程序代码的计算机可用存储介质(包括但不限于磁盘存储器、cd-rom、光学存储器等)上实施的计算机程序产品的形式。本技术实施例中的方案可以采用各种计算机语言实现，例如，面向对象的程序设计语言java和直译式脚本语言javascript等。
[0120]
本技术是参照根据本技术实施例的方法、设备(系统)、和计算机程序产品的流程图和/或方框图来描述的。应理解可由计算机程序指令实现流程图和/或方框图中的每一流程和/或方框、以及流程图和/或方框图中的流程和/或方框的结合。可提供这些计算机程序指令到通用计算机、专用计算机、嵌入式处理机或其他可编程数据处理设备的处理器以产生一个机器，使得通过计算机或其他可编程数据处理设备的处理器执行的指令产生用于实现在流程图一个流程或多个流程和/或方框图一个方框或多个方框中指定的功能的装置。
[0121]
这些计算机程序指令也可存储在能引导计算机或其他可编程数据处理设备以特定方式工作的计算机可读存储器中，使得存储在该计算机可读存储器中的指令产生包括指令装置的制造品，该指令装置实现在流程图一个流程或多个流程和/或方框图一个方框或多个方框中指定的功能。
[0122]
这些计算机程序指令也可装载到计算机或其他可编程数据处理设备上，使得在计算机或其他可编程设备上执行一系列操作步骤以产生计算机实现的处理，从而在计算机或其他可编程设备上执行的指令提供用于实现在流程图一个流程或多个流程和/或方框图一个方框或多个方框中指定的功能的步骤。
[0123]
尽管已描述了本技术的优选实施例，但本领域内的技术人员一旦得知了基本创造性概念，则可对这些实施例作出另外的变更和修改。所以，所附权利要求意欲解释为包括优选实施例以及落入本技术范围的所有变更和修改。
[0124]
显然，本领域的技术人员可以对本技术进行各种改动和变型而不脱离本技术的精神和范围。这样，倘若本技术的这些修改和变型属于本技术权利要求及其等同技术的范围之内，则本技术也意图包含这些改动和变型在内。

技术特征：
1.一种低轨卫星网络中卫星间最短路径的快速求解方法，其特征在于，包括以下内容：输入低轨卫星网络的星座参数和始末卫星的位置信息，所述星座参数包括低轨卫星网络的轨道面数量、每个轨道平面内均匀分布的卫星数量、轨道高度、相位因子和轨道倾角；基于输入的星座参数计算得到星座相位参数，所述星座相位参数包括轨道面内卫星间相位差、相邻轨道面之间的升交点赤经差和相邻轨道卫星相位差，并基于始末卫星的位置信息构建mesh状的最短路径求解区域；基于星座相位参数和始末卫星的位置信息计算得到始末卫星间的相位差；基于相位差判断始末卫星构成的相位情形为单谷情形或者双谷情形，并根据相位情形判断结果，在最短路径求解区域内求解始末卫星间最小跳数路径的最短路径，并输出最短路径的距离值和途经节点。2.如权利要求1所述的低轨卫星网络中卫星间最短路径的快速求解方法，其特征在于，基于下式计算得到始末卫星间的相位差：
△
u＝u
m,n-u0＝(m-1)
△
φ+(n-1)
△
f其中，
△
u表示始末卫星间的相位差，(m，n)表示末端卫星在最短路径求解区域中的位置编号，n为轨道面编号，m为轨道面内编号，u
m,n
表示末端卫星的相位，u0表示始端卫星的相位，
△
φ表示轨道面内卫星间相位差，
△
f表示相邻轨道卫星相位差。3.如权利要求1所述的低轨卫星网络中卫星间最短路径的快速求解方法，其特征在于，当始末卫星间的相位差时，则判定始末卫星构成的相位情形为单谷情形；当始末卫星间的相位差时，则判定始末卫星构成的相位情形为双谷情形；其中，u0表示始端卫星的相位，
△
f表示相邻轨道卫星相位差，mod()表示求余函数。4.如权利要求1所述的低轨卫星网络中卫星间最短路径的快速求解方法，其特征在于，在最短路径求解区域内，任一条最小跳数路径的距离计算公式为：其中，(m，n)表示末端卫星在最短路径求解区域中的位置编号，对应的始端卫星位置编号为(1，1)，其表示同轨星间链路的距离，r
e
为地球半径，h
s
为卫星的轨道高度，
△
φ表示轨道面内卫星间相位差，表示最小跳数路径上第i个异轨星间链路的距离，θ表示两卫星间连线地心角度，表示相邻轨道面之间的升交点赤经差，α表示卫星的轨道倾角，
△
f表示相邻轨道卫星相位差，u(v
i
)表示第i次跨轨道面转发处的卫星相位，u(v
i
)＝u0+(v
i-1)
△
φ+(i-1)
△
f,i＝1,
2,...,n-1，v
i
表示第i次跨轨道面转发处的卫星编号。5.如权利要求4所述的低轨卫星网络中卫星间最短路径的快速求解方法，其特征在于，在最短路径求解区域内求解始末卫星间最小跳数路径的最短路径时，将最小跳数路径的最短路径求解转化为所有跨轨道面转发位置的总路径相位偏移量最小求解，其中，总路径相位偏移量表示为：位偏移量表示为：表示第i次跨轨道面转发处的相位偏移量，表示第i次跨轨道面转发处的相位偏移量，u＝u
s
表示异轨星间链路距离函数d
h
(u)的对称轴。6.如权利要求5所述的低轨卫星网络中卫星间最短路径的快速求解方法，其特征在于，在单谷情形下求解始末卫星间最小跳数路径的最短路径的过程为：最短路中所有跨轨道面转发连续进行，先基于下式计算第i次跨轨道面转发处的卫星编号v
i
：v
i
＝v1,i＝1,2,...,n-11其中，u0表示始端卫星的相位，表示中间变量，round()表示四舍五入取整函数；然后，基于第i次跨轨道面转发处的卫星编号v
i
计算得到第i次跨轨道面转发处的卫星相位u(v
i
)，进而计算得到始末卫星间最小跳数路径的最短路径。7.如权利要求5所述的低轨卫星网络中卫星间最短路径的快速求解方法，其特征在于，在双谷情形下求解始末卫星间最小跳数路径的最短路径的过程为：将最短路径简化为包含两段连续跨轨道面转发的双台阶路径，基于下式分别计算得到第一段连续跨轨道面转发的转发次数r、第1次跨轨道面转发处的卫星编号v1和轨道面内连续转发的次数
△
v：v：v：
其中，r
h
表示r的取值上限，round()表示四舍五入取整函数，u0表示始端卫星的相位，mod()表示求余函数，表示中间变量，v
h
表示v1的取值上限；再基于下式计算第i次跨轨道面转发处的卫星编号v
i
和卫星相位u(v
i
)：)：然后，基于下式计算第i次跨轨道面转发处的相位偏移量：基于下式计算得到总路径相位偏移量：再令
△
v＝0，v1＝v2＝...＝v
n-1
，随后遍历v1＝1,2，...，n-1，求对应的和并取其中的最小值为比较和的大小，取两者中的较小者所对应的r、v1和
△
v来计算v
i
和u(v
i
)，进而计算得到始末卫星间最小跳数路径的最短路径。8.一种低轨卫星网络中卫星间最短路径的快速求解系统，采用如权利要求1～7任一项所述的快速求解方法，其特征在于，包括：输入模块，用于输入低轨卫星网络的星座参数和始末卫星的位置信息，所述星座参数包括低轨卫星网络的轨道面数量、每个轨道平面内均匀分布的卫星数量、轨道高度、相位因子和轨道倾角；第一计算模块，用于基于输入的星座参数计算得到星座相位参数，所述星座相位参数包括轨道面内卫星间相位差、相邻轨道面之间的升交点赤经差和相邻轨道卫星相位差，并基于始末卫星的位置信息构建mesh状的最短路径求解区域；第二计算模块，用于基于星座相位参数和始末卫星的位置信息计算得到始末卫星间的相位差；输出模块，用于基于相位差判断始末卫星构成的相位情形为单谷情形或者双谷情形，并根据相位情形判断结果，在最短路径求解区域内求解始末卫星间最小跳数路径的最短路
径，并输出最短路径的距离值和途经节点。9.一种电子设备，其特征在于，包括处理器和存储器，所述存储器中存储有计算机程序，所述处理器通过调用所述存储器中存储的所述计算机程序，用于执行如权利要求1～7任一项所述的方法的步骤。10.一种计算机可读取的存储介质，用于存储对低轨卫星网络中卫星间最短路径进行快速求解的计算机程序，其特征在于，所述计算机程序在计算机上运行时执行如权利要求1～7任一项所述的方法的步骤。

技术总结
本发明公开了一种低轨卫星网络中卫星间最短路径的快速求解方法及系统，该方法只需输入低轨卫星网络的星座参数和始末卫星的位置信息，即可基于星座参数计算得到星座相位参数并基于始末卫星的位置信息构建Mesh状的最短路径求解区域，再基于星座相位参数和始末卫星的位置信息计算得到始末卫星间的相位差，最后基于相位差判断始末卫星构成的相位情形并在最短路径求解区域内求解始末卫星间最小跳数路径的最短路径。该方法省去了迭代计算过程，并且无需提前计算链路长度，计算复杂度低且求解准确度高，而且，计算复杂度不随星座规模增加而增加，并且能保持良好的精确率，可以很好地适用于卫星数目繁多的巨型星座。地适用于卫星数目繁多的巨型星座。地适用于卫星数目繁多的巨型星座。


技术研发人员：陈全 杨磊 尹政龙 杨华果 程云 赵勇 龚李赠 吴帅 樊程广
受保护的技术使用者：中国人民解放军国防科技大学
技术研发日：2023.05.05
技术公布日：2023/7/12