无线网络的移动节点定位方法研究

孙苑莹

(长春理工大学 电子信息工程学院， 吉林 长春　130022)



无线网络的移动节点定位方法研究

孙苑莹

(长春理工大学 电子信息工程学院， 吉林 长春130022)

摘要：到达时间差算法(TDOA)是通过测量移动节点接收两个已知节点发射信号的时间差值估算距离，但移动节点需在通信范围内；DV-hop根据节点之间跳数测距,但估算误差较大。将两种方法相结合，在不增加网络硬件的条件下，提高了定位精度。

关键词：无线传感器网络； 移动节点； 定位

0引言

无线传感器节点一般是由传感、数据处理、电池等模块组成的，并通过自组织的方式工作，它们将信息通过采集、提取、传输到电脑，操作者可以通过电脑获定位信息，随机分布的传感器节点构成了无线传感器网络系统。在无线传感器网络中，已知位置坐标的节点叫做锚节点，不确定位置坐标的节点叫未知节点[1]。

在无线传感器网络中，获取未知固定节点位置坐标信息通过无线传感器网络本身是可以完成的，但若是节点的位置坐标是移动不定的，若通过给移动节点装上 GPS而定位其坐标，经济上就会出现困难，所以就需要对移动节点的定位方法进行进一步深入研究。

无线传感器网络定位方法依据是否需要测距主要分两种:一种是测距定位,首先测量已知节点到未知节点的距离，再根据测量的距离进行定位；另一种是非测距的定位计算。文中采用的是测距定位计算其位置坐标。

1基于测距算法

1.1　RSSI测距算法

已知移动节点的发射功率，当已知节点接收到移动节点发射出来的功率时，接收到的功率在传播时一定会有损耗，该算法利用消耗功率值来计算已知节点到未知节点的距离。

优点：不需要额外的成本，比较容易实现测距算法。

缺点：如果需要精确的距离信息时，就得需要较多的已知节点，并且在传播过程中，若不是在直线传播等因素的情况下，会造成结果的不准确[2]。

1.2　AOA测距算法

节点上配置天线，通过天线已知节点获取与未知节点的角度，从而计算出已知节点到未知节点的距离。

优点：需要的已知节点数目少并且定位的精度比较高。

缺点：配置上天线后，对于节点电量损耗比较大，与普通节点相比成本也提高了。

1.3　到达时间差法

到达时间差法的基本内容：测量不同的已知节点接到同一移动节点信号的时间差，通过时间差来建立双曲线方程，从而计算已知节点到未知节点的距离。当进行空间定位的时候，已知节点的数目要大于3个。

优点：算法简单而且易行性强，精度比RSSI测距算法还要高且应用广泛。

缺点：在计算信号时间差的时候，已知节点接收移动节点的信号时，容易受到其它信号的影响，导致有一定的误差。

1.4　DV-hop 算法

DV-hop 算法分为3步：

1)计算出已知节点间的平均跳数和每跳的平均距离；

2)测量出已知节点到移动节点的跳数;

3)用跳数乘以每跳平均距离就是已知节点到未知节点的距离。

优点：测量已知节点到移动节点间的距离不受外界因素的影响。

缺点：测量精度低，计算量多。

2定位算法

2.1　质心算法

已知节点向周围未知节点发射信号，信号的信息是已知节点的位置，当未知节点接收到的信号超过一个之前设置好的数量之后，那么未知节点就位于这些已知节点组成图形的质心上。

优点：算法比较简单，容易实现。

缺点：这是一种估计的算法，故精度不是很高，它的精度和已知节点的密度成正比。

2.2　凸规划定位(Convex Position Estimation)算法

将已知节点到未知节点的通信视为一种几何约束，把整个无线传感器网络看作一个凸集，将无线传感器网络移动节点的定位问题转化为凸集优化问题。

优点：算法简单，容易执行。

缺点：节点的估算会因为已知节点必须分布位置而做偏移[3]。

2.3　三边测量法

已知3个不同的已知节点到同一移动节点的距离，那么移动节点一定在以已知节点为圆心到未知节点距离为半径的3个圆的交点上。

优点：方法原理简单而且使用起来也很容易。

缺点：有可能由于误差原因，移动节点不在3个圆的交点上，这种情况就使得该算法无法估计出移动节点的位置。

3算法的建立

定位算法的好坏可以由多方面决定，例如是否节能、精度高低、定位范围广度等，文中的主要思想就是不增加组件的前提下提高算法的精度。由上文分析可知，到达时间差法定位算法虽然定位误差小，但是定位时有一定的局限性，一旦已知节点无法接到移动节点信号时，就无法进行定位；而DV-hop 算法虽然定位误差大，但对移动节点的位置没有限制要求。故文中结合两种算法的优缺点[4]，用到达时间差法定位算法弥补DV-hop 算法定位精度低的缺点，用DV-hop 算法弥补到达时间差法的定位位置限制的缺点，得到移动节点的距离后，用三边测量法对移动节点进行位置定位。

算法的流程如图1所示。

图1　流程图

其中N表示移动节点接收到已知节点信息的个数。

算法分为3个步骤：

1)到达时间差法测得已知节点到移动节点的距离。

首先，已知节点发送信号，当移动节点处在多于两个已知节点的通信射程范围时，就直接用到达时间差法算得距离，具体算法如下：移动节点到任意两个已知节点的距离差为固定值d时，移动节点一定位于以两个已知节点为焦点的双曲线上，用两双曲线组成的方程解出的交点坐标即为移动节点的位置坐标[5]，此算法原理图如图2所示。

图2　TDOA定位算法几何原理图

用到达时间差法测距之后，用三边定位法计算移动节点的位置坐标。如果当移动节点所处的通信范围内，少于3个已知节点对其进行测距，则用步骤2)DV-hop 来测距。

2)DV-hop 算法测得已知节点到移动节点的距离。

经过步骤1)，可以完成已知节点通信范围内的移动节点测距，如测得三边定位所需边中的一些长度，其余边的长度需要用 DV-hop算法来计算。

DV-hop算法如下[6]:

第1部分：计算得出移动节点与已知节点之间的跳数最小值。相邻已知节点接收到各个已知节点的跳数信息，比较接收送来的跳数信息后，留下小的数据，舍弃大的跳数数据，并将此跳数数据发给其相邻已知节点，以此方法计算已知节点最小跳数值。

第2部分：获取移动节点与已知节点间实际距离。根据第1部分得出的最小跳数，可得出每跳实际距离[7]:

(1)

式中：(xj,yj)，(xi,yi)----已知节点j和i的位置坐标；

hj----已知j最小跳数。

此时，网络中的移动节点分两类:

第1类：移动节点在一些已知节点的通信范围内，即移动节点可以通过到达时间差法测距，这时可以忽略已知节点向移动节点发送有关跳数数据，但移动节点如果接收到其它已知节点发送来的跳数信息，则这些移动节点的测距问题要靠DV-hop算法来计算；

第2类：移动节点不在已知节点的通信范围内，就可以直接用DV-hop定位算法计算。

3)三边定位方法估算移动节点位置坐标[8]。

通过上面两步，移动节点测得了到达已知节点的3个以上的距离。分别通过到达时间差法和DV-hop 算法测得，这时即可利用三边定位算法计算出移动节点的位置坐标。

三边法的几何原理如图3所示。

图3　三边测量法

如果未知节点M到已知节点A，B，C的距离分别为d1，d2，d3，那么M一定位于以A，B，C为圆心，d1，d2，d3为半径的3个圆的交点上。由此可计算出移动节点M的位置坐标。

4结语

论述了无线传感器网络中对移动节点的定位方法，提出了基于无线传感器网络的移动节点定位研究的新方法。此方法理论上简单明了，结合了到达时间差法和DV-hop 算法的优缺点计算距离，并用三边定位方法估算位置，不仅节约了无线传感器网络定位的时间，而且提高了无线传感器网络定位的精度，简单易行。

参考文献：

[1]Langendoen K, Reijers N. Distributed localization in wireless sensor networks: A quantitative comparison The Int'1 Journal of Computer and Telecommunications Networking[J]. Electronic Industry Press,2003，43(4)：499-518.

[2]王雪,钱志鸿,胡正超,等.基于二叉树的RFID防碰撞算法的研究[J].通信学报,2010,31(6):49-57.

[3]Yi Shang, Wheeler Ruml, Ying Zhang. Localization from mere connectivity[C]//MobiHoc ’03, Annapolis. Maryland, USA:[s.n.],2003：201-212.

[4]Shih E. Physical layer driven algorithm and protocol design for energy-efficient Wireless sensor networks[C]//Proceedings of the Senventh Annual International Conference on Mobile Computing and Networks (MobiCOM 01). Rome Italy:[s.n.],2001：272-286.

[5]钱志鸿,王义君.物联网技术与应用研究[J].电子学报,2012,40(5):1023-1029.

[6]余光伟.自主移动机器人路径规划方法研究[D]:[硕士学位论文].长春：长春工业大学电气与电子工程学院,2010:3-4.

[7]崔莉,鞠海玲,苗勇,等.无线传感器网络研究进展[J].计算机研究与发展,2005,42(1)：163-174.

[8]王楠.移动无线传感器网络定位问题的研究[J].辽宁工程技术大学学报，2010(1):14-16.

Mobile node localization in a Wireless Sensor Network

SUN Yuan-ying

(College of Electronics and Information Engineering, Changchun University of Science and Technology, Changchun 130022， China)

Abstract：Time Difference of Arrival (TDOA) algorithm is used to estimate the distance with the time difference of transmitting signals between the two receiving nodes but the nodes should be in the range of communication, while the DV-hop algorithm is applied to predict the distance according to the numbers of hop but with more error. We combine the two to obtain the high position accuracy under the same hardware environment.

Key words：Wireless Sensor Network (WSN); mobile node; positioning.

作者简介：孙苑莹(1990-)，女，汉族，吉林梅河口人，长春理工大学硕士研究生，主要从事无线传感器网络定位问题研究,E-mail:540929616@qq.com.

收稿日期：2014-06-08

中图分类号：TP 732

文献标志码：A

文章编号：1674-1374(2015)01-0057-04

DOI:10.15923/j.cnki.cn22-1382/t.2015.1.12