一种无线传感器网络定位算法的改进

梁 青, 韩昊澎, 李卓冉, 熊 伟

(1.西安邮电大学 电子工程学院， 陕西 西安 710121； 2.空军工程大学 信息与导航学院， 陕西 西安 710077)

一种无线传感器网络定位算法的改进

梁 青1, 韩昊澎1, 李卓冉1, 熊 伟2

(1.西安邮电大学 电子工程学院， 陕西 西安 710121； 2.空军工程大学 信息与导航学院， 陕西 西安 710077)

为了减小距离向量-跳段(DV-hop)算法中计算平均跳距时所造成的误差对定位的影响，提出一种基于测距信息的改进DV-hop算法。改进算法充分考虑DV-hop算法中信标节点计算平均跳距误差较大这一因素，将接收的信号强度指示(RSSI)算法中测得信号强度值转化为距离信息，再将距离信息引入DV-hop算法平均跳距的计算中，并在不同信号传播模型下进行仿真分析。仿真结果表明，在同一信号传播模型下，改进算法比原DV-hop算法有着更小的定位误差。

无线传感器网络；距离向量-跳段(DV-hop)；接收信号强度；传播模型

无线传感器网络(Wireless senor network, WSN)是由大量的传感器节点以及汇集节点构成的多跳自组织网络。在监测区域内部署的传感器节点感知采集监测区域内的信息，通过多跳、无线通信的方式将采集到的信息在网络中传递并最终传送给汇集节点[1]。传感器网络节点的位置信息在应用中有着重要意义，定位技术是无线传感器网络的主要支撑技术[2]。

定位技术分为基于距离(Range-Based)的定位技术和与距离无关(Range-Free)的定位技术。距离向量-跳段(Distance Vector-Hop, DV-hop)算法是最受关注的与距离无关的定位算法[1];接收的信号强度指示(Received signal Strength Indicator, RSSI)定位算法是一种典型的基于距离的算法[3]。文[2]通过对DV-hop算法的网络参数进行优化以减小定位误差；文[3]提出一种混合定位策略，在同一种网络中采用多种定位算法以减小定位误差。文[4]在各向异性的网络条件下对DV-hop算法进行了仿真分析。

DV-hop算法的优点是功耗小，但完全依赖信标节点，定位误差较大。RSSI算法实现简单，但定位精度受信号的衰落影响大。针对此种特点，本文拟提出一种基于信号功率的改进DV-hop算法，对DV-hop算法平均跳距的计算进行修正，以减小其定位误差。

1 DV-hop算法

DV-hop算法根据传感器节点的能量有限、节点间采用多跳通信且节点只与邻居节点进行数据交换等特点对未知节点进行定位。在距离-向量定位机制下，未知节点与信标节点进行通信，先记录两者间的最小跳数，再计算平均跳距，平均跳距乘以最小跳数，得到信标节点与未知节点之间的计算距离，最后利用极大似然估计法或三边测量法估算未知节点的位置坐标。

DV-hop算法的基本定位过程描述如下。

(1)记录信标节点与未知节点之间的最小跳数。

网络部署完成后，未知节点接收到周围信标节点所广播的自身位置信息，包括未知节点与信标节点间的跳数字段，未知节点记录能接收到周围每个信标节点的最小跳数。在图1所示的无线传感器感知区域中，L1、L2和L3为信标节点，其余节点为传感器,信标节点L1到L2的最小跳数为2，信标节点L1到L3的最小跳数为6。

图1 DV-hop算法实例

(2)信标节点与未知节点平均跳段距离计算。

信标节点根据第一个阶段中记录的该节点到其他信标节点的跳数与位置信息，计算平均跳距[5]。平均跳距

(1)

其中(xi,yi)和(xj,yj)分别是信标节点i和j的坐标，hj是信标节点i和j(j≠i)之间的跳段数。如图1可知，信标节点L1与L2之间的距离为40m，L2与L3之间的距离为75m，L1与L3之间的距离为100m,则未知节点到信标节点L1的平均跳距为

到信标节点L2的平均跳距为

到信标节点L3的平均跳距为

(3)利用极大似然估计法或三边测量法对未知节点位置进行估算。

未知节点根据第二阶段中所计算的到周围信标节点的平均跳距，根据极大似然估计法或三边测量法计算位置坐标。

综上，DV-hop算法中平均跳距完全依赖于信标节点，当网络中信标节点分布均匀，DV-hop算法有较好的定位性能，当网络中信标节点分布不均匀时，DV-hop算法定位误差较大。

2 传播模型

传感器节点信号的传播模型对基于距离的定位算法存在着重要影响。在传感器网络部署完成后，网络所处的地理环境，天气以及节点自身的影响等都与传播模型有关，节点间进行数据的收发时，在不同的信号传播模型下，RSSI算法有着不同的定位性能。

2.1 规则传播模型

在规则传播模型(RegularModel,RM)中，信号接收强度的表达式为[6]

(2)

其中PR为接收信号功率，PT(d)为发射信号功率，PL(d0)为信号传播参考距离,d0是损耗功率，η为路径损耗指数，d为传播距离。

规则传播模型是理想模型，未考虑信号在实际传播中受环境因子影响以及传播过程中受到障碍物的阻挡而造成的衰落。因此，适用范围较小，在实际部署的网络环境中造成的误差较大。

2.2 对数-阴影衰落模型

基于无线电波的传播特性，以及反射、折射、衍射、散射、节点差异性等因素的存在，相同的传感器节点将随着环境的变化具有不同的信号传播能力，因此，实际应用中传感器节点的信号传播具有衰落性。对数-阴影衰落模型(LogarithmicAttenuationModel，LAM)是一种典型的规则信号衰落模型，其信号接收强度的表达式为[6]

(3)

其中Xσ是由网络部署的环境造成的均值为零的阴影损耗，是均值为0，标准差为σ的高斯随机变量。该模型接收信号的均值表达式为[7-8]

(4)

对于RM和LAM，信号在各个方向上的路径衰落都是相同的[9-11]，即具有各向同性，但LAM考虑到环境因素对信号的影响，增加了信号阴影衰落，更符合实际环境[12]。

3 DV-hop算法改进

当网络中信标节点分布均匀，信号的传播模型较为规则时，DV-hop算法有较小的能耗和较好的定位性能[13-14]。当整个网络中信标节点局布分布不均匀，则DV-hop算法性能明显下降[15-16]。针对这种问题，可考虑采用以下改进方法。

参照RSSI定位算法测距原理，将实际测得未知节点与信标节点间距离引入DV-hop算法平均跳距的计算中，用测得未知节点与信标节点间实际距离替代信标节点间距离来计算平均跳距，以修正网络中节点分布的均匀度对定位性能的影响，减小计算平均跳距的误差。改进后算法的基本步骤如下。

(1)计算未知节点与每个信标节点的最小跳数。

(2)参照RSSI算法中理论模型，确定未知节点到通信半径内所有信标节点的距离dij。当信号传播模型采用RM时，dij由式(2)确定,当信号传播模型为LAM时，信号传播模型由式(3)确定。

(3)计算未知节点与信标节点的实际跳段距离

(5)其中k为信标节点数,hij为未知节点到信标节点的最小跳数，而未知节点到信标节点之间的距离dij取决于

(6)

(4)按照DV-hop算法用平均跳距计算距离并利用三边测量法或极大似然估计法计算自身位置。

4 仿真分析

在相同的节点布局条件下，采用Matlab多次仿真并求均值，对原DV-hop算法与改进算法进行仿真分析。假设定位误差定义为

(7)

其中(xi,yi)为未知节点的估计坐标，(xj,yj)为未知节点的实际坐标，N为未知节点个数，R为节点的通信半径。

假设在1 000×1 000m2的方形区域中随机部署300个节点，节点通信半径为200m，分别在RM及LAM两种模型下，就信标节点比例由0.1增加到0.5，对原DV-hop算法与改进算法进行100次仿真，取其平均定位误差，结果如图2所示。

(a) RM模型

(b) LAM模型

由图2可知，原DV-hop算法与改进算法误差都随着信标节点比例的增加而下降并趋于平稳。当传播模型为RM时，改进算法定位误差降低了18%；当传播模型为LAM时，改进算法定位误差降低了10%。

若假设在1 000×1 000m2的方形区域中，信标节点比例保持为0.3，节点通信半径为200m。当节点总数由100变化到300时，原DV-hop算法与改进算法仿真100次的平均定位误差如图3所示。

(a) RM模型

(b) LAM模型

由图3可知，当节点总数为100，在信标节点比例为0.3时，两种算法都有着较大的定位误差，随着节点总数的增加，两种算法的定位误差都逐渐下降并趋于平稳。节点总数越少，定位误差越大。当信号模型为RM时，改进算法定位误差降低了19%,而当传播模型为LAM时，改进算法相比较与原DV-hop算法，定位误差降低了13%。

5 结 语

在DV-hop定位算法的基础上提出一种基于RSSI值的改进DV-hop算法。改进DV-hop算法利用RSSI值转化为距离，对原DV-hop算法平均跳距的计算进行修正，并在两种传播模型下进行仿真分析。仿真结果表明，改进DV-hop算法相比较原DV-hop算法在RM和LAM两种模型下都有着更小的定位误差。

[1] 孙利民,李建中,陈渝,等.无线传感器网络[M].北京:清华大学出版社,2005：146-151.

[2] 李牧东,熊伟,梁青,等.无线传感器网络DV-hop定位算法研究[J].空军工程大学学报:自然科学版,2012,13(4):75-79.

[3] 方震,赵湛,郭鹏,等.基于RSSI测距分析[J].传感技术学报,2007,20(11):2526-2530.

[4] 王敬东,贲伟,马骏,等.无线传感器网络混合定位技术研究[J].现代电子技术,2012,35(18):60-63.

[5] 梁青,熊伟,韩昊澎.各向异性无线传感器网络DV-Hop算法性能仿真[J].西安邮电大学学报,2013,18(5):31-36.

[6] 许红艳,王经卓,董自健,等.MDS-MAP算法在不同传播模型中定位误差的比较[J].淮海工学院学报,2012,21(1):15-19.

[7] 方海涛,雷菁,胡昆明,等.基于RSSI修正的改进DV-hop测距算法[J].通信技术,2012,45(2):16-18.

[8] 张品,孙岩.一种新的无线传感器网络DV-hop算法[J].电子器件,2010,33(1):117-120.

[9] 曹珊,何志琴,杨靖.无线传感器网络中一种改进的DV-hop算法[J].现代机械,2012,12(4):71-73.

[10] 刘刚,周兴社,马骏岩,等.传感器网络节点的测距与定位[J].传感器与仪器仪表,2007,23(5):189-190.

[11] 张杰,胡向东.定位技术在无线传感器网络中的应用[J].论文选粹,2008,11(8):34-36.

[12] 竺如生.基于DV-hopWSN改进算法的研究与仿真[J].计算机应用,2012,31(6):18-20.

[13] 王福豹,史龙,任丰原.无线传感器网络中的自身定位系统和算法[J].软件学报,2005,16(5):857-868.

[14] 颜嘉俊,雷勇.基于RSSI的无线传感器网络节点定位[J].计算机仿真,2012,29(7):151-154.

[15]MaoG,FidanB,AndersonB.Wirelesssensornetworklocalizationtechniques[J].ComputerNetwork,2007,51(6):2529-2553.

[16]NiculescuD,NathB.Ad-hocpositioningsystem(APS)[C]//Proceedingsofthe2001IEEEGlobalTelecommunications.USATexasSanAntonio:IEEE,2003:1734-1743.

[责任编辑:王辉]

Improvement of a hybrid localization algorithm in wireless sensor network

LIANG Qing1, HAN Haopeng1, LI Zhuoran1, XIONG Wei2

(1. School of Electronic Engineering, Xi’an University of Posts and Telecommunications, Xi’an 710121, China； 2. Institute of Information and Navigation, Air Force Engineering University, Xi’an 710077, China)

In order to reduce the effect on positioning from the average hop distance error calculated by the DV-hop algorithm, a kind of improved DV-hop algorithm based on RSSI ranging is proposed. Considering the effect of beacon nodes while calculating the average hop distance in DV-hop，the improved algorithm can transform the measured signal intensity values into the distance information from RSSI algorithm ranging. Simulations are carried out in different transmission models and results show that the improved algorithm has smaller location error than the original algorithm in the same transmission model.

wireless sensor network, DV-hop algorithm,

signal strength indictor, transmission model

10.13682/j.issn.2095-6533.2014.03.003

2013-11-25

国家自然科学基金资助项目(61202490)；陕西省教育厅科学研究计划基金资助项目(11JK1013)

梁青(1966-)，女，副教授，从事无线传感器网络研究。E-mail：liangqing@xupt.edu.cn 韩昊澎(1988-)，男，硕士研究生，研究方向为无线传感器网络。E-mail：han_hao_peng@foxmail.com

TP393

A

2095-6533(2014)03-0011-04