软件学报  2014, Vol. 25 Issue (5): 1085-1100   PDF    
卫星网络路由技术
卢勇2, 赵有健1, 孙富春1, 李洪波1, 倪国旗2, 王殿军1    
1 清华大学 计算机科学与技术系, 北京 100084;
2 空军空降兵学院, 广西 桂林 541003
摘要:卫星网络周期性动态变化的拓扑对路由协议的设计提出了新的挑战.由于传统网络的路由协议不再适用于卫星网络,许多针对卫星网络的路由技术被相继提出来.在简要介绍卫星网络架构与拓扑控制策略的基础上,根据卫星网络路由技术的发展脉络,从分类的角度重点阐述了一些关键路由技术的核心机制、特点以及存在的主要问题.最后,针对应用需求,提出了卫星网络路由技术的发展趋势.
关键词卫星网络     路由    
Routing Techniques on Satellite Networks
LU Yong2, ZHAO You-Jian1, SUN Fu-Chun1, LI Hong-Bo1, NI Guo-Qi2, WANG Dian-Jun1    
1 Department of Computer Science and Technology, Tsinghua University, Beijing 100084, China;
2 Air Force Airborne Academy, Guilin 541003, China
Corresponding author:LU Yong, E-mail: lysky007@126.com
Abstract: The periodic and dynamic topology of satellite networks poses new challenge to the design of routing protocols. Since the routing protocols of conventional networks can not be effectively applied to satellite networks, many new routing techniques for satellite networks were put forward. With an introduction to satellite network architecture and topology control strategies along with the developmental history of routing techniques on satellite networks, this paper summarizes the core mechanism, feature and major problems of some important routing techniques of satellite networks from the classification perspective. Considering application requirements, the paper also suggests the future trends towards the development of routing techniques on satellite networks.
Key words: satellite network     routing    

运行于轨道的卫星通过星间链路构成的新型网络体系成为全新的全球通信模式,在空间信息获取和全球无缝通信领域发挥着地面网络无法比拟的作用.随着第一个全球个人通信Iridium计划[1]的公布,卫星网络开始引起广泛的关注与研究.目前,公开的卫星网络架构主要有Teledesic[2],Iridium[1],Celestri[3]以及NeLS[4].其中, Iridium卫星网络已在轨运营服务.由于地面网络受地理条件、自然灾害等多种因素的限制,卫星网络将为下一代互联网随时随地的全球通信能力发挥基础性的作用.

随着空间信息技术的迅速发展,各国普遍意识到:卫星网络在全球通信、导航定位、气象预测、环境与灾害监测、资源探测和军事应用等方面将发挥越来越重要的作用,以卫星网络为核心的空间网络平台日益成为各国持续研究与发展的战略性工程.2012年10月25日,我国第16颗北斗导航卫星发射的成功,标志着北斗导航卫星系统又迈出重要的一步;同时,卫星组网计划正稳步推进.未来几年,我国发展的卫星将逐步构成主体空间网络系统,在空间信息资源的利用方面将会有实质性的突破.因此,当前卫星网络的研究对于促进我国空间信息技术的发展具有重要的意义.卫星网络路由技术作为卫星网络通信协议的核心,承担着星间数据传输的重任,决定着卫星网络的整体性能.因此,卫星网络路由技术的研究非常必要.

卫星网络拓扑的动态性导致传统的TCP/IP协议不能直接应用于卫星网络.自20世纪90年代以来,国内外针对卫星网络进行了深入的研究,集中体现在星座设计、路由技术、传输层控制以及安全隐私等方面.其中,路由技术是卫星网络的热点研究问题.各种针对卫星网络的路由技术被相继提出来.本文首先对卫星网络的体系结构、拓扑控制策略进行介绍;然后,以卫星网络路由技术的发展过程和应用背景为依据,对不同的路由算法进行分类,从中选择重要的路由算法进行分析,阐述其核心机制、主要特点及存在的主要问题;最后指出卫星网络路由技术的发展趋势,为进一步研究提供参考.

1 卫星网络构架 1.1 卫星分类

卫星的轨道类型与轨道高度决定了卫星的运动特征.卫星轨道一般分为椭圆轨道与圆轨道.椭圆轨道以地球为焦点之一,而圆轨道以地球为圆心.椭圆轨道卫星的运动速度受卫星与地球之间的距离的影响,近地点速度快,远地点速度慢,故一般在远地点建立卫星与地球之间的通信.典型的椭圆轨道卫星有俄国的Molniya系统和Tundra系统[5].与椭圆轨道不同,圆轨道能够保证卫星以恒定速度绕地球运行,便于卫星之间星间链路的建立,因此,卫星网络一般采用圆轨道.此外,由于地球近层宇宙空间存在两个由高能带电粒子组成的强电磁辐射带,高度分别位于1 500km~5 000km与13 000km~20 000km之间,以其发现者范×艾伦(Van Alan)命名,如图 1所示.为了躲避范×艾伦带与大气阻力的影响,低地球轨道(LEO)卫星的轨道高度一般位于500km~1 500km,中地球轨道(MEO)卫星的轨道高度位于5 000km~10 000km,地球同步轨道(GEO)卫星的轨道高度为35 786km.轨道高度决定卫星的轨道周期以及与地面通信的传播时延.与GEO卫星相比,LEO与MEO卫星能够提供更短的传播时延与发射能量需求,广泛应用于卫星网络的设计,但它们更低的轨道高度导致更快的运动速度,增加了通信协议设计的复杂性.

Fig. 1 Satellite orbit selection图 1 卫星轨道选择
1.2 卫星星座设计

迄今为止,主要有两种星座设计用于卫星网络:Walker delta(倾斜星座)与Walker star(极轨道星座).Walker星座一般可形式化为NLxML/NL/F(F=0,1,…,NL-1)[6],其中,ML为单个轨道内卫星数目,NL为轨道数,F为相位因子.图 2显示了两种星座构型.倾斜星座中轨道倾角小于90°,一般位于40°~60°之间,相邻轨道在赤道面的角距离为360°/N;极轨道星座中轨道倾角接近于90°,一般位于80°~90°之间,相邻轨道在赤道面的角距离为180°/N.

Fig. 2 Walker delta and Walker star constellation图 2 Walker delta与Walker star星座

不考虑卫星失效的随机性,卫星网络采用的星座设计决定了拓扑变化特征.一般情形下,卫星网络包含两种类型的星间链路:轨道内相邻的卫星构成轨内链路,相邻轨道相邻的卫星构成轨间链路.极轨道卫星网络存在两个相邻的轨道,其卫星运动方向相反,形成一个所谓的缝隙(seam),如图 3所示.由于在缝隙两侧建立跨缝链路代价昂贵[7],且Gavish等人[8]验证了跨缝链路对端到端时延产生次要的影响,因此一般情况下不考虑极轨道卫星网络的跨缝链路.极轨道卫星网络的轨间链路在进入极地区域时会断开连接,离开极地区域后重新建立连接,直接造成其拓扑的动态性.此外,极轨道卫星网络另一个不利在于对地球覆盖的不均匀:人口密集的赤道附近覆盖稀疏,而人口稀疏的两极区域却覆盖密集.与极轨道卫星网络不同,倾斜轨道卫星网络能够实现均匀的全球覆盖,如图 4所示,但对轨间链路的建立提出更高的要求.随着技术的发展和研究的深入,如果选择合适的星座参数,倾斜轨道卫星网络可建立永久的轨内链路与轨间链路,如Celestri系统.Suzukia等人[9]对该类型卫星网络的星座设计进行了详细的分析.

Fig. 3 Satellite network with Walker star图 3 Walker star 卫星网络

Fig. 4 Satellite network with Walker delta[10]图 4 Walker delta 卫星网络[10]

卫星网络根据不同轨道高度的层次配置,可分为单层卫星网络与多层卫星网络.单层卫星网络由轨道高度相同的卫星通过星间链路构成.根据选择的轨道高度,单层卫星网络又可分为LEO卫星网络和MEO卫星网络.多层卫星网络由不同轨道高度的卫星通过轨间链路和不同卫星层之间的层间链路构成,如双层LEO/MEO卫星网络[11]、双层LEO/GEO卫星网络[12]以及三层LEO/MEO/ GEO卫星网络[13].与单层卫星网络相比,多层卫星网络能够提供更强的计算能力、数据传输能力以及通信协议设计的灵活性.随着空间通信技术的发展和应用需求的提升,多层卫星网络成为未来空间网络发展的主要趋势.

1.3 卫星网络拓扑控制策略

由于卫星严格的轨道运动,卫星网络的动态拓扑呈现周期性与可预测性,这是区别于其他动态网络,如自组织网络、传感器网络的主要特征.基于这一特点,卫星网络的路由技术一般采用拓扑控制策略来屏蔽拓扑的动态性,然后,针对静态的拓扑序列进行路由优化计算.

目前,卫星网络的拓扑控制策略主要包括虚拟拓扑策略[14,15,16]、虚拟节点策略[17, 18]和覆盖域划分方法[19].虚拟拓扑策略将卫星网络的动态拓扑进行离散化,一个系统周期T可划分为若干个时间片[t0,t1],[t1,t2],[t2,t3],…, [tn-1,tn],星间链路的变化仅在时间点t1,t2,…,tn发生,且每个时间片[ti,ti+1]内卫星网络假定拓扑不变.其中,以快照概念[16]为典型代表,其形式化描述由Fischer等人[20]完成.在快照概念中,一旦任意星间链路临时断开或重新连接,一个不同于先前的快照就形成了,每个快照内卫星拓扑固定不变.为了描述卫星网络快照的变化规律,Wang等人[6]给出了LEO卫星网络快照数目与快照长度的理论计算公式.虚拟节点概念最早由Mauger等人[17]提出,后来经Ekici等人[18]推广应用到LEO卫星网络的分布式路由技术.虚拟节点方法的基本思想是:利用卫星逻辑位置的概念,形成一个覆盖全球的虚拟网络,网络中每个节点即为虚拟节点,由最近的卫星提供服务.虚拟节点策略能够屏蔽卫星的运动,考虑卫星网络为固定拓扑结构.目前卫星天线系统主要有两种工作方式:卫星固定足印与地球固定足印模式[21],如图 5所示.在卫星固定足印模式下,卫星与其足印同步移动.在地球固定足印模式下,卫星能够自动调整天线,一段间隔内保持足印固定不变.虚拟节点策略的有效实现,需要借助卫星天线系统地球固定工作模式的支持[21].Lu等人[22]对基于虚拟节点策略的虚拟拓扑进行了形式化、优化设计,并且阐述了其重要特征.此外,Hashimoto等人[19]也提出了覆盖域划分的概念.其基本思想是:将地球表面按等间距划分为多个蜂窝(cell),每个蜂窝由最近的卫星提供服务.由于地球的自转与卫星的运动,采用该策略的每个卫星需要更新网络的拓扑信息,源卫星在转发数据前,需要根据目的节点的地理坐标计算相应的目的卫星.基于虚拟节点与覆盖域划分拓扑控制策略的本质区别在于构建虚拟网络的模式:虚拟节点策略构建的虚拟网络独立于地球的自转,与地球的地理位置无关;基于覆盖域划分的策略将划分的地球区域形式化为虚拟的节点,构成与地球同步运动的虚拟网络.

Fig. 5 Operation mode of satellite antenna[21]图 5 卫星天线工作模式[21]

卫星网络的拓扑控制策略直接影响到路由技术的设计.如果拓扑控制策略产生较多的拓扑变化,则不利于高效路由算法的实现.为了显示不同拓扑控制策略的特点,从天线工作模式需求、拓扑变化数目、适用的星座限制等方面对这3种拓扑控制策略进行了对比分析,见表 1.可以看出:虚拟拓扑策略与覆盖域划分适用限制少,但产生的拓扑变化较多,额外计算负载大;虚拟节点策略适用范围有限,但具有拓扑固定不变、无额外计算负载的优点.实际应用中,需要针对不同的环境采用相应的拓扑控制策略.

Table 1 Comparison of topological control strategy 表 1 拓扑控制策略对比
2 卫星网络主要路由技术分析

通过对卫星网络路由技术的研究,本文根据卫星网络路由技术的发展脉路以及相应特点进行了分类,如图 6所示.基于该分类,我们将系统地阐述一些重要单播与组播路由技术的主要功能、机制与特点.

Fig. 6 Taxonomy of routing technologies for satellite networks图 6 卫星网络路由技术分类
2.1 单层卫星网络路由技术 2.1.1 基于连接的路由技术

为了融合ATM网络与电路交换语音网络在卫星网络中的应用,早期卫星网络的路由技术主要采用基于连接的路由模式.Werner等人[14]首先在LEO卫星网络中引入ATM网络路由的概念,将路由策略分两个过程:首先,采用虚拟拓扑方法,将连续时变的卫星网络离散化为一系列静态拓扑,离散时间片选取以物理拓扑与链路长度的变化为依据,然后计算所有离散拓扑序列中任意卫星之间的路径集合;其次,根据优化目标从路径集合中选择最优路径.Chang等人[15, 23, 24]将LEO卫星网络模型为系统周期内一系列等长时间的有限状态自动机FSA(finite state automata),利用卫星之间的可视性建立每个状态的可视矩阵,然后根据流量需求计算最优链路分配机制,实现有限链路资源的充分利用.由于系统周期内大量的离散拓扑序列,这些算法一般采用集中计算方式,缺乏对流量拥塞、卫星失效的自适应能力.此外,这些算法仅仅考虑了动态拓扑控制策略与星上路由,没有处理链路或星间转交引起的路径变化问题.

根据前面的描述,在极轨道LEO卫星网络中,轨间链路会出现临时关闭与重建,链路转交频繁发生,导致已经建立的星上路径需要频繁更新,即需要重路由过程.显然,基于连接的路由策略中频繁的重路由会导致额外的信号负载和系统性能的降低.为了减少链路转交次数,Werner等人[25]提出了LEO卫星网络中ATM路由的优化算法,优化目标为尽可能减少链路转交次数.为了进一步满足时延敏感性应用如语音通话的需求,Werner等人[26]在卫星网络ATM路由机制上引入滑动时间窗口的概念,时间窗口尺寸大于平均呼叫持续时间,并保证在时间窗口内产生最少的链路转交次数,从而减少由链路转交引起的时延抖动.由于LEO卫星的高速运动(26 000km/h,即7km/s),会话期间服务于地面终端的卫星可能需要切换,该过程称为星间转交.它主要包括两种:如果会话期间服务于地面终端的卫星切换到同轨道下一颗卫星,该转交称为轨内转交;如果切换到相邻轨道的卫星,则称为轨间转交.前面的算法虽然考虑了星上链路转交的问题,但并未考虑星间转交的问题.

为了解决星间转交引起的重路由问题,Uzunalioglu等人[27]提出了针对极轨道LEO卫星网络的FHRP重路由协议(footprint handover rerouting protocol).该协议利用极轨道LEO卫星网络拓扑的规则性与可预测性,提出了星间转交发生时依然维持路径最优化的规则,主要包括增量与足印重路由两个阶段:第1阶段主要解决地面源与目的终端之一发生星间转交时路径变化的问题;第2阶段主要用于源与目的终端都发生星间转交后的重路由问题.基于FHRP,Uzunalioglu等人[28, 29]进一步提出以减少链路转交次数为目的概率路由协议PRP (probabilistic routing protocol).由于语音的呼叫持续时间为随机变量,PRP寻找会话连接期间以一定的概率p不会发生链路转交的路径,即满足:

P(min(TC,Thr)<Ti,lh)>p,

其中,TC为剩余会话持续时间,Thr为路径建立与星间转交重路由之间的间隔,Ti,hr为路径建立与卫星i发生链路转交的间隔.实验结果显示:通过在减少链路转交次数与降低呼叫阻塞概率之间的折中,概率p值被选为0.9时能够产生较好的效果.尽管PRP与FHRP能够以较小的额外通信、计算与存储负载快速实现星间或链路转交时的重路由问题,然而它们以时间均衡流量为假定,与现实复杂的流量分布相违背.而且,由于PRP或FHRP缺乏流量平衡能力,单一的计算路径容易被突发流量拥塞,而源与目的端之间其他路径上的链路不被充分利用.

大部分早期基于连接的路由算法集中于解决路径变化引起的重路由问题,一般采用离线集中计算方式,缺乏对流量拥塞与卫星失效的快速响应.随着Internet在21世纪的迅速推广,基于无连接的路由技术在卫星网络中得到广泛的应用与发展.

2.1.2 无连接路由技术

(1) 基于IP的路由技术

Hashimoto等人[19]首先提出了针对LEO卫星网络基于IP的路由算法.该算法利用覆盖域划分的概念,将地球表面按边长160km的长度划分为宏蜂窝,每个宏蜂窝进一步划分为边长相等的9个蜂窝,一颗LEO卫星可最多覆盖64个宏蜂窝.每个IP分组被分片为多个卫星信元S_cell,每个S_cell头部包含如下信息á宏蜂窝ID;蜂窝ID;终端ID;数据报ID;序列号;TTLñ,其中,前3个域构成类似IP地址的虚地址VID,且源终端通过地面网关获得目的终端的虚地址VID.星间路由时采用分布式转发,每个卫星计算全局拓扑信息,利用S_cell的地址计算最短的下一跳.Ekici等人[18, 30]进一步提出了分布式数据报路由协议DRA(datagram routing algorithm).不同于覆盖域划分策略,DRA采用虚拟节点策略屏蔽卫星的移动性,考虑极轨道LEO卫星网络具有静态的二维mesh拓扑,并采用分布式策略实现最短传播时延路由.与前面的路由算法相比,DRA仅仅根据目的节点的位置来转发分组,几乎不需要额外的计算与存储负载.Henderson等人[31]也提出了针对LEO卫星网络的分布式路由算法.该算法的基本过程是:首先以目的卫星为中心,在一定半径范围内进行链路状态洪泛,利用Dijkstra最短路径算法计算最优路径;而对范围之外的路由则利用网络的二维mesh拓扑特点,按目的节点的位置转发分组.尽管也提出了其他一些基于IP的分布式路由算法[32,33,34],但基本路由策略仍与DRA相同.除了极大程度地降低了路由的计算与存储负载,这些分布式算法能够在一定程度上消除卫星失效与流量拥塞的影响,但它们的路由决定局限于本地信息,不能从全局解决这些问题.例如,DRA实际上只能容忍任意卫星的一个邻居出现失效,如果某卫星两个邻居同时失效,则DRA缺乏有效的容忍策略实现容错路由.而且,由于高纬度地区的轨间链路距离更短,其传播时延大大低于赤道附近轨间链路的传播时延,DRA容易导致高纬度地区的卫星链路发生拥塞.尽管Lu等人[35]将二维mesh并行处理系统的容错路由策略进行改进,在路由层面将极轨道LEO卫星网络发展为自适应无死锁的容错路由系统,并利用分布式策略以降低系统负载,但他们没有考虑链路拥塞问题.随着基于Internet应用的迅速增长,这些分布式路由算法由于优化目标的限制导致路由性能有限,已经不能满足日益增长的多媒体应用如语音、视频服务等的需要.

为了提高LEO卫星网络基于IP的路由性能,Bai等人[36]提出了另一个分布式的路由协议DHRP(distributed hierarchical routing protocol).与DRA不同,DHRP将链路的传播时延与排队时延同时纳入路径代价评估.为了减少链路状态洪泛代价,DHRP对每个轨道设置一个轨道发言者,由它负责收集本轨道面内所有链路的状态信息;同时,与其他轨道面的轨道发言者进行链路状态信息交换,并利用Dijkstra最短路径算法计算最优路径.为了提高容错能力,DHRP对每个轨道也设置一个备份发言者,应付轨道发言者失效的情形.可见,DHRP利用LEO卫星网络拓扑的规则性,以较低的链路状态洪泛代价实现了类似OSPF的路由协议,达到了比DRA更好的路由性能.尽管如此,DHRP仍属于单路径路由,突发流量容易引起链路拥塞,DHRP与DRA缺乏流量平衡能力.

(2) 流量分配路由技术

· 区分服务路由

根据不同通信业务不同的传输要求,Svigelj等人[37]将流量分为3类:A类为典型的交互式实时数据传输,如VoIP(voice-over-IP)和交互式视频,这类应用以最小端到端时延为优化目标;B类为VoD(video-on-demand)与大文件传输应用,以最大吞吐量为优化目标;C类为最大努力传输,适宜无QoS请求的数据服务.基于该流量分类,路由过程针对不同的流量类分别进行优化,其中,A类与C类流量的链路代价度量属于加性,可直接采用Dijkstra最短路径算法;B类流量的优化需要同时满足最少跳数与最大可行带宽目标,属于凹性度量,Svigelj等人采用Bellman-Ford最短路径算法[38]进行路由表计算.在数据转发过程中,缓冲队列按A类、B类、C类的优先级顺序进行转发.根据同样的流量分类,Papapetrou等人[39]提出了多服务按需路由协议MOR(multiservice on-demand routing).MOR也单独对各类流量进行路由优化,但采用按需路由协议LAOR[40]的思想,路由更新更能反映网络即时的状态,而且同时适用于Walker star与Walker delta星座.Svigelj等人[37]提出的路由策略没有考虑Walker star星座卫星网络的链路转交问题.

· 流量平衡路由

Mohorcic等人[41]研究了倾斜轨道卫星网络Celestri在均匀流量分布下最短路径路由的特性,结果显示,星上流量的分布受地理位置的影响.由于高纬度地区轨间链路更短的传播时延,流量趋向于向高纬度地区的卫星集中.为了解决这一问题,Mohorcic等人[42]提出了ALR(alternate link routing)路由策略.ALR根据Celestri星座固定星间链路的特性,采用类似Internet的OSPF路由策略进行链路状态信息交互与路由更新.为了避免高纬度地区卫星链路的流量拥塞,ALR分别计算最优与次优路径,其调度策略包括ALR-S与ALR-A:ALR-S迫使每个分组在源卫星节点使用次优路径的下一跳,而在中间卫星节点使用最优下一跳;ALR-A对任意分组在任意卫星节点交替使用最优与次优下一跳.结果显示:ALR与单路径最短时延路由相比,减少了近50%的流量高峰.为了进一步显示卫星网络自适应路由在非均匀流量分布下的特性,Mohorcic等人[43]利用地球热点区域的分布规律建立流量分布场景,结果显示,星上流量依旧偏向于高纬度区域的卫星链路.为了解决该问题,相同的ALR路由策略也被应用于非均匀的流量场景[44].Korcak等人[45]提出了基于优先级的自适应路由算法PAR(priority-based adaptive routing).由于LEO卫星网络的二维mesh拓扑特征,任意一对卫星之间可能存在多条最短路径,构成最短路径集. PAR根据星间链路过去利用率与当前缓冲区大小在最短路径集合中选择下一跳,在一定程度上解决了高纬度地区流量集中的问题.此外,Bai等人[46]提出了LEO卫星网络的多路径路由算法CEMR(compact explicit multi- path routing).CEMR中每颗卫星为每对源目的节点计算两条路径,源卫星的流量被划分为相等的两部分,分别在两条路径上传输,从而平衡网络的流量负载.由于ALR[42],PAR[45]与CEMR[46]针对平衡流量的路由决定限于本地信息,并不能从全局角度解决流量平衡问题.

Tarik等人[47]提出了反应式流量平衡策略ELB(explicit load balancing).在ELB机制中,某卫星如果发现自己的链路从空闲进入忙碌或拥塞状态,就发送信号至邻居.邻居卫星收到信息后更新路由表,搜索其他后备路径,并降低至忙碌或拥塞卫星的数据发送率.尽管ELB能够降低丢包率,但当网络较为拥塞时,会产生大量的反馈信号,进一步恶化系统的性能.为了打破ELB的局限,Rao等人[48]提出了基于代理的流量平衡路由算法ALBR (agent-based load balancing routing).ALBR使用两种类型的代理:每个卫星的静态代理负责周期性地评估链路代价和计算路由表,而移动代理随机选择最远目的节点进行路径发现过程.ALBR的另一个特色是在链路代价评估中引入以卫星地理位置为参考的修改因子,从而隐含了地球流量分布不均匀的特性.实验结果显示:ALBR比ELB能够实现更好的流量平衡性能,并保证网络高负载情形下更大的吞吐率和更少的丢包率.此外, Kucukates等人[49]也提出了针对LEO卫星网络流量平衡的MFMR(minimum flow maximum residual)路由算法. MFMR算法也利用最短路径集的概念,但为了避免流量向高纬度区域的轨间链路集中,MFMR考虑所有源与目的之间最短路径区域内所有轨间链路有相同的长度.MFMR以最小链路最大流为优化目标,从而最大化网络的吞吐量.由于该优化目标问题为NP困难问题,MFMR算法将该问题分为两个过程:首先搜索最短路由集,确定路由的固定拓扑范围;然后,针对固定的拓扑采用修改的Dijkstra最短路径算法进行路由优化计算.

· QoS路由

Ercetin等人[50]提出了针对LEO卫星网络的QoS路由PRP(predictive routing protocol).PRP将卫星的足印划分为L个时间片,每个时间片内进行链路状态信息交换,并利用卫星网络拓扑的确定性预测未来一段时间内星间链路流量的变化.PRP以最大化最小剩余带宽为优化目标,为每个呼叫计算K条路径,从中选择以最小链路变化和流量平衡为目的的最优路径.但PRP没有考虑链路较交的问题,且星上计算负载偏大.Chen[51]提出了LEO卫星网络中同时考虑星间转交与链路转交的QoS路由协议QRA(QoS-based routing algorithm).与PRP不同,QRA将整个路由分为3个阶段:用户数据链路UDL路由、星间路由与转交重路由.QRA的目的是:在维持QoS服务的前提下,尽可能地减小时延抖动与重路由频率.此外,QRA也考虑了地球自转与高纬度地区卫星重叠覆盖的因素.但QRA仅考虑了星间链路的传播时延,路由性能有限.Rao等人[52]提出了针对LEO卫星网络的源QoS路由算法MPQR(multi-path QoS routing).当卫星收到地面终端的数据传输请求与QoS目标时,MPQR计算同时满足时延与带宽限制的最优路径;同时,MPQR将地球热点区域的分布特性引入链路代价评估,保证MPQR具有平衡流量的功能.由于MPQR基于遗传算法,对星上计算能力提出了较高的要求.

Cao等人[53]将交叉熵方法(cross entropy method)引入卫星网络的QoS路由计算,提出了针对LEO卫星网络的CEAARS(crossentropy accelerated ant routing system)路由策略.CEAARS也采用类似于ALBR[48]基于代理或蚂蚁的路径代价探索、评估与最优计算,但CEAARS包含3类路径前向蚂蚁:目的蚂蚁(destination-oriented ants)、标准蚂蚁(normal ants)和搜索蚂蚁(explorer ants).路由更新时,目的蚂蚁根据目的节点的位置,通过最短跳数路由至目的节点,从而提高最优与次优路径计算的收敛速度.当目的蚂蚁探索失败时,由标准蚂蚁获取最优路径.目的蚂蚁与标准蚂蚁按照一定的概率分布从邻居节点中选择下一跳,而搜索蚂蚁随机选择下一跳,用于搜索所有可行路径.最后,回退蚂蚁(backward ants)根据最优目标对前向蚂蚁探索的路径进行信息更新.Gao等人[54]提出了基于流量预测的分布式路由协议TPDRA(distributedroutmg algorithm with traffic prediction).TPDRA也采用代理去进行网络状态收集与路由更新,但与ALBR[48]和CEAARS[53]不同,TPDRA采用RBF神经网络(radial basis function neural network)机制,具有流量预测功能.尽管这些基于代理的QoS路由算法会产生额外的信号负载,但它们具有较强的路由自适应能力,并且能够保证一定的路由性能.

(3) 按需路由技术

针对卫星网络拓扑变化的特点,Papapetrou等人[40]首先引入无线自组织网络中反应式按需路由AODV[55]的思想,提出了针对LEO卫星网络的辅助定位按需路由协议LAOR(location-assisted on-demand routing).当通信请求到达时,为了降低额外的信号负载,LAOR根据卫星网络的二维mesh拓扑特征,限制路由区域,避免消息在整个网络中的洪泛;然后,LAOR调用路径发现过程寻找最短时延路径.由于星间链路在极地区域切换,LAOR利用路由入口管理过程按一定的周期对失效的路径进行更新.LAOR在路径建立阶段获取的链路状态信息更接近网络的真实负载状态,因此仿真结果显示:LAOR比集中式的算法产生更小的端到端时延与时延抖动,并且以较低的通信负载达到更高的数据传输率和平衡流量的目的.为了满足不同服务的需要,前面已经介绍,Papapetrou等人[39]进一步将LAOR扩展为多服务按需路由协议MOR.尽管LAOR与MOR在一定程度上能够达到的平衡网络流量的目的,但其路由请求区域为局部区域,并不能从全局角度实现流量平衡的目的.

2.1.3 组播路由技术

Ekici等人[56]首先提出了针对LEO卫星网络的IP组播路由算法MRA(multicast routing algorithm).该算法通过分布式DRA路由算法[18]创建基于源的组播树,其优化目标为最小化组播分组复制数目,仿真结果显示:与LEO卫星网络中应用一些传统组播路由算法相比,MRA具有相对较好的性能.为了解决MRA的信道资源浪费问题,Chen等人[57]提出了LEO卫星网络中基于核心树的组播路由算法,主要包括CCST(core-cluster combination-based shared tree)与w-CCST算法.与MRA相比,CCST算法能够提高带宽利用率.而且通过引入权重因子,w-CCST算法能够支持实时组播服务,并降低平均的端到端传播时延.Yang等人[58]进一步提出了LEO卫星网络中基于构建直线steiner树的组播路由算法.与MRA[56]相比,该算法以最小化带宽为优化目标,采用整数线性规划方法计算最小组播树.仿真结果显示:与基于最短路径树的算法相比,该算法将使用带宽降低到40%以下,且可扩展性较好.

2.2 多层卫星网络路由技术 2.2.1 基于IP的路由技术

为了打破单层LEO卫星网络在路由性能与收敛上的局限,Lee等人[59]首先提出了多层卫星网络体系的设计和一个QoS路由协议HQRP(hierarchical QoS routing protocol).HQRP利用MEO卫星相对较强的计算能力,将路由计算从LEO层移动至MEO层,LEO卫星直接向MEO卫星上报链路状态信息,通过MEO层实现快速的路由计算与收敛.此外,HQRP建议通过MEO层转发LEO层长跳数分组,从而减少LEO层的流量负载.

Akyildiz等人[13]提出了针对3层LEO/MEO/GEO卫星网络的路由协议MLSR(multilayered satellite routing). MLSR首先引入卫星组与组管理的概念:LEO卫星在某MEO卫星的覆盖区域内形成LEO组,MEO卫星在某GEO卫星的覆盖区域内形成MEO组,如图 7所示.链路状态信息由下层卫星发送至上层卫星.为了减少计算的复杂性,每个LEO组被定义为单个元节点,由GEO卫星进行全局路由计算,并通过MEO卫星提炼LEO层的路由表.为了及时反映拓扑的变化,MLSR的路由更新周期应小于最小卫星组成员变化的间隔.为了降低系统复杂性,Chen等人[11]提出了针对双层LEO/MEO卫星网络的路由协议SGRP(satellite grouping and routing protocol). SGRP进一步发展卫星组与组管理的概念.与MLSR相同,LEO层依然采用虚拟节点的概念,但每颗LEO卫星组不再被表示为单个元节点,且每颗LEO卫星选择最长覆盖时间的MEO卫星作为组管理者.由于LEO组成员变化的时间间隔不均匀,SGRP选择每隔2分钟或4分钟进行路由更新.路由更新过程是:LEO卫星直接上报链路状态信息至组管理者,由MEO层进行链路状态信息交换与路由计算,最后将路由表发送至LEO层.SGRP主要实现最短时延路由以及对LEO层链路拥塞与卫星失效的快速反应机制.

Fig. 7 Hierarchical organization for multi-layered satellite networks图 7 多层卫星网络等级组织
2.2.2 QoS路由技术

为了满足多媒体应用的需要,提出了一些针对多层卫星网络的QoS路由算法被提出.Bayhan等人[60]提出了针对双层LEO/MEO卫星网络QoS路由协议ARPQ(adaptive routing protocol for quality of service).ARPQ主要应用于时延敏感性场景,如VoIP(voiceover Internet protocol).它采用与SGRP相同的路由机制,其不同之处在于ARPQ的转发机制:ARPQ对语音分组首先进行分类,如果分组的路径传输时间小于某一阈值,则通过LEO层进行传输;如果大于该阈值,则由MEO层负责传输;在分组转发过程中,采用优先语音分组的排队策略满足其QoS目标.为了避免拥塞,ARPQ需要每个卫星连续监视自己的链路队列,根据队列利用率与预定义的阈值来判断链路状态,通过调整转发策略避免流量拥塞.ARPQ属于反应式拥塞避免机制,与ELB策略[47]类似,因此预测拥塞能力有限.Zhou等人[61]提出了基于LEO/MEO双层卫星网络的QoS路由协议HDRP(hierarchical and distributed QoS routing protocol).HDRP仍然采用卫星组与组管理的概念,但有一些新的特点:MLSR与SGRP采用虚拟节点的概念屏蔽LEO卫星的移动性,然而一旦LEO卫星运动到新的逻辑位置,其路由表就必须传送至其后继卫星,从而产生额外的负载;HDRP中的LEO层并未采用虚拟节点的概念,以卫星实际位置为组成员定位,因此系统中同时存在LEO与MEO卫星各自的轨道运动,导致组成员的变化更加复杂、频繁.为了减少系统快照数目,HDRP提出了快照合并策略,极大地减少了系统周期内快照变化的数目.HDRP主要提供带宽限制下的最短时延路径,其路由方式分为域内路由与域外路由两种:如果分组的源与目的卫星属于同一LEO组,则该分组通过LEO层进行转发;如果分组的源与目的卫星属于不同LEO组,则该分组通过MEO层进行转发.可见,HDRP进一步发展了Lee等人[59]提出的关于长跳分组由MEO层转发的建议,从而减轻了LEO层的传输负载.当相邻的源与目的卫星属于不同的LEO组时,HDRP将通过MEO层传输,可能产生相对较长的时延.随着启发式算法在QoS路由计算中的应用,Long等人[62]也提出了基于针对双层LEO/MEO卫星网络的QoS路由算法.该路由算法采用与HDRP相同的拓扑控制策略,通过遗传算法、蚁群算法等进一步优化卫星网络的路由性能.

尽管基于卫星组与组管理概念的多层卫星网络路由技术在一定程度上降低了计算的复杂性与通信的额外负载,然而该拓扑控制策略并不能保证数据传输的可靠性.卫星组与组管理概念的主要局限体现在:其拓扑控制策略仅考虑卫星组成员的变化,并未考虑负责数据传输的LEO层的拓扑变化.事实上,尽管某个时间间隔内卫星组成员保持不变,但LEO层自身的拓扑仍然可能发生变化,例如,LEO层的轨间链路在极地区域的临时断开或重建.即使LEO层利用虚拟节点的概念来屏蔽卫星的移动,但当LEO卫星失效时,LEO层的拓扑动态性依然不可避免[22].当且仅当卫星组与组管理策略能够精确地捕获负责数据传输卫星层的拓扑变化时,其数据传输可靠性才能得到保证.Lu等人[63]对此进行了阐述,并提出了一个可行的方案.

2.2.3 流量平衡路由技术

由于流量平衡技术能够提高网络的吞吐量和降低丢包率,有利于QoS路由的实现,多层卫星网络的路由研究也转向流量平衡问题.根据卫星网络拓扑的可预测性,如果存在流量拥塞区域,任意时刻进入该拥塞区的卫星就能提前确定.基于此思想,Nishiyama等人[12]提出了针对双层LEO/GEO卫星网络的流量平衡与QoS路由策略.它将用户流量分为3类:流量类A为时延敏感性应用,具有最高优先级路由,即使位于拥塞区也按最优路径转发;流量类B属于视频流类应用,当位于拥塞区时可进行偏绕路由,但只能通过LEO层进行传输;流量类C属于最大努力传递服务,可通过GEO卫星进行转发.当卫星进入拥塞区域时,它立即通知它的邻居,通过信息交互,拥塞区域附近的卫星能够预测自己是否将进入该区域,并提前进行流量偏绕路由,从而达到平衡流量的目的.对于双层LEO/MEO卫星网络,一颗MEO卫星覆盖多颗LEO卫星,当LEO卫星进入流量密集区域时,为了避免拥塞,位于流量密集区域的LEO卫星需要转发部分流量至MEO卫星,这将导致MEO卫星可能发生流量拥塞.为了避免这种情况的发生,Kawamoto等人[64]利用MEO层重叠覆盖的特性,允许一颗发生流量拥塞的LEO卫星同时向多个覆盖它的MEO卫星分配流量.Kawamoto等人主要讨论了单个LEO卫星能同时与多个MEO卫星通信的最优数目D,分析了D与LEO与MEO层的高度差、传播时延与排队时延的关系,从而以最小的传输时延标准来确定D的值. Nishiyama等人[65]进一步提出了针对双层LEO/MEO卫星网络的流量平衡路由策略.该策略基本上采用了ARPQ[60]的思想,但ARPQ仅将远距离实时流量通过MEO层传输,没有考虑其他流量的传输策略,不能从全局上达到流量平衡的目的.Nishiyama等人[65]的主要贡献是从理论上确定了流量偏绕阈值qd.在路由过程中,如果流量的距离超过qd,则通过MEO层进行传输;否则,通过LEO层进行传输.此外,他们的路由更新策略也与传统的卫星组与组管理模型不同,其路由计算在任意链路转交时进行,从而保证了数据传输的可靠性.但他们的流量平衡策略基于地球用户与流量均匀分布的假定,与实际应用环境存在差异.

2.2.4 组播路由技术

目前,多层卫星网络组播路由的主要代表为Akyildiz等人[66]提出的3层GEO/MEO/LEO卫星网络组播路由算法.该算法采用修改的MLSR算法[13]构建基于源的组播树,并以最小化组播树代价为优化目标.仿真结果显示:与多层卫星网络中应用传统基于核心树的组播路由算法相比,该算法在时延和树代价上有更好的性能.

3 路由分析与比较

卫星网络的路由技术随着用户应用需求与应用场景的变化而发展.由于不同的路由技术针对不同的应用背景,很难对它们进行优劣区分.为了描述卫星网络不同路由技术的特点,我们从计算模式、优化目标、错误容忍反应能力、星上负载等方面分别对单层与多层卫星网络的单播路由技术进行了分析对比,见表 2表 3.

Table 2 Comparison of routing technologies for single layered satellite networks 表 2 单层卫星网络路由技术对比

Table 3 Comparison of routing algorithms for multi-layered satellite networks 表 3 多层卫星网络路由算法对比
4 未来研究方向

由于拓扑的动态性、地球人口与流量分布的不均匀、用户需求的提升与卫星处理能力不能及时更新的矛盾,以及复杂空间环境等因素的影响,卫星网络的路由研究一直是一个挑战性的问题.迄今为止,尽管已提出了许多路由技术,但没有一个公认的路由协议进入IETF标准,仍有一些关键的问题需要研究:

(1) 随着空间通信技术的发展,未来卫星网络生存的空间环境较为复杂,不仅存在自然因素,如光电干扰、能量受限、物理故障等,也存在人为因素,如军事打击等,对卫星网络的可生存性造成较大的挑战.与地面设备相比,卫星设备维护的高代价与长周期决定了卫星故障的持久性.目前,大部分路由协议很少考虑卫星网络路由的可生存性问题,尽管Lu等人[32]提出了随机卫星失效情形下卫星网络的容错路由策略,但没有考虑路由性能问题.研究高效鲁棒的路由策略,对于维持卫星网络在未来太空环境下的可生存性和通信性能具有一定的价值.

(2) 未来卫星网络的空间组网机制将变得更为灵活,各类飞行装置可能临时或永久建立与卫星网络的连接,从而形成层次更为复杂的空间网络,为地面提供更为灵活、丰富的数据传输服务.因此,在通信业务日益多样化的背景下,如何有效地利用卫星网络资源,提升满足QoS的路由机制,依然是重要的研究课题.

(3) 卫星网络的路由复杂度问题需要进一步研究.目前,静态网络的路由复杂性已经得到深入的研究,形成了较完善的复杂性结果[[67],[68],[69],[70],[71],[72]].尽管Kucukates等人[49]推测卫星网络的路由问题是NP-hard问题,但没有给出形式化的证明.由于拓扑的动态性,预先计算的路径在卫星网络中不能保证其确定性.根据Lu等人[22]的分析,尽管在地球固定足印模式下不存在路径拉伸与收缩问题,但这些问题在卫星固定足印模式下依然存在.这将在路由复杂性方面产生3个新问题:最小化路径拉伸、最大化路径收缩与最大化路径保持问题.其中,最小化路径拉伸能够最大限度地避免卫星的移动性对通信的影响;最大化路径收缩能够最大限度地利用卫星的移动性;最大化路径保持问题能够最大限度地维持初始计算路径的确定性,有利于端到端时延的稳定.对于最大化路径保持问题,已经提出了一些相应的算法[11, 18, 19],主要通过尽可能地减少会话期间的链路或卫星转交次数达到目的.对于另外两个问题,则很少有文献进行分析研究.卫星网络路由复杂性的研究,对于推动卫星网络路由技术的发展具有一定的指导意义.

5 结 论

卫星网络的全球覆盖特性有力地拓展了网络的通信空间,推动了下一代互联网与星际网络的发展.未来空间技术的发展和应用需求的提升,将推动卫星网络与地面网络的无缝融合,承担更加丰富的通信服务.本文从发展的角度对卫星网络路由技术进行了分类,重点阐述了不同类型代表性路由技术的核心工作机制、主要特点和存在的问题,最后指出了卫星网络路由技术今后的研究方向.希望本文能够为进一步的研究提供参考.

参考文献
[1] Leopold RJ, Miller A. The Iridium communication system. IEEE Potentials, 1993,12(2):6-9 [doi: 10.1109/45.283817].
[2] Sturza MA. Architecture of teledesic satellite system. In: Proc. of the 4th Int’l Mobile Satellite Conf. (IMSC’95). Vancouver: Britannia Community Services Centre, 1995. 212-218.
[3] Tomren D, Kleiner N, Matteo D, Olds K. Optical intersatellite links for the celestri satellite communications system. In: Proc. of the Summaries of Papers Presented at the Conf. on Lasers and Electro-Optics, Technical Digest. San Francisco: IEEE, 1998.347 [doi: 10.1109/CLEO.1998.676275].
[4] Suzuki R, Nishiyama I, Motoyoshi S, Morikawa E, Yasuda Y. Current status of NeLS project: R&D of global multimedia mobile satellite communications. In: Proc. of the 20th Int’l Communications Satellite Systems Conf. and Exhibit (AIAA-2002-993). Reston: AIAA, 2002. 12-15.
[5] Maral G, Bousquet M. Satellite Communication Systems. Malden: Wiley and Sons, Inc., 1998. 44-45.
[6] Wang J, Li L, Zhou M. Topological dynamics characterization for LEO satellite networks.Computer Networks, 2009,51(1):43-53 [doi: 10.1016/j.comnet.2006.04.010].
[7] Ferreira J, Galtier J. Topological Design, Routing and Hand-Over in Satellite Networks. Handbook of Wireless Networks and Mobile Computing. London: Wiley, 2005. 473-507.
[8] Gavish B, Kalvenes J. The impact of intersatellite communication links on LEOS performance.Telecommunication Systems, 1997, 8(2-4):159-190 [doi: 10.1023/A:1019109420506].
[9] Suzuki R, Yasuda Y. Study on ISL network structure in LEO satellite communication systems.Acta Astronautica, 2007,61(7): 648-658 [doi: 10.1016/j.actaastro.2006.11.015].
[10] Long F. Research on satellite network robust QoS-aware routing [Ph.D. Thesis]. Beijing: Tsinghua University, 2010 (in Chinese with English abstract).
[11] Chen C, Ekici E. A routing protocol for hierarchical LEO/MEO satellite IP networks.ACM/Kluwer Wireless Networks Journal, 2005,11(4):507-521 [doi: 10.1007/s11276-005-1772-1].
[12] Nishiyama H, Kudoh D, Kato N, Kadowaki N. Load balancing and QoS provisioning based on congestion prediction for GEO/LEO hybrid satellite networks. Proc.of the IEEE, 2011,99(11):1998-2007 [doi: 10.1109/JPROC.2011.2157885].
[13] Akyildiz IF, Ekici E, Bender MD. MLSR: A novel routing algorithm for multi-layered satellite IP networks. IEEE/ACM Trans.on Networking, 2002,10(3):411-424 [doi: 10.1109/TNET.2002.1012371].
[14] Werner M. A dynamic routing concept for ATM-based satellite personal communication networks.IEEE Journal on Selected Areas in Communications, 1997,15(8):1636-1648 [doi: 10.1109/49.634801].
[15] Chang HS, Kim BW, Lee CG, Choi YH, Min SL, Kim CS. Topological design and routing for low-earth orbit satellite networks. In: Proc. of the IEEE GLOBECOM. Piscataway: IEEE, 1995. 529-535 [doi: 10.1109/GLOCOM.1995.501983].
[16] Gounder VV, Prakash R, Abu-Amara H. Routing in LEO-based satellite networks. In: Richardson TX, ed. Proc. of the Wireless Communications and Systems Workshop. Piscataway: IEEE, 1999.2211-2216 [doi: 10.1109/ETWCS.1999.897340].
[17] Mauger FR, Rosenberg C. QoS guarantees for multimedia services on a TDMA-based satellite network.IEEE Communications Magazine, 1997,35(7):56-65 [doi: 10.1109/35.601743].
[18] Ekici E, Akyildiz IF, Bender MD. A distributed routing algorithm for datagram traffic in LEO satellite networks. IEEE/ACM Trans. on Networking, 2001,9(2):137-147 [doi: 10.1109/90.917071].
[19] Hashimoto Y. Design of IP-based routing in a LEO satellite network. In: Proc. of the 3rd Int’l Workshop on Satellite-Based Information Services. New York: ACM, 1998. 81-88.
[20] Fischer D, Basin D, Engel T. Topology dynamics and routing for predictable mobile networks. In: Proc. of the ICNP 2008. Orlando: IEEE Communications Society, 2008.207-217 [doi: 10.1109/ICNP.2008.4697039].
[21] Omer K, Fatih A. Virtual topology dynamics and handover mechanisms in earth-fixed LEO satellite systems.Computer Networks, 2009,53(9):1497-1511 [doi: 10.1016/j.comnet.2009.01.010].
[22] Lu Y, Sun FC, Zhao YJ. Virtual topology for LEO satellite networks based on earth-fixed footprint mode.IEEE Communications Letters, 2013,17(2):357-360 [doi: 10.1109/LCOMM.2013.011113.122635].
[23] Chang HS, Kim BW, Lee CG, Min SL, Choi YH, Yang S. Performance comparison of static routing and dynamic routing in low earth orbit satellite networks. In: Proc. of the IEEE VTC. Piscataway: IEEE, 1996.1240-1243. [doi: 10.1109/VETEC.1996.5015 10].
[24] Chang HS, Kim BW, Lee CG. FSA-Based link assignment and routing in low-earth orbit satellite networks. IEEE Trans.on Vehicular Technology, 1998,47(3):1037-1048 [doi: 10.1109/25.704858].
[25] Werner M, Delucchi C, Vogel H, Maral G, De Ridder J. ATM-Based routing in LEO/MEO satellite networks with intersatellite links.IEEE Journal on Selected Areas in Communications, 1997,15(1):69-82 [doi: 10.1109/49.553679].
[26] Werner W, Berndl G, Edmaier B. Performance of optimized routing in LEO intersatellite link networks. In: Proc. of the IEEE 47th Vehicular Technology Conf. Piscataway: IEEE, 1997.246-250 [doi: 10.1109/VETEC.1997.596357].
[27] Uzunalioğlu H, Akyildiz IF, Yesha Y, Yen W. Footprint handover rerouting protocol for low Earth orbit satellite networks.ACM/Kluwer Wireless Networks Journal, 1999,5(5):327-337 [doi: 10.1023/A:1019127801155].
[28] Uzunalioglu H, Akyildiz IF, Bender MD. A routing algorithm for LEO satellite networks with dynamic connectivity.ACM-Baltzer Journal of Wireless Networks, 2000,6(3):181-190 [doi: 10.1023/A:1019133429805].
[29] Uzunalioglu H. Probabilistic routing protocol for low earth orbit satellite networks. In: Proc. of the ICC’98. Piscataway: IEEE, 1998.89-93 [doi: 10.1109/ICC.1998.682592].
[30] Ekici E, Akyildiz IF, Bender MD. Datagram routing algorithm for LEO satellite networks. In: Proc. of the IEEE INFOCOM. Piscataway: IEEE, 2000.500-508 [doi: 10.1109/INFCOM.2000.832223].
[31] Henderson T, Katz H. On distributed geographic based packet routing for LEO satellite networks. In: Proc. of the IEEE Globecom. Piscataway: IEEE, 2000.1119-1123 [doi: 10.1109/GLOCOM.2000.891311].
[32] Wang KD, Yi KC, Tian B, Wu CK. Packet routing algorithm for polar orbit LEO satellite constellation network.Science in China Series F: Information Sciences, 2006,49(1):103-127 [doi: 10.1007/s11432-004-5596-x].
[33] Sanctis MD, Cianca E, Ruggieri M. IP based routing algorithm for LEO satellite networks in near polar orbits. In: Proc. of the 2003 IEEE Aerospace Conf. Piscataway: IEEE, 2003. 3_1273-3_1280 [doi: 10.1109/AERO.2003.1235242].
[34] Papapetrou E, Pavlidou FN. Distributed load-aware routing in LEO satellite networks. In: Proc. of the IEEE Globecom. Piscataway: IEEE, 2008.1-5 [doi: 10.1109/GLOCOM.2008.ECP.565].
[35] Lu Y, Zhao YJ, Sun FC, Li HB, Wang DJ. Dynamic fault-tolerant routing based on FSA for LEO satellite networks. IEEE Trans.on Computers, 2013,62(10):1945-1958 [doi: 10.1109/TC.2012.127].
[36] Bai JJ, Lu XC, Lu ZX, Peng W. A distributed hierarchical muting protocol for non-GEO satellite networks. In: Proc. of the Int’l Conf. on Parallel Processing Workshops (ICPPW 2004). Piscataway: IEEE, 2004. 148-155.
[37] Svigelj A, Mohorcic M, Kandus G, Kos A, Pustisek M, Bester J. Routing in ISL networks considering empirical IP traffic.IEEE Journal on Selected Areas in Communications, 2004,22(2):261-272 [doi: 10.1109/JSAC.2003.819974].
[38] Apostolopoulos G, Williams D, Kamat S, Guerin R, Orda A, Przygienda T. QoS routing mechanisms and OSPF extensions. RFC 2676, 1999. http://tools.ietf.org/html/rfc2676.html.
[39] Papapetrou E, Karapantazis S, Pavlidou FN. Multiservice on-demand routing in LEO satellite networks. IEEE Trans.on Wireless Communications, 2007,8(1):107-112 [doi: 10.1109/TWC.2009.080334].
[40] Papapetrou E, Karapantazis S, Pavlidou FN. Distributed on-demand routing for LEO satellite systems.Computer Networks, 2007, 51(15):4356-4376 [doi: 10.1016/j.comnet.2007.05.008].
[41] Mohorcic M, Svigelj A, Kandus G, Werner M. Performance evaluation of adaptive routing algorithms in packet switched intersatellite link networks.Int’l Journal of Satellite Communications, 2002,20(2):97-120 [doi: 10.1002/sat.714].
[42] Mohorcic M, Werner M, Svigelj A, Kandus G. Alternate link routing for traffic engineering in packet-oriented ISL networks.Int’l Journal of Satellite Communications, 2001,19(5):463-480 [doi: 10.1002/sat.712].
[43] Mohorcic M, Werner M, Svigelj A, Kandus G. Adaptive routing for packet-oriented inter satellite link networks: Performance in various traffic scenarios. IEEE Trans. on Wireless Communications, 2002,1(4):808-818 [doi: 10.1109/TWC.2002.804176].
[44] Mohorcic M, Svigelj A, Kandus G, Hu YF, Sheriff RE. Demographically weighted traffic flow models for adaptive routing in packet switched non-geostationary satellite meshed networks.Computer Networks, 2003,43(2):113-131 [doi: 10.1016/S1389-1286 (03)00230-5].
[45] Korcak O, Alagoz F, Jamalipour A. Priority-Based adaptive routing in NGEO satellite networks.Int’l Journal of Communication Systems, 2007,20(3):313-333 [doi: 10.1002/dac.823].
[46] Bai JJ, Lu XC, Lu ZX, Peng W. Compact explicit multi-path routing for LEO satellite networks. In: Proc. of the Workshop on High Performance Switching and Routing (HPSR 2005). Piscataway: IEEE, 2005.386-390 [doi: 10.1109/HPSR.2005.1503260].
[47] Tarik T, Daisuke M, Jamalipour A. Explicit load balancing technique for NGEO satellite IP networks with on-board processing capabilities. IEEE/ACM Trans.on Networking, 2009,17(1):281-293 [doi: 10.1109/TNET.2008.918084].
[48] Rao Y, Wang RC. Agent-Based load balancing routing for LEO satellite networks.Computer Networks, 2010,54(17):3187-3195 [doi: 10.1016/j.comnet.2010.06.019].
[49] Roy K, Cem E. Minimum flow maximum residual routing in LEO satellite networks using routing set.ACM/Kluwer Wireless Networks Journal, 2008,14(4):501-517 [doi: 10.1007/s11276-006-0733-7].
[50] Ercetin O, Krishnamurthy S, Dao S, Tassiulas L. Provision of guaranteed services in broadband LEO satellite networks.Computer Networks, 2002,39(1):61-77 [doi: 10.1016/S1389-1286(01)00298-5].
[51] Chen C. A QoS-based routing algorithm in multimedia satellite networks. In: Proc. of the IEEE 58th Vehicular Technology Conf. (VTC 2003-Fall). Piscataway: IEEE, 2003. 2703-2707 [doi: 10.1109/VETECF.2003.1286057].
[52] Rao Y, Wang RC. Performance of QoS routing using genetic algorithm for Polar-orbit LEO satellite networks.AEU-Int’l Journal of Electronics and Communications, 2011,65(6):530-538 [doi: 10.1016/j.aeue.2010.08.008].
[53] Cao JH, Stefanovic M. Cross entropy accelerated ant routing in satellite networks. In: Proc. of the American Control Conf. (ACC). Piscataway: IEEE, 2010. 5080-5087.
[54] Gao ZH, Guo Q, Na ZY. A distributed routing algorithm with traffic prediction in LEO satellite networks.Information Technology Journal, 2011,10(2):285-292 [doi: 10.3923/itj.2011.285.292].
[55] Perkins CE, Royer EM. Ad-Hoc on-demand distance vector routing. In: Proc. of the 2nd IEEE Workshop on Mobile Computing Systems and Applications (WMCSA’99). Piscataway: IEEE, 1999.90-100 [doi: 10.1109/MCSA.1999.749281].
[56] Ekici E, Akyildiz IF, Bender MD. A multicast routing algorithm for LEO satellite IP networks. IEEE/ACM Trans.on Networking, 2002,10(2):183-192 [doi: 10.1109/90.993300].
[57] Chen L, Zhang J, Liu K. Core-Based shared tree multicast routing algorithms for LEO satellite IP networks. Chinese Journal of Aeronautics, 2007,20(4):353-361 [doi: 10.1016/S1000-9361(07)60055-7].
[58] Yang D, Liao W. On multicast routing using rectilinear Steiner trees for LEO satellite networks. IEEE Trans.on Vehicular Technology, 2008,57(4):2560-2569 [doi: 10.1109/TVT.2007.912605].
[59] Lee J, Kang S. Satellite over satellite (SOS) network: A novel architecture for satellite network. In: Proc. of the IEEE INFOCOM. Piscataway: IEEE, 2000.315-321 [doi: 10.1109/INFCOM.2000.832201].
[60] Bayhan S, Gur G, Alagoz F. Performance of delay sensitive traffic in multi-layered satellite IP networks with on-board processing capability.Int’l Journal of Communication Systems, 2007,20(12):1367-1389 [doi: 10.1002/dac.874].
[61] Zhou YH, Sun FC, Zhang B. A novel QoS routing protocol for LEO and MEO satellite networks.Int’l Journal of Satellite Communications and Networking, 2007,25(6):603-617 [doi: 10.1002/sat.892].
[62] Long F, Xiong NX, Vasilakos AV, Yang LT, Sun FC. A sustainable heuristic QoS routing algorithm for pervasive multi-layered satellite wireless networks.Wireless Networks, 2010,16(6):1657-1673 [doi: 10.1007/s11276-009-0220-z].
[63] Lu Y, Zhao YJ, Sun FC, Li HB. A survivable routing protocol for two-layered LEO/MEO satellite networks. Wireless Networks, 2013. http://link.springer.com/journal/11276/onlineFirst/page/4 [doi: 10.1007/s11276-013-0656-z]
[64] Kawamoto Y, Nishiyama H, Kato N, Yoshimura N, Kadowaki N. A delay-based traffic distribution technique for multi-layered satellite networks. In: Proc. of the Wireless Communications and Networking Conf. (WCNC). Piscataway: IEEE, 2012. 2401-2405.
[65] Nishiyama H, Tada Y, Kato N, Yoshimura N, Toyoshima M, Kadowaki N. Toward optimized traffic distribution for efficient network capacity utilization in two-layered satellite networks. IEEE Trans.on Vehicular Technology, 2013,62(3):1303-1313 [doi: 10.1109/TVT.2012.2227861].
[66] Akyildiz IF, Ekici E, Yue G. A distributed multicast routing scheme for multi-layered satellite IP networks.Wireless Networks, 2003,9(5):535-544 [doi: 10.1023/A:1024648402306].
[67] Bovet DP, Crescenzi P. Minimum-Delay schedules in layered networks.Acta informatica, 1991,28(5):453-461 [doi: 10.1007/BF0 1178583].
[68] Clementi AEF, Di Ianni M. On the hardness of approximating optimum schedule problems in store and forward networks. IEEE/ACM Trans.on Networking (TON), 1996,4(2):272-280 [doi: 10.1109/90.491013].
[69] Di Ianni M. Efficient delay routing.Theoretical Computer Science, 1998,196(1):131-151 [doi: 10.1016/S0304-3975(97)00198-9].
[70] Adler M, Rosenberg AL, Sitaraman RK, Unger W. Scheduling time-constrained communication in linear networks.Theory of Computing Systems, 2002,35(6):599-623 [doi: 10.1007/s00224-002-1001-6] .
[71] Busch C, Magdon-Ismail M, Mavronicolas M, Spirakis P. Direct routing: Algorithms and complexity.Algorithmica, 2006,45(1): 45-68 [doi: 10.1007/s00453-005-1189-3] .
[72] Peis B, Skutella M, Wiese A. Packet routing: Complexity and algorithms. In: Proc. of the Approximation and Online Algorithms. Berlin, Heidelberg: Springer-Verlag, 2010. 217-228 [doi: 10.1007/978-3-642-12450-1_20].
[10] 龙飞.卫星网络鲁棒QoS路由技术研究[博士学位论文].北京:清华大学,2010.