###
DOI:
Journal of Software:2006.17(4):932-938

用遗传算法寻找OLSR协议的最小MPR集
张信明,曾依灵,干国政,陈国良
(中国科学技术大学,计算机科学技术系,安徽,合肥,230027;国家高性能计算中心(合肥),安徽,合肥,230027;Department of Electrical Engineering and Computer Science, Korea Advanced Institute of Science and Technology, Daejeon 305701, Korea)
Finding the Minimum MPR Set in OLSR Protocol with Genetic Algorithms
ZHANG Xin-Ming,ZENG Yi-Ling,GAN Guo-Zheng,CHEN Guo-Liang
()
Abstract
Chart / table
Reference
Similar Articles
Article :Browse 3556   Download 3093
Received:April 21, 2004    Revised:October 11, 2005
> 中文摘要: 节点可以自由、自主地进入网络拓扑的特性,使得移动Ad hoc网络(mobile ad hoc network,简称MANET)被广泛应用于诸如灾难救援、战场等多种环境中.MANET中的路由要能迅速地适应频繁的网络拓扑结构的变化,同时最大限度地节约网络资源.OLSR(optimized link state routing protocol)协议是一个重要的MANET路由协议,而支撑此协议的一个关键技术是MPR(multipoint relays).在介绍了OLSR协议及MPR技术之后,揭示了目前启发式算法在寻找最小MPR上的弱点,提出了一种基于遗传算法(genetic algorithm,简称GA)的新算法,并证明了该算法的收敛性.通过采用不同遗传策略将此遗传算法衍生成了4个系列算法,并在随机生成的拓扑上对其进行模拟.模拟结果分析显示:提出的遗传算法是可行和适用的,选择的启发式策略也是恰当和正确的.
中文关键词: OLSR  MPR  启发式算法  遗传算法  移动Ad hoc网络
Abstract:The characteristic that nodes can enlist into the network topology freely and independently makes mobile Ad hoc networks (MANET) widely used in various environments such as disaster rescue, battlefield and so on. In MANET, the routing mechanism should adapt rapidly to the frequently changed network topology and in the mean time economize valuable network resources with its best. The Optimized Link State Routing Protocol (OLSR) is an important MANET routing protocol in which the key technique is MultiPoint Relays (MPR). After introducing the OLSR protocol and its MPR technique, the shortcoming of presently used heuristic algorithm in finding the minimum MPR sets is revealed. Then the new algorithm based on genetic algorithm (GA) is presented, and the convergence of the algorithm is proved. A series of 4 genetic algorithms are further developed by adopting different GA strategies and simulated in many topologies that are created randomly. Analysis on simulating results shows that the genetic algorithms are feasible and applicable and the choice of heuristic strategies is advisable and appropriate.
文章编号:     中图分类号:    文献标志码:
基金项目:Supported by the Key Project of the National China Next Generation Internet(CNGI) 2005 (国家"CNGI(下一代互联网示范工程)"专项重点支持项目); the Key Postdoctoral Foundation of the Ningbo City of China under Grant No.2003A61003 (宁波市重点博士科学基金); the Foundation of Science and Technology of Huawei of China under Grant No.YJCB2004036WL (华为科技基金); the International Scholar Exchange Fellowship (ISEF) of the Korea Foundation for Advanced Studies 2005-2006 (韩国高等教育财团国际交换学者奖) Supported by the Key Project of the National China Next Generation Internet(CNGI) 2005 (国家"CNGI(下一代互联网示范工程)"专项重点支持项目); the Key Postdoctoral Foundation of the Ningbo City of China under Grant No.2003A61003 (宁波市重点博士科学基金); the Foundation of Science and Technology of Huawei of China under Grant No.YJCB2004036WL (华为科技基金); the International Scholar Exchange Fellowship (ISEF) of the Korea Foundation for Advanced Studies 2005-2006 (韩国高等教育财团国际交换学者奖)
Foundation items:
Reference text:

张信明,曾依灵,干国政,陈国良.用遗传算法寻找OLSR协议的最小MPR集.软件学报,2006,17(4):932-938

ZHANG Xin-Ming,ZENG Yi-Ling,GAN Guo-Zheng,CHEN Guo-Liang.Finding the Minimum MPR Set in OLSR Protocol with Genetic Algorithms.Journal of Software,2006,17(4):932-938