基于多維梯度的衛星集群高可靠協同計算方法

馬步云/MA Buyun，任智源/REN Zhiyuan，李贊/LI Zan

（西安電子科技大學綜合業務網理論及關鍵技術國家重點實驗室，中國 西安 710071）

(State Key Laboratory of Integrated Services Networks,Xidian University,Xi’an 710071,China)

由于具有星地傳輸距離短、覆蓋范圍廣等優勢，基于低軌（LEO）衛星的通信系統[1]受到業界廣泛關注。同時，大量數據在傳輸過程中仍需進一步處理才能被使用（例如，衛星采集的圖像需要經過去噪、特征提取等后才可被使用）。然而，受限于衛星的載荷能力和宇宙射線的影響[2]，單顆衛星的計算能力難以大幅提升，很難獨自完成計算密集型任務。而將海量數據轉發至地面云計算中心，利用云平臺強大的計算資源處理數據[3]，雖然可有效降低計算時延，但是會帶來過高的通信開銷，仍難以有效滿足業務需求。因此，研究端到端業務計算方法勢在必行。通過協作可使衛星展現出強大的傳輸與計算數據的能力。

目前，大多數研究者致力于單方面優化路由[4-6]或業務卸載策略[7-10]，將兩者統一考慮的很少。而現有的端到端信息處理方案均為集中式業務調度[11-13]，其中，中心管理節點負責管理網絡并制訂合理的業務調度方案，LEO集群根據預先制訂好的方案相互協作。然而，LEO衛星數目眾多且計算資源有限，真實的衛星網絡很難擁有一個強大的中心管理節點（該節點一旦發生故障，整個網絡將癱瘓）。此外，由于衛星工作在復雜的宇宙環境中，極易受到干擾，如采用集中式調度模式處理業務，調度方案中的任何一顆衛星出現故障都將導致任務失敗，很難滿足業務的可靠性需求。基于此，針對單星計算能力弱、節點故障率高的分布式LEO集群，亟需一種分布式低時延高可靠的端到端業務計算方法，以滿足業務需求。

本文面向分布式LEO集群，提出了一種去中心式端到端信息處理技術方法。該方法首先依托時空擴展圖（TEG）來屏蔽LEO集群的高動態特性，隨后對端到端業務調度進行理論建模并設計分布式業務調度算法。當任務到來時，每顆衛星基于其鄰居節點信息，獨自運行該算法來選擇下一跳節點，并逐步完成數據的傳輸與計算。該算法提出了一種新的度量梯度指標（業務調度效率）作為選擇下一跳節點的依據。該梯度指標綜合考慮了節點的計算能力、鏈路傳輸速率、故障率、至目標衛星的跳數，可有效降低系統時延，提高系統可靠性。

1 系統模型

分布式LEO集群系統架構如圖1所示。其中，為不失一般性，假設地面站定時向LEO集群廣播全局拓撲信息，每顆衛星可計算自身到結果接收衛星的跳數。當任務到達時，每顆衛星根據自身相鄰節點的信息逐步選擇下一節點，并完成端到端業務計算。

▲圖1 低軌集群系統架構圖

1.1 LEO網絡模型

為屏蔽LEO集群的動態性，本節依托LEO衛星運行軌道參數構建TEG模型。

令N={n1,…,np,…,ns}表示 LEO集群，以地心為坐標原點，以赤道平面為X軸、Y軸所在平面，Z軸通過地心并垂直于赤道平面指向北極，建立空間直角坐標系。則在任意時刻t時，np(np∈N)的位置坐標可通運行軌道計算得到。np與no(np,no∈N,p≠o)之間的距離可通過式（1）來計算。

定義t時刻np與no之間的鏈路狀態為，并可表示為式（2）：

其中，r*為星間鏈路的設計速率，為t時刻np與no的理論傳輸速率。表示np與no連通且鏈路傳輸速率為r*，反之則表示np與no鏈路中斷。可根據香農公式得出式（3）：其中，B為星間鏈路帶寬，σ2為高斯白噪聲方差，為t時刻的信號接收功率。在星間鏈路中，信號傳輸損耗主要為自由空間傳輸損耗[14]。因此，可由式（4）來表示：

其中，Gr、Pt、Gt分別表示信號接收增益系數、信號發射功率和信號發射增益系數，λ為載波波長。則式（2）可進一步表示為：

基于式（5），通過遍歷可獲得LEO集群拓撲。此時，以LEO集群某一時刻狀態為起點，將系統運行周期T等分為n個連續時隙，長度定義為Δ=T/n。假設時隙內拓撲穩定不變，則LEO集群N可表示為N=(NT,ET)，其中NT={N1,…,Nn}為節點集合，ET為邊集合，如圖2所示。

▲圖2 低軌集群時空擴展圖模型

（1）時隙內邊的權重。任意時隙?q∈T內，邊的權重為節點傳輸單位數據量到節點的時延，如式（6）所示：

則q時隙內LEO集群可表示為式（7）：

（2）時隙間邊的權重。數據在傳輸過程中可能存在由鏈路中斷所導致傳輸失敗的情況，因此，需要定義時隙間邊的權重，即數據到達衛星節點時，當前時隙的剩余時間，如式（8）所示：

則相鄰時隙q,q+1∈T間LEO集群可表示為式（9）：

此時，LEO集群的TEG模型可表示為式（10）：

1.2 端到端業務計算理論模型

基于TEG，本節提出端到端業務計算理論模型。為不失一般性，本節按照子業務間的依賴關系建立業務有向無環圖（DAG）模型。同時，根據文獻[15]，任何結構的DAG均可解析為串行DAG，因此，本文僅考慮串行DAG。

定義 DAG 為 Ω =(Ψ,?)。其中，Ψ ={φ1,…,φl}為節點集合，表示子業務集群，φ1為業務起點，φl為業務終點；?為邊集合，表示子業務間的依賴關系。此外，φi∈ Ψ 由元組{Di,ηi,εi}表征，其中Di為輸入數據量，ηi為數據壓縮系數，εi為計算復雜度系數。同時，定義為子任務φj的先驅節點集合。此時，業務Ω在LEO集群中的調度可轉化為DAG至TEG的映射規則，如圖3所示。

▲圖3 DAG至TEG的映射示例

（1）節點映射規則

我們首先定義Υ。Ψ→NT表示子業務節點Ψ至衛星節點NT的映射。具體地，如式（11）所示，業務起點映射至業務發起衛星，業務終點映射至結果接收衛星，中間業務節點映射至任意衛星。為不失一般性，假設子業務不可再分，所有子業務均在單顆衛星上計算，考慮到傳輸過程中鏈路可能斷開，此時數據需在衛星上緩存，經過虛擬鏈路至下一時隙，ρi為跨時隙數目。

（2）邊映射規則

?→ET表示DAG有向邊?至TEG無向邊ET的映射，以反映子業務間的依賴關系。具體地，如式（12）所示，將DAG的有向邊 ?(φi,φj)∈?映射為圖N中 Υ(φi)至 Υ(φj)之間的最短路由。

1.3 分布式端到端業務調度算法

為了實現在分布式LEO集群中數據的“邊傳輸邊計算”，本節提出分布式端到端業務調度算法，如算法1所示。該算法主要由3個步驟構成：（1）任務到來時，通過廣播發現鄰居節點，并獲取其必要的狀態信息以用于計算任務調度效率（TSE）；（2）計算鄰居節點的TSE，并根據TSE選擇下一跳節點；（3）判斷當前時隙剩余時間是否充足，若充足則將數據發給已確定好的下一跳節點，否則返回步驟2，并基于下時隙信息重新選擇下一跳節點。

基于上述端到端業務計算理論模型分析，算法需統一考慮節點的計算能力和鏈路狀態以實現端到端業務計算，而由于缺乏中心節點的統一調度，僅考慮計算能力和鏈路狀態可能會導致數據的反向傳輸。因此，需要引入目標節點位置信息以實現數據的定向傳輸，同時為了保證數據傳輸的可靠性，節點故障率也需要被考慮進算法中。基于以上分析，本節定義TSE梯度指標，綜合考慮了節點的計算能力、鏈路狀態、故障率、距目標節點跳數多維梯度信息，如式（13）所示：

其中，HΥ(φi)Υ(φl)為映射節點 Υ(φi)至結果接收衛星Υ(φl)沿最短路徑所需跳數，χΥ(φi)為節點 Υ(φi)的故障率，fΥ(φi)為節點 Υ(φi)的計算能力，eΥ(φj)Υ(φi)為子任務φi的前向節點φj的映射節點Υ(φj)沿最短路徑至 Υ(φi)的傳輸速率。由式（13）可知，距目標節點越近，節點計算能力越強，故障率越低、鏈路傳輸速率越快，TSE就越小，該節點的調度效率也就越高。

算法1分布式端到端業務調度算法

輸入：DAG模型，TEG

步驟1：任務到來時，通過廣播發現鄰居節點并獲取其多維狀態信息，包括計算能力、鏈路狀態、故障率、距目標節點跳數；

步驟2：根據式（13）計算各鄰居節點的TSE指標，并選取TSE最小的節點為下一跳節點；

步驟3：判斷此時將數據傳輸至下一跳節點的時延是否小于當前剩余時隙，若小于則傳輸；否則就緩存數據，返回步驟2，并根據TEG預測下時隙的TSE指標，重新選擇下一跳節點。

輸出：下一跳節點

2 仿真與評估

為驗證本文提出的分布式業務調度方案的有效性，本節將該方案同集中式方案進行比較。在比較過程中，所有實驗均基于相同假設。在集中式業務調度模式下，中心節點運行集中式業務調度算法以獲取傳輸路徑上的關鍵計算節點。集中式業務調度算法采用經典的DAG調度算法-異態最早結束時間（HEFT）算法[15]。值得注意的是，由于集中式業務調度算法依賴較多的計算資源，衛星節點雖具備一定計算能力，但很難運行集中式業務調度算法。本節同時將基于TSE指標選擇下一跳節點的分布式業務調度算法（記為Proposed）同隨機式（記為Random）和貪婪式（記為Greedy）兩種常用業務調度算法進行比較，并對仿真結果進行分析與討論。

2.1 仿真場景及參數設置

本文考慮由15顆低軌衛星構成的衛星集群。其中，低軌衛星均取自銥星星座（軌道高度780 km）。本文中，我們利用衛星工具包（STK）獲取網絡真實連通情況。仿真時間段為2021年4月26日00:00—00:30。本文仿真平臺為Python 3.7，采用的業務圖為圖1中的DAG。參照文獻[11]和[16]，仿真參數如表1所示。此外，為不失一般性，本文所有仿真結果均基于3 000次蒙特卡洛實驗。

▼表1 基本參數

為了分析與評估性能，我們考慮端到端業務處理時延和任務成功率兩個指標。

（1）端到端業務處理時延

基于1.2節的DAG至TEG的調度規則，端到端業務處理時延可建模如下。

進行到子任務φi時的處理時延如式（14）所示：

其中，Tcomp(φi)表示φi的計算時延，Taccu(φi)表示φi前向節點的累積時延。fΥ(φi)為節點 Υ(φi)的計算能力，表示衛星節點Υ(φi)中央處理器（CPU）每秒運行的周期數。

因此，Ω的業務處理時延為最后一個子任務φl的處理時延，如式（15）所示。

（2）任務成功率α

任務成功率α是成功完成的任務數與總試驗次數的比值，如式（6）所示。

其中，Nsucc為成功完成的任務數，Ntotal為總實驗次數。

2.2 仿真結果與分析

2.2.1 可靠性性能

圖4比較了不同業務調度模式在不同環境下的可靠性性能。其中，任務量大小為100 Mbit。值得注意的是，衛星的故障概率包括衛星器件故障概率和衛星受到環境干擾（如發生“0-1翻轉”等）導致任務失敗的故障概率。因此，為不失一般性，本節設置了4種不同環境：最佳環境、良好環境、惡劣環境、混合環境。在最佳環境中，衛星的故障概率設置為0，即χi=0；在良好環境中，假定衛星的故障概率均勻分布，即χi～U([0,0.5%])；在惡劣環境中，χi～U([1%,3%])；在混合環境中，某些衛星的故障概率為χi～U([0,0.5%])，另外一些衛星的故障概率為χi～U([1%,3%])。由圖 4 可知，在最佳環境下，分布式業務調度和集中式業務調度的任務成功率均為100%。這是因為在理想環境中，不會出現衛星故障，任務能100%完成。然而，由于理想情況根本不存在，因此本文研究了3種現實環境下的可靠性性能。由圖5可知，集中式業務調度模式的可靠性性能在各種環境下均比較低。惡劣環境中，集中式業務調度模式的任務成功率僅為55.0%。相比之下，分布式業務調度的任務成功率為84.4%。這是因為，分布式業務調度僅須保障當前執行業務節點在執行業務期間不會發生故障，而集中式業務調度模式須保障業務調度方案中所有節點在執行任務之前均不會發生故障。

▲圖4 不同環境下不同業務調度模式的可靠性性能比較

2.2.2 時延性能

圖5比較了不同計算范式的時延性能，即云計算、本地計算和協同計算。其中，協同計算可進一步分為集中式業務調度和分布式業務調度，并且工作環境為混合環境。由圖5可知，當任務量較小時，3種計算范式均表現出良好的時延性能。但隨著任務量的增加，云計算的時延也迅速增加。這是因為云計算中心距衛星較遠，導致傳輸時延較高。而本地計算雖可避免較高的通信開銷，但由于單星計算能力有限，計算時延也較高。對于協同計算，由于衛星集群具備強大的計算能力，且衛星之間距離較近，因此，隨著數據量的增加，其時延仍在可接受范圍之內。

▲圖5 不同計算范式的時延性能比較

由圖5可知，分布式業務調度的時延略高于集中式業務調度。但應注意到，混合環境下，在處理100 Mbit的數據時，分布式業務調度的任務成功率比集中式業務調度提升了21.3%，而時延僅增加了6.21%，即以較小且可接受的時延為代價換取了可靠性性能的大幅度提升。

2.2.3 多種算法可靠性及時延性能分析

本節比較了基于TSE指標的算法（記為Proposed）同隨機式（記為Random）和貪婪式（記為Greedy）算法的時延性能和可靠性性能，分別如圖6、圖7所示。

▲圖6 不同算法時延性能比較

▲圖7 不同算法可靠性性能比較

圖6比較了不同算法的時延性能。其中，工作環境為混合環境。由圖6可知，當任務量較小時，3種算法時延差別不明顯。而隨著任務量的增加，所提算法的時延明顯低于其他兩種算法。例如，當任務量為500 Mbit時，Proposed、Greedy、Random的時延具體分別為76.14 s、83.08 s、90.94 s，所提算法比其他兩種算法的時延分分別低了8.35%、16.27%。這是因為，Random算法隨機選取下一跳節點，并未考慮其計算能力，同時Greedy算法選取計算能力最強的節點作為下一跳節點，并未考慮邊的傳輸能力和傳輸方向，因此時延性能均不如Pro?posed算法。

圖7比較了不同算法的可靠性性能，其中，任務量為100 Mbit。可以看出，除最佳環境外，在其他環境下所提算法的任務成功率均高于其他兩種算法。這是因為Random和Greedy算法在選擇下一跳節點時，均未考慮節點的故障概率，因此可靠性性能不如所提算法。

3 結束語

本文面向分布式LEO集群，提出了分布式端到端信息處理技術。首先我們構建TEG將LEO集群動態拓撲穩態化，隨后構建端到端信息處理理論模型并提出分布式業務調度算法。該算法通過綜合考慮計算資源、通信資源、至目標節點跳數、節點故障率多維信息來選取下一跳節點，并逐步完成數據的傳輸與計算。仿真結果表明，所提分布式業務調度技術以犧牲較小時延為代價，有效地提升了業務的執行成功率。

致謝

本研究得到西安電子科技大學綜合業務網理論及關鍵技術國家重點實驗室程文馳老師的幫助，謹致謝意！