基于节点RSSI值与临界RSSI比例的跳数修正和跳距重估的DV-HOP算法

方旺盛，雷高祥

（江西理工大学信息工程学院，江西赣州341000）

基于节点RSSI值与临界RSSI比例的跳数修正和跳距重估的DV-HOP算法

方旺盛*，雷高祥

（江西理工大学信息工程学院，江西赣州341000）

为了减少传统DV-Hop定位算法对未知节点定位时产生的较大误差，提出了一种基于节点RSSI值与临界RSSI比例跳数修正和跳距重估的DV-HOP算法。首先，采取节点RSSI值与临界RSSI比例来修正跳数，得到修正后的跳数；然后利用修正后的跳数求解跳距均衡系数对平均跳距进行穷尽三角组合加权修正，得到修正后的跳距；最后，将修正后跳距与通信半径进行比较，偏差最大和最小的跳距不参与计算，再求剩余跳距值的均值得到平均每跳距离。仿真结果表明：在相同的网络环境下，与经典的DV-Hop算法相比，文中算法仅需要节点通信芯片具有RSSI指示功能，并不需要其它额外的硬件，有效降低了定位误差；与其他DV-Hop修正算法相比，该算法同样也具有降低定位误差的优势。

无线传感器网络；DV-Hop定位算法；临界RSSI；跳数；均衡系数；跳距重估

现今，多种无线传感器网络定位算法被广泛应用。无线传感器网络按定位算法分为基于测距的定位算法和基于非测距的定位算法，几种常见的测量技术包括到达时间、到达时间差、到达角、接收信号强度指示等。基于非测距的定位算法包括DV-Hop算法，质心算法，Amorphous算法，APIT，MDS-MAP等等。在现有技术中，通常使用的是DV-Hop算法。针对DV-Hop算法的不足，有必要对DV-Hop算法提出改进算法。刘锋，张翰，杨骥等提出一种加权处理的无线传感器网络平均跳距离估计算法［1］来提高定位精度，Wanli Zhang，Xiaoying Yang等提出了一种用RSSI值加权跳数［2］，用全网的平均跳距代替每一个信标节点的平均跳距来提高定位精度，Deng yi，Zhang，and Liu Feng等通过对经典DV-Hop算法的改进［3］，采用加权平均来计算平均跳距来提高定位精度，嵇玮玮等人［4］提出了利用了最小均方法求平均每跳距离和采用不同参考节点平均跳距来计算未知节点到锚节点之间距离的方案。上述算法中，大部分是对传统DV-Hop算法的跳数和跳距计算方法的改进，但定位误差的减少不太明显。目前对这类算法最主要的改进是对节点在全局位置进行估计时的估计算法来进行改进。本文在DV-Hop算法的跳数计算和平均跳距地选取过程中引入了临界RSSI比，均衡系数和跳距重估，使得跳数和平均跳数更加接近真实值。

1 DV-Hop算法及最大似然估计法

1.1 DV-Hop定位算法

经典DV-Hop算法［5-6］的定位过程可分为3个阶段：

①采用典型的距离矢量路由交换协议，通过节点之间的信息交换，使网络中所有的节点获得与信标节点间的最小跳数。

②计算与信标节点的估计距离

信标节点根据在第一阶段中记录的其他导标节点的位置信息和相应的跳数，按照式（1）估计每跳的平均距离，并将其作为一个跳距校正值广播至网络中：

式中(xi,yi),(xj,yj)是信标节点i，j的坐标，hi是信标节点i，j的最小跳数。

未知节点接收离自己最近的一个信标节点的值作为自身的平均每跳距离值即：

式中AVG是未知节点平均每跳距离值，avgi是离未知节点最近的信标节点估计的平均每跳距离值。然后，算出到各信标节点的距离，公式如下：

③最后根据最大似然估计方法计算其坐标［6-7］。

然而，在实际的网络拓扑结构中，信标节点和未知节点之间的路径往往是折线［8］如图1所示，使用DV-Hop算法会带来很大的距离误差，进而引起定位误差。

图1 节点之间的折线图

1.2 最大似然估计法

(x1,y1),(x2,y2)…(xn,yn)为信标节点坐标，它们到未知节点（x，y）的距离分别为d1,d2,…dn，则未知节点坐标的计算公式为：

将上式看作线性方程组BX=b，解得：

得未知节点坐标为：

2 RSSI测距模型

本文提出基于临界RSSI比例加权系数处理跳数［8］，利用RSSI的测距屏蔽耗散模型［9-10］，屏蔽模型的路径损耗模型原理使用了一个接近中心的距离d0为参考，对距离为d的平均接收功率PL（d）进行预测，两者比值关系如下式：

考虑信号功率的损耗，经研究测量，无线信号路径损耗功率是对数正态随机变量［11］，为使测量值更接近真实值，在此引入一均值为零的高斯分布e。

3 本文算法步骤及分析

考虑到无线信号功率多为mW级别，极化后接收信号强度转化为负数的dBm，并且通信半径为R的节点1跳理想距离为R，本文算法将R处相应的RSSI值做为临界值RSSthreshold。其计算方法利用式（10）得到：

本文算法的具体步骤：

①每个信标节点广播一个数据包，基本信息有信标节点的标号ID；相应ID号信标节点的坐标（x，y）；初始值为0的跳数Hcot；第i跳接收数据包时接收信号强度值RSSIi，距离为R时的RSSI临界值RSSthrehold，然后信标节点以一定功率将数据包向周围节点广播出去。其它节点收到邻居节点发送的数据包后用接收到的数据包中RSSI值利用式（10）、式（11）求出临界比例系数hi，再根据数据包中的按照式（12）更新跳数，同时将更新后的信息转发给其邻居节点

②对已求出的每个信标节点的平均跳距，利用三角重组加权处理［12-13］每个信标节点的平均跳距。信标节点i估计的平均跳距记为Li，未知节点距离锚节点的跳数记为mi。假设未知节点共收到m个信标节点的信息，并记为q1,q2,q3,q4,…,qm，从这m个信标节点中取出3个作为一组，判断以它们为顶点的相应信标节点的跳距的大小，并给跳距较大的给以较小的系数修正，跳距较小的给以较大的系数修正［14］。假如选择了q1,q2,q3三个信标节点，相应的跳距为 L1,L2,L3，未知节点距离他们相应的跳数为m1,m2,m3。均衡系数计算如式（13）

利用均衡系数处理后的平均跳距Avg1为：

按同样的方法选择三个信标节点，直至穷尽所有信标节点的三角组合，总共有种，并且可以得到相应的平均跳距为将得到的平均跳距与通信半经R作差比较，偏差最大和最小的跳距不参与计算，即选除以下两种情况MAX[Avg1,Avg2,…Avg3],MIN[Avg1,Avg2,…Avg3], 最终得到平均跳距为：

利用式（15）计算出来的平均跳距和式（12）更新后的跳数信息按照下式计算未知节点到信标节点的距离D：

③未知节点坐标的求解，采用经典DV-Hop最大似然估计法定位。

临界RSSI比例原理如图2所示。

图2 临界比例原理图

计算临界比例方法如下公式：

当hi=1时，说明节点在通信半径边缘处，即在类似图2中的A点处，此时的跳数为1。

当hi＜1时，说明节点在距离小于通信半径R处，即在类似图2中的B点处，跳数小于1。

图1中根据传统DV-Hop算法计算跳数为3跳，若依据本文算法计算跳数为：

得到的跳数值始终比经典DV-Hop算法要小，减小了跳数计算误差，这样就使得计算的跳距更加接近实际跳距值。

4 算法仿真

本文利用MATLAB仿真软件对实验进行仿真分析。仿真环境在100 m×100 m区域内随机产生未知节点，节点总数为100个，在不同的通信半径与信标节点比例的条件下进行了定位性能分析，分别进行了50次仿真实验，并取平均值作为实验结果。相对定位误差和定位精度∂

式中，（xi，yi）为节点真实坐标，（xj，yj）为估计坐标位置，R为节点通信半径。

下面通过部分数据，定量分析本文算法的定位误差，表1列出了在通信半径为R=60 m，锚节点数为不同比例时，三种定位算法的定位误差变化关系。表2列出了在锚节点比例为5%，通信半径不同时，三种算法的定位误差变化关系。

表1 定位误差（100%）随锚节点变化关系（R=60 m）

表2 定位误差（100%）随通信半径的变化关系

图3表示网络节点总数固定，信标节点比例分别取5%，7%，9%，11%，13%，15%，20%，通信半径R=60 m和R=70 m情况下，经典DV-Hop，文献［1］改进算法和本文算法的定位仿真比较。由图3可知：本文提出的改进算法定位误差始终小于原DV-Hop和文献［1］算法，并且随着信标节点比例的增加，定位误差呈现下降的趋势，当锚节点达到了一定数量时趋于平缓。并不是锚节点数越多，误差就越小。当R=60 m时，与原DV-Hop相比，本文算法的定位误差减少了20.7%左右，与文献［1］相比，定位误差减少了8%左右。

图3 通信半径R=60 m和R=70 m相对定位误差

当R=70 m时，本文算法的定位误差比原DVHop算法和文献［1］改进算法分别减少了19%和13%左右。

图4表示当锚节点比例相同，节点通信半径不同时的定位误差比较。由图可知：当锚节点比例相同时，三种算法随着通信半径的增加，定位误差也随之下降，当半径为60 m左右与原算法和文献［1］偏差较大，误差减少效果明显，通信半径达到一定范围时误差波动不大，说明并不是通信半径越大越好。

图4 不同通信半径的定位误差比较图

5 结论

本文对DV-Hop定位算法的跳数和平均跳距分别采取节点RSSI值与临界RSSI的比例修正和跳距重估修正，经过节点RSSI值与临界RSSI比例修正后的跳数计算误差有一定减少，并且本文算法对跳距的重估，使得跳距更接近于真实值。最后用MATLAB进行仿真实验。仿真结果表明在通信开销不变情况下本文所提出的改进算法与原算法相比定位误差有相对的减少，并且与文献［1］算法相比定位误差也有所减少。

［1］刘锋，张翰，杨骥，等.一种基于加权处理的无线传感器网络平均跳距离估计算法［J］.电子与信息学报，2008，30（5）：1222-1225.

［2］Zhang W，Yang X，Song Q.DV-Hop Localization Algorithm Based on RSSI Correction［J］.Journal of Software Engineering，2015，9（1）：188-194.

［3］Deng yi，Zhang，Liu Feng.Improvement of DV-Hop Localization Algorithms in Wireless Sensor Networks［J］.Instrumentation& Measurement，Sensor Network and Automation（IMSNA），2012（2）：567-569.

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

［5］Niculeseu D，Nath B.DV-Based Positioning in Ad Hoc Networks［J］.Journal of Telecommunication Systems，2003，22（1/4）：267-280.

［6］石为人，贾传江，梁焕焕.一种改进的无线传感器网络DV-Hop定位算法［J］.传感技术学报，2011，24（1）：83-87.

［7］Xie Chuan.Research on Improved DV-HOP Localization Algorithm Based on Weighted Least Square Method［J］.Knowledge Acquisition and Modeling Workshop，2008，IEEE International Symposium，2008，12（21-22）：773-776

［8］夏少波，朱晓丽，邹建梅，等.基于跳数修正的DV-Hop改进算法［J］.传感技术学报，2015，28（5）：757-762.

［9］Cao J，Chen M.The Research of DV-HOP Positioning Algorithm Based on RSSI Calibration［J］.TELKOMNIKA Indonesian Journal of Electrical Engineering，2014，12（10）：7452-7458.

［10］Zhang Zheng，Zhixun Rao.A Weighted Compensation of Coordinate Error Localization Algorithm Based on RSSI［J］.Journal of Chemical and Pharmaceutical Research，2014，6（6）：448-454

［11］Zhang D Y，Cui G D.A Union Node LocalizationAlgorithm Based on RSSI and DV-Hop for WSNs［C］//Instrumentation，Measurement，Computer，Communication and Control（IMCCC），2012 Second International Conference on 2012 IEEE，2012，12：1094-1098.

［12］Lin Z G，Zhao L，Li L，et al.An Improved DV-HOP on Weighted and Distributed Calculation Method［J］.Advanced Materials Research，2013，787：1044-1049.

［13］Jang-Ping Sheu，Pei-Chun Chen，Chih-Shun Hsu.A Distributed Localization Scheme for Wireless Sensor Networks with Improved Grid-Scan and Vector-Based Refinement［J］.IEEE Transactions on Mobile Computing，2008，7（9）：1110-1123

［14］Cheng H Q，Wang H，Wang H K.An Improved Centroid Localization Algorithm Based on Weighted Average in WSN［C］//Proceedings of the 3rd International Conference on Electronics Computer Technology（ICECT’11），2011，4：258-262.

方旺盛（1963-），男，教授，硕士研究生导师，主要研究方向为无线传感器网络，数字水印，基因表达式编程等，fangwangsheng@163.com；

雷高祥（1992-），男，硕士研究生，研究方向为无线传感器网络，1210122486@qq.com。

A DV-HOP Algorithm Based on the Ratio between Node RSSI and the Critical RSSI Hop Correction and Hop Distance Revaluation

FANG Wangsheng*，LEI Gaoxiang
（Faculty of Information Engineering，Jiangxi University of Science and technology，Ganzhou Jiangxi 341000，China）

Traditional DV-Hop algorithm can cause greater positioning errors，To overcome such problem，this paper presents a improved algorithm which based on the ratio between node RSSI and the critical RSSI hop count correction and hop distance revaluation.Firstly，we take the ratio of node RSSI and the critical RSSI to modify hops，and the correction hops will be attained；then the average hop distance will be corrected through weighted combination of triangle.Finally，compared the hop distance with communication radius，the maximum and minimum hop distance will not be applied to calculate，According to the above，we will get the average distance per hop by calculating the average value among the remaining jump distance.The simulation results show that under the same network environment，compared with the classic DV-Hop algorithm，this proposed algorithm requires only node communication chips with RSSI indicator and does not require additional hardware overhead，can effectively reduce the location error；compared with other DV-Hop correction algorithm，this algorithm also has the advantage of reducing the location error.

wireless sensor networks；DV-Hop localization algorithm；critical RSSI；equilibrium coefficient；hop distance revaluation

TP393

A

1004-1699（2015）08-1244-05

��6150P

10.3969/j.issn.1004-1699.2015.08.024

2015-04-21 修改日期：2015-05-27