技术领域Technical Field
本发明涉及卫星通信网络技术领域，尤其涉及一种基于滚动优化的巨型星座网络路径选择方法。The present invention relates to the field of satellite communication network technology, and in particular to a giant constellation network path selection method based on rolling optimization.
背景技术Background Art
低轨卫星网络以其时延低、覆盖广、组网灵活等优点成为卫星通信网络领域的研究热点，而路由技术是发挥低轨卫星网络性能的关键。近年来，以Starlink和OneWeb为代表的巨型星座计划的出现掀起了低轨巨型星座的建设热潮。低轨巨型星座由数百至数千颗低轨卫星组成，其网络规模庞大、拓扑高度动态，给路由设计带来很大的挑战。在过去的几十年里，研究人员针对低轨卫星网络提出了多种路由算法，如基于虚拟拓扑的路由、基于覆盖域划分的路由等。然而，这些算法存在计算复杂度高、拓扑信息易过时、链路状态泛洪开销大等问题，因此不能适用于低轨巨型星座组成的网络。Low-orbit satellite networks have become a research hotspot in the field of satellite communication networks due to their advantages such as low latency, wide coverage, and flexible networking. Routing technology is the key to giving full play to the performance of low-orbit satellite networks. In recent years, the emergence of giant constellation plans represented by Starlink and OneWeb has set off a boom in the construction of low-orbit giant constellations. Low-orbit giant constellations are composed of hundreds to thousands of low-orbit satellites. Their network scale is huge and the topology is highly dynamic, which brings great challenges to routing design. In the past few decades, researchers have proposed a variety of routing algorithms for low-orbit satellite networks, such as routing based on virtual topology and routing based on coverage domain division. However, these algorithms have problems such as high computational complexity, easy outdated topology information, and high link state flooding overhead. Therefore, they are not applicable to networks composed of low-orbit giant constellations.
滚动优化是一种来自模型预测控制(Model Predictive Control,MPC)的优化思想。在MPC中，优化不是对整个时域进行，而是对有限长度的优化时域进行。当某时刻的有限时域优化问题求解完成后，MPC将对应于该时刻的控制信号施加于控制对象，之后将优化时域平移至下一时刻，求解下一时刻的有限时域优化问题。通过滚动优化，MPC得以适应控制对象的参数变化。Rolling optimization is an optimization concept from Model Predictive Control (MPC). In MPC, optimization is not performed on the entire time domain, but on an optimization time domain of finite length. When the finite time domain optimization problem at a certain moment is solved, MPC applies the control signal corresponding to that moment to the controlled object, and then shifts the optimization time domain to the next moment to solve the finite time domain optimization problem at the next moment. Through rolling optimization, MPC can adapt to the parameter changes of the controlled object.
发明内容Summary of the invention
本发明所要解决的技术问题在于，提供一种基于滚动优化的巨型星座网络路径选择方法，将滚动优化的思想运用于路由路径选择问题，在计算路由路径时，每个卫星节点只利用三跳范围内的链路状态信息进行最优路径计算，从而降低了路径计算开销和链路状态泛洪开销；同时，由于将链路状态信息的交换范围限制在三跳以内，可以确保链路状态信息的实时性，适应链路状态的变化。The technical problem to be solved by the present invention is to provide a giant constellation network path selection method based on rolling optimization, which applies the idea of rolling optimization to the routing path selection problem. When calculating the routing path, each satellite node only uses the link state information within a three-hop range to calculate the optimal path, thereby reducing the path calculation overhead and the link state flooding overhead; at the same time, since the exchange range of the link state information is limited to within three hops, the real-time nature of the link state information can be ensured and the change of the link state can be adapted.
为了解决上述技术问题，本发明实施例公开了一种基于滚动优化的巨型星座网络路径选择方法，所述方法包括：In order to solve the above technical problems, an embodiment of the present invention discloses a giant constellation network path selection method based on rolling optimization, the method comprising:
S1，构建巨型星座网络和静态网络；S1, building giant constellation networks and static networks;
S2，对所述巨型星座网络和所述静态网络进行映射，得到映射信息；S2, mapping the giant constellation network and the static network to obtain mapping information;
S3，根据所述映射信息，每个LEO卫星周期性与所述每个LEO卫星三跳以内相连的LEO卫星交换排队延迟信息，并将交换后的排队延迟信息保存在链路状态数据表中；S3, according to the mapping information, each LEO satellite periodically exchanges queuing delay information with a LEO satellite connected to each LEO satellite within three hops, and saves the exchanged queuing delay information in a link state data table;
所述链路状态数据表包括地理地址和排队延迟信息；The link state data table includes geographic address and queuing delay information;
S4，对所述链路状态数据表进行处理，得到最短路径信息；S4, processing the link state data table to obtain the shortest path information;
S5，根据所述最短路径信息选择下一跳LEO卫星，得到基于滚动优化的巨型星座网络路径选择结果。S5, selecting a next-hop LEO satellite according to the shortest path information, and obtaining a giant constellation network path selection result based on rolling optimization.
作为一种可选的实施方式，本发明实施例中，所述巨型星座网络包括N个不同高度的LEO卫星星座；所述LEO卫星星座的轨道类型为极轨道；As an optional implementation, in an embodiment of the present invention, the giant constellation network includes N LEO satellite constellations at different altitudes; the orbit type of the LEO satellite constellation is a polar orbit;
所述静态网络包括M个具有固定地理坐标的虚拟节点。The static network includes M virtual nodes with fixed geographical coordinates.
作为一种可选的实施方式，本发明实施例中，所述对所述巨型星座网络和所述静态网络进行映射，得到映射信息，包括：As an optional implementation manner, in an embodiment of the present invention, mapping the giant constellation network and the static network to obtain mapping information includes:
根据最小距离原则，对所述巨型星座网络和所述静态网络进行映射，得到映射信息；According to a minimum distance principle, mapping the giant constellation network and the static network to obtain mapping information;
所述映射信息为在任何时刻，离某一虚拟节点最近的卫星获得该节点的地理坐标；所述地理坐标为地理地址。The mapping information is the geographical coordinates of a virtual node obtained by the satellite closest to the node at any time; the geographical coordinates are the geographical addresses.
作为一种可选的实施方式，本发明实施例中，所述对所述链路状态数据表进行处理，得到最短路径信息，包括：As an optional implementation manner, in an embodiment of the present invention, the processing of the link state data table to obtain the shortest path information includes:
S41，对与任一LEO卫星一跳相连的第一卫星节点M1、第二卫星节点M2、第三卫星节点M3和第四卫星节点M4进行最短路径计算，得到第一卫星节点M1到目的地理地址的第一最短路径P1、第二卫星节点M2到目的地理地址的第二最短路径P2、第三卫星节点M3到目的地理地址的第三最短路径P3和第四卫星节点M4到目的地理地址的第四最短路径P4；S41, performing shortest path calculation on a first satellite nodeM1 , a second satellite nodeM2 , a third satellite nodeM3 and a fourth satellite nodeM4 connected to any LEO satellite by one hop, to obtain a first shortest pathP1 from the first satellite nodeM1 to a destination geographical address, a second shortest pathP2 from the second satellite nodeM2 to the destination geographical address, a third shortest pathP3 from the third satellite nodeM3 to the destination geographical address and a fourth shortest pathP4 from the fourth satellite nodeM4 to the destination geographical address;
S42，对所述第一卫星节点M1到目的地理地址的第一最短路径P1、所述第二卫星节点M2到目的地理地址的第二最短路径P2、所述第三卫星节点M3到目的地理地址的第三最短路径P3和所述第四卫星节点M4到目的地理地址的第四最短路径P4进行排序，得到距离最短的路径；S42, sort the first shortest pathP1 from the first satellite nodeM1 to the destination physical address, the second shortest pathP2 from the second satellite nodeM2 to the destination physical address, the third shortest pathP3 from the third satellite nodeM3 to the destination physical address, and the fourth shortest pathP4 from the fourth satellite nodeM4 to the destination physical address to obtain a path with the shortest distance;
S43，将所述距离最短的路径的下一跳添加到路由表中，得到最短路径信息；S43, adding the next hop of the path with the shortest distance to the routing table to obtain the shortest path information;
所述路由表包括目的卫星地理地址和下一跳卫星地理地址。The routing table includes a destination satellite geographical address and a next-hop satellite geographical address.
作为一种可选的实施方式，本发明实施例中，所述最短路径计算的方法为：As an optional implementation manner, in an embodiment of the present invention, the method for calculating the shortest path is:
对与任一LEO卫星三跳以内相连的LEO卫星和所述任一LEO卫星进行处理，得到图G(V,E)，其中V是顶点集合，E是边集合；Processing LEO satellites connected to any LEO satellite within three hops and the any LEO satellite to obtain a graph G(V,E), where V is a vertex set and E is an edge set;
对所述图G(V,E)进行权重计算，得到位于图G(V,E)中的边权重和位于图G(V,E)外的边权重；Performing weight calculation on the graph G(V,E) to obtain edge weights in the graph G(V,E) and edge weights outside the graph G(V,E);
对所述位于图G(V,E)中的边权重和所述位于图G(V,E)外的边权重进行处理，得到最短路径。The edge weights in the graph G(V, E) and the edge weights outside the graph G(V, E) are processed to obtain the shortest path.
作为一种可选的实施方式，本发明实施例第一方面中，所述位于图G(V,E)中的边权重表达式为：As an optional implementation, in the first aspect of the embodiment of the present invention, the edge weight expression in the graph G(V,E) is:
其中，e(i,j)是位于图G(V,E)中的卫星i和卫星j之间的边权重，τ(i,j)是卫星i和卫星j之间的链路传播延迟，n(t)是时刻t队列中的分组数，Lavg是平均分组长度。Where e(i,j) is the edge weight between satellite i and satellite j in the graph G(V,E), τ(i,j) is the link propagation delay between satellite i and satellite j, n(t) is the number of packets in the queue at time t, and Lavg is the average packet length.
作为一种可选的实施方式，本发明实施例中，所述位于图G(V,E)外的边权重为卫星i和卫星j之间的链路传播延迟τ(i,j)。As an optional implementation, in an embodiment of the present invention, the edge weight outside the graph G(V,E) is the link propagation delay τ(i,j) between satellite i and satellite j.
与现有技术相比，本发明实施例具有以下有益效果：Compared with the prior art, the embodiments of the present invention have the following beneficial effects:
(1)本发明采用了滚动优化思想，将最短路径计算从传统的全局优化转换为三跳范围内的局部优化，可以降低计算开销，提高路径计算的实时性，加快路由收敛速度；(1) The present invention adopts the rolling optimization concept, which converts the shortest path calculation from traditional global optimization to local optimization within a three-hop range, which can reduce the calculation overhead, improve the real-time performance of path calculation, and accelerate the routing convergence speed;
(2)本发明考虑了巨型星座网络中节点数量庞大的特性，通过将链路状态交换范围限制在三跳内，可以显著减少链路状态泛洪所需的开销；同时，可以确保链路状态信息的实时性；(2) The present invention takes into account the huge number of nodes in a giant constellation network. By limiting the scope of link state exchange to three hops, the overhead required for link state flooding can be significantly reduced. At the same time, the real-time nature of link state information can be ensured.
(3)本发明在路径计算过程中对三跳以外的边权重均采用链路传播延迟确定，可以保证路径计算的一致性，避免路由环路的产生。(3) In the process of path calculation, the present invention uses link propagation delay to determine the edge weights beyond three hops, which can ensure the consistency of path calculation and avoid the generation of routing loops.
附图说明BRIEF DESCRIPTION OF THE DRAWINGS
为了更清楚地说明本发明实施例中的技术方案，下面将对实施例描述中所需要使用的附图作简单地介绍，显而易见地，下面描述中的附图仅仅是本发明的一些实施例，对于本领域普通技术人员来讲，在不付出创造性劳动的前提下，还可以根据这些附图获得其他的附图。In order to more clearly illustrate the technical solutions in the embodiments of the present invention, the drawings required for use in the description of the embodiments will be briefly introduced below. Obviously, the drawings described below are only some embodiments of the present invention. For ordinary technicians in this field, other drawings can be obtained based on these drawings without paying creative work.
图1是本发明实施例公开的一种基于滚动优化的巨型星座网络路径选择方法的流程示意图；FIG1 is a schematic flow chart of a method for selecting a path in a giant constellation network based on rolling optimization according to an embodiment of the present invention;
图2是本发明实施例公开的另一种基于滚动优化的巨型星座网络路径选择方法的流程示意图。FIG2 is a flow chart of another method for selecting a path in a giant constellation network based on rolling optimization disclosed in an embodiment of the present invention.
具体实施方式DETAILED DESCRIPTION
为了使本技术领域的人员更好地理解本发明方案，下面将结合本发明实施例中的附图，对本发明实施例中的技术方案进行清楚、完整地描述，显然，所描述的实施例仅是本发明一部分实施例，而不是全部的实施例。基于本发明中的实施例，本领域普通技术人员在没有作出创造性劳动前提下所获得的所有其他实施例，都属于本发明保护的范围。In order to enable those skilled in the art to better understand the scheme of the present invention, the technical scheme in the embodiments of the present invention will be clearly and completely described below in conjunction with the drawings in the embodiments of the present invention. Obviously, the described embodiments are only part of the embodiments of the present invention, not all of the embodiments. Based on the embodiments of the present invention, all other embodiments obtained by ordinary technicians in this field without creative work are within the scope of protection of the present invention.
本发明的说明书和权利要求书及上述附图中的术语“第一”、“第二”等是用于区别不同对象，而不是用于描述特定顺序。此外，术语“包括”和“具有”以及它们任何变形，意图在于覆盖不排他的包含。例如包含了一系列步骤或单元的过程、方法、装置、产品或设备没有限定于已列出的步骤或单元，而是可选地还包括没有列出的步骤或单元，或可选地还包括对于这些过程、方法、产品或设备固有的其他步骤或单元。The terms "first", "second", etc. in the specification and claims of the present invention and the above-mentioned drawings are used to distinguish different objects, rather than to describe a specific order. In addition, the terms "including" and "having" and any variations thereof are intended to cover non-exclusive inclusions. For example, a process, method, device, product or equipment that includes a series of steps or units is not limited to the listed steps or units, but may optionally include steps or units that are not listed, or may optionally include other steps or units that are inherent to these processes, methods, products or equipment.
在本文中提及“实施例”意味着，结合实施例描述的特定特征、结构或特性可以包含在本发明的至少一个实施例中。在说明书中的各个位置出现该短语并不一定均是指相同的实施例，也不是与其它实施例互斥的独立的或备选的实施例。本领域技术人员显式地和隐式地理解的是，本文所描述的实施例可以与其它实施例相结合。Reference to "embodiments" herein means that a particular feature, structure, or characteristic described in conjunction with the embodiments may be included in at least one embodiment of the present invention. The appearance of the phrase in various places in the specification does not necessarily refer to the same embodiment, nor is it an independent or alternative embodiment that is mutually exclusive with other embodiments. It is explicitly and implicitly understood by those skilled in the art that the embodiments described herein may be combined with other embodiments.
本发明公开了一种基于滚动优化的巨型星座网络路径选择方法，该方法包括：构建巨型星座网络和静态网络；对所述巨型星座网络和所述静态网络进行映射，得到映射信息；根据所述映射信息，每个LEO卫星周期性与所述每个LEO卫星三跳以内相连的LEO卫星交换排队延迟信息，并将交换后的排队延迟信息保存在链路状态数据表中；所述链路状态数据表包括地理地址和排队延迟信息；对所述链路状态数据表进行处理，得到最短路径信息；根据所述最短路径信息选择下一跳LEO卫星，得到基于滚动优化的巨型星座网络路径选择结果。本发明采用了滚动优化思想，将全局最优路径计算分解为多段局部最优路径计算，可以降低计算复杂度，加快路由收敛速度；同时，将链路状态信息交换限制在局部区域，可以降低信令开销。以下分别进行详细说明。The present invention discloses a giant constellation network path selection method based on rolling optimization, the method comprising: constructing a giant constellation network and a static network; mapping the giant constellation network and the static network to obtain mapping information; according to the mapping information, each LEO satellite periodically exchanges queuing delay information with a LEO satellite connected within three hops of each LEO satellite, and saves the exchanged queuing delay information in a link state data table; the link state data table includes a geographic address and queuing delay information; processing the link state data table to obtain shortest path information; selecting the next hop LEO satellite according to the shortest path information to obtain a giant constellation network path selection result based on rolling optimization. The present invention adopts the rolling optimization concept, decomposing the global optimal path calculation into multiple segments of local optimal path calculation, which can reduce the calculation complexity and accelerate the routing convergence speed; at the same time, limiting the link state information exchange to a local area can reduce the signaling overhead. The following are detailed descriptions.
实施例一Embodiment 1
请参阅图1，图1是本发明实施例公开的一种基于滚动优化的巨型星座网络路径选择方法的流程示意图。其中，图1所描述的基于滚动优化的巨型星座网络路径选择方法应用于卫星通信网络技术领域，实现路由路径选择，本发明实施例不做限定。如图1所示，该基于滚动优化的巨型星座网络路径选择方法可以包括以下操作：Please refer to FIG. 1, which is a flowchart of a giant constellation network path selection method based on rolling optimization disclosed in an embodiment of the present invention. The giant constellation network path selection method based on rolling optimization described in FIG. 1 is applied to the field of satellite communication network technology to implement routing path selection, which is not limited in the embodiment of the present invention. As shown in FIG. 1, the giant constellation network path selection method based on rolling optimization may include the following operations:
S1，构建巨型星座网络和静态网络；S1, building giant constellation networks and static networks;
S2，对所述巨型星座网络和所述静态网络进行映射，得到映射信息；S2, mapping the giant constellation network and the static network to obtain mapping information;
S3，根据所述映射信息，每个LEO卫星周期性与所述每个LEO卫星三跳以内相连的LEO卫星交换排队延迟信息，并将交换后的排队延迟信息保存在链路状态数据表中；S3, according to the mapping information, each LEO satellite periodically exchanges queuing delay information with a LEO satellite connected to each LEO satellite within three hops, and stores the exchanged queuing delay information in a link state data table;
所述链路状态数据表包括地理地址和排队延迟信息；The link state data table includes geographic address and queuing delay information;
S4，对所述链路状态数据表进行处理，得到最短路径信息；S4, processing the link state data table to obtain the shortest path information;
S5，根据所述最短路径信息选择下一跳LEO卫星，得到基于滚动优化的巨型星座网络路径选择结果。S5, selecting a next-hop LEO satellite according to the shortest path information, and obtaining a giant constellation network path selection result based on rolling optimization.
可选的，所述巨型星座网络包括N个不同高度的LEO卫星星座；所述LEO卫星星座的轨道类型为极轨道；Optionally, the mega constellation network includes N LEO satellite constellations at different altitudes; the orbit type of the LEO satellite constellation is a polar orbit;
所述静态网络包括M个具有固定地理坐标的虚拟节点。The static network includes M virtual nodes with fixed geographical coordinates.
可选的，所述对所述巨型星座网络和所述静态网络进行映射，得到映射信息，包括：Optionally, mapping the giant constellation network and the static network to obtain mapping information includes:
根据最小距离原则，对所述巨型星座网络和所述静态网络进行映射，得到映射信息；According to a minimum distance principle, mapping the giant constellation network and the static network to obtain mapping information;
所述映射信息为在任何时刻，离某一虚拟节点最近的卫星获得该节点的地理坐标；所述地理坐标为地理地址。The mapping information is the geographical coordinates of a virtual node obtained by the satellite closest to the node at any time; the geographical coordinates are the geographical addresses.
可选的，所述对所述链路状态数据表进行处理，得到最短路径信息，包括：Optionally, the processing the link state data table to obtain the shortest path information includes:
S41，对与任一LEO卫星一跳相连的第一卫星节点M1、第二卫星节点M2、第三卫星节点M3和第四卫星节点M4进行最短路径计算，得到第一卫星节点M1到目的地理地址的第一最短路径P1、第二卫星节点M2到目的地理地址的第二最短路径P2、第三卫星节点M3到目的地理地址的第三最短路径P3和第四卫星节点M4到目的地理地址的第四最短路径P4；S41, performing shortest path calculation on a first satellite nodeM1 , a second satellite nodeM2 , a third satellite nodeM3 and a fourth satellite nodeM4 connected to any LEO satellite by one hop, to obtain a first shortest pathP1 from the first satellite nodeM1 to a destination geographical address, a second shortest pathP2 from the second satellite nodeM2 to the destination geographical address, a third shortest pathP3 from the third satellite nodeM3 to the destination geographical address and a fourth shortest pathP4 from the fourth satellite nodeM4 to the destination geographical address;
S42，对所述第一卫星节点M1到目的地理地址的第一最短路径P1、所述第二卫星节点M2到目的地理地址的第二最短路径P2、所述第三卫星节点M3到目的地理地址的第三最短路径P3和所述第四卫星节点M4到目的地理地址的第四最短路径P4进行排序，得到距离最短的路径；S42, sort the first shortest pathP1 from the first satellite nodeM1 to the destination physical address, the second shortest pathP2 from the second satellite nodeM2 to the destination physical address, the third shortest pathP3 from the third satellite nodeM3 to the destination physical address, and the fourth shortest pathP4 from the fourth satellite nodeM4 to the destination physical address to obtain a path with the shortest distance;
S43，将所述距离最短的路径的下一跳添加到路由表中，得到最短路径信息；S43, adding the next hop of the path with the shortest distance to the routing table to obtain the shortest path information;
所述路由表包括目的卫星地理地址和下一跳卫星地理地址。The routing table includes a destination satellite geographical address and a next-hop satellite geographical address.
可选的，所述最短路径计算的方法为：Optionally, the shortest path calculation method is:
对与任一LEO卫星三跳以内相连的LEO卫星和所述任一LEO卫星进行处理，得到图G(V,E)，其中V是顶点集合，E是边集合；Processing LEO satellites connected to any LEO satellite within three hops and the any LEO satellite to obtain a graph G(V,E), where V is a vertex set and E is an edge set;
对所述图G(V,E)进行权重计算，得到位于图G(V,E)中的边权重和位于图G(V,E)外的边权重；Performing weight calculation on the graph G(V,E) to obtain edge weights in the graph G(V,E) and edge weights outside the graph G(V,E);
对所述位于图G(V,E)中的边权重和所述位于图G(V,E)外的边权重进行处理，得到最短路径。The edge weights in the graph G(V, E) and the edge weights outside the graph G(V, E) are processed to obtain the shortest path.
所述最短路径为各边上权值之和最小的一条路径。The shortest path is a path with the smallest sum of weights on each edge.
可选的，所述位于图G(V,E)中的边权重表达式为：Optionally, the edge weight expression in the graph G(V,E) is:
其中，e(i,j)是位于图G(V,E)中的卫星i和卫星j之间的边权重，τ(i,j)是卫星i和卫星j之间的链路传播延迟，n(t)是时刻t队列中的分组数，Lavg是平均分组长度。Where e(i,j) is the edge weight between satellite i and satellite j in the graph G(V,E), τ(i,j) is the link propagation delay between satellite i and satellite j, n(t) is the number of packets in the queue at time t, and Lavg is the average packet length.
可选的，所述位于图G(V,E)外的边权重为卫星i和卫星j之间的链路传播延迟τ(i,j)。Optionally, the edge weight outside the graph G(V,E) is the link propagation delay τ(i,j) between satellite i and satellite j.
可见，本发明采用了滚动优化思想，将最短路径计算从传统的全局优化转换为三跳范围内的局部优化，可以降低计算开销，提高路径计算的实时性，加快路由收敛速度；本发明考虑了巨型星座网络中节点数量庞大的特性，通过将链路状态交换范围限制在三跳内，可以显著减少链路状态泛洪所需的开销；同时，可以确保链路状态信息的实时性；本发明在路径计算过程中对三跳以外的边权重均采用链路传播延迟确定，可以保证路径计算的一致性，避免路由环路的产生。It can be seen that the present invention adopts the idea of rolling optimization, converting the shortest path calculation from traditional global optimization to local optimization within a three-hop range, which can reduce the calculation overhead, improve the real-time performance of path calculation, and accelerate the routing convergence speed; the present invention takes into account the characteristics of a large number of nodes in a giant constellation network, and by limiting the link state exchange range to three hops, the overhead required for link state flooding can be significantly reduced; at the same time, the real-time performance of link state information can be ensured; in the process of path calculation, the present invention uses link propagation delay to determine the edge weights outside three hops, which can ensure the consistency of path calculation and avoid the generation of routing loops.
实施例二Embodiment 2
请参阅图2，图2是本发明实施例公开的另一种基于滚动优化的巨型星座网络路径选择方法的流程示意图。其中，图2所描述的基于滚动优化的巨型星座网络路径选择方法应用于卫星通信网络技术领域，实现路由路径选择，本发明实施例不做限定。如图2所示，该基于滚动优化的巨型星座网络路径选择方法可以包括以下操作：Please refer to FIG. 2, which is a flow chart of another giant constellation network path selection method based on rolling optimization disclosed in an embodiment of the present invention. The giant constellation network path selection method based on rolling optimization described in FIG. 2 is applied to the field of satellite communication network technology to implement routing path selection, which is not limited in the embodiment of the present invention. As shown in FIG. 2, the giant constellation network path selection method based on rolling optimization may include the following operations:
步骤S1，所述巨型星座网络，包括不同高度的LEO卫星星座，轨道类型为极轨道；采用虚拟节点设计，将巨型星座网络与静态网络对应，静态网络由具有固定地理坐标的虚拟节点组成。根据最小距离原则将巨型星座网络和静态网络进行映射，在任何时刻，离某一虚拟节点最近的卫星获得该节点的地理坐标，将该坐标称为地理地址；Step S1, the giant constellation network includes LEO satellite constellations at different altitudes, and the orbit type is a polar orbit; a virtual node design is adopted to correspond the giant constellation network to a static network, and the static network is composed of virtual nodes with fixed geographical coordinates. The giant constellation network and the static network are mapped according to the minimum distance principle. At any time, the satellite closest to a virtual node obtains the geographical coordinates of the node, and the coordinates are called the geographical address;
每个LEO卫星周期性与其三跳以内相连的LEO卫星交换排队延迟信息，并保存在链路状态数据表。链路状态数据表包含地理地址与排队延迟信息；Each LEO satellite periodically exchanges queuing delay information with LEO satellites connected within three hops and saves it in the link state data table. The link state data table contains geographic address and queuing delay information;
步骤S2，将步骤S1中，与一颗LEO卫星三跳以内相连的LEO卫星(含该LEO卫星)所组成的图记为G(V,E)，如图2所示；其中V是顶点集合，E是边集合。边的权重由链路传播延迟与排队延迟之和确定；边e(i,j)的权重为Step S2: The graph consisting of LEO satellites (including the LEO satellite) connected to a LEO satellite within three hops in step S1 is denoted as G(V,E), as shown in Figure 2; V is the vertex set and E is the edge set. The weight of the edge is determined by the sum of the link propagation delay and the queuing delay; the weight of edge e(i,j) is
其中，τ(i,j)是卫星i和卫星j之间的链路传播延迟，n(t)是时刻t队列中的分组数，Lavg是平均分组长度；Where τ(i,j) is the link propagation delay between satellite i and satellite j, n(t) is the number of packets in the queue at time t, and Lavg is the average packet length;
步骤S3，将与该LEO卫星一跳相连的卫星节点记为M1,M2,M3,M4，LEO卫星分别计算M1,M2,M3,M4到目的地理地址的最短路径，将四条最短路径记为P1,P2,P3,P4。在计算最短路径时，位于图G(V,E)中的边权重由步骤S2所述方法计算，位于图G(V,E)外的边权重由链路传播延迟确定，有Step S3, record the satellite nodes connected to the LEO satellite by one hop as M1 , M2 , M3 , M4 , and the LEO satellite calculates the shortest paths from M1 , M2 , M3 , M4 to the destination address respectively, and record the four shortest paths as P1, P2, P3, P4. When calculating the shortest path, the edge weights in the graph G(V, E) are calculated by the method described in step S2, and the edge weights outside the graph G(V, E) are determined by the link propagation delay, and there is
步骤S4，选择P1,P2,P3,P4中的最短路径，将该路径的下一跳添加到路由表。Step S4, select the shortest path among P1, P2, P3, and P4, and add the next hop of the path to the routing table.
路由表包含目的卫星地理地址、下一跳卫星地理地址信息。The routing table contains the destination satellite geographic address and the next hop satellite geographic address information.
可见，本发明采用了滚动优化思想，将最短路径计算从传统的全局优化转换为三跳范围内的局部优化，可以降低计算开销，提高路径计算的实时性，加快路由收敛速度；本发明考虑了巨型星座网络中节点数量庞大的特性，通过将链路状态交换范围限制在三跳内，可以显著减少链路状态泛洪所需的开销；同时，可以确保链路状态信息的实时性；本发明在路径计算过程中对三跳以外的边权重均采用链路传播延迟确定，可以保证路径计算的一致性，避免路由环路的产生。It can be seen that the present invention adopts the idea of rolling optimization, converting the shortest path calculation from traditional global optimization to local optimization within a three-hop range, which can reduce the calculation overhead, improve the real-time performance of path calculation, and accelerate the routing convergence speed; the present invention takes into account the characteristics of a large number of nodes in a giant constellation network, and by limiting the link state exchange range to three hops, the overhead required for link state flooding can be significantly reduced; at the same time, the real-time performance of link state information can be ensured; in the process of path calculation, the present invention uses link propagation delay to determine the edge weights outside three hops, which can ensure the consistency of path calculation and avoid the generation of routing loops.
以上所描述的装置实施例仅是示意性的，其中作为分离部件说明的模块可以是或者也可以不是物理上分开的，作为模块显示的部件可以是或者也可以不是物理模块，即可以位于一个地方，或者也可以分布到多个网络模块上。可以根据实际的需要选择其中的部分或者全部模块来实现本实施例方案的目的。本领域普通技术人员在不付出创造性的劳动的情况下，即可以理解并实施。The device embodiments described above are only illustrative, wherein the modules described as separate components may or may not be physically separated, and the components displayed as modules may or may not be physical modules, i.e., they may be located in one place, or they may be distributed on multiple network modules. Some or all of the modules may be selected according to actual needs to achieve the purpose of the scheme of this embodiment. Those of ordinary skill in the art may understand and implement it without paying creative labor.
通过以上的实施例的具体描述，本领域的技术人员可以清楚地了解到各实施方式可借助软件加必需的通用硬件平台的方式来实现，当然也可以通过硬件。基于这样的理解，上述技术方案本质上或者说对现有技术做出贡献的部分可以以软件产品的形式体现出来，该计算机软件产品可以存储在计算机可读存储介质中,存储介质包括只读存储器(Read-Only Memory，ROM)、随机存储器(Random Access Memory，RAM)、可编程只读存储器(Programmable Read-only Memory，PROM)、可擦除可编程只读存储器(ErasableProgrammable Read Only Memory，EPROM)、一次可编程只读存储器(One-timeProgrammable Read-Only Memory，OTPROM)、电子抹除式可复写只读存储器(Electrically-Erasable Programmable Read-Only Memory，EEPROM)、只读光盘(CompactDisc Read-Only Memory，CD-ROM)或其他光盘存储器、磁盘存储器、磁带存储器、或者能够用于携带或存储数据的计算机可读的任何其他介质。Through the specific description of the above embodiments, those skilled in the art can clearly understand that each implementation method can be implemented by means of software plus a necessary general hardware platform, and of course, it can also be implemented by hardware. Based on such an understanding, the above technical solution can be essentially or partly contributed to the prior art in the form of a software product, and the computer software product can be stored in a computer-readable storage medium, and the storage medium includes a read-only memory (ROM), a random access memory (RAM), a programmable read-only memory (PROM), an erasable programmable read-only memory (EPROM), a one-time programmable read-only memory (OTPROM), an electronically erasable rewritable read-only memory (EEPROM), a compact disc (CD-ROM) or other optical disc storage, magnetic disk storage, magnetic tape storage, or any other computer-readable medium that can be used to carry or store data.
最后应说明的是：本发明实施例公开的一种基于滚动优化的巨型星座网络路径选择方法及装置所揭露的仅为本发明较佳实施例而已，仅用于说明本发明的技术方案，而非对其限制；尽管参照前述实施例对本发明进行了详细的说明，本领域的普通技术人员应当理解；其依然可以对前述各项实施例所记载的技术方案进行修改，或者对其中部分技术特征进行等同替换；而这些修改或替换，并不使相应的技术方案的本质脱离本发明各项实施例技术方案的精神和范围。Finally, it should be noted that the giant constellation network path selection method and device based on rolling optimization disclosed in the embodiment of the present invention discloses only the preferred embodiment of the present invention, which is only used to illustrate the technical solution of the present invention, rather than to limit it. Although the present invention has been described in detail with reference to the aforementioned embodiments, it should be understood by those skilled in the art that the technical solutions described in the aforementioned embodiments can still be modified, or some of the technical features therein can be replaced by equivalents. However, these modifications or replacements do not deviate the essence of the corresponding technical solutions from the spirit and scope of the technical solutions of the various embodiments of the present invention.
| Application Number | Priority Date | Filing Date | Title |
|---|---|---|---|
| CN202410821215.3ACN118611736A (en) | 2024-06-24 | 2024-06-24 | A path selection method for giant constellation networks based on rolling optimization |
| Application Number | Priority Date | Filing Date | Title |
|---|---|---|---|
| CN202410821215.3ACN118611736A (en) | 2024-06-24 | 2024-06-24 | A path selection method for giant constellation networks based on rolling optimization |
| Publication Number | Publication Date |
|---|---|
| CN118611736Atrue CN118611736A (en) | 2024-09-06 |
| Application Number | Title | Priority Date | Filing Date |
|---|---|---|---|
| CN202410821215.3APendingCN118611736A (en) | 2024-06-24 | 2024-06-24 | A path selection method for giant constellation networks based on rolling optimization |
| Country | Link |
|---|---|
| CN (1) | CN118611736A (en) |
| Publication number | Priority date | Publication date | Assignee | Title |
|---|---|---|---|---|
| CN113767599A (en)* | 2019-05-23 | 2021-12-07 | 慧与发展有限责任合伙企业 | Optimized adaptive routing for hop reduction |
| CN114499644A (en)* | 2022-02-11 | 2022-05-13 | 西安电子科技大学 | Load Balancing Routing Method Based on Accurate Link State Feedback |
| CN114828144A (en)* | 2022-03-27 | 2022-07-29 | 西安电子科技大学 | Low-earth-orbit satellite constellation-oriented service quality guarantee routing method |
| Publication number | Priority date | Publication date | Assignee | Title |
|---|---|---|---|---|
| CN113767599A (en)* | 2019-05-23 | 2021-12-07 | 慧与发展有限责任合伙企业 | Optimized adaptive routing for hop reduction |
| CN114499644A (en)* | 2022-02-11 | 2022-05-13 | 西安电子科技大学 | Load Balancing Routing Method Based on Accurate Link State Feedback |
| CN114828144A (en)* | 2022-03-27 | 2022-07-29 | 西安电子科技大学 | Low-earth-orbit satellite constellation-oriented service quality guarantee routing method |
| Publication | Publication Date | Title |
|---|---|---|
| Gelenbe et al. | Improved neural heuristics for multicast routing | |
| EP0348327B1 (en) | Method of derermining an optimal end node to end node route through a data communications network | |
| CN108964746B (en) | Multi-topology search method for shortest route in time-varying satellite network | |
| CN111065105A (en) | Distributed intelligent routing method for unmanned aerial vehicle network slice | |
| CN116170327B (en) | Incremental deployment method for segmented routing networks based on graph neural network and reinforcement learning | |
| CN109586785A (en) | Low-track satellite network routing policy based on K shortest path first | |
| CN113821317B (en) | Side cloud cooperative microservice scheduling method, device and equipment | |
| CN113810287B (en) | A data retrieval and push method based on NDN and SDN | |
| Camelo et al. | Efficient routing in data center with underlying cayley graph | |
| JP2021530893A (en) | Physical network element Node virtualization methods, devices, equipment and storage media | |
| CN110099081A (en) | CDN system and its time source method, apparatus | |
| CN115361049B (en) | A routing method, device and electronic device based on direction constraints | |
| CN116112421A (en) | A routing optimization method and device | |
| CN118611736A (en) | A path selection method for giant constellation networks based on rolling optimization | |
| CN112511445B (en) | Shortest path route generating method based on load weighting | |
| CN115118655A (en) | Cross-network message forwarding method and device, electronic equipment and readable storage medium | |
| CN110177011A (en) | A Network Controller Deployment Method Adapting to Dynamic Network Structure | |
| CN107276898B (en) | A Shortest Routing Implementation Method Based on FPGA | |
| CN117614511A (en) | Method for planning ground transmission path of perception-limited giant star seat state data | |
| Noskov et al. | Interaction model of computer nodes based on transfer reservation at multipath routing | |
| US11405284B1 (en) | Generating network link utilization targets using a packet-loss-versus-link utilization model | |
| CN110768906B (en) | SDN-oriented energy-saving routing method based on Q learning | |
| Alnaser et al. | Modified Method of Traffic Engineering in DCN with a Ramified Topology | |
| CN111953522A (en) | A software optical network controller deployment method and storage medium | |
| CN116996431A (en) | A data processing method and device for optimizing network congestion |
| Date | Code | Title | Description |
|---|---|---|---|
| PB01 | Publication | ||
| PB01 | Publication | ||
| SE01 | Entry into force of request for substantive examination | ||
| SE01 | Entry into force of request for substantive examination |