基于次锚节点的无线传感器网络改进加权质心定位算法

张先超，刘兴长，张春园

(后勤工程学院 后勤信息与军事物流工程系，重庆401311)

0 引 言

无线传感器网络(wireless sensor networks，WSNs)是由随机部署在目标区域内的数量巨大的离散传感器节点组成，通过无线通信方式形成的一个多跳的自组织网络系统［1］。节点的位置信息对无线传感器网络十分重要，是其支撑技术，并且具有广泛的应用［2］。研究提高定位精度是当前无线传感器网络研究的热点［3～7］。

无线传感器网络的定位技术可分为两类:基于测距(range-based)的技术和无需测距(range-free)的技术［8］。到达时间差(time difference of arrival，TDOA)测距技术广泛应用于无线传感器网络定位，在不考虑非视距(NLOS)误差的情况下可取得较高的测距精度［9］。基于TDOA 测距的粒子群优化(PSO)无线传感器网络定位算法可比较准确地估计节点位置，但需要额外测距设备，增加了节点能耗。基于接收信号强度指示(RSSI)的加权质心算法通信开销小，算法简单［10］，但定位覆盖率和定位精度受锚节点数目影响较大。

本文提出了一种基于次锚节点的改进加权质心定位算法(IWCLA-SAN)，以克服加权质心定位算法(WCLA)对锚节点数量要求较高和定位精度较低的缺陷。

1 粒子群优化定位算法

文献［11，12］将粒子群优化算法应用于无线传感器网络定位中，验证了该定位算法的可靠性。粒子群优化算法的实现原理如下:

假设在D 维的搜索空间内，存在一个种群大小为M 的粒子群，即无线传感器网络中的锚节点;存在一个数量为N的搜索目标群，即无线传感器网络中的未知节点。每个粒子在空间中的位置坐标xi=(xi1，xi2，…，xid)，搜索速度vi=(vi1，vi2，…，vid)，搜索到的个体最优位置为pi=(pi1，pi2，…，pid)，搜索到的全局最优位置为gb=(gb1，gb2，…，gbd)，其中，i=1，2，…，M，d=1，2，…，D。该算法采用下列公式对粒子操作

学习因子c1和c2是非负的常数，常设c1=c2=2;r1和r2是介于［0，1］的随机数;w 为惯性权重，用来保持局部搜索和全局搜索的平衡，较大的w 有利于算法的全局搜索能力，较小的w 有利于算法的局部搜索能力;vid∈［-vmax，vmax］，vmax太大容易使粒子飞离最优解，vmax太小容易使粒子陷入局部最优，粒子的速度通常设为每维变换范围的10%～20%;k 为当前迭代次数，T 为终止迭代次数;f 为适应度函数，di为未知节点到各锚节点的距离;锚节点的坐标Ai(xi，yi)，未知节点坐标Nj(xj，yj)，其中，i=1，2，…，M，j=1，2，…，N。

2 测距原理与质心定位算法

2.1 RSSI 测距原理

节点在通信时可以直接获取RSSI 值，估计出未知节点与锚节点的距离。针对室外定位环境，文中采用自由空间传播模型(free space propagation model)和对数—常态分布(log-normal distribution)模型，用于分析和仿真［13］。自由空间模型无线信道的数学模型如下

对数—常态分布模型无线信道的数学模型如下

式中 PL(d0)为距离锚节点d0处的信号强度;PL(d)为距离锚节点d 处的信号强度;d 为未知节点与锚节点之间的距离;f 为频率;d0为参考距离，一般取为1 m，将d=1 m 代入式(6)得到Loss，即PL(d0)的值;n 为信道衰减指数，一般取值2～4;Xδ为均值为零、方差δ 的高斯随机噪声变量。

通常情况下，测距误差随着测量距离的增加而增大［14］，即较大的RSSI 值计算得到的距离值误差较小，而较小的RSSI 值计算得到的距离值误差较大。

2.2 质心定位算法

图1 CLA 示意图Fig 1 Schematic diagram of centroid localization algorithm

2.3 WCLA

WCLA 通过对不同的锚节点赋予不同权值，达到了提高定位精度的目的。通常加权值是未知节点到锚节点距离的函数［15］，一般将未知节点与锚节点距离的倒数作为加权值，得到加权质心定位算法，其计算公式为

式中 (xi，yi)为锚节点的坐标，wi为加权因子，di为未知节点到锚节点的距离，i=1，2，…，n。

2.4 IWCLA

为了更加体现未知节点到通信范围各锚节点距离对定位精度的影响，提出一种修正系数不固定的IWCLA。该算法对加权因子进行改进，设其为

其中，k 为修正系数，设定为

其中，D 为未知节点到通信范围内锚节点距离集合元素方差的归一化值，D 值的大小反映了未知节点通信范围内各锚节点分布的均匀程度，分布越均匀D 值越小。根据D 值的不同设定k 的值，使得计算不同未知节点的坐标时，修正系数k 的值不同。如图2 所示，对于锚节点分布均匀程度不同的两种情况，图2(a)的k 值大于图2(b)的。本文根据通信范围内各锚节点分布的均匀程度设定k 值，这样更能增加距离未知节点较近的锚节点的权重，减少距离较远的锚节点的权重。因此，与WCLA 相比，定位精度进一步提高。

2.5 IWCLA 描述

IWCLA 的定位步骤如下:

1)锚节点周期性发送自身节点ID 和自身节点位置信息，与邻居节点进行通信。

图2 锚节点分布图Fig 2 Diagram of anchor nodes distribution

2)未知节点收到锚节点信息后，分别记录同一个锚节点的RSSI 均值。

3)根据公式(6)计算出未知节点到各锚节点的距离di。

4)当未知节点接收到的锚节点信息达到阈值N 时，建立以下3 个集合:

锚节点集合Sbeacon={a1，a2，…，an};锚节点位置集合Sposition={(x1，y1)，(x2，y2)，…，(xn，yn)};未知节点到锚节点的距离集合Sd={d1，d2，…，dn}。

5)对未知节点到锚节点的距离集合中的各元素按从小到大依次排序，组成新的集合;对应的新的锚节点位置集合。由2.1 节分析可知，距离值越小，测距越准确，故优选距离值较小的锚节点估计未知节点坐标，以提高定位精度。

7)根据公式(7)计算出未知节点的坐标(X，Y)。

2.6 仿真与分析

利用Matlab 软件进行仿真。设锚节点数量为M，未知节点数量为N，锚节点和未知节点均随机分布在室外100 m×100 m 的区域内;通信半径r=30 m;信道衰减指数n=3.2，高斯随机噪声变量Xδ的标准差取为4，不考虑NLOS 误差对定位结果的影响。

设锚节点数目为50，未知节点数目为20。图3 为三种算法的定位误差，对于大多数未知节点，IWCLA 的定位误差明显低于其它两种CLA。

设定不同的锚节点个数，在每种锚节点个数情况下，独立进行30 次实验求出平均定位误差。图4 反映了三种定位算法平均定位误差与锚节点数目关系。锚节点数目越多，三种定位算法的平均定位误差越小，且IWCLA 定位效果始终优于另外二种定位算法。

图3 各未知节点的定位误差Fig 3 Positioning error of each unknown node

图4 锚节点数目对定位精度的影响Fig 4 Influence of number of anchor node on positioning precision

3 IWCLA-SAN

3.1 算法描述

锚节点的数量对IWCLA 的定位精度和定位覆盖率有很大影响，但带有GPS 的锚节点造价是普通节点的10 倍，不适宜大规模部署。为了提高IWCLA 的定位精度和定位覆盖率，本文将基于TDOA 测距的粒子群优化定位算法的未知节点升级为次锚节点(SAN)，再采用IWCLA 对其它未知节点进行定位。

3.2 仿真与分析

设锚节点数量为M，SAN 数为R，未知节点数量为N，锚节点、SAN 和未知节点均随机分布在室外100 m×100 m的区域内;通信半径r=30 m;信道衰减指数n=3.2，高斯随机噪声变量Xδ的标准差取为4，不考虑NLOS 误差对定位结果的影响。

在锚节点数目有限的情况下，研究加入SAN 对定位精度的影响。设锚节点数目依次为10，20，30，40，50;SAN 数目为20;未知节点数目为20。分别独立进行30 次实验，求出平均定位误差和定位覆盖率。由图5、图6 可知，IWCLASAN 与IWCLA 相比可以一定程度上提高定位精度和定位覆盖率。尽管将未知节点升级为SAN 会带来一定的误差累积，但基于TDOA 测距的粒子群优化无线传感器网络定位算法具有较高定位精度，将其作为SAN 具有一定可靠度。

4 结束语

图5 锚节点数目对定位精度的影响Fig 5 Influence of number of anchor node on positioning precision

图6 锚节点数目对定位覆盖率的影响Fig 6 Influence of number of anchor node on localization coverage rate

本文针对定位精度较低的缺陷，在加权因子中引入了修正系数;针对CLA 对锚节点数量要求较高的缺陷，为减少锚节点数量，降低成本，将基于TDOA 测距的粒子群优化无线传感器网络定位算法的未知节点升级为SAN。本文提出的IWCLA 定位精度相较于WCLA 有较大提高;在锚节点数目有限的情况下，加入SAN 可以提高定位精度和定位覆盖率。但本文并未考虑NLOS 误差对定位精度的影响，这需进一步研究该算法在NLOS 环境中的可靠性。

［1］ 宋 文，王 兵，周应兵，等.无线传感器网络技术与应用［M］.北京:电子工业出版社，2007:1-10.

［2］ 孙利民，李建中.无线传感器网络［M］.北京:清华大学出版社，2005:135-154.

［3］ Li F F，Luo F，Wang J X，et al.An effective self-adapting localization algorithm in wireless sensor networks［J］.J of Applied Mechanics and Materials，2011，58-60:1013-1017.

［4］ Jian L R，Zheng Y，Liu Y H.Beyond triangle inequality:Sifting noisy and outlier distance measurements for localization［C］∥Proc of IEEE INFOCOM 2010，San Diego:IEEE，2010:1-9.

［5］ Kung H T，Lin C K，Lin T H，et al.Localization with snap-inducing shaped residuals:Coping with errors in measurement［C］∥Proc of MobiCom 2009，Beijing:ACM，2009:333-344.

［6］ Li Z，Trappe W，Zhang Y，et al.Robust statistical methods for securing wireless localization in sensor networks［C］∥Proc of IPSN 2005，Los Angeles:IEEE，2005:91-98.

［7］ Zhang Q X，Di Q L，Xu G Y，et al.A RSSI-based localization algorithm for multiple mobile robots［C］∥Proc of CMCE 10，Changchun:IEEE，2010:190-193.

［8］ 李晓维，徐勇军，任丰原.无线传感器网络技术［M］.北京:北京理工大学出版社，2007:191-199.

［9］ 彭 宇，王 丹.无线传感器网络定位技术综述［J］.电子测量与仪器学报，2011，25(5):389-399.

［10］方 震，赵 湛，郭 鹏，等.基于RSSI 测距分析［J］.传感技术学报，2007，20(11):2526-2530.

［11］王晓乐，徐家品.基于粒子群优化算法的WSNs 节点定位研究定位［J］.计算机应用，2009，29(2):494-499.

［12］邢明彦，李腊元.粒子群优化算法在无线传感器网络中的应用［J］.计算机工程与应用，2009，45(32):72-74.

［13］陈维克，李文锋，首 珩，等.基于RSSI 的无线传感器网络加权质心算法定位［J］.武汉理工大学学报，2006，30(2):265-268.

［14］Chen W，Mei T，Sun L，et al.Error analyzing for RSSI-based localization in wireless sensor networks［C］∥7th World Congress on Intelligent Control and Automation，WCICA 2008，IEEE，2008:2701-2706.

［15］杨新宇，孔庆茹，戴湘军.一种改进的加权质心定位算法［J］.西安交通大学学报，2010，44(8):1-4.