一种新的三维无线传感器网络节点定位算法

曾传璜，蒋红刚

（江西理工大学信息工程学院，江西赣州 341000）

0 引言

无线传感器网络（wireless sensor networks，WSNs）涉及现代微机电系统（micro-electro-mechanical system，MEMS）、微电子、片上系统（system-on-chip，SoC）、纳米材料、传感器、无线通信、计算机网络、分布式信息处理等技术，在国防军事、工农业控制、城市管理、卫生医疗、环境监测、抢险救灾、反恐防恐、危险区域远程控制等领域有着潜在的应用前景。美国《商业周刊》将WSNs列为21世纪最有影响力的21项技术之一，《MIT技术评论》将无线传感器网络列于10种改变未来世界新兴技术之首［1］。

无线传感器网络的定位是指自组织的网络通过特定方法提供节点位置信息，这种自组织网络定位分为节点自身定位和目标定位。节点自身定位是网络自身属性的确定过程，可以通过人工标定或者各种节点自定位算法完成。目标定位是位置已知的网络节点为参考节点，确定事件或者目标在网络中所处的位置［2］。

根据定位过程中是否实际测量节点间的距离或角度，把传感器网络中的定位分类为基于距离的定位和距离无关的定位。基于距离的定位机制就是通过测量相邻节点间的实际距离或方位来确定未知节点的位置，通常采用测距、定位和修正等步骤实现。根据测量节点间距离或方位时所采用的方法，基于距离的定位分为基于ToA［3］的定位、基于TDoA［4］的定位、基于 AoA［5］的定位、基于 RSSI［6］的定位等。由于要实际测量节点间的距离或角度，基于距离的定位机制通常定位精度相对较高，所以，对节点的硬件也提出了很高的要求。距离无关的定位机制无须实际测量节点间的绝对距离或方位就能够确定未知节点的位置，目前提出的定位机制主要有质心算法、DV-Hop算法［7］、Amorphous算法、APIT算法等［8］。本文在结合三边定位和三角定位的基础上，提出一种新的基于测距的三角几何定位方法。

1 定位算法的提出与定位原理

在节点定位算法中，与距离相关的定位算法有三边测量法，三角测量法，极大似然估计法等。三边测量法需要知道与3个节点相关的距离信息;三角测量法需要知道与未知点相关的3个角度信息。本文提出的方法则是要知道未知节点与某一信标节点相关的一个距离，2个角度的相关信息。

如图1，p点为位置未知节点，o，o1和o2是选取的信标节点，现以oo1为x轴的正半轴，o1oo2为xoy平面建立三维坐标系。p1为p点在o1oo2三点所组成的平面上的投影。

图1 定位算法示意图Fig 1 Schematic diagram of localization algorithm

已知3个信标节点空间坐标，通过距离运算公式

可以得到三点间两两之间的距离:loo1，loo2，lo1o2。

利用余弦定理

可以得到角∠o1oo2的大小。

通过3个信标节点可以测量得到:lop，∠poo1，∠poo2。

根据余弦定理有

式（3）和式（4）相比得

根据三角函数运算有

由式（3）平方与式（6）及三角平方公式得

由式（5）与式（7）及平方公式得

根据图1所示和三角运算可知p点坐标（px，py，pz）

根据式（3）和式（9）得

根据式（3），式（5）和式（10）得

根据式（8）和式（11）得

通过以上的运算即可得到p点坐标（px，py，pz）。当然这是以o点为坐标原点，以oo1为x的正半轴，o1oo2为xoy平面建立三维坐标系得到的（px，py，pz）。在实际中这三点坐标并不是这样，但三点确定一个平面，可以将信标节点坐标进行平移变换，使其中一点平移变换到坐标原点。变换以后，将坐标原点的点与另外一点作为x轴，而平移变换后的三点便成为xoy平面，这样便可以使用上述方法计算出未知节点的相对坐标，再进行坐标变换就可以得到原坐标系中未知节点的实际坐标。

方法改进的讨论:

通过以上计算可知在测量得到与o点相关的数据信息，通过三角几何运算得到p点的相对坐标，再进行坐标变换即可得到p点在实际中的坐标。在计算未知节点的过程中不需要o1点和o2点的距离与角度信息，但是在坐标变换中又需要其相关信息。为了获取更多与未知节点相关的信息，提高定位的精确性，可以合理利用这两点与未知节点的相关信息，在此对以上方法进行改进。方法改进中，将o1点和未知节点相关的一边与两角测量出来，将o1作为坐标原点，o1o为x轴和上面的方法一样，对未知节点的相关数据信息进行计算，得到另一组p点的相对坐标。然后再运用坐标变换，可得到第二组p点实际坐标。同理，通过o2点与未知节点相关数据可以的到第三组p点实际坐标。当然o点，o1点，o2点本生是在同一坐标系内的，得到的未知节点的实际坐标应该是一样的。但由于测量误差的存在，这三组数据不一定相同，这时可以再运用质心法求解p点坐标。

改进算法的优点是:

1）测量数据之间是相互独立的，数据量很大时测量误差就会趋近于零。

2）通过3个信标节点就可以获取三组未知节点位置坐标，本方法在信标节点较少的情况下，仍然能够得到较多的关于未知节点坐标的信息（n个信标节点可以产生C3n×3组数据），可以应用于信标节点密度较小时对未知节点的定位。

2 算法性能评估

2．1 衡量标准

本文只针对定位算法本生所产生的节点定位精度进行

在误差计算时将3个信标节点对未知节点的定位误差分别计算出来。同时，利用质心法将3个信标节点的计算坐标进行处理。计算出定位坐标与实际坐标之间的误差，将平均定位误差作为本方法的最终定位误差。

其仿真过程如下:

1）在大小100 m×100 m×100 m的空间坐标中选取3个信标节点，假设分别为o点、o1点、o2点。

2）在上面的基础上再随机产生一个未知节点p点，假设为（x3，y3，z3，）。

3）通过在Matlab中编写程序计算出相应的角度与长度，并将其分为三组:

4）将以上计算得到的长度，角度分别加上随机误差，作为测量数据。

5）根据新算法，用三组带有随机误差的长度与角度计算未知节点的坐标，假设计算结果分别为（x，y，z），（x1，y1，z1），（x2，y2，z2），用质心法将上面三组数据处理得到（xi，yi，zi）。

6）用上面所产生的四组坐标数据与未知节点p（x3，y3，z3，），计算定位误差。

7）重复以上运算1 000次，显示每次定位误差，计算1000次定位的平均定位误差。

2．2 实验仿真

实验仿真中设定角度测量误差为5°，长度测量误差为5%R（R通信半径）。现取3 个信标节点（0，0，0 m）（53，0，0 m）（32，18，0 m）对100 m ×100 m ×100 m 内 1000 个任意未知点进行定位。计算出3个信标节点对1 000个未知节点相应的定位坐标，将3个信标节点定位坐标再利用质心法对其进行相应处理，将处理后的坐标定为最终的未知节点的坐标。仿真中分别计算出3个信标节点的相应定位误差和利用质心法处理上述3个信标节点定位坐标的定位误差，同时计算出这1000个未知节点定位的平均定位误差。用Matlab仿真，定位误差示意图如图2～图5所示。

经过质心算法改进后的平均定位误差为4．98%（第一个信标节点为坐标原点时的平均定位误差为8．62%，第二个信标节点为坐标原点时的平均定位误差为8．41%，第三个信标节点为坐标原点时的平均定位误差为10．11%）。可见该算法改进后的定位误差相比于其他的定位算法的定位误差要小得多。分析，利用Matlab对三角几何算法进行仿真。定位误差pe定义如下

图2 第一个信标节点为坐标原点时的定位误差示意图Fig 2 Localization error diagram while the 1st beacon node is the origin of coordinates

图3 第二个信标节点为坐标原点时的定位误差示意图Fig 3 Localization error diagram while the 2nd beacon node is the origin of coordinates

图4 第三个信标节点为坐标原点时的定位误差示意图Fig 4 Localization error diagram while the 3rd beacon node is the origin of coordinates

图5 运用质心算法改进定位误差示意图Fig 5 Localization error diagram with the improved centroid algorithm

3 结束语

本文提出了一种新的基于测距的三维无线传感器网络节点定位算法，通过测量一边、两角，运用三角几何知识计算出相对坐标，通过坐标转换计算出实际坐标，实现定位。该算法改进后相对其他的定位算法来说，定位精度相对较高。在信标节点相对较少的情况下仍然能够得到较多数据，适合于信标节点密度相对较小的情况，即可以应用到计算精度要求比较高，计算节点密度较小的三维无线传感器网络节点定位中去。

［1］ 徐勇军．无线传感器网络实验教程［M］．北京:北京理工大学出版社，2007．

［2］ 李晓维．无线传感器网络技术［M］．北京:北京理工大学出版社，2007:191．

［3］ Chuang Woo-cheol，Ha Dong-sam．An accurate ultrawideband（UWB）ranging for precision asset location［C］∥Proceedings of the IEEE Conference on Ultra Wideband Systems and Technologies Reston，Piscataway，NJ，USA，2003:389 －393．

［4］ Savvides A，Park H，Srivastava M．The bits and flops of the n-hop multilateration primitive for node localization problems［C］∥The first ACM International Workshop on Wireless Sensor Networks and Application，Atlanta，GA，USA，2002:112 －121．

［5］ Niculescu D，Nath B．Ad Hoc positioning system（APS）using AoA［C］∥Proceedings of the 22nd Annual Joint Conference of the IEEE Computer and Communications Societies（INFOCOM），Piscataway，USA，2003:1734 －1743．

［6］ Niculescu D，Nath B．DV-based positioning in Ad Hoc networks［J］．Journal of Telecommunication Systems，2003，22（1/4）:267－280．

［7］ Bulusu N，Heidemann J，Estrin D，et al．Self-configuring localization system:Design and experimental evaluation［J］．ACM Transaction on Embedded Computing System，2004，3（1）:24 －60．

［8］ 孙利民，李建树，陈 渝，等．无线传感器网络［M］．北京:清华大学出版社，2005:156－157．