基于链路权重的分布式星群网络路由算法

刘治国，张自敬，李秦锋

（大连大学a.信息工程学院；b.辽宁省通信网络与信息处理重点实验室，辽宁大连116622）

基于链路权重的分布式星群网络路由算法

刘治国a，b，张自敬a，b，李秦锋a，b

（大连大学a.信息工程学院；b.辽宁省通信网络与信息处理重点实验室，辽宁大连116622）

针对分布式卫星群间网络传输时延长、链路连接不稳定的问题，提出一种基于链路权重的改进AODV路由算法。利用链路时延和连接时间定义链路权重，调整蚁群算法的信息素大小，使数据包在传输过程中能够选择权重较小的链路，避开拥塞路径并均衡网络负载。采用蚁群算法改进AODV协议的路由表，达到优化分布式星群网络路由选择的目的。仿真结果表明，该算法在路由选择过程中能够选择低负载的路径，且当数据包发送速率高于600 Kb/s时，与位置辅助路由算法、AODV算法相比，具有较低的平均端到端时延和丢包率，以及较高的网络吞吐量。

分布式卫星网络；路由算法；蚁群算法；链路权重；AODV协议

1 概述

分布式卫星网络是指由分布在一个或多个相近轨道平面上的多个卫星组成的卫星网络，以一颗主星的方式，完成通信、遥感探测、跟踪定位等单颗卫星完成不了的任务［1］。而分布式星群网络是指由多个分布式卫星网络组成的星群通信网络，能够为大范围、长距离的客户端提供满足要求的服务。为提供高质量、无间断的服务，每个单独的分布式卫星网络都需要数颗卫星组成，这些卫星具有星上处理能力，卫星之间具有星际链路，与其他星群通过主星或者中继卫星进行通信。由此可见，分布式星群网络的卫星数目多、轨道周期长、覆盖区域大，在通信时既要考虑群内路径，又要兼顾群间路径。所以，路由问题一直是分布式星群网络研究的重点和难点［2-3］。

针对卫星网络路由问题，目前研究人员已提出流量工程路由算法［4］、基于预案的卫星网络路由算法［5］、动态故障容忍路由算法［6］等多种算法。文献［7］提出负载均衡路由协议PAR，根据链路过去的利用率与缓存信息确定链路等级，进而利用该等级选择下一跳，但PAR存在负载反映滞后的问题。文献［8］提出一种双层星座中负载均衡路由协议LBRD，利用分层思想，层间卫星采取地理位置路由策略，利用邻间链路负载通告的方式，调节单颗卫星的负载，但多颗相邻卫星过载时调节缓慢。文献［9］提出位置辅助路由协议LAOR，LAOR协议本质上是按需路由协议，利用卫星网络轨道的周期性，将路由请求（RREQ）分组限制在一定范围内，缩小了路由查找范围，但没有考虑卫星网络链路状态。

然而上述卫星路由算法都是针对卫星群内网络设计，不适用于分布式卫星群间网络。因此，本文针对分布式卫星群间网络的时延大、连接时间不固定等特点，提出一种适用于分布式卫星群间网络的路由算法：基于链路权重的改进AODV路由算法（Link W eight-based Ad Hoc On-demand Vector Routing，LW-AODV）。该算法利用链路时延和连接时间定义链路权重调整信息素大小，使数据包在传输过程中能够选择权重较小的链路。

2 AODV路由协议和蚁群算法

分布式卫星群间网络不仅具有传统卫星网络的特征，而且与Ad Hoc网络类似。一个星群本身即可视为Ad Hoc网络中的一个簇，簇头与簇头的通信可视为星群间主星的通信。因此，Ad Hoc路由算法对分布式星群路由算法的设计有一定的借鉴意义。

目前，经典的Ad Hoc网络路由协议主要有目的节点序列距离矢量（Destination Sequenced Distance Vector，DSDV）路由协议、动态源路由（dynamic Source Routing，DSR）协议、Ad Hoc网络按需距离矢量路由（AODV）协议。DSDV路由协议解决了无穷环路的问题，DSR路由协议解决了周期发送路由包的问题，而AODV路由协议是两者的结合，其在卫星网络适用性和性能方面已经得到验证。本文借鉴AODV协议思想，将其与改进的蚁群算法相结合应用于分布式卫星群间网络，以提高路由效率。

2.1 AODV路由协议

AODV路由协议是在DSDV协议的基础上结合DSR中的按需路由机制提出，因此，既有DSDV的逐跳路由、序现形式，又依据DSR形成特有的路由发现和路由维护过程。

（1）路由发现

源节点（Src）有数据包需要发送时，则启动路由发现过程。源节点向其邻节点广播路由请求报文RREQ。中间节点收到RREQ时，首先建立到上一跳的反向路由，接着查找自己的路由表，如果存在到目的节点（Dest）的有效路由，则通过已建立的反向路由返回路由应答（RREP）报文［10］；否则继续向邻节点广播RREQ，直到该RREQ到达目的节点，由目的节点生成RREP，并沿已建立的反向路由将RREP发送给源节点［11-12］。依次类推，直到到达目的节点或是中间某个有直接到达目的节点的节点。路由发现过程由建立反向路由和前向路由两部分组成，如图1所示。

图1 AODV路由发现过程

（2）路由维护

由于分布式星群网络卫星节点的移动性，网络拓扑结构时刻发生改变，因此路由要保持持续连通必须进行路由维护，其主要思想是通过节点周期性地发送Hello分组来实现。在每个周期开始时，每个节点都会构造一个生存时间（Time to Live，TTL）为1的RREP分组并对其所有邻居节点进行广播，收到广播分组的邻节点会对其回复Hello分组来确认彼此间的连通性。如果某个节点在过去收到过来自某节点的Hello分组，而在给定时间t后没有再次收到来自该节点的任何分组，则认为这2个节点间的链路已经断开，其上的路由信息视为无效，需进行路由修复。因此，本文提出的LW-AODV路由算法采取本地链路修复。

2.2 蚁群算法

尽管AODV路由协议已经被普遍使用，但是它仍然存在一些缺点，其中比较明显的缺点是：在建立路由时，邻居节点依次向周围节点广播此分组，导致分组包的数量激增，从而增加路径选择的管理开销。针对该问题，一些学者提出使用遗传算法、模拟退化算法、禁忌搜索算法、人工神经网络改进AODV协议的路由包，用于解决组合优化问题。但是这些算法需要设置系统输入参数，否则起不到改进AODV协议的结果。蚁群算法［13-14］是一种现代智能算法，通过蚂蚁释放的信息素浓度，以一定的概率选择最佳路径，并利用正反馈机制达到发现最优路径的目的，能够很好地解决AODV协议中广播路由包的缺点。

3 基于链路权重的分布式卫星群间路由算法

本文在AODV的RREQ和RREP报文的下一跳节点信息域中加入信息素值、链路权重值和概率选择表等参数，即将改进的基于链路权重的蚁群算法应用于AODV协议。本文算法基本思想是：每颗卫星都维护一张路由表，利用蚁群算法改进AODV协议后，此路由表被称为概率表。蚂蚁寻找食物的运动可以看作数据包的发送过程，则数据包寻路时会受到蚂蚁释放的信息素的影响，进而依据一定的概率有目标性地选择下一跳节点。每次进行路由查找过程时，源节点就会根据相关权重参数以及相关公式求得本节点到下一节点的信息素值，进而计算出选择下一节点的概率。在回复RREP时，设定初始目的节点信息素，并沿着反向路由进行扩散。本文算法在继承AODV算法路由建立和路由维护的基础上，利用蚁群算法优化下一跳选择。

3.1 算法基本规则

3.1.1 下一跳节点选择规则

式（1）规定了数据包K在节点i选择移动到下一跳节点j的概率：

其中，τij（t）表示节点i和节点j之间的信息素值；cij表示链路带宽；rij表示链路传输速率；lij表示链路丢包率；α，β和γ分别表示带宽、传输速率和丢包率对信息素影响的重要程度，取值为0～1；tabuK（K=1，2，…，m）为蚂蚁K的禁忌表，记录了蚂蚁K已走过的节点；allowedK=｛c-tabuK｝表示在t时刻蚂蚁K下一步允许选择的节点。

3.1.2 信息素更新规则

数据包的传输路径能够影响链路信息素的变化。若有数据包经过某链路，则释放信息素，使该链路信息素的值增加，否则该链路的信息素就会由于挥发而减少。信息素更新公式具体如下：

其中，ρ（0≤ρ≤1）表示路径上信息素的挥发系数，（1-ρ）表示信息素的残留因子；τij（Δt）表示路径（i，j）上信息素的增量；为常量，表示蚂蚁走完所有城市所释放的信息素总量，dij为路径（i，j）的长度。

3.1.3 链路权重定义规则

本文在蚁群算法的基础上考虑每一跳的权重，选择权重较小的路径，则能优化路由选择。相对于地面网络，卫星网络拓扑结构具有易变性，链路连接的时间是路由建立过程中必须考虑的因素；相对于群内卫星网络，群间卫星距离长，造成通信时延大，因此时延也是群间路由中必须考虑的问题。鉴于此，本文使用链路连接时间和时延2种参数来定义链路权重。节点Phert到邻居节点Phert之间链路的权重wij定义如下：

其中，D（i，j）表示链路（i，j）上的时延；L（i，j）表示链路（i，j）的连接时间；α1和β1分别表示时延和连接时间的相对重要性，可以根据对带宽和时延的具体要求进行调节。链路连接时间采用GPS运动方程，如式（6）所示：

其中，a=νicosθi-νjcosθj；b=χi-χj；c=νisinθiνjsinθj；d=yi-yj；νi和νj分别为节点i和j的平均移动速度；θi和θj分别为节点i和j的节点移动方向；（χi，yi）和（χj，yj）分别为节点i和j的坐标。

3.2 改进的蚁群算法

蚁群算法是根据路径上信息素的大小来做出路由决策，所以，将链路状态作为影响信息素增量的因素，即根据链路拥塞情况来增大或减小信息素增量。在算法开始时，设定一个适合的链路权重阈值w0，当所经过的链路权重小于该阈值时，信息素更新时就加上该链路的权重，否则就减去该链路权重。这样权重较小的链路更新时增加的信息素就较大，从而被后续蚂蚁选中的可能性就越大。根据链路权重更新信息素的规则，如式（7）所示：

当蚂蚁经过链路Phert后 ，该路径上的信息素按照式（3）、式（4）、式（7）进行更新，这样后来的蚂蚁就会受信息素的影响，选择链路权重较小的链路，更好地避开拥塞链路。

当网络初始化时，传统蚁群算法认为此时节点路由表为空，这将增加路由建立时间。但是卫星网络拓扑存在规则性和周期性特点，所以，卫星节点在开始时可以按照式（8）初始化路由表，则路由建立时间将会大大降低。

其中，HoPij是对于目的节点选择节点j作为下一跳节点的最短跳数。

3.3 分布式卫星群间路由算法步骤

分布式卫星群间网络通过群内主星进行通信，若距离较远，则通过中转卫星进行通信。本文假设每个卫星群主星节点都有与之相连的ILS（Intel Satellites Link）传播时延和连接时间等信息，同时假设发送数据的卫星群和接收数据的卫星群都已确定。当某个卫星节点收到链接请求时，首先检查自己的路由表是否有有效路由存在，若存在则利用此路由通信，否则该节点就成为路由进程的源节点，开始建立路由。该算法中Phert表示概率表，tabu表保存蚂蚁已经访问过的节点，以避免路由环的产生。该算法具体步骤如下：

（1）网络节点初始化：当时间t=0时，设置算法中相应的参数。按照分布式星群网络节点跳数的分配情况，根据式（8）初始化概率表，根据式（1）计算信息素表Phert，在源卫星节点s放置L只蚂蚁，并为每只蚂蚁设置一个空的禁忌表tabu。

（2）把源卫星节点s放入tabu中，蚂蚁从信息素表Phert中，选出概率最大卫星节点j，并将其选为下一跳节点。

（3）假设此时蚂蚁在节点i，当节点i为目的节点d时，则沿着蚂蚁来时的路径，向源节点发送一只反向蚂蚁，同时根据式（3）、式（4）、式（7）更新链路信息素的值。选择路径P（s，d），将该路径上所有节点放入tabu表中。更新Phert表，供下一次路径查找使用，本轮算法结束。如果i不是目的节点d，根据表移动到下一个节点j。

（4）如果j∈tabu，则蚂蚁返回节点i，重复步骤（3）。

（5）对于节点j，重复上述在节点i的步骤（3）、步骤（4）。

（6）在路由建立后，为维护路由，此算法利用Hello消息报文进行路由维护。

3.4 算法时间复杂度分析

假设有m只蚂蚁，则有m个路径表，初始化时间复杂度为O（m）。m只蚂蚁全部完成Nc次遍历是一个3层嵌套循环过程：最外层是遍历次数Nc，次外层是蚂蚁数量m，最内层是每只蚂蚁遍历的n个节点。最内层循环在每一步选择下一个节点时会计算概率和比较路径表中的节点，有一层复杂度为O（n）级别的嵌套，因此最终所有蚂蚁完成Nc次遍历的时间复杂度为O（Nc·m·n2）。而一般卫星网络的规模都较小，即节点较少，所以此时间复杂度在卫星网络是可以接受的。

4 实验仿真与性能分析

本文利用已在STK（Satellite Tool K it）中搭建好的仿真星座数据，在NS2中构建分布式星群网络仿真模型，分析改进的路由算法应用到分布式卫星网络的有效性和可行性。

4.1 仿真场景

本文仿真场景采取3个星群进行通信，卫星本身的处理速率为1 000 packet/s，卫星间链路带宽为10 M b/s，上行链路和下行链路带宽为9 M b/s，卫星天线的半功率角为1.179 4 rad。此场景采用2个GEO卫星群和一个LEO卫星群组成的3层星群模型结构。所有卫星（包括主星）用Lij标识，其中，i表示卫星所处星群编号；j表示卫星在星群内的序号。GEO卫星群和LEO卫星群各自与相邻节点建立ISL链路，群间通过各自星群内的主星建立群间链路。星群1向星群3发送数据和语音业务，等效拓扑结构如图2所示。

图2 三星群通信的等效拓扑结构

4.2 仿真结果分析

在模拟过程中，评价本文算法、LAOR算法以及AODV算法的性能，主要通过实验仿真网络的吞吐量、平均端到端时延和平均丢包率这3个指标来衡量算法性能，这3个指标是路由算法性能评价的重要指标。

图3是3种算法的平均端到端时延变化情况。当发送速率低于600 Kb/s时，网络处于低负载，AODV有较大优势，但随着发送速率的增强，网络业务量明显增加，本文算法和LAOR算法的平均端到端时延优于AODV算法。相比之下，本文算法选择权重较小，即繁忙程度低的路径，因此平均端到端时延较小。

图3 不同发送速率下的平均端到端时延

图4 是3种算法平均丢包率的变化情况。由此可知，当发送速率较低时，网络处于低负载，3种算法的丢包率基本为0。但随着发送速率的增加，网络节点开始出现拥塞，丢包率开始增加。当数据速率超过400 Kb/s时，AODV算法的丢包率迅速增加。然而，本文算法和LAOR算法的丢包率较小，因为本文算法在路由建立时，通过避开高负载的路径，降低了拥塞概率。图5是3种算法的网络吞吐量变化情况。

图4 不同发送速率下的平均丢包率

图5 不同发送速率下的网络吞吐量

当数据发送速率低于600 Kb/s时，3种算法并无明显区别。随着发送速率的提高，网络业务量不断增强，尤其当数据发送速率高于800 Kb/s时，本文算法吞吐量有明显改善，这是因为本文算法丢包率低，加大了网络吞吐量。综上分析可知，本文算法更适合于高负载的动态分布式卫星网络群间路由的建立。

5 结束语

本文针对分布式卫星群间网络提出一种改进的路由算法，采用改进的蚁群算法优化AODV协议的路由表，达到优化分布式卫星群间网络路由选择的目的。当链路连接不稳定与传输时延较长时，根据改进的蚁群算法的信息素更新策略，降低蚂蚁选择该路径的概率，避开网络中的拥塞路径并且均衡网络负载，进而减少链路时延和丢包率，增加网络吞吐量。下一步将对算法中信息素变化的计算以及信息素表的更新做进一步研究。

［1］ 潘成胜.空间信息网络的若干关键技术［J］.中国计算机学会通信，2013，9（4）：46-51.

［2］ 杨 力，杨校春，潘成胜.一种GEO/LEO双层卫星网络路由算法及仿真研究［J］.宇航学报，2012，33（10）：1444-1452.

［3］ Song Guanghua，Chao Mengyuan，Yang Bowei.A Trafficlight-based Intelligent Routing Strategy for NGEO Satellite IPNetworks［J］.Wireless Communications，2014，13（6）：37-46.

［4］ 肖 甫，孙力娟，叶晓国，等.面向卫星网络的流量工程路由算法［J］.通信学报，2011，32（5）：104-111.

［5］ 李洪鑫，张传富，苏锦海.基于OPNET的卫星网络路由协议仿真［J］.计算机工程，2011，37（11）：120-122.

［6］ Lu Yong，Zhao Youjian，Sun Fuchun.dynamic Faulttolerant Routing Based on FSA for LEO Satellite Networks［J］.IEEE Transactions on Computers，2013，62（10）：1945-1958.

［7］ Korcak O，A lagoz F，Jamalipour A.Priority-based Adaptive Shortest Path Routing for IP Over Satellite Networks［J］.International Journal of Communication System s，2007，20（3）：313-333.

［8］ 陈建州，王 路，刘立祥，等.双层星座中负载均衡路由协议研究［J］.宇航学报，2012，33（6）：743-753.

［9］ Papapetrou E，Karapantazis S，Pavlidou F N.Distributed On-demand Routing for LEO Satellite System s［J］. Computer Networks，2007，51（15）：4356-4376.

［10］ 薛 强，吕光宏.AODV的本地修复改进机制［J］.计算机工程，2008，34（19）：121-122，126.

［11］ 周少琼，徐 袆，蒋 丽，等.蚁群优化算法在Ad Hoc网络路由中的应用［J］.计算机应用，2011，31（2）：332-334.

［12］ 王 鹏，郭达伟.一种基于监听邻居信息的AODV本地修复算法［J］.科学技术与工程，2012，12（2）：313-316.

［13］ Wang Houtian，Zhang Qi，Xin Xiangjun，et al.Cross-layer Design and Ant-colony Optim ization Based Routing Algorithm for Low Earth Orbit Satellite Networks［J］.China Communications，2013，10（10）：37-46.

［14］ Jiang Wenjuan，Zong Peng.Multi-class Traffic QoS Routing For LEO Satellite Network［J］.Transactions of Nanjing University of Aeronautics&Astronautics，2012，29（3）：254-262.

编辑 陆燕菲

Routing Algorithm of Distributed Constellation Network Based on Link W eight

LIU Zhiguoa，b，ZHANG Zijinga，b，LIQinfenga，b
（a.College of Information Engineering；b.Liaoning Key Laboratory of Communication Networks and Information Processing，Dalian University，Dalian 116622，China）

Aim ing at the problems of long transmission delay and instable link-connection in distributed satellite intergroup network，this paper proposes an improved Ad Hoc On-demand Distance Vector（AODV）routing algorithm based on link weight.It defines the link weight by using link delay and connection time，adjusts the size of pheromone by using ant colony algorithm and chooses the light weight in the transmission process to avoid congestion and trade-off network load.It uses the improved ant algorithm to optimize routing table of AODV protocol to achieve the purpose of optimizing distributed satellite network routing selection.Simulation results show that this algorithm can choose low load path in the routing selection when the data package transmission rate is over 600 Kb/s.Compared with the position auxiliary routing algorithm and AODV algorithm，it can shorten the end-to-end delay，reduce the package loss and improve the throughout.

distributed satellite network；routing algorithm；ant colony algorithm；link weight；Ad Hoc On-demand Distance Vector（AODV）protocol

刘治国，张自敬，李秦锋.基于链路权重的分布式星群网络路由算法［J］.计算机工程，2015，41（9）：145-149.

英文引用格式：Liu Zhiguo，Zhang Zijing，Li Qinfeng.Routing Algorithm of Distributed Constellation Network Based on Link W eight［J］.Computer Engineering，2015，41（9）：145-149.

1000-3428（2015）09-0145-05

A

TP393

10.3969/j.issn.1000-3428.2015.09.026

国家自然科学基金资助项目（91338104）；国家“863”计划基金资助项目；大连市杰出青年人才计划基金资助项目（2014J 11JH135）。

刘治国（1974-），男，教授，主研方向：空间信息网络与通信；张自敬、李秦锋，硕士研究生。

2014-08-18

2014-10-26 E-m ail：liuzhiguo863@163.com