一种基于IDV-Hop算法的改进定位机制*

吕春峰,朱建平,陶正苏

(1.上海海洋大学大学工程学院,上海 201306;2 上海交通大学电子信息与电气工程学院,上海 200240)

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

2016-12-08修改日期2017-07-04

一种基于IDV-Hop算法的改进定位机制*

吕春峰1,朱建平1,陶正苏2*

(1.上海海洋大学大学工程学院,上海 201306;2 上海交通大学电子信息与电气工程学院,上海 200240)

无线传感器网络中的节点定位或者事件定位越来越受到重视。基于距离无关的定位机制DV-Hop,提出了一种改进定位算法IDV-Hop(Improved DV-Hop)。首先,对DV-Hop进行分析,提出了DV-Hop的局限性;根据这些局限性,结合密集节点的应用实际,提出了相应的改进措施;其次,基于改进的措施,提出了融合了HTC传送机制及权重最小二乘法的IDV-Hop协议;而且,为了提高系统的定位性能,提出了两个重要的参数:校正系数kc和权重因子wNx,i;最后,基于跳距、节点密度、锚节点分布比例、传输半径等参数,对IDV-Hop协议的性能进行仿真分析;并将基于IDV-Hop算法的定位机制性能与其他的典型的DV-Hop机制比较,得出了对于大规模定位网络,基于IDV-Hop算法的机制优于其他机制的结论。

基于距离无关定位;IDV-Hop定位;权重最小二乘法;无线传感器网络

随着传感器技术、MEMS技术、嵌入式技术、现代网络及通信技术的飞速发展,无线传感器网络(Wireless Sensor Networks,WSNs)得到了更为广泛的应用。没有具体的地理位置的监测数据或者事件,对于观测者或者观测中心来说,都是没有任何意义的,定位技术也是无线传感器网络的重要技术,研究高效、节能、精准的定位机制是延长网络寿命、提高定位精准度、保证定位实时性的保障。

无线传感器网络定位算法根据是否测量距离可以分成两类:基于距离(Range-based)的算法和距离无关(Range-free)的定位算法[1-2]。基于距离的定位主要是直接测量未知节点的确切距离或者角度,典型的Range-based定位方法主要包括:基于到达时间TOA(Time of Arrival)[3]、基于到达时间差TDOA(Time difference of Arrival)[4]、基于到达角度AOA(Angle of Arrival)[5]、基于接收信号强度指示RSSI(Received Signal Strength Indicator)[6]等。基于距离的算法定位精度高,但它对硬件资源要求非常高,其各个节点之间要保持严格的时钟同步,成本要求高,并不太适合无线传感器网络定位。基于距离无关的定位无需额外的硬件设备,其算法主要包括:DV-Hop算法[7-9]、质心算法(Centroid)、API(Approximate Pointin triangulation Test)、CPE(Convex Position Estimation)定位算法等。相比之下,在大规模无线传感器网络中,由于其低功耗、通信开销小、无需硬件设施支撑以及成本低等优势,距离无关的定位算法具有更大的实用性。

本文将对基于距离无关的定位算法DV-Hop算法进行全面的分析,并从3各方面对DV-Hop机制进行了改进。首先,提出DV-Hop定位的局限性,针对这些局限性提出了相应的改进措施,提出了IDV-Hop算法的定位机制(简称IDV-Hop机制),并引入距离修正系数kc和权重因子wNx,i;其次,对IDV-Hop机制进行实验验证;最后,将IDV-Hop机制和其他基于DV-Hop算法的定位机制进行性能比较。

图1 DV-Hop定位算法

1 IDV-Hop算法

1.1 DV-Hop算法

传统的DV-Hop算法[10]分3步(如图1)。

第1步 计算每个锚节点与未知节点的最小跳距。锚节点Ai广播一个包含其位置信息和初始值为0的跳数域hopi的信息包。每个收到该包的邻居节点(不论锚节点还是未知节点),都会更新这个域,如果原本存储的跳数比收到的包里的跳数大,存储该包里的跳数,否则忽略该包。在广播的过程中,未知节点获取了与每个锚节点的最小跳距。

第2步 计算未知节点与每个锚节点之间的确切距离。每个锚节点都获取了其他的锚节点与自己的最小跳距,可以计算每个锚节点的平均跳每距dphi,采用式(1):

(1)

知道了每个锚节点的平均每跳距,锚节点广播该平均每跳距,未知节点计算其与每个锚节点的距离。未知节点存储与其最近的锚节点的平均每跳距dphnear,乘以与每个锚节点之间的最小跳距,就是未知节点与每个锚节点之间的确切距离di=dphnear×hopi。

如图1中,未知节点Nx距离4个锚节点的距离计算如下:(1)锚节点A1距离A2=40 m、2跳;距离A3=100 m、6跳;距离A4=40 m、3跳;(2)锚节点A1平均每跳距dph1为(40+100+40)/(2+6+3)=16.36 m。同理,其他的锚节点平均每跳距dph2,dph3,dph4分别为17.5 m、16.88 m、17.73 m。Nx保存A2的dph2并计算与其他锚节点的距离:17.5×3=52.5 m,17.5×2=35 m,17.5×3=52.5 m,17.5×2=35 m。

第3步 采用三边测量法或最大似然估计计算未知节点的位置,具体计算公式见文献[10-13]。

1.2IDV-Hop算法

从上面的叙述可以看出,DV-Hop算法存在若干问题:①步1中,节点只要收到一次广播包,基本上hopi值就需要增加1,对于节点密度较大,传输距离较小的网络,hopi值的估算会大大增加;②节点之间的跳距受到网络连通度的影响,例如A1和A4之间只有40 m,但是跳距有3跳,如果网络是全连通,它们之间只有1～2跳,这样就增加了dphi误差;③未知节点只需要存储离它最近的锚节点的dphi,计算与所有锚节点的距离都采用这个dphi值,没有考虑到其他节点的dphi独立性,这显然有较大误差;④如果未知节点与2个或多个锚节点的跳距相同且都最短,未知节点不知道需要存储哪一个锚节点的dphi,存储不同的dphi值,计算的距离不同,会造成较大误差。

针对DV-Hop机制的这些缺点,很多文献都进行了改进。文献[7]将传统的DV-Hop定位算法用流程图直观展示出来,并提出了改进策略:①进入限跳机制,即设置一个跳数阈值;②引入RSSI测距技术,在节点接收到其他节点位置信息之后,在进行节点间跳距估算之前,先对节点间的跳数值作一个判断,如果跳数为1,直接采用RSSI测距技术;③信标节点不仅仅要还要估算出实际距离与估算距离间的误差,再用该误差作为修正值修正信标节点的平均每跳距,将修正后的平均每跳距作为校正值向外广播。文献[8]也对DV-Hop算法进行了改进:①平均跳距的估计:将离未知节点最近锚节点的每跳距计算出来的跳距d1和该最近锚节点与其他锚节点间的距离与跳数之商d2的平均数,考虑了其他的锚节点对该未知节点的影响;②位置修正:通过对原来估计距离进行修正,获取更准确的位置信息。文献[9]从两个方面对DV-Hop机制进行改进:①引入平均每跳距离均方加权误差的思想对信标节点平均每跳距进行优化;②采用改进的粒子群算法优化位置信息。

文献[7-9]中对DV-Hop的改进主要从跳数、每跳距等方面进行改进。本文不仅仅从跳数限制、每跳距离、未知节点与锚节点的距离等方面进行改进,而且从传输层获得支撑。本文对DV-Hop机制改进的措施:

①采用基于CSMA/CA传输机制的HTC机制[11],所有的传输、定位等都只限于2跳,这样在节点密度较高的情况下,减少传输冲突,降低hopi值估算的误差;②未知节点与每个锚节点的距离采用各自dphi分别乘以跳距,避免了所有的距离都是用一个dphnear值和相同跳距的锚节点dphi选择问题,并引入校正因子kc;③计算未知节点的坐标采用权重最小二乘法,定义了权重因子wNx,i,该因子全面考虑未知节点与锚节点的跳距、锚节点之间的跳距、传输距离等,更加准确可靠。

IDV-Hop算法如下:

步骤1 请求定位阶段。时间分成若干的时隙,定位时间由多个时隙组成。hopi初始化为0。在系统初始化结束,每个节点建立自己的一跳邻居列表,并在每个定位时隙初始阶段节点更新该邻居列表(HTC算法[11])。建立了这个邻居列表,未知节点Nx会确定他的一跳距离内的一跳锚节点邻居A1i,然后,Nx发送定位请求包给A1i。如果A1i数量等于或者大于3,节点直接执行DV-Hop机制进行定位;如果A1i数量小于3,那么这个请求定位的包还需要通过中继传送到他的二跳锚节点邻居A2i,并且二跳邻居节点会加到这个请求定位列表中,如果A1i和A2i的数量和等于或者大于3,可以进行DV-Hop定位,否则,定位失败。

步骤2 跳数信息交换阶段。定位请求阶段结束后,锚节点A1i广播一个HIE包(跳数信息交换,Hop Information Exchange)。该包包含A1i的位置信息、A1i的ID信息和hopi信息。计算hopi有3种情况:第1种,Nx的一跳与A1i的一跳的重叠邻居(锚节点)数量等于或者大于3个,hopi=1,且式(1)分母部分∑hopij(i≠j)值为所有A1i数量减1;第2种,如果这个重叠部分锚节点数量小于3,但是在Nx的1跳之内、A1i的1跳之外2跳之内锚节点数加上重叠部分锚节点数量等于或大于3,在那么式(1)的分母可以设置成(NA1i+2NA2i-1);第3种,Nx的1跳之内的锚节点数量小于3,那么需要扩充到他的2跳,这时∑hopij(i≠j)的计算跟第2种情况相同。

(2)

步骤3 距离计算阶段。采用式(1)计算每个锚节点的平均跳距。那么未知节点收到锚节点发送来的平均跳距,计算其到每个锚节点的距离。与DV-Hop算法只保存最近锚节点的dphnear不同,IDV-Hop算法是每个锚节点的每跳距乘以与未知节点的跳数,才是相应的距离。

(3)

步骤4 未知节点坐标计算。在本阶段的计算中,引入了2个参数:校正因子kc和权重因子wNx,i。kc采用的是已知锚节点之间的误差推广到锚节点与未知节点之间。

(4)

(5)

(6)

(7)

将式(7)两端平方并且简化,有式(8):

(8)

假设:

对于准备要参加的会议，会前若有征文，要精心撰写论文，不仅为争取大会发言创造条件，也为申请获得经费资助增加法码。另外，对于在大会上做报告的专家的学术情况要有所了解，以便在会上更好地与专家进行交流互动。

那么,有式(9):

QZ=H

(9)

因为IDV-Hop里的距离是采用每个锚节点与未知节点之间的距离,那么为了准确计算未知节点的坐标,采用权重最小二乘法WLS(WeightedLeastSquare)计算,如式(10):

Z=(Q′W′WQ)-1Q′W′WH

(10)

式中:W是权重矩阵,代表锚节点的跳距、锚节点与未知节点间的跳距、传送距离、锚节点的个数等因素对计算距离的影响。在ADV-Hop算法中[12],权重因子只考虑了锚节点与未知节点之间的跳距。

(11)

在计算权重因子时,锚节点的个数可以采用式(2)计算。

(12)

2 实验验证

2.1 性能验证

我们通过NS-2仿真软件来验证IDV-Hop机制的性能。搭建仿真平台:所有节点包含锚节点都分布在同一个边长1 km的正方形区域内;假设所有在传输距离内的传输,节点都能侦听到其他节点的传送;没有信号衰减。设定CSMA/CA机制参数为:重传次数为2,最大退避次数为4,数据包长为5个时隙单位。从前面分析可以看出,IDV-Hop的定位误差主要取决于跳距、节点密度、锚节点分布比例、传输半径等,我们从这几个参数来验证IDV-Hop的性能。

从图2可以看出,节点的密度越大,其定位误差越小;锚节点的比例越高,定位误差越小。从式(1)不难看出,dphi计算的准确度与∑hopij有较大关系,而IDV-Hop中的∑hopij计算涉及的跳数较少,而且不存在连通度的影响,所以较为准确;而且,锚节点数量增加,在Nx一跳内就可以直接执行IDV-Hop算法,这大大减小了误差。

图2 定位误差(节点密度影响)

图3 定位误差(传输距离影响)

定位误差也跟传输距离有较大关系。IDV-Hop机制的节点(包含锚节点)都是只考虑了2跳的传输,那么传输距离决定了锚节点的数量,这样也决定了dphi计算的准确性。而且,权重因子wN,i也考虑了传输距离。从图3看出,节点的传输距离并不是越大越好,而是有个权衡问题。

IDV-Hop定位机制针对的是实时定位,那么,实时性也是考虑的重点之一。从图4和图5看出,随着节点数量、锚节点比例的增加,实时性提高,原因跟前面定位误差的分析相似。

图4 定位时延(节点密度影响)

图5 定位时延(传输距离影响)

图6 定位误差比较

2.2 性能比较

在众多基于DV-Hop机制的定位算法中,ADV-Hop机制[12]、HDV-Hop机制[13]、Selective-3-anchor机制[14],是应用较广、算法相对简单的定位机制,本文将IDV-Hop机制与这几个机制进行比较,发现,IDV-Hop机制在实时性上表现较为优越,而在节点密度较大时定位误差也表现出了较好的优势。

图7 定位时延比较

3 结束语

本文首先对传统的距离无关定位机制DV-Hop进行了分析,指出其误差的主要来源,提出了一种基于DV-Hop的距离无关的定位改进机制IDV-Hop机制。首先,基于对DV-Hop机制的限制分析,提出了改进的措施;接着,基于改进措施,提出IDV-Hop机制;最后,基于跳距、节点密度、锚节点分布比例、传输半径等参数,进行仿真分析定位误差、定位实时性等性能;并将IDV-Hop机制与相关DV-Hop机制进行了性能比较。下一步的工作是在节点移动(包括未知节点和锚节点)的情况下,DV-Hop机制或者其他的相应机制的性能提高。

[1] Cheon J,Hwang H,Kim D S,et al. IEEE 802.15.4 ZigBee-Based Time-of-Arrival Estimation for Wireless Sensor Networks[J]. Sensors,2016,203(16):203-213.

[2] Boukerche A,Oliveira H A B,Nakamura E F,et al. Localization Systems for Wireless Sensor Networks[J]. IEEE Wireless Communications,2007,14(6):6-12.

[3] Spano D,Ricciato F. Opportunistic Time-of-Arrival Localization In Fully Asynchronous Wireless Networks[J]. Pervasive and Mobile Computing,2016,in press:1-15.

[4] 张会新,陈德沅,彭晴晴,等. 一种改进的TDOA无线传感器网络节点定位算法[J]. 传感技术学报,2015,28(3):412-415.

[5] 蒋鹏,覃添,陈岁生. 基于AOA降维和同心圆定位的三维传感器网络节点自定位方法[J]. 传感技术学报,2012,25(7):999-1006.

[6] 陈淑敏,乔晓田,毛佳,等. 基于接收信号强度(RSSI)的室内二次定位方法[J]. 传感技术学报,2015,28(4):572-5777.

[7] 夏少波,朱晓丽,邹建梅,等. 基于跳数修正的DV-Hop改进算法[J]. 传感技术学报,2015,28(5):757-762.

[8] 刘少飞,赵清华,王华奎. 基于平均跳距估计和位置修正的DV-Hop定位算法[J]. 传感技术学报,2009,22(8):1154-1157.

[9] 范时平,罗丹,刘艳林. 基于跳距与改进粒子群算法的DV-Hop定位算法[J]. 传感技术学报,2016,29(9):1410-1415.

[10] Nicuescu D,Nath B. DV Based Positioning in Ad Hoc Networks[J]. Telecommunication Systems,2003,22:267-280.

[11] Zhu J P,Tao Z S,Lü C F. Performance Analyses and Improvements for IEEE 802.15.4 CSMACA Scheme in Wireless Multi-Hop Sensor Networks Based on HTC Algorithm[J]. International Journal of Distributed Sensor Networks,2013(10):1-22.

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

[13] Safa H. A Noval Localization Algorithm for Large Scale Wireless Sensor Networks[J]. Computer Communications,2014,45:32-46.

[14] Gui L Q,Val T,Wei A,et al. Improvement of Range-Free Localization Technology by a Novel DV-Hop Protocol in Wireless Sensor Networks[J]. Ad Hoc Networks,2015,24:55-73.

AnImprovedLocalizationSchemeBasedonIDV-HopforLarge-ScaleWirelessSensorNetworks*

LÜChunfeng1,ZHUJianping1,TAOZhengsu2*

(1.SOU College of Engineering Science and Technology Shanghai Ocean University,Shanghai 201306,China; 2.Department of Electronic Information and Electrical Engineering Shanghai Jiaotong University,Shanghai 200240,China)

It is extremely urgent to establish and maintain low cost and high efficient localization schemes for real-time large-scale surveillance systems. An improved DV-Hop based localization scheme IDV-Hop embedded in WLS(weighted least square)method,accompanying with HTC scheme,is proposed for the purpose of surrounding surveillance,object localization for early warning,rescue operations and restructuring plan et al. Two critical parameters,correction coefficient kcand weighted coefficient wNx,i,are introduced into IDV-Hop scheme to improve location performance. And then,NS-2 simulations demonstrate that analysis results match well with simulation results. Besides,behaviors of IDV-Hop is improved largely relative to other DV-Hop based schemesfor large-scale sensor networks.

range-free localization;IDV-Hop scheme;weighted least square;wireless sensor networks

TP393

A

1004-1699(2017)10-1542-06

10.3969/j.issn.1004-1699.2017.10.015

吕春峰(1978-),男,2000年于昆明理工大学获得学士学位,2006年于昆明理工大学获得硕士学位,2014年于上海交通大学获得博士学位,现为上海海洋大学讲师,主要研究方向无线传感器技术、现代检测技术,cflv@shou.edu.cn;

朱建平(1978-),女,2000年于昆明理工大学获得学士学位,2005年于昆明理工大学获得硕士学位,2012年于上海交通大学获得博士学位,现为上海海洋大学副教授,主要研究方向无线传感器网络技术、在线检测技术,jp-zhu@shou.edu.cn;

陶正苏(1961-),男,2005年于香港科技大学获得博士学位,现为上海交通大学教授,主要研究方向无线传感器技术、在线测量理论及技术、光电检测新技术和仪器,zstao@sjtu.edu.cn。