[發明專利]時變網絡中定長隨機中斷場景最大錯誤分離路徑獲取方法

有效

• 申請號: 202110862161.1
• 申請日: 2021-07-29
• 公開（公告）號: CN113630268B
• 公開（公告）日: 2022-07-26
• 發明（設計）人: 趙聞博;王登峰;焦仲科;張攀;張華
• 申請（專利權）人: 西安電子科技大學;西安空間無線電技術研究所
• 主分類號: H04L41/142
• 分類號: H04L41/142;H04L41/14
• 代理公司: 西安長和專利代理有限公司 61227
• 代理人: 黃偉洪

本發明屬于網絡技術領域，公開了一種時變網絡中定長隨機中斷場景最大錯誤分離路徑獲取方法，搜索出源到匯的所有路徑，再為每條路徑計算沖突邊集，將對應的沖突邊集有交集的兩條路徑視為沖突路徑；對沖突路徑采用貪心的策略，從空集開始，不斷的以迭代的方式擴充一個路徑集合，在每次迭代中選擇權重最小的新的路徑，對選出的權重最小路徑和當前該集合中所有路徑不沖突，則將新路徑并入集合，構造出在時間上保持一定安全距離的最大的空間分離路徑。本發明有效提高了從源到匯的發送數據的成功率。本發明在問題建模的過程中，本發明還從經濟性的角度，考慮了總通信開銷的限定，確保所求得的路徑集合是滿足成本限制的最大集合。

技術領域

本發明屬于網絡技術領域，尤其涉及一種時變網絡中定長隨機中斷場景最大錯誤分離路徑獲取方法，具體涉及一種帶權時變網絡在定長隨機中斷下的最大錯誤分離路徑的啟發式構造方法。

背景技術

目前，在時變網絡的許多應用中，傳輸可靠性分析能夠預估網絡對錯誤的抵抗力，從而為改善網絡傳輸性能提供理論基礎和指導。例如，保證在空間通信中交換緊急信息的衛星網絡的傳輸可靠性至關重要。但是，由于兩種不同形式的中斷導致網絡拓撲不斷變化，時變網絡特別容易受到攻擊。

第一種類型的中斷被稱為固有中斷，這源自網絡的固有特性。例如，移動網絡中手機攜帶者周期性移動；公路交通網中的車輛在每天特定時間段內發車；衛星網中通信衛星在軌道上周期性運動等。這類中斷具有規律性，鏈接的變化可提前預知。第二類中斷表現為外在的和具有不可預測性，被稱為隨機中斷。例如，關于網絡拓撲演變的預測本身出錯，或是由于意外的物理遮擋、硬件故障和自然災害等種種不可預見的因素導致的鏈接或節點出錯。不可預測的中斷會大大降低網絡性能，而隨機性的引入，也會進一步增加網絡建模和在理論上進行可靠性分析的難度。

時變圖對于具有動態連通性的網絡(如車輛網絡)是一種有用的模型，然而，盡管它們具有強大的建模能力，但時變圖的許多重要特征仍未得到很好的理解。在研究時變圖基本性質方面存在大量工作，諸如連通性、距離、組合性質等。但是，對于時變圖魯棒特性的研究的工作很少。傳統的靜態網絡是通過研究網絡的最小割集，來度量網絡在面對數次中斷后依然能夠保持連通的能力。不幸的是，這種度量方法在時變網絡中是完全無效的。這是因為時變網絡在不同時刻有著不同的拓撲，而網絡中斷的時間非常長，它的連通性必須在更長的時間間隔內來測量。為了考慮時變網絡中的可靠傳輸問題，就必須關注故障的時間特性，即故障發生的時刻和該故障持續的時間。已有工作研究基于隨機時變圖的魯棒性，在關注確定性時變圖這方面的現有工作中，并未充分考慮故障的時間特性，也沒有精確刻畫時變網中通信特點。一些工作假設每個鏈路僅僅在一個時間切片中處于活動狀態，并且網絡中只發生永久性的故障，顯然這些假設并不符合實際情況。

已有工作通過計算最大獨立路徑來反應網絡本身魯棒特性，未考慮網絡中邊上的權重和傳輸成本的限制。

通過上述分析，現有技術存在的問題及缺陷為：

(1)有關時變圖魯棒特性的研究的工作很少。傳統靜態網中，往往通過找尋節點分離路徑或者邊分離路徑來增強魯棒性，而這種方法在時變網中不適用。這是因為，靜態網中的鏈路中斷是永久的，時變網中連接故障后之后隨著拓撲本身的變化，該連接可能會重現，而連接的稀疏性，使得在物理上完全分離的節點/邊分離路徑并不存在。

(2)時變網絡魯棒性的研究著眼于隨機時變圖，而本發明關注的是確定性時變圖。

(3)有關確定性時變圖魯棒性的工作，采用了不恰當的假設，未充分考慮故障的時間特性，也沒有精確刻畫時變網中通信特點，并不符合實際情況。這些假設包括：每個鏈路僅僅在一個時間切片中處于活動狀態，并且網絡中只發生永久性的故障等。

(4)現有技術考慮了在網絡中進行多重備份路由來降低端到端的丟包率，但是現有技術頁沒有合理的控制備份路徑的權重和以滿足通信耗費的限制，造成通信成本增加。

(5)現有技術的路徑計算方法在迭代中反復構造線型圖，對一些不發生變化的信息重復計算，復雜度太高。