Journal of Computer Applications ›› 2015, Vol. 35 ›› Issue (2): 305-308.DOI: 10.11772/j.issn.1001-9081.2015.02.0305

Previous Articles     Next Articles

Minimum MPR set selection algorithm based on OLSR protocol

LIU Jie1, WANG Ling1, WANG Shan2, FENG Wei3, LI Wen3   

  1. 1. College of Electrical and Information Engineering, Hunan University, Changsha Hunan 410082, China;
    2. College of Electronic Science and Engineering, National University of Defense Technology, Changsha Hunan 410073, China;
    3. Institute of China Electronics System Engineering Company, Beijing 100000, China
  • Received:2014-09-06 Revised:2014-11-04 Online:2015-02-10 Published:2015-02-12

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

刘杰1, 王玲1, 王杉2, 冯微3, 李文3   

  1. 1. 湖南大学 电气与信息工程学院, 长沙 410082;
    2. 国防科学技术大学 电子科学与工程学院, 长沙 410073;
    3. 中国电子系统设备工程公司研究所, 北京 100000
  • 通讯作者: 刘杰
  • 作者简介:刘杰(1990-),男,湖南平江人,硕士研究生,主要研究方向:嵌入式系统、Ad Hoc网络路由算法; 王玲(1962-),女,湖南长沙人,教授,博士,主要研究方向:现代通信与网络技术、图像信号处理; 王杉(1978-),男,陕西兴平人,副教授,博士,主要研究方向:无线通信网络、嵌入式系统; 冯微(1981-),女,河北石家庄人,硕士,主要研究方向:移动通信; 李文(1979-),男,北京人,硕士,主要研究方向:无线通信。
  • 基金资助:

    国家自然科学基金资助项目(91338105);通信抗干扰技术国家级重点实验室基金资助项目;通信网信息传输与分发技术重点实验室基金资助项目。

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

摘要:

针对传统优化链路状态路由(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仿真

CLC Number: