一種適用于空間容延遲網(wǎng)絡(luò)的路由算法

于相聲，孫晨華

(中國電子科技集團公司第五十四研究所，河北石家莊050081)

0 引言

2003年K.Fall［1］等科學(xué)家在ICIR上提出了延遲容忍網(wǎng)絡(luò)(Delay Tolerant Network，DTN)的概念。這種網(wǎng)絡(luò)主要泛指那些由于節(jié)點移動、能量受限等原因而頻繁出現(xiàn)鏈路中斷、甚至長時間處于分離狀態(tài)的一類無線網(wǎng)絡(luò)。衛(wèi)星網(wǎng)絡(luò)具有遠距離無線通信的高時延、衛(wèi)星間鏈路間歇性連通和信道傳輸數(shù)據(jù)率的不對稱等特點，因此，衛(wèi)星網(wǎng)絡(luò)可被看作一種典型的 DTN 網(wǎng)絡(luò)［2］。

本文針對衛(wèi)星網(wǎng)絡(luò)高延遲、高誤碼率和終端移動性的特點，提出了一種解決終端移動問題的路由算法SRM，該算法利用衛(wèi)星節(jié)點的運動規(guī)律和終端節(jié)點的相遇概率，通過構(gòu)造鏈接時序表和概率信息表，有效解決衛(wèi)星網(wǎng)絡(luò)的路由問題。

1 DTN路由研究現(xiàn)狀

由于DTN網(wǎng)絡(luò)的特點，路由問題一直是研究熱點，從路由策略［3，4］方面來看，DTN 路由算法可以分為確定性路由［5，6］和隨機性路由［7］兩大類。

1．1 確定性路由

確定性路由假定節(jié)點將來的移動和連接是可預(yù)測的，也就是整個網(wǎng)絡(luò)的拓?fù)浣Y(jié)構(gòu)是可以提前預(yù)知的。主要算法包括鏈接圖路由［8－10］和時空路由。這類路由需要太多的網(wǎng)絡(luò)知識(包括節(jié)點的移動規(guī)律、鏈接時序和網(wǎng)絡(luò)拓?fù)涞?。

1．1．1 鏈接圖路由

鏈接圖路由完全依賴于通信結(jié)點間鏈路的預(yù)先規(guī)劃，而且每個結(jié)點都知道規(guī)劃的詳情。節(jié)點能夠通過這些信息構(gòu)造出一個鏈接信息圖，節(jié)點通過鏈接信息圖實現(xiàn)動態(tài)的路由查找。

1．1．2 時空路由

時空路由通過構(gòu)建時空路由表，在當(dāng)前和將來預(yù)期的鄰居節(jié)點中選擇下一跳節(jié)點，不同于傳統(tǒng)的路由表，時空路由表使用目的節(jié)點位置和消息到達的時間來確定其下一跳節(jié)點。

1．2 隨機性路由

隨機性路由方案假定網(wǎng)絡(luò)是動態(tài)的、不確定的，這類路由不需要太多的網(wǎng)絡(luò)知識就能進行路由，但是它在網(wǎng)絡(luò)中產(chǎn)生了太多的復(fù)制，容易占用網(wǎng)絡(luò)資源。其中，傳染式路由是具有代表性的多副本路由算法。

1．2．1 傳染式路由

傳染式路由［11，12］模仿生物環(huán)境中傳染性病毒擴散傳播方式，即每個被病毒傳染的個體將把病毒傳給與其接觸的其他個體。傳染性路由采用洪泛機制，每個節(jié)點存儲所要轉(zhuǎn)發(fā)的消息，直到網(wǎng)絡(luò)中所有節(jié)點都收到此消息為止。

1．2．2 隨機轉(zhuǎn)發(fā)路由

在隨機轉(zhuǎn)發(fā)路由中，節(jié)點將數(shù)據(jù)包隨機地發(fā)送給鄰居節(jié)點，鄰居節(jié)點再將數(shù)據(jù)包隨機地發(fā)送給它的鄰居節(jié)點，直到找到目的節(jié)點為止。這種算法最好的結(jié)果是數(shù)據(jù)包只經(jīng)過一跳就到達了目的節(jié)點，最差的情況是數(shù)據(jù)包歷經(jīng)了網(wǎng)絡(luò)中所有的節(jié)點后才到達目的節(jié)點。

本文的空間DTN拓?fù)涫怯?顆同步衛(wèi)星、4顆低軌衛(wèi)星、1顆空間飛行器、1個地面中心站、1個機載站以及1個船載站組成，在軌衛(wèi)星可與空間飛行器、地面節(jié)點進行通信，近地軌道衛(wèi)星鏈路會因為節(jié)點的運動而斷開，網(wǎng)絡(luò)切換頻繁，同步衛(wèi)星位于地球靜止軌道，通信延時相對較大?？臻g飛行器與低軌有相似的軌道，既可以作為傳輸節(jié)點，又可以作為終端節(jié)點。機載站和船載站隨機移動，沒有固定的軌跡。網(wǎng)絡(luò)拓?fù)淙鐖D1所示。

圖1 空間DTN拓?fù)?/p>

上述路由算法中，確定性路由算法沒有考慮到網(wǎng)絡(luò)節(jié)點的隨意移動性，隨機性路由算法消耗大量的網(wǎng)絡(luò)資源，不適應(yīng)空間DTN的應(yīng)用。

2 SRM算法設(shè)計

首先，計算衛(wèi)星節(jié)點與隨機節(jié)點間的報文遞交概率，構(gòu)建節(jié)點相遇概率信息表，查找出與隨機節(jié)點相遇概率最大的衛(wèi)星節(jié)點;然后由地面站周期性計算并分發(fā)全網(wǎng)衛(wèi)星及固定節(jié)點連接時序圖，網(wǎng)絡(luò)節(jié)點利用該連接圖構(gòu)建網(wǎng)絡(luò)拓?fù)渎酚杀恚⒊浞挚紤]網(wǎng)絡(luò)中業(yè)務(wù)的實時性要求，采用時延作為鏈路權(quán)值。

2．1 節(jié)點相遇概率信息表

節(jié)點相遇概率主要指的是無規(guī)則移動節(jié)點和衛(wèi)星節(jié)點間的相遇概率。顯然，當(dāng)節(jié)點相遇頻繁時，相遇概率會隨著時間不斷地增大，反之會不斷地減少，這能很好地體現(xiàn)節(jié)點之間的聯(lián)系程度。通過此相遇概率可以大體估算出節(jié)點未來的相遇情況，從而為消息的轉(zhuǎn)發(fā)提供依據(jù)。

當(dāng)衛(wèi)星節(jié)點與隨機移動節(jié)點相遇時，首先對幾個通信節(jié)點的節(jié)點相遇概率進行計算:

式中，r為中繼節(jié)點;d為目標(biāo)節(jié)點;β為一個常量。

如果在時間T內(nèi)，某個節(jié)點沒有與其他任何節(jié)點相遇并發(fā)生連接，那么報文遞交概率進行衰減:

式中，γ 為衰老因子，γ∈(0，1)。

網(wǎng)絡(luò)中每個衛(wèi)星節(jié)點都有一份與隨機節(jié)點的報文遞交概率的表格，具體格式如表1所示。

表1 報文遞交概率信息表

當(dāng)與同步衛(wèi)星接觸時，衛(wèi)星節(jié)點將報文遞交概率的表格發(fā)送給同步衛(wèi)星，同時同步衛(wèi)星將搜集到的最新的各個傳輸節(jié)點到達隨機移動節(jié)點的遞交概率信息發(fā)送給各個衛(wèi)星節(jié)點。

2．2 構(gòu)建網(wǎng)絡(luò)拓?fù)渎酚杀?/h3>

每個衛(wèi)星結(jié)點內(nèi)都存儲了在整個時間軸上所有衛(wèi)星結(jié)點及固定節(jié)點之間的鏈接信息。在搜索路徑時，節(jié)點并不會搜索整個時間軸上的鏈接，為節(jié)省搜索算法的時間，結(jié)點動態(tài)地維護鏈接信息圖，將搜索的鏈接對象盡量控制在消息生存期范圍內(nèi)。每個鏈接信息圖包含如下信息:發(fā)送節(jié)點、接收節(jié)點、開始時間、結(jié)束時間和傳輸速率。

當(dāng)大小為size的消息m抵達通信節(jié)點A后，查詢其到達的目的節(jié)點D，并按順序提出目的節(jié)點D的鏈接信息，具體搜索過程如圖2所示。

圖2 搜索過程示意

①如果C．st-size/rate大于當(dāng)前時間，則跳過C，選擇下一條鏈接信息。否則進行下一操作。

②如果C的傳輸節(jié)點E等于當(dāng)前節(jié)點A:如果剩余鏈路容量小于size，則選擇下一條鏈接信息;否則節(jié)點D就是信息m的下一跳節(jié)點，將A加入到可連接列表中，記錄其當(dāng)前的跳數(shù)及傳輸時間。

③如果C的傳輸節(jié)點E不等于當(dāng)前節(jié)點A，將E加入排除列表中，并按順序提出節(jié)點E的鏈接信息，重復(fù)進行①。

當(dāng)搜尋到所有的可到達的鏈路后，從中選擇延遲最小的鏈路進行傳輸，若延遲相同則選擇跳數(shù)最小的鏈路。

3 路由算法仿真及性能分析

為了評價算法的性能，將SRM算法與現(xiàn)有的DTN算法進行了比較，比較對象選擇了比較典型的Epidemic算法。為了比較路由策略，必須定義評價其性能參數(shù)。性能的評價要考慮很多因素，在此只討論報文到達率和網(wǎng)絡(luò)開銷2個方面。

3．1 報文到達率

從丟包率可以反映出算法的報文到達率，在Epidemic算法中由于轉(zhuǎn)發(fā)數(shù)據(jù)量過于龐大，而衛(wèi)星的存儲空間有限，導(dǎo)致很多數(shù)據(jù)被丟棄，因而造成了丟包。在SRM算法中丟包的原因主要是因為引進了概率性，數(shù)據(jù)包一直在網(wǎng)絡(luò)中傳遞，直到生存周期結(jié)束。由于在仿真中將衛(wèi)星的內(nèi)存空間設(shè)置為無限大，因此Epidemic算法的到達率要略好于SRM算法，如圖3所示。

圖3 Epidemic與SRM算法的到達率對比

3．2 網(wǎng)絡(luò)開銷

網(wǎng)絡(luò)開銷可通過源端發(fā)送報文的數(shù)量和接收到的重復(fù)報文的數(shù)量以及報文被轉(zhuǎn)發(fā)的次數(shù)進行比較，Epidemic算法基本上每個通信節(jié)點都進行了數(shù)據(jù)轉(zhuǎn)發(fā)，在路由擴散過程中，引起的資源、緩存、帶寬和能量消耗都比較大;而SRM算法在整個網(wǎng)絡(luò)中只存在一個報文，網(wǎng)絡(luò)開銷要比Epidemic小得多。網(wǎng)絡(luò)中信令的開銷遠遠小于重復(fù)報文數(shù)量的開銷，因此將信令開銷忽略不計。SRM算法的網(wǎng)絡(luò)開銷近似一個常數(shù)，而Epidemic算法由于要在每個節(jié)點都要復(fù)制一次信息，因此最多的重復(fù)信息量可以達到原始數(shù)量的5倍左右，如圖4所示。因此，SRM的網(wǎng)絡(luò)開銷要遠遠小于Epidemic。

圖4 Epidemic與SRM算法的網(wǎng)絡(luò)開銷對比

4 結(jié)束語

本文提出了一種適應(yīng)于空間DTN的路由算法，該算法通過計算概率信息和鏈路信息確定路由的下一跳節(jié)點，實現(xiàn)簡單。通過理論分析和仿真測試表明，與Epidemic算法相比，SRM算法在報文到達率略小的情況下，有著更小的網(wǎng)絡(luò)開銷，能夠更好地支持終端節(jié)點的移動性。

［1］ FALL Kevin Fall，F(xiàn)ARRELL Steven．DTN:An Architectural Retrospective［J］．IEEE Journal on Selected Areas in Communications，2008，25(5):828 －836．

［2］ FALL Kevin．A Delay Tolerant Network Architecture for Challenged Internets［C］∥Proceedings of the 2003 Conference on Applications Technologies Architectures and Protocols for Computer Communications，ACM Press，2003:27－34．

［3］ 林 闖，董楊威，單志廣．基于DTN的空間網(wǎng)絡(luò)互聯(lián)服務(wù)研究綜述［J］．計算機研究與發(fā)展，2014，51(5):931－943．

［4］ 郭金鵬．運動網(wǎng)絡(luò)使用DTN技術(shù)的分析與研究［J］．無線電通信技術(shù)，2012，38(6):77 －80．

［5］ 李 濤．容遲網(wǎng)絡(luò)中的路由算法的研究及比較［J］．計算機與網(wǎng)絡(luò)，2009(17):69－72．

［6］ JAIN S，F(xiàn)ALL K，PATRA R．Routing in a Delay Tolerant Network［J］．Proc of the ACM SIGCOMM 2009．Communications Rev，2009，12(7):44 －52．

［7］ 祁 彥．容遲網(wǎng)絡(luò)中的隨機路由算法研究［J］．?dāng)?shù)據(jù)通信，2008(5):28－30．

［8］ SEGUI J，JENNINGS E，BURLEIGH S．Enhancing Contact Graph Routing for Delay Tolerant Space Networking［C］∥Global Telecommunications Conference(GLOBECOM 2011)，IEEE，2011:1 －6．

［9］ FARRELL S．Endpoint Discovery and Contact Graph Routing in Space and Terrestrial DTNs［C］∥Advanced Satellite Multimedia Systems Conference(asma)and the 11th signal processing for space communications workshop(spsc)，2010:89 －93．

［10］ CAINI C，F(xiàn)IRRINCIELI R．Application of Contact Graph Routing to LEO satellite DTN Communications［C］∥Communications(ICC)．2012 IEEE International Conference on．IEEE，2012:3 301 －3 305．

［11］ NAIN D，PETIGARA N，BALAKRISHNAN H．Integrated Routing and Storage for Messaging Applications in Mobile Ad Hoc Networks［J］．Mobile Networks and Applications，2004，9(6):595 －604．

［12］ BALASUBRAMANIAN A，LEVINE B N，VENKATARAMANI A．DTN Routing as a Resource Allocation Problem［J］．Computer Networks，2009，21(4):65－70．