基於多重性能自適應配對堆的時間演化圖路由算法

2023-06-04 18:41:31

基於多重性能自適應配對堆的時間演化圖路由算法
【專利摘要】本發明涉及一種基於多重性能自適應配對堆的時間演化圖路由算法，屬於衛星網絡路由【技術領域】，其主要技術特點是：構造一個按照通信時隙表分時隙通信的中軌道衛星網絡系統；根據24顆衛星的通信時隙表構造中軌道衛星網絡系統的時間演化圖模型；採用多重性能自適應配對堆優化迪傑斯特拉最短路徑算法的數據存儲結構；在時間演化圖模型中應用優化的迪傑斯特拉最短路徑算法計算最優路由。本發明通過優化時間演化圖路由算法的數據結構，在時間演化圖路由算法中採用多重性能自適應配對堆，並應用於分時隙通信的中軌道衛星網絡系統，網絡性能指數優於其他傳統路由算法，並且明顯降低了時間複雜度。
【專利說明】基於多重性能自適應配對堆的時間演化圖路由算法

【技術領域】
[0001] 本發明屬於衛星網絡路由【技術領域】，尤其是一種基於多重性能自適應配對堆的時 間演化圖路由算法。

【背景技術】
[0002] 近年來，隨著衛星網絡的迅速發展，通信衛星被廣泛應用於各個領域，例如軍事、 導航、定位、天氣預報、電視直播等等。根據不同的軌道高度可以將衛星網絡系統分為三種， 即低軌道（LE0)、中軌道（ΜΕ0)和高軌道（GE0)衛星網絡系統。
[0003] 單顆LE0衛星的覆蓋範圍有限，且存在衛星與用戶之間切換過於頻繁的問題。GE0 衛星也存在一些致命的缺陷，比如長距離導致延時過大，軌道資源稀缺，通信限制和巨大的 信號衰落。基於以上原因，ΜΕ0衛星可以作為GE0衛星和LE0衛星的折衷選擇。相比於GE0 衛星系統，ΜΕ0衛星系統的傳輸損耗較小，傳播延遲約為GE0的四分之一，相比於LE0衛星 系統，ΜΕ0的移動速度較慢，且由於其覆蓋範圍較大，ΜΕ0星座所需要的衛星數量較少。因 此，從某種程度上來看，ΜΕ0衛星網絡系統克服了 GE0和LE0衛星網絡系統的缺點，同時，其 服務性能、服務壽命、傳輸時延、技術和實施風險、系統複雜度和系統開銷都在可以控制在 一個合適的可以接受的範圍內。眾所周知，路由在這樣的動態拓撲通信網絡中佔有非常重 要的地位。然而，當今針對於ΜΕ0衛星網絡的路由算法仍非常缺乏。
[0004] ΜΕ0衛星網絡隨時間變化，當節點移動時，它的拓撲結構隨之改變。針對於單層衛 星網絡，現有的路由算法大致可以分為兩大類：虛擬拓撲路由算法和虛擬節點路由算法。對 於虛擬拓撲路由算法，衛星網絡的運行時間被分為若干個時隙，而其拓撲在每個時隙中被 看作固定不變的，但是這種算法對實時變化的適應性非常差，例如鏈路擁塞或者節點失效， 更糟糕的是，龐大的衛星數目使得路由表非常大且計算時間極高。對於虛擬節點路由算法， 地球的物理拓撲被虛擬節點組成的邏輯拓撲覆蓋，其用戶密度高度不均勻，且一個地區骨 當前提供服務的衛星不能提供一個很好的覆蓋，虛擬節點和真實衛星節點之間的映射並沒 有看起來那麼簡單。考慮到上述的問題以及基於分時隙通信的ΜΕ0衛星網絡系統的特點， 傳統的虛擬拓撲和虛擬節點路由算法是不適用的。它們不能滿足本發明中建立的ΜΕ0衛星 網絡系統的通信需求。
[0005] 在很多科學領域中，圖理論都有很好的應用，尤其是在分析和設計固定拓撲的網 絡路由方面。另外，時間演化圖可以從動態和暫態兩方面自然並準確地捕捉到圖中實體之 間關係的演化過程。Xuan，Ferreira和Jarry第一個研究了依據固定時間表動態變化的網 絡中的路由問題，網絡在不同時間間隔內的拓撲結構是可以預知的，他們利用了演化圖來 捕捉這樣的動態網絡的變化特徵。近期，Monteiro J，Goldman A和ArantesL應用演化圖 來評估不同的ad-hoc和DTN路由協議。在時間演化圖理論中，很多算法可以用於尋求最短 路徑，這些算法中最典型的是迪傑斯特拉算法（Dijkstra)，它可以計算出圖中兩點間的最 優路徑。Dijkstra算法中的關鍵步驟是"尋找到源節點的最小相鄰節點並從節點表中刪除 它"。然而，Dijkstra算法的問題在於，它花費了過長的時間來轉換節點表，刪除最小節點 並更新節點表。


【發明內容】

[0006] 本發明的目的在於克服現有技術的不足，提供一種設計合理、網絡性能指數優且 能夠明顯降低時間複雜度的基於多重性能自適應配對堆的時間演化圖路由算法。
[0007] 本發明解決現有的技術問題是採取以下技術方案實現的：
[0008] -種基於多重性能自適應配對堆的時間演化圖路由算法，包括以下步驟：
[0009] 步驟1、構造一個按照通信時隙表分時隙通信的中軌道衛星網絡系統；
[0010] 步驟2、根據24顆衛星的通信時隙表構造中軌道衛星網絡系統的時間演化圖模 型；
[0011] 步驟3、採用多重性能自適應配對堆優化迪傑斯特拉最短路徑算法的數據存儲結 構；
[0012] 步驟4、在時間演化圖模型中應用優化的迪傑斯特拉最短路徑算法計算最優路由。
[0013] 而且，所述步驟1構建方法為：採用STK仿真環境構造 Walker星座及其軌道模型， 利用STK仿真環境生成軌道數據信息，將軌道數據信息導入0ΡΝΕΤ應用在中軌道衛星網絡 系統中，使分時隙通信的中軌道衛星網絡系統中的24顆衛星按照其既定軌道正常運轉。
[0014] 而且，所述Walker星座為Walker-24/3/l結構星座群，每個衛星節點內配置應用 層、傳輸層、網絡層、鏈路層和物理層；每個衛星節點配置一對定向收發天線，在某一方向上 增益為200分貝，在其他方向上增益均為0;每個衛星的收發天線按照通信時隙表自動轉換 指向並與其他衛星建鏈通信。
[0015] 而且，所述步驟2的時間演化圖模型為一張給定圖的β個子圖的有序序列，每一 個子圖對應於網絡中某個時隙的網絡拓撲；每個衛星被視為網絡節點，衛星之間的連接被 視為邊，整個衛星網絡被視為一個圖，在構建時，根據通信時隙表將衛星之間連接存在的時 間間隔標註在相對應的邊上即可。
[0016] 而且，所述配對堆由配對堆節點構成，每一個節點包含隊列元素和前驅指針、左孩 子指針和右孩子指針；所述配對堆包括合併、插入、減少關鍵元素和刪除最小元素操作。
[0017] 而且，所述步驟3的具體處理過程為：
[0018] (1)初始化源節點信息並構造一個配對堆節點作為根節點，添加根節點的指針；
[0019] (2)根據根節點的信息判斷算法是否結束，如果沒有結束，遍歷當前節點的相鄰節 點並累積其開銷；如果結束，則執行步驟（5);
[0020] (3)如果相鄰節點的配對節點為空，生成一個並從相鄰節點中添加信息，隨後構造 該節點與堆節點之間的指針關係；
[0021] (4)利用當前節點的最小權重與相鄰節點來更新配對堆節點的信息，並調整堆結 構，返回步驟（2);
[0022] (5)根據最終節點的堆節點信息獲得路徑結果，並且釋放所有指針內存空間。
[0023] 而且，所述步驟（2)累積開銷按下式計算：
[0024] 開銷=Σ α ·時間+ β ·跳數+ δ ·延遲+ γ ·其它
[0025] 其中，α、β、δ、Υ分別為時間、跳數、延遲以及其它所需性能參數的權重值；所 述的權重值根據實際需要進行配置，或者根據衛星網絡運行過程中的吞吐量、擁塞、丟包 率、延遲進行自適應調整。
[0026] 而且，所述步驟4具體處理過程為：在初始化時，對源點S有最早到達時間d(s)= tMW，而對其它所有節點有d(u) =〇〇 ;此時，源點S是最小堆Q中的唯一根節點；然後，當最 小堆Q非空時，其根節點被取出並被分配給堆Q的根X，並將其刪除；接下來，如果X有一個 或者一些鄰節點，為其每一個鄰居v計算第一個有效邊的時間是否大於等於當前時間，如 果它不存在於堆Q中，將v插入堆Q ;隨後，更新d(v)及其關鍵元素；當X的所有鄰節點均 被遍歷後，更新堆Q，關閉節點X ;最後，將X插入最先到達路徑樹T中，如果堆Q中不存在任 何節點，整個算法結束，從而獲得了從源點S到其它所有節點的最先到達路徑樹T。
[0027] 本發明的優點和積極效果是：
[0028] 本發明設計合理，通過優化時間演化圖路由算法的數據結構，在時間演化圖路由 算法中採用多重性能自適應配對堆，並應用於分時隙通信的中軌道衛星網絡系統，網絡性 能指數優於其他傳統路由算法，並且明顯降低了時間複雜度，同時，當網絡節點數量大幅增 加時，應用多重性能自適應配對堆作為數據存儲結構比斐波那契堆在時間優化方面表現更 佳。

【專利附圖】

【附圖說明】
[0029] 圖1是衛星A1-A8在第1至第4時隙內的時間演化圖模型；
[0030] 圖2是本發明的多重性能自適應配對堆示意圖；
[0031] 圖3是本發明的基於多重性能自適應配對堆的迪傑斯特拉算法流程圖；
[0032] 圖4是時間演化圖中迪傑斯特拉算法流程圖；
[0033] 圖5是本發明中的路由算法與基於ATM的路由算法、基於IP的路由算法在吞吐量 方面的對比圖；
[0034] 圖6是本發明中的路由算法與基於ATM的路由算法、基於IP的路由算法在丟包率 方面的對比圖；
[0035] 圖7是傳統迪傑斯特拉算法、基於斐波那契堆的迪傑斯特拉算法與基於多重性能 自適應配對堆的迪傑斯特拉算法在平均端到端延時方面的對比圖；
[0036] 圖8是基於斐波那契堆的迪傑斯特拉算法與基於多重性能自適應配對堆的迪傑 斯特拉算法在網絡節點規模增大時的對比圖。

【具體實施方式】
[0037] 以下結合附圖對本發明實施例做進一步詳述。
[0038] 一種基於多重性能自適應配對堆的時間演化圖路由算法，包括以下步驟：
[0039] 步驟1、構造一個按照通信時隙表分時隙通信的中軌道衛星網絡系統。
[0040] 由於全球覆蓋方面步行者（Walker)星座具有其特定的優勢，因此，本發明構造 的衛星網絡模型採用Walker星座。具體來說，它由24顆ΜΕ0衛星及三個軌道面組成，每 個軌道面包含八顆衛星，所有24顆衛星形成了 Walker-24/3/l結構星座群。軌道高度為 30504. 137千米，軌道傾角為55度，離心率為0。
[0041] 具體到每個節點，每個衛星節點包含應用層、傳輸層、網絡層、鏈路層和物理層。而 且，每個衛星包含一對天線，即發射天線和接收天線。天線是定向的，在某個方向上有200dB 的增益，而在其它任何一個方向的的增益均為0。在每個時隙內，即3秒鐘內，一個衛星的發 射天線和接收天線同時指向另一個衛星，這對衛星相互通信，發送並接收數據，在接下來的 時隙中，天線的指向根據既定的時隙表發生轉換。
[0042] 應用STK仿真環境構造了 Walker星座及其軌道模型。同時，利用STK中生成的軌 道數據信息，將其導入0ΡΝΕΤ應用在ΜΕ0衛星網絡系統中，使分時隙通信的ΜΕ0衛星網絡系 統中的24顆衛星按照其既定軌道正常運轉。
[0043] 步驟2、根據24顆衛星的通信時隙表構造中軌道衛星網絡系統的時間演化圖模 型。
[0044] 圖理論是對動態網絡的一種正式的抽象。簡單地說，一個時間演化圖是一張給定 圖的β個子圖的有序序列，每一個給定序號的子圖對應於同一序號的某個時隙的網絡連 接拓撲。
[0045] 在圖模型中，衛星被視為網絡節點，衛星之間的連接被視為邊。同時，整個衛星網 絡被看作抽象意義上的一張圖。
[0046] 具體到本發明中的中軌道衛星網絡系統，根據下表所示的通信時隙表，衛星Α1-Α8 在第1至第4時隙內的時間演化過程如圖1所示，將衛星之間連接存在的時間間隔標註在 相對應的邊上。由於{Al, Α4}存在於時隙1，而{Α4, Α2}存在於時隙2,因此{Al, Α4, Α2}不 是一條有效的路徑。
[0047]

【權利要求】
1. 一種基於多重性能自適應配對堆的時間演化圖路由算法，其特徵在於包括以下步 驟： 步驟1、構造一個按照通信時隙表分時隙通信的中軌道衛星網絡系統； 步驟2、根據24顆衛星的通信時隙表構造中軌道衛星網絡系統的時間演化圖模型； 步驟3、採用多重性能自適應配對堆優化迪傑斯特拉最短路徑算法的數據存儲結構； 步驟4、在時間演化圖模型中應用優化的迪傑斯特拉最短路徑算法計算最優路由。
2. 根據權利要求1所述的基於多重性能自適應配對堆的時間演化圖路由算法，其特徵 在於：所述步驟1構建方法為：採用STK仿真環境構造 Walker星座及其軌道模型，利用STK 仿真環境生成軌道數據信息，將軌道數據信息導入OPNET應用在中軌道衛星網絡系統中， 使分時隙通信的中軌道衛星網絡系統中的24顆衛星按照其既定軌道正常運轉。
3. 根據權利要求2所述的基於多重性能自適應配對堆的時間演化圖路由算法，其特徵 在於：所述Walker星座為Walker-24/3/l結構星座群，每個衛星節點內配置應用層、傳輸 層、網絡層、鏈路層和物理層；每個衛星節點配置一對定向收發天線，在某一方向上增益為 200分貝，在其他方向上增益均為0 ;每個衛星的收發天線按照通信時隙表自動轉換指向並 與其他衛星建鏈通信。
4. 根據權利要求1所述的基於多重性能自適應配對堆的時間演化圖路由算法，其特徵 在於：所述步驟2的時間演化圖模型為一張給定圖的β個子圖的有序序列，每一個子圖對 應於網絡中某個時隙的網絡拓撲；每個衛星被視為網絡節點，衛星之間的連接被視為邊，整 個衛星網絡被視為一個圖，在構建時，根據通信時隙表將衛星之間連接存在的時間間隔標 注在相對應的邊上即可。
5. 根據權利要求1所述的基於多重性能自適應配對堆的時間演化圖路由算法，其特徵 在於：所述配對堆由配對堆節點構成，每一個節點包含隊列元素和前驅指針、左孩子指針和 右孩子指針；所述配對堆包括合併、插入、減少關鍵元素和刪除最小元素操作。
6. 根據權利要求1所述的基於多重性能自適應配對堆的時間演化圖路由算法，其特徵 在於：所述步驟3的具體處理過程為： (1) 初始化源節點信息並構造一個配對堆節點作為根節點，添加根節點的指針； (2) 根據根節點的信息判斷算法是否結束，如果沒有結束，遍歷當前節點的相鄰節點並 累積其開銷；如果結束，則執行步驟（5); (3) 如果相鄰節點的配對節點為空，生成一個並從相鄰節點中添加信息，隨後構造該節 點與堆節點之間的指針關係； (4) 利用當前節點的最小權重與相鄰節點來更新配對堆節點的信息，並調整堆結構，返 回步驟（2); (5) 根據最終節點的堆節點信息獲得路徑結果，並且釋放所有指針內存空間。
7. 根據權利要求6所述的基於多重性能自適應配對堆的時間演化圖路由算法，其特徵 在於：所述步驟（2)累積開銷按下式計算： 開銷=Σ α ·時間+β ·跳數+ δ ·延遲+ Υ ?其它 其中，α、β、δ、Υ分別為時間、跳數、延遲以及其它所需性能參數的權重值；所述的 權重值根據實際需要進行配置，或者根據衛星網絡運行過程中的吞吐量、擁塞、丟包率、延 遲進行自適應調整。
8.根據權利要求1所述的基於多重性能自適應配對堆的時間演化圖路由算法，其特徵 在於：所述步驟4具體處理過程為：在初始化時，對源點S有最早到達時間d(s) =tnOT，而對 其它所有節點有d(u) =〇〇;此時，源點S是最小堆Q中的唯一根節點；然後，當最小堆Q非 空時，其根節點被取出並被分配給堆Q的根X，並將其刪除；接下來，如果X有一個或者一些 鄰節點，為其每一個鄰居v計算第一個有效邊的時間是否大於等於當前時間，如果它不存 在於堆Q中，將v插入堆Q ;隨後，更新d (v)及其關鍵元素；當X的所有鄰節點均被遍歷後， 更新堆Q，關閉節點X ;最後，將X插入最先到達路徑樹T中，如果堆Q中不存在任何節點，整 個算法結束，從而獲得了從源點S到其它所有節點的最先到達路徑樹T。
【文檔編號】H04W40/02GK104243310SQ201410429748
【公開日】2014年12月24日 申請日期:2014年8月28日 優先權日:2014年8月28日
【發明者】劉崇華, 姜竹青, 何善寶, 李振東, 王宇鵬, 王雪暘, 黃承愷, 楊玉瑩, 劉欣萌, 李超 申請人:北京空間飛行器總體設計部, 北京郵電大學