基于通用相关的无线传感网络节点快速定位算法*

陈佳媛，杨 丹

（常州工学院计算机信息工程学院，江苏 常州 213032）

0 引 言

无线传感器网络中，许多的应用场合都需要有节点自身的位置信息，以便向用户提供有价值的服务，没有节点自身位置信息的监测数据是没有什么实际意义的[1]。例如，在仓储式超市中，对商品进行分类存放，根据存放类别再划分区域，同时在购物车上安置一个无线收发器，配置WSN每一个货架节点位置信息，顾客在购物时，就可以根据所需要的货物与自己的购物车的位置信息，快速准确找到所需要的货物。再如，对于天然气管道监测的应用，如果在某一处有漏气点，人们最关心的首要问题是漏气点的位置信息，以便进行处置。因此，节点的位置信息对于很多场景是至关重要的。

1 研究背景和意义

随着信息技术向物联智能化网络方向的发展，现实的物理世界和以计算机控制技术为核心的物联网融合需求越来越迫切，定位则成为连接物理世界和计算机网络技术的桥梁纽带[2]。

定位是利用电磁波信号确定目标的位置信息，位置信息是确定被监测目标与场景位置，方向等信息的最直接方法，是移动计算、物联网技术、普适计算等基于地理位置信息服务的基础。位置信息对物联网技术应用和基于位置信息服务的移动计算领域有着非常重要意义。因此，无线传感器网络节点定位技术也就成为学术界研究的热点之一[3]。

无线传感器网络节点定位技术主要分成基于测距的定位技术和非测距的定位技术二大类。基于测距定位技术主要包括：信号强度定位（Received Signal Strength Indication，RSSI）算法，时间差定位（TIme difference of Arrival，TDOA）算法，到达时间定位（TIme of Arrival，TOA）算法，以及到达角度定位（Arrival Of Angle，AOA）算法。这一类算法主要是通过传感器节点配备的测量电路硬件以及算法，精确测量目标距离及方位来实现节点定位，定位精度高。非测距定位主要包括：基于网络中跳数的 DV-HOP（Distance Vector，HOP）定位算法，基于网络连通性质心的Amorphous算法，以及基于区域划分的（Approximare Point In Triangulation Test）APIT定位算法。这些算法是利用节点连通性和路由交换信息等技术，估算未知节点与信标节点间的距离，从而实现定位。该类算法无需依托硬件支持。因此，可以减少开支和功耗，但估算节点间距离时会产生较大误差，定位精度较低[3-5]。

2 微弱信号检测

在野外恶劣环境下，定位信号往往被淹没在噪声中。此时，便需要有从噪声中检测定位信号的方法和技术。根据定位信号自身具有周期性和噪声信号随机性这些特点，通过自相关或互相关检测算法，应用于微弱定位信号的相关检测中，从而实现从噪声中提取周期性定位信号，得到精确的定位数据，达到定位目的[6-7]。

2.1 互相关算法的工作原理

互相关测距是一种实时动态测量方式。基本工作原理是：激光发射器向探测目标发射一周期性测量信号（可根据探测距离确定测量信号波长），测量信号碰到目标后，被反射回来形成回波信号，然后将这二路信号进行互相关分析处理，将距离的测量转化成对这二路信号时间间隔（て）的测量。图1所示为激光互相关测距示意图。图1中：S是被测目标与激光发射器和接收器的距离。て为激光传播的延时。

图1 激光互相关测距示意图

激光从发射器发射周期性探测波信号并以一定的波速传播。当探测波遇到目标物后，探测波将会发生反射现象，部分探测波从原路返回至接收器。因此，根据激光从发射探测波起到接收反射回来探测波的时间差。再加上已知环境中探测波的传播速度，就可以计算出激光传播的距离。从而计算出目标的距离。

2.2 通用互相关法计算延时

互相关法计算延时て，可以通过求二路信号的互相关值来估算。设S1（t）为发射器的发射信号。S2（t）为接收器接收到的信号。D是经过传播后的延时，n（t）是均值为0，方差为1的高斯白噪声。则：

其中，α为S1（t）经传播后的衰减，为计算方便，不妨设α=1。

由于噪声与信号互不相关，所以式（3）中RS1n（τ）=0。

由式（3）可知，S1（t），S2（t）互相关函数取得最大值时，RS1S1（τ-D）也取得最大值。而 RS1S1（τ-D）≤RS1S1（0），所有取得最大值时的て，即为延时D，即：τ=D 时 RS1S1（τ）取得最大值。

当 S1（t），S2（t）是紧密相关的信号时，RS1S2（τ）将会有一个很突出的相关峰出现，图 2为S1（t）与 S2（t）相关函数仿真波形。

图2 为 S1（t）与 S2（t）相关函数仿真波形

3 快速互相关峰值搜索算法

通过D/A对采集的信号数字化，其互相关函数的表达式为：

式中，N为积分区间上的采样数据总数，τj为τ的取值序列，τj的取值间隔与数据采样间隔相同。

若采集数字信号经相关处理得到τ0后，传播延时可由式（5）求出：

式中，fs为采样频率，C为信号传播速度。

式（4）中，j每变化一次，RS1S2（τj）就需要重新计算一次，故RS1S2（τj）的计算工作量是非常大的。

实际计算时，由于求 S1（t），S2（t）相关函数的过程是乘和加的运算。若不进行算法改进，则计算工作量很大。例如：在采样点数为512时，做一次延时计算则需要1 024×1 024次乘和加的运算。由于计算工作量大，造成定位的实时性受到影响，因而不实用。虽然可以采用降低采样率，减少计算次数的方法来提高运算速度，但这会造成延时的估计误差，达不到预期精度。通过对相关函数波形（见图2）分析可以看出，互相关法求延时的过程，实际上就是找互相关函数最大值的过程。而在互相关结果附近存在明显的最大峰特性，因而采用一定步长点数找互相关峰是一种快速有效的方法。其原理是：对采集的信号求互相关时，点数不是逐点的变化，而是一次进行多个点的跳跃计算，如每次进行n个点的跳跃计算，找出相关峰值存在的一个小区间，然后在该小区间再找出最大峰值位置。再以已经找到的最大点为中心，左右各扫描n-1个点，和已经求得的最大值比较，以确定下一个搜索中心。这样既可以减少计算点数，加快计算速度，又可以保证测量精度。

具体实现方法：在对采样得到的信号序列求相关时。采用“不定步长峰值搜索”进行互相关函数最大峰值确定，也就是求互相关峰值时，点数不是逐点的变化，而是一次进行多个点的跳跃式计算。例如：第1次进行n个点的跳跃式计算，找到相关峰值存在的一个区间，第二次进行n/2个点的跳跃式计算，找到相关峰值存在的一个较小的区间。依次数推，直到步长为1。最终求出相关峰值的值及位量。改进的算法表达式为：

具体实现步骤如下：

第 1 步：取步长为 n（n=2k），以 n 步长在 Rxy（n）中取出对应元素，组成新的序列RxyN（n），在新序列RxyN（n）中找出最大值MN及其位置LMN。

11xy再以LMN为中心，以n1为新的步长，取出对应元素，组成新序列 RxyN1（n），再在新序列 RxyN1（n）中，再次找出最大值MN1及位置LMN1。

22xy中再次以LMN1为中心，以n2为新的步长，取出对应元素，组成新序列RxyN2（n），再次在序列RxyN2（n）中，再一次找出最大值MN2及其位置LMN2。

以此类推，直至步长为1的序列搜索到最大值为止。便可确定互相关函数的最大值及对应位置，这样的算法可以使互相关的计算量减少到原

算法流程图如图3所示，其中Max_Value为记录最大值的变量，Max_P为记录最大值所在的位置，max_P_tem为找到的最大值点位置的临时变量，step_k为搜索步长变量，step_k_tem为步长的临时变量。

图3 算法流程

4 实验及仿真结果分析

利用Matlab进行算法仿真，仿真中，用调频（Frequency Modulation，FM）信号叠加上均值为“0”，方差为“1”的高斯白噪声，且信噪比（Signal-noiseRatio，SNR）为2的条件下进行仿真，仿真程序如下：

图4为延时d=30的仿真图。通过对改进算法仿真可以看出，理论上的延时与仿真得到的延时完全吻合，取得了非常好的效果。经实验，在采样点为512的情况下，一次通常的互相关计算时间为2 s，而改进算法，若K=2时，计算时间为0.25 s。若K=3时，计算时间为31.3 ms，与理论值很吻合。同时证明，采用此种快速计算方法具有很实用的价值。

图4 延时d=30的仿真图

5 结 语

本文针对通用互相关求延时计算量大的问题，提出了“不定长峰值搜索”改进算法，并进行了MatLab仿真和实验。仿真和实验结果表明，改进后的算法明显优于改进前的通用互相关算法。改进后的算法性能优越，在保证计算精度的情况下，极大地提高了计算速度，具有很好的实用性及广阔的市场应用前景。