基于多移动信标的DV-Hop定位算法

任明明,谢志军,金 光,何加铭

(宁波大学信息科学与工程学院浙江省移动网应用技术重点实验室,浙江宁波315211)

基于多移动信标的DV-Hop定位算法

任明明,谢志军,金 光,何加铭

(宁波大学信息科学与工程学院浙江省移动网应用技术重点实验室,浙江宁波315211)

针对传统DV-Hop定位算法严重依赖拓扑结构的问题,提出一种基于多移动信标和DV-Hop的定位算法MMB-DV-Hop。利用多个移动信标遍历整个DV-Hop定位网络,并且这些信标保持一定的相对位置关系,使用RSSI技术测距并为未知节点提供距离信息以辅助定位,从而有效结合基于测距和基于非测距2种算法的优势。仿真结果表明,与传统算法相比,该算法能减少约10%～15%的归一化平均定位误差,不仅降低对网络拓扑结构的依赖,而且减少了距离估计误差对定位精度的影响,从而提高平均定位精度。

无线传感器网络;定位;DV-Hop算法;多移动信标;非测距;误差

1 概述

无线传感器网络(Wireless Sensor Networks, WSN)是由部署在监测区域内的大量廉价微型传感器节点通过无线通信方式形成的一个多跳的自组织网络系统[1]。

WSN是一种比较新颖的信息获取、处理技术,它在工农业控制、环境监测、危险区域远程控制、物流管理、汽车工业等许多领域都有着广阔的应用前景[2];对于这些应用,位置信息可使感知数据具有意义;位置信息可辅助进行WSN的路由管理、拓扑管理等,因此,研究节点定位技术对无线传感器网络应用意义重大[3]。

本文对无线传感器网络定位算法进行研究,介绍传统的DV-Hop算法,指出该算法的问题所在,在此基础上,提出一种基于多移动信标的DV-Hop定位算法,通过实验仿真和数据统计的结果分析对改进算法进行性能评价。

2 相关工作

根据WSN定位的机制是否需要测距设备,定位算法可分为两大类:基于测距(Range-based)和基于非测距的(Range-free)定位方法[4]。Range-based定位测量节点之间的距离或者角度信息,之后使用三角测量、三边测量或最大似然估计定位法计算节点坐标。常用测距技术有RSSI[5]、TOA[6]、TDOA[7]和AOA[8];Range-free定位无需节点距离和角度信息,通过网络连通性信息就可实现定位。常用的Rangefree定位算法有 Centroid、APIT(Approximate Point in Triangle Test)、DV-Hop[9]、Amorphous、APS(Ad Hoc Positioning System)等。

DV-Hop算法巧妙地将网络的连通信息和距离矢量信息转化为近似的距离测量,是目前研究最广泛的算法之一。文献[10]修正平均每跳距离的角度,分别用最小二乘法校正平均每跳距离、加权处理平均每跳距离等方法优化改进 DV-Hop算法;文献[11]提出了一个锚节点信任度的概念,最后通过加权最小二乘法计算得到未知节点坐标,但是改进算法的通信量和计算量还是比较大的。锚节点之间的跳数一般都为整数,每跳之间距离不尽相同,必然偏离实际距离,因此文献[12]对锚节点之间的跳数进行了修正,使得跳数不再只是整数。

与无信标方法相比,基于移动信标的定位方法能得到更高的定位精度。MBL(Mobile Beaconassisted Localization Algorithm Based on Networkdensity Clustering)算法[13]首先对传感区域内未知节点分簇,计算簇内各个未知节点相对位置坐标,然后使用移动信标信息对簇头节点进行辅助定位,从而得到其他未知节点位置。使用多个移动信标辅助定位可获得更高定位效果。虚拟尺方法将2个信标放在长度固定的车辆上进行辅助定位,车辆移动期间测量各个未知节点之间的距离信息,从而计算得到未知节点位置[14]。

3 改进的DV-Hop定位算法

3.1 传统的DV-Hop算法

DV-Hop定位算法是一种分布式、逐跳计算的节点定位算法[15]。

这种算法分为以下3个步骤:

(1)使用距离矢量交换协议,使网络中所有未知节点获得距离锚节点的跳数。

(2)锚节点获得其他锚节点位置、相隔跳距后,可以计算网络平均每跳距离,然后将其作为一个校正值采用可控洪泛法广播至网络中。当接收到校正值后,节点根据跳数计算与锚节点之间的距离。

(3)当未知节点获得与3个或更多锚节点的距离时,则在第3阶段执行三边测量定位。

如图1所示,已知锚节点N1与N2,N3之间的距离、跳数。N2计算得到校正值(45+76)/(2+5)= 17.29,即平均每跳距离。假设A从N2获得校正值,则它与3个锚节点之间的距离分别为A-N1:3× 17.29,A-N2:2×17.29,A-N3:3×17.29,最后使用三边测量法确定未知节点A的位置。

图1 DV-Hop定位算法示意图

由于DV-Hop算法的定位精度主要由估计的平均每跳距离的精确度决定,因此它的定位精度很大程度上依赖于路线弯曲程度和网络的拓扑结构[16]。在各向同性的密集网络下,DV-Hop才可以得到较好的性能表现。否则,在网路拓扑不规则的随机分布网路下,DV-Hop无法得到合理的平均每跳距离,导致定位精度的急剧下降。

3.2 MMB-DV-Hop定位算法

Range-based定位方法的性能很大程度上依赖于距离测量中产生的误差大小,因此受环境的影响较大[16]。而Range-free定位方法,如DV-Hop方法能够弥补基于测距定位方法的不足,但是它只有在各向同性的密集网络下才能发挥比较好的性能。因此,可以通过结合Range-based和Range-free算法降低测量的精度和环境变化对Range-based算法的影响,以及DV-Hop对路线弯曲程度和网络拓扑结构的依赖。

本文通过在DV-Hop网络中引入3个移动信标,结合Range-based和Range-free 2种定位方法,弥补2种方法的不足之处。一个未知节点至少需要接收到 3个非共线虚拟信标信息,才可通过基于Range-based方法实现定位,如果使用一个移动信标的定位方法,则需要信标多次经过一个未知节点。因此本文提出一种基于多移动信标的DV-Hop定位算法(MMB-DV-Hop),同一时刻可以产生多个虚拟信标,且移动信标经过未知节点可以实现一次性定位该节点,同时在移动信标定位的过程中,实施基于Range-free的DV-Hop定位。

3.2.1 定位方法

移动信标通常携带 GPS(Global Positioning System)以获取自身位置,假定未知节点有RSSI测距能力。接收信号强度指示(RSSI)是通过接收到的信号强度衰减来估算距离的一种测距定位技术,其理论路径耗散函数如下:

其中,PL(d)表示信号在传播距离d后的强度衰减,以dB为单位;η是耗散系数,通常取值为2～4,用于指示耗散相对路径的增加速率;d0是从发射端附近测量的一个参考距离;Xσ是随机环境噪声值,遵循X～N(0,σ2)。

假定s是一个未知节点,真实位置为(xs,ys),估计位置为(x^s,y^y^s);信标节点Bi(i=1,2,3)的坐标值为Bi(xi,yi),它的传输范围在半径为R的圆内。当网络中的一个未知节点有效距离范围内,只存在一个信标信息,通过此信标信息无法定位该未知节点,因此需采用2个或者2个以上的信标节点。

本文采用文献[17]所使用的3个信标节点的位置关系,将3个信标排列成边长为R的等边三角形,如图2所示。

图2 3个信标之间的位置关系

设di(i=1,2,3)是S与Bi之间的距离,即:

如果S测得了3个虚拟信标的距离信息,未知节点便可使用三边测量法进行定位。如图3所示,如果S通过测量只得到2个虚拟信标的距离,假设S测得到B2的距离为d1,到B3的距离为d2,但却未收到来自B1的信号,通过式(3)可得到2个对称的位置S和S′,由于S必定在△B2B3A2内,可把S′排除,那么S的位置便确定。如果此时只有2个移动信标,S则无法确认自身位置(有可能是S′)。当信标节点到达3个以上,最终可能进一步提高精度,但是成本明显提高。因此,本文采用3个移动信标进行辅助定位:

图3 S的2种可能位置

算法 MMB-DV-Hop算法

算法主要分为2个阶段:

(1)3个移动信标节点以固定的位置关系,按照指定的信标移动路径在传感区域移动并周期性地广播信息包,信息包中有自身位置坐标和初始跳计数1。每个节点都记录并更新表{ki,(xi,yi)},其中, (xi,yi)为信标节点的坐标;ki为信标节点i到该节点的跳数,只保留一跳和二跳节点信息。通信半径内所有未知节点都不断检查是否接收到2个或者2个以上的信标节点信息包,如果接收到3个信标信息则可以通过三边测量法进行定位,接收到2个信标信息则可以按式(3)进行定位,这些未知节点定位成功成为虚拟信标。

(2)当3个移动信标遍历整个传感区域,如果仍有未知节点,则采用DV-Hop算法进行定位。当移动信标穿越整个传感区域或者设置的阈值达到最大值,DV-Hop定位算法启动。可以设置阈值为信标的数目。

3.2.2 信标移动路径的设计

对于依赖于移动信标的定位应用中,找到一条最优的移动路径对提高定位性能有很大帮助。而MMB-DV-Hop算法主要是通过移动信标产生大量的最优虚拟信标,并且结合三边测量法和DV-Hop来提高定位精度,移动信标的运动路径应该要保障在最短时间里尽量走完传感区域。因此,MMB-DV-Hop算法可以采用网格扫描(Scan)模型,如图4所示。

图4 网格扫描移动模型

图5 移动路径的覆盖情况

4 性能仿真

为了验证改进算法MMB-DV-Hop的有效性和可行性,利用Matlab7.8对本文改进算法、文献[18]基于RSSI的Range-free算法和传统DV-Hop算法进行仿真对比研究。

4.1 仿真环境与参数选择

在不同锚节点比例、不同节点个数的条件下对比文献[18]、传统DV-Hop和改进算法,从以下2个方面分析算法的性能:

其中,K为仿真次数;Un为未知节点的总数。归一化平均定位误差为平均误差error与通信半径R的比值:

(2)归一化的平均定位误差的均方差。所有未知节点的平均定位误差的均方差δ为:

归一化的平均定位误差的均方差为:

4.2 结果分析

向目标传感区域随机部署100个节点,节点密度平均为10.18,节点通信半径R为20 m,移动信标按照指定的路径走完传感区域,分析算法在不同在锚节点比例下的情况。在节点总数保持不变情况,在比例为0.05,0.15,0.20,0.25,0.30,0.35,0.40等不同锚节点比例下,节点归一化平均定位误差如图6所示,节点归一化定位误差的均方差关系对比如图7所示。

图6 归一化平均定位误差与锚节点的关系

图7 归一化定位误差的均方差与锚节点的关系

从图6中3条曲线的走势可以看出,3种定位算法的归一化平均定位误差都随着锚节点比例的增加而减小,最后趋于平稳状态;本文改进算法从锚节点为0.2开始,归一化平均误差就保持在0.3左右,相比传统 DV-Hop算法和文献[18]基于 RSSI的Range-free算法有明显的改进;MMB-DV-Hop的归一化平均定位误差相比传统DV-Hop算法降低了约10% ～15%。

归一化定位误差的均方差度量了节点与平均定位误差的偏离程度,均方差值越小,说明网络节点定位结果越稳定,则定位误差就集中分布在平均定位误差的两侧,均方差值越大,则定位结果越难以确定。在图7中,本文改进算法的归一化平均定位误差在对比的锚节点比例下都比其他2种定位算法小,最后趋于稳定值。当锚节点比例为0.4时,本文改进算法MMB-DV-Hop的归一化定位差的均方差值为0.207 8,而传统DV-Hop算法为0.278 4。由此说明本文改进算法的未知节点定位计算更稳定,不会出现节点定位误差偏离平均定位误差较大的情况,有更高的可信度。

向目标传感区域部署节点数分别为100,150, 200,250,300,350,400个,而且保持锚节点比例为10%,节点通信半径R为20 m的情况下,节点归一化平均定位误差、归一化定位误差的均方差与总节点个数的对比关系如图8和图9所示。由图8的结果可以看出,2种定位算法的归一化平均定位误差随着总节点个数的增加而减少,最后趋于稳定。由于在传感区域不变的情况下,节点总数的增加使得网络的平均网络连通度增大,即节点密度增大,定位精度相应提高了;当总结点个数为100时,本文改进算法的归一化平均定位误差为0.362 1,比传统DVHop算法减少15%左右。在图9的结果中,改进算法比传统DV-Hop的定位误差均方差平均少2%～10%,比文献[18]基于RSSI的Range-free算法平均少3%～14%,由此可知本文改进算法相对稳定。由图8和图9可知,与传统DV-Hop定位算法相比,在节点数相对较少的情况下,改进算法的性能相对突出。

图8 归一化平均定位误差与总节点个数的关系

图9 归一化定位误差的均方差与总节点个数的关系

5 结束语

本文通过分析传统DV-Hop算法的优缺点,将多个移动信标引入DV-Hop网络,给出一种基于多移动信标的无线传感网络定位算法MMB-DV-Hop。仿真结果表明,与传统的DV-Hop和基于测距的质心定位算法相比,MMB-DV-Hop定位方法具有良好的定位精度,定位性能稳定性较高,MMB-DV-Hop比较适合在节点数相对较少情况下进行定位。然而基于移动信标的定位方法就不适用于需要快速定位的网络,因此,如何规划移动信标的移动路径,从而快速覆盖传感网络区域将是进一步研究的方向。

[1] 孙利明,李建中,陈 瑜,等.无线传感器网络[M].北京:清华大学出版社,2005.

[2] Trigoni N,Krishnamachari B.Sensor Network Algorithms and Applications[J].Philosophical Transactions of the Royal Society A:Mathematical,Physical and Engineering Sciences,2012,370(1958):5-10.

[3] 崔焕庆,王英龙,郭 强,等.多移动信标辅助的分布式节点定位方法[J].通信学报,2012,33(3):103-111.

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

[5] Huang C T,Wu C H,Lee Y N,et al.A Novel Indoor RSS-based Position Location Algorithm Using Factor Graphs[J]. IEEE Transactions on Wireless Communications,2009,8(6):3050-3058.

[6] Jeon N R,Lee H B,Park C G,et al.Super Resolution TOA Estimation with Computational Load Reduction [J].IEEE Transactions on Vehicular Technology,2010, 59(8):4139-4144.

[7] Matin R K,Yan Chunpeng,Fan H H,et al.Algorithms and Bounds for Distributed TDOA-based Positioning Using OFDM Signals[J].IEEE Transactions on Signal Processing,2011,59(3):1255-1268.

[8] Yu Kegen,Guo Yingjie.Statistical NLOS Identification Based on AOA,TOA and Signal Strength[J].IEEE Transactions on Vehicular Technology,2009,58(1): 274-286.

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

[10] 林金朝,陈晓冰,刘海波.基于平均跳距修正的无线传感器网络节点迭代定位算法[J].通信学报,2009, 30(10):107-113.

[11] 朱 敏,刘昊霖,张志宏,等.一种基于DV-Hop改进的无线传感器网络定位算法[J].四川大学学报:工程科学版,2012,44(1):93-98.

[12] 肖丽萍,刘晓红.一种基于跳数修正的DV-Hop定位算法[J].传感技术学报,2012,25(12):1726-1730.

[13] 赵 方,马 严,罗海勇,等.一种基于网络密度分簇的移动信标辅助定位方法[J].电子与信息学报, 2009,31(12):2988-2992.

[14] Ding Yong,Wang Chen,Xiao Li.Using Mobile Beacons to Locate Sensors in Obstructed Environments[J]. Journal of Parallel and Distributed Computing,2010,70 (6):644-656.

[15] Niculescu D,Nath B.DV Based Positioning in Ad Hoc Networks[J].Telecommunication Systems,2003,22(1-4):267-280.

[16] Sichitiu M L,Ramadurai V.Localization of Wireless Sensor Networks with a Mobile Beacon[C]//Proc.of IEEE International Conference on Mobile Ad-hoc and Sensor Systems.[S.l.]:IEEE Press,2004:174-183.

[17] Zhang Zusheng,Yu Fengqi.Collaborative Localization Algorithm for Wireless Sensor Networks Using Mobile Anchors[C]//Proc.of Asia-Pacific Conference on Computational Intelligence and Industrial Applications [S.l.]:IEEE Press,2009:309-312.

[18] 刘 锋,章登义.基于RSSI的无线传感器网络质心定位算法[J].计算机科学,2012,39(6):96-98.

编辑 任吉慧

DV-Hop Localization Algorithm Based on Multi-mobile Beacon

REN Ming-ming,XIE Zhi-jun,JIN Guang,HE Jia-min
(Key Laboratory of Mobile Internet Application Technology of Zhejiang Province, College of Information Science and Engineering,Ningbo University,Ningbo 315211,China)

Due to the serious dependence on the topology of the network in DV-Hop algorithm,a DV-Hop localization algorithm based on multi-mobile beacon called MMB-DV-Hop is proposed in this paper.The algorithm incorporates Range-based and Range-free algorithms by introducing multi-mobile beacons into the DV-Hop positioning network,and the beacons keep a certain relative position while traversing the entire network and ranging with RSSI to provide information to unknown nodes to estimate locations.Simulation results show that the proposed algorithm has better locating performance in positioning accuracy by reducing the dependence on the topology of the network and the influence of distance estimation error on the positioning accuracy.

Wireless Sensor Networks(WSN);localization;DV-Hop algorithm;multi-mobile beacon;Range-free; error

1000-3428(2014)10-0092-06

A

TP393

10.3969/j.issn.1000-3428.2014.10.018

国家自然科学基金资助项目(60902097);浙江省自然科学基金资助项目(LY12F02013);浙江省科技厅重大科技专项基金资助重点工业项目(2011C11042);宁波市自然科学基金资助项目(2012A610013,2012A610014);宁波大学研究生重点课程建设基金资助项目(zdkc2012004)。

任明明(1986-),男,硕士研究生,主研方向:无线传感器网络;谢志军,副教授、博士;金 光、何加铭,教授、博士。

2013-08-28

2013-11-05E-mail:lieque1130@163.com

中文引用格式:任明明,谢志军,金 光,等.基于多移动信标的DV-Hop定位算法[J].计算机工程,2014, 40(10):92-97.

英文引用格式:Ren Mingming,Xie Zhijun,Jin Guang,et al.DV-Hop Localization Algorithm Based on Multi-mobile Beacon[J].Computer Engineering,40(10):92-97.