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

（哈爾濱工業(yè)大學，山東 威海 264209）

0 引言

空間動態(tài)網(wǎng)絡[1-3]是伴隨著人們?nèi)找嬖鲩L的服務需求而不斷發(fā)展的，網(wǎng)絡用戶數(shù)量的增長、節(jié)點類型的多樣化、數(shù)據(jù)傳輸?shù)母哔|(zhì)量要求以及網(wǎng)絡資源的受限等一系列的特點使得空間動態(tài)網(wǎng)絡在網(wǎng)絡擴展、資源共享、一體化組網(wǎng)和網(wǎng)絡傳輸能力等方面面臨著更大的挑戰(zhàn)。因此，在不增加衛(wèi)星網(wǎng)絡節(jié)點數(shù)量、頻帶、存儲、功率等資源的情況下，探索有效提升網(wǎng)絡傳輸容量和服務質(zhì)量的網(wǎng)絡傳輸方法是目前國內(nèi)外在衛(wèi)星領域研究的熱點問題，也是空間動態(tài)網(wǎng)絡發(fā)展的關(guān)鍵。

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

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

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

1 系統(tǒng)模型

1.1 網(wǎng)絡場景

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

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

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

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

衛(wèi)星網(wǎng)絡中星間鏈路的存在與否也可以用一個時間相關(guān)的矩陣集合來表示，其中為第t個時隙的衛(wèi)星網(wǎng)絡的星間鏈路矩陣。

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

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

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

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

圖1 衛(wèi)星網(wǎng)絡時間擴展圖

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

時間擴展圖通將分隔的各時隙拓撲圖聯(lián)系起來，能夠反映數(shù)據(jù)跨時隙傳輸?shù)倪^程，真正實現(xiàn)了衛(wèi)星網(wǎng)絡從動態(tài)到靜態(tài)的轉(zhuǎn)化，基于此，用于分析網(wǎng)絡容量的最大流算法便可以直接應用，至此我們完成了對衛(wèi)星網(wǎng)絡動態(tài)拓撲處理模型的描述。

1.2 優(yōu)化目標與約束條件

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

對于網(wǎng)絡流的源節(jié)點來說，每個時隙傳輸?shù)臄?shù)據(jù)總量應該由兩部分組成，一是本時隙成功發(fā)送的數(shù)據(jù)量，二是在本節(jié)點中緩存到下一時隙的數(shù)據(jù)量：

其中vs表示源節(jié)點，表示第t時隙源節(jié)點傳輸?shù)臄?shù)據(jù)總量。

對于網(wǎng)絡流的目的節(jié)點來說，目的節(jié)點只接收數(shù)據(jù)，數(shù)據(jù)到達目的節(jié)點之后不再轉(zhuǎn)發(fā)，因此也不會緩存到下一時隙，則有：

考慮到衛(wèi)星節(jié)點的存儲空間有限，每個時隙各節(jié)點緩存到下一時隙的數(shù)據(jù)量應滿足以下約束：

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

對于非網(wǎng)絡編碼的場景，網(wǎng)絡流約束為：

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

非網(wǎng)絡編碼的優(yōu)化問題可以表示為：

2 求解方法

2.1 基于網(wǎng)絡編碼的求解方法

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

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

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

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

圖2 網(wǎng)絡編碼的時間擴展圖

數(shù)據(jù)只能通過各時隙目的節(jié)點傳輸?shù)竭_虛擬節(jié)點，因此從源節(jié)點S傳輸?shù)竭_虛擬目的節(jié)點R的數(shù)據(jù)量即為從源節(jié)點到各時隙目的節(jié)點的數(shù)據(jù)量之和，利用Ford-Fulkerson最大流算法求節(jié)點S到節(jié)點R的最大流即可求得動態(tài)衛(wèi)星網(wǎng)絡中源衛(wèi)星到目的衛(wèi)星的最大流。

2.2 非網(wǎng)絡編碼的求解方法

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

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

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

圖3 非網(wǎng)絡編碼的時間擴展圖

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

性質(zhì)1：函數(shù)F(y)是關(guān)于y是非遞減的。

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

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

這個性質(zhì)也是顯然的，因為網(wǎng)絡的最大流量不可能超過割集的容量。

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

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

然后根據(jù)這些性質(zhì)，我們給出下面的定理。

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

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

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

3 仿真分析

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

表1 相關(guān)仿真場景中的常量參數(shù)

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

圖4 網(wǎng)絡容量隨節(jié)點功率變化曲線

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

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

圖5 網(wǎng)絡容量隨仿真時長變化曲線

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

4 結(jié)束語

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