基于混合粒子群算法Ad Hoc路由协议研究.pdf

基于混合粒子群算法的Ad Hoc 路由协议研究 1 1 2 2 陈玮 ，饶妮妮 ，廖瑞华 ，王炜华 1 电子科技大学生命科学与技术学院，成都（610054 ） 2 空军装备研究院通信所， 北京（100085 ） E-mail: chenweifly@ 摘 要: 针对当前Ad Hoc 路由协议在动态变化迅速的自组网中存在时延过大问题，本文引 入粒子群优化算法，结合遗传算法对其改进，形成了适用于路由问题的混合粒子群算法。研 究基于混合粒子群算法的路由协议，在网络仿真软件OPNET 上将其实现，并进行仿真实验。 与比较成熟的Ad Hoc 按需路由协议AODV 的仿真结果对比表明，新协议减小了网络的端到 端时延，更适合于动态变化大的Ad Hoc 网络。 关键词：Ad Hoc 网络；路由协议；混合粒子群算法；AODV ；OPNET 中图分类号：TP393 1．引言 自组网（Ad Hoc ，Wireless Network Without Infrastructure ）是一种能够临时快速自动组 网的移动通信技术[1] 。它不需要预设的网络基础设施，具有很强的抗毁性，故被广泛应用于 各种临时通信场合。路由协议是当前自组网技术的研究热点[2]，目前已有多种路由协议草案 被提出。按照路由建立方式分为主动路由协议和按需路由协议，其中后者适用于大规模，网 络拓扑变化迅速的环境。但是，由于它们大多采用洪泛机制，如 AODV[3]，使网络性能受到 制约。随着 Ad Hoc 技术的迅速发展，迫切需要能使网络性能更加优越的路由算法。 粒子群算法(Particle Swarm Optimization, PSO)是一种基于群智能的迭代优化计算技术， 它最早由 Kennedy 和 Eberhart 于 1995 年提出 [4][5] ，其基本思想源于对鸟群捕食行为的研究。 系统初始化为一群随机粒子(随机解) ，然后通过迭代找到最优解。在每一次迭代中，粒子通 过跟踪全局极值和局部极值来更新自己，使粒子始终跟随最优粒子运动。PSO 流程简单， [6] [7] [8] [9] 参数简洁，被广泛应用于各种目标优化问题 ，如决策调度 ，图像配准 ，天线阵列优化 等。对于路径优化问题，PSO 已被用来解决 TSP[10]，车辆路由选择[11]和 Ad Hoc 网络 QoS [12][13][14] 路由 。 本文结合遗传算法，对PSO进行改进，提出适用于路由问题的混合粒子群算法(HPSO， Hybrid Particle Swarm Optimization) ；然后按照按需路由协议机制，设计了一种基于HPSO 的 Ad Hoc路由协议框架。在OPNET 网络仿真软件上将其实现后进行系统级仿真实验，同时在 相同网络环境下与AODV协议进行比较。 2 ．Ad Hoc路由问题的数学描述 把网络看成一个赋权无向图G= (V, E) ，其中 V 是 G 中所有节点的集合；E 为 G 中任 意两相邻节点x, y 之间链路的集合。对于 E 中每条链路e (x, y) ，x , y ∈V ，均有某种非 负加权函数表示其属性，如D (e) 描述链路的延时，本文选择延时D (e) 作为链路的属性。 Ad Hoc 路由问题的数学描述为：已知源节点s ∈V 和目的节点d ∈V ，寻找路径P (s ,d ) ， 使经过该路径的数据包延时 ∑D (e(x , y )) 达到最小。 e(x ,y )∈P (s ,d ) 3 ．基本粒子群算法（PSO ） 基本粒子群算法 （PSO ）是基于群体和适应度概念，通过“群集智能”[15]