王幫元，宋　杰，周偉良

?

按需機制的高效低時延LEO衛(wèi)星網(wǎng)絡(luò)路由算法*

王幫元1+，宋杰2，周偉良1

1.安徽經(jīng)濟管理學(xué)院信息工程系，合肥230031
2.安徽大學(xué)計算機學(xué)院，合肥230601

ISSN 1673-9418 CODEN JKYTA8

Journal of Frontiers of Computer Science and Technology 1673-9418/2016/10(05)-0667-11

http://www.ceaj.org Tel: +86-10-89056056

* The National Social Science Foundation of China under Grant No. 13BTQ048 (國家社會科學(xué)基金); the Natural Science Research Program of Higher Education of Anhui Province under Grant No. KJ2015A394 (安徽省高校自然科學(xué)研究重點項目).

Received 2015-07,Accepted 2015-09.

CNKI網(wǎng)絡(luò)優(yōu)先出版: 2015-10-16, http://www.cnki.net/kcms/detail/11.5602.TP.20151016.1100.002.htm l

WANG Bangyuan, SONG Jie, ZHOU Weiliang. Efficient low-delay routing algorithm for LEO satellite networks based on on-dem and m echanism. Journal of Frontiers of Com puter Science and Technology, 2016, 10 (5)：667-677.

摘要：針對按需LEO（low earth orbit）衛(wèi)星網(wǎng)絡(luò)路由算法存在冗余控制開銷，未充分利用新建路徑有效信息完成后續(xù)路徑建立等問題，提出了基于按需機制的高效低時延LEO衛(wèi)星網(wǎng)絡(luò)路由算法EIORA（efficient improved on-demand routing algorithm）。該算法充分利用源衛(wèi)星與目的衛(wèi)星發(fā)送的控制分組，減少尋路的控制開銷，增加路由更新的廣泛性；采用RREP（route reply）分組免疫機制，中間衛(wèi)星收到RREP分組后若收到對應(yīng)的RREQ （route request）分組，則丟棄該RREQ分組，以減小網(wǎng)絡(luò)控制開銷；增加中間衛(wèi)星代替目的衛(wèi)星回復(fù)應(yīng)答的幾率，縮短路徑建立時間。仿真結(jié)果表明，與LAOR算法相比，該算法在減緩星地之間的控制開銷與端到端時延，以及提升傳輸效率上有明顯的改善。

關(guān)鍵詞：LEO衛(wèi)星；分組導(dǎo)航；反饋應(yīng)答；按需尋路

1 引言

LEO（low earth orbit）衛(wèi)星網(wǎng)絡(luò)[1-2]是由運轉(zhuǎn)于若干軌道的多顆衛(wèi)星構(gòu)成的網(wǎng)絡(luò)，以衛(wèi)星為網(wǎng)絡(luò)節(jié)點，衛(wèi)星之間通過星際鏈路（inter orbit links，IOL）互連而構(gòu)成的空間無線網(wǎng)絡(luò)。該網(wǎng)絡(luò)以空間資源最大有效利用為原則，通過衛(wèi)星轉(zhuǎn)發(fā)或反射空間電磁波來實現(xiàn)地球表面兩地的數(shù)據(jù)傳輸。LEO衛(wèi)星網(wǎng)絡(luò)的拓撲一直都在快速變化，并且這種變化又具有規(guī)律性，這是LEO衛(wèi)星網(wǎng)絡(luò)區(qū)別于地面自組織網(wǎng)絡(luò)的主要特點[3]。

Zhang等人[4]較早提出了基于LEO衛(wèi)星網(wǎng)絡(luò)拓撲結(jié)構(gòu)的路由算法。該算法采用ATM面向連接服務(wù)機制，主要分為兩個階段：虛擬拓撲結(jié)構(gòu)建立階段和路由選擇優(yōu)化階段。該算法最先提出了將持續(xù)動態(tài)變化的LEO衛(wèi)星網(wǎng)絡(luò)拓撲進行離散化處理，表示為一組靜態(tài)拓撲集合的思想，這一思想為后續(xù)算法奠定了基礎(chǔ)。但是該算法并沒有考慮解決由于星際鏈路切換而引起的路徑重選問題。Wang等人[5]提出了一種以網(wǎng)絡(luò)拓撲結(jié)構(gòu)和網(wǎng)絡(luò)流量為依據(jù)，從鏈路分配的角度來解決路由問題的LEO衛(wèi)星網(wǎng)絡(luò)路由算法。該算法設(shè)計目標(biāo)是通過鏈路的最優(yōu)化分配，降低整個衛(wèi)星網(wǎng)絡(luò)的業(yè)務(wù)負擔(dān)，提高網(wǎng)絡(luò)的吞吐量。但該算法選擇的路徑不一定是最短的，且算法的計算量太大，對于采用宇航級設(shè)備的衛(wèi)星是一種挑戰(zhàn)。Mohorcic等人[6]提出了一種基于面向連接的LEO衛(wèi)星網(wǎng)絡(luò)路由算法。該算法定義了LEO衛(wèi)星網(wǎng)絡(luò)中“快照”的概念，即在某一時刻LEO衛(wèi)星網(wǎng)絡(luò)的拓撲結(jié)構(gòu)。當(dāng)網(wǎng)絡(luò)中一個新的星際鏈路建立或者原有的星際鏈路斷開時，該算法則認為是一個新的快照形成。由于相鄰快照之間的差異較小，這樣就導(dǎo)致了衛(wèi)星節(jié)點需要存儲大量快照，對衛(wèi)星的存儲能力是一個挑戰(zhàn)。Peng等人[7]提出了一種緊湊的多路徑路由算法。該算法主要包括3個階段：鏈路狀態(tài)收集階段，路由計算階段和維護及流量分配階段。該算法中每顆衛(wèi)星節(jié)點都需要監(jiān)測自己緩存隊列中數(shù)據(jù)分組的數(shù)量，通過這種方式來估算數(shù)據(jù)分組的排隊時延。Papapetrou等人[8]將地面無線自組織網(wǎng)絡(luò)中的按需思想引入到LEO衛(wèi)星網(wǎng)絡(luò)中，提出了一種新的路由算法。該算法的設(shè)計目的是最小化端到端時延以及時延抖動，同時將控制開銷降到最低。Yuan等人[9]提出使用雙層衛(wèi)星網(wǎng)絡(luò)優(yōu)化數(shù)據(jù)分發(fā)，從而減少數(shù)據(jù)包在尋路過程中的延遲問題，提高數(shù)據(jù)及時性，實驗結(jié)果驗證了其技術(shù)的有效性。Gao等人[10]提出通過流量預(yù)測來分析數(shù)據(jù)擁塞情況，作為數(shù)據(jù)傳輸時的考量依據(jù)，選擇相對時延低的路徑分發(fā)消息，測試結(jié)果表明該方法能夠在一定程度上降低時延。Tsai等人提出的LAOR（lightweight ad hoc on-demand routing）算法[11]是將地面無線自組織網(wǎng)絡(luò)中的按需思想引入到LEO衛(wèi)星網(wǎng)絡(luò)中而形成的一種新的路由算法。該算法的設(shè)計目的是最小化端到端時延以及時延抖動，同時降低控制開銷，是一種比較典型常用的LEO衛(wèi)星網(wǎng)絡(luò)算法。

本文結(jié)合LEO衛(wèi)星網(wǎng)絡(luò)的特點，針對LAOR算法路徑更新以及控制開銷等方面存在的問題，提出了基于按需機制的高效低時延LEO衛(wèi)星網(wǎng)絡(luò)路由算法EIORA（efficient improved on-demand routing algorithm）。EIORA算法優(yōu)化了源衛(wèi)星節(jié)點到目的衛(wèi)星節(jié)點間路徑更新操作，以滿足衛(wèi)星拓撲動態(tài)變化特性，提高路由時效性；設(shè)計了RREP分組免疫機制以降低冗余的控制開銷；優(yōu)化了中間衛(wèi)星節(jié)點代替目的衛(wèi)星節(jié)點回復(fù)RREQ請求分組操作，以降低端到端時延；刪除了RREQ分組中存在的冗余字段，降低存儲開銷。

2 網(wǎng)絡(luò)模型

本文采用具有星際鏈路的近極地星座為網(wǎng)絡(luò)場景，在該星座系統(tǒng)中每顆衛(wèi)星節(jié)點設(shè)計有4條星際鏈路，即2條軌道間星際鏈路和2條軌道內(nèi)星際鏈路[11]，如圖1所示。

Fig.1 Typical polar constellation圖1 典型極地星座

在本文提出的EIORA算法中，衛(wèi)星網(wǎng)絡(luò)被抽象看作一個無向圖G(V, E)，其中V表示衛(wèi)星節(jié)點，E表示星際鏈路，V=N×M。每一顆衛(wèi)星都由一個唯一的虛擬坐標(biāo)(x, y)與之對應(yīng)，其中x表示當(dāng)前衛(wèi)星所處的軌道平面，y表示當(dāng)前衛(wèi)星所在該平面的位置，可知x∈[0, N)，y∈[0, M)。

EIORA算法假設(shè)不存在反向鏈路，使得G(V, E)類似格狀網(wǎng)絡(luò)，如圖2所示。

在EIORA算法中，認為星際鏈路的負載在上下行兩個方向上是不同的。

Fig.2 Result of a typical polar constellation圖2 典型極地星座的結(jié)果圖

3 EIORA算法

本文通過對目前比較經(jīng)典的應(yīng)用較廣泛的LEO衛(wèi)星網(wǎng)絡(luò)路由算法LAOR進行研究發(fā)現(xiàn)，該算法存在以下問題：

（1）在一次路徑發(fā)現(xiàn)過程中，LAOR算法RREP分組只記錄目的衛(wèi)星地址，完成中間衛(wèi)星和源衛(wèi)星到目的衛(wèi)星的路徑更新，對于網(wǎng)絡(luò)拓撲頻繁變化的衛(wèi)星網(wǎng)絡(luò)，路由更新的廣泛性較差。

（2）當(dāng)RREQ分組到達目的衛(wèi)星后，網(wǎng)絡(luò)中存在中間衛(wèi)星不知道目的衛(wèi)星是否已經(jīng)收到該RREQ分組，因此這些中間衛(wèi)星會繼續(xù)廣播該RREQ分組副本，從而導(dǎo)致不必要的控制開銷。

（3）中間衛(wèi)星是可以代替目的衛(wèi)星回復(fù)RREQ請求分組的，但LAOR算法沒有考慮到這一點，導(dǎo)致部分路徑建立時間過長，端到端時延較大。

（4）RREQ分組長度上存在冗余。

針對上述不足，本文提出了一種按需機制的高效低時延LEO衛(wèi)星網(wǎng)絡(luò)路由算法EIORA。通過有效利用源節(jié)點與目的節(jié)點間發(fā)送的控制消息，利用中間衛(wèi)星節(jié)點代替回復(fù)控制消息，可以縮短路徑建立時間，進而提高路徑更新的廣泛性，使源節(jié)點到目的節(jié)點間的路徑保持有效，降低端到端時延；同時，依據(jù)RREP分組免疫機制，目的衛(wèi)星節(jié)點收到RREQ分組后生成RREP分組，此時RREP分組記錄目的衛(wèi)星節(jié)點和其上一跳衛(wèi)星節(jié)點的地址，然后目的衛(wèi)星節(jié)點在一跳范圍內(nèi)廣播該RREP分組，中間衛(wèi)星節(jié)點收到RREP分組后，查詢該RREP分組記錄的最后的衛(wèi)星節(jié)點地址是否為自己，如果不是，則丟棄該RREP分組，不再進行轉(zhuǎn)發(fā)，達到減小控制開銷的目的。下面將詳細分析本文提出的EIORA算法原理。

3.1路徑更新

建立源衛(wèi)星節(jié)點到目的衛(wèi)星節(jié)點間路徑的過程中，源衛(wèi)星節(jié)點生成RREQ分組，用以記錄目的衛(wèi)星節(jié)點地址、源衛(wèi)星節(jié)點地址以及經(jīng)過節(jié)點的跳數(shù)等信息[8]。RREQ分組到達目的衛(wèi)星后，目的衛(wèi)星生成相應(yīng)的RREP分組，RREP分組記錄目的衛(wèi)星的地址，隨后按照原路徑返回，在返回的過程中依次完成中間衛(wèi)星節(jié)點和源衛(wèi)星節(jié)點到目的衛(wèi)星節(jié)點的路徑更新[12-14]。本文提出的EIORA算法RREP分組除記錄目的衛(wèi)星地址外，還記錄其經(jīng)過的中間衛(wèi)星地址，完成中間衛(wèi)星和源衛(wèi)星到目的衛(wèi)星的路由更新以及RREP分組后續(xù)經(jīng)過的衛(wèi)星節(jié)點對前面經(jīng)過的衛(wèi)星節(jié)點的路由更新，在一次尋路過程中完成了更多路由的更新，提高了路由表的實效性，以滿足衛(wèi)星拓撲的動態(tài)特性。

由于RREP分組需要記錄經(jīng)過的中間衛(wèi)星地址，與LAOR算法相比，EIORA算法中的RREP分組的長度勢必要增加，這將導(dǎo)致控制開銷的增加。首先給出一個引理。

引理EIORA算法在一次尋路中的控制開銷要小于LAOR算法。

Fig.3 Rectangle request area圖3 矩形請求區(qū)域

證明如圖3所示，在一個形成的矩形請求區(qū)域內(nèi)，除目的衛(wèi)星節(jié)點外，區(qū)域內(nèi)所有衛(wèi)星節(jié)點都需要生成RREQ分組或分組副本。假設(shè)請求區(qū)域內(nèi)衛(wèi)星節(jié)點個數(shù)為N，那么生成RREQ分組的衛(wèi)星節(jié)點個數(shù)為N-1。EIORA算法中的RREP分組記錄的衛(wèi)星節(jié)點地址是請求區(qū)域內(nèi)除源衛(wèi)星節(jié)點外的部分衛(wèi)星節(jié)點，假設(shè)個數(shù)為M，算法在一次尋路過程中建立的是單路徑路由，因此會有。研究發(fā)現(xiàn)，在LAOR算法中RREQ分組的pkt_src_seqnum字段和記錄衛(wèi)星節(jié)點地址的字段pkt_src長度相同，假設(shè)為a，則EIORA算法增加的開銷為(M-1)×a，由于刪除冗余字段，RREQ分組減少的開銷為(N-1)×a，可知M≤N-1，則(M-1)×a<(N-1)×a，從而EIORA算法在一次尋路中的控制開銷要小于LAOR算法。因此EIOR算法在不增加開銷的情況下，提高了路由更新的廣泛性，更加適合衛(wèi)星拓撲的動態(tài)變化?！?/p>

EIORA算法RREP分組和RREQ分組格式如圖4和圖5所示。

Fig.4 RREQ packet format圖4 RREQ分組格式

Fig.5 RREP packet format圖5 RREP分組格式

3.2 RREP分組免疫機制

EIORA算法中，目的衛(wèi)星節(jié)點收到RREQ分組后生成RREP分組，此時RREP分組記錄目的衛(wèi)星節(jié)點和其上一跳衛(wèi)星節(jié)點的地址，然后目的衛(wèi)星節(jié)點在一跳范圍內(nèi)廣播該RREP分組。中間衛(wèi)星節(jié)點收到RREP分組后，查詢該RREP分組記錄的最后的衛(wèi)星節(jié)點地址是否為自己，如果不是，則丟棄該RREP分組，不再進行轉(zhuǎn)發(fā)[14]。中間衛(wèi)星節(jié)點記錄RREP分組的格式如圖6所示。

Fig.6 Intermediate satellite node RREP packet format圖6 中間衛(wèi)星節(jié)點RREP分組格式

圖6中，dst表示生成RREP分組的目的衛(wèi)星節(jié)點地址，src表示生成RREP分組的源衛(wèi)星節(jié)點地址，timestamp等于該RREP分組對應(yīng)的RREQ分組生成的時間。

當(dāng)中間衛(wèi)星節(jié)點收到RREQ分組并轉(zhuǎn)發(fā)該RREQ分組前，獲取RREQ分組中pkt_src字段、pkt_dst字段和pkt_timestamp字段的值。檢查當(dāng)前衛(wèi)星節(jié)點記錄RREP分組的表中是否存在同時滿足式（1）、式（2）、式（3）的情況：

僅當(dāng)不存在滿足的表項時，該中間衛(wèi)星節(jié)點才繼續(xù)廣播該RREQ分組。

3.3 RREQ分組代替回復(fù)機制

在LAOR算法中，源衛(wèi)星節(jié)點生成請求分組RREQ進行尋路，當(dāng)源衛(wèi)星節(jié)點收到目的衛(wèi)星節(jié)點回復(fù)自己的RREP分組時，源衛(wèi)星節(jié)點的路由表項中rt_owner字段值置為1，此次尋路中RREP分組經(jīng)過的中間衛(wèi)星節(jié)點的路由表中rt_owner置為0。rt_ owne r置1表示當(dāng)前衛(wèi)星節(jié)點有可能代替目的衛(wèi)星節(jié)點回復(fù)其他衛(wèi)星節(jié)點的RREQ請求分組，因此在LAOR算法中，在一次尋路過程中只有源衛(wèi)星節(jié)點有可能在下一次尋路中代替目的衛(wèi)星節(jié)點回復(fù)其他衛(wèi)星節(jié)點的RREQ請求分組。但研究發(fā)現(xiàn)，rt_owner置1的條件是衛(wèi)星節(jié)點路由表中rt_path_cost和rt_path_ expiration_time為有效值，這兩個字段分別代表當(dāng)前衛(wèi)星節(jié)點到目的衛(wèi)星節(jié)點的代價值和路徑生存時間。當(dāng)衛(wèi)星間傳輸鏈路建立之后，中間衛(wèi)星節(jié)點通過收到的RREQ分組計算出源衛(wèi)星到該中間衛(wèi)星的代價值cost，進而與源衛(wèi)星到目的衛(wèi)星的總代價pkt_path_ cost相比較，當(dāng)rt_path_cost小于pkt_path_ cost與cost的差值，且路徑生存時間字段rt_path_expiration_time在生命周期內(nèi)時，中間衛(wèi)星節(jié)點的rt_owner字段滿足置1的條件，即可以代替源節(jié)點回復(fù)其他衛(wèi)星節(jié)點的RREQ請求分組，這樣就可以在一定程度上縮短路徑建立時間，優(yōu)化路徑建立過程。在一次尋路過程中，部分中間衛(wèi)星節(jié)點可以通過計算，獲得到目的衛(wèi)星節(jié)點的有效rt_path_cost和rtpath_expiration_ time值。在EIORA算法中，中間衛(wèi)星節(jié)點記錄最近收到的RREQ分組，記錄RREQ分組的格式如圖7所示。

Fig.7 Intermediate satellite node RREQ packet format圖7 中間衛(wèi)星節(jié)點RREQ分組格式

圖7中，cost、timestamp、dst、src依次表示中間傳輸代價、分組生命周期、目的衛(wèi)星地址、源衛(wèi)星地址[14]。如果記錄RREQ分組的表中存在同時滿足式（4）、式（5）、式（6）的表項：

則該衛(wèi)星節(jié)點到目的衛(wèi)星節(jié)點rt_path_cost字段和rt_path_expiration_time字段的有效值可以通過式（7）和式（8）進行計算：

其中，pkt_path_cost為源衛(wèi)星節(jié)點到目的衛(wèi)星節(jié)點的總代價；reqt_cost為源衛(wèi)星節(jié)點到該中間衛(wèi)星節(jié)點的代價，此時中間衛(wèi)星節(jié)點rt_owner字段可以置1，當(dāng)前中間衛(wèi)星節(jié)點在下次尋路中有可能代替目的衛(wèi)星節(jié)點回復(fù)其他衛(wèi)星節(jié)點的請求分組RREQ，這樣可以增加中間衛(wèi)星節(jié)點回復(fù)RREP的概率，縮短路徑建立時間。

3.4 EIORA算法操作

EIORA算法操作步驟如下。

步驟1源衛(wèi)星節(jié)點啟動形成請求區(qū)域進程，將路由選擇開銷保持在最低限度，具體操作如下：

當(dāng)衛(wèi)星節(jié)點與地面終端建立連接，第一個數(shù)據(jù)分組到達后，服務(wù)該終端的衛(wèi)星節(jié)點啟動形成請求區(qū)域進程，利用LEO衛(wèi)星網(wǎng)絡(luò)拓撲的規(guī)則性，盡可能地縮小控制分組的廣播區(qū)域范圍，達到將網(wǎng)絡(luò)開銷降低到最低的目的。該方法的理論基礎(chǔ)是，對于任意一對端衛(wèi)星節(jié)點，基于傳輸延時的最短路徑原則，由源衛(wèi)星節(jié)點與目的衛(wèi)星節(jié)點確定的最小矩形區(qū)域，稱為最小路由請求區(qū)域，如圖8和圖9所示。

Fig.8 Request area A圖8 請求區(qū)域A

Fig.9 Request area B圖9 請求區(qū)域B

步驟2源衛(wèi)星節(jié)點廣播RREQ分組進行尋路。中間衛(wèi)星節(jié)點收到RREQ分組后判斷自己是不是該RREQ分組的目的衛(wèi)星節(jié)點。如果是，則生成RREP分組，并在自身的一跳范圍內(nèi)廣播該RREP分組。如果不是，中間衛(wèi)星節(jié)點判斷自己是否有到目的衛(wèi)星節(jié)點的有效路徑。若有，中間衛(wèi)星節(jié)點則代替目的衛(wèi)星節(jié)點回復(fù)RREP分組，并在自身的一跳范圍內(nèi)廣播該RREP分組。如果沒有，中間衛(wèi)星節(jié)點則查詢自己是否存儲有該RREQ分組對應(yīng)的RREP分組。如果已經(jīng)存儲該RREP分組，則丟棄該RREQ分組。如果沒有則記錄該RREQ分組，然后向其鄰居衛(wèi)星節(jié)點轉(zhuǎn)發(fā)該RREQ分組。鄰居衛(wèi)星節(jié)點的虛擬坐標(biāo)應(yīng)滿足：

或者

步驟3 RREP分組在按照原路徑返回過程中，中間衛(wèi)星節(jié)點收到該RREP分組，更新該中間衛(wèi)星節(jié)點到RREP分組記錄的所有衛(wèi)星節(jié)點的路徑，然后判斷自己是否存有對應(yīng)的RREQ分組，如果有則將rt_ owner置為1，沒有則置為0。

步驟4源衛(wèi)星收到RREP分組，建立路徑并發(fā)送數(shù)據(jù)。

EIORA算法操作流程如圖10所示。

4 仿真和性能分析

4.1仿真環(huán)境設(shè)置

LAOR算法是當(dāng)前最小化LEO衛(wèi)星網(wǎng)絡(luò)端到端時延與時延抖動，同時降低控制開銷的常用方法，具有代表性。LAOR算法主要由3部分組成：形成請求區(qū)域，路徑發(fā)現(xiàn)和路由入口管理。但由于LEO衛(wèi)星網(wǎng)絡(luò)具有的一些特點，如網(wǎng)絡(luò)拓撲的動態(tài)變化性，星際鏈路的高時延，這些都會影響到路由發(fā)現(xiàn)信息的時效性，可能會導(dǎo)致出現(xiàn)剛剛尋找到的路徑由于軌道間星際鏈路關(guān)閉而失效的情況。故本文算法對LAOR算法進行改進。本文考慮在仿真環(huán)境以及具體參數(shù)上與LAOR算法存在一定的對比性，在結(jié)果分析上可以更能說明本文算法的有效性。鑒于與其他算法在原理以及仿真環(huán)境上的差異性，本文僅采用LAOR算法作為對比算法。

采用Opnet網(wǎng)絡(luò)仿真軟件[15]，仿真中wmin設(shè)為1，保證在路徑形成的矩形區(qū)域內(nèi)至少存在一條軌道間星際鏈路。仿真過程中，每一個衛(wèi)星節(jié)點任意選擇一個目的衛(wèi)星節(jié)點，并以某一傳輸比特率發(fā)送數(shù)據(jù)包。仿真選取不同的隨機種子，仿真數(shù)據(jù)取平均值。

衛(wèi)星網(wǎng)絡(luò)主要的仿真參數(shù)如表1所示。

Fig.10 EIORA operation process圖10 EIORA算法操作流程

Table 1 EIORA simulation parameters表1 EIORA仿真參數(shù)

業(yè)務(wù)產(chǎn)生參數(shù)如表2所示。

Table 2 Business generating parameters表2 業(yè)務(wù)產(chǎn)生參數(shù)

4.2仿真統(tǒng)計量

（1）歸一化網(wǎng)絡(luò)開銷，每發(fā)送一定數(shù)據(jù)所需要的控制分組的長度，計算公式為：

式中，PC為所有控制分組的總比特數(shù)；PD為所有到達目的節(jié)點的數(shù)據(jù)分組的比特數(shù)[12]。

（2）平均端到端時延，到達目的節(jié)點的所有數(shù)據(jù)分組的平均時延[12]，計算公式為：

式中，Ti表示第i個到達目的節(jié)點的分組的時延；D表示所有正確接收的分組個數(shù)。

（3）時延抖動，連續(xù)到達目的節(jié)點的數(shù)據(jù)包的時延平均值，計算公式為：

式中，Tjmax表示第j個數(shù)據(jù)流中最大分組端到端時延；Tjmin表示第j個數(shù)據(jù)流中最小分組端到端時延；M表示數(shù)據(jù)流總數(shù)。

在模型（15）～（16）中，i、j表示網(wǎng)絡(luò)中生成的數(shù)據(jù)包的個數(shù)，通過網(wǎng)絡(luò)仿真時間以及數(shù)據(jù)包生成時間可以計算得出，實際值可以通過仿真參數(shù)計算得到。

（4）成功率，正確接收到的分組數(shù)與發(fā)送的分組總數(shù)之間的比值，計算公式為：

其中，D表示網(wǎng)絡(luò)中目的節(jié)點收到數(shù)據(jù)分組數(shù)；S表示源節(jié)點產(chǎn)生的數(shù)據(jù)分組總數(shù)[12]。

（5）平均路徑建立時間，源節(jié)點發(fā)送RREQ分組尋路到接收到RREP分組的平均時間，計算公式為：

式中，Li表示第i(1

4.3仿真結(jié)果分析

（1）歸一化網(wǎng)絡(luò)開銷

由圖11可知，EIORA算法的歸一化網(wǎng)絡(luò)開銷小于LAOR算法。這是由于在尋路過程中，EIORA算法使用了RREP免疫機制，衛(wèi)星節(jié)點收到RREP分組后，再收到對應(yīng)RREQ分組時則丟棄該RREQ分組，避免了部分無效RREQ分組的繼續(xù)轉(zhuǎn)發(fā)，達到減小網(wǎng)絡(luò)開銷的目的。同時，EIORA算法優(yōu)化了路由更新機制，在一次路由尋路中更新了更多的衛(wèi)星節(jié)點的路由表，避免了即將失效的路徑重新尋路，進一步降低了網(wǎng)絡(luò)開銷。此外，在EIORA算法中，增加了中間衛(wèi)星代替目的衛(wèi)星回復(fù)RREP分組的概率，避免了后續(xù)衛(wèi)星節(jié)點轉(zhuǎn)發(fā)該RREQ分組，從而進一步降低了網(wǎng)絡(luò)開銷。

Fig.11 Normalized network overhead圖11 歸一化網(wǎng)絡(luò)開銷

（2）平均端到端時延

由圖12可知，EIORA算法的平均端到端時延性能要優(yōu)于LAOR算法。由于EIORA算法在一次尋路過程中更新了更多衛(wèi)星的路由表，衛(wèi)星能夠?qū)崟r感知網(wǎng)絡(luò)中的負載狀況以及網(wǎng)絡(luò)拓撲結(jié)構(gòu)變化，尋找更優(yōu)的路徑用于數(shù)據(jù)傳輸，減少了數(shù)據(jù)傳輸過程中路徑失效重新尋路的情況。同時，EIORA算法增加了中間衛(wèi)星代替目的衛(wèi)星回復(fù)RREP分組的概率，加快了路徑的建立過程，進一步降低了分組端到端時延。

（3）時延抖動

由圖13可知，當(dāng)網(wǎng)絡(luò)負載較小時，兩種路由算法的平均時延抖動性能基本一致，當(dāng)終端比特率大于600 Kb/s時，EIORA算法的平均時延抖動逐漸小于LAOR算法。這是由于EIORA算法在一次尋路過程中更新了更多衛(wèi)星的路由表，減少了數(shù)據(jù)包在傳輸過程中路徑失效的情況，此時數(shù)據(jù)包需存儲在節(jié)點緩存，等待衛(wèi)星節(jié)點重新尋路。因此EIORA算法的時延抖動要小于LAOR算法。

（4）成功率

由圖14可知，兩種算法終端比特率分組成功率都接近1，這是由于兩種算法采用洪泛建路的方式，負載較小時能夠保證數(shù)據(jù)包準(zhǔn)確送達目的衛(wèi)星。但當(dāng)終端比特率繼續(xù)增大時EIORA算法的分組投遞率要大于LAOR算法。這是由于在一次尋路過程中更新了更多衛(wèi)星的路由表，衛(wèi)星節(jié)點對于網(wǎng)絡(luò)拓撲和網(wǎng)絡(luò)負載等信息獲取及時準(zhǔn)確，數(shù)據(jù)包到達衛(wèi)星節(jié)點后可以盡快得到準(zhǔn)確轉(zhuǎn)發(fā)，避免了丟包情況的出現(xiàn)，因此EIORA算法的分組投遞率略微大于LAOR算法。

（5）平均路徑建立時間

在10 m in的仿真時間內(nèi)，每個節(jié)點每分鐘以任意節(jié)點為目的節(jié)點開始完整的路由發(fā)現(xiàn)過程。由圖15可知，EIORA算法的平均路徑建立時間要小于LAOR算法。這是由于EIORA算法優(yōu)化了中間節(jié)點代替目的節(jié)點回復(fù)請求過程，增加了中間節(jié)點代替目的節(jié)點回復(fù)RREP分組的概率，部分路徑不需要RREQ分組到達目的節(jié)點后再返回建立，而是中間節(jié)點生成RREP分組回復(fù)源節(jié)點，從而EIORA算法的平均路徑建立時間要小于LAOR算法。

Fig.12 Average end-to-end delay圖12 平均端到端時延

Fig.13 Delay jitter圖13 時延抖動

Fig.14 Success rate圖14 成功率

Fig.15 Average path establishment time圖15 平均路徑建立時間

通過上述仿真結(jié)果的對比分析，在相同的設(shè)定仿真環(huán)境參數(shù)下，本文提出的EIORA算法有效利用了源節(jié)點與目的節(jié)點間發(fā)送的控制消息，提高了路徑更新的廣泛性；設(shè)計RREP分組免疫機制，中間衛(wèi)星節(jié)點收到目的衛(wèi)星節(jié)點發(fā)送的RREP分組后，查詢該RREP分組記錄的最后衛(wèi)星節(jié)點地址信息，確定是否進行轉(zhuǎn)發(fā)，達到減小控制開銷的目的。通過上述改進措施，在仿真環(huán)節(jié)上的控制開銷、端到端時延以及成功率等指標(biāo)較LAOR算法有一定的改善，在整體性能上優(yōu)于原始算法，具有一定的參考價值。

5 結(jié)論

本文針對LEO按需路由算法LAOR在網(wǎng)絡(luò)運行時存在冗余控制開銷，沒有充分利用新建路徑的有效信息完成后續(xù)路徑建立等問題，提出了一種基于按需機制的高效低時延LEO衛(wèi)星網(wǎng)絡(luò)路由算法EIORA。該算法充分利用源衛(wèi)星與目的衛(wèi)星發(fā)送的控制分組信息，完成更多路徑更新，減少尋路的控制開銷，增加路由更新的廣泛性；采用RREP分組免疫機制降低了路由控制成本；增加中間衛(wèi)星代替目的衛(wèi)星回復(fù)應(yīng)答的概率，縮短了路徑建立時間。理論分析和仿真結(jié)果表明，同LAOR算法相比，EIORA算法在控制開銷以及平均端到端時延等性能上均有所提高。

在未來的工作中，將進一步研究如何減少數(shù)據(jù)包在尋路過程中的延遲問題。

References:

[1] Lu Yong, Zhao Youjian, Sun Chunfu, et al. Satellite network routing technology[J]. Journal of Software, 2014, 25(5): 1085-1100.

[2] Duan Sirui. Research on satellite network routing algorithm based on LEO polar orbit constellation[D]. Beijing: Beijing University of Posts and Telecommunications, 2014: 25-37.

[3] Jiang Wenjuan, Zong Peng. Research on network routing of LEO satellite constellation[J]. Computer Technology and Development, 2011, 21(3): 44-47.

[4] Zhang Quanxin, Niu Zhendong, Jin Fusheng. Improved multicast protocol based on routing grid[J]. Journal of Beijing Institute of Technology, 2008, 17(4): 415-418.

[5] Wang Ping, Chen Bingcai, Gu Xuemai, et al. Multi-constraint quality of service routing algorithm for dynam ic topology networks[J]. Journal of Systems Engineering and Electronics, 2008, 19(1): 58-64.

[6] Mohorcic M, Svigelj A, Kandus G, et al. Demographically weighted traffic flow models for adaptive routing in packetsw itched non-geostationary satellite meshed networks[J]. Computer Networks, 2011, 43(2): 113-131.

[7] Peng M in, Hong Peilin, Xue Kaiping, et al. Delivery probability prediction based efficient routing in DTN[J]. Chinese Journal of Computer, 2011, 34(1): 174-181.

[8] Papapetrou E, Karapantazis S, Pavlidou F N. Distributed ondemand routing for LEO satellite system s[J]. Computer Networks, 2012, 51(15): 4356-4376.

[9] Yuan Quan, Cardei I, Wu Jie. An efficient prediction based routing in satellite networks[J]. IEEE Transactions on Vehicular Technology, 2015, 16(21): 1870-1879.

[10] Gao Zihe, Guo Qing, Na Zhenyu.A distributed routing algorithm w ith traffic prediction in LEO satellite networks[J]. Information Technology Journal, 2012, 10(2): 285-292.

[11] Tsai K, Ma R P. DARTING: a cost-effective routing alternative for large space-based dynam ic-topology networks[C]// Proceedings of the 1995 M ilitary Communications Conference, San Diego, USA, Nov 7, 1995. Piscataway, USA: IEEE, 1995, 2: 682-686.

[12] Chan T H, Yeo B S, Turner L. A localized routing scheme for LEO satellite networks[J]. International Communications Satellite Systems Conferences, 2012, 17(33): 2357-2364.

[13] Ekici E, Akyildiz I F, Bender M D. A distributed routing protocol for datagram traffic in LEO satellite networks[J]. IEEE/ACM Transactions on Networking, 2011, 9(2): 137-147. [14] Paulo F, Barros J. Network coding protocols for secret key distribution[J]. On the Move to Meaningful Internet Systems, 2015, 48(4): 1718-1733.

[15] A li M, Stewart B G. Congestion adaptive multipath routing for load balancing in mobile WSN[J]. Innovations in Information Technology, 2014, 21(16): 305-309

附中文參考文獻：

[1]盧勇,趙有健,孫春福,等.衛(wèi)星網(wǎng)絡(luò)路由技術(shù)[J].軟件學(xué)報, 2014, 25(5): 1085-1100.

[2]段思睿.基于LEO極軌道星座的衛(wèi)星網(wǎng)絡(luò)路由算法研究[D].北京:北京郵電大學(xué), 2014: 25-37.

[3]蔣文娟,宗鵬.低軌道衛(wèi)星星座網(wǎng)絡(luò)路由研究[J].計算機技術(shù)與發(fā)展, 2011, 21(3): 44-47.

[7]彭敏,洪佩琳,薛開平,等.基于投遞概率預(yù)測的DTN高效路由[J].計算機學(xué)報, 2011, 34(1): 174-181.

WANG Bangyuan was born in 1963. He is an associate professor at Anhui Economic Management Institute. His research interests include network routing algorithm design, virtual instrument and automation, etc. He has published more than 10 academ ic papers and participated in the research project of Anhui Province Department of Education, key project of natural science research in colleges and universities in Anhui Province and national social science fund projects, etc.

王幫元（1963—），男，安徽含山人，安徽經(jīng)濟管理學(xué)院副教授，主要研究領(lǐng)域為網(wǎng)絡(luò)路由算法設(shè)計，虛擬儀器與自動化等。發(fā)表學(xué)術(shù)論文10多篇，主持與參加安徽省教育廳教研項目、安徽省高校自然科學(xué)研究重點項目以及國家社會科學(xué)基金項目等。

SONG Jie was born in 1966. He received the Ph.D. degree in computer application from Hefei University of Technology in 2006. Now he is an associate professor and M.S. supervisor at Anhui University. His research interests include computer network and information processing, etc. He has published over 20 papers and 5 textbooks, has been in charge of 2 scientific research projects of Anhui Province Department of Education and participated in 2 national natural science fund projects.

宋杰（1966—），男，安徽合肥人，2006年于合肥工業(yè)大學(xué)計算機應(yīng)用專業(yè)獲得博士學(xué)位，現(xiàn)為安徽大學(xué)副教授、碩士生導(dǎo)師，安徽大學(xué)計算機學(xué)院計算機原理與結(jié)構(gòu)實驗室主任、網(wǎng)絡(luò)工程系副主任，主要研究領(lǐng)域為計算機網(wǎng)絡(luò)，信息處理等。發(fā)表學(xué)術(shù)論文20余篇，出版教材5本，主持安徽省教育廳科研項目兩項，參加國家自然科學(xué)基金項目兩項。

ZHOU Weiliang was born in 1967. He is a professor at Anhui Economic Management Institute, and Ph.D. candidate at Hefei University of Technology. His research interests include computer network and information processing, etc. He has published 20 papers and 4 textbooks of Anhui Province“11th Ffive-Year Plan”, and has been in charge of 1 national social science fund project and more than 10 projects on natural science fund of Anhui Province and so on.

周偉良（1967—），男，湖南長沙人，安徽經(jīng)濟管理學(xué)院教授，合肥工業(yè)大學(xué)管理學(xué)院博士研究生，主要研究領(lǐng)域為計算機網(wǎng)絡(luò)，信息處理等。發(fā)表學(xué)術(shù)論文20篇，主編安徽省“十一五”規(guī)劃教材等4部，主持國家社會科學(xué)基金項目1項，安徽省自然科學(xué)基金項目與安徽省教育廳自然科學(xué)研究項目等10多項。

Efficient Low-Delay Routing A lgorithm for LEO Satellite Networks Based on Ondemand M echanism?

WANG Bangyuan1+, SONG Jie2, ZHOU Weiliang1
1. Department of Information Engineering,Anhui Econom ic Management Institute, Hefei 230031, China 2. College of Computer,Anhui University, Hefei 230601, China
+ Corresponding author: E-mail: wangbangyuan1963@sina.com

Key words:LEO satellite; packet navigation; feedback response; on-demand routing

Abstract:For these problems such as redundancy control packet, not fully utilizing information of new paths to complete the follow-up paths, this paper proposes an efficient and low-delay LEO (low earth orbit) satellite network routing algorithm based on on-demand mechanism EIORA (efficient improved on-demand routing algorithm). The proposed algorithm reduces control overhead and increases the universality of routing update by making full use of the control groups of the source and target satellites. At the same time, the RREP (route reply) packet is designed to reduce the network control overhead by discarding the RREQ (route request) packet when corresponding RREQ packet is received after intermediate satellite receiving the RREP packet. And the time of building the path is shortened by increasing the probability of intermediate satellite instead of target satellite to answer the response. Simulation results show that the proposed algorithm can reduce the control overhead and the end-to-end delay, as well as improve the transm ission efficiency compared w ith the LAOR (lightweight ad hoc on-demand routing) algorithm.

doi:10.3778/j.issn.1673-9418.1507083 E-mail: fcst@vip.163.com

文獻標(biāo)志碼：A

中圖分類號：TP393