空間信息網(wǎng)絡時變圖建模方法*

楊惠婷，劉偉

（西安電子科技大學，陜西 西安 710000）

0 引言

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

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

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

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

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

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

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

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

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

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

（2）網(wǎng)絡拓撲可預測性[22-23,27]：由于衛(wèi)星是在固定的軌道上移動，并且衛(wèi)星的通信覆蓋范圍是可被精準計算，因此，空間信息網(wǎng)絡拓撲動態(tài)變化是可預測的。

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

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

圖2 空間信息網(wǎng)絡拓撲變化示意圖

2 快照序列圖

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

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

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

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

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

3 時間擴展圖

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

圖4 具有三個時隙的時間擴展圖的示意圖

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

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

4 存儲時間聚合圖

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

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

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

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

5 多功能時間擴展圖

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

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

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

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

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

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

表1 各類時變圖模型的特點

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

6 結束語

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