基于RSSI的无线传感器网络三角形质心定位算法
周林 张厚望
摘 要： 无线传感器网络中，由于传统质心算法普遍存在信标节点分布不均与中心化问题，导致定位误差相对较大。针对这些问题，提出了基于RSSI的改进算法。在APIT的基础上，改进算法依靠未知节点接收到不同信标节点的RSSI数值，判断其周围是否存在最佳三角形，若存在则利用最佳三角形进行定位；若不存在则选出一个距其较近的三角形，利用移动信标节点的办法来缩小此三角形的范围进行定位。Matlab平台仿真结果表明，与传统质心算法相比，改进算法减少了定位误差，节点定位精度有所提高。
关键词： 无线传感器网络； 质心定位算法； APIT； RSSI； 最佳三角形； 移动信标节点
中图分类号： TN926?34 文献标识码： A 文章编号： 1004?373X（2015）01?0030?05
Abstract： In wireless sensor network， due to the widespread problems of beacons nodes' uneven distribution and centralization， traditional centroid algorithm has relatively large positioning error. In order to solve these problems， an improved algorithm based on RSSI is proposed. On the basis of APIT， the improved algorithm uses the received signal strength from different beacon nodes to determine whether the surrounding of a unknown node exists the best triangle. If does， the improved algorithm would use the best triangle to locate. If not， the improved algorithm would select a triangle which is closer to the unknown node and use the method of moving beacon node to narrow range of the triangle to locate. The results of Matlab simulation shows that， compared with the traditional centroid algorithm， the improved algorithm can reduce the positioning error and improve the positioning accuracy of nodes.
Keywords： wireless sensor network； centroid positioning algorithm； APIT； RSSI； best triangle； moving beacon node
0 引 言
在无线传感器网（Wireless Sensor Network，WSN）中，位置信息对传感器网络的监测活动至关重要，确定事件发生的位置或获取信息的节点位置对传感器应用的有效性起着关键的作用[1]。节点定位技术为整个网络系统获取大量真实且可靠的监测信息，提供了网络应用中非常重要的节点地理位置信息[2]。可以说，没有位置信息的信息是没有意义的。
在无线传感器网络中，有两种节点[3]：一种是已知自己地理位置信息的节点，称为信标节点，通过人工测量或者利用GPS等定位设备来获得自身的地理位置信息；另外一种是不知道自己地理位置信息的节点，称为未知节点，要借助信标节点的位置信息来确定自身位置。
在统计和系统分析已有定位算法的基础上[4]，一般按照是否采用测距技术，将定位算法分为基于测距（Range?based）的定位算法和无需测距（Range?free）的定位算法。质心定位算法的提出是为了避免节点之间直接测量距离，属于无需测距的定位算法。本文在RSSI技术、APIT方法与质心定位算法的基础之上，提出了一些改进，实验结果表明改进算法可以减少定位误差，提高节点定位精度。
1 算法模型
1.1 RSSI技术
当无线信号在大气环境中传播时， 由于多种因素影响， 信号强度会随着其传播距离的增加而衰减。这表明，信号强度变化与传播距离间存在着某种函数关系，且通常情况下传感节点均可很容易配置测定接收信号强度的模块[5]，这就是RSSI测距技术。其特点是随着节点间距离的增大（或减小），两者之间的信号强度变弱（或变强），RSSI数值变小（或变大）。
1.2 APIT方法
依靠于无线传感器网络未知节点密度较高及无线信号的传播特性的特点，APIT算法可判断未知节点是否位于由三个信标节点组成的三角形内部[6]。一般情况下，根据接收到的信号强度的大小变化判断是否同时靠近或是远离某个信标节点。在APIT算法中，未知节点与任一邻居节点作相对于信标节点的位置比较来达到PIT中节点移动的效果。如图1所示，若未知节点[X]通过与邻居节点1交换信息，获知如果未知节点[X]移动到节点1处，不会同时靠近或是远离信标节点[A、][B、][C，]故未知节点[X]位于信标节点[A、][B、][C]组成的三角形内部；反义，若未知节点[Y]通过与邻居节点2交换信息，获知如果未知节点[Y]移动到节点2处，将同时靠近或是远离信标节点[A、][B、][C，]故未知节点[Y]位于信标节点[A、][B、][C]组成的三角形外部。
1.3 传统质心算法
质心算法（Centriod Algorithm）是一种基于距离无关（Range?free）的节点定位算法，仅仅通过网络的连通度，节点就可以实现粗糙的定位，并且定位过程不需要其他的外在硬件设备[7]。它的基本原理是假设未知节点可接收到[n]个信标节点的位置坐标信息，则认为该未知节点位于这[n]个信标节点组成的多边形的质心。其具体的定位过程为：定位初始阶段，信标节点每间隔一段时间就广播自身的数据包，其中包括自身的ID和位置坐标信息；未知节点持续监听且接收来自信标节点的数据包，当未知节点在一段时间内所接收到的信标节点数据包的数量超过预先设定的阈值（或一定时间），计算得出此未知节点所接收到的所有信标节点组成的多边形的质心位置，最后将质心位置作为此未知节点的估计位置。
2 误差分析
2.1 信标节点随机分布
质心算法的优点在于仅需利用网络的连通度就可定位，实现简单，无需测量节点之间的距离或是角度信息，但是其定位精度很大程度上受到信标节点分布和密度的影响。文献[8]证明了在信标节点分布均匀的情况下，可以达到要求较好的定位精度；然而当信标节点随机分布时，信标节点的分布并不均匀，未知节点的估计位置会向信标节点密度较大的方向偏移，定位精度大幅下降。并且，无论信标节点是随机分布还是均匀分布，定位误差都会随着信标节点数量的增多而下降；此外，信标节点随机分布的定位精度总是小于均匀分布的定位精度，且往往达不到精度要求。如图3所示，当信标节点[A，][B，][C，][D，][E]分布不均匀的时候，根据传统质心算法得出的未知节点[M]的估计位置[M]明显偏于信标节点数量多的一侧。
2.2 中心化问题
传统质心算法中，通常存在中心化问题。所谓中心化问题，就是无论未知节点位于信标节点组成的多边形的何处，都笼统地认为未知节点位于此多边形的质心位置。为简化说明，以信标节点组成的多边形为三角形的情况进行分析[9]。如图4所示，无论未知节点[M]实际位于[△ABC]内部何处，传统质心算法都认为估计位置[M]为未知节点的所在位置。
3 本文改进算法
根据距离与RSSI数值成反比关系的特点，本文将在每个传感器节点中嵌入信号接收强度分析模块，解决信标节点随机分布与中心化问题。
3.1 最佳三角形的选择
合理选择未知节点通信半径范围内信标节点组成的三角形，可以解决其估计位置向信标节点密度较大方向偏移的问题。但是，若未知节点的通信半径范围内存在[n]个信标节点，则其周围存在[C3n]个三角形，如何选择未知节点通信范围内的最佳三角形是本文研究的重点。
通过大量理论实验分析，本文得出了未知节点周围最佳三角形的判决条件：
（1） 未知节点必须位于此三角形的内部，可利用APIT方法进行验证；
（2） 未知节点分别接收三个信号节点的信号强度数值的差值应小于一定阈值阈值的大小可根据定位精度要求人为设定：
[RSSI1-RSSI2≤ηRSSI1-RSSI3≤ηRSSI2-RSSI3≤η] （1）
式中：RSSI分别表示未知节点接收来自信标节点1、2、3的信号强度数值；[η]表示根据定位精度要求而人为设定的阈值。
若同时满足上述两个条件，未知节点就可确定其通信半径范围内的最佳三角形，则最佳三角形的质心位置就认为是未知节点的估计位置。如果存在多个最佳三角形，则分别求出多个最佳三角形的质心，再对这些质心求算术平均，其平均值就认为是未知节点的估计坐标。
如图5所示，[M]为未知节点实际位置，信标节点[A，][B，][C，][D，][E]均在其通信半径范围内，[M]为多边形[ABCDE]的质心。为了确定未知节点[M]周围的最佳三角形，具体步骤如下：首先，未知节点[M]判断其周围存在[C35=]10个三角形；其次，根据条件（1），利用APIT方法得出未知节点[M]只位于[△ABE]与[△ACD]内部；然后，分别计算未知节点[M]接收来自信标节点[A，][B，][E]与信标节点[A，][C，][D，]两两信号强度的差值，利用式（1），判断其差值是否小于阈值。就图5而言，[MA，][MB，][ME]之间的距离误差较小，其RSSIMA，RSSIMB，RSSIME数值也接近，因此选择[A，][B，][E]这三个信标节点的两两信号强度的差值更小，其定位精度最高。从图5可以看出，[M1]为[△ABE]的质心，[M2]为[△ACD]的质心，若将[M1]的位置作为[M]点的估计坐标，误差明显小于以[M2]作为[M]点的估计坐标。
3.2 缩小三角形的范围
为了解决未知节点周围不存在最佳三角形的情况，本文提出了缩小与其距离较近的一个特定三角范围的办法来提高定位精度，具体步骤如下：
（1） 在未知节点周围不存在最佳三角形的情况下，通过比较接收未知节点信号强度数值的大小，选择其中三个最大（较大）值，即选取离未知节点最近（较近）的三个信标节点；
（2） 利用APIT方法判断未知节点是否位于这三个信标节点组成的三角形内部，若不满足则返回到步骤（1）中继续寻找合适的三角形，直到满足条件为止；
（3） 以满足条件的三角形的三边为信标节点移动的轨迹，缩小此三角形的范围，改变质心位置，解决中心化问题。
如图6所示，在未知节点[U]周围选择了一个满足上述条件的[△ABC，]其中[A，][B，][C]为信标节点。固定信标节点[B，][C，]移动信标节点[A。]先在[AB]边上向着信标节点[B]以一定的速率移动。若移动过程中，未知节点[U]收到的RSSI值变大，则继续移动；若变小，不再移动。这样就可以在直线[AB]上找到一点[A，]使得[A]点到未知节点[U]的RSSI值最大，故[A]点到未知节点的距离越近。以相同的方法，可在[BC]边上找到一点[B，]在[CA]边上找到一点[C。]连接[ABC，]形成一个新的三角形。在图6中，[U]为未知节点的实际位置，[U]为原三角形质心，[U]为移动信标节点之后，即迭代一次之后，新三角形的质心。将新三角形质心坐标作为未知节点的坐标，不仅缓解了中心化问题，并且也提高了定位精度。也可以利用同样的方法继续缩小新[△ABC]的范围，依次循环，一直缩小三角形的范围。当满足定位精度要求时（或是迭代次数时），将最后一个小三角形的质心作为未知节点的坐标。
4 仿真验证与分析
（2） 不同的信标节点数量
其他仿真参数不变，分别在信标节点的数量为10～50情况下比较两种算法的性能。
如图9所示，当节点总数不变时，信标节点数量的增加会导致网络连通度的增大，未知节点可参考到的信标节点数量增多，未知节点越趋近于信标节点组成的多边形的质心，所以本文改进算法与传统质心算法的平均定位误差都会随着信标节点数量的增加而降低。但是可以看出，当信标节点数量相同时，本文改进算法的平均定位误差明显低于传统质心算法，而且当信标节点数量较少时，本文改进算法的平均定位精度也明显优于传统质心算法。因此，相比于传统质心算法，本文改进算法降低了定位误差，提升了定位精度。
（3） 不同通信半径
最后改变节点的通信半径，对两种算法进行性能比较，如图10所示。通信半径[R]分别取20，25，30。
从图10可以看出，当信标节点数量一定时，随着节点通信半径的不断增大，本文改进算法的平均定位误差也在降低。这是因为节点通信半径的增大会提升网络的连通度，未知节点可参考到更多的信标节点，其位置就越趋近于信标节点组成三角形的质心，定位精度就会相对准确。
5 结 语
节点定位技术在无线传感器网络中的定位至关重要，是检测事件位置发生的基础。与传统的质心算法相比，本文改进算法以解决传统质心算法普遍存在的信标节点分布不均与中心化问题为目的，有效地降低了传统算法中存在的误差。仿真结果表明，改进算法的定位误差明显低于传统质心算法，定位精度可满足实际需要。这就意味着，本文的改进算法更加实际且准确地反映了网络的状况，对于节点随机部署、大规模的无线传感器网络节点定位来说，符合无线传感器网络的基本要求，是一种有效的解决办法。
参考文献
[1] 马祖长，孙怡宁，梅涛.无线传感器网络综述[J].通信学报，2004，25（4）：114?124.
[2] 史跃飞，冯秀芳，高昊.一种基于动态锚节点的改进加权定位算法[J].计算机应用与软件，2013，30（10）：151?154.
[3] 彭宇，王丹.无线传感器网络定位技术综述[J].电子测量与仪器学报，2011，25（5）：389?399.
[4] 赵雁航，钱志鸿，尚小航，等.基于跳距修正粒子群优化的WSN定位算法[J].通信学报，2013，34（9）：105?114.
[5] 刘峰，章登义.基于RSSI的无线传感器网络质心定位算法[J].计算机科学，2012，39（6）：96?98.
[6] 徐小玲，张福强，李少彪.基于APIT的无线传感器网络质心算法研究[J].传感器与微系统，2011，30（7）：57?63.
[7] 刘皇保，王涛，彭刚.一种改进的质心定位算法[J].微型机与应用，2013，32（11）：73?75.
[8] 李兆斌，魏占祯，徐风麟.无线传感器网络增强的质心定位算法及性能分析[J].传感技术学报，2009，22（4）：563?566.
[9] 衣晓，王梓，薛兴亮.一种基于次锚节点的无线传感器网络质心定位算法[J].计算机应用与软件，2013，30（6）：116?120.
[10] 白进京，严新平，张存保，等.基于加权质心和DV?Hop混合算法WSN定位方法研究[J].计算机应用研究，2009，26（6）：2248?2250.
