节点RSSI比值跳数修正的DV-Hop算法

方旺盛， 雷高祥， 黄 辉

(江西理工大学 信息工程学院，江西 赣州 341000)

节点RSSI比值跳数修正的DV-Hop算法

方旺盛， 雷高祥， 黄 辉

(江西理工大学 信息工程学院，江西 赣州 341000)

针对传统的DV-Hop定位算法在计算锚节点与待定位节点之间的平均跳距和跳数时所造成的大量误差积累问题，提出一种基于接收信号强度指示(RSSI)比例修正的DV-Hop定位算法。在改进的算法中，根据不同平均跳距处的接收信号强度指示(RSSI)值，选取最大平均跳距、最小平均跳距处、通信半径处的RSSI值，求出比例因子，再利用该比列因子求出加权系数来修正每一跳数，从而得到更加精确的跳数和平均跳距，提高定位精度。仿真实验表明：该改进算法的定位精度优于传统算法。

无线传感网络； DV-Hop定位算法； 跳数； 接收信号强度指示(RSSI)比例因子； 加权系数

0 引 言

无线传感器网络(WSNs)按节点自定位算法[1]可分为Range-free的定位算法[2]和Range-based的定位算法两类[3]。基于Range-free的方法有Centroid，DV-Hop，Amorphous，APIT等。其中，DV-Hop算法因定位精度相对较低的缺点，许多研究者提出了改进方法。刘凯、余君君等人[4]提出了对锚节点进行优选和求解跳数加权系数，罗维等人[5]通过比较未知节点与锚节点之间的距离，对锚节点进行选取，并且对未知节点的坐标校正。

本文针对无线传感器网络DV-Hop算法，在计算未知节点到锚节点平均跳距和跳数时存在不足，提出一种基于接收信号强度指示(RSSI)比值跳数修正的改进算法，利用RSSI比值加权跳数值，使得跳数更加接近真实值。

1 经典DV-Hop定位算法

经典DV-Hop算法可分为以下几个步骤：

1)获取待定位节点与锚节点的最小跳数。

2)估算待定位节点和锚节点的距离。锚节点获得其他锚节点的位置信息和最小跳数，利用式(1)估算平均每跳的距离

(1)

式中 (xi,yi),(xj,yj)为相应锚节点i,j的坐标值，hi为锚节点i,j的跳数值。

3)计算待定位节点到锚节点的距离。每个节点保证从最近的锚节点获得平均跳距。网络中未知节点k利用下式计算与信标节点i的距离为

dki=avgsizek×hki

(2)

4)采取Range-based的定位算法[6]计算待定位节点位置,如最大似然估计方法[7]。

2 最大似然估计法

(x1,y1),(x2,y2),…,(xn,yn)为锚节点坐标位置，(xi,yi)为待定位节点i的坐标位置，锚节点与待定位节点i的距离分别为d1,d2,…，dn，则待定位节点坐标为

(3)

转换为线性方程组 ，解得

(4)

(5)

(6)

得未知节点坐标为

(7)

3 RSSI测距

根据对数—常态分布模型[8,9]可以计算出距离节点d处的平均接收功率PL(d)，则有下式

(8)

左右两边取对数

(9)

引入一均值为零的高斯分布ε[10]。

(10)

式中 距离d处的RSSI值为[PL(d)]dB，计量单位为dBm； n为路径损耗系数，一般取2～4，PL(d0)为参考距离1m的处RSSI。图1为RSSI值随距离变化关系。

图1 RSSI值随距离变化关系Fig 1 Relationship between RSSI and distance

4 改进DV-Hop算法步骤与算法分析

4.1 改进算法步骤

1)锚节点广播一个数据包，数据包中的信息有锚节点的坐标位置和初始值为0的跳数。网络中的节点记录和锚节点间的最小跳数，然后加1转发到其邻居节点。

2)根据所得到的最小跳数值和锚节的坐标，按照式(1)计算平均每跳距离。

3)根据步骤(2)求出的锚节点所对应的平均跳距，选取出最大的平均跳距。假设步骤(2)求出的所有信标节点对应的平均每跳距离分别为avgsize1,avgsize2,…,avgsizen。

其中,n表示信标节点的个数,则根据式(11)和式(12)得到最大平均跳距和最小平均跳距，即

maxave=MAX[avgsize1,avgsize2，…，avgsizen]

(11)

minave=MIN[avgsize1,avgsize2，…，avgsizen]

(12)

再根据式(10)求出距离为maxave和minave处的RSSI值，设为RSSImaxave，RSSIminave。

4)重复步骤(1)，但是跳数字段按照式(13)来更新跳数信息，即

(13)

式中 RSSIi表示第i跳的RSSI值，RSSIratic表示最大平均跳距，最小平均跳距和通信半径R处的平均接受信号强度值。

5)根据所更新的跳数，按照式(1)来求解平均每跳距离，此时的平均跳距为更新后的跳距。信标节点 所对应的平均跳距设为avgsizei。

6)利用式(13)更新后的跳数信息按式(1)计算出来的平均跳距，按照下式计算待定位节点到锚节点的距离L为

L=avgsizei×Hpcout

(14)

7)根据最大似然估计法计算待定位节点坐标[10]。

4.2 算法分析

假设电磁传播方向一致，并且无线信号功率多为mW级别，极化后接收信号强度[11]转换为负数的dBm。选取最大平均跳距maxave，最小平均跳距minave和半径R处相应的RSSI值，分别设为RSSImaxave，RSSIminave,RSSIR。利用式(10)得到最大平均跳距处的RSSI值

(15)

同理,可求出最小平均跳距

(16)

R处的RSSI值

(17)

RSSI比值原理[12]如图2。

图2 RSSI比值原理图Fig 2 Principle map of RSSI ratio

图2中，OC的距离为最大平均跳距maxave，OE的距离为最小平均跳距minave,OA的距离为通信半径R。求出比例因子RSSIratid为

RSSIratid=(RSSImaxave+RSSIminave+RSSIR)/3

(18)

利用比例因子构造跳数加权系数

hwi=RSSIi/RSSIratid

(19)

式中RSSIi表示节点i的接收信号强度，RSSIratid表示节点在三个不同位置的接收信号强度的平均值。

2)若未知节点恰好在RSSIDIS处，此时的跳数为1。

5 算法仿真

本文利用Matlab仿真软件对实验进行仿真分析。仿真参数设置：在100 m×100 m正方形区域内随机部署200个节点，分别进行了50次仿真实验，并且每个节点具有相同的通信半径R。节点i的定位误差定义为

(20)

式中 (xi,yi)为节点的实际坐标，(xjyj)为算法中估计出的坐标位置。所有待定位节点的平均定位误差定义为

(21)

式中 N为未知节点的个数。定位精度定义为

a=μave/R

(22)

通过部分数据定量分析本文算法的定位误差，表1列出了在通信半径为R=50m，锚节点数为不同比例时，两种定位算法的定位误差。表2列出了在锚节点比例为10 %，

表1 定位误差随锚节点变化关系(R=50 m) Tab 1 Positioning error changes as anchor proportion(R=50 m)

通信半径不同时，两种算法的定位误差。

表2 定位误差随通信半径的变化关系Tab 2 Positioning error changes as communication radius

图3表示在网络节点总数不变，锚节点比例分别取5 %，10 %，15 %，20 %，25 %，30 %，经典DV-Hop算法和改进算法的定位误差。从图中可以看出，随着锚节点数的增加，定位误差都相应减少了。当锚节点数达到25 %左右之后，定位误差变化趋于平缓。当通信半径r=50 m时，改进算法的定位误差相对于原DV-Hop算法下降了22 %左右，定位精度较高，当R=60 m时，下降了25 %左右。

图3 通信半径R=50m和R=60m定位误差率Fig 3 Positioning error rate while communication radius R=60 m and R=70 m

图4表示通信半径为30,35,…,65 m，锚节点数分别取10 %和15 %时，两种算法的定位误差。从图中可以看出，当信标节点比例相同时，随着节点通信半径的增加，定位误差都呈现下降的趋势。当信标节点比例为10 %时，改进算法相对于原算法，定位误差下降了25 %左右，当比例为15 %时，定位误差下降了24 %左右，定位精度优于原算法。

图4 不同通信半径的定位误差比较Fig 4 Positioning error comparison of different communication radius

图5表示在锚节点个数为15，通信半径R=60 m时，两种定位算法的定位误差。由图可知，改进算法能够有效地提高定位精度。并且相对于经典DV-Hop算法，定位精度提高了22 %左右，定位精度较高。

图5 不同节点总数的误差比较Fig 5 Error comparison of different node numbers

6 结 论

本文针对经典DV-Hop算法较大的误差积累问题，提出一种基于RSSI比值的改进算法，其主要原理是选取不同位置处的RSSI值，求解比例因子。利用节点的RSSI值求出跳数的加权系数，经过加权处理后的跳数值更加接近真实值。仿真实验表明:本文改进算法具有较好降低定位误差的作用，定位精度优于原DV-Hop算法。

[1] Chen H,Sezaki K,Deng P,et al.An improved DV-Hop localization algorithm for wireless sensor networks[C]∥Proceedings of the 3rd IEEE Conference on Industrial Electronics and Applications,ICIEA’08,2008:1557-1561.

[2] Caffery J．A new approach to the geometry of ToA location[C]∥Proc of IEEE Vehicular Technology Conference (VTC),2000：1943-1950．

[3] Niculescu D．Positioning in Ad Hoc sensor network[J].IEEE Network,2004，18(4)：24-29．

[4] 刘 凯，余君君，谭立雄．跳数加权DV-Hop定位算法[J]．传感技术学报， 2012，25(11)：1539-1542．

[5] 罗 维，姜秀柱，盛蒙蒙．无线传感器网络选择性DV-Hop定位算法[J]．传感器与微系统，2012，31(3)：71-77．

[6] Gao G Q,Lei L.An improved node localization algorithm based

on DV-Hop in WSNs[C]∥Proceedings of IEEE International Conference on Advanced Computer Control,ICACC ’10,2010:321-324.

[7] Zhang D Y，Cui G D.An union node localization algorithm based on RSSI and DV-Hop for WSNs[C]∥2012 The Second International Conference on Instrumentation,Measurement,Computer,Communication and Control (IMCCC),IEEE,2012：1094-1098.

[8] 张爱清,叶新荣,胡海峰,等.基于RSSI 每跳分级和跳距修正的DV-Hop 改进算法[J].仪器仪表学报,2012,33(11):2552-2559.

[9] 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.

[10] Wang Y H,Zhang J,Nan W,et al.An improved DV-Hop localization algorithm for wireless sensor networks[C]∥International Conference on Intelligent Computation Technology and Automation,2011:576-579.

[11] Zhang W,Yang X,Song Q.DV-Hop localization algorithm based on RSSI correction[J].Journal of Software Engineering,2015,9(1):188-194.

[12] Wang S S,Yin J P,Cai J P,et al .Localization algorithm for wireless sensor networks based on RSSI[C]∥Computer Research and Development,2008:385-388.

雷高祥,通讯作者,E—mail：leigaoxiang1992@163.com。

DV-Hop algorithm for wireless sensor networks based on node RSSI ratio hops correction

FANG Wang-sheng, LEI Gao-xiang, HUANG Hui

(Faculty of Information Engineering, Jiangxi University of Science and Technology,Ganzhou 341000,China)

Aiming at error accumulation issue of traditional DV-Hop localization algorithm in calculating average hop distance and hops between anchor node and unknown node，present a DV-Hop localization algorithm based on RSSI ratio correction.In the improved algorithm,according to RSSI value of different average hop distance select the maximum and minimum average hop distance and communication radiusR,then obtain scale factor.Use it to obtain weighting factor and to correct each hop-count,so as to obtain more accurate hops and average hop distance.The simulation suggests that positioning precision of the proposed algorithm is prior to traditional algorithm.

WSNs; DV-Hop localization algorithm; hops; RSSI scale factor; weighting coefficient

10.13873/J.1000—9787(2016)07—0132—04

2015—10—19

TP 393

A

1000—9787(2016)07—0132—04

方旺盛(1963-)，男，江西上饶人，硕士研究生导师，主要研究方向为无线传感器网络，数字水印，基因表达式编程。