基于時變圖的天地一體化網絡時間確定性路由算法與協議

李紅艷，張燾，張靖乾，史可懿，曾鵬程

（1.西安電子科技大學通信工程學院，陜西 西安 710071；2.中國電信福建分公司網絡運營支撐中心，福建 福州 350001)

1 引言

隨著應急通信、應急救援、導航定位、遙感遙測、國防安全、智慧城市等領域的迅速發展，天地一體化網絡在很多領域起著不可替代的作用[1]。如圖1 所示，未來天地一體化網絡將由中繼星、星座、星群、專用衛星、空間飛行器、地面站及地面用戶構成，通過一體化組網互聯，支持信息實時采集、傳輸和處理海量數據。特別地，與現有地面網絡相比，天地一體化網絡具有全球覆蓋、遠距離傳輸、不受地理環境限制、大容量等顯著優點[2]。然而，由于空間衛星不同周期的高速運動、空間與地面設備的動態加入與退出、網絡承載業務負荷隨時間的動態變化，導致天地一體化網絡拓撲和多維網絡資源（如鏈路容量、節點存儲等）具有時變性，造成網絡穩定的端到端傳輸路徑難構建、業務服務質量（QoS,quality of service）難保障、網絡資源利用率難提升[3]。此外，衛星與衛星之間、衛星與地面節點之間通信距離長，鏈路傳播時延大。例如，低軌衛星間的鏈路時延達毫秒級，遠超地面有線網絡中的節點間時延。鏈路的長時延特性造成網絡拓撲發現與維護不及時，導致過時路由產生，造成端到端數據傳輸不可達，同時用戶接入長時延也會影響端到端的時延性能保障。因此，長時延鏈路嚴重制約著組網協議的效能，導致傳統地面網絡路由協議在天地一體化網絡環境中不適用。基于此，針對鏈路長時延、資源時變的天地一體化網絡環境，亟需研究面向業務的時間確定性路由策略與協議，支持時變路由的構建、保障業務的傳輸QoS 需求、提升網絡資源的效率。

近年來，伴隨著物聯網、工業互聯網的發展需求，國內外研究機構及標準化組織紛紛啟動時間確定性網絡關鍵技術與協議的研究[4-11]。目前，在局域網領域，較成熟的時間確定性網絡技術、標準化工作正在進行；在多跳網絡領域，時間確定性網絡組網技術尚處于研究進程中。時間確定性網絡通過調度網絡資源與業務，保障業務的時延。當前，時間確定性網絡有著廣泛的應用需求，例如衛星測控網、車聯網、工業互聯網、無人機測控網、部分傳感器網絡等物聯網要求嚴格的業務時延保障；VR、AR、語音及視頻交互業務均要求較嚴格的時延。同時，IEEE 主導的以太網、第三代合作伙伴計劃（3GPP,3rd Generation Partnership Project）主導的下一代無線通信系統、美國國家航空航天局（NASA,National Aeronautics and Space Administration）主導的星載網絡均啟動了時間確定性網絡的研究工作。然而，針對時變環境的天地一化網絡時間確定性組網研究才剛開始，其主要原因在于，時變確定性組網設計面臨眾多挑戰，具體如下。

1) 資源共享與時間確定性相矛盾

由于網絡中節點（路由器或交換機）通過單跳或多跳鏈路互聯互通，路由器與鏈路采用共享模式進行信息傳輸。共享模式有效提升了鏈路資源的利用率，支撐靈活的組網模式，但是資源共享模式引入了網絡的高時變性，導致網絡的時間確定性難以保障。

圖1 天地一體化網絡示意

2) 資源表征無時間屬性，確定性路由難構建

現有的互聯網路由協議如TCP/IP，以及新興的分段路由（SR,segment routing）協議，由于路由表中缺乏時間屬性的刻畫，數據分組難以按時間進行轉發或路由，導致確定性路由難以構建。同時，天地一體化網絡中端到端路徑存在斷續連通的時變特性，穩定傳輸路徑的缺乏加劇了時間確定性路由構建的難度。

3) 多維資源未關聯，時變資源利用率低

傳統路由算法以靜態圖論為設計依據，因此在時變網絡環境中制約了資源的利用率，限制了時變網絡的吞吐量、時延等性能。如圖2 所示，假設前向鏈路與回程鏈路的容量均為50 Mbit/s。第1 秒時，回程鏈路的資源被某些業務占用，可用容量為20 Mbit/s；第2 秒時，前向鏈路的資源被某些業務占用，可用容量為20 Mbit/s。最新互聯網協議OSPFv3、RIPng 依托靜態圖論，將該網絡看作分時段的靜態網絡，則從基站到核心網節點的最大容量為20 Mbit/s。但是，若將該網絡看作時變網絡，如圖3 所示，第1 秒時，前向鏈路以滿負荷50 Mbit/s運行，其中20 Mbit/s 的業務流通過回程鏈路傳輸，其余30 Mbit/s 業務流暫存于中間節點；第2 秒時，前向鏈路以滿負荷20 Mbit/s 運行，回程鏈路以50 Mbit/s 運行，轉發來自前向鏈路及中間緩存的業務。基于此，從基站到核心網節點的容量達到35 Mbit/s，與基于靜態圖論的路由算法相比，路徑吞吐量提升了75%。由此可見，關聯利用存儲和鏈路資源，可有效提升網絡資源利用率，以及網絡對時間確定性業務的保障能力。

圖2 傳統靜態組網

實際上，時變圖理論對于時變的天地一化網絡研究具有天然優勢，包括建模的精準性以及求解的高效性[3]。這是因為時變圖通過引入時間屬性，支持時變網絡多維資源動態特性的刻畫。同時，時變圖可表征各時段網絡之間的承接關系，支持多維資源的關聯利用。然而，現有的時變圖模型及相應的時變圖求解算法均處于研究初期[12-19]，缺乏成熟的時變圖理論，難以設計高效的按需路由策略。因此，針對時變的天地一體化網絡環境，本文提出了基于時變圖的天地一體化網絡時間確定性路由算法與協議。首先，構建時變連續圖模型，實現天地一體化網絡拓撲、鏈路連通機會、鏈路帶寬、節點緩存等多維資源時空屬性的聯合刻畫；同時，給出時變路徑流守恒和鏈路容量約束等相關定義，設計鏈路的累積流量計算規則，支持具有差異化鏈路帶寬的路徑可行流計算。其次，提出面向業務的時間確定性路由算法，通過聯合考慮業務的傳輸量與開始時刻、鏈路的連通機會以及節點的存儲資源，構建面向業務的最短時延路徑，保障業務傳輸的時間確定性。再次，將所提路由算法與SR技術以及TSN 技術相結合，設計具有時延保障的時間確定性路由協議，支持時變拓撲發現、路由設計以及分組的按時轉發。最后，通過仿真實驗，驗證所提算法與協議的有效性與可行性。

圖3 時變組網

2 相關工作

2.1 時間確定性網絡發展動態

關于時間確定性網絡的研究可以追溯到20 世紀70 年代。早在1979 年，維也納技術大學（UVT,Vienna University of Technology）便提出時間觸發以太網（TTE,time-triggered ethernet）技術，旨在改變傳統以太網基于事件觸發的傳輸模式。該技術是局域網領域首個時間確定性網絡組網技術，通過調度業務的傳輸時刻，保障業務的時延[4-5]。而后，TTE技術被應用于2014 年發射的獵戶座太空船，并成為美國汽車工程師協會SAE AS6802 總線標準[6]。此外，2005 年，IEEE 802.1 任務組開始制定以太網標準音視頻橋（AVB,audio video bridging），主要應用于實時傳輸需求的音視頻領域[7]，包括IEEE 802.1D、IEEE 802.1Q、IEEE 802.1AS 等標準。2012 年，AVB工作組演進為時間敏感網絡（TSN,time sensitive network）工作組，對IEEE 802.1Q 協議進行了擴展，提升無線局域網絡對時延敏感類業務的保障能力[8]。

當前，TTE 和TSN 技術[9]成為時間確定性網絡的主要構成部分，也成為實時可靠網絡的研究熱點。國內外研究機構及標準化組織紛紛啟動時間確定性網絡關鍵技術與協議。例如，2014 年10 月互聯網工程任務組（IETF,Internet Engineering Task Force）啟動了確定性網絡（DetNet,deterministic networking）研究與標準化工作[10-11]，擬采用基于TSN 和多協議標簽交換（MPLS,multiprotocol label switching）的方案，旨在從網絡層協議設計出發，保障網絡時延。然而，DetNet 要求亞微秒級的時鐘同步，不適用互聯網等大型網絡。目前，確定性網絡仍以分時段靜態網絡為假設，網絡資源調度算法未考慮網絡的時變特征，網絡資源利用率難以提升。此外，2018 年12 月，3GPP 也發布了最新的5G 系統服務需求技術規范TS22.261，給出了自動化控制、交通物流、智慧城市、媒體娛樂等典型應用場景的服務指標（時延、可靠性、定位精度等）。可以預見，時間確定性組網設計將在未來網絡研究中扮演著越來越重要的角色。

2.2 時變圖模型與理論發展動態

一直以來，圖論都是網絡建模與求解的基礎理論工具之一[12]。時變圖模型是時變網絡資源及其關系的數學表征，也是時變網絡協議設計的理論基礎。事實上，模型的優劣主要考慮以下2 個因素：1) 精準度，即能否精準表征組網資源隨時間的變化關系及資源之間的相互制約關系；2) 高效性，包括模型所占存儲資源的大小和基于該模型分析網絡性能算法的高效性[3]。傳統靜態圖僅表征了鏈路資源及節點的連接關系，時變圖則增加對節點存儲資源、鏈路資源、節點連接關系等網絡時變特征的聯合刻畫。

圖4 離散時間的時變圖特性及演進過程

當前，時變圖模型可以分為兩大類：離散時間的時變圖模型和連續時間的時變圖模型。具體地，離散時間的時變圖模型將連續的時間范圍劃分為若干個時隙，每個時隙內存在一個相對靜止的網絡拓撲。因此，離散時間的時變圖模型是從靜態圖演變而來的，并且先后經歷了快照圖[13]、時間擴展圖[14]、時間聚合圖[15]、存儲時間聚合圖[16]的發展歷程，如圖4 所示。其中，快照圖（靜態圖序列）將時變拓撲在時間維度上進行離散化，每一個快照子圖均為靜態圖，實現動態網絡向靜態網絡的轉化。然而，快照圖割裂了快照之間的聯系，表征精準度低，造成資源浪費。同時，快照圖的快照子圖數量與時間長度成正比，存儲開銷大；基于快照圖的路由算法在所有的快照子圖內重復尋找，路由算法效率低。時間擴展圖將快照子圖中的對應節點用存儲鏈路相連，可以表征存儲?托管?轉發機制，表征精準度高；但是，當快照子圖較多、網絡規模較大時，時間擴展圖占用的存儲空間大，路由計算復雜度高。時間聚合圖將快照圖聚合到一起，用鏈路權重序列表征鏈路不同時段的權重。時間聚合圖模型不需要節點復制，通過資源的聚合表征，降低圖模型的存儲復雜度，但是缺乏對存儲資源的刻畫，圖模型表征精度低。針對現有時變圖模型面臨存儲復雜度高或表征精度低的問題，本文作者在前期工作中提出存儲時間聚合圖模型[16]。該模型融合了時間擴展圖與時間聚合圖模型的各自優勢，將時間擴展圖進行了聚合表征，在鏈路與節點處分別構建鏈路權值序列與節點存儲轉移序列，實現時變網絡時空多維資源以及分時段鏈路資源制約關系的聯合刻畫，降低了圖模型存儲復雜度，提升了圖模型的精準度和高效性，支持時變網絡最大流與路由算法的高效設計[16-17]。然而，將連續時間進行離散化處理會導致網絡時變特性的模糊化，同時劃分時隙的大小以及時隙的數量都將影響時變資源刻畫的精準度，以及相應求解算法的復雜度。另外，連續時間的時變圖模型，則是將鏈路或節點的時變特性利用時間函數來表示。然而，由于前后鏈路函數存在復雜的時間約束，導致利用時變函數難以求解時變網絡容量以及設計時變路由。

目前的時變圖模型可用于路由計算、網絡吞吐量求解以及網絡多維資源規劃，西安電子科技大學、清華大學、哈爾濱工業大學及東北大學等團隊均進行了相關研究，并發表成果[14,16-19]。但是，現有時變圖理論僅利用靜態圖、快照圖、時間擴展圖以及時間聚合圖進行時變網絡分析與求解，由于圖模型的高存儲復雜度與低精準度，導致相應算法求解復雜或無法得到全局最優解，而針對存儲時間聚合圖的高效求解算法的設計才剛剛起步，適用于時變網絡規劃、多播、穩健性設計的時變圖模型不完善或缺失，且適用于隨機時變網絡的模型也缺失。此外，針對天地一體化網絡中有限的傳輸資源對數據傳輸的約束與多樣化網絡任務的時間確定性保障需求的時間連續性表征仍然存在空白。因此，還需進一步完善時變圖模型，以降低時間確定性網絡分析與設計復雜度。

2.3 時變衛星網絡路由算法與協議

雖然天地一體化網絡尚未部署，但是近年來為了保障時變網絡環境中業務端到端的傳輸需求，許多基于圖論的時變網絡路由方法被陸續提出。例如，文獻[14]利用快照對衛星網絡的動態拓撲進行建模，提出了以最小化路徑費用為目標的動態路由算法但是，該算法僅在每個快照中計算路徑，忽略了快照間存在的可行路徑。為了提高快照的路由性能，文獻[20]增加了快照的連通性，通過重新分配星間鏈路，提升了網絡鏈路資源的利用效率。此外，文獻[21]利用事件驅動圖對衛星網絡拓撲及衛星存儲資源進行建模，并且設計了以傳輸能量消耗最小化為優化目標且滿足傳輸時延需求的路由算法。然而，事件驅動圖和空時圖均可歸屬于時間擴展圖。因此，隨著網絡規模或給定時間范圍的增加，導致該類圖模型存儲量大且相關路由算法求解復雜度高。與此同時，也有許多工作正在試圖將時延容量網絡（DTN,delay tolerant network）路由應用于衛星網絡中。例如，文獻[22]利用了存儲?托管?轉發機制來適應衛星鏈路斷續連通的特性，即當衛星沒有通信機會時，會將數據進行存儲，直到新的通信機會出現再進行相應的轉發。盡管存儲?托管?轉發機制可以提升網絡吞吐量，但是由于托管時長的不確定，因此無法保證數據的確定性時延。此外，文獻[23]分析了衛星網絡與DTN 的動態性，認為衛星網絡是典型的DTN。由于衛星的軌道和運動周期是固定且預知的，因此一些確定性的DTN 路由算法也被應用于可預測的衛星網絡。特別地，由NASA提出的接觸圖路由（CGR,contact graph routing）算法實現了時變衛星網絡拓撲的動態路由構建[24]，并且該路由算法在衛星網絡DTN 模擬器及幾個空間飛行實驗中得到了驗證[25]。實際上，CGR 是一種典型的基于中繼傳輸的路由策略，它根據路由失效時間和剩余鏈路容量來選擇最早連通的路徑。然而，現有的CGR 沒有考慮業務量等傳輸需求，同時由于衛星鏈路連通情況的時間順序，CGR不能保證大容量任務傳輸需求，并且網絡資源利用率低[17]。

在時變網絡路由協議方面，路由協議作為TCP/IP 協議棧的重要組成部分，能夠為網絡中的數據分組選擇合適的傳輸路徑，實現高效的端到端投遞。路由協議選擇的合適與否將直接影響衛星通信網絡的傳輸效率。傳統地面網絡多采用由IETF 開發開放最短路徑優先（OSPF,open shortest path first）協議[26-27]。OSPF 是一個基于鏈路狀態的路由協議，具有適用范圍廣、快速收斂、無自環和擴展性強等優勢，在互聯網中扮演了重要角色。然而，由于空間鏈路具有斷續連通、長時延、低帶寬、高誤碼等特性，傳統OSPF 協議在時變衛星網絡中會面臨鏈路狀態通告頻繁、路由重計算開銷大、路由收斂緩慢等問題，導致協議效率低下，業務QoS 難保障。為適應空間網絡的時變性，國際互聯網研究任務組（IRTF,Internet Research Task Force）的時延容忍網絡研究組（DTNRG,Delay Tolerant Networking Research Group）提出了束協議（BP,bundle protocol）[28-29]，該協議的傳輸層和應用層之間采用的存儲?托管?轉發機制能夠保障斷續連通通信環境中數據的可靠傳輸。然而，BP 在協議框架和路由算法方面仍存在不足。1) 缺乏動態拓撲發現與維護機制，網絡節點無法感知周圍節點的變化，易導致過時路由問題。2) 采用的CGR 算法未考慮業務負載和節點緩存的影響，路由結果非最優，且不能保障多業務的QoS 需求。近年來，不同種類的業務不斷涌現，對網絡提出了不同的要求，如低時延、低抖動、高帶寬和低分組丟失率等，而傳統的OSPF協議和BP 均無法保障差異化QoS 需求。在這種背景下，SR 應運而生[30]。SR 是基于源路由理念而設計的在網絡中轉發數據分組的一種協議，其根據業務需求，利用收集的網絡拓撲、帶寬利用率和時延等信息，為業務定義一條顯示路徑。路由信息通過編碼添加到數據分組頭，而網絡中的節點只需維護段信息，有助于實現業務的實時快速轉發。然而，人們對SR 的研究才剛剛起步。SR對網絡時變性的考慮不足，并且業務轉發缺乏時間屬性，存儲?托管?轉發方式和時間確定性保障面臨挑戰。

綜上所述，現有的路由算法和協議均無法高效地利用天地一體化信息網絡資源，無法保障業務的時間確定性傳輸需求，需設計適用于時變網絡環境的路由算法和協議。

3 系統模型

3.1 時變連續圖模型

天地一體化網絡是一個典型的時變網絡，同時由于衛星周期性的繞軌運動，網絡拓撲變化、鏈路容量、衛星節點的緩存大小以及運動周期等特性均具有可預測性。因此，本文針對可預測性的時變網絡環境建立系統模型。不失一般性地，假設在給定的時間范圍T內，網絡的所有狀態信息（包括拓撲信息、鏈路連通狀態以及節點存儲資源大小等）均已知。為了精準刻畫時變網絡時空多維資源，本文將天地一體化網絡中的所有物理實體如衛星、空間飛行器、地面站等均描述為節點，而物理實體之間（如衛星與衛星之間、衛星與地面站之間）的連通機會等均描述為相應的鏈路。同時，將時變的鏈路帶寬及連通機會按時間順序刻畫在對應的鏈路上，并將節點的存儲能力也表征在節點處。基于此，構建出連續時間的時變圖模型?時變連續圖（TCG,time-varying continuous graph），即TCG={V,E,T,Wu,v(t),Cu,v(T),Bufv,Nv(t)}，v∈V,(u,v)∈E,t∈T，其中，V表示節點集合，E表示星間鏈路與星地鏈路的集合，T表示給定的時間范圍，Wu,v(t)表示t時刻鏈路(u,v)的鏈路帶寬，Cu,v(T)表示在給定時間范圍T內節點u和v之間的所有連通時段集合，Bufv表示節點v的緩存大小，Nv(t)表示t時刻節點v的緩存占用情況。

為了便于理解，本文考慮一個由4 個節點構成的簡單網絡，其中節點的存儲資源有限且各鏈路的連通機會均隨時間變化。如圖5 所示，節點上利用Bufv刻畫出節點的存儲資源，而鏈路上則利用Wu,v(t)與Cu,v(T)分別刻畫出相應的鏈路帶寬與連通時段集合。例如，鏈路(S,A) 在給定時間范圍T=[t0,t5]內具有2 個連通時段（灰色條帶狀部分），因此連通時段集合CS,A(T)={[t0,t2],[t3,t4]}。特別地，為了便于描述，本文將時變連續圖中同一鏈路的不同連通時段進行按序編號，將連通時段數依次標記為，i={1,2,…,N}，其中分別表示第i個連通時段的起始和終止時刻。例如，鏈路(S,A) 的連通時段可表示為CS,A(T)=，其中和。

3.2 基于時變連續圖的相關定義及計算規則

在時變連續圖中，由于節點與鏈路均具有時間相關的約束，因此需要重新定義時變網絡中網絡流的相關約束及計算規則。首先，對于任一鏈路(u,v)∈E，將fu,v(t)定義為該鏈路的時變可行流，fu,v(t)需滿足以下幾個約束。

圖5 時變連續圖模型

1) 鏈路容量約束

本文規定鏈路(u,v)上任何時刻t∈T=[t0,th]的可行流均不能超過該鏈路對應時刻的鏈路帶寬，則有

同時，在給定的時間范圍T內，鏈路總的可行流量需小于該鏈路總的傳輸能力，即

其中，k為T=[t0,th]內鏈路(u,v)總的連通時段數。

2) 流守恒約束

對于給定的時間范圍T=[t0,th]內，流入任一節點v∈V的總數據量等于流出該節點的總數據量，即

其中，fu,v(t)和fv,u(t)分別表示在t時刻流入與流出節點v的可行流。

3) 節點緩存約束

對于任一時刻τ∈T，節點v的緩存占用情況Nv(τ)受限于該節點的緩存Bufv，以及流入與流出節點v的累積可行流，可描述為

此外，對于任意給定的業務M，需要根據業務量大小D(M)、業務傳輸開始時刻tstart(M)和終止時刻tend(M)，確定業務數據在端到端傳輸過程中對路徑上所有鏈路連通時段以及節點存儲的占用情況。因此，針對時變連續圖中端到端的單跳與多跳時變路徑，設計相應的鏈路累積流量及路徑累積流量計算規則，具體如下。

1) 面向業務的鏈路累積流量計算

對于單跳的時變路徑，可根據業務傳輸需求以及該鏈路的鏈路帶寬與連通時段集合，確定該鏈路用于數據傳輸的有效連通時段。不失一般性地，假設單跳的時變路徑為鏈路(A,B)∈E，鏈路連通時段集合為，如圖6 所示，具體計算規則如下。

①確定鏈路(A,B)有效連通時段的開始時刻

圖6 鏈路累積流量計算

② 確定鏈路(A,B)有效連通時段的終止時刻

在業務規定的傳輸時間范圍內，業務量與時變鏈路可行流需滿足如式(5)和式(6)所示關系。

2) 面向業務的路徑累積流量計算

對于多跳類時變路徑，需根據業務傳輸需求進行逐跳的鏈路計算，依次確定鏈路的有效連通時段，最終得到面向業務的路徑累積流量。為了便于描述，如圖7 所示，本文以兩跳類路徑(A,B,C)為例，介紹路徑累積流量的計算規則。

圖7 路徑累積流量計算

不失一般性地，上述介紹的兩跳類路徑計算規則也適于多跳類路徑計算。其核心思想在于需依次利用前一跳鏈路的有效連通時段計算后一跳鏈路的有效連通時段，最后得到面向業務的端到端路徑中節點與鏈路資源的占用情況，實現時變資源的按需分配。

4 面向業務的時間確定性路由方法

在時變的天地一體化網絡中，構建具有時間屬性的時變路由策略是保障業務端到端QoS 需求的關鍵。因此，基于所構建的時變連續圖模型以及設計的時變可行流約束與計算規則，本文進一步提出面向業務的時間確定性路由算法，如算法1 所示，該算法通過聯合考慮業務的傳輸量與開始時刻，鏈路的連通機會以及節點的存儲資源，借助鏈路累積流量計算規則，構建面向業務的最短時延路徑，從而保障業務傳輸的時間確定性。

算法1面向業務的時間確定性路由算法

輸入時變連續圖TCG={(V,E,T,Wu,v(t),Cu,v(T),Bufv,Nv(t))|v∈V,(u,v)∈E,t∈T}，給定的業務M，包括業務量大小D(M)、業務傳輸開始時刻tstart(M)、終止時刻tend(M)以及傳輸的源點S與目的點D

輸出從S到D的端到端時變路徑Path(M)，滿足M傳輸需求且具有確定性時延保障

步驟1每個節點v∈V均設置2 個路由參數c[v]與p[v]，其中c[v]表示將業務量D(M)從源點S傳輸到節點v的最早完成時間，p[v]表示路由過程中節點v的前一跳節點，同時將其初始化為c[v]=∞，p[v]=?1（?1 表示該節點沒有前一跳）。

步驟2配置節點S的節點費用c[S]=tstart(M)以及前一跳節點p[S]=?1，并將節點S加入節點隊列Q中，Q←S。

步驟3判斷隊列Q是否為空集，若Q為空集，跳轉至步驟7；否則，執行步驟4。

步驟4從Q中取出節點費用最小的節點u作為當前的找路節點，同時更新隊列Q←Q?u。

步驟5當節點u=S時，利用面向業務的鏈路累積流量計算規則，計算出節點u所有鄰接鏈路(u,v)的有效連通時段；當節點u≠S時，利用面向業務的路徑累積流量計算規則，根據鏈路(p[u],u)的有效鏈路時段以及節點u的緩存能力Bufu，計算出節點u所有鄰接鏈路(u,v)的有效連通時段。

步驟6利用鏈路(u,v)的終止時刻對鄰接節點v的節點費用c[v]進行更新（如果，則更新c[v]=且p[v]=u），并把節點v加入隊列Q，并跳轉至步驟3。

步驟7判斷目的點D的節點費用大小，若c[D]=∞，則表示任務M不存在從S到D的有效路徑，終止算法；否則，執行步驟8。

步驟 8從D開始，依次利用前一跳節點p[D]，獲得從S到D的路徑Path(M)，并記錄下路徑中各鏈路的有效連通時段。

為了便于理解，本文給出一個算法實例來描述路由算法的執行過程，如圖8 所示。具體地，在圖8(a)中，假設給定業務M的業務量為2 個單位數據，業務傳輸時刻為t0，要求從節點S傳輸到節點D；同時，網絡的鏈路連通時段隨時間變化，且每個時隙[ti,ti+1]內鏈路的傳輸能力為1 個單位數據。為了保障業務的端到端傳輸，所提路由算法的計算過程如下。首先，如圖8(b)所示，選擇節點S作為當前節點，并根據業務的傳輸開始時間t0，更新節點S的節點費用c[S]=t0和前一跳節點p[S]=?1，同時，利用面向業務的鏈路累積流量計算規則，計算出節點S的所有鄰接鏈路(S,A) 和(S,B)的有效連通時段，并基于有效連通時段的截止時刻對鄰接節點A和B進行節點費用與前一跳節點的更新；然后，如圖8(c)所示，選擇具有最早傳輸完成時間的節點A作為新的當前節點，利用面向業務的路徑累積流量計算規則，根據鏈路(S,A) 的有效連通時段，確定節點A所有鄰接鏈路(A,B)和(A,D)的有效連通時段，并且更新鄰接節點D和B的節點費用與前一跳節點；然后，如圖8(d)所示，繼續選擇具有最早傳輸完成時間的節點B作為新的當前節點，根據鏈路(A,B)的有效連通時段，計算鏈路(B,D)的有效連通時段；最后，如圖8(e)所示，根據節點D的前一跳節點p[D]，依次回溯，最終得到從S到D的時變路徑，即路徑（S?A?B?D）。同時，利用路徑（S?A?B?D）中各節點的節點費用以及鏈路的有效連通時段，可以實現網絡資源的按時分配與調度，滿足端到端業務的時間確定性傳輸。

圖8 面向業務的時間確定性路由算法實例

5 時間確定性路由協議

基于時變圖的時間確定性路由算法可為不同業務規劃出滿足傳輸需求的時變路徑，但為了保障業務傳輸的時間確定性，還需相應協議作為支撐。因此，本文針對天地一體化網絡的時變環境，提出時間確定性路由協議及協議棧模型，如圖9 所示。該模型在傳統TCP/IP 協議棧的基礎上對網絡層協議進行擴展，增加了時間確定性路由協議，包括自適應拓撲發現與維護機制和基于時變圖的多業務時間確定性路由算法，為業務傳輸規劃出滿足時延需求的時變路徑。此外，為對每類業務進行精準傳輸和托管控制，本文將路由協議與SRv6 協議相結合，提出基于SR 的時間觸發分組轉發機制，實現不同業務按不同顯式路徑高效傳輸，保障時間確定性。

圖9 天地一體化網絡節點協議棧模型

1) 自適應拓撲發現與維護機制

拓撲發現是路由計算的基礎，因此及時、準確地獲取網絡拓撲和可用資源等信息是時間確定性路由構建的關鍵。天地一體化網絡中節點的移動性、資源的共享性以及節點的動態加入和退出導致網絡拓撲頻繁變化，傳統的基于固定周期的拓撲發現機制面臨問題。拓撲發現周期越短，拓撲信息的準確性越高，但信令負荷重，制約路由算法的性能。若拓撲發現周期過長，則對于突發情況導致的拓撲變化發現不及時，易產生過時路由，導致分組丟失，且重路由將帶來額外的開銷。基于此，考慮到天地一體化網絡拓撲變化具有一定的可預測性，將周期性拓撲發現與基于拓撲預測的拓撲發現和基于主動探測的拓撲發現相結合，提出自適應的拓撲發現與維護機制，在保障拓撲信息及時、準確的同時降低信令負荷。

如圖10(a)所示，以時間T為周期發送Hello 分組進行拓撲探測。若依據節點的運行軌跡、速度和時間等信息預測拓撲的變化，在有鏈路斷開或連通的時刻發送Hello 分組，而在其余時刻按照大于T的周期進行拓撲探測和維護，則能夠有效降低開銷，如圖10(b)所示。對于由故障等原因引起的難以預測的拓撲變化，則由事件觸發，主動發送Hello分組進行探測，保障拓撲信息的及時性，如圖10(c)所示。

通過自適應拓撲發現與維護機制，能夠動態獲取天地一體化網絡的拓撲和可用資源等信息，作為多業務時間確定性路由算法的輸入，計算出確定性時延的時變路徑，并轉化為具有時間屬性的路由表，即包含每跳傳輸的開始和終止時刻。協議中各模塊的關系如圖11 所示。

2) 基于SR 的時間觸發分組轉發機制

借鑒TSN 技術允許周期性與非周期性數據在同一網絡中共同傳輸的思想，本文將業務分組分為時間確定性業務分組與普通業務分組（普通業務無時延保障），利用時間觸發機制實現分組轉發。特別地，對于時間確定性業務的分組，本文進一步融合了SR 技術對分組進行路由轉發。具體來說，依據構建出的時變路由表，將路由信息添加至分組頭部。此外，為了精準控制分組的傳輸，還添加了轉發的開始和結束時刻。當網絡節點轉發分組時，將優先識別分組頭部的路由信息，獲取下一跳節點，并由時間觸發，執行轉發流程，直到將分組投遞至目的節點。若需要在節點進行托管，則根據路由表信息設置定時器，在定時器超時后再傳輸數據。對于沒有嚴格的時延保障要求的普通業務，在不影響時間確定性業務傳輸的前提下，按照統一計算出的路由表，通過IPv6 流程實現分組的存儲?托管?轉發。

6 仿真與評估

為了驗證面向業務的時間確定性路由算法的有效性與可行性，本文將所提算法（記為TCG-based）與CGR 算法[24]和基于快照圖的路由算法[26-27]（記為snapshot-based）進行比較，并對仿真結果進行了分析與討論。

1) 仿真場景及參數設置

本文考慮一個由32 顆低軌衛星和3 個地面站構成的衛星網絡場景。其中，低軌衛星均取自Walker 星座，包含4 個軌道面（軌道高度為700 km，傾角為86°）且每個軌道面均勻分布8 顆衛星。地面站分別設在北京（東經116°20′、北緯39°56′）、酒泉（東經100°17′、北緯40°57′）和三亞（東經109°50′、北緯18°25′）。本文利用衛星工具包（STK,satellite tool kit）獲取網絡的真實連通情況，即網絡的時變拓撲，仿真時間段為2020 年6 月5 日00:00—12:00。此外，在32 顆低軌衛星和3 個地面站中隨機選定10 組源/匯節點對，且源節點的業務到達均服從泊松過程。特別地，每個業務的大小設定為30 MB，業務總數為400 個。初始時，設定每條傳輸鏈路的可用帶寬為300 Mbit/s，每顆衛星的可用存儲資源為100 MB。

圖10 自適應拓撲發現與維護機制

圖11 時間確定性路由與轉發協議中各模塊的關系

為了分析與評估算法性能，考慮如下3 項指標。

2) 仿真結果與分析

圖12 給出3 種路由算法的端到端時延對比。從圖12 可以看出，snapshot-based 算法的端到端時延最低，但是點數最少（即完成的業務數最少），其背后的原因在于，該算法僅在單獨的快照圖內搜索端到端路徑，不支持跨時段數據傳輸，所求路徑的跳數少、時延低。然而，當快照內不存在端到端路徑時，業務無法傳輸。TCG-based 算法與CGR 算法的端到端時延性能基本一致，由于均采用存儲?托管?轉發方式，時延略高于snapshot-based 算法。此外，TCG-based 算法比CGR 算法能夠完成更多的業務，原因是該算法選路時考慮到節點緩存限制，規避掉了緩存溢出節點。

3種路由算法的鏈路資源利用率對比如圖13所示。從圖13 中可以看出，TCG-based 算法的鏈路資源利用率最高，CGR 算法次之，而snapshot-based算法最低。該現象可以解釋為snapshot-based 算法無法聯合利用不同時段的網絡鏈路資源，而TCG-based 算法與CGR 算法借助節點緩存資源存儲?托管?轉發機制，能夠構建時變傳輸路徑，實現不同時段空閑資源的高效利用。此外，由于CGR算法在路徑計算時未考慮節點緩存限制，可能產生部分無效路徑，導致鏈路資源利用率低于TCGbased 算法。

圖12 3 種路由算法的端到端時延對比

圖13 3 種路由算法的鏈路資源利用率對比

圖14 給出了3 種路由算法的分組投遞率對比。從圖14 可以看出，snapshot-based 算法能夠成功傳輸的業務分組最少，原因是在衛星網絡環境中，由于拓撲斷續連通，單個快照內難以構建出端到端路徑，業務分組無法傳輸到目的節點，導致投遞率低。TCG-based 算法和CGR 算法均支持跨時段數據傳輸，在給定時間范圍內能夠到達目的節點的業務分組多。此外，由于TCG-based 算法考慮了節點緩存約束，避免由緩存溢出導致的分組丟失，因此投遞率更高。

7 結束語

圖14 3 種路由算法的分組投遞率對比

本文圍繞著天地一體化網絡中業務端到端傳輸的路由問題，提出基于時變圖的天地一體化網絡時間確定性路由算法及協議。首先，通過構建時變連續圖模型，實現天地一體化網絡時刻多維資源的精準刻畫；然后，提出面向業務的時間確定性路由算法，利用面向業務的時變鏈路累積流量計算規則，構建時變按需的最短時延路徑；最后，進一步設計了具有時延保障的時間確定性路由協議，支持斷續連通的時變網絡環境中拓撲的動態發現、確定性路由的高效計算以及數據分組的定時轉發。仿真結果表明，所提路由算法通過利用節點存儲資源，有效地提升了時變鏈路資源利用率，保障了業務在時變環境下的端到端傳輸需求。