本发明实施例提供了一种基于星上路由与频谱分配优化方法，首先基于LEO卫星星座模型设计了一种卫星节点位置管理策略，利用该位置管理策略，计算出所需要知道的卫星节点位置坐标，并计算出每颗卫星之间的相对位置与欧几里得距离。之后，提出一种自适应小窗口策略，利用源节点与目的节点的坐标位置信息生成初始小窗口，并根据初始小窗口内的链路负载调整窗口大小，提供给算法合适的收敛面积。最后提出跳数松约束策略，根据卫星节点位置管理策略计算出当前路由节点的邻接节点的相对位置，将邻接节点划分为高优先级节点与低优先级节点，最后提出一种结合上述路由策略的优化算法，在LEO的卫星星座上计算路由并利用首次匹配法分配频谱资源。
1.一种星上路由与频谱分配优化方法，其特征在于，所述星上路由与频谱分配优化方法包括：
第一步：当一个路由业务到来时，根据每个业务的源卫星节点与目的卫星节点的路由器地址，通过卫星节点位置管理策略，计算源节点与目的节点的位置坐标，生成初始矩形小窗口，并统计窗口内所有链路的频谱利用率，根据统计结果调整窗口大小，采用自适应小窗口策略限制算法的收敛面积；
基于LEO卫星网络的卫星节点位置管理策略，实施于LEO卫星星座上，其星座结构符合棋盘式排布；每一个LEO卫星都有一个专属的在星座中的位置坐标，组内所有LEO卫星成员所对应的位置坐标在任何时间点保持相对不变，即任何LEO节点之间的相对位置关系和其本身的坐标是初始确定且不随时间变化而改变的；每一个LEO卫星的位置坐标由在星座中的轨道编号和所在轨道位置确定，其位置管理策略的意义在于计算不同节点之间的位置关系；
利用卫星节点位置管理策略，确定LEO卫星星座内路由业务的源节点和目的节点的位置坐标，采用矩形窗的形式标定小窗内的卫星节点，其矩形窗的对角顶点为LEO源节点与目的节点，在初始小窗口生成后根据窗口内标定的卫星节点的邻接链路负载情况计算自适应小窗口包含节点个数，对窗口尺寸调节，窗口对优化方法的收敛范围收敛，即只允许在窗口内计算路由路径；
在完成小窗口的建立后，计算小窗口包含的行卫星节点数为边长lwx，与列卫星节点数作为边长lwy；之后统计在初始小窗口的频谱利用信息，计算小窗口标记过所有卫星节点的邻接节点频谱占用情况，计算总体的频谱利用率记为SW；它的值是小窗口中所有链路中使用的波长数与总波长数的比率；在小窗口中定义了负载阈值δ；它是一个0到1的常数，用于确定何时需要增加小窗口的覆盖范围；当链路中的负载大于负载阈值时，认为小窗口中链路中的负载较大，应该增加窗口大小和收敛范围，以提高通信的成功率；然后定义已调整大小的窗口的长度和宽度，它们的值是调整大小后小窗口的长度和宽度中包含的节点数；它们分别表示为lwx2和lwy2；最后，定义了自适应小窗口调整公式对于小窗口的尺寸调整，设计了相应的公式和规则：其中μ是交通强度因子，它是一个常数，反映了窗口中交通强度对其大小的影响；当通过自适应小窗调整公式计算新窗边长时，每个矩形窗的长度和宽度分别延伸到两端；
第二步：采用启发式算法通过跳数松约束策略来限制优化方法的收敛区域；
提出了优先邻接节点和次优先邻接节点概念，利用位置管理策略及自适应小窗口策略计算当前路由节点所有的邻接节点的坐标和目的节点的坐标，计算欧几里得距离；将邻接节点归类为优先节点和次优先节点，在计算路由时，先屏蔽次优先节点采用优先节点进行路由计算，当无可用优先节点时再采用次优先节点计算；
通过自适应小窗口策略来严格限制优化方法的收敛区域时，就会增加通信阻塞的概率，因为它限制了可用路由链路的探索潜力；另外一个重要的问题是如何选择可用的下一跳节点集；通过对下一跳集的优化，提高优化方法的性能；利用位置管理策略，LEO低轨星座中任意一个卫星的位置可以用坐标表示，因此，任意两个卫星节点的相对位置可以表示为向量，目标节点与当前节点之间的相对位置指向表示为箭头；相对位置向量可以由两个节点的坐标表示为: 其中，nd、nc分别代表目的节点与当前节点的横坐标，md、mc分别代表目的节点与当前节点的纵坐标，根据相对位置的表达式，主向量可以分成两个正交向量，相对距离可以计算为:
相对距离只与节点数有关，每个下一跳将产生一个与目的节点新的相对距离，它可以表示为： 如果 表明当前节点有效地接近目标节点，可以称之为有效跃点；
总共有三种当前节点位置：第一种情况，当前节点在窗口边缘的时候；在这种情况下，窗口中的节点将被判断为高优先级节点；窗外的节点将被判定为低优先级节点；此外，所有相邻的节点都在窗口中；在第二种情况下，当前节点及所有相邻节点都在窗口内部，窗口中的所有相邻节点将被判断为高优先级的相邻节点；第三种情况下，当前节点已经跳出窗口；通过卫星节点位置管理将确定相邻节点的矢量位移是否缩短了当前节点与目标节点之间的矢量距离；只有能够减少与目标矢量距离的节点才被视为高优先级的节点；否则，会被视为低优先级节点；
第三步：优化方法根据状态转移函数进入下一跳，并更新本地信息素，重复第二步，直到达到目的节点或无法预留频谱资源；
第四步：利用首次匹配方法分配可用频谱资源，更新全局信息素；
第五步：优化方法重复步骤1到步骤4直到优化方法收敛到一条最优的收敛路径。
一种星上路由与频谱分配优化方法
技术领域
[0001] 本发明涉及卫星通信技术领域，特别是涉及一种星上路由与频谱分配优化方法。技术背景背景技术
[0002] 随着即时通信业务和视频点播业务需求的急速上涨，与物联网技术的飞速发展。在万物互联的时代，不仅存在人与人之间的通信需求，物与物之间的通信也变得更为频繁与重要。此外，对于遥远山区与海洋的通信需求也逐渐显现出来。传统的地面网络受限于容量和覆盖面积已经无法完全满足大数据传输与高可靠性接入服务。因此卫星网络因为其独有的高覆盖、长距离、多接入能力使其在未来网络发展的重要性日渐加深。其中，随着小型轻量化的激光器投入生产并在卫星上进行使用，卫星光网络已经成为卫星网络中不可或缺的组成部分。而普通波分复用光网络存在着波长颗粒度大的问题，导致大量通信资源被浪费。为了解决这一问题，有着可变频谱颗粒度的灵活频谱栅格应运而出，这使得在卫星弹性光网络的频谱资源利用率得到了大大提高。
[0003] 路由与频谱分配算法是决定卫星弹性光网络性能的关键技术，路由是指在网络拓扑中从源节点到目的节点的路径顺序。相对于地面通信网络，卫星网络拓扑具有高动态性且节点分布比地面网络拓扑的更为密集与规律，故而采用常规的路由算法会导致卫星拓扑的局部流量堆积导致通信请求资源预留失败，且因为卫星星座链路会随着时间而产生断联现象，这就使得现有地面通信网络路由算法不适用于卫星通信，需要在地面通信网络路由算法的基础上进行卫星通信网络路由算法的研究，所以随着卫星网络的发展卫星路由算法也渐渐成为国内外学者的研究方向。在频谱分配方面，不合理的频谱分配方式会导致卫星弹性光网络中产生大量的频谱碎片，这些频谱碎片的频谱容量无法满足单个业务的需求，但频谱碎片的过多累计也会导致频谱资源的过度浪费，因此频谱分配也是弹性光网络中的重要问题之一。
[0004] 现阶段，基于LEO的单层卫星星座网络结构经过近几十年的快速发展，卫星弹性光网络可以承担全球物联网的接入和传输功能。由几十颗卫星组成的光学卫星网络可以提供几乎全球的覆盖范围。低轨卫星通过形成星座提供足够的地面覆盖面积。此外，低轨卫星可以通过微波束访问传统地面网络无法提供服务的远程地面网络。在低轨星座中，卫星通过激光束连接，形成永久或非永久激光链路。此外，随着软件定义网络技术的发展和应用，数据传输和计算解耦，可以缓解卫星计算能力不足的压力。光卫星网络的优势促进了民用、军事和商业通信的发展。
[0005] 优化算法需要具有的高鲁棒性和易于修改的特点才适合应用于卫星的高动态性网络拓扑上，针对卫星弹性光网络中的路由和频谱分配问题，当前路由策略存在卫星间链路丢失和较高的端到端时延等问题。如今在解决网络路由问题方面的研究越来越多，其中大部分研究的目的是降低阻塞率、降低时延、提高收敛速度以改善网络性能。
发明内容
[0006] 本发明实施例的目的在于提供一种星上路由与频谱分配的优化方法，以实现路由业务的低阻塞率、低时延，同时保证方法的收敛速度。具体技术方案如下：
[0007] 本发明实施的一方面，提供了基于LEO卫星网络的节点位置管理策略其中，[0008] 所述基于LEO卫星网络的节点位置管理策略，其目的在于后续策略确定LEO星座中各卫星之间的位置关系，为后续方法策略提供坐标信息。基于LEO卫星网络的节点位置管理策略主要实施与LEO的卫星星座网络，LEO卫星之间的排列呈曼哈顿网络的形式。除边缘节点，每个卫星节点都有四个链路与其他卫星相连。
[0009] 本专利之所以采用LEO星座，是因为LEO卫星具有传播时延小、误码率低、能够覆盖极地区域等优点，有利于避免GEO卫星无法覆盖极地区域和LEO卫星星上处理能力弱等缺点，而且该模型也采用了冗余设计，这是因为卫星节点需要有冗余，以防通信过程中节点故障从而影响整个网络的性能。
[0010] 所述基于LEO卫星网络的卫星节点位置管理策略，在LEO卫星星座网络的基础上，提出了基于LEO卫星网络的卫星节点位置管理策略，该系统每一个LEO卫星都有一个专属的在星座中的位置坐标。组内所有LEO卫星成员所对应的位置坐标在任何时间点保持相对不变，即任何LEO节点之间的相对位置关系和其本身的坐标是初始确定且不随时间变化而改变的。其LEO的位置坐标由其在星座中的轨道编号和所在轨道位置确定，其位置管理策略的意义在于计算不同节点之间的位置关系。
[0011] 本发明实施的一方面提供了一种基于优化方法的自适应小窗口策略，所述基于优化方法的自适应小窗口策略，其主要包括，自适应小窗口分为两部分。第一部分是初始化小窗口。第二部分是通过小窗口内的初始流量负载调整窗口大小。在初始化小窗口的步骤中，将首先获得源节点和目标节点的位置信息。当通信请求到达时根据每个业务的源卫星节点与目的卫星节点的路由器地址，通过卫星节点位置管理策略源卫星节点与目的卫星节点的路由器地址，计算出两者在卫星星座的位置坐标(ms,ns)，(md,nd)，并以源节点和目的节点的坐标生成限制优化方法收敛区域的矩形窗，作为初始优化方法的小窗口。每个轨道上的卫星数量是S，当|md‑ms|≤S/2使用 图 2 的 (a) 构造一个面积最小的矩形窗口时。否则，应该使用图 2 的 (b) 来构造窗口。当设置一个小的矩形窗口来限制优化方法的迭代范围时，很明显，优化会更快地收敛并以更短的跳数到达目标节点。在完成小窗口的建立后，计算小窗口包含的行卫星节点数为边长lwx，与包含的列卫星节点数作为边长lwy。之后统计在初始小窗口的频谱利用信息，计算小窗口标记过所有卫星节点的邻接节点频谱占用情况，计算总体的频谱利用率记为 SW。它的值是小窗口中所有链路中使用的波长数与总波长数的比率。在小窗口中定义了负载阈值δ。它是一个0到1的常数，用于确定何时需要增加小窗口的覆盖范围。当链路中的负载大于负载阈值时，认为小窗口中链路中的负载较大，应该增加窗口大小和收敛范围，以提高通信的成功率。然后定义已调整大小的窗口的长度和宽度，它们的值是调整大小后小窗口的长度和宽度中包含的节点数。它们分别表示为lwx2和lwy2。最后，定义了自适应小窗口调整公式对于小窗口的尺寸调整，相应的公式和规则为：
[0012]
[0013]
[0014] 其中是μ交通强度因子，它是一个常数，反映了窗口中交通强度对其大小的影响。当通过自适应小窗调整公式计算新窗边长时，每个矩形窗的长度和宽度分别延伸到两端。
[0015] 本发明实施的一方面，提供了一种跳数松约束策略，所述策略包括：
[0016] 通过一种自适应小窗口策略来限制优化方法的收敛区域。但是，如果我们使用一个小窗口来严格限制收敛区域，就会增加通信阻塞的概率。因为它限制了可用路由链路的探索潜力。另外，对于优化方法，一个重要的问题是如何选择可用的下一跳节点集。通过对下一跳集的优化，提高优化方法的性能。利用位置管理策略，LEO低轨星座中任意一个卫星的位置可以用坐标表示，因此，任意两个卫星节点的相对位置可以表示为向量，目标节点与当前节点之间的相对位置指向表示为箭头。类似地，相对位置向量可以由两个节点的坐标表示为: 根据相对位置的表达式，主向量可以分成两个正交向量，相对距离可以计算为:
[0017]
[0018] 应该注意的是，相对距离只与节点数有关，没有考虑链路长度。显然，路由计算过程就是使相对距离逐渐缩小。每个下一跳将产生一个新的相对距离目标节点，它可以表示为： 如果 可以认为当前节点有效地接近目标节点，可以称之为有效跃点。如图4所示，它用黑色表示高优先级节点，用无色表示低优先级节点，总共有三种当前节点位置。第一种情况，即当前节点在窗口边缘的时候。在这种情况下，窗口中的节点将被判断为高优先级节点。窗外的节点将被判定为低优先级节点。此外，所有相邻的节点都在窗口中。在第二种情况下，窗口中的所有相邻节点将被判断为高优先级的相邻节点。目的是为给算法提供更多的机会，计算不同的路由路径。
[0019] 当前节点已经跳出窗口。该方法将确定相邻节点的矢量位移是否缩短了当前节点与目标节点之间的矢量距离。只有能够减少与目标矢量距离的节点才被视为优先级较高的节点。否则，就会被视为低优先级节点。
[0020] 在跳数松约束规则下，当相邻节点集中同时存在高优先级节点和低优先级节点时。方法会先屏蔽掉低优先级的节点。如果高优先级邻接节点集中没有可用的连续波长，则将低优先级节点添加到可用的邻接节点集中。该规则允许方法在小窗口内相邻节点的波长资源不足时，计算窗口外的路由选择。
[0021] 本发明实施的又一方面，还提供了一种包含上述策略的路由与频谱分配方法，所述方法包括：
[0022] 在LEO卫星星座网络模型上实施该方法，采用上述卫星节点位置管理策略计算每个卫星的位置坐标信息，采用上述自适应小窗口策略限制方法的收敛范围，采用上述跳数松约束策略适当增加计算路由路径范围。
[0023] 方法优化过程:在本优化方法中，优化目标为：尽量减少所计算出的路由路径的时延和频谱利用率。
[0024] 第一步：当一个路由业务到来时，根据每个业务的源卫星节点与目的卫星节点的路由器地址，通过卫星节点位置管理策略，计算源节点与目的节点的位置坐标，生成初始矩形小窗口，并统计窗口内所有链路的频谱利用率，根据统计结果调整窗口大小，采用自适应小窗口策略限制方法的收敛面积。
[0025] 第二步：优化方法从源节点出发，利用上述跳数松约束策略判断其四个邻接节点的优先级，根据链路上残留的信息素首先在高优先级选择下一跳路由，如果不存在高优先级邻接节点，则从低优先级节点进行计算。
[0026] 第三步：根据状态转移函数进入下一跳，并更新本地信息素，重复第二步，直到达到目的节点或无法预留频谱资源。
[0027] 第四步：利用首次匹配方法分配可用频谱资源
[0028] 第五步：优化方法重复步骤1到步骤4直到所有的迭代完成。
附图说明
[0029] 为了更清楚地说明本发明实施例或现有技术中的技术方案，下面将对实施例或现有技术描述中所需要使用的附图作简单地介绍，显而易见地，下面描述中的附图仅仅是本发明的一些实施例，对于本领域普通技术人员来讲，在不付出创造性劳动的前提下，还可以根据这些附图获得其他的附图。
[0030] 图1为本发明实施例提供的优化方法流程图；
[0031] 图2为本发明实施例提供的自适应小窗口的初始窗口示意图；
[0032] 图3为本发明实施例提供的自适应小窗口策略的窗口扩张示意图；
[0033] 图4为本发明实施例提供的跳数松约束策略示意图；
具体实施方式
[0034] 下面将结合本发明实施例中的附图，对本发明实施例中的技术方案进行清楚、完整地描述，显然，所描述的实施例仅仅是本发明一部分实施例，而不是全部的实施例。基于本发明中的实施例，本领域普通技术人员在没有做出创造性劳动前提下所获得的所有其他实施例，都属于本发明保护的范围。
[0035] 参见图1，示出了本发明实施例提供的优化方法流程示意图：
[0036] 首先，当一个路由业务到来时，根据每个业务的源卫星节点与目的卫星节点的路由器地址，通过卫星节点位置管理策略，计算源节点与目的节点的位置坐标，生成初始矩形小窗口，并统计窗口内所有链路的频谱利用率，根据统计结果调整窗口大小，采用自适应小窗口策略限制方法的收敛面积；
[0037] 之后优化方法从源节点出发，利用上述跳数松约束策略判断其四个邻接节点的优先级，首先在高优先级选择下一跳路由，如果不存在高优先级邻接节点，则从低优先级节点进行计算；
[0038] 接着，根据状态转移函数进入下一跳，并更新本地信息素，重复第二步，直到达到目的节点或无法预留频谱资源；
[0039] 若存在可用频谱资源，利用首次匹配方法分配可用频谱资源；
[0040] 第五步：优化方法重复步骤1到步骤4直到所有的迭代完成。
[0041] 参见图2，示出了本发明实施例提供的自适应小窗口策略中初始化小窗口的生成示意图。
[0042] 在初始化小窗口的步骤中，将首先获得源节点和目标节点的位置信息。当通信请求到达时，可以将源节点的位置表示为。第一部分，根据每个业务的源卫星节点与目的卫星节点的路由器地址，通过卫星节点位置管理策略，通过源卫星节点与目的卫星节点的路由器地址，计算出两者在卫星星座的位置坐标，并以源节点和目的节点的坐标生成限制优化方法收敛区域的矩形窗，作为初始优化方法的小窗口。每个轨道上的卫星数量是S，当使用 图2 的 (a) 构造一个面积最小的矩形窗口时。否则，应该使用‑ 图2 的(b) 来构造窗口。当我们设置一个小的矩形窗口来限制优化方法的迭代范围时，很明显，优化会更快地收敛并以更短的跳数到达目标节点。
[0043] 参见图3，示出了本发明实施例提供的基于LEO星座网络的自适应小窗口调整策略，包括：
[0044] 基于LEO星座网络的自适应小窗口调整策略具体思路如下：
[0045] 第一步：计算小窗口包含的行卫星节点数为边长lwx，与包含的列卫星节点数作为边长lwy；
[0046] 第二步：统计在初始小窗口的频谱利用信息，计算小窗口标记过所有卫星节点的邻接节点频谱占用情况；
[0047] 第三步：计算总体的频谱利用率记为SW。它的值是小窗口中所有链路中使用的波长数与总波长数的比率。在小窗口中定义了负载阈值δ。它是一个0到1的常数，用于确定何时需要增加小窗口的覆盖范围。当链路中的负载大于负载阈值时，认为小窗口中链路中的负载较大，应该增加窗口大小和收敛范围，以提高通信的成功率；
[0048] 第四步：定义已调整大小的窗口的长度和宽度，它们的值是调整大小后小窗口的长度和宽度中包含的节点数。它们分别表示为lwx2和 lwy2。
[0049] 参见图4，示出了本发明实施例提供的基于LEO星座卫星网络的跳数松约束策略图，包括：
[0050] 跳数松约束策略的具体思路如下：
[0051] 目标节点与当前节点之间的相对位置指向表示为箭头。类似地，相对位置向量可以由两个节点的坐标表示为: 根据相对位置的表达式，主向量可以分成两个正交向量，相对距离可以计算为:
[0052]
[0053] 相对距离只与节点数有关，没有考虑链路长度。显然，路由计算过程就是使相对距离逐渐缩小。每个下一跳将产生一个新的相对距离目标节点，它可以表示为： 如果可以认为当前节点有效地接近目标节点，可以称之为有效跃点。如图所示，它用黑色表示高优先级节点，用灰色表示低优先级节点，总共有三种当前节点位置。第一种情况，即当前节点在窗口边缘的时候。在这种情况下，窗口中的节点将被判断为高优先级节点。窗外的节点将被判定为低优先级节点。此外，所有相邻的节点都在窗口中。在第二种情况下，窗口中的所有相邻节点将被判断为高优先级的相邻节点。这是因为的目的是为提供更多的机会，计算不同的路由路径。
[0054] 当前节点已经跳出窗口。该方法将确定相邻节点的矢量位移是否缩短了当前节点与目标节点之间的矢量距离。只有能够减少与目标矢量距离的节点才被视为优先级较高的节点。否则，就会被视为低优先级节点。
