毛腾跃，徐正全 ，朱容波 ，侯 睿

(1．中南民族大学计算机科学学院 武汉430074；2．武汉大学测绘遥感信息工程国家重点实验室 武汉430079)

1 引言

卫星网络无缝覆盖的优势可以弥补Internet的不足，使其成为Internet的延伸，为用户提供各类互联网应用、宽带多媒体数据及个人移动通信等服务。目前的卫星网络存在时延高、带宽利用率低及通信成本高、服务融合能力差的缺陷，难以满足用户廉价和方便的服务需求。下一代卫星网络只有利用地面Internet成熟的IP技术，以IP为核心思想，和地面 Internet无缝对接[1]，实现天地一体化的Internet，才能突破发展的瓶颈。

卫星网络与地面互联网相比，有许多独特的地方。卫星网络是一种高速移动网络，网络拓扑结构频繁地周期性变化，星间链路（inner-satellitelink,ISL）和星地链路频繁切换，而地面的Internet网络拓扑结构相对稳定。还有星上资源和能量受限、信道误码率远大于地面网络、卫星空间分布稀疏、节点间距离遥远等，决定了地面Internet的路由协议不适用于卫星网络。因此，需要结合卫星运动的规律性和周期性等特点，设计与地面Internet不同的路由协议。

2 路由技术面临的挑战

卫星网络是由许多处于不同轨道运行的卫星组成，包括各种类型的星座，如GEO(geostationaryearthorbit)、MEO（mediumearthorbit）、LEO(lowearthorbit)，卫 星 的 高 速 移动导致星间链路和星地链路频繁切换，卫星网络拓扑结构频繁地周期性变化。而地面Internet网络拓扑结构相对稳定，如采用地面Internet的路由协议，由于网络拓扑快速变化，拓扑信息很快过期而且需要经常刷新，会导致处理拓扑信息的开销过于庞大，卫星难以承受IP路由所带来的计算和存储开销，因而地面Internet的路由协议不适用于卫星网络。网络拓扑快速变化和链路状态信息实时变化，要求卫星网络的路由策略具有高稳定性和快速收敛的能力。

在卫星网络路由算法的设计中，卫星资源的严重受限给路由策略带来了重大挑战。星载设备的设计不同于地面设备，严格受到功率、重量、尺寸的限制，因此导致星上设备的运算能力、存储容量均受到限制，要求星上可实现的路由算法简单，对存储器的容量要求不能过高[2]。由于地面人口密度分布得不均匀，人口密度大的地区对流量的需求远大于人口稀少的地区，需求不对称和流量动态变化对路由算法提出了如何平衡流量的挑战。

星间链路、星地上下行链路频繁切换以及卫星链路的高传播时延特点，会导致时延增加以及时延抖动，特别是对实时要求较高的多媒体应用来说，严重影响QoS。而QoS苛刻的受限条件给QoS路由策略的设计提出了严峻的挑战。

卫星网络拓扑的快速变化和链路状态信息的实时变化，要求卫星网络的路由策略具有高稳定性和快速收敛的能力。空间系统的能量供给受限，星上设备维护不便，因此要求路由策略具备低功耗和高可靠性运行的能力[3]。需求不对称和流量动态变化要求路由策略具有动态的平衡性。实时多媒体应用对QoS路由策略的需求等因素导致路由策略极其复杂，作为IP网络中的核心技术，路由问题面临巨大的挑战，路由问题一直得到了极大的关注，成为持续的研究热点。

3 路由策略研究现状

由于卫星网络存在诸多的特性，地面Internet中广泛使用的路由策略不能直接应用到卫星网络中。目前关于卫星网络路由策略的研究非常多，都是结合卫星网络的某个特性或者某些特性而实现的[4]，如利用卫星拓扑结构频繁变化但具有周期性的特性提出的基于星座周期的路由策略,依据流量动态变化、需求不对称提出的实现负载均衡的路由策略等，具体分类见表1。

3.1 基于星座周期的路由

预先精确计算每对卫星间的路径，把动态拓扑结构规划成按时间段分隔的一系列连续的静态拓扑结构，在每个相对很短的间隔内，卫星的动态拓扑结构可模型化为固定拓扑，从而在静态拓扑结构的基础上提供优化的路由。Chang[5]提出的 FSA（finitestateautomataroute）算法对 LEO卫星网络拓扑结构按固定时间段进行离散处理，把离散化后的LEO卫星网络拓扑结构对应有限状态机。FSA算法把LEO卫星网络中ISL链路分配问题与路由问题相结合，优化目标是ISL利用率，通过动态规划中的退火算法来解决链路分配与路由分配的联合优化问题。其优点是对网络资源的最优化使用，但由于不是按最短路径原则选择路由，因此所选路由时延指标不能被保证，而且计算复杂性过高。Werner[6]提出的动态虚拓扑离散状态路由（time dynamicvirtualtopologyrouting，T-DVTR）算法根据卫星网络运行的周期性，把卫星系统周期划分为多个时间间隔，时间间隔适度小，在该期间内各个ISL的代价可以认为不变。ISL的连通和断开仅发生在离散时间点，经过离散化处理后，动态变化的LEO卫星网络拓扑结构表示为一系列静态拓扑结构周期性重复出现。通过典型最短路由算法计算路由，将链路切换次数作为优化目标。

表1 路由策略类型

由于基于星座周期的路由策略可以按照星座运行的周期性预先计算出路由，路由计算通常在地面预先集中处理，卫星不需要实时计算，卫星在时间间隔的分隔点修改路由表。它的优点是路由协议的开销小，对卫星的处理能力要求不高，而其缺点是对通信流量变化、链路拥塞以及故障等实时情况的适应性较差。

3.2 基于链路切换的路由

卫星高速移动导致星间链路、星地上下行链路频繁切换，如果每一次链路切换需要重建路由的话，会导致时延增加以及时延抖动，直接影响QoS，特别是对实时要求较高的多媒体应用来说，QoS的过度下降是不能容忍的。为避免QoS的下降，一些基于链路切换的路由策略在路由选择中，尽量选择链路切换次数少的路由，通过星间链路的切换率或者星地上下行链路的切换率来保证QoS。参考文献[7]中提出的概率路由协议（probabilisticroutingprotocol）在新连接路径建立阶段，通过去掉在其通信生存期内或卫星切换前可能经历链路切换的ISL，在这个新形成的卫星网络拓扑结构的基础上计算路由。参考文献[8]中通过收集星间链路的生存周期，选择生存周期最长的星间链路作为路由路径。参考文献[9]中提出了一个切换次数最少的自适应路由方案，其依据的原则是在保证一定QoS的基础上，最大限度地减少切换次数。参考文献[10]中提出了一种链路切换的概率路由策略，满足一定的QoS时延约束。

3.3 基于路径优化的路由

同地面互联网相比，卫星网络的节点间距离远，导致传输时延较长，卫星网络的时延主要取决于传输时延。因此，选择路径较短、跳数较少的路由可以尽可能地缩小传输时延。Ekici[11]提出的分布式路由算法以传输时延最小化作为约束目标，根据网络状况实时计算并选择新的路由，适应性强，同时存储空间很小，节省了星上资源。但该类路由通常要求网络拓扑结构非常规则,只适用于卫星数目较多且分布十分规则的卫星系统，而且路由计算利用局部状态信息，对每个数据分组进行局部最优转发，路由不一定全局最优化。参考文献[12]中通过Dijkstra算法寻求最小跳数，同时以最大吞吐量作为约束条件。

3.4 基于负载均衡的路由

由于地面人口密度分布的不均匀，导致人口密度大的地区对流量的需求远大于人口稀少的地区，需求不对称和流量动态变化对路由算法提出了如何平衡流量的挑战。参考文献[13]中提出的流量偏差（flowdeviation，FD）算法从整个网络中收集信息，通过指定的中央节点执行FD算法，能最大限度地减少传播时延，流量动态变化的性能优于自适应的Dijkstra算法。参考文献[14]提出了一个明确的负载平衡（explicitloadbalancing，ELB）路由策略，在多跳的 NGEO卫星星座中，能保证流量的有效分配。参考文献[15]中提出了分布式负载感知路由 （distributedload-awarerouting，DLAR）协议，采用分布式的方法处理复杂的卫星系统，并同时提供了一个逐跳机制分离流量负荷，以解决近极地地区发生的流量拥塞问题。

3.5 基于QoS的路由

QoS指标表现在多个方面，如端到端的时延、带宽、吞吐量、分组丢失率等。许多研究是在某个QoS需求上实现路由策略，或者在不同的QoS指标需求获得平衡的基础上实现路由策略。Jianjun[16]提出一个明确的紧凑型多路径路由算法，基于成本度量的指标，涉及传播和排队时延。Akyildiz[17]提出的多播路由算法，从基于端到端时延的QoS需求上进行优化。Tasi[18]提出的基于动态拓扑网络的成本效益的路由选择算法从链路的利用率上进行优化。Taleb[19]提出的NGEO宽带卫星网络中的IP流量负荷分布算法中，基于流量负载的信息，网络流量得到了更好的利用和平衡。Cetin[20]将端到端时延和LEO卫星网络的吞吐量再优化相结合，但没有提及如何添加更多的QoS需求。Fei[21]采用启发式算法，所有的QoS要求理论上可以在一个计算中，在QoS需求之间的平衡上能够获得良好的性能。

3.6 基于多层网络结构的路由

与单层LEO网络相比，多层网络在路由策略上表现出更大的灵活性，尽管网络结构复杂，但具有更加对称的星座结构，星间链接更多，路由选择的余地更大。目前对多层网络结构的路由研究成为路由策略研究的一个热点。参考文献[22]中提出了一个SOS(satellite-over-satellite)网络，通过LEO和MEO进行双层组网，低层LEO卫星发送ISL状态信息给上层MEO卫星，上层MEO卫星根据这些信息，向在覆盖范围内的低层LEO卫星分发本地路由信息，算法的优点是可以减少路由的跳数，资源消耗较小。参考文献[23]中提出了由GEO、LEO和高空平台（highaltitude platforms，HAP）组成的3层网络结构，其中GEO卫星充当骨干路由器，链路状态信息发送到固定的地面网关处理，网关将成型后的域内路由表上传到GEO层卫星，再由GEO层卫星将这些路由信息洪泛发给LEO和高空平台。参考文献[24]中提出的SGRP（satellite grouping and routing protocol）基于LEO/MEO卫星网络，在每个快照期，根据LEO卫星覆盖的区域将其分组，每一个组有一个MEO管理。MEO卫星根据从LEO层收到的链路状态信息，计算其低轨成员的最小时延路径。参考文献[25]在LEO/MEO卫星网络中，基于时隙划分，提出了分层分布式QoS路由协议，设计了自适应带宽受限最小时延路径算法，满足时延和带宽的要求，能有效计算路由。参考文献[26]中基于GEO/MEO/LEO 3层网络结构，提出了一种多QoS路由算法，相比SPF（shortest path first）路由算法，它能够较好地满足QoS的要求。

3.7 多播路由

与地面网络相比，卫星网络具有传播时延长、上下行链路不对称、链路误码率高、拓扑结构频繁变化、能量受限的特点。传统的地面网络多播算法，如距离向量多播路由协议(distance vector multicast routing protocol，DVMRP)、开放式多播最短路径优先 (multicast open shortest path first，MOSPF)等只适用于固定或者拓扑缓慢变化的网络中，而卫星高速移动；核基树(core based tree，CBT)等协议在高动态网络中会产生很大的开销，而卫星能量和处理能力受限。这些决定了传统的地面网络多播算法不能应用于卫星网络，因此需要设计高效和专用于卫星网络的多播算法。

由于多播算法具有极大的挑战性，近年来多播路由成为下一代卫星网络的一个研究热点。如采用启发式算法解决多播-路由、结合多播-路由和QoS问题、结合多播-路由和安全问题、基于多层网络下多播-路由的研究。参考文献[27]中的 MRA(multicast routing algorithm)，其源和中间卫星节点采用数据报路由算法为每个目的卫星节点确定下一跳路由方向，端到端传播时延较小，适合实时多媒体业务。参考文献[28]提出了一种基于单向卫星链路的可靠多播-通信协议，该协议命名为Reliable Multicast over Undirectional Satellite Link(RMUS)。RMUS协议主要针对卫星上下行链路不对称的问题，提供了特殊的差错恢复机制和拥塞控制机制。参考文献[29]中提出了基于遗传算法的QoS多播-路由策略，通过将多播-路由策略加入支持QoS的增强版核心树协议中，测试遗传算法的效率。

4 结束语

路由策略是下一代卫星网络的核心问题，目前研究的热点主要集中在QoS路由、多播-路由以及多层网络结构下的路由。大量的研究工作基于某种或者某些特定条件，解决了特定条件下的路由问题，但离实际应用可能还存在差距。因此，结合卫星的移动性和拓扑结构动态变化的特点，设计具有通用性的路由策略是未来卫星网络需要解决的关键技术。另外，QoS问题在地面Internet始终存在，针对卫星网络更为苛刻的受限条件将QoS问题和路由结合设计QoS路由策略，这将是下一代卫星网络路由技术未来非常重要的研究方向。

1 Taleb T,Hadjadj-Aoul Y,Ahmed T.Challenges,opportunities,and solutions for converged satellite and terrestrial networks.Wireless Communications,2011,18(1):46～52

2 晏坚.低轨卫星星座网络IP路由技术研究.清华大学博士学位论文，2010

3 周云晖.卫星网络QoS路由协议及其优化理论研究.清华大学博士学位论文，2007

4 Alagoz F,Korcak O,Jamalipour A.Exploring the routing strategies in next-generation satellite networks. Wireless Communications,2007,14(3):79～88

5 Chang H S.Performance comparison of optimal routing and dynamic routing in low-earth orbit satellite networks.Atlanta,GA,1996

6 Werner M,Delucchi C,Vogel H.ATM-based routing in LEO satellite networks with inter-satellite links.IEEE Journal on Selected Areas in Communications,1997,15(1):69～81

7 Ercetin O,Krishnamurthy S,Dao S,et al.A predictive QoS routing scheme for broadband LEO satellite networks.IEEE International Symposium on Personal,Indoor and Mobile Radio Communications,2000(2):1064～1074

8 Nguyen H N,Jukan A.An approach to QoS-based routing for LEO satellite networks.Global Telecommunications Conference,2000(2):1114～1118

9 Chen J,Jamalipour A.An adaptive path routing scheme for satellite IP networks.International Journal of Communication Systems,2003,16(1):5～21

10 Chen C.A QoS-based routing algorithm in multimedia satellite networks.IEEE 58th Vehicular Technology Conference,2004(4):2703～2707

11 Ekici E,Akyildiz I F,Bender M D.A distributed routing algorithm for datagram traffic in LEO satellite networks.IEEE/ACM Transactions on Networking,2001,9(2):137～147

12 Sun J,Modiano E.Routing strategies for maximizing throughput in LEO satellite networks.Selected Areas in Communications,2004,22(2):273～286

13 Gragopoulos I,Papapetrou E,Pavlidou F.Perormance study of adaptive routing algorithms for LEO satellite constellations under self-similar and poisson traffic.Space Communications,2000,16(1):15～22

14 Taleb T,Mashimo D,Jamalipour A,et al.ELB:an explicit load balancing routing protocol for multi-hop NGEO satellite constellations.Global Telecommunications Conference,2006,26(8):1～5

15 Papapetrou E.Distributed load-aware routing in LEO satellite networks.Global Telecommunications Conference,2008

16 Jianjun B.Compact explicit multi-path routing for LEO satellite network.High Performance Switching and Routing,2005

17 Akyildiz I F,Ekici E.A novel routing algorithm for multilayered satellite IP networks.Transactions on Networking,2002,10(3):411～424

18 Kuang T,Ma R P.A cost-effective routing alternative for large space based dynamic topology networks.Military Communications Conference,1995(2):682～686

19 Taleb T.IP traffic load distribution in NGEO broadband satellite networks.Computer and Information Science,2005(3733):113～123

20 ErCetin O.Provision of guaranteed service in broadband LEO satellite networks.Computer Networks,2002,39(1):61～77

21 Fei L,Naixue X,Athanasios V,et al.A sustainable heuristic QoS routing algorithm for pervasive multi-layered satellite wireless networks.Wireless Networks,2010,16(6):1657～1673

22 Lee J,Kang S.Satellite over satellite (SOS)network:a novel architecture for satellite network.Nineteenth Annual Joint Conference of the IEEE Computer and Communications Societies,Mar 2000

23 Dash D S,Durresi A,Jain R.Routing of VoIP traffic in multilayered satellite networks.Proceedings of SPIE Performance and Control of Next-Generation Communications Networks,2003

24 Chen C,Ekici E.A routing protocol for hierarchical LEO/MEO satellite IP networks.Wireless Networks,2005,11(4):507～523

25 Zhou Y H,Sun F C,Zhang B.A hierarchical and distributed QoS routing protocol for two-layered satellite networks.Computational Engineering in Systems Applications,IMACS Multiconference on Beijing,Oct 2006

26 Fei L.A multi-QoS objective optimization routing for hierarchical satellite networks.Education Technology and Computer Science,2010 Second International Workshop on Wuhan,March 2010

27 Ekici E,Akyildiz I F,Bender M D.A multicast routing algorithm for LEO satellite IP networks.IEEE/ACM Transactions on Networking,2002,10(2):183～192

28 Basu P,Kanchanasut K.A reliable multicast protocol for unidirectional satellite link.IEEE 2003 Symposium on Applications and Internet(SAINT’03),2000

29 Floriano D R.An enhanced QoS CBT multicast routing protocol based on genetic algorithm in a hybrid HAP-satellite system.Computer Communications,2007,30(16):3126～3143