基于通用相關的無線傳感網絡節點快速定位算法*

陳佳媛，楊 丹

（常州工學院計算機信息工程學院，江蘇 常州 213032）

0 引 言

無線傳感器網絡中，許多的應用場合都需要有節點自身的位置信息，以便向用戶提供有價值的服務，沒有節點自身位置信息的監測數據是沒有什么實際意義的[1]。例如，在倉儲式超市中，對商品進行分類存放，根據存放類別再劃分區域，同時在購物車上安置一個無線收發器，配置WSN每一個貨架節點位置信息，顧客在購物時，就可以根據所需要的貨物與自己的購物車的位置信息，快速準確找到所需要的貨物。再如，對于天然氣管道監測的應用，如果在某一處有漏氣點，人們最關心的首要問題是漏氣點的位置信息，以便進行處置。因此，節點的位置信息對于很多場景是至關重要的。

1 研究背景和意義

隨著信息技術向物聯智能化網絡方向的發展，現實的物理世界和以計算機控制技術為核心的物聯網融合需求越來越迫切，定位則成為連接物理世界和計算機網絡技術的橋梁紐帶[2]。

定位是利用電磁波信號確定目標的位置信息，位置信息是確定被監測目標與場景位置，方向等信息的最直接方法，是移動計算、物聯網技術、普適計算等基于地理位置信息服務的基礎。位置信息對物聯網技術應用和基于位置信息服務的移動計算領域有著非常重要意義。因此，無線傳感器網絡節點定位技術也就成為學術界研究的熱點之一[3]。

無線傳感器網絡節點定位技術主要分成基于測距的定位技術和非測距的定位技術二大類?；跍y距定位技術主要包括：信號強度定位（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 互相關算法的工作原理

互相關測距是一種實時動態測量方式?；竟ぷ髟硎牵杭す獍l射器向探測目標發射一周期性測量信號（可根據探測距離確定測量信號波長），測量信號碰到目標后，被反射回來形成回波信號，然后將這二路信號進行互相關分析處理，將距離的測量轉化成對這二路信號時間間隔（て）的測量。圖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仿真和實驗。仿真和實驗結果表明，改進后的算法明顯優于改進前的通用互相關算法。改進后的算法性能優越，在保證計算精度的情況下，極大地提高了計算速度，具有很好的實用性及廣闊的市場應用前景。