按需機制的高效低時延LEO衛星網絡路由算法*

王幫元，宋　杰，周偉良

?

按需機制的高效低時延LEO衛星網絡路由算法*

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

1.安徽經濟管理學院信息工程系，合肥230031
2.安徽大學計算機學院，合肥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 (國家社會科學基金); the Natural Science Research Program of Higher Education of Anhui Province under Grant No. KJ2015A394 (安徽省高校自然科學研究重點項目).

Received 2015-07,Accepted 2015-09.

CNKI網絡優先出版: 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）衛星網絡路由算法存在冗余控制開銷，未充分利用新建路徑有效信息完成后續路徑建立等問題，提出了基于按需機制的高效低時延LEO衛星網絡路由算法EIORA（efficient improved on-demand routing algorithm）。該算法充分利用源衛星與目的衛星發送的控制分組，減少尋路的控制開銷，增加路由更新的廣泛性；采用RREP（route reply）分組免疫機制，中間衛星收到RREP分組后若收到對應的RREQ （route request）分組，則丟棄該RREQ分組，以減小網絡控制開銷；增加中間衛星代替目的衛星回復應答的幾率，縮短路徑建立時間。仿真結果表明，與LAOR算法相比，該算法在減緩星地之間的控制開銷與端到端時延，以及提升傳輸效率上有明顯的改善。

關鍵詞：LEO衛星；分組導航；反饋應答；按需尋路

1 引言

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

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

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

2 網絡模型

本文采用具有星際鏈路的近極地星座為網絡場景，在該星座系統中每顆衛星節點設計有4條星際鏈路，即2條軌道間星際鏈路和2條軌道內星際鏈路[11]，如圖1所示。

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

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

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

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

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

3 EIORA算法

本文通過對目前比較經典的應用較廣泛的LEO衛星網絡路由算法LAOR進行研究發現，該算法存在以下問題：

（1）在一次路徑發現過程中，LAOR算法RREP分組只記錄目的衛星地址，完成中間衛星和源衛星到目的衛星的路徑更新，對于網絡拓撲頻繁變化的衛星網絡，路由更新的廣泛性較差。

（2）當RREQ分組到達目的衛星后，網絡中存在中間衛星不知道目的衛星是否已經收到該RREQ分組，因此這些中間衛星會繼續廣播該RREQ分組副本，從而導致不必要的控制開銷。

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

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

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

3.1路徑更新

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

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

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

Fig.3 Rectangle request area圖3 矩形請求區域

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

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

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

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

3.2 RREP分組免疫機制

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

Fig.6 Intermediate satellite node RREP packet format圖6 中間衛星節點RREP分組格式

圖6中，dst表示生成RREP分組的目的衛星節點地址，src表示生成RREP分組的源衛星節點地址，timestamp等于該RREP分組對應的RREQ分組生成的時間。

當中間衛星節點收到RREQ分組并轉發該RREQ分組前，獲取RREQ分組中pkt_src字段、pkt_dst字段和pkt_timestamp字段的值。檢查當前衛星節點記錄RREP分組的表中是否存在同時滿足式（1）、式（2）、式（3）的情況：

僅當不存在滿足的表項時，該中間衛星節點才繼續廣播該RREQ分組。

3.3 RREQ分組代替回復機制

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

Fig.7 Intermediate satellite node RREQ packet format圖7 中間衛星節點RREQ分組格式

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

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

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

3.4 EIORA算法操作

EIORA算法操作步驟如下。

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

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

Fig.8 Request area A圖8 請求區域A

Fig.9 Request area B圖9 請求區域B

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

或者

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

步驟4源衛星收到RREP分組，建立路徑并發送數據。

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

4 仿真和性能分析

4.1仿真環境設置

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

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

衛星網絡主要的仿真參數如表1所示。

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

Table 1 EIORA simulation parameters表1 EIORA仿真參數

業務產生參數如表2所示。

Table 2 Business generating parameters表2 業務產生參數

4.2仿真統計量

（1）歸一化網絡開銷，每發送一定數據所需要的控制分組的長度，計算公式為：

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

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

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

（3）時延抖動，連續到達目的節點的數據包的時延平均值，計算公式為：

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

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

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

其中，D表示網絡中目的節點收到數據分組數；S表示源節點產生的數據分組總數[12]。

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

式中，Li表示第i(1

4.3仿真結果分析

（1）歸一化網絡開銷

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

Fig.11 Normalized network overhead圖11 歸一化網絡開銷

（2）平均端到端時延

由圖12可知，EIORA算法的平均端到端時延性能要優于LAOR算法。由于EIORA算法在一次尋路過程中更新了更多衛星的路由表，衛星能夠實時感知網絡中的負載狀況以及網絡拓撲結構變化，尋找更優的路徑用于數據傳輸，減少了數據傳輸過程中路徑失效重新尋路的情況。同時，EIORA算法增加了中間衛星代替目的衛星回復RREP分組的概率，加快了路徑的建立過程，進一步降低了分組端到端時延。

（3）時延抖動

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

（4）成功率

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

（5）平均路徑建立時間

在10 m in的仿真時間內，每個節點每分鐘以任意節點為目的節點開始完整的路由發現過程。由圖15可知，EIORA算法的平均路徑建立時間要小于LAOR算法。這是由于EIORA算法優化了中間節點代替目的節點回復請求過程，增加了中間節點代替目的節點回復RREP分組的概率，部分路徑不需要RREQ分組到達目的節點后再返回建立，而是中間節點生成RREP分組回復源節點，從而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 平均路徑建立時間

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

5 結論

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

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

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]盧勇,趙有健,孫春福,等.衛星網絡路由技術[J].軟件學報, 2014, 25(5): 1085-1100.

[2]段思睿.基于LEO極軌道星座的衛星網絡路由算法研究[D].北京:北京郵電大學, 2014: 25-37.

[3]蔣文娟,宗鵬.低軌道衛星星座網絡路由研究[J].計算機技術與發展, 2011, 21(3): 44-47.

[7]彭敏,洪佩琳,薛開平,等.基于投遞概率預測的DTN高效路由[J].計算機學報, 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—），男，安徽含山人，安徽經濟管理學院副教授，主要研究領域為網絡路由算法設計，虛擬儀器與自動化等。發表學術論文10多篇，主持與參加安徽省教育廳教研項目、安徽省高校自然科學研究重點項目以及國家社會科學基金項目等。

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年于合肥工業大學計算機應用專業獲得博士學位，現為安徽大學副教授、碩士生導師，安徽大學計算機學院計算機原理與結構實驗室主任、網絡工程系副主任，主要研究領域為計算機網絡，信息處理等。發表學術論文20余篇，出版教材5本，主持安徽省教育廳科研項目兩項，參加國家自然科學基金項目兩項。

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—），男，湖南長沙人，安徽經濟管理學院教授，合肥工業大學管理學院博士研究生，主要研究領域為計算機網絡，信息處理等。發表學術論文20篇，主編安徽省“十一五”規劃教材等4部，主持國家社會科學基金項目1項，安徽省自然科學基金項目與安徽省教育廳自然科學研究項目等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

文獻標志碼：A

中圖分類號：TP393