无线传感器网络中DV-Hop定位算法的改进

曾福庚

(海南热带海洋学院 数学系,海南 三亚,572022)



无线传感器网络中DV-Hop定位算法的改进

曾福庚

(海南热带海洋学院 数学系,海南 三亚,572022)

针对无线传感器网络无需测距的DV-Hop定位算法中存在误差率较大的问题,本文从两个方面对其进行了改进:引入平均误差修正信标节点间的平均每跳距离;引入权重因子计算未知节点坐标.仿真结果表明,改进算法比传统DV-Hop算法误差率更低,能更好地应用于实际场景.

无线传感器网络; DV-Hop定位算法;平均每跳距离;权重因子

0 引言

传感器是一种能获取并将估计物理量转换成信号的设备,且其输出信号可以由观察者或仪器读取.传感器在无线网络中获得输入信息,存储信息,转换和传输数据到其他设备[1].比如,热电偶转换温度的输出电压可以通过一个电压表读取.无线传感器网络(WSNS)包括数以千计的节点,其内置传感器可以从周围环境收集各种信息,已被广泛用于工业生产、环境监测、军事侦察等领域[2].定位技术是无线传感器网络研究的最重要的问题之一,因为在任何情形中都很需要了解节点的位置信息.诸如火山监控、水质监测、精确农业等环境监测的应用中,如果不知道捕获的数据是在什么位置获取的,那么测量数据是无意义的.此外,节点位置估计还可以在库存管理、入侵检测、道路交通监控、健康监测、侦察和监视等方面有诸多应用.

当前的定位算法主要分为两类:基于测距的定位算法(Range-based)[3]和无需测距定位算法(Range-free)[4].基于测距的定位算法通过测量节点间点对点的距离或角度等信息来实现定位,其定位精度高,对硬件和成本的需求也较高.无需测距定位算法利用网络的连通性,通过节点间的距离来估计未知节点的位置.受到传感器价格、体积、功耗以及可扩展性等因素的限制,基于测距的定位算法在实际使用中有一定的局限性,而无需测距定位算法具有更高的实用性.

DV-Hop (Distance Vector Hop)算法[5-6]是当前研究应用中最为广泛的一种无需测距定位算法,其通过距离矢量的路由协议获得各信标节点的信息,突破了未知节点须与信标节点相邻才能实现定位的限制[7].然而随着未知节点到达信标节点跳数的增加,测距误差也会越来越大,因而计算未知节点和信标节点的距离估算也比较粗糙.本文通过修正信标节点间的平均每跳距离以及引入权重因子对DV-Hop算法进行改进.仿真结果表明,改进后的方案可以有效地减少误差,更好地提高DV-Hop算法的定位精度.

1 DV-Hop算法简介

DV-Hop[5-6]算法由Niculescu D等人提出,通过计算距离矢量和节点之间的跳数来估算未知节点到信标节点的距离,并应用多边测量法或者最大似然估计计算未知节点的位置情况.DV-Hop算法主要由以下3个阶段组成:

第1阶段(计算最小跳数值): 信标节点通过典型的距离矢量路由交换协议广播自身ID和坐标信息,使网络中所有节点能计算到各信标节点的最小跳数值h.

第2阶段(计算平均每跳距离值): 信标节点根据上一阶段收到的最小跳数值和自身坐标信息,利用式(1)计算自身的平均每跳距离值.

(1)

其中信标节点i和信标节点j的坐标分别为(xi,yi),(xj,yj);hij表示信标节点j到信标节点i的最小跳数值;dij表示信标节点i和信标节点j的距离.Hopsizei表示信标节点i的平均每跳距离.

信标节点在计算出平均每跳距离值后,将它作为校正值在网络中泛洪广播,未知节点收到后,将校正值乘以到该信标节点的最小跳数值作为未知节点与信标节点的距离.

第3阶段(定位估计值计算): 当未知节点获得到三个以上信标节点的距离时,通过使用最大似然估计计算未知节点的坐标.

令信标节点集合S=(xi,yi)T,其中i=1,2,…,N,N,表示信标节点的个数,未知节点坐标X=(x,y)T到信标节点i的最小跳数值为hi.由第2阶段所知,未知节点X=(x,y)T到信标节点i的距离值为

di=hi×Hopsizei.

(2)

未知节点X到N个信标节点的距离表示如下:

(3)

将(3)中前N-1个方程依次减去第N个方程并整理得:

(4)

记式(4)为AX=b,其中

(5)

(6)

使用最小二乘法可以得到未知节点X的估计坐标为:

X=(ATA)-1ATb.

(7)

2 改进的DV-Hop定位算法

通过对DV-Hop定位算法的原理深入研究,其误差主要是由最小跳数值计算出的平均每跳距离造成的,因此,设法提高后两个工作步骤,即在定位过程的第2步中对校验值进行修正和第3步中引入权重因子计算未知节点坐标.

2.1 细化第2阶段(计算校验值)

在DV-Hop算法第2阶段中,将信标节点间的距离求和除以它们相互的跳数之和作为每跳平均距离,每个信标节点将此估计值作为校正值在网络中泛洪广播.由于在网络中节点之间的连通一般不是直线,所以计算出来的校正值要比实际值偏大.信标节点之间实际距离和估计距离存在一定的误差,而且一般情况下实际距离要比估计距离小.

(8)

(9)

2.2 细化第3阶段(未知节点坐标计算)

在DV-Hop算法第3阶段中,对未知节点坐标的计算引入权重因子wp,i,其中p表示未知节点,i表示信标节点.假设某个未知节点到达信标节点的跳数越大,它们之间的距离误差也会越大,对应的加权应当较小,故取权重因子如下:

(10)

将权重因子wp,i(i=1,2,…,N-1)写成对角矩阵式,有

(11)

使用最小二乘法可以得到未知节点X的估计坐标为

X=(ATWTAW)-1ATWTWb.

(12)

3 仿真分析

为了验证改进算法的性能,本节使用MATLAB 2014a对传统DV-Hop定位算法和改进算法在不同条件下进行对比分析.在模拟实验中,所有信标节点和未知节点都是随机部署在平面区域内,通过改变信标节点的数量和传感器节点的数量两个方面来比较两个算法的性能.在模拟中,定位平均误差函数[8-9]如下:

(13)

其中(xe,ye)表示未知节点的估计坐标,(xt,yt)表示未知节点的实际坐标,是网络中所有节点的个数,R为节点通信半径.

3.1 改变信标节点比率

首先比较传统DV-Hop定位算法和改进算法在不同信标节点比率下的性能.假设所有节点的数目是80,传感器节点的通信半径为10m. 取50次模拟结果的平均值作为误差率,逐步增加信标节点的比例,具体的结果如图1所示.

图1 不同信标节点比率下的比较

图2 不同信标节点总数下的比较

由图1观察到,随着信标节点比例的增加,误差率有减少的趋势.改进算法要明显优越优于传统DV-Hop定位算法.在不同的信标节点比率下,改进方案要优于传统DV-Hop算法大约20%.

3.2 改变节点总数

比较两个算法在不同节点总数下的性能.假设信标节点的比率为20%,传感器节点的通信半径为10m.取50次模拟结果的平均值作为误差率,逐步将节点总数从30增加到100,得到的结果如图2所示.

由图2观察到,随着节点总数的增加,误差率有减少的趋势,并逐步趋向于平稳.因为改进算法引入了修正校正值和权重因子,所以在相同条件下,改进算法误差率要明显低于传统的DV-Hop算法,总体改进方案要优于传统DV-Hop算法大约15%.

4 结论

本文改进算法分为两个方面:修正每跳平均距离以及引入权重因子计算未知节点坐标.计算量方面,改进算法要比传统DV-Hop算法计算量稍大,但总体能以相对较小的计算量获得较低的误差率.降低误差率是定位算法的一个关键目标,而仿真分析结果表明:在不同的信标节点比率下,改进方案要优于传统DV-Hop算法大约20%,此外在不同的节点总数下,改进方案要优于传统DV-Hop算法大约15%,因此改进方案在实际应用中更具优势.

[1]GargM,GorshiEA,SinghEM.AReviewonLocalizationTechniquesinWSN[J].InternationalJournalofEngineeringScience, 2016, 6(5): 5804-5808.

[2]DaiH,ChenAG,GuXF,etal.Localisationalgorithmforlarge-scaleandlow-densitywirelesssensornetworks[J].Electronicsletters, 2011, 47(15): 881-883.

[3]杨凤,史浩山,朱灵波,等.一种基于测距的无线传感器网络智能定位算法[J].传感技术学报, 2008, 21(1): 135-140.

[4]LiM,LiuY.RenderedPath:Range-FreeLocalizationinAnisotropicSensorNetworksWithHoles[J].IEEE/ACMTransactionsonNetworking, 2010, 18(1): 320-332.

[5]NiculescuD,NathB.DVbasedpositioninginadhocnetworks[J].TelecommunicationSystems, 2003, 22(1-4): 267-280.

[6]NiculescuD,NathB.Adhocpositioningsystem(APS)usingAOA[C].INFOCOM2003.Twenty-SecondAnnualJointConferenceoftheIEEEComputerandCommunications.IEEESocieties.IEEE, 2003, 3: 1734-1743.

[7]周玲, 康志伟, 何怡刚.基于三角不等式的加权双曲线定位DV-HOP算法[J].电子测量与仪器学报, 2013, 27(5): 389-395.

[8]马淑丽, 赵建平.多通信半径的无线传感器网络DV-Hop定位算法[J].传感技术学报, 2016(4): 593-600.

[9]ZhangJ,GuoN,LiJ.AnImprovedDV-HopLocalizationAlgorithmBasedontheNodeDeploymentinWirelessSensorNetworks[J].InternationalJournalofSmartHome, 2015, 9(10): 197-204.

(编校:何军民)

Improved DV-Hop Localization Algorithm for Wireless Sensor Networks

ZENG Fu-geng

(Department of Mathematics, Hainan Tropical Ocean University, Sanya Hainan 572022, China)

The conventional DV-Hop algorithm is a typical range-free localization algorithm. It will bring about large error, due to taking average hop distance as the expected distant. In order to reduce the error, the original algorithm was improved from two aspects. Firstly, the average hop distance of the beacon nodes was corrected by introducing the average hop distance error. Secondly, the weight factor was added so as to calculate the coordinates of the unknown nodes. The simulation results show that the improved algorithm has lower error rate than that of the conventional DV-Hop algorithm, thus it applies to the actual scene more accurately.

wireless sensor networks; DV-Hop localization algorithm; average hop distance; weight factor

2016-08-14

三亚市院地科技合作项目(2015YD14)

曾福庚(1983-), 男,汉族,江西吉安人,海南热带学院数学系副教授,博士,研究方向为应用数学与密码学.

TP393

A

1008-6722(2016) 05-0068-04

10.13307/j.issn.1008-6722.2016.05.13