基于OLSR 的大规模组网路由*

贾 森，刘小娟，吴明曦

（武汉中原电子集团有限公司，湖北 武汉 430205）

0 引言

移动自组织网络（Mobile Ad hoc Networks，MANET）是一种由移动节点组成的自组织的无线网络，每个节点同时具有终端和路由器两者的功能[1]。不同于传统的蜂窝无线网络，MANET 不依赖基站，每个节点具有同等的地位，节点可以通过中间节点转发与多跳节点通信，因此它是一种多跳网络。MANET由于每个节点都具有终端和路由器的功能，对外部环境有更强的适应力，每个节点可以随意移动和自动组网，因此被广泛应用于军事通信、车车通信和无人机群通信等领域，具有很光明的发展前景。尤其在军用领域，野外环境复杂多变，MANET 无中心和自组织的特点非常适合陆、海、空作战使用。

美国国防部早在20 世纪70 年代初就开始研究移动分组网络，即MANET 的前身[2]。后美军MANET 技术迅速发展成熟，现在已经具有完整的技术体系[3]。我国在MANET 军用化方面起步较晚，现在还处于研究摸索阶段，尚未形成完整的体系。我国应重视网络技术，学习美军的长处，大力发展战术互联网[4]。在战场无线通信领域，网络中参与通信组网的节点一般最多30 多个，而随着我国无线通信技术以及网络技术的飞速发展，网络中组网节点的容量需求已经达到了100 多个节点的规模。但在大规模组网中，现有的一些网络路由协议并不完全适用，尤其是平面网络架构，该架构中的节点数量太大，会导致网络中路由开销过大，通信性能不佳，故针对大规模组网路由的研究十分必要。

本文内容安排为：第1 节介绍分簇网络架构，第2 节介绍簇内路由，第3 节介绍簇间路由，第4 节 进行仿真和分析，第5 节总结全文。

1 分簇网络架构

传统的平面网络架构如图1 所示，具有结构简单、网内节点地位平等、健壮性较好的优点。但随着网内节点数量的增加，网内路由开销会急剧增加，故平面网络架构只适用于小规模的MANET 网络，因此本文方案采取分簇网络架构来进行大规模组网[5]，如图2 所示。分簇是指将网络中节点划分为不同的虚拟群组集合这一过程。分簇网络架构中的节点类型有簇首节点、网关节点和成员节点3 种。可以看出，分簇网络架构的结构更复杂，网内开销更少，很适合大规模MANET 网络。

图1 平面网络架构

图2 分簇网络架构

簇首节点是分簇的管理者，负责管理分簇内部的成员节点，是网内的重要节点。簇首节点在不同的分簇路由算法中，起到的作用不完全相同。簇首节点可以统计分簇成员节点的信息和簇与簇之间的位置关系，并负责将簇内广播信息通知到分簇所有节点，还可以承担簇间寻址的职责。选举簇首及分簇常见的方法有最小ID分簇法、最高节点度分簇法、最低移动性分簇法、地理位置中心分簇法这几种[6]。最小ID 分簇法[7]为网络内每个节点都分配了一个独有的ID 号，然后选取ID 号最小的节点为簇首节点，其一跳邻居节点为该簇首节点的簇成员，然后继续选取剩下节点中ID 最小的节点，循环此选取过程。最高节点度分簇法[8]是将邻居节点最多的节点选为簇首节点。最低移动性分簇法[9]中，节点移动性越高，节点选为簇首的权重就越低，依次选择最低移动性的节点为簇首。地理位置中心分簇法[10]则是通过地理位置信息来选择簇首。这几种分簇方法各有优劣，可以基于不同组网方案具体选择其中一种来分簇。

网关节点负责邻簇之间的通信，发往邻簇的包须通过网关转发到邻簇的对应网关。可以通过簇间感知，根据收到信号的能量强度，把相邻两簇的综合信号能量强度最大的一对节点或几对节点选为网关。

2 簇内路由

路由协议的种类有先验式路由协议、反应式路由协议和这两种混合式路由协议。本路由方案采用一种改进的优化的链路状态路由（Optimized Link State Routing，OLSR）协议作为簇内路由。OLSR[11]是一种典型的先验式路由协议，RFC3626 中有详尽的描述。OLSR 会维护全网节点的拓扑结构，周期性更新全网拓扑结构，根据最短路径算法周期性计算本节点到网内其他节点的路由。OLSR 路由可以即时根据拓扑变化，快速地查询到路由，非常适合MANET 使用。

OLSR 的路由包主要有HELLO 和TC 两种。HELLO 包用来进行邻居发现，构建一跳两跳拓扑。TC 包经多跳转发，用来构建多跳拓扑。只有MPR节点才会产生TC 包，这样就减少了网络内TC 包的数量，大大减少了网络开销。节点在邻居节点中选出MPR，选择的标准是要保证通过MPR 节点集，可以到达节点的所有二跳节点。但标准MPR选举过程[12]选出的MPR 集有冗余，并不是最少集合，本方案用统一连通支配集（Unifying Connected Dominating Set，UCDS）算法[13]来选举MPR 集。UCDS 算法就是在寻找最少的连通支配集，本文方案MPR 选举过程如图3 所示。

图3 MPR 集合选举过程

其中的规则1 至规则4 具体如下文所述。

（1）规则1：

①如果节点i与其所有一跳邻居相比具有最高的支配因子（一跳邻居数量d），则节点i选择自己作为DS 集合成员。

②如果节点i的邻居节点j发现i在j的所有邻居节点中具有最高的支配因子，则节点j选择节点i作为DS 集合成员。

③如果节点i与N(j)中支配因子最高的节点k的支配因子相同，则比较节点ID，选择ID 号小的作为DS 集合成员。N(j)表示j的邻居节点集合。

（2）规则2：

①如果节点i的所有邻居节点都是直接连通的，则节点i不是CS 集合成员，为普通节点。

（3）规则3。对于DS 集合之外，且不满足规则2 的节点为：

①如果节点i不是DS 集合的成员，且i有邻居节点l和m，l和m中至少有一个属于DS集合的成员，如果节点l的Ds(N(l))与节点m的Ds(N(m))不相交，则i是CS 集合的候选成员。其中N(m)表示m的邻居节点集合，Ds(N(m))表示N(m)中归属于DS 集合的节点集合。

②如果l和m还有其他的满足上述条件的普通邻居节点i'，则比较所有i和i'的支配因子，支配因子最高的为CS 集合成员，支配因子相同时节点ID 小的选为CS 集合成员。

（4）规则4。对于DS 集合之外，不满足规则2，且满足规则3 的节点为：如果i的两个邻居节点j和k中，j不是DS 集合成员，k是DS 集合成员，而且节点i和节点j有同一个DS 邻居节点，则节点i不用执行规则3，将节点i重置为普通节点。

3 簇间路由

跨簇业务需要簇间路由，常见的簇间路由协议分为先验式和反应式两种。区域路由协议（Zone Routing Protocol，ZRP）[14]和基于分簇路由协议（Cluster Based Routing Protocol，CBRP）[15]簇间都采用反应式的路由方式，需要簇间路由时，才去寻找簇间路径，所以延迟比较大，簇间业务时延高。簇首网关交换路由协议（Cluster-head Gateway Switch Routing，CGSR）[16]簇间采用的是先验式路由方式，簇首和簇首之间周期性交互簇路由信息和簇成员信息，即时维护簇首和簇首之间的路由。CGSR 路由协议目前使用最为广泛，但是CGSR 路由协议有一个缺点，所有簇成员业务必须先发送到本簇簇首，然后通过本簇簇首转发到目的簇，这样会导致簇首节点流量过大，不利于负载均衡，网络比较脆弱。国内有些学者也针对CGSR 这一缺点做了研究，例如：文献[17]通过减少信息转发次数，减少簇首能量消耗；文献[18]通过选取多个簇首分摊流量的方式，平衡簇首能量消耗。但是这些研究中的业务仍需要先发往簇首，然后转发到目的簇。本文提出了一种簇间路由方法，业务直接由节点发往网关，不经过簇首。

本文所提方案中，每个簇首会分别在规划的簇首广播时隙内，将簇邻居信息和簇成员列表广播洪泛到全网。把每个簇看成一个节点，简称簇节点，并分配一个独有的ID，然后就可以得到簇与簇之间的路由，具体思路为：先根据本簇的邻簇信息得到本簇的一跳簇节点；然后根据收到的一跳簇节点的邻簇信息分析，若该节点的簇ID 不是本簇节点且不是本簇的一跳簇节点的簇，则为本簇的两跳簇节点；再根据两跳簇节点的邻簇信息分析，若该节点的簇ID 不是本簇的一跳簇节点且不是本簇的两跳簇节点的簇，则为本簇的三跳簇节点。以此类推，将此过程进行下去直到没有新的多跳簇节点产生。这样就构建出了整个簇间的路由。

参照图4 以节点1 为例说明簇间路由建立过程，1 的一跳簇节点为2、3、4、7。2 和4 的一跳簇节点是本簇节点，故2 和4 方向没有1 的二跳簇节点。3 的邻簇节点中，非本簇节点且非本簇的一跳簇节点的有5 和6，所以5 和6 为1 的两跳簇节点，路由为1-3-5，1-3-6。7 的符合条件的邻居簇节点为8，故8 是1 的两跳簇节点，路由为1-7-8。如图4 所示，节点1 的所有路由构建完成。

图4 8 个分簇邻居关系

路由寻址时，根据簇间收到的簇内节点信息，可以判断目的节点所处的簇ID，然后根据簇间路由查询下一跳需要发往的簇节点，本节点发送到其对应的本簇网关即可。簇内节点只需要把业务发往由簇间路由确定的本簇网关，然后本簇网关把包发给对应邻簇网关，业务到邻簇后继续通过簇间路由确定需要发往的对应网关，直到业务发到目的簇后，由网关发往目的节点。本簇间路由方案由于簇数量有限，所以建立路由的过程简单方便，而且实现了业务直接发往网关，不需要簇首的参与，还可以在选举网关时多选举几对来分摊网关的流量。

4 仿真及分析

本节用OPNET 仿真软件进行模拟建模，将本方案的分簇OLSR 路由协议和平面网络架构的标准OLSR 路由协议进行对比。如图5 所示，网内共有128 个节点，在运行标准OLSR 路由协议情况下，128 个节点不分簇，在运行本方案路由情况下，128个节点分为4 个簇，每个簇32 个节点，两者对比。

图5 128 节点仿真分布

仿真结果如图6 所示，对比两种情况下网内路由开销。仿真设置的10 s 开始运行路由，图6 横轴是运行时间，总共运行2分钟，纵轴是全网路由开销，单位bits/s 表示每秒全网路由开销的比特数。图6上半部分表示平面网络架构下标准OLSR 的路由开销，路由运行稳定后路由开销稳定在每秒20 万比特到每秒60 万比特之间。图6 下半部分表示本方案的分簇OLSR 路由的开销，路由运行稳定后路由开销稳定在接近每秒5 万比特。可以看出，运用分簇网络架构的本方案相比传统的平面网络架构的标准OLSR，能大幅度降低全网内网络开销，前者峰值仅为后者峰值的1/12。

图6 仿真结果对比

5 结语

随着MANET 中节点数越来越多，全网的路由开销越来越大，传统的平面网络架构已经不适用于MANET 网络。本文针对这一情况，选择分簇网络架构，提出了一种基于OLSR 的分簇路由协议，可以很好地降低大规模MANET 网内路由开销。下一步研究需要考虑如何花费较小时隙资源将簇内成员信息和簇间邻居关系广播到全网。