基于APIT算法的三维定位方法解析

通常，无线传感器网络（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错误。

1．3．3 TDAPIT算法流程

TDAPIT算法流程步骤如下：

①节点部署完成后，网络初始化配置。信标节点向网络广播消息（消息应该包含信标节点的ID、位置坐标等信息），而未知节点监听信标节点的消息。此阶段未知节点应随时更新接收到的信息，以防止冈网络的拓扑变化而造成的误差影响。

②设未知节点M监听到的信标节点数目为n（n=0，1，2，3，4，5，6…）。信标节点的坐标为A1，A2，A3，A4，…，An，未知节点将监听到的信标节点的坐标存入数组，如果n小于5则继续下一步，否则转向步骤④；

③当n=4、3或2时，即未知节点只能监听到4、3或2个信标节点。以未知节点所能监听到的信标节点为圆心，以通信距离为半径分别作球，两球分别相交，分别求出4个球体、3个球体、2个球体重叠区域的质心作为未知节点的坐标。

当n=1或0时，即未知节点只能监听到1或0个信标节点。此时，未知节点等待一段时间t（这里t应设置为略小于定位周期）后，向其所有邻居节点广播消息，请求获知邻居节点的坐标信息。若没有邻居节点返回消息，那么重复执行此步骤；若有邻居节点返回消息但邻居节点尚未定位，则信标节点继续等待一小段随机的时间后，重复请求消息；若有邻居节点返回消息并且邻居节点已经定位完毕，此时邻居节点成为已知节点，则未知节点把已知节点当成信标节点，重复执行步骤①。

④从n个信标节点中任取4个节点组成i（i=1，2，3，4，…，C4n）个四面体，得到包含未知节点的所有四面体，根据四面体相交后的重叠区域计算此重叠区域的质心坐标作为未知节点的坐标。

1．3．4 算法分析

信标节点广播消息时，采用洪泛的方法，使得通信距离内的未知节点都可以监听到消息，而且未知节点只负责监听消息，并不需要和相邻节点进行消息交换。这样就大大减少了网络中未知节点的通信量，增加了网络生命周期。但是为了使得未知节点能够监听到更多的信标节点，我们设定能量较多的信标节点来广播两次消息。第一次广播消息时同时监听周围的信标节点的广播，将监听到的其他信标节点的消息记录下来。第二次广播时，将所知道的所有的信标节点的信息都广播出去，此时监听的节点将接收到的消息和第一次接收的消息对比，若发现有新的信标节点则及时更新信息。

对于未知节点监听到的信标节点，不能构成四面体相交的，利用球体重合区域的质心作为未知节点的坐标。如果未知节点监听到的信标节点数目较少，可以利用已经定位完毕的节点来对未知节点进行定位。在求解球体重合区域的质心时，可以利用网格扫面算法，计算量较大、误差较小；也可以利用四面体质心扫面算法，计算量较小但是误差较大，根据实际情况予以选择。

1．4 算法流程

整个算法的流程如图2所示。

2 实验仿真与评估

本文中采用的仿真软件是Visual C++与Matlab7．5，选取的实验参数是定位覆盖率和定位误差。仿真实验中，200个节点是随机部署在边长为80 m的正方体监测区域内，信标节点和未知节点的通信半径都是一样的。为了减少随机分布和偶然因素带来的影响，仿真的结果是在相同的参数下仿真50次的平均值。通过比较二维空间中的APIT和文中提出的三维TDAPIT算法在不同的信标节点比例的情况下的定位覆盖率和定位误差，最后来分析扩展后算法的优劣。

2．1 定位覆盖率

定位覆盖率随信标节点比例变化图如图3所示。在信标节点比例为5％时，APIT定位覆盖率约为10％，而TDAPIT约为30％，这说明相对于二维空间中的APIT定位，TDAPIT定位在三维空间中的定位覆盖率在信标节点比例较小时，仍能发挥相当的效用。随着信标节点比例的上升，TDAPIT的定位覆盖率更是明显地上升，在信标节点比例为20％左右时，定位覆盖率就达到了90％以上。在这以后，信标节点比例的增加对定位覆盖率的影响大大降低。这是因为在算法中采用了循环扩散的思想，即将已知节点当做信标节点来实现定位，最大限度地减少了不良节点的数目。在信标节点比例达到30％左右时，APIT算法的定位覆盖率在85％左右，而且仍然还有上升的趋势，说明APIT算法对信标节点比例的依赖程度比较高。

2．2 定位误差

定位误差随信标节点比例变化图如图4所示。该仿真结果说明，在网络部署一定时，当两种算法的定位误差达到35％左右时，两者的定位精度很难再得到明显改善。在信标节点比例为5％左右时，TDAPIT的定位误差明显大于APIT的定位误差，这是因为在网络的初始阶段，APIT可定位的节点数目较少，而TDAPIT能够定位的节点相对较多，而且TDAPIT定位时，利用了本身定位就有误差的已知节点，使得定位出的节点的误差得到累加，明显加大了定位误差。当信标节点比例在20％左右时，两种算法的定位误差变化不明显，此时增加信标节点比例时，TDAP IT略显优秀，但定位误差仍然在30％以上，由此可见这种非基于测距的定位方法虽然成本较低、实现简单，但是定位误差比较大，而且当信标节点比例达到30％时，定位误差仍然在30％以上，此时即使增加信标节点的比例也很难改变定位误差。

结语

本文基于平面中的APIT算法，提出了扩展的三维TDAPIT算法。并在分析APIT误差来源的基础上，对TDAPIT进行了相应的改进。扩展的TDAPIT算法能够较好的在三维空间中实现节点的定位。通过仿真实验，虽然在网络的初始阶段，TDAPIT的定位覆盖率在信标节点很少的情况下较高，但这是以增加定位误差为代价的。
责任编辑；zl