基于拓扑变化预计算的多层卫星网络路由协议*

李洪鑫，李世民，王坤

(总参工程兵科研三所，河南洛阳 471023)

0 引言

基于星间链路的多层卫星网络由位于不同轨道高度的多种类型的卫星所组成，这些卫星通过星间链路进行互联互通，构成多层卫星网络。与单层卫星网络相比，多层卫星网络具有抗毁性强、应用范围广的特点，是未来卫星网络的一个发展趋势［1-4］。

在多层卫星网络中，路由是一个重要的问题，它在很大程度上决定了整个卫星网络通信资源的分配。目前，对于多层卫星网络路由协议已有较多的研究，典型的多层卫星网络路由协议包括HSRP(hierarchical satellite routing protocol)［5］，MLSR(multilayered satellite routing)［6］，TDRP(time-slot division QoS routing protocol)［7-8］等。这些协议的具体过程存在着较大差异，但基本思想是一致的:低层卫星向高层卫星报告链路状态，高层卫星汇总全网的链路状态，最后卫星网络完成路由计算。本文基于这种路由设计思想，以GEO/MEO/LEO(geostationary orbit/medium earth orbit/low earth orbit)三层卫星网络为例，设计一种新型的基于拓扑变化预先计算的多层卫星网络路由协议。

1 基于拓扑变化预计算的多层卫星网络路由协议

本文充分利用多层卫星网络自身的特点，设计了一种基于拓扑变化预计算的路由协议，总体过程如下:卫星网络事先根据各卫星运行规律进行拓扑变化预计算;在每次卫星网络拓扑发生变化前，各低层卫星将各自的链路状态信息报告给GEO卫星，GEO卫星之间对收到的链路状态信息进行交换和汇总，得到整个网络的拓扑结构，进而计算并下发各个节点的路由表。协议过程如图1所示。

图1 基于拓扑变化预先计算的多层卫星网络路由协议Fig.1 Routing protocol for multilayer satellite networks based on topology precomputation

1.1 拓扑变化预计算

本文中的GEO/MEO/LEO三层卫星网络的体系结构与目前大多数文献中的多层卫星网络相同［6，9-10］:整个卫星网络可以实现全球覆盖，各层卫星均采用Walker星座;网络中的每颗卫星与同一轨道内前后相邻的2颗卫星建立轨内链路，与同层中相邻2个轨道中的2颗卫星建立同层轨间链路;此外，各卫星还与不同层的卫星建立层间链路。为了化简网络拓扑结构以及考虑实际通信需求，假定一颗低层卫星在一个时刻只与同种类型的一颗高层卫星建立星间链路，如每颗LEO卫星在一个时刻只与一颗MEO卫星、一颗GEO卫星建立星间链路。整个多层卫星网络的拓扑结构可以用无向图G(t)=(S，L(t)，W(t))表示，节点S是卫星网络中所有卫星的集合，L(t)是星间链路的集合，W(t)则是链路权值的集合，反映了t时刻各链路的状态信息。

在多层卫星网络中，各卫星节点处于高速运动状态，导致卫星网络拓扑结构不断发生变化。但这种变化是有规律的，因为每颗卫星的轨道固定，整个卫星网络是一个拓扑结构变化可预知的动态网络。如果把卫星网络运行周期划分为一系列长度足够小的时隙，则可以认为在各时隙内网络拓扑结构固定。当卫星网络的拓扑结构发生了变化时，网络中至少有一条星间链路发生了通断变化。由于建立轨内链路的2颗卫星之间相对位置保持不变，因此轨内链路是永久链路，它不会对卫星网络拓扑变化造成影响。对于一颗卫星而言，只有同层卫星的轨间链路和层间链路通断会影响网络拓扑变化。

文献［11］研究了Walker星座的拓扑变化规律，给出了Walker星座中卫星轨间链路通断情况的计算方法。文献［12］研究了多层卫星网络层间链路的建立策略，根据这些策略可以确定任意时刻各层卫星间的链路建立情况。根据以上文献中提供的方法，可以计算出在系统周期T内任意一颗卫星Si的轨间链路和层间链路发生通断变化的时刻，从而可以将卫星网络运行周期T划分为一系列时隙，各时隙的分隔点即为拓扑发生变化的时刻，由此可以得到卫星Si引起的时隙分隔点集合Γi。用同样的方法可以得到其余所有卫星引起的时隙分隔点集合，对这些集合求并集，可以预先计算得到整个卫星网络的时隙分隔点集合，如图2所示。

图2 拓扑变化预先计算示意图Fig.2 Sketch map of topology precomputation

1.2 链路状态报告

通过拓扑变化预计算可以确定多层卫星网络拓扑结构图G(t)中的和，对于各链路的权值则需要通过链路状态报告得到。

(1)链路权值的计算

链路状态是反映网络拓扑结构的重要参数，它会在很大程度上影响网络中路由的选择，因此选取的链路状态应该能够反映星间链路的特点，体现出不同链路的差异。在本文中选取的链路状态信息包括3个，分别是链路时延D、误码率BER和可用带宽B。链路的时延包括发送时延和传播时延，其中传播时延起决定作用，反映了卫星之间距离的大小;误码率则与链路的损耗和功率等因素有关;可用带宽反映了链路中负载的大小。

在本文的路由协议中通过链路权值来反映各链路的状态。由于链路状态的3种指标数值大小表示的意义不同，比如大的时延和大的误码率意味着链路的质量较低，而大的可用带宽却意味着链路质量较高，并且它们的取值完全不在同一个数量级上，因此为了计算最终的链路权值，需要将它们的值进行统一。将每种指标的取值进行量化，量化结果的范围为10个值:1～10，令在该项指标的影响下链路质量最好时，量化结果为1，而质量最差时量化结果为10，下面以时延为例进行说明。

假设所有星间链路中时延最大值和最小值分别为 Dmax，Dmin，将 ［Dmin，Dmax］划分为 10 个区间:［D0，D1)，［D1，D2)，…，［D9，D10］，其中 D0=Dmin，D10=Dmax。

定义函数 f:当 D∈［Di-1，Di)时，f(D)=i，1≤i≤10，且 f(Dmax)=10。

通过函数f可以把时延对链路质量的影响统一为1～10的10个值，同理，分别针对误码率、可用带宽定义函数p和函数q，将它们对链路质量的影响也统一为1～10的10个值。链路权值的计算公式为

式中:α，β，γ为3种指标量化结果的系数，代表了各种指标对链路状态的影响程度，并且满足α+β+γ=1。

(2)链路状态报告内容

低层卫星所报告的信息为下一时隙它所建立链路的状态信息，如图3所示，其中目标卫星是指与该卫星建立星间链路的卫星。每条报告中最多包括6条链路状态信息，如当LEO卫星与GEO卫星存在星间链路时，它需要报告2条轨内链路、2条轨间链路、1条与MEO层卫星的层间链路和1条与GEO卫星的层间链路的状态信息。

图3 链路状态报告内容Fig.3 Content of link status reporting

(3)链路状态报告时机与方式

当网络拓扑发生变化时，路由也应该随之发生变化。本文的路由协议中，低层卫星在网络拓扑发生变化前将链路状态报告给GEO卫星，以使GEO卫星能够及时获取网络拓扑状态信息，完成路由的计算，并在下一时隙开始之前将计算好的路由信息下发至各低层卫星。本协议中链路状态报告是在下一时隙开始之前进行的，但它仍能反映下一时隙的网络状态，2.2节将对此进行详细分析。对于链路状态报告提前的时间量，可以通过多次仿真实验得到。

链路状态信息报告采取低层卫星向GEO卫星报告的方式。MEO卫星直接将自身的轨内链路、轨间链路以及与GEO卫星层间链路的状态信息通过层间链路向GEO卫星报告。LEO卫星的链路状态报告采用自适应的报告方式:当LEO卫星位于极区时，它将无法与GEO卫星建立链路，此时它将自身的链路信息发送给当前所接入的MEO卫星，由MEO卫星转发给GEO卫星;在其他时刻，LEO卫星直接通过与GEO卫星的层间链路将链路状态信息向GEO卫星报告。可以通过计算卫星的运动相位来判断其是否位于极区。

1.3 路由计算与分发

各GEO卫星收到的仅是其覆盖范围内卫星的链路状态，还需要和相邻的2颗GEO卫星进行交互，将链路状态信息汇总，才能掌握整个网络的拓扑结构。GEO卫星根据卫星网络中每2颗卫星之间的连接关系以及链路权值，可以建立当前时刻卫星网络的拓扑结构图G(t)=(S，L(t)，W(t))。图中任意两点之间的最短路径即为卫星网络的路由，使用图论中的最短路径算法，可以计算出任意2个卫星之间的最优通信路径，从而可以得到整个网络中每颗卫星的路由表。最后，GEO卫星将计算好的路由表通过层间链路发送给各LEO卫星和MEO卫星;当GEO与LEO之间不存在层间链路时，则通过MEO卫星转发路由表。

2 路由协议分析

本文设计的基于拓扑变化预计算的路由协议与已有协议的最大不同在于路由计算时机与链路状态报告方式，本节将对其合理性进行分析，并分析本文协议与其他协议相比的优势。

2.1 链路状态报告方式分析

在已有的路由协议中［6-8］，链路状态信息是由低层卫星向高层卫星逐层上报的，即LEO卫星先向MEO卫星报告，MEO卫星再将自身的链路信息及收到的LEO卫星链路信息向GEO卫星报告。一次路由计算过程的路径为:LEO层卫星→MEO层卫星→GEO层卫星→MEO层卫星→LEO层卫星。在本文协议中链路状态报告方式是自适应的，大部分时间LEO直接向GEO报告，不存在层间链路时则通过MEO卫星转发;与之相应，路由分发的方式与已有路由协议也不相同。

根据卫星之间建立层间链路的条件公式［8］，只要LEO卫星处于GEO覆盖范围内、并且LEO卫星和GEO满足最小通信仰角的要求，它们之间便可以建立链路。只有当LEO卫星运行到极区时，2种卫星之间才不存在层间链路。根据计算，大约在80%的时间内，LEO卫星与GEO卫星之间都存在层间链路，并且在相对运动速度及链路持续时间方面，LEO卫星与GEO卫星之间链路的性能要优于LEO卫星与MEO卫星之间的链路。因此，在对用户数据进行路由时，应该根据总体的性能选取合适的方案，而不应该将路由过程进行限制。

本文的路由协议中，大部分情况下各层卫星的链路状态信息直接报告给GEO卫星，而不经过中间层的转发，因此本文的方案缩减了一个过程，链路状态收集的效率更高，路由信息汇总的过程更快，这对网络拓扑状态频繁发生变化的多层卫星网络是非常重要的。同理，路由分发耗费的时间也比其他路由协议要小。

2.2 路由计算时机分析

在已有的路由协议中，HSRP等协议采用的链路状态更新方法为周期性更新，但卫星网络拓扑变化的间隔是变长的，因此更新周期的大小难以确定。当选取的周期较小时，会带来较大的通信负担，周期较大时又不能适应多层卫星网络拓扑变化频繁的特点。TDRP等协议采用的更新方式类似于部分地面网络路由协议，为拓扑变化后更新，但卫星网络拓扑变化很快，两次变化间隔时间很短，这种方式路由收敛较慢，不能及时反映出网络拓扑的变化情况。本文协议利用卫星网络拓扑变化具有周期性和可预知性的特点，事先计算好网络拓扑变化的时刻，在拓扑变化前完成下一时隙的路由计算和分发，从而各卫星可以及时获得拓扑变化后的路由，因此本文协议具有更高的效率。虽然链路状态报告和路由计算是在拓扑变化之前进行的，但它仍能反映下一时隙的网络拓扑状态，下面对此进行分析。

在网络拓扑变化的时刻，卫星网络中至少有一条链路发生了通断变化。对于一颗卫星SAT_A而言，所有的时隙分隔点可以分为2类:一类是分隔点前后SAT_A的链路状态不发生变化，即此时隙分隔点的形成是由其他卫星的接入切换引起的，如图4中的ti时刻;第2类时隙分隔点前后SAT_A的链路状态发生了变化，即此分隔点是由于卫星SAT_A的接入切换引起的，如图4中的tj时刻。

图4 链路状态报告时机Fig.4 Moment of link status reporting

对于多层卫星网络中的一颗卫星，大部分的时隙分隔点都是第1类时隙分隔点。可以认为在第1类时隙分隔点前后SAT_A的链路状态不变，因此在时隙分隔点前的ti-ε时刻，卫星可以将链路状态信息发送给GEO卫星，用于计算下一时隙的路由。对于第2类时隙分隔点，SAT_A在其前后分别与不同的卫星建立了链路，因此在tj-ε时刻，SAT_A不能获取下一时隙的链路状态。此时，SAT_A可以根据下一时隙所接入卫星的位置和自身的位置计算得到二者之间的距离，从而可以计算得到通信时延D;因为链路还未建立，因此下一时隙链路的可用带宽B即为链路的最大带宽;对于链路误码率，可以根据经验给出一个估计值，在下一次链路状态报告时可以给出此链路误码率的精确值。从而低层卫星可以得到所有的链路状态信息，并将该信息发送给GEO卫星。

3 结束语

多层卫星网络存在着巨大的优势和广阔的发展空间，同时也面临着诸多挑战。网络拓扑结构频繁变化使得多层卫星网络路由协议的设计比其他网络更为复杂。本文深入分析多层卫星网络的结构特点，充分利用了网络拓扑变化可预知的规律，设计了一种基于网络拓扑变化预计算的路由协议。与其他多层卫星网络路由协议相比，本文的协议更能适应多层卫星网络拓扑变化频繁的特点。在下一步的研究工作中，应该在本文协议的基础上，研究支持QoS的多层卫星网络路由协议，以更好地适应卫星网络多种应用业务的不同需求。

［1］ ILCEV S D.Hybrid Satellite Orbits(HSO)for Global Coverage［C］∥ Microwave and Telecommunication Technology(CriMiCo)2010，2010:404-405.

［2］ YIN Zhi-zhong.On-Demand QoS Multicast Routing for Triple-Layered LEO/HEO/GEO Satellite IP Networks［J］.Journal of Communications，2010，6(6):495-508.

［3］ LONG Fei，SUN Fu-chun.A Novel Routing Algorithm Based on Multi-Objective Optimization for Satellite Networks［J］.Journal of Networks，2011，6(2):238-246.

［4］ Durga Shankar Dasha，Arjan Durresi，Raj Jain.Routing of VoIP Traffic in Multi-Layered Satellite Networks［C］∥Proceedings of SPIE，2003:65-75.

［5］ LEE J，KANG S.Satellite over Satellite(SOS)Network:A Novel Concept of Hierarchical Architecture and Routing in Satellite Network［C］∥IEEE 2000 Conference on Local Computer Networks，2000:392-399.

［6］ Ian F Akyildiz，Eylem Ekici，Michael D Bender.MLSR:A Novel Routing Algorithm for Multilayered Satellite IP Networks［J］.IEEE/ACM Transactions on Networking，2002，10(3):411-424.

［7］ 周云晖.卫星网络QoS路由协议及其优化理论研究［D］.北京:清华大学，2007.ZHOU Yun-hui.A Novel QoS Routing Protocol for Satellite Networks and Its Optimization［D］.Beijing:Tsinghua University.2007.

［8］ 周云晖，孙富春，张钹，等.一种基于时隙划分的三层卫星网络QoS路由协议［J］.计算机学报，2006，29(10):1814-1822.ZHOU Yun-hui，SUN Fu-chun，ZHANG Bo，et al.A Time-Division QoS Routing Protocol for Three-Layered Satellite Networks［J］.Chinese Journal of Computer，2006，29(10):1814-1822.

［9］ 洪志国，吴凤鸽，范植华，等.基于PETRI网模型的LEO/MEO/GEO三层卫星网络的性能分析［J］.电子学报，2005，33(2):334-357.HONG Zhi-guo，WU Feng-ge，FAN Zhi-hua，et al.A Petri Net-Based Performance Analysis of a Triple-Layered LEO/MEO/GEO Satellite Network［J］.Acta Electronic Sinica，2005，33(2):334-357.

［10］ YUE Gao-feng;EKICI E，AKYILDIZ I F.A New Multicast Routing Algorithm in Hierarchical Satellite Networks［C］∥Globecom ＇02.IEEE，2002:2925-2929.

［11］ 佘春东，王俊峰，刘立祥，等.Walker星座卫星网络拓扑结构动态性分析［J］.通信学报，2006，27(8):46-51.SHE Chun-dong，WANG Jun-feng，LIU Li-xiang，et al.Topological Dynamics Analysis of Walkerconstellation Satellite Networks［J］.Journal on Communications.2006，27(8):46-51.

［12］ 吴廷勇，吴诗其.LEO/MEO双层卫星网络层间星际链路建立策略的性能研究［J］.电子与信息学报，2008，30(1):67-71.WU Ting-yong，WU Shi-qi.Performance Analysis of the Inter-Layer Inter-Satellite Link Establishment Strategies in Two-tier LEO/MEO Satellite Networks［J］.Journal of Electronics＆ Information Technology，2008，30(1):67-71.