LEO卫星网络路由算法研究

1、LEO卫星网络路由算法研究摘要：本文通过分析低轨道卫星路由的特点、目标，结合卫星网络的拓扑结构和运行规律，分别对有无星际链路（ISL）的卫星通信系统，提出相应的路由策略：最小延时路由算法、通信量和拓扑自适应的路由算法。关键词：低轨道（LEO）,卫星通信，路由（Route）,星际链路（ISL）1绪论1.1 卫星通信的低轨道化、网络化发展趋势信息，主导着当今的社会，从工业时代进入信息时代，作为这个时代的主要资源，信息资源，正处在其边际效用的最大值。与此同时，作为信息资源的载体和交换平台的通信网络也在无声无息的进化着，而如今人们的目光，更多的投向太空。卫星通信系统正是在这种形势下应运而生。以INMA

2、RSAT为代表的GEO卫星通信系统代表了二十世纪中期以前卫星通信系统的主流，然而山于轨道高度带来的延迟较大以及发射费用较高等缺点大大限制了其业务范围与综合能力。进入90年代中期，随着同步轨道资源限制与拥塞矛盾的白热化及其高纬度区域覆盖的局限性，人们寄希望与非同步轨道运而开发出克服上述缺陷的新一代MEO/LEO系统。LEO小卫星通信系统是在二十世纪80年代末期国际上兴起的一种全新概念的通信系统。它强调采用体化”的设计思想，尽量提高卫星功能密集度从而增加系统的性价比。相比传统的GEO卫星通信系统，由于轨道高度的差别LEO系统的信号传输延迟将大大减少从而具有更好的实时性；由于体积，重量及应用定位的差

3、别，LEO小卫星所需的研制成本远小于GEO卫星系统。总的看来，LEO小卫星通信系统具有良好的发展前景。虽然LEO和MEO等非静止轨道卫星具有上述优点，但单颗LEO或MEO卫星很难满足全球或区域性通信系统的要求。为满足通信全球化需求，必须采用星座方式将卫星网络化，形成卫星移动通信网，利用网络优势弥补单颗卫星覆盖特性的缺点。如Iridium,Globalstar和Teledesic等系统都是以星座运行模式来实现的。1.2LEO卫星通信网络化中的关键技术：路由算法卫星网络中的卫星数目的多少不同，拓扑结构也不同。当卫星网络中的卫星数目较少的情况下，卫星间可以通过地面信关站问连接，这种连接方式是合理的，

4、因为其可靠性高。当网络中的卫星数目增多的时候，如果单纯利用地面信关站作为卫星问信息沟通的桥梁，可能需要几十个或者更多的地面站，费用高，而且在海洋和荒芜的地区以及敌对国家建立信关站也是不可能的，因此单纯利用地面站完成网络中不同卫星间的信息沟通是不现实的。因此可以采用星间链路（ISL:Inter-Satellite-Links）连接不同卫星就可以弥补地面信关站连接方式的不足。无论是具有ISL还是不具有ISL,都需要考虑卫星间的路由问题。因为路由问题在通信网中一直是一个核心问题，路由算法的优劣将直接影响到整个通信网络的性能以及通信的质量。由于卫星网络具有的拓扑结构的动态变化等独有的特点，使得适用于地

5、面网络的一些路由算法不能直接应用于卫星网络上，因此必须针对卫星网络的特点设计适合于卫星网络的路由算法。1.3 路由算法设计的目标路由算法是随着网络规模、网络应用的扩大而发展起来的。路由选择的问题，本质上是个路径优化的问题，也就是选择哪条路由更好。优化的标准一般称之为度量值（Metric）,根据转接次数、距离、时延、误码率、安全性等指标来制定，优化基本方法主要有最短路径算法、最大流算法及最小费用。最优化指路由算法有选择最佳路径位置的能力。Metrics其权值决定最佳路由。例如，路由算法可能考虑节点数和延迟，但计算时延迟更重要。自然地，路由协议必须严格地定义它们的Metric计算算法。简单性路由算

6、法应被设计的尽可能的简单。换句话说，路由算法必须以最少的软件和使用费用获得高效的功能。当路由算法由软件实现，并在物理资源受限制的计算机上运行时，效率是特别重要的。健壮性路由算法必须是健壮的。换句话说，在异常的或者无法预料的情况面前（诸如硬件失效，高负载条件和不正确的安装和使用），它们也能正确运行。因为路由器定位在网络连接点，故障时它们能导致严重的问题。最好的路由算法应该经得住时间的考验，并被证明在各种网络条件之下能保证稳定工作。迅速收敛路由算法必须快速收敛。收敛指所有的路由器关于最佳的路由取得一致的过程。当一个网络拓扑发生改变时，路由器发送路由更新消息。路由更新消息弥漫网络，导致重新计算最佳路

7、由，并最终使所有的路由器一致同意这些路由，路由算法收敛过慢会产生路由循环或网络损耗。灵活性路由算法也应该具有灵活性。换句话说，路由算法应迅速和准确地适应各种各样的网络情况。例如，假定网络的一部分失灵，多数路由算法在监测到这个问题时，要很快地为使用该段网络的路由选择次优的路径。路由算法应被设计成能够适应变化，不论网络带宽、路由器队列大小、网络延迟，或是其它的变量。这些设计目标是路由算法的衡量标准，因此在设计卫星网络上的路由算法时也应遵循这些原则。1.4 卫星网络系统的路由特点前而讲过，因为卫星网络中数目的不同，少的时候，卫星间的连接可以通过地面信关站；但是数目多的时候，就需要通过星际链路来连接。

8、因此，不同的连接方式，有不同的路由算法。无ISL（星际链路）的路由设计，根据系统的实际情况，提出了一种比较适用的路由算法最小延时路由算法。具有ISL（星际链路）的卫星通信系统，因其具有的某些特征使得地面无线移动网络的各种网络层协议不能直接应用到ISL环境中，必须根据其特征进行适当的改造。ISL的特点可以归结为以下几点：1 、拓扑结构持续变动，卫星相对于网络中其他卫星处于不断的运动过程中，例如Iridium系统中LEO问ISL持续时间平均为10分钟。ISL传输时延长，相邻LEO卫星间传输时延在20ms左右，MEO问传输时延在50ms左右。ISL信道误码率高，通常只能在0.001到0.0001之间

9、，ISL传输速率高，当采用激光ISL时，ISL传输速率可以在50M到5G之间。2 、网络拓扑的频繁变化，将导致网络节点问关于网络结构更新信息的大量增加ISL传输时延长，将使得网络节点大量使用错误的网络拓扑信息，直接导致路由计算困难和传输效率降低；此外ISL传输时延和高误码率将共同影响网络阻塞控制和流量控制功能，可能导致大量反馈信息延误和数据包大量重传。在带有ISL的卫星网络中，每颗卫星可能同时与多颗其他卫星通过ISL相连接，即信息可以通过多种不同路由传递，因此路由算法是带有ISL的卫星网络关键问题。但ISL规律性同时也为解决路由问题提供有利条件。ISL中卫星必须在星座和轨道参数限制下运动，因此

10、卫星运行以及因卫星运动引起的ISL变化都是有规律性的。规律性主要表现为可预见性，周期性和固定性。可预见性指卫星位置和卫星间可见性关系可以通过预先计算得到，基于可遇见性特征，路由算法能够更好解决路由重建和优化问题；周期性指变化过程周期重现，而且其变化周期与卫星轨道周期存在关联，路由算法能够更好减少路由算法状态集个数；固定性指卫星网络规模的固定性，固定性可以明显降低路由规模。因此，基于上述规律性，为降低ISL时延限制路由算法的复杂性，提供了依据一一通过近似化因子和压缩因子，来降低复杂性。2LEO卫星数据通信系统的路由策略2.1 LEO卫星数据通信系统基本特征Iridium系统拥有星际链路（ISL）

11、、复杂的星上处理（OBP）以及星上交换（OBS）,形成一个独立的空间网络平台，不需要地面网支持就能够为全球用户提供实时的移动通信业务，支持语音、数据业务，真正实现了任何人随时随地通信的能力。而Globalstar系统采用透明转发卫星，更确切的说，它是作为地面移动通信系统和其他通信系统的延伸和补充，与地面系统兼容，没有星际链路和星上处理，依靠高速廉价的地面骨十网，形成一个弯管式”通信网络，也能够为全球用户提供通信业务，其系统成本低于Iridium系统，技术难度也小一些。一般说来，由于数据通信系统可以充分利用小卫星技术，形体结构简单，所需的投资要比语音系统小得多。无论是从政治上，还是从经济发展上考

12、虑，各国都迫切需要解决全球通信问题，而首先需要解决的是全球数据通信，LEO卫星数据通信系统就是一种很好的选择。但是该系统是一个腕管式”通信网络，需要地面站的强大支持，如果能在全球均匀的布置一定数量的信关站，信关站之间通过地面网相连，很好地解决了全球通信问题。但是，从政治、安全和现实出发，各国的LEO卫星数据通信系统不可能在全球布置足够数量目且分布均匀的地面站，故只能将信关站设置在各国自主控制的区域内。那么，在该区域内选取若十信关站（通过地面通信网连接），就可为各国用户之间提供实时数据通信；而对于该地区以外的用户，由于没有自主控制的信关站和地面网的支持，一般只能以存储/转发的通信方式进行通信。综

13、上所述，适用于各国的LEO卫星数据通信系统应具有以下一些基本特征：空间段由若十LEO（小）卫星组成，卫星采用带存储/转发功能的廉价卫星，不具有一复杂的星上处理能力，卫星之间没有星际链路；（2）系统的正常运行需要地面网和地面信关站的支持；（3）信关站的设置局限于各国自主控制的区域，信关站之间通过地面网实时相连；（4）通信方式与Iridium等系统不同，实时通信和存储/转发通信同时存在，如果通信双方都在国内，一般都能米用实时通信方式。如果通信双方之一处于国外，则通常大多只能采用存储/转发方式进行通信；（5）存储/转发通信的延时大小以及路由选择随着采用的路由算法不同而呈现巨大差异。2.2 信关站的选

14、择信关站数目与位置直接关系到整个网络运行效率、所能提供服务的性能以及系统可靠性等多个方而内容，成为了系统设计的一个重要方面。信关站的选择不仅要求节约投资，减少系统复杂度，还希望能够保证系统安全性和提高系统的健壮性等。信关站的选择及要求如下：(1) 在满足系统性能要求的前提下，信关站的数目要尽可能少，信关站过多不仅增大系统投资，而且会增加系统的复杂度；(2) 信关站之间要求始终保持连接，进而保证位丁不同卫星覆盖区的用户之间能够实时通信。因为在该系统中，卫星之间没有星际链路，用户之间通过卫星和信关站进行通信，需要信关站之间的协同工作；(3) 信关站站址要求在各国自主控制的范围内，而且希望能够通过信

15、关站与其他地面网(固定网与无线网)相连；(4) 在星座给定的条件下，要求信关站站址合理，使得实时覆盖区的面积尽可能大，所以一部分信关站要求尽量靠近边境；(5) 信关站的选择还应尽可能满足系统稳定性、健壮性的要求，在某些信关站失效时，系统能够降级运行；(6) 从系统的可靠性、抗毁性要求看，需要选择较多的信关站，以便在部分信关站发生故障或其通信链路故障时，能够使得系统正常工作，且其性能受到的影响相对较小，这就要求进行折中考虑。在卫星星座给定的情况下，如何找出实现最大实时覆盖区的信关站布局是一个最优化的问题，可用最优化理论来解决。但是，这样的最优化结果在实际中未必可行，因为信关站的位置和数目的选择都

16、要受到一些实际条件的限制，如地理条件、信关站数目、地面设施。因此，按照上述信关站的选择原则，可大致确定信关站的布局。2.3 最小延时路由算法根据存储/转发通信的特点，提出了一种适用丁LEO卫星数据通信系统的最小延时路山算法。在通信连接建立时，该算法可以判断出此次通信是实时通信还是存储/转发通信：若是存储/转发通信，就计算出本次通信所需要的最小延时，同时确定最优的通信路由，具有一定的现实意义，在具体讨论最小延时路山算法前先简单说明算法将要用到的一些基本公式。主要用丁计算一颗卫星是否能够覆盖到某个特定的位置点。2.3.1 相关计算公式星下点经、纬度坐标公式：星下点定义为卫星与地心连线与地球表面的交

17、点。卫星沿着轨道绕地球运行，地球本身也在自转，星下点轨迹在一般情况下不会再重复前一圈运行轨迹。假定当t=0时，卫星经过右升交点，则星下点经、纬度坐标公式如下：-180”(-180°<0<-90°)2=4+八rctg(cos(i)*±<0w(-90w<90八(2-1)180°(90°<0<180°)9=arcsin(sin(O*sni(八)(2-2)其中：么、Ws是卫星星下点的地理经、纬度；布升交点赤经；0是t时刻卫星在轨道平面内与右升交点之间的角距；好是地球自转角速度；t是飞行时间；毋别用丁顺行信道

18、和逆行信道；i轨道倾角。球面上任意两点之间的距离公式：d=&?)sin(供)+-(2-3)单颗卫星的覆盖区半径计算公式：r=R,arccos(-cos八)e(2-4)R+hL/J其中：为为两点的地理经度；W1,W2为两点地理纬度；Re是地球半径；h是轨道高度；e是终端对卫星的仰角。根据公式(2-1)、(2-2)可以计算出任意时刻t,卫星星下点的经纬度坐标；根据公式(2-3)、(2-4)可以计算出任意时刻t,任意给定点是否在某颗卫星的覆盖区内。由丁地面用户和信关站的地理位置是已知的，因此，只要求出其到卫星星下点的距离是否小丁卫星的覆盖区半径，便可判断其是否位丁该星的覆盖范围内。2.3.2

19、最小延时路由算法假定A表小系统中全体卫星的集合：S表小在时刻t可以接收来自主叫用户数据信息的所有卫星集合；/S是S的补集，表示系统中其他卫星的集合，则有A=/S+S；用t0表示主叫用户发起呼叫的时刻；T表示计算通信延时的当前时刻；成示采样时间问隔。At的值越小，延时计算精度越高，但其计算量会相应成比例增加，可根据实际需要，选取秒级或者分钟级精度的采样时间问隔；用R记录最小延时路由(一个字符申)。需要说明的是，在描述最小延时路由算法时，假设主叫用户拥有系统星座的星历知识和主被叫双方的位置信息，并忽略信息在通信过程中的传播延时等，如卫星与用户(或信关站)之间的信息传播延时和信息在地面网中的传播延时

20、。本算法对实时通信和存储/转发通信两种通信方式是统一的，实时通信等效丁延时为零的存储/转发通信，该算法的具体步骤如下：（1） 当主叫用户在to时刻发起呼叫时，初始化各项参数，S=直集)，/S=A,t=t0,R="”室字符申，表明主叫信息还不能到达信关站)；（2） 根据公式（2-1,2-2,2-3,2-4）,遍历S中的每一颗卫星并计算该星是否能够以一定仰角覆盖主叫用户（假定通信所需的最小仰角为10?,以下同），即判断该星是否能够在此刻接收主叫发出的信息，如果是，则把该星从/S中删除，加入到S中；（3）如果R不等丁空字符申，贝U表示主叫发出的信息己经可以传到国内的信关站，则转入执行（5）

21、;否则，继续执行（4）;（4）根据公式（2-1,2-2,2-3,2-4），遍历S中的每一颗卫星并计算该星是否能够以一定仰角覆盖某个信关站，如果是，则记录下该星和该信关站的标识，即R='卫星1+信关站1”，转入执行（5）;否则继续遍历下一颗卫星，直到遍历完S中的所有卫星，转入执行（6）;（5）遍历S中的每一颗卫星，如果该星能够覆盖某一信关站，则把该星从中删除，加入到S中，并标记该星通过某信关站转，表明该星在t时刻可以通过该信关站接收来自主叫的信息；（6）遍历S中的每一颗卫星，计算该星是否能够覆盖被叫用户，如果是，贝U把该星的标识记为卫星2,如果卫星2被标记为通过信关站转，则把相应信关站的

22、标识记为信关站2,转入执行（8）;否则，继续遍历S中的剩余卫星，直到S中卫星被遍历；（7） 7）T=t+4裁入执行（2）,进入下一轮循环；（8） 本次存储/转发通信的最小延时大小为tT0；如果卫星2没有被标识为通过信关站转，贝康小延时路由即为R='主叫一卫星2一被叫”，否则最小延时路由为R二生叫一卫星1一信关站1一地面网一信关站2一卫星2一被叫”，其中卫星1（或信关站1）等表示记录的卫星（或信关站）的标识。最后，对算法作一点补充说明，可以在步骤（6）加上一个通信延时大小的上限，当（T-t0）大于这个上限时，就跳出循环，认为本次通信无法建立。可以看出，当星座不能提供全球无缝覆盖（即有部分

23、地区始终不能被卫星覆盖时），或存储/转发通信虽然可以建立，但其延时超过了上限时，该算法仍能正确判断，并给予报告，从而保证了该算法的健壮性和有效性。最小延时路由算法不仅仅适用于由相同轨道高度的卫星组成的星座系统，还适用于由不同轨道高度、不同倾角以及不同轨道形式的异种卫星组成的系统：既可以是全球覆盖的系统，也可以是只对某个纬度带进行覆盖的系统，甚至于可以是各种不同用途的卫星的随意组合，只要卫星具有最基本的存储/转发功能。3具有星际链路（ISL）的低轨卫星通信系统路由策略具有星际链路的低轨卫星移动通信系统利用星座中星与星之间的星际链路构成空间网络，降低了对地面网络的依赖，能以更为灵活和迅捷的方式为全

24、球用户提供服务，增加了系统的灵活性和自治性，具有广阔的应用前景，也得到了越来越多的重视。3.1 星际链路星际链路，是连接卫星星座内的相邻卫星之间的通信链路。星座网络中的卫星通过星际链路（ISL）彼此连接。它将星座中的各卫星有机地联结为一体，使得系统内的任何用户通信链路建立都不需要地面通信网的支持。不同LEO系统，一颗卫星可分别有4,6或8条ISL。星际链路ISL乂分为不同轨道平面间星际链路（InterlSL）和同一轨道平面内星际链路（IntralSL）。用有星际链路的卫星通信，信息可以由地面站通过上行链路发往卫星，然后通过星际链路发往目的卫星，最后由目的卫星通过下行链路发往地面站，到达最终用户

25、。（见图3-1）整个通信经历了三个过程：信息在地面网段的传输；信息在卫星上、下行链路上传输；卫星在星际链路的传输。由丁卫星和地面终端具有相对运动，整个通信链路并不是一成不变的，大致可分为三种变化(如图3-2):(1) 通信过程中链路维持不变；(2) 通信过程中星际链路发生变化，而上、下行链路未发生变化，这时通信服务中的始、末端的卫星未变，但是出丁系统的整体考虑，在通信过程中改变了星际链路的联接；(3) 上、下行链路和星际链路均发生变化，这时主要的原因可能是起始端的卫星发生了变化，从而引起相应变化。在低轨道卫星通信中，卫星组成一个网，星际链路的选定也要采用一定的路由算法来选取最佳路由，也就是选取

26、效率最高的路由。由丁卫星在不断地移动，星上路由计算不会和常规的路由计算完全一致。如地面网常用的RIP和OSPF路由协议，在建立连接和网络状态改变时需要交换网络状态信息，而对LEO星座网络而言，拓扑结构的频繁变化会导致传播的更新信息量很大，会引起通信过程中切换的频繁发生，从而还会引起系统开销过大。3.2星座网络拓扑卫星之间通过一定的星座关系构成的网络结构图称为ISL网络拓扑图。星座网络拓扑结构有其独特的拓扑特点，由丁星座节点数固定、空间段运动周期性和星座运动的规律性和可预见性，使得其路由策略有简化和变通的可能。本系统采用的轨道采用Walker星座，有8个轨道平面，每个平面有6颗卫星，轨道倾角为5

27、2?,每颗卫星相对丁邻近轨道面上卫星的相移为7.5?,相位因子f=1。每颗卫星与同一轨道面的2颗相邻星之间、以及与相邻轨道面最近2颗卫星之间具有星际链路。3.2.1 卫星网络拓扑变化规律卫星网络拓扑在卫星的运行周期内，并不是一成不变的，它随时间动态变化。然而，它乂呈现出一定的规律性：卫星网络中节点总数不变、周期性、规则性、可预见性等。如果忽略星际链路长度的影响，其网络拓扑在每一个时间间隔内是保持不变的，只有当星际链路关闭（或重新连接）或者卫星从其相邻轨道的左边运行至右边（或从其相邻轨道的右边运行至左边）时，网络拓扑才发生变化。在图3-3中，黑点表示卫星节点，下方的数字表示卫星的编号，比如编号5

28、4表示第5轨道平面上的第4颗星。图中把上升卫星和下降卫星分成两组，分别用实虚线表示上升、下降卫星间的星际链路。3-3图表示的是当前时刻的网络拓扑快照，从图可以看到23,62星将最先越过北极地区，由上升的卫星变成下降的卫星，星座网络拓扑变化；与此同时下降卫星86、47越过南极，并由下降卫星变为上升卫星。变化后的网络拓扑快照如图3-4所示。比较图3-3和图3-4,可以看出发生变化前后，网络拓扑结构是一样的，只是每个网络节点的卫星编号不同。所以可以根据Walker星座的这种特性，简化卫星星际路由算法的实现。在实现中，可以把网络拓扑模型化为一个逻辑网络，将初始时刻的图3-3设为逻辑拓扑，图3-3中的编

29、号既为卫星的逻辑编号，也为它的物理编号。当网络拓扑发生变化时，卫星节点76就成为逻辑节点86,卫星节点86就成为逻辑节点18,卫星节点21变成逻辑节点31,卫星节点24变成逻辑节点34,其他节点类似。在初始时，建立逻辑拓扑中每个逻辑节点的状态信息和ISL链路信息，计算出每个逻辑节点对之间的最短路径，并保存在每个节点的路由表中。那么，在卫星运动过程中，路由表项或信道分配信息等状态信息只需要持续地从一颗卫星传递到下一颗卫星.就可以隐藏卫星的移动性，完成整个的通信功能。3.2.2 路由算法模型及说明具体路由算法模型如图3-5所示。1 、t=0时，建立卫星的星间链路逻辑网络拓扑图。为简便起见，星问链路

30、的权重均标为1。然后依据Dijkstra算法计算出每个卫星节点到所有其他节点的最短路径。此处加以改进，为每对卫星除了计算出第一最短路径外，还可以计算出第二、第三甚至是第四最佳路径，且各路径相互独立。即每一个后续路径都是在前面已经选出的路径完全排除在外之后选出的。2 、在卫星的运行周期内，共有72张网络拓扑快照，即共有72个时间间隔。假定卫星的运动、网络拓扑的变化以及切换都是在时间间隔的开始和结束发生。在第一个时间间隔开始的时候，根据逻辑网络拓扑的结构计算出每个节点的逻辑路由表，此时，逻辑节点就是物理节点所以逻辑路由表即为每个节点的物理路由表。当后续时间间隔到来的时候，根据逻辑节点到物理节点的映

31、射表，重新计算出每个卫星节点的物理路由表。3 、当呼叫到达源卫星节点时，并不是每次都选用第一最佳路径进行通信，而是按照一定的准则从多个最佳路径中选取的。此准则即是对路由的优化。本准则考虑的因素有：呼叫的优先级、一个路径中最拥塞的ISL,它是由路径的“热点”所决定的。 呼叫分为两种.新呼叫和切换呼叫。对用户来说，通话过程中被迫中断比新呼叫阻塞更加让人不能忍受。所以，对这两种呼叫，要分优先级来进行处理。呼叫阻塞的原因有多种：用户和卫星之间的信道剩余资源不足，星问链路信道资源随时间的变化出现阻塞，呼叫进而出现阻塞等。本文主要考虑由于星间链路信道资源不足而出现的阻塞。基于此，本文采用的切换优先策略是动态星问链路保护信道预留策略，即新呼叫和切换呼叫共享常规的星问链路信道，星问链路保护信道为切换预留，但是新呼叫也可以在允许概率下，使用保护信道。此