公开/公告号CN105430706A
专利类型发明专利
公开/公告日2016-03-23
原文格式PDF
申请/专利号CN201510737551.0
申请日2015-11-03
分类号H04W40/04(20090101);H04W40/10(20090101);H04W84/18(20090101);
代理机构36122 南昌市平凡知识产权代理事务所;
代理人姚伯川
地址 330096 江西省南昌市民营科技园民强路88号
入库时间 2023-12-18 15:12:07
法律状态公告日
法律状态信息
法律状态
2018-11-27
授权
授权
2016-04-20
实质审查的生效 IPC(主分类):H04W40/04 申请日:20151103
实质审查的生效
2016-03-23
公开
公开
技术领域
本发明涉及一种基于改进粒子群算法的无线传感网络路由优化方法,属无 线传感器路由方法技术领域。
背景技术
改进粒子群算法的无线传感网络路由优化方法建立在粒子群算法和路由算 法基础上,用关系矩阵作为粒子群算法的编码方式,来处理路由优化问题,也 就是粒子的位置是一个含有整个网络的拓扑结构信息的关系矩阵;并利用遗传 算法的交叉和变异机制的更新操作,从而实现目标的优化求解。但是,路由优 化问题,需要常常克服其方法所带来的编码复杂、对粒子群算法改动较大、实 现复杂等缺点。因此设计一种编码方法,能够无须对粒子群算法做出较大改动。 能够减少冗余空间的产生和冗余搜索,提高方法实时性,是粒子群算法的无线 传感网的路由算法的真正关键。
发明内容
本发明的目的是,克服现有技术存在的上述缺陷,提供一种基于改进粒子 群算法的无线传感网络路由优化方法,引入遗传算法的交叉和变异机制全局收 敛搜索,提高方法的实时性和稳定性。
实现本发明目的的技术方案是,本发明一种基于改进粒子群算法的无线传 感网络路由优化方法使用一种含有整个网络拓扑结构信息的关系矩阵作为粒子 群算法的编码方式,用来处理路由优化问题;并应用遗传算法的交叉和变异机 制实现全局收敛搜索;所述方法包括以下步骤:
(1)初始化参数:设定种群的规模M,网络节点数n,惯性权重w,以及最 大的迭代次数tmax,确定路由节点的基本信息:有效传输距离、初始能量及剩余 能量。
(2)初始化种群:对每个粒子i得到一个随机的初始位置Xi以及一个随机的 初始速度Vi;粒子位置表示为
(3)对新位置按照路由策略计算位置的适应值:QoS约束单播路由问题的 网络拓扑图用无向连通图G=(V,E)表示,其中,V为网络中所有网络节点集合, E为任意两相邻节点i,j之间的链路边eij集合,i,j=1,2,…,n,n表示网络的节点 数。使用罚函数Q(Pst)将约束单播路由优化问题转化为无约束优化问题进行求解:
(5)对于粒子群所有个体,根据关系矩阵编码方式,计算每个粒子个体的 位置和速度,对每个粒子进行变异操作,然后在此基础上对粒子进行交叉操作;
(5.1)设网络中的节点数是n,用具有大于或等于零的元素的二维关系矩阵
(5.2)变异操作:在每次迭代中,为了保持样本的多样性,根据速度更新公 式
(5.3)交叉操作:随机选取全局最优路由中的某个区间片段[a,b]进行交叉; 即从路由请求Rg中选择片段Rc={va,…,vb}插入到路由请求Rj中vji后面,并且vji离 va节点距离最小;然后在Rj原路径中删除节点va,…,vb,同时更新路由标识向量 Xj;
(5.4)根据位置更新公式计算下一代的位置。
(6)重新评价各粒子的适应度值,更新各个粒子的历史最优解,更新种群 的全局最优解;如果新位置的适应值比当前局部最好解的适应值还要小,则用 新的位置更新当前的局部最好解;假若有粒子的局部最优解优于当前的全局最 优解和其他粒子的局部最优解,则用此局部最优解更新当前的全局最优解。
(7)停机条件判断:如果当前迭代的次数等于最大迭代次数,转步骤(8), 否则转步骤(5)。
(8)输出求得的最好解路径。
所述步骤(3)中,根据评价函数对每一个粒子i进行评价时,将优化目标 函数可以直接定义算法的适应度函数,其结果作为粒子i的适应度
所述步骤(5.2)中,为了保持样本的多样性,进行变异,速度更新公式
所述步骤(5.3)中,为了跟踪全局最佳粒子,随机选取全局最优路由中的 某个区间片段[a,b]进行交叉;即从Rg中选择片段Rc={va,…,vb}插入到Rj中vji后 面,并且vji离va节点距离最小。然后在Rj原路径中删除节点va,…,vb,同时需更 新路由标识向量Xj。
本发明的有益效果是,本发明结构简单,引入了遗传算法的交叉和变异机 制全局收敛搜索,最终实现优化求解,通过关系矩阵编码方式,减少冗余空间 的产生和冗余搜索,提高了方法的实时性和稳定性。
附图说明
图1为本发明改进粒子群算法的无线传感网络路由优化方法实例流程图;
图2为网络结构拓扑图;
图中,101表示初始化参数和初始化种群;102表示计算粒子适应度函数; 103表示寻找Pbest和Gbest;104表示引入交叉和变异机制,更新粒子和速度;105 表示更新Pbest和Gbest;106表示是否满足终止条件。
具体实施方式
下面结合附图和实施例对本发明进行进一步详细说明。
参照图1,本发明所提出的方法包括以下计算步骤:
(1)首先执行步骤101,进行初始化参数:设定网络节点数n=13,粒子群 个体编码为13×13的矩阵,路由请求为R=[3.5.60,14,12],权重系数w从2.0迭代 刀0.8,以及最大的迭代次数tmax=200,还有确定路由节点的基本信息,如有效 传输距离、初始能量及剩余能量。
(2)执行步骤102,计算粒子适应度函数:定义一个罚函数Q(Pst)将约束优 化问题转化为无约束优化问题进行求解:其中,罚函数Q(Pst) 表示为
(3)执行步骤103,寻找Pbest和Gbest:对于每个个体,将其适应值与其所经 历过的最好位置的适应值进行比较,若较优,则更新最好位置;对于每个个体, 将其适应值与全局所经历的最好位置的适应值进行比较,若较好,则将其作为 当前的全局最好位置。
(4)执行步骤104,引入交叉和变异机制,更新粒子和速度:对于粒子群 所有个体,根据关系矩阵编码方式,计算每个粒子个体的位置和速度,对每个 粒子进行变异操作,然后在此基础上对粒子进行交叉操作。
变异。在每次迭代中,为了保持样本的多样性,根据速度更新公式
交叉。为了跟踪全局最佳粒子,随机选取全局最优路由中的某个区间片段 [a,b]进行交叉。即从Rg中选择片段Rc={va,…,vb}插入到Rj中vji后面,并且vji离va节点距离最小。然后在Rj原路径中删除节点va,…,vb,同时需更新路由标识向量 Xj。
根据位置更新公式计算下一代的位置。
(5)执行步骤105,更新Pbest和Gbest:重新评价各粒子的适应度值,更新 各个粒子的历史最优解,更新种群的全局最优解。如果新位置的适应值比当前 局部最好解的适应值还要小,则用新的位置更新当前的局部最好解;假若有粒 子的局部最优解优于当前的全局最优解和其他粒子的局部最优解,则用此局部 最优解更新当前的全局最优解。
(6)执行步骤106,停机条件判断:当Gbest不为全局最优解时,且迭代次 数t小于给定的限值,则迭代次数t=t+1,转入步骤(5)继续进化;否则此时输 出最好路径。
应用实例:
采用基于源路由的路由选择机制,即在仿真网络中的源节点需要维护全局 网络拓扑结构及其状态参数,基于此网络拓扑及其状态参数,在源端进行计算 并确定路由。边链路由三元组[C,Bw,D]描述,其中D,Bw,C分别表示开销,带宽和 延时。用于实验的网络拓扑图如图2所示。
机译: 一种内燃机喷油嘴的优化方法,包括使喷油嘴主体和针头在壳体的孔内轴向滑动,其中采用粒子群算法对喷嘴进行几何布置
机译: 基于聚类的无线传感器网络路由路径方法
机译: 基于聚类的无线传感器网络路由路径方法