引言

定位技术是无线传感器网络关键支撑技术之一[1]，在无线传感网络实际应用中，利用信标节点获得未知节点的绝对地理位置或者相对参照系位置的信息具有十分重要的意义。本文研究的APIT[3]定位算法是一种免于测距的定位算法，该算法基本思想简单，容易实现，具有功耗低、成本低、节点定位精度高等特点，因此得到广泛的应用和研究。然而APIT算法在节点分布稀疏和节点分布密集情况下容易出现较大定位误差，因此针对此问题本文提出一种改进的APIT算法。

1 APIT定位算法及误差分析

APIT定位算法是一种与距离无关的算法，该算法充分利用了无线传感网络中信标节点的拓扑结构信息。具体过程如下：

首先，信标节点覆盖在整个区域内，选取不共线的三个信标节点A、B、C组建三角形；其次，判断未知节点M是否在ΔABC内部，方法如下:未知节点M沿某一矢量l→移动到新的位置M′后，如果M′与三个端点A、B、C的距离满足关系式（1），则可以判定点M在ΔABC外部，如果不存在这样的方向矢量，则判定点M在ΔABC内部，并把ΔABC标记为优选三角形。定理证明见参考文献[3]，通过该方法可以找出包含未知节点的所有优选三角形。

最后，利用网格扫描算法 ( Grid Scan )将优选三角形区域无限重叠得到最佳位置，如图1所示。

图1 网格扫描算法示意图

可以看出，APIT算法依靠方向矢量进行三角形判定，要求有较高的网络连通度，然而组建一个完备矢量，要求同时满足：

① 未知节点与所有邻居节点连线方向矢量基本包括了0～2π的范围，如图2(a)所示。

② 方向矢量的构建要求在一个测试三角形内或者测试三角形外完成，如图2(b)所示。

图2 完备矢量构建示意图

在满足构建完备矢量的条件下，APIT测试可以顺利进行。相反，当节点分布稀疏或者节点分布不均匀时，会出现“内判外”或“外判内”的错误判定情况，如图3和图4所示。

图3 不满足构建完备矢量的示意图

图4 不同节点分布下误判发生情况

如图3(a)所示，这种情况下虽然满足矢量完备性条件1，但是不满足条件2，在三角形判定过程中，未知节点若选定邻居节点1构建方向矢量，则出现同时远离3个信标节点的情况，根据APIT测试，就会得出未知节点在三角形外的错误判断，称作内到外误判(InToOut Error)。如图4(b)所示，在节点分布密集时，远离或接近信标节点的方向矢量是很容易找到的，因此会出现较多InToOut Error。

如图3 (b)所示，这种情况下不满足矢量完备性条件1，所有的方向矢量没有同时远离或接近3个信标节点，根据APIT测试，就会得出未知节点在三角形内的错误判断，称作外到内误判(OutToIn Error)。这种错误常出现在节点分布稀疏的时候，如图4(a)所示。

这两种情况下APIT算法都会出现错误判断。其次在部署范围内的边界，信标节点往往不能将普通节点全部覆盖到，造成部分普通节点独立于信标节点外，无法定位，这种情况是由于APIT算法覆盖率不高造成的，也是APIT定位发生误差的主要原因之一。

2改进的APIT定位算法

在节点稀疏环境中，方向矢量少，没有同时接近或远离三角形的邻居节点，最容易出现较多的OutToIn Error。处在边缘环境中的未知节点组建的三角形数目较少或者根本无法组建三角形，也会造成APIT判定失效。针对这两个问题，可以通过以下方法弥补APIT定位缺陷：

① 首先，信标节点两两通信，记录到达对方的最短路径的距值，记为ξ。如图5所示，信标节点最短路径距离：ξAB=3,ξBC=3,ξAC=5。然后根据信标节点的位置信息，计算三角形三边距离总和L和平均最短路径l，设A、B、C的坐标分别为Ax1,y1,Bx2,y2,Cx3,y3,有：

图5 稀疏环境下未知节点与信标节点的最短路径示意图

② 其次，未知节点通过跳段式的传播方式与信标节点通信，记录到达3个信标节点所需要的最少跳数，记为λ，在图5中未知节点M到3个信标节点的最少跳数分别为λMA=3,λMB=2,λMC=4，这样估算出未知节点到3个信标节点的距离为:

③ 最后，利用三边测量法得:

化简得：

令:

则未知节点估算坐标为：X=[x y]。继续按上述方法计算第二组信标节点，直到到达规定的阈值N后结束，最后得到一组关于未知节点的估算位置Xi，求取平均值X-为最终估算位置。

在节点密集的环境中，由于方向矢量的增加，寻找同时远离或接近信标节点的方向矢量是很容易的，但会造成APIT算法出现InToOut Error。这里采用相对权重法来解决这个问题，该方法是通过权重对比，根据两种判定影响因素大小决定定位结果，以降低误判概率。方法如下:

① 每个节点设置计数器，用来计量权重值τ，初始状态为0。

② 统计所有方向矢量L→，分别进行APIT判定，记判外的方向矢量为L0→，次数为p，判内的方向矢量为Li→，次数q，通过式（8）比较二者权重:

最后根据τ的正负进行三角形的最终判断：若τ>0，那么未知节点在三角形内；若τ<0，则在三角形外。

改进后的APIT算法是针对不同的节点分布情况采用不同的定位方法， 当节点分布均匀时仍使用原始的算法，当节点分布不均匀时采用改进算法。这里以节点密度σ作为判定标准，设定最低门限为α，最高判决门限为β，当节点密度小于α或大于β时,均视为节点分布不均匀的情况，流程图如图6所示。

图6 改进后的APIT定位算法流程图

3APIT改进算法仿真分析

为了检测APIT改进算法与原始算法的性能，釆用MATLAB软件进行仿真。通过设置不同的实验环境，逐一比较两者的性能，每设置一次参数，仿真10次并对其结果取平均值作为最终数据。

3.1原算法性能分析

在1000×1000二维平面区域内随机部署100个未知节点和50个信标节点，设置未知节点通信距离为100 m，信标节点通信距离为300 m。

图7 不同密度下节点定位误差

如图7是APIT原算法在不同密度下节点的定位误差，可以看出，在节点密度低于11%或者高于24%时，定位误差较大。在节点密度较低的情况下，一方面导致判定方向矢量不足，在进行APIT判定时会出现较多的OutToIn Error，另一方面是信标节点稀疏无法组建有效的三角形，也会造成APIT算法失效；在节点密度较高情况下，与第一种情况相反出现较多的InToOut Error，同样导致误差较大。APIT算法在节点密度11%~24%之间时，定位误差维持在10%左右。因此，在改进的APIT算法中将最低判决门限α设为11%，最高判决门限β设为24%。在后面的仿真实验中，均按照此阈值进行对比分析。

3.2不同θ值下改进算法与原算法定位误差比较

设Ru是未知节点通信距离，Rb是信标节点距离，设通信半径比为θ，定义为Rb/Ru，不同θ值下的节点通信情况略——编者注，可以看出，随着信标节点通信距离的增加，网络覆盖面积也越来越大。

图8是不同θ值情况下原始算法与改进算法定位误差的比较。可以看出，改进后的APIT定位算法在不同的通信半径比情况下，定位误差相比于原算法都有明显的降低。

图8 不同θ值下改进算法与原算法定位误差比较示意图

3.3不同网络连通度下改进算法与原算法定位误差比较

APIT算法要求有较高的网络连通度，连通度是影响定位算法的关键因素，这里设置未知节点的通信范围为Ru，在信标节点通信距离一定，不同Ru情况下节点的通信情况略——编者注，可以看出Ru越大，单位面积内能够侦听到的信标节点越多，网络连通度越好。

图9 不同网络连通度下改进算法与原算法的误差比较

图9是不同的网络连通度情况下改进算法与原算法定位误差的比较。可以看出，改进后的APIT定位算法在不同的网络连通度情况下，定位误差相比于原算法都有明显的降低。

3.4改进算法与原算法网络覆盖率的比较

改进算法与原算法网络覆盖率的对比图略——编者注。可以看出，在信标节点比例较少的情况下，原始算法的覆盖率很低，只有极少的节点可以定位，而改进的APIT算法利用周围的邻居节点，在信标节点较少的情况下就可以有较高的覆盖率。改进后的APIT算法相比于原算法在不同的信标节点密度下，网络覆盖率有明显的提高。

结语

本文主要研究了无线传感网络经典定位算法之一的APIT算法，介绍了其定位原理及方法，并详细分析了APIT算法的缺陷以及产生原因，随后对算法出现的两种误判及稀疏节点环境下的定位限制进行改进，仿真结果表明，改进后的APIT算法定位误差和网络覆盖率都有很大的改进。