[發明專利]基于最小連通支配集的衛星網絡多播路由方法及系統

在審

• 申請號: 201710590874.0
• 申請日: 2017-07-19
• 公開（公告）號: CN107370536A
• 公開（公告）日: 2017-11-21
• 發明（設計）人: 楊志華;荊瑩;陳守鳳;于海峰
• 申請（專利權）人: 哈爾濱工業大學深圳研究生院
• 主分類號: H04B7/185
• 分類號: H04B7/185;H04L12/761
• 代理公司: 深圳市科吉華烽知識產權事務所(普通合伙)44248
• 代理人: 孫偉

技術領域

本發明涉及衛星多播路由技術領域，尤其涉及一種基于最小連通支配集的衛星網絡多播路由方法及系統。

背景技術

近年來，研究人員對連通支配集進行了深入研究，并取得了很大進展，同時提出了許多經典的連通支配集算法。有關最小連通支配集(Minimum Connected Dominating Set,簡稱MCDS)的構造算法，目前主要分為兩大類：集中式算法和分布式算法。

集中式算法的主要思想是把最大度的節點作為根節點開始構建一棵樹，樹包含圖中所有節點，選擇樹的非葉子節點作為支配點。要求將整個網絡的拓撲信息集中到某個中心節點，而這將需要花費極大的通信代價，也會出現局部節點通信量過大的問題，因而并不適用于拓撲變化迅速的網絡，可擴展性差，但獲得的連通支配集的規模通常比分布式的要小。

分布式算法只需要知道當前節點的局部信息，各個節點獨立地計算自己的連接情況，具有較強的自組織能力。根據構造連通支配集的方式又可以分為三大類：(1)基于鄰居節點信息、(2)基于自裁剪，(3)基于極大獨立集。基于鄰居節點信息的算法是利用節點周圍N跳(通常是2-3跳)內的連通拓撲情況啟發式地構造連通支配集；基于自裁剪的算法是首先將網絡中所有節點加入連通支配集，然后裁剪連通支配集中冗余的支配點，最后剩余的節點為近似最小連通支配集；而基于極大獨立集(Maximum Independent Set,簡稱MIS)的算法是先構建一個極大獨立集，然后添加一些網關節點將獨立集連通，進而構造連通支配集的算法。基于相鄰節點信息的分布式算法思想是：節點根據判斷規則，利用距離其2跳的節點信息來確定自身狀態，最終得到連通支配集。另外也有提出區別于上述三大類的分布式算法，算法思想是如果有一個節點被定義為支配集，則它必須滿足其兩個鄰居點不相鄰。該方法雖然實現起來簡單，但缺點也很明顯，該算法運行結束后會產生較多的冗余支配點，而且在應對動態變化的網絡時需要付出較大代價。

對于衛星拓撲控制策略，由于衛星嚴格的軌道運動，衛星網絡的動態拓撲呈現周期性與可預測性，這是區別于其他動態網絡，如自組織網絡、傳感器網絡的主要特征。基于這一特點，衛星網絡的路由技術一般采用拓撲控制策略來屏蔽拓撲的動態性,然后,針對靜態的拓撲序列進行路由優化計算。目前,衛星網絡的拓撲控制策略主要包括虛擬拓撲策略、虛擬節點策略和覆蓋域劃分方法.虛擬拓撲策略將衛星網絡的動態拓撲進行離散化,一個系統周期T可劃分為若干個時間片[t0,t1],[t1,t2],[t2,t3],…,[tn-1,tn],星間鏈路的變化僅在時間點t1,t2,…,tn發生,且每個時間片[ti,ti+1]內衛星網絡假定拓撲不變.其中,以快照概念為典型代表,其形式化描述由Fischer等人完成.在快照概念中,一旦任意星間鏈路臨時斷開或重新連接,一個不同于先前的快照就形成了,每個快照內衛星拓撲固定不變.快照序列路由算法利用星座地周期性，按時間段從實時變化的星座中提取出n個拓撲，每個時隙內的網絡拓撲配看做靜止不變，從而可以離線分段計算路由，衛星在時隙邊界切換路由表。快照序列路由算法通過消除衛星節點之間的拓撲信息交換降低星上處理負擔，減少信令開銷。

對于衛星多播路由，隨著衛星技術的發展以及對于高效多播業務的需求，越來越多的衛星多播路由方案被提出。目前大多數應用于LEO層衛星網絡的路由算法被提出，主要包括基于DRA(Datagram Routing Algorithm,DAR)的多播路由算法和基于矩形斯坦樹(Rectilinear Steiner Trees,RST)的多播路由算法。在DRA路由算法中，源節點和其他節點之間利用數據報路由算法來確定當前目的節點的下一跳路由方向，主要是降低實時衛星通信過程中的端到端時延。但是此算法為實現相關性能的提升占據了衛星傳輸中許多必要的資源，代價較高；RST算法采用一種整數線性規劃方法來求解最小RST數，主要是降低總的帶寬，適用于很多非實時多播應用，但是算法復雜度高。

在多播路由中，單個源節點或者多個源節點要將信息傳送給多個目的節點，若對每一個節點單獨發送數據包，則將大大浪費網絡資源，增加節點的處理負擔，這在衛星這種資源極其有限的網絡中是很不利的。另外，現有的大多數研究針對的是單層衛星的多播路由情況，主要是LEO層衛星。這些算法并不能很好地適用于多層衛星網絡，另外針對LEO/MEO/GEO三層衛星設計的多播路由算法較少。

發明內容

本發明提供一種基于最小連通支配集的衛星網絡多播路由方法及系統，以降低整個路由代價，并在路由跳數和路由代價之間取得一平衡。