張 方，周 淦，喻瑤瑤，聶殿輝，豐大軍

(1. 中國電子信息產(chǎn)業(yè)集團(tuán)有限公司第六研究所，北京 100083；2. 西安電子科技大學(xué) 空間科學(xué)與技術(shù)學(xué)院，陜西 西安 710071)

0 引言

隨著衛(wèi)星應(yīng)用和需求的不斷發(fā)展，衛(wèi)星導(dǎo)航系統(tǒng)無論是在戰(zhàn)略資源上還是商務(wù)民用方面都體現(xiàn)了其重要的應(yīng)用價(jià)值，給人們的工作和生活帶來很大的便利。然而，由于傳統(tǒng)的衛(wèi)星導(dǎo)航系統(tǒng)存在導(dǎo)航精度低、抗毀性能差和無自主運(yùn)行能力等缺點(diǎn)，已無法滿足人們對衛(wèi)星業(yè)務(wù)的需求。星間鏈路的建立則可以很好地解決以上問題，它不僅可以實(shí)現(xiàn)各節(jié)點(diǎn)(不同軌道的衛(wèi)星與地面站)之間的互聯(lián)互通，還幫助形成具有對空間傳輸信息的獲取、存儲、處理、傳輸以及分發(fā)等功能的空間信息網(wǎng)絡(luò)，是衛(wèi)星導(dǎo)航系統(tǒng)的必然發(fā)展方向[1-4]。

近年來，全球衛(wèi)星導(dǎo)航系統(tǒng)飛速發(fā)展并不斷完善，星間鏈路的引入給導(dǎo)航系統(tǒng)帶來較多的技術(shù)難題，其中，路由規(guī)劃問題成為研究的焦點(diǎn)。國內(nèi)外學(xué)者對于導(dǎo)航系統(tǒng)的路由規(guī)劃問題也有大量的研究成果可以借鑒。文獻(xiàn)[5]對星間可見性以及星間距離變化做了詳細(xì)分析，根據(jù)推導(dǎo)出的公式設(shè)計(jì)了一種靜態(tài)無需切換和一種動態(tài)帶切換的網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)；文獻(xiàn)[6]針對同軌道星間鏈路拓?fù)浣Y(jié)構(gòu)進(jìn)行分析，通過對比不同的拓?fù)浣Y(jié)構(gòu)對星地?cái)?shù)據(jù)傳輸性能的影響，得出當(dāng)數(shù)據(jù)在節(jié)點(diǎn)處理時(shí)延較大時(shí)同軌鏈路應(yīng)選擇八角星拓?fù)浣Y(jié)構(gòu)的結(jié)論；文獻(xiàn)[7]基于TDMA時(shí)分多址體制的星間通信模式提出了一種較為全面的通信代價(jià)評估方案，得出星間鏈路混合型拓?fù)浣Y(jié)構(gòu)比環(huán)形拓?fù)浣Y(jié)構(gòu)的通信性能更好的結(jié)論。

針對以上研究現(xiàn)狀，本文面向?qū)Ш叫亲芯堪l(wèi)星網(wǎng)絡(luò)所組成的天基網(wǎng)和各地面站所組成的地基網(wǎng)絡(luò)的多層空間網(wǎng)絡(luò)路由規(guī)劃問題，提出了一種混合路由方案。首先對節(jié)點(diǎn)負(fù)載和傳輸距離等影響數(shù)據(jù)傳輸?shù)囊蛩剡M(jìn)行單獨(dú)研究，然后綜合考慮等待時(shí)延、鏈路速率、節(jié)點(diǎn)負(fù)載和傳輸距離等多種影響因素，探索并建立合理的混合評價(jià)函數(shù)，使算法所規(guī)劃出的路徑能夠減小復(fù)雜的空間運(yùn)行環(huán)境對信息傳輸?shù)挠绊?，合理有效地利用星間鏈路資源，從而增強(qiáng)系統(tǒng)的穩(wěn)定性和可靠性，為正在建設(shè)過程中的“北斗”衛(wèi)星導(dǎo)航系統(tǒng)提供理論依據(jù)和應(yīng)用基礎(chǔ)。

1 星座拓?fù)浞治?/h2>

1.1 星座構(gòu)型

本文研究的空間網(wǎng)絡(luò)模型分為3層，包括高軌衛(wèi)星、中軌衛(wèi)星和地面站以及地面控制管理中心。其中，高軌衛(wèi)星高度約36 000 km，由3顆GEO和3顆IGSO構(gòu)成，GEO分布在赤道上，經(jīng)度分別為80°、110.5°和140°；IGSO軌道傾角為55°，三星相位差120°。中軌衛(wèi)星MEO由構(gòu)型為Walker24/3/1星座構(gòu)成，軌道高度為21 528 km，為了便于分析，將24顆MEO衛(wèi)星分別命名為MEOij(i∈[1,3]，表示軌道面編號；j∈[1,8]，表示軌道內(nèi)的衛(wèi)星編碼)。地面由3個(gè)地面站和1個(gè)地面控制管理中心構(gòu)成，分布于我國境內(nèi)，其中，地面控制管理中心通過對地面站合理的規(guī)劃與調(diào)度實(shí)現(xiàn)對衛(wèi)星的監(jiān)測與控制。導(dǎo)航星座整體架構(gòu)如圖1所示。

圖1 導(dǎo)航星座構(gòu)型示意圖

1.2 星間可視性分析

衛(wèi)星之間的可視性是星間通信的前提條件。目前影響衛(wèi)星之間的可視因素主要包括地球及大氣層的遮擋、衛(wèi)星天線波束掃描范圍限制以及電磁波測距極限3個(gè)方面，下面作詳細(xì)介紹。

(1)地球及大氣層的遮擋

假設(shè)地球半徑為R，衛(wèi)星軌道高度為h，大氣層厚度為H，衛(wèi)星A、B之間的距離為l，如圖2所示。

圖2 地球遮擋情況下衛(wèi)星可見關(guān)系示意圖

由幾何關(guān)系可得衛(wèi)星之間的距離l應(yīng)滿足如下關(guān)系式：

(1)

(2)衛(wèi)星天線波束掃描范圍限制

假設(shè)地球半徑為R，衛(wèi)星軌道高度為h，兩衛(wèi)星之間的距離為l，波束掃描范圍為±β，如圖3所示。

圖3 衛(wèi)星波束掃描范圍受限情況下可見關(guān)系示意圖

由幾何關(guān)系可得衛(wèi)星之間的距離l應(yīng)滿足如下關(guān)系式：

l>2(R+h)cosβ

(2)

綜上所述，兩衛(wèi)星之間建立通信的前提條件為它們之間的距離l應(yīng)滿足如下關(guān)系式：

(3)

(3)電磁波測距極限

衛(wèi)星A、B要能夠建立鏈路進(jìn)行通信，除了滿足以上兩個(gè)條件外，還必須滿足兩者之間的距離小于電磁波所能達(dá)到的最大距離，即：

l

(4)

式中，Lmax為測距極限，本文取Lmax=5 000 km。

因此，星間鏈路可見性可表述為：如果衛(wèi)星A、B之間的連線與地球表面(考慮大氣層)沒有交點(diǎn)，接收星在發(fā)射星的天線覆蓋范圍內(nèi)，且在發(fā)射星的測距范圍內(nèi)，則稱兩顆星是可見的；否則，如果缺少任何一個(gè)或幾個(gè)條件，則稱它們是不可見的。因此衛(wèi)星B對衛(wèi)星A的可見性VB→A定義為：VB→A=1，交點(diǎn)不存在，即可見；VB→A=0，交點(diǎn)存在，即不可見。由此，可以確定一個(gè)瞬時(shí)的拓?fù)浣Y(jié)構(gòu)。

1.3 衛(wèi)星拓?fù)淠Ｐ?/h3>

星間鏈路有3種，包括永久鏈路、非永久鏈路和不可見鏈路，分別對應(yīng)衛(wèi)星持續(xù)可見、非持續(xù)可見和永遠(yuǎn)不可見3種情況。對于導(dǎo)航星座來說，頻繁地切換拓?fù)浣Y(jié)構(gòu)對于系統(tǒng)的穩(wěn)定性是不利的，因此建立如下建鏈規(guī)則：

(1)優(yōu)先與永久鏈路建鏈，盡量減少網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)的切換頻度。

(2)采用在永久鏈路的基礎(chǔ)上增加非永久鏈路的組合方式建鏈，以避免鏈路性質(zhì)過于單一導(dǎo)致拓?fù)浣Y(jié)構(gòu)的抗毀性降低。

通過使用衛(wèi)星工具包(Satellite Tools Kit, STK)對星座進(jìn)行仿真，得到衛(wèi)星的永久鏈路有6條，包括同軌道中和本星相隔的2顆衛(wèi)星，西側(cè)相鄰軌道與目標(biāo)星平近點(diǎn)角相差-15°、-150°的2顆衛(wèi)星以及東側(cè)相鄰軌道與目標(biāo)星平近點(diǎn)角相差15°、150°的2顆衛(wèi)星。

對于非永久鏈路的選取，則采用GDOP貢獻(xiàn)值法，將除永久鏈路之外的可視衛(wèi)星進(jìn)行GDOP貢獻(xiàn)值排序，選取GDOP貢獻(xiàn)值較大的衛(wèi)星進(jìn)行建鏈，以保證導(dǎo)航星座的測量精度，提高導(dǎo)航服務(wù)質(zhì)量。本文中非永久鏈路為5條[8]。

2 路由方案的設(shè)計(jì)

2.1 概述

路由生成方案的設(shè)計(jì)要解決的問題是：針對特定場景，從多條備選路徑中搜索出最佳路由方案。通常，為鏈路設(shè)置一個(gè)權(quán)值來反映該鏈路的數(shù)傳代價(jià)，進(jìn)而通過選擇權(quán)值最小的鏈路進(jìn)行最優(yōu)路由的生成。本文針對鏈路權(quán)值展開重點(diǎn)分析，而在路徑搜索上則沿用傳統(tǒng)的Dijkstra算法。

2.2 Dijkstra算法描述

Dijkstra算法的基本思想是：以路徑長度為對應(yīng)路徑的權(quán)值，通過對權(quán)值的迭代，得到從源節(jié)點(diǎn)到目的節(jié)點(diǎn)的最小權(quán)值對應(yīng)的最短路徑[9]。代碼如下：

Dijkstra算法：function Dijkstra(G, w, s)

輸入： 鄰接矩陣G，起始節(jié)點(diǎn)w，目的節(jié)點(diǎn)s

輸出： 最短路徑對應(yīng)的節(jié)點(diǎn)及權(quán)值

for (each vertex v in V[G]){

d[v]:= infinity //將各點(diǎn)的已知最短距離設(shè)成無窮大

previous[v]:= undefined

}

d[s]:= 0

//將s到s的最小距離設(shè)為0

S:= empty set

Q:= set of all vertices

while (Q is not an empty set){

u:= Extract_Min(Q)

S.append(u)

for (each edge outgoing from u as (u,v)){

if d[v] > d[u] + w(u,v)

d[v]:= d[u] + w(u,v)

previous[v]:= u

}

}

通過使用Dijkstra算法即可搜索出源節(jié)點(diǎn)到目的節(jié)點(diǎn)的最短路徑。在實(shí)際的衛(wèi)星導(dǎo)航系統(tǒng)中，地面控制管理中心即可通過該路徑對全網(wǎng)衛(wèi)星進(jìn)行遙測回收或境外星指令上注，具有實(shí)際應(yīng)用價(jià)值。

2.3 混合路由策略

傳統(tǒng)的路由生成方法對于數(shù)傳的影響因素考慮較為單一，如最短路徑算法以距離作為數(shù)傳代價(jià)進(jìn)行路徑搜索，算法可以搜索出源節(jié)點(diǎn)到目的節(jié)點(diǎn)距離最短的路徑，但不能保證時(shí)延最小，實(shí)際上衛(wèi)星從接收信息到發(fā)射信息期間的時(shí)延是不容忽視的。因此，傳統(tǒng)的路由算法難以滿足實(shí)際工程應(yīng)用的需求。

本文在減小端到端時(shí)延和均衡節(jié)點(diǎn)負(fù)載方面，對影響因素進(jìn)行較為全面的分析。其中，端到端時(shí)延主要包括等待時(shí)延(衛(wèi)星從接收到發(fā)送期間的等待時(shí)間)、鏈路傳輸速率所產(chǎn)生的時(shí)延以及節(jié)點(diǎn)空間距離產(chǎn)生的傳播時(shí)延。同時(shí)，為了充分高效地利用空間網(wǎng)絡(luò)資源，算法會首先計(jì)算各節(jié)點(diǎn)的負(fù)載，然后再進(jìn)行路由規(guī)劃，并盡可能使各節(jié)點(diǎn)的負(fù)載均衡化，來降低網(wǎng)絡(luò)出現(xiàn)擁塞或者丟包的可能性，從而保障系統(tǒng)能夠穩(wěn)定運(yùn)行。因此，本文考慮的數(shù)傳代價(jià)包括[10]：(1)等待時(shí)延；(2)鏈路速率；(3)節(jié)點(diǎn)距離；(4)節(jié)點(diǎn)負(fù)載。

2.4 鏈路權(quán)值的定義

節(jié)點(diǎn)距離、節(jié)點(diǎn)負(fù)載以及等待時(shí)延與數(shù)據(jù)傳輸代價(jià)成正比，而鏈路速率越大，數(shù)據(jù)傳輸所消耗的時(shí)間就越短，因此鏈路速率與數(shù)據(jù)傳輸代價(jià)成反比。結(jié)合以上因素，本文給出鏈路權(quán)值Q的定義如下[11]：

(5)

其中，ρ為鏈路長度，ρmax為當(dāng)前時(shí)刻所有能夠進(jìn)行通信的節(jié)點(diǎn)之間的距離的最大值；l為節(jié)點(diǎn)的負(fù)載，lmax為當(dāng)前所有節(jié)點(diǎn)負(fù)載的最大值；t_wait為下一跳節(jié)點(diǎn)的等待時(shí)延，t_waitmax為全網(wǎng)節(jié)點(diǎn)等待時(shí)延的最大值；r為節(jié)點(diǎn)之間的信息傳輸速率，考慮到真實(shí)系統(tǒng)中鏈路傳輸速率的可選性，本文中星間傳輸速率包含4組可選值，而星地傳輸速率包含2組可選值，rmax為當(dāng)前正在進(jìn)行通信的所有衛(wèi)星間的最大信息傳輸速率。將式(5)中的各因素進(jìn)行歸一化處理可以更客觀公平地反映鏈路代價(jià)。

3 仿真結(jié)果

3.1 仿真場景

本實(shí)驗(yàn)采用典型的遙測回傳及數(shù)據(jù)上注的業(yè)務(wù)場景，實(shí)現(xiàn)地面控制管理中心對24顆中軌道衛(wèi)星的實(shí)時(shí)監(jiān)測和控制。地面站不可直接觀察到的衛(wèi)星為境外星；反之，則為境內(nèi)衛(wèi)星。兩種衛(wèi)星與地面控制管理中心的數(shù)據(jù)傳輸都需要對地面站進(jìn)行規(guī)劃與調(diào)度，另外，對于境外衛(wèi)星而言，還要選擇合適的節(jié)點(diǎn)星進(jìn)行數(shù)據(jù)中轉(zhuǎn)。因此，要求路由算法能夠規(guī)劃出一條合理的路徑，使得衛(wèi)星與地面控制管理中心的通信時(shí)延應(yīng)盡可能小，同時(shí)要保證各節(jié)點(diǎn)的負(fù)載指數(shù)差在可接受范圍內(nèi)。本實(shí)驗(yàn)仿真時(shí)刻為2017年10月13日4:00:00am，假設(shè)每顆衛(wèi)星所產(chǎn)生的遙測數(shù)據(jù)量相等(GEO/IGSO除外)，圖例中衛(wèi)星編號1～24分別對應(yīng)MEO11～MEO38。

3.2 實(shí)驗(yàn)結(jié)果

實(shí)驗(yàn)首先將最短路徑路由算法和所提出的混合指標(biāo)約束的路由算法得出的結(jié)果進(jìn)行對比，來驗(yàn)證混合指標(biāo)約束方案能夠從當(dāng)前滿足建鏈條件的衛(wèi)星中選擇距離較近的衛(wèi)星來建鏈；然后，將負(fù)載均衡路由算法和混合指標(biāo)約束路由方案得出的結(jié)果進(jìn)行對比，驗(yàn)證混合路由方案能從滿足建鏈條件的衛(wèi)星中選擇當(dāng)前時(shí)刻較為空閑的衛(wèi)星進(jìn)行數(shù)據(jù)傳輸；最后，將3種算法得到的路由方案時(shí)延進(jìn)行對比，驗(yàn)證混合路由方案可以在綜合多種影響因素的情況下為衛(wèi)星計(jì)算出時(shí)延最小的路由，從而確保地面控制管理中心對衛(wèi)星監(jiān)測和遙控的實(shí)時(shí)性。下面對仿真結(jié)果進(jìn)行詳細(xì)介紹。

3.2.1混合路由方案路徑最短驗(yàn)證

將最短路徑路由算法和混合路由方案所規(guī)劃的路徑進(jìn)行進(jìn)一步整理，得到兩種算法的鏈路距離，結(jié)果如圖4所示。

圖4 源節(jié)點(diǎn)到目的節(jié)點(diǎn)路徑的距離

從圖4中可以看出，混合路由方案在大部分情況下得到的結(jié)果與最短路徑算法得到的結(jié)果接近，只有在個(gè)別處出現(xiàn)較大的差距，這是因?yàn)榛旌下酚煞桨高x擇了使得遙測回傳時(shí)延最小的路徑而沒有選取最短路徑所致，并且通過3.2.3節(jié)可以看出這并不影響混合路由方案選擇出時(shí)延最小的路徑。

3.2.2混合路由方案負(fù)載均衡驗(yàn)證

將負(fù)載均衡算法和混合路由方案下各節(jié)點(diǎn)的負(fù)載情況進(jìn)行了統(tǒng)計(jì)，統(tǒng)計(jì)結(jié)果如圖5所示。

圖5 衛(wèi)星負(fù)載

從圖5可以看出兩種算法各節(jié)點(diǎn)的負(fù)載均衡度相差不大，混合路由方案在衛(wèi)星MEO17、MEO26處負(fù)載稍大，這種情況是符合最優(yōu)化理論的。為此進(jìn)一步計(jì)算出了所有節(jié)點(diǎn)負(fù)載指數(shù)的方差以定量分析均衡度。負(fù)載均衡算法各節(jié)點(diǎn)負(fù)載指數(shù)方差為0.022，混合路由方案下各節(jié)點(diǎn)負(fù)載指數(shù)方差為0.029，由此可以得到結(jié)論：混合路由方案能夠從滿足建鏈條件的衛(wèi)星中選擇相對空閑的衛(wèi)星建立鏈接，以達(dá)到負(fù)載均衡的目的。值得指出的是，兩種算法負(fù)載指數(shù)在衛(wèi)星MEO14、MEO15、MEO21、MEO22和MEO23處均出現(xiàn)峰值，這是由于當(dāng)前時(shí)刻這些衛(wèi)星節(jié)點(diǎn)作為境內(nèi)接入衛(wèi)星所導(dǎo)致的。

3.2.3混合路由方案最小時(shí)延驗(yàn)證

對于路由算法，其所規(guī)劃的路徑具有較小的時(shí)延是至關(guān)重要的。為了進(jìn)一步驗(yàn)證混合路由方案能夠規(guī)劃出時(shí)延較小的路徑，將最短路徑和負(fù)載均衡路由算法同本文提出的混合路由方案所規(guī)劃的路徑時(shí)延進(jìn)行了統(tǒng)計(jì)分析，統(tǒng)計(jì)結(jié)果如圖6所示。

圖6 衛(wèi)星數(shù)據(jù)下傳到地面站時(shí)延

圖6是最短路徑算法、負(fù)載均衡算法和混合路由方案下， 24顆MEO將數(shù)據(jù)下傳到地面站的時(shí)延統(tǒng)計(jì)圖。從圖中可以看出，混合路由方案所規(guī)劃的路徑時(shí)延在大部分情況下都是小于其他兩種算法的。這是由于在一些特殊情況下，為了使各節(jié)點(diǎn)負(fù)載相對均衡，算法選擇了等待時(shí)延或者距離稍大的衛(wèi)星作為中轉(zhuǎn)衛(wèi)星所致，但該路徑時(shí)延仍在可接受范圍內(nèi)。同樣，在衛(wèi)星MEO14、MEO15、MEO21、MEO22和MEO23處，各方案所規(guī)劃路徑時(shí)延相等是該衛(wèi)星和地面站的可見性導(dǎo)致的。

4 結(jié)論

本文首先簡要分析了星間鏈路拓?fù)浣Y(jié)構(gòu)模型，引出衛(wèi)星導(dǎo)航系統(tǒng)的路由問題；然后，提出了一種綜合考慮等待時(shí)延、鏈路速率、節(jié)點(diǎn)負(fù)載和傳輸距離等多種影響因素的混合路由策略；最后，以端到端時(shí)延和節(jié)點(diǎn)負(fù)載為評價(jià)指標(biāo)，通過實(shí)驗(yàn)驗(yàn)證了本文所提出的混合路由策略大部分情況下能夠在保證網(wǎng)絡(luò)負(fù)載均衡的同時(shí)，搜索出端到端時(shí)延最小的路徑，合理有效地利用星間鏈路資源，為正在建設(shè)過程中的北斗全球衛(wèi)星導(dǎo)航系統(tǒng)提供理論依據(jù)和應(yīng)用基礎(chǔ)。

[1] LUBA O, BOYD L, GOWER A, et al. GPSIII system operations concepts[J]. Position Location and Navigation Symposium, 2004, 20(1):354-363.

[2] RAJAN J A. Highlights of GPSII-R autonomous navigation

[C]//Proceedings of the ION 58th Annual Meeting of the Institute of Navigation and CIGTF 21st Guidance Test Symposium. Albuquerque, NM:The Institute of Navigation, Inc, 2002:354-363.

[3] HOLMES J K, RAGHAVAN S. A summary of the new GPS IIR-M and IIF modernization signals[C]//Proceedings of the Vehicular Technology Conference (VTC 2004-fall). Los Angeles: IEEE, 2004:4116-4126.

[4] 劉小躍.空間信息網(wǎng)高性能路由協(xié)議研究[D]. 西安：西安電子科技大學(xué)，2012.

[5] 李振東，何善寶，劉崇華，等，一種導(dǎo)航星座星間鏈路拓?fù)湓O(shè)計(jì)方法[J].航天器工程，2011,20(3):32-37.

[6] 侯穎，米志超，于衛(wèi)波，等，星地一體化導(dǎo)航系統(tǒng)星間鏈路仿真分析[J].通信技術(shù)，2014, 47(2)：145-149.

[7] 陳建云，吳光耀，馮旭哲，等，衛(wèi)星星座星間通信鏈路拓?fù)浞治鯷J].儀器儀表學(xué)報(bào)，2014, 35(12)：101-105.

[8] 周淦，張方，喻瑤瑤，等，導(dǎo)航星座星間鏈路拓?fù)浼盎旌下酚煞桨竅C].北京：中國衛(wèi)星導(dǎo)航學(xué)術(shù)年會，2018.

[9] 張美玉，簡琤峰，侯向輝，等.Dijkstra算法在多約束農(nóng)產(chǎn)品配送最優(yōu)路徑中的研究應(yīng)用[J]. 浙江工業(yè)大學(xué)報(bào)，2012, 40(3)：321-325，330.

[10] 王冬霞，趙金賢，胡彩波，等.雙層衛(wèi)星網(wǎng)星間鏈路混合路由算法設(shè)計(jì) [J]. 導(dǎo)航定位學(xué)報(bào)，2016, 4(2):29-35.

[11] 孫娟.導(dǎo)航星座星間鏈路設(shè)計(jì)研究[D]. 南京：南京航空航天大學(xué)，2011.