无线传感器网络定位技术的研究

卞国龙， 黄海松， 王安忆， 魏 琴

(1.贵州大学 a.现代制造技术教育部重点实验室，b.贵州省大数据产业发展应用研究院，贵阳 550025; 2.中国海洋大学 工程学院，山东 青岛 266100)

·计算机技术应用·

无线传感器网络定位技术的研究

卞国龙1a， 黄海松1a， 王安忆2， 魏 琴1b

(1.贵州大学 a.现代制造技术教育部重点实验室，b.贵州省大数据产业发展应用研究院，贵阳 550025; 2.中国海洋大学 工程学院，山东 青岛 266100)

提出了一种新的接收信号强度指示(RSSI)定位修正算法。该算法采用改进的退火算法对极大似然估计处理后的距离进行优化，有效解决在实际环境中遇到的一些问题，使算法更符合实际。同时，能有效降低运算的复杂度，并排除具有特征相似性的一些奇异点，提高精度。依据邻近节点间的距离，分析前后两组估计坐标间的关系，用目标函数判断两组解的优劣，由退火思想只接受比前一组优的新解进行迭代循环，可以得到一组移动点的估计坐标。将满足条件的移动点看做参考点，重复运算, 直至没有移动点可以升为参考点为止, 输出最终结果。实验结果表明, 改进的算法有效可行，且定位精度和稳定性有明显的提高，是一种可行的节点定位方案。

节点定位； 无线网络； 模拟退火法； 距离修正

0 引 言

随着物联网技术的发展，无线传感器网络(Wireless Sensor Networks，WSNs)技术得到了广泛应用[1]。定位技术是WSNs技术的重要研究方向，定位算法的研究已成为当前的热点方向。现有的定位算法从定位手段上分为基于测距(range based)和非测距(range-free)两大类[2]。基于测距的算法需要节点有测距功能，利用节点间距离或角度信息，使用三角定位、三边定位或极大估计等方法计算节点位置，主要算法有接收信号强度指示 (Received Signal Strength Indicator，RSSI)、基于到达时间 (TOA)、基于到达时间差 (TDOA)等；后者通过网络的连通性定位，主要有质心算法等[3]。由于目前的传感器都有RSSI值读取功能，可以通过RSSI算法计算节点距离，但RSSI值易受环境干扰，和通信半径相比，测距的绝对误差有时会达到40%。三边定位算法是由移动点测得与周围3个参考点的距离，分别作3个圆，在理想情况下3圆交于一点，通过几何计算可得移动点坐标，但由于噪声的存在使得3个圆不能交于一点[4]。本文提出了RSSI 距离修正算法，在圆不相交的情况下提高定位的准确性。同时针对移动曲线受客观因素影响导致不平缓，使准确性和稳定性受到影响等问题，引入一种改进的模拟退火算法(Simulated Annealing，SA)来对估算出的位置坐标信息处理。退火算法是基于Monte-Carlo迭代求解策略的一种随机寻优的全局优化算法，再通过距离修正进行误差补偿[5]。通过实验证明该方法确实可行并能提高定位精度。

1 定位基础原理

选用对数-正态分布模型，设环境中有n个移动点，m个参考点，共N个节点。n个移动点坐标参数向量T=[Tx，Ty]，其中Tx= [x1，x2,…,xn]，Ty=[y1，y2,…,yn]。在节点a和b之间距离为d时接收功率Pab的分布可以表示为：

(1)

(2)

(3)

(4)

(5)

图1 定位结构原理图

2 RSSI定位技术优化

2.1 无线信号的传输模型

常用的模型有自由空间模型、对数-正态分布模型和哈它模型等。自由空间模型可表示为：

P(d)=32.4+10lgd+10nplgf

(6)

式中：d为接收点与发射点间距离；P(d)为距离d后的信号损耗，dB；np为路径损耗指数；f为发射频率，MHz。由于节点性能的分散性和环境的复杂性，在自由空间模型下误差会较大，对数-正态分布模型更符合实际：

(7)

式中：Xδ是均值为0的高斯随机变量；P(d0)为d=1 m时接收到的信号强度[8]。根据上式可得各点接收功率为：

RSSI=P+G-P(d)

(8)

式中：G为天线增益；P为发射功率，dB。通过接收到RSSI值和式(7)～(8)可计算距离d，从而实现定位。

图2 RSSI值的变化曲线

2.2 卡尔曼初步滤波优化

本文采用卡尔曼滤波(Kalman Filtering，KF)算法对RSSI值进行初步处理，以减少误差[9]。KF是通过消除噪声影响后，用前一时刻的估算值和现在时刻的观测值来更新状态变量，以最小均方误差来寻求递推估计的计算方法。X表示RSSI值，KF算法分为预测状态阶段和修正估计阶段两部分。预测状态阶段为：

(9)

式中：X(k/k-1)为预测结果；X(k-1/k-1)为k时刻最优状态估算值；Yk为现在状态的控制量，其值此时为0；Vk/k-1和E为系统参数，是矩阵；RX(k|k-1)是与之对应的X( k|k-1)的协方差，为k时对下一时刻误差估计的方差矩阵；P为系统噪声，表示为

(10)

式中：Wk为k+1时的预测估算值；Gk为增益矩阵，能够实时更新；Mk为系统测量参数，是预测矩阵。每次Gk和R(k/k)通过前一时刻的值更新，通过递归估计直至达到收敛效果[11]。KF算法实时性好，当模型参数的系统状态比较稳定时，能减少由噪声叠加引起RSSI值偏离，滤波后的RSSI值更稳定。

2.3 改进模拟退火算法的优化

模拟退火算法常用来解决最优化问题，其基本思路原理为：将固体加热至高温，然后逐渐冷却，加热时，固体粒子随温度升高变的无序，内能增加；冷却时粒子逐渐变得有序，在每个时刻都达到平衡，最后在常温下内能最小[12]。将退火算法的原理应用于定位中，得到基于模拟退火的定位算法。将内能模拟为成本函数E，温度T模拟为控制参数t。对于t的每次取值，都比较新旧解的成本函数，以决定是否接受新解，经过大量解变换后，可得最终解。

(1) 成本函数。表示移动点当前估计坐标的符合情况，其值越小越符合实际：

(11)

(12)

在增加距离修正系数的基础上，定义新的约束条件：

(13)

加入约束条件，可以减小移动点的可行域。因为优化的结果即要使计算距离与测量值尽量吻合，所以要使定位结果满足下式：

(14)

则引入罚函数的构造条件，新生成的成本函数为：

(15)

式中：R为惩罚因子。如果测量误差超过平均误差，则所求解远离正确值，此时要加大惩罚使其向可行解靠近。

(2) 新解的更新。解指的是所有移动点估算坐标的集合，在当前解中，随机选择节点i，然后沿方向θ移动距离L，此时i得到一个新坐标。将节点i的当前估算坐标用新坐标代替，其余节点保持不变，此时可得新解。为了优化搜索范围，当控制参数t逐渐减少时，L也会减少：

(16)

式中：L为步长，随迭代次数增加而减小，L>0；c为缩放系数，0

(17)

(18)

式中：eij为单位方向矢量，eij=(Qi-Qj)/Dij，Qi、Qj为节点i与j的坐标；集合I为节点距小于通信半径r的节点集合，I={j|dij

(3) 控制参数t的变化表示为：

(19)

式中：t为控制参数，随迭代次数增加而减小，t>0；t0为初始控制参数；j为迭代次数；z为衰减系数，0

(20)

式中：aveΔE为ΔE>0时,ΔE的平均值，其值为aveΔE=VΔE/NΔE。设初始L0=1，VΔE0=0，NΔE0=0，VΔE为ΔE>0时ΔE值之和，NΔE为ΔE>0的次数。

(21)

(22)

Ei为在状态i时的成本函数，则系统处在状态i的概率，即退火算法找到一个解i∈s的概率为：

(23)

由上式可知,得到的概率分布函数为平稳分布。H0(t)为归一化因子，可由下式求得：

(24)

由准则可知，在迭代中不仅接受使成本函数变优的值，还有概率接受使其变差的值，由此可以扩大初始搜索范围。随着t减小，搜索范围也变小，使新解保持在全局最优附近[15]。同时在设置条件阈值的基础上，通过局部更新，对解空间进行搜索，保留下式中S1的有效解，新解空间需满足下式：

(25)

(26)

式中：sji表示ti下的第j个节点的解值。采用局部更新方式进行退火更新，直至极值空间不连续，并对获得的解迭代演算，如果解空间光滑，则停止迭代。基于改进退火定位算法的运算步骤如下：

步骤2 随机选择一个移动点，根据式(17)得该点新坐标。

步骤3 由式(15)计算新解和当前解的成本函数，并计算差值ΔE。

步骤4 根据规则，决定是否接受新解。如果不接受，解集合不变；如果接受，则更新解集合中扰动点坐标[16]。如果样本坐标值sj满足

则更新当前解si；j=j+1，重复步骤4至满足条件。

步骤6 当达到终止条件时，算法终止。t改变一次表示一次迭代，L与t同步。此时的解即为所有移动点的估算坐标的解集合。

2.4 迭代结果统计

在二维区域内随机布置多个参考点和移动点，假设移动点与参考点间的测量距离误差服从高斯分布。分别采用2种算法，设置温度初始参数T=1.0，c=0.96，迭代次数为退火算法搜索的最大次数，在测距误差为6%的条件下，取迭代次数为100进行定位实验，结果如图3所示。可以看出，当迭代次数大于50次时，曲线趋于缓和，综合考虑定位节点的能耗、成本和精度，最大迭代次数可选择为50次。

图3 退火算法的迭代变化曲线

3 实验结果验证

3.1 定位实验结果与分析

分别用传统的最小二乘法和优化后退火定位法对节点多次定位，并统计多次平均误差，对误差进行比较。实验场景设置为25 m×25 m，通信半径为15 m，参考节点数为8个，移动点为15个，对每个移动点多次测量求均值，实验结果如图4、5所示。

图4 实验环境二维图

图5 定位结果统计图

由定位结果计算，可得两种算法的定位误差如表1所示。通过分析实验结果可得改进后退火算法比基于最小二乘法的RSSI算法更具有精确性。

表1 实验结果分析表

3.2 不同连通度下误差分析

网络连通度可看做网络通信范围的大小，通信范围越大，连通度越好，能检测到的节点越多。在连通度较低时达到较高的精度和减小连通度对误差的影响是定位的重要研究方向。在实验环境布置12个参考点，15个移动点，通信半径R=10 m，计算移动点坐标，重复测量，获得多次误差结果并对误差统计，比较以下3种算法的性能。由图6可知，改进的退火算法受连通度影响更小，在连通度较小时即可获得较高精度。

3.3 不同算法的定位覆盖率

在定位中，能定位出的节点数占所有移动节点的比例为定位覆盖率。在实验环境下，移动点个数为15个，参考点数目改变，3种不同算法覆盖率变化如图7所示。可以看出，随着参考节点比例增加，现有的RSSI算法的覆盖率也会增加，但变化较缓慢；而改进的退火算法在参考点数较少时就能覆盖全部，减少了系统的复杂程度。

图6 不同连通度下的定位误差

图7 参考点比例对覆盖率的影响

4 结 语

通过对智能优化算法在定位中的应用进行研究，用组合优化的方法对定位问题进行了分析。RSSI算法是无线定位中成本较低且普遍使用的方法，但易受干扰。研究分析了引起误差的环境因素，该算法首先利用RSSI算法收集节点间的信息和距离估计，并优选参考点，采用模拟退火法和极大似然法有效结合，在极大似然法的基础上引入退火算法求初始解，增加初值的准确性，有效解决了精度受其他客观因素影响的问题。最后通过实验分析各种因素的影响并进行比较，结果显示无论是定位精度还是执行时间都有所提高。下一阶段将研究测距误差对算法的影响及其改进策略。

[1] Vempaty A, Ozdemir O, Agrawal K,etal.Localization in wireless sensor networks:Byzantines and mitigation techniques[J].IEEE Journal and Magazines, 2013, 61(6):1495-1508.

[2] Yu F C, Hu G M, Park S,etal. Quorum based sink location service for irregular wireless sensor networks[J]. Computer Communications, 2012, 35(12): 1422-1432.

[3] Redondi A, Chirico M, Borsani L.An integrated system based on wireless sensor networks of patient monitoring, localization and tracking[J].AD Hoc Networks, 2013, 11(1):39-53.

[4] Ahmed N, Rutten M, Bessell T,etal. Detection and tracking using particle-filter-based wireless sensor networks[J]. IEEE Transactions on Mobile Computing, 2010,9(9):1332-1345.

[5] 闫明明,郭 涛,鲍爱达.基于ARM的无线温度传感器网络设计[J].实验室研究与探索,2014,33(3): 105-108.

[6] Kim S W,Lee J M,Lee J H.Distributed network localization for wireless sensor networks[J].Applied Mathematics &Information Sciences, 2012, 6(3):1109-1115.

[7] Deshpande N，Grant E.Target Localization and autonomous navigation using wireless sensor networks-a pseudogradient algorithm approach[J].IEEE Systems Journal，2014，8(1): 93-103.

[8] 李牧东,熊 伟,梁 青.基于人工蜂群改进算法的无限传感器网络定位算法[J].传感技术学报, 2013,26(2):241-245.

[9] Guillermo Molina, Enrique Alba. Location discovery in wireless sensor networks using metaheuristics[J]. Applied Soft Computing, 2011, 11(1): 1223-1240.

[10] 郭小军. LM567及其在测距中的应用[J].实验室研究与探索，2007，26(10): 22-23.

[11] Subhan F,Hasbullah H,Rozyyev A,etal.Handover in Bluetooth networks using signal parameters[J]. Information Technology Journal，2011，10(5): 965-973.

[12] Vecchio M, Lopez V R, Marcelloni F.A two-objective evolutionary approach based on topological constraints for node localization in wireless sensor networks [J].Applied Soft Computing,2012, 12(7):1891-1901.

[13] Güney E, Aras N, Kuban A,etal. Efficient solution techniques for the integrated coverage, sink location and routing problem in wireless sensor networks[J]. Computers Operations Research, 2012, 39(7): 1530-1539.

[14] 刘志华, 陈家兴, 陈霄凯.无线传感器网络中序列定位新算法的研究[J] .电子学报, 2010, 38(7):1552-1556.

[15] Fang S,Wang C.A Dynamic hybrid projection approach for improved Wi-Fi location fingerprinting[J].Vehicular Technology,IEEE Transactions on,2011,60(3):1037-1044.

[16] France S L, Carroll J D, Xiong H. Distance metrics for high dimensional nearest neighborhood recovery: compression and normalization[J].Information Sciences, 2012, 184(1): 92-110.

Research on Localization Technology of Wireless Sensor Networks

BIANGuolong1a,HUANGHaisong1a,WANGAnyi2,WEIQin1b

(1a. Key Laboratory of Advanced Manufacturing Technology, Ministry of Education; 1b. Guizhou Big Data Industry Research Institute, Guizhou University, Guiyang 550025, China; 2. College of Engineering, Ocean University of China, Qingdao 266100, Shandong, China)

The research of the current wireless location algorithms generally has exist the problems of low positioning accuracy and high computational complexity. A new RSSI location algorithm is proposed in this paper. The improved annealing algorithm is used to optimize the distance of the maximum likelihood estimation. It can effectively solve some of the problems encountered in the actual environment and make the algorithm more practical. At the same time, it can effectively reduce the complexity of computing. It rules out some singular points with characteristic similarity, which can improveso that the accuracy is improved. Based on the distance between adjacent nodes, the relationship between the two sets of estimated coordinates is analyzed. They can judge the advantages and disadvantages of the two sets of solutions with the objective function. By Because the annealing algorithm only accepts a previous group optimizational point to implement iteration, it can get the estimated coordinates of a set of mobile points, and can find the mobile point which meets the conditions as a reference point. Then the operation is repeated until no moving point can be raised as a reference point, and the final result is outputted. The experimental results show that the improved algorithm is effective and feasible. The positioning accuracy and stability are obviously improved. It is a feasible node localization scheme.

node localization; wireless network; simulated annealing method; distance correction

2016-08-21

国家自然科学基金项目(51475097)；国家科技支撑计划项目(2014BAH05F01)；贵州省科技基金项目(黔科合J字[2015]2043)；贵州省科技支撑计划(黔科合GZ字[2015]3034);贵州省基础研究重大专项(黔科合JZ字[2014]2001)

卞国龙(1989-)，男，山东潍坊人，硕士生，主要研究方向为机械自动化，制造物联。

Tel.：18302639061;E-mail:1099205144@qq.com

黄海松(1977-)，女，贵州大方人，博士，教授，博士生导师，主要研究方向为制造业信息化，先进制造技术。

TP 391

A

1006-7167(2017)06-0122-06