DOI:10.13436/j.mkjx.2013.05.017 第 34 2013 卷第 年 05 05 期 月 煤 矿 机 械 Coal Mine Machinery Vol.34No.05 May. 2013 基于粒子群优化算法的 林 雯 1， 530003； 2. 广西工商职业技术学院 南宁 ， （1. 摘 要 节点定位方法研究 * WSN 张烈平 2， 桂林理工大学 机械与控制工程学院 王守峰 2 广西 桂林 ， 541004） ： 为提高无线传感器网络的节点定位精度， 将惯性权重的粒子群优化算法应用到无线 传感器网络节点定位中。 定位方法以未知节点与其邻近锚节点之间的估计距离和测量距离的均方 误差为适应度函数，采用基于惯性权重的粒子群优化算法对适应度函数进行优化 ，从而得到最优 解，实现节点有效定位。 仿真实验结果表明，与传统的最小二乘定位算法相比，基于惯性权重的粒 子群优化算法的定位精度更高，稳定性更好，具有较好的定位效果。 关键词 中图分类号 ： 无线传感器网络； 粒子群优化算法； 节点定位； 最小二乘法 ： TP393 文献标志码 ： A 文章编号 ： 1003 － 0794（2013）05 － 0084 － 03 Research on Nodes Localization Method for Wireless Sensor Networks Based on Particle Swarm Optimization Algorithm LIN Wen1， ZHANG Lie-ping2， WANG Shou-feng2 (1. Guangxi Vocational College of Technology and Business, Nanning 530003，China; 2. College of Mechanical and Control Engineering, Guilin University of Technology, Guilin 541004, China) Abstract: To improve the precision in location estimation, a nodes localization method for wireless sensor networks based on particle swarm optimization algorithm with self-adapting inertia was proposed in this paper. The sum of squared range errors between the unknown nodes and neighboring anchor nodes was considered as the objective function in this method. And the particle swarm optimization algorithm with self-adapting inertia was used to optimize the objective function, in order to obtain the optimal solution, and to achieve the effective nodes localization. The simulation experimental results showed that, compared with the east -squares method, the localization method base on particle swarm optimization algorithm with self-adapting inertia was stable with high localization accuracy and better localization effect. Key words: wireless sensor networks； particle swarm optimization algorithm； nodes localization 1 method； least-squares method 引言 粒子群优化 0 、 、 ， （PSO） 具有原理简单 个体数目少 收 敛速度快和 参数设置少 等优点 算法保留了基于种群的全局 计算复杂度 搜索策略 、 低 可 以有效解 决 全局优化问 题并且能避 免一些其他 优化方 法 的 以提 缺点 ， 高节点定位精度 节点定位中 仿真进行了验证 算法引入到 并通过 ， 定位问题描述 MATLAB 本文将 WSN PSO ， 。 。 节点定位实质是利用 WSN N 节点来计算 个未知节点的位置坐标 点获得的距离信息及其无线通信半径 位策略来确定未知节点位置的过程 间定位问题 未知节点坐 标 。 M 个位置已知的锚 利用未知节 根据某种定 ， 如一个二维空 ， ， θ＝［θx，θy］， θx=［x1， 可以利用锚节点的 位置 x2，… ，xN］，θy=［y1，y2，… ，yN］ 来计算 坐标 。 由于锚节点 与未知节 点之间测到 的距离并 不 是 真 因此可将未知节点的位置估算看作是一种优 实值 ［yN+1，yN+2，…，yN+M］ ［xN+1，xN+2，…，xN+M］ 和 其中 ， 广西区自然科学基金项目 桂科自 * 校重点资助科研项目 ( 桂教科研 0991252)；2012 年度广西高等学 （ 201202ZD051） 将未知节点与邻居锚节点之间距离的均方 化问题 误差作为节点定位问题的适应度函数 。 其中 姨 （xi，xi）2+（yi，yi）2 是未知节点的估计坐标 fi（x，y）=di- ,（xi，yi） 是第 个锚节 点与该未知 节点的估计 距离 个锚节点的实际坐标 i （1） ，（xi，yi）（i=1，2， ， 姨 （xi-xi）2+（yi-yi）2 ，fi（x，y） 个锚节点的测量距离与估计距离 i 是第 个锚节点与未知 节点之间 ，di 由于在现实中节点之间的测量距离并 故测量距离要采用实际距离加高 i i …，M） 是 第 是未知节点与第 之间的误差值 的测量距离 不是其实际距离 ， 即 斯误差的形式 。 ， di=dij（1＋randn×η） 式 中 个 节 点 之 间 距 离 的 真 实 值 dij———2 （2） ，dij= （xi-xj）2+（yi-yj）2 ； 姨 误差因子 服从均值为 与距离测量的精度有关 ， ； 的标准正 方差为 0、 1 η——— randn——— 态分布的随机变量 。 这样就把 数优化问题 。 84 WSN 适应度值越小 节点定位问题转化为适应度函 得 测距误差值就越小 ， ， 中国煤炭期刊网 www.chinacaj.net

。 αi——— 节点定位方法研究 林 雯 等 ， ——— Vol.34No.05 ， 本文选取 数 未知节点与第 i 量值精度的权值 到锚节点 比 路径时得到的 该跳数是由 ， i 。 M=4； 个锚节点之间距离测 该权值与未知节点 之间最短路径的跳数成反 算法求最短 ， Dijkstra 由此可见 ， ， 大小的重要因素 效提高节点的定位精度 对适应度函数进行优化 节点的定位精度 基于 程如下 。 测距误差是影响未知节点定位误差 最大限度的降低测距误差就能有 算法 本文采用 ， 故此 得到最优解 ， PSO 以提高 WSN 的节点定位方法实现过 ， ， PSO （3） （4） 规模 次数 ： 算法初始参数设置 ① NP， tmax， ② 最大速度 误差因子 vmax， η； 初始化粒子群 ， 节点的无限射程 ， 学习因子 和 c1 c2， 种群 最大迭代 R， 第 卷第 期 05 34 到的定位结果也就越准确 小化 可以降低定位误差 ， 基于 2 PSO 算法的 算法 WSN 基于粒子群优化算法的 WSN 通过对适应度函数的最 ， 提高节点定位精度 节点定位算法 ， （1）PSO 设在一个 n 维搜索空间中 由 ， 其中第 种群 X={x1，…，xi，…，xm}， 其速度为 （xi1，xi2，…，xin）T， 应的个体极值为 局极值为 Pg=（pg1，pg2，…，pgn）T。 子的原理 则粒子 （3） ， 速度和位置 将按式 xi Vi=（vi1，vi2，…，vin）T。 个粒子组成的 m 个粒子位置为 i xi= 其相 整个种群的全 按照追随当前最优粒 和式 改变自己的 （4） Pi=（pi1，pi2，…，pin）T， （t） （t） （t） （t+1） vid =vid+c1r1（pid-xid）+c2r2（pgd-xid） （t+1） xid =xid+vid （t+1） （t） （t） （t） 式中 d——— i——— m——— t——— r1、r2——— c1、c2——— ； d 维 ［0，1］ ，d＝1，2，…，n； ，i=1，2，…，m； ； 之 间 的 随 机 数 粒子的第 粒子 种群规模 当前进化代数 分 布 于 ； 个 体 粒 子 的 加 速 常 数 和 群 体 粒 子的加速常数 第 和位置 第 度和位置 。 算法基础上 ； 个粒子在第 可以引入惯性权重 代的飞行速度 代的飞行速 个粒子在第 t+1 ； i t i ， （t） vid、xid ——— （t） （t+1） vid 、xid ——— （t+1） 在基本 PSO 来改善算法的全局搜索能力和局部搜索能力 （t） （t+1） vid =wvid+c1r1（pid-xid）+c2r2（pgd-xid） （t） （t） （t） （t） 式中 （t） vid ——— w 惯性权重 ， （5） 粒子先前的速度 起到了调 节算法平衡全局和局部搜索的能力 ， 使得粒子有了足够的全局搜 反映 （t） c1r1（pid-xid） 索能力 了粒子间协同合作和知识的共享 避免局部极小 ， （t） ，c2r2（pgd-xid） （t） （t） 通过选择合 适的 w 的全局和局部收敛能力 。 从 时 0.9 解收敛 线性递减到 取值方法 0.4 ， ， 。 值就可 以很好的平 衡算法 相关研究成果表明 w 算法能够很快地向最优 当 ， 式中 w=0.9-0.5（nc/ncmax） nc——— ncmax——— 基于粒子群优化算法的节点定位算法 循环次数 最大循环次数 ； 。 （6） （2） 利用未知节 点到锚节点 之 间 的 多 跳 跳 段 距 离 及 它们之间的 跳数来降 低定位问题 的适应度 函 数 通过添加到未知节点跳段距离最近的几 的复杂度 个锚节点的加权位置信息 对定位误差适应度函数 进行改进 定义 ， 。 ， M Σαi 2fi Fi（x，y）= （7） 到 未 知 节 点 跳 段 距 离 最 近 的 锚 节 点 2（x，y） i = 1 式 中 M——— 85 w Nhop； ④ 根据式 置和速度 确定初始个体最优解和群体 个未知节 个锚节点 随机产生每个粒子的初始位置和 计算每个粒子的适应度值并把粒子的当前位 其中最好的作为全局极值 最优解 在特定网络区域内随机部署 点和 速度 置设置为个体极值 M ， N ， Pbest， Gbest 保存 ； 计算 ③ N 个未知节点分别到 按照 D， Dijkstra 距离矩阵 与锚节点之间最短路径及跳数 其距离最近的 跳数 个锚节点 4 j M 个锚节点之间 算法计算每个未知节点 到 i 及其 之间的距离矩阵 找出未知节点 ， d 和式 （4） （5） 更新群体中所有个体的位 ； 利用式 ⑤ （7） 计算每个个体的适应度函数值 并 适应度函数值小 ， 与当前历史群体最优解进行比较 的保留到下一代 即更新当前群体最优位置 ， ， 判断是否到达最大迭代次数 ⑥ tmax， 则输出全局最优解对应的个体位置 否则转至 件 是未知节点的位置估计坐标 ， ， ③。 ； 若满足条 也就 ［x，y］， 3 算法仿真及结果分析 仿真环境设置 （1） 设置网络节点总数为 随机分布在 ， 的正方形区域内 位置均固定不变 100 m 和部署 ， ， 100， 100 m× 未知节点和锚节点随机生成 锚节点的密度初始选为 根据经验和大量 节点的无限射程 学习因子 采用 MATLAB 进行仿真验证 20%， 。 反复试验选定定位方法的仿真参数 ： 最大速度 vmax=6， NP=20， tmax=100， 误差因子 种群规模 最大迭代次数 仿真结果与分析 R=40 m， c1=c2=2， （2） 在仿真中通过分别改变锚节点密度及测距误差 并将方法 来验证基于 ， 种定位方法 与基于 的未知节点定位效果放置到统一的纵坐标刻度下进 行比较 本文采用平均定位误差来评价算法的性能 算法的定位方法进行比较 算法定位方法的有效性 η=5%。 PSO LS ，2 。 中国煤炭期刊网 www.chinacaj.net

Vol.34 No.05 基于粒子群优化算法的 节点定位方法研究 WSN 林 雯 等 第 卷第 ， ——— 圆圈代表未知节点的实际位置 节点的位置 示定位后未知节点的估计位置 可以看出 ， 算法的定位方法能够实现节点的有效定位 34 ， 。 期 05 方框表 PSO ， 基于 。 40 35 30 m / 25 差 误 位 定 20 15 10 5 0 0 1 2 10 20 30 40 50 未知节点数 60 70 80 图 3 基于 PSO 和 LS 算法的未知节点的定位误差对比图 1. LS 2. PSO 100 90 80 70 60 50 40 30 20 10 0 0 图 10 20 基于 4 30 PSO 60 50 40 90 100 算法的节点定位效果图 80 70 4 结语 通过 ， 。 ， PSO MATLAB WSN 采用 节点定位方法 仿真平台对基于 算法优化以降低未知节点与相邻的 以 锚节点之间的估计距离和测量距离的均方误差 从而获得较好的定位精 实现 算法的定 度 位方法及传统的基于 算法的定位方法进行了仿 真对比实验 定位误差和 定位效果等方面分析和验证了定位方法的有效性和 正确性 。 参考文献 从锚节点密度 测距误差 PSO LS ， 、 、 ： , . ［1］Akyildiz I.F., Weilian Su, Sankarasubramaniam Y., et al. A survey on sensor networks ［J］. IEEE Communications Magazine, 2002, 40 （8）：102-114. ［2］Aspnes J, Goldenberg D, Yang Y R. On the computational complexity of sensor network localization ［C］. Proceedings of First International Workshop on Algorithmic Aspects of Wireless Sensor Networks. 2004. 廖萍 一种基于遗传算法的无线传感器网络节点定位技 孔翠香 , 术研究 赵仕俊 ［J］. 孙美玲 . 井冈山大学学报 . 自然科学版 ： ，2011,32（4）：71-75. 唐懿芳 基于遗传模拟退火算法的无线传 感 器 网 络定位算法 计算机应用与软件 ,2009, 26（10）：189-192. , ［J］. 孙美玲 基于遗传算法的无线传感器网络节点自身定位算法研究 ［3］ ［4］ ［5］ 青岛 中国石油大学 ,2009. ［D］. : 作者简介 ： 算机应用技术 林雯 电话 （1971- ）， 江西南康人 副 教 授 研 究 方 向 为 计 ， ， 电子信箱 ， ：0771-2276331， ：33538898@qq.com. 责任编辑 ： 卢盛春 收稿日期 ：2012－12－06 Error= 100 NR N i = 1 Σ （xi-xi）2+（yi-yi）2 姨 % （8） 式中 R——— N——— （xi、yi）——— （xi、yi）——— ； 节点的通信半径 未知节点个数 未知节点 未知节点 ； i 的估计位置 的实际位置 i ； 。 ， 。 在仿真过程中 保持其他参数不变 锚节点个数比例是评价定位的一个重要指标 ， 锚节点的多少直接影响到网络的 成 本 及 能 耗 的 大 小 通过改变锚 ， 节点密度来观察其对 种定位方法的平均定位误差 的影响 增 长到 种 方法的平均定位误差都是随着锚节点密度的增大而 减小 算法的定 位精度更高 总体性能要优于 基于 图 对平均定位误差的影响效果图 但在同一锚节点密度下 定位成本和功耗要小 是锚节点密度以 算法的定位方法 的间隔从 基于 显然 10% 30% PSO 5% ，2 1 2 。 ， ， 。 ， ， LS 16 14 12 10 8 6 4 % / 差 误 位 定 均 平 1 2 2 10 12 14 16 18 20 22 24 26 28 30 锚节点密度 /% 图 1 锚节点密度对平均定位误差的影响 图 2 。 差 误 位 定 均 平 40 35 % / 30 25 20 15 10 5 0 0 1 2 2 4 6 8 10 12 14 16 测距误差 /% 18 20 测距误差对平均定位误差的影响 1. LS 2. PSO 1. LS 2. PSO 。 ， η 误差因子 在仿真过程中 取值范围从 的测量距离有着直接影响 他参数不变 取误差因子 测距误差对定位误差的影响如图 长选为 中可以看出 示 的取值对未知节点和 锚 节 点 之 间 保持其 步 所 2 基 于 其平均定位误 此定位方法受到测距 从图 算法定位方法的定位误差最小 在相同测距误差下 也就是说 0～20%， 5%， η 2 ， 。 ， ， ， PSO 差曲线的斜率较小 误差影响最小 ， ， 定位效果比较好 ， 种定位方法 。 2 3 图 是 80 从图 知节点定位误差效果图 观察定位算法的未知节点定位误差情况 于 个未知节点中每个未 中可以比较直观地 基 算法的未知节点定位误差曲线波动比基于 算法的定位稳定 定位精度 说明基于 算法的定位稳定性 显然 PSO 3 ， 。 。 ， PSO 算法要小的多 LS 性能要优于基于 较高 定位效果好 ， 图 LS 。 为当误差因子 时 ， 定位方法的未知节点定位效果图 η=5% 4 基于 算法的 其中星号代表锚 PSO ， ： 本刊已许可中国学术期刊 发行 汇编 为即视为同意我社上述声明 信息网络传播本刊全文 、 、 （ 。 ， ） 版权声明 姨姨姨姨姨姨姨姨姨姨姨姨姨姨姨姨姨姨姨姨姨姨姨姨姨姨姨姨姨姨姨姨姨姨姨姨姨姨姨姨姨姨姨姨姨 光盘版 电子杂志社在中国知网及其系列数据库产品中以数字化方式复制 该社著作权使用费与本刊稿酬一并支付 、 作者向本刊提交文章发表的行 。 。 86 煤矿机械杂志社 2011 年 7 月 12 日 中国煤炭期刊网 www.chinacaj.net