空間信息網絡時變圖建模方法*

楊惠婷，劉偉

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

0 引言

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

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

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

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

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

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

1 空間信息網絡的特性

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

圖1 空間信息網絡示意圖

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

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

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

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

圖2 空間信息網絡拓撲變化示意圖

2 快照序列圖

快照序列圖主要通過一系列的離散時間上的快照來刻畫時變網絡拓撲的動態演進過程[33]，其中每個快照刻畫了特定時間段內保持不變的網絡拓撲，如圖3所示，其為圖2所對應的快照序列圖。在圖3中，藍色有向線表示的是通信鏈路，其刻畫了當前時隙中衛星之間或者衛星與地面站之間的通信機會，而通信鏈路上的數值表示的是該鏈路的通信容量，即在當前時間間隔內該鏈路能夠傳輸的最大數據量。此外，快照序列圖只可以表征時變網絡中的通信資源。快照序列圖的優缺點如下：

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

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

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

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

3 時間擴展圖

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

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

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

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

4 存儲時間聚合圖

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

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

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

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

5 多功能時間擴展圖

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

圖6 功能節點虛擬分解示意圖

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

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

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

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

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

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

6 結束語

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