Computer Engineering and Applications 计算机工程与应用 2017，53（2） 129 优化混合蛙跳算法的 WSN 三维定位方法 刘 宏，王其涛，夏未君 LIU Hong, WANG Qitao, XIA Weijun 江西理工大学 电气工程与自动化学院，江西 赣州 341000 School of Electrical Engineering and Automation, Jiangxi University of Science and Technology, Ganzhou, Jiangxi 341000, China LIU Hong, WANG Qitao, XIA Weijun. Research for three-dimensional positioning method of WSN based on opti- mized shuffled frog leaping algorithm. Computer Engineering and Applications, 2017, 53（2）：129-133. Abstract：According to the traditional Shuffled Frog Leaping Algorithm（SFLA）that its convergence speed is slow and its local optimum has the shortcomings. The Optimized Shuffled Frog Leaping Algorithm（OSFLA）is put forward here and applied to the three-dimensional positioning of the wireless sensor network node. In the three-dimensional positioning, at first, using maximum likelihood has a rough positioning, then having weighted processing for anchor nodes and setting the search area. Finally, using OSFLA achieves the effect of iterative refinement. The simulation result shows that, the OSFLA has higher convergence speed and precision than the traditional SFLA. At the same time, it is more suitable for the occasion that has the less number of anchor node. Besides, in the three dimensional positioning, compared with the commonly used several kinds of algorithms, the OSFLA algorithm’s positioning accuracy and stability of OSFLA algorithm are obviously improved. Key words：wireless sensor network; Shuffled Frog Leaping Algorithm（SFLA）; three-dimensional positioning; anchor nodes 摘 要：根据传统混合蛙跳算法（Shuffled Frog Leaping Algorithm，SFLA）收敛速度较慢、局部最优的不足，提出了 优化混合蛙跳算法（Optimized Shuffled Frog Leaping Algorithm，OSFLA），并将其应用于无线传感器网络（WSN）节 点三维定位。在三维定位中运用极大似然法进行粗略定位，对锚节点进行加权处理，设定搜索区域，再使用优化蛙 跳算法进行迭代求精。仿真实验结果表明：优化混合蛙跳算法（OSFLA）比混合蛙跳算法（SFLA）具有更高的收敛速 度和定位精度，同时更加适合于锚节点数较少场合。且在三维定位中与常用的几种算法相比 OSFLA 算法在定位精 确度和稳定性方面都具有一定的提高。 关键词：无线传感器网络；混合蛙跳算法；三维定位；锚节点 文献标志码：A 中图分类号：TP393 doi：10.3778/j.issn.1002-8331.1504-0186 1 引言 无线传感器网络[1]（Wireless Sensor Networks，WSN） 可以实时地把监测信息传送给用户，在实际应用中，位置 和监测信息缺一不可，位置是基础、监测信息则是重点， 因此如何确定 WSN 的节点的坐标非常重要。由于山区、 海底等地形的特点，还往往需要知道监测对象的三维坐 标，故 WSN 节点三维定位的研究目前已成为热点[2]。 目前 WSN 的三维定位算法已取得一些研究成果[3-5]。 通常所用的智能优化算法[6]因其控制参数少、计算量不 大、同时易于实现等优点，已经越来越受关注。文献[7] 在寻优过程中使用粒子群算法，该算法实现较简单、运 行较稳定，在一定程度上提高了定位精度，但算法难以 基金项目：国家自然科学基金（No.61163063）。 作者简介：刘宏（1968—），男，副教授，主要研究方向为无线传感器网络基础设施的理论和技术，E-mail：jxligonglh@163.com；王其涛 （1990—），男，硕士研究生，主要研究方向为无线传感器网络节点定位及设计；夏未君（1990—），男，硕士研究生，主要 研究方向为无线传感器网络路由协议。 收稿日期：2015-04-20 修回日期：2015-07-15 文章编号：1002-8331（2017）02-0129-05 CNKI 网络优先出版：2015-08-28, http://www.cnki.net/kcms/detail/11.2127.TP.20150828.1620.020.html 

130 2017，53（2） Computer Engineering and Applications 计算机工程与应用 跳出局部最优；文献[8]提出了利用萤火虫群算法进行 WSN 节点定位，该算法在节点定位中具有较好的适应 性且收敛速度也较快，但发现峰值概率较低、适应值偶 然出现震荡；文献[9]提出的定位方法因使用蛙跳算法 进行迭代求精而减少了参数的设置，实现较容易，但难 以跳出局部最优解，稳定性也不够好；文献[10]在迭代 求精阶段使用了人工蜂群算法，应用该算法的无线传感 器网络操作简单，鲁棒性较强，但因局部开发能力不足 而存在早熟缺陷。因此，智能优化算法在 WSN 节点三 维定位中依然存在不足之处需要加以改进。在此基础上， 本文提出了应用优化混合蛙跳算法（Optimize Shuffled Frog Leaping Algorithm，OSFLA）解决传统蛙跳算法的 不足，并将其应用于 WSN 节点的三维定位。 2 WSN 节点三维定位方法 首先运用极大似然法（ML 算法）进行粗略定位，对 锚节点进行加权处理，设定搜索区域。将蛙跳算法中 的子群更新策略进行优化，在设定的搜索区域内根据 适应度函数迭代求精，以提高节点的三维定位精度和 收敛速度。 2.1 估算锚节点与待定位节点距离 由锚节点 M 发射射频信号，待定位节点 N 接收信 号，根据接收信号强度（RSSI）可方便地进行测距[11]。在 实际应用环境中，由于多径、绕射等因素影响了待定位 节点接收到的 RSSI 测距信号精度。在此可采用具有统 计的对数-正态阴影模型[12]。设 PL(d )（单位：dB）为发 射端信号强度，PL(d)（单位：dB）为接收端信号强度： 0 PL(d)= PL(d )+ 10n lg(d/d ) + X 0 σ p 0 （1） 式中，d 为 N 与 M 之间的直线距离，d 为单位距离，通 0 常取 1 m；n p 为路径损耗系数；X σ 为高斯分布正态随机 变量：均值为 0。 由式（1）便可得出 M 与 N 之间的距离 d 为： PL(d )- PL(d) 0 10n p 0 ´ 10 （2） d = d 影响 RSSI 测距精度的因素有发射功率和路径损耗 系数。信号的发射功率越大，测距范围越大；路径损耗 系数越小，信号传播距离越远；但无论发射功率和路径 损耗系数是多少，结果都是在近距离时，信号衰减得厉 害，在远距离时信号衰减得较为缓慢，由于路径损耗系 数很难做到精确估算，导致远距离的测量值含有较高的 误差[13]。因此，当待定位节点周围锚节点多于四个时， 便可对 d 进行筛选，舍去误差较大的距离，达到减少了 计算量、提高了定位准确性的目的。在此设立阈值 Q ， 如式（3）。当测量距离 d 大于阈值 Q 时，表示锚节点和 待定位节点的距离误差较大，则在计算中舍弃该信息， 设 R 为锚节点通信半径： Q = t R 式中，t 0 0 为阈值系数。根据 RSSI 测距误差变化规律：在 （3） 无障碍物情况下，测量距离小于 0.5R 时，测距平均误差 小于 0.1R ；测量距离在 0.5R ~ 0.75R 之间时，测距平均 误差在 0.1R ~ 0.2R 之间；测量距离大于 0.75R 时，测距 平均误差则大于 0.2R 。因此在考虑锚节点布置比例和 定位精度基础上选择 t 2.2 设定搜索区域 为 0.75。 0 设待定位节点 N(xyz) 周围锚节点共有 k 个，分 ) ，如图 1 )、、M (x (x y z 别为 M )、M (x 1 1 1 1 2 y k z k k y 2 z 2 2 k 所示。 z y z M (x ) 1 1 1 1 d 1 M (x y 2 z 2 2 ) 2 d 2 N(xyz) y O d M (x y k z k k k x … d 3 k ) M (x y 3 z 3 ) 3 3 图 1 待定位节点 N 与锚节点 M 三维位置关系图 2 2 - y)2 + (z 1 - y)2 + (z - z)2 = d 2   1 - z)2 = d 2 2 那么存在： ì - x)2 + (y (x ï ï 1 1 ïï - x)2 + (y (x í ï                      ï ïï - x)2 + (y (x î 利用ML算法可得待定位节点 N 精确度较低的坐标： X̂ = (AT A)-1ATb （5） - z)2 = d 2 k - y)2 + (z （4） 2 k k k 式中： ] x̂    ŷ     ẑ T - x  2(x 1 k A = X̂ = [ é ê êêê 2(x ë é ê êê ê x2 ë k b = ) 2(y 1 ) k - y  2(z 1 - z  - x ) 2(y k - x2 + y2 k 1 k - 1 - y2 1 k - 1 x2 k ) 2(z - z 2 1 k - 1 - d 2 k k ) ù ú úúú ) û + d 2 1 k - z - y k + z 2 k  + z 2 k ù ú úú ú û k - 1 - x2 k - 1 + y2 k - y2 k - 1 - z 2 k - 1 - d 2 k + d 2 搜索空间为青蛙种群的活动区域：空间过小会导致 青蛙无法找到最优点从而影响定位精度，空间过大则需 要青蛙跳动更大的次数从而影响收敛速度。本文设立 

刘 宏，王其涛，夏未君：优化混合蛙跳算法的 WSN 三维定位方法 2017，53（2） 131 搜 索 空 间 为 ：以 上 述 定 位 节 点 N 得 出 的 估 计 位 置 N(xyz) 为中心，以式（6）计算出的 h 为搜索空间的内 切球半径，由此定义搜索空间范围： h = 1 k k å i = 1 d i （6） 2.3 混合蛙跳算法及其优化 混合蛙跳算法是由人类对生物界观察、探索进而模 仿而创造出的一种较高效的科学寻优方法。该算法以 青蛙种群集体寻找食物为基础、以种群分组实现信息交 换为重点、以子群内部交流和全局信息交换为中心来实 现寻优的整个过程，从而实现搜索寻优的目的。以下为 其数学模型[14]： 步骤 1 随机生成初始种群。共生成 P 只青蛙，维数 )。 可以根据需要任意设定，本文设定为三维：X = (x x a1 x a2 a3 a 步骤 2 排序。按照实际情况设计适应度函数，计算 P 只青蛙的适应值并从小到大排列。 步骤 3 分组。分为 m 个子群，单个子群包含 n 个青 蛙。分组按交替原则进行，把排序后序号为 1 到 m 的青 蛙取出，按照降序每个子群各放 1 只，再把序号为 m + 1 到 2m 的青蛙取出也按照降序每个子群放一个，以此类 推，直到把所有青蛙划分完毕。 步骤 4 子群搜索。确定子群内搜索次数，完成一个 子群搜索后再进行下一个子群的搜索，直到所有的子群 都搜索完毕，搜索细节如下： （1）确定最好和最差的青蛙。群体中的青蛙必然存 ，最差的青蛙 在好坏，所有子群中最好的青蛙表示为 X 表示为 X w ，种群中最好的青蛙表示为 X g b 。 步骤 6 判断。若达到全局信息交换次数 K 则输出 最优解，否则返回步骤 3。 由于上述步骤 4 中的子群更新策略导致算法存在 局部最优、收敛速度较慢等问题，同时为了提高算法精 度，现对子群中 X 的更新算法式（7）进行优化： w D = C × rand( ) ´(X - X (1 - C)× rand( ) ´(X g ) + - X ) w w b （9） 式中，C 为权重系数，初始值为 1，子群内部每进化一定 次数则对 C 进行一次调整，如式（10）所示： {F = Ne/10 newC = C - 0.1 （10） 式中，Ne 为子群搜索次数，newC 为调整后的权重系 数。子群每搜索 F 次，则用 newC 代替 C 完成一次权重 系数的调整。这种方法实现了子群内部搜索过程青蛙 跳距的由大到小的动态变化，进而实现了子群搜索区域 由大到小的变化，平衡了全局寻优与局部搜索，保持了 种群的多样性，从而提高了算法的收敛速度，跳出了局 部最优解，提高了解的质量。 2.4 适应度函数设计 适应度函数值用来衡量蛙跳定位算法当前解的优 劣，因此设计合理的适应度函数就显得尤其重要，故本 文关于三维定位算法的适应度函数设计如下。当前蛙 跳算法寻到的最优点 (xyz) 到锚节点 M ) 的 估计距离和测量距离 d 有如下关系： y i z i (x i i i = ε i 式中，ε i (x - x )2 + (y - y | || 为估计距离与测量距离之间的误差，则待定位 ，1  i  k （11） )2 + (z - z )2 - d | || i i i i （2）改进最差青蛙的位置。最差青蛙 X 按如下方 w 节点 N 周围 k 个锚节点的误差和为： 式调整： D = rand( ) ´(X newX = oldX - X ) b w + D ，D w w  D  D max min （7） （8） 式中，rand( ) 用于生成随机数，大小在 0 到 1 之间，D 为青蛙的最大跳距，D max 为最小跳距。在此过程中，青 min 蛙跳动寻找优于 X w 的位置，如果找到了就更新最差青 蛙，否则进行下一步。 （3）用种群最好的青蛙 X g 取代子群中最好的青蛙 重复计算式（7）、（8），如果依然没有找到更好的位置 X b 用来改善子群内最差的青蛙 X ，则进行下一步。 w （4）生成一个随机青蛙，无论这个青蛙的优劣，都用 f (xyz) = å k i = 1 ε i （12） f (xyz) 的值越小，则待定位节点位置和真实节点位置 越接近，估计坐标精度越高。但是，由于存在测距误差， 距离待定位节点距离不同的锚节点对其定位精度的影 响力是不同的，待定位节点和锚节点的距离越近，测距 误差越小 [15]。故引入权值控制不同距离的锚节点对定 位结果的影响，即距离较小的锚节点赋予较大的权值， 反之距离较大的锚节点赋予较小的权值，因此选择 d i 的倒数作为加权系数，故适应度函数为： min f (xyz) = å k 1 d i = 1 i ε i （13） 它取代 X 。 w 2.5 蛙跳定位算法流程 步骤 5 混合子群。在完成 m 个子群进化后，把所 综上所述，WSN 三维定位方法的具体实现过程如 有子群混合按步骤 2 中的方法重新排序。 图 2 所示。 

132 2017，53（2） Computer Engineering and Applications 计算机工程与应用 ML 计算坐标 (xyz) ， 按式（6）计算搜索区域 指定算法参数：种群中候选解个数 P ， 子群个数 m ，子群内解个数 n ，全局信 息交换次数 K ，子群内搜索次数 Ne 构造初始种群 种群中每只青蛙（候选解）按 式（13）计算适应值 f (xyz) 全局寻优 未达到全局交换数 K 否 是 种群中的青蛙进行分组 每个子群按式（8）（9）进行子群局部寻优 否 达到子群内部搜索次数 Ne 局部搜索 是 混合各子群中的青蛙 输出最优解作为待定位节点位置 图 2 算法流程图 3 仿真实验 3.1 实验设计 q å j = 1 avg = - - y x j j - z qR （14） 实验以 MATLAB2010b 软件为平台进行。仿真的 三维空间为 100 m3 的正方体，设定节点总数为 100 个， 锚节点的通信半径 R 为 50 m。共 50 个青蛙子群，每个 子群中有 35 只青蛙，子群内部搜索次数为 50，种群全局 信息交换次数为 100，以平均定位误差作为定位算法的 评价标准，如式（14）： - - x )2 + (y - - y )2 + (z - - z (x )2 j j j j j j 式中，( ) 为待定位节点 j 的真实坐标，(x j j 为待定位节点 j 的经蛙跳迭代后寻找到的最优坐标，q 为未知节点数。 y j z j ) 实验按如下情况进行： （1）OSFLA算法与SFLA算法性能及时间复杂度对比。 （2）OSFLA 算法、SFLA 算法和 ML 算法在相同测距 误差、锚节点密度和连通度下的定位精度和稳定性对比。 3.2 实验结果分析 （1）OSFLA 算法与 SFLA 算法性能对比 在测距误差为 20%的情况下 OSFLA 与 SFLA 两种 算法进行比较，仿真结果如图 3 所示。由图 3（a）、（b）可 看出：当迭代 10 次后，OSFLA 算法较 SFLA 算法适应值 明显降低，表明 OSFLA 算法比 SFLA 算法有更高的收敛 精度。OSFLA 算法和 SFLA 算法适应值在连通度为 5 时 的差值比连通度为 10 时适应值的差值要大，说明 OSFLA 算法在较小连通度下性能更优，更加适应锚节点较少的 环境。 0.8 0.7 0.6 0.5 0.4 0.3 0.2 0.1 1.3 1.2 1.1 1.0 0.9 0.8 0.7 0.6 0.5 0.4 0.3 值 应 适 值 应 适 SFLA OSFLA 0 10 20 30 40 50 60 70 80 90 100 总进化迭代数 （a）连通度为 5 SFLA OSFLA 0 10 20 30 40 50 60 70 80 90 100 总进化迭代数 （b）连通度为 10 图 3 不同连通度下 OSFLA 算法与 SFLA 算法性能对比 （2）测距误差与定位精度的关系 设定锚节点比例为 20%。为了模拟在现实环境中 含有误差的测量距离，用实际距离中乘以误差系数来实 现。由此仿真出不同测距误差下的三种算法的定位误 差曲线，如图 4 所示。从结果看出这三种算法的平均定 位误差都会随着测距误差的变大而增大，OSFLA 算法 曲线斜率最低，SFLA 算法次之，ML 算法最差；当测距 50 45 40 35 30 25 20 15 10 5 0 / % 差 误 位 定 均 平 ML SFLA OSFLA 5 10 15 20 测距误差/% 25 30 图 4 不同测距误差与平均定位误差的关系对比 

刘 宏，王其涛，夏未君：优化混合蛙跳算法的 WSN 三维定位方法 2017，53（2） 133 误差 20%时，ML 算法比 OSFLA 算法大 12.45%，SFLA 算法比 OSFLA 算法大 3.12%，且随着测距误差的增加， 差值不断扩大，说明OSFLA算法具有更强的抗干扰能力。 （3）锚节点密度与定位精度的关系 比较三种算法在不同锚节点密度环境下的平均定 位误差，仿真结果如图 5 所示。从图中可以看出：这三 种算法的平均定位误差都会随着锚节点密度的增加而 下降。当锚节点密度为 15%时，OSFLA 算法、SFLA 算 法和ML算法的平均误差分别为17.17%、20.11%、31.26%； 当锚节点密度为 40%时，平均定位误差则下降为 14.27%、 15.43%、23.46%。由此得出 OSFLA 算法平均定位误差 最低，且下降幅度更为平缓，对网络中锚节点的数量要 求更低，SFLA 算法次之，ML 算法最差。 / % 差 误 位 定 均 平 35 30 25 20 15 10 15 ML SFLA OSFLA 20 25 30 35 40 锚节点密度/% 图 5 不同锚节点密度环境下平均 定位误差关系对比 （4）平均连通度与定位精度的关系 连通度对定位结果的影响也是评价算法性能的重 要指标之一，比较三种算法在不同连通度环境下平均定 位误差，仿真结果如图 6 所示。结果表明三种算法都会 随着连通度的提高而降低平均定位误差：OSFLA 算法 下降了 2.45%、SFLA 算法下降了 4.41%、ML 算法下降了 9.76%。而且 OSFLA 算法在连通度较低的情况下仍然 保持了较好的定位精度。 40 35 30 25 20 15 10 / % 差 误 位 定 均 平 ML SFLA OSFLA 5 6 7 8 9 10 11 12 平均连通度 图 6 不同连通度环境下平均定位 误差关系对比 （5）稳定性与时间复杂度分析 在锚节点比例 20%的情况下，测试 ML 算法、SFLA 算法、OSFLA 算法的定位误差的平均值和标准差，以及 每个未知节点的平均定位时间，结果如表 1 所示：OSFLA 算法比 SFLA 算法及 ML 算法的平均定位误差和标准差 都要小，说明OSFLA算法定位精度和稳定性更高；OSFLA 算法平均定位时间比SFLA算法略快0.0351 s，小于0.05 s， 说明 OSFLA 算法的效率与 SFLA 算法相当。 表 1 稳定性与时间复杂度 算法 ML SFLA OSFLA 平均值 0.271 7 0.185 5 0.165 7 标准差 0.056 4 0.024 5 0.021 3 平均运行时间/s — 4.627 6 4.662 7 4 结束语 提出了优化混合蛙跳算法（OSFLA），并将 OSFLA 算 法应用于三维定位：设立搜索区域后，应用 OSFLA 算法 根据适应度函数迭代求精，得出节点的三维坐标。仿真 结果表明：OSFLA 算法较传统的混合蛙跳算法（SFLA） 在收敛速度和精度上有一定的改善，且在三维定位的计 算中，OSFLA 算法相比 ML、SFLA 算法，具有更好的定 位效果。 参考文献： [1] 王营冠，王智.无线传感器网络[M].北京：电子工业出版社， 2012：1-15. [2] Mert B，Liu M，Shen W M，et al.Localization in cooper- ative wireless sensor networks：a review[C]//Proceedings of the 2009 13th International Conference on Computer Supported Cooperative Work in Design，2009，23（4）： 438-443. [3] Cui Huanqing，Wang Yinglong.Four mobile beacon assisted localization in three-dimensional wireless sensor networks[J]. Comput Electric Eng，2012，38（3）：652-661. [4] Zhang Zhangxue，Cui Huanqing.Localization in 3D sensor networks using stochastic particle swarm optimization[J]. Wuhan Univ J Nat Sci，2012，17（6）：544-548. [5] Kumar A，Khosla A，Saini J S，et al.Stochastic algorithms for 3D node localization in anisotropic wireless sensor networks[C]//Proceedings of Seventh International Con- ference on Bio-inspired Computing：Theories and Appli- cations（BIC-TA 2012），Advances in Intelligent Systems and Computing.New Delhi：Springer India Private Ltd， 2013，12（3）：111-114. （下转 140 页）