天地聯合測控魯棒性路由算法

夏茹敏，史可懿，何 健，李紅艷

（1.西安電子科技大學 通信工程學院，陜西 西安 710071；2.上海航天電子技術研究所，上海 201109）

0 引言

隨著應急通信、應急救援、導航定位、遙感遙測、國防安全、智慧城市等領域的迅速發展，航天測控（Telemetry，Tracking，and Command，TT&C）網扮演起越來越重要的角色，為運載火箭、航天器跟蹤測軌、遙測信息的下傳接收與處理、遙控指令上行數據注入等任務提供服務和保障［1］。航天測控網由多個地面站、測控中心和通信系統組成［2］。隨著發射飛行器數量的激增以及功能的多樣化［3］，為滿足海量飛行器的高效測控需求，航天測控逐漸從以地面站為主的地基測控網演進為天地聯合的天基測控網［4］。傳統地基測控網過分依賴地面測控站，為實現近地衛星全天候不間斷的測控，需要進行全球布站。20 世紀80 年代建成的跟蹤與數據中繼衛星系統（Tracking and Data Relay Satellite System，TDRSS）［5］，以地球同步中繼衛星為依托，形成測控中心—地面站—中繼衛星—用戶星的前向鏈路，與用戶星—中繼衛星—地面站—測控中心的反向鏈路，完成衛星遙控指令的注入與衛星遙測數據的接收［6］。但是，TDRSS 系統仍然存在局限性［7］：一方面，TDRSS 系統整體服務的用戶數量仍然有限［8］；另一方面，TDRSS 仍然采用對測控任務進行預先規劃的測控形式，對于突發測控任務顯得無力。中低軌衛星星座代替地球同步軌道通信衛星為近地衛星提供中繼測控服務的機制，雖然有為更多用戶提供測控服務的能力，但其覆蓋性與TDRSS 系統相差甚遠。基于此，亟需研究一種新型的航天測控方法，既能滿足低軌衛星全覆蓋的需求，又能為未來海量多功能衛星提供實時、精準、靈活的測控服務，即天地聯合組網測控技術，如圖1 所示。

圖1 天地聯合組網測控架構Fig.1 TT&C architecture of space-ground integrated network

天地聯合測控網絡包含“兩網一鏈”：“兩網”分別位于空間和地面，天網是由低軌衛星星座與高軌衛星星座組成的星座網絡，用于為將來海量低軌道衛星及近地飛行器提供100%的軌道覆蓋率與豐富的測控資源；地網是由地面站、地面控制中心和地面通信互聯網組成的地基信息網絡，負責衛星測量、觀測數據與控制指令的接受、處理與傳輸；“一鏈”指天網中衛星節點之間的通信鏈路，即星間鏈路（Inter Satellite Links，ISL），是星間組網進行路由傳輸的基礎。星間鏈路的加入，將為衛星測控帶來極大的便利，拋棄測控站“靜態調度”“大測控，小中心”的舊模式是必然趨勢［9］。隨著航天任務頻次的增加及測量弧段等要求的提高，地基測控系統的發展已不能完全滿足未來運載火箭及衛星測控任務的需求［10］。我國的航天測控網的主要發展途徑逐步由陸、海基測控網向天基為主、天地結合的一體化綜合測控網發展［11］。

天地聯合組網測控雖然具備全球覆蓋、資源豐富和靈活度高等優勢，但也面臨一系列挑戰。測控高可靠要求與衛星組網路由不穩定相矛盾，中低軌衛星、臨近空間飛行器及地面測控站相對運動，難以存在穩定的端到端路徑。此外，空間環境復雜，空間輻射、日凌等因素會導致星間鏈路性能降低，甚至中斷。航天測控對測控信息的傳輸可靠性具有很高要求，需要路由具備較強的魯棒性以抵制網絡時變特征與鏈路不穩定特性所帶來傳輸路徑不可靠性。傳統的魯棒性指標用于衡量系統在結構、大小等參數的攝動下，仍能夠維持某些性能的特性。而路由魯棒性可定義為路徑中節點/鏈路失效時，維持端到端數據傳輸性能（如連通性、時延、吞吐量等）的能力。如何在時變網絡環境中構建高魯棒性路由是有待解決的問題。

網絡拓撲和多維資源的精準表征是路由設計的基礎，本文將采用時變圖模型刻畫天地聯合測控網絡的時變特征。為了不斷提升表征精準性和高效性，時變圖不斷演進，經歷了快照圖、時間擴展圖（Time-Expanded Graph，TEG）、時間聚合圖、存儲時間聚合圖的發展歷程［12］，如圖2 所示。

圖2 時變圖演進過程Fig.2 Temporal graph evolution process

快照圖是一段時間內多張靜態圖的集合，在時間維度上將連續變化的網絡拓撲進行離散化處理，由一段時間內的多個快照圖共同表征該段時間內的網絡特征［13］。快照圖在一定程度上記錄了時變網絡拓撲隨時間變化的狀態，但卻割裂了每個快照子圖之間的關聯關系。時間擴展圖適用于拓撲變化不頻繁的時變網絡，需要較大的存儲空間，產生較大的計算代價［14］。時間聚合圖去掉了時間擴展圖的存儲邊，在網絡拓撲圖的每個鏈路上用時間序列表示該鏈路的連接變化情況，將多個時隙的網絡子拓撲進行壓縮聚合，但是由于沒有節點復制，缺少對節點存儲資源的表征［15］。存儲時間聚合圖在2015 年被提出，該模型在時間聚合圖的基礎上，對節點模型進行改進，將節點存儲資源隨時間變化的過程抽象為節點存儲資源轉移的時間序列，結合時間擴展圖與時間聚合圖的優點，既精確地表征了時變網絡多維資源關系，又節省了模型的存儲空間，缺點在于鏈路時間序列與節點時間序列計算復雜［16］。

在地面網絡路由魯棒性的研究中，通常是通過備份路徑機制實現，即為業務傳輸同時構建兩條鏈路/節點分離的端到端路徑，一條為主路徑，另一條為備份路徑［17］。這種機制能夠有效保障在網絡單鏈路故障情況下，業務傳輸不中斷。對于衛星網絡，ZHAO［18］提出了一種基于面向連接結構的增強路由算法，能夠在源衛星和目標衛星間在線尋找最佳路徑。ZHANG 等［19］在2014 年于依賴 網絡模型中提出了一種基于重要抽樣的計算路徑失效概率的算法，并得到網絡中一對節點之間最具可靠性的路徑。LONG 等［20］在2014 年對多層衛星網絡的魯棒QoS 路由技術進行了研究，在鏈路擁塞和節點故障處理機制上進行改進，提出了一種新的衛星分組路由協議，使得路由策略更加健壯。

本文面向未來海量多功能衛星提供實時、精準、靈活、可靠測控的需求，設計了天地聯合測控魯棒性路由方法，在時變、干擾環境中保障測控業務端到端可靠傳輸。首先，分析現有地基與天基測控系統的優勢與不足，提出基于混合星座組網的新型測控架構；然后，借助時間擴展圖模型，精準表征天地聯合網絡拓撲連接和鏈路時延時變性，進而將時延保障魯棒路由問題建模為最短時延備份路徑問題，采用貪心思想和增廣路徑回退機制，提出基于時間擴展圖的最短時延備份路徑算法，能夠同時計算出兩條滿足時延需求且鏈路分離的端到端時變路徑，確保在單鏈路故障情況下測控業務的成功傳輸；最后，通過算例和復雜度分析驗證了算法效能。

1 系統模型

1.1 天地聯合組網測控架構

天地聯合組網測控網絡由空間段和地面段兩部分構成。空間段包括用戶飛行器（如遙感衛星、載人航天飛船、資源衛星等測控對象）、低軌星座網絡（如Iridium、OneWeb、Telesat 等配備星間鏈與星上處理能力的低軌衛星星座）；地面段包括若干地面站、地面控制中心、地面網絡以及用戶飛行器所對應的地面用戶。空間與地面網絡聯合對用戶飛行器進行測量與控制，完成控制指令的上注與測量信息的下傳，根據指令對用戶飛行器的飛行狀態進行調整，保障用戶飛行器的正常運行。

傳統的跟蹤與數據中繼系統是利用中繼衛星進行“彎管傳輸”，而在天地聯合組網測控模型中，低軌星座網絡代替中繼衛星來完成數據中繼的任務，相比傳統的地球同步軌道中繼衛星，低軌星座衛星不僅具備很高的覆蓋率，而且距離地面更近，具有更短的傳播時延。最重要是的，星座網絡中的衛星間存在星間鏈，衛星上裝備有具備路由功能的機載處理模塊，能夠組成功能強大的星座互聯網。在該星座互聯網中，每顆衛星都相當于一個獨立的IP 網絡節點，因此，針對突發任務請求，用戶飛行器可以按照自己的任務需求，在路由表中尋找相應的目的節點，獨立自主地完成數據的傳輸任務，不再依賴于預先規劃任務的測控機制，大大提高測控的靈活性。

地面控制中心是測控技術的計算中樞，地基、天基或是天地聯合組網的測控機制所查詢的任務調度方案（預約）或路由表（即時），都是在地面控制中心進行計算與生成的。以控制指令上傳過程為例，介紹天地聯合組網測控機制工作流程：首先，地面用戶會根據任務需求向地面控制中心申請進行測控控制指令上傳的工作；然后，地面控制中心會根據相關請求內容（控制用戶飛行器IP 地址、地面用戶IP 地址、用戶飛行器的調整策略等），在路由表中尋找對應的傳輸路徑，地面控制中心用查詢結果對測控指令進行封裝并將其發送至對應的地面站，地面站通過中繼網絡（低軌星座）將測控指令發送至對應的目標飛行器；最后，用戶飛行器會根據測控指令進行相應的姿態、方向等調整，完成控制指令上傳工作。對于用戶飛行器測量數據的下傳過程是控制指令上傳過程的逆過程，同樣根據查詢路由表完成測量數據的下傳工作。

1.2 時間擴展圖表征天地聯合網絡時變特性

考慮一個典型的天地聯合網絡，包含一顆源衛星s，多顆傳輸衛星{r1，r2，…，rN-2}和一個地面站節點d，如圖3 所示，鏈路連接關系隨時間變化。源衛星s期望通過傳輸衛星中繼或直接過頂下傳將信息（如位置、姿態、遙感信息等）發送到地面站，用于測控。為了精準刻畫天地聯合網絡的時變拓撲和鏈路時延，構建時間擴展圖模型TEG={V，E，D}。特別地，依據拓撲變化特征將規劃時間區間T=[t0，tk)劃分為k個連續時 隙(τ1，…，τh，…，τk)，τh=[th-1，th)，滿足各時隙內網絡拓撲保持不變。

圖3 天地聯合網絡示例Fig.3 An example of the space-ground integrated network

構建的時間擴展圖如圖4 所示，包含：1）節點集合V為網絡中衛星節點在各時隙中的復制。2）邊集合E。對于?uh，vh∈V，傳輸邊(uh，vh)∈E為從節點u到v的在時隙τh內的通信鏈路，對于?uh，uh+1∈V，存儲邊(uh，uh+1)∈E刻畫了節點u的存儲能力。3）鏈路時延集合D。對 于?(uh，vh)∈E，為在τh時隙內鏈路(u，v)的傳播時 延；對 于?(uh，uh+1)∈E，為節點u托管數據的時長，可以認為等于時隙τh的長度。本文假定所有時隙長度均為60 s。

圖4 時間擴展圖表征天地聯合網絡Fig.4 Time-expanded graph for modeling the space-ground integrated network

由于時間擴展圖將數據源衛星和地面站分別拆分為不同時段的多個源節點和目的節點，違背了單源單匯最短路徑的約束。

為解決該問題，在原始TEG 模型中分別引入虛擬源節點s′、輔 助發送邊(s′，s1)、虛擬目的節點d′和輔助匯聚邊{(dh，d′)|1≤h≤k}，得到修正的圖模型MTEG，如圖5 所示，支持跨時段端到端路徑的構建。

圖5 修正的時間擴展圖Fig.5 Modified time-expanded graph

基于MTEG，可以將時延保障魯棒路由問題建模為最短時延備份路徑問題，即

式 中：Pc={(s′，s1)，…，(u，v)，…，(di，d′)} 和Pb={(s′，s1)，…，(m，n)，…，(dj，d′)}為 從s′ 到d′ 的一條主路徑和一條備份路徑，兩者沒有重復邊；D(Pc)、D(Pb)為路徑Pc和Pb的端到端時延，由路徑中各通信鏈路的傳播時延和各節點的托管時長決定。

2 天地聯合魯棒性路由方法

2.1 基于時間擴展圖的最短時延備份路徑算法

對于給定的修正時間擴展圖MTEG，為求得兩條互為鏈路備份的最短時延路徑，最直觀的貪婪策略是先采用任意最短路徑算法搜索一條從s′到d′的最短時延路徑Pc。然后對MTEG 進行剪枝，即去除掉包含在Pc中的所有邊，得到殘余網絡----- -------MTEG，并搜索另一條端到端最短路徑Pb，獲得具有時延和魯棒性保障的備份路徑路由。然而，由于剪枝會降低網絡的連通性，可能導致備份路徑無法構建，如圖6所示。

圖6 剪枝導致備份路徑無法構建Fig.6 Construction failure of backup path owing to pruning

天地聯合網絡中節點高速移動、鏈路斷續連通，缺乏穩定的端到端連通路徑，基于剪枝的備份路徑構建算法應用受限。

本文依托增廣路徑回退思想，提出基于時間擴展圖的最短時延備份路徑算法。在路徑搜索過程中，若選定的主路徑導致滿足鏈路無關的備份路徑無法構建時，能夠自主對主路徑進行修正，得到滿足時延和魯棒性要求的兩條路徑。特別地，考慮到MTEG 中不同時隙的復制邊本質上對應同一條物理鏈路，一旦該鏈路在某時隙τh中斷，則后續時隙中相應的復制邊也不可用。因此，為嚴格滿足鏈路備份要求，在主路徑Pc搜索完并更新網絡鏈路時延代價時，對于?(uh，vh)∈Pc，MTEG 中(uh，vh)，…，(uk，vk)的時延代價均要修正，以避免備份路徑Pb構建時選擇與Pc重復的鏈路。具體算法步驟如下：

步驟1 時延懲罰值θ定價。θ定義為MTEG中虛擬源節點s′到虛擬目的節點d′之間最長時延無環路徑的時延代價。

步驟2主路徑Pc搜索。利用Dijkstra 算法［21］在MTEG 中搜索從s′到d′的最小時延路徑Pc={(s′，s1)，…，(u，v)，…，(di，d′)}。

步驟3鏈路時延代價更新，獲得殘余網絡。對 于?(u，v)∈Pc-{(s′，s1)，(di，d′)}，在MTEG 中引入反向邊(v，u)，定義時延代價為Dv，u=-Du，v，支 持Pc的調整；對 于Pc中的任意 通信鏈路(uh，vh)，在MTEG 中將邊(uh，vh)，…，(uk，vk)的時延均增加θ，避免搜索備份路由時重復選擇Pc中的鏈路。

步驟4備份路徑Pb構建。利用Bellman-Ford算法［22］在中尋找從s′到d′的最小時延路徑。

步驟5路徑更新。若Pc中存在子路徑在Pb中有對應的反向子路徑，則需抵消該子路徑，重構端到端路徑Pc′和Pb′，即為滿足鏈路備份要求的兩條最短時延路徑。

2.2 算法復雜度分析

定理1對于給定的天地聯合網絡，包含N個節點（衛星和地面站）和M條通信鏈路，基于時間擴展圖的最短時延備份路徑算法時間復雜度為O(k2NM)，其中，k為時間擴展圖劃分時隙數。

證明MTEG 表征天地聯合網絡時對節點和鏈路進行了復制，包含kN+2 個頂點和至多k(M+1)+1 條邊。步驟1 中時延懲罰值定價可通過將各邊時延代價取負，并利用Dijkstra 算法尋找最小“負時延”路徑，轉換后得到最長時延路徑代價θ，復雜度為O((kN+2)2) ≈O(k2N2)。步驟2 中調用Dijkstra 算法搜索主路徑Pc復雜度也為O((kN+2)2) ≈O(k2N2)。步驟3 中需更新時延代價的邊至多為(k+1)M條，因此復雜度為O((k+1)M)≈O(kM)。步驟4 中由于存在時延代價為負的邊，因此采用Bellman-Ford 算法計算Pb，復雜度為O((kN+2)((k+1)M+k+1))≈O(k2NM)。由于步驟5 中反向子路徑消除至多進行M次，因此復雜度為O(M)。綜上，基于時間擴展圖的最短時延備份路徑算法具有2·O(k2N2)+O(kM)+O(k2NM)+O（M）≈O（k2NM）的時間復雜度。

3 算法應用實例

基于圖6 給出的MTEG，給出基于時間擴展圖的最短時延備份路徑路由算法的運行實例。

圖7 基于時間擴展圖的最短時延備份路徑路由算法的應用Fig.7 An application of the TEG-based minimum delay backup path routing algorithm

傳統備份路由構建方法的運行實例如圖8 所示，該方法基于快照圖［13］、貪婪策略和剪枝操作。由于在第1 時段內，源節點s與目的節點d之間無連通路徑，僅能在第2 時段的網絡拓撲中搜索主路徑。如圖8（a）所示，以路徑時延最小化為優化目標，應用 Dijkstra 算法獲得主路徑Pc={(s，r2)，(r2，r3)，(r3，d)}，路徑時延D(Pc)=60+0.04=60.04 s，包 含60 s 的等待時延和0.04 s的路徑傳輸時延。

通過剪枝操作獲得的殘余網絡如圖8（b）所示，由于第1 和第2 時段內s與d均不連通，因此無法構建備份路徑Pb。

圖8 傳統備份路徑路由算法實例Fig.8 An example of the traditional backup path routing algorithm

4 結束語

本文針對未來海量多功能衛星可靠測控需求，提出天地聯合測控時延保障魯棒路由方法。首先，分析現有地基與天基測控系統的優勢與不足，提出基于混合星座組網的新型測控架構。然后，利用時間擴展圖模型表征網絡拓撲和鏈路時延的時變性，并將時延保障魯棒路由問題建模為最短時延備份路徑問題。基于構建的時間擴展圖模型，提出高效的最短時延備份路徑算法。該算法采用貪心思想并搜索路徑，并利用增廣路徑回退機制，動態調整主路徑，獲取滿足時延要求的備份路徑，確保在任意單鏈路故障情況下測控業務的快速傳輸。