一种基于群体智能的LEO卫星网络拥塞规避组播路由算法.pdf

(19)中华人民共和国国家知识产权局(12)发明专利申请(10)申请公布号CN114244774A(43)申请公布日2022.03.25(21)申请号202210165978.8(22)申请日2022.02.23(71)申请人武汉烽火凯卓科技有限公司地址430000湖北省武汉市洪山区卓刀泉271号五环广场二幢一单元15层18号房(72)发明人彭凯桂宾毛薇邓天平周昂陈程鹏(74)专利代理机构武汉蓝宝石专利代理事务所(特殊普通合伙)42242代理人万畅(51)Int.Cl.H04L47/12(2022.01)H04L45/48(2022.01)H04B7/185(2006.01)权利要求书2页说明书10页附图6页(54)发明名称一种基于群体智能的LEO卫星网络拥塞规避组播路由算法(57)摘要本发明涉及一种基于群体智能的LEO卫星网络拥塞规避组播路由算法，本发明提供的一种基于群体智能的LEO卫星网络拥塞规避组播路由算法，通过删除最小生成树与拥塞相交的边，将最小生成树转化为一组子树，将LEO卫星网络建模为直角网格拓扑的多跳网络，将拥塞规避的节省带宽最优的组播路由问题转化为拥塞规避的直角斯坦纳最小树问题；针对蚁群算法前期初始信息素的匮乏导致求解问题较慢的不足，考虑到遗传算法具有快速全局搜索能力的优势，本发明利用基于蚁群与遗传联合优化算法的拥塞规避直角斯坦纳最小树算法算法实现子树合并，可达到降低算法计算复杂度的同时降低拥塞规避直角斯坦纳最小树的树长，以实现拥塞规避和节省带宽最优的目标。CN114244774ACN114244774A权利要求书1/2页1.一种基于群体智能的LEO卫星网络拥塞规避组播路由算法，其特征在于，所述路由算法包括：步骤1，将LEO卫星网络建模为直角网格拓扑的多跳网络，构建由所有组播组节点组成的最小生成树，删除所述最小生成树中与拥塞相交的边后生成各个子树；步骤2，定义拥塞为平面上的矩形，组播组节点为平面上的点，基于所述组播组节点与所述拥塞的接触限制规则构建拥塞规避生成图；步骤3，通过GA‑ACO‑SM算法将各个所述子树转化为拥塞规避斯坦纳最小树，包括：利用遗传算法搜索得到全局优化路径，将得到的所述全局优化路径传递给蚁群算法，确定所述蚁群算法初期的信息素浓度分布，在所述拥塞规避生成图上利用所述蚁群算法进行寻路和优化，找到连接各个所述子树的最优路径后进行各个所述子树的合并，生成所述拥塞规避斯坦纳最小树。2.根据权利要求1所述的路由算法，其特征在于，所述步骤1中构建所述最小生成树的过程包括：构建由所有所述组播组节点组成的完整加权图，基于Prim算法生成所述最小生成树。3.根据权利要求1所述的路由算法，其特征在于，所述组播组节点与拥塞的接触限制规则包括：任意两个拥塞不能相互重叠；所述组播组节点不能位于任意所述拥塞的边界线的内部；所述拥塞规避直角斯坦纳最小树中的任何一条边均不能与任意所述拥塞相交。4.根据权利要求1所述的路由算法，其特征在于，所述遗传算法的编码方式为基于路径表示的编码方式，用基因表示一棵子树到其他子树的一条路径；生成备选路径集合的过程包括：用任意一棵子树到其他子树的各条路径生成所述备选路径集。5.根据权利要求1所述的路由算法，其特征在于，所述遗传算法的适应度函数定义为路径长度的倒数；在计算路径T长度时，将环路中的最长路径去除后，将剩余连通路径设为T'，将T'总长度作为染色体方案的代价。6.根据权利要求1所述的路由算法，其特征在于，所述遗传算法的遗传操作包括：选取适应度最高的上一代父代染色体，按照适应度从高到低依次和另一条父代染色体匹配，直到存在相同起始子树和目的子树且包含交叉点的基因；父代染色体出现多个重合节点时，使用父代染色体的第一个重合的节点进行操作；在每一次的交叉过程中，检测子代的路径中是否存在环路的情况，并且进行解环。7.根据权利要求1所述的路由算法，其特征在于，利用所述蚁群算法进行寻路和优化的过程包括：步骤311，在每棵子树上分别放置一只蚂蚁，使用PlaceAnt算法计算每只蚂蚁的初始位置和初始禁忌表所包含的顶点；步骤312，进行m群蚂蚁寻路；蚂蚁寻路过程中，通过AntMove算法解决蚂蚁进入死路，通过DetermineAntPath算法确定所有蚂蚁走过的路径；记录并更新每群蚂蚁寻路的最优路径；随机选一只蚂蚁选择下一节点并修改禁忌表；判断是否与其他蚂蚁或其他蚂蚁所在子树相遇，是则执行步骤313；否则重新执行步骤312；步骤313，判定当前蚂蚁死亡，并将该当前蚂蚁的禁忌表添加至另一只蚂蚁的禁忌表2CN114244774A权利要求书2/2页中，判断是否存在存活蚂蚁，是则重新执行步骤312；否则执行步骤314；步骤314，判断m群蚂蚁是否均完成寻路，是则执行步骤315；否则重新执行步骤311；步骤315，更新