1.本发明属于无线通信技术领域，涉及一种基于加权时空图的双层卫星网络连接计划设计方法。
背景技术：2.随着空间技术的快速发展和国家战略进程的不断推进，卫星网络在处理空间信息的传输、获取和分发中起着极其重要的作用，是未来完备空天地一体化网络的重要组成部分。卫星网络以广阔的覆盖范围、充足的网络资源，灵活的部署条件等特征，作为地面网络强有力的补充，被广泛应用于许多领域，如深空探测、地球观测、海域通信、应急通信和定位导航等。我国“十四五”规划中推进卫星通信系统与地面信息通信系统深度融合，从而初步形成覆盖全球、天地一体的信息网络。因此，将卫星网络的研究作为重要的研究方向。双层卫星网络系统相比于单层卫星网络，节点的移动性差异以及立体的层次结构导致网络中节点建立的连接具有偶发性，使得星间连接和网络拓扑在不断的变化。相比地面网络节点，卫星的运行成本较高且卫星星上资源有限，卫星位于的空间环境复杂因此不能随意更换。
3.连接计划设计是空间网络拓扑结构优化和网络性能提高的关键技术之一。如果把双层卫星网络中所有潜在的接触都配置为全连通的连接计划非常奢侈，庞大的潜在接触使网络中的接触过度冗余，增加了网络的复杂度和节点的计算复杂性。因此，利用剪枝与贪婪算法构造基于加权时空图的连接计划，在满足网络连通性和可靠性约束的条件下，合理规划网络中的可用连接，减少冗余连接的同时提升网络资源利用率。
4.cn109740832a，一种用于增强卫星系统自主导航能力的连接计划设计方法，依据星历计算得到可视矩阵；各卫星节点依据可视矩阵采用公平性连接计划算法计算得到连接计划输出；各节点在时间同步的基础上，分别按照连接计划设计结果在连接计划设计周期起始时刻同时执行链路调度。对于每个链路调度周期，连接计划设计过程均在星上完成而不依赖于地面站：1)卫星网络中各卫星节点通过与其他卫星节点进行信息交互，获取统一的全网最新星历，并依据星历计算得到可视矩阵，即连接计划设计的输入；2)卫星网络中各节点对确定的连接计划设计周期，对输入采用确定性的连接计划设计算法，在星上计算得到相同的连接计划设计输出；3)卫星网络中各卫星节点在时间同步的基础上，分别按照连接计划设计结果在连接计划设计周期起始时刻同时执行链路调度。
5.该专利根据星历计算得到可视矩阵，将可视矩阵作为连接计划设计的输入。确定连接计划设计的周期并划分每个周期的时隙，在每个时隙开始时刻输入可视矩阵。将可视矩阵转换为图模型，将所有连接的权重都设置为无穷大。对当前时隙的进行完全图最大权非完美匹配，当连接被匹配则将权重设定为0，通过匹配得到连接计划。本发明，对网络中存在的连接进行了基本的约束，引入深度优先搜索和剪枝排除无效或不满足的条件的连接，搜索到基本优化后的网络拓扑，以此减少了后续连接计划设计的复杂性。按照低轨卫星周期划分为多个时隙，通过加权时空图表征每个时隙中的网络拓扑时间连接和空间连接变化的关系。在设计连接计划时考虑了连接的权重，所有连接的权重综合考虑成本、能效以及不
可靠性，而不是单单的设定为一个固定值。引入贪婪算法，分别以最小成本、最大能效、最小成本效率比为目标，设计基于加权时空图的连接计划。
技术实现要素：6.本发明旨在解决以上现有技术的问题。提出了一种基于加权时空图的双层卫星网络连接计划设计方法。本发明的技术方案如下：
7.一种基于加权时空图的双层卫星网络连接计划设计方法，其包括以下步骤：
8.步骤101、根据静止轨道(geostationary earth orbit,geo)卫星的覆盖区域以及不同轨道卫星之间的物理可见性分析网络中存在的各类连接，基于dfs和 pruning遍历相关约束下网络中存在的各类连接，找到任意两个卫星节点之间存在的路径；
9.步骤102、根据低轨(low earth orbit,leo)卫星的周期性运动以及网络拓扑结构和节点间相对位置的动态变化关系，设计加权时空图建模动态网络；
10.步骤103、根据传输数据所消耗的能源量化连接成本，根据连接容量和数据流量定义连接能效，根据物理层技术评估连接不可靠性，得到时空图中每个时间和空间连接的权重；
11.步骤104、在满足网络连通性和可靠性约束的模型下，以最小成本、最大能效、最小成本效率比为目标，引入剪枝和贪婪算法设计基于加权时空图的连接计划。
12.进一步的，所述通过步骤101，根据静止轨道卫星的覆盖区域以及不同轨道卫星之间的物理可见性分析网络中存在的各类连接，基于dfs和pruning遍历相关约束下网络中存在的各类连接，找到任意两个卫星节点之间存在的路径：
13.(1)geo覆盖区域划分；
14.计算leo层geo足印区域的半边中心角λ以及geo星下点与leo的地心夹角∠a'ob，leo层geo覆盖区域的半边中心角λ表示式(1)：
[0015][0016]
其中，r为地球半径，hg、h
l
分别为geo和leo卫星的轨道高度，ε
min
为leo 与geo卫星之间的最小仰角；
[0017]
geo星下点与leo的地心夹角通过式(2)表示：
[0018][0019]
其中，|a'b|指geo卫星位于leo层的星下点与leo的间距；
[0020]
当leo卫星满足geo星下点与该leo的地心夹角小于半边中心角的条件(3)，则表示该leo位于geo覆盖范围；
[0021]
∠a'ob≤λ
ꢀꢀꢀ
(3)
[0022]
(2)卫星的物理可见性判断；
[0023]
已知卫星si和卫星sj的地理位置坐标分别为则两卫星与地面形成的地心夹角θ可通过式(4)计算得到：
[0024][0025]
已知地心夹角θ，通过式(5)-(7)计算出卫星节点对(si,sj)之间的间距l
i,j
以及各自的仰角δi和δj：
[0026][0027][0028][0029]
其中，ri和rj分别为卫星si和卫星sj的轨道半径；
[0030]
通过上述推导计算瞬时卫星si和卫星sj之间的连接与地心角的垂直高度h
i,j
：
[0031]hi,j
＝ricos(δi)＝rjcos(δj)
ꢀꢀꢀ
(8)
[0032]
进一步的，所述(1)geo覆盖区域划分步骤中，在任意时刻，leo可能同时位于2-3颗geo卫星的覆盖范围内，为了避免每个geo重复连接到一颗 leo卫星，对leo卫星有以下限制条件：当一颗leo卫星同时位于2-3个geo 卫星的足印区域内，则leo选择距离最近的geo，归属于该geo的覆盖范围内。
[0033]
进一步的，所述步骤(2)卫星的物理可见性判断步骤中：
[0034]
不同轨道高度的卫星可见性由卫星节点对之间的瞬时空间连接与地心角的垂直高度h
i,j
决定；当h
i,j
大于地球半径r时，卫星si和卫星sj是物理可见的，即表示此时卫星si和sj可建立连接；由于地球上空大气层信号的衰减及干扰，卫星之间的连接受到大气层的影响，在判断空间连接是否可建立时，不仅要依据建立空间连接的物理可见性临界条件，同时要考虑保护余隙h，以此减小大气层影响造成的误差，因此，当且仅当满足式(9)，不同轨道平面的卫星之间才可以建立空间连接：
[0035]hi,j
≥r+h
ꢀꢀꢀ
(9)
[0036]
在双层卫星网络中，在同一轨道内卫星的距离是均匀分布的且具有相同的运行速度，因此，在同一轨道内卫星之间相对位置的变化可以忽略，空间连接能够稳定并一直持续。
[0037]
进一步的，所述的深度优先搜索和剪枝包括(1)对于新发现的卫星节点sv，访问该节点；(2)如果sv有一条未被检测的连接，则遍历该连接并将相邻节点作为下一起点；(3)将相邻节点作为顶点，继续沿着这个连接进行检测，直到搜索完节点sv的所有连接；(4)重复遍历的过程，直到网络中所有节点和相通路径都被访问，最终搜索到网络的初始拓扑；(5)将初始拓扑作为输入，根据各类连接的相关约束条件，灵活设计并优化相应的搜索规则，通过剪枝以排除无效或不满足的条件的连接，从而对dfs得到的初始拓扑进行优化。
[0038]
进一步的，所述步骤102根据卫星的周期性运动以及网络拓扑结构和节点间相对位置的动态变化关系，设计加权时空图建模动态网络，具体包括以下步骤：
[0039]
(1)按照leo卫星的周期将动态网络划分为多个快照时隙；
[0040]
假设leo卫星的运动周期为t，并且将该周期划分为离散等间隔的时间段 {t1,t2,
…
,tn}，设g
t
＝(v
t
,e
t
)是一个有向图表示网络在时隙t的快照，在每个快照中网络拓扑是固定不变的，将动态网络建模为一系列快照{g
t
|t＝1,2,
…
,t}的合集；
[0041]
(2)将快照序列转换为加权时空图；
[0042]
将快照序列{g
t
|t＝1,2,
…
,t}转换成加权时空图，在相邻层之间添加空间和时间连接，空间连接指节点vi与节点vj在t时隙中存在的连接，表示在t时隙中节点vi向另一个节点vj传输信息，时间连接指连接同一节点vi，表示在时隙t期间存储信息，时空图中的连接集合为通过定义加权时空图，可以利用有向图捕捉时变网络中的拓扑变化。
[0043]
进一步的，所述步骤103根据传输数据所消耗的能源量化连接成本，根据连接容量和数据流量定义连接能效，根据物理层技术评估连接不可靠性，得到时空图中每个时间和空间连接的权重，具体步骤如下：
[0044]
(1)成本
[0045]
对于空间连接，成本是该连接传递数据的能源消耗如式(10)所示，表示通过连接传输数据的等效功耗，对于时间连接，成本对应于存储数据的能量消耗如式(11)所示：
[0046][0047][0048]
其中，其中pw为空间连接的恒定传输功率，ps为时间连接的恒定传输功率，为连接所传输的实际数据量，为能够传输的最大数据量；
[0049]
(2)能效
[0050]
对于空间连接，能效与传输的数据相关通过式(12)表示；对于时间连接，能效与剩余存储空间相关联由式(13)表示；
[0051][0052][0053]
其中，为连接的容量，为能够传输的最大数据量。
[0054]
(3)成本效率比
[0055]
一个连接的成本效率比由φ(e)＝c(e)/ε(e)表示，一个时空图g
t
＝(v
t
,e
t
)的成本
效率比φ(g
t
)是所有连接成本效率比的平均值，即mean 表示平均值，一条路径的成本效率比为该路径上所有连接成本效率比的平均值通过式(14)表示：
[0056][0057]
其中，表示在时空图g中，从t＝0时刻到t＝t源节点到目的节点经过的路径p。
[0058]
(4)不可靠性
[0059]
定义各连接的不可靠性概率为u(e)；空间连接在物理层通过连接估计技术得到各连接的不可靠概率如式(15)；对于每个时间连接，u(e)表示存储数据错误的概率，假设所有时间连接都是完全可靠的，即u(e)＝0；
[0060][0061]
进一步的，所述步骤104，在满足网络连通性和可靠性约束的模型下，以最小成本、最大能效、最小成本效率比为目标，引入剪枝和贪婪算法设计基于加权时空图的连接计划，具体步骤如下：
[0062]
以最小成本/最大能效/最小成本效率为目标，在满足连通性和可靠性的约束性下，通过贪婪算法构造基于加权时空图的连接计划；最小成本/最大能效/最小成本效率算法思想是在时空图g
t
＝(v
t
,e
t
)中，搜寻每对节点找出所有具有最小成本/最大能效/最小成本效率的可靠连接，将其列入连接计划；要求该路径的不可靠性要低于所设定的临界值β，因此将其标识为为了找到从节点到的可靠路径；路径从源节点到目标节点，每次构造一个节点；部分构造路径头部的任何节点都可以选择添加两个可供选择的输出连接中的一个，有两个选择和当添加的下一个连接其路径可靠性满足则被选择；然后将选中的节点作为当前部分构造路径的头部，继续选择下一个节点；通过这些选择，最终构建了从到的路径；当全局的节点都被选择，且网络拓扑中任意节点对之间具有连接，则表示得到的最终连接计划。
[0063]
进一步的，所述贪婪算法包括(1)将优化目标以及相关约束建立数学模型； (2)把设计网络中所有节点对之间的连接计划问题划分为求一对节点连接计划的子问题；(3)对每个子问题分别求解，并将该对节点标注已解决，得到每个子问题的局部最优解；(4)直到所有节点都被标注，把子问题的局部最优解合成为初始问题的一个解。
[0064]
进一步的，得到的连接计划能够满足以下目标：(1)根据全连通的时空图g 分别构造最小成本、最大能效、最小成本效率比的三个子图gs；(2)gs仍然是连通的；(3)gs的不可靠度是小于所设定的下界β。
[0065]
本发明的优点及有益效果如下：
[0066]
本发明方案通过深度优先搜索得到网络的初始拓扑，分析静止轨道卫星的覆盖区域以及不同轨道卫星之间的物理可见性，利用剪枝排除无效或者不满足条件的连接，对初始拓扑进行优化。优化后的网络拓扑被划分为多个快照，每个快照内的拓扑结构是固定不变的，将多个快照序列转换为加权时空图。通过加权时空图获得时间和空间连接权重的同时捕捉每个空间节点的时间和空间信息的关联性。加权时空图中每个连接的权重由成本、能效和不可靠性构成，其中根据传输数据所消耗的能源量化连接成本，根据连接容量和数据流量定义连接能效，根据物理层技术评估连接不可靠性。在满足网络连通性和可靠性约束的模型下，以最小成本、最大能效、最小成本效率比为目标，引入贪婪算法设计基于加权时空图的连接计划，通过连接计划优化网络冗余连接的同时提升了网络资源利用率。
附图说明
[0067]
图1是本发明提供优选实施例基于最小成本效率比加权时空图的双层卫星网络连接计划设计方法工作流程图；
[0068]
图2为geo卫星覆盖leo层的模型；
[0069]
图3为卫星的物理可见性模型；
[0070]
图4为只有两个单独节点的简单加权时空图以及通过连接计划设计得到的稀疏子图。
具体实施方式
[0071]
下面将结合本发明实施例中的附图，对本发明实施例中的技术方案进行清楚、详细地描述。所描述的实施例仅仅是本发明的一部分实施例。
[0072]
本发明解决上述技术问题的技术方案是：
[0073]
本发明内容所涉及的概念和模型如下：
[0074]
1、网络模型
[0075]
本方法以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时刻的空间节点和空间连接。
[0076]
2、最小成本连接计划设计
[0077]
加权时空图中的连接的权重为(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)的连接计划是
所需要的 最小成本可靠路径连接计划，以此得到的连接计划可以实现全局拓扑的最小成 本。此外，最大能效、最小成本效率比可靠路径连接计划设计的具体过程与最 小成本连接计划设计一致。
[0078]
本发明解决上述技术问题的技术方案是：
[0079]
本发明解决上述技术问题的技术方案是：一种基于加权时空图的双层卫星网络连接计划设计方法。采取基于成本、能效和成本效率比的加权时空图使动态时变的卫星网络静态离散化从而捕捉到每个时隙的固定网络拓扑结构。通过剪枝算法得到滤除不满足基本的连接约束条件的空间连接。通过卫星网络的资源来表征时空图的时间和空间连接的权重，根据传输数据所消耗的能源量化连接成本，根据连接容量和数据流量定义连接能效，根据物理层技术评估连接不可靠性。在满足网络连通性和可靠性约束的模型下，以最小成本、最大能效、最小成本效率比为目标，通过贪婪算法设计基于加权时空图的连接计划，实现合理规划网络中的潜在连接的同时提升网络资源利用率。具体步骤如下：
[0080]
第一步：通过计算leo层geo覆盖区域的半边中心角λ以及geo星下点与leo卫星的地心夹角∠a'ob，分析gll空间连接存在的基本约束条件。
[0081][0082]
足当一颗leo卫星同时位于2-3个geo卫星的覆盖区域内，则leo选择距离最近的geo作为建立连接，归属于该geo的覆盖范围内的成员。
[0083]
第二步：判断不同轨道卫星之间的物理可见性，约束网络中存在的空间连接。
[0084]hi,j
≥r+h
ꢀꢀꢀ
(2)
[0085]
其中，h
i,j
为卫星si和卫星sj之间的连接与地心角的垂直高度，当h
i,j
大于地球半径r时，卫星si和卫星sj是物理可见的，即表示此时卫星si和sj可建立空间连接。由于地球上空大气层信号的衰减及干扰，卫星之间的连接受到大气层的影响。在判断空间连接是否可建立时，不仅要依据建立空间连接的物理可见性临界条件，同时要考虑保护余隙h，以此减小大气层影响造成的误差。
[0086]
第三步：通过深度优先搜索和剪枝灵活设计并优化相应的搜索规则，通过剪枝以排除无效或不满足的条件的连接，从而对dfs得到的初始拓扑进行优化。
[0087]
第四步：将leo卫星的运行周期t划分为离散且等时隙的时间段 {t1,t2,
…
,tn}，将动态卫星网络建模为一系列有向图{g
t
|t＝1,2,
…
,t}的合集。
[0088]
第五步：将快照序列{g
t
|t＝1,2,
…
,t}转换为加权时空图，在相邻的层间添加时间和空间连接。
[0089]
第六步：通过卫星网络的资源来表征时空图的时间和空间连接的权重，根据传输数据所消耗的能源量化连接成本，根据连接容量和数据流量定义连接能效，根据物理层技术评估连接不可靠性。
[0090]
第七步：在满足网络连通性和可靠性约束的模型下，以最小成本、最大能效、最小成本效率比为目标，通过贪婪算法设计基于加权时空图的连接计划，实现合理规划网络中的潜在连接的同时提升网络资源利用率。
[0091]
上述实施例阐明的系统、装置、模块或单元，具体可以由计算机芯片或实体实现，
或者由具有某种功能的产品来实现。一种典型的实现设备为计算机。具体的，计算机例如可以为个人计算机、膝上型计算机、蜂窝电话、相机电话、智能电话、个人数字助理、媒体播放器、导航设备、电子邮件设备、游戏控制台、平板计算机、可穿戴设备或者这些设备中的任何设备的组合。
[0092]
还需要说明的是，术语“包括”、“包含”或者其任何其他变体意在涵盖非排他性的包含，从而使得包括一系列要素的过程、方法、商品或者设备不仅包括那些要素，而且还包括没有明确列出的其他要素，或者是还包括为这种过程、方法、商品或者设备所固有的要素。在没有更多限制的情况下，由语句“包括一个
……”
限定的要素，并不排除在包括所述要素的过程、方法、商品或者设备中还存在另外的相同要素。
[0093]
以上这些实施例应理解为仅用于说明本发明而不用于限制本发明的保护范围。在阅读了本发明的记载的内容之后，技术人员可以对本发明作各种改动或修改，这些等效变化和修饰同样落入本发明权利要求所限定的范围。
技术特征：1.一种基于加权时空图的双层卫星网络连接计划设计方法，其特征在于，包括以下步骤：步骤101、通过分析静止轨道geo卫星的覆盖区域以及不同轨道卫星之间的物理可见性，基于深度优先搜索dfs和剪枝遍历相关约束下网络中存在的各类连接，找到任意两个卫星节点之间存在的路径；步骤102、在空间连接建立的基本约束条件下，根据低轨leo卫星的周期性运动以及网络拓扑结构和节点间相对位置的动态变化关系，考虑空间中连接的权重设计加权时空图建模动态网络；步骤103、时空图中的连接综合考虑以成本、能效和不可靠性为权重，根据传输数据所消耗的能源量化连接成本，根据连接容量和数据流量定义连接能效，根据物理层技术评估连接不可靠性，得到时空图中每个时间和空间连接的权重；步骤104、在满足网络连通性和可靠性约束的模型下，以最小成本、最大能效、最小成本效率比为目标，引入贪婪算法设计基于加权时空图的连接计划。2.根据权利要求1所述的一种基于加权时空图的双层卫星网络连接计划设计方法，其特征在于，所述步骤101通过分析geo卫星的覆盖区域以及不同轨道卫星之间的物理可见性，基于dfs和剪枝遍历相关约束下网络中存在的各类连接，找到任意两个卫星节点之间存在的路径，具体包括以下步骤：(1)geo卫星覆盖区域划分；计算leo层geo足印区域的半边中心角λ以及geo星下点与leo的地心夹角∠a'ob，leo层geo覆盖区域的半边中心角λ表示式(1)：其中，r为地球半径，h
g
、h
l
分别为geo和leo卫星的轨道高度，ε
min
为leo与geo卫星之间的最小仰角；geo星下点与leo的地心夹角通过式(2)表示：其中，|a'b|指geo卫星位于leo层的星下点与leo的间距；当leo卫星满足geo星下点与该leo的地心夹角小于半边中心角的条件(3)，则表示该leo位于geo覆盖范围；∠a'ob≤λ
ꢀꢀꢀꢀꢀꢀꢀꢀꢀ
(3)(2)卫星的物理可见性判断；已知卫星s
i
和卫星s
j
的地理位置坐标分别为则两卫星与地面形成的地心夹角θ可通过式(4)计算得到：已知地心夹角θ，通过式(5)-(7)计算出卫星节点对(s
i
,s
j
)之间的间距l
i,j
以及各自的
仰角δ
i
和δ
j
：：：其中，r
i
和r
j
分别为卫星s
i
和卫星s
j
的轨道半径；通过上述推导计算瞬时卫星s
i
和卫星s
j
之间的连接与地心角的垂直高度h
i,j
：h
i,j
＝r
i
cos(δ
i
)＝r
j
cos(δ
j
)
ꢀꢀꢀꢀꢀꢀꢀꢀꢀꢀꢀꢀꢀꢀꢀꢀꢀ
(8)。3.根据权利要求2所述的一种基于加权时空图的双层卫星网络连接计划设计方法，其特征在于，所述(1)geo覆盖区域划分步骤中，在任意时刻，leo可能同时位于2-3颗geo卫星的覆盖范围内，为了避免每个geo重复连接到一颗leo卫星，对leo卫星有以下限制条件：当一颗leo卫星同时位于2-3个geo卫星的足印区域内，则leo选择距离最近的geo，归属于该geo的覆盖范围内。4.根据权利要求2所述的一种基于加权时空图的双层卫星网络连接计划设计方法，其特征在于，所述步骤(2)卫星的物理可见性判断步骤中：不同轨道高度的卫星可见性由卫星节点对之间的瞬时空间连接与地心角的垂直高度h
i,j
决定；当h
i,j
大于地球半径r时，卫星s
i
和卫星s
j
是物理可见的，即表示此时卫星s
i
和s
j
可建立连接；由于地球上空大气层信号的衰减及干扰，卫星之间的连接受到大气层的影响，在判断空间连接是否可建立时，不仅要依据建立空间连接的物理可见性临界条件，同时要考虑保护余隙h，以此减小大气层影响造成的误差，因此，当且仅当满足式(9)，不同轨道平面的卫星之间才可以建立空间连接：h
i,j
≥r+h
ꢀꢀꢀꢀꢀꢀꢀꢀꢀꢀꢀꢀꢀꢀꢀꢀꢀꢀꢀꢀꢀꢀꢀ
(9)在双层卫星网络中，在同一轨道内卫星的距离是均匀分布的且具有相同的运行速度，因此，在同一轨道内卫星之间相对位置的变化可以忽略，空间连接能够稳定并一直持续。5.根据权利要求2所述的一种基于加权时空图的双层卫星网络连接计划设计方法，其特征在于，所述的深度优先搜索和剪枝包括(1)对于新发现的卫星节点s
v
，访问该节点；(2)如果s
v
有一条未被检测的连接，则遍历该连接并将相邻节点作为下一起点；(3)将相邻节点作为顶点，继续沿着这个连接进行检测，直到搜索完节点s
v
的所有连接；(4)重复遍历的过程，直到网络中所有节点和相通路径都被访问，最终搜索到网络的初始拓扑；(5)将初始拓扑作为输入，根据各类连接的相关约束条件，灵活设计并优化相应的搜索规则，通过剪枝以排除无效或不满足的条件的连接，从而对dfs得到的初始拓扑进行优化。6.根据权利要求1所述的一种基于加权时空图的双层卫星网络连接计划设计方法，其特征在于，所述通过步骤102，在基本空间连接建立的基本约束条件下，根据leo卫星的周期性运动以及网络拓扑结构和节点间相对位置的动态变化关系，考虑空间中连接的权重设计加权时空图建模动态网络，具体包括以下步骤：
(1)按照leo卫星的周期将动态网络划分为多个快照时隙；假设低轨卫星的运动周期为t，并且将该周期划分为离散等间隔的时间段{t1,t2,
…
,t
n
}，设g
t
＝(v
t
,e
t
)是一个有向图表示网络在时隙t的快照，在每个快照中网络拓扑是固定不变的，将动态网络建模为一系列快照集合{g
t
|t＝1,2,
…
,t}；(2)将快照序列转换为加权时空图；将快照序列{g
t
|t＝1,2,
…
,t}转换成加权时空图，在相邻层之间添加空间和时间连接，空间连接指节点v
i
与节点v
j
在t时隙中存在的连接，表示在t时隙中节点v
i
向另一个节点v
j
传输信息，时间连接指连接同一节点v
i
，表示在时隙t期间存储信息，时空图中的连接集合为通过定义加权时空图，可以获得网络中各空间连接的权重以及能够捕捉时变网络中的拓扑变化。7.根据权利要求6所述的一种基于加权时空图的双层卫星网络连接计划设计方法，其特征在于，所述步骤103时空图中的连接权重综合考虑成本、能效以及不可靠性，根据传输数据所消耗的能源量化连接成本，根据连接容量和数据流量定义连接能效，根据物理层技术评估连接不可靠性，得到时空图中每个时间和空间连接的权重，具体步骤如下：(1)成本对于空间连接，成本是该连接传递数据的能源消耗如式(10)所示，表示通过连接传输数据的等效功耗，对于时间连接，成本对应于存储数据的能量消耗如式(11)所示：储数据的能量消耗如式(11)所示：其中，其中p
w
为空间连接的恒定传输功率，p
s
为时间连接的恒定传输功率，为连接所传输的实际数据量，为能够传输的最大数据量；(2)能效对于空间连接，能效与传输的数据相关通过式(12)表示；对于时间连接，能效与剩余存储空间相关联由式(13)表示；储空间相关联由式(13)表示；其中，为连接的容量，为能够传输的最大数据量。
(3)成本效率比一个连接的成本效率比由φ(e)＝c(e)/ε(e)表示，一个时空图g
t
＝(v
t
,e
t
)的成本效率比φ(g
t
)是所有连接成本效率比的平均值，即mean表示平均值，一条路径的成本效率比为该路径上所有连接成本效率比的平均值通过式(14)表示：其中，表示在时空图g中，从t＝0时刻到t＝t源节点到目的节点经过的路径p；(4)不可靠性定义各连接的不可靠性概率为u(e)；空间连接在物理层通过连接估计技术得到各连接的不可靠概率如式(15)；对于每个时间连接，u(e)表示存储数据错误的概率，假设所有时间连接都是完全可靠的，即u(e)＝0；8.根据权利要求7所述的一种基于加权时空图的双层卫星网络连接计划设计方法，其特征在于，所述步骤104，在满足网络连通性和可靠性约束的模型下，以最小成本、最大能效、最小成本效率比为目标，引入贪婪算法设计基于加权时空图的连接计划，具体步骤如下：按照leo卫星的周期将动态网络建模为加权时空图，以最小成本/最大能效/最小成本效率为目标，在满足连通性和可靠性的约束性下，通过贪婪算法构造基于加权时空图的连接计划；最小成本/最大能效/最小成本效率算法思想是在时空图g
t
＝(v
t
,e
t
)中，搜寻每对节点找出所有具有最小成本/最大能效/最小成本效率的可靠连接，将其列入连接计划；要求该路径的不可靠性要低于所设定的临界值β，因此将其标识为为了找到从节点到的可靠路径；路径从源节点到目标节点，每次构造一个节点；部分构造路径头部的任何节点都可以选择添加两个可供选择的输出连接中的一个，有两个选择和当添加的下一个连接其路径可靠性满足则被选择；然后将选中的节点作为当前部分构造路径的头部，继续选择下一个节点；通过这些选择，最终构建了从到的路径；当全局的节点都被选择，且网络拓扑中任意节点对之间具有连接，则表示得到的最终连接计划。9.根据权利要求8所述的一种基于加权时空图的双层卫星网络连接计划设计方法，其特征在于，所述贪婪算法包括(1)将优化目标以及相关约束建立数学模型；(2)把设计网络中所有节点对之间的连接计划问题划分为求一对节点连接计划的子问题；(3)对每个子问题分别求解，并将该对节点标注已解决，得到每个子问题的局部最优解；(4)直到所有节点
都被标注，把子问题的局部最优解合成为初始问题的一个解。10.根据权利要求9所述的一种基于加权时空图的双层卫星网络连接计划设计方法，其特征在于，得到的连接计划能够满足以下目标：(1)根据全连通的时空图g分别构造最小成本、最大能效、最小成本效率比的三个子图g
s
；(2)g
s
仍然是连通的；(3)g
s
的不可靠度是小于所设定的下界β。
技术总结本发明请求保护一种基于加权时空图的双层卫星网络连接计划设计方法，属于无线通信技术领域。该方法面向由低轨和静止卫星构成的双层卫星网络，针对网络拓扑时变、节点资源受限的问题，综合考虑成本、能效和不可靠性，构建加权时空图对动态时变拓扑进行静态离散化处理；根据传输数据所消耗的能源量化连接成本，根据连接容量和数据流量定义连接能效，根据物理层技术评估连接不可靠性，得到时空图中每个时间和空间连接的权重；在满足网络连通性和可靠性约束的模型下，分别以最小成本、最大能效、最小成本效率比为目标，引入剪枝和贪婪算法设计三种基于加权时空图的连接计划。本发明通过连接计划优化网络冗余连接的同时提升了网络资源利用率。利用率。利用率。
技术研发人员：戴翠琴 谢颖 张瑜 秦杰鹏 廖明霞 唐宏
受保护的技术使用者：重庆邮电大学
技术研发日：2022.06.21
技术公布日：2022/11/1
