一种新的战术网络路由与组网方法

张传金， 王剑锋， 姜永广

0 引言

战术网络既不同于传统有线网络，也与纯粹的 Ad Hoc网络[1-2]不同。战术网络可能既包含了有线IP网络的成份，又含有无线 Ad Hoc网络的组成部分。战术网络还可能具有卫星链路与数据链链路。战术网络的无线网络成分较多，其带宽资源十分宝贵，设计战术网络的路由协议时，必须尽量减少路由协议自身的传输开销。

我们将战术网络看成为广义的Ad Hoc网络，则不宜采用反应式(按需)路由协议。因为大多数按需路由是基于查询/响应的方法，并且采用了泛洪机制来散播查询分组与维持路由，当网络业务负荷和移动性增大时，按需路由往往效率很低。此外，反应式路由协议无法保证各类信息业务的服务质量(QoS)要求，特别是不能满足时延要求。因此，在战术网络中应采用先应式路由协议。路由算法大致可以分为距离矢量与链路状态两类。传统的距离矢量的优势，是协议与算法简单、信息量比较小而且计算效率高，可是由于无序号控制机制，使其具有收敛慢和产生路由环的致命弱点，不适合于高移动性的战术网络。而链路状态路由虽然具有收敛快且无环路的优点，但由于其报文格式长、路由信息量较大，使其扩充性受到很大的影响，不适合于战术网络。

由于战术网络内的节点比较多，网络规模较大，即使采用分层的路由设计方法[3]，每一层网络内也可能达到数十甚至上百个以上的节点，路由协议自身的控制开销不容忽视。因此，战术网络的路由协议必须具有可扩充性，能够适应组建大规模网络的需要。

战术网络的路由协议，必须满足战场环境战术节点的随遇接入、任意互连、快速开通、快速部署、网络能快速重组以及能及时反应拓扑变化等需求。战术网络中连接的局域网较多，每个节点都可能至少连接了一个附属的本地IP子网。若采用传统的 IP子网路由交换方法，则路由协议控制开销将非常大；若采用广义Ad Hoc以及ID与IP子网映射的方法，节点之间只交换 ID，既不交换互连子网的 IP，也不交换每个节点的附属 IP子网的信息，则可以大大压缩路由协议的控制开销。

战术网络需要一种先应式的、路由信息量小的、无路由环路的、可扩充的路由协议。在这篇文章中，我们提出一种基于多点中继、模糊视野泛洪机制以及目的地序号控制的距离矢量路由方法，并采取了高效率的消息压缩机制，该路由方法能满足战术网络的要求。

1 广义Ad Hoc网络设计

在每个战术网络节点中，除了本地连接的局域网外，将其它所有用于节点间互联的无线接口与有线接口当成为一个广义的Ad Hoc网络接口。组成广义Ad Hoc网络接口的各个物理接口，无论是有线还是无线接口，都不需要分配 IP子网地址。广义Ad Hoc网络接口也不需要分配IP地址。在广义Ad Hoc网络中，每个节点只有一个ID地址。

广义Ad Hoc网络中的每一条有线链路，相当于无线网络中在特定方向上的一条无线链路。在广义Ad Hoc网络中，节点ID与其本地IP子网之间为一种固定的静态映射关系。无论网络拓扑如何变化，无论网络如何重组，这种映射关系始终保持不变。采用这种设计，战术网络内的各个节点之间，将不再需要交换关于 IP子网的路由信息，只需要交换关于节点ID的路由信息。只要建立了节点ID路由，通过IP子网路由与节点ID路由之间的映射，就能实现IP子网之间的路由。这种方法是从网络规划设计出发，进行减少网络内路由信息总量的宏观控制。

广义Ad Hoc网络的设计思想，能够满足战术网络快速开通、快速部署以及压缩路由消息的长度的需求。此外，还便于采用适用于无线网络的 Ad Hoc路由协议，适应战术网络的任意拓扑结构应用。

2 基于多点中继与模糊视野路由的距离矢量路由方法

在路由信息量的微观控制上，我们联合采用多种方法来减少战术网络中交换的路由信息总量。

基于多点中继与模糊视野路由的距离矢量路由方法(HSMPR)包含五个有机组成部分，即 Hello协议、目的地序号控制(DSDV)距离矢量路由方法、多点中继(MPR)算法、模糊视野(HS)路由控制方法以及路由消息内容信息聚类压缩，下面分别进行叙述。

2.1 Hello协议

Hello协议用于建立和维护各节点之间的1-跳与2-跳邻居的连通信息。节点周期性地发送Hello分组，通告自己的存在与存活。同时每个 Hello分组中携带了发送节点的Hello间隔、发送节点的1-跳邻居节点ID表、链路方向表以及链路MPR状态表。

1-跳邻居节点ID表描述了发送节点通告的所有1-跳链路邻居的ID。

链路方向表描述了 1-跳邻居表包含的各个链路的方向(对称或非对称)。

链路MPR状态表中包含了发送节点的MPR选择信息(MPR节点或MPR选择节点)。

接收节点通过 Hello报文建立和维持与发送节点之间的邻居连通信息，通过Hello报文中携带的1-跳邻居节点地址表进行 2-跳邻域内的连通状态的判断，并建立自己的 2-跳邻居表。

接收节点可以根据邻居节点 Hello间隔来确定邻居链路的超时值。

Hello分组携带了发送节点的MPR挑选信息，邻居节点接收到Hello分组后，可以确定自己是否为该Hello分组发送节点的MPR节点。若为其MPR节点，则应对该Hello分组的发送节点承担多点中继的责任，即必须泛洪转发从MPR挑选节点接收到的拓扑更新消息。

Hello分组还携带了发送节点与其所有 1-跳邻居节点之间的链路方向属性(单向链路或对称链路标志)。每个节点在Hello协议的基础上，完成单向与双向对称链路的识别，建立1-跳(包括单向的和对称的)邻居表与2-跳对称邻居表，进而执行MPR挑选算法。

Hello分组的发送周期可以通过配置来进行设置，但应该比拓扑控制的更新周期短，最好不要超过拓扑控制更新周期的一半，确保在一个拓扑控制更新周期内能够发现对称的1-跳邻居。HSMPR路由协议启动初期，采取较短的Hello发送周期，这样可以快速建立(1-跳和2-跳)邻居关系并尽快完成MPR节点的挑选；在节点运行稳定之后，以较大的Hello间隔周期发送，减少网络负载。在节点运行稳定后，若节点发现了新邻居，会触发Hello报文的立即发送，无论Hello间隔是否到期。

Hello协议为MPR路由算法的基础。

2.2 DSDV路由算法

目的地序号的距离矢量(DSDV)[4]协议来源于对传统的Bellman-Ford路由(DBF)方法的改进，其特点是利用目的节点序列号解决了 DBF算法的路由环路和无穷计数问题。在DSDV中，每个节点保存一张路由表，路由表维护本节点到网络内部所有可达的目的节点的路由。路由条目中保存目的节点的序列号，用以区别新旧路由。为维护路由表，节点周期性地广播路由更新分组。收到路由更新分组后，节点比较其中的目的节点序列号和自己保存的同一目的节点的序列号，如果前者大，就更新自己的路由；如果路由序列相同，则选择具有较少跳数的路由。路由更新分组要延迟一段时间发送，以防止路由表的波动。

DSDV协议的主要优点是消除了路由环路，加快了收敛速度，同时减少了控制信息的开销。但是它的不足在于它难以适应速度变化快的移动 Ad Hoc网络，不支持单向信道，并且为一种路由域内全局性的泛洪机制，存在一定程度的带宽资源浪费。

2.3 MPR路由算法

多点中继(MPR)算法，建立在Hello协议的基础之上，为优化链路状态路由协议(OLSR)的核心算法[5]，特别适合于密集型的Ad Hoc网络。经过增强性扩展[6]，也能够在稀疏型网络中使用。

每个节点与邻居节点通过Hello协议报文的交换，获得其 2-跳邻居信息。根据其 2-跳邻居信息，挑选出愿意为自己转发路由更新消息的多点中继节点。在一个路由域内挑选出的所有 MPR节点，构成一个连通控制子集(CDS)，由 CDS内的节点来完成该区域内的路由消息的(非重复)泛洪。该路由域内的所有节点要么在CDS内，要么为CDS内节点1-跳可到达的。CDS内的节点仅仅为该路由域内的少量节点。

下面叙述我们采用的增强型MPR(EMPR)算法，它既适用于密集型网络，又适用于稀疏型网络。

在一个MPR路由域中，每个节点由一个标识号(ID，可为4字节的IP)来标识。增强型 MPR(EMPR)挑选算法中将使用以下术语：

H1(v)：节点v的对称1-跳邻居(与v连接的对应接口地址)的集合。

H2(v)：节点v的严格对称的2-跳邻居的集合。

C(v)：节点v的MPR节点集合。

当为节点v确定转发节点(MPR)时，先清除所有对称1-跳链路的MPR状态，然后执行以下步骤的MPR挑选操作：

① 对于H1(v)中的每个节点u，如果u的ID小于其所有1-跳对称邻居，且u具有两个未相互连通的对称1-跳邻居(包括进行MPR计算的本节点)，则将u添加到C(v)中(将该1-跳对称链路标记为MPR);

② 对于 H1(v)中的每个节点 u，如果 v不是 u的最小ID(1-跳)邻居，则将u添加到C(v)中；

③ 对于H2(v)中的每个节点w，如果w只能通过H1(v)中的节点u覆盖，则将u添加到C(v)中；反复执行该步骤，直到不存在这样的H2(v)节点为止；

④ 如果H1(v)中的节点u覆盖的H2(v)中没有被C(v)覆盖(即没有被标记为 MPR的对称 1-跳邻居所覆盖)的未覆盖节点最多，则将u添加到C(v)中。当两个节点覆盖的未覆盖节点的数量相同时，则由节点ID来选择添加到C(v)中的那个节点。反复执行该步骤，直到H2(v)被H1(v)完全覆盖为止。

与DSDV路由泛洪算法相比，MPR算法将路由信息限制在 CDS集合的范围之内，进一步减小了路由域内交换的路由信息总量。

2.4 模糊视野路由算法

模糊视野(HS)路由方法可以与其它路由协议结合使用，该方法以控制路由消息泛洪范围的机制来压缩路由域内的路由信息总开销。由于这两种方法所解决的是不同的问题领域，它与其它路由机制一起运作可以创建一种联合的泛洪机制，使其产生的开销比单独使用任何一种路由方法都低[6]。

HS算法的每个拓扑控制消息项中包含了一个向下计数的跳数域TTL，用于拓扑控制消息项的泛洪范围控制。

HS算法在进行了一次全局性的路由更新(RMU)消息传递(即将TTL域设置为代表无穷大的值，RMU消息将在整个CDS内泛洪)之后，如果在过去的tes内发生了一次链路状态变化，则节点每隔tes被“唤醒”并发送一个RMU消息，其TTL值为s1。此外，如果在过去的2tes内发生了一次链路状态变化，则节点每隔2tes被“唤醒”并传递一个RMU消息，其 TTL 值为 s2。一般地说，如果在过去的 2i-1×tes(i=1，2，3，…)内发生了一次链路状态变化，则节点每隔 2i-1×tes被“唤醒”并传递一个RMU消息，其TTL值为si。选择s1=2将s1,s2,s3,s4,…替换为2,4,8,16,…,可以使一个加入网络的节点引起的总开销最小化。

在一个具有N个节点的网络中，HS算法产生RMU消息的过程，可由下面的公式来描述：

如果i恰好等于2的幂值，则将RMU消息的跳数界限域的值设置为i。如果i不等于2的幂值，但能被2的j次幂除尽，则将RMU消息的跳数界限域的值设置为j。

为了使该算法适用于低移动性网络，可以设置一个周期全局广播(全局泛洪)定时器tb,确保每隔tbs至少传递一个全局RMU消息。为了便于理解，下面以图例来说明HS产生RMU更新的过程。

图1 HS算法产生拓扑更新消息的过程

图1 展示了HS算法中RMU消息产生过程的一个例子，由于移动性高，其结果每隔tes都产生了一个RMU。例如，考虑在时刻4te的情形。该时刻为te(与s1关联)的倍数，并且也为2te(与s2关联)和4te(与s3关联)的倍数。需要注意，如果在过去的te或2tes内发生了一次链路状态变化，则意味着在过去的4tes内也发生了一次链路状态变化。因而，如果节点已经设置TTL域至少为s1(或s2)，也必须将其增大为s3。同样，如果在过去的4tes内没有发生过一次链路状态变化，那么在过去的te或2tes内也没有发生过一次链路状态变化。因此，如果节点没有发送过TTL值设置为s3的RMU，那么节点也就根本没有发送过RMU。所以，在时刻4te(同样在时刻12te、20te以及4kte的任何其它时刻，这里k为奇数)，需要核查过去的4tes内是否发生链路状态变化。如果有，则发送一个TTL值设置为s3的RMU。因而，假设在高移动性场景中，在时刻4te和12te，将发送一个TTL值等于s3的RMU。很明显，HS算法能够保证离参考节点 si跳远的那些节点，将在最多 2i-1te秒后获得该节点的链路状态的变化情况。

HS算法在MPR算法的基础之上，限制了某些路由消息的泛洪范围，进一步减少了路由域内交换的路由信息总量。

2.5 路由消息聚类压缩

在对各节点进行ID编址时，若能保持高2字节或3字节相同，则在原始路由更新报文发送之前，可以根据信息内容组成，将各个HSMPR路由更新消息项的ID部分分离出来，集中形成多个 ID的聚类数据块，然后对聚类数据块进行压缩[8]，得到压缩后的路由更新报文，再进行传输。接收到压缩的路由更新报文后，先进行解压缩操作，然后复原为原始的路由消息报文，再进行正常的路由消息处理。

路由消息聚类压缩可以大大压缩路由更新报文的长度，进一步减少路由域内交换的路由信息总量。

3 HSMPR路由方法性能仿真

为便于性能对比，采用OPNET12.0.A仿真工具软件，在分布在100 km×100 km区域上均匀分布32个数节点的平面Ad Hoc网络内，分别对OLSR和HSMPR两种路由协议进行仿真。

本次试验的主要目的是对不同规模大小的扁平网络中采用两种路由协议的性能比较。

仿真的扁平战术网络规模为32个节点的平面网络，信道带宽为2 Mb/s，有效通信距离为设置为只能与相邻节点通信的范围，仿真网络运行一小时，统计结果如下仿真场景如图2所示。

图2 HSMPR路由协议仿真场景

图3 为32个节点的平面网络中HSMPR与OLSR的路由开销对比情况。

其中上面的统计线代表采用OLSR路由协议的情况，网络的路由开销稳定在 24 kb/s左右；下面的统计线代表采用HSMPR路由协议的情况，网络的路由开销稳定在10 kb/s左右。

从仿真结果来看，HSMPR路由方法，由于充分发挥了两种多点中继、模糊视野、距离矢量算法各自的优点。在这种场景中，HSMPR路由与 OLSR路由的平均开销比为 10/24≈41.6%。对于战术网络，联合采用HS、MPR以及DSDV的路由方法，是一种非常好的选择。

图3 32节点平面网络中两种协议的开销

这种路由方法用于战术网络的缺点，是每个节点不能了解全局的拓扑信息，而在链路状态路由方法中，每个节点都具有全局的网络拓扑态势信息。

4 结语

这篇文章提出了适用于战术网络的广义Ad Hoc网络概念，并提出了采用节点 ID与本地子网的固定映射关系，来解决 IP子网之间的路由问题。在战术网络中，只需要解决节点ID之间的Ad Hoc路由，这种方法可以大大压缩交换的路由信息量。采用MPR与HS以及DSDV融合的路由方法，可使路由协议的控制开销大大地降低，并且大大增强了战术路由协议的可扩充性，这种路由方法可以应用于规模较大的战术网络中。下一步的工作是采用更加优化的MPR算法，进一步缩小CDS的大小，使这种路由方法更加优化。

[1] 郭中华,史浩山. Ad Hoc网络路由协议性能分析[J].通信技术,2008,41(11)：111-113.

[2] 谢晓川,韦岗,吴克平.用于Ad Hoc网络的多径混合路由[J].通信技术,2009,42(01)：225-227.

[3] Xu Kaixin, Hong Xiaoyan, Gerla M,et al. Landmark Routing in Large Wireless Battlefield Networks Using Uavs[J]. IEEE,2001(01)：230-234.

[4] Perkins C E, Bhagwat P. Highly Dynamic Destination-Sequenced Distance-Vector Routing (DSDV) for Mobile Computers[C].USA：ACM,1994：234-244.

[5] Clausen T, acquet P.The Optimized Link State Routing Protocol[S].France：[s.n.],2003.

[6] Jie Wu, Wei Lou. Extended Multipoint Relays to Determine Connected Dominating Sets in MANETs[C].USA：IEEE, 2005：556-560.

[7] Maker J P, Dean J W.A Study of Link State Flooding Optimizations for Scalable Wireless Networks[C]. USA：ACM, 2004：1-6.

[8] Clausen T,Dean J,Dearlove C,et al.Generalized MANET Packet/Message Format[EB/OL].(2009-03-01)[2009-03-20].http： //www.ietf.org/work in progress draft-ietf-manet-packetbb- 17.txt.