权重和误差双修正的质心定位算法

(桂林航天工业学院自动化系，广西 桂林 541004)

0 引言

节点定位算法主要基于测距和非测距[1-3]。基于测距是通过测量节点间的距离或角度，使用三边(角)测量或最大似然估计法[4]计算。例如：接收信号强度法[5]、信号传输时间(差)法、信号角度法等。基于非测距是依据网络连通性等信息计算，例如：质心算法[6]、APIT算法[7]、DV-hop算法[8]等。

文献[9]将离未知节点最近的信标节点作为修正节点；文献[10]提出优选信标节点进行加权质心；文献[11]根据信标节点与未知节点的距离关系，调整加权系数；文献[12]对信标节点与未知节点的接收信号强度指示(received signal strength indication,RSSI)测距进行加权平均。以上方法都是以RSSI测距为基础，增加质心算法和距离权重，测距误差和距离权重直接影响定位精度。本文提出一种对距离权重和测距误差进行双修正的质心定位算法，提高定位性能。

1 算法模型

1.1 加权质心算法

利用权重因子体现各信标节点对质心位置的影响程度，反映它们之间的内在关系。

信标节点与未知节点的质心关系如图1所示。图1中，B1(XB1,YB1)、B2(XB2,YB2)、B3(XB3,YB3)分别为三个信标节点，D为未知节点。

图1 加权质心示意图

(1)

(2)

(3)

(4)

(5)

1.2 距离权重修正模型

利用加权质心定位算法，可以获得未知节点的一个位置预测，但是这种预测的位置仅反映质心三角形中未知节点和两个信标节点总的距离关系。实际上，两个信标节点与未知节点的实际距离不可能是完全一致的，且对未知节点的权重影响也该是有差异的。离未知节点越近的信标节点获得的距离权重越大，离未知节点越远的信标节点获得的距离权重越小。

为了完善距离权重差异化的作用，提出的改进算法首先修正距离权重，增加权重修正系数K1、K2、K3。

修正后，信标节点与未知节点的距离和权重修正系数成反比。

坐标权重修正式如下：

(6)

(7)

综合x，y坐标，可得距离权重修正式：

(8)

1.3 测距误差修正模型

达到距离权重修正模型的修正效果，必须要有预测测距的基础，而实际应用中由于环境影响和硬件限制的原因，RSSI测距不能保证足够的精确，测距误差较大。针对这一问题，改进算法从修正信标测距入手，减小RSSI测距误差影响。

(9)

误差因子αDBi的取值直接影响测距误差。如果能找到离未知节点足够近的信标节点作为修正节点，得到修正节点与其他任意一个信标节点的真实距离和RSSI测距，那么就可以得到关于这个修正节点的误差因子。由于未知节点和这个修正节点位置很接近，测距误差影响几乎相同，所以可以利用修正节点的误差因子代替未知节点的误差因子。

修正节点误差修正示意图如图2所示。

图2 修正节点误差修正示意图

取离未知节点最近的信标节点作为修正节点。从图2可以发现，距离未知节点D最近的信标节点为B0，则将其作为修正节点。

由于B0和B1都是信标节点，可以根据实际坐标精确得到两者之间的实际距离dB1B0。

(10)

(11)

αB1B0替代未知节点D与信标节点B1之间的误差因子αDB1：

αB1B0=αDB1

(12)

得到未知节点D与信标节点B1修正测距值：

(13)

同理可得另外两个误差因子αB2B0、αB3B0。

将误差因子αB1B0、αB2B0、αB3B0代入距离权重修正式，得到测距误差修正公式：

在同等测距误差影响下，误差因子αBiB0的修正可以有效修正测距误差的影响。

在实际环境中，如果未知节点与某一个(或几个)信标节点的通信范围超出了修正节点与信标节点的通信范围，那么就找不到对应的修正误差因子。这种情况下，就需要寻找次修正节点来保证未知节点与信标节点、修正节点与信标节点的通信范围是有交集的。如果仍然找不到交集，则取消修正。两次修正可以降低未修正测距误差的概率。同理，如果对精度要求严格，可以进行多次修正节点尝试。

2 算法步骤

质心定位算法的具体步骤如下。

① 信标节点周期性发送节点ID、自身位置信息P。

② 未知节点统计可通信范围内的信标节点集合ωΒ={Β1,Β2，…,Βn}，并选取同一个信标节点的多次RSSI均值作为当前信标节点与自身通信的RSSI值。

④ 未知节点选择集合ωΒ中RSSI值最大的三个信标节点构成质心三角形，结合距离权重系数得到权重修正预测位置。

⑥ 将修正误差因子代入测距误差修正式，得到基于距离权重和测距误差双修正的质心算法，最终得到较为精确的未知节点位置。

3 仿真结果与分析

利用Matlab仿真试验平台比较改进算法与传统加权质心算法的性能。节点随机分布在100 m×100 m的区域内，未知节点的位置随机产生，信标节点均匀随机分布。

从以下三个方面来衡量改进算法的效果。

① 以预测位置和实际位置的差异来衡量，距离权重和测距误差双修正质心算法的节点位置仿真结果如图3所示，加权质心算法节点位置仿真结果如图4所示。

从图3和图4可以看出，距离权重和测距误差双修正质心算法得到的未知节点的预测位置与实际位置之间的距离明显小于加权质心定位算法。

图3 双修正质心算法仿真图

图4 加权质心算法仿真图

② 从权重修正系数对平均定位误差的影响程度来衡量。定位误差指的是通过定位计算得到的未知节点的估计位置与实际位置的偏差。这种偏差可以用两者之间的欧氏距离除以节点的通信半径来衡量，最后，利用平均定位误差来衡量定位算法的优劣。

平均定位误差与修正系数关系图如图5所示。

图5 平均定位误差与修正系数关系图

计算节点定位误差为：

(14)

对N个未知节点的定位误差求平均，得到平均定位误差：

(15)

为了简化模型仿真，这里假设权重修正系数K1=K2=K3=K，平均定位误差随着权重修正系数的改变而不断变化。在K=5附近，达到最小平均定位误差。

③ 为了方便衡量测距误差对定位误差的影响，取测距误差范围在REi∈[0,+30%]变化。如果将待测区域划分成若干个范围比较小的子网络(例如：5 m×5 m)，那么可以认为子网络内的测距误差因子是不变的。

测距误差与定位误差关系图如图6所示。

图6 测距误差与定位误差关系图

从图6可以看出，随着测距误差的增大，未知节点的平均定位误差也随之增加，这是因为测距误差的增加使得距离权重影响误差加大，造成定位精度下降。采用距离权重和测距误差双修正质心算法可以减少测距误差带来的影响。测距误差越大，其误差修正的作用就越强。

4 结束语

本文在加权质心定位算法的基础上，利用距离模型对距离权重进行调节，为距离权重匹配修正系数。利用修正节点与信标节点的RSSI测距误差因子，校正未知节点与信标节点的RSSI测距误差因子，强化了信标节点与未知节点间距的权重影响，减少了RSSI测距带来的误差影响，提高了未知节点的定位精度。

质心定位算法不需要节点之间进行复杂的协调过程，算法复杂度也只比质心算法略有增加，具有良好的可扩展性，可以满足传感器网络中对位置精度不太苛刻的应用。

[1] Jonathan B,Adam M,Adam M.Localization in sensor networks[M].Handbook of Sensor Networks:Algorithms and Architectures.USA:Wiley-Interscience,2005:277-310.

[2] Rampatzis A,Lygeros J,Manesis S.A survey of applications of wireless sensors and wireless sensor networks[C]∥Proceedings of the 2005 IEEE International Symposium on,Mediterrean Conference on Control and Automation,2005:719-724.

[3] Akyildiz I,Su W,Sankarasvbramaniam Y.A survey on sensor networks[J].IEEE Communications Magazine,2011,40(8):102-l14.

[4] 温立.无线传感器网络定位技术研究[D].上海：复旦大学,2008:34-37.

[5] Luthy K A,Grant D,henderson T C.Leveraging RSSI for robotic reapair of disconnected wireless sensor networks[C]//2007 IEEE International Conference on Robotics and Automation.Rome,Italy,2007:10-14.

[6] Nirupama B,John H,Deborah E.GPS less low cost out door localization for very small devices[J].IEEE Personal Communications,2000,7(5):28-34.

[7] Niculescu D,Nath B.DV based positioning in Ad Hoc networks[J].Journal of Telecommunication Systems,2003,22(4):267-280.

[8] He T,Huang C,Blum B M,et al.Range-free localization schemes for large scale sensor networks[C]//ACM International Conference on Mobile Computing and Networking(MobiCom).San Diego,California,USA:ACM Press,2003:81-95.

[9] 程伟,史浩山,王庆文.基于差分修正的传感器网络加权质心定位算法[J].系统仿真学报,2012,24(2)：389-393.

[10]赵昭,陈小惠.无线传感器网络中基于RSSI的改进定位算法[J].传感技术学报，2009,22(3):391-394.

[11]胡咏梅,张欢.一种改进的无线传感器网络质心定位算法[J].计算机工程与科学,2012,34(2)：45-49.

[12]Blumenthal J,Grossmann R,Golatowski F,et al.Weighted centroid localization in Zigbee-based sensor networks[C]//IEEE International Symposium on Intelligent Signal Processing,WISP 2007.USA:IEEE,2007:1-6.