一种具有导向功能的ＬＥＯ网络源路由改进算法

王鸣涛　周　诠　黄普明

摘 要：针对全网广播路由导致系统利用率低的问题，结合卫星通信网络的周期性和准确预知等特点，在源路由算法(SRA)的基础上，引入方向性指导策略，提出了具有导向功能的源路由改进算法(i-SRA)。由于采用部分广播方式，仅向靠近目的节点的相邻卫星发送路由请求分组，降低了请求分组传输的盲目性。通过OPNET建模仿真，结果表明改进算法减少了路由负载开销，提高了资源利用率。

关键词：LEO卫星网络;导向策略;源路由;路由负载

中图分类号：TN927文献标识码：B

文章编号：1004-373X(2009)05-004-03

Improved Source Routing Algorithm with Directional Function for LEO Satellite Network

WANG Mingtao,ZHOU Quan,HUANG Puming

(National Key Laboratory,Xi′an Institute of Space Radio Technology,Xi′an,710000,China)

Abstract：Due to a low system usage of a route method which broadcasting in whole satellite networks,an improved approach adopting the directional strategy to the source routing algorithm in LEO satellite network is proposed,because the change of LEO satellite network is deterministic and can be predicted quite accurately.The strategy with partial broadcast forwards request route packets to satellites near the destination and the blind delivery of packets is reduced.In addition,the performance of the improved routing algorithm is evaluated by the OPNET modeling and simulation.The result shows that routing load is decreased and the utilized coefficient is raised.

Keywords：LEO satellite network;directional strategy;SRA;routing load

0 引 言

卫星通信具有覆盖地域广、长距离传输和易实现广播的特点，并且能够支持多媒体通信业务，成为军用和民用领域一种重要的通信手段。随着星上处理能力的增强，在卫星上采用路由交换技术已成为现代卫星网络发展的重要趋势之一。

目前，针对星上路由算法的研究大多采用将系统周期分割或者将覆盖区域分割的方法，屏蔽卫星网络拓扑结构的动态变化，在静态拓扑结构下设计星上路由算法。

系统周期分割方法虽然离线计算星上路由，卫星仅在时间分割点更新，对星上处理能力要求较低，但是不能根据链路的状态实时地选择路由，适应性差，并且由于分割的拓扑快照太多，导致星上需要大量的存储空间。

而覆盖域分割方法却根据分组的目的地理信息，在不同地面覆盖划分区域组成的静态逻辑结构上，依据路由策略和链路负载、故障、拥塞等情况实时计算路由，具有适应能力强，所需存储空间小，同时提供QoS保证的优点，因而，覆盖域分割类型的路由算法具有较强的优势，但由于星上处理能力和功耗的限制，该类算法较多的系统资源消耗需要尽量地减小。

类似IP网络的卫星网络路由机制中，每颗卫星保存整个卫星网络的拓扑图，实时地根据星间链路状态，将地面网关发送来的封装数据转发到目的卫星节点，但文中未见采用的路由算法。Ekici等人提出的分布式路由算法中，每颗卫星根据自身链路状态局部信息，按照逻辑地址为每个分组独立地选择最小传输时延路径。由于利用了卫星网络周期性和预知性的特点，路由开销非常小，但是每个分组采用相同的操作独立地路由转发，不区分对待不同业务类型，因而不能提供不同的服务质量。Admela J等设计的具有QoS保证的LEO网络源路由算法(Source Routing Algorithm，SRA)，源节点广播路由请求分组到目的节点，目的节点根据不同传输业务的不同服务要求，反馈相应的最优路径。虽然能够反映网络状态的变化，但是采用全网广播路由致使开销巨大。

本文结合卫星网络的特点，在LEO网络SRA算法的基础上，引入方向性指导策略，提出具有导向功能的源路由改进算法(improved Source Routing Algorithm,i-SRA)，并对其进行性能分析与仿真验证。

1 卫星网络的特点

由于卫星快速移动，星间链路频繁地切换，致使依靠不断交换拓扑信息来维护网络路由的地面路由技术不能适用于卫星网络。与地面网络相比，卫星网络有着其独有的特点。

卫星快速移动的影响 主要体现在：随着卫星的移动，轨道间的ISL长度不断变化，越过极区时需要不断开启或关闭，导致卫星网络的拓扑结构是动态的；针对星间链路的不断失效或生效，为保证通信路径的畅通，需要不断地进行链路切换；星下点覆盖域变化时，由于用户业务地域分布不均匀，导致卫星的通信量动态变化，极不均衡；由于卫星的轨道是固定的，网络拓扑的变化具有周期性、预知性。

卫星功率和星上处理能力有限 由于卫星通信环境的特殊性，星上设备的体积、功耗等都受到限制。路由选择的处理过程越复杂，所需的星上处理能力就越强，消耗的功率越多，卫星的寿命可能就会缩短。另外，一旦卫星发射，所应用的技术不能改进升级，存储和处理能力不能扩展。

其他特点 卫星网络中，星间链路传输距离较远，卫星轨道较高，卫星通信具有非常大的延时，对网络协议实现、高性能QoS服务等方面影响很大；卫星网络的节点数目通常是固定不变的；对星座网络来说，其拓扑结构具有很高的规则性和均衡性，使得卫星节点对之间存在许多可备选的通信链路。

星上路由算法与卫星网络的拓扑结构密切相关。虽然网络拓扑结构动态变化为星上路由算法增加了设计难度，但也有简便的一面。可以充分利用卫星网络的周期性和准确预测性、规则性和均衡性、以及节点数目少且固定的特点，来简化路由算法。

2 具有导向功能的源路由改进算法i-SRA

2.1 源路由SRA算法

源路由SRA算法是由源节点卫星发起的，目的节点卫星决定路由的面向连接的按需路由算法，采用覆盖域分割的策略来解决卫星网络拓扑结构的动态变化。对于每一次呼叫连接，SRA算法将路由请求分组全网广播传输到目的节点。在星间链路上传输的同时，路由请求分组收集传输路径上经过卫星节点的状态信息。目的节点收到请求分组后，依据这些信息来决定最合适的路由。

2.2 全网广播路由的局限性

由卫星网络特点可知，卫星的移动性会增大路由算法设计的难度，但由于卫星运行的轨道和地球自传速度是固定的，网络节点数目不变且非常少，所以卫星网络拓扑的变化是确定的，能够进行准确地预测。

但是采用全网广播路由请求分组来建立最优路径的方式，未能结合卫星网络这些有利条件来优化算法，仍向远离目的地址的卫星节点发送大量的路由请求分组。然而这些请求分组因为路由跳数过多，传输时延过长而被淘汰，结果该方向未形成最终的传输路径。由于星上功率和处理能力有限且十分宝贵，采用全网广播路由方式产生了过多无用的请求分组，导致网络资源的浪费。

2.3 改进算法i-SRA

卫星网络具有周期性和预知性，源节点卫星根据自己覆盖区域的逻辑编号(例如由轨道号和轨内卫星编号组成)以及传输分组包含的目的逻辑区域的逻辑编号，就可以得到目的节点的当前方位，估计传输路径所需的最小路由跳数。源节点根据这些先验信息，来定向地路由或直接转发分组。这一特性就是方向性指导策略，可以用来简化路由算法的复杂性以及减小路由开销。

i-SRA算法就是采用方向性指导策略，对LEO网络源路由SRA算法进行改进，以期降低路由算法的网络开销，提高资源利用率。

具有导向功能的源路由改进算法i-SRA的基本思想是：基于源路由SRA算法，根据方向性指导策略，对每次呼叫连接的路由请求分组以部分广播的形式传输。所谓的部分广播，就是在预知目的节点具体方位后，只将请求分组传播到那些与目的节点方向一致的星间链路上。也就是说，如果目的节点在东南方向，请求分组就不会被发送到通向西北方向的星间链路上。

具体算法描述如下：

Step 1：需要与远程目的用户D通信的源用户S向覆盖域内过顶时间最长的卫星Sat-S发送呼叫请求；

Step 2：源卫星节点Sat-S根据接收的呼叫请求，判断目的用户所在的逻辑覆盖区域以及具体方位，并依据呼叫请求的业务类型产生具有特定要求的路由连接请求；

Step 3：根据目的节点的方位，按照导向策略，选择同方向能够满足设定要求的星间链路；

Step 4：源卫星节点Sat-S将路由请求分组在已选链路ISL上传输，转发给相邻卫星节点，然后这些卫星节点以相同的方式将请求分组转发到其他相邻卫星，直至到达目的用户所在逻辑区域上空的目的卫星节点Sat-D；

Step 5：目的节点卫星Sat-D通知目的用户D有呼叫到达，并且在到达的多条候选链路中，选择满足呼叫业务要求(比如最小跳数)且最长寿命时间的链路作为最终的传输路径；

Step 6：Sat-D卫星沿着选择的路径，向Sat-S卫星反馈路由信息分组，同时获得通信资源的预留。当源卫星节点Sat-S获得该路由信息分组时，该通信链路就成功建立了。源用户S开始向目的用户D传输数据；

Step 7：已建立通信链路的寿命时间到达时，如果通信业务还未结束，回到Step 3，提前重新路由，并进行链路的切换。

2.4 i-SRA算法性能分析

改进算法i-SRA采用部分广播的方式，只将路由请求分组传播到与目的节点方向一致的星间链路上，没有在全网上传输。虽然与目的节点方向相反链路上传输的请求分组最终也可能到达目的节点，但是由于星间链路延时本身就比较大，其经历的卫星节点又很多，结果获得传输路径的延时非常大，在众多候选路径中最终也会被淘汰。

所以，i-SRA算法利用了网络拓扑结构的可预知性，减少请求分组传播的盲目性，不产生这些易被淘汰的路径，从源头上减少网络中路由请求分组的传输数量，节约了处理这些分组所耗费的星上功率，提高了网络资源的利用率。

3 仿真验证

使用STK软件构建了参数T/P/F为30/5/0(其中表示卫星数目为30颗，轨道数目为5，相位因子为0)的LEO圆形极轨walker星座，如图1所示。网络中卫星轨道高度为1 375 km，轨道倾角为84.7°。并且采用OPNET网络分析工具仿真了LEO卫星网络运行12 h期间路由负载的情况。

如图2所示为LEO网络源路由SRA算法和改进算法i-SRA的平均路由负载结果。源路由算法SRA每次路由的平均负载大约为11个路由请求分组，而i-SRA算法大约为8个路由请求分组。相比之下，i-SRA算法将路由选择的请求分组数量降低了近27.3%，减少了多余的无用分组。

通过仿真表明，采用方向指导策略后的i-SRA算法相比源路由SRA算法确实能够降低建立传输路径所需要的路由开销，提高网络资源利用率。

4 结 语

根据卫星网络周期性和预知性的特点，针对LEO网络源路由算法SRA采用全网广播路由方式导致系统开销大的缺陷，结合方向性指导策略，提出了具有导向功能的星上源路由改进算法i-SRA。由于减小了路由请求分组传输的盲目性，i-SRA算法从源头上降低了卫星网络中建立通信路径所需的请求分组传播数量，节约了星上处理资源。

在OPNET平台上建立了Walker圆形极轨卫星网络，并对改进算法的性能进行了分析验证。仿真结果表明，改进的i-SRA算法相比源路由SRA算法能够在很大程度上减少路由开销，提高卫星网络资源的利用率。

参考文献

［1］Alagoz F,Korcak D,Jamalipour A.Exploring the Routing Strategies in Next-Generation Satellite Networks［J］.IEEE Wireless Communications,2007,14(3):79-88.

［2］Chang S,Kim W.FSA-based Link Assignment and Routing in Low-earth Orbit Satellite Networks［J］.IEEE Trans.on Vehicular Technology,1998,47(3):1 037-1 048.

［3］Vidyashankar V Gounder,Ravi Prakash,Hosame Abu Amara.Routing in LEO-based Satellite Networks［J］.Proceedings of IEEE Emerging Technologies Symp:Wireless Communications and Systems,1999.

［4］Hashimoto Y.Design of IP-based Routing in a LEO Satellite Network［J］.Proceedings of the 3rd International Workshop on Satellite-based Information Services,Dallas,1998:81-88.

［5］Wood L.IP Routing Issues in Satellite Constellation Networks［J］.International Journal of Satellite Networks,2001,19(1):69-92

［6］Ekici E,Akyildiz I F,Bender M D.A Distributed Routing Algorithm for Datagram Traffic in LEO Satellite Networks［J］.IEEE/ACM Trans.on Networking,2001,9(2):137-147.

［7］Admela J,Hoang N N,Harmen R.An Approach to QoS-based Routing for LEO Satellite Networks［J］.Communication Technology Proceedings,2000,WCC-ICCT:922-929.

作者简介 王鸣涛 男，1984年出生，硕士研究生。主要研究方向为卫星数据传输与处理。

周 诠 男，1965年出生，博士、研究员、博士生导师。主要研究方向为卫星数据传输与处理、航天器通信技术。

黄普明 男，1971年出生，博士、研究员、硕士生导师。主要研究方向为卫星数据传输与处理、航天器通信技术。