WSN 基于节点位置相对关系定位的数学属性研究

刘 壮，晁美霞，张 婧，张 昕，刘 妍，张剑飞

(长春理工大学计算机科学与技术学院，长春130022)

WSN 基于节点位置相对关系定位的数学属性研究

刘 壮，晁美霞，张 婧，张 昕，刘 妍，张剑飞

(长春理工大学计算机科学与技术学院，长春130022)

为解决无线传感器网络基于位置相对关系进行定位算法中，定位精度过度依赖信标节点密度问题，通过3种非测距定位算法、质心算法、APIT(Approximate Point in Triangulation)算法及AIGS(Annulus Intersection and Grid Scan)算法的原理研究，给出了信标节点密度与定位精度和能耗之间的数学关系，并提出基于迭代的改进算法。3种算法定位精度正比于信标节点密度，算法能耗正比于信标节点密度，在同一个监测区域，信标节点比例相同情况下，AIGS算法定位精度最高，质心算法定位精度最低。当信标节点稀疏时，将部分未知节点通过质心算法转化为信标节点迭代算法，在较低信标节点比例条件下提升3种算法定位精度。

无线传感器网络;非测距定位算法;信标节点密度;能耗;迭代

0 引 言

在无线传感器网络(WSN:Wireless Sensor Network)中节点位置信息十分重要，因为没有携带位置信息的数据是毫无价值的。

目前，传感器的定位机制是根据少量的已知信标节点(Anchor Nodes)的位置按照某种定位方法计算未知节点位置。信标节点采用GPS进行定位，能耗较高，通信成本较大，因此无线传感器网络大多采用有限的信标节点［1］。目前无线传感器网络中定位算法一般分为基于测距［2］和基于非测距［3］两类，基于测距的定位算法需要通过测距硬件测量得到节点间实际距离或测角度硬件测量得到节点间发射夹角，使用三边或三角或最大似然估计法计算未知节点位置;基于非测距定位算法无需测量节点之间的实际距离或方位，节点可通过某种定位机制估计未知节点位置。前者定位精度高，但硬件成本较高，会提高网络部署成本;后者测量准确性较差，但实现简单，节点不需要额外硬件支持，成本低，功耗低，在大多数应用场景中能实现满足要求定位精度。典型的基于非测距定位算法有质心算法［4］、APIT［5］、DV-Hop［2］，但它们也存在一些缺点［6］，质心算法定位精度过低，APIT算法会出现较大比例的IntoOut和OuttoIn错误，DV-Hop算法会出现定位覆盖不足问题。文献［7］提出一种基于三角形重心扫描的改进 APIT (Approximate Point In Triangulation)算法，减少了因边界效应和信标节点密度低而引起OutToIn和InToOut问题。文献［8］提出一种基于最优信标节点的WSN质心位置计算算法，以解决质心算法较低精度的问题。笔者通过深入分析3种基于非测距的算法:质心算法、APIT算法以及文献［9］提出的一种基于圆环重叠区域和网络扫描(AIGS:Annulus Intersection and Grid Scan)的定位算法，得出信标节点密度与定位精度的关系，以及其三者之间的能耗消费高低的结论，从而为非测距定位算法的数学属性方面的研究提供有价值的参考。

1 相关工作

1.1 质心算法

质心算法［7］是一种基于网络连通性的比较简单容易实现的定位算法。该算法根据未知节点周围一定范围内不同信标节点组成的二维欧氏空间的多边形的欧氏几何中心作为未知节点的计算估计位置，未知节点通信半径内的信标节点的选择，可以是一跳范围内也可以是多跳范围内，这取决于WSN中的信标节点密度。信标节点通过周期内向其通信范围内的邻居节点广播数据包(位置、ID标识)，同时，未知节点会预设阈值K或设置特定时间t，若收到的数据包数量大于K或收到数据包的时间超过t，未知节点则停止接收这些来自不同信标节点的数据，并且以之前收到的信标节点的信息为依据确定自身位置。未知节点将这些信标节点所组成多边形的质心(即坐标平均值)作为估算坐标(见图1)。

如图1所示，节点O(x，y)为需要定位的未知节点，节点A(x1，y1)、B(x2，y2)、C(x3，y3)、D(x4，y4)、E(x5，y5)、F(x6，y6)为节点O通信半径内的信标节点，节点O在估算自身位置时将这些信标节点组成多边形并使其充当该形状的顶点，节点O的坐标是多边形ABCDEF的几何质心，可表示为

图1 质心算法原理图Fig.1 Principle diagram of centroid algorithm

其中(x，y)代表未知节点O的坐标，(x1，y1)、(x2，y2)、(x3，y3)、(x4，y4)、(x5，y5)、(x6，y6)代表6个信标节点坐标。

图2 APIT原理图Fig.2 Principle diagram of APIT

1.2 APIT定位

APIT算法原理如图2所示。近似的三角形的内点测试法(APIT)［8］是一种定位简单，对硬件要求不高的经典的非测距定位算法。该算法的主要思想是利用未知节点周围与其相邻3个信标节点组成的三角形，运用三角形内点测试(PIT)理论［10］，即当未知节点沿着一个方向移动同时能靠近和远离组成的三角形时，则表示节点在三角形外部;反之，节点在三角形内部，从而判断未知节点的位置是在三角形内部还是其外部。最后，找出未知节点附近信标节点组成的所有三角形，并把三角形的重叠区域的中心作为未知节点的位置。

1.3 AIGS算法

AIGS算法原理如图3所示。AIGS算法［6］是一种通过对比未知节点周围信标节点发射信号强度的大小，优化信标节点，并利用雷达扫描法求出未知节点位置的定位算法。

该算法的主要思想是每个信标节通过记录其他信标节点发射的位置信息和接收到信号的强度及信号到达的时间判断它们之间的距离，并将此信息发送给未知节点。未知节点根据接收的信息，并以某个信标节点为参照，按最大最小的原理，即以该未知节点到这个信标节点的强度为参照，找出一定范围内其他信标节点集合中到此信标节点信号强度比自己到此信标节点信号强度大的里面最小的一个和小的里面最大的一个，标记这3个信标节点，并以参照的信标节点为圆心，分别以最小信号强度和最大信号的距离为半径，画圆并形成圆环。最后，找出若干个这样的圆环，以圆环之间的重叠区域内的质心作为未知节点的估计坐标。

图3 AIGS原理图Fig.3 Principle diagram of AIGS

2 位置相对关系定位算法数学属性分析

2.1 节点密度与定位精度

定位技术是传感器网络应用的前提，定位精度的提高直接关系到传感器节点采集的数据有效性的增强。对于一个定位算法，定位精度显示了节点的计算位置与物理位置的匹配程度，节点定位精度为定位误差除以通信半径，表示如下

其中p表示定位精度，e表示定位误差，R表示节点的通信半径。从式(2)中可以得出，e越小，p越小，p定位算法的定位准确性越好。

基于非测距的节点定位算法是通过信标节点进行定位，所以信标节点密度对评价节点定位算法非常重要。信标节点密度为信标节点在全网节点所占的比例，如下所示

其中na表示WSN中的信标节点数目，N表示WSN中节点总数。通常情况下，d越大，p越小，在整个WSN中，当na=N时，即d=1，则所有的节点都是信标节点，不再需要额外的定位即可实现全网定位。

下面从定位精度和信标节点密度两方面讨论笔者方案的质心算法(Centroid)、APIT算法和AIGS算法。

质心算法完全依赖于网络连通能力，无线通信模型为理想的球形，未考虑影响定位精度的噪声、干扰等环境，在定位过程中使用迭代方法计算未知节点的估计坐标，会造成误差累积，而且算法实现过程中无法修正这些误差;APIT算法对网络连通性的依赖较大，定位过程中未知节点需要与信标节点通信且交换数据，对节点的密度较高，适合于信标节点比例较高的WSN，在信标节点较低的WSN中，该算法无法实现准确定位;AIGS算法的定位精度在信标节点一定情况下，信标节点的比例越大，定位越准确，其定位精度随着通信半径R的增加而提高。

信标节点分布随机，监测区域内密度不均匀，每个未知节点接收到信息的信标节点的数量也不相同。质心算法中，一个未知节点每增加一个信标节点的信息就会引起几何图形的改变而使质心变化即节点估计位置发生变化;APIT算法中，每多接收一个信标节点信息，三角形的组成数目由增加到，这表示从n个信标节点增加到n+1个信标节点，三角形数量通过组合公式也相应增加。因而最多三角形的覆盖区域发生改变，中心也会发生改变;AIGS算法中，每增加一个信标节点都会改变圆环宽度，改变未知节点估计坐标值。

综上所述，在信标节点密度d相同情况下，pc＜pa＜po，其中Pc表示质心算法定位精度，Pa表示APIT定位精度，Po表示AIGS算法定位精度。通常，定位精度很大程度上受网络初始化时所部属的信标节点的比例及分布情况影响。信标节点密度越大，分布越均匀，未知节点定位精度越高。因此评价一个定位算法的指标为R越高，d越低，表明这种算法性能越好。

2．2 通信能耗和计算能耗

无线传感器网络中，在对未知节点进行定位过程中，通常利用信标节点位置计算未知节点位置。在此过程中，信标节点和未知节点不断发送或接收广播信息，并根据接收信息，计算未知节点位置，同时将产生通信能耗和数据能耗。根据Heinzelman提出的无线通信能耗模型［11］，发送n比特字节无线传感器节点所需要能量为

其中Eelec为发射装置和接收装置电路单位bit能耗，εamp为发射放大器将每bit传送单元平方米所耗能量，εfs为空闲空间能耗，d为两个传感器节点请求数据传输距离，R为通信半径。

下面从通信能耗和计算能耗两方面讨论笔者方案的质心算法、APIT算法和AIGS算法。

根据式(4)，通信能耗ETx(n，d)为发射接收电路能耗Eelec与空闲空间能耗εfs之和。信标节点密度越大，发送广播信息就越多，即n越大，质心算法、APIT和AIGS等3种算法通信能耗越大。质心算法每增加一个信标节点，就会增加一次一跳范围内广播，APIT算法每增加一个信标节点，就会增加一次与一跳范围内未知节点的信号强度对比广播，AIGS算法每增加一个信标节点，会增加一次与一跳范围内信标节点的信号强度对比广播。

根据质心算法的原理，未知节点位置根据信标节点组成的多变形质心求出，信标个数m每增加一个，成为m+1的计算能耗，相应计算能耗越大。APIT根据未知节点附近所有信标节点组成的三角形重叠区域中心即为未知节点位置，假设某个未知节点周围有m个信标节点，此时组成三角形的个数为，每增加一个信标节点，三角形的个数将变为，将会增加个三角形的网格扫描计算能耗。AIGS运用未知节点附近信标节点强度，优选一些信标节点，根据最大最小原理，形成m个圆环，每增加一个信标节点，多一次对比信号强度的广播通信能耗，会多一次计算信号强度大小关系的计算能耗。

通过以上数学属性分析，可以设置节点密度，信标节点密度和通信半径的合理取值范围，在节点密度稀疏情况下，可以使用迭代方式将部分定位的未知节点转换为信标节点进行计算，下面是笔者提出的改进方案。

3 基于信标节点迭代的改进定位方案

笔者对质心算法、APIT和AIGS3种算法在Matlab 2011Rb下进行仿真实验，分析节点密度对通信误差影响。在通信半径为30 m情况下，定位精度对比图如图4所示。

从图4中可以看出，定位精度随着信标节点比例增加而提高，所以在信标节点稀疏时，笔者提出一种基于迭代改进算法。在监测区域中信标节点比例过低时，一个未知节点接收到信标节点总数就会很少，使用几何图形中相关属性进行估测未知节点位置时将会出现很大误差。为了降低此种误差，当一个未知节点获得本身位置信息时，会模拟信标节点广播信息(ID、位置信息)，而另一个未知节点接收到其信息和其他信标节点信息确定其位置，以此类推，可确定全部未知节点位置。这种定位思想在信标节点稀疏时动态增加了信标节点密度，提高了定位精度，但也使能量消耗增大。

图4 定位精度对比图Fig.4 Comparison diagram of localization accuracy

根据图4对比的3种算法，下一步研究需要分别降低这3种算法部署时的信标节点比例，定位一部分未知节点，通过迭代方式，将已定位未知节点作为新信标节点，对未定位未知节点进行定位，对比定位精度变化情况。

4 结 语

笔者通过无线传感器网络中质心算法，APIT和AIGS3种基于非测距定位算法分析，得出信标节点密度越大，定位精度越准确，但会引起更高的通信能耗和计算能耗。在信标节点密度稀疏条件下，提出一种基于迭代改进方案，该思路可提高定位精度，降低了网络部署成本，但此改进也增加了通信能耗和计算能耗，因此如何减少通信能耗和计算能耗并实现高定位精度成为进一步研究方向。

［1］孙利民，李建中，陈渝.无线传感器网络［M］.北京:清华大学出版社，2005. SUN Limin，LIJianzhong，CHEN Yu.Wireless Sensor Networks［M］.Beijing:Tsinghua University Press，2005.

［2］ZHANG D，LIU Y，GUO X，et al.On Distinguishing the Multiple Radio Paths in RSS-Based Ranging［C］∥Proceedings of IEEE INFOCOM.Orlando，FL:IEEE Press，2012:2201-2209.

［3］XIW，ZHAO J，LIU X，et al.EUL:An Efficient and Universal Localization Method for Wireless Sensor Network［C］∥Proceedings of IEEE ICDCS.Montreal，QC:IEEE Press，2009:192-210.

［4］朱博，陈曙.一种无线传感器网络质心定位算法［J］.传感技术学报，2010，23(6):868-872. ZHU Bo，CHEN Shu.An Improved Centroid Localization Algorithm for Wireless Sensor Network［J］.Chinese Journal of Sensors and Actuators，2010，23(6):868-872.

［5］HE T，HUANG C，BLUM B M，et al.Range-Free Localization Schemes for Large Scale Sensor Networks［C］∥Proc 9thAnnual Int'l Conf on Mobile Computing and Networking(MobiCom).San Diego，CA:Department of Computer Science School of Engineering University Virginia，2003:81-95.

［6］杨铮，吴陈沭，刘云浩.位置计算:无线网络定位与可定位性［M］.北京:清华大学出版社，2014. YANG Zheng，WU Chenshu，LIU Yunhao.Location-Based Computing:Localization and Localizability of Wireless Networks［M］.Beijing:Tsinghua University Press，2014.

［7］周勇，夏士雄，丁世飞，等.基于三角形重心扫描的改进APIT无线传感器网络自定位算法［J］.计算机研究与发展，2009，46(4):566-574. ZHOU Yong，XIA Shixiong，DING Shifei，et al.An Improved APIT Node Self-Localization Algorithm in WSN Based on Triangle Center Scan［J］.Journal of Computer Research and Development，2009，46(4):566-574.

［8］陈晓海，彭舰，刘唐.基于最优信标节点的无线传感器网络质心定位算法［J］.计算机应用，2015，35(1):5-9. CHEN Xiaohai，PENG Jian，LIU Tang.Optimal Beacon Nodes-Based Centroid Localization Algorithm for Wireless Sensor Network［J］.Journal of Computer Application，2015，35(1):5-9.

［9］LIU Zhuang，FANG Zhiyi，REN Naiji，et al.A New Range-Free Localization Algorithm Based on Annulus Intersection and Grid Scan in Wireless Sensor Networks［J］.Journal of Information and Computational Science，2012，9(4):831-841.

［10］陈锐标.无线传感器网络APIT定位算法研究［D］.广州:暨南大学信息科学技术学院，2008. CHEN Ruibiao.Research on APIT Localization［D］.Gaungzhou:College of Information Science and Technology，Jinan University，2008.

［11］WENDI B HEINZELMAN，ANANTHA P CANDRAKSAN，HARI BALAKRISHNAN.An Application-Specific Protocol Architecture forWireless Microsensor Network［J］.IEEE Transactions on Wireless Communications，2002，1(4):660-670.

(责任编辑:刘东亮)

Research on Mathematical Properties of Localization Algorithm Based on Sensor Relative Position in WSN

LIU Zhuang，CHAO Meixia，ZHANG Jing，ZHANG Xin，LIU Yan，ZHANG Jianfei

(College of Computer Science and Technology，Changchun University of Science and Technology，Changchun 130022，China)

Three kinds of range-free localization algorithms including Centroid algorithm，APIT(Approximate Point In Triangulation)algorithm and AIGS(Annulus Intersection and Grid Scan)algorithm are studied.We research on the mathematical relationship between density of anchors，location precision，and energy consumption.Research shows that the three algorithms can all getmore accurate location when enhance the density of anchors.However，all of those causemore energy consumption.In themonitoring area with the same proportion of anchors，comparing about positioning accuracy，AIGS algorithm is better than APIT algorithm，but APIT algorithm is better than Centroid algorithm.When density of anchors is low，we propose an iterative scheme which transforms unknown nodes after localization to beacon nodes.The new scheme can increase localization accuracy ofWSN(Wireless Sensor Network)with low density of anchors.

wireless sensor network(WSN);range-free localization algorithms;density of anchors;energy consumption;iterative ideology

TP393

A

1671-5896(2015)06-0685-05

2015-09-28

国家自然科学基金资助项目(61275080)

刘壮(1980— )，男，长春人，长春理工大学讲师，博士，主要从事物联网、无线传感器网络和复杂网络研究，(Tel)86-13159539927(E-mail)liuz@cust.edu.cn;通讯作者:张婧(1986— )，女，长春人，长春理工大学讲师，博士，主要从事物联网、无线传感器网络和计算机网络研究，(Tel)86-18686657001(E-mail)zhang_jing@cust.edu.cn。