一种新型MPR集选择算法

张 洪，高 杨

(1.成都大学 计算机学院，四川 成都 610106;2.成都大学 模式识别与智能信息处理四川省高校重点实验室，四川 成都 610106)

0 引 言

Ad hoc 网络是一种特殊的无线移动网络，网络中所有节点的地位平等，无需设置任何的中心控制节点.网络中的节点不仅具有普通移动终端所需的功能，而且具有报文转发能力.与普通的移动网络和固定网络相比，它具有无中心、自组织、多跳路由和动态拓扑的特点，适用于无法或不便预先铺设网络设施的场合［1－2］.本研究在传统优化链路状态路由(Optmized Link State Routing，OLSR)协议的基础上，通过组合数和按位运算结合的方法，不仅能达到传统OLSR 协议的目的，并且能有效找出特殊情况的MPR 集，减少不必要的数据转发开销，使其具有高效性，最后通过仿真平台实现了重新定义OLSR 的MPR 集算法.

1 OLSR与MPR简介

1.1 OLSR简介

OLSR 是根据MANET 的要求，在传统的LS(Link state)协议的基础上进行优化实现的.OLSR中的关键概念是多点转播MPRs，MPRs 在广播泛洪的过程中挑选转发广播的节点.传统的链路状态协议每个节点都转发它收到的信息的第一份拷贝，同它相比，OLSR 在很大程度上减少了转发的信息.

1.2 MPR的简介

1.2.1 MPR 的定义.OLSR 协议的核心是多点中继技术.多点中继的思路是通过减少同一区域内相同控制分组的重复转发次数来减少网络中广播分组的数量.网络中的每一个节点选取其邻节点的一个子集用于转发该节点发送的控制分组，这些被选择的节点就称为MPR.由此可见，网络中所有的节点可分为MPR 和非MPR.节点N 发送的广播分组会通过MPR 转发到达节点N 两跳以外的节点，而非MPR 只能进行读取和处理，不能转发.

1.2.2 传统OLSR 协议选择MPR 集存在的问题.

为了使用较少的数据转发开销，获得与全网泛洪一样的数据传输效果，区分MPR 集和非MPR 集是广播中继泛洪的核心.图1 中，节点N 向下一跳(节点a、b、c)发送广播数据.其中，节点b 的连接度最高，下一跳有5 个节点(节点2、3、4、5、6)，因此b节点即为首选的MPR.对于节点N 的两跳邻居(节点1、7)只能分别通过节点N 的一跳邻居a 和c 来接收广播数据.因此，节点a 和c 也为MPR.根据广播中继泛洪的思路，MPR={a，b，c}.

图1 广播中继泛洪的特例

观察图1 可见，节点a 的下一跳为节点1、2、3，节点c 的下一跳为节点4、5、6、7.而节点1 ～7 恰好全部为节点N 的两跳邻居.因此，节点N 通过节点a、c，广播数据同样可以达到全网泛洪的数据传输效果.相比传统的广播中继泛洪的方法，MPR = {a，c}，进一步减少了数据转发开销.

2 重新定义MPR集的OLSR改进方案

基于上述分析，本研究提出一种新的MPR 集选择算法，其思路是:

(1)全网泛洪，在每一节点定义变量并赋值为0，为后续的位运算做准备，并设置MPR 集初值为空.

(2)对中心节点的邻节点进行组合，Cin，(i =1，2，3，…，n)，其中，n 为中心节点的邻节点数.

(3)在每一次的组合中，凡是通过中心节点的邻节点能被访问到的二跳邻居全部自增1.

(4)对所有二跳邻居进行“与”运算，结果若为0，则变量的值全部重置为0，该节点不为MRP 集;结果若为1，则组合中的节点即为MPR 集.

(5)重复步骤(2)，直到所有一跳节点遍历完成，算法结束.

下面就图1 情况进行详细说明.

首先，将所有节点N 的二跳邻居定义变量并赋值为0，然后将分支节点a、b、c 进行组合，每一次组合即进行一次循环，访问到一次终端节点便自增1，最后进行按位“与”的运算，结果为0 便进行下一种组合的循环，直到“与”的运算结果为非零，即表示通过此次组合的分支节点能转发广播数据到下一跳的所有邻居.方法的具体实现步骤如下:

(1)首先从节点N 进行访问，在访问到的所有二跳邻居1 ～7 中分别定义变量TwoHopNeiI(I≤7，I∈N+)并赋予初值为0，然后将分支节点a、b、c 进行组合，即，

(2)第一次循环，分支节点a.

通过分支节点a 访问它的后继节点1、2、3.则节点中的变量TwoHopNeiI(I =1，2，3)自增1，结果为1.其他终端节点4 ～7 中变量的值不变，为0.然后进行所有终端节点中变量“与”的运算，即，

TwoHopNeiI(I=1，2，3)+ +;

TwoHopNeiI(I=4，5，6，7)= =0;

TwoHopNeiI＆＆……(I≤7，I∈N+)= =0;

所有终端节点变量的值重置为0，进行第二次循环.

(3)第二次循环，分支节点b.

通过分支节点b 访问它的后继节点2、3、4、5、6，则节点中的变量ChildI(I=2，3，4，5，6)自增1，结果为1，其他终端节点1、7 中变量的值不变，为0.然后进行“与”的运算，即，

TwoHopNeiI(I=2，3，4，5，6)+ +;

TwoHopNeiI(I=1，7)= =0;

TwoHopNeiI＆＆……(I≤7，I∈N+)= =0;

所有终端节点变量的值重置为0，进行第三次循环.

(4)第三次循环，分支节点c.

同理，“与”结果为0，进行第四次循环.

(5)第四次循环，分支节点a、b.

通过分支节点a 访问它的后继节点1、2、3，则节点中的变量ChildI(I =1，2，3)自增1，结果为1.通过分支节点b 访问它的后继节点2、3、4、5、6，则节点中的变量ChildI(I =1，4，5，6)自增1，结果为1.而终端节点2、3 自增2 次，结果为2.剩余终端节点7 中变量的值不变，为0.“与”的结果为，

TwoHopNeiI(I=1，2，3)+ +;

TwoHopNeiI(I=2，3，4，5，6)+ +;

TwoHopNeiI＆＆……(I≤7，I∈N+)= =0;

“与”结果为0，进行第五次循环.

(6)第五次循环，分支节点a、c.

通过分支节点a 访问它的后继节点1、2、3，则节点中的变量ChildI(I =1，2，3)自增1，结果为1.通过分支节点c 访问它的后继节点4、5、6、7，则节点中的变量ChildI(I =4，5，6，7)自增1，结果为1.此次进行“与”的运算结果为，

TwoHopNeiI(I=1，2，3)+ +;

TwoHopNeiI(I=4，5，6，7)+ +;

TwoHopNeiI＆＆……(I≤7，I∈N+)= =1;

结果非零，跳出循环.

所以，MPR={a，c}.

3 实 验

本实验通过仿真平台进行，本研究参考Ad hoc网络模型，在OPNET 网络仿真软件中实现.

1)仿真参数的设置.网络覆盖面积，3 ×3 km2;节点个数，25 个;节点的通信距离，300 m;信号的传输速度，0.5 Mb/s.

2)底层MAC 采用IEEE802.11 协议，以CSMA/CA 方式接入，物理层采用扩频跳频方式，网络层采用表驱动路由协议OLSR 协议.

实验仿真了网络在改进前后的数据传输成功率及数据传输时延，实验结果如图2、3 所示.

图2 数据传输成功率对比

图3 数据传输时延对比

从图2、3 可以看出，200 s 内，数据传输成功率明显提升，数据传输时延显著减少.此表明，采用组合数和按位“与”运算相结合的方法寻找最简MPR集不仅能达到传统OLSR 协议的目的，并且能有效地找出特殊情况的MPR 集，从而减少不必要的数据转发开销，使其具有高效性.

4 结 论

本研究所提的方法不仅能满足传统OLSR 协议的目标，即区分MPR 集和非MPR 集，使用较少的数据转发开销，获得与全网泛洪的数据传输效果，而且能有效地解决传统OLSR 协议选择MPR 集存在的问题.对于非特殊情况的全网泛洪，通过访问组合后1 跳邻居的后继节点以及按位进行“与”的运算能有效判断该种组合是否能达到泛洪全网的效果，从而有效区分出MPR 集与非MPR 集.

［1］周懿，郭伟，任智.战术互联网中的OLSR 路由协议研究［J］.电子技术，2004，37(3):11－19.

［2］张信明，曾依灵，干国政，等.用遗传算法寻找OLSR 协议的最小MPR 集［J］.软件学报，2006，17(4):932－938.

［3］卢宇，魏敏，吴钦章.基于MAC 层信息的OLSR 改进方案［J］.计算机工程，2007，33(22):121－123.

［4］陈文宇，陈洁莲，孙世新.面向链路状态信息的路由算法LSDSR［J］.电子科技大学学报(自然科学版)，2009，38(6):993－996.

［5］张洪，黄闽英.基于高速移动节点网络的OLSR 路由协议改进［J］.成都大学学报(自然科学版)，2008，27(1):38－40.