基于RSSI比值修正的无线传感器网络DV-Hop定位算法*

杨 祥，潘 玮

（1．武汉理工大学 信息工程学院，湖北 武汉 430070;2．桂林理工大学信息科学与工程学院，广西桂林 541004;3．桂林理工大学博文管理学院，广西桂林 541006;4．桂林理工大学机械与控制工程学院，广西桂林 541004）

0 引言

无线传感器网络通过向目标区域随机抛洒大量的微小网络节点，借助于节点内置的形式多样的传感器感知所在周边环境中各种各样的物理信号。它的应用范围极广［1，2］，只要涉及到有监控存在的地方，无线传感器网络技术都可展现它的优势，是继因特网之后，又一次对人类生产生活方式产生重大影响的技术之一。

一般情况下，没有位置信息的监测数据往往是没有任何意义的。例如:军事中，在目标区域内监测到敌军浸入，但是没有位置信息无法判断具体的入侵地点，从而不能采取相应的应对措施，实现精确的定位对无线传感器网络的协议特别是基于地理信息路由的设计、数据融合、目标跟踪等方面都具有非常重要的意义。目前为止，研究人员已提出许多无线传感器网络节点定位算法，无需测距定位算法由于其硬件要求、网络部署成本、能耗等方面的优势，相对来说更适合于无线传感器网络。其中，DV-Hop定位算法简单、覆盖度高和可行性好等特点，使得成为了一种经济适用型定位方法。它的主要缺点是定位精度不是很高，因此，对算法作出改进成为了一个研究热点［3］。

DV-Hop定位算法的第二阶段在计算未知节点平均每跳距离时，所利用的是距离自己最近的信标节点的平均每跳距离来计算。但是信标节点的平均每跳距离是通过到除本节点外所有其他信标节点的路径与最小跳数之比，所以得到的是全网络范围内的平均每跳距离，与该信标节点附近的网络分布密度有一定的差别。同时，仅仅利用跳数来估测距离，定位限制条件不够充分，不能区分具有相同跳数的节点距离，从而造成较大的定位误差。针对此问题，许多学者提出了改进算法，如 Wu Huarui［4］，王新生等人［5］提出把未知节点附近全部信标节点的平均每跳距离信息取平均来作为未知节点的平均每跳距离，但是不能解决相邻节点之间距离分布不均引起的每跳估算误差;周小波等人［6］提出WDV-Hop定位算法，该算法利用第一跳的RSSI作为基准值来修正之后的跳数，算法也无需进行RSSI测距，计算量适中，算法适应性较好，改进的精度适中。罗维等人［7］提出一种SDV-Hop改进算法，该算法选择距离较近的信标节点进行定位，同时利用信标节点来校正未知节点的估计坐标，但是，该改进算法会减小定位覆盖率，同时也是在增加一定的计算开销作为代价。

针对各种改进算法，本文提出一种距离修正算法，在算法中引入RSSI测距技术来辅助定位，但是，它又不需要基于RSSI进行距离计算，只是利用了RSSI作为距离的比征，对每一跳的距离进行修正，从而提高定位精度，几乎不需要增加计算和通信开销。

1 DV-Hop定位算法

DV-Hop算法［8，9］的基本思想是网络中各个节点通过典型的距离矢量交换协议，获得到各信标节点的最小跳数。各个信标节点获得其他信标节点位置和到它们之间的跳段距离后计算网络平均每跳距离，然后未知节点到信标节点的最小跳数乘以平均每跳距离得到位置节点到信标节点的距离估测。最后，当未知节点获得距3个或者3个以上信标节点的距离之后，利用三边测量法进行自身定位。DVHop定位算法主要分为以下3个阶段:

1）距离矢量交换阶段

每个信标节点向网络广播一个数据包{（xi，yi），Hopnum}，（xi，yi）表示信标节点的坐标位置，Hopnum为位置节点到信标节点的跳数，初始化为0。每个接收到该数据包的邻居节点保存该数据包，同时将数据包中跳数加1，同时比较来自相同信标节点的不同跳数信息，丢弃跳数大的数据包，保存跳数小的，保证未知节点到信标节点的跳数最小。接着再向自己的邻居节点广播，直到网络中所有节点都获得与之相邻信标节点的位置信息和相应的跳数值。

2）平均跳距估算和广播阶段

每个信标节点收集到其他信标节点的位置和跳数信息后，进行该信标节点的网络平均跳距Hopsizei估算，信标节点i的平均每跳估算公式如式（1）所示

其中，（xi，yi）为第j个信标节点位置坐标，Hopnumj为第j个信标节点到第i个信标节点的跳数。信标节点将计算得到的Hopsizei在网络中进行广播，每个未知节点仅接收获得的第一个校正值，丢弃所有后来接收到的值。未知节点再根据跳数信息依照式（2）来计算得到信标节点的距离d

3）位置估计阶段

当未知节点获得与3个或3个以上信标节点距离之后，就可执行三边测量或最大似然估计法定位。

2 基于RSSI比值修正距离估计定位算法

本文提出的基于RSSI比值修正的距离估算算法，从RSSI的测距耗散模型出发，根据RSSI理论路径耗散函数［6，10］

其中，PL（d）为经过距离d后的路径损耗，dBm;d0为从发射端附近测量的一个参考距离;n为路径损耗指数。从式（3）可以得出路径耗散值与距离呈反比的关系。考虑到节点的接收信号强度可以从无线节点芯片的寄存器直接读取，所以，可以充分利用这一点来修正DV-Hop计算所得的节点之间每一跳的距离，该方法无需经过复杂的RSSI距离转换，直接利用的是每一节点读取的RSSI值来构造修正系数εi

其中，RSSIi为节点i的接收信号强度值，RSSIavg为该节点在平均跳距广播阶段最先接收到的信标节点的平均信号强度值，具体如式（5）

其中，j为该信标节点可以到达周围的信标节点个数，nj为该信标节点到达周围第j个信标节点的最小跳数。

算法具体详细过程如下:

1）每个信标节点产生一个数据包{ID，（x，y），Hopnum，RSSIi，RSSI（i）}，ID为信标节点的编号，每个传感器节点都有唯一ID号;（x，y）为该ID号的信标节点位置坐标;Hopnum为跳数，初值为0;RSSIi为第i跳节点接收该数据包的信号强度，初值为0;RSSI（i）为第i跳为止全部节点的接收信号强度的累积，信标节点以固定功率向周围广播数据包。

2）直接邻居节点接收到数据包后将跳数Hopnum加1，将RSSIi置为其接收数据包时的接收信号强度，RSSI（i）置为第i跳为止节点的接收信号强度之和，其中，i=Hopnum。最后，得到该节点的数据包信息为{ID，（x，y），1，RSSIi，RSSI（1）}，其中，RSSI（1）=RSSI1+RSSI0=RSSI1。

3）接收到信标节点发送数据包的邻居节点以固定功率继续向其邻居节点发送数据包，接收到数据包的邻居节点将所得的数据包信息变为{ID，（x，y），2，RSSI2，RSSI（2）}，其中，RSSI（2）=RSSI2+RSSI1+RSSI0，当同一个节点先后接收到来自同一个ID号的数据包，则判断该数据包中的跳数与自己已存的同一个ID号的数据包中的跳数值，如果大于或等于已存跳数，则丢弃新接收的数据包;否则，替换。

4）重复步骤（3），直到经过n跳到达另一信标节点，该数据包最后得到的信息为{ID，（x，y），n，RSSIn，RSSI（n）}，其中，RSSI（n）=RSSIn+RSSIn－1+… +RSSI0。最后按照DV-Hop原算法计算信标节点的平均每跳距离Hopsize，同时根据式（5）计算平均接收信号强度值RSSIavg。然后，同DVHop方式一样广播Hopsize和RSSIavg。

5）计算距离d:首先建立每跳修正系数，用每一跳的RSSIi与RSSIavg相除，作为该跳跳距的修正系数εi，如式（5）所示。根据每跳修正系数，计算距信标节点为m跳的未知节点与信标节点距离

由以上各步骤，各未知节点可根据自身存储信息表中的累计信号强度RSSI（m）、平均信号强度RSSIavg和平均跳距Hopsize方便地计算出到各个信标节点的距离。

6）当未知节点获得与3个或3个以上信标节点距离之后，就可执行三边测量或最大似然估计法定位。

3 仿真实验

由于基于RSSI比值修正距离估算算法涉及到每个节点的接收信号强度RSSI，而RSSI是通过读取传感器节点中特定的寄存器得到的，而通过仿真软件无法得到RSSI。考虑到引入RSSI比值理论上主要是利用RSSI来比征距离，所以，使用任意两节点间的欧氏距离ED来代替节点的RSSI。仿真参数设置为在网络范围100 m×100 m区域内随机产生100个网络节点。下面分别讨论原DV-Hop定位算法，文献［6］提出的WDV-Hop定位算法和本文改进算法3种定位算法的网络节点平均相对当定位误差随信标节点比例和通信半径的影响，其中，相对定位误差σ定义为

其中，（xr，yr）为节点真实坐标位置，（xe，ye）为估计坐标位置，R为节点通信半径。每种算法性能的仿真都是随机进行100次而得到的结果，如图1，图2所示。由于文献［6］的WDV-Hop定位算法在通信半径小于40 m的时候，定位改进效果较差，甚至与原DV-Hop差不多，所以，取R大于40 m进行仿真，仿真结果表明:本文改进的算法定位误差始终小于原DV-Hop和WDV-Hop定位算法，且随着信标节点比例的影响不是很大，定位误差相对较稳定，对比图1和图2可以发现，本文改进算法随着通信半径的增加，定位误差也随之下降。

图1 通信半径R=40m相对定位误差比对图Fig 1 Relative localization error comparison chart with R=40 m

图2 通信半径R=50 m相对定位误差比对图Fig 2 Relative position error comparison chart with R=50 m

4 结论

本文的基于RSSI比值修正的DV-Hop定位算法，与文献［6］所提的改进算法类似，都是直接利用RSSI进行修正，增加的是有限的加法和除法，也无需信标节点进行重新广播，增加的计算和通信开销几乎可以忽略不计，同时修正系数都是一个比值，所以，对环境适应性较大［6］，但比起WDV-Hop定位算法，本文的定位误差明显占优势。相比文献［4，5，7］及其他的一些基于DV-Hop改进算法，本文的改进算法在计算开销、算法适应性、定位覆盖率等方面都有相对的优势，同时，该改进算法也存在一些不足，如受节点接收的RSSI影响较大，需要在取得的RSSI值真实的反映节点间欧氏距离情况下才能保证算法的精度。

［1］ Alemdar H，Ersoy C．Wireless sensor networks for healthcare:A survey［J］．Computer Networks，2010，54:2688 －2700．

［2］ Othmana M F，Shazali K．Wireless sensor network applications:A study in environment monitoring system［J］．Procedia Engineering，2012，41:1204 －1210．

［3］ 刘晓春．无线传感器网络DV-Hop定位算法的改进与仿真［D］．重庆:重庆交通大学，2011:13－15．

［4］ Wu Huarui，Gao Ronghua．An improved method of DV-Hop localization algorithm［J］．Journal of Computational Information Systems，2011，7（7）:2293 －2298．

［5］ 王新生，赵衍静，李海涛．基于DV-Hop定位算法的改进研究［J］．计算机科学，2009，38（2）:76 －90．

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

［7］ 罗 维，姜秀柱，盛蒙蒙．无线传感器网络选择性DV-Hop定位算法［J］．传感器与微系统，2012，31（3）:71 －77．

［8］ Niculescu D，Nath B．DV-based positioning in Ad Hoc networks［J］．Telecommunication Systems，2003，22（1）:268 －275．

［9］ 于宏毅，李 鸥，张效义，等．无线传感器网络理论、技术与实现［M］．北京:国防工业出版社，2010:260－266．

［10］ Shen Xingfa，Wang Zhi，Jiang Peng．Connectivity and RSSI-based localization scheme for wireless sensor networks［C］∥International Conference on Intelligent Computing，2005:578 －587．