第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节点承担在
第2期 钟珞，等：求解最小MPR集的蚁群算法与仿真 ·167 全网中通告链路状态的责任，为了计算到目的节点 MPR为{b,c,e},而实际上节点A的最小MPR集合 的最短路由，只需在链路状态信息中包含MPR节点 为{b,d}.可见，该算法可以在较短时间里找到一个 与其MS(MPR selector)节点之间的链路状态信息就 MPR集，但找到的解可能不是最优解， 足够了.那么要解决的一个关键问题就是求解节点 的最小MPR集.A.Qayyum等人证明了求解最小 MPR问题是一个NP完全问题6 MANET中，远距离节点之间的网络互连是通过 多跳技术实现的.互连拓扑动态变化的特性，给该领 域带来了许多难题.因此，路由问题是MANET技术 的关键问题，也是它能够有效应用而必须解决的问 题.因为无线网络比较灵活并且扩展性好，这些特性 易导致网络拓扑发生动态变化，这样它与物理、链 4 路、网络层之间相互影响的问题也随之而来.虽然路 由算法有很多，但是基本上每种路由都有一定的缺 图1基于贪心策略的启发式算法求MPR集 陷.此时，必须基于网络的需求，引入蚁群算法来完 Fig.1 Using heuristic algorithm to seek MPR set 成对路由协议的改善。 蚁群算法(ant colony optimization,ACO）是一种 用来在图中寻找优化路径的机率型算法)，它通过 个体之间的信息交流与相互协作最终找到最优解， 蚁群算法是一种模拟进化算法，该方法具有正反馈、 分布式计算和富于建设性的贪婪启发式搜索的特 点，如蚂蚁活动范围、路径的选择、路径上信息量的 更新以及蚂蚁之间的协同.由于蚁群中多个个体的 运动是随机的，当群体规模较大时，要找出一条较好 的路径需要较长的搜索时间.虽然人们已经针对不 同的具体问题提出了许多不同类型的改进蚁群算 法，但是这些算法模型的普适性不强，并且蚁群算法 图2实验中的拓扑结构(I)】 也不能直接应用于具体的优化问题，还必须加以改 Fig.2 Topology graph(I in experiments 进和限制. ●OOO0OO 经过比较，本文选择蚁群算法来改进路由协议 (optimized link state routing protocol,OLSR)MPR OOOO O (multipoint relays)技术，并用OPNET仿真工具进行 000O00O 仿真验证， O 1节点的最小MPR集求解 0 ○O○ OOO ○○○○○O 网络中各节点独立地计算自己的MPR集.如果 0 节点的MPR集满足如下条件： 000O0O0 1)节点与MPR之间必须是双向对称链路： 图3实验中的拓扑结构（Ⅱ） 2)节点所发送的分组通过MPR中继，能够到 Fig.3 Topology graph(II )in experiments 达所有的两跳邻居节点： 然后最小化MPR数量，得到节点的最小MPR 赵健等人通过对原MPR集合中节点的再次排 集.那么，MPR就能有效地进行TC分组的转发 序判断，除去了冗余节点，从而得到最小MPR集]； 图1是根据A.Qayyum等人的算法计算节点A 张信明等人采用遗传算法寻找最优MPR9,提出了 的最小MPR集的拓扑示意图（内圆里面是A节点的 一种基于遗传算法的具有收敛性的新算法，但若群 一跳节点，矩形框代表二跳节点)，可以得出最小 体规模太小时，算法的优化性能不会很好，而且容易
·168 智能系统学报 第6卷 陷入局部最优解 r(t+n)=（1-p)·T(t)+△r(t), 2基于蚁群算法求解最小MPR集 △r,()=∑△) 使用图G=(V,E,W)描述本算法，其中V= 式中：p是信息素挥发参数，其中0 Y(MPR)nodell △r(t)= N rQ·S,第k只蚂蚁时间t和t+1之间经过路径)： 移动m只蚂蚁并依据公 0,其地， 式2)、(3)更新路径信息 在Ant-Density模型中， △r(t)= N=N 「Q,若第k只蚂蚁在时间t和t+1之间经过路径()： L0,其他. MPR覆盖 Y 所有二跳 MINMPR 这3种模型各有优劣，应根据具体的问题来选 节点 择相应的模型.假设蚂蚁的数量为m,节点的数量为 结束 n,循环次数为N。,那么当n足够大时，该蚁群算法 Max(SCIFi) MRP)-nodeli] 的时间复杂度仍然为T(n)=O(N。·n2·m).与基 于贪心策略的启发式算法相比，该算法的收敛速度 图4基于蚊群算法求解最小MPR集的流程图 Fig.4 The flow chart of solving minimal MPR set 较慢Io,但能保证所求MPR集合是最小的. 说明： 在Matlab实验中，采用2种拓扑结构进行实 1)对每个蚂蚁k(k=1,2,…,m)按概率p(t) 验.第1种拓扑结构为圆形分布，即采取与A. 移至下一符合条件的节点方这里的概率P(t)为 Qayyum等人相同的拓扑结构（如图2所示）：共有 50个节点，求节点S的最小MPR集.本实验中，设 [Ty(t)][wa(t)]8 P(t)= (allowed, 定m=20p=0.1、Q=1.2,经过多次实验确定参数 ed =1.5B=2.5(效果比较好)，分别用改进后的蚁 else. 群算法的3种模型进行实验，得出的收敛曲线如图 式中：allowed:表示蚂蚁k下一步允许走过的节点 5所示.第2种拓扑结构是理想的均匀分布（如图3 的集合；α为信息启发因子；B为期望启发因子 所示)，求黑色节点的最小MPR集，在实验中，同样 2)更新路径上的信息强度.为了避免残留信息 设定m=20p=0.1、Q=1.2、a=1.5、B=2.5,再分 素过多引起残留信息淹没启发信息，在每只蚂蚁走 别用改进后的蚁群算法的3种模型进行实验，得出 完n个节点后，要对各路径上的信息量作更新： 的收敛曲线如图6所示
第2期 钟珞，等：求解最小MPR集的蚁群算法与仿真 ·169 100 100 100 95 95 95 90 90 90 函85 里5 的 85 80 80F 80 5 六 小3 75 MMni 20 406080100 00 20 4060 80100 100 406080100 t/s t/s (a)Ant-Cycle茯型 (b)Ant-Quantity模型 (c)Ant-Density模型 图5 采用拓扑结构(I)的3种模型的收敛曲线 Fig.5 The convergence curves of three types of models based on topology graph(I 130 130 130 125 9 120 115 I15 115 10 110 105 年 105 105 100 100 95 95 90 90 ww % 85 中 50 100 800 50 100 80 50 100 t/s tis (a)Ant-Cycle模型 (b)Ant-Quantity模型 (c)Ant-Density模型 图6采用拓扑结构（Ⅱ）的3种模型收敛曲线 Fig.6 The convergence curves of three types of models based on topology graph(II) 由图5可知Ant-Cycle模型的收敛速度较快，那 2)被点名的节点收到点名包后，启动计时器并 么在第1种拓扑结构中采用Ant-Cycle模型较好.由 逐个从数据包队列中取出数据包并发给主节点；如 图6可知Ant-Cycle模型和Ant-Density模型的收敛 果数据包发送完毕，则向主节点回复完毕信息， 效果大致相似，第2种拓扑结构可以采用其中任一 3)主节点接到数据完毕信息，立即点名下个节点 种模型.从实验中可知，可根据具体的问题来采选择 基于本文需求，设计了如图7所示的仿真节点 模型.但该算法是以收敛速度为代价来提高正确率； 模型，其中包括4个基本功能：产生包、处理包、接 在时间复杂度上要高于贪心策略的启发式算法。 收/发送包和定时控制（图7中用实线框分开） OPNET仿真 在所设计的节点模型中设计了多个进程模块， 4 此处仅以pk_deal进程模块的设计为例进行说明. 4.1模型设计 在pk_deal模块中，强制状态有：from_src、from_ra 采用OPNET工具，并设计点对多点的点名呼叫 dio、init、MPR,非强制状态：idle.其中MPR状态包含 工作方式的仿真模型，通过仿真结果说明数据连通 了以上蚁群算法，主要是计算节点的最小MPR集 性、数据一致性等来验证以所提算法的可行性 (选择Ant-Cycle模型)，便于后面数据包的发送.带 点对多点的点名呼叫工作方式的设计 箭头的线表示状态转移方向，其旁边括号内的字符 1)主节点依次给网络中的所有节点发送点名包， 串表示状态转移条件.如图8所示
·170 智能系统学报 第6卷 续发送点名包.图9为节点A的点名包和数据包发送 tokeh src 情况（横坐标表示时间，纵坐标表示每秒发送数据包 数量).图中的前11个波峰是发送点名包，末尾波峰 表示给自己点名，并发送数据包，故波峰较高。 pk oueue 图10为圆形分布结构的所有节点被点名后的 发送数据包情况.其中圆点是发送点名包标记，较低 波形代表节点A发送点名包.图中共有12个数据发 送波形，这就证明了节点之间是连通的.图11则为 d!pk 方形分布的所有节点被点名后的发送数据包情况， 亦能证明节点之间是连通的 米 函函 end Ink!end Ink2 end Ink3 end Inkl end Ink2 end_Ink3 图7节点模型示意 Fig.7 Schematic diagram of the node model /From sre (SRC_PK_ARRIVAL) MPR (PK MPR ARRIV 10 20 30 40 50 60 init idle -default 图10点名呼叫工作方式波形（圆形分布） (RADIO PK ARRIVAL) Fig.10 Waveforms of receiving and sending data (cir- cular） form \radio 图8 pk_deal进程模块的设计 Fig.8 Design of pk_deal module 4.2仿真结果 3 6 78 仿真的网络拓扑结构有2种：圆形分布（图1） 和方形分布（类似拓扑结构Ⅱ），需要调整节点的发 射功率以及节点之间距离以区分一跳节点和二跳节 点.节点A能够计算自己的MPR集合，然后根据集 10 20 合中的MPR节点转发信息， 30 40 4 图11点名呼叫工作方式波形（方形分布） Fig.11 Waveforms of receiving and sending data (square） 图12为节点1被点名后(2种拓扑结构的效果 类似)，发送数据包过程中其队列中数据包变化情 况.队列中数据包在点名之前都在累积，当被点名 后，就会发送队列中的所有数据包.这证明了数据的 时间一致性 10 20 30 40 50 60 仿真结果表明了本文给出的基于蚁群算法求最 图9节点A的发包波形 小MPR集是可行的.由于整个仿真过程的数据量较 Fig.9 Waveforms of node A sending data 少，整个网络也是处在理想状态下，所以延迟很小； 设置整个仿真时间为558，在7s之前节点A计 如果对于实际的MANET网络，其拓扑结构是经常 算自己的最小MPR集，从7s开始发送点名数据包， 发生变化的，因此在拓扑易变、高速和高数据流通量 等待被点名节点的信息回复，接收到回复信息之后继 的情况下，要提高网络性能不仅要选择路由协议，还
第2期 钟路等：求解最小MPR集的蚁群算法与仿真 171。 要改进算法和考虑路由层的QoS. Secure Network Protocols 1st IEEE ICNP Workshop,[S 1],2005::55-60. 2.5f [6]QAYYUM A,VIEMOT L,LAOUITI A.Multipoint relaying 10.0 for flooding broadcast messages in mobile wireless networks [C]]//The 35th Hawaii International Conference on System 7.5 Sciences(HICSS 2002)).Hawai,2002:3866-3875. ⑦]段海滨著.蚁群算法原理及其应用[M],北京：科学出 据包数 版社，2005：1-447. [⑧图，赵健，孙俊锁.OLSR路由协议的改进及其NS2仿真分 25 析[].计算机仿真，2008,25(1))：161-163. ZHAO Jian,SUN Junsuo.Simulation and analysis of an im- 10 20 304050 60 proved OISR routing protocol based on NS2[J].Computer t's Simulation,2008,25(1):161-163. 图12节点1被点名的数据包统计 [9张信明，曾依灵，干国政，陈国良.用遗传算法寻找0LISR协议 Fig.12 Statistics of the called node Is data packets 的最小PR集[J]]软件学报，2006,17(4)：92-98 ZHANG Xinming ZENG Yilig,GAO Guozheng,et al.Find 5结束语 the minimum MPR set in OLSR protool with genetic algorithms [Jourmal of Software,206,17(4))3932-98. 求最小MPR集是一个NP完全问题.本文利用 [0夏红霞，宋华珠，钟珞.算法设计与分析[M]]湖北武 蚁群算法对其进行求解并加以改进，通过对蚁群算 汉武汉大学出版社，2007：1-3441. 法中不同模型的分析、比较实验，可以得出拓扑结构 [小骆光明等，数据链-信息系统连接武器系统的捷径 (I)选择Ant-Cycle模型的蚁群算法具有较好的收 01.北凉：国防工业出版社，2008：8：1-356. 作者简介： 敛性，能在规定的时间内找到最小MPR集；拓扑结 钟路，男，1957年生，教授，博士生 构(II),可以选择Ant-Cyclet模型或者Ant-Density模 导师，武汉理工大学计算机学院院长， 型.Malab仿真结果表明了该算法的合理性与可行 CCF高级会员.武汉计算机软件工程学 性：进一步，本文利用OPNET在数据链点对多点的 会副理事长，湖北省计算机学会副理事 工作方式上对该算法进行仿真实验，仿真结果验证 长.主要研究方向为智能技术与智能系 统、网络软件工程.承担过多项国家级 了该算法的正确性.在下一步的研究中，将对该算法 和省部级重点科研项目，获湖北省自 进行优化，在保证正确求解最小MPR集的前提下， 然科学优秀学术论文一等奖1项、二等奖3项、三等奖5 减少时间上的开销，从而降低时间复杂度：同时在 项：获部级教学成果一等奖1项，湖北省科技进步一等奖2 OPNET仿真中加入分布式交互仿真策略，以促进仿 项，自然科学奖二等奖1项，国家重点科技攻关优秀成果 真间的互操作和可重用性。 奖1项.发表学术论文100余篇，其中50余篇被SCI、EI、 ISTP检索收录， 参考文献： [1]].HIDEHSA N.SATOSHI K.ABBAS J.et al.A dynamic a- nomaly detection scheme for AODV-based mobile ad hoc 赵先明，男，1984年生，硕士研究 networks[J].IEEE Transactions on Vehicular Technology, 生，主要研究方向为网络软件工程. 2009,58(⑤)：2471-2481. [2]]ASOKAN R.A review of quality of sService(QS))routing protools for mobile Ad hoc networks[C]//ICWCSC 2010, Chennai,2010:16. 3]川谢飞，张信明，郭嘉丰，陈国良.延迟主导的自适应移动 Ad hoc网络路由协议[J刀.软件学报，2005,16(9))： 1661-1667 夏红霞，女，1960年生，教授，硕士生 Xie Fei,Zhang Xinming,Guo Jiafeng,et al.A delay orien- 导师，主要研究方向为数据库应用技术、 ted adaptive routing protocol for mobile Ad hoc networks 专家系统、软件工程主持或参加了多项 [I:.Journal of Software,2005,16(9)):1661-1667.. 科研项目，参加”九五"国家重点攻关项目 [4]YONG Bai,LAN Chen.Extended multicast optimized link 混凝土安全性专家系统，2004获湖北省科 state routing protool in MANETs with asymmetric links 技进步一等奖.发表学术论文40篇.获湖 [C]]//GLOBECOM-IEEE Global Telecommunications Con- 北省自然科学优秀学术论文二等奖1项 ference.Washington,DC,2007:.1312-1317. 三等奖1项，获武汉市自然科学优秀学术论文二等奖1项、三等 5]WANG M.LAMORT L,MASON P,et al.An effective in- 奖2次. trusion detection approach for OLSR MANET protool[C]/
3 0 [1] HIDEHSA N,SATOSHI K,ABBAS J,et al. A dynamic anomaly detection scheme for AODV-based mobile ad hoc networks[J]. IEEE Transactions on Vehicular Technology, 2009,58(5) : 2471-2481. Secure Network Protocols 1st IEEE ICNP Workshop,[S. 1.] ,2005: 55-60. 赵先明,男,1984年生,硕士研究 生,主要研究方向为网络软件工程. 5] WANG M,LAMORT L,MASON P,et al. An effective intrusion detection approach for OLSR MANET protool[ C] // [2] ASOKAN R. A review of quality of sService(QS) routing protools for mobile Ad hoc networks[ C]//ICWCSC 2010, Chennai,2010: 16. [4] YONG Bai,LAN Chen. Extended multicast optimized link state routing protool in MANETs with asymmetric links [C] //GLOBECOM-IEEE Global Telecommunications Conference. Washington,DC,2007: 1312-1317. 第2期 [7] 段海滨著.蚁群算法原理及其应用[M] .北京: 科学出 版社,2005: 1-447. 钟路,男,1957年生,教授,博士生 导师,武汉理工大学计算机学院院长, CCF高级会员.武汉计算机软件工程学 会副理事长,湖北省计算机学会副理事 长.主要研究方向为智能技术与智能系 统、网络软件工程.承担过多项国家级 和省部级重点科研项目,获湖北省自 要改进算法和考虑路由层的QoS. 作者简介: 3] 谢飞,张信明,郭嘉丰,陈国良.延迟主导的自适应移动 Ad hoc 网络路由协议[J].软件学报,2005,16(9) : 1661-1667 6 0 2 .5 7.5 5.0 2.5 2 0 [11] 骆光明等.数据链-信息系统连接武器系统的捷径 [M] .北京: 国防工业出版社,2008: 1-356. 夏红霞,女,1960年生,教授,硕士生 导师,主要研究方向为数据库应用技术、 专家系统、软件工程.主持或参加了多项 科研项目,参加"九五"国家重点攻关项目 混凝土安全性专家系统,2004获湖北省科 技进步一等奖.发表学术论文40篇.获湖 北省自然科学优秀学术论文二等奖1项 三等奖1项,获武汉市自然科学优秀学术论文二等奖1项、三等 奖2次. [9] 张信明,曾依灵,干国政,陈国良.用遗传算法寻找OLISR 协议 的最小MPR集[J]].软件学报,2006,17(4): 92-938 ZHANG Xinming,ZENG Yilig,GAO Guozheng,et al. Find the minimum MPR set in OLSR protool with genetic algorithms [J]. Jourmal of Software,206,17(4) :932-98. t's 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) :1661-1667. 参考文献: ZHAO Jian,SUN Junsuo. Simulation and analysis of an improved OISR routing protocol based on NS2[J]. Computer Simulation,2008,25(1) : 161-163. 5 0 图12节点1被点名的数据包统计 [8] 赵健,孙俊锁.OLSR路由协议的改进及其NS2仿真分 析[J] .计算机仿真,2008,25(1) : 161-163. 钟珞,等: 求解最小MPR集的蚁群算法与仿真 10.0 求最小MPR 集是一个NP完全问题.本文利用 蚁群算法对其进行求解并加以改进,通过对蚁群算 法中不同模型的分析、比较实验,可以得出拓扑结构 (I) 选择 Ant-Cycle模型的蚁群算法具有较好的收 敛性,能在规定的时间内找到最小 MPR 集;拓扑结 构(Ⅱ) 可以选择 Ant-Cycle模型或者 Ant-Density 模 型.Malab仿真结果表明了该算法的合理性与可行 性;进一步,本文利用OPNET在数据链点对多点的 工作方式上对该算法进行仿真实验,仿真结果验证 了该算法的正确性.在下一步的研究中,将对该算法 进行优化,在保证正确求解最小MPR 集的前提下, 减少时间上的开销,从而降低时间复杂度;同时在 OPNET仿真中加入分布式交互仿真策略,以促进仿 真间的互操作和可重用性. [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) . Hawai,2002: 3866-3875. [10] 夏红霞,宋华珠,钟珞.算法设计与分析[M] 湖北武 汉:武汉大学出版社,2007: 1-344. 171。 0 4 0 Fig.12 Statistics of the called node 1s data packets 数据包数量 然科学优秀学术论文一等奖1 项、二等奖3项、三等奖5 项;获部级教学成果一等奖1项,湖北省科技进步一等奖2 项,自然科学奖二等奖1项,国家重点科技攻关优秀成果 奖1项.发表学术论文100余篇,其中50余篇被SCI、EI、 ISTP检索收录
