密集MANET 下MPR 的改进蚁群优化算法研究

赵启超，杨余旺，谢勇盛，汤小芳，李 操

（南京理工大学计算机科学与工程学院，南京 210094）

0 概述

移动自组网（Mobile Ad-hoc Network，MANet）是由一系列对等通信节点组成的分散式网络［1］，该网络无中心控制节点且节点间相互独立，旨在不依赖预先存在的基础架构下提供网络无线服务［2］。随着网络设备的不断增加，自组网已经延伸至各行各业，而人群的聚集与流动性通常给自组网带来巨大的挑战，密集型移动自组网中由于节点数目庞大且分组数量繁多，易导致网络拥塞甚至瘫痪，因此研究适用于密集流动型复杂场景的路由协议对于改善网络性能具有重要的意义。

优化链路状态（Optimized Link State Routing，OLSR）协议中多点中继（Multi-Point Relay，MPR）机制［3］有效抑制了消息开销，每个节点在接收到消息时都会重传消息，而MPR 机制中的消息仅由被选为MPR 的节点转发，实现了控制消息数量的优化，使得OLSR 协议在密集MANET 中具有很好的应用。传统的MPR 机制使用贪心算法，二跳节点覆盖数多的邻居被优先选为MPR，这导致MPR 集合存在较大冗余且网络越密集发生的概率越大。

蚁群优化（Ant Colony Optimization，ACO）算法［4］是一种来自于模仿蚂蚁觅食而得到的群体智能优化启发式算法［5-7］。该算法的优势在于其搜索的随机性，而传统贪心算法没有进行全局检测，仅限于当前最优。ACO 算法利用随机概率选择下一路径，但由于信息素和权值等因素的影响，导致某一路径的选择概率大幅增加，当概率增加到1 时，蚁群算法退化为传统贪心算法，将会陷入某一局部最优解。启发式蚁群算法在贪心算法基础上有所改进，但仍存在迭代时间过长而容易陷入局部最优解等缺陷［8-9］。……