基于混沌粒子群算法的无线传感器网络路由协议

【摘 要】无线传感网络是由大量微型化的传感器节点，以自组织、多跳的无线通信方式，协作地完成特定功能的智能网络。由于传感器节点多采用电池供电，因此节能成为传感器网络工作中非常重要的问题。利用混沌的随机性和遍历性，结合粒子群进行最优寻解，使得当算法陷入局部收敛时进行混沌搜索，以达到节能的目的。

【关键词】无线传感器网络；混沌；粒子群优化；局部最优解

0.引言

无线传感器网络（Wireless Sensor Network,简称WSN）[1]的系统架构主要由分布式无线传感器节点群、Sink 节点、传输介质和网络用户端等四部分组成[2]。多个传感器节点部署在感知区域内，自组织成网络，除了进行信息收集和数据处理外还协助其他节点工作，并将监测、感知的信息向Sink节点发送，再由Sink 链路将整个区域内的数据传送到用户端。

在无线传感器网络中，能耗主要由数据采集能耗和数据传输能耗两部分组成，其中数据传输是消耗能量最多的，而传感器节点有限的能量是传输的瓶颈，所以必须设计能量高效的路由协议。WSN的路由协议的目的主要是将数据从传感器节点发送到汇聚节点，这就要求协议能够选择合适的优化路径并且沿着选定的路径正确迅速地转发数据。

1.混沌理论

混沌特性就是在确定性系统中出现类似随机的现象。与其他非线性系统相比，它在优化问题的求解上有着独到之处。

首先产生一组与优化变量数目相同的混沌变量，再以类似载波的方式引人优化变量使其呈现混沌状态，同时扩大混沌运动的遍历范围，直到优化变量的取值区间，然后直接利用混沌变量进行搜索。由于混沌运动的随机性和对初始条件的敏感性等特点，基于混沌的搜索无疑比其它随机搜索技术更加具有优越性。

2.粒子群优化算法

粒子群优化算法（Particle Swarm Optimization，PSO）是1995年由美国的Kennedy和Eberhart提出的，可以用于复杂优化问题的求解[3]。

被称为粒子的个体是在超维搜索空间运动的，它具有的速度向量决定它飞行的方向和速度，围绕当地最好粒子和全局最佳粒子，并且参考自身的飞行经验在空间中寻优，根据自己的位置和速度来动态调整下一步自己的行为，那么更新方程为：

v■(t+1)=v■(t)+c■r■(p■(t)-x■(t))+c■r■(p■(t)-x■(t)) （2.1）

x■(t+1)=x■(t)+v■(t+1) （2.2）

其中，当中，v■和x■为粒子的速度与粒子当前位置，c■和c■是学习因子，r■、r■是（0，1）随机数，p■、p■分别代表粒子当前最好位置和种群中最好位置。

基本PSO算法容易陷入局部最优解而导致收敛速度慢精度低（影响其收敛速度的一个重要原因在于它的随机性减缓了收敛速度），利用数学的外推技巧来引导粒子的方向，可以减少算法的随机性而提高搜索的效率。由位置更新公式(2.2)可以在它附近产生一个虚拟位置。

x■(t+1)■=x■(t)+r■(t+1) （2.3）

由此可以推出

x■(t+1)■=x■(t+1)■+K(x■(t+1)■-x■(t+1))

=(1+K)(x■t+rv■(t+1))-K(x■t-v■(t+1))

=x■t+[(1+K)r-K)v■(t+1)] （2.4）

由于每个粒子的位置分量比较多，很容易出现分量非常接近甚至完全相同的粒子，因此在具体实现时，可以在公式（2.4）后面加上一个极小的随机数使其在进化后期起微调作用，得到的位置公式为

x■(t+1)=x■t+[(1+K)r-K)v■(t+1)+10■r] （2.5）

最后得到改进的位置更新公式如下：

v■(t+1)=v■(t)+c■r■(p■(t)-x■(t))+c■r■(p■(t)-x■(t))x■(t+1)=x■t+[(1+K)r-K)v■(t+1)+10■r] （2.6）

3.基于混沌的PSO无线路由算法

由于PSO方法存在早熟、局部收敛、运算量大等缺点，那么将具有遍历性和随机性的混沌序列引入PSO，就可以充分利用两种机制的优势。按粒子搜索方式不同将整个粒子群体分为两分群，分别命名为PSO分群（P 群）和混沌分群（C群）[4]。同时，优化分为两个阶段，第一阶段C群和P群分别按混沌遍历机制和PSO搜索机制迭代，P群粒子更新方程(2.1)中p■为整个粒子群体而不是t时刻此分群全局最优解，混沌优化算法的全局遍历性就避免了“早熟”；在第二阶段P群粒子收敛于局部极值点，C群粒子将以局部极值点为中心进行混沌迭代，同时用适应值较好的部分粒子替换P群中相同数量的较差粒子，帮助P群粒子逃离局部最优区。

设p■(t)、p■(t)分别代表P群t时刻的个体最优值和全局最优值，C■(t)C■(t)分代表t时刻C群全局历史极优解和整群全局历史最优解。那么混沌粒子群优化算法流程为：

Step1：设定粒子数，初始化两分群粒子的位置、最大迭代次数、设置分群规模、优化精度及相关初始参数，随机产生初始速度，计算每个粒子的初始适应值，并保存整群中适应度最优的粒子的适应值和位置。

Step2：初步搜索。P群和C群粒子分别产生粒子新位置，计算新适应值并及时更新，比较C■(t)和C■(t)的大小，更新p■(t)及其适应值，重复上面的操作直到满足精度要求。若P群粒子陷入局部最优则进入Step3。

Step3： 进一步搜索。重新产生C群N个混沌向量，在以p■(t)为中心，R为半径的邻域内进行混沌搜索，将混沌向量变换到解空间；

Xi=p■(t)+R,i=1,2,3,…N

计算两群各粒子的适应值并更新C■(t)和C■(t)的适应值，将两分群的粒子分别按适应值的优劣排序，用C群中适应值较优的粒子替换P群中相同数量适应值较差的粒子，并比较C■(t)和C■(t)的大小，保存p■(t)及其适应值，逐步减小R从而重复上面的操作，直至满足精度要求或达到最大迭代次数。

Step4：停止搜索，输出全群的历史最优位置及最优适应值。

4.算法仿真比较

基准测试函数如下：

f(x,y)=x2-0.4cos(3?仔x)+2y2-0.6cos(4?仔y)-1 （4.1）

其中-10?燮x，y?燮10在[-10，10]区间内有一个全局最小值点（0，0），全局最小值为0[7]。设定算法的初始化参数如下：群规模20，学习因子c1=1，c2=1，进化次数设为1000，混沌寻优次数设为500，连续运行50次所得的函数全局最小值点和全局最小值点的平均值作为衡量指标，粒子群优化算法和混沌粒子群优化算法的仿真结果比较如下：

表1 粒子群优化算法和混沌粒子群优化算法仿真比较

由表1，混沌粒子群优化算法的结果优于粒子群优化。混沌粒子群优化算法不但能克服早熟现象，还提高了算法的收敛速度。

5.结束语

本文利用混沌运动的遍历性、随机性和规律改进了PSO初始种群提取方法，克服PSO算法的局部最优和混沌优化搜索时间长的缺点，提出了一种混沌粒子群混合优化算法来解决无线传感网络的路由问题，使其高效节能。实验表明该算法精度高、全局收敛能力强，但是同时还有许多问题值得进一步研究。

【参考文献】

［１］王文光,刘士兴,谢武军.无线传感器网络概述[J].合肥工业大学学报,2010,9,33(9).

［２］黄席樾,向长城,殷礼胜.现代智能算法理论及应用[M].科学出版社,2009,3.

［３］陈如清,俞金寿.混沌粒子群混合优化算法的研究与应用[J].系统仿真学报,2008,(2).

［４］高鹰,谢胜利.混沌粒子群优化算法[J].计算机科学,2004,31(8).