基于時(shí)變圖的天地一體化網(wǎng)絡(luò)時(shí)間確定性路由算法與協(xié)議

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

（1.西安電子科技大學(xué)通信工程學(xué)院，陜西 西安 710071；2.中國(guó)電信福建分公司網(wǎng)絡(luò)運(yùn)營(yíng)支撐中心，福建 福州 350001)

1 引言

隨著應(yīng)急通信、應(yīng)急救援、導(dǎo)航定位、遙感遙測(cè)、國(guó)防安全、智慧城市等領(lǐng)域的迅速發(fā)展，天地一體化網(wǎng)絡(luò)在很多領(lǐng)域起著不可替代的作用[1]。如圖1 所示，未來(lái)天地一體化網(wǎng)絡(luò)將由中繼星、星座、星群、專用衛(wèi)星、空間飛行器、地面站及地面用戶構(gòu)成，通過(guò)一體化組網(wǎng)互聯(lián)，支持信息實(shí)時(shí)采集、傳輸和處理海量數(shù)據(jù)。特別地，與現(xiàn)有地面網(wǎng)絡(luò)相比，天地一體化網(wǎng)絡(luò)具有全球覆蓋、遠(yuǎn)距離傳輸、不受地理環(huán)境限制、大容量等顯著優(yōu)點(diǎn)[2]。然而，由于空間衛(wèi)星不同周期的高速運(yùn)動(dòng)、空間與地面設(shè)備的動(dòng)態(tài)加入與退出、網(wǎng)絡(luò)承載業(yè)務(wù)負(fù)荷隨時(shí)間的動(dòng)態(tài)變化，導(dǎo)致天地一體化網(wǎng)絡(luò)拓?fù)浜投嗑S網(wǎng)絡(luò)資源（如鏈路容量、節(jié)點(diǎn)存儲(chǔ)等）具有時(shí)變性，造成網(wǎng)絡(luò)穩(wěn)定的端到端傳輸路徑難構(gòu)建、業(yè)務(wù)服務(wù)質(zhì)量（QoS,quality of service）難保障、網(wǎng)絡(luò)資源利用率難提升[3]。此外，衛(wèi)星與衛(wèi)星之間、衛(wèi)星與地面節(jié)點(diǎn)之間通信距離長(zhǎng)，鏈路傳播時(shí)延大。例如，低軌衛(wèi)星間的鏈路時(shí)延達(dá)毫秒級(jí)，遠(yuǎn)超地面有線網(wǎng)絡(luò)中的節(jié)點(diǎn)間時(shí)延。鏈路的長(zhǎng)時(shí)延特性造成網(wǎng)絡(luò)拓?fù)浒l(fā)現(xiàn)與維護(hù)不及時(shí)，導(dǎo)致過(guò)時(shí)路由產(chǎn)生，造成端到端數(shù)據(jù)傳輸不可達(dá)，同時(shí)用戶接入長(zhǎng)時(shí)延也會(huì)影響端到端的時(shí)延性能保障。因此，長(zhǎng)時(shí)延鏈路嚴(yán)重制約著組網(wǎng)協(xié)議的效能，導(dǎo)致傳統(tǒng)地面網(wǎng)絡(luò)路由協(xié)議在天地一體化網(wǎng)絡(luò)環(huán)境中不適用?；诖?，針對(duì)鏈路長(zhǎng)時(shí)延、資源時(shí)變的天地一體化網(wǎng)絡(luò)環(huán)境，亟需研究面向業(yè)務(wù)的時(shí)間確定性路由策略與協(xié)議，支持時(shí)變路由的構(gòu)建、保障業(yè)務(wù)的傳輸QoS 需求、提升網(wǎng)絡(luò)資源的效率。

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

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

由于網(wǎng)絡(luò)中節(jié)點(diǎn)（路由器或交換機(jī)）通過(guò)單跳或多跳鏈路互聯(lián)互通，路由器與鏈路采用共享模式進(jìn)行信息傳輸。共享模式有效提升了鏈路資源的利用率，支撐靈活的組網(wǎng)模式，但是資源共享模式引入了網(wǎng)絡(luò)的高時(shí)變性，導(dǎo)致網(wǎng)絡(luò)的時(shí)間確定性難以保障。

圖1 天地一體化網(wǎng)絡(luò)示意

2) 資源表征無(wú)時(shí)間屬性，確定性路由難構(gòu)建

現(xiàn)有的互聯(lián)網(wǎng)路由協(xié)議如TCP/IP，以及新興的分段路由（SR,segment routing）協(xié)議，由于路由表中缺乏時(shí)間屬性的刻畫，數(shù)據(jù)分組難以按時(shí)間進(jìn)行轉(zhuǎn)發(fā)或路由，導(dǎo)致確定性路由難以構(gòu)建。同時(shí)，天地一體化網(wǎng)絡(luò)中端到端路徑存在斷續(xù)連通的時(shí)變特性，穩(wěn)定傳輸路徑的缺乏加劇了時(shí)間確定性路由構(gòu)建的難度。

3) 多維資源未關(guān)聯(lián)，時(shí)變資源利用率低

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

圖2 傳統(tǒng)靜態(tài)組網(wǎng)

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

圖3 時(shí)變組網(wǎng)

2 相關(guān)工作

2.1 時(shí)間確定性網(wǎng)絡(luò)發(fā)展動(dòng)態(tài)

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

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

2.2 時(shí)變圖模型與理論發(fā)展動(dòng)態(tài)

一直以來(lái)，圖論都是網(wǎng)絡(luò)建模與求解的基礎(chǔ)理論工具之一[12]。時(shí)變圖模型是時(shí)變網(wǎng)絡(luò)資源及其關(guān)系的數(shù)學(xué)表征，也是時(shí)變網(wǎng)絡(luò)協(xié)議設(shè)計(jì)的理論基礎(chǔ)。事實(shí)上，模型的優(yōu)劣主要考慮以下2 個(gè)因素：1) 精準(zhǔn)度，即能否精準(zhǔn)表征組網(wǎng)資源隨時(shí)間的變化關(guān)系及資源之間的相互制約關(guān)系；2) 高效性，包括模型所占存儲(chǔ)資源的大小和基于該模型分析網(wǎng)絡(luò)性能算法的高效性[3]。傳統(tǒng)靜態(tài)圖僅表征了鏈路資源及節(jié)點(diǎn)的連接關(guān)系，時(shí)變圖則增加對(duì)節(jié)點(diǎn)存儲(chǔ)資源、鏈路資源、節(jié)點(diǎn)連接關(guān)系等網(wǎng)絡(luò)時(shí)變特征的聯(lián)合刻畫。

圖4 離散時(shí)間的時(shí)變圖特性及演進(jìn)過(guò)程

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

目前的時(shí)變圖模型可用于路由計(jì)算、網(wǎng)絡(luò)吞吐量求解以及網(wǎng)絡(luò)多維資源規(guī)劃，西安電子科技大學(xué)、清華大學(xué)、哈爾濱工業(yè)大學(xué)及東北大學(xué)等團(tuán)隊(duì)均進(jìn)行了相關(guān)研究，并發(fā)表成果[14,16-19]。但是，現(xiàn)有時(shí)變圖理論僅利用靜態(tài)圖、快照?qǐng)D、時(shí)間擴(kuò)展圖以及時(shí)間聚合圖進(jìn)行時(shí)變網(wǎng)絡(luò)分析與求解，由于圖模型的高存儲(chǔ)復(fù)雜度與低精準(zhǔn)度，導(dǎo)致相應(yīng)算法求解復(fù)雜或無(wú)法得到全局最優(yōu)解，而針對(duì)存儲(chǔ)時(shí)間聚合圖的高效求解算法的設(shè)計(jì)才剛剛起步，適用于時(shí)變網(wǎng)絡(luò)規(guī)劃、多播、穩(wěn)健性設(shè)計(jì)的時(shí)變圖模型不完善或缺失，且適用于隨機(jī)時(shí)變網(wǎng)絡(luò)的模型也缺失。此外，針對(duì)天地一體化網(wǎng)絡(luò)中有限的傳輸資源對(duì)數(shù)據(jù)傳輸?shù)募s束與多樣化網(wǎng)絡(luò)任務(wù)的時(shí)間確定性保障需求的時(shí)間連續(xù)性表征仍然存在空白。因此，還需進(jìn)一步完善時(shí)變圖模型，以降低時(shí)間確定性網(wǎng)絡(luò)分析與設(shè)計(jì)復(fù)雜度。

2.3 時(shí)變衛(wèi)星網(wǎng)絡(luò)路由算法與協(xié)議

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

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

綜上所述，現(xiàn)有的路由算法和協(xié)議均無(wú)法高效地利用天地一體化信息網(wǎng)絡(luò)資源，無(wú)法保障業(yè)務(wù)的時(shí)間確定性傳輸需求，需設(shè)計(jì)適用于時(shí)變網(wǎng)絡(luò)環(huán)境的路由算法和協(xié)議。

3 系統(tǒng)模型

3.1 時(shí)變連續(xù)圖模型

天地一體化網(wǎng)絡(luò)是一個(gè)典型的時(shí)變網(wǎng)絡(luò)，同時(shí)由于衛(wèi)星周期性的繞軌運(yùn)動(dòng)，網(wǎng)絡(luò)拓?fù)渥兓㈡溌啡萘?、衛(wèi)星節(jié)點(diǎn)的緩存大小以及運(yùn)動(dòng)周期等特性均具有可預(yù)測(cè)性。因此，本文針對(duì)可預(yù)測(cè)性的時(shí)變網(wǎng)絡(luò)環(huán)境建立系統(tǒng)模型。不失一般性地，假設(shè)在給定的時(shí)間范圍T內(nèi)，網(wǎng)絡(luò)的所有狀態(tài)信息（包括拓?fù)湫畔ⅰ㈡溌愤B通狀態(tài)以及節(jié)點(diǎn)存儲(chǔ)資源大小等）均已知。為了精準(zhǔn)刻畫時(shí)變網(wǎng)絡(luò)時(shí)空多維資源，本文將天地一體化網(wǎng)絡(luò)中的所有物理實(shí)體如衛(wèi)星、空間飛行器、地面站等均描述為節(jié)點(diǎn)，而物理實(shí)體之間（如衛(wèi)星與衛(wèi)星之間、衛(wèi)星與地面站之間）的連通機(jī)會(huì)等均描述為相應(yīng)的鏈路。同時(shí)，將時(shí)變的鏈路帶寬及連通機(jī)會(huì)按時(shí)間順序刻畫在對(duì)應(yīng)的鏈路上，并將節(jié)點(diǎn)的存儲(chǔ)能力也表征在節(jié)點(diǎn)處?；诖?，構(gòu)建出連續(xù)時(shí)間的時(shí)變圖模型?時(shí)變連續(xù)圖（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表示節(jié)點(diǎn)集合，E表示星間鏈路與星地鏈路的集合，T表示給定的時(shí)間范圍，Wu,v(t)表示t時(shí)刻鏈路(u,v)的鏈路帶寬，Cu,v(T)表示在給定時(shí)間范圍T內(nèi)節(jié)點(diǎn)u和v之間的所有連通時(shí)段集合，Bufv表示節(jié)點(diǎn)v的緩存大小，Nv(t)表示t時(shí)刻節(jié)點(diǎn)v的緩存占用情況。

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

3.2 基于時(shí)變連續(xù)圖的相關(guān)定義及計(jì)算規(guī)則

在時(shí)變連續(xù)圖中，由于節(jié)點(diǎn)與鏈路均具有時(shí)間相關(guān)的約束，因此需要重新定義時(shí)變網(wǎng)絡(luò)中網(wǎng)絡(luò)流的相關(guān)約束及計(jì)算規(guī)則。首先，對(duì)于任一鏈路(u,v)∈E，將fu,v(t)定義為該鏈路的時(shí)變可行流，fu,v(t)需滿足以下幾個(gè)約束。

圖5 時(shí)變連續(xù)圖模型

1) 鏈路容量約束

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

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

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

2) 流守恒約束

對(duì)于給定的時(shí)間范圍T=[t0,th]內(nèi)，流入任一節(jié)點(diǎn)v∈V的總數(shù)據(jù)量等于流出該節(jié)點(diǎn)的總數(shù)據(jù)量，即

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

3) 節(jié)點(diǎn)緩存約束

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

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

1) 面向業(yè)務(wù)的鏈路累積流量計(jì)算

對(duì)于單跳的時(shí)變路徑，可根據(jù)業(yè)務(wù)傳輸需求以及該鏈路的鏈路帶寬與連通時(shí)段集合，確定該鏈路用于數(shù)據(jù)傳輸?shù)挠行нB通時(shí)段。不失一般性地，假設(shè)單跳的時(shí)變路徑為鏈路(A,B)∈E，鏈路連通時(shí)段集合為，如圖6 所示，具體計(jì)算規(guī)則如下。

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

圖6 鏈路累積流量計(jì)算

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

在業(yè)務(wù)規(guī)定的傳輸時(shí)間范圍內(nèi)，業(yè)務(wù)量與時(shí)變鏈路可行流需滿足如式(5)和式(6)所示關(guān)系。

2) 面向業(yè)務(wù)的路徑累積流量計(jì)算

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

圖7 路徑累積流量計(jì)算

不失一般性地，上述介紹的兩跳類路徑計(jì)算規(guī)則也適于多跳類路徑計(jì)算。其核心思想在于需依次利用前一跳鏈路的有效連通時(shí)段計(jì)算后一跳鏈路的有效連通時(shí)段，最后得到面向業(yè)務(wù)的端到端路徑中節(jié)點(diǎn)與鏈路資源的占用情況，實(shí)現(xiàn)時(shí)變資源的按需分配。

4 面向業(yè)務(wù)的時(shí)間確定性路由方法

在時(shí)變的天地一體化網(wǎng)絡(luò)中，構(gòu)建具有時(shí)間屬性的時(shí)變路由策略是保障業(yè)務(wù)端到端QoS 需求的關(guān)鍵。因此，基于所構(gòu)建的時(shí)變連續(xù)圖模型以及設(shè)計(jì)的時(shí)變可行流約束與計(jì)算規(guī)則，本文進(jìn)一步提出面向業(yè)務(wù)的時(shí)間確定性路由算法，如算法1 所示，該算法通過(guò)聯(lián)合考慮業(yè)務(wù)的傳輸量與開始時(shí)刻，鏈路的連通機(jī)會(huì)以及節(jié)點(diǎn)的存儲(chǔ)資源，借助鏈路累積流量計(jì)算規(guī)則，構(gòu)建面向業(yè)務(wù)的最短時(shí)延路徑，從而保障業(yè)務(wù)傳輸?shù)臅r(shí)間確定性。

算法1面向業(yè)務(wù)的時(shí)間確定性路由算法

輸入時(shí)變連續(xù)圖TCG={(V,E,T,Wu,v(t),Cu,v(T),Bufv,Nv(t))|v∈V,(u,v)∈E,t∈T}，給定的業(yè)務(wù)M，包括業(yè)務(wù)量大小D(M)、業(yè)務(wù)傳輸開始時(shí)刻tstart(M)、終止時(shí)刻tend(M)以及傳輸?shù)脑袋c(diǎn)S與目的點(diǎn)D

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

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

步驟2配置節(jié)點(diǎn)S的節(jié)點(diǎn)費(fèi)用c[S]=tstart(M)以及前一跳節(jié)點(diǎn)p[S]=?1，并將節(jié)點(diǎn)S加入節(jié)點(diǎn)隊(duì)列Q中，Q←S。

步驟3判斷隊(duì)列Q是否為空集，若Q為空集，跳轉(zhuǎn)至步驟7；否則，執(zhí)行步驟4。

步驟4從Q中取出節(jié)點(diǎn)費(fèi)用最小的節(jié)點(diǎn)u作為當(dāng)前的找路節(jié)點(diǎn)，同時(shí)更新隊(duì)列Q←Q?u。

步驟5當(dāng)節(jié)點(diǎn)u=S時(shí)，利用面向業(yè)務(wù)的鏈路累積流量計(jì)算規(guī)則，計(jì)算出節(jié)點(diǎn)u所有鄰接鏈路(u,v)的有效連通時(shí)段；當(dāng)節(jié)點(diǎn)u≠S時(shí)，利用面向業(yè)務(wù)的路徑累積流量計(jì)算規(guī)則，根據(jù)鏈路(p[u],u)的有效鏈路時(shí)段以及節(jié)點(diǎn)u的緩存能力Bufu，計(jì)算出節(jié)點(diǎn)u所有鄰接鏈路(u,v)的有效連通時(shí)段。

步驟6利用鏈路(u,v)的終止時(shí)刻對(duì)鄰接節(jié)點(diǎn)v的節(jié)點(diǎn)費(fèi)用c[v]進(jìn)行更新（如果，則更新c[v]=且p[v]=u），并把節(jié)點(diǎn)v加入隊(duì)列Q，并跳轉(zhuǎn)至步驟3。

步驟7判斷目的點(diǎn)D的節(jié)點(diǎn)費(fèi)用大小，若c[D]=∞，則表示任務(wù)M不存在從S到D的有效路徑，終止算法；否則，執(zhí)行步驟8。

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

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

圖8 面向業(yè)務(wù)的時(shí)間確定性路由算法實(shí)例

5 時(shí)間確定性路由協(xié)議

基于時(shí)變圖的時(shí)間確定性路由算法可為不同業(yè)務(wù)規(guī)劃出滿足傳輸需求的時(shí)變路徑，但為了保障業(yè)務(wù)傳輸?shù)臅r(shí)間確定性，還需相應(yīng)協(xié)議作為支撐。因此，本文針對(duì)天地一體化網(wǎng)絡(luò)的時(shí)變環(huán)境，提出時(shí)間確定性路由協(xié)議及協(xié)議棧模型，如圖9 所示。該模型在傳統(tǒng)TCP/IP 協(xié)議棧的基礎(chǔ)上對(duì)網(wǎng)絡(luò)層協(xié)議進(jìn)行擴(kuò)展，增加了時(shí)間確定性路由協(xié)議，包括自適應(yīng)拓?fù)浒l(fā)現(xiàn)與維護(hù)機(jī)制和基于時(shí)變圖的多業(yè)務(wù)時(shí)間確定性路由算法，為業(yè)務(wù)傳輸規(guī)劃出滿足時(shí)延需求的時(shí)變路徑。此外，為對(duì)每類業(yè)務(wù)進(jìn)行精準(zhǔn)傳輸和托管控制，本文將路由協(xié)議與SRv6 協(xié)議相結(jié)合，提出基于SR 的時(shí)間觸發(fā)分組轉(zhuǎn)發(fā)機(jī)制，實(shí)現(xiàn)不同業(yè)務(wù)按不同顯式路徑高效傳輸，保障時(shí)間確定性。

圖9 天地一體化網(wǎng)絡(luò)節(jié)點(diǎn)協(xié)議棧模型

1) 自適應(yīng)拓?fù)浒l(fā)現(xiàn)與維護(hù)機(jī)制

拓?fù)浒l(fā)現(xiàn)是路由計(jì)算的基礎(chǔ)，因此及時(shí)、準(zhǔn)確地獲取網(wǎng)絡(luò)拓?fù)浜涂捎觅Y源等信息是時(shí)間確定性路由構(gòu)建的關(guān)鍵。天地一體化網(wǎng)絡(luò)中節(jié)點(diǎn)的移動(dòng)性、資源的共享性以及節(jié)點(diǎn)的動(dòng)態(tài)加入和退出導(dǎo)致網(wǎng)絡(luò)拓?fù)漕l繁變化，傳統(tǒng)的基于固定周期的拓?fù)浒l(fā)現(xiàn)機(jī)制面臨問題。拓?fù)浒l(fā)現(xiàn)周期越短，拓?fù)湫畔⒌臏?zhǔn)確性越高，但信令負(fù)荷重，制約路由算法的性能。若拓?fù)浒l(fā)現(xiàn)周期過(guò)長(zhǎng)，則對(duì)于突發(fā)情況導(dǎo)致的拓?fù)渥兓l(fā)現(xiàn)不及時(shí)，易產(chǎn)生過(guò)時(shí)路由，導(dǎo)致分組丟失，且重路由將帶來(lái)額外的開銷?；诖?，考慮到天地一體化網(wǎng)絡(luò)拓?fù)渥兓哂幸欢ǖ目深A(yù)測(cè)性，將周期性拓?fù)浒l(fā)現(xiàn)與基于拓?fù)漕A(yù)測(cè)的拓?fù)浒l(fā)現(xiàn)和基于主動(dòng)探測(cè)的拓?fù)浒l(fā)現(xiàn)相結(jié)合，提出自適應(yīng)的拓?fù)浒l(fā)現(xiàn)與維護(hù)機(jī)制，在保障拓?fù)湫畔⒓皶r(shí)、準(zhǔn)確的同時(shí)降低信令負(fù)荷。

如圖10(a)所示，以時(shí)間T為周期發(fā)送Hello 分組進(jìn)行拓?fù)涮綔y(cè)。若依據(jù)節(jié)點(diǎn)的運(yùn)行軌跡、速度和時(shí)間等信息預(yù)測(cè)拓?fù)涞淖兓?，在有鏈路斷開或連通的時(shí)刻發(fā)送Hello 分組，而在其余時(shí)刻按照大于T的周期進(jìn)行拓?fù)涮綔y(cè)和維護(hù)，則能夠有效降低開銷，如圖10(b)所示。對(duì)于由故障等原因引起的難以預(yù)測(cè)的拓?fù)渥兓?，則由事件觸發(fā)，主動(dòng)發(fā)送Hello分組進(jìn)行探測(cè)，保障拓?fù)湫畔⒌募皶r(shí)性，如圖10(c)所示。

通過(guò)自適應(yīng)拓?fù)浒l(fā)現(xiàn)與維護(hù)機(jī)制，能夠動(dòng)態(tài)獲取天地一體化網(wǎng)絡(luò)的拓?fù)浜涂捎觅Y源等信息，作為多業(yè)務(wù)時(shí)間確定性路由算法的輸入，計(jì)算出確定性時(shí)延的時(shí)變路徑，并轉(zhuǎn)化為具有時(shí)間屬性的路由表，即包含每跳傳輸?shù)拈_始和終止時(shí)刻。協(xié)議中各模塊的關(guān)系如圖11 所示。

2) 基于SR 的時(shí)間觸發(fā)分組轉(zhuǎn)發(fā)機(jī)制

借鑒TSN 技術(shù)允許周期性與非周期性數(shù)據(jù)在同一網(wǎng)絡(luò)中共同傳輸?shù)乃枷?，本文將業(yè)務(wù)分組分為時(shí)間確定性業(yè)務(wù)分組與普通業(yè)務(wù)分組（普通業(yè)務(wù)無(wú)時(shí)延保障），利用時(shí)間觸發(fā)機(jī)制實(shí)現(xiàn)分組轉(zhuǎn)發(fā)。特別地，對(duì)于時(shí)間確定性業(yè)務(wù)的分組，本文進(jìn)一步融合了SR 技術(shù)對(duì)分組進(jìn)行路由轉(zhuǎn)發(fā)。具體來(lái)說(shuō)，依據(jù)構(gòu)建出的時(shí)變路由表，將路由信息添加至分組頭部。此外，為了精準(zhǔn)控制分組的傳輸，還添加了轉(zhuǎn)發(fā)的開始和結(jié)束時(shí)刻。當(dāng)網(wǎng)絡(luò)節(jié)點(diǎn)轉(zhuǎn)發(fā)分組時(shí)，將優(yōu)先識(shí)別分組頭部的路由信息，獲取下一跳節(jié)點(diǎn)，并由時(shí)間觸發(fā)，執(zhí)行轉(zhuǎn)發(fā)流程，直到將分組投遞至目的節(jié)點(diǎn)。若需要在節(jié)點(diǎn)進(jìn)行托管，則根據(jù)路由表信息設(shè)置定時(shí)器，在定時(shí)器超時(shí)后再傳輸數(shù)據(jù)。對(duì)于沒有嚴(yán)格的時(shí)延保障要求的普通業(yè)務(wù)，在不影響時(shí)間確定性業(yè)務(wù)傳輸?shù)那疤嵯?，按照統(tǒng)一計(jì)算出的路由表，通過(guò)IPv6 流程實(shí)現(xiàn)分組的存儲(chǔ)?托管?轉(zhuǎn)發(fā)。

6 仿真與評(píng)估

為了驗(yàn)證面向業(yè)務(wù)的時(shí)間確定性路由算法的有效性與可行性，本文將所提算法（記為TCG-based）與CGR 算法[24]和基于快照?qǐng)D的路由算法[26-27]（記為snapshot-based）進(jìn)行比較，并對(duì)仿真結(jié)果進(jìn)行了分析與討論。

1) 仿真場(chǎng)景及參數(shù)設(shè)置

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

圖10 自適應(yīng)拓?fù)浒l(fā)現(xiàn)與維護(hù)機(jī)制

圖11 時(shí)間確定性路由與轉(zhuǎn)發(fā)協(xié)議中各模塊的關(guān)系

為了分析與評(píng)估算法性能，考慮如下3 項(xiàng)指標(biāo)。

2) 仿真結(jié)果與分析

圖12 給出3 種路由算法的端到端時(shí)延對(duì)比。從圖12 可以看出，snapshot-based 算法的端到端時(shí)延最低，但是點(diǎn)數(shù)最少（即完成的業(yè)務(wù)數(shù)最少），其背后的原因在于，該算法僅在單獨(dú)的快照?qǐng)D內(nèi)搜索端到端路徑，不支持跨時(shí)段數(shù)據(jù)傳輸，所求路徑的跳數(shù)少、時(shí)延低。然而，當(dāng)快照內(nèi)不存在端到端路徑時(shí)，業(yè)務(wù)無(wú)法傳輸。TCG-based 算法與CGR 算法的端到端時(shí)延性能基本一致，由于均采用存儲(chǔ)?托管?轉(zhuǎn)發(fā)方式，時(shí)延略高于snapshot-based 算法。此外，TCG-based 算法比CGR 算法能夠完成更多的業(yè)務(wù)，原因是該算法選路時(shí)考慮到節(jié)點(diǎn)緩存限制，規(guī)避掉了緩存溢出節(jié)點(diǎn)。

3種路由算法的鏈路資源利用率對(duì)比如圖13所示。從圖13 中可以看出，TCG-based 算法的鏈路資源利用率最高，CGR 算法次之，而snapshot-based算法最低。該現(xiàn)象可以解釋為snapshot-based 算法無(wú)法聯(lián)合利用不同時(shí)段的網(wǎng)絡(luò)鏈路資源，而TCG-based 算法與CGR 算法借助節(jié)點(diǎn)緩存資源存儲(chǔ)?托管?轉(zhuǎn)發(fā)機(jī)制，能夠構(gòu)建時(shí)變傳輸路徑，實(shí)現(xiàn)不同時(shí)段空閑資源的高效利用。此外，由于CGR算法在路徑計(jì)算時(shí)未考慮節(jié)點(diǎn)緩存限制，可能產(chǎn)生部分無(wú)效路徑，導(dǎo)致鏈路資源利用率低于TCGbased 算法。

圖12 3 種路由算法的端到端時(shí)延對(duì)比

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

圖14 給出了3 種路由算法的分組投遞率對(duì)比。從圖14 可以看出，snapshot-based 算法能夠成功傳輸?shù)臉I(yè)務(wù)分組最少，原因是在衛(wèi)星網(wǎng)絡(luò)環(huán)境中，由于拓?fù)鋽嗬m(xù)連通，單個(gè)快照內(nèi)難以構(gòu)建出端到端路徑，業(yè)務(wù)分組無(wú)法傳輸?shù)侥康墓?jié)點(diǎn)，導(dǎo)致投遞率低。TCG-based 算法和CGR 算法均支持跨時(shí)段數(shù)據(jù)傳輸，在給定時(shí)間范圍內(nèi)能夠到達(dá)目的節(jié)點(diǎn)的業(yè)務(wù)分組多。此外，由于TCG-based 算法考慮了節(jié)點(diǎn)緩存約束，避免由緩存溢出導(dǎo)致的分組丟失，因此投遞率更高。

7 結(jié)束語(yǔ)

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

本文圍繞著天地一體化網(wǎng)絡(luò)中業(yè)務(wù)端到端傳輸?shù)穆酚蓡栴}，提出基于時(shí)變圖的天地一體化網(wǎng)絡(luò)時(shí)間確定性路由算法及協(xié)議。首先，通過(guò)構(gòu)建時(shí)變連續(xù)圖模型，實(shí)現(xiàn)天地一體化網(wǎng)絡(luò)時(shí)刻多維資源的精準(zhǔn)刻畫；然后，提出面向業(yè)務(wù)的時(shí)間確定性路由算法，利用面向業(yè)務(wù)的時(shí)變鏈路累積流量計(jì)算規(guī)則，構(gòu)建時(shí)變按需的最短時(shí)延路徑；最后，進(jìn)一步設(shè)計(jì)了具有時(shí)延保障的時(shí)間確定性路由協(xié)議，支持?jǐn)嗬m(xù)連通的時(shí)變網(wǎng)絡(luò)環(huán)境中拓?fù)涞膭?dòng)態(tài)發(fā)現(xiàn)、確定性路由的高效計(jì)算以及數(shù)據(jù)分組的定時(shí)轉(zhuǎn)發(fā)。仿真結(jié)果表明，所提路由算法通過(guò)利用節(jié)點(diǎn)存儲(chǔ)資源，有效地提升了時(shí)變鏈路資源利用率，保障了業(yè)務(wù)在時(shí)變環(huán)境下的端到端傳輸需求。