[1]钟珞,赵先明,夏红霞.求解最小MPR集的蚁群算法与仿真[J].智能系统学报,2011,6(2):166-171.
ZHONG Luo,ZHAO Xianming,XIA Hongxia.An ant colony algorithm and simulation for solving minimum MPR sets[J].CAAI Transactions on Intelligent Systems,2011,6(2):166-171.
点击复制
ZHONG Luo,ZHAO Xianming,XIA Hongxia.An ant colony algorithm and simulation for solving minimum MPR sets[J].CAAI Transactions on Intelligent Systems,2011,6(2):166-171.
求解最小MPR集的蚁群算法与仿真
《智能系统学报》[ISSN 1673-4785/CN 23-1538/TP] 卷:
6
期数:
2011年第2期
页码:
166-171
栏目:
学术论文—人工智能基础
出版日期:
2011-04-25
- Title:
- An ant colony algorithm and simulation for solving minimum MPR sets
- 文章编号:
- 1673-4785(2011)02-0166-06
- Keywords:
- minimum MPR set; ant colony algorithm; OLSR (optimized link state routing protocol); OPNET
- 分类号:
- TP393
- 文献标志码:
- A
- 摘要:
- 在分析利用贪心策略启发式算法求解最小MPR集的缺陷基础上，引入蚁群算法对最小MPR集进行求解.首先定义了节点及其出度和入度，并根据节点的出度和入度限制，给出了求解最小MPR集的蚁群算法.然后，对蚁群算法的3种模型AntCycle、AntQuantity和AntDensity加以改进，并对这3种改进模型的收敛性进行分析与实验.实验采用了圆形分布和理想均匀分布2种拓扑结构，前者实验结果表明AntCycle模型的收敛速度较快，后者结果表明AntCycle模型和AntDensity模型各有优势.因此，最小MPR集的蚁群算法的模型选择需依据拓扑结构确定.最后，使用OPNET基于该算法对数据链的点对多点的点名呼叫工作方式进行模拟仿真，选择的统计量显示了节点的连通性和数据一致性，验证了该算法的合理性.
- Abstract:
- Based on analyzing the defects of a heuristic algorithm of greedy strategy, an ant colony algorithm was imported to solve the minimum MPR set. First of all, a node and its out and indegrees were defined, and in accordance with the out and indegree constraints of the node, ant colony algorithms were given based on the graphics to find the minimum MPR set. Then, three kinds of ant colony algorithm models, the AntCycle, AntQuantity, and AntDensity models, were improved, and the convergence curves of the three kinds of models were analyzed and tested. An ideal uniform topology and a circular distribution topology were both used in experiments. Former experimental results showed that the AntCycle model was faster in convergence speed; the latter results showed that the AntCycle and AntDensity models both have advantages. Therefore, ant colony algorithm model selection of the minimum MPR set might be subject to topology. Finally, OPNET was used based on the above algorithm for simulation. It adopted the data link’s pointtomultipoint calling mode. The selected statistics show connectivity and data consistency among the nodes, which means that the algorithm is reasonable.
- 参考文献/References:
-
［1］HIDEHISA N，SATOSHI K, ABBAS J，et al. A dynamic anomaly detection scheme for AODVbased mobile ad hoc networks［J］. IEEE Transactions on Vehicular Technology, 2009, 58(5): 24712481.
［2］ASOKAN R. A review of quality of sService (QoS) routing protocols for mobile Ad hoc networks［C］//ICWCSC 2010, Chennai, 2010: 16.
［3］谢飞,张信明,郭嘉丰,陈国良.延迟主导的自适应移动Ad hoc网络路由协议［J］.软件学报, 2005, 16(9): 16611667.
Xie Fei, Zhang Xinming, Guo Jiafeng, et al. A delay oriented adaptive routing protocol for mobile Ad hoc networks［J］. Journal of Software, 2005, 16(9): 16611667.
［4］YONG Bai, LAN Chen. Extended multicast optimized link state routing protocol in MANETs with asymmetric links［C］//GLOBECOMIEEE Global Telecommunications Conference. Washington, DC, 2007: 13121317.
［5］WANG M, LAMORT L, MASON P, et al. An effective intrusion detection approach for OLSR MANET protocol［C］//Secure Network Protocols 1st IEEE ICNP Workshop, ［S.l.］, 2005: 5560.
［6］QAYYUM A, VIEMOT L, LAOUITI A. Multipoint relaying for flooding broadcast messages in mobile wireless networks［C］//The 35th Hawaii International Conference on System Sciences (HICSS 2002). Hawaii, 2002: 38663875.
［7］段海滨著. 蚁群算法原理及其应用［M］. 北京: 科学出版社, 2005: 1 447.
［8］赵健, 孙俊锁. OLSR路由协议的改进及其NS2仿真分析［J］. 计算机仿真, 2008, 25(1): 161163.
ZHAO Jian，SUN Junsuo. Simulation and analysis of an improved OLSR routing protocol based on NS2［J］. Computer Simulation, 2008, 25(1): 161163.
［9］张信明,曾依灵,干国政,陈国良. 用遗传算法寻找OLSR 协议的最小MPR集［J］. 软件学报, 2006, 17(4): 932938.
ZHANG Xinming, ZENG Yiling, GAO Guozheng, et al. Find the minimum MPR set in OLSR protocol with genetic algorithms［J］. Journal of Software, 2006, 17(4): 932938.
［10］夏红霞, 宋华珠, 钟珞. 算法设计与分析［M］ 湖北武汉:武汉大学出版社, 2007 :1344.
［11］骆光明等. 数据链信息系统连接武器系统的捷径［M］.北京:国防工业出版社, 2008: 1356.
- 相似文献/References:
-
[1]冀俊忠,刘椿年,黄 振.基于信息素扩散模型解耦控制策略的蚁群算法[J].智能系统学报,2007,2(4):1.
JI Jun-zhong,LIU Chun-nian,HUANG Zhen.An ant colony optimization algorithm based on a decouplingcontrol strategy of pheromone diffusion model[J].CAAI Transactions on Intelligent Systems,2007,2():1.
[2]印 峰,王耀南,刘 炜,等.个体速度差异的蚁群算法设计及仿真[J].智能系统学报,2009,4(6):528.[doi:10.3969/j.issn.1673-4785.2009.06.010]
YIN Feng,WANG Yao-nan,LIU Wei,et al.Design and simulation of an ant colony algorithm based on individual velocity differences[J].CAAI Transactions on Intelligent Systems,2009,4():528.[doi:10.3969/j.issn.1673-4785.2009.06.010]
[3]程显毅,巩向普.改进的模糊C-均值算法在医学图像分割中的应用[J].智能系统学报,2010,5(1):80.
CHENG Xian-yi,GONG Xiang-pu.An improved fuzzy Cmeans algorithm for segmentation of medical images[J].CAAI Transactions on Intelligent Systems,2010,5():80.
[4]孔 笋,陈增强.一种新的混沌蚁群算法及其在QoS组播路由优化问题中的应用[J].智能系统学报,2010,5(6):498.
KONG Sun,CHEN Zeng-qiang.A new chaotic ant colony optimization algorithm and its application in a QoS multicast routing problem[J].CAAI Transactions on Intelligent Systems,2010,5():498.
[5]陈明杰,黄佰川,张旻.混合改进蚁群算法的函数优化[J].智能系统学报,2012,7(4):370.
CHEN Mingjie,HUANG Baichuan,ZHANG Min.Function optimization based on an improved hybrid ACO[J].CAAI Transactions on Intelligent Systems,2012,7():370.
[6]杨本生,袁祥梦,黄晓光.基于动态优先权蚁群算法的分布式自动化测试调度[J].智能系统学报,2014,9(6):729.[doi:10.3969/j.issn.1673-4785.]
YANG Bensheng,YUAN Xiangmeng,HUANG Xiaoguang.Ant colony algorithm based on dynamic priority for distributed automation test scheduling[J].CAAI Transactions on Intelligent Systems,2014,9():729.[doi:10.3969/j.issn.1673-4785.]
[7]莫宏伟,马靖雯.基于蚁群算法的四旋翼航迹规划[J].智能系统学报,2016,11(2):216.[doi:10.11992/tis.201509009]
MO Hongwei,MA Jingwen.Four-rotor route planning based on the ant colony algorithm[J].CAAI Transactions on Intelligent Systems,2016,11():216.[doi:10.11992/tis.201509009]
[8]蒲兴成,李俊杰,吴慧超,等.基于改进粒子群算法的移动机器人多目标点路径规划[J].智能系统学报,2017,12(3):301.[doi:10.11992/tis.201606046]
PU Xingcheng,LI Junjie,WU Huichao,et al.Mobile robot multi-goal path planning using improved particle swarm optimization[J].CAAI Transactions on Intelligent Systems,2017,12():301.[doi:10.11992/tis.201606046]
[9]王辉,车超,于立君,等.鳍-水舱综合减摇混沌系统控制方法研究[J].智能系统学报,2017,12(3):318.[doi:10.11992/tis.201607012]
WANG Hui,CHE Chao,YU Lijun,et al.Control method for a fin/tank integrated stabilization chaotic system[J].CAAI Transactions on Intelligent Systems,2017,12():318.[doi:10.11992/tis.201607012]
[10]楼传炜,葛泉波,刘华平,等.无人机群目标搜索的主动感知方法[J].智能系统学报,2021,16(3):575.[doi:10.11992/tis.202009012]
LOU Chuanwei,GE Quanbo,LIU Huaping,et al.Active perception method for UAV group target search[J].CAAI Transactions on Intelligent Systems,2021,16():575.[doi:10.11992/tis.202009012]
备注/Memo
收稿日期： 2010-06-05.
基金项目：国家自然科学基金资助项目(61003130)；教育部高校行动计划资助项目(2004XD03).
通信作者：赵先明.
E-mail:freshzhaoxm@163.com.
作者简介：
钟珞，男，1957年生，教授，博士生导师，武汉理工大学计算机学院院长，CCF高级会员.武汉计算机软件工程学会副理事长，湖北省计算机学会副理事长.主要研究方向为智能技术与智能系统、网络软件工程.承担过多项国家级和省部级重点科研项目，获湖北省自然科学优秀学术论文一等奖1项、二等奖3项、三等奖5项；获部级教学成果一等奖1项，湖北省科技进步一等奖2项，自然科学奖二等奖1项，国家重点科技攻关优秀成果奖1项.发表学术论文100余篇，其中50余篇被SCI、EI、ISTP检索收录.
赵先明,男,1984年生，硕士研究生,主要研究方向为网络软件工程.
夏红霞，女，1960年生，教授，硕士生导师，主要研究方向为数据库应用技术、专家系统、软件工程.主持或参加了多项科研项目，参加“九五”国家重点攻关项目混凝土安全性专家系统，2004获湖北省科技进步一等奖.发表学术论文40篇. 获湖北省自然科学优秀学术论文二等奖1项、三等奖1项，获武汉市自然科学优秀学术论文二等奖1项、三等奖2 次.
更新日期/Last Update:
2011-05-19