一种基于加权处理和误差修的DV-Hop定位算法研究*

周杭霞,崔 晨,叶佳骏

(中国计量学院信息工程学院,杭州 310018)



一种基于加权处理和误差修的DV-Hop定位算法研究*

周杭霞*,崔 晨,叶佳骏

(中国计量学院信息工程学院,杭州 310018)

针对传统的DV-Hop算法在定位过程中出现的容易引起误差的问题,提出了一种综合考虑所有信标节点的平均跳距并引入权值修正,将信标节点当作未知节点计算误差进而优化精度的距离估计算法,使网络平均跳距和节点位置估计值更加准确。通过相关仿真实验表明:改进算法优化了原算法的定位精度和定位稳定性,达到了预期目标。

无线传感器网络;DV-Hop定位算法;归一加权;误差修正

无线传感器网络是一种特殊的Ad-Hoc网络[1],它由大量静止或移动的传感器以自组织和多跳的方式构成,并通过协作感知、内容采集、汇总处理最终将区域对象中的特定信息报告给用户,对于该网络而言节点的位置信息是网络实现过程较为重要的上下文信息之一[2]。目前国内外关于无线传感器网络节点定位的方法有许多种,其中按是否需要测距可将定位算法分为距离相关定位和距离无关定位两类。距离相关定位算法需要通过测量距离角度等信息实现定位,对硬件和成本要求较高,使得此类方法的应用受到了一定限制。而距离无关算法无需测距技术,仅利用节点间估计距离来计算位置,更适合于大规模无线传感器网络的实际要求,是目前备受关注的定位方法。

DV-Hop算法是目前应用较为广泛的距离无关定位算法[3],采用的主要思想是将定位节点到信标节点之间的距离用平均每跳距离和两者间跳数的乘积来表示[4]。然而在实验中我们发现原始DV-Hop算法在实际应用中误差较大,结果并不准确。现阶段虽然有多种改进方法对算法进行了优化,比如结合RSSI量化模型优化定位结果[5],限定主要参数的最优范围[6],改进定位结果求解的计算方法[7],但是这些算法并没有很好的解决DV-Hop算法多跳路径条件下估计距离不准确、平均跳距计算误差较大等问题[8]。本文通过细化原始算法定过过程中的关键步骤,分析误差产生原因,提出一种综合全网信息,修正定位误差并改进节点定位过程改进方案。仿真结果表明,该方法可以在不增加节点硬件开销的基础上有效减小定位误差,提高定位精度。

1 DV-Hop算法介绍与误差分析

1.1 算法描述

DV-Hop算法由3个阶段组成[9]:

①信息广播与距离计算阶段,这一阶段主要使用典型的距离矢量交换协议,锚节点将位置信息以数据分组的形式在网络中广播,其中跳数信息初始化为0。接受到此分组的每个邻居节点保留最小跳数信息后,跳数加1后转发至下一个节点,这样可以使网络中所有节点获得距锚节点的最小跳数。

②第2阶段,在获得其他锚节点位置和相隔跳距之后,锚节点利用式(1)计算自己的平均每跳距离hopi:

(1)

其中(xi,yi)为信标节点i的位置坐标;hj为信标节点i和j之间的最小跳数。之后信标节点然后将其作为一个校正值广播至网络中。校正值采用可控洪泛法在网络中传播,节点仅接受获得的第1个校正值,而丢弃所有后来者,在大型网络中,可通过为数据包设置一个TTL域来减少通信量[8]。当接收到校正值之后,节点根据跳数计算与锚节点之间的距离。当未知节点获得与3个或更多锚节点的距离后,则在第3阶段执行三边测量法或极大似然估计法求出节点坐标。

③极大似然估计法

当已知节点的个数大于或者等于4时,即节点个数n>=4,一般都采用极大似然估计值法来进行求解。有:

假设它的线性方程为Ax=b,其中

则由以上各个方程可得到线性方程Ax=b的解为:

(2)

此解即使为直接点D的坐标。

1.2 DV-Hop算法的缺陷

通过对传统DV-Hop算法的缺陷进行研究和分析我们发现,由于采用跳数乘以平均跳距来计算未知节点与锚节点间的距离,因此当跳数大于2时就会产生如图1所示的误差。

图1 DV-Hop误差示意图

图1中粗虚线代表锚节点L1和未知节点A的实际距离,而细虚线代表传统DV-Hop算法计算时采用的估计距离,由图示可知,由于无法测量实际距离,虽然DV-Hop算法采用了一种数值逼近的方法近似地获取了两点间的距离,但两者间还存有较大误差[10]。另外,原始算法中求出的平均跳距取值的精确性,每跳实际距离与平均跳距之间差值大小都是最终使得真实距离与计算距离之间产生误差从而影响定位精度[11]的原因之一。

2 改进的DV-Hop算法的实现

虽然传统DV-Hop算法在定位精度上还存在一些缺陷,但是其实现简单,通信开销小,硬件要求低的优点还是使其得到了广泛应用,因此改进算法在充分考虑原始算法优点的同时,针对其中存在的不足之处做了如下优化:

①传统DV-Hop算法中未知节点仅接受距离自己最近的一个信标节点估计出的平均每跳距离值作为自身的平均每跳距离,但相对于整个网络来说,单个锚节点的平均每跳距离值不足以反映全网的整体属性[12],因此我们在计算每个未知节点的平均每跳距离时需要综合考虑所有可以与之通信的锚节点,利用各个锚节点计算出的平均每跳距离与到未知节点跳数的乘积作为距离加权参数,并对所得权值进行归一化处理。其过程具体如下:

首先在信标节点广播跳数和平均每跳距离阶段,未知节点记录所有能获得的信标节点数据,并通过计算两者乘积对数值较大的赋予较小权值λi,λi的取值满足:

(3)

其中n表示未知节点可得到的所有信标个数,j表示其中一个信标节点,dij表示第i个未知节点到第j信标节点的跳数与该信标节点平均每跳距离的乘积。通过这个归一化的加权可以使未知节点获得的n个信标节点的平均每跳距离加权值之和为1。之后通过结合对应信标节点的平均每跳距离Sj,获得未知节点自身的平均每跳距离Si:

(4)

之后再根据DV-Hop算法的计算过程继续下一步的计算。

②虽然通过归一加权处理后使得实验数据比原始算法有了较大改进,但单个节点的计算坐标与真实坐标相比,每个节点仍平均有33%左右的定位误差,为了进一步提高定位精度,我们采用另一种全新的优化方法继续对定位算法结果进行改进,具体过程如下:

在获得原始定位数据后,我们从所有n个信标节点中随机抽取1个信标节点将其转化为未知节点,之后利用剩余n-1个信标节点对其进行定位,获得其定位值e′,之后通过与真实坐标求差获得该点处定位误差值Δe,有Δe=e-e′,此误差可看作其余n-1个信标节点对该点处及周围一定范围内所有未知节点产生的定位误差,然后我们对该点处一个半径为R内的所有未知节点通过Δe值进行误差修正,获得一个修正值当做节点新的位置坐标。最后对剩下n-1个信标节点循环运用此方法进行二次误差修正定位,直到对全部n个信标节点及其周围R范围内的未知节点完成误差修正为止。其中随机分布的信标节点及半径R的修正覆盖区域如图2所示,其中黑色圆点表示随机分布的未知节点,灰色星点表示信标节点。

图2 节点阈值半径R的取值示意图

3 算法仿真与分析

为了验证本文改进算法的性能,利用MATLAB2012b对DV-Hop算法和本文改进算法进行了对比仿真研究,算法仿真实现流程如图3所示。

图3 改进算法流程图

仿真场景为100×100的无线传感器网络区域,未知节点和锚节点均为实验区域内随机生成,实验取当锚节点个数、总节点个数、修正范围半径值R变化时的节点定位误差100次仿真结果平均值,并对其做了对比分析。归一化后每个节点的平均定位误差由式(4)计算,其中un表示待定位的节点个数,r为节点的通信半径,xi,yi表示由算法得到的定位节点坐标,Xi,Yi表示定位节点的真实坐标,error越小表示由定位算法得到的坐标与节点的真实坐标的差距越小[9],定位精度越高。

(5)

通过对原始算法和实验结果的分析我们发现在无线传感器网络中,信标节点个数的变化会同时引起定位精度的改变[13],因此仿真实验中我们设定网络区域内随机分布200个无线传感器节点,通信半径30,二次误差修正半径R为9,信标节点在所有节点中随机选取生成,在节点总数不变的情况下,信标节点数量取值分别为20、25、30、35、40和50时,本文算法与DV-Hop算法的性能比较,仿真结果如图4所示。

从图4可以看出,在节点总数不变的情况下,两种算法的error值都会随着信标节点数增加而减小。当信标节点数为20时,归一加权方法可以使每个节点的平均定位误差减小大约11.30%,之后对半径R内节点采用误差修正的方法后,每个节点平均定位误差再次减少约9.6%,结合来看本文改进算法可以在相同条件下使得节点平均定位误差减少约18.69%,当信标节点比例由10%逐渐增大至20%时,由于可参考的节点信息增加使得平均定位误差值下降较大,之后随着信标节点比例增大误差变化减小并逐渐趋于平稳,当信标节点数为50时,本文第1步改进算法减少每个节点平均定位误差19.63%,第2步改进在此基础上可再次减少定位误差17.23%左右,通过分析实验数据改进算法在此条件下可提高原始DV-HOP算法定位精度约33.48%。总体来看,经过本文第1步归一加权优化后的DV-HOP算法可以减少每个定位节点平均误差14.94%左右,之后采用误差修正半径R范围内节点定位结果可以再次减少误差约10.65%,最终本文改进算法在同等条件下可以减少原始DV-HOP定位算法节点平均定位误差24.01%左右。

图4 误差与锚节点之间关系

在固定区域范围内,区域节点总个数也会对定位误差有影响,节点数较少时可供参考的计算信息减少可能造成定位精度不够,节点数过多又会增加计算复杂度,并造成大量未定位节点从而影响最终实验结果。图5为信标节点数固定为20个,节点总数分别取100、200、250、300和400时本文改进算法对平均定位误差的改变结果。

当节点总数为100时,本文第1步改进算法减少了原始算法每个节点平均误差约9.2%,之后通过误差修正可以再次提高定位精度约7.8%,此条件下本文改进算法可以减少每个节点平均定位误差16.36%左右,之后随着节点总数的增加,平均定位误差会随之减少并逐渐趋于平缓,当节点总数达到400时,本文第1步改进算法可以减少定位误差约12.64%,第2步改进可再次减少约11.14%,此条件下本文改进算法可以减少每个节点平均定位误差23.31%左右。总体来看由于节点位置随机分布,节点总数的增加会造成网络结构的节点连通性的变化,使得定位误差呈现微小振动变化并且曲线下降趋势,但是本文改进算法相比较原始算法还是稳定的减少了定位误差,其中经过第1步优化每个节点平均定位误差下降了约11.33%,经过第2步优化定位误差再次下降约6.72%,总体来看本文改进算法比传统DV-Hop算法在同等条件下可以使定位误差减小16.83%左右。

图5 误差与节点总数之间关系

图6 改进方法中R取值的影响

在第2步改进中,我们添加了误差修正半径R,并将已知的信标节点看作未知节点,依次循环定位进而对结果进行最终优化。其中半径R取值范围的变化也会引起定位结果最终误差值的变化,当R取值较小时会因为修正区域内覆盖节点数不足造成性能减小,而R过大又会造成范围叠加引起节点间的多次修正影响定位精度。因此我们在之前实验条件的基础上,对其中选取的R值变化进行了实验,其中R取值从节点通信半径的10%增长至50%,取得每个节点定位误差计算5次后的平均值,结果如图6所示。

从图6我们可以发现,当修正半径值从2逐渐增加至8～10之间时,单个节点平均定位精度逐渐增加,当R取值范围为9时,节点定位精度的平均提高量达到最高值,每个节点定位精度平均可提高约1.4%左右,此时优化算法误差最小,修正区域覆盖范围更为合理性能最高,之后随着半径R值增大,节点定位精度提高量开始减少,并且由于覆盖区域过大性能逐渐下降,因此最终优化算法采用计算误差并修正半径R范围内节点坐标这一方法时,选取了节点通信半径中最优范围内的R取值,以保证定位精度和优化性能达到最优。

4 结束语

为了解决传统的DV-Hop算法在定位过程中求取的平均每跳距离难以正确反映全网信息,以及定位过程中误差较大,精确度不高的问题[14]提出了一种综合考虑所有信标节点平均跳距并归一加权,将信标节点当作未知节点计算误差并修正的距离估计算法,通过MATLAB软件的验证发现该算法可以使节点位置估计值更加准确,提高了定位精度。未来将继续针对第2种优化方法进行改进,研究在通信能力和信道环境更为复杂的情况下的应用前景,同时将研究如何在移动节点的环境中改善定位结果,使算法应用领域进一步扩大。

[1] 李文辰,张雷. 无限传感器网络加权质心定位算法研究[J]. 计算机仿真,2013,30(2):191-194.

[2]Kumar Shrawan,Lobiyal D K. An Advanced DV-Hop Localization Algorithm for Wireless Sensor Networks[J]. Wireless Personal Communications,2013,71(2):1365-1385.

[3]刘彩霞,黄延磊. WSN中抵御虫洞攻击的改进的DV-Hop算法研究[J]. 传感技术学报,2011,24(10):1473-1478.

[4]赵雁航,钱志鸿,尚小航,等. 基于跳距修正粒子群优化的WSN定位算法[J]. 通信学报,2013,34(9):105-114.

[5]胡斌,李方敏,刘新华. 基于RSSI量化模型的定位算法研究[J]. 武汉理工大学学报,2009,31(23):92-95.

[6]张震,闫连山,刘江涛,等. 基于DV-Hop的无线传感器网络定位算法研究[J]. 传感技术学报,2011,24(10):1469-1472.

[7]赵清华,刘少飞,张朝霞,等. 一种无需测距节点定位算法的分析和改进[J]. 传感技术学报,2010,23(1):122-127.

[8]赵灵锴,洪志全. 基于无线传感器网络的DV-Hop定位算法的改进[J]. 计算机应用,2011,31(5):1189-1192.

[9]石为人,贾传江,梁焕焕. 一种改进的无线传感器网络DV-Hop定位算法[J]. 传感技术学报,2011,24(1):83-87.

[10]李辉,熊盛武,刘毅,等. 无线传感器网络DV-HOP定位算法的改进[J]. 传感技术学报,2011,24(12):1782-1786.

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

[12]戴莹,王建平,张崇巍. 无线传感器网络节点定位算法的研究与改进[J]. 传感技术学报,2010,23(4):567-570.

[13]Myint T Z,Lynn N,Ohtsuki T. Range-Free Localization Algorithm Using Local Expocted Hop Length in Wireless Sensor Networks[C]//Proceedings of International Symposture on Conmmnicatiuns and Information Technologies. Tokyo:IEEE,2010:356-361.

[14]Zhang Y J,Wang K,Yuan S F,ed al. Research of WSN Node Localization Algorithm Based on Weighted DV-Hop[C]//IEEE. 24th Chinese Control and Decision Conference. Taiyuan:2012,3826-3829.

周杭霞(1963-),女,中国计量学院信息工程学院 教授,硕导。主要研究方向算法优化,无线传感网络和信息技术安全,zhx@cjlu.edu.cn;

崔晨(1987-),男,中国计量学院计算机应用技术专业硕士研究生,主要研究方向为无线传感器网络,doublecwork@163.com。

AStudyofDV-HopLocalizationAlgorithmBasedonWeightedProcessingandErrorModification*

ZHOUHangxia*,CUIChen,YEJiajun

(College of Information Engineering,China Jiliang University,Hangzhou 310018,China)

Aiming at the traditional DV-Hop algorithm easily caused error,the current thesis proposes a comprehensive consideration of all beacon nodes average one-hop distance and introducing weights corrected results. At the same time use beacon nodes as unknown nodes calculating error and use the error optimizing accuracy. Finally makes the average one-hop distance and node position estimates more accurate. Theoretical analysis and simulation results show that the proposed algorithm has better locating performance in locating precision and precision stability,achieve the expected goal.

wireless sensor networks;DV-Hop localization algorithm;normalized weighted;error correction

项目来源:国家自然科学基金项目(61027005)

2014-07-12修改日期:2014-10-23

TP393

:A

:1004-1699(2014)12-1699-05

10.3969/j.issn.1004-1699.2014.12.021