基于局部队列的导航卫星网络路由算法

燕洪成，张庆君，孙 勇

(中国空间技术研究院总体部，北京100094)

0 引言

卫星导航系统可以利用星间链路的星间测距功能实现自主导航;同时，也可以利用星间链路的星间通信功能实现全球组网，从而提高系统的整体性能［1－3］。由于导航卫星平台和指向性星间链路(Inter-Satellite Link，ISL)天线的约束，导航卫星所能携带的天线数量有限(比如仅能携带一条)，导航卫星网络中的ISL将呈现半双工、大时延、链路间断可用的特点。同时，由于地球自转和导航星座运行的影响，导航卫星与地面站之间的星地链路(Ground-Satellite Link，GSL)也呈现周期性的连接与中断特点。ISL和GSL的这种链路间断可用特点使导航卫星网络任意两个网络节点之间并不一定时刻存在端到端路径，使其形成一个典型的延迟/中断容忍网 络(Delay/Disruption Tolerant Network，DTN)［4－6］。这对导航卫星网络的数据传输问题，特别是路由问题带来了新的挑战［7］。

图1为一个典型导航卫星网络不同时刻的拓扑示意图，时间间隔固定为Δt，称为一个时隙。假设有6颗导航卫星(圆形)和1个地面站(正方形)，两颗导航卫星之间用两个单向箭头连接说明在该时隙内建立了半双工ISL，导航卫星和地面站之间用双向箭头连接说明在该时隙内建立了全双工GSL。假定每颗导航卫星均配置1副ISL天线和1副GSL天线，1颗导航卫星在1个时隙内仅能选择与另外1颗可见卫星建立ISL，并以一定策略与地面站建立GSL。从图1可以看出，由于ISL和GSL间断连接，导航卫星网络中任意两个节点间并不一定时刻存在端到端路径，从而形成一个非全连通的网络拓扑。比如卫星4与地面站G1在任何时隙均不存在端到端路径，这使Dijkstra算法［8］在任何一个时隙均不能计算出可行路径。但卫星4可以在时隙［0，Δt)将消息发送给卫星3，卫星3暂存消息，并在时隙［2Δt，3Δt)转发给地面站G1，最终完成消息的投递。导航卫星网络中的路由问题不仅需要考虑某一时刻的静态拓扑，同时需要考虑网络拓扑的时间演化特性，通过综合考虑不同时刻的网络拓扑完成路由计算。

图1 导航卫星网络在不同时刻的网络拓扑示意图Fig．1 Network topology of navigation satellite network in different time slots

导航卫星网络的网络拓扑由ISL和GSL的链路调度决定，ISL和GSL的链路调度一般根据一定策略提前生成，并分发到每个网络节点;因此，导航卫星网络的路由问题可以看作是确定链路调度的DTN路由问题。

由于传统的移动通信卫星网络路由算法［9－10］均假定网络时刻存在端到端路径，因此并不适用于导航卫星网络。学术界针对DTN路由问题的研究主要集中在机会网络［11－12］，确定链路调度的DTN路由算法相对较少。目前，学术界针对确定链路调度的DTN路由问题提出了演化图模型［7，13］、空时路由算法［14］、接触图路由(Contact Graph Routing，CGR)［15］、时变图模型［16］等，但这些路由算法均只考虑网络的链路调度，而未考虑网络的排队延时，因此，其性能有限。由于导航卫星网络链路通信机会有限，排队延时可能使消息错过当前可用通信机会，从而增大端到端延时，并使消息长时间占用网络资源，降低消息投递成功率。

Jain等［17］提出了基于本地队列的最早投递(Earliest Delivery with Local Queue，EDLQ)和基于全网队列的最早投递(Earliest Delivery with All Queues，EDAQ)路由算法;Bezirgiannidis等［18－19］针对CGR提出了一种基于最早传输机会(Earliest Transmission Opportunity，ETO)的路由算法(CGRETO)，并考虑全网队列信息。但上述路由算法存在以下问题:首先，仅考虑本地节点队列信息不能够使消息避开拥塞的邻居节点;其次，获取全网的队列信息会带来大量的协议开销，且由于导航卫星网络的端到端延时较大，网络节点获取的队列信息可能已经过时。因此，向全网泛洪队列信息带来的性能提升有限。

本文针对链路间断可用的导航卫星网络，提出一种基于局部队列的最早投递(Earliest Delivery with Partial Queues，EDPQ)路由算法。EDPQ综合利用链路调度信息、本地和邻居节点队列信息，可以实现链路调度按需更新，并以较低协议开销更新邻居节点队列信息，实现了更高效的数据传输。

1 EDPQ路由算法

EDPQ路由算法利用全网的链路调度信息、本地和邻居节点的队列信息完成路由计算。全网的链路调度信息为已知信息且一般周期性重复，由于提前存储未来所有的链路调度信息不现实，EDPQ采用一种按需更新的策略来更新链路调度信息;本地节点的队列信息较容易获取，而邻居节点的队列信息需要不断更新，EDPQ采用一种低开销的机制更新邻居节点队列信息。

1．1导航卫星网络的图模型

记导航卫星网络的节点集合为V，边集为E⊆V×V。定义ρ:E×R+→{0，1}为存在函数，表示在时刻t边e是否存在;定义d:E×R+→R+为传播延时函数，表示在时刻t边e的传播延时。对于导航卫星网络，节点集合为卫星、地面站和任务运行中心等网络节点的集合;边集为星间链路、星地链路和地面有线链路等通信链路的集合。

假定所有链路在可用时间间隔内带宽恒定，那么，在时刻t边e的容量可以表示为c(e，t)=b(e)·ρ(e，t)，其中b(e)为边e的带宽。

记边e的存在时间为I(e)={t∈R+:ρ(e，t)=1}，表示边e存在的所有时间的集合。边e的存在时间也可表示为一系列链路调度区间的集合，即I(e)={［t1，t2)∪［t3，t4)∪…}。对于导航卫星网络，链路的存在时间通常呈现周期性。定义边e存在函数的周期为p，即对于任意t∈R+，任意k∈N，ρ(e，t)=ρ(e，t+kp)成立。那么边e的存在时间可以表示为

1．2链路调度按需更新机制

对于导航卫星网络的链路调度信息，本文只存储每条边一个周期的链路调度信息，并在路径计算过程中按需更新链路调度信息;同时，每隔固定时间Δtrm移除过去的链路调度信息，防止链路调度信息无限制增长，占用导航卫星有限的存储资源。

EDPQ利用改进Dijkstra算法［17］计算下一跳，改进Dijkstra算法可以利用边的时变代价w:E×R+→R+计算延时最优路径。边的时变代价w(e，t)除了与边和时间有关外，与当前消息大小和本地节点也有关，因此，为了统一，将代价函数写为w(e，t)=w'(e，t，m，s)，其中，m为消息的大小，s为当前节点［17］。

w'(e，t，m，s)可以写为

w'(e，t，m，s)=t'(e，t，m，s)－t+d(e，t')

其中，

在上式中，函数Q(e，t，s)为本地节点s在时刻t获取的边e源端的队列长度，t'为将队列中的消息和当前消息发送到网络中的最早时刻［17］。

改进Dijkstra算法的关键在于时间t'的计算，在实际实现t'计算公式中的积分时，需要综合考虑当前队列中消息与待发送消息的大小、时刻t与接触机会的关系，以及接触机会的容量限制。图2为当前时刻与接触机会的三种关系示意图。第一种情况t=t1时，计算t'需要考虑下一个接触机会的容量，如果下一个接触机会容量不够，还需要考虑下下一个接触机会。第二种情况t=t2时，计算t'需要考虑当前接触机会的剩余容量，如果剩余容量不够，也要考虑下一个接触机会。第三种情况t=t3时，由于已经没有未来的接触机会可用，需要首先增加一个周期的接触机会，然后按第一种或第二种情况计算t'。

图2 当前时刻与接触机会的三种关系Fig．2 Three potential relationships between current time and contact opportunities

图3为计算t'及链路调度按需更新机制的伪代码，其中，I为链路调度区间链表，临时变量II为边的某个链路调度区间，并用start和stop分别表示该链路调度区间的开始时间和结束时间，load为当前消息和队列中消息大小的总和;函数AddSched()将增加边的一个周期的链路调度。

图3 计算t'及链路调度按需更新机制的伪代码Fig．3 Pseudocode of calculation for t'and on-demand link schedule updating mechanism

1．3邻居节点队列信息更新机制

演化图模型［7，13］、空时路由算法［14］、接触图路由［15］、时变图模型［16］和ED路由算法［17］等均只考虑链路调度信息，未考虑网络的排队延时，因此其性能有限。在DTN网络中，消息传输的端到端延时主要包括等待链路可用延时、排队延时、发送延时和传播延时。排队延时虽然可能只占路径延时的小部分，但由于导航卫星网络链路通信机会有限，较大的排队延时可能会使消息错过当前可用接触机会，而只能等待下次接触机会，从而增大端到端时延，并使消息长时间占用网络资源，降低消息投递成功率。因此，在导航卫星网络的路由计算中应该考虑消息的排队延时。

导航卫星网络的本地节点队列信息较容易获取，邻居节点队列信息也相对容易获取。由于仅利用本地节点队列信息不能使消息避开拥塞的邻居节点;而获取全网队列信息会带来较大的协议开销，且由于导航卫星网络路径延时较大，获取的全网队列信息时效性较差，实际能够带来的性能改进有限。因此，EDPQ除了利用链路调度信息外，仅考虑了本地和邻居节点的队列信息。

EDPQ采用一种队列阈值触发机制触发队列信息的发送，以降低邻居节点队列信息传播带来的协议开销。本地节点收到邻居节点发送的包含队列信息的消息(简称队列消息)后，通过人为加大拥塞的边的排队延时来降低选择此边的概率，从而避开排队延时大的路径。同时，邻居节点队列信息的作用应该随时间慢慢减弱，因此，本地节点对邻居节点队列信息按指数进行衰减。

当本地节点的发送机会(由于ISL为半双工)出现时，本地节点首先统计除当前边外，其它边的队列大小Qsize≥95%Qlimit(Qlimit为队列容量)的队列个数。如果超出阈值的队列个数大于等于1，本地节点将首先发送队列消息到邻居节点，然后再发送本地数据消息;否则，直接发送本地数据消息。邻居节点如果利用本地节点与其相连的边的话会产生路由环路，因此，没有统计当前边。Qsize≥95%Qlimit说明即将发生拥塞，需要通知邻居节点以避开此边。

邻居节点收到队列消息后，将Qsize≥95%Qlimit的相应队列的大小按下式设置为一个比较大的数值，以避免选择此边。

式(1)基于这样一种考虑，在DTN网络中，等待时间通常占端到端延时的大部分，而最短路径和次短路径的延时代价可能相差较大，且相差的部分主要来自等待时间，排队时间的变化通常不足以使最短路径变为次短路径，使消息仍然选择最短路径进一步加剧拥塞。

为了更清晰地说明上述情况，考虑图4所示的一个示意图。其中图4(a)显示了图1中卫星6到地面站G1的两条路径，图中假定Δt为3 s，半双工约定前半个时隙序号小的卫星先发送，后半个时隙正好相反;图4(b)为卫星6的一种队列情况示意图，图中卫星6为每个邻居节点分配一个等容量的队列用于缓存消息。假设卫星6的消息均发往地面站G1，由图4(a)可知，消息可以通过最短路径6－＞5－＞2－＞G1在4．5 s到达地面站G1，也可以通过次短路径6－＞3－＞G1在6 s到达地面站G1，最短和次短路径代价相差1．5 s。假定卫星6中卫星5的队列已经缓存了大量的消息，那么对于当前消息m，虽然通过卫星5转发会经历较大的排队延时，但只有当排队延时超过1．5 s时最短路径的代价才会高于次短路径。排队延时最大为队列容量除以ISL速率，假设队列容量为40 kbits，ISL速率为50 kbps，排队延时最大为0．8 s，仍然不能够使最短路径变为次短路径，因此需要人为加大拥塞的边的排队时间，降低选择此边的概率。由于最短路径和次短路径之间相差大于等于一个周期的情况较少，因此，设置排队时间为该边一个周期的时间。

EDPQ在产生消息或收到消息后，首先分别对本地队列和邻居节点队列进行处理。对每个本地队列，如果Qsize≥Qlimit，那么按式(1)设置该队列大小;对每个邻居节点队列，按下式进行衰减［20］

式中:Δt为距上次邻居节点队列信息更新所经历的时间间隔数量，其值为实际时间间隔除以时间单位tunit，β∈(0，1)为衰减因子。由于节点发送消息时使用的邻居节点队列信息可能不是最新的，而且邻居节点队列信息更新不是周期性的，因此邻居节点队列信息应该慢慢衰减。在对本地队列信息和邻居节点队列信息处理完成后，利用改进Dijkstra算法计算下一跳转发节点。

2 性能评估

2．1仿真环境

图4 用于解释队列大小设置的一个例子Fig．4 An example to explain the setting of queue size

为了校验EDPQ的性能，在典型的导航卫星网络中进行了仿真评估。导航卫星网络由导航卫星星座及相关地面站和任务运行中心(Mission Operation Center，MOC)组成，如图5所示。导航卫星星座构型选择walker 24/3/2，即一共24颗卫星分布在3个轨道面内，相位因子为2。导航卫星轨道高度为20232 km，倾角为55°。选用北京、喀什、三亚3个地面站，每个地面站均配置2副天线，并选择与自己未来通信时间最长的两颗导航卫星建立全双工GSL。地面站与MOC之间通过地面网络时刻保持连通。

图5 导航卫星网络系统架构图Fig．5 Network architecture of the navigation satellite network

每颗卫星仅携带一副半双工ISL天线，指向方位角限定在［－60°，60°］。由于地球的遮挡和ISL的指向限制，并不是所有卫星间都能建立ISL［21］。一颗导航卫星选择与哪颗可见卫星建立ISL属于导航卫星网络的链路分配问题［22］，不在本文的研究范围内。为简便起见，ISL的链路调度按每颗卫星均能与全周期可见的同轨和异轨卫星建立ISL的策略手动生成。ISL的链路调度共有8个时隙，并以此为周期循环，每个时隙的持续时间为Δt。

导航卫星网络ISL的链路调度用一个24×8的矩阵表示，如图6所示。矩阵的元素(i，j)表示卫星i与卫星(i，j)，在第j个时隙建立半双工ISL。比如位于第2行和第3列的13表示，在第3个时隙，卫星2与卫星13建立半双工ISL。每个时隙的前Δt/2，数值小的卫星发送，数组大的卫星接收，后Δt/2相反。

在OPNET网络仿真软件中对导航卫星网络进行了建模，默认仿真参数如表1所示，后文中，若无特殊说明，均采用此默认仿真参数。导航卫星网络的消息由卫星和MOC产生，消息到达时间间隔均服从指数分布。导航卫星产生消息的目的节点为MOC，MOC产生消息的目的节点为随机一颗卫星。

表1 默认仿真参数Table 1 The default simulation parameters

2．2仿真结果

比较的路由算法选择ED、EDLQ和EDAQ。EDAQ可以有分布式和集中式两种实现方式，由于Jain等［17］没有说明EDAQ具体采用哪种实现方式，本文同时实现了两种EDAQ，即EDAQ分布式(EDAQ Distributed，EDAQ-D)和EDAQ集中式(EDAQ Central，EDAQ-C)。EDAQ-D通过向全网泛洪队列消息来获取全网队列信息，而EDAQ-C维护一个全局的网络队列信息库，没有任何协议开销。EDAQ-C现实中较难实现，主要用作性能对比。

图6 导航卫星网络ISL的链路调度Fig．6 Link schedule of the navigation satellite network

性能度量指标选择消息投递成功率、端到端时延和协议开销。投递成功率为投递成功的消息数量占产生消息总量的百分比;端到端时延为消息从产生到成功投递所经历的时间，由于无法统计丢弃消息的时延，因此端到端时延仅统计成功投递的消息;协议开销为单位时间内传播的队列消息的比特数，即协议开销为传播的队列消息个数乘以队列消息大小，再除以仿真持续时间，其中，队列消息大小为416 bits。在比较的五种路由算法中，仅有EDPQ和EDAQ-D会产生协议开销。

为了测试不同网络负载对路由算法性能的影响，设置导航卫星的消息到达时间间隔从0．8 s以指数间隔变化到0．05 s，即网络负载不断增大。MOC的消息到达时间间隔保持恒定，仿真结果如图7所示。由图7(a)可以看出，随着网络负载的增大，五种路由的投递成功率均呈下降趋势，这是由于有限的存储资源逐渐不能存储产生的越来越多的消息，因此，越来越多的消息不能投递到目的地。ED和EDLQ的性能较差，其投递成功率在较低网络负载时就开始下降。EDAQ-C的投递成功率最高，EDPQ的性能与EDAQ-C接近。EDAQ-D的投递成功率在网络负载较大时比EDPQ要低，这是因为EDAQ-D产生了较大的协议开销，而EDPQ的协议开销相对较低，如图7(c)所示，较大的协议开销会占用导航卫星有限的存储资源，使消息不能得到存储而被丢弃。在图7(c)中，当消息到达时间间隔为0．8 s时，EDPQ和EDAQ-D的协议开销均为零。

图7(b)为不同路由算法的端到端时延性能。当网络负载较低时，五种路由算法的时延性能相当。随着网络负载的增大，ED与EDLQ的端到端时延仍然较低，这与其较低的投递成功率有关;而其它路由算法的时延开始增大，这与其选择拥塞程度差的路径避免丢包有关。EDAQ-D产生的大量协议开销会占用导航卫星网络有限的通信资源，使消息错过当前可用通信机会，增大端到端时延。EDPQ与EDAQ-C的端到端时延性能接近。

为了测试不同队列容量对路由算法性能的影响，设置导航卫星每邻居节点队列容量分别为20、30、40、50、60 kbits，仿真结果如图8所示。由图8(a)可以看出，随着队列容量的增大，五种路由的投递成功率均呈增大趋势，这是由于增多的队列容量可以存储更多的消息，使更多的消息成功投递到目的节点。在队列容量小于50 kbits时，EDPQ与EDAQ-C的投递成功率接近，而EDAQ-D的投递成功率要比EDPQ低。这是由于EDAQ-D产生了大量的协议开销，如图8(c)所示，大量的协议开销会占用有限的存储资源，使消息得不到存储而被丢弃。在队列容量非常充足时(60 kbits)，EDPQ、EDAQ-D和EDAQ-C的投递成功率均达到了百分之百。ED和EDLQ的投递成功率均较低。

图8(b)为不同路由算法的端到端时延性能。EDAQ-D的端到端时延较大，这是由于EDAQ-D产生的大量协议开销会占用有限的通信资源，使消息错过当前可用通信机会。EDPQ与EDAQ-C的端到端时延性能接近，但比EDAQ-D的端到端时延要低。ED与EDLQ的端到端时延较低，这与其较低的投递成功率有关。

图7 不同网络负载时的路由性能Fig．7 Performance with varying network loads

为了测试不同ISL通信速率和不同数据消息大小对路由算法性能的影响，设置ISL通信速率分别为20、40、60、80 kbps，设置数据消息大小分别为512、1024、2048、4096 bits，仿真结果如图9所示。由图9(a)可以看出，当ISL通信速率为20 kbps时，EDLQ、EDPQ与EDAQ-C的投递成功率接近，而EDAQ-D和ED性能较差。由于EDAQ-D会产生大量的通信开销占用有限的通信资源，这在ISL速率较低时会更明显，因此其投递成功率较低。当ISL通信速率为40、60和80 kbps时，EDAQ-C的投递成功率最高，EDPQ的投递成功率与EDAQ-C接近，EDAQ-D的投递成功率比EDPQ低，ED和EDLQ的投递成功率最低。

图8 不同队列容量时的路由性能Fig．8 Performance with varying queue capacities

在图9(b)中，当数据消息大小为512 bits时，EDPQ与EDAQ-C的投递成功率接近，而EDAQ-D与ED、EDLQ的投递成功率较低。这是由于EDAQD带来的较大协议开销在数据消息大小与队列消息大小相近时会更加明显。较大的协议开销使数据消息没有机会得到有限的存储资源，从而被丢弃;较大的协议开销也使数据消息不能获得有限的通信资源，而不得不等待未来的通信机会，进而使数据消息长时间占用网络存储资源，使其它消息不能得到存储资源，造成其它消息的丢弃。当数据消息大小为1024、2048和4096 bits时，EDAQ-C的投递成功率最高，EDPQ的投递成功率与EDAQ-C接近，EDAQD的投递成功率比EDPQ低，ED和EDLQ的投递成功率最低。

图9 投递成功率与ISL通信速率和消息大小的关系Fig．9 Delivery success ratio with varying ISL rates and message sizes

3 结论

本文提出了一种基于局部队列的最早投递(EDPQ)路由算法，并在典型的导航卫星网络中对EDPQ进行了仿真评估。仿真结果表明，EDPQ实现了较高的消息投递成功率和较低的端到端延时，且具有较低的协议开销，为链路间断可用的导航卫星网络的路由问题提供了一种可行的技术方案。

［1］Maine K，Anderson P，Bayuk F．Communication architecture for GPS III［C］．2004 IEEE Aerospace Conference，Big Sky，USA，March 6－13，2004．

［2］Luba O，Boyd L，Gower A．GPS III system operations concepts［J］．IEEE Aerospace and Electronic Systems Magazine，2005，20(1):10－18．

［3］Fernandez A．Inter-satellite ranging and inter-satellite communication links for enhancing GNSS satellite broadcast navigation data［J］．Advances in Space Research，2011，47:786－801．

［4］Fall K．A delay-tolerant network architecture for challenged internets［C］．ACM SIGCOMM 2003，Karlsruhe，Germany，August 25－29，2003．

［5］ 林闯，董扬威，单志广．基于DTN的空间网络互联服务研究综述［J］．计算机研究与发展，2014，51(5):931－943．［Lin Chuang，Dong Yang-wei，Shan Zhi-guang．Research on space internetworking service based on DTN［J］．Journal of Computer Research and Development，2014，51(5):931－943．］

［6］ 燕洪成，张庆君，孙勇，等．延迟/中断容忍网络技术及其在行星际因特网中的应用［J］．航天器工程，2014，23(2):114－123．［Yan Hong-cheng，Zhang Qing-jun，Sun Yong，et al．Delay/disruption tolerant network and its application to interplanetary Internet［J］．Spacecraft Engineering，2014，23(2):114－123．］

［7］ 王彦，刘波，虞万荣，等．基于演化图的导航星座星间路由算法［J］．中国空间科学技术，2012(5):76－83．［Wang Yan，Liu Bo，Yu Wan-rong，et al．Routing algorithm for navigation constellation based on evolving graph model［J］．Chinese Space Science and Technology，2012(5):76－83．］

［8］Cormen T，Leiserson C．Introduction to algorithm［M］．Cambridge:The MIT Press，2004．

［9］ 卢勇，赵有健，孙富春，等．卫星网络路由技术［J］．软件学报，2014，25(5):1085－1100．［Lu Yong，Zhao You-jian，Sun Fuchun，et al．Routing techniques on satellite networks［J］．Journal of Software，2014，25(5):1085－1100．］

［10］ 王路，刘立祥，胡晓惠．基于地理位置信息的无收敛多测度卫星网络路由算法研究［J］．宇航学报，2011，32(7):1542－1550．［Wang Lu，Liu Li-xiang，Hu Xiao-hui．Geographical location-based convergence-free routing using multiple metrics for satellite networks［J］．Journal of Astronautics，2011，32(7):1542－1550．］

［11］ 苏金树，胡乔林，赵宝康，等．容延容断网络路由技术［J］．软件学报，2010，21(1):119－132．［Su Jin-shu，Hu Qiao-lin，Zhao Bao-kang，et al．Routing techniques on delay/disruption tolerant networks［J］．Journal of Software，2010，21(1):119－132．］

［12］Cao Y，Sun Z．Routing in delay/disruption tolerant networks:a taxonomy，survey and challenges［J］．IEEE Communications Surveys＆Tutorials，2013，15(2):654－677．

［13］Ferreira A．Building a reference combinatorial model for MANETs［J］．IEEE Network，2004，18(5):24－29．

［14］Merugu S，Ammar M，Zegura E．Routing in space and time in networks with predictable mobility，GIT-CC－04－07［R］．Atlanta，USA:Georgia Institute of Technology，March 2004．

［15］Burleigh S．Contact graph routing，IRTF Internet-Draft［EB/OL］．2010－07－08［2014－12－02］．http://tools．ietf．org/html/draft-burleigh-dtnrg-cgr-01．

［16］Casteigts A，Flocchini P，Quattrociocchi W，et al．Time-varying graphs and dynamic networks［J］．International Journal of Parallel，Emergent and Distributed Systems，2012，27(5):387－408．

［17］Jain S，Fall K，Patra R．Routing in a delay tolerant network［J］．ACM SIGCOMM Computer Communication Review，2004，34(4):145－158．

［18］Bezirgiannidis N，Caini C，Montenero D P，et al．Contact graph routing enhancements for delay tolerant space communications［C］．7th Advanced Satellite Multimedia Systems Conference and the 13th Signal Processing for Space Communications Workshop(ASMS/SPSC)，Livorno，Italy，September 8－10，2014．

［19］Bezirgiannidis N，Tsapeli F，Diamantopoulos S，et al．Towards flexibility and accuracy in space DTN communications［C］．The 8th ACM MobiCom Workshop on Challenged Networks，Miami，USA，September 30，2013．

［20］Lindgren A．Probabilistic routing in intermittently connected networks［J］．ACM Mobile Computing and Communication Review，2003，7(3):19－20．

［21］ 李振东，何善宝，刘崇华，等．一种导航星座星间链路拓扑设计方法［J］．航天器工程，2011，20(3):32－37．［Li Zhendong，He Shan-bao，Liu Chong-hua，et al．An topology design method of navigation satellite constellation inter-satellite links［J］．Spacecraft Engineering，2011，20(3):32－37．］

［22］ 石磊玉，向为，唐小妹．一种兼顾卫星导航系统星间观测及通信的链路分配算法［J］．宇航学报，2011，32(9):1971－1977．［Shi Lei-yu，Xiang Wei，Tang Xiao-mei．A link assignment algorithm applicable to crosslink ranging and data exchange for satellite navigation system［J］．Journal of Astronautics，2011，32(9):1971－1977．］