基于多維梯度的衛(wèi)星集群高可靠協(xié)同計算方法

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

（西安電子科技大學(xué)綜合業(yè)務(wù)網(wǎng)理論及關(guān)鍵技術(shù)國家重點實驗室，中國 西安 710071）

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

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

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

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

1 系統(tǒng)模型

分布式LEO集群系統(tǒng)架構(gòu)如圖1所示。其中，為不失一般性，假設(shè)地面站定時向LEO集群廣播全局拓?fù)湫畔ⅲ款w衛(wèi)星可計算自身到結(jié)果接收衛(wèi)星的跳數(shù)。當(dāng)任務(wù)到達(dá)時，每顆衛(wèi)星根據(jù)自身相鄰節(jié)點的信息逐步選擇下一節(jié)點，并完成端到端業(yè)務(wù)計算。

▲圖1 低軌集群系統(tǒng)架構(gòu)圖

1.1 LEO網(wǎng)絡(luò)模型

為屏蔽LEO集群的動態(tài)性，本節(jié)依托LEO衛(wèi)星運(yùn)行軌道參數(shù)構(gòu)建TEG模型。

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

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

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

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

基于式（5），通過遍歷可獲得LEO集群拓?fù)洹４藭r，以LEO集群某一時刻狀態(tài)為起點，將系統(tǒng)運(yùn)行周期T等分為n個連續(xù)時隙，長度定義為Δ=T/n。假設(shè)時隙內(nèi)拓?fù)浞€(wěn)定不變，則LEO集群N可表示為N=(NT,ET)，其中NT={N1,…,Nn}為節(jié)點集合，ET為邊集合，如圖2所示。

▲圖2 低軌集群時空擴(kuò)展圖模型

（1）時隙內(nèi)邊的權(quán)重。任意時隙?q∈T內(nèi)，邊的權(quán)重為節(jié)點傳輸單位數(shù)據(jù)量到節(jié)點的時延，如式（6）所示：

則q時隙內(nèi)LEO集群可表示為式（7）：

（2）時隙間邊的權(quán)重。數(shù)據(jù)在傳輸過程中可能存在由鏈路中斷所導(dǎo)致傳輸失敗的情況，因此，需要定義時隙間邊的權(quán)重，即數(shù)據(jù)到達(dá)衛(wèi)星節(jié)點時，當(dāng)前時隙的剩余時間，如式（8）所示：

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

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

1.2 端到端業(yè)務(wù)計算理論模型

基于TEG，本節(jié)提出端到端業(yè)務(wù)計算理論模型。為不失一般性，本節(jié)按照子業(yè)務(wù)間的依賴關(guān)系建立業(yè)務(wù)有向無環(huán)圖（DAG）模型。同時，根據(jù)文獻(xiàn)[15]，任何結(jié)構(gòu)的DAG均可解析為串行DAG，因此，本文僅考慮串行DAG。

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

▲圖3 DAG至TEG的映射示例

（1）節(jié)點映射規(guī)則

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

（2）邊映射規(guī)則

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

1.3 分布式端到端業(yè)務(wù)調(diào)度算法

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

基于上述端到端業(yè)務(wù)計算理論模型分析，算法需統(tǒng)一考慮節(jié)點的計算能力和鏈路狀態(tài)以實現(xiàn)端到端業(yè)務(wù)計算，而由于缺乏中心節(jié)點的統(tǒng)一調(diào)度，僅考慮計算能力和鏈路狀態(tài)可能會導(dǎo)致數(shù)據(jù)的反向傳輸。因此，需要引入目標(biāo)節(jié)點位置信息以實現(xiàn)數(shù)據(jù)的定向傳輸，同時為了保證數(shù)據(jù)傳輸?shù)目煽啃?，?jié)點故障率也需要被考慮進(jìn)算法中?；谝陨戏治觯竟?jié)定義TSE梯度指標(biāo)，綜合考慮了節(jié)點的計算能力、鏈路狀態(tài)、故障率、距目標(biāo)節(jié)點跳數(shù)多維梯度信息，如式（13）所示：

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

算法1分布式端到端業(yè)務(wù)調(diào)度算法

輸入：DAG模型，TEG

步驟1：任務(wù)到來時，通過廣播發(fā)現(xiàn)鄰居節(jié)點并獲取其多維狀態(tài)信息，包括計算能力、鏈路狀態(tài)、故障率、距目標(biāo)節(jié)點跳數(shù)；

步驟2：根據(jù)式（13）計算各鄰居節(jié)點的TSE指標(biāo)，并選取TSE最小的節(jié)點為下一跳節(jié)點；

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

輸出：下一跳節(jié)點

2 仿真與評估

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

2.1 仿真場景及參數(shù)設(shè)置

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

▼表1 基本參數(shù)

為了分析與評估性能，我們考慮端到端業(yè)務(wù)處理時延和任務(wù)成功率兩個指標(biāo)。

（1）端到端業(yè)務(wù)處理時延

基于1.2節(jié)的DAG至TEG的調(diào)度規(guī)則，端到端業(yè)務(wù)處理時延可建模如下。

進(jìn)行到子任務(wù)φi時的處理時延如式（14）所示：

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

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

（2）任務(wù)成功率α

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

其中，Nsucc為成功完成的任務(wù)數(shù)，Ntotal為總實驗次數(shù)。

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

2.2.1 可靠性性能

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

▲圖4 不同環(huán)境下不同業(yè)務(wù)調(diào)度模式的可靠性性能比較

2.2.2 時延性能

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

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

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

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

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

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

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

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

圖7比較了不同算法的可靠性性能，其中，任務(wù)量為100 Mbit?？梢钥闯?，除最佳環(huán)境外，在其他環(huán)境下所提算法的任務(wù)成功率均高于其他兩種算法。這是因為Random和Greedy算法在選擇下一跳節(jié)點時，均未考慮節(jié)點的故障概率，因此可靠性性能不如所提算法。

3 結(jié)束語

本文面向分布式LEO集群，提出了分布式端到端信息處理技術(shù)。首先我們構(gòu)建TEG將LEO集群動態(tài)拓?fù)浞€(wěn)態(tài)化，隨后構(gòu)建端到端信息處理理論模型并提出分布式業(yè)務(wù)調(diào)度算法。該算法通過綜合考慮計算資源、通信資源、至目標(biāo)節(jié)點跳數(shù)、節(jié)點故障率多維信息來選取下一跳節(jié)點，并逐步完成數(shù)據(jù)的傳輸與計算。仿真結(jié)果表明，所提分布式業(yè)務(wù)調(diào)度技術(shù)以犧牲較小時延為代價，有效地提升了業(yè)務(wù)的執(zhí)行成功率。

致謝

本研究得到西安電子科技大學(xué)綜合業(yè)務(wù)網(wǎng)理論及關(guān)鍵技術(shù)國家重點實驗室程文馳老師的幫助，謹(jǐn)致謝意！