基于微粒群算法的无线传感器网络节点定位方法_图文


第 44 卷 Vol. 44

第 9期 No. 9













(理



版)

Journal of Shandong University( Natural Science)

2009 年 9 月 Sep. 2009

文章编号: 1671 29352(2009) 09 0052 04 2 2

基于微粒群算法的无线传感器网络节点定位方法
周书旺 , 王英龙 , 郭强 , 魏诺
1, 2 2 2, 3 2

( 1. 山东师范大学信 息科学与工程学院, 山东 济南 250014; 2. 山东省计算中心, 山东 济南 250014; 3. 山东经济学院信息管理学院, 山东 济南 250014)

摘要: 为了进一 步提高无线传感器网络未知节点 定位精 度, 将节点 定位问题 和微粒 群算法 结合在 一起, 提出了 基 于微粒群算法的节点定位算法。该算法是一 种基于 距离的 定位算 法, 根 据未知 节点到 锚节点 的距离直 接搜索 出 未知节点的坐标。实验结果表明, 和一般的固定 节点定 位算法 相比, 该算法 具有更 高的定 位精度, 并适 用于移 动 节点的追踪定位。 关键词: 无线传感器网络; 微粒群算法; 节点定位; 锚节点 中图分类号: TP393 文献标志码: A

Particle swarm optimization2based wireless sensor network nodes localization method
ZHOU Shu 2wang , WANG Ying2long , GUO Qiang , WEI Nuo
2. Shandong Computer Science Center , Jinan 250014, Shandong, China; 3. School of Information Management, Shandong Economic University, Jinan 250014, Shandong, China) Abstract: To further enhance the location precision of unknown nodes in wireless sensor networks, a localization method based on particle swarm optimization is presented, through the combination of wireless sensor network and particle swarm optimization, which is dependent on distance. It can directly search out the coordinates of unknown nodes by the distance from anchor nodes to unknown nodes. As is shown in the experimental results, compared to the normal location algorithms of fixed nodes, this method has higher positioning accuracy and can be applied to the tracking of moving nodes. Key words: wireless sensor networks( WSNs) ; particle swarm optimization( PSO) ; node location; anchor node
1, 2 2 2, 3 2

( 1. School of Information Science &Engineering Shandong Normal University, Jinan 250014, Shandong, China;

用户提供详尽而准确的信息 。

[1]

0

概述
无 线 传 感 器 网 络 ( wireless sensor networks,

在许多应用中传感器网络采集的信息与节点的 位置息息相关, 因此节点定位是传感器网络的关键 技术之一。目前无线传感器网络节点定位算法可以 分为基于距离的定位 算法和与距离无关的定 位算 法。与距离无关的定位算法无需额外的硬件支持, 成本低, 但定位精度较低 , 不能满足一些实际应 用。基于距离的定位算法包括测距和定位计算 2 个 步骤。目前, 常用的测距技术有 RSSI, TOA, TDOA,
[2 23]

WSNs) 综合了现代传感器技术、 微电子技术、 通信技 术、 嵌入式计算技术和分布式信息处理技术等学科, 是一个新兴的交叉研究领域。无线传感器网络能够 实时监测、 感知和采集网络分布区域内的各种环境 和检测对象的信息, 并对这些信息进行处理, 从而给
收稿日期: 2009 220 205

基金项目: 国家自然科学基金资助项目( 60802030) ; 山东省中青年科学家 科研奖励基金 资助项目( 2007BSC01002) ; 山 东省科技 攻关计划 资助项 目( 2007GG2Q T01007) 作者简介: 周书旺( 1985 2 ) , 男, 硕士研究生, 主要研究领域为无线传感器网络. Email: zhoushw@ keylab. net

第 9期

周书旺, 等: 基于微粒群算法的无线传感器网络 节点定位方法

53

AOA。节点定位计算方法包括: 三角测量法, 三边定 位算法及其改进 Bounding box 算法和最小二乘估计 定位算法等 。三角测量法所利用的 AOA 测距技 术易受 外界环境影响
[ 5] [ 4]

(3) 将每个锚 节点的当 前虚拟 位置的适 应度 (f 1 ) 与该锚节点所经历过的最好位置( pbest ) 的适应 度( f 2 ) 作比较, 如果 f 1 < f 2 , 则将该锚节点的当前虚 拟位置作为当前该锚节点所经历过的最好位置; (4) 将每个锚 节点的当 前虚拟 位置的适 应度 (f 1 ) 与全局所经历的最好位置( gbest) 的适应度(f 0 ) 作比较, 如果 f 1 < f 0 , 则将该锚节点的当前虚拟位置 作为当前全局所经历过的最好位置; ( 5) 根据公式 vid = wvid + c1 r ( ) ( pid - x id ) + c 2 R( ) ( pgd - x id ) , xid = x id + vid , ( 2) 确定该锚节点 接下来的 速度 v 和 位置 x, 其中 w、 c2 、2 为常量, r ( ) 、 ) 为随机函数, i 为第 i 个锚节 c R( 点, d 为维数, p id 是指第 i 个锚节点当前的最优位置 第 d 维的值, pid - xid 即为当前位置距该锚节点所经 历过的最优位置在第d 维的距离, pgd 是指全局最优 位置第 d 维的值, p gd - xgd 即为当前位置距全局最优 位置在第 d 维的距离; ( 6) 如未达到结束条件( 适应度小于一个指定 的数 ) ) ) 可以容忍的误差 Gmax ) , 则返回( 2) 。 212 算法中参数的作用 PSO 参数包括: 惯性权重 w, 加速常数 c1 和 c 2 , 最大速度 Vmax , 以及可容忍的最大误差 Gmax。 ( 1) 最大步长 Vmax Vmax 决定当前位置与最好位置之间的区域分辨 率( 或精度) 。如果 Vmax 太高, 微粒可能会飞过好解; 如果 Vmax太小, 微粒不能在局部好区间之外进行足 够的探索, 导致陷入局部最优值, 因此 Vmax 是影响算 法收敛与否以及收敛速度的一个重要因素。通常设 [ 11] 为每维变化范围的 10% ~ 20% 。 ( 2) 权重因子 在 PSO 算法中有 3 个权重因子: 惯性权重 w, 加 速常数 c1 和 c2 。惯性权重 w 使微 粒保持运 动惯 性, 使其有扩展搜索空间的趋势, 有能力探索新的区 域。加速常数 c 1 和 c 2 代 表将每个微粒推 向 pbest 和 gbest 位置的统计加速项的权重。低的值允许微 粒在被拉回之前可以在目标区域外徘徊, 而高的值 则导致微粒突然的冲向或越过目标区域。早期的试 验
[ 12] [10]

。由于节点间测 距存在误

差, 三边定位算法及 其改进 Bounding box 算法在实 际应用中定位精度不高。为了提高定位精度, 使用 最小二乘估计定位算法( ML) , 但定位精度仍然不能 尽如人意
[ 627]

。为了进一步提高定位精度, 本文提出

了基于微粒群算法的定位算法。

1

微粒群算法简介
微粒群算法
[8 29]

, 又称粒子群优化( particle swarm

opt imizat ion, PSO) , 是由 J. Kennedy 和 R. C. Eberhart 等于 1995 年开发的一种演化计算技术, 来源于对一 个简化社会模型的模拟。PSO 算法最初是为了图形 化的模拟鸟群优美而不可预测的运动, 而通过对动 物社会行为的观察, 发现群体中对信息的社会共享 提供一个演化的优势, 并以此作为开发算法的基础。 通过加入近邻的速度匹配, 并考虑了多维搜索和根 据距离的加速, 形成了 PSO 的最初版本。之后引入 了惯性权重 w 来更好地控制开发和探索, 形成了标 准版本。

2
211

微粒群定位算法
微粒群定位算法描述 该算法运行在具有中心服务器的无线传感器网

络中, 服务器作为网络的计算中心, 具有强大的计算 能力, 服务器收集未知节点与锚节点的关系数据( 如 信号强度) 并进行处理, 计算出各个未知节点的位置 坐标, 然后告知未知节点位置信息。 微粒群定位算法流程: (1) 初始化锚节点( 锚节点的个数为 m) , 包括 锚节点的位置和随机确定的各个锚节点的/ 运动0速 度。在这里锚节点的位置分为现实位置( T ij , i 代表 锚节点 的 编 号, j 代 表 维 数的 编 号) 和 虚 拟 位置 ( Lij ) 。现实位置即在初始化时由工具( 如 GPS) 测量 得到的位置, 虚拟位置即在算法迭代过程中计算所 得的位置。在开始时虚拟位置等于现实位置; ( 2) 计算每个虚拟位置的适应度 f , 计算公式为
i= m j= d 2 2

将 w 固定为 110, c 1 和 c2 固定为 210。 ( 3) 可容忍的误差 Gmax 可容忍的误差 Gmax 并非越小越好, Gmax 是 受测

f = i= 1 E 位置的距离;

E ( L ij - Tij ) - D i j= 1

,

( 1)

其中 d 为维数, Di 为未知节点到第 i 个锚节点现实

距误差制约的, 其计算公式为 Gmax = 1105# t= 0 Dt # E
oknum

e 1- e

2

,

( 3)

54













(理



版)

第 44 卷

其中, e 为测距误差, 该测距误差服从正态分布。D l 为未知节点测得的到第 l 个锚节点的距离, 该距离 含有测距误差。

数据, 未知节点真实坐标是( 30, 35) , 展示微粒群定 位算法在 1% 和 10% 测距误 差下的 定位结果 分布 图, 如图 2 和图 3。图 2 和图 3 都是由一次随机的实 验初始化了 100 次后得到的, 再次实验的结果可能 略有不同。由图 2 和图 3 可以清楚的看出微粒群定 位算法的搜索区域分布在未知节点的周围。图 2、 3 中符号含义同图 1。

3

仿真实验及结果分析
在实验中按微粒群算法的早期实验取 w= 110,

c 1 = 210, c 2 = 210, 假设锚节点的布设区域为 50 m@ 50 m 无障碍区域, 节点通信的最大距离为 71 m。设 4 个锚节点 p 1 ( 0, 0) 、 2 ( 50, 0) 、 3 ( 50, 50) 、 4 ( 0, p p p 50) , 最大步长 Vmax 与 WSNs 节点布设区域的跨度有 关, 在 实 验中 取 最大 步 长 为最 大 跨度 的 1/ 20, 即 Vmax = 215 m, 实验发现取该数值可使算法较快收敛, 并且有效避免了陷入局部最优的情况。 311 无测距误差的情况
图 2 测距误差 e= 1% 时定位结果 Fig. 2 Location results when e= 1%

在没有测距误差的情况下可准确地定位未知节 点。假设未知节点 X 1 , 测得锚节点到该未知节点的 距离分别为 d 1 = 461097m, d 2 = 401311 m, d 3 = 2510 m, d 4 = 331541 m。如图 1, 在初始化 100 次后可得定位结 果为 x= 301000 006 518 6148, y= 351000 000 486 387 4, 与真实坐标( 30, 35) 的误差为 615 @10 m, 这里所指 的定位误差是定位结果到未知节点真实值的距离。
- 6

图 3 测距误差 e= 10% 时定位结果 Fig. 3 Location results when e= 10%

微粒群定位算法与最小二乘估计法定位结果的 比较如 表 1。表中 微粒群定位算 法的数据是 由 25
图 1 测距误差 e= 0 时定位结果 Fig. 1 Location results when e= 0

次实验每次初始化 100 次计算得到的, 最小二乘估 计法的数据是依据上述 4 个锚节点计算得到的。
表 1 不同测距误差下的定位误差比较 Table 1 Location error comparison under different ranging error 测距 误差P% 1 5 10 15 20 25 30 35 微粒群定位算法 平均 最小 最大 误差Pm 误差Pm 误差Pm 01216 2 01186 2 01248 1 11049 8 01929 7 11182 4 11964 0 11761 8 21209 4 21701 1 21436 2 31073 2 31772 9 31332 7 41052 5 41524 9 31861 7 41970 7 51019 6 41318 3 51550 7 51782 8 51141 4 61384 4 最小二乘估计法 标准差 误差Pm 01013 3 01058 2 01109 3 01185 9 01188 8 01269 3 01353 7 01356 6 01222 5 11090 1 21124 3 31102 5 41024 9 41891 4 51702 0 61456 6

图中实心圆点是在每次初始化后得到的适应度 小于 G max 的点, / A0所指点是由上述所有点求平均 后得到的, 即最后的定位结果, / B0为未知节点的真 实位置。 无测距误差下的准确定位是所有定位算法都应 该做到的。 312 不同测距误差下微粒群定位算法与最小二乘 估计法的定位结果比较 将在 1% , 5% , 10% , 15% , 20% , 25% , 30% , 35% 的测距误差下分别讨论微粒群定位算法和最小 二乘估计法的定位结果, 仍采用 311 节中的锚节点

在此定位误差仍是定位结果到未知节点真实值

第 9期

周书旺, 等: 基于微粒群算法的无线传感器网络 节点定位方法

55

的距离, 可见微粒群定位算法的平均误差较之最小 二乘估计法有明显地降低, 并且微粒群定位算法的 标准差较小。可见微粒群定位算法的结果比较稳定。 另外, 由图 4 可以看出随着测距误差的增加, 微 粒群定位算法的误差增长速度要小于最小二乘估计 法。可见在测距误差较大的情况下, 微粒群定位算 法的优势更加明显。 综上所述微粒群定位算法较之最小二乘估计法 有着优良的定位性能。

[ 2] 段渭军, 王建 刚, 王福豹. 无线传感器 网络节点定 位系统 与算法的研究和发展[ J] . 信息 与控 制, 2006, 35( 2) : 239 2 245. [ 3] LANGENDOEN K, REIJERS N. Distributed localization in wireless sensor networks: a quantitative comparison[ J] . Com 2 puter Networks, 2003, 43( 8) : 499 2518. [ 4] NICULESCU D, NATH B. Error characteristics of ad hoc posi2 tioning systems[ C] / / Proceedings of MobiHoc. 04. Roppongi, Japan: [ s. n. ] , 2004: 20230. [ 5] AKYILDIZ I F, S W, SANKARAS U UBRAM ANIAM Y, et al. Wireless sensor networks: a survey[ J] . Computer Networks, 2002, 38( 4) : 393 2422. [ 6] GAU YUHE, CHU HUNGC HI, JAN RONGHONG. A Weight2 ed multilateration positioning method for wireless sensor net2 works[ C] / / Proceedings of Workshop on Wireless, Ad Hoc, and Sensor Networks. Taiwan, China: [ s. n. ] , 2005: 3 28. [ 7] 马祖长, 孙怡宁. 无 线传 感器网 络节 点的 定位 算法 [ J] . 计算机工程, 2004, 7( 4) : 13214. [ 8 ] KENNEDY J EBERHART R. Particle swarm optimization [ C] / / Proceedings IEEE Int Conf on Neural Networks, Perth:

图 4 定位结果比较 Fig. 4 Comparison of location results

[ s. n. ] , 1995: 1942 21948. [ 9] EBERHART R, KENNEDY J. A new optimizer using particle swarm theory[ C] / / Proceedings 6th Int Symposium on Micro Machine and Human Science, Nagoya: [ s. n. ] , 1995: 39243. [ 10] S YUHUI, EBERHART R. A modified particle swarm opti2 HI mizer[ C] / / Proceedings IEEE Int Conf on Evolutionary Com 2 putation, Anchorage: [ s. n. ] , 1998: 69 273. [ 11] EBERHART R, SHI YUHUI. Particle swarm optimization: Developments, applications and resources [ C] / / Proceedings IEEE Int Conf on Evolutionary Computation, Seoul: [ s. n. ] , 2001: 81 286. [ 12] KENNEDY J, EBERHART R. Particle swarm optimization [ C] / / Proceedings IEEE Int Conf on Neural Networks, Perth: [ s. n. ] , 1995: 1942 21948.

4

结语
无线传感器网络节点定位是该领域研究的一项

关键技术。基于微粒群算法的定位算法实现简单, 运行稳定, 与最小二乘估计法相比有更高的定位精 度, 比如在测距误差为 35% 情况下定位精度比最小 二乘法提高 01673 8 m。同时该算法也适用于对移 动节点的定位。
参考文献: [ 1] 丁海斌, 曾鹏, 梁 韦华. 智 能无 线传 感 器网 络系 统[ M] . 北 京: 科学出版社, 2006.

( 编辑: 孙培芹)


相关文档

基于改进粒子群算法的无线传感器网络节点定位
一种基于预测的无线传感器网络节点自定位算法
基于差分进化算法的无线传感器网络节点定位方法研究
改进粒子群算法的无线传感器网络节点定位
基于节点三角形选择方法的无线传感器网络定位算法
基于RSSI的无线传感器网络节点自身定位算法
基于移动信标节点的无线传感器网络定位算法研究
基于节点能量均衡的无线传感器网络目标定位算法
无线传感器网络节点定位的混沌粒子群优化算法
基于蚁群粒子群混合的无线传感器网络定位算法
电脑版