基于OLSR协议的最小MPR集选择算法

基于OLSR协议的最小MPR集选择算法

作者：刘杰 王玲 王杉 冯微 李文 来源：《计算机应用》2015年第02期

摘要：针对传统优化链路状态路由（OLSR）协议中利用贪婪算法求解最小多点中继（MPR）集时存在冗余的问题，提出了一种基于全局改进的Global_OP_MPR算法。首先引入了一种基于贪婪算法改进的OP_MPR算法，该算法通过逐步优化MPR集的方法去除冗余，可以简单高效地得到最小MPR集；然后在OP_MPR算法的基础上，将全局因素加入MPR选择判据中，引入“全局优化”代替“局部优化”，最终利用该算法可以得到整个网络的最小MPR集。在OPNET上采用Random Waypoint运动模型进行仿真，与传统OLSR协议相比，采用OP_MPR和Global_OP_MPR算法的OLSR协议在整个网络上有效地减少了MPR节点的数量，并且具有更少的网络负担拓扑控制（TC）分组数和更低的网络延时。仿真结果表明，所提出的算法均能优化MPR集的大小，提高协议的网络性能；同时，Global_OP_MPR算法由于考虑了全局因素，达到了更好的网络性能效果。

关键词：优化链路状态路由协议；贪婪算法；最小多点中继集；全局优化；OPNET仿真 中图分类号： TP393.07TN915.04 文献标志码：A

Abstract： Aiming at the problem that there is redundancy when using the greedy algorithm to solve the minimum MultiPoint Relay （MPR） set in the traditional Optimized Link State Routing （OLSR） protocol， a Global_OP_MPR algorithm based on the improvement of overall situation was proposed. First， an improved OP_MPR algorithm based on the greedy algorithm was introduced， and this algorithm removed the redundancy by gradually optimizing MPR set， which could simply and efficiently obtain the minimum MPR set； then on the basis of OP_MPR

algorithm， the algorithm of Global_OP_MPR added the overall factors into MPR selection criteria to introduce \"overall optimization\" instead of \"local optimization\"， which could eventually obtain the minimum MPR set in the entire network. Simulations were conducted on the OPNET using Random Waypoint motion model. In the simulation， compared with the traditional OLSR protocol， the OLSR protocol combined with OP_MPR algorithm and Global_OP_MPR algorithm effectively reduced the number of MPR nodes in the entire network， and had less network load to bear Topology Control （TC） grouping number and lower network delay. The simulation results show that the proposed algorithms including OP_MPR and Global_OP_MPR can optimize the size of the MPR set and improve the network performance of the protocol. In addition， due to taking the overall factors into consideration， Global_OP_MPR algorithm achieves a better network performance. Key words： Optimized Link State Routing （OLSR） protocol；greedy algorithm；minimum MultiPoint Relay （MPR） set；global optimization；OPNET simulation

龙源期刊网 http://www.qikan.com.cn

0 引言

优化链路状态路由 （Optimized Link State Routing，OLSR）协议是一种基于最优化链路状态的表驱式路由协议。在OLSR协议中，通过选取多点中继（MultiPoint Relay，MPR）机制有效地减少了在洪泛过程中广播消息的转发数量，克服了表驱式路由协议中网络维护开销大的缺点，并广泛应用于大而密集的网络环境中。由于只有被选作MPR的节点才转发控制消息，且MPR节点只产生其与MPR选择节点间的链路状态信息，因此在OLSR协议中，MPR集的选取至关重要，将直接影响网络的性能[1～3]。

越少的MPR节点数量将带来越少的网络分组，而最小MPR集选取问题是一个非确定性多项式（Nondeterministic Polynomial， NP）完全问题，传统的MPR集选择使用贪心算法，通过局部优化的方法求得一种近似最优解[4～6]。由于这种贪心算法仅仅采用一条节点的覆盖度作为优先策略，所以求得的近优解往往带有一定的冗余；且算法只是针对本节点来求最小MPR集，并没有针对整个网络予以考虑[7～9]。不少研究文献针对上述存在的问题对MPR选择算法进行了改进：

文献[10]提出了一种基于蚁群算法的具有收敛性的MPR选择算法，该算法能够很好地在MPR集选择集中找到一个最优解，但时间复杂度较高，不能达到快速收敛的目的；文献[11]提出使用遗传算法来进行MPR最小集选取，该算法在群体规模较大时能达到很好的优化效果，但在群体规模较小时容易陷入局部最优；

文献[12]在传统贪心算法选择的MPR集基础上对结果进行再次排序判断，除去了冗余节点，该算法简单高效，但最优解不一定在此贪心算法选择的MPR集中，从而导致再次优化得到的并不一定是最优解。

此外，目前大部分的文献都是针对单个节点MPR集选择的改进，并没有从整个网络予以考虑，而事实上只有整个网络的MPR节点变少，网络产生的分组开销才会明显减少，这才是OLSR路由协议应该要达到的目标。文献[13]也提出了应该从整个网络考虑MPR集选择的必要性，但其更侧重于增加MPR链路的稳定性，并没提出一种具体的选择策略。

本文提出了一种改进的MPR集选择算法，通过修改贪心策略，在保证MPR选择准则的前提下进行逐步优化，直至达到最优解。该算法继承了贪心算法简单高效的优点，避免了传统贪心算法容易陷入局部最优而带来的节点冗余问题。该算法在能求得单个节点的最小MPR集的基础上进行进一步优化，考虑到全局因素带来的影响，在进行最优化求解之前，先考虑使整个网络的MPR节点数达到最优，再逐步优化本节点的MPR集选取，并最终得到一种能保证整个网络MPR节点数最少的改进MPR集选择算法。 1 传统的最小MPR集选择算法 1.1 算法准则

龙源期刊网 http://www.qikan.com.cn

网络中每个节点独立地计算自己的MPR集，MPR集的选定应满足下列条件：首先，节点i的MPR集元素取自于i的一跳节点集；其次选定的一跳节点能覆盖i的全部二跳节点。因此可将最小MPR集选择问题转变为如下数学模型的表达形式：定义节点i的MPR集为集合S，其一跳邻居节点的集合为M1（i），二跳邻居节点的集合为M2（i），据MPR集的选定的必要条件：

上述方法的优点在于计算简单且快速，时间复杂度为O（n×lb（n））[11]，但是由于贪心策略的选择依据仅为一跳相邻节点的覆盖数最多的节点，得到的并不一定是最优解，所以利用该算法求得的MPR集可能会存在很大的冗余。 1.3 实例说明

如图1所示的拓扑结构中，若依照传统贪心策略算法，首先根据1.2节算法描述中的步骤3选择节点d，然后根据步骤4依次选择a、b、f，于是得到MPR集为：S={a，b，d，f}，而实际上此图的最小MPR集为{b，d，f}。由此可以说明依据传统最小MPR集选择算法得到的MPR集不一定是最优解。 2 改进的最小MPR集选择算法 2.1 针对贪心策略的改进

传统的MPR集选择算法得到的MPR节点集虽然满足了必要条件，但不一定能得到最优解，可能会使MPR节点集合存在很大的冗余。

因此本文提出了改进的最小MPR集选择算法，该算法为了避免MPR节点集的冗余，修改了贪心策略，在保证满足MPR集的选择条件下，逐步优化MPR集，使其能达到最优解。采用改进的贪心策略算法不仅可以得到最小MPR集，同时也是最优MPR集。其算法描述如下： 步骤1

定义中心节点i的MPR集S，且初始化S为M1（i），并将所有节点标记为未选定； 步骤2

对于M1（i）中所有的节点，分别获取它们在M2（i）中所能覆盖的节点个数； 步骤3

在将S中标记为未选定且覆盖数最小的节点退出S的情况下，测试此时在M2（i）中是否存在未被S中任何节点覆盖的二跳节点，如果存在则说明该节点不能退出S，并将该节点标记为已选定，否则将该节点退出S；

龙源期刊网 http://www.qikan.com.cn

步骤4

S中是否存在未选定的节点，存在则继续进行步骤3，否则算法结束。

关于算法时间复杂度的计算，在一般情况下，算法中基本操作重复执行的次数是问题规模n的某个函数，用T（n）表示，若有某个辅助函数f（n），使limn→∞（T（n）/f（n））的值是一个常数，则称f（n）是T（n）的同数量级函数，记O（f（n））为算法的时间复杂度。下面对上述算法的时间复杂度进行说明：

由此可知，上述算法与传统MPR集选择算法在理想情况下具有相同的时间复杂度（O（n×lb（n））），且该算法可以通过逐步优化的方法求得MPR集的最优解，避免在使用传统算法求解MPR集时所带来的冗余。

下面依据图1的实例来说明本算法能求解出MPR集的最优解。

若依照改进的贪心策略算法，首先根据上述算法描述中的步骤1初始化S为{a，b，c，d，e，f}，再根据步骤2分别计算其覆盖度为：{6，4，2，2，2，4}；最后根据步骤3选择覆盖度最小的节点测试其退出是否会影响M2（i）完整性，通过测试发现覆盖度最小的d的退出会影响M2（i）完整性，所以节点d不能退出，标记节点d为已选定。通过继续测试发现节点c、e的退出不会影响M2（i）完整性，b、d的退出会影响M2（i）完整性，并在最后将节点a去掉。所以测试的结果可以将节点c、e、a退出集合S，并得到MPR集为：S={b，d，f}，由此可知该算法得到的集合S为最小MPR集。 2.2 针对全局最小MPR集的改进

改进后的贪心策略算法能够快速高效地找到本节点的最小MPR集，但每个节点的局部最优并不代表整个网络最优。为了尽可能地减少网络分组的数量，提高网络性能，就必须要尽可能地减少整个网络MPR集的大小。

改进的MPR集选择算法为了能使整个网络的MPR集最小，在进行单个节点的MPR集优化时，先考虑全局因素，对于已被其他节点选入MPR集的一跳邻居节点，如果在其承载值（Willness：能成为其他节点的MPR的数量）范围内，则优先将其加入本节点的MPR集中，再在此基础上依照改进的贪心策略算法进行单个节点最小MPR集选取。最终得到一种能保证整个网络MPR节点数最少的改进MPR集选择算法，其算法描述如下： 步骤1

定义中心节点i的MPR集S，且初始化S为M1（i），并将所有节点标记为未选定； 步骤2

龙源期刊网 http://www.qikan.com.cn

对于M1（i）中所有的节点，分别计算它们在M2（i）中所能覆盖的节点个数； 步骤3

检测S中的所有节点，对于其中已经被其他中心节点标记为MPR的节点，判断其Willness是否为0，若不为0则优先加入MPR集中，将该节点标记为已选定，在测试完成之后则跳转步骤5。 步骤4

检测如果将S中标记为未选定且覆盖数最小的节点退出S的情况下，此时是否在M2（i）中还存在未被S中任何节点覆盖的节点，如果存在则说明该节点不能退出S，并将该节点标记为已选定，否则将该节点退出S。 步骤5

S中是否存在未选定的节点，存在则继续进行步骤4，否则算法结束。

该算法将全局因素在单个节点MPR集优化之前进行考虑，在选择本节点的MPR集时，优先将已被其他节点选定为MPR节点的节点加入本节点的MPR集中。由于此时部分二跳节点已被优先覆盖，二跳邻居节点集合将被缩小，本节点再进行MPR集选择时，会使额外MPR节点数降低，同时整个网络新增MPR节点也会减少，从而可以得到全局最小的MPR集。 2.3 改进算法的可行性分析

该改进算法总体上还是以2.1节所提算法为基础，由于针对贪心策略的改进算法继承了传统MPR集选择算法时间复杂度低、收敛快的优点，同时还避免了传统算法求得的MPR集所带来的冗余，而本算法在改进时并没有增加算法的额外时间复杂度，MPR集中大部分节点的选取仍然按针对贪心策略的改进算法求取，因此该算法同样具有高效、快速的优点，便于实际中的应用与实现。

该算法设计了“全局优化”代替“局部优化”，在选择本节点的MPR集时，优先将已被其他节点选定为MPR节点的节点加入本节点的MPR集中，因此实际上获取“其他节点选定为MPR节点”的信息是算法的基础，而在OLSR协议中相邻节点间可以通过广播报文获取相互的身份信息。同时，由于全局网络中随着网络拓扑的变化，MPR节点的选取将是一个持续进行的过程，在网络初始化时，由于大部分节点均未成为MPR节点，且大部分节点均未能获取到“其他节点选定为MPR节点”的信息，此时该算法相当于2.1节的针对贪心策略的改进算法；随着拓扑变动，网络中MPR节点的选取持续进行且选取时间不再同步，节点将能够检测到相邻的其他MPR节点，此时该算法将逐步体现出全局优化的优势。

龙源期刊网 http://www.qikan.com.cn

此外，该算法的运行将不可避免地加重MPR节点的传输负担，所以算法是在牺牲了一定的负载均衡的代价下，降低了整个网络的信息负载，因此该算法不利于电量有限的网络环境，如传感器网络等。但在移动自组织网环境中，节点一直处于位置变化之中，随着拓扑位置的变化，网路中任何节点都有被选为MPR节点的可能，所以此时该算法不会导致出现负载不均衡的情况。 3 仿真与分析

为了验证本文提出的MPR改进算法在整个网络中MPR节点数量上的优化以及网络性能上的提高与改进，对基于标准的OLSR路由协议和改进的路由协议分别在整个网络的MPR节点数、延时、转发拓扑控制（Topology Control， TC）消息分组数等方面进行了比较。其中MPR节点数的比较体现了整个网络中MPR节点数量上的优化，而延时和转发TC消息分组数的比较则体现了协议在网络性能上的改进。同时改进的路由协议分为基于贪心策略的改进（OP_MPR）和基于全局的改进（Glolbal_OP_MPR），并将其分别进行比较，进一步说明本文所提算法在整个网络上的优势。 3.1 仿真环境

通过OPNET仿真平台，对标准OLSR协议（OLSR）、采用OP_MPR算法的OP_OLSR协议和采用Glolbal_OP_MPR算法的Global_OP_OLSR协议分别进行仿真。仿真场景设置为：在大小为3000m×3000m的区域内设置有256个Ad Hoc节点，每个节点的承载值Willness设置为8，信道模型为自由空间传播，移动方式为随机模式，移动速度为10m/s。 3.2 仿真结果分析

图2～4分别给出了256个Ad Hoc节点在不同时刻下整个网络的MPR节点数量、TC消息分组数据传输率和网络延时的仿真结果比较。

由图2可知，在网络收敛稳定后，OLSR协议组成的Ad Hoc网络中MPR节点数量大概为240个，OP_OLSR协议组成的Ad Hoc网络中MPR节点数量大概为200个，而

Global_OP_OLSR协议组成的Ad Hoc网络中MPR节点数量大概为180个。OP_OLSR协议在单个节点的局部范围内求得最小MPR集，一定程度上减少了整个网络的MPR节点数量；而Global_OP_OLSR从全局角度出发，不仅继承了基于贪心策略改进的OLSR协议解决局部冗余的特性，还在整个网络上减少了MPR节点的数量。

由图3可知，在网络收敛稳定后，OLSR协议组成的Ad Hoc网络中TC分组数据传输率大概为4Mb/s，OP_OLSR协议组成的Ad Hoc网络中TC分组数据传输率大概为2.5Mb/s，而Global_OP_OLSR协议组成的Ad Hoc网络中TC分组数据传输率大概为1.8Mb/s。OP_OLSR协议和Global_OP_OLSR协议均优化了传统OLSR协议的MPR集，而Global_OP_OLSR协议

龙源期刊网 http://www.qikan.com.cn

在全局范围内优化效果更好，所以其网络负担TC分组数据传输率也更小。由图3也能进一步说明整个网络中MPR数量的减少将提高网络整体性能。

由图4可知，在网络收敛稳定后，OLSR协议组成的Ad Hoc网络的网络延时为0.9ms，OP_OLSR协议组成的Ad Hoc网络的网络延时为0.5ms，而Global_OP_OLSR协议组成的Ad Hoc网络的网络延时为0.3ms。这进一步说明了OP_OLSR协议和Global_OP_OLSR协议在网络性能上优于传统OLSR协议，且Global_OP_OLSR协议能达到更好的效果。 仿真结果表示，

基于贪心策略改进的MPR算法OP_MPR和基于全局改进的MPR算法Global_OP_MPR通过优化MPR集的大小，

提高了协议在Ad Hoc网络上的运行性能；同时，Global_OP_MPR算法从整个网络的角度出发，优化了整个网络的MPR集的大小，能达到更优的网络性能。 4 结语

本文在传统OLSR路由协议的基础上，从优化MPR集的角度出发，提出了基于贪心策略改进的OP_MPR算法和基于全局改进的Global_OP_MPR算法，分别考虑了单个节点最小MPR集的求解和整个网络的最小MPR集的求解。仿真结果显示采用全局优化的MPR集选择算法，不仅能求得整个网络的最小MPR集，还有效地提高了网络传输性能。由于网络中信息传播冗余不仅与网络整体MPR集合的元素个数有关，还直接与MPR集合中的节点度相关，为此下一步的研究应该深入到节点度的级别进行算法性能的测试与优化。 参考文献：

[1]WANG J. AdHoc mobile wireless technology [M]. Beijing： National Defense Industry Press， 2004： 44. （王金龙.Ad Hoc移动无线技术[M].北京：国防工业出版社，2004： 44.） [2]LAN P， LI E， HE G. Research of mesh network based on the improved OLSR routing protocol[J]. Journal of Hangzhou Dianzi University， 2013，33（4）：54-57. （兰鹏，李二涛，何桂仙. 基于改进OLSR路由协议mesh网络的研究[J]. 杭州电子科技大学学报， 2013，33（4）：54-57.）

[3]YAN W， GUO W， LIU J. Implementation of IPv6 OLSR protocols in Linux OS [J]. Application Research of Computers， 2009， 26（2）： 655-659. （严雯，郭伟，刘军.Linux操作系统基于IPv6地址的OLSR协议实现方案[J].计算机应用研究， 2009， 26（2）： 655-659.）

龙源期刊网 http://www.qikan.com.cn

[4]BAI Y， LIU Y， YUAN D. An optimized method for minimum MPRs selection based on node density [C]// Proceedings of the 2010 6th International Conference on Wireless Communications Networking and Mobile Computing. Piscataway： IEEE， 2010： 1-4.

[5]Yamada K， ITOKAWA T， KITASUKA T， et al. Cooperative MPR selection to reduce topology control packet in OLSR [C]// TENCON 2010： Proceedings of the 2010 IEEE Region 10 Conference. Piscataway： IEEE， 2010： 293-298.

[6]XIE F， ZHANG X， GUO J， et al. A delay oriented adaptive routing protocol for mobile Ad Hoc networks [J]. Journal of Software， 2005， 16（9）： 1661-1667. （谢飞， 张信明，郭嘉丰，等. 延迟主导的自适应移动Ad Hoc网络路由协议 [J]. 软件学报，2005，16（9）：1661-1667.）

[7]BAI Y， CHEN L. Extended multicast optimized linkstate routing protocol in MANETs with asymmetric links [C]// GLOBECOM 07： Proceedings of the 2007 IEEE Global Telecommunications Conference. Piscataway： IEEE， 2007： 1312-1317.

[8]LI Z， YU N， DENG Z. NFA： a new algorithm to select MPRS in OLSR [C]// WiCOM 08： Proceedings of the 4th International Conference on Wireless Communications. Piscataway： IEEE， 2008： 1-6.

[9]QAYYUM A， VIEMOT L， LAOUITI A. Multipoint relaying for flooding broadcast messages in mobile wireless networks [C]// HICSS 2002： Proceedings of the 35th Annual Hawaii International Conference on System Sciences. Piscataway： IEEE， 2002： 3866-3875. [10]ZHONG L， ZHAO X， XIA H. An ant colony algorithm and simulation for solving minimum MPR sets [J]. CAAI Transactions on Intelligent Systems， 2011，6（2）： 166-171.（钟珞，赵先明，夏红霞.求解最小MPR集的蚁群算法与仿真[J].智能系统学报，2011，6（2）：166-171.）

[11]ZHANG X， ZENG Y， GAN G， et al. Finding the minimum MPR set in OLSR protocol with genetic algorithms [J]. Journal of Software， 2006，17（4）：932-938.（张信明，曾依灵，干国政，等. 用遗传算法寻找OLSR协议的最小MPR集[J].软件学报，2006，17（4）：932-938.）

[12]ZHAO J， SUN J. Simulation and analysis an improved OLSR routing protocol based on NS2 [J]. Computer Simulation， 2008， 25（1）： 161-163. （赵健，孙俊锁. OLSR路由协议的改进及其NS2仿真分析[J]. 计算机仿真， 2008， 25（1）： 161-163.）

龙源期刊网 http://www.qikan.com.cn

[13]LEONARDO M， REBATO L. How to reduce and stabilize MPR sets in OLSR networks [C]// WiMob 2012： Proceedings of the IEEE 8th International Conference on Wireless and Mobile Computing. Piscataway： IEEE， 2012： 373-380.

龙源期刊网 http://www.qikan.com.cn