基于权重动态离散模型的WSNs定位算法*

刘 政

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



基于权重动态离散模型的WSNs定位算法*

刘 政*

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

针对测距误差和距离权重对定位误差的影响,提出一种离散距离权重动态修正的定位算法。算法首先分区域获取动态路径损耗指数,建立接收信号强度测距简化数学模型,抑制接收信号强度测距误差。然后将静态距离权重因子离散化,为离散距离权重匹配动态权重系数,并在划定的动态取值范围内寻找最优权重系数,权重系数与接收信号强度正相关。基于MATLAB平台仿真结果表明,与其他算法相比,该算法能够较好地抑制接收信号强度测距的误差影响,显著降低平均定位误差,提高定位精度。

无线传感器网络;定位算法;离散权重;动态路径损耗指数

无线传感器网络WSNs(Wireless Sensor Networks)是由大量的静止或移动的传感器节点以自组织和多跳的方式构成的无线网络。由于节点的通信能力和计算能力有限,节点之间的传感信息需要各个节点协作感知和计算,并将该信息在WSNs中共享,而节点定位是无线传感器网络的一项关键技术[1-3],目前的定位算法从定位手段上看主要有两大类:基于测距和非测距。基于测距是通过测量节点间的距离或角度信息,使用三边测量、三角测量或最大似然估计定位法[4]计算节点位置。常用的测距技术有:接收信号强度指示RSSI[5](Received Signal Strength Indication)、到达时间TOA(Time Of Arrive)、到达时间差TDOA(Time Difference Of Arrival)和到达角度AOA(Angle Of Arrival)等,非测距则不需要距离和角度信息,根据网络连通性等信息来实现节点定位。常用的非测距技术有质心算法[6]、近似三角形内点测试APIT(Approximate Point-in-Iriangulation Test)算法[7]、DV-hop算法[8]等。针对WSNs定位技术的研究已经有一些成果,文献[9]运用高斯噪声模拟路径衰减指数误差,根据信号强度对信标节点设定权重,抑制距离较远的信标节点的测距误差;文献[10]结合余弦定理,利用原有的信标节点定位信息构造出虚拟静态信标节点,优化信标节点数量;文献[11]通过分析接收信号强度的变化规律,利用均值和权重来降低环境因素对接收信号强度的影响;文献[12]以RSSI出现在区间每个距离点下的概率为权重对区间中的所有距离进行加权求和,建立能量和距离之间的映射关系;文献[13]统计RSSI测距和静态权重定位的实验数据,找出定位区域离散划分范围,提出高斯拟合动态权重定位算法。本文在已有研究基础之上,提出一种抑制RSSI测距误差的离散权重修正定位算法。算法结合传播路径损耗模型和对数-常态分布模型推算出RSSI与信标节点、待定位节点间距的简化计算模型,并对静态距离权重进行改进,强化较近距离信标影响力,弱化较远距离信标影响力,最终降低测距误差,提高定位精度。改进算法实现原理简单,不存在多维度矩阵的运算和复杂的迭代计算。

1 动态路径损耗指数的RSSI测距

信道的长距离衰落特性服从对数正态分布,受多径衰减、背景噪声和信标节点分布离散性影响,利用自由空间无线电传播路径损耗模型结合对数-常态分布模型计算信号传输的路径损耗更具合理性。

自由空间无线电传播路径损耗模型:

Loss=32.4+10n×lg(d)+10n×lg(f)

(1)

式中:Loss:信号传输d距离后的路径损耗;d:距信标节点的距离(单位:m);n:信号损耗系数,通常取2～4;f:传输信号的频率(单位:MHz)。

对数-常态分布模型如下:

PL(d)=PL(d0)+10n×lg(d/d0)+Xσ

(2)

式中:PL(d):信号传输d距离的路径损耗;d0:近地参考距离;PL(d0):信号传输d0距离后的路径损耗;n:路径损耗指数,范围在2～4之间;Xσ:平均值为0的高斯分布随机变数,标准差范围在4～10之间。

取d0=lm代入式(1)来计算Loss得到PL(d0)。

待定位节点收到信标节点的信号强度:

RSSI(d)=Pt-PL(d)

(3)

式中:RSSI(d):接收信号强度(单位:dBm);Pt:发射信号功率(单位:dBm);PL(d):路径损耗。

综合式(1)～式(3),经过IEEE 802.15.4简化的RSSI测距计算[14]:

(4)

式(4)的RSSI测距计算是基于路径损耗指数为常数的前提,但是如果区域环境变化影响较大,那么节点所处不同位置的路径损耗指数也不相同,利用式(4)计算的RSSI测距误差较大。为了弥补这种误差,可通过计算邻居信标节点间的RSSI值,先求出当前区域内的路径损耗指数。

将信标节点B1收到邻居信标节点B2、B3的RSSI值代入式(3):RSSI(dB1B2)=Pt-PL(d0)-10n×lg(dB1B2/d0)+Xσ

RSSI(dB1B3)=Pt-PL(d0)-10n×lgdB1B3/d0)+Xσ

(5)

由于信标节点的位置已知,故它们之间的间距dB1B2、dB1B3可以精确得到。

(6)

通过将式(5)中的RSSI(dB1B2)和RSSI(dB1B3)相减,得到路径损耗指数的算式:

(7)

将式(7)代入式(4),得到动态路径损耗指数的RSSI测距算式:RSSI(d)=

(8)

2 改进定位算法

2.1 加权质心定位原理

图1 加权质心原理

用3个信标节点B1,B2,B3与待定位节点D的不同距离作为权重因子对其质心定位,得到近似位置Pi(x,y)。

(9)

2.2 离散权重动态修正定位

拆分式(9)中的权重因子:

(10)

为了能够调节距离权重影响程度,在式(10)基础上增加权重系数K。

(11)

将式(11)代回式(9)得到修正式(12)。

(12)

由于权重系数K的取值能够调节距离权重,所以和测距距离有直接关系。从式(12)抽取任意一个信标节点Bs(x,y),利用最小函数值原理找出权重系数K的取值趋势。

(13)

式中:Pi,s(x,y)表示信标节点Bs(x,y)对待定位节点Di(x,y)的定位影响力。

(14)

(15)

(16)

文献[13]将定位区域划分为0.5 m×0.5 m的小方块单元,并对各个单元的离散权重系数进行统计,发现离散权重系数主要分布在1.5～2.0之间,比例达到80%以上,并且随着区域的扩大,权重系数为1.5的比例降低,权重为2.0的比例增长。借鉴文献[13]的实验统计结果,取权重系数K值范围在1～3.5之间,这种取值特点可以将定位区域进行粗分而不会降低太多的定位精度。

3 算法流程

①信标节点周期性发送包含节点ID、自身位置信息P的数据。②待定位节点在收到信标节点数据后统计RSSI值和信标节点位置信息P,对来自同一个信标节点的多次RSSI值先进行卡尔曼滤波再求均值作为最终RSSI值。③将RSSI值从大到小排序,建立RSSI集合RSSI={RSSIB1,RSSIB2,…,RSSIBn},取前3个作为邻居信标节点,计算邻居信标节点间的RSSI值,利用式(7)得到当前区域内的路径损耗指数n,代入式(8)得到RSSI测距距离。④利用高斯拟合函数对步骤⑤得到的距离进行过滤修正。⑤将从RSSI集合中选择的邻居信标节点构成如图1所示的质心三角形,如果不满足,则选择RSSI集合的第4个元素对应的信标节点,以此类推直到满足质心三角形。权重系数K在1～3.5之间选择,再由式(12)计算得到一组待定位节点位置坐标群。⑥由式(18)计算K分布在1～3.5之间对应的平均定位误差,K递增幅度0.1,找到误差最小对应的权重系数K值。⑦根据步骤⑥得到的K值,利用式(12)重新计算坐标,完成修正定位。

图2 硬件平台

4 实验结果与分析

4.1 RSSI(d)与d的高斯拟合

采用TI公司的CC2530作为WSNs定位节点(北京博创智联公司生产),2个待定位节点,10个信标节点,共12个节点,如图2所示。

设定1 m、5 m、10 m、15 m、20 m、25 m作为参考测量距离点,在每个距离点通过RSSI测距100次,利用式(8)算出一组RSSI(d)数据。再利用高斯拟合函数[13]对这组数据做高斯拟合修正处理,滤除一部分干扰数据,降低测距误差,如图3所示。

图3 RSSI与测距距离的高斯拟合

(17)

式中:d0和A是与距离和RSSI值有关系的待定系数,m为待定位节点接收到RSSI数据的信标节点个数。

图4为采用高斯拟合与均值拟合的误差比较,结果表明,待定位节点与信标节点的距离在10m到20m之间的误差波动较小,小于10m或大于20m的误差波动较大,整体上来看,高斯拟合对近距离的RSSI测距修正效果要明显优于均值拟合。

图4 拟合效果比较

利用MATLAB7.0进行仿真实验,网络参数设置:50个待定位节点和20个信标节点随机分布50m×50m的平面区域,节点的通信半径为20m。性能评价指标为平均定位误差,在同一网络环境下重复试验100次,对100次测距误差求均值。

归一化平均定位误差:

(18)

4.2 不同权重系数的定位结果比较

如图5所示,当权重系数K从1向3.5变化过程中,改进算法的平均定位误差有了明显的变化,当权重系数K为1时误差最大,达到28.1%,当权重系数K增加到1.9时,误差最低,仅为12.7%,这是一个逐渐降低的过程。当权重系数K大于1.9,误差逐渐升高。基本加权质心和静态加权质心的定位误差始终保持为31.3%和28.1%,这是因为这两种算法没有权重系数的动态调节。

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

4.3 不同信标节点个数的定位结果比较

信标节点个数的多少反应了当前WSNs中信标节点的分布密度,设定:初始信标节点个数从3个递增到12个,测距误差为25%。

如图6所示,随着信标节点数量的增加,3种算法的定位误差都有一定程度的下降,基本加权质心的平均定位误差从29.2%下降到23.9%,静态权重质心从22.5%下降到17.4%,改进算法从13.5%下降到9.05%。信标节点数量从3个增加到8个,定位误差下降明显,信标节点数量从8个继续增加到12个,定位误差下降趋势已经不明显,信标节点数量的增加对减小平均定位误差的作用逐渐弱化。

图6 信标节点个数与定位误差

4.4 不同测距误差的定位结果比较

测距误差直接影响到节点间距离测量值的准确度,进而会影响到定位结果的准确度。为了方便衡量测距误差对定位误差的影响,取测距误差在5%～35%范围之间变化。

从图7实验结果可知,随着测距误差的增大,3种算法的平均定位误差都随之增加,这是因为测距误差的增加使得距离权重误差影响加大,造成定位精度下降。当测距误差从5%增加到35%,基本加权质心的平均定位误差从17.5%增加到39.1%,静态权重质心从13.4%增加到27.5%,改进算法从9.1%增加到17.9%,相比较,改进算法抑制测距误差影响的效果最好。

图7 测距误差与定位误差

5 结论

本文利用动态路径损耗指数的RSSI(d)测距简化数学模型和高斯拟合修正,抑制RSSI测距误差,离散化静态距离权重,并为距离权重匹配动态权重系数。该算法不需要节点之间进行复杂的协调过程,算法复杂度也只比质心算法略有增加,具有良好的可扩展性,可以满足传感器网络中对位置精度要求不太苛刻的应用。下一步的改进思路:根据RSSI的衰减程度,为每一个不同距离的信标节点分配独立的权重系数,建立RSSI(d)与K、λ的精确数学模型。

[1]Rudafshni M,Datta S. Localization in Wireless Sensor Networks[C]//Information Processing in Sensor Networks(IPSN),2007:51-60.

[2]Arampatzis T,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]朱登科. 基于RSSI的无线传感器网络测距和定位技术研究[D]. 长沙:国防科技大学,2010.

[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(S1070-9916),2000,7(5):28-34.

[7]Niculescu D,Nath B. DV Based Positioning in Ad Hoc Networks[J]. Journal of Telecommunication Systems(S1572-9451),2003,22(1/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]陶金龙,康志伟,骆坚. 基于RSSI测距的加权概率定位算法[J]. 电子测量与仪器学报,2014,28(10):1123-1129.

[10]于海存,石为人,冉启可,等. 基于虚拟静态锚节点的加权质心定位算法[J]. 传感技术学报,2013,26(9):1276-1283.

[11]方震,赵湛,郭鹏. 基于RSSI测距分析[J]. 传感技术学报,2007,20(11):2526-2530.

[12]王缓缓,宫娜娜. 基于距离区间概率加权的RSSI测距方法[J]. 电子科技大学学报,2013,42(6):862-868.

[13]詹杰,刘宏立,刘述钢,等. 基于RSSI的动态加权定位算法研究[J]. 电子学报,2011,39(1):82-88.

[14]党小超,李小艳. 无线传感器网络节点定位加权校正模型[J]. 计算机应用,2012,32(2):355-358.

Localization Algorithm for Wireless Sensor Networks(WSNs) Based on Dynamic Discrete Weighted Model*

LIUZheng*

(Department of Automation,Guilin University of Aerospace Technology,Guilin Guangxi 541004,China)

Aiming at the effects of range error and distance weighted on positioning error,a locating algorithm based on dynamic correction of discreet distance weighted is proposed. Firstly,the algorithm accesses the dynamical path loss exponent based on regional division,establishes the simplified mathematical model of RSSI range,and suppresses the RSSI measurement error. Then the static distance weighted factors are discretized and the dynamic weighted coefficient of discreet distance weighted is matched,meanwhile the optimal weighted coefficient within the dynamic scope is searched,weighted coefficient and RSSI has positive correlation. Simulation results based on MATLAB platform shows that this algorithm can decrease the influence of RSSI measurement error compared with other algorithms. The algorithm significantly reduces the average position error,and enhances the positioning accuracy.

wireless sensor network;location algorithm;discreet weighting;dynamic path loss exponent

刘 政(1981-),男,讲师,主要研究方向为无线传感器网络,智能仪器,davidbetty@163.com,liuz@guat.edu.cn。

项目来源:国家自然科学基金项目(61202007);广西教育厅科研项目(201106LX718);桂林航天工业学院基金项目(YJ1302)

2014-09-26 修改日期:2014-12-10

C:7230

10.3969/j.issn.1004-1699.2015.03.024

TP393

A

1004-1699(2015)03-0437-06