基于局部隊(duì)列的導(dǎo)航衛(wèi)星網(wǎng)絡(luò)路由算法

燕洪成，張慶君，孫 勇

(中國空間技術(shù)研究院總體部，北京100094)

0 引言

衛(wèi)星導(dǎo)航系統(tǒng)可以利用星間鏈路的星間測(cè)距功能實(shí)現(xiàn)自主導(dǎo)航;同時(shí)，也可以利用星間鏈路的星間通信功能實(shí)現(xiàn)全球組網(wǎng)，從而提高系統(tǒng)的整體性能［1－3］。由于導(dǎo)航衛(wèi)星平臺(tái)和指向性星間鏈路(Inter-Satellite Link，ISL)天線的約束，導(dǎo)航衛(wèi)星所能攜帶的天線數(shù)量有限(比如僅能攜帶一條)，導(dǎo)航衛(wèi)星網(wǎng)絡(luò)中的ISL將呈現(xiàn)半雙工、大時(shí)延、鏈路間斷可用的特點(diǎn)。同時(shí)，由于地球自轉(zhuǎn)和導(dǎo)航星座運(yùn)行的影響，導(dǎo)航衛(wèi)星與地面站之間的星地鏈路(Ground-Satellite Link，GSL)也呈現(xiàn)周期性的連接與中斷特點(diǎn)。ISL和GSL的這種鏈路間斷可用特點(diǎn)使導(dǎo)航衛(wèi)星網(wǎng)絡(luò)任意兩個(gè)網(wǎng)絡(luò)節(jié)點(diǎn)之間并不一定時(shí)刻存在端到端路徑，使其形成一個(gè)典型的延遲/中斷容忍網(wǎng) 絡(luò)(Delay/Disruption Tolerant Network，DTN)［4－6］。這對(duì)導(dǎo)航衛(wèi)星網(wǎng)絡(luò)的數(shù)據(jù)傳輸問題，特別是路由問題帶來了新的挑戰(zhàn)［7］。

圖1為一個(gè)典型導(dǎo)航衛(wèi)星網(wǎng)絡(luò)不同時(shí)刻的拓?fù)涫疽鈭D，時(shí)間間隔固定為Δt，稱為一個(gè)時(shí)隙。假設(shè)有6顆導(dǎo)航衛(wèi)星(圓形)和1個(gè)地面站(正方形)，兩顆導(dǎo)航衛(wèi)星之間用兩個(gè)單向箭頭連接說明在該時(shí)隙內(nèi)建立了半雙工ISL，導(dǎo)航衛(wèi)星和地面站之間用雙向箭頭連接說明在該時(shí)隙內(nèi)建立了全雙工GSL。假定每顆導(dǎo)航衛(wèi)星均配置1副ISL天線和1副GSL天線，1顆導(dǎo)航衛(wèi)星在1個(gè)時(shí)隙內(nèi)僅能選擇與另外1顆可見衛(wèi)星建立ISL，并以一定策略與地面站建立GSL。從圖1可以看出，由于ISL和GSL間斷連接，導(dǎo)航衛(wèi)星網(wǎng)絡(luò)中任意兩個(gè)節(jié)點(diǎn)間并不一定時(shí)刻存在端到端路徑，從而形成一個(gè)非全連通的網(wǎng)絡(luò)拓?fù)?。比如衛(wèi)星4與地面站G1在任何時(shí)隙均不存在端到端路徑，這使Dijkstra算法［8］在任何一個(gè)時(shí)隙均不能計(jì)算出可行路徑。但衛(wèi)星4可以在時(shí)隙［0，Δt)將消息發(fā)送給衛(wèi)星3，衛(wèi)星3暫存消息，并在時(shí)隙［2Δt，3Δt)轉(zhuǎn)發(fā)給地面站G1，最終完成消息的投遞。導(dǎo)航衛(wèi)星網(wǎng)絡(luò)中的路由問題不僅需要考慮某一時(shí)刻的靜態(tài)拓?fù)?，同時(shí)需要考慮網(wǎng)絡(luò)拓?fù)涞臅r(shí)間演化特性，通過綜合考慮不同時(shí)刻的網(wǎng)絡(luò)拓?fù)渫瓿陕酚捎?jì)算。

圖1 導(dǎo)航衛(wèi)星網(wǎng)絡(luò)在不同時(shí)刻的網(wǎng)絡(luò)拓?fù)涫疽鈭DFig．1 Network topology of navigation satellite network in different time slots

導(dǎo)航衛(wèi)星網(wǎng)絡(luò)的網(wǎng)絡(luò)拓?fù)溆蒊SL和GSL的鏈路調(diào)度決定，ISL和GSL的鏈路調(diào)度一般根據(jù)一定策略提前生成，并分發(fā)到每個(gè)網(wǎng)絡(luò)節(jié)點(diǎn);因此，導(dǎo)航衛(wèi)星網(wǎng)絡(luò)的路由問題可以看作是確定鏈路調(diào)度的DTN路由問題。

由于傳統(tǒng)的移動(dòng)通信衛(wèi)星網(wǎng)絡(luò)路由算法［9－10］均假定網(wǎng)絡(luò)時(shí)刻存在端到端路徑，因此并不適用于導(dǎo)航衛(wèi)星網(wǎng)絡(luò)。學(xué)術(shù)界針對(duì)DTN路由問題的研究主要集中在機(jī)會(huì)網(wǎng)絡(luò)［11－12］，確定鏈路調(diào)度的DTN路由算法相對(duì)較少。目前，學(xué)術(shù)界針對(duì)確定鏈路調(diào)度的DTN路由問題提出了演化圖模型［7，13］、空時(shí)路由算法［14］、接觸圖路由(Contact Graph Routing，CGR)［15］、時(shí)變圖模型［16］等，但這些路由算法均只考慮網(wǎng)絡(luò)的鏈路調(diào)度，而未考慮網(wǎng)絡(luò)的排隊(duì)延時(shí)，因此，其性能有限。由于導(dǎo)航衛(wèi)星網(wǎng)絡(luò)鏈路通信機(jī)會(huì)有限，排隊(duì)延時(shí)可能使消息錯(cuò)過當(dāng)前可用通信機(jī)會(huì)，從而增大端到端延時(shí)，并使消息長時(shí)間占用網(wǎng)絡(luò)資源，降低消息投遞成功率。

Jain等［17］提出了基于本地隊(duì)列的最早投遞(Earliest Delivery with Local Queue，EDLQ)和基于全網(wǎng)隊(duì)列的最早投遞(Earliest Delivery with All Queues，EDAQ)路由算法;Bezirgiannidis等［18－19］針對(duì)CGR提出了一種基于最早傳輸機(jī)會(huì)(Earliest Transmission Opportunity，ETO)的路由算法(CGRETO)，并考慮全網(wǎng)隊(duì)列信息。但上述路由算法存在以下問題:首先，僅考慮本地節(jié)點(diǎn)隊(duì)列信息不能夠使消息避開擁塞的鄰居節(jié)點(diǎn);其次，獲取全網(wǎng)的隊(duì)列信息會(huì)帶來大量的協(xié)議開銷，且由于導(dǎo)航衛(wèi)星網(wǎng)絡(luò)的端到端延時(shí)較大，網(wǎng)絡(luò)節(jié)點(diǎn)獲取的隊(duì)列信息可能已經(jīng)過時(shí)。因此，向全網(wǎng)泛洪隊(duì)列信息帶來的性能提升有限。

本文針對(duì)鏈路間斷可用的導(dǎo)航衛(wèi)星網(wǎng)絡(luò)，提出一種基于局部隊(duì)列的最早投遞(Earliest Delivery with Partial Queues，EDPQ)路由算法。EDPQ綜合利用鏈路調(diào)度信息、本地和鄰居節(jié)點(diǎn)隊(duì)列信息，可以實(shí)現(xiàn)鏈路調(diào)度按需更新，并以較低協(xié)議開銷更新鄰居節(jié)點(diǎn)隊(duì)列信息，實(shí)現(xiàn)了更高效的數(shù)據(jù)傳輸。

1 EDPQ路由算法

EDPQ路由算法利用全網(wǎng)的鏈路調(diào)度信息、本地和鄰居節(jié)點(diǎn)的隊(duì)列信息完成路由計(jì)算。全網(wǎng)的鏈路調(diào)度信息為已知信息且一般周期性重復(fù)，由于提前存儲(chǔ)未來所有的鏈路調(diào)度信息不現(xiàn)實(shí)，EDPQ采用一種按需更新的策略來更新鏈路調(diào)度信息;本地節(jié)點(diǎn)的隊(duì)列信息較容易獲取，而鄰居節(jié)點(diǎn)的隊(duì)列信息需要不斷更新，EDPQ采用一種低開銷的機(jī)制更新鄰居節(jié)點(diǎn)隊(duì)列信息。

1．1導(dǎo)航衛(wèi)星網(wǎng)絡(luò)的圖模型

記導(dǎo)航衛(wèi)星網(wǎng)絡(luò)的節(jié)點(diǎn)集合為V，邊集為E?V×V。定義ρ:E×R+→{0，1}為存在函數(shù)，表示在時(shí)刻t邊e是否存在;定義d:E×R+→R+為傳播延時(shí)函數(shù)，表示在時(shí)刻t邊e的傳播延時(shí)。對(duì)于導(dǎo)航衛(wèi)星網(wǎng)絡(luò)，節(jié)點(diǎn)集合為衛(wèi)星、地面站和任務(wù)運(yùn)行中心等網(wǎng)絡(luò)節(jié)點(diǎn)的集合;邊集為星間鏈路、星地鏈路和地面有線鏈路等通信鏈路的集合。

假定所有鏈路在可用時(shí)間間隔內(nèi)帶寬恒定，那么，在時(shí)刻t邊e的容量可以表示為c(e，t)=b(e)·ρ(e，t)，其中b(e)為邊e的帶寬。

記邊e的存在時(shí)間為I(e)={t∈R+:ρ(e，t)=1}，表示邊e存在的所有時(shí)間的集合。邊e的存在時(shí)間也可表示為一系列鏈路調(diào)度區(qū)間的集合，即I(e)={［t1，t2)∪［t3，t4)∪…}。對(duì)于導(dǎo)航衛(wèi)星網(wǎng)絡(luò)，鏈路的存在時(shí)間通常呈現(xiàn)周期性。定義邊e存在函數(shù)的周期為p，即對(duì)于任意t∈R+，任意k∈N，ρ(e，t)=ρ(e，t+kp)成立。那么邊e的存在時(shí)間可以表示為

1．2鏈路調(diào)度按需更新機(jī)制

對(duì)于導(dǎo)航衛(wèi)星網(wǎng)絡(luò)的鏈路調(diào)度信息，本文只存儲(chǔ)每條邊一個(gè)周期的鏈路調(diào)度信息，并在路徑計(jì)算過程中按需更新鏈路調(diào)度信息;同時(shí)，每隔固定時(shí)間Δtrm移除過去的鏈路調(diào)度信息，防止鏈路調(diào)度信息無限制增長，占用導(dǎo)航衛(wèi)星有限的存儲(chǔ)資源。

EDPQ利用改進(jìn)Dijkstra算法［17］計(jì)算下一跳，改進(jìn)Dijkstra算法可以利用邊的時(shí)變代價(jià)w:E×R+→R+計(jì)算延時(shí)最優(yōu)路徑。邊的時(shí)變代價(jià)w(e，t)除了與邊和時(shí)間有關(guān)外，與當(dāng)前消息大小和本地節(jié)點(diǎn)也有關(guān)，因此，為了統(tǒng)一，將代價(jià)函數(shù)寫為w(e，t)=w'(e，t，m，s)，其中，m為消息的大小，s為當(dāng)前節(jié)點(diǎn)［17］。

w'(e，t，m，s)可以寫為

w'(e，t，m，s)=t'(e，t，m，s)－t+d(e，t')

其中，

在上式中，函數(shù)Q(e，t，s)為本地節(jié)點(diǎn)s在時(shí)刻t獲取的邊e源端的隊(duì)列長度，t'為將隊(duì)列中的消息和當(dāng)前消息發(fā)送到網(wǎng)絡(luò)中的最早時(shí)刻［17］。

改進(jìn)Dijkstra算法的關(guān)鍵在于時(shí)間t'的計(jì)算，在實(shí)際實(shí)現(xiàn)t'計(jì)算公式中的積分時(shí)，需要綜合考慮當(dāng)前隊(duì)列中消息與待發(fā)送消息的大小、時(shí)刻t與接觸機(jī)會(huì)的關(guān)系，以及接觸機(jī)會(huì)的容量限制。圖2為當(dāng)前時(shí)刻與接觸機(jī)會(huì)的三種關(guān)系示意圖。第一種情況t=t1時(shí)，計(jì)算t'需要考慮下一個(gè)接觸機(jī)會(huì)的容量，如果下一個(gè)接觸機(jī)會(huì)容量不夠，還需要考慮下下一個(gè)接觸機(jī)會(huì)。第二種情況t=t2時(shí)，計(jì)算t'需要考慮當(dāng)前接觸機(jī)會(huì)的剩余容量，如果剩余容量不夠，也要考慮下一個(gè)接觸機(jī)會(huì)。第三種情況t=t3時(shí)，由于已經(jīng)沒有未來的接觸機(jī)會(huì)可用，需要首先增加一個(gè)周期的接觸機(jī)會(huì)，然后按第一種或第二種情況計(jì)算t'。

圖2 當(dāng)前時(shí)刻與接觸機(jī)會(huì)的三種關(guān)系Fig．2 Three potential relationships between current time and contact opportunities

圖3為計(jì)算t'及鏈路調(diào)度按需更新機(jī)制的偽代碼，其中，I為鏈路調(diào)度區(qū)間鏈表，臨時(shí)變量II為邊的某個(gè)鏈路調(diào)度區(qū)間，并用start和stop分別表示該鏈路調(diào)度區(qū)間的開始時(shí)間和結(jié)束時(shí)間，load為當(dāng)前消息和隊(duì)列中消息大小的總和;函數(shù)AddSched()將增加邊的一個(gè)周期的鏈路調(diào)度。

圖3 計(jì)算t'及鏈路調(diào)度按需更新機(jī)制的偽代碼Fig．3 Pseudocode of calculation for t'and on-demand link schedule updating mechanism

1．3鄰居節(jié)點(diǎn)隊(duì)列信息更新機(jī)制

演化圖模型［7，13］、空時(shí)路由算法［14］、接觸圖路由［15］、時(shí)變圖模型［16］和ED路由算法［17］等均只考慮鏈路調(diào)度信息，未考慮網(wǎng)絡(luò)的排隊(duì)延時(shí)，因此其性能有限。在DTN網(wǎng)絡(luò)中，消息傳輸?shù)亩说蕉搜訒r(shí)主要包括等待鏈路可用延時(shí)、排隊(duì)延時(shí)、發(fā)送延時(shí)和傳播延時(shí)。排隊(duì)延時(shí)雖然可能只占路徑延時(shí)的小部分，但由于導(dǎo)航衛(wèi)星網(wǎng)絡(luò)鏈路通信機(jī)會(huì)有限，較大的排隊(duì)延時(shí)可能會(huì)使消息錯(cuò)過當(dāng)前可用接觸機(jī)會(huì)，而只能等待下次接觸機(jī)會(huì)，從而增大端到端時(shí)延，并使消息長時(shí)間占用網(wǎng)絡(luò)資源，降低消息投遞成功率。因此，在導(dǎo)航衛(wèi)星網(wǎng)絡(luò)的路由計(jì)算中應(yīng)該考慮消息的排隊(duì)延時(shí)。

導(dǎo)航衛(wèi)星網(wǎng)絡(luò)的本地節(jié)點(diǎn)隊(duì)列信息較容易獲取，鄰居節(jié)點(diǎn)隊(duì)列信息也相對(duì)容易獲取。由于僅利用本地節(jié)點(diǎn)隊(duì)列信息不能使消息避開擁塞的鄰居節(jié)點(diǎn);而獲取全網(wǎng)隊(duì)列信息會(huì)帶來較大的協(xié)議開銷，且由于導(dǎo)航衛(wèi)星網(wǎng)絡(luò)路徑延時(shí)較大，獲取的全網(wǎng)隊(duì)列信息時(shí)效性較差，實(shí)際能夠帶來的性能改進(jìn)有限。因此，EDPQ除了利用鏈路調(diào)度信息外，僅考慮了本地和鄰居節(jié)點(diǎn)的隊(duì)列信息。

EDPQ采用一種隊(duì)列閾值觸發(fā)機(jī)制觸發(fā)隊(duì)列信息的發(fā)送，以降低鄰居節(jié)點(diǎn)隊(duì)列信息傳播帶來的協(xié)議開銷。本地節(jié)點(diǎn)收到鄰居節(jié)點(diǎn)發(fā)送的包含隊(duì)列信息的消息(簡稱隊(duì)列消息)后，通過人為加大擁塞的邊的排隊(duì)延時(shí)來降低選擇此邊的概率，從而避開排隊(duì)延時(shí)大的路徑。同時(shí)，鄰居節(jié)點(diǎn)隊(duì)列信息的作用應(yīng)該隨時(shí)間慢慢減弱，因此，本地節(jié)點(diǎn)對(duì)鄰居節(jié)點(diǎn)隊(duì)列信息按指數(shù)進(jìn)行衰減。

當(dāng)本地節(jié)點(diǎn)的發(fā)送機(jī)會(huì)(由于ISL為半雙工)出現(xiàn)時(shí)，本地節(jié)點(diǎn)首先統(tǒng)計(jì)除當(dāng)前邊外，其它邊的隊(duì)列大小Qsize≥95%Qlimit(Qlimit為隊(duì)列容量)的隊(duì)列個(gè)數(shù)。如果超出閾值的隊(duì)列個(gè)數(shù)大于等于1，本地節(jié)點(diǎn)將首先發(fā)送隊(duì)列消息到鄰居節(jié)點(diǎn)，然后再發(fā)送本地?cái)?shù)據(jù)消息;否則，直接發(fā)送本地?cái)?shù)據(jù)消息。鄰居節(jié)點(diǎn)如果利用本地節(jié)點(diǎn)與其相連的邊的話會(huì)產(chǎn)生路由環(huán)路，因此，沒有統(tǒng)計(jì)當(dāng)前邊。Qsize≥95%Qlimit說明即將發(fā)生擁塞，需要通知鄰居節(jié)點(diǎn)以避開此邊。

鄰居節(jié)點(diǎn)收到隊(duì)列消息后，將Qsize≥95%Qlimit的相應(yīng)隊(duì)列的大小按下式設(shè)置為一個(gè)比較大的數(shù)值，以避免選擇此邊。

式(1)基于這樣一種考慮，在DTN網(wǎng)絡(luò)中，等待時(shí)間通常占端到端延時(shí)的大部分，而最短路徑和次短路徑的延時(shí)代價(jià)可能相差較大，且相差的部分主要來自等待時(shí)間，排隊(duì)時(shí)間的變化通常不足以使最短路徑變?yōu)榇味搪窂剑瓜⑷匀贿x擇最短路徑進(jìn)一步加劇擁塞。

為了更清晰地說明上述情況，考慮圖4所示的一個(gè)示意圖。其中圖4(a)顯示了圖1中衛(wèi)星6到地面站G1的兩條路徑，圖中假定Δt為3 s，半雙工約定前半個(gè)時(shí)隙序號(hào)小的衛(wèi)星先發(fā)送，后半個(gè)時(shí)隙正好相反;圖4(b)為衛(wèi)星6的一種隊(duì)列情況示意圖，圖中衛(wèi)星6為每個(gè)鄰居節(jié)點(diǎn)分配一個(gè)等容量的隊(duì)列用于緩存消息。假設(shè)衛(wèi)星6的消息均發(fā)往地面站G1，由圖4(a)可知，消息可以通過最短路徑6－＞5－＞2－＞G1在4．5 s到達(dá)地面站G1，也可以通過次短路徑6－＞3－＞G1在6 s到達(dá)地面站G1，最短和次短路徑代價(jià)相差1．5 s。假定衛(wèi)星6中衛(wèi)星5的隊(duì)列已經(jīng)緩存了大量的消息，那么對(duì)于當(dāng)前消息m，雖然通過衛(wèi)星5轉(zhuǎn)發(fā)會(huì)經(jīng)歷較大的排隊(duì)延時(shí)，但只有當(dāng)排隊(duì)延時(shí)超過1．5 s時(shí)最短路徑的代價(jià)才會(huì)高于次短路徑。排隊(duì)延時(shí)最大為隊(duì)列容量除以ISL速率，假設(shè)隊(duì)列容量為40 kbits，ISL速率為50 kbps，排隊(duì)延時(shí)最大為0．8 s，仍然不能夠使最短路徑變?yōu)榇味搪窂?，因此需要人為加大擁塞的邊的排?duì)時(shí)間，降低選擇此邊的概率。由于最短路徑和次短路徑之間相差大于等于一個(gè)周期的情況較少，因此，設(shè)置排隊(duì)時(shí)間為該邊一個(gè)周期的時(shí)間。

EDPQ在產(chǎn)生消息或收到消息后，首先分別對(duì)本地隊(duì)列和鄰居節(jié)點(diǎn)隊(duì)列進(jìn)行處理。對(duì)每個(gè)本地隊(duì)列，如果Qsize≥Qlimit，那么按式(1)設(shè)置該隊(duì)列大小;對(duì)每個(gè)鄰居節(jié)點(diǎn)隊(duì)列，按下式進(jìn)行衰減［20］

式中:Δt為距上次鄰居節(jié)點(diǎn)隊(duì)列信息更新所經(jīng)歷的時(shí)間間隔數(shù)量，其值為實(shí)際時(shí)間間隔除以時(shí)間單位tunit，β∈(0，1)為衰減因子。由于節(jié)點(diǎn)發(fā)送消息時(shí)使用的鄰居節(jié)點(diǎn)隊(duì)列信息可能不是最新的，而且鄰居節(jié)點(diǎn)隊(duì)列信息更新不是周期性的，因此鄰居節(jié)點(diǎn)隊(duì)列信息應(yīng)該慢慢衰減。在對(duì)本地隊(duì)列信息和鄰居節(jié)點(diǎn)隊(duì)列信息處理完成后，利用改進(jìn)Dijkstra算法計(jì)算下一跳轉(zhuǎn)發(fā)節(jié)點(diǎn)。

2 性能評(píng)估

2．1仿真環(huán)境

圖4 用于解釋隊(duì)列大小設(shè)置的一個(gè)例子Fig．4 An example to explain the setting of queue size

為了校驗(yàn)EDPQ的性能，在典型的導(dǎo)航衛(wèi)星網(wǎng)絡(luò)中進(jìn)行了仿真評(píng)估。導(dǎo)航衛(wèi)星網(wǎng)絡(luò)由導(dǎo)航衛(wèi)星星座及相關(guān)地面站和任務(wù)運(yùn)行中心(Mission Operation Center，MOC)組成，如圖5所示。導(dǎo)航衛(wèi)星星座構(gòu)型選擇walker 24/3/2，即一共24顆衛(wèi)星分布在3個(gè)軌道面內(nèi)，相位因子為2。導(dǎo)航衛(wèi)星軌道高度為20232 km，傾角為55°。選用北京、喀什、三亞3個(gè)地面站，每個(gè)地面站均配置2副天線，并選擇與自己未來通信時(shí)間最長的兩顆導(dǎo)航衛(wèi)星建立全雙工GSL。地面站與MOC之間通過地面網(wǎng)絡(luò)時(shí)刻保持連通。

圖5 導(dǎo)航衛(wèi)星網(wǎng)絡(luò)系統(tǒng)架構(gòu)圖Fig．5 Network architecture of the navigation satellite network

每顆衛(wèi)星僅攜帶一副半雙工ISL天線，指向方位角限定在［－60°，60°］。由于地球的遮擋和ISL的指向限制，并不是所有衛(wèi)星間都能建立ISL［21］。一顆導(dǎo)航衛(wèi)星選擇與哪顆可見衛(wèi)星建立ISL屬于導(dǎo)航衛(wèi)星網(wǎng)絡(luò)的鏈路分配問題［22］，不在本文的研究范圍內(nèi)。為簡便起見，ISL的鏈路調(diào)度按每顆衛(wèi)星均能與全周期可見的同軌和異軌衛(wèi)星建立ISL的策略手動(dòng)生成。ISL的鏈路調(diào)度共有8個(gè)時(shí)隙，并以此為周期循環(huán)，每個(gè)時(shí)隙的持續(xù)時(shí)間為Δt。

導(dǎo)航衛(wèi)星網(wǎng)絡(luò)ISL的鏈路調(diào)度用一個(gè)24×8的矩陣表示，如圖6所示。矩陣的元素(i，j)表示衛(wèi)星i與衛(wèi)星(i，j)，在第j個(gè)時(shí)隙建立半雙工ISL。比如位于第2行和第3列的13表示，在第3個(gè)時(shí)隙，衛(wèi)星2與衛(wèi)星13建立半雙工ISL。每個(gè)時(shí)隙的前Δt/2，數(shù)值小的衛(wèi)星發(fā)送，數(shù)組大的衛(wèi)星接收，后Δt/2相反。

在OPNET網(wǎng)絡(luò)仿真軟件中對(duì)導(dǎo)航衛(wèi)星網(wǎng)絡(luò)進(jìn)行了建模，默認(rèn)仿真參數(shù)如表1所示，后文中，若無特殊說明，均采用此默認(rèn)仿真參數(shù)。導(dǎo)航衛(wèi)星網(wǎng)絡(luò)的消息由衛(wèi)星和MOC產(chǎn)生，消息到達(dá)時(shí)間間隔均服從指數(shù)分布。導(dǎo)航衛(wèi)星產(chǎn)生消息的目的節(jié)點(diǎn)為MOC，MOC產(chǎn)生消息的目的節(jié)點(diǎn)為隨機(jī)一顆衛(wèi)星。

表1 默認(rèn)仿真參數(shù)Table 1 The default simulation parameters

2．2仿真結(jié)果

比較的路由算法選擇ED、EDLQ和EDAQ。EDAQ可以有分布式和集中式兩種實(shí)現(xiàn)方式，由于Jain等［17］沒有說明EDAQ具體采用哪種實(shí)現(xiàn)方式，本文同時(shí)實(shí)現(xiàn)了兩種EDAQ，即EDAQ分布式(EDAQ Distributed，EDAQ-D)和EDAQ集中式(EDAQ Central，EDAQ-C)。EDAQ-D通過向全網(wǎng)泛洪隊(duì)列消息來獲取全網(wǎng)隊(duì)列信息，而EDAQ-C維護(hù)一個(gè)全局的網(wǎng)絡(luò)隊(duì)列信息庫，沒有任何協(xié)議開銷。EDAQ-C現(xiàn)實(shí)中較難實(shí)現(xiàn)，主要用作性能對(duì)比。

圖6 導(dǎo)航衛(wèi)星網(wǎng)絡(luò)ISL的鏈路調(diào)度Fig．6 Link schedule of the navigation satellite network

性能度量指標(biāo)選擇消息投遞成功率、端到端時(shí)延和協(xié)議開銷。投遞成功率為投遞成功的消息數(shù)量占產(chǎn)生消息總量的百分比;端到端時(shí)延為消息從產(chǎn)生到成功投遞所經(jīng)歷的時(shí)間，由于無法統(tǒng)計(jì)丟棄消息的時(shí)延，因此端到端時(shí)延僅統(tǒng)計(jì)成功投遞的消息;協(xié)議開銷為單位時(shí)間內(nèi)傳播的隊(duì)列消息的比特?cái)?shù)，即協(xié)議開銷為傳播的隊(duì)列消息個(gè)數(shù)乘以隊(duì)列消息大小，再除以仿真持續(xù)時(shí)間，其中，隊(duì)列消息大小為416 bits。在比較的五種路由算法中，僅有EDPQ和EDAQ-D會(huì)產(chǎn)生協(xié)議開銷。

為了測(cè)試不同網(wǎng)絡(luò)負(fù)載對(duì)路由算法性能的影響，設(shè)置導(dǎo)航衛(wèi)星的消息到達(dá)時(shí)間間隔從0．8 s以指數(shù)間隔變化到0．05 s，即網(wǎng)絡(luò)負(fù)載不斷增大。MOC的消息到達(dá)時(shí)間間隔保持恒定，仿真結(jié)果如圖7所示。由圖7(a)可以看出，隨著網(wǎng)絡(luò)負(fù)載的增大，五種路由的投遞成功率均呈下降趨勢(shì)，這是由于有限的存儲(chǔ)資源逐漸不能存儲(chǔ)產(chǎn)生的越來越多的消息，因此，越來越多的消息不能投遞到目的地。ED和EDLQ的性能較差，其投遞成功率在較低網(wǎng)絡(luò)負(fù)載時(shí)就開始下降。EDAQ-C的投遞成功率最高，EDPQ的性能與EDAQ-C接近。EDAQ-D的投遞成功率在網(wǎng)絡(luò)負(fù)載較大時(shí)比EDPQ要低，這是因?yàn)镋DAQ-D產(chǎn)生了較大的協(xié)議開銷，而EDPQ的協(xié)議開銷相對(duì)較低，如圖7(c)所示，較大的協(xié)議開銷會(huì)占用導(dǎo)航衛(wèi)星有限的存儲(chǔ)資源，使消息不能得到存儲(chǔ)而被丟棄。在圖7(c)中，當(dāng)消息到達(dá)時(shí)間間隔為0．8 s時(shí)，EDPQ和EDAQ-D的協(xié)議開銷均為零。

圖7(b)為不同路由算法的端到端時(shí)延性能。當(dāng)網(wǎng)絡(luò)負(fù)載較低時(shí)，五種路由算法的時(shí)延性能相當(dāng)。隨著網(wǎng)絡(luò)負(fù)載的增大，ED與EDLQ的端到端時(shí)延仍然較低，這與其較低的投遞成功率有關(guān);而其它路由算法的時(shí)延開始增大，這與其選擇擁塞程度差的路徑避免丟包有關(guān)。EDAQ-D產(chǎn)生的大量協(xié)議開銷會(huì)占用導(dǎo)航衛(wèi)星網(wǎng)絡(luò)有限的通信資源，使消息錯(cuò)過當(dāng)前可用通信機(jī)會(huì)，增大端到端時(shí)延。EDPQ與EDAQ-C的端到端時(shí)延性能接近。

為了測(cè)試不同隊(duì)列容量對(duì)路由算法性能的影響，設(shè)置導(dǎo)航衛(wèi)星每鄰居節(jié)點(diǎn)隊(duì)列容量分別為20、30、40、50、60 kbits，仿真結(jié)果如圖8所示。由圖8(a)可以看出，隨著隊(duì)列容量的增大，五種路由的投遞成功率均呈增大趨勢(shì)，這是由于增多的隊(duì)列容量可以存儲(chǔ)更多的消息，使更多的消息成功投遞到目的節(jié)點(diǎn)。在隊(duì)列容量小于50 kbits時(shí)，EDPQ與EDAQ-C的投遞成功率接近，而EDAQ-D的投遞成功率要比EDPQ低。這是由于EDAQ-D產(chǎn)生了大量的協(xié)議開銷，如圖8(c)所示，大量的協(xié)議開銷會(huì)占用有限的存儲(chǔ)資源，使消息得不到存儲(chǔ)而被丟棄。在隊(duì)列容量非常充足時(shí)(60 kbits)，EDPQ、EDAQ-D和EDAQ-C的投遞成功率均達(dá)到了百分之百。ED和EDLQ的投遞成功率均較低。

圖8(b)為不同路由算法的端到端時(shí)延性能。EDAQ-D的端到端時(shí)延較大，這是由于EDAQ-D產(chǎn)生的大量協(xié)議開銷會(huì)占用有限的通信資源，使消息錯(cuò)過當(dāng)前可用通信機(jī)會(huì)。EDPQ與EDAQ-C的端到端時(shí)延性能接近，但比EDAQ-D的端到端時(shí)延要低。ED與EDLQ的端到端時(shí)延較低，這與其較低的投遞成功率有關(guān)。

圖7 不同網(wǎng)絡(luò)負(fù)載時(shí)的路由性能Fig．7 Performance with varying network loads

為了測(cè)試不同ISL通信速率和不同數(shù)據(jù)消息大小對(duì)路由算法性能的影響，設(shè)置ISL通信速率分別為20、40、60、80 kbps，設(shè)置數(shù)據(jù)消息大小分別為512、1024、2048、4096 bits，仿真結(jié)果如圖9所示。由圖9(a)可以看出，當(dāng)ISL通信速率為20 kbps時(shí)，EDLQ、EDPQ與EDAQ-C的投遞成功率接近，而EDAQ-D和ED性能較差。由于EDAQ-D會(huì)產(chǎn)生大量的通信開銷占用有限的通信資源，這在ISL速率較低時(shí)會(huì)更明顯，因此其投遞成功率較低。當(dāng)ISL通信速率為40、60和80 kbps時(shí)，EDAQ-C的投遞成功率最高，EDPQ的投遞成功率與EDAQ-C接近，EDAQ-D的投遞成功率比EDPQ低，ED和EDLQ的投遞成功率最低。

圖8 不同隊(duì)列容量時(shí)的路由性能Fig．8 Performance with varying queue capacities

在圖9(b)中，當(dāng)數(shù)據(jù)消息大小為512 bits時(shí)，EDPQ與EDAQ-C的投遞成功率接近，而EDAQ-D與ED、EDLQ的投遞成功率較低。這是由于EDAQD帶來的較大協(xié)議開銷在數(shù)據(jù)消息大小與隊(duì)列消息大小相近時(shí)會(huì)更加明顯。較大的協(xié)議開銷使數(shù)據(jù)消息沒有機(jī)會(huì)得到有限的存儲(chǔ)資源，從而被丟棄;較大的協(xié)議開銷也使數(shù)據(jù)消息不能獲得有限的通信資源，而不得不等待未來的通信機(jī)會(huì)，進(jìn)而使數(shù)據(jù)消息長時(shí)間占用網(wǎng)絡(luò)存儲(chǔ)資源，使其它消息不能得到存儲(chǔ)資源，造成其它消息的丟棄。當(dāng)數(shù)據(jù)消息大小為1024、2048和4096 bits時(shí)，EDAQ-C的投遞成功率最高，EDPQ的投遞成功率與EDAQ-C接近，EDAQD的投遞成功率比EDPQ低，ED和EDLQ的投遞成功率最低。

圖9 投遞成功率與ISL通信速率和消息大小的關(guān)系Fig．9 Delivery success ratio with varying ISL rates and message sizes

3 結(jié)論

本文提出了一種基于局部隊(duì)列的最早投遞(EDPQ)路由算法，并在典型的導(dǎo)航衛(wèi)星網(wǎng)絡(luò)中對(duì)EDPQ進(jìn)行了仿真評(píng)估。仿真結(jié)果表明，EDPQ實(shí)現(xiàn)了較高的消息投遞成功率和較低的端到端延時(shí)，且具有較低的協(xié)議開銷，為鏈路間斷可用的導(dǎo)航衛(wèi)星網(wǎng)絡(luò)的路由問題提供了一種可行的技術(shù)方案。

［1］Maine K，Anderson P，Bayuk F．Communication architecture for GPS III［C］．2004 IEEE Aerospace Conference，Big Sky，USA，March 6－13，2004．

［2］Luba O，Boyd L，Gower A．GPS III system operations concepts［J］．IEEE Aerospace and Electronic Systems Magazine，2005，20(1):10－18．

［3］Fernandez A．Inter-satellite ranging and inter-satellite communication links for enhancing GNSS satellite broadcast navigation data［J］．Advances in Space Research，2011，47:786－801．

［4］Fall K．A delay-tolerant network architecture for challenged internets［C］．ACM SIGCOMM 2003，Karlsruhe，Germany，August 25－29，2003．

［5］ 林闖，董揚(yáng)威，單志廣．基于DTN的空間網(wǎng)絡(luò)互聯(lián)服務(wù)研究綜述［J］．計(jì)算機(jī)研究與發(fā)展，2014，51(5):931－943．［Lin Chuang，Dong Yang-wei，Shan Zhi-guang．Research on space internetworking service based on DTN［J］．Journal of Computer Research and Development，2014，51(5):931－943．］

［6］ 燕洪成，張慶君，孫勇，等．延遲/中斷容忍網(wǎng)絡(luò)技術(shù)及其在行星際因特網(wǎng)中的應(yīng)用［J］．航天器工程，2014，23(2):114－123．［Yan Hong-cheng，Zhang Qing-jun，Sun Yong，et al．Delay/disruption tolerant network and its application to interplanetary Internet［J］．Spacecraft Engineering，2014，23(2):114－123．］

［7］ 王彥，劉波，虞萬榮，等．基于演化圖的導(dǎo)航星座星間路由算法［J］．中國空間科學(xué)技術(shù)，2012(5):76－83．［Wang Yan，Liu Bo，Yu Wan-rong，et al．Routing algorithm for navigation constellation based on evolving graph model［J］．Chinese Space Science and Technology，2012(5):76－83．］

［8］Cormen T，Leiserson C．Introduction to algorithm［M］．Cambridge:The MIT Press，2004．

［9］ 盧勇，趙有健，孫富春，等．衛(wèi)星網(wǎng)絡(luò)路由技術(shù)［J］．軟件學(xué)報(bào)，2014，25(5):1085－1100．［Lu Yong，Zhao You-jian，Sun Fuchun，et al．Routing techniques on satellite networks［J］．Journal of Software，2014，25(5):1085－1100．］

［10］ 王路，劉立祥，胡曉惠．基于地理位置信息的無收斂多測(cè)度衛(wèi)星網(wǎng)絡(luò)路由算法研究［J］．宇航學(xué)報(bào)，2011，32(7):1542－1550．［Wang Lu，Liu Li-xiang，Hu Xiao-hui．Geographical location-based convergence-free routing using multiple metrics for satellite networks［J］．Journal of Astronautics，2011，32(7):1542－1550．］

［11］ 蘇金樹，胡喬林，趙寶康，等．容延容斷網(wǎng)絡(luò)路由技術(shù)［J］．軟件學(xué)報(bào)，2010，21(1):119－132．［Su Jin-shu，Hu Qiao-lin，Zhao Bao-kang，et al．Routing techniques on delay/disruption tolerant networks［J］．Journal of Software，2010，21(1):119－132．］

［12］Cao Y，Sun Z．Routing in delay/disruption tolerant networks:a taxonomy，survey and challenges［J］．IEEE Communications Surveys＆Tutorials，2013，15(2):654－677．

［13］Ferreira A．Building a reference combinatorial model for MANETs［J］．IEEE Network，2004，18(5):24－29．

［14］Merugu S，Ammar M，Zegura E．Routing in space and time in networks with predictable mobility，GIT-CC－04－07［R］．Atlanta，USA:Georgia Institute of Technology，March 2004．

［15］Burleigh S．Contact graph routing，IRTF Internet-Draft［EB/OL］．2010－07－08［2014－12－02］．http://tools．ietf．org/html/draft-burleigh-dtnrg-cgr-01．

［16］Casteigts A，F(xiàn)locchini P，Quattrociocchi W，et al．Time-varying graphs and dynamic networks［J］．International Journal of Parallel，Emergent and Distributed Systems，2012，27(5):387－408．

［17］Jain S，F(xiàn)all K，Patra R．Routing in a delay tolerant network［J］．ACM SIGCOMM Computer Communication Review，2004，34(4):145－158．

［18］Bezirgiannidis N，Caini C，Montenero D P，et al．Contact graph routing enhancements for delay tolerant space communications［C］．7th Advanced Satellite Multimedia Systems Conference and the 13th Signal Processing for Space Communications Workshop(ASMS/SPSC)，Livorno，Italy，September 8－10，2014．

［19］Bezirgiannidis N，Tsapeli F，Diamantopoulos S，et al．Towards flexibility and accuracy in space DTN communications［C］．The 8th ACM MobiCom Workshop on Challenged Networks，Miami，USA，September 30，2013．

［20］Lindgren A．Probabilistic routing in intermittently connected networks［J］．ACM Mobile Computing and Communication Review，2003，7(3):19－20．

［21］ 李振東，何善寶，劉崇華，等．一種導(dǎo)航星座星間鏈路拓?fù)湓O(shè)計(jì)方法［J］．航天器工程，2011，20(3):32－37．［Li Zhendong，He Shan-bao，Liu Chong-hua，et al．An topology design method of navigation satellite constellation inter-satellite links［J］．Spacecraft Engineering，2011，20(3):32－37．］

［22］ 石磊玉，向?yàn)?，唐小妹．一種兼顧衛(wèi)星導(dǎo)航系統(tǒng)星間觀測(cè)及通信的鏈路分配算法［J］．宇航學(xué)報(bào)，2011，32(9):1971－1977．［Shi Lei-yu，Xiang Wei，Tang Xiao-mei．A link assignment algorithm applicable to crosslink ranging and data exchange for satellite navigation system［J］．Journal of Astronautics，2011，32(9):1971－1977．］