本发明属于通信，尤其涉及一种基于启发式规则a*算法的网格路由计算方法。
背景技术：
1、目前的空间网络低轨通信卫星系统中，常采用倾斜轨道星座和极地轨道星座两种构型，整个系统构建为典型的网格状拓扑。在这种连接方式下，每颗卫星有四颗相邻的卫星，两颗在同一轨道面上，两颗在相邻轨道面上。
2、传统的空间网络中，方向路由算法的问题是基于4个方向定义的转发规则来进行报文转发的，这样可以降低路由计算的代价。但是由于无全局拓扑视图，方向路由只能实现可达性，无法实现全局最短路径，也无法应对复杂的链路权重规则，尤其是出现链路中断时可能无法路由，且方向性路由只适用于卫星网络network路由，无法支持前缀路由；同时，方向路由不是转控分离架构，而是在收到报文后先按照方向路由的转发规则选择报文的出接口，然后再转发报文，因此每个报文都需要做路由选择，这种架构的转发性能无法提升。
3、而现代的路由交换设备通常都是采用转控分离架构，控制面计算好路由，然后下发到数据转发面，数据转发面只需要根据计算好的路由进行报文转发，这种架构是一种软件定义网络架构，数据转发面可以采用asic芯片实现，因此转发性能得以成千上万倍地提升。
4、此外，现代路由交换设备常采用dijkstra算法进行网络最短路径的计算。dijkstra算法是一种最短路径算法，核心思想是基于贪心策略，每次选择当前距离开始节点最近的节点，并通过该节点更新与它相邻的节点的距离。但是，dijkstra算法用于卫星网络存在以下几个问题：
5、1、没有很好地利用网络的网格状方向性拓扑的特征来简化路由计算；
6、2、dijkstra算法的实质是广度优先搜索，是一种发散式的搜索，所以空间复杂度和时间复杂度都比较高。
7、另一种最短路径算法是a*算法，a*算法在dijkstra算法的基础上增加了启发式规则，能够降低路由计算的复杂性，但是还没有在网络路由计算中得到应用。
技术实现思路
1、发明目的：基于卫星网络的拓扑特点，针对方向路由方法和dijkstra路由计算方法中存在的问题，本发明公开了一种基于启发式规则a*算法的a*+网格路由计算方法，既克服了方向性路由转控不分离的缺陷，又通过引入启发式规则来降低路由计算的复杂性，相比于传统的dijkstra路由计算方法，提升了卫星网络的路由计算性能，可以更快实现格状卫星网络拓扑中的路由计算。
2、本发明提出的一种a*+网格路由计算方法具体包括如下步骤：
3、s1、依照给定的格状路由的链路权重设定方法，建立全局网络连通性有向图：
4、s1.1在低轨卫星网络基础上建立全局网络连通性拓扑图。把整个卫星星座网络看成一个由卫星为顶点、星间链路为边形成的网状拓扑图，每颗卫星有一个主机地址，能够用于网络路由的下一跳，将每颗卫星上、左、下、右四个方向的出接口分别编号为oif1、oif2、oif3、oif4。
5、由于卫星网络的拓扑变化具有空间上的周期性，因此可以通过对卫星在地面上映射点的地理位置划分区域，每个区域用二元数组赋予一个逻辑地址，其中代表轨道编号，代表轨内卫星编号；区域的管理者为距离中心点最近的卫星，卫星离开该区域时由后续的卫星接替当前卫星的位置。
6、s1.2在全局网络连通性拓扑图基础上建立有向图。有向图中节点代表卫星节点，用区域的逻辑地址进行表示；边代表卫星间的链路，给定如下的格状拓扑的链路权重设定方法进行链路权重赋值，特别地，同一对卫星相互间的星间链路的两个方向均需要赋值且默认为相同值，卫星间链路断开时权重值为无穷大：
7、在采用网格状拓扑连接方式的星座中，如极轨星座和倾斜轨道星座，同一轨道面上相邻卫星建立的星间链路长度是确定值，临近轨道面的相邻卫星建立的星间链路长度在卫星运动过程中随着纬度发生空间周期性的变化。设同一轨道面上两颗卫星的星间链路长度为1，可以依照轨道面内和轨道面间链路长度关系，计算出不同纬度处的归一化的临近轨道间的相邻卫星星间链路长度，以此归一化的星间链路长度作为后续路径搜索时的链路开销，也即有向图中的链路权重值，从而将跳数与传播距离统一起来。
8、s2、基于步骤s1中建立的有向图，引入如下的启发式规则，对满足该规则的节点对直接建立最短路径，并计算最短路径经过节点的有序排列：
9、s2.1轨道内、轨道间相邻节点之间直接建立最短路径；
10、s2.2同时存在轨道内和轨道间链路时，优先选择轨道内链路，即规定同一轨道上的所有节点对之间的路径为建立的最短路径。
11、s3、对于不满足s2中所设定的启发式规则的剩余节点对，采用a*有向性搜索算法对最短路径及最短路径经过节点的有序排列进行计算。对路径上的当前点，a*+方法不但记录其到开始节点的开销，还计算当前点到目标点的期望开销，可以利用网格状方向性拓扑的特征降低路由计算的复杂性，提升路由计算性能。
12、移动开销 f的计算过程如下：
13、，
14、其中， g为所求节点距离开始节点的实际开销，即为该节点到开始节点的路径沿途有向边的开销之和， h为该节点距离终点的估计开销，由给定的启发函数确定。为了保证算法寻找到的最短路径的正确性，需要满足，其中为实际代价，启发函数设定为跳数*系数，系数的值根据 g值的大小进行调整，以确保可以寻找到正确的最短路径且启发函数的值接近最优路径的实际开销。
15、对于每个节点，使用a*算法计算得到该节点到其他所有节点的最短路径的步骤如下：
16、s3.1建立openlist表和closelist表两个状态表，其中，openlist表由待考察的节点组成，closelist表由已经考察过的节点组成；
17、s3.2将开始节点加入openlist表中；
18、s3.3重复以下过程：
19、s3.3.1遍历openlist表，查找 f值最小的节点，并将其作为当前要处理的节点。
20、s3.3.2对当前要处理的节点的所有相邻节点，做如下操作：
21、①若相邻节点不可达或已经存在于closelist表中，忽略该节点不进行处理；
22、②若相邻节点不在openlist表中，则将该节点加入openlist表，并将当前节点作为其父节点，计算新加入openlist表的相邻节点的 f、 g、 h值，注意此处的 g值是经由当前节点路径计算得到的 g值；
23、③若节点已经在openlist表中，用 g值作为参考检查经由当前节点的这条路径是否更好， g值更小说明该路径为更好的路径，则设当前节点为其父节点，重新计算 g值和 f值。
24、s3.3.3处理完openlist表中当前节点的所有相邻节点后，将该节点移入closelist表中。
25、s3.4对于每个节点，重复s3.3，直至满足下面条件中的一个时，计算终止：
26、①将目的节点加入到了openlist表中，表示已经找到了路径；
27、②查找目的节点失败，并且openlist表是空的，表示没有路径。
28、s3.5若目的节点已经找到，则记录从目的节点开始，每个节点都沿着父节点移动到开始节点的路径，该路径即为所求的最短路径，将经过最短路径的节点即依次放入列表中即为最短路径经过节点的有序排列。
29、s4、计算出每个卫星节点到其他所有节点的最短路径之后，进行network路由计算，对于每个节点，从最短路径中反推每个路径的下一跳及提取出接口信息，将每个节点的下一跳和相应的出接口信息添加到源节点的路由表中，计算得到卫星网络的network路由。
30、s5、基于步骤s4中计算出的卫星网络network路由，进行前缀路由的迭代计算：
31、s5.1在卫星节点上获取一条前缀路由的引入节点；
32、s5.2针对卫星节点，在network路由中获得引入节点的下一跳ip地址和出接口oif，从而迭代出该前缀路由的下一跳即为该ip地址，出接口为该oif；
33、s5.3重复s5.1、s5.2，直至迭代出卫星节点的所有前缀路由，迭代终止；
34、s5.4对下一个卫星节点重复步骤s5.1、s5.2、s5.3，进行下一个卫星的前缀路由迭代，直至算出所有路由前缀在所有卫星节点上的路由，计算终止。
35、s6、输出节点对之间的network路由和前缀路由的路由信息表：
36、s6.1输出每条路由的表项，包括网络前缀、掩码或前缀长度、下一跳ip地址和出接口oif；
37、s6.2进一步地，依据计算出的最短路径经过节点的有序排列，转换成源路由的有序排列（segment list），在源节点srh头部中封装segment list，转发面即可根据该有序排列进行段路由的逐段转发，从而实现显式路径的控制。
38、s7、控制面将计算好的路由信息表下发到数据转发面，形成转发信息表。
39、s8、数据转发面对分组报文直接查找转发信息表，获得报文的出接口，将报文转发至下一跳。
40、有益效果：
41、1、a*算法的时间复杂性低于dijkstra算法，即使在最坏情况下，a*算法会退化为dijkstra算法，复杂性也相当。对于a*算法而言，算法的精确性取决于启发函数，越接近实际开销，算法效果越好。本发明提出的a*+算法是基于a*算法实现的，时间复杂性低；同时设计了接近最优路径实际开销的启发函数，路由计算时间优于现有路由交换设备普遍采用的dijkstra路由计算方法。
42、2、相比于传统的a*算法，本发明提出的a*+方法通过增加启发式规则，减少探索的网络节点数，路由计算效率进一步提高。
43、3、本发明提出的a*+方法除了可以实现最短路由的计算，还可以与源路由（segment routing，sr）关联起来，将最短路径经过的节点序列转换成段和网络节点的有序排列，在控制面直接得到sr路由的segment list，数据转发面就可以根据这个有序排列进行段路由的逐段转发。
44、4、本发明提出的a*+方法实现了转控分离，相比于传统方向性路由，可以显著提升转发性能。
1.一种a*+网格路由计算方法，其特征在于，该方法包括如下步骤：
2.根据权利要求1所述的a*+网格路由计算方法，其特征在于，步骤s1所述的建立全局网络连通性有向图，包括：
3.根据权利要求2所述的a*+网格路由计算方法，其特征在于，所述进行链路权重赋值的时候，同一对卫星相互间的星间链路的两个方向均需要赋值且默认为相同值，卫星间链路断开时链路权重值为无穷大。
4.根据权利要求1所述的a*+网格路由计算方法，其特征在于，步骤s2、步骤s3中所述的启发式规则包括：
5.根据权利要求4所述的a*+网格路由计算方法，其特征在于，步骤s3所述的对不满足启发式规则的节点对采用a*搜索算法对最短路径及最短路径经过节点的有序排列进行计算，包括：
6.根据权利要求1所述的a*+网格路由计算方法，其特征在于，步骤s5所述的基于步骤s4中计算出的network路由进行前缀路由的迭代计算，包括：
7.根据权利要求1所述的a*+网格路由计算方法，其特征在于，步骤s6所述的输出节点对之间的network路由和前缀路由的路由信息表，具体包括：
