基于網絡編碼的衛星網絡容量提升方法*

王瑞松，鐘志聰，劉功亮，馬若飛

（哈爾濱工業大學，山東 威海 264209）

0 引言

空間動態網絡[1-3]是伴隨著人們日益增長的服務需求而不斷發展的，網絡用戶數量的增長、節點類型的多樣化、數據傳輸的高質量要求以及網絡資源的受限等一系列的特點使得空間動態網絡在網絡擴展、資源共享、一體化組網和網絡傳輸能力等方面面臨著更大的挑戰。因此，在不增加衛星網絡節點數量、頻帶、存儲、功率等資源的情況下，探索有效提升網絡傳輸容量和服務質量的網絡傳輸方法是目前國內外在衛星領域研究的熱點問題，也是空間動態網絡發展的關鍵。

在衛星通信系統中也有一些關于網絡容量方面的研究，文獻[4]針對多波束衛星-地面通信系統提出了一種自適應功率控制方法，通過優化傳輸功率來降低系統間的干擾，可以增加系統總容量。文獻[5]根據負載集中地區的位置，結合衛星的發射功率和衛星點波束的峰值增益來進行功率資源的分配，在發射功率和波束方向性之間進行權衡，與傳統的分配方法相比可以容納更多的流量。文獻[6]在多波束衛星通信系統中針對傳統的迭代注水算法存在的運算量和復雜性高的問題，提出了一種低復雜度的改進功率分配算法，可以減少計算的開銷并保證網絡容量的最大化。文獻[7]研究了利用智能網關分集設置在多波束高通量衛星系統中實現最佳容量分配的方法。上述研究雖然在資源分配和容量優化方面進行了深入研究，提供了一些相應的解決方案，但是這些研究都集中在多波束衛星對地通信的場景，且這些場景中的衛星數量比較少，沒有考慮在衛星網絡中進行星間通信的情況，這也是目前研究中的特點，大多數研究都主要針對星地通信而缺少對星間通信方面的研究。文獻[8]雖然建立了具有星間鏈路的星間通信模型，研究了衛星功率和帶寬聯合分配的優化算法，提高了衛星的資源利用率和系統容量，但是沒有考慮衛星網絡的動態特性，結構比較簡單，缺乏具體的空間動態網絡分析模型。

網絡編碼是一種有效地提升網絡容量的工具，自提出以來，學者們對網絡編碼理論的研究和完善從未間斷，取得了許多重要的研究成果。Katti等人在文獻[9]中提出一種完全機會編碼方案（COPE,Completely Opportunity Encoding），對網絡編碼的基礎理論研究提供了重要參考。受到COPE的啟發，研究者們相繼提出了一些通過將路由與流間網絡編碼相結合來提升網絡容量的方法[10-13]。但是這些流間網絡編碼的方法中網絡流通常是通過最短路徑進行傳輸，節點只能被動地等待可用的編碼機會，無法利用其它潛在的編碼機會。文獻[14-17]提出了能夠感知編碼機會的路由算法來克服COPE方法的缺點。近些年來，有大量的研究利用網絡編碼技術來探索地面網絡中包括無線自組網、無線網狀網和無線傳感器網絡的網絡傳輸性能提升方法，文獻[18]提出一種網絡編碼路由協議（NCRT,Network Coding Routing），利用編碼感知和負載感知路由度量來充分利用網絡編碼的優勢，并提出一種增強的編碼條件用以查找更多的編碼結構來傳輸更多的編碼分組，提高網絡容量。

綜合上面的分析，本文考慮了一個單源多目的的動態衛星網絡場景，然后針對網絡編碼與非網絡編碼情況對網絡容量進行了分析。本文的主要貢獻包含下面幾點：1）利用時間擴展圖對網絡的動態性進行了分析；2）針對網絡編碼的情形，分析了網絡容量并獲得最優解；3）針對非網絡編碼情形，分析了網絡容量并提出基于二分法的最優容量解；4）提供了仿真場景來評估網絡編碼對性能的影響。

1 系統模型

1.1 網絡場景

考慮一個單源多播的傳輸場景，其中源節點S向包含多個目的節點的目的節點集合D={di|i=1,2,…,N}傳輸同一段數據，利用線性網絡編碼的方法提高網絡的傳輸容量。業務在源節點產生時，源節點將原始數據劃分為多個分段，每個分段包含相同數量的數據包，然后源節點將每個分段的原始數據包進行隨機的線性組合后依次發送出去，這個將原始數據進行線性組合的過程就是編碼；中間節點收到編碼數據包之后，將編碼數據包存儲在本地，并與其他編碼數據包一起重新進行線性組合生成新的編碼數據包，然后發送出去；最后目的節點收到編碼數據包之后不再進行轉發，當其收到足夠多的非線性相關的編碼數據包便可以解碼得到原始數據包。

衛星網絡的動態特性是衛星網絡相關算法研究都需要處理的難點，動態性便意味著復雜性，如何處理衛星網絡復雜的動態變化是研究過程中首先要解決的問題。本文采用基于虛擬拓撲策略的動態拓撲分析方法，關鍵在于將衛星網絡連續的運行周期離散化，分解為多個時間片段，相應地，衛星網絡的動態特性也隨之離散靜止化。

為了刻畫網絡的動態性，本文將衛星網絡建模為一個時間擴展圖G(V,E,C,T,B)。具體的符號含義如下所示。T={1,2,...,n}表示時隙集合。對于衛星網絡的運行周期T，本文將其等間隔地劃分為n個時隙，每個時隙的持續時長為τ，即：

時隙的劃分是為了靜態化處理衛星網絡拓撲，在每個時隙內衛星之間的可見關系認為是固定不變的，一顆衛星A若在一個時隙的時間內持續可見另一顆衛星B，才認為衛星A在該時隙可見衛星B。對于衛星網絡的節點可見關系，這里可以用一個時間相關的矩陣集合表示，即V={vi,1≤i≤M}，表示衛星節點i。

衛星網絡中星間鏈路的存在與否也可以用一個時間相關的矩陣集合來表示，其中為第t個時隙的衛星網絡的星間鏈路矩陣。

星間鏈路的建立需要滿足衛星雙方相互可見的條件，也就是必須在的條件下，衛星i和衛星j才有可能建立星間鏈路。若不考慮其他建鏈約束，認為衛星之間相互可見即存在星間鏈路：

C={C(t)|t∈T }為衛星網絡在每個時隙的鏈路容量集合，為第t時隙的鏈路容量集合。其中可以根據香農公式計算：

其中GT、GR、P分別表示傳輸增益、接收增益以及發射功率。k、T、B分別表示玻爾茲曼常數、噪聲溫度以及帶寬，為兩個節點在第t個時隙的自由空間路損。

綜合以上的分析和總結，本文利用時間擴展圖對動態衛星網絡進行靜態地刻畫。首先，引入存儲弧的概念將網絡中不同時隙的同一節點連接起來，用以表示數據可以從上一時隙傳輸到下一時隙，將不同時隙的靜態拓撲相連接，實現數據的跨時隙傳輸，因此存儲弧必然是單向的，因為數據只能從上一時隙往下傳，而不能逆時間傳輸。圖1所示為包含5個節點的衛星網絡時間擴展圖。

圖1 衛星網絡時間擴展圖

圖1中存在兩種類型的弧，其中黑色的弧表示鏈路弧，用來反映衛星網絡的連通關系，其權重為星間鏈路傳輸容量，紅色的弧為存儲弧，用來反映節點在轉發受限時自身的緩存能力，是連通相鄰時隙拓撲圖的關鍵，其權重為衛星節點的緩存空間的大小。

時間擴展圖通將分隔的各時隙拓撲圖聯系起來，能夠反映數據跨時隙傳輸的過程，真正實現了衛星網絡從動態到靜態的轉化，基于此，用于分析網絡容量的最大流算法便可以直接應用，至此我們完成了對衛星網絡動態拓撲處理模型的描述。

1.2 優化目標與約束條件

對于給定的網絡傳輸模型，由于空間動態網絡中的數據傳輸采用的是“接收-存儲-轉發”的機制，因此，在每個時隙中，每個中間節點從上一跳節點中接收到的流量與從上一個時隙緩存下來的流量之和應該等于該節點在本時隙轉發出去的數據量加上存儲在本節點中緩存到下一時隙的數據量。因此，對于每個目的節點的網絡流而言，中間節點的流守恒約束為：

對于網絡流的源節點來說，每個時隙傳輸的數據總量應該由兩部分組成，一是本時隙成功發送的數據量，二是在本節點中緩存到下一時隙的數據量：

其中vs表示源節點，表示第t時隙源節點傳輸的數據總量。

對于網絡流的目的節點來說，目的節點只接收數據，數據到達目的節點之后不再轉發，因此也不會緩存到下一時隙，則有：

考慮到衛星節點的存儲空間有限，每個時隙各節點緩存到下一時隙的數據量應滿足以下約束：

除此之外，還需要添加上網絡流容量的約束。對于網絡編碼的場景，流量約束為：

對于非網絡編碼的場景，網絡流約束為：

對于單源多目的的衛星網絡多播場景，網絡容量實際上是衛星網絡在指定的時間內從源衛星節點發送相同數據到多個目的衛星節點的數據量上限。利用網絡編碼的鏈路資源共享特性，基于線性網絡編碼方案下的系統多播容量，實際上僅受各通向目的節點的網絡流中單播容量最小的一個限制，因此基于網絡編碼的優化問題可以表示為：

非網絡編碼的優化問題可以表示為：

2 求解方法

2.1 基于網絡編碼的求解方法

對于優化問題(12)，可以看出它是一個可分離的問題。根據目的節點的不同，可以將其分解為N并行的子問題，也就是：

假設對于每個目的節點d而言，問題(14)的最優目標函數值為,d∈D。則優化問題(14)的最優目標函數值為。因此，求解問題(12)的關鍵是求解問題(14)。

通過分析問題(14)，這是一個單源多目的最大流問題。有多個目的節點的主要原因是衛星網絡是隨時間變化的，盡管衛星是相同的，但是在每一個時刻衛星的狀態是不同的。為了求解這一問題，可以添加一個虛擬節點，然后添加虛擬邊來連通每一個目的節點，并將虛擬邊的容量設置為無窮大。為了說明這一過程，本文給出一個例子。

如圖2所示，圖中有一個源節點S兩個，目的節點D1、D2，三個中繼節點。網絡周期被劃分為3個時隙，在每個時隙中，盡管目的節點沒有改變，但是對于兩個不同的時隙，我們認為這是兩個不同的節點。然后，添加虛擬節點R1、R2。對于不同時隙的目的節點D1，添加單向弧將其與虛擬節點R1連接；對于目的節點D2，添加單向弧將其與虛擬節點R2連接，然后將虛擬邊的容量設置為無窮大。

圖2 網絡編碼的時間擴展圖

數據只能通過各時隙目的節點傳輸到達虛擬節點，因此從源節點S傳輸到達虛擬目的節點R的數據量即為從源節點到各時隙目的節點的數據量之和，利用Ford-Fulkerson最大流算法求節點S到節點R的最大流即可求得動態衛星網絡中源衛星到目的衛星的最大流。

2.2 非網絡編碼的求解方法

對于優化問題(13)，情況則變得更加復雜。這是由于約束(11)是一個耦合約束。為了處理這個問題，我們在下面提出一種方法來獲得該問題的最優解。

首先，假設y*是問題(13)的最優目標值。然后，必然存在一個最優解使得對于任意的d∈D，滿足。進一步，原問題(13)可以轉換如下：

然后，根據2.1節中的思路進一步刻畫相應的時間擴展圖。如圖3所示，進一步添加一個虛擬節點R，并添加虛擬邊將其與R1、R2連接，邊的容量設置為y。

圖3 非網絡編碼的時間擴展圖

然后，根據上面的方法可以定義一個y-最大流函數F(y)。這里，函數F(y)表示當虛擬邊容量為y時節點S到節點R的最大流量。然后，很顯然地可以得到下面的性質。

性質1：函數F(y)是關于y是非遞減的。

這個性質是顯然的，因為隨著邊容量的增加，網絡的最大流肯定是非遞減的。

性質2：F(y)-Ny≤0

這個性質也是顯然的，因為網絡的最大流量不可能超過割集的容量。

性質3：存在y*使得當0≤y≤y*時，F(y)-Ny=0；當y＞y*時，F(y)-Ny＜0。

這是因為當y比較小的時候，紫色虛擬邊構成的割集是限制網絡最大流的最關鍵因素；而當y趨近于無窮大的時候，網絡中的其他邊則成了限制網絡最大流的主要因素。

然后根據這些性質，我們給出下面的定理。

定理1：假設y*=argmax(F(y)?Ny)，則y*是問題(15)的最優解。

證明：首先根據性質3，F(y*)?Ny*=0是必然成立的。因此，根據前面的敘述，y*對應的解必然是問題(13)的一個可行解。然后，假設它不是最優解，則最優目標值y**＞y*。此時，只需要將紫色虛擬邊的容量設置y**，則可得F(y**)?Ny**=0。然而這與前面的假設矛盾，因此完成了該定理的證明。

為了得到這個最優解，我們利用二分法來設計算法。算法的基本步驟如下所示：

3 仿真分析

仿真以導航衛星網絡為背景，考慮了一個包含24顆MEO衛星的Walker星座衛星網絡，具體相關仿真場景中的常量參數如表1所示。接下來將從空間動態網絡的功率資源、緩存資源、運行時長和多播場景中目的節點數量四種因素對網絡容量的影響進行仿真分析。

表1 相關仿真場景中的常量參數

本實驗采用控制變量的方法，令仿真中的其他參數固定不變，其中假設仿真時長為300 s，即5個時隙，目的節點數量為2個，每顆衛星的最大緩存空間為500 Mbit，仿真在不同傳輸功率下網絡編碼方案以及功率分配優化方案對空間動態網絡容量的優化性能，各功率值對應場景仿真1 000次取平均，每次仿真源節點及目的節點從所有網絡節點中隨機選取。仿真結果如圖4所示。

圖4 網絡容量隨節點功率變化曲線

從圖4中可以看出，隨著每顆衛星的總傳輸功率的增加，平均系統多播容量也隨之增加，并且功率從50 W到800 W的大跨度增長下，網絡容量仍能繼續提升，這是因為節點功率與鏈路容量息息相關，而只要鏈路容量持續增大，則網絡容量便能隨之持續增長。在同一功率情況下，基于網絡編碼的方法與非網絡編碼方案相比，網絡容量得到了明顯的提升。在功率增長時網絡編碼方案具有更快的網絡容量增長速度，明確地展示了網絡編碼方案的優越性。

然后，為了評估時隙長度對性能的影響，我們給出了圖5。假設每顆衛星的最大緩存空間為1 Gbit，每顆衛星的總傳輸功率為100 W，目的節點數量為2個，仿真在不同仿真時長下網絡編碼方案以及功率分配優化方案對空間動態網絡容量的優化性能。仿真結果見圖5。

圖5 網絡容量隨仿真時長變化曲線

從圖5可以看出，在一定范圍內，隨著仿真時長的增加，網絡容量也在不斷增加，這是因為隨著仿真時長的增加，數據可以通過在節點中緩存的形式在后續增加的時隙中傳輸，使得網絡中可傳輸的數據量更多，但由于節點的存儲空間是有限的，隨著傳輸數據量的增加，當某個時隙的節點緩存空間被占用完后，數據不能無限制地往后續時隙緩存，網絡中的數據在一定時隙內便會被傳輸完成，使得即使仿真時長增加也沒有數據在后續時隙中傳輸，因而當仿真時長增加到一定值時，網絡容量便不再增長。通過對比發現，網絡編碼方案與非網絡編碼方案相比將網絡傳輸容量的極限提升了3倍之多，說明在充分利用仿真時間內的功率資源和緩存資源的情況下，更能凸顯網絡編碼的強大性能。

4 結束語

本文研究了衛星網絡的容量提升方法，包括網絡編碼與非網絡編碼兩種情形。其中，采用網絡編碼的最優衛星網絡容量可以求解多個單源單目的網絡最大流問題而得到。對于非網絡編碼情形，我們提出了基于二分法的最有容量求解方法。根據仿真結果，與非網絡編碼方案相比，采用網絡編碼的方案可以明顯地提升網絡的容量，并且，網絡容量提升幅度隨著資源以及網絡規模的增加而增加。這也充分說明了網絡編碼技術的使用可以充分利用衛星網絡的資源，從而改善衛星網絡資源極其受限的情況。