无线传感网络APIT定位算法的研究与改进※

苗少卿，高航，赵国安（南京航空航天大学计算机科学与技术学院，南京 210016）

无线传感网络APIT定位算法的研究与改进※

苗少卿，高航，赵国安
（南京航空航天大学计算机科学与技术学院，南京 210016）

针对APIT定位算法在节点分布不均匀和信标节点较少时定位误差较大的问题，对原算法进行改进，其中包括节点分布稀疏情况下，采用最短路径距离估算和三边测量的方法修正原算法三角形测试产生的Out-To-In Error，以及节点分布密集情况下，采用相对权重法修正In-To-Out Error。实验仿真结果表明，改进后的APIT算法定位精度和网络覆盖率相比原算法都有明显的提高。

APIT定位；三角形测试；网格扫描算法；三边测量

引 言

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

1 APlT定位算法及误差分析

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

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

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

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

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

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

图1 网格扫描算法示意图

图2 完备矢量构建示意图

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

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

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

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

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

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

2 改进的APlT定位算法

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

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

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

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

化简得：

令：

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

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

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

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

3 APlT改进算法仿真分析

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

3.1 原算法性能分析

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

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

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

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

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

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

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

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

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

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

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

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

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

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

结 语

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

编者注：本文为期刊缩略版，全文见本刊网站www. mesnet.com.cn。

［1］郭龙江，李建中，李金宝.无线传感器网络若干定位算法的研究［J］.计算机工程与设计，2006，27（12）：2114-2119.

［2］孙利民，李建中，陈渝，等.无线传感器网络［M］.北京：清华大学出版社，2005.

［3］T He，C Huang，B M Blum，et al.Range free localization schemes for large scale sensor networks［C］//ACM Int＇l Symptom Mobile Ad Hoc Networking and Computing（MOBIHOC 2003），Maryland，USA，2003.

［4］Z X Jia，C D Wu，Y Z Zhang，et al.Distributed Grid Location Estimation Scheme Based on Euclidean Distance［C］//IEEE 3rd Conference on Industrial Electronics and Applications，2008：1128-1132.

［5］Zhang Rui，Zhao Hang，Labrador，et al.A grid-based sink location service for large-scale wireless sensor network［C］//Proceedings of the 2006International Wireless Communications and Mobile Computing Conference，2006：689-694.

［6］萧奋洛.无线传感器网络节点设计和关键技术研究［D］.武汉：华中科技大学，2009.

［7］Liqiang Zhang，Xiaobo Zhou，Qiang Cheng.Landseape3D：A Robust Localization Scheme for Sensor Networks over Complex 3DTerrains［C］//Proceedings of the 31st IEEE Conference on Local Computer Networks，2006：239-246.

［8］王丹.三维无线传感器网络节点自定位算法研究［D］.成都：西南交通大学，2006.

苗少卿（研究生），研究方向为嵌入式操作系统；高航（副教授），研究方向为嵌入式系统及应用；赵国安（教授），研究方向为信息技术与物联网的应用。

Research and lmprovement of APlT Positioning Algorithm for Wireless Sensor Network※

Miao Shaoqing，Gao Hang，Zhao Guoan
（School of Computer Science and Technology，Nanjing University of Aeronautics&Astronautics，Nanjing 210016，China）

Aiming at the large positioning error problem of APIT positioning algorithm in no uniform nodes distribution and beacon less nodes，the article improves the original algorithm，including the distribution of nodes in sparse，amends the original triangle test produced a Out-To-In Error based on the shortest path distance estimation and three edge measurement method and dense nodes distribution situation，using the relative weight method to modify In-To-Out Error.The simulation results show that the positioning accuracy and coverage of APIT network algorithm are all improved compared to the original algorithm.

APIT positioning；the triangle test；the grid scanning algorithm；three edge measurement

TP393

A

��薛士然

2015-01-28）