基于改进OLSR路由协议mesh网络的研究

兰 鹏，李二涛，何桂仙

(1.杭州电子科技大学计算机应用研究所，浙江 杭州310018;2.东阳市东政电机有限公司，浙江 东阳322100)

0 引言

无线mesh网络是一种基于多跳自组织、对等网络技术的新型网络结构，具有移动宽带的特性，无线mesh网络广泛应用于军事通信、灾后紧急救援、传感器网络等众多领域［1］。由于无线mesh网络的分布式、无中心、自组织、节点可移动等技术特点，使得它存在很多技术难题需要解决，其中最关键的是路由协议的改进［2］。为了实现网路节点之间的负载均衡，提高系统资源的利用率和网络的吞吐量，降低网络延时［3］，本文基于最优化链路状态(Optimized Link State Routing，OLSR)协议［4］，提出一种 MPR 集合选择算法，综合最小化MPR的冗余性和每个节点的负载，避免了原有算法可能会导致网络节点负载过重、出现网络拥塞的情况［5－7］。

1 OLSR路由协议

OLSR路由协议是由移动自组网工作组提出的一种表格驱动、主动式路由协议，它继承了链路状态算法的稳定性，同时对经典的链路状态算法进行了优化。它的核心是多点中继(Multi Point Relay，MPR)，MPR是被专门选定的节点，用于在洪泛过程中转发广播消息。OLSR路由协议对纯链路状态算法所做的优化如下:

(1)采用多点中继机制有效的减少了洪泛过程中的转发广播消息。每个节点都从其邻居节点中选择一组节点作为MPR，只有被选作MPR的节点才负责转发控制消息。相比经典的洪泛机制极大的降低了信息开销，这是一种高效的洪泛机制。其工作机制如图1所示。

图1中节点a选择它的邻居节点m1、m2、m3作为它的MPR集合，当节点a洪泛广播消息的过程中只有节点m1、m2、m3转发这条消息，然后节点m1、m2、m3分别在它们自己的一跳邻居节点里面选择MPR集合，进行洪泛消息的转发，依此类推，将节点a洪泛消息传播到网络中的每一点，建立起了可靠的网路拓扑;

图1 MPR洪泛机制

(2)只有MPR节点才产生链路状态消息，缩减了控制分组的大小。网络中的节点并不发布与所有一跳邻居节点的链路信息，而只声明与其中继选择节点(MPR Selector)之间的链路。对比经典链路状态算法，OLSR协议的局部链路状态信息分布在网络中。

OLSR协议非常适用于规模大、节点密度高的网络，这是因为采用了MPR的优化在这种网络中表现良好。对比经典链路状态算法，网络的规模越大、节点密度越高，MPR优化的效果越好。OLSR协议使用逐跳路由，即每个节点使用其本地信息为分组选择传输路由。

2 OLSR协议MPR选择的不足及改进

一个节点的MPR集合应该满足:该节点通过其MPR集合中的节点能够到达所有对称两跳相邻节点;一个节点的MPR集合选择得尽可能小，以便降低协议的开销。

标准OLSR协议的贪婪算法虽然可以成功的选择了一个MPR集，但是存在如下问题:(1)MPR集合存在冗余;(2)在选择MPR集合时没有考虑节点的负载，有的节点出现负载过重，有的节点处于闲置状态，降低了整个网络的资源利用率。

基于上述问题，提出了一种改进的选择MPR集合的算法，改进了原有算法在选择MPR集时的不足。在OLSR路由协议的HELLO消息里面有个意愿程度(willingness)字段，用它表示一个节点愿意承载和转发其他节点的信息，其意愿程度可以设为0－7之间的任意一个整数。为了避免一个节点的被多次被其他节点选为MPR，我们可以动态的设置意愿程度这个字段，改进的MPR集合的选择算法描述如下:

(1)将节点的MPR集合置为空，将节点的一跳邻节点的意愿程度设为最大，即N_willingness域设为WILL_ALWAYS(既为7);(2)如果存在到达某个两跳邻节点的唯一通路的邻节点，则选择此节点作为MPR，并将N_willingness的值减1，删除N2中目前被MPR集覆盖的节点。如果此时N2中不存在任何节点，算法结束，否则进入下面步骤;(3)统计N_willingness的值，选择集合N中的willingness值最小的，如果只有一个删除掉，如果有多个，删除其中可到达性最小的，然后跳到b中继续执行。这里删除willingness最小的，表示不能选择负载较大的节点作为MPR集合，因为前面已经有很多节点选择其作为MPR集合，选择其他负载较小的节点可以优化网络性能，且此时选择的MPR集合的冗余性最小;(4)将一个节点的每个接口的MPR集合组合在一起，则建立MPR集合。

算法的流程如图2所示:

图2 改进MPR选择算法的流程图

该改进算法在选择MPR集合时通过一跳邻节点的willingness实时记载该节点的负载。考虑了网络的多路径的负载，提高了系统的资源利用率，不会出现一些节点负载过重，一些节点处于闲置的状态，又通过删减N中的willingness最小的节点，减小了MPR的冗余，也减小了路由的开销。

3 实验系统及结果分析

为了验证本文提出的MPR改进算法在mesh网络上性能的提高与改进，基于标准的OLSR路由协议和改进的路由协议分别在网络的吞吐量、延时、转发TC消息分组数等方面进行比较。

实验采用的硬件节点是ubiqiti公司的router-station pro，在空旷的200m×200m区域布置10个节点组成多跳、自组的无线mesh网络。在测试网速的吞吐量及网络延时采用的是NetIQ Chariot，统计转发TC消息分组数是通过监听MPR集合接口收到的数据包获取。

如图3所示，原OLSR路由协议组成的mesh网络的吞吐量大概为4.8Mbps，而修改后MPR选择算法后网络的吞吐量大概为5.2Mbps，有了一定程度的提高。因为改进的MPR算法均衡了网络节点的负载，不会出现某些节点过载，而一些节点出现空闲的状态，提高了网络的传输数据的容量。

图3 无线mesh网络的吞吐量

如图4所示，原OLSR协议的端到端的延时时0.023s，改进的算法组成的mesh网络的延时0.018s，可以看出较大程度上改进了网络的延时，原因是节点的链路选择避开了负载较重的链路，充分利用了网络的资源。

OLSR协议的TC消息由MPR广播和转发，将整个消息洪泛到整个网络，通过收集网络中的的转发TC分组的数量，可以反映网络中的MPR集的冗余程度。如图5所示，改进的OLSR的路由协议在TC消息转发(50个)方面要优于原来的OLSR协议(55个)，减少了MPR集合的冗余，降低了原协议10%的开销，改进了原来OLSR协议的性能。

图4 无线mesh网络的端到端的延时

图5 无线mesh网络的转发TC分组统计

4 结束语

本文从改进mesh网络的节点负载的、提高网络资源利用率出发，提出了一种新的OLSR协议MPR集合的算法，把节点的负载信息加到节点的意愿程度的字段上，在选择节点作为MPR集合时，通过排序，把节点负载较重的节点排除出去，既均衡了MPR集合中节点的负载，也减少了MPR集合的冗余度。通过实验收集数据，改进的OLSR协议在网络延时、网络吞吐量、网路转发TC消息数量等方面均优于原来的通过贪婪算法所选择的MPR集。

［1］陈林星，曾曦，曹毅.移动Ad-Hoc网络—自组织分组无线网络技术［M］.北京:电子工业出版社，2006:1－44.

［2］Navda v，Kashyap A，Das S R.Design and Evaluation of iMesh:an Infrastructure-mode Wireless Mesh Network［C］.WoWMoM:Sixth IEEE International Symposium on a World of Wireless Mobile and Multimedia Networks，2005:164－170.

［3］Song Wen，Fang Xu-ming.Routing with congestion control and load balancing in wireless mesh networks［C］.Chengdu:6th International Telecommunications Conference，2006:719 －724.

［4］Clausen T，Jacquet P.Optimized Link State Routing Protocol(OLSR)［EB/OL］.http://www.ietf.org/rfc/rfc3626.txt，2003－03－20.

［5］Bai Yun-fei，Liu Yuan-an，Yuan Dong-ming.An Optimized Method for Minimum MPRs Selection Based on Node Density［C］.Chengdu:Wireless Communications Networking and Mobile Computing 2010 6th International Conference，2010:1－4.

［6］Kenji Yamada，Tsuyoshi Itokawa，Teruaki Kitasuka.Cooperative MPR Selection to Reduce Topology Control Packet in OLSR［C］.Fukuoka:TENCON 2010 IEEE Region 10 Conference，2010:293 －298.

［7］Zhao Xian-ming，Song Hua-zhu，Xia Hong-xia.Using Ant Colony Algorithm for Solving Minimum MPR set and OPNET Simulation［C］.Nanjing:The 1st International Conference on Information Science and Engineering，2009:898 －901.