楊華果，陳 全，楊自鵬，張 群，吳 帥，楊 磊

(1.國(guó)防科技大學(xué)空天科學(xué)學(xué)院，長(zhǎng)沙 410073；2.北京宇航系統(tǒng)工程研究所，北京 100076；3.軍事科學(xué)院，北京 100091)

0 引言

近年來(lái)，衛(wèi)星通信在民生等各領(lǐng)域發(fā)揮了重要作用。低軌衛(wèi)星間可以通過(guò)建立星間鏈路形成衛(wèi)星組網(wǎng)，低軌衛(wèi)星網(wǎng)絡(luò)可以提供廣覆蓋、低時(shí)延、大容量的通信服務(wù)和隨遇接入的網(wǎng)絡(luò)服務(wù)，且具有鏈路損耗少、成本低、布設(shè)不受影響等優(yōu)點(diǎn)[1-3]，可提供不依賴地面網(wǎng)絡(luò)的通信服務(wù)，有效彌補(bǔ)地面通信網(wǎng)絡(luò)和高軌衛(wèi)星網(wǎng)絡(luò)的不足。

隨著衛(wèi)星通信技術(shù)的發(fā)展，發(fā)射成本逐漸降低，市場(chǎng)需求量不斷擴(kuò)大，低軌衛(wèi)星網(wǎng)絡(luò)向著巨型星座發(fā)展。近年來(lái)，“星鏈”(Starlink)、“一網(wǎng)”(OneWeb)和“柯伊伯”(Kuiper)等星座項(xiàng)目推動(dòng)了低軌巨型星座的飛速發(fā)展[4]。本文研究的主要對(duì)象為低軌巨型星座網(wǎng)絡(luò)，其網(wǎng)絡(luò)通信圖如圖1所示，包含地面網(wǎng)絡(luò)和衛(wèi)星星座網(wǎng)絡(luò)。地面網(wǎng)絡(luò)由分布在各地的信關(guān)站和用戶終端組成，衛(wèi)星星座網(wǎng)絡(luò)通過(guò)星間鏈路相連。

圖1 低軌衛(wèi)星網(wǎng)絡(luò)通信圖Fig.1 LEO satellite network communication

在低軌衛(wèi)星網(wǎng)絡(luò)的設(shè)計(jì)和建設(shè)中，衛(wèi)星網(wǎng)絡(luò)容量是網(wǎng)絡(luò)性能評(píng)價(jià)的重要指標(biāo)，反映網(wǎng)絡(luò)的最大服務(wù)能力，可以為提高網(wǎng)絡(luò)效率、設(shè)計(jì)高效的網(wǎng)絡(luò)協(xié)議提供依據(jù)[5]。網(wǎng)絡(luò)容量可定義為星間鏈路單位時(shí)間內(nèi)傳輸?shù)淖畲髷?shù)據(jù)量，即網(wǎng)絡(luò)能夠承載流量的最大值?，F(xiàn)有的衛(wèi)星網(wǎng)絡(luò)容量分析常采用仿真分析法、建模優(yōu)化法和數(shù)值分析法[6]。文獻(xiàn)[7]利用空間網(wǎng)絡(luò)仿真平臺(tái)分析了不同路由策略下的網(wǎng)絡(luò)吞吐量。文獻(xiàn)[8]建模了衛(wèi)星通信系統(tǒng)最大化信道有效容量的功率分配問(wèn)題，文獻(xiàn)[9]建立了網(wǎng)絡(luò)容量模型，并利用改進(jìn)后的分布式遺傳算法得出衛(wèi)星網(wǎng)絡(luò)容量上限。當(dāng)前已有的方法應(yīng)用于巨型星座仿真時(shí)大多計(jì)算復(fù)雜度高，耗時(shí)長(zhǎng)，特別是利用網(wǎng)絡(luò)仿真平臺(tái)的方法對(duì)計(jì)算機(jī)硬件要求較高，且計(jì)算開(kāi)銷隨網(wǎng)絡(luò)節(jié)點(diǎn)數(shù)增大而迅速增加，在巨型星座網(wǎng)絡(luò)評(píng)估中將產(chǎn)生巨大的計(jì)算開(kāi)銷。巨型星座規(guī)模的擴(kuò)張不僅提升了系統(tǒng)容量，也增加了系統(tǒng)復(fù)雜度和性能評(píng)估難度。

因此，本文提出一種基于最大流的網(wǎng)絡(luò)容量評(píng)估方法，通過(guò)求解最大流來(lái)替代網(wǎng)絡(luò)路由仿真，從而有效減小巨型星座網(wǎng)絡(luò)容量評(píng)估的復(fù)雜度與計(jì)算開(kāi)銷。最后基于“星鏈”星座，進(jìn)一步研究了星座構(gòu)型、星間鏈路拓?fù)溥B接方式、鏈路容量及用戶需求量對(duì)巨型星座網(wǎng)絡(luò)容量的影響。

1 基于最大流的低軌衛(wèi)星網(wǎng)絡(luò)容量評(píng)估模型

本文主要采用求解最大流的方法代替網(wǎng)絡(luò)仿真來(lái)進(jìn)行網(wǎng)絡(luò)容量的評(píng)估。在給定網(wǎng)絡(luò)規(guī)模下以最大流方法計(jì)算求解網(wǎng)絡(luò)容量，分析網(wǎng)絡(luò)容量與星座構(gòu)型、星間鏈路拓?fù)溥B接方式及鏈路容量的關(guān)系。衛(wèi)星之間通過(guò)建立星間鏈路來(lái)實(shí)現(xiàn)連通和通信，每顆衛(wèi)星可建立2條、3條、4條或6條星間鏈路。星地下行鏈路的流量遠(yuǎn)大于星地上行鏈路，因此星地鏈路主要考慮下行鏈路。在進(jìn)行仿真建模時(shí)，根據(jù)先驗(yàn)知識(shí)，綜合考慮地面信關(guān)站的布局、鏈路容量及功率分配等參數(shù)對(duì)網(wǎng)絡(luò)容量的影響，設(shè)定各參數(shù)值。

1.1 衛(wèi)星網(wǎng)絡(luò)模型

圖2 低軌衛(wèi)星網(wǎng)絡(luò)星座構(gòu)型圖Fig.2 LEO satellite network constellation

衛(wèi)星星座作為衛(wèi)星網(wǎng)絡(luò)研究的模型基礎(chǔ)，決定著衛(wèi)星網(wǎng)絡(luò)的整個(gè)體系架構(gòu)[10]。假設(shè)采用Walker-Delta星座構(gòu)型，其構(gòu)型如圖2所示，軌道面?zhèn)€數(shù)為N1，每個(gè)軌道面上的衛(wèi)星數(shù)量為N2。整個(gè)星座是均勻?qū)ΨQ的，且不存在反向縫?；趫D論方法，在衛(wèi)星星座中，可將每顆衛(wèi)星抽象為圖的一個(gè)節(jié)點(diǎn)，相鄰節(jié)點(diǎn)之間通過(guò)全雙工鏈路實(shí)現(xiàn)通信，這種鏈路即為星間鏈路 ISL(Inter-Sate-llite Link)[11]，將星間鏈路抽象為圖的邊。依據(jù)相鄰兩節(jié)點(diǎn)是否在相同軌道面內(nèi)，將星間鏈路分為軌內(nèi)星間鏈路(intra-plane ISL)和軌間星間鏈路(inter-plane ISL)[12]。

衛(wèi)星節(jié)點(diǎn)集為

S={a=(a1,a2)|0≤a1≤N1-1,
0≤a2≤N2-1}

(1)

其中，節(jié)點(diǎn)a代表位于第a1軌道上的第a2顆衛(wèi)星。鏈路集為

(2)

其中，b=((a1±1)modN1，a2)時(shí)，鏈路(a，b)代表相鄰軌道上第a2顆衛(wèi)星間的鏈路；b=(a1，(a2±1)modN2)時(shí)，鏈路(a，b)代表同一軌道上相鄰衛(wèi)星間的鏈路。網(wǎng)絡(luò)中的每顆衛(wèi)星在水平和垂直方向上各有2個(gè)相鄰節(jié)點(diǎn)，每顆衛(wèi)星均采用一星四鏈的連接方式[13]，網(wǎng)絡(luò)的局部拓?fù)淙鐖D3所示。

圖3 衛(wèi)星網(wǎng)絡(luò)局部拓?fù)銯ig.3 Satellite network partial topology

1.2 最大流算法原理

最大流問(wèn)題是研究在給定條件下如何使網(wǎng)絡(luò)流量達(dá)到最大值的組合優(yōu)化問(wèn)題[14]，其實(shí)質(zhì)就是求解從源點(diǎn)到達(dá)匯點(diǎn)的流量最大值[15]。求解最大流能夠?yàn)榇笠?guī)模網(wǎng)絡(luò)的計(jì)算研究提供基礎(chǔ)，其中一種經(jīng)典的解法為增載軌算法[16]。

在給定網(wǎng)絡(luò)中進(jìn)行流量傳輸時(shí)每條鏈路的容量是固定值，當(dāng)流量開(kāi)始分配后，每條鏈路上的剩余容量都會(huì)隨之改變。如果在從源節(jié)點(diǎn)到匯節(jié)點(diǎn)的一條鏈路中的每條邊都存在非零的剩余流量，則將該條鏈路稱為增廣鏈。該條鏈上還能增加的流量由所有邊中最小的剩余容量決定。增載軌算法就是在具有剩余容量的網(wǎng)絡(luò)中沿可行路徑增廣流值，直至網(wǎng)絡(luò)中不存在增廣鏈時(shí)累加達(dá)到的可行流就是整個(gè)網(wǎng)絡(luò)容量的最大值。

增廣鏈的正確選擇有利于提高計(jì)算效率，在進(jìn)行增廣鏈確定時(shí)需要首先確定一條從源節(jié)點(diǎn)到匯節(jié)點(diǎn)的通路，且該條鏈路每條邊均具有剩余容量，然后對(duì)每個(gè)節(jié)點(diǎn)進(jìn)行搜索，確定所有能到達(dá)的下一節(jié)點(diǎn)，直至得到包含所有節(jié)點(diǎn)的樹(shù)，最終確定一條增廣鏈。

在容量網(wǎng)絡(luò)G=(V，A，c)中，將從源點(diǎn)s到匯點(diǎn)t的非負(fù)函數(shù)fst定義為可行流，假如fst滿足以下條件[17]

(3)

則fst成為容量網(wǎng)絡(luò)G=(V，A，c)的全部可行流之一，當(dāng)該流值為所有流中的最大值時(shí)則成為最大流，記為fmax。

1.3 基于最大流的網(wǎng)絡(luò)容量評(píng)估模型

在實(shí)際運(yùn)行過(guò)程中，星下用戶密度不均且需求量不一致，會(huì)導(dǎo)致數(shù)據(jù)流量不一致，且不會(huì)一直保持飽和狀態(tài)[6]，因此將所有用戶虛擬為一個(gè)源節(jié)點(diǎn)，所有信關(guān)站虛擬為一個(gè)匯節(jié)點(diǎn)。源節(jié)點(diǎn)與所有衛(wèi)星相連，匯節(jié)點(diǎn)與距離每個(gè)信關(guān)站最近的兩顆衛(wèi)星相連。由于衛(wèi)星一直處于高速運(yùn)動(dòng)中，網(wǎng)絡(luò)拓?fù)浜途W(wǎng)絡(luò)容量都會(huì)隨之產(chǎn)生動(dòng)態(tài)變化，在仿真中可將衛(wèi)星運(yùn)行周期劃分為多個(gè)時(shí)間片，假設(shè)在各時(shí)間片中網(wǎng)絡(luò)拓?fù)錇殪o態(tài)，分別求解各時(shí)間片的最大流，計(jì)算平均值作為最終的網(wǎng)絡(luò)容量。

衛(wèi)星網(wǎng)絡(luò)最大流的模型示意圖如圖4所示。

圖4 衛(wèi)星網(wǎng)絡(luò)最大流模型示意圖Fig.4 Maximum flow model of satellite network

2 仿真算例

根據(jù)前文分析，以“星鏈”550 km軌道層星座的規(guī)模為例，進(jìn)行具體仿真實(shí)驗(yàn)。在給定的網(wǎng)絡(luò)規(guī)模下計(jì)算求解該網(wǎng)絡(luò)的最大流。最后，分析網(wǎng)絡(luò)容量與星座構(gòu)型、星間鏈路拓?fù)溥B接方式及鏈路容量的關(guān)系。

2.1 網(wǎng)絡(luò)容量求解

以“星鏈”550 km軌道層星座為基礎(chǔ)研究對(duì)象，星座包含72個(gè)軌道面，且每個(gè)軌道面上有22顆在軌衛(wèi)星。在計(jì)算網(wǎng)絡(luò)容量時(shí)綜合考慮星地連接約束、鏈路拓?fù)鋭?dòng)態(tài)變化、鏈路容量約束。地面采用全球分布的30個(gè)信關(guān)站布局，仿真場(chǎng)景設(shè)置參考已有文獻(xiàn)[18]。星座結(jié)構(gòu)決定衛(wèi)星間的相鄰關(guān)系、星間鏈路數(shù)量和網(wǎng)絡(luò)拓?fù)涞淖兓绞絒19-20]。在求解網(wǎng)絡(luò)容量中，首先要獲取低軌衛(wèi)星星座的星座構(gòu)型及其余各項(xiàng)參數(shù)，之后對(duì)每顆衛(wèi)星進(jìn)行編號(hào)，每顆衛(wèi)星的所在位置與網(wǎng)絡(luò)節(jié)點(diǎn)一一對(duì)應(yīng)。將衛(wèi)星運(yùn)行周期按照鏈路特性及運(yùn)動(dòng)規(guī)律劃分為多個(gè)時(shí)間片，在各時(shí)間片中將網(wǎng)絡(luò)拓?fù)湟暈殪o態(tài)。確定星間鏈路連接方式后生成鄰接矩陣，對(duì)矩陣進(jìn)行賦值。若兩顆衛(wèi)星間有連接則矩陣中對(duì)應(yīng)數(shù)值為1，否則為0。然后為每顆衛(wèi)星計(jì)算用戶流量輸入，并確定衛(wèi)星與信關(guān)站的連接狀態(tài)。最后，對(duì)各時(shí)間片分別求解最大流，將各時(shí)間片下的最大流值求平均即為該衛(wèi)星網(wǎng)絡(luò)的網(wǎng)絡(luò)容量。本文討論的方法均是對(duì)一個(gè)時(shí)間片進(jìn)行仿真驗(yàn)證，實(shí)際仿真過(guò)程中將仿真時(shí)間片設(shè)置為30 s，共仿真12 h，最后計(jì)算各時(shí)間片的網(wǎng)絡(luò)容量平均值。

貪婪算法是通過(guò)組合局部最優(yōu)解來(lái)構(gòu)建全局最優(yōu)解，在優(yōu)化問(wèn)題和網(wǎng)絡(luò)分析等領(lǐng)域被廣泛應(yīng)用。為驗(yàn)證本文方法的正確性和有效性，本文首先采用了貪婪算法求解網(wǎng)絡(luò)容量，并以“星鏈”550 km軌道層星座為研究對(duì)象，涵蓋了72個(gè)軌道面，且每個(gè)軌道面上有22顆在軌衛(wèi)星，每顆衛(wèi)星均建立4條星間鏈路。該算法計(jì)算復(fù)雜度為O(n2)，其中n是輸入規(guī)模，即總節(jié)點(diǎn)數(shù)。最大流算法的計(jì)算復(fù)雜度為O(mf)，其中m是圖的邊數(shù)，f是最大流的值。在本文設(shè)定的仿真規(guī)模條件下，最大流算法具有更低的計(jì)算復(fù)雜度。采用貪婪算法對(duì)網(wǎng)絡(luò)進(jìn)行仿真時(shí)，得到的計(jì)算數(shù)據(jù)與最大流算法的輸出相同，驗(yàn)證了該算法的正確性和有效性，但是，貪婪算法的平均運(yùn)行時(shí)間遠(yuǎn)大于最大流算法的平均運(yùn)行時(shí)間，說(shuō)明所提方法在巨型星座場(chǎng)景下的計(jì)算效率更高。兩種算法的性能比較如圖5所示。

圖5 兩種算法的性能比較Fig.5 Performance comparison of two algorithms

2.2 不同星座構(gòu)型下的仿真分析

“星鏈”550 km軌道層星座共有1 584顆衛(wèi)星，假設(shè)每顆衛(wèi)星均建立4條星間鏈路，即與其同軌前后和異軌左右的4顆相鄰衛(wèi)星建立星間鏈路。其中，每條軌道面上的第1顆衛(wèi)星同第N2顆衛(wèi)星建鏈，第一軌道面的衛(wèi)星同第N1軌道面的衛(wèi)星建鏈，形成無(wú)縫的均勻?qū)ΨQ網(wǎng)絡(luò)。假設(shè)每條星間鏈路容量為100 Mbit/s，用戶需求總量為20 Gbit/s，信關(guān)站容量為2 Gbit/s。在保持星座衛(wèi)星總數(shù)不變的情況下，改變軌道面數(shù)N1和每軌衛(wèi)星數(shù)N2，得到不同的星座構(gòu)型。不同星座構(gòu)型下仿真得到的網(wǎng)絡(luò)容量結(jié)果如表1所示。

表1 不同星座構(gòu)型下的網(wǎng)絡(luò)容量

由表1的仿真結(jié)果可知，在給定的星座規(guī)模中通過(guò)改變軌道數(shù)目和單軌衛(wèi)星數(shù)可設(shè)計(jì)不同的星座構(gòu)型，而不同配置的星座構(gòu)型會(huì)導(dǎo)致網(wǎng)絡(luò)性能的不同。仿真結(jié)果表明，當(dāng)N1與N2相差值最小(N1=36，N2=44)時(shí)，網(wǎng)絡(luò)容量達(dá)到最大。其成因可能是N1與N2更接近，星座的Mesh狀拓?fù)渚鶆驅(qū)ΨQ性更強(qiáng)，網(wǎng)絡(luò)連接效率更高，導(dǎo)致更大的網(wǎng)絡(luò)容量。

2.3 不同星間鏈路拓?fù)溥B接下的仿真分析

在給定規(guī)模的衛(wèi)星網(wǎng)絡(luò)中不同的拓?fù)溥B接方式將導(dǎo)致網(wǎng)絡(luò)性能的不同。星座包含72個(gè)軌道面，且每個(gè)軌道面上有22顆在軌衛(wèi)星，通過(guò)連接星間鏈路建立對(duì)稱的網(wǎng)絡(luò)。假設(shè)每條星間鏈路容量為100 Mbit/s，信關(guān)站容量為2 Gbit/s。本文選用的建鏈方式包括一星兩鏈(2-ISL)、一星三鏈(3-ISL)、一星四鏈(4-ISL)和一星六鏈(6-ISL)。不同的建鏈方式如圖6所示，仿真得到的網(wǎng)絡(luò)容量結(jié)果如表2所示。

(a)一星兩鏈

(b)一星三鏈

(c)一星四鏈

(d)一星六鏈圖6 不同星間鏈路的拓?fù)涫疽鈭DFig.6 Topological diagrams of different inter-satellite links

表2 不同星間鏈路拓?fù)溥B接下的網(wǎng)絡(luò)容量

由表2的仿真結(jié)果可以看出，在給定衛(wèi)星數(shù)目和構(gòu)型的星座內(nèi)，衛(wèi)星間建立的鏈路數(shù)目越多，網(wǎng)絡(luò)容量越大。星間鏈路的增加可提升網(wǎng)絡(luò)連接性，由于星間鏈路數(shù)目增加，同一時(shí)間單顆衛(wèi)星可承載的數(shù)據(jù)量也增加，進(jìn)而導(dǎo)致網(wǎng)絡(luò)容量增大?？紤]到星上體積功率受限以及星間通信終端的資源占用，單星可建立的星間鏈路數(shù)目也受限制，目前常見(jiàn)的構(gòu)型一般采用3～4ISL構(gòu)型。

2.4 不同鏈路容量參數(shù)下仿真分析

衛(wèi)星網(wǎng)絡(luò)系統(tǒng)中不同鏈路的容量差異也影響著整個(gè)網(wǎng)絡(luò)的傳輸效率及網(wǎng)絡(luò)容量。以“星鏈”星座550 km軌道層為研究對(duì)象，共有72個(gè)軌道面，且每個(gè)軌道面上都有22顆衛(wèi)星。假設(shè)每顆衛(wèi)星均采用一星四鏈的連接方式，用戶需求總量為100 Gbit/s。改變星間鏈路容量，得到不同星間鏈路容量下的平均網(wǎng)絡(luò)容量，如表3所示。

表3 不同星間鏈路容量下的網(wǎng)絡(luò)容量

由表3的仿真結(jié)果可以看出，在衛(wèi)星網(wǎng)絡(luò)規(guī)模及星座構(gòu)型確定的場(chǎng)景下，網(wǎng)絡(luò)容量隨星間鏈路容量的增加而增加，但當(dāng)星間鏈路容量增加到一定值時(shí)，網(wǎng)絡(luò)容量趨于平穩(wěn)，不再增加。其原因是，衛(wèi)星承載的流量來(lái)自其自身覆蓋域內(nèi)的業(yè)務(wù)量和周邊衛(wèi)星經(jīng)星間鏈路轉(zhuǎn)發(fā)的業(yè)務(wù)量。當(dāng)星間鏈路容量較小時(shí)，星上流量受限于星間鏈路容量，將隨著星間鏈路容量增加而增加，從而增加系統(tǒng)容量。當(dāng)星間鏈路足夠大時(shí)，星上業(yè)務(wù)量超出星地鏈路容量，限制了星上業(yè)務(wù)的星地傳輸，從而使得系統(tǒng)容量不再隨著星間鏈路容量增加而增加。

仿真中保持其他鏈路容量不變，改變用戶需求總量，得到不同用戶需求量下的網(wǎng)絡(luò)吞吐量結(jié)果，如表4所示。

表4 不同用戶需求總量下的網(wǎng)絡(luò)吞吐量

由表4的仿真結(jié)果可以看出，在衛(wèi)星規(guī)模及星座構(gòu)型確定的場(chǎng)景下，用戶需求總量也將影響整個(gè)網(wǎng)絡(luò)的吞吐量。當(dāng)用戶需求總量較少時(shí)，全部用戶業(yè)務(wù)需求都可轉(zhuǎn)發(fā)至信關(guān)站，此時(shí)網(wǎng)絡(luò)吞吐量與用戶需求量相等，隨著用戶需求量增長(zhǎng)而快速增長(zhǎng)。當(dāng)用戶需求總量較大時(shí)，受限于星間鏈路容量和星地鏈路容量，無(wú)法將所有數(shù)據(jù)下傳至匯節(jié)點(diǎn)，此時(shí)網(wǎng)絡(luò)吞吐量小于用戶需求總量，且兩者差值逐漸增大，網(wǎng)絡(luò)吞吐量逐漸增大至星間鏈路/星地鏈路確定的網(wǎng)絡(luò)容量上限。在本算例中，限制網(wǎng)絡(luò)容量的主要參數(shù)為星間鏈路容量。

3 總結(jié)

本文研究了采用最大流算法求解低軌衛(wèi)星網(wǎng)絡(luò)容量，以“星鏈”星座為例，分別分析了在給定規(guī)模下不同的星座構(gòu)型、星間建鏈數(shù)與鏈路容量參數(shù)對(duì)網(wǎng)絡(luò)容量的影響。與傳統(tǒng)網(wǎng)絡(luò)容量評(píng)估方法相比，計(jì)算復(fù)雜度更低，計(jì)算耗時(shí)更短。根據(jù)仿真結(jié)果可知，網(wǎng)絡(luò)容量與星間建鏈數(shù)和星間鏈路容量呈正相關(guān)。此外，網(wǎng)絡(luò)容量還受星座構(gòu)型和用戶需求總量等參數(shù)的影響。在設(shè)計(jì)通信網(wǎng)絡(luò)時(shí)可以考慮增加星間鏈路數(shù)，以提高整個(gè)網(wǎng)絡(luò)效率。