基于RSSI测距的三维无线传感网络萤火虫定位算法的研究①

张立国马 鹏 金 梅 范美常 刘宇浩



基于RSSI测距的三维无线传感网络萤火虫定位算法的研究①

张立国②马 鹏 金 梅 范美常 刘宇浩

(燕山大学河北省测试计量技术与仪器重点实验室 秦皇岛 066004)

研究了三维空间无线传感器网络(WSN)未知节点的定位。针对目前三维空间无线传感网络定位算法精度低的问题，提出一种基于接收信号强度指示(RSSI)测距的萤火虫定位的算法。该算法首先利用RSSI进行测距，建立信号强度随传播距离衰减的模型，然后在已知一定数量的锚节点的情况下，通过萤火虫算法寻找目标函数最优值，进而对未知节点进行定位。仿真验证结果表明，该定位算法相比其他算法定位精度有很大提高，在30m×30m×30m的空间内定位误差仅为0.59m。

无线传感网络(WSN)，三维空间，接收信号强度指示(RSSI)，萤火虫算法(FA)

0 引 言

无线传感网络(wireless sensor networks, WSN)节点位置对整个网络的应用有重要影响，因此节点定位技术在无线传感网络中有着举足轻重的地位。迄今为止无线传感网络的定位方法大都针对二维空间，而在实际应用中网络节点主要分布在三维空间，因而较好的三维空间定位方法有着良好的发展前景。节点定位不但要考虑定位精度，而且要考虑定位成本和复杂度。目前国内外针对此问题提出了多种算法。例如胡伟等人提出了一种基于四面体质心迭代的三维近似三角形内点测试(approximate point-in-triangle test, APIT)定位算法[1]，该算法虽提高了节点覆盖率，减小了计算量，但是实验过程较为复杂，不容易实现；印第安大学的Zhang等提出了一种Landscape-3D定位算法[2]，此方法节点间无需通讯，减小了功耗，但其存在即时迭代过程计算量大，LA装置在移动过程中要严格保持同步等缺点；Zhang等[3]利用粒子群优化(particle swarm optimization，PSO)算法进行节点定位，但此算法容易陷入局部最优且计算比较复杂。此外还有多种测距和定位算法[4]以及DV-Hop定位算法和改进的混合蛙跳算法[5]。

本研究采用接收信号强度指标(received signal strength indicator, RSSI)方法实现测距，并且对所测数据进行统计加权处理来减小环境等因素造成的测量误差，建立起距离与信号强度之间精确的衰减模型，然后用萤火虫算法对未知节点进行定位，并且与传统的四边测量算法[6]以及交叉粒子群算法[7]和遗传算法[8]进行对比，结果表明，萤火虫算法的定位精度明显高于四边测量算法、交叉粒子群算法和模拟退火算法，并且四点定位分八次测量再取均值的方法误差最小，定位精度最优。

1 RSSI测距

1.1 RSSI测距原理

无线信号传输过程中，信号强度会随着距离的增大而衰减。因此，接收信号强度指示(RSSI)测距原理是将信号强度的衰减转变成信号的传播距离，利用信号强度的衰减与传播距离之间的函数关系来估测传播距离[9，10]。

通常信号衰减模型采用对数——常态分布模型来获得距离信息，但在实际测量时，通常将上述模型转换为阴影模型，如下式所示：

RSSI=-10n×lgd+A

(1)

式中，RSSI为接收信号强度，单位为dBm；n为衰减因子，其值与环境有关；d为接收端与发射端之间的距离，单位为m；A为信号传播单位距离时接收到的信号强度，显然，A与n的值决定了RSSI与d的大小。

1.2 数据的统计加权

由于RSSI测量结果容易随环境变化而产生误差，因此有必要对测量数据进行加权处理以减小其误差[11]。

本文提出了一种利用测量中值对数据进行统计加权处理的方法。设每组数据测量次数为n，然后将数据按照从小到大顺序排列，因此数据中值定义如下式所示：

(2)

MRSSI即为测量中值，再求出各个RSSI值和测量中值之间的方差，如下式所示：

Di=(RSSIi-MRSSI)2

(3)

为了避免方差为零，进行加权系数处理，Pi为加权系数，用下式表示：

(4)

对加权系数进行求和处理，Fi为归一化加权系数，用下式表示：

(5)

由式(3)、(4)、(5)可以看出，测得的RSSI值与测量中值MRSSI相差越大，加权系数Fi的值越小，即所占比重越小；当RSSI值与MRSSI值相等时，加权系数Fi值最大，此时RSSI值被赋予最大权重。

此方法的优点在于以测量中值为基础计算权值，将包含粗大误差结果的RSSI值赋予很小的权值，累加时可以忽略，这样既没有简单的删掉粗差数据，又能滤除一部分粗大信号，使得RSSI测距方法能够适应更加复杂的环境。

2 萤火虫算法

2.1 萤火虫算法简介

萤火虫算法(firefly algorithm,FA)是由剑桥学者Yang在2009年提出的一种基于生物群智能的随机优化算法[12]，随后应用在寻优问题上，并能够成功寻找到函数最优解。

2.2 萤火虫算法实现定位

萤火虫之间均可以相互吸引，且由亮度低的向亮度高的靠近，发光强度由目标函数决定[13,14]。

(6)

f(x, y, z)=

(7)

(8)

程序执行步骤如下：

步骤1：获取锚节点与未知节点间距离。

步骤2：初始化萤火虫种群，在指定范围内随机分布萤火虫。

步骤3：计算目标函数值，目标函数越优，则自身亮度越高，萤火虫所处位置越好。

步骤4：比较萤火虫之间的发光亮度，更新萤火虫位置产生新解，如果迭代次数到达设定值，跳至步骤6。

步骤5：计算目标函数值，跳至步骤4。

步骤6：输出结果，程序结束。

3 实验分析

3.1 RSSI测距

测距实验采用TI公司生产的CC2530开发板来实现测量两节点之间的RSSI值。一般情况下，无线传感网络部署地区大多数在户外进行，因此本实验也选择在户外测取数据。实验一共测得50m内的RSSI值，由于距离较短时衰减变化比较明显，当距离较远，到达一定程度时，衰减变化不大，因此前30m每隔1m测量一次，后20m每隔4m测量一次。实验硬件和测量现场如图1、图2所示。

图1 zigbee CC2530硬件开发板

图2 测量现场图

实验时，每个位置测量30组数据，然后按照上述方法对数据进行统计加权处理，得到表1所示的数据。

表1 距离-RSSI值数据表

将所得数据带入式(1)，利用最小二乘法求出A与n的值为：A=-31.1949，n=2.5552，因此得到RSSI值与距离d之间的关系如下所示：

RSSI=-10×2.5552×lgd-31.1949

(9)

得到的原始数据和拟合曲线如图3所示。

图3 拟合曲线图

由图3拟合曲线图可以看出，得到的拟合曲线基本上和原数据点一致，并且拟合曲线斜率随着距离的增大而减小，说明RSSI值在距离较短阶段变化十分明显，而随着距离的增加，斜率变小，拟合曲线趋于平缓，RSSI值也趋于稳定。图4是相对误差图，从图4可以看出，原始数据和得到的拟合曲线上的数据，误差基本上都在5%以内。因此采用上述统计中值加权的处理方法，能够有效地减小误差，适应环境变化。

图4 相对误差图

使用zigbeeCC2530节点进行测距实验。该方法简单，成本低廉，利用干电池能够工作半年以上，并且经过仿真验证，精度较高，因此，用此方法进行测距实验能够在较低成本的情况下，获得较高的精确度，是一种很不错的定位测距方法。

3.2 萤火虫算法定位

由于高度受限，太高的地方无法进行节点设置，因此本实验在30m×30m×3m的长方体区域内进行，如图5所示。实验现场图如图6、图7所示。

图5 实验节点设置图

图6 节点高度设置图

图7 现场整体布局图

表2 定位数据表

首先协调器节点与电脑相连，建立无线传感器网路，随后，作为终端发射信号的未知节点和作为路由器的8个锚节点打开，开始加入网络。未知节点发射信号，8个锚节点接收信号，将自己接收到的信号强度传递给协调器节点并在电脑上显示[15]。

本文先选取A、E、F、H 4个点(选取点的原则为4点不共面，且未知节点在4点所构成的区域内)对未知节点N进行定位，将萤火虫数量设置为30，迭代次数为200，用MATLAB仿真的效果如图8所示。

图8 萤火虫初始分布图

图9 萤火虫最终分布图

接下来，用8个锚节点共同为未知节点定位，本次将萤火虫数量设置为60，迭代次数设置为300，仿真效果图如图10所示。

图10 萤火虫初始分布图

图11 萤火虫最终分布图

3.3 对比实验分析

依据上述仿真实验，当锚节点个数分别设置为4,5,6,7,8时(每个锚节点只利用一次，一起进行定位；当锚节点个数取8时，区别于上述8组四个节点平均值的方法)，萤火虫定位算法与交叉粒子群算法和遗传算法相比较，如图12所示。

从图12可以看出，萤火虫算法相比于这两种智能算法有着更精确的定位精度，将8组4个节点萤火虫定位算法与传统的四边定位算法加入对比，得到的比较结果如表3所示。

图12 三种算法对比图

算法名称锚节点数定位坐标定位误差(m)四边测量定位法4(12.15,15.55,0.95)3.09交叉粒子群算法8(15.34,18.72,1.07)1.62遗传算法8(15.28,18.16,2.23)1.88单次四个节点萤火虫定位算法4(15.31,21.13,1.19)1.42八个节点萤火虫定位算法8(15.12,21.26,2.4)1.23八组四个节点萤火虫定位算法平均值8(15.07,20.57,2.13)0.59

经比较，采用8组四个节点萤火虫定位算法平均值，不但充分利用上了全部8个锚节点，并且定位精度要远远高于传统的四边定位算法以及交叉粒子群算法和遗传算法的智能算法，相比于单次四个节点萤火虫定位方法和八个节点萤火虫定位方法，能够有效地将定位误差控制在1 m以内，因此效果最好。

4 结 论

本文主要提出了一种基于三维空间无线传感网络的萤火虫定位算法，打破了二维空间定位算法的局限性。该算法首先用RSSI方法对锚节点和未知节点之间进行测距，得到稳定的拟合曲线，然后利用加权算法处理误差，最后在此基础上利用测距结果使用萤火虫算法对未知节点进行定位。经过仿真验证，该算法相比于传统的四边定位算法以及交叉粒子群算法和遗传算法，在定位精度上有了很大的提高，在30m×30m×3m的空间内定位误差仅为0.59m，对于分布在三维空间上的无线传感网络节点的定位具有很好的理论和实际意义。

[ 1] 胡伟, 朱西平, 文红等. 基于四面体质心迭代的三维 APIT 定位算法研究.传感技术学报, 2013, 26(10): 1432-1436

[ 2] Zhang L, Zhou X, Cheng Q. Landscape-3D: a robust localization scheme for sensor networks over complex 3D terrains.Local Computer Network, 2006, 31st: 239-246

[ 3] Zhang Z, Cui H. Localization in 3D sensor networks using stochastic particle swarm optimization. Wuhan University Journal of Natural Sciences, 2012, 17(6): 544-548

[ 4] Dalce R, Val T, Bossche A. Comparison of indoor localization systems based on wireless communications. Wireless Engineering and Technology, 2011, (2):240-256

[ 5] 冯晨, 张玲华. 改进混合蛙跳算法在无线传感网定位中的应用. 计量学报, 2013, 34(004): 360-365

[ 6] 文举, 金建勋, 袁海. 一种无线传感器网络四边测距定位算法. 传感器与微系统, 2008, 27(5): 108-110

[ 7] 王俊, 李树强, 刘刚. 无线传感器网络三维定位交叉粒子群算法. 农业机械学报, 2014, 45(5): 233-238

[ 8] 王金鑫, 赖旭芝, 吴敏. 基于遗传算法的三维无线传感器网络定位新算法. 高技术通讯, 2008, 18(6): 579-584

[ 9] 徐世武, 王平. ZigBee 技术中基于 RSSI 测距的定位算法研究.单片机与嵌入式系统应用, 2012, 12(1): 1-3

[10] Zhu X, Feng Y. RSSI-based algorithm for indoor localization. Communications and Network, 2013, 5(02): 37-42

[11] 陶金龙, 康志伟, 骆坚. 基于 RSSI 测距的加权概率定位算法.电子测量与仪器学报,2014, 28(10): 1123-1129

[12] Yang X S. Firefly algorithms for multimodal optimization.Stochastic algorithms: foundations and applications. Springer Berlin Heidelberg, 2009. 169-178

[13] 高伟明. 萤火虫算法的研究与应用：[硕士学位论文]. 兰州：兰州大学, 2013. 18-22

[14] 王吉权, 王福林. 萤火虫算法的改进分析及应用. 计算机应用, 2014, 34(9): 2552-2556

[15] 王瑛辉, 石理碧, 孙坚. 基于 ZigBee 技术的无线传感器网络在能源计量系统中的应用. 计量技术, 2013, 11: 30-32

Research on a firefly localization algorithm based on RSSI ranging for 3D wireless sensor networks

Zhang Liguo, Ma Peng, Jin Mei, Fan Meichang, Liu Yuhao

(Measurement Technology and Instrumentation Key laboratory of Hebei Province,Yanshan University, Qinhuangdao 066004)

The techniques of localizing the unknown nodes of 3D wireless sensor networks (WSN) were studied. Aiming at the problem of low localization accuracy of current localization algorithms for 3D wireless sensor networks, a firefly localization algorithm based on the ranging using received signal strength indication (RSSI) for 3D wireless sensor networks was proposed. The algorithm uses RSSI to measure the signal-propagating distance and models the attenuation of signal strength with the signal-propagating distance, and then, uses the firefly algorithm to find the optimal value of the objective function to locate unknown nodes under the condition that a certain number of anchor nodes are known. The simulation results showed that the localization accuracy of the new localization algorithm was greatly higher than current algorithms, and its localizing error in the space of 10m×10m×10m was just 0.59m.

wireless sensor network (WSN), three-dimensional, received signal strength indication (RSSI), firefly algorithm (FA)

①河北省自然科学基金(F2015203392)和秦皇岛市科技计划(201502A043)资助项目。

2015-10-20)

10.3772/j.issn.1002-0470.2016.01.001

②男，1978年生，博士，副教授；研究方向：惯性导航，三维立体重构及智能信号处理；联系人，E-mail: zlgtime@163.com(