第6卷第2期 智能系统学报 Vol.6 No.2 2011年4月 CAAI Transactions on Intelligent Systems Apr.2011 doi:10.3969/i.issn.1673-4785.2011.02.012 求解最小MPR集的蚁群算法与仿真 钟珞，赵先明，夏红霞 (武汉理工大学计算机科学与技术学院，湖北武汉430070)】 摘要：在分析利用贪心策略启发式算法求解最小MPR集的缺陷基础上，引入蚁群算法对最小MPR集进行求解.首 先定义了节点及其出度和入度，并根据节点的出度和入度限制，给出了求解最小MPR集的蚁群算法.然后，对蚁群算 法的3种模型Ant-Cycle、Ant-Quantity和Ant-Density加以改进，并对这3种改进模型的收敛性进行分析与实验.实验 采用了圆形分布和理想均匀分布2种拓扑结构，前者实验结果表明At-Cycle模型的收敛速度较快，后者结果表明 Ant-Cycle模型和Ant-Density模型各有优势.因此，最小MPR集的蚁群算法的模型选择需依据拓扑结构确定.最后， 使用OPNET基于该算法对数据链的点对多点的点名呼叫工作方式进行模拟仿真，选择的统计量显示了节点的连通 性和数据一致性，验证了该算法的合理性. 关键词：最小MPR集；蚁群算法；OLSR协议；OPNET 中图分类号：TP393文献标识码：A文章编号：16734785(2011)02-016606 An ant colony algorithm and simulation for solving minimum MPR sets ZHONG Luo,ZHAO Xianming,XIA Hongxia (Department of Computer Science and Technology,Wuhan University of Technology,Wuhan 430070,China) 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 in-degrees were defined,and in ac- cordance with the out and in-degree 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 Ant-Cycle,Ant-Quantity, and Ant-Density 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 Ant-Cycle model was faster in convergence speed;the latter results showed that the Ant-Cycle and Ant-Density 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 simula- tion.It adopted the data link's point-to-multipoint calling mode.The selected statistics show connectivity and data consistency among the nodes,which means that the algorithm is reasonable. Keywords:minimum MPR set;ant colony algorithm;OLSR (optimized link state routing protocol);OPNET 移动Ad-hoc网络，又称为MANET(mobile ad hoc结构不断变化，需要对信息及时更新.该协议使用HEL, network),具有自创造、自组织和自管理的特点.该LO和TC消息发现链路状态信息，然后通过MANET广 网络不依赖于任何固定的网络设施，而是通过移动节 播链路状态信息，使网络信息及时更新12].每个节点都 点间的相互协作来进行网络互联.OLSR协议即最优链 维护和不断更新一系列的数据表.这些数据表都是以周 路状态路由协议，是MANET工作组提出的一种先应式 期发送的控制信息的内容为依据的，在某节点发起数据 表驱动的路由协议.MANET因其节点的移动性使得拓扑 发送请求时，它只需要查找自己的路由表，找到路径进行 数据发送3) 收稿日期：2010-0605. 基金项目：国家自然科学基金资助项目(61003130)：教育部高校行动 OLSR协议是用控制信息去感知和建立无线自 计划资助项目(2004X①03). 组网，同时用一种优化的方式去传递拓扑信息45， 通信作者：赵先明.E-mail:freshzhaoxm@163.com 在该协议中关键的概念就是MPR.MPR节点承担在