按需机制的高效低时延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算法在不增加开销的情况下，提高了路由更新的广泛性，更加适合卫星拓扑的动态变化。□

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