CN115276759A - A Design Method of Double-layer Satellite Network Connection Plan Based on Weighted Space-Time Map - Google Patents

Abstract

The invention discloses a double-layer satellite network connection plan design method based on a weighted space-time diagram, and belongs to the technical field of wireless communication. The method is oriented to a double-layer satellite network consisting of low orbit satellites and static satellites, and aims at the problems of time-varying network topology and limited node resources, the cost, the energy efficiency and the unreliability are comprehensively considered, and a weighted space-time diagram is constructed to perform static discretization processing on dynamic time-varying topology; quantizing connection cost according to energy consumed by data transmission, defining connection energy efficiency according to connection capacity and data flow, and evaluating connection unreliability according to a physical layer technology to obtain the weight of each time and space connection in a space-time diagram; under a model meeting network connectivity and reliability constraints, three connection plans based on weighted space-time diagrams are designed by introducing pruning and greedy algorithms with the aim of minimum cost, maximum energy efficiency and minimum cost-efficiency ratio. The invention optimizes the network redundant connection through the connection plan and simultaneously improves the utilization rate of network resources.

Description

Translated fromChinese

一种基于加权时空图的双层卫星网络连接计划设计方法A Design Method for Double-layer Satellite Network Connection Plan Based on Weighted Space-Time Graph

技术领域technical field

本发明属于无线通信技术领域，涉及一种基于加权时空图的双层卫星网络连接计划设计方法。The invention belongs to the technical field of wireless communication, and relates to a method for designing a double-layer satellite network connection plan based on a weighted space-time diagram.

背景技术Background technique

随着空间技术的快速发展和国家战略进程的不断推进，卫星网络在处理空间信息的传输、获取和分发中起着极其重要的作用，是未来完备空天地一体化网络的重要组成部分。卫星网络以广阔的覆盖范围、充足的网络资源，灵活的部署条件等特征，作为地面网络强有力的补充，被广泛应用于许多领域，如深空探测、地球观测、海域通信、应急通信和定位导航等。我国“十四五”规划中推进卫星通信系统与地面信息通信系统深度融合，从而初步形成覆盖全球、天地一体的信息网络。因此，将卫星网络的研究作为重要的研究方向。双层卫星网络系统相比于单层卫星网络，节点的移动性差异以及立体的层次结构导致网络中节点建立的连接具有偶发性，使得星间连接和网络拓扑在不断的变化。相比地面网络节点，卫星的运行成本较高且卫星星上资源有限，卫星位于的空间环境复杂因此不能随意更换。With the rapid development of space technology and the continuous advancement of the national strategic process, the satellite network plays an extremely important role in the transmission, acquisition and distribution of space information, and is an important part of the future complete air-space-ground integration network. Satellite network is widely used in many fields, such as deep space exploration, earth observation, sea area communication, emergency communication and positioning, as a powerful supplement to the ground network due to its wide coverage, sufficient network resources, and flexible deployment conditions. navigation etc. my country's "14th Five-Year Plan" promotes the deep integration of satellite communication systems and ground information communication systems, thus initially forming an information network that covers the world and integrates space and ground. Therefore, the study of satellite network is an important research direction. Compared with the single-layer satellite network, the difference in node mobility and the three-dimensional hierarchical structure of the double-layer satellite network system lead to sporadic connections between nodes in the network, which makes the inter-satellite connection and network topology constantly changing. Compared with ground network nodes, the operating cost of satellites is higher and the resources on satellites are limited, and the space environment where satellites are located is complex, so they cannot be replaced at will.

连接计划设计是空间网络拓扑结构优化和网络性能提高的关键技术之一。如果把双层卫星网络中所有潜在的接触都配置为全连通的连接计划非常奢侈，庞大的潜在接触使网络中的接触过度冗余，增加了网络的复杂度和节点的计算复杂性。因此，利用剪枝与贪婪算法构造基于加权时空图的连接计划，在满足网络连通性和可靠性约束的条件下，合理规划网络中的可用连接，减少冗余连接的同时提升网络资源利用率。Connection plan design is one of the key technologies for spatial network topology optimization and network performance improvement. If it is a luxury to configure all potential contacts in the double-layer satellite network as a fully connected connection plan, the huge potential contacts make the contacts in the network excessively redundant, increasing the complexity of the network and the computational complexity of the nodes. Therefore, the pruning and greedy algorithm is used to construct the connection plan based on the weighted space-time graph. Under the condition of satisfying the network connectivity and reliability constraints, the available connections in the network are reasonably planned, and the redundant connections are reduced while improving the utilization of network resources.

CN109740832A，一种用于增强卫星系统自主导航能力的连接计划设计方法，依据星历计算得到可视矩阵；各卫星节点依据可视矩阵采用公平性连接计划算法计算得到连接计划输出；各节点在时间同步的基础上，分别按照连接计划设计结果在连接计划设计周期起始时刻同时执行链路调度。对于每个链路调度周期，连接计划设计过程均在星上完成而不依赖于地面站：1)卫星网络中各卫星节点通过与其他卫星节点进行信息交互，获取统一的全网最新星历，并依据星历计算得到可视矩阵，即连接计划设计的输入；2)卫星网络中各节点对确定的连接计划设计周期，对输入采用确定性的连接计划设计算法，在星上计算得到相同的连接计划设计输出；3)卫星网络中各卫星节点在时间同步的基础上，分别按照连接计划设计结果在连接计划设计周期起始时刻同时执行链路调度。CN109740832A, a connection plan design method for enhancing the autonomous navigation capability of a satellite system, obtains a visible matrix based on ephemeris calculations; each satellite node calculates a connection plan output by using a fair connection plan algorithm according to the visible matrix; On the basis of synchronization, link scheduling is executed simultaneously at the beginning of the connection plan design cycle according to the connection plan design results. For each link scheduling cycle, the connection plan design process is completed on the satellite without depending on the ground station: 1) Each satellite node in the satellite network interacts with other satellite nodes to obtain the latest unified ephemeris of the entire network, And calculate the visual matrix according to the ephemeris, that is, the input of the connection plan design; 2) Each node in the satellite network uses a deterministic connection plan design algorithm for the input to determine the connection plan design cycle, and calculates the same on the satellite. Connection plan design output; 3) Each satellite node in the satellite network executes link scheduling at the beginning of the connection plan design cycle at the same time according to the connection plan design results on the basis of time synchronization.

该专利根据星历计算得到可视矩阵，将可视矩阵作为连接计划设计的输入。确定连接计划设计的周期并划分每个周期的时隙，在每个时隙开始时刻输入可视矩阵。将可视矩阵转换为图模型，将所有连接的权重都设置为无穷大。对当前时隙的进行完全图最大权非完美匹配，当连接被匹配则将权重设定为0，通过匹配得到连接计划。本发明，对网络中存在的连接进行了基本的约束，引入深度优先搜索和剪枝排除无效或不满足的条件的连接，搜索到基本优化后的网络拓扑，以此减少了后续连接计划设计的复杂性。按照低轨卫星周期划分为多个时隙，通过加权时空图表征每个时隙中的网络拓扑时间连接和空间连接变化的关系。在设计连接计划时考虑了连接的权重，所有连接的权重综合考虑成本、能效以及不可靠性，而不是单单的设定为一个固定值。引入贪婪算法，分别以最小成本、最大能效、最小成本效率比为目标，设计基于加权时空图的连接计划。The patent calculates the visibility matrix according to the ephemeris, and uses the visibility matrix as the input of the connection plan design. Determine the cycle of the connection planning design and divide the time slots of each cycle, and input the visual matrix at the beginning of each time slot. Convert the visual matrix to a graphical model, setting all connection weights to infinity. Perform complete graph maximum weight imperfect matching on the current time slot, set the weight to 0 when the connection is matched, and obtain the connection plan through matching. The present invention imposes basic constraints on the connections existing in the network, introduces depth-first search and pruning to exclude invalid or unsatisfied connections, and searches for a basically optimized network topology, thereby reducing the cost of subsequent connection plan design. Complexity. It is divided into multiple time slots according to the cycle of low-orbit satellites, and the relationship between the network topology time connection and space connection change in each time slot is represented by a weighted space-time diagram. When designing the connection plan, the weight of the connection is considered. The weight of all connections takes into account cost, energy efficiency and unreliability, rather than simply setting it as a fixed value. A greedy algorithm is introduced, aiming at minimum cost, maximum energy efficiency, and minimum cost-efficiency ratio, respectively, and designing a connection plan based on weighted space-time graph.

发明内容Contents of the invention

本发明旨在解决以上现有技术的问题。提出了一种基于加权时空图的双层卫星网络连接计划设计方法。本发明的技术方案如下：The present invention aims to solve the above problems of the prior art. A design method of two-level satellite network connection plan based on weighted space-time graph is proposed. Technical scheme of the present invention is as follows:

一种基于加权时空图的双层卫星网络连接计划设计方法，其包括以下步骤：A method for designing a double-layer satellite network connection plan based on a weighted space-time graph, comprising the following steps:

步骤101、根据静止轨道(Geostationary earth orbit,GEO)卫星的覆盖区域以及不同轨道卫星之间的物理可见性分析网络中存在的各类连接，基于DFS和 Pruning遍历相关约束下网络中存在的各类连接，找到任意两个卫星节点之间存在的路径；Step 101. According to the coverage area of geostationary earth orbit (GEO) satellites and the physical visibility between satellites in different orbits, analyze the various types of connections existing in the network, and traverse the various types of connections existing in the network based on DFS and Pruning related constraints. Connect to find the path that exists between any two satellite nodes;

步骤102、根据低轨(Low earth orbit,LEO)卫星的周期性运动以及网络拓扑结构和节点间相对位置的动态变化关系，设计加权时空图建模动态网络；Step 102, according to the periodic motion of the low earth orbit (Low earth orbit, LEO) satellite and the dynamic change relationship between the network topology and the relative position of the nodes, design a weighted space-time graph to model the dynamic network;

步骤103、根据传输数据所消耗的能源量化连接成本，根据连接容量和数据流量定义连接能效，根据物理层技术评估连接不可靠性，得到时空图中每个时间和空间连接的权重；Step 103. Quantify the connection cost according to the energy consumed for transmitting data, define the connection energy efficiency according to the connection capacity and data flow, evaluate the connection unreliability according to the physical layer technology, and obtain the weight of each time and space connection in the space-time diagram;

步骤104、在满足网络连通性和可靠性约束的模型下，以最小成本、最大能效、最小成本效率比为目标，引入剪枝和贪婪算法设计基于加权时空图的连接计划。Step 104, under a model that satisfies the constraints of network connectivity and reliability, aiming at minimum cost, maximum energy efficiency, and minimum cost-effectiveness ratio, introduce a pruning and greedy algorithm to design a connection plan based on a weighted space-time graph.

进一步的，所述通过步骤101，根据静止轨道卫星的覆盖区域以及不同轨道卫星之间的物理可见性分析网络中存在的各类连接，基于DFS和Pruning遍历相关约束下网络中存在的各类连接，找到任意两个卫星节点之间存在的路径：Further, through step 101, analyze various types of connections existing in the network according to the coverage area of geostationary orbit satellites and physical visibility between satellites in different orbits, and traverse various types of connections existing in the network based on DFS and Pruning related constraints , find the path that exists between any two satellite nodes:

(1)GEO覆盖区域划分；(1) GEO coverage area division;

计算LEO层GEO足印区域的半边中心角λ以及GEO星下点与LEO的地心夹角∠A'OB，LEO层GEO覆盖区域的半边中心角λ表示式(1)：Calculate the half-side central angle λ of the GEO footprint area of the LEO layer and the angle ∠A'OB between the GEO sub-satellite point and the center of the LEO, and the half-side central angle λ of the GEO coverage area of the LEO layer is expressed in (1):

其中，R为地球半径，h_G、h_L分别为GEO和LEO卫星的轨道高度，ε_min为LEO 与GEO卫星之间的最小仰角；Among them, R is the radius of the earth, h_G , h_L are the orbit heights of GEO and LEO satellites respectively, and ε_min is the minimum elevation angle between LEO and GEO satellites;

GEO星下点与LEO的地心夹角通过式(2)表示：The angle between the sub-satellite point of GEO and the center of LEO is expressed by formula (2):

其中，|A'B|指GEO卫星位于LEO层的星下点与LEO的间距；Among them, |A'B| refers to the distance between the sub-satellite point of the GEO satellite located in the LEO layer and LEO;

当LEO卫星满足GEO星下点与该LEO的地心夹角小于半边中心角的条件(3)，则表示该LEO位于GEO覆盖范围；When the LEO satellite satisfies the condition (3) that the angle between the sub-satellite point of GEO and the center of the LEO is less than half the central angle, it means that the LEO is located in the GEO coverage area;

∠A'OB≤λ (3)∠A'OB≤λ (3)

(2)卫星的物理可见性判断；(2) Judgment of the physical visibility of the satellite;

已知卫星S_i和卫星S_j的地理位置坐标分别为

则两卫星与地面形成的地心夹角θ可通过式(4)计算得到：The geographic coordinates of known satellite S_i and satellite S_j are respectively

Then the angle θ formed between the two satellites and the ground can be calculated by formula (4):

已知地心夹角θ，通过式(5)-(7)计算出卫星节点对(S_i,S_j)之间的间距L_i,j以及各自的仰角δ_i和δ_j：Knowing the angle θ between the center of the earth, the distance L_i,j between the satellite node pair (S_i ,S_j ) and the respective elevation angles δ_i and δ_j are calculated by formulas (5)-(7):

其中，R_i和R_j分别为卫星S_i和卫星S_j的轨道半径；Among them, R_i and R_j are the orbital radii of satellite S_i and satellite S_j respectively;

通过上述推导计算瞬时卫星S_i和卫星S_j之间的连接与地心角的垂直高度h_i,j：Calculate the vertical height h_i,j of the connection between the instantaneous satellite S_i and the satellite S_j with respect to the geocentric angle by the above derivation:

h_i,j＝R_icos(δ_i)＝R_jcos(δ_j) (8)h_i,j =R_i cos(δ_i )=R_j cos(δ_j ) (8)

进一步的，所述(1)GEO覆盖区域划分步骤中，在任意时刻，LEO可能同时位于2-3颗GEO卫星的覆盖范围内，为了避免每个GEO重复连接到一颗 LEO卫星，对LEO卫星有以下限制条件：当一颗LEO卫星同时位于2-3个GEO 卫星的足印区域内，则LEO选择距离最近的GEO，归属于该GEO的覆盖范围内。Further, in the (1) GEO coverage area division step, at any moment, LEO may be located within the coverage of 2-3 GEO satellites at the same time, in order to avoid each GEO being repeatedly connected to a LEO satellite, the LEO satellite There are the following restrictions: when a LEO satellite is located within the footprint area of 2-3 GEO satellites at the same time, LEO will select the closest GEO and belong to the coverage of the GEO.

进一步的，所述步骤(2)卫星的物理可见性判断步骤中：Further, in the step (2) satellite physical visibility judgment step:

不同轨道高度的卫星可见性由卫星节点对之间的瞬时空间连接与地心角的垂直高度h_i,j决定；当h_i,j大于地球半径R时，卫星S_i和卫星S_j是物理可见的，即表示此时卫星S_i和S_j可建立连接；由于地球上空大气层信号的衰减及干扰，卫星之间的连接受到大气层的影响，在判断空间连接是否可建立时，不仅要依据建立空间连接的物理可见性临界条件，同时要考虑保护余隙H，以此减小大气层影响造成的误差，因此，当且仅当满足式(9)，不同轨道平面的卫星之间才可以建立空间连接：Satellite visibility at different orbital heights is determined by the instantaneous spatial connection between satellite node pairs and the vertical height h_i,j of the geocentric angle; when h_i,j is greater than the radius R of the earth, satellite S_i and satellite S_j are physically Visible means that satellites S_i and S_j can establish a connection at this time; due to the attenuation and interference of atmospheric signals above the earth, the connection between satellites is affected by the atmosphere. When judging whether a space connection can be established, it is not only based on the established The critical condition of physical visibility of the space connection, at the same time, the protection clearance H should be considered, so as to reduce the error caused by the influence of the atmosphere. Therefore, if and only if formula (9) is satisfied, the space between satellites in different orbital planes can be established connect:

h_i,j≥R+H (9)h_i,j ≥ R+H (9)

在双层卫星网络中，在同一轨道内卫星的距离是均匀分布的且具有相同的运行速度，因此，在同一轨道内卫星之间相对位置的变化可以忽略，空间连接能够稳定并一直持续。In a double-layer satellite network, the distances of satellites in the same orbit are evenly distributed and have the same speed. Therefore, the relative position changes between satellites in the same orbit can be ignored, and the space connection can be stable and continuous.

进一步的，所述的深度优先搜索和剪枝包括(1)对于新发现的卫星节点S_v，访问该节点；(2)如果S_v有一条未被检测的连接，则遍历该连接并将相邻节点作为下一起点；(3)将相邻节点作为顶点，继续沿着这个连接进行检测，直到搜索完节点S_v的所有连接；(4)重复遍历的过程，直到网络中所有节点和相通路径都被访问，最终搜索到网络的初始拓扑；(5)将初始拓扑作为输入，根据各类连接的相关约束条件，灵活设计并优化相应的搜索规则，通过剪枝以排除无效或不满足的条件的连接，从而对DFS得到的初始拓扑进行优化。Further, the depth-first search and pruning include (1) for the newly discovered satellite node S_v , visit the node; (2) if S_v has an undetected connection, traverse the connection and The adjacent node is used as the next starting point; (3) Take the adjacent node as the vertex, and continue to detect along this connection until all the connections of the node S_v are searched; (4) Repeat the traversal process until all nodes in the network are connected to The paths are all visited, and the initial topology of the network is finally searched; (5) The initial topology is used as input, and according to the relevant constraints of various connections, the corresponding search rules are flexibly designed and optimized, and invalid or unsatisfied ones are excluded by pruning. Conditional connection, so as to optimize the initial topology obtained by DFS.

进一步的，所述步骤102根据卫星的周期性运动以及网络拓扑结构和节点间相对位置的动态变化关系，设计加权时空图建模动态网络，具体包括以下步骤：Further, the step 102 designs a weighted spatio-temporal graph modeling dynamic network according to the periodic movement of the satellite and the network topology and the dynamic relationship between the relative positions of the nodes, specifically including the following steps:

(1)按照LEO卫星的周期将动态网络划分为多个快照时隙；(1) Divide the dynamic network into multiple snapshot time slots according to the period of the LEO satellite;

假设LEO卫星的运动周期为T，并且将该周期划分为离散等间隔的时间段 {T₁,T₂,…,T_n}，设G^t＝(V^t,E^t)是一个有向图表示网络在时隙t的快照，在每个快照中网络拓扑是固定不变的，将动态网络建模为一系列快照{G^t|t＝1,2,…,T}的合集；Assuming that the motion period of the LEO satellite is T, and this period is divided into discrete time intervals {T₁ , T₂ ,…,T_n }, let G^t = (V^t , E^t ) be a directed graph Represents the snapshot of the network at time slot t, the network topology is fixed in each snapshot, and the dynamic network is modeled as a collection of snapshots {G^t |t=1,2,...,T};

(2)将快照序列转换为加权时空图；(2) Convert the sequence of snapshots into a weighted spatiotemporal graph;

将快照序列{G^t|t＝1,2,…,T}转换成加权时空图，在相邻层之间添加空间和时间连接，空间连接

指节点v_i与节点v_j在t时隙中存在的连接，表示在t时隙中节点v_i向另一个节点v_j传输信息，时间连接

指连接同一节点v_i，表示在时隙t期间存储信息，时空图中的连接集合为

通过定义加权时空图，可以利用有向图捕捉时变网络中的拓扑变化。Convert the sequence of snapshots {G^t |t=1,2,…,T} into a weighted spatiotemporal graph, adding spatial and temporal connections between adjacent layers, spatial connections

Refers to the connection between node v_i and node v_j in time slot t, which means that node v_i transmits information to another node v_j in time slot t, and the time connection

Refers to connecting the same node v_i , which means storing information during time slot t, and the connection set in the space-time graph is

By defining a weighted spatiotemporal graph, directed graphs can be exploited to capture topological changes in time-varying networks.

进一步的，所述步骤103根据传输数据所消耗的能源量化连接成本，根据连接容量和数据流量定义连接能效，根据物理层技术评估连接不可靠性，得到时空图中每个时间和空间连接的权重，具体步骤如下：Further, the step 103 quantifies the connection cost according to the energy consumed for transmitting data, defines the connection energy efficiency according to the connection capacity and data flow, evaluates the connection unreliability according to the physical layer technology, and obtains the weight of each time and space connection in the time-space diagram ,Specific steps are as follows:

(1)成本(1) cost

对于空间连接，成本是该连接传递数据的能源消耗如式(10)所示，表示通过连接传输数据的等效功耗，对于时间连接，成本对应于存储数据的能量消耗如式(11)所示：For a spatial connection, the cost is the energy consumption of data transmitted by the connection, as shown in Equation (10), which represents the equivalent power consumption of transmitting data through the connection. For a temporal connection, the cost corresponds to the energy consumption of storing data, as shown in Equation (11). Show:

其中，其中P_w为空间连接的恒定传输功率，P_s为时间连接的恒定传输功率，

为连接所传输的实际数据量，

为能够传输的最大数据量；where P_w is the constant transmission power of the space connection, P_s is the constant transmission power of the time connection,

is the actual amount of data transferred for the connection,

is the maximum amount of data that can be transmitted;

(2)能效(2) Energy efficiency

对于空间连接，能效与传输的数据相关通过式(12)表示；对于时间连接，能效与剩余存储空间相关联由式(13)表示；For spatial connections, the relationship between energy efficiency and transmitted data is expressed by formula (12); for time connections, the relationship between energy efficiency and remaining storage space is expressed by formula (13);

其中，

为连接的容量，

为能够传输的最大数据量。in,

is the capacity of the connection,

is the maximum amount of data that can be transferred.

(3)成本效率比(3) Cost-effectiveness ratio

一个连接的成本效率比由φ(e)＝c(e)/ε(e)表示，一个时空图G^t＝(V^t,E^t)的成本效率比φ(G^t)是所有连接成本效率比的平均值，即

mean 表示平均值，一条路径

的成本效率比为该路径上所有连接成本效率比的平均值通过式(14)表示：The cost-efficiency ratio of a connection is represented by φ(e)=c(e)/ε(e), and the cost-efficiency ratio φ(G^t ) of a space-time graph G^t =(V^t ,E^t ) is the cost efficiency of all connections than the average value of

mean represents the mean value, a path

The cost-efficiency ratio of is the average cost-efficiency ratio of all connections on the path, which is expressed by formula (14):

其中，

表示在时空图G中，从t＝0时刻到t＝T源节点

到目的节点

经过的路径p。in,

In the space-time graph G, from t=0 to t=T source node

to the destination node

The path p traversed.

(4)不可靠性(4) Unreliability

定义各连接的不可靠性概率为u(e)；空间连接在物理层通过连接估计技术得到各连接的不可靠概率如式(15)；对于每个时间连接，u(e)表示存储数据错误的概率，假设所有时间连接都是完全可靠的，即u(e)＝0；Define the unreliability probability of each connection as u(e); the spatial connection obtains the unreliability probability of each connection through the connection estimation technology in the physical layer as formula (15); for each time connection, u(e) represents the storage data error The probability of , assuming that all time connections are completely reliable, ie u(e)=0;

进一步的，所述步骤104，在满足网络连通性和可靠性约束的模型下，以最小成本、最大能效、最小成本效率比为目标，引入剪枝和贪婪算法设计基于加权时空图的连接计划，具体步骤如下：Further, in step 104, under a model that satisfies network connectivity and reliability constraints, aiming at minimum cost, maximum energy efficiency, and minimum cost-effectiveness ratio, introduce pruning and greedy algorithms to design a connection plan based on a weighted space-time graph, Specific steps are as follows:

以最小成本/最大能效/最小成本效率为目标，在满足连通性和可靠性的约束性下，通过贪婪算法构造基于加权时空图的连接计划；最小成本/最大能效/最小成本效率算法思想是在时空图G^t＝(V^t,E^t)中，搜寻每对节点

找出所有具有最小成本/最大能效/最小成本效率的可靠连接，将其列入连接计划；要求该路径的不可靠性要低于所设定的临界值β，因此将其标识为

为了找到从节点

到

的可靠路径；路径从源节点到目标节点，每次构造一个节点；部分构造路径头部的任何节点都可以选择添加两个可供选择的输出连接中的一个，

有两个选择

和

当添加的下一个连接

其路径可靠性满足

则

被选择；然后将选中的节点作为当前部分构造路径的头部，继续选择下一个节点；通过这些选择，最终构建了从

到

的路径；当全局的节点都被选择，且网络拓扑中任意节点对之间具有连接，则表示得到的最终连接计划。With the goal of minimum cost/maximum energy efficiency/minimum cost efficiency, under the constraints of connectivity and reliability, a greedy algorithm is used to construct a connection plan based on weighted space-time graph; the idea of minimum cost/maximum energy efficiency/minimum cost efficiency algorithm is in In the space-time graph G^t =(V^t ,E^t ), search for each pair of nodes

Find all reliable connections with minimum cost/maximum energy efficiency/minimum cost efficiency, and include them in the connection plan; the unreliability of this path is required to be lower than the set critical value β, so it is marked as

In order to find slave nodes

arrive

A reliable path for ; a path is constructed one node at a time from a source node to a target node; any node at the head of a partially constructed path can choose to add one of two alternative output connections,

there are two options

and

When adding the next connection

Its path reliability satisfies

but

is selected; then use the selected node as the head of the current part of the construction path, and continue to select the next node; through these selections, the final construction from

arrive

The path of ; when the global nodes are all selected, and there is a connection between any pair of nodes in the network topology, it represents the final connection plan obtained.

进一步的，所述贪婪算法包括(1)将优化目标以及相关约束建立数学模型； (2)把设计网络中所有节点对之间的连接计划问题划分为求一对节点连接计划的子问题；(3)对每个子问题分别求解，并将该对节点标注已解决，得到每个子问题的局部最优解；(4)直到所有节点都被标注，把子问题的局部最优解合成为初始问题的一个解。Further, the greedy algorithm includes (1) establishing a mathematical model with optimization objectives and related constraints; (2) dividing the connection planning problem between all pairs of nodes in the design network into sub-problems of seeking a pair of node connection plans; ( 3) Solve each sub-problem separately, and mark the pair of nodes as solved to obtain the local optimal solution of each sub-problem; (4) until all nodes are marked, synthesize the local optimal solution of the sub-problems into the initial problem a solution of .

进一步的，得到的连接计划能够满足以下目标：(1)根据全连通的时空图G 分别构造最小成本、最大能效、最小成本效率比的三个子图G_s；(2)G_s仍然是连通的；(3)G_s的不可靠度是小于所设定的下界β。Further, the obtained connection plan can meet the following objectives: (1) According to the fully connected space-time graph G, three subgraphs G_s with minimum cost, maximum energy efficiency, and minimum cost-effectiveness ratio are respectively constructed; (2) G_s is still connected ; (3) The unreliability of G_s is less than the set lower bound β.

本发明的优点及有益效果如下：Advantage of the present invention and beneficial effect are as follows:

本发明方案通过深度优先搜索得到网络的初始拓扑，分析静止轨道卫星的覆盖区域以及不同轨道卫星之间的物理可见性，利用剪枝排除无效或者不满足条件的连接，对初始拓扑进行优化。优化后的网络拓扑被划分为多个快照，每个快照内的拓扑结构是固定不变的，将多个快照序列转换为加权时空图。通过加权时空图获得时间和空间连接权重的同时捕捉每个空间节点的时间和空间信息的关联性。加权时空图中每个连接的权重由成本、能效和不可靠性构成，其中根据传输数据所消耗的能源量化连接成本，根据连接容量和数据流量定义连接能效，根据物理层技术评估连接不可靠性。在满足网络连通性和可靠性约束的模型下，以最小成本、最大能效、最小成本效率比为目标，引入贪婪算法设计基于加权时空图的连接计划，通过连接计划优化网络冗余连接的同时提升了网络资源利用率。The solution of the present invention obtains the initial topology of the network through depth-first search, analyzes the coverage area of geostationary orbit satellites and the physical visibility between satellites in different orbits, and uses pruning to eliminate invalid or unsatisfactory connections to optimize the initial topology. The optimized network topology is divided into multiple snapshots, the topology within each snapshot is fixed, and the sequence of multiple snapshots is converted into a weighted spatiotemporal graph. The temporal and spatial connection weights are obtained through the weighted spatiotemporal graph while capturing the correlation of temporal and spatial information of each spatial node. The weight of each connection in the weighted space-time graph consists of cost, energy efficiency and unreliability, where the cost of the connection is quantified according to the energy consumed to transmit data, the energy efficiency of the connection is defined according to the connection capacity and data flow, and the connection unreliability is evaluated according to the physical layer technology . Under the model that satisfies the constraints of network connectivity and reliability, with the goal of minimum cost, maximum energy efficiency, and minimum cost-effectiveness ratio, a greedy algorithm is introduced to design a connection plan based on a weighted space-time graph, and the network redundancy connection is optimized through the connection plan. Simultaneously improve network resource utilization.

附图说明Description of drawings

图1是本发明提供优选实施例基于最小成本效率比加权时空图的双层卫星网络连接计划设计方法工作流程图；Fig. 1 is the working flow diagram of the double-layer satellite network connection plan design method based on the minimum cost-effectiveness ratio weighted space-time graph according to the preferred embodiment of the present invention;

图2为GEO卫星覆盖LEO层的模型；Figure 2 is a model of the GEO satellite covering the LEO layer;

图3为卫星的物理可见性模型；Figure 3 is the physical visibility model of the satellite;

图4为只有两个单独节点的简单加权时空图以及通过连接计划设计得到的稀疏子图。Figure 4 shows a simple weighted spatiotemporal graph with only two individual nodes and a sparse subgraph designed by a connection plan.

具体实施方式Detailed ways

下面将结合本发明实施例中的附图，对本发明实施例中的技术方案进行清楚、详细地描述。所描述的实施例仅仅是本发明的一部分实施例。The technical solutions in the embodiments of the present invention will be described clearly and in detail below with reference to the drawings in the embodiments of the present invention. The described embodiments are only some of the embodiments of the invention.

本发明解决上述技术问题的技术方案是：The technical scheme that the present invention solves the problems of the technologies described above is:

本发明内容所涉及的概念和模型如下：The concepts and models involved in the content of the present invention are as follows:

1、网络模型1. Network model

本方法以4颗GEO卫星(3颗在轨，1颗作为备用卫星)和72颗LEO卫星 (66颗在平均分布在6个轨道，每个轨道留有1颗作为备用卫星)。根据LEO 卫星的运动周期为T，并且将该周期划分为离散等间隔的时间段{1,2,…,T}。假设GEO/LEO双层卫星网络模型为G^t＝(V^t,E^t)，其中V^t和E^t分别表示在t时刻的空间节点和空间连接。This method uses 4 GEO satellites (3 in orbit, 1 as a backup satellite) and 72 LEO satellites (66 are evenly distributed in 6 orbits, and 1 satellite is reserved in each orbit as a backup satellite). According to the motion period of the LEO satellite is T, and this period is divided into discrete and equally spaced time periods {1,2,...,T}. Assume that the GEO/LEO two-tier satellite network model is G^t = (V^t , E^t ), where V^t and E^t represent the spatial nodes and spatial connections at time t, respectively.

2、最小成本连接计划设计2. Minimum cost connection plan design

加权时空图中的连接的权重为(c(e),ε(e),u(e))。如附图4(a)简单例子所示， 空间连接

的成本开销为5，能效为2，不可靠度为0.4，时间连接

的成本 开销为4，能效为1，不可靠度为0。路径

的成本效率比 为2.75/2.67。首先，通过剪枝算法滤除不满足条件的连接，得到如图4(a)所示的 连接，该拓扑的总成本为38，通过贪婪算法搜寻拓扑中满足需求的连接，并将 其放入连接计划。通过不同的连接计划可以得到如附图4(b)-4(d)所示的不同子图 (加粗线)，虽然这些子图比较稀疏，但随着时间的推移仍然是连接的。每个节 点都可以找到通往任何其他节点的时空路径。显然附图4(c)具有最小的总成本， 子图的不可靠性为0.4与完整拓扑相同。因此生成图4(c)的连接计划是所需要的 最小成本可靠路径连接计划，以此得到的连接计划可以实现全局拓扑的最小成本。此外，最大能效、最小成本效率比可靠路径连接计划设计的具体过程与最 小成本连接计划设计一致。The weights of the connections in the weighted space-time graph are (c(e), ε(e), u(e)). As shown in the simple example in Figure 4(a), the spatial connection

The cost overhead is 5, the energy efficiency is 2, the unreliability is 0.4, and the time connection

The cost overhead is 4, the energy efficiency is 1, and the unreliability is 0. path

The cost-effectiveness ratio is 2.75/2.67. First, the connections that do not meet the conditions are filtered out through the pruning algorithm, and the connections shown in Figure 4(a) are obtained. The total cost of the topology is 38. The connections that meet the requirements in the topology are searched through the greedy algorithm, and put into Connection plan. Different subgraphs (bold lines) as shown in Fig. 4(b)-4(d) can be obtained through different connection schemes, although these subgraphs are relatively sparse, they are still connected over time. Every node can find a space-time path to any other node. It is clear that Fig. 4(c) has the smallest total cost, and the unreliability of the subgraph is 0.4 which is the same as the full topology. Therefore, the connection plan generated in Figure 4(c) is the required minimum-cost reliable path connection plan, and the connection plan obtained from this can achieve the minimum cost of the global topology. In addition, the specific process of the design of the maximum energy efficiency and minimum cost-effectiveness ratio reliable path connection plan is consistent with the design of the minimum cost connection plan.

本发明解决上述技术问题的技术方案是：The technical scheme that the present invention solves the problems of the technologies described above is:

本发明解决上述技术问题的技术方案是：一种基于加权时空图的双层卫星网络连接计划设计方法。采取基于成本、能效和成本效率比的加权时空图使动态时变的卫星网络静态离散化从而捕捉到每个时隙的固定网络拓扑结构。通过剪枝算法得到滤除不满足基本的连接约束条件的空间连接。通过卫星网络的资源来表征时空图的时间和空间连接的权重，根据传输数据所消耗的能源量化连接成本，根据连接容量和数据流量定义连接能效，根据物理层技术评估连接不可靠性。在满足网络连通性和可靠性约束的模型下，以最小成本、最大能效、最小成本效率比为目标，通过贪婪算法设计基于加权时空图的连接计划，实现合理规划网络中的潜在连接的同时提升网络资源利用率。具体步骤如下：The technical solution of the present invention to solve the above-mentioned technical problems is: a method for designing a double-layer satellite network connection plan based on a weighted space-time diagram. A weighted space-time graph based on cost, energy efficiency and cost-effectiveness ratio is used to statically discretize the dynamic time-varying satellite network to capture the fixed network topology of each time slot. The spatial connections that do not meet the basic connection constraints are filtered out through the pruning algorithm. The weight of the time and space connections of the space-time diagram is represented by the resources of the satellite network, the connection cost is quantified according to the energy consumed by the transmitted data, the connection energy efficiency is defined according to the connection capacity and data flow, and the connection unreliability is evaluated according to the physical layer technology. Under the model that satisfies the constraints of network connectivity and reliability, aiming at the minimum cost, maximum energy efficiency, and minimum cost-effectiveness ratio, the connection plan based on the weighted space-time graph is designed through a greedy algorithm, and the potential connections in the network can be rationally planned and improved at the same time. Network resource utilization. Specific steps are as follows:

第一步：通过计算LEO层GEO覆盖区域的半边中心角λ以及GEO星下点与LEO卫星的地心夹角∠A'OB，分析GLL空间连接存在的基本约束条件。Step 1: By calculating the central angle λ of the half side of the GEO coverage area of the LEO layer and the angle ∠A'OB between the GEO sub-satellite point and the LEO satellite, the basic constraints of the GLL spatial connection are analyzed.

足当一颗LEO卫星同时位于2-3个GEO卫星的覆盖区域内，则LEO选择距离最近的GEO作为建立连接，归属于该GEO的覆盖范围内的成员。When a LEO satellite is located within the coverage area of 2-3 GEO satellites at the same time, the LEO selects the nearest GEO as the connection establishment and belongs to the members within the coverage area of the GEO.

第二步：判断不同轨道卫星之间的物理可见性，约束网络中存在的空间连接。Step 2: Judging the physical visibility between satellites in different orbits and constraining the spatial connections that exist in the network.

h_i,j≥R+H (2)h_i,j ≥ R+H (2)

其中，h_i,j为卫星S_i和卫星S_j之间的连接与地心角的垂直高度，当h_i,j大于地球半径R时，卫星S_i和卫星S_j是物理可见的，即表示此时卫星S_i和S_j可建立空间连接。由于地球上空大气层信号的衰减及干扰，卫星之间的连接受到大气层的影响。在判断空间连接是否可建立时，不仅要依据建立空间连接的物理可见性临界条件，同时要考虑保护余隙H，以此减小大气层影响造成的误差。Among them, h_i,j is the vertical height between the connection between satellite S_i and satellite S_j and the center of the earth, when h_i,j is greater than the radius R of the earth, satellite S_i and satellite S_j are physically visible, that is Indicates that satellites S_i and S_j can establish space connection at this time. Due to the attenuation and interference of atmospheric signals above the earth, the connection between satellites is affected by the atmosphere. When judging whether a space connection can be established, it is not only based on the critical condition of physical visibility for establishing a space connection, but also the protection clearance H should be considered, so as to reduce the error caused by the influence of the atmosphere.

第三步：通过深度优先搜索和剪枝灵活设计并优化相应的搜索规则，通过剪枝以排除无效或不满足的条件的连接，从而对DFS得到的初始拓扑进行优化。The third step: flexibly design and optimize the corresponding search rules through depth-first search and pruning, and optimize the initial topology obtained by DFS by pruning to exclude invalid or unsatisfied connections.

第四步：将LEO卫星的运行周期T划分为离散且等时隙的时间段 {T₁,T₂,…,T_n}，将动态卫星网络建模为一系列有向图{G^t|t＝1,2,…,T}的合集。Step 4: Divide the operating period T of the LEO satellite into discrete and equal time slots {T₁ ,T₂ ,…,T_n }, and model the dynamic satellite network as a series of directed graphs {G^t | The set of t=1,2,...,T}.

第五步：将快照序列{G^t|t＝1,2,…,T}转换为加权时空图，在相邻的层间添加时间和空间连接。Step 5: Convert the sequence of snapshots {G^t |t=1,2,…,T} into a weighted spatiotemporal graph, adding temporal and spatial connections between adjacent layers.

第六步：通过卫星网络的资源来表征时空图的时间和空间连接的权重，根据传输数据所消耗的能源量化连接成本，根据连接容量和数据流量定义连接能效，根据物理层技术评估连接不可靠性。Step 6: Use the resources of the satellite network to characterize the time and space connection weights of the space-time diagram, quantify the connection cost according to the energy consumed to transmit data, define the connection energy efficiency according to the connection capacity and data flow, and evaluate the connection unreliability according to the physical layer technology sex.

第七步：在满足网络连通性和可靠性约束的模型下，以最小成本、最大能效、最小成本效率比为目标，通过贪婪算法设计基于加权时空图的连接计划，实现合理规划网络中的潜在连接的同时提升网络资源利用率。Step 7: Under the model that satisfies the constraints of network connectivity and reliability, with the goal of minimum cost, maximum energy efficiency, and minimum cost-effectiveness ratio, design a connection plan based on a weighted space-time graph through a greedy algorithm to achieve a reasonable planning of potential in the network. Improve network resource utilization while connecting.

上述实施例阐明的系统、装置、模块或单元，具体可以由计算机芯片或实体实现，或者由具有某种功能的产品来实现。一种典型的实现设备为计算机。具体的，计算机例如可以为个人计算机、膝上型计算机、蜂窝电话、相机电话、智能电话、个人数字助理、媒体播放器、导航设备、电子邮件设备、游戏控制台、平板计算机、可穿戴设备或者这些设备中的任何设备的组合。The systems, devices, modules, or units described in the above embodiments can be specifically implemented by computer chips or entities, or by products with certain functions. A typical implementing device is a computer. Specifically, the computer may be, for example, a personal computer, a laptop computer, a cellular phone, a camera phone, a smart phone, a personal digital assistant, a media player, a navigation device, an email device, a game console, a tablet computer, a wearable device, or Combinations of any of these devices.

还需要说明的是，术语“包括”、“包含”或者其任何其他变体意在涵盖非排他性的包含，从而使得包括一系列要素的过程、方法、商品或者设备不仅包括那些要素，而且还包括没有明确列出的其他要素，或者是还包括为这种过程、方法、商品或者设备所固有的要素。在没有更多限制的情况下，由语句“包括一个……”限定的要素，并不排除在包括所述要素的过程、方法、商品或者设备中还存在另外的相同要素。It should also be noted that the term "comprises", "comprises" or any other variation thereof is intended to cover a non-exclusive inclusion such that a process, method, article, or apparatus comprising a set of elements includes not only those elements, but also includes Other elements not expressly listed, or elements inherent in the process, method, commodity, or apparatus are also included. Without further limitations, an element defined by the phrase "comprising a ..." does not exclude the presence of additional identical elements in the process, method, article or apparatus comprising said element.

以上这些实施例应理解为仅用于说明本发明而不用于限制本发明的保护范围。在阅读了本发明的记载的内容之后，技术人员可以对本发明作各种改动或修改，这些等效变化和修饰同样落入本发明权利要求所限定的范围。The above embodiments should be understood as only for illustrating the present invention but not for limiting the protection scope of the present invention. After reading the contents of the present invention, skilled persons can make various changes or modifications to the present invention, and these equivalent changes and modifications also fall within the scope defined by the claims of the present invention.

Claims (10)

1. A double-layer satellite network connection plan design method based on a weighted space-time diagram is characterized by comprising the following steps:

101, searching various types of connections existing in a network under DFS and pruning traversal correlation constraints based on depth first by analyzing the coverage area of a geostationary orbit GEO satellite and the physical visibility among different orbit satellites, and finding a path existing between any two satellite nodes;

102, under the basic constraint condition of space connection establishment, designing a weighted space-time diagram modeling dynamic network by considering the weight of connection in space according to the periodic motion of a low-orbit LEO satellite and the dynamic change relationship between a network topological structure and relative positions among nodes;

step 103, taking cost, energy efficiency and unreliability as weights for comprehensive consideration of connection in the space-time diagram, quantizing connection cost according to energy consumed by data transmission, defining connection energy efficiency according to connection capacity and data flow, and evaluating the unreliability of connection according to a physical layer technology to obtain the weight of each time and space connection in the space-time diagram;

and step 104, introducing a greedy algorithm to design a connection plan based on a weighted space-time diagram under the condition of meeting network connectivity and reliability constraints and with the minimum cost, the maximum energy efficiency and the minimum cost-efficiency ratio as targets.

2. The method according to claim 1, wherein the step 101 finds paths existing between any two satellite nodes based on various types of connections existing in the network under the constraints of DFS and pruning traversal by analyzing coverage areas of GEO satellites and physical visibility between satellites in different orbits, and specifically comprises the following steps:

(1) Dividing a GEO satellite coverage area;

calculating a half-edge central angle lambda of a GEO footprint area of the LEO layer and an included angle & lt A' OB between a GEO satellite lower point and an LEO, wherein the half-edge central angle lambda of a GEO coverage area of the LEO layer is expressed by a formula (1):

wherein R is the radius of the earth, h_G、h_LOrbital altitude, ε, of GEO and LEO satellites respectively_minIs the minimum elevation angle between the LEO and GEO satellites;

the included angle between the lower point of the GEO star and the geocentric of the LEO is represented by the formula (2):

wherein, | A' B | refers to the distance between the lower point of the GEO satellite at the LEO layer and the LEO;

when the LEO satellite meets the condition (3) that the included angle between the lower point of the GEO satellite and the geocenter of the LEO is smaller than the half-edge central angle, the LEO is positioned in the coverage range of the GEO;

∠A'OB≤λ (3)

(2) Judging the physical visibility of the satellite;

known satellite S_iAnd satellite S_jRespectively are

Then the centroid angle θ formed by the two satellites and the ground can be calculated by equation (4):

knowing the earth center angle theta, calculating the satellite node pair (S) by the formulas (5) - (7)_i,S_j) A distance L between_i,jAnd respective elevation angle delta_iAnd delta_j：

Wherein R is_iAnd R_jAre respectively a satellite S_iAnd satellite S_jThe radius of the track of (a);

calculating the instantaneous satellite S by the derivation_iAnd satellite S_jThe vertical height h of the connection between the two and the center of the earth angle_i,j：

h_i,j＝R_icos(δ_i)＝R_jcos(δ_j) (8)。

3. The method for designing a two-tier satellite network connection plan based on weighted space-time diagrams according to claim 2, wherein in the step (1) of dividing GEO coverage areas, LEO may be located within the coverage range of 2-3 GEO satellites at any time, and in order to avoid the repetitive connection of each GEO satellite to one LEO satellite, the following constraints are imposed on the LEO satellites: when one LEO satellite is simultaneously located in the footprint area of 2-3 GEO satellites, the LEO selects the GEO with the closest distance and belongs to the coverage range of the GEO.

4. The design method of the weighted space-time diagram-based two-layer satellite network connection plan according to claim 2, wherein in the step (2), the physical visibility of the satellite is determined by:

satellite visibility at different orbital altitudes is determined by the vertical height h of the instantaneous spatial connection between pairs of satellite nodes and the earth's center angle_i,jDetermining; when h is_i,jGreater than the earth radius R, satellite S_iAnd satellite S_jIs physically visible, i.e. represents the satellite S at that time_iAnd S_jA connection may be established; because of attenuation and interference of atmospheric signals on the earth, the connection between satellites is influenced by the atmosphere, and when judging whether the space connection can be established, the connection is not only established according to the critical condition of physical visibility for establishing the space connectionWhile taking into account the protection clearance H, to reduce the errors due to atmospheric effects, therefore, if and only if equation (9) is satisfied, a spatial connection can be established between satellites in different orbital planes:

h_i,j≥R+H (9)

in a two-layer satellite network, the distances of the satellites in the same orbit are uniformly distributed and have the same running speed, so that the change of the relative positions of the satellites in the same orbit is negligible, and the spatial connection can be stable and continuous all the time.

5. The method of claim 2, wherein the depth-first search and pruning comprises (1) for newly discovered satellite nodes S_vAccessing the node; (2) If S is_vIf there is a connection which is not detected, traversing the connection and taking the adjacent node as the next starting point; (3) Using adjacent nodes as vertexes, and continuing to detect along the connection until the searching of the node S is completed_vAll connections of (c); (4) Repeating the traversal process until all nodes and communication paths in the network are accessed, and finally searching the initial topology of the network; (5) The initial topology is used as input, corresponding search rules are flexibly designed and optimized according to relevant constraint conditions of various types of connection, and connection with invalid or unsatisfied conditions is eliminated through pruning, so that the initial topology obtained by DFS is optimized.

6. The method according to claim 1, wherein the step 102 of designing the weighted space-time diagram-based two-layer satellite network connection plan takes into account the weights of connections in space to design the weighted space-time diagram modeling dynamic network according to the periodic motion of the LEO satellite and the dynamic variation relationship between the network topology and the relative positions of the nodes under the basic constraint condition of the establishment of the basic spatial connection, and specifically includes the following steps:

(1) Dividing the dynamic network into a plurality of snapshot time slots according to the period of the LEO satellite;

suppose the period of motion of a low earth orbit satellite is T and the period is divided into discrete equally spaced time segments { T }₁,T₂,…,T_n}, set G^t＝(V^t,E^t) Is a snapshot of a directed graph representing the network in time slot t, the network topology is fixed in each snapshot, and the dynamic network is modeled as a series of snapshot sets { G }^t|t＝1,2,…,T}；

(2) Converting the snapshot sequence into a weighted space-time diagram;

will snapshot sequence G^tL T =1,2, \8230 |, T } is converted into a weighted space-time diagram, spatial and temporal connections are added between adjacent layers, spatial connections

Finger node v_iAnd node v_jThe presence of a connection in a t-slot, meaning that node v is in the t-slot_iTo another node v_jTransmitting information, time-connecting

Finger connecting the same node v_iIndicating that information is stored during a time slot t, the set of connections in the space-time diagram being

By defining a weighted space-time diagram, the weight of each spatial connection in the network can be obtained and the topological change in the time-varying network can be captured.

7. The method according to claim 6, wherein the connection weight in the space-time diagram of step 103 comprehensively considers cost, energy efficiency and unreliability, the connection cost is quantified according to the energy consumed by data transmission, the connection energy efficiency is defined according to connection capacity and data traffic, and the unreliability of connection is evaluated according to the physical layer technique to obtain the weight of each time and space connection in the space-time diagram, and the method specifically comprises the following steps:

(1) Cost of

For a spatial connection, the cost is the energy consumption of the connection to transfer data, as shown in equation (10), representing the equivalent power consumption of transferring data over the connection, and for a temporal connection, the cost corresponds to the energy consumption of storing data, as shown in equation (11):

wherein P is_wFor constant transmission power, P, of the spatial connection_sFor a constant transmission power of the time connection,

in order to connect the actual amount of data transferred,

is the maximum amount of data that can be transmitted;

(2) Energy efficiency

For spatial connectivity, the correlation of energy efficiency with transmitted data is represented by equation (12); for temporal connectivity, energy efficiency is associated with the remaining storage space as represented by equation (13);

wherein,

in order to be able to connect with the capacity,

the maximum amount of data that can be transmitted.

(3) Cost to efficiency ratio

The cost-efficiency ratio of a connection is represented by phi (e) = c (e)/epsilon (e), a space-time diagram G^t＝(V^t,E^t) Cost-efficiency ratio of phi (G)^t) Is the average of all connections cost-efficiency ratio, i.e.

mean represents the mean, a path

The cost-efficiency ratio of (a) is an average of the cost-efficiency ratios of all connections on the path, and is represented by equation (14):

wherein,

represented in the space-time diagram G from the time T =0 to the source node T = T

To the destination node

A path p traversed;

(4) Unreliability of

Defining the probability of unreliability of each connection as u (e); the spatial connection obtains the unreliable probability of each connection as the formula (15) through the connection estimation technology at the physical layer; for each time connection, u (e) represents the probability of a storage data error, assuming that all time connections are completely reliable, i.e. u (e) =0;

8. the method according to claim 7, wherein in step 104, a greedy algorithm is introduced to design the weighted space-time diagram-based connection plan with the goals of minimum cost, maximum energy efficiency and minimum cost-efficiency ratio under a model satisfying network connectivity and reliability constraints, and the specific steps are as follows:

modeling a dynamic network into a weighted space-time diagram according to the period of an LEO satellite, and constructing a connection plan based on the weighted space-time diagram through a greedy algorithm by taking minimum cost/maximum energy efficiency/minimum cost efficiency as a target under the condition of meeting the constraints of connectivity and reliability; the algorithm idea of least cost/most energy efficiency/least cost efficiency is in the space-time diagram G^t＝(V^t,E^t) In searching each pair of nodes

Finding out all reliable connections with minimum cost/maximum energy efficiency/minimum cost efficiency, and listing the reliable connections into a connection plan; the unreliability of this path is required to be below a set threshold value beta and is therefore identified as

To find a slave node

To

The reliable path of (2); constructing a node each time a path is from a source node to a target node; any node that partially constructs the path header may choose to add one of two alternative output connections,

has two options

And

when the next connection is added

The path reliability of which is satisfied

Then the

Is selected; then, taking the selected node as the head of the current part construction path, and continuously selecting the next node; through these choices, a slave is finally constructed

To

A path of (a); when the nodes of the global are all selected and any node pair in the network topology has connection, the final connection plan is obtained.

9. The method of claim 8, wherein the greedy algorithm comprises (1) modeling optimization objectives and associated constraints as mathematical models; (2) Dividing the problem of a connection plan between all node pairs in a design network into sub-problems for solving a pair of node connection plans; (3) Solving each subproblem respectively, and marking the pair of nodes with solved problems to obtain a local optimal solution of each subproblem; (4) Until all nodes are labeled, the locally optimal solution of the sub-problem is synthesized into a solution of the initial problem.

10. The method for designing a connection plan of a two-layer satellite network based on a weighted space-time diagram according to claim 9, wherein the obtained connection plan can satisfy the following objectives: (1) Respectively constructing three subgraphs G with minimum cost, maximum energy efficiency and minimum cost-to-efficiency ratio according to the fully-communicated space-time diagram G_s；(2)G_sAre still connected; (3) G_sIs less than a set lower bound beta.

Images