第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节点的 一种基于遗传算法的具有收敛性的新算法，但若群 一跳节点，矩形框代表二跳节点)，可以得出最小 体规模太小时，算法的优化性能不会很好，而且容易