一种适用于矿下人员定位的改进DV-Hop算法

张 琪，周胜梅，黄廷磊

（桂林电子科技大学，广西 桂林541004）

随着网络技术的飞速发展，通信技术及无线定位技术也迅速发展起来。伴随信息时代的到来，无线定位技术被广泛应用于人员定位、救援等领域。我国矿难频繁发生，这为国家和人民带来了巨大的损失，所以矿下救援成为国家和煤矿企业非常重视的一个问题。矿下救援主要是对矿下人员的救援，其过程主要是确定矿下人员的准确位置。无线定位技术的发展为矿下救援带来了方便，它能大大加快救援速度。现有的定位技术在实际应用中还有待研究，为了进一步改善其技术，定位算法的选择至关重要。现有的定位算法有基于距离的算法（RSSI、TOA/TDOA和 AOA）和非基于距离的算法（质心、DV-Hop、APIT、Amorphous、凸规划）。

DV-Hop节点定位算法由于对信标节点比例要求较少，定位精度较高，从而可大大降低网络的布置成本。以往对DV-Hop算法的改进有：结合ZigBee技术来组建无线通信网络；与加权质心相结合；与RSSI算法结合等。文本在分析DV-Hop算法的误差成因后，在保留其算法简单、不依赖于测距误差优点的基础上对其进行了改进。本文根据矿上地理位置进行划分范围，以缩小查找未知节点的单位来提高定位精度。

1 DV-Hop定位算法

1.1 DV-Hop算法的基本思想

DV-Hop算法由Niculescu等人提出，其基本思想是将未知节点和锚节点之间的距离用两者之间的跳数和最近锚节点的平均跳距的乘积表示,当未知节点获得与3个或更多锚节点的距离时进行三边测量定位。其具体过程分为以下三步：

(1)通过节点之间的信息交换，使网络中的每个未知节点获取到信标节点的最小跳数。

(2)在已知信标节点的位置和它们到未知节点的最小跳数后，利用式（1）计算出网络中平均每跳的距离，然后计算未知节点到每个信标节点的跳段距离。

其中，(xi，yi)、(xj，yj)为信标节点 i、j的坐标，hj为信标节点 i与 j(i≠j)之间的跳段数。

(3)未知节点在获得3个或3个以上到信标节点的跳段距离时，利用三边测量公式法(如式(2)所示)或极大似然估计值法计算出未知节点的坐标。

1.2 DV-Hop算法的举例基本思想

如图 1所示，如果 A、B、C为信标节点,第(1)步泛洪后可得到跳数，根据它们的坐标和跳数计算出相互间的距离，进一步计算出平均每跳的距离：A为(20+40)/(3+5)=7.5；B 为(20+30)/(3+3)=8.33；C 为(30+40)/(3+5)=8.75。它们向其邻居节点发送该平均距离，最后未知节点P得到的平均距离是最小跳数对应的信标节点B的平均每跳距离，即8.33，则 P到各个节点的距离为：P到A 为 8.33×2=16.66；P到 B 为 8.33×1=8.33；P到 C 为8.33×3=24.99，然后P根据这些距离和信标节点的坐标通过三边测量法来计算自身坐标[1]。

1.3 现有改进的DV-Hop算法

[2]中，王新生等人提出了使用多个锚节点估算的平均跳距并且采用加权平均跳距代替传统算法中的平均跳距的改进算法。参考文献[3]中，沈明玉等提出了一种基于平均跳距和估计距离的改进的DV-Hop算法。该算法考虑了未知节点到参考节点的路径与参考节点间的路径可能存在重合或部分重合这一特性,对平均跳距进行修改,并利用误差对距离进行修正。参考文献[4]～[5]中，周小波、吕振等提出了基于RSSI的改进型DV-Hop算法。

2 改进DV-Hop算法

对提高定位精度的一个有效方法就是缩小查找范围，从而减小定位误差。以往的算法应用于整个区域，而本文是将所有的节点进行分类，将查找的区域分成多块，再在未知节点所在的那块区域应用DV-Hop算法来确定未知节点的位置。具体步骤如下：

(1)将矿下整个区域看成是一个长方形，那么未知节点就在这个长方形范围内。把信标节点均匀分布在这个长方形区域内，使其整个区域都能被信号覆盖(此区域内的每个节点至少能接收到1个信标节点广播的信号)。

(2)导致DV-Hop算法定位精度不高的一个主要原因就是对平均跳距的计算存在很大的误差，本文利用RSSI测距技术来计算平均跳距。

未知节点收集邻节点信息，选出RSSI最小值并确定此值所属的信标节点。如果这个信标节点在边界上，则另外选出与这个信标节点最相邻的3个信标节点构成一个新的区域；如果这个信标节点在其内部，则选出与这个信标节点最相邻的4个信标节点构成一个新的四边形区域。

(3)以9个信标节点为例，位置分别在长方形的顶点、中心和四边的中点处,如图2所示。如果测出RSSI最小值信标节点是 1，则选择 1、2、8、9 或 1、7、8、9 四个信标节点构成四边形区域(一般矿下是非常窄的通道，选 1、7、8、9 比较合理)；如果是 2，则选取 1、3、9 三个信标节点构成三角形区域；如果是 9，则选取 2、4、6、8这样的信标节点构成四边形区域。

(4)对已知坐标的节点进行归类。归类方法：判定已知节点是否在新构成的多边形区域内，若在，则保留这个节点作为新的信标节点；否则放弃。如图2所示，可以把已知节点归类到A、B、C、D四个区域中。

(5)在未知节点所在的区域中，把已知信息的未知节点当做信标节点，采用基本DV-Hop算法来确定未知节点的位置。

3 实验及仿真结果

为了验证本文算法的可行性，使用Matlab7.0作为仿真工具进行仿真，并对仿真结果进行分析。仿真环境是在100 m×100 m的正方形范围内[6]，随机产生 191个未知传感器网络节点和9个确定的信标节点，节点的通信距离为15 m。仿真结果数据取自20次仿真的平均值。初始节点分布图如图3所示。

缩小范围后，节点分布图如图4所示。

节点分类后，保留4个固定的信标节点，其余54个未知节点随机分布。其中，也可将在其范围内的已知节点当做新的信标节点，这样可大大提高对未知节点的定位精度。

当把随机给出的未知节点分类后，得出54个未知节点，在其范围内随机定义5个已知的邻节点和4个固定的信标节点作为新的信标节点。图5所示为在缩小的范围内当有9个信标节点、54个未知节点时，每个未知节点的误差。

图6是在通信距离为50 m时的平均定位误差图，从图中可以看出随着信标节点的增加，未知节点的定位误差会相对减少。与原始的DV-Hop算法相比，改进后的算法定位误差减少了近20%。改进后将4个固定节点当做是信标节点，然后随着随机增加信标节点来确定定位误差。以信标节点占全部节点的比例作为图中的横坐标，以未知节点的平均误差作为纵坐标。

介于矿下的特殊环境，本文介绍了一种基于DVHop的改进后的节点定位算法，在保留传统DV-Hop算法计算简单、通信开销小的优点的基础上，用缩小定位范围的方法来提高定位精度。本文先对未知节点进行模糊定位，确定未知节点在哪块区域内，再把已知坐标的节点当成信标节点进行分类，最后在缩小定位范围内使用DV-Hop算法对未知节点进行定位。实验结果证明，此方法大大提高了定位精度，很适合于煤矿快速查找人员所在的位置。

参考文献

[1]倪海燕，应祥岳，简家文，等.无线传感器网络的自身定位算法研究[J].宁波大学学报，2009，22(1)：7-11.

[2]王新生，赵衍静，李海涛.基于 DV-Hop定位算法的改进研究[J].计算机科学，2011，38(2)：76-78.

[3]沈明玉，张寅.基于改进的平均跳距和估计距离的DVHop 定位算法[J].计算机应用研究，2011，28(2)：648-650.

[4]周小波，乔钢柱，曾建潮.无线传感器网络中基于RSSI的加权DV-HOP定位方法[J].计算机工程与应用，2011，18(4)：93-96.

[5]吕振，李亚杰，孙延飞，等.基于 DV-Hop的修正和改进定位算法[J].传感器与微系统，2008，29(8)：31-33.

[6]杨小莹，张万礼，房爱东.一种改进的 DV-Hop定位算法[J].宿州学院学报，2011，18(4)：23-25.