基于DV-Distance的无线传感器网络定位算法研究

马庆功，刘冉冉

(1.常州大学 信息中心，江苏 常州 213000；2.常州刘国钧高等职业技术学校，江苏 常州 213000)

无线传感器网络是21世纪最重要的信息获取和处理技术之一，能够广泛的应用在智能交通、国防军事和空间探索等许多领域．节点自定位技术是无线传感器网络的主要支撑技术之一，节点自身的准确定位是提供监测信息事件位置信息的前提，而没有位置信息的监测信息是毫无意义的[1]．

1 DV-Distance定位算法

1.1 DV-Distance定位算法介绍

美国路特葛斯大学(Rutgers University)的Dragos Niculescu等人利用GPS定位的原理和距离矢量路由提出了一系列分布式定位算法，因为是在自组织网络下研究得到的，因此将它们合称为自组织定位系统(ad hoc positioning system，APS)[2-4]．这里面包含了以下几种算法：DV-Coordinate、DV-Hop、DV-Radial、DV-Distance、DV-Bearing和DV-Euclidean．为了降低对节点的性能要求，Badri Nath等人提出了DV-Distance定位算法，这个算法比DV-Hop定位算法对节点的要求更低，节点不用存储网络中每个节点的位置信息，这样就降低了节点间的通信量，所以节省了节点的大量工作能量，使节点有了更长的生存周期．缺点是它需要直接测量节点之间的距离，导致这个定位算法对距离的敏感性要求高，误差很大[5-7]．

本文中所研究的DV-Distance算法的定位主要分以下两个步骤进行：(1)确定信标节点与所有未知节点之间的跳段距离.两个节点之间的跳段总数称为跳数，各个跳段的距离之和称为两个节点之间的跳段距离．根据距离矢量交换协议的基本理论，所谓信标节点是指通过GPS能获取自身物理坐标，它只向其通信半径内的所有邻居节点传播其位置信息，即跳数和跳段距离．位置确定过程如下：首先初始化信标节点与未知节点的跳数及跳段距离为0，比较同一个参考节点的跳数后，各接收节点保留其中跳数最小的分组，将跳数加1并累加与各个参考节点之间的跳段距离，转发给其他未知节点．此方法避免了定位过程中无限循环的广播信息，并能够记录下无线传感器网络中所有已知节点到邻居节点的累计跳段距离和最小跳数．(2)确定未知节点的位置.通过上述第(1)步确定的各已知节点到邻居节点的累计跳段距离，并将其作为有效距离利用三边测量法确定出未知节点的坐标位置，如式(1)所示．

(1)

DV-Distance定位算法采用RSSI技术，利用接收信号强度的值以及传统的路径损耗传播模型计算出各个节点间的距离，并进一步确定未知节点和信标节点间的跳段距离，将其作为有效距离，利用距离矢量路由算法传播未知节点与信标节点之间的累计距离．当获取三个以上有效距离后，利用三边测量法进一步求出未知节点的坐标．

(2)

1.2 DV-Distance定位算法的分析

DV-Distance的算法优点[8]：(1)因为采用RSSI测距技术测定每一跳的距离，所以每跳不必距离相等；(2)该算法所需的无线传感器网络简单、可升级，且算法较为健壮；(3)算法对节点的要求比较低，节点不用储存网络中各个节点的位置信息，减少了节点之间因为通信而消耗的能量；(4)通过修正因子可以大大提高定位的精度．

DV-Distance定位算法自身存在着一定的缺陷[9]，它的缺点有：(1)RSSI测距技术受环境影响较为严重，温度不同，有无障碍物、传播模式不同、各节点的实际距离不同都给测量带来较大的精确度差异；(2)DV-Distance定位算法将未知节点与信标节点之间的折线距离作为有效距离，当存在多个跳段或某个跳段距离过大时，该算法所确定出的有效距离就会存在较大的误差；(3)因为在网络中使用了RSSI测距技术，所以节点内需要有测量信号强度的模块，这使得设备造价较为昂贵．

实验显示，DV-Distance定位算法的定位精度为20%(网络平均连通度为9，信标节点比例为10%，测距误差小于10%)，但随着测距误差的增大，DV-Distance算法的定位误差也将急剧增大[10-11]．

2 算法仿真与结果分析

2.1 基本算法与流程

本算法利用MATLAB进行仿真分析，具体流程如下:第一步,设置初始量，布置了一个范围为100×100的区域，其中随机的布置了200个无线传感器节点，这两百个节点中的信标节点数量可以进行更改，同时设定了节点通信半径．第二步，从第一个信标节点开始，找到在该信标节点的通信半径内的所有未知节点，并记录这些与信标节点相距只有一跳的未知节点，然后再通过刚刚得到的与信标节点相距一跳的节点寻找跳数为二的未知节点，依次进行下去完成关于未知节点的跳数矩阵．第三步，通过跳数矩阵，利用RSSI技术的测距模型，计算出未知节点与信标节点的距离．第四步，当未知节点获得与三个或更多信标节点的距离后，使用最小二乘法的方法计算出未知节点的位置．第五步，将计算出的节点位置以及系统初始化的节点位置同时表示在同一张图上，并计算其平均误差以及测距精度．

2.2 仿真结果与分析

2.2.1 不同信标节点密度时的仿真结果及分析

在仿真中，对无线传感器网络的设置是范围为100×100 m，共有200个无线传感器节点，信标节点的密度分别为20%、30%时，通信半径设定为20 m．图1即为仿真出的节点分布图，图中用*来表示信标节点的位置，用o来表示未知节点的位置．

为了更好的研究DV-Distance算法，利用MATLAB进一步描绘出节点之间的邻居节点图，即节点之间的通信连接图．如图2所示，节点之间的通信以连线的模式来表示，通过该图可以较为清楚的了解节点之间的通信传输．

为了较为清楚的看出仿真算法的定位效果，将定位后的节点分布图再次显示出来，如图3所示，并用线连接了未知节点的实际位置与定位测算位置，可以较为定量的看出节点定位的误差是否存在很大的波动．

(a) 信标节点密度20%时的节点分布 (b) 信标节点密度30%时的节点分布

图1节点分布图

(a) 信标节点密度20%时节点间邻居关系图 (b) 信标节点密度30%时节点间邻居关系图

图2节点间邻居关系图

(a) 信标节点密度20%时的定位误差图 (b) 信标节点密度30%时的定位误差图

图3仿真的定位误差图

信标节点密度20%时共有160个未知节点，其中有25个未知节点的位置无法测算，其定位误差为0.34605．信标节点密度30%时共有140个是未知节点，仿真实现定位时共有9个不能被定位的未知节点．本次仿真的定位误差为0.29747．

通过多次仿真比较，增加信标节点的密度，可以减少定位算法的定位误差，同时可以减少无法定位的未知节点的数目．但是增加信标节点的密度，等同于增加信标节点的数量，信标节点含有GPS装置，而且通常信标节点拥有更好的通信能力和更持久的能量供应，这就导致信标节点的费用远高于普通节点．增加信标节点的数量，提高定位精度的同时，带来的是费用的增加，如何平衡这两者，则要视具体情况而定．

2.2.2 GPS存在误差时的仿真结果及分析

通过文献可知，我们之所以能够知道信标节点的位置，是因为信标节点内预先布置了GPS定位装置，但是通常情况下，GPS装置自身也存在一定的定位误差，在上面的仿真中，并没有考虑到GPS自身的定位误差．对此进行改进，在前面的仿真基础中加入GPS自身的定位误差，设定定位误差为3%，当信标节点密度为20%，所得的节点分布图、邻居关系图及定位误差图分别如图4～7所示．

仿真结果显示，定位时共有4个不能被定位的未知节点，定位误差为0.3584．通过多次仿真实验可知，由于GPS装置自身的定位误差被带入了仿真测算中，导致了仿真的定位的误差增大，可见GPS误差的能够影响到DV-Distance算法的定位精度．

图4节点分布图(GPS存在误差)图5邻居关系图(GPS存在误差)

图6定位误差图(GPS存在误差)图7节点分布图(存在障碍物)

2.2.3 存在障碍物时的仿真结果及分析

在实际的监测情况里，往往有可能存在着障碍物，因为无线传感器网络的通信方式是无线通信，这些障碍物会对节点间的通信造成影响，甚至有可能阻碍到节点间的通信.为了使仿真更接近真实情况，对程序进行了改动，模拟出如图8的具有障碍物的监测区域．在信标节点密度为30%时，所得的节点分布图、邻居关系图及定位误差图分别如图8～11所示．

仿真结果显示，共有9个不能被定位的未知节点，定位误差为0.33062．进一步分析图8，由于存在障碍物，使得处在障碍物上下方的未知节点与信标节点之间的跳数变得较大，跳数变大将影响到距离的计算值，这样会导致定位的误差增大．

对上述信标节点密度为20%，以及节点密度为30%在无GPS误差、GPS定位误差为3%和存在障碍物共四种情况下进行多次实验，将所得出的误差值利用二维图进行绘制，以此来分析算法定位的性能．由图10可以看出，信标节点密度为30%的网络的定位略优于信标节点密度为20%的情况．而综合分析图10以及图11之后，可以看出在障碍物存在的情况下，定位的误差是最大的，而当GPS有误差时，其定位效果就不如GPS无误差的情况．

图8邻居关系图(存在障碍物)图9定位误差图(存在障碍物)

图10误差分析(1)图11误差分析(2)

3 结论

本文介绍了用于无线传感器网络的定位算法，着重研究了基于DV-Distance的定位算法，阐述了其原理，并对DV-Distance定位算法在不同信标节点密度、GPS存在误差及有障碍物情况下分别进行仿真分析．结果表明增加信标节点的密度，可以减少定位算法的定位误差，但会增加成本，而当存在障碍物时定位误差最大．

[1]万润泽，雷建军. 无线传感器网络密钥管理方案比较研究[J]. 吉林师范大学学报(自然科学版),2013,34(3):104～107.

[2]Niculescu D,Nath B. Ad-Hoc positioning systems (APS) [C]. GLOBECOM 2001,San Antonio. New York: IEEE Press,2001,5: 2926～2931.

[3]李洁鸿，谢 睿，陈向东，等.改进的无线传感器网络DV-Distance定位算法 [J].通信技术，2012，45(3)：52～54.

[4]Niculescu D,Nath B. DV based positioning in ad hoc networks[J]. Journal of Telecommunication Systems,2003,22(1):267～280.

[5]于海斌，曾 鹏，梁 斡．智能无线传感器网络系统[M]. 北京: 科学出版社,2006.

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

[7]He T,Huang C,Blum B M,et al. Range-free localization and its impact on large scale sensor networks [J]. ACM Trans. Embedded Computing and System,2005,4(4): 877～906.

[8]Patwari N,Ash J N,Kyperountas S,et al. Locating the nodes: cooperative localization in wireless sensor networks [J]. IEEE Signal Process,2005,22(4): 54～69.

[9]R Want,A Hopper,V Falcao,J Gibbon. The action badge location system ACM Transactions on Information System [J].1992,10 (1): 91～102.

[10]J Robet,D Gregory. The smart floor: A mechanism for natural user identification and tracking[C]. In Proceedings of the 2000 Conference on Human Factors in Computing System(CHI 2000),The Hage,Netherlands,ACM Press,2000,4: 275～276.

[11]A Cerpa and D Estrin. Ascent: Adaptive self-configuring sensor network topologies,Technical Report C'SD-TR 01-009[D].University of California,Los Angeles,Computer Science department,2001.