[發明專利]基于動態區間限定的DTN網絡最短時延路由方法

有效

• 申請號: 201910565211.2
• 申請日: 2019-06-27
• 公開（公告）號: CN110233797B
• 公開（公告）日: 2020-08-25
• 發明（設計）人: 劉勤;龍秋云;黃鵬宇;遲凱;李紅艷
• 申請（專利權）人: 西安電子科技大學;中國電子科技集團公司第二十研究所
• 主分類號: H04L12/727
• 分類號: H04L12/727
• 代理公司: 陜西電子工業專利中心 61205
• 代理人: 田文英;王品華

本發明公開了一種基于動態區間限定的時延容忍網絡最短時延路由方法，解決了現有技術存儲量大，存在大量冗余計算的問題。本發明的實現步驟是，首先構建離散時間聚合圖，通過節點到達時間序列轉換將離散時間聚合圖中所有的鏈路傳輸時延序列轉換為節點到達時間序列。根據鏈路的節點到達時間序列與對應時刻間的關系確定動態區間限定條件，根據該條件計算固定起始時間下節點間的最短時延路由。本發明有效的節省了方法執行的存儲需求，減少了大量的冗余計算，降低了時延容忍網絡的通信開銷。

技術領域

本發明屬于通信技術領域，更進一步涉及網絡通信技術領域中的一種基于動態區間限定的時延容忍網絡DTN(Delay-Tolerant NetWorks)最短時延路由方法。本發明能夠在時延容忍網絡DTN中選取一條端到端傳輸的最短時延路由，保證信息傳輸的高效性。

背景技術

時延容忍網絡DTN是一種新型的自組織網絡，由于能在端到端往返時延長、連接頻繁中斷等網絡受限條件下進行通信，所以在軍事、交通、災難救援等領域具有廣泛的應用前景。與傳統通信網絡相比，時延容忍網絡DTN沒有穩定的端到端傳輸路徑，傳統通信網絡中的路由算法不能直接應用到時延容忍網絡DTN中。所以，研究有效可靠的路由技術成為時延容忍網絡DTN中的關鍵問題。

哈爾濱工業大學深圳研究生院在其申請的專利文獻“衛星DTN網絡的時間擴散性路由搜尋方法”(專利申請號201510677212.8，申請公布號CN 105245451A)中公開了一種基于時間擴展的DTN網絡路由搜尋方法。該方法將時變網絡的所有信息存儲在時間擴展圖中，基于時間擴展圖搜尋直接連通的端到端路徑和依靠間斷鏈路進行通信的路徑，并進行量化分析。該方法存在的不足之處是，使用時間擴展圖存儲時變網絡信息，會出現存儲量大、存在冗余節點，以及重復計算等問題，加大了網絡的通信開銷。

Gunturi V,Shekhar S,Yang K S在在其發表的論文“A Critical-Time-PointApproach to All-Departure-Time Lagrangian Shortest Paths”(IEEE Transactionson Knowledge and Data Engineering,2015,27(10)：2591-2603)中提出了一種基于關鍵時間點的最短路由方法CTAS(Critical Time-point based ALSP Solver)。該方法采用離散時間聚合圖進行建模，首先將鏈路的傳輸時延序列轉換為節點到達時間序列，通過不同鏈路節點到達時間序列間的相對變化確定關鍵時間點，通過關鍵時間點和到達時間序列計算不同開始時間下源節點到目的節點的最短路徑。該方法存在的不足之處是，直接基于節點到達時間序列計算最短路徑，未進行任何處理，導致方法執行的計算復雜度增大，加大了網絡的通信開銷。

發明內容

本發明的目的在于針對上述現有技術的不足，提出了一種基于動態區間限定的時延容忍網絡DTN最短時延路由方法，通過離散時間聚合圖存儲時變網絡信息，由于離散時間聚合圖是以序列的形式表示和存儲時變的鏈路信息，故節省了存儲空間，降低了方法的計算復雜度；通過動態區間限定計算節點間的最短時延路由，減少了大量冗余計算，有效降低網絡開銷。

本發明實現上述目的的具體思路是：根據時延容忍網絡DTN拓撲結構和鏈路狀態的變化，構造離散時間聚合圖。然后通過節點到達時間序列轉換將離散時間聚合圖中所有的鏈路傳輸時延序列轉換為節點到達時間序列。考慮節點到達時間序列與對應時刻的關系，得到動態區間限定條件，根據該條件計算固定起始時間下節點間的最短時延路由。

本發明實現上述目的的步驟包括如下：

(1)構造離散時間聚合圖：

(1a)將時延容忍網絡DTN中的所有節點組成一個節點集合；

(1b)節點集合中每兩個節點間若存在鏈路，將該鏈路在每秒時刻的所有傳輸時延，組成一個鏈路傳輸時延序列；