王鳴濤　周　詮　黃普明

摘 要：針對全網(wǎng)廣播路由導(dǎo)致系統(tǒng)利用率低的問題，結(jié)合衛(wèi)星通信網(wǎng)絡(luò)的周期性和準(zhǔn)確預(yù)知等特點(diǎn)，在源路由算法(SRA)的基礎(chǔ)上，引入方向性指導(dǎo)策略，提出了具有導(dǎo)向功能的源路由改進(jìn)算法(i-SRA)。由于采用部分廣播方式，僅向靠近目的節(jié)點(diǎn)的相鄰衛(wèi)星發(fā)送路由請求分組，降低了請求分組傳輸?shù)拿つ啃?。通過OPNET建模仿真，結(jié)果表明改進(jìn)算法減少了路由負(fù)載開銷，提高了資源利用率。

關(guān)鍵詞：LEO衛(wèi)星網(wǎng)絡(luò);導(dǎo)向策略;源路由;路由負(fù)載

中圖分類號：TN927文獻(xiàn)標(biāo)識碼：B

文章編號：1004-373X(2009)05-004-03

Improved Source Routing Algorithm with Directional Function for LEO Satellite Network

WANG Mingtao,ZHOU Quan,HUANG Puming

(National Key Laboratory,Xi′an Institute of Space Radio Technology,Xi′an,710000,China)

Abstract：Due to a low system usage of a route method which broadcasting in whole satellite networks,an improved approach adopting the directional strategy to the source routing algorithm in LEO satellite network is proposed,because the change of LEO satellite network is deterministic and can be predicted quite accurately.The strategy with partial broadcast forwards request route packets to satellites near the destination and the blind delivery of packets is reduced.In addition,the performance of the improved routing algorithm is evaluated by the OPNET modeling and simulation.The result shows that routing load is decreased and the utilized coefficient is raised.

Keywords：LEO satellite network;directional strategy;SRA;routing load

0 引 言

衛(wèi)星通信具有覆蓋地域廣、長距離傳輸和易實(shí)現(xiàn)廣播的特點(diǎn)，并且能夠支持多媒體通信業(yè)務(wù)，成為軍用和民用領(lǐng)域一種重要的通信手段。隨著星上處理能力的增強(qiáng)，在衛(wèi)星上采用路由交換技術(shù)已成為現(xiàn)代衛(wèi)星網(wǎng)絡(luò)發(fā)展的重要趨勢之一。

目前，針對星上路由算法的研究大多采用將系統(tǒng)周期分割或者將覆蓋區(qū)域分割的方法，屏蔽衛(wèi)星網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)的動態(tài)變化，在靜態(tài)拓?fù)浣Y(jié)構(gòu)下設(shè)計星上路由算法。

系統(tǒng)周期分割方法雖然離線計算星上路由，衛(wèi)星僅在時間分割點(diǎn)更新，對星上處理能力要求較低，但是不能根據(jù)鏈路的狀態(tài)實(shí)時地選擇路由，適應(yīng)性差，并且由于分割的拓?fù)淇煺仗?，?dǎo)致星上需要大量的存儲空間。

而覆蓋域分割方法卻根據(jù)分組的目的地理信息，在不同地面覆蓋劃分區(qū)域組成的靜態(tài)邏輯結(jié)構(gòu)上，依據(jù)路由策略和鏈路負(fù)載、故障、擁塞等情況實(shí)時計算路由，具有適應(yīng)能力強(qiáng)，所需存儲空間小，同時提供QoS保證的優(yōu)點(diǎn)，因而，覆蓋域分割類型的路由算法具有較強(qiáng)的優(yōu)勢，但由于星上處理能力和功耗的限制，該類算法較多的系統(tǒng)資源消耗需要盡量地減小。

類似IP網(wǎng)絡(luò)的衛(wèi)星網(wǎng)絡(luò)路由機(jī)制中，每顆衛(wèi)星保存整個衛(wèi)星網(wǎng)絡(luò)的拓?fù)鋱D，實(shí)時地根據(jù)星間鏈路狀態(tài)，將地面網(wǎng)關(guān)發(fā)送來的封裝數(shù)據(jù)轉(zhuǎn)發(fā)到目的衛(wèi)星節(jié)點(diǎn)，但文中未見采用的路由算法。Ekici等人提出的分布式路由算法中，每顆衛(wèi)星根據(jù)自身鏈路狀態(tài)局部信息，按照邏輯地址為每個分組獨(dú)立地選擇最小傳輸時延路徑。由于利用了衛(wèi)星網(wǎng)絡(luò)周期性和預(yù)知性的特點(diǎn)，路由開銷非常小，但是每個分組采用相同的操作獨(dú)立地路由轉(zhuǎn)發(fā)，不區(qū)分對待不同業(yè)務(wù)類型，因而不能提供不同的服務(wù)質(zhì)量。Admela J等設(shè)計的具有QoS保證的LEO網(wǎng)絡(luò)源路由算法(Source Routing Algorithm，SRA)，源節(jié)點(diǎn)廣播路由請求分組到目的節(jié)點(diǎn)，目的節(jié)點(diǎn)根據(jù)不同傳輸業(yè)務(wù)的不同服務(wù)要求，反饋相應(yīng)的最優(yōu)路徑。雖然能夠反映網(wǎng)絡(luò)狀態(tài)的變化，但是采用全網(wǎng)廣播路由致使開銷巨大。

本文結(jié)合衛(wèi)星網(wǎng)絡(luò)的特點(diǎn)，在LEO網(wǎng)絡(luò)SRA算法的基礎(chǔ)上，引入方向性指導(dǎo)策略，提出具有導(dǎo)向功能的源路由改進(jìn)算法(improved Source Routing Algorithm,i-SRA)，并對其進(jìn)行性能分析與仿真驗(yàn)證。

1 衛(wèi)星網(wǎng)絡(luò)的特點(diǎn)

由于衛(wèi)星快速移動，星間鏈路頻繁地切換，致使依靠不斷交換拓?fù)湫畔砭S護(hù)網(wǎng)絡(luò)路由的地面路由技術(shù)不能適用于衛(wèi)星網(wǎng)絡(luò)。與地面網(wǎng)絡(luò)相比，衛(wèi)星網(wǎng)絡(luò)有著其獨(dú)有的特點(diǎn)。

衛(wèi)星快速移動的影響 主要體現(xiàn)在：隨著衛(wèi)星的移動，軌道間的ISL長度不斷變化，越過極區(qū)時需要不斷開啟或關(guān)閉，導(dǎo)致衛(wèi)星網(wǎng)絡(luò)的拓?fù)浣Y(jié)構(gòu)是動態(tài)的；針對星間鏈路的不斷失效或生效，為保證通信路徑的暢通，需要不斷地進(jìn)行鏈路切換；星下點(diǎn)覆蓋域變化時，由于用戶業(yè)務(wù)地域分布不均勻，導(dǎo)致衛(wèi)星的通信量動態(tài)變化，極不均衡；由于衛(wèi)星的軌道是固定的，網(wǎng)絡(luò)拓?fù)涞淖兓哂兄芷谛浴㈩A(yù)知性。

衛(wèi)星功率和星上處理能力有限 由于衛(wèi)星通信環(huán)境的特殊性，星上設(shè)備的體積、功耗等都受到限制。路由選擇的處理過程越復(fù)雜，所需的星上處理能力就越強(qiáng)，消耗的功率越多，衛(wèi)星的壽命可能就會縮短。另外，一旦衛(wèi)星發(fā)射，所應(yīng)用的技術(shù)不能改進(jìn)升級，存儲和處理能力不能擴(kuò)展。

其他特點(diǎn) 衛(wèi)星網(wǎng)絡(luò)中，星間鏈路傳輸距離較遠(yuǎn)，衛(wèi)星軌道較高，衛(wèi)星通信具有非常大的延時，對網(wǎng)絡(luò)協(xié)議實(shí)現(xiàn)、高性能QoS服務(wù)等方面影響很大；衛(wèi)星網(wǎng)絡(luò)的節(jié)點(diǎn)數(shù)目通常是固定不變的；對星座網(wǎng)絡(luò)來說，其拓?fù)浣Y(jié)構(gòu)具有很高的規(guī)則性和均衡性，使得衛(wèi)星節(jié)點(diǎn)對之間存在許多可備選的通信鏈路。

星上路由算法與衛(wèi)星網(wǎng)絡(luò)的拓?fù)浣Y(jié)構(gòu)密切相關(guān)。雖然網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)動態(tài)變化為星上路由算法增加了設(shè)計難度，但也有簡便的一面?？梢猿浞掷眯l(wèi)星網(wǎng)絡(luò)的周期性和準(zhǔn)確預(yù)測性、規(guī)則性和均衡性、以及節(jié)點(diǎn)數(shù)目少且固定的特點(diǎn)，來簡化路由算法。

2 具有導(dǎo)向功能的源路由改進(jìn)算法i-SRA

2.1 源路由SRA算法

源路由SRA算法是由源節(jié)點(diǎn)衛(wèi)星發(fā)起的，目的節(jié)點(diǎn)衛(wèi)星決定路由的面向連接的按需路由算法，采用覆蓋域分割的策略來解決衛(wèi)星網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)的動態(tài)變化。對于每一次呼叫連接，SRA算法將路由請求分組全網(wǎng)廣播傳輸?shù)侥康墓?jié)點(diǎn)。在星間鏈路上傳輸?shù)耐瑫r，路由請求分組收集傳輸路徑上經(jīng)過衛(wèi)星節(jié)點(diǎn)的狀態(tài)信息。目的節(jié)點(diǎn)收到請求分組后，依據(jù)這些信息來決定最合適的路由。

2.2 全網(wǎng)廣播路由的局限性

由衛(wèi)星網(wǎng)絡(luò)特點(diǎn)可知，衛(wèi)星的移動性會增大路由算法設(shè)計的難度，但由于衛(wèi)星運(yùn)行的軌道和地球自傳速度是固定的，網(wǎng)絡(luò)節(jié)點(diǎn)數(shù)目不變且非常少，所以衛(wèi)星網(wǎng)絡(luò)拓?fù)涞淖兓谴_定的，能夠進(jìn)行準(zhǔn)確地預(yù)測。

但是采用全網(wǎng)廣播路由請求分組來建立最優(yōu)路徑的方式，未能結(jié)合衛(wèi)星網(wǎng)絡(luò)這些有利條件來優(yōu)化算法，仍向遠(yuǎn)離目的地址的衛(wèi)星節(jié)點(diǎn)發(fā)送大量的路由請求分組。然而這些請求分組因?yàn)槁酚商鴶?shù)過多，傳輸時延過長而被淘汰，結(jié)果該方向未形成最終的傳輸路徑。由于星上功率和處理能力有限且十分寶貴，采用全網(wǎng)廣播路由方式產(chǎn)生了過多無用的請求分組，導(dǎo)致網(wǎng)絡(luò)資源的浪費(fèi)。

2.3 改進(jìn)算法i-SRA

衛(wèi)星網(wǎng)絡(luò)具有周期性和預(yù)知性，源節(jié)點(diǎn)衛(wèi)星根據(jù)自己覆蓋區(qū)域的邏輯編號(例如由軌道號和軌內(nèi)衛(wèi)星編號組成)以及傳輸分組包含的目的邏輯區(qū)域的邏輯編號，就可以得到目的節(jié)點(diǎn)的當(dāng)前方位，估計傳輸路徑所需的最小路由跳數(shù)。源節(jié)點(diǎn)根據(jù)這些先驗(yàn)信息，來定向地路由或直接轉(zhuǎn)發(fā)分組。這一特性就是方向性指導(dǎo)策略，可以用來簡化路由算法的復(fù)雜性以及減小路由開銷。

i-SRA算法就是采用方向性指導(dǎo)策略，對LEO網(wǎng)絡(luò)源路由SRA算法進(jìn)行改進(jìn)，以期降低路由算法的網(wǎng)絡(luò)開銷，提高資源利用率。

具有導(dǎo)向功能的源路由改進(jìn)算法i-SRA的基本思想是：基于源路由SRA算法，根據(jù)方向性指導(dǎo)策略，對每次呼叫連接的路由請求分組以部分廣播的形式傳輸。所謂的部分廣播，就是在預(yù)知目的節(jié)點(diǎn)具體方位后，只將請求分組傳播到那些與目的節(jié)點(diǎn)方向一致的星間鏈路上。也就是說，如果目的節(jié)點(diǎn)在東南方向，請求分組就不會被發(fā)送到通向西北方向的星間鏈路上。

具體算法描述如下：

Step 1：需要與遠(yuǎn)程目的用戶D通信的源用戶S向覆蓋域內(nèi)過頂時間最長的衛(wèi)星Sat-S發(fā)送呼叫請求；

Step 2：源衛(wèi)星節(jié)點(diǎn)Sat-S根據(jù)接收的呼叫請求，判斷目的用戶所在的邏輯覆蓋區(qū)域以及具體方位，并依據(jù)呼叫請求的業(yè)務(wù)類型產(chǎn)生具有特定要求的路由連接請求；

Step 3：根據(jù)目的節(jié)點(diǎn)的方位，按照導(dǎo)向策略，選擇同方向能夠滿足設(shè)定要求的星間鏈路；

Step 4：源衛(wèi)星節(jié)點(diǎn)Sat-S將路由請求分組在已選鏈路ISL上傳輸，轉(zhuǎn)發(fā)給相鄰衛(wèi)星節(jié)點(diǎn)，然后這些衛(wèi)星節(jié)點(diǎn)以相同的方式將請求分組轉(zhuǎn)發(fā)到其他相鄰衛(wèi)星，直至到達(dá)目的用戶所在邏輯區(qū)域上空的目的衛(wèi)星節(jié)點(diǎn)Sat-D；

Step 5：目的節(jié)點(diǎn)衛(wèi)星Sat-D通知目的用戶D有呼叫到達(dá)，并且在到達(dá)的多條候選鏈路中，選擇滿足呼叫業(yè)務(wù)要求(比如最小跳數(shù))且最長壽命時間的鏈路作為最終的傳輸路徑；

Step 6：Sat-D衛(wèi)星沿著選擇的路徑，向Sat-S衛(wèi)星反饋路由信息分組，同時獲得通信資源的預(yù)留。當(dāng)源衛(wèi)星節(jié)點(diǎn)Sat-S獲得該路由信息分組時，該通信鏈路就成功建立了。源用戶S開始向目的用戶D傳輸數(shù)據(jù)；

Step 7：已建立通信鏈路的壽命時間到達(dá)時，如果通信業(yè)務(wù)還未結(jié)束，回到Step 3，提前重新路由，并進(jìn)行鏈路的切換。

2.4 i-SRA算法性能分析

改進(jìn)算法i-SRA采用部分廣播的方式，只將路由請求分組傳播到與目的節(jié)點(diǎn)方向一致的星間鏈路上，沒有在全網(wǎng)上傳輸。雖然與目的節(jié)點(diǎn)方向相反鏈路上傳輸?shù)恼埱蠓纸M最終也可能到達(dá)目的節(jié)點(diǎn)，但是由于星間鏈路延時本身就比較大，其經(jīng)歷的衛(wèi)星節(jié)點(diǎn)又很多，結(jié)果獲得傳輸路徑的延時非常大，在眾多候選路徑中最終也會被淘汰。

所以，i-SRA算法利用了網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)的可預(yù)知性，減少請求分組傳播的盲目性，不產(chǎn)生這些易被淘汰的路徑，從源頭上減少網(wǎng)絡(luò)中路由請求分組的傳輸數(shù)量，節(jié)約了處理這些分組所耗費(fèi)的星上功率，提高了網(wǎng)絡(luò)資源的利用率。

3 仿真驗(yàn)證

使用STK軟件構(gòu)建了參數(shù)T/P/F為30/5/0(其中表示衛(wèi)星數(shù)目為30顆，軌道數(shù)目為5，相位因子為0)的LEO圓形極軌walker星座，如圖1所示。網(wǎng)絡(luò)中衛(wèi)星軌道高度為1 375 km，軌道傾角為84.7°。并且采用OPNET網(wǎng)絡(luò)分析工具仿真了LEO衛(wèi)星網(wǎng)絡(luò)運(yùn)行12 h期間路由負(fù)載的情況。

如圖2所示為LEO網(wǎng)絡(luò)源路由SRA算法和改進(jìn)算法i-SRA的平均路由負(fù)載結(jié)果。源路由算法SRA每次路由的平均負(fù)載大約為11個路由請求分組，而i-SRA算法大約為8個路由請求分組。相比之下，i-SRA算法將路由選擇的請求分組數(shù)量降低了近27.3%，減少了多余的無用分組。

通過仿真表明，采用方向指導(dǎo)策略后的i-SRA算法相比源路由SRA算法確實(shí)能夠降低建立傳輸路徑所需要的路由開銷，提高網(wǎng)絡(luò)資源利用率。

4 結(jié) 語

根據(jù)衛(wèi)星網(wǎng)絡(luò)周期性和預(yù)知性的特點(diǎn)，針對LEO網(wǎng)絡(luò)源路由算法SRA采用全網(wǎng)廣播路由方式導(dǎo)致系統(tǒng)開銷大的缺陷，結(jié)合方向性指導(dǎo)策略，提出了具有導(dǎo)向功能的星上源路由改進(jìn)算法i-SRA。由于減小了路由請求分組傳輸?shù)拿つ啃?，i-SRA算法從源頭上降低了衛(wèi)星網(wǎng)絡(luò)中建立通信路徑所需的請求分組傳播數(shù)量，節(jié)約了星上處理資源。

在OPNET平臺上建立了Walker圓形極軌衛(wèi)星網(wǎng)絡(luò)，并對改進(jìn)算法的性能進(jìn)行了分析驗(yàn)證。仿真結(jié)果表明，改進(jìn)的i-SRA算法相比源路由SRA算法能夠在很大程度上減少路由開銷，提高衛(wèi)星網(wǎng)絡(luò)資源的利用率。

參考文獻(xiàn)

［1］Alagoz F,Korcak D,Jamalipour A.Exploring the Routing Strategies in Next-Generation Satellite Networks［J］.IEEE Wireless Communications,2007,14(3):79-88.

［2］Chang S,Kim W.FSA-based Link Assignment and Routing in Low-earth Orbit Satellite Networks［J］.IEEE Trans.on Vehicular Technology,1998,47(3):1 037-1 048.

［3］Vidyashankar V Gounder,Ravi Prakash,Hosame Abu Amara.Routing in LEO-based Satellite Networks［J］.Proceedings of IEEE Emerging Technologies Symp:Wireless Communications and Systems,1999.

［4］Hashimoto Y.Design of IP-based Routing in a LEO Satellite Network［J］.Proceedings of the 3rd International Workshop on Satellite-based Information Services,Dallas,1998:81-88.

［5］Wood L.IP Routing Issues in Satellite Constellation Networks［J］.International Journal of Satellite Networks,2001,19(1):69-92

［6］Ekici E,Akyildiz I F,Bender M D.A Distributed Routing Algorithm for Datagram Traffic in LEO Satellite Networks［J］.IEEE/ACM Trans.on Networking,2001,9(2):137-147.

［7］Admela J,Hoang N N,Harmen R.An Approach to QoS-based Routing for LEO Satellite Networks［J］.Communication Technology Proceedings,2000,WCC-ICCT:922-929.

作者簡介 王鳴濤 男，1984年出生，碩士研究生。主要研究方向?yàn)樾l(wèi)星數(shù)據(jù)傳輸與處理。

周 詮 男，1965年出生，博士、研究員、博士生導(dǎo)師。主要研究方向?yàn)樾l(wèi)星數(shù)據(jù)傳輸與處理、航天器通信技術(shù)。

黃普明 男，1971年出生，博士、研究員、碩士生導(dǎo)師。主要研究方向?yàn)樾l(wèi)星數(shù)據(jù)傳輸與處理、航天器通信技術(shù)。