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

有效

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

本發明涉及一種基于群體智能的LEO衛星網絡擁塞規避組播路由算法，本發明提供的一種基于群體智能的LEO衛星網絡擁塞規避組播路由算法，通過刪除最小生成樹與擁塞相交的邊，將最小生成樹轉化為一組子樹，將LEO衛星網絡建模為直角網格拓撲的多跳網絡，將擁塞規避的節省帶寬最優的組播路由問題轉化為擁塞規避的直角斯坦納最小樹問題；針對蟻群算法前期初始信息素的匱乏導致求解問題較慢的不足，考慮到遺傳算法具有快速全局搜索能力的優勢，本發明利用基于蟻群與遺傳聯合優化算法的擁塞規避直角斯坦納最小樹算法算法實現子樹合并，可達到降低算法計算復雜度的同時降低擁塞規避直角斯坦納最小樹的樹長，以實現擁塞規避和節省帶寬最優的目標。

技術領域

本發明涉及組播路由算法領域，尤其涉及一種基于群體智能的LEO衛星網絡擁塞規避組播路由算法。

背景技術

LEO（Low Earth Orbit，低地球軌道）衛星網絡能夠以多個LEO衛星構建低軌衛星通信系統的方式來實現真正的全球無縫覆蓋，兼具傳輸損耗小、通信時延短、抗毀能力強、終端小型化等突出特點，其具備的高帶寬特性，使之成為組播業務的理想載體。研究衛星組播通信的關鍵技術之一是建立性能良好的組播樹。為了傳送多個組播，應該盡量減少對于網絡帶寬的消耗。然而LEO衛星網絡中存在著網絡擁塞等情況，網絡擁塞將導致整個網絡的性能下降。

現有的LEO組播路由算法往往將目標集中在最小化組播樹的整體開銷或傳輸時延方面。然而，全球范圍內的網絡流量并未均衡分布，發達國家相比發展中國家產生更高的網絡流量，因此，LEO衛星網絡中用戶分布不均以及太空環境中不確定的空間干擾因素會使得衛星之間的通信鏈路出現部分鏈路不穩定的狀況，導致網絡擁塞的問題在衛星通信網絡中難以避免。網絡擁塞會對整個網絡造成極大的危害，嚴重時將導致整個系統發生擁塞崩潰。但現有LEO組播路由算法通常忽略了網絡擁塞的問題。如何實現網絡擁塞規避來找到一條網絡資源占用少的路徑，從而滿足視頻聊天、應急通信等各種應用需求，是為全球提供可靠網絡服務的關鍵。

發明內容

本發明針對現有技術中存在的技術問題，提供一種基于群體智能的LEO衛星網絡擁塞規避組播路由算法，將LEO衛星網絡建模為直角網格拓撲的多跳網絡，將擁塞規避的節省帶寬最優的組播路由問題轉化為擁塞規避的直角斯坦納最小樹問題；針對蟻群算法前期初始信息素的匱乏導致求解問題較慢的不足，考慮到遺傳算法具有快速全局搜索能力的優勢，本發明提出了基于蟻群與遺傳聯合優化算法的擁塞規避直角斯坦納最小樹算法，以實現擁塞規避和節省帶寬最優的目標。

根據本發明的第一方面，提供了一種基于群體智能的LEO衛星網絡擁塞規避組播路由算法，包括：步驟1，將LEO衛星網絡建模為直角網格拓撲的多跳網絡，構建由所有組播組節點組成的最小生成樹，刪除所述最小生成樹中與擁塞相交的邊后生成各個子樹；

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

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

在上述技術方案的基礎上，本發明還可以作出如下改進。

可選的，所述步驟1中構建所述最小生成樹的過程包括：構建由所有所述組播組節點組成的完整加權圖，基于Prim算法生成所述最小生成樹。

可選的，所述組播組節點與擁塞的接觸限制規則包括：

任意兩個擁塞不能相互重疊；

所述組播組節點不能位于任意所述擁塞的邊界線的內部；

所述擁塞規避直角斯坦納最小樹中的任何一條邊均不能與任意所述擁塞相交。