天地一體化網(wǎng)絡(luò)分散式算力路由控制策略

李洪鈞 任保全 鞏向武 國曉博 任智源

1.軍事科學(xué)院系統(tǒng)工程研究院系統(tǒng)總體研究所 北京 100101 2.軍事科學(xué)院系統(tǒng)工程研究院網(wǎng)絡(luò)信息研究所 北京 100141 3.中國電子科技集團(tuán)公司第五十四研究所 河北 石家莊 050081 4.西安電子科技大學(xué)綜合業(yè)務(wù)網(wǎng)理論及關(guān)鍵技術(shù)國家重點(diǎn)實(shí)驗室 陜西 西安 710071

天地一體化網(wǎng)絡(luò)（space-ground integration networks, SGIN）能夠為用戶提供全球覆蓋范圍、快速建立聯(lián)接、強(qiáng)大機(jī)動性能、信息實(shí)時處理等能力[1], 在全球偵察情報、全域聯(lián)合指揮控制、天基信息支援、天地一體化智能協(xié)同抗干擾等各類軍事應(yīng)用中已成為研究熱點(diǎn)[2-4]. 隨著星間鏈路和星載計算處理技術(shù)的發(fā)展,大量數(shù)據(jù)傳輸、實(shí)時處理業(yè)務(wù)紛紛出現(xiàn),對SGIN端到端傳輸能力、星上處理能力提出更高要求[5-8], 而路由控制將成為天地一體化網(wǎng)絡(luò)高效聯(lián)接和傳輸信息的核心基礎(chǔ).

針對上述挑戰(zhàn), 算力路由（computing-dependent route, CDR）作為算力網(wǎng)絡(luò)中的關(guān)鍵技術(shù)被提出, 是一種將網(wǎng)絡(luò)中的算力與傳輸結(jié)合起來的一種路由范式[9], 這種特質(zhì)使得算力路由可以滿足大量遙感圖像傳輸和處理等等業(yè)務(wù)的需求. 但是, 現(xiàn)階段的算力路由主要針對地面網(wǎng)絡(luò)[10].同時, 為了屏蔽信息同步所帶來的損耗, 算力路由僅適用于靜態(tài)的網(wǎng)絡(luò)中, 無法適應(yīng)SGIN 的高動態(tài)環(huán)境. 因此, 本文重點(diǎn)研究SGIN 場景下的算力路由方法.

但是, 在SGIN 中實(shí)現(xiàn)算力路由會面臨諸多問題.一般情況下, 路由和計算策略應(yīng)該由計算能力強(qiáng)大的控制中心進(jìn)行控制. 然而, 由于SGIN 網(wǎng)絡(luò)節(jié)點(diǎn)的分步范圍廣、數(shù)量大, 很難找到一個控制中心對全網(wǎng)信息進(jìn)行統(tǒng)一管理. 因此, 網(wǎng)絡(luò)的無中心特點(diǎn)給分散式算例路由（dispersed computing-dependent route,DCDR）控制策略的制定帶來很大的挑戰(zhàn). 許多學(xué)者在無中心動態(tài)網(wǎng)絡(luò)的分散式算法方面有了初步的研究, 如S. Jo?ilo 系統(tǒng)平均參數(shù)作為分散式計算和路由策略制定的依據(jù),但這種方法不適用于動態(tài)網(wǎng)絡(luò)[11]. 為了適應(yīng)網(wǎng)絡(luò)動態(tài)性特點(diǎn), 一些基于廣播的算法被提出[12-13]. 但這些方法均忽略廣播帶來的時延損耗, 不適用于天地一體化網(wǎng)絡(luò)這種遠(yuǎn)距離傳輸?shù)膱鼍?

因此, 本文提出一種面向SGIN 的DCDR 控制策略. 通過將任務(wù)的處理步驟建模為有向無環(huán)圖（directed acyclic graph, DAG）模型, 構(gòu)建一個由DAG 向SGIN 中單條路徑映射的映射問題. 設(shè)計了一個改進(jìn)的定向擴(kuò)散算法（improved directional diffusion algorithm, IDDA）, 并將廣播所產(chǎn)生的時延考慮在內(nèi). 在此算法的支持下, 實(shí)現(xiàn)了任務(wù)邊傳輸、邊計算、邊制定映射策略的目標(biāo), 并將分散式算法的抗毀性優(yōu)點(diǎn)發(fā)揮出來.

1 相關(guān)工作

隨著云計算、霧計算和邊緣計算[14-16]的發(fā)展, 分布式計算已經(jīng)成為當(dāng)前算網(wǎng)融合的發(fā)展主流. 文獻(xiàn)[17]將邊緣計算擴(kuò)展到天空地海一體化網(wǎng)絡(luò)（spaceair-ground-aqua integrated network, SAGAIN）, 將衛(wèi)星視為移動邊緣計算節(jié)點(diǎn), 提供必要的計算和緩存功能. 算力網(wǎng)絡(luò)作為一種算網(wǎng)融合的新技術(shù)方案, 能夠通過網(wǎng)絡(luò)算力間深度的連接, 將網(wǎng)絡(luò)中無處不在的計算資源進(jìn)行靈活調(diào)度[9], 而算力路由是實(shí)現(xiàn)端到端算力優(yōu)化調(diào)度的核心技術(shù)點(diǎn). 為了實(shí)現(xiàn)SGIN 網(wǎng)絡(luò)中傳輸和計算結(jié)合, 本文重點(diǎn)研究在SGIN 場景下的算力路由方法. 但是, 如何在SGIN 中通過建模和算法實(shí)現(xiàn)算力路由仍面臨諸多技術(shù)問題.

在早期階段, 研究人員將不同的任務(wù)表示為不同的有向無環(huán)圖, 為了優(yōu)化網(wǎng)絡(luò)業(yè)務(wù)的傳輸速率, 文獻(xiàn)[18-19]研究了映射到網(wǎng)絡(luò)拓?fù)渖系牟煌蝿?wù)DAG模型的最大傳輸速率, 但上述研究沒有考慮任務(wù)的計算. 為了共同優(yōu)化任務(wù)的計算和傳輸, 文獻(xiàn)[20]提出了一種業(yè)務(wù)圖邊緣和節(jié)點(diǎn)映射技術(shù), 該技術(shù)考慮了節(jié)點(diǎn)的計算能力約束, 但其不適用于復(fù)雜的任務(wù)DAG 模型. 針對這一問題, 文獻(xiàn)[21]制定了復(fù)雜DAG的映射優(yōu)化方案, 將任務(wù)DAG 的適用范圍擴(kuò)展到任何有向無環(huán)圖模型. 然而, 上述研究都是基于有中心管理節(jié)點(diǎn)的網(wǎng)絡(luò), 在沒有控制中心的情況下, 如何利用SGIN 中節(jié)點(diǎn)的計算能力在任務(wù)傳輸時處理任務(wù)仍是一個挑戰(zhàn).

2 系統(tǒng)模型

本節(jié)介紹了由衛(wèi)星站和地面節(jié)點(diǎn)組成的SGIN架構(gòu), 并詳細(xì)解釋了DCDR 的定義. 基于SGIN 架構(gòu),建立了衛(wèi)星節(jié)點(diǎn)與地面節(jié)點(diǎn)、星間鏈路和星地鏈路的運(yùn)動模型,并對采用時空擴(kuò)展圖模型進(jìn)行穩(wěn)態(tài)化處理.

2.1 SGIN 架構(gòu)

在對SGIN 進(jìn)行建模之前, 首先介紹SGIN 的架構(gòu). 如圖1 所示, 本文提出的SGIN 體系架構(gòu)包括中軌道（medium earth orbit, MEO）衛(wèi)星、低軌道（low earth orbit, LEO）衛(wèi)星和地面節(jié)點(diǎn). 其中, 采用帶服務(wù)器的MEO 和LEO 衛(wèi)星既作為算法執(zhí)行節(jié)點(diǎn), 協(xié)同制定DCDR 控制策略, 又作為主要計算和傳輸節(jié)點(diǎn), 根據(jù)任務(wù)映射策略參與任務(wù)計算；地面節(jié)點(diǎn)作為傳輸節(jié)點(diǎn)與衛(wèi)星節(jié)點(diǎn)共同為用戶提供傳輸功能.

圖1 SGIN 系統(tǒng)架構(gòu)示意圖Fig.1 Schematic diagram of SGIN system architecture

DCDR 的定義是SGIN 網(wǎng)絡(luò)中基于計算的路由,因此, 路徑的形成與用戶任務(wù)的特點(diǎn)密切相關(guān). 以圖1 為例, 如果訪問節(jié)點(diǎn)和目標(biāo)節(jié)點(diǎn)已知, 則分別計算子任務(wù)1 和子任務(wù)4. 將其他不同的子任務(wù)映射到傳輸路徑上的不同衛(wèi)星節(jié)點(diǎn), 從而實(shí)現(xiàn)任務(wù)邊傳輸邊計算. 此外, 應(yīng)該注意到不同的衛(wèi)星節(jié)點(diǎn)可以通過星間鏈路（inter-satellite links, ISLs）或星地鏈路聯(lián)接.例如, 計算任務(wù)1 和任務(wù)2 的衛(wèi)星是通過ISLs 連接的. 但是, 由于計算任務(wù)3 和任務(wù)4 的衛(wèi)星之間的連接較差, 因此, 需要同時考慮ISLs 和星地鏈路.

2.2 動態(tài)SGIN 模型

根據(jù)衛(wèi)星軌跡的可預(yù)測性, 衛(wèi)星在任意時間的位置都可以被預(yù)測. 同樣, 地面節(jié)點(diǎn)坐標(biāo)可以根據(jù)地球的半徑及自轉(zhuǎn)速度計算得到. 因此, 本文將根據(jù)衛(wèi)星和地面節(jié)點(diǎn)的相對位置, 對星間鏈路和星地鏈路進(jìn)行建模, 構(gòu)建動態(tài)SGIN 模型.

如圖2 所示, 以地心為原點(diǎn)建立三維坐標(biāo)系. 任何衛(wèi)星節(jié)點(diǎn)的坐標(biāo)都可以用開普勒六大參數(shù)來確定,其中,ai為半長軸,ei為偏心率,δi為傾角, Ωi為升交點(diǎn)赤經(jīng), ωi為近近地點(diǎn)幅角, fi（t）為真近地點(diǎn)角. 對于SGIN 中衛(wèi)星節(jié)點(diǎn)的位置都可以通過三維坐標(biāo)獲得, 其中, M 為衛(wèi)星個數(shù). 文獻(xiàn)[22]已經(jīng)對星間鏈路建模進(jìn)行了詳細(xì)的闡述, 不做過多介紹. 基于文獻(xiàn)[14]中的工作, 本文對星地鏈路建模進(jìn)行詳細(xì)的介紹.

圖2 地心坐標(biāo)圖Fig.2 Geocentric coordinate orientation

其中, Re是地球半徑；ωe是地球自轉(zhuǎn)角速度；分別可以通過經(jīng)度和緯度得知.

地面節(jié)點(diǎn)位于地球表面. 衛(wèi)星與地面節(jié)點(diǎn)之間的能見度取決于地面節(jié)點(diǎn)相對于衛(wèi)星的仰角. 對于地面節(jié)點(diǎn), 根據(jù)衛(wèi)星坐標(biāo)和地面節(jié)點(diǎn)坐標(biāo),可以計算得到其距離圖3 中δ3可以通過三角關(guān)系計算得到.

圖3 衛(wèi)星與地面節(jié)點(diǎn)之間的幾何關(guān)系Fig.3 The geometric relationships between satellite and ground station

假設(shè)地面節(jié)點(diǎn)和衛(wèi)星節(jié)點(diǎn)間的仰角為δ0, 則衛(wèi)星vi和地面節(jié)點(diǎn)gi是否連通取決于δ0. δ3為地面節(jié)點(diǎn)和衛(wèi)星節(jié)點(diǎn)之間的連線與衛(wèi)星節(jié)點(diǎn)和地心之間連線的夾角. δ4為地面節(jié)點(diǎn)和衛(wèi)星節(jié)點(diǎn)之間的連線與地面節(jié)點(diǎn)和地心之間連線的夾角.

如果δ4-90°<δ0, 則衛(wèi)星節(jié)點(diǎn)和地面節(jié)點(diǎn)間物理可視, 即需要滿足以下條件：

只有地面節(jié)點(diǎn)gi在衛(wèi)星節(jié)點(diǎn)vi的覆蓋范圍之內(nèi),才可建立通信鏈路, δ3應(yīng)滿足以下條件：

由于接收放大器可以恢復(fù)自由空間的傳播損耗,本節(jié)不再過多關(guān)注自由空間損耗[23], 主要關(guān)注了另外兩個衰減源：電離層閃爍和地面多徑衰落. 在傳輸過程中, 信號通過不同的路徑到達(dá)接收端. 接收信號是直視信號和通過建筑物、山脈、森林等其他信號的疊加. 為了同時分析電離層閃爍和多徑衰落的影響,本文采用經(jīng)典的雙射線傳播模型[15]. 反射系數(shù)Γ 由文獻(xiàn)[24]給出.

其中, ε0=8.854×10-12F/m, 并且σ 為多普勒頻移. 根據(jù)文獻(xiàn)[15]中σ=1, 兩條反射路徑的相位差為：

其中, pt是發(fā)射功率Gt和Gr分別是發(fā)射和接受天線增益. 然后, 根據(jù)香農(nóng)公式, 星間鏈路上下行鏈路容量可以表示為：

其中,

2.3 加權(quán)時空擴(kuò)展圖

由于SGIN 網(wǎng)絡(luò)具有高動態(tài)性, 因此, 很難直接在動態(tài)網(wǎng)絡(luò)中研究DCDR 控制策略. 為了解決SGIN拓?fù)漕l繁變化引起的路由不穩(wěn)定問題, 本文采用SGIN 時空擴(kuò)展圖（SGIN time-expanded graph, SGINTEG）方法對SGIN 的動態(tài)拓?fù)溥M(jìn)行穩(wěn)態(tài)化處理[25-27].

文獻(xiàn)[27]對衛(wèi)星網(wǎng)絡(luò)視同擴(kuò)散圖進(jìn)行了的建模,本節(jié)在文獻(xiàn)[27]的衛(wèi)星時空擴(kuò)展圖的基礎(chǔ)上考慮了星地鏈路, 構(gòu)建SGIN 時空擴(kuò)展圖模型.

2.3.1 時空鄰接矩陣

令時隙S 內(nèi)的網(wǎng)絡(luò)拓?fù)錇?1 鄰接矩陣LS, 則矩陣中元素可以表示為：

其中, C0和C1分別為星間鏈路和星地鏈路連通的容量門限的門限. 基于上述矩陣LS, 構(gòu)建了SGINTEG的01 鄰接矩陣.

其中, I 是一個（M+N）×（M+N）的單位矩陣, 代表了時隙間的虛擬鏈路. 0 是一個（M+N）×（M+N）的0 矩陣代表, 非相鄰的時隙沒有虛擬鏈路直連. Graph 左下角的單位矩陣表示經(jīng)過K 個時隙后, 網(wǎng)絡(luò)拓?fù)浠氐匠跏紶顟B(tài).

2.3.2 時延加權(quán)鄰接矩陣

最后, 加權(quán)SGINTEG 可以表示為：

3 改進(jìn)的定向擴(kuò)散算法

SGIN 除了具有高動態(tài)的特點(diǎn), 同時具有無中心的特點(diǎn). 定向擴(kuò)散算法作為一種分散式路由策略, 能夠很好地適應(yīng)大規(guī)模分散式網(wǎng)絡(luò)[28]. 然而, 傳統(tǒng)的定向擴(kuò)散算法是一種無中心路由算法, 無法實(shí)現(xiàn)計算的映射. 這里提出一種改進(jìn)的定向擴(kuò)散算法, 源節(jié)點(diǎn)根據(jù)目標(biāo)節(jié)點(diǎn)和不同的應(yīng)用需求定義不同的任務(wù)類型,通過向網(wǎng)絡(luò)廣播興趣消息來選擇計算節(jié)點(diǎn)和建立路由. 中間節(jié)點(diǎn)通過接受計算和轉(zhuǎn)發(fā), 形成從源節(jié)點(diǎn)到目的節(jié)點(diǎn)的梯度. 自動生成任務(wù)節(jié)點(diǎn)映射和從源節(jié)點(diǎn)到目標(biāo)節(jié)點(diǎn)的一條最優(yōu)路徑. 最后, 任務(wù)通過此路徑和SGIN 中的節(jié)點(diǎn)完成計算和傳輸.

3.1 興趣擴(kuò)散

其中, s 為信息傳播的跳數(shù), 通常s=1, 如果一跳之內(nèi)沒有合適的節(jié)點(diǎn)映射, 則s>1.

除目標(biāo)節(jié)點(diǎn)和源節(jié)點(diǎn)外, 其他子任務(wù)在傳輸時盡可能多地計算, 每映射一個子任務(wù), 從前一個子任務(wù)映射的鄰居節(jié)點(diǎn)中選擇下一個子任務(wù).

3.2 梯度建立

3.3 路徑選擇

在鄰居節(jié)點(diǎn)的梯度已知后, 父節(jié)點(diǎn)根據(jù)梯度從小到大進(jìn)行排序, 并根據(jù)這個順序設(shè)置優(yōu)先級, 梯度越小, 優(yōu)先級越高.

4 仿真分析

為驗證提出方案的有效性, 進(jìn)行了大量的實(shí)驗.通過分析不同DAG 下和不同任務(wù)終點(diǎn)情況下的DCDR 性能以及抗毀性, 根據(jù)仿真結(jié)果展示了不同DAG 的映射結(jié)果和不同任務(wù)量的映射結(jié)果, 衛(wèi)星鏈路參數(shù)根據(jù)文獻(xiàn)[32-33]設(shè)置.

基于星鏈星座選擇了20 顆衛(wèi)星和10 個地面節(jié)點(diǎn)構(gòu)建一個SGIN. 衛(wèi)星v1是源節(jié)點(diǎn), v8是目標(biāo)節(jié)點(diǎn).根據(jù)地面節(jié)點(diǎn)觀測更新時間, 每個時隙長度為60 s,第1 個時隙開始時間為上午8 點(diǎn), 衛(wèi)星軌道數(shù)據(jù)來自SpaceX 網(wǎng)站, 衛(wèi)星計算能力為5 MHz～10 MHz 均勻分布. 星鏈星座中所選衛(wèi)星編號、地面節(jié)點(diǎn)分別如表1、表2 所示.

表1 衛(wèi)星編號信息Table1 Number information of satellites

表2 地面節(jié)點(diǎn)名稱Table2 Names of ground stations

4.1 DCDR 的時延性能仿真

圖4 任務(wù)DAGsFig.4 DAGs of task

通過圖5 對DCDR 的性能進(jìn)行分析, 不同任務(wù)DAG 對任務(wù)傳輸和計算的時延有較大的影響. 首先,任務(wù)執(zhí)行的總時延不僅隨著任務(wù)量的增多也增多,也隨著任務(wù)的分支變多逐漸增加. 這是因為隨著分支變多, 而這些分支需要映射到一條路徑中, 增加了任務(wù)傳輸?shù)呢?fù)擔(dān). 在總的執(zhí)行時延中, 計算時延所占的比重很大, 并且隨著分支數(shù)目和任務(wù)量增加也增加. 因此, 在SGIN 場景中的DCDR 控制策略更加適合串行的任務(wù), 并且在執(zhí)行任務(wù)時, 計算時延在任務(wù)處理過程中起較為關(guān)鍵性的作用.

圖5 不同任務(wù)DAGs 對時延的影響Fig.5 Effects of different DAGs on latency

如圖6 所示, 對比了DCDR 與傳統(tǒng)云計算之間的差異. 傳統(tǒng)云計算需要接入衛(wèi)星將任務(wù)傳輸至云計算中心, 然后將計算結(jié)果返回給目的衛(wèi)星節(jié)點(diǎn). 在這里, 選擇了g6地面節(jié)點(diǎn)作為云計算節(jié)點(diǎn), 計算能力為10 MHz. 發(fā)現(xiàn)針對O1=1 I2=1, O1=2 I4=2, O1=3 I5=3 的任務(wù)而言, 云計算由于其較長的星間和星地傳輸路徑, 導(dǎo)致時延大于DCDR. 針對O1=4 I6=4, 隨著并行分支變多, 這些分支需要映射到一條路徑中, 增加了DCDR 中任務(wù)傳輸?shù)呢?fù)擔(dān), 導(dǎo)致DCDR 時延大于云計算. 因此, 針對并行分支較少的任務(wù)DAG 而言, DCDR 在降低任務(wù)總處理時延方面有較為明顯的優(yōu)勢. 但是隨著任務(wù)并行分支變多, DCDR 降低時延的效果一般.

圖6 DCDR 與云計算的時延對比圖Fig.6 Latency comparison diagram of DCDR and cloud computing

4.2 DCDR 的冗余抗毀性能仿真

為了測試DCDR 的冗余抗毀性, 同時考慮了衛(wèi)星和地面節(jié)點(diǎn)的意外損壞. 假定衛(wèi)星和地面節(jié)點(diǎn)損壞的個數(shù)服從均勻分布, 即damage_num～U（[1, 10]）.每次算法運(yùn)行的過程中隨機(jī)毀壞1～10 個節(jié)點(diǎn), 并且針對不同的損壞個數(shù)分別測試100 次實(shí)驗, 計算其任務(wù)處理失敗的概率. 如圖7 所示, 以O(shè)1=1 I2=1 為例, DCDR 的失敗概率明顯低于采用固定傳輸路徑的方法. 無中心分散式的DCDR 方法能夠在選擇路徑的過程中動態(tài)規(guī)避毀壞的節(jié)點(diǎn), 從正常工作的節(jié)點(diǎn)中重新規(guī)劃下一跳的路徑并映射計算, 從而達(dá)到有效提高DCDR 的抗毀性.

圖7 DCDR 抗毀性分析Fig.7 Invulnerability analysis of DCDR

4.3 DCDR 映射結(jié)果展示

圖8 給出兩個不同的任務(wù)DAG 的映射結(jié)果和同一個DAG 不同任務(wù)量的映射結(jié)果. 通過圖8（a）和圖8（b）對比, 發(fā)現(xiàn)不同的DAG 會有不同的映射結(jié)果,這表示所提出的DCDR 方法可以適應(yīng)不同任務(wù)DAG 模型得到不同的映射結(jié)果. 其次, 對比圖8（a）和圖8（c）, 發(fā)現(xiàn)對于同一個任務(wù)DAG 當(dāng)任務(wù)的計算和傳輸時延超過的一個時隙的長度時, 會出現(xiàn)通過虛擬鏈路跨時隙的情況, 達(dá)到適應(yīng)網(wǎng)絡(luò)動態(tài)變化的效果.

圖8 不同任務(wù)DAG 相同任務(wù)量以及不同任務(wù)量相同DAG映射結(jié)果Fig.8 The mapping results of different DAGs with same size of task and different size of task with same DAG

5 結(jié)論

針對無中心、分布式、高動態(tài)的天地一體化網(wǎng)絡(luò)中大規(guī)模端到端傳輸問題, 本文提出一種考慮計算映射與動態(tài)分布的DCDR 范式. 通過采用時空擴(kuò)展圖模型對動態(tài)網(wǎng)絡(luò)進(jìn)行了穩(wěn)態(tài)化處理, 基于穩(wěn)態(tài)化SGIN 設(shè)計改進(jìn)的定向擴(kuò)散算法實(shí)現(xiàn)最優(yōu)DCDR控制策略制定. 仿真結(jié)果表明, DCDR 控制策略能夠靈活高效地實(shí)現(xiàn)不同種類的任務(wù)的計算和傳輸, 適應(yīng)SGIN 的動態(tài)變化及時調(diào)整傳輸路徑, 并具有較好的冗余抗毀性. 下一步將考慮面向高中低軌道衛(wèi)星、計算資源受限下的路由控制策略研究, 進(jìn)一步優(yōu)化模型及冗余抗毀性能, 以提高時延性能和路由效率.研究成果將為面向各類軍事應(yīng)用的天地一體化網(wǎng)絡(luò)的高效聯(lián)接和魯棒傳輸, 提供理論方法和技術(shù)支撐.