龚　健

（广州铁路职业技术学院，广州　510430）

改进内测点测试算法在无线传感网络中的定位研究

龚健

（广州铁路职业技术学院，广州510430）

在无线传感网络定位算法中，三角形内点测试APIT算法和最佳三角内测点PIT算法受节点密度影响较大，在特定情况下会出现In-To-Out Error和Out-To-In Error错误，导致目的节点实际坐标往往与三角重叠区域质心位置相差较远，影响定位精准度；新算法提出利用内测点三角成形面积有效检测和避免上述两类错误，并在重叠区域采取指纹分布概率以投票方式计算目的节点坐标；仿真实验证明，新算法受节点密度影响较小，拥有更高的定位精度和准确性。

三角形内点测试；In-To-Out Error；Out-To-In Error；RSSI

0　引言

无线传感器网络定位算法分为基于测距和无需测距算法两类［1-2］。三角形内点测试APIT算法属于无需测距算法，与同类基于跳数的DV-Hop算法、凸规划定位算法、改进跳数测距的Amorphous算法和最佳三角内测点PIT算法相比，在同等条件下其定位精度较高，对节点分布密度依赖性较小，满足低开销、低能耗工程需求，在无线传感网络定位中应用最广。

APIT算法在定位过程中，网络中各节点周期性广播自身位置坐标信息。目的锚节点根据接收信号强度计算彼此之间的距离和位置，以此判断该节点是否在其他节点组成的三角形内。设集合有n个节点，则存在C3n种选取方式组成不同的三角形，穷尽所有组合并逐一测试是否位于每个三角形内部，找出满足条件的所有三角形并利用网格扫描方法计算重叠区域质心，从而定位目的节点。网格扫描方式见图1。

APIT算法定位精度依赖于节点密度，节点越多，定位精度越高，当邻近节点较疏或不能组成三角形时容易产生较大误差，这是由于算法的In-To-Out和Out-To-In两种计算错误造成的［3］。

图1　APIT定位算法

1　In-To-Out Error和Out-To-In Error

1.1In-To-Out Error

目的节点M和相邻节点1、2、3都处于△ABC内部，节点3在△ABC外部并且与节点1、2、3的距离大于节点M的距离时，APIT根据算法会误将M判为在△ABC外部，导致In-To-Out Error，又称为边界效应见图2。

1.2Out-To-In Error

目的节点M和相邻节点1、2、3都处于△ABC外部，其中节点2、4较目的节点M更靠近三角形的边AB，此时节点2接收到来自A的信号强度和节点4接收到来自B、C的信号强度都高于其他节点，APIT根据算法会误将M判为在△ABC内部，导致Out-To-In Error，见图3。

In-To-Out Error和Out-To-In Error两种错误是由于节点分布不均造成的。APIT遍历找出所有三角形的重叠区域，当目的节点距离重叠区域质心较远时，算法只能在有限方向上进行判断，产生两类错误，导致较大定位误差［45］。因此，如何发现和避免In-To-Out Error和Out-To-In Error两类错误是提高APIT定位精度的有效方式，也是目前亟待解决的问题［67］。

图2　In-To-Out Error

图3　Out-To-In Error

2　新算法设计

新算法利用内测点三角成形面积判断内测点所处△ABC的位置，以此发现上述两类错误的产生。当新算法对每个三角内测点位置判断和APIT算法不同时，即判为发生In-To-Out Error和Out-To-In Error。此时若仍简单的利用网格扫描计算重叠区域质心位置必会产生较大误差［89］。新算法采用在三角重叠区域基于指纹分布概率对重叠区域网格进行投票，以此估算目的节点坐标。

2.1内测点位置的判断

目的节点M与A、B、C可组成3个三角形△AMC、△BMC和△AMB。若面积S△AMC+S△BMC+S△AMB=S△ABC，则即可判断M在△ABC内部，反之，若S△AMC+S△BMC+S△AMB＞S△ABC，则M在△ABC外部，见图4所示，以此发现APIT算法中可能出现的两类错误。

图4　内测点位置判断示意图

2.2基于指纹分布概率的投票方式

第一步：根据RSSI接收信号强度初始化RADAR损耗模型公式为：

第二步：以三角重叠区域质心O（Xo，Yo）为中心，建立直角坐标系，然后在范围内进行网格划分以及初始化。

第三步：根据RADAR损耗模型建立重叠区域位置指纹强度概率，建立概率分布直方图。如第i个网格接收到第k个节点的概率直方图为HRssi，见图5。

图5　概率分布直方图

定义C为第n个样本测量次数，Pck是每个样本接收到到邻居节点指纹为Rssck的概率，则Pck概率为：

其中Count（RSSck）是同一样本测量C次后的信号强度值为Rssck的出现次数。

第四步：设当前网格坐标为Lxy，信号强度为RSSxy，根据贝叶斯公式有：

其中：P（Lxy）在网格i内均匀分布。

由于无线传感网络中的锚节点信号相互独立，对于网络中每个节点存在以下关系：

则P（Rssi|Ln）在网格i信号强度向量为Rssi的条件概率，其值为：

P（Rssi|Ln）=P（（Rssi1，Rssi2，…，Rssin）|Ln）（5）

第五步：在三角重叠区域网格内根据P（Rssi|Ln）概率进行投票。投票过程所有节点具有相同权重，若节点在网格P（Rssi|Ln）概率有效覆盖范围内，则对其投票，格子票数越多，则越多三角形认可目的节点位置，得票最多的网格颜色最深，该网格即为目的节点位置，见图6。

2.3定位偏差

设l（x1，y1）为三角重叠区域A内任意一点，l（x1，y1）∈A，

图6　区域投票定位图

j（x2，y2）为新算法计算的节点位置，定位偏差为：

则重叠区域A上的定位偏差满足公式：

3　仿真测试

3.1测试环境

仿真环境采用基于网格节点放置模型，节点在100×100区域内随机分布，其中节点数量50，目的锚节点数10，节点通信半径20，利用MATLAB7.0软件对两种算法仿真比较。为减少节点随机分布导致的误差，所有结果均为在同等参数下仿真20次的平均值。

3.2定位偏差测试

如图7所示，3种算法定位偏差都随测距距离增加而加大。其中PIT算法定位偏差最大，APIT次之，这两种算法造成偏差的主要原因是受节点密度影响较大，节点分布不均会产生部分内测点测试失败的问题，导致In-To-Out Error和Out-To-In Error。内测点测试失败，目的节点实际位置必定和三角重叠区域质心相差较远，此时求其质心以计算节点坐标已无太大意义。新算法偏差最小，这是由于新算法利用内测点三角成形面积有效发现上述两类错误的发生，并在重叠区域采取指纹分布概率以投票方式计算目的节点坐标，定位结果最为精准。3.3节点密度对算法的影响

图7　定位偏差图

目前，几乎所有的定位算法都存在一个共性：定位偏差随节点密度增大而减小。在图8中，PIT和APIT算法的In-To-Out Error和Out-To-In Error受节点密度影响较大，当节点较为稀疏时偏差较大。但随着节点密度的增加，区域内达15个节点以上时，三角形内点测试可以参考更多的成形三角形加以参考，误判率明显降低，偏差都在3米以下。而新算法能有效避免两类错误的发生，在同样15个节点情况下，误差保持在1米以内。

图8　节点密度对误差的影响

4　结束语

新算法利用内测点三角成形面积有效发现和避免In-To-Out Error和Out-To-In Error两类错误的产生，并在三角重叠区域采取指纹分布概率以网格投票方式估算目的节点坐标，受节点密度影响较小，算法更为科学。下一步工作将着眼于改进传统RADAR损耗模型以修正指纹概率分布，进一步提高算法定位的精准度。

［1］唐明虎，张长宏，昝风彪.无线传感器网络APIT定位算法［J］.微型机与应用，2010（21）：114-120.

［2］周四清，陈锐标.无线传感器网络APIT定位算法及其改进［J］.计算机工程，2009（7）：275-279.

［3］徐云剑，郭艾寅.基于APIT的三维移动代理路由算法研究［J］.计算机应用研究，2010（6）：142-146.

［4］韩彪，徐昌彪，袁海，等.无线传感器网络中一种改进的APIT定位算法［J］.计算机工程与应用，2008（04）：23-28.

［5］He T，Huang C D，Blumb M.Range-free localiza-tion schemes for large scale sensor networks［A］.Proc of the 9th An-nual International MobiCom［C］.2013，22（14）：163-170.

［6］Ganeriwal S，Kumar R，Srivastava M B.Timing-Sync Protocol for Sensor Network［A］.Proceedings of the 1st international conference on Embedded networked sensor systems［C］.2013，16（6）：328-332.

［7］Agrawal P，Ghosh R K，Das S K.Localization of wireless sensor nodes using proximity information［A］.Proc of the16th Int Conf on Computer Communications and Networks（ICCCN2007）［C］. 2007，19（7）：1232-1240.

［8］Niewiadomska SzynkiewiczE，Marks.Optimization Schemes for Wireless Sensor Networks Localization［J］.Int.J.Appl. Math.Comput.Sci.2009，4（2）：398-403.

［9］Lazos L，Poovendran R.HiRLoc：High-Resolution robust localization for wireless sensor networks［J］.IEEE Journal on Selected Areas in Communications.2006，15（4）：1896-1911.

Research on The Localization of Improved Triangle Measured Point Test Algorithm in Wireless Sensor Networks

Gong jian
（Guangzhou Institute of Railway Technology，Guangzhou510430，China）

In wireless sensor network localization algorithm，the triangular test APIT algorithm and optimal triangulation measured point PIT algorithm are influenced by the density of nodes，and can lead to error Out-To-In and error In-To-Out.When these two types errors occur，the coordinates of node are often different from the centric of the triangle.New algorithm put forwards use the triangular area to avoid these two kinds of errors，and calculation fingerprint distribution probability in overlapping area to locate nodes.Finally，simulation show that the new algorithm can avoid the above two kinds of errors effectively and has higher positioning accuracy.

triangle interior point test；In-To-Out error；Out-To-In error；RSSI

1671-4598（2016）05-0309-03

10.16526/j.cnki.11-4762/tp.2016.05.085

TP393

A

2015-11-08；

2016-01-04。

中国高等教育学会2011年教育科学研究年度专项课题。

龚健（1968-），男，硕士研究生，讲师，主要从事计算机应用和高等职业教育研究。