LEO/MEO卫星网络改进的动态路由协议的实现与测试

高明亮，孟祥斌，陈 鑫

(1.沈阳工程学院 自动控制工程系，辽宁 沈阳 110136；2.大庆师范学院 物理与电气信息工程学院，黑龙江 大庆163712)

0 引言

近年来，随着通信技术的发展，低地球轨道(LEO，Low Earth Orbit)和中地球轨道(MEO，Medium Earth Orbit)卫星网络作为第三代移动通信系统的重要组成部分，正受到越来越多的科研人员的关注。其中路由技术作为LEO/MEO卫星组网技术的核心，成为研究热点[1]。

由于LEO/MEO卫星网中卫星运行的周期性和可预知性，在其路由技术中，前些年国内外研究人员提到比较多的是离线路由算法[2-4]。但是离线路由算法抗毁性很差，针对这个缺点，文献[1]中提出了一种面向于卫星网络的动态路由协议，该协议运用了静态的路由配制与动态的路由调整相结合的思想。但是此动态路由协议中，存在以下两个缺点[5]：

1)非最优路由问题：此协议采用分级的路由结构，在簇内采用链路反转算法。反转时链路不加区分进行反转，导致部分到目的节点的路由非最优。

2)路由振荡问题：当面向目的节点的所有链路都发生故障时，簇内部分节点间会不停的转发链路反转信息，反转次数超过门限值时，才认为目的节点不可达，造成路由的震荡，降低了网络的收敛速率。

由此文献[5]提出了簇内有向树抗毁路由算法，对文献[1]的动态路由协议进行了改进。本文在有线网络搭建空间网络仿真平台，在此平台上实现改进的动态路由协议，最后进行仿真测试。

1 改进的动态路由协议的描述

这里将卫星网络拓扑的变化的周期离散化为若干个离散的时间片，动态路由协议中路由建立和维护都是针对某一个时间片来说的，当时间片切换时，重新初始化路由。文献[5]提出的改进的动态路由协议是对簇内路由进行改进。而协议中还包括动态成簇，簇间路由等算法，这些算法与原动态路由协议相同，所以本部分主要对簇内有向树抗毁算法进行描述。

基于上面原动态路由协议中簇内链路反转算法缺点的分析，改进后的簇内路由维护对链路反转算法进行了两点修改[5]：

1)基于有向树结构，把目的节点作为有向树的根节点，以下再分为子树。

2)对链路进行分类，分为主干链路和后备链路，后备链路又分为树内和树间后备链路。

1.1概念介绍

在簇内，通过离线的方式静态配置路由，把卫星网络配置成有向树结构，把目的节点作为有向树的根节点，其他节点都有唯一指向自己父节点的链路，从而保证每个节点都具有到目的节点的有向路径。基于以上过程所建立的树称之为面向目的节点的有向树(destination oriented directed tree)，记作DODT；反之，如果树内节点没有到目的节点的有效下行链路,称为非面向目的节点的有向树(destination disoriented directed tree)记作DDDT[5]。

1.2 有向树抗毁路由算法原理[5]

根据文献[1]提到的初始化路由综合考虑的因素，为每一个卫星的节点初始化到目的节点的主干链路，后备链路以及后备链路属性(树内或树间)，并且标识每个节点分属于的子树。以图1卫星网络拓扑为例，以1节点为目的节点，路由初始化为DODT，如图2所示。

图1 卫星网络拓扑 图2 路由初始化

1.2.1 后备路径故障

当后备链路发生故障时，直接从节点的后备链路列表中删除该后备链路，无需通告其它节点，也不需要任何网络开销。

1.2.2 根路径故障

如果上图1中树的根节点1和子节点2之间的链路发生故障，节点2以及以节点2为根节点的子树失去了到节点1的下行链路，由DODT蜕变为DDDT，这时启动有向树抗毁路由算法。因为根路径发生故障，首先查询本地是否存在树间后备链路。这里节点2发现本地存在树间后备链路，则把此链路添加到路由表，作为目的节点下一跳。此外还要通知5节点此链路不再是树间后备链路，同时通知所有上行节点子树属性发生变化。

1.2.3 目的节点不可达

节点1、2间断路并重新建立新路由后，如果节点1和4之间断路，此时由于本地无树间后备链路，则节点4发送高优先级查询报文，询问上行节点是否有树间后备链路，由于根节点1只有一棵子树，因此直到叶子节点6和10都没有发现树间后备链路，然后，叶子节点返回查询失败报文。节点4收到此报文后，检查收到的失败报文个数是否等于发送的查询报文数，当相等时表明目的节点不可达，通知本子树的所有节点删除自己到目的节点的路由。

1.2.4 子树路径故障

当节点4和7间断路时，节点7没有到达节点1的路由，所以启动有向树抗毁算法。首先节点7无后备链路，需要向上行节点查询后备链路，由于是非根路径故障，因此发送低优先级路由查询报文，询问上行节点是否有后备链路。节点8存在后备链路，则应答路由请求。节点7接到应答报文后，发送确认报文，更新路由。

2 空间网络仿真平台介绍

文献[5]中，对此动态路由协议进行仿真都是基于NS2模拟平台。因为NS2是基于算法和协议正确性方面的模拟[6]，对于协议在实施阶段的测试和验证却是无能为力。所以在本文中提出有线局域网上搭建空间网络仿真平台，在Linux操作系统上实现了此协议，在真实的网络环境中仿真空间网络特性对协议进行测试。总体说本文提出的空间网络仿真平台解决了测试空间网络路由协议在实施阶段遇到的问题，它对路由协议实现阶段进行了仿真。

空间网络仿真平台采用分布式运行、集中式管理的思想，在各分布式终端节点运行真正的路由协议，而在中心控制端通过虚拟移动和虚拟拓扑管理控制多个终端节点来仿真复杂的网络拓扑。对于终端节点通过网络行为的过滤实现强制两个直接通信的终端必须经过路由协议选路，这是此仿真平台中共享单跳网络模拟成多跳的拓扑结构的基本原理。该仿真平台网络结构中用一台计算机作为中心控制端，而其它计算机作为分布式终端节点。

3 改进的动态路由协议主要功能模块的实现

空间网络仿真平台是在Linux系统上设计完成的，此动态路由协议在这个仿真平台的测试就首先要把该协议在Linux系统上用程序实现，然后与空间网络仿真平台的程序对接，当启动这个仿真平台时就可以安装编写好的路由协议进行测试。协议的程序设计中主要是采用在Linux系统的用户空间编写协议的功能模块，这样路由协议就工作在用户空间。通过Linux socket编程把协议的功能模块所产生的路由信息传到内核空间，可以实现用户空间与内核空间的信息交换。簇内有向树抗毁路由算法是本协议的核心，本文协议实现部分主要讲述有向树抗毁路由算法的实现。对于此算法主要分断路处理和接收报文处理两方面实现。

3.1 断路处理的实现

当链路断路时，首先调用linkStateChanged()函数，判断断路的链路是簇间还是簇内。如果簇间链路断路，则进行簇间路由重建，如果簇内链路断路就启动簇内有向树抗毁路由算法，此时断路节点调用link_tree(string nbrid)函数来处理，其中参数nbrid代表发生链路断路的邻居节点。

1) 首先遍历所有到目的节点的DODT，并调出到目的节点的上行、下行节点链表和后备链路链表。关键代码截取：

for(LsDodtMap::iterator iter=LsRouting::dodt.begin();;iter!=LsRouting::dodt.end();iter++)

{pathlist*downpath=&(iter->second.downstream);

pathlist *uppath=&(iter->second.upstream);

pathlist *backuppath= &(iter->second.backupstream);}

2)判断nbrid所代表的节点在哪一链表中，若在上行节点链表或后备链路链表中，直接删除。从上行节点链表删除关键代码截取：

for(pathlist::iterator iterup=uppath->begin();iterup!=uppath->end(); iterup++)

{ if(iterup->nextHop==nbrid){ iterup=uppath->erase(iterup); break;}}

若在下行节点链表中，直接将此节点删除，再根据nbrid是否为根节点，向上行节点发送高、低优先级路由查询报文。发送时调用编写的sendRHRev()和sendRLRev()函数。

3.2接收处理的实现

这里包括接收高优先级路由查询报文、低优先级路由查询报文和应答报文等的处理。

3.2.1查询报文的处理算法

这里以低优先级路由查询报文为例，如果接收到低优先级路由查询报文则由编写的bool RecvRLRev(string ipDest，string ipNeighbor)函数来处理。参数说明：ipDest为目的节点的ip地址，也是map结构中的存储关键字；ipNeighbor为发消息的相邻节点的ip地址。

接收到此报文的节点主要判断是否有后备链路.如果有后备链路则发送应答报文，否则检查是否有上行链路，如果有则转发低优先级路由查询报文，如果没有则发送路由失败报文。这里调用所编写的sendARev()函数发送应答报文。

3.2.2 应答报文的处理算法

首先检查是否发给本节点的应答报文。不是发给本节点的则调用sendARev()函数来转发。如果本节点是应答报文的目的节点，停止接收新应答报文，向此路径发送更新路由消息，更新路由。

4 仿真与分析

本文借助有线网络搭建空间网络仿真平台，仿真空间网络特性对协议进行测试，在仿真中利用了16台计算机，其中1台作为控制中心，15台作为仿真节点(终端节点)。

4.1 仿真模型协议性能评估参数

这里采用拓扑结构如图3所示。因为卫星运行周期中某一时间片内，卫星网络拓扑结构是不变的，所以仿真时设置各节点是相对静止的。在这里把15个节点分为3个簇，第一个簇由1到9号节点组成，设5号节点为此簇的簇首，第二个簇由10到12号节点组成，设10号节点是此簇的簇首，第三个簇是由13到15号节点组成， 13号节点是此簇的簇首。

在性能评价中选择了以下2个参数：1)信令开销：网络中传输控制包数目；2)网络平均吞吐率：目的节点收到的数据包与源节点发出数据包的比率。

4.2 仿真结果分析

4.2.1 簇内一条链路断路的情况

设置簇内每个节点都向节点1发送数据包，各节点发送速率相同，仿真时间为100s。这里把第一簇内节点1与2之间设置成断路，此时调用簇内有向树抗毁路由算法调整簇内路由。各终端节点显示所有经过节点2发往节点1的路由都调整成再经过节点5、4到达节点1，例如节点3发包，在原动态路由协议中簇内采用链路反转算法，经过节点6、9、8、7、4才能到达节点1，而在改进动态路由协议中簇内用有向树算法，数据包只经过节点2、5、4就能到达节点1，显示出优化的路由。

图3 链路无故障时拓扑情况

1)信令开销，信令开销性能如图所示，此图是发送速率为2Kbyte/s时测得的各节点的信令开销，横坐标为节点号，纵坐标为控制包的个数。

图4 簇内一条链路断路时的信令开销

由图4，可以看出原动态路由协议和改进的动态路由协议都采用分层的网络结构，主要的信令开销集中在簇首，所以网络平均信令开销很小。对于链路反转算法在本地直接进行链路反转。而有向树算法需要进行路由查询、应答和确认，所以信令开销方面改进的动态路由协议要比原动态路由协议稍微大一些。同时某一簇内链路出现故障，不会影响到其它簇路由，所以其它簇节点的信令开销没变化。

2)吞吐率，吞吐率性能如图5所示，横坐标代表发包的速率，分别为2Kbyte/s、4Kbyte/s、6Kbyte/s、8Kbyte/s、10Kbyte/s，纵坐标代表网络平均吞吐率。

图5 一条链路断路情况的网络平均吞吐率性能曲线

图5中可以看到原动态路由协议的吞吐率要比改进的动态路由协议的吞吐率低。在发生断路情况下簇内链路反转算法重建的路径并非全局最优，造成吞吐率的下降。而有向树抗毁路由算法能快速的查询到后备链路，更新路由，保证了指向根节点的路由的最优性。所以说改进的动态路由协议在吞吐率上相比于原动态路由协议有了很大的提高。

4.2.2 簇内目的节点不可达

设置每个节点发送速率都为2Kbyte/s，簇内节点都向节点1发送数据包，仿真时间为100s。这里把与节点1相连的所有链路全都设置成断路，此时簇内没有可用路径到达节点1，图6为此时信令开销的性能。

由图6可以看到原动态路由协议的信令开销有明显的增加，要明显高于改进的动态路由协议。因为这种情况采用簇内链路反转算法会发生路由震荡，不停发送链路反转报文，当发到一定次数时才停止。对于有向树抗毁路由算法只是发送查询和路由失败报文，而且此算法把信令开销限制在发生故障的节点的子树范围内，所以此时改进的动态路由协议避免了路由震荡，降低了网络的信令开销。

对于簇间路由，改进的动态路由协议和原动态路由协议原理一样，所以只有簇间链路短路时两者的信令开销和吞吐率才达到基本一样。

图6 目的节点不可达时的信令开销

5 总结

本文首先讲述了文献[5]所提出的一种面向于卫星网络的改进动态路由协议。文献[5]中只用NS2对此协议进行模拟，由于NS2模拟器采用单机模拟方式工作，这与真实网络环境存在较大差距，所以本文提出了将动态路由协议在Linux系统上实现，并在有线局域网上搭建的空间网络仿真平台对协议进行测试，进一步验证了协议的性能。经过测试得出了簇内路由重建时原动态路由协议的信令开销要比改进的动态路由协议略小。但当面向目的节点不可达时，改进的动态路由协议避免了路由震荡，节省了信令开销。同时改进的动态路由协议路由重建的路径是比较优化的，所以其网络平均吞吐率明显高于原动态路由协议。改进的动态路由协议同样采用分层网络结构，主要的信令开销都集中在簇首节点，这样可以节省信令开销。

[参考文献]

[1] 李喆，李冬妮，王光兴. LEO/MEO卫星网络中运用自组网思想的动态路由算法[J].通信学报，2005，26(5):50-56.

[2] Markus Werner, Cecilia Delucchi, Hans-Jorg Vogel. ATM-based routing in LEO/MEO satellite net- works with intersattelite links[J]. IEEE Journal on Selected Areas in Commu- nications, 1997, 15 (1) : 69-82.

[3] Vidyashankar V Gounder, Ravi Prakash, Hosame Abu-Amara.Routing in LEO-based satellite networks [C ]. Proc of IEEE Emerging Technologies Symp. Wireless Communicati- ons and Systems, Apr, 1999.

[4] Chang H S, Kim B H, Lee C G,et al. Topological design and routing fo r low-earth orbit satellite networks[C]. Proc. of IEEE GLOBE-COM , 1995：529-535.

[5] 赵运弢.LEO/MEO卫星网络的有向树抗毁路由算法的研究与仿真[D].沈阳：东北大学硕士学位论文,2006.

[6] 徐雷鸣，庞博，赵耀. NS与网络仿真[M].北京:人民邮电出版社,2003.