您现在的位置： 首页 >> 技术支持 >> 基于三边测距和质心的三边质心网络定位算法
基于三边测距和质心的三边质心网络定位算法
无线传感器网络节点自身定位至关重要，在军事和民用领域中有着广泛的应用前景。文中针对传统的网络定位算法。提出的改进算法实验结果表明，算法能够有效地对节点进行定位、减少了误差率。
无线传感器网络的定位技术是无线传感器网络的研究热点。在无线传感器网络应用领域，有时需要知道节点的坐标位置信息。位置信息对于无线传感器网络的监测尤为重要。传感器节点监测的信息要与其坐标信息对应，才算完成了一个监测对象的确认，所以确认事件发生的位置是传感器网络中最基本的功能之一。但受到节点价格、体积、功耗以及硬件性能等因素的限制，造成节点自身定位仍然是一个问题。这也成为制约无线传感器网络技术发展的瓶颈。无线传感器网络的节点一般情况下是一个微型处理器。但由于节点体积小、价格高和电源供给有限等因素的影响，因此造成了节点自身的数据处理能力、通信能力和存储能力都有限。这些节点只能在自身通信范围内才能与其他节点进行通信。
文中针对传统的三边测距定位法的不足，提出了一种改进算法，即引入质心法，建立基于三边测距和质心的三边质心网络定位算法。实验结果表明，提出的改进算法能够有效地对节点进行定位，并且减少误差率。
1 传感器网络节点定位技术
在传感器网络中，节点定位技术就是无线传感器网络节点通过某种方法在基于已知节点位置信息的情况下来计算和确定未知节点或目标节点的坐标位置的技术。在应用中，只有知道节点的位置信息才能实现对目标信息的监测，这就需要监测到该事件的多个传感器节点之间的相互协作。只有正确的节点定位才是提供监测对象信息的前提。
在传感器网络应用场合中，节点的放置一般采取随机放置的方法。由于数目较多，不可能每个节点都要定位确定位置信息。所以通常采用对其中5％～10％的节点使用定位系统，一般的方法是采用GPS定位设备来获得自身的精确位置。目前研究的主要方向包括两个方面：(1)利用锚节点基于定位算法确认其他节点的位置，这些锚节点事先借助外部设备已经确定了自身位置。(2)事先设置好锚节点建立坐标系，其他节点随机摆放，然后再利用定位算法来计算未知节点的坐标位置。
1．1 基于距离的定位算法
基于距离的定位算法，就是要先测量锚节点和未知节点之间的距离，然后利用几何关系估算未知节点的坐标位置。解析几何中有多种方法可以确定空间中点的位置。任何可以确定某一点位置的几何学方法，只要有传感器提供足够的信息，均可成为定位方法。较为常用的方法是三边定位(Trilateration)和角度定位(AOA)。为提高定位精度，通常使用最小二乘法利用多边进行定位(Mulilateration)。使用角度定位需要测量接收信号夹角(AOA)，测量出夹角后，可使用不同的几何条件来求节点的位置。
1．2 三边定位法
在使用基于距离的定位技术时，需要多个锚节点的协作才能确定未知节点位置。用测量的一组数值建立数学方程，那么数学方程的个数会大于变量的个数，此时可使用极大似然法来获取最小均方差意义上的估计值。
在无线传感网络中，通常使用的坐标系是二维的，因此只要知道未知节点与3个锚节点的距离可以计算出未知节点的位置。
假设3个锚节点坐标分别为(X1，Y1)、(X2，Y2)、(X3，Y3)，未知节点的坐标(Xu，Yu)，未知节点距离3个锚节点的距离分别是R1、R2和R3，如图1所示，则根据二维坐标系距离公式可以得到如下方程组
综上所述，只要知道未知节点到3个锚节点的距离，就可定位未知节点，实际应用中可能得到未知节点到多个锚节点的距离，这便可以每次选取不同的3个点计算，最后对多次计算结果取平均值进而提高定位精度。
1．3 改进的三边测距定位算法
三边质心定位法将质心定位算法思想引入到三边测距算法中，通过计算相交圆的交点及由交点组成区域的质心来估计未知节点，使估算出的未知节点坐标准确度提高。设未知节点D的坐标(xd，yd)，A、B、C 3个信标节点的坐标分别为(xa，ya)，(xb，yb)，(xc，yc)，到D的距离分别为dad，dbd，dcd。则可得如下方程组
式（1）减式（3）；式（2）减式（3）后联立方程
可解得D点的坐标(xd，yd)。
三边测距算法确定未知节点坐标的思想如图2所示。
由于三边测距算法基于两条直线的交点来估算未知节点的坐标，未充分利用A，B，C 3个节点的坐标信息，使估算的未知节点的坐标可能存在较大误差。
在图3中，根据式(1)～式(3)可解出圆A与圆C的交点Mac1(xac1，yac1)和Mac2(xac2，yac2)，圆B与圆C的交点Mbc1(xbc1，ybc1)和Mbc2(xbc2，ybc2)；圆A与圆B的交点Mab1(xab1，yab1)，Mab2(xab2，yab2)。通过将圆A与圆C交点Mac1(xac1，yac1)，Mac2(xac2，yac2)代人式(x-x2)2+(y-y2)2，判断大小即可找出两点距圆B的圆心较近的点，假设为Mac1(xac1，yac1)。同理可找出圆B，圆C交点中距圆A较近的点设为Mbc1(xbc1，ybc1)，圆A，圆B交点中距圆C的圆心较近的点设为Mab2(xab1，yab1)，依据质心思想估算未知节点D的坐标为
从上述分析可知，若要对未知节点的定位误差进行补偿首先需要获得信标节点的坐标误差。获得信标节点坐标误差的过程中，由于取不同的3个信标节点做三边定位同样会得到不同的测量值，需要用这些测量值来得到最终的信标节点A0的计算坐标。文中采用加权质心算法来计算信标节点的计算坐标，如图3所示。
假设A01，A02，A03，…，A0n为A0坐标的多个不同测量值；A0’为A01，A02，A03，…，A0n的质心；d1，d2，…，dn为坐标A0到坐标A01，A02，A03，…，A0n的距离。
定义1 信标节点的计算坐标
为加权因子，表示坐标Aoi的权重，离质心A0’的距离越近，所占的权重则越大；xi为Aoi的X坐标值，yi为Aoi的Y坐标值所以信标节点的坐标误差为
式中，x为信标节点X坐标实际值；xc为信标节点计算坐标X值；y为信标节点Y坐标实际值；yc为信标节点计算坐标Y值。信标节点的坐标误差反映了系统针对该节点附近区域的定位能力。
然而在定位系统实际应用过程中，未知节点B未必恰好处于某个信标节点附近，而可能离各个信标节点距离相当，因此并不能按照理想情况直接用A0的坐标误差去补偿未知节点B的坐标误差。但是，每个信标节点所在区域的定位误差都可以通过信标节点坐标误差来反映，综合考虑所有信标节点坐标误差就可得到由信标节点所构成的区域定位误差，只要未知节点B处于该区域内，其坐标误差就可以用该误差进行补偿。这里的区域大小需根据网络不同的精度要求和节点密度来具体设定。如图2所示，当未知节点B处于由信标节点A1，A2，…，Ai构成的区域时，先通过RSSI值计算出这些信标节点和自身的距离，然后综合各个信标节点的的坐标误差可得出未知节点所在区域的定位误差。
定义2 未知节点校正误差
是加权因子，表示信标节点Aj的坐标误差对未知节点校正误差的决定权，从上述分析可知，信标节点Aj离未知节点的距离越近，所占的权重越大，m为用于坐标校正的信标节点个数。所以未知节点D最终坐标为
式中，xc1为未知节点加权质心法计算的X坐标；yc1为未知节点加权质心法计算的Y坐标。将质心算法所求的未知节点D的坐标代入式(10)中，即可更准确地估计出未知节点D的坐标。
2 仿真实验与分析
在Matlab仿真环境里，这3种算法均处于相同环境。节点个数都是50个节点其中38个锚节点和12个未知节点，坐标系为50 m×50 m，节点通信半径为100 m，图4～图7为部分仿真结果。
从实验结果可看出，文中提出的改进算法能够有效地对节点进行定位，并且减少了误差。