基于静态无线传感器网络的APIT改进算法

杨凌云，冯友宏，王再见

(安徽师范大学 物理与电子信息学院,安徽 芜湖 241000)



基于静态无线传感器网络的APIT改进算法

杨凌云，冯友宏，王再见

(安徽师范大学 物理与电子信息学院,安徽 芜湖 241000)

摘要：在静态无线传感器网络中，传统的APIT算法认为未知节点是在由锚节点组成的三角形内部的，在这种前提下得到未知节点的位置判断结论的判断存在着很大的位置判别误差，从而影响了未知节点定位的精度，为了减少这种判别错误的出现，在传统APIT算法的基础上提出了一种基于三角形面积判别的方法，同时通过对能量值加权的质心算法估计出未知节点的坐标。同时通过Matlab对算法进行了仿真比较，该方法在一定程度上提高了定位精度，减少了估计误差。

关键词：APIT算法；面积判决；精度；质心定位；能量值加权

0引言

无线传感器网络是一种低损耗的无线网络传输技术[1]，它在很多领域特别是人类无法亲自到达的区域进行信息跟踪、数据采集等方面发挥着重要作用[2]。在这些地区，节点是随机播撒在指定区域的各个地方的，节点在初始状态下是不知道自身位置的，而节点没有自身位置信息是没有办法实现数据采集等工作的，节点自身定位是实现数据采集的非常关键的一个初始化行为。目前研究的节点自身定位方法根据是否与距离有关[2]，可以分为两大类：与距离有关的定位和与距离无关的定位方法[3]，其中APIT技术是一种典型的与距离无关的定位算法之一。它适合于高密度的节点自身定位，而且思想简单，容易实现，是目前比较有优势的一种自身定位算法[4]。本文针对APIT算法中对未知节点的是否在锚节点组成的三角形内部的判断提出自己的观点，它可获得更好的精度估计[5]。

1APIT算法

APIT算法中的PIT测试的核心思想就是在定位之前首先要确定要定位的未知节点是否在3个锚节点组成的三角形的内部，如果在就执行相关算法，估计出未知节点的值；如果不在，则认为是不合格的锚节点三角形，不予计算。这样就无形中提高了定位精度，剔除了一些误差比较大的估计值。但它是相对于动态节点的，如果未知节点同时远离或者靠近3个锚节点，那么节点就在三角形外，否则就在三角形内部[6,7]。但对于静态网络而言，节点位置相对来说是静止的，这种方法行不通，后来就有人提出通过比较这个未知节点的邻居节点与锚节点的距离关系[8]，如果邻居节点与锚节点距离同时大于或者小于未知节点与锚节点的距离，认为在三角形外部，否则认为在三角形内部[9-11]。

同时，在上面in-out判别算法的基础上，找出所有未知节点在锚节点组成的三角形内部的集合，计算所有集合的中心，估计出位置信息[12,13]。所以可以看到in-out判别方法和精确度直接关系着位置估计的精度，是一个非常关键的环节。针对PIT测试估计在一些极端情况下容易出现较大误差[14,15]，比方说，未知节点比较靠近锚节点组成三角形的一个边时，或者它的邻居节点位置比较分散，造成未知节点和邻居节点分别在三角形内部和外部时等[16,17]，提出一种新的基于三角形面积的in-out判断方法(NA-APIT算法)。

2改进算法(NA-APIT)

定理：在图1和图2中分别给出了未知节点D在锚节点ABC组成的内部和外部2种情况，可以看到，图1中未知节点在三角形内部时，未知节点和锚节点组成的新的三角的面积之和等于锚节点组成三角形的面积。而图2中未知节点在锚节点外部时，面积之和大于锚节点面积。

图1　未知节点在　　　　图2　未知节点在　三角形内部　三角形外部

证明：锚节点进行信息传递时，传递的信息包括节点能量信息和节点自身的位置信息，那么根据通用的能量传递公式，能量的传递与距离的平方是成反比例的关系，

即：

(1)

式中，E1为到达未知节点的能量，E0为锚节点发送时刻的能量，d1为未知节点与锚节点的距离，k为一常数，它与信号波长，传输环境等信息有关，特定的条件下为一常数，用k表示。

通过能量比值很容易得到未知节点到锚节点的相对精确的距离值，这样很容易得到三角形面积值，通过面积比较久可以得出未知节点D是否在锚节点组成的三角形的内部。

3改进后NA-APIT的算法流程

①所有的锚节点在通信半径范围内，向各个方向广播自己的节点位置信息和初始能量信息。

②未知节点把接收到的能量信息和初始能量信息相比较，并通过式(1)计算出未知节点到相对应锚节点的距离值。

④根据三角形加权质心定位算法，估计出这组估计值。这里提出一种精度更高的权值计算方法，即

三角形质心加权定位估计值为：

(2)

这里设三角形的3个点分别是A点(坐标(xA,yA))、B点坐标(xB,yB)和C点坐标(xC,yC)，未知节点到这3个锚节点的距离分别为d1、d2和d3。

⑥对所有符合条件的关于未知节点的估计值求平均，设有m个估计值，则估计值为：

(3)

⑦与实际的位置信息相比较，计算出估计误差：

(4)

式中，(x，y)为未知节点的实际二维坐标。

4算法仿真分析

在仿真实验中，选取的仿真环境为100×100的一片区域，在未知节点和锚节点随机分布在这篇区域，锚节点可以广播自己的位置信息和能量信息，仿真参数为锚节点的个数和通信半径，在不同的锚节点个数和不同的通信半径下2种算法的误差进行比较。

锚节点的个数为30个，节点通信距离从20~50 m之间的误差值如图3所示。从图3可以看出，在图中给出的通信范围内，改进后的算法有效降低了误差，提高了定位精度。

图3　不同通信距离的误差值比较

保持通信距离不变，锚节点的个数从30~60个之间的一个误差值如图4所示。锚节点个数的增加是每5个测试一次，从图4中同样可以得出结论：改进后的算法有效地降低了误差，提高了定位精度。

图4　不同锚节点个数的误差比较

5结束语

APIT算法是一种经典的静态无线传感器节点的定位算法，它的优点在于未知节点的定位与距离无关，随着对节点定位精度的提高，需要对其进行改进，针对APIT算法中未知节点与锚节点三角形位置关系的in-out判断方法进行了改进，提出了基于三角形面积的in-out判断方法，分别在改变距离和锚节点这2种条件下进行仿真，对2种算法进行误差比较，结果表明该改进算法有效地提高了未知节点的定位精度。

参考文献

[1]孙利民，李建中，陈渝，等.无线传感器网络[M].北京：清华大学出版社，2005：151-152.

[2]Niculescu D，Nath B.DV based Positioning in Ad Hoc Networks[J].Journal of Tele- communication Systems，2003，22(1)：267-280.

[3]嵇玮玮,刘中.DV-Hop定位算法在随机传感器网络中的应用研究[J].电子与信息学报,2008,30(4):970-974.

[4]Mechitov K，Sundresh S，Kwon Y， et al．Cooperative Tracking with Binary Detection Sensor Networks[C]∥Proceedings of the 1st Intemational Conference on Embedded Networked Sen-sor Systems，New York:ACM Press,2003:332-333．

[5]He Tian，Huang Cheng-du，Blum B M， et a1．Range-free Localization Schemes in Large Scale Sensor Networks[C]∥Proceedings of the 9th Annual International Conference on Mobile Computing and Networking MOBICOM’ 2003，San Diego，CA，USA，2003:81-95．

[6]韩彪， 徐昌彪， 袁海， 等.无线传感器网络中一种改进的APIT 定位算法[J].计算机工程与应用，2008,44 (4):122-124.

[7]Bulusu N，Heidemann J，Estrin D.GPS-less Low Cost Outdoor Localization for Very Small Devices[J]． IEEE Personal Communications Magazine， 2000,7(5):28- 34．

[8]Wang Jia，Fu Jingqi.Research on APIT and Monte Carlo Method of Localization Algorithm for Wireless Sensor Networks[C]∥Life System Modeling and Intelligent Computing，2010：128-137.

[9]孙庭波， 屈玉贵， 赵保华.一种无线传感器网络安全定位的新方法[J].小型微型计算机系统，2009,130 (9)：1738-1741.

[10]赵成林，毛松，谭虎.无线传感器网络能量均衡分簇路由协议[J].无线电工程，2011，41(3):1-4.

[11]陈爱斌，张陆勇，夏新兰，等.无线传感器网络能量异构分簇算法的研究[J].无线电工程，2012，42(1):7-10.

[12]梁小满，姜小奇，李英玲． 无线传感器网络节点的三维质心定位算法研究[J].通信技术，2009，42(2):121-123．

[13]赵清华，刘少飞，张朝霞，等.一种无需测距节点定位算法的分析和改进[J]．传感技术学报，2010,23(1):122-127.

[14]万国峰,钟俊.基于三角形理论的无线传感器网络定位算法[J].计算机应用研究,2013,30(1):249-251.

[15]徐小玲,张福强,李少彪.基于APIT的无线传感器网络质心算法研究[J].传感器与微系统,2011,30(7):57-59,63.

[16]俞黎阳,王能,张卫,等． 异构无线传感器网络中异构节点的部署与优化.计算机科学，2008,35(9):48-51．

[17]冯秀芳,关志艳,全欣娜.基于虚拟力的异构节点网络覆盖增强算法[J].计算机工程,2009(5):103-105.

Modified APIT Algorithm Based on Static Wireless Sensor Network

YANG Ling-yun,FENG You-hong,WANG Zai-jian

(College of Physics and Electronic Information,Anhui Normal University,Wuhu Anhui 241000,China)

Abstract：In static wireless sensor networks,the traditional APIT algorithm has a default consideration that the unknown sensor is inside the beacon triangle,and this may lead to serious error in position determination of the unknown sensor,which will influence the location precision.In order to reduce such errors,based on traditional APIT algorithm,the paper proposes a new method of energy weighting triangle area judgment to evaluate the unknown sensor’s position.Compared with the traditional APIT algorithm by Matlab,the result shows that the new method improves the location precision and reduces the estimation errors.

Key words：APIT algorithm; area judgment; precision; energy weighting

中图分类号：TP393

文献标识码：A

文章编号：1003-3114(2016)02-20-3

作者简介：杨凌云(1983—)，女，讲师，主要研究方向：无线电网络。冯友宏(1979—)，男，副教授，主要研究方向：无线电网络。

基金项目：国家自然科学基金项目(61401004)

收稿日期：2015-12-03

doi:10.3969/j.issn.1003-3114.2016.02.05

引用格式：杨凌云，冯友宏，王再见.基于静态无线传感器网络的APIT改进算法[J].无线电通信技术,2016,42(2):20-22.