戴永珊 ， 姜興龍 ， 劉會(huì)杰

（1.中國科學(xué)院 上海微系統(tǒng)與信息技術(shù)研究所，上海 200050；2.上海微小衛(wèi)星工程中心 上海 201210）

衛(wèi)星星座與衛(wèi)星編隊(duì)飛行技術(shù)是現(xiàn)階段兩種主流衛(wèi)星集群實(shí)現(xiàn)方式[1]。衛(wèi)星星座系統(tǒng)是面向特定需求而設(shè)計(jì)的通信系統(tǒng)，在最初設(shè)計(jì)階段限定了網(wǎng)絡(luò)的規(guī)模和容量，在業(yè)務(wù)需求超過原有系統(tǒng)的承載能力時(shí)，需要進(jìn)行網(wǎng)絡(luò)擴(kuò)容；而衛(wèi)星編隊(duì)飛行中以美國的F6計(jì)劃[2]最為典型，以“快速響應(yīng)需求、靈活采辦、快速研制、快速部署、分散目標(biāo)、靈活重構(gòu)、適于攻防對(duì)抗”為設(shè)計(jì)目標(biāo)，需要具備自發(fā)現(xiàn)、自動(dòng)配置、故障自愈功能；此外，復(fù)雜的空間環(huán)境使衛(wèi)星及星間鏈路存在故障風(fēng)險(xiǎn)。因此，航天任務(wù)對(duì)空間網(wǎng)絡(luò)提出了新的技術(shù)要求——具有可快速兼容平穩(wěn)擴(kuò)展、自主故障發(fā)現(xiàn)并修復(fù)的特性，自組織網(wǎng)絡(luò)技術(shù)正好可以解決這個(gè)技術(shù)難題。隨著空間技術(shù)的發(fā)展，未來航天任務(wù)的發(fā)展正向靈活的分布式動(dòng)態(tài)星座、成型空間移動(dòng)平臺(tái)組成的自組織空間網(wǎng)絡(luò)[2]方向靠攏。另一方面，星座系統(tǒng)往往受到成本及風(fēng)險(xiǎn)的制約，在分階段擴(kuò)展部署過程中，稀疏空間網(wǎng)絡(luò)的路由問題將是其面對(duì)的首要問題。

在Ad Hoc網(wǎng)絡(luò)中，移動(dòng)節(jié)點(diǎn)通過無線多跳實(shí)現(xiàn)相互通信，開發(fā)一種能有效找到節(jié)點(diǎn)間路由的動(dòng)態(tài)路由算法是網(wǎng)絡(luò)設(shè)計(jì)的關(guān)鍵。常用的自組織路由算法[4]主要有DSDV、WRP、AODV、DSR等，但應(yīng)用于空間自組織網(wǎng)的路由算法研究較少。文獻(xiàn)[2]研究了空間自組織網(wǎng)絡(luò)的拓?fù)浣Y(jié)構(gòu)、消息傳遞機(jī)制、路由算法，其路由算法通過對(duì)空間網(wǎng)絡(luò)中每一個(gè)節(jié)點(diǎn)進(jìn)行特殊的多層次命名，根據(jù)節(jié)點(diǎn)名稱的可識(shí)別性進(jìn)行路由路徑選擇。該方法在空間系統(tǒng)龐大情況下，具有較高效率，而在單個(gè)衛(wèi)星系統(tǒng)中效率極低。文獻(xiàn)[5]提出了在LEO/MEO衛(wèi)星網(wǎng)絡(luò)中運(yùn)用自組網(wǎng)思想，將整個(gè)網(wǎng)絡(luò)劃分成簇，將一張大網(wǎng)規(guī)劃成子網(wǎng)，降低系統(tǒng)信令開銷，該方案適用于網(wǎng)絡(luò)節(jié)點(diǎn)密集，且星間結(jié)構(gòu)變化不頻繁的情況。

鑒于對(duì)稀疏空間網(wǎng)絡(luò)路由算法研究的不足，以LEO衛(wèi)星稀疏自組織網(wǎng)絡(luò)為研究對(duì)象，針對(duì)缺乏持續(xù)連接（缺乏穩(wěn)定的端到端路徑）、高延時(shí)、網(wǎng)絡(luò)資源有限的特點(diǎn)，提出一種基于鏈路預(yù)測(cè)的異步路由算法，并從時(shí)延最優(yōu)和跳數(shù)最少兩個(gè)方面對(duì)算法進(jìn)行了仿真比較。

1 基于鏈路預(yù)測(cè)的LEO衛(wèi)星稀疏自組織網(wǎng)絡(luò)異步路由

LEO衛(wèi)星稀疏自組織網(wǎng)絡(luò)缺乏穩(wěn)定連接，傳統(tǒng)的同步路由算法通常無效，但這不表示衛(wèi)星間不能傳輸數(shù)據(jù)。隨著衛(wèi)星的運(yùn)動(dòng)，鏈路在網(wǎng)絡(luò)中不同的位置不斷連接或斷開。如果將單位時(shí)間內(nèi)的網(wǎng)絡(luò)看成一個(gè)靜態(tài)網(wǎng)絡(luò)，用靜態(tài)的無向圖描述，將多個(gè)這樣的無向圖按時(shí)間序列重疊，則必然存在一條或多條“基于時(shí)間推移的端到端路徑”[6]?；谶@種思想，通過鏈路預(yù)測(cè)預(yù)估衛(wèi)星間的連接關(guān)系，將衛(wèi)星網(wǎng)絡(luò)通過時(shí)間-空間圖描述，然后基于最少跳數(shù)、最短時(shí)延準(zhǔn)則，運(yùn)用三維的Bellman-Ford算法，得到最優(yōu)路由表。

1.1 研究模型與度量標(biāo)準(zhǔn)

Walker星座具有很好的對(duì)稱性，在星座系統(tǒng)中有廣泛的應(yīng)用，例如Globalstar，GPS，北斗。研究模型選擇Walker傾斜軌道星座[5]，由N顆衛(wèi)星在P個(gè)相同傾斜衛(wèi)星軌道平面組成、能夠全球覆蓋的衛(wèi)星星座。Walker星座通常采用符號(hào)N/P/F表示，參數(shù)描述：

1）S＝N/P表示每個(gè)軌道面衛(wèi)星的個(gè)數(shù)，F(xiàn)表示 Walker星座的相位因子（F=1，2，…，P-1），F(xiàn) 確定了相鄰軌道平面上衛(wèi)星之間的偏離角度Δwf=2πF/N；

2）傾斜軌道平面的上升節(jié)點(diǎn)沿著赤道等間隔排列；

3）傾斜軌道平面之間具有固定的平面偏移ΔΩ=2π/P；

4）每個(gè)傾斜軌道平面內(nèi)衛(wèi)星以Δω=2π/S間隔均勻分布。

文中Walker星座模型為應(yīng)用場(chǎng)景，研究LEO衛(wèi)星稀疏異步自組織網(wǎng)絡(luò)的路由算法，從而實(shí)現(xiàn)星上最優(yōu)路徑路由表生成。

根據(jù)稀疏Ad Hoc網(wǎng)絡(luò)的結(jié)構(gòu)特點(diǎn)[7]，可歸納主要的性能度量準(zhǔn)則如下：

1）跳數(shù)：描述了源到目的節(jié)點(diǎn)的組成路徑的鏈路數(shù)量，跳數(shù)少則整體功耗低。

2）端到端時(shí)延：端到端時(shí)延指的是數(shù)據(jù)包從目的到源節(jié)點(diǎn)所經(jīng)歷的時(shí)間，包括路由等待時(shí)間和接口時(shí)延等。

3）生存時(shí)間：路由生存時(shí)間指的是路由建立開始到下一次更新所能夠正常使用的時(shí)間。

4）路由容量：路由容量用來描述源到目標(biāo)節(jié)點(diǎn)在生存時(shí)間內(nèi)能夠傳輸?shù)淖畲髷?shù)據(jù)量。

本算法為異步路由算法，只要前一個(gè)節(jié)點(diǎn)的數(shù)據(jù)成功傳輸?shù)较乱粋€(gè)節(jié)點(diǎn)，以前的鏈路不再影響后續(xù)路由，路由生存時(shí)間只與數(shù)據(jù)當(dāng)前到達(dá)時(shí)間、時(shí)間窗結(jié)束時(shí)間相關(guān)，故算法選擇最少跳數(shù)、最短端到端時(shí)延為最優(yōu)路由路徑的衡量準(zhǔn)則。

1.2 路由算法描述

Walker星座是一個(gè)具有延遲拓?fù)浣Y(jié)構(gòu)[8]的LEO衛(wèi)星稀疏自組織網(wǎng)絡(luò)，不同節(jié)點(diǎn)對(duì)應(yīng)不同衛(wèi)星，節(jié)點(diǎn)間的連接關(guān)系代表星間鏈路，如圖1所示（以Walker6/2/1為例）。衛(wèi)星隨時(shí)間不斷運(yùn)動(dòng)，網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)也在不斷變化。傳統(tǒng)靜態(tài)圖不能表示出這種變化過程，需要一系列的靜態(tài)圖來建立隨時(shí)間變化的延遲拓?fù)渚W(wǎng)絡(luò)結(jié)構(gòu)模型。如圖1所示，每一張靜態(tài)圖都是網(wǎng)絡(luò)中所有節(jié)點(diǎn)的快照，記錄當(dāng)前時(shí)刻各節(jié)點(diǎn)間的連接關(guān)系。在T0時(shí)刻，該星座存在三條星間鏈路，整個(gè)網(wǎng)絡(luò)是不連通的，不能實(shí)現(xiàn)從sat11至sat13的數(shù)據(jù)傳送。本文描述的鏈路預(yù)測(cè)，是指通過STK軟件實(shí)時(shí)預(yù)報(bào)的軌道信息，計(jì)算出衛(wèi)星間的連通關(guān)系，得到任意時(shí)刻的網(wǎng)絡(luò)連接圖。通過約束星間的可見條件，可以模擬衛(wèi)星網(wǎng)絡(luò)的變化。

圖1 衛(wèi)星網(wǎng)絡(luò)的隨時(shí)間變化的連接關(guān)系Fig.1 A time-evolving topologies of a satellite network

為方便下文算法的描述，進(jìn)一步分析上述模型，并轉(zhuǎn)化為圖論問題。將連續(xù)的時(shí)間分成離散時(shí)間序列{1，2，…，T}，該星座有 6 個(gè)節(jié)點(diǎn)，分別為 sat11、sat12、sat13、sat21、sat22、sat23，以 S={s1，s2，…，s6}表示，而 Gt=（St，Et）表示網(wǎng)絡(luò)在時(shí)刻 t的網(wǎng)絡(luò)快照，其中∈Et表示節(jié)點(diǎn)si和節(jié)點(diǎn)sj在時(shí)刻t存在一條互相連通的信道，因此該網(wǎng)絡(luò)可以表示為{Gt|t=1，2，…，T}。圖2描述了在時(shí)刻t處的星座網(wǎng)絡(luò)對(duì)應(yīng)的快照示意圖，這種表示法包含了空間和時(shí)間上的所有信息，與大多數(shù)現(xiàn)有的延遲拓?fù)渚W(wǎng)絡(luò)路由算法適用的如圖3所示的連接模型不同（在時(shí)刻t每個(gè)節(jié)點(diǎn)都連接著多個(gè)其余節(jié)點(diǎn)，有多條可選擇路徑，整個(gè)網(wǎng)絡(luò)中任意兩個(gè)節(jié)點(diǎn)互相可達(dá)，但該模型忽略了網(wǎng)絡(luò)中的時(shí)間、順序信息，沒有反映出同一時(shí)刻鏈路的部分有效性），為此，本文條件下，需針對(duì)圖2所示模型進(jìn)行深入分析。

圖2 衛(wèi)星網(wǎng)絡(luò)的網(wǎng)絡(luò)快照示意圖Fig.2 A sequence of snapshots of the satellite network at each time slot satellite network

圖3 衛(wèi)星網(wǎng)絡(luò)的網(wǎng)絡(luò)連接示意圖Fig.3 The aggregated graph modelofthe

將圖2的靜態(tài)圖轉(zhuǎn)化為圖4的時(shí)間-空間關(guān)系圖G=（υ，ε）。由圖知，該時(shí)間-空間關(guān)系圖G中有T+1組節(jié)點(diǎn)，每組含6 個(gè)節(jié)點(diǎn)，其中 υ={|j=1，…，6 and t=0，…，T}，是所有節(jié)點(diǎn)的集合，因此網(wǎng)絡(luò)總共含6（T+1）個(gè)節(jié)點(diǎn)。圖中所示有兩種類型的鏈路，分別為時(shí)間鏈路和空間鏈路，組與組之間的空白部分代表的是時(shí)間的流逝，在一塊空白中數(shù)據(jù)保存在本節(jié)點(diǎn)則向右平傳，否則在該時(shí)間段內(nèi)傳送到下一個(gè)時(shí)間節(jié)點(diǎn)。因此，表示在第（t-1）秒至第t秒間，數(shù)據(jù)保存在j節(jié)點(diǎn)，相當(dāng)于時(shí)間鏈路；表示在第（t-1）秒至第t秒間，數(shù)據(jù)從節(jié)點(diǎn)i傳送到j(luò)節(jié)點(diǎn)，相當(dāng)于空間鏈路。通過上述定義，時(shí)間-空間關(guān)系圖中的任意一條鏈路都能用數(shù)學(xué)模型抽象表示，如圖4所示，路徑sat110sat133表示一條路由路徑從節(jié)點(diǎn)sat11出發(fā)，在節(jié)點(diǎn)sat11處存儲(chǔ)了1個(gè)單位時(shí)間間隔，在第二個(gè)單位時(shí)間間隔傳送至節(jié)點(diǎn)sat22，在第3個(gè)單位時(shí)間間隔傳送至節(jié)點(diǎn)sat13。

圖4 衛(wèi)星網(wǎng)絡(luò)的時(shí)間-空間連接關(guān)系表Fig.4 The time-space graph of the satellite network

至此，問題轉(zhuǎn)化為通過圖4表示的連接關(guān)系，選擇一條最優(yōu)路徑，由起始點(diǎn)至終點(diǎn)。即：假定鏈路都是可靠的，基于最少跳數(shù)、最短端到端時(shí)延原則，利用三維的Bellman-Ford算法求取最優(yōu)路徑。

Bellman-Ford算法基本思想是通過迭代確定最優(yōu)路徑。假定我們尋找一條從源節(jié)點(diǎn)s1到目的節(jié)點(diǎn)s3的最短端到端時(shí)延路徑，以迭代方程表示如下：

其中，dij由每一時(shí)刻的鄰接矩陣給出，若衛(wèi)星i和衛(wèi)星j之間存在星間鏈路，則設(shè)定其鏈路重量dij為1，否則為無窮大（Inf）。

在s1→s3最短端到端時(shí)延路徑求解中，目的節(jié)點(diǎn)為s3，距離符號(hào)Di表示在一定限制條件下，從i節(jié)點(diǎn)到目的節(jié)點(diǎn)s3的最優(yōu)路徑的代價(jià)（其中i為任意中間節(jié)點(diǎn)），每次迭代過程中，所有節(jié)點(diǎn)的距離標(biāo)號(hào)都是臨時(shí)標(biāo)號(hào)，當(dāng)?shù)K止時(shí)，限制條件被完全消除，因此所有節(jié)點(diǎn)的臨時(shí)標(biāo)號(hào)同時(shí)被轉(zhuǎn)為永久標(biāo)號(hào)，j是最優(yōu)路徑的中間節(jié)點(diǎn)。即D是第h次迭代得到的節(jié)點(diǎn)i的臨時(shí)標(biāo)號(hào)，表示經(jīng)h步可到達(dá)的路徑中最短徑的長(zhǎng)度。最后得到的Di=D是最終的最短路徑的時(shí)延。

2 算法仿真

為了對(duì)算法的性能進(jìn)行仿真驗(yàn)證，搭建基于STK和OPNET的仿真平臺(tái)，選取典型的仿真場(chǎng)景進(jìn)行系統(tǒng)建模和仿真。

2.1 仿真場(chǎng)景設(shè)置

仿真目的主要包括：1）驗(yàn)證基于鏈路預(yù)測(cè)的低軌衛(wèi)星自組織網(wǎng)絡(luò)異步路由算法，因此僅包含衛(wèi)星交換網(wǎng)絡(luò)，不包括地面站、終端等設(shè)備；2）分析其擴(kuò)展性，比較該算法在不同規(guī)模網(wǎng)絡(luò)結(jié)構(gòu)中的整體網(wǎng)絡(luò)性能；3）比較以不同性能度量為設(shè)計(jì)目標(biāo)的系統(tǒng)性能，性能度量選取典型的平均時(shí)延和平均跳數(shù)。

網(wǎng)絡(luò)規(guī)模分別選取常見的6/2/1Walker星座、12/3/1Walker星座、24/4/1Walker星座、48/8/1 Walker星座。衛(wèi)星軌道選擇軌道高度為1 400 km，軌道傾角為52°的圓軌道（參照Globalstar）。仿真中假設(shè)衛(wèi)星天線為全向天線，限定最遠(yuǎn)通信距離為該軌道高度視距可見最大距離8 800 km，仿真周期設(shè)為2個(gè)軌道周期（軌道周期為6 600 s）。在時(shí)延統(tǒng)計(jì)上，假設(shè)星間鏈路帶寬足夠大，不存在擁塞，時(shí)延主要來自等待時(shí)延和傳播時(shí)延。

2.2 仿真結(jié)果

根據(jù)上述設(shè)置，分別以最少跳數(shù)和最短時(shí)延為設(shè)計(jì)準(zhǔn)則，仿真分析基于鏈路預(yù)測(cè)的LEO衛(wèi)星稀疏自組織網(wǎng)絡(luò)異步路由算法的可行性，得到了以平均時(shí)延、平均跳數(shù)為衡量準(zhǔn)則的網(wǎng)絡(luò)性能隨星座規(guī)模的變化規(guī)律。

如圖5所示，網(wǎng)絡(luò)傳輸平均時(shí)延與Walker星座規(guī)模的變化關(guān)系，由結(jié)果分析可知：衛(wèi)星的平均傳輸時(shí)延隨著衛(wèi)星規(guī)模的增加而減小。1）在網(wǎng)絡(luò)規(guī)模較小，即LEO衛(wèi)星分布很稀疏的情況下（15顆星以下），星座網(wǎng)絡(luò)是非連通的，時(shí)延以等待時(shí)延為主（等待時(shí)延遠(yuǎn)大于傳播時(shí)延），兩種準(zhǔn)則得到的平均時(shí)延普遍偏高；2）隨著網(wǎng)絡(luò)規(guī)模逐漸擴(kuò)大，即LEO衛(wèi)星分布相對(duì)密集情況下，以最短時(shí)延實(shí)現(xiàn)路由路徑尋找效果更好。在衛(wèi)星規(guī)模大于24顆時(shí)，星座網(wǎng)絡(luò)是全連通的，平均時(shí)延以傳播時(shí)延為主，由于系統(tǒng)仿真的時(shí)延統(tǒng)計(jì)設(shè)置最小分辨率為分鐘，故該值恒為1。

圖5 以最少跳數(shù)和最短時(shí)延為設(shè)計(jì)準(zhǔn)則的平均時(shí)延Fig.5 The average cost time of the network based on minimumhops and minimum delay

圖6 以最少跳數(shù)和最短時(shí)延為設(shè)計(jì)準(zhǔn)則的平均跳數(shù)Fig.6 The average hops of the network based on minimumhops and minimum delay

如圖6所示，網(wǎng)絡(luò)傳輸平均跳數(shù)與Walker星座規(guī)模的變化關(guān)系，由結(jié)論分析可知：以最少時(shí)延實(shí)現(xiàn)最優(yōu)路由路徑尋找，所耗費(fèi)的網(wǎng)絡(luò)平均跳數(shù)大于以最少跳數(shù)準(zhǔn)則，且隨著網(wǎng)絡(luò)規(guī)模的擴(kuò)大，差距越明顯；為實(shí)現(xiàn)最少跳數(shù)，網(wǎng)絡(luò)平均最小跳數(shù)長(zhǎng)期保持接近于1（卻總是保持大于1，有一些節(jié)點(diǎn)不能通過一跳傳輸直接到達(dá)目的節(jié)點(diǎn)）。

綜上所述，平均時(shí)延最小準(zhǔn)則可以得到時(shí)延性能突出的路由表，但隨著網(wǎng)絡(luò)規(guī)模的擴(kuò)大將帶來平均路由跳數(shù)的增加，也將大大提高星間鏈路的傳輸負(fù)荷，這對(duì)稀缺的星間鏈路傳輸帶寬資源提出了挑戰(zhàn)；而平均跳數(shù)最小準(zhǔn)則隨著衛(wèi)星規(guī)模的擴(kuò)大，平均跳數(shù)變化相對(duì)平穩(wěn)，對(duì)星間鏈路傳輸帶寬要求較低，但時(shí)延性能相比平均時(shí)延最小準(zhǔn)則大幅增加。

3 結(jié)束語

基于現(xiàn)有衛(wèi)星集群方式，分析其組網(wǎng)的技術(shù)特點(diǎn)，考慮移動(dòng)自組織網(wǎng)絡(luò)技術(shù)，提出一種基于鏈路預(yù)測(cè)的稀疏LEO自組織網(wǎng)絡(luò)異步路由算法，并通過仿真驗(yàn)證了算法的可行性。該算法具有擴(kuò)展性、抗毀性，適用范圍廣的優(yōu)點(diǎn)。

但該算法也有不足之處，算法描述模型中一個(gè)單位時(shí)間只允許一跳傳輸，若需要在一個(gè)單位時(shí)間間隔內(nèi)進(jìn)行多跳，則需要在算法中添加虛擬的路徑，將多跳起始點(diǎn)與終點(diǎn)相連接，這可作為稀疏自組織網(wǎng)絡(luò)的下一步研究問題。同時(shí)，可進(jìn)一步研究考慮星間鏈路帶寬較小并存在擁塞的情況下算法采用自適應(yīng)的機(jī)制去調(diào)整路由優(yōu)化的準(zhǔn)則。

[1]董云峰，王興龍.衛(wèi)星集群概念研究[J].航天器工程，2012（4）:83-88.DONG Yun-feng，WANG Xing-long.Research on conception of satellite cluster[J].Spacecraft Engineering，2012（4）:83-88.

[2]吳勤.美國F6計(jì)劃概況[J].國際太空，2008（5）:1-5.WU Qing.The general situation of the F6 plan[J].Space International，2008（5）:1-5.

[3]Chien-Chung Shen， SundaramRajagopalan， GirishBorkar.A exible routing architecture for ad hoc space networks[J].Computer Networks，2004(46):389-410.

[4]曹英烈.移動(dòng)ad hoc網(wǎng)絡(luò)路由算法研究[D].廣州：華南理工大學(xué)，2006.

[5]李喆，李冬妮，王光興.LEO/MEO衛(wèi)星網(wǎng)絡(luò)中運(yùn)用自組網(wǎng)思想的動(dòng)態(tài)路由算法[J].通信學(xué)報(bào)，2005，26（5）:50-56.LI Zhe，LI Dong-ni，WANG Guang-xing.New dynamic routing algorithm based on MANET technologyin the LEO/MEO satellite network[J].Journal on Communications，2005，26（5）:50-56.

[6]王欣.容遲/容斷移動(dòng)自組織網(wǎng)絡(luò)路由技術(shù)研究[D].天津：天津大學(xué)，2010.

[7]Cruz-Sa'nchez H，F(xiàn)ranck L，Beylot A L.Routing metrics for store and forward[J].The Institution of Engineering and Technology，2010，4（13）:1563-1572.

[8]Huang M，Chen S，Li F，et al.Topology design in time-evolving delay-tolerant networks with unreliable links[C]//Global Communications Conference（GLOBECOM），2012IEEE.IEEE，2012:5296-5301.