周錦雯,劉乃金,陳清霞

錢學(xué)森空間技術(shù)實(shí)驗室,北京 100094

1 引言

隨著衛(wèi)星技術(shù)的發(fā)展,在軌衛(wèi)星數(shù)量和衛(wèi)星星座規(guī)模不斷擴(kuò)大,由此衍生出各種衛(wèi)星應(yīng)用和更多的計算需求,衛(wèi)星節(jié)點(diǎn)從數(shù)據(jù)中繼向集群化網(wǎng)絡(luò)化的方向發(fā)展[1]。新一代衛(wèi)星網(wǎng)絡(luò)集成不同軌道衛(wèi)星,可以實(shí)現(xiàn)全球覆蓋、隨時接入、按需服務(wù)[2]。特別是在人口稀少、缺乏電信基礎(chǔ)設(shè)施的特殊區(qū)域,配備了計算資源和存儲資源的衛(wèi)星形成了衛(wèi)星邊緣計算集群,便于缺少計算資源的地面用戶將計算任務(wù)遷移到邊緣衛(wèi)星節(jié)點(diǎn)以獲得更高效快捷的服務(wù)[3]。低軌道衛(wèi)星引入的傳播延遲較低,正逐漸成為未來綜合衛(wèi)星系統(tǒng)的重要組成部分。雖然其星上處理能力通常有限,但低軌星座網(wǎng)絡(luò)(特別是超級星座LEO網(wǎng)絡(luò))中的多顆衛(wèi)星可以形成一個虛擬資源池,如果能整合多顆衛(wèi)星資源協(xié)同處理計算任務(wù),那么LEO衛(wèi)星通信網(wǎng)絡(luò)將會具有地面移動通信系統(tǒng)無法比擬的優(yōu)勢和潛能。

目前,得益于低軌星座的發(fā)展,具有計算和存儲資源的衛(wèi)星節(jié)點(diǎn)可以形成邊緣計算集群,利用星間鏈路實(shí)現(xiàn)協(xié)同服務(wù),可有效降低用戶響應(yīng)時延。邊緣計算是指將計算單元轉(zhuǎn)移到用戶設(shè)備附近的接入節(jié)點(diǎn),或者在用戶設(shè)備[4]本地處理數(shù)據(jù)的技術(shù)。通過在低軌衛(wèi)星部署邊緣服務(wù)器,可以避免將應(yīng)用程序產(chǎn)生的流量回調(diào)到遠(yuǎn)程數(shù)據(jù)中心,從而大大減少訪問延遲,有效地利用無線電資源。越來越多的學(xué)者開始關(guān)注邊緣計算增強(qiáng)的衛(wèi)星集群問題,主要集中在衛(wèi)星邊緣計算架構(gòu)、計算卸載等方面[5]。

對于衛(wèi)星邊緣計算架構(gòu),文獻(xiàn)[6]對未來空間網(wǎng)絡(luò)的多層邊緣計算架構(gòu)設(shè)計和異構(gòu)邊緣計算資源協(xié)同調(diào)度進(jìn)行了討論。文獻(xiàn)[7]為太空-空中-地面-水上綜合網(wǎng)絡(luò)(SAGAIN)提出了一種新的架構(gòu)——面向任務(wù)的智能網(wǎng)絡(luò)架構(gòu)(TOINA),以提供個性化的網(wǎng)絡(luò)服務(wù)。雖然上述研究對衛(wèi)星邊緣計算網(wǎng)絡(luò)的聯(lián)合任務(wù)卸載和資源分配等問題進(jìn)行了討論,但沒有詳細(xì)給出計算卸載的方法。

針對計算卸載方法的研究,文獻(xiàn)[8]提出了基于時延、計算能力和傳輸功率衰減歸一化加權(quán)和的網(wǎng)絡(luò)片調(diào)度方法,以優(yōu)化卸載速率。文獻(xiàn)[9]引入了一種雙邊緣計算架構(gòu),利用最小代價匹配算法優(yōu)化邊緣服務(wù)器上的系統(tǒng)能耗和卸載任務(wù)的平均延遲。文獻(xiàn)[10]針對衛(wèi)星網(wǎng)絡(luò)提出了一種基于動態(tài)優(yōu)先隊列的時延優(yōu)化調(diào)度算法(SDPLS),以縮短任務(wù)響應(yīng)延遲。文獻(xiàn)[11]研究了聯(lián)合計算和通信資源管理問題,提出了一個博弈理論用于衛(wèi)星通信網(wǎng)絡(luò),以最小化計算密集型應(yīng)用的執(zhí)行延遲。文獻(xiàn)[12]提出了一個計算卸載博弈框架,并基于排隊論優(yōu)化任務(wù)的響應(yīng)時間和能量消耗。文獻(xiàn)[13]研究了混合云和邊緣計算網(wǎng)絡(luò)的計算卸載決策,使用數(shù)學(xué)規(guī)劃法來減少地面用戶的總能耗。為了最大限度地降低移動設(shè)備的能耗,文獻(xiàn)[14]提出了一種節(jié)能計算卸載與資源分配算法(E-CORA)。雖然上述工作研究了針對邊緣計算增強(qiáng)的低軌衛(wèi)星網(wǎng)絡(luò)任務(wù)卸載問題,但都沒有考慮到多顆LEO衛(wèi)星之間的協(xié)同計算。該問題難點(diǎn)在于低軌星座拓?fù)浣Y(jié)構(gòu)多變,需要對衛(wèi)星間鏈路的距離、帶寬和可用性進(jìn)行動態(tài)建模。

因此對邊緣增強(qiáng)的低軌衛(wèi)星網(wǎng)絡(luò)進(jìn)行研究,其通過LEO集群協(xié)同處理用戶產(chǎn)生的任務(wù)。結(jié)合星座拓?fù)涮攸c(diǎn)進(jìn)行建模,提出并優(yōu)化了一種適用于低軌衛(wèi)星集群的協(xié)同計算架構(gòu)和計算卸載過程的基于分布式深度學(xué)習(xí)算法的衛(wèi)星邊緣計算卸載算法(deep learning-based offloading algorithm,DLOA),該算法可提高衛(wèi)星網(wǎng)絡(luò)計算業(yè)務(wù)的服務(wù)質(zhì)量。

2 系統(tǒng)模型與問題建模

考慮一個由LEO衛(wèi)星星座和多個地面用戶組成的典型場景,LEO衛(wèi)星通過星間鏈路(ISL)實(shí)現(xiàn)多顆衛(wèi)星的協(xié)同處理,每顆衛(wèi)星與相鄰?fù)蜻\(yùn)行軌道面的相鄰節(jié)點(diǎn)以及同軌道面的相鄰節(jié)點(diǎn)可組成相對穩(wěn)定的拓?fù)渚W(wǎng)絡(luò),實(shí)現(xiàn)衛(wèi)星間的信息交換。在t時刻下,某一衛(wèi)星接收到覆蓋范圍內(nèi)地面用戶產(chǎn)生的具有時間限制的任務(wù)請求,假設(shè)該任務(wù)組的任務(wù)量較大且彼此間獨(dú)立,該衛(wèi)星根據(jù)任務(wù)的資源需求與其他衛(wèi)星組成臨時任務(wù)組。任務(wù)組中的節(jié)點(diǎn)通過DNS進(jìn)行注冊,接收請求衛(wèi)星自動成為主節(jié)點(diǎn),其他衛(wèi)星屬于從節(jié)點(diǎn)。臨時主節(jié)點(diǎn)作為任務(wù)組訪問節(jié)點(diǎn)需要負(fù)責(zé)任務(wù)卸載和資源調(diào)度決策,其他節(jié)點(diǎn)作為負(fù)載節(jié)點(diǎn)執(zhí)行特定的計算任務(wù)。任務(wù)處理流程如圖1所示。

圖1 任務(wù)的計算卸載過程Fig.1 Collaboratively computing among multiple LEO satellites

2.1 網(wǎng)絡(luò)狀態(tài)和任務(wù)集模型

考慮到衛(wèi)星網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)的時變特性,用時變參數(shù)來描述衛(wèi)星拓?fù)浼百Y源狀態(tài)。對于時刻t下,一個可用的衛(wèi)星計算域,其節(jié)點(diǎn)數(shù)記為N,用集合V={vi|i∈[1,N]}來表示該網(wǎng)絡(luò)的節(jié)點(diǎn)集合,各節(jié)點(diǎn)之間的傳輸速率用集合R(t)來表示,記為R(t)={rij(t)|i,j∈[1,N],rij(t)∈{0,Risl}},rij(t)表示節(jié)點(diǎn)vi和vj間的傳輸速率,rij(t)=0時,表示節(jié)點(diǎn)vi和vj之間沒有直接連接的星間鏈路,這兩個節(jié)點(diǎn)需要從中間節(jié)點(diǎn)轉(zhuǎn)發(fā)才能實(shí)現(xiàn)通信,rij(t)=Risl表示節(jié)點(diǎn)vi和vj在當(dāng)前時刻下可直接通信。Risl為星間鏈路固有傳輸速率,受服務(wù)器硬件資源和能耗約束。另外,rij和rji默認(rèn)表示同一衛(wèi)星間鏈路的傳輸,故rij=rji。

2.2 通信模型

綜上所述,將任務(wù)m卸載至主節(jié)點(diǎn),再由主節(jié)點(diǎn)分發(fā)至節(jié)點(diǎn)vn,直至完成計算并將結(jié)果返回用戶這一過程中的總通信時延和總通信能耗表達(dá)式為:

2.3 計算模型

2.4 問題建模

將任務(wù)m卸載到衛(wèi)星vn的總時延包括通信時延和計算時延,總能耗包括通信能耗和計算能耗,因此可將總時延和總能耗分別表示為:

將需要卸載給衛(wèi)星集群的獨(dú)立任務(wù)總數(shù)定義為M,集群中能夠提供計算資源的衛(wèi)星數(shù)量定義為N?？紤]一個由主節(jié)點(diǎn)衛(wèi)星與少量衛(wèi)星組成邊緣計算拓?fù)渚W(wǎng)絡(luò),主節(jié)點(diǎn)經(jīng)過星間鏈路將任務(wù)卸載至從節(jié)點(diǎn),將所有用戶輸入數(shù)據(jù)的任務(wù)需求IM(t)、邊緣衛(wèi)星集的算力大小Fv(t)、各節(jié)點(diǎn)之間的傳輸速率R(t)以及節(jié)點(diǎn)間距離D(t)合記為輸入狀態(tài)st,為了使完成所有用戶任務(wù)的總延遲和相應(yīng)的能源消耗最小化,首先引入一個系統(tǒng)效用Q(st,a,c),定義為能源消耗和任務(wù)完成延遲的加權(quán)和:

式中:a={amn|m=1,2,…,M;n=1,2,…,N},amn表示是否將第m個計算任務(wù)卸載給第n個衛(wèi)星,cmn表示節(jié)點(diǎn)vn為任務(wù)m分配的計算資源比例,c={cmn|m=1,2,…,M;n=1,2,…,N},ζ1,ζ2∈[0,1]分別表示時延和能耗的標(biāo)量權(quán)重。然后,通過聯(lián)合優(yōu)化每個任務(wù)的卸載決策{amn)和節(jié)點(diǎn)vn為任務(wù)m分配的計算資源比例{cmn),得到一個優(yōu)化問題(P1),以最小化Q(st,a,c):

優(yōu)化問題(P1)是一個動態(tài)混合整數(shù)規(guī)劃問題,涉及連續(xù)變量cmn和二進(jìn)制變量amn的選擇,難以直接求解。在下一節(jié)中,將研究一種基于分布式深度學(xué)習(xí)的衛(wèi)星邊緣計算卸載算法求解該問題。

3 基于分布式深度學(xué)習(xí)的衛(wèi)星邊緣計算卸載算法

上文將衛(wèi)星邊緣計算場景下的多衛(wèi)星協(xié)同計算卸載問題表示為混合整數(shù)規(guī)劃問題。這類問題已被證明是NP-hard的,在多項式時間內(nèi)無法得到問題的最優(yōu)解,并且目標(biāo)二進(jìn)制卸載決策集的決策空間大小為2MN,該數(shù)量隨著任務(wù)數(shù)量和衛(wèi)星計算域中節(jié)點(diǎn)個數(shù)的增加而指數(shù)級增加,直接在數(shù)量龐大的決策集中尋找最優(yōu)解是相當(dāng)困難的。因此,在本節(jié)中,采用一種基于分布式深度學(xué)習(xí)的DLOA算法[16]。

使用的基于深度學(xué)習(xí)的卸載算法體系結(jié)構(gòu)如圖2所示,對于每個輸入st,使用B個分布式DNN高效地生成B個候選卸載動作集{ab|b∈B},其中b={1,2,…,B},ab的維數(shù)是M×N。圖3為單個分布式DNN的決策過程。當(dāng)B個卸載動作生成之后,原來的優(yōu)化問題(P1)就變成了資源分配問題(P2),即

cmn∈[0,1]

圖2 DLOA算法結(jié)構(gòu)Fig.2 Architecture of DLOA algorithm

圖3 單個DNN卸載決策器結(jié)構(gòu)Fig.3 Architecture of an offloading actor

問題(P2)及其約束條件都是凸的,可以將該問題寫成拉格朗日函數(shù)并對其求極小值,然后采用牛頓法對新的目標(biāo)函數(shù)求一階和二階導(dǎo)數(shù),選擇合適的初始值代入牛頓法迭代公式,不斷迭代直至得到最優(yōu)解,該解即為所需的資源分配的結(jié)果。

在解決計算資源分配問題(P2)后,在所有B個候選動作中選擇使得Q*(st,a)最小的卸載動作a*,這個選定的a*將作為相對于輸入st的二進(jìn)制卸載決策輸出。

一旦獲得了最佳的卸載決策a*,將它與輸入構(gòu)成一個有標(biāo)簽數(shù)據(jù)的新條目(st,a*)存儲在有限大小的內(nèi)存結(jié)構(gòu)中,當(dāng)內(nèi)存被存滿之后,最先被存儲的數(shù)據(jù)條目將被丟棄,這些生成的標(biāo)記數(shù)據(jù)會被進(jìn)一步用來訓(xùn)練所有B個DNN。

該算法沒有存儲整個數(shù)據(jù)記憶來訓(xùn)練DNN,而是采用了有限內(nèi)存大小的經(jīng)驗回放,所有的DNN共享相同的內(nèi)存,每個DNN從內(nèi)存中隨機(jī)抽取一批數(shù)據(jù)樣本。在這里內(nèi)存結(jié)構(gòu)的有限大小設(shè)計有助于提高數(shù)據(jù)效率,因為新生成的數(shù)據(jù)條目比舊的優(yōu)先級更高。采用梯度下降算法優(yōu)化各DNN的網(wǎng)絡(luò)參數(shù)值θb以最小化交叉熵?fù)p失,將交叉熵?fù)p失定義為:

L(θb)=-aTlnfθb(st)-

(1-a)Tln [1-fθb(st)]

算法初始時,用隨機(jī)參數(shù)值θb初始化所有的DNN,內(nèi)存為空。通過在B個卸載動作的選擇,該算法有望收斂到最優(yōu)卸載動作。

在下一節(jié)中,將對該算法進(jìn)行數(shù)值研究。

4 算法仿真與評估

4.1 參數(shù)設(shè)置

在仿真實(shí)驗中,在主節(jié)點(diǎn)覆蓋范圍內(nèi)的多個地面用戶生成大量需要應(yīng)急響應(yīng)的獨(dú)立任務(wù),并將這些任務(wù)卸載到用戶可見的衛(wèi)星主節(jié)點(diǎn)進(jìn)行處理,由衛(wèi)星主節(jié)點(diǎn)運(yùn)行卸載算法將每個任務(wù)卸載至合適的衛(wèi)星節(jié)點(diǎn)或者自行處理。假定所有任務(wù)的輸入數(shù)據(jù)大小隨機(jī)分布在10M～50M之間,各節(jié)點(diǎn)發(fā)送功率皆為10W,衛(wèi)星節(jié)點(diǎn)處理器的計算頻率處于2～6GHz之間,任務(wù)截止時間由(0.6～0.8)×∑MImγm/∑VpV(t)計算。為了評估不同的卸載算法,根據(jù)該協(xié)同計算網(wǎng)絡(luò)配置預(yù)先生成了40000組輸入數(shù)據(jù)。對于每組輸入數(shù)據(jù),通過枚舉空間大小為2MN的二進(jìn)制卸載操作組合來找到最優(yōu)卸載操作,然后選取最優(yōu)的一個。定義其他算法得出的系統(tǒng)效用與最優(yōu)卸載的系統(tǒng)效用之比為系統(tǒng)效用比,該比例越接近1,說明生成的卸載動作就越好。

4.2 收斂特性研究

首先研究算法參數(shù)對該算法收斂性的影響。為了獲得最優(yōu)的系統(tǒng)效用值,設(shè)置較少的任務(wù)數(shù)以便生成有限且適當(dāng)?shù)拿杜e空間。圖4比較了采用相同隱藏層結(jié)構(gòu)(同構(gòu)DLOA)和不同隱藏層結(jié)構(gòu)(異構(gòu)Het.DLOA)的收斂性,二者都使用了3個全連接的DNN。為了公平比較,將異構(gòu)DLOA中每個DNN的互連復(fù)雜度保持在DLOA中的相同規(guī)模。每個DNN網(wǎng)絡(luò)中的神經(jīng)元數(shù)量見表1 。異構(gòu)DLOA在5000步達(dá)到收斂時,同構(gòu)DLOA滯后900步左右達(dá)到收斂,采用異構(gòu)DNN的收斂速度較同構(gòu)DNN收斂速度提升18%,此外異構(gòu)DLOA卸載結(jié)果更接近最優(yōu)值且更加平穩(wěn)。

圖4 同構(gòu)DNN網(wǎng)絡(luò)和異構(gòu)DNN網(wǎng)絡(luò)的收斂性Fig.4 Convergence performance of DLOA and heterogeneous DLOA

表1 同構(gòu)網(wǎng)絡(luò)和異構(gòu)網(wǎng)絡(luò)的隱藏層結(jié)構(gòu)

在圖5中,研究了不同數(shù)量DNN下的異構(gòu)DLOA算法。DNN的數(shù)量越多,算法的收斂速度越快,但同時也需要更多的并行計算資源。從圖可知使用較少的DNN(大于等于3個)就可以收斂于局部最優(yōu)。而當(dāng)DNN個數(shù)為1或者2時,算法收斂效果不佳,但是使用更多的DNN只能少量提升算法的收斂速度,所以本實(shí)驗最終設(shè)置的DNN個數(shù)為3。

4.3 算法比較

為了評估資源分配方案的有效性,采用了兩種參考方案,并在系統(tǒng)效用方面進(jìn)行了比較。兩種資源分配方案是平均資源分配(ARA)和優(yōu)化的資源分配(ORA)方案,平均資源分配(ARA)指的是所有衛(wèi)星節(jié)點(diǎn)對分派的任務(wù)進(jìn)行計算資源均分,優(yōu)化的資源分配(ORA)指的是采用最優(yōu)化工具進(jìn)行計算資源分配的方案。如圖6和圖7所示,隨著ζ1或ζ2的增加,所有方案的總開銷成本都增加,異構(gòu)DLOA比同構(gòu)DLOA方案系統(tǒng)效用更低,表現(xiàn)更好,同時優(yōu)化的資源分配方案優(yōu)于平均資源分配方案。

圖6 ζ2等于1時,不同ζ1下的策略比較Fig.6 System utility under different ζ1 for different resource allocation algorithms

圖7 ζ1等于1時,不同ζ2下的策略比較Fig.7 System utility under different ζ2 for different resource allocation algorithms

下面將研究不同策略下的任務(wù)按時交付情況,共評估了以下幾種算法及策略,分別是單星計算、二進(jìn)制粒子群(BPSO)算法、同構(gòu)DLOA算法以及異構(gòu)DLOA算法。單星計算意味著所有任務(wù)由直接可見的單顆衛(wèi)星計算,沒有協(xié)同計算過程,該方案耗時最大。二進(jìn)制粒子群算法模擬鳥群飛行覓食的行為,是一個參數(shù)少、簡單易行、收斂速度快的智能優(yōu)化算法,能比較快速地得到較優(yōu)的結(jié)果。圖8顯示了不同策略下,任務(wù)數(shù)量對任務(wù)完成率的影響?？梢钥闯?隨著任務(wù)數(shù)量的增加,所有策略下任務(wù)的完成率會降低。這是由于隨著用戶數(shù)量的增加,等待計算的任務(wù)數(shù)量會增加,資源短缺會導(dǎo)致任務(wù)完成率下降。另外,為了保證仿真結(jié)果的有效性,圖中的每個點(diǎn)都是經(jīng)過多次試驗取平均值得到的,每次試驗持續(xù)20000個時間槽?？梢钥吹紻LOA算法的性能優(yōu)于二進(jìn)制粒子群算法,而單星計算策略的性能最差。這是因為DLOA算法側(cè)重于減少任務(wù)的總延遲,另一方面,智能優(yōu)化算法如BPSO算法只能優(yōu)化某一特定時隙的決策,而不能對多個時隙的卸載和調(diào)度決策進(jìn)行連續(xù)優(yōu)化,且算法每一步都需要迭代,帶來了較高的時間成本,而DLOA算法可以在決策過程中不斷積累經(jīng)驗來優(yōu)化決策。使用異構(gòu)DNN的DLOA算法的任務(wù)完成率高于使用同構(gòu)DNN的DLOA算法。此外采用優(yōu)化的資源分配(ORA)方案的也優(yōu)于平均資源分配(ARA)方案。優(yōu)化的資源分配(ORA)方案會將更多的資源分配給難以在有限的延遲內(nèi)完成的任務(wù)?？偟膩碚f,同時采用異構(gòu)DNN和優(yōu)化資源分配方案的DLOA算法能夠更有效提高任務(wù)的完成率,且任務(wù)之間具有公平性,與采用同構(gòu)DNN和平均分配資源方案的DLOA算法相比,任務(wù)完成率提高了5%左右,與單星運(yùn)算方案任務(wù)相比完成率提升1倍左右,與粒子群算法方案相比提升20%左右。

圖8 不同任務(wù)規(guī)模下的任務(wù)完成率Fig.8 Task completion rate under different number of tasks for different algorithms

5 結(jié)論

研究了基于分布式深度學(xué)習(xí)的衛(wèi)星邊緣計算卸載算法(DLOA),以保證網(wǎng)絡(luò)的服務(wù)質(zhì)量,最大限度地減少衛(wèi)星的時延和能量消耗。該算法利用多個DNN的優(yōu)勢,在不需要人工標(biāo)記數(shù)據(jù)的情況下生成接近最優(yōu)解。采用異構(gòu)DNN結(jié)構(gòu)比同構(gòu)DNN能獲得更快和更優(yōu)的收斂效果。采用更多的DNN個數(shù)能加快算法的收斂速度,但是超過3個對收斂速度的優(yōu)化并不明顯,因此,少量DNN就可獲得較優(yōu)的結(jié)果并節(jié)約算力資源。實(shí)驗表明,采用DLOA算法方案的任務(wù)完成率顯著優(yōu)于采用單衛(wèi)星計算、二進(jìn)制粒子群(BPSO)算法方案。此外,利用異構(gòu)DNN和優(yōu)化的資源分配(ORA)方案能進(jìn)一步提升DLOA算法本身的性能,仿真結(jié)果表明優(yōu)化的方案能夠獲得更低的系統(tǒng)效用值和更高的任務(wù)完成率。