宽带多媒体LEO卫星网络路由技术研究

2019-06-03蔡海东边东明

数字通信世界 2019年4期

蔡海东，边东明，苗青

（1.中国人民解放军陆军工程大学研究生院，南京 210007；2.中国人民解放军陆军工程大学通信工程学院，南京 210007；3.中国人民解放军78167部队，成都 610000）

在全球信息科技革命浪潮的推动下，卫星通信中高清图像、视频通话、互联网接入服务等宽带多媒体业务的传输需求不断增长。宽带GEO卫星通信存在传输时延较大、不能覆盖地球南北极、存在“南山”效应等缺点，难以满足全球覆盖条件下的卫星宽带多媒体业务传输的需要。与GEO卫星相比，LEO卫星星座具有全球覆盖性好、传输时延较短、组网方便等优点，但采用透明转发技术的LEO卫星通信系统存在信关站数量过多、地理上设站困难等问题，随着卫星通信技术的发展成熟，采用星间链路（Inter-satellite Link，ISL）技术可以较好地解决上述问题。星间链路是用于卫星之间通信的无线链路，也称为星际链路或交叉链路（Crosslink）。LEO卫星星座通过星间链路互联组成了一个以卫星为数据交换节点的空间信息网络。这类星座的组网技术也成为了研究的热点，国外已有投入实际使用的Iridium Next[1][3]，还有已提出设想的Starlink[2]、Leosat[3]及Telesat[3]等；国内由中国航天科工集团提出了“虹云”工程[4]，且已于去年底成功发射首星开展技术验证。

LEO卫星网络路由技术指卫星网络拓扑结构中节点根据路由算法为数据包选择最优路由转发的过程。路由技术主要解决三个问题：一是建立LEO卫星网络拓扑结构；二是对建立的拓扑结构进行维护；三是确定路由算法。考虑到传输业务的新特点，路由协议还要考虑算法的健壮性和网络QoS性能，保证数据包传输的成功率。

1 宽带多媒体LEO卫星网络

1.1 网络拓扑结构

近年来，研究者对LEO卫星星座组网技术进行了大量的研究，包括LEO卫星星座的网络拓扑结构、接入模式、资源分配和路由协议等。针对卫星网络拓扑结构的复杂变化，研究者设计了两类典型的LEO卫星星座：倾斜轨道星座和近极轨道星座。倾斜轨道星座也称为Walker-δ[5-6]或玫瑰（Rosette）[7]星座，可以实现较好的区域覆盖或纬度带覆盖效果，但仍不能覆盖地球两极；Walker设计了一种近极轨道星座，通过合理设计各个参数，可以满足LEO卫星星座的全球覆盖特性要求。两类LEO卫星星座拓扑结构如图1所示。

图1 两类典型的LEO卫星星座拓扑结构

1.2 路由协议性能评价参数

路由协议的首要目标是网络中数据包从源节点到目的节点的传输成功率，LEO卫星网络节点缓存空间不足、链路容量受限等是导致数据包丢失、影响传输成功率的主要原因。LEO卫星宽带多媒体业务传输的高突发性、流量不均匀性等特点，也对网络传输时延、时延抖动、链路带宽利用率、负载均衡、路由收敛速度等路由协议性能评估参数的影响越来越大。而且LEO卫星工作环境极为恶劣、星上设备维护困难等问题，对卫星上硬件设备的制造工艺及软件的鲁棒性、可扩展性提出了很高的要求；复杂的路由协议还要求控制星上计算负荷、降低星上存储开销等。

2 路由分析

针对不同的LEO卫星网络拓扑结构、业务类型分类、目标函数及参数权值设置和网络QoS需求等特点，研究者在LEO卫星网络路由算法上已经取得了大量的研究成果。路由算法根据是否屏蔽卫星网络动态变化，大致可分为静态路由和动态路由两种，再考虑网络流量负载的影响，介绍四种基于网络负载均衡的路由。其详细分类如图2所示。

2.1 静态路由

静态路由为屏蔽LEO卫星网络拓扑变化，按一定的规则对动态网络拓扑进行虚拟化，生成静态拓扑。根据虚拟化方法的不同，可以分为时间虚拟化和空间虚拟化两种。时间虚拟化方法也称为基于虚拟拓扑的策略，利用卫星网络拓扑变化的周期性对一个周期进行时间片划分；空间虚拟化方法则利用LEO卫星星座网络拓扑的对称特性，对星座的覆盖区域或星座本身进行虚拟化，分别对应基于覆盖域划分的策略和基于虚拟节点的策略。

图2 LEO卫星网络路由方法分类

2.1.1 基于虚拟拓扑的策略

该策略利用LEO卫星网络拓扑变化的周期性和星座星历预测，将一个周期划分成一系列时间间隔，并假设在每个间隔内拓扑保持不变，将动态的网络拓扑离散为一系列静态的虚拟拓扑，再采用Dijkst ra等传统最短路径算法或启发式算法计算路由。该策略中网络拓扑离散化和路由计算等工作可以预先在地面离线完成，对卫星星上处理能力要求较低，生成的路由表可全部存放于卫星，或间隔一定时间上传到卫星，这要求星上的存储空间足够大，且该策略严重依赖卫星网络拓扑变化的周期性，无法应对卫星节点故障失效等特殊情况，灵活性较差。

离散时间动态虚拟拓扑路由（Discrete TimeDynamic Virtual Topology Routing，DT-DVTR）[8]算法基于ATM机制，将一个卫星网络变化周期划分为若干时间片，并假定一个时间片内的拓扑近似不变，根据该虚拟拓扑计算最优和备选路径，选择时延最短或跳数最少的路径作为最优路由。基于有限状态机（Finite State Automation，FSA）[9]的算法将每个时间片内的网络拓扑结构看作一个“状态”，根据卫星节点可用性和链路参数约束对“状态”建模，采用迭代法计算链路分配的最优解并解算路由表。基于拓扑快照[10-11]的算法假设每增加或断开一条ISL，网络拓扑形成一个新“快照”，在“快照”中计算最优路径。文献[12]将快照内即将失效的链路去除，可以延长快照持续时间和避免丢包过多。可预测链路状态路由（Predictable Link-State Routing，PLSR）[13]算法将链路状态与快照相结合，在卫星节点上预置快照的链路状态数据库。

2.1.2 基于覆盖区域划分的策略

该策略将地球表面划分成若干区域，按一定规则为每一个区域分配惟一的逻辑地址，该地址包含了区域的地理位置信息，也作为网络中数据的源、目标地址。网络中最接近该区域中心的卫星节点保存对应区域的路由信息表。路由计算时，数据包根据逻辑地址选择最优路由。卫星节点根据逻辑地址可以推算出全网内任意节点的位置，可以避免网络节点的链路状态信息交互操作，卫星节点按照当前逻辑地址实时选择路由，无需提前计算，可以节省卫星存储空间，但要求星上处理能力较强。基于IP的卫星路由（Satellite IP-based Routing，SIPR）[14]协议将地球表面划分为160km边长的正方形超级蜂窝，每个超级蜂窝又划分为9个蜂窝，按一定的规则为超级蜂窝和蜂窝分配惟一的逻辑地址并假定距离蜂窝中心最近的卫星覆盖该蜂窝。概率路由协议（Probabilistic Routing Protocol，PRP）[15]根据卫星星历、用户通信周期信息及概率论选择在用户通信周期内切换概率小于特定阈值的ISL，若ISL的切换概率大于阈值则视为断路。覆盖域切换重路由协议（Footprint Handover Rerouting Protocol，FHRP）[16]通过路径增量和路径重建的组合找到切换后的最优路径。带有地理位置信息的改进型OSPF算法[17]结合了分布式地理路由算法（Distribute Geographic Routing Algorithm，DGRA）[18]的思想，在扩展的链路状态通告（Link Status Advertisement，LSA）中包含了卫星覆盖区域的地理位置信息。

2.1.3 基于虚拟节点的策略

该策略是将LEO卫星网络看作由一系列位置固定的虚拟节点（Vir tual Node，VN）构成的虚拟网络拓扑，VN保存路由表、信道分配等状态信息。卫星与离之最近的VN一一映射，并根据VN的位置解算路由。在卫星运行过程中，任一时刻VN和卫星之间都有一一对应关系，当另一颗卫星距离VN更近时切换成新的对应卫星，状态信息也转移到新卫星。该策略主要用于极轨道LEO卫星网络，且对卫星网络拓扑结构的规则度要求较高，对卫星故障、ISL失效等情况的适应性较差；卫星为每一个数据包做出独立的路由选择，节点之间不交换网络拓扑和流量负载信息，只考虑目的节点的位置，可以降低通信开销。数据报路由算法（Datagram Routing Algorithm，DRA）[19]采用静态的二维mesh网络拓扑对卫星节点进行逻辑编址，卫星的逻辑地址由轨道编号和卫星在轨道内的编号组成。算法先假设所有ISL长度相同，根据卫星节点的逻辑地址，找到源节点到目的节点的多条最短路径；再取消之前的假设，根据ISL的长短确定优先级，选择优先级高的ISL。由于卫星通过极区时会关闭轨道间ISL，故当ISL长度相同时，尽量选择同一个轨道面内的ISL；为最小化时延，应尽量选择高纬度地区（避开极区）的轨道间ISL。文献[18]根据目的卫星的位置进行数据转发，且当数据传输到目的节点附近时，在以目的节点为中心的一定范围内卫星进行泛洪来搜集链路状态信息，避免出现路由环路的情况。文献[20]依据类DRA算法进行逻辑编制并通过最小跳数算法动态求解路由。文献[21]通过对存储在分组头部的最短时延路径判断最优路由。文献[22]基于位置信息并利用倾斜圆轨道卫星对地的准不变性，解决了LEO卫星网络中的极区节点失效问题。基于交通信号灯的分布式路由算法（Traffic light Distributed Routing Algorithm，TDRA）[23]定时搜集相邻卫星的状态，避开失效卫星；卫星在缓存区存放待转发的数据，根据邻居卫星的缓存占用情况独立选择选择下一跳节点。基于局部区域的分布式路由（Localized Zone Distributed Routing，LZDR）[24]算法首先将三维的LEO卫星网络转化为二维的规则曼哈顿网络（Manhattan Street Network，MSN）；再将VN进行分区处理，通过分区通信机制降低路由开销。相邻的VN组合为一个区域，选择其中一个VN作为该区域的管理节点，对区域内和区域间采用不同的路由策略：区域内VN互相交换状态信息，采用最小时延准则；区域间则采用最小跳数准则，VN不交换信息。基于IP的分布式分层路由协议（Distributed Hierarchical Routing Protocol，DHRP）[25]在每个轨道面上设置一个“代表”卫星及“候选代表”（防止“代表”卫星失效），通过“代表”卫星来搜集本轨道内所有卫星的链路信息，并与相邻轨道“代表”进行交换。文献[26]将失效卫星周围的若干卫星组成一个“自愈区”，数据包在“自愈区”内进行泛洪，限制了传播范围。

2.2 动态路由

LEO卫星网络静态路由仅仅考虑网络拓扑动态变化的特点，较少考虑链路状态和网络流量的变化，在负载较大时容易导致拥塞。动态路由则考虑了网络部分链路状态信息，节点根据实时信息动态计算路由，对网络拓扑结构变化和链路拥塞等情况有很强的适应性，但由于卫星ISL频繁连接与断开，网络拓扑结构变化迅速，卫星节点之间交换链路状态信息的开销较大。根据算法实现原理的不同，主要分为基于数据驱动和基于多播的方法两种。

2.2.1 基于数据驱动的方法

也称为按需路由算法，卫星节点通过相互发送数据包来获取路由信息，网络只在数据包传输时才更新网络拓扑结构和节点路由信息，无数据包传输时不更新。该方法适合网络拓扑结构及流量不大的小范围通信，且不需要存储全局信息，可以节省星上存储空间，但当网络流量较大时，网络拓扑及链路状态更新的需求十分频繁，对星上处理能力要求较高，且算法只考虑局部信息，不能从全局解决卫星失效与网络拥塞问题。

分布式的Darting[27]路由协议在传输数据包时才对网络拓扑状态进行更新，减少了节点之间的信息交互，避免了周期性的更新及泛洪产生的协议信息开销。分布式按需路由（Location-Assisted Ondemand Routing，LAOR）[28-29]算法借鉴了Ad-hoc网络中的按需距离矢量路由（Ad-hoc On-demand Distance Vector，AODV）[30-31]思想，只在需要路由时才发起一次路由过程，通过形成最小路由请求区域来减小路由开销，最小化端到端时延及时延抖动；计算网络中各条路径在每个时间段的生存周期，在有限区域内进行信令泛洪及节点应答等操作。文献[32]根据用户的分布情况动态分配带宽，为用户密集区域分配更多带宽。高效低时延路由（Efficient Improved On-demand Routing，EIOR）[33]算法采用RREP（route reply）分组免疫机制，中间卫星收到RREP分组后若收到对应的RREQ（route request）分组，则丢弃该RREQ分组，减小网络控制开销；增加中间卫星代替目的卫星回复应答的几率，缩短路径建立时间。

2.2.2 基于多播的方法

也称为组播路由算法，主要采用洪泛机制传输数据，包括基于源树（Source-Based Trees，SBT）的方法和基于核心树（Core-Based Trees，CBT）或共享树（Shared Trees，ST）的方法两类。该方法能够得到较多的候选路径，具有较高的路径探测性能，但洪泛机制导致网络广播信令增多，网络开销巨大，且多播算法的优化目标通常为最小化多播树的传输时延或树开销，无法主动避让繁忙链路，使得从源节点到中间节点的路径并非最优。

（1）基于SBT的方法主要用于多播成员较少的情况，多播路由算法（Multicast Routing Algorithm，MRA）[34]构建一棵以源节点为根的多播树，树中流量从根节点流向所有中间节点和叶节点。文献[35]预先设置传输时延上限，将满足限制的目的节点沿最小开销路径依次添加至多播树。动态源路由算法（Dynamic Source Routing algorithm in Satellite Constellation，DSRSC）[36]利用路由缓存机制降低整个网络的开销，提高了路由收敛速度。基于核心簇的特定源多播（Core-Cluster-based Source-specific Multicast，CSSM）[37]算法将源节点定义为簇首，新目的节点通过最短路径算法加入簇。基于时间尺度的多度量负载均衡多播算法（Load Balancing Multicasting algorithm based on Timeseales，LBMT）[38]获取ISL状态信息并设计评价其“比对开销”，建立“比对开销”多播树。文献[39]基于SBT的多播更新方法提高了网络收敛速度，降低了网络开销。

（2）基于CBT的多播路由算法主要针对多播成员较多的情况，它选择一个或多个节点作为核心节点，也称为汇聚点（Rendezvous Point，RP），网络中所有节点先将数据包发送给RP，然后由RP以泛洪的方式发送给其他节点。基于多核心共享树（Multi-Core Shared Tree，MOST）[40]的多播算法将整个网络分为8个相同规模的子网，每个子网中距离中心节点最近的目的节点称为子网的核心，再利用MRA得出核心到核心或核心到目的节点的路径。基于联合核心簇的共享树（Core-cluster Combination-based Share Tree，CCST）[41]的多播算法计算多播组的“质心”，并取距离质心最近的节点为核心，树外节点选择最低开销的最短路径加入组播树。基于直线Steiner树[42]的多播算法先建立一棵粗糙树，新节点计算到树上节点的最短路径并连接开销最小的节点加入多播树；源节点通过周期性向所有树上节点发送信息，对可能存在的重路由区域执行重路由操作，降低整体树开销。

2.3 考虑网络流量负载均衡的路由

静态和动态路由没有感知全网LEO卫星节点和链路状态，也没有对流量业务的特点进行分析并划分优先级，容易导致全网流量不均衡。考虑网络流量负载均衡的路由算法可以降低网络拥塞率，提高网络利用率和用户服务质量。

2.3.1 基于实时节点链路状态的方法

收集实时节点链路的状态信息主要有以下三种方法：

（1）基于链路感知的方法。也称为链路信息动态交互的方法，节点之间通过交互链路和自身状态信息，感知网络拓扑结构变化和网络拥塞情况，选择QoS最优的路由，在低负载的情况下，可以有效降低丢包率，但节点间频繁交换链路状态信息，协议开销较大。概率路由PRP[15]采用ISL传播时延作为路径度量，使用最短路径算法计算路由。在减小链路切换概率的同时，文献[43]对链路利用率进行了最大化，文献[44]满足了用户的QoS需求，文献[45]令通信时延最小化。文献[46]选择可用时间最长的链路作为最优路由。文献[47]为链路可用带宽设置一个阈值，只有大于阈值该链路才能进行数据传输。高性能卫星路由（High Performance Satellite Routing，HPSR）[48]协议通过一次呼叫接入实现在全网范围内重新分配带宽及计算路由。文献[49]根据网络拓扑结构和网络流量变化进行链路的最优化分配。文献[50]采用一种逐跳机制来分割流量负载，以缓解极区附近发生的拥塞问题。精确负载均衡（Expl icit Load Balancing，ELB）[51]路由算法采取链路信息动态交互的方式，邻近卫星交换队列使用状况以表示其目前的拥塞状况，即将发生拥塞的卫星则主动发送信号给邻居节点，通知其降低数据发送速率，邻节点选择次优路径，从而减少网络拥塞。基于链路状态的卫星网络路由（Satellite Link State Routing，SLSR）[52]协议优化了OSPF协议的Hel lo消息机制，当节点第一次接收到邻居的Hello消息时，不需要应答便开始交换数据，加快了路由协议的收敛速度，但通过减少Hel lo的发送周期使得网络的丢包率增加，通信质量和稳定性变差。受限最短路径优先（Constraints Shortest Path First，CSPF）[53]算法采用链路带宽的反比定义链路权重，根据业务QoS需求，通过链路状态数据库计算最短路径。文献[54]实时感知链路状态信息并作出路由决策。文献[55]利用遗忘函数测算数据包排队时间，并由路径上卫星节点的位置信息和每条ISL的开销确定路由开销。文献[56]通过卫星节点监测自身缓存队列中分组的数量估算排队时延。文献[57]考虑卫星链路时延和带宽资源建立相关优化模型，降低了业务传输时延，提高了网络中的带宽利用率。文献[43]利用相对空闲链路来减少链路拥塞，降低了端到端时延。文献[58]根据ISL队列占用情况设计了ISL可用指数，并基于网络流量分布特点提出了卫星可用指数。文献[59]通过平衡网络时延和分组丢失率降低星上处理的复杂度。文献[60]以ISL时延作为计算开销来判断路由选择的优劣，并对网络中的非对称链路进行相应处理。文献[61-62]基于多目标决策理论，根据链路时延、剩余带宽和丢包率计算权值系数，确定目标函数和约束条件，建立多目标优化模型，计算满足业务QoS需求的路由。文献[63]借鉴经济学中合作博弈论的优化策略，将一条路径上的多个中继节点作为一个合作博弈联盟，利用节点实时状态信息以及网络路由性能指标定义该联盟的合作收益，采用夏普里值（Shapley value，SV）作为合作博弈的解，确定最优路径。针对网络的业务量大小和链路切换问题，文献[64]将链路状态和拓扑快照进行联合优化，根据业务量大小更新链路的权值。自适应权值路由算法[65]考虑网络时延和链路切换，依据卫星节点的当前状态和链路权值，选择开销最小的路由，均衡流量负载。

（2）基于历史信息预测的方法。网络拓扑结构变化、网络流量拥塞及链路的利用率等历史信息可用来对未来网络拓扑、流量及链路状态进行预测估计，减少了网络节点间频繁的信息交互，降低了网络负载，但由于卫星节点的不断移动导致不同条件下网络的参数差异较大，历史信息预测结果与实际网络状态的误差较明显，影响了路由算法的有效性。基于优先级的自适应路由（Priority-based Adaptive Routing，PAR）[66]算法根据链路利用率的历史信息和当前缓冲队列的大小，计算网络中横、纵两个方向路由的优先级，得到最小跳数路径。基于拥塞预测的路由（Congestion-Predictionbased Qos-Aware routing，CPQA）[67]算法根据网络拥塞历史信息预测并假定某一区域为拥塞区域，当卫星节点即将经过该区域时，该节点通知相邻节点将低QoS需求的数据绕过该卫星。基于流量预测的分布式路由算法（Distributed Routing Algorithm with Traffic Prediction，TPDRA）[68]通过流量预测来分析数据拥塞情况，根据预测结果选择相对时延低的路径。文献[69]将链路可用性评估与网络拓扑预测相结合，数据传输时延有所降低。文献[70]对卫星链路可用性和传输成功率进行感知和推理，得到ISL质量评价结果并用于路由优化。文献[71]将网络流量预测值作为路由决策过程中调节因子的一个保护量，防止产生正反馈效应。文献[63]通过在数据中传递额外的网络状态信息，实现卫星节点对于不同路由方向上网络状态的实时感知与预测。

（3）基于Agent的方法。基于代理（Agent）的协议通过Agent来收集网络链路时延和节点拥塞信息，从而计算最优路由。该方法通过Agent传输信令，网络开销较低，能在负载很高的情况下降低网络平均端到端时延和丢包率，提高吞吐量。基于代理的负载平衡路由（Agent-based LoadBalancing Rout ing，ALBR）[72]算法使用静态Agent和移动Agent来收集信息，静态Agent主要负责周期性评估链路代价并计算路由，移动Agent则随机选择最远目的节点选择路由。文献[73]将移动Agent搜索的路径作为从源卫星节点到目的节点的最优路由，并收集纬度信息和ISL开销来参数化卫星。文献[58]综合卫星节点和ISL可用指数提出了移动Agent迁移策略、星际QoS路由及其重建算法等。文献[70]应用“多智能体”作为Agent进行链路认知。典型算法还有基于多代理的分布式多路径路由算法（Distributed Multipath Routing strategy combined with Multi-Agent System，MASMR）[74]和基于Agent的分布式流量预测路由算法（Agentbased distributed Routing Algorithm with Traffic Prediction，TPARA）[75]等。

2.3.2 基于业务分类的方法

该方法根据业务优先级选择路由，可以有效地均衡卫星网络负载，提高吞吐量，但需要大量存储空间缓存等待转发的数据包，对星上存储空间要求较高。基于不同的Qo S需求，多业务类Qo S路由（Multi-class QoS Routing，MQoSR）[76]算法根据时延和带宽指标将业务分为三类并分配优先级，依据优先级对网络各链路状态进行分析计算。文献[77]将业务分为最小端到端时延、最大吞吐量和尽力而为三种类型，针对不同的业务类型分别计算路由表。文献[78]对话音和数据业务提供差异化服务。文献[28]为不同类型的业务单独调用最短路径发现进程，满足网络中话音业务的QoS需求。分布式多服务按需路由（Multiservice On-demand Routing，MOR）[79]协议针对特定的业务种类启用不同的路由选择方式，在保证不同业务QoS的同时提高网络效率。文献[80]基于拓扑快照，综合考虑业务优先级、占用带宽和持续时间来计算路由。文献[81]为不同类型数据选取不同的下一跳，同时引入权值调节因子调整链路权值，均衡处于热点纬度卫星的负载。文献[82]将业务分为时延敏感、带宽敏感和可靠性敏感三类，采用本征向量法计算业务权值，并利用一致性比率方法对权值进行判定。文献[83]运用多业务加权分簇的算法，在链路状态通告（Linkstate Advertisement，LSA）扩散阶段对网络分簇。文献[71]利用不同卫星业务的时域、空域及频域差异，对信息素进行定量描述和动态学习，使信息素动态地反映网络链路状态。

2.3.3 基于多路径的方法

根据选择不同的优化目标，源、目的节点之间通常存在多条可用路径，使用多路径的方法，可以计算分别满足时延最小和带宽限制的最优路径。该方法考虑卫星星座拓扑结构的特点，采用实现较简单的链路跳数为路由代价寻找多条备选路径，增强了卫星网络的抗毁能力和流量负载均衡能力，降低了星上的路由开销，但在备选路径中选择最优路径的策略比较单一，无法实现全局最优。

交替链路路由（Al ter na te Lin k Rout ing，ALR）[84-85]算法采用ALR-S与ALR-A两种调度策略，结合最优与次优路径选择路由。ALR-S策略规定数据包在源节点选择次优路径，在中间节点选择最优路径；ALR-A策略则规定数据包在路径上的所有节点交替选择最优和次优路径。紧凑显示多路径路由（Compact Explicit Multi-path Routing，CEMR）[86]算法基于源路由思想划分卫星平面，每个平面通过单星收集与其他平面交互的信息，采用无环路由备份和路径信息压缩编码双重机制。文献[64]计算最短及第二或第三短路径以供备选。文献[87]结合流量密度、优先级、错误QoS需求等，通过源节点到目标节点的多路径联合选择均衡流量，提高了网络利用效率。基于红绿灯信号机制的智能多径路由策略（Traff ic-light-based Intelligent Routing Strategy，TLR）[88]以传输时延最小化为目标，计算从源节点到目的节点的多条路径，同时节点将自身队列占用率等状态信息作为邻居节点的红绿灯信号信息进行周期性广播。路由时，数据包根据邻居节点的红绿灯信号信息，尽量绕开拥塞卫星节点，对路径进行局部调整。

2.3.4 基于智能优化的方法

为解决路由NP优化问题，研究者利用计算机的大规模计算能力，应用智能优化算法取得了不错的效果，该方法也称为启发式优化方法，可以提高最优路由的搜索效率，均衡网络负载性能，但算法开销较大，只能在地面离线计算，不适合星上处理，算法灵活性较差。典型算法包括遗传算法（Genetic Algorithm，GA）[89]、模拟退火（Simu lated Annealing，SA）[90]算法、粒子群（Particle Swarm Optimization，PSO）[91]算法、蚁群（Ant Colony Optimization，ACO）[92]算法、人工蜂群（Artificial Bee Colony，ABC）[93]算法等。文献[94]基于遗传算法，将链路时延和路径老化特性引入QoS目标函数，选择拟合度最高的路径作为最优路径。文献[95]结合遗传算法与线性规划的思想均衡了网络负载。文献[85]重新设计了适应度函数和变异概率，利用遗传算法和模拟退火思想解决初始种群的多样性问题。文献[96]利用粒子群算法中的交叉嫡模型启发式地求解按需路由的快速收敛问题。文献[97]根据蚁群算法的节点概率函数选择下一跳节点，求解能同时满足时延、带宽和链路容量要求的最佳路径。