基于RSSI值跳数修正和跳距加权处理的DV-HOP算法

雷高祥， 黄辉，　方旺盛

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

基于RSSI值跳数修正和跳距加权处理的DV-HOP算法

雷高祥， 黄辉，方旺盛

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

针对传统DV-Hop定位算法在计算节点间的跳数和平均跳距存在的误差，提出了一种基于RSSI值跳数修正和跳距加权修正的DV-HOP算法.首先，采取节点RSSI比值修正跳数；然后选择距离未知节点最近的3个锚节点，并利用修正后的跳数求加权系数对平均跳距进行加权修正.仿真结果表明：在相同的网络环境下，该算法没有增加其他硬件开销，并且定位误差相对于传统DV-Hop算法有一定减少.

无线传感器网络；DV-Hop定位算法；RSSI值；跳数；加权系数

0　引言

随着相关技术的发展，无线传感器网络定位技术已被广泛运用，目前已有的无线传感器网络定位算法可分为源定位算法、节点自定位算法和地图匹配算法.其中源定位算法包括基于测距和基于非测距的定位算法.常见的基于测距定位算法包括到达时间、到达时间差、到达角、接收信号强度指示等，基于非测距的定位算法包括DV-Hop算法、质心算法、Amorphous算法、APIT、MDS-MAP等.经典DV-Hop算法通过跳段距离而不是直线距离来估计未知节点与锚节点之间的距离，然而在实际情况下，未知节点与锚节点相互之间的连接是折线，直接利用跳段距离必然会造成大量的误差积累.杨祥等［1］提出了一种基于RSSI比值修正的无线传感器网络DV-Hop定位算法，通过将RSSI作为节点间欧氏距离的比值来修正每一跳的距离.张爱清等［2］提出了一种基于RSSI每跳分级和跳距修正的DV-Hop算法，该算法将每一条细化分级，利用最小均方误差准则处理平均跳距，有效降低了定位误差，提高了定位精度，Deng等通过对经典DVHop算法的改进［3］，采用加权平均来计算平均跳距来提高定位精度.本文在DV-Hop算法的跳数过程中引入了RSSI比值，并且利用加权系数对跳距加权，使得跳数和平均跳数更加接近真实值.

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

1.1DV-Hop定位算法

由Niculescu和Nath提出的DV-Hop算法［4］可分为3个步骤：

1）待定位节点与信标节点的最小跳数的获取.每一个信标节点广播包含自身位置信息和跳数字段的分组，跳数初始值为0.其他节点记录其接收到的每个信标节点的最小跳数，忽略来自同一信标节点较大跳数的分组，并将跳数字段加1转发给邻居节点.这样网络中所有节点都能获得与信标节点之间的最小跳数.

2）估算待定位节点和信标节点间的距离.根据在第一阶段中得到的其他信标节点的位置信息和最小跳数，按照下式（1）估计每跳的平均距离：

式（1）中（xi-xj），（yi-yj）表示相应信标节点i，j的坐标值，hi表示信标节点i，j的跳数值.

待定位节点得到最近信标的跳距值：

式（2）中AVG是待定位节点的平均跳距，avgi是距离待定位节点最近的信标节点平均跳距.待定位节点接收到每跳距离并根据其到信标节点的最小跳数来估算其到各信标节点的距离如公式（3）：

3）利用基于测距的定位算法［5-6］计算待定位节点位置.如根据最大似然估计方法计算其坐标［7］.

在实际情况下，网络的拓扑结构如图1所示，未知节点B到信标节点A的跳数并不是理想的跳数，A到B的实际路径为A→C→B，这样如果利用跳段距离就会引起大量的误差积累，定位误差也会随之增大.

图1　网络拓扑结构

1.2最大似然估计法

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

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

得未知节点坐标为:

2　RSSI测距模型

常见的无线信号传播路径损耗模型［8］有：对数距离路径损耗模型、Hata模型、对数-常态分布模型、自由空间传播模型，本文采用最常用的是对数-常态分布模型［9］.提出基于临界RSSI比例加权系数处理跳数，选取距离为d0参考距离，当距离为d时，可以预测此时节点的平均接收功率PL（d），两者关系如下式：

两边取对数得：

为使测量值更接近真实值，引入一均值为零的高斯分布ε［10］.

其中，［PL（d）］dB距离 d处的接收信号强度，计量单位为dBm；n表示路径损耗因子，一般取2～4，文中取n=4.PL（d0）为发射端参考距离1 m的处RSSI，即为发射功率.RSSI值随距离变化关系如图2所示.

图2　RSSI值随距离变化关系

3　算法分析及步骤

3.1算法分析

3.1.1RSSI比值

考虑到无线信号功率多为mw级别，极化后接受信号强度［11］转化为负数的dbm.本文算法将R处相应的RSSI值做为比例因子RSSIR.利用式（12）得到：

RSSI比值原理如图3所示：

图3　临界比例原理图

计算RSSI比值如式（13）：

当hi=1时，说明节点半径R处，即在类似图3中的A点处，即跳数为1.

当hi＜1时，说明节点在通信范围内部，即在类似图3中的B点处，即跳数小于1.

图1中根据传统DV-Hop算法计算跳数为2跳，通过本文算法加权后的跳数为：

得到的跳数值更加接近节点实际情况下的跳数.

3.1.2跳距加权

对跳距的加权处理主要包括以下步骤：首先，选取距离待定位节点最近的3个信标节点，然后，计算加权系数，最后用加权系数处理每个信标节点相应的平均跳距.

假设未知节点共收到m个信标节点的信息，从这m个信标节点中取出距离未知节点最近的3个信标节点，判断这3个相应信标节点的跳距的大小，并将系数较小的赋给跳距较大进行修正，将系数较大的赋给跳距较小的进行修正.假如3个最近的信标节点ID为q1，q2，q3，相应的跳距为L1，L2，L3跳数为m1，m2，m3.加权系数［12-13］计算如式（14）：

对平均跳距赋以加权系数，得到最终跳距值A vgi为:

其中，Li（i=1，2，3）为离待定位节点最近的信标节点的平均跳距，mi（i=1，2，3）待定位节点到相应最近信标节点的跳数.

3.2算法步骤

1）所有的信标节点发送一个包含自身信息的数据包，包括节点ID，坐标信息，跳数；第i跳接收数据包时接收信号强度值RSSIi，距离为R时的接收信号强度值RSSIR.利用公式（16）更新跳数，其中hati表示最新跳数：

然后通过典型的距离矢量交换协议，使网络中所有节点得到距离每个信标节点的最小跳数值，同时将更新后的信息转发给其邻居节点［12］.

2）信标节点根据第一步得到的位置信息和最小跳数后，利用传统DV-Hop求解平均跳距的方法求解平均每跳距离.

3）根据最大似然估计方法计算其坐标.

4　算法仿真

本文利用MATLAB仿真软件对实验进行仿真分析.仿真环境设置为：在100 m×100 m正方形区域内随机部署100个未知节点和信标节点，信标节点在随机部署的节点中选取相应的参考坐标进行仿真实验，每个节点具有相同的通信半径为R.并且在不同的通信半径与信标节点比例的情况下对文中算法性能进行仿真分析，分别进行了50次仿真实验，并取平均值最为实验结果.节点间的测距暂不考虑测量误差对定位的影响 （假设噪声值为零，测量值即为真实距离）.在室外空旷环境下，电磁传播各向一致，采用的shadowing模型，损耗指数n=4，参考距离d0=1m选取RSSI值.相对定位误差£和定位精度∂:

其中，（xi，yi）为节点的实际坐标，（xj，yj）为算法中估计坐标位置，R为节点通信半径.

下面通过部分数据，定量分析文中算法的定位误差，表1列出了在通信半径为R=60m，锚节点数取5%，10%，15%，20%，25%时，两种定位算法的定位误差变化数据.表2列出了在锚节点比例为5%，通信半径R取50 m，55 m，60m，65 m时，二种算法的定位误差变化数据.

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

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

如图4所示为网络的总节点数和通信半径不变，信标节点比例分别取5%，10%，15%，20%，25%时，两种算法在通信半径R=60 m和R=70m两种情况下的误差比较.由图4所示可知：随着信标节点数目的增加，两种算法的定位误差也随之下降，当节点数达到一定比例时，定位误差率区域平缓，并且改进算法定位误差相对于原DV-Hop算法有一定优势.说明并不是锚节点数越多，误差就越小.当R=60 m时，与原DV-Hop相比，文中算法的定位误差减少了17%左右.当R=70 m时，相对于传统算法，文中算法的定位误差减少了15%左右.

如图5所示为信标节点比例相同，节点通信半径不同时，两种算法的定位误差比较结果.由图5所示可知：当信标节点比例相同时，随着通信半径的增加，两种算法的定位误差也随之下降，当通信半径在60m左右时，两种算法的定位误差偏差较大，半径达到一定大小时，定位误差趋于平缓，通信半径越大，定位误差不一定越小.

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

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

5　结论

文中对DV-Hop定位算法的跳数采取RSSI比值修正，以减少计算跳数带来的误差，经过节点RSSI值与临界RSSI比例修正后的跳数计算误差有一定减少.并且使用加权系数处理跳距，使得跳距更加接近真实值.最后用MATLAB进行仿真实验.仿真结果表明在通信开销不变情况下文中所提出的改进算法与原算法相比定位误差有相对的减少.

［1］杨祥，潘玮.基于RSSI比值修正的无线传感器网络DV-Hop定位算法［J］.传感器与微系统，2013（7）:126-128，135.

［2］张爱清，叶新荣，胡海峰等.基于RSSI每跳分级和跳距修正的 DV-HOP改进算法 ［J］.仪器仪表学报，2012，11:2552-2559.

［3］Zhang D Y，Liu F.Improvement of DV-Hop localization algorithms in wireless Sensor networks［J］.Instrumentation& Measurement，Sensor Network and Automation（IMSNA），2012，2: 567-569.

［4］Niculeseu D，Nath B.DV-based positioning in Ad Hoc networks［J］. Journal of Telecommunication Systems，2003，22（1）：267-280．

［5］周小波，乔钢柱，曾建潮．无线传感器网络中基于RSSI的加权DV-Hop定位方法［J］．计算机工程与设计，2011，47（14）：109-111．

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

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

［8］Guo Z，Min L，Li H，et al.Improved DV-Hop localization algorithm based on RSSIvalue and hop correction［M］.Advances in Wireless Sensor Networks.Springer Berlin Heidelberg，2013:97-102.

［9］Zhang D Y，Cui G D.A union node localization algorithm based onRSSIandDV-HopforWSNs［C］//Instrumentation，Measurement，Computer，Communication and Control（IMCCC），2012 Second International Conference on 2012 IEEE，2012，12: 1094-1098.

［10］Cao J，Chen M.The Research of DV-HOP Positioning Algorithm Based on RSSICalibration［C］//Applied Mechanics and Materials，2014，610:882-887.

［11］Fang Z，Zhao Z，Geng D，et al.RSSI variability characterization and calibrationmethod in wireless sensor network［C］//Information and Automation（ICIA），2010 IEEE International Conference on. IEEE，2010:1532-1537.

［12］Lin ZG，Zhao L，Li L，et al.An improved DV-HOP on weighted anddistributedcalculationmethod［C］//AdvancedMaterials Research，2013，787:1044-1049.

［13］Zhang Z，Rao Z X.A weighted compensation of coordinate error localization algorithm based on RSSI［J］.Journal of Chemical and Pharmaceutical Research，2014，6（6）:448-454.

A DV-HOP algorithm based on RSSI hop count correction and hop distance weighted processing

LEI Gaoxiang，HUANG Hui，FANG Wangsheng
（School of Information Engineering，JiangxiUniversity of Science and Technology，Ganzhou 341000，China）

To reduce the errors in calculating the hop count and average hop distance between nodes by the traditional DV-Hop localization algorithm，this paper presents a DV-HOP algorithm based on the ratio between node RSSI and the critical RSSI hop count correction and hop distance weighted revaluation.Firstly，the correction hops are attained by taking the ratio between node RSSI and the critical RSSI corrected hops；then three nearestanchor nodes to the unknown node are chosen，and the average hop distance is corrected by using the weighting coefficient，which is attained through the corrected hop count.The simulation results show that in the same network environment，compared with the traditional DV-Hop algorithm，the proposed algorithm requires only node communication chips with RSSI indicator，without additional hardware expenses，thus effectively reducing the location error.

wireless sensor networks；DV-Hop localization algorithm；RSSI ratio；hop count；weighting coefficient

TP398

A

2095-3046（2015）05-0080-05

10.13265/j.cnki.jxlgdxxb.2015.05.014

2015-05-11

雷高祥（1992-），男，硕士研究生，主要从事无线传感器网络等方面的研究，E-mail:leigaoxiang1992@163.com.

方旺盛（1963-），男，教授，主要从事无线传感器网络，数字水印等方面的研究，E-mail:fangwangsheng@163.com.