电子产品世界

摘要：根据经典的APIT算法特点，将其扩展到三维空间中实现节点的定位。针对APIT算法的不足，提出了一种改进的TDAPIT算法，并从节点定位误差和定位覆盖率两个方面分析算法的性能。在改进的算法中利用了循环的思想，大大减少了不良节点的数量。仿真实验结果证明，TDAPIT算法可以较好地应用于三维空间定位，而且在定位覆盖率上比APIT有了明显提高。

关键词：无线传感器；定位；APIT；TDAPlT

引言

通常，无线传感器网络(Wireless Sensor Networks，WSN)信息采集节点是被随机放置或是从飞机上随机抛撒的。因此如何确定节点的具体位置成为无线传感器网络研究的难点和重点。

WSN的定位主要分对节点自身的定位和对外部目标的跟踪定位。WSN自身定位方法分为基于测距的方法和非基于测距的方法。基于测距的定位通过测量相邻节点之间的绝对距离或方位等来计算未知节点的位置，需要特定的硬件设备，定位精度较高。而非基于测距的定位机制无需测距或角度信息，不用直接测量这些信息，仅根据网络的连通性等信息实现节点的定位，典型的有质心算法、DV-Hop算法、凸规划算法和APIT算法等。

参考文献提出了一种IAPIT的定位方法，主要思路是将3边测量法以及几何上的由已知两点在辅助条件下求解两圆交点的方法融入到APIT算法中，但是算法仍然局限于二维宅间中的定位。参考文献通过对单跳质心算法进行多跳扩展以改善定位比率，并加入场强加权过程和去中心化过程以提高定位精度。参考文献提出将所有收集到的来自于同一信标节点的RSSI值做平均，作为未知节点接收到此固定信标节点的RSSI值，进行定位计算。参考文献结合三角形测试原理(PIT)，主要针对信标节点分布不均匀的情况提出了CBPIT算法。参考文献提出了一种节点自身的定位方法，能够通过相对准确的测试来确定节点所在的区域，但是没有考虑未知节点监听到信标节点数目较少的情况。

本文针对三维空间的节点定位提出了改进的TDAPIT算法。

1 算法描述

1．1 术语定义

①信标节点：已知位置并能协助未知节点定位的节点，也称锚节点。

②邻居节点：在节点的通信范围内，并可与这个节点直接通信的所有节点。

③未知节点：不知道自身的位置，需使用信标节点的位置信息并运用一定的算法得到估计位置的节点，也称待定位节点。

④已知节点：圩始时不知道自身的位置信息，但是经过一段时间的定位后，已经通过信标节点的位置信息并用一定的算法得到了位置信息的节点。

⑤不良节点：定位过程结束后，仍然不能够实现定位的节点。

实际上，WSN的节点定位即未知节点在信标节点的协助下转变成已知节点的过程。在实际定位过程中，由于种种原因，难免会出现不良节点，应当尽力减少不良节点的个数。

1．2 APIT算法

APIT算法的基本思想是未知节点任选3个相邻信标节点，测试是否位于它们所组成的三角形中，使用不同信标节点组合重复测试，直到穷尽所有组合或达到所需定位精度。最后，计算包含目标节点的所有三角形交集的质心位置，并以此作为目标节点位置。

APIT算法理论基础是PIT测试。如果存在一个方向，并且沿着此方向运动的未知节点会同时远离或者是接近三角形的三个顶点，那么此未知节点在三角形的外部，否则在三角形的内部。

在实际测试中，可以用未知节点和它的邻居节点来模拟此运动。若未知节点的邻节点都没有同时远离或靠近3个信标节点，那么此未知节点就在三角形内，否则在三角形外。PIT测试时，一般采用信号强度来判断远离或者是接近信标节点。

PIT测试误差分析如下：

①PIT测试中容易出现InToOut和OutToIn错误。InToOut错误即将三角形内部的点误判为在三角形外面。PIT测试图像如图1所示。当未知节点靠近或者正好在三角形的一条边上时，就容易出现上述的错误。

②如果信标节点和未知节点的邻居节点密度过小，对定位结果的影响很大，抑或使得有些节点不能被定位，定位覆盖率较低。

③在网络的中间部分和未知节点相邻的信标节点可能很多，但是其中任意3个节点所组成的三角形可能都不包括未知节点，因此在算法完成后仍不能定位这类节点。

④在网络的边缘部分，容易造成无法满足APIT的定位条件，当和未知节点相邻的信标节点数目少于3个时，造成未知节点无法定位。

⑤对重叠区域的重心计算中，采用的是网格扫描的算法，效率较低，计算精度不高。

⑥算法中，未知节点不仅要与信标节点交互信息，还要与其他的邻居节点进行协调信息处理，使得网络中节点的计算量增大，通信开销也上升了很多。

1．3 基于APIT的三维定位方法

1．3．1 TDAPIT算法原理

信标节点是WSN空间中已经知道自身坐标位置的固定节点(如通过GPRS定位等)，空间中的任意一个未知节点，能够监听到信标节点的数目为n，那么从n中任意选取4个点组成一个四面体，共有C4n个四面体；然后，测试该未知节点是否在这4个信标节点组成的四面体内，重复这种测试，直到监听到所有信标节点的组合或者是达到了要求的精度；最后，计算包含未知节点的所有四面体的重叠区域，将重叠区域的质心作为未知节点的位置。

1．3．2 TDAPIT测试

若存在一个方向，沿着这个方向未知节点M会同时远离或接近四面体的四个顶点，则M位于四面体外，否则M位于四面体内部。

在随机部署的传感器网络中，有一些节点侦听到的信标节点个数小于4，则这些节点不能进行PIT测试；有些节点尽管接收到的信标节点数目大于或等于4个，也能进行PIT测试，但是却仍然无法判断其位置。在测试中，利用如下方法判断未知节点位置：

①通过未知节点接收到信标节点的RSS值大小来判断节点和信标节点之间的距离。

②通过未知节点的邻居节点来模拟未知节点的移动，即假设未知节点移动到它的邻居节点。

③通过对未知节点所有邻居节点的模拟来近似地遍历未知节点的所有方向。

④为了减少InToOut和OutToIn错误，我们可以通过在节点上设置相应的MAXrss和MINrss阈值来进一步判断。对于初步判定为在三角形外部的节点，如果未知节点接收到的信号强度值大于设置的阈值，则认为判定错误；同样，对于判定为在三角形内部的节点，如果接收到的信号强度小于设定的阈值，则认为发生OutToIn错误。

关键词： 三维定位 算法 网络 传感器 APIT 无线 基于