基于混合粒子群算法的ad hoc路由协议研究

《基于混合粒子群算法的ad hoc路由协议研究》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、http://www.paper.edu.cn基于混合粒子群算法的AdHoc路由协议研究1122陈玮，饶妮妮，廖瑞华，王炜华1电子科技大学生命科学与技术学院，成都（610054）2空军装备研究院通信所，北京（100085）E-mail:chenweifly@sohu.com摘要:针对当前AdHoc路由协议在动态变化迅速的自组网中存在时延过大问题，本文引入粒子群优化算法，结合遗传算法对其改进，形成了适用于路由问题的混合粒子群算法。研究基于混合粒子群算法的路由协议，在网络仿真软件OPNET上将其实现

2、，并进行仿真实验。与比较成熟的AdHoc按需路由协议AODV的仿真结果对比表明，新协议减小了网络的端到端时延，更适合于动态变化大的AdHoc网络。关键词：AdHoc网络；路由协议；混合粒子群算法；AODV；OPNET中图分类号：TP3931．引言自组网（AdHoc，WirelessNetworkWithoutInfrastructure）是一种能够临时快速自动组[1]网的移动通信技术。它不需要预设的网络基础设施，具有很强的抗毁性，故被广泛应用于[2]各种临时通信场合。路由协议是当前自组网技术的研

3、究热点，目前已有多种路由协议草案被提出。按照路由建立方式分为主动路由协议和按需路由协议，其中后者适用于大规模，网[3]络拓扑变化迅速的环境。但是，由于它们大多采用洪泛机制，如AODV，使网络性能受到制约。随着AdHoc技术的迅速发展，迫切需要能使网络性能更加优越的路由算法。粒子群算法(ParticleSwarmOptimization,PSO)是一种基于群智能的迭代优化计算技术，[4][5]它最早由Kennedy和Eberhart于1995年提出，其基本思想源于对鸟群捕食行为的研究。系统初始化为

4、一群随机粒子(随机解)，然后通过迭代找到最优解。在每一次迭代中，粒子通过跟踪全局极值和局部极值来更新自己，使粒子始终跟随最优粒子运动。PSO流程简单，[6][7][8][9]参数简洁，被广泛应用于各种目标优化问题，如决策调度，图像配准，天线阵列优化[10][11]等。对于路径优化问题，PSO已被用来解决TSP，车辆路由选择和AdHoc网络QoS[12][13][14]路由。本文结合遗传算法，对PSO进行改进，提出适用于路由问题的混合粒子群算法(HPSO，HybridParticleSwarmOp

5、timization)；然后按照按需路由协议机制，设计了一种基于HPSO的AdHoc路由协议框架。在OPNET网络仿真软件上将其实现后进行系统级仿真实验，同时在相同网络环境下与AODV协议进行比较。2．AdHoc路由问题的数学描述把网络看成一个赋权无向图G=(V,E)，其中V是G中所有节点的集合；E为G中任意两相邻节点x,y之间链路的集合。对于E中每条链路exy=(,)，x,yV∈，均有某种非负加权函数表示其属性，如De()描述链路的延时，本文选择延时De()作为链路的属性。AdHoc路由问题的

6、数学描述为：已知源节点sV∈和目的节点dV∈，寻找路径Psd(,)，使经过该路径的数据包延时∑D(e(x,y))达到最小。e(x,y)∈P(s,d)3．基本粒子群算法（PSO）[15]基本粒子群算法（PSO）是基于群体和适应度概念，通过“群集智能”求解目标函数f(x)-1-http://www.paper.edu.cn的最优值问题。该算法能迅速找到某个或某些x，让f(x)达到或接近最优值。其中x是N维向量，当N为1时，x为标量。算法的执行框架如下：1）根据优化目标函数f(x)，在自变量x的取值范

7、围内随机产生n个x值作为初始粒子，同时随机产生n个初始速度对应于各粒子。2）根据当前的位置和速度，依照下面公式更新每个粒子的速度和位置。v=+cvcpbest()−+xcgbest()−x(1)k+10k1kk2kkxxv=+(2)kk++11k其中，k代表迭代次数，v是粒子的速度向量，x是当前粒子的位置，pbest表kkk示粒子本身所找到的最优解位置，gbestk为整个群体目前找到的最优解位置。c0是惯性权重，促进粒子向新空间搜索；c，c为加速因子，分别表示粒子向局部极值和全12局极值的趋向程

8、度。3）计算各个粒子新位置的目标函数值。对每个粒子，若新值优于原来的个体极值pbest，k设置新值为pbest，否则pbest不变。再从各个粒子的个体极值里选出最优的一个作kk为全局极值gbest。k4）检查gbest是否达到要求或迭代次数是否已达最大值。若条件满足，输出gbest及最kk优目标函数值；否则返回步骤2）继续迭代。PSO主要处理连续性优化问题，通过发挥粒子群体的功能使优化函数很快达到最优值。4．适用于AdHoc网络环境的混合粒子群算法(HPSO)设计基本粒子群算法适用于连续性优化问