应用多智能体链路认知的低轨卫星网络路由算法

双炜

（山东航天电子技术研究所，山东烟台 264670）

1 引言

低轨卫星网络中的卫星沿着各自轨道高速运转，使整个网络的拓扑结构快速变换，这对网络中的路由机制提出了特殊要求。此外，卫星轨道低，面临着各种干扰，星际链路质量会发生不可预测的变化，也使通信网络路由面临着严重挑战。

国内外对卫星网络上的路由机制进行了一些研究，主要包括负载平衡路由技术、服务质量（QoS）路由技术和多服务路由技术。早期的卫星网络路由算法［1-4］着眼于寻找一条连接源卫星和目的卫星的路由，自适应能力较差。随着研究的深入，负载平衡问题逐渐受到重视［5］。然而，现有的分布式负载平衡路由技术，仅使用局部流量信息，不能反映出全局流量分布情况［6］。近年来，卫星网络QoS得到重视并取得了一些成果［7］，不过其由于计算复杂度过高而无法在实际工程中应用，而且算法性能不高导致找到的链路不是最优的。文献［8-10］中提出了卫星网络多服务路由技术，但它的路由更新是以周期性为主，对网络流量变化自适应能力不强，且要维护大量链路状态信息，导致网络开销大。

为了克服上述卫星网络路由技术的不足，本文提出了一种多智能体链路认知的低轨卫星路由算法，运用移动智能体技术［11］和认知理论［12］解决低轨卫星网络的路由问题。该算法可通过多智能体对节点负载、链路投递率和链路可用性等环境进行感知和推理，实时获得网络中星际链路的质量评价，且评价结果能实时地用于路由的自适应优化，可提高低轨卫星网络通信的路由性能。

2 路由算法描述

2.1 基本思路

应用多智能体链路认知的低轨卫星网络中卫星节点的路由更新算法体系结构，如图1所示。每个卫星节点中部署静止智能体、移动智能体和管理智能体。其中：静止智能体可包括多个，如链路代价／位置智能体、路由表维护智能体等。移动智能体自治迁移探测路径，一旦迁移入某个卫星节点，即成为该卫星节点的访问智能体。访问智能体通过与静止智能体的信息交互来感知网络链路，收集路由信息（包括星际链路代价、卫星位置等），更新路由表。而且，移动智能体以传递路由信息的方式通知路由表维护智能体更新路由表。管理智能体负责静止智能体、移动智能体的创建，与后两者共同完成监控星际链路的工作状态、评估星际链路代价和更新路由条目的任务。

图1 卫星节点的路由更新算法体系结构Fig.1 Satellite node routing updating algorithm architecture

低轨卫星网络路由更新过程中，为了避免出现返回的移动智能体滞后问题，将移动智能体分簇，并限制单个移动智能体移动的最大范围，让簇内移动智能体完成簇内的链路感知任务，簇间移动智能体完成簇间的信息交接，以保证时延达到要求，同时也避免使用多个移动智能体。

2.2 卫星节点状态感知

卫星节点状态感知主要由移动智能体来完成。移动智能体感知获取相关链路信道质量和卫星节点对业务流负载的处理能力等性能参数。根据移动智能体的成功投递率，可获取卫星节点的成功投递率（间接反映链路上的通信干扰及其数据传输率）；通过感知卫星节点队列缓存容量的占用率，可获取卫星节点间链接的可用性。占用率反映本卫星节点的业务流强度，并反映卫星节点还可接纳的分组容量。

在移动智能体迁移过程中，卫星节点j 完整地接收到另外一个邻居卫星节点i 传输过来的信息帧，则认为一个帧发送、接收成功；如果接收到的帧发生校验错误，或因为发生冲突造成帧接收不完整，则认为该帧丢失。移动智能体的成功投递率为

式中：Ns（i，j）和Nr（i，j）分别为卫星节点i到相邻卫星节点j发送和成功接收的数据帧数目。

设卫星节点i的队列缓存总容量为C（i），当前缓存分组数为M（i），则其队列缓存当前占用率为

2.3 星际链路状态推理

通过移动智能体获取卫星节点的成功投递率，以及队列的缓存容量占用率等基础状态信息。星际链路质量的良好程度与卫星节点的成功投递率、卫星节点的队列缓存空闲度均有关，如果只考虑成功投递率，会出现网络节点负载不均衡，使单个卫星节点负载过高而影响整体性能。为了达到网络节点负载均衡的目的，即相关卫星节点的负载相等时会得到一个性能的极好值。设卫星节点i和卫星节点j的队列缓存空闲度分别为Li和Lj，表示节点能继续承担的网络负载能力大小，用来衡量卫星节点平衡程度。在节点队列缓存空闲度之和Li＋Lj一定时，当Li＝Lj时，即负载均衡时取极大值。

定义卫星节点i与j 之间链路质量状态的良好程度为

式中：α和β为预设的指数，取值范围为［0，3］；Li＝1-ηi。

3 多智能体路由优化选择

链路状态推理过程中使用两种移动智能体，即前向智能体和后向智能体。前向智能体使用高优先级队列及时传递路由信息，每隔固定的时间，各卫星节点加载前向智能体，并派遣至网络中；此后，前向智能体在卫星网络中自治地迁移，通过与部署在所到达卫星节点中的静止智能体交互，感知链路状态。前向智能体到达目的卫星节点时自动转换为后向智能体。后向智能体沿着前向智能体的路径反向迁移。在各中间卫星节点，后向智能体与静止智能体交互，向其传递路由信息。后向智能体根据获取的路由信息更新卫星路由表。移动智能体工作过程如图2所示。

路径优化选择原则为：源卫星节点和目的卫星节点分别为ns和nd，两个节点之间的路径集合定义为R，假如R ≠∅，满足条件为的路径P 即为ns到nd所要选择的路由路径。该路径上所有链路的质量良好程度之和为YP，ns和nd之间的任何一条路径由网络节点序列（n1，n2，…，nk）表示为式中：k为该路径经过的中间节点总数；nm为该路径上第m 个中间节点。

图2 移动智能体工作过程示意Fig.2 Travelling agent work process

4 仿真试验

4.1 仿真环境

以类似“铱”（Iridium）的卫星系统为研究对象，对本文算法进行仿真验证。假设数据从源终端经过卫星系统传输到达目的终端，仿真环境设置如表1所示。

表1 仿真环境参数Table 1 Simulation environment parameters

以下对吞吐量、丢包率和端到端时延等指标，分别用本文提出的算法与传统的自适应最短路径路由算法［13］进行比较。

4.2 仿真结果与分析

1）吞吐量

图3 为网络吞吐量随着终端数据率的变化情况。从图3可以看出，当终端数据率较低时，本文算法和自适应最短路由算法基本一致，负载较高时，本文算法的吞吐量能提高7%～22%。

图3 不同终端数据率下的吞吐量Fig.3 Thruput at different terminal data rates

2）丢包率

图4为网络不同终端数据率下的丢包率变化情况。从图4可以看出，数据率较低时，两种算法的丢包率都接近于0，但是随着数据率的增加，本文算法丢包率明显低于自适应最短路由算法。

图4 不同终端数据率下的丢包率Fig.4 Packet loss rate at different terminal data rates

3）端到端时延

图5为网络不同负载下的端到端时延变化情况。从图5可以看出，负载较低时，本文算法端到端时延明显长于自适应最短路径路由算法；但负载较高时，本文算法时延要短于自适应最短路径路由算法。这是因为：在低负载情况下，本文算法的数据包穿越了较多的跳数，需要较长的时延，而自适应最短路径路由算法基于优先级的选择机制，偏向于最少跳数的路径路由，需要较短时延；当负载较高时，自适应最短路径路由算法性能急剧下降，更容易拥塞，导致长时延。因此，本文算法在高负载情况下具有优势，更适用于流量变化剧烈的低轨移动通信网络。

图5 不同终端数据率下的端到端时延Fig.5 End to end delay at different terminal data rates

5 结束语

本文在低轨卫星网络通信路由中引入了多智能体技术和认知理论，提出了一种路由算法，在自适应最小路径的基础上，通过感知星际链路投递率和链路可用性等信息，反映卫星网络中卫星节点处理负载的能力，根据卫星节点的感知信息对链路质量进行推理，获得星际链路质量评价，再进行路由的优化选择，从而提高网络的吞吐量，实现负载均衡。本文提出的算法可以提高低轨卫星网络路由的环境适应性，为我国低轨卫星通信网络建设提供参考。

（References）

［1］Alagoz F，Korcak O，Jamalipour A.Exploring the routing strategies in next-generation satellite networks［J］.IEEE Journal on Wireless Communications，2007，14（3）：79-88

［2］Werner M，Delucchi C，Vogel H，et al.ATM-based routing in LEO／MEO satellite networks with intersatellite links［J］.IEEE Journal on Selected Areas in Communications，1997，15（1）：69-82

［3］Werner M，Berndl G，Edmaier B.Performance of optimized routing in LEO intersatellite link networks［C］／／Proceedings of IEEE 47th Vehicular Technology.New York：IEEE，1997：246-250

［4］Werner M.A dynamic routing concept for ATM-based satellite personal communication networks［J］.IEEE Journal on Selected Areas in Communications，1997，15（8）：1636-1648

［5］Taleb T，Jamalipour A，Kato N，et al.Computer and information sciences-ISCIS［M］.Verlag Berlin：Springer Berlin Heidelberg，2005：113-123

［6］Chatterjee P，Das N.Distributed computing and networking［M］.Verlag Berlin：Springer Berlin Heidel-berg，2008：332-338

［7］Molinaro A，De Rango F，Marano S，et al.A scalable framework for end-to-end QoS assurance in IP-oriented terrestrial-GEO satellite networks［J］.IEEE Communications Magazine，2005，43（4）：130-137

［8］Svigelj A，Mohorcic M，Kandus G，et al.Routing in ISL networks considering empirical IP traffic［J］.IEEE Journal on Selected Areas in Communications，2004，22（2）：261-272

［9］Mohorcic M，Svigelj A，Kandus G.Traffic class dependent routing in ISL networks［J］.IEEE Transactions on Aerospace and Electronic Systems，2004，40（4）：1160-1172

［10］Gorazd Kandus，Ales Svigelj，Mihael Mohorcic.The impact of different scheduling policies on traffic class dependent routing in intersatellite link networks［J］.International Journal of Satellite Communications and Networking，2004，22（5）：533-546

［11］Fünfrocken S，Mattern F.Kommunikation in verteilten systemen（KiVS）［M］.Verlag Berlin：Springer Berlin Heidelberg，1999：32-43

［12］Gelenbe E，Liu P，Szymanski B K，et al.Cognitive and self-selective routing for sensor networks ［J］.Computational Management Science，2011，8（3）：237-258

［13］Korcak O，Alagoz F，Jamalipour A.Priority-based adaptive shortest path routing for IP over satellite networks ［J］.International Journal of Communication Systems，2007，20（3）：313-333