基于指数平滑预测模型的移动节点定位算法

单志龙， 王宣琳

(1. 华南师范大学计算机学院， 广州 510631； 2. 华南师范大学网络教育学院， 广州 510631)



基于指数平滑预测模型的移动节点定位算法

单志龙1,2*， 王宣琳1

(1. 华南师范大学计算机学院， 广州 510631； 2. 华南师范大学网络教育学院， 广州 510631)

针对无线传感器网络移动节点定位精度不足的问题，提出了一种基于指数平滑预测模型的移动节点定位算法，该算法利用指数平滑预测模型获得节点的速度信息和方向信息，然后根据节点的历史轨迹时间序列，应用H指数进一步精确采样区域，从而获得更接近于未知节点位置的高质量样本点． 此外，通过高质量样本点构建“有效样本点矩形盒子”，减少了节点采样次数． 仿真结果表明，改进算法在不同的运动速度、锚节点密度等条件下，均提高了定位精度，表现出了较好的性能．

指数平滑预测；H指数；R/S分析法； 矩形盒子； 定位

无线传感器网络[1](Wireless Sensor Networks, WSN)的定位技术应用最为广泛的一个领域是目标跟踪领域[2]，但是由于传感器大小、电能消耗和其他因素的限制，现实中对目标的跟踪面临着很多挑战． 如何在较少的成本及获得目标的精确位置之间取得平衡的定位算法成为了现今研究的一个热点问题．

根据是否使用测距信息可以将定位算法分为2类：基于测距的定位算法和无需测距的定位算法． 基于测距的定位算法往往需要借助特殊的硬件设备来测得接收信号强度(RSSI)、到达时间(TOA)、2种不同信号到达时间差(TDOA)和到达角度(AOA)等信息[3-6]等来辅助定位． 而无需测距的定位算法则不需借助特殊硬件设备，主要利用节点之间的连通度和多跳通信信息来进行定位，类似算法有质心算法[7]、DV-HOP算法[8]、APIT算法[9]、MDS-MAP算法[10]等．

由于传感器节点的移动性，在移动无线传感器网络中节点的定位比在静态网络中更具挑战性． 2004年，HU和EVANS[11]首次将粒子滤波算法运用于无线传感器网络移动节点定位中，提出了经典的蒙特卡罗算法(Monte Carlo Algorithm, MCL)． MCL算法假设所有的节点都是移动的，且节点知道自己的最大运动速度． 时间在MCL算法中被分割为一个个离散时间步，在每个时间步中所有的传感器节点都更新他们的位置，在获取较高定位精度的同时也保持了算法的简便性． 针对MCL算法的不足，学者们提出了各种改进的MCL算法：BAGGIO和LANGENDOEN[12]提出了蒙特卡罗箱定位方法(Monte Carlo Localization Boxed,MCB)，通过引入锚盒子的概念，将样本点限制在由锚节点通信重叠范围所组成的一个锚盒子内，使得算法采样的成功率及效率得到很大提高；考虑到当有很多锚节点存在时只需要少许采样点即可成功表征节点的位置分布，WANG等[13]提出了采样自适应蒙特卡洛定位方法(SAMCL)，可以自适应调整采样大小进而减少计算成本；ZHANG等[14]提出了基于权值的MCL算法，利用两跳邻居锚节点的负效应和传感器节点的估计位置信息来进一步减小MCB算法中所构建的锚盒子大小；YI等[15]结合了MCL算法、DV-Hop算法和MCB算法，提出了基于多跳的蒙特卡罗定位算法，该算法不需要在定位过程中知道节点的通讯半径，在节点密度较低时能够比较精确地定位；单志龙等[16]利用灰度预测模型来进行节点下一时刻的运动预测，同时在采样样本数不够时通过限制性线性交叉过程来生成新的样本点，加快样本的生成；王洁等[17]利用牛顿插值法、前n个时刻的历史轨迹来推测节点下一时刻的运动速度和方向大小，从而缩小采样区域，改善了MCL算法在低锚节点密度时的性能．

上述算法虽然从不同方面对MCL算法进行了相关改进，但是仍存在不同缺陷． 通常在无线传感器网络实际的应用环境中，物体的运动轨迹相对来说都较为规则，而需要跟踪的目标或者节点的运动轨迹也相对较平滑，一般不会产生一些不切实际的运动行为，如急速转弯或突然停止等状况． 根据这些特点，本文提出了一种基于指数平滑预测模型的移动节点定位算法(Index Smoothing Prediction based on Monte Carlo Localization Boxed,ISPMCB)，利用节点前几个时刻的历史位置信息，应用指数平滑模型让节点能够计算自身的位置、速度和方向，根据历史轨迹利用H指数进一步精确采样区域，加快高质量样本点的生成，受遗传算法和锚盒子思想启发，构建“有效样本点矩形盒子”进行重采样，大大减小节点可能的范围和采样的工作量，从而提高了节点的定位精度．

1 MCB算法分析

不同于MCL算法，MCB算法充分利用了产生样本前后锚节点的信息，通过约束MCL算法的采样区域，快速且更有效地产生样本粒子，减少被过滤的不符合条件的样本点．

在MCB算法中，每个节点都会通过建立一个能覆盖所有一二跳锚节点重叠区域的锚盒子来约束采样区域，在构建锚盒子〈(xmin,ymin),(xmax,ymax)〉后，以节点上一时刻位置Lt-1为中心构建采样盒边界：

(1)

在采样盒中采取到足够样本点后，根据所接收到的一二跳锚节点信息来滤除掉不符合条件的样本点，如果过滤后的样本数目不足，则进行重采样和过滤操作，直到过滤后的样本点满足给定的最大样本数，最后将所有样本点的均值作为待定位节点的估计位置(图1)．

图1 MCB采样盒

2 ISPMCB算法

2.1 指数平滑预测

在无线传感器网络中，节点的运动通常比较平滑，很少发生突变． 节点当前时刻的位置随时间变化而变化，但与历史节点位置相关联，离现在时间较近的数据比较远的数据影响更大，节点的历史运动轨迹可看作是一个基于位置的时间序列． 因此，利用指数平滑预测模型[18]中的平滑系数来进行数据信息处理，会使预测数值减弱异常数据的影响，显著体现历史数据当中包含的规律信息，从而可以更精确地预测对象的将来值． 本文使用了适用于平滑特性的单指数平滑预测模型[19]来预测节点的运动趋势，具体过程如下：

设前10个时刻节点历史位置坐标为y1,y2,…,y10，用S表示指数平滑值，一次指数平滑值计算公式如下：

(2)

由式(2)可估算出当前时刻节点的运动速度和方向为

(3)

则预测位置坐标可表示为：

(4)

2.2 H指数采样优化

如前所述，节点的历史运动轨迹可看作是一个基于位置的时间序列，在得出节点的运动速度和方向等运动信息后，基于前面时刻的历史位置时间序列，可应用H指数[20]来判断节点下一时刻位置对时间的依赖性，以此精确节点的采样区域，减少算法的迭代次数． 本文选取前面10个时刻的历史位置时间序列来判断，具体操作如下：当H=0.5时，时间序列之间的变量相互独立，历史的事件不会影响未来的事件发生，因此在节点运动方向上顺时针和逆时针各展开θ角度得到一个三角形或多边形采样区域；当0≤H<0.5时，表明时间序列的趋势是反持续性的，前后变量之间的关系负相关，则以上一时刻为原点，vt为半径，顺时针展开(1/2)θ角，逆时针展开(3/2)θ角得到一个三角形或多边形采样区域；当0.5

图2 节点采样

本文使用R/S分析法[21]来计算H指数． 假设有时间序列{X1,X2,…,Xn}，其均值、累积离差、极差、标准差分别为：

(5)

(6)

(7)

(8)

R(n)与S(n)的比值满足[22]：

(9)

其中a和H(即H指数)均为常数，

(10)

对log(R(n)/S(n))与loga进行最小二乘法回归，则可以估计出H指数的值．

2.3 加权滤波

在滤波过程中，节点根据当前所接收到的一跳锚节点和二跳锚节点信息过滤掉那些不可能存在的样本点． 根据上一时刻估计位置的一跳锚节点集合S1和二跳锚节点集合S2来对所采样本进行过滤，滤波表达式如下：

{∀s2S2,r

(11)

同时，为了更好地表征样本点对未知节点位置估计的贡献，本文利用所采样本的所在位置与指数平滑预测模型的下一时刻预测值对所采样本加以不同的权重，即以上一时刻位置lt-1为起点、所采样本节点i为终点的向量Ui与以上一时刻位置lt-1为起点、指数平滑模型预测值p为终点的向量Pi之间的夹角大小对样本点赋予不同的权值wi，设Ui与Pi之间的夹角为，则权值可表示为：

wi=1/.

(12)

2.4 “有效样本点矩形盒子”重采样

经过上一步骤的滤波操作后，剩下的有效样本可能不足最大采样数N，取上一步所得到的所有有效样本点坐标中横坐标最小者和最大者分别为“有效样本点矩形盒子”的左边界和右边界，所有有效样本点坐标中纵坐标最小者和最大者分别为盒子的下边界和上边界，构建“有效样本点矩形盒子”，进行重采样操作，从而得到更多的有效样本点，提高定位效率． “有效样本点矩形盒子”表示如下：

(13)

在这个矩形盒子区域里面随机采样，假设经过滤波后剩下的有效样本点数目为x，则在这个矩形盒子区域中随机采2×(N-x)个样本点，再次滤波后若还不满足最大采样数目N，则继续在矩形盒子随机采样，直到收集到足够的有效样本点．

2.5 位置估计

在经过位置预测、过滤、重采样阶段后，最后根据滤波加权阶段的样本点权重进行位置估计，估计位置坐标如下：

(14)

3 仿真分析

算法仿真实验在MATLAB 2013平台上进行，并与MCB算法进行对比． 假设节点的通信半径为25 m，所有传感器节点随机分布在区域为250 m*250 m的正方形内，该区域不包括障碍物． 节点最大运动速度vmax=5 m/s，最小运动速度vmin=0 m/s，锚节点数目为40，未知节点数为1． 根据文献[23]，本文将有效样本数设置为50． 在1 次仿真中，迭代运行20次，取其平均定位误差作为仿真结果．

定位误差为所有节点真实位置(xt,yt)与估计位置(xest,yest)之间的平均距离再除以通讯半径r得出的商:

(15)

考虑到现实中的大多数运动轨迹是平滑的，因此本文假设所有节点都遵循高斯马尔科夫移动模型(Gauss-MarkovModel,GM)运动轨迹． 该模型能够比较恰当地模拟无线传感器网络中节点运动的情况，且可以较完整地覆盖定位区域，同时也能在一定的范围内减少网络中的开销． 移动节点不知道自身的速度和方向，每个节点也都会在[0,2π]范围内随机选择1个方向、在[vmin,vmax]范围内随机选择1个速度值进行移动．

图3展现了ISPMCB算法和MCB算法的未知节点在20个时间周期内的定位误差情况． 从图中可以看出，在节点定位的前10个时间周期中，ISPMCB算法和MCB算法采取了同样的定位方法，因此2个算法都表现出相同的趋势，定位误差也相差无几. 随着节点的不断移动，从第11个时间周期起，ISPMCB算法依然表现出跟MCB算法相同的趋势，但是定位误差明显小于MCB算法，充分展现了ISPMCB算法的优越性. 这是因为ISPMCB算法通过指数平滑预测模型得到节点下一时刻的相关运动信息，再进一步根据运动信息来利用H指数去精确采样区域，让样本更多地产生于后验概率较高的采样区域，从而得到高质量样本，提高了定位精度. 从图中也可以看出，ISPMCB算法的定位精度明显优于原始MCB算法，其定位精度比MCB算法约提高10%.

图3 定位误差随时间周期变化关系图

Figure3Variationoflocalizationerrorswithdifferenttimeperiods

在算法中，最大运动速度vmax对于采样效率会有2种不同的影响：当vmax比较小时，网络中有效的采样区域比较小，而所有的有效样本点都只能从这个有效采样区域中产生，因此节点的位置估计可能会不准确；当vmax比较大时，接收到的锚节点信息增多，可以覆盖更大的有效采样区域，使得高质量样本点产生几率增大． 如图4所示，2种算法表现出相似的变化趋势，但ISPMCB算法表现出更好的优势． 当vmax>1.2 m/s时，ISPMCB算法定位误差趋于稳定，这说明当vmax增大时，未知节点能够收到的锚节点信息增加，有效采样区域的扩大会产生高质量样本点，从而能够提高定位精度．

图4 定位误差随最大运动速度变化关系图

当锚节点密度越大时，未知节点可以充分利用一跳锚节点和二跳锚节点的信息，节点所获知的信息越多，得到的有效样本点也越多，定位精度也就越高． ISPMCB算法比MCB算法表现出更高的精度(图5)，这是因为ISPMCB算法利用H指数进一步精确了采样区域，且引入了“有效样本点矩形盒子”进行重采样，有利于生成较高质量的样本点，因此获得了较高的定位精度．

图5 定位误差随锚节点数量变化关系图

Figure 5 Variation of localization errors with different number of anchor nodes

通信半径是影响节点定位精度的一个重要参数，一般来说，节点通信半径越大，未知节点接收到的一跳和二跳锚节点信息越多，能够得到更多的观测信息，有利于筛选出更符合条件的样本点． 如图6所示，随着通信半径的增大，定位误差不断减小，但ISPMCB算法的定位误差表现优于MCB算法，这是因为ISPMCB算法充分利用了节点的历史位置信息，并有效构建了“有效样本点矩形盒子”，产生了高质量样本点，提高了节点定位精度．

图6 定位误差随通信半径变化关系图

Figure 6 Variation of localization errors with different communication radius

4 结语

本文根据节点在一定时间内的运动连续性，提出了基于运动模型的移动节点定位方法，利用指数平滑模型和H指数来获得后验概率密度值较大区域，从而加快高质量样本点的生成，提高了定位效率． 通过利用已生成的高质量样本点构建“有效样本点矩形盒子”，减少了节点采样次数，加快了算法的收敛． 此外，基于节点的运动轨迹优化了样本点权值，提高了定位精度． 在接下来的工作中，将研究不同的指数平滑模型与节点运动模型对算法的具体影响．

[1] 孙利民,李建中,陈俞. 无线传感器网络[M]. 北京:清华大学出版社,2005:4-45.

[2] XU E,DING Z,DASGUPTA S.Target tracking and mobile sensor navigation in wireless sensor networks[J]. IEEE Transactions on Mobile Computing,2013,12(1):177-186.

[3] DIL B,DULMAN S,HAVINGA P. Range-based localization in mobile sensor networks[M]∥RÖMER K,KARL H,MATTERN F. Wireless Sensor Networks. Berlin:Sp-ringer,2006:164-179.

[4] YU K,GUO Y J. Statistical NLOS identification based on AOA,TOA,and signal strength[J]. IEEE Transactions on Vehicular Technology,2014,58(1):274-286.

[5] ZHENG Y S,WANG H,WAN L,et al. A placement strategy for accurate TOA location algorithm[C]∥Proceedings of the 2009 Seventh Annual Communication Networks and Services Research Conference. Washington:IEEE,2009,34:166-170.

[6] VANKAYALAPATI N,KAY S,DING Q. TDOA based direct positioning maximum likelihood estimator and the cramer-raobound[J]. IEEE Transactions on Aerospace & Electronic Systems,2014,50(3):1616-1635.

[7] LIANG S C,LIAO L H,LEE Y C. Localization algorithm based on improved weighted centroid in wireless sensor networks [J]. Journal of Networks,2014,9(1):183-189.

[8] GRIBBEN J,BOUKERCHE A. Location error estimation in wireless ad hoc networks[J]. Ad Hoc Networks,2014,13:504-515.

[9] CHENG W H,LI J,LI H Z. An improved APIT location algorithm for wireless sensor networks[J]． Advances in Electrical Engineering and Automation,2012,139:113-119．

[10]YI S,RMNL W,ZHANG Y,et a1.Localization from mere connectivity[C]∥Proceedings of the 4th ACM International Symposium on Mobile Ad Hoe Networking & Computing. New York:ACM,2003:201-212．

[11]HU L,EVANS D. Localization for mobile sensor networks[C]∥Proceedings of the 10th Annual International Conference on Mobile Computing and Networking. New York:ACM,2004:45-57.

[12]BAGGIO A,LANGENDOEN K. Monte-Carlo localization for mobile wireless sensor networks[C]∥CAO J N,STOJMENOVIC I,JIA X H,et al. Mobile Ad-Hoc and Sensor Networks. Berlin:Springer,2006:317-328.

[13]WANG Y,LEDERER S,GAO J. Connectivity-based sensor network localization with incremental delaunay refinement method[C]∥Proceedings of the IEEE International Conference on Computer Communications. Rio de Janeiro:IEEE,2009:2401-2409.

[14]ZHANG S,CAO J,CHEN L,et al. Accurate and energy-efficient range-free localization for mobile sensor networks[J]. IEEE Transactions on Mobile Computing,2010,9(6):897-910.

[15]YI J,YANG S,CHA H. Multi-hop-based montecarlo localization for mobile sensor networks[C]∥Proceedings of the 4th Annual IEEE Communications Society Conference on Sensor,Mesh and Ad Hoc Communications and Networks (SECON). San Diego,CA:IEEE,2007:162-171.

[16] 单志龙,刘兰辉,张迎胜,等. 一种使用灰度预测模型的强自适应性移动节点定位算法[J]. 电子与信息学报,2014(6):1492-1497.

SHAN Z L,LIU L H,ZHANG Y S,et al. A strong self-adaptivitylocalization algorithm based on gray prediction model for mobile nodes[J]. Journal of Electronics & Information Technology,2014(6):1492-1497.

[17] 王洁,王洪玉,高庆华,等. 一种适用于移动传感器网络的增强型蒙特卡罗定位跟踪算法[J]. 电子与信息学报,2010,32:864-868.

WANG J,WANG H Y,GAO Q H,et al. Enhanced monte carlo localization and tracking algorithm for mobile wireless sensor network [J]. Journal of Electronics & Information Technology,2010,32:864-868.

[18]BILLAH B,KING M L,SNYDER R D,et al. Exponential smoothing model selection for forecasting[J]. International Journal of Forecasting,2006,22(2):239-247.

[19] 王冬星,朱建秋,杨引霞. 一种指数平滑预测的参数优化方法及实现[J]. 微机发展,2005,15(3):1-4.

WANG D X,ZHU J Q,YANG Y X. A method of optimizing parameter of exponent smoothing prediction and implementation[J]. Microcomputer Development,2005,15(3):1-4.

[20]叶中行,曹奕剑. Hurst指数在股票市场有效性分析中的应用[J]. 系统工程,2001,19(3):21-24.

[21]吴拥政. 重标极差法及其应用[J]. 理论新探,2004,8(176):23-24.

[22] 孟祥磊. 基于Hurst指数的中国股指期货市场有效性研究[D]. 哈尔滨：哈尔滨工业大学,2014:22.

MENG X L. Research on the efficiency of China stock index futures market based on hurst exponent [D]. Harbin:Harbin Institute of Technology,2014:22.

[23]RUDAFSHANI M,DATTA S. Localization in wireless sensor networks[C]∥Proceedings of the 6th International Conference on Information Processing in Sensor Networks. Cambridge,MA:IEEE,2007:51-60.

【中文责编：庄晓琼 英文责编：肖菁】

A Localization Algorithm Based on Index Smoothing Prediction Model for Mobile Nodes

SHAN Zhilong1,2*， WANG Xuanlin1

(1. School of Computer Science,South China Normal University,Guangzhou 510631,China; 2. School of Network Education,South China Normal University,Guangzhou 510631,China)

To solve the problem of low location accuracy of mobile nodes in Wireless Sensor Network, an algorithm based on index smoothing prediction model is proposed in this paper. By applying the Smoothing Prediction Model in the algorithm, the information of nodes’ speed and direction is obtained, and according to the nodes’ historical trajectory the accuracy of sampling area through the application of Hurst Exponent is further improved. By this way, the above information to predict the unknown node’s next state is used and the “high quality sample” is obtained. Moreover, by making use of the “high quality sample” the “valid sample rectangular box” is constructed, which can decrease the number of sampling. The simulation result shows that the proposed algorithm has improved the location accuracy in the context of different time, velocity, radius and anchor density, showing good performance.

index smoothing prediction; Hurst exponent;R/Sanalysis; rectangular box; localization

2016-04-21 《华南师范大学学报(自然科学版)》网址：http://journal.scnu.edu.cn/n

国家自然科学基金项目(61671213，61370003)；广东省自然科学基金项目(2015A030313395，2016A030308006)；广东省科技计划项目(2013B040401014)

TP393

A

1000-5463(2016)05-0123-06

*通讯作者:单志龙，教授，Email:zhilongshan@gmail.com.