《无线传感网络移动节点位置并行微粒群优化策略_王雪》由会员分享，可在线阅读，更多相关《无线传感网络移动节点位置并行微粒群优化策略_王雪（6页珍藏版）》请在金锄头文库上搜索。
1、第 30 卷 第 4 期 2007 年 4 月计 算 机 学 报 CHINESE JOURNAL OF COMPUTERSVol. 30 No. 4 Apr. 2007收稿日期: 2005 -03 -09; 修改稿收到日期: 2007 - 01 -30. 本课题得到国家/ 九七三0重点基础研究发展规划项目基金( 2006CB303000) 和国家自然科学基金( 60673176, 60373014, 50175056) 资助.王 雪, 男, 1963 年生, 博士, 副教授, 从事智能仪器与数据融合和传感网络研究工作. E -mail: wangx ue mail. tsinghua. edu
2、. cn. 王 晟, 男, 1981 年生, 博士研究生, 主要从事无线传感网络的研究工作. 马俊杰, 男, 1985 年生, 硕士研究生, 主要从事网络化测量工作.无线传感网络移动节点位置并行微粒群优化策略王 雪 王 晟 马俊杰( 清华大学精密仪器与机械学系精密测试技术及仪器国家重点实验室 北京 100084)摘 要 网络节点位置优化是无线传感网络研究的核心问题之一. 无线传感网络通常由固定节点和少量移动节点构成, 传统的虚拟力导向算法无法解决固定节点对移动节点优化的约束. 该文针对这一问题, 提出了基于并行微粒 群算法的优化策略. 微粒群算法具有适于解决连续空间多维函数优化问题、 能快速收
3、敛至全局最优解的特点. 并行框架提高了算法的运行效率, 降低了算法的运算复杂度, 使算法能够满足无线传感网络的需求. 通过并行微粒群算法搜索不同状态下无线传感节点的最优位置, 使无线传感网络能够利用移动节点实现网络结构的动态重组, 最大化网络覆盖范围, 提高网络测量可靠性. 实验证明, 并行微粒群优化策略能快速有效地实现无线传感网络移动节点 位置优化.关键词 无线传感网络; 传感节点位置优化; 并行微粒群算法; 移动节点 中图法分类号TP393Parallel Particle Swarm Optimization Based Mobile Sensor Node Deployment in
4、Wireless Sensor NetworksWANG Xue WANG Sheng MA Jun -Jie(State Key Laboratory of Precision M easurement T echnology and Instruments, Dep artment of Precision Instruments,T singhua University , Beij ing 100084)Abstract Sensor node deployment is one of the key topics addressed in the researches of wire
5、lesssensor networks ( WSNs) . WSNs always consist of stationary and mobile sensor nodes. Virtual force ( VF) algorithm can not conquer the impact of stationary sensor nodes because force exerted by stationary sensor nodes will fetter the movements of mobile sensor nodes, which will strongly deterior
6、ate its performance. T his paper proposes a self -organizing technique for enhancing the coverage of WSNs, which is so - called parallel particle swarm optimization ( PPSO) . PSO is an outstanding algorithm for solving mult- i dimension function optimization in continuous space and has a series of a
7、dvantages, such as, high -speed regional convergence and efficient global searchingability. In the proposed algorithm, PSO is adopted in a parallel mechanism to optimize the de - ployment of mobile sensor nodes. Because of the parallel mechanism, PPSO can be successfully used in WSNs and effectively
8、 achieve global searching for optimal strategy of mobile sensor nodes deployment. Simulation results demonstrate that the proposed PPSO has better performance on regional convergence and global searching than VF algorithm and can implement sensor deploy- ment more efficiently and rapidly.Keywords wi
9、reless sensor networks;sensor node deployment optimization; parallel particle swarm optimization; mobile sensor node1 引 言无线传感网络需要大量节点协同完成测量任务, 同时也面临着复杂多变的工作环境 1. 根据不同 环境合理布置节点, 有利于提高无线传感网络的工 作效率、 降低花费. 移动节点使无线传感网络动态自治成为可能. 采用移动节点实现对网络结构的动态 重组, 扩大网络覆盖范围, 优化网络性能已成为无线 传感网络的关键技术之一 2. 近年来, 研究人员尝试从不同角度解决无
10、线传感节点位置优化问题, 提出 很多有效的方法. 文献 3 提出一种用于解决移动节 点位置优化问题的分布式自散布算法( DistributedSelf Spreading Algorithm, DSSA) . 文献 4 中介绍 了两种网格化无线传感节点布置方法 MAX_AVG_ COV、 MAX_MIN_COV, 通过放置尽可能少的无线传感节点达到期望的覆盖要求. 在这些算法中, 虚拟力导向算法 2, 5 -7在扩大网 络覆盖范围, 优化网络连接性能方面表现得突出, 能够满足仅由移动节点构成的无线传感网络的位置优 化需求. 但对于由固定节点和移动节点构成的无线 传感网络, 最终优化结果受固定节
11、点的影响, 无法实现全局最优. 事实上, 由于移动节点造价高, 且节点 在移动过程中消耗大量能量, 因此, 全部采用移动 节点构建无线传感网络是不现实的. 为解决含有固定节点的无线传感网络节点位置优化问题, 本文提 出了基于并行微粒群算法( Parallel Particle Swarm Optimization, PPSO) 的无线传感网络节点位置优化策略, 利用微粒群算法优化无线传感网络移动节点 位置, 并通过并行框架降低算法的计算时间和运算 复杂度, 提高算法效率. 实验证明, 提出的并行微粒群优化策略能实时有效地实现无线传感网络移动节 点的位置优化配置.2 问题模型与假设无线传感网络由
12、大量具有感知能力、 无线通信 能力的传感节点构成. 节点位置优化策略通过有效配置节点位置, 扩大网络有效覆盖面积提高网络测 量和通信性能. 通常, 无线传感网络由固定节点和移 动节点构成. 各节点具有相同的测量范围 r、 测量可 靠度和通信半径 c. 假设节点 si的位置为(xi, yi), 目标位于(x, y), 则目标与节点 si的距离为 d(si, P) =( xi- x)2+ ( y i- y)2. 对于二进制测量模型, 则节 点 si对目标的检测概率为cxy( si) =1,d(si, P) 0 时, 无线传感节点对目标的测量概率有可 能小于 1. 这意味着在测量过程中, 需采用多个
13、无线传感节点同时测量目标, 以提高目标测量概率. 多个 无线传感节点对目标的联合测量概率如下所示:cx, y(Sov) = 1-FsiI Sov(1- cx, y(si)(5)其中, Sov为测量目标的无线传感节点集合. 令 cth为 节点测量概率阈值, 则目标可被有效测量的条件为 minx, ycx, y( si, sj)E cth(6)网络初始化时, 各节点被随机或依某种方案放 置于待测区域中. 随机初始化布局如图 1 所示, 其中圆点代表无线传感网络节点, 圆圈表示节点固定测 量范围, 网络对各点的联合测量概率由灰度表示.图 1 无线传感网络随机初始化布局由图 1 可知, 随机布置的无线
14、传感节点测量区域通常是不规则的, 无法用解析方法直接求解网络 的有效测量区域面积. 为有效评价无线传感网络的 覆盖性能, 本文采用网格化方法将待测区域划分成564计 算 机 学 报2007 年网格, 其粒度(即相邻网格间的距离)由待求解问题精度决定. 评价网络覆盖性能时, 将单元格简化为点, 分析各无线传感节点对该点的联合测量概率. 最终, 计算满足式(6)要求的单元格数量占所有单元格 数量的比例, 该数值即约等于有效测量区域占整个待测区域的比例. 实验证明, 当粒度大小为待测区域大小的 4% 0 125% 时, 计算值与精确值之间的绝对偏差约为 0 15% 011%. 网格化方法无需考虑有效
15、测量区域形状, 避免通过解析方法求解. 方法步骤简单、 易于实现, 但该方法也存在求解问题耗时较长的缺点, 且耗时随粒 度的减小成平方增长, 不利于提高问题的求解精度.针对无线传感网络中固定节点数量较多的特点, 本文采用分步计算方法评价网络有效覆盖性能, 即在网络初始化时先确定固定节点构成的有效测量区 域, 网络动态调整时, 只需分析剩余区域的测量概率, 并将新增有效测量区域与固定节点构成的有效测量区域相加获得最终结果. 通过分步计算, 节省了 大量重复搜索时间, 提高了搜索效率.为简化问题模型, 本文针对无线传感网络特点做出如下假设:(1) 无线传感网络由大量固定传感节点和移动 传感节点构成
16、. 另外, 网络中还包含少量智能传感节点和一个中心处理节点. 其中, 智能传感节点计算能力较强, 用于并行实现微粒群优化; 中心处理节点可 靠性高, 用于融合各智能传感节点的优化结果.(2) 节点可以通过某种方式(如采用全球定位系统(GPS)或其它节点定位方法)获取自身位置.(3) 移动节点具有移动能力, 能够准确移动至 优化后的位置中.(4) 移动节点能量较充裕, 能够支持移动节点完成位置迁移过程.3 并行微粒群算法及节点位置优化3 11 微粒群算法基本原理 微粒群算法是一种群智能进化计算方法 9, 具有运算简单, 易于实现的优点. 近年的研究和实践表明, PSO 在多维空间多峰寻优、 动态寻优方面有速度快、 解质量高、 鲁棒性好等优点 10. 设搜索空间为 n 维, 微粒群规模为 m. Xi= (xi 1,xi2, , xin) 为微粒 i 位置, Vi= ( vi 1, vi 2, , vin) 为微粒 i 飞行速度, Pi= (pi1, pi 2, , pin) 为微粒 i 经 历的最佳位置,
