楊惠婷，劉偉

（西安電子科技大學(xué)，陜西 西安 710000）

0 引言

未來6G網(wǎng)絡(luò)的關(guān)鍵特征和期望之一是提供全球無縫覆蓋，實(shí)現(xiàn)從萬物互聯(lián)到萬物智聯(lián)的躍遷[1-5]。在實(shí)現(xiàn)這愿景的過程中，星地融合網(wǎng)絡(luò)成為了推動力量之一，其在6G中擔(dān)任尤為重要的角色[4,6-7]。星地融合網(wǎng)絡(luò)主要由地面移動通信網(wǎng)絡(luò)和空間信息網(wǎng)絡(luò)等共同組成[4,7-8]。星地融合網(wǎng)絡(luò)實(shí)現(xiàn)全球無縫覆蓋，在6G的許多應(yīng)用領(lǐng)域提供了有力支撐，例如智慧城市、遠(yuǎn)洋航行、偏遠(yuǎn)地區(qū)監(jiān)測等[9-12]。特別地，在沒有基站覆蓋的偏遠(yuǎn)地區(qū)，例如沙漠、無人區(qū)、海洋和山區(qū)等，以及基站被摧毀的重災(zāi)地區(qū)，例如地震、山洪等[5,10,13]。

空間信息網(wǎng)絡(luò)是星地融合網(wǎng)絡(luò)中一個重要組成部分[4,14]，其由同步軌道（GEO,Geostationary Earth Orbit）衛(wèi)星、中軌道（MEO,Middle Earth Orbit）衛(wèi)星、低軌道（LEO,Low Earth Orbit）衛(wèi)星和地面站等組成的多層次網(wǎng)絡(luò)[13,15-16]。星地融合網(wǎng)絡(luò)通過空間信息網(wǎng)絡(luò)可以實(shí)現(xiàn)全球無縫覆蓋，并且可以支持靈活、無處不在的網(wǎng)絡(luò)接入[16-17]。此外，星地融合網(wǎng)絡(luò)中的空間信息網(wǎng)絡(luò)具有高可靠性、大容量、遠(yuǎn)距離傳輸和不受地理環(huán)境限制等顯著優(yōu)點(diǎn)[15,17]。

對空間信息網(wǎng)絡(luò)進(jìn)行合適的建模是網(wǎng)絡(luò)規(guī)劃、資源管理和性能分析等空間信息網(wǎng)絡(luò)研究的基礎(chǔ)[18-21]。通過空間信息網(wǎng)絡(luò)的建模，可以更深入理解網(wǎng)絡(luò)結(jié)構(gòu)和性能，可以有助于提高資源利用率、提升網(wǎng)絡(luò)性能、保障網(wǎng)絡(luò)的魯棒性和不同任務(wù)的服務(wù)質(zhì)量需求（QoS,Quality of Service）[19-23]。因此，空間信息網(wǎng)絡(luò)的建模得到廣泛研究[19-27]。然而，與傳統(tǒng)地面網(wǎng)絡(luò)相比，空間信息網(wǎng)絡(luò)的衛(wèi)星分布較為稀疏，并且衛(wèi)星沿著固定軌道高速移動，使得衛(wèi)星之間的通信鏈路間歇性連通，導(dǎo)致空間信息網(wǎng)絡(luò)拓?fù)潆S時間動態(tài)變化且可預(yù)測[19-23]。

圖模型是一種重要的網(wǎng)絡(luò)建模與分析的理論工具，已經(jīng)被廣泛應(yīng)用于表征各種網(wǎng)絡(luò)[22,28]。傳統(tǒng)的地面網(wǎng)絡(luò)通常采用靜態(tài)圖模型來刻畫其網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)[29]。然而，傳統(tǒng)的靜態(tài)圖模型無法刻畫空間信息網(wǎng)絡(luò)拓?fù)鋭討B(tài)變化。因此，采用時變圖模型來表征時變的空間信息網(wǎng)絡(luò)成為了一個研究熱點(diǎn)[21-25,27,30-32]。

目前，表征時變的空間信息網(wǎng)絡(luò)的時變圖主要包括:快照序列圖[33]、時間擴(kuò)展圖[29]、存儲時間聚合[18]和多功能時間擴(kuò)展圖[19]。文獻(xiàn)[30]采用了快照序列圖表征空間信息網(wǎng)絡(luò)的動態(tài)演進(jìn)過程，其聯(lián)合表征了衛(wèi)星的通信資源和計(jì)算資源，并基于快照序列圖提出了一種滿足端到端（E2E,End-to-End）時延需求的條件下使得網(wǎng)絡(luò)收益最大化的路由策略。文獻(xiàn)[27,31-32]采用了時間擴(kuò)展圖刻畫空間信息網(wǎng)絡(luò)拓?fù)涞膭討B(tài)變化。其中，文獻(xiàn)[27]和文獻(xiàn)[31]采用時間擴(kuò)展圖聯(lián)合表征了空間信息網(wǎng)絡(luò)的通信資源和存儲資源，并基于時間擴(kuò)展圖，文獻(xiàn)[27]提出了一種滿足E2E時延需求條件下完成任務(wù)優(yōu)先級總和最大化的路由策略，文獻(xiàn)[31]提出了一種在收發(fā)信機(jī)受限的條件下網(wǎng)絡(luò)流最大化的路由策略；文獻(xiàn)[32]采用時間擴(kuò)展圖聯(lián)合表征了軟件定義空間信息網(wǎng)絡(luò)的通信、存儲和計(jì)算資源，并基于時間擴(kuò)展圖提出了一種通信資源消耗最小化的路由策略。文獻(xiàn)[18]提出了采用存儲時間聚合圖來表征時變的空間信息網(wǎng)絡(luò)，并基于存儲時間聚合圖提出一種在滿足E2E時延條件下網(wǎng)絡(luò)流最大化的路由策略。文獻(xiàn)[23-24]采用多功能時間擴(kuò)展圖來聯(lián)合表征時變的軟件定義空間信息網(wǎng)絡(luò)的通信、存儲和計(jì)算資源，其中，文獻(xiàn)[23]基于多功能時間擴(kuò)展圖提出了一種在保障E2E時延需求條件下完成任務(wù)總數(shù)最大化的網(wǎng)絡(luò)切片路由策略；文獻(xiàn)[24]基于多功能時間擴(kuò)展圖研究了網(wǎng)絡(luò)性能和網(wǎng)絡(luò)協(xié)同開銷之間的折中問題。

采用一個合適的時變圖模型對于空間信息網(wǎng)絡(luò)性能分析至關(guān)重要。因此，在后面章節(jié)中首先介紹了空間信息網(wǎng)絡(luò)的特性，然后詳細(xì)介紹了多種空間信息網(wǎng)絡(luò)時變圖模型建模方法，包括快照序列圖、時間擴(kuò)展圖、存儲時間聚合圖和多功能時間擴(kuò)展圖，并且分析了它們的特征和優(yōu)缺點(diǎn)。

1 空間信息網(wǎng)絡(luò)的特性

空間信息網(wǎng)絡(luò)是一個由同步軌道衛(wèi)星、中軌道衛(wèi)星、低軌道衛(wèi)星和地面站等組成的多層立體的異構(gòu)網(wǎng)絡(luò)，如圖1所示。與傳統(tǒng)地面網(wǎng)絡(luò)相比，空間信息網(wǎng)絡(luò)具有如下特點(diǎn)：

圖1 空間信息網(wǎng)絡(luò)示意圖

（1）網(wǎng)絡(luò)拓?fù)鋾r變性[22-23,27,31-32]：由于空間信息網(wǎng)絡(luò)的衛(wèi)星節(jié)點(diǎn)分布較為稀疏，并且衛(wèi)星沿著固定軌道高速移動，使得衛(wèi)星之間的通信鏈路間歇性連通，導(dǎo)致空間信息網(wǎng)絡(luò)拓?fù)潆S時間發(fā)生動態(tài)變化[22-23,27,31-32]。因此，在空間信息網(wǎng)絡(luò)中，很難保障節(jié)點(diǎn)之間實(shí)時存在端到端的傳輸路徑，使得節(jié)點(diǎn)通常需要將接收的數(shù)據(jù)進(jìn)行存儲-攜帶-轉(zhuǎn)發(fā)的方式傳輸給下一個節(jié)點(diǎn)[22,34-35]。

（2）網(wǎng)絡(luò)拓?fù)淇深A(yù)測性[22-23,27]：由于衛(wèi)星是在固定的軌道上移動，并且衛(wèi)星的通信覆蓋范圍是可被精準(zhǔn)計(jì)算，因此，空間信息網(wǎng)絡(luò)拓?fù)鋭討B(tài)變化是可預(yù)測的。

（3）網(wǎng)絡(luò)資源動態(tài)、受限性[13,36]：由于衛(wèi)星的尺寸、制造和發(fā)射成本、平臺重量等限制導(dǎo)致衛(wèi)星所攜帶的載荷數(shù)量和大小是十分有限的，其中載荷包括了收發(fā)信機(jī)、存儲器、處理器等[13]。因此，空間信息網(wǎng)絡(luò)的通信、計(jì)算和存儲等資源是稀缺的[13,36]。此外，由于衛(wèi)星在軌道上周期性高速運(yùn)動，并且衛(wèi)星之間的通信鏈路是斷續(xù)聯(lián)通的，導(dǎo)致空間信息網(wǎng)絡(luò)的通信資源的可用性是周期性動態(tài)變化的[35]。

后面的章節(jié)將討論空間信息網(wǎng)絡(luò)時變圖模型的建模方法，考慮一個示例空間信息網(wǎng)絡(luò)，由4顆衛(wèi)星組成，分別為v1,v2,v3和v4，如圖2所示。在時隙[t0,t1)和時隙[t1,t2)中，衛(wèi)星v1和衛(wèi)星v2是聯(lián)通的，但由于衛(wèi)星的移動性，導(dǎo)致在時隙[t2,t3)中衛(wèi)星v1和衛(wèi)星v2通信中斷。因此，空間信息網(wǎng)絡(luò)的拓?fù)涫莿討B(tài)變化且可預(yù)測的。目前，表征時變的空間信息網(wǎng)絡(luò)的時變圖主要包括：快照序列圖、時間擴(kuò)展圖、存儲時間聚合圖和多功能時間擴(kuò)展圖，將在下面章節(jié)中逐一介紹。

圖2 空間信息網(wǎng)絡(luò)拓?fù)渥兓疽鈭D

2 快照序列圖

快照序列圖主要通過一系列的離散時間上的快照來刻畫時變網(wǎng)絡(luò)拓?fù)涞膭討B(tài)演進(jìn)過程[33]，其中每個快照刻畫了特定時間段內(nèi)保持不變的網(wǎng)絡(luò)拓?fù)?，如圖3所示，其為圖2所對應(yīng)的快照序列圖。在圖3中，藍(lán)色有向線表示的是通信鏈路，其刻畫了當(dāng)前時隙中衛(wèi)星之間或者衛(wèi)星與地面站之間的通信機(jī)會，而通信鏈路上的數(shù)值表示的是該鏈路的通信容量，即在當(dāng)前時間間隔內(nèi)該鏈路能夠傳輸?shù)淖畲髷?shù)據(jù)量。此外，快照序列圖只可以表征時變網(wǎng)絡(luò)中的通信資源?？煺招蛄袌D的優(yōu)缺點(diǎn)如下：

圖3 具有三個時隙的快照序列圖的示意圖

（1）優(yōu)點(diǎn)：由于快照序列圖中的每個快照都可以視為一個靜態(tài)圖，因此，基于靜態(tài)圖設(shè)計(jì)的路由算法都適用于快照序列圖中的每個快照，例如，可以通過Ford-Fulkerson、Edmonds-Karp等網(wǎng)絡(luò)最大流算法在每個快照內(nèi)求解端到端最大流[29,37]；還可以通過Dijkstra等最短路徑算法在每個快照內(nèi)求解端到端的最短路由[37]。此外，針對靜態(tài)圖設(shè)計(jì)的軟件定義網(wǎng)絡(luò)具有服務(wù)功能鏈約束（即從源節(jié)點(diǎn)到目的節(jié)點(diǎn)的任務(wù)流必須按照特定順序依次接收服務(wù)功能）的路由算法同樣適用于快照序列圖中的每個快照[38-40]。

（2）缺點(diǎn)：由于在空間信息網(wǎng)絡(luò)中節(jié)點(diǎn)稀疏且間歇性聯(lián)通，使得在某些快照內(nèi)節(jié)點(diǎn)間可能不存在端到端的傳輸路徑，導(dǎo)致大量數(shù)據(jù)通常需要依靠存儲-攜帶-轉(zhuǎn)發(fā)的形式到達(dá)目的節(jié)點(diǎn)。但是，快照序列圖只刻畫每個快照內(nèi)的網(wǎng)絡(luò)拓?fù)渥兓?，而忽略了各個快照之間的聯(lián)系，即快照序列圖只表征了時變網(wǎng)絡(luò)的通信資源，忽略了存儲和計(jì)算等其他資源。因此，基于快照序列圖設(shè)計(jì)的路由策略網(wǎng)絡(luò)性能差，資源利用率低[19,21-22]。

以圖3為例來介紹快照序列圖的網(wǎng)絡(luò)性能，假設(shè)v1和v4分別為源節(jié)點(diǎn)和目的節(jié)點(diǎn)，從圖3可以看出該快照序列圖中的三個快照均不存在從v1到v4的傳輸路徑，在時隙τ1內(nèi)v1分別與v2和v3存在傳輸路徑，而在時隙τ3內(nèi)v2和v3均與v4存在傳輸路徑，但是由于快照序列圖沒有考慮各個快照聯(lián)系，導(dǎo)致v1無法給v4傳輸數(shù)據(jù)，即該網(wǎng)絡(luò)最大流為0。因此，雖然快照序列圖可以表征時變網(wǎng)絡(luò)的動態(tài)演進(jìn)過程，但是，快照序列圖忽略了存儲資源，造成資源利用低、網(wǎng)絡(luò)性能差。

3 時間擴(kuò)展圖

時間擴(kuò)展圖是在快照序列圖的基礎(chǔ)上引入了存儲鏈路，使得可以將離散時間上的快照連接起來，如圖4所示，其為圖2所對應(yīng)的時間擴(kuò)展圖[29]。時間擴(kuò)展圖中每一層的節(jié)點(diǎn)對應(yīng)相應(yīng)時隙的網(wǎng)絡(luò)節(jié)點(diǎn)的副本。時間擴(kuò)展圖中的鏈路可以分為兩種類型，分別為通信鏈路和存儲鏈路，如圖4所示，藍(lán)色有向線表示的是通信鏈路，而紅色有向虛線表示的是存儲鏈路，其中存儲鏈路刻畫了其對應(yīng)的節(jié)點(diǎn)存儲攜帶數(shù)據(jù)的能力。在圖4中，存儲鏈路上的數(shù)值表示的是該存儲鏈路的存儲容量，即其對應(yīng)的節(jié)點(diǎn)能夠存儲攜帶的最大數(shù)據(jù)量。因此，在時間擴(kuò)展圖中，通信鏈路和存儲鏈路分別表征了時變網(wǎng)絡(luò)中的通信資源和存儲資源。此外，時間擴(kuò)展圖的優(yōu)缺點(diǎn)如下：

圖4 具有三個時隙的時間擴(kuò)展圖的示意圖

（1）優(yōu)點(diǎn)：時間擴(kuò)展圖通過引入存儲鏈路將各個快照聯(lián)系起來，從而能夠聯(lián)合表征時變網(wǎng)絡(luò)的通信資源和存儲資源，可以有效提高資源利用率和網(wǎng)絡(luò)性能[21,27]。具體而言，在一個時隙內(nèi)如果一個節(jié)點(diǎn)接收的數(shù)據(jù)量大于其可發(fā)送的數(shù)據(jù)量，則其將發(fā)送完后剩余的數(shù)據(jù)量存儲攜帶等待下一次傳輸機(jī)會再進(jìn)行傳輸，從而可以充分利用網(wǎng)絡(luò)資源并有效提高網(wǎng)絡(luò)性能[21-22]。此外，時間擴(kuò)展圖通過引入存儲鏈路，實(shí)現(xiàn)時變網(wǎng)絡(luò)的靜態(tài)化表征，因此，針對靜態(tài)網(wǎng)絡(luò)設(shè)計(jì)的大部分路由算法均可以直接適用于時間擴(kuò)展圖，例如Dijkstra最短路徑算法、Ford-Fulkerson、Edmonds-Karp等最大流算法。

（2）缺點(diǎn)：時間擴(kuò)展圖只能聯(lián)合表征通信資源、存儲資源和節(jié)點(diǎn)只有單一的計(jì)算功能的計(jì)算資源，其無法刻畫節(jié)點(diǎn)具有多個的計(jì)算功能的計(jì)算資源[19]。軟件定義空間信息網(wǎng)絡(luò)可以打通異構(gòu)網(wǎng)絡(luò)資源壁壘，實(shí)現(xiàn)網(wǎng)絡(luò)的多維資源融合共享，從而提高資源利用率和保障不同QoS需求[17,21,23]。因此，軟件定義空間信息網(wǎng)絡(luò)在未來扮演非常重要的角色[21,23,32]。但是，在軟件定義空間信息網(wǎng)絡(luò)中，節(jié)點(diǎn)可以被部署多個不同的虛擬網(wǎng)絡(luò)功能，并且任務(wù)流在節(jié)點(diǎn)上接收虛擬網(wǎng)絡(luò)功能將消耗該節(jié)點(diǎn)的計(jì)算資源。然而，時間擴(kuò)展圖無法表征節(jié)點(diǎn)具有多個計(jì)算功能的計(jì)算資源，因此，時間擴(kuò)展圖無法表征軟件定義空間信息網(wǎng)絡(luò)任務(wù)流同時接收多個虛擬網(wǎng)絡(luò)功能的場景[19,23-24]。此外，當(dāng)時間規(guī)劃周期和網(wǎng)絡(luò)規(guī)模越大，時間擴(kuò)展圖的節(jié)點(diǎn)副本數(shù)量越龐大，使得所涉及的變量數(shù)劇增，導(dǎo)致求解優(yōu)化問題的時間復(fù)雜度極高[21-22,27]。

4 存儲時間聚合圖

存儲時間聚合圖是將時間擴(kuò)展圖進(jìn)行聚合表征，即將各個快照內(nèi)的鏈路通信容量表示為鏈路容量序列，將節(jié)點(diǎn)在各個快照之間存儲的數(shù)據(jù)量表示為存儲轉(zhuǎn)移序列，如圖5所示，其為圖4所對應(yīng)的存儲時間聚合圖[18]。為了便于理解存儲時間聚合圖，以圖5為例，從節(jié)點(diǎn)v1到節(jié)點(diǎn)v2的通信鏈路所對應(yīng)的鏈路容量序列為(20,10,0)，其表示的是從節(jié)點(diǎn)v1到節(jié)點(diǎn)v2的通信鏈路在第一個快照和第二個快照內(nèi)的通信容量分別為20和10，而在第三個快照內(nèi)的通信容量為0，即在第三個快照內(nèi)節(jié)點(diǎn)v1和節(jié)點(diǎn)v2不存在通信鏈路；節(jié)點(diǎn)v1所對應(yīng)的存儲容量為50，其表示的是節(jié)點(diǎn)v1在各個快照之間能夠存儲的最大數(shù)據(jù)量為50；節(jié)點(diǎn)v1所對應(yīng)的存儲轉(zhuǎn)移序列為[0,0]，其表示的是節(jié)點(diǎn)v1從第一個快照到第二個快照之間，以及從第二個快照到第三個快照之間均未存儲任何數(shù)據(jù)。因此，存儲時間聚合圖可以聯(lián)合表征時變網(wǎng)絡(luò)的通信資源和存儲資源。此外，存儲時間聚合圖的優(yōu)缺點(diǎn)如下：

圖5 具有三個時隙的存儲時間聚合圖的示意圖

（1）優(yōu)點(diǎn)：存儲時間聚合圖將各個快照進(jìn)行聚合表征，精簡了圖模型，從而降低了圖模型的空間復(fù)雜度[18]。

（2）缺點(diǎn)：存儲時間聚合圖只能聯(lián)合表征通信資源和存儲資源，而無法表征計(jì)算資源。然而，在空間信息網(wǎng)絡(luò)中大部分任務(wù)通常需要通信、存儲和計(jì)算等多維資源相互協(xié)作。此外，針對靜態(tài)圖設(shè)計(jì)的路由算法無法直接適用于存儲時間聚合圖[18]，例如Dijkstra最短路徑算法、Ford-Fulkerson、Edmonds-Karp等最大流算法。

5 多功能時間擴(kuò)展圖

多功能時間擴(kuò)展圖是在時間擴(kuò)展圖的基礎(chǔ)上，將每個具有多個計(jì)算功能的節(jié)點(diǎn)進(jìn)行虛擬分解為：一個虛擬子節(jié)點(diǎn)、多個虛擬功能節(jié)點(diǎn)和虛擬傳輸鏈路，如圖6所示，其中虛擬子節(jié)點(diǎn)不提供任何計(jì)算功能，只起到中繼作用；而每個虛擬功能節(jié)點(diǎn)只可以為任務(wù)流提供一種計(jì)算功能。以圖2為例，假設(shè)v1和v4不提供任何計(jì)算功能，而v2和v3均可以提供兩種不同的計(jì)算功能，因此，可以將v2和v3均虛擬分解為一個虛擬子節(jié)點(diǎn)和兩個虛擬功能節(jié)點(diǎn)，而v1和v4保持不變，無需進(jìn)行虛擬分解，從而可以獲得如圖7所示的多功能時間擴(kuò)展圖。

圖6 功能節(jié)點(diǎn)虛擬分解示意圖

多功能時間擴(kuò)展圖中的節(jié)點(diǎn)可以分為三種類型：非功能節(jié)點(diǎn)、虛擬子節(jié)點(diǎn)和虛擬功能節(jié)點(diǎn)，其中非功能節(jié)點(diǎn)表示的是不具有計(jì)算功能的節(jié)點(diǎn)，其可以提供通信資源和存儲資源，如圖7綠色圓圈所示；虛擬子節(jié)點(diǎn)可以提供通信資源和存儲資源，但不提供任何計(jì)算資源，如圖7藍(lán)色圓圈所示；而虛擬功能節(jié)點(diǎn)只可以提供一種計(jì)算功能，如圖7橙色方形所示。多功能時間擴(kuò)展圖中的鏈路可以分為三種類型：通信鏈路、存儲鏈路和虛擬傳輸鏈路，其中，虛擬傳輸鏈路是將虛擬子節(jié)點(diǎn)和虛擬功能節(jié)點(diǎn)連接起來的鏈路，如圖7綠色有向點(diǎn)虛線所示。此外，多功能時間擴(kuò)展圖的優(yōu)缺點(diǎn)如下：

（1）優(yōu)點(diǎn)：多功能時間擴(kuò)展圖可以聯(lián)合表征時變網(wǎng)絡(luò)中的通信、存儲和計(jì)算資源。此外，多功能時間擴(kuò)展圖能夠表征節(jié)點(diǎn)具有多個計(jì)算功能的計(jì)算資源，因此，多功能時間擴(kuò)展圖可以適用于刻畫軟件定義空間信息網(wǎng)絡(luò)任務(wù)流同時接受多個計(jì)算功能的場景[19,23-24]。

（2）缺點(diǎn)：當(dāng)網(wǎng)絡(luò)規(guī)模和時間規(guī)劃周期越大，多功能時間擴(kuò)展圖中的節(jié)點(diǎn)數(shù)量越龐大，則所涉及的變量數(shù)劇增，導(dǎo)致求解優(yōu)化問題的時間復(fù)雜度極高[23-24]。此外，針對靜態(tài)圖設(shè)計(jì)的路由算法同樣不適用于多功能時間擴(kuò)展圖[23-24]。

表1給出了各時變圖模型特征對比情況。不同的時變圖模型的特征不同，有各自的優(yōu)點(diǎn)和缺點(diǎn)。時間擴(kuò)展圖和多功能時間擴(kuò)展圖都可以表征時變的空間信網(wǎng)絡(luò)的通信、存儲和計(jì)算資源，但是應(yīng)用場景不同，選擇的圖模型也有所不同。具體而言，如果所考慮的空間信息網(wǎng)絡(luò)場景，節(jié)點(diǎn)不需要提供多個計(jì)算功能，則采用時間擴(kuò)展圖表征時變的空間信息網(wǎng)絡(luò)更加合適[20-21,25]。因?yàn)?，與多功能時間擴(kuò)展圖相比，時間擴(kuò)展圖所涉及的變量數(shù)量相對較小，使得求解優(yōu)化問題的時間復(fù)雜度相對降低。然而，如果所考慮的是軟件定義空間信息網(wǎng)絡(luò)場景，并且節(jié)點(diǎn)需要提供多個計(jì)算功能，則采用多功能時間擴(kuò)展圖表征時變的軟件定義空間信息網(wǎng)絡(luò)更加合適[19,23]。因?yàn)?，時間擴(kuò)展圖無法刻畫任務(wù)流在同一個節(jié)點(diǎn)上接受多個計(jì)算功能，而多功能時間擴(kuò)展圖能夠表征節(jié)點(diǎn)具有多個計(jì)算功能的計(jì)算資源，并且能夠刻畫任務(wù)流在同一個節(jié)點(diǎn)接受多個計(jì)算功能的流守恒轉(zhuǎn)化關(guān)系。因此，需要根據(jù)場景選擇合適的時變圖模型。

表1 各類時變圖模型的特點(diǎn)

此外，雖然現(xiàn)有的時變圖模型，例如時間擴(kuò)展圖和多功能時間擴(kuò)展圖，可以聯(lián)合表征時變的空間信息網(wǎng)絡(luò)的通信、存儲和計(jì)算資源，但是還是存在一些不足。其中，最主要的問題在于時間擴(kuò)展圖和多功能時間擴(kuò)展圖在網(wǎng)絡(luò)規(guī)模和時間規(guī)劃周期很大時，其節(jié)點(diǎn)數(shù)量非常龐大，導(dǎo)致求解問題的時間復(fù)雜度極高。因此，在基于時變圖模型的研究中，如何設(shè)計(jì)低復(fù)雜度算法求解問題，仍是亟待解決的問題。

6 結(jié)束語

空間信息網(wǎng)絡(luò)是6G星地融合網(wǎng)絡(luò)的一個重要組成部分，是各個國家的重要信息網(wǎng)絡(luò)基礎(chǔ)設(shè)施?？臻g信息網(wǎng)絡(luò)具有全球無縫覆蓋、遠(yuǎn)距離傳輸和不受地理環(huán)境限制等顯著優(yōu)點(diǎn)，在未來6G網(wǎng)絡(luò)中擔(dān)任非常重要的角色。但是，由于空間信息網(wǎng)絡(luò)的衛(wèi)星節(jié)點(diǎn)分布較為稀疏，并且衛(wèi)星之間的通信鏈路間歇性連通，導(dǎo)致空間信息網(wǎng)絡(luò)拓?fù)潆S時間動態(tài)變化。為了精準(zhǔn)表征時變的空間信息網(wǎng)絡(luò)拓?fù)渥兓投嗑S資源的時變性，可以采用時變圖模型。目前表征時變的空間信息網(wǎng)絡(luò)的時變圖主要包括：快照序列圖、時間擴(kuò)展圖、存儲時間聚合圖和多功能時間擴(kuò)展圖。不同的時變圖模型的特征不同，有各自的優(yōu)點(diǎn)和缺點(diǎn)。因此，需要根據(jù)應(yīng)用場景選擇合適的時變圖模型。