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

Minimum MPR set selection algorithm based on OLSR protocol

针对传统优化链路状态路由(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算法由于考虑了全局因素,达到了更好的网络性能效果。

Aiming at the problem that there is redundancy when using the greedy algorithm to solve the minimum MuhiPoint 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 OPMPR 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.