前沿 | 低轨卫星网络路由技术研究分析
北京呼风唤雨文化传媒有限公司
低轨卫星网络路由技术研究分析
文 | 吴署光、王宏艳、王宇、钱克昌、李海滨、万颖（航天工程大学 等）
低轨卫星由于其轨道高度较低，在与地面节点进行通信时，存在双程时延低、星地链路损耗小、数据传输速率高等优点，但由于其轨道运行周期短，网络拓扑变化比较快，传统的地面网络路由无法适应高动态的低轨卫星网络。为适应动态变化的网络拓扑，保证低轨卫星通信质量，各类路由技术相继被提出。本文根据卫星网络路由技术的发展脉络，对当前主要的路由技术进行分类，综述各类路由技术的功能、机制及特点，然后从开销和性能两个方面对各类技术的优缺点进行对比，最后结合低轨卫星网络发展趋势，提出了在设计卫星网络路由技术时应当重点把握的几点原则。
天地一体化网络是以地面网络为基础、以卫星网络为延伸，实现空、天、地信息网络的相互融合，为天基、空基、陆基、海基等提供信息通信保障的基础设施，是国家信息网络实现全球覆盖、宽带传输、军队联合作战等的必经之路。低轨卫星网络作为天地一体化网络的重要组成部分，其应用与发展正在加速推进，以Starlink、铱星等为代表的低轨卫星服务正在逐渐渗透到计算机互联、医疗数据、应急业务、交通信息等军民各类领域，低轨资源也逐渐成为各国争夺的又一新领域。
低轨卫星由于其轨道高度比较低，在进行通信时，存在双程时延低、星地链路损耗小、数据传输速率高等优点，但由于轨道运行周期短，网络拓扑变化比较快，在通信时既要保证通信质量，又要适应动态变化的网络拓扑。所以，路由问题一直是低轨卫星网络研究的重点和难点。
根据卫星网络路由技术的发展脉络和相应特点，通常可以把低轨卫星网络路由技术分为面向连接和面向非连接的卫星网络路由[17]，具体分类如图1所示。我们将系统地阐述各类路由技术的主要功能、机制及特点。
图1 低轨卫星网络路由算法分类图
以ATM为代表的面向连接网络技术在上世纪90年代得到了非常广泛的研究与应用,当时的人们将其看作构建未来宽带综合业务网的基本网络机制[1]。最早的对于LEO卫星网络路由技术的研究都是从ATM机制开始的,很多算法都采用面向连接的机制[2，3]。已经提出的面向连接的单层LEO卫星网络路由算法主要有以下2类:
（1）基于虚拟拓扑的路由算法
Werner[6～8]提出的基于ATM 机制的DT-DVTR 路由算法、Chang[21]提出的基于FSA的路由算法、Gounder[22]提出的基于快照的路由算法、CEMR路由算法、ELB[23，24]路由算法、PAR[25]路由算法都属于系统周期分割机制。为保证吞吐率能够满足不同的业务需求，确保网络的性能良好，李楠[33]等人提出了一种复合分组调度策略和基于拥塞控制的备份路由方法相结合的算法，能够满足不同业务的服务质量需求，同时也保证网络节点在发生负载时实现业务分流。
基于虚拟拓扑的路由算法，是通过利用卫星星座运转的周期性和可预测性,将星座周期划分成若干个时间片,如图2所示，将系统的网络结构在时间轴上划分为多个离散的快照，每个时间片内网络拓扑被看作是固定不变的,从而依据网络结构的可预测性提前为各网络节点建立不同时间片内的连接关系。
图2 拓扑快照示意图
DT-DVTR算法[4～6]是基于虚拟拓扑路由算法的典型代表。该算法将卫星网络的系统周期划分为N个时间片,每个时间片内的网络拓扑被认为是固定不变的,我们只需要计算N个静态虚拟拓扑下的VP路由。算法首先根据星间链路拓扑数据以及路径时延最小的要求,在每个时间片内，为每对卫星间计算出多条路径,形成备选VP路径集合;然后从这些备选的VP路径集合中选择相邻时间片之间VP路径变化最小的路径作为最优路径。优化过的路由需要在地面预先计算后发送给卫星,卫星在时间片分割点处修改路由表。
此类算法不能有效解决链路切换引起的重路由问题,该问题对于面向连接的卫星网络而言是非常重要的。
（2）基于覆盖域划分的路由算法
基于覆盖域划分的路由算法主要是为了解决因链路切换而引起的重路由问题,该算法假设是卫星的移动引起了切换的发生,然后由地面终端来选择切换后新的源端卫星和目的端卫星,空间段不再执行完全重路由，面是按照卫星覆盖区域的邻接关系计算最优路径。如图3所示，由于卫星的轨道运动，用户B的接入卫星由卫星2转移到卫星3，此时需要建立卫星2和卫星3间的路由。
图3 用户终端接入卫星转移示意图
覆盖域切换重路由协议(FHRP)[9]是基于覆盖域划分路由算法的典型代表。该协议可以分为路径增量更新算法和路径重建算法。在路径增量更新阶段,利用卫星网络拓扑结构的规则性和周期性,计算切换后新加入卫星到原来路径上的卫星之间的增量，并与原路径合并形成新的路径。该算法假设在路径更新前从源到目的的初始路由是优化的，路径更新后新的卫星接替而形成的路由也是优化的。
在多次的路径增量更新后，由于通信流量和链路特性等情况发生变化，路径增量更新阶段形成的路径可能会偏离最优路径，那么在一定时间段内需要进行重路由，这就是路径重建阶段，该阶段由源节点确定重建时间,向目的节点发送路由建立请求并进行初始化,新路径的网络资源满足后,各节点开始更新路由信息,最后删除原来的路径。
与基于虚拟拓扑的路由算法相比，该算法优点是发生切换发生后根据卫星的覆盖域特性计算出新的最优路径，算法操作比较简单。但由于该算法是一个切换控制协议,端用户需要参与协议的计算,这将增加端用户设计的复杂性和计算量。此外，以固定的间隔更新路由会导致性能的剧烈震荡。
IP技术的地面网络中的应用促使其在卫星网络中得到快速发展。在卫星IP网络中,我们可以把每一个卫星节点可以看作独立的交换机或路由器,可在星上实现数据分组转发。相比于面向连接的卫星网络,面向无连接的卫星网络可以把星间链路路由与星地链路路由分开讨论,不必要考虑因切换而引起的重路由问题[10，11]。由于基于IP的网络机制在地面网络中广泛应用,在考虑与地面网络结合融合,促进天地一体化建设方面，面向无连接的卫星网络具有较大优势。
面向无连接的单层卫星网络路由算法主要分为以下3类:
（1）基于数据驱动的路由算法
Darting 算法[26]和Karapantazis等人[13]提出的LAOR算法都属于基于数据驱动的路由算法，董绍进[29]引入了多路径技术和基于多路径的负载均衡技术，提出了MBR算法，毕梦格[20]引入了继承协作卫星，将服务时间最大化作为路由选择的度量标准，对AODV算法进行优化。
该类算法以降低网络拓扑结构更新频繁而引起的通信开销为设计目标,只有在进行数据传输时才驱动路由查询，没有数据传输时不进行路由更新。基于数据驱动的路由策略只需维护到达网络中部分卫星的路由，节省了星上的存储空间，降低了路由开销。
图4 AODV路由建立过程
按需路由是基于数据驱动的路由策略的一种，由于低轨卫星网络拓扑结构变化比较快，这个特点与AdHoc网络具有一定的相似性，于是我们引入了应用于无线自组织网络中的反应式按需路由（AODV）[12]的思想。AODV主要包括三类报文，分别是路由请求（RouteRequest，RREQ）、路由回复（RouteReply，RREP）与路由错误（RouteError，RERR）。
协议可分为路由发现过程与维护过程，在运行过程中通过链路探测进行路由维护。当节点向目的节点传输数据而不存在可用路由时驱动路由协议的运行，为源目的节点对计算路由，图4为AODV路由建立过程[20]。文献[13]提出了辅助定位按需路由协议LAOR,当通信请求到达时,为了降低额外的信号负载,算法根据源卫星与目的卫星的相对位置,限制了泛洪区，避免消息在整个网络中的泛洪,通过调用路径发现过程寻找时延最短路径。
按需路由协议只需要周期性地探测链路连通性，无需交换网络拓扑信息，能够很好的适应节点失效、临时入网与退网的情况，相比于其它路由算法，降低了路由的收敛时间，增加了路由响应拓扑变化的速度，有效地节省了卫星网络中有限的资源，对保证自组织低轨卫星网络中的数据传输质量显得更加有效，但由于其对路由请求区域进行了限制,不能从全网角度实现平衡流量的目的。
（2）基于覆盖域划分的路由算法
Hashimoto[15]提出的基于IP的路由、Mauger[27]提出的基于TDMA的路由，都属于区域分割机制。在不同的卫星网络运行时刻,每颗卫星的覆盖区域动态变化,地面用户也在不同的服务卫星间切换。卫星可保存网络的动态拓扑结构的卫星间的相对位置，地面用户位置相对随机，如果将地面用户的地理位置封装在数据分组中，有利于地面用户间通过卫星网络进行路由。该算法将地球表面划分为不同的区域，并给定不同的逻辑地址，在固定时刻，该区域的逻辑地址赋予最靠近区域中心的卫星。卫星根据其运行状态动态改变其逻辑地址。卫星覆盖域划分如图5所示[14]。
图5 卫星覆盖域划分示意图
Y.Hashimoto等提出一种基于IP的卫星网络路由框架(SIPR)[15],该框架根据卫星的覆盖域将地球表面划分为一定数量的蜂窝(Cell)和宏蜂窝(SuperCell)并对其进行编号,地面终端按照其所属蜂窝的编号确定在卫星网络中的地址,以此确定地面终端位置和卫星位置的对应关系。将卫星分组的头部格式定义为:<SID,CID,Terminal ID, Datagram ID, Sequence No,TTL>,分别代表<宏蜂窝标识，蜂窝标识，终端标识，分组标识，序列号，TTL>。其中,SID、CID和TerminalID共同组成目的节点的虚地址(VID,Virtual ID),该地址包含了目的节点的地理位置,DatagramID用来分别不同的报文,序列号用来区分一个报文被分成的多个卫星分组。
该方法由地面网关系统生成卫星分组头，卫星保存网络系统的拓扑结构，在任何时候都知道自己与邻居卫星的邻接关系，在进行分组转发时，各卫星节点根据数据包头部的目的终端位置信息来确定下一跳转发方向，直到转发到目的卫星。分布式地理位置路由算法（DGRA）[16]就是在在SIPR路由框架的基础上提出来的一种基于覆盖域划分的路由算法。该算法分两种情况进行分组转发，当分组与目的卫星距离较远时,依据当前卫星和目的卫星的位置关系进行转发，当接近目的卫星时,则根据收集到的本地拓扑信息计算到目的卫星的最短路径,并沿此转发。
基于覆盖域划分的路由算法利用了卫星星座运转的规律性,实现较为简单。这类算法的缺陷在于如果网络拓扑的规则性被打破,就会出现路由失败的问题,如在“缝”两侧、极地区域和某卫星失效等情况下会出现路由失败,健壮性较差。
（3）基于虚拟节点的路由算法
E.Ekici[17,18]提出的分布式路由算法DRA，T.H.Chan[28]提出的基于局部区域LZDR算法都是基于虚拟节点的路由算法。刘庆利[34]等人提出的基于地理位置的多业务LEO卫星网络路由算法，通过地理位置来确定数据的下一跳转发方向，并为不同数据类型实时计算路由，业务的服务质量得到了有效的提升。李贺武[35]等人提出了一种基于地理位置的路由算法—LA-ISTN算法，该算法通过卫星间的位置关系来确定转发接口，没有路由更新包交换开销，不依赖预测的链路连接关系，稳定性强，存储开销小。
该类算法是在基于覆盖域划分路由算法的基础上进行改进。首先建立一下由虚拟节点组成的卫星网络模型,为每个虚拟节点分配一个固定的地理坐标。卫星在运行过程中，根据当前位置与虚拟节点地理位置的距离关系，将距离卫星最近的虚拟节点位置被认为是该卫星的位置。在卫星发生切换时,路由表和链路队列等状态信息从当前卫星转移到后续卫星上。通过以上地理位置转化，我们在计算路由时，不必考虑卫星星座的动态性，只需要计算由虚拟节点构成的逻辑平面内最短路由。
图6 DRA算法路由示意图
分布式路由算法（DRA）是基于虚拟节点路由算法的典型代表,该算法以全球卫星通信网络（Teledesic）为参考模型，将分组传输时延最小化作为优化目标,星座中的每颗卫星的地理坐标用逻辑地址<P,S>来表示,其中P表示卫星所处的轨道面在星座中的编号,S表示卫星在本轨道内的编号，该逻辑地址在卫星的运行过程中动态变化。DRA算法主要包括方向估计、方向修正和拥塞处理三个阶段。在方向估计阶段,该算法假设所有星间链路（ISL）的长度相等,依据当前卫星与目的卫星的逻辑地址,将逻辑平面上两点的最短路径作为度量代价，来确定下一跳转发方向。
卫星收到该分组时，根据自己当前的逻辑地址及目的卫星逻辑地址,来决定下一跳卫星的候选方向,图中源卫星节点的候选方向是北(上)或者东(右)。在方向修正阶段,算法对轨内ISL和轨间ISL的长度进行区分，根据源卫星和目的卫星逻辑地址的相对位置关系，将方向估计阶段计算的方向标记为主要方向和次要方向，并提供了卫星在极地地区及“缝”两侧时的解决方案。
为了解决各卫星之间不交换网络状态信息和控制信息而引起网络拥塞的问题，算法引入拥塞处理阶段,算法实时监控链路出口队列缓冲区占用情况,一旦发现缓冲区可能溢出,则通过反向传输拥塞信息来消除拥塞。其它学者也提出了一些基于IP的分布式路由算法[30～32],算法的基本策略与DRA相同，在一定程度上降低了路由的计算与存储开销,一定程度上消除了卫星失效与流量拥塞等情况造成的影响,但不能从全局角度消除这些问题。
基于虚拟节点的路由策略将实际卫星与虚拟节点进行绑定，削弱了卫星网络拓扑动态变化对路由协议的影响，简化了路由计算的复杂性，卫星无需维护大量的路由表；但是通常只能应用在拓扑规则的卫星网络中，当网络中的节点或链路失效时，路由协议不能快速更新，数据转发无法正常进行。根据地球地理特征，高纬度地区的轨间链路距离更短,其传播时延大大低于赤道附近轨间链路,该算法容易造成高纬度地区的链路发生拥塞。
基于对以上各类路由算法的主要功能、特点及性能进行分析，我们进一步对各类算法的开销和性能进行整理分析，如下表所示：
表1主要的LEO卫星网络路由协议开销及性能比较
由于卫星网络拓扑结构的高度动态变化，面向连接的路由技术存在以下缺点：（1）无法从根本上避免链路切换和连接切换以及由此引起的一系列切换控制和重路由计算问题。（2）计算开销比较大而且星上实现困难，一般都需要地面系统的辅助计算。（3）要实现与地面IP网络的融合,需要经过协议转换、数据格式转换等一系列中间过程,这将带来额外的时间开销与处理开销,使系统实现更加复杂。因此，现在的低轨卫星路由协议研究主要集中在非连接的路由算法上。
低轨卫星网络系统的发展方向是宽带数据通信,能够提供实时的多媒体通信服务,支持卫星间的宽带的星际链路,形成卫星自治域系统,减少对地面网络资源的依赖,星上处理能力更强,具备更多的数据处理与存储能力。低轨卫星网络系统是一个非常复杂的系统工程,涉及卫星研制、生产、发射和测控以及网络通信、数据处理和存储等,在设计最初的网络系统时,就要进行全方位的考虑。
网络路由算法是随着网络规模的不断扩大和网络应用的不断丰富发展起来的，路由选择的本质是路径优化问题。根据卫星网络系统的特点,在设计路由算法时应当遵循以下几点原则:
(1)简单性。卫星资源的使用效率将直接影响卫星寿命及效能发挥，所以我们在设计路由算法时，尽量最少算法设计的复杂性，避免开销和存储开销，节省卫星的宝贵资源。
(2)健壮性。随着低轨卫星技术的快速发展，其网络规模在不断扩大，卫星节点新增、失效以及拥塞等情况时有发生，路由算法应当具备灵活适应各种网络情况的能力，在各类突发情况和异常情况下，也能够保证正确运行。
(3)收敛性。路由算法收敛过慢将会导致路由循环或网络损耗，算法应当很好的适应节点失效、临时入网与退网的情况，尽量减小收敛时间，保证数据传输的有效性。
(4)适用性。随着卫星网络不断发展，大的卫星网络系统往往包含各种轨道类型以及地面网络，路由算法应当很好地适用于各类网络系统，能够实现与地面网络的融合。
[1]W.Stallings.ISDN and Broadband ISDNwith Frame Relay and ATM(FourthEdition,影印版),机械工业出版社,2002,ISBN:7-111-09163-9
[2]I.F.Akyildiz,S.Jeong.SatelliteATM networks:A suvrey,IEEE Communication
Magazine,July,1997:30～44
[3]T.C.Keong,0.K.L.Victor.SatelliteATM networks architectures: an overview,IEEE
Network September/Oetobor,1998:61～71
[4]M.Werner,C.Delucchi,H.Vogel,G.Maral,and J.De Ridder. ATM-based routing in
LEO/MEO satellite networks withintersatellite links, IEEE Journal on Selected Aeras inCommunications,January,1997:69～82
[5]G.Berndl,M.Werner, and B. Edmaier.Performance of optimized routing in LEO intersatellite linknetworks,In:Proc.of IEEE 47ht Vehicular TechnologyConferce,May,1997:246～250
[6]M.Werner.A dynamic routing concept forATM-based satellite personal ommunication netwokrs,IEEE Journal onSelected Areas in Communications, August,1997:1636～1648
[7] Werner,M.,G.Berndl, andB.Edmaier.Performance of Optimized Routing in LEO Intersatellite LinkNetworks[C]. 2002:IEEE.
[8] Werner,M.,Delucchi, C., Vogel, H.J.,etal. ATM-based Routing in LEO/MEO Satellite Networks withIntersatellite Links[J]. IEEE Journal on Selected Areas inCommunications, 2002. 15(1): p.69-82
[9]H.Uzunalioglu,I.F.Akyildiz,Y.Yesha,W.Yen.Footprint handover rerouting protocol for LEO satellitenetwokrs, ACM-Baltzer Jounral of WirelessNetworks(WINET),October,1999:327～337
[10]E.Ekici,I.F.Akyildiz, M.D.Bender.Adistributed routing algorithm for datagram traffic in LEO satellitenetworks, IEEE/ACM Trnas. on Networking, Feburayr,2001:137～147
[11]P.Narveaz,A.Clerget,W.Dabbous.Internetrouting over LEO satellite constellations, In:Proc.of Third ACM/IEEEInternational Workshop on Satellite-Based InformationServices(WOSBIS'98),Oetober,1998:89～95
[12]PERKINS C E, ROYER E M. RFC 3561 Adhoc on-demand distance vector (AODV) routing[S]. IETF, 2003.
[13]PAPAPETROU E, KARAPANTAZIS S, PAVLIDOUF N. Distributed on-demand routing for LEO satellite systems[J].Computer Networks, 2007, 51(15): 4356-4376.
[14]T. R. Henderson. Netwokring overnext-generation satellite systems, Ph.D. Thesis, Graduate Division ofthe university of ealiformia at berkele,1999
[15]Y.Hashimoto, B.Sarikaya. Design ofIP-based routing in a LEO satellite network, In:Proc. Of the 3rdInternational Workshop on Satellite-Based Information Services,Mobicom’98, October,1998:81-88
[16]T.R.Henderson, R.H.Katz. Ondistributed, geographic-based packet routing for LEO satellitenetwokrs,In:Proc.of Globecom 2000,Decembe,200O:1119-112
[17]E. Ekici, I.F.Akyildiz, M.D.Bender.Datagram routing algorithm for LEO satellite networks. In: Proc.ofIEEE Infocom 2000. March 2000:500-508
[18]E. Ekici, I.F.Akyildiz, M.D.Bender. Adistributed routing algorithm for datagram traffic in LEO satellitenetworks, IEEE/ACM Trans. on Networking, February, 2001:137-147
[19]白建军.天基网路由技术研究[D].湖南：国防科学技术大学，2005
[20]毕梦格.低轨卫星网络路由技术研究[D].陕西：西安电子科技大学，2019
[21]Chang, H.S., Kim, B.W., Lee, C.G.,etal. FSA-based Link Assignment and Routing in Low-earth OrbitSatellite Networks[J].IEEE Transactions on Vehicular Technology,2002. 47(3): p.1037-1048
[22]Gounder, V.V., R.Prakash, and H.Abu-Amara. Routing in LEO-based Satellite Networks[C]. 2002:IEEE
[23]Taleb, T., Mashimo, D., Jamalipour,A., et al. ELB: an Explicit Load Balancing Routing Protocol forMulti-hop NGEO Satellite Constellations[C]. GLOBECOM. 2006
[24]Taleb, T., Mashimo, D., Jamalipour,A., et al. Explicit Load Balancing Technique for NGEO Satellite IPNetworks With On-Board Processing Capabilities [J]. IEEE/ACMTransactions on Networking, 2009.17(1): p.281-293.
[25]Kor ak, F. Alag z, and A. Jamalipour,Priority based Adaptive Routing in NGEO Satellite Networks[J].International Journal of Communication Systems, 2007. 20(3):p.313-333
[26]Tsai, K. and R.P. Ma. DARTING: ACost-effective Routing Alternative for Large Space-basedDynamic-topology Networks[C]. 2002:IEEE
[27] Mauger, R. and C. Rosenberg. QoSGuarantees for Multimedia Services on a TDMA-based Satellite Network[J]. Communications Magazine, IEEE, 2002. 35(7):p.56-65.
[28]Chen, C., E. Ekici, and I.F. Akyildiz.Satellite Grouping and Routing Protocol for LEO/MEO Satellite IPNetworks. WoWMoM. 2002: ACM
[29]董绍进.LEO 卫星星座路由算法研究与仿真[D].湖南：国防科学技术大学，2011
[30]Wang KD, Yi KC, Tian B, Wu CK. Packetrouting algorithm for polar orbit LEO satellite constellationnetwork. Science in China Series F: Information Sciences,2006,49(1):103127. [doi: 10.1007/s11432-004-5596-x]
[31]Sanctis MD, Cianca E, Ruggieri M. IPbased routing algorithm for LEO satellite networks in near polarorbits. In: Proc. of the 2003 IEEE Aerospace Conf. Piscataway: IEEE,2003. 3_12733_1280. [doi: 10.1109/AERO.2003.1235242]
[32] 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]
[33]李楠，宗鹏.基于opnet的低轨卫星网络路由仿真与优化[J].飞行器控制学报，2013，32（5）：408-413
[34]刘庆利，刘楠楠，石怀峰.基于地理位置多业务IEO卫星网络路由算法[J].计算机仿真，2015，32（9）：95-98
[35]李贺武，刘李鑫，刘君，吴茜.基于位置的天地一体化网络路由寻址机制研究[J].通信学报，2020，41（8）