基于位置的天地一體化網(wǎng)絡(luò)路由尋址機(jī)制研究

李賀武，劉李鑫，劉君，吳茜

（1.清華大學(xué)網(wǎng)絡(luò)科學(xué)與網(wǎng)絡(luò)空間研究院，北京 100084；2.北京信息科學(xué)與技術(shù)國家研究中心，北京 100084）

1 引言

衛(wèi)星網(wǎng)絡(luò)因其在覆蓋范圍和移動接入能力等方面與地面網(wǎng)絡(luò)具有極強(qiáng)的互補(bǔ)關(guān)系，受到各界的關(guān)注，近年來得到迅速發(fā)展，如 Iridium[1]、OneWeb[2]、Starlink[3]等。天地一體化網(wǎng)絡(luò)是以地面網(wǎng)絡(luò)為基礎(chǔ)、以衛(wèi)星網(wǎng)絡(luò)為延伸，覆蓋太空、空中、陸地、海洋等自然空間，為天基、空基、陸基、?；雀黝愑脩舻幕顒犹峁┬畔⒈Ｕ系幕A(chǔ)設(shè)施。天地一體化網(wǎng)絡(luò)不僅符合未來技術(shù)發(fā)展的趨勢，也是中國的重大戰(zhàn)略需求[4-5]。然而因衛(wèi)星高速移動所導(dǎo)致的衛(wèi)星網(wǎng)絡(luò)內(nèi)部及與地面網(wǎng)絡(luò)之間的連接關(guān)系不斷變化的特性一直是困擾衛(wèi)星網(wǎng)絡(luò)及天地一體化網(wǎng)絡(luò)路由機(jī)制設(shè)計(jì)的最重要難題之一，尋求一種不受頻繁切換影響的路由機(jī)制越來越重要。

早期的衛(wèi)星網(wǎng)絡(luò)主要通過“快照技術(shù)”[6-7]來實(shí)現(xiàn)星上的路由轉(zhuǎn)發(fā)，即基于虛擬拓?fù)涞募惺铰酚蓹C(jī)制。衛(wèi)星數(shù)量的激增及星座規(guī)模的迅速膨脹，使衛(wèi)星網(wǎng)絡(luò)內(nèi)及其與地面網(wǎng)絡(luò)間的連接關(guān)系變化愈發(fā)頻繁?；谔摂M拓?fù)涞目煺諜C(jī)制在鏈路連接關(guān)系更加高動態(tài)變化場景中，尋求靜態(tài)離散場景難度加大?；谔摂M拓?fù)淝蟹值玫降臅r間片數(shù)目正比于鏈路切換次數(shù)，這直接導(dǎo)致星上需要存儲和維護(hù)的路由表數(shù)目增長正比于鏈路切換次數(shù)的增長，對星上資源有限的衛(wèi)星網(wǎng)絡(luò)造成極大沖擊。與此同時，基于虛擬拓?fù)涞穆酚蓹C(jī)制在與地面路由機(jī)制融合時的難度較大。因?yàn)榍罢呤抢眯l(wèi)星標(biāo)識和星間連接關(guān)系生成路由信息，在與基于IP 路由的地面網(wǎng)絡(luò)融合時，需要兩種路由機(jī)制配合，且需要前者能根據(jù)當(dāng)前地面用戶連接情況及時地更新星上路由的存儲信息，這會產(chǎn)生相當(dāng)大的星上維護(hù)開銷，加劇星上資源壓力。

考慮衛(wèi)星網(wǎng)絡(luò)內(nèi)部的星間相對位置通常相對固定，一部分工作提出基于虛擬節(jié)點(diǎn)的分布式路由機(jī)制[8-10]?；谝阎男情g相對位置信息，根據(jù)星上存儲的預(yù)先計(jì)算生成的映射表選擇轉(zhuǎn)發(fā)接口，或者鄰居之間交換位置信息和移動方向信息，比較鄰居距目的地址絕對距離得到下一跳路由。這避免了基于虛擬拓?fù)涞募惺铰酚蓹C(jī)制存在的路由表存儲開銷巨大的問題。然而，現(xiàn)有相關(guān)路由算法假設(shè)落地衛(wèi)星標(biāo)識已知，由于衛(wèi)星高速運(yùn)動，衛(wèi)星與用戶之間切換頻繁，獲取落地衛(wèi)星標(biāo)識會產(chǎn)生大量的位置更新開銷。此外，由于衛(wèi)星位置具有時變性，部分解決方案需要鄰居間定期交換狀態(tài)信息。隨著衛(wèi)星星座規(guī)模的增大，鄰居間消息交換愈發(fā)頻繁，導(dǎo)致衛(wèi)星網(wǎng)絡(luò)中帶寬資源浪費(fèi)嚴(yán)重。

地面互聯(lián)網(wǎng)通過TCP/IP 實(shí)現(xiàn)了異構(gòu)網(wǎng)絡(luò)互聯(lián)且發(fā)展成熟，將地面基于IP 的分布式路由協(xié)議遷移應(yīng)用能充分發(fā)揮地面互聯(lián)網(wǎng)的優(yōu)勢，用較低的開銷實(shí)現(xiàn)一體化網(wǎng)絡(luò)建設(shè)。然而現(xiàn)有分布式IP 路由協(xié)議主要是針對地面互聯(lián)網(wǎng)設(shè)計(jì)，其拓?fù)浠痉€(wěn)定，這導(dǎo)致協(xié)議對一體化網(wǎng)絡(luò)鏈路連接關(guān)系高動態(tài)變化場景應(yīng)對不足，路由頻繁更新使協(xié)議可用性受到極大影響。為此，已有研究嘗試?yán)眯l(wèi)星周期運(yùn)行規(guī)律，引入預(yù)測信息，優(yōu)化一體化網(wǎng)絡(luò)路由機(jī)制設(shè)計(jì)，如OSPF+（open shortest path first）[11]、BGP+（border gateway protocol）[12]等。然而，衛(wèi)星星座規(guī)模的增大導(dǎo)致星上環(huán)境更加復(fù)雜，所需要的預(yù)測指標(biāo)增多，這對衛(wèi)星存儲能力和計(jì)算能力提出了更高要求，頻繁的消息交換也給衛(wèi)星能耗帶來更大挑戰(zhàn)。

本文提出一種基于位置的天地一體化網(wǎng)絡(luò)路由尋址機(jī)制（LA-ISTN,location based routing addressing mechanism of integrated satellite and terrestrial network），不同于上述提及的若干通過獲取鄰居信息計(jì)算下一跳的位置路由機(jī)制，LA-ISTN 不需要獲取鄰居衛(wèi)星的位置信息，僅需要從IP 地址中獲取目的地址的位置信息來計(jì)算其方位，由選擇算法計(jì)算得到的衛(wèi)星自身最優(yōu)的接口直接進(jìn)行數(shù)據(jù)分組轉(zhuǎn)發(fā)。LA-ISTN 結(jié)合傳統(tǒng)路由表查找機(jī)制的優(yōu)勢，提出星上臨時路由表的概念，將分布式計(jì)算結(jié)果存儲到路由表中，當(dāng)衛(wèi)星與目的地址相對位置發(fā)生改變時，更新臨時路由表。臨時路由表使LA-ISTN 對于連續(xù)數(shù)據(jù)傳輸支持度更高，極大地提升了機(jī)制性能。

2 相關(guān)工作

衛(wèi)星通信技術(shù)的發(fā)展使低軌衛(wèi)星星座內(nèi)通過組網(wǎng)路由實(shí)現(xiàn)遠(yuǎn)距離高帶寬傳輸成為可能。

早期典型的星間路由機(jī)制設(shè)計(jì)[6]是基于衛(wèi)星運(yùn)行規(guī)律預(yù)測虛擬拓?fù)洌瑢⑿l(wèi)星運(yùn)行周期切分為離散的時間片，地面集中計(jì)算并生成每個時間片的轉(zhuǎn)發(fā)表，星上存儲所有時間片內(nèi)轉(zhuǎn)發(fā)表，并定期進(jìn)行更新。文獻(xiàn)[13]在時間片切分的基礎(chǔ)上，將時延抖動等納入路由生成算法優(yōu)化目標(biāo)。文獻(xiàn)[14]提出滑動窗口機(jī)制，星上只存儲窗口大小時間內(nèi)路由表信息，衛(wèi)星過頂時，通過地面站上傳新的窗口大小時間內(nèi)路由表信息。這類方法路由表獲得基于地面集中預(yù)測衛(wèi)星運(yùn)行信息生成的先驗(yàn)知識，在實(shí)際運(yùn)行環(huán)境中，抵抗衛(wèi)星節(jié)點(diǎn)失效和鏈路故障的能力差。且隨著衛(wèi)星規(guī)模增大，切分衛(wèi)星運(yùn)行周期內(nèi)靜態(tài)拓?fù)淦蔚碾y度增加，時間片數(shù)量正比于鏈路切換次數(shù)，這使星上存儲開銷和維護(hù)開銷急增，星上面臨路由表“爆炸”問題，對網(wǎng)絡(luò)可用性造成極大影響。

文獻(xiàn)[8]考慮引入衛(wèi)星相對位置信息解決基于虛擬拓?fù)涞募惺铰酚蓹C(jī)制存儲開銷大的問題，利用同軌道高度內(nèi)衛(wèi)星相對位置進(jìn)行路由尋址，從而解決星上路由表“爆炸”問題。文獻(xiàn)[9-10]引入擁塞等指標(biāo)對路由機(jī)制進(jìn)一步優(yōu)化。文獻(xiàn)[15]中提出基于地理位置信息進(jìn)行路由的貪心算法，更靠近目的節(jié)點(diǎn)的鄰居節(jié)點(diǎn)作為下一跳。文獻(xiàn)[16-17]引入平面路由方案，對文獻(xiàn)[15]中可能出現(xiàn)的最后一跳不可達(dá)問題進(jìn)行優(yōu)化。由于衛(wèi)星位置時變，此類解決方案算法計(jì)算開銷大，且需要鄰居之間定期交換位置信息和移動方向信息，消息交換開銷大。此類方案假設(shè)衛(wèi)星可以獲取到落地衛(wèi)星信息，由于衛(wèi)星移動，目的用戶接入衛(wèi)星頻繁切換，落地衛(wèi)星的信息難以獲得，且隨著星座規(guī)模增大，切換更加普遍，尋址機(jī)制實(shí)際部署困難。

一種路由機(jī)制的設(shè)計(jì)思路是借鑒地面互聯(lián)網(wǎng)成熟的分布式IP 路由協(xié)議來實(shí)現(xiàn)星間組網(wǎng)路由。文獻(xiàn)[18]指出了衛(wèi)星網(wǎng)絡(luò)中IP 路由存在的挑戰(zhàn)：鏈路連接關(guān)系高動態(tài)變化；星上計(jì)算資源受限，能耗受限。這類解決方案嘗試?yán)眯l(wèi)星拓?fù)渚哂兄芷谛院涂深A(yù)測性的特點(diǎn)，典型思路是將預(yù)測信息引入OSPF（open shortest path first）協(xié)議，以避免不必要的路由收斂，加速必要的路由收斂[11]。此類優(yōu)化方案使協(xié)議在衛(wèi)星網(wǎng)絡(luò)部署時更適應(yīng)鏈路連接關(guān)系高動態(tài)變化環(huán)境，帶來了路由協(xié)議性能一定的提升。但是隨著衛(wèi)星規(guī)模增加，鏈路切換更加頻繁，需要的預(yù)測信息增多，路由頻繁更新也使網(wǎng)絡(luò)可用性受到極大影響。

本文提出的LA-ISTN 利用基于地理位置信息編址的IP 編址策略，解決基于虛擬節(jié)點(diǎn)的路由機(jī)制面臨的目的位置信息很難獲得的問題。每顆衛(wèi)星從IP 地址中獲取目的地址的位置信息并計(jì)算出相對方位，得出最優(yōu)的轉(zhuǎn)發(fā)接口進(jìn)行數(shù)據(jù)分組轉(zhuǎn)發(fā)，不需要鄰居間交換狀態(tài)信息，省去了消息交換開銷。LA-ISTN 利用傳統(tǒng)查表路由機(jī)制的優(yōu)勢，提出將路由計(jì)算結(jié)果存儲到臨時路由表中，當(dāng)衛(wèi)星與目的地址的相對位置發(fā)生改變時，更新路由表，增強(qiáng)對連續(xù)數(shù)據(jù)傳輸?shù)闹С侄?，提升機(jī)制性能。

3 LA-ISTN 路由尋址介紹

3.1 問題描述

低軌衛(wèi)星網(wǎng)絡(luò)因具有時延低、帶寬高、覆蓋范圍廣的特點(diǎn)，與地面互聯(lián)網(wǎng)有極強(qiáng)互補(bǔ)性，成為一體化網(wǎng)絡(luò)的研究熱點(diǎn)。不同于地面網(wǎng)絡(luò)相對固定的特點(diǎn)，低軌衛(wèi)星相對地面運(yùn)動速度快，星地之間鏈路頻繁切換，終端平均每10 min 即需要切換接入衛(wèi)星。傳統(tǒng)IP 邏輯編址機(jī)制中，改變接入衛(wèi)星會導(dǎo)致終端IP 地址改變，觸發(fā)綁定更新，頻繁的綁定更新會消耗大量星上通信資源。為了解決綁定更新頻繁的問題，文獻(xiàn)[19]提出終端IP 地址基于地理區(qū)塊編址，使綁定更新與切換無關(guān)，降低IP 地址更新的頻率，從而解決綁定更新頻繁的問題，但并未給出相應(yīng)的基于位置的星間路由方案。IP 生成規(guī)則的修改，需要給出相應(yīng)的高效星間路由方案，現(xiàn)有的路由機(jī)制在面對接入用戶量龐大的一體化網(wǎng)絡(luò)場景時，會因頻繁的路由更新導(dǎo)致網(wǎng)絡(luò)不可用。因此，本文基于節(jié)點(diǎn)位置信息和方位信息提出了LA-ISTN，即地理區(qū)塊編址場景下的星間路由策略。

假設(shè)衛(wèi)星網(wǎng)絡(luò)內(nèi)每顆低軌衛(wèi)星攜帶4 個接口[20]，分別與軌內(nèi)軌間的4 個鄰居建立星間鏈路?？紤]軌間建立星間激光鏈路的難度，假設(shè)其中2 個與同軌道內(nèi)的鄰居衛(wèi)星建立星間鏈路的接口為激光接口，且假設(shè)在衛(wèi)星運(yùn)行過程中，鏈路始終保持連接。其余2 個與相鄰軌道的鄰居衛(wèi)星建立星間鏈路的接口為微波接口，在運(yùn)行過程中，若衛(wèi)星進(jìn)入極區(qū)，與相鄰軌道鄰居衛(wèi)星建立的星間鏈路將斷開。此外，由于衛(wèi)星跟瞄系統(tǒng)的精度和速度的限制，本文假設(shè)2 個運(yùn)行方向不同的相鄰軌道的衛(wèi)星之間不建立星間鏈路，所提及的地面接入節(jié)點(diǎn)為地面固定的地面站或直接與衛(wèi)星通信的移動終端。

LA-ISTN 所涉及的概念和變量定義如下。

目的地址位置信息。基于地球表面分區(qū)編碼算法得到的區(qū)塊編碼信息，或目的地址一定精度的經(jīng)緯度信息，通過編址算法將目的地址位置信息嵌入IPv6 地址中。常見的地球表面分區(qū)編碼算法有Geohash[21]、Google S2 等。

衛(wèi)星位置信息。衛(wèi)星位置信息指當(dāng)前衛(wèi)星投影到地面所得的基于地球表面分區(qū)編碼算法得到的區(qū)塊編碼信息或一定精度的經(jīng)緯度位置信息。衛(wèi)星系統(tǒng)天然具有時空特性，易獲得其位置信息。

衛(wèi)星節(jié)點(diǎn)坐標(biāo)系。以當(dāng)前衛(wèi)星為原點(diǎn)，當(dāng)前衛(wèi)星所在軌道為y軸，正方向?yàn)樾l(wèi)星運(yùn)動方向；垂直所在軌道方向?yàn)閤軸，正方向?yàn)橛蚁颉?/p>

衛(wèi)星接口方向。衛(wèi)星接口方向即衛(wèi)星通過接口與鄰居衛(wèi)星節(jié)點(diǎn)建立的星間鏈路遠(yuǎn)離當(dāng)前衛(wèi)星的方向。衛(wèi)星節(jié)點(diǎn)S與C建立星間鏈路，射線S—C方向即為S與C建立星間鏈路接口的方向，如圖1 所示。

圖1 衛(wèi)星接口方向示意

記當(dāng)前接收到數(shù)據(jù)分組的衛(wèi)星為S，數(shù)據(jù)分組目的地址為D。若位置信息由基于地球表面分區(qū)編碼算法生成的字符串表示，則當(dāng)前衛(wèi)星位置信息為Sl，數(shù)據(jù)分組目的地址位置信息為Dl；若位置信息由一定精度的經(jīng)緯度信息表示，則當(dāng)前衛(wèi)星位置信息為（latc,lonc），數(shù)據(jù)分組的目的地址位置信息為（latd,lond）。dx表示在以當(dāng)前衛(wèi)星為原點(diǎn)建立的直角坐標(biāo)系中目的地址所處位置在x軸上的投影的長度，dy表示在y軸上投影的長度。星上接口方向與S—D連線所形成的夾角定義為接口的方向角，記為α。衛(wèi)星與n個鄰居節(jié)點(diǎn)建立星間鏈路所形成的n個接口方向角為α1,α2,…,α n（本文中n＜4），如圖1 所示α1和α2即為S的2 個接口方向角。

3.2 路由機(jī)制

3.2.1 LA-ISTN

不同于文獻(xiàn)[15]使用位置信息計(jì)算鄰居節(jié)點(diǎn)距離目的地址的絕對距離或絕對方向來選擇下一跳路由節(jié)點(diǎn)的方法，LA-ISTN 根據(jù)目的地址的位置信息計(jì)算其相對于當(dāng)前衛(wèi)星的方位，然后利用相對方位選擇當(dāng)前衛(wèi)星的最優(yōu)轉(zhuǎn)發(fā)接口進(jìn)行數(shù)據(jù)分組轉(zhuǎn)發(fā)。每顆衛(wèi)星獨(dú)立計(jì)算轉(zhuǎn)發(fā)接口，不需要鄰居間交換狀態(tài)信息。本文給出了LA-ISTN 選擇轉(zhuǎn)發(fā)接口的2 種實(shí)現(xiàn)方式——基于接口方向角比較的轉(zhuǎn)發(fā)接口選擇算法（IA-ISA,interface angle based on interface selection algorithm）和基于星間相對位置的轉(zhuǎn)發(fā)接口選擇算法（RP-ISA,relative position based on interface selection algorithm）。

IA-ISA 中定義的最優(yōu)轉(zhuǎn)發(fā)接口指當(dāng)前衛(wèi)星所形成的接口方向角中，最小的接口方向角對應(yīng)的接口，IA-ISA 的具體實(shí)現(xiàn)如算法1 所述。特別地，LA-ISTN不同接口選擇算法實(shí)現(xiàn)中待選擇的轉(zhuǎn)發(fā)接口不包括接收到當(dāng)前數(shù)據(jù)分組的接口，以避免數(shù)據(jù)分組從接收接口再轉(zhuǎn)發(fā)給前一跳衛(wèi)星節(jié)點(diǎn)形成路由環(huán)路。因此，算法1 中輸入的衛(wèi)星節(jié)點(diǎn)接口方向角中不包括收到的當(dāng)前數(shù)據(jù)分組的接口對應(yīng)的接口方向角。

算法1IA-ISA

輸入D,α1,α2,…,α n

輸出next_port

1) next_port=ip_lookup()//查詢臨時路由表，獲取轉(zhuǎn)發(fā)信息

2) if next_port//若查詢到對應(yīng)表項(xiàng)，則根據(jù)表項(xiàng)進(jìn)行轉(zhuǎn)發(fā)

3) next_port=sort_angle(α1,α2,…,α n)// 對輸入的接口方向角進(jìn)行排序，將最小接口方向角對應(yīng)的接口賦值給next_port，若最小接口方向角有多個，優(yōu)先選擇同軌內(nèi)鄰居建立鏈路的接口

forward(next_port);

4) route_item=generate_route(D,next_port);

add_route(route_item)//將本次路由計(jì)算結(jié)果加入臨時路由表

return;

算法1 首先查找臨時路由表，若查找成功，將數(shù)據(jù)分組從路由表中記錄的接口轉(zhuǎn)發(fā)給目的用戶；否則，選擇對應(yīng)最小接口方向角的轉(zhuǎn)發(fā)接口，將數(shù)據(jù)分組從該接口轉(zhuǎn)發(fā)給下一跳鄰居衛(wèi)星節(jié)點(diǎn)。

考慮某些低軌衛(wèi)星網(wǎng)絡(luò)建設(shè)規(guī)模大、單顆衛(wèi)星成本較低，因此存在單顆衛(wèi)星計(jì)算能力不足的缺陷。衛(wèi)星接口方向角的獲得和計(jì)算開銷對此類衛(wèi)星網(wǎng)絡(luò)來講壓力過大，因此，本文給出LA-ISTN 接口選擇的第二種實(shí)現(xiàn)方式RP-ISA。

RP-ISA 利用星間鄰居相對位置來選擇轉(zhuǎn)發(fā)接口，對當(dāng)前衛(wèi)星建立衛(wèi)星節(jié)點(diǎn)坐標(biāo)系，易知目的地址一定位于以當(dāng)前衛(wèi)星為原點(diǎn)所建立的衛(wèi)星節(jié)點(diǎn)坐標(biāo)系的坐標(biāo)軸或者4 個象限中。目的地址與衛(wèi)星的相對方位根據(jù)目的IP 地址中記錄的位置信息計(jì)算得到，以(dx,dy)的形式表示。RP-ISA 將復(fù)雜的接口選擇問題轉(zhuǎn)化為選擇軌內(nèi)星間鏈路或軌間星間鏈路轉(zhuǎn)發(fā)的問題?？紤]不同緯度軌間星間鏈路的長度有區(qū)別，在選擇最優(yōu)轉(zhuǎn)發(fā)接口時，若目的地址相對當(dāng)前衛(wèi)星處于較高緯度，優(yōu)先軌內(nèi)轉(zhuǎn)發(fā)；若目的地址相對當(dāng)前衛(wèi)星處于較低緯度，優(yōu)先軌間轉(zhuǎn)發(fā)，具體實(shí)現(xiàn)如算法2 所示。

算法2RP-ISA

輸入D,(latd,lond),(latc,lonc),dx,dy

輸出next_port

1) next_port=ip_lookup();//查詢臨時路由表，獲取轉(zhuǎn)發(fā)信息

2) if next_port:

forward(next_port);

return;

end if

3)//確定intra_port 和inter_port 對應(yīng)值，其中intra_port 表示本次選擇過程中軌內(nèi)鏈路對應(yīng)的接口，inter_port 表示本次選擇過程中軌間鏈路對應(yīng)的接口

//接口可用的條件是該接口當(dāng)前建立了星間鏈路且不是接收到數(shù)據(jù)分組的接口

//若dx＞0，則目的地址位于坐標(biāo)系中一、四象限，接口可用前提下選擇東向（x軸正方向）接口作為軌間接口

//若dx＜0，則目的地址位于坐標(biāo)系中二、三象限，接口可用前提下選擇西向（x軸負(fù)方向）接口作為軌間接口

4) if(|latc| ＜ |latd|)

//當(dāng)前衛(wèi)星所處緯度低于目的地址所處緯度，越高緯，軌間鏈路越短，故此刻優(yōu)先選擇軌內(nèi)接口轉(zhuǎn)發(fā)，靠近高緯時，判斷是否需要進(jìn)行軌間轉(zhuǎn)發(fā)

//Lv表示同軌內(nèi)兩顆衛(wèi)星的平均距離，若y軸方向上距離小于，根據(jù)最強(qiáng)信號強(qiáng)度連接原則，目的地址可能位于當(dāng)前衛(wèi)星同緯度衛(wèi)星覆蓋區(qū)域，此時選擇軌間轉(zhuǎn)發(fā)

//Lh表示相鄰軌道內(nèi)兩顆衛(wèi)星的平均距離，若x軸方向上距離小于，推測目的地址可能位于當(dāng)前衛(wèi)星同經(jīng)度衛(wèi)星覆蓋區(qū)域，此時選擇軌內(nèi)轉(zhuǎn)發(fā)

3.2.2 臨時路由表

臨時路由表指星上存儲臨時接入當(dāng)前衛(wèi)星的終端路由信息和LA-ISTN 生成的路由表項(xiàng)。當(dāng)衛(wèi)星與目的地址的相對位置發(fā)生改變時，清除當(dāng)前路由表項(xiàng)信息，以保證臨時路由表中記錄始終是有效的。當(dāng)前衛(wèi)星相對于地球表面的橫向移動速度為vx，相對于地球表面的縱向移動速度為vy，臨時路由表項(xiàng)有效時長如式(1)和式(2)所示。

取tx和ty中較小的一個作為當(dāng)前路由表項(xiàng)的有效時長，例如tx相對較小,則當(dāng)經(jīng)過tx時間后，清除當(dāng)前路由表項(xiàng)。特別地，由于采用地理位置信息編址的方法，臨時路由表中會出現(xiàn)依據(jù)地理區(qū)塊聚類的現(xiàn)象。位置信息的精度也影響著上述有效時長的計(jì)算，本質(zhì)上算法獲取的位置信息是一定精度大小的區(qū)塊信息。因此，為了進(jìn)一步降低星上計(jì)算開銷和路由表維護(hù)開銷，本文對臨時路由表的更新做出進(jìn)一步優(yōu)化，即當(dāng)衛(wèi)星投影到地面所在分區(qū)發(fā)生變化時，清空當(dāng)前臨時路由表，根據(jù)運(yùn)行情況重新生成臨時路由表。

3.3 機(jī)理分析

3.3.1 最后一跳尋址可達(dá)性分析

分布式位置路由算法存在可達(dá)性疑問的位置在于路由的最后一跳，傳統(tǒng)基于絕對距離的路由算法存在最后一跳不可達(dá)問題[15]；LA-ISTN 同樣是基于位置的分布式路由算法，衛(wèi)星覆蓋區(qū)域重疊導(dǎo)致用戶節(jié)點(diǎn)位于當(dāng)前衛(wèi)星覆蓋范圍內(nèi)但并未接入當(dāng)前衛(wèi)星的情況發(fā)生。根據(jù)LA-ISTN 描述，此種情況下，尋址機(jī)制繼續(xù)選取靠近目的位置的接口方向進(jìn)行轉(zhuǎn)發(fā)。

本文給出最復(fù)雜重疊情況下的證明，如圖2 所示，即目的地址D位于衛(wèi)星A、C、E、S重疊覆蓋區(qū)域，均有可能連接到某顆衛(wèi)星時的情況，這種情況下算法的路由可達(dá)性證明如下。

圖2 最后一跳可達(dá)性分析示意

證明若D接入S，S查找星上臨時路由表獲得下一跳路由，將數(shù)據(jù)分組數(shù)據(jù)分組轉(zhuǎn)發(fā)給D，此時路由可達(dá)。若D未接入S，S查找臨時路由表失敗，依據(jù)接口方向轉(zhuǎn)發(fā)到A或者C。

若D接入A，算法選擇的轉(zhuǎn)發(fā)接口是與A相連的接口，則路由可達(dá)；若算法選擇的轉(zhuǎn)發(fā)接口是與C相連的接口，數(shù)據(jù)分組轉(zhuǎn)發(fā)到C，C查找臨時路由表失敗，依據(jù)接口方向轉(zhuǎn)發(fā)到E。同樣地，E查找臨時路由表失敗，將數(shù)據(jù)分組轉(zhuǎn)發(fā)到A，路由可達(dá)。

同理，D接入C的情況路由可達(dá)。

若D接入E，算法選擇的接口是A或者C，根據(jù)算法，數(shù)據(jù)分組轉(zhuǎn)發(fā)到E，路由可達(dá)。

特別地，考慮在數(shù)據(jù)分組轉(zhuǎn)發(fā)過程中，D接入的衛(wèi)星發(fā)生變化的情況，LA-ISTN 將數(shù)據(jù)分組沿著形成的四邊形轉(zhuǎn)發(fā)，最終一定路由可達(dá)。由于不會出現(xiàn)用戶來回在2 顆衛(wèi)星之間切換的情況，其路由在靠近目的地址的位置最多繞一圈便可完成數(shù)據(jù)分組轉(zhuǎn)發(fā)，故不會產(chǎn)生路由環(huán)路的問題。

3.3.2 軌間鏈路斷開及拼縫位置尋址可達(dá)性分析

3.1 節(jié)給出了LA-ISTN 所對應(yīng)的低軌衛(wèi)星網(wǎng)絡(luò)場景的具體介紹。除拼縫位置軌間不建立星間鏈路，其余位置軌間鏈路未按照地面預(yù)測連接關(guān)系正常建立或突然斷開時，給出尋址可達(dá)性證明如下。

證明 首先給出只涉及一條軌間鏈路斷開（即單條鏈路斷開）情況下的可達(dá)性分析。如圖3(a)所示，當(dāng)S與右側(cè)鄰居的軌間鏈路斷開時，算法會選擇先轉(zhuǎn)發(fā)至B，而后轉(zhuǎn)發(fā)至A，最后一跳可達(dá)性證明同3.3.1 節(jié)。

圖3 軌間鏈路斷開情況下可達(dá)性分析示意

其次，當(dāng)涉及多條軌間鏈路斷開時，如圖3(b)所示，S、B、A等衛(wèi)星節(jié)點(diǎn)均與右側(cè)軌道衛(wèi)星節(jié)點(diǎn)星間鏈路斷開。根據(jù)算法描述可知，在此情況下，數(shù)據(jù)分組會沿著當(dāng)前軌道逐跳轉(zhuǎn)發(fā)，直到轉(zhuǎn)發(fā)至某一衛(wèi)星節(jié)點(diǎn)，其靠近目的位置的軌間鏈路正常連接。當(dāng)前衛(wèi)星將數(shù)據(jù)分組轉(zhuǎn)發(fā)至相鄰軌道衛(wèi)星節(jié)點(diǎn)E，在相鄰軌道內(nèi)繼續(xù)轉(zhuǎn)發(fā)，直至到達(dá)D。

最后，給出當(dāng)2 條相鄰軌道之間的星間鏈路全部斷開，即拼縫位置的尋址可達(dá)性分析。如圖4 所示，拼縫位置相鄰軌道間不建立星間鏈路。根據(jù)算法描述，數(shù)據(jù)分組轉(zhuǎn)發(fā)至拼縫位置的某條軌道時，會沿著該軌道逐跳轉(zhuǎn)發(fā)。當(dāng)越過極點(diǎn)N時，數(shù)據(jù)分組會繼續(xù)沿更靠近D的方向轉(zhuǎn)發(fā)，不經(jīng)過未建立軌間鏈路的拼縫位置，后續(xù)可達(dá)性分析同前文所述，最終實(shí)現(xiàn)路由可達(dá)。

圖4 拼縫位置可達(dá)性分析示意

3.3.3 開銷分析

本節(jié)從鄰居信息交換開銷、星上存儲開銷、算法時間復(fù)雜度三方面對算法開銷進(jìn)行分析。

1) 鄰居信息交換開銷。LA-ISTN 需要的衛(wèi)星接口方向信息和位置信息通過本地讀取衛(wèi)星上關(guān)于天線角度的狀態(tài)信息和位置信息來獲得，并不需要交換鄰居信息。與地面基于IP 的分布式路由機(jī)制及傳統(tǒng)位置路由算法相比，LA-ISTN 不需要鄰居間“hello”消息傳遞和位置信息傳遞，鄰居間信息交換開銷為零。

2) 星上存儲開銷。LA-ISTN 僅存儲包含當(dāng)前接入衛(wèi)星用戶的路由信息和在一定時期內(nèi)的算法計(jì)算結(jié)果，且IP 地址基于地理區(qū)塊信息生成，算法計(jì)算得出的路由表項(xiàng)可聚類，進(jìn)一步減少星上路由表存儲開銷。與快照機(jī)制相比，存儲開銷的降低程度與鏈路切換次數(shù)成正比。

3) 算法時間復(fù)雜度。IA-ISA 的算法復(fù)雜度由算法1 中的步驟1)進(jìn)行路由表查找、步驟3)接口方向角排序和步驟4)添加表項(xiàng)三部分組成。星上路由表規(guī)模記為M，則查詢運(yùn)行時間為O(M)。由3.1 節(jié)描述可知，算法輸入接口方向角個數(shù)至多為除了接收到數(shù)據(jù)分組的接口之外的所有接口數(shù)，即輸入規(guī)模n≤3，故算法1 的步驟3)運(yùn)行時間為常數(shù)級。步驟4)添加表項(xiàng)操作運(yùn)行時間為O(1)。故IA-ISA 的時間復(fù)雜度為O(M)。

RP-ISA 時間復(fù)雜度由算法2 中的步驟1)路由表查找、步驟3)軌內(nèi)軌間轉(zhuǎn)發(fā)接口確定、步驟4)部分接口選擇和步驟5)添加表項(xiàng)四部分組成。查詢步運(yùn)行時間與IA-ISA 相同，為O(M)。由算法2 描述可知，軌內(nèi)軌間轉(zhuǎn)發(fā)接口確定各需要進(jìn)行2 次比較，接口選擇需要進(jìn)行2 次比較，總比較次數(shù)為6 次，故步驟3)和步驟4)的運(yùn)行時間為常數(shù)級。步驟5)添加表項(xiàng)操作運(yùn)行時間為O(1)。故RP-ISA 的時間復(fù)雜度為O(M)。

綜上可知，LA-ISTN 運(yùn)行的計(jì)算開銷主要來源于路由表查找開銷。

3.3.4 性能分析

本節(jié)從路徑最優(yōu)性、抗毀性和對于連續(xù)數(shù)據(jù)傳輸支持的角度對算法進(jìn)行分析。

1) 路徑最優(yōu)性。分布式 IP 路由協(xié)議通過Dijkstra 算法計(jì)算生成最短路徑。LA-ISTN 逐跳計(jì)算下一跳路由，在鄰近目的地址時可能會出現(xiàn)多跳尋址的情況，使算法獲得的路徑不是最短路徑。根據(jù)最后一跳尋址可達(dá)性分析可知，從路徑跳數(shù)的角度比較，記最短跳數(shù)為n，則LA-ISTN 所得路徑跳數(shù)至多為n+2。從路徑傳輸時延的角度比較，LA-ISTN 第二種實(shí)現(xiàn)方式（RP-ISA）將緯度越高、橫向鏈路距離越短的特性納入考慮，記最短路徑傳輸時延為T，則LA-ISTN 所得路徑的傳輸時延最大值為T+2L，其中，L表示單條縱向或橫向星間鏈路的最大傳輸時延。

2) 抗毀性。LA-ISTN 僅考慮當(dāng)前有效的接口，不依賴預(yù)測的鏈路連接關(guān)系，故路由選擇靈活性和抗毀性強(qiáng)。

3) 對于連續(xù)數(shù)據(jù)傳輸支持。LA-ISTN 提出臨時路由表的概念，利用傳統(tǒng)路由查表機(jī)制的優(yōu)勢，連續(xù)數(shù)據(jù)流只需計(jì)算一次，后續(xù)路由查找臨時路由表獲得，避免單個數(shù)據(jù)分組計(jì)算帶來的額外開銷，對連續(xù)數(shù)據(jù)傳輸支持度高。

4 實(shí)驗(yàn)驗(yàn)證

本文使用STK（Systems Tool Kit）衛(wèi)星工具包[22]和Mininet 網(wǎng)絡(luò)仿真軟件[23]搭建了一體化網(wǎng)絡(luò)仿真環(huán)境。低軌衛(wèi)星網(wǎng)絡(luò)由于距地面距離近、時延低成為了衛(wèi)星網(wǎng)絡(luò)發(fā)展的趨勢。低軌衛(wèi)星網(wǎng)絡(luò)的拓?fù)渥兓铑l繁，路由機(jī)制設(shè)計(jì)所面臨的形勢相較其他軌道高度衛(wèi)星來講更嚴(yán)峻，因此本文仿真的一體化網(wǎng)絡(luò)場景中衛(wèi)星網(wǎng)絡(luò)部分為低軌衛(wèi)星網(wǎng)絡(luò)。由于銥星系統(tǒng)經(jīng)過多年的發(fā)展，其星座結(jié)構(gòu)最具有代表性，故本文的仿真場景基于銥星系統(tǒng)的星座結(jié)構(gòu)來模擬低軌衛(wèi)星網(wǎng)絡(luò)，增加衛(wèi)星節(jié)點(diǎn)數(shù)來模擬多個場景。低軌衛(wèi)星網(wǎng)絡(luò)參數(shù)如表1 所示。地面節(jié)點(diǎn)選取了15 個地面站進(jìn)行地面站間組網(wǎng)，在全球范圍內(nèi)選取了25 個用戶節(jié)點(diǎn)，共40個地面節(jié)點(diǎn)。

本文通過將真實(shí)的衛(wèi)星軌道運(yùn)行參數(shù)和地面節(jié)點(diǎn)位置信息輸入STK 衛(wèi)星工具包，模擬了網(wǎng)絡(luò)在一個衛(wèi)星運(yùn)動周期（100 min）內(nèi)的拓?fù)渥儞Q情況并選取了最典型的快照機(jī)制[6]和地面應(yīng)用最廣泛的分布式路由協(xié)議OSPF[22]與LA-ISTN 進(jìn)行對比。開銷測試通過在Mininet 網(wǎng)絡(luò)仿真軟件中搭建上述不同規(guī)模的網(wǎng)絡(luò)，使用Quagga 路由軟件[24]部署OPSF協(xié)議來進(jìn)行。從路由表存儲開銷、路由更新開銷、網(wǎng)絡(luò)可用性及路徑傳輸時延4 個方面對3 種機(jī)制進(jìn)行對比分析。

表1 低軌衛(wèi)星網(wǎng)絡(luò)參數(shù)

4.1 路由表存儲開銷

記一次衛(wèi)星運(yùn)行周期內(nèi)，單顆衛(wèi)星上采用的基于虛擬拓?fù)涞目煺諜C(jī)制[6]攜帶的路由表規(guī)模為CVT，OSPF 協(xié)議存儲的路由表規(guī)模為COSPF，LA-ISTN 存儲的臨時路由表規(guī)模為CLA-ISTN，切分的靜態(tài)拓?fù)鋾r間片數(shù)為R。根據(jù)3 種路由機(jī)制的設(shè)計(jì)可知，快照機(jī)制需要攜帶所有時刻的路由表，星上定期更新當(dāng)前時刻生效路由表，OSPF協(xié)議僅存儲當(dāng)前時刻的路由表，故存在如式(3)所示關(guān)系。

根據(jù)3.2.2 節(jié)所述臨時路由表的定義可知，LA-ISTN 中衛(wèi)星僅需要存儲當(dāng)前時刻衛(wèi)星的接入終端地址項(xiàng)及算法計(jì)算出的網(wǎng)絡(luò)部分路由信息。與存儲當(dāng)前時刻全網(wǎng)路由信息的OSPF 相比，可得式(4)所示不等式。

整理可得式(5)所示關(guān)系。

隨著衛(wèi)星星座規(guī)模增長，鏈路切換更加頻繁，使靜態(tài)時間片切分難度加大，導(dǎo)致R不斷增大。由式(5)可知，快照路由機(jī)制面臨著嚴(yán)峻的路由表存儲開銷急增問題和復(fù)雜的維護(hù)問題，其存儲規(guī)模是LA-ISTN 存儲規(guī)模的R倍。相比快照機(jī)制，LA-ISTN更適合大規(guī)模衛(wèi)星網(wǎng)絡(luò)，雖然OSPF 協(xié)議的路由表存儲開銷與LA-ISTN 基本一致，但其路由更新頻繁，使資源有限的衛(wèi)星難以承受。

4.2 路由更新開銷

路由更新開銷定義為由于路由更新所致的更新數(shù)據(jù)交換開銷?？煺諜C(jī)制是基于虛擬拓?fù)漕A(yù)先計(jì)算出每一時間片的路由信息，隨時間片更新當(dāng)前生效路由表，不需要發(fā)送更新數(shù)據(jù)進(jìn)行路由表更新，因此其路由更新開銷為0。

LA-ISTN 中路由表更新發(fā)生在單顆衛(wèi)星切換分區(qū)時衛(wèi)星本地更新路由表，不需要鄰居間路由信息交換和其他通信，因此其路由更新開銷為0。

OSPF 協(xié)議中使用“hello”消息來監(jiān)聽鏈路連接狀態(tài)，鏈路狀態(tài)變化會觸發(fā)路由表更新。由于OSPF 協(xié)議需要得知全網(wǎng)連接信息以計(jì)算最短路徑，因此本地路由表更新會導(dǎo)致鄰居間傳遞LSA update 數(shù)據(jù)分組，交換各自路由表，因此OSPF 協(xié)議存在更新數(shù)據(jù)交換開銷。實(shí)驗(yàn)得到該協(xié)議在不同網(wǎng)絡(luò)規(guī)模下一個衛(wèi)星周期內(nèi)的路由更新引起的數(shù)據(jù)交換總開銷，如圖5 所示。由圖5 可以看出，OSPF協(xié)議因路由更新引起的數(shù)據(jù)交換開銷隨著網(wǎng)絡(luò)節(jié)點(diǎn)規(guī)模的增長近乎呈指數(shù)級增長。

圖5 OSPF 協(xié)議路由更新數(shù)據(jù)交換總開銷變化

綜上分析可知，LA-ISTN 無路由更新開銷，可以極大地減少星上帶寬資源消耗，提升網(wǎng)絡(luò)整體性能。

4.3 網(wǎng)絡(luò)可用性

網(wǎng)絡(luò)可用性定義為當(dāng)前時刻路由表能準(zhǔn)確地反映當(dāng)前時刻網(wǎng)絡(luò)拓?fù)錉顩r的時長占比?？煺諜C(jī)制下衛(wèi)星網(wǎng)絡(luò)理論上始終可用，但在實(shí)際運(yùn)行過程中衛(wèi)星具有一定的隨機(jī)性，不能保證其鏈路連接狀態(tài)與地面預(yù)測結(jié)果時刻保持一致。倘若發(fā)生鏈路建立失敗或鏈路意外斷開等情況，網(wǎng)絡(luò)實(shí)際拓?fù)鋵⑴c預(yù)測信息不一致，其網(wǎng)絡(luò)可用性將受到毀滅性打擊。

根據(jù)3.3.4 節(jié)抗毀性分析可知，LA-ISTN 基本不受鏈路預(yù)測的影響，星間鏈路建立失敗僅會導(dǎo)致當(dāng)前可選擇接口減少，可能會引起星間轉(zhuǎn)發(fā)跳數(shù)的增加，但能保證數(shù)據(jù)分組可達(dá)。因此意外情況對LA-ISTN 下的網(wǎng)絡(luò)可用性無影響，網(wǎng)絡(luò)始終可用。

分布式IP 路由協(xié)議遇到故障會引起全網(wǎng)路由更新，路由長時間處于收斂狀態(tài)，收斂過程中，網(wǎng)絡(luò)可用性受到極大影響。OSPF 協(xié)議的網(wǎng)絡(luò)可用性測試是在Mininet 環(huán)境中使用Quagga 路由軟件部署，得到了不同網(wǎng)絡(luò)節(jié)點(diǎn)規(guī)模下一個衛(wèi)星運(yùn)行周期內(nèi)的OSPF 協(xié)議的運(yùn)行情況，計(jì)算得到其網(wǎng)絡(luò)可用時長占比，如表2 所示。

表2 不同網(wǎng)絡(luò)節(jié)點(diǎn)規(guī)模仿真發(fā)生路由更新次數(shù)及網(wǎng)絡(luò)可用時長占比

由表2 可以看到，隨著網(wǎng)絡(luò)規(guī)模的增長，路由更新次數(shù)增長對OSPF 協(xié)議可用性的影響較大，當(dāng)網(wǎng)絡(luò)規(guī)模為178 時，可用時長占比已不足7%。綜上，相較快照機(jī)制和OSPF 協(xié)議，LA-ISTN 在網(wǎng)絡(luò)可用性方面占據(jù)明顯優(yōu)勢。

4.4 路徑傳輸時延

本文選擇分別位于北京和開羅的2 個地面接入節(jié)點(diǎn)，在不同的網(wǎng)絡(luò)規(guī)模下，測量并比較了IA-ISA、RP-ISA 和最短路徑3 種路由選擇算法計(jì)算得到的路徑傳輸時延，結(jié)果如表3 所示。其中，最短路徑算法是快照機(jī)制和OSPF 協(xié)議的路由選擇算法，IA-ISA 和RP-ISA 是LA-ISTN 機(jī)制下2 種不同的路由選擇算法。

由表3 可以看出，IA-ISA 在不同網(wǎng)絡(luò)規(guī)模下的路徑傳輸時延與最短路徑傳輸時延相同，即為最優(yōu)傳輸路徑。當(dāng)RP-ISA 的節(jié)點(diǎn)規(guī)模分別為130、154、178 時，路徑傳輸時延相比最短路徑有一定延遲，平均差值為7.792 2 ms，與3.3.4 節(jié)性能分析的結(jié)果相符，差值在理論分析范圍內(nèi)。

表3 3 種算法路徑傳輸時延比較

5 結(jié)束語

本文提出一種基于位置的天地一體化網(wǎng)絡(luò)路由尋址機(jī)制——LA-ISTN，基于用戶IP 地址根據(jù)其地理位置信息生成的編址方式，在星間路由時，利用IP 地址中的位置信息計(jì)算路由方位，根據(jù)路由方位選擇最優(yōu)的轉(zhuǎn)發(fā)接口進(jìn)行轉(zhuǎn)發(fā)。實(shí)驗(yàn)結(jié)果表明，相較快照協(xié)議和OSPF 路由協(xié)議，LA-ISTN 星上路由表規(guī)模僅為前者的（R為快照機(jī)制攜帶的路由表的數(shù)目）。LA-ISTN 路由更新引起的數(shù)據(jù)分組交換開銷和鄰居通信開銷為0，且路由選擇不依賴于預(yù)測的鏈路連接關(guān)系，穩(wěn)健性強(qiáng)，可保證網(wǎng)絡(luò)時刻可用。