摘  要： 分析了无线传感器网络分布边缘地带可能存在锚节点密度过小而造成的未知节点不能利用APIT法定位情况，有选择地将定位精度较高的已定位节点升级为锚节点，继续采用APIT定位，扩大APIT算法适用范围并防止误差过度积累。通过仿真，在对定位精度影响不大的情况下提高了定位覆盖率。
关键词： 无线传感器网络；节点；定位；APIT

　随着通信技术、嵌入式计算技术和传感器技术的飞速发展和日益成熟，无线传感器网络节点技术得到快速发展。根据定位机制可将无线传感器网络WSN（Wireless Senor Network）节点自身定位算法分为两类[1]：基于距离的(Range-Based)定位算法和不基于距离的(Range-Free)定位算法。Range-Free主要有基于接收信号强度衰减的定位(RSSI)及其改进算法[2]、基于到达时间的定位(TOA)和基于到达时间差的定位[3]、基于角度的定位(AOA）[4]。Range-Free定位算法无需节点间的距离和角度信息，仅根据网络连通性等信息实现定位，在成本、功耗等方面具有很大优势，对硬件要求较低，主要有质心算法、DV-HOP算法、Amorphou算法[5]、HOP-TERRAIN算法、APIT算法等[6]，特别是APIT算法备受关注。然而，无线传感器节点的分布具有随机性，当锚节点密度过小时，传统APIT算法定位覆盖率下降。本文通过将已定位节点有选择地升级为锚节点，继续应用APIT算法定位，在防止定位误差过度积累的同时提高了节点定位覆盖率。
1 APIT定位算法
1.1 PIT算法定位基本原理
    最佳三角形内点测试法PIT（Perfect Point-In-Triangulation Test）原理如图1所示，假如存在一个方向，M点沿着这个方向会同时远离或接近A、B、C，则M位于△ABC外，否则M位于△ABC内。

1.2 APIT算法定位原理
    为了能在静态网络中执行PIT测试，定义APIT（Approximate Point-In-Triangulation Test）：假如节点M的邻居节点中没有同时远离或者靠近三个锚节点A、B、C的节点，则节点M就在△ABC内，否则M在△ABC外。利用无线传感器较高的节点密度来模拟节点移动，在给定方向上，距离锚节点越远接收信号越弱，利用这一无线传播特性来判断与锚节点的远近。通过邻居节点之间的信息交换，仿效PIT测试，如图2（a）所示，节点M通过与邻居节点1交换信息，得知如果自身移动到节点1将远离锚节点B和C，但会接近A，与邻居节点2、3、4的通信和判断过程类似，最终确定自身位于△ABC内；而图2（b）中，节点M可知若自身运动至节点4，则同时远离锚节点A、B、C，最终判断出自身在△ABC外。

    在APIT算法中，一个未知节点在其通信半径内任选3个锚节点，测试自己是否位于它们所组成的三角形中，使用不同锚节点的组合重复测试，直到穷尽所有组合或达到所需的定位精度。最后计算包含目标节点的所有三角形重合区域的质心，将这一点作为未知节点的位置。
1.3 in-to-out error与out-to-in error
    在某些情况下，APIT算法也存在误判情况。如图3(a)所示，当未知节点靠近三角形的一边，且邻居节点2位于三角形内时，根据APIT定义，若未知节点M移动至节点2，则同时远离锚节点A、B和C，从而做出M位于△ABC外的错误判断，称为in-to-out error；当节点M的邻居节点分布如图3(b)所示时，就会做出M在△ABC内的错误判断，称为out-to-in error。

1.4 未知节点的邻居锚节点少于三个的情况
    因为未知节点和锚节点的分布具有很大的随机性，所以在网络覆盖区域的边缘地带未知节点很可能拥有比较少的邻居锚节点，致使无法满足APIT算法定位条件，甚至当邻居锚节点少于3时，未知节点将不能被定位。如图4所示，无论节点B旁边的锚节点怎么组合都无法将B包含在内，而节点C在通信半径范围内的锚节点数量甚至少于3个。有文献提出将已定位节点升级为锚节点参与定位，但是，这将会带来积累误差[7]。

    试验显示[7]，在无线信号传播模式不规则和传感器节点随机部署的情况下，APIT算法定位精度高、性能稳定、测试错误概率相对较小(最坏情况下14%)，平均定位误差小于节点无限射程的40%。与其他Range-Free算法相比本算法最大的优点是更为简单，节点密度影响小且节点间通信量少，大大降低了功耗，相对于资源受限的传感器网络比较合适。但是在同一锚节点比例下，随着未知节点数目的增加，定位覆盖率急剧下降，说明APIT算法不具有很好的扩展性。随着网络部署规模扩大，将会有更多的节点得不到有效利用。
2 APIT算法改进
    参考文献[8]提出了信标节点可迁移的方法，本文将该方法与APIT结合，提出IAPIT算法。算法的主要思想是，当未知节点在通信半径内锚节点不足3个时，使未知节点在其通信范围内的已定位节点Mj(j∈{1，2，…，N})有选择地升级为锚节点，然后再继续运用APIT算法定位。已定位节点有选择地升级为锚节点的方法如下：
    (1)已定位节点Mj向其通信半径内所有锚节点广播包含其ID的数据包；
    (2)已定位节点Mj的所有邻居锚节点根据各自收到的数据包值计算出锚节点和已定位节点间的距离，由凸规法可知，仅当不等式组（1）成立时，已定位节点的范围可以确定，此时未知节点升级为候选锚节点，若不等式组无解，则已定位节点无法升级。

    同时，利用质心加权法和信号强度定位的结果间的误差为：
    
    (4)网络中的未知节点通信半径范围内若有符合条件的升级锚节点，则可以被未知节点利用，以满足APIT算法。
3 算法流程图
    算法流程图如图5所示。

4 性能仿真
4.1 仿真环境和参数
    仿真环境采用Visul C++和Matlab，每次仿真都运行算法50次，然后求平均值得到结果，仿真相关参数如下：
    (1)节点部署的网络区域为40 m×40 m的正方形，节点总数为100、150、200和300四种情况，所有节点都随机分布在该区域；
    (2)未知节点和锚节点通信半径取为10 m；
    (3)测距误差取为0～30%真实距离的随机分布，以接近最坏情况；
    (4)定位结果误差门限ε=5 m，δ=5 m，σ=3 m。
4.2 IAPIT仿真结果
    以相同的锚节点与未知节点密度比列对定位覆盖率和定位精度进行仿真。如图6（a）所示，IAPIT算法定位覆盖率最高可达到90%，较传统APIT算法有所提高。从图6（b）可知，未知节点定位精度变化不大。

　总体而言, 新算法通过有选择地将已定为节点升级为锚节点，在降低定位误差积累、对定位精度影响不大的情况下，提高了定位覆盖率。由于无限传感器网络的各种应用差别很大，没有普遍适合各种应用的定位算法，因此应综合考虑，本文提出的算法具有较强的扩展性，对于大规模无线传感器网络节点定位具有参考价值。
参考文献
[1] 孙利民，李建中，陈渝，等.无线传感器网络[M].北京：清华大学出版社，2005.
[2] 余义斌.传感器网络定位算法及相关技术研究[D].重庆：重庆大学，2006.
[3] 于海斌，曾鹏，智能无线传感器网络系统[M].北京：科学出版社，2006.
[4] NICULESCU D，NATH B.Ad Hoc positioning system(APS) using AOA[A].Proc.of the IEEE INFOCOM2003[C].Vol.3，San Francisco：IEEE Computer and Communications Societies，2003.
[5] 王福豹，史龙，任丰原.无线传感器网络中的自身定位系统和算法[J].软件学报，2005(16)：857-868.
[6] 段渭军，黄晓利，王福豹，等.无线传感器网络测距技术的研究[J].计算机科学，2007(9)：51-62.
[7] HE T，HUANG C D，BLUM B M，et al.Range-free localization schemes in large scale sensor networks[C].In Proc. ACM/IEEE 9th Annu.Int.Conf.Mobile Computing and Networking(MobiCom’03)，2003.
[8] 沙超，王汝传，孙力娟，等.无线传感器网络中一种信标节点可迁移的协作定位方法[J]，电子学报，2010，38(11)：2624-2629.