[發明專利]一種基于群體智能的LEO衛星網絡擁塞規避組播路由方法

有效

• 申請號: 202210165978.8
• 申請日: 2022-02-23
• 公開（公告）號: CN114244774B
• 公開（公告）日: 2022-05-06
• 發明（設計）人: 彭凱;桂賓;毛薇;鄧天平;周昂;陳程鵬
• 申請（專利權）人: 武漢烽火凱卓科技有限公司
• 主分類號: H04L47/12
• 分類號: H04L47/12;H04L45/48;H04B7/185
• 代理公司: 武漢藍寶石專利代理事務所(特殊普通合伙) 42242
• 代理人: 萬暢

1.一種基于群體智能的LEO衛星網絡擁塞規避組播路由方法，其特征在于，所述路由方法包括：

步驟1，將LEO衛星網絡建模為直角網格拓撲的多跳網絡，構建由所有組播組節點組成的最小生成樹，刪除所述最小生成樹中與擁塞相交的邊后生成各個子樹；

步驟2，定義擁塞為平面上的矩形，組播組節點為平面上的點，基于所述組播組節點與所述擁塞的接觸限制規則構建擁塞規避生成圖；

步驟3，通過遺傳與蟻群聯合優化算法將各個所述子樹轉化為擁塞規避斯坦納最小樹，包括：利用遺傳算法搜索得到全局優化路徑，將得到的所述全局優化路徑傳遞給蟻群算法，確定所述蟻群算法初期的信息素濃度分布，在所述擁塞規避生成圖上利用所述蟻群算法進行尋路和優化，找到連接各個所述子樹的最優路徑后進行各個所述子樹的合并，生成所述擁塞規避斯坦納最小樹；

步驟4，對所述擁塞規避斯坦納最小樹中的斜線邊進行直線化得到初始擁塞規避直角斯坦納最小樹，對所述初始擁塞規避直角斯坦納最小樹進行去除冗余段的局部優化后，得到擁塞規避直角斯坦納最小樹。

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，判定當前螞蟻死亡，并將該當前螞蟻的禁忌表添加至另一只螞蟻的禁忌表中，判斷是否存在存活螞蟻，是則重新執行步驟312；否則執行步驟314；

步驟314，判斷m群螞蟻是否均完成尋路，是則執行步驟315；否則重新執行步驟311；

步驟315，更新m群螞蟻所走過路徑的信息素濃度后，判斷迭代是否結束，是則將歷次迭代過程中的最短路徑作為子樹合并的所述最優路徑，將子樹與所述最優路徑中的每條邊相連實現子樹合并；否則重新執行步驟311。