RSSI-Based Differential Correction Least-Squares-Quasi-Newton Positioning Algorithm*

CHENG Xiuzhi，ZHU Darong，ZHANG Shen，ZHU Guang

(1.School of Mechanical and Electrical Engineering，Anhui Jianzhu University，Hefei230022，China; 2.CUMT-IoT Perception Mine Research Center，Xuzhou Jiangsu 221008，China)

RSSI-Based Differential Correction Least-Squares-Quasi-Newton Positioning Algorithm*

CHENG Xiuzhi1，ZHU Darong1，ZHANG Shen2*，ZHU Guang1

(1.School of Mechanical and Electrical Engineering，Anhui Jianzhu University，Hefei230022，China; 2.CUMT-IoT Perception Mine Research Center，Xuzhou Jiangsu 221008，China)

A least－squares differential correction based on RSSI－Newton location algorithm is presented in accordance with the low positioning accuracy lying in the Wireless Sensor Network(WSN)in this paper.In terms of RSSI ranging，correction coefficient had been firstly acquired by self－correcting of beacon nodes，and then had been applied to distance solving from unknown nodes to the beacon nodes;in terms of positioning calculations，utilizing character of simpleness of LS and the fast rate of convergence of Quasi－Newton algorithm，the initial value worked out by Quasi－Newton algorithm had been applied for the iterative refinement of unknown node coordinate with LS method.The simulation experiment showed that the accuracy of positioning algorithm presented is36%higher compared with the traditional LSmethod.

WSN;received signal strength indication;least squares;quasi－Newton method;differential correction

节点定位是WSN的关键技术，定位的精度对其所监测的区域有着至关重要的影响。传统的获取节点位置的信息主要采用GPS定位方法来实现，但是考虑到价格、体积、能耗等方面的因素，GPS定位不可能大规模的布置在监测区域，因此有必要采取简单有效的定位算法来满足大多数WSN应用场合的需求［1］。

目前，针对WSN提出的定位算法大体可以分为两类［2－6］:基于距离的定位算法(Range－Based)和与距离无关的定位算法(Range－Free)［3］。前者需要测量相邻节点间的绝对距离或者角度信息［4］，使用较多的测距定位技术有RSSI，TDOA，AOA，TOA［5］;后者需知道传感器网络的连通性等信息［6］。其中，RSSI具有定位算法简单、成本低、功耗小且无需额外的硬件等优势被广泛应用。但在实际环境中，基于RSSI的测距技术受环境的影响非常大，使得该技术在环境恶劣的情况下，定位误差较大，精度不高。在定位计算上，由于最小二乘法在定位过程中可能存在非奇异矩阵，导致最小二乘法估计出来的未知节点坐标不仅误差大，而且定位精度的稳定性差，甚至出现错误的结果。

近年来许多国内外学者提出很多针对RSSI技术的定位算法，文献［7］提出了距离未知节点最近的信标节点作为参考节点对RSSI测距进行差分校正。文献［8］采用了混合滤波的方法对RSSI的值进行优化。文献［9］首先通过加权的方式优化RSSI值，然后将粒子群算法应用到定位计算中。然而在实际环境中，基于RSSI的测距技术受环境的影响非常大，若只对RSSI值进行优化，定位误差依然很大，即便有些方法在定位过程中通过智能优化算法计算，但对初值依赖较大，容易陷入局部最优解，导致定位精度的误差很大。基于此，本文提出了一种基于RSSI差分校正的最小二乘－拟牛顿定位算法。测距阶段，该算法主要是利用信标节点的定位误差，对未知节点到信标节点的距离进行修正;定位阶段，将最小二乘法估计出来的未知节点坐标，作为拟牛顿法的初值，对未知节点坐标进行迭代求精。

第1节中给出并讨论了无线电损耗模型、给出了差分校正的方法及信标节点自动校正的定位过程。第2节介绍了本文中最小二乘－拟牛顿法的具体实现过程。第3节通过本文提出的算法与其他算法仿真实验，从各个方面对本文算法进行评价。最后，给出本文的总结。

1 基于差分校正的无线电传播损耗模型

1.1 无线电传播损耗模型

在无线传感器网络定位算法中，常用的测距技术有RSSI定位技术［10］。一方面，传感器本身的通信功能及其具有的RSSI测量功能使得测距简单。但另一方面，当定位环境中存在较严重的多径效应、反射、折射等干扰时，RSSI的测量误差就会很大，定位误差也随之增大。目前常用的信号传播模型主要有自由空间传播损耗模型与对数－常态分布模型。

自由空间传播损耗模型:

式中，P(d0)是无线电传播距离d0的路径损耗，k为路径损耗因子，通常取2～5之间，f为信号的频率。

对数－常态分布模型:

式中，P(d)是传输距离为d的路径损耗，P(d0)是传输距离为d0=1 m时的路径损耗，ξn为均值为0的高斯随机分布函数。

节点接收信标节点的信号强度为:

式中，RSSI为接收到的功率，Psend为发射功率，Pamplify为天线增益，通过式(1)～式(3)可求节点间的距离d。

实际环境中由于障碍物等环境因素的影响，测距出来的RSSI值并不能直接满足无线电传播损耗模型，若仍采用该模型而不对RSSI的值进行修正［9］就会引起定位精度偏低。本文利用离未知节点最近的信标节点在定位过程中产生的校正系数反馈给未知节点，未知节点通过该误差校正系数求出到信标节点的校正距离。该方法从测距存在的误差方面对算法进行改进，从根本上减小了对定位结果的影响，因而能够提高定位精度。

1.2 信标节点的自校正定位过程

如图1所示，信标节点A0(x0，y0)距离未知节点O最近，该信标节点距其通信范围内的信标节点A1(x1，y1)、A2(x2，y2)、……Ai(xi，yi)的实际距离为d01，d02，d03，…，d0i，信标节点A0(x0，y0)通过RSSI测距所得到的与其他信标节点间估计距离分别为^d01，^d02，^d03，…，^d0i，令^A0(^x0，^y0)为差分信标节点。

图1 信标节点的差分校正定位示意图

(1)信标节点的校正系数:

式中，n是未知节点通信半径内的所有信标节点个数。传感器网络中的其他信标节点也可以通过以上方法获得自身的校正系数，以便对其最近的未知节点进行校正。β表示使用信标节点的信息测量RSSI值时的差分校正系数。

(2)信标节点到未知节点的校正距离:

式中，di是差分校正后的未知节点的估计距离;d0'i是未知节点O到信标节点的测量距离;β是信标节点的校正系数。

2 最小二乘－拟牛顿法

2.1 最小二乘法［11］

在WSN中，若未知节点获得3个或者3个以上能够与其相互通信的信标节点的信息，则执行三边定位法或最大似然估计法即能够求出未知节点的估计坐标。假设某一未知节点p坐标为(x，y)测得到m个信标节点的距离，第i个信标节点的坐标为(xi，yi)，未知节点p到信标节点i的距离为di。假设有n个未知节点，则未知节点p的坐标可以根据式(6)方程组估计。

上述方程组可以转化为AX=b的形式。其中，

因此，方程AX=b利用最小二乘法解未知节点的估计坐标为:~X=(ATA)－1ATb。

2.2 利用拟牛顿法对未知节点坐标迭代求精

在定位计算方面，利用最小二乘法可求出未知节点的估计坐标，但是在某些异常情况下，逆矩阵(ATA)－1估计无法实现，从而导致求解未知节点坐标失败［12］。

拟牛顿法是一种高效的求解优化问题的方法，该算法收敛速度快、定位精度高，因此被广泛应用在求解优化问题的算法中［13］。

本文采用最小二乘法和无约束拟牛顿法相结合的算法求解未知节点的估计坐标，即首先通过最小二乘法获得未知节点的估计坐标，然后把估计值作为拟牛顿算法的初值，进一步对未知节点坐标迭代求精。因此，可以将定位问题转换为求非线性最小二乘优化问题，通常也叫做无约束的极小平方和函数问题，即:

式中，xi，yi分别为信标节点i的横坐标和纵坐di为未知节点到信标节点i的距离。对于本文中求解未知节点的坐标，即求F(x，y)，x∈R+且y∈R+的最优解X*(x*，y*)。

采用最小二乘－拟牛顿法求解未知节点坐标的步骤如下:

步骤1:通过最小二乘法求得未知坐标的估计值X，将估计值X作为拟牛顿算法的初始值X(0)， H0∈Rn×n，0≤ε≤1，K=0;

步骤2:如果‖gk‖≤‖▽F(X(k))‖≤ε，停止计算，否则计算dk∈－Hkgk;

步骤3:沿着dk方向进行线性搜索，并求ak，接着令xk+1=xk+akdk;

步骤4:校正Hk+1=Hk，使拟牛顿条件成立;

步骤5:令K=K+1，重复步骤二。

3 仿真结果与分析

本文利用MATLAB平台对改进后的定位算法进行仿真分析，并同相关方法进行了对比，验证本文提出的算法性能。

3.1 仿真参数设置及相关定义

本文将原始的RSSI测距结合最小二乘的算法记为RSSI，将文献［9］通过粒子群优化算法对加权质心定位算法的改进记为RSSI－WP，将最小二乘法和拟牛顿法相结合的算法改进记为最小二乘－拟牛顿改进(RSSI－LN)，将RSSI－差分改进和最小二乘－拟牛顿改进综合的算法记为本文所述的改进算法(RSSI－DLN)。

仿真的网络环境如下:WSN区域大小为100 m× 100 m，该区域内随机布置100个传感器节点(包括未知节点和信标节点)。假设无线电信号的路径传播模型的路径损耗衰减因子k=4.8，无线信号载波频率为2.4 GHz，信道中的随机噪声分布在5～8之间。为了验证算法的稳定性，对该算法进行100次仿真并取均值，图中涉及的相关定义如下:

(1)设节点i的实际位置为Ti，估计位置为~Ti，记|Ti－~Ti|为一次网络仿真时节点i的定位误差，定义整个网络的平均定位误差为

式中，K为未知节点的个数，N=100为仿真次数。

(3)算法的性能评价，通常使用均方根RMS (Root Mean Square)［14］作为算法性能的评价指标，具体公式为:

式中，e(i)为估计值，r(i)为真实值，N为锚节点数目，M=1。

3.2 仿真结果分析

图2仿真了通信半径为30、信标节点为20时，传统定位算法(RSSI)与本文中改进算法(RSSIDLN)的未知坐标偏差图。从图2中可以看出，RSSI－DLN算法比RSSI测距算法的定位精度高很多，RSSI－DLN的定位精度偏差大体分布在4 m左右。

图2未知坐标偏差图

图3 仿真了通信半径为30时，4种不同方法的归一化平均定位误差。从图3中可以看出，随着信标节点个数的增多，提供给求取RSSI值的有用信息也都越来越多，定位误差首先快速下降，然后缓慢下降。RSSI－DLN算法比传统RSSI测距算法提高了约28%～36%的定位精度，比RSSI－WP算法提高了近16%的定位精度。

图3归一化平均定位误差图

图4 仿真了信标节点为20、通信半径为30时，平均定位误差随通信半径变化比例之间的关系。从图4中可以看出，通信半径小于15时，4种算法的平均定位误差基本接近，这是由于通信半径过小导致很多未知节点无法定位。随着通信半径的增加本文提出的算法优势越来越明显，比RSSI提高了近36%的定位精度。从图4中还可以看出，4种定位算法的平均定位误差都随着通信半径的增大先减小而后缓慢回升，说明通信半径并不是越大越好。因此，在大规模的无线传感器网络定位算法中，选取最优的通信半径十分重要，本文所述的网络环境下最优通信半径为33。

图4 3种算法的平均定位误差曲线

表1给出了通信半径为30时的算法性能比较，从表中可以看出，平均定位误差的比较中，本文改进算法(RSSI－DLN)比传统定位算法(RSSI)更低。RSSI－DLN算法的均方根误差仅为RSSI算法的RSSI－DLN算法在定位精度方面更具有优势。

表1 算法性能比较

4 结论

本文提出了一种基于RSSI差分校正的最小二乘－拟牛顿定位算法。该算法充分利用RSSI测距和定位估计两个方面存在的较大误差，提出把信标节点在定位过程中存在的误差利用到求未知节点到信标节点的距离当中以及用拟牛顿法对最小二乘法估计出来的坐标进行迭代求精。在相同的仿真网络环境下，本文算法在精度和鲁棒性上都比传统算法更优，同时本文提出的定位算法对硬件的要求不高，满足了低成本低功耗的要求，具有很高的应用价值。

［1］嵇玮玮，刘中.DV－Hop定位算法在随机传感器网络中的应用研究［J］.电子与信息学报，2008，30(4):970－974.

［2］He T，Huang C D，Blum B M，et al.Range－Free Localization Schemes in Large Scale Sensor Networks［C］//Proceedings of the Ninth Annual Intemational Conference on Mobile Computing and Networking SanDiego，United states，2003.81－95.

［3］Kyildiz IF A，Su W，Sankarasubramaniam Y，et al.Wireless Sensor Network a Survey［J］.Computer Networks，2002，38(4):393－425.

［4］杨凤，史浩山，朱灵波，等.一种基于测距的无线传感器网络智能定位算法［J］.传感技术学报，2008(1):135－140.

［5］林金朝，陈晓冰，刘海波.基于平均跳距修正的无线传感器网络节点迭代定位算法［J］.通信学报，2009，30(10):107－113.

［6］孙利民，李建中，陈渝，等.无线传感器网络［M］.北京:清华大学出版社，2005.

［7］任维政，徐连明，邓中亮，等.基于RSSI的测距差分修正定位算法［J］.传感技术学报，2008，21(7):1247－1250.

［8］陶为戈，朱昳华，贾子彦.基于RSSI混合滤波和最小二乘参数估计的测距算法［J］.传感技术学报，2012，25(12):1748－1753.

［9］王新芳，张冰，冯友兵.基于粒子群优化的改进加权质心定位算法［J］.计算机工程，2012(1):90－92.

［10］胡咏梅，张欢.一种改进的无线传感器网络质心定位算法［J］.计算机工程与科学，2012(2):45－49.

［11］刘少飞，赵清华，王华奎.基于平均跳距估计和位置修正的DV－Hop定位算法［J］.传感技术学报，2009(8):1155－1158.

［12］Langendoen K，Reijers N.Distributed Localization in Wireless Sensor Networks:A Quantitative Comparison［J］.Computer Networks，2003，43(4):499－518.

［13］史洪宇，燕莎.WSN中一种改进的DV－Hop节点定位算法［J］.电光与控制，2011(4):93－96.

［14］Entenmann R C.A Circuit for Finding the Root Mean Square［J］. Proc IEEE，1964，52(2):193.

程秀芝(1975－)，女，安徽建筑大学讲师，中国矿业大学硕士，目前主要研究方向为传感器网络定位技术与煤矿安全自动化;

张申(1957－)，男，中国矿业大学教授，博士，博士生导师，煤炭学会资深会员，国家863项目初评专家。目前主要研究方向为矿山通信和矿山物联网。

基于RSSI差分校正的最小二乘－拟牛顿定位算法*

程秀芝1，朱达荣1，张申2*，朱广1

(1.安徽建筑大学，机械与电气工程学院，合肥230022;2.中国矿业大学物联网(感知矿山)研究中心，江苏徐州221008)

针对无线传感器网络(WSN)中存在定位精度不足的问题，提出了一种基于RSSI差分校正的最小二乘－拟牛顿定位算法。在RSSI测距方面，首先通过信标节点的自校正定位求得误差校正系数，将该误差校正系数运用到求未知节点到信标节点的距离当中。在定位计算方面，该算法运用最小二乘法估计简单和拟牛顿法收敛速度快的特点，将最小二乘法计算出来的初值，用拟牛顿法对未知节点坐标进行迭代求精。通过仿真实验表明，本文提出的定位算法定位精度高，与传统的最小二乘法相比提高了近36%的精度。

无线传感器网络;接收信号强度指示;最小二乘;拟牛顿法;差分校正

TP301.6;TP212

A

1004－1699(2014)01－0123－05

2013－10－23修改日期:2013－12－03

C:6150P

10.3969/j.issn.1004－1699.2014.01.023

项目来源:国家自然科学基金项目(61073161);省自然科学基金项目(KJ2012B048);省科技攻关基金项目(1301022066)